內(nèi)存分配,首次適應(yīng)算法

./實(shí)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)：存分配與回收二、實(shí)驗(yàn)容：用首次適應(yīng)算法實(shí)現(xiàn)存儲(chǔ)空間的分配,回收作業(yè)所占用的存儲(chǔ)空間。三、實(shí)驗(yàn)?zāi)康模阂粋€(gè)好的計(jì)算機(jī)系統(tǒng)不僅要有足夠的存儲(chǔ)容量,較高的存取速度和穩(wěn)定可靠的存儲(chǔ)器,而且能夠合理的分配和使用這些主存空間。當(dāng)用戶提出申請(qǐng)主存空間的要求時(shí),存儲(chǔ)管理能夠按照一定的策略分析主存的使用情況,找出足夠的空間分配給申請(qǐng)者；當(dāng)作業(yè)運(yùn)行完畢,存儲(chǔ)管理要回收作業(yè)占用的主存空間。本實(shí)驗(yàn)實(shí)現(xiàn)在可變分區(qū)存儲(chǔ)管理方式下,采用最先適應(yīng)算法對(duì)主存空間進(jìn)行分配和回收,以加深了解操作系統(tǒng)的存儲(chǔ)管理功能。實(shí)驗(yàn)過(guò)程：基本思想空閑分區(qū)鏈以地址遞增的次序連接。在分配存時(shí),從鏈?zhǔn)组_(kāi)始順序查找,直至找到一個(gè)大小能夠滿足要求的空閑分區(qū)為止；然后再按照作業(yè)大小,從該分區(qū)中劃出一塊存空間分配給請(qǐng)求者,余下的空閑分區(qū)仍然留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū),則此次存分配失敗。b>主要數(shù)據(jù)結(jié)構(gòu)typedefstructFreeLink{//空閑鏈 structFreeLink*prior; charname; intstart; intsize; boolflag; structFreeLink*next;}*ptr,*head;headtop;ptrp;c>存分配算法當(dāng)有進(jìn)程要求分配主存時(shí),依據(jù)首次適應(yīng)算法從鏈頭開(kāi)始,延鏈查找一個(gè)足以容納該進(jìn)程的空閑區(qū)。若這個(gè)分區(qū)比較大,則一分為二,一部分分配給進(jìn)程,另一部分作為空閑區(qū)仍留在鏈中的當(dāng)前位置,修改它的上一個(gè)空閑區(qū)的前向指針值為再加上分配給進(jìn)程的分區(qū)大小,下一個(gè)空閑區(qū)的后向指針值為再加上分配給進(jìn)程的分區(qū)大小,使鏈保持完整。若這個(gè)分區(qū)的大小正好等于進(jìn)程的大小,該分區(qū)全部分配給進(jìn)程,并將該空閑區(qū)從鏈中摘除〔即修改下一個(gè)空閑區(qū)的后向指針=該空閑區(qū)后向指針,上一個(gè)空閑區(qū)的前向指針=該空閑區(qū)的前向指針。再在已分配區(qū)表中找一個(gè)空表目,登記剛剛分配的存始址、長(zhǎng)度和進(jìn)程號(hào)。d>存的回收當(dāng)進(jìn)程運(yùn)行完成,釋放存時(shí),通過(guò)輸入進(jìn)程號(hào),來(lái)回收進(jìn)程占用的分區(qū)。在回收時(shí),釋放區(qū)與空閑區(qū)相鄰接的情況要考慮4種情況：⊙釋放區(qū)下鄰空閑區(qū)⊙釋放區(qū)上鄰空閑區(qū)⊙釋放區(qū)與上下空閑區(qū)均相鄰⊙釋放區(qū)與上下空閑區(qū)均不相鄰e>程序流程圖※空閑鏈的首次適應(yīng)算法分配流程圖開(kāi)始申請(qǐng)xkb內(nèi)存開(kāi)始申請(qǐng)xkb內(nèi)存由鏈頭找到第一個(gè)空閑區(qū)分區(qū)大小≥xkb？大于分區(qū)大小=分區(qū)大小-xkb,修改下一個(gè)空閑區(qū)的后向指針內(nèi)容為〔后向指針+xkb;修改上一個(gè)空閑區(qū)的前向指針為〔前向指針+xkb將該空閑區(qū)從鏈中摘除：修改下一個(gè)空閑區(qū)的后向地址=該空閑區(qū)后向地址,修改上一個(gè)空閑區(qū)的前向指針為該空閑區(qū)的前向指針等于小于延鏈查找下一個(gè)空閑區(qū)到鏈尾了？作業(yè)等待返回是否登記已分配表返回分配給進(jìn)程的內(nèi)存首地址※空閑鏈的首次適應(yīng)算法回收流程圖開(kāi)始開(kāi)始輸入完成進(jìn)程的標(biāo)號(hào)在分配區(qū)表中查找釋放區(qū)p下鄰分區(qū)空閑區(qū)前一個(gè)空閑區(qū)的后向指針指向p的后一個(gè)分區(qū),p的后一個(gè)分區(qū)的前向指針指向p的前一個(gè)分區(qū),且p的前一個(gè)分區(qū)大小更改為加上p的大小,釋放p釋放區(qū)p上鄰分區(qū)空前一個(gè)分區(qū)的后向指針指向p的后一個(gè)空閑分區(qū),p的后一個(gè)空閑分區(qū)的前向指針指向p的前一個(gè)分區(qū),且p的后一個(gè)分區(qū)大小更改為加上p的大小釋放區(qū)p上下均鄰空閑區(qū)前一個(gè)空閑區(qū)的后向指針指向p的后一個(gè)空閑分區(qū),p的后一個(gè)空閑分區(qū)的前向指針指向p的前一個(gè)空閑分區(qū),且p的前一個(gè)空閑分區(qū)大小更改為加上p的大小再加上p的后一個(gè)空閑分區(qū)的大小,合并后的這個(gè)空閑區(qū)的后向指針指向p的下下個(gè)分區(qū),如果p的下下個(gè)分區(qū)不為空,則其前向指針指向合并后的這個(gè)空閑區(qū),釋放p和p的下一個(gè)分區(qū)釋放區(qū)p上下均不鄰空閑區(qū)將p放在鏈?zhǔn)?并修改其狀態(tài)位為空閑f截屏五、源代碼#include<iostream.>#include<malloc.h>#include<stdlib.h>usingnamespacestd;typedefstructFreeLink{//定義空閑鏈 structFreeLink*prior; charname; intstart; intsize; boolflag; structFreeLink*next;}*ptr,*head;headtop;ptrp;voidprint<>{//將存分配情況打印到屏幕上 p=top; cout<<"************************存分配情況表************************"<<endl; cout<<"區(qū)號(hào)\t\t"<<"起始位置\t"<<"區(qū)間長(zhǎng)度\t"<<"區(qū)間狀態(tài)\t"<<endl;do{ cout<<p->name<<"\t\t"<<p->start<<"\t\t"<<p->size<<"\t\t"; if<p->flag==false>//flag為false,表明該分區(qū)空閑 { cout<<"空閑"<<endl; } else { cout<<"已占用"<<endl;} p=p->next; } while<p!=NULL>;}voidclear<>{//結(jié)束操作時(shí)清空"存"以備其他操作 do{ p=top; top=top->next; free<p>; } while<top!=NULL>; cout<<"存已清空！";}voidhebing<ptr&p>{//若被操作的存有相鄰空閑區(qū)則將空閑區(qū)拼接合并 intx; if<p->prior->flag==false&&p->next->flag==false>x=1;//釋放區(qū)與上下空閑區(qū)均相鄰 if<<p->prior->flag==false&&p->next->flag==true>||<p->prior->flag==false&&p->next==NULL>>x=2;//釋放區(qū)下鄰空閑區(qū) if<<p->prior->flag==true&&p->next->flag==false>||<p->prior==NULL&&p->next->flag==false>>x=3;//釋放區(qū)上鄰空閑區(qū) if<<p->prior->flag==true&&p->next->flag==true>||<p->prior==NULL&&p->next->flag==true>||<p->prior->flag==true&&p->next==NULL>>x=4;//釋放區(qū)與上下空閑區(qū)均不相鄰switch<x>{ case1:p->next->prior=p->prior; p->prior->next=p->next; p->prior->size=p->prior->size+p->size+p->next->size; p->prior->next=p->next->next; if<p->next->next!=NULL> p->next->next->prior=p->next->prior; free<p->next>;//釋放 free<p>; break;case2:if<p->next==NULL>//p為最后一個(gè)分區(qū) { p->prior->next=p->next; } else{ p->next->prior=p->prior; p->prior->next=p->next; } p->prior->size=p->prior->size+p->size; free<p>; break; case3:if<p->prior==NULL>//p為第一個(gè)分區(qū) { top=p->next; p->next->prior=NULL; p->next->start=p->start; p->next->size=p->next->size+p->size; } else{ p->next->prior=p->prior; p->prior->next=p->next; p->next->start=p->start; p->next->size=p->next->size+p->size; } free<p>; break; case4:p->name='*';//將釋放區(qū)移至鏈?zhǔn)撞?biāo)記為未被占用 p->flag=false; break; }}voidallocate<ptr&p>{//最先適應(yīng)法的存分配函數(shù) FreeLink*fl=<FreeLink*>malloc<sizeof<FreeLink>>; cout<<"請(qǐng)輸入要分配存的進(jìn)程號(hào)："; cin>>fl->name; cout<<"請(qǐng)輸入要分配存的大?。?; cin>>fl->size; fl->flag=true; do{ if<p->flag==false&&p->size>fl->size>{ fl->start=p->start; p->start=fl->start+fl->size; p->size=p->size-fl->size; fl->next=p; fl->prior=p->prior; p->prior->next=fl;p->prior=fl;gotoa; } if<p->flag==false&&p->size==fl->size>{p->flag=fl->flag; p->name=fl->name; free<fl>;gotoa; } p=p->next; }while<p!=NULL>; cout<<"存過(guò)小,分配失??！"<<endl; gotob;a:cout<<"分配成功！"<<endl;b:;//啥也不做}voidhuishou<ptr&p>{//存回收函數(shù) charn=''; cout<<"請(qǐng)輸入要回收的存對(duì)應(yīng)的進(jìn)程號(hào)："; cin>>n; do{ if<p->flag==true&&p->name==n> { hebing<p>;gotoc; } p=p->next; }while<p!=NULL>; cout<<"存未能分配給該進(jìn)程,回收失?。?<<endl; gotod;c:cout<<"存回收成功！"<<endl;d:;}intfirstfit<>{//最先適應(yīng)法 charchoice=''; print<>; ptrpcb=<FreeLink*>malloc<sizeof<FreeLink>>; pcb->next=top; pcb->prior=top->prior;top->prior=pcb; pcb->start=top->start; cout<<"請(qǐng)輸入要為系統(tǒng)分配的存塊號(hào)："; cin>>pcb->name; cout<<"請(qǐng)輸入要分配存的大?。?; gotof;e: cout<<"超過(guò)存最大容量,請(qǐng)重新輸入要分配存的大?。?;f: cin>>pcb->size; if<pcb->size>256> gotoe; top->size=top->size-pcb->size; top=pcb; top->flag=true; top->next->start+=top->size; print<>; while<true>{ do{ p=top->next; cout<<"請(qǐng)從下列選項(xiàng)中進(jìn)行選擇："<<endl; cout<<"1.分配存"<<endl; cout<<"2.回收存"<<endl; cout<<"3.結(jié)束操作"<<endl; cout<<"請(qǐng)輸入你的選擇："; cin>>choice; }while<choice!='1'&&choice!='2'&&choice!='3'>; switch<choice>{ case'1':allocate<p>;print<>;break; case'2':huishou<p>;print<>;break; case'3':clear<>;return0;break; } }}intmain<>{//主函數(shù)ptrfree=<FreeLink*>malloc<sizeof<FreeLink>>;top=free;top->name='*';top->start=0;top->size=256; top->flag=false;top->prior=NULL;top->next=NU