PintOS project1. Threads

PintOS 1주차의 기록

기본 구성

 

thread 흐름

thread의 status는
Thread_Running, Thread_Ready, Thread_blocked, Thread_dying 로 4가지이다.
이 개략적인 그림을 알고 있으면 상태 변화를 이해하기 쉽다.
(참고: https://poalim.tistory.com/33?category=758538) 

[Pintos] Project 1 : Thread(스레드) - Priority Scheduling(1)

추가로 PintOS document를 꼭 꼭 잘 읽자 (project 부분만이 아닌 appendix 부분을 꼼꼼히 잘 읽자)

Alarm Clock

첫번째 과제는 busy wait 방식을 개선하는 것이다.
현재 PintOS의 thread 정책은, busy wait 방식으로 block된 thread를 unblock한다.
쉽게 말해, 100초 간 자라고 시킨 thread가 있다면 100초 후에 깨우면 되는데 매초마다 100초 지났나? 하고 확인하는 것과 같다. 이는 비효율적이므로 개선해보자.

timer.c에 있는 timer_sleep() 함수는, 현재 while문을 통해 하염없이 waiting 중이다.
가장 큰 문제는 sleep 시킨 함수를 yield 한다는 것이다!!!!  (즉, ready_list에 다시 넣는다는 뜻이다)
이렇게 되면, ready_list에 있던 현재 sleep중인 thread가 running 상태가 될 때마다 우리는 시간을 체크해줘야 한다.
여기서 큰 비효율이 발생하고 이를 개선해보자.

thread를 sleep 시킬 때, awake해야하는 시간을 기록해두고 sleep_list를 만들어 그 시간을 기준으로 정렬해보자.
그럼, 현재 10초일 때 20초를 재운 thread A와, 15초일 때 10초를 재운 thread B, 20초일 때 20초를 재운 thread C가 있으면 20초가 됐을 때는 sleep_list에 B - A - C 순으로 정렬이 돼있다. (일어나야 하는 시간이 30초, 25초, 40초 이므로!!)
이 상태에서 가장 작은 값 (B가 일어나야 하는 시간)보다, 현재 tick이 높아진다면 B를 sleep_list에서 꺼내고 ready_list에 넣어주면 된다.
즉 우리가 해야하는 일은 while문을 제거하는 것이고 방법은 다음과 같다.
1. thread 구조체에 awake_time을 추가하여 unblock 돼야 하는 시간을 기록한다 (ready_list에 다시 들어갈 시간)
2. sleep 함수를 호출하면, yield가 아닌 sleep_list에 추가하고 block하는 새로운 함수를 생성한다.
3. 이 함수에서 sleep_list에 정렬된 순서로 추가한다 (insert_ordered 함수를 이용해보자) + 추가적으로 가장 작은 값을 기록해두면 좋다 ( 즉, sleep_list의 맨 앞 값이 얼마인지 기록!)
4. 그 후, timer_interrupt 함수에서, 매 틱마다 깨울 thread가 있는지 확인한다. (확인 방법은 앞서 말한 것과 같이, 가장 작은 awake_time을 가진 thread와 현재 tick을 비교한다!)

이렇게 되면 sleep 시킨 함수를 다시 ready_list로 보내어 매번 running_thread로 올라올 때마다 체크해주는 것이 아닌
sleep 조건이 끝나고 나서 ready_list에 추가 되기 때문에 시간이 많이 개선된다.

Priority Schedule

그럼 또 뭘 개선할 수 있을까???
우리는 busy wait 방식을 개선하였다. 그럼 현재 PintOS는 ready_list에서 running으로 가는 방식이 어떤지 살펴보자.
즉 Schdule을 어떤 로직으로 하는 중일까??
살펴보면, 현재는 맨 앞의 ready_list를 꺼내어 running으로 올려보내고, ready_list에 삽입할 때는 맨 뒤에 넣는다.
즉 단순히 시간을 기준으로 한 선입선출 방식이다.  이 방식은 Round-robin 방식으로, 어찌보면 단순한 방법이다.
그런데 만약, thread A, B, C 중에서 C가 가장 급하게 실행이 돼야하는 상황라면 어떨까??
현재 round-robin 방식으로는 A - B - C 순으로 실행이 될 수 밖에 없다. 이런 Scheduling 방식을 개선하기 위해 우리는 Priority를 도입할 수 있다!

 

이 방법은 각 thread에 Priority를 부여하여서, 가장 높은 Priority를 가진 thread가 우선적으로 실행되게 하는 방법이다.
잘 생각해보면, alarm clock에서 했던 것처럼 thread 구조체에 priority를 추가한 후에 ready_list를 priority를 기준으로 정렬하면 된다!!
우선 ready_list에 추가되는 경우는 둘 뿐이다. thread_yield 함수와 thread_unblock 함수가 호출 됐을 때이다.
이 때 ready_list에 push_back 함수를 이용하여 추가하는데, 이 방식을 list_insert_ordered()를 사용하여 바꾸자.
(push_back 이후 나중에 최대 priority를 가지는 thread를 추출해도 되지만, 넣을 때 정렬하고 list_begin을 추출하는 것이 더 효율적이라고 판단했다)

이렇게 하면 ready_list는 priority 순으로 내림차순 정렬이 됐다. 마지막 마무리 작업은 priority가 변경 됐을 때 현재의 running_thread와 ready_list의 첫번째 (가장 큰 priority)를 비교해줘야 한다. priority가 변경되는 경우 또한 2가지이다.
thread_create 함수와 thread_set_priority 함수가 실행됐을 때이다.
이 두 함수에 각각 running_thread와 ready_list의 최대 priority를 비교하는 작업을 추가해주면
priority schedule이 1차 완성이다!!

 

정리하면
1. ready_list에 추가할 때 priority 순으로 추가한다! (yield와 unblcok에서 insert 방식을 변경한다)
2. priority가 변경되는 순간에 preemption을 체크한다 (누가 더 priority가 높은지!)

 

Priority Donation

그러나 진짜 큰 문제는 아직 끝나지 않았다.

priority를 우선적으로 수행하는 것은 매우 좋다. 그러나 lock이 연결되면 문제가 달라진다.

예를 들어, thread A는 priority 10, lokc A를 가지고 있다. thread B는 priority 20, lock A가 필요하다.
우리의 알고리즘에서는 thread B가 running_thread가 될 것이고, B는 계속해서 lock A를 요구한다.
문제는 thread B가 요구를 하면서 계속 running을 점유하는 것이다. A가 running이 되어  lock A를 release 해야하는데 그러지 못하는 상황이다. (dead lock)
이를 해결하기 위해 우리는 priority donation을 사용한다. 즉, B가 A에게 자신의 priority를 준다는 의미이다.
이렇게 하면 A는 priority가 20이 되어 running thread가 될 수 있고,  lock A를 release 하는 순간 다시 original_priority(10)으로 돌아오고 thread B가 실행되어 lock A 를 획득할 수 있다.

언급한 방법이 쉽게 와닿지 않을 가능성이 높다 (나는 그랬다 ㅠ)
가장 좋은 방법은 test-case를 분석하는 것이다. 예를 들어 priority-donate-multiple2를 보자!
여기서는 3개의 thread가 등장한다 ( main thread 제외)
먼저 main thread는 lock a, b를 획득한 상태에서, priority 3인 A를 생성한다 (A는 lock a가 필요하다) (+ main은 0이라 가정한다.)  그럼 이 순간 A가 running이 되어야 한다! 그러나, 앞서 말한대로 A가 실행이 되면 a_thread_func가 실행이 되고, 여기서 lock_acquire(lokc a)가 실행된다.
이 상태에서 A는 계속해서 lock을 기다리는 상태가 되는데, lock a가 release되기 위해서는 main thread가 실행되어 코드를 더 진행해야한다. (lock_release(lock a)가 한참 아래에서 실행되기 때문에!!)

그래서 우리는 이때 A의 priority를 main에 donate 해야한다. 그리고 A를 block 상태로 변경하고, main이 priority 3이 되어 running을 점유한다. 다시 main에서 thread C를 생성하고 이는 priority 1이고 lock을 요구하지도 않으므로 priority가 3이 된 main이 계속 실행된다.
마찬가지로 B가 생성되고 main의 priority는 5가 된다.
이후에 lock_release(a)가 실행되면 A가 실행이 된다.    가 아니다!!!! 여기서 헷갈렸다면 다시 테스트 케이스를 돌아보길 바란다. lock a를 풀어주면 Thread A는 실행이 가능하게 되지만, 더 높은 priority인 B가 존재한다 (지금 상태에서는 donate 받은 main 또한 A보다도 크다)
그래서 main이 계속해서 running 돼고 lock b가 풀리면 main priority -> 3이 되고 thread B가 실행된다.
thread B가 완료 된 후, main priority -> 0 이 된 후에 thread A가 실행된다.
이후 thread C까지 완료 후 main thread도 실행 완료가 된다!!


이렇게 test case를 분석하면 우리가 어떤 부분을 코드로 작성해야하고, 어떤 경우를 대비해야 하는지 알 수 있다.
반드시 test_case 여러개 (가능하다면 모두)를 뜯어보고 분석하기를 추천한다!!!!!! 강추!!!!!!!!!!!!

 

정리하면
1. 우리는 donate 함수를 구현해야한다. (이 때 초기 original priority를 보관하는 방법과 나에게 donate한 thread들, 등등 필요한 정보를 어떻게 활용할지 고민해보자)
2. 그리고 donate가 끝나면 priority를 return 해야 한다.
3. 결국 donate가 일어나는 순간은 lock이 acquire 됐을 때이다.

더 자세한 작성은 추후에 추가해보자...!
추가로, lock 구조체에 original_priority를 저장하는 방식으로 구현을 했는데 donate-chain case를 통과하지 못했다.
혹시 이러한 방식으로 코드를 짜서 통과가 됐다면 공유를 부탁드립니다.

 

Advanced Schedule

마지막 과제이다. 결국 priority schedule도 성에 차지 않기 때문에 새로운 것이 필요하다.
왜 성에 차지 않을까??
priority 방식은 우선순위별로 실행되어 중요도가 높은 thread를 실행하지만 그렇게 되면 priority가 작은 thread는 굉장히 늦게 실행될 수 있다. 실제 OS는 그런식으로 동작하는 것이 좋지 않을 수 있다.
때문에 mlfqs 방식을 활용한다.
이는 복잡한 수식이 필요하지만 개념만 짚어보자!
결국 priority가 높은 thread가 running이 되어야 하는 것은 맞다. 그러나 running을 오래 점유한 경우 priority가 점차 낮아져서 다른 thread에게 양보할 수 있어야한다.

이를 위해 nice라는 int값을 추가하는데 nice가 높을수록 다른 thread에게 잘 양보한다고 생각하면 된다.
즉 tick마다 최근 cpu를 점유한 정도와 nice를 따져서 priority를 재조정해준다! (즉 매 tick마다 변경되는 것 말고는 priority를 따로 설정하고 변경할 수 없다. 초기 값은 설정할 수 있다)
그럼 결국 중요한 점은 cpu를 사용한 시간과 nice에 얼만큼의 가중치를 주어 priority를 변경할 지인데, 이는 수학자들이 잘 구해주어서 document를 보고 구현해보면 될 것 같다.
쉽지 않지만, 사실 donate까지 거쳐 왔다면 이 부분은 단순 구현에 가까워서 오히려 조금 쉽게 할 수 있었다.