東北大學(xué)操作系統(tǒng)實(shí)驗(yàn)報(bào)告

1、計(jì)算 機(jī)科學(xué) 與工程 學(xué)院實(shí) 驗(yàn)報(bào)告實(shí)驗(yàn)課程名稱(chēng)操作系統(tǒng)實(shí)驗(yàn)實(shí)驗(yàn)成績(jī)專(zhuān)業(yè)計(jì)算機(jī)科學(xué) 與技術(shù)班級(jí)1507 班指導(dǎo)教師簽字學(xué)號(hào)20154377姓名羅藝博實(shí)驗(yàn)報(bào)告批改 時(shí)間實(shí)驗(yàn)項(xiàng)目目錄1. 實(shí)驗(yàn)一熟悉Linux系統(tǒng)2. 實(shí)驗(yàn)二進(jìn)程狀態(tài)3. 實(shí)驗(yàn)三進(jìn)程同步和通信4. 實(shí)驗(yàn)四進(jìn)程的管道通信5. 實(shí)驗(yàn)五頁(yè)面置換算法實(shí)驗(yàn)報(bào)告正文實(shí)驗(yàn)一熟悉Linux系統(tǒng)一、實(shí)驗(yàn)?zāi)康氖煜ず驼莆誏inux系統(tǒng)基本命令，熟悉 Linux編程環(huán)境，為以后的實(shí)驗(yàn)打下基礎(chǔ)。二、實(shí)驗(yàn)原理基于linux系統(tǒng)的基礎(chǔ)操作三、實(shí)驗(yàn)內(nèi)容（源碼、注釋、基礎(chǔ)內(nèi)容、擴(kuò)展點(diǎn)等）、rm啟動(dòng)、退出、Is （顯示目錄內(nèi)容）、cp （文件或目錄的復(fù)制）、mv （文

2、件、目錄更名或移動(dòng)）（刪除文件或目錄）、mkdir （創(chuàng)建目錄）、rmdir （刪除空目錄）、cd （改變工作目錄）C語(yǔ)言編輯、編譯四、實(shí)驗(yàn)結(jié)果（截圖）Is mkdir:cd:rmdir:實(shí)驗(yàn)二進(jìn)程狀態(tài)一、實(shí)驗(yàn)?zāi)康淖孕芯幹颇M程序，通過(guò)形象化的狀態(tài)顯示，使學(xué)生理解進(jìn)程的概念、進(jìn)程之間的狀態(tài)轉(zhuǎn)換及其所帶來(lái)的PCB內(nèi)容、組織的變化，理解進(jìn)程與其PCB間的對(duì)應(yīng)關(guān)系。二、實(shí)驗(yàn)原理1. 進(jìn)程在內(nèi)存中存在三種基本狀態(tài)：就緒態(tài)、執(zhí)行態(tài)、阻塞態(tài)2. 三種狀態(tài)在滿(mǎn)足某種條件時(shí)會(huì)發(fā)生轉(zhuǎn)換： 就緒一一運(yùn)行：調(diào)度程序選擇一個(gè)新的進(jìn)程運(yùn)行 運(yùn)行一一就緒：運(yùn)行進(jìn)程用完了時(shí)間片運(yùn)行進(jìn)程被中斷，因?yàn)橐桓邇?yōu)先級(jí)進(jìn)程處于就緒狀態(tài)

3、 運(yùn)行一一阻塞：當(dāng)一進(jìn)程等待某一事件的發(fā)生時(shí)，如請(qǐng)求系統(tǒng)服務(wù)；初始化I/O 且必須等待結(jié)果；無(wú)新工作可做；等待某一進(jìn)程提供輸入（IPC） 阻塞一一就緒：當(dāng)所等待的事件發(fā)生時(shí)三、實(shí)驗(yàn)內(nèi)容（源碼、注釋、基礎(chǔ)內(nèi)容、擴(kuò)展點(diǎn)等）#in clude <iostream>#in elude <vector>#i nclude <stdlib.h>#i nclude <algorithm> /for "sort" in vectorusing n amespace std;class Pro /process classpublic:char

4、 n ame;string status;vector<Pro> ru,re,bl;ru->runnin g,re->ready,bl->blocked/function declarati onint helloUI();int in iQ();int showPCB();int ruTOre();int ruTObl();int blTOre();int neTOre();int ruTOex();int helloUI() /start UIcout << "Hello!Welcome to come back." <&

