【正文】 repeat ?? collect data in nextp。 semaphore full = 0。 試寫出利用信號(hào)量機(jī)制實(shí)現(xiàn)兩 個(gè) 任務(wù)共享單緩沖區(qū)的同步算法。 until false。 Enter and buy ticket。 ② semaphore S=20。 ③ 如果購(gòu)票者最多為 n 個(gè)人，試寫出信號(hào)量取值的可能變化范圍 (最大值和最小值 )。若把一個(gè)購(gòu)票者看作一個(gè)進(jìn)程，請(qǐng)回答以下問題： ① 用信號(hào)量管理這些并發(fā)進(jìn)程時(shí)，應(yīng)該怎樣定義信號(hào)量，寫出信號(hào)量的初值以及信號(hào)量的各取值的含義。 即 ∑ Allocation[i]=m – Available ② 由 ① 式和 ② 式可以得到： ∑ Need[i] + ∑ Allocation[i]=n*Available+n+ m – Available=（ n1） *Available+m+n ③ 又因?yàn)?n=1，所以（ n1） =0，又因?yàn)?Available=0，所以（ n1） *Available=0 ④ 由 ③ 式和 ④ 式可以得到∑ Need[i] + ∑ Allocation[i]=0+m+n=m+n ⑤ 根據(jù)題意知： ∑ Max[i]m+n ⑥ 又因?yàn)椋?Max[i]=Need[i]+Allocation[i],所以∑ Max[i]= ∑ Need[i] + ∑ Allocation[i] ⑦ 由 ⑥ 式和 ⑦ 式得：∑ Need[i] + ∑ Allocation[i]m+n ⑧ 由假設(shè)推出的 ⑤ 式和由題意推出的 ⑧ 式相矛盾，所以假設(shè)是錯(cuò)誤的，即系統(tǒng)不會(huì)產(chǎn)生死鎖。 假設(shè)此系統(tǒng)可以發(fā)生死鎖。 (15) 考慮由 n個(gè)進(jìn)程共享的具有 m個(gè)同類資源的系統(tǒng)，如果對(duì)于 i=1,2,3,… ,n,有 Need[i]0并且所有進(jìn)程的最大需求量之和小于 m+n，試證明系統(tǒng)不會(huì)產(chǎn)生死鎖。 解： 系統(tǒng)中不會(huì)發(fā)生死鎖的最小資源數(shù)量是 13，這樣可以保證當(dāng)每一個(gè)進(jìn)程都占有 4 個(gè)資源的時(shí)候，有一個(gè)進(jìn)程可以獲得最后一個(gè)資源后被運(yùn)行，運(yùn)行完畢后釋放資源，于是其余進(jìn)程也能順利運(yùn)行完，所以不會(huì)死鎖。 (12) 某系統(tǒng)中有 A、 B、 C、 D 四類資源，且其總數(shù)量都是 8 個(gè)。在這種方法中，進(jìn)程只能在獲得其原有資源和所申請(qǐng)的新資源時(shí)才能繼續(xù)執(zhí)行。這種方法破壞了請(qǐng)求和保持條件，從而避免死鎖的發(fā)生。此時(shí)，若系統(tǒng)有足夠的資源，就把進(jìn)程需要的全部資源一次性地分配給它；若不能全部滿足進(jìn)程的資源請(qǐng)求，則一個(gè)資源也不分給它，即使有部分資源處于空閑狀態(tài)也不分配給該進(jìn)程。 (11) 死鎖的預(yù)防策略有哪些？請(qǐng)簡(jiǎn)要說明。 產(chǎn)生死鎖的原因可以歸結(jié)為兩點(diǎn)： 1）競(jìng)爭(zhēng)資源， 2） 各進(jìn)程之間的推進(jìn)順序不當(dāng)。 3. 管道通信系統(tǒng)：管道通信是一種以文件 系統(tǒng)為基礎(chǔ)實(shí)現(xiàn)的適用于在進(jìn)程之間實(shí)現(xiàn)大量數(shù)據(jù)傳送的通信方式。 2. 消息傳遞系統(tǒng)：消息傳遞機(jī)制可以實(shí)現(xiàn)不同主機(jī)間多個(gè) CPU 上進(jìn)程的通信。 1. 共享存儲(chǔ)器系統(tǒng)：在共享存儲(chǔ)器系統(tǒng)中，相互通信的進(jìn)程通過共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)實(shí)現(xiàn)進(jìn)程之間的通信。 consume(item) } } (9) 進(jìn)程的高級(jí)通信機(jī)制有哪些？請(qǐng)簡(jiǎn)要說明。 (item)。 } count=0。 count=count1。 } int remover() { if (count==0) wait(empty)。 count=count+1。 void insert(int item) { if (count==N) wait(full)。生產(chǎn)者 消費(fèi)者同步問題可以用偽代碼描述如下： monitor ProducerConsumer condition full,empty。 until false。 Ssignal(mutex, empty)。 nextc := buffer(out)。 until false。 in := (in+1) mod n。 . . . Swait(empty, mutex)。 in out: integer := 0, 0。 解： 利用 AND 信號(hào)量解決生產(chǎn)者－消費(fèi)者問題的算法描述如下： var mutex,empty,full: semaphore:=1,n,0。 think }while(1)。 } eat signal(chopstick[i])。 } else { wait(chopstick[(i+1)%5])。 Pi(){ //i 號(hào)哲學(xué)家的進(jìn)程 do{ if(i(i+1)%5) { wait(chopstick[i])。 semaphore chopstick[5]={1}。 (7) 利用信號(hào)量寫出不會(huì)出現(xiàn)死鎖的哲學(xué)家進(jìn)餐問題的算法。 如果缺少了 V(empty)，例如在生產(chǎn)者進(jìn)程向 n 個(gè)緩沖區(qū)放滿產(chǎn)品后消費(fèi)者進(jìn)程才開始從中取產(chǎn)品，這時(shí) empty=0， full=n，那么每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品時(shí) empty 并沒有被改變，直到緩沖池中的產(chǎn)品都取走了， empty 的值也一直是 0，即使目前緩沖池有 n 個(gè)空緩沖區(qū)，生產(chǎn)者進(jìn)程要想再往緩沖池中投放產(chǎn)品會(huì)因申請(qǐng)不到空緩沖區(qū)而被阻塞。在整型信號(hào)量機(jī)制中，未遵循“讓權(quán)等待”的準(zhǔn)則。 當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即 放棄占用 CPU，以使其它進(jìn)程有機(jī)會(huì)得到 CPU 的使用權(quán)，以免陷入“饑餓”狀態(tài) 。 對(duì)要求訪問臨 界 資源的進(jìn)程， 應(yīng)保證進(jìn)程能在有限時(shí)間 內(nèi) 進(jìn)入臨界區(qū)，以免陷入“饑餓”狀態(tài)。 當(dāng)有一個(gè)進(jìn)程在臨界區(qū)時(shí)，其它欲進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證進(jìn)程互斥地訪問臨界資源。 當(dāng)無進(jìn)程處于臨界區(qū)時(shí)，允許進(jìn)程進(jìn)入臨界區(qū)，并且只能在臨界區(qū)運(yùn)行有限的時(shí)間。 (3) 同步機(jī)構(gòu)需要遵循的基本準(zhǔn)則是什么？請(qǐng)簡(jiǎn)要說明。互斥是一種特殊的同步方式。進(jìn)程同步的主要任務(wù)就是使并發(fā)執(zhí)行的各進(jìn)程之間能有效地共享資源和相互合作，從而在執(zhí)行時(shí)間、次序上相互制約，按照一定的協(xié)議協(xié)調(diào)執(zhí)行，使程序的執(zhí)行 具有可再現(xiàn)性。試計(jì)算使用先來先服務(wù)、短作業(yè)優(yōu)先、高響應(yīng)比優(yōu)先算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 動(dòng)態(tài)優(yōu)先級(jí)是 在 進(jìn)程運(yùn)行前先確定一個(gè)優(yōu)先級(jí)， 進(jìn)程 運(yùn)行過程中根據(jù)進(jìn)程 等待時(shí)間的長(zhǎng)短、執(zhí)行時(shí)間的多少、輸入輸出信息量的大小等，通過計(jì)算得到新的優(yōu)先級(jí)。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則需要重新調(diào)度，搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程插入原隊(duì)列的末尾。 3. 進(jìn)程由于等待事件而放棄 CPU后 , 進(jìn)入等待隊(duì)列 , 一旦等待的事件發(fā)生 , 則回到原來的就緒隊(duì)列。 2. 新進(jìn)程就緒后，先插入隊(duì)列 1 的末尾，按 FCFS 算法調(diào)度。它的算法思想如下 (設(shè)采用搶占式調(diào)度 )： 1. 需要設(shè)置多個(gè)就緒隊(duì)列，并且為它們分別賦予不同的優(yōu)先級(jí)。 (19) 試說明多級(jí)反饋隊(duì)列調(diào)度算法思想。調(diào)度程序暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過 CPU 現(xiàn)場(chǎng)切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程，當(dāng)然，進(jìn)程可以未使用完一個(gè)時(shí)間片，就讓出 CPU(如阻塞 )。時(shí)間片的長(zhǎng)度從幾個(gè) ms 到幾百 ms。 解： 在采用時(shí)間片輪轉(zhuǎn)調(diào)度 算法的系統(tǒng)中，將系統(tǒng)中所有的就緒進(jìn)程按照 FCFS 原則，排成一個(gè)隊(duì)列。 (17) 在批處理系統(tǒng)、分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)中，應(yīng)分別采用哪種作業(yè) (進(jìn)程 )調(diào)度算法？ 解： 批處理系統(tǒng)采用先來先服務(wù)調(diào)度算法；分時(shí)系統(tǒng)采用時(shí)間片 輪轉(zhuǎn)法；實(shí)時(shí)系統(tǒng)采用高響應(yīng)比優(yōu)先調(diào)度算法。 3. 短進(jìn)程優(yōu)先原則 。 每個(gè)進(jìn)程均 被 賦于一個(gè)調(diào)度優(yōu)先級(jí)，通常一些重要 和緊急的進(jìn)程被賦于較高的優(yōu)先級(jí)。 各進(jìn)程按系統(tǒng)分配給的一個(gè)時(shí)間片運(yùn)行，當(dāng)該時(shí)間片用完或由于該進(jìn)程等待某事件發(fā)生而被阻塞時(shí)，系統(tǒng)就停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。 (16) 搶占式調(diào)度的原則是什么？請(qǐng)簡(jiǎn)要說明。 ? 低級(jí)調(diào)度：按照一定的算法從就緒隊(duì)列中選擇一個(gè)進(jìn)程，然后將處理器分配給它。 ? 中級(jí)調(diào)度：中級(jí)調(diào)度主要涉及進(jìn)程在內(nèi)存和外存之間的交換。 (15) 處理器調(diào)度的層次有哪些？各層次的主要工作是什么？ 解： 處理器調(diào)度的層次分為三級(jí)調(diào)度：高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。進(jìn)程間通信很麻煩，而同一進(jìn)程的線程則通過共享進(jìn)程的資源很方便地通信和同步，同步開銷小得多。 4. 管理開銷不同。 3. 擁有資源數(shù)量不同。 2. 并發(fā)粒度不同。線程基本上不擁有資源，只 需要一些 必不可少的資源 (如程序計(jì)數(shù)器、一組寄存器和棧 )。 (14) 什么是線程？請(qǐng)比較它與進(jìn)程的異同。 解： 系統(tǒng)調(diào)用進(jìn)程終止原語(yǔ)來終止進(jìn)程。創(chuàng)建原語(yǔ)首先 為新進(jìn)程申請(qǐng)獲得惟一的數(shù)字標(biāo)示符，并從 PCB 集合中 獲取一個(gè)空白 PCB；為新進(jìn)程的程序和數(shù)據(jù)以及用戶棧分配必要的內(nèi)存空間；然后對(duì) PCB 進(jìn)程初始化；最后將新進(jìn)程插入就緒隊(duì)列中，等待被調(diào)度執(zhí)行。 . (12) 試說明進(jìn)程創(chuàng)建的過程。 (11) 試說明引起進(jìn)程阻塞和喚醒的典型事件。 (10) 試說明引起進(jìn)程撤銷的典型事件。 (9) 試說明引起進(jìn)程創(chuàng)建的典型事件 。調(diào)用掛起原語(yǔ)把處于活動(dòng)阻塞的進(jìn)程掛起后，它的狀態(tài)就轉(zhuǎn)換為靜止阻塞。 解： 在引入掛起狀態(tài)的操作系統(tǒng)中，又增加了靜止就緒和靜止阻塞兩個(gè)新的進(jìn)程狀態(tài)。 解： 處于就緒狀態(tài)的進(jìn)程，在調(diào)度程 序 為之分配了處理器之后，就可以投入運(yùn)行。 掛起狀態(tài)的特點(diǎn)： 交換到磁盤 上的進(jìn)程 ，不讓其參與進(jìn)程調(diào)度，以達(dá)到平衡系統(tǒng)負(fù)荷的目的 。 ? 阻塞狀態(tài) ：當(dāng)一個(gè)進(jìn)程正在等待某個(gè)事件的發(fā)生 (如等待 I/O 的完成 )而暫停執(zhí)行，這時(shí)，即使分配有 CPU 時(shí)間，它也無法執(zhí)行。 ? 就緒狀態(tài) ：進(jìn)程已獲取到除 CPU 之外的所有必要資源，只要再得到 CPU，就可以馬上投入運(yùn)行。進(jìn)程與 PCB 是一一對(duì)應(yīng)的。 (4) 什么是 PCB？它具有什么作用？為什么說 PCB 是進(jìn)程存在的唯一標(biāo)識(shí)？ 解： 進(jìn)程控制塊 (Process Control Block， PCB)是操作系統(tǒng)為了管理進(jìn)程而設(shè)置的一個(gè)專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進(jìn)程的外部特征，描述進(jìn)程的運(yùn)動(dòng)變化過程。而對(duì)于未建立任何進(jìn)程的程序，都不能作為一個(gè)獨(dú)立的單位參加運(yùn)行。引入進(jìn)程的目的正是為了使其程序能和其它進(jìn)程的程序并發(fā)執(zhí)行，而程序是不能并發(fā)執(zhí)行的。 (3) 試從并發(fā)性、獨(dú) 立性、動(dòng)態(tài)性上比較程序和進(jìn)程的不同。 (2) 什么是進(jìn)程？為什么要在操作系統(tǒng)中引入進(jìn)程？ 解： 進(jìn)程是 可并發(fā)執(zhí)行且具有獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程，它是操作系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位 。所以，這些資源的狀態(tài)是由多個(gè)程序改變的，從而使程序的運(yùn)行失去了封閉性。 第 3章 處理器管理 (1) 為什么程序并發(fā)執(zhí)行會(huì)產(chǎn)生間斷性特征，并失去封閉性和可再現(xiàn)性？ 解： 之所以產(chǎn)生間斷性特征是因?yàn)?多個(gè)程序在并發(fā)執(zhí)行時(shí)，需要為了完成同一 項(xiàng)任務(wù)而相互合作，并發(fā)執(zhí)行的程序間的這種相互制約導(dǎo)致了“暫停 — 執(zhí)行 — 暫?！?的間斷性運(yùn)行規(guī)律。系統(tǒng)調(diào)用的主要類型包括： 1. 進(jìn)程控制類，主要用于進(jìn)程的創(chuàng)建和終止、對(duì)子進(jìn)程結(jié)束的等待、進(jìn)程映像的替換、進(jìn)程數(shù)據(jù)段大小的改變以及關(guān)于進(jìn)程標(biāo)識(shí)符或指定進(jìn)程屬性的獲得等； 2. 文件操縱類，主要用于文件的創(chuàng)建、打開、關(guān)閉、讀 /寫及文件讀寫指針的移動(dòng)和文件屬性的修改，目錄的創(chuàng)建及關(guān)于目錄、特別文件或普通文件的索引結(jié)點(diǎn)的建立等； 3. 進(jìn)程通信類，用于實(shí)現(xiàn)各種類型的通信機(jī)制如消息傳遞、共享存儲(chǔ)區(qū)及信息量集機(jī)制等； 4. 信息維護(hù)類，用于實(shí)現(xiàn)關(guān)于日期和時(shí) 間及其它系統(tǒng)相關(guān)信息的設(shè)置和獲得。每當(dāng)用戶在程序中需要操作系 統(tǒng)提供某種服務(wù)時(shí)，便可利用一條系統(tǒng)調(diào)用命令，去調(diào)用所需的系統(tǒng)過程。 5. 錯(cuò)誤處理 ： 操作系統(tǒng) 通過錯(cuò)誤處理機(jī)制 ，以便及時(shí)發(fā)現(xiàn)錯(cuò)誤并采取正確的處理步驟，避免損害系統(tǒng) 的 正確性和統(tǒng)一性。 3. 操作文件系統(tǒng) ：為了保證實(shí)現(xiàn)“按名存取”，文件系統(tǒng)應(yīng)該為用戶提供根據(jù)文件名來創(chuàng)建、訪問、修改、刪除文件的方法，以確保文件數(shù)據(jù)的安全可靠以及正確存取。 (3) 請(qǐng)說明操作系統(tǒng)具有的共性服務(wù)有哪些不同類別，這些類別分別用于完成什么功能？ 解 ： 所有的操作系統(tǒng) 都通過一些 基本服務(wù) 來 幫助用戶簡(jiǎn)單便捷 地 使用計(jì)算機(jī)各類資源，它們包括以下幾個(gè)類別： 1. 控制程序運(yùn)行 ： 系統(tǒng)通過服務(wù)將用戶程序裝入內(nèi)存并運(yùn)行該程序， 并 且要控制程序在規(guī)定時(shí)間內(nèi)結(jié)束 。 操作系統(tǒng)包括三種類型的用戶接口：命令接口（具體又可分為聯(lián)機(jī)命令接口與脫機(jī)命令接口）、 程序接口及圖形化用戶接口。全系統(tǒng)初始化 階段 要做的就是啟動(dòng)用戶接口 程序，對(duì)系統(tǒng)進(jìn)行必要的初始化