For a concurrent program to be correct it needs decent synchronisation (wow, he uses both spellings…he used a ‘z’ in the title which I copy and pasted, and an ‘s’ everywhere else) and communication.
Shared variables communication
We all know the problems with two tasks updating the same variable. This is why shared-nothing (Erlang) works; because it doesn’t allow this. However if you want to be stupid and shoehorn concurrency into normal paradigms you need mutual exclusion to protect critical sections.
Not only that, but a task may also need to wait before it can do something. For example if you have a bounded buffer and two different tasks – a producer and a consumer – the consumer can’t consume anything from an empty buffer; it must wait for the producer to produce something. As an aside, if you only have 1 producer and 1 consumer and you code carefully you don’t need mutual exclusion.
Old methods of fixing
- Busy waiting; keep testing until the condition is satisfied. Consumes resources etc.
- Semaphores; higher level than busy waiting but still low level and error prone; you might make a programming mistake and get the wrong semaphores etc.
Not so old
- Monitors; mutexes and condition variables. Provides encapsulation around data so that the operations performed on that shared data automatically have mutual exclusion.
- Condition Variables; addition to monitors which allow tasks to free up the lock on the monitors while still within the monitor. For example an ‘append’ task to the bounded buffer (which is in a monitor) can use
if size == max: wait(spaceavailable); endif
which will halt it within the monitor and then continue oncespaceavailable
is true. – You can have problems where two things are waiting on the same condition variable or one jumps in ahead of something waiting and somehow (this is why concurrency like this sucks) both end up running and there’s a problem. You can either have a preference-type system where tasks waiting in the monitor have preference, or (POSIX does this) you have a while loop around thewait
to double check when you come out. Seems a bit weird to me.
Problem(s) with monitors
Readers-Writers Problem
This has a Wikipedia Page. You can fix this problem using monitors by having entry and exit protocols; but not just using a standard monitor because they don’t give you read-locks and write-locks.
Java’s Synchronized Methods
- Simple monitors within an OO framework.
- Every object you create has a lock (the JVM creates it for you). It is accessed by either using the method modifier
synchronized
or by using ‘block synchronization’ (see below). - A
synchronized
method can only be executed once the lock has been obtained for that object. - Synchronized methods have mutually exclusive access to the data in the object if that data is only accessed by other synchronized methods. Unsynchronized methods do not require the lock and can be called at any time.
Java’s Block Synchronization
This provides a mechanism where a ‘block’ of a task can be labeled and syncrhonized. You do something like:
<% highlight java %> public int read() { synchronized(this) { return theData; } } <% endhighlight %>
The argument to synchronized
is the object whose lock needs to be obtained before the task can continue.
These are useful. In the example of a ‘SharedInteger’ on the slides, what if you want to do some calculations in between reading and writing from it? Even though SharedInteger has synchronized methods, we want to have the lock the whole time otherwise someone might come along and change it in the middle of our calculation. So you can encapsulate it in a synchronized
block to get the lock, then you can do what you like.
Apparently if you do this you’re undermining the encapsulation stuff. Or something.
Then…
I lost track a bit from here. Slide 19+. More stuff about the readers-writers problem and static data.