2. 운영체제 : CPU 스케줄링

해당 내용은 이것이 컴퓨터 과학이다 with CS 기술면접을 학습한 기록입니다.

 

목차
1. CPU 스케줄링의 이해
2. CPU 스케줄링 알고리즘

 

 

컴퓨터의 뇌라고 불리는 CPU는 한 번에 하나의 프로세스만 실행할 수 있다. 하지만 실제로는 여러 프로그램이 동시에 실행되는 것처럼 보이는데, 이는 운영체제가 CPU 사용 시간을 잘게 나누어 여러 프로세스에 배분하기 때문이다.

 

이처럼 운영체제가 여러 프로세스에 CPU 사용을 효율적으로 분배하는 정책을 CPU 스케줄링(CPU Scheduling)이라고 한다.

---

1. CPU 스케줄링의 이해

1-1. 왜 스케줄링이 필요한가 ? 

모든 프로세스는 실행 과정에서 다음 두 상태를 반복한다.

• CPU Burst : 실제 연산을 수행하는 구간 (CPU를 사용하는 시간)
• I/O Burst : 입출력을 기다리는 구간

 

문제는 입출력 작업이다.

만약 하나의 프로세스가 CPU를 계속 할당하면, 해당 프로세스가 입출력을 기다리는 동안 CPU는 아무 작업도 하지 못하고 유휴 상태에 빠지게 된다. 이러한 비효율을 해결하기 위해 운영체제는 다음과 같이 동작한다.

 

입출력 작업을 기다리는 프로세스 대신, 실행 가능한 다른 프로세스에 CPU를 할당

 

 

이 과정을 반복하면 다음과 같은 결과를 얻을 수 있다.

1. CPU 활용률 증가
2. 처리량 증가 
3. 응답 시간 개선

즉, CPU 스케줄링은 상황에 맞게 CPU를 배분하여 시스템 전체 성능을 결정하는 핵심 메커니즘이다.

---

1-2. 우선순위 (Priority) 

모든 프로세스가 동일하게 CPU를 할당받지는 않는다.

운영체제는 각 프로세스의 중요도를 판단하여 우선순위를 부여하고, 이를 PCB에 기록한다. 그리고 일반적으로 우선순위가 높은 프로세스에 CPU를 먼저 할당한다.

 

우선순위 정책을 이해하려면 먼저 프로세스를 두 가지로 나눠볼 수 있다.

 

이미지 출처 : 이것이 취업을 위한 컴퓨터 과학이다.

 

• 입출력 집중 프로세스 (I/O bound process)
  • 입출력이 많은 프로세스
  • CPU를 짧게 사용한 뒤 바로 I/O 요청 발생 
  • 예시 : 웹 서버, DB 요청 처리, 파일 읽기
  • CPU 점유 시간이 짧고, 빠른 응답이 필요
  • OS 전략 : 우선순위를 높게 설정, 빠르게 실행 뒤 I/O 요청 대기 구간에 다른 프로세스 실행
• CPU 집중 프로세스 (CPU bound process)
  • 복잡한 연산 작업이 많은 프로세스
  • CPU를 오랫동안 점유
  • 예시 : 컴파일, 영상 인코딩, 수치 계산
  • CPU 사용시간이 길고, 상대적으로 응답성보다 처리량이 중요
  • OS 전략 : 우선순위를 상대적으로 낮게 설정, CPU를 오래 점유하지 않도록 제어

 

이러한 정책으로 I/O 작업은 빠르게 처리하고, CPU는 놀지 않도록 만들 수 있다.

---

1-3. 스케줄링 큐 (Scheduling Queue)

운영체제는 프로세스를 상태에 따라 여러 큐로 관리한다.

이는 단순한 분류가 아니라, CPU 작업을 효율적으로 배분하기 위한 대기 구조이다.

 

스케줄링 큐의 종류

이미지 출처 : https://www.geeksforgeeks.org/operating-systems/types-of-scheduling-queues/

 

