, Lecture Con.04
Semester 1, 2022
ýThe University of Melbourne
SWEN90004 (2022) Semaphores; Java summary 1 / 24
Copyright By PowCoder代写 加微信 powcoder
Modelling Complex Software Systems
Semaphores; Java summary
Monitor recap Semaphores State diagrams
SWEN90004 (2022) Semaphores; Java summary 2 / 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 (2022) Semaphores; Java summary 3 / 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 (2022) Semaphores; Java summary 4 / 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.
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 5 / 24
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 7 / 24
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 8 / 24
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 10 / 24
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, 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 (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 12 / 24
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 13 / 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 (2022) Semaphores; Java summary 14 / 24
State diagram for the semaphore solution
SWEN90004 (2022) Semaphores; Java summary 15 / 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 (2022) Semaphores; Java summary 16 / 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 (2022) Semaphores; Java summary 17 / 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 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 18 / 24
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 19 / 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 (2022) 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 (2022) 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 (2022) Semaphores; Java summary
State diagram for Peterson
Note: this is actually half of the state diagram. The arrow on the left from (p6, q2, 1, 0, 0) actually leads to (p2, q2, 0, 0, 2) (ie, turn = 2 rather than turn = 1); however, the same reasoning applies.
SWEN90004 (2022) Semaphores; Java summary 23 / 24
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 24 / 24
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com