오퍼레이팅 시스템 : Processor Scheduling Ⅱ

1. MP Scheduling

1) Process Scheduling in MP

(1)  Multiple-Processor(MP) Scheduling

• MP 시스템 분류
  1. 느슨하게 결합되거나 분산된 멀티프로세서 또는 cluster(클러스터)
     • 각 프로세서는 고유한 메인 메모리 및 I/O 채널을 가지고 있음
     • 이러한 유형의 구성은 16장에서 다룸
  2. 기능적으로 특화된 프로세서
     • 예를 들어 I/O 프로세서가 있습니다. 이 경우 마스터 범용 프로세서가 있음
       특수 프로세스는 마스터 프로세서에 의해 제어됨(11장 참조)
  3. 단단히 결합된 멀티프로세서
     • 공통 메인 메모리를 공유하고 운영 체제의 통합 제어 하에 있는 프로세서 세트로 구성됨
• MP 스케줄링 방법
  1. Asymmetric multiprocessing(master/slave) → 확장성이 떨어짐
     • 마스터에 의한 모든 스케줄링 결정, 다른 프로세서는 사용자 프로그램만 실행할 수 있음
     • 하나의 코어만 시스템 데이터 구조에 접근하므로 간단
     • 이 접근 방식의 단점은 마스터 서버가 잠재적인 병목 현상(bottle neck)이 된다는 것!!
  2. Symmetric multiprocessing(SMP, peer)
     • 커널은 어떠한 프로세서에서 실행할 수 있다.
     • 각 프로세서는 self-scheduling

(2)  Design Issues

1. Uniprocessor scheduling
   • 작업 실행 시기 결정
2. Multiprocessor scehduling
   • 작업 실행 시기뿐만 아니라 실행 위치도 결정
   • 단일 프로세서 스케줄링의 목표와 거의 동일하지만 새로운 문제가 발생
     • 프로세스 실제 dispatching
     • 대기열을 유지 관리하는 방법
     • 프로세서에 대한 프로세스 할당
     • 프로세서 heterogeneity 관리 방법

(3) Scheduling for MP

• 프로세서 하나와 프로세서 두 개의 스케줄링 비교
  • C의 값 증가는 서비스 시간 간의 변동성 증가에 해당
  • Cs = 0 → 모든 프로세스의 서비스 시간과 동일
• Observation
  • 2개의 프로세서를 사용하며 FCFS의 경우 서비스 시간이 긴 단일 프로세스가 훨씬 덜 중단됨
  • 두 개의 프로세서를 사용하는 경우 특정 스케줄링 분야는 훨씬 덜 중요
  • 다중 프로세서 시스템에는 간단한 FCFS 교육만으로 충분할 수 있음

Cs = σs / Ts
σs = standard deviation of service time(서비스 시간의 표준편차)
Ts = mean service time(평균 서비스 시간)

 

2) Processor Affinity

(1) Processor Affinity

• 특정 프로세서에서 프로세스가 실행된 경우 캐시 메모리에 어떤 변화가 발생하는지 고려
  • 프로세스에서 가장 최근에 액세스한 데이터가 캐시를 채움
  • 결과적으로 프로세스에 의한 연속적인 메모리 액세스는 종종 캐시 메모리(warm cache라고 불림)에서 충족됨
  • SMP를 지원하는 대부분의 OS는 동일한 프로세서에서 프로세스를 계속 실행하려고 warm cache를 활용
  • 프로세스가 프로세서에 대한 affinity(선호도)를 가진다.

(2) Affinity 종류

• Soft affinity → guarantee를 해주는 것
  • 운영 체제가 프로세스를 동일한 프로세서에서 계속 실행하려고 시도하지만 실행을 보장(guarantee)하지 않는 정책을 가지고 있는 경우
  • Load balacing 중에 프로세스가 프로세서 간에 migrate될 수 있다.
• Hard affinity → guarantee를 하지 않는 것
  
  • 프로세스가 실행될 수 있는 프로세서의 하위 집합 지정 허용
