이제 OS가 어떻게 돌아가는지 아주 조금은 감이 오는 것 같다.
다행히도 핀토스의 악명에 비해서는 순조로운 한 주를 보낸 것 같다.
나머지 3개의 프로젝트도 팀원들과 잘 마무리 할 수 있도록 해야겠다.
kaist pintos project1(thread)에서는 아래의 3가지 과제를 수행하게 된다.
1. Alarm Clock
첫번째 과제에서는 time_sleep 함수와 몇 개의 함수를 수정해 쓰레드를 위한 알람시계를 구현한다.
주어진 pintos에서는 잠을 자고 있는 쓰레드들도 실행을 기다리는 ready_list안에 들어가 있어 ready_list 내에서 본인의 차례가 돌아오면 깨어날 시간이 아닌데도 잠깐씩 cpu를 점유하고 있었다. (busy waiting)
그래서 sleep_list를 만들어 자고 있는 쓰레드들을 ready_list가 아닌 sleep_list에 넣고 각 쓰레드들 마다 깨어나야 할 시간을 따로 저장해 timer_interrupt가 실행될 때마다(매 tick마다) 일어나야 할 쓰레드들을 깨우는 형태로 재구현해 busy waiting을 없앨 수 있었다.
2. Priority Scheduling
주어진 pintos는 각 쓰레드의 우선순위를 고려하지 않고 선입선출 방식으로 쓰레드들을 실행하고 있었다. 두번째 과제의 목표는 우선순위를 고려해 스케줄링을 해 우선순위가 빠른 쓰레드들이 먼저 실행될 수 있도록 하는 것이다.
이를 위해 1. 쓰레드가 ready_list에 들어갈 때 우선순위 순으로 넣어주고, 2. ready_list에 현재 수행중인 쓰레드보다 우선순위가 높은 쓰레드가 있다면 cpu 선점이 일어나도록 해준다.
한편 우선순위가 높은 쓰레드가 lock A를 필요로 하는데 우선순위가 낮은 쓰레드가 lock A를 갖고 있다면 우선순위가 높은 쓰레드가 우선순위가 낮은 쓰레드를 기다리는 현상이 발생한다. 이때는 우선순위가 높은 쓰레드가 우선순위가 낮은 쓰레드에게 자신의 우선순위를 donate해 lock A을 release할 수 있도록 한다. 이를 priority donation이라 한다.
이때 한 쓰레드가 여러 쓰레드에게 donate를 받은 multiple donate와 donate가 연쇄적으로 일어나있는 nested donate를 고려해 priority donation을 구현한다.
3. Advanced Scheduler(Multi-Level Feedback Queue Scheduler)
MLFQS(Multi-Level Feedback Queue Scheduler) 는 donation을 사용하는 대신 최근에 얼마나 많은 cpu time을 사용했는지를 표현하는 recent_cpu와 다른 쓰레드에게 얼마나 nice한지를 나타내는 (nice 값이 높으면 다른 쓰레드의 cpu time을 뺏지 않음, 낮다면 다른 쓰레드의 cpu time을 뺏음) nice, 대기중인 쓰레드를 나타내는 load_avg를 이용해 주기적으로 priority를 재설정해준다.
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice
load_avg = (59/60) * load_avg + (1/60) * ready_threadsMLFQS의 목적은 우선순위가 낮은 쓰레드들이 오랫동안 cpu를 점유하지 못하는 starvation을 방지하는 것이다.
이때 고려해야할 점이 두 가지 있다.
첫번째는 recent_cpu와 load_avg 값이 실수값이지만 pintos는 커널에서 부동소수점 연산을 지원하지 않는다는 점이다. 따라서 고정소수점 연산을 직접 구현해 사용했다.
두번째는 recent_cpu, priority를 재설정 해줄 때 ready_list에 있는 쓰레드 뿐만이 아니라 실행중인 쓰레드, block된 쓰레드들도 모두 포함해야한다는 점이다.
구현은 어떻게든 할 수 있지만 OS가 어떻게 돌아가는지를 완벽하게 이해하는 것은 조금 어려운 것 같다.
남은 3주간 OS와 많이 친해지도록 해야겠다.
피드백 환영합니다.
-끝-
