16. CPU Scheduling

서울대학교 컴퓨터공학과 김진수 교수님의 "고급 운영체제" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

CPU Scheduling §

• 매 cpu time 은 매우 짧기 때문에, 그 짧은 시간동인 효율적으로 process 를 돌리기 위한 방법이 필요하다.
• Mechanism: 어떻게 전환할까? 등
• Policy: 누구를 선택할거냐?, 언제 전환할까? 등

Preemptive: 내쫒는게 가능하냐 §

• Non-preemptive policy 의 경우에는 cpu 를 스스로 내려놓 (yield syscall) 기 전까지는 계속 이놈이 사용한다.
  • 임베디드에서 이런 policy 를 사용하기도 한다.
  • 이때는 각 task 들이 cooperate 해서 서로서로 잘 양보할 수 있게 한다.
• Preemptive policy 의 경우에는 synchronize 라는 비용을 지불해야 한다.
  • Concurrency 나 deadlock 이 발생하는 요인중에 하나는 이 preemption 이기에, preemption 을 하게 되면 자연스레 synchronize 를 고려하게 된다.
  • 하지만 결국에는 general purpose 로 가면 이들을 모두 cooperate 하는 것이 어렵기 때문에 어쩔 수 없이 대부분의 OS 가 채택한다.
  • 참고로, kernel mode 에서도 preemption 이 가능하다. (아마 interrupt handler)

Work-conserving §

• Work-conserving policy 는 CPU 가 노는 꼬라지를 보지 않게 하는 정책이고, 많은 OS 에서 흔하게 채택한다.
  • 정확하게 말하면 리소스를 누군가 사용하고자 하는데도 해당 리소스를 idle 하게 두진 않겠다는 의미이다.
• Non-work conserving policy 의 경우에는
  • 특정 cpu 가 특정 task 를 전담해서 해당 task 가 없으면 놀게 되는 예시
  • IO scheduler 의 경우에는 좀만 기다리면 인접한 section 에 대한 요청이 올테니까 멀리있는 section 에 대한 요청은 잠시 보류하는 Anticipatory I/O Scheduler 가 있다
  • Multi core 의 경우에는 각 core 에 run queue 가 있고 여기에 process 가 고르게 들어가면 좋겠지만 실제로는 그것이 쉽지 않아 결국에는 일부 core 에 몰릴 수 있게 된다.
    • 즉 이 경우에는 의도치 않게 non work conserving 비스무리하게 돌아가게 되는것

Priority Scheduling §

• Static 은 priority 가 안바뀌는 것, dynamic 은 상황에 따라 바뀌는 것
• Static 하게 우선순위를 줄 수 있지만 이 경우에는 starvation 이 걸릴 수 있기 때문에
  • 즉, 높은 우선순위의 task 가 계속 들오면 낮은 우선순위는 손가락만 빨다가 아사할 수 있게 되는 것.
  • 참고로, static priority 의 경우에 같은 우선순위들에 대해서는 그냥 FIFO 나 RR 등을 사용하게 된다.
• 현대의 대부분 OS 는 (1) Preemptive, (2) Dynamic priority scheduling 을 기본적으로 채택한다.
• 흔히 사용되는 mechanism 은 Multi Level Feedback Queue 이다.
• 대부분의 OS 들은 모두 dynamic 이지만
  • Priority 를 얼마나 올리고
  • Time slice 를 얼마로 잡을것인지 등의 차이가 있다.
• User interactive 한 process (화면 터치 등) 은 priority 가 높게 설정 된다고 한다.
• 그리고 일반적으로는 priority 가 높으면 time slice 도 길다.
  • 경향성이지 무조건 그렇다는 것은 아니다; 이전의 windows 의 경우에는 저 둘을 independent 하게 관리했다고 한다.
• 지금의 linux 에는 Completely Fair Scheduling (CFS) 를 사용한다.
  • ingo 라는 아저씨가 제안 (사실은 뺏어온) 했다고 한다
• Scheduling class: 이것은 Linux 의 workload type 들을 classify 해놓은 것이라 생각하면 된다.
  • 아래 보이는 것처럼 scheduling class 별로 우선순위와 정책이 있다.

CLASS	DESC	POLICY
DL	real-time w/ deadline - 우선순위가 제일 높음	SCHED_DEADLINE
RT	real time	SCHED_FIFO, SCHED_RR
Fair	일반 time sharing process	SCHED_NORMAL, SCHED_BATCH
Idle	우선순위가 제일 낮고, 일반적으로 엄청나게 많은 연산을 필요로 하는	SCHED_IDLE

Linux v2.4: Epoch-based Scheduler §

Terminology §

NICE §

