技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

2024-07-04: オペレーティング システムの同期と相互排他に関する研究メモ

---

同時プロセスまたはプログラムは、実行時にクロージャを失います。つまり、2 つのプログラムが別々の領域で共有リソースを使用する場合、それぞれの実行結果が異なる可能性があります。

その理由は、プログラム a とプログラム b の両方がアクセスする必要がある共有リソース x を保護していないためです。

---

9.1 同期と相互排除の基本概念

9.1.1 同期関係

相互に制限的な関係が同期です。同期を簡単に理解すると、プロセスの実行には順序が必要です。

---

9.1.2 相互排他関係

間接的に相互に制限する関係は、相互排他関係と呼ばれます。

---

9.1.3 重要なリソース

• 一定期間内に 1 つのプロセスのみがアクセスを許可されるリソースは、クリティカル リソース (または排他的リソース) と呼ばれます。
• 重要なリソースを共有するには、プロセス間で相互排他を使用する必要があります。

「生産者と消費者モデル」
カウンター+ +

首先把变量放到寄存器里面
register1 = counter;
接下来对寄存器进行一个自增
register1 = register1 + 1;
再把结果返回到counter里
counter = register1;
1
2
3
4
5
6

カウンター- -

首先把变量放到寄存器里面
register2 = counter;
接下来对寄存器进行一个自减
register2 = register2 - 1;
再把结果返回到counter里
counter = register2;
1
2
3
4
5
6

解決策: counter を重要なリソースとして扱い、プロセスが変数 counter に相互にアクセスできるようにします (同期メカニズムについては後で学びます)

---

9.1.4 クリティカルセクション

ハードウェアクリティカルなリソースであっても、ソフトウェアクリティカルなリソースであっても、複数のプロセスが相互にアクセスする必要があります。

これらの領域は本質的にコードです

• エントリーエリア
• クリティカルセクション
• 出口エリア
• 残りの領域

---

9.1.5 同期メカニズムはルールに従う必要がある

• 出入り自由

クリティカル セクションにプロセスが存在しない場合は、クリティカル セクションのリソースがアイドル状態であることを示します。リソースを効果的に利用するために、クリティカル セクションへの参加を要求するプロセスは、すぐに自身のクリティカル セクションへの参加を許可される必要があります。

• 忙しいなら待っててね

既存のプロセスがクリティカル セクションに入ると、クリティカル リソースにアクセス中であることを示します。そのため、クリティカル セクションに入ろうとする他のプロセスは、クリティカル リソースへの相互排他的なアクセスを確保するために待機する必要があります。

• 待ち時間が限られている

クリティカルなリソースへのアクセスが必要なプロセスの場合、「待機中」状態に陥るのを避けるために、限られた時間内にプロセスが独自のクリティカル セクションに入ることができるようにする必要があります。

• 道を譲って待つ

プロセスが自身のクリティカル セクションに入ることができない場合、プロセスが「ビジー待機」状態に陥るのを防ぐために、プロセッサ (CPU) を直ちに解放する必要があります。

---

9.2 ソフトウェア同期メカニズム

9.2.1 シングルマーク方式

• クリティカル セクションにプロセスが存在するかどうかを示すパブリック整数変数を設定します。クリティカル セクションにプロセスがすでに存在する場合、プロセスがクリティカル セクションを出た後、フラグが設定されてループ チェックが行われます。出口エリアで変更されます。
• シングルフラグ方式では、公開整数変数turn を設定して、turn=0 の場合、クリティカル セクションに入ることが許可されるプロセス番号を指定します。
• turn=1 の場合、プロセス P1 はクリティカル セクションへの進入を許可され、クリティカル セクションから出る際に、クリティカル セクションの使用権が別のプロセスに与えられます (Pi がクリティカル セクションから出る場合は、turn=j とします)。

两个进程必须交替进入临界区，若一个进程不再进入临界区，则另一个进程也无法进入临界区，违背了“空闲让进”准则

---

9.2.2 ダブルマークファーストチェック方法

ダブルフラグファーストチェックメソッドは、各プロセスがクリティカルセクションに入ろうとしていることをマークするブール配列 flag[2] を設定します。 flag[i]=true は、Pi がクリティカルセクションに入ろうとしていることを意味します。

• Piがクリティカルセクションに入る前に、まず相手がクリティカルセクションに入っているかどうかを確認し、入っている場合は待ちます。
• それ以外の場合は、クリティカル セクションに入る前に flag[i] を true に設定します。
• Pi がクリティカル セクションを出るとき、flag[i] を false に設定します。

• while ループは信号機のメカニズムに相当します
• 相手側のフラグを立てることは、相手側の信号機を変更することと同じです。
• ただし、両方のプロセスが最初にフラグをチェックし [最初に信号機を確認] し、最初は両方とも false (両方の信号が青) であるため、2 つのプロセスが同時に信号機を通過し、クリティカル セクションに一緒に入る可能性があります。 。

---

