운영체제 #7 — xv6에 MLFQ 스케줄러 얹기

첫 번째 프로젝트는 xv6의 스케줄러를 MLFQ로 바꾸는 것이었다. 이론 #4에서 본 그 MLFQ다.

기존 xv6 스케줄러 읽기

바꾸기 전에 원래 있던 걸 읽어야 한다. xv6는 Round Robin을 쓴다. 각 프로세스가 time quantum을 넘기면 ready queue의 마지막으로 가고, quantum이 지나지 않았어도 I/O가 발생하면 waiting queue로 가고 다음 프로세스를 스케줄링한다.

구현은 이렇게 되어 있다.

• ptable이라는 job queue가 있다. 동시에 최대 64개(NPROC)의 프로세스를 담는다. 안에는 lock과 프로세스를 담는 proc[NPROC]이 있다.
• 프로세스를 할당할 때는 ptable에서 UNUSED 상태의 슬롯을 찾아 EMBRYO(수업에서 배운 NEW와 같다)로 바꾼다. 그 후 fork()나 userinit() 시 RUNNABLE(READY)로 바꾼다.
• timer interrupt가 발생하거나 상태가 바뀌면 다음 프로세스에게 넘긴다.

넘기는 경로는 이렇다.

• yield() — 현재 실행 중인 프로세스를 RUNNABLE로 바꾸고 sched()를 호출한다.
• sched() — 오류가 없는지 여러 확인을 하고 scheduler()로 context switching한다.
• scheduler() — ptable에서 RUNNABLE인 프로세스를 찾아 context switching한다. 무한 루프를 돌면서 return하지 않는다.

xv6는 ticks를 time quantum으로 쓰고, ptable을 계속 돌면서 index 순으로 RUNNABLE을 찾는다. 그래서 Round Robin이라고 볼 수 있다. (다만 자기보다 먼저 생성된 프로세스가 죽어서 UNUSED가 되면 순서가 완전히 보장되지는 않을 것 같다.)

프로세스 상태는 이렇게 정의되어 있다. UNUSED(프로세스가 없다), EMBRYO(new), SLEEPING(스케줄링 대상이 아니다, waiting 같은 상태), RUNNABLE(ready), RUNNING, ZOMBIE.

기존 xv6의 struct proc. 여기에 필드를 붙여 나간다.

cprintf를 넣어 확인해보니 흐름이 보였다. userinit 하고 시작하면 RUNNABLE이 하나 만들어져 있고, mpmain()에서 cpu %d: starting 출력 후 scheduler가 처음 시작한다. 그러다 $ 프롬프트가 나오는 순간(shell이 입력을 받는 순간)부터 scheduler가 무한 반복한다. 아직 실행할 프로세스가 없으니 RUNNABLE이 없어서 도는 것이고, 정상적인 상황이다.

부팅 직후 스케줄러의 흐름. 프롬프트가 뜬 뒤로는 계속 빈 루프를 돈다.

만들 MLFQ

L0, L1, L2 세 개의 큐를 만든다.

• 큐의 우선순위는 숫자가 작을수록 높다. 모든 프로세스는 맨 처음 L0에 들어간다.
• 각 큐 Ln의 time quantum은 2n + 4 ticks다. 프로세스마다 각 큐에 있을 수 있는 시간을 의미한다.
• L0, L1은 Round Robin, L2는 Priority 스케줄링을 따른다.
  • L2는 priority가 낮은(숫자가 작아 우선순위가 높은) 프로세스를 먼저 실행한다.
  • priority가 같으면 FCFS로 고른다.

예를 들어 A, B, C, D가 순서대로 들어오면 모두 L0에 들어가서 1 tick(timer interrupt 간격, xv6 기본 약 10ms)마다 스케줄링한다. A, B, C, D, A, B, C, D, A, B, C, D, A(L1으로), B(L1으로), C(L1으로), D(L1으로) 이런 식이다.

구현

proc 구조체에 필드 추가

• priority — L2에서 우선순위 비교에 쓴다.
• time — 그 프로세스의 time quantum(누적 사용 tick).
• level — 프로세스가 위치한 큐의 레벨. schedulerLock 상태를 표시하기 위해 lock이 걸리면 -1을 갖는다.
• enterL2 — L2에 들어간 순서를 표시한다. priority가 같을 때 FCFS를 위해 필요하다.

proc 구조체에 추가한 필드들.

시스템 콜

