1、XX大學“操作系統(tǒng)課程設計讀書工程報告學院軟件學院年級2010級專業(yè)軟件工程學號報告日期2013/7/03成績XX大學計算機科學技術學院XX大學軟件學院一、根本理論闡述.死鎖的概念：系統(tǒng)中多個進程因素因競爭資源而產(chǎn)生的僵死狀態(tài)，假設無外力推動進程將無法繼續(xù)執(zhí)行。.死鎖的根本原因；對資源的競爭；進程推進的順序不當。3死鎖產(chǎn)生的必要條件互斥條件在某一段時間里，某資源被一個進程所占有，不能為別的進程使用；請求并保持不釋放進程每次申請它所需要的一局部資源。在等待新資源的同時，進程繼續(xù)占用已分配到的資源；非剝奪條件進程所獲得的資源在為使用完之前，不能被其他進程強行奪走，即只能由獲得該資源的進程自己來釋放

2、；環(huán)路條件存在一種進程資源的循環(huán)等待鏈，鏈中的每一個進程已獲得資源的同時被鏈中下一個進程所請求。.死鎖的預防破壞互斥條件。由于資源特性所限，一般情況下這個條件是無法摒棄的，但對于某些互斥共享的設備，如打印機，那么可以通過Spooling技術來摒棄互斥條件。破壞”請求與保持條件。可以采用資源靜態(tài)分配法，即對資源采用一次性分配策略，但會導致資源利用率的下降。破壞“非剝奪條件。可以采用剝奪策略，但涉及到對資源現(xiàn)場的恢復問題，需付出高昂代價。因此，一般只適用于處理機和存儲器資源，不適宜對其他資源使用該方法。破壞“環(huán)路等待條件。可以采用資源順序分配法，但實際情況是：資源編號增加的順序與實際使用資源的順序

3、不一致，從而可能導致提早分配資源而導致資源長期不用的現(xiàn)象，使資源利用律下降。通過精心分配資源，可以動態(tài)回避死鎖；即通過執(zhí)行一種算法，在分配過程中預測出死鎖發(fā)生的可能性并加以防止。死鎖防止算法的實質(zhì)是防止系統(tǒng)進入不平安狀態(tài)。常用的是銀行家算法。但執(zhí)行這種測試需要的開銷較大。.進程：是操作系統(tǒng)中最根本、最重要的概念，但直到目前還沒有一個統(tǒng)一的定義，下面通過能反映進程實質(zhì)的幾點描述來認識進程：進程是程序的一次執(zhí)行；進程是可以和別的計算并發(fā)執(zhí)行的計算；進程是程序在一個數(shù)據(jù)集合上運行的過程，是系統(tǒng)進展資源分配和調(diào)度的一個獨立單位；進程是一個具有一定功能的程序關于某個數(shù)據(jù)集合的一次運行活動。進程具有幾個根

4、本的特征：動態(tài)性、并發(fā)性、獨立性、異步性；每個進程通常由程序段、數(shù)據(jù)段和進程控制塊三局部組成，其中進程控制塊能唯一標識一個進程。進程執(zhí)行時間的連續(xù)性，決定了進程可能具有多種狀態(tài)。事實上，運行中的進程至少具有以下三種根本狀態(tài)：就緒狀態(tài)：進程已獲得除處理機以外的所有資源，一旦分到了處理機就可以立即執(zhí)行，這時進程所處的狀態(tài)為就緒狀態(tài)；執(zhí)行狀態(tài)：又稱運行狀態(tài)。當一個進程獲得必要的資源，并占有處理機，即在處理機上運行，此時進程所處的狀態(tài)為執(zhí)行狀態(tài)；阻塞狀態(tài)：又稱等待狀態(tài)，正在執(zhí)行的進程，由于發(fā)生了某事件而暫時無法執(zhí)行下去如等待輸入/輸出完成，此時進程所處的狀態(tài)稱為阻塞狀態(tài)。進程并非固定處于某一狀態(tài)，它隨

