計算機學(xué)科專業(yè)基礎(chǔ)綜合計算機操作系統(tǒng)

1、計算機學(xué)科專業(yè)基礎(chǔ)綜合計算機操作系統(tǒng)-8(總分:99.99,做題時間：90分鐘)一、綜合應(yīng)用題(總題數(shù)：25，分?jǐn)?shù)：100.00)A和B兩個程序，程序A順序執(zhí)行情況如下：計算20s，使用設(shè)備10s，計算10s，使用設(shè)備20s，計算 10s；程序B順序執(zhí)行情況如下：使用設(shè)備20s，計算20s，使用設(shè)備10s，計算10s，使用設(shè)備20s。比較 單道和多道程序(不考慮管理開銷，設(shè)備和CPU都必須互斥使用)情況下CPU和設(shè)備各自的利用率是多少？(分?jǐn)?shù)：4.00)單道程序情況下，CPU和設(shè)備利用率均為多道程序情況下，CPU和設(shè)備利用率均為什么是內(nèi)核支持線程和用戶級線程?并對它們進行比較。(分?jǐn)?shù)：4.00

2、) 內(nèi)核支持線程是在內(nèi)核支持下實現(xiàn)的，即每個線程的線程控制塊設(shè)置在內(nèi)核中，所有對線程的操作(如創(chuàng)建、 撤銷和切換等)，都是通過系統(tǒng)功能調(diào)用由內(nèi)核中的相應(yīng)處理程序完成。而用戶級線程僅存在于用戶空間中， 即每個線程的控制塊設(shè)置在用戶空間中，所有對線程的操作也在用戶空間中完成，而無需內(nèi)核的幫助?？蓮囊韵聨讉€方面比較內(nèi)核支持線程和用戶級線程：內(nèi)核支持。用戶級線程可在一個不支持線程的OS中實現(xiàn)，而內(nèi)核支持線程則不然，它需要得到OS內(nèi)核 的支持。處理器的分配。在多處理機環(huán)境下，對純粹的用戶級線程來說，內(nèi)核一次只為一個進程分配一個處理機， 即進程無法享用多處理機帶來的好處。而在設(shè)置有內(nèi)核支持線程時，內(nèi)核可調(diào)

3、度一個應(yīng)用中的多個線程同 時在多個處理機上并行運行，從而提高程序的執(zhí)行速度和效率。調(diào)度和線程執(zhí)行時間。對設(shè)置有內(nèi)核支持線程的系統(tǒng)，其調(diào)度方式和算法與進程的調(diào)度相似，只不過調(diào) 度的單位是線程。而對只設(shè)置了用戶級線程的系統(tǒng)，調(diào)度的單位則仍為進程。因此，在條件相同的情況下， 內(nèi)核支持的線程通常比用戶級線程得到更多的CPU執(zhí)行時間。切換速度。用戶級線程的切換，通常發(fā)生在一個應(yīng)用程序的多個線程之間，由于不需陷入內(nèi)核，而且切 換的規(guī)則也相當(dāng)簡單，因此切換速度比內(nèi)核支持線程至少快一個數(shù)量級。系統(tǒng)調(diào)用。在典型的OS中，許多系統(tǒng)調(diào)用都會引起阻塞。當(dāng)一個用戶級線程執(zhí)行這些系統(tǒng)調(diào)用時，被 阻塞的將是整個進程。而當(dāng)一

4、個內(nèi)核支持線程執(zhí)行這些系統(tǒng)調(diào)用時，內(nèi)核只阻塞這個線程，但仍可調(diào)度其 所屬進程的其他線程執(zhí)行。什么是線程?進程和線程是什么關(guān)系？(分?jǐn)?shù)：4.00) 線程可定義為進程內(nèi)的一個執(zhí)行單位，或者定義為進程內(nèi)的一個可調(diào)度的實體。在具有多線程機制的操作系統(tǒng)中，處理機調(diào)度的基本單位不是進程而是線程。一個進程可以有多個線程， 而且至少有一個可執(zhí)行的線程。進程和線程的關(guān)系是：線程是進程的一個組成部分；進程的多線程都在進程的地址空間活動；資源是分給進程的，而不是分給線程的，線程在執(zhí)行中需要資源時，系統(tǒng)從進程的資源配額中扣除并分 配給它；處理機調(diào)度的基本單位是線程，線程之間競爭處理機，真正在處理機上運行的是線程；線程

