프로세스는 생성, 준비, 실행, 대기와 같은 여러 상태를 거치며 작업이 이루어진다. 여기서
CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 하며 CPU스케줄러가 하는 모든 작업을CPU 스케줄링이라 한다.
스케줄링 알고리즘은 크게 비선점형 알고리즘(non-preemptive)과 선점형 알고리즘(preemptive)로 나누어져 있다.
비선점형 알고리즘 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식. 자발적으로 대기 상태에 들어가기 전까지는 계속 실행된다.
- FCFS(First Come First Served)
- SJF(Short Job First)
- HRN(Highest Response Ratio Next)
선점형 알고리즘 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 뺏을 수 있는 스케줄링 방식.
- 라운드 로빈
- SRT(Shortest Remaining Time)
- 우선순위 스케줄링
- 다단계 큐 스케줄링(Multi Level Queue Scheduling)
- 다단계 피드백 큐 스케줄링(Multi Level Feedback Queue Scheduling)
비선점형 스케줄링은 문맥 교환에 의한 낭비가 발생하는 선점형 스케줄링에 비해 장점이 있지만, CPU 사용시간이 긴 프로세스가 작업이 끝나기 전까진 뒤에 스케줄된 프로세스가 작업할 수 없기에 시스템의 처리율이 떨어지고 과거의 일괄 작업 프로그래밍에서 사용되곤 했다. 요즘은 선점형 스케줄링 방식이 대부분 사용된다.
-
FCFS 스케줄링 동작방식 FCFS(First Come First Served) 알고리즘은 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식.
-
FCFS 스케줄링의 성능 성능은 프로세스들의 평균 대기 시간으로 평가를 대부분 진행한다. (대기 시간 : 프로세스가 Queue에 도착하고 작업을 수행을 시작하기까지 걸린 시간)
| 도착 순서 | 도착 시간 | 작업 시간 | 대기 시간 |
|---|---|---|---|
| P1 | 0 | 30 | 0 |
| P2 | 3 | 18 | 27 |
| P3 | 6 | 9 | 42 |
다음과 같은 프로세스 도착 순서와 작업 시간의 예가 있을 때, FCFS를 사용했을 때 도착 순서에 따라 작업이 진행된다. P1의 대기시간은 0, P2의 대기시간은 27(30-3), P3의 대기시간은 42(48-6)이고 평균 대기 시간은 (0+27+42) / 3 = 23이다.
- FCFS 스케줄링의 평가 단순하고 공평하지만, 처리 시간이 긴 프로세스가 프로세스를 차지하면 다른 프로세스는 하염없이 기다려야 하는 콘보이 효과(호위 효과)가 발생한다. 또한 입출력 작업을 요청하는 경우 CPU는 작업하지 않고 쉬는 시간이 많아져 효율이 떨어진다. 뒤에서 배울 시분할 시스템에서는 입출력을 요청한 프로세스를 대기 상태로 보내어 처리할 수 있다.
-
SJF 스케줄링 동작방식 SJF(Shortest Job First)스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 할당하는 비선점형 방식.
-
SJF 스케줄링의 성능 위의 작업그래프를 SJF 스케줄링을 이용한다면 P2와 P3가 순서가 바뀌어 작업이 진행된다. (P2가 일찍 도착했지만 P3의 작업 시간이 더 작기 때문에 SJF에 의하여 순서가 변경된다)
| 도착 순서 | 도착 시간 | 작업 시간 | 대기 시간 |
|---|---|---|---|
| P1 | 0 | 30 | 0 |
| P2 | 3 | 18 | 36 |
| P3 | 6 | 9 | 24 |
작업은 P1 -> P3 -> P2 순으로 진행되며 각각 대기 시간은 P1은 0, P3는 24(30-6), P2는 36(39-3)이고 평균 대기 시간은 (0+24+36)/3 =20이다.
- SJF 스케줄링의 평가 FCFS보다 빠르지만 다음과 같은 이유로 사용이 어렵다.
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기가 어렵다.
- 공평하지 못하다. 위의 상황처럼 P3보다 작업 시간이 짧은 프로세스들이 계속 들어오면 P3는 결국 작업 시간이 길다는 이유만으로 작업이 밀리게 되고
아사 현상이 발생하게 된다.
- HRN 스케줄링 동작방식
HRN(Highest Response Ratio Next)는 위에 언급한
아사 현상을 방지하기 위해 만들어진 비선점형 스케줄링으로, 최고 응답률 우선 스케줄링이라고도 한다. 우선 순위를 설정하여 스케줄링을 진행하며대기 시간을 포함하여 우선순위를 결정한다. 이를에이징이라고 한다.
HRN 스케줄링 우선순위 결정 방법 우선순위 = 대기시간 + CPU 사용시간 / CPU 사용시간
우선순위가 높을수록 먼저 배정된다.
- HRN 스케줄링 동작방식 HRN은 앞에 언급한 SJF 스케줄링과 비교하면 아사 현상을 완화한다. 하지만 여전히 공평성이 위배되기 때문에 많이 사용되지 않는다.
-
라운드로빈 스케줄링의 동작방식 라운드 로빈 스케줄링은 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐 맨 뒤로 가서 자기 차례를 기다리는 선점형 알고리즘 중 가장 단순하고 대표적인 방식이다.
-
라운드로빈 스케줄링의 성능 라운드 로빈 스케줄링 같은 선점형 방식에는 프로세스가 CPU를 일정 시간동안 사용한 후 다른 프로세스에게 넘겨주어야 하기 때문에 콘보이 효과가 줄어든다.
-
타임 슬라이스의 크기와 문맥 교환 타임 슬라이스는 적절히 설정해주어야 하는데 타임 슬라이스가 매우 작다면 여러 프로그램이 동시에 실행되는 것처럼 느껴질 것이고 콘보이 효과나 아사 현상이 줄어들 것이지만
문맥 교환에 발생하는오버헤드가 상대적으로 커지게 된다. 따라서 타임 슬라이스는 문맥 교환을 고려하여 너무 크지도 않게, 작지도 않게 설정하여야 한다.
-
SRT 스케줄링의 동작방식 SRT 스케줄링(Shortest Remaining Time)스케줄링은 SJF와 라운드로빈을 혼합한 방식이다. 기본적으로는 라운드로빈을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.
-
SRT 스케줄링의 평가 실제로 SRT 스케줄링을 SJF와 비교하면 평균 대기 시간이 짧다. 하지만 SRT 스케줄링은 좋은 알고리즘이 아니다. 현재 실행중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 적은 프로세스와 문맥교환을 해야하므로 SJF에는 없는 작업이 추가된다. 또한, 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 발생하여 잘 사용하지 않음.
- 우선순위 스케줄링의 동작방식
프로세스는 중요도에 따라
우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다. 우선순위 스케줄링은 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다. 추가적으로 우선순위 알고리즘은 선점형 또는 비선점형 방식으로 구현이 가능하다.
고정 우선순위 알고리즘 : 한 번 우선순위가 부여되면 바뀌지 않고 고정되는 알고리즘 변동 우선순위 알고리즘 : 일정 시간마다 우선순위가 변한다. 우선순위를 반영하는데 복잡하지만 효율적 운영이 가능한 알고리즘
- 우선순위 스케줄링의 평가
준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성 위배, 아사현상을 일으킨다. 또한 우선순위를 매번 바꾸면서 오버헤드가 발생하여 시스템의 효율성을 떨어트린다. 다만, 그럼에도 불구 시스템의 효율성이 아니라
프로세스의 중요도를 기반으로 결정되기 때문에커널 프로세스를일반 프로세스보다 먼저 실행하게 하는 등의 프로세스의 중요도에 따라 정해지는 스케줄링에 사용된다.
-
다단계 큐 스케줄링(Multi Level Queue Scheduling)은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다.
-
각각의 큐는 라운드 로빈 방식으로 운영되고 있고, 우선순위에 따라 다단계로 나누어져 있다. 우선순위는 고정형 우선순위를 사용하며, 상단의 큐의 프로세스가 모두 끝나야 하위 큐의 작업이 진행된다.
-
다단계 큐 스케줄링은 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전까지는 하위 큐 프로세스의 작업을 할 수 없다. 이를 보완하기 위해 제안된 것이
다단계 피드백 큐 스케줄링이다.
-
다단계 피드백 큐 스케줄링(Multi Level Feedback Queue Scheduling)은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다. 오늘날 운영체제가 일반적으로 사용하는 방식이다.
-
기본적으로 다단계 큐 스케줄링과 기본적인 형태가 같지만 라운드 로빈만 사용하는 다단계 큐 스케줄링과 다르게 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 원래의 큐가 아닌 우선순위가 하나 낮은 큐의 끝으로 들어간다.
-
또 다른 특징으로는 우선순위 큐 마다 타임 슬라이스의 크기가 다르다. 우선순위가 낮아질수록 큐의 타임 슬라이스가 커진다. 마지막 큐의 타임 슬라이스는 무한대로서, FCFS의 작업을 수행하게 된다.
-
다단계 피드백 큐 스케줄링은 변동 우선순위 알고리즘의 전형적인 예이다. 유닉스에서 타임 고정하지 않고 조정할 수 있게 하는 이유는 이 알고리즘 때문이다.
