CS 563 Concurrent Programming
Lecture 14: Semaphores
Semaphores
Copyright By PowCoder代写 加微信 powcoder
History: Dijkstra — 1968
Basic idea: comes from train semaphores to signal whether the track is free
Definition
sem s := 0 # or some non-negative value
< await (s>0) s = s-1; >
< s = s+1; >
What P and V stand for?
Probeer (try) and Verhoog (increment)
Basic Uses of Semaphores
Critical sections: mutual exclusion
sem mutex = 1;
process CS[i = 1 to n] { while (true) {
critical section; V(mutex); noncritical section;
Barriers: Signaling
sem arrive[1:n] = ([n] 0); # initially
# zeros to indicate that
# conditions have not yet
# occurred
Pr[i]: V(arrive[i]); # signal I am here
P(arrive[j]); # wait for partner
Pr[j]: V(arrive[j]); # signal I am here
P(arrive[i]); # wait for partner
Combine instances of these to form a dissemination or butterfly structure
Producer/Consumer: Split Binary Semaphores
Recall the problem
sem empty = 1, full = 0;
Producer: P(empty); deposit; V(full);
Consumer: P(full); fetch; V(empty);
Split binary semaphores: empty and full can be seen as a single binary semaphore that has been split into two binary sems
Key property: If they are used as above, mutual exclusion is satisfied between a P and next V
Generalization
sem empty = 1, full = 0;
Producer: P(empty); deposit; V(full);
Consumer: P(full); fetch; V(empty);
Generalize producer/consumer solution
What changes: representation of buffer and initial value of empty. That’s all!
Producer/Consumer
Producer/Consumer
Dining Philosopher
Solution Idea
Pick up two forks
sem forks[1:5] = ([5] 1); # each fork
# is a critical section
# so use 1 for initial value
First attempt for philosopher code
P(fork[i]); P(fork[i%5 + 1])
V(fork[i]); V(fork[i%5 + 1]);
What is the Problem?
Deadlock due to circular waiting Solutions:
(a) change order for some, but not all (b) limit number at table
sem limit = 4;
P(limit); above code; V(limit);
Readers/Writers Problem
sem rw = 1;
P(rw); P(rw);
read write;
V(rw); V(rw);
Over-constrained!
Allow Concurrent Readers
Idea: first reader to arrive does P(rw) and last to leave does V(rw)
This requires keeping a counter
P(mutexR);
if (nr == 1) P(rw);
V(mutexR);
P(mutexR);
if (nr == 0) V(rw);
V(mutexR);
Now nr is a shared variable that has to be accessed atomically
Predicates
Develop a predicate that exactly characterize the good and bad states
nr = number of readers; nw = number of writers
BAD state (to be avoided):
(nr > 0 and nw > 0) or (nw >1) GOOD states == not BAD states == RW
(nr = 0 or nw = 0) and (nw <= 1)
Coarse-Grained Solution
We want RW to be a global invariant so,
< await (nw == 0) nr++; >
< await (nr == 0 and nw == 0) nw++; >
Fine-Grained Solution
How can we turn the above into a solution that just uses semaphores?
Need CS protection and to implement the delay in the await statements
We actually know how to do this using split binary semaphores
Outline of Basic Idea of “Passing the Baton”
< await (nw == 0) nr++; >
< await (nr == 0 and nw == 0) nw++; >
(nr = 0 or nw = 0) and (nw <= 1)
if (nw == 0 and dr > 0) {
dr = dr-1; V(r); # awaken a reader, or }
elseif (nr == 0 and nw == 0 and dw > 0) { dw = dw-1; V(w); # awaken a writer, or
V(e); # release the entry lock
if (nw == 0 and dr > 0) {
dr = dr-1; V(r); # awaken a reader, or }
elseif (nr == 0 and nw == 0 and dw > 0) { dw = dw-1; V(w); # awaken a writer, or
V(e); # release the entry lock
Shortest Job Next
request(time, id)
take resource
delay by time
release(id)
if (some process delayed)
awaken first one (min value of time) and give it the resource
make resource free
General Solution Pattern:
request(parameters):
if (request cannot be satisfied) DELAY; take units;
release(parameters): P(e);
return units
Shortest Job Next
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com