5、在執(zhí)行過程中，需要同步。進程和程序之間可以形成一對一、一對多、多對一、多對多的關(guān)系，請分別舉例說明在什么情況下會形 成這樣的關(guān)系。(分?jǐn)?shù)：4.00)執(zhí)行一條命令或一個應(yīng)用程序時，進程和程序之間形成一對一的關(guān)系；進程在執(zhí)行過程中可以加載執(zhí)行不 同的應(yīng)用程序，從而形成一對多的關(guān)系；當(dāng)以不同的參數(shù)或數(shù)據(jù)多次執(zhí)行同一個應(yīng)用程序時，形成多對一 的關(guān)系；當(dāng)并發(fā)地執(zhí)行不同的應(yīng)用程序時，形成多對多的關(guān)系。解析從進程的概念、進程與程序之間 的關(guān)系來考慮問題的解答。進程是程序的執(zhí)行過程，進程代表執(zhí)行中的程序，因此進程與程序的差別就隱 含在“執(zhí)行”之中。程序是靜態(tài)的指令集合，進程是程序的動態(tài)執(zhí)行過程。靜態(tài)的程序除占

6、用磁盤空間外， 不需要其他系統(tǒng)資源，只有執(zhí)行中的進程才需要分配內(nèi)存、CPU等系統(tǒng)資源。進程的定義說明了兩點：進程與程序相關(guān)，進程包含了程序。程序是進程的核心內(nèi)容，沒有程序就沒有進程。進程不僅僅是程序，還包含了程序在執(zhí)行過程中使用的全部資源，沒有資源程序就無法執(zhí)行，因此。進 程是執(zhí)行程序的載體。當(dāng)運行一個程序時，操作系統(tǒng)首先要創(chuàng)建一個進程，為進程分配內(nèi)存等資源，然后將程序加載到進程中執(zhí) 行。就單個進程某個時刻而言，一個進程只能執(zhí)行一個程序，進程和程序之間是一對一的關(guān)系。但從整個 系統(tǒng)中的進程集合以及進程的生命周期而言，進程和程序之間可以形成一對一、一對多、多對一、多對多 的關(guān)系。為什么進程之間的

7、通信必須借助于操作系統(tǒng)內(nèi)核功能?簡單說明進程通信的幾種主要方式。(分?jǐn)?shù)：4.00) 每個進程有自己獨立的地址空間。在操作系統(tǒng)和硬件的地址保護機制下，進程無法訪問其他進程的地址空 間，所以必須借助于操作系統(tǒng)的系統(tǒng)調(diào)用函數(shù)實現(xiàn)進程之間的通信。進程通信的主要方式有：共享內(nèi)存區(qū)：通過系統(tǒng)調(diào)用創(chuàng)建共享內(nèi)存區(qū)。多個進程可以(通過系統(tǒng)調(diào)用)連接同一個共享內(nèi)存區(qū)，通 過訪問共享內(nèi)存區(qū)實現(xiàn)進程之間的數(shù)據(jù)交換。使用共享內(nèi)存區(qū)時需要利用信號量解決同步互斥問題。消息傳遞：通過發(fā)送/接收消息系統(tǒng)調(diào)用實現(xiàn)進程之間的通信。當(dāng)進程發(fā)送消息時，系統(tǒng)將消息從用戶 緩沖區(qū)拷貝到內(nèi)核中的消息緩沖區(qū)中，然后將消息緩沖區(qū)掛入消息隊列中。

8、進程發(fā)送的消息保持在消息隊 列中直到被另一進程接收。當(dāng)進程接收消息時，系統(tǒng)從消息隊列中解掛消息緩沖區(qū)，將消息從內(nèi)核的消息 緩沖區(qū)中拷貝到用戶緩沖區(qū)，然后釋放消息緩沖區(qū)。管道通信：管道是一個先進先出(FIFO)的信息流，允許多個進程向管道寫入數(shù)據(jù)，允許多個進程從管道 讀出數(shù)據(jù)。在讀/寫過程中，操作系統(tǒng)保證數(shù)據(jù)的寫入順序與讀出順序是一致的。進程通過讀/寫管道文件 或管道設(shè)備實現(xiàn)彼此之間的通信。共享文件：利用操作系統(tǒng)提供的文件共享功能實現(xiàn)進程之間的通信。這時，也需要利用信號量解決文件 共享操作中的同步互斥問題。解析在操作系統(tǒng)中，進程是競爭和分配計算機系統(tǒng)資源的基本單位。每 個進程有自己獨立的地址空間

