操作系統(tǒng)課程設計管程的實現(xiàn)（生產(chǎn)者消費者問題）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、者a from q生產(chǎn)者a 退出生產(chǎn)者a 進入管程生產(chǎn)者a apply mutex 生產(chǎn)者a get mutex thread: 生產(chǎn)者b is run生產(chǎn)者b sleepthread: 消費者a is run消費者a sleepthread: 生產(chǎn)者a is run生產(chǎn)者a 生產(chǎn)一個產(chǎn)品， 當前產(chǎn)品個數(shù)： 4， 放入一個： 0 生產(chǎn)者a release mutex wake 消費者b from q生產(chǎn)者a 退出生產(chǎn)者a 進入管程生產(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: 消費者b is run消費者b get mutex 消費者b 得到一個產(chǎn)品 當前產(chǎn)品個數(shù) 1 產(chǎn)品 0 ;消費者b wake up 生產(chǎn)者a消費者b release mutex wake 消費者a from q消費者b 喚醒一個進程消費者b apply mutex 消費者b sleepthread: 生產(chǎn)者b is run生產(chǎn)者b get mutex 生產(chǎn)者b 生產(chǎn)一個產(chǎn)品， 當前產(chǎn)品個數(shù)： 1， 放入一個： 0 在等待隊列中喚醒一個進程生產(chǎn)者b release mutex wake 消費者b from qthread: 生產(chǎn)者a is run生產(chǎn)者a apply mutex

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

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

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

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

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

23、 release mutex 生產(chǎn)者b 喚醒一個進程生產(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: 消費者a is run消費者a get mutex 消費者a 得到一個產(chǎn)品 當前產(chǎn)品個數(shù) 2 產(chǎn)品 0 ;消費者a release mutex 消費者a 退出消費者a 進入消費者a apply mutex 消費者a get mutex 緩沖區(qū)空!消費者a - waitq消費者a release mutex thread: 消費者b is run消費者b apply

24、 mutex 消費者b get mutex 消費者b 得到一個產(chǎn)品 當前產(chǎn)品個數(shù) 4 產(chǎn)品 0 ;消費者b release mutex 消費者b 退出消費者b 執(zhí)行結束thread: 生產(chǎn)者b is run生產(chǎn)者b 退出生產(chǎn)者b 進入管程生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex 生產(chǎn)者b 生產(chǎn)一個產(chǎn)品， 當前產(chǎn)品個數(shù)： 3， 放入一個： 0 生產(chǎn)者b wake up 消費者athread: 消費者a is run消費者a apply mutex 消費者a sleepthread: 生產(chǎn)者b is run生產(chǎn)者b release mutex wake 消費者a from q生產(chǎn)者b 喚醒一個進程生產(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 進入管程生產(chǎn)者b apply mutex 生產(chǎn)者b get mutex