CPU Scheduling
- A policy deciding which proces to run next, given a set of runnable processes
Mechanism VS Poicy
How to trnasition vs When to transition or To whom?
Basic Approches
Non-preemptive scheduling
스케쥴러가 기다려줌 강제로 종료하기 보다는 자원적으로 CPU를 이제 내놓도록
따라서 프로세스들이 협력적이어야함
스케쥴러가 간단해짐 + timer interrupt()가 필요 X
Preemptive scheduling
스케쥴러가 process interrupt 가능
대신 중요한 순간에는 내쫓으면 안됨!!
다양한 방식들
FIFO
먼저 오면 먼저 실행
문제는 굉~~장히 긴 job이 하나 들어오면 다들 걔를 기다려야한다는 점
SJF
가장 짧은 run time 가진 job 고르기
starve 가능성 있음
STCF(Shortest Time-to- Completion First)
preemtive version of SJF라고 생각하면 됨
일단 실행하고 있다가 더 짧은 runtime job 들어오면 내쫓고 걔 실행하기
RR(Round Robin)
각각의 job에 일종의 tiem slice를 주는 것임
reposne time 개선 ! 귯~
(Static) Priority Scheduling
각각의 job이 고정된 우선 순위를 갖는 것
같은 우선순위를 가질 경우, 보통 RR혹은 FIFO
Incorporating I/O
I/O를 들어간 경우 다른 job 바꿔서 실행
MLFQ(Multi-Level Feedback Queue)
Priority마다 queue header가 있고 거기에 각각 runable process를 que에 집어 넣음 !
일반적으로 쓰이는 것 Dynamic Preemtive priority scheduling !
스케쥴러가 process의 priority를 계속 바꾼다.
Priority
CPU를 오래 쓰면 순위 낮아지고
I/O 같이 interactive한 경우는 순위가 높아야 함
Rule
-
if A > B, A 실행
-
if A == B, RR
-
첫번째로 job이 system에 들어오면 가장 높은 우선 순위
4a. 만약 job이 time slice를 전부 다 쓰게된다면 우선순위가 아래로 한단계 떨어짐 (one queue 내려가는 것임)
4b. 만약 time slice 전에 CPU 돌려주면 우선순위 유지그런데 이때 악의적인 사용자가 일부러 time slice보다 작게 job을 계속 넣어버릴 수도 있고, starve 문제가 있을 수도 있으며 program 자체가 시간이 지남에 따라 행동이 바뀌는 경우도 있음 따라서
5.일정 기간이 지나면 모든 job을 다시 가장 높은 우선순위로 올려준다.
또한 짧은 프로세스 여러개로 구성된 job들이 불리하기 때문에
4를 단순히 CPU 사용 횟수보다는 total CPU 사용 시간으로
Linux CFS(Completely Fair Scheduler)
Linux Task Priority
총 (0~139) 140의 level이 있고 작은 숫자일수록 높은 priority
-20 <= nice value <= 19
이 사이의 nice 값이 non-real-time task의 priority
Default는 0
CPU는 각 task에게 weight에 따라 할당된다
Nice to Weight
따라서 nice -> weight로의 변환이 필요함
얘의 기본 원리는 nice value가 1오를 때 10% 적게 CPU time을 갖게 하는 것
Virtual Runtime
실제 physical time이 동일할 때, 즉 만약 모든 task가 3초를 할당 받았다고 생각해보면.
우선순위가 높은 task에게 3초는 턱없이 부족하고, 우선순위가 낮은 task l에게는 3초가 과분하게 길다. 이런 느낌으로 weight가 크면, 즉 priority가 높은 경우 동일한 physical time에서 Virtual Runtime이 더 작다고 생각하면 된다.
따라서 Weight에 반비례하도록 VR(T)를 변환해서 구하고, 가장 작은 VR(T)부터 실행하도록 하면된다.
Runqueue
vruntime을 기준으로 정렬된 red-black tree
이중에서 vruntime 가장 ㅏㅈㄱ은 runnable task를 골라서 실행한다.
Challenges
당연히 !! 아직 남은 문제들이 많음
만약 I/O하느라 시간을 결국 많이 쓰는데도 CPU 쓰는 시간이 적어서 VR(T)가 작은 task
갑자기 새로운 process가 등장해서 VR(T)가 0으로 시작해서 계속 낮은 VR을 유지해서 CPU를 할당 받는 경우
등등의 문제들이 있다
