[OS 공룡책] Ch05. CPU Scheduling

Chapter 5: CPU Scheduling

과제3 https://github.com/j-nary/Process_Scheduling_Policy

Scheduling Criteria

Basic Concepts

• Process execution cycle

  

  • CPU 동작시간 = CPU burst + I/O burst + 대기
  • CPU burst : 10ms 이내로 정리 → 굳이 길게 X

CPU Scheduler

• Short-term scheduler : ready queue에 대기하고 있는 process 중 하나 CPU에게 주는 역할

  1. nonpreemptive : 비선점

     • running → waiting
     • terminates

     → 간단

  2. preemptive : 선점

     • running → waiting
     • running → ready
     • waiting → ready
     • terminates

     → real-time(deadline 중요)

     → 프로세스 간 데이터 공유 시, 일관성 유지 비용 발생

• Long-term scheduler

Dispatcher

• Scheduler에 의해 결정된 프로세스를 CPU한테 넘겨주는 작업
• context switching → user mode로 변경 → PC에 다음 프로그램 카운터값 저장
  
• Dispatch latency
  • 스케줄링 끝난 시점 ~ 새로운 프로세스 돌아가는 시점
  • context switching + 약간의 작업

Scheduling Criteria ⭐️

1. CPU utilization ⬆️

   : CPU를 가능한 한 바쁘게 유지

2. Throughput ⬆️

   : 단위 시간동안 처리하는 작업의 개수

---

1. Turnaround time ⬇️

   : 하나의 프로세스가 시작 ~ 종료까지 걸리는 시간

   → waiting time + CPU burst + I/O burst

2. Waiting time ⬇️

   : 하나의 프로세스가 ready queue에 대기하는 데 걸리는 시간

3. Response time ⬇️

   : 첫번째 응답이 올 때까지의 시간

   → 사용자에게 요청 받은 순간 ~ 요청 내보내는 순간

   → real-time system에서 중요

→ trade-off 관계 : 어떤 지표에 집중해서 설계할 것인가?

Scheduling Algorithms

CPU Scheduling Algorithms

1. FCFS 선입 선처리 스케줄링 (Non-preemptive)

2. SJF 최단 작업 우선 스케줄링 (Non-preemptive)

   → SRTF (Preemptive)

3. RR 라운드 로빈 스케줄링 (Preemptive)

4. 우선순위 스케줄링 (both)

→ average waiting time

First-Come, First-Served (FCFS) Scheduling

• Non-Preemptive
• 장점 : 구현 간단
• Convoy effect
  • 앞의 순서인 process가 길면 → average waiting time 증가
  • Convoy effect 크면 → FCFS 성능 저하
• Worst 스케줄링 방식

Shortest-Job-First (SJF) Scheduling

• Non-preemptive

• CPU burst가 가장 짧은 process부터

  → 한 번의 CPU를 점유하는 데 걸리는 시간
  

• waiting time 측면에서 베스트 스케줄링

• 현실적으로 구현 X

• CPU Burst 예측 : exponential averaging

  

  • 알파값은 보통 1/2로 설정

    

  • 알파 = 0 : 실측값 고려X, 처음 예측했던 거 그대로

  • 알파 =1 : 예측값 고려 X, 실제 얻은 값만

Shortest-remaining-time-first ⭐️

• SRTF = STCF(Shortest-time to Complete First)

  → SJF의 Preemptive 버전 (더 효율적)
  

• CPU Time이 짧다면 양보

  → 내가 먼저면 context switching 발생 X
  

• Example

  

  • Arrival Time 1, 2, 3 빼주는 거 잊지 말기

    → 실제 시간 차이는 적게 난다 : Context Switching 발생

Priority Scheduling

• 정수값이 낮을 수록 우선적으로 뽑아 사용
• 구동 방식

  1. Preemptive

  2. Nonpreemptive

     → Priority Scheduler는 둘 다 가능

• 장점
  • OS가 수행시키는 프로세스들의 다양한 특성 반영
• 단점 : Starvation ⭐️
  • 우선순위가 낮은 애들이 굶어죽음
  • 해결 : Aging → 나이가 들수록 우선순위를 높여주는 기법
    

Round Robin (RR) Scheduling

• 100% Preemptive
• time quantum, time slice
  • 보장하는 최대 CPU burst time (보통 10ms)
  • time quantum 간격으로 timer interrupt 발생 → waiting → ready
    
  • 너무 작게 → context switching overhead 자주 발생
  • 성능에 직접적인 영향
• 복합적 사용 가능 : 누구부터 먼저 줄거냐?
  • FIFO
  • priority 기반
  • SJF : 계산 복잡해서 잘 사용 X
• average response time에 가장 좋은 Scheduler 방식 → process가 사용자에게 응답하는 데에 걸리는 시간
  
