《操作系統(tǒng)課程設(shè)計(jì)》指導(dǎo)書

1、操作系統(tǒng)課程設(shè)計(jì)實(shí)驗(yàn)指導(dǎo)課程設(shè)計(jì)一：進(jìn)程調(diào)度1、 設(shè)計(jì)目的（1） 要求學(xué)生設(shè)計(jì)一個模擬進(jìn)程調(diào)度的算法（2） 理解進(jìn)程控制塊的結(jié)構(gòu)（3） 理解進(jìn)程運(yùn)行的并發(fā)性（4） 掌握進(jìn)程調(diào)度的三種基本算法注：三種算法任選一種編程實(shí)現(xiàn)。2、 設(shè)計(jì)要求在多道程序運(yùn)行環(huán)境下，進(jìn)程數(shù)目一般多于處理機(jī)數(shù)目，使得進(jìn)程要通過競爭來使用處理機(jī)。這就要求系統(tǒng)能按某種算法，動態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個進(jìn)程，使之運(yùn)行，分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。一個進(jìn)程被創(chuàng)建后，系統(tǒng)為了便于對進(jìn)程進(jìn)行管理，將系統(tǒng)中的所有進(jìn)程按其狀態(tài)，將其組織成不同的進(jìn)程隊(duì)列。于是系統(tǒng)有運(yùn)行進(jìn)程隊(duì)列、就緒進(jìn)程隊(duì)列和各種事件的進(jìn)程等待隊(duì)列。進(jìn)程

2、調(diào)度的功能就是從就緒隊(duì)列中挑選一個進(jìn)程到處理機(jī)上運(yùn)行。進(jìn)程調(diào)度的算法有多種，常用的有優(yōu)先級調(diào)度算法、先來先服務(wù)算法、時(shí)間片輪轉(zhuǎn)算法。進(jìn)程是程序在處理機(jī)上的執(zhí)行過程。進(jìn)程存在的標(biāo)識是進(jìn)程控制塊(PCB)，進(jìn)程控制塊結(jié)構(gòu)如下：Typeedef struct node Char name10; /*進(jìn)程標(biāo)識符*/ Int prio; /*進(jìn)程優(yōu)先數(shù)*/ Int round; /*進(jìn)程時(shí)間片輪轉(zhuǎn)時(shí)間片*/ Int cputime /*進(jìn)程占用CPU時(shí)間*/ Int needtime /*進(jìn)程到完成還需要的時(shí)間*/ Int count; /*計(jì)數(shù)器*/ Char state; /*進(jìn)程的狀態(tài)*/ Str

3、uct node *next; /*鏈指針*/PCB;系統(tǒng)創(chuàng)建一個進(jìn)程，就是由系統(tǒng)為某個程序設(shè)置一個PCB，用于對該進(jìn)程進(jìn)行控制和管理。進(jìn)程任務(wù)完成，由系統(tǒng)收回其PCB，該進(jìn)程便消亡。每個進(jìn)程可以有三個狀態(tài)：運(yùn)行態(tài)、就緒態(tài)和完成狀態(tài)。用VC編寫一個程序?qū)崿F(xiàn)進(jìn)程調(diào)度算法，模擬進(jìn)程調(diào)度的過程，加深對進(jìn)程控制塊概念和進(jìn)程調(diào)度算法的理解。（1） 進(jìn)程調(diào)度算法采用優(yōu)先數(shù)調(diào)度算法。（2） 采用動態(tài)優(yōu)先數(shù)法確定進(jìn)程的優(yōu)先級別。（3） 設(shè)計(jì)三個鏈隊(duì)列，分別用來表示運(yùn)行隊(duì)列、就緒隊(duì)列和完成隊(duì)列。（4） 用戶輸入進(jìn)程標(biāo)識符以及進(jìn)程所需要的時(shí)間，申請空間存放進(jìn)程PCB信息。優(yōu)先數(shù)調(diào)度算法為每個進(jìn)程設(shè)一個優(yōu)先數(shù)，它總

