用銀行家算法實(shí)現(xiàn)資源分配課程設(shè)計

1、.實(shí)驗(yàn)一: 資源分配仿真 (8學(xué)時)一、 實(shí)驗(yàn)內(nèi)容模擬資源分配算法，了解死鎖的產(chǎn)生和預(yù)防方法。二、 實(shí)驗(yàn)?zāi)康脑谡n程已經(jīng)學(xué)習(xí)了死鎖的4個必要條件的基礎(chǔ)上，為了了解系統(tǒng)的資源分配情況，假定系統(tǒng)中任一資源在每一時刻只能由一個進(jìn)程使用，任何進(jìn)程不能搶占其它進(jìn)程正在占有的資源，當(dāng)進(jìn)程得不到資源時，必須等待。因此，只要資源分配策略能保證不出現(xiàn)循環(huán)等待，系統(tǒng)就不會發(fā)生死鎖。要求學(xué)生編寫和調(diào)試系統(tǒng)動態(tài)分配資源的仿真程序，觀察死鎖產(chǎn)生的條件，再采用適當(dāng)?shù)乃惴?，有效地防止和避免死鎖發(fā)生。三、 實(shí)驗(yàn)題目用銀行家算法實(shí)現(xiàn)資源分配要求：1、 設(shè)計34個并發(fā)進(jìn)程共享10個同類資源的系統(tǒng)，各進(jìn)程動態(tài)地申請和釋放資源；2、

2、用銀行家算法和隨機(jī)分配算法分別設(shè)計資源分配程序，觀察系統(tǒng)的運(yùn)行情況；3、 確定一組進(jìn)程依次申請的資源數(shù)序列，運(yùn)行上述程序，顯示各進(jìn)程依次申請的資源情況。提示：1、 銀行家分配算法的原則是：系統(tǒng)掌握每個進(jìn)程對資源的最大需求量，當(dāng)進(jìn)程要求申請資源時，系統(tǒng)就測試該進(jìn)程還需要資源的最大量。如果系統(tǒng)中現(xiàn)存的資源數(shù)大于或等于該進(jìn)程還需要的最大量時，則滿足進(jìn)程的當(dāng)前申請。這樣可以保證至少有一個進(jìn)程能得到全部資源而執(zhí)行到結(jié)束。然后歸還它占用的全部資源，供其它進(jìn)程使用。銀行家算法破壞了產(chǎn)生死鎖的環(huán)路等待條件，即不可能產(chǎn)生循環(huán)等待，從而可以避免死鎖的發(fā)生。2、 把各進(jìn)程需要和已占用資源的情況記錄在進(jìn)程控制塊中。假

3、定進(jìn)程控制塊PCB的格式如下：其中，狀態(tài)有：就緒、等待和完成。當(dāng)進(jìn)城處于等待態(tài)時，表示系統(tǒng)不能滿足進(jìn)程的當(dāng)前申請?！百Y源需求量”表示進(jìn)程在執(zhí)行過程中總共要申請的資源量?！耙颜假Y源量”表示進(jìn)程目前已經(jīng)得到但還未歸還的資源量。因此，進(jìn)程在以后還需要的剩余資源量等于資源需要總量減去已占資源量。顯然每個進(jìn)程的資源需求總量不應(yīng)超過系統(tǒng)擁有的資源總量。3、 由于銀行家算法可以避免死鎖，為了觀察死鎖現(xiàn)象的發(fā)生，要求采用兩個算法：銀行家算法和隨機(jī)算法。隨機(jī)算法的分配原則是：當(dāng)進(jìn)程申請資源時，如果系統(tǒng)現(xiàn)存資源數(shù)能夠滿足進(jìn)程當(dāng)前申請量，就把資源分配給進(jìn)程；否則，讓其等待。這樣，隨機(jī)算法可能引起死鎖。資源分配仿真程

