[OS] Chap05. CPU Scheduling

해당 글은
경희대학교 조진성, 허선영 교수님의 강의 자료 및 내용을 정리한 글입니다
개인적으로 공부하며 작성된 글이라 잘못된 부분이 있을 수 있습니다!
오류가 있다면 알려주세요

 

 

 

 

Basic Concepts

Multi-programming이란 동시에 여러 program을 돌리는 것을 의미한다. 

이때 CPU Utilization을 최대화하기 위해서 OS는 Kernel-level thread를 scheduled한다.

 

항상 명령어만이 돌아가며 CPU를 사용하는 것이 아니다!

CPU 명령어 수행과 I/O 실행 시간이 반복(Cycle)되며 프로세스는 실행된다.

I/O brust 동안은 CPU를 사용하지 못하고, Process는 waiting 상태이다

각 Process마다 유형이 다르며,

CPU-bound process의 경우 처리할 계산량이 많은 것이고, I/O bound process의 경우 User와 Interactive하게 작용할 것이 많은 유형이라고 생각할 수 있겠다

 

 

 

CPU Scheduler

CPU scheduler는 Ready queue에 존재하는 process 중 선택하여, CPU core 중 하나로 할당하는 스케줄링을 수행한다.

 

1. running → waiting: CPU brust가 끝나고, I/O brust가 발생하는 경우
2. running → ready: 문제 발생! CPU 독점을 막기 위하거나, Interrupt가 발생한 경우
3. waiting → ready: 기다리고 있던 리소스의 사용이 가능해지는 경우
4. terminates: 수행이 끝난 경우

(1), (4)의 경우는 항상 새로운 process가 실행되기 위해서 선택이 되어야 하고,

(2), (3)의 경우는 선택할 수 있는 Scheduling에 대한 옵션이 존재한다.

 

Scheduling에 대한 옵션? ⇒ Preemptive & Nonpreemptive

 

 

▶ Preemptive & Nonpreemptive Scheduling

• Preemptive: CPU burst가 종료되지 않았음에도 다른 process를 실행할 수 있음
• Nonpreemptive: 한번 CPU burst가 시작되면, 종료 때까지 다른 process에게 brust를 넘겨주지 않음

 Nonpreemprive의 경우, 필요한 Context-Switches만 일어나기 때문에 overhead가 상대적으로 적으나

CPU brust가 아주 긴 process라면 다른 process가 과하게 기다려야 하는 문제가 발생할 수 있겠음!

따라서 Windows, Mac OS, Linux, UNIX 등 현대 OS는 대부분 Preemptive scheduling~

 

 

▶ Dispatcher

Scheduling이란 OS가 ready queue에 있는 process들 중 어떤 process를 dispatch할 지 정하는 것이다.

Dispatch란 OS가 process를 processor에 할당하는, 즉 CPU에 올리는 작업을 의미한다

Process는 ready에서 running 상태가 된다

$PCB_0$의 상태를 저장한 뒤, OS가 실행되어 scheduling을 진행한다.

 

Dispatch 과정에서 일어나는 context switching으로,

한 process를 중지하고 다른 process 실행을 시작하는 데 걸리는 시간인 Dispatch Latency가 발생한다

 

 

 

Scheduling

▶ Criteria

값이 클수록 좋은 것, 값이 작을수록 좋은 것

• CPU utilization
  • 시간당 CPU 사용한 시간의 비율
  • process를 실행 상태로 항상 유지하려고 해야함 (CPU가 busy하게끔)
• Throughput (처리율)
  • 단위 시간당 끝마친 프로세스의 수
  • 단위 시간당 완료되는 작업 수가 많도록 해야함
  • 동일한 프로세스에서 측정해야함
• Turnaround time (반환 시간) 
  • Process가 생성-종료되어 사용하던 자원을 모두 반환하는데 소요되는 시간
  • 작업이 Ready-queue에서 기다린 시간+CPU에서 실행 시간+I/O 작업 시간
• Waiting time
  • Ready queue에서 process가 실행되기를 기다리는 시간
  • Ready-queue에서 기다린 시간의 총합
