운영체제가 어떤 프로세스를 프로세서에 할당할 것인가 정하는 프로세스 스케줄링(Process scheduling)에 대해 다루는 포스트이다.

FCFS, SJF, RR등 다양한 프로세스 스케줄링에 대해 소개한다.

Scheduling Criteria

운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치(Dispatch)라고 한다. (이때 프로세스 상태가 ready 에서 running으로 바뀐다.)

그리고 운영체제가 레디큐(Ready queue)에 있는 프로세스들 중에서 어떤 프로세스를 디스패치할 것인가 정하는 것이 프로세스 스케줄링(Process scheduling)이다.

스케줄링 알고리즘에는 대표적으로 FCFS, SJF, SRF, RR 네가지 방식이 있고, 알고리즘을 평가할 때는 수행시간(Burst time)과 CPU 사용량(CPU utilization), 단위 시간 당 끝마친 프로세스의 수(Throughput), 하나의 프로세스가 레디 큐에서 대기한 시간부터 작업을 마칠 때까지 걸리는 시간(Turnaround time), 프로세스가 레디큐에서 대기한 시간 (Waiting time), 프로세스가 처음으로 CPU를 할당받기까지 걸린 시간(Response time)을 기준으로 한다.

Burst time	Response time	Turnaround time	Waiting time
수행시간	프로세스가 첫 Output을 내는데 걸리는 시간	하나의 프로세스가 시작에서 종료까지 걸리는 시간	하나의 프로세스가 Ready Queue에서 기다린 총 시간

선점(Preemptive) 방식과 비선점 (Non-Preemptive) 방식으로 나뉜다.

선점 스케줄링은 운영체제가 강제로 프로세스의 사용권을 통제하는 방식이고, 비선점 스케줄링은 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식이다.

즉, 선점 스케줄링 방식에는 CPU에 프로세스가 할당 되어 있을 때도 운영체제가 개입해 다른 프로세스에게 CPU를 할당할 수 있다.

구분	선점(Preemptive) 스케줄링	비선점(Non-preemptive) 스케줄링
개념	– 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지 시키고 자신이 CPU 점유	– 한 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유불가
특징	– 하드웨어(Timer) 필요 공유 데이터에 대한 프로세스 동기화 필요	– 특수 하드웨어(Timer) 없음 – 종료 시까지 계속 CPU 점유
장점	– 비교적 빠른 응답 – 대화식 시분할 시스템에 적합	– 응답시간 예상이 용이 – 모든 프로세스에 대한 요구를 공정하게 처리
단점	– 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래	– 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기
알고리즘	Round Robin, SRT, 다단계 큐, 다단계 피드백 큐	우선순위 스케줄링, 기한부 스케줄링, FCFS, SJF, HRN
활용	– 실시간 응답 환경, Deadline 응답 환경	– 처리시간 편차가 적은 특정 프로세스 환경

FCFS (First-Come, First-Served)

먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식이다.
Queue의 FIFO(First-in First-out)와 동일하다.
구현이 쉬워서 간단한 시스템에 자주 사용된다.
프로세스 처리 순서에 따라 성능이 크게 달라질 수 있다.
수행 시간이 큰 프로세스가 먼저 들어오면 그 뒤에 들어온 프로세스들이 불필요하게 오랜 시간을 기다리게 되는 콘보이 효과(convoy effect)가 발생한다.

먼저 온 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

Process	Burst time	Response time	Turnaround time	Waiting time
P1	9	0	9	0
P2	1	9	10	9
P3	1	10	11	10

                +----+----+----+----+----+----+----+----+----+----+----+
                |                     P1                     | P2 | P3 |
                +----+----+----+----+----+----+----+----+----+----+----+
                0                                            9    10   11

Average waiting time = (0 + 9 + 10) / 3 = 6.33

P1, P2, P3 프로세스가 들어온 순서대로 할당됐다.

P2, P3는 수행시간이 짧음에도 P1이 끝날 때까지 기다리게 되어 평균 대기 시간이 늘어났다.

SJF (Shortest Job First)

프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
FCFS에서 발생하는 콘보이 효과를 해결할 수 있다.
최적 알고리즘이지만 수행시간을 정확히 알 수 없다.(앞서 처리한 프로세스들의 기록을 보고 추측한다.)
버스트 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
버스트 시간이 짧은 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

