西安交通大學(xué)操作系統(tǒng)課內(nèi)實(shí)驗(yàn)報(bào)告

1、西安交通大學(xué) 實(shí)驗(yàn)報(bào)告 操作系統(tǒng)原理課內(nèi)實(shí)驗(yàn)姓名：班級(jí)： 學(xué)號(hào)：實(shí)驗(yàn)一 用戶接口實(shí)驗(yàn)一、 實(shí)驗(yàn)?zāi)康?1、理解并掌握面向操作命令的接口Shell，學(xué)會(huì)簡(jiǎn)單的shell編碼。 2、理解操作系統(tǒng)調(diào)用的運(yùn)行機(jī)制，掌握創(chuàng)建系統(tǒng)調(diào)用的方法。 二、 實(shí)驗(yàn)內(nèi)容 1、 控制臺(tái)命令接口實(shí)驗(yàn)理解面向操作命令的接口shell和進(jìn)行簡(jiǎn)單的shell編程。 該實(shí)驗(yàn)是通過“幾種操作系統(tǒng)的控制臺(tái)命令”、“終端處理程序”、“命令解釋程序”和“Linux 操作系統(tǒng)的 bash”來讓實(shí)驗(yàn)者理解面向操作命令的接口 shell 和進(jìn)行簡(jiǎn)單的 shell 編程。l 查看 bash 版本。 l 編寫 bash 腳本，統(tǒng)計(jì)/my 目錄下 c

2、 語言文件的個(gè)數(shù) 2) 系統(tǒng)調(diào)用實(shí)驗(yàn) 。2、系統(tǒng)調(diào)用實(shí)驗(yàn) 理解操作系統(tǒng)調(diào)用的運(yùn)行機(jī)制。 該實(shí)驗(yàn)是通過實(shí)驗(yàn)者對(duì)“Linux 操作系統(tǒng)的系統(tǒng)調(diào)用機(jī)制”的進(jìn)一步了解來理解操作 系統(tǒng)調(diào)用的運(yùn)行機(jī)制；同時(shí)通過“自己創(chuàng)建一個(gè)系統(tǒng)調(diào)用 mycall（）”和“編程調(diào)用自己 創(chuàng)建的系統(tǒng)調(diào)用”進(jìn)一步掌握創(chuàng)建和調(diào)用系統(tǒng)調(diào)用的方法。 l 編程調(diào)用一個(gè)系統(tǒng)調(diào)用 fork（），觀察結(jié)果。 l 編程調(diào)用創(chuàng)建的系統(tǒng)調(diào)用 foo（），觀察結(jié)果。 l 自己創(chuàng)建一個(gè)系統(tǒng)調(diào)用 mycall（），實(shí)現(xiàn)功能：顯示字符串到屏幕上。 l 編程調(diào)用自己創(chuàng)建的系統(tǒng)調(diào)用。 三、實(shí)驗(yàn)準(zhǔn)備 為了使用戶通過操作系統(tǒng)完成各項(xiàng)管理任務(wù)，操作系統(tǒng)必須為用戶提

3、供各種接口來實(shí)現(xiàn) 人機(jī)交互。經(jīng)典的操作系統(tǒng)理論將操作系統(tǒng)的接口分為控制臺(tái)命令和系統(tǒng)調(diào)用兩種。前者主 要提供給計(jì)算機(jī)的操作人員對(duì)計(jì)算機(jī)進(jìn)行各種控制；而后者則提供個(gè)程序員，使他們可以方 便地使用計(jì)算機(jī)的各種資源。四、 實(shí)驗(yàn)步驟及結(jié)果1、 控制臺(tái)命令接口實(shí)驗(yàn)（1）查看 bash 版本操作：在 shell 提示符下輸入：$echo $BASH_VERSION結(jié)果：版本是4.2.42（1）-release（2）建立 bash 腳本，輸出 Hello word操作：在編輯器中輸入以下內(nèi)容#!/bin/bashecho Hello World!結(jié)果：操作：執(zhí)行腳本 使用指令：$./text結(jié)果：（3）編寫

4、bash 腳本：統(tǒng)計(jì)/my 目錄下 c 語言文件的個(gè)數(shù)通過 bash 腳本，可以有多種方式實(shí)現(xiàn)這個(gè)功能，而使用函數(shù)是其中個(gè)一個(gè)選擇。在使用函數(shù)之前，必須先定義函數(shù)。 進(jìn)入自己的工作目錄，編寫名為 count 的文件。腳本程序：#! /bin/bashfunctioncountechon" Number of matches for $1: "#接收程序的第一個(gè)參數(shù)ls$1|wc l#對(duì)子程序的第一個(gè)參數(shù)所在的目錄進(jìn)行操作將 count 文件復(fù)制到當(dāng)前目錄下，然后在當(dāng)前目錄下建立文件夾，在 my 目錄下建立幾個(gè) c 文件,以便用來進(jìn)行測(cè)試。2、 添加系統(tǒng)調(diào)用 （1）編程調(diào)用一

