Choi.ethStudy

[CS] 운영체제 · Chapter 3

CPU 스케줄링

작성자: Choi.eth

10 min read

https://www.inflearn.com/course/운영체제-기술면접-비전공자?cid=337649

https://www.inflearn.com/course/운영체제-기술면접-비전공자?cid=337649

본 포스트는 인프런 “[CS 기술면접 2] 말이 트이는 운영체제” 강의를 학습하며 정리한 내용을 다룹니다.

CPU 스케줄링이란?

앞서 운영체제가 프로세스를 관리하기 위해 Ready Queue와 스케줄러를 사용한다는 내용을 살펴봤습니다. 여러 프로세스가 CPU를 사용하기 위해 기다리고 있다면, 운영체제는 어떤 프로세스를 먼저 실행할지 결정해야 합니다.

이처럼 여러 프로세스가 CPU를 기다리는 상황에서 어떤 프로세스에 CPU를 할당할지 결정하는 과정을 CPU 스케줄링(CPU Scheduling)이라고 합니다.

  • 여러 프로세스가 CPU를 기다리는 상황에서 CPU를 어떤 프로세스에 할당할지 결정하는 과정
  • 스케줄링 알고리즘을 통해 프로세스의 실행 순서 결정

CPU 스케줄링에는 여러 알고리즘이 있으며, 어떤 알고리즘을 사용하느냐에 따라 CPU 사용 효율이나 프로세스의 대기 시간이 달라질 수 있습니다.

CPU 스케줄링 성능 척도

CPU 스케줄링 알고리즘을 비교하려면 먼저 성능을 평가하는 기준을 알아야 합니다. CPU 스케줄링의 성능 척도는 크게 시스템 입장에서 중요한 지표와 프로그램 입장에서 중요한 지표로 구분할 수 있습니다.

1. CPU 이용률(CPU Utilization)

  • 전체 시간 중 CPU가 놀지 않고 실제로 작업을 수행한 시간의 비율

2. 처리량(Throughput)

  • 주어진 시간 동안 처리가 완료된 프로세스의 수

3. 대기 시간(Waiting Time)

  • 프로세스가 Ready 상태에서 CPU 할당을 기다린 총 시간
  • Ready Queue에 머문 시간의 합계

4. 응답 시간(Response Time)

  • Ready 상태의 프로세스에 최초로 CPU가 할당되기까지 걸린 시간

5. 소요 시간(Turnaround Time)

  • 프로세스가 CPU를 요청한 시점부터 원하는 만큼의 CPU를 모두 사용하는 데 걸린 시간

시스템과 프로그램 입장의 차이

각 성능 척도는 누구의 입장에서 평가하느냐에 따라 중요도가 달라집니다.

시스템 입장

시스템은 한정된 CPU 자원으로 최대한 많은 작업을 처리하는 것이 중요합니다.

  • CPU 하나로 최대한 많은 작업을 처리할수록 높은 성능
  • 주요 지표: CPU 이용률, 처리량
  • 두 지표는 값이 클수록 높은 효율

프로그램 입장

반면 프로그램 입장에서는 자신의 작업이 얼마나 빠르게 처리되는지가 중요합니다.

  • 프로그램의 작업이 최대한 빠르게 완료될수록 높은 성능
  • 주요 지표: 대기 시간, 응답 시간, 소요 시간
  • 세 지표는 시간이 짧을수록 높은 효율

즉, 시스템은 CPU를 얼마나 효율적으로 활용하는지에 집중하고, 프로그램은 자신의 작업이 얼마나 빠르게 처리되는지에 집중한다는 차이가 있습니다.

CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘을 알아보기 전에 먼저 선점형과 비선점형 스케줄링의 차이를 이해해야 합니다.

  • 선점형 스케줄링(Preemptive Scheduling): 실행 중인 프로세스가 CPU를 강제로 빼앗길 수 있는 방식
  • 비선점형 스케줄링(Non-Preemptive Scheduling): 실행 중인 프로세스가 CPU를 강제로 빼앗기지 않는 방식

