/ OS

Process Scheduling

Process Scheduling에 대한 개념을 정리하였다.

CPU Scheduling

CPU Scheduler는 프로세스를 ready queue로부터 선택하여 CPU를 할당하는 역할을 한다. CPU Scheduler는 100ms 이하의 짧은 시간마다 동작하며 끊임없이 CPU 코어의 할당을 변경한다.

Context Switch

Interrupt 또는 system call이 발생 시에 Context Switch가 일어난다.

OS 커널은 여러 프로세스의 각 PCB(Process Control Block) 들을 번갈아가며 Store 및 Load 하면서, CPU의 코어 할당 대상을 변경한다. 기존 프로세스의 PCB를 저장하고, 다른 프로세스의 저장된 PCB를 불러와서 스케쥴된 프로세스를 실행한다. 이를 Context Switch라고 한다.

Context Switch에 소요되는 시간은 순수한 overhead에 해당한다. Switching 도중 시스템은 유용한 작업을 수행하지 않기 때문이다.

또한 소요 시간은 Hardware-depedent하다. 레지스터의 지원에 따라 메모리 액세스가 필요할 수도, 필요하지 않을 수도 있기 때문이다.

Thread Scheduling

현대 OS는 프로세스가 아닌 kernel-level thread를 스케줄링한다.

User-level thread는 thread library에 의해 관리된다. 커널은 thread library의 존재를 알지 않는다.

User-level thread들은 LWP에 의해 kernel-level thread에 맵핑된다.

Contention Type

  1. Process Contention Scope (Pink Check School)

    • Scope: Process

    각 유저 레벨 프로세스 내에서, 쓰레드들 간 LWP를 선점하기 위한 경쟁이 일어난다.

    우선순위가 높은 쓰레드가 선택되어 CPU core를 할당받는다.

  2. System Contention Scope (SCS)

    • Scope: System-wide

    시스템 전체 쓰레드 간 CPU 경쟁이 발생한다.

    Thread library는 쓰레드를 가용 LWP에 스케줄링한다. OS는 LWP의 kernel thread를 물리적 CPU core에 스케줄링한다.

PThread Scheduling

PThread에서는 Scheduling Policy 선택을 지원한다.

  • PTHREAD_SCOPE_PROCESS - PCS Scheduling

    유저 레벨 쓰레드를 이용 가능한 LWP에 할당한다.

  • PTHREAD_SCOPE_SYSTEM - SCS Scheduling

    각 유저 레벨 쓰레드에 대한 LWP를 생성하고 연결한다.

Multi-Processor Scheduling

  • 전통적 Multiprocessor 정의: 단일 코어를 가진 물리적 CPU가 여러 개 이상 존재

  • 현대의 Multiprocessor 유형

    • Homogenous (Symmetric Multiprocessing, 각 개체가 동일한 기능 수행)
      • Multicore CPUs
      • Multithreaded CPUs
      • NUMA(Non-Uniform Memory Access) systems
    • Heterogenous Multiprocessing (Assymetric Multiprocessing, 기능적으로 서로 다른 작업 수행)

Scheduling in Multiprocessor Systems

  1. Assymetric Multiprocessing

    모든 스케줄링 결정을 master가 처리한다.

  2. Symmetric Multiprocessing (SMP)

    각 프로세서가 개별적으로 스케줄링을 수행 가능하다.

Scheduling in SMP

각 쓰레드를 SMP에서 조직화하여 관리하는 방법은 다음과 같다.

  1. Common Run Queue - 코어들이 하나의 thread queue를 공유할 수 있다. 이 경우, race condition이 발생 가능하므로 이를 handling할 수단이 필요하다.

    • queue에서 쓰레드가 손실되지 않도록 보장해야 한다.
    • 서로 다른 코어가 동일한 thread를 스케줄하지 않도록 보장해야 한다.
    • race condition을 방지하기 위해 locking을 사용할 수 있다.

  2. 각 코어마다 서로 다른 queue를 사용할 수 있다. 각 코어마다 작업량의 차이가 발생할 수 있으므로 load balancing 작업이 필요하다.

Multithreaded Processing Core

Memory Stall

