[xv6] Scheduling

글의 참고

-

---

글의 전제

- 밑줄로 작성된 글은 강조 표시를 의미한다.

- 그림 출처는 항시 그림 아래에 표시했다.

---

글의 내용

- 타이머 스케줄링

: `xv6`에서 타이머가 호출되면, 직접적으로 프로세스 스케줄링을 하는 것이 아니라, 프로세스들중에서 `SLEEPING`인 프로세스를 `RUNNABE`로 바꾸기만 한다. 실제 스케줄링을 하는 프로시저인 `sched` 프로시저를 호출하지는 않는다. `xv6`에서는 모든 인터럽트 및 트랩은 `trap` 함수에서 관리한다. `trap`에서는 제일 먼저 시스템 콜인지 체크한다. 그리고, 아니라면 인터럽트 및 익셉션인지를 확인한다. 타이머 인터럽트라면, `wakeup` 함수를 호출한다. 

// trap.c uint ticks; ... ... //PAGEBREAK: 41 void trap(struct trapframe *tf) {   if(tf->trapno == T_SYSCALL){     if(myproc()->killed)       exit();     myproc()->tf = tf;     syscall();     if(myproc()->killed)       exit();     return;   }   switch(tf->trapno){   case T_IRQ0 + IRQ_TIMER:     if(cpuid() == 0){       acquire(&tickslock);       ticks++;       wakeup(&ticks);       release(&tickslock);     }     lapiceoi();     break;   case T_IRQ0 + IRQ_IDE:     ideintr(); ... ... }

 

: 아래 코드를 보면, 알 수 있다시피 `xv6`에서는 타이머가 호출될 때마다 `SLEEPING`인 프로세스를 찾아서 깨운다. 그리고 그것만조건에 있는 것은 아니다. 각 프로세스에는 `chan` 이라고 값이 존재하는데, 이 값은 `lock`이 걸린 프로세스를 식별하는데 사용한다. 즉, 나중에 `lock`에서 깨어나기 위해 각 프로세스를 식별하는 값이 된다. 즉, `pid`는 각 프로세스를 선별하는 값이라면, `chan`은 `lock`이 걸린 각 프로세스를 식별하는데 사용한다.  그런데, `lock`에도 여러 가지 종류가 존재한다. `wakeup` 함수를 통해 깨어나는 프로세스는 `sleep` 함수를 통해 `lock`에 걸린 프로세스들만 깨운다.

// proc.c ... ... //PAGEBREAK! // Wake up all processes sleeping on chan. // The ptable lock must be held. static void wakeup1(void *chan) {   struct proc *p;   for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)     if(p->state == SLEEPING && p->chan == chan)       p->state = RUNNABLE; } // Wake up all processes sleeping on chan. void wakeup(void *chan) {   acquire(&ptable.lock);   wakeup1(chan);   release(&ptable.lock); } ... ...

: 타이머 인터럽트를 통해서 `wakeup` 되는 프로세스들은 `chan` 변수에 `tick` 변수의 주소가 들어간 프로세스들이 된다. 그런데, 왜 `p->state == SLEEPING && p->chan == chan` 조건에 걸리는 모든 프로세스들을 깨우는 것일까? 즉, 하나의 프로세스만 `RUNNABLE` 상태로 바꾸고 끝나는게 아니라, 프로세스 테이블을 전부 돌면서 위의 조건들이 맞는 모든 프로세스들을 `RUNNABLE`하고 있다.

 

: 그 이유는 `sleep` 함수의 구조 때문이다. 예를 들어, 프로세스 A, B가 있다. 프로세스 A는 시스템 콜 `sys_sleep`을 호출하면서  `sleep(10, &ticklock)`을 호출했다. 그리고 4ms 뒤에 프로세스 B는 시스템 콜 `sys_sleep`을 호출하면서 `sleep(6, &ticklock)`이 호출했다고 치자. 그리고 타이머 인터럽트느 2ms 간격으로 호출된다고 치자. 시간 간격상 프로세스 A와 프로세스 B는 동시에 wakeup 해야 한다.

 

1" 프로세스 A 웨이크 업 타임 = 10ms
2" 프로세스 B 웨이크 업 타임 = 4ms + 6ms = 10ms

 

: 만약 8ms에서 타이머 인터럽트가 호출됬다고 치자. 그러면 아래에서 자세히 보겠지만, `sys_sleep`에서 `ticks - ticks0 < n`을 지키지 못하게 된다. 아래와 같이 말이다. 그래서 루프문을 다시 돌면서, 프로세스가 깨어나더라도 다시 `sleep` 함수를 호출하게 된다.

 

