南京郵電大學(xué)操作系統(tǒng)課后習(xí)題答案教材

1、操作系統(tǒng)教程南郵正式版 習(xí)題解答 第三章 進(jìn)程管理與調(diào)度習(xí)題 1、什么是多道程序設(shè)計(jì)？多道程序設(shè)汁利用了系統(tǒng)與外|朋殳備的并行工作能力，從而提高 工作效率，具體表現(xiàn)在哪些方而？ 答： 讓多個(gè)計(jì)算問題同時(shí)裝入一個(gè)計(jì)算機(jī)系統(tǒng)的主存儲(chǔ)器并行執(zhí)行，這種設(shè)計(jì)技術(shù)稱“多道程序 設(shè)計(jì)”，這種訃算機(jī)系統(tǒng)稱“多道程序設(shè)計(jì)系統(tǒng)“或簡稱“多道系統(tǒng)“。在多道程序設(shè)il的系 統(tǒng)中，主存儲(chǔ)器中同時(shí)存放了多個(gè)作業(yè)的程序。為避免相互干擾，必須提供必要的手段使得 在主存儲(chǔ)器中的各道程序只能訪問自己的區(qū)域。 提高工作效率，具體表現(xiàn)在： 提高了處理器的利用率： 充分利用外囤設(shè)備資源：計(jì)算機(jī)系統(tǒng)配宜多種外帀設(shè)備，采用多道程序設(shè)計(jì)并行

2、工 作時(shí)，可以將使用不同設(shè)備的程序搭配在一起同時(shí)裝入主存儲(chǔ)器，使得系統(tǒng)中外 國設(shè)備經(jīng)常處于忙碌狀態(tài)，系統(tǒng)資源被充分利用： 發(fā)揮了處理器與外困設(shè)備以及外圍設(shè)備之間的并行工作能力： 從總體上說，采用多道程序設(shè)汁技術(shù)后，可以有效地提高系統(tǒng)中資源的利用率，增加單位時(shí) 間內(nèi)的算題量，從而提高了吞吐率。 2、請描述進(jìn)程的定義和屬性。 答： 進(jìn)程是具有獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)，是系統(tǒng)進(jìn)行資源分配、調(diào) 度和保護(hù)的獨(dú)立單位。 進(jìn)程的屬性有：結(jié)構(gòu)性共享性動(dòng)態(tài)性獨(dú)立性制約性并發(fā)性 3、請描述進(jìn)程與程序的區(qū)別及關(guān)系。 答： 20 程序是靜止的，進(jìn)程是動(dòng)態(tài)的。進(jìn)程包括程序和程序處理的對象(數(shù)據(jù)集)

3、，進(jìn)程能得到程 序處理的結(jié)果。進(jìn)程和程序并非一一對應(yīng)的，一個(gè)程序運(yùn)行在不同的數(shù)據(jù)集上就構(gòu)成了不同 的進(jìn)程。通常把進(jìn)程分為“系統(tǒng)進(jìn)程”和“用戶進(jìn)程“兩大類，把完成操作系統(tǒng)功能的進(jìn)程稱為 系統(tǒng)進(jìn)程，而完成用戶功能的進(jìn)程則稱為用戶進(jìn)程。 4、進(jìn)程有哪三種基本狀態(tài)？三種進(jìn)程狀態(tài)如何變化？ 答： 通常，根據(jù)進(jìn)程執(zhí)行過程中不同時(shí)刻的狀態(tài)，可歸納為三種基本狀態(tài)： 等待態(tài)：等待某個(gè)事件的完成； 就緒態(tài)：等待系統(tǒng)分配處理器以便運(yùn)行； 運(yùn)行態(tài)：占有處理器正在運(yùn)行。 進(jìn)程在執(zhí)行中狀態(tài)會(huì)不斷地改變，每個(gè)進(jìn)程在任何時(shí)刻總是處于上述三種基本狀態(tài)的某一種 基本狀態(tài)，進(jìn)程狀態(tài)之間轉(zhuǎn)換關(guān)系： 運(yùn)行態(tài)-等待態(tài)往往是由于等待外設(shè)，

