본 게시물은 영남대학교 곽종욱 교수님의 강의를 기반으로 작성됨
Preemptive vs Non-Preemptive
- Non - Preemptive(비선점형) : 한번 CPU에 올라오는 프로세스는 해당 CPU 점유시간을 모두 채우고 나서 빠져나가는 방식
- Preemptive(선점형) : 어떠한 기준에 의해 CPU에 올라간 프로세스가 CPU 점유시간을 모두 채우지 않고 dispatch 될 수 있는 방식
FCFS란?
- First-Come, First-Served 의 약자, FIFO라고도 한다
- 먼저 자원 사용 요청을 한 프로세스에게 자원을 할당해 주는 정책이라고 보면된다. 즉, 먼저 들어온 프로세스부터 레디 큐에 올려서 처리한다.
- 디스크 스케쥴링에서도 적용이 가능하다.
- Non-preemption 방식이라서 한번 CPU에 올라가면 해당 프로세스는 끝 마칠 때까지 작업을 수행한다.
Scheduling Criteria 비교
- Waiting Time이 상당히 비효율적으로 측정된다. 예를 들어 레디큐에 처음 들어온 프로세스의 Burst Time이 상당히 큰 시간이였다면, 그 시간을 레디큐 뒤쪽의 프로세스들은 오롯이 실행되길 기다려야 한다.
- 가장 초창기의 정책이라고 하며, 비효율적인 알고리즘을 가진다.
SJF란?
- Shortest Job First의 약자이고, 즉 최단 작업 우선 스케쥴링이란 뜻으로, 평균 대기 시간을 최소화하기위해서 CPU점유 시간(Burst Time)이 가장 적은 프로세스를 먼저 실행시키는 정책이다.
- 특히 비선점 방식을 가지는 정책을 SJF라 한다.
Scheduling Criteria 비교
- 비선점형이라서 Burst Time이 긴 프로세스의 경우 기아 상태가 발생 할 수있다.
- FCFS보다는 Waiting Time을 줄일 수 있다.
SRTF란?
- Shortest Remaining Time First의 약자이며, SJF정책을 비선점형에서 선점형을 변경시킨 정책이다.
- 즉 현재 진행중인 프로세스를 중단시키고 CPU 점유시간이 짧게 남은 프로세스를 처리를 가능하게 하는 정책이다.
SJF vs SRTF
CPU 점유시간 비교 정책들의 문제점
- 그래서 어떻게 CPU Burst Time을 알아낼것이가?에 대한 문제가 발생
- 실행 시간이라는 임의의 값이라서 실제로 예측하기 어렵기 때문에 이러한 문제가 생긴다.
- 통계학적인 유추를 통해 BT 추정(Exponential Average 이용)
- 𝞃(i+1) = 𝛼t(i) + (1-𝛼)𝞃(i)
- 𝛼는 가중치 값
- 위 공식을 이용하여 예측이 가능하며 아래의 그림처럼 결과가 나온다