[ 운영체제 ] 프로세스 스케줄링(Process Scheduling)

💡 이번 글에서 (프로세스, 쓰레드, Job, Task)스케줄링을 혼용해서 쓴다! 💡

Basic Concept

CPU 스케줄링이란, ready 큐에 있는 프로세스 중 누구에게 CPU를 할당할 것인지 결정하는 알고리즘이다. 먼저, 이번 글에서 자주 쓰이는 용어에 대한 정리를 하겠다.

 

• CPU 스케줄러 : 프로세스 스케줄링을 수행하는 운영체제의 컴포넌트 모듈이다. 커널 안에 있는 알고리즘(코드)로 봐도 무방.
• Dispatch(er) : 스케줄러 안에 있는 모듈 중 하나로, 스케줄러에 의해 선택된 쓰레드에게 CPU를 할당하는 행위.
• CPU burst : CPU만 사용. ex) CPU burst time 작업 시작부터 종료까지 순수하게 CPU만 사용하는 시간.
• CPU bound : CPU를 많이 사용한다는 뜻. ex) CPU bound process란 CPU burst time이 긴 프로세스를 말한다.
• Preemptive(선점) : OS가 필요에 따라 프로세스로부터 CPU를 뺏을 수 있다.
• Non-Preemptive(비선점) : OS가 프로세스로부터 CPU를 뺏을 수 없다. 따라서 프로세스가 끝날때까지 기다려야한다. 

선점(Preemptive)과 비선점(Non-Preemptive)은 워낙 중요해서 설명을 추가하겠다. 프로세스가 선점이냐 비선점이냐에 따라 스케줄링의 장단점이 달라진다. 응답 시간의 개념은 바로 아래 Scheduling Criteria 파트에 있으니 참고하길 바란다. 

 

Preemptive Scheduling

• 장점 : 응답 시간(Response Time)이 감소한다. 처음 레디 큐에 들어온 프로세스가 CPU를 빨리 할당받을 수 있기 때문.
• 단점 : CPU에 올라가는 프로세스가 수시로 바뀔 수 있으므로 context switch 오버헤드가 증가한다.

Non-Preemptive Scheduling

• 장점 : CPU에 프로세스가 한 번 올라가면 끝날때까지 쓰므로 context switch 오버헤드가 감소한다.
• 단점 : 응답 시간(Resonse Time)이 증가한다. 처음 레디 큐에 들어온 프로세스가 CPU를 할당 받으려면 오래 기다려야 하기 때문.

Scheduling Criteria

CPU 스케줄링의 목표는 시스템 성능의 최적화다. 그렇다면 어떤 스케줄링 알고리즘이 좋은 것일까? 이 질문에 답을 하기 위해서는 기준이 있어야 한다. 스케줄링 알고리즘을 평가하는 다섯 가지 기준에 대해 소개한다. 

 

• CPU utilization : CPU 가동률.
• Throughput : (Jobs / Time) 값으로 시간당 처리하는 Job의 개수.
• Turnaround Time : 특정 프로세스가 완료 될 때까지 걸린 시간. (Completion Time - Arrival Time)
• Waiting Time : 프로세스가 CPU를 할당받기까지 ready queue에서 기다리는 시간.
• Response Time : 프로세스가 처음 CPU를 할당 받기까지 걸리는 시간. (First Run Time - Arrival Time)

그렇다면 이제 다시 질문해 보자. 어떤 스케줄링 알고리즘이 좋은 것일까? 이제 위 기준을 근거로 대답할 수 있다. 각 기준에 대해 효율적인 알고리즘이란 아래와 같다.

 

• Maximize CPU utilization : CPU가 최대한 쉬지 않게 하는 것이 좋다.
• Maximize Throughput : 같은 시간에 여러 개의 Job을 처리하는 것이 좋다.
• Minimize Turnaround Time : 프로세스까 빨리 완료될수록 좋다.
• Minimize Waiting Time : 프로세스가 레디 큐에서 빨리 나올수록 좋다.
• Minimize Response Time : 프로세스가 CPU를 빨리 할당 받을수록 좋다. 

이 글에서는 스케줄링 알고리즘의 평가 척도로 Average Waiting Time을 사용한다. 

Scheduling Algorithms

CPU 스케줄링 알고리즘은 레디 큐에 있는 프로세스 중 어떤 녀석에게 CPU를 할당할 것인지 결정하는 알고리즘이다. 여기서 소개할 알고리즘은 크게 다섯 가지다.

 

