注：查看全文请关注作者，或点击前往：主存储器空间的分配和回收的C++实现 实验七-2 主存储器空间的分配和回收 第一题 可变分区管理方式下的最先适应算法 实验题目

在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。

鄂州ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：18982081108（备注：SSL证书合作）期待与您的合作！提示

(1) 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：

（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

（3）采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。

由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图：

（4）当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图：

（5）请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

程序中使用的数据结构及符号说明

1. 结构体及其数组（数据结构）：空闲区条目和作业条目

struct item //空闲区条目和作业条目的结构体
{int len;   //长度
	int start; //起址(闭)
	int end;   //终址(开)=起址+长度
	int num;   //编号（用于作业）
};
item Free[10010]; //空闲区条目
item work[10010]; //主存中作业的条目

2. 整型变量

int Freecnt = 0;  //空闲区条目的数量
int workcnt;      //主存中作业的数量
int max_len;      //主存空间的大长度
int os_len;       //操作系统的长度

3. 自定义函数
   • bool cmp(item a, item b)：将条目按起始地址排序
   • void display_work()：输出作业表
   • display_Free()：输出空闲表
   • void init()：初始化主存
   • void alloc()：分配新作业
   • void release()：作业撤离，归还空间

源程序并附上注释

// 可变分区管理最先适应算法
#include#include 
#includeusing namespace std;

struct item //空闲区条目和作业条目的结构体
{int len;   //长度
	int start; //起址(闭)
	int end;   //终址(开)=起址+长度
	int num;   //编号（用于作业）
};
item Free[10010]; //空闲区条目
item work[10010]; //主存中作业的条目
int Freecnt = 0;  //空闲区条目的数量
int workcnt;      //主存中作业的数量
int max_len;      //主存空间的大长度
int os_len;       //操作系统的长度

bool cmp(item a, item b) //将条目按起始地址排序
{return a.start< b.start;
}

//输出作业表
void display_work()
{cout<< "作业表如下："<< endl;
	cout<< "---------------------------------"<< endl;
	cout<< "|序号|  作业  | 起址 | 长度 |"<< endl;
	for (int i = 1; i<= workcnt; i++)
	{cout<< "|"<< setw(4)<< i;
		cout<< "| 作业"<< left<< setw(3)<< work[i].num;
		cout<< "|"<< right<< setw(4)<< work[i].start<< "k |";
		cout<< right<< setw(4)<< work[i].len<< "k |";
		cout<< endl;
	}
	cout<< "---------------------------------"<< endl;
}

//输出空闲表
void display_Free()
{cout<< "空闲表如下："<< endl;
	cout<< "------------------------"<< endl;
	cout<< "|序号| 起址 | 长度 |"<< endl;
	for (int i = 1; i<= Freecnt; i++)
	{cout<< "|"<< setw(4)<< i;
		cout<< "|"<< right<< setw(4)<< Free[i].start<< "k |";
		cout<< right<< setw(4)<< Free[i].len<< "k |";
		cout<< endl;
	}
	cout<< "------------------------"<< endl;
}