이 두 가지 방식은 실행 중인 프로세스의 CPU 사용을 운영체제가 중간에 중단시킬 수 있는지에 따라 구분됩니다.

1. FCFS(First-Come First-Served)

FCFS는 가장 먼저 도착한 프로세스부터 CPU를 할당하는 방식입니다. 쉽게 생각하면 은행이나 식당에서 먼저 도착한 사람부터 차례대로 처리하는 선착순 방식과 비슷합니다.

  • 먼저 도착한 프로세스부터 순서대로 CPU 할당
  • 비선점형 스케줄링 방식
  • 실행 시간이 긴 프로세스가 먼저 도착하면 뒤에 있는 프로세스들의 대기 시간이 길어져 전체적인 처리 효율 저하

2. SJF(Shortest Job First)

FCFS는 먼저 도착한 프로세스부터 실행하기 때문에, 실행 시간이 긴 프로세스가 앞에 있으면 다른 프로세스들이 오랫동안 기다려야 하는 문제가 있습니다.

SJF는 이러한 문제를 개선하기 위해 CPU를 사용하는 시간이 짧은 프로세스부터 실행하는 방식입니다.

  • CPU Burst가 짧은 프로세스에 먼저 CPU 할당
  • 비선점형 스케줄링 방식
  • CPU Burst가 긴 프로세스는 오랜 시간 CPU를 할당받지 못하는 Starvation 문제 발생 가능

CPU Burst와 I/O Burst

프로세스는 실행 과정에서 CPU를 사용하는 작업과 입출력 장치를 사용하는 작업을 반복합니다. 각각의 작업이 진행되는 시간을 CPU Burst와 I/O Burst라고 합니다.

  • CPU Burst: 프로세스가 CPU를 사용하여 계산이나 데이터 처리 작업을 수행하는 시간
  • I/O Burst: 프로세스가 I/O 장치를 사용하여 데이터를 입력하거나 출력하는 시간

Starvation 문제

Starvation은 우선순위가 낮은 프로세스가 장시간 자원을 할당받지 못하는 상태를 의미합니다.

SJF에서는 CPU Burst가 짧은 프로세스들이 계속 도착하면 실행 시간이 긴 프로세스는 CPU를 할당받지 못하고 계속 기다리는 상황이 발생할 수 있습니다.

3. SRTF(Shortest Remaining Time First)

SRTF는 SJF와 비슷하지만, 실행 중 새로운 프로세스가 도착했을 때 다시 스케줄링한다는 차이가 있습니다.

  • SJF와 유사하지만, 실행 도중 새로운 프로세스가 도착하면 다시 스케줄링 수행
  • 선점형 스케줄링 방식
  • 현재 실행 중인 프로세스의 남은 CPU Burst 시간보다 더 짧은 CPU Burst 시간을 가진 프로세스가 도착하면 기존 프로세스의 CPU를 빼앗아 새 프로세스에 할당

즉, SJF는 한 번 CPU를 할당하면 중간에 빼앗지 않지만, SRTF는 더 짧은 작업이 도착하면 실행 중인 프로세스를 중단하고 새로운 프로세스를 실행할 수 있습니다.

4. Priority Scheduling

Priority Scheduling은 프로세스마다 우선순위를 부여하고, 우선순위에 따라 CPU를 할당하는 방식입니다.

선점형과 비선점형 모두 사용할 수 있으며, 높은 우선순위의 프로세스가 도착했을 때 어떻게 처리하는지에 차이가 있습니다.

  • 프로세스의 우선순위에 따라 CPU 할당
  • 선점형 방식: 더 높은 우선순위의 프로세스가 도착하면 현재 실행 중인 프로세스의 CPU를 빼앗아 새로운 프로세스에 할당
  • 비선점형 방식: 더 높은 우선순위의 프로세스가 도착하더라도 현재 실행 중인 프로세스를 중단하지 않고 Ready Queue에서 대기
  • 우선순위가 낮은 프로세스가 CPU를 할당받지 못하는 Starvation 문제 발생 가능
  • Starvation 문제를 해결하기 위해 에이징(Aging) 기법 사용
    • 에이징(Aging): 오랫동안 기다린 프로세스의 우선순위를 점진적으로 높여주는 기법

