<운영체제> CPU SCHEDULING - FCFS, SJF, SRTF

본 게시물은 영남대학교 곽종욱 교수님의 강의를 기반으로 작성됨

Preemptive vs Non-Preemptive

• Non - Preemptive(비선점형) : 한번 CPU에 올라오는 프로세스는 해당 CPU 점유시간을 모두 채우고 나서 빠져나가는 방식
• Preemptive(선점형) : 어떠한 기준에 의해 CPU에 올라간 프로세스가 CPU 점유시간을 모두 채우지 않고 dispatch 될 수 있는 방식

FCFS란?

1. First-Come, First-Served 의 약자, FIFO라고도 한다
2. 먼저 자원 사용 요청을 한 프로세스에게 자원을 할당해 주는 정책이라고 보면된다. 즉, 먼저 들어온 프로세스부터 레디 큐에 올려서 처리한다.
3. 디스크 스케쥴링에서도 적용이 가능하다.
4. Non-preemption 방식이라서 한번 CPU에 올라가면 해당 프로세스는 끝 마칠 때까지 작업을 수행한다.

Scheduling Criteria 비교

1. Waiting Time이 상당히 비효율적으로 측정된다. 예를 들어 레디큐에 처음 들어온 프로세스의 Burst Time이 상당히 큰 시간이였다면, 그 시간을 레디큐 뒤쪽의 프로세스들은 오롯이 실행되길 기다려야 한다.
2. 가장 초창기의 정책이라고 하며, 비효율적인 알고리즘을 가진다.

SJF란?

1. Shortest Job First의 약자이고, 즉 최단 작업 우선 스케쥴링이란 뜻으로, 평균 대기 시간을 최소화하기위해서 CPU점유 시간(Burst Time)이 가장 적은 프로세스를 먼저 실행시키는 정책이다.
2. 특히 비선점 방식을 가지는 정책을 SJF라 한다.

Scheduling Criteria 비교

1. 비선점형이라서 Burst Time이 긴 프로세스의 경우 기아 상태가 발생 할 수있다.
2. FCFS보다는 Waiting Time을 줄일 수 있다.

SRTF란?

1. Shortest Remaining Time First의 약자이며, SJF정책을 비선점형에서 선점형을 변경시킨 정책이다.
2. 즉 현재 진행중인 프로세스를 중단시키고 CPU 점유시간이 짧게 남은 프로세스를 처리를 가능하게 하는 정책이다.

SJF vs SRTF

• 비선점

• 선점

CPU 점유시간 비교 정책들의 문제점

• 그래서 어떻게 CPU Burst Time을 알아낼것이가?에 대한 문제가 발생
• 실행 시간이라는 임의의 값이라서 실제로 예측하기 어렵기 때문에 이러한 문제가 생긴다.
• 통계학적인 유추를 통해 BT 추정(Exponential Average 이용)
• 𝞃(i+1) = 𝛼t(i) + (1-𝛼)𝞃(i)
• 𝛼는 가중치 값
• 위 공식을 이용하여 예측이 가능하며 아래의 그림처럼 결과가 나온다