[PintOS] Project1-2 Alarm Clock

목표

Alarm Clock기능을 구현해 쓰레드를 일정시간(ticks) 대기상태에서 준비상태로 전환시킨다.

---

Alarm Clock

Alarm Clock은 지정된 시간(tick)에 스레드를 깨우는 기능이다. 특정 시간 후에 작업을 수행해야 하는 경우 (예: 주기적인 작업, 타임아웃 처리 등)에 사용할 수 있다.

---

도출과정

초기 Pintos의 timer_sleep기능은 일정 시간(tick)동안 실행상태의 쓰레드를 지속적으로 준비상태로 바꾸는 busy wait 방식이다.

이를 해결하기 위해 쓰레드를 대기(block)상태로 전환뒤 다른 컨텍스트들을 실행하다 깨워야하는 시간이 됐으면 unblock하는 방식으로 구현을 진행한다.

대기(block)상태의 쓰레드를 unblock시킬 컨텍스트가 필요하다 timer인터럽트는 매 tick발생해 ticks를 증가 시킨다 timer인터럽트에서 조건을 체크해 block된 쓰레드를 깨운다.

이를 위해선 쓰레드구조체 필드변수 하나와 하나의 리스트, 하나의 lcok와 세가지 함수가 필요하다

• wakeup_tick
• sleep_list
• sleep_lock
• thread_sleep
• thread_wakeup 또는 thread_check_sleep_list

wakeup_tick

쓰레드 구조체 필드에 sleep된 쓰레드를 깨울때 기준으로 사용되는 변수 wakeup_tick을 만든다

sleep_list

block된 쓰레드들을 관리할 별도의 sleep_list가 필요하다 이 리스트는 thread_sleep에 의해 block된 쓰레드들을 저장했다가 깨울시간이 되면 해당 쓰레드를 깨우는데 사용된다

이 리스트는 thread_start를 진행할때 초기화를 한다

sleep_lock

공유변수 sleep_list는 race condition문제가 발생한다. 해결하기위해 사용할 세마포어 lock을 사용한다.

thread_sleep

일정시간 동안 block시킬 쓰레드를 sleep_list에 먼저 깨울 틱순으로 tick 오름차순 저장하고 block시키는 함수다

thread_check_sleep_list

인터럽트마다 sleep_list의 front의 틱을 확인해 현재 시간(ticks)이 깨울 틱(wakeup_tick)을 넘으면 해당 쓰레드를 sleep list에서 제거하고 unblock시킨다.

---

구현

struct thread

struct thread {
    /* Owned by thread.c. */
    tid_t tid;                          /* Thread identifier. */
    enum thread_status status;          /* Thread state. */
    char name[16];                      /* Name (for debugging purposes). */
    int priority;                       /* Priority. */

            ...

    unsigned magic;                     /* Detects stack overflow. */
    int64_t wakeup_tick; // 슬립 쓰레드 시간되면 깨우는 틱
}

timer_sleep

/* 대략 TICKS 타이머 틱 동안 실행을 일시 중단합니다. */
void timer_sleep (int64_t ticks) {
    int64_t start = timer_ticks ();

    ASSERT (intr_get_level () == INTR_ON);

    if(timer_elapsed(start) < ticks) // 끝나고자하는 tick보다 작다면 쓰레드 슬립
        thread_sleep(start + ticks);
}

timer_interrupt

/* Timer interrupt handler. */
/* 타이머 인터럽트 핸들러. */
static void timer_interrupt (struct intr_frame *args UNUSED) {
    ticks++;
    thread_tick ();
    thread_check_sleep_list(); // 매 인터럽트마다 리스트를 확인해 쓰레드 깨우기
}

thread_sleep

void thread_sleep(int64_t end_tick){
    enum intr_level old_level;
    struct thread *cur = thread_current();

    ASSERT(!intr_context());
    ASSERT(cur != idle_thread);

    old_level = intr_disable();
    cur->wakeup_tick = end_tick; // 쓰레드에 종료틱 설정

    lock_acquire(&sleep_lock); // 슬립리스트는 공유 변수이니까 락 설정

    list_insert_ordered(&sleep_list, &cur->elem, tick_less, NULL); // 슬립리스트에 종료틱 오름차순으로 삽입
    lock_release(&sleep_lock); // 슬립락 해제

    thread_block(); // 현재 쓰레드 블록

    intr_set_level(old_level);
}

thread_check_sleep_list

void thread_check_sleep_list(){
    enum intr_level old_level;
    struct thread *t;
    old_level = intr_disable();
    int64_t ticks = timer_ticks();
    // lock_acquire(&sleep_lock); // 인터럽트 컨텍스트에는 락을 걸면 안됨
    while (!list_empty(&sleep_list)) { // 슬립 리스트에서 꺠울 쓰레드 탐색
        t = list_entry(list_front(&sleep_list), struct thread, elem); // 슬립 리스트 맨 앞 쓰레드 조회
        if (t->wakeup_tick > ticks) { // 쓰레드가 현재 글로벌 틱보다 크다면 탐색 종료
            break;
        }
        list_pop_front(&sleep_list); // 쓰레드가 현재 글로벌 틱보다 작거나 같다면 슬립 리스트에서 제거
        thread_unblock(t); // 해당 쓰레드 언블록
    }
    // lock_release(&sleep_lock);
    intr_set_level(old_level);
}

구현도중 발생한 문제점

sleep_list의 race condition문제 해결을 위해 thread_sleep과 thread_check_sleep_list함수에서 sleep_list를 수정할 때 lock을 사용해 동시성을 해결하고자 했다. 하지만, thread_check_sleep_list함수에서 lock_acuire을 사용하면 현재 실행중인 컨텍스트가 인터럽트라는 ASSERT에러가 발생했다.

---

문제해결

만약 어떤 쓰레드가 lock A을 획득하고 실행중일때 인터럽트가 실행되면 그 인터럽트도 똑같은 lock A를 요청한다면 해당 인터럽트는 block이 되어 실행되지 못하고 무한 대기상태에 빠져 교착 상태가 발생했을 것이다.
어차피 우리 PintOS는 컨텍스트 스위칭이 타이머 인터럽트에 의해 thread_tick이 증가하면 일어나기 때문에 인터럽트만 비활성화 해주면 race condition이 발생하지 않는다.

---

test 실행

test check결과 8개 PASS

 

GitHub - hyunS00/pintos-kaist: 크래프톤 정글 5기 Pint OS