[운영체제] CH4. CPU Scheduling

1. Basic Concepts

• Multiprogramming : 컴퓨터의 CPU에서 동시에 여러 프로그램을 실행하는 기술
  • multiprogramming의 목적은 CPU utilization의 극대화임

 

process는 CPU execution 주기와 I/O wain 으로 구성됨. 즉, 프로세스가 일정 시간 동안 CPU에서 실행된 다음, 계속 실행되기 전에 I/O 작업이 완료될 때까지 기다림. 

 

CPU Burst distribution은 1) 짧고 많은 cpu burst 와 2) 길고 적은 cpu burst 가 있는데,

• I/O Bound program은 짧고 많은 cpu burst를 가지며
• CPU-Bound program은 길고 적은 cpu burst를 가짐

 

 distribution에서 왼쪽은 burst duration이 짧고 frequency가 높은 I/O burst가 해당하며

오른쪽은 duration이 길고 frequency가 적은 CPU burst가 해당한다

 

CPU Scheduler 

: CPU Scheduler는 memory에서 ready to execute 된 process 중 process를 선택하고, 해당 프로세스에 CPU를 할당한다

이러한 스케줄링을 하는 상황은 네 가지가 있다.

1. 프로세스가 실행 상태에서 대기 상태로 전환되는 경우
2. 프로세스가 실행 상태에서 준비 상태로 전환될 때
3. 프로세스가 대기 상태에서 준비 상태로 전환될 때
4. 프로세스가 종료되는 경우

1, 4의 경우 nonpreemption임. 즉 CPU가 하나를 이미 하고 있으면 다른 프로세스 할당 X 기다려야 함

2, 3의 경우는 하던 프로세스를 중단하고 다른 프로세스를 할당할 수 있음

Dispatcher

: CPU scheduler에 의해 선택 된 프로세스를 CPU의 core로 넘기는 역할을 함.

 

우선 순위를 부여해야 하는 프로세스를 결정했으면 (scheduler) 해당 프로세스를 실행하도록 CPU에 지시합니다. 디스패처는 시스템이 CPU를 효과적으로 활용하고 적시에 워크로드 변화에 대응할 수 있도록 서로 다른 프로세스 사이를 빠르고 효율적으로 전환해야 합니다.

 

1. Context switching

2. user mode switching

3. 다시 프로그램 실행하기 위해 jumping to the proper location

 

등의 단계를 포함함.

 

Dispatch latency : 하나의 프로세스를 멈추고 다른 프로세스를 실행(switching)을 하는데 걸리는 시간. 

2. Scheduling Criteria

• (MAX) CPU utilization : CPU가 Busy한 정도. 바쁠수록 좋음
• (MAX) Throughput : 시간 당 끝낸 프로세스의 수. 많을 수록 좋음
• (MIN) Turnaround time : 프로세스 submission(도착 시점)으로부터 끝날 때 까지의 Interval 
• (MIN) Waiting time : wait queue에서 기다린 시간의 총 합
• (MIN) Response time : submission 이후 첫 response가 생성될 때 까지의 시간. (전체 출력X)

 
 
3. Scheduling Algorithms

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

• ready queue에 먼저 도착한 process를 먼저 cpu에 할당함 (FIFO queue)
• Convoy effect : 다른 모든 프로세스가 하나의 big process가 cpu에서 끝날 때까지 기다려야 하는 것

 
2) Shortest-Job-First (SJF) Scheduling

• CPU Burst가 가장 작은 프로세스에 CPU 할당
• 실행에 필요한 시간(cpu-burst-time)이 가장 적은 프로세스를 고려하여 CPU를 할당

 

• Nonpreemptive : 수행 중 더 짧은 프로세스가 도착해도 현재 진행되고 있는 프로세스는 끝내고 처리
• preemptive : 수행 중 더 짧은게 오면 바로 현재 하던 프로세스 중단하고 바꿔버림 (=Shortest-Remaining-Time-First (SRTF) )

단점) 다음 CPU Request의 length를 알기 어려움.

따라서 우리는 process time에 limit을 설정해두고, 무한히 돌 때 끊어버림.

혹은 그 값을 예상하는 것도 가능

* next CPU burst 예상하기 (by exponential average)

tn : 실제 n번째 때의 CPU Burst 길이

τn+1 : 다음 cpu burst 예상값

α : 최근 데이터가 얼마나 중요한지 

 - α = 0 : 최근 history no effect

 - α = 1 : 오직 most recent cpu burst만 중요

 - α = 1/2 : recent history와 past history가 equally weighted

3) Round Robin (RR)

