놀라운 운영체제 #3 – CPU 스케줄링

목차

• 개요
• 1. 스케줄러의 개념 및 종류
  • 1-1. 장기(고수준) 스케줄러
  • 1-2. 단기(저수준) 스케줄러
  • 1-3. 중기(중간수준) 스케줄러
• 2. CPU 스케줄링이란?
• 3. CPU 스케줄링의 목적
• 4. 선점형 vs 비선점형 스케줄링
• 5. CPU 집중 프로세스 vs 입출력 집중 프로세스
• 6. 프로세스 우선순위 및 분류
• 7. 다중 큐(Queue) 관리
  • 7-1. 준비 상태의 다중 큐
  • 7-2. 대기 상태의 다중 큐
• 8. 스케줄링 알고리즘의 선택 기준
• 9. 주요 CPU 스케줄링 알고리즘
• 10. 다단계 큐(MLQ) 스케줄링
• 11. 다단계 피드백 큐(MLFQ) 스케줄링
• Reference

개요

앞선 글에서 프로세스와 스레드가 어떻게 운영체제에서 관리되는지 살펴봤다.

여러 작업이 동시에 돌아가는 상황에서,
운영체제는 “누구에게, 언제, 어떻게 CPU 사용 기회를 줄 것인가?”라는
복잡하고 중요한 결정을 내려야 한다.
만약 이 선택이 효율적이지 못하다면, 어떤 작업은 지나치게 오래 기다리거나 시스템 전체의 응답성이 떨어질 수 있다.

이번 글에서는,
이런 현실적인 문제와 한계를 해결하기 위해 운영체제가 어떤 기준과 원리로
각 작업의 CPU 사용 순서를 정하는지,
CPU의 선택 기준을 결정짓는 스케줄링 전략에 대해 다뤄보고자 한다.

1. 스케줄러의 개념 및 종류

운영체제에서 스케줄러(Scheduler)는 여러 프로세스 중 어떤 것을 실행할지 결정하는 역할을 한다. 효율적 자원 관리와 시스템의 성능 향상에 매우 중요하다.

• 장기(고수준) 스케줄러 (Long-Term Scheduler)
• 단기(저수준) 스케줄러 (Short-Term Scheduler)
• 중기(중간수준) 스케줄러 (Medium-Term Scheduler)

운영체제에서의 프로세스 상태 전이와도 밀접한 관련이 있다.
앞서 다룬 프로세스의 5가지 상태(생성, 준비, 실행, 대기, 종료, 보류 등)에서
각 스케줄러가 어느 단계에 관여하는지 예시로 보면 더욱 쉽게 이해할 수 있다.

---

1-1. 장기(고수준) 스케줄러

역할: 보조 기억장치(디스크)에 있는 작업 중 어떤 작업을 메모리(주기억장치)에 올릴지 결정한다.

프로세스가 생성된 후,
→ 작업 큐(NEW 상태)에 있던 프로세스가
→ 준비 상태(Ready Queue)로 진입할 때
→ 장기 스케줄러가 개입하여 "입장관리자" 역할을 한다.

특징: 실행 빈도가 낮고, 시스템 전체의 작업 부하 조절 역할

특징: 실행 빈도가 낮고, 시스템 전체의 작업 부하 조절 역할

1-2. 단기(저수준) 스케줄러

역할: 준비 상태(Ready Queue)에 있는 프로세스 중에서 CPU에 할당할 프로세스를 선택한다.

프로세스가 준비 상태(Ready)에서
→ 실행 상태(Running)로 전환될 때
→ 단기 스케줄러가 개입하여 실제 CPU에 올라갈 프로세스를 결정한다.

특징: 실행 빈도가 매우 높으며, 컨텍스트 스위칭(문맥교환)마다 동작

---

1-3. 중기(중간수준) 스케줄러

역할: 실행/대기 중인 프로세스 중 일부를 메모리에서 디스크로 내보내거나(swap-out), 다시 불러옴(swap-in)

예를 들어 입출력 대기(Waiting) 상태나,
시스템에 메모리가 부족할 때
→ 중기 스케줄러가 프로세스를 "보류(Suspended)" 상태로 전환해
일시적으로 메모리에서 내보내고, 필요할 때 다시 메모리에 불러오는 역할을 한다.

