※ 이 내용은 ‘쉽게 배우는 운영체제’ 책 내용을 바탕으로 작성되었습니다.
스케줄링 개요
CPU 스케줄링은 어떤 작업에 CPU를 배정할지 결정하는 것을 말합니다. 그리고 이는 CPU 스케줄러가 처리합니다.
스케줄링
여러 프로세스 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일
스케줄링 단계
- 고수준 스케줄링(장기 스케줄링, 작업 스케줄링)
- 중간 수준 스케줄링
- 저수준 스케줄링(단기 스케줄링)
고수준 스케줄링
전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정합니다. 일단 작업이 시작되면 시스템 자원을 사용하기 때문에 기존 작업에 영향을 미칩니다. 작업 요청이 오면 스케줄러가 시스템의 상황을 고려하여 작업을 승인할지, 거부할지 결정합니다. 고수준 스케줄링에 따라 시스템에서 동시에 실행 가능한 총 프로세스가 정해집니다. 고수준 스케줄링은 메인프레임과 같은 큰 시스템에서 규모가 큰 일괄 작업을 처리할 때 사용됩니다.
저수준 스케줄링
고수준 스케줄링과 반대로 가장 작은 단위의 스케줄링을 말합니다. 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정합니다. 앞서 배운 프로세스의 상태 변경이 저수준 스케줄링에 해당합니다. 저수준 스케줄링은 아주 짧은 시간 동안 일어나기 때문에 단기 스케줄링이라고도 부릅니다.
중간 수준 스케줄링
중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막습니다. 즉 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스가 원만하게 동작하도록 지원합니다. 이는 프로세스 상태 중 보류 상태에 해당하며, 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할을 합니다.
스케줄링의 목적
- 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안 된다.
- 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 줘야 한다.
- 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
- 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
- 반응 시간 보장: 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
- 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.
스케줄링 시 고려사항
선점형 스케줄링과 비선점형 스케줄링
- 선점형 스케줄링(preemptive scheduling): 어떤 프로세스가 CPU를 할당받아 실행 중이어도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
- 비선점형 스케줄링(non-preemptive scheduling): 어떤 프로세스가 CPU를 할당받아 점유 중이라면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
선점형 스케줄링은 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합합니다. 단점은 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생깁니다. 대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용합니다.
비선점형 스케줄링은 어떤 프로세스가 실행 상태에 들어가 CPU를 사용하면 그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계속 실행됩니다. 때문에 선점형 스케줄링에 비해 작업량이 적고 문맥 교환에 의한 낭비도 적습니다. 하지만 CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 효율이 떨어집니다. 정리하면 다음과 같습니다.
| 구분 | 선점형 | 비선점형 |
|---|---|---|
| 작업 방식 | 실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있다. | 실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능하다. |
| 장점 | 프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합하다. | CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다 |
| 단점 | 문맥 교환의 오버헤드가 많다. | 기다리는 프로세스가 많아 처리율이 떨어진다. |
| 사용 | 시분할 방식 스케줄러 | 일괄 작업 방식 스케줄러 |
| 중요도 | 높음 | 낮음 |
프로세스 우선순위
프로세스는 크게 커널 프로세스와 일반 프로세스로 구분됩니다. CPU 스케줄러는 각 프로세스에 우선순위를 부여하는데 커널 프로세스의 우선순위가 일반 프로세스보다 높습니다. 만약 같은 우선순위로 처리한다면 커널과 관련된 중요한 프로세스의 작업이 제대로 이뤄지지 않겠죠.
우선순위가 높다는 것은 더 빨리 자주 실행된다는 것을 의미합니다. 준비 상태의 커널 프로세스와 일반 프로세스가 있다고 가정하면 커널 프로세스의 우선순위가 높기 때문에 우선적으로 실행됩니다. 또한 같은 커널 프로세스라 하더라도 우선순위의 높고 낮음이 존재합니다. 이는 일반 프로세스도 마찬가지입니다.
결론적으로 시스템에는 다양한 우선순위의 프로세스가 공존하며, 우선순위가 높은 프로세스가 CPU를 먼저, 더 자주, 오래 차지합니다.
CPU 집중 프로세스와 입출력 집중 프로세스
- 버스트: 특정 기준에 따라 한 단위로서 취급되는 연속된 신호나 데이터의 모임
- CPU 버스트(CPU burst): CPU를 할당받아 실행하는 중일 때
- 입출력 버스트(I/O burst): 입출력 작업을 할 동안 기다릴 때
- CPU 집중 프로세스: 수학 연산과 같이 CPU를 많이 사용하는 프로세스, 즉 CPU 버스트가 많은 프로세스
- 입출력 집중 프로세스: 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스, 즉 입출력 버스트가 많은 프로세스
다중 큐
준비 상태의 다중 큐
준비 큐에는 각 프로세스가 자신의 우선순위에 해당하는 큐의 tail에 삽입됩니다. 그리고 우선순위가 가장 높은 큐에서 head에 있는 프로세스가 다음에 CPU에 할당됩니다. 준비 큐를 몇 개로 나눌지, 여러 개의 준비 큐에 있는 프로세스 중 어떤 프로세스를 CPU에 할당할지는 스케줄링 알고리즘에 따라 달라집니다.
프로세스의 우선순위를 배정하는 방식에는 고정 우선순위 방식과 변동 우선순위 방식이 있습니다.
- 고정 우선순위 방식: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 종료될 때까지 우선순위가 변하지 않는 방식입니다. 구현은 쉬우나 유동적인 시스템 상황에 맞추기 어렵습니다.
- 변동 우선순위 방식: 프로세스 생성시 부여받은 우선순위가 시스템 상황에 따라 변하는 방식입니다. 구현은 어렵지만 시스템의 효율성이 높아집니다.
대기 상태의 다중 큐
같은 입출력을 요구한 프로세스끼리 구성된 큐입니다. 예를 들어 하드 디스크 입출력, CD-ROM 입출력 등에 각각의 큐가 존재하는 것입니다.
준비 상태의 다중 큐와 대기 상태의 다중 큐 차이점
- 준비 큐 - 한 번에 하나의 프로세스를 꺼내어 CPU에 할당합니다.
- 대기 큐 - 여러 개의 PCB를 동시에 준비 상태로 옮깁니다. 시스템에는 여러 입출력장치가 있기 때문에 입출력이 동시에 끝난 경우 여러 개의 인터럽트가 한 번에 처리됩니다. 이렇게 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료구조를 사용하죠. 인터럽트 벡터에는 동시에 완료된 입출력 정보와 처리 방법이 담겨 있고, 이 정보에 따라 완료된 PCB가 준비 상태로 이동합니다.
스케줄링 알고리즘
크게 비선점형 알고리즘과 선점형 알고리즘으로 나뉩니다. 비선점형 알고리즘은 효율 문제로 현재는 거의 사용되지 않습니다. 종류를 간단하게 정리하면 다음과 같습니다.
| 구분 | 종류 |
|---|---|
| 비선점형 알고리즘 | FCFS, SJF, HRN |
| 선점형 알고리즘 | Round Robin, SRT, 다단계 큐, 다단계 피드백 큐 |
| 둘 다 가능 | 우선순위 스케줄링 |
스케줄링 알고리즘의 평가 기준
- CPU 사용률: 전체 시스템 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
- 처리량: 단위 시간당 작업을 마친 프로세스의 수. 클수록 좋은 알고리즘
- 대기 시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간. 짧을수록 좋음
- 응답 시간: 프로세스 시작 후 첫 번째 출력 혹은 반응이 나올 때까지 걸리는 시간. 짧을수록 좋음
- 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸린 시간. 대기시간 + 실행 시간
스케줄링 알고리즘을 비교할 땐 주로 평균 대기 시간을 봅니다. 이는 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값입니다. 앞으로 성능 평가를 위해 사용할 프로세스의 도착 순서와 작업 시간의 예입니다(단위 = 밀리초).
| 도착 순서 | 도착 시간 | 작업 시간 |
|---|---|---|
| P1 | 0 | 30 |
| 3 | 18 | |
| 6 | 9 |
FCFS 스케줄링
개요
준비 큐에 도착한 순서대로 CPU에 할당하는 비선점형 방식의 알고리즘입니다. 선입선출 스케줄링이라고도 합니다. 비선점형 방식이기 때문에 한 번 실행한 프로세스가 종료될 때까지 다른 작업은 하지 못합니다. 또한 큐가 하나이기 때문에 모든 프로세스의 우선순위는 동일합니다.
성능 평가
- P1은 도착하자마자 실행되므로 대기 시간은 0, 작업 시간은 30입니다.
- P2는 3밀리초 후에 도착했고, 작업 중인 P1을 기다리므로 대기 시간은 27입니다.
- P3는 6밀리초 후에 도착했고, P1 종료 후 P2의 종료까지 기다리므로 대기 시간은 30 + 18 - 6 = 42입니다.
즉 FCFS의 평균 대기 시간은 (0 + 27 + 42)/3 -> 23밀리초입니다.
FCFS 스케줄링은 단순하고 공평하지만, 처리 시간이 긴 프로세스가 CPU를 차지하면 기다리는 프로세스들의 처리가 늦어져 효율성이 떨어진다는 단점이 있습니다. 이를 콘보이 효과(convey effect) 또는 호위 효과라고 합니다.
SJF 스케줄링
개요
준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU에 할당하는 비선점형 방식의 알고리즘입니다. 최단 작업 우선 스케줄링이라고도 합니다.
성능 평가
- P1은 도착하자마자 실행되므로 대기 시간은 0, 작업 시간은 30입니다.
- P2는 3밀리초 후에 도착했고, P3는 6밀리초 후에 도착했습니다. 이때 P1의 작업은 끝나지 않았고 P3의 작업 시간이 P2보다 짧기 때문에 P1이 종료되면 P3가 실행됩니다. 즉 P3의 대기 시간은 24입니다.
- P2는 P1과 P3의 작업 종료 후 실행됩니다. 대기 시간은 30 + 9 - 3 = 36이 됩니다.
즉 SJF의 평균 대기 시간은 (0 + 24 + 36)/3 -> 20밀리초 입니다.
SJF 스케줄링은 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아집니다. 하지만 다음과 같은 이유로 사용하기가 힘듭니다.
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵습니다.현대의 프로세스는 사용자와의 상호작용이 빈번하게 발생하기 때문에 프로그램의 종료 시간을 파악하기 어렵습니다.
- 공평하지 못합니다.위와 같이 P2는 P3와 같은 프로세스가 들어오면 계속 기다리는 상태가 됩니다. 이를 아사 현상 또는 무한 봉쇄 현상이라고 합니다. 작업 시간이 길다는 이유만으로 계속 뒤로 밀린다면 공평성이 현저히 떨어집니다.
두 문제를 해결할 방법은 있습니다.
문제 1은 프로세스 자신이 운영체제에 작업 시간을 직접 알려줌으로서 해결할 수 있습니다. 하지만 프로세스가 자신의 작업 시간을 정확히 알기 어려울 뿐만 아니라, 일부 악의적인 프로세스가 작업 시간을 조작한다면 시스템의 효율성이 낮아질 것입니다.
문제 2는 에이징을 통해 완화할 수 있습니다. 프로세스가 몇 번 이상까지만 밀리도록 상한선을 정하는 것입니다. 상한선에 도달하면 그 프로세스는 다음 번에는 밀리지 않고 실행되게 합니다. 하지만 이 또한 에이지 값을 정하는 기준이 문제가 되어 한계가 있습니다. 이러한 이유로 SJF 스케줄링 또한 잘 사용되지 않습니다.
HRN 스케줄링
개요
SJF 스케줄링의 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘입니다. 최고 응답률 우선 스케줄링이라고도 합니다. HRN 스케줄링은 대기 시간과 작업 시간을 고려하여 스케줄링하여 우선순위를 결정합니다.
우선순위 = (대기 시간 + 작업 시간) / 작업 시간
성능 평가
- P1은 도착하자마자 실행되므로 대기 시간은 0, 작업 시간은 30입니다.
- P2는 3밀리초 후 도착하고, P3는 6밀리초후 도착했습니다. P1이 작업 중이므로 우선순위를 결정합니다. P2의 대기 시간은 27밀리초이고, 작업 시간은 18밀리초입니다. 이를 통해 우선순위를 계산하면 2.5가 됩니다. P3의 대기 시간은 24밀리초이고, 작업 시간은 9밀리초입니다. 우선순위는 약 3.67이 됩니다. HRN 스케줄링에서는 숫자가 클수록 우선순위가 높으므로 P3가 P1 종료 시 실행됩니다.
- P2는 P3 종료시 실행됩니다.
HRN의 평균 대기 시간은 (0 + 24 + 36)/3 = 20밀리초 입니다.
HRN 스케줄링은 SJF에 비하여 아사 현상을 완화함으로써 모든 프로세스가 CPU를 할당받을 확률을 높입니다. 하지만 여전히 공평성이 많이 위배되어 많이 사용되지 않습니다.
라운드 로빈 스케줄링
개요
한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식입니다. 선점형 알고리즘 중 가장 단순하고 대표적인 방식으로, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행됩니다. 이 방식은 우선순위가 적용되지 않는 가장 단순한 선점형 스케줄링 방식입니다.
성능 평가
타임 슬라이스가 10밀리초인 시스템이라고 가정하겠습니다.
- P1은 도착하자마자 실행되므로 대기 시간은 0, 작업 시간은 30이지만 타임 슬라이스의 제한때문에 10 밀리초 작업 후 맨 뒤로 밀려납니다.
- P2는 3밀리초 후 도착했으므로 대기 시간은 7, 작업 시간은 18밀리초이지만 타임 슬라이스의 제한때문에 10밀리초 작업 후 맨 뒤로 밀려납니다.
- P3는 6밀리초 후 도착했고, P2의 작업 시간까지 기다렸으므로 대기 시간은 14, 작업 시간이 9밀리초이므로 한 번에 처리되고 종료됩니다.
- P1의 차례가 돌아왔습니다. 이때 P1의 대기 시간은 첫 번째 작업 종료 후부터 지금까지이므로 19입니다. 남은 작업이 20이지만 타임 슬라이스의 제한 때문에 10밀리초 작업 후 다시 뒤로 밀립니다.
- P2 차례가 돌아왔습니다. 이때 P2의 대기 시간은 P3의 작업 시간 + P1의 작업 시간이므로 19밀리초입니다. 남은 작업이 8밀리초에 끝났습니다. P2 또한 종료됩니다.
- P1이 다시 돌아왔습니다. 대기 시간은 8밀리초이고, 남은 작업을 모두 마치고 종료됩니다.
라운드 로빈 스케줄링의 평균 대기 시간은 (0 + 7 + 14 + 19 + 19 + 8)/3 = 약 22.33밀리초 입니다.
라운드 로빈 스케줄링같은 선점형 방식은 타임 슬라이스 이후 다른 프로세스가 CPU에 할당되므로 콘베이 효과가 줄어듭니다. 하지만 이 방법 또한 문제가 없지 않습니다. 타임 슬라이스 이후에 프로세스가 바뀌면서 문맥 교환이 계속 발생하기 때문에 이에 대한 오버헤드가 존재합니다. 따라서 라운드 로빈 스케줄링이 효과적으로 동작하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 조절해야 합니다.
타임 슬라이스의 크기는 프로세스의 반응 시간에 영향을 미칠 뿐만 아니라 시스템 전체의 성능에도 영향을 미칩니다. 타임 슬라이스의 크기가 너무 크면 프로그램이 뚝뚝 끊겨 보일 것이고, 너무 작으면 시스템의 성능이 떨어집니다.
SRT 우선 스케줄링
개요
SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로, 최소 잔류 시간 우선 스케줄링이라고도 부릅니다. 기본적으로 라운드 로빈 스케줄링을 사용하지만 CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 프로세스를 선택합니다.
성능 평가
이 또한 타임 슬라이스가 10밀리초라고 가정하겠습니다.
- P1은 도착하자마자 실행되므로 대기 시간은 0, 작업 시간은 30밀리초이지만 타임 슬라이스의 제한때문에 10밀리초 작업 후 뒤로 밀려납니다.
- P2는 3밀리초 후 도착했고, P3는 6밀리초 후 도착했습니다. 이때 남아있는 작업 시간이 P3가 더 적으므로 다음에는 P3가 실행됩니다. P3의 대기 시간은 4, 작업 시간은 9입니다.
- P3의 작업이 종료됐고 남아있는 작업 시간이 P2가 더 적으므로 P2가 실행됩니다. P2의 대기 시간은 16, 작업 시간은 10입니다.
- P2의 작업이 한 단계 끝났고 다시 작업 시간을 확인하니 P2가 더 적으므로 P2가 실행됩니다. P2의 대기 시간은 0, 작업 시간은 8입니다.
- P1이 남아서 남은 작업을 처리합니다. 대기 시간은 27, 작업 시간은 10입니다. 아직 작업이 남았으므로 다시 실행됩니다. 대기 시간은 0, 작업 시간은 10입니다. 이렇게 모든 프로세스가 종료됩니다.
SRT 우선 스케줄링의 평균 대기 시간은 (0 + 4 + 16 + 0 + 27 + 0)/3 = 약 15.67밀리초 입니다.
평균 대기 시간만 놓고보면 좋은 알고리즘인 듯 합니다. 하지만 SRT 스케줄링은 좋은 알고리즘이 아닙니다. 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가됩니다. 또한 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않습니다.
우선순위 스케줄링
개요
각 프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘입니다. 기준에 따라 다양하게 구현할 수 있습니다. 위 프로세스들을 작업 시간에 따라 우선순위를 매겨봅시다.
| 도착 순서 | 도착 시간 | 작업 시간 | 우선순위 |
|---|---|---|---|
| 0 | 30 | 3 | |
| 3 | 18 | 2 | |
| 6 | 9 | 1 |
이를 FCFS 스케줄링에 적용한 결과는 다음과 같습니다.
- P1은 가장 먼저 도착했으므로 바로 실행됩니다. 대기 시간은 0, 작업 시간은 30입니다.
- P2는 3밀리초 후 도착했고, P3는 6밀리초 후 도착했습니다. 둘 중 P3가 우선순위가 더 높으므로 P1 종료 시 P3가 실행됩니다. P3의 대기 시간은 24, 작업 시간은 9입니다.
- P3 종료 후 P2가 실행됩니다. P2의 대기 시간은 36, 작업 시간은 18입니다.
우선순위를 적용한 FCFS 스케줄링의 평균 대기 시간은 (0 + 24 + 36)/3 = 20밀리초 입니다.
우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있습니다. 우선순위 알고리즘은 고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 나뉩니다.
- 고정 우선순위 알고리즘: 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정됩니다. 구현은 단순하나 시스템의 유동적인 변화에 대응하지 못해 효율성이 떨어집니다.
- 변동 우선순위 알고리즘: 우선순위가 시스템의 상황에 따라 변합니다. 구현은 복잡하지만 효율성이 높아집니다.
우선순위 스케줄링은 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스를 먼저 CPU에 할당하므로 아사 현상을 일으키고 공평성에 문제를 발생시킵니다. 또한 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위를 매번 바꿔야 하므로 오버헤드가 발생하여 시스템의 효율성을 떨어뜨립니다. 하지만 프로세스의 우선순위는 시스템의 효율성이 아니라 중요도에 따라 결정됩니다. 커널 프로세스와 일반 프로세스의 우선순위가 같다면 더 중요한 커널 프로세스의 처리가 제대로 이루어지지 않게 됩니다.
다단계 큐 스케줄링
우선순위에 따라 준비 큐를 여러 개 사용하는 방식입니다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입됩니다. 큐는 라운드 로빈 방식으로 운영되며 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정됩니다. 우선순위는 고정형 우선순위를 사용하며, 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됩니다.
다단계 큐 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식입니다. 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있고 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있습니다. 하지만 우선순위가 높은 상위 큐의 작업이 모두 끝나지 않으면 하위 큐들의 프로세스들의 작업은 처리되지 않는다는 단점이 있습니다. 이를 해결한 방식이 다단계 피드백 큐 스케줄링입니다.
다단계 피드백 큐 스케줄링
이 방식은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식입니다. 다단계 피드백 큐 스케줄링은 CPU를 사용하고 난 프로세스의 우선순위가 낮아집니다. CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어갑니다.
다단계 피드백 큐 스케줄링은 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화합니다. 물론 프로세스의 우선순위가 낮아진다고 해도 커널 프로세스가 일반 프로세스의 큐에 삽입되진 않습니다.
또 다른 특징은 우선순위에 따라 타임 슬라이스의 크기가 다르다는 것입니다. 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커집니다. 따라서 이 방법 역시 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스에 비해 CPU를 얻을 확률이 여전히 낮습니다. 그래서 기회를 얻었을 때 CPU를 점유하는 시간을 늘리는 방식으로 처리합니다. 결국 마지막에 있는 큐의 타임 슬라이스는 무한대가 됩니다. 즉 프로세스가 종료될 때까지 작업을 진행합니다. 그러므로 다단계 피드백 큐 스케줄링에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작합니다.
다단계 피드백 큐 스케줄링은 오늘날 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식이고, 변동 우선순위 알고리즘의 전형적인 예입니다.
Uploaded by Notion2Tistory v1.1.0