使用信号量的单车道桥同步 [英] Single lane bridge Synchronization using semaphores
问题描述
我正在尝试实现单车道桥同步问题. 一次，汽车只能朝一个方向行驶，桥的最大载重为5.我在下面提出了一些建议.
I am trying to implement Single Lane Bridge synchronization problem. At a time, cars can go in one direction only and also the capacity of the bridge is 5.I have come up with something below.
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的汽车同时进入.
The synchronization does not work.When i test this i can see cars with direction1 and 2 entering at same time.
else
{
ReleaseMutex(mut_mutex);
WaitForSingleObject(sem_bridgempty, INFINITE); //line 1
WaitForSingleObject(mut_mutex, INFINITE);//line 2
假定方向为2的线程1正在等待sem_bridge_empty.
当网桥变空(direction=-1)时，它位于第2行，但是在获取mut_mutex之前，另一个方向= 1的线程调用enter并看到direction=-1并进入.现在，当控制权返回时在线程1处，它也以direction=2进入，因为它忽略了已经进入了另一个方向不同的事实.
如何同步同步mut_mutex和sem_bridge_empty?
Suppose Thread1 with direction 2 is waiting for sem_bridge_empty.
When the bridge becomes empty(direction=-1), it comes at line 2.But before it acquires mut_mutex, another thread with direction = 1 calls enter and sees direction=-1 and enters.Now when control comes back at thread1, it also enters with direction=2 because it is oblivious of the fact that another thread has already entered which is of different direction.
How can i bring mut_mutex and sem_bridge_empty in sync?
推荐答案
您的WaitForSingleObject(mut_mutex)不匹配ReleaseMutex(mut_mutex)计数-您(输入)需要2到3次针对单个WaitForSingleObject调用ReleaseMutex，这已经是严重的错误. if (direction == curr_direction)已经在同步部分之外被调用-因此curr_direction可以随时更改.
your WaitForSingleObject(mut_mutex) not match ReleaseMutex(mut_mutex) count - you (in enter) 2 or 3 times call ReleaseMutex for single WaitForSingleObject this already critical bug. if (direction == curr_direction) called already outside of synchronization section - so curr_direction can be changed at any time.
正确的解决方案-检查和修改必须是原子"操作-在某些关键部分内.因此，将某些 cs 与网桥相关联，以保护其状态.当汽车尝试进入桥梁时-在此 cs 中输入一次(！)，确定汽车可以进入还是需要等待.退出 cs .以及是否需要等待-等待(当然在 cs 之外). mutex 也可以在这里使用，但是使用 cs 或 SRW 锁定要好得多-因为有了 mutex ，您将成为时间进入内核进行同步.使用CS-仅在真正需要等待时使用.
correct solution - check and modify must be "atomic" operation - inside some critical section. so associate some cs with bridge, which will be guard it state. when car try enter to bridge - enter once(!) to this cs, decide are car can enter or need wait. exit cs. and if need wait - wait (of course outside cs). mutex also can be used here but use cs or SRW locks much better - because with mutex you will be every time enter kernel for synchronization. with cs - only when really need wait.
也不会考虑下一种情况-if (direction == curr_direction)您总是输入要桥接.但是如果从对面的站点已经等了些车怎么办?拳头进入桥的一侧(方向)可以无限地保持它(假设此方向上有无限的车流)，而另一个方向将无限等待.为了解决这个问题-需要添加一些交通灯"-即使carr沿当前桥梁方向移动并且桥上存在自由空间-如果已经有汽车从对侧等候，它也可以停止并等待.
also you not take in account next situation - if (direction == curr_direction) you always enter to bridge. but what if from opposite site already waited some cars ? the side (direction) which fist enter to bridge can infinite hold it (assume infinite car stream in this direction), when another direction will be infinite wait. for solve this - need add some "traffic light" - even if carr moved in current bridge direction and exist free space on bridge - it can stop and wait, if already cars waited from opposite side.
还请注意如何将参数(方向)传递给线程-为什么按指针而不按值?如果是c ++，为什么不封装网桥逻辑(所有变量和同步对象在某些结构中?
also note how you pass parameter (direction) to thread - why by pointer but not by value ? and if this is c++ - why not encapsulate bridge logic (all it variables and synchronization objects in some struct ?
我将选择下一个解决方案(具有统计信息):
i be select next solution (with statistic):
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出口处收集一些统计信息.还要注意，在每个出口我都检查方向是否正确:if (_direction != direction) __debugbreak();
for check how cars go on bridge i collect some stat on every n*0x1000 exits. also note that on every exit i check direction is correct : if (_direction != direction) __debugbreak();
一些统计信息输出:(在每个方向上有多少辆汽车经过桥梁，现在在桥梁上有多少辆汽车，并且它的方向(+/-).现在有多少辆汽车在等待)
some stat output: (how many cars gone through bridge in every direction, how many cars now on bridge and it direction(+/-). and how many cars wait now)
<(+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)>
您还可以取消注释消息框并减少手动"模式下控制汽车的过境次数
also you can uncomment messageboxes and reduce Number of transits for control cars in "manual" mode
也可以与MaxPositions和MaxTransitsWhenOppositeWait一起玩.
of corse also can play with MaxPositions and MaxTransitsWhenOppositeWait for example when 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)>
这篇关于使用信号量的单车道桥同步的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
