操作系統(tǒng)實驗講稿

1、操作系統(tǒng)實習·本次實習的要求：1總學時為36學時，要求每位同學確保在此時間內(nèi)完成實驗。2實習結束時，由老師上機驗收，并上交實習報告。驗收成績占75%，實習報告成績占25%。3實習報告內(nèi)容（紙質(zhì)報告）：（1） 實習題目。（2）實習內(nèi)容及設計思想：設計思路、主要數(shù)據(jù)結構、主要代碼結構及代碼段分析。（3）上機實驗所用平臺及相關軟件。（可以采用任何軟件平臺設計實現(xiàn)）（4）調(diào)試過程：測試數(shù)據(jù)設計、測試結果分析。（5）總結：實習中遇到的問題及解決方法、實習中產(chǎn)生的錯誤及原因分析、實習體會及收獲。4. 實習內(nèi)容：完成下述實習題的設計，或者23個同學一組設計一個操作系統(tǒng)。5注意：實習二及實習三中，有

2、兩個算法的實現(xiàn)思想類似，要求完成不同思想的兩個算法。如內(nèi)存管理用位示圖實現(xiàn)，則外存管理應采用連續(xù)外存分配方法，不能采用位示圖。實習一 處理器調(diào)度一、實習內(nèi)容選擇一個調(diào)度算法，實現(xiàn)處理器調(diào)度。二、實習目的本實習模擬在單處理器環(huán)境下的處理器調(diào)度，加深了解處理器調(diào)度的工作。三、實習題目本實習有兩題，可任選一題。第一題：設計一個按優(yōu)先數(shù)調(diào)度算法實現(xiàn)處理器調(diào)度的程序。提示：(1)假定系統(tǒng)有5個進程，每個進程用一個PCB來代表。PCB的結構為：·進程名如P1P5。·指針按優(yōu)先數(shù)的大小把5個進程連成隊列，用指針指出下一個進程PCB的首地址。·要求運行時間假設進程需要運行的單位時

3、間數(shù)。·優(yōu)先數(shù)賦予進程的優(yōu)先數(shù)，調(diào)度時總是選取優(yōu)先數(shù)大的進程先執(zhí)行。·狀態(tài)假設兩種狀態(tài)：就緒和結束，用R表示就緒，用E表示結束。初始狀態(tài)都為就緒狀態(tài)。(2) 每次運行之前，為每個進程任意確定它的“優(yōu)先數(shù)”和“要求運行時間”。(3) 處理器總是選擇隊首進程運行。采用動態(tài)改變優(yōu)先數(shù)的辦法，進程每運行1次，優(yōu)先數(shù)減1，要求運行時間減1。(4) 進程運行一次后，若要求運行時間不等于0，則將它加入就緒隊列，否則，將狀態(tài)改為“結束”，退出隊列。(5) 若就緒隊列為空，結束，否則轉(zhuǎn)到(3)重復。要求能接受鍵盤輸入的進程優(yōu)先數(shù)及要求運行時間，能顯示每次進程調(diào)度的情況，如哪個進程在運行，哪些

4、進程就緒，就緒進程的排列情況。第二題：設計一個按時間片輪轉(zhuǎn)法實現(xiàn)處理器調(diào)度的程序提示：（1）假定系統(tǒng)有5個進程，每個進程用一個PCB來代表。PCB的結構為：·進程名如Q1Q5。·指針把5個進程連成隊列，用指針指出下一個進程PCB的首地址。·要求運行時間假設進程需要運行的單位時間數(shù)。·已運行時間進程已運行的單位時間數(shù)，初始值為0。·狀態(tài)假設兩種狀態(tài)，就緒和結束，用R表示就緒，用E表示結束。初始狀態(tài)都為就緒狀態(tài)。(2) 每次運行之前，為每個進程任意確定它的“要求運行時間”。(3) 把5個進程按順序排成循環(huán)隊列，用指針指出隊列連接情況。用一個標志單元

