운영체제 || 9. Process Scheduling II

1. Priority Scheduling

> 우선순위를 어떻게 할당하냐에 의해 알고리즘이 달라짐.

> preemptive, non-preemptive 둘 다 디자인 가능

 

> 이 우선순위 알고리즘에 몇가지 문제가 존재함

 

  a) Starvation 문제

>> 높은 우선순위가 계속 들어오게되면 낮은 우선순위를 가진 프로세스는 실행되지 못함

>> 해결방법으로는 ready queue에 있는 시간이 길어지면 일시적으로 우선순위를 높여주는 방법이 있음

 

  b) Priority inversion problem

>> 우선순위 역전 문제

>> 순위 높은순으로 진행해야하는데, 경우에따라 낮은 프로세스가 먼저 실행될 때가 있음.

>> 가장 유명한 예시로 PathFinder > Low 프로세스에서 LOCK을 걸어서 HIGH 프로세스대신 Middle 프로세스가 먼저 실행이 됨

 

>> 우선순위 역전의 해결법으로는 크게 두 가지가 있음.

 

    i) Priority inheritance protocol (PIP)

> 높은 우선순위가 낮은 우선순위에게 자신의 우선순위를 상속해주는 행위

> 이렇게 되면 middle 우선순위에 의해 역전당할 일이 없음. 왜냐면 더이상 LOW컨디션이 아니기 때문에

 

    ii) Priority ceiling protocol(PCP)

> 이건 미리 구현되어 있어야하는데, 어떤 리소스가 LOCK이 걸려있으면 해당 리소스를 홀딩 중에는 HIGH로 올라감.

 

이 둘의 차이는 PIP는 High에서 직접 상속받아오는거라면, PCP는 리소스가 해당 우선순위를 승격시켜줌

 

2. Round Robin

> FIFO구조이지만 짧은 시간동안 CPU의 권한을 할당받고, 다시 FIFO의 마지막으로 들어가는 구조

> time slice가 얼마나 길 지가 이슈

> 동일한 Time Slot을 할당해주고, 프로세스들이 번갈아가면서 사용함

> Preemtive한 알고리즘

> Starvation현상이 일어나지 않음(Starvation은 한 프로세스가 계속해서 할당받지 못하는 현상)

> 반응성을 향상시켜줌

 

평균 waiting time은?

> 전에도 포스팅했지만, waiting타임 구하는 가장 쉬운 방법은 turnaround time - CPU burst Time임

P1 + P2 + P3 + P4 =(16-7) + (21-9) + (10-2) + (13-3)

평균 waiting time = 11

 

평균 turnaround time은?

P1 + P2 + P3 + P4 = 16 + 21 + 10 + 13 

평균 turnaround time = 20

 

 

3. Multilevel queue scheduling

> 시스템에는 많은 다양한 프로세스들이 있음. 대표적으로 Interactive한 알고리즘, batch한 알고리즘 ...

> ReadyQueue가 왜 하나여야하냐?는 물음에서 시작된것

> 각 프로세스의 특성에 맞게 레디큐를 따로 둬서 각자 알맞은 알고리즘을 사용하게하자는 것

 

>> 큐 사이의 스케쥴링도 필요함

> 큐마다 우선순위가 다르게 지정할것인가? 아니면 큐 마다 RoundRobin을 적용하여 Time slot을 줄것인가?

> 그렇지만 우리는 프로세스의 타입의 예측이 힘들고, 심지어 어떤 프로세스는 타입이 실행중에 바뀌기도 함

> 그런 문제 때문에 나온것이 Multilevel Feedback Queue임.

 

4. Multilevel Feedback Queue(MLFQ)

> 프로세스가 어떤 동작을 보이냐에 따라서 큐 간 이동이 가능함.

> 각 큐는 설돠른 우선순위를 가지고있음

> 각 큐에서 실행되고 해당 큐에서 실행 완료되지 않으면 그 다음 큐로 우선순위가 낮아짐

> 리눅스 시스템에서 기본적으로 MLFQ를 채용중