• Base static priority 로 NICE 를 사용
  • Base-static 의 의미는 우선순위 계산에 static 하게 반영되는 값이라는 소리다.
  • 낮은 숫자가 더 좋은거다.
  • Superuser 만 숫자를 낮출 수 있고 일반 유저는 높일수만 있다

Time slice (Tick, Counter) §

• NICE 에 따라서 tick 이라는 식권을 받아 해당 tick 만큼 cpu 를 잡고 쓸 수 있게 된다고 이해하면 된다.
  • Tick 은 시간단위이고, x86 의 경우에는 100Hz = 10ms 이다.
• NICE 에 따라 tick 을 계산하는 공식은 아래와 같더라.
  • 뭐 여기에는 편의상 $/4$ 로 적었는데, 원래는 bitwise operation >> 2 이다.

$$Tick=(20-NICE)/4+1$$

• 위 공식으로 계산해보면
  • default nice 인 0 의 경우에는 6tick 을 받고
  • lowest 인 20 는 1tick 을 받고
  • highest 인 19 는10tick 을 받음

Epoch §

• Epoch 은 권투의 라운드라고 생각하면 된다.
• 우선 epoch 이 시작되면, 각 task 들은 NICE 에 따라 tick 을 분배받고, NICE 우선순위로 해당 tick 만큼 실행된다.
  • Tick 을 모두 소진하면 runnable task 에서 제외되고, 다음 epoch 에 다시 실행된다.
  • IO 같은 이유로 block 되면 마찬가지로 runnable task 에서 제외되고, ready 상태로 바뀔 때 까지 제외된 상태로 있는다.
• 그리고 runnable task 가 더이상 없으면, epoch 이 종료되고 새로운 epoch 이 시작되며 위 과정이 반복된다.
  • 만약 해당 epoch 동안 tick 을 다 못썼으면 다음 epoch 에는 남은 tick 의 절반만 인정해준다.
  • 따라서 tick 을 안쓰고 끝까지 버텨도 (등비수열 극한 계산 해보면) 처음 tick 의 두배는 넘지 못한다고 한다.

Goodness §

• Goodness 는 다음 실행할 task 를 결정하는 계산된 우선순위값인데, 높을수록 우선순위가 높다.
• 대략 다음처럼 계산된다.
  • 0 이면 더이상 실행될 수 없음 (tick 없음)
  • 1000 이상이면 real-time 우선순위임.
  • 그 사이면 일반 time-slice task 들의 우선순위인데
    • $Tick-NICE+20$ (혹은 조건에 따라 21) 정도로 계산된다.
    • 즉, 남아있는 tick 이 높을수록, NICE 는 적을수록 높은 goodness 를 가지게 되는 것.

v2.4 ~ v2.6: O(N) scheduler §

• Linux 2.4 ~ 2.6 까지 쓰이던 scheduler 를 O(N) scheduler 라고 하고 기본 원리는 위와 같지만
• Epoch 시작때 tick 분배도 선형적으로 하고
• Next process 를 정할 때에도 run queue 를 쭉 돌며 goodness 를 계산하고 goodness 가 가장 높은놈을 실행한다
• 하지만 이것은 너무 느리다
  • 이름부터가 O(N) scheduler 이다.
  • 어떤 workload 의 경우에는 전체 시간동안 거의 절반에 가까운 시간을 scheduler 가 먹었다고 한다
• 그리고 이때 tick 을 가지고 있는 task 가 너무 많아서 epoch 이 안끝나는 문제도 있었다고 한다

v2.6 ~ v2.6.23: O(1) scheduler §

• 위의 O(N) 와 기본 원리는 같지만,
  • Epoch 이 시작될때마다 tick 을 주는 것이 아닌 epoch 중간중간 tick 을 나눠주고
  • 우선순위 level (Goodness 랑 똑같은 건지는 모르겠음) 에 따라 run queue 를 둬서 모든 task 를 풀스캔하지 않도록 했다더라
  • 그 외에 비트맵이나 다른 array 를 더 사용해서 O(N) scheduler 를 최적화한 버전.

Linux-latest: Completely Fair Scheduler (CFS) §

• 간단하게 요약해보면
  • Priority 로 weight 를 구한 다음 한 interval 안에서 task 들이 cpu time 을 나눠 가지는 것이 CFS 의 코어이다.
  • 각 task 들은 CPU time 을 얼마나 할당받을 것이냐: 전체 task 들의 weight 총합에서 내 weight 가 차지하는 비중으로 cpu time 을 받음
    • 즉, weight 별로 time 을 나눠가지는 Proportional Share Scheduling 정책
  • Task 들을 어떤 순서로 실행할 것이냐: weight 가 크고 지금까지 실행한 cpu time 이 적은 task 에게 배정

Priority to Weight §

