2010-10-03 113 views
11

我正在寫一個模擬一個男女皆宜的浴室的程序(用於作業)。一次只允許4人入住,如果另一個人已經在使用浴室,男人和女人不能入住。我的問題是允許最多4人在浴室。從輸出中可以看到,一次只有1人進入洗手間。這裏是我的代碼:相互排斥和信號量

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

的人已經退出了廁所
洗手間裏的人:0

一個男人已經進入洗手間
人們在廁所:1

的人已經退出了廁所
人們在廁所:0

一個女人進入廁所
人們在廁所:1

一個女人已退出廁所
人們在廁所:0

一個女人進入廁所 在洗手間
人:1

一個女人已經離開廁所
人們在廁所:0

依此類推,直到永遠。

+1

這段代碼的一部分,被認爲是負責預防男人進入洗手間,如果那裏已經有女人了,反之亦然? – 2010-10-03 16:03:43

+0

這個任務應該是單線程的嗎?使用線程?協同程序? – dgnorton 2010-10-03 16:17:35

+23

我不明白:如果男女不能同時進入同一個房間,他們應該怎麼做愛? – ereOn 2010-10-03 16:20:09

回答

0

編輯5(我知道這可能是太少太遲,因爲這很可能一個家庭作業,但我只是想到了一個辦法做到這一點只用信號燈。)

好,這裏是我的僞代碼:

//shared variables 
//the # of men or women in the bathroom 
int menCountIn=0; 
int womenCountIn=0; 

//the # of men or women waiting 
int menCountWtg=0; 
int womenCountWtg=0; 

//whose turn it is to go next 
int turn = -1; 
//-1 = anybody can go 
//0 = only men can go 
//1 = only women can go 

#define capacity 4 

//semaphores 
semaphore mutex; //a sort of bathroom key 
//mutex will protect menCountIn, womenCountIn, and turn 
semaphore waiting; 
//waiting protects the variable count of how many people are waiting 

//Female thread: 
bool in = false; //a thread-specific variable telling me whether I'm in or not 
//will be used in an almost-spinlocking type of way 

wait(waiting); 
womenWaiting++; 
signal(waiting); 

while(!in){ 
    thread.sleep(60); //to avoid constant spinlock 
    wait(mutex); 
    if (menCountIn ==0 && (turn == -1 || turn == 1) && womenIn < capacity) 
    { 
     wait(waiting); 
     womenWtg---; //no longer waiting to get in 
     signal(waiting); 
     womenCountIn++; // a women entered 
     cout << "Woman entered restroom" << endl; 
     in=true; 
    } 
}//end while loop 

thread.sleep(60);//in bathroom taking care of business! 

wait(mutex); 
womenIn--; 
cout << "A woman left the restoom." << endl; 
wait(waiting); 
if(menWaiting > womenWtg) 
{ 
    turn = 0; //men should get in at next opportunity 
    cout << "It's mens' turn!" << endl; 
} 
else if (menWaiting == womenWtg == 0) 
{ 
    turn = -1; //anybody should be able to get in 
} 
signal(waiting); 
signal(mutex); 

「Man」線程的行爲應該類似。請記住,等待和互斥信號量可以保護男性和女性的變量。


在男人/女人「退出」浴室之前,您正在發出互信號。如果我理解正確,互斥是這樣的,任何時候只有一個性別在浴室裏。既然你在輸出「男人已經離開浴室」之前發出信號,那麼女人可以得到互斥並進入。

由於男人和女人最初都在等待兩個不同的信號燈,所以有些人會接受初始信號量。從那裏開始,看起來你已經獲得了互斥體(在男性和女性之間共享),然後在你進入之後釋放它,然後退出。也許你的意思是在這裏發出信號「男人」或「女人」的信號?

編輯:我想我的答案的要點是這樣的:互斥是男性和女性共享的。在你的代碼中,當一個人得到他們所說的互斥體時,你會減少他們正在等待的內容,然後釋放互斥體。更深入地思考最後一步。如果你在他們離開之前釋放互斥鎖,這裏有什麼可能?

編輯2(回覆您的評論):你的新代碼是什麼樣的(編輯你的原始文章)?

這將幫助我們將代碼抽象到邏輯上,然後我們可以嘗試正確地構建您的邏輯,並比較我們認爲正確的代碼是幹什麼的。

