基于信号量的单车道桥同步
我正在尝试实现单车道桥同步问题。一次，汽车只能朝一个方向行驶，而且这座桥的容量也是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);同步并不是work.When，我测试这一点，我可以看到方向为1和2的汽车同时进入。
else
{
ReleaseMutex(mut_mutex);
WaitForSingleObject(sem_bridgempty, INFINITE); //line 1
WaitForSingleObject(mut_mutex, INFINITE);//line 2假设Thread1和2方向都在等待sem_bridge_empty。当桥变为空(direction=-1)时，它出现在第2行。但是在获得mut_mutex之前，另一个具有1 =1的线程调用enter，当控制返回thread1时看到direction=-1和enters.Now，它也进入direction=2，因为它忽略了另一个线程已经进入了不同方向的线程这一事实。如何使mut_mutex和sem_bridge_empty同步？
回答 2
Stack Overflow用户
发布于 2017-07-16 22:46:46
您的WaitForSingleObject(mut_mutex)不匹配ReleaseMutex(mut_mutex)计数-您(在enter中)2或3次为单个WaitForSingleObject调用ReleaseMutex，这已经是一个严重的错误。if (direction == curr_direction)已经在同步部分之外调用了-因此curr_direction可以在任何时候更改。
正确的解决方案-检查和修改必须是“原子”操作-在某些关键部分。所以把一些cs和桥联系起来，它会保护它的状态。当汽车试着进入桥-输入一次(！)对此，决定是汽车可以进入还是需要等待。从cs出口出来。如果需要的话-等等(当然是在cs之外)。在这里也可以使用互斥锁，但使用cs或SRW锁要好得多--因为有了互斥锁，每次输入内核进行同步时，您都会使用互斥锁。只有在真正需要等待的时候。
另外，你也没有考虑到下一个情况-- if (direction == curr_direction)，你总是进入桥牌。但是，如果从相反的地点已经等待了一些汽车呢？先入桥的一侧(方向)可以无限地握住它(假设这个方向上有无限车流)，当另一个方向将是无限等待。为了解决这一问题，需要添加一些“红绿灯”--即使卡尔在目前的桥梁方向移动并在桥上存在自由空间--如果汽车已经从相反的方向等待，它也可以停下来等待。
还请注意如何将参数(方向)传递给线程--为什么是指针而不是值？如果这是c++ -为什么不封装桥逻辑(所有的变量和同步对象在某些结构中？
我将选择下一个解决方案(有统计数据)：
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();
一些统计输出：(有多少辆车在各个方向通过桥，现在有多少辆车在桥上，以及它的方向(+/-))。现在有多少辆车在等着呢？
<(+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和MaxTransitsWhenOppositeWait，例如，当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)>Stack Overflow用户
发布于 2017-07-16 18:34:00
我想我会采取完全不同的做法。
我认为问题就在于如何更接近真实生活的模型。
有座桥。桥的每一端都有一排队伍，汽车在那里等候入口处。有一个代理(对应于桥头的旗手)可以将汽车从队列中释放出来。
想要跨过桥的汽车(线程)会创建一个事件，并将事件放入队列中，以便沿着桥的任何方向过桥。然后它就会在这个事件上睡觉。当它到达队列的前端，代理决定释放该汽车时，它会将事件从队列中移除并发出信号。然后，汽车驶过了桥。当它到达另一端时，它会通过执行ReleaseSemaphore通知它正在离开桥。
每个代理人都在等待(我相信)三个因素：
- 方向==我的方向
- 桥上有地方
- 我的队伍里至少有一辆车
当发生这种情况时，它会从队列中释放一辆汽车，然后重复。
如果您想添加一点点缀，代理可以在其队列为空时(或者仅当它在短时间内保持空)时释放其剩余的时间片段。
至少对我来说，这似乎更容易实现，而且要现实得多。当桥改变方向时，我们不想只选择五辆随机的车通过--我们总是选择那些等待时间最长的车。
如果我们想让事情变得更加现实，我们可以把它变成一个德行，而不是一个队列。紧急车辆(救护车、消防车等)会走到衣柜前面而不是后面。当他们到达时，移动另一个方向的车辆的计时器将立即过期(但他们仍然会等待桥上的车辆在进入之前离开)。
https://stackoverflow.com/questions/45125598
复制相似问题
腾讯云开发者
