1. CPU 스케줄링의 이해

1-1. 스케줄링 (Scheduling)

운영체제가 프로세스나 스레드에 할당할 시스템 자원의 사용 순서와 방법을 결정하는 과정

이는 한정된 자원을 효율적으로 관리하여 시스템 서능을 최적화하는 데 핵심적인 역할을

스케줄링의 목적

1. 효율성 극대화 (Efficiency)

• CPU 이용률 최대화 (Maximize CPU Utilization)
  CPU가 최대한 많은 시간 동안 작업을 처리하도록 유지하는 것이 중요한 목표
  CPU가 유휴(Idle) 상태에 있는 시간을 최소화하여 낭비를 줄임

1. 성능 향상 (Performance)

• 처리량 최대화림
  단위 시간당 완료되는 작업(프로세스)의 수를 최대로 늘림
• 응답 시간 최소화
  특히 대화형 시스템(Interactive System)에서, 사용자의 요청(키보드 입력 등)이 들어온 시점부터 첫 번째 응답이 출력될 때까지 걸리는 시간을 최소화함
  사용자가 체감하는 시스템의 반응 속도를 개선

1. 공정성 및 예측 가능 (Fairness & Predictability)

• 대기 시간 & 반환 시간최소화
• 프로세스가 준비(Ready) 상태 큐에서 CPU를 할당받기 위해 기다리는 총 시간 (대기시간)
  프로세스가 시스템에 진입하여 종료될 때까지 걸리는 총 시간 (반환시간)을 최소화
  → 작업의 완료 시간을 예측 가능하게 함
• 균형있는 자원 사용 모든 프로세스가 CPU를 공평하게 할당받도록 보장하여, 특정 프로세스만 무한정 기다리는 기아 현상 (Starvation)이 발생하지 않도록 해야 함

스케줄링의 필요성

스케줄링은 현대 운영체제가 멀티태스킹 환경을 효과적으로 구현하기 위한 근본적인 해결책임

1. 멀티프로그래밍 구현 (Implementing Multiprogramming): CPU 유휴 시간 감소
2. 사용자 경험 개선 (Improving User Experience): 빠른 응답성 보장 (시분할, Time-sharing 효과)
3. 시스템 자원 효율적 관리 (Efficient Resource Management): 병목 현상 해소

1-2. CPU-버스트(CPU-Burst)와 I/O-버스트(I/O-Burst) 사이클

대부분의 프로세스는 실행되는 동안 CPU를 사용하는 시간과 입출력(I/O) 작업을 위해 대기하는 시간을 번갈아 가며 반복하는데, 이러한 프로세스의 특성을 설명하는 것이 바로 CPU-I/O 버스트 사이클

CPU-버스트 (CPU Burst)

• 정의:
  프로세스가 CPU를 사용하여 명령을 실행하는 시간
  계산 작업을 수행하거나 코드의 논리적인 처리가 일어나는 구간
• 특징:
  이 기간 동안 프로세스는 실행(Running) 상태에 있음
  버스트의 길이는 프로세스의 특성이나 현재 실행 중인 코드에 따라 다름

I/O-버스트 (I/O Burst)

• 정의:
  프로세스가 입출력(I/O) 작업을 요청한 후, I/O 작업이 완료될 때까지 대기하는 시간
  디스크 읽기/쓰기, 네트워크 통신, 사용자 입력 대기 등이 여기에 해당됨
• 특징:
  이 기간 동안 프로세스는 대기(Waiting/Blocked) 상태로 전환되며,
  CPU는 다른 프로세스에게 할당되어 유휴(Idle) 상태가 되는 것을 방지

CPU-I/O 버스트 사이클 (The Cycle)

프로세스는 시스템에서 실행을 완료할 때까지 CPU-버스트와 I/O-버스트를 번갈아 가며 반복하는 라이프사이클을 가짐
CPU-버스트→I/O-버스트→CPU-버스트→I/O-버스트→⋯→최종 CPU-버스트→종료

1. 시작
   프로세스는 보통 CPU-버스트로 시작
2. I/O 요청
   CPU-버스트가 끝나면, 프로세스는 I/O 작업을 수행하기 위해 운영체제에 I/O 요청
3. 대기
   I/O 요청 후 I/O-버스트 구간 동안 프로세스는 I/O 작업이 완료될 때까지 대기
4. CPU 재요청
   I/O 작업이 완료되면, 프로세스는 다시 CPU를 할당받기 위해 준비(Ready) 큐로 이동하여 다음 CPU-버스트를 기다림