5、個(gè)系統(tǒng)調(diào)用fork（），觀察結(jié)果。源程序：# include <stdio.h> int main()int iUid;iUid=fork();if(iUid=0)for(;) printf("This is child process.n"); sleep(1); if(iUid>0)for(;) printf("This is parent process.n");sleep(1);if(iUid<0) printf("Can not use system call.n");return 0; 實(shí)驗(yàn)結(jié)果：（

6、2）操作：1. Linux-3.0.tar.bz2拷貝到/usr/src目錄下命令：cp linux-3.0.tar.bz2 /usr/src/ 2. 打開終端，獲得root權(quán)限命令：sudo s 3. 進(jìn)入/usr/src目錄命令：cd /usr/src 4. 解壓linux源碼命令：tar xvzf linux-3.0.tar.bz2 5. 進(jìn)入目錄linux-3.0.5命令：cd linux-3.0 6. 添加系統(tǒng)調(diào)用：gedit kernel/myservice.c 在文本編輯器中添加 #include <linux/kernel.h> #include <linux

7、/linkage.h> asmlinkage void sys_mycall() printk(KERN_INFO "Hello, world!n"); return; 7. 修改kernel/Makefile添加生成myservice.c添加到Makefile的編譯規(guī)則中： obj-y += myservice.o 8. .修改arch/x86/include/asm/unistd_32.h，添加以下內(nèi)容： #define _NR_mycall SYS_ID /SYS_ID表示新添加系統(tǒng)調(diào)用的調(diào)用號(hào) 并修改文件中的NR_syscalls，將其值增加1 9. .修改a

8、rxh/x86/include/asm/syscalls.h添加以下內(nèi)容： asmlinkage void sys_mycall(); 10. 修改arch/x86/kernel/syscall_table_32.S，添加以下內(nèi)容： .long sys_mycall 11. 配置內(nèi)核（僅僅修改local versions即可）命令：make menuconfig 12. 編譯內(nèi)核命令：make j4 bzImage（開4個(gè)線程編譯） 13. 編譯內(nèi)核模塊命令：make j4 modules14. 安裝內(nèi)核模塊命令：make modules_install15. 安裝內(nèi)核命令：make inst

9、all 16. 重啟系統(tǒng)，在系統(tǒng)選擇頁(yè)面選擇進(jìn)入自己編譯的linux-3.0內(nèi)核 17. 在桌面建立測(cè)試的C程序test.c程序內(nèi)容如下： #include <stdio.h> int main(int argc, char *argv) syscall(SYS_ID); / SYS_ID表示新添加系統(tǒng)調(diào)用的調(diào)用號(hào) return 0; 18. 編譯程序gcc test.c o a.out 19. 運(yùn)行程序./a.out 20. 查看內(nèi)核日志（printk的輸出信息在內(nèi)核日志中）：dmesg結(jié)果：（1）編譯內(nèi)核成功截圖:（2）編譯模塊成功截圖:五、實(shí)驗(yàn)問題及分析在進(jìn)行內(nèi)核編譯時(shí)，遇到

10、的困難就是將缺少的程序補(bǔ)入，但因?yàn)楸臼?Ubantu 所帶 的編輯器很不好用，在輸入過程中就花費(fèi)了非常大的時(shí)間。但最后經(jīng)過學(xué)長(zhǎng)的幫助順利完成。 在編譯期間有經(jīng)歷了一個(gè)多小時(shí)的時(shí)間，最后編譯成功。六、實(shí)驗(yàn)心得通過本次實(shí)驗(yàn)，我了解并初步掌握了面向操作命令的接口Shell，學(xué)會(huì)了簡(jiǎn)單的 shell 編碼，理解了操作系統(tǒng)調(diào)用的運(yùn)行機(jī)制，掌握了創(chuàng)建系統(tǒng)調(diào)用的方法。本次實(shí)驗(yàn)通過內(nèi)核編譯，將一組源代碼變成操作系統(tǒng)的內(nèi)核，并由此重新引導(dǎo)系統(tǒng)，這讓我們初步了解了操作系統(tǒng)的生成過程。雖然在實(shí)驗(yàn)過程中遇到了不少問題，但最終在學(xué)長(zhǎng)的幫助下，最終還是成功了。最后看見自己的實(shí)驗(yàn)結(jié)果心里還是挺高興的?？傊?，這次實(shí)驗(yàn)我們學(xué)習(xí)

11、了linux系統(tǒng)的使用方法，掌握了一些基本的linux命令，學(xué)習(xí)了添加系統(tǒng)調(diào)用的方法，更深入的了解了操作系統(tǒng)，為我們以后的工作學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。實(shí)驗(yàn)二：進(jìn)程管理實(shí)驗(yàn)一、 實(shí)驗(yàn)?zāi)康?、 理解進(jìn)程的概念，知道進(jìn)程與程序的區(qū)別；2、 理解并發(fā)執(zhí)行、進(jìn)程互斥及進(jìn)程通信的基本概念；3、 了解并掌握進(jìn)程管理的機(jī)制和操作步驟。二、 實(shí)驗(yàn)內(nèi)容1、 編制實(shí)現(xiàn)軟中斷通信的程序使用系統(tǒng)調(diào)用 fork()創(chuàng)建兩個(gè)子進(jìn)程，再用系統(tǒng)調(diào)用 signal()讓父進(jìn)程捕捉鍵盤上發(fā)出 的中斷信號(hào)（即按 delete 鍵），當(dāng)父進(jìn)程接收到這兩個(gè)軟中斷的某一個(gè)后，父進(jìn)程用系統(tǒng)調(diào) 用 kill()向兩個(gè)子進(jìn)程分別發(fā)出整數(shù)值為 16

