전 포스팅에서 스케줄러에 대해서 알아봤으니 CPU 스케줄러에 대해서 알아보도록 하자.
CPU 스케줄러
스케줄링 대상은 Ready Queue에 있는 프로세스들이다.
비선점형 스케줄러
FCFS (First Come Fisrt Served)
특징
- 먼저 온 순서대로 처리 (=FIFO)
- 일단 CPU를 잡으면 CPU Burst가 완료될 때 까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링이 이뤄지게 된다.
문제점
- Convoy Effect 소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.
SJF (Shortest Job Fisrt)
특징
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이뤄진다.
- CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식
문제점
- 기아 문제 발생
HRN (Highest Response Ratio Next)
특징
- SJF 스케줄링의 단점인 긴 작업과 짧은 작업 사이의 불평등을 보완하기 위한 방법임
- 우선순위 계산 공식
- (대기시간 + 서비스(실행)시간) / 서비스(실행)시간 = 시스템 응답 시간
- 위 공식에서 시스템 응답시간이 커질 수록 우선순위가 높아진다.
선점형 스케줄러
SRTF (Shortest Remaining Time Fisrt)
특징
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이뤄진다.
현재 수행중인 프로세스의 남은 burst time (실행 시간) 보다 더 짧은 CPU busrt time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏기게 된다.
문제점
- 기아문제
- 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU Busrt Time을 측정할 수 없다.
Round Robin
특징
- 현대적인 CPU 스케줄링
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
- 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
- RR은 CPU사용시간이 랜덤한 프로세스들이 섞여있을 경우 효율적임
- RR이 가능한 이유는 프로세스의 context를 save 할 수 있기 때문이다.
- Response time이 빠르다. n개의 프로세스가 ready queue에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간을 1/n을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
- 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다. 공정한 스케줄링임
주의점
설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작으면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch로 overhhead가 발생한다. 그렇기 때문에 적당한 time quantum 설정이 중요함.
Multilevel Feedback Queue
- 각 단계마다 하나의 큐를 두고, 큐 시간 할당량 내에 처리하지 못하면 다음 큐로 보내는 방식
- 단계가 커질수록 시간 할당량이 커지는 형식
Priority Scheduling
특징
- 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 우선순위랑 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
선점형일 경우
- 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다.
비선점형 일 경우 - 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head (큐의 앞)에 넣는다.
문제점
- 기아문제
- 무기한 봉쇄 (indefinite blocking) 실행 준비는 되어있으나 CPU를 사용못하는 프로세스를 CPU가 무기한 대기하는 상태
해결책
- aging 아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.
References
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main/OS#cpu-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%9F%AC
https://melonicedlatte.com/2022/04/30/162100.html
형이 먹여살릴게