본문 바로가기
방송통신대학교12/컴퓨터과학과 [3학년 1학기]

[운영체제] 3강 스케줄링 알고리즘

by Jundol 2018. 3. 13.

1. 스케줄링 성능 평가 기준
이번강좌에선 주로 하위단계 스케줄링(디스팩터)을 다룬다

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

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

[대기시간은 준비큐에서 기다리고있던 시간만큼이 대기시간이된다]
[반환시간은 준비큐에 들어온시점부터 CPU 수행이 완료된 시간이 반환시간이된다]

(그림 평균반환대기시간)

 

 

2. 다양한 스케줄링 알고리즘

1) FCFS (First-Come First-Served)

[자료구조에서 큐를 생각하면된다.]
비선점 스케줄링 알고리즘
준비 큐에 도착한 순서에 따라 디스패치

예) (그림 FCFS 스케줄링의 예)

 

장점: 가장 간단한 스케줄링 기법
단점: 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로스세가 나중에 수행될 수 있음
        프로세스들의 도착 순서에 따라 평균 반환시간이 크게 변함

(그림 FCFS 스케줄링의 단점)

 

2) SJF (Shortest Job First)

비선점 스케줄링 알고리즘
준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상된 것을 먼저 디스패치

예) (그림 SJF 스케줄링의 예)

 

(그림 SJF 스케줄링에서 큐에 도착한 시간이 각기 다른 경우)

 

장점: 일괄처리 환경에서 구현하기 쉬움
단점: 실행 예정 시간 길이를 사용자의 추정치에 의존하기때문에 실제로는 먼저 처리할 작업의 CPU 시간을 예상할 수 없음.

3) SRT (Shorest Remaining Time)

선점 스케줄링 알고리즘
실행이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치

예) (그림 SRT 스케줄링의 예)

 

장점: SJF보다 평균 대기시간이나 평균 반환시간에서 효율적
        대화형 운영체제에 유용
단점: 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등 SJF보다 오버헤드가 큼

(그림 SRT의 문맥교환)


문맥교환시 기존에 CPU에서 수행하던 프로세스의 정보(남은수행시간등)을 어딘가에 저장해야되기때문에 부가적인 시간이 추가될 수 있다.

4) RR (Round Robin)

선점 스케줄링 알고리즘
준비 큐에 도착한 순서에 따라 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한
시간 할당량 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치

예) (그림 RR 스케줄링의 예)

장점: CPU를 독점하지않고 공평하게 이용, 대화형 운영체제에 유용
단점: 시간 할당량이 너무 크면 FCFS 스케줄링과 같아짐
        시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함

(그림 다양한 시간할당량에 따른 평균대기반환시간)

5 와 6사이를 기준으로 시간할당량이 6이상이 될 경우 FCFS와 다를바가 없고
5 이하로 갈 수록 문맥교환 횟수가 증가하여 오버헤드가 크게 증가한다.
그러므로 1과 5사이의 적절한 시간할당량을 골라 사용해야함.

5) HRN (Highest Response Ratio Next)

비선점 스케줄링 알고리즘
준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
(그림 응답비율 계산식)

예) (그림 HRN 스케줄링의 예)

프로세스 ABCD가 각각 종료될때마다 나머지 대기큐에있는 프로세스들의 응답비율을 계산하여 응답비율이 가장 큰 프로세스를 CPU 점유 시킨다.

장점: SJF의 단점을 보완

6) 다단계 피드백 큐 스케줄링

선점 스케줄링 알고리즘
I/O중심 프로세스와  CPU중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여
n개의 단계
각 단계마다 하나씩의 큐 존재
단계가 커질수록 시간 할당량도 커짐
[각각의 단계가 라운드로빈방식과 유사]

스케줄링 방법

신규 프로세스는 단계 1의 큐에서 FIFO 순서에 따라 CPU 점유
입출력 같은 이벤트가 발생하면 CPU를 양보하고 대기상태로 갔다가 다시 준비상태가 될 때에는 현재와 동일한 단계의 큐에 배치
시간 할당량을 다 썼지만 프로세스가 종료되지 못했다면 다음 단계의 큐로 이동 배치
마지막 단계 n에서는 RR스케줄링 방식으로 동작
단계 k의 큐에 있는 프로세스가 CPU를 할당 받으려면 단계 1부터 단계 k - 1 까지 모든 큐가 비어있어야만 함.

장점: I/O 위주의 프로세스(대화형)는 높은 우선권 유지
        연산 위주의 CPU중심 프로세스는 낮은 우선권이지만 긴 시간 할당량을 가짐

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

시간 할당량을 다 쓰기전에 CPU를 반납하는 경우 하나 작은 단계의 큐로 이동 배치
연산 위주의 프로세스가 I/O 위주로 바뀐다면 점점 작은 단계로 배치 가능


(그림 비선점과 선점에 따른 알고리즘 분류)

댓글0