• priority 를 0 ~ 139 (140개) 으로 지정
  • NICE -20 ~ 19 가 100 ~ 139 에 매핑됨
  • 100 아래는 real time 관련된 놈이 사용됨
  • Default 는 NICE 0 (priority 120) 으로 동일하다
• weight 과 priority 는 개념적인 연관은 없다
  • 개념적으로는 weight 은 cpu proportion 이고, priority 는 cpu 를 누가 차지할 것이냐에 대한 수치이기 때문
• 하지만 어쨋든 priority 가 바뀌면 weight 도 바뀌어야 하기 때문에 이것들 연관지어야 하는데 이것이 NICE to weight table 이다
  • 그래서 nice 가 1 증가하면 (우선순위가 낮아지므로) cpu time proportion 이 대략 10% 정도 줄어들게 하기로 하고
    • 10% 라는 수치는 그냥 ingo 아저씨가 임의적으로 정한 것이다
  • 이것을 고려하여 weight 를 계산하는데
  • 결과적으로는 nice 가 1 증가하면 weight 은 25% 가량 줄어들게 하여 table 로 하드코딩되어 있다.
  • 그래서 nice 0 일 때 weight 를 1024 로 잡고 다음처럼 table 이 그냥 constant 로 박혀있다.

Virtual runtime §

• Virtual Runtime (VR) 는 task T 의 환산 실행 시간으로, 실제 실행 시간을 weight 를 이용해 환산한 것이다.
• 이렇게 계산된다:
  • Task T 가 실제로 사용한 시간: Physical runtime of T = $PR(T)$
  • Task T 의 weight: $Weight(T)$
  • NICE 가 0 인놈의 Weight: $Weigh{t}_0$
  • 이때, Virtual Runtime $VR(T)=Weigh{t}_0/Weight(T)\ast PR(T)$
• Virtual runtime 이 작다는 것은 내 weight 에 비해 cpu time 을 적게 받았다는 의미를 가진다.
• 따라서 cpu scheduling 의 우선순위는 높아진다.
  • $PR(T)$ 가 작다는 것은 지금까지 task T 가 cpu time 를 적게 사용했다는 것이기 때문에 cpu 를 scheduling 해주는 것이 합리적이고
    • 즉, 지지부진한 놈에게 cpu 를 주겠다
  • $Weigh{t}_0/Weight(T)$ 가 작다는 것은 NICE 0 인놈의 weight 에 비해 task T 의 weight 가 더 크다는 뜻이기에 마찬가지로 cpu 를 scheduling 해주는 것이 합리적
• 이렇게 생각해 보자
  • Task T 의 weight 가 0 이라면, $VR(T)=PR(T)$ 가 된다.
  • 하지만 weight 가 0 인 놈보다 커지면, $VR(T)$ 은 $PR(T)$ 에 비해 점점 작아지게 되며, 따라서 weight 가 0 인 놈과 실제로는 동일한 시간동안 실행되었음에도 난 더 적게 실행되었다 라고 주장해 cpu 를 더 높은 우선순위로 scheduling 받게 되는 것.
  • 반대로 weight 가 0 인 놈보다 작아지면, $VR(T)$ 은 $PR(T)$ 에 비해 점점 커지게 되며, 따라서 weight 가 0 인 놈과 실제로는 동일한 시간동안 실행되었음에도 난 더 많이 실행되었다고 분류되어 cpu 를 너 낮은 우선순위로 scheduling 받게 된다.

Runqueue §

• CFS 에서 runqueue 는 red-black binary tree 로 구현되고 가장 왼쪽에 있는 놈이 가장 VR 이 작으니까 얘한테 CPU 를 scheduling 해주게 된다.
  • Red-black binary tree 는 간단히 말해 그냥 binary tree 와 유사한데,
  • Root 에서 longest path leaf 까지의 길이가 shortest path leaf 까지의 길이의 2배를 넘기지 않도록 self-balancing 되는 binary tree 라고 한다.
  • 당연히 tree 니까 $O(logN)$ 으로 작동함

Timeslice §

• Weight 의 비율에 따라 task 가 가져가는 cpu time 을 Timeslice ($TS(T)$) 라고 한다.
  • 즉, Timeslice 는 task 가 preempt 되기 전까지 실행할 수 있는 최대 시간인 것.
  • kubernetes 에서 cpu resource notation 이 여기서 가져온거다
  • 즉, 전체 weight 총합에서 내가 차지하는 weight 의 비율에 따라 cpu time 이 정해지는 것
    • 그래서 뭐 알다시피 weight 가 같아도 전체 weight 총합이 다르면 내가 가져가는 cpu time 은 달라질 수 있다.
• 이렇게 계산된다:

$$TS(T)=\frac{Weight(T)}{\sum Weight}\ast P$$

