マルチプロセッサプログラミングの芸術第二章練習問題9-20

練習問題9は与えられた相互反発アルゴリズムについて、r−有界待機を定義します.もしDjA->DkBなら、CSjA->CS(k＋r)Bです.Petersonアルゴリズムのポーチを定義する方法がありますか?これにより、ある値rに対して、アルゴリズムを変更してr-有界待ちをサポートすることができますか?答え:
ここでr-有界待つという定義は、先に来たサービスの定義と似ています.Petersonアルゴリズムでは、個人的には、ポーチを追加する必要はないと思います.アルゴリズムは2つのスレッドまたはプロセスを制御するだけで、ポーチで待つスレッドやプロセスは常に1つしかないので、元のアルゴリズムのflags配列は十分です.元のアルゴリズムはすでに境界が待っているので、rは値があるべきで、アルゴリズムにr-有界をサポートさせることができます.
練習問題10
なぜポーチエリアを定義する必要がありますか?なぜ、最初のサービス(FFFFS)は、lock()方法に基づいて第1の命令が実行される順序の相互反発アルゴリズムにおいて定義されないのですか?ロック()方法によって第一の命令を実行する方法――異なるユニットまたは同じユニットに対する読みと書きは、それぞれの結論を証明します.
答え:
ポーチエリアはこのエリアに入るスレッドを確保し、一定のステップ制限内で臨界エリアに入ることができます.
2.8節において、ロックオブジェクトの上書き状態を定義すると、少なくとも全ての共有記憶ユニットを書き込みたいスレッドがありますが、このロックオブジェクト記憶ユニットは、臨界領域が空のように見えます.
この定義によって、ロックのトリガは書き込み操作が必要であると判断しましたが、ロックの第一のコマンドでは判断できません.今回の操作は読み操作ですか?それとも書き込み操作ですか?
PS.書いた後に読んでいない操作は、スレッドがないのに等しいです.読み書きができる時は、第一条の命令はポーチエリアの標識と見なされます.
練習問題11
Flaakyコンピュータ会社のプログラマは、nスレッドの相互反発を保証するために、図に示すようなプロトコルを設計した.以下の各問題について、またはその成立を証明するか、または逆の例を与える.

1 class Flaky implements Lock {
2    private int turn;
3    private boolean busy = false;
4    public void lock() {
5      int me = ThreadID.get();
6      do {
7        do {
8          turn = me;
9        } while (busy);
10       busy = true;
11     } while (turn != me);
12   }
13   public void unlock() {
14     busy = false;
15   }
16 }

