concurrency - オブジェクトのグループへの同時アクセス

Question

ワークスティーリングアルゴリズムを使用してタスクを同時に実行し、スレッドのプールで構成されるアプリケーションを開発しようとしています。

これらのタスク

• 事前定義されたオブジェクトのセットにアクセスします。
• 実際に実行する前に、アクセスするすべてのオブジェクトに対する読み取り/書き込み権限を「アトミックに」取得する必要があります。
• 終了したら（そして最終的には終了することが保証されます）、取得したオブジェクトを解放します。

この問題を解決する1つの可能な方法は、各スレッドに一度にタスクを取得させてから、事前定義された順序を使用して各オブジェクトをロックしようとすることです。少なくとも1つが失敗した場合は、すべてのロックを解放し、別のタスクに進みます。

ただし、この方法では、オブジェクトの依存関係が大きいタスクが不足する可能性が高くなり、ライブロックが発生する可能性もあります。

同時実行性を最大化しながら一連のロックを取得する別の方法はありますか？（グローバルロックなし）または、システムを不要になるように変更しますか？もしそうなら、それについての良い論文はありますか？

ps：ティトンが答えたように、これは「食事する哲学者」問題の一般化されたバージョンです。非集中型のソリューション、特に高負荷（タスクの追加と削除）でうまく機能するアルゴリズムを探しています。

Answer 1

リソースの注文は有効なアプローチです。頭に浮かぶもう1つの簡単なアプローチは、リソースの可用性に関する情報を保持する共有アービターを導入することです。タスクは、単一のアトミックステップ「acquire（r1、r2、...、rn）」でアービターを介して必要なすべてのリソースをロックし、「release（r1、r2、...、rn）」で同様に解放します。

「取得」要求Aが満たされる場合、アービターは、Aがリソースを解放するまで、他のタスクがAによって保持されているリソースを取得できないことを確認します。

アービターは、着信要求を満たすためにいくつかの戦略を使用する場合があります。

1. すぐに満たすことができない要求を拒否します-タスクは再試行する必要があります。これにより、ライブロックと飢餓への扉が開かれます。
2. すべての着信要求をキューに保持し、先頭の要求に必要なリソースが利用可能になると、FIFO方式でそれらを処理します。
3. 満たされていないすべてのリクエストを（要求されたリソースをブロックせずに）リストに保持し、一部のリソースが解放されるたびに（おそらく古いリクエストを優先して）それらを繰り返し処理して、満たすことができるリクエストを見つけます。

Answer 2

タスクがある時点で失敗するだけでオブジェクトをロックしようとすると、最初のタスクがその時点でオブジェクトを所有しているため、別のタスクがオブジェクトのロックに失敗する可能性があります。

最初にロックを取得しようとするとき、そして最終的にすべてを解放するときにも、グローバルロックを使用すると思います。

単純なソリューションが実際には不十分であることが判明した場合、最大の同時実行性について心配します。

Answer 3

あなたの問題は食事する哲学者と呼ばれています。あなたはこのキーワードの下であなたが必要とするどんな量の文献も見つけるべきです:-)。