編輯3:好吧,看起來你越來越近了。這裏有一些事情要考慮(我沒有發佈完整的解決方案,因爲這是作業,我希望你學習!)

  • 什麼是互斥保護?
  • 什麼是男人/女人保護?
  • 什麼是restroomCount保護?
  • 什麼是maxCapacity保護?
  • 這些信號應該以什麼順序獲得 ?
  • ......即,其中信號量保護哪些其他信號量以及如何?

想想尤其是好好的,廁所計數信號......(提示:這可能比簡單地保護計數變量更重要的是它可能需要保護其他信號量的釋放...。)

編輯4:所以我終於意識到,你正試圖避免在這個問題上的飢餓(如下面的評論所示)。雖然你的作業與讀者/作者的問題非常相似,但避免任何線程類型的飢餓的額外約束使得難以實現。我個人不知道如何做到這一點,而不使用事件設置偏好(http://msdn.microsoft.com/en-us/library/dd492846.aspx),即使如此,也不能保證飢餓永遠不會發生,如果我正確理解關於此主題的維基百科(http://en.wikipedia.org/wiki/Readers-writers_problem#The_third_readers-writers_problem)文章是唯一的方法來做到這一點。

你被允許使用事件嗎?

我不得不道歉,因爲沒有完全維護這個額外的讀者/作家的不飢餓約束。希望別人能更好地幫助你。

+0

女人和男人的信號量應該用來表明下一個性別應該進入洗手間(以防止飢餓)。這個問題確實存在於互斥體中。我調整了這些代碼並確定了相互排斥,現在遇到了一個問題,一次只允許一個人進入洗手間。 – Jen 2010-10-03 16:15:55

+0

你的意思是「一次只讓一個人進廁所?」您的初始化代碼似乎只會將max_capacity信號量初始化爲1而不是4,並且如果4 ppl位於洗手間中,您只能等待該信號量。我認爲你可以嘗試將信號量初始化爲4,然後等待它。 – AndyG 2010-10-03 16:21:44

+0

我做到了這一點,現在我陷入了僵局。此外,我對互斥的違反似乎還沒有得到解決。在這個過程中,一個女人和一個男人進入洗手間。 – Jen 2010-10-03 16:27:51

2

我認爲你有太多的信號量。你的男人/女人信號量一次只能對一個人開門。考慮使用一些受互斥體保護的狀態變量(衛生間的當前性別,浴室中的人數),而不是那麼多不同的信號量。

您是否保持排隊順序或可以根據當前的廁所性別跳過?例如,如果你有女人,女人,女人,男人,女人,是第四名被允許跳過男人進入洗手間的女人,或者讓3名女人出口,那麼男人出入,那麼女人可以進入?這是一個比允許跳過更容易的問題。

2

是使用信號量的一個要求嗎?例如,在「C++」僞代碼,實現類似於:

首先讓我們創建一個狀態對象,各國之間的驗證轉換

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

讓我們也創造了一個全球性的參考函數目前的狀態和功能的基礎上

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

然後我們創建一個全球矢量持有美國未來的一些期望的狀態來更新當前狀態,並表示女人的功能線程試圖去洗手間

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 

,並用處理循環邏輯和初始化

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

此代碼應工作(ⅰ沒有測試它)的主要功能。我已經欺騙了一點,因爲我沒有刪除任何創建的臨時狀態,所以每個狀態都會一直存在,直到進程終止。正確的垃圾收集將需要一種稱爲危險指針管理的技術。請注意,我不使用任何互斥信號或鎖,我使用的唯一鎖定原語是CAS(address,old_value,new_value)(比較和交換)。這個原語自動比較一個指針(地址),如果它仍然包含(old_value),那麼它分配它new_value併成功,否則失敗。另外,你仍然需要一個std :: vector的全局鎖,用於存儲我沒有包含在代碼中的狀態(你也可以泄漏它們,但是我把它們存儲在某個地方,所以你可以認爲這些應該在你知道的時候被刪除在這些情況下GC如何工作)

由於我所有的中間狀態都是不可變的(lisp/clojure風格inmutabilitity),所以線程的爭用(因此,飢餓)大大提高。在你的例子中,狀態集合很小(只是一堆人),它不是太糟糕,我們不刪除使用的狀態。然而,即使我提到的問題,我認爲你會同意發生的事情的邏輯更加明確和可讀。

+0

你的isEmpty()方法是錯誤的。如果有人在洗手間,當前的實現將返回true。我想你想男人和女人<= 0('<'在那裏,因爲它可能發生,如果它沒有編碼。) – Woot4Moo 2010-10-07 15:26:04

+0

你是對的,我修好了。謝謝。我不擔心<在這種情況下,因爲可能的轉換不允許負面狀態(從空只有男人== 1或女人== 1可能會發生) – lurscher 2010-10-07 15:28:23

0

與問題
原代碼的問題是不是很OO。

浴室隊列的處理應該與隊列中的人的生成分開 - 如果至少在隊列填滿之後沒有運行單獨的線程。

假設男女基本上都是分開排隊的 - 不是以某種固定的順序混合在一起的,否則這個問題對於使用信號燈沒有任何意義。

問題並沒有描述當條件成熟時有多少人進入,男性廁所多於男性,你是否填充到4或直到男性隊列再次少於女性?

即使如此,所描述的問題(以及基於沒有線程的示例代碼)在我看來並不適用於信號量,主要問題是信號量不容易計數並且成功地等待改變計數。

我在這個問題上看到的有趣的事情是,在排隊長度接近相等的情況下效率低下,並且在禁止同一性別進入廁所之間進行交易,以及在廁所中剩餘人員離開相同數量之前進行交易性再次變得更大。讓我們面對它,這是男女皆宜的,所以它應該允許4人,不分性別;)