• yield() — timer interrupt 시 호출된다. time을 1 증가시키고 각 큐의 time quantum을 지났는지 확인한다. 지났다면 큐를 이동하거나(L0, L1) priority를 바꾼다(L2). L2로 이동하는 경우 FCFS를 위해 enterL2를 초기화한다. 순서를 표시하는 global 변수를 하나 두고 그 값을 넣는다.
• getLevel() — 프로세스가 속한 큐의 레벨을 반환한다.
• setPriority(int pid, int priority) — 해당 pid의 priority를 설정한다.
• schedulerLock(int password) — 해당 프로세스가 우선적으로 스케줄링되도록 한다. password가 맞으면 priority boosting 없이 global tick만 0으로 초기화한다. 틀리면 pid와 time quantum, 큐 레벨을 출력한다.
• schedulerUnlock(int password) — 우선 스케줄링을 중지한다. schedulerLock을 호출했던 프로세스만 호출할 수 있다. lock을 건 본인만이 lock을 풀 수 있다는 것이다. password가 맞으면 level, time quantum, priority를 초기값으로 되돌리고, 틀리면 마찬가지로 프로세스 정보를 출력한다.

yield() — time quantum을 넘었는지 확인하고 큐를 옮긴다.

schedulerLock().

schedulerUnlock() — lock을 건 본인만 풀 수 있다.

인터럽트로 lock 걸기

schedulerLock과 schedulerUnlock은 각각 interrupt 129, 130을 통해서도 호출할 수 있게 했다. tvinit 안에 게이트를 추가해서 user mode에서도 호출 가능하도록 DPL을 열어주고, trap 함수 안에 해당 case를 추가했다.

tvinit에 인터럽트 129, 130 게이트를 추가한다.

trap()에 추가한 case.

#6에서 "비어 있는 IDT 엔트리에 새로운 interrupt를 만들 수 있다"고 적어놨는데, 그게 여기서 쓰인다. 시스템 콜을 새로 파는 것과 IDT에 게이트를 하나 더 여는 것이 사실상 같은 일이라는 게 이때 손에 잡혔다.

allocproc

UNUSED 상태의 프로세스를 EMBRYO로 바꿔주고 추가한 변수들을 초기화한다. priority는 setPriority를 이용해 초기화했다. 이건 userinit()과 fork()에서 쓰인다.

scheduler

핵심은 여기다.

• for(;;)로 무한 루프를 돌아 return하지 않는다.
• 안에서 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)를 돌아 Round Robin을 구현한다.
• 새로운 running 대상을 찾을 때마다 targetLevel()로 target이 될 레벨을 찾는다. RUNNABLE인 프로세스 중 최소 큐 레벨을 찾는 함수다.

scheduler() — ptable을 돌며 다음 실행 대상을 찾는다.

targetLevel() — RUNNABLE인 프로세스 중 최소 큐 레벨.

레벨에 따라 분기한다.

• target level이 -1일 때 — schedulerLock을 건 프로세스가 있고 RUNNABLE이라는 뜻이다. ptable에서 그 프로세스를 찾는다. 여기서 p--을 해서 다시 대상인지 확인하게 하면 lock이 풀리기 전까지 계속 실행 대상이 된다. 그리고 lock이 풀렸다 해도 p--을 해두면 priority boosting이 일어나거나 unlock되었을 때 가장 먼저 실행되므로, L0의 가장 앞으로 들어가서 실행되는 효과가 생긴다.
• target level이 0 또는 1일 때 — 해당 큐에 있는 프로세스 중에서 탐색한다. timer interrupt나 실행 중인 프로세스의 terminate 시 순서대로 다음 대상을 찾으므로 Round Robin이 된다.
• target level이 2일 때 — priority 기준이라 다르다. targetID()로 대상 pid를 구해 p->pid == targetID()인지 확인한다. targetID()는 먼저 최소 priority를 찾고, 그중 가장 먼저 들어온 프로세스를 찾아 그 pid를 반환한다.

targetID() — 최소 priority를 찾고, 동률이면 먼저 들어온 순.

priority boosting

global tick이 100이 되면 allReset으로 priority boosting을 한다. allocproc에서 초기화했던 값으로 되돌린다.

allReset() — global tick 100에서의 priority boosting.

결과

fork로 프로세스를 여러 개 만들어 확인했다.

timer interrupt마다 RUNNABLE 프로세스들이 돌아가면서 실행된다. pid 3의 level이 1이면 L0에 있는 프로세스들부터 실행되고, L2에서는 priority가 낮은(우선순위가 높은) 프로세스만 실행된다.

