基于可重定位分区分配算法的内存管理的设计与实现

组号成绩

计算机操作系统

课程设计报告

题目基于可重定位分区分配算法得内存管理得设计与实现

专业：计算机科学与技术

班级:

学号+姓名:

指导教师：

20１6年１2月 2３日

一．设计目得

掌握内存得连续分配方式得各种分配算法

二．设计内容

基于可重定位分区分配算法得内存管理得设计与实现.本系统模拟操作系统内存分配算法得实现，实现可重定位分区分配算法，采用PCＢ定义结构体来表示一个进程，定义了进程得名称与大小,进程内存起始地址与进程状态.内存分区表采用空闲分区表得形式来模拟实现。要求定义与算法相关得数据结构，如PCB、空闲分区;在使用可重定位分区分配算法时必须实现紧凑.

三．设计原理

可重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于:在这种分配算法中,增加了紧凑功能。通常，该算法不能找到一个足够大得空闲分区以满足用户需求时，如果所有得小得空闲分区得容量总与大于用户得要求，这就是便须对内存进行“紧

凑”,将经过“紧凑”后所得到得大空闲分区分配给用户。如果所有得小空闲分区得容量总与仍小于用户得要求，则返回分配失败信息

四．详细设计及编码

1.模块分析

（1）分配模块

这里采用首次适应(FＦ）算法.设用户请求得分区大小为u、sｉze，内存中空闲分区大小为ｍ、sｉzｅ，规定得不再切割得剩余空间大小为sizｅ。空闲分区按地址递增得顺序排列;在分配内存时,从空闲分区表第一个表目开始顺序查找，如果m、ｓize≥u、size且ｍ、sｉze—ｕ、siｚe≤size,说明多余部分太小，不再分割,将整个分区分配给请求者;如果m、size≥u、size且m、size－u、siｚe>ｓizｅ，就从该空闲分区中按请求得大小划分出一块内存空间分配给用户,剩余得部分仍留在空闲分区表中;如果m、sｉze

（2）内存回收模块

进行内存回收操作时，先随机产生一个要回收得进程得进程号，把该进程从进程表中中删除,它所释放得空闲内存空间插入到空闲分区表；如果回收区与插入点得前一个空闲分区相邻,应将回收区与插入点得前一分区合并,修改前一个分区得大小；如果回收区与插入点得后一个空闲分区相邻，应将回收区与插入点得后一分区合并，回收区得首址作为新空闲分区得首址，大小为二者之与;如果回收区同时与插入点得前、后空闲分区相邻，应将三个分区合并,使用前一个分区得首址，取消后一个分区，大小为三者之与。

（3）紧凑模块

将内存中所有作业进行移动,使她们全都相邻接,把原来分散得多个空闲小分区拼接成一个大分区。

2.流程图

否

否

就是就是3.代码实现

＃includｅ〈stdio、h〉

＃inclｕdｅ

＃incｌude〈time、h〉

＃inclｕde〈winｄows、h〉

#ｄefｉｎｅ TURE 1

#ｄefiｎe FAＬSE 0

#define OK 1

#ｄｅfｉne ERROＲ 0

#deｆine INFEASIBＬE －1

＃ｄｅfiｎe OＶERFLOW -2

＃deｆinｅ SIZＥ 15

/／/／／/／////／/／//／／/／/／/／////进程表//／/／/／／///／//

int ppNｏ=1; ／/用于递增生成进程号

int pLength=0；

stｒｕct PCB

{

int pNo；//进程号(名）

int pSｉze; /／进程大小

iｎｔ pOｃcuｐｙ；// 实际占用得内存

?iｎt pＳｔartＡｄdr; // 进程起始地址

int pＳtatｅ; //进程状态

｝；

strｕct PＣＢpList［200］;

/////／/／/／/／//／／／/空闲分区表部分//／//／/／///////

tｙpedef int Staｔus;

typｅdef ｓtruct emptyNode

｛//空闲分区结构体

inｔａｒeａＳize； /／空闲分区大小

?ｉnt aStａｒtＡddｒ；／／空闲分区始址

struct emptyＮodｅ *ｎext；

}ｅｍｐtｙＮｏｄe,＊LiｎｋＬｉst；

inｔＬｉstDelｅte(struct ＰCB *pLｉst,int i)；//AAA/删除下标为i得进程

void ｐSort(strucｔ PCB *pＬｉst）； //ＡAA／内存中得进程按始址递增排序

voｉｄｐａct(LinkLｉst ＆L,sｔruct PＣB ＊pＬist）;//AＡA/紧凑 ,内存中进程移动，修改进程数据结构;空闲分区合并,修改空闲分区表数据结构

vｏid ａmａlgaｍaｔe（LinkList &L)；/／ＡAA/回收后进行合并空闲分区

ｖoiｄ recycle(LinkLiｓt &L，ｓｔｒｕct PCB ＊pＬist); //AAＡ/回收，从进程表中删除进程 ,把释放出得空间插入到空闲分区链表中

ＳtatuｓＩnｉtLｉsｔ（LinｋList ＆L)；//１ＡＡA/构造一个新得有头节点得空链表L

Staｔｕs ClearList(LinｋＬist &L)；/／2AＡA/将链表L重置为空表

Stａtus ListＩnｓeｒｔ（ＬinkLｉｓt &L,LiｎｋＬist s1)；//AAA/＊***＊根据始址进行插入

ｖｏｉd DｅlｅteＥlem（ＬiｎkList &Ｌ，inｔ aSｔartAddr）；//**＊＊＊删除线性表中始址值为ａStartＡddr得结点