4、是把處理機(jī)給就緒隊(duì)列中具有最高優(yōu)先權(quán)的進(jìn)程。常用的算法有靜態(tài)優(yōu)先數(shù)法和動態(tài)優(yōu)先數(shù)法。動態(tài)優(yōu)先數(shù)法，使進(jìn)程的優(yōu)先權(quán)隨時(shí)間而改變。初始的進(jìn)程優(yōu)先數(shù)取決于進(jìn)程運(yùn)行所需要的時(shí)間，時(shí)間大，則優(yōu)先數(shù)低?？刹扇⑦M(jìn)程優(yōu)先數(shù)定為一個較大的數(shù)（50）減去進(jìn)程運(yùn)行所需要的時(shí)間。隨著進(jìn)程的運(yùn)行對優(yōu)先數(shù)進(jìn)行調(diào)整，每次運(yùn)行時(shí)都是從就緒隊(duì)列中選取優(yōu)先數(shù)最大的進(jìn)程運(yùn)行，所以，就將就緒隊(duì)列按照優(yōu)先數(shù)的大小從高到低排序，這樣，每次選隊(duì)首進(jìn)程即可。進(jìn)程每執(zhí)行一次，優(yōu)先數(shù)減一個數(shù)（自定），CPU時(shí)間數(shù)加1，進(jìn)程還需要的時(shí)間減1。如果進(jìn)程所需時(shí)間為0，說明進(jìn)程運(yùn)行完畢，將其狀態(tài)變?yōu)橥瓿蔂顟B(tài)“F”，將此進(jìn)程PCB插入到完成隊(duì)列中，若就

5、緒隊(duì)列不空，則將就緒隊(duì)列中的第一個PCB變?yōu)檫\(yùn)行狀態(tài)。進(jìn)程若沒有完成，則將其優(yōu)先數(shù)和就緒隊(duì)列中的第一個PCB的優(yōu)先數(shù)作比較，如果小，則將其變?yōu)榫途w態(tài)，插入到就緒隊(duì)列中適當(dāng)?shù)奈恢?，將就緒隊(duì)列中的第一個PCB變?yōu)檫\(yùn)行態(tài)投入運(yùn)行，重復(fù)上述過程，直到就緒隊(duì)列為空，所以進(jìn)程成為完成狀態(tài)為止。1 時(shí)間片輪轉(zhuǎn)算法完成進(jìn)程的調(diào)度 設(shè)計(jì)要求：（1）進(jìn)程調(diào)度算法采用時(shí)間片輪轉(zhuǎn)算法。（2）設(shè)計(jì)三個鏈隊(duì)列，分別用來表示運(yùn)行隊(duì)列、就緒隊(duì)列和完成隊(duì)列。（3）用戶輸入進(jìn)程標(biāo)識符以及進(jìn)程所需要的時(shí)間，申請空間存放進(jìn)程PCB信息。（4）輸出格式和上面的一樣時(shí)間片輪轉(zhuǎn)調(diào)度：具體做法是調(diào)度程序每次把CPU分配給就緒隊(duì)列首進(jìn)程使用一

6、個時(shí)間片。當(dāng)這個時(shí)間片結(jié)束時(shí)，就強(qiáng)迫一個進(jìn)程讓出處理器，讓它排列到就緒隊(duì)列的尾部，等候下一輪的調(diào)度。實(shí)現(xiàn)這種調(diào)度要使用一個間隔時(shí)鐘。當(dāng)一個進(jìn)程開始運(yùn)行時(shí)，就將時(shí)間片的值置入間隔時(shí)鐘內(nèi)，當(dāng)發(fā)生間隔時(shí)鐘中斷時(shí)，就表明該進(jìn)程連續(xù)運(yùn)行的時(shí)間已超過一個規(guī)定的時(shí)間片。此時(shí)，中斷處理程序就通知處理器調(diào)度進(jìn)行處理器的切換工作。2 用先來先服務(wù)算法完成進(jìn)程的調(diào)度 設(shè)計(jì)要求：（1）進(jìn)程調(diào)度算法采用先來先服務(wù)算法。（2）設(shè)計(jì)三個鏈隊(duì)列，分別用來表示運(yùn)行隊(duì)列、就緒隊(duì)列和完成隊(duì)列。（3）用戶輸入進(jìn)程標(biāo)識符以及進(jìn)程所需要的時(shí)間，申請空間存放進(jìn)程PCB信息。（4）輸出格式和上面的一樣先來先服務(wù)算法：按照進(jìn)程進(jìn)入就緒隊(duì)列的先

7、后次序來分配處理器。先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先被挑選，運(yùn)行進(jìn)程一旦占有處理器將一直運(yùn)行下去直到運(yùn)行結(jié)束或被阻塞，這是一種非剝奪式調(diào)度。課程設(shè)計(jì)二：磁盤調(diào)度1、 設(shè)計(jì)目的（1） 要求學(xué)生設(shè)計(jì)一個模擬磁盤調(diào)度的程序。（2） 理解磁盤調(diào)度過程中的三個時(shí)間段（3） 理解磁盤調(diào)度的三種算法2、 實(shí)驗(yàn)原理共享設(shè)備的典型代表為磁盤，磁盤物理塊的地址由柱面號、磁頭號、扇區(qū)號來指定，完成磁盤某一個物理塊的訪問要經(jīng)過三個階段：尋道時(shí)間Ts、旋轉(zhuǎn)延遲時(shí)間Tw和讀寫時(shí)間Trw。尋道時(shí)間Ts是磁頭從當(dāng)前磁道移動到目標(biāo)磁道所需要的時(shí)間；旋轉(zhuǎn)延遲時(shí)間Tw是當(dāng)磁頭停留在目標(biāo)磁道后，目標(biāo)物理塊從當(dāng)前位置旋轉(zhuǎn)到磁頭位置的時(shí)間；讀寫

