CPU 스케줄링 알고리즘
Multiple-Processor Scheduling
- 멀티 프로세서: 여러 개의 프로세서 적용된 상태. CPU 스케줄링 알고리즘이 복잡해질 수 있음
- 멀티 프로세서 내 CPU 종류가 다를 수도 있음
- 비대칭적 멀티 프로세싱: 한 번에 한 프로세서만 데이터 접근 가능
- 대칭적 멀티 프로세싱(SMP): 한 번에 여러 개의 프로세서가 접근 가능
Processor affinity
- 프로세스는 현재 진행 중인 프로세서에 대한 친화도를 가지고 있음
- Soft affinity: 같은 프로세서에 작동하는 프로세서를 유지한다는 보장 X
- Hard affinity: 항상 같은 프로세서에 작동한다는 보장 O
- 장점: 로드 밸런싱. 각 프로세서마다 서로 다른 프로세스를 할당함
- 단점: 퍼포먼스 오버헤드. 두 프로세서 간의 컨텍스트 스위칭 존재
NUMA 스케줄링
- Non-uniform memory access: 단일하지 않은 메모리에 접근할 수 있음
- Remote memory access는 오버헤드가 커지는 문제점 O
Load balancing
- SMP → 모든 CPU가 효율성을 위해 로드되어야 함
- 작업량이 공평하게 분배하는 게 목적
- Push/Pull migration: 프로세서 상태를 확인하면서 여러 프로세스를 옮기기
Multicore processors
- 같은 피지컬 칩에 멀티 프로세서 코어를 적재
- 더 빠르고 더 저렴한 파워 소모
- 코어 당 멀티 스레드도 커지는 추세: 동시의 SMT, HW 멀티 스레딩 가능(메모리 스톨이 일어나는 동안 다른 태스크 수행 가능)
- 메모리 스톨 시간을 활용하는 Multithreading
- Concurrency: 진행 상태 태스크 한 개 이상을 지원함(하나의 코어에서 여러 개의 스레드 처리)
- 멀티 스레딩 환경에서의 Parallelism: 시스템이 여러 개의 태스크를 동시에 수행하기(멀티 코어 시스템에서 멀티 스레드 처리)
- Data parallelism: 하나의 데이터의 부분집합들이 병렬적으로 처리됨
- Task parallelism: 하나의 태스크의 부분집합-연산이 병렬적으로 처리됨
Amdahl's Law
- 순차/병렬 처리 프로세서 추가를 통해 얻을 수 있는 퍼포먼스 법칙
스레드
- 프로세스: 프로세스 간의 protection domain → 주소 공간이 다르기 때문에 침범할 수 없음. 공유 메모리 옵션에 따라서 일부분을 조회할 수는 있음
- 스레드: 코드/데이터 섹션이 프로세스 내 공유되는 실행 흐름. Light weight - 프로세스보다 경량화되어 있다는 특징. 멀티 스레드 환경에서 스레드는 자신의 레지스터/스택만 보유
스레드의 장점
- Responsiveness: 프로세스 일부가 블락되었을 때 다른 스레드가 블락된 스레드의 작업을 유연하게 이어서 처리
- Resource sharing: 하나의 주소 공간을 모두 공유하기 때문에 효율적인 메모리 참조 가능
- Performance: 프로세스 생성보다 비용이 작고 컨텍스트 스위칭보다 적은 스레드 스위칭
- Scalability: 멀티 코어 환경에서 확장성 존재
Real-time Scheduling
- Soft real-time: 데드라인에 맞춰야 한다는 보장 X
- Hard real-time: 태스크가 데드라인까지 무조건적으로 처리되어야 함
- Latencies: (1). 인터럽트: 인터럽트 도착 - ISR까지 걸리는 지연 시간 (2). 디스패치: 현재 작업을 다른 작업으로 스위칭하는 지연 시간
- 인터럽트 처리 완료 후 다른 작업 수행 가능. Conflict과 dispatch로 이루어진 dispatch latency
- 우선순위에 따라 프로세스 중 어떤 프로세스를 수행할지 정하는 Conflict
- 정해진 프로세스를 dispatch
Priority + Real-time
- 스케줄러: 비선점/우선순위 스케줄링
- hard real-time이라면 데드라인까지 포함
- 프로세스: CPU를 점유하는 프로세싱 시간 T, 데드라인 D, 주기 P.
RM Scheduling
- 우선순위는 주기의 역에 따라 할당: 주기가 짧다면 높은 우선순위, 주기가 길다면 낮은 우선순위
- 특정 프로세스가 자신의 D 안에 완료되는지 확인하기
RM 스케줄링이 데드라인을 준수하지 못할 수도 있다!
- hard real-time에 적절하지 않은 알고리즘
Earliest Deadline First Scheduling (EDF)
- 데드라인에 따라 동적으로 우선순위 할당
- 데드라인이 가까울 수록 우선순위 높고 멀수록 우선순위 낮음
- T마다 프로세스가 돌아오면서 자신에게 남은 데드라인을 동적으로 계산하고 현재 CPU를 점유하고 있는 프로세스와 비교, 스케줄링 실행
Proportional Share Scheduling
- 프로세스가 비율적으로 CPU를 점유하도록 스케줄링
- Admission Control: 시간 점유 비율이 1을 넘지 않도록 (최대 제공율이 100%이기 때문) 체크하기 → 현재 70% 실행 중이라면 30% 이상 요구하는 프로세스는 실행 불가능
Virtualization and Scheduling
- VM의 CPU가 스케줄링 단위 → 게스트 OS가 자신만의 스케줄링 적용 중
- 피지컬 CPU → 호스트 OS → VM → 게스트 OS의 (가상) CPU
Deterministic Evaluation
- 주어진 문제(처리 시간 등 정보가 제공된 여러 프로세스 정보) → 문제에 따라 스케줄링 알고리즘마다 서로 다른 성능 보일 수 있음
Simulations
- 스케줄링 알고리즘을 가상으로 테스트하는 방법
- 알고리즘 퍼포먼스를 간접적으로 알려주는 통계 수치를 파악하는 방법
Impementation
- CPU 스케줄링 알고리즘은 OS에 따라 작동 방식이 달라질 수 있음
JUST DO IT