實

　驗

　報

　告

　 實驗課程：

　計算機操作系統

　學生姓名：

　張虹

　學

　號：

　 6100409033

　 專業班級：

　電氣信息類 III 091 班

　0 2010 年 年 2 12 月 月 8 18 日

　目錄

　 操作系統安裝及其接口環境 ............................. 2 編程實現銀行家安全算法 ................................ 7 進程調度算法的實現 ................................... 16 存儲管理的模擬實現 ................................... 22

　 告 南昌大學實驗報告 ---操作系統安裝及其接口環境 學生姓名：

　張虹

　學

　號：

　6100409033

　 專業班級：

　 電Ⅲ091 班

　 實驗類型：□ 驗證 ■ 綜合 □ 設計 □ 創新

　 實驗日期：

　實驗成績：

　 一、實驗目的 熟悉 Windows//Linux 操作系統的安裝過程與安裝方法，并掌握該操作系統所提供的用戶接口環境，并為后續實驗做好編程環境準備。

　二、實驗內容 1、熟悉 Windows//Linux 操作系統的安裝過程與安裝方法，并掌握該操作系統所提供的用戶接口環境，通過系統提供的用戶管理程序、查看系統中的用戶情況、進程、線程、內存使用情況等，學會使用它進行監視進程的狀況、系統資源的使用情況及用戶情況。并為后續實驗做好編程環境準備。

　2、用 C 語言編寫一小段程序，使其可以通過某個系統調用來獲得 OS 提供的某種服務。

　三、實驗要求 1． 了解所安裝的操作系統對軟硬件資源的具體要求； 2． 機器最低硬件配置要求； 3． 操作系統所提供的用戶接口環境的熟悉； 4． 了解主要 BIOS CMOS 參數的含義及其設置方法； 5． 掌握程序編寫中系統調用的方法。

　四、主要實驗步驟 1、可以通過 Vmware workstation 虛擬機來模擬并記錄安裝 Windows 和 Linux 的過程，主要要準備光盤（虛擬機也可使用光盤鏡像 ISO 文件或精靈虛擬光驅），若計算機已經裝有一個操作系統，則在安裝之前要注意：如果是使用光盤用電腦自帶光驅安裝，則安裝之前必須設定計算機的 BIOS，讓計算機從光驅啟動；若是使用 USB 光驅或者是 U 盤引導，則要設定 BIOS 使計算機從 USB 接口啟動。安裝系統主要需要輸入序列號，設定管理員及使用者姓名和身份密碼。用戶可以選擇要安裝的系統程序（Linux 為軟件包），或者也可以在安裝完后在控制面板的添加/刪除程序中選擇。安裝方法一般來說使用光盤直接安裝，將光盤放入光驅中，沒有光驅的電腦可以使用 USB 光驅或者使用 U 盤安裝。

　2、熟悉查看用戶的接口環境可以使用系統自帶的管理程序，操作如下：

　“右擊我的電腦”——“管理”——“設備管理器”，也可以“右擊我的電腦”——“屬性”——“硬件”——“設備管理器”，進入設備管理器可以看到計算機的設備情況，包括計算機的各個接口。

　3、查看系統中的用戶情況、進程、線程、內存使用情況，可進行如下操作：

　“右擊我的電腦”——“管理”——“本地用戶和組”——“用戶”，這樣就可以查看系統中的用戶情況，并可以對用戶進行添加、刪除、禁用、修改等操作。

　使用任務管理器可以看到系統中活動的用戶、系統中的進程、線程和內存的使用情況，進行的操作如下：

　“右擊任務欄”——“任務管理器”，或者直接在鍵盤上使用 ctrl+alt+delete 的快捷鍵打開任

　務管理器。在任務管理器中，點擊“進程”就可以看見當前計算機在運行的進程及該進程的用戶、CPU 占用率和內存使用情況。點擊“性能”即可看見計算機當前 CPU 的使用、CPU 使用記錄、PF 使用率、頁面文件使用記錄和線程數。點擊“用戶”就可以看見當前計算機活動的用戶。

　4、調用系統服務：

　打開 Microsoft Visual C++ 6.0，新建 C++ Sourse File，寫入以下代碼：

　#include<stdlib.h> void main() {

　 system("date"); } 保存，使用工具編譯，得到結果。

　五、實驗數據及處理結果 安裝 Windows Xp Sp2 的過程：

　 安裝 Ubuntu Linux 10.04 的過程：

　以下是計算機 Xs19 的情況，Xs19 中 Windows Xp 的設備管理器：

　Xs19 中 Windows Xp 的用戶情況：

