[OS] 7 - CPU scheduling (2)

 CPU Scheduling 알고리즘을 살펴보자

• FCFS (First-Come, First-Served) scheduling
• SJF (Short-Job-First) scheduling
• Priority scheduling
• RR (Round-Robin) scheduling
• MultiLevel Queue scheduling
• MultiLevel Feedback Queue scheduling

* 이 글에서 쓰이는 Burst time은 프로세스의 실행시간을 뜻한다.

FCFS (First-Come, First-Served)

** Nonpreemptive 방식으로 동작

 

말그대로 먼저 들어온 프로세스가 먼저 처리 되는것을 뜻한다.

 

ex)

다음과 같이 3개의 프로세스와 Burst Time이 주어진다.

 

P1은 0에 들어와 24만큼 수행하고 종료한다. p2는 p1이 종료된 24부터 3만큼 동작하고 종료한다. p3도 같은 과정을 거친다.

 

각 프로세스의 대기시간과 총 대기 시간 평균을 알아보자

 

P1의 대기시간 - 0 (첫 진입)

P2의 대기시간 - 24 (P1이 끝날 때 까지의 시간)

P3의 대기시간 - 27 (P1, P2 가 끝날 때 까지의 시간)

총 평균 - (0 + 24 + 27) / 3 = 17  인 것을 알 수 있다.

 

이제 다른 예제를 살펴보자

 

같은 동작을 통해 대기시간을 알아보면

 

P1의 대기시간 - 6 ( P2, P3 가 끝날 때 까지의 시간 )

P2의 대기시간 - 0 (첫 진입)

P3의 대기시간 - 3 ( P2가 끝날 때 까지의 시간 )

총 평균 - (6 + 0 + 3) / 3 = 3  인 것을 알 수 있다.

 

이와 같이 FCFS알고리즘은 알고리즘은 간단하지만 CPU의 최적 효율은 볼 수 없는 구조이다.

또한 먼저 들어온 것이 먼저 처리된다는 특성 때문에, 먼저 들어오는 프로세스가 아주 긴 Burst Time을 가질 경우 뒤의 프로세스들은 하염없이 기다려 Waiting Time이 커지게 되는 현상이 발생하는데 이를 Convoy Effect라 한다.

SJF (Short-Job-First)

** 기본적으로 Nonpreemptive 방식으로 동작

 

CPU가 가용될 떄, 다음 CPU Burst가 가장 작은 프로세스부터 할당되는 알고리즘이다.

다음과 같이 프로세스들이 있을 때, CPU Busrt 가 작은 순인 P4, P1, P3, P2 순서대로 할당된다.

 

이론 상 이처럼 동작하기 때문에, SJF보다 더 효율적인 알고리즘은 없다.

하지만 치명적인 단점이 있다. 다음 CPU Burst를 알아내기 어렵다는 점이다. 그렇기에 실용적이지 못하다.

 

여기서 Preemptive한 방식을 도입하면 Next CPU Burst를 조금 더 알아내기가 쉽다.a

다음은 Preemptive SJF의 예제이다.

여기서는 한 가지 개념이 더 등장하는데 프로세스의 도착시간이다. 프로세스의 도착시간과 실행시간을 통해 남은 CPU Burst로 Next CPU Burst로 책정하여 알고리즘을 구성할 수 있다. 

동작 방식을 보자

1. 먼저, P1 프로세스가 도착시간이 0이므로 첫 진입을 하여 실행된다.
2. 도착시간이 1인 P2프로세스가 도착하는데, P2의 Burst Time은 4 P1의 Burst Time은 8 - 1 = 7이므로, Next CPU Burst 가 더 작은 P2 프로세스가 P1프로세스의 점유를 뺏는다. 이때, P1은 1만큼 수행되었으므로 남은 Burst Time 은 8 - 1 = 7이되고, 이것이 P1의 CPU Burst Time이 된다.
3.  다음으로 P3 프로세스가 2에 도착하는데,  수행 중인 P2의 남은 Burst Time은 4 - 1 = 3, P3의 Burst Time은 9로, Next CPU Burst가 P2 < P3이므로 P3프로세스는 CPU를 점유하지 못한채 넘어간다.
4. P4프로세스가 3에 도착하는데, 이때 수행 중인 P2의 남은 Burst Time은 4 - 3 =1, P4의 Burst Time은 5로, Next CPU Burst가 P2 < P4이므로 P4프로세스는 CPU를 점유하지 못한채 넘어간다. P2가 계속 실행된다.
5. 실행시간 5가 되어 P2가 종료되고 다음 프로세스가 들어와야 할 차례이다. 이때, 각 프로세스의 남은 Next CPU Burst는 P1: 7, P3: 9, P4: 5 이므로 가장 작은 CPU Burst를 가진 P4가 할당되어 수행된다.
6. 이런 방식으로 도착시간, 실행시간을 계산하여 Preemptive한 방식으로 모든 프로세스가 동작을 마칠때 까지 반복한다.

각각 P1, P2, P3, P4의 대기시간을 통해 평균 대기시간을 구한 것이다.

Priority

말 그대로 프로세스에 우선순위가 주어져 우선순위가 높은 순대로 실행되는 스케줄링 알고리즘이다.

Burst Time이 낮을 수록 우선순위가 높아진다. (반드시 그렇지는 않는다.)

 

예시를 보자

