본문 바로가기
[Pint OS] 핀토스

[PintOS] 핀토스 뽀개기 - Threads 1 - Alarm Clock

by codeomni 2023. 12. 16.
반응형

 

틀린 내용은 댓글 부탁드립니다.

Alarm clock 정의

특정 시간(tick 수)이 지난 후 스레드를 ready 상태로 전환하여 다시 스케줄링하는 기능입니다.

운영체제(OS) 또는 커널 수준에서, 현재 시간을 기준으로 지정된 시간이 지나기까지 스레드를 잠재웠다가, 시간이 되면 스레드를 다시 실행 가능(ready) 상태로 복귀시키는 메커니즘을 말합니다. 스레드가 바로 실행되지 않고, 특정 시간까지 "대기"해야 하는 경우가 많습니다. (예: 입출력 대기, 타이머 기반 작업 등)

busy waiting 방식은 CPU를 낭비하므로, Alarm Clock처럼 block/wakeup 기반으로 효율적으로 대기해야 합니다.

 

 

사전 지식 - linux의 timer 

 

Linux의 alarm(2)은 seconds 단위로 알람을 예약합니다.

Pintos의 Alarm Clock은 ticks 단위로 시간을 관리하며, 스레드를 직접 block하고 이후 인터럽트 시 tick을 체크해 wakeup합니다.

 

 

문제 인식

대기는 busy waiting (바쁜 대기)과 blocking (차단 대기)으로 구분할 수 있습니다. 기본 PintOS는 timer_sleep()을 busy waiting 방식으로 구현합니다.

CPU 낭비 원하는 시간이 올 때까지 계속 CPU를 쓰면서 확인합니다. 다른 유용한 작업을 할 수 없습니다.
비효율적 멀티태스킹 여러 스레드가 sleep 요청을 하면 모두 busy waiting을 하므로 CPU가 과부하될 수 있습니다.

 

Busy-waiting 방식

busy waiting에서는 현재 스레드가 CPU를 계속 점유하면서, 원하는 시간이 될 때까지 while 루프를 돌며 깨어날 시점을 확인합니다. busy waiting은 시간 대기(timer_sleep)나 공유 자원 획득 대기(mutex 등) 상황에서 발생할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
/* timer.c */
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
    int64_t start = timer_ticks ();
 
    ASSERT (intr_get_level () == INTR_ON);
    
    while (timer_elapsed (start) < ticks)
        thread_yield ();
}

▲ 쓰레드의 상태를 확인하면 running 상태와 ready 상태를 반복합니다.

  • thread_yield () : cpu를 할당하고 ready_list에 스레드를 삽입한다.
  • timer_ticks() : 현재 틱 값을 반환한다.
  • timer_elased () : 시작 후 경과한 틱 수를 반환한다

주어진 틱까지 대기하는 루프 기반입니다. -> while문 기반(while (timer_elapsed (start) < ticks) 이 부분)

busy waiting 중에 thread_yield()를 통해 현재 스레드를 ready 상태로 만들고, 다른 스레드에 CPU를 양보합니다.

쓰레드가 지정된 시간까지 대기하는 동안 계속 실행된다.

이게 뭔 소리냐면, while문으로 tick만큼 CPU를 점유한 상태가 지속된다는 말이다.

 

thread_yield ()

해당 함수는 running 상태의 쓰레드를 비활성화하고 ready_list의 맨 뒤에 삽입합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* Yields the CPU.  
 * The current thread is not put to sleep and 
 * may be scheduled again immediately at the scheduler's whim. */
void
thread_yield (void) {
    struct thread *curr = thread_current ();
    enum intr_level old_level;
 
    ASSERT (!intr_context ());
 
    old_level = intr_disable ();
    if (curr != idle_thread)
        list_push_back (&ready_list, &curr->elem);
    do_schedule (THREAD_READY);
    intr_set_level (old_level);
}
  • intr_disable () - 인터럽트를 비활성화하고 이전 인터럽트 상태를 반환한다.
  • list_push_back () - 현재 쓰레드가 유휴 쓰레드가 아닐 경우, ready_list에 넣어준다.
  • do_schedule () - running 상태의 쓰레드를 ready 상태로 전환하기 위해 context switch 작업을 수행한다.
  • intr_set_level () - 매개 변수에 전달된 상태로 인터럽트 상태를 설정하고 이전 인터럽트 상태를 반환한다.

 

▲ thread_yield ()

busy waiting 도중 thread_yield()를 호출하면 현재 스레드가 ready 상태로 전환되어 ready_list로 이동합니다.

ready_list의 쓰레드는 본인의 순서가 될 경우 일어날 시간에 상관 없이 일어나서 running 상태가 됩니다.

 

과제(목표)는 Busy-waiting 방식에서 Sleep-wake up 방식으로 사용하도록 코드를 수정합니다.

1
2
3
4
5
6
7
8
/* thread.h */
/* States in a thread's life cycle. */
enum thread_status {
    THREAD_RUNNING,     /* Running thread. */
    THREAD_READY,       /* Not running but ready to run. */
    THREAD_BLOCKED,     /* Waiting for an event to trigger. */
    THREAD_DYING        /* About to be destroyed. */
};

단서는 thread.h에 사전에 쓰레드 상태가 정의되어 있습니다. 바쁜 대기에서는 쓰레드의 RUNNING 상태와 READY 상태를 사용합니다. 사용하지 않을 쓰레드를 BLOCKED 상태로 만들어서 관리해주면 됩니다.

Pint OS에는 모든 쓰레드들은 list로 관리하기 때문에 BLOCKED 상태인 쓰레드를 관리할 list도 만들어줍니다. (/lib/kernel/list.c)

 