• Time Quantum ↔ Context Switch Time
  • 너무 큰 Time Quantum := FCFS
  • 너무 작은 Time Quantum : 과한 context switching
  • quantum > context 필수 → 성능 저하 방지
    
• Turnaround Time varies with Time Quantum

  1. Time Quantum = 6

     • P1 : 0 ~ 6
     • P2 : 6 ~ 9
     • P3 : 9 ~ 10
     • P4 : 10 ~ 16
     • P4 : 16 ~ 17

     → P4의 시스템 오버헤드가 달라짐

     → Context Switching은 없음 : 다른 애랑 바뀌어야 발생

     → Scheduling을 결정하는 시간 때문에 P4(10~17)보다 복잡도가 약간 높아짐

     → 평균 총처리 시간 : (6 + 9 + 10 + 17) / 4 = 10.5

  2. Time Quantum = 1

     • P1 : 0 ~ 1
     • P2 : 1 ~ 2
     • P3 : 2 ~ 3
     • P4 : 3 ~ 4
     • P1 : 4 ~ 5
     • P2 : 5 ~ 6
     • P4 : 6 ~7

     → 평균 총처리 시간 : (15 + 9 + 3 + 17) / 4 = 11.0

CFS (Completely Fair Scheduling)

- SCHED_OTHER : CFS
- Real Time : FIFO, RR, Deadling
- IDLE

• Priority + Round Robin 의 특성

  • Nonpreemptive : time slice 동안은 중단 X
  • Priority Scheduler 일종
  • Linux Scheduler

• Fair 보장을 위한 4가지 요소

  1. virtual runtime(가상 실행 시간) 도입
     • CPU 차지한 시간에 비례한 시간
     • 여러번 점유하고 여러번 썼으면 시간 증가
     • 새로 생성되는 process : 최우선
     • virtual runtime이 작을 수록 우선순위
  2. run queue (ready queue)
     • red black tree로 구성 : 맨 왼쪽 리프노트가 최우선
     • 실행 대기 중인 process들이 들어있는 queue, tree로 구성
     • 누적 가상실행시간이 짧은 순으로 정렬 (우선순위)
  3. 타임 슬라이스 제공
     • RR Scheduler
     • 강제 중단없이 CPU의 실행을 보장받는 시간
  4. 가중치 weight
     • Priority Scheduler
     • weight

       • nice 값(-20 ~ 19)에 따라 결정

       • nice 작을 수록 weight 커짐 → 우선순위 높아짐

         → 클수록 가상 실행시간 작게, 타임슬라이스 길게

     • 프로세스마다 별도의 가중치 유지

• 개요

  • CPU 사용 시간이 짧은 process 우선
  • process 선택 시, weight 반영 → 타임 슬라이스 계산
  • Nonpreemptive : 타임 슬라이스동안 강제 중단 X
  • CPU 덜 할당받은 process 시간 지날수록 CPU 사용 시간 낮아짐 → 우선순위 증가 : aging 기법 적용 → starvation 발생 X
    

• 작동 과정

  

  1. process 생성되면
     • ready queue(그동안 사용한 CPU의 누적시간)에 삽입
     • 가상실행시간 : queue에 들어있는 최솟값
  2. 스케줄링
     • 가장 짧은 누적가상실행시간을 가진 process 선택
  3. 실행
  4. 실행 도중
     • process가 타임 슬라이스 소진 시 → 가상실행시간, 누적가상실행시간 계산, run queue에 삽입
       
     • procees 실행 중 I/O 발생 시 → wait queue에 삽입
       
     • 입출력 완료 시 → 깨어나 가상실행시간, 누적가상실행시간 계산, run queue에 삽입
       

• nice와 weight

  1. nice
     • nice 값 클수록 우선순위 낮음 → 양보 잘 함.
     • default nice값 = 0
     • nice 값 조절 : 시스템 호출
  2. weight
     • nice값 → weight
     • 클수록 높은 우선순위
       • 가상실행시간 작게
       • 타임슬라이스 크게 (더 오래 CPU 사용 가능)

• 가상실행시간

  

  • actual_run_timep : 프로세스 p의 실제 실행 시간
  • vrp : 가상실행시간
  • vr_totalp : 누적 가상실행시간
  • 계산 시점
    • 프로세스 생성 시 : ready queue의 가장 짧은 누적 가상실행시간으로
    • 프로세스 타임슬라이스 소진 시
    • wait queue → ready queue 이동 시

• 타임 슬라이스

  

  • scheduling_period : CFS에서 계획한 주기 시간
  • time splice : 중단없이 실행되도록 CPU를 부여하는 시간
  • 프로세스마다, 스케줄링 시 타임슬라이스 새로 계산

Multilevel Queue Scheduling

• Ready queue 분할

  

  1. foreground (interactive)

     • 가장 먼저

  2. background (batch)
     - 1번 queue가 비워지면 실행

     → 각각의 queue 내부에서의 scheduling은 방법 다양하게!

