[운영체제] #6. CPU Scheduling 이란?

Basic Concepts

Scheduling

CPU Scheduling은 여러 프로세스가 CPU를 효율적으로 사용할 수 있도록 우선순위와 순서를 결정하는 메커니즘
Multiprogramming 환경에서 메모리에 여러 프로세스가 대기(Ready State) 중인 경우, CPU를 어떤 프로세스에 할당할지 결정.
CPU 사용 효율과 처리량(Throughput)을 최대화하는 것이 목표이다.

Process 수행 사이클의 구성

CPU-I/O Burst Cycle
- 프로세스는 CPU를 사용하는 작업과 I/O를 기다리는 작업이 주기적으로 반복됨.
  - CPU Burst: CPU에서 연산을 수행하는 시간.
  - I/O Burst: I/O 작업을 수행하거나 기다리는 시간.
Process 분류에 따른 CPU Burst 특징
- CPU-Bound Process
  - 짧은 주기의 긴 CPU Burst 사용
    ex) 머신러닝 모델 계산, 비디오 렌더링
- I/O-Bound Process
  - 긴 주기의 짧은 CPU Burst 사용
    ex) 파일 다운로드, 프린터 작업

=> 어떤 종류의 Process 가 많은지에 따라 스케줄링 기법의 효율성이 달라진다.

Histogram of CPU-Burst Times

대부분의 프로세스는 긴 주기의 짧은 CPU Burst (I/O-Bound Process) 를 가지며, 소수의 프로세스만 긴 Burst를 가짐.
서로 다른 Process, System에도 불구하고, 대체적으로 아래 그래프와 같은 경향을 보인다.

Scheduling 의 종류

CPU Scheduling 의 결정은 다음 시점에 따라 이루어진다.
1. Running 에서 Waiting 상태로
2. Running 에서 Ready 상태로
3. 수행 종료
4. Ready 에서 Running 상태로
비선점형 스케줄링 (Non-preemptive Scheduling)
- 1, 3 상황에서만 수행
- 한 번 CPU 를 할당받으면 작업이 끝날 때까지 CPU 를 계속 사용
선점형 스케줄링 (Preemptive Scheduling)
- 그 외 다른 Scheduling 기법
- 실행 중이 프로세스라도, 더 높은 우선순위를 가진 프로세스가 Ready 상태가 되면 CPU 를 빼앗김

Scheduling Criteria

CPU 사용률 (CPU Utilization) : 전체 시스템 시간 중 CPU 가 작업을 처리하는 비율
처리량 (Throughput) : CPU 가 단위 시간 당 처리하는 프로세스의 개수
응답 시간(Response Time) : 사용자가 요청한 작업의 첫 번째 응답이 오기까지 걸리는 시간
대기 시간(Waiting Time) : 프로세스가 Ready Queue 에서 기다리는 시간
Turnaround Time : 프로세스가 시작해서 끝날때까지 걸리는 시간
- CPU Burst + I/O Burst + Waiting Time
이상적인 스케줄러
- 최대 CPU 사용률
- 최대의 처리량
- 최소의 응답시간
- 최소의 대기시간
모든 조건을 만족시키는 Scheduler 를 만드는 것은 현실적으로 불가능
시스템의 용도에 따른 요구사항이 달라진다.
- 슈퍼 컴퓨터 - CPU 사용률
- 개인용 컴퓨터 - 응답시간
- 워크 스테이션 - 처리량

Scheduling Algorithms

First-Come, First-Served Scheduling (FCFS) : 요청 순서대로 프로세스를 처리
Shortest Job First (SJF) : 다음 CPU Burst 가 가장 짧은 프로세스에 CPU 를 먼저 할당
Priority Scheduling : 프로세스의 우선순위에 따라 CPU 할당
Round-Robin Scheduling (RR) :고정된 시간 (Time Quantum) 단위로 CPU 를 순환하며 할당
Multilevel Queue Scheduling : 여러 대기 큐를 사용하여 프로세스 유형에 따라 분리
Multilevel Feedback Queue Scheduling : 프로세스가 실행 중에 다른 큐로 이동할 수 있는 다단계 큐 스케줄링

1. FCFS Scheduling

먼저 CPU 할당을 요청한 Process 에 CPU 를 먼저 할당한다.
- FIFO Queue 를 사용하여 간단하게 구현 가능
- 비선점형 스케줄링
예제

