[OS] Scheduling Algorithm

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

스케줄링 알고리즘에는 여러가지가 있다.

알고리즘이라면 성능을 젤 수 있어야 하지 않는가? 그래서 아래가 스케줄링 알고리즘을 평가할 수 있는 5가지 요쇼이다.

1. CPU utilization : 계속 CPU를 사용할수 있도록 하기 위함. CPU가 컴퓨터가 켜져있는 동안 계속 동작한다면 100% 그리고 CPU가 한번도 동작하지 않는다면 0%이다.

2. Throughput : 특정 시간동안 실행될 수 있는 프로세스 몇개인가?

3. Turnaround time : 메모리에 들어가기 위해 기다리는 시간 + ready queue에서 기다리는 시간 + CPU 실행하는 시간 + I/O하는 시간

4. Waiting time : 프로세스가 ready queue에서 기다리는 시간의 총 합

5. Response time : 프로세스가 응답을 시작할 때까지 걸리는 시간

자 그럼 이제 본격적으로 스케줄링 알고리즘에 대해서 공부해보자.

1. First-Come, First-Served Scheduling(FCFS Scheduling)

가장 간단한 스케줄링 알고리즘은 First-Come, First-Served Scheduling(FCFS Scheduling)이다. 먼저 ready queue에 들어온 프로세스가 먼저 실행되는 것이다.

만일 P1, P2, P3 순서대로 프로세스들이 ready queue에 쌓였다고 하고 각 프로세스들의 Burst Time이 아래와 같다고 했을 때, 이 알고리즘의 waiting time을 계산해보자.

Process	Burst Time
P1	24
P2	3
P3	3

이 프로세스는 다음과 같은 타임라인으로 수행될 것이다.

Wating Time을 계산해보자.

P1 : 0 - 0 = 0 (기다린 시간이 없으므로)

P2 : 24 - 0 = 24 (P1이 끝날 때까지 기다려야 했으므로)

P3 : 27 - 0 = 27 (P1과 P2가 끝날 때까지 기다려야 했으므로)

Waiting Time : (0 + 24 + 27) / 3 = 17

즉, 모든 프로세스가 평균적으로 17 milliseconds를 기다린 샘이다. 매우 비효율적이다.

위의 그림이 P3까지 있지 않고 P10까지 있다고 해보자. (단, P1을 제외한 나머지의 Burst Time은 3이라고 하자.) 이럴 경우 굉장히 비효율적이게 된다. 긴 프로세스 시간을 가지고 있는 P1하나를 처리하기 위해서 24 milliseconds + a를 기다려야 하기 때문이다. (이러한 현상을 convoy effect 라고 한다.) 해결책은 무엇일까? 간단하다! 짧은 것부터 먼저 처리하는 식으로 알고리즘을 바꾸면 된다.

2. Shortest-Job-First Scheduling (Shortest-Remaining-Time-First Scheduling)

SJF 스케줄링이라고 불린다. 짧은 프로세스부터 먼저 끝내고 보는 알고리즘이다.

각 프로세스들의 Burst Time이 아래와 같다고 했을 때, 이 알고리즘의 waiting time을 계산해보자. 

※ Arrival Time : Process가 ready queue에 들어온 시간

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

이 프로세스는 다음과 같은 타임라인으로 수행될 것이다.

Wating Time을 계산해보자.

Waiting Time : [ (10 - 1) + (1 - 1) + (17 - 2) + (5 - 3) ] / 4 = 6.5

Waiting Time은 6.5 milliseconds이다. 

위의 그림은 P1 → P2로 변할 때 Preemption이 발생한다.

※ Non-Preemption 일 때는 waitting time이 7.75가 된다.

SJF 스케줄링은 가장 이상적으로 waiting time을 줄일 수 있는 스케줄링 기법이다. 이 기법 중에서 가장 중요한 부분은 단연 가장 짧은 프로세스를 구하는 방법이다. 애석하게도 스터디 팀원들과 공부할 때 해결하지 못 했다. 

3. Priority Scheduling

우선 순위를 갖는 스케줄링이다. SJF 스케줄링에서 Burst Time을 일종의 priority로 해석한다면 SJF 스케줄링도 Priority Scheduling이 될 수 있다.

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