12、和 17 軟中斷信號(hào)，子進(jìn)程獲得對(duì)應(yīng)軟中斷信號(hào)， 然后分別輸出下列信息后終止：Child process 1 is killed by parent !Child process 2 is killed by parent !父進(jìn)程調(diào)用 wait()函數(shù)等待兩個(gè)子進(jìn)程終止后，輸入以下信息，結(jié)束進(jìn)程執(zhí)行： Parent process is killed! 多運(yùn)行幾次編寫的程序，簡(jiǎn)略分析出現(xiàn)不同結(jié)果的原因。2、編制實(shí)現(xiàn)進(jìn)程的管道通信的程序使用系統(tǒng)調(diào)用 pipe()建立一條管道線，兩個(gè)子進(jìn)程分別向管道寫一句話：Child process 1 is sending a message!Child p

13、rocess 2 is sending a message!而父進(jìn)程則從管道中讀出來自于兩個(gè)子進(jìn)程的信息，顯示在屏幕上。要求：父進(jìn)程先接收子進(jìn)程 P1 發(fā)來的消息，然后再接收子進(jìn)程 P2 發(fā)來的消息。三、 實(shí)驗(yàn)步驟及結(jié)果分析1、 進(jìn)程的軟中斷通信（1） 算法流程圖： 軟中斷通信程序流程圖（2）程序源代碼：#include <stdio.h> #include <signal.h> #include <unistd.h> #include <sys/types.h>int wait_flag; void stop( ); main( ) int p

14、id1, pid2; / 定義兩個(gè)進(jìn)程號(hào)變量 signal(3,stop); / 或者 signal(14,stop); while(pid1 = fork( ) = -1);/ 若創(chuàng)建子進(jìn)程1不成功,則空循環(huán)if(pid1 > 0) / 子進(jìn)程創(chuàng)建成功,pid1為進(jìn)程號(hào) while(pid2 = fork( ) = -1);/ 創(chuàng)建子進(jìn)程2 if(pid2 > 0) wait_flag = 1; sleep(5); / 父進(jìn)程等待5秒 kill(pid1,16); / 殺死進(jìn)程1kill(pid2,17); / 殺死進(jìn)程2 wait(0); / 等待第1個(gè)子進(jìn)程1結(jié)束的信號(hào) wa

15、it(0); / 等待第2個(gè)子進(jìn)程2結(jié)束的信號(hào) printf("n Parent process is killed !n"); exit(0); / 父進(jìn)程結(jié)束 else wait_flag = 1; signal(17,stop); / 等待進(jìn)程2被殺死的中斷號(hào)17 printf("n Child process 2 is killed by parent !n"); exit(0); else wait_flag = 1; signal(16,stop); / 等待進(jìn)程1被殺死的中斷號(hào)16 printf("n Child process

16、1 is killed by parent !n"); exit(0); void stop( ) wait_flag = 0; （3）實(shí)驗(yàn)結(jié)果：（4）簡(jiǎn)要分析1) signal函數(shù) 上述程序中，調(diào)用函數(shù)signal()都放在一段程序的前面部位，而不是在其他接收信號(hào)處。這是因?yàn)閟ignal()的執(zhí)行起的作用只是為進(jìn)程指定信號(hào)量16和17，以及分配相應(yīng)的與stop()過程連接的指針。因而signal()函數(shù)必須在程序前面部分執(zhí)行。 2）wait函數(shù) 在父進(jìn)程中調(diào)用第1個(gè)wait(0)后，則父進(jìn)程被阻塞。進(jìn)入等待第一個(gè)子進(jìn)程運(yùn)行結(jié)束的隊(duì)列，等待子進(jìn)程結(jié)束。當(dāng)子進(jìn)程結(jié)束后，會(huì)產(chǎn)生一個(gè)終止?fàn)?/p>

17、態(tài)字，系統(tǒng)會(huì)向父進(jìn)程發(fā)出SIGCHLD信號(hào)。當(dāng)接到信號(hào)后，父進(jìn)程提取子進(jìn)程的終止?fàn)顟B(tài)字，從wait()返回繼續(xù)執(zhí)行原程序。同樣的方式，父進(jìn)程繼續(xù)執(zhí)行第二個(gè)wait(0)，并再次阻塞，等待第2個(gè)子進(jìn)程運(yùn)行結(jié)束。當(dāng)?shù)诙€(gè)子進(jìn)程運(yùn)行結(jié)束后父進(jìn)程繼續(xù)執(zhí)行剩余的語句。 3）關(guān)于exit函數(shù) 該函數(shù)中每個(gè)進(jìn)程退出時(shí)都用了語句exit(0)，這是進(jìn)程的正常終止。在正常終止時(shí)，exit()函數(shù)返回進(jìn)程結(jié)束狀態(tài)。進(jìn)程終止時(shí)，則由系統(tǒng)內(nèi)核產(chǎn)生一個(gè)代表異常終止原因的終止?fàn)顟B(tài)，該進(jìn)程的父進(jìn)程都能用wait()得到其終止?fàn)顟B(tài)。在子進(jìn)程調(diào)用exit()后，子進(jìn)程的結(jié)束狀態(tài)會(huì)返回給系統(tǒng)內(nèi)核，由內(nèi)核根據(jù)狀態(tài)字生成終止?fàn)顟B(tài)，供

