操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)-140401-3

1、o5persi 丁 yg長(zhǎng)春工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院操作系統(tǒng)是信息科學(xué)、計(jì)算機(jī)軟件的核心和基礎(chǔ)學(xué)科，對(duì)它的掌握程度， 決定著計(jì)算機(jī)學(xué)習(xí)者的發(fā)展水平及方向。同時(shí)它是一門(mén)實(shí)踐性很強(qiáng)的課程，不僅 要學(xué)習(xí)書(shū)木上的理論，而且必須動(dòng)手實(shí)踐才能對(duì)操作系統(tǒng)基木原理真止理解。木 課程提供實(shí)驗(yàn)課，其口的在于加深學(xué)生對(duì)教學(xué)內(nèi)容的理解，培養(yǎng)學(xué)生初步掌握操 作系統(tǒng)基木功能的設(shè)計(jì)方法及其實(shí)現(xiàn)過(guò)程。為使學(xué)生能更好的了解操作系統(tǒng)，木 次實(shí)驗(yàn)安排了熟悉linux操作系統(tǒng)的基木特性，在linux系統(tǒng)下進(jìn)行實(shí)驗(yàn)題目的 設(shè)計(jì)與實(shí)現(xiàn)。實(shí)驗(yàn)1熟悉linux環(huán)境11.1實(shí)驗(yàn)冃的11.2實(shí)驗(yàn)內(nèi)容11.3實(shí)驗(yàn)預(yù)習(xí)內(nèi)容11.4 linux簡(jiǎn)

2、單命令簡(jiǎn)介11.5 linux的全屏幕程序應(yīng)用41.6使用編輯器vi編輯文件5實(shí)驗(yàn)2進(jìn)程調(diào)度算法設(shè)計(jì)72.1實(shí)驗(yàn)冃的72.2實(shí)驗(yàn)內(nèi)容72.3實(shí)驗(yàn)要求72.4實(shí)驗(yàn)預(yù)習(xí)內(nèi)容72. 5實(shí)驗(yàn)指導(dǎo)9實(shí)驗(yàn)3進(jìn)程間通信算法設(shè)計(jì)183實(shí)驗(yàn)?zāi)康?83.2實(shí)驗(yàn)內(nèi)容183.3實(shí)驗(yàn)耍求183.4實(shí)驗(yàn)預(yù)習(xí)內(nèi)容183.5實(shí)驗(yàn)指導(dǎo)19351共享內(nèi)存程序設(shè)計(jì)193.5.2消息隊(duì)列程序設(shè)計(jì)233.5.3管道通信程序設(shè)計(jì)27實(shí)驗(yàn)4死鎖與哲學(xué)家就餐問(wèn)題324.1采用預(yù)先分配法預(yù)防死鎖的哲學(xué)家就餐問(wèn)題324.1.1實(shí)驗(yàn)?zāi)康?24.1.2實(shí)驗(yàn)要求324.1.3實(shí)驗(yàn)步驟324.2采用有序分配法預(yù)防死鎖的哲學(xué)家就餐問(wèn)題33421實(shí)驗(yàn)冃的3

3、34.2.2實(shí)驗(yàn)要求334.2.3實(shí)驗(yàn)步驟334.3不預(yù)防死鎖情況卜的哲學(xué)家就餐問(wèn)題34431實(shí)驗(yàn)?zāi)康?44.3.2實(shí)驗(yàn)要求344.3.3實(shí)驗(yàn)步驟35實(shí)驗(yàn)5存儲(chǔ)管理算法設(shè)計(jì)365.1 內(nèi)存空間的分配和回收365.1.1實(shí)驗(yàn)?zāi)康?65.1.2實(shí)驗(yàn)內(nèi)容365.1.3實(shí)驗(yàn)要求365.1.4預(yù)習(xí)內(nèi)容：365.1.5實(shí)驗(yàn)指導(dǎo)375.2虛擬存儲(chǔ)管理395.2.1實(shí)驗(yàn)?zāi)康?95.2.2實(shí)驗(yàn)內(nèi)容395.2.3實(shí)驗(yàn)要求395.2.4預(yù)習(xí)內(nèi)容4()5.2.5實(shí)驗(yàn)指導(dǎo)40實(shí)驗(yàn)6同步機(jī)制-讀者與寫(xiě)者問(wèn)題426.1實(shí)驗(yàn)冃的426.2實(shí)驗(yàn)內(nèi)容426.3實(shí)驗(yàn)要求426.4預(yù)習(xí)內(nèi)容436.5實(shí)驗(yàn)指導(dǎo)(算法分析)436.5.1

4、讀者優(yōu)先436.5.2寫(xiě)者優(yōu)先476.5.3無(wú)優(yōu)先496.5.4設(shè)計(jì)并分析測(cè)試數(shù)據(jù)516.5.5程序功能及界面設(shè)計(jì)516.5.6函數(shù)設(shè)計(jì)建議51實(shí)驗(yàn)7假脫機(jī)打印程序與虛擬設(shè)備527.1實(shí)驗(yàn)冃的527.2實(shí)驗(yàn)要求537.3數(shù)據(jù)結(jié)構(gòu)分析537.4程序結(jié)構(gòu)54操作系統(tǒng)課程實(shí)驗(yàn)候選題目57操作系統(tǒng)課程實(shí)驗(yàn)報(bào)告要求59主要參考文獻(xiàn)60實(shí)驗(yàn)1熟悉linux環(huán)境1.1實(shí)驗(yàn)?zāi)康模?）熟悉linux下的基本操作，學(xué)會(huì)在linux環(huán)境下使用各種簡(jiǎn)單命令進(jìn) 行操作。（2）學(xué)會(huì)在linux環(huán)境下或者使用vi編輯器編輯簡(jiǎn)單的c語(yǔ)言程序，并 能對(duì)其編譯和調(diào)試。1.2實(shí)驗(yàn)內(nèi)容（1）登陸系統(tǒng)，并使用各種簡(jiǎn)單命令來(lái)實(shí)現(xiàn)基本的文

