操作系統(tǒng)實(shí)驗(yàn)講稿

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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