【正文】 ******大學(xué)操作系統(tǒng)課程設(shè)計(jì)題目一：實(shí)現(xiàn)生產(chǎn)者消費(fèi)者問(wèn)題題目二：實(shí)現(xiàn)銀行家算法 指導(dǎo)老師: ****** 班 級(jí)： ******班 學(xué) 號(hào)： ****** 姓 名： ****** 2007年12月12日目 錄第一部分：實(shí)現(xiàn)生產(chǎn)者與消費(fèi)者問(wèn)題一、題目……………………………………………………………………………………………2課程設(shè)計(jì)目的…………………………………………………………………………………2課程設(shè)計(jì)要求…………………………………………………………………………………2二、設(shè)計(jì)內(nèi)容………………………………………………………………………………………2三、開發(fā)環(huán)境………………………………………………………………………………………3四、分析設(shè)計(jì)………………………………………………………………………………………3設(shè)計(jì)原理………………………………………………………………………………………3涉及的數(shù)據(jù)結(jié)構(gòu)………………………………………………………………………………5流程圖…………………………………………………………………………………………6五、運(yùn)行示例及結(jié)果分析…………………………………………………………………………8運(yùn)行示例………………………………………………………………………………………8運(yùn)行結(jié)果分析：………………………………………………………………………………9六、個(gè)人體會(huì)………………………………………………………………………………………9七、附錄（源程序）………………………………………………………………………………10第二部分：實(shí)現(xiàn)銀行家算法一、題目……………………………………………………………………………………………14課程設(shè)計(jì)目的…………………………………………………………………………………14二、設(shè)計(jì)內(nèi)容………………………………………………………………………………………14三、開發(fā)環(huán)境………………………………………………………………………………………14四、分析設(shè)計(jì)………………………………………………………………………………………14預(yù)備知識(shí)……………………………………………………………………………………14設(shè)計(jì)原理……………………………………………………………………………………17涉及的數(shù)據(jù)結(jié)構(gòu)……………………………………………………………………………18安全檢測(cè)……………………………………………………………………………………18流程圖………………………………………………………………………………………19五、運(yùn)行示例及結(jié)果分析…………………………………………………………………………19運(yùn)行示例……………………………………………………………………………………19運(yùn)行結(jié)果分析：……………………………………………………………………………20六、個(gè)人體會(huì)………………………………………………………………………………………21七、附錄（源程序）………………………………………………………………………………21參考文獻(xiàn)………………………………………………………………………………………29第一部分：實(shí)現(xiàn)生產(chǎn)者與消費(fèi)者問(wèn)題一、題目：實(shí)現(xiàn)生產(chǎn)者與消費(fèi)者問(wèn)題此問(wèn)題是經(jīng)典的進(jìn)程同步互斥問(wèn)題，問(wèn)題描述參見(jiàn)教材第36頁(yè)和第46頁(yè)，要求編程實(shí)現(xiàn)，生產(chǎn)者放入產(chǎn)品的和消費(fèi)者取走產(chǎn)品的速度可以調(diào)節(jié)。課程設(shè)計(jì)目的：在我們所學(xué)的《操作系統(tǒng)》這門課程中，關(guān)于經(jīng)典進(jìn)程的同步問(wèn)題進(jìn)行了一定的描述和探討，介紹了幾個(gè)經(jīng)典的算法，需要我們?cè)趯?shí)踐中學(xué)會(huì)熟練運(yùn)用。在生產(chǎn)者與消費(fèi)者問(wèn)題中，需要我們了解進(jìn)程同步的概念，理解信號(hào)量機(jī)制的原理，掌握運(yùn)用信號(hào)量解決進(jìn)程同步問(wèn)題的方法，進(jìn)而學(xué)會(huì)運(yùn)用進(jìn)程的同步與互斥解決生產(chǎn)者與消費(fèi)者的沖突問(wèn)題。課程設(shè)計(jì)要求：生產(chǎn)者與消費(fèi)者問(wèn)題可以算作是經(jīng)典進(jìn)程同步問(wèn)題的典型代表。該課程設(shè)計(jì)要求運(yùn)用基于單緩沖區(qū)和多緩沖區(qū)的生產(chǎn)者與消費(fèi)者問(wèn)題的多種實(shí)現(xiàn)機(jī)制,其中利用了數(shù)據(jù)結(jié)構(gòu)中的循環(huán)隊(duì)列和堆棧來(lái)模擬實(shí)現(xiàn)是一種比較容易實(shí)現(xiàn)的方法。這種思想能夠幫助我們更好的理解所學(xué)內(nèi)容，并加以鍛煉我們的動(dòng)手實(shí)踐能力,實(shí)現(xiàn)它內(nèi)在具有的超強(qiáng)的參考價(jià)值和實(shí)踐意義。該課程設(shè)計(jì)通過(guò)了解進(jìn)程間的兩種制約關(guān)系，從而理解信號(hào)量機(jī)制；通過(guò)對(duì)實(shí)例的分析和討論，理解信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程的同步及互斥的方法；通過(guò)對(duì)經(jīng)典進(jìn)程同步問(wèn)題的剖析，初步掌握運(yùn)用信號(hào)量解決進(jìn)程同步問(wèn)題的方法。二、設(shè)計(jì)內(nèi)容在同一個(gè)進(jìn)程地址空間內(nèi)執(zhí)行的兩個(gè)線程。生產(chǎn)者線程生產(chǎn)物品，然后將物品放置在一個(gè)空緩沖區(qū)中供消費(fèi)者線程消費(fèi)。消費(fèi)者線程從緩沖區(qū)中獲得物品，然后釋放緩沖區(qū)。當(dāng)生產(chǎn)者線程生產(chǎn)物品時(shí)，如果沒(méi)有空緩沖區(qū)可用，那么生產(chǎn)者線程必須等待消費(fèi)者線程釋放出一個(gè)空緩沖區(qū)。當(dāng)消費(fèi)者線程消費(fèi)物品時(shí)，如果沒(méi)有滿的緩沖區(qū)，那么消費(fèi)者線程將被阻塞，直到新的物品被生產(chǎn)出來(lái)，我的具體做法也是如此，建立緩沖區(qū)，生產(chǎn)者生產(chǎn)的產(chǎn)品放入，消費(fèi)者從中取產(chǎn)品，如果沒(méi)有產(chǎn)品，則等待。三、開發(fā)環(huán)境此程序的設(shè)計(jì)在Windows XP操作系統(tǒng)下,基于Microsoft Visual C++。用C語(yǔ)言實(shí)現(xiàn)編程。四、分析設(shè)計(jì)設(shè)計(jì)原理進(jìn)程同步是指幾個(gè)進(jìn)程相互合作，一個(gè)進(jìn)程到達(dá)某個(gè)點(diǎn)后，除非另一個(gè)進(jìn)程已經(jīng)完成某些操作，否則就不得不停下來(lái)，等待這些操作的結(jié)束，這就是進(jìn)程同步的概念。生產(chǎn)者消費(fèi)者問(wèn)題是一個(gè)經(jīng)典的進(jìn)程同步問(wèn)題，該問(wèn)題最早由Dijkstra提出，用以演示他提出的信號(hào)量機(jī)制。本作業(yè)要求設(shè)計(jì)在同一個(gè)進(jìn)程地址空間內(nèi)執(zhí)行的兩個(gè)線程。生產(chǎn)者線程生產(chǎn)物品，然后將物品放置在一個(gè)空緩沖區(qū)中供消費(fèi)者線程消費(fèi)。消費(fèi)者線程從緩沖區(qū)中獲得物品，然后釋放緩沖區(qū)。當(dāng)生產(chǎn)者線程生產(chǎn)物品時(shí)，如果沒(méi)有空緩沖區(qū)可用，那么生產(chǎn)者線程必須等待消費(fèi)者線程釋放出一個(gè)空緩沖區(qū)。當(dāng)消費(fèi)者線程消費(fèi)物品時(shí)，如果沒(méi)有滿的緩沖區(qū)，那么消費(fèi)者線程將被阻塞，直到新的物品被生產(chǎn)出來(lái)。生產(chǎn)者—消費(fèi)者問(wèn)題是一種同步問(wèn)題的抽象描述。計(jì)算機(jī)系統(tǒng)中的每個(gè)進(jìn)程都可以消費(fèi)或生產(chǎn)某類資源，當(dāng)系統(tǒng)中某一進(jìn)程使用某一資源時(shí)，可以看作是消耗，且該進(jìn)程稱為消費(fèi)者。而當(dāng)某個(gè)進(jìn)程釋放資源時(shí)，則它就相當(dāng)一個(gè)生產(chǎn)者。 通過(guò)一個(gè)有界緩沖區(qū)把生產(chǎn)者和消費(fèi)者聯(lián)系起來(lái)。假定生產(chǎn)者和消費(fèi)者是相互等效的，只要緩沖區(qū)未滿，生產(chǎn)者就可以將產(chǎn)品送入緩沖區(qū)，類似地，只要緩沖區(qū)未空，消費(fèi)者就可以從緩沖區(qū)中去走物品并消費(fèi)它。生產(chǎn)者和消費(fèi)者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖區(qū)輸送產(chǎn)品，也禁止消費(fèi)者從空的緩沖區(qū)中提取物品。 在生產(chǎn)者—消費(fèi)者問(wèn)題中，信號(hào)燈具有兩種功能。首先，它是跟蹤資源的生產(chǎn)和消費(fèi)的計(jì)數(shù)器；其次，它是協(xié)調(diào)資源的生產(chǎn)者和消費(fèi)者之間的同步器。消費(fèi)者通過(guò)再一指派給它的信號(hào)燈上做P操作來(lái)表示消耗資源，而生產(chǎn)者通過(guò)在同一信號(hào)燈上做V操作來(lái)表示生產(chǎn)資源。再這種信號(hào)燈的實(shí)施中，計(jì)數(shù)在每次P操作后減1，而在每次V操作中加1。個(gè)這一計(jì)數(shù)器的初始值是可利用的資源數(shù)目。當(dāng)資源是不可利用時(shí)，將申請(qǐng)資源的進(jìn)程放置在等待隊(duì)列中。如果有一個(gè)資源釋放，在等待隊(duì)列中的第一個(gè)進(jìn)程被喚醒并得到資源的控制權(quán)。 為解決這一類生產(chǎn)者——消費(fèi)者問(wèn)題，設(shè)置了兩個(gè)同步信號(hào)燈，一個(gè)說(shuō)明空緩沖區(qū)的數(shù)目，用empty表示，其初值為有界緩沖區(qū)的大小n，另一個(gè)說(shuō)明緩沖區(qū)的數(shù)目，用full表示，其初制值為0。由于有界緩沖區(qū)是一個(gè)零界資源，必須互斥使用，所以另外還需設(shè)置一個(gè)互斥信號(hào)燈mutex,起初值為1。 假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖區(qū)中，具有n個(gè)緩沖區(qū)，這時(shí)可以利用互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用；利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者互相等效果，只要緩沖池未滿，生產(chǎn)者便可以將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可以從緩沖池中取走一個(gè)消息。在生產(chǎn)者消費(fèi)者問(wèn)題中應(yīng)注意：首先，在每個(gè)程序中用于互斥的wait(mutex)和signal(mutex)必須成對(duì)出現(xiàn)；其次，對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。生產(chǎn)者與消費(fèi)者進(jìn)程共享一個(gè)大小固定的緩沖區(qū)。其中，一個(gè)或多個(gè)生產(chǎn)者生產(chǎn)數(shù)據(jù)，并將生產(chǎn)的數(shù)據(jù)存入緩沖區(qū)，并有一個(gè)或多個(gè)消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)。假設(shè)緩沖區(qū)的大小為n（存儲(chǔ)單元的個(gè)數(shù)），它可以被生產(chǎn)者和消費(fèi)者循環(huán)使用。分別設(shè)置兩個(gè)指針in和out，指向生產(chǎn)者將存放數(shù)據(jù)的存儲(chǔ)單元和消費(fèi)者將取出數(shù)據(jù)的存儲(chǔ)單元，如圖，指針in和out初始化指向緩沖區(qū)的第一個(gè)存儲(chǔ)單元。生產(chǎn)者從第一個(gè)存儲(chǔ)單元開始存放數(shù)據(jù)，一次存放一條數(shù)據(jù)一條數(shù)據(jù)且in指針向后移一個(gè)位置，當(dāng)in 指針指向第n個(gè)存儲(chǔ)單元，下一次將指向第一個(gè)存儲(chǔ)單元，如此循環(huán)反復(fù)使用緩沖區(qū)。消費(fèi)者從緩沖區(qū)中逐條取走數(shù)據(jù)，一次取一條數(shù)據(jù)，相應(yīng)的存儲(chǔ)單元變?yōu)椤翱铡?，可以被生產(chǎn)者再次使用。每次取走一條數(shù)據(jù)，out指針向后移一個(gè)存儲(chǔ)單元位置。試想，如果不控制生產(chǎn)者與消費(fèi)者，將會(huì)產(chǎn)生什么結(jié)果？ 1 2 3 4 5 6 7 8 n ………… In out 1 2 3 4 5 6 7 8 n ………… In out 其中，in表示存