Up Top

Thread の待機処理の枠組み : SpinLock, Mux による処理


概要(Summary)

これらは ParkEvent を用いて構築されたシンプルなスピンロック, 及び Mutex 実装. ごく短い critical section に対してのみ使われることになっている.

具体的には, 以下の 2種類のロック/アンロック関数が用意されている.

(#Under Construction)

    ((cite: hotspot/src/share/vm/runtime/thread.cpp))
    // Internal SpinLock and Mutex
    // Based on ParkEvent

    // Ad-hoc mutual exclusion primitives: SpinLock and Mux
    //
    // We employ SpinLocks _only for low-contention, fixed-length
    // short-duration critical sections where we're concerned
    // about native mutex_t or HotSpot Mutex:: latency.
    // The mux construct provides a spin-then-block mutual exclusion
    // mechanism.
    //
    // Testing has shown that contention on the ListLock guarding gFreeList
    // is common.  If we implement ListLock as a simple SpinLock it's common
    // for the JVM to devolve to yielding with little progress.  This is true
    // despite the fact that the critical sections protected by ListLock are
    // extremely short.
    //
    // TODO-FIXME: ListLock should be of type SpinLock.
    // We should make this a 1st-class type, integrated into the lock
    // hierarchy as leaf-locks.  Critically, the SpinLock structure
    // should have sufficient padding to avoid false-sharing and excessive
    // cache-coherency traffic.

Thread::SpinAcquire(), Thread::SpinRelease()

引数で指定された int 型のメモリ領域を mutex として使用する.

Thread::muxAcquire(), Thread::muxRelease()

引数で指定された intptr_t 型のメモリ領域を mutex として使用する.

最下位ビット以外のビットは, ロック待ちしているスレッドのポインタを格納する.

(なお, 現在の実装では, Thread オブジェクトの _MuxEvent フィールドにある ParkEvent オブジェクトを使用している)

Thread::muxAcquire() で寝る前に OnList を非ゼロにしておき, Thread::muxRelease() で起こした対象の OnList をゼロにクリアする. 起きたスレッドは, OnList が非ゼロのままなら再び眠りにつく.

    ((cite: hotspot/src/share/vm/runtime/thread.cpp))
    // muxAcquire and muxRelease:
    //
    // *  muxAcquire and muxRelease support a single-word lock-word construct.
    //    The LSB of the word is set IFF the lock is held.
    //    The remainder of the word points to the head of a singly-linked list
    //    of threads blocked on the lock.
    //
    // *  The current implementation of muxAcquire-muxRelease uses its own
    //    dedicated Thread._MuxEvent instance.  If we're interested in
    //    minimizing the peak number of extant ParkEvent instances then
    //    we could eliminate _MuxEvent and "borrow" _ParkEvent as long
    //    as certain invariants were satisfied.  Specifically, care would need
    //    to be taken with regards to consuming unpark() "permits".
    //    A safe rule of thumb is that a thread would never call muxAcquire()
    //    if it's enqueued (cxq, EntryList, WaitList, etc) and will subsequently
    //    park().  Otherwise the _ParkEvent park() operation in muxAcquire() could
    //    consume an unpark() permit intended for monitorenter, for instance.
    //    One way around this would be to widen the restricted-range semaphore
    //    implemented in park().  Another alternative would be to provide
    //    multiple instances of the PlatformEvent() for each thread.  One
    //    instance would be dedicated to muxAcquire-muxRelease, for instance.
    //
    // *  Usage:
    //    -- Only as leaf locks
    //    -- for short-term locking only as muxAcquire does not perform
    //       thread state transitions.
    //
    // Alternatives:
    // *  We could implement muxAcquire and muxRelease with MCS or CLH locks
    //    but with parking or spin-then-park instead of pure spinning.
    // *  Use Taura-Oyama-Yonenzawa locks.
    // *  It's possible to construct a 1-0 lock if we encode the lockword as
    //    (List,LockByte).  Acquire will CAS the full lockword while Release
    //    will STB 0 into the LockByte.  The 1-0 scheme admits stranding, so
    //    acquiring threads use timers (ParkTimed) to detect and recover from
    //    the stranding window.  Thread/Node structures must be aligned on 256-byte
    //    boundaries by using placement-new.
    // *  Augment MCS with advisory back-link fields maintained with CAS().
    //    Pictorially:  LockWord -> T1 <-> T2 <-> T3 <-> ... <-> Tn <-> Owner.
    //    The validity of the backlinks must be ratified before we trust the value.
    //    If the backlinks are invalid the exiting thread must back-track through the
    //    the forward links, which are always trustworthy.
    // *  Add a successor indication.  The LockWord is currently encoded as
    //    (List, LOCKBIT:1).  We could also add a SUCCBIT or an explicit _succ variable
    //    to provide the usual futile-wakeup optimization.
    //    See RTStt for details.
    // *  Consider schedctl.sc_nopreempt to cover the critical section.
    //

処理の流れ (概要)(Execution Flows : Summary)

Thread::SpinAcquire()

Thread::SpinAcquire()
-> Atomic::cmpxchg() と待機を繰り返す.
   待機処理では以下のどれかが呼び出される.
   * os::NakedYield()
   * os::PlatformEvent::park()
   * SpinPause())

Thread::SpinRelease()

Thread::SpinRelease()
-> OrderAccess::fence() でメモリバリアを張った後,
   引数(adr)で指定された箇所を 0 で上書きする(= ロックを解放する)だけ

Thread::muxAcquire()

Thread::muxAcquire()
-> Atomic::cmpxchg_ptr() によるスピンロックと
   os::PlatformEvent::park() による待機が繰り返される

Thread::muxRelease()

Thread::muxRelease()
-> Atomic::cmpxchg_ptr()
-> os::PlatformEvent::unpark()

処理の流れ (詳細)(Execution Flows : Details)

Thread::SpinAcquire()

See: here for details

os::NakedYield() (Linux の場合)

See: here for details

os::NakedYield() (Solaris の場合)

See: here for details

os::NakedYield() (Windows の場合)

See: here for details

SpinPause() (Linux x86-32 の場合)

See: here for details

SpinPause() (Linux x86-64 の場合)

See: here for details

SpinPause() (Linux Sparc の場合)

(#Under Construction)

SpinPause() (Linux zero の場合)

See: here for details

SpinPause() (Solaris Sparc の場合)

See: here for details

SpinPause() (Solaris x86 の場合)

(#Under Construction)

SpinPause() (Windows x86 の場合)

See: here for details

Thread::SpinRelease()

See: here for details

Thread::muxAcquire()

See: here for details

Thread::muxAcquireW()

(#Under Construction) (どこからも使われてなさそうだが...)

Thread::muxRelease()

See: here for details


This document is available under the GNU GENERAL PUBLIC LICENSE Version 2.