CS/운영체제
[OS] CPU 스케줄링 알고리즘
yoon_seon
2023. 9. 8. 22:43
CPU 스케줄링 알고리즘
- 선입 선처리 스케줄링
- 최단 작업 우선 스케줄링
- 라운드 로빈 스케줄링
- 최소 잔여 시간 우선 스케줄링
- 우선순위 스케줄링
- 다단계 큐 스케줄링
- 다단계 피드백 큐 스케줄링
선입 선처리 스케줄링(FIFO)
- CPU를 먼저 요청한 프로세스부터 CPU 할당
- 준비큐에 삽입된 순서되로 처리되는 비선점형 스케줄링이다.
- 부작용으로 호위효과가 있다.
- 호위효과 : 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것
최단 작업 우선 스케줄링(SJF 스케줄링)
- 준비 큐 프로세스 중 CPU 이용시간이 짧은 프로세스부터 실행
- 호위효과를 방지할 수 있다.
라운드 로빈 스케줄링
- 선입 선처리 스케줄링에 타임 슬라이스가 지정되어있는 방식이다.
- 레디 큐에 삽입된 순서로 실행하되 타임 슬라이스만큼 실행되며 타임 슬라이스보다 긴 프로세스는 타임아웃으로 다시 준비상태가 된다.
- 선점형 스케줄링 방식이다.
최소 잔여 시간 우선 스케줄링(SRT 스케줄링)
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 작업 시간 짧은 프로세스부터 처리하되 타임슬라이스만큼 실행된다.
우선순위 스케줄링
- 프로세스마다 우선순위를 부여하며 우선순위가 높은순으로 실행되는 방식
- 최단 작업 우선 스케줄링는 작업 시간 짧은순으로 우선순위 부여한다고 볼 수 있고 최소 잔여 시간 스케줄링은 남은 시간 짧은 순으로 우선순위가 부여된다고 볼 수 있기 때문에 우선순위 스케줄링은 범용적이라고 볼 수 있다.
- 아사현상을 야기할 수 있다.
- 아사현상 : 우선순위가 높은 프로세스를 실행하느라 우선순위가 낮은 프로세스의 실행이 계속 연기되는 현상
- 예를들어 각 우선순위가 1 2 5 7 8 인 프로세스가 준비상태에 있을 때 갑자기 우선순위가 높은 프로세스가 준비큐에 들어온다면 뒤에있는 우선순위가 낮은 프로세스가 계속 연기된다.
- 아사현상을 해결하는 방법은 에이징 기법이다.
- 에이징 기법 : 대기시간이 점차 길어지면 우선순위를 높히는 방식
다단계 큐 스케줄링
- 우선순위별 준비 큐를 여러개 사용하는 방식
- 프로세스 유형별로 큐 구분 가능(CPU 바운드, I/O 바운드, 실시간 프로세스 등)
- 큐 별 다른 스케줄링 알고리즘 적용 가능
- 큐 별 다른 타임슬라이스 적용 가능
- 다단계 큐 스케줄링 방식은 프로세스가 큐 간의 이동이 불가능하기 때문에 아사현상을 야기할 수 있다. 이것을 방지하기 위해 다단계 피드백 큐 스케줄링 방식이 있다.
다단계 피드백 큐 스케줄링
- 프로세스가 큐 간의 이동 가능 및 에이징 기법 적용
- 정해진 타임슬라이스동안 실행이 끝나지 않으면 낮은 우선순위 큐로 이동한다. 이후 에이징 기법을 통해 우선순위가 높아지는 식으로 작동한다.
- CPU 바운드 프로세스는 CPU를 점유하는 시간이 길기 때문에 자연스럽게 우선순위가 내려간다. 반대로 I/O 바운드 프로세스는 높은 우선순위에서 끝난다. 그렇기 때문에 CPU 바운드, I/O 바운드 프로세스를 구분할 수 있다.