18、父進(jìn)程在wait()中讀取數(shù)據(jù)。若子進(jìn)程結(jié)束后，父進(jìn)程還沒有讀取子進(jìn)程的終止?fàn)顟B(tài)，則子進(jìn)程就變成了“孤兒進(jìn)程”，系統(tǒng)進(jìn)程init會(huì)自動(dòng)“收養(yǎng)”該子進(jìn)程，成為該子進(jìn)程的父進(jìn)程，即父進(jìn)程標(biāo)識(shí)號(hào)變成1，當(dāng)子進(jìn)程結(jié)束時(shí)，init會(huì)自動(dòng)調(diào)用wait()讀取子進(jìn)程的遺留數(shù)據(jù)，從而避免在系統(tǒng)中留下大量的垃圾。 4）結(jié)果顯示上述結(jié)果中“Child process 1 is killed by parent !” 和“Child process 2 is killed by parent !”相繼出現(xiàn)，當(dāng)運(yùn)行幾次后，誰在前誰在后是隨機(jī)的。這是因?yàn)椋簭倪M(jìn)程調(diào)度的角度看，子進(jìn)程被創(chuàng)建后處于就緒態(tài)。此時(shí)，父進(jìn)程和子進(jìn)

19、程作為兩個(gè)獨(dú)立的進(jìn)程，共享同一個(gè)代碼段，分別參加調(diào)度、執(zhí)行，直至進(jìn)程結(jié)束。但是誰會(huì)先被調(diào)度程序選中執(zhí)行，則與系統(tǒng)的調(diào)度策略和系統(tǒng)當(dāng)前的資源狀態(tài)有關(guān)，是不確定的。因此，誰先從fork()函數(shù)中返回繼續(xù)執(zhí)行后面的語句也是不確定的。2、 進(jìn)程的軟中斷通信（1） 算法流程圖： 管道通信程序流程圖（2） 程序源代碼#include <unistd.h> #include <signal.h> #include <stdio.h> int pid1,pid2; / 定義兩個(gè)進(jìn)程變量 main( ) int fd2; char OutPipe100,InPipe100;

20、/ 定義兩個(gè)字符數(shù)組 pipe(fd); / 創(chuàng)建管道 while(pid1 = fork( ) = -1); / 如果進(jìn)程1創(chuàng)建不成功,則空循環(huán) if(pid1 = 0) / 如果子進(jìn)程1創(chuàng)建成功,pid1為進(jìn)程號(hào) lockf(fd1,1,0); / 鎖定管道 sprintf(OutPipe,"n Child process 1 is sending message!n"); / 給Outpipe賦值 write(fd1,OutPipe,50);/ 向管道寫入數(shù)據(jù) sleep(5); / 等待讀進(jìn)程讀出數(shù)據(jù) lockf(fd1,0,0); / 解除管道的鎖定 exit(0

21、); / 結(jié)束進(jìn)程1 else while(pid2 = fork() = -1); / 若進(jìn)程2創(chuàng)建不成功,則空循環(huán) if(pid2 = 0) lockf(fd1,1,0); sprintf(OutPipe,"n Child process 2 is sending message!n"); write(fd1,OutPipe,50); sleep(5); lockf(fd1,0,0); exit(0); else wait(0); / 等待子進(jìn)程1 結(jié)束 read(fd0,InPipe,50); / 從管道中讀出數(shù)據(jù) printf("%sn",InP

22、ipe); / 顯示讀出的數(shù)據(jù) wait(0); / 等待子進(jìn)程2 結(jié)束 read(fd0,InPipe,50); printf("%sn",InPipe); exit(0); / 父進(jìn)程結(jié)束 （3） 實(shí)驗(yàn)結(jié)果 （4） 簡(jiǎn)要分析 管道，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程，以實(shí)現(xiàn)它們之間信息的共享文件又稱pipe文件。向管道（共享文件）提供輸入的發(fā)送進(jìn)程（即寫進(jìn)程），以字符流形式將大量的數(shù)據(jù)送入管道；而接收管道輸送的接收進(jìn)程（讀進(jìn)程），可以從管道中接收數(shù)據(jù)。 為了協(xié)調(diào)雙方的通信，管道通信機(jī)制必須提供以下3方面的協(xié)調(diào)能力：1） 互斥。當(dāng)一個(gè)進(jìn)程正在對(duì)pipe進(jìn)程讀/寫操作時(shí)，另