建議的解決方案
所以你需要使用一個信號,關於信號的有趣的事情是多種用途的記錄(不像互斥體),如果沒有空閒空間,那麼它可能會等待。然而,它並不區分那些等待的人,它只會說明有空間。

有1個信號燈,並認爲你應該檢查信號燈,當一個人進入隊列或有人離開浴室。

然後,你可以爲男性和女性分別設置1個「隊列」(從這個基本上算是一個計數)。這些隊列在進入方面並沒有真正相關或限制,所以與信號量無關。每個可以遵循一個無鎖定的提供者模式,但是你可能會發現使用一個互斥體更容易同步,這樣你就可以檢查隊列的大小並對它們進行操作。在下面我剛剛直接使用了count,而應該使用某種形式的InterlockedIncrement和InterlockedDecrement來防止在同一隊列中添加和刪除人員。

在粗糙,Bathroom.h

class Bathroom 
{ 
public: 
    Bathroom(void); 
    ~Bathroom(void); 

    AddMan(); 
    AddWoman(); 
    Run(); 
private: 
    StateChange(); 

    int m_Menwaiting; 
    int m_Womenwaiting; 
    semaphore max_capacity; 

    enum Users { 
     NOBODY , 
     WOMEN, 
     MEN 
    } m_inUseBy; 
}; 

Bathroom.cpp

Bathroom::Bathroom(void) 
    : m_Menwaiting(0) 
    , m_Womenwaiting(0) 
    , m_inUseBy(NOBODY) 
{ 
    initialsem(max_capacity,4); 
} 


Bathroom::~Bathroom(void) 
{ 
    freesem(max_capacity); 
} 

Bathroom::AddMan(){ 
    ++m_Menwaiting; 
    StateChange(); 
} 

Bathroom::AddWoman(){ 
    ++m_Womenwaiting; 
    StateChange(); 
} 

Bathroom::StateChange() { 

    // extra at a time 
    if(m_Menwaiting > m_Womenwaiting && inUseBy != WOMEN) { 
     if(wait(max_capacity,0 delay) != timeout) 
      m_Menwaiting--; 
    } 

    if(m_Womenwaiting > m_Menwaiting && inUseBy != MEN) { 
     if(wait(max_capacity,0 delay) != timeout) 
      m_Womenwaiting--; 
    } 

    // all available slots 
    if(m_Menwaiting > m_Womenwaiting && inUseBy != WOMEN) { 
     while(wait(max_capacity,0 delay) != timeout) 
      m_Menwaiting--; 
    } 

    if(m_Womenwaiting > m_Menwaiting && inUseBy != MEN) { 
     while(wait(max_capacity,0 delay) != timeout) 
      m_Womenwaiting--; 
    } 

} 

Bathroom::run(){ 
// people leaving bathroom simulated 
    while(1) { 
     Delay(); 
     signal(max_capacity); 
     StateChange(); 
    } 
} 

Program.cpp

Bathroom b1; 

addPeople() { 
    while(true) { 
    // randomly add people 
    Delay(); 
    b1.AddMen(); 
    b1.AddWomen(); 
    } 
} 

int main(){ 

    thread(addPeople); 

    b1.run(); 
}