シングルレーンブリッジセマフォを使用した同期

Question

シングルレーンブリッジ同期の問題を実装しようとしています。 一度に車は一方向にしか行くことができませんし、橋の容量も5です。私は下に何かを考え出しました。

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); 

同期は私が同時に入る方向1と2で車を見ることができ、これをテストするものではありませんwork.When。

else 
    { 
     ReleaseMutex(mut_mutex); 
     WaitForSingleObject(sem_bridgempty, INFINITE); //line 1 
     WaitForSingleObject(mut_mutex, INFINITE);//line 2 

は方向2とスレッド1がsem_bridge_emptyを待っていると仮定します。 ブリッジ（direction=-1）空になると、それはmut_mutexを取得する前に、それは制御がスレッド1に戻ったとき、それはまたためdirection=2と入射enterを呼び出し、direction=-1を見てenters.Now 1方向と別のスレッド=、ライン2.Butに付属異なる方向の別のスレッドが既に入っているという事実を知らない。 mut_mutexとsem_bridge_emptyを同期させるにはどうすればよいですか？

Answer 1

あなたWaitForSingleObject(mut_mutex)ReleaseMutex(mut_mutex)数と一致していない - あなたを（入力中）2または3回は、単一のWaitForSingleObjectこのすでに重大なバグのためReleaseMutexを呼び出します。 if (direction == curr_direction)は、同期部の外側に既に呼ば - そうcurr_directionはいつでも変更することができます。

正解 - チェックおよび変更は、「アトミック」操作でなければならない - いくつかの重要なセクション内。それに状態を守るされる、ブリッジといくつかCSを関連付けます。カーブリッジに入力しようとすると - （！）を1回入力します。このCSには、決め車が入るか待つ必要があることができます。出口cs待っている必要がある場合は待ちます（もちろんの外側にあります。）。 ミューテックスも、ここで使用することができるが、ロックはるかに優れてCSかSRWを使用 - ミューテックスとあなたが毎回同期のためのカーネルに入ることになるので。 csで - 本当に待たなければならない時のみ。

もそのアカウントに次のような状況にならない - if (direction == curr_direction)あなたは常に埋めるために入力します。反対側のサイトから既にいくつかの車を待っていたら？橋に入る最初の側（方向）はそれを無限に保持することができます（この方向で無限の流れを仮定します）。これを解決するためには、たとえcarrが現在の橋の方向に動いていても橋の自由空間が存在していても、 "信号機"を追加する必要があります。なぜポインタではなく値で -

はまた、あなたがスレッド化にパラメータ（方向）を渡す方法に注意してください？これは、C++の場合 - ブリッジロジック（いくつかの構造体のすべてのIT変数と同期オブジェクト

をカプセル化していない理由を私は統計と次のソリューション（）を選択すること：車が橋の上を行くかのチェックのために

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)>\n", 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); 
     } 
    } 
} 

？私はすべてのn * 0x1000番地の終了にいくつかのstatを集めるも、私は方向が正しいことを確認し、すべての終了時に次の点に注意してください。if (_direction != direction) __debugbreak();

いくつかのstat出力：あらゆる方向に橋を経てどのように多くの車（、どのように多くの車今橋の上方向（+/-）、現在何台の車が待っているか ）

<(+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)> 

はまた、あなたがメッセージボックスのコメントを解除し、「手動」モードでコントロール車のための遷移の数を減らすことができコルスの

はまた、例えばMaxPositionsとMaxTransitsWhenOppositeWaitenum { 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)> 

Answer 2

私はこれをむしろ違うと思います。

私が問題を見る方法は、実際の生活を少しずつモデル化することです。

橋があります。橋の両端には車が入るための待ち行列があります。キューから車を解放できるエージェント（橋の端にある旗人に対応する）があります。

橋を渡りたい車（スレッド）は、イベントを作成し、どの方向に橋を渡すためにイベントをキューに入れます。その後、イベントで眠ります。それが待ち行列の前面に到達し、エージェントがその自動車を解放することを決定すると、待ち行列からイベントを取り除き、それを通知します。その後、車は橋を渡って進みます。もう一方の端に達すると、ReleaseSemaphoreを実行して橋を離れることが通知されます。

各エージェントには、三つの要因（私は信じている）上の待機：

1. 方向==私の方向
2. 橋の上に部屋があります
3. 私のキュー内の少なくとも1台の車があります

これらが発生すると、そのキューから車を解放し、その後繰り返します。

少し装飾を追加したい場合、エージェントはそのキューが空のとき（または何らかの短時間以上空になっているときだけ）、タイムスライスの残りの部分を解放することができます。

少なくとも私には、これは実装が簡単で、かなり現実的です。ブリッジが方向を変えるとき、私たちは5台のランダムな車を選んで通過するのを望んでいません - 私たちは常に最長のものを選びます。

さらに現実的なものにしたい場合は、キューではなく両端キューにすることができます。緊急車両（救急車、消防車など）は、背中の代わりに靴下の前に行きます。彼らが到着すると、他の方向に移動する車両のタイマーはすぐに期限切れになります（しかし、彼らはまだ彼らが入力する前にブリッジ上の車両が終了するのを待つだろう）。