読書メモ: xv6 book - Chapter 4: Locking #xv6

xv6 は multiprocessor なので、 lock が必要。
single processor だとしても、interrupt を考えると、排他制御は必要

Spinlock

共有リソースに struct spinlock がくっついていて、それを獲得してからそのリソースを使う
使いみちは、IDE driver の disk request queue の不変条件を守る, console (avoid intermixed output), process table など多数.

xchgl: atomic にメモリ(word)と、レジスタの値を交換

acquire(lk): spin lock を獲得

割り込みを禁止
xchg を使って atomic に lk->lock を獲得(解放されるまでまつ)
stack trace などデバッグ情報を lk に書く

release()

lk を acquire した CPU が呼んでなければバグ
lk->lock = 0
割り込みを許可

擬似コード

acquire(struct spinlock lk) {
  割り込み禁++  // 1 以上だと割り込み禁止. ネストすることもあるので=1としない
  __sync_synchronize() // (memory barrier. reorder を防ぐ)
  loop {
    r = 1
    xchg(lk->locked, r)
    if (!r) break;
  }
  lk->cpu = ...
}
release(...) {
  CHECK(lk->cpu == mycpu());
  mov(lk->lock, 0) // atomic にすべての byte を 0 にする
  __sync_synchronize()
  割り込み禁--
}

複数プロセスの read write race があるときは lock が必要

lock を使うときは、不変条件を意識することが大事.
不変条件とは、データ構造の性質であって、lock の外では常に守られるもの
不変条件が複数のメモリアドレスを含むなら、それらはともに１つの lock で守るのがよい。lock が細かいと同時に2つ以上のlockをとらないと不変条件を守れないとかややこしい。
lock は並列性能を下げる。極端な例は giant kernel lock: kernel に入るとき acquire, 出るとき release ... 常に1つのCPUしかkernelを実行できない
xv6 ではわりと粗く、ひとつのデータ構造を 1つの lock で守る (process table 全体など (Chapter 5))

2つ以上のlockを取るときは常に同じ順番にしないと deadlock する。最長の例：creating a file acquires locks in the following order:

the directory (file table)
the new inode
disk block buffer (ディスク内容の in memory copy)
IDE queue
process table

Sleep lock

長く lock をとる必要がある場合に使う
xv6 では file system のみで使用 (disk に書き/読み終わるまで disk 内容の in memory copy を守る)
lock を取ったプロセスを、待っている interrupt があるまで sleep 状態にして、他のプロセスがそのCPUで走れるようにする。つまり spin lock とは異なり、割り込みは無効化しない。すでに lock が取られているときも、同様に sleep 状態にしてその開放を待つ。(lock の開放は、同じ lock で待っている process を全員起こす)

sleeplock を(同じCPUが) spin lock でとろうとすると、当然いつまでたっても起きず deadlock になる。

sleep というのは、CPU命令とかではなく、p->state = SLEEPING にして sched を呼ぶ (Chapter 5). wakeup は sleep の逆で、state を RUNNABLE にする

acquiresleep(struct sleeplock lk) {
  acquire(lk->lk)
  while(lk->locked)
    sleep the process on lk // (Chapter 5)
  lk->locked = 1;
  release(lk->lk)
}
releasesleep(lk) {
  acquire(lk->lk)
  lk->locked = 0
  wakeup the processes on lk // (Chater 5)
  release(lk->lk)
}

Limitation of locks

lock をとる関数で、caller にその lock をとるのと、とる必要がないのがある場合の対処:

1.　2種類の関数を用意 (wakeup, wakeup1), or
2.　caller がつねに lock をとることを要求 (sched)

いずれにしても caller は注意する必要がある

両方が他の thread からの update を待っている場合 (pipe buffer)
p1 -> buf <- p2 みたいになっていてどちらも lock を取れない (他方からの update ができなくなってしまう) この場合は sleep, wakeup を使う (Chater 5)

Real world

pthread (POSIX thread) - user process が複数の thread を複数の CPU で動かせるようにする. カーネルのサポートが必要:

プロセスの thread 1 が syscall でブロックされているあいだ、同じプロセスの thread 2 がその CPU で動けるようにする
process がおいてあるアドレスが変化したとき、page table を更新するだけでなく、そのプロセスがもつ thread が動いている別の CPU の TLB を (interprocess interrupt で) invalidate する必要がある。さもないとその thread が古いキャッシュをみてしまう

多くの processor が同じ spin lock をとっていくのはキャッシュが効かないため高価。lk->lock が別の CPU のキャッシュに乗っていると、xchg は (キャッシュコヒーレンシを守るため)、そのキャッシュを invalidate する。
これを避けるため、なるべく lock を減らす lock free programming というもあるけど、xv6 ではつかってない

用語

thread: 仮想的な、process 専用の CPU
TLB: translation lookaside buffer - MMU の, virtual address translation のキャッシュ