• First-Come, First-Served (FCFS) Scheduling - 선착순
• Shortest-Job-First (SJF) Scheduling - 짧은 아이부터
• Shortest-Remaining-Time-First (SRTF) Scheduling - 조금 남은 아이부터
• Highest-Response-Ratio(HRRN) Scheduling - response ratio가 큰 아이부터
• Round-Robin Scheduling - 똑같이 돌아가면서 차례대로

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

가장 간단한 방법이다. 레디 큐에 들어온 순서대로 CPU를 할당하는 방법이다. 이 방법은 비선점이기 때문에 모든 프로세스는 레디 큐에 들어온 순서대로 완료된다. 

 

 

프로세스가 레디 큐에 들어온 순서대로 실행되기 때문에 같은 프로세스들이라도, 들어온 순서에 따라 average waiting time이 달라질 수 있다. 아래 두 가지 예시로 살펴보자. 레디 큐에는 세 개의 프로세스가 있다고 가정한다. 이해하기 쉽게 시간의 단위는 (초)로 설정하자.

 

프로세스 정보

 

예시1: P1-P2-P3 순서로 실행되는 경우 평균 대기 시간은 17초다

 

예시2: P2-P3-P1 순서로 실행되는 경우 평균 대기 시간은 3초

첫 번째 예시의 평균 대기 시간은 17초, 두 번째 예시의 평균 대기 시간은 3초로 14초나 차이가 나고 있다. 만약에 처음 CPU를 할당 받는 프로세스의 CPU burst time이 100초라면 어떻게 될까? 아마 평균 대기 시간은 더 증가할 것이다. 이렇게 앞에 있는 프로세스 때문에 뒤에 있는 프로세스들이 지연되는 효과를 Convoy Effect라고 한다. FCFS 스케줄링 방식은 Convoy Effect를 발생시킬 수 있다.

2. Shortest-Job-First(SJF) Scheduling

레디 큐에 있는 프로세스의 CPU Burst Time이 짧은 순서대로 CPU를 할당하는 방법이다. 혹시 FCFS의 예시에서 먼저 실행되는 프로세스의 CPU burst time이 짧을 수록 평균 대기 시간이 짧은 것을 기억하는가? SJF는 이를 그대로 반영시킨 알고리즘이다. SJF 역시 비선점이다. 만약 더 짧은 CPU burst time을 가지는 프로세스가 새롭게 레디 큐에 들어온다고 해도 일단 CPU를 할당 받은 프로세스가 끝나고 보겠다는 뜻이다. 예시를 하나 보자. 레디 큐에는 아래 네 개의 프로세스가 있다고 가정한다.

프로세스 정보

 

Burst Time이 짧은 순서대로 진행된다

 

SJF가 선점(Preemptive)인 경우 어떻게 될까? 아니, SJF가 선점이라 게 무엇을 뜻하는지 먼저 이해해보자. '선점'이란 OS가 프로세스로부터 CPU를 뺐을 수 있다는 것을 의미한다. 즉, SJF가 선점이라는 것은 새로운 프로세스가 들어왔을 때, 이 프로세스 또한 고려해준다는 것을 의미한다. 이제 만약 새로운 프로세스의 burst time이 CPU를 사용하는 프로세스의 burst time보다 짧다면 새로운 프로세스가 CPU를 차지할 수 있게 됐다. SJF의 선점 버전이 바로 Shortest-Remaining-Time-First Scheduling 방식이다. 

 

P1 실행 중에 CPU Burst Time이 더 짧은 새로운 프로세스 P2가 레디 큐에 들어왔을 때...

1. P1 그대로 실행한다(비선점) → SJF
2. P2 로 바꾼다(선점) → SRTF

3. Shortest-Remaining-Time-First(SRTF) Scheduling

이제 선점이기 때문에 상황이 바꼈다. 새로운 프로세스가 들어올 때마다 burst time이 가장 작은 프로세스가 CPU를 차지할 수 있게 됐다. 아래의 예시로 SRTF와 SJF를 비교해 보자.

 

프로세스 정보

 

SRTF(preemptive)

 

SJF(non-preemptive)

 

SRTF의 경우 프로세스의 Arrival Time마다 모든 프로세스의 남은 burst time을 비교해줘야 한다. 위 예시에서는 2, 4, 5초에 비교를 해주고 가장 적게 남은 프로세스에게 CPU를 할당해줬다. SJF의 경우 비선점이기 때문에 새로운 프로세스가 들어와도 무시하고 있다. 평균 대기 시간은 STRF가 1초 더 빠른 것을 확인할 수 있다.

 

여기까지 봤을 때 STRF 방식이 가장 최고의 효율을 내고 있다. 그러나 STRF 방식은 치명적인 단점이 하나 있다. 말이 안 되긴 하지만 CPU burst time이 무한인 어마무시한 프로세스가 레디 큐에 들어왔다고 가정해보자. 과연 이 친구는 STRF 방식에서 CPU를 차지할 수 있을까? 정답은 '절대 절대 그럴 일은 없다'이다. 

 