프로세스의 우선 순위가 P2, P5, P1, P3, P4이므로 이 순서대로 프로세스가 실행된다.

 

이 알고리즘은 Preemptive, Non-Preemptive 두 가지 방식으로 수행 될 수 있다.

 

이 알고리즘에도 단점이 있다.

우선선위가 높은 프로세스가 CPU를 계속 점유하고 있으면 나머지는 하염없이 대기해야한다는 점이다. 이것을 indefinite blocking 또는 Startvation이라 한다.

 

Starvation을 해결하기 위해서는 Aging이란 방법을 사용하는데, 이 방법은 우선순위가 낮은 프로세스를 조금씩 우선순위를 높여주면서 CPU에 할당 될 수 있도록 만드는 방식이다.

RR (Round-Robin)

** Preemptive 방식으로 동작

 

TQ (Time-Quantom)이라는 개념이 등장한다.

TQ는 보통 10~100ms의 적은 수의 CPU 시간(time quantum)을 갖는다. 이 시간이 지나면 다른 프로세스가 점유하여 프로세스를 실행하게 된다 (TQ이내에 끝내지 못하면, 프로세스를 강제 점유하기에 Preemptive이다.)

 

예시를 보자, 이 예시의 TQ는 4이다.

(p1,p2,p3 순으로 동작을 가정한다.)

1. 먼저, P1이 CPU를 점유한다. P1의 총 Burst Time은 24인데, TQ는 4이므로 최대 4만큼만 수행할 수 있다.
2. P1의 TQ가 끝났으므로, P2가 실행된다. P2의 Burst Time은 3이므로 TQ이내에 모두 수행하고 P3에 CPU를 넘겨준다. 
3. P3가 실행된다. P3의 Burst Time은 3이므로 TQ이내에 모두 수행하고 남은 시간이 있는 P1에 CPU를 넘겨준다.
4. 이후 계속 P1이 동작한다.

Waiting Queue 에 n개의 프로세스가 있고 TQ이 q라면, 각 프로세스는 최대 q 시간 단위로 CPU 시간의 1/n을 한 번에 얻는다.

 

RR 알고리즘의 성능은 TQ에 의해 결정된다.

TQ가 매우 크면, FCFS 알고리즘처럼 동작한다.

TQ가 매우 작으면, Process Sharing 처럼 동작한다.

 

TQ가 너무 작으면 Context Switching이 빈번하게 일어나 그만큼 오버헤드가 발생하므로 너무 작지 않은 것이 좋다.

Multilevel Queue

Ready Queue를 성격에 따라 여러 개로 분할하고, 각각의 queue의 우선순위를 정한다.

보통 foreground, background Queue로 이루어져있다.

foreground (interactive) Queue는 CPU Burst가 짧은 프로세스가 들어오는 Queue로 우선순위가 높고,

backgroud (batch) Queue는 긴 시간 동안 수행된느 프로세스로 Queue의 우선 순위가 낮다.

그렇기 떄문에 Queue마다 다른 스케줄링을 적용해주어야하는데, foreground 는 RR 알고리즘을, background는 FCFS 알고리즘을 사용한다. 

 

 

각 프로세스는 해당 프로세스의 우선 순위에 따라 각각의 queue에 배치되고, queue 간 경쟁을 통해 하나의 queue가 CPU를 점유한다.

 

스케줄링 방식의 차이때문에 Queue간 점유시간의 차이가 켜져 Starvation이 일어날 가능성이 높다.

이를 해결하기위해 Time Slice를 사용하는데, Time Slice는 각 Queue의 CPU 할당 시간 비율을 적절하게 나누어서 제공하는 것이다.

Multilevel Feedback Queue

Multilevel Queue에서 발생하는 Starvation 및 구성 방법의 복잡함을 해결한 방식이다.

프로세스가 여러개의 Queue을 왔다갔다하면서 동작하는 방식의 알고리즘이다.

 

Multilevel Feedback Queue Scheduling은 다음과 같은 기준들에 의해 정의된다.

• Queue의 개수
• 각 Queue의 스케줄링 알고리즘
• 프로세스를 우선순위를 강등하는 시기에 사용되는 방법 (Queue를 이동하는 기준)
• 프로세스를 우선순위를 높이는 시기에 사용되는 방법 (Queue를 이동하는 기준)
• 프로세스가 서비스가 필요할 때 프로세스가 들어갈 대기열을 결정하는 데 사용되는 방법

ex)

총 3개의 Queue가 존재한다.

1. Q0 - RR 알고리즘, TQ - 8ms
2. Q1 - RR 알고리즘, TQ - 16ms
3. Q2 - FCFS알고리즘 

다음과 같은 규칙으로 스케줄링이 수행된다.

• 먼저, 스케줄러는 Q0의 프로세스를 모두 실행한다.
  • 8만큼 시간 동안 작업을 하여도 끝나지 않은 작업은 Q1으로 옮겨진다. Q1에서 해당 프로세스를 16 만큼 진행해도 끝나지 않으면 Q2이동한다.
• Q0이 비어 있을때만, Q1의 프로세스가 실행된다.
• Q2의 프로세스는 Q0과 Q1이 비어있을 때만 실행되어야한다.
• 스케줄링에 따라 Q2, Q1사이를 이동할 수 있다.

 

사진 출처: Provided by Operating Systems Concepts, 10th Edition (Abraham Silberschatz, Peter Baer Galvin, Greg Gagne)