c ++ - Enkeltløbsbro Synkronisering ved brug af semaforer

Indlæg af Hanne Mølgaard Plasc

Problem



Jeg forsøger at implementere Single Lane Bridge synkroniseringsproblem.
På et tidspunkt kan biler kun gå i en retning, og også broens kapacitet er 5. Jeg er kommet op med noget nedenfor.


int curr\_direction = -1;
//curr\_direction values can be -1,1 and 2.-1 means bridge is empty
int cars\_count = 0; 
HANDLE sem\_bridgempty;//To keep track whether the bridge is empty or not
HANDLE sem\_bridgecount; //To keep track of count of cars on bridge
HANDLE mut\_mutex;//For exclusive access
unsigned WINAPI enter(void *param) 
{
    int direction = *((int *)param);
    WaitForSingleObject(mut\_mutex,INFINITE);
    if (curr\_direction == -1)
        curr\_direction = direction;
    ReleaseMutex(mut\_mutex);
    WaitForSingleObject(sem\_bridgecount, INFINITE);//Wait if more than 5 cars
    WaitForSingleObject(mut\_mutex, INFINITE);
    if (direction == curr\_direction)
    {
        cars\_count++;
        std::cout << "Car with direction " << direction << " entered " << 
      GetCurrentThreadId() << std::endl;
    ReleaseMutex(mut\_mutex);
    }
    else
    {
        ReleaseMutex(mut\_mutex);
        WaitForSingleObject(sem\_bridgempty, INFINITE);//Wait for bridge to be empty so other direction car can enter
        WaitForSingleObject(mut\_mutex,INFINITE);
        curr\_direction = direction;
        cars\_count++;
        std::cout << "Car with direction " << direction << " entered " << GetCurrentThreadId() << std::endl;
        ReleaseMutex(mut\_mutex);
    }
    return 0;
}
unsigned WINAPI exit(void *param)
{   
    WaitForSingleObject(mut\_mutex, INFINITE);
    cars\_count--;
    std::cout << "A Car exited " << GetCurrentThreadId() << std::endl;
    ReleaseSemaphore(sem\_bridgecount, 1, NULL);
    if (cars\_count == 0)
    {
        curr\_direction = -1;
        std::cout << "Bridge is empty " << GetCurrentThreadId() << 
        std::endl;
        ReleaseSemaphore(sem\_bridgempty, 1, NULL);
    }
    ReleaseMutex(mut\_mutex);
    return 0;
 }

 int main()
{
sem\_bridgecount = CreateSemaphore(NULL, 5, 5, NULL);
sem\_bridgempty = CreateSemaphore(NULL, 0, 1, NULL);
sem\_bridge\_not\_empty = CreateSemaphore(NULL, 0, 2, NULL);
mut\_mutex = CreateMutex(NULL, false, NULL);


Synkroniseringen virker ikke. Når jeg tester dette, kan jeg se biler med retning 1 og 2 på samme tid.


  else
    {
        ReleaseMutex(mut\_mutex);
        WaitForSingleObject(sem\_bridgempty, INFINITE); //line 1
        WaitForSingleObject(mut\_mutex, INFINITE);//line 2


Antag, at tråd 1 med retning 2 venter på sem\_bridge\_empty.
Når broen bliver tom (direction=-1), kommer den på linje 2. Men før den køber mut\_mutex, kalder en anden tråd med retning=1 enter og ser direction=-1 og går ind. Nu når kontrol kommer tilbage på tråd 1, går det også ind med direction=2, fordi det er uvidende om, at en anden tråd allerede er indtastet, som er af forskellig retning.
Hvordan kan jeg bringe mut\_mutex og sem\_bridge\_empty i synkronisering?

Bedste reference


din WaitForSingleObject(mut\_mutex) stemmer ikke overens med ReleaseMutex(mut\_mutex) - du (i indtastning) 2 eller 3 gange kalder ReleaseMutex for single WaitForSingleObject denne allerede kritiske fejl. if (direction == curr\_direction) kaldes allerede uden for synkroniseringssektionen - så curr\_direction kan ændres til enhver tid.


Korrekt løsning - Kontroller og modificer skal være 'atomisk' operation - inde i nogle kritiske afsnit. så associerer nogle cs med bro, som vil være vagt det stat. Når bilen forsøger at gå ind for at bro - indtast en gang (!) til denne cs , beslutte, at bilen kan komme ind eller skal vente. Afslut cs . og om nødvendigt vent - vent (selvfølgelig udenfor cs ). mutex kan også bruges her, men bruge cs eller SRW låse meget bedre - fordi med mutex bliver du hver tid indtaste kerne for synkronisering. med cs - kun når du virkelig har brug for at vente.


også du tager ikke højde for næste situation - if (direction == curr\_direction) du indtaster altid for at bro. men hvad nu hvis der fra en modsat side allerede ventede nogle biler? den side (retning), hvilken næve går ind i broen, kan uendelig holde den (antage uendelig bilstrøm i denne retning), når en anden retning vil være uendelig ventetid. for at løse dette - brug for at tilføje noget 'trafiklys' - selvom carr flyttede i nuværende broretning og eksisterer ledig plads på broen - det kan stoppe og vente, hvis allerede biler ventede fra modsatte side.


Bemærk også, hvordan du passerer parameter (retning) til tråd - hvorfor med peger men ikke efter værdi? og hvis dette er c ++ - hvorfor ikke indkapsler brologikken (alle det er variabler og synkroniseringsobjekter i nogle struct?


Jeg vælger næste løsning (med statistik):


struct Bridge : CRITICAL\_SECTION
{
    enum { MaxPositions = 3, MaxTransitsWhenOppositeWait = 1 };

    HANDLE \_hSemaphore[2];
    ULONG \_nWaitCount[2];
    ULONG \_nFreePositions, \_nTransits;
    LONG \_direction;

    //+++ statistic for test only

    struct STAT {
        ULONG \_Exits[2];
        ULONG \_nWaitCount[2];
        LONG \_direction;
        ULONG \_CarsOnBridge;
    } \_stat[16];

    ULONG \_i\_stat, \_Exits[2], \_nExits;

    void CollectStat(LONG direction)
    {
        \_Exits[direction]++;

        if (!(++\_nExits & 0xfff))// on every 0x1000*n exit save stat
        {
            if (\_i\_stat)
            {
                STAT *stat = &\_stat[--\_i\_stat];
                stat->\_CarsOnBridge = MaxPositions - \_nFreePositions;
                stat->\_direction = direction;
                stat->\_nWaitCount[0] = \_nWaitCount[0];
                stat->\_nWaitCount[1] = \_nWaitCount[1];
                stat->\_Exits[0] = \_Exits[0];
                stat->\_Exits[1] = \_Exits[1];
            }
        }
    }

    void DumpStat()
    {
        if (ULONG i = RTL\_NUMBER\_OF(\_stat) - \_i\_stat)
        {
            do 
            {
                STAT *stat = &\_stat[\_i\_stat++];
                DbgPrint("<(+\%05u, -\%05u) \%c\%u (+\%u, -\%u)>
", stat->\_Exits[0], stat->\_Exits[1], 
                    stat->\_direction ? '-' : '+', 
                    stat->\_CarsOnBridge, stat->\_nWaitCount[0], stat->\_nWaitCount[1]);
            } while (--i);
        }
    }

    void InitStat()
    {
        RtlZeroMemory(\_Exits, sizeof(\_Exits)), \_nExits = 0;
        RtlZeroMemory(\_stat, sizeof(\_stat)), \_i\_stat = RTL\_NUMBER\_OF(\_stat);
    }

    //--- statistic for test only

    void Lock() { EnterCriticalSection(this); }

    void Unlock() { LeaveCriticalSection(this); }

    Bridge()
    {
        InitializeCriticalSection(this);

        \_hSemaphore[0] = 0, \_hSemaphore[1] = 0;
        \_nWaitCount[0] = 0, \_nWaitCount[1] = 0;

        \_nFreePositions = MaxPositions, \_nTransits = MaxTransitsWhenOppositeWait, \_direction = -1;

        InitStat();
    }

    ~Bridge()
    {
        DeleteCriticalSection(this);

        if (\_hSemaphore[1]) CloseHandle(\_hSemaphore[1]);

        if (\_hSemaphore[0]) CloseHandle(\_hSemaphore[0]);

        if (\_nWaitCount[0] || \_nWaitCount[1] || \_nFreePositions != MaxPositions)
        {
            \_\_debugbreak();
        }

        DumpStat();
    }

    BOOL Create()
    {
        return (\_hSemaphore[0] = CreateSemaphore(0, 0, MaxPositions, 0)) &&
            (\_hSemaphore[1] = CreateSemaphore(0, 0, MaxPositions, 0));
    }

    BOOL IsOppositeSideWaiting(LONG direction)
    {
        return \_nWaitCount[1 - direction];
    }

    void EnterCars(LONG direction, ULONG n)
    {
        if (IsOppositeSideWaiting(direction))
        {
            \_nTransits--;
        }

        \_nFreePositions -= n;
    }

    void Enter(LONG direction)
    {
        BOOL bWait = FALSE;

        Lock();

        if (\_direction < 0)
        {
            \_direction = direction;
            goto \_\_m0;
        }
        else if (\_direction == direction && \_nFreePositions && \_nTransits)
        {
\_\_m0:
            EnterCars(direction, 1);
        }
        else
        {
            bWait = TRUE;
            \_nWaitCount[direction]++;
        }

        Unlock();

        if (bWait)
        {
            if (WaitForSingleObject(\_hSemaphore[direction], INFINITE) != WAIT\_OBJECT\_0)
            {
                \_\_debugbreak();
            }
        }
    }

    void Exit(LONG direction)
    {
        if (\_direction != direction)
        {
            \_\_debugbreak();
        }

        Lock();

        CollectStat(direction);

        if (++\_nFreePositions == MaxPositions)
        {
            // bridge is empty
            \_direction = -1, \_nTransits = MaxTransitsWhenOppositeWait;

            // change direction if opposite side wait
            if (IsOppositeSideWaiting(direction))
            {
                direction = 1 - direction;
            }
        }

        HANDLE hSemaphore = \_hSemaphore[direction];

        ULONG n = \_nTransits ? min(\_nWaitCount[direction], \_nFreePositions) : 0;

        if (n)
        {
            \_direction = direction;
            EnterCars(direction, n);
            \_nWaitCount[direction] -= n;

            ReleaseSemaphore(hSemaphore, n, 0);
        }

        Unlock();
    }

} g\_Bridge;

ULONG car(LONG direction)
{
    direction &= 1;// 0 or 1

    WCHAR caption[16];

    int i = 0x10000;// Number of transits

    do 
    {
        swprintf(caption, L"[\%u] \%08x", direction, GetCurrentThreadId());
        //MessageBoxW(0, 0, caption, MB\_OK);

        SwitchToThread();// simulate wait

        g\_Bridge.Enter(direction);

        SwitchToThread();// simulate wait
        //MessageBoxW(0, 0, caption, direction ? MB\_ICONWARNING : MB\_ICONINFORMATION);

        g\_Bridge.Exit(direction);

        direction = 1 - direction;// reverse direction

    } while (--i);

    return direction;//visible thread exit code in debug window
}

void SLBT()
{
    if (g\_Bridge.Create())
    {
        HANDLE hThreads[8], *phThread = hThreads, hThread;
        ULONG n = RTL\_NUMBER\_OF(hThreads), m = 0;
        do 
        {
            if (hThread = CreateThread(0, PAGE\_SIZE, (PTHREAD\_START\_ROUTINE)car, (PVOID)n, 0, 0))
            {
                *phThread++ = hThread, m++;
            }
        } while (--n);

        if (m)
        {
            WaitForMultipleObjects(m, hThreads, TRUE, INFINITE);
            do 
            {
                CloseHandle(*--phThread);
            } while (--m);
        }
    }
}


for at kontrollere, hvordan biler går på bro, samler jeg nogle stat på hver n * 0x1000 udgang. Bemærk også, at på hver exit skal du kontrollere, at retningen er korrekt: if (\_direction != direction) \_\_debugbreak();


nogle stat output: ( hvor mange biler gik i broen i hver retning, hvor mange biler nu på broen og den retning (+/-). og hvor mange biler venter nu )


<(+32768, -32768) +3 (+2, -3)>
<(+30720, -30720) -2 (+2, -3)>
<(+28672, -28672) +3 (+2, -3)>
<(+26625, -26623) +1 (+2, -5)>
<(+24576, -24576) -3 (+3, -2)>
<(+22529, -22527) +1 (+2, -5)>
<(+20480, -20480) +2 (+3, -2)>
<(+18432, -18432) +3 (+1, -3)>
<(+16385, -16383) +1 (+2, -3)>
<(+14335, -14337) -1 (+4, -2)>
<(+12288, -12288) +3 (+2, -3)>
<(+10239, -10241) -1 (+3, -2)>
<(+08192, -08192) +2 (+3, -3)>
<(+06143, -06145) -1 (+3, -2)>
<(+04096, -04096) +3 (+2, -3)>
<(+02048, -02048) +2 (+3, -3)>


Du kan også ukommentere meddelelsesbokse og reducere Antal overgange til kontrolbiler i 'manuel' tilstand


of corse kan også spille med MaxPositions og MaxTransitsWhenOppositeWait for eksempel når enum { MaxPositions = 5, MaxTransitsWhenOppositeWait = 2 };


<(+32766, -32770) -1 (+7, -0)>
<(+30721, -30719) -5 (+0, -1)>
<(+28674, -28670) +1 (+0, -7)>
<(+26623, -26625) +5 (+2, -0)>
<(+24574, -24578) -1 (+7, -0)>
<(+22528, -22528) -5 (+0, -0)>
<(+20479, -20481) -3 (+2, -0)>
<(+18431, -18433) +5 (+2, -1)>
<(+16383, -16385) +5 (+2, -0)>
<(+14337, -14335) -5 (+0, -2)>
<(+12290, -12286) +1 (+0, -5)>
<(+10241, -10239) -5 (+0, -2)>
<(+08190, -08194) -1 (+7, -0)>
<(+06143, -06145) -2 (+3, -1)>
<(+04096, -04096) +5 (+0, -1)>
<(+02047, -02049) -3 (+1, -0)>

Andre referencer 1


Jeg tror, ​​at jeg vil gå om det lidt anderledes.


Hvordan jeg kunne se problemet ville være at modellere virkeligheden lidt nærmere.


Der er en bro. Der er en kø i hver ende af broen, hvor biler venter på indrejse. Der er en agent (svarende til flagmand ved enden af ​​broen), der kan frigøre biler fra en kø.


En bil (tråd), der ønsker at krydse broen, skaber en begivenhed og sætter begivenheden i køen for at krydse broen i hvilken retning den går. Den sover derefter på arrangementet. Når det kommer til køens forside og agenten beslutter at frigive denne bil, den fjerner begivenheden fra køen og signalerer den. Bilen fortsætter derefter over broen. Når den kommer til den anden ende, meddeles det, at den forlader broen ved at lave en ReleaseSemaphore.


Hver agent venter på (tror jeg) tre faktorer:



  1. Retning == min retning

  2. Der er plads på broen

  3. Der er mindst en bil i min kø



Når de opstår, frigiver den en bil fra sin kø, og gentager derefter.


Hvis du vil tilføje en lille udsmykning, kan en agent frigive resten af ​​sit tidsskive, når køen er tom (eller måske kun når den forbliver tom for mere end en kort periode).


I hvert fald for mig synes dette at være enklere at gennemføre og betydeligt mere realistisk. Når broen skifter retning, vil vi ikke bare vælge fem tilfældige biler til at lade gennem - vi vælger altid de, der har ventet længst.


Hvis vi ville gøre tingene endnu mere realistiske, kunne vi gøre det til en dæk i stedet for en kø. Nødkøretøjer (ambulance, brandbil osv.) Ville gå til forsiden af ​​dækket i stedet for bagsiden. Når de ankommer, vil timeren for køretøjerne, der bevæger sig i den anden retning, udløbe straks (men de 'v stadig venter på køretøjer på broen for at afslutte før de kom ind).