9、。為了保證多個進程能夠彼此互不干擾地共享物理內(nèi)存，操作系統(tǒng)利用硬件 地址機制對進程的地址空間進行了嚴(yán)格的保護，限制每個進程只能訪問自己的地址空間。線程和進程有什么區(qū)別?舉例說明它們分別適用的系統(tǒng)環(huán)境。(分?jǐn)?shù)：4.00) 進程是程序的執(zhí)行過程，是競爭和分配計算機系統(tǒng)資源的基本單位。線程是進程中的一個程序執(zhí)行單元。 一個進程可以包含多個線程，進程中的程序可以由多個線程并發(fā)地執(zhí)行，因此線程是進程中的并發(fā)執(zhí)行機 制。進程中的多個線程共享進程的地址空間和其他資源。線程和進程之間的最大區(qū)別是它們的運行、管理 和通信開銷。創(chuàng)建進程需要建立進程的地址空間，而線程不需要，因為它共享進程的地址空間。在處理機 調(diào)度

10、過程中，進程切換包括切換CPU執(zhí)行現(xiàn)場和進程地址空間，而同一進程下的線程切換只需要切換CPU 執(zhí)行現(xiàn)場。由于共享進程的地址空間，同一進程下的線程之間可以直接進行數(shù)據(jù)交換，不需要調(diào)用操作系 統(tǒng)的內(nèi)核通信函數(shù)。多線程并行程序適用于共享存儲結(jié)構(gòu)的多處理機系統(tǒng)(SMP)，因為這類系統(tǒng)能夠很好地支持線程對進程地址 空間和資源的物理共享，而多進程并行程序適用于松散耦合的多處理機系統(tǒng)。解析需要了解和掌握線 程、進程的基本概念以及它們之間的關(guān)系。操作系統(tǒng)為了支持多道程序的運行和管理，引入了進程概念和 進程管理機制。為了加快應(yīng)用程序的執(zhí)行速度，提出了并行程序的設(shè)計思想。將一個大的應(yīng)用程序或大作 業(yè)分解成若干個能

11、夠并行處理的子任務(wù)，由執(zhí)行主程序的進程創(chuàng)建多個子進程，每個子進程執(zhí)行一個子任 務(wù)。利用進程的并發(fā)性，使得多個子進程的I/O過程與CPU計算過程相互重疊，從而提高處理機利用率， 加快應(yīng)用程序的運行速度。在多處理機系統(tǒng)中，為了進一步提高并行程序的運行效率。引入了線程概念和線程管理機制。線程是進程 中的一個程序執(zhí)行單元。線程包含CPU執(zhí)行線程和執(zhí)行堆棧，可以獨立地執(zhí)行程序。進程中的程序可以由 多個線程并發(fā)地執(zhí)行，進程中的多個線程共享進程的地址空間和其他資源，包括程序、數(shù)據(jù)、文件、通信 端口等。正是由于線程對進程的地址空間和資源的共享，明顯地減少了并行開銷（包括線程創(chuàng)建、切換和通 信），非常有利于并行

12、程序的開發(fā)和運行。下面的進程狀態(tài)轉(zhuǎn)換可能發(fā)生嗎?為什么？阻塞一運行；就緒一阻塞；就緒一退出。（分?jǐn)?shù)：4.00） 阻塞到運行狀態(tài)是不可能的，因為必須經(jīng)就緒狀態(tài)；就緒到阻塞狀態(tài)是不可能的；就緒到退出狀態(tài)也是不 可能的，中間必須經(jīng)過執(zhí)行狀態(tài)。Windows XP采用了動態(tài)優(yōu)先級的調(diào)度算法對下面的進程的優(yōu)先級進行提高。試分析這樣做的原因和結(jié)果， 由此說明Windows XP的調(diào)度策略。完成I/O操作的進程；信號量或事件等待結(jié)束的進程；前臺進程（線程）完成一個等待操作；由于窗口活動而被喚醒的應(yīng)用程序進程；進程（線程）在就緒隊列中的等待時間過長。（分?jǐn)?shù)：4.00） 第1種情況是因為進程完成I/O后，需要提

