NWEN303 Concurrent Programming
7 Critical section Coherent data Monitors, condition variables
and Synchronized keyword
Marco Servetto VUW
● ● ●
– – –
● ●
Person: a worker while executing a task The room is a metaphor for an object
Critical Section
The main Idea of the critical section:
a room, that can host only one person at the time,
that person can
assume the room is in a tied-up (coherent) state mess up with the stuff in the room,
leave the room in any tied-up (coherent) state.
● ● ●
– – –
● ●
Person: a worker while executing a task The room is a metaphor for an object
Critical Section
The main Idea of the critical section:
a room, that can host only one person at the time,
that person can
assume the room is in a tied-up (coherent) state mess up with the stuff in the room,
leave the room in any tied-up (coherent) state.
● ● ●
– – –
● ●
Critical Section
The main Idea of the critical section:
a room, that can host only one person at the time,
that person can
assume the room is in a tied-up (coherent) state mess up with the stuff in the room,
leave the room in any tied-up (coherent) state.
Person: a worker while executing a task
The room is a metaphor for a set of objects/values that together represents a self contained entity in the domain of your application.
●
●
Critical Section
class Dragon{
int x=5; int y=5; …}
In the example of last lecture, the room is composed of the Dragon, x and y coordinates.
In general any chunk of objects that represent a self contained entity in the domain of your application.
Usually there is a “container” or “root” object of such group.
●
●
●
●
●
Critical Section – representative
In Java, you need to choose a representative object of such group.
The “container” or “root” object of such group is a good candidate
A private otherwise invisible and unused object is another possible choice
In the case of the example, it could be the dragon itself. Then we can use synchronized!
…
synchronized(dragon){ dragon.x=dragon.x+10; dragon.y=dragon.y+3; }
…
synchronized
synchronized(dragon){ dragon.x=dragon.x+10; dragon.y=dragon.y+3; }
The block of code is the action on the room,(not the room itself) and the key is the dragon object.
If you “own” (not just have) the dragon, you can enter in the room using the door (the synchronized block)
However, Java is not preventing you to enter from the roof, or from under the floor.
That is, you still can write dragon.x=… anywhere else and thus violate the dragon room.
●
●
●
●
Synchronized block – objects as locks
Any object in Java can also act as a “lock” and can be used for the synchronized block.
Runnable threads own locks; other objects does not own locks!
To own a lock, the thread execute a synchronized block during its execution.
a lock is released when the thread exits from the synchronized block (or wait() is called, see later)
Debunking misconception number 1 of synchronize:
having the object (in a field or local variable) has nothing to do with having the lock of that object.
●
●
●
●
●
–
●
“Synchronized” and “Reentrant”
A Thread that owns a lock can enter any
number of synchronized blocks that require that
lock, so
public void run() { synchronized(obj){ synchronized(obj){
●
…;}}
is possible, and behaves exactly the same as
public void run() { synchronized(obj){
●
…;}
This is very useful for recursive methods.
Synchronized methods You can declare a method Synchronized.
It is just compiled away and turned into a synchronized block over this
private synchronized void putTreasureDown(){ /*some code*/}
private static void putTreasureDown(){//equivalent code synchronized(this){/*some code*/}}
Same for static methods, but it would synchronize over
the corresponding class object
private static synchronized void putTreasureDown(){ /*some code*/}
private static void putTreasureDown(){//equivalent code synchronized(MyClass.class){/*some code*/}}
● ●
●
Critical Section and coherent data
The main Idea of the critical section: a room, that can host only one person at the time, that person can
assume the room is in a tied-up (coherent) state mess up with the stuff in the room,
leave the room in any tied-up (coherent) state.
●
– – –
●
It is easy to see the critical section and think on a single operation over data, so the operations and the data (the room) tends to be sort of confused in our mind; but we can have more then one operation onto the same room.
●
Critical Section and coherent data
The most important part in the design, is to identify the data that must be kept coherent and that often offers some formal invariant.
Internal coherence: the data is self coherent, so for example x and y on a Point are coordinates that are actually intended to be on the same conceptual point
Historical coherence: no update is lost (see bank example of last time)
●
●
●
●
The monitor is a design pattern, or if you prefer an idea.
The idea of hiding such coherent data inside an object, where all the operations that you can perform over that data are encoded as methods.
Then, the methods of this object will have sequential execution with respect to the data of the monitor itself.
To implement a monitor in java, synchronized methods/blocks can be used in order to ensure a proper “observably sequential” order of execution for such operations.
●
●
Monitor
●
●
Note that both updating the data and reading the data is an operation.
Moreover, reading the data, reason about it and update the data depending on such original read is an operation (all of it atomically).
So, we can end up with a ton of operations.
Using the monitor design patter in a strict way may generate sort of god objects.
●
●
Monitor
●
An object with only private fields, and all the public methods are synchronized. (No static fields allowed.)
The reachable object graph from those fields is either immutable or defensively cloned.
In all methods, inputs and outputs are transitively immutable data structures (output can be mutable defensively cloned).
No other part of the program ever uses that object for a synchronized block.
– You can ensure nothing is synchronizing over the same lock by avoiding synchronized methods and instead using synchronized blocks over a private object stored in a field that is never exposed/used for anything else. Using multiple objects in this way you can emulate multiple condition variables as in the original monitor concept.
Here you can find an article/opinion about how to improve on the way java manages monitors.
http://www.javaworld.com/article/2077769/core-java/better-monitors- for-java.html
●
●
●
●
Monitor in Java
Monitors
Related to objects in OO languages, but designed as a high level synchronization mechanism. In 1974
Used to encapsulate synchronization logic.
If properly used, the monitor concept as we have seen is powerful enough to ensure a correct handling of critical sections.
Monitors and condition variables
Monitors also offer another kind of support for synchronization: Condition variables.
Historically, monitors hold multiple condition variables, and every condition variable is a “thing” held by a single monitor.
In Java every object can be synchronized over, so it can play the role of a monitor, that have a single associated condition variable that is identified with the object itself.
A condition variable has an associated wait queue and two operations:
waitC(conditionVariable)
By calling waitC, a worker enqueues itself and blocks.
When it becomes blocked, it releases exclusive access over the monitor of such condition variable
signalC(conditionVariable)
By calling signalC, a worker unblocks a waiting process, if there is one. Has no effect if queue is empty.
Monitors and condition variables
waitC(conditionVariable)
By calling waitC, a worker enqueues itself and blocks.
When it becomes blocked, it releases exclusive access over the monitor of such condition variable
—
So, using wait VIOLATES the concept of sequential ordering for the operations of the monitor
—
The main use case for wait is that some process may want to act on a resource only when some condition is verified, so if it is not the right time to act, the process will wait.
Later, when another process modifies the state of the monitor, it will signal to awake whoever is waiting. It has some similarity with the observer pattern.
Monitors and condition variables
signalC(conditionVariable)
By calling signalC, a worker unblocks a waiting worker, if there is one. Has no effect if queue is empty.
—
Which workers can get exclusive access after a signal:
(1)-Signaling workers continue to keep the exclusive access, and only when it is somehow released, the blocked worker, or any other worker waiting to enter can get it.
(2)-The signaling worker is blocked and loose possession of the exclusive access that is given to the blocked/now-awaken workers
Those two strategies are often called
signal and wait waiting worker gets exclusive access
signal and continue the signaling worker retains exclusive access
Monitors and condition variables
signal and wait waiting worker gets exclusive access
In this strategy, the worker which is awaken can assume that the state of the monitor is changed, and in certain cases may also be able to assume that if it was awaken, it must have been the right time/condition for it to act.
signal and continue the signaling process retains exclusive access
In this case, time will pass, and some worker can further modify the status of the monitor, so the awaken worker needs to check again for the state of the monitor, to see if it is now the right time/condition to act.
Java offers the second strategy, that is more robust, since it does not allow the first process to make that kind of assumptions, that are often very fragile with respect to software evolution.
●
●
●
●
Java version of condition variables: wait() and notifyAll()
Sometimes you want to do something only when some condition hold, and you want to stop and wait otherwise.
The idea is, enter in the room, check the condition, and if does not hold, go underground and wait.
Object.wait() allows to release the lock without exiting from the room.
Object.notifyAll() is like ringing a bell, so that the underground workers can get out!
Example code
final Object dragonRoom=new Object(); Thread t1=new Thread(()->{
synchronized(dragonRoom){ while(treasureNotHere()){ try{dragonRoom.wait();}
catch (InterruptedException e) {/**/} }
takeTreasure(); }});
Thread t2=new Thread(()->{ synchronized(dragonRoom){
putTreasureDown();
dragonRoom.notifyAll();
}});
Example code
final Object dragonRoom=new Object(); Thread t1=new Thread(()->{
synchronized(dragonRoom){ while(treasureNotHere()){
try{dragonRoom.wait(3000);}
catch (InterruptedException e) {/**/} }
takeTreasure(); }});
Thread t2=new Thread(()->{ synchronized(dragonRoom){
putTreasureDown();
//dragonRoom.notifyAll();
}});
public class LockRelease {
static volatile int foo=1;
public static void main(String[]a){
final Object o1=new Object(); final Object o2=new Object(); Thread t1=new Thread(()->{
synchronized(o1){ synchronized(o2){
foo=3;
try{o2.wait();}
catch (..) {/**/} System.out.println(foo);
}}});
Thread t2=new Thread(()->{
synchronized(o2){ while(foo!=3){
try{o2.wait(100);} catch (..) {/**/} }
} synchronized(o1){
synchronized(o2){ foo=5;
o2.notifyAll();
}}});
t1.start();
t2.start();}}
●
Explain wait()
The only released lock is the one of the object we were waiting for, so the following code never terminates
Here t1 acquire two locks, o1 and o2.
Then it releases lock o2 by wait(). But is keeping o1.
t2 is waiting until foo is 3, then it acquires locks o1 and o2 and notify.
●
●
● This code just get blocked forever.
public class LockRelease {
static volatile int foo=1;
public static void main(String[]a){
final Object o1=new Object(); final Object o2=new Object(); Thread t1=new Thread(()->{
synchronized(o2){ synchronized(o2){
foo=3;
try{o2.wait();}
catch (..) {/**/} System.out.println(foo);
}}});
Thread t2=new Thread(()->{
synchronized(o2){ while(foo!=3){
try{o2.wait(100);} catch (..) {/**/} }
} synchronized(o2){
synchronized(o2){ foo=5;
o2.notifyAll();
}}});
t1.start();
t2.start();}}
●
Explain wait()
However, this code, with o1 replaced with o2 works.
Locks are reentrant, so is possible to enter in both blocks.
Wait release the lock, no matter how many synchronized block we are in.
That is the shortest code that explains how wait works for real… good luck…
●
●
●
●
Well, it is not very “safe” since you have the responsibility to understand what data is dynamically protected by what lock and to properly acquire such lock before even reading such data. That is, you need to be sure to pass through the door, but nothing in the language is stopping you from entering from the roof. Moreover, even if you are in the room, you can use wait() to hide under the floor and let someone else in!
Moreover, now that we have this lock concept, lots of related problems are possible: Deadlock, Livelock and starvation.
Is it at least simple? well yes, with respect to any other alternative. We will see later how solving the problem of the critical section have put concurrency researchers on their knees for a long, long time.
●
●
Simple and safe solution?
Synchronized is a language feature
Is it a needed feature? or can we implement a concept of Critical section on our own? without relaying on language features? That is the topic of the next lecture.
●
●
●
Simulate the universe
http://www.nature.com/news/model-universe- recreates-evolution-of-the-cosmos-1.15178
A team of MIT scientists using some serious computation power can simulate a nice chunk of universe.
On a much more modest goal, will we manage to simulate some hundred thousand asteroids?
●
●
●
Java Project with a minimal graphical interface, showing particle moving
You are supposed to read and understand the whole code. For real. Dedicate at least 3-4 hours to this task, especially if you are not used to reading lots of code.
Java code