1

私は並行性を学ぶことに決め、2つの異なるプロセスからの命令がどのように重複する可能性があるかを知りたいと思いました。両方のプロセスのコードは、各反復で3つの命令が実行される10回の反復ループです。問題は、ある時点でX命令を固定したままにして、他のプロセスからの他のX命令を、順序付けする必要があることを考慮してスペースの間に収めることであると考えました（プロセスBの命令4は常に命令20の前に来る必要があります）。

この数を数えるプログラムを作成し、結果を見て、解がnの組み合わせkであることがわかりました。ここで、kは1つのプロセスのループ全体で実行される命令の数であるため、10回の反復では30になります。 nはk*2（2プロセス）です。言い換えると、n / 2が固定され、スペースの間にn / 2を収める必要がある、n個のオブジェクト。後者のn/2は順序を失うことはありません。

問題は解決しました。いいえ、そうではありません。これがなぜであるかはわかりません。組み合わせの定義は、n個のグループからk個の要素を取得して、すべてのグループが異なるが、要素を取得する順序が異なるようにする方法がいくつあるかを理解しています。重要です。この場合、n個の要素があり、すべての命令が実行されるため（n C n）、実際にはそれらすべてを取得しています。

バッグの中に2kの青（A）と赤（B）のオブジェクトがあり、バッグからk個のオブジェクトを取り出すと説明すると、2k個の命令が実際に実行されたときにk個の命令しか取得しません。これに光を当てていただけませんか？

前もって感謝します。

4

3 に答える 3

6

FWIWそれはこのように見ることができます：あなたはk個の青とk個の赤のボールが入ったバッグを持っています。同じ色のボールは区別できません（同じプロセス/スレッド内の命令の順序が固定されているという制限と同様に、これは最近のプロセッサには当てはまりませんが、今のところ単純にしましょう）。バッグからすべてのボールを引き出す方法はいくつありますか？

私の組み合わせスキルはかなり錆びていますが、私の最初の推測は

(2k!)
-----
2*k!

ウィキペディアによると、これは確かに等しい

(2k)
(k )

（申し訳ありませんが、これを表示する方法がわかりません）。

n個のプロセスの場合、バッグにn個の異なる色のボールを入れることで一般化できます。

更新：厳密な意味では、これは単一のプロセッサで異なるプロセスが実行される状況のみをモデル化するため、すべてのプロセスからのすべての命令はプロセッサレベルで線形に順序付けられる必要があることに注意してください。マルチプロセッサ環境では、複数の命令を文字通り同時に実行できます。

于 2010-04-10T12:35:54.940 に答える
2

一般的に、私はペテルの答えに同意しますが、OPが完全にクリックされていないように見えるので、これが私のショットです（純粋に数学/組み合わせの観点から）。

まとめる30（k）命令のセットが2つあり、合計60（n）命令になります。30の各セットを順番に保持する必要があるため、各セット内のどの命令からの命令であるかを追跡する必要はありません。したがって、60個の「スロット」があり、一方のセット（たとえば、赤）から30個の命令を配置し、もう一方のセット（たとえば、青）から30個の命令を配置します。

30個の赤い命令を60個のスロットに配置することから始めましょう。これを行うには（60は30を選択）= 60！/（30！30！）の方法があります（60のどの30スロットが赤い指示で埋められるかを選択しています）。これで、まだ30個の青い命令がありますが、残っている空きスロットは30個だけです。（30は30を選択）= 30！/（30！0！）=残りのスロットに青い命令を配置する1つの方法があります。したがって、合計で（60は30を選択）*（30は30を選択）=（60は30を選択）* 1 =（60は30を選択）それを行う方法があります。

ここで、30個の2セットではなく、3セット（赤、緑、青）のk個の命令があるとします。合計3kのスロットを埋めることができます。まず、赤いものを配置します：（3kはkを選択）=（3k）！/（k！（3k-k）！）=（3k）！/（k！（2k）！）。次に、緑色のスロットを残りの2kスロットに配置します：（2kはkを選択）=（2k）！/（k！k！）。最後に、青いスロットを最後のkスロットに配置します：（kはkを選択）= k！/（k！0！）= 1合計：（3kはkを選択）*（2kはkを選択）*（kはkを選択） =（（3k）！*（2k）！* k！）/（k！（2k）！* k！k！* k！0！）=（3k）！/（k！k！k！）

さらなる拡張として（完全な説明は提供しませんが）：

  • 長さがa、b、cの3セットの命令がある場合、可能性の数は（a + b + c）！/（a！b！c！）です。
  • i番目のセットにki命令があるnセットの命令がある場合、可能性の数は（k1 + k2 + ... + kn）！/（k1！k2！... kn！）です。
于 2010-04-10T17:44:18.080 に答える
1

Péterの答えは十分に良いですが、それは並行性が難しい理由を説明するものではありません。これは、最近では、複数の実行ユニット（コア、CPU、ノード、コンピューターなど）を使用できることがますます多くなっているためです。つまり、命令間で重複する可能性がさらに高まるということです。従来のインターリーブで何が起こるかを正しくモデル化できるという保証はありません。

これが、セマフォ/ミューテックスを正しく使用するという観点から考えることが重要である理由であり、メモリバリアが重要である理由です。それは、これらすべてが、本当の厄介な絵をはるかに理解しやすいものに変えてしまうからです。ただし、ミューテックスは実行可能な実行数を減らすため、全体的なパフォーマンスと潜在的な効率が低下します。これは間違いなくトリッキーです。そのため、他の方法では相互作用しないアクティビティのスレッド間でメッセージを渡すという観点から作業できると、はるかに優れています。理解しやすく、同期が少ない方が良いです。

于 2010-04-10T13:12:26.643 に答える