原文はこちら。
The original article was written by Dave Dice (Senior Research Scientist, Oracle).
https://blogs.oracle.com/dave/biased-locking-in-hotspot

HotSpotのbiased lockingスキームは、Dave Dice、Mark Moir、Bill Schererが執筆した以下の論文から生まれました。

Quickly Reacquirable Locks
https://cdn.app.compendium.com/uploads/user/e7c690e8-6ff9-102a-ac6d-e4aebca50425/f4a5b21d-66fa-4885-92bf-c4e81c06d916/File/ccd39237cd4dc109d91786762fba41f0/qrl_oplocks_biasedlocking.pdf

簡単に説明すると、Javaモニタを取得するために通常使用されるcompare-and-swap（CAS）操作では、実行中のCPUにかなりのローカルレイテンシが発生します。その寿命の間、最大でも1つのスレッドがほとんどのオブジェクトをロックしているため、そのスレッドがオブジェクトを自分自身に向けてバイアスをかけることができます。一度バイアスをかけると、そのスレッドはその後、高価なアトミック命令に頼らずにオブジェクトをロックしたりロック解除したりできます。明らかに、常に最大で一つのスレッドにオブジェクトを偏らせることができます（そのスレッドをバイアス保持スレッド（bias holding thread）と呼びます）。しかし、別のスレッドがbiased objectを取得しようとした場合、元のスレッドからバイアスを取り消す必要があります（この時点では、オブジェクトをリバイアスするか、オブジェクトの残りのライフタイムを通常のロックに戻すかのどちらかを選択できます）。バイアス解除における重要な課題は、revoker（解除する側）とrevokee（解除される側、ここではバイアス保持スレッド）を協調させることです。revokeeが解除の間にオブジェクトをロックしたりロック解除したりしないようにしなければなりません。論文で述べているように、解除はシグナル、サスペンション、セーフポイントなどの様々な方法で実装できます。Biased Lockingで利益を生むために重要なことは、アトミックな命令を回避することで得られる利益が、解除のコストを上回る必要があるということです。Biased Lockingを概念化するもう一つの等価な方法は、元の所有者が、オブジェクトが競合に遭遇するまで、単にオブジェクトのロックを解除するのを延期するというものです。Biased Lockingはロック予約の概念に似ていますが、これは河内谷氏の論文に詳しく記載されています。

Java Locks: Analysis and Acceleration by Kiyokuni Kawachiya
【Javaのロック処理の分析と高速化 by 河内谷 清久仁 氏】
https://researcher.watson.ibm.com/researcher/files/jp-KAWATIYA/Kawachiya05phd.pdf

これはまた、様々なファイルシステムに見られる便宜的ロック（opportunistic locks、oplocks） にも似ていますし、Mike Burrowsの “How to implement unnecessary mutexes” (In Computer Systems: Theory, Technology and Applications, Dec. 2003) に記述されているスキームや、Christian Siebertのone-sided mutual exclusion primitivesにも似ています。

Computer Systems: Theory, Technology and Applications, Dec. 2003
https://archive.org/details/springer_10.1007-b97622
One-sided Mutual Exclusion A new Approach to Mutual Exclusion Primitives by Christian Siebert
https://www.tu-chemnitz.de/informatik/service/ib/pdf/CSR-04-05.pdf

Biased lockingは、厳密にはCASのレイテンシへの対応です。CASはローカルレイテンシを発生させますが、最新のプロセッサではスケーラビリティに影響を与えないことに注意してください。よく言われる神話として、CASの各操作は「バスに乗る（go on the bus）」というものがあり、インターコネクトが固定の競合リソースであることを考えると、CASを使用するとスケーラビリティが損なわれる可能性があるというものですが、これは誤りです。ラインが既に M-stateになっている場合に、ローカルで、つまりバストランザクションなしで、CASを実行できます。CASは通常、既存の MESI snoop ベースのキャッシュコヒーレンスプロトコルの上に実装されますが、バスに関しては、CASはストアと何ら変わりません。

MESI Protocol
https://en.wikipedia.org/wiki/MESI_protocol