5、著自身的推進和外界條件的變化而發(fā)生變化。.銀行家算法：銀行家算法是一種有代表性的防止死鎖的算法。在防止死請資源，但系統(tǒng)在進展資源分配之前，應先計算此次分配資源的平安性，假設分配不會導致系統(tǒng)進入不平安狀態(tài)，那么分配，否那么等待。為實現(xiàn)銀行家算法，系統(tǒng)必須設置假設干數(shù)據(jù)構造。要解釋銀行家算法，必須先解釋操作系統(tǒng)平安狀態(tài)和不平安狀態(tài)。平安序列是指一個進程序列P1,Pn是平安的，即對于每一個進程Pi(ii0,na以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj(ji)當前占有資源量之和。.銀行家算法原理：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請

6、求分配資源相當于用戶向銀行家貸款。為保證資金的平安，銀行家規(guī)定：當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客；顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量；當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；當顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金。操作系統(tǒng)按照銀行家制定的規(guī)那么為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量那么按當前的申請量分配資源，否那么就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程本次申請的資源數(shù)是

7、否超過了該資源所剩余的總量。假設超過那么拒絕分配資源，假設能滿足那么按當前的申請量分配資源，否那么也要推遲分配。二、當前應用現(xiàn)狀操作系統(tǒng)是一管理電腦硬件與軟件資源的程序，同時也是計算機系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)身負諸如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設備、操作網(wǎng)絡與管理文件系統(tǒng)等根本領務。管理計算機系統(tǒng)的全部硬件資源包括軟件資源及數(shù)據(jù)資源;控制程序運行;改善人機界面;為其它應用軟件提供支持等，使計算機系統(tǒng)所有資源最大限度地發(fā)揮作用，為用戶提供方便的、有效的、友善的效勞界面。操作系統(tǒng)的管理控制程序，大致包括5個方面的管理功能:進程與處理機管理、作業(yè)管理、存儲管理、設備管

8、理、文件管理。目前微機上常見的操作系統(tǒng)有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等。但所有的操作系統(tǒng)具有并發(fā)性、共享性、虛擬性和不確定性四個根本特征。根據(jù)應用領域來劃分，可分為桌面操作系統(tǒng)、效勞器操作系統(tǒng)、主機操作系統(tǒng)、嵌入式操作系統(tǒng)。.、操作系統(tǒng)的開展手工操作階段。在這個階段的計算機，主要元器件是電子管，運算速度慢，沒有任何軟件,更沒有操作系統(tǒng)。用戶直接使用機器語言編寫程序,上機時完全手工操作,首先將預先準備好的程序紙帶裝入輸入機,然后啟動輸入機把程序和數(shù)據(jù)送入計算機,接著通過開關啟動程序運行,計算完成后,打印機輸出結果。批處理階段多道程序系統(tǒng)階段現(xiàn)

9、代操作系統(tǒng)階段.計算機操作系統(tǒng)的開展現(xiàn)狀Windows是一款流行的操作系統(tǒng)，在全球桌面系統(tǒng)市場占有90%左右的份額，同時在中低端效勞器市場也有廣泛的應用，如web效勞器和數(shù)據(jù)庫效勞器。Windows作為一個現(xiàn)代操作系統(tǒng)，無論在技術方面，還是在市場方面，都是成功的。Unix操作系統(tǒng)具有統(tǒng)一開放的事實標準和認證標準。該標準使不同unix操作系統(tǒng)上開發(fā)的應用程序可以輕松移植，極大地促進了unix的開展和應用。Unix已經(jīng)成為大型機、效勞器以及工作站的主要操作系統(tǒng)。Linux作為unix技術的繼承者，日益得到越來越多的效勞器設備、數(shù)據(jù)庫和中間件等軟件廠商的支持，并對商業(yè)版unix系統(tǒng)構成很強的威脅。開

10、源軟件模式及其實現(xiàn)的價值越來越得到社會的認可。以開源linux等為代表的類unix操作系統(tǒng)在不斷地侵蝕unix的市場空間。Linux操作系統(tǒng)無論從硬件還是從軟件來講，linux都已經(jīng)是個成熟的操作系統(tǒng)。免費與開源的特性使得linux對windows的威脅也越來越大。在效勞器和嵌入式系統(tǒng)市場上，linux已經(jīng)是主流的操作系統(tǒng)之一。Linux現(xiàn)在正在穩(wěn)步拓展桌面操作系統(tǒng)市場隨著linux的流行，越來越多的廠商開場愛其銷售的計算機上預裝linux。.處理死鎖的方法兩相封鎖法TwoPhaseLocl通過防止并發(fā)操作間的沖突到達事務處理之間的同步。在讀出數(shù)據(jù)項x之前，事務處理必須要對x擁有讀封鎖。在對數(shù)

