NWEN303 Concurrent Programming
9
Race condition,
Deadlock, Livelock
Marco Servetto VUW
● ● ● ●
●
● ●
Unexpected Race condition Deadlock
Livelock
Starvation (next time)
Informally, those are kinds of bugs or unexpected behaviors unique of parallel programs.
However, there are also more precise definitions.
For each of those, we will now show the informal and formal meaning.
What are those?
●
A Race Condition is any kind of non- determinism induced by the presence of parallel/concurrent execution.
Thus, not all Race Conditions are bugs.
However, we want to predict the behavior of our programs, so an unexpected behavior caused by a race condition is a bug.
● ●
Race condition
●
“Two or more tasks act at the same time on the representation of an element in your application, pushing it into incoherent/wrong/unexpected state.”
The element representation does not need to be a single area of memory, for example can be a point where x and y can be independently set.
It mention unexpected behavior, so it is something that is in the mind of the programmer more than in the code itself?
Usually, this kind of issue happen when there is too little synchronization despite active task communication.
●
●
●
Unexpected Race condition: Informal typical example
Data Race: Formal definition
● Conflicting Accesses: A read of or write to a variable is an access to that variable. Two accesses to the same shared field or array element are said to be conflicting if at least one of the accesses is a write.
● Data Race: Two accesses form a data race in an execution of a program if they are from different threads, they conflict, and they are not ordered.
● Languages provide ordering mechanisms; Java provides the synchronized and volatile keywords.
● C/C++ memory models rely on the absence of data races in order to be applicable, that is every execution that have race conditions is undefined (that is, even unrelated parts of the program can freely go nuts).
● Java memory model is “safer”, and provide a well defined, but human unfriendly behavior (that is, other parts of the program are still self coherent, but in general not even the best researchers in the area of concurrent programming are able to write correct software in the presence of data races).
●
Race condition: Formally/Informally
So, informally ‘unexpected race conditions’ can be caused by bugs in the logic and are about “data” in an abstract sense. It is a useful concept for understanding and debugging our applications
Formally, data races are a kind of race conditions. They refer to words of memory / individual variables / individual fields, and are useful to understand the semantic of the programming language in the presence of multiple communicating threads.
So: informal / formal
bugs in logic / formal language semantic abstract data / words of memory
●
●
– –
Deadlock/Livelock
Deadlock/Livelock
Deadlock/Livelock
Deadlock/Livelock
I need the helmet and the key to use
the motorbike!
I need the key and the helmet to use
the motorbike!
Deadlock/Livelock
Deadlock/Livelock
Deadlock/Livelock
I need the key now! I’m going to wait
until I get it!
Deadlock/Livelock
I need the key now! I’m going to wait
until I get it!
I need the Helmet now! I’m going to wait
until I get it!
●
Informally: when multiple locks are acquired by multiple tasks and egoistically kept waiting for the other to release it. For example, there are two flatmates, Bob and Alice, sharing a single motorbike and a single helmet. One needs to go to warehouse and the other needs to go to the supermarket.
Bob wears the helmet.
At the same time, Alice takes the key of the motorbike.
Then, Bob starts searching for the key, and since he can not find it, he continue searching.
Alice starts searching for the helmet, and since she can not find it, she continue searching.
To weeks later, they are still there, searching for the missing resource, and no one have done any useful task.
●
●
●
●
●
Deadlock/Livelock
●
●
Philosophers thinks and eats.
Since they are no very rich, they only eat rice and have only one chopstick each.
However, by sitting on one chair every philosopher can acquire the control of the chopstick on its left and then on the chopstick on its right.
●
Deadlock/Livelock: Dinning philosophers
●
Philosophers thinks and eats.
Thread t1=new Thread(()->{ while(true){
think(); synchronized(stickLeft){
synchronized(stickRight){
eat(); }}});
One sad day, every philosopher decided to eat at the same time.
And then nothing happened any more.
●
●
Deadlock/Livelock: Dinning philosophers
●
This implementation produces a deadlock: the cpu is left without nothing to do. the pc can cool down and stop doing anything at all.
If the locking was implemented with some kind of busy wait, or with some other kind of complex action could have been performed by the workers while waiting for the resources (like Adam searching for the key in the former example) then we would had a livelock
●
Deadlock/Livelock
Thread t1=new Thread(()->{ while(true){
think(); synchronized(stickLeft){
synchronized(stickRight){
eat(); }}});
●
There is a ring of threads owning at least a resource each, and waiting to acquire a resource owned by another thread on the ring.
Since all the threads are waiting, no thread is able to act, no action means that no resources are even going to be released.
●
Deadlock formally
●
There is a ring of threads owning at least a resource each, and actively trying to gather a resource owned by another thread on the ring.
Some thread is acting in order to search for such resource, so it could in principle decide to release its owned resource in any moment. However, in the specific execution that produces the livelock, it choose to never do so (likely, the programmer have not realized the potential issue).
●
Livelock formally
public class BankAccount {
private String name;
private volatile int cash;//use BigInteger in a real version public BankAccount(String name,int cash){
if(cash<0){throw new IllegalArgumentException("Negative cash "+cash);} this.name=name;
this.cash=cash;
}
public int getCash(){ return this.cash; }
public synchronized void deposit(int cash){
if(cash<0){throw new IllegalArgumentException("Negative cash "+cash);} this.cash+=cash;
}
public synchronized void withdrawal(int cash){
if(cash<0){throw new IllegalArgumentException("Negative cash "+cash);} if(this.cash-cash<0){throw new NotEnoughCash();}
this.cash-=cash;
}
public static class NotEnoughCash extends RuntimeException{} public synchronized void transfer(int cash, BankAccount target){
this.withdrawal(cash); target.deposit(cash); }
public String toString(){return "["+this.name+":"+this.cash+"]";} }
Example
public class MainBank {
public static final int aMillion=1000000;
Example
public static class BankWorker extends Thread{ BankAccount src; BankAccount dest; BankWorker(BankAccount src, BankAccount dest){
this.src=src;this.dest=dest;
}
public void run(){
for(int i=0;i
}
A variation of transfer where the money is transferred only if the target is not too rich.
Here we need to acquire two locks/keys at the same time, or, if you prefer, we want to be in exclusive control of two different “rooms” for critical sections.
Removing the synchronized block causes race conditions, keeping it causes deadlocks!
●
●
●
●
The Banker’s algorithm is a resource allocation and deadlock avoidance algorithm developed by Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources before deciding whether allocation should be allowed to continue
Banker algorithm?
●
Never spread your resources into too many workers at the same time, otherwise It may happen that the “Bank” does not have enough resources to allows anyone to finish.
Predetermined maximum possible amounts of resources: all workers are supposed to know beforehand how much resources they are going to require.
●
Deadlock avoidance
●
●
This algorithm, originally designed for operative systems, supports multiple kinds of resources.
Often, the following things are considered resources: Memory, exclusive access to a file, tcp/udp ports,exclusive access to a usb key during formatting, mouse focus, …
A lock is a resource too, and exclusive access to other kinds of resources is often implemented using locks.
●
What is a resource?
●
●
Wikipedia have a good description of the banker algorithm, so have a nice reading.
http://en.wikipedia.org/wiki/Banker%27s_algorithm
Banker algorithm