實(shí)驗(yàn)三 存儲(chǔ)管理實(shí)驗(yàn)

實(shí)驗(yàn)三存儲(chǔ)管理實(shí)驗(yàn)一.

目的要求：

1、通過編寫和調(diào)試存儲(chǔ)管理的模擬程序以加深對(duì)存儲(chǔ)管理方案的理解。熟悉虛存管理的各種頁面淘汰算法。

2、通過編寫和調(diào)試地址轉(zhuǎn)換過程的模擬程序以加強(qiáng)對(duì)地址轉(zhuǎn)換過程的了解。二.例題

設(shè)計(jì)一個(gè)請(qǐng)求頁式存儲(chǔ)管理方案。并編寫模擬程序?qū)崿F(xiàn)之。產(chǎn)生一個(gè)需要訪問的指令地址流。它是一系列需要訪問的指令的地址。為不失一般性，你可以適當(dāng)?shù)兀ㄓ萌斯ぶ付ǖ胤椒ɑ蛴秒S機(jī)數(shù)產(chǎn)生器）生成這個(gè)序列，使得50％的指令是順序執(zhí)行的。25％的指令均勻地散布在前地址部分，25％的地址是均勻地散布在后地址部分。為簡單起見。頁面淘汰算法采用FIFO頁面淘汰算法，并且在淘汰一頁時(shí)，只將該頁在頁表中抹去。而不再判斷它是否被改寫過，也不將它寫回到輔存。

具體的做法可以是：產(chǎn)生一個(gè)需要訪問的指令地址流；指令合適的頁面尺寸（例如以1K或2K為1頁）；指定內(nèi)存頁表的最大長度，并對(duì)頁表進(jìn)行初始化；每訪問一個(gè)地址時(shí)，首先要計(jì)算該地址所在的頁的頁號(hào)，然后查頁表，判斷該頁是否在主存——如果該頁已在主存，則打印頁表情況；如果該頁不在主存且頁表未滿，則調(diào)入一頁并打印頁表情況；如果該頁不足主存且頁表已滿，則按FIFO頁面淘汰算法淘汰一頁后調(diào)入所需的頁，打印頁表情況；逐個(gè)地址訪問，直到所有地址訪問完畢。存儲(chǔ)管理算法的流程圖如下：三.

實(shí)驗(yàn)題：1、設(shè)計(jì)一個(gè)固定式分區(qū)分配的存儲(chǔ)管理方案，并模擬實(shí)現(xiàn)分區(qū)的分配和回收過程?？梢约俣總€(gè)作業(yè)都是批處理作業(yè)，并且不允許動(dòng)態(tài)申請(qǐng)內(nèi)存。為實(shí)現(xiàn)分區(qū)的分配和回收，可以設(shè)定一個(gè)分區(qū)說明表，按照表中的有關(guān)信息進(jìn)行分配，并根據(jù)分區(qū)的分配和回收情況修改該表。#include<stdio.h>#include<math.h>#include<stdlib.h>#defineNUM4#definealloMemory(type)(type*)malloc(sizeof(type))structpartiTab{intno;intsize;intfirstAddr;charstate;}parTab[NUM];typedefstructpartiTabPARTITAB;typedefstructjcb{/*定義作業(yè)控制塊JCB,部分信息省略*/charname[10];//作業(yè)名intsize;//作業(yè)大小structjcb*link;//鏈指針}JCB;typedefstruct{JCB*front,*rear;}jcbQue;jcbQue*jcbReadyQue;voidAllocateMemory(intsize);voidcreateTab();voidcheckTab();voidrecycleMemory(inti);voidAllocateMemory(intsize){for(inti=0;i<NUM;i++){PARTITABp=parTab[i];if(p.state='N'&&p.size>size)parTab[i].state='Y';elseprintf("沒有空閑分區(qū)，無法分配內(nèi)存！\n");}}voidcreateTab(){for(inti=1;i<=NUM;i++)//getPartiTab(PARTITAB);{parTab[i-1].no=i;parTab[i-1].size=20;parTab[i-1].firstAddr=21;parTab[i-1].state='N';}}voidcheckTab(){printf("分區(qū)號(hào)\t大小\t起址\t狀態(tài)\n");for(inti=0;i<NUM;i++){printf("%d\t",parTab[i].no);printf("%d\t",parTab[i].size);printf("%d\t",parTab[i].firstAddr);printf("%c\t",parTab[i].state);printf("\n");}}voidrecycleMemory(inti){parTab[i-1].state='N';}intmain(intargc,char*argv[]){createTab();checkTab();printf("請(qǐng)按任意鍵繼續(xù)：\n");getchar();printf("每個(gè)分區(qū)裝入一道作業(yè)：\n");for(inti=0;i<NUM;i++){AllocateMemory((i+1)*3);}checkTab();printf("請(qǐng)按任意鍵繼續(xù)：\n");getchar();printf("假如一段時(shí)間后，其中一個(gè)作業(yè)結(jié)束，回收給它分配的分區(qū)(假如該作業(yè)在第2分區(qū))\n");recycleMemory(2);checkTab();printf("請(qǐng)按任意鍵繼續(xù)：\n");getchar();printf("接著,從外存后備作業(yè)隊(duì)列中選擇一個(gè)作業(yè)裝入該分區(qū)(假如該作業(yè)大小為10)\n");AllocateMemory(10);checkTab();return0;}