11、據(jù)項x寫入之前，事務處理必須要對x擁有寫封鎖。擁有讀封鎖和寫封鎖要遵照兩條管理規(guī)那么：第一、二個事務處理不能同時對于同一個數(shù)據(jù)項擁有相互沖突的封鎖。第二，在一個事務釋放了對某一個數(shù)據(jù)項的封鎖擁有權以后，就不得再申請要求得到對任何數(shù)據(jù)項的封鎖擁有權。上述對封鎖擁有權的規(guī)定使得每個事務處理都以兩相方式獲得封鎖的擁有權。在增加封鎖擁有權的階段，事務處理不能釋放對任何數(shù)據(jù)項的封鎖擁有權、而只可以不斷申請獲得新的數(shù)據(jù)項的封鎖擁有權。在一旦釋放了對某一數(shù)據(jù)項的封鎖擁有權以后，事務處理進入壓縮封鎖擁有權的階段。在這個階段中。事務處理只能不斷釋放它的封鎖擁有權而不得再申請對任何數(shù)據(jù)項的封鎖擁有權。在事務處理完

12、畢或夭折時，將自動釋放全部封鎖。兩相封鎖法有一種特殊情況，在事務處理的主體局部執(zhí)行以前，就申請擁有該事務處理所需要的全部封鎖擁有權，通常稱這種特殊情況為“事先要求。顯然，事先要求算法有二個缺點：第一，過早地對數(shù)據(jù)項擁有封鎖權將會限制系統(tǒng)可能到達的并發(fā)程度。第二，對程序設計者提出了事先列出本領務所需要的全部的封鎖權要求，增加了程序設計者的負擔。用兩相封鎖法處理讀寫寫寫沖突操作時，它實現(xiàn)了非循環(huán)的rwrww關系，保證了一組事務處理過程的可串行化。串行執(zhí)行的順序由事務處理獲得封鎖擁有權的先后次序而定。在增長階段完畢時，獲得了所需要的全部封鎖有權以后，稱為到達了該事務處理的封鎖點。令E表示采用兩相封鎖

13、法作為同步機構時，各事務處理的執(zhí)行順序，令E表示每個事務處理在它的封鎖點一次申請擁有全部所需封鎖擁有權的情況下的執(zhí)行順序。在這兩種情況下所作出的rwr及ww關系是一樣的，因而這二者的執(zhí)行順序也是一致的。根本型兩相封鎖法兩相封鎖法的實現(xiàn)機構是一個調(diào)度程序，當事務處理對數(shù)據(jù)項發(fā)出讀寫請求時，調(diào)度程序按兩相封鎖法所描述的規(guī)定對數(shù)據(jù)項進展封鎖和解鎖操作。在分布式系統(tǒng)中，在每一個DM上有一調(diào)度程序，管理該DM所管轄的數(shù)據(jù)庫中的數(shù)據(jù)項。當DM接收到對數(shù)據(jù)項x的讀出寫入請求時，調(diào)度程序自動地為該數(shù)據(jù)項申請讀寫封鎖。如果這時該數(shù)據(jù)項已被其它操作封鎖，那么把申請封鎖操作置于該數(shù)據(jù)項的封鎖等待隊列中。在寫入操作完

14、成以后，調(diào)度程序自動釋放寫封鎖，釋放讀封鎖需要專用的釋放操作，它可以和寫入操作同時發(fā)出。寫入操作標志著壓縮階段的開場。當某一事務處理釋放了它的讀寫封鎖后；以先進先出的方式處理在等待隊列上的其他事務處理的讀寫封鎖的請求。在數(shù)據(jù)項有多個副本的情況下，假設邏輯數(shù)據(jù)項x有副本x1,x2,，xn,對于讀操作，事務處理可以讀任何一個副本，因此只需要獲得它實際執(zhí)行讀操作的那個副本上的讀封鎖。對于寫操作，需要修改數(shù)據(jù)項的所有副本，必須要獲得所有副本上的寫封鎖。主副本型的兩相封鎖法本方法專用于處理邏輯數(shù)據(jù)項有多個副本的情況，每個邏輯數(shù)據(jù)項的一份副本被指定為主副本，事務處理在邏輯數(shù)據(jù)項的任何副本以前，必須在主副本