• FCFS랑 유사하지만 Preemption이 추가되어 Process간 전환이 가능함
  • time quantum(10~100milsec)이라는 고정된 실행 시간이 주어짐. 그 시간 지나면 CPU는 이전 프로세스가 실행을 완료했는지 여부에 관계없이 ready queue에 있는 다음 프로세스 실행. 하던 것은 ready queue 뒤로 다시 붙임
  • 만약 한 quantum 안에 하나의 프로세스가 끝났으면 다른 프로세스로 바로 switching
• 만약 ready queue에 n 개의 process가 있고, time quantum이 q라면 각 process는 CPU 시간의 1/ n을 최대 q time units 만큼만 할당함. 따라서 각 process는 (n-1)q 보다 오래 기다리지 않는다. (어떤 프로세스가 cpu를 장기 독점하지 x)
• Performance 
  • time quantum이 매우 큰 경우 => FCFS와 동일
  • 작은 경우 : context swiches 너무 자주 일어남

 
4) Priority Scheduling

• 가장 높은 priority를 가지는 process를 cpu에 할당한다
  • equal-priority processes는 FCFS order 
  • SJF 알고리즘은 가장 단순한 priority algorithm (priority : inverse of next CPU burst, cpu burst 크면 우선순위 낮음)
  • Priorities는 internally/ externally 정의되는것 모두 가능
    • Internally defined priorities: 측정 가능한 quantity를 이용해 priority 부여
      • Time limits, memory requirements, open file 수, 평균 cpu Burst 대비 평균 I/O Burst 비율 
    • External priorities : 운영체제 외부의 기준에 따라 설정
      • importance of the process, 업무 후원하는 부서, 정치적 요인 등
• Nonpreemptive : 하던 거 끝냄
• preemptive
  • 작업 수행 도중 더 priority 높은 애가 도착하면 하던거 버리고 새로운거 함

 

 

Problem - Starvation (indefinite blocking)

: low-priority process는 무한히 기다려야 함

 

Solution - Aging 

: 오래 기다린 process의 priority를 점진적으로 증가시

 

--> 우선 순위가 높은 프로세스의 실행 우선 순위를 지정함으로써 운영 체제는 중요한 작업이 먼저 완료되도록 할 수 있으며 시스템은 시간에 민감한 작업에 신속하게 대응할 수 있습니다. 그러나 낮은 우선순위 프로세스에 starvation 문제가 발생하여 전체 시스템 성능이 저하될 수 있습니다.

이 문제를 완화하기 위해 일부 우선순위 스케줄링 알고리즘은 에이징을 사용합니다. 이는 프로세스가 준비 대기열에서 오랫동안 대기한 경우 시간이 지남에 따라 프로세스의 우선순위를 높이는 것과 관련됩니다. 이렇게 하면 우선 순위 값이 더 낮은 경우에도 모든 프로세스가 결국 실행 기회를 얻게 됩니다.

 

* 우선 순위가 같은 process 간에는 Round-robin 적용할 수 있음

5) Multilevel Queue Scheduling

• Process type에 따라 queues를 구분해서 따로 두는 알고리즘
  • Foreground(interactive), background(batch)
  • priority 마다 각각 큐 만들어서 관리할 수도 있음 (어떤 프로세스가 highst-priority인지 알려면 O(n)) search가 필요함)

• 각 큐는 각자의 스케줄링 알고리즘을 가질 수 있음
  • 각 대기열의 스케줄링 알고리즘은 해당 대기열에 할당된 우선 순위 수준에 따라 결정
  • 예를 들어 우선순위가 높은 큐는 라운드 로빈과 같은 preemption스케줄링 알고리즘을 사용하고 낮은 우선순위 큐는 FCFS와 같은 non-preemption 스케줄링 알고리즘을 사용
• 큐 사이의 스케줄링도 해야 함
  • 큐 간 우선순위도 있음. 따라서 starvation 위험도 있음
  • Time slice: 각 큐는 CPU Time의 일부를 할당받아 그 안에서 스케줄링
    • Foreground Queue - 80% of the CPU time 
    • Background Queue - 20% of CPU time

• [Multilevel Feedback Queue scheduling] 
  • 큐 간 프로세스 이동이 허용된다면 (=aging) starvation을 방지할 수 있음
    • 만약 한 프로세스가 너무 많은 CPU 타임을 잡아먹는다면  lower-priority로 이동
    • 한 프로세스가 너무 오래 기다렸으면 higher-priority queue로 이동
       
  • MFQS는 다음과 같은 parameter로 정의됨
    • ✓ The number of queues
    • ✓ The scheduling algorithm for each queue
    • ✓ The method used to determine when to upgrade a process
    • ✓ The method used to determine when to demote a process
    • ✓ The method used to determine which queue a process will enter when that process needs service

 
4. Multie-Processor Scheduling