13、高優(yōu)先級，這是一種照顧I/O為主進程的策略；后4種情況均 是因為它們長時間沒有得到運行的機會，需要提高優(yōu)先級，這是一種典型的動態(tài)優(yōu)先級策略。實現(xiàn)多進程并行程序的好處是什么？多線程并行程序?qū)τ诙噙M程并行程序有哪些優(yōu)勢？原因是什么？（分?jǐn)?shù)：4.00） 線程并行相對于進程并行可以降低上下文的切換開銷。為什么說ULT不能實現(xiàn)在多個CPU上的真正并行，而混合實現(xiàn)線程則可以?（分?jǐn)?shù)：4.00） 多CPU的調(diào)度依賴于操作系統(tǒng)內(nèi)核的調(diào)度，而ULT不能影響操作系統(tǒng)的調(diào)度策略，因此不能實現(xiàn)真正的并 行。在多處埋機調(diào)度中，為什么需要讓進程中的多個線程同時被調(diào)度執(zhí)行？（分?jǐn)?shù)：4.00） 提高并行執(zhí)行的程度。設(shè)系統(tǒng)中有

14、下述解決死鎖的辦法：銀行家算法；檢測死鎖，終止處于死鎖狀態(tài)的進程，釋放該進程所占有的資源；資源預(yù)分配。簡述哪種辦法允許最大的并發(fā)性，也即哪種辦法允許更多的進程無等待地向前推進?請按“并發(fā)性”從大到 小的順序?qū)ι鲜?種辦法進行排序。（分?jǐn)?shù)：4.00） 死鎖檢測方法可以獲得最大并發(fā)性。并發(fā)性排序：死鎖檢測方法、銀行家算法、資源預(yù)分配法。什么是饑餓?死鎖和饑餓的主要差別是什么？（分?jǐn)?shù)：4.00）饑餓是系統(tǒng)并沒有死鎖，但至少有一個進程被無限期地推遲的現(xiàn)象。饑餓不同于死鎖。死鎖是這樣一種情 形：其中某進程正等待一個絕不會發(fā)生的事件；而饑餓現(xiàn)象是指某進程正等待這樣一個事件：它發(fā)生了但 總是受到其他進程的影

15、響，以致一直輪不到(或很難輪到)該進程。假設(shè)某操作系統(tǒng)采用RR調(diào)度策略，分配給A類進程的時間片為100ms，分配給B類進程的時間片為400ms， 就緒進程隊列的平均長度為5(包括正在運行的進程)，其中A類進程有4個，B類進程有1個，所有進程的 平均服務(wù)時間為2s，問A類進程和B類進程的平均周轉(zhuǎn)時間各為多少？(不考慮I/O情況)。(分?jǐn)?shù)：4.00) 因為就像進程隊列的平均長度為5,單個RR調(diào)度循環(huán)周期的時間為：4X100+1X400=800(ms)A類進程需要20個時間片的執(zhí)行時間，B類進程需要5個時間片的執(zhí)行時間(1s=1000ms)。A類進程的平均 周轉(zhuǎn)時間為：20X0.8=16(s)B類進

16、程的平均周轉(zhuǎn)時間為：5X0.8=4(s)解析時間片輪轉(zhuǎn)調(diào)度(RR)是輪流地調(diào)度就緒隊列中的每個進 程，進程每次占用CPU的時間長度限制為時間片的大小。當(dāng)采用固定的時間片大小時，每個進程按照固定 周期被循環(huán)地執(zhí)行。所以，進程的執(zhí)行速度是由該進程的時間片大小在一個循環(huán)周期中所占的比例決定的， 比例越高，進程的相對執(zhí)行速度就越快。某多道程序設(shè)計系統(tǒng)中配有一臺處理器CPU和兩臺輸入/輸出設(shè)備IO 、IO 2，現(xiàn)有優(yōu)先級由高到低 的3個進程P 、P 2、P 3同時存在，它們使用資源的先后順序和占用時間分別是：進程 P 1 : IO 2 (30ms)，CPU(10ms)，IO 1 (30ms)，CPU(1

17、0ms)，IO 2 (10ms)。進程 P 2 : IO 2 (20ms)，CPU(20ms)，IO 1 (40ms)。進程 P : CPU(30ms)，IO (20ms)。若進程調(diào)度采用“可搶占的最高優(yōu)先級”調(diào)度算法，且忽略調(diào)度等所需的時間，請回答下列問題：進程P 、P 2、P 3從開始到完成所用的時間分別是多少？(要求用坐標(biāo)畫出進程P 1 P 2、P 3的工作過程，其中橫坐標(biāo)表示時間，縱坐標(biāo)表示CPU和I/O設(shè)備)。123這三個進程從開始到全部完成時CPU的利用率為多少？IO 、IO 2的利用率為多少？(分?jǐn)?shù)：4.00)123進程P 、P 2、P 3從開始到完成所用的時間分別是90ms、1

