개요

스케쥴링이란, CPU 자원을 계획에 따라 여러 프로세스에게 나누어주는 방법입니다. 여러가지 스케쥴링 항목에 대해 공부하기 전에, 왜 스케쥴러를 사용하는지에 대해 생각하면 더 편하게 이해할 수 있습니다.

앞서 공부한 프로세스의 상태 중, CPU를 할당받기 위해 Ready → Running 상태의 전이를 담당하는것이 스케쥴링입니다. 그래서 기본적으로 Ready Queue에 여러 프로세스가 대기중이고, 스케쥴링 정책은 이 큐에 있는 프로세스를 어떻게 실행할지에 대한 이야기라고 생각하면 됩니다.

운영체제는 목적에 따라 여러 종류가 있습니다. 대화형 시스템, 배치 시스템 등..

대화형 시스템에서는 CPU의 활용성이 조금 떨어지더라도 유저의 요청에 반응하는 시간이 빨라야하고,

대규모 데이터를 처리하는 배치 시스템에서는 응답시간보다는 처리량이 우선일 것입니다.

응답시간, 처리량같이 운영체제별로 스케쥴링의 목적이 있고, 이외에도 공평성, 무한대기 방지, 활용률 등 다양한 평가항목이 있어, 스케쥴링 알고리즘을 선택할 때 고려해야 합니다.

스케쥴링 성능평가 용어 정리

• Response Time, 응답시간 / T(response) - T(arrival) : 레디큐에 도착해 처음으로 스케쥴될때까지 걸린 시간
• Waiting Time, 대기시간 / T(sum of waiting) : 레디큐에 도착해 running이 되기까지 걸린 시간의 합
  • 응답시간은 Ready Queue도착에서 첫 스케쥴까지 걸린시간, 대기시간은 프로세스가 종료되기까지 Ready Queue에 있는 시간의 총 합을 의미합니다.
• Burst Time, 실행시간 / T(completion) - T(start) : CPU를 할당받아 실행한 시간
• Turnaround Time, 반환시간 / T(completion)- T(arrival) : 레디큐에 도착해 작업을 완료하기까지 걸린 시간

위와 같은 기준들로 “성능” 을 평가할 수 있으며, 여러 프로세스가 번갈아가며 실행하므로, 일반적으로는 반환시간 또는 대기시간의 평균을통해 스케쥴링의 적합성을 판단합니다.

또한, 공정성도 중요한 평가요소 중 하나입니다. 스케쥴링 방법을 공부하다보면 알겠지만, 일반적인 경우 처리량과 공정성은 등가교환 관계이기 때문에 주의해야 합니다.

스케쥴링 방법들

먼저 알고가야 할것. 선점형 vs 비선점형

유저 이벤트로 인한 프로세스 시작이나 I/O 종료 인터럽트로 인해 Ready Queue에 다양한 프로세스들이 들어옵니다.

이 때, 새로운 프로세스가 즉시 CPU 할당을 받아서(뺏어와서) 실행할 수 있는 스케쥴링 종류를 선점형(Preemitive), 그렇지 않고 해당 프로세스의 Burst Time이 끝나는것을 기다려하는 스케쥴링 종류를 비선점형(Non-Preemitive)라고 합니다

FCFS (또는 FIFO) 알고리즘

First Come First Service (First In First Out) 즉, 선착순/선입선출 알고리즘입니다. Ready Queue에 들어온 순서대로 CPU를 할당해줍니다. 비선점형 스케쥴링 알고리즘입니다

일상생활에서는 공평하게 처리하기 위해 자주 사용되는 알고리즘입니다. 매우 간단하고 얼핏보면 공평해보이지만, 아래의 경우를 확인해보면 비효율적인 알고리즘인걸 알 수 있습니다.

프로세스	A	B	C
실행시간	60	10	10
도착시간	0	0	0
반환시간	60	70	80

만약 A,B,C가 거의 동시에 도착해 A,B,C순으로 처리한다고 할 때, 평균 반환시간을 체크해보면

Average Turnaround Time : (60 + 70 + 80) /3 = 70 으로, 굉장히 비효율적입니다.

라면 하나를 사려고 계산대에 줄을 섰는데, 앞에서 엄청 많은 물건을 계산하고있는 상황을 생각해보면 편할겁니다.

이처럼 짧은 시간동안 자원을 사용하는 프로세스가 오랜 시간동안 할당을 기다려야 하는 현상을 Convoy Effect라고 합니다.

