链接：https://pan.baidu.com/s/1RByUnHpoZX5M1rXhm0tQXg 

提取码：4r0v 

 

4 · Jeremy Manson, William Pugh and Sarita Adve

Initially, x == y == 0

Thread 1 Thread 2

1: r1 = x; 4: x = 1

2: y = 1; 5: r3 = y

3: r2 = x;

r1 == r2 == r3 == 0 is legal behavior

Fig. 1. Incorrect Synchronization Can Lead To Surprising Results

tions – this is an informal definition of what we shall refer to as the program order.

This model basically reflects an interleaving of the actions in each thread; under

sequential consistency, a read must return the value written most recently to the

location being read in the total order.

While it is an intuitive extension of the single threaded model, sequential consistency restricts the use of many system optimizations. In general, a sequentially

consistent system will not have much freedom to reorder memory statements within

a thread, even if there are no conventional data or control dependences between

the two statements. This can be a serious limitation, since many important optimizations involve reordering program statements.

Figure 1 provides a simple example of how a lack of sequential consistency can

result in surprising behavior. As we shall see, this program is incorrectly synchronized – shared variables are accessed concurrently without synchronization. Under

sequential consistency, either the write or x or the write to y must occur before the

reads in statements 3 and 5. Thus, it would seem that either r2 or r3 should be

1. One common compiler optimization involves having the value read for r1 reused

for r2: they are both reads of x with no intervening write by Thread 1. If this

optimization is applied, then the behavior r1 == r2 == r3 == 0 could result.

Recently, hardware designers have developed techniques that alleviate some of the

limitations of sequential consistency by reordering accesses speculatively [Gharachorloo et al. 1991; Ranganathan et al. 1997]. The reordered accesses are committed

only when they are known to not be visible to the programmer. Compiler techniques

to determine when reorderings are safe have also been proposed [Shasha and Snir

1988; Sura et al. 2002], but are not yet comprehensively evaluated or implemented

in commercial compilers.

A common method to overcome the limitations of sequential consistency is the

use of relaxed memory models, which allow more optimizations [Dubois et al. 1986b;

Gharachorloo et al. 1990a; IBM 1983; May et al. 1994; Sites and Witek 1995; Weaver

and Germond 1994]. Many of these models were originally motivated by hardware

optimizations and are described in terms of low-level system attributes such as

buffers and caches. Generally, these models have been hard to reason with and, as

we show later, do not allow enough implementation flexibility either. Having said

this, Java’s memory model is a relaxed one.

To achieve both programming simplicity and implementation flexibility, alternative models, referred to as data-race-free models [Adve 1993; Adve and Hill 1990;

1993] or properly-labeled models [Gharachorloo 1996; Gharachorloo et al. 1992],

have been proposed. This approach exploits the observation that good programming practice dictates that programs be correctly synchronized (data-race-free); a

data race is often a symptom of a bug. The data-race-free models formalize correct

ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.