[CS] CPU 스케줄링 알고리즘

• 여러 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하는 정책
• CPU 스케줄링의 목표
  1. CPU 이용률 ↑ 
     
     • 하드웨어 효율 관점
     • CPU가 놀고 있지 않도록
  2. 주어진 시간에 많은 일을 하게
     • 시스템 성능 관점
     • 처리량 ↑
  3. 준비 큐에 있는 프로세스는  ↓ 
     • 자원 공정성 관점
     • 불필요한 대기 ↓
       📝준비큐가 길다는 것은? 실행할 준비는 됐지만 CPU를 못받아 대기중이라는 뜻.
  4. 응답시간 ↓ 
     • 사용자 체감 UX 관점
     • 사용자가 '멈췄다'고 느끼지 않도록

CPU 스케줄링의 4가지 목표는
CPU를 놀리지 않으면서,
많은 일을 공정하게 처리하고,
사용자가 빠르다고 느끼게 만들기 위해 존재한다.

---

출처: https://pyoungt.tistory.com/246

1. 비선점형 방식

• 운영체제 초창기에는 단일 작업 위주, 사용자 입력 즉시 반응 X, 시스템 구조 단순함이 중요했기때문에 구현이 단순하고, 컨텍스트 스위칭을 최소화하며, 예측 가능한 실행을 목표로 함.
• 프로세스가 스스로 CPU 소유권을 포기하는 방식 (강제로 프로세스 중지 X)
• 컨텍스트 스위칭으로 인한 부하가 적음 → CPU 낭비 ↓ 오버헤드 ↓
• 긴 작업이 앞에 있으면 뒤의 짧은 작업이 오래 기다림 : Convoy Effect(호위 효과)

1. FCFS (First Come First Served)

• 도착한 프로세스 먼저 CPU 할당
• 👍🏻장점
  • 구현이 매우 단순
  • 오버헤드가 적음
• 👎🏻단점
  • Convoy Effect 발생

2. SJF (Shortest Job First)

• CPU 사용 시간이 가장 짧은 프로세스부터 실행
• 👍🏻장점
  • 평균 대기 시간 최소
• 👎🏻단점
  • 긴 시간을 가진 프로세스가 실행되지 않는 기아 현상(Starvation) 발생 가능
  • 실행 시간을 미리 알 수 없음 
• 예측 기법(이전 실행 시간 기반 추정)을 활용하여 보완

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

• 오래된 작업일수록 우선순위를 높이는(aging) 방법을 사용해 SJF의 단점을 보완한 알고리즘
• 우선순위가 높은 프로세스에게 CPU 할당
• 👎🏻 단점
  • 낮은 우선순위 프로세스 무한 대기(Starvation)

 

---

2. 선점형 방식

• 현대 운영체제가 쓰는 방식
• 현재 실행 중인 프로세스라도 운영체제가 필요하다고 판단하면 CPU를 강제로 빼앗아 다른 프로세스에게 CPU를 할당하는 방식
• 비선점형의 한계를 해결하고, 기술적인 변화(하드웨어 타이머 도입, 인터럽트 처리 성능 향상, 메모리 보호 등)
  → CPU를 나눠써도 시스템이 무너지지 않게 됨
• 선점형의 목표
  

  목표	이유
  응답 시간 단축	사용자 체감 성능 향상
  공정성 확보	CPU 독점 방지
  시스템 반응성	인터랙티브 환경 대응
  실시간 처리	긴급 작업 즉시 처리

 

1. 라운드 로빈(Round Robin)

• 고정된 시간 할당량(Time Quantum)만큼 CPU 사용하고, 해당 시간이 지나면 다시 큐의 뒤로 이동
• 👍🏻 장점
  • 응답 시간이 빠름
  • 공정성 보장
• 👎🏻 단점
  • 타임 퀀텀 설정이 중요
    • 타임 퀀텀이 너무 크면 FCFS와 유사
    • 타임 퀀팀이 너무 작으면 컨텍스트 스위칭이 잦아 오버헤드 증가

 

2. SRF(Shortest Remaining Time First)

• 남은 실행 시간이 가장 짧은 프로세스에게 CPU 할당
• SJF의 선점형 버전
  → 새로운 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행
• 👍🏻  장점
  • 평균 대기 시간 최소화
• 👎🏻 단점
  • 실행 시간 예측 필요
  • 잦은 컨텍스트 스위칭 발생

 

3. 다단계 큐

• 프로세스를 성격별로 여러 개의 준비 큐로 나누고, 큐마다 서로 다른 스케줄링 알고리즘과 우선순위를 적용하며, 상위 큐가 하위 큐를 선점할 수 있는 방식 → “프로세스 종류에 따라 줄을 따로 세우고, 중요한 줄이 항상 먼저 CPU를 쓴다”
• 예시 구조
  
  

  큐 레벨	프로세스 종류	스케줄링
  Q0 (최상위)	시스템 / 실시간	FCFS or RR
  Q1	사용자 인터랙션	Round Robin
  Q2	백그라운드 작업	FCFS

  👉 Q0 > Q1 > Q2 (상위 큐가 항상 선점)
• 상위 큐가 항상 우선
• 큐 간 프로세스 이동 X → 하위 큐 프로세스의 기아 상태 가능성

 

구분 방식 대표 알고리즘 특징

비선점형	CPU 반환 전까지 유지	FCFS, SJF	단순, 응답 느림
선점형	CPU 강제 회수 가능	RR, SRF	응답 빠름, 오버헤드