　Xs19 的任務管理器：

　調度服務的結果：

　六、實驗體會或對改進實驗的建議 感覺這個實驗不是光靠掌握書上內容就能做的，平時的實踐也是非常重要的，如果對計算機非常熟悉的話，這個實驗做起來難度很小。在做的時候基本上可以完成，中間碰到一個問題，就是對計算機有的系統服務不熟悉，所以要用 C 語言編程時感覺有點不知所措。

　七、參考資料 《計算機操作系統》（第三版）

　《計算機操作系統實驗指導書》

　 告 南昌大學實驗報告 ---編程實現銀行家安全算法 學生姓名：

　張虹

　學

　號：

　6100409033

　 專業班級：

　 電Ⅲ091 班

　 實驗類型：□ 驗證 ■ 綜合 □ 設計 □ 創新

　 實驗日期：

　實驗成績：

　一、實驗目的 通過實驗加強對銀行家安全算法的理解和掌握。

　二、實驗內容 熟悉避免死鎖發生的方法，死鎖與安全序列的關系，編程實現銀行家算法，要求輸出進程的安全序列。

　三、實驗要求 1、 需寫出設計說明； 2、 設計實現代碼及說明 3、 運行結果； 四、主要實驗步驟 1、 分析銀行家算法結構； 2、 畫出銀行家算法的流程圖，即設計說明； 3、 根據畫出的流程圖使用 C 語言編寫相應的代碼（代碼過長，放到最后）； 程序主要由 main 函數和以下幾個函數組成：

　void input();用戶輸入銀行家算法的初始數據； void output();輸出當前系統資源分配情況； void change();當請求資源滿足要求時，進行分配，系統資源發生改變； int check();安全性算法，檢查是否存在安全序列； void outputsafe();輸出安全序列的資源分配表。

　4、 檢查代碼，將編出的代碼編譯、鏈接，驗證其正確性。

　開始輸入銀行家算法初始數據執行安全性算法數據是否正確是否存在安全序列輸入進程Pi 發出的請求向量請求資源是否小于需求資源系統將資源分配給 Pi執行算法的是否為初始數據結束資源分配無效 ， 恢復分配前的系統資源情況輸出當前資源分配表N NY YN NY YN NY Y輸出安全序列的資源情況是否有進程發出請求向量N NY YN NY Y請求資源是否小于系統資源Y Y進程Pi需等待N NY Y

　五、實驗數據及處理結果

　 六、實驗體會或對改進實驗的建議 體會：編寫銀行家算法需要較好分析能力，C 語言也要掌握的很好，而且需要細心和極大地耐心。我的程序在最開始編出來的第一份代碼編譯時大大小小一堆錯誤，有些是一個小錯誤導致了下面全錯，這些小錯誤在一百多行里找起來非常費勁。然后小錯誤全部找出來以后，再編譯，錯誤沒有了，但是得到的結果卻是錯誤的，這樣又要開始一行一行分析，看是哪里出了問題。到最后得到了想要的結果以后，程序還需要修飾，至少要輸出要簡潔明朗，要讓別人一運行這個程序就知道自己在什么時候該輸入什么數據，數據是什么作用，而不是只有自己知道輸進去的是什么東西。

　七、參考資料 《計算機操作系統》 《C 程序設計》 《C 語言程序設計_現代方法》 八、實驗代碼 #include <stdio.h> #include <stdlib.h> #include <string.h> int max[5][3];

　//開始定義銀行家算法中需要用到的數據 int allocation[5][3]; int need[5][3]; int available[3]; int request[5][3]; char *finish[5]; int safe[5]; int n,i,m; int k=0;

　int j=0; int work[3]; int works[5][3]; void start(); //表示程序開始 void end(); //表示程序結束 void input(); //輸入數據 void output(); //輸出數據 void change(); //系統分配資源，原有資源情況改變 void outputsafe(); //輸出安全序列的資源分配情況 int check(); //安全性算法 void main()

　//主程序開始 {

　start();

　for (;j==0;)

　 //確認輸入數據的正確性，若輸入錯誤，重新輸入

　{

　 input();

　 printf("以下為進程資源情況，請確認其是否正確：\n");

　 output();

　 printf("數據是否無誤：\n 正確：輸入\n 錯誤：輸入\n 請輸入：");

　 scanf("%d",&j);

　}

　printf("數據確認無誤，算法繼續。\n");

　if (check()==0)

　 //若 check 函數返回值為，表示輸入的初始數據找不到安全序列，無法進行下一步，程序結束

　{

　 end();

　 exit(0);

　}

　for(;j==1;)

　 //當有多個進程請求資源時，循環開始