특징: 시스템 메모리 부하 조절, 프로세스 상태 전환(ready ↔ suspended) 담당

---

2. CPU 스케줄링이란?

컴퓨터에서 동시에 실행되는 여러 프로세스(혹은 스레드)들이
모두 한 번에 CPU를 사용할 수는 없다.
따라서 운영체제는 한정된 CPU 자원을 각 작업에 어떻게, 언제, 누구에게 배분할지
지속적으로 판단하고 결정해야 한다.

이처럼 CPU라는 가장 중요한 자원을 여러 작업에게 효율적으로 나누어주는 작업을
바로 CPU 스케줄링(CPU Scheduling)이라고 한다.

CPU 스케줄링은 시스템 전체의 성능, 각 작업의 응답 속도,
자원의 효율적 분배 등 운영체제의 전반적인 품질에 직접적으로 영향을 미치는
핵심 기능 중 하나다.

---

3. CPU 스케줄링의 목적

CPU 스케줄링은 아래와 같은 목표를 달성하기 위해 실행된다.

• 공평성(Fairness): 모든 프로세스가 공정하게 CPU를 사용할 수 있도록.
• 효율성(Efficiency): 자원을 최대한 활용.
• 안정성(Stability): 예측 가능하고 안정적인 시스템 동작.
• 확장성(Scalability): 시스템 규모가 커져도 일정 성능 유지.
• 반응 시간 보장(Response time): 대화형 시스템 등에서 빠른 응답.
• 무한 연기 방지(Starvation 방지): 특정 프로세스가 영원히 실행되지 못하는 현상 방지.

---

4. 선점형 vs 비선점형 스케줄링

여러 프로세스가 CPU를 두고 경쟁하는 환경에서는, 작업의 순서뿐만 아니라,
CPU를 할당받은 작업을 얼마나 오랫동안 실행하냐? 또한 하나의 문제다.

이때 운영체제는 CPU 사용권을 프로세스에게 어떻게, 언제까지 맡길지에 따라 크게
두가지 방식의 스케줄링 전략을 사용한다.

• 선점형(Preemptive):

  • 실행 중인 프로세스라도 더 높은 우선순위의 프로세스가 오면 CPU를 빼앗길 수 있음.
  • ex) 라운드로빈(RR), SRTF, 우선순위(선점형)

• 비선점형(Non-Preemptive):

  • CPU를 할당받은 프로세스의 작업이 끝나거나, 입출력등으로 CPU를 반납할 때까지 실행.
  • ex) FCFS, SJF(비선점), 우선순위(비선점)

---

5. CPU 집중 프로세스 vs 입출력 집중 프로세스

운영체제에서 프로세스의 성격을 구분할 때,
CPU 집중 프로세스와 입출력(I/O) 집중 프로세스로 나누기도 한다.

• CPU 집중 프로세스

  • 수학 계산, 암호화 등과 같이 CPU 연산을 많이 사용하는 작업
  • CPU 버스트(CPU burst) 구간이 길고 빈번하게 발생
  • 입출력 작업 전에 CPU에서 오랜 시간 연산을 수행함

• 입출력 집중 프로세스

  • 파일 복사, 데이터베이스 접근 등 입출력(I/O) 작업이 많은 작업
  • I/O 버스트(I/O burst) 구간이 많음
  • CPU에서 잠깐 연산한 뒤, 곧바로 저장장치 등 외부 장치와 데이터를 주고받는 작업을 반
    복

  ---

6. 프로세스 우선순위 및 분류

운영체제는 모든 프로세스에게 동등한 조건으로 CPU를 배분하지 않는다.
CPU 스케줄링 시 각 프로세서의 중요도나 성격에 따라 우선순위를 부여한다.

• 커널 프로세스 > 사용자 프로세스
  (시스템 핵심 기능을 수행하는 커널 프로세스가 더 높은 우선순위를 가짐)
• 입출력 집중 프로세스 > CPU 집중 프로세스
  (I/O 작업을 많이 하는 프로세스에 CPU를 우선 할당하면 전체 시스템 효율이 높아진다)
