3강 제 3강 스케줄링 알고리즘

학습목표

1. 스케줄링 성능 평가 기준을 설명할 수 있다.

2. 다양한 스케줄링 기법을 나열하고 설명 할 수 있다.

 

주요 용어

# 평균대기시간 #평균반환시간 #FCFS #SJF #SRT #RR #HRN #다단계 피드백큐

 

 

 

3.1 스케줄링 성능 평가 기준

 

스케줄링 알고리즘의 성능을 평가하는데

평균대기시간(average waiting time)과 평균 반환시간(average turnaround time)이 이용된다.

 

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

 

평균 반환 시간 : 각 프로세스가 생성된 시점(준비큐에  들어온 시점과 동일한 것으로 가정) 부터 수행 완료 된 시점까지의 소요시간의 평균값

 

 

 

3.2 FCFS ( First-Come First-Served ) 스케줄링

비선점 스케줄링 

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

ABCD 순서대로 삽입

 

CBDA 순서로 삽입

장점

 -가장 간단한 스케줄링 기법

 

단점 

 -짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음

 -프로세스들의 도착 순서에 따라 평균 반환 시간이 크게 변함

 

 

 

 

3.3 SJF (Shortest Job First ) 스케줄링

-비선점 스케줄링

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

CBDA 순으로 삽입

 

ABCD 순으로 삽입

장점 

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

 

단점 

 실행 예정 시간 길이를 사용자의 추정치에 의존하기 떄문에 실제로는 먼저 처리할 작업의 CPU 시간을 예상할 수 없음

 

 

 

 

3.4 SRT (Shortest Remaining Time ) 스케줄링

 선점 스케줄링

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

 

장점

 SJF 보다 평균대기시간이나 평균반환시간에서 효율적

 대화형 운영체제에 유용

 

단점

 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환등 SJF 보다 오버헤드가 큼

(위 그림에 빨간 색 동그라미 부분 : 문맥 교환)

 

(문맥 교환 : CPU가 현재 실행하고 있는 프로세스의 문맥(상태)을 프로세스 제어블록 (PCB)에 저장하고, 다음 프로세스의 PCB로부터 문맥을 복원하는 작업)

 

 

 

 

 

 

3.5 RR ( Round Rpbin ) 스케줄링

선점 스케줄링

준비 큐에 도착한 순서에 따라 디스패치 하지만 정해진 시간 할당량에 의해 실행을 제한

시간 할당량( 시간 간격 ) 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치

 

장점 

CPU를 독점하지 않고 공평하게 이용

대화형 운영체제에 유용

 

단점

시간 할당향이 너무 크면 FCFS 스케줄링과 같아짐

시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가

 

 

 

 

 

3.6 HRN ( HRRN, Highest Response Ratio Next ) 스케줄링

- 비선점 스케줄링 알고리즘

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

- 대기시간과 서비스 받을 시간을 함께 고려한 우선순위에 따라 스케줄링하는 비선점 방식의 알고리즘

 

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

 

 

장점 

 SJF의 단점을 보완 

 >>>  SJF 의 단점 수행시간이 긴 프로세스는 계속 기다릴수 있다 .

    HRN 방식은 기다릴수록 우선순위가 높아짐

 

 

 

 

 

 

3.7 다단계 피드백 큐 스케줄링

선점 스케줄링

-입출력 위주의 프로세스(대화식 작업)가 CPU 스케줄링에 우선권을 갖도록 하는 선점 방식의 알고리즘

-n 개의 단계 ( 단계 1 ~ 단계 n )

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

-단계가 커질수록 시간 할당량도 커짐 

 

 

스케줄링 방법

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

-입출력 같은 이벤트가 발생하면 CPU를 양보하고 대기상태로 갔다가 다시 준비상태가 될 때에는 현재와 동일한 단계의 큐에 배치 

-시간 할당량을 다 썼지만 프로세스가 종료되지 못했다면 다음 단계의 큐로 이동 배치 

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

-단계 𝑘 의 큐에 있는 프로세스가 CPU를 할당 받으려면 단계 1 부터 단계 𝑘-1 까지 모든 큐가 비어있어야만 함

 

 

장점

-I/O 위주의 프로세스(대화형)는 높은 우선권 유지 

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

 

 

 

 

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

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

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

 

 

 

 

 

 

각 알고리즘 간의 연관 관계

 

FCFS   >>  ( 시간 할당량 적용 ) >>   RR   >>  ( 단계 추가 )  >>>     다단계피드백 큐

 

SJF    >>> ( 남은 대기 시간이 짧은게 )   >>>   SRT

        >>> (기다리는 시간이 길어질수록 ) >> HRN

 

 

 

 

 

 

 

 

 

 

2강 2장 프로세스 개요

2강 2장 프로세스 개요

 

4강 4강 병행프로세스 1

4강 4강 병행프로세스 1