[운영체제] 프로세스 스케줄링 알고리즘
Updated:
Goal
- 프로세스 스케줄링 알고리즘에 대해 알아보자
1. FCFS (First Come First Served) 스케줄링
- 가장 간단한 스케줄링 방식
- 비선점 스케줄링 방법
- 프로세스들은 대기 큐에 도착한 순서에 따라 중앙처리장치를 할당받는다.
- 프로세스가 중앙처리장치를 차지하면 완료될 때까지 CPU를 점유하며 수행된다.
- 모든 프로세스가 동일하게 취급되고, 응답 시간의 차이가 적게나며, 작업 완료 시간을 예측하기가 용이하다.
- 단점 : Convoy Effect (호위 효과)
- 첫 번째 프로세스가 끝날 때까지 매우 긴 시간을 기다리게 된다. -> CPU와 장치 이용률이 낮아진다.
2. SJF (Shortest Job First) 스케줄링
- 프로세스 중에서 수행시간이 가장 짧은 것을 먼저 수행하는 비선점 스케줄링 방식
- 긴 프로세스보다 짧은 프로세스에게 더 유리하다.
- 단점 :
- 수행될 프로세스나 프로세스가 얼마나 긴 것인가를 정확히 알아야 하는데, 이 정보를 얻기가 어려움
- 적절한 응답시간이 보장되어야 하는 시분할방식의 시스템 상황에서는 적당하지 못하다.
3. 우선순위(Priority) 스케줄링
- 각 프로세스에게 우선순위가 주어지며, 중앙처리장치는 가장 높은 우선순위를 가진 프로세스로 할당
- 프로세스가 ready큐에 도착하면, 그 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교한다.
- 현재 실행중인 프로세스보다 높으면, 중앙처리장치를 선점하게 된다.
- 단점 :
- 무한 대기(Indefinite blocking) 또는 기아 현상(Starvation)
- 낮은 우선순위의 프로세스들이 중앙처리장치를 무한히 대기하게 하는 경우
- 낮은 우선순위의 프로세스들의 무한 대기 문제에 대한 해결책 -> 에이징(aging)기법
- 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법
- ex) 매 15분마다 대기 중인 프로세스의 우선순위를 1씩 증가시킨다.
4. 라운드 로빈(Round-Robin) 스케줄링
-
대화식 사용자들에게 알맞은 응답시간을 보장해 주어야 하는 시분할 시스템을 위하여 고안된 선점 스케줄링 방식
- 각 프로세스는 같은 크기의 중앙처리장치 시간을 할당 받음
- 할당시간(time quantum)의 크기는 보통 10에서 100ms 사이
- 너무 크면, 각 프로세스를 처리 완료하는데 필요한 시간보다 많은 시간이 할당되는 경우가 된다. - FCFS 방식이 됨
- 너무 작으면, Context Switching으로 인한 오버헤드가 커진다.
- 만약 프로세스가 중앙처리장치 시간이 만료될 때까지 처리를 완료하지 못하면 그 중앙처리장치는 대기 중인 다음 프로세스에게 어가며, 실행 중이던 프로세스는 준비완료 리스트(ready queue)의 가장 뒤로 보내진다.
5. SRT(Shortest Remaining Time) 스케줄링
SJF 기법에 선점 방식을 도입한 방법
- 시분할 시스템에서 유용
- 새로 도착한 프로세스를 포함하여 처리가 완료되는 데 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행
- SJF는 한 번 작업의 처리가 시작되면 완료될 때까지 계속 실행되지만, SRT에서는 실행 중인 프로세스가 선점될 수 있다.
6. 다단계 큐 (Multilevel Queue) 스케줄링
- 작업들을 여러 그룹으로 나누어 여러 개의 큐를 이용하는 기법
- 전면작업 (foreground job : 대화식)과 후면작업 (background job : 일괄처리) 프로세스들로 나눈다. 서로 다른 응답시간을 요구하기 때문에 상이한 스케줄링이 필요하다.
- 전면작업 프로세스들은 후면작업 프로세스들 보다도 높은 우선순위 부여됨
- 후면작업 큐가 선입선출 알고리즘에 의해 스케줄 되는 반면 전면작업 큐는 라운드 로빈 알고리즘에 의해 스케줄 됨
- 큐별로 스케줄링
- 전면작업 큐에는 자신의 프로세스들 사이에서 라운드 로빈 스케줄링을 위해 중앙처리장치 시간의 80%
- 후면작업 큐는 자신의 프로세스들을 선입 선처리 방식으로 중앙처리장치 시간의 20% 등의 방법으로 처리
7. HRN (High Response ratio Next) 스케줄링
- SJF의 약점, 특히 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법이다.
- 일단 한 작업이 중앙처리장치를 차지하면 그 작업은 완성될 때까지 실행하며, 대기시간이 고려되어 긴 작업과 짧은 작업 간의 불평등을 어느 정도 완화함
- 짧은 작업일지라도 대기시간이 큰 작업은 우선순위가 높아진다.
- 우선순위 : (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간 = 시스템 응답시간
Leave a comment