xv6 MLFQ Scheduling Wiki (4. 부록)
proc.c 파일 함수들에서 볼 수 있는 process state의 transition 과정을 아래에서 살펴보고 분석해봅시다.
enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };| Function | Main State Transition | Time Complexity | Exception |
|---|---|---|---|
| allocproc | UNUSED -> EMBRYO | O(NPROC) | UNUSED → UNUSED |
| userinit | EMBRYO → RUNNABLE | O(1) | None |
| fork | EMBRYO → RUNNABLE | O(1) | EMBRYO → UNUSED |
| exit | RUNNING -> ZOMBIE | O(N) | None |
| wait | child 있는 경우: child ZOMBIE -> UNUSED | ||
| child가 ZOMBIE인 경우 : | |||
| parent RUNNING -> SLEEPING | O(N) | None | |
| wakeup1 | SLEEPING -> RUNNABLE | O(NPROC) | None |
| scheduler | RUNNABLE -> RUNNING | O(N) | None |
| yield | RUNNING -> RUNNABLE | O(1) | None |
| sleep | RUNNING → SLEEPING | O(1) | None |
| kill | SLEEPING -> RUNNABLE | O(N) | None |
state transition with image
기존의 scheduling은 timer interrupt에 따라 1ticks마다 Running 프로세스를 선택하는 Round Robin 방식을 채택하였습니다.
현재 RUNNING상태의 프로세스 다음 인덱스부터 시작하여 ptable을 반복적으로 순회하며 RUNNABLE 상태의 프로세스를 찾고 RUNNING 상태의 프로세스로 바꿔줍니다.