4、等待主存等資源分配或等待人工干預(yù)而引起的。 等待態(tài)-就緒態(tài)則是等待的條件已滿足，只需分配到處理器后就能運(yùn)行。 運(yùn)行態(tài)T就緒態(tài)不是由于自身原因，而是由外界原因使運(yùn)行狀態(tài)的進(jìn)程讓出處理器，這時(shí) 候就變成就緒態(tài)。例如時(shí)間片用完，或有更髙優(yōu)先級的進(jìn)程來搶占處理器等。 就緒態(tài)T運(yùn)行態(tài)系統(tǒng)按某種策略選中就緒隊(duì)列中的一個(gè)進(jìn)程占用處理器，此時(shí)就變成了運(yùn) 行態(tài)。 5、進(jìn)程控制塊是什么，有何作用？通常進(jìn)程控制塊包含哪些信息？ 答： 進(jìn)程控制(Process Control Block.簡稱PCB),是操作系統(tǒng)為進(jìn)程分配的用于標(biāo)志進(jìn)程，記 錄各進(jìn)程執(zhí)行情況的。進(jìn)程控制塊是進(jìn)程存在的標(biāo)志，它記錄了進(jìn)程從創(chuàng)建到消亡動(dòng)態(tài)

5、變化 的狀況，進(jìn)程隊(duì)列實(shí)際也是進(jìn)程控制塊的鏈接。操作系統(tǒng)利用進(jìn)程控制塊對進(jìn)程進(jìn)行控制和 管理。 標(biāo)志信息含唯一的進(jìn)程統(tǒng) 說明信息有進(jìn)程狀態(tài)、等待原因、進(jìn)程程序存放位置和進(jìn)程數(shù)據(jù)存放位置 現(xiàn)場信息包括通用、控制和程序狀態(tài)字寄存器的內(nèi)容 管理信息存放程序優(yōu)先數(shù)和隊(duì)列指針 進(jìn)程控制塊的作用有： 20 （1）記錄進(jìn)程的有關(guān)信息，以便操作系統(tǒng)的進(jìn)程調(diào)度程序?qū)M(jìn)程進(jìn)行調(diào)度。這些信息 包括標(biāo)志信息、說明信息、現(xiàn)場信息和管理信息等： （2）標(biāo)志進(jìn)程的存在，進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志 6、什么是可再入程序？ 答： （1）什么是可再入程序。一個(gè)能被多個(gè)用戶同時(shí)調(diào)用的程序稱做可再入的程序。 （2）可再入程序的性

6、質(zhì)。 可再入程序必須是純代碼，在執(zhí)行時(shí)自身不改變； 一個(gè)可再入程序要求調(diào)用者提供工作區(qū)，以保證程序以同樣方式為各用戶服務(wù)。 編譯程序和操作系統(tǒng)程序通常都是”可再入”程序，能同時(shí)被不同用戶調(diào)用而構(gòu)成不同的 進(jìn)程。 7、闡述進(jìn)程調(diào)度的常用算法：先來先服務(wù)、優(yōu)先數(shù)法、輪轉(zhuǎn)法。 答： 先來先服務(wù)調(diào)度算法該算法按進(jìn)程進(jìn)入就緒隊(duì)列的先后次序選擇可以占用處理器 的進(jìn)程。 優(yōu)先數(shù)調(diào)度算法對每個(gè)進(jìn)程確左一個(gè)優(yōu)先數(shù)，該算法總是讓優(yōu)先數(shù)最髙的進(jìn)程先使 用處理器。對具有相同優(yōu)先數(shù)的進(jìn)程，再采用先來先服務(wù)的次序分配處理器。系統(tǒng) 常以任務(wù)的緊迫性和系統(tǒng)效率等因素確定進(jìn)程的優(yōu)先數(shù)。進(jìn)程的優(yōu)先數(shù)可以固定的, 也可隨進(jìn)程執(zhí)行過

