4．内存的分配与释放
在Linux下编写一个C程序，申请一段内存空间，并在终端上显示其起始地址，在用户要求下能释放该内存空间。
功能要求：
（1）用malloc函数分配；
（2）显示所分配的内存起始地址；
（3）按q键用free函数释放内存。
#include <iostream>
using namespace std;
#define MAX_PROCESSES 10 /*假定模拟实验中,系统允许的最多进程为10个*/
#define MAX_FREE_MEMORY_DISTRICT 10 /*假定模拟实验中,系统允许的空闲区表最多为10个*/
#define MIN_SIZE 100
#define TRUE 1
#define FALSE 0
struct
{
long address; /*某进程装入模块在内存中起始地址*/
long length; /*进程装入模块长度，单位为字节*/
int ProcessId;//进程ID
int UsedFlag; /*分配标志，TRUE表示该表项已分配，FALSE表示该表项未分配*/
}used_table[MAX_PROCESSES]; /*已分配区表*/
struct
{
long address; /*内存空闲区块起始地址*/
long length; /*内存空闲区块长度，单位为字节*/
int AllocFlag; /*表示该表项是否指向空闲内存块，TRUE表示已指向某空闲区块，FALSE表示未指向某空闲区块*/
}free_table[MAX_FREE_MEMORY_DISTRICT]; /*空闲区表*/
void allocate(int ProcessId,long ProcessMemLength) //进程ID，进程所需内存长度
/*采用最优分配算法分配ProcessMemLength大小的空间*/
{
int i,k;
long FirstAddress;
k=-1;
for(i=0;i<MAX_FREE_MEMORY_DISTRICT;i++) /*寻找空间大于ProcessMemLength的最小空闲区*/
{
if((free_table[i].AllocFlag == TRUE) && (free_table[i].length>=ProcessMemLength))
{
if((k==-1) || (free_table[i].length<free_table[k].length))
{
k=i;
}
}
}
if(k==-1)/*未找到可用空闲区，返回*/
{
printf("无可用空闲区\n");
return;
}
//找到可用空闲区，开始分配：若空闲区大小与要求分配的空间差小于MIN_SIZE大小，则空闲区全部分配；
//若空闲区大小与要求分配的空间差大于MIN_SIZE大小，则从空闲区划出一部分分配*/
if((free_table[k].length - ProcessMemLength) <= MIN_SIZE)
{
free_table[k].AllocFlag = FALSE; //表示该空闲区块已分配给该进程
//该表项又可指向其他空闲区块，但还没有指向其他空闲区块
FirstAddress=free_table[k].address;
ProcessMemLength=free_table[k].length;
}
else
{
free_table[k].length=free_table[k].length - ProcessMemLength;
FirstAddress = free_table[k].address+free_table[k].length;
}
/*修改已分配区表*/
i=0;
while((used_table[i].UsedFlag == TRUE) && (i < MAX_PROCESSES)) /*寻找空表目*/
{
i++;
}
if(i>=MAX_PROCESSES) /*无表目填写已分分区*/
{
printf("无表目填写已分分区，错误\n");
/*修正空闲区表*/
if(free_table[k].AllocFlag == FALSE)
{
/*前面找到的是整个空闲分区*/
free_table[k].AllocFlag = TRUE;
}
else
{/*前面找到的是某个空闲分区的一部分*/
free_table[k].length=free_table[k].length+ProcessMemLength;
return;
}
}
else
{/*修改已分配表*/
used_table[i].address=FirstAddress;
used_table[i].length=ProcessMemLength;
used_table[i].UsedFlag=TRUE;
used_table[i].ProcessId = ProcessId;
}
return;
}/*主存分配函数结束*/
void reclaim(int ProcessId)
/*回收作业名为J的作业所占主存空间*/
{
int i,k,j,s,t;
long FirstAddress;//内存起始地址
long length; //该进程所需内存长度
/*寻找已分配表中对应登记项*/
s=0;
while(((used_table[s].ProcessId != ProcessId) || (used_table[s].UsedFlag == FALSE))
&& (s<MAX_PROCESSES))
{
s++;
}
if(s>=MAX_PROCESSES)/*在已分配表中找不到进程号为ProcessId的进程*/
{
printf("找不到该进程\n");
return;
}
/*修改已分配表*/
used_table[s].UsedFlag=FALSE;
/*取得归还分区的起始地址S和长度L*/
FirstAddress=used_table[s].address;
length=used_table[s].length;
j=-1;k=-1;i=0;
/*寻找回收分区的空闲上下邻，上邻表目k，下邻表目j*/
while((i < MAX_FREE_MEMORY_DISTRICT) && ((j == -1) || (k==-1)) )
{
if(free_table[i].AllocFlag == TRUE)
{
if(free_table[i].address+free_table[i].length==FirstAddress)/*找到上邻*/
{
k=i;
}
if(free_table[i].address==FirstAddress+length)/*找到下邻*/
{
j=i;
}
}
i++;
}
if(k!=-1) /*上邻空闲区*/
{
if(j!=-1)
/* 上邻空闲区，下邻空闲区，三项合并*/
{
free_table[k].length=free_table[j].length+free_table[k].length+length;
free_table[j].AllocFlag = FALSE;
}
else
{
/*上邻空闲区，下邻非空闲区，与上邻合并*/
free_table[k].length=free_table[k].length+length;
}
}
else /*上邻非空闲区*/
{
if(j!=-1)/*上邻非空闲区，下邻为空闲区，与下邻合并*/
{
free_table[j].address=FirstAddress;
free_table[j].length=free_table[j].length+length;
}
else
/*上下邻均为非空闲区，回收区域直接填入*/
{
/*在空闲区表中寻找空栏目*/
t=0;
while((free_table[t].AllocFlag == TRUE) && (t < MAX_FREE_MEMORY_DISTRICT))
{
t++;
}
if(t >= MAX_FREE_MEMORY_DISTRICT)/*空闲区表满,回收空间失败,将已分配表复原*/
{
printf("主存空闲表没有空间,回收空间失败\n");
used_table[s].UsedFlag = TRUE;
return;
}
free_table[t].address=FirstAddress;
free_table[t].length=length;
free_table[t].AllocFlag = TRUE;
}
}
return;
}/*主存回收函数结束*/
void main( )
{
int i, SelectItem;
long ProcessMemLength; //进程所需内存长度
int ProcessId;
/*空闲分区表初始化：*/
free_table[0].address=1000;
free_table[0].length=10000;
free_table[0].AllocFlag = TRUE;
for(i=1;i<MAX_FREE_MEMORY_DISTRICT;i++)
free_table[i].AllocFlag =FALSE;
/*已分配表初始化：*/
for(i=0;i<MAX_PROCESSES;i++)
used_table[i].UsedFlag=FALSE;
while(1)
{
cout<<"选择功能项（0-退出,1-分配主存,2-回收主存,3-显示主存）"<<endl;
cout<<"选择功项(0~3) :";
cin>>SelectItem;
switch(SelectItem)
{
case 0: exit(0); /*a=0程序结束*/
case 1: /*a=1分配主存空间*/
cout<<"请输入进程ID号和进程所需内存长度Length: ";
//scanf("%*c%c%f",&J,&xk);
cin >>ProcessId>>ProcessMemLength;
allocate(ProcessId,ProcessMemLength);/*分配主存空间*/
break;
case 2: /*a=2回收主存空间*/
cout<<"输入要回收分区的进程ID号";
cin>>ProcessId;
reclaim(ProcessId);/*回收主存空间*/
break;
case 3: /*a=3显示主存情况*/
/*输出空闲区表和已分配表的内容*/
cout<<"输出空闲内存区表：\n起始地址 长度"<<endl;
for(i=0;i<MAX_FREE_MEMORY_DISTRICT;i++)
{
if(free_table[i].AllocFlag == TRUE)
{
cout<<free_table[i].address<<" \t"<<free_table[i].length<<endl;
}
}
cout<<"输出已分配内存进程表：\n进程ID 起始地址 长度 分配标志"<<endl;
for(i=0;i<MAX_PROCESSES;i++)
{
if(used_table[i].UsedFlag == TRUE)
{
cout<<used_table[i].ProcessId<<" \t"<<used_table[i].address<<" \t";
cout<<used_table[i].length<<" \t"<<used_table[i].UsedFlag<<endl;
}
}
break;
default:printf("没有该选项\n");
}/*case*/
}/*while*/
}/*主函数结束*/