Process	Burst time	Response time	Turnaround time	Waiting time
P1	6	3	9	3
P2	8	16	24	16
P3	7	9	16	9
P4	3	0	3	0

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
            |      P4      |              P1             |                P3                |                   P2                  |
            +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
            0              3                             9                                  16                                      24

Average waiting time = (3 + 16 + 9 + 0) / 4 = 7

프로세스의 수행 시간을 정확히 예측했다는 가정하에, 수행 시간이 짧은 순서대로 프로세서에 할당됐다.

SRF (Shortest Remaining Time First)

프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
SJF에서 발생하는 기아 문제를 해결할 수 있다.
수행 중 다른 프로세스보다 남은 수앻 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.

Process	Arrival time	Burst time	Response time	Turnaround time	Waiting time
P1	0	8	0	17	9
P2	1	4	1	5	0
P3	2	9	17	24	15
P4	3	5	5	7	2

                +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
                | P1 |         P2        |           P4           |                P1                |                     P3                     |
                +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
                0    1                   5                        10                                 17                                           26

Average waiting time = (9 + 0 + 15 + 2) / 4 = 26

P1이 수행되던 중, 1ms에 P2가 들어왔다.

이때 P1의 남은 수행시간은 7ms이고, P2의 남은 수행 시간은 4ms이기 때문에 운영체제가 개입해 P1의 수행을 중단하고 P2를 프로세서에 할당한다.

P2가 프로세서에 할당된 사이, 2ms에 P3가 들어왔으나 P2의 남은 수행시간은 3ms이고, P3의 남은 수행시간은 9ms이기 때문에 프로세서는 P2를 계속 수행한다.

이어서 3ms일 때 P4가 들어왔지만 P2의 남은 수행 시간은 2ms이고, P4의 남은 수행 시간은 5ms이기 때문에 여전히 P2가 수행된다.

이후에도 같은 방식으로 프로세스의 작업이 끝나거나 새로운 프로세스가 들어올 때마다 남은 수행시간을 비교해 자리를 바꿔준다.

RR (Round Robin)

일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.
시스템의 time-sharing과 같은 방식이다.
반응성이 좋다.
주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.
시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

Process	Burst time	Response time	Turnaround time	Waiting time
P1	15	0	19	4
P2	2	3	5	3
P3	2	5	7	5

Time quantum = 3ms

            +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
            |      P1      |    P2   |    P3   |      P1      |      P1      |      P1      |      P1      |
            +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
            0              3         5         7              10             13             16             19

Average waiting time = (4 + 3 + 5) / 3 = 4

모든 프로세스들이 동일하게 3ms씩 프로세스에 할당된다.

P2와 P3의 경우 수행 시간이 2ms이기 때문에 할당된 3ms를 모두 사용하지 않았다.

Priority Scheduling

특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.
프로세스 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다.
SRF의 경우 남은 수행시간을 기준으로 우선순위를 부여한다고 할 수 있다.
다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다.

Process	Priority	Burst time	Response time	Turnaround time	Waiting time
P1	3	5	4	9	4
P2	1	1	0	1	0
P3	4	2	9	11	9
P4	5	1	11	12	11
P5	2	3	1	4	1

                +----+----+----+----+----+----+----+----+----+----+----+----+
                | P2 |      P5      |           P1           |    P3   | P4 |
                +----+----+----+----+----+----+----+----+----+----+----+----+
                0    1              4                        9         11   12

Average waiting time = (4 + 0 + 9 + 11 + 1) / 5 = 5

우선순위에 따라 프로세스가 할당되었다.

사용자가 자주 사용하는 프로세스의 우선순위를 높게 부여하는 식으로 기준을 만들 수 있다.

다만 특정 프로세스의 우선 순위가 계속 밀려 기아가 발생할 수 있으므로, 시간이 지날 때마다 프로세스의 나이를 증가시켜 오래 대기한 프로세스의 우선순위를 높여주는 조치가 필요하다.

제가 올린 글에서 잘못된 부분이 있으면 제 메일로 연락주세요!

Reference : https://parksb.github.io/article/9.html, http://blog.skby.net/cpu-비선점-스케줄링-기법/, Operation System Concept

이승수의 저작물인 이 저작물은(는) 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제 라이선스에 따라 이용할 수 있습니다.

seungsle

CPU Scheduling