CPU 스케줄링

 

CPU 스케줄링이란?

CPU 스케줄링은 운영체제가 여러 프로세스들 중에서 어떤 프로세스를 언제 실행할지를 결정하는 과정이다. 현대의 컴퓨터 시스템은 다수의 프로세스가 동시에 실행되기를 요구하지만, 대부분의 경우 CPU는 한 번에 하나의 프로세스만 실행할 수 있다. 따라서 CPU의 사용 권한을 효율적으로 분배하기 위해 스케줄링이 필요하다.

CPU 스케줄링이 필요한 이유

• CPU 자원은 한정되어 있다
  동시에 여러 작업을 처리해야 하는 환경에서, CPU는 항상 바쁘게 동작하며, 모든 요청을 즉시 처리할 수 없다.
• 프로세스마다 특성이 다르다
  어떤 프로세스는 계산 중심(CPU-bound)이고, 어떤 프로세스는 입출력 중심(I/O-bound)이다. 이를 고려한 스케줄링이 필요하다.
• 응답 시간과 처리율 최적화
  사용자 프로그램은 빠른 응답을 원하고, 시스템은 가능한 많은 작업을 처리해야 한다. 이를 위해서는 전략적인 스케줄링이 필수적이다.
• 멀티태스킹 구현의 기반
  사용자 입장에서 여러 프로그램이 동시에 실행되는 것처럼 보이게 하려면, 스케줄링이 순간순간 CPU를 적절히 분배해야 한다.

---

 

프로세스의 우선순위

모든 프로세스가 동일하게 중요한 것은 아니다. 어떤 프로세스는 빠르게 처리되어야 하는 반면, 어떤 프로세스는 상대적으로 나중에 실행해도 괜찮다. 이처럼 CPU 스케줄링에서 프로세스 간의 우선순위를 고려하는 이유는 전체 시스템의 효율성과 사용자 만족도를 높이기 위함이다.

입출력 중심 프로세스와 CPU 중심 프로세스

분류	설명	예시
입출력 중심 (I/O-bound)	입출력 장치와의 작업이 많은 프로세스. CPU를 사용하는 시간은 짧고 I/O 작업이 자주 발생한다.	파일 다운로드, DB 쿼리
CPU 중심 (CPU-bound)	계산 등 CPU 자원을 오래 사용하는 프로세스. 연산 시간이 길고 I/O는 상대적으로 적다.	영상 인코딩, 대규모 수치 연산

 

어떤 프로세스를 먼저 실행하는 것이 유리할까?

입출력 중심 프로세스를 먼저 실행하는 것이 시스템 전체 성능에 더 유리하다. 그 이유는 다음과 같다:

• 병렬 처리 효과
  입출력 중심 프로세스는 빠르게 CPU를 사용하고 I/O 작업으로 넘어가므로, 그 동안 CPU는 다른 프로세스를 처리할 수 있다.
• CPU 자원 활용 극대화
  CPU 중심 프로세스만 연달아 실행하면 I/O 장치는 놀게 된다. 입출력 중심 프로세스를 적절히 섞어 실행하면 CPU와 I/O를 동시에 활용할 수 있다.
• 응답 시간 개선
  사용자 요청은 대개 입출력 중심이며, 이런 요청을 우선 처리하면 사용자 입장에서 응답 속도가 빨라진다.

 

---

 

스케줄링 큐

CPU 스케줄링은 단순히 한 줄로 된 대기열에서 프로세스를 하나씩 꺼내는 방식이 아니다. 운영체제는 여러 종류의 스케줄링 큐(Scheduling Queue)를 두고 각 단계마다 프로세스를 관리한다. 각 큐는 프로세스의 상태와 목적에 따라 다르며, 이들 사이의 이동이 스케줄링의 핵심이다.

대표적인 스케줄링 큐

큐 이름	설명
Job Queue	시스템에 들어온 모든 작업이 처음 등록되는 큐. 아직 메모리에 올라가지 않은 상태.
Ready Queue	메모리에 올라와서 실행 대기 중인 프로세스들이 대기하는 큐. 흔히 말하는 "스케줄링 대상 큐"다.
Device Queue	특정 I/O 장치를 기다리는 프로세스들이 대기하는 큐. 장치별로 별도로 존재하며, I/O 작업 완료 후 Ready Queue로 복귀함.
Waiting Queue	이벤트 발생을 기다리는 상태로, 입출력 완료, 타이머 만료, 인터럽트 등 다양한 상황을 포함한다. Device Queue보다 넓은 개념으로 볼 수 있다.
Terminated List	종료된 프로세스가 정리되기 전 잠시 머무는 공간으로, 프로세스가 완전히 해제되기 전에 후처리를 기다린다.