7、程動(dòng)態(tài)變化。一個(gè)高優(yōu)先數(shù)的進(jìn)程占用處理器后，系統(tǒng)處理該進(jìn) 程時(shí)有兩種方法，一是”非搶占式”，列一種是可搶占式”。前者是此進(jìn)程占用處理 器后一直運(yùn)行到結(jié)朿，除非本身主動(dòng)讓出處理器，后者則是嚴(yán)格保證任何時(shí)刻總是 讓優(yōu)先數(shù)最高的進(jìn)程在處理器上運(yùn)行。 時(shí)間片輪轉(zhuǎn)調(diào)度法把規(guī)定進(jìn)程一次使用處理器的最長時(shí)間稱為”時(shí)間片“。時(shí)間片輪 轉(zhuǎn)涮度算法讓就緒進(jìn)程按就緒的先后次序排成隊(duì)列，每次總選擇該隊(duì)列中第一個(gè)進(jìn) 程占用處理器，但規(guī)泄只能使用一個(gè)時(shí)間片，如該進(jìn)程尚未完成，則排入隊(duì)屋，等 待下一個(gè)供它使用的時(shí)間片。各個(gè)進(jìn)程就這樣輪轉(zhuǎn)運(yùn)行。時(shí)間片輪轉(zhuǎn)算法經(jīng)常用于 分時(shí)操作系統(tǒng)中。 8、程序狀態(tài)字包含哪些主要內(nèi)容？ 答：

8、（1）程序基本狀態(tài) 20 （2）中斷碼 （3）中斷屏蔽位 9、比較進(jìn)程調(diào)度與作業(yè)調(diào)度的不同點(diǎn)。 答： 1）作業(yè)調(diào)度是宏觀調(diào)度，它決泄了哪一個(gè)作業(yè)能進(jìn)入主存。進(jìn)程調(diào)度是微觀調(diào)度，它決左 各作業(yè)中的哪一個(gè)進(jìn)程占有中央處理機(jī)。（或）作業(yè)調(diào)度是髙級調(diào)度，它位于操作系統(tǒng)的作 業(yè)管理層次。進(jìn)程調(diào)度是低級調(diào)度，它位于操作系統(tǒng)分層結(jié)構(gòu)的最內(nèi)層。 （2）作業(yè)調(diào)度是選符合條件的收容態(tài)作業(yè)裝入內(nèi)存。進(jìn)程調(diào)度是從就緒態(tài)進(jìn)程中選一個(gè)占 用處理機(jī)。 10、C程序說明系統(tǒng)調(diào)用fork（）的應(yīng)用。請?jiān)谔幪钊胗嘘P(guān)父、子進(jìn)程的正確語句： / * Example to demonstrate the function of Sys

9、tem Call fork */ mainO int i； if（i）0 printf （）: else printf （”）: printf （）: 執(zhí)行本程序時(shí)，子進(jìn)程在標(biāo)準(zhǔn)輸出上打印以下結(jié)果： It is child process. Exit. 父進(jìn)程在標(biāo)準(zhǔn)輸出上打印以下結(jié)果： It is Parent process. Exit. 11、單道批處理環(huán)境下有5個(gè)作業(yè)，各作業(yè)進(jìn)入系統(tǒng)的時(shí)間和估計(jì)運(yùn)行時(shí)間如下表所示： 20 作業(yè) 進(jìn)入系統(tǒng)時(shí)間 估計(jì)運(yùn)行時(shí)間/分鐘 1 50 C 11:10 12:00 D 10:50 12:20 各作業(yè)周轉(zhuǎn)時(shí)間為：作業(yè)A 70,作業(yè)B 30,作業(yè)C 90,作

10、業(yè)D 90。平均作業(yè)周 轉(zhuǎn)時(shí)間為70分鐘。 20 第四章并發(fā)進(jìn)程的同步與互斥 1、進(jìn)程間同步和互斥的含義是什么？ 答： 同步：并發(fā)進(jìn)程之間存在的相互制約和相互依賴的關(guān)系。 互斥：若干進(jìn)程共享一資源時(shí)，任何時(shí)刻只允許一個(gè)進(jìn)程使用。 2、用文字描述銀行家算法的基本思想？ 答： 銀行家算法的基本思想是：將系統(tǒng)中的所有資源比做銀行家的資金，每進(jìn)行 一次資源的分配，銀行家都要從當(dāng)前的資源分配情況出發(fā)，計(jì)算這種分配方案的 安全性，如果是安全的，則進(jìn)行分配，否則選擇其它可能的分配方案。這樣，每 次分配都汁算安全性，從而可以避免死鎖的發(fā)生。 3、簡述死鎖的防I匕與死鎖的避免的區(qū)別。 答： 死鎖的防止是系統(tǒng)預(yù)先

