# XV6 A simple, Unix-like Teaching Operating System Chapter 5

---

> [TOC]

---

## Chapter 5 Scheduling
- 在 OS 製造一個 Process 獨占處理器的假象，並利用 OS 的 multiplexing 機制模擬一個 Processor 變成多個虛擬 Processors。
- 將說明 xv6 是如何為多個 Process 模擬出多處理器的。

---

### Multiplexing (多路復用機制)
- 實現方法
- 當一個進程等待磁盤請求時，xv6 使之進入睡眠狀態，然後調度執行另一個進程。另外，當一個進程耗盡了它在處理器上運行的時間片（100毫秒）後，xv6 使用時鐘中斷強制它停止運行，這樣調度器才能調度運行其他進程。這樣的多路復用機制為進程提供了獨占處理器的假象，類似於xv6使用 (內存分配器) 和 (頁表硬件) 為進程提供了獨占內存的假象。

---

### Code: Context switching

- By Chap 2
- 每個 xv6 Process 都有自己的 Kernel Stack 以及 Reg。
- 每個 CPU 都有一個單獨的 Scheduler Thread，這樣 Scheduling 就不會發生在 Process 的 Kernel Thread 中，而是在 Scheduler Thread 中。
- 其中 %esp 和 %eip 的變換意味著 CPU 會切換運行的 Stack 與 Code。

- By Chap 3
- 有可能在中斷的最後，trap 會調用 yield。
- yield 又調用 sched，其中 sched 會調用 swtch 來保存當前上下文到 proc->context 中然後切換到之前保存的調度器上下文 cpu->scheduler。

- 這章
- sched 調用 swtch 切換到 cpu->scheduler，即 per-cpu 的 Scheduler 的 Context。這個 Context 是在之前 Scheduler 調用 swtch 時保存的。當 swtch 返回時，它不會返回到 sched 中，而是返回到 scheduler，其 Stack Pointer 指向了當前 CPU 的 Scheduler Stack，而非initproc 的 Kernel Stack。

---

### Code: Scheduling
- Process 想要讓出 CPU 必須要獲得進程表的鎖ptable.lock，並釋放其擁有的其他鎖，修改自己的狀態（proc->state），然後調用sched。

### - scheduler()

// File:proc.c
//PAGEBREAK: 42
// Per-CPU process scheduler.
// Each CPU calls scheduler() after setting itself up.
// Scheduler never returns.  It loops, doing:
//  - choose a process to run
//  - swtch to start running that process
//  - eventually that process transfers control
//      via swtch back to the scheduler.
void
scheduler(void)
{
  struct proc *p;

  for(;;){
    // Enable interrupts on this processor.
    sti();

    // Loop over process table looking for process to run.
    acquire(&ptable.lock);
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->state != RUNNABLE)
        continue;

      // Switch to chosen process.  It is the process's job
      // to release ptable.lock and then reacquire it
      // before jumping back to us.
      proc = p;
      switchuvm(p);
      p->state = RUNNING;
      swtch(&cpu->scheduler, proc->context);
      switchkvm();

      // Process is done running for now.
      // It should have changed its p->state before coming back.
      proc = 0;
    }
    release(&ptable.lock);

  }
}

---

:::warning
- Problem
- 沒看到 PageTable 的交換
:::

---

### Sleep and wakeup
- 鎖的機制使得 CPU 之間的 Process 不會互相打擾；調度使得進程可以共享 CPU 。但是現在我們還不知道 Process 之間是如何交換信息的。
- Sleep 和 Wakeup 實際上就提供了 Process 間通信的機制，可以讓一個 Process 暫時休眠等待某個特定事件的發生，然後當特定事件發生時另一個 Process 會喚醒該 Process。睡眠與喚醒通常被稱為 順序合作（sequence coordination） 或者 有條件同步（conditional synchronization） 機制。