23、一進(jìn)程必須等待，程序中使用lock(fd1,1,0)函數(shù)實(shí)現(xiàn)對(duì)管道的加鎖操作，用lock(fd1,0,0)解除管道的鎖定。2） 同步。當(dāng)寫進(jìn)程把一定數(shù)量的數(shù)據(jù)寫入pipe后，便去睡眠等待，直到讀進(jìn)程取走數(shù)據(jù)后，再把它喚醒。當(dāng)讀進(jìn)程試圖從一空管道中讀取數(shù)據(jù)時(shí)，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將其喚醒。3） 判斷對(duì)方是否存在。只有確定寫進(jìn)程和讀進(jìn)程都存在的情況下，才能通過管道進(jìn)行通信。四、 實(shí)驗(yàn)心得通過本次實(shí)驗(yàn)，我了解了進(jìn)程的實(shí)質(zhì)和進(jìn)程管理的機(jī)制，并通過實(shí)驗(yàn)操作掌握了有關(guān)的知識(shí)。實(shí)驗(yàn)是在 Linux 系統(tǒng)下實(shí)現(xiàn)進(jìn)程從創(chuàng)建到終止的全過程，從中我體會(huì)了進(jìn)程的創(chuàng)建過程、父進(jìn)程和子進(jìn)程的關(guān)系、

24、進(jìn)程狀態(tài)的變化、進(jìn)程之間的同步機(jī)制、 進(jìn)程調(diào)度的原理和以信號(hào)和管道為代表的進(jìn)程間通信方式的實(shí)現(xiàn)。當(dāng)然，在實(shí)驗(yàn)過程中還有許多不足，我一定會(huì)慢慢改正，提升自我。實(shí)驗(yàn)三 存儲(chǔ)器管理實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?、 理解內(nèi)存頁(yè)面調(diào)度的機(jī)理2、 掌握幾種理論頁(yè)面置換算法的實(shí)現(xiàn)方法3、 了解HASH數(shù)據(jù)結(jié)構(gòu)的使用4、通過實(shí)驗(yàn)比較幾種調(diào)度算法的性能優(yōu)劣頁(yè)面置換算法是虛擬存儲(chǔ)管理實(shí)現(xiàn)的關(guān)鍵，通過本次實(shí)驗(yàn)理解內(nèi)存頁(yè)面調(diào)度的機(jī)制，在模擬實(shí)現(xiàn)FIFO、LRU、NRU和OPT幾種經(jīng)典頁(yè)面置換算法的基礎(chǔ)上，比較各種頁(yè)面置換算法的效率及優(yōu)缺點(diǎn)，從而了解虛擬存儲(chǔ)實(shí)現(xiàn)的過程。二、實(shí)驗(yàn)內(nèi)容對(duì)比以下幾種算法的命中率：1、先進(jìn)先出算法 FIF

25、O（First In First Out）2、最近最少使用算法 LRU（Least Recently Used）3、最近未使用算法 NUR（Never Used Recently）4、最佳置換算法 OPT（Optimal Replacement）三、實(shí)驗(yàn)分析1、置換算法原理FIFO 原理簡(jiǎn)述：（1） 在分配內(nèi)存頁(yè)面數(shù)（AP）小天進(jìn)程頁(yè)面數(shù)（PP）時(shí)，當(dāng)然是最先運(yùn)行的 AP 個(gè)頁(yè)面放入內(nèi)存；（2） 這時(shí)又需要處理新的頁(yè)面，則將原來放的內(nèi)存中的 AP 個(gè)頁(yè)中最先進(jìn)入的調(diào)出（FIFO），再將新頁(yè)面放入；（3） 以后如果再有新頁(yè)面需要調(diào)入，則都按上述規(guī)則進(jìn)行。（4） 算法特點(diǎn)：所使用的內(nèi)存頁(yè)面構(gòu)成一個(gè)

26、隊(duì)列。LRU 算法原理簡(jiǎn)述（1） 當(dāng)內(nèi)存分配頁(yè)面數(shù)（AP）小于進(jìn)程頁(yè)面數(shù)（PP）時(shí)，把最先執(zhí)行的 AP 個(gè)頁(yè)面放入內(nèi)存。（2） 當(dāng)需調(diào)頁(yè)面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁(yè)面全部不空閑時(shí)，選擇將其中最長(zhǎng)時(shí)間沒有用到的那一頁(yè)調(diào)出，以空出內(nèi)存來放置新調(diào)入的頁(yè)面（LRU）。算法特點(diǎn)：每個(gè)頁(yè)面都有屬性來表示有多長(zhǎng)時(shí)間未被 CPU 使用的信息。NUR 算法原理簡(jiǎn)述所謂“最近未使用”，首先是要對(duì)“近”做一個(gè)界定，比如 CLEAR_PERIOD=50，便是 指在 CPU 最近的 50 次進(jìn)程頁(yè)面處理工作中，都沒有處理到的頁(yè)面。那么可能會(huì)有以下幾種 情況：（1） 如果這樣的頁(yè)面只有一個(gè)，就將其換出，放入需要處理的新

