備忘録的なやつ

TrsNiumの勉強ログ

3章: 線形化可能性

TAoMPで紹介されている一貫性は以下の3種類です。 - 静止一貫性 - 逐次一貫性 - 線形化可能性

何となく線形化可能性だけ書きます

線形化可能性

線形化可能性ではオーバーラップしないメソッド呼び出しの順序では、それと対応する逐次履歴と同じである必要があります。呼び出しがオーバーラップする場合、それぞれの呼び出し順序は曖昧でよく、呼び出し順序は入れ替わっても良いです。オーバーラップしないときに、特定の順序または逆の順序で実行した場合と一致することを示します。図にすると下記のように表すことができます。

f:id:yakuta55:20190324162657p:plain

上の図ではthread1がObjに3を書く呼び出し、次にthread2がObjに-7を書き込んでいます。しかし、呼び出しのオーバーラップが発生する為に、thread2の読み込みは3になっています。これを線形化ポイントを付け図に示すと下記のようになります。
(※ 線形化ポイントとは、メソッドの呼び出し結果が他のメソッド呼び出しから参照できるようになるステップ)

f:id:yakuta55:20190324163714p:plain

参考

Eventual Consistencyまでの一貫性図解大全 - Qiita

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ではどちらかのスレッドがもう一方のスレッドよりも前に実行さえすればデッドロックは起こらない。