NWEN303 Concurrent Programming
12:
Common parallel patterns: Locks, readers/writes
Marco Servetto VUW
Synchronized and locks
Synchronized block are *a* solution to the critical section problem.
It is provided by the language. There is also the Lock class.
The biggest advantage of Lock objects over synchronized blocks is their ability to back out of an attempt to acquire a lock. The tryLock method backs out if the lock is not available immediately or before a timeout expires (if specified). The lockInterruptibly method backs out if another thread sends an interrupt before the lock is acquired.
import java.util.concurrent.locks.Lock
Lock l = …;
l.lock();
try {/**/} finally {l.unlock();}
Lock l = …; try{
●
Base case, just remember to use finally!
l.lockInterruptibly();
try {/**/} finally {l.unlock();} }
Version that can be interrupted. Can be useful.
Most useful version.
you can acquire locks if they are free, otherwise you can do other stuff.
●
catch(InterruptedException e){/**/} ●
Lock l = …; if(l.tryLock()){
try {/**/} finally {l.unlock();}
} else{/**/}
REMBER TO USE
REMBER TO USE FINALLY
Acquiring two locks?
I could not find a library call for it. My best handcrafted solution is the following:
public static void lockBoth(ReentrantLock l1, ReentrantLock l2) { l1.lock();//take first lock
if(l2.tryLock()) {return;}//take other if free l1.unlock();//otherwise, free all acquired locks
//we now know l2 is busy, let’s wait on l2
try{lockBoth(l2,l1);}
catch(StackOverflowError e) {throw new Error(“possible?”);} }
public static void unlockBoth(ReentrantLock l1,ReentrantLock l2){ if(!l1.isHeldByCurrentThread()) {l1.unlock();}
//this will fail: IllegarMonitorState exception l2.unlock();//this may fail, in that case we did not touch l1. l1.unlock();
} }
●
●
Does it prevents individual starvation? does it matters?
●
●
Locks are a Java class, they could have been designed differently.
Can you imagine a better/safer design for locks, still allowing the kind of expressiveness?
Lock design
●
Rarely it happens: we have massive objects that we can not afford to duplicate ever but we need to read very often and sometimes update them.
The idea is that we read order of magnitude more often then writing/updating.
Clearly readers can read in parallel, and writers need to be executed in isolation form both other readers and writers.
Reading state: everyone can read, no one write Writing state: Only one can write, no one read
●
●
● ●
Readers/Writers
●
For example, we have a FinancialModel,used to automatically buy and sell in an online treading system.
If it goes wrong, we can lose millions!
Some cool mathematician wrote a mathematical model that we can use to estimate what is going up and down. It is an adaptive model, so every few minutes, we get a better model!
We have to put stuff in order, so that the concrete pieces of code that check what to buy and sell can not mess stuff up!
● ●
●
Readers/Writers Example
●
More in concrete: Bob, your mathematician friend have designed those models, but they are around 150Gb each. By selling your car you manage to buy a nice server with 256 GB memory and 256 cores. The model predict when some company shares would go up or down, but it needs to be run on the recent trading data of any company of interest.
Multiple tasks will explore the network, get this trading data, feed it to the model and decide for a buy, sell or hold action. In a single minute of activity we may buy/sell several thousand times, not something a human can do.
Different tasks would use different sources to gather more trade data about more and more companies, such tasks are so many, and are subject to continuous change. We want to ensure that such tasks can not corrupt the model!
●
●
Readers/Writers Example
Readers/Writers Example
class Model{/*…*/}
//an enormous set of complex rules,
//GigaBytes of objects
class ReadOnlyModel{
private Model m;
/*access methods*/
}
interface Reader
//Readers: many barely tested web readers
T read(ReadOnlyModel m) throws Exception; }
interface Updater
//Updater:good code proved correct by the mathematician
T update(Model m) throws Exception; }
Readers/Writers Example
public class FinancialModel {
private Model m=/*…*/;
private ReadOnlyModel rm=new ReadOnlyModel(m);
private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
public
finally { rwl.readLock().unlock(); }
}
public
finally { rwl.writeLock().unlock();}}
}
Readers/Writers Example Lock
Model
ReadOnlyModel
Reader Reader
Reader Reader
Updater
●
***Match(…)
This allows to check an arbitrary condition on elements of a collection.
Very useful inside assertions!
List
–
Streams: useful operations
●
flatMap(..)
This allows to unfold nested collections
Streams: useful operations
List
long howMany=ss.stream().flatMap(e->e.stream()).count();
Streams: useful operations
flatMap(..)
can also encode a ‘map’+filter by returning an empty stream with ‘Stream.of()’.
convenient when declaring sub-functions
List
.collect(Collectors.toUnmodifiableList()); …
Stream
}
●
–
●
reduce(.. .. ..)
there are various kinds of reduce. The version with 3 arguments is the most flexible and the best for parallel computations. We provide:
a starting point,
a way to accumulate the result onto a partial result given another element
a way to accumulate two partial results
List
0,//starting point (i,s)->i+s.length(),//int + string -> int (i1,i2)->i1+i2);//int + int -> int
– –
–
Streams: useful operations
0 0
0 0 0
+ +
”a”.lenght() + ”b”.lenght() +
”aa”.lenght() ”bb”.lenght()
+ +
… 3 … 3
.. .. ..
Streams: useful operations
reduce may create a grid like the one below: List
int sumLenght=ss.parallelStream().reduce(
●
0,//starting point (i,s)->i+s.length(),//int + string -> int (i1,i2)->i1+i2);//int + int -> int
…
… ….
+ = total
Streams: useful operations
jumping back and forth from parallel and sequential:
List
.map(s->”[“+s+s+”]”)//this map is ok in parallel .sequential()//the filter below needs to be sequential .filter(s-> s.length()>1 ? true : !discarded.add(s)) .collect(Collectors.toUnmodifiableList());
●
Streams: labs solutions
static
}
//If all the strings in ss are shorter then 5, then return the empty list. //Otherwise, return the list of all strings longer then 10.
static List
if(ss.stream().allMatch(s->s.length()<5)) {return List.of();} return toList(ss.stream().filter(s->s.length()>10));
}
//Assert that the two lists have the same length.
//Create a list of all names and surnames.
static List
assert names.size()==surnames.size(); return toList(IntStream
.range(0, names.size())
.boxed()
.map(i->names.get(i)+” “+surnames.get(i)));
}
//Return a list of all the suspects that are also criminals.
static List
}
Streams: labs solutions
//Without building an intermediate list,
//return a string with all the names of the the suspects that are also criminals //divided by a new line.
static String ex4(List
return suspects.stream()
.filter(criminals::contains).collect(Collectors.joining(“\n”)); }
//Sum all the x and y coordinates of all the points into a single Point result //What should happen if ps is empty?
static Point ex6(List
return ps.stream().reduce(new Point(0,0),
(p1,p2)->new Point(p1.x+p2.x,p1.y+p2.y)); }
Streams: labs solutions
static class Point{int x;int y;Point(int x,int y){this.x=x;this.y=y;}} //Note: equals is not defined on Point!!
//Assert that the two lists have the same length.
//return a list with all the points made wit the xs and the ys.
//Do not include repeated points; that is, points with the same coordinates. //Do not include points with negative coordinates.
static List
assert xs.size() == ys.size(); return toList(IntStream
.range(0, xs.size())
.boxed()
.map(i -> new Point(xs.get(i), ys.get(i))) .filter(p -> p.x >= 0 && p.y >= 0) .map(Wrapper::new)
.distinct()
.map(Wrapper::p));
}
private static record Wrapper(Point p){ @Override public boolean equals(Object o) {
var q = ((Wrapper)o).p();
return q.x == p.x && q.y == p.y; }
@Override public int hashCode() { return Objects.hash(p.x, p.y);
} }