선점 스케줄링에 해당하는 선점 우선순위, SRT, RR, 다단계 큐, 다단계 피드백 큐 알고리즘에 대하여 알아보자.
>선점 스케줄링은 대부분 비선점 스케줄링을 보완한 것이다.
1. 선점 우선순위
* 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법이다.
* 비선점 우선순위 기법을 선점 형태로 변경한 것으로, 준비상태 큐에 새로 들어온 프로세스의 순위가 높을 경우 현재의 프로세스를 보류하고 새로운 프로세스를 실행한다.
2. SRT(Shortest Remaining Time)
* 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법으로, 선점 SJF 기법이라고도 한다.
* 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법으로, 시분할 시스템에 유용하다.
* 준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가한다.
>SRT는 SJF를 변경한 것으로, 두 개의 알고리즘을 비교하는 문제가 출제됨.
SJF는 실행시간이 가장 짧은 프로세스.
SRT는 현재 실행중인 프로세스의 남아 있는 실행 시간과 새로운 프로세스의 실행 시간을 비교하여 짧은 것.
3. RR(Round Robin)
* 시분할 시스템(Time Sharing System)을 위해 고안된 방식으로, FCFS 알고리즘을 선점 형태로 변형한 기법이다.
* FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량(Time Slice, Quantum) 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치된다.
* 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생한다.
* 할당되는 시간의 크기가 작으면 작은 프로세스들에게 유리하다.
>RR은 전반적인 내용을 묻는 문제가 출제됨. RR은 시간 할당량을 사용하는 데 할당된 시간이 클수록 FCFS와 같고, 할당되는 시간이 작을수록 문맥 교환과 오버헤드가 자주 발생된다.
예제]
4. 다단계 큐(MQ, Multi-level Queue)
* 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법이다.
* 일반적으로 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등으로 나누어 준비상태 큐를 상위, 중위, 하위 단계로 배치한다.
[그림]
>다단계 큐와 다단계 피드백 큐의 차이점을 알아두자.
* 각 준비상태 큐는 독자적인 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 서로 다른 스케줄링 기법을 사용할 수 있다.
* 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없다.
* 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당해야 한다.
5. 다단계 피드백 큐(MFQ, Multi-level Feedback Queue)
* 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법이다.
* 각 준비상태 큐마다 시간 할당량을 부여하여 그 시간 동안 완료하지 못한 프로세스는 다음 단계의 준비상태 큐로 이동된다.
* 상위 단계 준비상태 큐일수록 우선순위가 높고, 시간 할당량이 적다.
* 요구하는 시간이 적은 프로세스, 입ㆍ출력 중심의 프로세스, 낮은 우선순위에서 너무 오래 기다린 프로세스를 기준으로 높은 우선순위를 할당한다.
* 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당하며, 마지막 단계 큐에서는 작업이 완료될 때까지 RR 스케줄링 기법을 사용한다.
비선점 스케줄링에 해당하는 FCFS, SJF, HRN, 우선순위, 기한부 알고리즘에 대하여 알아보자.
>잠깐만!
비선점 스케줄링과 선점 스케줄링
다음과 같이 대응되는 표를 이용하여 각 알고리즘이 선점 기법인지 비선점 기법인지 정리하자.
[표]
1. FCFS(First Come First Service, 선입선출) = FIFO
* FCFS는 준비상태 큐(대기 큐, 준비 완료 리스트, 작업준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘이다.
* 먼저 도착한 것이 먼저 처리되어 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 된다.
예제]
>FCFS(FIFO)는 비선점 기법이며 준비상태 큐에 도착한 순서대로 할당을 받는다.
2. SJF(Shortest Job First, 단기 작업 우선)
* SJF는 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법이다.
* 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘이다.
* 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무한 연기 상태가 발생될 수 있다.
>SJF의 전반적인 특징, 평균 반환 시간을 계산하는 문제가 촐제됨.
예제1]
예제2]
3. HRN(Hightest Response-ratio Next)
* 실행 시간이 긴 프로세스에 불리한 SKF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행) 시간을 이용하는 기법이다.
* 우선순위 계산 공식을 이용하여 서비스(실행) 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 주어 CPU를 할당한다.
* 서비스 실행 시간이 짧거나 대기 시간이 긴 프로세스일 경우 우선순위가 높아진다.
* 우선순위를 계산하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위가 부여된다.
* 우선순위 계산식
[수식]
>HRN에서는 의미, 우선순위를 계산하는 공식, 계산문제가 출제됨.
예제]
4. 기한부(Deadline)
* 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법이다.
* 프로세스가 제한된 시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행해야 한다.
* 시스템은 프로세스에게 할당할 정확한 시간을 추정해야 하며, 이를 위해서 사용자는 시스템이 요구한 프로세스에 대해 정확한 정보를 제공해야 한다.
* 여러 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며, 프로세스 실행 시 집중적으로 요구되는 자원 관리에 오버헤드가 발생한다.
5. 우선순위(Priority)
* 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법이다.
* 우선순위가 동일할 경우 FCFS 기법으로 CPU를 할당한다.
* 우선순위는 프로세스의 종류나 특성에 따라 다르게 부여될 수 있다.
* 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아 상태(Starvation)가 발생할 수 있다.
>무한 연기/기아 상태
우선순위가 낮아 CPU 할당이 무한히 연기되는 상태를 무한 연기라 하고, 무한 연기 상태에서 결국 프로세스를 완료하지 못하는 상태를 기아 상태라 한다.
>잠깐만!
에이징(Aging) 기법
ㆍ시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록하는 기법이다.
ㆍ SJF나 우선순위 기법에서 발생할 수 있는 무한 연기 상태, 기아 상태를 예방할 수 있다.
