問題タブ [mutual-exclusion]

私はマルチスレッドを研究しており、セマフォと相互排除の概念を理解しようとしています。私がオンラインで見つけた例のほとんどは、セマフォまたはミューテックスを実装するためにある種のライブラリ (例: pthread) を使用していますが、クリティカル セクションを確立する単純なセマフォの実装にもっと興味があります。メモリの領域。

このタスクには、ミューテックス (用語を正しく理解していればバイナリ セマフォとも呼ばれます) が必要になると思います。セマフォがコードのセクションを単一のスレッドに「ロック」することで競合状態を防ぐ方法はわかりますが、セマフォ自体で競合状態が発生するのを防ぐものは何ですか?

ロックを追跡するためにint値を保持するバイナリセマフォを想像します。

2 つのスレッドが同時に関数を呼び出し、両方が同時にチェックにP到達し、条件をtrueとして評価するとします。これにより、両方のスレッドが同時にメモリの同じ領域へのアクセスを許可される競合状態が作成されます。if(lock > 0)

では、セマフォの実際の実装でこの競合状態が発生するのを妨げているのは何でしょうか?

Hoare のモニターを使用して証券取引所を実装しようとしています。

次のように、buy() と Sell() の 2 つの関数があります。

また、買い手 ID、売り手 ID、ティッカー、株式数、および価格に関する情報を出力する必要があります。そして公平さは常に満たされています。

私のソリューションの疑似コードは次のとおりですが、完全ではありません。基本的に、ティッカーごとに条件変数キューを使用します。売り手プロセスは、売り注文を証券取引所に送信するときにこのキューでスリープ状態になり、買い手プロセスは、条件 (価格制限と株式数の一致) が満たされた場合に買いたいことをこの売り手プロセスに通知します。

このようなアプローチは、複数のティッカーの複数の売買注文を処理できるでしょうか? それとも行き止まりにつながりますか？

私は、マルチスレッド プログラムを扱う必要がある学校向けの Java プロジェクトに取り組んでいます。基本的に同時アクセスを管理する必要がある値のマトリックスである多くのスレッド間で共有されるクラスが必要です。それは次のようになります。

各項目に 1 つずつ、ReentrantReadWriteLock のマトリックスを使用してそれを管理しようとしていましたが、マトリックスのサイズが約 10^3 X 10^3 であることに気付きました。

これが進むべき道だと思いますか？(そんなに多くのロックを作成しても大丈夫ですか?)

このクラスを使用するスレッドの数が少数の N (N の範囲は 2 から 8) に制限されていることを考慮して、最小の相互排除のみを保持し、ロックの使用を減らすより良い方法を見つけることができますか?

ご支援ありがとうございます！

以下は、Peterson の 2 スレッド ロック アルゴリズムの一般化されたバージョンであり、「n」個のスレッド/プロセスがクリティカル セクションをめぐって競合できるようになっています。

基本的に、「n」レベルと「n」スレッドがあります。非アクティブまたは非クリティカル セクション領域で実行中のスレッドはレベル 0 です。レベル n-1 はクリティカル セクションです。すべてのスレッド/プロセスは、クリティカル セクションに入る前に n-1 レベルを通過する必要があります。

レベル [n] と犠牲者 [n] の 2 つの配列があります。最初の配列は、スレッドの threadId によってインデックス付けされ、エントリ level[i] には、threadId 'i' を持つスレッドの現在のレベルが格納されます。2 番目の配列はレベル番号によってインデックス付けされ、エントリの犠牲者 [i] には、レベル「i」に入る最新のスレッドのスレッド ID が格納されます。

level[] のすべての要素は 0 に初期化されます。victim[] の特定の初期化はありません。

このコードは、Maurice Herlihy と Nir ​​Shavit による本「The Art of Multiprocessor Programming」からの直接のコピーです。

問題は、コードが相互排他性を満たしていないように見えることです!!

理由:- 6 行目は、同じレベルまたはそれ以上のレベルのスレッドが存在し、スレッド自体が現在のレベルに入る最新のスレッドになるまで、スレッドがそのレベルでループし続けることを意味します。レベルにとどまります。2 番目のスレッドが同じレベルになると、最初のスレッドの 'victim[i] == me' 式が false になり、次のレベルにプッシュ ダウンされます。

ここで、各レベルに 1 つのスレッドがあり、レベル 0 のスレッドがレベル 1 に進もうとすると、レベル 1 のスレッドはレベル 1 の犠牲者ではなくなるため、レベル 1 のスレッドがレベル 2 にプッシュされます。波及効果と各スレッドが 1 レベルずつ押し下げられ、レベル n-2 のスレッドもそのクリティカル セクションに入る!!

コードは実際に間違っているのでしょうか、それとも何か間違っていると解釈しましたか?