• 많은 시스템이 Soft affinity와 Hard affinity를 모두 제공
  • 예를 들어 Linux는 Soft affinity를 구현하지만 Hard affinity를 지원하는 sched_setaffinity() 시스템 호출도 제공
• MP 스케줄러는 프로세서 affinity(선호도)를 고려해야 한다.

3) Single-Queue MP Scheduling

(1) Single-Queue MP Scheduling

• global ready queue가 유지되며, 각 프로세서는 idle(유휴)상태일 때, queue에서 프로세스를 선택
• 프로세스가 특정 프로세서에 할당되지 않음
• UP 스케줄링을 위한 기본 framework를 재사용하기만 하면 됨
• 장점 : simplicity, load sharing( load balancing 불필요)
• 단점
  • 다른 시간에 다른 프로세서에서 실행될 수 있음(Affinity : 평가)
  • common ready queue를 이 race condition로부터 보호하기 위해 어떤 형태로든 잠금을 사용
    → Lack of scalability(확장성 부족)

4) Multi-Queue MP Scheduling

(1) Multi Queue MP Scheduling

• 각 프로세서는 자체 private queue를 가질 수 있음
  • 작업이 시스템에 입력되면 정확히 하나의 스케줄링 큐에 배치된다.
  • 프로세스가 활성화될 때부터 완료될 때까지 하나의 프로세서에 영구적으로 할당되는 경우
  • 각 큐는 특정한 스케줄링 규칙을 따름
• synchronization(동기화) 문제 방지
• 이를 통해 scalability(확장성) 및 프로세서 affinity(선호도) 향상

(2) 단점 : load imbalance

SMP 시스템에서는 두 개 이상의 프로세서의 이점을 최대한 활용하기 위해 모든 프로세서 간에 workload의 균형을 유지한 것이 중요

5) Load Balancing

(1) Load Balacing

• Load Balancing : SMP 시스템의 모든 프로세서에 걸쳐 워크로드를 균등하게 분산 유지
• Load Balancing에 대한 두 가지 일반적인 접근
  1. Pull migration
     • idle 프로세서가 idle 프로세서가 아닌 프로세서의 프로세스를 훔친다.
     • 예: FreeBSD
       - 프로세서가 할 일이 없으면 global bit-mask에 비트를 설정하여 idle 상태임을 나타냄.active processor가 자체 run queue에 작업을 추가하려고 하면 먼저 이러한 idle 비트를 확이낳고 설정된 idle 비트가 발견되면 프로세스를 idle 프로세서로 전달
  2. Push migration → 주기적으로 체그하여 load
     • 특정 작업이 각 프로세서의 로드를 주기적으로 확인함
     • 예 : Free BSD
       - 이 작업은 시스템에서 가장 로드가 많은 프로세서와 가장 로드가 적은 프로세서를 선택하고 run queue를 동일하게 함
• 고려사항
  • 다른 queue를 너무 자주 둘러보는 경우 → 높은 오버헤드로 인해 어려움을 겪을 것
    • 잦은 load balancing은 affinity를 해칠 수 있음

(2) Heterogeneous Multiprocessing(HMP)

• Heterogenous Multiprocessing(이기종 다중 처리)
  • 이제 동일한 명령 집합을 실행하면서도 clock 속도와 전력 관리 측면에서 다양한 코어를 사용하여 설계됨
  • 이것은 Asymmetric multiprocessing(AMP)의 한 형태가 아님
• 이를 지원하는 ARM 포로세서용
  • big.LITTLE 알려진 고성능 big core들과 에너지 효율적인 little core들이 결합된 솔루션

• HMP에서의 스케줄링
  • 고성능이 필요하지 않지만 little core들에서 오랜 기간 실행해야하는 작업 할당
  • 더 많은 처리 능력을 요구하지만 더 짧은 기간 동안 실행할 수 있는 interactive application은 big core에 할당