여러 CPU 또는 프로세서를 동시에 관리하기 위한 스케줄링 알고리즘. 프로세스를 동시에 실행할 수 있는 여러 개의 CPU가 있어 각 CPU에 프로세스를 할당하고 CPU는 프로세스를 병렬적으로 실행

운영 체제는 모든 CPU에 걸쳐 workload balance를 유지하고 각 CPU가 실행할 프로세스 수가 거의 동일하도록 해야 함

 

• Asymmetric multiprocessing
  • 시스템 리소스를 관리하고 보조 프로세서를 제어하는 ​​하나의 기본 프로세서가 있음. 이 single processor에 의해 handled (master server)
  • 한 프로세서가 system data structure에 접근하므로 data sharing 필요 X
• Symmetric multiprocessing
  • 모든 CPU가 동등하게 취급되며 모든 CPU는 모든 프로세스를 실행할 수 있음
  • 각 프로세서가 self-scheduling

• common ready queue
  • core가 ready queue를 공유해 작업들이 고르게 분배됨
  • BUT shared ready queue 에서 race condition이 발생할 수 있음
    • race condition이란 두 개 이상의 프로세스가 공통 자원을 동시에 읽거나 쓰는 동작을 할 때, 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다. Race 는 두 개의 스레드가 하나의 자원을 놓고 서로 경쟁하는 상황을 말한다.
  • 이런 문제를 막기 위해 locking 사용함
• own private queue
  • 각 core별로 ready Queue 가 존재함. 작업이 하나로 몰릴 수 있음
    • 다양한 size의 workloads
    • 모든 프로세스 간의 workload를 equaliizing하는 balancing algorithm이 필요

Multicore processor : 단일 물리적 chip에 여러개의 computing cores 가 포함된 cpu

 --> CPU가 물리적 chip 여러 개 갖는 것보다 빠르고 더 적은 전원을 소비

 

Memory stall : 프로세서가 memory에 access할 때, 프로세스가 메모리에서 데이터를 사용할 수 있을 때까지 상당히 오랜 시간이 걸림

--> 프로세서는 데이터 available을 기다리는 데에 최대 50% 시간을 쓸 수 있음

 

Multithreaded processing core : 2개 이상의 hw threads가 각 core에 할당됨

* CMT (Chip Multithreading)

- 동일한 물리적 칩에 여러 computing core을 배치하고, 각 core에는 hw thread가 포함됨. 각 hw thread는 instruction pointer나 register set와 같이 architectural state를 유지하며, software thread를 실행할 수 있는 logical CPU의 형태로 나타남. 이를 통해 단일 프로세서 칩에서 여러 스레드를 동시에 실행할 수 있음.

 

이 예에서는 프로세서에 4개의 컴퓨팅 코어가 포함되어 있으며 각 코어에는 2개의 하드웨어 스레드가 있음.

따라서 소프트웨어 스레드를 실행하는 데 사용할 수 있는 총 8개의 논리적 CPU가 생성됨.

 

 

Multithread의 두 가지 방식:

 

1. Coarse-grained multithreading

: 다음 스레드로 전환하기 전에 단일 실행 스레드에 전체 프로세서 주기를 할당하는 것. 이는 각 스레드가 다른 스레드의 실행 전 특정 시간 동안 프로세서에 독점적으로 액세스할 수 있음을 의미함.  stalling동안 clock cycle을 낭비함

2. Fine-grained(or interleaved) multithreading

: 단일 프로세서 주기 내에서 여러 스레드의 실행을 인터리빙 .빈큼없이 stalling 최소화 함 

 

 

Load Balancing : SMP system (Symmetric Multiprocessing) 에서 processors 간 workload를 고르게 분배하기 위한 것 (own private ready queue 사용) (특정 cpu에 작업 몰릴 때 how to 분배)

1. Push migration : 바쁜 곳에서 덜 바쁜 곳으로 옮기기

2. Pull migration 

 

migrate할 때 첫 번째 프로세서의 cache memory가 invalidated 되고 두 번째 processor의 cache를 다시 채워야 함. 따라서 이러한 과정이 high cost임.

 

Processor affinity - 옮기는 거 싫어함 (overhead). 머무르려는 속성. 쓰레드를 최대한 같은 프로세서로 유지하기 위한 노력. 프로세서 간 전환과 관련된 오버헤드를 줄임으로써 병렬 응용 프로그램의 성능을 향상시키는 데 사용됨.

 1) Soft affinity :  preferred processor 에서 실행하려고 하지만 무조건은 아님 필요한 경우 다른 프로세서에 할할 수 있음

 2) Hard affinity : 지정된 프로세서에서만 스레드 또는 프로세스를 schedule하고 그외에서는 절대 안 함

 

load balancing은 이러한 processor affinity의 장점을 없애버릴 수도 있음

 

