テキストの62ページ

本文

1. sleepはデッドロックを回避するために lk != &ptable.lock であるかどうかチェックを行う。

if(lk != &ptable.lock){
  acquire(&ptable.lock);
  release(lk);
}

を

release(lk);
acquire(&ptable.lock);

に置き換えて、その特殊な場合（デッドロックが起きる場合）そのものを除去したとする。
これはsleepを壊すだろう。
どういう流れで問題が起きるか説明しなさい。

2. ほとんどのプロセスのクリーンアップ処理は、exitとwaitのどちらか一方または両方で出来たはずだ。
がしかし、 exitはp->kstackを解放すべきでないということを以前の節で見た。
だったら、exitは開いているファイルを閉じるためのものでなければならないということになる。
何故か？
パイプという言葉をつかって説明しなさい。

3. xv6用のセマフォを実装しなさい。
mutexは使えるが、sleepとwakeupは使えないものとする。
xv6の中でsleepとwakeupを使ってるところをセマフォで置き換えなさい。
その結果を推察しなさい。

作業

1. について
これは”起き損ないの問題”が起きるパターンかと思います。
sleepの呼び出し側のインバリアントの保護のためのlkが解放されているのに、まだsleep/wakeupのための&ptable.lockが確保されていないタイミングが生まれてしまうため、そのタイミング（まだスリープは完了してない段階）で別のプロセスによる同じチャンネル上のwakeupが実行されてしまう危険があります。

proc.cのsleep関数（変更前のソース。参考用）

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

2. について
ちょっと質問の内容がよく分かりませんが、「クリーンアップ処理についてwaitで子プロセスのproc構造体を、exitで自身のファイルディスクリプタをそれぞれ受け持つような役割になってるのは何故か？」という質問だと仮定してみます。

まずwaitについては、子プロセスを待つために親プロセスで使われるので、その中で子プロセスそれぞれのproc構造体をクリーンアップするのは理にかなってると言えます。
（子プロセスがすべて終了しZOMBIEになった直後にwaitは処理を受け継ぐ事が出来るので。）

もしexitでproc構造体をクリーンアップするとしたら、exit関数の処理中はまだプロセスは生きていて、生きているプロセスのproc構造体をそれ自身でクリーンアップするのは、（ちゃんと追ってませんが）いかにも問題ありそうです。
少なくともp->kstackはexit中では解放出来ません。

exitについては、子プロセスが終了するために子プロセスで使われる（親プロセスでも使われますが、それはそのプロセスのさらに親、例えばシェル、に対して使われるものなので、同じことです）と敢えて考えてみると、それぞれの子プロセスがもつファイルをこのタイミングで閉じるのも理にかなってると言えます。

それぞれのプロセスが開いているファイルは、proc構造体のofileに情報があり、親子関係であろうとそれはプロセス間で全くバラバラになり得るので、それぞれのプロセスが責任をもって自分が開いたファイルを閉じるのがシンプルで良いと思います。

もしこれをwaitで行うとすると、子プロセスのproc構造体をクリーンアップしてる部分にファイルの解放処理を追加することになると思います。
しかしそれだと親がwaitを呼ぶまで子が開いたファイルを閉じれないということになります。

また、「親が何かの処理を繰り返すためにメインループを実行し、そのメインループ中に子の生成を繰り返し、子は各々勝手に処理を行い、親が子のexitを待つ必要なく、親がwaitを呼ぶのは親が終了するときだけ」というアプリケーションもあり得ます。（サーバプログラムによくあるパターンです）

その場合、waitで子のファイルを閉じるようになってると、無数の子が開いた無数のファイルが親が終了するまで全く閉じられないことになります。
もちろんこの場合も、waitを最後だけじゃなくて適宜呼ぶことでこの問題を回避することは出来るはずですが、パフォーマンスは落ちるはずです。
それが無視出来る程度だったとしても、ユーザサイドのプログラミングにおける決まりごとを増やすのはあまり良いやり方とは思えません。

proc.cのexit, wait関数（参考用）

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

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

3. について
まずはxv6で使われてるスピンロックとmutexの違いを。
どちらも処理の同期化（直列化）のために使われるものですが、

スピンロック
ロックが獲得できるようになるまでビジーウェイトで待つ方式。
ビジーウェイトと聞くと重そうではあるが、典型的にはCのコードにして数行分待つ間だけ（もちろんデッドロックを除いた最悪の場合、かなり長い間CPUを浪費する場合も有りうる）で、他でロックが解放されてから獲得できるようになるまでのタイムラグが究極的に小さい（もちろん他との獲得競争があってそれに破れた側の視点からのみ見るとその限りではないが、全体としてはロックが必要とされてるのに誰も獲得していないという空白期間を最小に出来る）。

mutex
mutexは色んなOSで色んな実装があって、仕様的にもそれぞれ微妙に違ってたりするので、ここはxv6的に以下のように定義されるとします。

ロックが確保出来た場合はすぐに呼び出し元に戻る。
ロックが確保できなかった場合はsleepして確保できるようになるまで待つ。
再帰ロックは出来ない。
ロックを解放するときは解放した後wakeupを呼び、他のロック解放待ちのプロセスを起こす。
インターフェイスは、
void acquiremutex(struct mutex *m);
void releasemutex(struct mutex *m);
とする。

と、ここまで考えたものの、そのようなmutexを使い、直接sleepとwakeupを使わないセマフォの実装は考えつかず。
前提がおかしいのか頭がおかしいのか…

感想

3が手も足も出なくてくやしい