2. Real-Time Scheduling

Real-time system : task 처리에 걸리는 시간을 일관되게 유지할 수 있냐가 중요한 성능의 척도이다.

• real-time system의 이벤트 중심적 특성
  • 시스템은 일반적으로 real time으로 이벤트가 발생하기를 기다림
    • (periodic : 비정기적으로) 차량이 장애물에 접근하는 것을 감지했을 때 타이머가 만료되는 경우
  • 이벤트가 발생하면 시스템이 가능한 한 신속하게 대응하고 서비스를 제공해야 함
  • "event latency(대기시간)" = Interrupt latency + dispatch latency
  • dispatch latency를 낮게 유지하는 가장 효과적인 기술은 preemptive kerner(사전 예방적 커널)을 제공하는 것

• 최신 real-time 운영 체제
  • 지연시간 최소화는 중요하지만 특별히 유용한 metric은 아님
  • real-time OS 평가에서 더 중요한 목표
    • 가장 valuable 시간에 task를 완료(또는 시작)
• Soft real-time system( - process)
  • 중요하지 않은 프로세스보다 real-time 프로세스에 우선권이 부여된다는 것만 보장
  • real-time 프로세스가 스케줄링되는 시기에 대한 보증 제공 안 함
  • 바람직하지만(desirable) 필수(mandatory)는 아닌 관련 deadline이 있다.
• Hard real-time system( - process)
  • 프로세스는 deadline까지 처리되어야 함
  • deadline을 준수해야 함
  • 그렇지 않으면 시스템에 허용할 수 없는 damage 또는 fatal error(치명적인 에러)가 발생
  • 기한이 만료된 후의 서비스는 서비스가 전혀 없는 것과 동일
• Real-Time Task
  
  • 스케줄링되어야 하는 RT 프로세스들의 특성
    • Periodic(주기적) task : 일정한 시간 간격(주기)로 반복적으로 발생하는 과업
      • 주기적인 프로세스가 CPU를 획득하면 CPU에서 서비스를 제공해야 하는 데 필요한 실행 시간이 정해져 있음
    • Aperiodic(비정기적인) task : 발생간격이 일정하지 않고 간헐적으로 발생하는 작업
    • Starting deadline : 작업을 시작해야 하는 시간
    • Completion deadline : 작업을 완료해야 하는 시간. 일반적인 real-time 애플리케이션에는 starting deadline 또는 completion deadline이 포함되지만, 둘 다 포함되지는 않음

• A : 1 / T = 1 / 0.02 = 50 Hz  ( T = 20ms / C(수행시간) : 10ms / A(1) d(마감일) : 20ms)
• B : 1 /T = 1 / 0.05 = 20Hz ( T =50ms / C : 25ms / B(1) d : 50ms)

1) Priority Based Scheduling

• real-time 운영체제의 가장 중요한 기능은 real-time 프로세스에 즉시 대응하느는 것
• real-time 운영체제의 스케줄러는 preemption이 있는 우선 순위 기반 알고리즘을 지원해야 함
  • 스케줄러가 가장 높은 우선순위 ready-queue에서 시작된다.
  • Preemptive(선제적인) 우선 순위 기반 스케줄러를 제공하면 soft real-time 기능만 보장된다.
  • 우선순위가 낮은 프로세스는 starvation에 빠질 수 있음

UNIX 및 많은 다른 시스템에서 우선 순위 값이 클수록 우선 순위가 낮은 프로세스를 나타낸다. 달리 명시되지 않은 한 이 규칙을 따른다. Windows와 같은 일부 시스템에서는 반대의 규칙을 사용한다. 숫자가 클수록 우선순위가 높음

2) Earliest-Deadline-First(EDF)

• Earliest-Deadline-First(EDF)
  • deadline 요구 사항을 시스템에 알린다.
  • deadline에 따라 우선순위를 동적으로 할당
    1. deadline이 빠를수록 우선순위가 높아짐
    2. deadline이 늦어질수록 우선순위가 낮아짐
  • 새로 실행 가능한 프로세스의 마감일을 반영하여 우선 순위를 조정해야 할 수도 있음
