操作系統(tǒng)課程設(shè)計(jì)管程的實(shí)現(xiàn)（生產(chǎn)者消費(fèi)者問(wèn)題）

1、操作系統(tǒng)課程設(shè)計(jì)2、管程的實(shí)現(xiàn)（生產(chǎn)者消費(fèi)者問(wèn)題） 1.設(shè)計(jì)背景： 管程是一種高級(jí)抽象數(shù)據(jù)類(lèi)型，它支持在它的函數(shù)中隱含互斥操作。結(jié)合條件變量和其他一些低級(jí)通信原語(yǔ)，管程可以解決許多僅用低級(jí)原語(yǔ)不能解決的同步問(wèn)題。例如，本實(shí)驗(yàn)中利用管程提供一個(gè)不會(huì)發(fā)生死鎖的生產(chǎn)者消費(fèi)者問(wèn)題就是利用管程的很好的例子。 管程封裝了并發(fā)進(jìn)程或線程要互斥執(zhí)行的函數(shù)。為了讓這些并發(fā)進(jìn)程或線程在管程內(nèi)互斥的執(zhí)行，管程的實(shí)現(xiàn)必須隱含的具有鎖或二值信號(hào)量。 如果沒(méi)有條件變量，管程就不會(huì)有很有用，條件變量提供了一種對(duì)管程內(nèi)并發(fā)協(xié)作進(jìn)程的同步機(jī)制。條件變量代表了管程中一些并發(fā)進(jìn)程或線程可能要等待的條件。一個(gè)條件變量管理著管程內(nèi)的一

2、個(gè)等待隊(duì)列。如果管程內(nèi)某個(gè)進(jìn)程或線程發(fā)現(xiàn)其執(zhí)行條件為假，則該進(jìn)程或線程就會(huì)被條件變量掛入管程內(nèi)等待該條件的隊(duì)列。如果管程內(nèi)另外的進(jìn)程或線程滿足了這個(gè)條件，則它會(huì)通過(guò)條件變量再次喚醒等待該條件的進(jìn)程或線程，從而避免了死鎖的產(chǎn)生。所以，一個(gè)條件變量c應(yīng)具有兩種操作c.wait()和c.signal()。 當(dāng)管程內(nèi)同時(shí)出現(xiàn)喚醒者和被喚醒者時(shí)，由于要求管程內(nèi)的進(jìn)程或線程必須互斥執(zhí)行，因此就出現(xiàn)了兩種樣式的條件變量：mesa style(signal-and-continue):喚醒者進(jìn)程或線程繼續(xù)執(zhí)行，被喚醒者進(jìn)程或線程等到喚醒者進(jìn)程或線程阻塞或離開(kāi)管程后再執(zhí)行。hoare style(signal-

3、and-wait):被喚醒者進(jìn)程或線程立即執(zhí)行，喚醒者進(jìn)程或線程阻塞，直道被喚醒者阻塞或離開(kāi)管程后再執(zhí)行。我們實(shí)驗(yàn)所做的就是在原來(lái)mesa樣式的基礎(chǔ)上進(jìn)行hoare樣式的改進(jìn);這種樣式也是我們實(shí)驗(yàn)中需要實(shí)現(xiàn)的樣式。2.設(shè)計(jì)目標(biāo)驗(yàn)證并分析nachos中bridge管程是否能夠正確的解決單行橋雙向過(guò)橋問(wèn)題。n 定義和實(shí)現(xiàn)hoare樣式的條件變量condition_h類(lèi)n 利用hoare樣式的條件變量condition_h,實(shí)現(xiàn)ring類(lèi)中定義的各個(gè)方法,使用ring管程解決生產(chǎn)者/消費(fèi)者問(wèn)題。利用ring對(duì)象的put操作和get操作代替信號(hào)量來(lái)完成同步操作。這樣就避免了由于不恰當(dāng)?shù)氖褂眯盘?hào)量而引起