//初始化主存
void init()
{cout<< "请输入主存空间的长度（长度单位均为k）：";
	cin >>max_len;
	//构建主存中的操作系统空间
	cout<< "请输入操作系统所占空间的长度：";
	cin >>os_len;
	//构建主存中的作业
	cout<< "请输入主存中作业的条目：";
	cin >>workcnt;
	for (int i = 1; i<= workcnt; i++)
	{cout<< "请输入第"<< i<< "个作业的起始地址、长度：";
		cin >>work[i].start >>work[i].len;
		work[i].end = work[i].start + work[i].len;
		work[i].num = i;
		if (work[i].end >max_len)
		{	cout<< "超出了主存空间的大长度，请重新输入"<< endl;
			i--;
		}
		else if (work[i].start< os_len)
		{	cout<< "与操作系统空间部分重叠，请重新输入"<< endl;
			i--;
		}
		else
		{	for (int j = 1; j< i; j++)
			{		if ((work[i].start >work[j].start) && (work[i].start< work[j].end))
				{cout<< "与作业"<< j<< "部分重叠，请重新输入"<< endl;
					i--;
					break;
				}
				else if ((work[j].start >work[i].start) && (work[j].start< work[i].end))
				{cout<< "与作业"<< j<< "部分重叠，请重新输入"<< endl;
					i--;
					break;
				}
			}
		}
	}
	sort(work + 1, work + 1 + workcnt, cmp);
	//OS相当于最开始的作业
	work[0].start = 0;
	work[0].len = os_len;
	work[0].end = os_len;
	//基于主存剩余空间构建空闲表
	for (int i = 1; i<= workcnt; i++)
	{if (work[i].start >work[i - 1].end) //起址大于上一项的尾地址，则构建空闲区
		{	Freecnt++; //空闲区个数加1
			Free[Freecnt].start = work[i - 1].end;
			Free[Freecnt].len = work[i].start - work[i - 1].end;
			Free[Freecnt].end = work[i].start;
		}
	}
	//主存末端的空闲区
	if (work[workcnt].end< max_len) //起址最后的作业的尾地址小于主存长度则存在
	{Freecnt++;
		Free[Freecnt].start = work[workcnt].end;
		Free[Freecnt].len = max_len - Free[Freecnt].start;
		Free[Freecnt].end = max_len;
	}
	display_work();
	display_Free();
	return;
}

//分配新作业
void alloc()
{cout<< "开始分配新作业："<< endl;
	int tempcnt = workcnt + 1; //作业编号的临时值
	cout<< "请输入作业"<< tempcnt<< "长度：";
	cin >>work[tempcnt].len;
	work[tempcnt].num = tempcnt;
	bool flag = 0; //分配是否成功的标记
	//遍历(未分配)空闲表
	for (int i = 1; i<= Freecnt; i++)
	{if (Free[i].len >= work[tempcnt].len) //空闲区长度大于等于作业长度，则可在此空闲区分配
		{	//确定作业起址
			work[tempcnt].start = Free[i].start;
			work[tempcnt].end = work[tempcnt].start + work[tempcnt].len;
			//修改空闲区
			Free[i].len -= work[tempcnt].len;
			Free[i].start += work[tempcnt].len;
			if (Free[i].len == 0) //若空闲区长度变为0，删除该空闲区
			{		Freecnt--;
				for (int j = i; j<= Freecnt; j++)
				{Free[j] = Free[j + 1];
				}
			}
			//标记：成功
			flag = 1;
			break;
		}
	}
	if (flag) //分配成功
	{workcnt++; //主存中作业数加一
		cout<< "分配成功！起址为"<< work[workcnt].start<< "K"<< endl;
		cout<< "----------------------"<< endl;
		sort(work + 1, work + 1 + workcnt, cmp); //按起址排序
	}
	else
	{cout<< "分配失败！"<< endl;
		cout<< "----------"<< endl;
	}
	display_work();
	display_Free();
	return;
}

