クリティカルセクション

並行プログラミングでは、共有リソースへの同時アクセスは予期しない動作やエラーを引き起こす可能性があります。したがって、共有リソースがアクセスされるプログラム部分は、同時アクセスを回避する方法で保護する必要があります。その方法の 1 つは、クリティカルセクションまたはクリティカル領域と呼ばれます。この保護されたセクションには、一度に複数のプロセスまたはスレッドが入ることはできません。他のプロセスまたはスレッドは、最初のプロセスまたはスレッドがクリティカルセクションを離れるまで中断されます。通常、クリティカルセクションは、データ構造、周辺機器、ネットワーク接続などの共有リソースにアクセスしますが、これらのリソースは、複数の同時アクセスのコンテキストでは正しく動作しません。^[1]

クリティカルセクションの必要性

異なるコードまたはプロセスは、同じ変数または読み取りまたは書き込みが必要な他のリソースで構成されますが、その結果はアクションが発生する順序によって異なります。たとえば、変数xがプロセス A によって読み取られ、プロセス B が同時に変数xに書き込む必要がある場合、プロセス A はxの古い値または新しい値を取得する可能性があります。

プロセスA:

// プロセス A 
. 
. 
b = x + 5 ; // 命令は時刻 = Tx に実行されます。

プロセスB:

// プロセス B 
. 
. 
x = 3 + z ; // 命令は時刻 = Tx に実行されます。

より細かい粒度のロック機構が必要ない場合、クリティカルセクションは重要です。上記のケースでは、 A がxの更新された値を読み取る必要がある場合、プロセス A とプロセス B を同時に実行すると、必要な結果が得られない可能性があります。これを防ぐために、変数x はクリティカルセクションによって保護されます。まず、 B がセクションへのアクセスを取得します。 B が値の書き込みを完了すると、 A はクリティカルセクションへのアクセスを取得し、変数xを読み取ることができます。

クリティカルセクションの内外でどの変数が変更されるかを注意深く制御することで、共有変数への同時アクセスを防止できます。クリティカルセクションは通常、マルチスレッドプログラムが、別のスレッドがそのデータに競合する変更を加えることなく、複数の関連変数を更新する必要がある場合に使用されます。関連する状況では、クリティカルセクションを使用して、共有リソース (たとえば、プリンタ) に一度に 1 つのプロセスのみがアクセスできるようにすることができます。

クリティカルセクションの実装

クリティカルセクションの実装は、オペレーティングシステムによって異なります。

クリティカルセクションは通常有限時間で終了し、^[2]スレッド、タスク、またはプロセスはそこに入るために一定時間待機する必要があります (制限付き待機)。クリティカルセクションの排他的使用を保証するには、プログラムの入口と出口で何らかの同期メカニズムが必要です。

クリティカルセクションは、アクセスの相互排他を必要とするプログラムの一部です。

図^{[3]に示すように、相互排他（}ミューテックス）の場合、1つのスレッドが共有リソースにアクセスする必要があるときにロック技術を使用してクリティカルセクションをブロックし、他のスレッドはそのセクションに入る順番を待たなければなりません。これにより、2つ以上のスレッドが同じメモリ空間を共有し、共通のリソースにアクセスしたい場合に競合が防止されます。^[2]

クリティカルセクション内でプロセッサ制御が変更されるのを防ぐ最も簡単な方法は、セマフォを実装することです。ユニプロセッサシステムでは、クリティカルセクションに入るときに割り込みを無効にし、セクション内でコンテキストスイッチを引き起こす可能性のあるシステムコールを回避し、終了時に割り込みを以前の状態に復元することでこれを実現できます。この実装により、システム内のクリティカルセクションに入る実行スレッドは、元のスレッドがクリティカルセクションを離れるまで、割り込みを含む他のスレッドに CPU での処理時間が許可されないようにします。

このブルートフォースアプローチは、セマフォを使用することで改善できます。クリティカルセクションに入るには、スレッドはセマフォを取得する必要があります。セマフォは、セクションを出るときに解放されます。他のスレッドは、元のスレッドと同時にクリティカルセクションに入ることはできませんが、CPU の制御を取得して、別のセマフォによって保護されている他のクリティカルセクションを含む他のコードを実行することはできます。セマフォロックには、デッドロック状態を防ぐための時間制限もあります。デッドロック状態とは、ロックが 1 つのプロセスによって無限の時間取得され、クリティカルセクションによって保護されている共有リソースを使用する必要がある他のプロセスが停止する状態です。

