[PintOS] Thread - Alarm Clock (Project 1)

KAIST Jungle 7주차, OS 프로젝트를 진행하며 학습한 내용을 정리한 글입니다.

 

들어가기 전에

프로세스는 뭐고 스레드는 뭔가요? [유튜브 영상 강의]

• CPU의 동시성은 여러 작업을 일부분씩 context switching 하면서 진행됨
  • A, B, C 작업 동시 처리 시 순서대로 A(5% 수행)▶️ B(5% 수행) ▶️ C(5% 수행) ▶️ A(10% 수행)▶️ B(10% 수행) ▶️ C(10% 수행) ... (반복) ▶️ A(100% 수행)▶️ B(100% 수행) ▶️C(100% 수행)
• 병렬성은 프로세스 하나에 코어 여러 개가 달려서 각각이 작업을 동시에 진행하는 것(작업분담)
  • 첫 번째 코어에서 A작업, 두 번째 코어에서 B작업, 세 번째 코어에서 C작업을 같은 시점에 작업함
• 한 프로세스(ex. 크롬) 내에서 다양한 작업이 진행되어야 할 때 💡 Thread
  • Thread는 프로세스마다 주어진 전체 자원을 함께 사용하는 것
    • 장점: 속도, 효율 ⬆️
    • 단점: Thread가 동시에 자원을 사용하게 되는 경우, 이로 인한 error가 발생하기 쉽다는 단점이 있음
      • 싱크로나이즈(synchronize) : 둘 이상의 스레드가 동시에 자원을 사용하지 못 하도록 함

커널 스레드(Kernel Treads)

• 커널 스레드는 운영 체제의 핵심 부분에서 실행되는 Thread
  • 이들은 하드웨어와 직접 상호 작용하고, 시스템 자원을 관리하며, 사용자 수준의 스레드 및 프로세스에 서비스를 제공함
• PintOS 구현에 필수적인 사항: Thread 스케줄링, Thread 생성 및 종료,Thread 간 동기화(예: 세마포어, 락), 우선 순위 스케줄링을 지원 ➡️ 이를 통해 운영 체제가 다양한 작업을 효율적으로 관리할 수 있음

싱크로나이즈(synchronization) - 과제 설명서 기반 정리

특히나 OS kernel의 Thread 간 자원을 공유할 때 통제된 형식(controlled fashion)을 지키지 않는다면 big mess한 결과를 볼 수 있다. PintOS에서는 이를 막기 위해 다양한 다양한 synchronization 함수(primitives)를 제공한다.

• Disabling Interrupts
  • Synchronization을 하는 가장 단순한 방법은 interrupts를 불가능하게 하는 것
  • interrupts가 켜져 있으면, 진행 중인 Thread가 언제든 다른 Thread에 의해 선점(preempt)될 수 있음(error 발생 가능)
  • interrupts를 끄면, 진행중인 Thread 선점이 불가능함
    • Thread 선점은 time interrupts(시스템 타이머로부터 정해진 시간 간격에 따라 interrupts 발생)에 의해 이뤄지기 때문
    • 다만Interrupts 비활성화 되어 있다면 OS는 시스템의 제어권을 다시 얻을 수 없음(악의적 프로그램이 프로세스 독점을 가능하게 함)
  • 일반적인 Unix 시스템은 '선점불가능(nonpreemptible)'이지만, PintOS는 '선점가능한(preemptible)' Kernel임
    • '선점가능한' Kernel의 경우 명시적인 synchronization이 더욱 필요함
  • 외부 interrupts handler와 kernel thread를 동기화시키기 위함
    • 외부 interrupts handler는 잠들게 할 수 없기에 비활성화 시키지 않고는 동기화가 거의 불가능 함

(참고) 수정해야 할 전체 코드 라인 수

과제 설명서 내 FAQ

Alarm Clock(OS, "Thread 일정 시간 이후에 일어나")

Alarm Clock 과제는 timer_sleep() 함수를 재구현하는 과제이다. 기존에 구현되어 있는 방식은 busy-waiting 방식으로 'OS에서 Thread를 재웠다가 곧바로 시간을 확인하고 아직 일어날 시간이 아니라면 다시 재우고 또, 곧바로 시간을 확인하는 과정을 반복하는 것'이다. 이는 Thread의 상태가 Running ↔️ Ready를 반복한다.

조금 더 풀어서 과정을 보면, Running 상태에서 sleep 명령을 받은 Thread는 Ready 상태가 되고 ready queue에 추가 된다. Ready queue에 있는 Threads는 일어날 시간이 아님에도 상관없이 깨워져서 Running 상태가 된다. 일어날 시간이 아니었기에 다시 Ready 상태가 되고, ready queue에 추가된다.