11、確左一些資源分配策略，進(jìn)程按規(guī)左申請資源，系統(tǒng)按預(yù)先規(guī)龍的策 略進(jìn)行分配，從而防止死鎖的發(fā)生。 而死鎖的避免是當(dāng)進(jìn)程提出資源申請時(shí)系統(tǒng)測試資源分配，僅當(dāng)能確保系統(tǒng)安全時(shí)才把資源 分配給進(jìn)程，使系統(tǒng)一直處于安全狀態(tài)之中，從而避免死鎖。 4、試說明資源的靜態(tài)分配策略能防止死鎖的原因。 答： 資源靜態(tài)分配策略要求每個(gè)進(jìn)程在開始執(zhí)行前申請所需的全部資源，僅在系統(tǒng)為之分配了所 需的全部資源后，該進(jìn)程才開始執(zhí)行。這樣，進(jìn)程在執(zhí)行過程中不再申請資源，從而破壞了 死鎖的四個(gè)必要條件之一“占有并等待條件“，從而防止死鎖的發(fā)生。 5、有三個(gè)進(jìn)程Pl, P2和P3并發(fā)工作。進(jìn)程P1需用資源S3和S1：進(jìn)程P2需用資

12、源S1 和S2；進(jìn)程P3需用資源S2和S3?；卮穑?(1) 若對資源分配不加限制，會(huì)發(fā)生什么情況?為什么？ (2) 為保證進(jìn)程正確工作，應(yīng)采用怎樣的資源分配策略?為什么？ 答： (1)可能會(huì)發(fā)生死鎖 20 例如：進(jìn)程PI, P2和P3分別獲得資源S3. S1和S2后再繼續(xù)申請資源時(shí)都要等待(2 分)，這是循環(huán)等待。 (或進(jìn)程在等待新源時(shí)均不釋放已占資源) (2)可有幾種答案： A.采用靜態(tài)分配 由于執(zhí)行前已獲得所需的全部資源，故不會(huì)出現(xiàn)占有資源又等待別的 資源的現(xiàn)象(或不會(huì)出現(xiàn)循環(huán)等待資源現(xiàn)象)。 或B.采用按序分配不會(huì)出現(xiàn)循環(huán)等待資源現(xiàn)象。 或C.采用銀行家算法因?yàn)樵诜峙鋾r(shí)，保證了系統(tǒng)處于安

13、全狀態(tài)。 6、某車站售票廳，任何時(shí)刻最多可容納20爼購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí), 則廳外的購票者可立即進(jìn)入，否則需在外而等待。若把一個(gè)購票者看作一個(gè)進(jìn)程，請回答下 列問題： (1) 用PV操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號量，寫出信號量的初值以及信號量 各種取值的含義。 (2) 根據(jù)所定義的信號量，把應(yīng)執(zhí)行的PV操作填入適當(dāng)，以保證進(jìn)程能夠正確地并發(fā)執(zhí) 行。 COBEGIN PROCESS PI(I=h 2,) begin: 進(jìn)入售票廳： 購票； 退出： end； COEND (3) 若欲購票者最多為n個(gè)人，寫出信號量可能的變化范羽(最大值和最小值)。 答： (1)定義一信號

14、量S,初始值為20。 意義： 票廳的人數(shù) S=o表示售票廳中已有20名顧 客(購票者) S0 S的值表示可繼續(xù)進(jìn)入售 進(jìn)入售票廳: 購票； 退岀： V（s） （3）S的最大值為20 S的最小值為20-n 注：信號量的符號可不同（如寫成t）,但使用時(shí)應(yīng)一致（即上述的s全應(yīng)改成t）。 7、假泄系統(tǒng)有三個(gè)并發(fā)進(jìn)程read, move和print共享緩沖器Bl和B2。進(jìn)程read負(fù)責(zé)從輸 入設(shè)備上讀信息，每讀岀一個(gè)記錄后把它存放到緩沖器B1中。進(jìn)程move從緩沖器B1中 取出一記錄，加工后存入緩沖器B2。進(jìn)程print將B2中的記錄取出打印輸出。緩沖器B1 和B2每次只能存放一個(gè)記錄。要求三個(gè)進(jìn)程協(xié)調(diào)

