操作系統(tǒng)補充內(nèi)容-經(jīng)典同步問題

1、（嗜睡的理發(fā)師問題，由圖靈獎獲得者（嗜睡的理發(fā)師問題，由圖靈獎獲得者Dijkstra教授提出。教授提出。）一個理發(fā)店由一個有幾張椅子的等待室和一個放有一張理發(fā)椅子的理發(fā)室組成。若沒有要理發(fā)的顧客，則理發(fā)師就睡覺。一個顧客走進理發(fā)店，若發(fā)現(xiàn)所有椅子都被等待理發(fā)的顧客占用，則該顧客就離開理發(fā)店；若理發(fā)師正在理發(fā)并且有空椅子，則該顧客就找一個空椅子坐下來等待；若理發(fā)師在睡覺，則顧客便喚醒他。請設(shè)計理發(fā)師和顧客的同步算法。分析：對于互斥同步，主

2、要解決兩個問題：1正確設(shè)置信號量，2恰當安排PV原語的使用順序。1信號量有無要理發(fā)的顧客，m=0；進入等待室的顧客的理發(fā)權(quán)，s=1；等待室中空椅子數(shù)量count=N及檢查時的使用權(quán)t=1。2同步算法顧客：p(t)ifcount=0thenv(t)exit若無空椅子，則退出理發(fā)店；count–1坐在一張空椅子上；v(t)v(m)有要理發(fā)的顧客；p(s)現(xiàn)在能否理發(fā)，若不能則等待；被叫入理發(fā)室；p(t)count1騰出一張空椅子；v(t)理

3、發(fā)；理發(fā)師：p(m)若沒有要理發(fā)的顧客，則睡覺。叫入一位顧客進入理發(fā)室；v(s)理發(fā)3競爭合作關(guān)系互斥競爭關(guān)系：1顧客之間要競爭N把空椅子count，同時要競爭計數(shù)檢查時的使用權(quán)t；2表面看是競爭N把空椅子，其實count也起到了同步作用，即限制可以等待的顧客的數(shù)量，最多N個；3進入等待室的顧客要競爭理發(fā)權(quán)s，起到了先來后到的作用。合作同步關(guān)系：1顧客向理發(fā)師發(fā)出一個新的理發(fā)請求，理發(fā)師要查看有無要理發(fā)的顧客；2每叫入一位顧客到理發(fā)室，

4、也表示將理發(fā)權(quán)傳遞給下一位等待的顧客。請同學(xué)們也考慮有無其他方案，說明理由，不同教材中也有不同描述。p(s)從排隊隊列queue中取下一個服務(wù)號；v(s)為該號顧客提供服務(wù)；注：這里也存在不足嗎，請考慮。這些同步問題中需要處理的是競爭和合作關(guān)系，既有競爭又有合作，競爭的一般是公有資源，合作的一般是同步信號，即時序關(guān)系，有的簡單一些，有的復(fù)雜一些，我們這里提供的是使用一般信號量機制來解決，也有需要信號量集機制進行解決的問題，比如哲學(xué)家就餐