[정보처리기사] 스케줄링 알고리즘

* 선점형 기법 (Preemptive)

- 다른 프로세스가 실행 중이더라도 운영체제가 CPU를 강제로 뺏을 수 있는 방식

- 잦은 문맥 교환(Context Switching)으로 오버헤드가 많이 발생

 

1) Round Robin

- 시간단위를 정해서 프로세스를 순서대로 CPU를 할당하는 방식

2) SRT (Shortest Remaining Time)

- 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법

- CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식

- 반환시간 = 실행시간 + 대기시간 - 도착시간

3) 다단계 큐 (MLQ, Multi-Level Queue)

- 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당 ( ~> 기아현상 발생할 수 있음)

4) 다단계 피드백 큐 (MLFQ, Multi-Level Feedback Queue)

- 프로세스 생성 시 가장 높은 우선순위 준비 큐에 등록되며 등록된 프로세스는 FCFS 순서로 CPU를 할당받아 실행되고, 할당된 시간이 끝나면 다음 단계의 준비큐로 이동

 

* 비선점형 기법 (Non-Preemptive)

- 순서대로 처리되는 공정성 보장

- 다음에 처리해야 할 프로세스와 관계없이 응답시간을 예상할 수 있음

 

1) FCFS (First Come First Service)

- 먼저 도착한 프로세스를 먼저 처리하는 스케줄링 알고리즘

- 최대 평균 시간 : 작업이 오래 걸리는 작업을 우선으로 처리하여 반환시간을 계산 (내림차순 정렬 후 계산)

- 최소 평균 시간 : 작업이 빨리 끝나는 작업을 우선으로 처리하여 반환시간을 계산 (오름차순 정렬 후 계산)

2) SJF (Shortest Job First)

- 짧은 작업들을 우선적으로 처리하다 보니, 평균 대기시간이 가장 적은 최적의 스케줄링

- 기아현상이 발생할 수 있음 (기아현상 : SJF, 우선순위, SRT, MLQ / 에이징 기법 : HRN, MLFQ)

3) HRN (Highest Response ratio Next)

- SJF 기법에서 비교적 실행시간이 긴 프로세스가 가질 수 있는 불리함을 보완한 스케줄링 방식

- 우선순위 = (대기시간 + 실행시간) / 실행시간

4) 우선순위 (Priority)

- 프로세스마다 우선순위를 부여하여 높은 우선순위를 가진 프로세스에게 먼저 자원을 할당

5) 기한부 (Deadline)

- 주어진 시간 내에 완료되지 못할 경우, 해당 프로세스는 제거되거나 처음부터 다시 실행되어야 하므로 부담이 매우 큰 기법