DragonFly - Light Weight Kernel Threading Model ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ The Light Weight Kernel Threading Model 軽量カーネルスレッドモデル DragonFly employs a light weight kernel threading (LWKT) model at its core. Each process in the system has an associated thread, and most kernel-only processes are in fact just pure threads. For example, the pageout daemon is a pure thread and has no process context. DragonFly はその中核部分に軽量カーネルスレッド(LWKT)を用います。システムの プロセスは全てスレッドと結びついていて、カーネルのみのプロセスのほとんどは 事実上純粋なスレッドです。たとえば、 pageout デーモンは純粋なスレッドでプ ロセスコンテクストを持ちません。 The LWKT model has a number of key features that can be counted on no matter the architecture. These features are designed to remove or reduce contention between cpus. LWKT モデルはアーキテクチャによらないいくつかの鍵となる特徴があります。こ れらの特徴は CPU 間の競合を除く、あるいは減らすために設計されています。 1. Each cpu in the system has its own self-contained LWKT scheduler. Threads are locked to their cpus by design and can only be moved to other cpus under certain special circumstances. Any LWKT scheduling operation on a particular cpu is only directly executed on that cpu. This means that the core LWKT scheduler can schedule, deschedule, and switch between threads within a cpu's domain without any locking whatsoever. No MP lock, nothing except a simple critical section. 1. システムの各 CPU は自己完結の LWKT スケジューラを持ちます。スレッドは意 図的に CPU に結びついていて、いくつかの特殊な状況下でのみ他の CPU へ移動す ることができます。特定の CPU 上の LWKT スケジューリング処理はその CPU 上で のみ直接実行されます。これは、 LWKT スケジューラ本体がスケジュール追加、除 去、 CPU 内でのスレッド間スイッチを、ロックを一切せずに処理できるというこ とです。単純なクリティカルセクションの除いては MP ロックもなにもなしにです。 2. A thread will never be preemptively moved to another cpu while it is running in the kernel, a thread will never be moved between cpus while it is blocked. The userland scheduler may migrate a thread that is running in usermode. A thread will never be preemptively switched to a non-interrupt thread. If an interrupt thread preempts the current thread, then the moment the interrupt thread completes or blocks, the preempted thread will resume regardless of its scheduling state. For example, a thread might get preempted after calling lwkt_deschedule_self() but before it actually switches out. This is OK because control will be returned to it directly after the interrupt thread completes or blocks. 2. スレッドはカーネルで動作中は他の CPU にプリエンプティブに移動されること はありません。スレッドはブロックされている間は CPU 間を移動しません。ユー ザランドスケジューラはユーザモードで実行しているスレッドを移動できます。ス レッドは非割り込みスレッドへプリエンプティブにスイッチすることはありません。 割り込みスレッドがカレントスレッドをプリエンプトする場合、割り込みスレッド が終了またはブロックした時点でプリエンプトされた方のスレッドはスケジュール 状態によらず復元されます。たとえば、あるスレッドは lwkt_deschedule_self() を呼んだあと、実際に(訳注: 別のスレッドへ)スイッチする前にプリエンプトされ る可能性があります。これは問題ありません。なぜなら割り込みスレッドが完了ま たはブロックしたあとそのスレッドに直接制御が戻るからです。 3. Due to (2) above, a thread can cache information obtained through the per-cpu globaldata structure without having to obtain any locks and, if the information is known not to be touched by interrupts, without having to enter a critical section. This allows per-cpu caches for various types of information to be implemented with virtually no overhead. 3. 上の(2)により、スレッドは CPU ごとの globaldata 構造体を通じて得た情報 をロックなしにキャッシュすることができます。また、その情報が割り込みスレッ ドによって変更されないと分かっている場合は、クリティカルセクションに入る必 要がありません。これによって、いろいろな種類のデータの CPU ごとのキャッシュ (訳注: 「の」の連続だ)を、事実上オーバヘッドなしに持つことができます。 4. A cpu which attempts to schedule a thread belonging to another cpu will issue an IPI-based message to the target cpu to execute the operation. These messages are asynchronous by default and while IPIs may entail some latency, they don't necessary waste cpu cycles due to that fact. Threads can block such operations by entering a critical section and, in fact, that is what the LWKT scheduler does. Entering and exiting a critical section are considered to be cheap operations and require no locking or locked bus instructions to accomplish. 4. ある CPU が他の CPU に属するスレッドをスケジュールしようとする場合は、 ターゲット CPU に IPI ベースのメッセージを発行して、処理を実行します。この メッセージはデフォルトで非同期で、このため IPI はレイテンシを伴うことがあ りますが必ずしも CPU サイクルを浪費するとは限りません。この IPI の処理はク リティカルセクションに入ったスレッドによってブロックされます。実際、 LWKT スケジューラはそうします。クリティカルセクションの出入りは安価な処理と考え られるので、ロックやバスロック命令を必要としません。 5. The IPI messaging subsystem deals with FIFO-full deadlocks by spinning and processing the incoming queue while waiting for its outgoing queue to unstall. The IPI messaging subsystem specifically does not switch threads under these circumstances which allows the software to treat it as a non-blocking API even though some spinning might occassionally occur. 5. IPI メッセージサブシステムは FIFO あふれによるデッドロックに対し、送信 キューの停滞が解消するのを待つ間、受信キューをスピンして処理することで対処 します。 IPI メッセージサブシステムはこのような状況下で特にスレッドのスイ ッチを行いません。これによって、まれにスピンが発生する場合があってもソフト ウェアはこれをノンブロッキング API のように扱うことができます。 In addition to these key features, the LWKT model allows for both FAST interrupt preemption AND threaded interrupt preemption. FAST interrupts may preempt the current thread when it is not in a critical section. Threaded interrupts may also preempt the current thread. The LWKT system will switch to the threaded interrupt and then switch back to the original when the threaded interrupt blocks or completes. IPI functions operate in a manner very similar to FAST interrupts and have the same trapframe capability. This is used heavily by DragonFly's SYSTIMERS API to distribute hardclock() and statclock() interrupts to all cpus. これらの鍵となる特徴に加え、 LWKT モデルでは高速割込みプリエンプションとス レッド割込みプリエンプションを両立します。高速割り込みはカレントスレッドが クリティカルセクションに入っていない場合はプリエンプトできます。スレッド割 込みもカレントスレッドをプリエンプトできます。 LWKT システムは、スレッド割 込みにスイッチしたあとそれがブロックまたは完了した場合にもとのスレッドに戻 ります。 IPI 関数は高速割り込みと非常に似たやり方で動作し、同じく trapframe 機能を持ちます。これは DragonFly の SYSTIMERS API で hardclock() や statclock() の割込みを全ての CPU に分配するために多く用いられています。 The IPI Messaging Subsystem IPI メッセージサブシステム The LWKT model implements an asynchronous messaging system for communication between cpus. Basically you simply make a call providing the target cpu with a function pointer and data argument which the target cpu executes asynchronously. Since this is an asynchronous model the caller does not wait for a synchronous completion, which greatly improves performance, and the overhead on the target cpu is roughly equivalent to an interrupt. LWKT モデルは CPU 間通信のための非同期メッセージシステムを実装します。基本 的には、関数ポインタとデータ引数を引数として関数を呼び出すとターゲット CPU にそれを渡り、ターゲット CPU はそれを非同期に実行します。これは非同期モデ ルなので呼び側は同期完了を待ちません。このため性能が非常に向上し、ターゲッ ト CPU へのオーバヘッドもおおまかには割り込みと同等程度です。 IPI messages operate like FAST Interrupts... meaning that they preempt whatever is running on the target cpu (subject to a critical section), run, and then whatever was running before resumes. For this reason IPI functions are not allowed to block in any manner whatsoever. IPI messages are used to do things like schedule threads and free memory belonging to other cpus. IPI メッセージは高速割り込みのように動作します...つまり(クリティカルセクシ ョンに左右されますが)ターゲット CPU で動いているものは何でもプリエンプトし、 実行し、そのあともともと動いていたものに復帰します。このため IPI 関数はい かなる理由であってもブロックすることは許されません。 IPI メッセージはスレ ッドをスケジュールしたり他の CPU に属しているメモリを解放するといった処理 をするのに用いられます。 IPI messaging is used heavily by at least half a dozen major LWKT subsystems, including the per-cpu thread scheduler, the slab allocator, and messaging subsystems. Since IPI messaging is a DragonFly-native subsystem, it does not require and does not use the Big Giant Lock. All IPI based functions must therefore be MP-safe (and they are). IPI メッセージ処理は少なくとも 6個の主な LWKT サブシステムで多用されていま す。それらには、 CPU ごとのスレッドスケジューラ、 slab allocator 、メッセ ージサブシステムが含まれています。 IPI メッセージ処理は DragonFly に本来的 に適応したサブシステムなので、 Big Giant Lock を必要とせず、使用してもいま せん。全ての IPI ベースの関数は従って MP セーフである必要があります(そうな っています)。 The IPI-based CPU Synchronization Subsystem IPI ベースの CPU 同期サブシステム The LWKT model implements a generalized, machine independant cpu synchronization API. The API may be used to place target cpu(s) into a known state while one is operating on a sensitive data structure. This interface is primarily used to deal with MMU pagetable updates. For example, it is not safe to check and clear the modify bit on a page table entry and then remove the page table entry, even if holding the proper lock. This is because a userland process running on another cpu may be accessing or modifying that page, which will create a race between the TLB writeback on the target cpu and your attempt to clear the page table entry. The proper solution is to place all cpus that might be able to issue a writeback on the page table entry (meaning all cpus in the pmap's pm_active mask) into a known state first, then make the modification, then release the cpus with a request to invalidate their TLB. LWKT モデルは、汎用でマシンに依存しない CPU 同期 API が備わっています。こ の API によって、デリケートなデータ構造にアクセスしている状態のターゲット CPU を既知の状態に移行させることができます。このインタフェイスは主に MMU のページテーブルを更新するのに使用されています。たとえば、もし適切なロック を確保していたとしても、ページテーブルエントリのモディファイビットをテスト、 クリアしたあとにページテーブルエントリを削除するのは安全ではありません。こ れは、他の CPU で動作しているユーザランドプロセスがそのページを読み書きす る可能性があるからで、その場合向こう側の CPU が TLB を書き戻すのとページテ ーブルエントリをクリアしようとする処理の間にレース状態が生じます。適切な解 決は、ページテーブルエントリへ書き戻す可能性のある CPU (つまり pmap の pm_active マスクでセットされている全 CPU)をまず既知の状態に移行し、変更処 理をしてから、各 CPU の TLB を無効化するリクエストによって CPU を解放する という方法です。 The API implemented by DragonFly is deadlock-free. Multiple cpu synchronization activities are allowed to operate in parallel and this includes any threads which are mastering a cpu synchronization event for the duration of mastering. Even with this flexibility, since the cpu synchronization interface operates in a controlled environment the callback functions tend to work just like the callback functions used in the IPI messaging subsystem. DragonFly に備わっている API にはデッドロックがありません。複数の CPU 同期 処理が並行に動作することが可能で、これは CPU 同期イベントの主導権を握って いるスレッドにもあてはまります。これは柔軟なしくみですが、 CPU 同期インタ フェイスは制御された環境で動作するため、コールバック関数は IPI メッセージ サブシステムで用いられるものとちょうど同じように動作する傾向にあります。 Serializing Tokens 同期トークン A serializing token may be held by any number of threads simultaneously. A thread holding a token is guaranteed that no other thread also holding that same token will be running at the same time. 同期トークンはいくつものスレッドが同時につかめます。トークンをつかんでいる スレッドは、同一のトークンをつかんでいる他のスレッドが同時には実行しないこ とが保証されます。 A thread may hold any number of serializing tokens. 一つのスレッドは同期トークンをいくつでもつかむことができます。 A thread may hold serializing tokens through a thread yield or blocking condition, but must understand that another thread holding those tokens may be allowed to run while the first thread is not running (blocked or yielded away). あるスレッドは、イールドまたはブロック条件を通じて同期トークンをつかむこと がありますが、そのスレッドが(ブロックあるいはイールドされて)実行中でない間 、それらのトークンをつかんでいる他のスレッドが実行する可能性があることを考 慮に入れる必要があります。 There are theoretically no unresolvable deadlock situations that can arise with the serializing token mechanism. However, the initial implementation can potentially get into livelock issues with multiply held tokens. 理論上、同期トークンの機構から起きるデッドロック状態で解決できないものはあ りません。しかし、初期の実装ではトークンを同時につかんだ場合にライブロック の問題が起きる可能性があります。 Serializing tokens may also be used to protect threads from preempting interrupts that attempt to obtain the same token. This is a slightly different effect from the Big Giant Lock (also known as the MP lock), which does not interlock against interrupts on the same cpu. It is important to note that token atomicy is maintained through preemptive conditions, even though preemption involves a temporary switch to another thread. It is not necessary to enter a spl() level or critical section to preserve token atomicy. 同期トークンは、同一のトークンをつかもうとする割り込みが他のスレッドをプリ エンプトしてしまうことから保護するのにも使われます。これは Big Giant Lock (BGL; MP ロックともいう)とは若干違った作用があります。 BGL は同一 CPU の割 り込みをインターロックすることはありません。重要なことは、プリエンプション によって一時的に他のスレッドへのスイッチが起きることがあるとしても、トーク ンの原子性(?atomicity)プリエンプティブ条件によって維持されるということです。 トークンの原子性(?atomicity)を維持するために spl() レベルやクリティカルセ クションに入る必要はありません。 Holding a serializing token does not prevent preemptive interrupts from occuring, though it might cause some of those interrupts to block-reschedule. Unthreaded FAST and IPI messaging interrupts are not allowed to use tokens as they have no thread context of their own to operate in. These subsystems are instead interlocked through the use of critical sections. 同期トークンはプリエンプティブは割り込みが起きるのをさまたげることはありま せんが、割込みをブロックして再スケジュールさせることがあります。スレッド化 されていない高速割り込みや IPI メッセージング割り込みはトークンをつかうこ とができません。それは処理に必要なスレッドコンテキストを持っていないからで す。そのかわり、これらのサブシステムはクリティカルセクションを使うことで排 他制御をします。