[운영체제] 스케줄링 알고리즘 : Priority, FCFS, RR

 

오늘은 스케줄링 알고리즘 Priority, FIFO, RR에 대해서 알아보겠습니다.

 

 

  개요

지난 글에서 다룬 Scheduling의 종류 중에서 Short-Term Scheduling은 어떤 방법이 효율적이라고 할 수 있을까요??

 

사용자의 관점에서 본다면 response time. 즉, 내가 프로그램을 실행했을 때 실행되는 반응 속도가 빨라야할 것입니다.

하지만 시스템 적으로 바라본다면 CPU utilization. 즉, CPU를 얼마나 효율적으로 사용하는 지가 관건일 것입니다.

 

 

  스케줄링 판단 기준

그렇다면 스케쥴링을 판단하기 위한 몇가지 기준과 용어에 대해서 다뤄보겠습니다.

 

CPU utilization : CPU가 user의 프로세스들을 실행하기 위해 차지하는 시간의 비율

Throughput : 단위 시간동안 완수한 프로세스의 수

Turnaround time : 한 프로세스의 시작부터 끝까지 소요되는 시간

Response time : 사용자가 프로세스의 시작이나 어떠한 명령을 요청한 후, 프로세스가 반응하는데 소요되는 시간

Waiting time : 한 프로세스의 생성부터 종료까지 ready 상태에 있는 시간

 

 

   우선순위

기본적으로 프로세스는 PCB에 priority를 저장합니다. 만약 A프로세스가 우선순위 3을 갖고 있으면서 CPU에 배정되어 프로그램을 실행 중이라고 해봅시다. 근데 만약 프로세스 B가 우선순위 1을 갖고 들어온다면 프로세스 A는 OS에게 CPU를 빼앗기고 ready 상태로 들어가게 됩니다.

 

그런데 우리가 배웠을 때, ready Queue는 하나만 있다고 표시되어 있었고, 그러한 과정에서 어떠한 프로세스를 뽑을지 정하는 과정을 조금 깊게 확인해볼 필요가 있습니다.

 

 

하단의 그림을 보면 사실 우선순위를 이용하는 OS는 ready queue가 여러개입니다. 이러한 방식으로 우선순위가 높은 것을 먼저 가져올 수 있게 됩니다. 하지만 이렇게 되면 우선순위가 낮은 프로세스는 계속해서 프로세서에게 배정받길 기다리는 starvation 현상이 생길 것으로 보입니다.

 

이에, 각 운영체제에 대응하는 방식은 다르겠지만 기본적으로는 기다린 시간만큼 우선순위를 올려주는 방식을 이용합니다.

 

우선순위를 이용한다면 ready queue는 1개가 아니다.

 

한 가지 더 생각해볼 것은, 프로세스가 매우 적게 돌아가는 과정에서도 많은 ready queue들이 존재하게 되고 이는 쓸데없는 메모리 공간을 낭비하는 것처럼 보입니다.

 

하지만, 사실은 Queue가 배열로 구현된 것이 아닙니다. LinkedList로 구현된 큐이므로 메모리 공간은 PCB가 존재하는만큼만 공간을 차지하게 된다는 것을 알아둡시다.

 

 

  스케줄링 알고리즘

지금부터 FIFO와 RR 방식에 대해서 다룹니다. 이 두 알고리즘은 아래와 같은 예시의 조건에서 동일하게 설명하도록 하겠습니다.

Arrival Time은 프로세스가 메모리에 로드될 때의 시간을 의미하고, service Time은 해당 프로세스가 작업을 모두 마치기 위해서 소요되는 시간을 의미합니다.

 

 

  First-Come First-Served(FCFS, FIFO)

처음 들어온 프로세스에게 service TIme만큼을 할당합니다. 즉, 먼저 들어온 프로세스를 종료할 때까지 진행하는 방식을 의미합니다.

 

아래와 같은 형태로 서비스가 진행될 수 있습니다.

FIFO 방식의 service routine

 

위에서 B가 빨간 부분에 도착했음에도 불구하고 스케줄 정책에 의해 A의 service가 끝나고 B가 할당됨을 알 수 있습니다.

 

하지만 해당 정책은 단점이 분명하게 보입니다. 만약 매우 짧게 걸리는 프로세스임에도 이전에 service Time이 긴 프로세스가 실행 중이라면 매우 오래 기다려야합니다. 

 

해당 방식은 CPU-bound process들에게 좋습니다. 즉, I/O 연산이 많이 않고 단순한 compute가 수행되는 프로세스에게 유용하게 됩니다.

 

 

이제 위 방식의 waiting time을 구해봅시다. 각 프로세스의 waiting time은 아래와 같습니다. 특이한 점은 FIFO 방식에서는 waiting time과 response time이 동일하다는 것입니다. 프로세스가 자신에게 배정되는 즉시 끝날 때까지 진행하기 때문입니다.

 

A = 0, B = 1, C = 5, D = 7, E = 10

따라서 평균 waiting time 은 (0+1+5+7+10)/5 = 4.6초입니다.

 

하지만 이 FIFO 방식은 실행되는 순서에 따라 waiting time이 달라집니다. 실제로 여러분이 순서를 바꿔서 다시 waiting time을 계산해보면 알 수 있습니다.

 

 

  Round-Robin(RR)

Clock Interrupt가 들어올 때마다, 스케줄링하여 실행시킬 프로세스를 선택하는 방법입니다. 기본적으로는 FIFO 방식으로 작동됩니다.

 

RR에서 time slice가 1 지날 때마다 스케줄링을 진행하기로 세팅했다고 해봅시다. 그러면 1초에서 A 실행을 멈추고 스케줄링을 시작합니다. 하지만 ready 상태인 프로세스는 A 밖에 없으므로 다시 A를 실행시킵니다. 이후, 두 번째 clock Interrupt가 발생했을 때 스케줄링을 다시 하는데, B가 들어왔으므로 이제 B를 실행해줍니다.

 

RR은 FIFO 방식으로 작동된다고 하였으므로 B 다음에는 A가 실행되고 이를 반복합니다. 하지만 후에 다른 프로세스가 들어오게 된다면 해당 프로세스까지 규칙적으로 작동하게 될 것입니다.

 

RR의 waiting time을 구해봅시다.

A = 1, B = 10, C = 9, D = 9, E = 5

 

average awaiting time은 (1+10+9+9+5)/5 = 6.8이 되겠습니다.

이렇게 보면 사실 RR이 FIFO보다 꽤나 안 좋아보입니다.

 

response time을 확인해봅시다.

 

A = 0, B = 0, C = 1, D = 1, E = 2

average response time은 (0+0+1+1+2)/5 = 0.8입니다.

 

response time에서 압도적인 차이가 발생함을 알 수 있습니다.

 

 

하지만 이것은 time slice가 1씩 바뀔 때마다 스케줄링을 하도록 설정하였습니다. 우리는 이런 time quantum의 기준을 잘 설정해야하는데, 해당 설정을 적절하게 하는 것이 RR의 관건 사항이 되겠습니다.

 

---

 

이것으로 우선순위, FIFO, RR 스케줄링 알고리즘에 대해 다뤄봤습니다. 다음 시간에는 Shortest Process Next, Shortest Remaining TIme First에 대해서 다뤄보겠습니다. 감사합니다.