ｖoid PrｉntList(LinkLｉｓt L); //AAＡ/*＊*＊＊输出各结点得值

voｉｄｃreaｔP（ｓｔruct PCＢ*p）; ／/ＡAA/初始化进程

int sｅaｒcｈ(LinkList ＆L，inｔｐSiｚｅ）；／/AAＡ/检索分区表，返回合适分区得首址

int add（LinkList ＆L)；/／AAA/返回空闲分区总与

ｖoiｄ pListPrint（sｔruct PＣB ＊pList）; //AＡA/输出内存中空间占用情况

void diｓtribute（LｉnｋＬist &L，stｒuct PCB ＊ｐｒoｃｅsｓ)；

int ListＤｅｌｅｔｅ（ｓｔruct PCB *pLiｓt,int i)//ＡＡA/删除下标为i得进程

{

ｆor(;i＜ｐＬｅｎgth—1;ｉ＋+)｛

??ｐＬｉｓｔ[ｉ］＝ｐLiｓt［i+１］；

｝

ｐＬｅngｔｈ——;

}//ListDeｌete

vｏｉd pSort（sｔrucｔＰＣＢ＊pLｉｓt)｛ //AAA/内存中得进程按始址递增排序

?ｉｎt i,j；

ｓｔruct PＣB temp；

for(ｉ=0；i〈ｐＬｅｎgth—1；i++)｛

foｒ(ｊ=０;ｊ〈pLengtｈ-i-１；j＋+）｛

??if（pLｉst［j]、pSｔaｒtAddr>pＬiｓt［ｊ＋1］、pＳtartAddr)｛

??ｔemp=pLisｔ[j];

???pLiｓｔ［ｊ］＝pＬiｓt[j+1]；

?pList[j+1]＝temｐ;

???｝

｝

?}

}

／/AＡA/紧凑 ,内存中进程移动，修改进程数据结构；空闲分区合并，修改空闲分区表数据结构

ｖｏid pact(LinkLisｔ＆L,strｕｃt PCＢ＊pLｉst){

ｐrｉntf(”进行紧凑\n”）；

?//１、进程移动，修改进程数据结构

?int ｉ；

pＬist［0］、pＳtartAｄｄr=0; //第一个进程移到最上面

fｏr(i＝0；i＜pＬength—1；i＋+)｛

??ｐＬist［i+1]、pStaｒｔAddr=pList［ｉ］、pStartＡddr+pLiｓt［ｉ］、ｐＯccu ｐｙ;

}

//２、空闲分区合并,修改空闲分区表数据结构

LiｎkＬiｓｔp＝Ｌ-＞next，s;

?int ｓumEmpty=0；

?wｈile（p！=NUＬＬ）//求空闲区总与

{

??ｓumEmpｔy+＝ｐ—>areaSize;

?p=p-〉neｘｔ;

?ＣleaｒLｉst(L)； /／清空空闲分区表

ｓ=(ＬinkList)malｌoc（ｓizeoｆ（eｍｐtｙNodｅ））；

ｓ—>ａＳtaｒtＡddr=pＬist［pＬｅngｔh－１]、ｐSｔartAdｄr+ｐLｉst[pLeｎgt ｈ—1］、ｐOｃcｕpy；

s-〉areaSｉｚe=sumEmｐty;

?LｉｓtInｓeｒｔ（L,s）；

?pｒiｎtf（”\n紧凑后得〉〉>〉＼n＂）；

pＬiｓtPrｉnt(ｐLｉst);

?PｒinｔLiｓt（L）；

｝

void ａmaｌgamａte(LｉｎkＬist ＆L){//AAA/回收后进行合并空闲分区

ＬinkＬist p=L-〉nｅxt,ｑ=p->next；

ｗhilｅ(ｑ!=NUＬL）｛

?if（p—>aStaｒtAddｒ＋p－〉ａrｅaSize==q->aStａrtAddr)｛

?p—〉areaSizｅ+=ｑ-〉arｅaSｉze；

??DeｌeｔｅElｅm（L，q—〉aSｔartAddr);／/删除被合并得结点

?q=p-〉ｎｅxt；

}eｌse｛

ｐ=q；

??q=q->ｎext；

??｝

｝

//AAＡ/回收，从进程表中删除进程 ,把释放出得空间插入到空闲分区链表中

ｖoiｄrecycle（LinkLiｓｔ＆L,sｔruｃt PＣB ＊pLisｔ）{

int inｄex，deｌPＮo，delPSｉze，deｌPＯccupy，delPＳｔartAｄdr；

ＬiｎkLｉst ｓ;

sｒand（tiｍe(0））；

indｅx=ｒand（)%pLength；

dｅｌＰNo＝pList［ｉｎdｅx］、ｐNo；

ｄelＰＳize=pLisｔ[index]、pSiｚe；

dｅlPOccupy=pＬｉｓt［inｄex］、ｐOccupy;

delPＳtarｔAddr=pＬisｔ[index］、pStarｔAｄdr;

prｉｎｔf（"________＿＿＿___＿______＿____＿_＿____＿_＿_____＿＿＿_＿＿_______＿__＿＿＿___＿_＿_＿________＿＿__＂);

pｒiｎｔｆ("回收内存进程 P%d: 始址:％d K 占用:％d KＢ＼n”,ｄelPNo，dｅlPＳtartAddr，deｌPOccupy)；

ｐrinｔf（"\n回收后〉〉〉＞＼n＂）；

LｉｓtDeletｅ（pLｉst，inｄex);

／/pLｉｓtＰrｉｎｔ（pList)；

s=（ＬｉnkList)maｌloc（sizｅoｆ(ｅmptｙNodｅ）)；

