Movatterモバイル変換


[0]ホーム

URL:


Contents |Prev |Next |IndexThe Java Virtual Machine Specification


CHAPTER 8

Threads and Locks


This chapter details the low-level actions that may be used to explain the interactionof Java virtual machine threads with a shared main memory. It has been adapted with minimal changes from Chapter 17 of the first edition ofThe Java Language Specification, by James Gosling, Bill Joy, and Guy Steele.


8.1 Terminology and Framework

Avariable is any location within a program that may be stored into. This includes not only class variables and instance variables, but also components of arrays. Variablesare kept in amain memory that is shared by all threads. Because it is impossiblefor one thread to access parameters or local variables of another thread, it does not matter whether parameters and local variables are thought of as residing in the shared main memory or in the working memory of the thread that owns them.

Every thread has aworking memory in which it keeps its ownworking copy of variables that it must use or assign. As the thread executes a program, it operates on these working copies. The main memory contains themaster copy of every variable. There are rules about when a thread is permitted or required to transfer the contents of its working copy of a variable into the master copy or vice versa.

The main memory also containslocks; there is one lock associated with each object. Threads may compete to acquire a lock.

For the purposes of this chapter, the verbsuse,assign,load,store,lock, andunlock name actions that a thread can perform. The verbsread,write,lock, andunlock name actions that the main memory subsystem can perform. Each of these operations is atomic (indivisible).

Ause orassign operation is a tightly coupled interaction between a thread's execution engine and the thread's working memory. Alock orunlock operation is a tightly coupled interaction between a thread's execution engine and the main memory. But the transfer of data between the main memory and a thread's working memory is loosely coupled. When data is copied from the main memory to a working memory, two actions must occur: aread operation performed by the main memory, followed some time later by a correspondingload operation performed by the working memory. When data is copied from a working memory to the main memory, two actions must occur: astore operation performed by the working memory, followed some time later by a correspondingwrite operation performed by the main memory. There may be some transit time between main memory and a working memory, and the transit time may be different for each transaction; thus, operations initiated by a thread on different variables may be viewed by another thread as occurring in a different order. For each variable, however, the operations in main memory on behalf of any one thread are performed in the same order as the corresponding operations by that thread. (This is explained in greater detail later.)

A single thread issues a stream ofuse,assign,lock, andunlock operations as dictated by the semantics of the program it is executing. The underlying Java virtual machine implementation is then required additionally to perform appropriateload,store,read, andwrite operations so as to obey a certain set of constraints, explained later. If the implementation correctly follows these rules and the programmer follows certain other rules of programming, then data can be reliably transferred between threads through shared variables. The rules are designed to be "tight" enough to make this possible, but "loose" enough to allow hardware and software designers considerable freedom to improve speed and throughput through such mechanisms as registers, queues, and caches.

Here are the detailed definitions of each of the operations:

Thus, the interaction of a thread with a variable over time consists of a sequence ofuse,assign,load, andstore operations. Main memory performs aread operation for everyload and awrite operation for everystore. A thread's interactions with a lock over time consist of a sequence oflock andunlock operations. All the globally visible behavior of a thread thus comprises all the thread's operations on variables and locks.


8.2 Execution Order and Consistency

The rules of execution order constrain the order in which certain events may occur. There are four general constraints on the relationships among actions:

The last rule may seem trivial, but it does need to be stated separately and explicitly for completeness. Without the rule, it would be possible to propose a set of actions by two or more threads and precedence relationships among the actions that would satisfy all the other rules but would require an action to follow itself.

Threads do not interact directly; they communicate only through the shared main memory. The relationships between the actions of a thread and the actions of main memory are constrained in three ways:

Most of the rules in the following sections further constrain the order in which certain actions take place. A rule may state that one action must precede or follow some other action. Note that this relationship is transitive: if actionA must precede actionB, andB must precedeC, thenA must precedeC. The programmer must remember that these rules are theonly constraints on the ordering of actions; if no rule or combination of rules implies that actionA must precede actionB, then a Java virtual machine implementation is free to perform actionB before actionA, or to perform actionB concurrently with actionA. This freedom can be the key to good performance. Conversely, an implementation is not required to take advantage of all the freedoms given it.

In the rules that follow, the phrasing "B must intervene betweenA andC" means that actionB must follow actionA and precede actionC.


8.3 Rules About Variables

LetT be a thread andV be a variable. There are certain constraints on the operations performed byT with respect toV :

Provided that all the constraints in Sections8.3,8.6, and8.7 are obeyed, aload orstore operation may be issued at any time by any thread on any variable, at the whim of the implementation.

There are also certain constraints on theread andwrite operations performed by main memory:

Note that this last rule appliesonly to actions by a thread on thesame variable. However,there is a more stringent rule forvolatile variables(§8.7).


8.4 Nonatomic Treatment of and Variables

