[운영체제] Chapter 5. CPU Scheduling

경희대학교 허선영 교수님의 운영체제 수업을 기반으로 정리한 글입니다.

 

Basic Concepts

• Multiprogramming: multiple program을 concurrent하게 작동 -> 목표: maximize CPU utilization
  
  • multiple process를 동시에 관리
• Kernel-level threads -> os에 의해 scheduled
  • process scheduling & thread scheduling -> 종종 혼용돼서 사용
  • scheduling은 정확히 말하면 thread scheduling!! 
• process는 항상 ready 상태가 X -> data, resource를 기다리는 상황이 있을 수 있음 -> 이때, 바로 다른 process를 실행
• Process execution -> CPU execution & I/O wait의 cycle
  
  • CPU burst distribution is main concern

 

CPU Scheduling 

1. CPU Scheduler

• CPU scheduler -> ready queue에 위치한 processes 중 하나에 CPU core를 할당
• CPU scheduling이 발생하는 순간
  1. running -> waiting state: 실행되다가, 다른 I/O를 기다리기 위해 wait state로 -> I/O는 wait 상태 process 중 선택
  2. running -> ready state: interrupt
  3. waiting -> ready: 중요한 process -> 우선순위가 더 높음 -> 현재 실행되는 process를 쫓아내고 실행될 수 있음
  4. Terminates: terminate 시에 core가 empty -> scheduling

• case 1 & 4 -> new process(ready queue에 존재하는)가 반드시 하나 실행돼야 함
• case 2 & 3 -> scheduling의 선택권이 발생

 

2. Preemptive & Nonpreemptive Scheduling

• Nonpreemptive scheduling: Running process가 CPU를 release하기전(terminatingor switching to the waiting state)까지 CPU 권한 유지
  
  • case 1 & 4
  • 규모가 작은 computing device
• Preemptive scheduling: Running process가 실행 도중에 preempted될 수 있음 
  
  • case 1, 2, 3, 4 어디서든 발생 가능
  • 몇몇의 processes가 data를 공유하는 상황에서 발생할 수 있음 -> 대부분의 복잡한 OS
• 대부분의 modern OS(Windows, MacOS, Linux, and UNIX) -> preemtive scheduling algorithms 사용

 

3. Scheduling Criteria

- How optimal is a scheduling algorithm?

• CPU Utilization: CPU를 가능한 한 바쁘게 유지
  
  • 개념적으로는 0 ~ 100 percent (in a real system, range from 40 to 90 percent)
  • 100에 가까울수록 positive
• Throughput: 단위 시간 동안 완료된 processes의 수
  • CPU & Throughput은 positive할수록 좋은 지표
• Turnaround Time: 특정 process를 실행하는 데 걸리는 총 시간
  
  • waiting in the ready queue, executing on the CPU, doing I/O의 총합
  • process가 완료된 시간 - 프로세스가 도착한 시간 -> Completion Time - Arrival Time
• Waiting Time: process가 ready queue에서 대기(wait)한 총 시간
  • waiting in the ready queue -> turnaround time의 일부
• Response Time: process가 처음 실행되는 시간에서 프로세스가 도착한 시간을 뺀 시간
  • FirstRun Time - Arrival Time

 

Scheduling Algorithms

• Problem -> ready queue의 어떤 processes가 CPU cores를 할당받을 것인가?
• Algorithms
  • First-Come First-Served (FCFS) Scheduling
  • Shortest-Job-First (SJF) Scheduling
  • Round-Robin (RR) Scheduling
  • Priority Scheduling
  • Multi-level Queue Scheduling
  • Multi-level Feedback Queue Scheduling

1. First-Come First-Served (FCFS) Scheduling

• Policy: CPU를 먼저 요청한 process 먼저 schedule -> Nonpreepmtive (먼저 cpu를 점유 -> 다른 processes 접근 X)
  
  • FIFO Queue를 이용하여 구현이 쉬움
  • Average waiting time이 보통 quite long

-> 상황에 따라 waiting time이 크게 벌어질 수 있다.

 

• Convoy Effect: Short process behind Long process
  
  • 하나의 CPU bound와 many I/O-bound processes

Burst: 어떤 현상이 짧은 시간 안에 집중적으로 일어나는 것

Input/output(IO): 파일을 읽고 쓰거나, 네트워크 어딘가에 있는 다른 존재와 데이터를 주고받거나, 모니터/마우스 같은 입출력 장치와 데이터를 주고 받는 것을 IO라고 한다.

