[5] CPU Scheduling

[ 5-1 : CPU Scheduling ]

 

Multiprogrammed OS의 기초

CPU Utilization을 최대화하기 위해

 

Conccurency(Multiprogramming)의 전제조건

CPU가 너무 빨라 하나의 Process만 실행하기에는 CPU가 노는 시간이 많으니, Context-Switch를 통해 PCB를 빠른 시간안에 교체하면서, 시간을 나눠서(time sharing) CPU 자원을 interleaving해도 이용에 지장에 안감.

몇몇 프로세스를 항상 실행하기 위해, 그리고 CPU utilization을 최대화하기 위해.

 

프로세스를 조사해보니, CPU를 직접 사용하는

(1) CPU burst time이 큰 프로세스는 많지 않고, 대신

(2) I/O burst time이 많은 프로세스가 더 많은 경향이 있었다.

→ 프로세스마다 (1), (2)로 나뉘므로, 상황에 따라 적절하게 해결법을 결정해야 함.

 

[ CPU Scheduler ]

Ready 상태에 있는 프로세스에 CPU를 할당해주는 것.

 

- FIFO Queue

- Priority Queue

우선순위는 어떻게 결정하지?

 

[ Preemptive vs  Non-Preemptive ]

[1] Non-preemptive scheduling

프로세스가 CPU를 선점하고 나면 자발적으로 terminate or switch하기 전까지 계속 위치.

[2] Preemptive

스케줄러에 의해 프로세스를 wait state로 강제로 보낼 수 있다.

 

Decision Making for CPU-Scheduling

Preemptive의 경우 중간에 강제로 들어가거나 나갈 수 있다.

(1) Waiting state에서 우선순위가 높아진다면 바로 Ready state로 진입하거나,

(2) Running state에서 time out이 된다면 Ready state로 강제로 이동.

이 발생할 수 있다.

 

Non-preemptive는 자발적으로 나오는 것을 기다려야 하므로 효율이 낮고,

Preemptive는 선택권이 넓으니, 보통 Preempitve를 사용한다.

 

[ Dispatch ]

CPU 스케줄러에 의해 선택된 프로세스에게 CPU Core의 control을 넘겨주는 module.

기능 : Context Switching

user mode로 switching

PCB를 교체해야 하므로 엄청 빨라야한다.

 

[ Scheduling Criteria ]

- CPU Utilization : 가능한 하나의 CPU를 바쁘게 유지

- Throughput : 단위 시간내에 완료되는 프로세스의 수

- Turn around Time : 실행 - 완료 사이의 시간

- Waiting Time : Ready Queue내의 대기시간 합

 

 

[ Scheduling Algorithm ]

 

CPU Scheduling Problem

Ready Queue에 있는 프로세스 중 어느 프로세스에 CPU를 할당할 것인가?

 

Solution Overview

[1] FCFS : First Come, First Served

[2] SJF : Shortest Job First

[2-1] SRTF : Shortest Reamining Time First → 전체시간 전부 할당

[3] RR : Round Robin → time sharing (interleaving)

[3-1] Priority-based : (RR에서 다음 process 선택시 우선순위 사용)

[4] MLQ : Multi-Level Queue

[4-1] MLFQ : Multi-Level Feedback Queue

 

[1] FCFS

FIFO Queue로 구현 : 먼저 요청 → 먼저 할당

Avg waiting time이 최소는 아니고, CPU bust time이 다양하다면 어떤 순서로 오냐에 따라 상당히 다양해진다.

Non-preemptive에 해당.

 

[ Convoy Effect ]

 : 다른 모든 프로세스들이 한 프로세스의 긴 처리시간을 기다리는 것.

CPU utilization 감소를 불러옴.

 

[2] SJF : Shortest-next-CPU-burst-first scheduling

Next CPU burst가 가장 작은 것을 할당.

만약 여러 개가 같다면, FCFS 사용. (먼저 요청한 것)

 

아마도 optimal하다

→ Average waiting time이 최소임을 보장함.

 

하지만, 구현은 어떻게 해야할까?

"Next" CPU burst time을 알 수 있는 방법이 없음.

처리가 다 끝나야 burst time을 알 수 있기 때문.

 