• completion deadline이 포함된 periodic(주기적) task 스케줄링의 예
  • 두 개의 센서에서 데이터를 수집하고 처리하는 시스템을 고려
  • 이 예에서는 deadline이 가장 가까운 작업의 preemption point에서 우선순위를 부여하도록 스케줄링함으로써 모든 시스템 요구사항을 충족할 수 있다.

• 시작 deadline이 있는 aperiodic task(비정기적인 작업)을 처리하기 위한 계획을 고려

Earliest Deadline with Unforced Idle Times(EDUIT) 알고리즘은 각 작업데 대해 실행 시간과 데드라인을 알고 있어야 함. 또한 이 알고리즘은 언제든지 시스템이 비어 있을 때 즉, 실행 가능한 작업이 없을 때 대기 상태로 유지하는 것을 허용한다. 이러한 대기 상태를 'unforced idle time'이라고 함

3) Rate Monotonic Scheduling(RMS)

• preemption이 있는 static priority policy를 사용하여 periodic task를 스케줄링
  • 시스템에 진입하면 각 periodic task에 주기에 따라 역으로 우선 순위가 할당됨
  • 기간이 짧을수록 우선 순위가 높아짐
  • 기간이 길수록 우선순위가 낮아짐
• 작업의 우선순위를 rate(frequency)의 함수로 표시하면 결과는 단조롭게 증가하는 함수이다.

• 표기법
  • C :Execution Time(실행 시간)
  • T : period(기간)
  • U = C/T → Process Utilization(프로세스 활용율)

- 다음 부등식은 유지되어야 한다,

1. 완벽한 스케줄링 알고리즘이 성공적으로 스케줄링할 수 있는 작업 수에 대한 제한을 제공

특정 알고리즘의 경우, 경계는 더 낮을 수 있

2. RMS의 경우, 다음과 같은 부등식이 유지됨을 알 수 있다.

• 예를 들어, 세가지 주기적인 작업의 경우를 생각해보자
  • 작업 P1 : C1 = 20, T1 = 100, U1 = 0.2
  • 작업 P2 : C2 = 40, T2 = 150, U2 = 0.267
  • 작업 P3 : C3 = 100, T3 = 350, U3 = 0.286
• 이 세 가지 작업의 총 사용률은 0.2 + 0.267 + 0.286 = 0.753이다
• 세 가지 작업에 필요한 총 사용률이 RMS의 상항(0.753 < 0.779)보다 작기 때문에 RMS를 사용하면 모든 작업이 성공적으로 스케줄링된다.

4) EDF vs RMS

• EDF
  1. 프로세스가 실행 가능해지면 프로세스가 스케줄러에 마감일을 공지해야하는 요구사항
  2. EDF 스케줄링의 매력은 이론적으로 최적이라는 것
     • 프로세스 간의 Contest switch 및 interrupt 처리 비용으로 인해 이 수준의 CPU utilization을 달성할 수 없음
  3. 따라서 전반적인 프로세서 활용률을 높여 EDF를 통해 보다 주기적인 작업을 수용할 수 있음
• RMS
  1. 프로세스가 주기적이어야 한다는 요구사항
     • 작업의 우선 순위는 해당 기간에 따라 결정됨
  2. 그럼에도 불구하고 RMS는 산업 응용 분야에서 널리 채택됨
  3. 실제로는 성능 차이가 작고. 방정식(10.2)의 상한은 보수적이다.
  4. 대부분의 하드 실시간 시스템에서 소프트 실시간 실시간 구성 요소도 있다.
  5. RMS를 사용하면 안정성을 더욱 쉽게 확보할 수 있음
     • 우선순위를 변경하려면 작업 기간을 변경해야 함
     • EDF로 인해 RMS보다 우선순위 변경이 복잡해짐