Process	Burst Time
P1	24
P2	3
P3	3

(1) 여기서, P1, P2, P3 순서로 요청하였을 때,

대기 시간 : P1 = 0, P2 = 24, P3 = 27
평균 대기 시간 : (0+24+27) / 3 = 17

(2) 여기서, P2, P3, P1 순서로 요청하였을 때,

대기 시간 : P1 = 6, P2 = 0, P3 = 3
평균 대기 시간 : (6+0+3)/3 = 3

=> (1) 의 경우 보다 짧은 대기 시간을 가짐

즉, 작업의 수행 순서에 따라 대기 시간이 변할 수 있다.

2. SJF Scheduling

다음 CPU Burst Time 이 가장 짧은 Process 에 CPU 를 먼저 할당한다.
- 최소의 평균 대기 시간을 제공
비선점형 방식
- 한 번 CPU 를 할당 받으면 자신의 CPU Burst Time 이 끝나기 전에는 놓지 않는다.
선점형 방식
- CPU 를 할당 받아 수행 중이더라도 CPU Burst Time 이 자신의 현재 남은 시간보다 짧은 시간을 가진 프로세스가 생성되면 CPU 를 양보한다.
- Shortest Remaining Time First Scheduling (SRTF)
예제

Process	Arrival Time	Burst Time
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

비선점형 SFJ Scheduling 결과
- 대기 시간 (Turnaround Time - Burst Time) = (전체시간 - arrival Time) - Burst Time
  - P1 = (7-0) - 7 = 0
  - P3 = (8 - 4) - 1 = 3
  - P2 = (12-2)-4 = 6
  - P4 = (16-5) - 4 = 7
- 평균 대기 시간 : (0+6+3+7) / 4 = 4
선점형 SFJ Scheduling 결과
- 대기 시간 (Turnaround Time - Burst Time) = (전체시간 - arrival Time) - Burst Time
  - P1 = (16-0) - 7 = 9
  - P3 = (5-4) - 1 = 0
  - P2 = (7-2) - 4 = 1
  - P4 = (11-5) - 4 = 2
- 평균 대기 시간 : (9+1+0+2) / 4 = 3

3. Priority Scheduling

프로세스 우선순위를 기준으로 CPU를 할당
- 비선점형 방식 : CPU 를 할당받은 프로세스가 작업을 끝날 때까지 CPU 를 점유
- 선점형 방식 : 더 높은 우선순위를 가진 프로세스가 도착하면, 현재 작업 중인 프로세스를 중단하고 CPU 를 빼았음
문제점 : 기아 상태 (Starvation)
- 낮은 priority 를 가진 프로세스는 CPU 를 거의 할당받지 못해 영구적으로 대기할 수 있음
- 이 문제는 선점형 방식에서 두드러짐
해결 방법 : Aging
- 대기 시간이 길어질 수록 프로세스의 prioirty 를 점차적으로 높여, 결국 실행되도록 보장

4. Round Robin Scheduling

CPU 를 프로세스에 고정된 시간 단위(Time Quantum) 동안 순환적으로 할당
- 선점형 Scheduling 방식
- 보통 Time Quantum 은 10-100 milliseconds
- Time Quantum 만큼 수행 한 Process 는 Ready Queue 의 끝으로 들어가 다시 할당을 기다림\
- Context Switching 이 많은 반면, 응답 시간이 짧
예제 (Time Quantum = 20)

Process	Burst Time
P1	53
P2	17
P3	68
P4	24

Ready Queue 내의 Process : n 개
Time Quantum : q 시간
각각의 Process 가 할당 받는 시간 : 1/n 만큼의 CPU 시간을 q 로 쪼개어 할당 받음
각 Process 의 다음 Time Quantum 이 돌아오기까지의 대기 시간 : 최대 (n-1) x q
성능
- q 가 클 경우 : FCFS
- q 가 작을 경우 : 문맥 전환 (Context Switching) 에 필요한 시간보다 낮다면 효율이 매우 떨어짐

4. Multilevel Queue Scheduling (MQS)

Ready Queue 를 여러 개의 Queue 로 분리하여 각각에 대해 다른 기법을 사용
- ForeGround Queue
  - Interactive 한 동작이 필요한 Process 를 위한 Queue
  - Round Robin 기법 사용
- BackGround Queue
  - CPU 연산 작업을 주로 수행하는 Process 를 위한 Queue
  - FCFS 기법 사용
