[Operating System] - 8. CPU Scheduling

우리누리·2024년 5월 19일

👓 Operating System

(본 글은 다음 링크를 참조하였습니다.)
https://github.com/gyoogle/tech-interview-for-developer?tab=readme-ov-file

CPU Scheduling이란?

CPU가 하나의 프로세스 작업을 끝내면, 다음 프로세스 작업을 수행해야 한다. 이 때 다음 프로세스를 선택하는 알고리즘을 CPU Scheduling이라고 한다.

즉, 운영체제가 프로세스에 합리적으로 CPU 자원을 할당하는 정책을 만드는 것

프로세스 상태

(출처 : https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/CPU%20Scheduling.md)

승인 (Admitted) : 프로세스 생성이 가능하여 승인됨
스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것
인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것
입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우,입출력/이벤트가 모두 끝날 때 까지 대기 상태로 만드는 것
입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스가 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것
선점형 : Interrupt, I/O or Event Completion, I/O or Event Wait, Exit
비선점형 : I/O or Event Wait, Exit

CPU 스케줄링의 종류 (비선점형 vs 선점형)

비선점형

FCFS (First Come First Served) (FIFO)
- 큐에 도착한 순서대로 CPU 할당
- 실행 시간이 짧은게 뒤로 가면 평균 대기 시간이 길어진다.
SJF (Shortest Job First)
- 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
- FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리
HRN (Highest Response-ratio Next)
- 우선순위를 계산하여 점유 불평등을 보완한 방법 (SJF의 단점 보완)
- 우선순위 = (대기시간 + 실행시간) / (실행시간)

비선점형 정리

FCFS는 실행 시간이 짧은게 뒤로 가면 평균 대기 시간이 길어지는 문제가 발생한다.
FCFS를 보완하기 위해, SJF을 사용 -> 수행시간이 짧은 것부터 처리 가능! 그러나 점유 불평등이 발생함 (짧은 것만 우선처리 하기 때문)
SJF를 보완하기 위해 우선순위를 계산하여 점유 불평등을 개선함 -> HRN 기법

선점형

Priority Scheduling
- 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
- 우선순위가 낮은 프로세스가 무한정 기다리는 기아(Starvation) 현상이 발생할 수 있음
- 이를 위해, Aging 방법으로 기아 현상을 해결 가능
- Aging : 자원을 기다리는 시간에 비례하여 우선순위를 부여하는 기법
  -> 10번이나 기다렸어? 너 내가 지금 처리해줄게!
Round Robin (RR)
- 프로세스들 사이에 우선순위를 두지 않는 기법
- 순서대로 시간단위로 CPU를 할당하는 방식
- FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum만큼 CPU를 할당 받는다.
- 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환(Context Switching)이 잦아져서 오버헤드가 증가하는 문제가 있음
Multilevel - Queue (다단계 큐)
- 작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법
- 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정해주는 방식
- 우선순위가 높은 큐는 작은 Time Quantum할당, 우선순위가 작은 큐는 높은 Time Quantum 할당
(출처 : https://m.blog.naver.com/jk130694/220691932450)

프로세스가 도착하면 역할에 따라 각 큐로 배정된다.
하지만, 분명 우선순위가 낮아 하염없이 기다리는 작업이 존재한다. 이 때, Time Quantum을 큐마다 다르게 부여하여 우선순위가 낮은 큐들에게 처리 시간을 더 많이 줌으로써 해결한다.
Multilevel-Feedback-Queue (다단계 피드백 큐)
- 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로 남는 기법
- 짧은 작업에 유리, 입출력 위주 (Interrupt가 잦은) 작업에 우선권을 줌
- 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌
  
  (출처 : https://taegyunwoo.github.io/os/OS_MultiLayerQueue_MultiProcessor_RealtimeSystem)

선점형 정리

우선순위 스케줄링을 쓰다보니 기아 현상이 발생 (물론 Aging 기법으로 해결 가능함) -> 모두에게 CPU를 돌려가며 쓰도록 해야겠다.
우선순위 스케줄링 단점 보완을 위한 Round Robin 기법 -> Time Quantum이 크면 FCFS와 같고, 작으면 문맥 교환이 잦아져 오버헤드 증가
RR 단점 보완을 위한 다단계 큐 기법 -> 우선순위가 있는 여러개의 큐를 사용 -> 우선순위와 Time Quantum을 반비례하게 사용 -> 조금 더 보완할 방법이 없을까?
다단계 피드백 큐 기법 -> 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 다음 큐로 이동, 그렇지 않으면 기존 큐 그대로 -> 맨 마지막 FCFS로 이동 후 프로세스 끝까지 처리