2、設(shè)計(jì)一個(gè)可變式分區(qū)分配的存儲(chǔ)管理方案。并模擬實(shí)現(xiàn)分區(qū)的分配和回收過程。對(duì)分區(qū)的管理法可以是下面三種算法之一：首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法首次適應(yīng)算法:運(yùn)行情況#include<iostream>#include<stdio.h>#include<stdlib.h>#include<math.h>#defineFree0//空閑狀態(tài)#defineBusy1//已用狀態(tài)#defineOK1//完成#defineERROR0//出錯(cuò)#defineMAX_length640//最大內(nèi)存空間為640KBtypedefintStatus;usingnamespacestd;typedefstructfreearea//定義一個(gè)空閑區(qū)說明表結(jié)構(gòu){intID;//分區(qū)號(hào)longsize;//分區(qū)大小longaddress;//分區(qū)地址intstate;//狀態(tài)}ElemType;//線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)typedefstructDuLNode//doublelinkedlist{ElemTypedata;structDuLNode*prior;//前趨指針structDuLNode*next;//后繼指針}DuLNode,*DuLinkList;DuLinkListblock_first;//頭結(jié)點(diǎn)DuLinkListblock_last;//尾結(jié)點(diǎn)Statusalloc(int);//內(nèi)存分配Statusfree(int);//內(nèi)存回收StatusFirst_fit(int,int);//首次適應(yīng)算法StatusBest_fit(int,int);//最佳適應(yīng)算法voidshow();//查看分配StatusInitblock();//開創(chuàng)空間表StatusInitblock()//開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表{block_first=(DuLinkList)malloc(sizeof(DuLNode));block_last=(DuLinkList)malloc(sizeof(DuLNode));block_first->prior=NULL;block_first->next=block_last;block_last->prior=block_first;block_last->next=NULL;block_last->data.address=0;block_last->data.size=MAX_length;block_last->data.ID=0;block_last->data.state=Free;returnOK;}//分配主存Statusalloc(intch){intID,request;cout<<"請(qǐng)輸入作業(yè)(分區(qū)號(hào))：";cin>>ID;cout<<"請(qǐng)輸入需要分配的主存大小(單位:KB)：";cin>>request;if(request<0||request==0){cout<<"分配大小不合適，請(qǐng)重試！"<<endl;returnERROR;}if(ch==2)//選擇最佳適應(yīng)算法{if(Best_fit(ID,request)==OK)cout<<"分配成功！"<<endl;elsecout<<"內(nèi)存不足，分配失??！"<<endl;returnOK;}else//默認(rèn)首次適應(yīng)算法{if(First_fit(ID,request)==OK)cout<<"分配成功！"<<endl;elsecout<<"內(nèi)存不足，分配失??！"<<endl;returnOK;}}//首次適應(yīng)算法StatusFirst_fit(intID,intrequest)//傳入作業(yè)名及申請(qǐng)量{//為申請(qǐng)作業(yè)開辟新空間且初始化DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode*p=block_first->next;while(p){if(p->data.state==Free&&p->data.size==request)//有大小恰好合適的空閑塊{p->data.state=Busy;p->data.ID=ID;returnOK;break;}if(p->data.state==Free&&p->data.size>request)//有空閑塊能滿足需求且有剩余"{temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;returnOK;break;}p=p->next;}returnERROR;}//最佳適應(yīng)算法StatusBest_fit(intID,intrequest){intch;//記錄最小剩余空間DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode*p=block_first->next;DuLNode*q=NULL;//記錄最佳插入位置while(p)//初始化最小空間和最佳位置{if(p->data.state==Free&&(p->data.size>request||p->data.size==request)){{{q=p;ch=p->data.size-request;break;}p=p->next;}while(p){if(p->data.state==Free&&p->data.size==request)//空閑塊大小恰好合適p->data.ID=ID;p->data.state=Busy;returnOK;break;}if(p->data.state==Free&&p->data.size>request)//空閑塊大于分配需求if(p->data.size-request<ch)//剩余空間比初值還小{ch=p->data.size-request;//更新剩余最小值q=p;//更新最佳位置指向}}p=p->next;}if(q==NULL)returnERROR;//沒有找到空閑塊else//找到了最佳位置并實(shí)現(xiàn)分配{temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;returnOK;}}//主存回收Statusfree(intID){DuLNode*p=block_first;while(p){{if(p->data.ID==ID){p->data.state=Free;p->data.ID=Free;if(p->prior->data.state==Free)//與前面的空閑塊相連{p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;}if(p->next->data.state==Free)//與后面的空閑塊相連{p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;}break;}p=p->next;}returnOK;}}//顯示主存分配情況voidshow(){cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++主存分配情況+++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n";DuLNode*p=block_first->next;while(p){cout<<"分區(qū)號(hào)：";if(p->data.ID==Free)cout<<"Free"<<endl;elsecout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address<<endl;cout<<"分區(qū)大?。?<<p->data.size<<"KB"<<endl;cout<<"狀態(tài)：";if(p->data.state==Free)cout<<"空閑"<<endl;elsecout<<"已分配"<<endl;cout<<"——————————————"<<endl;p=p->next;}}//主函數(shù)intmain(){intch;//算法選擇標(biāo)記cout<<"動(dòng)態(tài)分區(qū)分配方式的模擬\n";cout<<"1)首次適應(yīng)算法\n2)最佳適應(yīng)算法\n";cout<<"請(qǐng)選擇分配算法：";cin>>ch;Initblock();//開創(chuàng)空間表intchoice;//操作選擇標(biāo)記while(1){cout<<"1:分配內(nèi)存\n2:回收內(nèi)存\n";cout<<"3:查看分配\n0:退出\n";cout<<"請(qǐng)輸入您的操作：";cin>>choice;if(choice==1)alloc(ch);//分配內(nèi)存elseif(choice==2)//內(nèi)存回收{(diào)intID;cout<<"請(qǐng)輸入您要釋放的分區(qū)號(hào)：";cin>>ID;free(ID);}elseif(choice==3)show();//顯示主存elseif(choice==0)break;//退出else//輸入操作有誤{cout<<"輸入有誤，請(qǐng)重試！"<<endl;continue;}}}

