챕터 5: CPU Scheduling
Basic Concepts
- CPU Utilization을 극대화하기 위해서는 CPU가 노는 시간이 없도록 해야함
- CPU burst Process와 I/O burst Process가 번갈아 가며 실행됨
burst duration에 따른 빈도수 그래프
- I/O burst Process가 훨씬 많음을 보임
=> 이런 Process들을 잘 스케줄링하여 CPU가 노는 시간을 최소화 하도록 해야함
CPU Schedular
- ready queue에 있는 프로세스를 선택하고 CPU자원을 할당
Dispatcher
- context switch가 일어날 때 이를 처리하는 모듈
- dispatcher가 cpu를 중단 시키고 다음 프로세스가 실행될 때까지의 시간을 dispatch latency라함
Scheduling 평가요소
CPU utilization: cpu가 활용되는 정도, %로 나타냄
Throughput: 시간당 프로세스 처리량, scheduling 방법보단 프로세스 종류에 영향을 많이 받음
Turnaround time: 특정 프로세스가 대기하는 시간 + 실행시간 즉, 총 처리 시간
Waiting Time: 특정 프로세스가 대기하는 시간
Response Time: 특정 프로세스가ready queue에 올라가 처음 running되기 까지의 시간
Scheduling 알고리즘
FCFS(First-Come, First-Served)
FCFS
- 가장 단순한 알고리즘으로 먼저 queue에 들어온 순서대로 실행
- convoy effect가 발생할 수 있음
- Nonpreemptive함
convoy effect: 긴 실행시간을 가진 작업이 다른 짧은 실행 시간을 가진 작업을 block시키는 것
SJF(Shortest-Job-First)
SJF
- 실행시간(CPU burst time)이 짧은 순으로 실행
- 평균 대기 시간이 가장 짧은 최적의 알고리즘
- CPU Burst를 예측해야되기 때문에 실제로는 적용이 어려움
선점 알고리즘(Shortest-Remaining-Time-First)
- SJF는 비선점 알고리즘으로 실행 중인 작업과는 비교하지 않지만
- SRTF는 선점 알고리즘으로 새로 들어온 작업의 실행시간이 실행 중인 작업의 남은 시간보다 작으면 선점한다
RR(Round-Robin)
- 정해진 실행시간을 각 작업들이 나눠서 사용하는 방법, 이 정해진 시간을 time quantum이라 한다
Time Quantum
- 만약 time quantum이 모든 작업의 실행시간보다 크다면 FCFS와 같다
- 만약 time quantum이 너무 작다면 지나친 context switch가 일어나 성능이 저하된다
=> 따라서 적당한 time quantum size가 필요하다
time quantum = 4 인 RR
- 일반적으로, waiting time과 turnaround time은 SJF에 비해 떨어지지만 response time은 더 좋다
Priority
- 우선순위를 부여하여 순서를 정하는 방법
- SJF도 실행시간을 기준으로 우선순위를 부여했다고 볼 수 있다
문제점 및 해결방법
- 낮은 우선순위가 실행되지 않는 starvation이 발생할 수 있음
- 오래 대기한 작업의 우선순위를 높이는 aging을 사용하거나
- 일정 실행시간이 보장되는 RR을 결합시켜 사용
Priority와 RR의 조합
- 이 부분이 시험문제에 나와서 약간의 논란이 있었는데 포인트는 'RR이 priority를 무시하고 선점할 수 있느냐 아니면 RR이어도 priority가 더 우선이다' 이었다.
배울 때는 같은 우선순위만 RR을 적용하는 것이었는데 시험문제에서는 같은 우선순위인 것이 없는 채로 RR을 결합한 문제 나왔고 따로 명시가 되어있지 않은채로 헷갈리게 나왔다.
이에 대해 GPT에게 물어보니
그런데 이방법을 사용하는 이유 자체가 starvation을 줄이기 위해서 였는데 같은 우선순위에서만 적용하면 starvation문제가 여전히 해결되지 않는 것 같아 다시 물어봤더니
라고한다.
결론적으로,
priority와 RR의 결합은 일반적으로는 같은 우선순위에 대해서만 RR을 적용시키고 추가적으로 aging알고리즘도 함께 결합하여 starvation을 해결할 수 있다고 보면 될 것 같다.
Multilevel Queue
multilevel queue
- ready queue를 여러개로 나누어 큐 자체에 우선순위를 부여하여 작업을 실행시키는 방법
- 각각의 큐는 상황에 맞게 스케줄링 기법을 선택할 수 있지만 일반적으로 RR을 사용
- 모든 큐가 RR을 사용하면 앞의 priority & RR의 combining한 기법을 구현한 것임
- 우선순위 기법을 베이스로 했기 때문에 starvation이 생길 수 있음
Multilevel Feedback Queue
- multilevel queue에서 starvation을 방지하기 위한 방법
- 낮은 priority의 queue에 너무 오래 있다면 더 높은 우선순위 queue로 옮김, 그리고 이것이 곧 aging 기법
Thread Scheduling
PCS(Process-contention Scope)
- 유저 스레드가 LWP를 점유하기 위한 경쟁의 범위(in process)
SCS(System-contention Scope)
- 커널 스레드가 CPU를 점유하기 위한 경쟁의 범위(in System)
Multi-Processor Scheduling
Asymmetric/ Symmetric multiprocessing
multiple-processor에서의 두 가지 전략
Asymmetric multiprocessing: 하나의 프로세서가 모든 스케줄링을 관리하는 것, 하나의 공통 큐를 가짐
symmetric multiprocessing: 각각의 프로세서가 자신의 큐에서 스케줄링 하는 것, 각자의 큐를 가짐
Multicore Processor
- 최근에는 더 빠르고 전력소모가 적은 멀티코어를 많이 사용한다
- 동시에 각각의 코어에 내장된 하드웨어 스레드도 많이 사용한다
Multithreaded multicore system을 이용하여 Memory stall을 해결
=> 이렇게 하나의 코어 내에 동시에 여러개의 스레드가 실행되어 성능을 향상시킬 수 있다.
이를 hyper-threading(Intel용어) 또는 Simultaneous Multithreading(AMD용어)이라 부른다
Two levels of scheduling
Two levels of scheduling
- Multithreaded multicore processor는 물리적 하드웨어가 존재하기 때문에 두 번의 schduling을 거쳐야 한다.
- level1이 기존의 thread를 스케줄링하는 것이고
- level2가 어떤 hardware thread를 사용할지 스케줄링 하는 것이다.
Load Balancing
- SMP 시스템을 이용할 때 모든 CPU가 고루 사용되어야 하는데, 이를 Load Balancing이라 한다
push migration: 밸런스를 맞추기 위해 overload된 CPU에서 idle CPU로 작업을 분산 시키는 것
pull migration: idle CPU에서 busy processor의 작업을 가져오는 것
Processor Affinity
- 프로세스가 실행되고 있던 프로세서에 친화성을 가지는 것(캐시 메모리 활용을 위해)
soft affinity: 원래 프로세서에서 실행되기를 유지하려고는 하지만, load balancing의 이유로 다른 프로세서로 갈 수 있음
hard affinity: 시스템 콜을 사용하여 프로세스를 실행할 CPU에 바인딩 되는 경우
NUMA
NUMA 구조
- NUMA의 구조자체가 Affinity가 보장이 되는 구조임
Heterogeneous Multiprocessing
- 같은 코어 구조를 가지고 있지만 전력소모와 clock speed에 차이를 가지는 구조
ex) ARM processor의 big.LITTLE
높은 성능이 요구되는 작업에는 big core를
성능보단 낮은 전력 소모가 요구되는 작업에는 little core를 사용
Real-Time CPU Scheduling
Soft read-time vs Hard real-time
soft real-time: deadline을 보장하려고 노력하는 시스템
hard real-time: deadline이 보장되는 시스템
Latency의 최소화
- real-time은 반응속도가 매우 중요하여 Latency를 최소화 시키는 것이 관건이다
event 처리 과정
Event latency: 이벤트가 일어나고 이 이벤트에 대한 반응이 일어나기 까지의 시간
Interrupt latency: 인터럽트가 발생하고 인터럽트 서비스 루틴이 시작 될 때까지의 시간
Dispatch latency: 현재 실행중인 프로세스를 해제하고 새로운 프로세스로 전환 시키기까지의 시간, 서비스 루틴까지의 처리가 완료된 뒤에 일어남
=> 반응시간을 빠르게 하기 위해 event latency를 최소화 시키기 위해서는 interrupt latency와 Dispatch latency를 최소화 해야한다
priority-based Scheduling
- real-time scheduling은 선점적이고 우선순위를 기반으로 한 스케줄링 기법을 사용해야한다
- 주기적으로 발생하는 작업을 먼저 고려하여, 이 작업들을 예측 가능한 주기와 패턴 내에서 처리하기 위한 방법을 사용한다.
- 이때 사용하는 개념이 각각 time t, deadline d, period p이고 0 ≤ t ≤ d ≤ p
- 하나의 주기에 데드라인을 두고 그안에 작업을 실행해야함
Rate Monotonic
- 주기가 짧은(자주 실행해야 하는)작업이 우선순위가 높도록 하는 방법
- 시간이 급한 것을 먼저 처리하므로 deadline을 더 잘 지킬 수 있음
ex) p1 = 50, t1=20 / p2=100, t2=35
Rate Montonic X
Rate Montonic O
- 같은 조건에서 Rate Montonic 스케줄링을 적용한 것이 더 안정적임을 볼 수 있음
- 스케줄링하는 프로세스의 개수가 N 일때 N(2^(1/N) - 1) 보다 CPU Utilization이 작으면 deadline을 넘지 않음
- 이경우에는 약 83% > 75%이므로 가능
EDF(Earliest Deadline First)
- 각 주기의 시작마다 deadline을 비교하여 우선순위를 정하는 방법
- CPU Utilization이 100%보다 작기만 하면 된다
Propotional Share
- 각 프로세스의 할당량만큼 작업시간을 부여하는 방식, 주기적인 방식이 아님
- 만약 전체 시간을 넘는 요청이 추가로 들어오면 거절한다.
