스케줄링 알고리즘

2022.02.25 - [개발/운영체제] - 프로세스 (Process)

프로세스 (Process)

이어지는 포스팅입니다.

 

목차

• 스케줄링 성능 평가기준
• 스케줄링 알고리즘

---

스케줄링 성능 평가기준

 

 스케줄링이란 모든 프로세스가 효율적으로 적정 수준을 유지하면서 CPU  작업을 할 수 있도록 하고 (공정성), 시스템의 자원들이 충분하게 고루 활용 (균형)될 수 있게 하는 것을 말합니다. (이전 포스팅 참고) 그러므로 스케줄링의 성능은 위 2가지(공정성, 균형)를 얼마나 효율적으로 수행하나를 평가해야 합니다. 스케줄링 성능의 평가 기준은 크게 2가지입니다.

 

• 평균 대기시간 : 프로세스가 준비 큐에서 실행될 때까지 기다린 시간의 평균값
• 평균 반환시간 : 프로세스가 생성된 시점에서 수행 완료된 시점까지의 소요시간의 평균값

 

 아래와 같이 A, B 프로세스가 진행되었다고 했을 때, 평균 대기시간은 3.5, 평균 반환시간은 6.5가 됩니다.

 

---

스케줄링 알고리즘

 

 스케줄링을 진행할 때 선점 정책으로 할지, 비선점 정책으로 할지, 어떤 기준에 의해 준비 큐의 대기 중인 프로세스를 가져올지 등을 결정해야 합니다. 따라서 위와 같은 기준들을 정할 수 있는 스케줄링 알고리즘이 필요합니다. 대표적인 스케줄링 알고리즘에는 아래와 같은 것들이 있습니다.

 

• FCFS 스케줄링
• SJF 스케줄링
• SRT 스케줄링
• RR 스케줄링
• HRN 스케줄링
• 다단계 피드백 큐 스케줄링

 

FCFS (First come First Served) 스케줄링

• 비선점 스케줄링 정책
• 준비 큐에 도착한 순서대로 디스패치 (dispatch)
• 장점 : 스케줄링 알고리즘이 간단함
• 단점 : 수행 시간이 짧은 프로세스가 앞의 긴 프로세스를 기다리는 경우가 생김. (비효율)

 

* 디스패치 : 프로세스에 CPU를 할당.

 

SJF (Shortest Job First) 스케줄링

• 비선점 스케줄링 정책
• 준비 큐에 있는 프로세스 중 실행시간이 가장 짧을 것으로 예상되는 것을 디스패치
• 장점 : 전체 프로세스를 일괄처리에서 구현하기 용이함
• 단점 : 각 프로세스들의 실행 예정시간을 사용자의 추정치이기 때문에 실제 수행 시간과 다를 수 있음

 

SRT (Shortest Remaining Time) 스케줄링

• 선점 스케줄링 정책
• 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치
• 선점 정책이기 때문에, 실행 중인 프로세스가 있다면 문맥 교환 발생
• 장점 : SJF 보다 평균 대기 / 반환 시간이 효율적임, 대화형 운영체제에 적합
• 단점 : 문맥 교환 발생, SJF 대비 오버헤드가 큼

 

RR (Round Robin) 스케줄링

• 선점 스케줄링 정책
• 기본적으로 준비 큐에 도착한 순서대로 디스패치, 프로세스별로 동일한 실행 시간 할당량을 주어서 실행시간에 제한
• 이때 시간 할당량 안에 끝내지지 못한 프로세스는 준비 큐의 맨 뒤에 put
• 장점 : CPU를 특정 프로세스가 독점하지 않고, 공평하게 수행, 대화형 운영체제에 적합
• 단점 : 시간 할당량이 크면 FCFS 스케줄링과 차이가 없음. 시간 할당량이 너무 작으면 문맥 교환 빈도가 잦아져 오버헤드가 증가

 

HRN (Highest Response Ratio Next) 스케줄링

• 비선점 스케줄링 정책
• 준비 큐의 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
• 장점 : SJF의 단점을 보완함

* 응답비율이 큼 = 예상시간이 짧고, 대기시간이 김

 

 

다단계 피드백 큐 스케줄링

• 선점 스케줄링 정책
• I/O 중심 프로세스와 CPU 중심 프로세스의 특성을 고려하여 각기 다른 시간 할당량 부여
• n단계로 이루어짐 (n은 1 이상), 단계별로 하나씩 큐가 존재
• 단계가 커지면 시간 할당량이 증가함

 

진행순서

 

1. 신규 프로세스는 FIFO를 따라 단계 l 큐에 진입
2. I/O와 같은 이벤트가 발생 시 CPU를 양보하고 대기상태.
3. 다시 준비단계로 갈 때는 현재 큐 (단계 l)에 재배치
4. 시간 할당량을 다 써도 종료되지 못한 프로세스는 다음 단계 큐 (l+1)로 이동
5. 마지막 단계 n에서는 RR 스케줄링 방식으로 동작
6. 단계 k의 큐에 프로세스가 CPU를 할당받기 위해서는 이전 단계의 모든 큐가 비어있어야 함

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