CPU burst: 프로세스가 CPU에서 한 번에 연속적으로 실행되는 시간을 의미 -> 메모리에 올라간 프로세스가 자신의 차례가 되어, CPU에서 실행될 때, 자신의 instructions가 CPU에서  연속적으로 실행되는 시간

IO burst: 프로세스가 IO 작업을 요청 -> 그 결과를 기다리는 시간

-> 앞 부분은 I/O bound job -> CPU를 짧게 사용(short CPU burst)
-> 뒷 부분이 CPU bound job -> CPU를 길게 점유(long CPU burst)
-> CPU bound job이 CPU를 너무 길게 점유하면, I/O bound job의 대기 시간이 너무 길어짐
-> 적절한 Scheduling 필요

참고자료: https://velog.io/@hosunghan0821/CPU-Bound-IO-Bound

 

2. Shortest-Job-First(SJF) Scheduling 

• policy: 짧은 job 먼저 schedule -> Nonpreemptive
  • 다음 CPU burst의 길이가 가장 짧은 process부터 schedule을 진행
• How do we determine the length of the next CPU burst?
  • ask the user
  • estimate
• 구현이 가능하다는 가정 하에 -> average waiting time 측면에서는 Optimal한 성능을 보임
• Preemptive version -> Shortest-remaining-time-first

- Nonpreemptive version (Shortest  Job First)

 

- Determining Next CPU Burst Length

• next CPU burst의 length를 알 방법이 X 
  
  • 추정만 가능
• 일반적으로 이전 bursts 길이의 exponential averaging으로 예측

-> α는 hyper parameter로, 이전 예측값과 실제 길이 중에서 어디에 더 가중치를 부여할지 결정

-> 보통 1/2로 설정

 

- Preemptive version (Shortest Remaining Time First)

• arrival time이 다르다 가정
• 남은 burst time이 가장 짧은 process부터 우선적으로 실행

 

3. Round Robin(RR) Scheduling

• 각 process는 time quantum(or time slice)라는 CPU time의 작은 단위를 가짐 - 보통 10 - 100 miliseconds
• 해당 시간이 지나면 process는 preempted -> ready queue의 마지막에 추가
  • Timer는 매 quantum마다 interrupt 요청 -> other process로 context switching
• n processes in the ready queue, quantum: q -> 최소 (n - 1)q time units 안에 response를 받을 수 있음 -> 최대 대기 시간
• 일반적으로, average turnaround time은 SJF 보다 큼 -> but response 측면에서는 better
• quantum은 context switch time보다 반드시 커야함
  • 보통 q 10 ~ 100 miliseconds
  • context switch < 10 microseconds
• Quantum이 너무 커지면 -> RR은 FCFS로 퇴화함
  • Quantum -> ∞: FCFS와 동일
  • Quantum -> 0: Processor Sharing -> context switching overhead 빈번하게 발생

 

 

• time quantumdㅔ 따라, turnaround time이 달라짐 

4. Priority Scheduling

• 각 process에 priority number를 할당 -> 작을수록, 높은 우선 순위
• CPU는 highest priority를 가진 process에 할당됨
  • Preemptive -> priority가 높으면, 중간에 cpu를 선점당할 수 있음
  • Nonpreemptive -> priority순서대로, but 중간에 cpu 소유권을 뺏지는 않음
• Problem: Starvation - low priority는 영원히 실행되지 않을 수 있음
• Solution: Aging - 시간이 흐를수록 기존 process의 priority 증가

 

- Priority Scheduling with Round-Robin

• 같은 priority를 같은 processes는 round-robin algorithm에 따라 실행

 

5. Multilevel Queue

• Ready queue -> multiple queues로 구성
• Multilevel queue scheduler를 정의하는 parameters
  • queue의 개수
  • 각 queue의 Scheduling algorithm
  • process가 service를 필요로 할 때, process가 어떤 queue에 배정될지 결정하는 방법
  • Queues 간의 Scheduling

 

- Multilevel Queue with Priority Scheduling

• 각 priority 마다 별개의 queues 존재
• highest-priority queue의 process 먼저 schedule

-> process type에 따라 우선순위 부여

 

6. Multilevel Feedback Queue

• process는 다양한 queues 사이에서 이동 가능
• Multilevel feedback queue scheduler를 정의하는 parameters
  • queue의 개수
  • 각 queue의 Scheduling algorithm
  • process를 언제 upgrade할지 결정하는 방법
  • process를 언제 demote할지 결정하는 방법
  • process가 service를 필요로 할 때, process가 어떤 queue에 배정될지 결정하는 방법