　{

　 printf("請輸入請求資源的進程 i(0、、、、)：");

　//輸入發出請求向量的進程及請求向量

　 scanf("%d",&i);

　 printf("請輸入進程 P%d 的請求向量 Request%d：",i,i);

　 for(n=0;n<3;n++)

　scanf("%d",&request[i][n]);

　 for (;request[i][0]>need[i][0] || request[i][1]>need[i][1] || request[i][2]>need[i][2];) //若請求向量大于需求資源，則認為是輸入錯誤，要求重新輸入

　 {

　printf("數據輸入有誤，請重試！\n 請輸入進程 P%d 的請求向量 Request%d：",i,i);

　for(n=0;n<3;n++)

　 scanf("%d",&request[i][n]);

　 }

　if(request[i][0]<=available[0] && request[i][1]<=available[1] && request[i][2]<=available[2])

　//判斷系統是否有足夠資源提供分配

　 {

　printf("系統正在為進程 P%d 分配資源……\n",i);

　change();

　//分配資源

　j=0;

　 }

　 else

　printf("系統沒有足夠的資源，進程 P%d 需要等待。\n",i);

　 if (j==0)

　 //j=0 表示系統有足夠資源分配的情況

　 {

　printf("當前系統資源情況如下：\n");

　//輸出分配資源后的系統資源分配情況

　output();

　if(check()==0)

　//若找不到安全系列，則之前的資源分配無效

　{

　 printf("本次資源分配作廢，恢復原來的資源分配狀態。\n");

　 for (m=0;m<3;m++)

　//恢復分配資源前的系統資源狀態

　 {

　available[m]+=request[i][m];

　allocation[i][m]-=request[i][m];

　need[i][m]+=request[i][m];

　 }

　output();

　 //輸出系統資源狀態

　}

　 }

　 printf("是否還有進程請求資源？\n 是：輸入\n 否：輸入\n 請輸入：");

　 scanf("%d",&j);

　//若還有進程請求資源，j=1，之前的 for 循環條件滿足

　}

　end(); } void line()

　 //美化程序，使程序運行時更加明朗美觀 {

　printf("------------------------------------------------------------------\n"); }

　void start()

　 //表示銀行家算法開始 {

　line();

