Fairness

背景

• Starvation-freedomでは、Lock獲得までの時間は保証されていない
• 「フェア」なLockアルゴリズムとは?

定義

• Fairnessの定義: first-come-first-served
  • 先着順、ということ。スレッドAがスレッドBより先にロックを呼び出した場合、Aが先にクリティカルセクションに入るべき、ということ
• Starvation-freedomよりも強い性質。
  • Deadlock-freedomかつfirst-come-first-servedなら、Starvation-freedomでもある

Lockがfirst-come-first-servedである条件

• lock習得処理をdoorway sectionとwating sectionにわけ、$\text{if }{D}_A^j\to D_B^k\text{ then }C{S}_A^j\to C{S}_B^j$なとき、first-come-first-servedという
  • doorway section ($D_{Thread}^{n-thcall}$) : フラグを立てるなど、他スレッドの実行状態に関係なく進行できる部分.
    • 有限の決まったステップ数で終わる(ループのないコードの部分など。ループがあってもこれを提供するものもあるらしい?(kekeho))
    • Bounded wait-free特性を持つ。
  • wating: 他スレッドの状態によって待機が必要な部分
    • unboundedなステップ数がかかる
  • 「スレッドBがdoorwayを始める前にスレッドAがdoorwayを終了したら、AがBに追い越されないとき、first-come-first-reservedといえる」という感じ