//作业撤离，归还空间
void release()
{int temp_num;
	cout<< "请输入要撤离的作业编号：";
	cin >>temp_num;
	bool flag1 = 0; //标记作业是否存在于主存
	int pos;        //作业位置
	//寻找作业位置
	for (int i = 1; i<= workcnt; i++)
	{if (work[i].num == temp_num)
		{	flag1 = 1;
			pos = i;
			break;
		}
	}
	if (flag1 == 0)
	{cout<< "该作业不在主存中！";
		cout<< "------------------"<< endl;
		return;
	}
	//检查是否有与归还区下邻的空闲区
	bool flag2 = 0; //标记：是否有与归还区下邻的空闲区
	for (int i = 1; i<= Freecnt; i++)
	{//若有，合并成一个较大的空闲区
		if (work[pos].end == Free[i].start)
		{	flag2 = 1;
			Free[i].start = work[pos].start;
			Free[i].len += work[pos].len;
			break;
		}
	}
	//检查是否有与归还区上邻的空闲区
	bool flag3 = 0; //标记：是否有与归还区上邻的空闲区
	for (int i = 1; i<= Freecnt; i++)
	{//若有
		if (work[pos].end == Free[i].start)
		{	flag3 = 1;
			if (flag2) //若归还区已和下邻的空闲区合并，合成一个更大的空闲区
			{		Free[i].len += Free[i + 1].len;
				Free[i].end = Free[i + 1].end;
				//删除被合并的空闲区
				Freecnt--;
				for (int j = i + 1; j<= Freecnt; j++)
				{Free[j] = Free[j + 1];
				}
			}
			if (!flag2) //若归还区没有和下邻的空闲区合并
			{		Free[i].len += work[pos].len;
				Free[i].end = work[pos].end;
			}
			break;
		}
	}
	if (flag2 == 0 && flag3 == 0) //若没有相邻空闲区，则新建一个空闲区
	{Freecnt++; //空闲区个数加1
		//新建
		Free[Freecnt].start = work[pos].start;
		Free[Freecnt].len = work[pos].len;
		Free[Freecnt].end = work[pos].end;
		sort(Free + 1, Free + 1 + Freecnt, cmp); //排序
	}
	work[pos].start = 0x3f3f3f;              //将被释放的作业的起址改为无穷大
	sort(work + 1, work + 1 + workcnt, cmp); //排序
	workcnt--;                               //在主存中的作业总数减一
	display_work();
	display_Free();
	return;
}

int main()
{init();
	int op; //操作号
	while (1)
	{cout<< "请输入操作（1:分配新作业 2:撤离作业 0:结束）：";
		cin >>op;
		if (op == 1)
			alloc();
		else if (op == 2)
			release();
		else if (op == 0)
			break;
	}
	cout<< "程序结束"<< endl;
	return 0;
}

程序运行时的初值及运行结果 1

主存空间的长度（长度单位均为k）：128
操作系统所占空间的长度：10
主存中作业的条目：3
第1个作业的起始地址、长度：10 4
第2个作业的起始地址、长度：32 8
第3个作业的起始地址、长度：14 12

2

分配新作业：

作业4长度：6

3

撤离作业：

要撤离的作业编号：3

4

撤离作业：

要撤离的作业编号：2

第二题 分页式管理方式下的位示图 实验题目

在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。

提示

（1）分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。

（2） 假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占用了，那么位示图情况如下图：

（3） 当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。按找到的计算出对应的块号，其计算公式为：块号=j*8+i。其中，j表示找到的是第n个字节，i表示对应的是第n位。根据分配给作业的块号，为作业建立一张页表，页表格式：

（4）当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：

• 字节号 j=[块号/8] （[ ]表示取整）
• 位数 i={块号/8} （{ }表示取余）

（5）设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。

要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。

程序中使用的数据结构及符号说明

1. 结构体及其数组（数据结构），保存作业条目

   struct item                //作业条目的结构体
   {int page_num;   //页个数
   	int list[1001]; //页表
   	int num;        //编号
   	bool in;        //是否存在于主存
   };
   item work[1001];

2. 整型数组（数据结构）

   int bit_img[1001][1001];   //位示图
   int work_list[1001][1001]; //作业的页表

3. 整型变量

   int byte_num;              //位示图的字节数
   int free_block;            //空闲块数
   int work_cnt;              //总数

4. 自定义函数

   • void display_bit()：输出位示图
   • void display_page(int i)：输出作业work[i]的页表
   • void init()：初始化
   • void create()：分配新作业
   • void release()：回收作业

源程序并附上注释

#include#includeusing namespace std;

