critical_section cs cs.enter(0) // whatever cs.exit(0) |
semaphore s(1) s.get() // Whatever s.put() |
int x = ... critical_section cs co cs.enter(0) x = ... x ... cs.exit(0) || cs.enter(1) x = ... x ... cs.exit(1) oc |
int x = ... semaphore mutex(1) co mutex.lock() x = ... x ... mutex.unlock() || mutex.lock() x = ... x ... mutex.unlock() oc |
lock() (get()) and unlock()
(put()).
(#mutex.put() - #mutex.get()) + #in_cr = 1
data buffer bool empty = true | |
producer
while true
while !empty skip
buffer = p()
empty = false
|
consumer
while true
while empty skip
c(buffer)
empty = true
|
empty and full.
data buffer semaphore empty(1) semaphore full(0) ## empty.available() + full.available() = 1 | |
producer [i = 1 to m]
while true
empty.wait()
buffer = p()
full.signal()
|
consumer [i = 1 to n]
while true
full.wait()
c(buffer)
empty.signal()
|
wait() (get()) and
signal() (put()).
empty.available() + #in_cr + full.available() = 1
empty and full.
0 <= (Sum i : 0 <= i < n : s[i].available()) <= 1
const int k = ... data buffer[0 : k - 1] int front = 0, back = 0 semaphore empty(k) semaphore full(0) ## empty.available() + full.available() = k | |
producer
while true
empty.get()
buffer[back] = p()
back = (back + 1) % k
full.put()
|
consumer
while true
full.get()
c(buffer[front])
front = (front + 1) % k
empty.put()
|
front; multiple producers
interfere over back.
const int k = ... data buffer[0 : k - 1] int front = 0, back = 0 semaphore empty(k), full(0) semaphore back_mtx(1), front_mtx(1) ## empty.available() + full.available() = k | |
producer [i = 1 to m] while true empty.wait() back_mtx.lock() buffer[back] = p() back = (back + 1) % k back_mtx.unlock() full.signal() |
consumer [i = 1 to n] while true full.wait() front_mtx.lock() c(buffer[front]) front = (front + 1) % k front_mtx.unlock() empty.signal() |
semaphore forks[0:4] = ([5] 1)
process philosopher [ i = 0 to 4 ]
while true
think
forks[(i + ((i + 1) % 2)) % 5].lock()
forks[i + (i % 2)].lock()
eat
forks[(i + ((i + 1) % 2)) % 5].unlock()
forks[i + (i % 2)].unlock()
database db
semaphore mutex(1)
## mutex.available() + # in cr = 1
process reader [ i = 1 to m ]
mutex.lock()
read the data base
mutex.unlock()
process writer [ i = 1 to n ]
mutex.lock()
write the data base
mutex.unlock()
database db
semaphore mutex(1)
int readers = 0
process reader [ i = 1 to m ]
< if ++nr == 1 then mutex.lock() >
read the data base
< if --nr == 0 then mutex.unlock() >
process writer [ i = 1 to n ]
mutex.lock()
write the data base
mutex.unlock()
process reader [ i - 1 to m ]
r_mutex.lock()
if ++nr == 1 then mutex.lock()
r_mutex.unlock()
read the data base
r_mutex.lock()
if --nr == 0 then mutex.unlock()
r_mutex.unlock()
semaphore mtx(0) semaphore r_go(0), w_go(0) int dw = 0, dr = 0, nr = 0, nw = 0 | |
// writer entry protocol mtx.lock() if nw + nr > 0 dw++ mtx.unlock() w_go.wait() mtx.lock() dw-- else nw++ mtx.unlock |
// reader entry protocol
mtx.lock()
if nw + dw > 0
dr++
mtx.unlock()
r_go.wait()
mtx.lock()
if --dr > 0
r_go.signal()
nr++
mtx.unlock
|
// writer exit protocol mtx.lock() nw-- if dr > 0 r_go.signal() else if dw > 0 nw++ w_go.signal() mtx.unlock() |
// reader exit protocol mtx.lock() if --nr == 0 and dw > 0 nw++ w_go.signal() mtx.unlock() |
nr readers in the database.
mtx.unlock() r_go.wait() mtx.lock()
prevents the code from providing writer-exclusive access.
mtx.lock() // reader entry
if nw + dw > 0
dr++
mtx.unlock()
r_go.wait() { there are nr cs readers }
mtx.lock()
if --dr > 0 { there are nr cs readers }
nr++
r_go.signal() { there are nr cs readers }
else
nr++
mtx.unlock
mtx.lock() // writer exit
nw--
if dr > 0 { there are nr cs readers }
nr++
r_go.signal() { there are nr cs readers }
else if dw > 0 { there are nw cs readers }
nw++
w_go.signal() { there are nw cs readers }
mtx.unlock()
// entry protocol
mtx.lock()
if delay
mtx.unlock()
delay.wait()
mtx.lock()
// whatever
mtx.unlock
|
// exit protocol
mtx.lock()
// whatever
if delayed
delay.signal()
mtx.unlock()
|
// entry protocol
mtx.lock()
if delay
mtx.unlock()
delay.wait()
|
// exit protocol
mtx.lock()
// whatever
if delayed
delay.signal()
else
mtx.unlock()
|
// writer entry protocol mtx.lock() if nw + nr > 0 dw++ mtx.unlock() w_go.wait() |
// reader entry protocol mtx.lock() if nw + dw > 0 dr++ mtx.unlock() r_go.wait() |
// writer exit protocol mtx.lock() nw-- if dr > 0 |
// reader exit protocol mtx.lock() if --nr == 0 and dw > 0 |
// reader entry mtx.lock() if nw + dw > 0 dr++ mtx.unlock() r_go.wait() --dr if dr > 0 r_go.signal() nr++ mtx.unlock()
nr++.
allocation request(parameters) < await request satisfied ; allocate > void release(parameters, allocation) < return allocation >
semaphore mutex(1) semaphore change(0) int waiters = 0 | |
request()
mutex.lock()
while !satisfied
waiters++
mutex.unlock()
change.signal()
mutex.lock()
waiters--
// allocate
if waiters > 0
change.signal()
mutex.unlock()
|
release()
mutex.lock()
// deallocate
if waiters > 0
change.signal()
mutex.unlock()
|
semaphore mutex(1) semaphore change(0) int waiters = 0 | |
request()
mutex.lock()
while !satisfied
waiters++
mutex.unlock()
change.wait()
waiters--
// allocate
if satisfied
change.signal()
else
mutex.unlock()
|
release()
mutex.lock()
// deallocate
if satisfied
change.signal()
else
mutex.unlock()
|
struct qe { params ; semaphore wait(0) }
queue<qe> wq
semaphore mutex(1)
| |
request(params, time)
mutex.lock()
if not satisfied(params)
wq.push(time, qe(papams))
qe & me wq.top()
mutex.unlock()
me.wait.wait()
wq.pop()
// allocate
if satisfied()
wq.top().waiter.signal()
else
mutex.unlock()
|
release()
mutex.lock()
// deallocate
if satisfied()
change.signal()
else
mutex.unlock()
|
static satisfied()
return
not wq.empty() and
satisfied(wq.front().params)
|
|
This page last modified on 27 June 2003.