[Computer Science][Operating System] CPU 스케줄링의 이해 🖥️

김상욱·2024년 8월 12일

CS OS Operating System computer science

CPU 스케줄링은 컴퓨터 시스템에서 프로세스를 효율적으로 할당하여 CPU 자원을 효과적으로 사용하는 방법을 다룹니다. 이 글에서는 CPU 스케줄링의 기본 개념과 다양한 알고리즘을 살펴보겠습니다.

1. 스케줄링

CPU를 효율적으로 사용하기 위해 프로세스를 적절히 배정하는 것이 중요합니다. 다음은 스케줄링의 기본 조건입니다:

오버헤드 낮게: 시스템 자원을 최소한으로 소모해야 합니다.
사용률 높게: CPU 사용률을 극대화해야 합니다.
기아 현상 낮게: 모든 프로세스가 공정하게 CPU를 사용할 수 있어야 합니다.

목표

Batch System: 가능한 많은 작업을 수행하고, 시간보다 처리량이 중요합니다.
Interactive System: 빠른 응답 시간과 적은 대기 시간을 추구합니다.
Real-time System: 기한을 맞추는 것이 핵심입니다.

2. 선점 / 비선점 스케줄링

선점(preemptive): 운영체제가 CPU 사용권을 강제로 회수할 수 있는 경우로, 처리 시간이 예측하기 어려운 작업에 적합합니다.
비선점(nonpreemptive): 프로세스가 종료되거나 I/O 등의 이벤트가 발생할 때까지 실행이 보장되는 경우로, 처리 시간이 예측하기 용이합니다.

3. 프로세스 상태

프로세스는 여러 상태를 거치며 전이됩니다:

New: 프로세스가 생성됩니다.
Ready: CPU 할당을 기다리는 상태입니다.
Running: CPU에서 실행 중인 상태입니다.
Terminated: 프로세스가 종료된 상태입니다.
Waiting: 특정 조건이 충족될 때까지 대기하는 상태입니다.

상태 전이

승인(Admitted): 프로세스가 생성 가능하여 승인됩니다.
스케줄러 디스패치(Scheduler Dispatch): 준비 상태의 프로세스 중 하나를 선택하여 실행합니다.
인터럽트(Interrupt): 예외 상황이 발생하여 현재 프로세스를 준비 상태로 변경합니다.
입출력 또는 이벤트 대기(I/O or Event Wait): 프로세스가 I/O 작업 등으로 대기 상태로 전환됩니다.
입출력 또는 이벤트 완료(I/O or Event Completion): 대기 중이던 작업이 완료되어 준비 상태로 돌아옵니다.

4. CPU 스케줄링의 종류

비선점 스케줄링

FCFS (First Come First Served): 큐에 도착한 순서대로 CPU를 할당합니다. 실행 시간이 짧은 작업이 뒤로 가면 평균 대기 시간이 길어지는 단점이 있습니다.
SJF (Shortest Job First): 수행 시간이 가장 짧은 작업을 먼저 수행합니다. FCFS보다 평균 대기 시간이 감소하지만 긴 작업은 지연될 수 있습니다.
HRN (Highest Response-ratio Next): 우선순위를 계산하여 점유 불평등을 보완하는 방법입니다. 우선순위는 (대기시간 + 실행시간) / 실행시간으로 계산하여, 대기 시간이 긴 프로세스에 우선권을 부여합니다.

선점 스케줄링

Priority Scheduling: 정적 또는 동적으로 우선순위를 부여하여 우선순위가 높은 프로세스부터 처리합니다. Starvation 문제를 해결하기 위해 Aging 기법을 사용할 수 있습니다. Aging은 우선순위가 낮은 프로세스가 일정 시간 동안 실행되지 않으면, 운영체제가 이 프로세스의 우선순위를 점진적으로 높이는 방법입니다.
Round Robin: FCFS에 의해 프로세스가 할당되면 각 프로세스는 동일한 시간의 Time Quantum만큼 CPU를 할당받습니다. 할당 시간이 크면 FCFS와 같아지고, 작으면 문맥 교환으로 오버헤드가 증가할 수 있습니다.
Multilevel-Queue: 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하여 우선순위가 낮은 큐들이 실행되지 못하는 것을 방지합니다. 각 큐마다 다른 Time Quantum을 설정하여 우선순위가 높은 큐는 작은 Time Quantum을, 우선순위가 낮은 큐는 큰 Time Quantum을 할당받습니다. 우선순위가 높은 큐가 짧은 시간 동안만 CPU를 사용하고 빠르게 반환하면 낮은 우선순위 큐에 있는 프로세스들이 CPU를 사용할 기회가 더 많아져 오랜시간 CPU를 할당받는 문제를 방지할 수 있습니다.
Multilevel-Feedback-Queue: 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 낮은 큐로 내려가고, 다 채우지 못한 프로세스는 원래 큐에 남습니다. Time Quantum을 다채우는 프로세스는 CPU-Bound 즉, CPU 사용량이 많은 프로세스일 가능성이 높기 때문에 작업이 지연될 수 있어서 낮은 큐로 내리고 반대로 다 채우지 못한 프로세스일 경우, I/O-Bound 프로세스로 판단되어 더 높은 우선순위를 부여 받아 빠르게 처리될 수 있게 합니다. 짧은 작업에 유리하며, 입출력 위주(Interrupt가 잦은)의 작업에 우선권을 부여하여 처리 완료 시간을 줄이는 데 기여합니다. 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround(처리 완료 시간) 평균 시간을 줄여줍니다.