5、件操作并觀察linux 文件系統(tǒng)的特點(diǎn)；（2）寫(xiě)一c程序，并對(duì)該程序進(jìn)行編譯和鏈接，輸岀程序的運(yùn)行結(jié)果。1.3實(shí)驗(yàn)預(yù)習(xí)內(nèi)容參閱相關(guān)linux的命令參考手冊(cè)，熟悉linux下的操作命令。1.4 linux簡(jiǎn)單命令簡(jiǎn)介1.4.1命令的基本格式1、格式：$命令-命令選項(xiàng)參數(shù)1參數(shù)22、說(shuō)明：字段間用一個(gè)或多個(gè)空格分開(kāi)，linux對(duì)大小寫(xiě)敏感，只接受小 寫(xiě)命令。1.4.2常用命令1. who命令功能：可以列出當(dāng)前登錄到系統(tǒng)的所有用戶的登錄名、終端號(hào)和登錄吋間$ whodavid tty04 nov 28 08:27daniel ttyol nov28 08:302. man命令可以顯示在線電子文檔3.

6、 pwd顯示當(dāng)前目錄的絕對(duì)路徑名$pwd/usr/jamcs4. cd改變工作目錄$cd source （相對(duì)路徑）$cd /usr/david （絕對(duì)路徑）$cd $i1ome或者cd返回用戶主目錄5. mkdir創(chuàng)建目錄$mkdir memos在當(dāng)前目錄f創(chuàng)建子目錄$mkdir /sourcc/mcmos指定目錄的名字$mkdir - p xx/yy/zz創(chuàng)建多個(gè)分級(jí)目錄6. rmdir刪除目錄$ rmdir important刪除一個(gè)空目錄如果目錄不空，則無(wú)法刪除必須在父目錄或者更高層刪除了目錄7. is顯示指定目錄的內(nèi)容$ls列出當(dāng)前目錄內(nèi)容$ls source顯示目錄source的文

7、件列表$ls source/first. c顯示指定的文件$ls -a列出所有文件，包括隱藏文件$ls -r循環(huán)列出了目錄的內(nèi)容$ls -1按照長(zhǎng)格式列表，顯示文件的詳細(xì)信息total 3-rw-r-r- 1 david student 1026 jun25 12:30 123-rw-r-r- 1 david student 684 jun25 12:30 reportdrw-rr 1 david student 48jun25 12:30 momos文件類(lèi)型：第1列由10個(gè)字符組成，每行的第一個(gè)字符表示文件類(lèi)型。-：普通文件d:目錄文件b:塊設(shè)備文件，例如磁盤(pán)c:字符設(shè)備文件，例如打印機(jī)文件

8、的訪問(wèn)模式：9個(gè)字符表示，r:允許讀w:允許寫(xiě)x:允許執(zhí)行第一組允許所有者的讀、寫(xiě)和執(zhí)行權(quán)限。第二組允許用戶組的讀、寫(xiě)和執(zhí)行權(quán)限。第三組允許其他用戶的讀、寫(xiě)和執(zhí)行權(quán)限。如果是可執(zhí)行文件，標(biāo)記執(zhí)行許可權(quán)。& rm刪除文件rm既可以刪除文件，也可以刪除目錄。5命令沒(méi)有任何警告信息，當(dāng)刪除文件的時(shí)候，不出問(wèn)題的話，文件就 被刪除了。rm-i刪除文件前，確認(rèn)rm-r刪除指定的目錄及目錄中所有文件和了目錄9. cp復(fù)制文件格式：cp源目標(biāo)目的目標(biāo) 如果目的目標(biāo)已經(jīng)存在，那么他的內(nèi)容將被破壞。$cp f訂el file210. niv移動(dòng)文件、更改名字格式：mv源目標(biāo)目的目標(biāo)$mv filel f

9、ile2 （更改名字）cp和mv命令都可以接受多于兩個(gè)的參數(shù)，但最后參數(shù)必須是目錄$cp filel filc2 filc3 dircctoryl11. uptime命令：用來(lái)得到有關(guān)系統(tǒng)負(fù)載的大致數(shù)據(jù)。$uptime3:20pm up 2days, 2:41, 16 users, load average: 1. 90, 1. 43, 1. 33 uptime報(bào)告當(dāng)前的時(shí)間，系統(tǒng)已經(jīng)啟動(dòng)的時(shí)間以及有關(guān)任務(wù)負(fù)載的三個(gè)平 均數(shù)據(jù)（最后1分鐘，最后5分鐘，最后15秒），該數(shù)據(jù)是對(duì)cpu使用量的大致 接近。12. ps命令：生成一個(gè)報(bào)告，總結(jié)當(dāng)前進(jìn)程執(zhí)行的統(tǒng)計(jì)信息。該命令的選 項(xiàng)控制要列出的進(jìn)程和要

10、顯示的信息。最常用的格式就是$ps - of-e：顯示所有進(jìn)程-f：顯示詳細(xì)信息uidpidppid cstimettytime cmdroot00009:36:35? 0:00schcdjamcs8881131517:02:05tty610:02via. txt其中：uid：用戶idpid：進(jìn)程idppid：父進(jìn)程idc：當(dāng)前的調(diào)度程序的值stime：進(jìn)程的開(kāi)始時(shí)間tty：和進(jìn)程相關(guān)的終端time：總的cpu運(yùn)行時(shí)間cmd：進(jìn)程運(yùn)行的命令13. nice命令：指定運(yùn)行程序的優(yōu)先值。格式：nice - n +卜數(shù)字 命令例：$nicc - n 10 myprog$nice - n - 10 m

