리눅스와 윈도우 스케줄링 비교 - Operating System 5-3

리눅스와 윈도우가 CPU 스케줄링을 어떻게 구현하는지 비교하고, 실제 운영체제에서 스케줄링 정책이 어떤 방식으로 적용되는지 정리합니다.

xmoonanx 14 min
리눅스와 윈도우 스케줄링 비교 - Operating System 5-3

🍀 운영체제 전공 수업 정리

Linux Scheduling Through Version 2.5

2.5 이전에는 표준 UNIX 스케줄링 알고리즘의 변형을 사용, 2.5부터는 상수 시간 O(1) 스케줄링 시간을 가진 알고리즘으로 전환

  • O(1) scheduling time: 상수 알고리즘 ✅특징:
    1. Preemptive, priority based
    2. 우선순위가 2가지로 나뉨
  • 1~99: real-time class(낮은 숫자 = 높은 우선순위 주의!)
  • 100~140: conventional class
    1. 전역 우선순위 매핑
  • 숫자가 낮을수록 높은 우선순위
  • 우선순위가 높을수록 더 큰 시간 할당량(quantum)을 받음
    1. 태스크 상태 관리
  • 시간 할당량이 남아있으면 태스크는 active(실행 가능)
  • 시간 할당량을 모두 사용하면 expired(다른 태스크가 모두 시간 할당량을 사용할 때까지 실행 불가)
    1. runqueue 데이터 구조
  • 각 CPU마다 존재하는 실행 가능한 태스크 추적 구조
  • 두 개의 우선순위 배열 (active, expired)
  • 태스크는 우선순위로 인덱싱됨
  • active 배열이 비면 active와 expired 배열을 교체

alt text

O(1) 스케줄러는 효율적으로 작동했지만, 인터랙티브 프로세스에 대한 응답 시간이 좋지 않았음

Linux Scheduling in Version 2.6.23+

앞의 linux O(1) 스케줄러 이후 2.6.23부터는 CFS를 도입

📚Completely Fair Scheduler(CFS):

  • CFS는 우선순위를 직접 할당하지 않고 virtual run time에 따라 동적으로 조정
  • runnable 태스크 중에서 virtual run time이 가장 작은 것을 먼저 실행
  • → 고정된 시간 할당 대신 CPU 시간의 비율에 기반한 스케줄링

Sheduling Classes

리눅스 커널에서 다양한 프로세스랑 스레드를 관리하기 위한 프레임 워크 기본적으로, Linux Scheduling은 Scheduling class에 의존하여 작용

  • 각 클래스는 특정 우선순위를 가진다
  • 스케줄러는 가장 높은 스케줄링 클래스에서 가장 높은 우선순위 태스크를 선택
  • 기본적으로 2개의 클래스가 포함되며 추가 확장 가능:
    • Defalut(CFS)
    • real-time(RT)

virtual run time과 nice value란??

  • virtual run time: 프로세스가 CPU를 사용한 시간을 추적하는 매트릭 → 단순히 물리적 실행시간 X, 우선순위(nice value)에 따라 가중치 적용된 시간
  • CFS는 각 태스크별로 virtual run time을 vruntime 변수에 저장
  • 가장 낮은 vruntime값을 가진 태스크를 다음에 실행할 테스크로 선택함
  • 태스크가 실행되면 실행 시간에 따라 vruntime이 증가
    • 많은 CPU 시간을 사용한 프로세스는 우선순위가 낮아짐
    • 적은 CPU 시간을 사용한 프로세스는 우선순위가 높아짐
  • nice value: nice value는 -20부터 +19까지의 범위를 가진다
  • nice value↓(-20) = 우선순위↑
  • nice value↑(+19) = 우선순위↓

  • 기본값은 0

  • nice value는 대상 지연(target latency)계산에 적용된다
    • target latency: 모든 실행 가능한 task가 적어도 한 번은 실행되어야 하는 시간 간격(= 응답 시간)
    • 활성 task 수가 증가하면 각 task의 timeslice(=context switching)이 짧아짐 → target latency 증가
  • nice value에 따라 decay계수가 결정
    • decay 계수: 실제 실행 시간에서 가상 실행 시간으로 변환할 때 적용되는 계수
    • 우선순위가 낮을수록(=값이 클수록) decay 계수가 높아진다
    • nice = 0인 경우, 가상 실행 시간 = 실제 실행 시간

