操作系統(tǒng)實(shí)驗(yàn)答案操作系統(tǒng)實(shí)驗(yàn)答案操作系統(tǒng)實(shí)驗(yàn)答案xxx公司操作系統(tǒng)實(shí)驗(yàn)答案文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度部分實(shí)驗(yàn)答案第三部分操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)3指導(dǎo)[實(shí)驗(yàn)內(nèi)容]進(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é)果，并分析原因?！闯绦颉?include<>main(){intp1,p2; if(p1=fork())/*子進(jìn)程創(chuàng)建成功*/ putchar('b'); else { if(p2=fork())/*子進(jìn)程創(chuàng)建成功*/ putchar('c'); elseputchar('a');/*父進(jìn)程執(zhí)行*/ }}SHAPE<運(yùn)行結(jié)果> bca(有時(shí)會(huì)出現(xiàn)abc的任意的排列)分析：從進(jìn)程執(zhí)行并發(fā)來看，輸出abc的排列都是有可能的。原因：fork()創(chuàng)建進(jìn)程所需的時(shí)間雖然可能多于輸出一個(gè)字符的時(shí)間，但各個(gè)進(jìn)程的時(shí)間片的獲得卻不是一定是順序的，所以輸出abc的排列都是有可能的。進(jìn)程的控制<任務(wù)>修改已編寫好的程序，將每個(gè)程序的輸出由單個(gè)字符改為一句話，再觀察程序執(zhí)行時(shí)屏幕上出現(xiàn)的現(xiàn)象，并分析其原因。如果在程序中使用系統(tǒng)調(diào)用lockf()來給每個(gè)程序加鎖，可以實(shí)現(xiàn)進(jìn)程之間的互斥，觀察并分析出現(xiàn)的現(xiàn)象?！闯绦?〉#include<>main(){ intp1,p2,i; if(p1=fork()){ for(i=0;i<500;i++) printf("parent%d\n",i);wait(0);/*保證在子進(jìn)程終止前，父進(jìn)程不會(huì)終止*/ exit(0);} else { if(p2=fork()) { for(i=0;i<500;i++) printf("son%d\n",i);wait(0);/*保證在子進(jìn)程終止前，父進(jìn)程不會(huì)終止*/ exit(0);/*向父進(jìn)程信號(hào)0且該進(jìn)程推出*/} else { for(i=0;i<500;i++) printf(“grandchild%d\n",i); exit(0);} }}〈運(yùn)行結(jié)果〉 parent…. son… grandchild… grandchild… 或grandchild …son …grandchild …son …parent 分析：由于函數(shù)printf()輸出的字符串之間不會(huì)被中斷，因此,每個(gè)字符串內(nèi)部的字符順序輸出時(shí)不變。但是,由于進(jìn)程并發(fā)執(zhí)行時(shí)的調(diào)度順序和父子進(jìn)程的搶占處理機(jī)問題，輸出字符串的順序和先后隨著執(zhí)行的不同而發(fā)生變化。這與打印單字符的結(jié)果相同。〈程序2〉#include<>main(){ intp1,p2,i; if(p1=fork()) { lockf(1,1,0); for(i=0;i<500;i++) printf("parent%d\n",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;i<500;i++)printf("son%d\n",i); lockf(1,0,0);wait(0);/*保證在子進(jìn)程終止前，父進(jìn)程不會(huì)終止*/ exit(0); } else { lockf(1,1,0); for(i=0;i<500;i++)printf("daughter%d\n",i); lockf(1,0,0); exit(0); } }}<運(yùn)行結(jié)果〉輸出parent塊,son塊,grandchild塊的順序可能不同，但是每個(gè)塊的輸出過程不會(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)程捕捉鍵盤上來的中斷信號(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)后，分別輸出下列信息后終止：childprocess1iskilledbyparent!childprocess2iskilledbyparent!父進(jìn)程等待兩個(gè)子進(jìn)程終止后，輸出以下信息后終止：parentprocessiskilled!<程序流程圖>〈程序〉#include<>#include<>#include<>voidwaiting(),stop(),alarming();intwait_mark;main(){ intp1,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);/*接受SIGALRM waiting(); kill(p1,16);/*向p1發(fā)軟中斷信號(hào)16*/ kill(p2,17);/*向p2發(fā)軟中斷信號(hào)17*/ wait(0);/*同步*/ wait(0); printf("parentprocessiskilled!\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("childprocess2iskilledbyparent!\n"); lockf(1,0,0); exit(0); } } else { wait_mark=1; signal(16,stop);signal(SIGINT,SIG_IGN);/*忽略^c信號(hào)*/ while(wait_mark!=0) lockf(1,1,0); printf("childprocess1iskilledbyparent!\n"); lockf(1,0,0); exit(0); }}voidwaiting(){ sleep(5);if(wait_mark!=0)kill(getpid(),SIGALRM);}voidalarming(){ wait_mark=0;}voidstop(){ wait_mark=0;}<運(yùn)行結(jié)果>不做任何操作等待五秒鐘父進(jìn)程回在子進(jìn)程縣推出后退出，并打印退出的順序；或者點(diǎn)擊ctrl+C后程序退出并打印退出的順序。〈任務(wù)2〉在上面的任務(wù)1中，增加語句signal(SIGINT,SIG_IGN)和語句signal(SIGQUIT,SIG_IGN)，觀察執(zhí)行結(jié)果，并分析原因。這里，signal(SIGINT,SIG_IGN)和signal(SIGQUIT,SIG_IGN)分別為忽略鍵信號(hào)以及忽略中斷信號(hào)。<程序>#include<>#include<>#include<> intpid1,pid2; intEndFlag=0; intpf1=0; intpf2=0;voidIntDelete(){ kill(pid1,16); kill(pid2,17);}voidInt1(){ printf("childprocess1iskilled!byparent\n"); exit(0);}voidInt2(){ printf("childprocess2iskilled!byparent\n"); exit(0);}main(){ intexitpid; if(pid1=fork()) { if(pid2=fork()) { signal(SIGINT,IntDelete); waitpid(-1,&exitpid,0); waitpid(-1,&exitpid,0); printf("parentprocessiskilled\n"); exit(0); } else { signal(SIGINT,SIG_IGN); signal(17,Int2); pause(); } } else { signal(SIGINT,SIG_IGN); signal(16,Int1); pause(); }}〈運(yùn)行結(jié)果〉請(qǐng)讀者將上述程序輸入計(jì)算機(jī)后，執(zhí)行并觀察。進(jìn)程的管道通信〈任務(wù)〉 編制一段程序，實(shí)現(xiàn)進(jìn)程的管道通信。使用系統(tǒng)調(diào)用pipe()建立一條管道線。兩個(gè)子進(jìn)程p1和p2分別向通道個(gè)寫一句話：child1processissendingmessage!child2processissendingmessage!而父進(jìn)程則從管道中讀出來自兩個(gè)進(jìn)程的信息，顯示在屏幕上?！闯绦颉?include<>#include<>#include<>intpid1,pid2;main(){intfd[2];charoutpipe[100],inpipe[100];pipe(fd);/*創(chuàng)建一個(gè)管道*/while((pid1=fork())==-1);if(pid1==0){lockf(fd[1],1,0);sprintf(outpipe,"child1processissendingmessage!"); /*把串放入數(shù)組outpipe中*/write(fd[1],outpipe,50);/*向管道寫長(zhǎng)為50字節(jié)的串*/sleep(5);/*自我阻塞5秒*/lockf(fd[1],0,0);exit(0);}else{while((pid2=fork())==-1);if(pid2==0){lockf(fd[1],1,0);/*互斥*/sprintf(outpipe,"child2processissendingmessage!");write(fd[1],outpipe,50);sleep(5);lockf(fd[1],0,0);exit(0);}else{wait(0);/*同步*/read(fd[0],inpipe,50);/*從管道中讀長(zhǎng)為50字節(jié)的串*/printf("%s\n",inpipe);wait(0);read(fd[0],inpipe,50);printf("%s\n",inpipe);exit(0);}}}〈運(yùn)行結(jié)果〉 延遲5秒后顯示: child1processissendingmessage! 再延遲5秒: child2processissendingmessage!〈分析〉 請(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ā)送和接收的程序?！闯绦蛟O(shè)計(jì)〉為了便于操作和觀察結(jié)果，用一個(gè)程序?yàn)椤耙印?，先后fork()兩個(gè)子進(jìn)程，SERVER和CLIENT，進(jìn)行通信。SERVER端建立一個(gè)Key為75的消息隊(duì)列，等待其他進(jìn)程發(fā)來的消息。當(dāng)遇到類型為1的消息，則作為結(jié)束信號(hào)，取消該隊(duì)列，并退出SERVER。SERVER每接收到一個(gè)消息后顯示一句“(server)received”。CLIENT端使用Key為75的消息隊(duì)列，先后發(fā)送類型從10到1的消息，然后退出。最后的一個(gè)消息，既是SERVER端需要的結(jié)束信號(hào)。CLIENT每發(fā)送一條消息后顯示一句“(client)sent”。父進(jìn)程在SERVER和CLIENT均退出后結(jié)束?！闯绦颉?include<>#include<sys/>#include<sys/>#include<sys/>#defineMSGKEY75/*定義關(guān)鍵詞MEGKEY*/structmsgform/*消息結(jié)構(gòu)*/{ longmtype; charmtexe[100];/*文本長(zhǎng)度*/}msg;intmsgqid,i;voidCLIENT(){ inti; msgqid=msgget(MSGKEY,0777|IPC_CREAT); for(i=10;i>=1;i--) { =i; printf("(client)sent\n"); msgsnd(msgqid,&msg,1030,0);/*發(fā)送消息msg入msgid消息隊(duì)列*/ } exit(0);}voidSERVER(){msgqid=msgget(MSGKEY,0777|IPC_CREAT);/*由關(guān)鍵字獲得消息隊(duì)列*/do{ msgrcv(msgqid,&msg,1030,0,0);/*從隊(duì)列msgid接受消息msg*/ printf("(server)receive\n");}while!=1);/*消息類型為1時(shí)，釋放隊(duì)列*/msgctl(msgqid,IPC_RMID,0);}main(){if(fork()){SERVER(); wait(0);} elseCLIENT();}<結(jié)果>從理想的結(jié)果來說，應(yīng)當(dāng)是每當(dāng)Client發(fā)送一個(gè)消息后，server接收該消息，Client再發(fā)送下一條。也就是說“(Client)sent”和“(server)received”的字樣應(yīng)該在屏幕上交替出現(xiàn)。實(shí)際的結(jié)果大多是，先由Client發(fā)送兩條消息，然后Server接收一條消息。此后ClientServer交替發(fā)送和接收消息.最后一次接收兩條消息.Client和Server分別發(fā)送和接收了10條消息,與預(yù)期設(shè)想一致<分析>message的傳送和控制并不保證完全同步,當(dāng)一個(gè)程序不再激活狀態(tài)的時(shí)候,它完全可能繼續(xù)睡眠,造成上面現(xiàn)象,在多次sendmessage后才receivemessage.這一點(diǎn)有助于理解消息轉(zhuǎn)送的實(shí)現(xiàn)機(jī)理.2.共享存儲(chǔ)區(qū)的創(chuàng)建,附接和斷接<任務(wù)>使用系統(tǒng)調(diào)用shmget(),sgmat(),smgdt(),shmctl()編制一個(gè)與上述功能相同的程序.<程序設(shè)計(jì)>(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ā)來的消息.當(dāng)該字節(jié)的值發(fā)生變化時(shí),表示收到了該消息,進(jìn)行處理.然后再次把它 的值設(shè)為-1.如果遇到的值為0,則視為結(jié)束信號(hào),取消該隊(duì)列,并退出每接 收到一次數(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<sys/>#include<sys/>#include<sys/>#defineSHMKEY75/*定義共享區(qū)關(guān)鍵詞*/intshmid,i;int*addr;CLIENT(){ inti; 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)sent\n");/*打?。╟lient）sent*/ *addr=i;/*把i賦給addr*/ } exit(0);}SERVER(){ do { while(*addr==-1); printf("(server)received\n%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)行的過程中，發(fā)現(xiàn)每當(dāng)client發(fā)送一次數(shù)據(jù)后，server要等大約秒才有響應(yīng)。同樣，之后client又需要等待大約秒才發(fā)送下一個(gè)數(shù)據(jù)。<分析〉出現(xiàn)上述的應(yīng)答延遲的現(xiàn)象是程序設(shè)計(jì)的問題。當(dāng)client端發(fā)送了數(shù)據(jù)后，并沒有任何措施通知server端數(shù)據(jù)已經(jīng)發(fā)出，需要由client的查詢才能感知。此時(shí)，client端并沒有放棄系統(tǒng)的控制權(quán)，仍然占用CPU的時(shí)間片。只有當(dāng)系統(tǒng)進(jìn)行調(diào)度時(shí)，切換到了server進(jìn)程，再進(jìn)行應(yīng)答。這個(gè)問題，也同樣存在于server端到client的應(yīng)答過程之中。3比較兩種消息通信機(jī)制中的數(shù)據(jù)傳輸?shù)臅r(shí)間 由于兩種機(jī)制實(shí)現(xiàn)的機(jī)理和用處都不一樣，難以直接進(jìn)行時(shí)間上的比較。如果比較其性能，應(yīng)更加全面的分析。消息隊(duì)列的建立比共享區(qū)的設(shè)立消耗的資源少.前者只是一個(gè)軟件上設(shè)定的問題,后者需要對(duì)硬件操作,實(shí)現(xiàn)內(nèi)存的映像,當(dāng)然控制起來比前者復(fù)雜.如果每次都重新進(jìn)行隊(duì)列或共享的建立,共享區(qū)的設(shè)立沒有什么優(yōu)勢(shì)。當(dāng)消息隊(duì)列和共享區(qū)建立好后,共享區(qū)的數(shù)據(jù)傳輸,受到了系統(tǒng)硬件的支持,不耗費(fèi)多余的資源;而消息傳遞,由軟件進(jìn)行控制和實(shí)現(xiàn),需要消耗一定的CPU資源.從這個(gè)意義上講,共享區(qū)更適合頻繁和大量的數(shù)據(jù)傳輸.消息的傳遞,自身就帶有同步的控制.當(dāng)?shù)鹊较⒌臅r(shí)候,進(jìn)程進(jìn)入睡眠狀態(tài),不再消耗CPU資源.而共享隊(duì)列如果不借助其他機(jī)制進(jìn)行同步,接受數(shù)據(jù)的一方必須進(jìn)行不斷的查詢,白白浪費(fèi)了大量的CPU資源.可見消息方式的使用更加靈活.實(shí)驗(yàn)5指導(dǎo)[實(shí)驗(yàn)內(nèi)容]<任務(wù)>設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū),并使用下列算法計(jì)算訪問命中率.進(jìn)先出的算法（FIFO）最近最少使用的算法（LRU）最佳淘汰算法(OPT)最少訪問頁面算法(LFU)最近最不經(jīng)常使用算法(NUR) 命中率=(1-頁面失效次數(shù))/頁地址流長(zhǎng)度<程序設(shè)計(jì)〉 本實(shí)驗(yàn)的程序設(shè)計(jì)基本上按照實(shí)驗(yàn)內(nèi)容進(jìn)行。即首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對(duì)不同的算法計(jì)算出相應(yīng)的命中率。相關(guān)定義如下：1數(shù)據(jù)結(jié)構(gòu) (1)頁面類型typedefstruct{intpn,pfn,counter,time;}pl-type;其中pn為頁號(hào),pfn為面號(hào),counter為一個(gè)周期內(nèi)訪問該頁面的次數(shù),time為訪問時(shí)間. (2)頁面控制結(jié)構(gòu)pfc-struct{intpn,pfn;structpfc_struct*next;}typedefstructpfc_structpfc_type;pfc_typepfc_struct[total_vp],*freepf_head,*busypf_head;pfc_type*busypf_tail;其中pfc[total_vp]定義用戶進(jìn)程虛頁控制結(jié)構(gòu),*freepf_head為空頁面頭的指針,*busypf_head為忙頁面頭的指針,*busypf_tail為忙頁面尾的指針.2．函數(shù)定義 （1）Voidinitialize():初始化函數(shù),給每個(gè)相關(guān)的頁面賦值. （2）VoidFIFO():計(jì)算使用FIFO算法時(shí)的命中率. （3）VoidLRU():計(jì)算使用LRU算法時(shí)的命中率. （4）VoidOPT():計(jì)算使用OPT算法時(shí)的命中率. （5）VoidLFU():計(jì)算使用LFU算法時(shí)的命中率. （6）VoidNUR():計(jì)算使用NUR算法時(shí)的命中率.3.變量定義 (1)inta[total_instruction]:指令流數(shù)據(jù)組. (2)intpage[total_instruction]:每條指令所屬的頁號(hào). (3)intoffset[total_instruction]:每頁裝入10條指令后取模運(yùn)算頁號(hào)偏移值. (4)inttotal_pf:用戶進(jìn)程的內(nèi)存頁面數(shù). (5)intdisaffect:頁面失效次數(shù).4.程序參考源碼及結(jié)果<程序>#defineTRUE1#defineFALSE0#defineINVALID-1#defineNULL0#definetotal_instruction320/*指令流長(zhǎng)*/#definetotal_vp32/*虛頁長(zhǎng)*/#defineclear_period50/*清0周期*/typedefstruct/*頁面結(jié)構(gòu)*/{ intpn;fn=INVALID;/*置頁面控制結(jié)構(gòu)中的頁號(hào)，頁面為空*/ pl[i].counter=0;/*頁面控制結(jié)構(gòu)中的訪問次數(shù)為0*/ pl[i].time=-1;/*訪問的時(shí)間*/ } for(i=0;i<total_pf-1;i++) /*建立pfc[i-1]和pfc[i]之間的鏈接*/ { pfc[i].next=&pfc[i+1]; pfc[i].pfn=i; } pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0];/*空頁面隊(duì)列的頭指針為pfc[0]*/ return0;}intFIFO(inttotal_pf)/*先進(jìn)先出算法total_pf:用戶進(jìn)程的內(nèi)存頁面數(shù)*/{ inti,j; pfc_type*p; /*中間變量*/ initialize(total_pf);/*初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)*/ busypf_head=busypf_tail=NULL;/*忙頁面隊(duì)列頭，隊(duì)列尾鏈接*/ for(i=0;i<total_instruction;i++) { if(pl[page[i]].pfn==INVALID)/*頁面失效*/ { diseffect+=1;/*失效次數(shù)*/ if(freepf_head==NULL)/*無空閑頁面*/ { p=busypf_head->next; pl[busypf_head->pn].pfn=INVALID; freepf_head=busypf_head;/*釋放忙頁面隊(duì)列的第一個(gè)頁面*/ freepf_head->next=NULL;/*表明還是缺頁*/ busypf_head=p; } p=freepf_head->next; freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn; freepf_head->next=NULL;/*使busy的尾為null*/ if(busypf_tail==NULL) { busypf_tail=busypf_head=freepf_head; } else { busypf_tail->next=freepf_head; busypf_tail=freepf_head; } freepf_head=p; } } printf("FIFO:%6.4f\n",1-(float)diseffect/320); return0;intLRU(inttotal_pf)/*最近最久未使用算法leastrecentlyused*/{ intmin,minj,i,j,present_time;/*minj為最小值下標(biāo)*/ initialize(total_pf); present_time=0; for(i=0;i<total_instruction;i++) { if(pl[page[i]].pfn==INVALID)/*頁面失效*/ { diseffect++; if(freepf_head==NULL)/*無空閑頁面*/ { min=32767; /*設(shè)置最大值*/ for(j=0;j<total_vp;j++)/*找出time的最小值*/ { if(min>pl[j].time&&pl[j].pfn!=INVALID) { min=pl[j].time; minj=j; } } freepf_head=&pfc[pl[minj].pfn];fn=INVALID; pl[minj].time=0; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn;ime=present_time; freepf_head=freepf_head->next;ime=present_time;6.4ffn==INVALID)/*頁面失效*/ { diseffect++; if(freepf_head==NULL)/*無空閑頁面*/ { cont_flag=TRUE; old_dp=dp; while(cont_flag) { if(pl[dp].counter==0&&pl[dp].pfn!=INVALID) cont_flag=FALSE; else { dp++; if(dp==total_vp) dp=0; if(dp==old_dp) for(j=0;j<total_vp;j++) pl[j].counter=0; } } freepf_head=&pfc[pl[dp].pfn]; pl[dp].pfn=INVALID; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn; freepf_head->pn=page[i]; freepf_head=freepf_head->next; } else pl[page[i]].counter=1; if(i%clear_period==0) for(j=0;j<total_vp;j++) pl[j].counter=0;}printf("NUR:%6.4f\n",1-(float)diseffect/320);return0;}intOPT(inttotal_pf)/*最佳置換算法*/{ inti,j,max,maxpage,d,dist[total_vp]; pfc_type*t; initialize(total_pf); for(i=0;i<total_instruction;i++) { if(pl[page[i]].pfn==INVALID)/*頁面失效*/ { diseffect++; if(freepf_head==NULL)/*無空閑頁面*/ { for(j=0;j<total_vp;j++) { if(pl[j].pfn!=INVALID) dist[j]=32767; else dist[j]=0; } for(j=0;j<total_vp;j++) { if((pl[j].pfn!=INVALID)&&(dist[j]==32767)) { dist[j]=j; } } max=0; for(j=0;j<total_vp;j++) if(max<dist[j]) { max=dist[j]; maxpage=j; } freepf_head=&pfc[pl[maxpage].pfn]; freepf_head->next=NULL; pl[maxpage].pfn=INVALID; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } } printf("OPT:%6.4f\n",1-(float)diseffect/320); return0;}/*該算法時(shí)根據(jù)已知的預(yù)測(cè)未知的，leastfrequencyUsed是最不經(jīng)常使用置換法*/intLFU(inttotal_pf){ inti,j,min,minpage; pfc_type*t; initialize(total_pf); for(i=0;i<total_instruction;i++) { if(pl[page[i]].pfn==INVALID)/*頁面失效*/ { diseffect++; if(freepf_head==NULL)/*無空閑頁面*/ { min=32767; /*獲取counter的使用用頻率最小的內(nèi)存*/ for(j=0;j<total_vp;j++) { if(min>pl[j].counter&&pl[j].pfn!=INVALID) { min=pl[j].counter; minpage=j; } } freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INVALID; pl[minpage].counter=0; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn;ounter++; freepf_head=freepf_head->next;ounter; pl[page[i]].counter=pl[page[i]].counter+1; } } printf("LFU:%6.4f\n",1-(float)diseffect/320); return0;} <結(jié)果一：〉4pageframesFIFO:::::5pageframesFIFO:::::6pageframesFIFO:::::7pageframesFIFO:::::8pageframesFIFO:::::9pageframesFIFO:::::10pageframesFIFO:::::11pageframesFIFO:::::12pageframesFIFO:::::13pageframesFIFO:::::14pageframesFIFO:::::15pageframesFIFO:::::16pageframesFIFO:::::17pageframesFIFO:::::18pageframesFIFO:::::19pageframesFIFO:::::20pageframesFIFO:::::21pageframesFIFO:::::22pageframesFIFO:::::23pageframesFIFO:::::24pageframesFIFO:::::25pageframesFIFO:::::26pageframesFIFO:::::27pageframesFIFO:::::28pageframesFIFO:::::29pageframesFIFO:::::30pageframesFIFO:::::31pageframesFIFO:::::32pageframesFIFO:::::<分析> 從上述結(jié)果可知，在內(nèi)存頁面數(shù)較少（4~5頁）時(shí)，五種算法的命中率差別不大，都是30%左右。在內(nèi)存頁面為7~18個(gè)頁面之間時(shí)，5種算法的訪內(nèi)命中率大致在35%~60%之間變化。但是，F(xiàn)IFO算法與OPT算法之間的差別一般在6~10個(gè)百分點(diǎn)左右。在內(nèi)存頁面為25~32個(gè)頁面時(shí)，由于用戶進(jìn)程的所有指令基本上都已裝入內(nèi)存，使命中率增加，從而算法之間的差別不大。比較上述5種算法，以O(shè)PT算法的命中率最高，NUR算法次之，再就是LFU算法和LRU算法，其次是FIFO算法。就本問題，在15頁之前，F(xiàn)IFO的命中率比LRU的高。<結(jié)果二：>4pageframesFIFO:::::5pageframesFIFO:::::6pageframesFIFO:::::7pageframesFIFO:::::8pageframesFIFO:::::9pageframesFIFO:::::10pageframesFIFO:::::11pageframesFIFO:::::12pageframesFIFO:::::13pageframesFIFO:::::14pageframesFIFO:::::15pageframesFIFO:::::16pageframesFIFO:::::17pageframesFIFO:::::18pageframesFIFO:::::19pageframesFIFO:::::20pageframesFIFO:::::21pageframesFIFO:::::22pageframesFIFO:::::23pageframesFIFO:::::24pageframesFIFO:::::25pageframesFIFO:::::26pageframesFIFO:::::27pageframesFIFO:::::28pageframesFIFO:::::29pageframesFIFO:::::30pageframesFIFO:::::31pageframesFIFO:::::32pageframesFIFO:::::<分析> 從結(jié)果可以看出，F(xiàn)IFO的命中率竟然比OPT的還高。至于為什么，請(qǐng)?zhí)接?。?shí)驗(yàn)6指導(dǎo)[實(shí)驗(yàn)內(nèi)容]<任務(wù)>為L(zhǎng)inux系統(tǒng)設(shè)計(jì)一個(gè)簡(jiǎn)單的二級(jí)文件系統(tǒng)。要求做到以下幾點(diǎn)：1.可以實(shí)現(xiàn)下列幾條命令： login用戶登錄 dir列目錄 create創(chuàng)建文件 delete刪除文件 open打開文件 close關(guān)閉文件 read讀文件 write寫文件2．列目錄時(shí)要列出文件名，物理地址，保護(hù)碼和文件長(zhǎng)度3．源文件可以進(jìn)行讀寫保護(hù)<程序設(shè)計(jì)>(1)設(shè)計(jì)思想本文件系統(tǒng)采用兩級(jí)目錄，其中第一級(jí)對(duì)應(yīng)于用戶賬號(hào)，第二級(jí)對(duì)應(yīng)于用戶帳號(hào)下的文件。另外，為了簡(jiǎn)便文件系統(tǒng)未考慮文件共享，文件系統(tǒng)安全以及管道文件與設(shè)備文件等特殊內(nèi)容。對(duì)這些內(nèi)容感興趣的讀者，可以在本系統(tǒng)的程序基礎(chǔ)上進(jìn)行擴(kuò)充。(2)主要數(shù)據(jù)結(jié)構(gòu)I節(jié)點(diǎn)structinode{structinode*i_forw;structinode*i_back;charI_flag;unsignedinti_into;/*磁盤i節(jié)點(diǎn)標(biāo)號(hào)*/unsignedinti_count;/*引用計(jì)數(shù)*/unsignedshortdi_number;/*關(guān)聯(lián)文件書，當(dāng)為0時(shí)，則刪除該文件*/unsignedshortdi_mode;/*存取權(quán)限*/unsignedshortdi_uid;/*磁盤i節(jié)點(diǎn)用戶*/unsignedshortdi_gid;/*磁盤i節(jié)點(diǎn)組*/Unsignedintdi_addr[NADDR];/*物理塊號(hào)*/b)磁盤i結(jié)點(diǎn)Structdinode{unsignedshortdi_number;/*關(guān)聯(lián)文件數(shù)*/unsignedshortdi_mode;/*存取權(quán)限*/unsignedshortdi_uid;unsignedshortdi_gid;unsignedlongdi_size;/*文件大小*/unsignedintdi_addr[NADDR];/*物理塊號(hào)*/c)目錄項(xiàng)結(jié)構(gòu)Structdirect{chard_name[DIRSIZ];/*目錄名*/unsignedintd_ino;/*目錄號(hào)*/}d)超級(jí)塊Structfilsys{unsignedshorts_isize;/*i節(jié)點(diǎn)塊塊數(shù)*/unsignedlongs_fsize;/*數(shù)據(jù)塊塊數(shù)*/unsignedints_nfree;/*空閑塊塊數(shù)*/unsignedshorts_pfree;/*空閑塊指針*/unsignedints_free[NICFREE];/*空閑塊堆棧*/unsignedints_ninode;/*空閑i節(jié)點(diǎn)數(shù)*/unsignedshorts_pinode;/*空閑i節(jié)點(diǎn)指針*/unsignedints_inode[NICINOD];/*空閑i節(jié)點(diǎn)數(shù)組*/unsignedints_rinode;/*銘記i節(jié)點(diǎn)*/chars_fmod;/*超級(jí)塊修改標(biāo)志*/};e)用戶密碼Structpwd{unsignedshortP_uid;unsignedshortP_gid;charpassward[PWOSIZ];}f)目錄Structdir{strutdirectdirect[DIRNUM];intsize;}g).查找i內(nèi)存節(jié)點(diǎn)的hash表Structhinode{strutinode*iforw;}h).系統(tǒng)打開表Structfile{charf_flag;/*文件操作標(biāo)志*/unsignedintf_count;/*引用計(jì)數(shù)*/structinode*f_inode;/*指向內(nèi)存節(jié)點(diǎn)*/unsignedlongf_off;/*讀/寫指針*/}i)用戶打開表Structuser{unsignedshortu_default_mode;unsignedshortu_uid;/*用戶標(biāo)志*/unsignedshortu_gid;/*用戶組標(biāo)志*/unsignedshortu_ofile[NOFILE];/*用戶打開表*/}3.主要函數(shù) （1）i節(jié)點(diǎn)內(nèi)容獲取函數(shù)iget()（詳細(xì)描述略）。 （2）節(jié)點(diǎn)內(nèi)容釋放函數(shù)iput()（詳細(xì)描述略）。 （3）目錄創(chuàng)建函數(shù)mkdir()（詳細(xì)描述略）。 （4）目錄搜索函數(shù)namei()（詳細(xì)描述略）。（5）磁盤塊分配函數(shù)balloc()（詳細(xì)描述略）。（6）磁盤塊釋放函數(shù)bfree()（詳細(xì)描述略）。（7）分配i節(jié)點(diǎn)區(qū)函數(shù)ialloc()（詳細(xì)描述略）。 （8）解釋結(jié)點(diǎn)區(qū)函數(shù)ifree（）（詳細(xì)描述略）。 （9）搜索當(dāng)前目錄下文件的函數(shù)iname（）（詳細(xì)描述略）。 （10）訪問控制函數(shù)access（）（詳細(xì)描述略）。 （11）顯示目錄和文件函數(shù)_dir（）（詳細(xì)描述略）。 （12）改變當(dāng)前目錄用函數(shù)chdir（）（詳細(xì)描述略）。 （13）打開文件函數(shù)open（）（詳細(xì)描述略）。 （14）創(chuàng)建文件函數(shù)create（）（詳細(xì)描述略）。 （15）讀文件用函數(shù)read（）（詳細(xì)描述略）。 （16）讀文件用函數(shù)write（）（詳細(xì)描述略）。 （17）用戶登陸函數(shù)login（）（詳細(xì)描述略）。 （18）用戶退出函數(shù)logout（）（詳細(xì)描述略）。 （19）文件系統(tǒng)格式化函數(shù)format（）（詳細(xì)描述略）。 （20）進(jìn)入文件系統(tǒng)函數(shù)install（）（詳細(xì)描述略）。 （21）關(guān)閉文件函數(shù)close（）（詳細(xì)描述略）。 （22）退出文件系統(tǒng)函數(shù)halt（）（詳細(xì)描述略）。 （23）文件刪除函數(shù)delecte（）（詳細(xì)描述略）。4．主程序說明beginStep1對(duì)磁盤進(jìn)行格式化Step2調(diào)用install（），進(jìn)入文件系統(tǒng)Step3調(diào)用_dir（），顯示當(dāng)前目錄Step4調(diào)用login（），用戶注冊(cè)Step5調(diào)用mkdir（）和chdir（）創(chuàng)建目錄Step6調(diào)用create（），創(chuàng)建文件0Step7分配緩沖區(qū)Step8寫文件0Step9關(guān)閉文件0和釋放緩沖Step10調(diào)用mkdir（）和chdir（）創(chuàng)建子目錄Step11調(diào)用create（），創(chuàng)建文件1Step12分配緩沖區(qū)Step13寫文件1Step14關(guān)閉文件1和釋放緩沖Step15調(diào)用chdir將當(dāng)前目錄移到上一級(jí)Step16調(diào)用create（），創(chuàng)建文件2Step17分配緩沖區(qū)Step18調(diào)用write（），寫文件2Step19關(guān)閉文件1和釋放緩沖Step20調(diào)用delecte（），刪除文件0Step21調(diào)用create（），創(chuàng)建文件1Step22為文件3分配緩沖區(qū)Step23調(diào)用write（），寫文件2Step24關(guān)閉文件3并釋放緩沖區(qū) Step25調(diào)用open()，打開文件2 Step26為文件2分配緩沖 Step27寫文件3后關(guān)閉文件3 Step28釋放緩沖 Step29用戶退出（logout） Step30關(guān)閉（halt）End由上述的描述過乘可知，該文件系統(tǒng)實(shí)際是為用戶提供一個(gè)解釋執(zhí)行相關(guān)命令的環(huán)境。主程序中的大部分語句都被用來執(zhí)行相應(yīng)的命令。下面我們給出每個(gè)過程的相關(guān)C語言程序。讀者也可以使用這些子過程，編寫一個(gè)用Shell控制的文件系統(tǒng)界面。<程序>1.編寫管理文件makefile本文件系統(tǒng)程序用編寫makefile管理工具進(jìn)行管理。其內(nèi)容如下：***********************************************************************//*******************************************makefile*******************************************/filsys:cc-ofilsys:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c:cc-c系統(tǒng)調(diào)用函數(shù)說明、參數(shù)值及定義1、fork() 創(chuàng)建一個(gè)新進(jìn)程 intfork() 其中返回int取值意義如下： 0：創(chuàng)建子進(jìn)程，從子進(jìn)程返回的id值 大于0：從父進(jìn)程返回的子進(jìn)程id值 -1：創(chuàng)建失敗2、lockf(files,function,size): 用作鎖定文件的某些段或者整個(gè)文件，本函數(shù)適用的頭文件為： #include<> 參數(shù)定義： intlockf(files,function,size) intfiles,function; longsize; 其中：files是文件描述符：function是鎖定和解鎖；1表示鎖定，0表示解鎖。size是鎖定和解鎖的字節(jié)數(shù)，若用0，表示從文件的當(dāng)前位置到文件尾。3、msgget(key,flag): 獲得一個(gè)消息的描述符，該描述符指定一個(gè)消息隊(duì)列以便用于其他系統(tǒng)調(diào)用。 該函數(shù)使用偷文件如下： #include<sy/> #include<sy/> #include<sy/> 參數(shù)定義 intmsgget(key,flag) key_tkey; intflag; 語法格式：msgqid=msgget(key,flag) 其中：msgid是該系統(tǒng)調(diào)用返回的描述符，失敗則返回-1；flag本身由操作允許權(quán)和控制命令值相“或”得到。 如：IP_CREAT|0400是否該隊(duì)列應(yīng)被創(chuàng)建； IP_EXCL|0400是否該隊(duì)列的創(chuàng)建應(yīng)是互斥的；等。4、msgsnd(id,msgp,size,flag): 發(fā)送一消息。 該函數(shù)是用頭文件如下： #include<sy/> #include<sy/> #include<sy/> 參數(shù)定義 intmsgnd(id,msgp,size,flag) intid,size,flag; structmsgbuf*msgp; 其中：id是返回消息隊(duì)列的描述符；msgp是指向用戶存儲(chǔ)區(qū)的一個(gè)構(gòu)造體指針，size指示由msgp指向的數(shù)據(jù)結(jié)構(gòu)中字符數(shù)組的長(zhǎng)度；即消息的長(zhǎng)度。這個(gè)數(shù)組的最大值由MSG-MAX系統(tǒng)可調(diào)用參數(shù)來確定。flag規(guī)定當(dāng)核心用盡內(nèi)部緩沖空間時(shí)應(yīng)執(zhí)行的動(dòng)作；若在標(biāo)志flag中末設(shè)置IPC_NOWAIT位，則當(dāng)該消息隊(duì)列中字節(jié)數(shù)超過一最大值時(shí)，或系統(tǒng)范圍的消息數(shù)超過某一最大值時(shí)，調(diào)用msgsnd進(jìn)程睡眠。若是設(shè)置IPC_NOWAIT，則在此情況下，msgsnd立即返回。5、msgrcv(id,msgp,size,type,flag): 接受一消息。 該函數(shù)調(diào)用使用頭文件如下： #include<sy/> #include<sy/> #include<sy/> 參數(shù)定義 intmsgrcv(id,msgp,size,type,flag) intid,size,type,flag; structmsgbuf*msgq; structsgbuf{longmtpe;chatmtext[];}; 語法格式： count=msgrcv(id,msgp,size,type,flag) 其中：id是用來存放欲接收消息的擁護(hù)數(shù)據(jù)結(jié)構(gòu)的地址；size是msgp中數(shù)據(jù)數(shù)組的大??；type是用戶要讀的消息類型： type為0:接收該隊(duì)列的第一個(gè)消息； type為正：接收類型type的第一個(gè)消息； type為負(fù)：接收小于或等于type絕對(duì)值的最低類型的第一個(gè)消息。 flag規(guī)定倘若該隊(duì)列無消息，核心應(yīng)當(dāng)做什么事，如果此時(shí)設(shè)置了IPC_NOWAIT標(biāo)志，則立即返回，若在flag中設(shè)置了MSG_NOERROR，且所接收的消息大小大于size，核心截?cái)嗨邮艿南ⅰ?count是返回消息正文的字節(jié)數(shù)。6、msgctl(id,cmd,buf): 查詢一個(gè)消息描述符的狀態(tài)，設(shè)置它的狀態(tài)及刪除一個(gè)消息描述符。 調(diào)用該函數(shù)使用頭文件如下： #include<sy/> #include<sy/> #include<sy/> 參數(shù)定義 intmsgctl(id,cmd,buf) intid,cmd; structmsgbuf*msgq; structmsqid_ds*buf; 其中：函數(shù)調(diào)用成功時(shí)返回0，調(diào)用不成功時(shí)返回-1。id用來識(shí)別該消息的描述符；cmd規(guī)定命令的類型。 IPC_START將與id相關(guān)聯(lián)的消息隊(duì)列首標(biāo)讀入buf。 IPC_SET為這個(gè)消息序列設(shè)置有效的用戶和小組標(biāo)識(shí)及操作允許權(quán)和字節(jié)的數(shù)量。 IPC_RMID刪除id的消息隊(duì)列。 buf是含有控制參數(shù)或查詢結(jié)果的用戶數(shù)據(jù)結(jié)構(gòu)的地址。 附：msgid_ds結(jié)構(gòu)定義如下： structmsgid_ds {structipc_permmsg_perm;/*許可權(quán)結(jié)構(gòu)*/ shotpadl[7];/*由系統(tǒng)使用*/ ushortonsg_qnum; /*隊(duì)列上消息數(shù)*/ ushortmsg_qbytes; /*隊(duì)列上最大字節(jié)數(shù)*/ ushortmsg_lspid; /*最后發(fā)送消息的PID*/ ushortmsg_lrpid; /*最后接收消息的PID*/ time_tmsg__stime; /*最后發(fā)送消息的時(shí)間*/ time_tmsg_rtime; /*最后接收消息的時(shí)間*/ me_tmsg_ctime; /*最后更改時(shí)間*/ }； structipc_perm {ushortuid; /*當(dāng)前用戶id*/ ushortgid; /*當(dāng)前進(jìn)程組id*/ ushortcuid; /