Ready Queue는 CPU를 기다리는 프로세스들의 핵심 대기열이며, 실제 스케줄러가 CPU 할당을 수행하는 주요 대상이다.

스케줄링 큐와 우선순위

모든 Ready Queue가 단순한 선입선출 구조는 아니다. 운영체제는 다음과 같은 다양한 전략으로 Ready Queue를 구성한다:

• 단일 큐 + 우선순위: 하나의 Ready Queue 안에서 우선순위가 높은 프로세스가 앞에 오도록 정렬된다.
• 다중 큐 구조: 우선순위에 따라 여러 개의 Ready Queue를 두고, 각 큐마다 다른 스케줄링 정책을 적용할 수도 있다 (예: MLFQ).

이처럼 우선순위가 스케줄링에 반영되면, 높은 우선순위의 프로세스가 먼저 CPU를 할당받는다. 그리고 이러한 정책이 선점형(Preemptive) 스케줄링과 결합되면, 실행 중인 프로세스도 CPU를 빼앗길 수 있다.

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

구분	설명	예시
비선점형 (Non-Preemptive)	한 프로세스가 CPU를 점유하면 스스로 종료하거나 대기 상태가 되기 전까지 다른 프로세스는 CPU를 빼앗을 수 없다.	FCFS, SJF (비선점형)
선점형 (Preemptive)	스케줄러가 상황에 따라 현재 실행 중인 프로세스를 강제로 중단시키고 CPU를 다른 프로세스에게 할당할 수 있다.	Round Robin, Priority (선점형)

 

비선점형은 문맥 교환이 적어 오버헤드가 낮지만 응답성이 떨어질 수 있고, 선점형은 빠른 응답성과 공정성을 확보할 수 있는 대신 컨텍스트 스위칭 비용이 발생한다.

 

---

 

CPU 스케줄링 알고리즘

운영체제는 Ready Queue에 있는 여러 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하기 위해 다양한 알고리즘을 사용한다. 스케줄링 알고리즘은 선점형(preemptive)과 비선점형(non-preemptive)으로 크게 나뉘며, 각각의 방식에 따라 장단점과 적용 상황이 달라진다.

---

비선점형 스케줄링 알고리즘

비선점형 방식은 한 번 CPU를 할당받은 프로세스가 스스로 종료되거나 I/O 대기 상태로 바뀌기 전까지는 CPU를 다른 프로세스에게 넘기지 않는다.
컨텍스트 스위칭이 적어 오버헤드가 낮은 반면, 응답성이 떨어질 수 있다.

• FCFS (First Come First Serve): 도착 순서대로 처리. 구조가 단순하지만, 기다리는 프로세스가 길어질 수 있다.
• SJF (Shortest Job First): 실행 시간이 가장 짧은 작업부터 수행. 평균 대기 시간이 낮지만, 실행 시간 예측이 필요하다.
• Non-preemptive Priority: 우선순위가 높은 프로세스를 먼저 실행하되, 한 번 실행된 프로세스는 끝날 때까지 유지된다.
• HRRN (Highest Response Ratio Next): (대기 시간 + 실행 시간) / 실행 시간 값을 기준으로 높은 비율의 프로세스를 선택. SJF의 기아 현상을 완화한다.

---

선점형 스케줄링 알고리즘

선점형 방식은 운영체제가 언제든지 현재 실행 중인 프로세스를 중단시키고, 더 적합한 프로세스에게 CPU를 할당할 수 있는 구조다.
응답 속도가 빠르고 공정성을 확보할 수 있지만, 문맥 전환 비용이 발생한다.

• Preemptive SJF (SRTF): 현재 실행 중인 프로세스보다 실행 시간이 더 짧은 새 프로세스가 들어오면 교체.
• Preemptive Priority: 더 높은 우선순위의 프로세스가 도착하면 CPU를 선점.
• Round Robin (RR): 고정된 시간 할당량(Quantum)을 기준으로 순환 처리.
• MLFQ (Multi-Level Feedback Queue): 실행 이력에 따라 우선순위를 동적으로 조정하는 다단계 큐 기반의 유연한 스케줄링.
• O(1) Scheduler: Linux 2.6에서 사용되었던 방식으로, O(1) 시간에 다음 프로세스를 선택함.
• CFS (Completely Fair Scheduler): 현재 Linux 커널에서 사용하는 방식으로, 각 프로세스에게 공정한 CPU 시간 배분을 목표로 함.