If adouble orlong variable is not declaredvolatile, then for the purposes ofload,store,read, andwrite operations it is treated as if it were two variables of 32 bits each; wherever the rules require one of these operations, two such operationsare performed, one for each 32-bit half. The manner in which the 64 bits of adouble orlong variable are encoded into two 32-bit quantities and the order of the operations on the halves of the variables are not defined byThe Java Language Specification.

This matters only because aread orwrite of adouble orlong variable may be handled by an actual main memory as two 32-bitread orwrite operations that may be separated in time, with other operations coming between them. Consequently, if two threads concurrently assign distinct values to the same shared non-volatiledouble orlong variable, a subsequent use of that variable may obtain a value that is not equal to either of the assigned values, but rather some implementation-dependent mixture of the two values.

An implementation is free to implementload,store,read, andwrite operations fordouble andlong values as atomic 64-bit operations; in fact, this is strongly encouraged. The model divides them into 32-bit halves for the sake of currently popular microprocessors that fail to provide efficient atomic memory transactions on 64-bit quantities. It would have been simpler for the Java virtual machine to define all memory transactions on single variables as atomic; this more complex definition is a pragmatic concession to current hardware practice. In the future this concession may be eliminated. Meanwhile, programmers are cautioned to explicitly synchronize access to shareddouble andlong variables.


8.5 Rules About Locks

LetT be a thread andL be a lock. There are certain constraints on the operations performed byT with respect toL:

With respect to a lock, thelock andunlock operations performed by all the threads are performed in some total sequential order. This total order must be consistent with the total order on the operations of each thread.


8.6 Rules About the Interaction of Locks and Variables

LetT be any thread, letV be any variable, and letL be any lock. There are certain constraints on the operations performed byT with respect toV andL:


8.7 Rules for Variables

If a variable is declared volatile, then additional constraints apply to the operations of each thread. LetT be a thread and letV andW be volatile variables.


8.8 Prescient Store Operations

If a variable is not declaredvolatile, then the rules in the previous sections are relaxed slightly to allowstore operations to occur earlier than would otherwise be permitted. The purpose of this relaxation is to allow optimizing compilers to performcertain kinds of code rearrangement that preserve the semantics of properly synchronized programs, but might be caught in the act of performing memory operationsout of order by programs that are not properly synchronized.

Suppose that astore byT ofV would follow a particularassign byT ofV according to the rules of the previous sections, with no interveningload orassign byT ofV. Then thatstore operation would send to the main memory the value that theassign operation put into the working memory of threadT. The special rule allows thestore operation actually to occur before theassign operation instead, if the following restrictions are obeyed:

This last property inspires us to call such an earlystore operationprescient: it has to know ahead of time, somehow, what value will be stored by theassign that it should have followed. In practice, optimized compiled code will compute such values early (which is permitted if, for example, the computation has no side effects and throws no exceptions), store them early (before entering a loop, for example), and keep them in working registers for later use within the loop.


8.9 Discussion

Any association between locks and variables is purely conventional. Locking any lock conceptually flushesall variables from a thread's working memory, and unlocking any lock forces the writing out to main memory ofall variables that the thread has assigned. That a lock may be associated with a particular object or a class is purely a convention. For example, in some applications it may be appropriate always to lock an object before accessing any of its instance variables;synchronized methods are a convenient way to follow this convention.In other applications, it may suffice to use a single lock to synchronize access to a large collection of objects.

If a thread uses a particular shared variable only after locking a particular lock and before the corresponding unlocking of that same lock, then the thread will read the shared value of that variable from main memory after thelock operation, if necessary, and will copy back to main memory the value most recently assigned to that variable before theunlock operation. This, in conjunction with the mutual exclusion rules for locks, suffices to guarantee that values are correctly transmitted from one thread to another through shared variables.

The rules for volatile variables effectively require that main memory be touched exactly once for eachuse orassign of a volatile variable by a thread, and that main memory be touched in exactly the order dictated by the thread execution semantics. However, such memory operations are not ordered with respect toread andwrite operations on nonvolatile variables.


8.10 Example: Possible Swap

Consider a class that has class variablesa andb and methodshither andyon:

class Sample {    int a = 1, b = 2;    void hither() {    a = b;    }    void yon()     b = a;    }}
Now suppose that two threads are created and that one thread callshither while the other thread callsyon. What is the required set of actions and what are the orderingconstraints?

Let us consider the thread that callshither. According to the rules, this thread must perform ause ofb followed by anassign ofa. That is the bare minimum required to execute a call to the methodhither.

Now, the first operation on variableb by the thread cannot beuse. But it may beassign orload. Anassign tob cannot occur because the program text does not call for such anassign operation, so aload ofb is required. Thisload operation by the thread in turn requires a precedingread operation forb by the main memory.