4、的死鎖和饑餓問(wèn)題。n 利用hoare樣式的條件變量condition_h,實(shí)現(xiàn)dp管程中定義的各個(gè)方法,使用ring管程解決哲學(xué)家就餐問(wèn)題。避免了由于不恰當(dāng)?shù)氖褂眯盘?hào)量而引起的死鎖和饑餓問(wèn)題。3.設(shè)計(jì)環(huán)境我們將使用以下的環(huán)境和資料學(xué)習(xí)和實(shí)驗(yàn)nachos系統(tǒng)，展開(kāi)我們的操作系統(tǒng)設(shè)計(jì)。0 1.實(shí)驗(yàn)環(huán)境為linux操作系統(tǒng)。1 2.nachos-3.4版系統(tǒng)源代碼電子文檔及相關(guān)編譯軟件gcc-2.8.1-mips。2 3.study book ：講授nachos系統(tǒng)的原理和實(shí)現(xiàn)的教材。3 4.introductory book：講授nachos系統(tǒng)的實(shí)驗(yàn)方法、實(shí)驗(yàn)步驟、實(shí)驗(yàn)要求的實(shí)驗(yàn)指導(dǎo)書(shū)。4.設(shè)計(jì)

5、說(shuō)明1.hoare樣式條件變量設(shè)計(jì)算法說(shuō)明：對(duì)于hoare樣式管程，相比于mesa樣式新增了一個(gè)喚醒者等待隊(duì)列。在hoare樣式中，喚醒者喚醒被喚醒者后，被喚醒者加入到readytorun隊(duì)列中，將被喚醒者加入到喚醒者等待隊(duì)列中，被喚醒者阻塞或者離開(kāi)時(shí)會(huì)喚醒喚醒者等待隊(duì)列中的一個(gè)喚醒。這樣我們需要一個(gè)新的條件變量，重寫(xiě)它的wait（）和signal（）方法來(lái)實(shí)現(xiàn)hoare樣式管程。設(shè)計(jì)內(nèi)容和步驟：在synch.h文件中定義一個(gè)新的結(jié)構(gòu)體condition_h。結(jié)構(gòu)體condition_h中包含的私有變量有char* name（條件變量名稱(chēng)）、list* queue（等待在該條件變量的線程）、l

6、ock* lock（管程鎖，條件變量共享）、semaphore *next（指向喚醒者等待隊(duì)列，條件變量共享）、int *nextcount（記錄喚醒者等待隊(duì)列中線程數(shù)量，條件變量共享）；方法有char* getname()、void wait(lock *conditionlock)、void signal(lock *conditionlock)。在synch.cc文件中定義結(jié)構(gòu)體condition_h中方法的具體實(shí)現(xiàn)。在方法 condition_h:wait (lock *conditionlock) 中，首先判斷隊(duì)列是否為空，是則把傳入的鎖賦給條件變量的鎖。調(diào)用條件變量的等待隊(duì)列que

7、ue的append(currentthread)方法，把當(dāng)前線程放入等待隊(duì)列中當(dāng)前線程釋放鎖。如果喚醒這等待隊(duì)列中有線程，則喚醒一個(gè)線程，即把它加入readytorun隊(duì)列中，調(diào)用了條件變量next的v方法。當(dāng)前線程sleep，放棄資源，在readytorun隊(duì)列中選取下一個(gè)執(zhí)行的線程，該線程申請(qǐng)鎖。在方法void condition_h:signa l(lock *conditionlock)中，如果條件變量的等待隊(duì)列queue非空則從中移除一個(gè)線程，并把該線程放入readytorun等待隊(duì)列中。當(dāng)前線程釋放鎖，并把當(dāng)前線程加入喚醒這等待隊(duì)列中，調(diào)用了條件變量next的p方法。在readyt