메모리는 CPU보다 속도가 느리므로, CPU는 메모리 접근 시 데이터가 이용가능해질 때까지 기다려야 하는 경우가 있다. 이러한 경우를 Memory Stall이라고 한다.

Multithreaded Processing Core

이러한 상황을 방지하기 위해, 현대 CPU는 Multithreaded processing core들을 구현한다.

이 방식에서는 둘 이상의 hardware thread를 하나의 core에 할당한다. 즉, 하나의 물리 core가 각 hardware thread에게 논리적 CPU를 각각 할당하게 된다.

한 thread에 stall이 발생하면, core가 다른 thread로 전환하여 작업을 수행한다.

OS 관점에서는 해당 Hardware thread들을 여러 software thread를 실행하는 논리적 CPU로 보고 스케줄링을 수행한다.

이를 Intel에서는 Chip MultiThreading(CMT) 라고 한다.

프로세서가 4개의 코어를 갖고 있고, 각 코어가 2개의 hardware thread를 포함하는 경우, OS에서는 8개의 논리적 CPU가 이용가능한 것으로 보인다. (4코어 8쓰레드)

Multithread a Processing Core

  1. Coarse-grained multithreading

    Memory stall과 같은 long-latency 이벤트 발생 전까지 한 core에서 실행되다가, 명령 pipeline이 비워진 후 switching이 완료된다. 명령 pipeline을 비우는 과정으로 인해, switching 부하가 높다.

  2. Fine-grained multithreading

    Instruction cycle이라는 더욱 세밀한 단위에서 switching이 발생한다. Thread 간 전환 비용이 작다. Architectural Design 단계에서 먼저 쓰레드 교환 회로가 구현되어야 한다.

Levels of Scheduling

하나의 Processing core는 한번에 하나의 hardware thread를 실행할 수 있다.

캐시/파이프라인과 같은 물리적 자원은 각 core에 탑재된 hardware thread간에 공유된다.

상위 단계(level 1)에서 먼저 OS scheduler에 의해 software thread가 선택된 후, 하단(level 2)에서 hardware thread(logical CPU)가 할당된다.

Hardware thread는 core scheduler에 의해 선택된다.

단순한 Round-robin 방법으로 선택되거나, hardware thread마다 urgency값을 부여하고 switching을 trigger하는 이벤트 발생 시 urgency에 따라 적절한 hardware thread를 할당하는 방법이 있다.

Software Thread to Hardware Thread Mapping

각 software thread는 동일한 core에 할당될 수도, 서로 다른 core에 할당될 수도 있다. 동일한 core에 할당되면 race condition이 발생하여 비효율적이므로 OS scheduler에게 자원에 대한 정보를 공유하여 효율적으로 core를 할당할 필요가 있다.

Load Balancing

SMP 시스템에서는 Multiprocessing의 이점을 활용하기 위해 부하를 최대한 균등하게 배분하는 것이 중요하다.

Common run queue (각 코어가 같은 queue 공유) 이용 시에는 필요하지 않다.

Approaches

  1. Push migration

    특정 task가, 주기적으로 load를 검사하여 imbalance가 발생 시 thread를 move/push 함으로써 load balancing을 수행한다.

  2. Pull migration

    Idle한 processor가 직접 busy한 processor로부터 task를 pull 하여 load balancing을 수행한다.

두 방법을 동시에 혼합하여 사용할 수도 있다.

Definition of “Balanced Load”

  • 개수 측면: 모든 큐에 대략적으로 동일한 개수의 thread 분포, 보통의 경우 이 경우를 일컫는다.

  • 우선순위 측면: 모든 큐에 대략적으로 동일한 우선순위의 thread 분포

Processor Affinity

한 thread가 특정 프로세서에서 실행될 때, 캐시 메모리에는 무슨 일이 발생할까?

Warm Cache

Thread에 의해 연속적인 메모리 접근이 발생하면 최근 사용된 데이터는 캐시 메모리에 저장 및 로드될 수 있다.

Load Balancing and Cache

Load Balancing에 의해 한 쓰레드가 다른 processor로 migration이 발생할 수 있다. 이 경우, 이전 core에서 사용하던 warm cache를 사용할 수 없게 된다. 따라서 새로운 core에 다시 데이터를 채워 넣어야 하는 일이 발생하게 된다.