1" 프로세스 A : 8 - 0 < 10
2" 프로세스 B : 4 - 0 < 6

 

: 10ms가 되면, 타이머 인터럽트가 발생하고 `wakeup`이 호출될 것이다. 이 때는, 프로세스 A, B 모두 웨이크 업 조건을 만족하게 된다. 이 때, 만약 `wakeup1`에서 프로세스 A 만 깨우고 루프문을 빠져 나오면 어떻게 될까? 프로세스 B는 다음 타이머 인터럽트에서 깨어나게 될 것이다. 이렇게 동일한 시점에 깨어나야 하는 문제때문에 프로세스 테이블 전체를 검색해야 하는 것이다.

 

: 그런데, 프로세스의 `chan` 변수에 &tick 들어가는 경우는 어느 경우일까? `sleep` 함수가 호출되는 케이스는 상당히 많지만, `&ticks`가 들어가는 경우는 `xv6` 에서 딱 하나밖에 없다.

 

: `sys_sleep` 시스템 콜 함수를 호출할 때 뿐이다. 실제 이 함수가 전형적인 `sleep` 함수의 형태를 띄고 있다. 이게 무슨말이냐면, 원래라면 `sleep` 함수는 시간을 계산하는 코드가 있어야 하는데, `xv6`에서 `sleep` 함수는 프로세스 관리용으로 사용되는 함수다. 그리고 실제 시간 계산은 `sys_sleep` 함수에서 하고 있다. `ticks0 = ticks` 는 이 `sys_sleep`이 호출된 시점에 시간을 저장하는 것을 의미한다. 그리고, `ticks - ticks0`은 `sys_sleep` 이 호출된 시점으로부터 얼마나 흘렀는지를 나타낸다. `n`은 `sys_sleep` 시스템 콜 호출 시, 전달된 인자를 의미한다. 

// defs.h extern uint     ticks; ... ... #################################################################################################### // sysproc.c ... ... int sys_sleep(void) {   int n;   uint ticks0;   if(argint(0, &n) < 0)     return -1;   acquire(&tickslock);   ticks0 = ticks;                       while(ticks - ticks0 < n){          if(myproc()->killed){       release(&tickslock);       return -1;     }     sleep(&ticks, &tickslock);   }   release(&tickslock);   return 0; } ... ...

 

: `sleep` 함수는 동기화 코드때문에 복잡해 보이지만, 실상은 단순하다. 현재 `sleep` 이 호출된 프로세스는 다른 프로세스에게 프로세서를 양도한다. 그러면, `sleep` 함수에 10을 전달하면 딱 10ms 자고 깨어날까? 절대 그렇지 않다. 프로세스가 거의 정확히 10ms를 자고 일어나려면, 해당 프로세스가 10ms 까지 계속 프로세서를 독점하면서 루프문에서 정확히 10ms 동안 갇혀있어야 한다. 그런데, `xv6` 에서 `sleep`은 그런 구조가 아니다. 특정 프로세스가 `sleep` 함수를 호출하면 프로세서를 다른 프로세스에게 양보하는 구조이기 때문에, 다시 `RUNNABLE`이 되려면, 타이머 인터럽트에 의해서만 가능하다. 그런데, `RUNNABLE`이 됬다고 해서 언제 다시 스케줄링 될지를 알 수가 없기 때문에 정확한 시간은 보장되지 않는다.

// proc.c ... ... // Atomically release lock and sleep on chan. // Reacquires lock when awakened. void sleep(void *chan, struct spinlock *lk) {   struct proc *p = myproc();      if(p == 0)     panic("sleep");   if(lk == 0)     panic("sleep without lk");   // Must acquire ptable.lock in order to   // change p->state and then call sched.   // Once we hold ptable.lock, we can be   // guaranteed that we won't miss any wakeup   // (wakeup runs with ptable.lock locked),   // so it's okay to release lk.   if(lk != &ptable.lock){  //DOC: sleeplock0     acquire(&ptable.lock);  //DOC: sleeplock1     release(lk);   }   // Go to sleep.   p->chan = chan;   p->state = SLEEPING;   sched();   // Tidy up.   p->chan = 0;   // Reacquire original lock.   if(lk != &ptable.lock){  //DOC: sleeplock2     release(&ptable.lock);     acquire(lk);   } } ... ...

: `sleep` 함수를 통해 `SLEEPING`이 된 프로세스들이 `RUNNABLE`이 되어 다시 스케줄링 되었을 때, 깨어나는 지점은  `p->chan = 0` 지점이다.