• Linux Scheduling: (1). O(1) 스케줄러 - 속도 빠르지만 응답 속도가 느림 (2). CFS: O(1) 스케줄러 + defualt/real-time 스케줄러

CPU 스케줄러 알고리즘

CFS Scheduling

• nice value: -20 ~ +19 값 할당 → Quantum 계산, 낮은 값 = 높은 우선순위
• target latency: 최소 한 번 태스크가 실행되어야 하는 시간, 주기. 하나의 태스크 당 만족해야 하는 최소 latency. active 태스크가 늘어날 경우 늘어날 수 있음 → 스케줄링 주기를 계산하는 _sched_period. 현재 실행 중인 프로세스 개수를 계산.
• virtual runtime: 현재 실행 시간, 우선순위 따라서 할당. 레드 블랙 트리를 통해 할당 → calc_delta_fair 함수를 통해 v runtime 계산
• 레드 블랙 트리: 이진 탐색 노드. 특정 노드의 크기는 왼쪽 노드보다 크고 오른쪽 노드보다 작다. (균형 + 효율)

Linux CPU Scheduling

• 디폴트 + Real-time 방식 구현
• Real-time: 전역 우선순위

Windows CPU Scheduling

• 선점형, 우선순위 기반 CPU 스케줄링
• 프로세스: 타임 슬라이스 모두 사용 / 우선순위 더 높은 프로세스 존재 / 모든 작업 수행 → 스케줄러에 의해 다른 프로세스 할당
• 디스패처 = 스케줄러
• 우선순위가 리눅스 레벨보다 세분화(총 32레벨) - 각 우선순위마다 큐 존재
• Starvation 방지 위한 Wait 시 우선순위를 높여주는 Boost 존재
• Foreground 프로세스는 Background 프로세스보다 우선순위 세 배로 높음
• 유저 모드 스케줄링: 커널과 독립적으로 스레드 생성 및 관리 가능. 스레드 양이 많다면 매우 효율적

POSIX Real-Time Scheduling

• API → real-time 스레드 관리하는 함수 제공
• real-time 스레드에 대한 두 가지 스케줄링 클래스 정의(FIFO, RR)