操作系統(tǒng)實(shí)驗(yàn)答案.doc

部分實(shí)驗(yàn)答案第三部分 操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)3 指導(dǎo)實(shí)驗(yàn)內(nèi)容1 進(jìn)程的創(chuàng)建任務(wù)編寫一段程序，使用系統(tǒng)調(diào)用fork( )創(chuàng)建兩個(gè)子進(jìn)程。當(dāng)此程序運(yùn)行時(shí)，在系統(tǒng)中有一個(gè)父進(jìn)程和兩個(gè)子進(jìn)程活動(dòng)。讓每一個(gè)進(jìn)程在屏幕上顯示一個(gè)字符；父進(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(有時(shí)會(huì)出現(xiàn)abc的任意的排列)分析：從進(jìn)程執(zhí)行并發(fā)來(lái)看，輸出abc的排列都是有可能的。原因：fork()創(chuàng)建進(jìn)程所需的時(shí)間雖然可能多于輸出一個(gè)字符的時(shí)間，但各個(gè)進(jìn)程的時(shí)間片的獲得卻不是一定是順序的，所以輸出abc的排列都是有可能的。2 進(jìn)程的控制 修改已編寫好的程序，將每個(gè)程序的輸出由單個(gè)字符改為一句話，再觀察程序執(zhí)行時(shí)屏幕上出現(xiàn)的現(xiàn)象，并分析其原因。如果在程序中使用系統(tǒng)調(diào)用lockf()來(lái)給每個(gè)程序加鎖，可以實(shí)現(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); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會(huì)終止*/exit(0);else if(p2=fork() for(i=0;i500;i+) printf(son %dn,i); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會(huì)終止*/ exit(0); /*向父進(jìn)程信號(hào)0且該進(jìn)程推出*/ else for(i=0;i500;i+) printf(“grandchild %dn,i); exit(0);運(yùn)行結(jié)果parent.songrandchildgrandchild或grandchildsongrandchildsonparent分析：由于函數(shù)printf()輸出的字符串之間不會(huì)被中斷，因此,每個(gè)字符串內(nèi)部的字符順序輸出時(shí)不變。但是 , 由于進(jìn)程并發(fā)執(zhí)行時(shí)的調(diào)度順序和父子進(jìn)程的搶占處理機(jī)問(wèn)題，輸出字符串的順序和先后隨著執(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)程不會(huì)終止*/ exit(0);else if(p2=fork() lockf(1,1,0); for(i=0;i500;i+) printf(son %dn,i); lockf(1,0,0); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會(huì)終止*/exit(0); else lockf(1,1,0); for(i=0;i500;i+) printf(daughter %dn,i); lockf(1,0,0); exit(0); 運(yùn)行結(jié)果輸出parent塊,son塊,grandchild塊的順序可能不同，但是每個(gè)塊的輸出過(guò)程不會(huì)被打斷。分析：因?yàn)樯鲜龀绦驁?zhí)行時(shí)，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)輸出不會(huì)被中斷，加鎖與不加鎖效果不相同。3軟中斷通信任務(wù)1編制一段程序，使用系統(tǒng)調(diào)用fork()創(chuàng)建兩個(gè)子進(jìn)程，再用系統(tǒng)調(diào)用signal()讓父進(jìn)程捕捉鍵盤上來(lái)的中斷信號(hào)（即按ctrl+c鍵），當(dāng)捕捉到中斷信號(hào)后，父進(jìn)程用系統(tǒng)調(diào)用kill()向兩個(gè)子進(jìn)程發(fā)出信號(hào)，子進(jìn)程捕捉到信號(hào)后，分別輸出下列信息后終止：child process1 is killed by parent!child process2 is killed by parent!父進(jìn)程等待兩個(gè)子進(jìn)程終止后，輸出以下信息后終止：parent process is killed! 程序#include#include#include void waiting(),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信號(hào)，轉(zhuǎn)stop*/signal(SIGALRM,alarming);/*接受SIGALRMwaiting();kill(p1,16); /*向p1發(fā)軟中斷信號(hào)16*/ kill(p2,17); /*向p2發(fā)軟中斷信號(hào)17*/ wait(0); /*同步*/wait(0);printf(parent process is killed!n);exit(0); else wait_mark=1;signal(17,stop);signal(SIGINT,SIG_IGN); /*忽略 c信號(hào)*/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信號(hào)*/while (wait_mark!=0)lockf(1,1,0);printf(child 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)程縣推出后退出，并打印退出的順序；或者點(diǎn)擊ctrl+C后程序退出并打印退出的順序。任務(wù)2在上面的任務(wù)1中，增加語(yǔ)句signal(SIGINT,SIG_IGN)和語(yǔ)句signal(SIGQUIT,SIG_IGN)，觀察執(zhí)行結(jié)果，并分析原因。這里，signal(SIGINT,SIG_IGN)和signal(SIGQUIT,SIG_IGN)分別為忽略鍵信號(hào)以及忽略中斷信號(hào)。#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 !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();運(yùn)行結(jié)果請(qǐng)讀者將上述程序輸入計(jì)算機(jī)后，執(zhí)行并觀察。3 進(jìn)程的管道通信任務(wù) 編制一段程序，實(shí)現(xiàn)進(jìn)程的管道通信。使用系統(tǒng)調(diào)用pipe()建立一條管道線。兩個(gè)子進(jìn)程p1和p2分別向通道個(gè)寫一句話： child1 process is sending message!child2 process is sending message!而父進(jìn)程則從管道中讀出來(lái)自兩個(gè)進(jìn)程的信息，顯示在屏幕上。程序#include #include #include int pid1,pid2; main( ) int fd2;char outpipe100,inpipe100;pipe(fd); /*創(chuàng)建一個(gè)管道*/while (pid1=fork( )=-1);if(pid1=0) lockf(fd1,1,0); sprintf(outpipe,child 1 process is sending message!); /*把串放入數(shù)組outpipe中*/ write(fd1,outpipe,50); /*向管道寫長(zhǎng)為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 message!); write(fd1,outpipe,50); sleep(5); lockf(fd1,0,0); exit(0); else wait(0); /*同步*/ read(fd0,inpipe,50); /*從管道中讀長(zhǎng)為50字節(jié)的串*/ printf(%sn,inpipe); wait(0); read(fd0,inpipe,50); printf(%sn,inpipe); exit(0); 運(yùn)行結(jié)果延遲5秒后顯示:child1 process is sending message! 再延遲5秒:child2 process is sending message!分析請(qǐng)讀者自行完成 。 1、程序中的sleep(5)起什么作用？2、子進(jìn)程1和2為什么也能對(duì)管道進(jìn)行操作？實(shí)驗(yàn)4指導(dǎo)實(shí)驗(yàn)內(nèi)容1 消息的創(chuàng)建，發(fā)送和接收 任務(wù) 使用系統(tǒng)調(diào)用msgget( ), megsnd( ), msgrev( )及msgctl()編制一長(zhǎng)度為1K的消息發(fā)送和接收的程序 。程序設(shè)計(jì)（1） 為了便于操作和觀察結(jié)果，用一個(gè) 程序?yàn)椤耙印?，先后fork( )兩個(gè)子進(jìn)程，SERVER和CLIENT，進(jìn)行通信。（2） SERVER端建立一個(gè)Key為75的消息隊(duì)列，等待其他進(jìn)程發(fā)來(lái)的消息。當(dāng)遇到類型為1的消息，則作為結(jié)束信號(hào)，取消該隊(duì)列，并退出SERVER 。SERVER每接收到一個(gè)消息后顯示一句“(server)received”。（3） CLIENT端使用Key為75的消息隊(duì)列，先后發(fā)送類型從10到1的消息，然后退出。最后的一個(gè)消息，既是 SERVER端需要的結(jié)束信號(hào)。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; /*文本長(zhǎng)度*/msg;int msgqid,i;void 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消息隊(duì)列*/exit(0);void SERVER( ) msgqid=msgget(MSGKEY,0777|IPC_CREAT); /*由關(guān)鍵字獲得消息隊(duì)列*/ do msgrcv(msgqid,&msg,1030,0,0); /*從隊(duì)列msgid接受消息msg*/ printf(server)receiven); while(msg.mtype!=1); /*消息類型為1時(shí)，釋放隊(duì)列*/ msgctl(msgqid, IPC_RMID,0);main() if(fork() SERVER(); wait(0);else CLIENT( );從理想的結(jié)果來(lái)說(shuō)，應(yīng)當(dāng)是每當(dāng)Client發(fā)送一個(gè)消息后，server接收該消息，Client再發(fā)送下一條。也就是說(shuō)“(Client)sent”和“(server)received”的字樣應(yīng)該在屏幕上交替出現(xiàn)。實(shí)際的結(jié)果大多是，先由 Client 發(fā)送兩條消息，然后Server接收一條消息。此后Client Server交替發(fā)送和接收消息.最后一次接收兩條消息. Client 和Server 分別發(fā)送和接收了10條消息,與預(yù)期設(shè)想一致 message的傳送和控制并不保證完全同步,當(dāng)一個(gè)程序不再激活狀態(tài)的時(shí)候,它完全可能繼續(xù)睡眠,造成上面現(xiàn)象,在多次send message 后才 receive message.這一點(diǎn)有助于理解消息轉(zhuǎn)送的實(shí)現(xiàn)機(jī)理.2.共享存儲(chǔ)區(qū)的創(chuàng)建,附接和斷接 使用系統(tǒng)調(diào)用shmget(),sgmat(),smgdt(),shmctl()編制一個(gè)與上述功能相同的程序. (1)為了便于操作 和觀察結(jié)果，用一個(gè) 程序?yàn)椤耙印?，先后fork( )兩個(gè)子進(jìn)程，SERVER 和 CLIENT，進(jìn)行通信。 (2)SERVER端建立一個(gè)KEY為75的共享區(qū),并將第一個(gè)字節(jié)置為-1.作為數(shù)據(jù)空的標(biāo)志.等待其他進(jìn)程發(fā)來(lái)的消息.當(dāng)該字節(jié)的值發(fā)生變化時(shí),表示收到了該消息,進(jìn)行處理.然后再次把它的值設(shè)為-1.如果遇到的值為0,則視為結(jié)束信號(hào),取消該隊(duì)列,并退出SERVER.SERVER每接收到一次數(shù)據(jù)后顯示”(server)received”. (3)CLIENT端建立一個(gè)為75的共享區(qū),當(dāng)共享取得第一個(gè)字節(jié)為-1時(shí), Server端空閑,可發(fā)送請(qǐng)求. CLIENT 隨即填入9到0.期間等待Server端再次空閑.進(jìn)行完這些操作后, CLIENT 退出. CLIENT每發(fā)送一次數(shù)據(jù)后顯示”(client)sent”. (4)父進(jìn)程在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ū)，長(zhǎng)度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*/*addr=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();else CLIENT(); 結(jié)果 運(yùn)行的結(jié)果和預(yù)想的完全一樣。但在運(yùn)行的過(guò)程中，發(fā)現(xiàn)每當(dāng)client發(fā)送一次數(shù)據(jù)后，server要等大約0.1秒才有響應(yīng)。同樣，之后client又需要等待大約0.1秒才發(fā)送下一個(gè)數(shù)據(jù)。分析出現(xiàn)上述的應(yīng)答延遲的現(xiàn)象是程序設(shè)計(jì)的問(wèn)題。當(dāng)client端發(fā)送了數(shù)據(jù)后，并沒(méi)有任何措施通知server端數(shù)據(jù)已經(jīng)發(fā)出，需要由client的查詢才能感知。此時(shí)，client端并沒(méi)有放棄系統(tǒng)的控制權(quán)，仍然占用CPU的時(shí)間片。只有當(dāng)系統(tǒng)進(jìn)行調(diào)度時(shí)，切換到了server進(jìn)程，再進(jìn)行應(yīng)答。這個(gè)問(wèn)題，也同樣存在于server端到client的應(yīng)答過(guò)程之中。3 比較兩種消息通信機(jī)制中的數(shù)據(jù)傳輸?shù)臅r(shí)間 由于兩種機(jī)制實(shí)現(xiàn)的機(jī)理和用處都不一樣，難以直接進(jìn)行時(shí)間上的比較。如果比較其性能，應(yīng)更加全面的分析。(1) 消息隊(duì)列的建立比共享區(qū)的設(shè)立消耗的資源少.前者只是一個(gè)軟件上設(shè)定的問(wèn)題,后者需要對(duì)硬件操作,實(shí)現(xiàn)內(nèi)存的映像,當(dāng)然控制起來(lái)比前者復(fù)雜.如果每次都重新進(jìn)行隊(duì)列或共享的建立,共享區(qū)的設(shè)立沒(méi)有什么優(yōu)勢(shì)。(2) 當(dāng)消息隊(duì)列和共享區(qū)建立好后,共享區(qū)的數(shù)據(jù)傳輸,受到了系統(tǒng)硬件的支持,不耗費(fèi)多余的資源;而消息傳遞,由軟件進(jìn)行控制和實(shí)現(xiàn),需要消耗一定的CPU資源.從這個(gè)意義上講,共享區(qū)更適合頻繁和大量的數(shù)據(jù)傳輸.(3) 消息的傳遞,自身就帶有同步的控制.當(dāng)?shù)鹊较⒌臅r(shí)候,進(jìn)程進(jìn)入睡眠狀態(tài),不再消耗CPU資源.而共享隊(duì)列如果不借助其他機(jī)制進(jìn)行同步,接受數(shù)據(jù)的一方必須進(jìn)行不斷的查詢,白白浪費(fèi)了大量的CPU資源.可見(jiàn)消息方式的使用更加靈活.實(shí)驗(yàn)5指導(dǎo)實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū),并使用下列算法計(jì)算訪問(wèn)命中率.（1） 進(jìn)先出的算法（FIFO）（2） 最近最少使用的算法（LRU）（3） 最佳淘汰算法(OPT)（4） 最少訪問(wèn)頁(yè)面算法(LFU)（5） 最近最不經(jīng)常使用算法(NUR)命中率=(1-頁(yè)面失效次數(shù))/頁(yè)地址流長(zhǎng)度程序設(shè)計(jì)本實(shí)驗(yàn)的程序設(shè)計(jì)基本上按照實(shí)驗(yàn)內(nèi)容進(jìn)行。即首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁(yè)地址流，并針對(duì)不同的算法計(jì)算出相應(yīng)的命中率。相關(guān)定義如下：1 數(shù)據(jù)結(jié)構(gòu)(1)頁(yè)面類型 typedef struct int pn,pfn,counter,time; pl-type;其中pn 為頁(yè)號(hào),pfn為面號(hào), counter為一個(gè)周期內(nèi)訪問(wèn)該頁(yè)面的次數(shù), time為訪問(wèn)時(shí)間.(2) 頁(yè)面控制結(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; 其中pfctotal_vp定義用戶進(jìn)程虛頁(yè)控制結(jié)構(gòu),*freepf_head為空頁(yè)面頭的指針,*busypf_head為忙頁(yè)面頭的指針,*busypf_tail為忙頁(yè)面尾的指針.2函數(shù)定義（1）Void initialize( ):初始化函數(shù),給每個(gè)相關(guān)的頁(yè)面賦值.（2）Void FIFO( ):計(jì)算使用FIFO算法時(shí)的命中率.（3）Void LRU( ):計(jì)算使用LRU算法時(shí)的命中率.（4）Void OPT( ):計(jì)算使用OPT算法時(shí)的命中率.（5）Void LFU( ):計(jì)算使用LFU算法時(shí)的命中率.（6）Void NUR( ):計(jì)算使用NUR算法時(shí)的命中率.3.變量定義(1)int atotal_instruction: 指令流數(shù)據(jù)組.(2)int pagetotal_instruction: 每條指令所屬的頁(yè)號(hào).(3)int offsettotal_instruction: 每頁(yè)裝入10條指令后取模運(yùn)算頁(yè)號(hào)偏移值.(4)int total_pf: 用戶進(jìn)程的內(nèi)存頁(yè)面數(shù).(5)int disaffect: 頁(yè)面失效次數(shù).4.程序參考源碼及結(jié)果#define TRUE 1#define FALSE 0#define INVALID -1#define NULL 0#define total_instruction 320 /*指令流長(zhǎng)*/#define total_vp 32 /*虛頁(yè)長(zhǎng)*/#define clear_period 50 /*清0周期*/typedef struct /*頁(yè)面結(jié)構(gòu)*/int pn; /頁(yè)號(hào) logic numberint pfn; /頁(yè)面框架號(hào) physical frame numberint counter; /計(jì)數(shù)器int time; /時(shí)間pl_type;pl_type pltotal_vp; /*頁(yè)面線性結(jié)構(gòu)-指令序列需要使用地址*/typedef struct pfc_struct /*頁(yè)面控制結(jié)構(gòu)，調(diào)度算法的控制結(jié)構(gòu)*/ int pn;int pfn;struct pfc_struct *next;pfc_type;pfc_type pfctotal_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(); /*由于每次運(yùn)行時(shí)進(jìn)程號(hào)不同，故可用來(lái)作為初始化隨機(jī)數(shù)隊(duì)列的“種子”*/s=(float)319*rand( )/32767/32767/2+1; /*正態(tài)分布*/for(i=0;itotal_instruction;i+=4) /*產(chǎn)生指令隊(duì)列*/if(s319)printf(When i=%d,Error,s=%dn,i,s);exit(0); ai=s; /*任選一指令訪問(wèn)點(diǎn)m*/ai+1=ai+1; /*順序執(zhí)行一條指令*/ai+2=(float)ai*rand( )/32767/32767/2; /*執(zhí)行前地址指令m*/ai+3=ai+2+1; /*順序執(zhí)行一條指令*/s=(float)(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+) /*將指令序列變換成頁(yè)地址流*/pagei=ai/10;offseti=ai%10;for(i=4;i=32;i+) /*用戶內(nèi)存工作區(qū)從4個(gè)頁(yè)面到32個(gè)頁(yè)面*/printf(-%2d page frames-n,i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);return 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; /*置頁(yè)面控制結(jié)構(gòu)中的頁(yè)號(hào)，頁(yè)面為空*/pli.counter=0; /*頁(yè)面控制結(jié)構(gòu)中的訪問(wèn)次數(shù)為0*/pli.time=-1; /*訪問(wèn)的時(shí)間*/for(i=0;itotal_pf-1;i+)/*建立pfci-1和pfci之間的鏈接*/pfci.next=&pfci+1;pfci.pfn=i; pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0; /*空頁(yè)面隊(duì)列的頭指針為pfc0*/return 0;int FIFO(int total_pf) /*先進(jìn)先出算法total_pf:用戶進(jìn)程的內(nèi)存頁(yè)面數(shù)*/int i,j;pfc_type *p;/*中間變量*/initialize(total_pf); /*初始化相關(guān)頁(yè)面控制用數(shù)據(jù)結(jié)構(gòu)*/busypf_head=busypf_tail=NULL; /*忙頁(yè)面隊(duì)列頭，隊(duì)列尾鏈接*/for(i=0;inext; plbusypf_head-pn.pfn=INVALID;freepf_head=busypf_head; /*釋放忙頁(yè)面隊(duì)列的第一個(gè)頁(yè)面*/freepf_head-next=NULL; /*表明還是缺頁(yè)*/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=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) /*頁(yè)面失效*/diseffect+;if(freepf_head=NULL) /*無(wú)空閑頁(yè)面*/min=32767;/*設(shè)置最大值*/for(j=0;jplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; /騰出一個(gè)單元plminj.pfn=INVALID;plminj.time=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空閑頁(yè)面,改為有效plpagei.time=present_time;freepf_head=freepf_head-next; /減少一個(gè)free 頁(yè)面elseplpagei.time=present_time; /命中則增加該單元的訪問(wèn)次數(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) /*頁(yè)面失效*/diseffect+;if(freepf_head=NULL) /*無(wú)空閑頁(yè)面*/ 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+)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) /*頁(yè)面失效*/diseffect+;if(freepf_head=NULL) /*無(wú)空閑頁(yè)面*/for(j=0;jtotal_vp;j+)if(plj.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;/*該算法時(shí)根據(jù)已知的預(yù)測(cè)未知的，least frequency 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) /*頁(yè)面失效*/ diseffect+;if(freepf_head=NULL) /*無(wú)空閑頁(yè)面*/ min=32767;/*獲取counter的使用用頻率最小的內(nèi)存*/for(j=0;jplj.counter&plj.pfn!=INVALID)min=plj.counter;minpage=j;freepf_head=&pfcplminpage.pfn;plminpage.pfn=INVALID;plminpage.counter=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空閑頁(yè)面,改為有效plpagei.counter+;freepf_head=freepf_head-next; /減少一個(gè)free 頁(yè)面elseplpagei.counter;plpagei.counter=plpagei.counter+1;printf(LFU:%6.4fn,1-(float)diseffect/320);return 0;結(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.371