クリティカルセクションの使用

カーネルレベルのクリティカルセクション

通常、クリティカルセクションは、プロセッサ間のスレッドとプロセスの移行、および割り込みや他のプロセスやスレッドによるプロセスとスレッドのプリエンプションを防止します。

クリティカルセクションでは、多くの場合、ネストが許可されます。ネストにより、複数のクリティカルセクションをほとんどコストをかけずに開始および終了できます。

スケジューラがクリティカルセクションで現在のプロセスまたはスレッドを中断する場合、スケジューラは現在実行中のプロセスまたはスレッドをクリティカルセクションの完了まで実行できるようにするか、プロセスまたはスレッドを別の完全なクォンタムにスケジュールします。スケジューラはプロセスまたはスレッドを別のプロセッサに移行せず、現在のプロセスまたはスレッドがクリティカルセクションにある間は別のプロセスまたはスレッドを実行するようにスケジュールしません。

同様に、クリティカルセクションで割り込みが発生した場合、割り込み情報は将来の処理のために記録され、クリティカルセクション内のプロセスまたはスレッドに実行が返されます。 ^[4]クリティカルセクションが終了し、場合によってはスケジュールされたクォンタムが完了すると、保留中の割り込みが実行されます。スケジューリングクォンタムの概念は、「ラウンドロビン」や同様のスケジューリングポリシーに適用されます。

クリティカルセクションは、それが入ったプロセッサ上でのみ実行されるため、同期は実行プロセッサ内でのみ必要です。これにより、クリティカルセクションへの出入りはほぼコストなしで行えます。プロセッサ間の同期は必要ありません。必要なのは命令ストリームの同期だけです。 ^[5]ほとんどのプロセッサは、現在の実行状態を中断することで、必要な量の同期を提供します。これにより、ほとんどの場合、クリティカルセクションは、プロセッサごとに入ったクリティカルセクションの数だけになります。

パフォーマンス強化には、すべてのクリティカルセクションの終了時に保留中の割り込みを実行することと、すべてのクリティカルセクションの終了時にスケジューラを実行できるようにする機能が含まれます。さらに、保留中の割り込みは、実行のために他のプロセッサに転送される場合があります。

クリティカルセクションは、長時間持続するロックプリミティブとして使用しないでください。クリティカルセクションは、ハードウェアやスケジューラからの割り込みが発生することなく、開始、実行、終了できるように、十分に短くする必要があります。

カーネルレベルのクリティカルセクションは、ソフトウェアロックアウト問題の基礎です。

データ構造の重要なセクション

並列プログラミングでは、コードはスレッドに分割されます。読み取りと書き込みが競合する変数はスレッド間で分割され、各スレッドにはそれらのコピーがあります。リンクリスト、ツリー、ハッシュテーブルなどのデータ構造には、リンクされたデータ変数があり、スレッド間で分割できないため、並列処理の実装は非常に困難です。^[6]データ構造の実装効率を向上させるために、挿入、削除、検索などの複数の操作を並列で実行できます。これらの操作を実行しているときに、同じ要素が1つのスレッドで検索され、別のスレッドによって削除されるシナリオが発生する可能性があります。このような場合、出力が誤っている可能性があります。要素を検索しているスレッドはヒットする可能性がありますが、他のスレッドはその後それを削除する可能性があります。これらのシナリオは、誤ったデータを提供することで、プログラムの実行中に問題を引き起こします。これを防ぐ方法の1つは、データ構造全体をクリティカルセクションの下に保持し、一度に1つの操作のみが処理されるようにすることです。もう1つの方法は、クリティカルセクションの下で使用中のノードをロックし、他の操作が同じノードを使用しないようにすることです。したがって、クリティカルセクションを使用すると、コードが期待どおりの出力を提供することが保証されます。^[6]

周辺機器に関する重要なセクション

