PintOS
Project 1. THREADS
1-1 Alarm Clock
sleep 중인 thread를 awake 시간에 다시 ready 상태로 만들어 주는 것이 목표.
sleep 중인 thread list를 만들고 sleep 싱태가 될 때 마다 sleep_list에 추가.
sleep_list를 check하여 awake 시간이 되면 ready_list에 다시 넣어 준다.
1-2 Priority Scheduling
우선 순위 순으로 thread를 running thread로 바꿔주는 것이 목표.
각 thread의 priority를 check하여 우선 순위가 제일 높은 thread를 running thread로 바꿔 준다.
기존에 running인 thread보다 우선 순위가 높은 thread가 생기면 기존 thread는 ready로 바꾸고 우선 순위가 높은 thread는 running으로 바꿈.
우선 순위가 높은 thread는 mutex나 semaphore의 lock을 얻고 싶어하고, 기존에 lock을 얻은 thread는 작업을 하고 lock을 반납하는 작업을 하고 싶어하나 우선 순위에 밀려 작업을 하지 못하는 deadlock 상태를 막기 위해 donation(priority 기부)을 하는 상황도 발생 할 수 있다.
1-3 Advanced Scheduler
mlfqs = Multi-Level Feedback Queue Scheduler 의 약자.
priority 인자 외에 niceness, recent_cpu, load_avg 인자를 추가하여 우선 순위를 더욱 효율적으로 계산. (starvation 방지)
-
priority
PRI_MIN : 0, PRI_MAX : +63
PRI_DEFAULT : 31
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
매 4 tick 마다 모든 스레드의 priority 를 재계산한다. -
niceness
niceness가 클수록 다른 thread에게 점유를 양보하는 정도가 큼 = priority가 낮아짐.
- recent_cpu
thread가 최근에 얼마나 running 했는지를 나타내는 값이다.
recent_cpu가 클수록 최근에 더 많이 running 했을음 의미하고 우선 순위가 낮아짐.
recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice
매 tick 마다 running 스레드의 recent_cpu 값이 1 증가한다. (idle tread가 아닐 때)
1초 마다 모든 thread의 recent_cpu 값을 재계산한다.
- load_avg
최근 1분 동안 수행 가능한 스레드의 평균 개수를 나타낸다.
이 값이 크면 recent_cpu 값은 천천히 감소(priority 는 천천히 증가)하고, 작으면 recent_cpu 값이 빠르게 감소(priority 는 빠르게 증가)한다.
이유는 수행 가능한 스레드의 평균 개수가 많을 때는 모든 스레드가 골고루 CPU time 을 배분받을 수 있도록 이미 사용한 스레드의 priority 가 천천히 증가하여야 하고, 평균 개수가 적을 때는 조금 더 빠르게 증가해도 모든 스레드가 골고루 CPU time 을 배분받을 수 있기 때문이다.
load_avg = (59/60) * load_avg + (1/60) * ready_threads, (ready_threads 는 ready + running 상태의 thread의 개수)
매 1 초마다 load_avg 값을 재계산한다.
위 인자들과 계산식을 이용하여 priority를 계산 한 뒤, 우선 순위가 높아진 thread를 running한다.
진행 상황 공유
make check 결과 mlfqs-nice-10 부분만 통과됐다 안됐다를 반복.
원인 불명 (코드를 비효율적으로 짜서겠지 뭐..)
