CPU Scheduling

CPU and I/O Bursts in Program Execution

CPU를 사용하는 단계와 I/O를 하는 단계

CPU-Burst Time 분포

CPU 스케쥴링이 필요하다.

• 여러 종류의 Job(Process)이 섞여있기 때문
• Interactive Job에게 적절한 Response 제공이 필요
• CPU와 I/O 장치 등 시스템 자원을 효율적으로 사용

프로세스 특성 분류

• CPU Bound Job
• CPU, 계산 위주로 쓰는 Job
• few very long CPU bursts

• I/O Bound Job
• CPU 사용 시간보다 I/O에 많은 시간을 쓰는 Job
• many short CPU bursts

CPU Scheduler & Dispatcher

• CPU Scheduler
• Ready 상태의 프로세스 중에서 CPU를 줄 프로세스를 고른다.

• Dispatcher
• CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다.
• 이 과정을 Context Switch(문맥 교환)라 한다.

• CPU Scheduling이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있을 경우임
1. Running → Blocked (I/O 요청하는 System Call)
2. Running → Ready (할당 시간 만료로 Timer Interrupt)
3. Blocked → Ready (I/O 완료 후 Interrupt)
4. Terminate
• 1, 4는 non-preemptive (자진 반납)
• 2, 3은 preemptive (강제 반납)

Scheduling Criteria

Performance Index(Performance Measure, 성능 척도)

• CPU Utilization(이용률)
• CPU를 최대한 바쁘게 유지한다.

• Throughput(처리량)
• 단위 시간당 수행을 완료하는 프로세스의 수

• Turnaround Time(소요시간, 반환시간)
• CPU가 프로세스를 실행을 시작해서 완료할 때까지의 총 시간 (기다린 시간 포함)

• Waiting Time(대기시간)
• 프로세스가 Ready Queue에서 기다린 총 시간

• Response Time(응답시간)
• 요청이 지출되고 처음 응답이 오는데 걸리는 시간 (Time-Sharing 환경에서)

Algorithm

FCFS(First-Come First-Served)

먼저온 것, 먼저 처리

단점

SJF(Shortest-Job-First)

CPU Burst Time이 가장 짧은 프로세스를 가장 먼저 스케쥴

• 각 프로세스의 다음번 CPU Burst Time을 가지고 스케쥴링에 활용

• Two Schemes
• Non-Preemptive
• 일단 CPU를 잡으면, 이번 CPU Burst가 완료될 때까지 CPU를 뺏기지 않음(Preemption)
• Preemptive
• 현재 수행중인 프로세스의 남은 Burst Time보다 더 짧은 CPU Burst Time을 가지는 새로운 프로세스가 도착하면, CPU를 빼앗김
• SRTF(Shortest-Remaining-Time-First)라고도 불림

장점

단점

• Starvation
• CPU 사용 시간이 긴 프로세스는 영원히 못 받을 수 있음

다음 CPU Burst Time의 예측

• 다음 CPU Burst Time을 어떻게 알 수 있을까?
• Input Data
• Branch
• User

• 추정(Estimate)만 가능

• 과거의 CPU Burst Time을 이용해서 추정
• Exponential Averaging

Priority Scheduling

• Priority Number는 각 프로세스와 연관되어있다.

• Highest Priority를 가진 프로세스에게 CPU 할당 (작은 수가 높은 우선 순위)
• Preemptive
• Non-Preemptive

• SJF는 일종의 Priority Scheduling이다.
• Priority = Predicted Next CPU Burst Time

• 문제점
• Starvation: 낮은 우선 순위의 프로세스는 영원히 실행될 수 없다.

• 해결 방안
• Aging: 시간이 지나면 프로세스의 우선 순위를 높인다.

RR: Round Robin

현대 컴퓨터의 CPU 스케쥴링은 이 알고리즘에 기반을 둠

특징

• 각 프로세스는 동일한 크기와 할당 시간(Time Quantum)을 가짐 (일반적으로 10 - 100ms)

• 할당 시간이 지나면 프로세스는 CPU를 빼앗기고(Preempted) 당하고, Ready Queue의 제일 뒤에 다시 줄을 선다.

