Serializing token
IRCのosdev-jで話題に上ったので。
serializing tokenは、主にDragonfly BSDで使用されているカーネルプログラミングテクニック/同期プリミティブで、主にMutexと比較される。
- http://en.wikipedia.org/wiki/Serializing_tokens
- http://thread.gmane.org/gmane.os.dragonfly-bsd.kernel/4436
- Dillon(DflyBSDリーダ)の発言が参考になる。
短い歴史
CPUが2つ以上あるシステムでは、デバイス(やメモリ)へのアクセスが競合しないように何らかの調停を行う必要がある。
古いFreeBSD(や他のOS)は、そもそもカーネルがリエントラントでなかった。つまり、あるCPUがカーネルを実行している間は、他のCPUはカーネルを実行できない。このとき、ロックは1つだけ使うことになる。カーネルの入口で確保し、出口で解放する。このようなロックを"Giant Lock"のように表現する。
これではパフォーマンスが出ないので、現在のメジャーなOSは、カーネル内でMutexを使ってアクセスを可能な限り細かい粒度で排他するようにデバイスドライバを作り直している。しかし、Mutexを使ったプログラミングはデッドロックのような問題が有ってちょっと難しい。
DragonFly BSDはMutexでない別のプリミティブSerializing tokenを用いることでプログラミングを簡単にしたまま、かつ、Giant Lockingを排除しようとしている。
前提
スレッドはプリエンプションされないと考える方がすっきりする。つまり、割り込みの処理にロックやtokenを確保する必要があって、他人にロックが保持されているようなケースでは、割り込みの処理も遠慮無く遅延することになる。
Dflyとしては、そもそも、その手の競合を減らすようにデザインするのが好ましいということになっている。
Serialized token
Serialized tokenは2つの操作+αを提供する。
- (生成/破棄)
- get
- release
getはトークンを取得し、releaseはトークンを解放する。これはMutexに似ているが、非常に重要な点は"トークンは他人にも取られている可能性があるが、実行時点で持っているのは自分だけ"という点。(Mutexは、一度確保することに成功すれば、自分が実行されていないときにも他人に確保されることは無い。)
スレッドは任意の数のトークンを取得することが出来る。
... この挙動はちょっと理解しづらいかもしれないが、幾つかの方法で同じ事を説明出来る。
- トークンが世界に一つしか無いなら、Mutexと同じように働く。そのトークンを開放するまで、他の(そのトークンを確保したい)スレッドは待たされる。
- あるスレッドが2つ以上のトークンを確保するときは事情が異なる。
- スケジューラは、あるトークンを持っているスレッドが同時に1つだけ解放されるまで連続して実行されることを保証する必要がある。逆に言えば、あるトークンが複数のスレッドに獲得されていることもある。単に、そのグループのうち1つだけが実行され、他が寝ているということになる。(あるいは、そのグループ全てが寝ている。)
- スレッドは"実行するために要求するトークンのリスト"を持つ。そして、そのトークンすべてが確保できるときだけ、スケジューラはそのスレッドをスケジュールする。
- アプリケーションの側から見ると、トークンを待つためにsleepした場合、それまで獲得に成功した全てのトークンを手放したと考える必要がある。そして、そのsleepから返ってきたときに、今まで獲得していた全てのトークンも同時に復帰することになる。
- つまり、その間にデータが書き換えられている可能性もある。
先に書いたように、非同期的にスレッドがプリエンプションされるケースはあまり考えない方が良い。仮にタイムスライスを使い切るなりなんなりの理由でスレッドが停止された場合は、確保したトークンを手放したことにはならない。
トークンは、あるコード領域が、ある条件下で連続して実行されることだけを保証する(= シリアライズ)。