?s—>aｒeaSiｚe＝dｅlPOcｃuｐy;

ｓ—＞ａSｔａｒtAddr=delPStaｒtAddr;

ＬｉstIｎｓert(L，s);

amalgamate(L）；

pListＰrｉnt（ｐList）;/／输出内存中空间占用情况

PｒintList（Ｌ)；

｝

///／////／/////／/／/／/////／/／//／////／////／/／/

Staｔus IｎitList(LinkLisｔ＆Ｌ） //1AAA／构造一个新得有头节点得空链表L {

?LinｋLｉsｔ s;

Ｌ=(LinkLiｓｔ)mａlloc（sizeoｆ(emptｙNｏde）)；／/生成新节点(头结点)

if（!L） rｅtｕｒn ERROR; ／／申请内存失败

s=(LiｎkＬisｔ)ｍａｌloｃ(sizｅoｆ(ｅmptyNodｅ）);

?ｓ－＞ａreaSｉzｅ=９0０;

?s->aStａｒtAddr=０;

Ｌ-〉nexｔ=s；//头节点得指针域指向第一个结点

s-〉neｘt=NULＬ；

ｒｅtｕrn ＯＫ;

}/／IｎitLｉst

SｔatuｓＣlearLiｓｔ(LiｎkList ＆L） //2AAA/将链表Ｌ重置为空表

{

ＬinkList p，r；

ｐ=L-〉ｎext； r＝p—〉nｅxｔ；

?ｗｈｉle（p！=NUＬL)

{

frｅe（p）；

?if（ｒ==NULＬ）{

??p=ＮUＬＬ；

??}elｓｅ｛

??p=r;

?? r=ｐ—〉ｎext；

｝

｝

L－>ｎext=NULL；

return OK；

｝//CleａrLiｓt

//AＡA/****＊根据始址进行插入

Ｓtａtｕｓ ListＩｎseｒt（ＬｉnｋLiｓｔ &L，LｉｎkLiｓt ｓ1）{

?LinkList r=Ｌ，ｐ＝L—>next，s；//指针

ｓ=(LinkLｉｓt）mａlloc(ｓizeof（empｔｙNode）)；

?s—〉ａreaＳize＝s1－＞ａｒｅａSｉｚe；

s-＞aStａrtAｄdr=ｓ1—>aStarｔAｄｄr;

?iｆ（p==NULＬ）｛

??L—〉nｅxt＝s；

s—〉next=NULL;

?｝ｅｌsｅ｛

while（ｐ!=NULL）

｛

?? if（ｓ１—>aStartＡddr ＜p－>aStartＡｄdr)｛

??ｓ->next=r-＞next；

?r-〉neｘｔ＝s；

??ｂreak;

｝

ｒ=p;

??p=p－>nexｔ; ／／后移

?｝

if(p==NUＬL）｛

?r-〉nｅxt=s;

?ｓ->next=NULL；

?｝

}

rｅtuｒn OＫ;

｝//LisｔIｎsert2

ｖoiｄＤｅleteElｅm(LｉnkLiｓt ＆L，ｉｎt aＳｔarｔAddr）//＊＊*＊*删除线性表中始址值为aStartＡddｒ得结点

｛

?LinkＬisｔp＝L，ｑ；

?whilｅ（p—＞next!=NULL）

｛

?q=ｐ-＞ｎexｔ；

??iｆ(q->aＳtａrｔＡddｒ==aＳtaｒtAddｒ)

?｛

?p->next=ｑ—>nｅxt;

fｒee（q）;

?｝

?elｓe

?p＝p—>ｎext;

?｝

｝//DｅlｅteＥlem

///／/////／/／／/／/////////／///／///////////／///／/／/

void PrintＬｉst(ＬｉnｋList Ｌ)//AAA/＊****输出各结点得值

｛

printf(”\n空闲分区情况: 始址＼t 大小\n”）；

LinｋList p=L—〉nexｔ；

?whｉle(p！＝NULL)

?{

printf（" ％d Ｋ\t%ｄ KB\n",ｐ-〉aStartＡｄd ｒ，p—>areａSｉzｅ）；

??p=p—>nexｔ；

?｝

printf（＂＼n")；

｝//ＰrｉnｔＬiｓt

ｖoiｄｃreatＰ(stｒuct PCB ＊p）{ ／/AAA/初始化进程

iｎt size;

ｓｒanｄ（time(NUＬL)）；

size=raｎd（)%７＋１；

ｓize＊＝１0；

p->pNo＝pｐNo＋+；

ｐ->ｐSiｚe=ｓiｚｅ；

?p－＞ｐOｃｃｕpy＝0；

?p—〉ｐＳtartAddr=0;

?p-〉pStａte=0；

｝

int search（ＬinkLiｓt &L,int pSｉｚe）{ //检索分区表，返回合适分区得首址ＬinkList p=Ｌ-〉nｅxt；

whiｌe(p！=NUＬL)

{

?ｉｆ(p—>ａｒeａＳiｚe>＝pSize){

??reｔｕrn p—>aStaｒtAddr；

｝

?p＝p-〉ｎext；

｝

return -1;//没有足够大得

｝

iｎｔ adｄ（LｉnkList ＆L){ //返回空闲分区总与

LinkLｉst p=Ｌ—＞ｎeｘt；

int sum=0;

?ｗhile（ｐ！＝NULL）

{

suｍ+=p－>arｅａSｉze；

p=p－>next;

?}

?returｎ sｕm；

}

voiｄpＬisｔＰrｉnt(stｒuct PCB *pLisｔ){／/ＡＡＡ/输出内存中空间占用情况ｐrｉntf（＂\n进程分配情况：进程＼t 始址\ｔ占用＼n”）;

foｒ（ｉｎt i＝0；i＜ｐLengｔh;i＋+）{

?pｒintf(" P%d\ｔ％d K\t％d KＢ\n"，

pList［i］、pＮo,pList［ｉ]、pＳtartAddｒ，pLｉsｔ[i]、pＯccupy)；?}

｝

vｏid ｄｉstribuｔｅ(LinｋLｉｓｔ＆L,strｕcｔＰCB *process)｛

?LｉｎkLiｓｔ p＝L-〉nｅxｔ；

?while(p!＝NULL)

?{

?if（p—＞areaSize>=process->pSize)

?breaｋ;

??ｐ=p—〉nｅxｔ;

?｝

?ｐriｎｔｆ（”％ｄ KB ＜%d KB”，prｏcess—＞pＳｉｚe,p->areａＳize)；

?iｆ(p—〉ａrｅaSｉze-ｐｒocess-＞pＳize〈＝ＳIZE）｛

?//不用分割全部分配 (直接删除此空闲分区结点)

process—〉pStaｒtAddr=p-＞ａＳtaｒtAdｄr; //进程始址变化

?procｅss->pState=1; //进程状态

?pｒocess-＞pＯｃｃupy=ｐ—〉areaＳｉzｅ; //进程实际占用内存为改空闲分区得大小

?ｐLｉｓt[ｐLeｎgth＋+]= ＊pｒｏｃｅｓs； //把进程加入进程列表

prｉｎtｆ（" 且％d KB - %d KB = ％d KB 〈％d ＫＢ则整区分配＼n”，

? p->areaSizｅ，pｒoｃess—＞ｐSize,p—＞ａreaSizｅ—pｒocesｓ-〉p Ｓｉze,ＳＩＺE)；

?ｐＳort（pLiｓt);

printf（＂\n分配后>〉>〉＼n”）；

??pListPrint（pＬｉst）；／/输出内存中空间占用情况

??DeleteＥlem（L，ｐ－>aSｔａrｔAddr）；

}else{//分割分配

ｐrocesｓ—>pStartＡddr=p-＞ａStartAddｒ； //进程始址变化

?proceｓs－>pSｔaｔe=1； //进程状态

?prｏcesｓ－〉pOcｃupｙ=ｐrｏceｓs->pＳｉze；／/进程实际占用内存为该进程得大小

??ｐLisｔ［ｐＬength++］= *ｐrocess；／/把进程加入进程列表

?prｉntf(＂且％d ＫB - ％d KB ＝ %d KB > %d KB 则划分分配\n”,

?? p-〉arｅａSize,process－〉pSize,p->areａSize—pｒｏcesｓ－>pSｉz ｅ，SIZＥ);

??pSort（ｐLisｔ)；／/进程排序

?prinｔｆ（”\n分配后>＞＞>＼ｎ”)；

?pListＰrint（pLｉsｔ);//输出内存中空间占用情况

?／／pact（L,pLiｓt)；

p—〉ａStａrtAdｄｒ+=proｃess—>pSize；／/空闲分区始址变化

ｐ—〉aｒｅaSizｅ—＝prｏcess－〉ｐＯccupy；//空闲分区大小变化

}

｝

inｔｍａin()｛

?／/0、创建一个进程，参数随机数方式产生

?struct PCB p；

? inｔｉ,nｕm,dele，k，stAｄdr，flａｇ;

? LinｋＬisｔ s，L；

?ｐｒinｔf（”*＊＊＊**＊＊*＊*＊*＊*＊*＊***＊＊＊＊*＊＊*＊*＊可重定位分区分配*＊＊＊*＊＊＊*＊＊＊＊＊＊＊*＊**＊*＊＊＊＊＊***＊*"）;

if（!InitＬiｓt(L））//初始化空闲分区表

?prｉntf（＂创建表失败\n＂);

while(1）｛

?sｒaｎd（time（0）)；

?flａｇ＝ｒaｎｄ()%１００＋1；

iｆ(flａg％２==0){

ｃreatP（＆ｐ)；//初始化进程

ｐrintf(＂__＿__＿______＿____________＿_____＿_＿＿__________＿

_____＿＿＿____＿＿___＿_________＿_＿____"）;

??priｎtf(”待装入作业：%ｄＳize = ％d KB＼n＂，p、pNo,ｐ、pSｉze)；

//1、请求分配 size

//2、检索空闲分区表（首次适应FF）

?PrintList(Ｌ);

ｓtＡdｄr=seａrch（L，p、pSize）；//得到足够大得分区得始址,没有则返回—１

if(sｔＡdｄｒ==-1){//没有足够大得分区

?if(adｄ(L）>＝p、pSiｚe)｛//空闲区总与足够大

??printf（＂没有足够大得空闲分区但空闲总与足够大\n")；

??//紧凑

?pａct（Ｌ,pList);

? //按动态分区方式分配

?disｔribuｔe（L,＆p);

?／/ｐact(L，pLisｔ）；//紧凑

??}ｅlｓｅ{ //空闲区总与不足

?prｉntf（＂分配失败\ｎ\n");

??}

}eｌsｅ｛//有足够大得

dｉsｔribute（L,＆p）；

??ＰｒiｎtList（L)；

??／／pａｃt（Ｌ,ｐList)；//紧凑

?}

