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

목차

1. 스케줄링 성능 평가 기준
2. 다양한 스케줄링 알고리즘

---

1. 스케줄링 성능 평가 기준

:  스케줄링 성능 평가 기준

■ 평균 대기시간

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

 

■ 평균 반환시간

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

---

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

:  FCFS 스케줄링

■ FCFS(First Come First Served) 스케줄링

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

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

 

■ 장점

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

 

■ 단점

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

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

 

:  SJF 스케줄링

■ SJF(Shortest Job First) 스케줄링

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

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

 

■ 장점

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

 

■ 단점

- 실행 예정 시간 길이를 사용자의 추정치에 의존하기 때문에 

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

 

:  SRT 스케줄링

■ SRT(Shortest Remaining Time) 스케줄링

- 선점 스케줄링 알고리즘

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

 

■ 장점

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

- 대화형 운영체제에 유용

 

■ 단점

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

 

:  RR 스케줄링

■ RR(Robin Round) 스케줄링

- 선점 스케줄링 알고리즘

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

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

 

■ 장점

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

- 대화형 운영체제에 유용

 

■ 단점

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

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

 

:  HRN 스케줄링

■ HRN(Highest Response Ratio Next) 스케줄링

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

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

 

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

 

■ 장점

- SJF의 단점을 보완

 

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

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

- 선점 스케줄링 알고리즘

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

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

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

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

 

■ 스케줄링 방법

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

- 입출력 같은 이벤트가 발생하면 CPU를 양보하고 대기상태로 갔다가

  다시 준비상태가 될 때에는 현재와 동일한 단계의 큐에 배치

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

- 마지막 단계 n :  RR 스케줄링 방식으로 동작

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

 

■ 장점

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

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

 

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

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

- 연산 위주의 프로세스가 I/O위주로 바뀌는 경우 : 점점 작은 단계로 배치 가능

---

 

정리하기

- FCFS 스케줄링 : 준비 큐에 도착한 순서에 따라 디스패치하는 비선점 방식의 스케줄링 알고리즘

- SJF 스케줄링 : 준비 큐에서 기다리는 프로세스 중 수행시간이 가장 짧다고 예상되는 것을 먼저 디스 패치하는 비선점 방식의 스케줄링 알고리즘

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

- RR 스케줄링 : 정해진 시간 간격만큼씩 순서대로 돌려가며 디스패치하는 선점 방식의 알고리즘

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

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

- 다단계 피드백 큐 스케줄링은 각 단계의 큐마다 주어진 시간 할당량을 모두 소비하고 선점된 프로세스는 큰 단계 큐로 가고, 그렇지 않은 프로세스는 점차 작은 단계로 갈 수 있게 하는 적응적 방식의 변형도 있다.