[06] 운영체제 - 스케줄링

안녕하세요.

시간이 지날수록 각종 팀프로젝트와 과제들로 인해 업로드가 점점 늦어지고 있네요...!

그래도 최대한 다음 수업 시간 전까지는 포스팅하기 위해 이렇게 글을 쓰려 노트북 앞에 앉았습니다.

이번 주에는 운영체제의 중요한 기능, 역할 중 하나인 CPU 스케쥴링 (CPU Scheduling)에 관해 포스팅 해보도록 하겠습니다.

그럼 바로 시작하겠습니다.

앞에 포스팅 해놓은 내용들을 다시 생각해보면 운영체제의 역할은 컴퓨터를 보다 효율적으로 

사용하게 해주는 중요한 역할을 하고 있습니다. 여기서 효율적이라하면 자원을 최대한 바쁘게 활용하는 것을 말하는데요.

그 중의 하나가 바로 MultiProgramming 기법이었고 거기에  time quantum의 개념을 도입한 것이 MultiTasking 기법이었습니다.

한가지 더 중요한 것이 바로 CPU의 스케쥴링이였는데요.

Scheduling ( 스케쥴링 )

보다 효율적인 자원의 활용을 위해 어떤 작업을 메모리에 올리고 어떤 작업에게 자원을 할당해야하는지를 결정하는 행위.

여기서는 메모리에 올라와 있는 작업들 중 어떤 것을 실행, 즉 어떤 작업에게 CPU 작업을 할당해야하는지를 결정하는 

Short-Term Scheduler에 관해 이야기해보도록 하겠습니다.

위에서 언급한 작업들은 크게 두가지 종류로 나눌수 있는데 

어떤 자원들을 사용하냐에 따라 다음과 같이 나눌수 있습니다.

1. CPU-burst : CPU 자원을 많이 요구하는 작업

2. I/O-burst : I/O 의 사용이 많은 작업

그리고 스케쥴링은 다음과 같은 프로세스(Process) 상태의 변화에서 발생하게 됩니다.

1. Running -> Waiting (e.g. I/O request)

2. Terminates

3. Running -> Ready (e.g. Interrupt)

4. Waiting -> Ready ( e.g. I/O Completion)

위의 상태 변화에 대해서는 이전에 다룬바가 있기 때문에 자세히 설명하지는 않도록 하겠습니다.

그리고 우리는 스케쥴링이 일어나는 4가지의 방법을 스케쥴링 방법에 따라 다시 두 부류로 나누어 볼 수 있습니다.

1번, 2번 : Nonpreemtive

3번, 4번 : Preemptive

그럼 다시 두가지 부류가 어떻게 다르고 어떤 특징을 갖고 있는지 살펴보도록 하겠습니다.

Nonpreemptive VS Preemptive

1. Nonpreemptive

Nonpreemptive 방식은 프로세스가 한번 CPU를 할당 받으면 프로세스가 스스로 CPU자원을 반납하기 전까지는

운영체제가 해당 자원을 회수할 수 없는 것을 말합니다. 

그러므로 time quantum 역시 존재하지 않게 됩니다.

2. Preemptive

Preemptive 방식은 위와 같이 스스로 자원을 반납하기 전에 해당 자원을 강제로 회수해 올 수 있는 방법을 말합니다.

그 예로는 주어진 time quantum이 다 끝나거나 우선순위가 높은 프로세스가 들어오는 상황이 있을 수 있습니다.

이러한 Preemptive 방식은 time quantum 등의 하드웨어적인 Interrupt가 필요하기 때문에 H/W의 지원을 요구합니다.

이렇게 강제로 CPU 자원을 회수해오면 당연히 그에 해당하는 문제점도 있을텐데요.

바로 데이터의 동시 접근으로 인한 데이터 손실이 있을 수 있습니다.

이러한 두 방법을 이용한 여러 스케쥴링 알고리즘이 존재하는데요.

알고리즘을 알아보는데 앞서서 알고리즘의 성능을 판단하는 기준들이 있는데 간단히 살펴도록 하겠습니다.

1. CPU Utilization - CPU를 최대한 바쁘게!

2. Throughput - 시간 단위안에 실행이 완료되는 프로세스의 수!

3. Turnaround Time - 하나의 프로세스가 시작에서 종료까지 걸리는 시간!

4. Waiting Time - 하나의 프로세스가 Ready Queue에서 기다린 총 시간!

5. Response Time - 프로세스가 첫 Output을 내는데 걸리는 시간!