따라서 OS는 되도록이면 thread의 core migration을 피하려고 한다. 이 경우 프로세스는 특정 core에 대한 affinity를 가진다고 할 수 있다.

Thread queue의 구성이 processor affinity에 영향을 미친다.

Common ready queue의 경우, thread는 기본적으로 임의의 processor에서 실행 가능하다. 따라서 core migration의 가능성이 존재한다.

Priviate, per-processor(core) ready queue의 경우, thread는 항상 특정 processor에서만 실행 가능하다. 따라서 core migration의 가능성이 없다. 그러므로, processor affinity가 제공된다고 볼 수 있다.

Forms of Affinity

  1. Soft Affinity

    Thread가 특정 processor에서 실행되도록 요청할 수 있지만, OS는 이를 보장하지 않는다.

  2. Hard Affinity

    Thread가 특정 processor에서 실행되도록 요청할 수 있고, OS는 이를 보장한다.

많은 시스템은 두 가지 형태를 모두 제공한다.

예를 들어 Linux는 기본적으로 soft affinity이나, sched_setaffinity()를 통해 hard affinity를 제공하기도 한다.

Main-memory Architecture

NUMA의 경우, OS Scheduler 및 Memory Placement 알고리즘이 NUMA-aware 일 때, 특정 thread에게 할당된 CPU에게 가까운(접근 속도가 빠른) 메모리 위치를 할당하게 된다.

Heterogeneous Multiprocessing (HMP)

task의 요구에 기반하여 특정 core에 할당함으로써 전력 소모를 관리한다.

예) big.LITTLE for ARM

  • big core: high performance, high power consumption

  • LITTLE core: low performance, low power consumption

고성능을 요구하지만 짧은 기간 실행되는 foreground, interactive task에는 big core가 할당된다.

반면, low performance를 요구하지만 긴 기간 실행되는 background, non-interactive task에는 LITTLE core가 할당된다.

절전 모드에 들어간 mobile device는 big core를 disable하기도 한다.

Real-Time CPU Scheduling

  • Soft real-time system

    되도록이면 task 수행의 deadline을 맞추지만, deadline을 맞추지 못하는 경우가 있을 수 있다.

    process가 덜 중요한 process보다 우선적으로 스케줄 된다는 것만 보장한다.

  • Hard real-time system

    task 수행의 deadline을 반드시 맞춰야 한다. Deadline 이후의 service는 전혀 service를 수행하지 않은 것과 동일시된다.

    예) 자율주행차의 긴급 제동 시스템(ABS)은 반드시 실시간으로 동작해야 한다.

Minimizng Latency

  • 이벤트 발생

    1. 시스템은 이벤트 발생을 대기한다.
    2. 소프트웨어적(타이머 만료) 또는 하드웨어적으로 이벤트가 발생할 수 있다.
    3. 이벤트 발생 시, 시스템은 가능한 한 빨리 반응하여 서비스를 최대한 빨리 수행해야 한다.

이벤트 발생 시점으로부터, 시스템이 응답하는 시점까지의 시간을 event latency라고 한다.

이벤트에 따라 요구되는 event latency는 다를 수 있다.

Interupt Latency

  • interrupt 발생으로부터 CPU가 interrupt에 따른 routine을 실행하기까지의 시간을 지칭한다.

  • OS는 실행중이던 명령을 완료한 후 발생한 인터럽트 type을 결정한다.

  • 현재 process의 상태를 저장하고 Interrupt Service Routine을 이용하여 처리한다.

실시간 task가 즉시 수행되도록 interrupt latency를 최소화하는 것이 중요하다.

Hard real-time system에서는 단순한 최소화가 아닌, 시스템의 엄격한 요구 사항을 충족해야 한다.

커널 데이터 구조가 업데이트되는 동안 interrupt가 비활성화 되는 시간은 interrupt latency에 영향을 미치는 중요한 요인 중 하나이다.

Real-time OS에서는 이러한 비활성화 시간을 최소화해야 한다.

Dispatch Latency