• Response time
  • 요청이 제출된 시점 부터, 최초의 응답이 생성될 때까지 소요되는 시간.
  • For Time-sharing environment
  • Waiting time과 구분하기

 

 

▶ Algorithms

Ready queue안의 processes에서, 어떤 것이 CPU cores에 할당되어야 할까요?

 

First-Come First-Served (FCFS)

먼저 도착하는 Job을 우선적으로 수행한다! (FIFO)

Non-preemptive, Average waiting time이 조금 긴 편이다.

 

👍 장점

모든 Process가 동일하게 처리되기 때문에 no Starvation

 

👎 단점

Long process가 초반에 배치될 경우, Average waiting time이 길어지는 Convoy Effect가 발생할 수 있다

실행 순서의 영향을 많이 받게된다

 

 

Shortest Job First (SJF)

CPU brust가 작을 것으로 예상하는 process 부터 처리한다!

Non-preemptive, Average waiting time 측면에서 Optimal

 

👎 단점

최적일 수 있으나, 실제 next CPU burst length를 알 수가 없다

Starvation할 가능성이 존재한다

 

따라서 다음 burst length가 이전의 것과 유사하다는 가정 아래,

이전의 burst 길이를 기반으로 Exponential Averaging을 통해 예측하곤 한다

 

 

 

Shortest Remaining Time First (SRTF)

끝날 때 시작한 시간 - 도착 시간 - 이전에 작동한 시간

 

실행하던 process보다, 남은 burst time이 짧은 process가 있다면 그것을 우선적으로 처리한다!

Preemptive, SJF의 선점형 버전

 

👎 단점

하지만 마찬가지로 CPU burst를 정확하게 예측하는 것이 어려움

 

 

Round Robin (RR)

각 process에게 동일한 CPU time(Time Quantum)을 부여하고, 해당 시간 동안만 CPU를 이용하게 함. 이를 번갈아 처리한다!

Preemptive, 매 quantum마다 다음 process를 schedule하기 위한 Timer interrupts가 발생함

 

👍 장점

$N$개의 process, $q$의 time quantum 일 때, $(n-1)q$가 Maximum waiting time이고,

모든 process가 공평하게 CPU를 차지할 수 있다.

SJF와 비교했을 때 더 높은 turnaround를 보인다

 

👎 단점

$q$가 너무 커지면 FCFS와 다름 없어지고,

$q$가 너무 작아지면 모든 process가 $1/N$배 속도로 동작하는 Process Sharing 문제가 발생한다

잦은 Context-switching이 발생하기 때문에, context-switching 시간이 $q$보다 짧아야 보완이 된다.

또한 80%의 CPU burst가 $q$보다 짧아야 Turnaround time에서의 이득을 볼 수 있다

위 그림에서는 time quantum 6~7 때부터 좋아지네요

FCFS으로 처리하는 게 좋나봄. 계산해보기

 

 

Prioroty Scheduling

우선 순위에 따라서 CPU에 할당되어 처리된다!

Preemptive / Nonpreemptive

 

👎 단점

낮은 우선 순위의 process는 계속해서 실행되지 않는 문제인 Starvation이 발생할 수 있다

따라서, Aging과 같은 시간이 지나면 우선 순위를 높이는 해결 방법을 사용하기도 한다

 

Priorty Scheduling + Round-Robin : 우선 순위대로, 같은 우선 순위에서는 RR로 처리합니다

 

 

Multilevel Queue

위까지는 하나의 Ready Queue에 존재하는 process들이고, 여기서부터는 여러 개의 Ready Queue를 관리한다

Queue마다 서로 다른 scheduling algorithm을 적용하고,

우선 순위가 높은 Queue가 처리되면 다음으로 넘어간다

순서대로 넘어가기 때문에 starvation이 발생할 수 있겠군요

 

 

Multilevel Feedback Queue

따라서 위의 문제를 해결하기 위해서 Multilevel Queue 사이에서 Process가 이동할 수 있음!

Aging처럼, 시간이 갈 수록 우선 순위가 높아지는 경우 process가 Queue 사이를 이동하는거임

