セマフォとは何ですか？
1. 序章
このチュートリアルでは、強力でよく知られているプロセス同期ツールであるセマフォについて詳しく説明します。
セマフォの操作、タイプ、およびその実装について見ていきます。 次に、セマフォを使用すると、発生する可能性のあるプロセス同期の問題を克服するのに役立つマルチスレッドのケースについて説明します。
2. セマフォとは何ですか？
セマフォは整数変数であり、複数のプロセス間で共有されます。 セマフォを使用する主な目的は、並行環境での共通リソースのプロセス同期とアクセス制御です。
セマフォの初期値は、目前の問題によって異なります。 通常、利用可能なリソースの数を初期値として使用します。 次のセクションでは、さまざまなユースケースでセマフォを初期化する例をさらに示します。
ビジーウェイトを必要としない同期ツールです。 したがって、リソースへのアクセスが不足しているためにプロセスが動作できない場合でも、オペレーティングシステムはCPUサイクルを浪費しません。
2.1. セマフォ操作
セマフォには、2つの不可分（不可分）操作、つまりとがあります。これらの操作は、および、または、または一部のコンテキストではと呼ばれることもあります。
この記事では、オペレーティングシステムカーネルに実装されているセマフォに焦点を当てましょう。 したがって、および操作はシステムコールとして実装されます。
セマフォとします。その整数値は、使用可能なリソースの量を表します。 次に、操作がどのように機能するかを調べてみましょう。
The
次に、操作を調べてみましょう。
リソースを待機している他のプロセスがない場合、操作はSを増分します。 それ以外の場合は、値をインクリメントする代わりに、オペレーティングシステムスケジューラによってウェイクアップされる待機中のプロセスが選択されます。 その結果、そのプロセスがリソースの制御を取得します。
2.2. セマフォタイプ
セマフォには次の2つのタイプがあります。
- バイナリセマフォ
- セマフォを数える
バイナリセマフォは、0または1の2つの整数値のみを持つことができます。実装が簡単で、相互排除を提供します。 バイナリセマフォを使用して、クリティカルセクションの問題を解決できます。
一部の経験豊富な読者は、バイナリセマフォを ミューテックス。 それらは交換可能に使用できるという一般的な誤解があります。 しかし実際には、セマフォはシグナリングメカニズムであり、一方、ミューテックスはロックメカニズムです。 したがって、バイナリセマフォはミューテックスではないことを知っておく必要があります。
カウントセマフォも整数値であり、無制限のドメインにまたがることができます。これを使用して、リソース割り当てなどの同期の問題を解決できます。
3. セマフォの実装
上記のように、オペレーティングシステムカーネルに実装されているセマフォに焦点を当てています。
ビジー待機のない実装には、整数値（セマフォ値を保持するため）と待機リスト内の次のプロセスへのポインターが必要です。リストは、操作でスリープ状態になるプロセスで構成されます。 カーネルは2つの追加操作を使用します：と、プロセスをコマンドします。
複数のプロセスが同時にセマフォ変数にアクセスする必要がないため、セマフォの実装はクリティカルセクションの問題と考えることができます。
いくつかのプログラミング言語は、並行性とセマフォをサポートしています。 たとえば、 Javaはセマフォをサポートしており、マルチスレッドプログラムでそれらを使用できます。
4. プロセスの同期
マルチスレッド環境では、プロセスの同期とは、並行プロセスによるシステムリソースの効率的な共有を意味します。 同期された実行を保証するには、共有データを使用するプロセスを調整する方法が必要です。 満足のいく同期メカニズムは、デッドロックと飢餓を回避することに加えて、並行性を提供します。
注意深く使用すると、セマフォはプロセスの同期を可能にする強力な同期ツールです。 次に、いくつかの問題にどのように対処できるかを調べてみましょう。
4.1. デッドロックの回避
デッドロックは、プロセスのグループが他のメンバーのアクションを待機している状態でブロックされた場合に発生します。 デッドロックの可能性を回避するには、セマフォの実装方法に注意する必要があります。 デッドロックのケースを調べてみましょう。
ここに、個別に実行する必要のあるコードがいくつかあります。
wait（）を実行し、その直後に割り込みをかけた場合を考えてみましょう。 次に、実行を開始するとします。 最初はセマフォを待機し、次にwait（）ステートメントでブロックされるため、スリープ状態になります。
カーネルが再び実行されると、次の操作が待機しています（）。 セマフォはすでにによって使用されているため、両方のプロセスが互いに待機している状況になり、デッドロックが発生します。
いずれかのプロセスで行の順序を逆にし、共通の順序を使用する場合、この例ではデッドロックを省略します。
4.2. 飢餓の回避
私たちが注意しなければならない次の概念は飢餓です。
有名な飢餓の例は、食事する哲学者の問題です。これについては、次のセクションで説明します。 この問題では、5人の哲学者が円形のテーブルの周りに座っています。 彼らは5本の箸を共有しています。 各哲学者は考えるか食べるかのどちらかです。 哲学者が食べるには、2本の箸が必要です。
この架空の問題は飢餓を象徴しています。 箸へのアクセスがないために哲学者のプロセスが永久にブロックされると、それは飢えます。
プロセスの同期を使用して、各プロセスが遅かれ早かれサービスを受けるようにします。
4.3. 優先順位の逆転
セマフォの非効率的な使用によって引き起こされる可能性のある別の考えられる問題は、優先順位の逆転です。 優先順位の逆転は、優先順位の低いジョブが優先順位の高いジョブよりも優先される場合に発生します。
優先度の低いプロセスが、優先度の高いプロセスで必要とされるセマフォを保持していると想像してみましょう。 さらに、中優先度のプロセスがスケジューラキューでも待機していると想定します。
この場合、カーネルは優先度の低いプロセスをスケジュールせず、優先度の高いプロセスをブロックします。 代わりに、カーネルは中優先度のジョブを続行し、高優先度のジョブを待機させ続けます。
考えられる解決策は、セマフォで優先度継承を使用することです。
5. 動作中のセマフォ
セマフォとは何かを定義したので、セマフォのいくつかのユースケースを調べてみましょう。
5.1. クリティカルセクションの問題
上記の例では、クリティカルセクションアクセスでの相互排除を保証しています。
ビジー待機の代わりに、待機プロセスはクリティカルセクションの順番を待っているためスリープ状態になっています。
次に、シグナル操作が実行され、カーネルはスリープ状態のプロセスをレディキューに追加します。 カーネルがプロセスを実行することを決定した場合、カーネルはクリティカルセクションに進みます。
このようにして、常に1つのプロセスのみがクリティカルセクションにあることを確認します。
5.2. 注文実行中
前にコードフラグメントを実行したいとします。言い換えると、：の実行が完了するまで実行する前に待機したいとします。
初期値を0に設定したセマフォを使用することで、この問題を簡単に克服できます。 コードを変更してみましょう：
セマフォを使用することにより、セクションの実行前に、の実行が完了するまで待機することが保証されます。
5.3. 生産者/消費者問題
次に、よく知られている生産者/消費者問題について考えてみましょう。 この問題では、セルで構成される限られたバッファーがあります。つまり、バッファーは最大の要素を格納できます。
この問題を克服するために、完全なセルの数を表すカウントセマフォを使用します。
最初は、。 プロデューサーがアイテムをバッファーに入れると、シグナル操作によってセマフォが増加します。 逆に、消費者がアイテムを消費すると、待機操作によってセマフォが減少します。
コンシューマーがバッファー内の最後のアイテムを使用すると、最後の待機操作によってスリープ状態になります。
5.4. 制限付きバッファプロデューサー-コンシューマーの問題
上記のソリューションに加えて、さらに2つのセマフォを追加することで、バッファーがいっぱいの場合にプロデューサーを強制的にスリープ状態にすることができます。バッファー内の使用可能なセルの数を表すセマフォを導入するとします。 また、バッファ内の完全なセルの数を表すセマフォを紹介します。 この場合、バッファでセマフォを使用します。 この場合も、プロデューサープロセスとコンシューマープロセスは同時に実行されます。
セマフォを含めるようにプロデューサーコードとコンシューマーコードを変更します。
ここで、カウントセマフォは完全なセルの数を表し、カウントセマフォは制限されたバッファで使用可能なセルの数を表します。 さらに、セマフォSは、同時アクセスからバッファを保護します。
まず、プロデューサーの動作を観察しましょう。
セマフォが0になると、バッファに空のセルがなくなるため、プロデューサはスリープ状態になります。
さらに、プロデューサーはバッファーにアクセスする前にセマフォを待機します。 別のプロセスがすでに待機している場合、そのプロセスはスリープ状態になります。
新しいアイテムを作成した後、プロデューサーはセマフォに信号を送ります。これにより、待機中のプロセスが発生する可能性のあるすべてのコンシューマーを起動します。
同様に、消費者は同じセマフォを使用します。
セマフォがゼロの場合、バッファで待機しているアイテムはありません。 消費者は眠りにつく。
の待機操作により、一度に1つのプロセスのみがバッファにアクセスできるようになります。 したがって、上の信号は待機中のプロセスをウェイクアップします。
そして最後に、セマフォの信号は、バッファに入れるものがあるプロデューサーをウェイクアップします。 結局、消費者は次のアイテムを消費する準備ができています。
このソリューションは、バッファーに使用可能なスロットができるまでプロデューサーがスリープすることを保証します。 それどころか、消費者は消費するアイテムができるまで眠ります。
5.5. 読者と作家の問題
この問題には、同じデータセットで動作するいくつかの問題があります。プロセスはデータセットのみを読み取ります。 更新は実行されません。 一方、プロセスは読み取りと書き込みの両方が可能です。
ここでの同期の問題は、一度に1人のライターだけがデータセットにアクセスできるようにすることです。複数のリーダーが問題なく同時に読み取ることができます。
データセットがロックされていると仮定します。 最初にデータセットをロックする必要があり、その後、先に進んで読み取りを開始できます。 最後は、読み取りが終了したらロックを解除する必要があります。
読み取りを開始または読み取りを停止すると、otherおよびのデータセットをロック/ロック解除する必要があります。
この問題でプロセスの同期を有効にするために、整数値と2つのセマフォを使用できます。
整数をゼロに初期化してみましょう。これは、ファイルにアクセスする回数を表します。 これはセマフォではなく、整数のみです。
また、セマフォを1に初期化して、変数が複数のプロセスによって更新されないようにします。
最後に、セマフォを1に初期化するとします。これにより、データセットが複数のによって同時にアクセスされるのを防ぎます。 したがって、とプロセスの擬似コードは次のとおりです。
この場合、セマフォで待機して信号を送るだけです。 セマフォを取得できれば、続行できます。 それ以外の場合、待機操作はそれをブロックします。
書き込み操作が完了するとすぐに、ライターはセマフォに信号を送ります。 したがって、他のプロセスがデータセットにアクセスできます。
のワークフローはもっと複雑です。 最初に行うことは、をインクリメントすることです。 そのためには、セマフォを取得して値を変更し、複数のプロセスが同時にアクセスしないようにする必要があります。
現在、他のデータセットにアクセスしていない場合は、インクリメント操作後に1になります。 この場合、データセットにアクセスする前にセマフォを待機して、ライターがアクセスしていないことを確認します。
セマフォを解放した後、は先に進み、読み取り操作を実行します。
最後に、データセットの操作が完了すると、値をデクリメントする必要があります。 この場合も、セマフォを取得し、変数を変更して、最後にセマフォを解放します。
5.6. 食事する哲学者の問題
食事する哲学者の問題は、同期ツールをテストするためのよく知られた思考実験です。
5本の箸を持ってテーブルの周りに5人の哲学者が座っています。 哲学者が食べたいときはいつでも、2本の箸を手に入れる必要があります。 この問題では、箸はプロセス間で同期させたいリソースです。
セマフォを使用してソリューションを実装しましょう。 まず、5本の箸を5本の配列で表すセマフォを初期化します。 次に、次のように実装します。
このソリューションでは、哲学者が食べることを決定すると、最初にセマフォを待ちます。 それを取得した後、哲学者はセマフォを待ちます。 両方の箸を手に入れると食べられます。
哲学者がいっぱいになると、それぞれのセマフォで信号操作を呼び出すことにより、同じ順序で箸を解放します。
この例はデッドロックのないソリューションを保証するものではないことに注意する必要があります。 小さな微調整を実装して、3つの条件すべてを保証できます。
6. 結論
セマフォは非常に強力なプロセス同期ツールです。
このチュートリアルでは、最初に2つのアトミック操作（待機とシグナル）を定義することにより、セマフォの動作原理を要約しました。 考えられるプロセス同期の問題をよりよく理解した後、セマフォを効果的に使用する方法をよりよく理解するためにいくつかの例を取り上げました。