5、記錄輪到運行的進程。處理器調(diào)度總是選擇標志單元指示的進程運行，對所指的進程，將其“已運行時間”加1。(4) 進程運行一次后，若“要求運行時間”等于“已運行時間”，則將狀態(tài)改為“結束”，退出隊列，否則將繼續(xù)輪轉(zhuǎn)。(5) 若就緒隊列為空，結束，否則轉(zhuǎn)到(3)重復。要求能接受鍵盤輸入的進程要求運行時間，能顯示每次進程調(diào)度的情況，如哪個進程在運行，哪些進程就緒，就緒進程的排列情況。實習二 主存空間的分配和回收一、實習內(nèi)容主存儲器空間的分配和回收。二、實習目的通過本實習幫助理解在不同的存儲管理方式下應怎樣進行存儲空間的分配和回收。三、實習題目本實習有兩題，可任選一題。第一題：可變分區(qū)管理方式下采用首次適

6、應算法實現(xiàn)主存分配和回收提示：(1) 可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存容量查看是否有足夠的空閑空間，若有，則按需分配，否則，作業(yè)無法裝入。假定內(nèi)存大小為128K(可輸入)，空閑區(qū)說明表格式為：·起始地址指出空閑區(qū)的起始地址；·長度一個連續(xù)空閑區(qū)的長度；·狀態(tài)有兩種狀態(tài)，一種是“未分配”狀態(tài)；另一種是“空表目”狀態(tài)，表示該表項目前沒有使用。(2) 采用首次適應算法分配回收內(nèi)存空間。運行時，輸入一系列分配請求和回收請求。要求能接受來自鍵盤的空間申請及釋放請求，能顯示分區(qū)分配及回收后的內(nèi)存布局情況。第二題：在分頁

7、管理方式下采用位示圖來表示主存分配情況，實現(xiàn)主存分配和回收提示：(1) 假定系統(tǒng)的主存被分成大小相等的64個塊，用0/1對應空閑/占用。(2) 當要裝入一個作業(yè)時，根據(jù)作業(yè)對主存的需求量，先查空閑塊數(shù)是否能滿足作業(yè)要求，若能滿足，則查位示圖，修改位示圖和空閑塊數(shù)。位置與塊號的對應關系為：塊號=j*8+i，其中i表示位，j表示字節(jié)。根據(jù)分配的塊號建立頁表。頁表包括兩項：頁號和塊號。(3) 回收時，修改位示圖和空閑塊數(shù)。要求能接受來自鍵盤的空間申請及釋放請求，能顯示位示圖和空閑塊數(shù)的變化，能顯示進程的頁表。實習三 磁盤存儲空間的分配和回收一、實習內(nèi)容模擬磁盤空閑空間的表示方法，以及模擬實現(xiàn)磁盤空間

8、的分配和回收。二、實習目的磁盤初始化時把磁盤存儲空間分成許多塊（扇區(qū)），這些空間可以被多個用戶共享。用戶作業(yè)在執(zhí)行期間常常要在磁盤上建立文件或把已經(jīng)建立在磁盤上的文件刪去，這就涉及到磁盤存儲空間的分配和回收。一個文件存放到磁盤上，可以組織成順序文件（連續(xù)文件）、鏈接文件（串聯(lián)文件）、索引文件等，因此，磁盤存儲空間的分配有兩種方式，一種是分配連續(xù)的存儲空間，另一種是可以分配不連續(xù)的存儲空間。怎樣有效地管理磁盤存儲空間是操作系統(tǒng)應解決的一個重要問題，通過本實習使學生掌握磁盤存儲空間的分配和回收算法。三、實習題目本實習有三個題目，可以任選一個，但不能與內(nèi)存管理的題目類似。第一題：連續(xù)磁盤存儲空間的分

9、配和回收提示：(1) 要在磁盤上建立順序文件時，必須把按序排列的邏輯記錄依次存放在磁盤的連續(xù)存儲空間中?？杉俣ù疟P初始化時，已把磁盤存儲空間劃分成若干等長的塊（扇區(qū)），按柱面號和盤面號的順序給每一塊確定一個編號。隨著文件的建立、刪除、磁盤存儲空間被分成許多區(qū)（每一區(qū)包含若干塊），有的區(qū)存放著文件，而有的區(qū)是空閑的。當要建立順序文件時必須找到一個合適的空閑區(qū)來存放文件記錄，當一個文件被刪除時，則該文件占用的區(qū)應成為空閑區(qū)。為此可用一張空閑區(qū)表來記錄磁盤存儲空間中尚未占用的部分，格式如下：序 號起始空閑塊號空閑塊個數(shù)狀 態(tài)156未 分 配2143未 分 配32130未 分 配4空 表 目(2) 建

