PintOS는 알람을 구현할 때 기본적으로 busy waiting 방식을 사용한다.
따라서 sleep/wakeup 방식으로 개선하는 것이 목표이다.
기존의 timer_sleep 함수
timer_sleep 함수는, running중인 스레드를 지정된 ticks 동안 blocked 시키는 함수이다.
기존의 timer_sleep은 위 사진처럼 busy waiting이 일어나도록 설계되어 있다.
지정된 ticks가 지날 때 까지 while문 조건을 끝없이 검사하며 의미없이 CPU를 잡아먹는다.
즉, 지정된 시간을 기다리기만 할 뿐인 스레드가 무의미하게 while문을 돌며 CPU자원을 소모한다. 이것이 busy waiting이며, 개선해야 하는 부분이다.
어떻게 개선해야 하는가?
- thread 구조체에, 깨어나야 할 시간을 의미하는 Local Tick 필드를 추가하여 현재 시스템 Tick과 비교해 지정된 시간이 되면 깨우도록 하기.
- 매 timer interrupt 마다 thread_awake 함수가 작동하며, 지정된 Local Tick 시간이 되면 sleep_list에서 깨워 ready_list로 넣어주도록 하기.
thread.c
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. */
int64_t localTick ; // 로컬 틱 필드 추가
/* Shared between thread.c and synch.c. */
struct list_elem elem ; /* List element. */
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t * pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf ; /* Information for switching */
unsigned magic ; /* Detects stack overflow. */
};
우선 thread 구조체에 Local Tick을 의미하는 localTick 필드를 추가한다.
해당 필드 값을 보고 thread_awake 함수에서 깨울 지 말지를 검사한다.
thread.c
// ready_list 선언
static struct list ready_list ;
// sleep_list 선언
static struct list sleep_list ;
thread.c 파일에 ready_list는 이미 선언되어 있을 것이다. ready_list와 똑같은 형태로 sleep_list를 선언해 준다.
sleep_list에는 Sleep(Blocked)상태인 스레드들이 저장될 것이다.
thread.c
// 스레드 시스템 초기화 + PintOS의 초기 스레드 생성
// 여기서 run queue(ready_list) 초기화함
// sleep_list도 초기화하도록 추가해야 한다
void
thread_init ( void ) {
ASSERT ( intr_get_level () == INTR_OFF );
/* Reload the temporal gdt for the kernel
* This gdt does not include the user context.
* The kernel will rebuild the gdt with user context, in gdt_init (). */
struct desc_ptr gdt_ds = {
. size = sizeof ( gdt ) - 1 ,
. address = ( uint64_t ) gdt
};
lgdt ( & gdt_ds );
/* Init the globla thread context */
lock_init ( & tid_lock );
list_init ( & ready_list ); // ready_list 초기화
list_init ( & sleep_list ); // sleep_list 초기화
list_init ( & destruction_req );
/* Set up a thread structure for the running thread. */
initial_thread = running_thread ();
init_thread ( initial_thread , "main" , PRI_DEFAULT );
initial_thread -> status = THREAD_RUNNING ;
initial_thread -> tid = allocate_tid ();
}
sleep_list를 선언했으니 초기화는 필수이다.
thread_init 함수는 PintOS의 초기 스레드를 초기화하는 함수이다. 이 함수에서는 기본적으로 ready_list가 초기화되는데, ready_list와 같은 방식으로 sleep_list도 함께 초기화해 준다.
timer.c
void
timer_sleep ( int64_t ticks ) {
// 시간 재기 ( OS 부팅 후 시간을 가져온다 )
int64_t start = timer_ticks ();
ASSERT ( intr_get_level () == INTR_ON );
// elapsed는 start이후로 지난 시간을 반환한다.
// ticks가 0이 아니라면 재우게 된다.
if ( timer_elapsed ( start ) < ticks ) {
// start + ticks 시간까지 잠재우게 된다
thread_sleep ( start + ticks );
}
}
개선된 timer_sleep
개선된 timer_sleep 함수는 while문을 돌지 않고 thread_sleep() 함수를 호출하고 있다. 로직을 보려면 thread_sleep 함수를 봐야 한다.
thread.c
// 로컬틱 넣고, state 변경하고, sleep_list에 넣고, 스케줄러 호출하기
void thread_sleep ( int64_t ticks ) {
// 현재 스레드 담을 포인터
struct thread * curThread ;
// 인터럽트 레벨 담을 변수
enum intr_level old_level ;
// 인터럽트 비활성화 + 인터럽트 상태 old_level에 저장
old_level = intr_disable ();
// 현재 스레드 담기
curThread = thread_current ();
// 현재 스레드가 idle이 아닐 경우
if ( curThread != idle_thread ) {
// 로컬 틱 설정
curThread -> localTick = ticks ;
// localTick 기준으로 정렬되어 삽입
list_insert_ordered ( & sleep_list , & curThread -> elem , compare_thread_ticks , NULL );
// state를 blocked로 만들고 스케줄러 호출, 새 스레드에게 CPU 주기
// 이거 위에 있었을 때 안됐다
thread_block ();
}
// 인터럽트 활성화 + 복구
intr_set_level ( old_level );
}
스레드를 지정된 ticks 동안 재우는 함수이다.
재운다는 건, 스레드 state를 BLOCKED로 만들고 sleep_list에 넣는 걸 의미한다.
우선 작업을 하기 전 인터럽트를 비활성화 해야 한다. 이것은 sleep_list의 조작을 방해받지 않고 안전하게 하기 위해서, 또는 race condition 같은 상황을 방지하기 위해서 필수적이다.
현재 스레드가 idle thread가 아닐 경우 로직을 실행한다. idle thread는 CPU가 실행할 작업이 아무것도 없을 때 실행되는 스레드이며, 수행할 작업이 없다면 항상 실행되고 있어야 한다. idle thread는 재우면 안 되므로 조건문으로 걸러준다.
이후 현재 스레드의 localtick 을 입력받은 ticks 로 설정한다. system tick이 localtick과 동일해지면 해당 스레드는 깨어난다.
그리고 sleep_list에 스레드를 localtick 기준으로 정렬해서 넣는데, 이렇게 하면 가장 먼저 깨어나야 할 스레드가 sleep_list의 HEAD쪽에 위치하게 되므로 리스트를 전부 탐색할 필요가 없어진다.
마지막으로 thread_block()을 호출하여 현재 스레드의 state를 blocked로 만들고 스케줄러를 호출하여 다음 스레드에게 CPU를 넘겨준다.
thread.c
// list_insert_ordered를 위한 구현, 로컬틱 기준 정렬
bool compare_thread_ticks ( const struct list_elem * a , const struct list_elem * b , void * aux UNUSED ){
struct thread * thread_a = list_entry ( a , struct thread, elem);
struct thread * thread_b = list_entry ( b , struct thread, elem);
if ( thread_a -> localTick < thread_b -> localTick ) {
return true ;
}
else return false ;
}
list_insert_ordered 함수의 3번째 인자로 들어가는 함수이다. 함수의 인자로 함수가 들어간다.
a, b의 localTick을 비교하여 b가 클 경우 true, 아닐 경우 false를 리턴한다.
이 함수를 인자로 넣으면, localTick이 작은 스레드가(먼저 깨어나야 할 스레드가) 리스트의 HEAD 쪽에 오게 정렬된다.
따라서 이후에 thread_awake를 통해 sleep_list에서 깨울 스레드를 찾을 때 리스트를 전부 검사할 필요가 없게 된다.
timer.c
// sleep_list의 HEAD를 확인하여 System tick과 일치하면 wakeup 시킨다. ( sleep_list 정렬되어있어야함 )
static void
timer_interrupt ( struct intr_frame * args UNUSED ) {
// 타이머 인터럽트가 실행될 때마다 system ticks가 증가한다
ticks ++ ;
// 실행 중인 프로세스의 CPU 사용량을 업데이트 하는 함수
thread_tick ();
// 모든 tick마다 실행되어, wakeup할 스레드를 고르는 코드
thread_awake ( ticks );
}
PintOS는 매 타이머 인터럽트마다(1ms 간격) system tick을 1 증가시키고, sleep_list에서 깨울 스레드들을 찾는다.
아니, 정확히는 찾게 만들어야 한다. 따라서 thread_awake 함수를 timer_interrupt에 추가해야 한다.
thread.c
// 현재 system tick에 깨어나야 할 스레드를 찾고 깨우는 함수
void thread_awake ( int64_t ticks ) {
// sleep_list가 비어 있으면 바로 return
if ( list_empty ( & sleep_list )) {
return ;
}
// sleep_list HEAD 가지고 오기
struct list_elem * e = list_begin ( & sleep_list );
// 정렬해놨으니까 HEAD만 보면서, system tick보다 큰 값 나오면 break
while ( e != list_end ( & sleep_list ) && ! list_empty ( & sleep_list ) && e != list_head ( & sleep_list )) {
// 스레드 가져오기
struct thread * t = list_entry ( e , struct thread, elem);
// localTick이 systemTick 과 같거나 이미 지났을 경우 깨우기
if ( t -> localTick <= ticks ) {
// sleep_list에서 지워주기, 다음 요소 획득
e = list_remove ( e );
// sleep_list에서 unblock 하기
// state를 READY로 바꾸고 ready_list에 삽입한다
thread_unblock ( t );
}
// HEAD의 localTick이 systemTick보다 한 번이라도 클 경우 break
else {
break ;
}
}
}
thread_awake 함수이다. timer_interrupt 함수에 포함되어 있으므로 매 타이머 인터럽트마다(1ms마다) 이 함수가 실행되는 것이다.
인자로 ticks를 받아서 스레드가 가진 Local Tick과 비교해 일치하거나 일어날 시간이 지났다면 해당 스레드를 sleep_list에서 지우고 unblock한 후 실행될 수 있도록 ready_list에 넣는다.
참고로 PintOS의 list 형태는 {TAIL, 요소, HEAD} 형태이며 HEAD와 TAIL은 의미없는 값을 가지는 더미데이터이다. 즉 리스트의 끝을 판단하기 위한 역할일 뿐이다. 따라서 우리가 원하는 가장 빨리 깨어나야 하는 스레드를 찾으려면 list_begin 함수로 HEAD 다음 요소를 가져와야 한다.
또한 list는 정렬되어 있기 때문에 단 한번이라도 깨어날 시간이 되지 않은 스레드를 만난다면, 그대로 리스트 탐색을 종료해도 된다. 그 뒤의 스레드들은 더 늦게 깨어날 스레드들일 테니까.
=========================
이렇게 Alarm Clock은 끝이 났다. 무의미하게 CPU를 낭비하는 busy waiting 방식을 개선하고 sleep/wakeup으로 바꾸어 CPU가 낭비되지 않게 했다.
실행 결과
550 idle ticks
Thread: 550 idle ticks 부분을 보면 CPU 유휴 시간이 늘어났다는 걸 알 수 있다.
기존엔 0 idle ticks였는데 busy waiting을 개선하고 나니 550 idle ticks로 늘어났다.
참고로 550 idle ticks는 idle thread가 550 ticks동안 실행되었다는 것이다.
즉 CPU가 550 ticks 동안 놀았다는 뜻이고, CPU 자원 낭비가 줄어들었다는 걸 의미한다.