• 전면(전경) 프로세스 > 후면(백그라운드) 프로세스
  (사용자 직접 사용하는 작업이 우선)

7. 다중 큐(Queue) 관리

7-1. 준비 상태의 다중 큐

• 프로세스는 저마다 중요도(우선순위)가 다르며, 이 값은 프로세스 제어 블록(PCB)에 기록된다.
• CPU 스케줄러가 모든 PCB를 매번 뒤져 가장 높은 우선순위 프로세스를 찾는 것은 비효율적이기 때문에,
• 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막(tail)에 삽입된다.
• 준비 큐의 개수나, 여러 큐 중 어느 프로세스에 CPU를 먼저 할당할지는 스케줄링 알고리즘에 따라 다르다.

우선순위 배정 방식

• 고정 우선순위 (Static Priority): 프로세스가 종료될 때까지 우선순위가 변하지 않는다.
• 변동 우선순위 (Dynamic Priority): 작업 도중에도 우선순위가 바뀔 수 있다.
  (예: 오래 기다린 프로세스의 우선순위를 올려주는 "에이징(aging)" 등)
  ※ 우선순위가 낮은 프로세스가 높은 프로세스로 변할 때 이를 반전 우선순위(priority inversion)라고도 한다.

---

7-2. 대기 상태의 다중 큐

• 대기 상태(Waiting)는 입출력이 완료되기를 기다리는 프로세스들이 모여 있는 곳이다.
• 시스템에는 다양한 종류의 입출력 장치가 있으므로,
  동일한 입출력(I/O) 장치를 기다리는 프로세스들끼리 별도의 큐로 관리한다.
• 이를 통해, 필요한 프로세스를 더 효율적으로 찾고 관리할 수 있다.

준비 큐 vs 대기 큐 차이

• 준비 큐: 한 번에 하나의 프로세스만 꺼내서 CPU를 할당

• 대기 큐: 여러 프로세스의 입출력이 동시에 끝나면(여러 인터럽트 발생 시),
  관련된 여러 프로세스가 한꺼번에 준비 상태로 이동

• 시스템에는 여러 입출력 장치가 있어, 입출력이 동시에 완료되면 인터럽트 벡터를 통해
  완료된 모든 프로세스 제어 블록을 준비 상태로 옮긴다.

---

8. 스케줄링 알고리즘의 선택 기준

CPU 스케줄링 알고리즘을 선택할 때 운영체제는 여러 가지 현실적인 기준을 종합적으로 고려한다.
대표적인 선택 기준은 다음과 같다.

• CPU 이용률(Throughput):
  단위 시간 동안 처리된 프로세스의 수를 의미.
  (값이 높을수록 시스템이 많은 작업을 효율적으로 처리하고 있다는 뜻)

• 평균 대기 시간(Average Waiting Time):
  각 프로세스가 준비 큐에서 실행을 기다린 평균 시간.
  (짧을수록 사용자 입장에서 쾌적하다)

• 반환 시간(Turnaround Time):
  프로세스가 시스템에 들어온 시점부터 완전히 끝나는 시점까지 걸린 총 시간.
  (사용자/작업의 전체 처리 효율을 평가하는 지표)

• 응답 시간(Response Time):
  사용자 입력(명령) 이후, 시스템이 첫 반응을 보일 때까지 걸린 시간.
  (대화형 시스템, 실시간 시스템에서 특히 중요)

• 공정성(Fairness):
  모든 프로세스(사용자)가 합리적으로 CPU 사용 기회를 갖는지 여부.
  (특정 작업이 계속 무시되거나, 기아(Starvation)가 발생하지 않게끔 설계)

• 시스템 특성/요구사항:
  예를 들어 실시간 시스템은 빠른 응답이,
  대용량 배치 시스템은 전체 처리량이 더 중요할 수 있다.

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

9-1. FCFS (First-Come, First-Served, 선입선출)

• 원리: 먼저 도착한 순서대로 처리(큐의 앞에서부터 순차적으로 실행)
• 장점: 구현이 매우 쉽고, 공평하다
• 단점: 앞에 긴 작업이 있으면 짧은 작업이 오래 대기하는 Convoy Effect(호위 효과) 발생
  → 평균 대기시간이 늘어날 수 있음
