CPU 스케줄링

Lee Jeong Min·2022년 4월 25일

운영체제

목록 보기

5/12

프로그램 실행에서의 CPU와 I/O Bursts

CPU-burst Time의 분포

CPU를 짧게 쓰고 I/O bound가 끼어드는 작업을 I/O bound job
CPU를 오랫동안 쓰는 프로그램을 CPU bound job이라고 함

여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다.

interactive job(I/O)에게 적절한 response 제공 요망
CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

프로세스의 특성 분류

프로세스는 특성에 따라 다음 두 가지로 나눈다.

I/O-bound process
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
- (many short CPU bursts)
CPU-bound process
- 계산 위주의 job
- (few very long CPU bursts)

CPU Scheduler & Dispatcher

CPU Scheduler

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

Dispatcher

CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
이 과정을 context switch(문맥 교환)라고 한다.

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다

1. Running -> Blocked(I/O 요청하는 시스템 콜)
2. Running -> Ready(할당 시간 만료 후 timer interrupt)
3. Blocked -> Ready(I/O 완료후 인터럽트)
4. Terminate

1번과 4번의 스케줄링은 비선점형(nonpreemptive) = 강제로 빼앗지 않고 자진 반납
2번 3번은 선점형(preemptive) = 강제로 빼앗음

현대의 스케줄러는 대부분 선점형을 사용하고 있음

스케줄링 알고리즘

FCFS (First-Come First-Served)
SJF (Shortest-Job-First)
SRTF (Shortest-Remaining-Time-First)
Priority Scheduling
RR (Round Robin)
Multilevel Queue
Multilevel Feedback Queue

스케줄링 척도(Scheduling Criteria)

성능 척도의 요소

CPU utilization (이용률)

CPU가 놀지 않고, 일을 한 시간
Throughput (처리량)

주어진 시간동안 몇개의 작업을 완료했는지
Turnaround time (소요시간, 반환 시간)

CPU burst가 끝나고 나갈때까지의 시간을 말함
Waiting time (대기 시간)

CPU를 사용하기 위해 ready queue에서 기다린 시간
Response time (응답 시간)

처음으로 CPU를 얻은 시간

FCFS(First-Come First-Served)

먼저 온 프로세스를 먼저 처리

➡️ 그렇게 효율적이지는 않다.

비선점형이다.

Convoy effect란? ➡️ 앞의 긴 작업 때문에 큐에서 짧은 작업들이 기다리는 현상

SJF (Shortest-Job-First)

각 프로세스의 다음번 CPU burst Time을 가지고 스케줄링에 활용하여 이 시간이 가장 짧은 프로세스를 제일 먼저 스케줄한다.

Two schemes:

Nonpreemptive
- 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
Preemptive
- 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
- 이 방법은 Shortest-Remaining-Time-First(SRTF)이라고도 부른다.

이 SJF는 주어진 프로세스들에 대해 minimum average waiting time을 보장! --> SJF의 preemptive 버전

SJF의 문제점

starvation
➡️ CPU burst가 긴 작업들은 영원히 작업을 수행할 수 없음
CPU 사용시간을 미리 알 수 없음
➡️ 과거에 얼마나 쓴지 확인해서 추측은 가능

Priority Scheduling

각 프로세스와 연관된 우선 번호를 이용하여 높은 우선순위를 가진 프로세스에게 CPU 할당(작은 숫자가 우선순위가 높음)

Preemptive
nonpreemptive

SJF는 일종의 priority scheduling 이다(CPU burst time이 우선순위)
➡️ priority = predicted next CPU burst time

문제

starvation: 낮은 우선순위는 영원히 실행 X

해결

Aging: 시간이 지날수록 프로세스의 우선순위를 높임

RR (Round Robin)

현대적인 CPU 스케줄링은 RR에 기반함.

장점은 응답시간이 빠르다는 것!

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐(일반적으로 10-100 milliseconds)
할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
➡️ 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
Performance
- q large => FCFS
- q small => context switch 오버헤드가 커진다.

특징:

기다리는 시간(waiting)이 자신이 CPU를 사용하려는 시간(CPU bursts)과 비례한다.
time quantum을 몇으로 설정하느냐에 따라 average turnaround time이 달라진다.

Multilevel Queue

Ready queue를 여러 개로 분할

foreground(interactive)
background(batch - no human interaction)

각 큐는 독립적인 스케줄링 알고리즘을 가짐

foreground - RR
background - FCFS

큐에 대한 스케줄링이 필요

Fixed priority scheduling
- serve all from foreground then from background
- Possibility of starvation
Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
- Eg., 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

프로세스가 다른 큐로 이동 가능
에이징을 이와 같은 방식으로 구현할 수 있다
Multilevel-feedback-queue scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫒는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

Multiple-Processor Scheduling

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐

Homogeneous processor인 경우

Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
반드시 특정 프로세스에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐

Load sharing

일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘의 필요
별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

Symmetric Multiprocessing (SMP)

각 프로세서가 각자 알아서 스케줄링 결정

Symmetric: 대칭이라는 의미

Asymmetric multiprocessing

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

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를 스케줄할지 결정

Algorithm Evaluation

알고리즘 성능 측정 방법

Queuing models

확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
Implementation & Measurement

실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교(리눅스 커널에 소스코드를 바꿔서 직접 실험)
Simulation

알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교
2번째와 같이 실제 실험을 하는 것은 아님(리눅스 소스 코드 커널을 직접 수정하거나 그러지는 않음)