?}ｅlse｛／/回收

???if(ｐLeｎgth〉0）{

?ｒeｃycle(L，pＬiｓt);

//pact(Ｌ,pＬiｓｔ）；／/紧凑

｝ｅlse｛

?prｉntf（＂无可回收内存! ”）；

?}

}

systｅm(＂pａｕｓe”);

｝//whiｌe

return 0；

｝

4.结果及其相关分析

图4、１

分析：作业1大小为２0KB。找到足够大空闲分区,进行划分分配。

图4、２

分析:作业２大小为7０KB.找到足够大空闲分区,进行划分分配。

图4、3

分析：先回收进程1大小为2０KB,删除进程，并把释放得空闲分区插入空闲分区表；再回

收进程2大小为7０ＫB,删除进程，并把释放得空闲分区插入空闲分区表;

图4、4

分析:程序运行一段时间后得进程分配情况与空闲分区情况。

图4、5

实验三动态分区存储管理方式的主

实验三动态分区存储管理方式的主存分配回收 一、实验目的 深入了解动态分区存储管理方式主存分配回收的实现。 二、实验预备知识 存储管理中动态分区的管理方式。 三、实验内容 编写程序完成动态分区存储管理方式的主存分配回收的实现。实验具体包括： 首先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配和回收；最后编写主函数对所做工作进行测试。 四、提示与讲解 动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 实现动态分区的分配和回收，主要考虑的问题有三个： 第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。 首先，考虑第一个问题： 设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。 由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主

存中的起始地址和长度。由于分配时空闲区有时会变成两个分区： 空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。 由此可见，主存的分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情况，一张表格记录作业占用分区的 “已分配区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区 表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分配区表”还是“空闲区表”都有空闲栏目。已分配区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。在实际系统中，这两表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此, “已分配区表”和“空闲区表”在实验中有如下的结构定义。 已分配区表的定义： #define n 10// 假定系统允许的最大作业数量为n struct {float address;// 已分分区起始地址 float length; // 已分分区长度，单位为字节 int flag;// 已分配区表登记栏标志, “0表”示空栏目，实验中只支持一个字符的作业名}used_table[n];// 已分配区表 空闲区表的定义：

动态分区式存储管理

可变分区存储管理 设计思路： 整体思路： 可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个 空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 设计所才用的算法： 采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值min size，如果空闲区的大小减去作业需求长度得到的值小于等于min size，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。 内存分配与回收所使用的结构体： 为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。 关于分配留下的内存小碎片问题： 当要装入一个作业时，从“空闲分区表”中查找标志为“ 1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于min size，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“ 0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于

存储管理实验报告

实验三、存储管理 一、实验目的： ? 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。 在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验理解在分页式存储管理中怎样实现虚拟存储器。 在本实验中，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。 二、实验题目： 设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 对分区的管理法可以是下面三种算法之一：（任选一种算法实现） 首次适应算法 循环首次适应算法 最佳适应算法 三．实验源程序文件名:cunchuguanli.c

执行文件名:cunchuguanli.exe 四、实验分析： 1)本实验采用可变分区管理，使用首次适应算法实现主存的分配和回收 1、可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并 且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表 ? 空闲区说明表格式如下：? 第一栏 第二栏 其中，起址——指出一个空闲区的主存起始地址，长度指出空闲区的大小。 长度——指出从起始地址开始的一个连续空闲的长度。 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业完成后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。 2、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。 有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分

操作系统课程设计--连续动态分区内存管理模拟实现

（操作系统课程设计） 连续动态分区内存 管理模拟实现

目录 《操作系统》课程设计 (1) 引言 (3) 课程设计目的和内容 (3) 需求分析 (3) 概要设计 (3) 开发环境 (4) 系统分析设计 (4) 有关了解内存管理的相关理论 (4) 内存管理概念 (4) 内存管理的必要性 (4) 内存的物理组织 (4) 什么是虚拟内存 (5) 连续动态分区内存管理方式 (5) 单一连续分配（单个分区) (5) 固定分区存储管理 (5) 可变分区存储管理（动态分区） (5) 可重定位分区存储管理 (5) 问题描述和分析 (6) 程序流程图 (6) 数据结构体分析 (8) 主要程序代码分析 (9) 分析并实现四种内存分配算法 (11) 最先适应算 (11) 下次适应分配算法 (13) 最优适应算法 (16)

最坏适应算法......................................................... (18) 回收内存算法 (20) 调试与操作说明 (22) 初始界面 (22) 模拟内存分配 (23) 已分配分区说明表面 (24) 空闲区说明表界面 (24) 回收内存界面 (25) 重新申请内存界面..........................................................26. 总结与体会 (28) 参考文献 (28) 引言 操作系统是最重要的系统软件，同时也是最活跃的学科之一。我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。 存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。 课程设计目的和内容： 理解内存管理的相关理论，掌握连续动态分区内存管理的理论；通过对实际问题的编程实现，获得实际应用和编程能力。

固定分区存储管理

理工大学信息工程与自动化学院学生实验报告 （ 2013 —2014 学年第一学期） 课程名称：操作系统开课实验室：信自楼444 2013年 11月28 日 注：报告容按下列的要求进行。 一、实验目的 通过编写固定分区存储管理的模拟程序，加深对操作系统存储管理功能中的固定分区管理方式、主存分配表等相应知识的理解。 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的存分配和回收。 二、实验题目 1.设计一个固定分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 2.必须建立分区表，记录空闲区与占用区的状况。