15、完成任務(wù)，使打印出來的與讀入的記錄的 個(gè)數(shù)，次序完全一樣。 請用PV操作，寫出它們的并發(fā)程序。 答： begin SR.SM 1 ,SM2.SP:semaphore; Bl.B2:record; SR:=l;SMl:=0;SM2:=l;SP:=0 cobegin process read X:record; begin R:（接收來自輸入設(shè)備上一個(gè)記錄） X:=接收的一個(gè)記錄： P（SR）： B1:=X; V（SM1）; goto R; end; Process move Y:record; begin 20 Y:=B 1; V(SR) 加工Y P(SM2)： B2:=Y; V(SP); go

16、to M; end; Process print Z:record; begin P:P(SP); Z:=B2; V(SM2) 打印z goto P: end; coend; end; 8、某系統(tǒng)中有10臺(tái)打印機(jī)，有三個(gè)進(jìn)程Pi, P2, P3分別需要8臺(tái)，7臺(tái)和4臺(tái)。若Pi, P2, P3已申請到4臺(tái)，2臺(tái)和2臺(tái)。試問：按銀行家算法能安全分配嗎？請說明分配過程。 答： 系統(tǒng)能為進(jìn)程P3分配二臺(tái)打印機(jī)。因?yàn)楸M管此時(shí)10臺(tái)打印機(jī)已分配給進(jìn)程P1 4臺(tái)，P22 臺(tái)和P34臺(tái)，全部分配完，但P3已分配到所需要的全部4臺(tái)打印機(jī)，它不會(huì)對打印機(jī)再提 出申請，所以它能順利運(yùn)行下去，能釋放占用的4臺(tái)打印機(jī)，

17、使進(jìn)程Pl, P2均可能獲得乘 余的要求4臺(tái)和5臺(tái)，按銀行家算法是安全的。 9、有兩個(gè)用戶進(jìn)程A和B,在運(yùn)行過程中都要使用系統(tǒng)中的一臺(tái)打印機(jī)輸出計(jì)算結(jié)果。 (1) 試說明A、B兩進(jìn)程之間存在什么樣的制約關(guān)系？ (2) 為保證這兩個(gè)進(jìn)程能正確地打印出各自的結(jié)果，請用信號量和P、V操作寫出各自 20 的有關(guān)申請、使用打印機(jī)的代碼。要求給岀信號量的含義和初值。 答： (1) A、B兩進(jìn)程之間存在互斥的制約關(guān)系。因?yàn)榇蛴C(jī)屬于臨界資源，必須一個(gè)進(jìn)程 使用完之后另一個(gè)進(jìn)程才能使用。 (2) mutex：用于互斥的信號量，初值為1。 進(jìn)程A進(jìn)程B P( mutex) 申請打印機(jī) 使用打印機(jī) P( mute

18、x) 申請打印機(jī) 使用打印機(jī) V(mutex) V( mutex) 試以生產(chǎn)者一消費(fèi)者問題說明進(jìn)程同步問題的實(shí)質(zhì)。 答： 一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者和一個(gè)產(chǎn)品之間關(guān)系是典型的進(jìn)程同步問題。設(shè)信號量S為倉庫 內(nèi)產(chǎn)品，P-V操作配對進(jìn)行缺一不可。生產(chǎn)者進(jìn)程將產(chǎn)品放人倉庫后通知消費(fèi)者可用：消 費(fèi)者進(jìn)程在得知倉庫有產(chǎn)品時(shí)取走，然后告訴生產(chǎn)者可繼續(xù)生產(chǎn)。 I 0 .請描述產(chǎn)生死鎖的四個(gè)必要條件。 答： 互斥使用(資源獨(dú)占)一個(gè)資源每次只能給一個(gè)進(jìn)程使用 不可強(qiáng)占(不可剝奪)資源申請者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有 者自愿釋放 請求和保持(部分分配，占有申請)一一個(gè)進(jìn)程在申請新的資源的同時(shí)