10、立文件時，先查找空閑區(qū)表，從狀態(tài)為“未分配”的表項中找出一個塊數(shù)能滿足要求的區(qū)，由起始空閑塊號能依次推得可使用的其它塊號。若不需要占用該區(qū)的所有塊時，則剩余的塊仍應為未分配的空閑塊，這時要修改起始空閑塊號和空閑塊數(shù)。若占用了該區(qū)的所有塊，則相應登記欄中的狀態(tài)修改成“空表目”。刪除一個文件時，需要考慮空閑塊的合并情況。磁盤存儲空間的分配和回收算法類似于主存儲器的可變分區(qū)方式的分配和回收。同學們可參考實習二的第一題。(3) 當找到空閑塊后，必須啟動磁盤把信息存放到指定的塊中，啟動磁盤必須給出由三個參數(shù)組成的物理地址：盤面號、柱面號和物理記錄號（即扇區(qū)號）。故必須把找到的空閑塊號換算成磁盤的物理地址

11、。為了減少移臂次數(shù)，磁盤上的信息按柱面上各磁道順序存放?，F(xiàn)假定一個盤組共有200個柱面，（編號0-199）每個柱面有20個磁道（編號0-19，同一柱面上的各磁道分布在各盤面上，故磁道號即盤面號。），每個磁道被分成等長的6個物理記錄（編號0-5，每個盤面被分成若干個扇區(qū)，故每個磁道上的物理記錄號即為對應的扇區(qū)號）。那么，空閑塊號與磁盤物理地址的對應關系如下：則 物理記錄號 = 空閑塊號 % 6磁道號=（空閑塊號 / 6 ）% 20 柱面號=（空閑塊號 / 6）/20(4) 刪除一個文件時，從文件目錄表中可得到該文件在磁盤上的起始地址和邏輯記錄個數(shù)，假定每個邏輯記錄占磁盤上的一塊，則可推算出歸還后

12、的起始空閑塊號和塊數(shù)，登記到空閑區(qū)表中。換算關系如下：起始空閑塊號=（柱面號´20+磁道號）´6+物理記錄號空閑塊數(shù)=邏輯記錄數(shù)(5) 請設計磁盤存儲空間的分配和回收程序，要求把分配到的空閑塊轉(zhuǎn)換成磁盤物理地址，把歸還的磁盤空間轉(zhuǎn)換成空閑塊號。要求能接受來自鍵盤的空間申請及釋放請求，能顯示或打印分配及回收后的空閑區(qū)表以及分配到的磁盤空間的起始物理地址。第二題：用位示圖管理磁盤存儲空間提示：(1) 為了提高磁盤存儲空間的利用率，可在磁盤上組織成鏈接文件、索引文件，這類文件可以把邏輯記錄存放在不連續(xù)的存儲空間。為了表示哪些磁盤空間已被占用，哪些磁盤空間是空閑的，可用位示圖來指出

13、。位示圖由若干字節(jié)構成，每一位與磁盤上的一塊對應，“1”狀態(tài)表示相應塊已占用，“0”狀態(tài)表示該塊為空閑。位示圖的形式與實習二中的位示圖一樣，但要注意，對于主存儲空間和磁盤存儲空間應該用不同的位示圖來管理，絕不可混用。(2) 申請一塊磁盤空間時，由分配程序查位示圖，找出一個為“0”的位，計算出這一位對應塊的磁盤物理地址，且把該位置成占用狀態(tài)“1”。假設現(xiàn)在有一個盤組共8個柱面，每個柱面有2個磁道（盤面），每個磁道分成4個物理記錄。那么，當在位示圖中找到某一字節(jié)的某一位為“0”時，這個空閑塊對應的磁盤物理地址為：柱面號=字節(jié)號磁道號= 位數(shù) / 4物理記錄號= 位數(shù) % 4(3) 歸還一塊磁盤空間

