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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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