例えば、真の16 wayシステムがあるとします。スレッドを起動して、thread-privateの場所に10億回CAS操作を行い、経過時間を計測します。次に16個のスレッドを起動し、すべてのスレッドがthread-privateの場所にCAS操作した場合、経過時間は同じになります。スレッド同士が干渉したり、妨害したりすることはありません。16 個のスレッドを起動してすべて同じ場所にCAS操作した場合、通常は相互接続のトラフィックのために大規模な速度低下が発生します（この主張の唯一の例外はSunのNiagaraで、これはL2$ がインターコネクトとして機能するため、大規模な共有をさらっと許容できます）。このCASを通常のストアに変更すると、同様に速度低下します。前述の通り、コヒーレンシーバス・トラフィック（coherency bus traffic）の点では、CAS は通常のストアと大差がないためです。CAS に関する誤った情報のいくつかは、おそらくIntelプロセッサ上でのオリジナルのlock:cmpxchg（CAS）の実装に由来するものでしょう。lock:prefix はLOCK#シグナルをアサートし、バスへの排他的アクセスを取得します。もちろん、これはスケーラブルではありませんでした。lock:cmpxchg の後続の実装では、キャッシュコヒーレンシープロトコル（一般的にはスヌープベースの MESI）を利用しており、LOCK#はアサートされません。lock:cmpxchg が LOCK# を駆動するのはある非常に特殊なケース、それはメモリアドレスの位置がずれていて 2 本のキャッシュラインにまたがっているような場合であることに注意してください。最後に、ユニプロセッサでは安全にcmpxchgを利用できますが、マルチプロセッサシステムではlock:cmpxchgを使わなければなりません。lock:cmpxchgの方がレイテンシが大きくなりますが、これはその反面、cmpxchgとは根本的に異なる命令です。lock:cmpxchg は直列化しており、双方向の mfence相当のセマンティクスを提供します（ユニプロセッサではフェンスやバリア命令は必要ありません）。この事実もまたCASがマルチプロセッサシステムでより高価であるという神話につながっているのかもしれませんが、当然ながら、lock:cmpxchgは8CPUのシステムより2CPUのほうがレイテンシは小さくなります。

バス操作の話題から脱線してしまいますが、プログラムの順序でロード操作の後に同じキャッシュラインにストアまたはCASが続くとします。キャッシュラインが発行プロセッサに存在しない場合、ロードはラインをS-stateにするためのrequest-to-shareトランザクションを生成し、ストアやCASが続いてrequest-to-ownトランザクションを生成して、ラインを強制的にM-stateにします。この2回目のトランザクションは、いくつかのプラットフォームでは、ロードの前にprefetch-for-write命令を使用して、ラインを直接M-stateに強制することで回避できます。典型的なクラッシックSMPシステムでは、純粋なread-sharingが非常に効率的であることも言及しておくべきでしょう。すべてのリクエストプロセッサはキャッシュラインをそれぞれのキャッシュに複製できます。しかし、1台のプロセッサでも共有キャッシュラインに書き込みを行うと、その書き込みによってかなりのキャッシュコヒーレンストラフィックが発生します。それは、（write-updateではなく）write-invalidate（書き込み無効化）キャッシュコヒーレンスポリシーを仮定すると、readerはキャッシュラインを継続的に再ロードして、その後にwriterが無効化したキャッシュラインを読み込んでしまうからです。言い換えれば、キャッシュラインへのロードは、他のプロセッサが同じラインからロードしても、そのラインへストアしない場合にはコストが低いということです。他のプロセッサが同時に同じラインにストアしたり、同じラインからロードしたりすることがない場合にのみ、ストアのコストが低くなります（あるキャッシュラインに対して、常に1つのライタしか存在できないという点で、キャッシュコヒーレンシープロトコルとリードライトロックの間にはちょっとした共通点があります。それが、M-stateにあるラインを持つプロセッサです。ラインの複数のreaderが許可されており、もちろんreaderの寿命は書き込みと重ならないようになっています。しかし、従来のread-writeロックとは異なり、キャッシュコヒーレンシープロトコルでは、writerがreaderを無効にできるので、類似点を押し付けすぎることはできません。ひねくれた意味では、コヒーレンシープロトコルはobstruction-freeです）。コヒーレンシー帯域幅は固定で競合するグローバルリソースなので、ローカルレイテンシに加えて、過度の共有トラフィックは全体のスケーラビリティに影響を与え、他のプロセッサ上で実行されているスレッドの進行を阻害します。いわゆるコヒーレンシーミス（例えば、プロセッサP2がキャッシュラインをM-stateにしているところでプロセッサP1でロード操作する場合など）は、通常のミスよりもはるかに遅くなります（Niagaraを除く）。ロックの取得にはロックメタデータのストア（明らかにCAS）が含まれていることにも注意してください。プロセッサP1とP2のスレッドが同じものを繰り返し取得している場合、ロックの取得自体がコヒーレンシートラフィックを生成し、結果としてメタデータを保持しているラインの cache sloshingが発生します。一般的に、クラシックSMPシステムでは、過度のコヒーレンシータラフィックは避けるべきです。しかし、いつも通り、どんなルールにも例外はあります。この場合の例外はSunのNiagaraで、共有をさくっと許容できます。そろそろCAS命令のレイテンシの話に戻るべきですが、この問題がbiased lockingの必要性の動機です。

