CPU scheduling, 노예의 탄생

https://ko.wikipedia.org/wiki/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81_(%EC%BB%B4%ED%93%A8%ED%8C%85)

스케줄링 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

 

단일 프로세스 시스템(Single Processor System)에서 CPU는 한 개의 프로세스만 점유하고 있고 프로세스가 종료될 때까지 CPU의 점유를 내려놓지 않습니다.

그런데 CPU를 점유하고 있는 프로세스는 생각보다 열심히 일하지 않습니다. 예를 들어 키보드, 마우스의 입력을 기다리고 있거나 다른 프로세스에서 메시지를 줄 때까지 기다리는 등 wait에 사용되는 시간이 있습니다.

그런데 wait에 사용되는 시간을 모아보니 생각보다 많았던 것에 불만을 가진 여러 학자들이 CPU scheduling이라는 개념을 만들게 되었습니다.

 

---

 

Windows, Mac, Linux의 OS들이 하는 매우 중요한 작업 중에 하나인 CPU scheduling은 적용 여부, 방법에 따라 엄청난 성능 차이를 보여주게 됩니다.

https://www.researchgate.net/figure/Performance-comparisons-of-scheduling-algorithms-in-BLAST-tool_fig4_330075047

단일 프로세스 시스템으로 볼 수 있는 FCFS과 성능이 좋다고 평가받는 Round Robin만 비교해도 두배 정도의 성능차이를 보여주고 있습니다.

 

---

 

스케쥴링은 크게 두 종류로 나뉘고 각 종류에 따라 여러 스케쥴링 기법이 있습니다.

• 비 선점

1. FCFS (First Come First Served Scheduling)
2. SJF (Shortest Job First Scheduling)
3. HRRN (Highest Response Ratio Next Scheduling)

• 선점형

1. RR (Round Robin Scheduling)
2. SRTF (Shortest Remaining-Time First Scheduling)
3. 다단계 큐, MQ (Multilevel Queue Scheduling)
4. 다단계 피드백 큐, MFQ (Multilevel Feedback Queue Scheduling)
5. RM (Rate Monotonic Scheduling)
6. EDF (Earliest Deadline First Scheduling)

 

이중 몇 가지만 뽑아서 공부해보았습니다.

 

FCFS (First Come First Serve)

우리는 이미 FCFS의 동작 방식을 알고 있을 수도 있습니다. 자료구조의 FIFO이 스케쥴링으로 넘어오면 FCFS가 됩니다. 들어오는 순서대로 CPU를 점유한다. 자료구조에서 들어온 순서대로 나간다 와 같은 의미가 됩니다.

보통 성능평가를 위해 평균 대기시간을 계산하는데 간단한 예제를 첨부하겠습니다.

평균 wating time = (총 wating time) / process 갯 수 

 

https://www.w3schools.in/operating-system-tutorial/scheduling-algorithms/

process	Time	wating time
p1	3	0
p2	3	24
p3	24	27

p1은 최초에 들어온 process이므로 waiting time=0,

p2는 p1이 끝날 때까지 대기했으므로 wating time=24

p3는 p1, p2가 모두 끝날 때까지 대기했으므로 wating time=27

평균 wating time = (0 + 24 + 27) / 3 = 17 [ms]

 

근데 만약 순서가 p2, p3, p1으로 들어왔다면 어떻게 됐을까요??

process	Time	wating time
p2	3	0
p3	3	3
p1	24	6

p2은 최초에 들어온 process이므로 waiting time=0,

p3는 p2이 끝날 때까지 대기했으므로 wating time=3

p1는 p2, p3가 모두 끝날 때까지 대기했으므로 wating time=6

평균 wating time = (0 + 3 + 6) / 3 = 3 [ms]

 

들어온 순서를 바꾼 것 만으로 벌써 약 6배 정도 차이가 납니다. 벌써 성능이 극심한 차이를 보이고 있습니다.

학자들은 이걸 가만히 보고 있을 리가 없습니다. 그래서 나온 스케쥴링 방법이 SJF(shortest job first)입니다.

 

 

SJF (Shortest Job First)

SJF는 먼저 대기 중인 Process를 모두 받아서 CPU를 점유하는 시간이 가장 짧은 순서대로 실행하게 됩니다. process의 작업 시간을 오름차순으로 실행하게 되는 것입니다.

진행 과정이 일단 다 받아! 그리고 젤 빨리 끝나는 것부터 해! 가 됩니다.

process	Time	wating time
p4	3	0
p1	6	3
p3	7	9
p2	8	16

평균 wating time = (0 + 3 + 9 + 16) / 4 = 7 [ms]

이 알고리즘의 경우는 프로세스가 들어오는 시간이 다르지 않다면 언제나 평균 wating time은 같습니다.

 

 

RR (Round Robin Scheduling)

현대에 가장 많이 사용되고 있는 스케쥴링 기법입니다. 성능 대비 리소스가 가장 적게 든다고 전해지고 있습니다.

모든 프로세스가 동등한 위치에서 CPU를 할당받게 되며 지금까지는 프로세스가 CPU를 할당받으면 작업을 완료할 때까지 CPU를 점유하고 있었지만 이제는 일정 시간이 지나면 강제로 CPU 점유권을 빼앗습니다.

Round Robin 방식의 핵심은 모든 프로세스가 CPU에 대해 동일한 시간의 사용권을 부여받는 것입니다. 각 프로세스는 부여받은 시간 동안 작업을 진행하고 시간이 끝나면 강제로 뺏기게 됩니다.

 

Gantt chart of RR algorithm

process	Time	wating time
p1	4	6
p2	8	2+6+3+2 = 13
p3	3	4+6 = 10
p4	6	6+5+2 = 13

평균 wating time = (6 + 13 + 10 + 13) / 4 = 10.5 [ms]

RR 스케쥴링은 할당된 시간 (slice time)의 크기에 따라 성능이 크게 달라지게 됩니다. 너무 작게 하면 Context Switching에 너무 많은 시간을 사용하게 되고 너무 크게 설정하면 FCFS와 다를게 없어지게 됩니다.

 

 

다단계 큐, MQ (Multilevel Queue Scheduling)

프로세스를 그룹으로 나눠서 처리하는 스케쥴링 방식입니다. 각 그룹들마다 개별적인 스케쥴링 방식을 적용할 수 있으며 그룹마다 우선순위가 정해져 있어 우선순위가 높은 그룹부터 처리하게 됩니다.

예제로 가장 많이 활용되고 있는 그림입니다.

Multilevel Queue Scheduling

예를 들면 System Process는 RR, Interactive Process는 SJF 이런 방식으로 스케쥴링을 할 수 있다는 것 같습니다.