SWEN90004
Modelling Complex Software Systems
Semaphores; Java summary
Artem Polyvyanyy, Nic Geard Lecture Con.04
Semester 1, 2021
⃝c The University of Melbourne
SWEN90004
(2021)
Semaphores; Java summary
1 / 24
Java has lightweight monitors
A lock is associated with every object. To execute a synchronized method, a process must first acquire the lock for that object. It releases the lock upon return.
Java monitors do not guarantee fairness.
A process P that holds the lock on object o can choose to give it up,
by invoking wait(). It is then waiting on o.
Another process Q may execute o.notify(), thereby changing some
waiting process’s state to locking (P, say).
SWEN90004 (2021) Semaphores; Java summary 2 / 24
Java has lightweight monitors
The process Q that executes o.notify() obviously has o’s lock (and is running).
Some programming languages (and the original monitor proposals) stipulate that, at that point, the notified process P is given priority over other locking processes, and even the notifying process Q. (This makes sense, because Q has presumably changed some condition that made notification of P pertinent.)
Java does not do this. Instead we get the typical pattern of wrapping a while loop around a wait().
The notifier will hold on to the lock (until the end of the synchronised method or code block).
SWEN90004 (2021) Semaphores; Java summary 3 / 24
Java has lightweight monitors
Some of the original monitor concepts allowed for many separate wait sets—each waiting for some specific condition to hold. Java does not have that.
Some third process may update x and y. If it changes x, it would want to notify whoever waits for x. If it changes y, it would want to notify whoever waits for y.
However, Java falls back on the notifyAll() solution: Release all processes waiting on the affected object (as opposed to the condition).
synchronized methodX() { if (x == 0)
wait();
synchronized methodY() { if (y == 0)
wait();
SWEN90004 (2021) Semaphores; Java summary 4 / 24
Implementing Java monitors
For a class to meet the requirements of a monitor: all attributes should be private
all methods should be synchronized
This ensures that all methods will be treated as atomic events.
SWEN90004 (2021) Semaphores; Java summary
5 / 24
Volatile variables
For efficiency, compilers or virtual machines may load the value of a variable into a cache. If the value of the variable is modified by one thread, other threads relying on cached values may not detect this, and continue to use the stale cached value.
Similarly, updates to variable values may be made initially in the cache and not immediately written back to memory.
To avoid this, variables can be declared as volatile, which directs the virtual machine to read and write that variable directly from or to memory.
SWEN90004 (2021) Semaphores; Java summary 6 / 24
Process states again
Runnable
Running
Created
Non-runnable
We previously discussed how running threads could pause their execution by yielding (to return to runnable) and sleeping (to temporarily become non-runnable).
Dead
SWEN90004 (2021) Semaphores; Java summary 7 / 24
Process states again
Runnable
Running
Created
Blocked
Various synchronization constructs, such as monitors, can result in a different type of non-runnable state, in which the process is blocked. A blocked process relies on other processes to unblock it, after which it is again runnable.
Dead
SWEN90004 (2021) Semaphores; Java summary 8 / 24
Semaphores
A semaphore is a simple but versatile concurrent device for managing access to a shared resource.
It consists of a value v ∈ N of currently available access permits, and a wait set W of processes currently waiting for access.
It must be initialized S := (k,{ }), where k is the maximum number of threads can simultaneously access some resource.
S comes with two atomic operations, wait and signal.
SWEN90004 (2021) Semaphores; Java summary 9 / 24
Semaphore operations
Assume process p executes the operation:
S.wait()
S.signal()
if S.W == { } S.v++
else
choose q from S.W S.W = S.W \ {q} q.state = runnable
if S.v > 0 S.v–
else
S.W = S.W U {p} p.state = blocked
Hence when p signals S whose wait set is empty, S’s value is incremented; otherwise an arbitrary process is unblocked, that is, removed from the wait set, having its state changed to runnable.
SWEN90004 (2021) Semaphores; Java summary
10 / 24
The binary semaphore
If S .v ∈ {0, 1}, S is called binary.
For a binary semaphore the operations are:
S.wait()
S.signal()
if S.W == { } S.v = 1
else
choose q from S.W S.W = S.W \ {q} q.state = runnable
if S.v == 1 S.v = 0
else
S.W = S.W U {p} p.state = blocked
If S .v = 1 then S.signal() is undefined. Sometimes a binary semaphore is called a mutex.
SWEN90004 (2021) Semaphores; Java summary 11 / 24
The Mutex problem again
Using a binary semaphore, it is easy to solve the Mutex problem for two processes:
binary semaphore S = (1,{});
loop
p1: non_critical_p(); p2: S.wait();
p3: critical_p();
p4: S.signal();
loop
q1: non_critical_q(); q2: S.wait();
q3: critical_q();
q4: S.signal();
SWEN90004 (2021) Semaphores; Java summary 12 / 24
State diagrams
State diagrams are often used to describe the behaviour of systems. They are directed graphs, where nodes represent states and edges
represent transitions, that is, state changes.
A state gives pertinent information about a process at a given point in
time—usually the values of its instruction pointer and local variables.
SWEN90004 (2021) Semaphores; Java summary 13 / 24
State diagram for the semaphore solution
Again, we just use the four interesting program points:
p4 q2 (0, { })
p2 q2 (1, { })
p2 q4 (0, {p})
p4 q2 (0, {q})
p2 q4 (0, { })
The diagram shows that the solution is correct, and that there is no deadlock or starvation.
SWEN90004 (2021) Semaphores; Java summary 14 / 24
Using semaphores to control execution order
integer array A
binary semaphore S1 = (0,{}) binary semaphore S2 = (0,{})
p1: sort low half p2: S1.signal() p3:
q1: sort high half q2: S2.signal() q3:
m1: S1.wait() m2: S2.wait() m3: merge halves
SWEN90004 (2021) Semaphores; Java summary 15 / 24
Strong semaphores
The binary semaphore solution to the Mutex problem generalises to N processes.
However, when N > 2, there is no longer a guarantee of freedom from starvation, because blocked processes are taken arbitrarily from a set.
The obvious (fair) way of implementing semaphores is to let processes wait in a queue.
This removes the starvation issue and we then talk about strong semaphores.
SWEN90004 (2021) Semaphores; Java summary 16 / 24
The bounded buffer problem
Assume we have a “producer” process p and a “consumer” process q.
Process p generates items for q to process. If the two are of similar average speed, but each of varying speed, then the use of a buffer can smoothen overall processing and speed it up, allowing for asynchronous communication between the two.
General semaphores can be used to implement the cooperation.
The idea is to have two semaphores S1 and S2 and maintain a loop invariant S1.v + S2.v = n, where n is the buffer size.
Because of the roles they play, let us call the semaphores notEmpty and notFull.
SWEN90004 (2021) Semaphores; Java summary 17 / 24
Semaphores for the bounded buffer problem
buffer = empty queue; semaphore notEmpty = (0,{}); semaphore notFull = (n,{});
item d
loop
p1: d = produce();
p2: notFull.wait(); p3: buffer.put(d);
p4: notEmpty.signal();
item d
loop
q1: notEmpty.wait(); q2: d = buffer.take(); q3: notFull.signal(); q4: consume(d);
SWEN90004 (2021) Semaphores; Java summary 18 / 24
Semaphores in Java
The package java.util.concurrent has a Semaphore class.
The wait and signal operations are called acquire() and release().
The Semaphore constructor has, apart from the value argument, an optional Boolean argument which, when true, makes the semaphore strong; that is, it gives access to waiting threads on a “first in, first out” basis.
SWEN90004 (2021) Semaphores; Java summary 19 / 24
Java thread states in more detail
Locking
Waiting for o
got lock on o
o.notify(), o.notifyAll() interrupt()
timeout
attempting to lock o
o.wait()
start()
scheduled preempted
yield()
timeout
interrupt()
timeout
dies
Runnable
Running
Created
interrupt()
or u died
sleep()
u.join()
red = by self blue = by other
Dead
Sleeping
Joining u
SWEN90004
(2021)
Semaphores; Java summary
20 / 24
Example: Peterson’s mutex algorithm
static int p = 0; static int q = 0; static int turn = 1;
while (true) {
p1: non_critical_p();
p2: p = 1;
p3: turn = 2;
p4: while (q && turn == 2); p5: critical_p();
p6: p = 0;
}
while (true) {
q1: non_critical_q();
q2: q = 1;
q3: turn = 1;
q4: while (p && turn == 1); q5: critical_q();
q6: q = 0;
}
We can reason about Peterson’s algorithm (and the other mutex algorithms that we met) by considering the finite number of states the combination of processes P and Q can be in.
SWEN90004 (2021) Semaphores; Java summary 21 / 24
State diagrams
In this case a state is a quintuple (pi, qj, p, q, turn), where pi is P’s instruction pointer and qj is Q’s. There are possibly as many as 288 = 6 × 6 × 2 × 2 × 2 states, but in fact most are unreachable.
Also we can disregard the four statements that are not part of the protocol (p1, p5, q1 and q5).
we depict the state (pi, qj, p, q, turn) as
The next slide shows the 14 states of interest and all the possible
transitions.
SWEN90004 (2021) Semaphores; Java summary
22 / 24
pi qj
p q turn
State diagram for Peterson
p2 q2 001
p2 q3 011
p2 q4 011
p2 q6 011
p3 q2 101
p3 q3 111
p3 q4 111
p4 q4 112
p4 q6 112
p4 q2 102
p4 q3 112
p4 q4 111
p6 q4 111
p6 q2 102
Mutex achieved: all states of form (p6, q6, , , ) are unreachable. No state of form (p4, q4, , , ) is stuck, so there is no deadlock. Fromeachstateofform(p4, , , , ),astate(p6, , , , )canbe reached, and similarly for q4, so there is no starvation.
SWEN90004 (2021) Semaphores; Java summary
23 / 24
References
M. Ben-Ari, Principles of Concurrent and Distributed Programming, Prentice Hall, 2nd edition, 2006.
B. Goetz, Java: Concurrency in Practice, Addison-Wesley, 2006. D. Lea, Concurrent Programming in Java: Design Principles and
Patterns, Addison-Wesley, 2nd edition, 2000.
P. Sestoft, Java Precisely, MIT Press, 2nd edition, 2005.
SWEN90004 (2021) Semaphores; Java summary 24 / 24