　printf("

　 銀行家算法開始\n");

　printf("

　 ——Designed by Zhang Hong\n");

　line(); }

　void end()

　 //表示銀行家算法結束

　{

　line();

　printf("

　 銀行家算法結束，謝謝使用\n");

　line(); }

　void input()

　//輸入銀行家算法起始各項數據 {

　 for (n=0;n<5;n++)

　 {

　printf("請輸入進程 P%d 的相關信息：\n",n);

　printf("Max:");

　for (m=0;m<3;m++)

　 scanf("%d",&max[n][m]);

　printf("Allocation:");

　for (m=0;m<3;m++)

　 scanf("%d",&allocation[n][m]);

　for (m=0;m<3;m++)

　 need[n][m]=max[n][m]-allocation[n][m];

　 }

　printf("請輸入系統可利用資源數 Available:");

　for (m=0;m<3;m++)

　 scanf("%d",&available[m]); }

　void output()

　//輸出系統現有資源情況 {

　line();

　printf("資源情況

　 Max

　 Allocation

　Need

　Available\n");

　printf("進程

　 A

　B

　C

　A

　B

　C

　 A

　B

　C

　 A

　B

　C\n");

　line();

　for(n=0;n<5;n++)

　{

　 printf("P%d%9d%3d%3d%5d%3d%3d%6d%3d%3d",n,max[n][0],max[n][1],max[n][2],allocation[n][0],allocation[n][1],allocation[n][2],need[n][0],need[n][1],need[n][2]);

　 if (n==0)

　printf("%6d%3d%3d\n",available[0],available[1],available[2]);

　 else

　printf("\n");

　}

　line(); }

　void change()

　 //當 Request[i,j]<=Available[j]時，系統把資源分配給進程 P[i]，Available[j]和 Need[i,j]發生改變 {

　for (m=0;m<3;m++)

　{

　 available[m]-=request[i][m];

　 allocation[i][m]+=request[i][m];

　 need[i][m]-=request[i][m];

　} }

　void outputsafe()

　 //輸出安全序列的資源分配表 {

　printf("該安全序列的資源分配圖如下：\n");

　line();

　printf("資源情況

　Work

　 Need

　Allocation Work+Allocation

　Finish\n");

　printf("進程

　 A

　B

　C

　A

　B

　C

　A

　B

　C

　 A

　B

　C\n");

　line();

　for(n=0;n<5;n++)

　 printf("P%d%9d%3d%3d%5d%3d%3d%5d%3d%3d%6d%3d%3d%12s\n",safe[n],works[safe[n]][0],works[safe[n]][1],works[safe[n]][2],need[safe[n]][0],need[safe[n]][1],need[safe[n]][2],allocation[safe[n]][0],allocation[safe[n]][1],allocation[safe[n]][2],works[safe[n]][0]+allocation[safe[n]][0],works[safe[n]][1]+allocation[safe[n]][1],works[safe[n]][2]+allocation[safe[n]][2],finish[n]);

　line(); }

　int check()

　//安全性算法 {

　printf("開始執行安全性算法……\n");

　for (m=0;m<3;m++)

　//數組 work 和 finish 初始化

　 work[m]=available[m];

　for (n=0;n<5;n++)

　{

　 finish[n]="false";

　 safe[n]=0;

　}

　k=0;

　for (m=0;m<5;m++)

　 for (n=0;n<5;n++)

　if(strcmp(finish[n],"false")==0 && need[n][0]<=work[0] && need[n][1]<=work[1] && need[n][2]<=work[2])

　 //查找可以分配資源但尚未分配到資源的進程

　{

　 safe[k]=n;

　//以數組 safe[k]記下各個進程得到分配的資源的順序

　works[safe[k]][0]=work[0];

　 works[safe[k]][1]=work[1];

　 works[safe[k]][2]=work[2];

　 work[0]+=allocation[n][0];

　 //進程執行后釋放出分配給它的資源

　 work[1]+=allocation[n][1];

　 work[2]+=allocation[n][2];

　 finish[n]="ture"; //finish[n]變為以示該進程完成本次分

　 k++;

　}

　for (m=0;m<5;m++)

　//判斷是否所有進程分配資源完成

　{

　 if (strcmp(finish[m],"false")==0)

　 {

　printf("找不到安全序列，系統處于不安全狀態。\n");

　return 0;

　//找不到安全序列，結束 check 函數，返回

　 }

　 else

　 if (m==4)

　 //此處 m=4 表示所有數組 finish 的所有元素都為 ture

　{

　 printf("找到安全序列 P%d->P%d->P%d->P%d->P%d，系統是安全的\n",safe[0],safe[1],safe[2],safe[3],safe[4]);

　 j=1;

　 outputsafe();

　 //輸出安全序列的資源分配表

　}

　}

　return 1; }

　 告 南昌大學實驗報告

　---進程調度算法的實現 學生姓名：

　張虹

　學

　號：

　6100409033

　 專業班級：

　 電Ⅲ091 班

　 實驗類型：□ 驗證 ■ 綜合 □ 設計 □ 創新

　 實驗日期：

　實驗成績：

　 一、實驗目的 通過實驗加強對進程調度算法的理解和掌握。

　二、實驗內容 編寫程序實現進程調度算法，具體可以編寫程序實現先來先服務算法或優先度高者調度算法。

　三 、實驗要求 1、 需寫出設計說明； 2、 設計實現代碼及說明 3、 運行結果； 四、主要實驗步驟 1、 分析實驗內容，畫出算法流程圖； 2、 根據流程圖寫出實驗代碼； 3、 編譯代碼，驗證結果正確與否； 4、 對程序進行修改，得到最后結果。

　流程圖如下：

　開始系統隨機產生數據將數據按照到達時間從小到大排序用戶輸入數據進程到達時前一個進程是否已經完成完成時間=服務時間+前一個進程完成時間完成時間=服務時間+到達時間周轉時間=完成時間-到達時間帶權周轉時間=完成時間/服務時間是否所有進程已完成計算輸出結果結束YNYNYN

　五、實驗數據及處理結果

　六、實驗體會或對改進實驗的建議 在做這個實驗的時候，一開始以為很簡單，只要做簡單的加減乘除就行了，但是仔細做過以后發現需要考慮很多情況。比如說輸入進程到達時間的時候，要是亂序的該怎么辦？還有到達時間和服務時間等等定義的都是整型變量，但是帶權周轉時間確會得到小數，此時就需要用到強制轉換。在做系統產生隨機數的時候也要考慮隨機數的范圍，如到達時間可以為0，但是服務時間卻不能為 0，否則帶權周轉時間的計算會出錯。

　七、參考資料 《計算機操作系統》 《計算機操作系統實驗指導書》 《C 程序設計》 《C 語言程序設計_現代方法》 八、實驗代碼 #include <stdio.h>

　#include <stdlib.h> #include <time.h> #define N 5

　 //進程個數，可改變 int rt[N];

　//到達時間 int st[N];

　//服務時間 int ct[N];

　//完成時間 int cyt[N]; //周轉時間 float rct[N]; //帶權周轉時間 float av[2]; //平均數 int n,m; void start(); //表示程序開始 void end(); //表示程序結束 void input(); //輸入數據 void random(); //系統隨機產生數據 void ordination(); //對數據按到達時間進行排序 void fcfs(); //先來先服務計算 void output(); //輸出結果 void main() {

　start();

　int which;

　int c=1;

　for (;c==1;)

　{

　 for (;;)

　 {

　printf("輸入數據還是由系統隨機產生數據？\n1、輸入數據\t2、系統隨機產生數據\n 請輸入：");

　scanf("%d",&which);

　if (which==1)

　{

　 input();

　 break;

　}

　else

　 if (which==2)

　 {

　random();

　break;

　 }

　 else

　printf("輸入錯誤，請重新輸入！");

　 }

　 ordination();

　//進程按照到達時間進行排序

　fcfs();

　 output();

　 printf("繼續輸入，退出輸入。請輸入：");

　 scanf("%d",&c);

　}

　end(); } void line()