11、yprog14. rcnicc命令：指定進(jìn)程的優(yōu)先值。格式：rcnicc - n +|-數(shù)字 pid例：$renice - n +10 1001$renice - n - 10 131315. k訂1命令：向進(jìn)程發(fā)信號(hào)并殺死進(jìn)程。格式：kill -信號(hào)pid (s)信號(hào)是要發(fā)給進(jìn)程的信號(hào)(可選)，缺省是15,通知進(jìn)程終止有時(shí)候發(fā)出kill信號(hào)z后進(jìn)程依然可能存在。此時(shí)可以使用kill -9命令。 一般這樣就能夠保證殺死進(jìn)程。當(dāng)殺死一個(gè)進(jìn)程的時(shí)候，也殺死了進(jìn)程的所有了進(jìn)程。1.5 linux的全屏幕程序應(yīng)用在linux h設(shè)計(jì)全屏幕應(yīng)用程序要使用curses函數(shù)庫(kù)。假設(shè)我們的全屏幕 應(yīng)用程序名為

12、tc. c,以下介紹設(shè)計(jì)步驟。1. 開(kāi)機(jī)，登錄，進(jìn)入linux圖形用戶界面。2. 單擊任務(wù)欄上的主菜單，選擇“程序->應(yīng)用程序->gedit文木編輯器” ,進(jìn)入gedit的文木編輯界面。選擇“文件->新建”命令，將創(chuàng)建一個(gè)新文檔， 在文檔窗口屮輸入以下代碼：include <unistd.h>include <stdlib. h>#inelude curses.h>int main(int argc, char* argv ) char select;/存放用戶的菜單選項(xiàng)bool end二false; /循環(huán)控制變量，若為true則跳出循環(huán)，結(jié)束

