Pintos lab1 thread review

📕 Thread

pintos의 첫번째 랩이 thread를 통해, os가 어떻게 thread들을 scheduling 하고, synchronization 시키는지 알 수 있었다. 각 chapter를 통해 어떤 기능들이 어떤 요구에 생겨나게 되었는지를 중점으로 이해하고자 노력하였다. 모든 케이스를 생각하고 고려하는 것을 통해 OS에 있어서 generality가 얼마나 중요한가를 느낄 수 있었다....

👉 1. Alarm clock

기존의 timer sleep 함수는 busy waiting으로 설정한 sleep time이 지났는지 확인하였다. 그래서 cpu를 계속 잡아먹고 있다. 이를 ready list를 통해 busy waiting을 하지않고 idle thread로 효율을 높이는 것이 목표이다.

이를 위해, thread 구조체에 wake up thread tick을 계산하여 넣어주었다. 또한 현재 자고 있는 thread들 중에 가장 빨리 일어나야할 thread tick을 저장하는 변수(min_wake_up_tick)를 만들어서, 매 tick마다 sleep list를 일일히 확인하지 않도록 하였다. 그러기 위해 ready list에 들어가기 전에 이 min_wake_up_tick을 갱신하여 주었다.

👉 2. Priority Scheduling

기존의 pintos는 FIFO 스케쥴링으로, 먼저 잠든 순서대로 일어나고 있었다. 또한 ready list들도 Round robin 방법으로 4 ticks마다 순서대로 실행되고 있었다. 하지만, 스레드마다 중요성이 다름은 분명하다. 이 pintos를 유저가 원하는 priority 순서대로 먼저 실행되도록 하는 것이 목표이다.

이를 위해, thread의 priority를 입력받아(pintos에 이미 셋팅되어 있었다.) priority가 높은 thread부터 먼저 실행되어 마쳐질 수 있도록 하였다. 또한, thread가 생성되었을 때, thread가 unblock 될 때, 유저가 priority을 다시 설정했을 때에 현재 실행중인 thread의 우선 순위와 비교하여, 새로운 priority가 더 높다면 바로 실행될 수 있도록 하였다.

한편 thread의 동시성 때문에 같은 자원에 접근하다가는 에러가 일어날 수 있다. 이를 막기위해 동기화(synchronize)를 통해 같은 critical area에 한 thread씩 들어갈 수 있도록, 상호 배제(Mutual exclusion)를 보장해줘야 한다. 이를 위해 pintos에서는 다음과 같은 방법을 사용한다.

Disabling interrupts : interrupts를 차단시킴
Semaphore : 양수의 정수를 사용해, 접근을 제한하고 대기시킴 (다른 thread가 sema up (release) 가능)
Lock : boolean을 통해, 접근을 제한하고 대기시킴, (lock holder만 release 가능)
Monitor : lock과 (monitor에 대한 접근 locks), condition variables을 통해 조건이 되면 깨움, 전체를 깨울 수도 있다.(pintos에서는 이를 semaphore를 활용해 구현)
Optimization barriers - complier에게 memory assumption을 하지 않도록 막는 영역 지정

synchronization 해제 뒤에도 priority 높은 순서대로 바로 실행될 수 있도록 구현하였다. 하지만, 이런 synchronization에 의해 priority가 높은 thread가 실행되지 못하는 priority inversion이 발생한다.

이를 해결하기 위해 donation을 구현했다. (Pintos에서는 lock에 대해서만 donation을 구현한다.) donation은 내가 묶여 있는 lock holder의 priority가 나보다 낮다면 나의 priority를 빌려줌으로써, 빨리 실행되어 lock을 release하게하고, 나도 제때 실행될 수 있도록 한다. nested donation은 내가 묶여있는 lock holder들의 lock holder들까지 재귀적으로 나의 priority보다 낮다면 나의 priority를 빌려주는 것이다. multiple donation은 한 thread들에 여러 lock들이 걸려있을 때 모든 lock들이 lock holder 에게 필요하다면 priority를 빌려주고 donation list에 저장한다. 이후 어떠한 lock이 release 되어도 donation list에서 남아 있는 lock들 중 높은 priority로 교체한다.

👉 3. Advanced scheduler

priority sheduler를 통해 thread 간의 우선 순위를 고려했지만, 낮은 priority를 가진 thread는 자칫 영원히 실행될 수 없는 starvation 문제를 가진다.
이를 해결하기 위해 Multi level feedback queue인 4BSD를 구현하였다. thread들의 recent_cpu(cpu 사용시간), load_avg(대기중인 thread 수), nice(요구된 중요도)를 모두 고려해 주어진 시간마다 priority를 다신 계산하도록 하였다. 이를 통해 overhead는 늘어나게 되지만 모든 thread들이 balnced, 즉 유동적이고 필요에 의해 실행될 수 있었다.
추가적으로 빠른 연산을 위해 고정소수점 연산을 구현하였다.