8、orun隊(duì)列中選取下一個(gè)執(zhí)行的線程，該線程申請(qǐng)鎖。如果隊(duì)列為空，則不做。實(shí)驗(yàn)收獲：1.需要注意的一點(diǎn)是，喚醒者等待隊(duì)列是屬于管程的2.一個(gè)常用的規(guī)則是，在.h頭文件中聲明方法頭，然后在.cc中將具體的方法實(shí)現(xiàn)，這是老師上課強(qiáng)調(diào)的一點(diǎn)，在試驗(yàn)中應(yīng)實(shí)踐好。3.實(shí)驗(yàn)受到了張洪烈老師的鼓勵(lì)與幫助，在此表示感謝。實(shí)驗(yàn)過(guò)程中，具體實(shí)現(xiàn)的每一個(gè)思想都會(huì)遇到很多問(wèn)題，有的時(shí)候可能只是一個(gè)未知的知識(shí)點(diǎn)的忽略，受到老師點(diǎn)撥之后問(wèn)題往往可以迎刃而解。運(yùn)行結(jié)果分析：（無(wú)）2.消費(fèi)者生產(chǎn)者管程設(shè)計(jì)算法說(shuō)明：生產(chǎn)者消費(fèi)者問(wèn)題是一個(gè)著名的進(jìn)程同步問(wèn)題。它描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將此產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)

9、。為使生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在它們之間設(shè)置有個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程可將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中，消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)取得一個(gè)產(chǎn)品消費(fèi)。使用管程的思想解決這個(gè)問(wèn)題，我們需要使用兩個(gè)條件變量和一個(gè)管程鎖，一個(gè)喚醒者等待隊(duì)列以及一系列控制的參數(shù)。方法包括void put(slot *message); void get(slot *message);int full()；int empty(); void enter();void exit();設(shè)計(jì)內(nèi)容和步驟： slot結(jié)構(gòu)體的實(shí)現(xiàn)。slot結(jié)構(gòu)體用于存儲(chǔ)生產(chǎn)者存放和消費(fèi)者所取的數(shù)據(jù)。包括兩個(gè)實(shí)例變量： thread_i

10、d和 value（int類(lèi)型）。ring結(jié)構(gòu)體的實(shí)現(xiàn)。ring結(jié)構(gòu)體即生產(chǎn)者消費(fèi)者問(wèn)題的管程類(lèi)。包括的實(shí)例變量有： int size; /緩沖區(qū)大小 int in, out; /存放和取數(shù)據(jù)的位置記錄 slot *buffer; /緩沖區(qū)（環(huán)形） condition_h *notfull; /條件變量 condition_h *notempty; /條件變量 lock *mutexlock; /管程鎖 semaphore *next; /喚醒這等待隊(duì)列包括的方法有： void put(slot *message); /生產(chǎn)者放數(shù)據(jù)void get(slot *message);/消費(fèi)者取數(shù)據(jù)i

11、nt full(); /緩沖區(qū)是否滿int empty(); /緩沖區(qū)是否空void enter(); /進(jìn)入管程void exit(); /出管程ring結(jié)構(gòu)體中方法的具體實(shí)現(xiàn)。 void put(slot *message);判斷緩沖區(qū)是否為滿，滿則生產(chǎn)者在在notfull條件變量上等待；不滿則放入數(shù)據(jù)，修改變量in的值，在notempty條件變量上喚醒一個(gè)消費(fèi)者。void get(slot *message); 判斷緩沖區(qū)是否為空，空則消費(fèi)者在條件變量notempty上等待；不空則取出一個(gè)數(shù)據(jù)，修改變量out的值，在條件變量notfull上喚醒一個(gè)生產(chǎn)者。void enter();進(jìn)程獲

12、取鎖，進(jìn)入管程，mutexlock-acquire()。void exit();進(jìn)程釋放鎖，出管程，mutexlock -release()。使用管程解決生產(chǎn)者消費(fèi)者問(wèn)題。首先生成ring變量，聲明緩沖區(qū)大小，生產(chǎn)者消費(fèi)者數(shù)量。為每一個(gè)生產(chǎn)者創(chuàng)建線程，設(shè)置優(yōu)先級(jí)，運(yùn)行producer（）方法。為每一個(gè)消費(fèi)者創(chuàng)建線程，設(shè)置優(yōu)先級(jí)，運(yùn)行consumer（）方法。 producer(_int which)設(shè)置一個(gè)循環(huán)體，循環(huán)次數(shù)是生產(chǎn)者生產(chǎn)產(chǎn)品的數(shù)量，每次生產(chǎn)一個(gè)產(chǎn)品。封裝程slot類(lèi)型變量message，調(diào)用管程ring的方法，分別是 ring-enter(); ring-put(message)

13、; ring-exit();get(slot *message); 設(shè)置一個(gè)循環(huán)體，循環(huán)次數(shù)是消費(fèi)者消費(fèi)產(chǎn)品的數(shù)量，每次生消費(fèi)一個(gè)產(chǎn)品。新建slot類(lèi)型變量message，調(diào)用管程ring的方法，分別是 ring-enter(); ring- get(message); ring-exit();實(shí)驗(yàn)收獲：1.需要注意的一點(diǎn)是，喚醒者等待隊(duì)列是屬于管程的2.增強(qiáng)了對(duì)進(jìn)程同步與互斥問(wèn)題的實(shí)際編程、調(diào)試和分析問(wèn)題的能力。4.調(diào)試及運(yùn)行1、在終端里進(jìn)入到threads的文件夾目錄，在終端里面輸入make命令，執(zhí)行編譯和鏈接2、輸入./nachos 運(yùn)行程序，運(yùn)行的一次結(jié)果為:ckpckp-lenovo

14、-3000-g430:/桌面/nachos-3.4_2_1/code/threads$ ./nachosthread: 生產(chǎn)者a is run生產(chǎn)者a 開(kāi)始執(zhí)行生產(chǎn)者a 進(jìn)入管程生產(chǎn)者a apply mutex 生產(chǎn)者a get mutex 生產(chǎn)者a 生產(chǎn)一個(gè)產(chǎn)品， 當(dāng)前產(chǎn)品個(gè)數(shù)： 1， 放入一個(gè)： 0 生產(chǎn)者a release mutex 生產(chǎn)者a 退出生產(chǎn)者a 進(jìn)入管程生產(chǎn)者a apply mutex 生產(chǎn)者a get mutex thread: 生產(chǎn)者b is run生產(chǎn)者b 開(kāi)始執(zhí)行生產(chǎn)者b 進(jìn)入管程生產(chǎn)者b apply mutex 生產(chǎn)者b sleepthread: 消費(fèi)者a is

15、run消費(fèi)者a 開(kāi)始執(zhí)行消費(fèi)者a 進(jìn)入消費(fèi)者a apply mutex 消費(fèi)者a sleepthread: 消費(fèi)者b is run消費(fèi)者b 開(kāi)始執(zhí)行消費(fèi)者b 進(jìn)入消費(fèi)者b apply mutex 消費(fèi)者b sleepthread: 生產(chǎn)者a is run生產(chǎn)者a 生產(chǎn)一個(gè)產(chǎn)品， 當(dāng)前產(chǎn)品個(gè)數(shù)： 2， 放入一個(gè)： 0 生產(chǎn)者a release mutex wake 生產(chǎn)者b from q生產(chǎn)者a 退出生產(chǎn)者a 進(jìn)入管程生產(chǎn)者a apply mutex 生產(chǎn)者a get mutex 生產(chǎn)者a 生產(chǎn)一個(gè)產(chǎn)品， 當(dāng)前產(chǎn)品個(gè)數(shù)： 3， 放入一個(gè)： 0 生產(chǎn)者a release mutex wake 消費(fèi)