27、頁(yè)面。（2） 如果有這樣的頁(yè)面不止一個(gè)，就在這些頁(yè)面中任取一個(gè)換出（可以是下標(biāo)最小的或者最小的），放入需要處理的頁(yè)面。如果沒有一個(gè)這樣的頁(yè)面，就隨意換出一個(gè)頁(yè)面（可以是下標(biāo)最小的或者最大的）。OPT 原理簡(jiǎn)述所謂的最佳算法是一種理想狀況下的算法，它要求先遍歷所有的 CPU 待處理的進(jìn)程頁(yè)面序 列。在這些頁(yè)面中，如果有些已經(jīng)在內(nèi)存中，而 CPU 不再處理的，就將其換出；而有些頁(yè) 面已在內(nèi)存中而 CPU 即將處理，就從當(dāng)前位置算起，取最后才會(huì)處理到的頁(yè)面，將其換出。OPT 算法實(shí)現(xiàn):為每個(gè)進(jìn)程頁(yè)面設(shè)一個(gè)“間隔”屬性 cDistance 表示 CPU 將在第幾步處理到該頁(yè)面，如 果頁(yè)面不再被 CPU

28、 處理，可以被設(shè)為某個(gè)很大的值（如 32767），這樣每次被換出的就是 cDistance 最大的那個(gè)頁(yè)面。（1） 初始化。設(shè)置兩個(gè)數(shù)組 pageap和 pagecontrolpp分別表示進(jìn)程頁(yè)面數(shù)和內(nèi)存分 配的頁(yè)面數(shù)，并產(chǎn)生一個(gè)隨機(jī)數(shù)序列 maintotal_instruction（這個(gè)序列由 pageap的下標(biāo)隨機(jī)構(gòu)成）表示待處理的進(jìn)程頁(yè)面順序，diseffect 置 0。然后掃描整個(gè)頁(yè)面訪問序列，對(duì) cDistanceTOTAL_VP數(shù)組進(jìn)行賦值，表示該頁(yè)面將在第幾步被處理。（2） 看序列 main中是否有下一個(gè)元素，如果有，就由 main中獲取一個(gè) CPU 待處 理的頁(yè)面號(hào)，并轉(zhuǎn)（3）

29、，如果沒有則轉(zhuǎn)（6）。（3） 如果該頁(yè)面已經(jīng)在內(nèi)存中了，就轉(zhuǎn)（2），否則轉(zhuǎn)（4），同時(shí) diseffect 加 1。（4） 看是否有空閑頁(yè)面，如果有，就返回頁(yè)面指針，并轉(zhuǎn)到（5），否則，遍歷所有 未處理的進(jìn)程頁(yè)面序列，如果有位于內(nèi)存中的頁(yè)面而以后 CPU 不再處理的，首 將其換出，返回頁(yè)面指針；如果沒有這樣的頁(yè)面，找出 CPU 將最晚處理的頁(yè)面， 將其換出，并返回該頁(yè)面指針。（5） 在內(nèi)存頁(yè)面和待處理的進(jìn)程頁(yè)面之間建立聯(lián)系，轉(zhuǎn)（2）。 輸出計(jì)算 1-diseffect / total_instruction*100%的結(jié)果，完成。四、 實(shí)驗(yàn)步驟及結(jié)果（1）實(shí)驗(yàn)源程序：#include <

30、iostream>#include <string>#include <vector>#include <cstdlib>#include <cstdio>#include <unistd.h>using namespace std;#define INVALID -1const int TOTAL_INSTRUCTION(320);const int TOTAL_VP(32);const int CLEAR_PERIOD(50);#include "Page.h"#include "PageCon

31、trol.h"#include "Memory.h" int main()int i; CMemory a; for(i=4;i<=32;i+)a.FIFO(i);a.LRU(i); a.NUR(i); a.OPT(i); cout<<"n"return 0;#ifndef _MEMORY_H#define _MEMORY_Hclass CMemorypublic: CMemory();void initialize(const int nTotal_pf); void FIFO(const int nTotal_pf); v

32、oid LRU(const int nTotal_pf); void NUR(const int nTotal_pf); void OPT(const int nTotal_pf);private:vector<CPage> _vDiscPages;vector<CPageControl> _vMemoryPages;CPageControl *_pFreepf_head,*_pBusypf_head,*_pBusypf_tail;vector<int> _vMain,_vPage,_vOffset;int _nDiseffect; CMemory:CMem

33、ory():_vDiscPages(TOTAL_VP),_vMemoryPages(TOTAL_VP),_vMain(TOTAL_INSTRUCTION),_vPage(TOTAL_INSTRUCTION),_vOffset(TOTAL_INSTRUCTION)int S,i,nRand; srand(getpid()*10); nRand=rand()%32767;S=(float)319*nRand/32767+1;for(i=0;i<TOTAL_INSTRUCTION;i+=4)_vMaini=S;_vMaini+1=_vMaini+1nRand=rand()%32767;_vMa