이 프로세스는 다음과 같은 타임라인으로 수행될 것이다.

Priority Scheduling에서 단점은 indefinite blocking 또는 starvation 이라고 불리우는 현상이 발생할 수 도 있다는 것이다. starvation은 어떤 특정 프로세스의 priority가 너무 낮아서 계속 실행이 안 되는 현상을 의미한다. 실제로 MIT에서 IBM7094 서버를 종료시키려고 했을 때, 8년 전에 실행시켜놓은 프로세스가 아직도 끝나지 않았었다던 극한 예도 있었다고 한다.

이러한 현상을 방지하기 위해 aging 이라는 기법을 이용한다. 사람은 시간이 지나면 나이를 먹는 것처럼 프로세스도 시간이 지나면 priority가 1씩 높아지게 된다. 따라서 아무리 낮은 priority를 가지고 있는 프로세스도 언젠가는 높은 priority를 갖게 되기 때문에 CPU에 의해 실행될 수 있게 된다.

4. Round-Robin Scheduling (RR scheduling)

이 기법은 time-sharing system을 기반으로 수행되는 스케줄링이다. Time-sharing system은 이전에 설명했듯이 CPU 점유시간을 최대한 몇 milliseconds로 제한해놓는 것이다. 이 시간을 time quantum이라고 한다. 즉, time quantum이 길어지면 한 프로세스가 사용할 수 있는 CPU 시간이 길어진다. RR 스케줄링은 다음과 같이 수행된다.

만일 P1, P2, P3 순서대로 프로세스들이 ready queue에 쌓였다고 하고 각 프로세스들의 Burst Time이 아래와 같다고 했을 때, 이 알고리즘의 waiting time을 계산해보자.

Process	Burst Time
P1	24
P2	3
P3	3

이 프로세스는 다음과 같은 타임라인으로 수행될 것이다. (단, time quantum 은 4)

P1 → P2로 바뀔 때 P1은 끝나지 않았지만 해당 Time quantum 동안 CPU를 계속 사용하였기 때문에 P2에 의해 Preemption 되었다.

RR 스케줄링에서 적절한 Time quantum을 정하는 것은 매우 중요한 일이다. Time quamtum을 너무 크게 잡으면 FCFS 알고리즘과 다를게 없어지고, 너무 적게 잡으면 프로세스들이 거의 매시간 preemption 되기 때문에 time-sharing 효과를 낼 수 있다. 대신에 preemption 될 때, 즉, context switching이 일어날 때의 시간이 소요된다.(context switch overhead)

5. Multilevel Queue Scheduling

Multilevel Queue 스케줄링은 ready queue를 몇 개로 나누어서 해당 queue 마다 다른 우선순위를 주고 다른 방법으로 구현을 시켜놓은 스케줄링 알고리즘이다. 

당연한 이야기이지만, 만일 낮은 priority를 가진 queue의 프로세스가 실행되고 있다가 높은 priority의 queue에 속하는 프로세스가 들어오면 preemption 된다. 이러한 시스템에서 만일 프로세스가 queue 를 왔다 갔다 할 수 있다면 그것이 multilevel feedback queue scheduling이다.

6. Multilevel feedback queue scheduling

이 스케줄링 알고리즘은 위에서 설명했듯이, 프로세스들이 서로 다른 priority를 가진 queue를 이동할 수 있다. 다음과 같이 이동한다.

모든 프로세스는 우선 가장 높은 priority를 가진 queue에 들어오고 특정 time quantum 만큼 CPU를 사용한다. (각 queue 마다 time quantum은 다르다. 낮은 priority queue로 갈수록 time quantum은 높아진다.) 그 프로세스가 끝나면 그 queue의 다른 프로세스를 수행할 것이고 그 프로세스가 끝나지 않으면 그 프로세스는 priority가 낮은 다음 queue로 보내진다. 그 queue에서도 끝나지 않으면 priority가 한 단계 더 낮은 queue로 보내진다. 

※ 하나의 queue가 비어지기 전까지는 그 queue의 priority보다 낮은 priority를 가진 queue의 프로세스는 실행되지 않는다.

대략적으로 유명한 스케줄링 알고리즘에 대한 설명은 끝난 것 같다. 힘들다...