• 다만 주의할 것은 저 $\sum Weight$ 는 runqueue 에 있는 task 들 대상이라는 것이다.
  • 만일 어떤 task 가 block 되면, 이놈은 runqueue 에서 빠지고 이 $TS(T)$ 계산에서도 빠진다.
  • Runqueue 의 task 들이 바뀌지 않으면, 매 $P$ 마다 새로운 interval 이 시작되지만
  • Task 가 block 되는 등에 의해 runqueue task 가 바뀌면 새로 interval 이 시작된다고 생각해도 된다.
  • 이게 뭔말인지는 뒤에 CFS Example 보면 좀 감이 올거다.
• 이 Scheduling Period $P$ 는 task 들이 나눠먹을 전체 cpu time interval 를 의미한다.
  • 피자 한판이 $P$,
  • 누가 몇조각 먹을지는 $TS(T)$,
  • 누가 먼저 먹기 시작할지는 virtual runtime
• 그럼 이 $P$ 를 몇으로 잡아야 되냐
• 6ms 면 8 task 기준 각각 최소 0.75 ms 는 줄 수 있다고 한다.
  • 최소한 0.75 는 제공해 주는 입장
  • 기존의 O(N) 이나 O(1) 에 비해 cpu time 비율을 반드시 지켜주겠다는 것이 CFS 의 차이점
• 만약 task 가 더 많아지면 그에 따라 $P$ 를 더 늘림

CFS Example §

#SNU_CSE_MS_AOS24S_EXAM CFS 작동과정 ppt 39p. 보면서 연습하기

Scenario w/o blocking §

• 첫 $P$ interval 이 끝난 직후에 다음과 같았다면, 다음 $P$ interval 에서는 어떻게 될지 생각해 보자.

• 우선 T1 을 실행할거다.
  • 실행될 시간 $TS(T1)=1024/(1024+3121+335)\ast 6=1.37$
  • 실행 이후 $VR(T1)=(1024/1024)\ast (1.37\ast 2)=2.74$
• 그리고 다음으로 $VR$ 이 낮은 T2 가 실행된다.
  • 실행될 시간 $TS(T2)=3121/(1024+3121+335)\ast 6=4.18$
  • 실행 이후 $VR(T2)=(1024/3121)\ast (4.18\ast 2)=2.74$
• 마지막으로 T3 이 실행된다.
  • 실행될 시간 $TS(T3)=335/(1024+3121+335)\ast 6=0.45$
  • 실행 이후 $VR(T3)=(1024/335)\ast (0.45\ast 2)=2.75$
• 결과적으로:
  • 참고로 그림에서 $VR(T3)$ 이 2.76 인 것은 오타이다.

Scenario w/ blocking §

• 위 예시 상황 그대로에서, 다음에는 T2 가 scheduling 될텐데, 여기서 T2 가 1ms 만 실행되고 block 되었다고 생각해 보자:
  • 그럼 $VR(T2)=1024/3121\ast (4.18\ast 2+1)=3.07$ 가 된다.

• 그리고, 이후의 상황에 대해 생각해 보자.
• 우선 Runqueue 의 left-most 인 T1 가 실행된다:
  • 실행될 시간 $TS(T1)=1024/(1024+335)\ast 6=4.52$
  • 실행 이후 $VR(T1)=(1024/1024)\ast (1.37\ast 2+4.52)=7.26$
• 그리고 T3 이 실행된다:
  • 실행될 시간 $TS(T3)=335/(1024+335)\ast 6=1.48$
  • 실행 이후 $VR(T3)=(1024/335)\ast (0.45\ast 2+1.48)=7.27$
• 결과적으로 아래 그림처럼 된다:
  • 참고로 그림에서 $VR(T3)$ 이 7.28 인 것 또한 오타이다.

Some heuristics… §

• weight 대로 기계적으로 하면 좋겠지만 실제로는 많은 휴리스틱이 들어간다
  • 즉, 상황에 따라서 여러가지 예외 케이스들이 진자루 많이 들어간다
  • 예를 들어 block 에서 깨어난 놈은 RB tree 의 제일 왼쪽의 nice 에서 조금 더 뺴주는 등

여기부터는 2024-05-09 강의

Tickless kernel §

• CONFIG_NO_HZ_IDLE: 시스템이 idle 한 경우에는 timer interrupt 를 disable 시키는 기능
  • 현재에는 이것이 default 이다 - 기본적으로는 idle 한 경우에 timer interrupt 를 받지 않는다.
  • 대신 어느정도의 긴 시간 간격을 설정해 알람을 맞춰 이때 깨워달라 라고 설정할 수도 있고
  • 모든 core 에 대해서 전부 끄지는 않는다고 한다.