18、10ms、80ms。這三個進程從開始到全部完成 時的時間為110ms，在此期間內(nèi)：CPU 的利用率=(30+20+10+10) 110=63.3%IO 的利用率=(20+30+40) 110=81.8%IO 2的利用率=(30+20+10) 110=54.5% 解析在“可搶占的最高優(yōu)先級”調(diào)度中，任何時刻內(nèi)核都將處 理機分配給當(dāng)前最高優(yōu)先級的就緒進程。也就是說，只有當(dāng)高優(yōu)先級進程主動放棄CPU時，低優(yōu)先級進程才有機會運行，并且，一旦高優(yōu)先級進程需要使用CPU時，內(nèi)核就會剝奪低優(yōu)先級進程的CPU，分配給它 使用。在本題中，由于進程P 1和P 2在開始執(zhí)行時先需要進行I/O,所以最低優(yōu)先級的進程P

19、 3獲得了 CPU。但 是，P 3運行了 20ms后就被/2搶占了 CPU，因為P 2剛好完成了 I/O,并且P 2的優(yōu)先級大于P 3。同 樣的原因，P 2運行了 10ms后，就被P 1搶占了 CPU。P 1在CPU上運行10ms之后再次需要進行I/O而放 棄cpu，于是:P 2、P 獲得繼續(xù)運行的機會。以此方式，P 1、P 2和？ 3相繼完成自己的運行過程。許多操作系統(tǒng)采用動態(tài)優(yōu)先級調(diào)度算法，即當(dāng)一個“阻塞”進程變成“就緒”時提高該進程的優(yōu)先級。為什么采用這種方法？(分?jǐn)?shù)：4.00) 進程進入“阻塞”狀態(tài)，是因為進程需要等待某種資源。當(dāng)進程獲得資源時，進程被喚醒，變成“就緒” 狀態(tài)。這時提高

20、該進程的優(yōu)先級可以使進程盡快地完成慢速設(shè)備的I/O過程。這樣，一方面提高了 I/O設(shè) 備的利用率，另一方面，設(shè)備的I/O活動能夠與CPU執(zhí)行其他進程的計算工作充分地并行，從而提高整個 系統(tǒng)的性能。解析在操作系統(tǒng)中，多個進程共享系統(tǒng)的資源必然發(fā)生資源的競爭。進程在運行過程中， 如果需要使用的資源（如I/O設(shè)備）正被其他進程占用，該進程就會進入“阻塞”狀態(tài)，等待資源的釋放。 如果某種資源的使用時間比較長（例如慢速的I/O設(shè)備），就會發(fā)生許多進程等待該資源的情況，而CPU時 常處于空閑狀態(tài)。這時，慢速的I/O設(shè)備成為阻礙系統(tǒng)性能的瓶頸。提高設(shè)備的利用率和提高設(shè)備與CPU 的并行度是解決瓶頸問題的方法

21、之一。論述一下解決雙進程臨界區(qū)問題的軟件算法是錯誤的。Process P0:do flag0=true; while（flag1）;臨界區(qū)Flag0=false; while（1）;Process P1:do flag1=true; while（flag0）;臨界區(qū)Flag1=false; while（1）;（分?jǐn)?shù)：4.00） 通過使用標(biāo)志牌flag0和flag1能夠保證滿足“互斥”條件。但是，當(dāng)兩個進程按照的順序執(zhí) 行程序時，它們各自舉起標(biāo)志牌，同時都因為觀察到對方也舉起了標(biāo)志牌而等待在while語句中。由于兩 個進程都不會放下自己的標(biāo)志牌，因此都無法進入臨界區(qū)，不能滿足“有限等待”的條件。

22、所以，上述解 決雙進程臨界區(qū)問題的算法是錯誤的。解析在算法中，兩個進程P和P各自擁有自己的標(biāo)志牌flag012和flag1。當(dāng)進程需要進入臨界區(qū)時，舉起標(biāo)志牌（設(shè)置值為true）。然后觀察對方是否舉起標(biāo)志牌，是 則等待并繼續(xù)觀察（while語句），直到對方放下標(biāo)志牌（設(shè)置值為false）。這時，進程才進入臨界區(qū)。進程 退出臨界區(qū)時，放下標(biāo)志牌（設(shè)置值為false）。在具有N個進程的系統(tǒng)中，允許M個進程（NNMN1）同時進入他們的共享區(qū)，其信號量s的值的變化范 圍是1，處于等待狀態(tài)的進程數(shù)最多是2個。（分?jǐn)?shù)：4.00）（M-N，M）； N-M。解析信號量s及其P操作、V操作具有資源管理的內(nèi)涵：s