13、程序的執(zhí)行initscr( ) ;/初始化curses函數(shù)庫(kù)/若用戶沒(méi)冇選擇功能3則循環(huán)執(zhí)行以下代碼/清屏/刷新物理屏幕i ）；顯示菜單i ）；i ）；i ）;i ）；main menu/接收用戶的菜單選項(xiàng)while(!end)clear();refresh();printw(|printw(，z | l:fcfs printw(，z | 2:round robinprintw(z，| 3:exit printv( |printwcenter your choice(13):)； refresh();doselect= (char)getch();refresh();while(select!

14、二t'&&select!二'2'&&select!二'3'); /若輸入不是 1、2、3 則重新輸 入clear();refresh();switch(select) case ' r :printw(，znfcfs. n)；break;case ' 2 ：printw(，znround rob in. n)； break;case ' 3 ：printw(，n");end二true;/根據(jù)用八選項(xiàng)顯示和應(yīng)信息printwpress getch(); refresh();endwin();

15、 return 0;any key to continue. n)；/按任意鍵繼續(xù)執(zhí)行/恢復(fù)curses庫(kù)原來(lái)的設(shè)置選擇“文件-另存為”命令，將文檔保存在當(dāng)而目錄下，并命 在作者 的機(jī)器上，實(shí) 際上是保存到輸入完成后， 名為tc. c o/home/testbook/test_curses/tc. c 中。3. 單擊任務(wù)欄上的終端仿真程序圖標(biāo)，進(jìn)入外殼程序bash,用cd命令進(jìn)入tc. c 所在的目錄。cd /home/testbook/test_curses4. 編譯tc. c生成可執(zhí)行文件tc. o,即在命令提示符卜鍵入卜面的編譯命令：gcc tc. c - o tc. o - lcurs

16、cs5.運(yùn)行tc.o,即在命令提示符卜鍵入卜面的命令：./tc.o可以看到程序首先顯示主菜單如 圖1-e在主菜單下輸入數(shù)字1,屏幕 輸出如圖l-2o按任意鍵回到主菜單， 在主菜單卜輸入數(shù)字2,屏幕輸出如圖 1-3。按任意鍵冋到主菜單，在主菜單 卜輸入數(shù)字3,屏幕輸出如圖1-4。按任意鍵結(jié)束程序的執(zhí)行，回到basho|mainmenu1|1:fcfs2:round robinfcfs.press any key to continue.圖1-2press any key to continue圖1 -4round robin.press any key to continue.圖1-31.6使用

17、編輯器vi編輯文件字符界面的linux系統(tǒng)，在命令提示符下鍵入以下命令將進(jìn)入vi編輯器以 便編輯源程序。1. 進(jìn)入linux的文本模式之后，在命令行鍵入vi f訂ename. c然后冋車(chē)。vi 命令是打開(kāi)vi編輯器。后面的filename, c是用戶即將編輯的c文件名字。2. 最基本的命令i :當(dāng)進(jìn)入剛打開(kāi)的文件時(shí)，不能寫(xiě)入信息，這時(shí)按一下鍵 盤(pán)上的i鍵（insert）,插入的意思，就可以進(jìn)入編輯模式了。如圖1-5 所示：rra in( )pr int ln( *he i lo vor id!ma 2.26-33 全刑圖1-5編輯模式3. 當(dāng)文件編輯完后，需要保存退出，這時(shí)需要經(jīng)過(guò)以下幾個(gè)步驟

18、：1）按一下 鍵盤(pán)上的esc鍵；2）鍵入冒號(hào)（：）,緊跟在冒號(hào)后而是wq （意思是保存 并退岀）。如果不想保存退岀，則在第二步鍵入冒號(hào)z后，鍵入q!（不帶w ,機(jī)尾部保存）。如圖1-6所示:mi in（ ）pr int ln（ i lo u）r id!*）;圖1-6保存模式4. 退出vi編輯器的編輯模式z后，要對(duì)剛才編寫(xiě)的程序進(jìn)行編譯。編譯的命 令是：gcc f 訂ename, c -o outputf 訂ermine, out,其中 gcc 是 c 的編譯 器。參數(shù)：filename, c是要編譯的源文件的名稱，outputf訂cnamc表示 輸出文件名稱，中括號(hào)表示括號(hào)內(nèi)部的內(nèi)容可輸入也可

19、以不輸入（中括號(hào) 本身不再命令行中出現(xiàn)）。如果不輸入outputfilename, out,默認(rèn)的輸出 文件是a. out o5. 最后一步是運(yùn)行程序，方法如b ： . /outputf ilcnamc. out實(shí)驗(yàn)2進(jìn)程調(diào)度算法設(shè)計(jì)2.1實(shí)驗(yàn)?zāi)康倪M(jìn)程管理是操作系統(tǒng)中的重要功能，用來(lái)創(chuàng)建進(jìn)程、撤消進(jìn)程、實(shí)現(xiàn)進(jìn)程狀 態(tài)轉(zhuǎn)換，它提供了在可運(yùn)行的進(jìn)程之間復(fù)用cpu的方法。在進(jìn)程管理屮，進(jìn)程 調(diào)度是核心，因?yàn)樵诓捎枚嗟莱绦蛟O(shè)計(jì)的系統(tǒng)中，往往有若干個(gè)進(jìn)程同時(shí)處于就 緒狀態(tài)，當(dāng)就緒進(jìn)程個(gè)數(shù)大于處理器數(shù)目時(shí)，就必須依照某種策略決定哪些進(jìn)程 優(yōu)先占用處理器。本實(shí)驗(yàn)?zāi)M在單處理器情況下的進(jìn)程調(diào)度，目的是加深對(duì)進(jìn)

20、程 調(diào)度工作的理解，掌握不同調(diào)度算法的優(yōu)缺點(diǎn)。2.2實(shí)驗(yàn)內(nèi)容選擇兩個(gè)調(diào)度算法作為兩個(gè)實(shí)驗(yàn)題耳，實(shí)現(xiàn)處理器調(diào)度。2.3實(shí)驗(yàn)要求要求完成以下功能：運(yùn)行處理器調(diào)度算法，顯示就緒進(jìn)程隊(duì)列、顯示運(yùn)行進(jìn) 程隊(duì)列、顯示阻塞進(jìn)程隊(duì)列、創(chuàng)建新進(jìn)程、阻塞進(jìn)程、喚醒進(jìn)程、刪除進(jìn)程、退 出程序。實(shí)驗(yàn)報(bào)告中給出程序中使用的數(shù)據(jù)結(jié)構(gòu)及流程圖。2.4實(shí)驗(yàn)預(yù)習(xí)內(nèi)容(1) 進(jìn)程控制塊為了管理和控制進(jìn)程，系統(tǒng)在創(chuàng)建每一個(gè)進(jìn)程時(shí)，都為其開(kāi)辟一個(gè)專(zhuān)用的存 儲(chǔ)區(qū)，用以隨時(shí)記錄它在系統(tǒng)中的動(dòng)態(tài)特性。而當(dāng)一個(gè)進(jìn)程被撤消時(shí)，系統(tǒng)就收 回分配給它的存儲(chǔ)區(qū)。通常，把這一存儲(chǔ)區(qū)稱為該進(jìn)程的“進(jìn)程控制塊” (process control bloc

21、k )o由于pcb是隨著進(jìn)程的創(chuàng)建而建立，隨著進(jìn)程的撤消而取消的，因此系統(tǒng) 是通過(guò)pcb來(lái)“感知,，一個(gè)個(gè)進(jìn)程的，pcb是進(jìn)程存在的唯一標(biāo)志。(2) 進(jìn)程控制塊隊(duì)列在多道程序設(shè)計(jì)環(huán)境里，同時(shí)會(huì)創(chuàng)建多個(gè)進(jìn)程。當(dāng)計(jì)算機(jī)系統(tǒng)只冇一個(gè)cpu 吋，每次只能讓一個(gè)進(jìn)程運(yùn)行，其他的進(jìn)程或處于就緒狀態(tài)，或處于阻塞狀態(tài)。 為了對(duì)這些進(jìn)程進(jìn)行管理，操作系統(tǒng)要做三件事。 把處于相同狀態(tài)的進(jìn)程的pcb,通過(guò)各門(mén)的隊(duì)列指針鏈接在一起，形 成一個(gè)個(gè)隊(duì)列。通常有運(yùn)行隊(duì)列、就緒隊(duì)列、阻塞隊(duì)列。 為每一個(gè)隊(duì)列設(shè)立一個(gè)隊(duì)列頭指針，它總是指向排在隊(duì)列之首的進(jìn)程的 pcbo 排在隊(duì)尾的進(jìn)程的pcb,它的“隊(duì)列指針”項(xiàng)內(nèi)容應(yīng)該為“nu

22、lls或一 個(gè)特殊的符號(hào)，以表示這是該隊(duì)的隊(duì)尾pcb。在單cpu系統(tǒng)中，任何時(shí)刻都只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)，因此運(yùn)行隊(duì)列 中只能有一個(gè)pcb；系統(tǒng)中所有處于就緒狀態(tài)的進(jìn)程的pcb排成一隊(duì)，稱其為“ 就緒隊(duì)列一般地，就緒隊(duì)列中會(huì)有多個(gè)進(jìn)程的pcb排在里面，它們形成處理 機(jī)分配的候選對(duì)象。如果就緒隊(duì)列里沒(méi)有pcb存在，則稱該隊(duì)列為空；所有處 于阻塞狀態(tài)進(jìn)程的pcb,應(yīng)該根據(jù)阻塞的原因進(jìn)行排隊(duì)，每一個(gè)都稱為一個(gè)“阻 塞隊(duì)列覽比如等待磁盤(pán)輸入/輸出進(jìn)程的pcb排成一個(gè)隊(duì)列，等待打印機(jī)輸出 進(jìn)程的pcb排成一個(gè)隊(duì)列等。所以，系統(tǒng)中可以有多個(gè)阻塞隊(duì)列，每個(gè)阻塞隊(duì) 列中可以有多個(gè)進(jìn)程的pcb,也可以為空。（

23、3）進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法用于確定就緒隊(duì)列中的哪一個(gè)進(jìn)程即將獲得cpuo常用的進(jìn) 程調(diào)度算法有先來(lái)先服務(wù)法、時(shí)間片輪轉(zhuǎn)法、優(yōu)先數(shù)法等。 先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法的基木思想是：以到達(dá)就緒隊(duì)列的先后次序?yàn)闃?biāo)準(zhǔn)來(lái)選 擇占用處理機(jī)的進(jìn)程。一個(gè)進(jìn)程一旦占有處理機(jī)，就一直使用卜去，直至正常結(jié) 束或因等待某事件的發(fā)生而讓出處理機(jī)。采用這種算法時(shí)，應(yīng)該這樣來(lái)管理就緒 隊(duì)列：到達(dá)的進(jìn)程的pcb總是排在就緒隊(duì)列末尾；調(diào)度程序總是把cpu分配給 就緒隊(duì)列中的第一個(gè)進(jìn)程使用。 時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)調(diào)度算法的基木思想是：為就緒隊(duì)列中的每一個(gè)進(jìn)程分配一個(gè)稱 為“時(shí)間片''的時(shí)間段，它是允許

