[PintOS] Project 1 : Alarm Clock 구현

Alarm Clock

운영체제의 Alarm clock 기능이란 운영체제가 실행중인 스레드를 잠시 재웠다가 일정 시간이 지나면 다시 깨우도록 하는 것이다.

Busy Wait

어떤 조건이 충족될 때 까지 CPU를 계속 돌리며 루프를 도는 방식의 대기

→ 문제 : 실제 대기 중인 상태에서도 CPU를 계속 사용함

Sleep-awake (잠자는 스레드)

일정 시간 동안 스레드를 block 상태로 전환
→ 해당 스레드는 스케줄러에서 제외되고, CPU는 다른 스레드에게 양보됨
→ 시간이 지나면 timer interrupt가 깨워줌

과제 관련 개념 이해

위의 과제를 들어가기 전에 선행으로 이해가 필요했던 내용을 간략히 적어봅니다.

프로세스 상태 전이 (State Transition)

1. Ready 상태
   • 프로세스가 실행할 준비는 되었지만, 아직 CPU를 받지 못한 상태
   • 생성되고 메모리 로딩이 끝남
   • CPU 스케줄러가 실행 기회를 줄 때까지 대기한다
2. Running 상태
   • 프로세스가 CPU를 점유해서 실행 중인 상태
   • 스케줄러가 Ready 상태 프로세스를 선택하여 CPU를 줬을 때 이 상태로 전환한다
   • 프로그램 카운터를 기반으로 명령어를 수행한다.
   • 이 상태는 일시적이다 :
     • CPU 타임 슬라이스가 끝나면 다시 ready 상태로 돌아오거나
     • I/O의 요청으로 Blocked 상태로 갈 수 있다.
3. Blocked 상태
   • 프로세스가 I/O 요청 등 외부 이벤트를 기다리는 중이라 실행 불가능한 상태

Double-Linked List

Pintos에서 사용하는 list는 더블리 링크드 리스트(double-linked list) 구조이다. 즉, 각 노드(여기서는 list_elem)가 앞 노드와 뒷 노드에 대한 포인터를 모두 가지고 있다.

PintOS 의 list_elem 구조체는 다음과 같이 정의되어 있다.

struct list_elem {
  struct list_elem *prev;     /* Previous list element. */
  struct list_elem *next;     /* Next list element. */
};

 

왜 이러한 구조를 사용할까?

• 중간 노드 삭제가 빠르다
• 단방향 리스트에서는 삭제하려면 이전 노드를 탐색해야 하지만, 더블리 링크드 리스트는 prev 포인터 덕분에 현재 노드만 알면 삭제할 수 있다.
• 앞뒤로 자유롭게 순회 가능
• 예를 들어, 리스트를 거꾸로 탐색하거나, 우선순위 정렬을 할 때 유용하다.
• 스레드 구조체가 다양한 리스트에 들어갈 수 있도록 효율적인 삽입/삭제를 지원

Thread 구조체와 list_elem

그러면 PintOS에서는 더블리 링크드 리스트를 어떻게 활용하고 있을까?

운영체제는 여러 스레드를 다양한 리스트에 넣어 관리합니다. 예를 들어:

• ready_list: 준비 상태의 스레드들을 담는 리스트
• sleep_list: 자고 있는 스레드들을 담는 리스트
• donations: 우선순위 기부 목록으로 사용되는 리스트

그런데 C 언어는 리스트에 구조체를 그대로 넣을 수 없고, 포인터를 써서 '링크 노드'를 따로 관리해야 하기 때문에 struct thread 안에 list_elem을 넣어두고, 이걸 이용해 리스트를 만든다.

즉, 이렇게 각 스레드가 자기 안에 list_elem을 가지고 있고, 이 요소를 기준으로 연결된다. 이것을 기억하고 함수를 구현해야 잘못된 구조체를 참조하지 않을 수 있다.

구현 목표

