[SOLVED] SWEN90004 (2022) Semaphores; Java summary 1 / 23

, Lecture Con.04
Semester 1, 2022
The University of Melbourne
SWEN90004 (2022) Semaphores; Java summary 1 / 23

Copyright By Assignmentchef assignmentchef

Modelling Complex Software Systems
Semaphores; Java summary

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 processs state to locking (P, say).
SWEN90004 (2022) Semaphores; Java summary 2 / 23

Java has lightweight monitors
The process Q that executes o.notify() obviously has os 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 (2022) Semaphores; Java summary 3 / 23

Java has lightweight monitors
Some of the original monitor concepts allowed for many separate wait setseach waiting for some specific condition to hold. Java does not have that.
synchronized methodX() { if (x == 0)
synchronized methodY() { if (y == 0)
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).
SWEN90004 (2022) Semaphores; Java summary 4 / 23

Implementing Java monitors
For a class to meet the requirements of a monitor:
all attributes that represent shared data should be private
all methods that access those attributes should be synchronized
This ensures that all of these methods will be treated as atomic events and hence there is no risk of interference if multiple Threads are working with the shared data held by that monitor.
SWEN90004 (2022) Semaphores; Java summary

Process states again
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).
SWEN90004 (2022) Semaphores; Java summary 6 / 23

Process states again
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.
SWEN90004 (2022) Semaphores; Java summary 7 / 23

Java thread states in more detail
Waiting for o
got lock on o
o.notify(), o.notifyAll() interrupt()
attempting to lock o
scheduled preempted
interrupt()
interrupt()
red = by self blue = by other
Semaphores; Java summary

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 (2022) Semaphores; Java summary 9 / 23

Semaphore operations
Assume process p executes the operation:
S.signal()
if S.W == { } S.v++
if S.v > 0 S.v
choose q from S.W S.W = S.W {q} q.state = runnable
S.W = S.W U {p} p.state = blocked
Hence when p signals S whose wait set is empty, Ss value is incremented; otherwise an arbitrary process is unblocked, that is, removed from the wait set, having its state changed to runnable.
SWEN90004 (2022) Semaphores; Java summary

The binary semaphore
If S.v {0, 1}, S is called binary.
For a binary semaphore the operations are:
S.signal()
if S.W == { } S.v = 1
if S.v == 1 S.v = 0
choose q from S.W S.W = S.W {q} q.state = runnable
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 (2022) Semaphores; Java summary 11 / 23

The Mutex problem again
Using a binary semaphore, it is easy to solve the Mutex problem for two processes:
binary semaphore S = (1,{});
p1: non_critical_p(); p2: S.wait();
p3: critical_p();
p4: S.signal();
q1: non_critical_q(); q2: S.wait();
q3: critical_q();
q4: S.signal();
SWEN90004 (2022) Semaphores; Java summary 12 / 23

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 timeusually the values of its instruction pointer and local variables.
SWEN90004 (2022) Semaphores; Java summary 13 / 23

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 (2022) Semaphores; Java summary 14 / 23

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 (2022) Semaphores; Java summary 15 / 23

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 (2022) Semaphores; Java summary 16 / 23

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 smooth 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 (2022) Semaphores; Java summary 17 / 23

Semaphores for the bounded buffer problem
buffer = empty queue; semaphore notEmpty = (0,{}); semaphore notFull = (n,{});
p1: d = produce();
p2: notFull.wait(); p3: buffer.put(d);
p4: notEmpty.signal();
q1: notEmpty.wait(); q2: d = buffer.take(); q3: notFull.signal(); q4: consume(d);
SWEN90004 (2022) Semaphores; Java summary 18 / 23

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 (2022) Semaphores; Java summary 19 / 23

Example: Petersons 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 Petersons 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 (2022) Semaphores; Java summary 20 / 23

State diagrams
In this case a state is a quintuple (pi, qj, p, q, turn), where pi is Ps instruction pointer and qj is Qs. 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 (2022) Semaphores; Java summary

State diagram for Peterson
Mutex achieved: all states of form (p6, q6, _, _, _) are unreachable. No state of form (p4, q4, _, _, _) is stuck, so there is no deadlock. From each state of form (p4, _, _, _, _), a state (p6, _, _, _, _) can be reached, and similarly for q4, so there is no starvation.
SWEN90004 (2022) Semaphores; Java summary 22 / 23

References
M. Ben-Ari, Principles of Concurrent and Distributed Programming,, 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 (2022) Semaphores; Java summary 23 / 23

CS: assignmentchef QQ: 1823890830 Email: [email protected]