24、該進(jìn)程運(yùn)行的時(shí)間長(zhǎng)度。在使用完一個(gè)時(shí)間片后 ,即使進(jìn)程還沒(méi)有運(yùn)行完畢，也要強(qiáng)迫其釋放處理機(jī)，讓給另一個(gè)進(jìn)程使用。它 口己則返回到就緒隊(duì)列末尾，排隊(duì)等待卞一次調(diào)度的到來(lái)。采用這種調(diào)度算法時(shí) ,對(duì)就緒隊(duì)列的管理與先來(lái)先服務(wù)完全相同。主要區(qū)別是進(jìn)程每次占用處理機(jī)的 時(shí)間由時(shí)間片決定，而不是只要占用處理機(jī)就一直運(yùn)行下去，直到運(yùn)行完畢或?yàn)?等待某一事件的發(fā)生而口動(dòng)放棄。 優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法的基本思想是：為每一個(gè)進(jìn)程確定一個(gè)優(yōu)先數(shù)，進(jìn)程就緒隊(duì) 列按照優(yōu)先數(shù)排序。如何確定進(jìn)程的優(yōu)先數(shù)（也就是進(jìn)程的優(yōu)先級(jí)）？可以從如卜幾個(gè)方面考慮。i）根據(jù)進(jìn)程的類(lèi)型。系統(tǒng)中既有系統(tǒng)進(jìn)程，又有用戶進(jìn)程。系統(tǒng)進(jìn)程 完成

25、的任務(wù)是提供系統(tǒng)服務(wù)，分配系統(tǒng)資源，因此，給予系統(tǒng)進(jìn)程較高的優(yōu)先數(shù) 能夠提高系統(tǒng)的工作效率。ii）根據(jù)進(jìn)程執(zhí)行任務(wù)的重要性。重要性和緊迫性高的進(jìn)程應(yīng)當(dāng)被賦予 較高的優(yōu)先級(jí)。iii）根據(jù)進(jìn)程程序的性質(zhì)。一個(gè)cpu繁忙的進(jìn)程，由于需要占用較長(zhǎng)的 運(yùn)行時(shí)間，影響系統(tǒng)整體效率的發(fā)揮，因此只能給予較低的優(yōu)先數(shù)。一個(gè)i/o繁 忙的進(jìn)程，給予它較高的優(yōu)先數(shù)后，就能充分發(fā)揮cpu和外部設(shè)備z間的并行 工作能力。iv）根據(jù)對(duì)資源的要求。系統(tǒng)資源有處理機(jī)、內(nèi)存儲(chǔ)器和外部設(shè)備等。 可以按照一個(gè)進(jìn)程所需資源的類(lèi)型和數(shù)量，確定它的優(yōu)先數(shù)。比如給予占用cpu 時(shí)間短或內(nèi)存容量少的進(jìn)程以較高的優(yōu)先數(shù)，這樣可以提高系統(tǒng)的吞吐

26、量。v）根據(jù)用戶的請(qǐng)求。系統(tǒng)可以根據(jù)用戶的請(qǐng)求，給予它的進(jìn)程很高的 優(yōu)先數(shù)，作“加急"處理。 多級(jí)隊(duì)列調(diào)度算法多級(jí)隊(duì)列調(diào)度算法也稱多級(jí)反饋隊(duì)列調(diào)度算法，它是時(shí)間片調(diào)度算法與 優(yōu)先數(shù)調(diào)度算法的結(jié)合。實(shí)行這種調(diào)度算法時(shí)，系統(tǒng)中將維持多個(gè)就緒隊(duì)列，每 個(gè)就緒隊(duì)列具有不同的調(diào)度級(jí)別，可以獲得不同長(zhǎng)度的時(shí)間片。例如，系統(tǒng)維持 n個(gè)就緒隊(duì)列，第1級(jí)就緒隊(duì)列中進(jìn)程的調(diào)度級(jí)別最高，可獲得的時(shí)間片最短， 第n級(jí)就緒隊(duì)列中進(jìn)程的調(diào)度級(jí)別最低，可獲得的時(shí)間片最長(zhǎng)。具體的調(diào)度方法是：創(chuàng)建一個(gè)新進(jìn)程時(shí)，它的pcb將進(jìn)入第1級(jí)就緒隊(duì)列 的末尾。對(duì)于在第1級(jí)到第n1級(jí)隊(duì)列中的進(jìn)程，如杲在分配給它的時(shí)間片內(nèi)完 成了

