08. CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

프로세스 스케줄러는 프로세스 스케줄링 알고리즘에 따라 프로세서를 할당하고 작업을 완료한다.

스케줄링 알고리즘의 선택기준

CPU 사용률

• 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법

• 가장 이상적인 수치는 100%이지만 실제로는 여러가지 이유로 90%에도 못 미침

처리량

• 단위 시간당 작업을 마친 프로세스의 수
• 이 수치가 클수록 좋은 알고리즘임

대기시간

• 프로세스가 생성된 후 실행되기 전까지 대기하는 시간

응답시간

• 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지의 시간

실행시간

• 프로세스 작업이 시작된후 종료되기 까지의 시간

반환시간

• 대기시간을 포함하여 실행이 종료될 때까지의 시간

평균 대기시간

• 모든 프로세스의 대기시간을 합한 뒤 프로세스의 수로 나눈 값

FCFS 스케줄링

선입 선처리(FCFS, First Come First Served) 스케줄링은 비선점 기법으로 프로세서 스케줄링 알고리즘 중 가장 간단하다. 프로세서를 요구하는 순서로 프로세서를 할당하는 방법으로 선입선출(FIFO, First In First Out) 큐로 구현한다. 일괄 처리 시스템에서는 매우 효율적이나 대화식 시스템에서는 사용자가 빠른 응답을 요구하기 때문에 적합하지 않다

프로세스가 준비 큐에 들어오면, 즉 새로운 작업이 시스템에 들어오면 프로세스의 프로세스 제어블록(PCB)은 준비 큐의 마지막에 연결된다. 차례가 되면 준비 큐의 앞부분에 잇는 프로세스는 프로세서를 할당 받고 준비 큐에서 삭제된다. 선입 선처리 성능은 좋지 않은 경우가 많으며 평균 대기시간이 긴 경우도 가끔 있다.

동작 방식

• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
• 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있음
• 큐가 하나로 모든 프로세스의 우선순위는 동일함

성능

프로세스 도착 순서와 작업의 시간

도착 순서	도착 시간	작업 시간
P1	0	30
P2	3	18
P3	6	9

FCFS 스케줄링의 평균 대기시간

※ 평균 대시 시간은 $(0+27+41)\div3=23$

평가

• 처리량이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있는데 이를 콘보이 효과(Convory effect) 또는 호위 효과라고 함
• 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어짐

SJF 스케줄링

최소작업 우선(SJF, Shortest Job First) 스케줄링은 프로세서 버스트 시간이 짧은 작업에 프로세스를 할당하는 기법이다. 이때 두 프로세스가 다음 순서로 동일한 프로세서 버스트를 가진다면 선입 선처리 스케줄링을 적용한다.

동작 방식

• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
• 콘보이 효과를 완화하여 시스템의 효율성을 높임

성능

SJF 스케줄링의 평균 대기시간

※ 평균 대기시간은 $(0+24+36)\div3=20$

평가

• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
• 작업시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐 >> 아사(starvation) 현상이 발생할수 있음

에이징

• 아사현상의 완화방법
• 프로세스가 양보할 수 있는 상한선을 정하는 방식
• 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정하는 것

HRN 스케줄링

최고 응답률 우선 (HRN, Highest Response-Rate Next) 스케줄링은SJF 스케줄링 알고리즘의 약점이었던 긴 작업과 짧은 작업간의 지나친 불평등을 어느정도 보완한 알고리즘이다.

동작방식

• SJF 스케줄링에서 발생할 수 있는 아사현상을 해결하기 위해 만들어진 비선점형 알고리즘
• 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식
• 프로세스의 우선순위를 결정하는 기준

$$
우선순위= \frac{대기한\ 시간+CPU\ 사용\ 시간}{CPU\ 사용\ 시간}
$$

CPU 사용 시간이 분모에 있으므로 CPU 사용 시간이 짧은 작업이 우선순위가 높다. 그리고 대기한 시간이 분자에 있으므로 CPU 사용 시간이 긴 작업에도 대기한 시간이 큰경우에는 우선순위가 높아진다.

성능

HRN 스케줄링의 평균 대기시간

※ 평균 대기시간은 $(0+24+36)\div3=20$

평가

• 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사현상을 완화
• 대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당받을 확률을 높임
• 여전이 공평성이 위배되어 많이 사용되지 않음

라운드 로빈 스케줄링

순환 할당(Round Robin) 스케줄링은 시분할 시스템을 위해 특별히 설계되었다. 이 순환 알고리즘은 규정 시간량(Time Quantum) 또는 시간 할당량(Time Slice)라고 하는 작은 단위의 사간을 정의한다. 준비 큐는 순환 큐로 설계하여 프로세서 스케줄러가 준비 큐를 돌아가면서 한 번에 한 프로세스에 정의된 규정 시간량 만큼의 프로세서를 제공한다.

동작방식

• 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
• 선점형 알고리즘 중 가장 단순하고 대표적인 방식
• 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행

성능

라운드 로빈 스케줄링의 평균 대기 시간

※ 총 대기 시간은 $0(P_1)+7(P_2)+14(P_3)+19(P_1)+19(P_2)+8(P_1)=67$

※ 평균 대기 시간은 $67\div3=22.33$

타임 슬라이스의 크기와 문맥교환

• 라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함
• 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요

타임 슬라이스가 큰 경우

• 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여 FCFS 스케줄링과 다를게 없음

