[Nachos] 4. Priority Scheduler 구현

[Nachos] 4. Priority Scheduler 구현

1. 문제제기

a) 목표

현재 디폴트 값인 Round-Robin 스케줄러를 통해서 실행되고 있는 나쵸스 프로그램을, 아직 덜 구현된 Priority 스케줄러를 사용하여 구현한다.

b) 상황

현재 PriorityScheduler 클래스에는 내부클래스로 PriorityQueue와 ThreadSate가 선언되어있고 이 중 ThreadState의 맴버함수중getPriority(), EffectivePriority(), SetPriority()가 아직 덜 구현되어있다.

기존에 정의되어있는 priority를 사용하면 심각한 deadlock에 빠질 가능성이 있다.

예를 들어 설명하면 3의 우선순위를 가진 스레드 A와 5의 우선순위를 가진 스레드 B가 있고 두 스레드는 하나의 공유변수가 있다고 가정한다. 또한 공유변수가 있기 때문에 lock을 이용하여 serialize를 한다고 가정한다. 이 때 만약에 공유변수에 접근할 수 있는 Lock을 쥔 상태로 sleep에 빠진다면 기존의 정의되어있는 getPriority()만 구현된 Priority 스케쥴링은 DeadLock에 빠진다. 왜냐하면 스케줄러는 A가 sleep한 이후 우선순위5인 B를 실행할 것이고 동시에 B는 A가 Lock을 release 하길 기다릴 것이다. 스케줄러는 우선순위가 B(5)보다 낮은 A(3)에게 CPU를 할당하지 않을 것이므로 서로서로 끝나기를 기다리는 상태가 된다.

이 같은 문제를 해결하기 위해 2가지 해결책을 사용할 수 있는데 첫째는 aging 방식으로 A 가 시간이 지나 B와 우선순위가 같아지는 시점이 오도록 만들면 A가 실행되어 데드락이 해결될 것이다 두 번째 방법은 우선순위가 높은 스레드 B가 A에게 CPU를 양보하는 것이다. 이를 전문적인 용어로 Priority-Donation이라 하는데, 아래 코드는 두 번째 방법을 사용하여 이러한 문제를 해결하고자 한다.

2. 분석 및 알고리즘

a) getPriority()코드 분석

PriorityScheduler.getPriortity()

 

ThreadState.getPriority()

b) getEffectivePriority() 코드 분석

 

c) setPriority()코드분석

 

d) PrioritySchedulerTest.java 코드분석

 

3. 결과 화면

4. 결론 및 고찰

 낮은 우선순위를 가진 T1 스레드가 Lock을 쥔 채로 sleep 하고, 높은 우선순위를 가진 T2 스레드가 이후에 실행되어 lock을 acquire 하는 환경을 가상적으로 만들었다. 이 때 이전 과제에서 구현하였던 Threa.join과 conditional variable을 사용하였다. 결과를 보면 T2가 lock을 호출하면서 T1 에게 CPU를 양보하여 데드락에 걸리지 않는 확인할 수 있다.

Priority 스케줄링을 작성해보면서 이 스케줄링의 장점과 약점에 대해서 정확하게 알 수 있게 되었다. 또한 그 약점을 극복할 수 있는 방법을 알고 구현하여 보면서 눈으로 확인할 수 있었다.  어떠한 스케쥴링방식을 도입할 때 그 알고리즘의 장점과 특히 단점을 분석하여 최대한 오류가 없도록 또한 각각의 기능이 독립적으로 구현되어야 함을 절실히 알 수 있었다. 또한 이번 과제를 통해 프로그래밍 언어의 정확한 문법과 보이지 않는 은닉에 대해서도 깊이 공부할 수 있는 계기가 되었던 것 같다. 

nachos (2).zip

0.39MB

PriorityScheduler 소스코드