27、全部工作，那么就撤離系統(tǒng)；如果在時(shí)間片沒(méi)有用完時(shí)提出了輸入/輸出請(qǐng) 求或要等待某事件發(fā)生，那么就進(jìn)入相應(yīng)的阻塞隊(duì)列里等待。在所等待的事件出 現(xiàn)時(shí)，仍回到原隊(duì)列末尾，參與卜一輪調(diào)度（也就是每個(gè)隊(duì)列實(shí)行先來(lái)先服務(wù)調(diào) 度算法）；如果用完了時(shí)間片還沒(méi)有完成口己的工作，那么只能放棄對(duì)cpu的使 用，降到低一級(jí)隊(duì)列的末尾，參與那個(gè)隊(duì)列的調(diào)度。對(duì)位于最后一個(gè)隊(duì)列里的進(jìn) 程，實(shí)行時(shí)間片輪轉(zhuǎn)調(diào)度算法。整個(gè)系統(tǒng)最先調(diào)度1級(jí)就緒隊(duì)列；只有在上一級(jí)就緒隊(duì)列為空時(shí)，才去下一 級(jí)隊(duì)列調(diào)度。當(dāng)比運(yùn)行進(jìn)程更高級(jí)別的隊(duì)列中到達(dá)一個(gè)進(jìn)程（可以肯定，在此之 前比運(yùn)行進(jìn)程級(jí)別高的所有隊(duì)列全為空）時(shí)，系統(tǒng)將立即停止當(dāng)而運(yùn)行進(jìn)程的運(yùn) 行

28、，讓它回到口己隊(duì)列的末尾，轉(zhuǎn)去運(yùn)行級(jí)別高的那個(gè)進(jìn)程?？梢钥闯觯嗉?jí)隊(duì)列調(diào)度算法優(yōu)先照顧i/o繁忙的進(jìn)程。i/o繁忙的進(jìn)程在 獲得一點(diǎn)cpu時(shí)間后就會(huì)提出輸入/輸出請(qǐng)求，因此它們總是被保持在1、2級(jí) 等較前面的隊(duì)列中，總能獲得較多的調(diào)度機(jī)會(huì)。對(duì)于cpu繁忙的進(jìn)程，它們需 要較長(zhǎng)的cpu時(shí)間，因此會(huì)逐漸地由級(jí)別高的隊(duì)列往下降，以獲得更多的cpu 時(shí)間，它們“沉”得越深，被調(diào)度到的機(jī)會(huì)就越少。但是，一旦被調(diào)度到，就會(huì)獲 得更多的cpu時(shí)間。2. 5實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)中用到的主要數(shù)據(jù)結(jié)構(gòu)是進(jìn)程控制塊，其結(jié)構(gòu)如圖21所示。數(shù)據(jù)項(xiàng)作用next前向指針，指向下一個(gè)進(jìn)程控制塊，用來(lái)構(gòu)成進(jìn)程隊(duì)列processname

29、進(jìn)程名稱proccss_numbcr進(jìn)程號(hào)，當(dāng)進(jìn)程有相同名稱時(shí)，用來(lái)區(qū)分進(jìn)程process_start_moment進(jìn)程啟動(dòng)時(shí)刻process_need_time進(jìn)程要求運(yùn)行時(shí)間process_lime_slice時(shí)間片proccsspriority優(yōu)先數(shù)圖2-1進(jìn)程控制塊參考源代碼: 進(jìn)程調(diào)度算法 編譯命令gcc process_schedule.cpp -o process_schedule.o -leurses程序清單 頭文件 process_schedule>hsincludecurses. h> include <stdlib.h>sinclude <u

30、nistd.h>sincludestring. h> #define max_process 10int process_number=0;typedef struct pcb struct pcb *next; char process_name20; int process_number; int process_start_moment; int process_need_time; int process_time_slice; int processpriority;pcb;pcb pcb_tablemax_process;pcb *pcb_run二null;pcb *p

31、cb_free二mull;pcb *pcb_ready二hull;pcb *pcb_ready_rear=null;pcb *pcb_blockcd二mull;pcb *pcb_blocked_rear=null;void init_pcb_table();void display_process_queue(pcb *queue); pcb *create_process();void block_process_by_name();void wakeup_process();void fcfs ();void rr();void hpf();void mfbq();源文件 process_

32、schedule. cpp#include z/process_schedule h int main(int argc, char *argv) char select;initscr(); init_pcb_table(); bool end二false;while(!end) clear ();printw(main menu1 n0printw(z/1:first come first served1 n0printw(z/2:round robin1 n0printw(z/3:highest priority first1 n0printw(z/4:multi_level feedb