5. 종료
   프로세스의 마지막 작업은 I/O 요청이 없는 최종 CPU-버스트로 끝나며, 그 후 시스템을 떠나게 됨

버스트 분포와 스케줄링

운영체제는 프로세스의 버스트 길이 분포(CPU-Burst length distribution)를 주요하게 고려하여 가장 효율적인 CPU 스케줄링 알고리즘을 선택하거나 설계

[버스트 길이 분포]

• 일반적으로 대부분의 프로세스는 짧은 CPU 버스트를 가짐
  매우 긴 CPU 버스트를 가지는 경우는 적음
  이러한 분포는 통계적으로 지수 분포와 유사하게 나타남
• I/O-바운드 프로세스 (I/O-Bound Process)
  I/O-버스트 시간이 CPU-버스트 시간보다 훨씬 긴 프로세스
  이들은 짧게 CPU를 사용한 후 바로 I/O 대기에 들어감
  e.g. 워드 프로세서, 웹 서버
• CPU-바운드 프로세스 (CPU-Bound Process)
  CPU-버스트 시간이 I/O-버스트 시간보다 훨씬 긴 프로세스
  이들은 한 번 CPU를 잡으면 오랫동안 놓지 않음
  e.g. 복잡한 계산 프로그램, 대용량 파일 압축

1. 짧은 버스트를 위한 최적화 (대부분의 경우)

앞서 설명했듯이, 대부분의 프로세스는 짧은 CPU 버스트를 가집니다 (I/O-바운드 프로세스). 이러한 분포적 특징을 기반으로 설계된 알고리즘은 시스템의 응답 시간과 처리량을 크게 개선합니다.

• 선택되는 알고리즘: SJF (Shortest-Job-First) 또는 그 선점형 버전인 SRTF (Shortest-Remaining-Time-First)가 이론적으로는 평균 대기 시간을 가장 최소화하는 최적의 알고리즘으로 간주됩니다.
• 실제 적용: SJF/SRTF는 미래를 정확히 예측할 수 없으므로, 운영체제는 프로세스의 과거 CPU 버스트 길이를 측정하여 다음 버스트 길이를 예측하는 방식으로 유사한 효과를 얻으려 합니다.
  

2. 긴 버스트를 위한 공정성 보장

매우 긴 CPU 버스트를 가진 프로세스(CPU-바운드 프로세스)가 CPU를 독점하면, 뒤에 있는 짧은 버스트 프로세스들이 너무 오래 기다리는 기아 현상(Starvation)이나 호위 효과(Convoy Effect)가 발생할 수 있습니다.

• 선택되는 알고리즘: 라운드 로빈 (Round Robin, RR) 알고리즘이 효과적입니다. RR은 긴 작업도 짧게 끊어 공평하게 CPU 시간을 할당하여, 대화형 시스템의 응답성을 보장하고 공정성을 유지합니다.
• 복합적 접근: 현대 OS는 단순히 하나의 알고리즘만 쓰기보다는, 다단계 피드백 큐 (MLFQ)처럼 여러 개의 큐를 두고 각 큐에서 다른 스케줄링 알고리즘(예: 짧은 큐에서는 RR, 긴 큐에서는 FCFS)을 적용하여 짧은 작업에 우선권을 주면서 긴 작업의 공정성도 확보하는 복합적인 방식을 사용합니다. 결론적으로, 운영체제는 프로세스의 버스트 분포가 '짧은 버스트가 많다'는 통계적 경향을 바탕으로 짧은 작업을 우선 처리하는 쪽으로 알고리즘을 설계하고 선택합니다.
  

1-3. 스케줄링의 주체와 시점

스케줄링은 운영체제가 CPU를 어떤 프로세스에 할당할지 결정하는 행위

스케줄링의 주체는 이 결정을 수행하는 존재

스케줄러의 주체

프로세스의 수명 주기 중 어느 단계에 관여하느냐에 따라 3가지로 나뉨

스케줄러	역할	관여하는 프로세스 상태
장기 스케줄러 (Long-Term Scheduler)	작업 승인 (Job Admission) — 어떤 프로세스를 메모리에 올릴지 결정	디스크의 작업 큐 → 메모리의 준비(Ready) 큐
중기 스케줄러 (Medium-Term Scheduler)	스와핑 (Swapping) — 메모리 부족 시 프로세스를 디스크로 내보내거나 다시 불러옴	메모리 ⇌ 디스크 (일시 중단/재개)
단기 스케줄러 (Short-Term Scheduler)	CPU 할당 (CPU Dispatch) — 준비 큐에서 어떤 프로세스를 CPU에 보낼지 결정	메모리의 준비(Ready) 큐 → CPU (실행)