5、lt; en dl;cout << ”#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#”<< endl;cout << en dl;cout << en dl;return 0;int in iQ()/in itialize the processint i;cout << "Please en ter processes n ames and their status." << en dl;cout << en dl;for(i=0; i<5; i+)1

6、5 process a to oPro process;char n am;string sta;cout << "Please en ter " << i <<" processes n ames." << en dl;cin >> nam;process .n ame = n am;cout << "Please en ter processes status." << en dl;cout << "Status contai

7、ns r1(r unnin g),r2(ready) and b(blocked)." << en dl; cin >> sta;process.status = sta;if(sta = "r1") /judge which statusif(ru.size()<1)ru.push_back(process);cout << "yes" << en dl;elsecout << "Error!" << en dl;else if(sta = &q

8、uot;r2")re.push_back(process);else if(sta = "b")bl.push_back(process);elsecout << "Error!" << en dl;cout <<"AAAAAAAAAAAAAAAAAAAAAAAAAAAAA"<< en dl;cout << en dl; showPCB(); return 0;int showPCB() int i;cout << "runnin g:&quo

9、t;for(i=0; i<ru.size(); i+)cout << rui. name <<cout << en dl;cout << "ready:"for(i=0; i<re.size(); i+)cout << << ","cout << en dl;cout << "blocked:"for(i=0; i<bl.size(); i+)cout << <<