• 적용: 배치 작업 등, 작업 순서가 중요한 경우

---

9-2. SJF (Shortest Job First, 최단 작업 우선)

• 원리: 실행 시간이 가장 짧은 작업부터 실행
• 장점: 평균 대기 시간을 최소화할 수 있음(이론상 가장 효율적)
• 단점: 각 작업의 실제 실행 시간을 미리 알기 어려움.
  긴 작업이 계속 뒤로 밀릴 경우 기아(Starvation)가 발생할 수 있음
• 적용: 작업 길이를 예측할 수 있는 상황, 단순한 배치 처리 등

---

9-3. SRF(SRTF) (Shortest Remaining Time First, 남은 시간 우선)

• 원리:
  SJF의 선점형 버전.
  새로운 작업이 도착하면 현재 작업과 남은 시간을 비교하여
  더 짧은 작업이 있으면 바로 CPU를 빼앗아 교체(선점)
• 장점:
  SJF의 평균 대기시간 최소화 효과를 유지하면서
  실시간으로 더 짧은 작업에 즉각 반응할 수 있음
• 단점:
  각 작업의 남은 시간을 항상 추적/예측해야 하는 부담
  긴 작업의 기아 가능성 존재
• 적용:
  실시간 시스템, 대화형 환경 등 빠른 반응성 필요할 때

---

9-4. HRN (Highest Response Ratio Next, 응답률 우선)

• 원리:
  응답률 = (대기시간 + 실행시간) / 실행시간
  이 값이 가장 높은 프로세스부터 실행

• 장점:
  짧은 작업이 빨리 끝나면서도,
  오래 기다린 작업의 우선순위도 자동으로 올라가
  기아(Starvation)를 방지할 수 있다.

• 적용:
  다양한 작업이 섞인 환경에서 공정성과 효율성을 동시에 추구

프로세스	대기 시간 (W)	실행 시간 (S)	응답률 (R)
P1	2	4	(2 + 4) / 4 = 1.5
P2	4	3	(4 + 3) / 3 = 2.33
P3	1	2	(1 + 2) / 2 = 1.5

• 이 경우, P2의 응답률(R)이 가장 높으므로 먼저 실행된다.
• 실행이 끝나면, 남은 프로세스들의 대기 시간이 늘어나
  다음 선택에 자동으로 반영된다.

---

9-5. 라운드 로빈(RR, Round Robin)

• 원리:
  각 프로세스에 동일한 시간 할당량(Quantum)을 주고,
  할당 시간이 끝나면 준비 큐의 맨 뒤로 이동
• 장점:
  모든 프로세스가 정기적으로 실행 기회를 보장받아,
  대화형/멀티태스킹 환경에서 빠른 응답성을 가짐
• 단점:
  타임퀀텀(Quantum) 크기 조절이 중요:
  너무 작으면 오버헤드(문맥교환)가 커지고,
  너무 크면 FCFS와 별 차이 없어짐
• 적용:
  사용자와 직접 상호작용이 많은 운영체제, 멀티태스킹 환경

---

9-6. 우선순위 스케줄링(Priority Scheduling)

• 원리:
  프로세스마다 우선순위를 지정해서,
  더 높은 우선순위 작업부터 실행(선점형/비선점형 모두 지원)
• 장점:
  중요한 작업을 빠르게 처리 가능(유연성)
• 단점:
  낮은 우선순위 작업이 계속 밀려서 기아(Starvation) 발생 가능
  → 이를 보완하기 위해 에이징(Aging) 등 기법 사용
• 적용:
  실시간 시스템, 미션 크리티컬한 작업이 있는 경우

---

실제 운영체제에서는 이들 알고리즘을 조합하거나,
상황에 따라 동적으로 전환하며 시스템 목적(효율/응답/공정성 등)에 최적화합니다.

---

10. 다단계 큐(MLQ) 스케줄링

실제 운영체제에는 다양한 유형의 프로세스(대화형/배치/시스템/실시간 등)가 동시에 존재합니다.
각 유형의 프로세스는 요구하는 서비스 특성이 다르고,
한 가지 스케줄링 알고리즘만으로는 모든 요구를 충족하기 어렵습니다.