8、時(shí)間Trw是目標(biāo)物理塊內(nèi)容與內(nèi)存中對應(yīng)交換的時(shí)間。磁盤調(diào)度的原則是公平和高吞吐量，衡量指標(biāo)有訪問時(shí)間T和平均訪問時(shí)間Ta: T=Ts+Tw+Trw Ta=Tsa+Twa+Trwa尋道時(shí)間和旋轉(zhuǎn)延遲時(shí)間成為調(diào)度算法的主要考慮因素。減少訪問時(shí)間就是要減少尋道時(shí)間和旋轉(zhuǎn)延遲時(shí)間。3、 設(shè)計(jì)要求（1） 設(shè)計(jì)一個函數(shù)完成先來先服務(wù)的磁盤調(diào)度功能。（2） 設(shè)計(jì)一個函數(shù)完成最短尋道時(shí)間優(yōu)先的磁盤調(diào)度功能。（3） 設(shè)計(jì)一個函數(shù)完成電梯算法的磁盤調(diào)度功能。（4） 從鍵盤輸入一組磁盤訪問序列，選擇三種算法中的一種，輸出其磁頭移動的總的磁道數(shù)課程設(shè)計(jì)三：主存空間的分配與回收1、 設(shè)計(jì)目的主存是中央處理器能直接存取指

9、令和數(shù)據(jù)的存儲器，能否合理地利用主存，在很大程度上將影響到整個計(jì)算機(jī)系統(tǒng)的性能。主存分配是指在多道作業(yè)和多進(jìn)程環(huán)境下，如何共享主存空間。主存回收是指當(dāng)作業(yè)執(zhí)行完畢或進(jìn)程運(yùn)行結(jié)束后將主存空間歸還給系統(tǒng)。主存分配與回收的實(shí)現(xiàn)是與主存儲器的管理方式有關(guān)。本次設(shè)計(jì)主要是為了幫助理解主存空間的分配與回收的幾種算法。（1） 掌握最先適應(yīng)分配算法（2） 掌握最優(yōu)適應(yīng)分配算法（3） 掌握最壞適應(yīng)分配算法2、 設(shè)計(jì)要求用戶提出內(nèi)存空間請求，系統(tǒng)根據(jù)申請者要求，按照最先適應(yīng)算法的分配策略分析主存空間的使用情況，找出能滿足請求的空閑區(qū)，分給申請者，當(dāng)程序執(zhí)行完畢時(shí)，系統(tǒng)要收回它所占用的內(nèi)存空間。建立空閑區(qū)數(shù)據(jù)文件，

10、空閑區(qū)數(shù)據(jù)文件包括若干行，每行有兩個字段：起始地址、內(nèi)存塊大?。ň鶠檎麛?shù)），各字段以逗號隔開。下面是一個空閑區(qū)數(shù)據(jù)文件的示例：0， 1010， 0818， 1028， 0634， 1044， 09讀取空閑區(qū)數(shù)據(jù)文件，建立空閑區(qū)表并在屏幕上顯示空閑區(qū)內(nèi)存狀態(tài)，空閑區(qū)表記錄了可供分配的空閑內(nèi)存的起始地址和大小，用標(biāo)志位指出該分區(qū)是否是未分配的空閑區(qū)。 接收用戶的內(nèi)存申請，格式為：作業(yè)名、申請空間的大小。按照內(nèi)存分配算法中的一種方法選擇一個空閑區(qū)，分割并分配，修改空閑區(qū)表，填寫內(nèi)存已分配區(qū)表（起始地址、長度、標(biāo)志位），其中標(biāo)志位的一個作用是指出該區(qū)域分配給哪個作業(yè)。作業(yè)結(jié)束后回收內(nèi)存。分區(qū)表的結(jié)構(gòu)如