타임 슬라이스가 작은 경우

• 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생

※ 유닉스 운영체제에서는 타임 슬라이스가 대략 100 ms

SRT 우선 스케줄링

최소 잔여 시간 우선 (SRT, Shortest Remaining Time) 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합반 방식이다. 쉽게 말해 SJF의 선점형 버전이라 할 수 있다. SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당 받을 프로세스를 선택할 때 남야 있는 작업 시간이 가장 적은 프로세스를 선택한다. 라운드 로빈 스케줄링이 큐에 있는 순서대로 CPU를 할당한다면, SRT 스케줄링은 남은 시간이 적은 프로세스에 CPU를 먼저 할당한다.

동작방식

• 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택 할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택

성능

SRT 스케줄링의 평균 대기시간

※ 총 대기 시간은 $0(P_1)+4(P_3)+16(P_2)+27(P_1)=47$

※ 평균 대기 시간은 $47\div3=15.66$

평가

• 현재 실행 중인 프로세와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가됨
• 운영체제가 프로세의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않음

우선순위 스케줄링

프로세스는 중요도에 따라 우선순위(Priority)를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다. 우선순위 스케줄링은 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다.

동작 방식 예

도착 순서	도착 시간	작업 시간	우선순위
P1	0	30	3
P2	3	18	2
P3	6	9	1

FCFS 스케줄링에 우선순위를 적용한 결과

우선순위 적용

• 우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있음

SJF 스케줄링

• 작업시간이 짧은 프로세스에 높은 우선순위를 부여

HRN 스케줄링

• 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여

SRT 스케줄링

• 남은 시간이 짧은 프로세스에 높은 우선순위를 부여

고정우선순위 vs 변동우선순위

고정우선순위

• 한 번 우선순위를 부여받으면 종료될 때 까지 우선순위가 고정
• 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어짐

변동우선순위

• 일정 시간마다 우선순위가 변하며 일정 시간마다 우선순위를 새로 계산하고 이를 반영
• 복잡하지만 시스템의 상황을 반영하여 효율적인 운영 가능.

우선순위 스케줄링의 평가

• 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으김
• 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성을 떨어뜨림

다단계 큐 스케줄링

다단계 큐(Multi-Level Queue) 스케줄링은 각 작업들을 서로 다른 묶음으로 분류할 수있을 때 사용하는 알고리즘이다. 준비상채의 큐를 종류별로 여러 단계로 분할하고 작업을 기억장치의 크기나 프로세스의 형태에 따라 어느 한 큐에 지정한다. 각 큐는 자신만의 독자적인 스케줄링 알고리즘을 갖고 있다. 또한 각 큐는 순서대로 절대적인 우선순위를 갖는다.

---

• 각 작업들을 서로 다른 묶음으로 분류할 수 있을 때 사용
• 준비 상태 큐를 종류별로 여러단계로 분할, 그리고 작업을 메모리의 크기나 프로세스의 형태에 따라 특정 큐에 지정, 각 큐는 자신만의 독자적인 스케줄링 알고리즘을 갖는다.

동작방식

• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
• 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입
• 우선순위는 고정형 우선순위를 사용
• 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨

장점

• 응답이 빠르다

단점

• 여러 준비 큐와 스케줄링 알고리즘 때문에 추가 오버헤드가 발생한다.
• 우선순위가 낮은 큐의 프로세스는 무한정 대기하는 기아상태가 발생할 수 있다.

다단계 피드백 큐 스케줄링

다단계 큐 스케줄링은 작업이 시스템에 들어가면 한 큐에서만 고정되어 실행된다. 즉, 작업은 다른 큐로 옮겨지지 않는다. 이러한 방식은 스케줄링 부담이 적다는 장점이 있으나 융통성이 떨어진다는 단점도 있다.

다단계 피드백 큐(Multi-Level Feedback Queue) 스케줄링은 작업이 큐 사이를 이동할 수 있다. 이 기법은 프로세서 버스트의 특성에 따라 분리하여 구분한다.

그러나 높은 우선순위의 큐가 완전히 비어야 낮은 우선순위의 준비 큐에 있는 작업이 실행될 수 있기 때문에 낮은 우선순위의 큐에 입력된 작업이 무한정 기다리게 되는 하사현상에 빠질 수 있다는 문제점이 있다. 물론 특정 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 이동시키거나, 프로세서 점유 시간이 긴 작업을 우선순위가 낮은 큐로 이동시켜서 기아상태를예방하는 에이징 기법을 활용한다.

---

프로세서 버스트의 특성에 따라 분리/구분하며, 작업이 큐 사이를 이동 가능함

• 어떤 작업이 요구하는 프로세서 시간이 너무 길면 작업을 낮은 단계 큐로 옮김
• 입출력 중심 작업과 전면작업(대화형 작업)을 높은 우선순위 큐에 놓고 프로세서 중심 프로세스는 낮은 우선순위 큐에 놓음.

알고리즘 구현시 고려사항

• 큐의 수
• 각 큐에 대한 스케줄링 알고리즘
• 작업을 좀 더 높은 우선순위의 큐로 격상시키는 시기를 결정하는 방법
• 작업을 좀 더 낮은 우선순위의 큐로 격하시키는 시기를 결정하는 방법
• 프로세스들이 어느 큐에 들어갈 것인가를 결정하는 방법
• 프로세스가 서비스를 받는 시기를 결정하는 방법

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALLㅈ