操作系統(tǒng)實驗答案

1、部分實驗答案第三部分 操作系統(tǒng)實驗指導(dǎo)實驗3 指導(dǎo)實驗內(nèi)容1 進(jìn)程的創(chuàng)建任務(wù)編寫一段程序，使用系統(tǒng)調(diào)用fork( )創(chuàng)建兩個子進(jìn)程。當(dāng)此程序運行時，在系統(tǒng)中有一個父進(jìn)程和兩個子進(jìn)程活動。讓每一個進(jìn)程在屏幕上顯示一個字符；父進(jìn)程顯示字符“a”，子進(jìn)程分別顯示字符“b”和“c”。試觀察記錄屏幕上的顯示結(jié)果，并分析原因。程序#includemain()int p1,p2;if(p1=fork() /*子進(jìn)程創(chuàng)建成功*/ putchar(b);else if(p2=fork() /*子進(jìn)程創(chuàng)建成功*/ putchar(c); else putchar(a); /*父進(jìn)程執(zhí)行*/bca(有時會出現(xiàn)abc

2、的任意的排列)分析：從進(jìn)程執(zhí)行并發(fā)來看，輸出abc的排列都是有可能的。原因：fork()創(chuàng)建進(jìn)程所需的時間雖然可能多于輸出一個字符的時間，但各個進(jìn)程的時間片的獲得卻不是一定是順序的，所以輸出abc的排列都是有可能的。2 進(jìn)程的控制 修改已編寫好的程序，將每個程序的輸出由單個字符改為一句話，再觀察程序執(zhí)行時屏幕上出現(xiàn)的現(xiàn)象，并分析其原因。如果在程序中使用系統(tǒng)調(diào)用lockf()來給每個程序加鎖，可以實現(xiàn)進(jìn)程之間的互斥，觀察并分析出現(xiàn)的現(xiàn)象。程序1#includemain()int p1,p2,i;if(p1=fork() for(i=0;i500;i+) printf(parent%dn,i);

3、wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/exit(0);else if(p2=fork() for(i=0;i500;i+) printf(son %dn,i); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/ exit(0); /*向父進(jìn)程信號0且該進(jìn)程推出*/ else for(i=0;i500;i+) printf(“grandchild %dn,i); exit(0);運行結(jié)果parent.songrandchildgrandchild或grandchildsongrandchildsonparent分析：由于函數(shù)printf()輸出的字符串之間不

4、會被中斷，因此,每個字符串內(nèi)部的字符順序輸出時不變。但是 , 由于進(jìn)程并發(fā)執(zhí)行時的調(diào)度順序和父子進(jìn)程的搶占處理機(jī)問題，輸出字符串的順序和先后隨著執(zhí)行的不同而發(fā)生變化。這與打印單字符的結(jié)果相同。程序2#includemain()int p1,p2,i;if(p1=fork() lockf(1,1,0); for(i=0;i500;i+) printf(parent %dn,i); lockf(1,0,0); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/ exit(0);else if(p2=fork() lockf(1,1,0); for(i=0;i500;i+) printf

5、(son %dn,i); lockf(1,0,0); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/exit(0); else lockf(1,1,0); for(i=0;i500;i+) printf(daughter %dn,i); lockf(1,0,0); exit(0); 運行結(jié)果輸出parent塊,son塊,grandchild塊的順序可能不同，但是每個塊的輸出過程不會被打斷。分析：因為上述程序執(zhí)行時，lockf(1,1,0)鎖定標(biāo)準(zhǔn)輸出設(shè)備，lockf(1,0,0)解鎖標(biāo)準(zhǔn)輸出設(shè)備，在lockf(1,1,0)與lockf(1,0,0)中間的for循環(huán)輸出不會被中斷

6、，加鎖與不加鎖效果不相同。3軟中斷通信任務(wù)1編制一段程序，使用系統(tǒng)調(diào)用fork()創(chuàng)建兩個子進(jìn)程，再用系統(tǒng)調(diào)用signal()讓父進(jìn)程捕捉鍵盤上來的中斷信號（即按ctrl+c鍵），當(dāng)捕捉到中斷信號后，父進(jìn)程用系統(tǒng)調(diào)用kill()向兩個子進(jìn)程發(fā)出信號，子進(jìn)程捕捉到信號后，分別輸出下列信息后終止：child process1 is killed by parent!child process2 is killed by parent!父進(jìn)程等待兩個子進(jìn)程終止后，輸出以下信息后終止：parent process is killed! 程序#include#include#include void w

7、aiting(),stop(),alarming();int wait_mark;main()int p1,p2;if(p1=fork() /*創(chuàng)建子進(jìn)程p1*/if(p2=fork() /*創(chuàng)建子進(jìn)程p2*/wait_mark=1;signal(SIGINT,stop); /*接收到c信號，轉(zhuǎn)stop*/signal(SIGALRM,alarming);/*接受SIGALRMwaiting();kill(p1,16); /*向p1發(fā)軟中斷信號16*/ kill(p2,17); /*向p2發(fā)軟中斷信號17*/ wait(0); /*同步*/wait(0);printf(parent proce

8、ss is killed!n);exit(0); else wait_mark=1;signal(17,stop);signal(SIGINT,SIG_IGN); /*忽略 c信號*/while (wait_mark!=0);lockf(1,1,0);printf(child process2 is killed by parent!n);lockf(1,0,0);exit(0);elsewait_mark=1;signal(16,stop);signal(SIGINT,SIG_IGN); /*忽略c信號*/while (wait_mark!=0)lockf(1,1,0);printf(chi

9、ld process1 is killed by parent!n);lockf(1,0,0);exit(0);void waiting()sleep(5);if (wait_mark!=0) kill(getpid(),SIGALRM);void alarming()wait_mark=0;void stop()wait_mark=0; 不做任何操作等待五秒鐘父進(jìn)程回在子進(jìn)程縣推出后退出，并打印退出的順序；或者點擊ctrl+C后程序退出并打印退出的順序。任務(wù)2在上面的任務(wù)1中，增加語句signal(SIGINT,SIG_IGN)和語句signal(SIGQUIT,SIG_IGN)，觀察執(zhí)行結(jié)

10、果，并分析原因。這里，signal(SIGINT,SIG_IGN)和signal(SIGQUIT,SIG_IGN)分別為忽略鍵信號以及忽略中斷信號。#include#include#includeint pid1,pid2;int EndFlag=0;int pf1=0;int pf2=0;void IntDelete()kill(pid1,16);kill(pid2,17);void Int1()printf(child process 1 is killed !by parentn);exit(0);void Int2()printf(child process 2 is killed !

11、by parentn);exit(0);main()int exitpid;if(pid1=fork() if(pid2=fork() signal(SIGINT,IntDelete);waitpid(-1,&exitpid,0);waitpid(-1,&exitpid,0);printf(parent process is killedn);exit(0); else signal(SIGINT,SIG_IGN);signal(17,Int2);pause(); elsesignal(SIGINT,SIG_IGN);signal(16,Int1);pause();運行結(jié)果請讀者將上述程序輸入

12、計算機(jī)后，執(zhí)行并觀察。3 進(jìn)程的管道通信任務(wù) 編制一段程序，實現(xiàn)進(jìn)程的管道通信。使用系統(tǒng)調(diào)用pipe()建立一條管道線。兩個子進(jìn)程p1和p2分別向通道個寫一句話： child1 process is sending message!child2 process is sending message!而父進(jìn)程則從管道中讀出來自兩個進(jìn)程的信息，顯示在屏幕上。程序#include #include #include int pid1,pid2; main( ) int fd2;char outpipe100,inpipe100;pipe(fd); /*創(chuàng)建一個管道*/while (pid1=fork

13、( )=-1);if(pid1=0) lockf(fd1,1,0); sprintf(outpipe,child 1 process is sending message!); /*把串放入數(shù)組outpipe中*/ write(fd1,outpipe,50); /*向管道寫長為50字節(jié)的串*/ sleep(5); /*自我阻塞5秒*/ lockf(fd1,0,0); exit(0); else while(pid2=fork( )=-1); if(pid2=0) lockf(fd1,1,0); /*互斥*/ sprintf(outpipe,child 2 process is sending

14、message!); write(fd1,outpipe,50); sleep(5); lockf(fd1,0,0); exit(0); else wait(0); /*同步*/ read(fd0,inpipe,50); /*從管道中讀長為50字節(jié)的串*/ printf(%sn,inpipe); wait(0); read(fd0,inpipe,50); printf(%sn,inpipe); exit(0); 運行結(jié)果延遲5秒后顯示:child1 process is sending message! 再延遲5秒:child2 process is sending message!分析請讀者

15、自行完成 。 1、程序中的sleep(5)起什么作用？2、子進(jìn)程1和2為什么也能對管道進(jìn)行操作？實驗4指導(dǎo)實驗內(nèi)容1 消息的創(chuàng)建，發(fā)送和接收 任務(wù) 使用系統(tǒng)調(diào)用msgget( ), megsnd( ), msgrev( )及msgctl()編制一長度為1K的消息發(fā)送和接收的程序 。程序設(shè)計（1） 為了便于操作和觀察結(jié)果，用一個 程序為“引子”，先后fork( )兩個子進(jìn)程，SERVER和CLIENT，進(jìn)行通信。（2） SERVER端建立一個Key為75的消息隊列，等待其他進(jìn)程發(fā)來的消息。當(dāng)遇到類型為1的消息，則作為結(jié)束信號，取消該隊列，并退出SERVER 。SERVER每接收到一個消息后顯示一

16、句“(server)received”。（3） CLIENT端使用Key為75的消息隊列，先后發(fā)送類型從10到1的消息，然后退出。最后的一個消息，既是 SERVER端需要的結(jié)束信號。CLIENT每發(fā)送一條消息后顯示一句“(client)sent”。（4） 父進(jìn)程在 SERVER和 CLIENT均退出后結(jié)束。程序#include #include #include #include #define MSGKEY 75 /*定義關(guān)鍵詞MEGKEY*/struct msgform /*消息結(jié)構(gòu)*/long mtype;char mtexe100; /*文本長度*/msg;int msgqid,i;v

17、oid CLIENT( )int i;msgqid=msgget(MSGKEY,0777|IPC_CREAT);for(i=10;i=1;i-) msg.mtype=i; printf(client)sentn); msgsnd(msgqid,&msg,1030,0); /*發(fā)送消息msg入msgid消息隊列*/exit(0);void SERVER( ) msgqid=msgget(MSGKEY,0777|IPC_CREAT); /*由關(guān)鍵字獲得消息隊列*/ do msgrcv(msgqid,&msg,1030,0,0); /*從隊列msgid接受消息msg*/ printf(server)

18、receiven); while(msg.mtype!=1); /*消息類型為1時，釋放隊列*/ msgctl(msgqid, IPC_RMID,0);main() if(fork() SERVER(); wait(0);else CLIENT( );從理想的結(jié)果來說，應(yīng)當(dāng)是每當(dāng)Client發(fā)送一個消息后，server接收該消息，Client再發(fā)送下一條。也就是說“(Client)sent”和“(server)received”的字樣應(yīng)該在屏幕上交替出現(xiàn)。實際的結(jié)果大多是，先由 Client 發(fā)送兩條消息，然后Server接收一條消息。此后Client Server交替發(fā)送和接收消息.最后一次

19、接收兩條消息. Client 和Server 分別發(fā)送和接收了10條消息,與預(yù)期設(shè)想一致 message的傳送和控制并不保證完全同步,當(dāng)一個程序不再激活狀態(tài)的時候,它完全可能繼續(xù)睡眠,造成上面現(xiàn)象,在多次send message 后才 receive message.這一點有助于理解消息轉(zhuǎn)送的實現(xiàn)機(jī)理.2.共享存儲區(qū)的創(chuàng)建,附接和斷接 使用系統(tǒng)調(diào)用shmget(),sgmat(),smgdt(),shmctl()編制一個與上述功能相同的程序. (1)為了便于操作 和觀察結(jié)果，用一個 程序為“引子”，先后fork( )兩個子進(jìn)程，SERVER 和 CLIENT，進(jìn)行通信。 (2)SERVER端建

20、立一個KEY為75的共享區(qū),并將第一個字節(jié)置為-1.作為數(shù)據(jù)空的標(biāo)志.等待其他進(jìn)程發(fā)來的消息.當(dāng)該字節(jié)的值發(fā)生變化時,表示收到了該消息,進(jìn)行處理.然后再次把它的值設(shè)為-1.如果遇到的值為0,則視為結(jié)束信號,取消該隊列,并退出SERVER.SERVER每接收到一次數(shù)據(jù)后顯示”(server)received”. (3)CLIENT端建立一個為75的共享區(qū),當(dāng)共享取得第一個字節(jié)為-1時, Server端空閑,可發(fā)送請求. CLIENT 隨即填入9到0.期間等待Server端再次空閑.進(jìn)行完這些操作后, CLIENT 退出. CLIENT每發(fā)送一次數(shù)據(jù)后顯示”(client)sent”. (4)父進(jìn)

21、程在SERVER和CLIENT均退出后結(jié)束.#include#include#include#define SHMKEY 75 /*定義共享區(qū)關(guān)鍵詞*/int shmid,i;int *addr; CLIENT()int i;shmid=shmget(SHMKEY,1024, 0777|IPC_CREAT); /*獲取共享區(qū)，長度1024，關(guān)鍵詞SHMKEY*/addr=shmat(shmid,0,0); /*共享區(qū)起始地址為addr*/for(i=9;i=0;i-) while(*addr!= -1); printf(client)sentn); /*打?。╟lient）sent*/*add

22、r=i; /*把i賦給addr*/exit(0); SERVER() dowhile(*addr = =-1);printf(server)receivedn%d,*addr); /*服務(wù)進(jìn)程使用共享區(qū)*/if(*addr!=0)*addr=-1; while(*addr); wait(0);shmctl(shmid,IPC_RMID,0); main()shmid=shmget(SHMKEY,1024,0777|IPC_CREAT); /*創(chuàng)建共享區(qū)*/addr=shmat(shmid,0,0); /*共享區(qū)起始地址為addr*/*addr=-1;if(fork() SERVER();els

23、e CLIENT(); 結(jié)果 運行的結(jié)果和預(yù)想的完全一樣。但在運行的過程中，發(fā)現(xiàn)每當(dāng)client發(fā)送一次數(shù)據(jù)后，server要等大約0.1秒才有響應(yīng)。同樣，之后client又需要等待大約0.1秒才發(fā)送下一個數(shù)據(jù)。分析出現(xiàn)上述的應(yīng)答延遲的現(xiàn)象是程序設(shè)計的問題。當(dāng)client端發(fā)送了數(shù)據(jù)后，并沒有任何措施通知server端數(shù)據(jù)已經(jīng)發(fā)出，需要由client的查詢才能感知。此時，client端并沒有放棄系統(tǒng)的控制權(quán)，仍然占用CPU的時間片。只有當(dāng)系統(tǒng)進(jìn)行調(diào)度時，切換到了server進(jìn)程，再進(jìn)行應(yīng)答。這個問題，也同樣存在于server端到client的應(yīng)答過程之中。3 比較兩種消息通信機(jī)制中的數(shù)據(jù)傳輸?shù)?/p>

24、時間 由于兩種機(jī)制實現(xiàn)的機(jī)理和用處都不一樣，難以直接進(jìn)行時間上的比較。如果比較其性能，應(yīng)更加全面的分析。(1) 消息隊列的建立比共享區(qū)的設(shè)立消耗的資源少.前者只是一個軟件上設(shè)定的問題,后者需要對硬件操作,實現(xiàn)內(nèi)存的映像,當(dāng)然控制起來比前者復(fù)雜.如果每次都重新進(jìn)行隊列或共享的建立,共享區(qū)的設(shè)立沒有什么優(yōu)勢。(2) 當(dāng)消息隊列和共享區(qū)建立好后,共享區(qū)的數(shù)據(jù)傳輸,受到了系統(tǒng)硬件的支持,不耗費多余的資源;而消息傳遞,由軟件進(jìn)行控制和實現(xiàn),需要消耗一定的CPU資源.從這個意義上講,共享區(qū)更適合頻繁和大量的數(shù)據(jù)傳輸.(3) 消息的傳遞,自身就帶有同步的控制.當(dāng)?shù)鹊较⒌臅r候,進(jìn)程進(jìn)入睡眠狀態(tài),不再消耗CP

25、U資源.而共享隊列如果不借助其他機(jī)制進(jìn)行同步,接受數(shù)據(jù)的一方必須進(jìn)行不斷的查詢,白白浪費了大量的CPU資源.可見消息方式的使用更加靈活.實驗5指導(dǎo)實驗內(nèi)容設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū),并使用下列算法計算訪問命中率.（1） 進(jìn)先出的算法（FIFO）（2） 最近最少使用的算法（LRU）（3） 最佳淘汰算法(OPT)（4） 最少訪問頁面算法(LFU)（5） 最近最不經(jīng)常使用算法(NUR)命中率=(1-頁面失效次數(shù))/頁地址流長度程序設(shè)計本實驗的程序設(shè)計基本上按照實驗內(nèi)容進(jìn)行。即首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的

26、命中率。相關(guān)定義如下：1 數(shù)據(jù)結(jié)構(gòu)(1)頁面類型 typedef struct int pn,pfn,counter,time; pl-type;其中pn 為頁號,pfn為面號, counter為一個周期內(nèi)訪問該頁面的次數(shù), time為訪問時間.(2) 頁面控制結(jié)構(gòu)pfc-struct int pn,pfn; struct pfc_struct *next; typedef struct pfc_struct pfc_type;pfc_type pfc_structtotal_vp,*freepf_head,*busypf_head;pfc_type *busypf_tail; 其中pfcto

27、tal_vp定義用戶進(jìn)程虛頁控制結(jié)構(gòu),*freepf_head為空頁面頭的指針,*busypf_head為忙頁面頭的指針,*busypf_tail為忙頁面尾的指針.2函數(shù)定義（1）Void initialize( ):初始化函數(shù),給每個相關(guān)的頁面賦值.（2）Void FIFO( ):計算使用FIFO算法時的命中率.（3）Void LRU( ):計算使用LRU算法時的命中率.（4）Void OPT( ):計算使用OPT算法時的命中率.（5）Void LFU( ):計算使用LFU算法時的命中率.（6）Void NUR( ):計算使用NUR算法時的命中率.3.變量定義(1)int atotal_in

28、struction: 指令流數(shù)據(jù)組.(2)int pagetotal_instruction: 每條指令所屬的頁號.(3)int offsettotal_instruction: 每頁裝入10條指令后取模運算頁號偏移值.(4)int total_pf: 用戶進(jìn)程的內(nèi)存頁面數(shù).(5)int disaffect: 頁面失效次數(shù).4.程序參考源碼及結(jié)果#define TRUE 1#define FALSE 0#define INVALID -1#define NULL 0#define total_instruction 320 /*指令流長*/#define total_vp 32 /*虛頁長*/

29、#define clear_period 50 /*清0周期*/typedef struct /*頁面結(jié)構(gòu)*/int pn; /頁號 logic numberint pfn; /頁面框架號 physical frame numberint counter; /計數(shù)器int time; /時間pl_type;pl_type pltotal_vp; /*頁面線性結(jié)構(gòu)-指令序列需要使用地址*/typedef struct pfc_struct /*頁面控制結(jié)構(gòu)，調(diào)度算法的控制結(jié)構(gòu)*/ int pn;int pfn;struct pfc_struct *next;pfc_type;pfc_type p