11、下：Typedef struct node Int start; Int length; Char tag20;job設(shè)計(jì)內(nèi)容：1 設(shè)計(jì)一個內(nèi)存分配回收的函數(shù)使用最優(yōu)適應(yīng)分配算法2 設(shè)計(jì)一個內(nèi)存分配回收的函數(shù)使用最壞適應(yīng)分配算法3設(shè)計(jì)一個內(nèi)存分配回收的函數(shù)使用最先適應(yīng)分配算法用戶提出內(nèi)存空間請求，系統(tǒng)根據(jù)申請者要求，分別使用上述算法分析內(nèi)存空間的使用情況，找出合適的空閑區(qū)，分給申請者，當(dāng)作業(yè)執(zhí)行完畢后，系統(tǒng)收回它所占用的內(nèi)存空間。課程設(shè)計(jì)四：P,V操作設(shè)計(jì)要求：編程模擬實(shí)現(xiàn)下列任一問題：1桌上有一盤子，可以存放一個水果。爸爸總是放蘋果到盤子中，而媽媽總是放香蕉到盤子中；一個兒子專等吃盤中的香蕉

12、，一個女兒專等吃盤中的蘋果。請用P，V操作實(shí)現(xiàn)上述問題的解。分析：在本題中，爸爸、媽媽、兒子和女兒共用一個盤子，盤子一次只能放一個水果。當(dāng)盤子為空時(shí)，爸爸和媽媽都可以試著將一個水果放入盤中，但一次只能有一人成功放入水果。若放入盤子中的是香蕉，則允許兒子吃，女兒必須等待；若放入盤子中的是蘋果，則允許女兒吃，兒子必須等待。 在本題中，應(yīng)設(shè)置3個信號量dish、apple、banaba，信號量dish表示盤子是否為空，其初值為1；信號量apple表示盤中是否有蘋果，其初值為0；信號量banana表示盤中是否有香蕉，其初值為0。進(jìn)程之間的同步描述如下：Semaphore dish=1;Semaphor

13、e apple,banana=0;Main() cobegin father(); mother(); son(); daughter(); coendFather() mather() while(true) while(true) p(dish); p(dish); 將蘋果放入盤中； 將香蕉放入盤中； v(apple); v(banana); Son() daughter() while(true) while(true) p(banana); p(apple); 從盤中取出香蕉； 從盤中取出蘋果； v(dish); v(dish); 吃香蕉； 吃蘋果； 2、設(shè)公共汽車上，司機(jī)和售票員的活

14、動分別是：司機(jī)的活動：啟動車輛；正常行車；到站停車。售票員的活動：關(guān)車門；售票；開車門。在汽車不斷的到站、停站、行駛過程中，用信號量和P,V操作實(shí)現(xiàn)它們的同步。分析：在汽車行駛過程中，司機(jī)活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后向司機(jī)發(fā)開車信號，司機(jī)接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開車門讓乘客下車。因此司機(jī)啟動車輛的動作必須與售票員關(guān)車門的動作取得同步；售票員開車門的動作也必須與司機(jī)停車取得同步。在本題中，應(yīng)設(shè)置兩個信號量s1、s2，s1表示是否允許司機(jī)啟動汽車，其初值為0；s2表示是否允許售票員開車門，其初值為0。這兩個活動的同步

15、用P,V原語描述如下：Semaphore s1,s2=0; Main() cobegin driver(); busman(); coendDriver() busman() while(true) while(true) p(s1); 關(guān)車門； 啟動車輛； v(s1); 正常行車； 售票； 到站停車； p(s2); v(s2); 開車門； 上下乘客； 3,、讀者寫者問題（算法略）4、多個生產(chǎn)者與消費(fèi)者問題（算法略）5、哲學(xué)家就餐問題（算法略）課程設(shè)計(jì)五：銀行家算法1、 設(shè)計(jì)目的(1) 了解多道程序系統(tǒng)中，多個進(jìn)程并發(fā)執(zhí)行的資源分配。(2) 掌握死鎖產(chǎn)生的原因、產(chǎn)生死鎖的必要條件和處理死鎖的基

16、本方法。(3) 掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。(4) 掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略。(5) 理解避免死鎖在當(dāng)前計(jì)算機(jī)系統(tǒng)不常使用的原因2、 設(shè)計(jì)要求在多道程序系統(tǒng)中，雖可借助于多個進(jìn)程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)-死鎖。死鎖是指多個進(jìn)程在運(yùn)行中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都將無法向前推進(jìn)。銀行家算法是最具有代表性的避免死鎖的算法，它的基本思想是分配資源之前，判斷系統(tǒng)是否是安全的，若是才分配資源。設(shè)計(jì)一個n個并發(fā)進(jìn)程共享M個系統(tǒng)資源的程序?qū)崿F(xiàn)銀行家算法。要求包含：(1) 簡單的選擇界面(2) 能顯示當(dāng)前系統(tǒng)資源的占用和剩余情況(3) 為進(jìn)程分配資源，如果進(jìn)程要求的資源大于系統(tǒng)剩余的資