　 //美化程序，使程序運行時更加明朗美觀 {

　printf("------------------------------------------------------------------\n"); } void start()

　 //表示 FCFS 算法開始 {

　line();

　printf("

　 FCFS 算法開始\n");

　printf("

　 ——Designed by Zhang Hong\n");

　line(); } void end()

　 //表示 FCFS 算法結束 {

　line();

　printf("

　 FCFS 算法結束,謝謝使用\n");

　line(); } void input() {

　printf("請輸入%d 個進程的到達時間：",N);

　for (n=0;n<N;n++)

　 scanf("%d",&rt[n]);

　printf("請輸入%d 個進程對應的服務時間：",N);

　for (n=0;n<N;n++)

　 scanf("%d",&st[n]); } void random() {

　srand((unsigned)time(NULL));

　for (n=0;n<N;n++)

　{

　 rt[n]=rand()%100;

　 for (m=0;m<n;m++)

　if (n!=0 && rt[n]==rt[m])

　{

　 rt[n]=rand()%100;

　 m=0;

　 }

　 st[n]=rand()%98+1;

　 for (m=0;m<n;m++)

　if (n!=0 && st[n]==st[m])

　{

　 st[n]=rand()%98+1;

　 m=0;

　}

　} } void ordination()

　//重新排序，應對出現輸入的到達時間為亂序的情況 {

　int temp;

　for (n=0;n<N;n++)

　 for (m=0;m<N-n-1;m++)

　if (rt[m+1]<rt[m])

　{

　 temp=rt[m+1];

　 rt[m+1]=rt[m];

　 rt[m]=temp;

　 temp=st[m+1];

　 st[m+1]=st[m];

　 st[m]=temp;

　} } void fcfs()

　 //執行 fcfs 算法 {

　av[0]=0;

　av[1]=0;

　ct[0]=rt[0]+st[0];

　for (n=1;n<N;n++)

　{

　 if (ct[n-1]>=rt[n])

　//考慮當前一個進程完成而后一個進程還沒有到達的情況

　ct[n]=ct[n-1]+st[n];

　 else

　ct[n]=rt[n]+st[n];

　}

　for (n=0;n<N;n++)

　 cyt[n]=ct[n]-rt[n];

　for (n=0;n<N;n++)

　 rct[n]=(float)cyt[n]/(float)st[n];

　for (n=0;n<N;n++)

　{

　 av[0]+=(float)cyt[n]/N;

　av[1]+=rct[n]/N;

　} } void output()

　 //輸出結果 {

　line();

　printf("進程名\t");

　for (n=0;n<N;n++)

　 printf("\t%c",65+n);

　printf("\t 平均\n 到達時間");

　for (n=0;n<N;n++)

　 printf("\t%d",rt[n]);

　printf("\n 服務時間");

　for (n=0;n<N;n++)

　 printf("\t%d",st[n]);

　printf("\n 完成時間");

　for (n=0;n<N;n++)

　 printf("\t%d",ct[n]);

　printf("\n 周轉時間");

　for (n=0;n<N;n++)

　 printf("\t%d",cyt[n]);

　printf("\t%0.1f",av[0]);

　printf("\n 帶權周轉時間");

　for (n=0;n<N;n++)

　 printf("\t%0.1f",rct[n]);

　printf("\t%0.1f",av[1]);

　printf("\n");

　line(); }

　 南昌大學實驗報告

　---存儲管理的模擬實現 學生姓名：

