CPU 스케줄링

스케줄러는 실행 준비가 되어있는 메모리 내의 프로세스들 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.

| 스케줄링 기준

> CPU 이용률

> 처리량 : 단위 시간당 완료된 프로셋의 개수

> 총 처리 시간 : 프로세스를 실행하는데 소요된 시간

> 대기 시간 : 프로세스가 준비 완료 큐에서 대기하는 시간

> 응답 시간 : 응답이 시작되는 데까지 걸리는 시간

>> CPU 이용률, 처리량 최대화, 총 처리 시간, 대기 시간, 응답 시간 최소화

| 스케줄링 종류

 1) 선입 선출 스케줄링(FCFS : First Come, First Served)

   : 가장 먼저 들어온 프로세스부터 차례로 할당되는 방식 (비선점형)

프로세스	버스트 시간
P1	24
P2	3
P3	3

  프로세스들이 P1,P2,P3 순으로 도착하고, FCFS로 서비스 받는다면

   

 

   위와 같이 동작한다.

   > 대기 시간 : P1=0, P2=24, P3=27

   > 평균 대기시간 : (0+24+27)/3=17

   반면, P2, P3, P1 순으로 도착하면,

   

   위와 같이 동작하고

   > 대기 시간 : P1=6, P2=0, P3=3

   > 평균 대기 시간 : (6+0+3)/3=3

   으로 앞의 경우보다 평균 대기 시간이 많이 줄어든다.

   

   > 호위 효과(convoy effect) 발생 가능

      : 짧은 프로세스들이 긴 프로세스가 CPU를 양도하기를 기다림

  짧은 프로세스들이 먼저 처리될 때보다 CPU와 장치 이용률이 저하

 2) 최단 작업 우선 스케줄링(SJF:Shortest Job First)

   : 가장 실행시간이 짧은 작업 먼저 수행하는 방식으로, 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가지는 스케줄링 방법(비선점형)

    > 동작 예

   

    > 평균 대기 시간 : (0+6+3+7)/4=4

 3) SRT(Shortest Remaining Time first)

   : SJF 방식의 선점형 방식으로 준비 큐에 있는 프로세스들 중에서 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행

    > SRT 방식 동작 예

   

   

   > 평균 대기 시간 = (9+1+0+2)/4=3

 4) Round Robin(RR) 스케줄링

   - FCFS로 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당받는다. (선점형)

   - 시분할 시스템에 적합

   - 시간 할당량이 매우 크면, FCFS와 같아진다.

   - 시간 할당량이 최소한 문맥 교환시간 보다는 커야함 (너무 작을 경우 오버헤드가 커짐)

   > 동작 예

   

   > 시간할당량은 4 밀리초

   > 평균 대기 시간 = (6+4+7)/3 = 5.66/ms

 5) HRN(Highest Response ratio Next) 스케줄링

  

   - 긴 작업과 짧은 작업 간의 지나친 불평들을 어느정도 해소한, SJF의 약점을 보완한 기법 (비선점형)

   - 일단 한 작업이 CPU를 차지하면 그 작업은 완성될 때까지 실행함

   - 우선순위 = (대기시간+서비스를 받을시간) / 서비스를 받을시간 = 시스템 응답시간

 6) 다단계 큐 스케줄링(MLQ)

   - 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법 (선점형)

   - 그룹화된 작업들을 각각의 준비 큐에 넣어두고 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당받는 방법 (포그라운드:RR, 백그라운드:FCFS)

   - 다단계 큐 알고리즘에서는 상위 단계에서 하위 단계까지 5개의 큐로 분할되어 있다. (시스템 작업, 대화형 작업, 편집 작업, 일괄처리 작업, 학생 작업)

   - 포그라운드 큐는 백그라운드 큐보다 절대적으로 높은 우선순위 부여

 7) 다단계 피드백 큐 스케줄링(MFQ)

   - 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 서로 다른 타임 슬라이스를 부여 (선점형)

   - 프로세스가 큐들 사이를 이동하는 기법으로, 프로그램이 들어오면 높은 우선순위를 할당해 주어 단계 1에서 즉시 수행해주고, 점차 낮은 우선순위를 부여하여 단계 n쯤 되는 나중에는 작업이 완료될 때까지 라운드 로빈으로 순환한다.

   - 큐들 사이 이동으로 aging을 구현하여 기아 상태를 예방

     * 기아 상태 : 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 상태

   - 결과적으로, CPU 사용시간이 짧은 입출력 중심의 프로세스와 대화형 프로세스들이 높은 우선순위 큐에서 실행되고, 반대로 계산 위주의 작업은 낮은 단계의 큐에 머물면서 우선순위는 낮지만 충분한 시간동안 CPU를 할당받게 된다.

   - UNIX 시스템은 이 방식을 스케줄링 알고리즘으로 채택

종류	방법	특징	선점/비선점
FCFS	작업이 시스템에 들어온 순서대로 수행하는 방법	- 대화형에 부적합  - 간단하고 공평  - 반응속도 예측가능	비선점
Round Robin	FCFS 방식의 변형으로 일정한 시간을 부여하는 방법	- 시분할 방식에 효과적  - 할당시간이 크면 FCFS와 같음  - 할당시간이 작으면 문맥교환이 자주 발생	선점
SJF	수행시간이 짧은 작업을 우선적으로 처리하는 방법	- 작은 작업에 유리하고 큰 작업은 상당히 시간이 많이 걸림	비선점
SRT	수행도중 나머지 수행시간이 짧은 작업을 우선적으로 처리	- 작업 처리는 SJF와 같으나 이론적으로 가장 작은 대기시간이 걸림	선점
HRN	SJF에서 큰 작업 시간이 많이 걸리는 점을 보완한 방법	- 에이징 기법으로 기아상태 해결	비선점
MLQ	서로 다른 작업을 각각의 큐에서 timeslice로 처리	- 각각의 큐는 독자적인 스케줄링 알고리즘 사용	선점
MFQ	하나의 준비상태 큐를 통해서 여러 개의 피드백 큐를 거쳐 일을 처리	- CPU와 I/O 장치의 효율을 높일 수 있음	선점

[참고]

정보보안기사&산업기사 필기 / 탑스팟 / 조상진 

http://cs.sch.ac.kr/lecture/os/2013/13-OS.htm