int bit_img[1001][1001];   //位示图
int work_list[1001][1001]; //作业的页表
int byte_num;              //位示图的字节数
int free_block;            //空闲块数
int work_cnt;              //总数
struct item                //作业条目的结构体
{int page_num;   //页个数
	int list[1001]; //页表
	int num;        //编号
	bool in;        //是否存在于主存
};
item work[1001];

//输出位示图
void display_bit()
{cout<< "位示图如下："<< endl;
	//表头
	cout<< "| 位数 |";
	for (int i = 0; i< 8; i++)
	{cout<< ' '<< setw(2)<< i<< " |";
	}
	cout<< endl;
	cout<< "|字节数|";
	for (int i = 0; i< 8; i++)
	{cout<< "____"
		<< "|";
	}
	cout<< endl;
	for (int j = 0; j< byte_num; j++)
	{cout<< "|  "<< setw(2)<< j<< "  |";
		for (int i = 0; i< 8; i++)
		{	cout<< ' '<< setw(2)<< bit_img[j][i]<< " |";
		}
		cout<< endl;
	}
	for (int i = 0; i< 48; i++)
	{cout<< '-';
	}
	cout<< endl;
	cout<< "当前空闲块数："<< free_block<< endl;
}

//输出作业work[i]的页表
void display_page(int i)
{cout<< "作业"<< work[i].num<< "的页表如下"<< endl;
	//表头
	cout<< "| 页号 | 块号 |"<< endl;
	for (int j = 0; j< work[i].page_num; j++)
	{cout<< "|  "<< setw(2)<< j<< "  | "<< setw(4)<< work[i].list[j]<< " |"<< endl;
	}
	cout<< "--------------"<< endl;
}

//初始化
void init()
{cout<< "请输入位示图的字节数：";
	cin >>byte_num;
	free_block = byte_num * 8;
	//初始化位示图每一位为0
	for (int j = 0; j< byte_num; j++)
	{for (int i = 0; i< 8; i++)
		{	bit_img[j][i] = 0;
		}
	}
	//初始化主存中的作业
	cout<< "请输入主存中作业的个数：";
	cin >>work_cnt;
	for (int i = 1; i<= work_cnt; i++)
	{cout<< "请输入第"<< i<< "个作业的信息"<< endl;
		cout<< "编号：";
		cin >>work[i].num;
		cout<< "页个数：";
		cin >>work[i].page_num;
		for (int j = 0; j< work[i].page_num; j++)
		{	cout<< "请输入页"<< j<< "所在的块为：";
			cin >>work[i].list[j];
			if (bit_img[work[i].list[j] / 8][work[i].list[j] % 8] == 1) //若该块被占用
			{		cout<< "该块已被占用，请重新输入"<< endl;
				j--;
			}
			else if (work[i].list[j] >8 * byte_num)
			{		cout<< "超过了主存大小，请重新输入"<< endl;
				j--;
			}
			else
			{		bit_img[work[i].list[j] / 8][work[i].list[j] % 8] = 1;
				free_block--;
			}
		}
		display_page(i);
		work[i].in = 1; //标记存在于主存
	}
	display_bit();
	return;
}

//分配新作业
void create()
{int i = work_cnt + 1;
	cout<< "请输入第"<< i<< "个作业的信息"<< endl;
	cout<< "编号：";
	cin >>work[i].num;
	cout<< "页个数：";
	cin >>work[i].page_num;
	for (int j = 0; j< work[i].page_num; j++)
	{cout<< "请输入页"<< j<< "所在的块为：";
		cin >>work[i].list[j];
		if (bit_img[work[i].list[j] / 8][work[i].list[j] % 8] == 1) //若该块被占用
		{	cout<< "该块已被占用，请重新输入"<< endl;
			j--;
		}
		else if (work[i].list[j] >8 * byte_num)
		{	cout<< "超过了主存大小，请重新输入"<< endl;
			j--;
		}
		else
		{	bit_img[work[i].list[j] / 8][work[i].list[j] % 8] = 1;
			free_block--;
		}
	}
	work[i].in = 1; //标记存在于主存
	work_cnt++;     //作业个数增加
	display_page(i);
	display_bit();
}