ready_list 처럼 sleep 상태를 모아 놓을 공간인 sleep_list를 만들고, 쓰레드를 사용 시 thread_awake () 함수로 호출해서 ready_list로 옮깁니다.

쓰레드를 sleep으로 만들어 CPU 점유를 차단하고 필요시만 깨워서 사용하는 방법입니다.

수정 파일

threads/thread.*

devices/timer.*

Sleep-Wake 방식 구현

쓰레드를 sleep 상태가 되면 sleep_list에 block 상태로 넣고, 일어날 시간이 되면 wake해서 ready 상태로 ready_list에 넣습니다. sleep_list () 를 만들어서 timer_sleep() 호출을 통해 running 상태의 쓰레드를 blocked로 변경하고 sleep_list에 넣습니다. timer 인터럽트가 발생 시 tick을 확인해서 만료가 된 쓰레드를 sleep_list에서 삭제하고 ready_list에 넣습니다.

 

▲ Sleep-Wake 방식

 

1. sleep_list를 생성과 초기화와  wakeup_ticks 선언

1
2
/* /threads/thread.c */
static struct list sleep_list;

CPU를 점유 받기 위해 대기하는 쓰레드들의 ready_list처럼 잠자는 쓰레드를 관리할 sleep_list를 만들어 줍니다.

 

1
2
3
4
5
/* /threads/thread.c */
void
thread_init (void) {
    list_init(&sleep_list);
}

쓰레드 시스템을 초기화 할 때 sleep_list도 사용할 수 있도록 초기화합니다.

 

1
2
3
4
5
/* /include/threads/thread.h */
struct thread {
    /* Alarm Clock */
    int64_t wakeup_ticks;
};

또한 재운 각각의 쓰레드가 tick을 가지고 해당 ticks이 되면 일어날 수 있도록 쓰레드 구조체 안에 wakeup_ticks 변수를 만듭니다.

 

▲ 1번까지 구현한 상태입니다.

 

2. thread_sleep () 함수 구현

sleep_list를 만들었으니 현재 쓰레드를 재우는 함수를 구현합니다.

쓰레드를 재울 때 해당 쓰레드가 일어날 틱을 저장한 후에 sleep_list의 마지막 요소에 집어 넣습니다. sleep_list의 마지막 요소(tail)로 넣고 해당 쓰레드를 block 상태로 만들고 스케줄링합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* threads/thread.c */
void
thread_sleep (int64_t ticks) {
    struct thread *curr = thread_current();
    enum intr_level old_level;
 
    ASSERT (!intr_context ());
 
    old_level = intr_disable ();
 
    ASSERT(curr != idle_thread);
    
    // thread를 재울 때 일어날 시간을 저장한다.
    curr->wakeup_ticks = ticks;
    
    list_push_back(&sleep_list, &curr->elem);
    thread_block();
 
    intr_set_level (old_level);
}

 

3. timer의 timer_sleep () 함수 변경

타이머의 timer_sleep () 함수가 호출하면 해당 쓰레드의 대기 시간을 설정할 수 있습니다. 이 때 해당 쓰레드가 현재 대기하는 시점인 start부터 잠자고 있을 시간인 ticks 만큼으로 thread_sleep () 함수를 실행합니다.

1
2
3
4
5
6
7
8
9
10
/* /devices/timer.c */
void
timer_sleep (int64_t ticks) {
    int64_t start = timer_ticks ();
 
    ASSERT (intr_get_level () == INTR_ON);
 
    /* Alarm Clock */
    thread_sleep(start + ticks);
}

▲ timer_sleep() 함수가 호출되면 sleep_list의 마지막 요소(tail)로 넣어줍니다.

 

4. thread_awake () 함수 생성

sleep_list를 순회하며, wakeup_ticks ≤ 현재 ticks인 스레드만 sleep_list에서 제거하고 ready_list에 넣어 ready 상태로 만듭니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* /threads/thread.c */
void
thread_awake (int64_t ticks) {
    struct list_elem *e = list_begin (&sleep_list);
 
    enum intr_level old_level;
 
    old_level = intr_disable();
 
    while (e != list_end (&sleep_list)) {
        struct thread *curr = list_entry (e, struct thread, elem);
        if (curr->wakeup_ticks <= ticks) {
            e = list_remove (e);
            thread_unblock (curr);
        }
        else {
            e = list_next (e);
        }
    }
 
    intr_set_level (old_level);
}

 

5. timer_interrupt () 함수 수정

타이머가 설정한 간격마다 CPU가 시간을 추적하고 쓰레드들의 대기 시간이 지나면 해당 쓰레드를 깨울 수 있도록 합니다.

1
2
3
4
5
6
7
8
/* /devices/timer.c */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
    ticks++;
    thread_tick ();
 
    thread_awake (ticks);
}

 

6. 최종 결과

Pintos의 기본 alarm clock은 busy waiting을 사용하여 비효율적이었지만, sleep-wake 방식을 도입해 스레드를 block하고 wakeup_ticks 기준으로 깨우는 방식으로 개선할 수 있습니다.

▲ sleep_list 추가된 alarm clock 구조

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
FAIL tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
FAIL tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
FAIL tests/threads/priority-fifo
FAIL tests/threads/priority-preempt
FAIL tests/threads/priority-sema
FAIL tests/threads/priority-condvar
FAIL tests/threads/priority-donate-chain
FAIL tests/threads/mlfqs/mlfqs-load-1
FAIL tests/threads/mlfqs/mlfqs-load-60
FAIL tests/threads/mlfqs/mlfqs-load-avg
FAIL tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-10
FAIL tests/threads/mlfqs/mlfqs-block
20 of 27 tests failed.

 

저작자표시 비영리 변경금지 (새창열림)

댓글

티스토리툴바