선점형 스케줄링 방식(preemptive)
CPU 자원을 사용 중인 프로세스에 interrupt를 걸고, 다른 프로세스를 실행시킬 수 있다.
어떤 경우에 프로세스에 interrupt를 걸건지 알아보자!
1. 라운드 로빈 스케줄링(Round Robin; RR)
한 프로세스가 할당받은 시간(time slice, time quantum) 동안 작업을 하다가 작업을 완료하지 못하면 ready queue의 맨 뒤로 가서 자기 차례를 기다리는 방식
프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다. 선점형 방식 중에 가장 단순하다.
라운드 로빈은 각 프로세스마다 CPU를 사용할 수 있는 최대 시간, time slice가 있다는 것이다. 프로세스는 자신에게 주어진 time slice동안만 작업을 할 수 있으며 작업이 다 끝나지 않으면 ready queue의 맨 뒤로 다시 삽입된다.
만약 더 이상 실행될 것들이 없다면(실행 시간 <= time slice) 완료되고, 실행할 것은 남아있는데 time slice를 다 썼다면 time out되어 ready queue 맨 뒤에 다시 들어가서 자신의 순서가 오기를 기다린다.
2. SRT 우선 스케줄링(Shortest Remaining Time)
최소 잔류 시간 우선 스케줄링으로, SJF(shortest job first)의 preemptive 버전이라고 할 수 있다.
SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만 CPU를 할당 받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 프로세스를 선택한다. 라운드 로빈 스케줄링이 큐에 있는 순서대로 CPU를 할당한다면, SRT 스케줄링은 남은 작업 시간 순서 중 가장 적은 프로세스를 선택한다.
ready queue에 있는 프로세스 중 잔류 시간(남아있는 실행 시간)이 가장 짧은 프로세스를 선정하여 실행시킨다.
만약 모두 동일하다면 라운드 로빈으로 (앞에서부터 순서대로) 돌아가면서 실행된다.
SRT는 time slice를 따로 두지 않기 때문에 한 번 실행되면 자신보다 작업시간이 짧은 process가 있지 않는 한 계속해서 실행된다.
2.1 Advanced SRT 우선 스케줄링
SRT는 fairness 문제가 있다. 즉, 작업 시간이 긴 프로세스는 실행되지 않는 starvation 문제가 발생할 수 있다. 이는 SRT 알고리즘이 time slice 없이 동작하기 때문이다. 그렇다면 time slice를 주어 특정 프로세스만 계속해서 동작하지 않도록 해주면 fairness를 어느정도 개선할 수 있다.
3. 우선순위 스케줄링
프로세스는 중요도에 따라 priority를 가지는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다. 우선순위 스케줄링은 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다.
예를 들어 FCFS 스케줄링에서 '작업 시간이 짧은' 프로세스에게 높은 우선순위를 부여한다고 가정해보자.
첫번째로 도착한 프로세스 P1은 대기하지 않고 바로 실행된다. P1이 작업을 마치면 P2와 P3가 기다리고 있다. 두 프로세스 중 P3의 우선순위가 P2보다 높기 때문에 P3가 먼저 실행되고, P3가 작업을 마치면 이어서 P2가 실행된다. 이 경우 총 대기 시간과 평균 대기 시간은 SJF 스케줄링과 같다.
참고로 우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있다.
- 비선점형 방식
- SJF 스케줄링: 작업 시간이 짧은 프로세스에게 높은 우선순위를 부여한다.
- HRN 스케줄링: 작업 시간이 짧거나 대기 시간이 긴 프로세스에게 높은 우선순위를 부여한다.
- 선점형 방식
- SRT 스케줄링: 남은 작업시간이 짧은 프로세스에게 높은 우선순위를 부여한다.
이처럼 우선순위 스케줄링은 선점형 or 비선점형 방식으로 구현이 가능하다.
- 고정 우선순위 알고리즘: 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정된다. 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.
- 변동 우선순위 알고리즘: 일정 시간마다 우선순위가 변한다. 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만, 시스템의 상황을 반영하여 효율적인 운영이 가능하다.
4. 다단계 큐 스케줄링
우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다.
프로세스는 OS로부터 부여받은 우선순위에 따라 해당 우선순위 큐에 삽입된다.
라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나눠져있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정된다. 우선순위는 고정형 우선순위를 사용하며 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.
다단계 큐 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능한 선점형(preemptive) 방식이다. 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있으며, 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있다.
다단계 큐 스케줄링은 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다. 우선순위가 1번인 큐에 CPU 할당을 기다리는 프로세스가 있다면 우선순위가 2번인 큐의 프로세스는 1번 큐에 프로세스의 작업이 끝날 때까지 기다려야 한다. 즉, 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데 이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다.
즉, 하나의 큐에서는 선점형 방식으로 프로세스들이 time slice를 할당받아 작업이 진행되지만, 큐들끼리는 비선점형 방식이기 때문에 상위 큐에서 프로세스들이 실행이 완료되기 전까지는 하위가 실행될 수 없다.
5. 다단계 피드백 큐 스케줄링
우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
다단계 큐 스케줄링과 기본적인 형태는 같아 우선순위를 가진 여러 개의 큐를 사용한다. 하지만 다단계 피드백 큐 스케줄링의 경우 CPU를 사용하고 난 뒤 프로세스의 우선순위가 낮아진다. CPU를 사용한 프로세스는 원래 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
결국 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는(우선순위가 가장 낮은) 프로세스는 무한대의 time slice를 얻는다. 때문에 가장 마지막 큐에 있는 프로세스를 처리하는 방식은 FCFS가 된다.
다단계 피드백 큐 스케줄링은 오늘날 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예이다.
unix에서 time slice를 고정하지 않고, 10~200 ms 사이에서 조정할 수 있도록 한 이유는 바로 다단계 피드백 큐 스케줄링을 사용하기 때문이다.