SJF 알고리즘 / Non Preemitive

Shortest Job First 즉, 짧은 작업을 우선해서 처리하는 알고리즘입니다.

비선점형으로 동작하는 경우부터 살펴보겠습니다.

FCFS에서는 실행시간이 짧은 프로세스가 앞서 실행되는 긴 프로세스의 실행을 기다려하는 Convoy Effect가 문제였습니다.

SJF에서는 레디큐에 있는 Job들 중, 짧은것을 우선적으로 실행합니다.

마트에서 줄이 짧은 사람을 먼저 계산하게 해줍니다!

프로세스	B	C	A
실행시간	10	10	60
도착시간	0	0	0
반환시간	10	20	80

앞선 FIFO의 예시입니다. A,B,C가 동시에 도착하면 B,C가 먼저 스케쥴되어 반환시간을 계산하면

Average Turnaround Time :(10+20+80) / 3 = 36.6 , 반환시간이 절반정도로 줄어든걸 확인할 수 있습니다.

SJF 문제점

비선점형이라는 것을 고려하면 아래와 같이 동작합니다.

B,C는 time:10에 도착했으므로 이미 실행중인 A를 종료시키지 못하고, time:60까지 기다립니다. 이 경우 반환시간은

프로세스	A	B	C
실행시간	60	10	10
도착시간	0	10	10
반환시간	60	60	70

Average TurnAround Time = (60+60+70)/3 = 63.3으로, 앞선 FSFS와 큰 차이가 없습니다.

SRTF(또는 SCTF) 알고리즘

SRTF: Shortes Remaining Time First (= SCTF: Shortest Time to Completion First)는 최소 잔여시간이 적은 프로세스를 선점형으로 실행하는 알고리즘입니다.

앞선 SJF와 비교해보면 B,C가 도착한 time: 10시점에 더 짧게 남은 잡을 계산해 CPU를 선점한다는걸 확인할 수 있습니다.

이 경우 반환시간을 계산해보겠습니다.

프로세스	A	B	C
실행시간	60	10	10
도착시간	0	10	10
반환시간	80	20	30

Average TurnAround Time = (80+20+30)/3 = 43.3으로, B,C가 늦게 도착한 경우에 평균 반환시간을 개선할 수 있었습니다.

SRTF 문제점

SRTF에도 공정성, 응답시간 측면에서 문제점이 있습니다.

만약 실행시간이 10인 프로세스가 레디 큐에 계속 들어온다면, 남은 실행시간이 20인 프로세스는 CPU를 할당받지 못하는 상태가 되고(Starvation), 응답시간이 계속 늘어납니다.

또한 운영체제는 Ready Queue에 있는 프로세스의 실행시간을 알지 못합니다.

Round Robin 알고리즘

Round Robin알고리즘은 일정 Time Quantum을 기점으로 Ready Queue에 있는 모든 프로세스들에게 공정하게 실행시간을 배분해주는 알고리즘을 말합니다.

문제점 해결

해당 방식으로 실행하면 SRTF에서 실행시간이 많이 남은 프로세스가 CPU를 계속 할당받지 못하는 공평성 문제가 해결되고, 응답시간이 대폭 개선됩니다.

특징

대화형 시스템에 적합합니다.

새로 Ready상태가 되거나 실행시간을 마친 Job은 Ready Queue의 맨 뒤로 갑니다.

• A가 실행되고 나서 C가 Ready상태가 되었다면, …. → A → C 순으로 실행됩니다.
• 반대로 C가 Ready Queue에 도착하고 A의 실행이 끝난다면, …→ C → A 순으로 실행됩니다.

새로운 문제점

평균 반환시간 관점으로 보았을 때, 최악의 알고리즘입니다.

또한 적절한 Time Quantum을 설정해야합니다. 잦은 Context Switch는 성능 저하를 불러옵니다.

정리

반환시간, 응답시간, 공평성은 등가교환 관계입니다.

SJF, SRTF는 반환시간이 개선되지만 응답시간, 공정성 측면에서는 비효율적이고

RR의 경우 응답시간과 공평성은 해결했지만 반환시간이 비효율적입니다.

뒤이어 배울 MLFQ등을 통해 각각의 장점을 절충하는 스케쥴러의 동작을 공부해보겠습니다.

Reference

OSTEP: Operating Systems: Three Easy Pieces

[HPC Lab. KOREATECH, OS Lecture CH.5 Lecture 5. Process Scheduling](**https://www.youtube.com/watch?v=jZuTw2tRT7w )**