西安交通大學操作系統(tǒng)課內(nèi)實驗報告

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

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

3、供各種接口來實現(xiàn) 人機交互。經(jīng)典的操作系統(tǒng)理論將操作系統(tǒng)的接口分為控制臺命令和系統(tǒng)調(diào)用兩種。前者主 要提供給計算機的操作人員對計算機進行各種控制；而后者則提供個程序員，使他們可以方 便地使用計算機的各種資源。四、 實驗步驟及結(jié)果1、 控制臺命令接口實驗（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)計/my 目錄下 c 語言文件的個數(shù)通過 bash 腳本，可以有多種方式實現(xiàn)這個功能，而使用函數(shù)是其中個一個選擇。在使用函數(shù)之前，必須先定義函數(shù)。 進入自己的工作目錄，編寫名為 count 的文件。腳本程序：#! /bin/bashfunctioncountechon" Number of matches for $1: "#接收程序的第一個參數(shù)ls$1|wc l#對子程序的第一個參數(shù)所在的目錄進行操作將 count 文件復制到當前目錄下，然后在當前目錄下建立文件夾，在 my 目錄下建立幾個 c 文件,以便用來進行測試。2、 添加系統(tǒng)調(diào)用 （1）編程調(diào)用一

5、個系統(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; 實驗結(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. 進入/usr/src目錄命令：cd /usr/src 4. 解壓linux源碼命令：tar xvzf linux-3.0.tar.bz2 5. 進入目錄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)用號 并修改文件中的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個線程編譯） 13. 編譯內(nèi)核模塊命令：make j4 modules14. 安裝內(nèi)核模塊命令：make modules_install15. 安裝內(nèi)核命令：make inst

9、all 16. 重啟系統(tǒng)，在系統(tǒng)選擇頁面選擇進入自己編譯的linux-3.0內(nèi)核 17. 在桌面建立測試的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)用號 return 0; 18. 編譯程序gcc test.c o a.out 19. 運行程序./a.out 20. 查看內(nèi)核日志（printk的輸出信息在內(nèi)核日志中）：dmesg結(jié)果：（1）編譯內(nèi)核成功截圖:（2）編譯模塊成功截圖:五、實驗問題及分析在進行內(nèi)核編譯時，遇到

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

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

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

13、rocess 2 is sending a message!而父進程則從管道中讀出來自于兩個子進程的信息，顯示在屏幕上。要求：父進程先接收子進程 P1 發(fā)來的消息，然后再接收子進程 P2 發(fā)來的消息。三、 實驗步驟及結(jié)果分析1、 進程的軟中斷通信（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; / 定義兩個進程號變量 signal(3,stop); / 或者 signal(14,stop); while(pid1 = fork( ) = -1);/ 若創(chuàng)建子進程1不成功,則空循環(huán)if(pid1 > 0) / 子進程創(chuàng)建成功,pid1為進程號 while(pid2 = fork( ) = -1);/ 創(chuàng)建子進程2 if(pid2 > 0) wait_flag = 1; sleep(5); / 父進程等待5秒 kill(pid1,16); / 殺死進程1kill(pid2,17); / 殺死進程2 wait(0); / 等待第1個子進程1結(jié)束的信號 wa

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

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

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

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

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

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

21、); / 結(jié)束進程1 else while(pid2 = fork() = -1); / 若進程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); / 等待子進程1 結(jié)束 read(fd0,InPipe,50); / 從管道中讀出數(shù)據(jù) printf("%sn",InP

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

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

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

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

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

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

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

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

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

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