1.進(jìn)程通信就是進(jìn)程之間進(jìn)行信息交換。系統(tǒng)中各進(jìn)程異步執(zhí)行,但有些進(jìn)程之間必須保持一定的聯(lián)系,以便協(xié)調(diào)一致地完成指定任務(wù)。這種聯(lián)系就是通過(guò)交換一定數(shù)量的信息來(lái)實(shí)現(xiàn)的。
消息緩沖通信技術(shù)是一種高級(jí)通信機(jī)制,由Hansen首先提出。其基本思想是:根據(jù)"生產(chǎn)者－消費(fèi)者關(guān)系"原理,利用公共消息緩沖區(qū)實(shí)現(xiàn)進(jìn)程之間的信息交換。
(1)試敘述高級(jí)通信機(jī)制與低級(jí)通信機(jī)制P、V原語(yǔ)操作的主要區(qū)別。(5分)
(2)試敘述解釋消息緩沖通信技術(shù)的基本原理。(10分)
(3)消息緩沖通信機(jī)制中提供發(fā)送消息原語(yǔ)。Send(receiver,a)和接收消息原語(yǔ)Receive(a)。調(diào)用參數(shù)a分別表示發(fā)送消息的內(nèi)存區(qū)首地址或接收進(jìn)程的內(nèi)存消息區(qū)首地址。試設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu),并用P、V操作原語(yǔ)實(shí)現(xiàn)Send和Receive原語(yǔ)。(15分)
答案:
(1)要點(diǎn)：進(jìn)程間通信時(shí)所交換的信息量可多可少。少者僅是一些狀態(tài)和數(shù)據(jù)的交換，或者僅是一個(gè)簡(jiǎn)單的喚醒信號(hào)；多者可交換大量信息。前者稱為進(jìn)程同步與進(jìn)程互斥，亦稱進(jìn)程間低級(jí)通信；后者通信方式稱為進(jìn)程間高級(jí)通信。
（答出要點(diǎn)給3分，根據(jù)組織情況再給2分）
(2)要點(diǎn)：
①由操作系統(tǒng)在系統(tǒng)空間維護(hù)一組緩沖區(qū)；
②由操作系統(tǒng)提供兩個(gè)進(jìn)程高級(jí)通信原語(yǔ)Send和Receive;
③發(fā)送進(jìn)程要發(fā)送消息時(shí)，執(zhí)行Send系統(tǒng)調(diào)用命令，產(chǎn)生自愿性中斷 進(jìn)入操作系統(tǒng) 核心；
④操作系統(tǒng)為發(fā)送進(jìn)程分配一個(gè)空緩沖區(qū)，并將所發(fā)送的消息內(nèi)容從發(fā)送進(jìn)程空間拷貝到該緩沖區(qū)中；然后將此緩沖區(qū)連接到接收進(jìn)程的消息隊(duì)列尾；發(fā)送進(jìn)程就完成了發(fā)送，返回到用戶態(tài)繼續(xù)執(zhí)行；
⑤當(dāng)接收進(jìn)程執(zhí)行到receive系統(tǒng)調(diào)用命令時(shí)，也產(chǎn)生自愿性中斷，進(jìn)入操作系統(tǒng)核心；
⑥操作系統(tǒng)將載有消息的緩沖區(qū)從消息隊(duì)列中取出，并將消息內(nèi)容拷貝到接收進(jìn)程空間中，然后收回空閑緩沖區(qū)；接收進(jìn)程完成了消息接收，返回到用戶態(tài)繼續(xù)執(zhí)行；
（①、②、④、⑥為2分；③、⑤為1分）
(3)要點(diǎn)：①消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)為：
TypeMessage=Recoud
Sender(消息發(fā)送者)
Size(消息長(zhǎng)度)
text(消息正文)
pointer(消息隊(duì)列指針)
End,
②設(shè)置信號(hào)如下：
*每個(gè)接收進(jìn)程有一個(gè)m-mutex：互訴對(duì)消息隊(duì)列的操作，初值為1；
*buffe：管理空閑緩沖區(qū)，初值為空閑緩沖區(qū)個(gè)數(shù)；
*b-mutex：互訴操作空閑緩沖區(qū)，初值為為1；
*message：管理接收進(jìn)程消息，初值為0；
③Send(receiver,a)
Begin
根據(jù)參數(shù)R尋找接收進(jìn)程，如果未找到，則出錯(cuò)返回；
P(buffer)；
P(b-mutex)；
從消息緩沖區(qū)鏈上摘取一個(gè)空閑消息緩沖區(qū)；
V(b-mutex)；
將消息長(zhǎng)度及消息正文由a指示由發(fā)送區(qū)拷貝到消息緩沖區(qū)中；
將發(fā)送進(jìn)程的名字也記錄在該緩沖區(qū)中；
P(m-mutex)；
將消息緩沖區(qū)掛到接收進(jìn)程消息鏈的尾部；
V(m-mutex)；
V(mmssage)
End.
④Receive(a)
Begin
P(message)；
P(m-mutex)；
從消息隊(duì)列中取一個(gè)載有消息的緩沖區(qū)；
V(m-mutex)；
將消息長(zhǎng)度及肖息正文由消息緩沖區(qū)拷貝到接收區(qū)(由a指示)；
P(b-mutex)；
將空閑緩沖區(qū)掛到系統(tǒng)消息緩沖區(qū)鏈尾；
V(b-mutex)；
V(buffer)；
End.
(①3分②4分③4分④4分③，④重點(diǎn)在P，V操作)
2 . (1).進(jìn)程調(diào)度的主要功能。（8分）
(2).何時(shí)可進(jìn)行進(jìn)程調(diào)度？（8分）
(3).進(jìn)程調(diào)度算法解決以何種次序?qū)Ω骶途w進(jìn)程進(jìn)行處理機(jī)的分配以及按何種時(shí)間比例讓進(jìn)程占用處理機(jī)。時(shí)間片輪轉(zhuǎn)進(jìn)程調(diào)度算法的基本思想是什么？時(shí)間片的大小對(duì)系統(tǒng)有什么影響？在選取時(shí)間片時(shí)應(yīng)考慮哪些因素？（14分）
答案:(1).進(jìn)程調(diào)度的主要功能是:
①.記錄系統(tǒng)中所有進(jìn)程的執(zhí)行狀況;(2分)
②.根據(jù)一定的調(diào)度算法,從就緒隊(duì)列中選出一個(gè)進(jìn)程來(lái),準(zhǔn)備把CPU分給它;(2分)
③.把CPU分配給進(jìn)程,即把選中的進(jìn)程控制塊內(nèi)在關(guān)的現(xiàn)場(chǎng)信息,如程序狀態(tài)字,通用寄存器的內(nèi)容送入處理器相應(yīng)的寄存器中,從而讓它占用CPU運(yùn)行.(4分)
(2).進(jìn)程調(diào)度的時(shí)機(jī)是:
①.正在執(zhí)行的進(jìn)程運(yùn)行完畢;(1分)
②.正在執(zhí)行的進(jìn)程調(diào)用阻塞原語(yǔ)或P原語(yǔ)操作將自己阻塞起來(lái)進(jìn)入等待狀態(tài);(2分)
③.執(zhí)行中的進(jìn)程提出I/O請(qǐng)求后被阻塞;(1分)
④.在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完;(2分)
以上都是在CPU為不可剝奪方式下引起進(jìn)程調(diào)度的原因.在CPU方式為可剝奪時(shí),有以下原因:
⑤.就緒隊(duì)列中的某個(gè)進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí),從而也將引起進(jìn)程調(diào)度.(2分)
(3).時(shí)間片輪轉(zhuǎn)法(RR):
這主要是分時(shí)系統(tǒng)中使用的一種調(diào)度算法.時(shí)間片輪轉(zhuǎn)法的基本思想是:將CPU的處理時(shí)間劃分成一個(gè)個(gè)時(shí)間片(2分),就緒隊(duì)列中的諸進(jìn)程輪流運(yùn)行一個(gè)時(shí)間片(2分).當(dāng)時(shí)間片結(jié)束時(shí),就強(qiáng)迫運(yùn)行進(jìn)程讓出CPU,該進(jìn)程進(jìn)入就緒隊(duì)列,等待下一次調(diào)度(1分).同時(shí),進(jìn)程調(diào)度又去選擇就緒隊(duì)列中的一個(gè)進(jìn)程,分配給它一個(gè)時(shí)間片,以投入運(yùn)行(1分)
在輪轉(zhuǎn)法中,時(shí)間片長(zhǎng)度的選擇非常重要,將直接影響系統(tǒng)開銷和響應(yīng)時(shí)間(1分).如果時(shí)間片長(zhǎng)度很小,則調(diào)度程序剝奪處理機(jī)的次數(shù)頻繁,加重系統(tǒng)開銷(2分);反之,如果時(shí)間片長(zhǎng)度選擇過(guò)長(zhǎng),比方說(shuō)一個(gè)時(shí)間片就能保證就緒隊(duì)列中所有進(jìn)程都執(zhí)行完畢,則輪轉(zhuǎn)法就退化成先進(jìn)先出算法(2分)
影響時(shí)間片大小設(shè)置的主要因素有:系統(tǒng)響應(yīng)時(shí)間(1分),就緒進(jìn)程數(shù)目(終端數(shù)目)(1分)和計(jì)算機(jī)處理能力(1分).
3.從資源管理的觀點(diǎn)來(lái)看，操作系統(tǒng)的管理對(duì)象是計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)則是管理系統(tǒng)資源的程序集合。
(1).試問(wèn)操作系統(tǒng)所管理的資源有哪些？（4分)
(2).操作系統(tǒng)從哪幾個(gè)方面對(duì)資源進(jìn)行管理？主要完成什么工作？（12分）
(3).以存儲(chǔ)管理中的段式存儲(chǔ)管理為例，請(qǐng)敘述操作系統(tǒng)對(duì)內(nèi)存的具體管理方案（包括功能、數(shù)據(jù)結(jié)構(gòu)和算法）。（14分)
答案:
(1).操作系統(tǒng)所管理的資源分為硬件資源和軟件資源，硬件資源包括：CPU、內(nèi)存、各種外部設(shè)備，軟件資源主要是信息（程序和數(shù)據(jù)）。（4分）
(2).操作系統(tǒng)在共享的前題下，以資源分配、使用和回收為出發(fā)點(diǎn)，考慮操作系統(tǒng)各部分程序的功能和算法，解決并發(fā)環(huán)境中的資源管理問(wèn)題。
雖然操作系統(tǒng)所管理的各類資源的性質(zhì)各不相同，但所需要解決的問(wèn)題以及資源管理的策略又都具有類似之處。因此，每種資源管理模塊都要研究以下幾方面的內(nèi)容：
①記住資源的使用狀態(tài)，即記住哪些資源處于空閑，哪些資源已被使用和被誰(shuí)使用等；
②確定資源的分配策略，即根據(jù)各類資源的不同特點(diǎn)確定一組原則，以決定如何進(jìn)行資源的分配和調(diào)度；
③執(zhí)行資源的分配，即根據(jù)用戶的要求和資源分配策略，具體執(zhí)行資源的分配工作；
④回收資源，即當(dāng)某些用戶作業(yè)已不再需要某種資源時(shí)，系統(tǒng)及時(shí)地回收資源，以便重新分配給其它的作業(yè)使用。
(答出一項(xiàng)給3分。)
(3).首先從內(nèi)存劃分、程序邏輯地址劃分、內(nèi)存分配幾方面考慮段式存儲(chǔ)管理方案的工作原理：
①內(nèi)存劃分：內(nèi)存空間被動(dòng)態(tài)地劃分為若干個(gè)長(zhǎng)度不相同的區(qū)域，每個(gè)區(qū)域稱作一個(gè)物理段、每個(gè)物理段在內(nèi)存中有一個(gè)起始地址，稱作段首址。將物理段中的所有單元從0開始依次編址，稱為段內(nèi)地址。（2分）
②邏輯地址空間劃分：用戶程序按邏輯上有完整意義的段來(lái)劃分。稱為邏輯段。例如主程序、子程序、數(shù)據(jù)等都可各成一段，每段對(duì)應(yīng)于一個(gè)過(guò)程，一個(gè)程序模塊或一個(gè)數(shù)據(jù)集合。將一個(gè)用戶程序的所有邏輯段從0開始編號(hào)，稱為段號(hào)。將一個(gè)邏輯段中的所有單元從0開始編址，稱為段內(nèi)地址。(2分)
用戶程序的邏輯地址由段號(hào)和段內(nèi)地址兩部分組成：段號(hào)，段內(nèi)地址
③內(nèi)存分配：系統(tǒng)以段為單位進(jìn)行內(nèi)存分配，為每一個(gè)邏輯段分配一個(gè)連續(xù)的內(nèi)存區(qū) (物理段)。邏輯上連續(xù)的段在內(nèi)存不一定連續(xù)存放。（2分) 然后，從實(shí)現(xiàn)方法上考慮：
④建立段表（2分）
系統(tǒng)為每個(gè)用戶程序建立一張段表，用于記錄用戶程序的邏輯段與內(nèi)存物理段之間的對(duì)應(yīng)關(guān)系，包括邏輯段號(hào)，物理段首地址和物理段長(zhǎng)度三項(xiàng)內(nèi)容。用戶程序有多少邏輯段，該段表里就登記多少行，且按邏輯段的順序排列。段表存放在內(nèi)存系統(tǒng)區(qū)里。
⑤建立空閑區(qū)表（6分）
系統(tǒng)中設(shè)立一張內(nèi)存空閑區(qū)表，記錄內(nèi)存中空閑區(qū)域情況，用于為段分配和回收內(nèi)存。系統(tǒng)在尋找空閑區(qū)時(shí)可采用以下三種分配算法。
①首先適應(yīng)算法
根據(jù)申請(qǐng)，在空閑區(qū)表中選取第一個(gè)滿足申請(qǐng)長(zhǎng)度的空閑區(qū)。此算法簡(jiǎn)單，可以快速做出分配決定。
②適應(yīng)算法
根據(jù)申請(qǐng)，在空閑區(qū)表中選擇能滿足申請(qǐng)長(zhǎng)度的最小空閑區(qū)。此算法最節(jié)約空間，因?yàn)?它盡量不分割大的空閑區(qū)。其缺點(diǎn)是可能會(huì)形成很多很小的空閑區(qū)域，稱作碎片。
③最壞適應(yīng)算法
根據(jù)申請(qǐng)，在空閑區(qū)表中選擇能滿足申請(qǐng)要求的的空閑區(qū)。該算法的出發(fā)點(diǎn)是：在大空頭區(qū)中裝人信息后，分割剩下的空閑區(qū)相對(duì)也大，還能用于裝入新的信息。該算法的優(yōu)點(diǎn)是可以避免形成碎片；缺點(diǎn)是分割大的空閑區(qū)后，再遇到較大的申請(qǐng)時(shí)，無(wú)法滿足的可能性較大。
4. 目前，大多數(shù)計(jì)算機(jī)系統(tǒng)都支持虛擬頁(yè)式地址轉(zhuǎn)換機(jī)制。試回答下列問(wèn)題：
(1).頁(yè)式存儲(chǔ)管理方案中，用戶地址空間怎樣劃分？?jī)?nèi)存地址空間怎樣劃分？?jī)?nèi)存分配過(guò)程是怎樣的？（10分）
(2).頁(yè)表應(yīng)設(shè)計(jì)哪些數(shù)據(jù)項(xiàng)，每個(gè)數(shù)據(jù)項(xiàng)的作用是什么？（10分）
(3).頁(yè)式存儲(chǔ)管理方案中，地址映射機(jī)制需要哪種寄存器的支持？為了加快地址映射速度，需要采取什么措施？該措施的作用是什么？（10分）
答案:
(1).系統(tǒng)將用戶程序的邏輯空間按照相等大小劃分成若干界面，稱為邏輯頁(yè)面。（2分）各個(gè)邏輯頁(yè)面從0開始依次編號(hào)，每個(gè)邏輯頁(yè)面內(nèi)也從0開始編址，稱為頁(yè)內(nèi)地址。用戶程序的邏輯地址由邏輯頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分組成。（2分）
頁(yè)式存儲(chǔ)管理將內(nèi)存空間按照邏輯頁(yè)面大小劃分成等長(zhǎng)的若干區(qū)域，每個(gè)區(qū)域?yàn)橐粋€(gè)內(nèi)存塊。（2分）內(nèi)存的所有內(nèi)存塊從0開始編號(hào)。（1分）
內(nèi)存分配時(shí)，以頁(yè)面（塊）為單位，并按用戶程序所需頁(yè)數(shù)多少進(jìn)行分配。（2分）邏輯上相鄰的頁(yè)面在內(nèi)存中不一定相鄰，即分配給用戶程序的內(nèi)存塊不一定連續(xù)。（1分）
(2).頁(yè)表表項(xiàng)有：
邏輯頁(yè)面號(hào)；（2分）
物理頁(yè)面號(hào)（或塊號(hào)）；（2分）
駐留位（中斷位或特征位）：指示該頁(yè)在內(nèi)存還是在外存；（2分）
外存地址：指示該頁(yè)在外存的地址；（2分）
修改位：指示該頁(yè)在內(nèi)存駐留期間是否被修改過(guò)；（2分）
(3).系統(tǒng)提供一對(duì)硬件寄存器：頁(yè)表始址寄存器和頁(yè)表長(zhǎng)度寄存器。（2分，答對(duì)1個(gè)為1分）
①頁(yè)表始址寄存器，用于保存正在運(yùn)行進(jìn)程的頁(yè)表在內(nèi)存的首地址。當(dāng)進(jìn)程被調(diào)度程序選中投入運(yùn)行時(shí)，系統(tǒng)將其頁(yè)表首地址從進(jìn)程控制塊中取出送入該寄存器。（2分）
②頁(yè)表長(zhǎng)度寄存器，用于保存正在運(yùn)行進(jìn)程的頁(yè)表的長(zhǎng)度。當(dāng)進(jìn)程被選中運(yùn)行時(shí)，系統(tǒng)將它從進(jìn)程控制中塊中取出送入該寄存器。（2分）
為了加快地址映射速度，可在地址映射機(jī)制中增加一個(gè)小容量的聯(lián)想寄存器（相聯(lián)存儲(chǔ)器），（2分）它由高速寄存器組成，成為一張快表，快表用來(lái)存放當(dāng)前訪問(wèn)最頻繁的少數(shù)活動(dòng)頁(yè)的頁(yè)號(hào)。（2分）
5. 有一個(gè)文件系統(tǒng)，根目錄常駐內(nèi)存，如圖所示。目錄文件采用鏈接結(jié)構(gòu)，假設(shè)每個(gè)目錄下最多允許建立60個(gè)文件或目錄（統(tǒng)稱為下級(jí)文件）。又假設(shè)每個(gè)磁盤塊最多可存放10個(gè)文件目錄項(xiàng)：如果下級(jí)文件是目錄文件，則上級(jí)目錄項(xiàng)指向該目錄文件的第一塊地址；
如果下級(jí)文件是普通文件，則上級(jí)目錄項(xiàng)指向該文件的FCB（文件控制塊）地址。假設(shè)圖中所示的文件目錄結(jié)構(gòu)中，文件或子目錄按自左向右的次序建立，而符號(hào)"…"表示尚有其他文件或子目錄未列出。
(1) 假設(shè)普通文件采用UNIX的三級(jí)索引結(jié)構(gòu)，主索引表放在文件控制塊中。
①假設(shè)每個(gè)物理塊能存放128個(gè)地址（物理塊塊號(hào)），那么，普通文件的大小為多少塊？（3分）
②若要讀/A/D/G/I/K的第7461塊，系統(tǒng)最少啟動(dòng)硬盤幾次，最多幾次？（6分）
(2) 若普通文件采用順序結(jié)構(gòu)，若要讀/A/D/G/I/K的第285塊，最少啟動(dòng)硬盤幾次，最多幾次？（6分）
(3) 為了打開文件，用戶給出文件名后，操作系統(tǒng)應(yīng)做哪些工作？（6分）
(4) 一般在文件系統(tǒng)中，為了加快文件目錄檢索速度（減少啟動(dòng)硬盤的次數(shù)），可以采用什么方法？（9分）
答案:
(1) ①10+128+1282+1283塊
?、谧钌賳?dòng)硬盤8次，最多啟動(dòng)硬盤23次
(2) 最少啟動(dòng)硬盤6次，最多啟動(dòng)硬盤21次
(3) 打開文件時(shí)，用戶首先給出文件名，操作系統(tǒng)完成以下工作：
?、俨檎夷夸?，檢查文件是否存在，如不存在，則報(bào)告錯(cuò)誤；
②如該文件存在，檢查操作的合法性，例如，若該文件為只讀文件，但用戶卻將"讀寫方?quot;置為寫，則系統(tǒng)不予打開；
?、鄹鶕?jù)文件名在目錄文件中找到該文件的文件控制塊，把該文件的文件控制塊調(diào)入內(nèi)存。
(4)．一般在文件系統(tǒng)中，為了加快文件目錄檢索速度，減少啟動(dòng)硬盤的次數(shù)，可以采用兩種方法。
①引入"當(dāng)前目錄"。在一個(gè)多層次的樹形文件目錄結(jié)構(gòu)中，如果每次都從根結(jié)點(diǎn)開始檢索，很不方便，通常各目錄文件放在外存，故影響訪問(wèn)速度，尤其是當(dāng)層次較多時(shí)檢索要耗費(fèi)很多時(shí)間。為克服這一缺點(diǎn)，引入"當(dāng)前目錄"或稱"工作目錄"的概念。查找文件時(shí)可以從當(dāng)前目錄開始向下檢索。這樣檢索路徑縮短，檢索速度提高。
?、诓捎?目錄項(xiàng)分解?quot;。一個(gè)文件控制塊一般要占很多空間，這樣一個(gè)目錄文件往往很大。在檢索目錄時(shí)，為了找到所需要的目錄項(xiàng)，常常要將存放目錄文件的多個(gè)物理塊逐塊讀入內(nèi)存進(jìn)行查找，這就降低了檢索速度。可以利用目錄項(xiàng)分解法解決這一問(wèn)題，即把目錄項(xiàng)（文件控制塊）分為兩部分：名號(hào)目錄項(xiàng)，包含文件名以及相應(yīng)的文件內(nèi)部號(hào)；基本目錄項(xiàng)，包含了除文件名外文件控制塊的其他全部信息。
6.在多道程序系統(tǒng)中，一組進(jìn)程中的每一個(gè)進(jìn)程均無(wú)限期的等待被該組進(jìn)程中的另一進(jìn)程所占有、且永遠(yuǎn)不會(huì)釋放的資源，這種現(xiàn)象將導(dǎo)致系統(tǒng)處于死鎖狀態(tài)。試述：
(1)產(chǎn)生死鎖的原因是什么？（10分）
(2)產(chǎn)生死鎖的必要條件是什么？（10分）
(3)如何處理死鎖？（10分）
答案:
(1).產(chǎn)生死鎖的原因:一是系統(tǒng)提供的資源數(shù)量有限,不能滿足每個(gè)進(jìn)程的使用(5分);二是多道程序運(yùn)行時(shí),進(jìn)程推進(jìn)順序不合理(5分).
(2)產(chǎn)生死鎖的必要條件是:
1)互斥條件(2.5分)
2)不剝奪條件(不可搶占)(2.5分)
3)部分分配(2.5分)
4)循環(huán)等待(2.5分)
(3)死鎖的處理:
1)死鎖的預(yù)防
2)死鎖的避免
3)死鎖的檢測(cè)
4)死鎖的解除
5)不做任何處理
(以上要點(diǎn)每答對(duì)1個(gè)給2.5分,答對(duì)4個(gè)及以上要點(diǎn)最多給10分)
消息緩沖通信技術(shù)是一種高級(jí)通信機(jī)制,由Hansen首先提出。其基本思想是:根據(jù)"生產(chǎn)者－消費(fèi)者關(guān)系"原理,利用公共消息緩沖區(qū)實(shí)現(xiàn)進(jìn)程之間的信息交換。
(1)試敘述高級(jí)通信機(jī)制與低級(jí)通信機(jī)制P、V原語(yǔ)操作的主要區(qū)別。(5分)
(2)試敘述解釋消息緩沖通信技術(shù)的基本原理。(10分)
(3)消息緩沖通信機(jī)制中提供發(fā)送消息原語(yǔ)。Send(receiver,a)和接收消息原語(yǔ)Receive(a)。調(diào)用參數(shù)a分別表示發(fā)送消息的內(nèi)存區(qū)首地址或接收進(jìn)程的內(nèi)存消息區(qū)首地址。試設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu),并用P、V操作原語(yǔ)實(shí)現(xiàn)Send和Receive原語(yǔ)。(15分)
答案:
(1)要點(diǎn)：進(jìn)程間通信時(shí)所交換的信息量可多可少。少者僅是一些狀態(tài)和數(shù)據(jù)的交換，或者僅是一個(gè)簡(jiǎn)單的喚醒信號(hào)；多者可交換大量信息。前者稱為進(jìn)程同步與進(jìn)程互斥，亦稱進(jìn)程間低級(jí)通信；后者通信方式稱為進(jìn)程間高級(jí)通信。
（答出要點(diǎn)給3分，根據(jù)組織情況再給2分）
(2)要點(diǎn)：
①由操作系統(tǒng)在系統(tǒng)空間維護(hù)一組緩沖區(qū)；
②由操作系統(tǒng)提供兩個(gè)進(jìn)程高級(jí)通信原語(yǔ)Send和Receive;
③發(fā)送進(jìn)程要發(fā)送消息時(shí)，執(zhí)行Send系統(tǒng)調(diào)用命令，產(chǎn)生自愿性中斷 進(jìn)入操作系統(tǒng) 核心；
④操作系統(tǒng)為發(fā)送進(jìn)程分配一個(gè)空緩沖區(qū)，并將所發(fā)送的消息內(nèi)容從發(fā)送進(jìn)程空間拷貝到該緩沖區(qū)中；然后將此緩沖區(qū)連接到接收進(jìn)程的消息隊(duì)列尾；發(fā)送進(jìn)程就完成了發(fā)送，返回到用戶態(tài)繼續(xù)執(zhí)行；
⑤當(dāng)接收進(jìn)程執(zhí)行到receive系統(tǒng)調(diào)用命令時(shí)，也產(chǎn)生自愿性中斷，進(jìn)入操作系統(tǒng)核心；
⑥操作系統(tǒng)將載有消息的緩沖區(qū)從消息隊(duì)列中取出，并將消息內(nèi)容拷貝到接收進(jìn)程空間中，然后收回空閑緩沖區(qū)；接收進(jìn)程完成了消息接收，返回到用戶態(tài)繼續(xù)執(zhí)行；
（①、②、④、⑥為2分；③、⑤為1分）
(3)要點(diǎn)：①消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)為：
TypeMessage=Recoud
Sender(消息發(fā)送者)
Size(消息長(zhǎng)度)
text(消息正文)
pointer(消息隊(duì)列指針)
End,
②設(shè)置信號(hào)如下：
*每個(gè)接收進(jìn)程有一個(gè)m-mutex：互訴對(duì)消息隊(duì)列的操作，初值為1；
*buffe：管理空閑緩沖區(qū)，初值為空閑緩沖區(qū)個(gè)數(shù)；
*b-mutex：互訴操作空閑緩沖區(qū)，初值為為1；
*message：管理接收進(jìn)程消息，初值為0；
③Send(receiver,a)
Begin
根據(jù)參數(shù)R尋找接收進(jìn)程，如果未找到，則出錯(cuò)返回；
P(buffer)；
P(b-mutex)；
從消息緩沖區(qū)鏈上摘取一個(gè)空閑消息緩沖區(qū)；
V(b-mutex)；
將消息長(zhǎng)度及消息正文由a指示由發(fā)送區(qū)拷貝到消息緩沖區(qū)中；
將發(fā)送進(jìn)程的名字也記錄在該緩沖區(qū)中；
P(m-mutex)；
將消息緩沖區(qū)掛到接收進(jìn)程消息鏈的尾部；
V(m-mutex)；
V(mmssage)
End.
④Receive(a)
Begin
P(message)；
P(m-mutex)；
從消息隊(duì)列中取一個(gè)載有消息的緩沖區(qū)；
V(m-mutex)；
將消息長(zhǎng)度及肖息正文由消息緩沖區(qū)拷貝到接收區(qū)(由a指示)；
P(b-mutex)；
將空閑緩沖區(qū)掛到系統(tǒng)消息緩沖區(qū)鏈尾；
V(b-mutex)；
V(buffer)；
End.
(①3分②4分③4分④4分③，④重點(diǎn)在P，V操作)
2 . (1).進(jìn)程調(diào)度的主要功能。（8分）
(2).何時(shí)可進(jìn)行進(jìn)程調(diào)度？（8分）
(3).進(jìn)程調(diào)度算法解決以何種次序?qū)Ω骶途w進(jìn)程進(jìn)行處理機(jī)的分配以及按何種時(shí)間比例讓進(jìn)程占用處理機(jī)。時(shí)間片輪轉(zhuǎn)進(jìn)程調(diào)度算法的基本思想是什么？時(shí)間片的大小對(duì)系統(tǒng)有什么影響？在選取時(shí)間片時(shí)應(yīng)考慮哪些因素？（14分）
答案:(1).進(jìn)程調(diào)度的主要功能是:
①.記錄系統(tǒng)中所有進(jìn)程的執(zhí)行狀況;(2分)
②.根據(jù)一定的調(diào)度算法,從就緒隊(duì)列中選出一個(gè)進(jìn)程來(lái),準(zhǔn)備把CPU分給它;(2分)
③.把CPU分配給進(jìn)程,即把選中的進(jìn)程控制塊內(nèi)在關(guān)的現(xiàn)場(chǎng)信息,如程序狀態(tài)字,通用寄存器的內(nèi)容送入處理器相應(yīng)的寄存器中,從而讓它占用CPU運(yùn)行.(4分)
(2).進(jìn)程調(diào)度的時(shí)機(jī)是:
①.正在執(zhí)行的進(jìn)程運(yùn)行完畢;(1分)
②.正在執(zhí)行的進(jìn)程調(diào)用阻塞原語(yǔ)或P原語(yǔ)操作將自己阻塞起來(lái)進(jìn)入等待狀態(tài);(2分)
③.執(zhí)行中的進(jìn)程提出I/O請(qǐng)求后被阻塞;(1分)
④.在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完;(2分)
以上都是在CPU為不可剝奪方式下引起進(jìn)程調(diào)度的原因.在CPU方式為可剝奪時(shí),有以下原因:
⑤.就緒隊(duì)列中的某個(gè)進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí),從而也將引起進(jìn)程調(diào)度.(2分)
(3).時(shí)間片輪轉(zhuǎn)法(RR):
這主要是分時(shí)系統(tǒng)中使用的一種調(diào)度算法.時(shí)間片輪轉(zhuǎn)法的基本思想是:將CPU的處理時(shí)間劃分成一個(gè)個(gè)時(shí)間片(2分),就緒隊(duì)列中的諸進(jìn)程輪流運(yùn)行一個(gè)時(shí)間片(2分).當(dāng)時(shí)間片結(jié)束時(shí),就強(qiáng)迫運(yùn)行進(jìn)程讓出CPU,該進(jìn)程進(jìn)入就緒隊(duì)列,等待下一次調(diào)度(1分).同時(shí),進(jìn)程調(diào)度又去選擇就緒隊(duì)列中的一個(gè)進(jìn)程,分配給它一個(gè)時(shí)間片,以投入運(yùn)行(1分)
在輪轉(zhuǎn)法中,時(shí)間片長(zhǎng)度的選擇非常重要,將直接影響系統(tǒng)開銷和響應(yīng)時(shí)間(1分).如果時(shí)間片長(zhǎng)度很小,則調(diào)度程序剝奪處理機(jī)的次數(shù)頻繁,加重系統(tǒng)開銷(2分);反之,如果時(shí)間片長(zhǎng)度選擇過(guò)長(zhǎng),比方說(shuō)一個(gè)時(shí)間片就能保證就緒隊(duì)列中所有進(jìn)程都執(zhí)行完畢,則輪轉(zhuǎn)法就退化成先進(jìn)先出算法(2分)
影響時(shí)間片大小設(shè)置的主要因素有:系統(tǒng)響應(yīng)時(shí)間(1分),就緒進(jìn)程數(shù)目(終端數(shù)目)(1分)和計(jì)算機(jī)處理能力(1分).
3.從資源管理的觀點(diǎn)來(lái)看，操作系統(tǒng)的管理對(duì)象是計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)則是管理系統(tǒng)資源的程序集合。
(1).試問(wèn)操作系統(tǒng)所管理的資源有哪些？（4分)
(2).操作系統(tǒng)從哪幾個(gè)方面對(duì)資源進(jìn)行管理？主要完成什么工作？（12分）
(3).以存儲(chǔ)管理中的段式存儲(chǔ)管理為例，請(qǐng)敘述操作系統(tǒng)對(duì)內(nèi)存的具體管理方案（包括功能、數(shù)據(jù)結(jié)構(gòu)和算法）。（14分)
答案:
(1).操作系統(tǒng)所管理的資源分為硬件資源和軟件資源，硬件資源包括：CPU、內(nèi)存、各種外部設(shè)備，軟件資源主要是信息（程序和數(shù)據(jù)）。（4分）
(2).操作系統(tǒng)在共享的前題下，以資源分配、使用和回收為出發(fā)點(diǎn)，考慮操作系統(tǒng)各部分程序的功能和算法，解決并發(fā)環(huán)境中的資源管理問(wèn)題。
雖然操作系統(tǒng)所管理的各類資源的性質(zhì)各不相同，但所需要解決的問(wèn)題以及資源管理的策略又都具有類似之處。因此，每種資源管理模塊都要研究以下幾方面的內(nèi)容：
①記住資源的使用狀態(tài)，即記住哪些資源處于空閑，哪些資源已被使用和被誰(shuí)使用等；
②確定資源的分配策略，即根據(jù)各類資源的不同特點(diǎn)確定一組原則，以決定如何進(jìn)行資源的分配和調(diào)度；
③執(zhí)行資源的分配，即根據(jù)用戶的要求和資源分配策略，具體執(zhí)行資源的分配工作；
④回收資源，即當(dāng)某些用戶作業(yè)已不再需要某種資源時(shí)，系統(tǒng)及時(shí)地回收資源，以便重新分配給其它的作業(yè)使用。
(答出一項(xiàng)給3分。)
(3).首先從內(nèi)存劃分、程序邏輯地址劃分、內(nèi)存分配幾方面考慮段式存儲(chǔ)管理方案的工作原理：
①內(nèi)存劃分：內(nèi)存空間被動(dòng)態(tài)地劃分為若干個(gè)長(zhǎng)度不相同的區(qū)域，每個(gè)區(qū)域稱作一個(gè)物理段、每個(gè)物理段在內(nèi)存中有一個(gè)起始地址，稱作段首址。將物理段中的所有單元從0開始依次編址，稱為段內(nèi)地址。（2分）
②邏輯地址空間劃分：用戶程序按邏輯上有完整意義的段來(lái)劃分。稱為邏輯段。例如主程序、子程序、數(shù)據(jù)等都可各成一段，每段對(duì)應(yīng)于一個(gè)過(guò)程，一個(gè)程序模塊或一個(gè)數(shù)據(jù)集合。將一個(gè)用戶程序的所有邏輯段從0開始編號(hào)，稱為段號(hào)。將一個(gè)邏輯段中的所有單元從0開始編址，稱為段內(nèi)地址。(2分)
用戶程序的邏輯地址由段號(hào)和段內(nèi)地址兩部分組成：段號(hào)，段內(nèi)地址
③內(nèi)存分配：系統(tǒng)以段為單位進(jìn)行內(nèi)存分配，為每一個(gè)邏輯段分配一個(gè)連續(xù)的內(nèi)存區(qū) (物理段)。邏輯上連續(xù)的段在內(nèi)存不一定連續(xù)存放。（2分) 然后，從實(shí)現(xiàn)方法上考慮：
④建立段表（2分）
系統(tǒng)為每個(gè)用戶程序建立一張段表，用于記錄用戶程序的邏輯段與內(nèi)存物理段之間的對(duì)應(yīng)關(guān)系，包括邏輯段號(hào)，物理段首地址和物理段長(zhǎng)度三項(xiàng)內(nèi)容。用戶程序有多少邏輯段，該段表里就登記多少行，且按邏輯段的順序排列。段表存放在內(nèi)存系統(tǒng)區(qū)里。
⑤建立空閑區(qū)表（6分）
系統(tǒng)中設(shè)立一張內(nèi)存空閑區(qū)表，記錄內(nèi)存中空閑區(qū)域情況，用于為段分配和回收內(nèi)存。系統(tǒng)在尋找空閑區(qū)時(shí)可采用以下三種分配算法。
①首先適應(yīng)算法
根據(jù)申請(qǐng)，在空閑區(qū)表中選取第一個(gè)滿足申請(qǐng)長(zhǎng)度的空閑區(qū)。此算法簡(jiǎn)單，可以快速做出分配決定。
②適應(yīng)算法
根據(jù)申請(qǐng)，在空閑區(qū)表中選擇能滿足申請(qǐng)長(zhǎng)度的最小空閑區(qū)。此算法最節(jié)約空間，因?yàn)?它盡量不分割大的空閑區(qū)。其缺點(diǎn)是可能會(huì)形成很多很小的空閑區(qū)域，稱作碎片。
③最壞適應(yīng)算法
根據(jù)申請(qǐng)，在空閑區(qū)表中選擇能滿足申請(qǐng)要求的的空閑區(qū)。該算法的出發(fā)點(diǎn)是：在大空頭區(qū)中裝人信息后，分割剩下的空閑區(qū)相對(duì)也大，還能用于裝入新的信息。該算法的優(yōu)點(diǎn)是可以避免形成碎片；缺點(diǎn)是分割大的空閑區(qū)后，再遇到較大的申請(qǐng)時(shí)，無(wú)法滿足的可能性較大。
4. 目前，大多數(shù)計(jì)算機(jī)系統(tǒng)都支持虛擬頁(yè)式地址轉(zhuǎn)換機(jī)制。試回答下列問(wèn)題：
(1).頁(yè)式存儲(chǔ)管理方案中，用戶地址空間怎樣劃分？?jī)?nèi)存地址空間怎樣劃分？?jī)?nèi)存分配過(guò)程是怎樣的？（10分）
(2).頁(yè)表應(yīng)設(shè)計(jì)哪些數(shù)據(jù)項(xiàng)，每個(gè)數(shù)據(jù)項(xiàng)的作用是什么？（10分）
(3).頁(yè)式存儲(chǔ)管理方案中，地址映射機(jī)制需要哪種寄存器的支持？為了加快地址映射速度，需要采取什么措施？該措施的作用是什么？（10分）
答案:
(1).系統(tǒng)將用戶程序的邏輯空間按照相等大小劃分成若干界面，稱為邏輯頁(yè)面。（2分）各個(gè)邏輯頁(yè)面從0開始依次編號(hào)，每個(gè)邏輯頁(yè)面內(nèi)也從0開始編址，稱為頁(yè)內(nèi)地址。用戶程序的邏輯地址由邏輯頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分組成。（2分）
頁(yè)式存儲(chǔ)管理將內(nèi)存空間按照邏輯頁(yè)面大小劃分成等長(zhǎng)的若干區(qū)域，每個(gè)區(qū)域?yàn)橐粋€(gè)內(nèi)存塊。（2分）內(nèi)存的所有內(nèi)存塊從0開始編號(hào)。（1分）
內(nèi)存分配時(shí)，以頁(yè)面（塊）為單位，并按用戶程序所需頁(yè)數(shù)多少進(jìn)行分配。（2分）邏輯上相鄰的頁(yè)面在內(nèi)存中不一定相鄰，即分配給用戶程序的內(nèi)存塊不一定連續(xù)。（1分）
(2).頁(yè)表表項(xiàng)有：
邏輯頁(yè)面號(hào)；（2分）
物理頁(yè)面號(hào)（或塊號(hào)）；（2分）
駐留位（中斷位或特征位）：指示該頁(yè)在內(nèi)存還是在外存；（2分）
外存地址：指示該頁(yè)在外存的地址；（2分）
修改位：指示該頁(yè)在內(nèi)存駐留期間是否被修改過(guò)；（2分）
(3).系統(tǒng)提供一對(duì)硬件寄存器：頁(yè)表始址寄存器和頁(yè)表長(zhǎng)度寄存器。（2分，答對(duì)1個(gè)為1分）
①頁(yè)表始址寄存器，用于保存正在運(yùn)行進(jìn)程的頁(yè)表在內(nèi)存的首地址。當(dāng)進(jìn)程被調(diào)度程序選中投入運(yùn)行時(shí)，系統(tǒng)將其頁(yè)表首地址從進(jìn)程控制塊中取出送入該寄存器。（2分）
②頁(yè)表長(zhǎng)度寄存器，用于保存正在運(yùn)行進(jìn)程的頁(yè)表的長(zhǎng)度。當(dāng)進(jìn)程被選中運(yùn)行時(shí)，系統(tǒng)將它從進(jìn)程控制中塊中取出送入該寄存器。（2分）
為了加快地址映射速度，可在地址映射機(jī)制中增加一個(gè)小容量的聯(lián)想寄存器（相聯(lián)存儲(chǔ)器），（2分）它由高速寄存器組成，成為一張快表，快表用來(lái)存放當(dāng)前訪問(wèn)最頻繁的少數(shù)活動(dòng)頁(yè)的頁(yè)號(hào)。（2分）
5. 有一個(gè)文件系統(tǒng)，根目錄常駐內(nèi)存，如圖所示。目錄文件采用鏈接結(jié)構(gòu)，假設(shè)每個(gè)目錄下最多允許建立60個(gè)文件或目錄（統(tǒng)稱為下級(jí)文件）。又假設(shè)每個(gè)磁盤塊最多可存放10個(gè)文件目錄項(xiàng)：如果下級(jí)文件是目錄文件，則上級(jí)目錄項(xiàng)指向該目錄文件的第一塊地址；
如果下級(jí)文件是普通文件，則上級(jí)目錄項(xiàng)指向該文件的FCB（文件控制塊）地址。假設(shè)圖中所示的文件目錄結(jié)構(gòu)中，文件或子目錄按自左向右的次序建立，而符號(hào)"…"表示尚有其他文件或子目錄未列出。
(1) 假設(shè)普通文件采用UNIX的三級(jí)索引結(jié)構(gòu)，主索引表放在文件控制塊中。
①假設(shè)每個(gè)物理塊能存放128個(gè)地址（物理塊塊號(hào)），那么，普通文件的大小為多少塊？（3分）
②若要讀/A/D/G/I/K的第7461塊，系統(tǒng)最少啟動(dòng)硬盤幾次，最多幾次？（6分）
(2) 若普通文件采用順序結(jié)構(gòu)，若要讀/A/D/G/I/K的第285塊，最少啟動(dòng)硬盤幾次，最多幾次？（6分）
(3) 為了打開文件，用戶給出文件名后，操作系統(tǒng)應(yīng)做哪些工作？（6分）
(4) 一般在文件系統(tǒng)中，為了加快文件目錄檢索速度（減少啟動(dòng)硬盤的次數(shù)），可以采用什么方法？（9分）
答案:
(1) ①10+128+1282+1283塊
?、谧钌賳?dòng)硬盤8次，最多啟動(dòng)硬盤23次
(2) 最少啟動(dòng)硬盤6次，最多啟動(dòng)硬盤21次
(3) 打開文件時(shí)，用戶首先給出文件名，操作系統(tǒng)完成以下工作：
?、俨檎夷夸?，檢查文件是否存在，如不存在，則報(bào)告錯(cuò)誤；
②如該文件存在，檢查操作的合法性，例如，若該文件為只讀文件，但用戶卻將"讀寫方?quot;置為寫，則系統(tǒng)不予打開；
?、鄹鶕?jù)文件名在目錄文件中找到該文件的文件控制塊，把該文件的文件控制塊調(diào)入內(nèi)存。
(4)．一般在文件系統(tǒng)中，為了加快文件目錄檢索速度，減少啟動(dòng)硬盤的次數(shù)，可以采用兩種方法。
①引入"當(dāng)前目錄"。在一個(gè)多層次的樹形文件目錄結(jié)構(gòu)中，如果每次都從根結(jié)點(diǎn)開始檢索，很不方便，通常各目錄文件放在外存，故影響訪問(wèn)速度，尤其是當(dāng)層次較多時(shí)檢索要耗費(fèi)很多時(shí)間。為克服這一缺點(diǎn)，引入"當(dāng)前目錄"或稱"工作目錄"的概念。查找文件時(shí)可以從當(dāng)前目錄開始向下檢索。這樣檢索路徑縮短，檢索速度提高。
?、诓捎?目錄項(xiàng)分解?quot;。一個(gè)文件控制塊一般要占很多空間，這樣一個(gè)目錄文件往往很大。在檢索目錄時(shí)，為了找到所需要的目錄項(xiàng)，常常要將存放目錄文件的多個(gè)物理塊逐塊讀入內(nèi)存進(jìn)行查找，這就降低了檢索速度。可以利用目錄項(xiàng)分解法解決這一問(wèn)題，即把目錄項(xiàng)（文件控制塊）分為兩部分：名號(hào)目錄項(xiàng)，包含文件名以及相應(yīng)的文件內(nèi)部號(hào)；基本目錄項(xiàng)，包含了除文件名外文件控制塊的其他全部信息。
6.在多道程序系統(tǒng)中，一組進(jìn)程中的每一個(gè)進(jìn)程均無(wú)限期的等待被該組進(jìn)程中的另一進(jìn)程所占有、且永遠(yuǎn)不會(huì)釋放的資源，這種現(xiàn)象將導(dǎo)致系統(tǒng)處于死鎖狀態(tài)。試述：
(1)產(chǎn)生死鎖的原因是什么？（10分）
(2)產(chǎn)生死鎖的必要條件是什么？（10分）
(3)如何處理死鎖？（10分）
答案:
(1).產(chǎn)生死鎖的原因:一是系統(tǒng)提供的資源數(shù)量有限,不能滿足每個(gè)進(jìn)程的使用(5分);二是多道程序運(yùn)行時(shí),進(jìn)程推進(jìn)順序不合理(5分).
(2)產(chǎn)生死鎖的必要條件是:
1)互斥條件(2.5分)
2)不剝奪條件(不可搶占)(2.5分)
3)部分分配(2.5分)
4)循環(huán)等待(2.5分)
(3)死鎖的處理:
1)死鎖的預(yù)防
2)死鎖的避免
3)死鎖的檢測(cè)
4)死鎖的解除
5)不做任何處理
(以上要點(diǎn)每答對(duì)1個(gè)給2.5分,答對(duì)4個(gè)及以上要點(diǎn)最多給10分)