[OS] CPU 스케줄링

CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다. 이때 다음 프로세스가 어느 프로세스 인지를 선택하는 알고리즘을 CPU Scheduling 알고리즘이라고 한다. 간단히 생각해보면 먼저 온 프로세스가 먼저 실행되는 것이 가장 좋을 것이라 생각할 수 있다. 하지만 여러 상황에서 사용되는 컴퓨터 환경에서 꼭 그렇지만은 않다. 그러므로 CPU 스케줄링에는 여러가지 방법이 존재한다.

1. 선점(Preemptive) VS 비선점(Non-Preemptive)

1.1 선점(Preemptive)

선점(Preemptive)은 프로세스가 CPU를 점유하고 있는 동안 IO나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다. 즉, 프로세스가 정상적으로 수행중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있는 것이다.

1.2 비선점(Non-Preemptive)

비선점(Non-Preemptive)은 말그대로 선점의 반대이다. 한 프로세스가 한 번 CPU를 점유했다면 IO(프로세스 상태가 실행 -> 대기로 변경되는 경우) 혹은 프로세스가 종료될 때 까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.

2. Scheduling Criteria

Scheduling Criteria (척도)는 스케줄링의 효율을 분석하는 기준들이다.

• CPU Utilization(CPU 이용률 : %) : CPU가 수행되는 비율
• Throughput(처리율, jobs/sec) : 단위 시간당 처리되는 작업 수(처리량)
• Turn-around-time(반환 시간) : 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 걸린 시간이다. (CPU, waiting, IO등 모든 시간을 포함한다.) 반환시간은 짧을 수록 좋다.
• Waiting time(대기시간) : CPU를 점유하기 위해 ready queue에서 기다린 시간을 말한다.(다른 큐에서 대기한 시간은 제외한다.)
• Response time(응답시간) : 일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다.

3. CPU Scheduling Algorithms

3.1 First-Come, First-Served(FCFS)

FCFS는 먼저 온 프로세스가 먼저 CPU를 점유하는 방식이다. 이는 매우 단순하고 많이 사용하는 방법이지만, 모든 부분에서 효율적인 것은 아니다. 

 

위 그림은 각 프로세스가 사용한 시간(burst time)을 나타낸다. 평균 대기시간을 계산하면 다음과 같다.

• Average Waiting Time = (0 + 24 + 27) / 3 = 17 msec

만약 프로세스가 들어온 순서가 P3, P2, P1이라면 아래 그림과 같을 것이다.

• Average Waiting Time = (6 + 3 + 0) / 3 = 3 msec

두 예제에서 모든 프로세스가 끝난 시간은 30 msec으로 같으나 평균 대기시간으로 봤을 때는 위는 17 msec, 아래는 3 msec으로 차이가 난다. 즉, 들어온 순서대로 수행한다고 반드시 효율적인 것이 아닐수도 있다는 것을 알 수 있다.

위 예제처럼 순서대로 들어온 것을 Convoy Effect라고 한다. 이는 CPU 시간을 오래 사용하는 프로세스가 먼저 수행하는 동안 나머지 프로세스들은 그만큼 오래 기다리는 것을 말한다. P1이 수행되는 동안 P2, P3는 오래 기다리고 있는 것을 확인할 수 있다. 이는 FCFS의 단점 중 하나이다. 그리고 FCFS는 비선점이다. 하나의 프로세스가 끝나기 전에는 다른 프로세스가 끼어들 수 없다.

3.2 Shortest-Job-First(SJF)

SJF는 가장 짧게 수행되는 프로세스가 가장 먼저 수행되는 것을 말한다. FCFS에서 보았듯이 수행 시간이 짧은 프로세스가 먼저 오는 것이 평균 대기시간이 짧은 것을 알 수 있었다. 이를 이용한 것이 SJF이다.

위 그림의 평균 대기시간을 계산하면 다음과 같다.

• Average Waiting Time (AWT) : (3 + 16 + 9 + 0) / 4 = 7 msec

위 표를 FCFS를 사용한다면 아래와 같다.

• Average Waiting Time(AWT) : (0 + 6 + 14 + 21) / 4 = 10.25 msec

SJF와 FCFS의 평균 대기시간을 살펴보면 SJF 가 더 짧은 것을 확인할 수 있다. SJF가 평균 대기시간 기준으로 어떠한 방법보다 짧은 것은 수학적으로 증명되었다. 그러므로 어떠한 예제를 보더라도 SJF가 AWT는 가장 짧다.