3、編寫并調(diào)試一個(gè)段頁式存儲(chǔ)管理的地址轉(zhuǎn)換的模擬程序。首先設(shè)計(jì)好段表、頁表，然后給出若干個(gè)有一定代表性的地址，通過查找段表頁表后得到轉(zhuǎn)換的地址。要求打印轉(zhuǎn)換前的地址，相應(yīng)的段表，頁表?xiàng)l款及轉(zhuǎn)換后的地址，以便檢查。#include<iostream>#include<string>usingnamespacestd;typedefstructQuick{intqs;//快表段號(hào)intqp;//快表頁號(hào)intqb;//快表段號(hào)}Quick;typedefstructData{intnum;//內(nèi)存的塊數(shù)stringstr;//對(duì)應(yīng)數(shù)據(jù)塊的作業(yè)內(nèi)容，簡化起見說明內(nèi)容為一串字符。}Data;//頁表typedefstructPage{intnum;//頁號(hào)intflag;//頁狀態(tài)，即是否在內(nèi)存。intblock;//該頁對(duì)應(yīng)的塊號(hào)}Page;typedefstructStack{intnum;//段號(hào)intflag;//段狀態(tài)intplen;//頁表長度intpsta;//頁表始址}Stack;//段表寄存器typedefstructStare{intssta;//段表始址intslen;//段表長度}Stare;Stackss[10];////全局變量Starest;///////全局變量Datawork[20];//全局變量Quickqu;//////全局變量Pagepage[5][5];boolmenuflag=0;intbbs;//內(nèi)存塊大小intbs;//內(nèi)存大小voidmenu();voidstart();voidchange();intmain(){menu();return0;}voidmenu(){cout<<"請(qǐng)選擇:"<<endl;cout<<endl;cout<<"1、初始化表"<<endl;cout<<"2、物理地址轉(zhuǎn)換"<<endl;cout<<"3、退出"<<endl;intmenu1;cin>>menu1;if(menu1!=1&&menu1!=2&&menu1!=3){cout<<"請(qǐng)輸入正確的選項(xiàng)"<<endl;menu();}switch(menu1){case1:{menuflag=1;start();break;}case2:{if(menuflag==0){cout<<"請(qǐng)初始化表"<<endl;menu();}change();break;}case3:return;}//switch}voidstart(){cout<<"請(qǐng)輸入內(nèi)存大小(K)"<<endl;cin>>bs;cout<<"請(qǐng)輸入內(nèi)存塊的大小(k)"<<endl;cin>>bbs;intblocknum;blocknum=bs/bbs;cout<<"內(nèi)存一共被分為"<<blocknum<<"塊，每塊"<<bbs<<"k"<<"一共"<<bs<<"k"<<endl;cout<<"請(qǐng)輸入進(jìn)程個(gè)數(shù)"<<endl;intpn;cin>>pn;//下面求所有進(jìn)程的總段數(shù)和段表,并為每段創(chuàng)建頁表intsums=0;for(intpn1=0;pn1<pn;pn1++){cout<<"請(qǐng)輸入第"<<pn1<<"個(gè)進(jìn)程的段數(shù)"<<endl;intppn;cin>>ppn;sums+=ppn;}for(intss1=0;ss1<sums;ss1++){cout<<"請(qǐng)輸入第"<<ss1<<"個(gè)段表數(shù)據(jù)：段號(hào)，狀態(tài)，頁表長度，頁表始址"<<endl;cin>>ss[ss1].num>>ss[ss1].flag>>ss[ss1].plen>>ss[ss1].psta;cout<<"請(qǐng)初始化第"<<ss1<<"段的頁表，輸入兩個(gè)數(shù)據(jù)頁表狀態(tài)和對(duì)應(yīng)塊號(hào)"<<endl;for(intsss1=0;sss1<ss[ss1].plen;sss1++){page[ss1][sss1].num=sss1;cout<<"請(qǐng)輸入該段第"<<sss1<<"個(gè)頁表的頁表狀態(tài)和對(duì)應(yīng)塊號(hào)"<<endl;cin>>page[ss1][sss1].flag>>page[ss1][sss1].block;}}//初始化段表寄存器cout<<"初始化段表寄存器的段表始址"<<endl;cin>>st.ssta;st.slen=sums;//初始化內(nèi)存中物理地址每一塊的數(shù)據(jù)區(qū)cout<<"簡單起見，我們對(duì)物理地址的每一塊用字符串進(jìn)行簡單的初始化，沒有具體到每一物理地址"<<endl;for(intbn=0;bn<blocknum;bn++){work[bn].num=bn;cout<<"請(qǐng)輸入第"<<bn<<"個(gè)內(nèi)存塊里的作業(yè)內(nèi)容"<<endl;cin>>work[bn].str;}//初始化快表cout<<"簡單起見，我們初始化快表只有一個(gè)"<<endl;cout<<"請(qǐng)輸入要作為快表的段號(hào)和頁號(hào)"<<endl;cin>>qu.qb>>qu.qp;while(ss[qu.qb].flag!=1||page[qu.qb][qu.qp].flag!=1){cout<<"該頁不在內(nèi)存請(qǐng)輸入一頁在內(nèi)存中的作為快表,請(qǐng)輸入要作為快表的段號(hào)和頁號(hào)"<<endl;cin>>qu.qb>>qu.qp;}qu.qs=page[qu.qb][qu.qp].block;menu();}voidchange(){cout<<"請(qǐng)輸入要轉(zhuǎn)化的邏輯地址，段號(hào)s，段內(nèi)頁號(hào)p，頁內(nèi)偏移地址d(B)"<<endl;intsnum,pnum,dnum;cin>>snum>>pnum>>dnum;//首先查快表if(snum==qu.qb&&pnum==qu.qp){cout<<"快表命中"<<"對(duì)應(yīng)塊號(hào)是"<<qu.qs<<endl;cout<<"該塊中作業(yè)數(shù)據(jù)是"<<work[page[qu.qb][qu.qp].block].str<<endl;cout<<"物理地址是"<<qu.qs*bbs*1024+dnum<<endl;;menu();}//訪問段表寄存器else{cout<<"快表沒有命中,訪問段表寄存器，段號(hào)等于段表始址加上偏移地址"<<endl;intssnum;ssnum=st.ssta+snum;if(ssnum>st.slen-1){