✔️ CPU 스케줄링
CPU 스케줄링이란?
- CPU를 잘 사용하기 위해 프로세스를 배정하는 것으로 오버헤드와 기아 현상을 줄이고, 사용률을 높임
- CPU 스케줄링의 척도로는
작업이 처음 실행되기까지 걸린 시간인 응답 시간과
실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때까지 걸린 시간인 반환 시간이 존재
- CPU 스케줄링에는 3가지 목표가 존재
- Batch System : 가능한 많은 일(높은 처리량)을 수행해야 함
- Interactive System : 빠른 응답 시간, 적은 대기 시간을 가져야 함
- Real-time System : 기한을 맞춰야 함
프로세스 상태 전이
스케줄링의 대상은 Ready Queue에 있는 프로세스들
- 승인 (Admitted) : New → Ready
프로세스 생성(New)이 가능하여 승인
- 스케줄러 디스패치 (Scheduler Dispatch) : Ready → Running
준비 상태에 있는 프로세스 중 하나를 선택하여 실행
- 인터럽트 (Interrupt) : Running → Ready
예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리
- 입출력 또는 이벤트 대기 (I/O or Event wait) : Running → Waiting
실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것
- 입출력 또는 이벤트 완료 (I/O or Event Completion) : Waiting → Ready
입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것
- 선점 스케줄링은 Interrupt, I/O or Event Completion, I/O or Event Wait, Exit가 발생
비선점 스케줄링은 I/O or Event Wait, Exit가 발생
CPU 스케줄링의 종류
- OS가 CPU의 사용권을 강제 회수할 수 있는 선점 스케줄링은 처리 시간 예측이 어려움
- SRTF (Shortest Remaining Time First)
새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어지며
현재 수행 중인 프로세스의 남은 수행 시간보다 더 짧은 수행 시간을 가지는 작업이 있다면 CPU응 뺏기게 됨
- Priority Scheduling
정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리하며 우선순위가 낮은 작업은 기아 상태에 빠질 수 있음
- Round Robin
FCFS에 의해 작업들이 보내지면 각 작업은 동일한 시간의 시간 할당량만큼 CPU를 할당 받게 됨
할당 시간이 크면 FCFS와 같게 되고 작으면 문맥 교환이 잦아져서 오버헤드가 증가하게 됨
- Mutilevel-Queue
작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 방법
우선순위가 낮은 큐들이 기아 상태에 빠지는 것을 방지하기 위해 각 큐마다 다른 시간 할당량을 설정
- Multilevel-Feedback-Queue
Multilevel-Queue에서 자신의 시간 할당량을 다 채운 작업은 밑으로 내려가고
자신의 시간 할당량을 다 채우지 못한 작업은 원래 큐에 그대로 두도록 함
Mutilevel-Queue
Multilevel-Feedback-Queue
- 프로세스 종료 또는 I/O 등의 이벤트가 있을 때까지 실행을 보장하는 비선점 스케줄링은 처리시간 예측이 용이함
- FCFS (First Come First Served)
큐에 도착한 순서대로 CPU를 할당하며 실행 시간이 짧은 작업이 나중에 도착할 경우 대기 시간이 길어짐
- SJF (Shortest Job First)
수행 시간이 가장 짧다고 판단되는 작업을 먼저 수행하며 FCFS보다 평균 대기 시간이 감소하며 짧은 작업에 유리함
- HRN (Hightest Response-ratio Next)
'(대기 시간 + 실행 시간) / 실행 시간'을 통해 우선순위를 계산하여 점유 불평등을 보완