34、ini+2=(float)_vMaini*nRand/32767;_vMaini+3=_vMaini+2+1;nRand=rand()%32767;S=(float)nRand *(318-_vMaini+2)/32767+_vMaini+2+2;for(i=0;i<TOTAL_INSTRUCTION;i+)_vPagei=_vMaini/10;_vOffseti=_vMaini%10;_vPagei%=32;void CMemory:initialize(const int nTotal_pf)int ix;_nDiseffect=0;for(ix=0;ix<_vDiscPage

35、s.size();ix+)_vDiscPagesix.m_nPageNumber=ix;_vDiscPagesix.m_nPageFaceNumber=INVALID;_vDiscPagesix.m_nCounter=0;_vDiscPagesix.m_nTime=-1;for(ix=1;ix<nTotal_pf;ix+)_vMemoryPagesix-1.m_pNext=&_vMemoryPagesix;_vMemoryPagesix-1.m_nPageFaceNumber=ix-1;_vMemoryPagesnTotal_pf-1.m_pNext=NULL;_vMemoryP

36、agesnTotal_pf-1.m_nPageFaceNumber=nTotal_pf-1;_pFreepf_head=&_vMemoryPages0;void CMemory:FIFO(const int nTotal_pf)int i; CPageControl *p; initialize(nTotal_pf);_pBusypf_head=_pBusypf_tail=NULL;for(i=0;i<TOTAL_INSTRUCTION;i+)if(_vDiscPages_vPagei.m_nPageFaceNumber=INVALID)_nDiseffect+=1;if(_pF

37、reepf_head=NULL)/no empty pagesp=_pBusypf_head->m_pNext;_vDiscPages_pBusypf_head->m_nPageNumber.m_nPageFaceNumber=INVALID;_pFreepf_head=_pBusypf_head;_pFreepf_head->m_pNext=NULL;_pBusypf_head=p;p=_pFreepf_head->m_pNext;_pFreepf_head->m_pNext=NULL;_pFreepf_head->m_nPageNumber=_vPage

38、i;_vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;if(_pBusypf_tail=NULL)_pBusypf_head=_pBusypf_tail=_pFreepf_head;else_pBusypf_tail->m_pNext=_pFreepf_head;_pBusypf_tail=_pFreepf_head;_pFreepf_head=p;cout<<"FIFO: "<<1-(float)_nDiseffect/320;void CMemo

39、ry:LRU(const int nTotal_pf)int i,j,nMin,minj,nPresentTime(0); initialize(nTotal_pf); for(i=0;i<TOTAL_INSTRUCTION;i+)if(_vDiscPages_vPagei.m_nPageFaceNumber=INVALID)_nDiseffect+;if(_pFreepf_head=NULL)nMin=32767;for(j=0;j<TOTAL_VP;j+) /get the subscribe of the least used pageif(nMin>_vDiscPag

40、esj.m_nTime&&_vDiscPagesj.m_nPageFaceNumber!=INVALID)nMin=_vDiscPagesj.m_nTime;minj=j;_pFreepf_head=&_vMemoryPages_vDiscPagesminj.m_nPageFaceNumber;_vDiscPagesminj.m_nPageFaceNumber=INVALID;_vDiscPagesminj.m_nTime=-1;_pFreepf_head->m_pNext=NULL;_vDiscPages_vPagei.m_nPageFaceNumber=_pF

41、reepf_head->m_nPageFaceNumber;_vDiscPages_vPagei.m_nTime=nPresentTime;_pFreepf_head=_pFreepf_head->m_pNext;else_vDiscPages_vPagei.m_nTime=nPresentTime;nPresentTime+;cout<<"LRU: "<<1-(float)_nDiseffect/320;void CMemory:NUR(const int nTotal_pf)int i,j,nDiscPage,nOld_DiscPag

42、e; bool bCont_flag; initialize(nTotal_pf); nDiscPage=0;for(i=0;i<TOTAL_INSTRUCTION;i+)if(_vDiscPages_vPagei.m_nPageFaceNumber=INVALID)_nDiseffect+;if(_pFreepf_head=NULL) bCont_flag=true;nOld_DiscPage=nDiscPage;while(bCont_flag)if(_vDiscPagesnDiscPage.m_nCounter=0&&_vDiscPagesnDiscPage.m_n

43、PageFaceNumber!=INVALID)bCont_flag=false;elsenDiscPage+;if(nDiscPage=TOTAL_VP) nDiscPage=0;if(nDiscPage=nOld_DiscPage)for(j=0;j<TOTAL_VP;j+)_vDiscPagesj.m_nCounter=0;_pFreepf_head=&_vMemoryPages_vDiscPagesnDiscPage.m_nPageFaceNumber;_vDiscPagesnDiscPage.m_nPageFaceNumber=INVALID;_pFreepf_head

