プログラムが連続して一貫性のあるアーキテクチャで実行できる方法の数

Question

私はこの問題を理解し、解決しようとしていません。 それぞれa、b、c命令を持つ3つのスレッドがあるとします。プログラムが順次一貫性のあるアーキテクチャで実行できるさまざまな方法 H この問題はどのように解決する必要がありますか？

Answer 1

スレッドが3つあります。それぞれが一連のアクションを処理しますa、b、およびcスレッドに数値を使用できるようにします。理解すべき重要なこと：各スレッド1〜3は、の処理をの順に実行する必要があります。バリエーションは、スレッドが多くの組み合わせで作業を実行できるためにのみ発生します。私たちのマシンはいつでもスレッドしか提供できないと仮定しましょう。そして、そのアクションはスレッドコンテキストスイッチが発生する前に完了しています。あなたが持つことができる

：

それを見て

1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c 
1a, 2a, 1b, 1c, 2b, 2c, 3a, 3b, 3c 
1a, 2a, 2b, 1b, 1c, 2c, 3a, 3b, 3c 
1a, 2a, 2b, 2c, 1b, 1c, 3a, 3b, 3c 
1a, 2a, 2b, 2c, 3a, 1b, 1c, 3b, 3c 
1a, 2a, 2b, 2c, 3a, 3b, 1b, 1c, 3c 
... 

を、一つはすべての組み合わせを産卵木を構築するアルゴリズムを考えることができます。あなたは基本的に "1a"のような候補を選び、次にどのステップが可能かを決めます（この場合は1b、1c、2a、... 3c）。 次に、パスを構築することができます。

1a-1b 
1a-2a 
... 

などとなります。各パスについて、そのパス上の要素を覚えています。また、別の要素を追加するには、「残りの」要素をチェックアウトします。残りの各オブジェクトは別の新しいパスを定義します。繰り返す。

このようにすると、すべての可能なパスを計算するアルゴリズムを定義できるはずです。

これは良いコーディングカタカナの練習を構成します - そして私の入力はあなたを得るために十分であるべきです。ショートカットが必要な場合はhereと表示されます。またはthere。

これ以外にも、純粋な数学的問題として解くこともできます。すべての要素1a、... 3cをリストに入れて、そのリストのすべての順列を作成すれば、9！したがって、362880の可能性。もちろん、これはうまくいきません。なぜなら、1b、1aなどの順列を除外しなければならないからです（なぜなら、a、b、cは常にあなたの必要条件を満たしているからです）。

So（number threads + number steps）！有効なパスの数はupperとなります。他の人が来て、無効なパスの数を計算するためにもう少し数学を追加するかもしれません。

（BTW：「印刷」するための別のアプローチであろうと、すべての可能なパスが - 単に9つの要素のすべての順列を作成し、無効であるものをドロップ）

免責事項：上記のみせるの全ての基礎となるマシンが正確にの1つの「本当の」スレッドを持っていると仮定したときの感覚です。そのスレッドの実行とコンテキストの切り替えは、操作が完了した後に行われます。言い換えれば

1: aaaabbbbcccc 
2: aaaabbbbcccc 
3:  aaaabbbbccc 

：あなたはこれらの仮定をドロップした場合は、のための部屋を作るあなたは実機での潜在的なパスを考えると、物事ははるかに複雑になります。