CPU 스케줄링 알고리즘
책 『면접을 위한 CS 전공지식 노트』를 바탕으로 스터디를 진행하면서 공부한 내용을 정리했다.
~ 목차 ~
1. 스케줄링이란?
2. 스케줄링 알고리즘의 종류
2.1 비선점형 방식
2.1.1 FCFS
2.1.2 SJF
2.1.3 우선순위
2.2 선점형 방식
2.2.1 라운드 로빈
2.2.2 SRF
2.2.3 다단계 큐
1. CPU 스케줄링이란?
- 스케줄링(scheduling)은 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 것이다.
↳여기서는 CPU를 의미함
- 목적: 자원을 효율적으로 이용하고, CPU를 공정하게 사용할 수 있도록 한다.
- 스케줄링 방법에 따라서 시스템 성능이 달라진다.
(추구 방향: CPU이용률↑, 시간대비 일의 양↑, 준비큐에 있는 프로세스 개수↓, 응답 시간↓)
2. 스케줄링 알고리즘의 종류
- 스케줄링 알고리즘은 CPU를 뺏을 수 있는가에 따라서 비선점형 스케줄링과 선점형 스케줄링으로 나눠진다.
전체적인 작업방식과 장단점은 아래와 같다.
| 비선점형 스케줄링 | 선점형 스케줄링 | |
| 작업 방식 | 어떤 프로세스가 CPU를 점유하면 이를 다른 프로세스가 뺏을 수 없음 |
어떤 프로세스가 CPU를 점유하면 이를 다른 프로세스가 뺏을 수 있음 |
| 장점 | CPU 스케줄러의 작업량↓, 문맥 교환 오버헤드↓ (∵프로세스 강제 중지x) |
프로세스가 CPU를 독점할 수 없기 때문에 처리율↑ |
| 단점 | 기다리는 프로세스가 많기 때문에 처리율↓ | CPU 스케줄러의 작업량↑, 문맥 교환의 오버헤드↑(∵프로세스 강제 중지o) |
2.1 비선점형 스케줄링
2.1.1 FCFS
- FCFS는 First Come First Served의 약자로, 선입선출 스케줄링이라고도 한다.
- 준비 큐에 도착한 순서대로 CPU를 할당하는 방식이다.
- 장점
- 스케줄링의 이해와 구현이 단순하다.
- 단점
- 콘보이 효과(convoy effect)가 발생할 수 있다.
↳ 처리시간이 긴 프로세스가 CPU를 차지했을 때 다른 프로세스들이 하염없이 기다리게 되는 현상
→ 전체 효율성이 떨어짐
2.1.2 SJF
- SJF는 Shortest Job First의 약자로, 최단 프로세스 우선 스케줄링이라고도 한다.
- 준비 큐에 있는 프로세스 중에서 실행시간이 가장 짧은 작업부터 CPU를 할당하는 방식이다.
- 콘보이 효과를 완화해서 시스템의 효율성을 높인다.
- 장점
- 항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기시간이 가장 짧다.
- 단점
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
- 실행시간이 긴 작업이 실행되지 않는 아사(starvation)현상이 발생함
→ 해결방법: 에이징. 프로세스가 양보할 수 있는 상한선을 정하는 방식
2.1.3 우선순위
- 우선순위 스케줄링은 프로세스의 중요도에 따라서 우선순위를 메기고,
우선순위가 높은 프로세스에 먼저 CPU를 할당한다.
- 장점
- 각 프로세스의 상대적 중요성을 정확히 정의할 수 있다.
- 다양한 반응으로 실시간 시스템에 사용 가능하다.
- 단점
- 공평성을 위배하고 아사현상이 발생할 수 있다.
- 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생해서 시스템 효율성이 떨어진다.
2.2 선점형 스케줄링
2.2.1 라운드 로빈
- 라운드 로빈 스케줄링은 작은 단위의 시간인 규정 시간량을 정의한 뒤,
↳ 리눅스: 기본 100밀리초, 윈도우: 기본 20밀리초
할당받은 시간동안 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 기다리는 방식이다.
- 선점형 스케줄링 알고리즘 중 가장 단순하고 대표적인 방법이다.
- 장점
- 콘보이 효과가 완화된다.
- 프로세스의 최악의 응답시간을 알 수 있다.
- 단점
- 규정 시간량이 너무 길면 FCFS로 변하고, 너무 짧으면 문맥교환이 많이 일어나서 부담이 된다.
- 미완성 작업은 프로세서를 또 기다려야하므로 평균 처리 시간이 길어진다.
2.2.2 SRF
- SRF은 Shortest Remaining time First의 약자로, 남은 실행시간이 가장 짧은 작업부터 수행한다.
- 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행한다.
(cf. SJF는 수행하던 프로세스를 중지하지는 않음)
2.2.3 다단계 큐
- 다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다.
- 큐마다 다른 스케줄링 알고리즘을 적용할 수 있다.
- 메모리 크기나 프로세스의 형태에 따라 작업을 특정 큐에 지정한다.
- 장점
- 응답이 빠르다.
- 단점
- 준비 큐가 여러 개이기 때문에 추가 오버헤드가 발생한다.
- 우선순위가 낮은 큐의 프로세스는 무한정 대기하는 아사 현상이 발생할 수 있다.
참고문헌
[1] 주홍철, 면접을 위한 CS 전공지식 노트, 서울: 길벗, 2022.
[2] 구현회, 그림으로 배우는 구조와 원리, 개정 3판, 서울: 한빛아카데미, 2018.
[3] 조성호, 쉽게 배우는 운영체제, 2판, 서울: 한빛아카데미, 2023.
'CS' 카테고리의 다른 글
| [자료구조] 비선형 자료구조(힙, 우선순위 큐, 맵, 셋, 해시테이블) (0) | 2024.12.17 |
|---|---|
| [데이터베이스] 인덱스 (1) | 2024.11.26 |
| [네트워크] IP주소 (1) | 2024.11.11 |
| [운영체제] 프로세스 (1) | 2024.11.05 |