CPU 스케줄링 알고리즘
CPU 스케줄링 (CPU Scheduling)
- CPU core가 하나라면 한 번에 하나의 프로세스만 가능
- CPU 이용율을 극대화하기 위해서는 멀티 프로그래밍이 필요함
- 이 때 필요한 것이 CPU 스케줄링
- 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업
목표
- 높은 CPU 이용률
- 주어진 시간에 많은 일
- 준비 큐에 있는 프로세스 적게
- 짧은 응답 시간
CPU 스케줄러가 스케줄링을 결정하는 경우
- 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때
- 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때
- 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때
- 종료(Terminated)될 때
- 1, 4번 상황에서만 스케줄링이 발생하는 것이 비선점형
- 이외의 모든 스케줄링은 선점형
스케줄링의 기준
- CPU 이용률 (utilization)
- 처리량 (throughput)
- 단위 시간당 완료된 프로세스의 개수
- 긴 프로세스의 경우 몇 초 동안 한 프로세스가 될 수 있고, 짧은 트랜잭션의 경우 초당 수십 개의 프로세스가 될 수도 있음
- 총처리 시간(turnaround time)
- 프로세스의 제출 시간과 완료 시간의 간격
- 총 처리시간 = 준비 큐 대기시간 + CPU 실행시간 + I/O 시간
- 대기 시간(waiting time)
- 응답 시간(response time)
- 유저가 하나의 요구를 제출 한 뒤 첫 번째 응답이 나올 때 까지의 시간
- 첫번 째 응답의 기준은 응답이 시작되는 데 까지 걸리는 시간이고, 출력하는 데 걸리는 시간은 포함하지 않음
비선점형 스케줄링
- 어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식
- 강제로 프로세스를 중지하지 않음
- 문맥 교환(Context Switching)으로 인한 부하가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 나게 됨
1. 선입 선처리 스케줄링, FCFS (First Come, First Served)
- 가장 먼저 요청한 프로세스에 CPU를 할당해주는 선착순 방식
- CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당
- 선입선출(FIFO) Queue로 쉽게 관리
- 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료 또는 I/O 처리를 위해 CPU를 방출할 때까지 CPU를 점유
- Convoy Effect(호위 효과)가 발생할 수 있음
- Convoy 효과 : 몇 개의 시간이 오래 걸리는 프로세스로 인해 전체 OS가 느려지는 현상
- 다른 프로세스들이 하나의 긴 프로세스가 CPU를 놓기를 기다리는 것
- 선입 선처리 스케줄링에서는 호위 효과가 발생
- 결론적으로 낮은 CPU와 장치 사용률을 보이게 됨
- 한 프로세스가 지나치게 오랫동안 CPU를 점유하는 것을 허용되기 때문에 큰 손해가 발생
2. 최단 작업 우선 스케줄링, SJF (Shortest Job First)
- 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘
- 각 프로세스의 next CPU burst 길이를 고려
- 실제로는 프로세스의 CPU 실행 시간을 예측하는 것이 어렵다는 문제가 존재
- 긴 시간을 필요로 하는 프로세스가 우선순위가 계속 밀려 실행되지 못하고 무기한으로 대기하게 되는 기아(Starvation) 현상이 일어날 수 있음
- CPU가 이용 가능해지면, 가장 작은 next CPU burst를 가진 프로세스에 CPU를 할당
- 두 프로세스가 동일한 길이의 next CPU burst를 가지면, 선입 선처리 스케줄링을 적용
- SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가짐
- 실행하기 전 next CPU burst의 길이를 완벽하게 예측하기 어려움
- Next CPU Burst 예측
- 한계를 극복하고자 next CPU burst를 예측
- next CPU burst 길이의 근삿값을 계산
- 지수 평균한 것으로 근삿값을 계산
- 최소 잔여 시간 우선, STCF(shortest remaining time first)
- 만약 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU burst를 가지고 있다면 Context Switching 발생
3. 우선순위 (Priority)
- 각각의 프로세스에 우선순위 넘버가 있는 알고리즘
- CPU는 가장 높은 우선순위를 가진 프로세스에 할당
- SJF 알고리즘의 경우, 낮은 우선 순위의 프로세스가 절대 실행되지 않는 기아(Starvation) 문제가 발생할 수 있는데 이를 해결하기 위해서 노화(aging)를 사용할 수 있음
- 오래된 작업의 우선순위를 높여주는 식
- 기아 상태(Starvation) 또는 무한 봉쇄(indefinite blocking) 문제 발생
- 우선순위 스케줄링 알고리즘을 사용할 경우 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생
- 노화(Aging)로 해결
- 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가
선점형 스케줄링
- 현대 운영체제가 사용하고 있는 방식
- 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺏을 수 있는 방식
- 알고리즘에 따라 강제로 중단시키고 다른 프로세스에 CPU를 할당하는 방식
- 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 컨텍스트 스위칭으로 인해 오버헤드(Overhead)가 커질 수 있음
1.라운드 로빈 (RR, Round Robin)
- 현대 컴퓨터가 사용하는 우선순위 스케줄링
- 각각의 프로세스에 동일한 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용
- 할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어가므로 선점형 방식
- 시간 할당량(time quantum), 또는 타임슬라이스(time slice)라고 하는 작은 단위의 시간을 정의
- CPU 스케줄러는 준비 큐를 돌면서 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당
- CPU 버스트가 한 번의 시간 할당량을 초과하면, 프로세스는 선점되고 준비 큐로 되돌아감
- 시간 할당량(time quantum)의 크기에 매우 많은 영향을 받음
- 시간 할당량이 매우 크면, RR 알고리즘의 경우 선입 선처리 정책(FCFS)과 비슷해짐
- 한 프로세스가 지나치게 오랫동안 CPU를 점유
- 시간 할당량이 매우 적다면, RR 알고리즘은 매우 많은 Context Switching을 야기
- 실행 두 가지 경우
- 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작은 경우
- 프로세스 자신이 CPU를 자발적으로 방출할 것이다. 스케줄러는 그 후 준비 큐에 있는 다음 프로세스를 진행
- 현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴 경우
- 시간 할당량 이후에 interrupt 발생, Context Switching이 일어나고 실행하던 프로세스는 다시 준비 큐에 넣어진다. 그 후 스케줄러는 준비 큐의 다음 프로세스를 선택
2. SRF
- 실행되고 있는 프로세스는 중단 없이 끝까지 실행하는 비선점형 SJF와는 다르게, 선점형 SRJ에서는 현재 실행되고 있는 프로세스의 남은 시간보다 더 빨리 끝날 수 있는 짧은 프로세스가 들어오면 현재 실행되는 프로세스를 중단하고 짧은 프로세스를 실행하도록 바꿈
- SRTF(Shortest Remaining Time First)라고도 함
- 이 스케줄링은 평균 대기 시간을 줄일 수 있지만 역시 다음 프로세스의 CPU burst time을 예측하는 것이 어렵다는 문제가 존재
3. 다단계 큐 (Multilevel Queue)
- 우선순위에 따른 준비 큐가 여러 개의 큐들로 나뉘고 각각의 큐는 각자의 스케줄링 알고리즘
- 우선순위가 가장 높은 큐에서 프로세스를 스케줄함
- 준비 큐를 foreground와 background 큐로 나눌 수 있음
- 우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리가 안되는 기아(Starvation)현상이 나타날 수도 있으며, 각 큐 사이에서 프로세스들이 이동할 수 없어서 유연성이 떨어짐