44、->m_pNext=NULL;_vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;_pFreepf_head=_pFreepf_head->m_pNext;else_vDiscPages_vPagei.m_nCounter=1;if(i%CLEAR_PERIOD=0)for(j=0;j<TOTAL_VP;j+)_vDiscPagesj.m_nCounter=0;cout<<"NUR:"<<1-(float)_nDiseffect/320;v

45、oid CMemory:OPT(const int nTotal_pf)int i,j,max,maxpage,nDistance,vDistanceTOTAL_VP;initialize(nTotal_pf);for(i=0;i<TOTAL_INSTRUCTION;i+)if(_vDiscPages_vPagei.m_nPageFaceNumber=INVALID)_nDiseffect+;if(_pFreepf_head=NULL)for(j=0;j<TOTAL_VP;j+if(_vDiscPagesj.m_nPageFaceNumber!=INVALID)vDistancej

46、=32767;else vDistancej=0; nDistance=1;for(j=i+1;j<TOTAL_INSTRUCTION;j+)if(_vDiscPages_vPagej.m_nPageFaceNumber!=INVALID)&&(vDistance_vPagej=32767)vDistance_vPagej=nDistance;nDistance+; max=-1;for(j=0;j<TOTAL_VP;j+)if(max<vDistancej)max=vDistancej;maxpage=j;_pFreepf_head=&_vMemor

47、yPages_vDiscPagesmaxpage.m_nPageFaceNumber;_pFreepf_head->m_pNext=NULL;_vDiscPagesmaxpage.m_nPageFaceNumber=INVALID;_vDiscPages_vPagei.m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;_pFreepf_head=_pFreepf_head->m_pNext;cout<<"OPT:"<<1-(float)_nDiseffect/320;（2）實(shí)驗(yàn)結(jié)果

48、：五、實(shí)驗(yàn)心得通過本次實(shí)驗(yàn)，我學(xué)習(xí)了內(nèi)存頁(yè)面調(diào)度的機(jī)制，對(duì)在課堂上學(xué)的幾種理論頁(yè)面置換算法的掌握也更加牢固了。同時(shí)，我還了解了 HASH 數(shù)據(jù)結(jié)構(gòu)的使用。實(shí)驗(yàn)過程中通過實(shí)現(xiàn)這幾種算法，比較了較各種頁(yè) 面置換算法的效率及優(yōu)缺點(diǎn)，從而了解了虛擬存儲(chǔ)實(shí)現(xiàn)的過程。實(shí)驗(yàn)四 一個(gè)簡(jiǎn)單文件系統(tǒng)的實(shí)現(xiàn)一、 實(shí)驗(yàn)?zāi)康?、 熟悉Ext文件系統(tǒng)的原理2、 根據(jù)Ext文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和構(gòu)建方法，自行實(shí)現(xiàn)一個(gè)簡(jiǎn)單的內(nèi)存文件系統(tǒng)。二、 實(shí)驗(yàn)內(nèi)容1、 定義一個(gè)數(shù)組代表磁盤存儲(chǔ)空間，在其上建立并維護(hù)超級(jí)塊、位圖、inode表等各種數(shù)據(jù)結(jié)構(gòu)。2、 在此基礎(chǔ)上，實(shí)現(xiàn)文件系統(tǒng)的常用接口，如open，create，read，wri

49、te，close等。三、 實(shí)驗(yàn)原理1、 Ext文件系統(tǒng)結(jié)構(gòu)： 2、 引導(dǎo)塊BootBlock 每個(gè)硬盤分區(qū)的開頭1024字節(jié)，即0 byte至1023 byte是分區(qū)的啟動(dòng)扇區(qū)。存放由ROM BIOS自動(dòng)讀入的引導(dǎo)程序和數(shù)據(jù)，但這只對(duì)引導(dǎo)設(shè)備有效，而對(duì)于非引導(dǎo)設(shè)備，該引導(dǎo)塊不含代碼。這個(gè)塊與ext2沒有任何關(guān)系。3、 超級(jí)塊SuperBlock每個(gè)分區(qū)均有一個(gè)super block塊，定義了文件系統(tǒng)的全局信息，包括塊的大小，總塊數(shù)，空閑塊，索引結(jié)點(diǎn)數(shù)，各種位圖和i節(jié)點(diǎn)表的地址和大小等信息。4、 數(shù)據(jù)塊位圖這是ext2管理存儲(chǔ)空間的方法。即位圖法。每個(gè)位對(duì)應(yīng)一個(gè)數(shù)據(jù)塊，位值為0表示空閑，1表示已經(jīng)分配。數(shù)據(jù)塊位圖定義為一個(gè)塊大小。于是，一個(gè)組中的數(shù)據(jù)塊個(gè)數(shù)就決定了。假設(shè)塊大小為b 字節(jié)?？梢詤^(qū)別的塊數(shù)為b*8個(gè) 5、 數(shù)據(jù)塊 DataBlocks每個(gè)組的數(shù)據(jù)最大個(gè)數(shù)是在塊大小定義后就確定了的。所以組容量也就確定了。假設(shè)塊大小為b 字節(jié)。那么組容量就確