10、 ","cout << en dl;return 0;int ruTOre()if(!ru.empty() /runnin gQueue is being used.re.push_back(ru.fr on t();/runnin g's first process go to ready'lastru.erase(ru.begi n();/delete runnin g's first processru.push_back(re .fron t();re.erase(re.begi n();elsecout << &qu

11、ot;Error in ruTOre" << en dl;showPCB();return 0;int ruTObl()if(!ru.empty() /runnin gQueue is being used.bl.push_back(ru .fron t();ru.erase(ru.begi n();if(!re.empty()ru.push_back(re .fron t();re.erase(re.begi n();else elsecout << "Error in ruTObl2." << endl;showPCB();

12、return 0;int blTOre()if(!bl.empty() /blockedQueue is not empty.re.push_back(bl.fr on t();bl.erase(bl.begi n();if(ru.empty() /runnin gQueue is empty,the n ready->r unning ru.push_back(re .fron t();re.erase(re.begi n();elsecout << "Error in blTOre" << en dl;showPCB();return 0;

13、int neTOre()int i;cout << "Please en ter processes n ames and their status." << en dl; cout << en dl;Pro process;char n am;string sta;cout << "Please en ter processes n ames." << en dl;cin >> n am;process .n ame = nam;process.status = "r2&

14、quot;re.push_back(process);cout <<"AAAAAAAAAAAAAAAAAAAAAAAAAAAAA"<< en dl;if(ru.empty()ru.push_back(re .fron t(); re.erase(re.begi n();showPCB();return 0;int ruTOex()if(!ru.empty()/runnin gQueue is being used.ru.erase(ru.begi n();if(!re.empty()ru.push_back(re .fron t(); re.eras

15、e(re.begi n();elsecout << "Error in ruTOex1." << en dl;elsecout << "Error in ruTOex2." << endl;showPCB();return 0;int mai n()int act; /choose acti onhelloUI();cout << "Please in itialize the process." << en dl; ini Q();while(1)cout &l

16、t;<"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"<< en dl;cout << "Please select the action to take." << en dl;cout << "2:r unnin g->ready" << en dl; cout << "3:r unnin g->blocked" << en dl; cout << "4:blocked-&g

17、t;ready" << en dl; cout << "5:n ew->ready" << en dl;cout << "6:r unnin g->exit" << en dl;cin >> act;if(act = 2)ruTOre();else if(act = 3)ruTObl();else if(act = 4)blTOre();else if(act = 5)n eTOre();else if(act = 6)ruTOex();elsecout <

18、;< "Error in select."<<e ndl;cout << "#" << endl;cout << en dl;return 0;拓展點(diǎn)：五狀態(tài)模型四、實(shí)驗(yàn)結(jié)果(截圖)創(chuàng)建進(jìn)程：狀態(tài)runningready狀態(tài)runningblocked：狀態(tài)blockedready創(chuàng)建新進(jìn)程：情況一有進(jìn)程正在運(yùn)行情況二無(wú)進(jìn)程正在運(yùn)行終止進(jìn)程：實(shí)驗(yàn)三進(jìn)程同步和通信一、實(shí)驗(yàn)?zāi)康恼{(diào)試、修改、運(yùn)行模擬程序，通過(guò)形象化的狀態(tài)顯示，使學(xué)生理解進(jìn)程的概念，了解同步和通信 的過(guò)程，掌握進(jìn)程通信和同步的機(jī)制，特別是利用

19、緩沖區(qū)進(jìn)行同步和通信的過(guò)程。通過(guò)補(bǔ)充新功 能，使學(xué)生能靈活運(yùn)用相關(guān)知識(shí)，培養(yǎng)創(chuàng)新能力。、實(shí)驗(yàn)原理假定緩沖區(qū)可以容納8個(gè)數(shù)據(jù)；因?yàn)榫彌_區(qū)是有限的，因此當(dāng)其滿(mǎn)了時(shí)生產(chǎn)者進(jìn)程應(yīng)該等待；當(dāng)消費(fèi)者取走一個(gè)數(shù)據(jù)后,應(yīng)喚醒正在等待的生產(chǎn)者進(jìn)程；當(dāng)緩沖區(qū)空時(shí)，消費(fèi)者進(jìn)程應(yīng)該等待；當(dāng)生產(chǎn)者向緩沖區(qū)放入了一個(gè)數(shù)據(jù)時(shí)，應(yīng)喚醒正在等待的消費(fèi)者進(jìn)程。這就是生產(chǎn)者和消費(fèi)者之間的同步 三、實(shí)驗(yàn)內(nèi)容（源碼、注釋、基礎(chǔ)內(nèi)容、擴(kuò)展點(diǎn)等）基礎(chǔ)內(nèi)容：編寫(xiě)程序使其模擬兩個(gè)進(jìn)程，即生產(chǎn)者（producer）進(jìn)程和消費(fèi)者（Consumer）進(jìn)程工作；生產(chǎn)者每次產(chǎn)生一個(gè)數(shù)據(jù)，送入緩沖區(qū)中；消費(fèi)者每次從緩沖區(qū)中取走一個(gè)數(shù)據(jù)。每次寫(xiě)入和讀出數(shù)據(jù)

20、時(shí)，都將讀和寫(xiě)指針加一。當(dāng)指針到達(dá)緩沖區(qū)尾，重新將指針退回起點(diǎn);/*/*PROGRAM NAME:PRODUCER CONSUMER*/*This program simulates two processes, producer which*/*/* continuesto produce message and put it into a buffer /* impleme nted by PIPE, and con sumer which continues to get */*/* message from the buffer and use it./*The program als

21、o dem on strates the synchronism betwee n*/*/* processes and uses of PIPE./*/#in clude<stdio.h>#in clude<stdlib.h>#in clude <time.h> #defi ne PIPESIZE 8 #defi ne PRODUCER 0#defi ne CONSUMER 1#defi ne RUN/* statu of process */#defi ne WAIT/* statu of process */#defi ne READY/* statu

22、 of process */#defi ne NORMAL #defi ne SLEEP #defi ne AWAKE #in clude <stdio.h> /Process Con trol blockstruct pcb char *n ame;int statu; int time;/* times of execution */Buffer/typestruct pipetype char type;int writeptr;/Write poin terint readptr;/Read poin terstruct pcb *po intp;/* write wait

23、 point*/struct pcb *po intc; /* read wait point*/in t pipePIPESIZE;/Buffer arraystruct pipetype pipetb;struct pcb process2;nu mber of producer - nu mber of con sumer,buffer. count >= 8:too many prodecers; <=0:too many con sumersint coun t=0;int coun tp=0,co un tr=0;main ()int output,ret,i;/out

24、put- >nu mber of times, ret->prese nt statuschar in 2;int run p(),r un c(),pr n();pipetb.type = 'c' pipetb.writeptr = 0; pipetb.readptr = 0;pipetb.po intp = pipetb.po intc = NULL;processPRODUCER. name = "Producer、。"；processCONSUMER. name = "Con sumer0"processPRODUCE

25、R.statu = processCONSUMER.statu = READY;processPRODUCER.time = processCONSUMER.time = 0;output = 0;prin tf("Now starti ng the program!n");printf(" Press 'p1' to run PRODUCER1, press 'p2' to run PRODUCER2.n press 'c' to run CONSUMER.n");/PRODUCER1->produ

26、ct 1 new data, PRODUCER2->product 2 new dataprintf(” Press 'e' to exit from the program.n");for(i=0;i<1000;i+)in 0='N'while(i n0='N')sca nf("%s",i n);/whe n not p,c,e con ti nueif(in 0!='e'&&in 0!='p'&&in 0!='c')in

27、0='N：/producer and readyif(in 0='p'&&processPRODUCER.statu=READY)if(i n1 = 2)/producedint m;for(m=0;m<2;m+)if(co untp > 3)/the nu mber of waitti ng producer over 4,waitqueue=4prin tf("wro ng!n");con ti nue;if(cou nt<8)/output = ran d()%99+1;099output = (output+

28、1)%100;if(ret=ru np(output,process,pipe, &pipetb,PRODUCER)=SLEEP) /sleep,set write wait poin terpipetb.poi ntp = &processPRODUCER;if(ret=AWAKE)awake,execute con sumer(pipetb.poi ntc)->statu=READY;run c(process,pipe,&pipetb,CONSUMER); coun tr-;prin tf("co un tr=%dn",co untr);

29、if(co un tr=0) pipetb.po in tc=NULL;else if(i n1 = '1') /producer1if(coun tp > 3)prin tf("wro ng!n");con ti nue;if(cou nt<8)/output = ran d()%99+1;099output = (output+1)%100;/sleepif(ret=ru np(output,process,pipe,&pipetb,PRODUCER)=SLEEP)pipetb.poi ntp = & processPRODU

30、CER;if(ret=AWAKE)/awake(pipetb.poi ntc)->statu=READY;run c(process,pipe, &pipetb,CONSUMER);coun tr-;prin tf("co un tr=%dn",co un tr);if(co un tr=0)pipetb.po in tc=NULL;if(in 0='c'&&processCONSUMER.statu=READY)/con sumer and readyif(ret=ru nc(process,pipe, &pipetb

31、,CONSUMER)=SLEEP) /sleeppipetb.poi ntc = &processCONSUMER;if(ret=AWAKE) /awake(pipetb.poi ntp)->statu=READY;output=(output+1)%100;run p(output,process,pipe，& pipetb,PRODUCER);coun tp-;prin tf("co un tp=%dn",co un tp);if(co un tp=0)pipetb.po in tp=NULL;if(in 0='p'&&am

32、p;processPRODUCER.statu=WAIT)/producer and waitif(i n1 = 2)/producedint m;for(m=0;m<2;m+)if(coun tp > 3)prin tf("wro ng!n ”);printf("PRODUCER is waiting, can't be scheduled.n”);con ti nue;coun tp+;prin tf("co un tp=%dn",co un tp);else if(i n1 = '1')/producedif(c

33、oun tp > 3)prin tf("wro ng!in");printf("PRODUCER is waiting, can't be scheduled.n");con ti nue;coun tp+;prin tf("co un tp=%dn",co un tp);prin tf("Look out.n");/printf("PRODUCER is waiting, can't be scheduled.n");if(in 0='c'&&am

34、p;processCONSUMER.statu=WAIT)/con sumer and waitif(co untr > 3)prin tf("wro ng!in");printf("CONSUMER is waiting, can't be scheduled.n");con ti nue;coun tr+;prin tf("co un tr=%dn",co untr);prin tf("Look out!n");/printf("CONSUMER is waiting, can'

35、t be scheduled.'n");if(i n0='e') exit(1);prn( process,pipe,pipetb); in0 ='N：run p(out,p,pipe,tb,t) /* run producer */ int out,pipe,t;struct pcb p;struct pipetype *tb;pt.statu=RUN;",out);/buffer over 8prin tf("run PRODUCER. product %dif(co un t>=8)pt.statu=WAIT; retu

36、rn(SLEEP);/only has 01234567tb->writeptr=tb->writeptr%8;pipetb->writeptr=out; /cha nge tb->writeptr+;prin tf("writeptr%dn",tb->writeptr);coun t+;prin tf("co un t=%dn",co un t); pt.time+;/prin tf("time+%dn",pt.time); pt.statu=READY;if(tb->poi ntc)!=NULL

37、)/printf("返回 AWAKE"); return(AWAKE); return(NORMAL);run c(p,pipe,tb,t) in t pipe,t; struct pcb p; struct pipetype *tb; int c;/* run con sumer */pt.statu = RUN;/buffer too lessprin tf("r un CONSUMER.");if(coun t<=0)pt.statu=WAIT; return(SLEEP);c=pipetb_>readptr; pipetb_>r

38、eadptr=O; tb_>readptr+; tb->readptr=tb->readptr%8;prin tf("readptr=%dn",tb->readptr); printf(” use %d",c);coun t-;prin tf("co un t=%dn",co un t); pt.time+;/prin tf("time+%dn",pt.time); pt.statu=READY;if(tb->poi ntp!=NULL)/printf(” 返回 AWAKE'n"

39、;); return(AWAKE);return(NORMAL);prn(p,pipe,tb)in t pipe;struct pipetype tb;struct pcb p;int i;prin tf("n");for(i=0;i<PIPESIZE;i+)printf(”");I")；prin tf("n/pipe in sidefor(i=0;i<PIPESIZE;i+)if(pipei!=O)pipei has someth ingelseprintf("%2d|",pipei);printf("

40、;I")；prin tf("n");for(i=0;i<PIPESIZE;i+)printf("");prin tf("nwriteptr = %d, readptr = %d, ",tb.writeptr,tb.readptr);if(pPRODUCER.statu=WAIT )| cou ntp>=1)nu mber of producer >=1elseprin tf("%d PRODUCER wait ",co un tp);prin tf("PRODUCER read

41、y ");if(pCONSUMER.statu=WAIT)|cou ntr>=1)prin tf("%d CONSUMER wait ",cou ntr);elseprin tf("CONSUMER ready ");prin tf("n");prin tf("n# n");拓展點(diǎn)：設(shè)置了等待隊(duì)列的長(zhǎng)度，并顯示等待隊(duì)列內(nèi)部情況四、實(shí)驗(yàn)結(jié)果（截圖）生產(chǎn)者:情況一正常生產(chǎn)情況二超過(guò)緩沖區(qū)情況三超過(guò)等待隊(duì)列消費(fèi)者:情況一正常情況二無(wú)產(chǎn)品可消費(fèi)又開(kāi)始生產(chǎn): 實(shí)驗(yàn)四進(jìn)程的管道通信、實(shí)驗(yàn)?zāi)康?加深對(duì)進(jìn)程概念的理

42、解，明確進(jìn)程和程序的區(qū)別；學(xué)習(xí)進(jìn)程創(chuàng)建的過(guò)程，進(jìn)一步認(rèn)識(shí)并發(fā)執(zhí)行的實(shí)質(zhì)；分析進(jìn)程爭(zhēng)用資源的現(xiàn)象，學(xué)習(xí)解決進(jìn)程互斥的方法；學(xué)習(xí)解決進(jìn)程同步的方法；掌握Linux系統(tǒng)進(jìn)程間通過(guò)管道通信的具體實(shí)現(xiàn)方法。二、實(shí)驗(yàn)原理1. 基本概念：進(jìn)程的概念；進(jìn)程與程序的區(qū)別；并發(fā)執(zhí)行的概念進(jìn)程互斥的概念；進(jìn)程通信的基本原理2. 系統(tǒng)調(diào)用：設(shè)置系統(tǒng)調(diào)用號(hào)：設(shè)置多條系統(tǒng)調(diào)用命令，并賦予每條系統(tǒng)調(diào)用命令一個(gè)唯一的系統(tǒng)調(diào)用號(hào)處理系統(tǒng)調(diào)用：OS中有一張系統(tǒng)調(diào)用入口表，表中每個(gè)表目對(duì)應(yīng)一條系統(tǒng)調(diào)用命令，包含該系統(tǒng)調(diào)用自帶參數(shù)的數(shù)目、系統(tǒng)調(diào)用命令處理程序的入口地址等。OS內(nèi)核便是根據(jù)所輸入的系統(tǒng)調(diào)用號(hào)在該表中查找到相應(yīng)的系統(tǒng)調(diào)用

43、，進(jìn)而轉(zhuǎn)入它的入口地址去執(zhí)行系統(tǒng)調(diào)用程序。Linux的系統(tǒng)調(diào)用機(jī)制：通過(guò)中斷機(jī)制實(shí)現(xiàn)三、實(shí)驗(yàn)內(nèi)容(源碼、注釋、基礎(chǔ)內(nèi)容、擴(kuò)展點(diǎn)等)#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <uni std.h>#in elude <sys/types.h>#in clude <sys/wait.h>int mai n()in t pid1,pid2,pid3;int fd2;char outpipe50,i npipe50;pipe(fd);while (pid 1= fork() = -1);

44、if(pid1 = 0)prin tf("s1n");lockf(fd1,1,0);/prin tf("s11 n");spri ntf(outpipe,"l am the 1st!"); write(fd1,outpipe,50); sleep (3);lockf(fd1,0,0);/sleep (2);exit(0);elsewhile(pid2=fork() = -1);if(pid2 = 0)prin tf("s2n ”);/if(pid1 != 0)/wait(0);/prin tf("s22n"

45、;);lockf(fd1,1,0);/prin tf("f1");spri ntf(outpipe,"l am the 2nd!");write(fd1,outpipe,50);sleep(2);lockf(fd1,0,0);/sleep(2); exit(0);elsewhile(pid3=fork() = -1);if (pid3 = 0)prin tf("s3n");lockf(fd1,1,0);spri ntf(outpipe,"l am the 3rd!"); write(fd1,outpipe,50);

46、 sleep(2);lockf(fd1,0,0);exit(O);elsewait(O);read(fdO,i npipe,50);prin tf("%s n",i npipe);/prin tf("f1");wait(0);read(fd0,i npipe,50);/prin tf("f2");prin tf("%s n",i npipe);wait(0);read(fd0,i npipe,50);prin tf("%s n",i npipe);exit(0);return 0;四、實(shí)驗(yàn)結(jié)果(

47、截圖) 三次運(yùn)行順序不同： 實(shí)驗(yàn)五頁(yè)面置換算法一、實(shí)驗(yàn)?zāi)康倪M(jìn)一步理解父子進(jìn)程之間的關(guān)系理解內(nèi)存頁(yè)面調(diào)度的機(jī)理掌握頁(yè)面置換算法的實(shí)現(xiàn)方法 通過(guò)實(shí)驗(yàn)比較不同調(diào)度算法的優(yōu)劣 培養(yǎng)綜合運(yùn)用所學(xué)知識(shí)的能力頁(yè)面置換算法是虛擬存儲(chǔ)管理實(shí)現(xiàn)的關(guān)鍵，通過(guò)本次試驗(yàn)理解內(nèi)存頁(yè)面調(diào)度的機(jī)制，在模擬 實(shí)現(xiàn)FIFO、LRU等經(jīng)典頁(yè)面置換算法的基礎(chǔ)上，比較各種置換算法的效率及優(yōu)缺點(diǎn)，從而了解 虛擬存儲(chǔ)實(shí)現(xiàn)的過(guò)程。將不同的置換算法放在不同的子進(jìn)程中加以模擬，培養(yǎng)綜合運(yùn)用所學(xué)知識(shí) 的能力。二、實(shí)驗(yàn)原理1. FIF0算法：FIFO表示先進(jìn)先出，類(lèi)似于對(duì)列，在數(shù)據(jù)的結(jié)構(gòu)上使用對(duì)列來(lái)實(shí)現(xiàn)。結(jié)構(gòu)圖：（1） 新訪(fǎng)問(wèn)的數(shù)據(jù)插入FIFO隊(duì)列

48、尾部，數(shù)據(jù)在 FIFO隊(duì)列中順序移動(dòng)；（2）淘汰FIFO隊(duì)列頭部的數(shù)據(jù)；2. LRU算法：LRU表示很少使用算法，其核心思想是“如果數(shù)據(jù)最近被訪(fǎng)問(wèn)過(guò)，那么將來(lái)被訪(fǎng)問(wèn) 的幾率也更高。最常見(jiàn)的實(shí)現(xiàn)是使用一個(gè)鏈表保存緩存數(shù)據(jù)，結(jié)構(gòu)圖如下：（1）新數(shù)據(jù)插入到鏈表頭部；（2）每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪(fǎng)問(wèn)），則將數(shù)據(jù)移到鏈表頭部；（3）當(dāng)鏈表滿(mǎn)的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄。三、實(shí)驗(yàn)內(nèi)容（源碼、注釋、基礎(chǔ)內(nèi)容、擴(kuò)展點(diǎn)等）#i nclude <stdio.h>#i nclude <stdlib.h>#in clude <time.h>#in clude <sys/t

49、ypes.h>#i nclude <sys/stat.h>#in clude <error.h>#in clude <wait.h>#in clude <uni std.h>#defi ne total_i nstruction 20/Tatal Page Hits/LRUint LRU（i nt Acess_series）int M_Frame3; /memoryint M3; /Record whether memory is hitedfloat diseffect = 0;int p = 0; /p->where to use

50、/in itialize memoryfor （int i = 0; i < 3; i+）M_Framei = 0;Mi = 0;/sleep （2）;prin tf（" n Start LRU!n ”）;for （int i = 0; i < total_ in struct ion; i+）/All empty if (p = 0)M_FrameO = Acess_seriesi; diseffect+;P+；2 emptyelse if (p = 1)0->hitif (M_FrameO = Acess_seriesi)M0 = -1;/page faulte

51、lseM_Frame1 = Acess_seriesi; diseffect+;p+;1 emptyelse if (p = 2)0->hitif (M_Frame0 = Acess_seriesi)M_Frame0 = M_Frame1;M_Frame1 = Acess_seriesi; M0 = -1;1->hitelse if (M_Frame1 = Acess_seriesi)M1 = -1;/page faultelseM_Frame2 = Acess_seriesi; diseffect+;p+;/all usedelse0->hitif (M_FrameO =

52、Acess_seriesi)M_Frame0 = M_Frame1;M_Frame1 = M_Frame2;M_Frame2 = Acess_seriesi; M0 = -1;1->hitelse if (M_Frame1 = Acess_seriesi) M_Frame1 = M_Frame2;M_Frame2 = Acess_seriesi; M1 = -1;2->hitelse if (M_Frame2 = Acess_seriesi)M2 = -1;/page faultelseM_Frame0 = M_Frame1;M_Frame1 = M_Frame2;M_Frame2

53、 = Acess_seriesi; diseffect+;/print memoryprin tf("|");for (i nt j = 0; j < 3; j+)printf(" %d |", M_Framej);Mj+;/judge whether hitif (M0 && M1 && M2)prin tf(" page fault");elseprin tf(”hit");prin tf("n");printf("The Page fault Rate

54、 is:%f. n", diseffect/total_instruction);prin tf("The Hit Rate is:%f. n", 1-diseffect/total_i nstructio n); return 0;/FIFOint FIFO3(i nt Acess_series)int M_Frame3; /memoryint M = 0; /Record whether memory is hitedfloat diseffect = 0;int p = 0;p->where to use/in itialize memoryfor (

55、int i = 0; i < 3; i+)M_Framei = 0;/sleep (2);prin tf(" n Start FIFO!n");for (int i = 0; i < total_ in struct ion; i+)/all emptyif (p = 0)M_Frame0 = Acess_seriesi;diseffect+;p+;/2 emptyelse if (p = 1)/page faultif (M_Frame0 != Acess_seriesi)M_Frame1 = Acess_seriesi; diseffect+;p+;/hit

56、 elseM = 1;11l emptyelse if (p = 2)/hitif (M_FrameO = Acess_seriesi |M_Frame1 = Acess_seriesi)M = 1;/page faultelseM_Frame2 = Acess_seriesi; diseffect+;P+；/all usedelse/hitif (M_Frame0 = Acess_seriesi |M_Frame1 = Acess_seriesi |M_Frame2 = Acess_seriesi) M = 1;/page faultelseM_Frame0 = M_Frame1;M_Frame1 = M_Frame2;M_Frame2 = Acess_seriesi; diseffect+;/print memoryprin tf("|");for (i nt j = 0; j < 3; j+)printf(” %d |", M_Framej);/judge whether hitif (M = 1)prin tf("hit");M = 0;elseprintf(" page fault");prin tf(&qu