クリティカルセクションは、I/O デバイスなどの外部周辺機器を操作するコードでも発生します。周辺機器のレジスタは、特定の順序で特定の値にプログラムする必要があります。2 つ以上のプロセスが同時にデバイスを制御すると、どちらのプロセスもデバイスを必要な状態にすることができず、誤った動作が発生します。

複数の出力操作を発行して出力デバイス上に複雑な情報単位を生成する必要がある場合、別のプロセスが独自の出力ビットをインターリーブしてデータを破損しないように、排他的アクセスが必要です。

入力方向では、複数の個別の入力操作を介して複雑なデータを読み取るときに排他的アクセスが必要です。これにより、別のプロセスがデータの一部を消費して破損が発生するのを防ぎます。

ストレージデバイスは、メモリの形式を提供します。クリティカルセクションの概念は、メインメモリ内の共有データ構造と同様に、ストレージデバイスにも関連しています。ファイルに対して複数のアクセスまたは更新操作を実行するプロセスは、適切なファイルロックメカニズムで保護する必要があるクリティカルセクションを実行しています。

参照

参考文献

^ Raynal, Michel (2012).並行プログラミング: アルゴリズム、原理、基礎. Springer Science & Business Media. p. 9. ISBN 978-3642320279。
^ ab Jones, M. Tim (2008). GNU/Linux アプリケーションプログラミング (第 2 版). [マサチューセッツ州ヒンガム] Charles River Media. p. 264. ISBN 978-1-58450-568-6。
^ Chen、Stenstrom、Guancheng、Per (2012 年 11 月 10 ～ 16 日)。「クリティカルロック分析: マルチスレッドアプリケーションにおけるクリティカルセクションのボトルネックの診断」。2012国際高性能コンピューティング、ネットワーキング、ストレージ、分析会議。pp. 1 ～ 11。doi : 10.1109/ sc.2012.40。ISBN 978-1-4673-0805-2. S2CID 12519578。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
^ 「クリティカルセクション問題のソフトウェアソリューションに関する研究論文」。国際先端技術工学研究ジャーナル (IJATER)。1 。2011 年11月。
^ Dubois、 Scheurich 、Michel、Christoph (1988)。「マルチプロセッサにおける同期、一貫性、およびイベント順序付け」。調査およびチュートリアルシリーズ。21 ( 2): 9–21。doi :10.1109/2.15。S2CID 1749330。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
^ ab Solihin, Yan (2015 年 11 月 17 日)。並列マルチコアアーキテクチャの基礎。Taylor & Francis。ISBN 9781482211184。

外部リンク

Microsoft Docs Web ページのクリティカルセクションのドキュメント
クリティカルセクションのチュートリアル
Mutex のコード例
セマフォのチュートリアル
クリティカルセクションでのロック競合

[1] Raynal, Michel (2012).並行プログラミング: アルゴリズム、原理、基礎. Springer Science & Business Media. p. 9. ISBN 978-3642320279。

[:0-2] Jones, M. Tim (2008). GNU/Linux アプリケーションプログラミング (第 2 版). [マサチューセッツ州ヒンガム] Charles River Media. p. 264. ISBN 978-1-58450-568-6。

[3] Chen、Stenstrom、Guancheng、Per (2012 年 11 月 10 ～ 16 日)。「クリティカルロック分析: マルチスレッドアプリケーションにおけるクリティカルセクションのボトルネックの診断」。2012国際高性能コンピューティング、ネットワーキング、ストレージ、分析会議。pp. 1 ～ 11。doi : 10.1109/ sc.2012.40。ISBN 978-1-4673-0805-2. S2CID 12519578。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[4] 「クリティカルセクション問題のソフトウェアソリューションに関する研究論文」。国際先端技術工学研究ジャーナル (IJATER)。1 。2011 年11月。

[5] ^ Dubois、 Scheurich 、Michel、Christoph (1988)。「マルチプロセッサにおける同期、一貫性、およびイベント順序付け」。調査およびチュートリアルシリーズ。21 ( 2): 9–21。doi :10.1109/2.15。S2CID 1749330。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[:1-6] Solihin, Yan (2015 年 11 月 17 日)。並列マルチコアアーキテクチャの基礎。Taylor & Francis。ISBN 9781482211184。