Scheduling Algorithm

알고리즘의 분류에는 두가지가 있는데 Ready Queue를 하나만 사용하는지 여러개를 사용하는지로 나눌 수 있습니다.

<1개의 Ready Queue를 사용하는 알고리즘>

1. FCFS

FCFS는 "먼저 들어온 작업을 먼저 처리"  하는 방식입니다.

위의 그림을 해석해보자면 P1, P2, P3 순서대로 들어왔고, 각각의 CPU burst time은 24, 3, 3이 됩니다.

그러면 P1이 완료되는데 걸리는 시간은 24이고, P2는 24를 기다리고 작업을 수행하고,

P3는 P2의 CPU burst time 3을 더 기다린 27을 기다리게 됩니다.

그래서 평균 Waiting Time은 위와 같이 (0 + 24 + 27)/3 = 17 이라는 식이 나오게 됩니다.

그렇다면 다른 예를 들어보도록 하겠습니다.

위의 그림은 첫번째의 예시와 같은 작업들이지만 도착 순서를 바꾼 예시입니다.

첫번째 예시와는 달리 CPU burst time이 오래 걸리는 작업을 맨 뒤로 보냄으로써

평균 Waiting Time이 훨씬 짧아지는 것을 확인하실 수 있습니다.

이와 같이 FCFS에서 CPU burst time이  긴 작업이 먼저오게 됨에 따라

전체적인  Waiting Time이 증가되는 것을 Convoy Effect 라고 합니다.

이러한 현상이 발생하게 되면 CPU 자원의 효율성이 떨어지게 됩니다.

위의 계산법이나 작업의 처리를 보면 FCFS는 Nonpreemptive 스케쥴링 방식을 사용하였는데요.

그러면 Preemptive 방식을 사용하여 FCFS를 구현할 수 있을까요?

답은 불가능하다입니다. 그 이유는 FCFS 알고리즘의 방법 자체가 "먼저 들어온 작업을 먼저 처리"  이기 때문에 

운영체제가 강제로 CPU를 회수하고 다른 작업에게 할당하여 수행이 완료되는 순서가 바뀌는  Preemptive 방식에 모순이기 때문입니다.

2. SJF

SJF는 "CPU  burst time이 적은 것부터 수행하는 것" 을 의미합니다. (모두 같다면 FCFS)

위의 예시를 살펴보면 위의 에시는 작업이 끝날 때 까지 CPU를 계속 사용하는 Nonpreemptive 방식으로 스케쥴링 된 예시입니다.

가장 CPU burst time이 짧은 P4가 먼저 선택되고 P4가 종료되면 P1이 선택되고 차례로 P3와 P2가 선택되는 방식입니다.

그래서 Waiting Time은 수행되는 작업의 순서대로 0, 3, 9, 16 이 되고 Average Waiting Time 은 (3 + 16 + 9 + 0 ) /4 = 7이 됩니다.

SJF 알고리즘은 Preemptive 방식으로도 스케쥴링이 가능한데 그 예시는 다음과 같습니다.

위의 예시는 약간 복잡한데 한번 천천히 설명해보도록 하겠습니다.

일단 가장 먼저 도착한 P1에게 CPU를 할당시켜줍니다. 그리고 1초가 지나면 P2가 도착하게 되는데 둘의 CPU burst time을 비교하면

P1은 1초가 사용되었기 때문에 7이 되고 P2는 이제 막 들어왔으니 4가 됩니다. 그리하여 1초에서는 P2에게 CPU가 할당이 되어

P2가 CPU를 사용하게 됩니다. 이런식으로 매초마다 각각의 작업들의 CPU burst time을 비교해가며 가장 짧은 작업에게 CPU를 할당하는

스케쥴링을 작업을 수행하게 됩니다.

Waiting Time 을 계산해보면 P1은 제일 먼저 수행되지만 이후 순위에서 밀려나 다시 스케쥴링되기 까지 9초가 걸리므로 Waiting Time은 9가 됩니다. 그리고 P2는 들어오자마자 작업이 수행되고 완료되었으므로 Waiting Time은 0이 됩니다. 나머지 작업들도 계산을 해보면

P3와 P4는 각각 15, 9 가 됩니다. 그리하여 Average Waiting Time은 (9 + 0 + 15 + 2 ) / 4 = 6.5가 됩니다.

 

SJF 알고리즘은 사실상 각 작업들의 CPU burst time을 예측하여 알고 있어야 하므로 현실적으론 불가능한 이론상의 알고리즘입니다.