대표적인 큐는 다음과 같다.

• 준비 큐 (Ready Queue) : CPU 할당을 기다리는 프로세스
• 대기 큐 (Waiting Queue) : I/O 작업을 기다리는 프로세스

 

프로세스는 실행 과정에서 상태가 계속 바뀌며, 그에 따라 적절한 큐로 이동한다. 

** 프로세스 상태 관련된 내용은 아래의 게시글에 정리하였다.

2.운영체제 : 프로세스와 스레드

 

준비 큐에 들어오는 프로세스들은 단순히 선입선출(FIFO)로 처리되지 않는다. 운영체제는 스키줄링 알고리즘을 통해 실행 대상을 선택하는데, 이때 우선순위 등을 고려하게 된다. 

---

1-4. 선점형 스케줄링과 비선점형 스케줄링

준비 큐에서 프로세스를 선택하고, 해당 프로세스를 언제까지 실행시킬 것인가에 대한 문제가 발생한다.

이 기준에 따라 CPU 스케줄링은 크게 두 가지로 나뉜다.

1. 비선점형 스케줄링 : 한 번 CPU를 할당받은 프로세스가 스스로 CPU를 반환할 때 까지 계속 실행
   • 동작 흐름 : Ready Queue → CPU 할당 → 작업 완료 or I/O → 다음 프로세스 선택
   • 컨텍스트 스위칭이 적어 오버헤드가 낮고 구현이 단순하다.
   • 긴 작업이 CPU를 점유하면 뒤에 있는 프로세스들이 그만큼 대기해야 하며, 응답 시간이 느려지는 Convoy Effect가 발생할 수 있다.
2. 선점형 스케줄링 : 실행 중인 프로세스를 중단시켜, 운영체제가 강제로 CPU를 회수할 수 있는 방식
   1. 타임 슬라이스가 종료되거나, 더 높은 우선순위 프로세스가 등장하는 경우 선점이 발생한다.
   2. 동작 흐름 : Ready Queue → CPU 실행 → (시간 만료 or 우선순위 변화) → 다시 Ready Queue → 다른 프로세스 실행
   3. CPU 독점을 막고 여러 프로세스에 골고루 CPU 자원을 배분할 수 있다.
   4. 문맥 교환이 자주 발생하여 오버헤드가 증가될 수 있고, 구현 복잡도가 증가한다.

---

2. CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘이란, 준비 큐에 있는 프로세스 중 어떤 것을 먼저 실행할지 결정할 때 사용하는 규칙을 말한다.

 

각 알고리즘은 다음 기준들 사이에서 서로 다른 트레이드오프를 가진다.

• 응답시간
• 대기시간
• 처리량
• 공정성

---

2-1. 선입선처리 스케줄링 (FCFS, First Come First Served)

가장 단순한 방식으로, 준비 큐에 먼저 도착한 프로세스를 먼저 실행하는 알고리즘이다.

 

비선점형 스케줄링에 해당되기 때문에, 비선점형 스케줄링의 장단점이 특징으로 드러난다.

즉, 오버헤드가 적고 예측이 가능하나 긴 작업이 앞에 있으면 전체 대기 시간이 증가하는 convoy effect가 발생할 수 있다.

 

FCFS 부작용 Convoy Effect

이미지 출처 : 생성형 AI 자체 제작 (구글 나노 바나나2)

 

---

2-2. 최단 작업 우선 스케줄링 (SJF, Shortest Job First)

CPU 사용 시간이 가장 짧은 프로세스를 먼저 실행하는 비선점형 스케줄링 알고리즘이다. 평균 대기 시간을 최소화하는 이론적으로 최적의 알고리즘이지만 실제로는 CPU Burst 시간을 예측하기 어렵고 긴 작업은 계속 밀릴 수 있는 부작용 Starvation 현상이 발생할 수 있다.

---

