动态分区分配算法
计算机操作系统动态分区磁盘调度算法
一个好的计算机系统不仅要有足够的存储容量，较高的存取速度和稳定可靠的存储器，而且能够合理的分配和使用这些主存空间。当用户提出申请主存空间的要求时，存储管理能够按照一定的策略分析主存的使用情况，找出足够的空间分配给申请者；当作业运行完毕，存储管理要回收作业占用的主存空间。本实验采取可变分区存储管理方法，用常用分区管理算法模拟磁盘管理过程，以加深了解操作系统的存储管理功能。
1. 本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。
2. 采用最先适应法、最佳适应法、最坏适应法分配主存空间。
3. 当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。
4. 当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。
5. 设计的模拟系统中，进程数不小于5，进程调度方式可以采用实验一中的任何一种。 6. 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。
首次适应算法
将内存中的空闲区按照地址由低到高的顺序形成空闲区表
当一个新作业要求装入主存时，查空闲区表，从中找到第一个满足要求的空闲区，为作业分配主存空间，并将剩余空闲区按照地址由小到大的顺序插入空闲区表的合适位置，修改已分配表
当作业运行结束后，回收作业的主存空间，并与相邻空闲区合并，修改空闲区表和已分配表 每次主存分配和回收后，打印空闲区表和已分配表
详细描述实验设计思想、程序结构及各模块设计思路； 详细描述程序所用数据结构及算法； 明确给出测试用例和实验结果；
为增加程序可读性，在程序中进行适当注释说明；
认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；
#include #include
using namespace std; const int procsize=5; typedef struct Node{ int PId; int Prio; int NeedRunTime; int Room; Node * next; }PCB;
typedef struct{ PCB *front; PCB *rear; }AleadyQueue;
typedef struct Tab{ int CalledId; int TabId; int Size; int StartAdd; char * Status; Tab *next; }Table;
//进程Id //进程优先数
//进程需要运行时间 //进程所需空间大小
//就绪队列中的下个就绪进程的地址
//就绪链式队列结构体
//分区表结构体
//调用该分区的进程Id //分区号 //大小 //始址 //使用状态 //指向下个分区
void CinInfo(PCB P[procsize]){ //输入进程信息
cout>P[j].PId>>P[j].Prio>>P[j].NeedRunTime>>P[j].Room; } }
void Sort(PCB P[procsize]){ //根据优先数由冒泡法对进程进行排序 int i,j,exchange=1; //exchange表示相邻PCB是否调换 PCB Temp; for(i=procsize;i>1&&exchange;i--){ exchange=0; for(j=0;j
} }
}
AleadyQueue InitQueue(){ //就绪队列初始化函数 AleadyQueue Q; Node *p; p=(Node *)malloc(sizeof(PCB)); if(!p) { coutnext=NULL; return Q; } }
void EnQueue(AleadyQueue &Queue,PCB &P){ Node *p; p=(Node *)malloc(sizeof(PCB)); if(!p) coutnext=NULL; Queue.rear->next=p; Queue.rear=p; } }
void EnQueue1(AleadyQueue &Queue,PCB &P){ Node *p; p=(Node *)malloc(sizeof(PCB)); if(!p) coutnext=NULL; Queue.rear->next=p;
//进程入队操作函数
//进程入队操作函数
}
}
Queue.rear=p;
PCB OutQueue(AleadyQueue &Q){ //进程出队操作函数 Node *P; P=(Node *)malloc(sizeof(PCB)); if(Q.front->next!=NULL){ P=Q.front->next; Q.front->next=P->next; } return *P; }
PCB OutQueue1(AleadyQueue &Q){ //进程出队操作函数 Node *P; P=(Node *)malloc(sizeof(PCB)); if(Q.front->next!=NULL){ P=Q.front->next; Q.front->next=P->next; } return *P; }
void printinfo(AleadyQueue Q){ //打印就绪队列的情况 coutnext; while(1){ if(Q.front!=NULL){ coutPIdPrioNeedRunTimeRoomnext; } else break; } }
int chose(){ //选择所选算法 int i;
cout算法为进程分配内存!\n"; cout算法为进程分配内存!\n"; cout算法为进程分配内存!\n"; cout>i; return i;
}
Table * CreateMMTable(){ Table * FT; Table * R; Table * P; FT=(Table *)malloc(sizeof(Tab)); R=FT; FT->next=NULL; int num=0; int LastAdd=0; int LastSize=1; while(1){ P=(Table *)malloc(sizeof(Tab)); P->CalledId=0; P->TabId=num; P->Size=3*num+1; P->StartAdd=LastAdd+LastSize; P->Status="Free"; num++; LastAdd=P->StartAdd; LastSize=P->Size;
P->next=NULL; R->next=P; R=P;
if(P->StartAdd==93)
break; } return FT; }
Table * CreateUsedTable(){ Table * T; T=(Table *)malloc(sizeof(Tab));
//定义主存分区表 //用尾插入法
//被调用的进程调Id初始化为0 //主存分区号 //分区大小 //分区始址 //分区状态 //分区号加1
//重新定义LastAdd为上次的StartAdd //同上
//内存初始化完毕
//创建已分配表
cout算法为进程分配内存!\n"; cout算法为进程分配内存!\n"; cout算法为进程分配内存!\n"; cout>i; return i;
}
Table * CreateMMTable(){ Table * FT; Table * R; Table * P; FT=(Table *)malloc(sizeof(Tab)); R=FT; FT->next=NULL; int num=0; int LastAdd=0; int LastSize=1; while(1){ P=(Table *)malloc(sizeof(Tab)); P->CalledId=0; P->TabId=num; P->Size=3*num+1; P->StartAdd=LastAdd+LastSize; P->Status="Free"; num++; LastAdd=P->StartAdd; LastSize=P->Size;
P->next=NULL; R->next=P; R=P;
if(P->StartAdd==93)
break; } return FT; }
Table * CreateUsedTable(){ Table * T; T=(Table *)malloc(sizeof(Tab));
//定义主存分区表 //用尾插入法
//被调用的进程调Id初始化为0 //主存分区号 //分区大小 //分区始址 //分区状态 //分区号加1
//重新定义LastAdd为上次的StartAdd //同上
//内存初始化完毕
//创建已分配表
T->next=NULL; return T; }
void CoutMMTable(Table * FTL){ //打印主存表情况 coutnext; while(1){ coutTabIdStartAddSizeStatusnext; if(FTL->next==NULL) break; } }
void CoutFreeTable(Table * FTL){ //打印空闲区表 coutnext; while(1){ coutTabIdStartAddSizeStatus); FTL=FTL->next; if(FTL->next==NULL) break; } }
void CoutUsedTable(Table * UTL){ //打印已分配表 coutnext; while(1){ if(UTL->Status=="Used"){ coutTabIdStartAddSizeStatus); } UTL=UTL->next; if(UTL->next==NULL) break; } }
int DistribMM(Table * MMTableList,PCB Temp,Table * FTL,Table * UTL){//分配一块一定大小的内存 Table *P;
Table * TempMM; TempMM=MMTableList; Table * TTT;
TTT=MMTableList->next;
//需要改为已分配节点的上一个节点
while(1){ //查找满足大小的分区节点 if(TTT->Size>=Temp.Room && TTT->Status=="Free") break; TTT=TTT->next; if(TTT==NULL){ cout
//以下是内存改为已分配 P=(Table *)malloc(sizeof(Tab)); while(1){ if(TempMM->next==TTT) break; TempMM=TempMM->next; }
P->next=TempMM->next; TempMM->next=P;
P->StartAdd=TTT->StartAdd; P->Size=Temp.Room; P->CalledId=Temp.PId; P->TabId=TTT->TabId; P->Status="Used"; P=P->next;
while(P!=NULL){ (P->TabId)++; P=P->next; }
FTL=FTL->next; while(1){ if(FTL->StartAdd==TTT->StartAdd) break; FTL=FTL->next; }
//将空闲分区对应的首地址更改
}
TTT->StartAdd=FTL->StartAdd=TTT->StartAdd+Temp.Room;//空闲表的首地址=原来+Room TTT->Size=FTL->Size=TTT->Size-Temp.Room; while(FTL!=NULL){ (FTL->TabId)++; FTL=FTL->next; }
return 2;
void ReturnMM(Table * MMTableList,Table * FTL,Table * UTL,PCB &Temp){ MMTableList=MMTableList->next; FTL=FTL->next; Table *TT; while(1){ if(MMTableList->CalledId==Temp.PId) { if(MMTableList->next->Status=="Free"){
//回收一块内存
MMTableList->Status="Free"; //修改内存,相邻的为Free MMTableList->CalledId=0; MMTableList->Size=MMTableList->Size+MMTableList->next->Size; MMTableList->next=MMTableList->next->next; TT=MMTableList; while(FTL!=NULL){ if(FTL->StartAdd==TT->next->StartAdd) break; FTL=FTL->next; } FTL->Size=TT->Size; } if(MMTableList->next->Status!="Free") { MMTableList->Status="Free"; //修改内存，相邻的为USed MMTableList->CalledId=0; while(FTL!=NULL){ if(FTL->StartAdd==TT->next->StartAdd) break; FTL=FTL->next; } FTL->Size=TT->Size; } }
if(MMTableList->next==NULL) break;
MMTableList=MMTableList->next; }//总while cout
int FF(Table * MMTableList,Table * FTL,Table * UTL,AleadyQueue &Q){ //首次适应算法 PCB Temp;
int i; //记录分配函数的返回值0 int num=0; //记录进程首次分配内存 while(1){ Temp=OutQueue(Q); if(num
} CoutUsedTable(MMTableList); } if(num==4){ } //打印已分配表 cout
cout
Temp.NeedRunTime--; //进程还需运行时间减1
cout
cout
num++;
if(Temp.NeedRunTime==0) { //判断是否进程运行完毕，如果运行时间为0，则不再入队
cout
cout
if(Temp.PId==5)return 1;
ReturnMM(MMTableList,FTL,UTL,Temp); //回收内存
CoutMMTable(MMTableList); //打印主存情况
CoutFreeTable(FTL); //打印空闲分区表
CoutUsedTable(MMTableList); //打印已分配表
printinfo(Q);
if(Q.front->next==NULL) //判断就绪队列是否为空
break;
}
else
EnQueue(Q,Temp); //运行时间不为0，还需入队等待下一个时间片再次执行
}
return 2;
}
int BF(Table * MMTableList,Table * FTL,Table * UTL,AleadyQueue &Q2){ //最佳适应算法 PCB P[procsize]; //定义五个进程
CinInfo(P); //输入进程信息
Sort(P); //根据优先数的大小进行排序，形成进程数组P
for(int k=0; k
cout
cout
num++;
if(Temp.NeedRunTime==0) { //判断是否进程运行完毕，如果运行时间为0，则不再入队
cout
cout
cout
if(Q2.front->next==NULL) //判断就绪队列是否为空
break;
}
else
EnQueue1(Q2,Temp); //运行时间不为0，还需入队等待下一个时间
片再次执行
}
return 1;
}
int WF(Table * MMTableList,Table * FTL,Table * UTL,AleadyQueue &Q2){ //最坏适应算法 PCB P[procsize]; //定义五个进程
CinInfo(P); //输入进程信息
Sort(P); //根据优先数的大小进行排序，形成进程数组P Q2=InitQueue(); //就绪队列初始化
for(int k=0; k
EnQueue(Q2,P[k]);
int i; //记录分配函数的返回值0 int num=0; PCB Temp; while(1){ Temp=OutQueue1(Q2); if(num
为0，则不再入队
cout
cout
if(Q2.front->next==NULL) break; } else
//判断就绪队列是否为空 EnQueue1(Q2,Temp);
片再次执行
}
return 2;
}
void main(){
AleadyQueue Q1; AleadyQueue Q2; AleadyQueue Q3; //运行时间不为0，还需入队等待下一个时间 //定义一个就绪队列 PCB P[procsize]; CinInfo(P); Sort(P); Q1=InitQueue(); Q2=InitQueue(); Q3=InitQueue(); for(int k=0; k
} int i; int j; while(1){ j=chose(); if(j==1) //记录0，内存不足 //记录所选算法 //判断所选算法,所需操作（FF、BF、WF） i=FF(MM,FreeTableList,UsedTableList,Q1);//首次适应算法 if(i==0) exit(0); //内存不足 if(j==2) i=BF(MM,FreeTableList,UsedTableList,Q2);//最佳适应算法 if(i==0) exit(0); //内存不足 if(j==3) i=WF(MM,FreeTableList,UsedTableList,Q3);//最坏适应算法 if(i==0) exit(0); //内存不足 if(j==4) break; //结束内存分配 } cout