하지만 가장 빠른 스케쥴링 알고리즘으로 다른 스케쥴링 알고리즘들의 성능을 알아보는 척도가 되는 알고리즘입니다.

3. Priority Scheduling

Priority Scheduling, 즉 우선순위 스케쥴링은 우선순위가 높은 작업들을 먼저 수행하는 알고리즘인데 CPU burst time이 일종의

우선순위가 된다면 SJF 역시 Priority Scheduling이라고 할 수 있습니다.

이 알고리즘 역시 Preemptive와 Nonpreemptive 두 방식으로 모두 구현할 수 있습니다.

Priority Scheduling에는 문제점이 생길 수 있는데 바로 한번 우선순위가 밀리고 계속해서 높은 우선순위의 작업이 들어온다면

그 밀린 작업은 계속해서 CPU를 할당받지 못하게 되는 Infinite blocking ( Starvation ) 상태가 됩니다.

이러한 문제점을 해결하기 위해 도입된 방법이 Aging이라는 방법인데

Aging이라는 방법은 오랜 시간 기다린 작업의 우선순위를 일정 비율만큼 올려줌으로써 위와 같은 문제를 해결하는 방법입니다.

4. RR(Round-Robin) Scheduling

RR Scheduling은 time quantum을 할당하는 알고리즘으로 Preemptive의 방식으로만 구현할 수 있습니다.

위의 예시에서는 time quantum이 4초가 주어지는데 위의 예시를 살펴보면 P1에게 먼저 4초동안 할당이 되고 시간이 지나면

다시 P2에게 CPU가 4초동안 할당이 됩니다. 하지만 P2는 3초의 시간만을 사용하는데 이때 남은 1초를 기다리는 것이 아니라 

P2의 작업이 끝나자마자 바로 다시 처음부터 초기화되어 4초의 time quantum이 P3에게 할당이 됩니다.

위와 같은 방식으로 P1, P2, P3의 Waiting Time을 이용하여 Average Waiting Time을 계산해보면 (6 + 4 + 7)/3 = 5.66이 됩니다.

이러한 time quantum을 정하는 것도 굉장히 중요한데 다음 예시 그림을 살펴보도록 하겠습니다.

위의 예시에서 time quantum을 1로 정한 것과 10으로 정한 것이 있는데 단순히 시간을 계산하면 저렇게 나오지만

실제로 time quantum 안에는 Context Switching을 하는 시간까지 포함되어 있어 더욱 시간은 늘어나게 됩니다.

하지만 그럼에도 불구하고 time quantum을 짧게 가져가 전체 Waiting Time이 길어지는 방식을 체택하는 경우가 있는데

그것은 바로 사용자와 실시간으로 상호작용하는 작업이 바로 그 경우에 해당합니다.

<다수의 Ready Queue를 사용하는 알고리즘>

1. Multi-Level Queue Scheduling 

Multi-Level Queue Scheduling은 여러개의 Ready Queue를 사용하게 되는데

각 Queue에는 용도에 맞는 작업들이 들어가게 됩니다. 그리고 한번 Queue가 배정되면 바뀌지 않게 됩니다.

각각의 Queue에는 같거나 서로 다른 스케쥴링 알고리즘들을 갖고 있습니다.

그리고 각 Queue끼리의 우선순위가 다를 수 있는데 이러한 우선순위 때문에 특정 Queue만 수행되는 Starvation이 발생할 수 있습니다.

그래서 각 Queue마다 CPU를 사용 시간을 달리 적용하는 Time Slice 방법을 사용하여 특정 Queue가 CPU를 독점하는 일을 방지합니다.

2. Multi-Level Feedback Queue Scheduling

Multi-Level Feedback Queue Scheduling은 위의 알고리즘과는 다르게 Queue를 옮겨다닐수 있습니다. 

이러한 방식으로 Starvation을 예방할 수 있습니다.

이상으로 스케쥴링(Short-Term)이 무엇인지, 스케쥴링의 방법과 알고리즘에 대해서 살펴보았습니다.

중요한 만큼이나 많은 양을 다루었는데요. 조금이나마 공부하시는데 도움이 되기를 바래봅니다.

다음 시간에는 앞선 포스팅에서 다룬 Shared Memory와 같이

데이터를 동시에 접근해서 발생하는 문제인 충돌에 관해 알아보고

해결방법을 공부해보는 시간을 갖도록 하겠습니다.

감사합니다!