论文:Eliminating Synchronization-Related Atomic Operations with Biased Locking and Bulk Rebiasing
尽量直译。
1. Background and Motivation
A class of optimizations which can be termed lightweight locking [1, 2, 5] are focused on avoiding as much as possible the use of “heavy-weight” operating system mutexes and condition variables to implement Java monitors. The assumption behind these techniques is that most lock acquisitions in real programs are uncontended. Lightweight locking techniques use atomic operations upon monitor entry, and sometimes upon exit, to ensure correct synchronization. These techniques fall back to using OS mutexes and condition variables when contention occurs.
一类称作轻量级锁定的优化,关注的是,尽量避免使用“重量级”的操作系统互斥锁和条件变量来实现 Java 监视器。这些技术背后的假设是,在实际程序中,大多数锁的获取是没有争用的。轻量级锁定技术在进入监视器时使用原子操作,有时退出监视器也使用原子操作,以确保正确的同步。当发生争用时,这些技术又退回使用 OS 的互斥锁和条件变量。
A related class of optimizations which can be termed biased locking [3, 7, 9] rely on the further property that not only are most monitors uncontended, they are only entered and exited by one thread during the lifetime of the monitor. Such monitors may be profitably biased toward the owning thread, allowing that thread to enter and exit the monitor without using atomic operations. If another thread attempts to enter a biased monitor, even if no contention occurs, a relatively expensive bias revocation operation must be performed. The profitability of such an optimization relies on the benefit of the elimination of atomic operations being higher than the penalty of revocation.
一类相关的优化称为偏向锁定,它依赖于进一步的属性,即大多数监视器不仅是没有争用的,而且在它们的生命周期中仅有一个线程进入和退出。这样的监视器可以偏向于拥有它的线程,允许该线程在不使用原子操作的情况下进入和退出这个监视器。如果有另一个线程尝试进入一个偏向监视器,即使没有发生争用,也必须执行代价相对昂贵的偏向撤销操作。这种优化的收益依赖于消除原子操作的好处高于撤销的惩罚。
This paper presents a novel technique for eliminating atomic operations associated with the Java language’s synchronization primitives called store-free biased locking (SFBL). It is similar to, and is inspired by, the lock reservation technique [9] and its refinements [12, 10]. The specific contributions of our work are:
- We build upon invariants preserved by the Java HotSpot VM to eliminate repeated stores to the object header. Store elimination makes it easier to transfer bias ownership between threads.
- We introduce bulk rebiasing and revocation to amortize the cost of per-object bias revocation while retaining the benefits of the optimization.
- An epoch-based mechanism which invalidates previously held biases facilitates the bulk transfer of bias ownership from one thread to another.
本文提出了一种新的技术,用于消除与 Java 语言的同步原语相关的原子操作,这个技术称为无存储偏向锁定(SFBL)。它类似于,也启发于,锁保留技术及其改进。我们工作的具体贡献是: - 我们基于 Java HotSpot VM 保留的不变量,来消除对象头的重复存储。存储消除使得它可以更容易地在线程之间转移偏向所有权。
- 我们引入批量重偏向和撤销,以摊分每个对象撤销偏向的成本,同时保留优化的收益。
- 一个基于 epoch 的机制可以使得之前持有的偏向失效,从而方便地实现偏向所有权从一个线程到另一个线程的批量转移。
2. Overview of Lightweight Locking in the Java HotSpot VM
The Java HotSpot VM uses a two-word object header. The first word is called the mark word and contains synchronization, garbage collection and hash code information. The second word points to the class of the object. See figure 1 for an overview of the layout and possible states of the mark word.
Java HotSpot VM 使用一个双字的对象头。第一个字称为 mark word,包含同步、垃圾收集和哈希码信息。第二个字指向对象的类。有关 mark word 的布局和可能的状态的概述,请参见图1。
Our biased locking technique relies on three invariants. First, the locking primitives in the language must be mostly block-structured. Second, optimized compiled code, if it is produced by the virtual machine, must only be generated for methods with block-structured locking. Third, interpreted execution must detect unstructured locking precisely. We now show how these invariants are maintained in our VM.
我们的偏向锁定技术依赖于三个不变量。首先,语言中的锁原语必须主要是块结构的。其次,优化编译的代码(如果它是由虚拟机生成的)必须仅为具有块结构锁的方法生成。第三,解释执行必须精确地检测非结构化锁定。现在我们展示如何在 VM 中维护这些不变量。(综合论文的描述,我理解的这段的意思是,JVM 必须要保证加锁和解锁成对出现。)
Whenever an object is lightweight locked by a monitorenter bytecode, a lock record is either implicitly or explicitly allocated on the stack of the thread performing the lock acquisition operation. The lock record holds the original value of the object’s mark word and also contains metadata necessary to identify which object is locked. During lock acquisition, the mark word is copied into the lock record (such a copy is called a displaced mark word), and an atomic compare-and-swap (CAS) operation is performed to attempt to make the object’s mark word point to the lock record. If the CAS succeeds, the current thread owns the lock. If it fails, because some other thread acquired the lock, a slow path is taken in which the lock is inflated, during which operation an OS mutex and condition variable are associated with the object. During the inflation process, the object’s mark word is updated with a CAS to point to a data structure containing pointers to the mutex and condition variable.
当一个对象通过 monitorenter 字节码被轻量锁定时,锁记录就会隐式或显式地在线程(正在执行锁获取操作的线程)的栈上分配。锁记录保存了对象 mark word 的原始值,还包含了用于标识被锁对象所需的元数据(元数据就是描述数据的数据)。在获取锁的过程中,将 mark word 复制到锁记录中(这个 mark word 副本叫 displaced mark word),并执行 CAS 操作尝试使对象 mark word 指向锁记录。如果 CAS 成功了,当前线程就拥有了这个锁。如果失败了,因为其它线程获得了锁,则锁膨胀(膨胀过程中,OS 互斥锁和条件变量会与该对象关联)。在锁膨胀的过程中,对象 mark word 用 CAS 更新,以指向包含互斥锁和条件变量指针的数据结构。(这段话介绍了轻量级锁定的过程)
During an unlock operation, an attempt is made to CAS the mark word, which should still point to the lock record, with the displaced mark word stored in the lock record. If the CAS succeeds, there was no contention for the monitor and lightweight locking remains in effect. If it fails, the lock was contended while it was held and a slow path is taken to properly release the lock and notify other threads waiting to acquire the lock.
在解锁操作期间,尝试使用存储在锁记录中的 displaced mark word 来对 mark word(它应该仍然指向锁记录)进行 CAS。如果 CAS 成功了,那就没有发生过监视器争用,并且轻量级锁定仍然有效。如果它失败了,锁在被持有期间被争用了,那么将会采取一个缓慢的方式来正确地释放锁,并且通知正在等待获取锁的其他线程。(这段话介绍了轻量级解锁的过程)
Recursive locking is handled in a straightforward fashion. If during lightweight lock acquisition it is determined that the current thread already owns the lock by virtue of the object’s mark word pointing into its stack, a zero is stored into the on-stack lock record rather than the current value of the object’s mark word. If zero is seen in a lock record during an unlock operation, the object is known to be recursively locked by the current thread and no update of the object’s mark word occurs. The number of such lock records implicitly records the monitor recursion count. This is a significant property to the best of our knowledge not attained by most other JVMs.
递归锁定以一种简单的方式处理。如果在轻量级锁获取过程中,发现对象的 mark word 指向的是当前线程的栈,那就确定了当前线程拥有该锁,则把 0 存入栈上的锁记录,而不是对象 mark word 的当前值中。如果在解锁操作期间,在锁记录中看到 0,则知道该对象被当前线程递归锁定,而且该对象的 mark word 没有发生更新。这样的锁记录的数量相当于隐式地记录了该监视器递归计数。据我们所知,这是一个大多数其它 JVM 没有做到的重要的属性。
3. Store-Free Biased Locking
Assuming the invariants in Section 2, the SFBL algorithm is simple to describe. When an object is allocated and biasing is enabled for its data type (discussed further in Section 4), a bias pattern is placed in the mark word indicating that the object is biasable (figure 1). The Java HotSpot VM uses the value 0x5 in the low three bits of the mark word as the bias pattern.
在第 2 节中不变量的假设下,SFBL 算法描述起来很简单。当一个对象被分配,并且在它的数据类型中启用了偏向(在第 4 节进一步讨论)。放在 mark word 中的偏向模式表明该对象是可偏向的(图一)。Java HotSpot VM 令 mark word 低三位值为 0x5 时,为偏向模式。
The thread ID may be a direct pointer to the JVM’s internal representation of the current thread, suitably aligned so that the low bits are zero. Alternatively, a dense numbering scheme may be used to allow better packing of thread IDs and potentially more fields in the biasable object mark word.
线程 ID 可以是一个直接指针,指向当前线程(适当对齐,使得指针低位为 0)在 JVM 内部的表示。或者,可以使用密集编号方案来更好地打包线程 ID,并可能在可偏向对象 mark word 中包含更多字段。
During lock acquisition of a biasable but unbiased object, an attempt is made to CAS the current thread ID into the mark word’s thread ID field. If this CAS succeeds, the object is now biased toward the current thread, as in figure 2. The current thread becomes the bias owner. The bias pattern remains in the mark word alongside the thread ID.
在锁定获取一个可偏向但无偏向的对象时,使用 CAS 尝试将当前线程 ID 放入 mark word 的 thread ID 字段。如果这个 CAS 操作成功了,该对象现在就偏向于当前线程,如图 2 所示。当前线程成为这个偏向的所有者。偏向模式保留在 mark word 中 thread ID 的旁边。
If the CAS fails, another thread is the bias owner, so that thread’s bias must be revoked. The state of the object will be made to appear as if it had been locked by the bias owner using the JVM’s underlying lightweight locking scheme. To do this, the thread attempting to bias the object toward itself must manipulate the stack of the bias owner. To enable this a global safepoint is reached, at which point no thread is executing bytecodes. The bias owner’s stack is walked and the lock records associated with the object are filled in with the values that would have been produced had lightweight locking been used to lock the object. Next, the object’s mark word is updated to point to the oldest associated lock record on the stack. Finally, the threads blocked on the safepoint are released. Note that if the lock were not actually held at the present moment in time by the bias owner, it would be correct to revert the object back to the “biasable but unbiased” state and re-attempt the CAS to acquire the bias. This possibility is discussed further in section 4.
如果 CAS 失败了,另一个线程是偏向的所有者,因此必须撤销该线程的偏向。对象的状态将显示为它被偏向所有者使用 JVM 的底层轻量级锁定方案锁定。为此,试图使对象偏向自身的线程必须操作偏向所有者的栈。要实现这一点,需要达到一个全局安全点,此时没有线程执行字节码。偏向所有者的栈被遍历,与对象关联的锁记录被填充进(如果使用轻量级锁定来锁对象,将会产生的)值。接下来,更新对象的 mark word,以指向栈上最古老的关联锁记录。最后,在安全点上阻塞的线程被释放。请注意,如果当前偏向所有者没有实际持有锁,那么将对象恢复到“可偏向但无偏向”的状态并重新尝试CAS以获得偏向是正确的。第4节将进一步讨论这种可能性。(这段描述了偏向失败后的做法。)
If the CAS succeeded, subsequent lock acquisitions examine the object’s mark word. If the object is biasable and the bias owner is the current thread, the lock is acquired with no further work and no updates to the object header; the displaced mark word in the lock record on the stack is left uninitialized, since it will never be examined while the object is biasable. If the object is not biasable, lightweight locking and its fallback paths are used to acquire the lock. If the object is biasable but biased toward another thread, the CAS failure path described in the previous paragraph will be taken, including the associated bias revocation.
如果 CAS 成功了,后面的锁获取将检查对象的 mark word。如果对象是可偏向的,并且偏向的所有者是当前线程,那么锁将被获取,而不需要进一步的工作,也不需要更新对象头;栈上的锁记录中 displaced mark word 未初始化,因为当对象是可偏向的时,它将永远不会被检查。如果对象是不可偏向的,则使用轻量级锁及其回退方式来获取锁。如果对象是可偏向的,但偏向于另一个线程,则将采用上一段描述的 CAS 失败处理方式,包括相关的偏向撤销。(这段描述了偏向成功后,后面锁获取时的做法。最后一句例外,最后一句针对的是一个新的想获取偏向锁的线程。)
When an object is unlocked, the state of its mark word is tested to see if the bias pattern is still present. If it is, the unlock operation succeeds with no other tests. It is not even necessary to test whether the thread ID is equal to the current thread’s ID. If another thread had attempted to acquire the lock while the current thread was actually holding the lock and not just the bias, the bias revocation process would have ensured that the object’s mark word was reverted to the unbiasable state.
当一个对象被解锁时,将测试其 mark word 的状态,以确定是否仍然处在偏向模式。如果是,解锁操作成功,没有其他测试。不需要测试是否 thread ID 等于当前线程的 ID。如果另一个线程尝试过获取锁,而且这个锁是当前线程实际正在持有的而不是仅仅是偏向的。另一个线程撤销偏向的过程确保对象的 mark word 恢复到不可偏向状态。
Since the SFBL unlock path does no error checking, the correctness of the unlock path hinges on the interpreter’s detection of unstructured locking. The lock records in interpreter activations ensure that the body of the monitorexit operation will not be executed if the object was not locked in the current activation. The guarantee of matched monitors in compiled code implies that no error checking is required in the SFBL unlock path in compiled code.
由于 SFBL 解锁方式不进行错误检查,所以解锁方式的正确性取决于解释器对非结构化锁的检测。解释器活动中的锁记录,确保当前活动中的对象没有被锁定,将不会执行 monitorexit 操作的主体。已编译代码中对监视器匹配的担保,意味着在已编译代码中的 SFBL 解锁方式不需要错误检查。
Figure 2 shows the state transitions of the mark word of an object under the biased locking algorithm. The bulk rebiasing edge, which is described further in sections 4 and 5, is only an effective, not an actual, transition and does not necessarily involve an update to the object’s mark word. Recursive locking edges, which update the on-stack lock records but not the mark word, and the heavyweight locking state, which involves contention with one or more other threads, are omitted for clarity.
图 2 显示了在偏向锁定算法下对象的 mark word 的状态转换。在第 4 节和第 5 节中进一步描述的批量重偏向仅仅是一种有效的转换,而不是实际的转换,并且不需要更新对象的 mark word。为了清晰起见,这里省略了递归锁定(更新栈上的锁记录,但不更新 mark word)和重量级锁定状态(涉及与一个或多个其他线程的争用)。
4. Bulk Rebiasing and Revocation
Analysis of execution logs of SFBL for the SPECjvm98, SPECjbb2000, SPECjbb2005 and SciMark benchmark suites yields two insights. First, there are certain objects for which biased locking is obviously unprofitable, such as producer-consumer queues where two or more threads are involved. Such objects necessarily have lock contention, and many such objects may be allocated during a program’s execution. It would be ideal to be able to identify such objects and disable biased locking only for them. Second, there are situations in which the ability to rebias a set of objects to another thread is profitable, in particular when one thread allocates many objects and performs an initial synchronization operation on each, but another thread performs subsequent work on them.
对 SPECjvm98、SPECjbb2000、SPECjbb2005 和 SciMark 基准测试套件的 SFBL 执行日志的分析得出了两个结论。首先,对于某些对象,偏向锁定显然是无利可图的,例如涉及两个或多个线程的生产者-消费者队列。这样的对象必然存在锁争用,并且在程序执行过程中可能会分配许多这样的对象。能够识别这样的对象并仅为它们禁用偏向锁定是理想的。其次,在某些情况下,将一组对象重偏向到另一个线程是有好处的,特别是当一个线程分配许多对象并对每个对象执行一个初始同步操作,而另一个线程对这些对象执行后续操作时。(这段描述了,批量撤销和批量重偏向针对的场景。注意:HotSpot VM 的批量撤销和批量重偏向针对的都是同类对象的操作。)
When attempting to selectively disable biased locking, we must be able to identify objects for which it is unprofitable. If one were able to associate an object with its allocation site, one might find patterns of shared objects; for example, all objects allocated at a particular site might seem to be shared between multiple threads. Experiments indicate this correlation is present in many programs[6]. Being able to selectively disable the insertion of the biasable mark word at that site would be ideal. However, due to its overhead, allocation site tracking is to the best of our knowledge not currently exploited in production JVMs.
当尝试有选择地禁用偏向锁定时,我们必须能够识别出不适合偏向的对象。如果能够将对象与其分配位置关联起来,就可能发现共享对象的模式;例如,在特定位置上分配的所有对象似乎都在多个线程之间共享。实验表明,这种相关性存在于许多程序中。能够有选择地在该位置上禁用可偏向 mark word 的插入将是理想的。但是,由于它的开销,就我们所知,还没有 JVM 产品使用分配位置追踪。
We have found empirically that selectively disabling SFBL for a particular data type is a reasonable way to avoid unprofitable situations. We therefore amortize the cost of rebiasing and individual object bias revocation by performing such rebiasing and revoking in bulk on a per-data-type basis.
我们已经从经验中发现,对特定数据类型选择性地禁用 SFBL 是避免无利可图情况的合理方法。因此,我们通过在每个数据类型的基础上执行这种批量重偏向和撤销,来平摊重偏向和单个对象偏向撤销的成本。
Heuristics are added to the basic SFBL algorithm to estimate the cost of individual bias revocations on a per-data-type basis. When the cost exceeds a certain threshold, a bulk rebias operation is attempted. All biasable instances of the data type have their bias owner reset, so that the next thread to lock the object will reacquire the bias. Any biasable instance currently locked by a thread may optionally have its bias revoked or left alone.
在基本的 SFBL 算法中添加了启发式算法,以估计基于每个数据类型的单个偏向撤销成本。当成本超过某个阈值时,将尝试进行批量重偏向操作。数据类型的所有可偏向实例的偏向所有者都将重置,以便下一个锁定对象的线程将重新获得偏向。任何当前被线程锁定的可偏向实例都可以有选择地撤销或保持其偏向。(在 JDK8 HotSpot VM 中,一个类型的单个偏向撤销次数达到一定的阈值(默认 20 次),就可以对该类型对象进行批量重偏向。如果该类型距上次批量重偏向的时间超过设定阈值(默认 25000 毫秒,即 25 秒),则会重置单个偏向撤销的计数,后面计数重新达到 20 后能够再次进行批量重偏向。)
If bias revocations for individual instances of a given data type persist after one or more bulk rebias operations, a bulk revocation is performed. The mark words of all biasable instances of the data type are reset to the lightweight locking algorithm’s initial value. For currently-locked and biasable instances, the appropriate lock records are written to the stack, and their mark words are adjusted to point to the oldest lock record. Further, SFBL is disabled for any newly allocated instances of the data type.
如果给定数据类型的单个实例的偏向撤销在一次或多次批量重偏向操作之后仍然存在,则执行批量撤销。该数据类型的所有可偏向实例的 mark word 被重置为轻量级锁定算法的初始值。对于当前已锁定并且是可偏向的实例,将适当的锁记录写入栈,并调整它们的 mark word 以指向最旧的锁记录。此外,SFBL 将禁用该数据类型任何新分配实例的可偏向。(在 JDK8 HotSpot VM 中,简单来说,一个类型的对象在短时间(默认 25 秒)内频繁发生偏向撤销(默认 40 次),就会触发该类型的批量撤销。)
The most obvious way of finding all instances of a certain data type is to walk through the object heap, which is how these techniques were initially implemented (Section 5 describes the current implementation). Despite the computational expense involved, bulk rebiasing and revocation are surprisingly effective.
查找某个数据类型的所有实例的最明显的方法是遍历对象堆,这就是这些技术最初是如何实现的(第5部分描述了当前的实现)。尽管涉及到计算开销,但批量重偏向和撤销的效率惊人。
Figure 3 illustrates the benefits of the bulk revocation and rebiasing heuristics compared to the basic biased locking algorithm. The javac sub-benchmark from SPECjvm98 computes many identity hash codes, forcing bias revocation of the affected objects since there are no bits available to store the hash code in the biasable state (see figure 1). Bulk revocation benefits this and similar situations, here in particular because our early implementations performed relatively inefficient bias revocation in this case. SPECjbb2000 and SPECjbb2005 transfer a certain number of objects between threads as each warehouse is added to the benchmark, not enough to impact scores greatly but enough to trigger the bulk revocation heuristic. The addition of bulk rebiasing, which is then triggered at the time of addition of each warehouse, reclaims the gains to be had. Note that the addition of both bulk revocation and rebiasing does not reduce the peak performance of biased locking compared to the basic algorithm without these operations. This is discussed further in Section 7.
图3说明了与基本的偏向锁定算法相比,批量撤销和再偏向启发式算法的优点。SPECjvm98 的 javac 子基准计算了许多对象哈希码,强制取消受影响对象的偏向,因为在可偏向状态下没有可用的位来存储哈希码(见图 1)。批量撤销有利于这种情况和类似的情况,尤其是在这里,因为我们的早期实现在这种情况下执行的偏向撤销效率相对较低。SPECjbb2000 和 SPECjbb2005 在线程之间传输一定数量的对象,因为每个数据仓库都被添加到基准中,这并不足以影响分数,但足以触发批量撤销。添加批量重偏向,然后在每个仓库添加时触发,收回要获得的收益。请注意,与不进行这些操作的基本算法相比,添加批量撤销和重偏向并没有降低偏向锁定的峰值性能。这将在第7节进一步讨论。
图35. Epoch-Based Bulk Rebiasing and Revocation
Though walking the object heap to implement bulk rebias and revocation algorithms is workable for relatively small heaps, it does not scale well as the heap grows. To address this problem, we introduce the concept of an epoch, a timestamp indicating the validity of the bias. As shown in figure 1, the epoch is a bitfield in the mark word of biasable instances. Each data type has a corresponding epoch as long as the data type is biasable. An object is now considered biased toward a thread T if both the bias owner in the mark word is T, and the epoch of the instance is equal to the epoch of the data type.
虽然遍历对象堆来实现批量重偏向和撤销算法对于相对较小的堆是可行的,但是它不能随着堆的增长而很好地扩展。为了解决这个问题,我们引入了 epoch 的概念,一个表示偏向有效性的时间戳。如图 1 所示,epoch 是可偏向实例的 mark word 中的一个位字段。每个可偏向的数据类型都有相应的 epoch。如果一个对象的 mark word 中的偏向所有者是 T,而且对象的 epoch 等于其数据类型的 epoch,则认为这个对象现在是偏向于线程 T 的。
With this scheme, bulk rebiasing of objects of class C becomes much less costly. We still stop all mutator threads at a safepoint; without stopping the mutator threads we cannot reliably tell whether or not a biased object is currently locked. The thread performing the rebiasing:
- Increments the epoch number of class C. This is a fixed-width integer, with the same bit-width in the class as in the object headers. Thus, the increment operation may cause wrapping, but as we will argue below, this does not compromise correctness.
- Scans all thread stacks to locate objects of class C that are currently locked, updating their bias epochs to the new current bias epoch for class C. Alternatively, based on heuristic consideration, these objects’ biases could be revoked.
使用这种方案,类 C 的对象的批量重偏向的成本将大大降低。我们仍然会在一个安全点停止所有的 mutator 线程;如果不停止 mutator 线程,我们就无法可靠地判断当前是否锁定了一个偏向对象。线程执行重偏向:
- 增加类 C 的 epoch。这是一个固定宽度的整数,类中的位宽与对象头中的位宽相同。因此,增加操作可能会导致溢出,但正如我们将在下面讨论的,这并不会影响正确性。
- 扫描所有线程的栈,以定位类 C 中当前被锁定的对象,将它们的 epoch 更新为类 C 当前的 epoch。或者,基于启发式的考虑,可以撤销这些对象的偏向。
No heap scan is necessary; objects whose epoch numbers were not changed will, for the most part, now have a different epoch number than their class, and will be considered to be in the biasable but unbiased state.
不需要堆扫描那些 epoch 没有改变的对象,在大多数情况下,如果对象的 epoch 值和它的类的 epoch 值不同,则可以认为这个对象处于可偏向但未偏向的状态。(如果对象的 epoch 和 其类型的 epoch 不同,则可以直接对该对象进行重偏向。)
The pseudocode for the lock-acquisition operation then looks much like:
伪码
Above we made the qualification that incrementing a class’s bias epoch will “for the most part” rebias all objects of the given class. This qualification is necessary because of the finite width of the epoch field, which allows integer wrapping. If the epoch field is N bits wide, and X is an object of type T, then if 2ˆN bulk rebiasing operations for class T occur without any lock operation updating the bias epoch of X to the current epoch, then it will appear that X is again biased in the current epoch, that is, that its bias is valid. Note that this is purely a performance concern – it is perfectly permissible, from a correctness viewpoint, to consider X biased. It may mean that if a thread other than the bias holder attempts to lock X, an individual bias revocation operation may be required. But a sufficiently large value of N can decrease the frequency of this situation significantly: objects that are actually locked between one epoch and the next have their epoch updated to the current epoch, so this situation only occurs with infrequently-locked objects. Further, we could arrange for operations that naturally visit all live objects, namely garbage collection, to normalize lock states, converting biased objects with invalid epochs into biasable-but-unbiased objects. (If done in a stop-world collection this can be done with non-atomic stores; in a concurrent marker, however, the lock word would have to be updated with an atomic operation, since the marking thread would potentially compete with mutator threads to modify the lock word.) Therefore, wrapping issues could also be prevented by choosing N large enough to make it highly likely that a full-heap garbage-collection would occur before 2ˆN bulk rebias operations for a given type can occur.
上面我们做了这样的限定:增加一个类的 epoch 将“在大部分情况下”重偏向该类的所有对象。这个限定是必要的,因为 epoch 字段的宽度是有限的,它允许整数溢出。如果 epoch 字段是 N 位宽,X 是一个类型 T 的对象,然后如果对类 T 有 2^N 次批量重偏向操作,而且没有任何锁定操作更新 X 的 epoch 到当前类的 epoch,那么就会出现 X 在当前 epoch 再次是已偏向的,也就是说它的偏向是有效的。请注意,这纯粹是一个性能问题—从正确性的角度来看,完全允许考虑 X 已偏向。这可能意味着,如果一个非偏向持有者的线程试图锁定 X,可能需要一个单独的偏向撤销操作。但是足够大的 N 值会显著降低这种情况的发生频率:实际上在一个 epoch 和下一个 epoch 之间被锁定的对象会将它们的 epoch 更新到当前的 epoch,所以这种情况只会发生在不经常被锁定的对象上。此外,我们可以安排自然访问所有活动对象的操作,即垃圾收集,以规范化锁状态,将带有无效 epoch 的有偏向对象转换为可偏向但未偏向的对象。(如果是在一个 stop-world 收集中完成的,那么可以使用非原子操作更新;然而,在并发标记中,lock word 必须用原子操作更新,因为标记线程可能会与 mutator 线程竞争来修改 lock word。因此,溢出问题可以通过选择足够大的 N 来阻止,使得很有可能一个全堆垃圾收集发生在一个给定类型发生 2^N 次批量重偏向之前。
In practice, wrapping of the epoch field can be ignored. Benchmarking has not uncovered any situations where individual bias revocations are provoked due to epoch overflow. The current implementation of biased locking in the Java HotSpot VM normalizes object headers during GC, so the mark words of biasable objects with invalid epochs are reverted to the unbiased state. This is done purely to reduce the number of mark words preserved during GC, not to counteract epoch overflow.
在实践中,可以忽略 epoch 字段的溢出。基准测试还没有发现任何情况下,单独偏向撤销是由 epoch 溢出引起的。Java HotSpot VM 中偏向锁定的当前实现在 GC 期间将对象头进行规范化,因此带有无效 epoch 的可偏向对象的 mark word 将恢复到无偏向状态。这样做纯粹是为了减少在 GC 期间已偏向 mark word 的数量,而不是为了抵消 epoch 溢出。
It is a straightforward extension to support bulk revocation of biases of a given data type. Recall that in bulk revocation, unlike bulk rebiasing, it is desired to completely disable the biased locking optimization for the data type, instead of allowing the object to be potentially rebiased to a new thread. Rather than incrementing the epoch in the data type, the “biasable” property for that data type may be disabled, and a dynamic test of this property added to the lock sequence:
伪码
它是一个支持批量撤销给定数据类型的偏向的简单扩展。回想一下,在批量撤销中,与批量重偏向不同,我们希望完全禁用数据类型的偏向锁定优化,而不是允许对象可能重偏向到一个新线程。与在数据类型中递增 epoch 不同,该数据类型的 “biasable” 属性可能会被禁用,并且该属性的一个动态测试将被添加到锁定代码中:(通过在锁定时判断类的可偏向属性来判断对象偏向的有效性。)
This variant of the lock sequence is the one currently implemented in the Java HotSpot VM.
锁代码的这种变体是目前在 Java HotSpot VM 中实现的。
Epoch-based rebiasing and revocation may also be extended to rebias objects at a granularity between the instance and class level. For example, we might distinguish between objects of a given class based on their allocation site; JIT-generated allocation code could be modified to insert an allocation site identifier in the object header. Each allocation site could have its own epoch, and the locking sequence could check the appropriate epoch for the object:
伪码
基于 epoch 的重偏向和撤销也可以扩展到实例级和类级之间的粒度上的可偏向对象。例如,我们可以根据分配位置来区分给定类的对象;可以修改 jit 生成的分配代码,以便在对象头中插入分配位置标识符。每个分配位置都可以有自己的 epoch,锁序列可以检查对象对应的 epoch:
To simplify the allocation path for new instances as well as storage of the per-data-type epochs, a prototype mark word is kept in each data type. This is the value to which the mark word of new instances will be set. The epoch is stored in the prototype mark word as long as the prototype is biasable.
为了简化新实例的分配方法和每个数据类型 epoch 的存储,在每个数据类型中都保留一个原型标记字。这是新实例的标记字将被设置的值。只要原型是可偏向的,epoch 就存储在原型标记字中。
In practice, a single logical XOR operation in assembly code computes the bitwise difference between the instance’s mark word and the prototype mark word of the data type. A sequence of tests are performed on the result of the XOR to determine whether the bias is held by the current thread and currently valid, whether the epoch has expired, whether the data type is no longer biasable, or whether the bias is assumed not held, and the system reacts appropriately. Listing 4 shows the complete SPARC assembly code for the lock acquisition path of SFBL with epochs.
在实践中,汇编代码中的一个逻辑异或操作按位计算实例的标记字和数据类型的原型标记字之间的差异。测试序列进行异或的结果,确定偏向被当前线程持有并且是有效的,epoch 是否已经过期,是否数据类型不再允许偏向,或偏向是否认为被持有,并且系统会做出适当的反应。清单 4 显示了带有 epoch 的 SFBL 锁获取方法的完整SPARC 汇编代码。
网友评论