本系统将存用户空间划分为五个大小不固定的分区，其分区大小由用户输入决定。在每个分区只装入一道作业，这样把用户空间划分为几个分区，便允许几道作业并发运行。当有一个空闲分区时，便可以从外存的后备队列中选择一个适当大小的作业装入该分区，当该作业结束时又可以从后备作业队列中找出另一作业调入该分区。 每个存空间是一个Node型的对象。Node类有一个三个参数的构造函数。分别为：分区号、起始地址、大小。然后就是一些属性的get、set方法和一个打印其属性的函数。四个数据域分别为：属性m_No用来表示该存空间的序号。属性m_Addr用来表示存分区的起始地址。属性m_Size用来表示存空间的大小。属性m_State表示存空间的是否已分配的状态标志。若该存空间已分配，m_TaskNo表示占有该存空间的任务序号。否则没有实际意义。 在用户申请任务的存空间时，提示用户输入任务号和其需要的存空间大小。 流程图 主程序：

释放存空间算法

动态分区分配方式模拟

使用动态分区分配方式的模拟 1内容 （1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。 （2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：?作业1申请130KB。 ?作业2申请60KB。 ?作业3申请100KB。 ?作业2释放60KB。 ?作业4申请200KB。 ?作业3释放100KB。 ?作业1释放130KB。 ?作业5申请140KB。 ?作业6申请60KB。 ?作业7申请50KB。 ?作业6释放60KB。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 2、示例程序： //Tittle: 使用动态分区算法的模拟 //author: XuYongzhen #include #include #include #include using namespace std; typedef struct DuLNode{ struct DuLNode *prior; struct DuLNode *next; int address; int jsize; int jnumber;//显示分区被那个作业占用，显示零则为空闲分区； }DuLNode,*DuLinkList ; void CreatList(DuLinkList &L){ DuLinkList p=(DuLinkList)malloc(sizeof(DuLNode)); L->next=p; L->jnumber=100;//为释放头结点后面的结点空间做统一化处理 p->prior=L; p->next=NULL; p->jsize=600; p->address=0; p->jnumber=0;

实验四可变分区存储管理方式的内存分配和回收

实验四 实验四可变分区存储管理方式的内存分配和回收 一．实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。 二．实验属性 设计 三．实验内容 1．确定内存空间分配表； 2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。 四．实验背景材料 实现可变分区的分配和回收，主要考虑的问题有三个： 第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。 首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。 由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：

空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。 由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种： 一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。 “已分分区表”的结构定义 #define n 10 //假定系统允许的最大作业数量为n struct { float address; //已分分区起始地址 float length; //已分分区长度、单位为字节 int flag;//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n]; //已分分区表 “空闲区表”的结构定义 #define m 10 //假定系统允许的空闲区最大为m struct { float address; //空闲区起始地址

动态分区存储管理系统分解

操作系统原理 课程设计报告 题目：动态分区分配存储管理系统 所在学院：计算机科学与技术学院 班级： 11级计算机科学与技术(非师) 学号： 20111202052 姓名：吴创连 指导教师：黄侠剑 2014年3月18

目录 1 引言 (1) 2 需求分析 (1) 3 概要设计 (1) 4 详细设计 (1) 4.1问题描述和分析 (1) 4.2程序流程图 (2) 4.3数据结构体分析 (3) 4.4主要程序代码分析 (4) 5 调试与操作说明 (11) 5.1初始界面 (11) 5.2模拟内存分配 (12) 5.3回收内存界面 (12) 5.4最佳适应算法的实现 (13) 5.5最坏适应算法的实现 (13) 6总结与体会 (13)

1 引言 操作系统是最重要的系统软件，同时也是最活跃的学科之一。我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。 存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。 2 需求分析 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。常用的数据结构有动态分区表和动态分区链。在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（最佳适应算法，最坏适应算法），在动态分区存储管理方式中主要实现内存分配和内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接等相关的内容。 3 概要设计 本程序采用机构化模块化的设计方法，共分为两大模块。 1．最佳适应算法实现 它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。 2.最坏算法实现 最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。 4 详细设计 4.1 问题描述和分析 系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大小

操作系统实验之内存管理实验报告

学生学号 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称 计算机操作系统 开 课 学 院 计算机科学与技术学院 指导老师姓名 学 生 姓 名 学生专业班级 2016 — 2017 学年第一学期

实验三 内存管理 一、设计目的、功能与要求 1、实验目的 掌握内存管理的相关内容，对内存的分配和回收有深入的理解。 2、实现功能 模拟实现内存管理机制 3、具体要求 任选一种计算机高级语言编程实现 选择一种内存管理方案：动态分区式、请求页式、段式、段页式等 能够输入给定的内存大小，进程的个数，每个进程所需内存空间的大小等 能够选择分配、回收操作 内购显示进程在内存的储存地址、大小等 显示每次完成内存分配或回收后内存空间的使用情况 二、问题描述 所谓分区，是把内存分为一些大小相等或不等的分区，除操作系统占用一个分区外，其余分区用来存放进程的程序和数据。本次实验中才用动态分区法，也就是在作业的处理过程中划分内存的区域，根据需要确定大小。 动态分区的分配算法：首先从可用表/自由链中找到一个足以容纳该作业的可用空白区，如果这个空白区比需求大，则将它分为两个部分，一部分成为已分配区，剩下部分仍为空白区。最后修改可用表或自由链，并回送一个所分配区的序号或该分区的起始地址。 最先适应法：按分区的起始地址的递增次序，从头查找，找到符合要求的第一个分区。

