Deriving Efficient Semaphore Solutions from
"<await (B) S; >" (atomic action) Statements
from
Andrews Chapter 4
SIGNAL: 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
}
else
v(e); # release the entry (mutex) lock
int n = 0, nw = 0; ##RW: (nr==0 or nw == 0) and
nw <=1
sem e = 1,
#controls entry to critical sections
r =
0, # use to delay
readers
w = 0; #used to
delay writers
int dr =
0, #number of delayed readers
dw = 0;
#number of delayed writers
process Reader [i = 1 to M] {
while(true) {
#<await nw
== 0 nr = nr +1; >
P(e);
if (nw > 0) {dr =dr+1; V(e); P(r); }
nr = nr+1;
SIGNAL: 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
}
else
v(e); # release the entry (mutex) lock
read the database;
# <nr = nr-1;>
P(e);
nr = nr - 1;
SIGNAL: 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
}
else
v(e); # release the entry (mutex) lock
}
}
process Writer [j = 1 to N] {
while(true) {
# <await nr==0 and nw==0)
nw = nw+1;>
P(e);
if (nr > 0 or nw >0) {dw = dw+1; V(e); P(w); }
nw = nw
+1;
SIGNAL: 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
}
else
v(e); # release the entry (mutex) lock
write the database;
# <nw
= nw-1;>
P(e);
nw = nw-1;
SIGNAL: 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
}
else
v(e); # release the entry (mutex) lock
}
}
int nr = 0, nw = 0; #RW: (nr==0 or nw==0)
and nw<=1
sem e=1, r=0, w=0; #controlling entry to crit. sect.
and holding delayed readers and writers
int dr =0, dw = 0; #counting delayed readers and writers
process Reader [ i = 1 to M] {
while(true) {
# <await (nw ==0) nr = nr + 1;
>
P(e);
if (nw > 0 {dr
= dr + 1; V(e); P(r); }
nr = nr +1;
if (dr > 0) {dr = dr - 1; V(r); }
else V(e);
read the database;
#<nr = nr -1;>
P(e);
nr = nr -1;
if ( nr ==0 and dw > 0) { dw = dw -1; V(w)}
else V(e);
}
}
process Writer [j = 1 to N] {
while(true) {
# <await nr==0 and nw==0) nw = nw+1;>
P(e);
if (nr > 0 or nw >0) {dw = dw+1; V(e); P(w); }
nw = nw
+1;
V(e);
write the database;
# <nw = nw-1;>
P(e);
nw = nw-1;
if (dr > 0) { dr = dr - 1; V(r);}
elseif (dw
> 0) { dw = dw - 1;
V(w); }
else V(e);
}
}