• 장점

  • 하나의 queue에서 하나의 process 선택하는 overhead 감소
  • 같은 우선순위끼리의 명확한 구분 (grouping)

• 단점

  • priority scheduling 방식 → starvation 발생

    → (보완) Multilevel Feedback Queue

Multilevel Feedback Queue

• 하나의 process가 특정 queue내에 고정 X

• Multilevel Feedback Queue 예시

  

  • Q0 : RR (8ms), Q1 : RR (16ms), Q2 : FCFS
  • 새로운 process : Q0

    1. I/O를 요구해서 wait으로 가면 다시 Q0로

    2. wait로 가지 않고 time slice 끝나서 쫓겨나면 Q1로

       → Q1에서도 time slice 끝나서 쫓겨나면 Q3으로

  • 짧은 CPU burst : interactive한 foreground process일 확률 높음
  • starvation 발생 : aging 기법 적용

Multiprocessor Scheduling

Multiprocessor Scheduling

• homogeneous(동종) multiprocessor cf. ↔ heterogeneous(이종) : 각각의 core가 하는 일이 상이
  
• Multiprocessing

  1. Asymmetric multiprocessing(AMP)

     → 각 프로세서가 균등하지 않은 고유한 역할을 가짐

     (주 프로세서가 리소스, 메모리 관리 주로 담당)

  2. Symmetric multiprocessing(SMP)

     → 모든 프로세서가 동등한 역할

     • Load balancing 고려
     • Context switching overhead 고려
• Load balancing 거의 동일한 개수로 나눠져야함

  1. Push migration

     • 주기적으로 각 core에 몇 개씩 있는지 검사하는 core 존재
     • 몰려있는 process를 밀어서 다른 쪽으로 이동

  2. Pull migration
     - 각각의 core마다 자신의 ready queue를 모니터링하는 processor 만들기
     - 몰려있는 process를 자신 쪽으로 당겨옴

     → OS가 구현

Processor Affinity

• 프로세서 친화도
• CPU의 cache에 저장 → 프로세서 이주 : 비용 증가

1. 약한 친화도 (soft affinity)
   • 가급적 동일 프로세서에서 수행
   • 이주할 수도 있음
2. 강한 친화도 (hard affinity)
   • 시스템 호출 사용 sched_setaffinity()
   • 어떤 프로세스는 이주하지 않음을 명시

• NUMA(Non-Uniform Memory Access) 구조
  • processor affinity가 중요!
  • NUMA : 각 CPU마다 고유한 memory ↔ UMA : 동일한 메모리 접근
    

Multicore Processors

• CPU bound + I/O bound 적절히 섞어서

멀티 스레드 다중코어 시스템

• 칩 다중 스레드 (Chip Multithreading, CMT)
  • 하나의 core에, 여러 개의 thread
  • hyperthreading
  • 레지스터 파일만 2개로 분할 (virtual core가 2개) → simultaneous threading → dispatch latency 필요 X
    
• 두 계층 스케줄링
  • virtual(logical) CPU에서 동작할 process 결정
  • 각 core는 물리적 core에서 실행될 processor를 결정

Real-Time CPU Scheduling

Real-Time CPU Scheduling

• 주어진 deadline 내에 무조건 responds 해야하는 시스템

  

  1. Soft real-time systems

     → 가급적 지켜주면 좋은 것, 큰 일은 X

  2. Hard real-time systems

     → deadline 안 지키면 큰 일

Priority-based Scheduling

• 우선순위 : Periodic(주기)의 역순

• 0 ≤ processing시간(t) ≤ deadline(d) ≤ periodic(p)

  

• Rate Monotonic Scheduling

  • Preemptive, static scheduling

  • p1 : 수행시간 20 / 주기 50 → 40%

  • p2 : 수행시간 35 / 주기 100 → 35%

    → CPU 이용률 총 75%, p1 > p2

    

  • 문제점

    • 주기의 정확한 판단 X
    • 수행시간 정확한 판단 X (:= SJF)
    • p2 : deadline 만족 X

  • CPU 이용률 상한 존재

    

Earliest Deadline First Scheduling (EDF)

• Preemptive, dynamic scheduling
• deadline 빠른 것부터
• 이론적으로 CPU 100% 사용 가능 → 실제론 context switching 등의 overhead로 인해 불가
  

Proportional Share Scheduling

• token 비율대로 나눠주기

Real Examples & Algorithm Evaluation

간단하게 읽어보고 넘어가기

POSIX Real-Time Scheduling

• SCEHD_FIFO
• SCHED_RR

Linux Scheduling

• O(1) Scheduling : Active 배열, Expired 배열
• CFS
• BFS : deadline기준 linked-list

Algorithm Evaluation

• Implementation
• Simulations
• Queueing models
• Deterministic evaluation

→ 복잡할수록 평가 정확도 향상