4、序的總流程見圖1：隨機(jī)分配算法流程圖見圖2：銀行家算法流程如圖3：四、 實(shí)驗(yàn)報告:1、程序中使用數(shù)據(jù)結(jié)構(gòu)和符號說明；2、給出程序流程；3、顯示程序運(yùn)行的初始狀態(tài)和運(yùn)行結(jié)果；4、附程序?qū)崿F(xiàn)的核心代碼（編程語言不限）；5、收獲體會及改進(jìn)意見。實(shí)驗(yàn)二: 可變分區(qū)主存空間的分配與回收仿真(8學(xué)時)一、 實(shí)驗(yàn)內(nèi)容仿真可變分區(qū)主存空間的分配與回收 二、 實(shí)驗(yàn)?zāi)康闹鞔嬷醒胩幚頇C(jī)能直接存取指令和數(shù)據(jù)的存儲器。能否合理而有效地使用它，在很大程度上將影響整個計算機(jī)系統(tǒng)的性能。本實(shí)驗(yàn)主要讓大家熟悉主存的分配與回收。所謂分配，就是解決多道作業(yè)如何共享主存空間的問題；當(dāng)作業(yè)運(yùn)行完成時，如何回收作業(yè)所占的主存空間。主存的

5、分配與回收的實(shí)現(xiàn)是與主存儲器的管理方式相關(guān)的。通過本實(shí)驗(yàn)，幫助學(xué)生理解在不同的存儲管理方式下如何實(shí)現(xiàn)主存空間的分配與回收。三、 實(shí)驗(yàn)題目采用可變式分區(qū)管理時，采用首次或最佳適應(yīng)算法實(shí)現(xiàn)主存的分配與回收。提示:1、 可變式分區(qū)管理是指在處理進(jìn)程的過程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的需要，并且分區(qū)的個數(shù)是可以調(diào)整的。當(dāng)要裝入一個進(jìn)程時，根據(jù)進(jìn)程需要的主存量，查看是否有足夠的空閑空間，若有，則按需求量分割一部分給進(jìn)程；若無，則進(jìn)行“緊湊”；否則，作業(yè)等待。隨著進(jìn)程的裝入、完成，主存空間被分割成許多大大小小的分區(qū)，有的分區(qū)被進(jìn)程占用，有的分區(qū)空閑。為了說明哪些分區(qū)是空閑，可以裝入新進(jìn)程，必須有一張

6、空閑區(qū)說明表或者空白存儲塊鏈（+2）其中：起始地址指出空閑區(qū)的主存起始地址 長度指出空閑區(qū)大小 狀態(tài)：未分配該欄目是有效空閑區(qū) 空表目沒有登記信息 由于分區(qū)個數(shù)補(bǔ)丁，所以空閑區(qū)說明表中應(yīng)有足夠的空表目項(xiàng)。否則造成溢出，無法登記。2、 當(dāng)有一個新進(jìn)程要求裝入主存時，必須查空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)的需求量，這時應(yīng)該將空閑區(qū)一分為二。一個分給進(jìn)程，另一個仍作為空閑區(qū)留在空閑區(qū)表中。為了盡量減少由于分割造成的碎片，盡可能分配低地址部分的空閑區(qū)，將較大空閑區(qū)留在高地址端，以利于大作業(yè)的裝入。為此在空閑區(qū)表中，按空閑區(qū)地址從高到低登記。為了方便查找，要不斷調(diào)整表格，讓“空表目”欄目留在表的后部。3、 當(dāng)一個進(jìn)程執(zhí)行完成時，進(jìn)程所占用的分區(qū)應(yīng)該歸還給系統(tǒng)。在歸還時要考慮相鄰空閑區(qū)合并的問題（使用邊界標(biāo)識法+2）。 4、 請按首次或最佳適應(yīng)算法設(shè)計主存的分配和回收程序，以提示1中給出的分區(qū)說明表作為當(dāng)前主存的初始值。學(xué)生自己仿真一個進(jìn)程的申請隊列及進(jìn)程完成后的釋放順序，實(shí)現(xiàn)主存的分配與回收。把空閑區(qū)說明表（空白塊鏈）的變化情況及各進(jìn)程的申請，釋放