【正文】 圖是不可完全簡化的。J 剝奪資源J 撤消進(jìn)程5. 銀行家算法178。若系統(tǒng)不存在這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。例，系統(tǒng)共有12臺磁帶機(jī)，T0時刻的情況如下表，已分配出9臺，可用磁帶機(jī)為3臺。 進(jìn)程 最大需求 已分配 尚需要 可用 P1 10 5 5 3（2） P2 4 2 2 P3 9 2（3） 7（6）若此時P3請求1臺磁帶機(jī)，則分配情況如上表（括號內(nèi)的數(shù)據(jù)），此時系統(tǒng)不存在安全序列，進(jìn)入不安全狀態(tài)，將導(dǎo)致死鎖。 利用銀行家算法避免死鎖216。 步驟設(shè)request[j]=k，表示進(jìn)程P需要k個j類資源。 安全性算法（1） 設(shè)置向量work和finish的初始值work=available 目前可提供的資源數(shù)目finish[i]=false 表示該進(jìn)程尚未運(yùn)行完成。 needi 163。 若找到，執(zhí)行（3），否則執(zhí)行（4）。習(xí)題分析一. 判斷改錯題（判斷由下劃線標(biāo)明的關(guān)鍵詞的敘述是否正確，正確的打√，錯誤的打并改正。（ ）（2） 在生產(chǎn)者消費(fèi)者進(jìn)程中，V操作的次序無關(guān)緊要，而P操作次序不能顛倒。（ ）（4） 原語是指操作系統(tǒng)中的初始化程序。( )（6） 并發(fā)進(jìn)程可以同時進(jìn)入臨界區(qū)，交替訪問臨界資源。（ ）（8） 消息通信因為它數(shù)據(jù)量較小，因而它是一種低級通信方式。（ ）（10） 管道通信，是以管道消息為單位進(jìn)行讀寫的，可進(jìn)行大批量數(shù)據(jù)交換，其工作是以先進(jìn)先出為順序的。（ ）（12） 操作系統(tǒng)的進(jìn)程管理是整個操作系統(tǒng)管理中的核心，它包含了進(jìn)程的調(diào)度、協(xié)調(diào)以及進(jìn)程通信。（2） 對；（3） 錯；應(yīng)為：產(chǎn)生死鎖的原因是：進(jìn)程推進(jìn)順序不當(dāng)或競爭資源。（5） 錯；應(yīng)為：……當(dāng)引起阻塞的條件被解除時，進(jìn)程狀態(tài)應(yīng)變?yōu)榫途w狀態(tài)。（7） 錯；應(yīng)為：程序的封閉性是指該程序在運(yùn)行獨占系統(tǒng)資源，只有程序本身能改變系統(tǒng)資源。（9） 錯；應(yīng)為：單機(jī)系統(tǒng)只允許一個進(jìn)程處于運(yùn)行狀態(tài)。（2） 消息傳遞系統(tǒng)屬于 級通信方式，進(jìn)程間的數(shù)據(jù)交換以 為單位。（4） 一個進(jìn)程可以由系統(tǒng)創(chuàng)建，或者由 用創(chuàng)建原語創(chuàng)建。在條件成熟時，采用 原語為它們分配除 以外的所需資源，并被排列到 隊列中。（6） 輪轉(zhuǎn)法是按照 輪流地把處理器分配給就緒隊列中的進(jìn)程，該算法多用于 系統(tǒng)中，其難點在于 。（8） 死鎖的檢測可以通過 圖，利用 定理來實現(xiàn)。（10） 有m個進(jìn)程共享同一臨界資源，若使用信號量機(jī)制實現(xiàn)對臨界資源的互斥訪問，則信號量值的變化范圍是 。（12） 操作系統(tǒng)中的第一個進(jìn)程是由 程序建立的一個 或一個系統(tǒng)主進(jìn)程。主要功能有：進(jìn)程控制、進(jìn)程同步、進(jìn)程通信和進(jìn)程調(diào)度。封閉性——程序在封閉的環(huán)境下運(yùn)行，獨占全機(jī)資源，執(zhí)行結(jié)果不受外界因素影響。而程序的并發(fā)執(zhí)行恰好相反，具有間斷性、失去封閉性和不可再現(xiàn)性。Bernstein條件為： 設(shè)R(p)為進(jìn)程p的讀集，W(p)為進(jìn)程p的寫集，有進(jìn)程P1和P2，則P1和P2并發(fā)的條件是： R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={} 如：有進(jìn)程：S1：a=x+y。 S3：c=ab。 ∵ R(S1)∩W(S2)∪R(S2)∩W(S1)∪ W(S1)∩W(S2)={}，滿足bernstein條件：∴S1和S2兩條語句可以并發(fā)∵ R(S1)∩W(S3)∪R(S3)∩W(S1)∪ W(S1)∩W(S3)={a}≠{}，不滿足Bernstein條件： ∴S1和S3不能并發(fā)(4) 簡述進(jìn)程的定義，進(jìn)程的基本狀態(tài)以及進(jìn)程狀態(tài)轉(zhuǎn)換的典型原因。進(jìn)程有三種基本狀態(tài)：就緒，執(zhí)行和阻塞。答：進(jìn)程是可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運(yùn)行過程，進(jìn)程有動態(tài)性、并發(fā)性、獨立性和異步性、結(jié)構(gòu)特征，而程序是靜態(tài)的，不能并發(fā)執(zhí)行，未建立進(jìn)程的程序也不能作為一個獨立的單位參加運(yùn)行。程序是進(jìn)程運(yùn)行所對應(yīng)的執(zhí)行代碼，數(shù)據(jù)集合是進(jìn)程運(yùn)行所必需的數(shù)據(jù)資源，進(jìn)程控制塊是保存進(jìn)程狀態(tài)，控制進(jìn)程轉(zhuǎn)換的標(biāo)志。答：PCB的內(nèi)容216。216。 進(jìn)程調(diào)度信息——進(jìn)程狀態(tài)、優(yōu)先級等。 進(jìn)程控制信息——程序和數(shù)據(jù)地址、同步機(jī)制、資源清單等。最基本的通信原語有發(fā)送原語和接收原語。答：讀者—寫者問題是典型的進(jìn)程同步問題。允許多個讀進(jìn)程同時讀一個共享對象，但絕不允許一個寫進(jìn)程和其它讀進(jìn)程或?qū)戇M(jìn)程同時訪問共享對象。(10) 簡述直接通信與間接通信的區(qū)別。發(fā)送和接收進(jìn)程都以顯式的方式，提供對方的標(biāo)識符。(11) 什么是操作系統(tǒng)的內(nèi)核？答：內(nèi)核是計算機(jī)硬件的第一層擴(kuò)充軟件，由與硬件緊密相關(guān)的模塊以及運(yùn)行頻率較高的模塊組成，常駐內(nèi)存，以提高OS的運(yùn)行效率。(13) 簡述引起進(jìn)程調(diào)度的原因。時間片到——分時系統(tǒng)中，每當(dāng)時間片到，正在運(yùn)行的進(jìn)程被暫時停止，排入就緒隊列，引起調(diào)度另一就緒進(jìn)程進(jìn)入運(yùn)行外部中斷——外部中斷信號引起調(diào)度。(14) 進(jìn)程調(diào)度有何功能？有哪些常用的調(diào)度算法？答：查詢、登記和更新進(jìn)程控制表PCB中相應(yīng)表項，并根據(jù)表項中的內(nèi)容和狀態(tài)作出選擇決定；根據(jù)系統(tǒng)選定的調(diào)度算法，從就緒進(jìn)程隊列中選取一個就緒進(jìn)程，分配CPU，并決定它運(yùn)行多長時間（調(diào)度方式）；進(jìn)行實際分配工作，更新被調(diào)度進(jìn)程和正在運(yùn)行進(jìn)出的PCB表項，修改狀態(tài)，切換進(jìn)程執(zhí)行代碼。(15) 簡述進(jìn)程調(diào)度的“輪轉(zhuǎn)法”。這樣就保證隊列中所有的進(jìn)程，在一給定的時間內(nèi)，均能獲得一時間片的處理機(jī)執(zhí)行時間。在銀行家算法中檢查資源分配后系統(tǒng)的安全性，保證系統(tǒng)處于安全狀態(tài)，不會發(fā)生死鎖。答：安全性算法是銀行家算法的重要一步。Work＝work＋allocation，finish＝true；若所有進(jìn)程的finish＝true，表示系統(tǒng) 處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。答：進(jìn)程之間存在兩種相互制約關(guān)系：（1）間接相互制約——資源共享關(guān)系，是由于多個進(jìn)程共享同一資源引起的。其中（1）、（2）屬于間接相互制約，而（3）、（4）屬于直接相互制約。因為4個資源分配給3個進(jìn)程，無論如何分配，總會有1個進(jìn)程能夠分配到2個資源，該進(jìn)程獲得其最大資源數(shù)后，完成并釋放其資源，剩余2個進(jìn)程就可獲得最大資源數(shù)，順利完成，系統(tǒng)始終存在安全序列，故系統(tǒng)不會死鎖。答：資源分配圖是用來描述死鎖的工具。若資源分配是圖不可完全簡化的 ，該狀態(tài)為死鎖狀態(tài)。(21) 資源分配圖如下圖，系統(tǒng)是否處于死鎖狀態(tài)？P0 P10P2P4P3 由于該圖是不可完全簡化的，所以根據(jù)死鎖定理，系統(tǒng)處于死鎖狀態(tài)。 P3P4P2(22) 簡述解決死鎖的途徑：1）、預(yù)防死鎖——設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件之一。3）、檢測死鎖——允許發(fā)生死鎖，但通過系統(tǒng)設(shè)置的檢測機(jī)構(gòu)，檢測死鎖的發(fā)生，并精確確定與死鎖有關(guān)的進(jìn)程和資源。 (23) 設(shè)有進(jìn)程P1和P2并發(fā)執(zhí)行，都要享用資源R1，R2，使用資源情況如下：進(jìn)程P1：……申請R1……申請R2……釋放R1……進(jìn)程P2：……申請R2……申請R1……釋放R2……判斷是否會產(chǎn)生死鎖，并解釋其原因。在某時刻，P1占用R1，又去申請R2；而P2占用R2，又去申請R1；互不釋放自己占用的資源，又得不到自己所需的資源，系統(tǒng)處于僵持狀態(tài)，形成死鎖。答：用資源分配圖加以簡化的方法來檢測系統(tǒng)是否處于死鎖狀態(tài)。該充分條件稱為死鎖定理。從上圖表示可以看出，此題相當(dāng)于是用信號量描述前趨關(guān)系。P1：起跑——前進(jìn)100米——V(S1)P2：P(S1)——起跑——前進(jìn)100米——V(S2)P3：P(S2)——起跑——前進(jìn)100米——V(S3)P4：P(S3)——起跑——前進(jìn)100米——到達(dá)終點(2) 有一發(fā)送者進(jìn)程和一接收者進(jìn)程，其流程如下。試完成流程圖。相應(yīng)的，A為P(m)，B為V(m)。 (3) 桌上有一只盤子，最多允許存放兩只水果，每次只能放入或取出一個水果。試用PV操作實現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。只有盤中有蘋果，兒子才能取，只有盤中有桔子，女兒才能取，即兒女取水果的操作取決于相應(yīng)水果是否存在。每次只能向盤子放入或從盤中取出一個水果，用互斥信號量實現(xiàn)。解答：根據(jù)常識，車門關(guān)好后司機(jī)方可啟動車輛，到站停車后售票員方可打開車門，即門的開、關(guān)與車的停、開存在著相互制約的同步關(guān)系。定義信號量stop表示售票員是否可以開車門，即車是否停好（0表示車停，1表示車開），初值為0。售票員： 上乘客； 關(guān)車門； V(run)。 售票； P(stop)。 下乘客； 司機(jī)： P(run)。 正常行車； 到站停車； V(Stop)。(5) 某寺廟，有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚引用。水井徑窄，每次只能容一個桶取水。每次入、取缸水僅為一桶，且不可同時進(jìn)行。解答：分析題目可知，小和尚負(fù)責(zé)用桶到井中取水并將水倒入缸中，其操作依次為拿桶、井中取水、倒水入缸。老和尚負(fù)責(zé)用桶從缸中取水，其操作依次為拿桶、缸中取水。每次入、取缸水僅為一桶，且不可同時進(jìn)行，表明小和尚倒水入缸、老和尚取水必須互斥。設(shè)置互斥信號量和同步信號量： m1=1，表示小和尚從水井取水時，對水井的互斥訪問，即一次只能有一個水桶進(jìn)出水井；m2=1，表示小和尚倒水入缸、老和尚取水時對水缸的互斥訪問，即每次入、取缸水只能一個桶；count=4，表示是否有桶可以供小和尚、老和尚使用； full=0滿緩沖，表示缸內(nèi)有水的桶數(shù)，控制老和尚取水；empty=12，空緩沖，缸內(nèi)還能放水的桶數(shù)，控制小和尚倒水入缸； P(empty) 判斷缸中是否有倒水的位置，若有，水位1，繼續(xù)； P(count) 判斷是否有水桶可以使用，若有，可用水桶數(shù)目1，繼續(xù)； P(m1) 判斷能否對水井訪問，即是否有其他小和尚從水井取水 從井中取水 互斥控制一個水桶從水井取水； V(m1) P(m2) 判斷能否對水缸訪問，即是否有其他和尚取水或倒水 送水入缸 互斥地將水倒入水缸； V(m2) V(count) 水入缸后，水桶空閑，可供其他和尚使用。若某時刻水缸水滿（empty=0。老和尚無法取水，小和尚無法倒水，形成僵局，死鎖發(fā)生。小和尚從水井取水入缸老和尚從缸中取水 P(full) 缸中是否有水供老和尚取用；若有，可取水的桶數(shù)1，繼續(xù)； P(count) 判斷是否有水桶可以使用，若有，可用水桶數(shù)目1，繼續(xù)； P(m2) 判斷能否對水缸訪問，即是否有其他和尚取水或倒水 從缸中取水 互斥地從水缸中取水； V(m2) V(empty) 取水后，水缸中增加了倒水的位置，水位+1； V(count) 取水后，水桶空閑，可供其他和尚使用。最大資源需求已分配資源剩余資源數(shù)ABCABCABCP1559212233P2536402P34011405P4425204P542431415217i. 完成剩余資源數(shù)的計算：ii. T0時刻是否安全？iii. 若P2請求資源（0，3，4），系統(tǒng)如何處理？解答：T0時刻的向量見圖中粗體數(shù)字。按照銀行家算法，在T0時刻P2請求資源（0，3，4），因請求資源數(shù)（0，3，4）最大請求資源數(shù)（1，3，4），繼續(xù)。(7) P1，P2，P3，P4四個進(jìn)程同時依次進(jìn)入就緒隊列，它們所需要的處理器時間和優(yōu)先數(shù)如下，若不計調(diào)度等所消耗的時間，請回答：進(jìn)程 處理器時間（秒） 優(yōu)先數(shù) P1 20 2 P2 15 3 P3 10 5 P4 12 3（a） 分別寫出采用先來先服務(wù)和非搶占式的優(yōu)先數(shù)調(diào)度算法時進(jìn)程執(zhí)行的次序。解答：（a）進(jìn)程執(zhí)行次序為： 先來先服務(wù)法非搶占式的優(yōu)先數(shù)法PPPP4PPPP1 （b） 先來先服務(wù)法： 每個進(jìn)程在就緒隊列的等待時間分別為 P1：0（秒） P2：0+20=20（秒） P3：20+15=35（秒） P4：35+10=45（秒） 平均等待時間為（0+20+35+45）/4=25（秒） 非搶占式的優(yōu)先數(shù)法： 每個進(jìn)程在就緒隊列的等待時間分別為 P1：25+12=37（秒）P2：0+10=10（秒）P3：0（秒）P4：10+15=25（秒）平均等待時間為（37+10+0+25）/4=18（秒）(8) 系統(tǒng)中有四道作業(yè)，分別用先來先服務(wù)、短作業(yè)優(yōu)先調(diào)度方法和最高響應(yīng)比優(yōu)先法調(diào)度，完成表格的計算，并計算平均帶權(quán)周轉(zhuǎn)時