16、者a from q生產(chǎn)者a 退出生產(chǎn)者a 進(jìn)入管程生產(chǎn)者a apply mutex 生產(chǎn)者a get mutex thread: 生產(chǎn)者b is run生產(chǎn)者b sleepthread: 消費(fèi)者a is run消費(fèi)者a sleepthread: 生產(chǎn)者a is run生產(chǎn)者a 生產(chǎn)一個(gè)產(chǎn)品， 當(dāng)前產(chǎn)品個(gè)數(shù)： 4， 放入一個(gè)： 0 生產(chǎn)者a release mutex wake 消費(fèi)者b from q生產(chǎn)者a 退出生產(chǎn)者a 進(jìn)入管程生產(chǎn)者a apply mutex 生產(chǎn)者a get mutex 緩沖區(qū)滿!生產(chǎn)者a - waitq生產(chǎn)者a release mutex wake 生產(chǎn)者b from

17、qthread: 消費(fèi)者b is run消費(fèi)者b get mutex 消費(fèi)者b 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 1 產(chǎn)品 0 ;消費(fèi)者b wake up 生產(chǎn)者a消費(fèi)者b release mutex wake 消費(fèi)者a from q消費(fèi)者b 喚醒一個(gè)進(jìn)程消費(fèi)者b apply mutex 消費(fèi)者b sleepthread: 生產(chǎn)者b is run生產(chǎn)者b get mutex 生產(chǎn)者b 生產(chǎn)一個(gè)產(chǎn)品， 當(dāng)前產(chǎn)品個(gè)數(shù)： 1， 放入一個(gè)： 0 在等待隊(duì)列中喚醒一個(gè)進(jìn)程生產(chǎn)者b release mutex wake 消費(fèi)者b from qthread: 生產(chǎn)者a is run生產(chǎn)者a apply mutex

18、 生產(chǎn)者a sleepthread: 消費(fèi)者a is run消費(fèi)者a sleepthread: 消費(fèi)者b is run消費(fèi)者b get mutex 消費(fèi)者b apply mutex 消費(fèi)者b sleepthread: 生產(chǎn)者b is run生產(chǎn)者b release mutex wake 生產(chǎn)者a from q生產(chǎn)者b 退出生產(chǎn)者b 進(jìn)入管程生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex 緩沖區(qū)滿!生產(chǎn)者b - waitq生產(chǎn)者b release mutex wake 消費(fèi)者a from qthread: 生產(chǎn)者a is run生產(chǎn)者a get mutex 生產(chǎn)者a 生產(chǎn)一個(gè)產(chǎn)品

19、， 當(dāng)前產(chǎn)品個(gè)數(shù)： 5， 放入一個(gè)： 0 在等待隊(duì)列中喚醒一個(gè)進(jìn)程生產(chǎn)者a release mutex 生產(chǎn)者a release mutex wake 消費(fèi)者b from q生產(chǎn)者a 退出生產(chǎn)者a 執(zhí)行結(jié)束thread: 消費(fèi)者a is run消費(fèi)者a get mutex 消費(fèi)者a 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 5 產(chǎn)品 0 ;消費(fèi)者a wake up 生產(chǎn)者bthread: 消費(fèi)者b is run消費(fèi)者b sleepthread: 生產(chǎn)者b is run生產(chǎn)者b apply mutex 生產(chǎn)者b sleepthread: 消費(fèi)者a is run消費(fèi)者a release mutex wake 消

20、費(fèi)者b from q消費(fèi)者a 喚醒一個(gè)進(jìn)程消費(fèi)者a apply mutex 消費(fèi)者a get mutex 消費(fèi)者a apply mutex 消費(fèi)者a get mutex 喚醒一個(gè)進(jìn)程消費(fèi)者a release mutex 消費(fèi)者a release mutex wake 生產(chǎn)者b from q消費(fèi)者a 退出消費(fèi)者a 進(jìn)入消費(fèi)者a apply mutex 消費(fèi)者a get mutex 消費(fèi)者a 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 3 產(chǎn)品 0 ;喚醒一個(gè)進(jìn)程消費(fèi)者a release mutex 消費(fèi)者a release mutex thread: 消費(fèi)者b is run消費(fèi)者b get mutex 消費(fèi)者b

