Introduction
본 Project 01에서 수행할 과제는 다음과 같다.
- Alarm clock
- Priority scheduling
- Advanced Scheduler
Project 수행 시 advanced scheduler를 포함하여 모든 테스트를 통과했다. 자세한 코드 내용은 팀 노션에 정리되어 있고, 본문은 과제를 복기하면서 느낀점과 이론에 대해 적어볼 생각이다. 대부분 생각나는 대로 적는 것들이 많아 다소 틀린 부분이 있을 수 있다.
Alarm clock
Alarm은 호출한 프로세스를 정해진 시간 동안 재웠다가 일정 시간이 지나면 깨우는 기능으로 현재 PintOS는 busy waiting으로 구현되어 있다. 이를 설명하기 위해 thread의 lifecycle을 보면 다음과 같다.
현재는 busy-waiting으로 구현되어 있기 때문에 thread들은 끊임없이 ready_list에서 cpu를 점유할 때마다 자신이 깨어날 시간인지 확인하고, 만일 깨어날 시간이 아니라면 thread_yield를 수행해서 다른 thread에게 CPU를 양보하고 ready_list로 들어가게 된다.
이는 다음 코드에서도 확인할 수 있다.
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks (); // 현재 ticks 값을 반환하는 함수
ASSERT (intr_get_level () == INTR_ON);
while (timer_elapsed (start) < ticks)
thread_yield ();
- timer_sleep: 현재 thread를 ticks 시간 동안 재우는 함수
- timer_ticks: 현재 tick 값을 반환하는 함수
- timer_elapsed: 인자로 받은 시각(tick)으로부터 몇 tick이 경과했는지 반환하는 함수
따라서, timer_elapsed의 return 값이 자야하는 시간 즉 tick보다 작으면 CPU를 양보하고 ready list에 들어간다. 이 과정을 ticks보다 커질때까지 반복하는 것이다. 계속 스케줄링을 받으며 CPU와 ready_list를 오가고 있기 때문에 CPU나 프로세스나 개고생이 따로 없다.
결론적으로 CPU는 엄연히 프로세스가 자고 있을 시간 즉, 실행될 시간이 아닌 경우에도 계속 context switching을 하며 시스템 자원들을 낭비하고 있다.
이를 개선하기 위해 sleep 시 block 시켜 sleep list라는 자고 있는 thread들을 관리하기 위한 list에 넣고, 깰 시간이 되었을 때 unblock해서 ready_list에 넣는 것이다.
본 과제를 적절히 수행했는지 확인하는 방법은 이전 포스팅에 나왔던 idle thread을 통해 확인할 수 있다. idle thread는 ready_list에 아무 스레드도 존재하지 않을 경우 나타난다고 이전 포스팅에서 서술했다.
현재 busy-waiting은 말 그대로 재우고 난 후에도 계속 스케줄링 되고 있기 때문에 idle thread가 cpu를 점유하고 있을 일이 없는 것이다.
하지만 본 과제를 성공적으로 마쳤다면 모든 thread들이 자고 있는 경우엔 idle_thread가 CPU를 점유할 것이고 thread_tick에서 idle thread의 tick수가 올라갈 것이다.
Solution
- while 문 기반의 busy-waiting 방식에서 sleep/wake up 방식으로 변경
- timer_sleep() 호출 시 thread를 ready_list에서 제거하고, sleep list에 추가
- thread 구조체 내에 깨어나야 할 tick을 저장할 변수 추가(wakeup_tick)
- 전역변수 추가
- sleep list: sleep 된 쓰레드들 관리할 리스트
- next_tick_to_awake: sleep_list에서 대기중인 스레드들의 wakeup_tick 값 중 최소값을 저장함.
이 값이 없으면 매 timer_interrupt 마다 sleep_list를 돌면서 깰 시간이 된 thread가 있는지 확인해야 함.
- timer_interrupt 수정
- interrupt 발생시마다 현재 tick과 next_tick_to_awake 값을 비교해 tick이 같거나 클 경우 thread_awake를 호출함
- thread_awake
- sleep_list를 돌면서 깰 시간이 된 thread를 sleep list에서 제거하고, unblock하여 ready_list에 넣어준다.
- next_tick_to_awake 갱신을 위해 깰 시간이 안된 thread들을 대상으로 크기 비교를 통해 작은 값으로 갱신할 수 있도록 해준다.
- thread_sleep
- 현재 스레드의 wakeup_tick 값에 인자로 받은 ticks 값을 저장하고, 이 값과 next_tick_to_awake 값을 비교해 만일 현재 스레드의 tick값이 작으면 해당 값으로 갱신하고, sleep_list에 추가한 뒤 block 한다.
- 뒤에 나오는 과제들에 비하면 크게 어렵지 않은 수준이었다. 자세한 코드는 git이랑 팀 노션에 정리되어 있으므로 생략했지만 이 정도만으로도 복기하는데 충분할 듯 보인다.
Priority scheduling
- 현재 PintOS의 scheduler는 round-robin(4tick)으로 구현되어 있는데 이를 우선순위를 고려하여 스케줄링 할 수 있도록 수정하는 과제
- Ready list에 새로 추가된 thread의 우선순위가 현재 CPU를 점유중인 thread의 우선순위보다 높으면, 기존 thread를 밀어내고 CPU를 점유한다.
- 여러 thread가 lock, semaphore를 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유한다.
- PintOS에서의 우선순위는 PRI_MIN(=0)부터 PRI_MAX(=63)까지의 범위를 가지며 숫자가 클수록 우선순위가 높음.
- thread_create 시 초기 우선순위 값은 PRI_DEFAULT(=31)으로 세팅
Solution
- thread의 unblock 및 yield 후 ready_list에 우선순위 순으로 정렬되어 삽입될 수 있도록 list_push_back이 아닌 list_insert_ordered로 수정.
- thread_create 시 unblock 후 현재
실행중인 thread와ready_list의 첫 번째 thread(만일 새로 생성된 thread의 우선 순위가 가장 높다면 unblock에서 list_push_back에 의해 정렬되어 삽입되므로 list의 head 바로 뒤에 존재할 것) 즉, 우선 순위가 가장 높은 thread의 우선 순위를 비교하여 CPU를 선점할 것인지를 판단한다. - 현재 thread의 priority를 수정하는 thread_set_priority에도 우선 순위를 고려하여 스케줄링 하는 함수 호출 추가
- test_max_priority
- ready_list에서 우선 순위가 가장 높은 thread와 현재 thread의 우선 순위를 비교하여 현재 thread의 우선 순위가 더 작다면 thread_yield 호출
- cmp_priority
- list_insert_ordered 함수에서 사용
- ready_list 내 thread의 priority를 비교하는 함수로 첫 번째 인자의 우선순위가 높으면 1, 두 번째 인자의 우선순위가 높으면 0을 반환
- list에는 list_elem 형태로 있기 때문에 thread의 우선 순위를 확인하기 위해서는 list_entry 함수를 이용해 thread 구조체에서 elem 위치만큼의 offset을 이용하여 thread 주소를 계산한 후 priority member에 접근하여 값을 비교함.
Priority scheduling-Synchronization
- 여러 스레드가 Lock, Semaphore, Condition variable을 얻기 위해 기다릴 경우 우선 순위가 가장 높은 threadrk CPU를 점유하도록 구현
- semaphore를 대기 하고 있는 스레드들의 list인 waiters에 push 될 때 정렬되어 삽입되도록 수정하여 우선 순위가 가장 높은 thread가 unblock 될 수 있도록 수정
Solution
- 공유 자원에 접근하고자 하는 thread가 sema_down 실행 시, 사용가능한 자원이 없을 경우 semaphore의 wait list에 우선순위 순으로 정렬되어 삽입될 수 있도록 수정
- 공유 자원을 모두 사용하면 해당 자원을 기다리고 있는 wait list에서 우선 순위가 가장 높은 thread를 unblock해서 ready_list에 넣어주고, 우선순위 선점을 고려하기 위해 test_max_priority를 호출한다.
Priority inversion problem
- 우선순위가 높은 thread가 우선순위가 낮은 thread를 기다리는 우선순위 역전 문제로 다음과 같이 정리했다.
multiple donation
Nested donation
- Multiple에서 동일한 thread에게 여러번 priority를 donation 한것이 아닌 chain처럼 High, Mid, Low가 서로 연결되어 우선순위를 기부하는 상황
- 예를들어 High가 lock B(thread Mid 점유)를 얻기 위해 대기하고 이때, Mid는 lock A(thread Low 점유)를 얻기 위해 대기하고 있으면 High의 우선순위는 thread Low, Mid에게 모두 donation 되어야 함.
Solution
- 해당 donation 과제를 수행하며 작성한 코드와 주석들은 모두 team notion에 정리되어 있으므로 생략하고, 해당 과제들의 개요를 복기하는 시간을 가졌다.
Multi level feedback queue scheduler
-- 추후 작성