①この協議は相互反発特性を満たしていますか?
②当該協議は空腹がないものですか?
③当該協議は無固定ですか?
答え:
このコードはLockTwoに似ています.証明方法はLockTwoを参考にしてもいいです.
①証明:
成立しないと仮定して、各スレッドはk回目(j回目)において臨界領域に入る前に最後にロック()方法を呼び出す実行状況を考慮する.
コードで確認できます.
writeA(turn=A)->readA(turn==B) (1.1)
writeB(turn=B)->readB(turn==A)(1.2)
スレッドBは、イベントwriteA(turn=A)とイベントreadA(turn=B)の間で、ターンにBを付与しなければならない.これは最後の賦課ですので、あります.
writeA(turn=A)->writeB(turn=B)->readA(turn=B)
ターンがBに設定されると、そのまま維持されます.したがって、その後の読み出し動作はBに戻り、数式1.2と矛盾します.
したがって、このプロトコルは相互反発の特性を満たしている.
②証明:
仮定が成り立たない.スレッドAがずっといる子のロック()方法を仮定すると、それは必ずwhile文を実行しています.busyがfalseとturnにセットされてBに値が付けられます.
Aが前に進まない場合、スレッドBは何回も臨界領域に入る可能性があり、このようにスレッドBは一旦臨界領域に入るとturnをBに設定する.ターンがBに設定されると、もう変更されなくなりますが、busyは状態を変えていません.最内階のwhileサイクルは下がりませんでした.だから、スレッドAはロック()から外れていません.このようにスレッドBは待ち続け、Aがロック()から退出するのを待つ.反証に失敗する
したがって、この契約は空腹ではない.
③証明:
ここでは、出現する可能性があります.
writeA(turn=A)->writeA(busy=true)->readB(busy==false) 
この時AはturnがAになるのを待っています.Bはbusyがfalseに設定されるのを待っています.
飢餓の中で最後に述べたのが、この問題の原因です.
したがって、この契約はノーデッドロックではない.
練習問題12
フィルタロックは、他のスレッドを任意の回数で超えることができることを証明しています.
答え:
ここでまずフィルタロックの待合室の重要な特性を振り返ってみます.
1.少なくとも層kに入ることを試みているスレッドが成功します.
2.以上のスレッドが層kに入ると、少なくとも一つのスレッドがブロックされます(その層で待ち続けます).
参考書の中で空腹の証明に対して、明らかにフィルタリングが他のスレッドの任意回数を超えることができます.
練習問題13
ダブルスレッドのPetersonロックの一種の改良は、二叉樹の中に一連のダブルスレッドのPetersonロックを配置することである.nを2のべき乗とする.各スレッドに対して、他のスレッドによって共有されてもよい葉子錠を指定します.各ロックは自分のスレッドを2つ共有し、スレッド0とスレッド1と見なす.
ツリーロック要求において、スレッドは、スレッドに対応する葉からツリーの根までの全てのスレッドのPetersonロックを順次取得する.ツリーロック放出においては、葉が解放されるまでの二叉樹の根から、各スレッドのPetersonロックが得られている.いつでも、スレッドは限られた時間で遅延される可能性があります.(言い換えれば、スレッドはまどろみをしてもよく、またはうたい歌をしてもよいが、それらは決して死んでしまうことはない.)次の各特性について、または拡張ロックがこのような特性を維持することができることを証明するか、または実行の逆例(おそらく無限である)を与えることは、その特性を備えていないということを説明する.
1.反発し合う
2.デッドロックなし
3.空腹がない
スレッドからツリーロックが成功的に獲得されるまでの間、ツリーロックが要求されてリリースされる回数は上界がありますか?
答え:
この問題は個人的にはよく分かりませんでしたので、他の人の答えを探しました.
(参照 )
帰納法を用いる
k層のこのようなロックは、互いに反発することを満たしていると仮定し、ツリー高がk＋1層に増加すると、Petersonロックは、互いに反発することを満たすため、k＋1層上のスレッドがk層ノードごとにスレッドを推薦するだけであり、結果としてk層を構成するツリーであり、仮定に従って、相互反発を満たす.
同じ理屈で空腹もない.
デッドロックがないことを満たして、ロックを獲得する過程はリーフノードからノードとの方向なため、全体の図はいずれかの方向リングがあることを探し出すことができなくて、デッドロックの条件を満たしません.
上界はnである
まず上界>==n(自分を含めて今回)は、そうでないとお互いに反発することを満たしていません.
h=k(ルートノードh=0)を仮定すると、上界はn=(2^k)であり、リーフノードが2 n、h=k＋1の場合、あるリーフノードAが兄弟ノードに勝つ可能性があり、兄弟ノードはh=k層に2^k回ロックをかける.Petersonロックの性質により、次の兄弟ノードが競争に参加するのはA勝ちとなる.回は必ずロックがかかります.あるいは、スレッドAのロックが成功すれば、次の参加時は必ず他のスレッドよりも第二回ロックが開始される前に参加するスレッドB(第一回ロックを含む)がロックされます.葉っぱ結点がnなので、それ以前にnスレッドがあります.
また、ロックをかけたら次のフライングロックは必ずAに負けるので、界はnです.
練習問題14
よく分かりませんでした.参考にしてください.http://blog.csdn.net/fulltopic/article/details/16835571でしょう
練習問題15
実際のアプリケーションでは、ほとんどのロック要求は無駄です.したがって、ロック性能を測定するための実用的な基準は、他のスレッドがないときに、必要な操作ステップを取得することです.
Cataloupe-Myelon大学の科学者は任意のロックに対する「包装器」を設計しました.また、基本的なロック類が相互反発と飢餓性がない場合、FastPath錠もこの2つの特性を持っています.そして無競争の場合には定数ステップでロックを獲得することができます.なぜ彼らの結論が正しいのか、または逆の例を示してみます.

1  class FastPath implements Lock {
2    private static ThreadLocal myIndex;
3    private Lock lock;
4    private int x, y = -1;
5    public void lock() {
6      int i = myIndex.get();
7      x = i; // I’m here
8      while (y != -1) {} // is the lock free?
9      y = i; // me again?
10     if (x != i) // Am I still here?
11       lock.lock(); // slow path
12   }
13   public void unlock() {
14     y = -1;
15     lock.unlock();
16   }
17 }

解答:
証明書は書かないほうが面倒くさいです.本の中の例を参照してください.
ここのロック関数は大丈夫です.全部ロックできます.しかし、ここでこのように書いてください.無限の再帰コールが発生するはずです.スタックにオーバーフローがないなら、問題はないはずです.
ここで唯一の問題は、unlockの中のlock.unlockにあると思います.(javaはこのように書いてもいいですか?javaのこのような使い方はあまり詳しくないです.)ここでは15行を無視して、自分の理解に役立ちます.
相互反発を満足していますが、ロックがかかります.ロックに入ると、現在のスレッドではないかもしれません.他のスレッドになるかもしれません.だから、現在のスレッドは同じようにロックされていて、ロック解除ができません.