로드 밸런싱으로 인해 특정 프로세서에 이미 바인딩된 스레드나 프로세스가 다른 프로세서로 이동되기도 함

 

*Non-uniform memory access (NUMA)

: 메모리 액세스 시간이 프로세서와 관련된 메모리 위치에 따라 달라지는 다중 처리에 사용되는 컴퓨터 아키텍처 설계

NUMA는 일반적으로 프로세서가 둘 이상인 시스템에서 사용되며 각 프로세서는 자체 로컬 메모리에 액세스하고 공유 메모리 공간에도 액세스할 수 있습니다.

 

NUMA 시스템은 처리를 로컬 메모리에 가깝게 유지하여 메모리 액세스 대기 시간을 최소화하도록 설계되었습니다. 액세스해야 하는 메모리에 가장 가까운 프로세서에 프로세스를 할당하면 됩니다. 프로세서와 메모리 사이의 거리를 최소화함으로써 NUMA 시스템은 기존 SMP(대칭 다중 처리) 시스템보다 더 나은 성능과 확장성을 달성할 수 있습니다.

5. Real-Time CPU Scheduling

 

: for 즉각적인 처리. 라운드 로빈 또는 SJF 과 같은 표준 CPU 스케줄링 알고리즘과 다른 알고리즘을 사용하여 실시간 프로세스가 정시에 실행되도록 함

 

  1) Soft-real-time systems

  : 프로세스에 우선 순위가 부여되지만 반드시 준수해야 하는 엄격한 기한은 없음

 

  2) Hard real-time systems 

  : 무조건 task가 dealine에 맞춰서 처리되어야 함

 

event latency : event가 발생하고 그것이 서비스 되기까지의 time

  - Interrupt latency : inturrupt가 도착하고 해당 인터럽트 처리가 시작되기 까지의 시간 (지연)

  - Dispatch latency : dispatcher가 한 프로세스를 중지하고 다른 프로세스를 시작하기 위해 걸리는 시간

프로세스가 실행될 준비가 되면 운영 체제는 적절한 프로세서를 선택하고 컨텍스트를 현재 프로세스에서 새 프로세스로 전환해야 함. 

• 이미 kernel에서 실행중인 process에 대한 preemption
• low-priority process를 해제하고 high-priority process에게 resource 주기

과정에서 latency 발생

 

 

 
1) Priority-based scheduling

 : real-time operating system의 스케줄러는 priority-based algorithm with preemption을 지원해야 함 

(데드라인 얼마 안남음 == priority 높음)

( soft real-time 만 보장함)

 

periodic : CPU의 constant intervals

필요한 처리 시간 t, 데드라인 d, period p 

 

0<=t<=d<=p

 

2) Rate-Monotonic Scheduling

기간이 짧거나 빈도가 높은 프로세스에 더 높은 우선 순위가 지정

: static priority policy with preemption

• 각 period task에는 주기에 따라 거꾸로 priority가 할당됨
  • period가 짧을 수록 priority가 높아짐
• 만약 프로세스 period P1, P2가 각각 50, 100일 때, processing time t1 = 20 (P1) t2 = 35(P2) 라고 하면
  • 프로세스의 CPU utilization ratedms t/p임
    • P1 : 20/50 = 0.4
    • P2 : 35/100 = 0.35
• 그러므로 이러한 Task를 deadline은 맞추면서 CPU의 available cycles을 남겨두는 방식으로 스케줄

 

예를 들어 P2보다 P1이 더 period 가 짧다면, 더 높은 우선 순위를 갖는다.

만약 P1이나 P2의 Period가 한 번 끝나면 무조건 switch

이렇게 하면 miss 되는 경우가 생김

 

따라서 CPU resource를 항상 maximize하는 것이 불가능

worst case (N processes) : N(2^(1/N) - 1)

Process가 하나있으면 CPU utilization 100%, 프로세스가 많아질 수록 69%까지 떨어짐

 

 

P2 먼저 하면 P1이 miss나지만, 더 짧은 p1 먼저 하면 괜찮음

but 이경우에는 p2가 miss가 남

 

3) Earliest Deadline First Scheduling (EDF)

 : deadline이 빠른 것이 높은 priority를 갖는다! 눈 앞에 보이는 deadline 먼저 처리. 

작업 끝나면 switch. period 지났을 때 데드라인 검사 다시 해서 변동 있으면 다시 switch

RLT 스케줄링 중 핵심. 무조건 잘 됨!
 
6. Operating System Examples
1) Linux
 
2) Windows
 
3) Solaris
 
7. Algorithm Evaluation
 

1) 알고리즘 선택할 때의 기준 선정

• Maximizing CPU utilization
• Maximizing throughput

2) deterministic modeling

미리 workload와 performance 예측