스케줄링 알고리즘
✔ 스케줄링 알고리즘의 선택 기준
- CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용 된 시간을 측정
(이상적인 수치는 100%이지만 실질적으로 어렵다.) - 처리량 : 단위 시간 당 작업을 마친 프로세스의 수
- 대기 시간 : 프로세스가 생성된 후 자원의 할당을 대기하는 총 시간
- 응답 시간 : 프로세스 시작 후 첫번 째 출력까지 걸리는 시간
- 반환 시간(CPU burst time) : 프로세스가 생성된 후 사용하던 자원을 모두 반환하는데 까지 걸리는 시간 (대기시간 + 실행시간)
- 실행 시간 : 프로세스의 작업이 시작 된 후 종료되기 까지의 시간
- 평균 대기시간 : (모든 프로세스의 대기시간의 합) / (프로세스의 수)
- 평균 반환시간 : (모든 프로세스의 반환시간의 합) / (프로세스의 수)
이 중 주로 대기 시간, 응답 시간, 반환 시간을 성능의 지표로 쓴다. (CPU 사용률, 처리량은 측정하기 어렵다.)
✔ 스케줄링 알고리즘 종류
1. 비선점 스케줄링
- FCFS (First Come First Served) Scheduling
먼저온 순서대로 처리하는 방식으로 구현이 간단하다. 최근 시스템에서 FCFS 스케줄링은 주요 방법이 아니라 다른 방법과 결합하여 쓰이고 있다.
ex) 테이블이 하나만 있는 레스토랑
문제점 :
- 입출력 작업 시 CPU의 쉬는 시간이 많아져 비효율적
- convoy effect 발생 : CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들의 대기 시간이 늘어나는 현상
- SJF (Shortest Job First)
Ready queue에서 작업 시간이 가장 짧은 프로세스부터 CPU를 할당한다. convoy effect을 해결하였다. 선점 방식으로도 사용될 수 있는데 SRF(Shortest Remaining Time First) 또는 SRTF라고 불린다.
문제점 :
- 운영체제가 프로세스의 CPU burst time을 정확히 예측하기 힘들다.
- 스케줄링 목적 중 하나인 공평성을 위배, CPU burst time이 길면 순서가 계속 밀리는 기아(starvation)문제가 발생한다.
해결책:
aging기법을 통해 해결 가능, 하지만 에이징의 기준을 정해야 하는 문제가 있다.
+) aging 기법 : 오랫동안 기다린 프로세스에게 카운트를 사용해 우선순위를 높여줌으로서 처리하는 기법
- HRN (Hightest Response-ratio Next) Scheduling
프로세스의 대기시간과, CPU 사용 시간을 같이 고려하여 스케줄링 우선순위를 정하는 방식이다. 에이징 기법이 알고리즘에 포함되어 sjf의 아사현상을 완화
우선순위 = (대기시간 + CPU 사용 시간) / (CPU 사용 시간)
문제점
- 준비상태 큐에 있는 각 프로세스의 cpu burst time을 지속적으로 예측해야 하므로 Overhead 증가
2. 선점 스케줄링
- Priority Scheduling
우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 우선순위가 같다면 FIFO방식으로 동작
선점형과 비선점형 둘 다 가능하며 비선점형은 더 높은 우선순위의 프로세스가 오면 ready queue의 head에 추가된다.
문제점 :
- starvation 문제
- Indefinite Blocking (무기한 봉쇄) :
실행 준비가 되어 있으나 CPU를 사용하지 못하는 프로세스가 CPU를 무한정 기다리는 상태 - 우선순위가 매번 바뀔 수 있어 Overhead 발생 가능
해결책:
- aging 기법
+)
- 고정 순위 알고리즘 : 우선순위를 한번 부여받으면, 종료 될 때 까지 우선순위가 고정
- 변동 순위 알고리즘 : 우선순위가 일정 시간마다 변화시켜 시스템이 복잡하지만, 시스템의 상황을 잘 반영 할 수 있기 때문에 효율적인 운영 가능
- RR(Round Robin) Scheduling
FCFS방식으로 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할당 받아 실행되고 ready queue tail로 돌아가는 선점 방식이다. CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적이다. 공정하며(우선순위가 없다.) 응답시간이 빠른 현대적인 CPU 스케줄링
+) Time Quantum or Time Slice : 실행의 최소 단위 시간
문제점 :
- 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 너무 작으면 문맥 교환 (Context Switching) 잦아져서 Overhead가 증가한다.
- 평균 처리 시간이 높다.
SRT(Shortest Remaining Time)
기본적으로 RR스케줄링 이지만, CPU를 할당받을 프로세스를 정할 때 잔여 실행 시간이 가장 짧은 프로세스 CPU를 할당. 대화형 운영체제에 유용하며 SJF보다 평균 대기시간이나 평균 반환시간에서 효율적이다.
문제점 :
SJF와 동일하게 starvation문제와 선점을 위한 문맥 교환되어야 하므로 SJF보다 오버헤드가 더 크다.
- MLQ(Multi Level Queue) Scheduling
프로세스 성격에 따라 ready queue를 여러개로 분리하고 각 queue는 우선순위를 가지며 프로세스는 최초에 배정된 queue를 벗어나지 못한다. 프로세스가 들어왔을 때, 어떤 큐에게 보내야되는지 결정하는 메커니즘이 필요하다.
빠른 응답을 필요로 하는 대화형 작업(전위 큐)과 그렇지 않는 작업(후위 큐)으로 나눠서 프로세스를 ready queue에 분배 한다. 전위 큐에서는 빠른 응답시간을 위해 보통 RR을 사용하고 후위 큐에서는 응답 시간보다 계산 위주이기 때문에 FCFS를 사용해 오버헤드를 줄이도록 한다.
우선순위가 낮은 큐에서 기아 현상이 발생 할 수 있으므로 우선 순위가 높은 큐에는 작은 Time Quantum을, 낮은 큐에는 큰 Time Quantum을 할당한다.
문제점
- 여러개의 스케줄링 알고리즘과 queue를 관리해야하는 overhead와 우선 순위에 따른 starvation 문제가 존재한다.
+) 보통의 우선순위
1. 실시간 프로세스
2. 시스템 프로세스
3. 대화형 프로세스
4. 배치 프로세스
- MFQ(Multilevel-Feedback-Queue)
MLQ와 동일하지만 프로세스는 최초에 배정된 queue를 벗어날 수 있다. 프로세스가 time slice내에 작업이 끝나면 한단계 낮은 큐로 내려 보낸다. 반대로 어떤 큐에서 일정시간내에 작업이 실행되지 못하면 한단계 높은 큐로 프로세스를 이동시킨다. 이를 통해 MLQ의 단점인 starvation문제를 해결할 수 있다.
변동 우선순위 알고리즘의 전형적인 예이며 프로세스의 다양한 성격을 반영해 구현할 수 있다.
ex) 가장 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻을 수 있다.(FCFS 방식과 동일)
문제점
- 설계와 구현이 매우 복잡하다.