- EX

    struct q {
        void *ptr;
    };

    void*
    send(struct q *q, void *p)
    {
        while(q->ptr != 0)
            ;
        q->ptr = p;
    }

    void*
    recv(struct q * q)
    {
        void *p;
        while((p = q->ptr) == 0)
            ;
        q->ptr = 0;
        return p;
    }

- 缺點：如果發送者很少發送，那麼接受者就會消耗大量的時間在while循環中苦苦等待一個指針的出現。

- 加上 Sleep , Awake

    void*
    send(struct q *q, void *p)
    {
        while(q->ptr != 0)
            ;
        q->ptr = p;
        wakeup(q);    /*wake recv*/
    }

    void*
    recv(struct q *q)
    {
        void *p;
        while((p = q->ptr) == 0)
            sleep(q);
        q->ptr = 0;
        return p;
    }

- 問題：假設在第 215 行 recv 發現 q->ptr == 0，然後決定調用 sleep ，但是在 recv 調用 sleep 之前（譬如這時處理器突然收到一個中斷然後開始執行中斷處理，延遲了對 sleep 的調用），send 又在另一個 CPU 上運行了，它將 q->ptr 置為非零，然後調用 wakeup，發現沒有進程在休眠，於是什麼也沒有做。接著，recv 從第 216 行繼續執行了：它調用 sleep 進入休眠。這就出現問題了，休眠的 recv 實際上在等待一個已經到達的指針。而下一個 send 又在睡眠中等著 recv 取出隊列中的指針。這種情況就被稱為死鎖（deadlock）。