timer interrupt마다 RUNNABLE 프로세스가 번갈아 실행된다.

global tick이 100이 되면 priority boosting이 일어나 값들이 초기화된다.

priority boosting으로 level과 time이 초기값으로 돌아간 모습.

schedulerLock을 걸면 lock한 프로세스만 실행되고 다른 프로세스는 실행되지 않는다.

schedulerLock 테스트 — lock을 건 프로세스만 실행된다.

다만 lock한 프로세스가 sleep하면 다른 RUNNABLE 프로세스가 실행된다. level -1인 pid 3이 sleeping일 때 level 1인 pid 4가 실행되는 걸 확인했다.

level -1인 프로세스가 sleep한 사이 level 1인 프로세스가 실행된다.

schedulerUnlock 후에는 level이 0으로, time도 0으로 돌아가고 자식 프로세스도 다시 실행된다.

i = 50 부근에서 unlock되어 level과 time이 초기화된다.

int 129, int 130으로 호출했을 때도 cprintf가 찍히는 걸 확인했다.

Trouble Shooting

time quantum을 잘못 이해하고 있었다

가장 오래 붙잡은 게 이거다. time quantum은 한 프로세스가 한 번에 실행하는 최대 시간이다. 그런데 timer interrupt가 있으면 얘기가 달라진다.

명세의 "time quantum이 4, 6, 8 ticks"는 4, 6, 8 × 10ms라는 뜻이다. 그런데 그 시간 동안 timer interrupt가 계속 일어나므로, 그때마다 각 큐의 기법으로 다음 프로세스를 결정한다. timer interrupt가 없다면 8ms 안에 안 끝나는 경우 다음 큐로 이동하는 것이지만, timer interrupt가 있다면 그때마다 다음 프로세스로 CPU를 넘기고 time quantum이 지나지 않았다면 넘겨준 프로세스도 남아 있는다. 그러다 큐에 머문 시간이 time quantum이 되면 다음 큐로 넘어간다.

time quantum과 timer interrupt의 관계. 큐에 머문 시간이 quantum에 닿아야 아래로 내려간다.

timer interrupt 때 sleeping이 runnable로 바뀐다

timer interrupt를 지나면 sleep 상태였던 프로세스가 runnable로 바뀌는 걸 발견했다. sleep 시 tick을 chan으로 설정하고, timer interrupt 시 tick을 chan으로 설정한 모든 프로세스를 깨우기 때문이었다. sleep하는 것 또한 프로세스가 실행되어야 카운트 되므로 자연스러운 것으로 봐도 될 듯하다.

다만 sleeping으로 바꿔주려는 와중에 timer interrupt가 발생해서 time이 증가해 버리는 경우가 있다. level이 -1인 경우는 time을 안 쓰니 상관없지만, 나머지 레벨에서는 신경 써야 한다.

myproc()이 null일 때가 있다

case T_IRQ0 + IRQ_TIMER에서 myproc()을 호출했더니 panic이 났다. 시작할 때, 그리고 RUNNABLE인 프로세스가 없을 때 myproc()의 리턴값이 0(null)이 되는데, 이때 myproc()->을 하면 없는 프로세스에 접근하니 문제가 생긴다. if (myproc() != 0) 조건을 달아서 해결했다.

이게 프로젝트 전체에서 가장 값비싼 버그였다. 원래는 Queue 구조체를 따로 만들어 진행하고 있었는데, 중간중간 확인하지 않고 쭉 짜다가 어느 순간 커널 패닉이 났고 원인을 못 찾아서 결국 위 방식으로 다시 구현했다. 나중에야 그 원인이 trap.c의 timer interrupt 부분에서 myproc을 호출해서 일어난 것이라는 걸 알게 됐다. 큐를 따로 만드는 방식은 나중에 다시 해볼 생각이다.

cprintf 위치 때문에 panic

sleep 상태인지 확인하려고 cprintf를 struct proc 밑에 넣었더니 panic: acquire가 떴다. lock 관련 문제인가 싶어 위치를 옮기니 해결됐다.

추가로 알게 된 것

• 유저 모드에서 시스템 콜을 호출하면 등록되어 있는 wrapper function을 호출해 모드 전환 후 우리가 원하는 함수를 호출하는 것이다. 커널 모드에서 호출할 때는 wrapper를 거치지 않고 바로 호출한다.
• sleep()을 호출하면 yield를 거치지 않고 바로 sched()를 호출한다. 즉 timer interrupt가 일어나기 전까지 기다리지 않고 다음에 running할 프로세스를 찾는다.