　張虹

　學

　號：

　6100409033

　 專業班級：

　 電Ⅲ091 班

　 實驗類型：□ 驗證 ■ 綜合 □ 設計 □ 創新

　 實驗日期：

　實驗成績：

　 一、

　實驗目的 存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術。本實驗的目的是通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式管理的頁面置換算法。

　二、

　實驗內容 1． 過隨機數產生一個指令序列，共 320 條指令。其地址按下述原則生成：

　①50%的指令是順序執行的； ②25%的指令是均勻分布在前地址部分； ③25%的指令是均勻分布在后地址部分； 具體的實施方法是：

　A. 在[0，319]的指令地址之間隨機選區一起點 M; B. 順序執行一條指令，即執行地址為 M+1 的指令； C. 在前地址[0，M+1]中隨機選取一條指令并執行，該指令的地址為 M’; D. 順序執行一條指令，其地址為 M’+1； E. 在后地址[M’+2，319]中隨機選取一條指令并執行； F. 重復 A—E，直到執行 320 次指令。

　2． 指令序列變換成頁地址流，設：

　（1）

　頁面大小為 1K； （2）

　用戶內存容量為 4 頁到 32 頁； （3）

　用戶虛存容量為 32K。

　在用戶虛存中，按每 K 存放 10 條指令排列虛存地址，即 320 條指令在虛存中的存放方式為：

　第 0 條—第 9 條指令為第 0 頁（對應虛存地址為[0，9]）； 第 10 條—第 19 條指令為第 1 頁（對應虛存地址為[10，19]）； 。。。。。。。。。。。。。。。。。。。。。

　第 310 條—第 319 條指令為第 31 頁（對應虛存地址為[310，319]）； 按以上方式，用戶指令可組成 32 頁。

　3． 計算并輸出下述各種算法在不同內存容量下的命中率。

　A. FIFO 先進先出的算法 B. LRU 最近最少使用算法 C. LFU 最少訪問頁面算法 三、

　實驗要求 1、 需寫出設計說明； 2、 設計實現代碼及說明 3、 運行結果；

　四、

　主要實驗步驟 1、 分析算法結構； 2、 畫出算法的流程圖，即設計說明； 3、 根據畫出的流程圖使用 C 語言編寫相應的代碼（代碼過長，放到最后）； 程序主要由 main 函數和以下幾個函數組成：

　void initialization();初始化內存數據 void FIFO();FIFO 先進先出算法； void LRU();LRU 最久未使用算法； void LFU();LFU 最近最久未使用算法； 4、 檢查代碼，將編出的代碼編譯、鏈接，驗證其正確性。

　開始按要求產生 320個隨機數將隨機數轉換成頁面用戶內存容量i i= =4 4i i> > 32? ?FIFO 頁面置換算法LRU 頁面置換算法LFU 頁面置換算法i i= =i i+ +1 1結束N NY Y 頁面置換算法整體結構