CAS命令とフェンス（別名バリアまたはMEMBAR）命令は直列化していると言われています。マルチプロセッサシステムでは、直列化命令は、メモリに対してどのストアがロードかを可視化する順序を制御します。このような命令は、現在のほとんどのプロセッサでは、大雑把な方法で実装されていることが多いです。一般的に、直列化命令は、CPUをほぼ停止状態にして、Out-of-Order（OoO）命令を止めて禁止し、ローカルストアバッファが空になるのを待ちます。これは単純なプロセッサでは問題ありませんが、より洗練された OoOプロセッサではかなりのパフォーマンスの低下を招きます。CAS命令やフェンス命令が遅いという根本的な理由はありません。最近までは、CAS命令やフェンス命令の性能が悪くなる傾向がありましたが、この傾向は逆転しつつあるようです。IBMは、Power4とPower5の間でフェンスのレイテンシを大幅に改善しました。同様に、Intelは最近のCore2プロセッサでlock:cmpxchgとmfenceレイテンシの両方で顕著な改善を行いました。

Biased lockingの場合、オブジェクトが共有されていないことがわかっているので、バイアス保持スレッドの動作は、オブジェクトのロックワードとデータの下にあるキャッシュラインをM-stateまたはE-stateに保つと考えるのが妥当です。

興味深いことに、メモリバリアもしくはフェンス命令がCAS命令よりも十分に速い場合、Dekkerのようなメカニズムを使ってbiased lockingの解除を実装できます。

興味深いことに、メモリバリア、つまり「フェンス」命令がCASよりも十分に高速であれば、デッカーのようなメカニズムで偏ったロック解除を実装することができます。より深く掘り下げたい方は、以下のような記事に興味を持たれるかもしれません（この文書の中で、マルチプロセッサシステムの状態遷移コードパスからMEMBARを削除できた、HotSpotで使われた最適化も説明しています）。

Asymmetric Dekker Synchronization
https://app.compendium.com/api/post_attachments/4efee069-668f-41f0-a034-8441c34bfa8e/view

Kenneth RussellとDavid Detlefs（元SunLabs）がOOPSLA’06に掲載された論文で、解除コストを削減するスキームについて述べています。

Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing
https://dl.acm.org/doi/10.1145/1167515.1167496

ここで重要なのは、JSR 133で明確にされされたJavaメモリモデルでは、biased lockingが許可されているという点です。Java言語仕様第3版第17章第4節をご覧ください。Doug LeaのJSR-133 Cookbookは、JVM開発者や好奇心旺盛なJavaプログラマのための優れたリソースです。

JSR-133: JavaTM Memory Model and Thread Specification
https://download.oracle.com/otndocs/jcp/memory_model-1.0-pfd-spec-oth-JSpec/
17.4 Memory Model (Java Language Specification, 3rd edition)
https://docs.oracle.com/javase/specs/jls/se6/html/memory.html#17.4
The JSR-133 Cookbook for Compiler Writers
http://gee.cs.oswego.edu/dl/jmm/cookbook.html

最後に、現在、mark wordには、biased lockingエンコーディングに必要なスレッドIDだけでなく、アイデンティティのhashCode() 値の両方をサポートするスペースがありません。このことを考えると、System.identityHashCode(o)を呼び出すことで、オブジェクトごとにbiased lockingを回避できます。オブジェクトがすでにバイアスされている場合、アイデンティティのHashCodeを割り当てることは失効（バイアス解除）につながり、そうでない場合、hashCode() の割り当てにより、オブジェクトは後続のbiased lockingに対して不適格になります。もちろん、このプロパティは現在の実装の成果物です。

余談ですが、CASのようなアトミックな読み書き変更操作の待ち時間は、Mostly Lock-Free Mallocメカニズムを開発する上での筆者とAlex Garthwaiteを動機づけるものでした。このメカニズムはプロセッサローカルな割り当てをアトミックやスレッドのバインドをプロセッサに要求せずにプロセッサローカルの割り当てを使用するというものです。

Mostly Lock-Free Malloc (ISMM 2002)
https://dl.acm.org/doi/10.1145/512429.512451
https://www.researchgate.net/publication/221032958_Mostly_lock-free_malloc

US07814488 (2002).もご覧ください。

Quickly reacquirable locks
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=7814488.PN.&OS=PN/7814488&RS=PN/7814488
https://patents.google.com/patent/US7814488B1/en