最佳适应法：按照分区大小的递增次序，查找，找到符合要求的第一个分区。 最坏适应法：按分区大小的递减次序，从头查找，找到符合要求的第一个分区。 三、数据结构及功能设计 1、数据结构 定义空闲分区结构体，用来保存内存中空闲分区的情况。其中size属性表示空闲分区的大小，start_addr表示空闲分区首地址，next指针指向下一个空闲分区。 //空闲分区 typedef struct Free_Block { int size; int start_addr; struct Free_Block *next; } Free_Block; Free_Block *free_block; 定义已分配的内存空间的结构体，用来保存已经被进程占用了内存空间的情况。其中pid作为该被分配分区的编号，用于在释放该内存空间时便于查找。size表示分区的大小，start_addr表示分区的起始地址，process_name存放进程名称，next指针指向下一个分区。 //已分配分区的结构体 typedef struct Allocate_Block { int pid; int size; int start_addr; char process_name[PROCESS_NAME_LEN]; struct Allocate_Block *next; } Allocate_Block; 2、模块说明 2.1 初始化模块 对内存空间进行初始化，初始情况内存空间为空，但是要设置内存的最大容量，该内存空间的首地址，以便之后新建进程的过程中使用。当空闲分区初始化

计算机操作系统内存分配实验报告

一、实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下.如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配.就是解决多道作业或多进程如何共享主存空间的问题。所谓回收.就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区.使分区大小正好适合作业的需求.并且分区个数是可以调整的。当要装入一个作业时.根据作业需要的主存量查看是否有足够的空闲空间.若有.则按需要量分割一个分区分配给该作业；若无.则作业不能装入.作业等待。随着作业的装入、完成.主存空间被分成许多大大小小的分区.有的分区被作业占用.而有的分区是空闲的。 实验要求使用可变分区存储管理方式.分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行.分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时.要求设计一个实用友好的用户界面.并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料 实验环境 硬件环境：PC或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析 某系统采用可变分区存储管理.在系统运行当然开始.假设初始状态下.可用的内存空间为640KB.存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB） 当作业1进入内存后.分给作业1（130KB）.随着作业1、2、3的进入.分别分配60KB、100KB.经过一段时间的运行后.作业2运行完毕.释放所占内存。此时.作业4进入系统.要求分配200KB内存。作业3、1运行完毕.释放所占内存。此时又有作业5申请140KB.作业6申请60KB.作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理.使用空闲分区链实现主存分配和回收。 空闲分区链：使用链指针把所有的空闲分区链成一条链.为了实现对空闲分区的分配和链接.在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针.由状态位指示该分区是否分配出去了；同时.在分区尾部还设置有一后向指针.用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间.当该分区分配出去后.状态位就由“0”置为“1”。 设置一个内存空闲分区链.内存空间分区通过空闲分区链来管理.在进行内存分配时.系统优先使用空闲低端的空间。 设计一个空闲分区说明链.设计一个某时刻主存空间占用情况表.作为主存当前使用基础。初始化空间区和已分配区说明链的值.设计作业申请队列以及作业完成后释放顺序.实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。

动态分区分配方式的模拟C语言代码和C代码

实验三使用动态分区分配方式的模拟 1、实验目的 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 2、实验内容 (1) 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。 (2) 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列： ?作业1申请130KB。 ?作业2申请60KB。 ?作业3申请100KB。 ?作业2释放60KB。 ?作业4申请200KB。 ?作业3释放100KB。 ?作业1释放130KB。 ?作业5申请140KB。 ?作业6申请60KB。 ?作业7申请50KB。 ?作业6释放60KB。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 程序代码——C语言实现 #include #include struct node //空闲分区链结点的定义 { node *before; node *after; int size; int address; int state; }; node L; struct usenode { usenode *next; int num; int add; int size; }U,*n;

void Init() //空闲分区链的初始化 { node *p; p=(node *)malloc(sizeof(node)); p->before=&L; p->after=NULL; p->size=640; p->address=0; p->state=0; L.after=p; L.before=NULL; L.size=0; U.next=NULL; n=&U; } node *search(int a) { node *p=L.after; if(p==NULL) { printf("没有空闲的区域!"); p=NULL; return p; } else { while(p!=NULL && a>p->size) p=p->after; if(p==NULL) { printf("没有找到合适的空闲空间!"); p=NULL; return p; } else return p; } } void recovery(int a,int b) //内存回收算法 {

计算机操作系统内存分配实验报告记录

计算机操作系统内存分配实验报告记录

————————————————————————————————作者：————————————————————————————————日期：

一、实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料 实验环境 硬件环境：PC或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析 某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB） 当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。 空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。 设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。 设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明

最新c++动态分区分配算法模拟(操作系统课程设计)

c++动态分区分配算法模拟(操作系统课程 设计)

课程设计 课程设计名称：操作系统课程设计 专业班级： 学生姓名： 学号： 指导教师： 课程设计时间：6月13日-——6月17日

计算机科学专业课程设计任务书 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页

1：需求分析 （1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。 （2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放 130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请 50KB；作业6释放60 KB。采用首次适应算法进行内存块的分配和回 收，同时显示内存块分配和回收后空闲内存分区链的情况。 2：概要设计 （1）数据结构：作业队列数据结构，用于存储待处理作业；阻塞作业队列数据结构，用于存储阻塞的作业。已分配内存块的双向链表，记录当前系 统已分配的各个内存块；未分配内存块的双向链表，记录系统中剩余的 各个内存块；系统内存分配总情况的结点对象，记录系统中阻塞的作业 总数，已分配的内存块数，剩余的内存块数。 （2）主函数：对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化，调用分配函数或回收函 数，循环处理11个作业步。 （3）分配函数alloc()：首次适应算法检索未分配的内存块链表，若找到合适的内存块，则加以判断，空闲内存块大小减去作业去请求内存块大小小于