33、ack queue1 n0printw(z/5:display ready process queue1 n0printw(z/6:display blocked process queue1 n0printw(z/7:display running queue1 n0printw(z/a:create a process1 n0printw(z/b:delete a process1 n0printw(z/c:block a process1 n0printw(z/d:wakeup a process1 n0printw(z/8:exit1 n0printw(-iv)refresh ();p

34、rintw(z/select a function(1、&d):)； refresh ();do先到先服務(wù)/時(shí)間片輪轉(zhuǎn)調(diào)度/優(yōu)先級(jí)調(diào)度優(yōu)先數(shù)調(diào)度顯示就緒進(jìn)程隊(duì)列顯示等待進(jìn)程隊(duì)列/顯示運(yùn)行隊(duì)列/創(chuàng)建一個(gè)隊(duì)列/刪除一個(gè)隊(duì)列使一個(gè)隊(duì)列進(jìn)入等待狀態(tài)/喚醒一個(gè)隊(duì)列select= (char)getch();refresh ();while(!(49<=select&&select<=56) |(97<=select&&select<=100); clear ();refresh (); switch (select) case '

35、r :fcfs (); break;case ' 2": rr(); break;case ' 3":hpfo； break; case ' 4，:mfbqo ; break;case ' 5":printw(z/ready queue'rt);display_process_queue(pcb_ready);break;case ' 6 :printw(/?blocked queue'rt);display_process_queue(pcb_blocked); break;case ' t :pr

36、intw(z/running queuen)；displar_process_queue (pcb_run); break;case ' a :create_process();break;case ' b":break;case ' c，:block_process_by_name();break;case ' d':wakeup_process();break;case ' 8":printw(zzn，/);end二true; ” ” printw(/zpress any key to continue. rt); get

37、ch();refresh ();endwin ();return 0;void init_pcb_table()int i二0;pcb_free=&pcb_table0;pcb_tablemax_process-1. next=null;pcb_tablemax_process-1. process_number=0; pcb_tablemax_process-1. process_start_moment=0; pcb_tablemax_process-1. process_need_time=0; pcb_tablemax_process1. process_time_slice=

38、0; pcb_tablemax_process-1. process_priority=0; strcpy(pcb_tablemax_process1. process_name,; for(i=0;i<max_pr0cess-l;i+)pcb_tablei next=&pcb_tablei+l; pcb_tablei. process_number=0; pcb_tablei process_start_moment=0; pcb_tablei process_neecl_time=0; pcb_tablei process_time_slice=0; pcb_tablei p

39、rocess_priority=0; strcpy (pcb_tablei process_name,z/，/);void display_process_queue(pcb *queue)pcb *p=queue;int i=4;slice | priority |n);i1lrmove(l, 1);printw(/z |111);move (2, 1);printw(z/ namenumber start | needmove (3, 1);printw(z，|111);while(p!=null)move(i, 1); printwci /z); printw(z，%sz/, p->

40、;process_name);moved, 12);printwci /z);printw(z，%d/z, p->process_number); move(i, 23);printw(/z ”)； printw(z/%dz，, p->process_start jnoment); moved, 34);printwci /z);printw(z/%dz，, p->process_need_time); moved, 45);printw(/z ”)；printw(z，%d/z, p->process_time_s 1 ice); move(i, 56);printwc

41、i /z);printw(z/%dz，, p->process_priority); moved, 67);printwci');p二p-next;i+；moved, 1);printw(z，|111);refresh (); void fcfs ()辻(pcb_ready二二null) ” ” printw(z，ready queue is empty, no process to run rt);elsepcb_run=pcb_ready;if(pcb_ready=pcb_ready_rear)pcb_ready=pcb_ready_rear=null;pcb_ready=p

42、cb_ready->next;pcb_run->next=null; void rr()void iipfovoid mfbq() ipcb *create_process()pcb *p=pcb_free;if(p=nulqreturn null;elsepcb_free=pcb_free->next;clear ();refresh ();priority |rt);printw(z/please enter the following fields:nz/); printw(z/ name | start_moment | needtime | time-slice s

43、canw ("%s%d%d%d%d", p->process_name,& (p->ptocess_start_moinent),&(p->process_need_t ime),& (p->process_t ime_slice), &(p->process_priority);p->process_number=(process_number+l)%100; process_number+;p->next二null;if(pcb_ready=null) pcb_ready=pcb_ready_re

44、ar=p;elsepcb_ready_rear->next=p; pcb_ready_rear=p; return p; void block_process_by_name()char process_name20; pcb *p=pcb_ready;pcb *previous_p=pcb_ready;辻(p=null) ” ” printw(z/ready queue is empty, no process can be blocked! n，z);return;display_process_queue(pcb_ready);printw(z/enter the process

45、name you want to block: nz，); );while(p!=null)if(!strcmp(p->process_name, process_name)break;previous_p=p;p=p->next;辻(p=null) ” ” printw(no such a process in ready queue:%snyou typed the wrong namen", process_name);return;elseif (p=pcb_ready_rear)無(wú)標(biāo)題文檔pcb_ready_rear=previous_p

46、;previous_p->next=p->next;if (pcb_blocked=null) pcb_blocked=pcb_blocked_rear=p; p-next二null;elsepcb_blocked_rear->next=p;pcb_blocked_rear=pcb_blocked_rear->next; p-next二null;void wakeup_process()pcb *p=pcb_blocked;if(pcb_blocked=null) ” ” printw(z/blocked queue is empty, no process needs

47、 to be wakeuped n”)；else if(pcb_blocked=pcb_blocked_rear) pcb_blocked=pcb_blocked_rear=null;elsepcb_blocked=pcb_blocked->next;if (pcb_ready=null) pcb_ready=pcb_ready_rear=p; p->next=null;elsepcb_ready_rear->next=p; pcb_ready_rear=pcb_ready_rear->next; p->next二null;/wakeup實(shí)驗(yàn)3進(jìn)程間通信算法設(shè)計(jì)3

48、.1實(shí)驗(yàn)?zāi)康?. 通過(guò)基礎(chǔ)實(shí)驗(yàn)，基本掌握共享內(nèi)存的程序設(shè)計(jì)。2. 通過(guò)編寫(xiě)程序，使讀者掌握消息隊(duì)列的設(shè)計(jì)方法。3. 通過(guò)編寫(xiě)程序，掌握通道通信的設(shè)計(jì)方法3.2實(shí)驗(yàn)內(nèi)容1. 共享內(nèi)存程序設(shè)計(jì)：創(chuàng)建兩個(gè)進(jìn)程，在a進(jìn)程中創(chuàng)建一個(gè)共享內(nèi)存，并 向其寫(xiě)入數(shù)據(jù)，通過(guò)b進(jìn)程從共享內(nèi)存中讀出數(shù)據(jù)。2. 消息隊(duì)列程序設(shè)計(jì)：創(chuàng)建一個(gè)消息隊(duì)列，如何使用消息隊(duì)列進(jìn)行兩個(gè)進(jìn) 程(發(fā)送端和接受端)之間的通信，包括消息隊(duì)列的創(chuàng)建、消息發(fā)送與讀取、消 息隊(duì)列的撤銷(xiāo)和刪除等多種操作。3. 管道通信程序設(shè)計(jì)：編寫(xiě)程序?qū)崿F(xiàn)進(jìn)程的管道通信，掌握冇名管道的創(chuàng)建和讀 寫(xiě)方式，并熟悉linux支持的有名管道通信方式3.3實(shí)驗(yàn)要求理解進(jìn)程通

49、信的不同方法，要求仿真實(shí)現(xiàn)共享內(nèi)存方式或消息傳遞方式或管 道方式。運(yùn)行程序并分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)報(bào)告中給出程序中使用的數(shù)據(jù)結(jié)構(gòu)及流程圖。3.4實(shí)驗(yàn)預(yù)習(xí)內(nèi)容參閱相關(guān)資料，熟悉共享內(nèi)存、消息隊(duì)列、管道通信策略及實(shí)現(xiàn)技術(shù)。3.5實(shí)驗(yàn)指導(dǎo)3.5.1共享內(nèi)存程序設(shè)計(jì)1. 函數(shù)說(shuō)明：共享內(nèi)存的實(shí)現(xiàn)分為兩個(gè)步驟，第一步是創(chuàng)建共享內(nèi)存，這里用 到的函數(shù)是shmget(),也就是從內(nèi)存中獲得一段共享內(nèi)存區(qū)域。第二步映射共享 內(nèi)存，也就是把這段創(chuàng)建的共享內(nèi)存映射到具體的進(jìn)程空間中，這里使用的函數(shù) 是shmatoo到這里，就可以使用這段共享內(nèi)存了，也就是可以使用不帶緩沖的 i/o讀寫(xiě)命令對(duì)其進(jìn)行操作。除此之外，當(dāng)然還

50、有撤銷(xiāo)映射的操作，其函數(shù)為 shmdt()o2. 共享內(nèi)存的用法：使用共享內(nèi)存進(jìn)行進(jìn)程間通信一般要經(jīng)歷卜面幾個(gè)步驟：1 分配：進(jìn)程通過(guò)調(diào)用shmget來(lái)分配一個(gè)共享內(nèi)存塊。2 映射：要讓一個(gè)進(jìn)程獲取對(duì)一塊共享內(nèi)存的訪問(wèn)，這個(gè)進(jìn)程必須先調(diào)用 shmat映射共享內(nèi)存。3 脫離與釋放：當(dāng)進(jìn)程結(jié)束使用共享內(nèi)存時(shí)，使用shhkit使共享內(nèi)存脫離 進(jìn)程。當(dāng)不再需要共享內(nèi)存時(shí),使用shmctl (sid, ipc_rmid, 0)刪除它。3實(shí)驗(yàn)步驟及代碼： 1)自己建立文件夾，然后分別編輯shm_com.h> shml.cs shm2.c. 1root©localhostbyy#vishm_

51、com.hrootlocalhostbyy#vishml.crootlocalhostbyy#cpshml.cshm2.croot©localhostbyy#vishm2.c/*shm com.h*/#dehne text_sz 2048struct shared_use_stint written_by_you;char some_uxttext_szl;功能描述：本程序申請(qǐng)和分配共享內(nèi)存，然后輪詢并讀取共享內(nèi)存中的數(shù)據(jù)，直至讀到“end”/*shml.c*/#include<unistd>h>#include<stdio>h>#include&

52、lt;stdlib.h>#include<string.h>#include<sys/types>h>#include<sys/ipc.h>#include<sys/shnieh>#include f,shm_com.hnint main(void)int running=l;void *shared_memory=(void *)0;struct shared use st shared stuff;int shmid;/*創(chuàng)建共享內(nèi)存*/shmid=shmget(key_t) 1234sizeof(struct shared_us

53、e_st),0666|ipc_creat);if(shmid=-l)fprintf(stderr/fshmget failednft); exit(exit_failure);/*映射共享內(nèi)存勺shared_memory=shmat(shmidxvoid *)0,0); if(shared_memory=(void *)-1)fprintf(stderr/fshmat failednft); exit(exit_failure);printf(f,memory attached at %xn,(int)shared_memory);/*讓結(jié)構(gòu)體指針指向這塊共享內(nèi)存引 shared_stuff=

54、(struct shared_use_st *)shared_memory; 八控制讀寫(xiě)順序引shared_stuff->written_by_you=0;/*循環(huán)地從共享內(nèi)存中讀數(shù)據(jù)，直到讀到“end”為止勺 while(running)if(shared_stuff->written_by_you)printf(myou wrote: %s115shared_stuff->some_text);/*讀進(jìn)程睡眠1秒，同時(shí)會(huì)導(dǎo)致寫(xiě)進(jìn)程睡眠1秒，做到先讀后寫(xiě) 勺 sleep(l);shared_stuff->written_by_you=0;if(strncmp(shared_stuff->some_text/fend,3)=0)running=o;/結(jié)束循環(huán)/*刪除共享內(nèi)存*/if(shmdt(shared_memory)=-l)fprintf(stderr/fshmdt failednm); exit(exit_failure); exit(exit_success);功能描述：本程序申請(qǐng)了上一段程序相同的共享內(nèi)存，然后循環(huán)地向共享內(nèi)存中寫(xiě)數(shù)據(jù), 直