12

マルチスレッドアルゴリズムは、設計/デバッグ/証明が特に困難です。デッカーのアルゴリズムは、正しい同期アルゴリズムを設計することがいかに難しいかを示す代表的な例です。タネンバウムの最新のオペレーティングシステムは、IPCセクションの例でいっぱいです。誰かがこれについての良い参考文献（本、記事）を持っていますか？ありがとう！

4

6 に答える 6

13

保証に基づいて構築せずに何かを証明することは不可能であるため、最初に行うことは、ターゲット プラットフォームのメモリ モデルに慣れることです。Java と x86 の両方に、堅固で標準化されたメモリ モデルがあります。CLR についてはよくわかりませんが、他のすべてが失敗した場合は、ターゲットの CPU アーキテクチャのメモリ モデルに基づいて構築することになります。このルールの例外は、可変状態の共有をまったく許可しない言語を使用する場合です。Erlang はそのようなものだと聞いています。

同時実行の最初の問題は、可変状態の共有です。

これは次の方法で修正できます。

  • 状態を不変にする
  • 状態を共有していません
  • 同じロックによる共有可変状態の保護 (常にこれら 2 つのロックを正確に使用しない限り、2 つの異なるロックで同じ状態を保護することはできません)

並行性の 2 番目の問題は、安全なパブリケーションです。他のスレッドがデータを利用できるようにするにはどうすればよいですか? 引き継ぎはどのように行うのですか？この問題は、メモリ モデルと (できれば) API で解決できます。たとえば、Java には状態を発行する方法が多数あり、java.util.concurrent パッケージには、スレッド間通信を処理するために特別に設計されたツールが含まれています。

並行性の 3 番目の (そして難しい) 問題はロックです。ロック順序の管理ミスは、デッドロックの原因です。コードでデッドロックが発生する可能性があるかどうかを、メモリ モデルの保証に基づいて分析的に証明できます。ただし、それを念頭に置いてコードを設計および作成する必要があります。そうしないと、コードが複雑になり、そのような分析を実際に実行できなくなる可能性があります。

次に、同時実行性の正しい使用法を証明したら、または証明する前に、シングルスレッドの正確性を証明する必要があります。並行コード ベースで発生する可能性のあるバグのセットは、シングル スレッド プログラムのバグのセットに、発生する可能性のあるすべての同時実行バグを加えたものと同じです。

于 2008-09-16T17:53:39.877 に答える
3

モバイルプロセスの理論であるパイ計算は、始めるのに適した場所です。

于 2008-09-17T22:35:43.983 に答える
3

「並行および分散プログラミングの原則」、M. Ben-Ari
ISBN-13: 978-0-321-31283-9
彼らはオンラインでサファリの本を読んでいます:
http://my.safaribooksonline.com/9780321312839

于 2008-09-18T15:09:27.323 に答える
2

簡単な答え: 難しいです。

1980 年代後半の DEC SRC Modula-3 とカラマツの作品には、本当に優れた成果がありました。

例えば

  • スレッド同期: AD Birrell、JV Guttag、JJ Horning、R Levin System Programming with Modula-3、第 5 章による正式な仕様 (1991 年)

  • David L. Detlefs、David L. Detlefs、K. Rustan、K. Rustan、M. Leino、M. Leino、Greg Nelson、Greg Nelson、James B. Saxe、James B. Saxe による拡張静的チェック(1998)

Modula-3 の優れたアイデアのいくつかは、JML などの Java の世界に取り入れられていますが、「JML は現在、順次仕様に制限されています」とイントロで述べられています。

于 2008-09-16T19:08:37.607 に答える
1

具体的な参考資料はありませんが、Owicki-Gries理論（定理証明が好きな場合）またはプロセス理論/代数（さまざまなモデル検査ツールも利用可能）を調べてみてください。

于 2008-09-17T22:31:49.047 に答える
0

@念のため：私はそうです。しかし、私が学んだことから、自明ではないアルゴリズムに対してそうするのは大きな苦痛です。そのようなことは頭のいい人に任せます。私が知っていることは、KM Chandy、J Misra による Parallel Program Design: A Foundation (1988) から学びました。

于 2008-09-16T17:38:14.783 に答える