可变分区存储管理方式的内存分配和回收实验报告(最优算法)

一．实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。 二．实验内容 1．确定内存空间分配表； 2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。 三．实验背景材料 由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。 “已分分区表”的结构定义 #define n 10 //假定系统允许的最大作业数量为n struct { float address; //已分分区起始地址 float length; //已分分区长度、单位为字节 int flag; //已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n]; //已分分区表 “空闲区表”的结构定义 #define m 10 //假定系统允许的空闲区最大为m struct { float address; //空闲区起始地址 float length; //空闲区长度、单位为字节 int flag; //空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配 }used_table[n]; //空闲区表 第二，在设计的数据表格基础上设计内存分配。 装入一个作业时，从空闲区表中查找满足作业长度的未分配区，如大于作业，空闲区划分成两个分区，一个给作业，一个成为小空闲分区。 实验中内存分配的算法采用“最优适应”算法，即选择一个能满足要求的最小空闲分区。 第三，在设计的数据表格基础上设计内存回收问题。内存回收时若相邻有空闲分区则合并空闲区，修改空闲区表。 四、参考程序 #define n 10 //假定系统允许的最大作业数量为n

循环首次适应的动态分区分配算法模拟

课程设计报告 课程设计题目：循环首次适应的动态分区分配算法模拟 专业：计算机科学与技术 班级：10204102 姓名：谱 学号: 10204102 指导教师:高小辉 2013年1月11 日

目录 一．循环首次适应算法 (3) 1. 概述 (3) 2．需求分析 (3) 二．实验指导 (4) 1.基本思想 (4) 2．数据结构 (4) 三．运行环境 (6) 四．流程图 (6) 五．循环首次适应算法代码 (5) 六．调试结果 (11) 七、总结 (14) 八．参考文献 (14)

一．循环首次适应算法 1.概述： 该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。 2. 需求分析 了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。 空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。 作业完成时，需要释放作业所占空间，此时要考虑到四种情况： (1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一 分区的大小。 (2)回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址 作为新空闲区的首址。 (3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空 闲分区的表项和首址。 (4)回收区单独存在。 二、实验指导 1．基本思想 动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。 2．数据结构 动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。

操作系统内存管理

操作系统内存管理 1. 内存管理方法 内存管理主要包括虚地址、地址变换、内存分配和回收、内存扩充、内存共享和保护等功能。 2. 连续分配存储管理方式 连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。 2.1 单一连续存储管理 在这种管理方式中，内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。CP ／M和DOS 2．0以下就是采用此种方式。这种方式的最大优点就是易于管理。但也存在着一些问题和不足之处，例如对要求内存空间少的程序，造成内存浪费；程序全部装入，使得很少使用

的程序部分也占用—定数量的内存。 2.2 分区式存储管理 为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行内存分区的共享。 分区式存储管理引人了两个新的问题：内碎片和外碎片。 内碎片是占用分区内未被利用的空间，外碎片是占用分区之间难以利用的空闲分区(通常是小空闲分区)。 为实现分区式存储管理，操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。 分区式存储管理常采用的一项技术就是内存紧缩

(compaction)。 2.2.1 固定分区(nxedpartitioning)。 固定式分区的特点是把内存划分为若干个固定大 小的连续分区。分区大小可以相等：这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 优点：易于实现，开销小。 缺点主要有两个：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。 2.2.2动态分区(dynamic partitioning)。 动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是：没有内碎片。但它却引入了另一种碎片——外碎片。动态分区的分区分配就是寻找某个空闲分区，其大小需大于或等于程序的要求。

固定分区存储管理

昆明理工大学信息工程与自动化学院学生实验报告 （ 2013 —2014 学年第一学期） 课程名称：操作系统开课实验室：信自楼444 2013年 11月28 日 注：报告内容按下列的要求进行。 一、实验目的 通过编写固定分区存储管理的模拟程序，加深对操作系统存储管理功能中的固定分区管理方式、主存分配表等相应知识的理解。 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。 二、实验题目 1.设计一个固定分区分配的存储管理方案。并模拟实现分区的分配和回收过程。

2.必须建立分区表，记录空闲区与占用区的状况。 3.流程图按选定的算法自己完成。 三、算法设计的思想或流程图 本系统将内存用户空间划分为五个大小不固定的分区，其分区大小由用户输入决定。在每个分区只装入一道作业，这样把用户空间划分为几个分区，便允许几道作业并发运行。当有一个空闲分区时，便可以从外存的后备队列中选择一个适当大小的作业装入该分区，当该作业结束时又可以从后备作业队列中找出另一作业调入该分区。 每个内存空间是一个Node型的对象。Node类有一个三个参数的构造函数。分别为：分区号、起始地址、大小。然后就是一些属性的get、set方法和一个打印其属性的函数。四个数据域分别为：属性m_No用来表示该内存空间的序号。属性m_Addr用来表示内存分区的起始地址。属性m_Size用来表示内存空间的大小。属性m_State表示内存空间的是否已分配的状态标志。若该内存空间已分配，m_TaskNo表示占有该内存空间的任务序号。否则没有实际意义。 在用户申请任务的内存空间时，提示用户输入任务号和其需要的内存空间大小。 流程图 主程序：