이를 보면 SJF가 가장 효율적인 CPU 스케줄링 방법인것 같지만 이 스케줄링 방식은 매우 비현실적이다. 왜냐하면 현실적인 컴퓨터 환경에서는 프로세스의 CPU 점유 시간(burst time)을 알 수 없다. 왜냐면 한 프로세스가 실행되는 중에는 많은 변수가 존재하기 때문에 CPU 점유시간을 알려면 실제로 수행하여 측정하는 수 밖에 없다. 실제 측정한 시간으로 예측해서 SJF를 사용할 수도 있지만, 이는 오버헤드가 매우 큰 작업으로 잘 사용되지 않는다.

SJF는 선점과 비선점 방식 둘다 사용가능하다.

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

기존과 다르게 도착시간이 추가됐다. 첫째로 비선점 방식으로 확인해보자.

가장 먼저 도착한 P1이 수행되는 동안 P2, P3, P4 모두 도착하지만 비선점이므로 이미 수행중인 프로세스가 끝날때 까지 기다려야 한다.

• Average Waiting Time (AWT) : (0 + 7 + 15 + 9) / 4 = 7.75 msec

두번째는 선점 SJF를 살펴보자

이번에는 선점 방식이므로 프로세스가 도착할 때 마다, 어느 프로세스가 가장 짧은 것인지 선택해야 한다. 주목할 점은 P2 프로세스가 도착했을 때, 현재 남은 burst time 중 가장 짧은 프로세스가 P2이므로 P1을 수행하던 것을 멈추고 P2가 실행된다.

• Average Waiting Time (AWT) : (9 + 0 + 15 + 2) / 4 = 6.5 msec

선점 SJF은 현재 남아있는 시간 중 가장 짧은 프로세스를 선택하므로 Shortest-Remaining-Time-First(최소 잔여시간 우선)이라 불리기도 한다.

3.3 Prioirty

Priority 스케줄링은 우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘이다. 운영체제에서 일반적으로 우선순위는 정수값으로 나타내며, 적은 값이 우선순위가 높다. (Unix/Linux 기준)

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

표에서 우선순위 값이 가장 낮은 순서대로 수행한 모습을 나타낸 그림이다.

• Average Waiting Time (AWT) : (6 + 0 + 16 + 18 + 1) / 5 = 8.2 msec

우선순위를 정하는 방법은 크개 내부적인 요소와 외부적인 요소 두 가지로 나뉜다.

• Internal : 수행시간, 메모리/IO/CPU 소비량(적은 것 먼저)
• External : 유료 서버 컴퓨터의 경우 높은 등급의 사용자의 프로세스를 높힘. 혹은 정책에 의해 우선순위가 높아짐.

Priority 스케줄링 역시 선점과 비선점 방식 모두 사용할 수 있다. 중간에 더 우선순위가 높은 프로세스가 입력되면 프로세스를 밀어내고 높은 우선순위의 프로세스가 먼저 실행된다면 선점, 그렇지 않고 우선순위가 높은 프로세스가 입력되도 프로세스를 밀어내지 않으면 비선점 스케줄링이다.

Priority 스케줄링의 문제점

Priority 스케줄링의 문제점은 Starvation(기아)가 있다. Starvation은 CPU의 점유를 오랫동안 하지 못하는 현상을 말한다. Priority 스케줄링 방식에서 우선순위가 매우 낮은 프로세스가 ready queue에서 오랫동안 대기하고 있다고 가정해보자. 이 프로세스는 아무리 기다려도 CPU를 점유하지 못할 가능성이 매우 크다. 실제 컴퓨터 환경에서는 새로운 프로세스가 자주 ready queue에 들어온다. 이러한 프로세스가 모두 우선순위가 높은 상태라면 이미 기다리고 있던 우선순위가 낮은 프로세스는 하염없이 대기 상태로 남아 있을 수 밖에 없다.

Aging

이를 해결하는 방법 중 하나는 Aging 기법이다. ready queue에서 프로세스가 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 것이다. 이렇게 하면 우선순위가 낮은 프로세스라 하더라도 기다리는 시간이 길어질수록 우선순위가 높아져 수행될 가능성이 높아지게 된다.

3.4 Round-Robin(RR)

Round-Robin은 원 모양으로 모든 프로세스가 돌아가며 스케줄링하는 것을 말한다. 이는 시분할 시스템에서 주로 사용하는 방식이다. 일정 시간을 정해서 하나의 프로세스가 이 시간동안 수행하고 다시 대기 상태로 돌아간다. 그리고 다음 프로세스가 역시 같은 시간동안 수행한 뒤에 대기한다. 이러한 작업을 모든 프로세스가 돌아가면서 하며, 마지막 프로세스가 끝나면 다시 처음 프로세스로 돌아와서 반복한다.