Sleep/Wake up 기반의 Alarm Clock 구현

기존 방식에서 Running ↔️ Ready 상태가  반복적으로(while문 안에서) 깨어날 시간까지 실행되는 비효율을 해결하기 위해 Ready 상태로 전환하는 것이 아닌 Block 상태로 전환해 Block 상태인 것은 깨어날 시간이 되기 전엔 스케쥴링에 포함되지 않도록 수정한다. 깨어날 시간이 되었을 때, Block 상태를 ➡️ Ready 상태로 바꾸어준다.

 

Sleep queue 자료 구조 추가

/* List of processes in THREAD_READY state, that is, processes
   that are ready to run but not actually running. */
static struct list ready_list;
static struct list sleep_list;

...

void thread_init(void) {
	...
    /* Init the globla thread context */
    lock_init(&tid_lock);
    list_init(&ready_list);
    list_init(&sleep_list);
    list_init(&destruction_req);
   ...
}

Sleep 되어 있는 Threads를 저장할 queue 구조체를 선언한다. 이후 Thread 초기화 시 sleep_list를 함께 초기화되도록 한다. 이 sleep_list는 Block 상태의 Threads가 저장되어 깨어날 시간이 되기 전까지 머무르는 곳이다.

 

Thread_sleep() 함수 구현

void thread_sleep(int64_t ticks) {
    struct thread *curr = thread_current();
    enum intr_level old_level;

    ASSERT(!intr_context());

     old_level = intr_disable(); // Disabling Interrupts
    if (curr != idle_thread) { 			// idle thread는 sleep 되지 않아야 함
        curr->wakeup_tick = ticks;                // 현재 thread에 일어나야 하는 시간 저장
        list_push_back(&sleep_list, &curr->elem); // sleep queue에 push back
        thread_block();			        // thread block 상태로 전환
    }

    intr_set_level(old_level);   // Anabling Interrupts
}

Thread를 sleep queue에 삽입(list_push_back())하고, blocked 상태로 만들어서 대기한다. 이때, Disabling Interrupts를 통해 과정 중 Interrupts를 받아들이지 않고, thread를 Block 상태로의 전환 후에 Interrupts를 받아들인다(Anabling Interrupts). 

 

timer_sleep() 함수 수정

void timer_sleep(int64_t ticks) {
    int64_t start = timer_ticks();

    ASSERT(intr_get_level() == INTR_ON);
    thread_sleep(start + ticks);       // 현재 tick + 자야하는 tick = 깨어나야할 시각
}

Interrupts를 받아들이고 있을 때(Interrupts ON), 현재 OS의 tick(시간)에 자야하는 시간 tick을 더해서 깨어나야할 '시각'을 구하여 thread_sleep() 함수의 인자로 사용한다. 💡 즉, 현재 threads는 OS의 tick이 'start + tick'일 때 wake up 하게 된다.

 

timer_interrupt() 함수

static void timer_interrupt(struct intr_frame *args UNUSED) {
    ticks++;
    thread_tick();
    thread_awake(ticks);
}

timer_interrup() 함수에 thread_awake(ticks)를 추가하여서 ticks가 증가할 때마다 wake up할 수 있는 Thread가 있는지 찾고, Ready 상태로 전환시켜 준다. 이로써 Sleep/Wake up 방식으로 구현이 가능하다.

 

🐛 발생한 Bug

Alarm Clock 구현 중 발생한 Bug(Kernel PANIC)

thread_sleep() 함수 구현 중 발생했던 'Keral PANIC' error이다. 구현 결과를 살펴보면, 아래와 같다.

Timer: 27 ticks
Thread: 1 idle ticks, 26 kernel ticks, 0 user ticks

26 kernel ticks와 1 idle ticks 후, Kernel PANIC으로 test가 failed 했다.

Kernel PANIC

이는 "LINUX 시스템에 심각한 오류가 생겨 시스템을 다운시키는 동작"이라고 한다. Thread 구현 중 해당 오류가 발생할 수 있는 경우로 '자원의 고갈', '시스템의 불안정성', '오류 처리의 실패', '디버깅 및 오류 보고 매커니즘'을 들 수 있다(by Chat GPT). 시스템에 충분한 자원이 없게 되었을 경우가 있음을 알 수 있었다.

문제는 sleep_list에 push back 하는 current thread의 ticks가 할당되지 않았기에 발생했고, 이로인해 Kernel에서 이 Thread들을 다시 Wake up 시키지 못했기에 발생한 오류였다. 그래서 26 ticks의 kernel과 1 ticks의 idle 후에 사용할 수 있는 자원이 없어 Kernel Panic이 발생한 것이다.