One lane bridge using semaphores

2019-06-14 05:55发布

问题:

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