[Pintos] Alarm Clock

Alarm Clock 과제는 다음과 같습니다.

devices/timer.c 에 있는 timer_sleep()을 다시 구현해봅시다.

Although a working implementation is provided, it busy waits, that is, it spins in a loop checking the current time and calling thread_yield() until enough time has gone by. Reimplement it to avoid busy waiting.

 

🔥 이미 잘 작동하는 timer_sleep()이 구현되어있지만 이는 busy wait 방식입니다. 즉 이는 계속해서 반복문을 돌면서 현재 시간을 확인하고 충분한 시간이 경과할 때까지 thread_yield()를 호출합니다. busy waiting 을 피하도록 다시 구현합니다.

 

 

Suspends execution of the calling thread until time has advanced by at least x timer ticks. Unless the system is otherwise idle, the thread need not wake up after exactly x ticks. Just put it on the ready queue after they have waited for the right amount of time.

void timer_sleep (int64_t ticks);

 

🔥 timer가 적어도 x번 tick 할때까지 thread 호출의 실행을 일시 중단합니다. 시스템이 idle(다음 thread가 없는) 상태가 아니라면, thread가 정확히 x번의 tick이 발생한 직후에 wake up 할 필요가 없습니다. thread가 적절한 시간동안 대기 한 후 ready queue에 놓이게 해주세요.

 

 

States in a thread's life cycle

스레드가 가질 수 있는 상태는 다음과 같습니다.

 

 

현재 Alarm Clock의 timer sleep 함수는

ticks 만큼 wait하여 현재 스레드를 yield하여 사용 못하게 끔 합니다.

다시 말해 wait하는 동안에는 CPU는 아무 스레드도 사용하지 못하게 됩니다.

 

따라서 timer가 sleep시킬 스레드는 최소 ticks 이후에 실행될 수 있음이 보장됩니다.

 

그러나 이러한 방식은 CPU 자원을 낭비하므로,

busy-wait 방식을 blocking 방식으로 바꿔야 합니다.

 

blocking 방식이란,

sleep 시킬 스레드의 상태를 THREAD_BLOCKED로 바꾸고 해당 스레드를 blocked thread list에 넣어 따로 관리하는 것을 의미합니다.

 

기존 방식은 현재 스레드를 BLOCKED 상태로 바꾸는 것 없이,

cpu에서 방출하여 곧바로 ready queue의 맨 마지막으로 삽입하고 있습니다.

 

이를 blocking 방식으로 변경해,

timer_sleep으로 현재 스레드를 일정 ticks동안 작동하지 않게 하고 싶다면?

 

현재 스레드의 상태를 THREAD_BLOCKED로 바꾼 뒤, blocked thread list에 삽입한 후,

타이머 인터럽트 때마다 해당 스레드의 sleep과 연관된 tick 정보를 확인하여

일정 sleep tick 이상이 흐른 스레드를 다시 깨운 후, ready list로 스케쥴링 하면 됩니다.

 

 

timer_sleep 기존 구현

 

일정 ticks 동안 계속 while loop에서 현재 스레드를 방출하고 있습니다.

이게 busy_waiting 방식을 의미합니다.

 

timer_sleep을 blocking 방식으로 수정

1. 현재 스레드를 언제까지 sleep 시킬 지 적어둔 후 blocking

2. 타이머 인터럽트마다 해당 스레드의 sleep과 연관된 tick 정보를 확인

2-1. 일정 sleep tick 이상이 흐른 스레드를 다시 깨운 후

2-2. ready list로 스케쥴링 하면 됩니다.

 

 

1. 현재 스레드를 언제까지 sleep 시킬 지 적어둔 후 blocking

update_next_wakeup_ticks 함수를 통해, 깨울 시간이 가장 가까운 스레드의 시간을 기입

즉 바로 다음 스레드를 깨울 시간을 계속 유지

이후 blocked_list에 삽입한 후

스레드 블락

 

 

 

2. 타이머 인터럽트마다 해당 스레드의 sleep과 연관된 tick 정보를 확인

2-1. 일정 sleep tick 이상이 흐른 스레드를 확인하기 위한 if문

if 문 통과하면 thread_wakeup

timer_interrupt 에 추가된 코드

 

2-2. ready list로 스케쥴링 하면 됩니다.

thread_unblock 함수가 ready list로 다시 스케쥴링을 해줌