14、時，由回收程序根據(jù)歸還的磁盤物理地址計算出歸還塊在位示圖中的對應位，把該位置成“0”。按照（2）中假設的盤組，歸還塊在位示圖中的位置計算如下：字節(jié)號=柱面號位數(shù)=磁道號´4+物理記錄號(4) 設計申請磁盤空間和歸還磁盤空間的程序。要求能接受來自鍵盤的空間申請及釋放請求，要求能顯示或打印程序運行前和運行后的位示圖；分配時把分配到的磁盤空間的物理地址顯示或打印出來，歸還時把歸還塊對應于位示圖的字節(jié)號和位數(shù)顯示或打印出來。第三題：模擬UNIX系統(tǒng)的空閑塊成組鏈接法，實現(xiàn)磁盤存儲空間的管理提示：(1) 假定磁盤存儲空間已被劃分成長度為n的等長塊，共有M塊可供使用。UNIX系統(tǒng)中采用空閑塊成組

15、鏈接的方法來管理磁盤存儲空間，將磁盤中的每N個空閑塊（N<M）分成一組，最后一組可以不足N塊，每組的第一塊中登記了下一組空閑塊的塊數(shù)和塊號，第一組的塊數(shù)和塊號登記在專用塊中，登記的格式如下：0空閑塊數(shù)k1空閑塊號12空閑塊號2K空閑塊號k當?shù)谝豁梼?nèi)容為“0”時，則第二項起指出的空閑塊是最后一組。（2）可用二維數(shù)組A 0M-1 0n-1來模擬管理磁盤空間，用Ai表示第I塊，第0塊A0作為專用塊。(3) 成組鏈接的分組情況記錄在磁盤物理塊中，為了查找鏈接情況，必須把它們讀入主存，故當磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容復制到主存中。定義一個數(shù)組MA存放專用塊內(nèi)容，即MA: =A0。申請一塊磁盤空

16、間時，查MA，從中找出空閑塊號，當一組的空閑塊只剩第一塊時，則應把該塊中指出的下一組的空閑塊數(shù)和塊號復制到專用塊中，然后把該塊分配給申請者。當一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復制到主存，再為申請者分配。 (4) 歸還一塊時給出歸還的塊號，若當前組不滿規(guī)定塊數(shù)時，將歸還塊登記入該組；若當前組已滿，則另建一新組，這時歸還塊作為新一組的第一塊，應把主存中登記的一組鏈接情況MA復制到歸還塊中，然后在MA重新登記一個新組。(5) 設計分配和歸還磁盤空間的程序。要求能接受來自鍵盤的空間申請及釋放請求，能顯示或打印分配的磁盤空間的塊號，在完成一次分配或歸還后能顯示或打印各空閑塊組的情況（

17、各組的空閑塊數(shù)和塊號）。本實習省去了塊號與物理地址之間的轉(zhuǎn)換工作，而在實際的系統(tǒng)中必須進行塊號與物理地址的轉(zhuǎn)換工作。實驗四 銀行家算法實現(xiàn)一、實習內(nèi)容編寫實現(xiàn)銀行家算法，實現(xiàn)資源的安全分配。二、實習目的通過本實驗熟悉銀行家算法，對預防死鎖有更深刻的認識。三、實驗內(nèi)容初始狀態(tài)下，設置數(shù)據(jù)結構存儲可利用資源向量（Available），最大需求矩陣（MAX），分配矩陣（Allocation），需求矩陣（Need），輸入待分配進程隊列和所需資源。設計安全性算法，設置工作向量表示系統(tǒng)可提供進程繼續(xù)運行的可利用資源數(shù)目。如果進程隊列可以順利執(zhí)行打印輸出資源分配情況，如果進程隊列不能順利執(zhí)行打印輸出分配過程，提示出現(xiàn)死鎖位置。實驗五 模擬頁面地址重定位一、實驗目的：1、 編寫和調(diào)試模擬實現(xiàn)頁式地址重定位。2、 加深理解頁式地址重定位技術在多道程序設計中的作用和意義。二、實驗原理：當進程在CPU上運行時，如指令中涉及邏輯地址時，操作系統(tǒng)自動根據(jù)頁長得到頁號和頁內(nèi)偏移，把頁內(nèi)偏移拷貝到物理地址寄存器，再根據(jù)頁號，查頁表，得到該頁在內(nèi)存中的塊號，把塊號左移頁長的位數(shù)，寫到物理地址寄存器。三、實驗內(nèi)容：1、設計頁表結構;2、 設計地址重定位算法3、 有良好的人機對話界面編號： 實驗一二三四五六七八九十總評教師簽名成績武漢大學計算機學院課程實驗(設計)報告專業(yè)(班)： 學 號： 姓 名： 課程