• Aging -> multilevel feedback queue를 사용함으로써 구현될 수 있음

- Example

• Q0 - RR(time quantum 8 milliseconds)
• Q1 - RR(time quantum 16 milliseconds)
• Q2 - FCFS

-> new process가 Q0에 진입(RR) -> 8 milliseconds 안에 완료하지 못하면 Q1으로 이동

-> Q1에서 16 milliseconds의 추가 시간을 부여받음(RR) -> 16 milliseconds 안에 완료하지 못하면, preempted & Q2로 이동

 

Multiple-Processor Scheduling

• Multiple CPUs
  
  • processor chip이 여러 개인 경우 -> mother board를 cpu 여러 개 설치 가능하도록 설계
• Multithreaded cores 
  • 하나의 processor 안에 여러 개의 core
• NUMA(Non-Uniform Memory Access) systems
  
  • processor마다 별개의 memory 존재 -> 각각의 cpu 들이 interconnect라는 내부의 연결을 통해서 서로의 memory에 접근 가능
  • 다른 memory 접근은 더 오래 걸리므로, 데이터의 적절한 분배가 중요
• Heterogeneous multiprocessing
  
  • 일반적으로는 core의 성능이 모두 비슷 -> Heterogeneous에서는 core의 특성이 다 다름 
  • ex) big little -> big core(processing power good) + little core(energy 소모 good)

좌측부터 순서대로 Multiple CPUs, Multithreaded cores, NUMA(Non-Uniform Memory Access) systems

• Symmetric multiprocessing (SMP)
  • each processor -> self scheduling 
  • a) 모든 threads가 공통의 common ready queue 내부에 존재
  • b) 각 processor는 자신의 private queue of threads를 가짐

1. Multicore Processors

• Multiple processor cores를 같은 physical chip 위에 올리는 최근 트렌드 -> 더 적은 power로 더 빠른 속도
• Multiple (hardware) threads per core -> memory stall의 이점을 이용 -> memory stall 대기시간 동안 또다른 thread 진행
  • ex) inter의 hyperthreading

- Multithreaded Multicore System

• 각 core가 1개보다 많은 threads 개수를 가짐
• 한 thread에서 memory stall 발생 -> another thread로 교체

• Chip-multithreading(CMT): 각 core에 multiple hardware threads를 할당
  
  • intel의 hyperthreading
  • quad-core system: core 당 2개의 hardware threads -> os는 8개의 logical processors로 인식

• Two levels of scheduling
  1. operating system은 logical CPU 위에서 어떤 software thread가 작동할지 결정
  2. 각 core가 어떤 hardware thread가 physical core 위에서 작동할지 결정

Software Threads
- single process 내부에서 concurrent하게 execution하는 programming contstruct
- os 혹은 runtime library에 의해 관리됨
- 같은 parent process의 memory space 공유


Hardware Threads
- hardware-supported multi-threading / Hyper-threading에서 언급되는 개념
- single CPU core 위에서 multiple threads가 simutaneous하게 execution하도록 함
- 각 core는 multiple hardware threads를 관리

Software Threads vs Hardware Threads
- Level of Operation:
    - software threads: os 혹은 application level에서 존재하고, thread scheduler에 의해 관리됨
    - hardware threads: cpu level에서 존재하고, single core 내에서 parallel execution 제공
- Resource Sharing
    - software threads: process의 같은 memory space를 공유(synchronization mechanism)
    - headware threads: CPU resources의 특정 부분을 공유, core 내부에서 parallel execution의 이점을 가짐
- Performance Impact
    - software threads: 사용 가능한 cpu cores 개수와 hardware threads의 개수에 따라 성능 향상 어느정도 제약
    - hardware threads: CPU performance와 직결됨

출처: https://www.youtube.com/watch?v=s3UU8XdnM44&ab_channel=blogize

 

 2. Load Balancing

• symmetric multiprocessing이 모든 CPU load를 효율적으로 유지해야 한다면 사용
•  Load Balancing: workload가 균등하게 분배되도록 시도
  • Push migration: 각 processor의 load를 주기적으로 checks -> overloaded CPU에서 other CPUs로 task push
  • Pull migration: idle 상태의 processors가 busy processor의 task를 pull - processor가 할 일을 끝내고, load를 많이 가진 processor에서 task를 pull

 

3. Processor Affinity

