In the University I'm given this canonical parallel programming problem from "Gregory R. Andrews-Foundations of Multithreaded .... programming": (though I have a newer and Russian edition of the book I found an old English variant and try to convey everything properly)
The One Lane Bridge. Cars coming from the north and the south arrive at a one-
lane bridge. Cars heading in the same direction can cross the bridge at the same
time, but cars heading in opposite directions cannot.
Specify a global invariant Develop a fair solution such that cars could move in groups of no more than m cars.... Use semaphores to solve this task
(Yeah I know there is single-lane bridge problem but) The lecturer told me to make it using means described in the book Specifically: Use "Readers Writers" problem's solution where I should have two kinds of processes (north_car and south_car) both of which should behave like "readers" so I tried to mimic the solution:
Readers/Writers:
//RW: (nr == 0 or nw == 0) and nw <= 1 "global invariant" (=A "good" state)
int nr = 0,nw = 0;
sem e = 1, //used to perform atomic actions
r = 0, //used to pause readers
w = 0; //used to pause writers
//always 0<=(e+r+w)<=1, (e,r,w) form a "shared binary semaphore"
int dr = 0, //number of paused readers
dw = 0; //number of paused writers
process Reader[i = 1 to M] {
while (true) {
P(e);
if (nw >0) { dr = dr+1; V(e); P(r); } //(1)
nr = nr+1;
if(dr>0){dr=dr-1;V(r);} //"passing baton"
else V(e);
read resource;
P(e);
nr = nr-1;
if(nr==0 and dw>0){dw=dw-1;V(w);} //"passing baton"
else V(e);
}
}
process Writer[i = 1 to N] {
while (true) {
P(e);
if (nr > 0 or nw >0) { dw = dw+1; V(e); P(w); }
nw = nw+1;
V(e)
write resource;
P(e);
nw = nw-1;
if(dr>0){dr=dr-1;V(r);} //(2) continue reader-process
elseif (dw>0){dw=dw-1;V(w);} //(3) continue writer-process
else V(e); //release entry lock
}
}
And so here is my wrong try to solve my problem:
int nn = 0,ns = 0;
int m;//consider initialised
sem e = 1,
n = 0,
s = 0; //lecturer's comment: "l+n+s=1 ??"
int dn = 0, ds = 0;
## RW: (nn == 0 and ns < m) or (ns == 0 and nn < m) "global invariant"
process North_car[i = 1 to N] {
while (true) {
P(e);
if (ns >0) { dn = dn+1; V(e); P(n); }
if(nn<mm){ //I tried to add this when was asked
//"WHERE IS THE "move in groups of no more than m cars" CONDITION??"
//but it seems no luck(
nn = nn+1;
if(dn>0){dn=dn-1;V(n);} //"passing baton"
else V(e);
cross bridge going from north;
P(e);
nn = nn-1;
if(nn==0 and ds>0){ds=ds-1;V(s);}
else V(s);
} //I tried to add this
}
}
process South_car[i = 1 to S] {
while (true) {
P(e);
if (nn >0 or ns > m) { //my another try is adding "or ns > m"
ds = ds+1; V(e); P(s);
}
if(ns<m){ //I tried to add this
ns = ns+1;
if(ds>0){ds=ds-1;V(s);} //"passing baton"
else V(e);
cross bridge going from south;
P(e);
ns = ns-1;
if(ns==0 and dn>0){dn=dn-1;V(n);}
else V(s);
} //I tried to add this
}
}
But of course my solution is just a try to randomly mimic code from book... And it's not a proper solution to the problem. Help me please to solve it properly using this proposed syntax. My next task is to solve analogous task using "Monitor" I decided to post that as another question