운영체제 Day 3

스케줄링 성능 평가 기준 

 

평균 대기시간 : 짧을 수록 좋음

각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균

준비큐에서 기다리고 있는 시간! 

 

평균 반환시간 : 짧을 수록 좋음

각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간의 평균값

처음 준비큐에 들어온 순간부터 완료되는 순간까지!

 

 

다양한 스케줄링 알고리즘

FCFS (First Come First Served) 스케줄링 

비선점 스케줄링 알고리즘 

준비 큐에 도착한 순서에 따라 디스패치 

장점 : 가장 단순한 스케줄링 기법

단점 : 짧은 프로세스가 길게 대기할 수 있다.

중요한 프로세스가 나중에 수행될 수 있다. 

프로세스들의 도착 수선에 따라 평균 반환시간이 크게 변한다. 

 

 

 

SJF (Shortest Job First) 스케줄링 

비선점 스케줄링 알고리즘 

준비큐에서 대기중인 프로세스 중 실행시간이 가장 짧다고 예상된 것을 먼저 디스패치 

 

장점 :  일괄처리 환경에서 구현하기 쉬움

단점 : 실제 예정 시간 길이를 알기가 어렵기 때문에(추정만 가능), 적용하기 힘들다. 

실제로는 먼저 처리할 작업의 CPU시간을 예상할 수가 없다. 

 

SRT (Shortest Remaining Time) 스케줄링 

선점 스케줄링 알고리즘

실행이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치

장점 : SJF 보다 대기시간이나 반환시간이 효율적 

대화형 운영체제에 유용하다 

단점 : 각 프로세스의 실행시간 추적, 관리를 하고 있어야함. 선점을 위한 문맥 교환 등

문맥 교환이라는 오버헤드가 발생함 (레지스터 값들을 PCB에 저장해두게됨)

 

RR (Round Robin) 스케줄링

선점 스케줄링 알고리즘 

도착한 순서에 따라 디스패치를 하긴 하는데 정해진 시간 할당량만큼 CPU를 사용하게끔 한다. 

정해진 시간이 끝나면 준비큐의 가장 맨 뒤에 배치된다. 

장점 : CPU를 독점하지 않고 공평하게 사용한다

대화형 운영체제에 유용하다

단점 : 시간 할당량에 따라 편차가 많이 발생한다. 

너무 크면 FCFS 방식이랑 같아짐

너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함

 

 

HRN (Highest REsponse Ratio Next) 스케줄링

비선점 스케줄링 알고리즘 

준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치 

응답비율 : (대기시간+예상실행시간) / 예상실행시간 = 대시간/예상실행시간 +1 

예상 실행시간이 짧을수록, 대기시간이 길수록 응답비율이 커짐 

장점 :  SJF의 단점을 보완했다

(오래 기다리면 응답비율이 커진다 -> 오래걸리는 작업도 응답비율이 높아지면 빨리 가능!)

 

 

 

다단계 피드백 큐 스케줄링 

선점 스케줄링 알고리즘 

I/O 중심 (입출력) 프로세스와 CPU 중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여 

N개의 단계 존재

각 단계마다 하나씩의 큐 존재 

단계가 커질수록 시간 할당량이 커진다 

 

1. 신규 프로레스는 단계 1의 큐에서 FIFO 순서에 따라 CPU 점유 

단계 1에서 시간할당량을 다 썼는데 처리를 다 못했으면 단계 2로 이동 

입출력이 발생하면 CPU를 양보하고 대기상태로 갔으면, 원래 자기 단계 유지. 

2. 마지막 단계에서는 RR스케줄링 방식으로 동작 

3. 단계 1에서 K까지의 모든 큐가 비어있어야 K 단계에 CPU를 할당하게 된다. 

 

장점 : I/O 위주의 프로세스는 높은 우선권 유지 

연산 위주의 CPU 중심 프로세스는 낮은 우선권이지만 긴 시간 할당량을 가진다. 

 

적응정 다단계 피드백 큐 스케줄링 

시간 할당량을 다쓰기전에 CPU를 반납하게 되면 하나 작은 단계의 큐로 이동 배치 

연산 위주의 프로세스가 I/O 위주로 바뀐다면 점점 작은 단계로 배치 가능

 

 

 

 

비선점	선점
FCFS	RR (FCFS보완)
SJF	다단계 피드백큐 (RR 보완)
HRN (SJF 보완)	SRT(SJF 보완)