なんもわからんな

LookOne について

※メモのために書いているので、文章のアレコレは気にしていません

ここ最近分散システムの勉強をしていましたが、各ノードのパフォーマンスを最大まで上げないと分散させる意味あんまりないのでは?って思い並列コンピューティングの勉強をしています。

使っている本はこちら www.amazon.co.jp

現在、相互排他の章のLockOneのところが終わったので忘れぬように纏めます

#共有カウンタ
class Counter{
  private int value;
  public Counter(int c){
    value = c;
  }

  public int getAndIncrement(){
    int temp = value; # やばいところ
    value = temp + 1; # やばいところ
    return temp;
  }

シングルスレッドで上記のインクリメントを読んでも問題ないが、複数スレッドで上記のインクリメントを呼ぶとやばいところ がやばくなるのである。
それを回避するためにクリティカルセッションやばいところ を守る。
(読み込み/書き込みのシーケンスを一度に1つのスレッドが行う)

//interface 

public interface Lock{
  public void lock;
  public void unlock();
}

class Counter{
  private int value;
  public Counter(int c){
    value = c;
  }

  public int getAndIncrement(){
    lock.lock();
    try{
      int temp = value; # クリティカルセッション
      value = temp + 1; # クリティカルセッション
      return temp;
    }finally{
      lock.unlock();
    }
  }

lockでスレッドはデータをクリティカルセッションに入れるまで待つ。
クリティカルセッションに入れたら、ロックをかけデータの見出し及び書き込みをする。
上記が成功/失敗したらロックを解除する。

あるスレッドが無限に占有することがないことからスターベーションフリーである。
またスレッドがロックを試み取得でき、ロックを取得できる。スレッド1がロック取得できないとしたら、スレッド2がクリティカルセッションをこなしていることから、デットロックフリーとなる。

LockOne

LockOneアルゴリズムでは2つのスレッドの環境で考える。 またスレッドがロックを確保している|しようとしている のステートを表すためサイズ2のbooleanの配列を用意する。

下記ではスレッドAがスレッドBに邪魔されずにロックを確保できる例を示す。

f:id:yakuta55:20190225230638p:plain

スレッドAはクリティカルセッションに入るために、ロックを確保しようとする。

f:id:yakuta55:20190225230829p:plain

f:id:yakuta55:20190225231055p:plain

f:id:yakuta55:20190225231143p:plain

下記ではスレッドBがスレッドAに邪魔されロックの確保を待たされる例を示す。 f:id:yakuta55:20190225231420p:plain

f:id:yakuta55:20190225231458p:plain

下記では、スレッドA,Bが同時にロックをかけようとしてスターベーションの状態を示す f:id:yakuta55:20190225231547p:plain

writeA(flag[A] = true)とwriteB(flag[B])がreadA(flag[B])とreadB(flag[A])よりも先に起こるためおきる。

LockOneではどちらかのスレッドがもう一方のスレッドよりも前に実行さえすればデッドロックは起こらない。