비선점형 프로세스 스케줄링 - FIFO, SJF, HRN, 우선순위, 기한부

 

👊 FIFO(First Input First Output) = FCFS(First Come First Service)

 

먼저 온 순서대로 프로세스를 처리하므로 "공정하다"는 것 말고는 별 볼일 없다.

소요시간이 짧거나 중요한 작업이더라도 늦게 기다렸다가 실행되어야 하는 불상사가 생긴다.

다른 계획 없이 대기 큐에 그냥 줄줄이 받으므로 평균반환시간이 굉장히 길다.

 

FIFO 평균 반환시간 계산

작업	실행시간(실행시간의 추정치)	도착시간(제출시간)
A	24	0
B	6	1
C	3	2

 

반환시간 = 실행시간 + 대기시간
실행시간평균 = (24+6+3) / 3 = 11
대기시간평균 = [(0) + (24-1) + (30-2)] / 3 = 17
∴ 반환시간평균 = 28

---

👊 SJF(Short Job First)

 

짧은 작업에게 우선권을 부여하는 방식

현재 실행중인 프로세스는 중단할 수 없지만, 아직 대기중인 프로세스들 사이에서 실행시간이 짧은 프로세스 순서대로 대기 큐를 변경한다.

단, 대기중인 프로세스 중 실행시간이 상대적으로 긴 프로세스가 있다면, 그 프로세스는 계속 뒤로 밀리기만 하는 "무한대기(기아상태)" 상태에 빠지게 되는 단점이 있다. 이를 해결하는 방법으로 뒤로 밀리는 최대 시간을 한계점으로 두어, 그 시간이 초과되면 그것부터 그냥 실행시키는 "Aging(노화)기법"이 있다.

*무한대기는 언젠가는 실행이 되긴 하는 것이지만, 다른 개념으로 "교착상태"는 실행의 가능성이 아예 없는 것을 말한다.

 

SJF 평균 반환시간 계산

작업	실행시간(실행추정시간)	도착시간(제출시간)
A	24	0
B	6	1
C	3	2

반환시간 = 실행시간 + 대기시간
실행시간평균 = (24+3+6) / 3 = 11
대기시간평균 = [(0) + (24-1) + (27-2)] / 3 = 16
∴ 반환시간평균 = 27

---

👊 HRN(Highest Response-ratio Next)

 

지금까지 살펴본 결과 FIFO는 최적화 기능이 아예 없었고, SJF는 실행시간이 긴 것은 외면당했다.

HRN은 FIFO와 SJF의 단점을 모두 보완하였다.

실행시간 추정과 선점 기능 때문에 스케줄러가 복잡해지고 남은 계산 시간들을 저장해 놓아야 하는 단점을 보완

프로세스가 실제 실행(할당)될 시간과 대기시간에 따라 우선순위를 결정

HRN은 대기시간 + 서비스(실행)시간 / 서비스(실행)시간 값이 큰 순서대로 실행한다.

 

HRN 우선순위 계산

작업	실행시간(실행추정시간)	대기시간
A	18	10
B	24	16
C	19	8

A = (10+18) / 18 = 1.56
B = (24+16) / 24 = 1.67
C = (19+8) / 19 = 1.42
B->A->C 순서로 실행

---

👊 우선순위

 

미리 정의한 알고리즘대로 프로세스의 우선순위를 결정하는 방식

---

👊 기한부

 

프로세스마다 정해진 시간할당량만큼만 실행되도록 지정하는 방식

다중프로그래밍 정도(프로세스량)가 클수록 좋지 않다.