2-3. 라운드 로빈 스케줄링 (RR, Round Robin)

라운드 로빈 스케줄링은 선입 선처리 스케줄링(FCFS)에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이며, 타임 슬라이스란 프로세스가 CPU를 사용하도록 정해진 시간을 의미한다. 

 

즉, 각 프로세스는 삽입된 순서대로 CPU를 이용하고 고정된 시간만큼 순환하며 실행하는 선점형 스케줄링에 해당하며, 공정성과 빠른 응답 시간을 확보할 수 있다. 하지만 고정된 시간이 너무 짧으면 문맥 교환이 자주 발생하여 오버헤드가 증가할 수 있고, 반대로 너무 길면 FCFS처럼 동작할 수 있다.

---

2-4. 최소 잔여 시간 우선 스케줄링 (SRT, Shortest Remaining Time)

최단 작업 우선 스케줄링(SJF), 라운드 로빈 스케줄링을 합친 선점형 스케줄링이다. 즉, 정해진 타임 슬라이스만큼 CPU를 이용하되 남은 실행 시간이 가장 짧은 프로세스를 우선 실행하는 알고리즘이다.

 

SJF와 같이 평균 대기 시간을 최소화할 수 있으나, 단점도 마찬가지로 실행 중에도 계속 비교해야 하므로 오버헤드가 발생하거나 긴 작업이 계속 뒤로 밀리는 Starvation 현상이 발생할 수 있다.

---

2-5. 우선순위 스케줄링 (Priority Scheduling)

우선순위 스케줄링은 프로세스마다 우선순위를 부여하고, 가장 높은 우선순위의 프로세스를 먼저 실행하는 스케줄링 방식이다. 우선순위에 따라 중요한 작업을 빠르게 처리할 수 있으나, 낮은 우선순위가 무한 대기하는 Starvation 현상이 발생할 수 있다.

 

이 문제를 해결하기 위해 에이징(Aging) 방식을 사용한다. 에이징은 오래 대기한 프로세스의 우선순위를 시간에 따라 점진적으로 증가시키는 방식이다. 이를 통해 "지금은 우선순위가 낮더라도, 결국 실행 기회를 보장"할 수 있다.

---

2-6. 다단계 큐 스케줄링 (Multi-Level Queue)

우선순위 스케줄링의 발전된 형태로, 우선순위별로 여러 개의 준비큐를 사용하는 스케줄링 방식이다.

우선순위 별 준비 큐

이미지 출처 : https://www.geeksforgeeks.org/operating-systems/multilevel-feedback-queue-scheduling-mlfq-cpu-scheduling/

 

우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 해당 큐가 비어 있게 되면 그 다음으로 우선순위 높은 큐를 확인하여 처리하게 된다.  하지만 프로세스들이 큐 사이를 이동할 수 없기 때문에, 우선순위가 낮은 프로세스의 작업이 계속 연기될 수 있다. 

---

2-7. 다단계 피드백 큐 스케줄링(Multi-Level Feedback Queue)

프로세스들이 큐 사이를 이동할 수 있어 앞서 언급한 다단계 큐의 Starvation 현상을 보완한 방식이다.

 

기본 동작 방식은 다음과 같다.

1. 새로운 프로세스는 가장 높은 우선순위 큐에 삽입된다.
2. 해당 큐에서 정해진 타임 슬라이스 동안 실행된다.
3. 실행이 끝나지 않으면 한 단계 낮은 우선순위 큐로 이동한다.

1~3번 과정을 반복하면서 CPU를 오래 사용하는 프로세스는 점점 낮은 우선순위 큐로 이동하고, 비교적 CPU를 적게 사용하는 입출력 집중 프로세스는 우선순위가 높은 큐에서 실행이 끝나게 된다. 또한 다단계 큐와 마찬가지로 에이징 기법을 적용할 수 있으며, 응답성과 처리량을 모두 균형있게 확보할 수 있다.