The thread may optionallystore the value ofa after theassign has occurred. If it does, then thestore operation in turn requires a followingwrite operation fora by the main memory.

The situation for the thread that callsyon is similar, but with the roles ofa andb exchanged.

The total set of operations may be pictured as follows:





Here an arrow from actionA to actionB indicates thatA must precedeB.

In what order may the operations by the main memory occur? The only constraint is that it is not possible both for thewrite ofa to precede theread ofa and for thewrite ofb to precede theread ofb, because the causality arrows in the diagram would form a loop so that an action would have to precede itself, which is not allowed. Assuming that the optionalstore andwrite operations are to occur, there are three possible orderings in which the main memory might legitimately perform its operations. Letha andhb be the working copies ofa andb for thehither thread, letya andyb be the working copies for theyon thread, and letma andmb be the master copies in main memory. Initiallyma=1 andmb=2. Then the three possible orderings of operations and the resulting states are as follows:

Thus, the net result might be that, in main memory,b is copied intoa,a is copied intob, or the values ofa andb are swapped; moreover, the working copies of the variables might or might not agree. It would be incorrect, of course, to assume that any one of these outcomes is more likely than another. This is one place in which the behavior of a program is necessarily timing-dependent.

Of course, an implementation might also choose not to perform thestore andwrite operations, or only one of the two pairs, leading to yet other possible results.

Now suppose that we modify the example to usesynchronized methods:

class SynchSample {    int a = 1, b = 2;    synchronized void hither() {    a = b;    }    synchronized void yon()     b = a;    }}
Let us again consider the thread that callshither. According to the rules, this thread must perform alock operation (on the instance of classSynchSample on which thehither method is being called) before the body of methodhither is executed. This is followed by ause ofb and then anassign ofa. Finally, anunlock operation on that same instance ofSynchSample must be performed after the body of methodhither completes. That is the bare minimum required to execute a call to the methodhither.

As before, aload ofb is required, which in turn requires a precedingread operation forb by the main memory. Because theload follows thelock operation, the correspondingread must also follow thelock operation.

Because anunlock operation follows theassign ofa, astore operation ona is mandatory, which in turn requires a followingwrite operation fora by the main memory. Thewrite must precede theunlock operation.

The situation for the thread that callsyon is similar, but with the roles ofa andb exchanged.

The total set of operations may be pictured as follows:





Thelock andunlock operations provide further constraints on the order of operations by the main memory; thelock operation by one thread cannot occur between thelock andunlock operations of the other thread. Moreover, theunlock operations require that thestore andwrite operations occur. It follows that only two sequences are possible:

While the resulting state is timing-dependent, it can be seen that the two threads will necessarily agree on the values ofa andb.


8.11 Example: Out-of-Order Writes

This example is similar to that in the preceding section, except that one method assigns to both variables and the other method reads both variables. Consider a class that has class variablesa andb and methodsto andfro:

class Simple {    int a = 1, b = 2;    void to() {    a = 3;    b = 4;    }    void fro()     System.out.println("a= " + a + ", b=" + b);    }}
Now suppose that two threads are created and that one thread callsto while the other thread callsfro. What is the required set of actions and what are the ordering constraints?

Let us consider the thread that callsto. According to the rules, this thread must perform anassign ofa followed by anassign ofb. That is the bare minimum required to execute a call to the methodto. Because there is no synchronization, it is at the option of the implementation whether or not tostore the assigned values back to main memory! Therefore, the thread that callsfro may obtain either1 or3 for the value ofa and independently may obtain either2 or4 for the value ofb.

Now suppose thatto issynchronized butfro is not:

class SynchSimple {    int a = 1, b = 2;    synchronized void to() {    a = 3;    b = 4;    }    void fro()     System.out.println("a= " + a + ", b=" + b);    }}
In this case the methodto will be forced tostore the assigned values back to main memory before theunlock operation at the end of the method. The methodfro must, of course, usea andb (in that order) and so mustload values fora andb from main memory.

The total set of operations may be pictured as follows:



Here an arrow from actionA to actionB indicates thatA must precedeB.

In what order may the operations by the main memory occur? Note that the rules do not require thatwritea occur beforewriteb; neither do they require thatreada occur beforereadb. Also, even though methodto is synchronized, methodfro is not synchronized, so there is nothing to prevent theread operations from occurring between thelock andunlock operations. (The point is that declaring one methodsynchronized does not of itself make that method behave as if it were atomic.)

As a result, the methodfro could still obtain either1 or3 for the value ofa and independently could obtain either2 or4 for the value ofb. In particular,fro might observe the value1 fora and4 forb. Thus, even thoughto does anassign toa and then anassign tob, thewrite operations to main memory may be observed by another thread to occur as if in the opposite order.

Finally, suppose thatto andfro are bothsynchronized:

class SynchSynchSimple {    int a = 1, b = 2;    synchronized void to() {    a = 3;    b = 4;    }    synchronized void fro()     System.out.println("a= " + a + ", b=" + b);    }}
In this case, the actions of methodfro cannot be interleaved with the actions of methodto, and sofro will print either "a=1, b=2" or "a=3, b=4".


8.12 Threads

Threads are created and managed by the classesThread andThreadGroup. CreatingaThread object creates a thread, and that is the only way to create a thread. When the thread is created, it is not yet active; it begins to run when itsstart method is called.


8.13 Locks and Synchronization

There is a lock associated with every object. The Java programming language does not provide a way to perform separatelock andunlock operations; instead, they are implicitly performed by high-level constructs that always arrange to pair such operationscorrectly. (The Java virtual machine, however, provides separatemonitorenter andmonitorexit instructions that implement thelock andunlock operations.)

Thesynchronized statement computes a reference to an object; it then attempts to perform alock operation on that object and does not proceed further until thelock operation has successfully completed. (Alock operation may be delayed because the rules about locks can prevent the main memory from participating until some other thread is ready to perform one or moreunlock operations.) After the lock operation has been performed, the body of thesynchronized statement is executed. Normally, a compiler for the Java programming language ensures that thelock operation implemented by amonitorenter instruction executed prior to the execution of the body of thesynchronized statement is matched by an unlock operation implemented by amonitorexit instruction whenever thesynchronized statement completes, whether completion is normal or abrupt.

Asynchronized method automatically performs alock operation when it is invoked; its body is not executed until thelock operation has successfully completed. If the method is an instance method, it locks the lock associated with the instance for which it was invoked (that is, the object that will be known asthis during execution of the method's body). If the method isstatic, it locks the lock associated with theClass object that represents the class in which the method is defined. If execution of the method's body is ever completed, either normally or abruptly, anunlock operation is automatically performed on that same lock.

Best practice is that if a variable is ever to be assigned by one thread and used or assigned by another, then all accesses to that variable should be enclosed insynchronized methods orsynchronized statements.

Although a compiler for the Java programming language normally guarantees structured use of locks (seeSection 7.14, "Synchronization"), there is no assurance that all code submitted to the Java virtual machine will obey this property. Implementations of the Java virtual machine are permitted but not required to enforce both of the following two rules guaranteeing structured locking.

LetT be a thread andL be a lock. Then:

  1. The number oflock operations performed byT onL during a method invocation must equal the number ofunlock operations performed byT onL during the method invocation whether the method invocation completes normally or abruptly.

  2. At no point during a method invocation may the number ofunlock operations performed byT onL since the method invocation exceed the number oflock operations performed byT onLsince the method invocation.
In less formal terms, during a method invocation everyunlock operation onL must match some precedinglock operation onL.

Note that the locking and unlocking automatically performed by the Java virtual machine when invoking a synchronized method are considered to occur during the calling method's invocation.


8.14 Wait Sets and Notification

Every object, in addition to having an associated lock, has an associated wait set, which is a set of threads. When an object is first created, its wait set is empty.

Wait sets are used by the methodswait,notify, andnotifyAll of classObject. These methods also interact with the scheduling mechanism for threads.

The methodwait should be invoked for an object only when the current thread (call itT ) has already locked the object's lock. Suppose that threadT has in fact performedNlock operations on the object that have not been matched byunlock operations on that same object. Thewait method then adds the current thread to the wait set for the object, disables the current thread for thread scheduling purposes, and performsNunlock operations on the object to relinquish the lock on it. Locks having been locked by threadT on objects other than the oneT is to wait on are not relinquished. The threadT then lies dormant until one of three things happens:

The threadT is then removed from the wait set and reenabled for thread scheduling. It then locks the object again (which may involve competing in the usual manner with other threads); once it has gained control of the lock, it performsN -1 additionallock operations on that same object and then returns from the invocation of thewait method. Thus, on return from thewait method, the state of the object's lock is exactly as it was when thewait method was invoked.

Thenotify method should be invoked for an object only when the current thread has already locked the object's lock, or anIllegalMonitorStateException will be thrown. If the wait set for the object is not empty, then some arbitrarily chosen thread is removed from the wait set and reenabled for thread scheduling. (Of course, that thread will not be able to proceed until the current thread relinquishes the object's lock.)

ThenotifyAll method should be invoked for an object only when the current thread has already locked the object's lock, or anIllegalMonitorStateException will be thrown. Every thread in the wait set for the object is removed from the wait set and reenabled for thread scheduling. (Those threads will not be able to proceed until the current thread relinquishes the object's lock.)


Contents |Prev |Next |Index

Virtual Machine Specification
Copyright © 1999 Sun Microsystems, Inc.All rights reserved
Please send any comments or corrections through ourfeedback form


[8]ページ先頭

©2009-2025 Movatter.jp