- 下面我們還將看到一段能保護該固定狀態但仍有問題的代碼：

    struct q {
        struct spinlock lock;
        void *ptr;
    };

    void *
    send(struct q *q, void *p)
    {
        acquire(&q->lock);
        while(q->ptr != 0)
            ;
        q->ptr = p;
        wakeup(q);
        release(&q->lock);
    }

    void*
    recv(struct q *q)
    {
        void *p;
        acquire(&q->lock);
        while((p = q->ptr) == 0)
            sleep(q);
        q->ptr = 0;
        release(&q->lock;
        return p;
    }

- 當 recv 帶著鎖 q->lock 進入睡眠後，發送者就會在希望獲得鎖時一直阻塞。

- 所以想要解決問題，我們必須要改變sleep的接口。sleep必須將鎖作為一個參數，然後在進入睡眠狀態後釋放之；這樣就能避免上面提到的“遺失的喚醒”問題。一旦進程被喚醒了，sleep在返回之前還需要重新獲得鎖。

    struct q {
        struct spinlock lock;
        void *ptr;
    };

    void *
    send(struct q *q, void *p)
    {
        acquire(&q->lock);
        while(q->ptr != 0)
            ;
        q->ptr = p;
        wakeup(q);
        release(&q->lock);
    }

    void*
    recv(struct q *q)
    {
        void *p;
        acquire(&q->lock);
        while((p = q->ptr) == 0)
            sleep(q, &q->lock);
        q->ptr = 0;
        release(&q->lock;
        return p;
    }

- recv 持有 q->lock 就能防止 send 在 recv 檢查 q->ptr 與調用 sleep 之間調用 wakeup 了。當然，為了避免死鎖，接收進程最好別在睡眠時仍持有鎖。所以我們希望 sleep 能用原子操作釋放 q->lock 並讓接收進程進入休眠狀態。

---

### Code: Sleep and wakeup
### - Sleep()

// File：proc.c
// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void
sleep(void *chan, struct spinlock *lk)
{
  if(proc == 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.
  proc->chan = chan;
  proc->state = SLEEPING;
  sched();

  // Tidy up.
  proc->chan = 0;

  // Reacquire original lock.
  if(lk != &ptable.lock){  //DOC: sleeplock2
    release(&ptable.lock);
    acquire(lk);
  }
}

### - wakeup()

//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);
}

---

### Code: Pipes
- 從管道的一端寫入數據字節，然後數據被拷貝到內核緩衝區中，接著就能從管道的另一端讀取數據了。

### - Structure

struct pipe {
  struct spinlock lock;
  char data[PIPESIZE];
  uint nread;     // number of bytes read
  uint nwrite;    // number of bytes written
  int readopen;   // read fd is still open
  int writeopen;  // write fd is still open
};

### - pipewrite()

//PAGEBREAK: 40
int
pipewrite(struct pipe *p, char *addr, int n)
{
  int i;

  acquire(&p->lock);
  for(i = 0; i < n; i++){
    while(p->nwrite == p->nread + PIPESIZE){  //DOC: pipewrite-full
      if(p->readopen == 0 || proc->killed){
        release(&p->lock);
        return -1;
      }
      wakeup(&p->nread);
      sleep(&p->nwrite, &p->lock);  //DOC: pipewrite-sleep
    }
    p->data[p->nwrite++ % PIPESIZE] = addr[i];
  }
  wakeup(&p->nread);  //DOC: pipewrite-wakeup1
  release(&p->lock);
  return n;
}

### - piperead()

int
piperead(struct pipe *p, char *addr, int n)
{
  int i;

  acquire(&p->lock);
  while(p->nread == p->nwrite && p->writeopen){  //DOC: pipe-empty
    if(proc->killed){
      release(&p->lock);
      return -1;
    }
    sleep(&p->nread, &p->lock); //DOC: piperead-sleep
  }
  for(i = 0; i < n; i++){  //DOC: piperead-copy
    if(p->nread == p->nwrite)
      break;
    addr[i] = p->data[p->nread++ % PIPESIZE];
  }
  wakeup(&p->nwrite);  //DOC: piperead-wakeup
  release(&p->lock);
  return i;
}

---

### Code: Wait, exit, and kill
### - wait()

// Wait for a child process to exit and return its pid.
// Return -1 if this process has no children.
int
wait(void)
{
  struct proc *p;
  int havekids, pid;

  acquire(&ptable.lock);
  for(;;){
    // Scan through table looking for zombie children.
    havekids = 0;
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->parent != proc)
        continue;
      havekids = 1;
      if(p->state == ZOMBIE){
        // Found one.
        pid = p->pid;
        kfree(p->kstack);
        p->kstack = 0;
        freevm(p->pgdir);
        p->state = UNUSED;
        p->pid = 0;
        p->parent = 0;
        p->name[0] = 0;
        p->killed = 0;
        release(&ptable.lock);
        return pid;
      }
    }

    // No point waiting if we don't have any children.
    if(!havekids || proc->killed){
      release(&ptable.lock);
      return -1;
    }

    // Wait for children to exit.  (See wakeup1 call in proc_exit.)
    sleep(proc, &ptable.lock);  //DOC: wait-sleep
  }
}

### - exit()

// Exit the current process.  Does not return.
// An exited process remains in the zombie state
// until its parent calls wait() to find out it exited.
void
exit(void)
{
  struct proc *p;
  int fd;

  if(proc == initproc)
    panic("init exiting");

  // Close all open files.
  for(fd = 0; fd < NOFILE; fd++){
    if(proc->ofile[fd]){
      fileclose(proc->ofile[fd]);
      proc->ofile[fd] = 0;
    }
  }

  iput(proc->cwd);
  proc->cwd = 0;

  acquire(&ptable.lock);

  // Parent might be sleeping in wait().
  wakeup1(proc->parent);

  // Pass abandoned children to init.
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->parent == proc){
      p->parent = initproc;
      if(p->state == ZOMBIE)
        wakeup1(initproc);
    }
  }

  // Jump into the scheduler, never to return.
  proc->state = ZOMBIE;
  sched();
  panic("zombie exit");
}

### - kill()

// Kill the process with the given pid.
// Process won't exit until it returns
// to user space (see trap in trap.c).
int
kill(int pid)
{
  struct proc *p;

  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->pid == pid){
      p->killed = 1;
      // Wake process from sleep if necessary.
      if(p->state == SLEEPING)
        p->state = RUNNABLE;
      release(&ptable.lock);
      return 0;
    }
  }
  release(&ptable.lock);
  return -1;
}

---