이렇게 CPU Burst Time이 너무 길어서 계속 대기만 하는 현상을 Starvation이라고 한다. 이를 해결할 수 있는 방법은 없을까? CPU Burst Time이 긴 프로세스들은 그만큼 대기 시간이 길어질 것이다. 그렇다면 오래 기다린 만큼 어떤 어드벤티지를 주면 해결할 수 있지 않을까? 이 방법이 Aging이다. 즉, Starvation은 Aging으로 해결할 수 있다. Aging은 오래 기다른 프로세스에게 우선권을 주는 방식으로 대기시간에 따른 가중치를 부여하는 방식이다. Aging 기법을 사용한 스케줄링 방식이 바로 Highest Response Next Scheduling 방식이다. 

4. Highest-Response-Ration(HRRN) Scheduling

HRRN은 우선순위 스케줄링 방식의 일종이다. 우선순위 방식은 가장 높은 우선순위를 가지는 프로세스에게 CPU를 할당하는 방식이다. 우선순위를 어떻게 설정하는지에 따라 성능이 크게 바뀌고 종류 또한 매우 다양하다. 참고로 FCFS와 SJF 또한 우선순위 방식으로 볼 수 있다. 

 

HRRN은 response ratio로 우선순위 값을 판단하며 이 값이 클수록 높은 우선순위를 가진다. Response Ratio 식은 아래와 같다. 

 

estimated run time = cpu burst time으로 이해하면 된다

 

위 식의 의미를 한번 생각해보자. 가장 우변을 보면 분자에는 기다린 시간, 분모에는 cpu burst time이 있다. 기다린 시간이 분자에 있기 때문에 오래 기다릴수록 response ratio 값은 커진다. 즉, 오래 기다릴수록 우선권을 가진다는 뜻이다. 만약 같은 시간을 기다렸다면? CPU burst time이 작은 프로세스가 우선권을 가질 것이다. 이 방법이 어떻게 starvation 문제를 해결할 수 있는지는 쉽게 이해할 수 있다. 아래의 예시를 보자.

 

P1 waiting time = 5
P1 cpu burst time = 5
P1 response ratio  = 5/5 = 1

P2 waiting time = 101
P2 cpu burst time = 100
P2 response ratio = 101/100 = 1.xx

 

위와 같이 두 개의 프로세스가 P1, P2가 있다. P2의 CPU burst time은 100초로 굉장히 길다. 만약 SJF 방식이라면 CPU를 할당 받기까지 굉장히 오랜 시간이 걸릴 수 있다. Starvation 상황이 발생한 것이다. 그런데 위와 같이 P2의 waiting time이 101인 경우 상황은 역전된다. P2의 Response ratio 값이 cpu burst time이 훨씬 작은 P1보다 크기 때문에 P2가 우선권을 가진다. 이렇게 기다린 시간에 가중치를 부여함으로써 starvation 문제를 해결할 수 있다.

5. Round-Robin(RR)

이 방법은 선점 방식으로, 특정 시간(time quantum)을 간격으로 프로세스에게 CPU를 할당하는 방법이다. 만약 time quantum이 무한이라면 FCFS 방법과 완전하게 동일하다. 

 

 

만약에 time quantum이 너무 짧으면 어떤 문제가 발생할까? Context Switch가 너무 많이 발생해서 엄청난 오버헤드가 발생할 것이다. 따라서 RR 방식은 time quantum의 설정이 굉장히 중요한 이슈다. 일반적으로 10ms ~ 100ms 사이로 설정된다고 한다. SJF와 비교했을 때 average turnaround time은  길지만, response time은 짧다. 그래서 응답성이 중요한 프로그램에 좋다고 한다. 아래는 time quantum을 2로 설정한 스케줄링 예시다. 

 

 

 

---

CPU Burst Time은 사실 모르는 값이다...

여기까지 프로세스 스케줄링에 대한 내용을 다뤄봤다. 그런데 한 가지 충격적인 사실을 알려주자면, 사실 CPU Burst Time은 실제값이 아니라 예측값이다. 프로세스 A가 레디 큐에 들어올 때, 이 프로세스를 CPU에 직접 돌려보지 않고는 실질적인 CPU Burst Time을 알 수 없다. 왜냐고 물어본다면... 내가 오히려 물어보고 싶다. 돌려보지 않고 어떻게 정확한 CPU Burst Time을 알 수 있나요...? 그래서 다음 글에서는 CPU Burst Time을 예측하는 방법에 대해 다뤄볼 생각이다.