オペレーティング システムの同期プリミティブの包括的な分析
- 不言オリジナル
- 2018-09-17 15:27:271452ブラウズ
この記事は、オペレーティング システムの同期プリミティブの包括的な分析を提供します。必要な方は参考にしていただければ幸いです。
競合状態
一般的なオペレーティング システムでは、さまざまなプロセスがハードディスク上のメモリやファイルなどの共通の記憶域を共有することがあり、これらのプロセスはこれらの領域で実行できます。そして書き続けます。
オペレーティング システムには、共通領域を使用してプロセスを調整し、目的の操作を正しい方法で実行する責任があります。これらのプロセスは相互に通信し、あるプロセスのアクションが別のプロセスの通常のアクションに影響を与えないようにするために議論する必要があります。その結果、プロセスの実行後に期待した結果が得られなくなります。オペレーティング システムの概念では、通常、複数のプロセス間の通信を表すために IPC (Inter Process Communication) という用語が使用されます。
競合状態とは何かを説明するために、簡単な例を紹介します。
数値 n がファイルに格納されており、プロセス A とプロセス B の両方がこのファイルを読み取りたい場合、1 を加えます。この番号に変更し、ファイルに保存し直します。 n の初期値が 0 であると仮定すると、理想的なケースでは、プロセス A とプロセス B の実行後、ファイル内の n の値は 2 になるはずですが、実際には n の値が 1 になる可能性があります。これを行うときに、各プロセスがどのような手順を実行する必要があるかを検討できます。
ファイル内の n の値を読み取ります。
n = とします。 n 1
新しい n 値をファイルに保存し直します。
競合状態について詳しく説明する前に、まずオペレーティング システムの概念に関するいくつかの知識ポイントを確認する必要があります。
プロセスは (競合状態であっても) 同時に実行できます。は 1 つの CPU のみです)
オペレーティング システムのクロック割り込みにより、プロセスが再スケジュールされます。
クロック割り込みに加えて、 , 他のデバイスからの割り込みによってもプロセスの再スケジュールが発生します
プロセス A がステップ 1 と 2 の実行を終了したが、まだステップ 3 の実行を開始していないときに、クロック割り込みが発生したとします。このとき、オペレーティング システムはプロセス B の実行を開始するようにスケジュールします。プロセス B がステップ 1 を実行すると、n の値が 0 であることがわかり、ステップ 2 と 3 を実行し、最終的に n = 1 をファイルに保存します。プロセス A がその後も実行を続ける場合、ステップ 3 を実行する前にプロセス B がファイル内の値を変更したことを認識していないため、プロセス A も n = 1 をファイルに書き戻します。これが問題です。プロセス A の実行中、他のプロセスはそのプロセスが操作するデータを操作します。
n = 2 にする唯一の方法は、プロセス A とプロセス B がすべてのステップを順番に完了することを期待することです。 競合状態を定義できます。
上記の例を例に挙げると、ステップ 1 ～ 3 のプログラム フラグメントをクリティカル セクションとして定義できます。クリティカル セクションは、プロセスがこの領域に到達するとパブリックになることを意味するため、この領域が機密であることを意味します。データが領域またはファイルを操作しているということは、他のプロセスがクリティカル セクションで実行されている可能性があることも意味します。 2 つのプロセスが同時にクリティカル セクションに入らないように適切な措置を講じれば、競合状態を回避できます。
つまり、「相互排他」をどう実現するかを考える必要があるのです。
マスク割り込み
前述の例で、プロセス B がクリティカル セクションに入ることができたのは、プロセス A がクリティカル セクションで割り込まれたためです。プロセス A に、クリティカル セクションに入った直後にすべての割り込みをマスクし、クリティカル セクションを出た後にのみ割り込みに応答するように依頼すると、割り込みが発生しても CPU は他のプロセスに切り替わらないため、プロセス A は安全にプロセスを変更できます。他のプロセスがその作業を妨げることを心配することなく、ファイルの内容を確認できます。
しかし、このアイデアは美しいですが、実際には実現可能ではありません。まず、複数の CPU がある場合、プロセス A は他の CPU への割り込みをマスクできません。そのため、他の CPU によってスケジュールされたプロセスは引き続きクリティカル セクションに入ることができます。次に、電力についての質問です。ユーザープロセスに与えられるブロック割り込みの数は?このプロセスが割り込みをマスクし、割り込みに応答しない場合、プロセスがオペレーティング システム全体をハングさせる可能性があります。
ロック変数
ロック フラグを設定して、初期値を 0 に設定できるかもしれません。プロセスがクリティカル セクションに入りたいときは、まずロックの値が 0 であるかどうかを確認します。 0 の場合は 1 に設定し、クリティカル セクションに入り、クリティカル セクションを抜けた後にロックの値を 0 に変更します。チェック時にロックの値がすでに 1 である場合は、他のプロセスがロックされていることを意味します。すでにクリティカル セクションに入っているため、プロセスは Wait をループし、ロック値が 0 になるまでチェックし続けます。
しかし、このメソッドには競合状態もあります。その理由は、プロセスがロックの値を 1 に設定する前に、ロックの値を 0 として読み取ると、別のプロセスがスケジュールされ、ロックの値も読み取るためです。 lock が 0 であるため、両方のプロセスが同時にクリティカル セクションにある状況が発生します。
厳密なローテーション方法
ロック変数に問題がある理由は、実際には、ロック変数を 0 から 1 に変更するアクションが、ロック変数を取得したいプロセスによって実行されるためです。ロック。このアクションをロックを取得したプロセスによって実行されるように変更すると、競合状態は発生しなくなります。
まず、現在ロックを取得できるユーザーを表す変数turnを設定します。プロセスAのロジックは次のとおりです。
while (turn != 0){// 如果还没轮到自己获取锁，则进入循环等待
}
do_critical_region();// 执行临界区的程序
turn = 1;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
do_non_critical_region();// 执行非临界区的程序
プロセスBのロジックは次のとおりです。 :
while (turn != 1) {// 如果还没轮到自己获取锁，则进入循环等待
}
do_critical_region();// 执行临界区的程序
turn = 0;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
do_non_critical_region();// 执行非临界区的程序
しかし、ここで考慮する必要があることが 1 つあります。プロセス A の do_non_critical_region() を長時間実行する必要があるとします。つまり、プロセス A の非クリティカル領域のロジックです。プロセス B の非クリティカル領域のロジックは、実行後すぐに実行されますが、プロセス A がプロセス B よりもクリティカル セクションに入る頻度が低いことは明らかです。理想的には、プロセス B は、クリティカルセクションにさらに数回入る必要があります。しかし、プロセスBは非クリティカルセクションのロジックを実行する前にturnを0に設定するため、すぐに非クリティカルセクションのロジックを実行した後、戻ってturnの値を確認すると、ターンの値が 1 になったことはありません。この値を使用するにはプロセス A が 1 に設定する必要がありますが、プロセス A は現在長い非クリティカル セクションのロジック コードを実行しているため、プロセス B はクリティカル セクションに入ることができません。
これは、あるプロセスが別のプロセスよりもはるかに遅い場合、厳密なローテーションが得策ではないことを示しています。
ピーターソン アルゴリズム
厳密なローテーション方法の問題は、厳密という言葉にあります。つまり、複数のプロセスが順番にクリティカル セクションに入るということです。根本的な理由は、プロセスが、ロック変数を変更するには他のプロセスに依存する必要があり、他のプロセスはロック変数を変更する前に最初に非クリティカル セクション ロジックを実行する必要があります。
厳密なローテーション方式のターン変数は、ロックを取得する順番を示すために使用されるだけでなく、その値が変更される前に、他のプロセスがクリティカル セクションに入るのを防ぐことも意味します。プロセスでは常に、turn の値は非クリティカル セクションのロジックを通過した後にのみ変更されます。
したがって、2 つの変数を使用してそれを表すことができます。1 つの変数は現在ロックを取得する順番を表し、もう 1 つの変数は現在のプロセスがクリティカル セクションを離れたことを表します。このメソッドは実際には Peterson アルゴリズムと呼ばれます。 、オランダの数学によって開発され、T. Dekker によって提案されました。
static final int N = 2;
int turn = 0;
boolean[] interested = new boolean[N];
void enter_region(int process) {
int other = 1 - process;
interested[process] = true;
turn = process;
while(turn == process && !interested[other]) {
}
}
void exit_region(int process) {
interested[process] = false;
}
プロセスがクリティカル セクションに入る必要がある場合、最初に enter_region を呼び出し、クリティカル セクションを出た後、exit_region を呼び出します。 Peterson のアルゴリズムにより、プロセスはクリティカル セクションを出た後、クリティカル セクションへの「関心」を即座に排除するため、他のプロセスはターンの値に基づいてクリティカル セクションに合法的に入ることができるかどうかを判断できます。
TSL 命令
#前に述べた「ロック変数」メソッドを思い出してください。その致命的な欠点の 1 つは、状態変数を 0 から 1 または 1 に変更するときです。割り込みによって中断されるため、競合状態が発生します。
その後、ロック変数に基づいて、ロック変数の変更がクリティカル セクションに入りたいプロセスによって変更されるのではなく、クリティカル セクションに入った後にクリティカル セクションから出ようとするプロセスによって変更される場合を提案しました。クリティカル セクションに到達すると、競合状態を回避できます。これにより、厳密な回転方法が使用され、ピーターソン アルゴリズムは厳密な回転方法に基づいて改良されます。これらの方法はすべてソフトウェアの観点から検討されています。実際、ハードウェア CPU のサポートにより、ロック変数の変更が中断されないようにすることができるため、ロック変数はプロセスの相互排他を解決する優れた方法になります。
現在のコンピュータ CPU のほとんどは、Test and Set Lock と呼ばれる TSL 命令をサポートしています。これは、メモリ変数 (ワード) をレジスタ RX に読み取り、メモリ アドレスに 0 以外の値を格納します。操作と書き込み操作は、ハードウェア レベルで中断できないことが保証されています。つまり、アトミックです。この手法は、TSL 命令の実行時にメモリ バスをロックし、TSL 命令が終了する前に他の CPU がメモリにアクセスすることを禁止します。これは、私たちがよく CAS (Compare And Set) と呼ぶものでもあります。
ロック変数を 0 から 1 に変更する必要がある場合、まずメモリ値をレジスタにコピーし、メモリ値を 1 に設定してから、レジスタ値が 0 であるかどうかを確認します。0 であれば、動作は次のようになります。 0 以外の場合は、レジスタ値が 0 になるまで検出を繰り返します。レジスタ値が 0 になった場合は、別のプロセスがクリティカル セクションから離脱したことを意味します。プロセスがクリティカル セクションを離れるときは、メモリ内のこの変数の値を 0 に設定する必要があります。
ビジー ウェイティング
上記の Peterson アルゴリズムと TSL メソッドには、実際には 1 つの特徴があります。それは、クリティカル セクションに入るのを待つときに、ビジー ウェイティング (私たちでもよく呼びます) を使用することです。スピン。欠点は、CPU タイム スライスを無駄にし、優先順位逆転の問題を引き起こす可能性があることです。
2 つのプロセスを持つコンピューターを考えてみましょう。H の優先順位が高く、L の優先順位が低くなります。スケジューリング ルールでは、H が準備完了状態にある限り実行できると規定されています。ある瞬間、L はクリティカル領域にあり、H は準備完了状態で実行の準備ができています。しかし、H は待機する必要があり、L は優先度が低いためスケジュールできず、したがってクリティカル セクションから離れることができません。したがって、H は永遠に待機することになり、L は決してクリティカル セクションから離れることができません。この状況は、優先順位逆転問題(優先順位逆転問題)と呼ばれます。
プロセスのブロックとウェイクアップ
オペレーティング システムには、スリープとウェイクアップといういくつかのプリミティブが用意されています。
コア外部の呼び出しに対してカーネルによって提供されるプロセスまたは関数はプリミティブになり、プリミティブでは実行中の中断は許可されません。
sleep は、別のプロセスが wakeup メソッドを呼び出すまで呼び出しプロセスをブロックするシステム コールで、ブロックされたプロセスをパラメータとして受け取り、ウェイクアップします。ブロックとビジー待機の最大の違いは、プロセスがブロックされた後は CPU がタイム スライスを割り当てないのに対し、ビジー待機は常にアイドル状態になり、CPU のタイム スライスを消費することです。
セマフォ
最初に理解する必要があるのは、プロセスのブロックと覚醒は別のプロセスで発生するため、セマフォがどのような問題を解決するかということです。たとえば、プロセス A は sleep() を呼び出します。ブロッキングに入り、プロセス B の wakeup(A) 呼び出しによってプロセス A が起動されます。別工程で行われるため、中断の問題もある。ロジックによれば、プロセス A は、sleep() を呼び出してブロッキング状態に入る必要がありますが、クロックの中断により、プロセス B が実行を開始します。 wakeup() メソッドを呼び出してプロセス A をウェイクアップしますが、プロセス A がまだブロッキング状態に入っていないため、プロセス A が以前に中断された位置から実行を続けてブロッキングに入ると、ウェイクアップ信号が失われ、どのプロセスもウェイクアップできなくなります。それをアップします。
したがって、プロセスのブロックと覚醒には、追加の変数を導入して記録する必要があります。この変数は、覚醒の回数を記録するたびに、変数の値が 1 ずつ増加します。この変数を使用すると、ウェイクアップ操作がスリープ操作よりも先に行われた場合でも、プロセスがスリープ状態になると、他のプロセスがすでにウェイクアップしているため、プロセスはブロッキングに入る必要がないと見なされます。州。
この変数は、オペレーティング システムの概念ではセマフォと呼ばれ、1965 年にダイクストラによって提案された方法です。
セマフォには、ダウンとアップの 2 つの操作があります。
ダウン操作は実際にはスリープに対応します。まず、セマフォの値が 0 より大きいかどうかを検出します。0 より大きい場合は、1 ずつ減分します。この時点でプロセスをブロックする必要はありません。これはウェイクアップを消費することと同じであり、セマフォが 0 の場合、プロセスはブロッキング状態になります。
アップ操作はウェイクアップに対応します。アップ操作後、このセマフォでプロセスがブロックされていることが判明した場合、システムはプロセスの 1 つを選択してそのセマフォをウェイクアップします。変更する必要はありませんが、すでにブロックされています。アップ操作中にセマフォでブロックされているプロセスがない場合は、セマフォの値が 1 増加します。
一部の場所では、ダウン操作とアップ操作を PV 操作と呼びます。これは、ダイクストラの論文では、それぞれダウンとアップを表すために P と V が使用されているためです。
セマフォのダウン操作とアップ操作はオペレーティング システムによってサポートされる基本的な操作であり、中断されません。
Mutex
Mutex (ミューテックス) は実際にはセマフォの特殊なケースで、その値は 0 と 1 のみです。 セマフォのカウント機能を使用する必要がない場合は、これは、実際には、クリティカル セクション値では 1 つのプロセスのみが同時に入ることができるのに対し、セマフォでは複数のプロセスが同時にクリティカル セクションに入ることができることを意味します。
以上がオペレーティング システムの同期プリミティブの包括的な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。