각 Queue 에 대해 CPU 를 어떻게 할당할 것인지를 결정해야 함
- Queue 에 대한 Prioirty 또는 Time Slice 를 사용할 수 있음

Real-Time Processes
- 가장 높은 우선순위를 가진 Queue.
- Real-Time 시스템에서 사용하는 프로세스는 시간 민감도가 높으며, 즉각적인 처리가 요구된
- 주로 선점형 스케줄링이나 Round Robin 알고리즘이 적용된다.
- 예:
  - 의료 모니터링 시스템.
  - 로봇 제어 프로그램.
Normal Processes
- 우선순위가 중간 정도인 일반적인 작업들을 처리하는 Queue.
- 사용자가 요청하는 일반 프로그램(예: 텍스트 편집기, 웹 브라우저 등)이 포함된다.
- FCFS(First-Come, First-Served)나 Round Robin 스케줄링을 주로 사용.
Batch Processes
- 우선순위가 가장 낮은 Queue.
- 배치 처리는 시간이 중요하지 않은 대량 작업(예: 데이터 분석, 백그라운드 데이터 처리)을 의미한다
- 일반적으로 비선점형 스케줄링(예: FCFS, SJF)이 사용된
- 예:
  - 대규모 로그 처리.
  - 데이터베이스 백업.

5. Multilevel Feedback Queue Scheduling (MLFQ)

프로세스가 서로 다른 Queue로 이동할 수 있는 방식 (aging 의 한 방법)
프로세스의 특성과 실행 시간에 따라 다른 Queue로 이동하여 CPU 자원을 동적으로 활용.
필요한 요소들
- Queue 의 개수
- 각 Queue 마다의 Scheduling 기법
- 언제 Process 를 한 단계 높은 Queue 로 옮길 것인가
- 언제 Process 를 한 단계 낮은 Queue 로 옮길 것인가
- 어떤 Process 가 특정한 Service 를 필요로 할 때, 그것을 제공하는 Queue 로 옮겨줄 방법

: Time Quantum = 8ms
$Q_{1}$: Time Quantum = 16ms
$Q_{2}$: FCFS (First-Come, First-Served)

새로운 프로세스 도착
- 처음에는 높은 우선순위 Queue ($Q_{0}$)에서 실행.
- $Q_{0}$ 에서 8ms 동안 실행.
- 작업이 완료되지 않으면 $Q_{1}$ 으로 이동.
$Q_{1}$ 에서 실행
- 16ms 동안 실행.
- 작업이 완료되지 않으면 $Q_{2}$ 로 이동.
$Q_{2}$ : FCFS로 처리
- 가장 낮은 우선순위 Queue에서 FIFO 방식으로 실행.

=> 즉, 생성되고 8 + 16 ms 동안 종료되지 않은 Process는 많은 CPU 작업을 필요로 하는 Process로 간주하여 FCFS 기법을 이용해 충분한 CPU Time을 할당해주는 Scheduling 방법

Multiple Processor Scheduling 의 구분

여러 CPU를 사용하는 시스템에서, 프로세스와 CPU 간의 스케줄링을 효율적으로 관리.
비대칭 멀티프로세싱 (Asymmetric MultiProcessing)
- 하나의 CPU 만 스케줄링, I/O 작업을 처리
- 나머지 CPU 는 계산 작업만 담당

대칭 멀티프로세싱 (Symmetric MultiProcessing)
- 모든 CPU 가 스케줄링과 작업 처리를 균등하게 담당
- 대부분의 현대 시스템에서 사용

Multiprocessor Scheduling 방식

Processor Affinity
- 특정 프로세스가 과거에 실행된 CPU 에 다시 할당되도록 보장.
- 프로세스가 캐시 데이터를 재사용할 수 있어 속도 증가
Load Balancing
- 모든 CPU 에 균등하게 작업 분배
- Ready Queue 가 여러 개일 경우, Queue 간의 작업량을 조정하여 부하를 분산
- CPU 가 동일할 경우, 동일한 Process 를 수행할 수 있음
- CPU 마다 각각의 Ready Queue 를 둘 경우 : 일부 CPU 에 Process 가 집중될 수 있음
- CPU 모두에 하나의 Ready Queue 만을 둘 경우 : 사용 가능한 CPU 에 차례대로 Process 를 배정

저작자표시 비영리 변경금지 (새창열림)

하얀해킹