PintOS의 첫번째 프로젝트는 다음과 같이 진행된다.
우선 쓰레드를 재웠다가 다시 깨우는 alarm-clock의 구동 방식을 busy-waiting에서 sleeping 방식으로 구현하도록 한다.
다음으로 ready 상태에 있는 쓰레드들의 우선순위를 고려하여 스케줄링을 하고, priority inversion 문제를 해결하기 위한 priority donation을 구현한다.
마지막으로 MLFQ(Multi-level Feedback Queue)를 구현하는 것이 목표인데 능력, 시간의 부족으로 구현에 옮기지는 못하였다.
Alarm-Clock
기존에 주어진 PintOS에서 쓰레드가 running state와 ready state를 오가는 방식은 busy-waiting 방식이었다. 이 방식은 Running state에서 sleep 명령을 받으면 ready_list로 갔다가 일어날 시간이 될 때까지 계속 running state에서 ready state가 되기를 반복한다. 이러한 과정에서 불필요한 CPU 자원의 낭비가 있을 수 있기 때문에 sleep된 쓰레드를 ready가 아닌 block 상태로 만드는 sleeping 방식으로 구현하도록 한다.
구현을 위해 변경/추가한 사항은 다음과 같다.
struct thread {...}
: 쓰레드가 block 상태에서 일어날 시간을 정하기 위해 wakeup이라는 변수 추가static struct list sleep_list
: sleep 상태의 쓰레드들을 저장할 sleep_list 생성, thread_init에서 초기화void thread_sleep(int64_t ticks)
{
일어날 시간을 저장하고, sleep_list에 추가한 후 block 상태로 변경
}void thread_awake(int64_t ticks)
{
sleep_list 중에 깨어날 시간이 된 쓰레드가 있는지 확인하고,
있으면 sleep_list에서 ready_list로 옮겨주고 unblock.
이 함수를 timer_interrupt 함수에 포함시켜 매 틱마다 실행되도록 한다.
}Priority Scheduling
쓰레드들이 ready_list에서 running state가 될 때, 그 순서를 정하는 priority를 통해 스케줄링 하는 방식을 구현할 것이다. 기존의 스케줄링 방식은 우선순위를 고려하지 않는 선입선출(First In First Out, FIFO) 방식으로 구현되어 있었다.
Priority Scheduling을 구현하기 위해, 쓰레드가 ready_list로 들어갈 때 priority 순서대로 정렬되도록 한다. 우선 thread.c에서 사용되는 list는 doubly linked list임을 확인했다.
ready_list로 쓰레드가 추가되는 때는 thread_unblock, thread_yield 함수가 호출될 때이다