19、保持對原有資源的占 有(只有這樣才是動(dòng)態(tài)申請，動(dòng)態(tài)分配) 循環(huán)等待一存在一個(gè)進(jìn)程等待隊(duì)列P1,P2,，Pn,其中P1等待P2占有的資源,P2等待 P3占有的資源，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路 1 1、兩個(gè)并發(fā)執(zhí)行的進(jìn)程A和B的程序如下： 進(jìn)程A Repeat N=N+5: Until false; 進(jìn)程B 20 Repeat 打印N的值： N=0； Until false; 其中N為整數(shù)，初值為4。若進(jìn)程A先執(zhí)行了三個(gè)循環(huán)后，進(jìn)程A和進(jìn)程B又并發(fā)執(zhí) 行了一個(gè)循環(huán)，寫出可能出現(xiàn)的打印值。正確的打印值應(yīng)該是多少？請用P、V操作進(jìn)行管 理，使進(jìn)程A和B并發(fā)執(zhí)行時(shí)不會(huì)岀現(xiàn)與時(shí)間有關(guān)的錯(cuò)

20、誤。 答： 因?yàn)镹初值為4,若進(jìn)程A先執(zhí)行了三個(gè)循環(huán)，此時(shí)N的值為19。當(dāng)進(jìn)程A和進(jìn)程B并 發(fā)執(zhí)行時(shí)可能會(huì)有如下兩種執(zhí)行次序，即進(jìn)程A先執(zhí)行一次循環(huán)，然后再進(jìn)程B執(zhí)行一次 循環(huán)，此時(shí)打印的是正確值24,執(zhí)行后N中的值為0.但若進(jìn)程B先執(zhí)行一次循環(huán)，然后 再進(jìn)程A執(zhí)行一次循環(huán)，則打印的值是19,執(zhí)行后N中的值是5。這是錯(cuò)誤的，即發(fā)生了 與時(shí)間有關(guān)的錯(cuò)誤。用P、V操作進(jìn)行管理，使進(jìn)程A和B并發(fā)時(shí)不會(huì)出現(xiàn)與時(shí)間有關(guān)的 錯(cuò)誤的程序如下：(S為互斥信號:g：,初值為1), 進(jìn)程A Repeat P(S); N=N+5: V(S); Until false; 進(jìn)程B Repeat P(S); 打印N的值：

21、 N=0； V(s)； Until false; 1 2、四個(gè)進(jìn)程P0.P1.P2.P3和四個(gè)信箱M0.M1.M2.M3進(jìn)程間借助相鄰的信箱傳遞消息： 每次從中取岀一條消息，經(jīng)加工送入中。其中M0.M1.M2.M3分別設(shè)有3,322個(gè)格子， 20 每個(gè)格子放一條消息，初始時(shí)，M0裝滿了三條消息，其余為空。寫出使用信號量實(shí)現(xiàn)進(jìn)程 (1=0,1,2,3)同步及互斥的流程。 答： mutexO mutex3 :分別用于控制互斥訪問MO M 3,初值為1 fullO - fulB :分別用于控制同步訪問M0M3,其中fullO初值為3, fulll -full3初值為0, 表示信箱中消息條數(shù)。 emp

22、tyO - empty3 :分別用于同步控制對MO M3的訪問。EmptyO初值為0, empty2- empty3 初值為2, empty 1初值為3,分別用于表示信箱中空格子個(gè)數(shù)。 另用send ( Mi, message )表示將消息送到(Mi mod 4)號信箱中；而用receive ( Mi, message ) 表示接收已存在于(Mi mod 4 )中的消息。 則使用信號量實(shí)現(xiàn)進(jìn)程Pi (i = 0,1 ,2,3 )同步及互斥的流程如下： mutexO , in utex 1. m utex2 , m utex3 : semaphore ; fullO, ful 11 . ful