• loop 기반 wait() -> sleep-awake 로 변경
• timer_sleep() 호출시 thread를 ready_list에서 제거, sleep queue에 추가
• wake up 수행timer interrupt가 발생시 tick 체크시간이 다 된 thread는 sleep queue에서 삭제하고, ready_list에 추가

구현

자료구조 추가

include/threads/thread.h

Sleep queue 자료구조를 추가하고, 연결리스트 내부의 sleep_elem 으로 데이터 노드끼리 연결한다.

일어날 시간을 저장하는 wakeup_tick 변수를 추가한다.

struct thread {
    ... 
    **struct list_elem sleep_elem;
    int64_t wakeup_tick;
    ...**
}

 

devices/timer.c

sleep queue 자료구조를 정의한다.

static struct list sleep_list;

수정 / 추가 함수 구현

devices/timer.c : timer_sleep()

• 현재의 tick 수를 start에 저장하고
• wakeup 시점을 정의한다. start 시점부터 + ticks (일정 시간) 이 지난 후에 깨어나도록 설정한다.
• ASSERT로 인터럽트가 활성화 되어있는지 확인한다 (기본 설정)
  • 임계 영역에 진입하기 전에, 현재 상태를 old_level 로 저장하고 인터럽트를 비활성화 한다.
• 현재 실행중인 스레드를 포인터로 설정하고, 해당 스레드의 wakeup_tick 필드에 깨어날 시간을 저장한다.
• Sleep list에 저장될 때, 일어날 시간을 기준으로 정렬하여 삽입한다.
• 현재 스레드를 block 상태로 바꾸고 schedular에서 제외한다.
• 스레드가 깨어날 때, 인터럽트를 기존 상태로 복원한다.

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

    ASSERT(intr_get_level() == INTR_ON);

    enum intr_level old_level = intr_disable();

    struct thread *cur = thread_current();
    cur->wakeup_tick = wakeup;

    list_insert_ordered(&sleep_list, &cur->elem, cmp_wakeup_time, NULL);
    thread_block();
    intr_set_level (old_level);
}

 

devices/timer.c : timer_interrupt()

• 타이머 인터럽트가 발생하면 현재 상태를 old_level로 저장하고 임계 영역에 진입하기 전에 인터럽트를 비활성화 한다.
  • 이유는 한 번에 여러 인터럽트가 발생하면, 여러 스레드가 동시에 임계 영역에 진입하는 것을 방지하기 위함이다.
• Sleep queue를 순차적으로 확인하며, 각 스레드의 깨울 시간을 확인한다.
• 깨울 시간이 지난 스레드는 슬립 큐에서 제거하고 thread_unblock을 호출하여 실행 대기 상태로 만든다.
• 이후 스케줄러는 실행할 스레드를 선택하고 스레드를 전환한다.

static void
timer_interrupt (struct intr_frame *args UNUSED) {
    ticks++;
    enum intr_level old_level = intr_disable();

    while(!list_empty(&sleep_list)){
        struct thread *t = list_entry(list_front(&sleep_list), struct thread, elem);
        if(t->wakeup_tick > ticks)
            break;
        list_pop_front(&sleep_list);
        thread_unblock(t);
    }
    intr_set_level(old_level);
    thread_tick ();
}

 

devices/timer.c : cmp_wakeup_time()

• 두 sleep_queue 항목을 비교하여 wakeup_time 값을 기준으로 오름차순 정렬되게 한다
• a의 wakeup_time이 b의 wakeup_time 보다 작으면 true 반환하여 a가 먼저 온다
• 그렇지 않으면 false를 반환하여 b가 먼저 오도록 한다

bool
cmp_wakeup_time(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    struct thread *t_a = list_entry(a, struct thread, elem);
    struct thread *t_b = list_entry(b, struct thread, elem);

    return t_a->wakeup_tick < t_b->wakeup_tick;
}

테스트 결과