30、fctotal_vp, *freepf_head, *busypf_head, *busypf_tail;int diseffect, atotal_instruction; /* a為指令序列*/int pagetotal_instruction, offsettotal_instruction;/*地址信息*/int initialize(int);int FIFO(int);int LRU(int);int LFU(int);int NUR(int); /not use recentlyint OPT(int);int main( )int s,i,j;srand(10*getpid()

31、; /*由于每次運行時進(jìn)程號不同，故可用來作為初始化隨機(jī)數(shù)隊列的“種子”*/s=(float)319*rand( )/32767/32767/2+1; /*正態(tài)分布*/for(i=0;itotal_instruction;i+=4) /*產(chǎn)生指令隊列*/if(s319)printf(When i=%d,Error,s=%dn,i,s);exit(0); ai=s; /*任選一指令訪問點m*/ai+1=ai+1; /*順序執(zhí)行一條指令*/ai+2=(float)ai*rand( )/32767/32767/2; /*執(zhí)行前地址指令m*/ai+3=ai+2+1; /*順序執(zhí)行一條指令*/s=(fl

32、oat)(318-ai+2)*rand( )/32767/32767/2+ai+2+2;if(ai+2318)|(s319)printf(a%d+2,a number which is :%d and s=%dn,i,ai+2,s);for (i=0;itotal_instruction;i+) /*將指令序列變換成頁地址流*/pagei=ai/10;offseti=ai%10;for(i=4;i=32;i+) /*用戶內(nèi)存工作區(qū)從4個頁面到32個頁面*/printf(-%2d page frames-n,i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);retur

33、n 0;/*初始化相關(guān)數(shù)據(jù)結(jié)構(gòu) total_pf表示內(nèi)存的塊數(shù) */int initialize(int total_pf) int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pfn=INVALID; /*置頁面控制結(jié)構(gòu)中的頁號，頁面為空*/pli.counter=0; /*頁面控制結(jié)構(gòu)中的訪問次數(shù)為0*/pli.time=-1; /*訪問的時間*/for(i=0;itotal_pf-1;i+)/*建立pfci-1和pfci之間的鏈接*/pfci.next=&pfci+1;pfci.pfn=i; pfctotal_pf-1.next=NULL;pfctota

34、l_pf-1.pfn=total_pf-1;freepf_head=&pfc0; /*空頁面隊列的頭指針為pfc0*/return 0;int FIFO(int total_pf) /*先進(jìn)先出算法total_pf:用戶進(jìn)程的內(nèi)存頁面數(shù)*/int i,j;pfc_type *p;/*中間變量*/initialize(total_pf); /*初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)*/busypf_head=busypf_tail=NULL; /*忙頁面隊列頭，隊列尾鏈接*/for(i=0;inext; plbusypf_head-pn.pfn=INVALID;freepf_head=busypf_hea

35、d; /*釋放忙頁面隊列的第一個頁面*/freepf_head-next=NULL; /*表明還是缺頁*/busypf_head=p;p=freepf_head-next; freepf_head-pn=pagei;plpagei.pfn=freepf_head-pfn;freepf_head-next=NULL; /*使busy的尾為null*/if(busypf_tail=NULL)busypf_tail=busypf_head=freepf_head;elsebusypf_tail-next=freepf_head;busypf_tail=freepf_head;freepf_head=

36、p;printf(FIFO:%6.4fn,1-(float)diseffect/320);return 0;int LRU (int total_pf) /*最近最久未使用算法least recently used*/int min,minj,i,j,present_time; /*minj為最小值下標(biāo)*/initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /*頁面失效*/diseffect+;if(freepf_head=NULL) /*無空閑頁面*/min=327

37、67;/*設(shè)置最大值*/for(j=0;jplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; /騰出一個單元plminj.pfn=INVALID;plminj.time=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空閑頁面,改為有效plpagei.time=present_time;freepf_head=freepf_head-next; /減少一個free 頁面elseplpagei.time=present_time; /命中則

38、增加該單元的訪問次數(shù)present_time+;printf(LRU:%6.4fn,1-(float)diseffect/320);return 0;int NUR(int total_pf ) /*最近未使用算法Not Used recently count表示*/ int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i+) if (plpagei.pfn=INVALID) /*頁面失效*/diseffect+;if(freepf_head=NULL) /*無

39、空閑頁面*/ cont_flag=TRUE;old_dp=dp;while(cont_flag) if(pldp.counter=0&pldp.pfn!=INVALID)cont_flag=FALSE;elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;jnext=NULL;plpagei.pfn=freepf_head-pfn;freepf_head-pn=pagei;freepf_head=freepf_head-next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;jtotal_vp;j

40、+)plj.counter=0;printf(NUR:%6.4fn,1-(float)diseffect/320);return 0;int OPT(int total_pf) /*最佳置換算法*/int i,j, max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) /*頁面失效*/diseffect+;if(freepf_head=NULL) /*無空閑頁面*/for(j=0;jtotal_vp;j+)if(plj.

41、pfn!=INVALID)distj=32767;elsedistj=0; for(j=0;jtotal_vp;j+) if(plj.pfn!=INVALID)&(distj=32767)distj=j;max=0;for(j=0;jtotal_vp;j+)if(maxnext=NULL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;printf(OPT:%6.4fn,1-(float)diseffect/320);return 0;/*該算法時根據(jù)已知的預(yù)測未知的，least fr

42、equency Used是最不經(jīng)常使用置換法*/int LFU(int total_pf) int i,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) /*頁面失效*/ diseffect+;if(freepf_head=NULL) /*無空閑頁面*/ min=32767;/*獲取counter的使用用頻率最小的內(nèi)存*/for(j=0;jplj.counter&plj.pfn!=INVALID)min=plj.counter;minpage

43、=j;freepf_head=&pfcplminpage.pfn;plminpage.pfn=INVALID;plminpage.counter=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空閑頁面,改為有效plpagei.counter+;freepf_head=freepf_head-next; /減少一個free 頁面elseplpagei.counter;plpagei.counter=plpagei.counter+1;printf(LFU:%6.4fn,1-(float)diseffect/320);return 0

44、;結(jié)果一：4 page framesFIFO:0.2562LRU:0.2531OPT:0.3031LFU:0.2812NUR:0.2812 5 page framesFIFO:0.2969LRU:0.2906OPT:0.3500LFU:0.3219NUR:0.3094 6 page framesFIFO:0.3375LRU:0.3281OPT:0.3844LFU:0.3375NUR:0.3344 7 page framesFIFO:0.3563LRU:0.3563OPT:0.4031LFU:0.3563NUR:0.3500 8 page framesFIFO:0.3937LRU:0.3750OPT:0.4531LFU:0.3937NUR:0.3719