일전에도 정리했었지만 우리의 CPU(중앙처리장치)는 프로세스를 하나씩 처리한다.
동시에 처리하는 것 같아보이지만,
실제로는 아주 빠른 속도로 특정 속도 별로 작업을 하기 때문에 동시에 일어나는 것처럼 보이는 것이다.
그러면 이런 실행 순서에 대한 할당은 어떻게 결정하는 것인지 알아보자.
CPU 스케줄링이란?
CPU 스케줄링은 운영체제(OS) 의 핵심 기능 중 하나로,
한정된 CPU 자원을 시스템 내의 여러 프로세스(또는 스레드) 들에게 공정하고 효율적으로 할당하는 정책 및 과정이다.
이때 CPU 스케줄링은 실행 대기 중인 프로세스(준비 큐, Ready Queue) 중에서 다음에 어떤 프로세스에게 CPU를 할당할지를 결정한다.
목적
앞서 언급했듯이 여러 프로세스들이 돌아가기 위해선 공정하고 효율적으로 할당하는 과정이 CPU 스케줄링으로, 최종적인 목적은 CPU 스케줄링은 시스템의 성능을 최적화하는 것 이다.
그렇다면 어떤 것을 기준으로 성능 최적화를 판단할까?
다음을 기준으로 성능 최적화에 대하여 판단한다.
스케줄링을 통하여 늘려야하는 것들
- CPU 이용률 (CPU Utilization) 증대: CPU가 쉬지 않고 최대한 많이 일하도록 하여 시스템 효율을 높이는 것으로, 이용률이 늘면 최적화이다.
- 처리량 (Throughput) 증대: 단위 시간당 완료되는 프로세스의 수가 최대일수록 좋다.
스케줄링을 통하여 줄여야하는 것들
- 대기 시간 (Waiting Time) 최소화: 프로세스가 준비 큐에서 기다리는 시간을 최소화한다. Waiting Time = TurnaroundTime - Burst Time 으로 계산한다
- 응답 시간 (Response Time) 최소화: 요청 후 첫 번째 응답이 나올 때까지의 시간을 줄여 사용자 체감 속도를 개선한다. Response Time = CPU Allocation Time(when the CPU was allocated for the first) - Arrival Time 으로 계산한다.
- 소요 시간 (Turnaround Time) 최소화: 프로세스가 시스템에 들어와서 완료될 때까지 걸리는 총 시간을 줄인다.
위의 요소들을 종합적을 고려하여 최적화에 대한 판도를 내린다.
종류
스케줄링이 이루어지는 시점과 역할에 따라서 스케줄러에 대하여 3가지로 나눌 수 있다.
- 장기 스케줄러 (Long-Term Scheduler) ( = 작업 스케줄러(Job Scheduler))
어떤 프로세스를 시스템에 받아들여 준비 큐에 넣을지 결정하여 시스템 내의 프로세스 수(다중 프로그래밍 정도)를 조절한다.
실행 빈도는 적고 느리다.
2. 중기 스케줄러 (Medium-Term Scheduler) (중단/재개 스케줄러)
메모리 관리를 위해 시스템 과부하 시 프로세스를 일시적으로 메모리에서 디스크로 내보내거나 (Swap Out), 다시 메모리로 불러들이는 (Swap In) 작업을 결정해준다.
실행 빈도는 중간
3. 단기 스케줄러 (Short-Term Scheduler)
준비 큐에 있는 프로세스 중 다음에 CPU를 사용할 프로세스를 선택하고 CPU를 할당하는 작업을 한다.
매우 잦고 빠름
CPU 스케줄링 알고리즘의 분류
CPU 스케줄링 알고리즘은 CPU를 할당받은 프로세스가 작업 도중에 "CPU를 강제로 빼앗길 수 있는지 여부" 에 따라 선점형과 비선점형으로 나뉜다.
위의 사진대로 비선점형 스케줄링의 경우에는 하나의 프로세스가 진행중일 때에는 Interrupt 되고, 이에 대하여 고정 할당에 대해 지나면 다른 프로세스로 스위치되는 형식을 보이고 있다.
반면 선점형 스케줄링의 경우, 고정 할당이 존재하지 않고 스위칭되고 있음을 확인할 수 있다.
비선점형 스케줄링 (Non-Preemptive Scheduling)
우선은 CPU를 강제로 빼앗을 수 없는 비선점형에 대하여 알아보자.
한 프로세스가 CPU를 할당받으면 작업이 완료되거나 스스로 대기 상태로 전환될 때까지 CPU를 점유하며, 다른 프로세스가 중간에 CPU를 빼앗을 수 없다.
오버헤드가 적지만, 중요한 작업이 긴 작업 뒤에 대기해야 하는 문제가 발생할 수 있다.
1. FCFS (First-Come, First-Served)
준비 큐에 도착한 순서대로 CPU를 할당 (FIFO)한다. 도착 순이기에 구현이 가장 간단하다.
긴 프로세스가 먼저 도착하면 뒤의 짧은 프로세스들이 오래 기다리는 호위 효과(Convoy Effect) 발생 가능하다.
위의 사진 속 예시를 보면, Arrival Time을 통하여 프로세스에 대한 순서를 할당한 것을 확인 가능하다.
도착 순서가 가장 빠른 PID 3에 대하여 가장 먼저 스케줄링을 분배하고 나머지도 도착 순서에 따라서 할당하는 것을 확인할 수 있다.
2. SJF (Shortest-Job-First)
CPU 사용 시간이 가장 짧은 프로세스에게 CPU를 할당한다. 짧은 애들 순으로 돌리기 때문에 평균 대기 시간이 가장 짧은 최적의 알고리즘이다.
그러나 실제 사용 시간을 예측하기 어렵고, 긴 프로세스가 영원히 실행되지 못하는 기아 현상(Starvation) 발생 가능하다. (짧은 애들 위주로 처리되기 때문)
위의 사진의 경우에는 도착 시간이 가장 빠른 PID 3 이후에는 , Burst Time을 기준으로 가장 짧은 프로세스를 제일 먼저 실행하는 것이다.
3. 우선순위 스케줄링 (Priority Scheduling)
가장 높은 우선순위를 가진 프로세스에게 CPU를 할당하는 방법이다.
우선순위가 낮은 프로세스가 무한정 대기하는 기아 현상 발생 가능하다는 단점이 존재하지만,
에이징(Aging) 기법으로 해결 시도 (오래 기다린 프로세스의 우선순위를 점차 높여줌) 가능하다.
선점형 스케줄링 (Preemptive Scheduling)
한 프로세스가 CPU를 사용 중이라도, 우선순위가 더 높은 프로세스가 도착하거나 할당된 시간(Time Quantum)이 만료되면 현재 프로세스의 CPU 사용을 중단시키고 CPU를 빼앗아 다른 프로세스에게 할당할 수 있다.
반응 시간이 중요한 대화형 시스템이나 실시간 시스템에 적합하다.
1. 라운드 로빈 (Round Robin, RR)
FCFS에 시간 할당량(Time Slice 또는 Time Quantum) 개념을 추가한 알고리즘이다.
프로세스는 할당 시간 동안만 CPU를 사용하고, 끝나지 않으면 준비 큐 맨 뒤로 돌아간다. (대기열에 등록)
시분할 시스템에 적합하고 공평성이 높다.
그러나 할당 시간이 너무 길면 FCFS와 유사해지고, 너무 짧으면 잦은 컨텍스트 스위칭으로 인한 오버헤드가 커진다.
위의 사진으로 예시를 들면, 기존의 비선점형과 동일한 도착 및 소요 시간이어도,
일정한 시간할당량을 기준으로 프로세스를 처리중인 것을 확인 할 수 있다.
2. SRTF (Shortest-Remaining-Time-First)
SJF를 선점형으로 바꾼 것이다(점유 금지)
현재 실행 중인 프로세스의 남은 시간보다 더 짧은 남은 시간을 가진 새 프로세스가 도착하면 CPU를 빼앗는 형식으로 유동적이다.
SJF와 마찬가지로 평균 대기 시간이 가장 짧습니다.
그러나 새로운 프로세스가 도착할 때마다 남은 시간을 비교해야 하므로 오버헤드가 발생할 수 있다.
3. 다단계 큐 (Multi-Level Queue)
프로세스를 특성에 따라 여러 개의 준비 큐로 나누고, 각 큐마다 다른 스케줄링 알고리즘을 적용한다.
각 큐 사이에는 고정된 우선순위가 있어, 상위 큐가 비어야 하위 큐가 실행되어야한다.
큐 간의 프로세스 이동은 불가능하다.
4. 다단계 피드백 큐 (Multi-Level Feedback Queue, MLFQ)
다단계 큐의 문제점을 개선하여, 프로세스가 큐 간에 이동할 수 있게 한 것이다.
CPU를 너무 오래 사용한 프로세스는 낮은 우선순위 큐로 이동하고, 낮은 큐에서 오래 대기한 프로세스는 높은 큐로 이동시켜 기아 현상을 방지한다 (에이징).
현대 운영체제에서 가장 일반적인 스케줄링 방식이다.
REF
'CS > 운영체제' 카테고리의 다른 글
| [CS/운영체제] 뮤텍스와 세마포어 (0) | 2025.10.28 |
|---|---|
| [CS/운영체제] 프로세스 관리와 통신 (1) | 2025.10.14 |
| [CS/네트워크] 운영체제의 기초 (6) | 2025.10.01 |