23、0：表示有s個資源可用。s=0：表示無資源可用。s0：表示有| s|個進程在等待資源。P（s）:表示申請一個資源。V（s）:表示釋放一個資源。信號量必須置一次且只能置一次初值?；コ庑盘柫康某踔禐?，同步信號量的初值為0，代表多個資源的信 號量的初值為正整數(shù)，即為可用的資源總數(shù)。在本題中，允許M個進程同時進入它們的共享區(qū)，可以看作有M個可用的資源總數(shù)。信號量s的最大值是 可用資源總數(shù)M，最小值是當(dāng)N個進程都需要使用共享區(qū)時的值，這時有| M-N|個進程需要等待進入共享區(qū)。有3個并發(fā)進程通過使用緩沖區(qū)buf1、buf2以及信號量none1、nonf1、none2、nonf2，協(xié)作完成如圖 所示的任

24、務(wù)，buf1、buf2的大小分別為n1、n2，S1和S2的初值都為1。這3個進程的程序如下，試補充完整（初值：none1=none2=0； nonf1=n1，nonf2=n2）。輸入進程：While （1） _mP(s1);輸入一個字符到bufl;V(sl);=；加工進程：While (1) P(nonel);從bufl中取一個字符到ch;_$=;V(nonfl);P(nonf2);P(s2);ch 送 buf2;V(s2);V(none2);輸出進程：while (1) ;從buf2取一個字符到打印口 ;=;(分?jǐn)?shù)：4.00)P(nonf1)V(none1)P(s1)V(s1)P(none2

25、)P(s2)V(s2)V(nonf2)解析信號量及其P操作、V操作是解決同步、互斥問題的常 用方法。在應(yīng)用信號量時必須注意兩點：對信號量只能執(zhí)行P操作、V操作，且P操作、V操作必須成對出現(xiàn)：當(dāng)實現(xiàn)互斥時，它們出現(xiàn)在同一 進程中；當(dāng)實現(xiàn)同步時，則出現(xiàn)在不同的進程中。同步P操作與互斥P操作在一起時，同步P操作應(yīng)該放在互斥P操作之前。本題是一個生產(chǎn)/消費者類型的同步互斥問題。有兩組生產(chǎn)者和消費者，利用不同的緩沖區(qū)進行操作。第1 組生產(chǎn)者和消費者是輸入進程和加工進程，第2組生產(chǎn)者和消費者是加工進程和輸出進程。在生產(chǎn)者進程 與消費者進程之間存在一種同步關(guān)系：生產(chǎn)者不能往“滿”的緩沖區(qū)中放產(chǎn)品，必須等待消

26、費者取走產(chǎn)品 之后(第1個同步點)；消費者亦不能從“空”的緩沖區(qū)中取產(chǎn)品，必須等待生產(chǎn)者放入產(chǎn)品之扁第2個同 步點)。也就是說，在生產(chǎn)者和消費者的程序中，需要使用兩個信號量實現(xiàn)上述兩個同步點。另外，還需要 實現(xiàn)對緩沖區(qū)buf 1和buf2互斥訪問。從列出的程序中可以看出，信號量s1和s2分別用于實現(xiàn)對緩沖區(qū)buf 1和buf2互斥訪問；none1和nonf1 用于實現(xiàn)輸入進程和加工進程之間的同步，none2和nonf1用于實現(xiàn)加工進程和輸出進程之間的同步。在一個倉庫中可以存放A和B兩種產(chǎn)品，但要求：每次只能存入一種產(chǎn)品(A或B)；A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量M；B產(chǎn)品數(shù)量-A產(chǎn)品數(shù)量N；其中，M、N

27、是正整數(shù)，試用P操作、V操作描述產(chǎn)品A與產(chǎn)品B的入庫過程。(分?jǐn)?shù)：4.00)產(chǎn)品A與產(chǎn)品B的入庫過程如下：Semaphore:Sa,Sb,mutex;Sa=m-1;Sb=n-1;mutex=1;process_A() While(1) P(Sa);P(mutex);A產(chǎn)品入庫；V(mutex);V(Sb);Process_B() While(1) P(Sb);P(mutex);B產(chǎn)品入庫；V(mutex);V(Sa);解析這也是一個生產(chǎn)/消費者類型的同步互斥問題。這里有兩個生產(chǎn)者：生產(chǎn)者A放入產(chǎn)品A,生產(chǎn) 者B放入產(chǎn)品B，但沒有或不考慮消費者。根據(jù)本題所給的條件，找出生產(chǎn)者A、B之間的相互制約

