ランポートのベーカリー アルゴリズム: ランポートのベーカリー アルゴリズム

Lamport's Bakery 法と呼ばれる同期法は、並列コンピューティング システムにおけるクリティカル セクションの問題を解決します。複数のプロセスが共有リソースを同時に使用する必要があるが、それができるのが 1 つのプロセスだけである場合、これはクリティカル セクション問題と呼ばれます。競合を回避し、システムの正確性を保証するための課題は、各プロセスが相互に排他的な方法でリソースを使用することを保証することです。

Lamport ベーキング アルゴリズムの擬似コード

Lamport のベイク アルゴリズムの疑似コードは次のとおりです -

• サイズ N (N はプロセスの総数) の配列 (「選択」と呼ばれる) をすべて 0 に初期化します。

• サイズ N ですべて 0 の配列 (number と呼ばれる) を初期化します。

• 各プロセスは、クリティカルセクションに入るときに次のコードを実行します -

  • 選択範囲[i] = 1

  を設定します

  • 数値[i] = max(数値[0], 数値[1], ..., 数値[N-1]) 1

  を設定します。

  • 選択範囲[i] = 0

  を設定します。

  • 他のプロセス j ごとに、(number[j] == 0) または (number[i], i)

  キー部分を入力してください

各プロセスでは、クリティカル セクションを離れるときに次のコードを実行します -

• セット番号[i] = 0

これは、Lamport のベイク アルゴリズムの実際の応用を説明するコードです。この例では実装言語として C を使用します。

Lamport ベーキング アルゴリズムの利点

Lamport のベイク アルゴリズムの利点は以下にリストされています -

共有リソースへのアクセスを要求するプロセスまたはスレッドにさまざまなトークンを提供することで、公平性が確保されます。

• 指定された値に基づいてトークンを配布することで、飢餓を防ぎます。

• シンプルで理解しやすく実行しやすいトークンベースの戦略を使用します。

• 効率的で、複雑なデータ構造やプロセス間の対話は必要ありません。

• 特殊なハードウェアやハードウェアの支援を必要とせずに、相互排他を実現します。

• 幅広いアプリケーションと高い適応性を備えており、さまざまなシナリオに適用して、同時計算の公平性と相互排他を確保できます。

• 分散システムまたは並列システムに取り組むソフトウェア エンジニアにとって便利なツールです。

• Lamport ベーキング アルゴリズムの欠点

- このアルゴリズムはビジー待機を呼び出します。これにより、特に同じ共有リソースへのアクセスを求めて競合する多数のプロセスまたはスレッドがある場合に、非効率性と高い CPU 使用率が発生する可能性があります。 。

• 飢餓
- アルゴリズムは正義を保証しますが、安全策はありません。場合によっては、プロセスまたはスレッドが繰り返し停止され、トークンの取得やリソースへのアクセスが妨げられることがあります。

• オーバーヘッド
- このアルゴリズムでは、プロセスまたはスレッドごとに状態情報を保存する必要があるため、トークン シーケンスを決定するためにより多くのメモリと処理時間が必要になります。

• 複雑さ
- アルゴリズムの適用は、競合状態やデッドロックを注意深く処理する必要があり、ミューテックスやセマフォなどの同期メカニズムを使用する場合があるため、困難になる場合があります。

• ＃＃＃結論は＃＃＃

  Lamport のベイク アルゴリズムと呼ばれる相互排他的なアルゴリズムにより、個々のプロセスまたはスレッドが相互に干渉することなく共有リソースを利用できるようになります。これは飢餓を防ぎ、正義を確保するためのシンプルなアルゴリズムです。 李>このアルゴリズムは、リソース アクセス リクエストを行う各プロセスまたはスレッドにトークンを割り当て、これらのトークンの値を比較して、与えられた順序を決定することによって機能します。リソースは、トークンが最も少ない操作から最初に利用可能になります。

以上がランポートのベーカリー アルゴリズム: ランポートのベーカリー アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。