alt text

리눅스는 POSIX.1b 표준에 따라 실시간 스케줄링을 지원

  • 실시간 작업과 일반 작업을 글로벌 우선순위 체계로 통합
  • nice value -20: 글로벌 우선순위 100에 매핑 (가장 높은 일반 우선순위)
  • nice value 0: 글로벌 우선순위 120에 매핑 (기본 우선순위)
  • nice value +19: 글로벌 우선순위 139에 매핑 (가장 낮은 우선순위)
  • 리눅스는 load balancing 뿐만 아니라 NUMA-aware도 지원함
    Scheduling Domain
  • Scheduling Domain: load balacing이 가능한 CPU 코어의 집합
  • domain은 공유하는 자원(ex: 캐시 메모리)에 따라 구성된다
  • 또한 스레드가 도메인 간에 migration되는 것을 방지

스레드가 다른 노드로 migration되면 여러 문제가 발생!

  1. Cold Cache 문제:
    • 새 노드의 캐시는 스레드의 데이터를 포함X → 캐시를 다시 채우는데 시간 소요
  2. 원격 메모리 접근 증가:
    • 스레드가 원래 할당된 노드의 메모리를 계속 사용하면 원격 접근 발생
    • → 메모리 접근 지연 시간이 증가함

alt text

캐시 L1은 각 CPU코어에 전용으로 할당
L2는 코어별 또는 코어 쌍별로 할당
L3는 NUMA 노드 전체가 공유

Window Scheduling

📚Window Scheduling: 우선순위 기반 선점 스케줄링

✅스레드 실행 조건:

  1. 블록(block) 상태가 되었을 때 (예: I/O 작업 대기)
  2. 할당된 시간 할당량(time slice)을 모두 사용했을 때
  3. 더 높은 우선순위의 스레드에 의해 선점되었을 때
  4. 스레드가 종료되었을 때
  • real-time 스레드는 non-real-time(일반) 스레드를 선점 가능

윈도우는 32-level의 우선순위 scheme가 있다

  • Variable class: 1-15
  • real-time class: 16-31
  • 우선순위 0은 메모리 관리 스레드

  • 숫자가 클수록 우선순위가 높다(리눅스와 차이점 주의)

  • 각 우선순위마다 별도의 Queue(=ready queue)가 존재
  • 실행 가능한 스레드가 없으면 idle thread가 실행

Windows Priority Classes

window OS는 두 단계의 우선순위 체계를 사용

  1. Priority Class: 프로세스에 할당되는 우선순위
  2. Relative Priority: 같은 Priority Class 내에서 스레드에 할당되는 우선순위

Priority Class

  1. REALTIME_PRIORITY_CLASS: 가장 높은 우선순위
  2. HIGH_PRIORITY_CLASS
  3. ABOVE_NORMAL_PRIORITY_CLASS
  4. NORMAL_PRIORITY_CLASS: 일반적인 애플리케이션의 기본 우선순위
  5. BELOW_NORMAL_PRIORITY_CLASS
  6. IDLE_PRIORITY_CLASS: 시스템이 Idle 상태일 때만 실행되는 가장 낮은 우선순위
  • Real-time을 제외한 모든 Priority Class는 가변적 → 시스템이 필요에 따라 우선순위 조정 가능

Relative Priority

  1. TIME_CRITICAL: 같은 클래스 내에서 가장 높은 우선순위
  2. HIGHEST
  3. ABOVE_NORMAL
  4. NORMAL: 기본 우선순위
  5. BELOW_NORMAL
  6. LOWEST
  7. IDLE: 같은 클래스 내에서 가장 낮은 우선순위
  • Priority Class + Relative Priority = 숫자 우선순위(Numeric Priority) alt text

✅윈도우는 다음과 같은 경우에 우선순위를 동적으로 조정:

  1. quantum 만료: 우선순위 하락, 기본 우선순위보다 낮아지지는 않음
  2. 대기 상태 발생: 스레드가 아무것도 안하고 있으면 우선순위 상승(Variable class에 속한 task만 해당, 키보드I/O>디스크I/O)
  3. Foreground window: 사용자가 현재 활성화한 창은 3배의 우선순위 부스트를 받음
    • Varialbep priority 스레드가 I/O 작업을 기다리면 디스패처가 우선순위를 상승 → I/O-bound 스레드가 CPU-bound 스레드보다 우선시됨을 의미

