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