Scheduling dispatcher가 한 프로세스를 멈추고 다른 것을 시작하기 위해 필요한 시간에 해당한다.

CPU에 즉시 접근해야 하는 실시간 task를 실행하는 실시간 OS는 이 dispatch latency도 최소화해야 한다.

Preemptive(선점형) kernel을 사용하면 dispatch latency를 최소화할 수 있다.

Hard real-time system에서는 평균 수 microseconds 내이다.

  • Conflict phase

    1. 커널 프로세스의 선점
    2. 낮은 우선순위의 프로세스는 더 높은 우선순위의 프로세스에 의해 자원을 해제

  • Dispatch phase: 높은 우선순위의 프로세스를 이용가능한 CPU에 스케줄한다.

두 phase의 시간을 합한 것이 dispatch latency이다.

Priority-based Scheduling

기본적으로 soft real-time scheduling 제공

Hard real-time system 에서는 추가적인 scheduling 기법 필요

Properties

각 process는 주기적이다. 즉, 일정 간격으로 CPU를 요구한다.

t: 고정된 처리 시간 p: 프로세스의 주기 d: deadline

라고 할 때,

\[0 \leq t \leq d \leq p\]

의 관계를 가진다.

rate of a periodic task =\(\frac{1}{p}\)

(주기가 짧을수록 우선순위가 높음)

프로세스는 스케줄러에게 자신의 deadline을 알려야 한다.

Rate-Monotonic (RM) Scheduling

rate of a periodic task = \(\frac{1}{p}\)

(주기가 짧을수록 우선순위가 높음)

deadline과 주기가 같다. (p=d)

각 주기당 CPU 사용 시간(또는 처리 시간 = t), 즉 \(\frac{t}{p}\)를 측정한다. 각 프로세스의 t/p를 더하면 CPU 이용률을 계산할 수 있다.

Deadline을 맞추면서, 이용가능한 CPU cycle이 남도록 스케줄링한다.

우선 순위가 높은 프로세스부터 실행해야 deadline 맞추기가 용이하다.

RM Scheduling은 optimal한 것으로 간주되며, 이 알고리즘으로 실시간 스케줄링이 불가능한 경우는 static priority를 부여하는 경우에 한해, 어떤 다른 알고리즘으로도 불가능하다고 알려져 있다.

CPU 이용률이 100% 미만인 경우에도 스케줄링이 불가능할 수 있으므로 주의해야 한다.

Earliest-Deadline-First (EDF) Scheduling

deadline이 가장 이른 프로세스에게 높은 우선순위를 동적으로 부여한다.

process가 실행가능해지면, 시스템에 자신의 deadline을 알려야 한다.

새로 실행가능한 process의 deadline을 반영해서 우선순위가 계속 조정된다.

process들의 주기마다 각 process의 deadline을 확인하고, deadline이 가장 임박한 프로세스에게 높은 우선순위를 부여한다.

RM 알고리즘과 달리 CPU burst time이 상수일 필요도 없고, process가 주기적일 필요도 없다.

동적 priority 부여 알고리즘 중에서, 이론적으로 optimal하다.

Proportinal Share Scheduling

모든 application을 합쳐 총 시간 T를 할당받는다.

각 application은 T의 일부에 해당하는 자신의 share를 가지고 있다.

새로운 프로세스가 요구하는 share가 T를 초과할 때, 그 요청을 무시한다.

POSIX Real-Time Scheduling

POSIX는 real-time thread를 위해 두 개의 scheduling class를 정의한다.

  • SCHED_FIFO : First-In-First-Out
  • SCHED_RR : Round-Robin
  • SCHED_OTHER : 구현이 정의되어 있지 않고 시스템에 따라 다르다.

Algorithm Evaluation

시스템 환경에 따라 적절한 Scheduling Algorithm을 선택해야 한다.

  • 기준 설정: 중요도에 따라 성능을 평가할 기준을 정의한다.
  • Deterministic Modeling: 미리 정의된 특정 작업 부하를 이용하여 수학적으로 각 알고리즘의 성능을 평가한다.
  • Simulation: 모의 환경을 구축하여 알고리즘을 실제로 실행하여 성능을 평가한다.
  • Implementation: 실제 시스템에서 테스트한다.