CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. 이 때 어떤 프로그램에 CPU 소유권을 줄 것인지 결정하는 것이 바로 CPU 스케줄링 알고리즘이다.
CPU 스케줄링 알고리즘은 다음과 같이 나눌 수 있다.
Non Preemptive (비선점형)
비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식으로 강제로 프로세스를 중지하지 않는다.
- FCFS (First Come First Served)
- 큐에 가장 먼저 도착한 순서대로 CPU 할당
- 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐으로 준비 큐에서 오래 기다리는 현상인 'Convoy Effect' 가 발생한다
- SJF (Shortest Job First)
- 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
- 수행시간이 긴 프로세스가 실행되지 않는 'Starvation' 이 발생한다.
- FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
- 실제 실행 시간은 알 수 없음
- HRN (Hightest Response-ratio Next)
- 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 Starvation 해결)
- 우선순위 = (대기시간 + 실행시간) / (실행시간)
- 오래된 작업일수록 우선순위를 높이는 방법인 'Aging'을 통해 단점 보완
Preemptive (선점형)
선점형 방식은 현대 운영체제가 쓰는 방식으로 현재 프로세스를 중단시키고 다른 프로세스에 CPU 소유권을 할당하는 방식을 말한다.
- Round Robin
- 우선순위 스케줄링의 일종으로 동일한 시간을 주고 시간안에 해결되지 않으면 다시 준비 큐의 뒤로가는 알고리즘
- FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할당 받음
- Time Quantum or Time Slice : 실행의 최소 단위 시간
- 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가
- SRF (Shortest Remaining Time First
- SJF의 선점형 스케줄링 방식
- 남은 프로세스의 작업보다 더 짧은 작업이 들어오면 프로세스를 중지하고 해당 프로세스를 수행
- Multilevel-Queue (다단계 큐)
- 우선순위에 따른 준비 큐를 여러개 사용하고 각 큐마타 RR이나 FCFS등 여러 스케줄링 알고리즘을 적용
- 우선순위가 낮은 큐들이 실행 못하는 것을 방지하고자 각 큐마가 다른 시간을 할당
'개발자의 기본 소양 > OPERATING SYSTEM' 카테고리의 다른 글
PCB (Process Control Block, 프로세스 제어 블록) (0) | 2023.06.28 |
---|---|
운영체제(4) - DeadLock (교착 상태) (0) | 2023.05.30 |
운영체제(3) - 공유 자원과 임계 영역 (0) | 2023.05.29 |
운영체제(2) - 프로세스와 스레드 (0) | 2023.01.05 |
운영체제(1) - 시작하기 (0) | 2022.12.28 |