다단계 큐(MLQ, Multi-Level Queue) 스케줄링은
이런 현실적인 문제를 해결하기 위한 방식입니다.

• 동작 원리:

  • 여러 개의 Ready Queue(준비 큐)를 운영
  • 각 큐마다 프로세스의 유형이나 우선순위, 성격(예: 시스템/대화형/배치/실시간 등)에 따라 프로세스를 분리
  • 각 큐별로 서로 다른 스케줄링 알고리즘을 적용할 수 있음
    (예: 대화형 큐는 RR, 배치 큐는 FCFS 등)
  • 큐 간 이동이 불가(프로세스는 배정된 큐에서만 실행)

• 예시:
  1번 큐: 실시간 작업(RR, 빠른 응답 보장)
  2번 큐: 대화형 프로그램(짧은 타임슬라이스 RR)
  3번 큐: 배치 작업(FCFS, 긴 작업도 차례로 처리)

• 특징:

  • 분류 기준(큐 배정)은 주로 프로세스의 우선순위, 생성 목적, 사용자 등으로 결정
  • 각 큐별로 자원 할당 비율을 달리할 수 있어 자원 관리가 유연
  • 프로세스가 큐를 한 번 배정받으면, 다른 큐로 옮겨 다닐 수 없음
    → 큐 간 이동이 없기 때문에, "고정 분류"에 가깝다.

• 장점:

  • 다양한 유형의 작업을 효율적으로 분리 및 관리
  • 우선순위, 시스템 특성에 맞는 차별화된 서비스 가능

• 단점:

  • 큐 배정이 잘못되면 특정 큐의 작업이 영원히 실행되지 못할 수도 있음(기아 발생)

---

11. 다단계 피드백 큐(MLFQ) 스케줄링

다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue)는
다단계 큐의 한계(큐 간 이동 불가, 고정 우선순위 등)를 극복하기 위해
큐 간 이동과 동적 우선순위를 도입한 더욱 “현대적”인 스케줄링 기법입니다.

• 동작 원리:

  • 여러 개의 큐를 두고, 프로세스가 상위 큐에서 하위 큐로 자유롭게 이동할 수 있음
  • 새로 도착한 프로세스는 항상 최상위 큐(가장 높은 우선순위)에 배정
  • 주어진 시간(타임퀀텀) 내에 작업을 끝내지 못하면,
    → 더 낮은 우선순위(하위) 큐로 이동(“피드백”)
  • 반대로, 오랜 대기 등 특정 조건을 만족하면 우선순위가 다시 올라갈 수도 있음(aging)

• 타임퀀텀(Quantum) 특징:

  • 상위 큐일수록 더 짧은 타임퀀텀을 할당
    → 대화형/짧은 작업에 빠른 응답성 제공
  • 하위 큐로 갈수록 타임퀀텀이 길어짐
    → 긴 작업도 차별받지 않고, 결국엔 처리 보장

• 장점:

  • 응답성이 중요한 대화형 작업과, 긴 배치 작업을 모두 효율적으로 관리
  • 우선순위가 동적으로 변하므로, 특정 작업이 계속 무시되는 “기아(Starvation)”를 방지
  • 실제 현대 운영체제(예: Windows, Linux)에서 가장 널리 사용

• 단점:

  • 큐 이동/우선순위 관리가 복잡해 구현 난이도가 높다

• 예시:

  • 새로 들어온 단기 작업은 상위 큐에서 빠르게 처리
  • 오래 CPU를 점유하거나, 시간이 오래 걸리는 작업은 점차 하위 큐로 내려가
    → CPU 자원을 “공정하게” 분배
  • 대기 시간이 길어진 작업은 다시 우선순위가 올라가기도 한다

---

MLQ vs MLFQ 요약 비교

	MLQ(다단계 큐)	MLFQ(다단계 피드백 큐)
큐간 이동	X(불가, 고정 큐)	O(상하위 큐 이동 가능)
우선순위	고정	동적(작업 성격에 따라 변화)
목적	유형별 분리, 효율화	응답성 + 공정성 + 효율성
대표적 적용	제한적/과거 OS	현대 OS(윈도우, 리눅스 등)

---

[Reference]

• 쉽게 배우는 운영체제