21、 release mutex 消費(fèi)者b 退出消費(fèi)者b 進(jìn)入消費(fèi)者b apply mutex 消費(fèi)者b get mutex 消費(fèi)者b 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 4 產(chǎn)品 0 ;消費(fèi)者b release mutex 消費(fèi)者b 退出消費(fèi)者b 進(jìn)入消費(fèi)者b apply mutex 消費(fèi)者b get mutex 消費(fèi)者b 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 1 產(chǎn)品 0 ;消費(fèi)者b release mutex 消費(fèi)者b 退出消費(fèi)者b 進(jìn)入消費(fèi)者b apply mutex 消費(fèi)者b get mutex 消費(fèi)者b 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 5 產(chǎn)品 0 ;thread: 生產(chǎn)者b is run生產(chǎn)者b slee

22、pthread: 消費(fèi)者a is run消費(fèi)者a 退出消費(fèi)者a 進(jìn)入消費(fèi)者a apply mutex 消費(fèi)者a sleepthread: 消費(fèi)者b is run消費(fèi)者b release mutex wake 生產(chǎn)者b from q消費(fèi)者b 退出消費(fèi)者b 進(jìn)入消費(fèi)者b apply mutex 消費(fèi)者b get mutex 緩沖區(qū)空!消費(fèi)者b - waitq消費(fèi)者b release mutex wake 消費(fèi)者a from qthread: 生產(chǎn)者b is run生產(chǎn)者b get mutex 生產(chǎn)者b 生產(chǎn)一個(gè)產(chǎn)品， 當(dāng)前產(chǎn)品個(gè)數(shù)： 2， 放入一個(gè)： 0 生產(chǎn)者b wake up 消費(fèi)者b生產(chǎn)者b

23、 release mutex 生產(chǎn)者b 喚醒一個(gè)進(jìn)程生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex 生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex 生產(chǎn)者b release mutex thread: 消費(fèi)者a is run消費(fèi)者a get mutex 消費(fèi)者a 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 2 產(chǎn)品 0 ;消費(fèi)者a release mutex 消費(fèi)者a 退出消費(fèi)者a 進(jìn)入消費(fèi)者a apply mutex 消費(fèi)者a get mutex 緩沖區(qū)空!消費(fèi)者a - waitq消費(fèi)者a release mutex thread: 消費(fèi)者b is run消費(fèi)者b apply

24、 mutex 消費(fèi)者b get mutex 消費(fèi)者b 得到一個(gè)產(chǎn)品 當(dāng)前產(chǎn)品個(gè)數(shù) 4 產(chǎn)品 0 ;消費(fèi)者b release mutex 消費(fèi)者b 退出消費(fèi)者b 執(zhí)行結(jié)束thread: 生產(chǎn)者b is run生產(chǎn)者b 退出生產(chǎn)者b 進(jìn)入管程生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex 生產(chǎn)者b 生產(chǎn)一個(gè)產(chǎn)品， 當(dāng)前產(chǎn)品個(gè)數(shù)： 3， 放入一個(gè)： 0 生產(chǎn)者b wake up 消費(fèi)者athread: 消費(fèi)者a is run消費(fèi)者a apply mutex 消費(fèi)者a sleepthread: 生產(chǎn)者b is run生產(chǎn)者b release mutex wake 消費(fèi)者a from q生產(chǎn)者b 喚醒一個(gè)進(jìn)程生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex 生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex 生產(chǎn)者b release mutex 生產(chǎn)者b 退出生產(chǎn)者b 進(jìn)入管程生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex