프로세스 스케줄링_3 (FCFS, SJF, SRTF)

이때까지 프로세스 스케줄링에 대한 이론적인 개념을 배워보았다면, 오늘은 실제로 스케줄러에 적용되는 알고리즘을 하나씩 살펴보자.

 

 

 

1. FCFS / FIFO

 

First-Come, First-Served 이름에서 알 수 있듯이 큐에 들어온 순서대로 실행시켜주는 것이다.

 

일반적으로 Non-preemptive 하다.

 

또한, 아무리 앞의 프로세스의 실행시간이 길다고 하더라도 어쨌든 모든 프로세스에게 순서가 돌아가므로 starvation도 없다.

 

이 알고리즘의 문제로는 convey effect가 있는데, 한마디로 굉장히 실행시간이 긴 프로세스가 앞에 있으면, 뒤에 있는 프로세스들의 turnaround time 이 길어진다는 것이다.

 

FCFS

 

위의 그림에서 첫번째 경우가 대표적인 convoy effect이다. P1때문에 P2와 P3가 굉장히 오래 기다리는 것을 확인할 수 있다.

 

또한, 위의 그림에서 확인할 수 있듯이, FCFS 방식에서는 실행시간이 짧은 프로세스가 앞에 있을수록 waiting time과 turnaround time이 줄어드는 것을 확인할 수 있다.

 

 

 

2. SJF (Shortest Job First)

 

SJF방식은 스케줄러에 온 프로세스들을 보고, 가장 적게 걸릴만한 프로세스를 먼저 실행시켜주는 방법이다.

 

이 방식은 가장 짧은 waiting time을 보장해준다는 장점이 있다.

 

Non-preemptive 방식이고, Priority Scheduling 방식을 사용한다.

 

• 문제점

1) Starvation이 발생할 수도 있다.

  - 계속해서 실행시간이 짧은 프로세스들이 들어온다면 상대적으로 실행시간이 긴 프로세스는 starvation 발생

 

2) CPU burst time을 미리 측정하기 힘들다.

  - SJF 방식을 사용하려면 현재 큐에있는 프로세스들의 CPU burst time을 알아야하는데, 이걸 미리 아는것은 어려우므로 SJF를 쓰기 곤란하다.

 

 

 

3. SRTF (Shortest Remaining Time First)

 

어떤 새로운 job이 들어왔을 때, 각 task의 남은 시간을 따져보고 가장 짧은 녀석에게 CPU를 할당해주는 방식이다.

 

SJF 방식의 preemptive 버전이라고 보면 된다.

 

job이 올 때마다 각 task의 남은 시간을 계산을 해주어야 하는데, 이 때 현재 실행중인 task도 포함이다.

 

SRTF

 

위의 그림은 SRTF 방식을 나타낸 그림인데, P3가 프로세스에 들어오는 순간 각 task의 남은 시간을 따져보면,

 

P1 : 6, P2 : 2, P3 : 9 이므로(P1이 2만큼 지났을 때 P2가 들어왔다고 가정) 가장 짧은 P2가 계속해서 도는 것이다.

 

SRTF방식 또한 starvation이 발생할 수 있다.

 

 

 

4. Priority Scheduling

 

각각의 job들은 priority를 가지고 있고, 그 priority에 따라서 실행순서를 정해주는 방식이다.

 

preemptive할지, Non-preemptive할지는 설계자 마음이다.

 

이 경우 문제점은 크게 두가지가 있는데, 하나는 starvation이고, 다른 하나는 priority inversion problem이다.

 

첫째로, 자신보다 priority가 높은 job들이 계속 오면 starvation이 발생할 수 있는데, 해결방법으로는 두가지가 있다.

 

1) aging - 시간이 지나면 조금씩 age를 먹고, 이를 반영하는 방식

 

2) priority boosting - priority를 임의로 조정하는 방식

 

 

두번째 문제점으로는 priority inversion problem이 있다.

 

이 문제점은 Mars pathfinder라는 화상탐사로봇에서도 발생한 문제점인데,

 

어떤 priority 스케줄 시스템에서 낮은 priority task가 high priority task가 필요로하는 자원을 잠깐 잡고 있는 사이 그 시점에 low보다는 높고 high보다는 제 3의 priority녀석이 끼어들어 high priority task가 더이상 진행하지 못하도록 하는 문제점이다.

 

이게 뭔소린지 읽어도 모를것이다...; 그림으로 한번 이해해보자!

 

priority inversion

 

위의 그림에서 보면, low task가 lock을 잡고있는동안, high task가 실행이 되었고, 이 high task가 low task의 자원이 필요해서 마저 처리를 하라고 돌려보내줘서 low task가 자원을 처리하는 동안 middle task가 갑자기 두둥등장해서 priority를 뺐어가버린다. 이 동안 low task 가 자원 처리를 못마쳐서 high task가 계속 못돌아가는 것이다...!

 

아무튼 이러한 priority inversion은 두가지 해결방법이 있는데,

 

1) Priority ceiling protocol (PCP)

 

 - 특정 프로세스가 resource를 잡는 순간 priority를 미친듯이 높여주는 것이다. 그리고 resource를 release 하는 순간 다시 priority를 원래대로 돌려놓는 방식이다. 위의 예제에서는 high가 수행되기 전에 low가 resource를 잡는 순간(acquire) priority를 최대로 높여주어 low를 다 수행하고 난 뒤 high 를 수행하는 것이다.

 

2) Priority inheritance protocol (PIP)

 

- high task가 low task가 가진 자원이 필요하다면, 필요한 순간, low 의 priority를 올려주는 것이다. 즉, high가 수행되고 다시 low의 lock을 처리하러 돌아갔을 때 low의 priority를 올려주는 것이다.

 

이 둘의 차이는, resource를 잡는 low를 다 처리하고 high를 실행하느냐 (PCP), 아니면 high갔다가 다시 low의 lock을 끝까지 다 실행하느냐 (PIP)의 차이이다.

 

 

좀 글로 설명하기 애매한 부분이라서, 내가 쓰면서도 이게 이해가 될까... 생각이 든다.. 나중에 글쓰기 스킬이 더 늘어난다면 다시 정리해보겠다...ㅠㅠ

 

 

 

5. Round Robin Scheduling

 

모든 job을 time slice(=scheduling quantum)의 크기로 쪼개고, 한 slice 씩 모든 task들을 concurrent 하게 돌리는 방식이다.

 

즉, circular FIFO queue 로 처리하는 것이다.

 

각 time slice가 지나면 바로 다른 task로 넘어가므로 preemptive하다.

 

모든 task들이 계속해서 돌아가므로 starvation이 없다.

 

이 방법의 경우, 굉장히 짧은 시간 내에 실행이 시작되므로, response time이 개선된다.

 

만약, time slice가 너무 짧다면 - context switch overhead가 너무 클 것이다.

 

반대로 time slice가 너무 길다면 - responsive가 줄어들 것이다.

 

그래서 한마디로 time slice를 잘 결정해야 한다.

 

RR을 약간 변형하여 job마다 time slice를 다르게 줘서 특정 job에 가중치를 주는 방법도 있다.

 

 

 

6. Multilevel Queue Scheduling

 

큐를 여러개 준비하고, 각각의 큐에 각각 다른 스케줄링을 적용하는 방식이다. 이 때, 큐들끼리는 priority를 가진다.

 

Multilevel Queue

 

그림을 보면 딱 이해가될 것이다. 바로 이것이 Multilevel queue scheduling이다.

 

각각의 큐(네모박스)는 다른 스케줄링 알고리즘을 사용할 것이다.

 

하지만 이 방식의 경우에는 새로운 job이 들어왔을 경우 어느 큐로 분류해야 할지 애매하다는 불편함이 있다. 이 불편함을 극복하기 위해 나온것이 MLFQ이다.

 

 

 

7. Multi Level Feedback Queue (MLFQ)

 

새로운 job이 들어오자마자 어느 큐로 들어갈지 애매하니, 일단 그냥 돌려보고, 피드백 받으면서 어느 큐에 집어넣을지 결정하는 방식이다.

 

이 방식은 실제로 리눅스에서 사용하는 방식이다. 리눅스에서 큐 끼리의 priority는 RR을 변형하여 큐마다 time slice를 다르게 주어서 사용하는 방식을 사용한다. (priority 높을수록 time slice 많이줌) 이렇게 하면, starvation이 없지만 priority inversion은 발생할 수도 있다.

 

 

오늘 배운 내용을 정리해보면,

 

1.프로세스 스케줄링 방법에는 FIFO, SJF, SRTF, MLFQ, RR, Priority를 이용하는 방법등이 있다.

 

2. 리눅스에서는 MLFQ쓴다.

 

본 내용은 공부하며 정리한 것으로 오류가 있을 수 있습니다.