プリエンプションはメモリの並べ替えのためのガベージコレクションである (2019)

以前、プリエンプションがカーネル内よりもユーザー空間でのロックフリープログラミングを難しくすることを指摘しました。今では、プリエンプションはガベージコレクションのように、既にコストを支払っているものとして扱うべきだと考えています。割り込み処理（実際には割り込みハンドラからの復帰）はx86では完全にシリアライズされており、他のプラットフォームでも同様でしょう。ユーザー空間の命令は、割り込みの前に完全に実行されるか、ユーザー空間への復帰後に再実行されます。これは、明示的なバリアなしにメモリアクセス間の順序を保証するために悪用できるものです。この割り込みの悪用は、Bounded TSOと相補的です。Bounded TSOは、インフライト状態にある可能性のあるストア命令のハードウェア上限を測定し（命令が順序通りにリタイアされるという知識と組み合わせ）、オーバーヘッドなしに、通常はわずかなレイテンシでライブネスを保証します。しかし、最悪実行時間情報がないと、命令数を実時間にマッピングするのは困難です。割り込みを追跡することで、以前の書き込みが確実にリタイアしたと判断できる十分な実時間が経過した時点を特定できますが、Bounded TSOの典型的なケースよりも保守的な遅延の後になります。 この考えに至ったのは、イベントカウントと、ハザードポインタやエポックリクレメーションで使用される非対称フラップフリップという2つのロックフリー同期プリミティブに取り組んだ後です。これらは、スローパスがファストパスからの生命の兆候を待つという点で似ていますが、「スタックした」ファストパスの処理方法が異なります。Linux/x86[-64]で私が開発したイベントカウントとフラップフリップの実装について説明します。これらはどちらも順序保証のために割り込みに依存しています。うまくいけば、プリエンプションがユーザー空間でのロックフリーコードのための、前払いされたバリアの有用なソースであると納得していただけるでしょう。私は、ロックフリープログラミング、特にセーフメモリリクレメーション技術に既に精通しており、形式的なメモリモデルでの推論にある程度の経験がある読者を対象にこれを書いています。さらに参照したい場合は、SamyのACM Queueでの概要が良いリソースです。既にConcurrency Kitのイベントカウントと、私のbarrierdプロジェクトの割り込みベースの逆バリアのコードをコミットしています。 イベントカウントとx86-TSOおよびfutexes イベントカウントは、本質的にはバージョンカウンタであり、スレッドが現在のバージョンが任意の以前のバージョンと異なるまで待つことができます。単純な「待機」実装は、バージョンカウンタをスピンさせることができます。しかし、イベントカウントの利点は、ロックフリーコードがOSレベルのブロッキングと統合できることです。待機者はイベントカウントの現在のバージョンv0を取得し、バージョン付きデータでやりたいことを行い、イベントカウントのバージョンがv0と異なるまでスピンするのではなく、スリープして新しいデータを待つことができます。イベントカウントは、多くの名前（例：ブロックポイント）で再発明される一般的な同期プリミティブです。重要なのは、ライターがバージョンカウンタを更新でき、待機者がバージョンを読み取り、任意のコードを実行し、イベントカウントのバージョンが前のバージョンと同じである間効率的に待機できることです。明示的なバージョンカウンタは、擬似コードに示すように、誤用された条件変数に関連するウェイクアップの喪失問題を解決します。 bad condition waiter: while True: atomically read data if need to wait: WaitOnConditionVariable(cv) else: break 正しく機能するためには、条件変数では、待機条件がまだ満たされているかを確認してから条件変数で待機する前に、データと条件変数の両方を保護するミューテックスを待機者が取得する必要があります。 good condition waiter: while True: with(mutex): read data if need to wait: WaitOnConditionVariable(cv, mutex) else: break 待機者は、ライターがデータに変更を加えるのを防ぐ必要があります。そうでなければ、データ変更（および関連する条件変数ウェイクアップ）が、待機条件を確認してから条件変数での待機を開始する間に発生する可能性があります。その場合、待機者はウェイクアップを見逃し、既に発生したものを待ち続けて永遠にスリープしてしまう可能性があります。 good condition waker: with(mutex): update data SignalConditionVariable(cv) 以下の6つの図は、シグナラー（ライター）がデータに変更を加え、待機者をウェイクアップするのと、待機者がデータを観察して待機キューに入る間の可能なインターリーブを示しています。左側の2つの図は何もインターリーブしません。これらは正しいロッキングによって許可される唯一のシナリオです。残りの4つは待機者とシグナラーを実際にインターリーブし、3つは偶然正しい（幸運）ですが、WSSWという1つのケースでは待機者がウェイクアップを見逃します。 待機者がライターの進行を妨げることができる場合、ロックフリープロトコルは成り立ちません。イベントカウントにより、待機者はウェイクアップされたであろう時点（イベントカウントのバージョンカウンタが変更された）を検出し、待機者がまだ観測していないデータ変更に対するウェイクアップを見逃す可能性のあるこのウィンドウを修正できます。決定的に重要なのは、待機者はウェイクアップの喪失を防ぐのではなく、それを検出することです。したがって、イベントカウントはロックフリー（さらにはウェイトフリー！）を維持します。例えば、ロックフリーリングバッファでイベントカウントを使用できます。コンシューマが書き込みポインタをスピンする代わりに、書き込みポインタをイベントカウントにエンコードし、コンシューマはCPUサイクルを消費して新しいメッセージを待つのではなく、効率的にそれにブロックすることができます。 イベントカウントを実装する上での難しい点は、スリーパーをウェイクアップさせることを確実にするだけでなく、ウェイクアップすべきスリーパーがいる場合にのみ行うことです。一部のユースケースでは、指数バックオフで十分なため、積極的なウェイクアップを行う必要はありません。バージョン更新がリクエスト/レスポンス通信パターンでのレスポンスの到着を示す場合、指数バックオフ（例：1.1倍のバックオフ係数）は、バックオフ中のブラインドスリープによって引き起こされるレスポンスレイテンシの増加を、例えば10%に制限できます。残念ながら、それは常に適用可能ではありません。 一般的に、シグナルが以前のリクエストに対するレスポンスに対応すると仮定することはできません。通常は進行が非常に速く、待機者がより多くの作業を取得する前に短時間しかスピンしないケースをサポートする必要があります。後者の期待は、バージョンカウンタをインクリメントするたびにスリーパーをウェイクアップするために無条件にシステムコールを実行するだけでは遅すぎることを意味します。この問題は新しくなく、アダプティブスピンロックにデプロイされているものと同様の解決策があります。アダプティブロックの解決策パターンは、OSプリミティブ（例：futexes）との緊密な統合に依存しています。制御ワード（待機者がスピンするマシンワード）は、通常のデータ（この場合はバージョンカウンタ）と、OSシステムコールでウェイクアップされるべきスリーパーがいることを示す新しいフラグをエンコードします。制御ワードへのすべての書き込みはアトミックリード・モディファイ・ライト命令を使用し、スリープする前に、待機者は「スリーパーが存在する」フラグが設定されていることを確認し、制御ワードが期待通りであり、スリーパーフラグが設定されている場合にのみスリープするためのシステムコールを行います。 OpenBSDのLinuxのfutexes用の互換性シムは、futex呼び出しの実装としては最も単純なものです。futexのウェイクアップと待機のためのOSコードは、ユーザー空間がミューテックスと条件変数（waitqueues）で行うことと同一です。待機者は、futexワードまたはそれより粗いスーパーセットに対してウェーカーをロックアウトし、futexワードの値が期待通りであることを確認し、futexのwaitqueueに入ります。ウェーカーは書き込みのためにfutexワードを取得し、waitqueueをウェイクアップします。違いは、これらすべてがカーネル内で実行されることであり、任意のミューテックス/条件変数ペアとは異なり、カーネルはスケジューラに協力を強制できることです。futexコードはカーネルで実行できます。なぜなら、任意のミューテックス/条件変数ペアとは異なり、保護されたデータは常に単一のマシン整数であり、待機条件は等価テストだからです。このセットアップは、カーネルで完全に実装するには十分単純でありながら、有用であるには十分一般的です。OS支援の条件付きブロッキングは、イベントカウントに適合させるのに十分単純です。制御ワードはイベントc