5. Round Robin(RR)

Round Robin은 각 프로세스에 동일한 크기의 CPU 사용 시간을 할당하고, 정해진 시간이 지나면 다음 프로세스에 CPU를 넘기는 방식입니다.

FCFS처럼 하나의 프로세스가 CPU를 오랫동안 점유하는 것이 아니라, 여러 프로세스가 짧은 시간씩 번갈아 CPU를 사용할 수 있도록 합니다.

  • 각 프로세스에 동일한 크기의 CPU 할당 시간(Time Quantum)을 부여하는 현대적인 스케줄링 방식
  • CPU 할당 시간이 지난 프로세스는 Ready Queue의 가장 뒤로 이동하여 다시 CPU 할당 대기
  • 여러 프로세스에 CPU를 빠르게 할당할 수 있어 짧은 응답 시간을 기대할 수 있다는 장점
  • CPU 할당 시간이 너무 크면 FCFS와 비슷하게 동작
  • CPU 할당 시간이 너무 짧으면 문맥 교환(Context Switching) 오버헤드 증가
  • CPU 사용 효율과 응답 시간을 고려한 적절한 할당 시간 설정이 중요

즉, Round Robin에서는 각 프로세스에 CPU를 얼마나 오래 할당할지 결정하는 Time Quantum 설정이 중요한 요소입니다.

문맥 교환(Context Switching)

앞서 Round Robin은 여러 프로세스가 CPU를 번갈아 사용한다고 했습니다. 그런데 CPU가 프로세스 A를 실행하다가 프로세스 B로 전환하려면, 프로세스 A가 어디까지 실행되었는지 기억하고 있어야 합니다.

이때 필요한 과정이 문맥 교환(Context Switching)입니다.

  • CPU가 현재 실행 중인 프로세스의 상태(Context)를 저장하고, 새로운 프로세스의 상태를 복구하여 실행을 전환하는 과정
  • 여러 프로세스를 번갈아 실행하기 위해 필요한 작업

문맥 교환의 주요 단계

1. 현재 프로세스 상태 저장

  • 현재 실행 중인 프로세스의 CPU 레지스터 값(PC, Stack Pointer 등)과 기타 실행 정보를 PCB에 저장

2. 새로운 프로세스 선택

  • 스케줄러가 Ready Queue에서 다음에 실행할 프로세스를 선택

3. 새로운 프로세스 상태 복구

  • 선택된 프로세스의 PCB에 저장된 정보를 읽어 CPU 레지스터에 실행 상태 복구

4. 새로운 프로세스 실행

  • 복구한 실행 상태를 바탕으로 새로운 프로세스의 명령어 실행

문맥 교환을 통해 CPU는 여러 프로세스를 번갈아 실행할 수 있습니다.

다만 문맥 교환 과정에서는 실행 상태를 저장하고 복구해야 하므로 추가적인 비용(오버헤드)이 발생합니다. 따라서 Round Robin처럼 CPU 할당 시간이 짧은 알고리즘에서는 문맥 교환이 지나치게 자주 발생하지 않도록 주의해야 합니다.

정리

이번에는 운영체제가 CPU를 어떤 프로세스에 할당할지 결정하는 CPU 스케줄링에 대해 살펴봤습니다.

CPU 스케줄링은 시스템의 CPU 이용률과 처리량뿐만 아니라, 개별 프로세스의 대기 시간과 응답 시간에도 영향을 미칩니다.

또한 FCFS, SJF, SRTF, Priority Scheduling, Round Robin처럼 다양한 알고리즘이 있으며, 각각 CPU를 할당하는 기준과 장단점이 다릅니다.

특히 스케줄링 과정에서 프로세스가 전환될 때는 문맥 교환이 발생하고, 이 과정에서도 비용이 발생하기 때문에 CPU 사용 효율과 응답 시간을 함께 고려해야 한다는 점이 중요합니다.