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

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

2、要解決兩個(gè)問題：1正確設(shè)置信號(hào)量，2恰當(dāng)安排PV原語的使用順序。1信號(hào)量有無要理發(fā)的顧客，m=0；進(jìn)入等待室的顧客的理發(fā)權(quán)，s=1；等待室中空椅子數(shù)量count=N及檢查時(shí)的使用權(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ā)的顧客，則睡覺。叫入一位顧客進(jìn)入理發(fā)室；v(s)理發(fā)3競(jìng)爭(zhēng)合作關(guān)系互斥競(jìng)爭(zhēng)關(guān)系：1顧客之間要競(jìng)爭(zhēng)N把空椅子count，同時(shí)要競(jìng)爭(zhēng)計(jì)數(shù)檢查時(shí)的使用權(quán)t；2表面看是競(jìng)爭(zhēng)N把空椅子，其實(shí)count也起到了同步作用，即限制可以等待的顧客的數(shù)量，最多N個(gè)；3進(jìn)入等待室的顧客要競(jìng)爭(zhēng)理發(fā)權(quán)s，起到了先來后到的作用。合作同步關(guān)系：1顧客向理發(fā)師發(fā)出一個(gè)新的理發(fā)請(qǐng)求，理發(fā)師要查看有無要理發(fā)的顧客；2每叫入一位顧客到理發(fā)室，

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