pintos project 1 - Threads

useful link:
http://www.scs.stanford.edu/07au-cs140/pintos/pintos_2.html#SEC15


Pintos project 1 은
1) Alarm clock
2) priority scheduling
3) Advanced scheduler
위의 세가지 기능을 구현하는 프로젝트이다.

내용상 가장 쉽고 금방 구현할 수 있는 프로젝트 이지만, 이 프로젝트로 핀토스를 처음 접하기 때문에 체감 난이도는 엄청 쉽지많은 않았다 (그래도 다른 프로젝트들에 비하면 엄청 쉽긴 했지만..).

1) Alram clock
device/timer.c의 timer_sleep()는 호출한 thread을 특정 시간 동안 'sleep' 상태로 만들어 진행 중 이던 작업을 지연시키는 역할을 하는 함수이다.
핀토스에 원래 구현되어 있는 timer_sleep()은 while문을 돌면서 매번 thread을 깨울 시간이 되었는지 안되었는지를 확인하는 busy wait으로 구현되어 있다. 따라서 while문을 도는 동안 다른 유용한 작업을 하지 못해 매우 비효율적인 디자인이라고 할 수 있다. 이 문제를 해결하는 것이 첫번째 alarm clock파트이다.

이 문제를 고치기 위해 device/timer.c와 threads/thread.c, threads/thread.h을 고쳐야 한다.
busy wait을 없애기 위해선 sleep된 thread을 보관할 sleep list을 직접 만들어야한다. 핀토스에 제공된 data structure중 하나인 list을 사용하는 것이 편리하고,  list 사용 방법은 thread.c의 ready_list을 보고 감을 잡을수도 있고, lib/kernel/list.c의 주석을 참고하면 쉽게 사용할 수 있다.

timer_sleep() 에서 while문을 없애고, sleep state로 만들 thread (timer_sleep()을 호출한 thread) 을 sleep_list에 넣고, 주기적으로 리스트를 확인하여 깨어날 시간이 된 thread만 sleep list에서 꺼내면 된다. (주기적으로 리스트를 확인하기 위해 timer.c의 timer_interrupt()함수을 이용하면 된다)

꺼낼 시간과 현재시간을 비교하기 위해 thread마다 깨어날 시간을 기록할 멤버변수가 필요하고, list에서 깨어날 시간이 작은 순서대로 정렬하기 위한 비교 함수도 필요하다.
몇몇가지 함수만 만들면 쉽게 alarm clock을 구현할 수 있다.

2) Priority scheduling
여러개의 thread들이 동시에 실행되고 있을때 synchronization을 위해 사용되는 도구는 lock, semaphore, condition등이 있다. 만약, 여러개의 thread가 하나의 lock을 기다리는 상황이 생기면 어떤 thread가 먼저 lock을 가질 수 있게 해야할지를 정하는 방법엔 여러가지 방법이 있다.
이 프로젝트에서는 thread마다 priority을 주고, 큰 priority을 가진 thread가 우선권을 가지는 priority scheduling algorithm을 구현한다.
이를 위해, thread.h에 thread의 멤버변수로 priority (0~63 사이의 값을 가질 수 있고, 숫자가 클수록 priority을 가진다. 기존의 구현에선 기본적으로 모두 PRI_DEFAULT(31)을 가지고 있다.)을 가지고 있다.
구현해야 되는 내용으로는 semaphore, lock, condition이 있다. 이 부분을 구현하기 전, semaphore, lock, condition이 무엇인지 수업 렉쳐노트 등을 통해 확실히 이해를 한 뒤 진행해야 수월하게 진행할 수 있을 것이다.

lock은 semaphore의 특수한 경우로 생각할 수 있으므로, 세마포어를 먼저 구현한다.

sema up, down pseudo code는 구글링을 해보면 위키백과 등 많은 곳에서 볼 수 있다. 따라서 구현하면 될 것이다.
(간단히 요약하면, semaphore의 value가 0이 아니면 value을 1 감소시키고 계속 진행시키고, value가 0이면 sema_down을 호출한 thread을 block시키고 value가 1 이상이 되길 기다린다. sema_up에선 해당 semaphore을 기다리고 있는 thread가 있다면 그 중 가장 priority가 큰 thread을 unblock시키고, value을 1 증가시킨다.)

semaphore구현이 끝나면 lock을 구현한다. lock과 semaphore의 차이점은 lock은 semaphore와 다르게 하나의 thread 만 얻을 수 있다는 점이다 (value 1인 semaphore인 셈). 따라서 lock은 자신을 현재 가지고 있는 thread로의 pointer을 가지고 있다.

lock_acquire와 lock_release에선 각각 sema_down과 sema_up을 사용한다. 하지만 좀 더 생각해 주어야 할 점이 priority donation에 의해 생기는 문제점들이다. 다양한 해결방법이 있겠지만, 내가 사용한 방법은 lock에 list_elem들을 추가하여, lock을 요청한 thread들의 list와 각 thread마다 보유하고 있는 lock list을 가지게 하여 해당 문제를 해결하였다. 자세한 알고리즘은 직접 생각해보는 것이 도움이 될 것이다. priority donation과 관련된 부분이 이 프로젝트에서 가장 어려운 부분이고 이것만 해결한다면 condition 구현 부분은 매우 쉽게 할 수 있을 것이다.

3) Advanced scheduler는 구현하지 않았다.