互斥和信号量 [英] Mutual exclusion and semaphores
问题描述
我正在编写一个模拟男女通用浴室的程序(用于家庭作业).一次只能容纳4人，并且如果其他性别已经在使用洗手间，则男人和女人无法进入.我的问题是最多允许4个人进入洗手间.从输出中可以看到，一次只有1个人进入洗手间.这是我的代码:
I am writing a program (for homework) that simulates a unisex bathroom. Only 4 people are allowed at a time and men and woman cannot enter if the other sex is already using the bathroom. My problem is with allowing a max of 4 people in the bathroom. As you can see from the output, only 1 person is getting into the restroom at a time. Here is my code:
const int Delayx = 60;
int i;
int restroom = 0;
int Menwaiting = 0;
int Womenwaiting = 0;
semaphore max_capacity;
semaphore woman;
semaphore man;
semaphore mutex;
semaphore restroomcount;
void Delay(void)
{
int DelayTime;
DelayTime = random(Delayx);
for (i = 0; i<DelayTime; i++);
}
void Woman(void)
{
// for(;;){
Womenwaiting++;
//wait(mutex);
wait(woman);
wait(max_capacity);
//wait(woman);
wait(mutex);
wait(restroomcount);
cout << "A Woman has entered Restroom"<<endl;
cout << "People in the Restroom:" << restroom++ <<endl <<endl;
signal(restroomcount);
Womenwaiting--;
Delay();
wait(restroomcount);
cout << "A woman has exited Restroom"<<endl;
cout << "People in the Restroom:" << restroom-- <<endl<<endl;
signal(restroomcount);
signal(mutex);
signal(max_capacity);
if(Menwaiting > Womenwaiting){
signal(man);
}
else{
signal(woman);
}
//signal(max_capacity);
//signal(man);
// }
}
void Man(void)
{
// for(;;){
Menwaiting++;
//wait(mutex);
wait(man);
wait(max_capacity);
//wait(man);
wait(mutex);
wait(restroomcount);
cout <<"A Man has entered the Restroom"<<endl;
cout <<"People in the Restroom:" << restroom++ <<endl<<endl;
signal(restroomcount);
Menwaiting--;
//signal(mutex);
Delay();
//wait(mutex);
wait(restroomcount);
cout << "A man has exited the Restroom"<<endl;
cout <<"People in the Restroom:" << restroom-- <<endl<<endl;
signal(restroomcount);
signal(mutex);
signal(max_capacity);
if(Womenwaiting > Menwaiting){
signal(woman);
}
else{
signal(man);
}
//signal(max_capacity);
//signal(woman);
//}
}
void main()
{
initialsem(woman,1);
initialsem(man,1);
initialsem(max_capacity,4);
initialsem(mutex,1);
initialsem(restroomcount,1);
cobegin
{
Woman(); Woman(); Woman(); Woman(); Woman(); Man(); Man(); Man(); Man(); Man();
}
}
这将产生以下输出:
一个人进入洗手间
洗手间里的人:1
A Man has entered the Restroom
People in the Restroom:1
一个男人已经离开洗手间
洗手间的人:0
A man has exited the Restroom
People in the Restroom:0
一个人进入洗手间
洗手间里的人:1
A Man has entered the Restroom
People in the Restroom:1
一个男人已经离开洗手间
洗手间的人:0
A man has exited the Restroom
People in the Restroom:0
一个女人进入洗手间
洗手间里的人:1
A Woman has entered Restroom
People in the Restroom:1
一个女人离开洗手间
洗手间的人:0
A woman has exited Restroom
People in the Restroom:0
一个女人进入洗手间
洗手间里的人:1
A Woman has entered Restroom
People in the Restroom:1
一个女人离开洗手间
洗手间的人:0
A woman has exited Restroom
People in the Restroom:0
以此类推，直到永远.
推荐答案
使用信号量是否有要求?例如，在"c ++"伪代码中，实现如下所示:
is the use of semaphores a requirement? for example, in "c++" pseudo-code, a implementation would look like:
首先让我们创建一个状态对象和一个验证状态之间转换的函数
First lets create a state object and a function that validates transitions between states
struct BathRoomState
{
int women;
int men;
BathRoomState( int w , int m ) : women(w) , men(m) {}
bool hasWomen()
{
if (women > 0 && men == 0)
return true;
return false;
}
bool isEmpty()
{
return (women + men == 0);
}
static bool isValidTransition( BathRoomState* a , BathRoomState* b )
{
if (a->HasWomen())
{
if ( (abs( a->women - b->women ) == 1) && (a->men == b->men) )
return true;
else false;
} else if (a->isEmpty())
{
if ((b->women == 1 && b->men == 0)
|| (b->women == 0 && b->men == 1))
return true else false;
} else //a has men
{
if ((abs( a->men - b->men ) == 1) && ( a->women == b->women))
return true else false;
}
}
}
我们还要创建一个对当前状态的全局引用，以及一个根据某些下一个所需状态更新当前状态的功能
Lets also create a global reference to the current state and a function to update the current state based on some next desired state
BathRoomState* currentBathroomState = 0;
bool TryToChangeState(BathRoomState* newState)
{
BathRoomState* existingState = currentBathroomState;
if (BathRoomState::isValidTransition( existingState , newState ))
{
//this atomic operation depends on library support
bool success = CompareAndSwapAtomically( currentBathroomState , existingState , newState );
return success;
}
}
然后我们创建一个全局向量来保存状态，并创建一个表示试图去洗手间的女性线程的函数
then we create a global vector to hold the states, and a function representing a women thread trying to go to the bathroom
std::vector< BathRoomState* > noGCinThisExample;
//thread functtion
void women()
{
BathRoomState* existingState = currentBathroomState;
BathRoomState* newState = new BathRoomState( existingState.women+1 , existingState.men );
while (!TryToChangeState(newState))
{
//yield or sleep from time to time here to let other threads progress
existingState = currentBathroomState;
newState.women = existingState.women + 1;
newState.men = existingState.men;
}
noGCinThisExample.push_back( newState ); //no GC in this example
//the woman is in the bathroom now. lets give her some time
delayForWomen();
//lets try to get her out
BathRoomState* exitState = new BathRoomState( existingState.women-1 , existingState.men );
while (!TryToChangeState(exitState ))
{
//yield or sleep from time to time here to let other threads progress
existingState = currentBathroomState;
exitState.women = existingState.women - 1;
exitState.men = existingState.men;
}
noGCinThisExample.push_back( exitState); //no GC in this example
}
//homework: do a similar function for men
以及具有过程循环逻辑和初始化功能的主要功能
and the main function with process loop logic and initialization
void main()
{
BathRoomState* initialState = new BathRoomState( 0 , 0);
noGCinThisExample.push_back( initialState );
currentBathroomState = initialState;
while(some_condition)
{
if (random() > 0.5)
thread( women() );
else
thread( men() );
}
};
此代码应该可以工作(我尚未对其进行测试).我作弊了一点，因为我没有删除创建的任何临时状态，因此每个状态都会一直存在，直到进程终止.正确的垃圾收集将需要一种称为 危险指针管理 的技术.
this code should work ( i haven't tested it ). I've cheated a bit because i'm not deleting any of the provisional states created, so each state persist until the process dies. proper garbage collection would require a technique called hazard pointer management.
请注意，我不使用任何互斥量信号量或锁，我使用的唯一锁定原语是CAS(address，old_value，new_value)(比较和交换).该原语原子地比较一个指针(地址)，如果它仍然包含(旧值)，则将其分配给new_value并成功，否则失败.另外，您仍然需要为std :: vector设置全局锁，以存储我未包含在代码中的状态(您也可以泄漏它们，但是我将它们存储在某个地方，这样您就可以认为一旦知道就应该删除它们)在这些情况下如何使GC工作)
Note that i dont use any mutex semaphores or lock, the only locking primitive i am using is the CAS( address, old_value , new_value ) (compare and swap). This primitive atomically compares a pointer (address) and if it still contains (old_value) then it assign it new_value and succeeds, otherwise it fails. Also, you still need a global lock for the std::vector storing the states that i have not included in the code (you can also just leak them, but i store them somewhere so you can think that those should be deleted once you know how GC could be made to work in these cases)
由于我所有的中间状态都是不可变的(lisp/clojure风格不可变性)，因此线程的争用(因此饥饿)大大改善了.在您的示例中，状态集很小(只是一堆人)，还不错，我们不删除使用过的状态.
Since all my intermediate states are inmutable (lisp/clojure style inmutabilitity) the contention (and hence, starvation) of the threads vastly improves. In your example the set of states is small (just a bunch of persons) its not too bad that we don't delete the used states.
但是，即使遇到了我提到的问题，我认为您也同意发生的事情的逻辑更加明确和易于理解.
however, even with the problems i've mentioned, i think you would agree that the logic of what is happening is much more explicit and readable.
这篇关于互斥和信号量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