quantum time이 늘어나고 있군요.

 

 

▶ Multiple-Processor Scheduling

좌측이 Multiple CPU, 우측이 Multithread Cores입니다

Multiple CPU는 Process 자체가 여러 칩 들어있는 것을 의미하고,

Multithread core는 하나의 칩(process)에 여러 Core가 들어있는 것을 의미해요

 

• NUMA(Non-Uniform Memory Access)

보통의 multiple CPU는 memory를 공유하나, 이는 메모리를 공유하지 않고 각자 가져요

 

• Heterogeneous multiprocessing: multicore인데, core마다의 성능이 달라요. 모바일 CPU에 활용됨

 

Symmetric multiprocessing(SMP)

각 프로세서들은 각자의 scheduling을 수행합니다.

모든 thread가 하나의 Ready queue를 가지거나, 각 processor마다 각자의 Ready queue를 가집니다

 

 

▶ Multicore Processors

 

하드웨어 자체에서 2개의 thread를 가지면서 진행한다고 생각하면 됩니다. 해당 thread는 kernel thread임

아래 동작은 하나의 Core에서 이루어지고요!

2개의 thread가 번갈아서 동작하면서 동시에 돌아가는 것처럼 수행됩니다.

Computer cycle이 겹칠 수는 없어요! 그래서 번갈아서 됨

 

 

Chip-multithreading(CMT)

Hyperthreading

Hardware 상의 core는 4개인데, Logical core가 8개 인 것 처럼! 작동합니다

OS 상에서는 8개 인걸로 보이는거죠.

scheduling도 이에 따라서 수행됩니다.

결국 concurrency하게 실행되겠지만, 하드웨어에서 이를 관리하면서 context switching에 대한 load가 작아진다는 장점이 있어요

 

Two-levels of scheduling

 

1) 운영체제가 logical CPU에서 실행할 software thread를 결정하고,

2) 각 core가 physical core에서 실행할 hardware thread를 결정합니다

 

 

Load Balancing

SMP에서 각 core에 Load를 고르게 분배하는 것이 중요합니다

• Push migration: Kernel은 각 process가 얼마의 workload를 가지고 있는지 check합니다
• Pull migration: Processor이 자신이 Idle 상태인 경우, 다른 Processor의 workload를 빼앗아 옵니다

하나의 코어에서 일어나는건 scheduling

여러개의 코어에서는 코어 간 load를 분배함

 

 

Processor Affinity

Thread를 여러 개 생성해두면, 어떤 processor에서 실행할 지를 미리 설정할 수 있습니다.

• Soft affinity: 꼭 이 process가 해당하는 core에서 실행되지 않아도 되나, 되면 좋고
• Hard affinity: 꼭 여기에서 실행해주~

 

 

 

 

Real-Time CPU Scheduling

Real-time이란, Dead Line이 존재하는 Task를 처리하는 것을 의미

• Soft real-time system: 되도록 deadline 엄수! 따로 guarantee가 존재하지는 않음 
• Hard real-time system: 반드시 엄수!

 

 

▶ Periodic Task Scheduling

발생 주기 $p$마다 task가 발생하며, task는 dead line이 존재합니다

• 0 ≤ $t$ ≤ $d$ ≤ $p$
• Rate to periodic task $1/p$

Preemptive, Priority-based Scheduling

우선 순위가 낮아지는지, 아닌지

 

Rate Monotonic Scheduling (RM)

Priod가 긴 경우, 우선 순위가 낮아집니다

예를 들어 $p_1$ period: 50, $p_2$의 period: 100이라면

p_1이 p_2보다 높은 우선순위를 가지는 것

 

Earliest Deadline First Scheduling (EDF)

Deadline이 가까울 경우, 우선 순위가 높아집니다

​

 

 

Algorithm Evaluation

알고리즘을 선택하는 기준에는 무엇이 있을까요?

• Minimum Turn-Around time
• Minimum average waiting time

Deterministic Modeling: 지정된 workload를 사용하여 각 알고리즘의 성능을 정의하는 analytic evaluation

 

계산하는 예시