The Java Memory Modellowast;
Jeremy Manson and William Pugh Department of Computer Science University of Maryland, College Park College Park, MD
{jmanson, pugh}@cs.umd.edu
Sarita V. Adve
Department of Computer Science University of Illinois at Urbana-Champaign Urbana-Champaign, IL
ABSTRACT
This paper describes the new Java memory model, which has been revised as part of Java 5.0. The model specifies the legal behaviors for a multithreaded program; it defines the semantics of multithreaded Java programs and partially determines legal implementations of Java virtual machines and compilers.
The new Java model provides a simple interface for cor- rectly synchronized programs – it guarantees sequential con- sistency to data-race-free programs. Its novel contribution is requiring that the behavior of incorrectly synchronized programs be bounded by a well defined notion of causality. The causality requirement is strong enough to respect the safety and security properties of Java and weak enough to allow standard compiler and hardware optimizations. To our knowledge, other models are either too weak because they do not provide for sufficient safety/security, or are too strong because they rely on a strong notion of data and control dependences that precludes some standard compiler transformations.
Although the majority of what is currently done in compil- ers is legal, the new model introduces significant differences, and clearly defines the boundaries of legal transformations. For example, the commonly accepted definition for control dependence is incorrect for Java, and transformations based on it may be invalid.
In addition to providing the official memory model for Java, we believe the model described here could prove to be a useful basis for other programming languages that currently lack well-defined models, such as C and C#.
Categories and Subject Descriptors: D.3.1 [Program- ming Languages]: Formal Definitions and Theory; D.3.0 [Programming Languages]: Standards; F.3.2 [Logics
lowast;Jeremy Manson and William Pugh were supported by National Science Foundation grants CCR-9619808, ACI- 9720199 and CCR-0098162, and a gift from Sun Microsys- tems. Sarita Adve was supported in part by an Alfred P. Sloan research fellowship.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
POPLrsquo;05, January 12–14, 2005, Long Beach, California, USA. Copyright 2005 ACM 1-58113-830-X/05/0001 ...$5.00.
and Meanings of Programs]: Operational Semantics
General Terms: Design, Languages, Standardization
Keywords: Concurrency, Java, Multithreading, Memory Model
INTRODUCTION
The memory model for a multithreaded system specifies how memory actions (e.g., reads and writes) in a program will appear to execute to the programmer, and specifically, which value each read of a memory location may return. Ev- ery hardware and software interface of a system that admits multithreaded access to shared memory requires a memory model. The model determines the transformations that the system (compiler, virtual machine, or hardware) can apply to a program written at that interface. For example, given a program in machine language, the memory model for the machine language / hardware interface will determine the optimizations the hardware can perform.
For a high-level programming language such as Java, the memory model determines the transformations the compiler may apply to a program when producing bytecode, the trans- formations that a virtual machine may apply to bytecode when producing native code, and the optimizations that hardware may perform on the native code.
The model also impacts the programmer; the transfor- mations it allows (or disallows) determine the possible out- comes of a program, which in turn determines which de- sign patterns for communicating between threads are legal. Without a well-specified memory model for a programming language, it is impossible to know what the legal results are for a program in that language. For example, a mem- ory model is required to determine what, if any, variants of double checked locking [37] are valid within a particular language.
Background
Over the last two decades, there has been a tremendous amount of work in the area of memory models at the hard- ware interface [2, 3, 4, 12, 14, 17, 31, 40, 43], but little at the programming language level. Programming languages present two challenges that do not occur in the hardware world. First, many programming languages, such as Java, have strong safety and security properties that must be re- spected. Second, the ability of a compiler to perform global and subtle analysis in order to transform a program is es- sentially unlimited, while hardware systems tend to use a more circumscribed scope in performing optimizations.
Previous work [33, 34] has shown that the original seman- tics for multithreaded Java [18, sect;17] had serious problems. To address these issues, the Java memory model has recently undergone a major revision. The new model now provides greater flexibility for implementors, a clear notion of what it means to write a correct program, and clear semantics for
both correct and incorrect programs. Despite this funda- mental change, it is largely, although not entirely, consistent with previous good programming practice and
全文共23045字，剩余内容已隐藏，支付完成后下载完整资料
Java内存模型*
杰里米曼森和威廉普格 萨里塔V.Adve
计算机科学系 计算机科学系
马里兰大学，学院公园 伊利诺伊大学厄巴纳 - 香槟分校
学院公园 厄巴纳 - 香槟，伊利诺伊州
{jmanson，pugh}@cs.umd.edu sadve@cs.uiuc.edu
抽象
本文描述了新的Java内存模型，其中已被修改为Java 5.0的一部分。该模型指定多线程程的法律行为;它定义多线程Java程序的语义和部分确定Java虚拟机的合法实现和编译器。新的Java模型为正确提供了一个简单的界面同步程序 - 它保证了顺序一致性到无数据竞争的节目。其新颖的贡献程序受到明确的因果关系概念的限制。因果关系的要求足够强大，以尊重Java的安全和安全属性和足够弱允许标准的编译器和硬件优化。至我们的知识，其他模式要么太弱，因为他们没有提供足够的安全/保障，或者也是如此强大，因为它们依赖于强大的数据和概念控制依赖，排除一些标准的编译器转换。尽管目前大部分工作都是在编译器中完成的是合法的，新模式引入了重大差异，并明确界定了法律转型的界限。例如，普遍接受的控制定义依赖对Java不正确，并且基于转换它可能是无效的。除了提供官方的内存模型之外Java，我们相信这里描述的模型可以证明是一个目前其他编程语言的有用基础缺乏定义明确的模型，如C 和C＃。类别和主题描述符：D.3.1 [编程语言]：形式定义和理论; D.3.0[编程语言]：标准; F.3.2 [逻辑]。
*杰里米曼森和威廉普格支持美国国家科学基金会授予CCR-9619808，ACI-9720199和CCR-0098162，以及Sun Microsystems的礼物。萨里塔Adve部分支持阿尔弗雷德体育斯隆研究奖学金。允许制作全部或部分作品的数字或硬拷贝个人或课堂使用授予，不收费，但副本是不是为盈利或商业利益而制作或发行的，并且是复制品请在第一页上注明本通知和全部引用。要另外复制到重新发布，在服务器上发布或重新发布到列表，需要事先具体说明许可和/或费用。POPL#39;05，2005年1月12 - 14日，美国加利福尼亚州长滩市。
Copyright 2005 ACM 1-58113-830-X / 05/0001 ... $ 5.00。
和[程序的含义]：操作语义
一般条款：设计，语言，标准化
关键字：并发性，Java，多线程，内存，模型
1.引言
多线程系统的内存模型指定如何在程序中执行内存操作（例如，读取和写入）似乎会对程序员执行，具体而言，每个读取内存位置的值可能会返回。一切允许的系统的硬件和软件接口。
多线程访问共享内存需要一个内存模型。该模型确定了转换系统（编译器，虚拟机或硬件）可以应用到在该界面编写的程序。例如，给出机器语言中的程序，内存模型机器语言/硬件接口将决定优化硬件可以执行的操作。对于像Java这样的高级编程语言来说，内存模型决定了编译器的转换当生成字节码时，可能适用于程序中的转换虚拟机可能适用于字节码当生成本机代码时，以及优化硬件可以在本地代码上执行。该模型也影响程序员;转变它允许（或不允许）确定可能的结果的程序，这又决定了哪个设计线程之间进行通信的模式是合法的。
如果没有一个编程良好的内存模型语言，就不可能知道什么是法律效果用于该语言的程序。例如，一个内存模型是需要确定什么，如果有的话，变体双重检查锁定[37]在特定范围内有效语言。
1.1背景
在过去的二十年里，1这是一个巨大的硬件内存模型领域的工作量界面[2,3,4,12,14,17,31,40,43]，但很少编程语言级别。编程语言提出了硬件中不存在的两个挑战
世界。首先，许多编程语言（如Java）具有强大的安全性和安全性，必须受到尊重。其次，编译器执行全局性的能力本质上是为了改造一个程序而进行细微的分析无限制，而硬件系统倾向于使用执行优化的范围更大。378先前的工作[33,34]已经表明了原始的语义对于多线程Java [18，sect;17]有严重的问题。为了解决这些问题，最近有Java内存模型经历了重大修改。新模型现在提供它意味着要编写一个正确的程序，并为其清除语义正确和不正确的程序。尽管这是根本改变，但很大程度上，虽然不完全一致与以前良好的编程习惯和现有的JVM实施和硬件。内存模型必须在易用性之间取得平衡对于程序员和实现灵活性系统设计师。最容易理解的模型，顺序一致性[26]，指定了内存操作必须以单个总订单一次执行一个;给定线程的动作必须以这个总的顺序出现在它们出现在程序中的顺序相同（称为程序订单）。顺序一致性本身是否合适高级语言程序员的模型是一个主题辩论：它使程序员可以更轻松地写出微妙的以及复杂的不使用显式的并发算法同步。不幸的是，这样的算法是通常设计或实施不正确，有些会认为几乎所有的程序员都应该感到灰心从写作微妙和复杂的同步免费并发算法。
顺序一致性大大限制了使用许多编译器和硬件转换。一般来说，顺序一致性限制任何一对的重新排序一个线程中的内存语句，即使没有。这可能是一个严重的限制，因为很多重要的优化涉及重新排序程序语句。即使是普遍的子表达式无处不在的优化消除和冗余读取消除可以看作是重新排序：每个普通表达式的评估在概念上“移动”到评估点首次。在顺序一致的系统中，没有编译器或处理器重排序应该可见给程序员。最近，硬件设计师已经开发了技术，这减轻了顺序一致性的一些限制通过推测访问重新排序[16,35]。重新排序只有在知道它们的情况下才进行访问对程序员不可见。编译器技术以确定何时重新排序是安全的也已提出[38,42]，但尚未全面评估或在商业编译器中实现。克服顺序局限性的常用方法一致性是使用宽松的内存模型，其中允许更多的优化[12,17,19,31,40,43]。许多这些模型最初是由硬件优化激发的并用低级系统来描述属性，如缓冲区和缓存。一般来说，这些模型一直难以推理，正如我们后面所展示的那样不允许有足够的实施灵活性。实现编程简单和实现灵活性，替代模型，称为数据无损模型[2,4,6]或适当标记模型[14,15]具有被提出。这种方法利用了这一观察。
良好的编程习惯决定了程序的正确性同步（无数据竞争）;数据竞赛往往是一个
最初，x == y == 0
线程1线程2
1：r2 = x; 3：r1 = y
2：y = 1; 4：x = 2
r2 == 2，r1 == 1违反顺序一致性。随着顺序一致性，结果r2 == 2，r1 == 1是不可能的。这样的结果将意味着声明4之前1（因为r2 == 2），1之前2（因为程序顺序），2来到3之前（因为r1 == 1），3来了前4（由于节目顺序），所以4前4。顺序一致性禁止这样的循环。然而，如果硬件或编译器重新排列指令在每个线程中，语句3可能不会在4之前，和/或1可能不会在2之前，从而得出上述结果可能。因此，顺序一致性限制了重新排序即使它们不是数据或控制，也可以在线程中执行指令依赖。图1：违反顺序一致性。一个bug的症状。无数据竞争的模型正确无误程序是那些没有数据竞争和保证的程序这样的顺序一致性的简单语义程式。为了充分实现灵活性，这些模型不要为包含的程序提供任何保证数据竞赛。这种方法允许标准硬件和编译器优化，同时提供一个简单的模型根据广泛接受的做法编写的程序。
1.2 Java内存模型
新的Java模型采用无数据竞争的方法正确的程序 - 正确的程序是那些数据无竞争;这样的程序保证了顺序一致性。不幸的是，如果一个模型离开了语义不明确的程序未指定，它允许违反安全以及Java程序所需的安全属性。修改工作的一个重要贡献就是展示Java的安全性和安全性要求禁止一类包含数据竞赛和执行的执行以前没有表征过。挑战是在没有的情况下表征和禁止这类处决禁止标准的编译器和硬件转换或使模型过于复杂。在先前轻松模型，这样的执行或者被允许，或者只是被允许禁止执行传统的控制和数据依赖。我们表明后一种方法限制了标准编译器优化，并不适用于Java。修订后的Java模型基于一种新技术在允许标准的同时禁止必要的执行优化。我们的技术迭代地构建法律执行。在每次迭代中，它提交一组内存操作;如果行为发生在某些行为良好的行为中，可以采取行动执行还包含之前提交的操作迭代。对“良好行为”的仔细定义确保禁止适当的执行并允许标准的编译器转换。至我们的知识，这是拥有此属性的唯一模型。本文重点介绍普通读取的语义并在Java内存中写入，锁定和变量变量模型。它还涵盖了交互的内存语义与外部世界和无限执行。对于空间原因，我们省略了对两个重要问题的讨论379Java内存模型：最终字段的处理和最终化/ 垃圾收集。我们讨论模型的其余部分详细;完整的规范在其他地方可用[20]。Java模型的修订过程涉及不断来自更广泛的Java社区的反馈和参与;我们将读者引用到Java内存模型邮件列出档案的更多信息的演变模型[21]。虽然这个模型是为Java开发的，但很多所解决的问题适用于所有多线程语言。我们希望这里介绍的工作可以充分利用以提供安全和效率的正确平衡为将来的编程语言。
2.对JAVA存储器的要求
模型我们的主要设计目标是在两者之间提供平衡
- 足够的易用性
- 转换和优化
用于当前（和理想的未来）编译器和硬件。鉴于当前的硬件和编译器采用转换违反顺序一致性，这是目前不可能提供顺序一致的编程Java的模型。因此，Java的内存模型一个轻松的模式。Java的需求的详细描述模型和他们的进化可以在别处找到[30]。这里我们提供一个简要的概述。
2.1正确同步的程序
程序员很难推断具体的问题硬件和编译器转换。为了便于使用，我们因此请指定模型，以免程序员不知道推理硬件或编译器转换或甚至是正确同步代码的正式语义。我们遵循无数据竞争的方法来正确定义同步程序（无数据竞争）和正确的语义对于这样的程序（顺序一致性）。下列定义使这些概念正式化。
bull;冲突访问：读取或写入变量是对该变量的访问。两次访问相同的共享字段或数组元素被认为是如果至少有一次访问是写入，则会发生冲突。
bull;同步操作：同步操作包括锁定，解锁，读取易失性变量，以及写入易失性变量。
bull;同步顺序：每次执行一个程序与同步顺序相关联，是所有同步操作的全部顺序。去没有错误的数据竞争程序正确，我们被允许只考虑那些同步命令也符合程序的顺序和在哪里阅读到一个volatile变量返回写入的值到在同步读取之前排序的订购。后者对这些要求同步顺序被明确地强加为同步其余的订单一致性要求的论文。
bull;同步 - 按顺序：对于两个操作x和y,我们使用x→y表示x与...同步年。监视器m上的解锁操作与同步所有对m执行的锁定操作通过任何线程，后续是根据什么来定义的到同步顺序。同样，写一个到一个易变的变量v与所有后续的同步通过任何线程读取v。还有额外的与Java中的边缘同步[20]，这些都没有讨论这里为了简洁起见。
bull;在订单之前发生：对于两个行为x和y，我们使用x→y表示x在y之前发生[25]。发生 之前是程序订单的传递式关闭并与订单同步。
bull;数据竞赛：两次访问x和y形成数据竞赛在执行一个程序时，如果它们来自不同的程序线程，它们发生冲突，而且它们不是按顺序排列的之前发生。
bull;正确同步或无数据传输程序[4，6]：一个程序被说成是正确同步的或者只有在全部顺序的情况下才能实现数据竞争程序的一致执行没有数据比赛。Java模型的第一个要求是确保顺序正确同步或数据自由度的一致性如上所定义的程序。程序员然后需要只担心代码转换会产生影响如果这些方案包含数据的话，他们的方案的结果比赛。例如，图1中的代码被错误地同步。任何顺序一致的代码执行包含对x和y的冲突访问以及这些冲突访问不是按发生前排序（因为没有程序中的同步）。一种制作这个程序的方法正确同步是将x和y声明为volatile变量;那么该程序可以保证顺序一致结果与Java模型。
2.2不正确的精简空间保证
程式修订工作的大部分努力以及我们的重点在此，了解不正确同步的要求码。之前的离开语义的策略对于未指定的不正确程序是不一致的Java的安全和安全保证。这样的策略已经被用于一些先前的语言。例如，Ada简单将非同步代码定义为“错误”[1]。推理在这背后是因为这样的代码是不正确的（在一些级别），发生时不应作出任何保证。这是类似于一些语言在数组中使用的策略边界溢出 - 可能出现不可预知的结果，并且它程序员有责任避免这些情况。上述方法不适合写作安全和安全的代码。在理想的世界里，每个程序员会一直写出正确的代码。在我们的世界里，程序经常包含错误;这不仅是因为这个原因代码行为不端，但它也可以让攻击者违反程序中的安全假设（缓冲区也是如此）溢出）。我们之前的工作已经描述了危险这种情况更详细[28]。程序语义必须完全定义：如果程序员不知道他们的代码在做什么，他们不会：
最初
x == y == 0
线程1线程2
r1 = x; r2 = y;
y = r1; x = r2;
错误地同步，但我们想要禁止r1 == r2 == 42。图2：空气不足结果能够知道他们的代码做错了什么。第二Java模型的广泛需求是提供一个清晰的以及代码应该如何表现的权威语义不
全文共7042字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15814]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