여기서 일정 시간을 Time Quantum(Time Slice)라 부른다. Time Quantum은 일반적으로 10 ~ 100msec 사이의 범위를 갖는다. Round-Robin은 기본적으로 선점이다. 한 프로세스가 종료되기 전에 time quantum이 끝나면 다른 프로세스에게 CPU를 넘겨주기 때문이다.

 

Process	Burst Time(msec)
P1	24
P2	3
P3	3

Time Quantum

4 msec

 

Round-Robin 방식에서는 Time Quantum이 끝나면 CPU는 현재 프로세스를 대기상태로 보내고 다음 프로세스를 수행한다. 예제에서 P1이 0msec에 수행을 시작하여 종료되기 전에 time quantum 시간이 끝나며 P2가 수행되는 모습을 볼 수 있다. 그리고 P2, P3는 Time Quantum이 끝나기 전에 수행이 끝나고 나머지 P1은 다른 프로세스가 없으므로 종료될때 까지 계속해서 수행하는 모습이다.

• Average Waiting Time (AWT) : (6 + 4 + 7) / 3 = 5.66 msec

RR 방식은 Time Quantum 크기에 따라 AWT 와 같은 스케줄링 척도가 바뀐다. Time Quantum에 매우 의존적인 것이다.

만약 Time Quantum 크기가 무한에 가깝게 설정한다면 FCFS와 동일하게 작동한다. 반대로 0에 가깝게 설정하면 switching overhead가 매우 증가하여 비효율적이다. 결과적으로 적당한 크기로 설정해야 하는데 일반적으로 10 ~ 100msec으로 정한다.

3.5 다단계 큐(Multilevel Queue : MLQ)

먼저 프로세스 그룹에 대해 살펴보자. 프로세스는 기준에 따라 여러 그룹으로 나눌 수 있다.

• 시스템 프로세스(System Process) : 운영체제 커널 수준의 프로세스. 시스템 요소는 중요하므로 우선순위가 높아야 한다.
• 대화형 프로세스(Interactive Process) : 유저 수준의 대화형 프로세스. 상호작용은 바로바로 작동해야 하므로 우선순위가 높다.
• 대화형 편집 프로세스(Interactive Editing Process) : Word와 같은 상호작용을 하는 편집기
• 일괄처리 프로세스(Batch Process) : 상호작용 없이 컴퓨터가 적당히 일괄적으로 처리하는 프로세스. 지금 당장 처리해야할 일보다는 우선순위가 낮다.
• 학생 프로세스(Student Process)

위와 같이 여러 성격에 따라 프로세스 그룹을 나눌 수 있는데 이를 하나의 큐에 사용하는 것은 비효율적이라고 판단된다. 그래서 각 그룹에 따라 큐를 두어서 여러 개의 큐를 사용하는 것이 Multilevel Queue 방식이다.

각 큐마다 다른 규칙을 지정할 수 있다.

먼저, 큐마다 우선순위를 지정할 수 있다. 프로세스 그룹을 보면 System Process는 커널 수준에서 중요한 작업이므로 우선순위가 높은 그룹이라 볼 수 있다. 위 그림에서 System Process, interactive Process, Batch Process 순으로 우선순위가 높다. Batch 프로세스는 운영체제의 개입이 매우 적으므로 우선순위가 가장 낮다고 볼 수 있다.

위의 방식 이외에도 큐에 따라 여러 기준을 둘 수 있다. 큐마다 CPU 시간을 다르게 줄 수도 있고, 큐마다 다른 스케줄링 방식을 사용할 수도 있다.

3.6 다단계 피드백 큐(Multilevel Feedback Queue : MLFQ)

MLQ 방식과 같이 여러 개의 큐를 사용한다는 점에서 유사하다.

먼저 모든 프로세스는 가장 위의 큐에서 CPU 점유를 대기한다. 이 상태로 있다가 이 큐에서 기다리는 시간이 너무 오래 걸리게 되면 아래의 큐로 프로세스를 옮긴다. 이와 같은 방식으로 대기 시간을 조정할 수 있다. 그리고 MLFQ에서도 큐마다 다른 스케줄링, 다른 우선순위 등을 사용할 수 있다.

만약 우선순위 순으로 큐를 사용하는 상황에서 우선순위가 낮은 아래의 큐에 있는 프로세스에서 Starvation(기아)상태가 발생한다면 이를 우선순위가 높은 큐로 옮길 수도 있다.

대부분의 상용 운영체제는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 사용한다. 프로세스의 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율을 높일 수 있는 방법을 선택한다.