//回收作业
void release()
{int temp_num;
	cout<< "请输入要回收的作业：";
	cin >>temp_num;
	int pos; //作业的位置
	//寻找位置
	int i;
	for (i = 1; i<= work_cnt; i++)
	{if (work[i].num == temp_num && work[i].in) //编号相同且作业存在于主存
		{	pos = i;
			break;
		}
	}
	if (i == work_cnt + 1)
	{cout<< "作业"<< temp_num<< "不存在于主存！"<< endl;
		return;
	}
	for (int i = 0; i< work[pos].page_num; i++)
	{bit_img[work[pos].list[i] / 8][work[pos].list[i] % 8] = 0;
		free_block++;
	}
	work[pos].in = 0; //标记不存在于主存
	cout<< "回收成功！"<< endl;
	display_bit();
	return;
}

int main()
{init();
	int op; //操作号
	while (1)
	{cout<< "请输入操作（1:分配新作业 2:回收作业 0:结束）：";
		cin >>op;
		if (op == 1)
			create();
		else if (op == 2)
			release();
		else if (op == 0)
			break;
	}
	cout<< "程序结束"<< endl;
	return 0;
}

程序运行时的初值及运行结果 1

位示图的字节数：8
主存中作业的个数：2
第1个作业的信息
编号：1
页个数：6
页0所在的块为：0
页1所在的块为：1
页2所在的块为：9
页3所在的块为：11
页4所在的块为：13
页5所在的块为：24

第2个作业的信息
编号：2
页个数：4
页0所在的块为：4
页1所在的块为：5
页2所在的块为：6
页3所在的块为：31

2

分配新作业

第3个作业的信息
编号：3
页个数：5
页0所在的块为：2
页1所在的块为：10
页2所在的块为：18
页3所在的块为：26
页4所在的块为：34

3

回收作业2

思考题

结合实际情况，参考书本，仔细考虑各种主存分配算法的优缺点。把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时把作业的信息按页分散存放在主存的空闲块中，这样很可能导致每个作业按页装入主存中时，某一页还存在一定的空闲空间，思考如何才能有效的利用这些空闲区域。

各种主存分配算法

1. 最先适应算法：地址递增，顺序查找，第一个能满足的即分配给进程。

   优点：最简单的，而且通常也是最好和最快的。

   缺点：会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。

2. 邻近适应算法：循环首次适应算法。

   优点：比较块

   缺点：常常会导致在内存的末尾分配空间，分裂成小碎片。

3. 最佳适应算法：容量递增，找到第一个能满足要求的空闲分区。

   优点：每次分配给文件的都是最合适该文件大小的分区。

   缺点：内存中留下许多难以利用的小的空闲区。

4. 最坏适应算法：容量递减，找到第一个能满足要求的分区。

   优点：尽可能地利用存储器中大的空闲区。

   缺点：容易导致没有可用的大的内存块造成浪费。

空闲空间可以通过紧凑来解决，就是操作系统不时地对进程作业进行移动和整理。

实验心得

1. 第一个实验Allocation_and_recycling_of_main_storage_space算法实现的关键点就在于置换算法的设计。了解该算法后，选用合适的数据结构作为内存中的页队列，并按照算法思想对队列进行维护即可。通过该实验，我对Allocation_and_recycling_of_main_storage_space及其他置换算法有了更加深入的理解。
   的大小分页，作业装入主存时把作业的信息按页分散存放在主存的空闲块中，这样很可能导致每个作业按页装入主存中时，某一页还存在一定的空闲空间，思考如何才能有效的利用这些空闲区域。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站题目：主存储器空间的分配和回收模拟的C++实现-创新互联
网页URL：http://chengdu.cdxwcx.cn/article/csoceg.html