---

FCFS (First Come First Serve)

FCFS는 프로세스가 도착한 순서대로 CPU를 할당하는 방식이다. 큐 구조는 일반적인 FIFO(First-In First-Out) 형태다.

• 장점: 구현이 매우 간단하며, 컨텍스트 스위칭이 적어 오버헤드가 낮다.
• 단점: 긴 작업이 먼저 들어오면 전체 대기 시간이 증가하는 Convoy 현상이 발생할 수 있다.

예시
도착 순서: P1, P2, P3
실행 시간: P1(10), P2(2), P3(1)

→ P2, P3가 짧은 작업임에도 긴 P1이 먼저 실행되어 전체 평균 대기 시간이 증가함.

---

SJF (Shortest Job First)

SJF는 실행 시간이 가장 짧은 프로세스를 우선적으로 실행하는 방식이다. 이론적으로 평균 대기 시간을 가장 최소화할 수 있다.

• 비선점형 SJF: 한 번 CPU를 할당받으면 실행이 끝날 때까지 유지.
• 선점형 SJF (SRTF): 더 짧은 실행 시간이 도착하면 현재 작업을 중단하고 CPU를 선점.
• 장점: 평균 대기 시간이 매우 낮음
• 단점: 실행 시간을 미리 예측해야 하고, **기아(Starvation)**가 발생할 수 있음

예시
도착 시간: 모두 0
실행 시간: P1(6), P2(8), P3(7), P4(3)
→ P4 → P1 → P3 → P2 순으로 실행되며, FCFS보다 평균 대기 시간이 훨씬 짧아진다.

---

Priority Scheduling

우선순위(priority)를 기준으로 높은 순위의 프로세스를 먼저 실행하는 방식이다. 우선순위는 정수로 표현되며, 숫자가 작을수록 높은 순위로 간주되는 경우가 많다.

• 비선점형: 현재 실행 중인 프로세스가 끝날 때까지 유지
• 선점형: 더 높은 우선순위가 도착하면 CPU를 강제로 선점
• 장점: 중요한 작업을 먼저 처리할 수 있음
• 단점: 낮은 우선순위의 작업이 무한정 기다리는 기아(Starvation) 현상 발생 가능

→ 해결 방법으로는 Aging 기법이 사용되며, 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높여준다.

---

Round Robin (RR)

Round Robin은 각 프로세스에게 동일한 시간 할당량(Quantum)을 부여하고, 정해진 시간이 지나면 CPU를 회수하고 다음 프로세스에 넘기는 방식이다.

• 장점: 응답 시간이 일정하여 사용자 경험이 좋아짐, 공정한 분배
• 단점: 타임 슬라이스 설정이 부적절하면 오버헤드 과다 또는 긴 응답 시간이 발생할 수 있음

예시
프로세스: P1(8), P2(4), P3(9), P4(5)
Quantum = 3이라면 → P1(3) → P2(3) → P3(3) → P4(3) → P1(3) → P2(1) … 이런 식으로 순환함

→ 컨텍스트 스위칭 비용이 많아지므로, 타임 슬라이스는 상황에 맞게 조절해야 한다.

---

MLFQ (Multi-Level Feedback Queue)

MLFQ는 여러 개의 우선순위 큐를 두고, 프로세스의 실행 이력을 바탕으로 큐를 이동시키며 우선순위를 동적으로 조정하는 고급 알고리즘이다.

• 초기에는 높은 우선순위 큐에 배치되고, CPU 사용 시간이 늘어나면 점차 낮은 큐로 이동
• 짧고 자주 실행되는 프로세스(인터랙티브)는 높은 우선순위를 유지
• 긴 작업(배치형)은 낮은 우선순위로 내려가지만, Aging 등을 통해 다시 끌어올릴 수 있음
• 장점: 다양한 특성의 작업을 유연하게 처리할 수 있음 (복합 환경에 강함)
• 단점: 구현 복잡도 높고, 정책 설정에 따라 성능이 크게 달라짐