UMS(User-Mode Scheduling)

Window 7부터는 User-Mode Scheduling(UMS)이 추가됨

✅UMS 특징:

  • 애플리케이션이 커널과 독립적으로 스레드를 생성하고 관리
  • 대량의 스레드를 처리할 때 훨씬 효율적
  • UMS 스케줄러는 C++ Concurrent Runtime(ConcRT) 프레임워크와 같은 프로그래밍 언어 라이브러리에서 제공

Algorithm Evaluation

운영체제에서 CPU 스케줄링 알고리즘을 선택하는 것은 시스템 성능에 큰 영향을 미치는 중요한 결정이다

✅스케줄링 알고리즘 선택 과정:

  1. 평가 기준 설정
  2. 알고리즘 평가
  3. 최적 알고리즘 선택

✅CPU 스케줄링 알고리즘 평가 방법:

  1. Deterministic modeling
  2. Queueing models
  3. Simulations
  4. Implementation

Deterministic modeling

📚Deterministic modeling: 분석적 평가(analytic evaluation) 유형

  • 특정한 미리 정의된 워크로드에 대해 각 알고리즘의 성능을 정확히 계산
    • 간단하고 빠른 평가 방법
    • 정확한 입력값이 필요하며, 해당 입력에만 적용 가능
    • 주로 평균 대기 시간과 같은 성능 지표를 계산

alt text

  1. FCFS-average waiting time = 28ms
  2. Non-preemptive SJF-average waiting time = 13ms
  3. RR-average waiting time =23ms

❌특정 워크로드에 대해서만 성능을 평가해서 다양한 조건에서의 알고리즘 성능을 일반화하기 어려움

Queueing Models

📚Queueing Models: 프로세스의 도착과 CPU 및 I/O 버스트를 확률적으로 표현하는 방법

✅특징:

  • 지수 분포(exponential distribution)를 사용하고 평균값(mean)으로 표현
  • 처리량, 자원 활용률, 대기 시간 등의 성능 지표 계산

Little’s Formula

📚Little’s law: ‘$n = λ * W$’ = 안정 상태에서 시스템 내의 평균 프로세스 수(n)는 도착률(λ)과 평균 대기 시간(W)의 곱과 같음

  • $n$ = queue length의 평균(jobs)
  • $W$ = queue에서의 평균 wating time(sec)
  • $λ$(도착률) = queue에 도착하는 평균량(jobs/sec)

    ex: 초당 7개의 프로세스가 도착, queue에 14개 프로세스가 있다면 평균 wait time은??
    n = 14, λ = 7 → $W = n/λ = 2(sec)$

❌실제 시스템의 복잡성을 완전히 반영X

Simulations

Queue model보다 Simulations이 더 정확함

  • 컴퓨터 시스템의 프로그래밍 모델을 사용
  • 시간을 변수로 취급 → 알고리즘 성능 통계 수집

✅simulation data 수집 방법:

  1. Random number generator
    • 확률에 따라 이벤트 생성
  2. Distributions of mathematically(수학적)/empirically(경험적)
    • 수학 공식으로 정의된 분포
    • 실제 시스템을 관찰해 얻은 경험적 데이터
  3. Trace tapes
    • 실제 시스템에서 발생한 이벤트 기록

alt text

  1. 트레이스 테이프나 생성된 데이터를 입력으로 받음
  2. 여러 알고리즘(FCFS, SJF, RR 등)에 대해 동일한 입력으로 시뮬레이션 실행
  3. 각 알고리즘의 성능 통계(CPU 사용률, 대기 시간, 응답 시간, 처리량 등) 수집
  4. 결과 비교를 통해 특정 워크로드에 가장 적합한 알고리즘 선정

Implemenation

Simulation으로 알고리즘의 성능을 충분히 평가해도 실제 시스템에서 동작은 다를 수 있다 Implemenation: 최종적으로 실제로 구현하고 테스트해봐야 함

  • 가장 정확한 성능 평가 방법
  • 높은 비용과 위험이 수반됨
  • 실제 환경의 모든 변수를 고려할 수 있음

📝4가지 평가 방법 비교
alt text alt text