9.2.3 ダブルマーク事後検査方法

ダブルフラグポストチェック方式では、相手のフラグをチェックしてから自分のフラグを設定します。この 2 つの操作は一度に実行できないため、2 つのプロセスが同時にクリティカル セクションに入る可能性があります。まず自分のフラグを立ててから相手のフラグを確認し、相手のフラグがtrueの場合は待機し、クリティカルセクションに入るという方法が考案されました。

---

9.2.4 ピーターソンアルゴリズム

Peterson のアルゴリズムは次のことを組み合わせます。シングルマーク方式そしてダブルマーク事後チェック方法このアイデアは、flag[] を使用して相互排他的アクセスの問題を解決し、turn を使用して飢餓問題を解決することです。

両方の当事者がクリティカル セクションに入るために競合している場合、プロセスは他の当事者にクリティカル セクションに入る機会を与えることを許可できます。
各プロセスはクリティカルセクションに入る前に、自身のフラグを設定し、その後、相手のフラグを検出し、同時にターンを行うことで、1 つのプロセスのみがクリティカルセクションに入ることができるようにします。双方が同時にクリティカルセクションへの入力を要求します。

待つ権利を放棄しないこと

---

9.3 ハードウェア同期メカニズム

クリティカルセクションへの各プロセスの相互排除の問題をソフトウェアで解決することは困難であり、そのため、コンピュータはこの問題を解決するためにいくつかの特別なハードウェア命令を提供します。

9.3.1 割り込みをオフにする

(1) 割り込みオフの定義

• 割り込みをオフにすることは、CPU の PSW レジスタのビットを変更することを指します。このビットは、現在の CPU が対応する割り込みにのみ応答するかどうかを制御します。アンマスカブル割り込みは停止できない
• オペレーティング システムにおけるプロセスのスケジューリングは、クロック割り込みなどの割り込みに依存します。
• クリティカル セクションでのプロセスの実行中、コンピュータ システムは割り込みをシャットダウンします。これにより、スケジューリングはトリガーされず、プロセスやスレッドの切り替えは行われません。

(2) 割り込みオフのデメリット

• 端末の誤用は重大な結果を招く可能性があります
• シャットダウン時間が長すぎると、システムの効率に影響します。
• 割り込みをオフにする方法は、マルチ CPU システムには適用されません。1 つのプロセッサで割り込みをオフにしても、プロセスが他のプロセッサで同じ重要なコードを実行することは妨げられません。

---

9.3.2 テストアンドセットコマンド（TSコマンド）

ＴＳ命令は、実行過程が分割不可能な関数処理（プリミティブ）とみなすことができる。

• ロックには 2 つの状態があります。
• • *lock=FALSE はリソースが空いていることを示します
• • *lock=TRUE はリソースが使用されていることを示します

TS を使用して重要なセクションを管理し、各重要なリソースにロックを設定します。

• 初期値は FALSE で、重要なリソースがアイドル状態であることを示します。
• プロセスはクリティカル セクションに入る前に、まず TS を使用してロックをテストします。ロックが FALSE の場合は、ロックに TRUE 値を割り当てて、クリティカル リソースを閉じます。

---

9.3.3 スワップコマンド

これはスワップ命令と呼ばれ、2 つのワードの内容を交換するために使用されます。

• 初期値 FALSE を使用して、重要なリソースごとにグローバル ブール変数ロックを設定します。
• 上記のハードウェア命令を使用して、プロセスの相互排他を完了します。
• ただし、この方法では、アクセス プロセスが継続的にテストされ、「ビジー待機」状態になるため、「右待機」の原則に準拠しません。

---

9.4 セマフォ機構

9.4.1 整数セマフォ

これは、リソースの数を表すために使用される整数 S として定義されます。この整数セマフォには、初期化 (初期値の割り当て)、待機 (デクリメント)、シグナル (インクリメント) の 3 つの操作しかありません。

• wait と signal はどちらもアトミックな操作であり、実行中に中断することはできません。
• プロセスがセマフォを変更するとき、他のプロセスは同時にセマフォを変更できません。

---

9.4.2 レコードセマフォ

「ビジー待機」現象のないプロセス同期メカニズム

• リソースの数を表すために使用される整変数値に加えて
• また、リソースを待っているすべてのプロセスをリンクするプロセスリンクリスト L を追加する必要があります。

• wait 操作は P 操作と同等です。
• 信号操作はV操作と同等です。
• 名前が違うだけで機能は全く同じです
• 待つ(A) = P(A)
• 信号(B) = V(A)

---

(1) セマフォを利用してプロセス相互排他を実現

相互に排他的なセマフォ mutex=1 を設定し、重要なリソースにアクセスする各プロセスのクリティカル セクションを wait(mutex) と signal(mutex) の間に配置します。

---

(2) セマフォを使用してプロセスの同期を実現する

同期セマフォ S=0 を設定して、最初に実行する必要があるステートメントのシグナル (S) が実行され、次に待機 (S) が実行されるようにします。