トークンのシリアル化

コンピュータサイエンスにおいて、シリアル化トークンは、 DragonFly BSDの継続的な開発から生まれた並行制御の概念です。Matthew Dillonによると、シリアル化トークンはSPLに最も似ていますが、トークンは複数のCPUにまたがって機能しますが、SPL は単一の CPU のドメイン内でのみ機能します。

トークンをシリアル化することで、プログラマーは、自分自身や下位レベルのサブシステムが同じトークンを保持している可能性のあるすべてのエンティティを認識する必要なく、マルチプロセッサ対応のコードを書くことができます。

トークンと相互排他(ミューテックス) メカニズムはロックです。ミューテックスとは異なり、トークンは、ブロックまたはスリープ状態のときに他のスレッドがリソースにアクセスすることを除外しません。他のスレッドとリソースを共有するスレッドは、さまざまな理由で停止および開始されることがあります。

1. タイムスライス: ユーザー空間 (US) スケジューラは、すべてのスレッドが公平に実行されるように努め、各スレッドを短時間 (タイムスライス) 実行してから別のスレッドに切り替えます。
2. 同時実行: マルチプロセッサ コンピュータでは、スレッドは別の CPU 上の別のスレッドとまったく同時に実行されることがあります。
3. プリエンプション: スレッドは、ハードウェア割り込みや軽量カーネル スレッドなどの優先度の低いスレッドをプリエンプトする場合があります。
4. 自発的なブロッキング: スレッドは、何かを待機する必要がある場合、実行する作業がない場合、またはブロックする関数を呼び出す場合にスリープすることがあります。ロックを取得するための呼び出しでもブロックされる可能性があります。

次の表は、トークンとミューテックスのプロパティをまとめたものです。

デッドロックや優先順位の逆転などの問題は回避が非常に難しく、カーネルの多くのレベルで調整が必要になります。トークンによるロックはデッドロックにならず、取得されたトークンは後続の操作がブロックされるときにアトミックである必要がないため、ミューテックスよりもはるかにシンプルなコードが可能になります。

... FreeBSD-5 を見ると、FreeBSD-5 では、非常に深いプロシージャ レベルでミューテックスを一時的に解放して切り替えたり、ブロックしたり、デッドロックに対処したりできるように、保持されているミューテックスをサブルーチン スタックに頻繁に渡していることに気付くでしょう。このため、FreeBSD-5 ではコード汚染がかなり発生しています (一部のプロシージャでは、適切に機能するために、他の無関係なプロシージャによって保持されているミューテックスに関する情報を与える必要があります)。

— マシュー・ディロン

次の疑似コードと説明は、トークンのシリアル化がどのように機能するかを示しています。

Mac OS XのDarwinカーネルは、同様の手法 (ファンネルと呼ばれる) を使用して、カーネルの BSD部分へのアクセスをシリアル化します。

• ロックフリーおよび待機フリーのアルゴリズム

• マシュー・ディロンがトークンについて詳細に説明しているメーリングリストのスレッド。2017年2月5日にWayback Machineにアーカイブされました。
• Darwin スレッド アーキテクチャ