23、12 , ful 13 : semaphore ; emptyO , em ptyl , em pty2 , em pty3 : semaphore ; begin mutexO : = 1 ; mutex 1 : = 1 ; mutex2 : = 1 ; mutex : = 1 ; fullO : = 3; fulll : = 0; full2 : = 0; full3 : =0; emptyO : = 0 ; empty 1 : = 3 ; empty2 : = 2 ; empty3 : = 2 ; Parbegin P0： begin repeat P ( mutexO ); P ( f

24、ullO); Receive (M0,message); V (emptyO); Processing the message until finished; P( mutex 1 ); P( empty 1 ); Send ( Ml.message ); V( fulll ); 20 V ( mutex 1 ); Until false; end ; Pl： 可類似于PO實(shí)現(xiàn)之; P2： 可類似于PO實(shí)現(xiàn)之; P3： 可類似于PO實(shí)現(xiàn)之; Parend ; End: 1 3、設(shè)系統(tǒng)中僅有一類數(shù)量為M的獨(dú)占型資源，系統(tǒng)中N個(gè)進(jìn)程競爭該類資源，其中各 進(jìn)程對該類資源的最大需求量為W。當(dāng)M、N、W

25、分別取下列值時(shí)，試判斷哪些情況會(huì)發(fā) 生死鎖？為什么？ M=2, N=2, W=1 M=3, N=2, W=2 M=3, N=2, W=3 M=5, N=3, W=2 M=6, N=3, W=3 答： 可能會(huì)發(fā)生死鎖。只要一個(gè)進(jìn)程占用了少于3個(gè)獨(dú)占型資源而另一個(gè)進(jìn)程占用了苴余的獨(dú) 占型資源，兩個(gè)進(jìn)程都會(huì)相互處于等待對方進(jìn)程釋放資源的狀態(tài)。 也可能會(huì)發(fā)生死鎖。當(dāng)每個(gè)進(jìn)程都分配了兩個(gè)資源時(shí)，3個(gè)進(jìn)程都會(huì)彼此等待。 1 4、假泄具有5個(gè)進(jìn)程的進(jìn)程集合P= P0.P1.P2.P3.P4，系統(tǒng)中有三類資源A, B和C。 其中A類資源有10個(gè)，B類資源有5個(gè)，C類資源有7個(gè)。假左在某時(shí)刻有如下狀態(tài)： A A

26、llocation B Max C Available ABC B C A P0 0 1 0 7 5 3 332 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 試給出Need,并說明當(dāng)前系統(tǒng)是否處于安全狀態(tài)，如果是，給岀安全序列。如果不 是，說明理由。 20 答: 當(dāng)前系統(tǒng)處于安全狀態(tài)，安全序列如下求解: work = Available = (3,3,2) 尋找 Ncedj = work = ( 3,3,2 ) ( j = 0,1 , 2,3,4) j= 1 Needl =(1 ,2,3)v = (3,3,2) wor

27、k := (3,3,2 ) + (2 ,0 ,0 ) = (5,3,2) 尋找 Nccdj = work = (5,3,2)(j=0,2,3,4) j = 3 Need3 = (0)v = (5,3,2) work := (5,3,2 ) + (2 4 J ) = (7,4,3) 尋找 Nccdj = work = (7,4,3)(j = 0,2 ,4) j = 4 Need4 = (4,3,1 ) = (7,4,3) work : = (7,4,3 ) + (0,0 ,2) = (7,4,5) 尋找 Nccdj = work = (7,4,5) (j = 0,2 ) j = 2 Need2

28、= (6 ,0 ,0) = (7,4,5) work : = (7,4,5 ) + (3 ,0 ,2 ) = (10,4,7) 尋找 Needj = work = (10.4,7) (j = 0) j = 0 work : = (10,4,7) + (0 J ,0) = (10,5,7) 所以安全序列為o 1 5、有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記。該表中每個(gè)表項(xiàng)代表閱覽室中 的一個(gè)座位。讀者離開時(shí)要消掉英登記信息。閱覽室共有50個(gè)座位。登記表每次僅允許一 位讀者進(jìn)行登記或注銷。讀者登記時(shí)，發(fā)現(xiàn)登記表滿，他在閱覽室外等待，直至有空位再登 記進(jìn)入。試用類Pascal語言和P、V操作,