　開始內存數據初始化 ， 物理塊0 0< <m m< <i i 中頁面停留時間time[ [m m ]=m m+ +1 1n n= =0 0用戶內存中是否已存在要調用的頁面用戶內存中是否存在空物理塊N N將頁面調入空物理塊中 ， 該物理塊time[ [m m ]=0 0比較所有物理塊的time[ [m m] ] ， 找到最大值 ，將頁面調入最大值所在物理塊 ， 該物理塊time[ [m m ]=0 0所有已經存入頁面的內存 time[ [m m ]++ ，n n ++N NY YY Yn n> > 320? ?結束將頁面p p[ [n n] ] 調入內存Y YN N FIFO 頁面置換算法

　開始內存數據初始化 ， 物理塊0 0< <m m< <i i 中頁面停留時間time[ [m m ]=m m+ +1 1n n= =0 0用戶內存中是否已存在要調用的頁面用戶內存中是否存在空物理塊N N將頁面調入空物理塊中 ， 該物理塊time[ [m m ]=0 0比較所有物理塊的time[ [m m] ] ， 找到最大值 ，將頁面調入最大值所在物理塊 ， 該物理塊time[ [m m ]=0 0所有已經存入頁面的內存 time[ [m m ]++ ，n n ++N NY YY Yn n> > 320? ?結束將頁面p p[ [n n] ] 調入內存Y YN N存在該頁面的物理塊timg[ [m m ]=0 0 LRU 頁面置換算法

　開始內存數據初始化 ， 物理塊0 0< <m m< <i i 中頁面停留時間time[ [m m ]=m m+ +1 1n n= =0 0n n> > 50? ?將頁面p p[ [n n] ] 調入內存比較物理塊中頁面在之前的 50 次調用中出現的次數 ， 將頁面p p[ [n n] ] 調入使用最少的頁面占用的物理塊n n> > 320? ?結束按照 LRU 頁面置換算法調入頁面n n ++Y YN NY YN N LFU 頁面置換算法

　五、

　實驗數據及處理結果

　六、

　實驗體會或對改進實驗的建議 我做實驗的時候，主要的難度是在幾個特殊情況的處理上，如 LRU 內存中的頁面都是之前沒有調用過的，那怎么辦，還有就是 LFU 中還沒有達到“一定時間間隔”的條件時怎么辦？另外就是由于實驗使用的是系統產生的隨機數，所以難以驗證實驗結果的正確性。

　實驗產生隨機指令的方法是：

　1、 在[0，319]的指令地址之間隨機選區一起點 M; 2、 順序執行一條指令，即執行地址為 M+1 的指令； 3、 在前地址[0，M+1]中隨機選取一條指令并執行，該指令的地址為 M’; 4、 順序執行一條指令，其地址為 M’+1； 5、 在后地址[M’+2，319]中隨機選取一條指令并執行； 6、 重復 A—E，直到執行 320 次指令。

　那么，產生的第一個隨機起點 M 指令是否執行？這對結果影響比較大，若起點 M 執行，那么命中率至少能提高 0.2 以上！

　七、

　參考資料 《計算機操作系統》 《計算機操作系統實驗指導書》 《C 程序設計》 《C 語言程序設計_現代方法》 《計算機操作系統教程習題解答與實驗指導(第二版)》 八、

　實驗代碼 #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 320 #define M 32 #define R 32 #define runtime 100 //程序運行次數，保證結果的準確性 int run; float average[3][32]; //取平均數，使結果更加準確 int s,i; //s表示產生的隨機數，i表示物理塊數 int m,n,h; //循環專用 int k,g,f; int sum; //缺頁次數 float r; //rate命中率 int p[N]; //page頁數 int a[N]; //執行的指令 int pb[M]; //physical block用戶內存容量（物理塊）

　void FIFO(); void LRU(); void LFU(); void line(); void start(); void end(); void main() {

　start();

　srand((int) time (NULL)); //以計算機當前時間作為隨機數種子

　for (run=0;run<runtime;run++) //共產生“runtime”次隨機數，保證結果的準確性

　{

　 for (n=0;n<N;n+=3)

　 {

　s=rand()%N+0; //隨機產生一條指令

　a[n]=s+1; //順序執行一條指令

　 s=rand()%(a[n]+1); //執行前地址指令M`

　a[n+1]=s+1;

　s=rand()%(N-a[n+1]-1)+(a[n+1]+1);

　a[n+2]=s;

　 }

　 for (n=0;n<N;n++)

　p[n]=a[n]/10; //得到指令相對的頁數

　 for (i=4;i<=32;i++)

　 {

　FIFO();

　LRU();

　LFU();

　 }

　}

　printf("物理塊數\t FIFO\t\t LRU\t\t LFU\n");

　line();

　for (i=4;i<=32;i++)

　{

　 printf("\n

　%2d：",i);

　 for (m=0;m<3;m++)

　printf("\t\t%6.4f",average[m][i]); //輸出“runtime”次運行后的平均數

　}

　end(); } void initialization() //用戶內存及相關數據初始化 {

　for (n=0;n<M;n++)

　 pb[n]=-1;

　sum=0;

　r=0;

　k=0;

　g=-1;

　f=-1; }

　void FIFO() //先進先出置換算法 {

　int time[M]; //定義進入內存時間長度數組

　int max; //max表示進入內存時間最久的，即最先進去的

　initialization();

　for(m=0;m<i;m++)

　 time[m]=m+1;

　for (n=0;n<N;n++)

　{

　k=0;

　 for (m=0;m<i;m++)

　if (pb[m]==p[n]) //表示內存中已有當前要調入的頁面

　{

　 g=m;

　 break;

　}

　 for (m=0;m<i;m++)

　if (pb[m]==-1) //用戶內存中存在空的物理塊

　{

　 f=m;

　 break;

　}

　 if (g!=-1)

　g=-1;

　 else

　 {

　if (f==-1) //找到最先進入內存的頁面

　{

　 max=time[0];

　 for(m=0;m<i;m++)

　if(time[m]>max)

　{

　 max=time[m];

　 k=m;

　}

　 pb[k]=p[n];

　 time[k]=0; //該物理塊中頁面停留時間置零

　 sum++; //缺頁數+1

　}

　else

　{

　 pb[f]=p[n];

　 time[f]=0;

　 sum++;

　 f=-1;

　}

　 }

　 for (m=0;m<i && pb[m]!=-1;m++)

　time[m]++; //物理塊中現有頁面停留時間+1

　 /*if (n==0 && i==6)

　printf("\n");

　 if (i==6 && n<=30)

　 {

　 printf("%d......",p[n]);

　for (m=0;m<i;m++)

　 printf("%d ",pb[m]);

　printf("\n");

　 }*/

　}

　r=1-(float)sum/N;

　average[0][i]+=r/runtime; }

　void LRU() //最近最少使用算法 {

　int time[M];

　int max;

　initialization();

　for (m=0;m<i;m++)

　 time[m]=m+1;

　for (n=0;n<N;n++)

　{

　 k=0;

　 for (m=0;m<i;m++)

　if (pb[m]==p[n])

　{

　 g=m;

　 break;

　}

　 for (m=0;m<i;m++)

　if (pb[m]==-1)

　{

　 f=m;

　 break;

　}

　 if (g!=-1)

　 {

　time[g]=0;

　g=-1;

　 }

　 else

　 {

　if (f==-1)

　{

　 max=time[0];

　 for (m=0;m<i;m++)

　if (time[m]>max)

　 {

　 k=m;

　 max=time[m];

　}

　pb[k]=p[n];

　time[k]=0;

　sum++;

　}

　else

　{

　 pb[f]=p[n];

　 time[f]=0;

　 sum++;

　 f=-1;

　}

　 }

　 for (m=0;m<i && pb[m]!=-1;m++)

　time[m]++;

　}

　r=1-(float)sum/N;

　average[1][i]+=r/runtime; }

　void LFU() //最少訪問頁面算法 {

　initialization();

　int time_lru[M],time[M],min,max_lru,t;

　for (m=0;m<i;m++)

　{

　 time[m]=0;

　 time_lru[m]=m+1;

　}

　for (n=0;n<N;n++)

　{

　 k=0;

　 t=1;

　 for (m=0;m<i;m++)

　if (pb[m]==p[n])

　{

　 g=m;

　 break;

　}

　 for (m=0;m<i;m++)

　if (pb[m]==-1)

　 {

　 f=m;

　 break;

　}

　 if (g!=-1)

　 {

　time_lru[g]=0;

　g=-1;

　 }

　 else

　 {

　if (f==-1)

　{

　 if (n<=R) //將最少使用的間隔時間定位為R個單位

　 {

　max_lru=time_lru[0]; //在未達到“一定時間”的要求時，先采用LRU進行頁面置換

　for (m=0;m<i;m++)

　 if (time_lru[m]>max_lru)

　 {

　k=m;

　max_lru=time_lru[m];

　 }

　 pb[k]=p[n];

　 time_lru[k]=0;

　 sum++;

　 }

　 else

　 {

　for (m=0;m<i;m++) //計算一定時間間隔內物理塊中的頁面使用次數

　 for (h=n-1;h>=n-R-1;h--)

　if (pb[m]==p[h])

　 time[m]++;

　min=time[0];

　for (m=0;m<i;m++)

　 if (time[m]<min)

　 {

　min=time[m];

　k=m;

　 }

　for (m=0;m<i;m++) //應對出現頁面使用次數同樣少的情況

　 if (time[m]==min)

　t++;

　 if (t>1) //若使用次數同樣少，將次數相同的頁面按照LRU進行頁面置換

　{

　 max_lru=time_lru[k];

　 for (m=0;m<i && time[m]==min;m++)

　if (time_lru[m]>max_lru)

　{

　 k=m;

　 max_lru=time_lru[m];

　}

　}

　pb[k]=p[n];

　time_lru[k]=0;

　sum++;

　 }

　}

　else

　{

　 pb[f]=p[n];

　 time_lru[f]=0;

　 sum++;

　 f=-1;

　}

　 }

　 for (m=0;m<i && pb[m]!=-1;m++)

　time_lru[m]++;

　}

　r=1-(float)sum/N;

　average[2][i]+=r/runtime; } void line()

　 //美化程序，使程序運行時更加明朗美觀 {

　printf("------------------------------------------------------------------"); } void start()

　 //表示算法開始 {

　line();

　printf("\n

　 頁面置換算法開始\n");

　printf("

　 ——Designed by Zhang Hong\n");

　line();

　printf("\n\n"); } void end()

　 //表示算法結束 {

　 printf("\n");

　line();

　printf("\n

　 頁面置換算法結束,謝謝使用\n");

　line(); }

推薦訪問： 操作系統 實驗 報告