1. 단기 스케줄러 (CPU Scheduler)

• 가장 빈번하게 실행되며, 시스템 성능에 직접적인 영향을 미침
• 준비 상태 큐에 있는 프로세스들 중 어떤 프로세스에게 당장 다음 CPU를 할당할지 결정하고 CPU를 넘겨줌
  e.g. FCFS, RR, SJF

1. 중기 스케줄러 (Swapper)

• 메모리 효율성 및 시스템 부하를 관리함
• 너무 많은 프로세스가 메모리에 있어 과부하(Thrashing)가 걸릴 경우,
  일부 프로세스를 메모리에서 디스크의 스왑 영역으로 쫓아내고 (Swap Out),
  나중에 다시 메모리로 불러와 (Swap In) 중단된 지점부터 실행을 재개시킴

1. 장기 스케줄러 (Job Scheduler)

• 시스템의 다중 프로그래밍 수준을 조절
• 디스크에 저장된 작업 중 어떤 것을 선택하여 메모리로 불러와 (레디 큐)프로세스로 만들지 결정함
  시스템이 얼마나 많은 프로세스를 동시에 처리할지 제어

CPU 스케줄링이 발생하는 네 가지 상황

발생 시점	설명	선점 여부
프로세스가 실행 상태에서 → 대기 상태(Waiting) 로 전환될 때	I/O 요청, 이벤트 대기 등으로 CPU를 놓음	비선점
프로세스가 실행 상태에서 → 준비 상태(Ready) 로 전환될 때	타이머 인터럽트, 우선순위 높은 프로세스 등장 등	선점
프로세스가 대기 상태에서 → 준비 상태(Ready) 로 전환될 때	I/O 완료 등으로 다시 실행 가능한 상태로 변함	선점 가능
프로세스가 종료(Terminated) 될 때	CPU가 완전히 해제됨	비선점

1-4. 스케줄링 방식

구분	설명	예시
비선점형 (Non-preemptive)	한 프로세스가 CPU를 얻으면 자발적으로 반납할 때까지 빼앗지 않음	FCFS, SJF, 우선순위(비선점형), HRN
선점형 (Preemptive)	운영체제가 CPU를 강제로 회수 가능	RR, SRTF, 우선순위(선점형), Multilevel Queue

CPU를 이미 할당받아 실행 중인 프로세스로부터 CPU를 빼앗을 수 있는지 여부에 따라 크게 두 가지로 나뉨

선점형(Preemptive) 스케줄링

실행 중인 프로세스라도 강제로 CPU를 빼앗을 수 있는 방식

운영체제는 다음 두 가지 상황에서 현재 실행 중인 프로세스를 중단시키고 다른 프로세스에게 CPU를 할당할 수 있음

1. 새로운 프로세스가 도착했는데, 이 프로세스가 현재 실행 중인 프로세스보다 우선순위가 더 높을 때
2. 시간 할당량 (Time QUantum)이 만료되었을 때 (Round-Robin)
3. 프로세스가 대기 상태에서 준비 상태로 복귀했을 때, 이 프로세스의 우선순위가 더 높을 경우

[장점]

• 응답 시간이 빠름
  중요한 작업이나 대화형 작업이 즉시 CPU를 할당받아 처리될 수 있음
• 공정성 보장
  모든 프로세스에 cpu 시간을 공평하게 나누어 줄 수 있음

[단점]

• 문맥 교환 오버헤드가 큼
  빈번하게 프로세스가 중단되고 재개되면서 발생하는 오버헤드가 시스템 성능에 영향을 줄 수 있음
• 공유 데이터에 대한 동기화 문제가 복잡해짐
  언제든지 프로세스가 중단될 수 있으므로, 커널 데이터의 일관성을 유지하기 위해 엄격한 동기화 매커니즘이 필수적임

[대표적인 알고리즘]

• 라운드 로빈 (RR, Round Robin)
  정해진 시간 할당량마다 CPU를 강제로 빼앗아 다음 프로세스에게 할당함
• SRTF (Shortest-Remaining-Time-First)
  남으 실행 시간이 가장 짧은 프로세스가 도착하면 현재 프로세스를 중단시키고 CPU를 선점함