SJF를 Approximate(근사화하여 구현)를 할려고 해보자

next CPU burst time을 예측할 수 있을지도 모른다.

[ How to Predict next CPU burst? ]

과거에 측정된 CPU burst를 통해 exponential average을 구해보자.

CPU burst time을 기록하는 것도 힘들기 때문에 SJF는 실질적으로 optimal은 아니게 됨.

이론상 Optimal이므로 다른 알고리즘과 비교하기 위해 언급한 것.

 

SJF는 preemptive일수도 있고, non-preempitve일수도 있다.

새로운 process가 도착했을 때, 이전 프로세스가 이미 실행중이어도 새로 들어온 process가 짧다면 쫓아내고 먼저 실행하는 것이 더 좋음.

그런데, Ready Queue에 들어갈 때마다 실행중인 process의 남은 burst time을 아는 것이 쉽지 않음.

→ [2-1] SRTF(Preempitve-SJF) : Shortest-Remaining-Time-First

SJF보단, 더 optimal에 가깝다.

거의 가장 Optimal Algorithm에 해당함.

 

[3] Round Robin Scheduling

Preemptive FCFS with a time quantum

10~100ms의 시간 제한을 두고, 계속 교체하는 방식

Ready Queue : circular queue로 구현

 

1) 만약 CPU burst가 time quantum보다 짧은 경우

→ process가 스스로 CPU를 빠져나옴.

2) 만약 CPU burst가 time quantum보다 더 긴 경우

→ 시간이 다 되면 OS에 Interrupt를 걸어줌.

Context-Switch가 일어나고, 다시 ready queue의 끝으로 이동.

RR에서, Average waiting time은 좀 더 길어질 수 있다. 하지만, 나중에 SJF와 섞는다면 더 효율적.

RR은 프로세스의 정해진 시간이 끝날 때 마다 선점당하고 다시 ready queue에 넣으므로 Preemptive.

 

- Performance

time quantum의 크기에 매우 영향을 많이 많음.

Context-Switch가 발생할 때 마다, Dispatch latency가 생기기 때문.

→ 너무 작으면 Context-Switch가 자주 발생하고, 너무 크면 FCFS와 비슷해지므로 적정 크기를 찾아야 함.

 

[3-1] Priority-base Scheduling

(low CPU burst → High Priority), highest priority를 갖는 process를 할당.

같은 priority라면 FCFS.

SJF도 priority-base의 한 종류

 

Priority Scheduling은 Preemptive or Non-Preempitve가 될 수 있다.

 

[ The problem of Starvation (indefinite blocking) ]

둘 다 해당되는데, High Priority가 계속 들어온다면, Starvation이 발생할 수 있음.

Priority가 낮은 프로세스는 스케줄링되지 않는 것.

 

Solution : Aging

주기적으로 프로세스들의 priority를 증가시켜주는 것.

오래 스케줄되지 않은 프로세스는 priority가 계속 증가함.

 

[ Combine RR and Priority scheduling ]

 

[4] MLQ : Multi-Level Queue

프로세스의 용도에 따라 Priority가 다를 것이므로, 여러 개의 Priority를 갖는 Queue를 사용하자는 것.

위로 갈수록 High Priority Queue에 해당.

 

 

[4-1] MLFQ : Multi-Level Feedback Queue

[4] MLQ의 문제점은, Queue 단위의 Starvation이 발생할 수 있다.

CPU bound가 높은 Process일수록 Time Quantum을 높게 주고, 낮을수록 Priority를 높게 주고, Quantum을 작게줘서 자주 할당될 수 있게 해서 Starvation을 방지.

Modern OS가 이 방식을 기반으로 사용.

 

[ Thread Scheduling ]

운영체제 커널입장에서는, kernel threads만 스케줄링하면 된다.

user thread는 thread library에 의해 관리되기 때문.

kernel은 user threads에 대해 알지 못한다.

그래서 kernel threads을 user threads에 매핑만 시켜주면 됨.

 

그래서 O/S 커널은 kernel thread에 대해서만 스케줄링하면 된다.

여태 배운 스케줄링을 kernel threads를 대상으로 적용시키면 됨.