28、關(guān)系。 條件1：生產(chǎn)者A和B必須互斥地使用倉庫。條件2：若只放入A產(chǎn)品，而不放入B產(chǎn)品，則A產(chǎn)品最多可放M-1次便被阻塞。即表示可放入A產(chǎn)品數(shù) 目的計數(shù)器初值為M-1，A進程每放入一個產(chǎn)品就應(yīng)當(dāng)將計數(shù)器減1，當(dāng)計數(shù)器值為0時，進程A被阻塞; 每當(dāng)放入一個B產(chǎn)品，則可令A(yù)產(chǎn)品的計數(shù)器增1，表明A進程可以多一次放入產(chǎn)品的機會。條件3：若只放入B產(chǎn)品，而不放入A產(chǎn)品，則B產(chǎn)品最多可放N-1次便被阻塞。即表示可放入B產(chǎn)品數(shù) 目的計數(shù)器初值為N-1，B進程每放入一個產(chǎn)品就應(yīng)當(dāng)將計數(shù)器減1，當(dāng)計數(shù)器值為0時，進程B被阻塞; 每當(dāng)放入一個A產(chǎn)品，則可令B產(chǎn)品的計數(shù)器增1，表明B進程可以多一次放入產(chǎn)品的機會。

29、因此，需要使用信號量mutex控制兩個進程互斥訪問臨界資源(倉庫)。使用同步信號量Sa和Sb(分別代表 產(chǎn)品A和產(chǎn)品B的入庫計數(shù)器)滿足條件2和條件3。今有一個文件P供多個進程共享，現(xiàn)把這些進程分成A、B兩組，規(guī)定同組進程可以同時讀文件P，但 當(dāng)有A組(或B組)進程在讀文件P時，就不允許B組(或A組)進程讀文件P。試用C語言實現(xiàn)兩組進程的 讀文件過程。(分?jǐn)?shù)：4.00) 程序示意如下：Semaphore:S1,S2,mutex;int:num1,num2;S1=1;S2=1;mutex=1;num1=0;num2=0;Process_A() P(S1);num1=num1+1;if(num1=

30、1) then P(mutex);V(S1);讀文件P;P(S1);num1=num1-1;if(num1=0) then V(mutex);V(S1);Process_B() P(S2);Num2=num2+1;if(num2=1) then P(mutex);V(S2);讀文件P;P(S2);Num2=num2-1;if(num2=0) then V(mutex);V(S2);解析這是一個讀者/寫者類型的同步互斥問題。有A、B兩組讀者，但沒有寫者。兩組讀者相互競爭對 文件P的讀權(quán)限，而讀權(quán)限在同組進程之間是共享的，因此，在到達臨界區(qū)(即“讀文件P”)的同組進程 中，由第一個到達進程負(fù)責(zé)競爭

31、臨界區(qū)的入場券(即“讀權(quán)限”)，由最后一個離開進程負(fù)責(zé)釋放臨界區(qū)的 入場券。因此需要使用一個互斥信號量mutex，實現(xiàn)A、B兩組讀者互斥地進入臨界區(qū)。為了確定第一個到達的進程和最后一個離開的進程，需要定義兩個計數(shù)器num 1和num2,分別記錄A組和B 組中需要或正在讀文件P的進程數(shù)。計數(shù)器在同組進程之間是共享資源，需要互斥地訪問。因此，每組進 程需要使用一個互斥信號量(S1、S2)，保證對計數(shù)器進行正確的并發(fā)操作。有座東西方向架設(shè)、可雙向通行的單車道簡易橋，最大載重負(fù)荷為4輛汽年。請定義合適的信號量，正 確使用P操作、V操作，實現(xiàn)雙向車輛的過橋過程。(分?jǐn)?shù)：4.00) 設(shè)置4個信號量：S：代