• n개의 프로세스가 Ready Queue에 있고 할당 시간이 q Time Unit인 경우, 각 프로세스는 최대 q Time Unit 단위로 CPU 시간의 1 / n을 얻는다. → 어떠한 프로세스도 (n - 1) q Time Unit 이상 기다리지 않는다.

• 기다리는 시간이 CPU를 사용하는 시간에 비례함

• 일반적으로 SJF보다 Average Turnaround Time이 길지만, Response Time은 더 짧다.

장점

• 예측 필요 없음

• 어떠한 프로세스도 (n - 1) q Time Unit 이상 기다리지 않는다.

단점

• CPU 사용 시간이 비슷한 작업끼리 있으면 응답 시간은 좋으나, 다같이 오래걸리며 동시에 종료

성능

• q Large → FCFS

• q Small → Context Switch Overhead가 커진다.

Turnaround Time Varies With Time Quantum

Algorithm Evaluation

• Queueing Models



• 확률 분포로 주어지는 Arrival Rate와 Service Rate 등을 통해 각종 Performance Index를 계산

• Implementation & Measurement
• 실제 시스템에 알고리즘을 구현하여 실제 작업(Workload)에 대해 성능을 측정, 비교

• Simulation
• 알고리즘을 모의 프로그램으로 작성 후, Trace를 입력으로 하여 결과 비교

Multi-level Queue

• Ready Queue를 여러개로 분할
• Foreground(Interactive)
• Background(Batch - No Human Interaction)

• 각 큐는 독립적인 Scheduling Algorithm 가짐
• Foreground - RR
• Background - FCFS

• 큐에 대한 스케쥴링이 필요
• Fixed Priority Scheduling
• Foreground 먼저 하고 Background
• Starvation 발생 가능
• Time Slice
• 각 큐에 CPU Time을 적절한 비율로 할당
• ex) 80% Foreground RR, 20% Background FCFS

Multi-level Feedback Queue

• 프로세스가 다른 큐로 이동 가능

• Aging을 이와 같은 방식으로 구현 가능

• 프로세스 시간 예측이 필요 없음

• 짧은 프로세스 먼저

• Multi-level Feedback Queue Scheduler를 정의하는 파라미터
• Queue의 수
• 각 큐의 Scheduling Algorithm
• Process를 상위 큐로 보내는 기준
• Process를 하위 큐로 보내는 기준
• Process가 CPU 서비스를 받으려 할 때, 들어갈 큐를 결정하는 기준

Example of Multi-level Feedback Queue

• 세개의 큐
• Q0 - Time Quantum 9ms
• Q1 - Time Quantum 18ms
• Q2 - FCFS

• 스케쥴링
• New Job이 Q0으로 들어감
• CPU를 잡아서 할당 시간 9ms 동안 수행
• 9ms 안에 끝내지 못하면 Q1으로 내려감
• Q1에서 기다리다가 CPU를 잡아 18ms 동안 수행
• 18ms 안에 끝내지 못하면, Q2로 내려감

Multiple-Processor Scheduling

• CPU가 여러개인 경우 스케쥴링은 더 복잡

• Homogeneous Processor
• Queue에 한줄로 세워 각 프로세서가 알아서 꺼내가게
• 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 더 복잡

• Load Sharing
• 일부 프로세서에 Job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
• 별도의 큐를 두는 방법 VS 공동 큐를 두는 방법

• Symmetric Multi-Processing(SMP)
• 동등한 각 프로세서가 각자 알아서 스케쥴링 결정

• Asymmetric Multi-Processing
• 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

• Hard Real-Time Systems
• Hard Real-Time Task는 정해진 시간 안에 반드시 끝내도록 스케쥴링 해야함

• Soft Real-Time Computing
• Soft Real-Time Task는 일반 프로세스에 비해 높은 Priority를 갖도록 해야함

Thread Scheduling

• Local Scheduling
• User Level Thread의 경우, 사용자 수준의 Thread Library에 의해 어떤 Thread를 스케쥴할지 결정

• Global Scheduling
• Kernel Level Thread의 경우, 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 Thread를 스케쥴할지 결정

출처