• thread가 한 processor 위에서 작동할 때, processor의 cache contents에 해당 thread의 memory 접근을 저장
• 해당 thread가 processor에 affinity를 가진다고 말함 - processor affinity
  • load balancing이 processor affinity에 영향을 미칠 수 있음 -> 부하 분산에 따라 thread가 기존 processor에서 other processor로 이동하면서 기존 processor에 저장된 cache contents를 잃게 됨
• Soft Affinity:  thread가 동일 processor 위에서 실행되도록 시도하지만, 해당 processor 위에서 실행되지 않을 수도 있음
• Hard Affinity: process가 실행될 processors의 set을 명시함 -> 무조건 해당 processors에서 실행

 

Real-Time CPU Scheduling

• Real-time system은 task 처리에 걸리는 시간을 일관되게 유지할 수 있는지가 중요한 성능의 척도 -> 실시간 성능 보장 목표
• Soft real-time systems: critical real-time tasks가 가장 높은 priority를 가지지만, 그들이 언제 schedule될지는 보장되지 않는다.
• Hard real-time systems: task가 반드시 deadline을 지켜야 함

• soft real-time systems - system이 deadline을 놓치면, 결과의 가치가 하락
• hard real-time systems: system이 deadline을 놓치면, function을 중지

https://www.intel.com/content/www/us/en/robotics/real-time-systems.html

Real-Time Systems Overview and Examples-Intel

 

• real-time scheduling을 지원하기 위해서 -> scheduler는 preemptive, priority-based scheduling 조건을 만족해야 함
  • soft real-time에서는 그저 guarantee
  • hard real-time의 경우 -> 반드시 deadline을 지킬 수 있는 능력을 줘야함

1. Periodic Task Scheduling

• processes가 고정된 간격의 주기를 가짐
  • 0 <= t <= d <= p (processing time: p, deadline: d, period: p)
  • Rate(주기적 task): 1/p

• preemptive scheduling algorithms for periodic tasks

	Deadline = Period	Deadline <= Period
Static Priority	Rate Monotonic (RM)	Deadline Monotonic (DM)
Dynamic Priority	EDF	EDF*

 

- Rate Monotonic(RM) Scheduling

• priority - 주기의 역에 따라 할당됨(static priority)
  • 짧은 주기 - 높은 우선순위
  • 긴 주기 - 낮은 우선순위
  • ->> 자주 실행되는 task에 priority

-> 중간에 우선순위에 따라 preemption이 일어나지 않으면, p1은 deadline 안에 task를 완료하지 못함

 

-> 해당 process set의 경우, Rate-Monotonic 방식으로 scheduling할 수 없다. - infeasible

-> RM 방식으로 scheduling할 수 없는 경우, 다른 priority scheduler로도 scheduling할 수 없다.

-> static priority를 사용하는 algorithm 중에 가장 적합한 algorithm으로 여겨짐

 

- Earliest Deadline First Scheduling (EDF)

• priority가 deadlines에 따라 할당됨 -> dynamic priority
  • Earlier the deadline = higher priority
  • Later the deadline = lower priority

 

 

Algorithm Evaluation

• How to select a scheduling algorithm for an OS? -> Determine criteria

1. Deterministic Modeling 

• analytic evaluation의 일종
• 특정 predetermined workload를 통해서 performance를 정의

 

2. Example

• 각 algorithm에 대해서 minimum average waiting time 계산

-> average waiting time의 측면에서는 SFJ가 최적

---

참고자료

• https://icksw.tistory.com/123

[OS] 프로세스를 스케줄링 하는 방법들 (Scheduling) - OS 공부 3

• https://velog.io/@hosunghan0821/CPU-Bound-IO-Bound

[CS]CPU Bound / IO Bound

• https://velog.io/@kmjoo/OS-CPU-Scheduling-1

[OS] CPU burst와 CPU Scheduler

• https://sete3683.tistory.com/56

FCFS, SJF, SRTF, RR의 계산 및 비교

• https://zzsza.github.io/development/2018/07/29/cpu-scheduling-and-process/

CPU Scheduling, Process 이해하기

• https://wpaud16.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-Multiple-Processor-Scheduling-Load-balancing-Affinity-%EB%A9%80%ED%8B%B0-%ED%94%84%EB%A1%9C%EC%84%B8%EC%84%9C-%EC%8A%A4%EC%BC%80%EC%A5%B4%EB%A7%81

운영체제 Multiple-Processor Scheduling ( Load balancing, Affinity, 멀티 프로세서 스케쥴링 )

• https://www.intel.com/content/www/us/en/robotics/real-time-systems.html

Real-Time Systems Overview and Examples-Intel

• https://lazymankook.tistory.com/49

Real-Time CPU Scheduling