CPU scheduling
-> Linux CFS (Completely Fair Scheduling) scheduler
Basic concept
기본적으로 CPU time = total CPU time * (weight of task / total weight)
Nice to weight
weight값은 pre-defined array로 하드코딩 돼있어야함
Time slice
task의 실행되어야 하는 최소 시간
task의 weight에 따라 할당됨
time_slice = 10ticks * (weight of task / total weight)
vruntime (virtual runtime)
process가 weight에 비례해 실행된 시간을 나타냄
vruntime = (actual runtime) * (weight of nice 20 / weight of task)
CFS Scheduling
1. 가장 작은 vruntime을 가진 task가 scheduled 됨
2. scheduled 된 task는 {weight / total weight}의 비율에 맞추어 time slice를 얻음
3. task가 running되는 동안, vruntime이 updated 됨
4. task가 time slice보다 더 run 될 경우 1.로 돌아가야함
Implement CFS on xv6
-
runnable processes 중에서 가장 작은 vruntime을 갖는 process를 선택
-
각 timer interrupt시에 runtime / vrumtime을 update 해줘야함
-
task가 time slice 이상으로 run 되면 yield 해야함
-
default nice 값은 20이고, 범위는 0 ~ 39까지임 그리고 nice 20의 weight 값은 1024
-
time slice = 10tick * (weight of current process / total weight of runnable processes)
-
vruntime += runtime * (1024 / weight of current process)
-
- 새로 forked 된 process는 parent process의 vruntime을 상속받음
-
- woken up process의 vruntime (1tick) = 1tick * (weight of nice 20 / weight of current process)
-
- -> process wake up 하는 동안 sched() 호출되면 안됨
-
- -> woken up process는 최소의 vruntime을 갖는데, 그 때 돌아가고 있는 current process의 time slice가 만료될 때까지 schedule 되면 안됨 -> This is by default in xv6
testcfs.c
- millitick unit (multiply the tick by 1000) 사용해야함/ runtime, vruntime, total tick에 float, double 사용하면 안됨
- ps()에서 indent 맞춰서 출력해야함
vruntime의 integer overflow도 고려해야함 (runtime, total tick은 고려안해도됨)
trap.c yield() 호출 부분 변경
proc.h 파일 proc 구조체에 위와 같이 변수 추가
proc.c 파일에서 스케쥴러 구현함 (최대한 구현 해봤는데 결과는 모르겠다)
추가적으로 uint overflow는 string으로 처리 해보려했는데 리눅스에선 C 헤더파일이 계속 충돌나서 atoi(), itoa(), strcat()이런 거 다 직접 구현해야한다는 사실에 슬펐는데 어찌됐건 최대한 vruntime_overflow()함수 짜보려했으나 생각과 달리 잘 안됐다 내가 졌다 completely fucking schedular..