15、上獲得所需的封鎖。對于讀封鎖，本方法比根本型的兩相封鎖法有更多的通信開銷，當事務處埋希望讀出的副本不是主副本時，它必須與二個DM通信。一個是存放主副本的DM，另一個是要讀出的副本所在的DM，而在根本型兩相封鎖法中，只要和要讀出的副本所在的DM通信。當事務處理所在的TM與要讀出的副本所在的DM在同一個計算機結點時，增加的開銷是很大的。對于寫封鎖，主副本型兩封相鎖法比根本型的封鎖開銷要少。在根本型算法中，事務處理要向具有副本的所有結點發(fā)出封寫鎖請求，而在主副本型算法中，只要向主副本所在結點發(fā)出請求。投票表決型兩相封鎖法投票表決型兩相封鎖法也是用于多副本的系統(tǒng)中的一種同步算法。當事務T要對x發(fā)出寫入

16、請求時，把請求發(fā)往持有x的副本的所有DM，DM檢查本數(shù)據(jù)庫中x的副本情況，如果x已被封鎖，那么發(fā)回“封鎖受到阻塞的信號；如果x沒有被封鎖，那么對x加鎖，并發(fā)回“封鎖已設置信號，事務T對“封鎖已設置的響應信號計數(shù)，當數(shù)量過半，那么認為全部封鎖均已設置，如數(shù)量缺乏半數(shù)，它將等待發(fā)出“封鎖受到阻塞的DM在x被解鎖以后發(fā)回“封鎖已設置的信號。只要不出現(xiàn)死鎖，它最終將收到足夠的“封鎖已設置信號而繼續(xù)工作。集中型兩相封鎖法集中型兩相封鎖法把管理數(shù)據(jù)項封鎖的調(diào)度程序全部集中在一個結點上，在讀寫任何結點上的數(shù)據(jù)以前，必須從中心結點的調(diào)度程序獲得相應的封鎖。這個算法非常相似于主副本型的兩相封鎖法，相當于把所有數(shù)

17、據(jù)項的主副本都集中在中心結點上，故很容易在中心結點構成通信和封鎖操作的瓶頸。它的主要優(yōu)點是簡單。三、對銀行家算法局部的體會通過此次的實驗，讓我知道了應付死鎖最好的方法銀行家算法。更讓我知道了銀行家算法的實現(xiàn)過程。.銀行家算法1如果Requesticor=Need,那么轉(zhuǎn)向步驟（2）；否那么，認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。2如果RequesEor=Available那么轉(zhuǎn)向步驟3；否那么，表示系統(tǒng)XX無足夠的資源，進程必須等待。3系統(tǒng)試探把要求的資源分配給進程Pi,并修改下面數(shù)據(jù)構造中的數(shù)值：Available=Available-Requesti;Allocation=

18、Allocation+Request;Need=Need-Request;(4)系統(tǒng)執(zhí)行平安性算法，檢查此次資源分配后，系統(tǒng)是否處于平安狀態(tài)。.平安性算法系統(tǒng)所執(zhí)行的平安性算法可描述如下：設置兩個向量工作向量Work，它表示系統(tǒng)可以提供應進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行平安算法開場時，Work：=Available。Finish,它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開場時先做Finishi：=FALSE；當有足夠資源分配給進程時，再令Finishi：=TRUE。從進程集合中找到一個能滿足下述條件的進程：Finishi=FALSE；NeedI,jor=Wor

19、kj;假設找到，執(zhí)行步驟3，否那么，執(zhí)行步驟4。當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行：Workj：=Workj+Allocationi，j；Finishi：=TRUE；Gotostep2；如果所有進程的Finishi=TRUE都滿足，那么表示系統(tǒng)處于平安狀態(tài)；否那么，系統(tǒng)處于不平安狀態(tài)。四、課程設計過程中的應用與實踐目的：切實加深對進程死鎖的認識；正確理解系統(tǒng)的平安狀態(tài)與不平安狀態(tài)；更進一步地理解和掌握銀行家算法。內(nèi)容：將本實驗分成兩個階段，第一階段實現(xiàn)系統(tǒng)平安性檢測算法；第二階段實現(xiàn)銀行家算法；要求用戶能自主地輸入不同的向量矩陣；程序能正確輸出不同的運算結果；程序應具備良好的容錯能力；力求用戶界面的簡潔美觀；數(shù)據(jù)構造數(shù)組intMax100100=0;/各進程所需各類資源的最大需求intAvaliable100=0;/系統(tǒng)可用資源charname100=0;/資源的名稱intAllocation100100=0;/系統(tǒng)已分配資源intNeed100100=0;/還需要資源intRequest100=0;/請求資源向量inttemp100=0;/存放平安序列intWork100=0;/存放系統(tǒng)可提供資源算法設計