32、表橋的互斥使用的信號量，初值為1；Scounteast :代表由東向西方向的車輛計數(shù)器的互斥使用的信號量，初值為1； Scountwest :代表由西向東方向的車輛計數(shù)器的互斥使用的信號量，初值為1； Scount4：代表橋上車輛計數(shù)器的信號量，初值為4。算法如下：Semaphore:S,Scounteast,Scountwest,Scount4;int Counteast,Countwest;S=1;Scounteast=1;Scountwest=1;Scount4=4;Counteast=0;Countwest=0;Program_east() P(Scounteast);if(Count

33、east=0) then P(S);Counteast=Counteast+1;V(Scounteast);P(Scount4);過橋:V(Scount4);P(Scounteast);Counteast=Counteast-1;if(Counteast=0) then V(S);V(Scounteast);Program_west() P(Scountwest);if(Countwest=0) then P(S);Countwest=Countwest+1;V(Scountwest);P(Scount4);過橋：V(Scount4);P(Scountwest);Countwest=Count

34、west-1;if(Countwest=0) then V(S);V(Scountwest);解析這也是一個讀者/寫者類型的同步互斥問題。有兩組讀者或?qū)懻撸簭臇|向西的車流和從西向東的 車流。共享的資源是可雙向通行的單車道簡易橋，即雙向過橋的車輛對橋的使用是互斥的，同方向上允許 有多輛車輛同時過橋，但是同時過橋的車輛數(shù)目不能大于4輛。因此，可以按照通常的讀者/寫者問題進行 處理，但在同組讀者使用資源的過程中需要增加信號量的控制，以滿足最大載重負(fù)荷為4輛汽車的條件。若系統(tǒng)中有5臺繪圖儀，有多個進程均需要使用2臺，規(guī)定每個進程一次僅允許申請1臺，則至多允許 多少個進程參與競爭而不會發(fā)生死鎖？(分?jǐn)?shù)：

35、4.00) 在資源分配系統(tǒng)中，死鎖發(fā)生的原因是因為多個進程共享優(yōu)先的獨占型資源。當(dāng)多個進程占有了部分資源 又需要更多的資源時，就可能形成循環(huán)等待鏈而導(dǎo)致死鎖。假設(shè)系統(tǒng)中的某種資源的個數(shù)為M，共享該資源的進程數(shù)為N，每個進程對該資源的最大需求量為X。最極 端的資源分配情況是，每個進程都巳經(jīng)占有了 X-1個資源，同時都需要再分配一個資源。這時，如果要保 證不發(fā)生死鎖，系統(tǒng)中必須至少還有一個可分配的資源。即M滿足下面的關(guān)系式：MNN(X-1)+1因此，保證系統(tǒng)不會發(fā)生死鎖的最小M值可以從下面的公式獲得：M=N(X-1)+1將M=5, X=2代入公式，可得N=4。即至多允許出現(xiàn)4個進程參與資源競爭。首

36、先計算每個進程的剩余需求量，也就是在占有部分資源的基礎(chǔ)上還需要多少資源。列表如下:然后，分別計算系統(tǒng)現(xiàn)有的資源量能否滿足進程P 1 (P2或P 3 )的當(dāng)前請求量以及滿足之后的安全序列。 P 1的申請被阻塞。因為滿足了 P 1的申請之后，P 1的剩余需求量為(0，1，3)，而系統(tǒng)的剩余資源量為 (0，1，2)，無法繼續(xù)滿足任何進程的剩余需求量，因此不存在安全序列。P 2的申請被阻塞。因為申請數(shù)量超出了系統(tǒng)現(xiàn)有的資源數(shù)量。p 3的申請可以滿足。因為滿足了 p 3的申請之后，p 3的剩余需求量為(0，1，1)，而系統(tǒng)的剩余資源量 為3(0，1，1)，可以繼續(xù)滿足P 3的剩余需求量?？梢杂嬎愠霭踩蛄蠵 3，P 2，P 1或寸3，P 1， P 2。解析在分配資源時確保系統(tǒng)處于安全狀態(tài)，這是一種保守的死鎖避免方法。銀行家算法就是這樣一種資源分配方法。算法的基本思想是：在分配資源時，檢查系統(tǒng)中是否存在一個安全序列P ，P12，Pn，使得系統(tǒng)按照這個序列分配現(xiàn)有的資源，可以保證所有進程Pi能夠運行結(jié)束。也就是說， 用系統(tǒng)現(xiàn)有的資源滿足P 1的全部資源需求，使得P 1能夠運行結(jié)束并釋放所占用的資源；用系統(tǒng)現(xiàn)有資 源加上P 1釋放的資源滿足P 2的全部資源需求，使得P 2能夠運行結(jié)束并釋放所占用的資源