• 우선순위 스케줄링(Priority Scheduling)
  더 높은 우선순위의 프로세스가 도착하며 CPU를 선점함

비선점형(Non-Preemptive) 스케줄링

프로세스가 자발적으로 CPU를 반납할 때까지 CPU를 계속 점유하는 방식

일단 CPU를 할당받으면 해당 프로세스는 다음 중 하나의 상황이 될 때까지 CPU를 독점적으로 사용함

1. 프로세스가 종료될 때
2. 프로세스가 I/O 요청등으로 대기(Waiting/BLocked) 상태로 전환될 때

[장점]

• 문맥 교환 오버헤드가 적음
  실행중인 프로세스가 자주 중단되지 않으므로 OS가 프로세스의 상태를 저장하고 복원하는 작업이 줄어듦
• 커널 데이터에 대한 경쟁 상태 (Race Condition) 문제가 적음
  프로세스가 CPU를 사용하는 동안 다른 프로세스가 끼어들지 않으므로, 데이터 일관성을 유지하기 위한 복잡한 동기화 메커니즘이 덜 필요함

[단점]

• 응답 시간이 길어질 수 있음
  긴 작업을 가진 프로세스가 CPU를 독점하면, 뒤에 있는 짧고 중요한 작업들이 오랫동안 기다려야 함
• 실시간(Real-Time) 시스템에는 부적합
  긴급한 작업이 발생해도 즉시 CPU를 빼앗아 처리할 수 없음

2. 주요 CPU 스케줄링 알고리즘

스케줄링 = CPU나 자원 배분을 어떻게 할 것인가라는 운영체제의 정책 (Policy)

스케줄링 알고리즘 = 그 정책을 실제로 구현하는 절차

비선점형 알고리즘

FCFS (First-Come, First-Served)

• 준비 큐에 가장 먼저 도착한 프로세스가 CPU를 할당받아 작업을 마칠 때까지 실행
  가장 간단하고 구현이 쉬움
• 공정성이 보장됨
• 호위 효과(Convoy Effect)
  짧은 작업이 긴 작업을 기다려야 함

SJF (Shortest-Job-First)

• 준비 큐에 있는 프로세스 중 다음 CPU 버스트 시간(실행 시간)이 가장 짧은 프로세스에게 CPU를 할당
• 주어진 프로세스 집합에 대해 평균 대기 시간을 최소화하는 최적의 알고리즘
• 비선점형 SJF ↔ 선점형 SJF (SRTF: Shortest-Remaining-Time-First)
• 문제점 (미래 예측의 어려움)
  다음 CPU 버스트 시간을 정확히 알 수 없기 때문에 실제로는 과거 실행 시간을 기반으로 예측하여 사용

선점형 알고리즘

라운드 로빈 (Round Robin, RR)

• 각 프로세스에 정해진 시간 할당량(Time Quantum / Time Slice)을 순서대로 부여함
• 시간 할당량이 만료되면 CPU는 강제로 빼앗기고 다음 프로세스로 넘어감
• 시분할 시스템 (Time-Sharing)에서 가장 널리 사용되어 빠른 응답 시간과 공정성을 보장함
• 시간 할당량의 크기가 성능에 큰 영향을 미침
• 너무 크면 FCFS와 유사해지고, 너무 작으면 잦은 문맥 교환(Context Switching)으로 인한 오버헤드가 커짐

SRTF (Shortest-Remaining-Time-First)

• SJF의 선점형 버전
• CPU를 할당받아 실행 중이더라도, 남은 실행 시간이 더 짧은 새로운 프로세스가 도착하면 CPU를 강제로 빼앗아 그 프로세스에게 할당
• 비선점형 SJF보다 평균 대기 시간이 더 짧을 수 있음
• 마찬가지로 다음 버스트 시간 예측 문제가 있으며, 잦은 선점으로 인해 문맥 교환 오버헤드가 높음

우선순위 스케줄링 (Priority Scheduling)

• 각 프로세스에 우선순위를 부여하고 가장 높은 우선순위(숫자가 낮을 수록 높음)를 가진 프로세스에게 CPU를 할당
• 선점 /비선점형 모두 가능
• 기아 현상(Starvation) 문제
  낮은 우선순위의 프로세스가 영원히 CPU를 할당받지 못하고 대기
• 문제 해결 기법: 노화(Aging)
  시간이 지날수록 프로세스의 우선순위를 높여주는 방법으로 기아 현상을 방지