Pintos Project 1 Threads. Priority Scheduling

Project 1의 중요 목표로 우선순위 스케쥴링을 구현해야 한다.

기존의 스케쥴러는 FIFO(First-in First-out) ronud-robin 방식으로 스케쥴링을 하고 있다. 이것을 우선순위 스케쥴링으로 바꿔줘야 한다.

이를 위해 신경써야 할 부분은 아래와 같다.

1. FIFO 형식으로 다음 실행될 스레드를 찾고 있는데, 이를 우선순위가 높은 스레드부터 찾도록 바꿔줘야 한다. ready_list가 ready queue의 역할을 하고 있는데 ready_list를 우선순위가 높은 스레드가 먼저 오도록 유지하게 하자. ready_list뿐만 아니라 semaphore를 기다리고 있는 스레드들 중에서도 우선순위가 높은 스레드부터 semaphore를 소유할 수 있도록 해야 한다.
2. 현재 스케쥴러는 실행되고 있는 스레드를 가로채는 것(Pre emption)을 지원하지 않는다. 이를 지원하여야 하고 실행중인 스레드의 우선순위가 ready queue에서 가장 큰 우선순위를 지니는 스레드보다 작아지면 CPU를 양보해줘야 한다.
3. 실행에 있어서 우선순위를 부여하게 되면 우선순위가 낮은 스레드가 소유하고 있는 lock을 그보다 우선순위가 높은 스레드가 원할 수도 있다. 이 때, lock을 소유하고 있는 스레드가 실행될 수 있도록 우선순위를 일시적으로 높여줘야 한다.

1번을 구현하기 위해서는 스레드가 ready queue로 들어갈 때, 다음 실행될 스레드를 ready queue에서 들고 올 때를 살펴봐야 한다.

스레드가 ready queue로 들어갈 때는 어떤 경우가 있을까?

스레드가 막 만들어지는 thread_create, 자고 있거나 semaphore를 기다리고 있다가 ready queue에 들어갈 때가 되는 경우, 실행중인 스레드에서 CPU를 양보해줄 경우인 thread_yield가 있다.

이렇게 ready queue로 스레드를 삽입할 때, 스레드들의 우선순위의 내림차순으로 유지하도록 하자. 그러면 ready_list의 제일 첫 번째 원소를 가져오면 ready_list에서 가장 높은 우선순위를 가진 스레드를 항상 가져올 수 있다. 즉, 현재 구현과 달라지지 않아도 된다.

그리고 위에서 말한 첫번째와 두번째경우에는 현재 thread_unblock 함수를 사용하고 있다. 따라서, thread_unblock과 thread_yield만 수정해주면 되겠다.

다행히도 pintos 자체에서 이런 list를 어떤 특정한 order로 유지하도록 하는 삽입방식을 list_insert_ordered에서 지원해주고 있다. 내 경우에는 alarm clock을 구현할 때 sleep_list에 스레드를 넣을 때도 사용했다.

스레드 우선순위 비교함수

위 사항들을 반영한 수정사항은 이 커밋에서 확인할 수 있다. 여기까지 수정하면 제일 기본적인 우선순위 관련 테스트인 alarm-priority는 통과할 수 있다.

이제 semaphore에서 우선순위를 구현해줘야 한다. 그리고 ready_list에 새로운 스레드가 들어왔을 때, 해당 스레드가 현재 실행중인 스레드보다 우선순위가 높다면 CPU를 가로챌 수 있게 해줘야 한다(preemption). 그리고 현재 실행중인 스레드의 우선순위가 바뀌었을 때도 마찬가지이다.

preemption은 실행중인 스레드의 우선순위가 바뀔 때(thread_set_priority), ready_list에 새로운 스레드가 들어왔을 때에 일어날 수 있다. 그리고 그 조건은 현재 실행중인 스레드(thread_current)의 우선순위가 ready_list에 존재하는 스레드의 우선순위보다 작아야 한다는 것이다.

이 조건들을 만족한다면 현재 실행중인 스레드는 CPU를 양보해야한다(thread_yield). 여기서, 자고 있던 스레드들을 깨울 때도 이 스레드들이 ready_list에 들어가게 되는데 thread_yield는 timer interrupt 도중에는 호출되면 안된다.

자고 있다가 깨어나서 ready_list로 추가될 애가 우선순위가 더 높다면 걔부터 실행되어야 하는거 아닌가? 그런데 깨우는건 timer_interrupt가 발생시에 해주고 있다. timer interrupt가 끝나면 interrupt 전의 실행중이던 코드로 돌아갈텐데 이건 항상 다를텐데 어떻게 CPU를 양보해야 할지 모르겠다. 다행인지 아닌지 이 경우를 고려하지 않아도 기본적으로 제공하는 테스트는 통과할 수 있다. 왜 통과하는지 아시는 분이 계시면 알려주시면 좋겠다.

아무튼 semaphore 부분도 수정해야 한다. semaphore를 기다리고 있는 스레드 중에 가장 우선순위가 높은 스레드가 semaphore를 소유하도록 하는 것은 sema_down, sema_up 부분을 수정하면 된다.

semaphore를 소유하고 싶은 스레드는 sema_down을 호출하고, 만약 소유할 수 없다면 semaphore의 waiters에 들어가서 깨워줄 때까지 기다리게 된다. 이 때, waiters도 우선순위의 내림차순을 유지하도록 하자. 그러면 sema_up에서 waiters의 제일 앞 스레드를 깨워주면 우선순위가 높은 스레드가 깨어나게 될 것이다.

이제 위 내용들을 코드로 짜주면 된다. 건드려야 할 부분은 thread_set_priority, thread_create, sema_up, sema_down 정도가 되겠다. 그리고 synch.c 파일에서는 ready_list에 접근할 수가 없기 때문에 preemption이 가능한지 체크하는 함수를 따로 만들어 줬다.

preemption이 가능한지 체크하는 함수

thread_create(좌), thread_set_priority(우)

여기까지 수정을 마쳤으면 priority-condvar과 donate 관련, mlfqs 관련 테스트 외에는 통과할 수 있다.

condvar 같은 경우는 모니터링을 위한 자료구조 같은데 이것도 비슷하게 waiters라는 대기 리스트를 들고 있고 이거를 우선순위 기준으로 정렬하면서 빼주고 넣어주고 하면 통과한다.

여러 번의 커밋에 걸쳐서 진행했기 때문에 한 번에 코드를 보긴 힘들고 여기에서 Implement Basic Priority Scheduling에서부터 Make preemption check in thread.c 까지 보면 될거 같다.

제일 처음에 말했던 lock과 관련된 내용이 donate 관련 테스트들인데 이를 해결하는 방법은 다음 글에서 쓰도록 하겠다.