29、描述讀者行為。 答： Begin initial value of S is 50 Parbegin Begin register P(S)； Register and enter into the reading room ; End; 20 Begin leave off Register off and leave ; V（s）； End; End; 1 6、考慮一個(gè)共有150個(gè)存儲(chǔ)單元的系統(tǒng)，如下分配給三個(gè)進(jìn)程，P1最大需求70,己占 有25： P2最大需求60.己占有40： P3最大需求60.己占有45。使用銀行家算法，以確世 下面的任何一個(gè)請求是否安全。（1）P4進(jìn)程到達(dá)，P4最大

30、需求60,最初請求25個(gè)。（2）P4 進(jìn)程到達(dá)，P4最大需求60,最初請求35。如果安全，找岀所有的安全序列；如果不安全, 給出結(jié)果分配情況。 答： （1）由于系統(tǒng)目前還有150-25-40-45=40個(gè)單元，P4進(jìn)程到達(dá)，把25個(gè)單元分給它。這 時(shí)系統(tǒng)還余15個(gè)單元，可把15個(gè)單元分給P3,它執(zhí)行完后會(huì)釋放60個(gè)單元。于 是可供P1（還要45個(gè)單元），P2（還要20個(gè)單元），P4（還要35個(gè)單元）任何一個(gè)執(zhí)行。 安全序列為： P1, P2, P3, P4, P3, P1, P2, P4 PI, P2, P3, P4, P3, P1, P4, P2 P1, P2, P3, P4, P3, P2

31、, P1, P4 P1, P2, P3, P4, P3, P2, P4, Pl P1, P2, P3, P4, P3 P4, Ph P2 P1, P2, P3, P4, P3, P4, P2, Pl （2） P4進(jìn)程到達(dá)，P4最大需求60,最初請求35。如果把35個(gè)單元分給P4,系統(tǒng)還余5 個(gè)單元，不再能滿足任何一個(gè)進(jìn)程的需求，系統(tǒng)進(jìn)入不安全狀態(tài)。 1 7、在一個(gè)盒子里，混裝了數(shù)量相等的黑白用棋子?，F(xiàn)在用自動(dòng)分揀系統(tǒng)把黑子、白子分 開，設(shè)分揀系統(tǒng)有二個(gè)進(jìn)程P1和P2,英中P1揀白子：P2揀黑子。規(guī)左每個(gè)進(jìn)程每次揀一 子；當(dāng)一個(gè)進(jìn)程在揀時(shí)，不允許另一個(gè)進(jìn)程去揀：當(dāng)一個(gè)進(jìn)程揀了一子時(shí)，必須讓另一個(gè)

32、進(jìn) 程去揀。試寫出兩進(jìn)程P1和P2能并發(fā)正確執(zhí)行的程序。 答： 實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問題，設(shè)信號量S1和S2分別表示可揀白子和黑子，不失一般性, 若令先揀白子。 20 var SLS2:semaphore; Sl:=l;S2:=0; cobegin process Pl begin repeat P(S1)； 揀白子 V(S2); until false; end process P2 begin repeat P(S2); 揀黑子 V(S1); until false; end cocnd. 1 8.系統(tǒng)有A、B、C、D共4種資源，在某時(shí)刻進(jìn)程PO、Pl. P2. P3和P4對資源的占 有

33、和需求情況如表，試解答下列問題： Process Allocation Claim Available A B C D A B C D A B C D P（） 0 03 2 00 4 4 16 2 2 20 P1 10 0 0 27 5 0 P2 135 4 3 610 10 P3 0 33 2 0 9 84 P4 0 01 4 0 6 6 10 (1) 系統(tǒng)此時(shí)處于安全狀態(tài)嗎？為什么？ (2) 若此時(shí)P2發(fā)岀request 1(1. 2、2、2),系統(tǒng)能分配資源給它嗎？為什么？ 答： (1) 系統(tǒng)處于安全狀態(tài)，存在安全序列： PO,P3,P4,Pl,P2 PO,P3,Pl,P4,P2 PO,P3,Pl,P2,P4 (2) 不能分配，否則系統(tǒng)會(huì)處于不安全狀態(tài)。 1 9、假設(shè)有32個(gè)存儲(chǔ)區(qū)域，英編號為0, 1,，31,用一個(gè)32位的標(biāo)志字，位號也是 0, 1,31,分別描述32個(gè)存儲(chǔ)區(qū)域使用狀態(tài)：當(dāng)某一位