实验4  内存管理

一、实验目的

1、对内存管理的相关内容做进一步的理解。

2、了解内存管理的主要任务。

3、了解内存管理任务的主要实现方法。

4、通过编程加深理解内存的分配、回收等主要算法的原理。

二、实验内容及要求

1、在该实验中，采用可变分区方式完成对存储空间的管理（即存储空间的分配与回收工作）。

2、设计用来记录主存使用情况的数据结构：已分区表和空闲分区表。

3、在设计好的数据结构上设计一个主存分配算法，要求实现的基本功能操作有：寻找空闲分区，空闲分区表的修改，已分区表的修改。

4、在设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。

三、实验报告

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

2、给出主要算法的流程图。

3、给出测试数据和运行结果，要求系统每进行一次分配或回收，都要给出内存映像图或已分配表及未分配表以观察内存的变化。

代码：
// OS4.1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include<stdio.h>
#include<stdlib.h>
#define OK 1    //完成 
#define ERROR 0 //出错
typedef int Status;
typedef struct free_table//定义一个空闲区说明表结构
{
	int num; //分区序号
	long address; //起始地址
	long length;//分区大小 
	int state; //分区状态 
}ElemType;
typedef struct Node//线性表的双向链表存储结构
{
	ElemType data;
	struct Node*prior;//前趋指针
	struct Node *next;//后继指针
}Node, *LinkList;
LinkList first;//头结点
LinkList end;//尾结点
int flag;//记录要删除的分区序号


Status Initblock()//开创带头结点的内存空间链表
{
	first = (LinkList)malloc(sizeof(Node));
	end = (LinkList)malloc(sizeof(Node));
	first->prior = NULL;
	first->next = end;
	end->prior = first;
	end->next = NULL;
	end->data.num = 1;
	end->data.address = 40;
	end->data.length = 600;
	end->data.state = 0;
	return OK;
}

void sort()//分区序号重新排序
{
	Node *p = first->next, *q;
	q = p->next;
	for (; p != NULL; p = p->next)
	{
		for (q = p->next; q; q = q->next)
		{

			if (p->data.num >= q->data.num)
			{
				q->data.num += 1;
			}
		}
	}
}//显示主存分配情况 
void show()
{
	int flag = 0;//用来记录分区序号
	Node *p = first;
	p->data.num = 0;
	p->data.address = 0;
	p->data.length = 40;
	p->data.state = 1;
	sort();
	printf("\n\t\t》主存空间分配情况《\n");
	printf("**********************************************************\n\n");
	printf("分区序号\t起始地址\t分区大小\t分区状态\n\n");
	while (p)
	{
		printf("%d\t\t%d\t\t%d", p->data.num, p->data.address, p->data.length);
		if (p->data.state == 0)
			printf("\t\t空闲\n\n");
		else
			printf("\t\t已分配\n\n");
		p = p->next;
	}
	printf("**********************************************************\n\n");
}//首次适应算法
Status First_fit(int request) {//为申请作业开辟新空间且初始化
	Node *p = first->next;
	LinkList temp = (LinkList)malloc(sizeof(Node));
	temp->data.length = request;
	temp->data.state = 1;
	p->data.num = 1;
	while (p)
	{
		if ((p->data.state == 0) && (p->data.length == request))
		{//有大小恰好合适的空闲块
			p->data.state = 1;
			return OK;
			break;
		}
		else if ((p->data.state == 0) && (p->data.length > request))
		{//有空闲块能满足需求且有剩余
			temp->prior = p->prior;
			temp->next = p;
			temp->data.address = p->data.address;
			temp->data.num = p->data.num;
			p->prior->next = temp;
			p->prior = temp;
			p->data.address = temp->data.address + temp->data.length;
			p->data.length -= request;
			p->data.num += 1;
			return OK;
			break;
		}
		p = p->next;
	}
	return ERROR;
}//最佳适应算法
Status Best_fit(int request)
{
	int ch;//记录最小剩余空间
	Node *p = first;
	Node *q = NULL;//记录最佳插入位置
	LinkList temp = (LinkList)malloc(sizeof(Node));
	temp->data.length = request;
	temp->data.state = 1;
	p->data.num = 1;
	while (p)//初始化最小空间和最佳位置
	{
		if ((p->data.state == 0) && (p->data.length >= request))
		{
			if (q == NULL)
			{
				q = p;
				ch = p->data.length - request;
			}
			else if (q->data.length > p->data.length)
			{
				q = p;
				ch = p->data.length - request;
			}
		}
		p = p->next;
	}

	if (q == NULL) return ERROR;
	//没有找到空闲块
	else if (q->data.length == request)
	{
		q->data.state = 1;
		return OK;
	}
	else
	{
		temp->prior = q->prior;
		temp->next = q;
		temp->data.address = q->data.address;
		temp->data.num = q->data.num;
		q->prior->next = temp;
		q->prior = temp;
		q->data.address += request;
		q->data.length = ch;
		q->data.num += 1;
		return OK;
	}
	return OK;
}//最差适应算法
Status Worst_fit(int request)
{
	int ch;//记录最大剩余空间
	Node *p = first->next;
	Node *q = NULL;//记录最佳插入位置
	LinkList temp = (LinkList)malloc(sizeof(Node));
	temp->data.length = request;
	temp->data.state = 1;
	p->data.num = 1;
	while (p)//初始化最大空间和最佳位置
	{
		if (p->data.state == 0 && (p->data.length >= request))
		{
			if (q == NULL)
			{
				q = p;
				ch = p->data.length - request;
			}
			else if (q->data.length < p->data.length)
			{
				q = p;
				ch = p->data.length - request;
			}
		}
		p = p->next;
	}
	if (q == NULL) return ERROR;//没有找到空闲块
	else if (q->data.length == request)
	{
		q->data.length = 1;
		return OK;
	}
	else
	{
		temp->prior = q->prior;
		temp->next = q;
		temp->data.address = q->data.address;
		temp->data.num = q->data.num;
		q->prior->next = temp;
		q->prior = temp;
		q->data.address += request;
		q->data.length = ch;
		q->data.num += 1;
		return OK;
	} return OK;
}//分配主存
Status allocation(int a)
{

	int request;//申请内存大小
	printf("请输入申请分配的主存大小(单位:KB):");
	scanf_s("%d", &request);
	if (request < 0 || request == 0)
	{
		printf("分配大小不合适，请重试！");
		return ERROR;
	}

	switch (a)
	{
	case 1://默认首次适应算法
		if (First_fit(request) == OK)
			printf("\t****分配成功！****");
		else printf("\t****内存不足，分配失败！****");
		return OK;
		break;
	case 2://选择最佳适应算法
		if (Best_fit(request) == OK)
			printf("\t****分配成功！****");
		else printf("\t****内存不足，分配失败！****");
		return OK;
		break;
	case 3://选择最差适应算法
		if (Worst_fit(request) == OK)
			printf("\t****分配成功！****");
		else printf("\t****内存不足，分配失败！****");
		return OK;
		break;
	}
}
Status deal1(Node *p)//处理回收空间
{
	Node *q = first;
	for (; q != NULL; q = q->next)
	{
		if (q == p)
		{
			if (q->prior->data.state == 0 && q->next->data.state != 0)
			{
				q->prior->data.length += q->data.length;
				q->prior->next = q->next;
				q->next->prior = q->prior;
				q = q->prior;
				q->data.state = 0;
				q->data.num = flag - 1;
			}
			if (q->prior->data.state != 0 && q->next->data.state == 0)
			{
				q->data.length += q->next->data.length;
				q->next = q->next->next;
				q->next->next->prior = q;
				q->data.state = 0;
				q->data.num = flag;
			}
			if (q->prior->data.state == 0 && q->next->data.state == 0)
			{
				q->prior->data.length += q->data.length;
				q->prior->next = q->next;
				q->next->prior = q->prior;
				q = q->prior;
				q->data.state = 0;
				q->data.num = flag - 1;
			}
			if (q->prior->data.state != 0 && q->next->data.state != 0)
			{
				q->data.state = 0;
			}
		}
	}
	return OK;
}
Status deal2(Node *p)//处理回收空间
{
	Node *q = first;
	for (; q != NULL; q = q->next)
	{
		if (q == p)
		{
			if (q->prior->data.state == 0 && q->next->data.state != 0)
			{
				q->prior->data.length += q->data.length;
				q->prior->next = q->next;
				q->next->prior = q->prior;
				q = p->prior;
				q->data.state = 0;
				q->data.num = flag - 1;
			}
			if (q->prior->data.state != 0 && q->next->data.state == 0)
			{
				q->data.state = 0;
			}
			if (q->prior->data.state == 0 && q->next->data.state == 0)
			{
				q->prior->data.length += q->data.length;
				q->prior->next = q->next;
				q->next->prior = q->prior;
				q = q->prior;
				q->data.state = 0;
				q->data.num = flag - 1;
			}
			if (q->prior->data.state != 0 && q->next->data.state != 0)
			{
				q->data.state = 0;
			}
		}
	}
	return OK;
}//主存回收
Status recovery(int flag)
{
	Node *p = first;
	for (; p != NULL; p = p->next)
	{
		if (p->data.num == flag)
		{
			if (p->prior == first)
			{
				if (p->next != end)//当前P指向的下一个不是最后一个时
				{
					if (p->next->data.state == 0)//与后面的空闲块相连
					{
						p->data.length += p->next->data.length;
						p->next->next->prior = p;
						p->next = p->next->next;
						p->data.state = 0;
						p->data.num = flag;
					}
					else p->data.state = 0;
				}
				if (p->next == end)//当前P指向的下一个是最后一个时
				{
					p->data.state = 0;
				}
			}//结束if(p->prior==block_first)的情况
			else if (p->prior != first)
			{
				if (p->next != end)
				{
					deal1(p);
				}
				else
				{
					deal2(p);
				}
			}//结束if(p->prior!=block_first)的情况
		}//结束if(p->data.num==flag)的情况
	}
	printf("\t****回收成功****");
	return OK;
}//主函数
void main()
{
	int i;//操作选择标记
	int a;//算法选择标记
	printf("**********************************************************\n");
	printf("\t\t用以下三种方法实现主存空间的分配\n");
	printf("\t(1)首次适应算法\t(2)最佳适应算法\t(3)最差适应算法\n");
	printf("**********************************************************\n");
	printf("\n");
	printf("请输入所使用的内存分配算法:");
	scanf_s("%d", &a);
	while (a < 1 || a>3)
	{
		printf("输入错误，请重新输入所使用的内存分配算法:\n");
		scanf_s("%d", &a);
	}
	switch (a)
	{
	case 1:printf("\n\t****使用首次适应算法：****\n"); break;
	case 2:printf("\n\t****使用最佳适应算法：****\n"); break;
	case 3:printf("\n\t****使用最坏适应算法：****\n"); break;
	}
	Initblock();//开创空间表
	while (1)
	{
		show();
		printf("\t1: 分配内存\t2: 回收内存\t0: 退出\n");
		printf("请输入您的操作：");
		scanf_s("%d", &i);
		if (i == 1)
			allocation(a);//分配内存
		else if (i == 2)//内存回收
		{
			printf("请输入您要释放的分区号：");
			scanf_s("%d", &flag);
			recovery(flag);
		}
		else if (i == 0)
		{
			printf("\n退出程序\n");
			break;//退出
		}
		else//输入操作有误
		{
			printf("输入有误，请重试！");
			continue;
		}
	}
}

运行结果：



分配和回收测试的情况很多，自己试自己体会吧。
转载自：操作系统课程设计内存管理含源代码（百度文库）

  1 本章要点：

  2     1。储存管理任务。

  3     2。内存划分与分配技术。

  4     3。程序装入技术。

  5     4。简单存储管理技术。

  6     5。虚拟存储管理技术。

  7 

  8 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

  9 储存管理任务：

 10 

 11 （一）存储分配：

 12     1。基本任务：管理内存空间的分配与回收。

 13         (1)分配基本内存空间。

 14         (2)增加新的内存空间－动态申请／释放内存空间。

 15         (3)回收内存空间。

 16 

 17     2。内存管理的数据结构：

 18         位示图、空闲页框表等

 19 

 20     3。内存分配步骤：

 21         1。根据内存分配算法，寻找空闲的满足条件的内存空间进行分配。

 22         2。更新进程的资源分配清单、内存分配情况清单等数据结构。

 23 

 24     4。内存空间的回收：

 25 

 26 

 27 （二）地址映射：

 28     逻辑地址（相对地址）：一般从0开始

 29         高级语言使用符号地址，编译、连接后符号地址变成逻辑地址，编译、连接程

 30         序会自动计算逻辑地址。

 31     物理地址（绝对地址）：标识内存中的每一个储存单元。

 32 

 33 

 34     静态映射：静态重定位

 35     1。地址映射：逻辑地址－>物理地址。

 36     2。重定位：对地址（指令和数据）进行修改。

 37     3。静态重定位：地址转变只在程序装入时一次完成。不适合多道程序设计。

 38 

 39 

 40     动态映射：动态重定位

 41     地址管理部件

 42 

 43 

 44 （三）存储保护：

 45     防止地址越界，防止操作越权。

 46 

 47     存储保护的实现：

 48     1。只能在程序执行过程中动态进行。

 49     2。地址管理部件。

 50 

 51 （四）储存共享：

 52     1。多个进程物理空间有相交的部分。

 53     2。代码／数据共享。

 54     3。代码共享－节约储存空间，数据共享－实现通信。

 55 

 56     共享代码：程序可重入（代码区和数据区分开）

 57         创建新进程时，不需要为该进程的代码部分另外申请内存空间，只需要将该进

 58         程PCB中的进程代码空间的地址指向已有的代码空间地址。

 59 

 60         进程的数据区，要么等到操作系统为其分配相应的内存空间以后，将数据区

 61         地址填写在PCB中；要么由进程运行时向OS动态申请。

 62 

 63 

 64 （五）储存扩充

 65     虚拟储存系统

**
页式存储管理
**
一、页式存储管理的基本原理
【页式存储管理的基本原理】

分页存储器将主存划分成多个大小相同的页架
受页架尺寸限制，程序的逻辑地址也自然分页
不同的页可以放在不同页架中，不需要连续
页表用于维系进程的主存完整性



【页式存储管理中的地址】

页式存储管理的逻辑地址由两部分组成：页号和单元号，逻辑地址形式：


页式存储管理的物理地址也有两部分组成：页架号和单元号，物理地址形式：


地址转换（直接把页号变为页架号）可以通过查页表完成

【页式存储管理的地址转换思路】


【页式存储管理的内存分配/去配】

可用一张位示图来记录主存分配情况
建立进程页表维护主存逻辑完整性



【页的共享】

页式存储管理能够实现多个进程共享程序和数据
数据共享：不同进程可以使用不同页号共享数据页
程序共享：不同进程必须使用相同页号共享代码页

#共享代码中的（JMP<页内地址>）指令，使用不同页号时做不到

二、页式存储管理的地址转换
【页式存储管理的地址转换代价】

页表放在主存：每次地址转换必须访问两次主存

1.按页号读出页表中的相应页架号

2.按计算出来的绝对地址进行读写
存在问题：降低了存取速度
解决方法：利用Cache存放部分页表

【页式存储管理的快表】

为提高地址转换速度，设置一个专用的高速存储器，用来存放页表的一部分
快表：存放在高速存储器中的页表部分
快表表项：页号，页架号
这种高速存储器是联想存储器，即按照内容寻址，而非按照地址访问

【引入快表后的地址转换代价】

采用快表后，可以加快地址转换速度
假定主存访问时间为200毫微秒，快表访问时间为40毫微秒，查快表的命中率是90%。平均地址转换代价为：（200+40）*90%+（200+200）*10%=256毫微秒
比两次访问主存的时间（400毫微秒）下降了36%

【基于快表的地址转换流程】

按逻辑地址中的页号查快表
若该页已在快表中，则由页架号和单元号形成绝对地址
若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中
当快表填满后，又要登记新页时，则需在快表中按一定策略淘汰一个旧登记项

【多道程序环境下的进程表】

进程表中登记了每个进程的页表
进程占有处理器运行时，其页表起始地址和长度送入页表控制寄存器



【多道程序环境下的地址转换】


三、页式虚拟存储管理
【页式虚拟存储管理的基本思想】

把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后，根据执行行为，动态调入不在主存的页，同时进行必要的页面调出
现代OS的主流存储管理技术
首次只把进程第一页信息装入主存，称为请求页式存储管理

【页式虚拟存储管理的页表】

需要扩充页表项，指出

#每页的虚拟地址、实际地址

#主存驻留标志、写回标志、保护标志、引用标志、可移动标志



【页式虚拟管理的实现】

CPU处理地址

#若页驻留，则获得块号形成绝对地址

#若页不在内存，则CPU发出缺页中断
OS处理缺页中断

#若有空闲页架，则根据辅存地址调入页，更新页表与快表等

#若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表

【页式虚拟存储管理的地址转换】


【缺页中断的处理流程】


四、页面调度
【页面调度】

当主存空间已满又需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去
选择淘汰页的工作称为页面调度
选择淘汰页的算法称为页面调度算法
页面调度算法如果设计不当，会出现（刚被淘汰的页面立即又要调入，并如此反复）这种现象称为抖动或颠簸

【缺页中断率】

假定进程P共n页，系统分配页架数m个
P运行中成功访问次数为S，不成功访问次数为F，总访问次数A=S+F
缺页中断率定义为：f=F/A
缺页中断率是衡量存储管理性能和用户编程水平的重要依据

【影响缺页中断率的因素】

分配给进程的页架数：可用页架数越多，则缺页中断率就越低
页面的大小：页面尺寸越大，则缺页中断率就越低
用户的程序编制方法：在大数据量情况下，对缺页中断率也有很大影响

【用户编程的例子】

程序将数组置为“0”，假定仅分得一个主存页架，页面尺寸为128个字，数组元素按行存放，开始时第一页在主存



【OPT页面调度算法】

理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页
该算法由Belady提出，称Belady算法，又称最佳算法（OPT）
OPT只可模拟，不可实现

【先进先出FIFO页面调度算法】

总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页（常驻的除外）
模拟的是程序执行的顺序性，有一定合理性

【最近最少用LRU页面调度算法】

淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到
模拟了程序执行的局部属性，既考虑了循环性又兼顾了顺序性
严格实现的代价大（需要维持特殊队列）

【LRU算法的模拟实现】

每页建一个引用标志，供硬件使用
设置一个时间间隔中断：中断时页引用标志置0
地址转换时，页引用标志置1
淘汰页面时，从页引用标志为0的页中随机选择
时间间隔多长是个难点

【最不常用LFU页面调度算法】

淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
基于时间间隔中断，并给每一页设置一个计数器
时间间隔中断发生后，所有计数器清0
每访问页1次就给计数器加1
选择计数值最小的页面淘汰

【时钟CLOCK页面调度算法】

采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表
队列指针则相当于钟表面上的表针，指向可能要淘汰的页面
使用页面引用标志位

【CLOCK算法的工作流程】

页面调入主存时，其引用标志位置1
访问主存页面时，其引用标志位置1
淘汰页面时，从指针当前指向的页面开始扫面循环队列

#把所遇到的引用标志位是1的页面的引用标志位清0，并跳过

#把所遇到的引用标志位是0的页面淘汰，指针推进一步

五、反置页表
【反置页表的提出】

页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用
为页式存储管理设置专门硬件机构
内存管理单元MMU：CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面
反置页表IPT：MMU用的数据结构

【反置页表的基本设计思想】

针对内存中的每个页架建立一个页表，按照块号排序
表项包含：正在访问该页架的进程标识、页号及特征位，和哈希链指针等
用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换

【反置页表的页表项】

页号：虚拟地址页号
进程标志符：使用该页的进程号（页号和进程标志符结合起来标志一个特定进程的虚拟地址空间的一页）
标志位：有效、引用、修改、保护和锁定等标志信息
链指针：哈希链

【基于反置页表的地址转换过程】

MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT（反置页表）的一个表目
MMU遍历哈希链找到所需进程的虚页号，该项的索引就是页架号，通过拼接移位便可生成物理地址
若遍历整个反置页表中未能找到匹配表项，说明该页不在内存，产生缺页中断，请求操作系统调入

【反置页表下的地址转换示意】



未显示选择淘汰页面，同样由MMU完成

**
段式存储管理
**
一、段式存储管理
【段式程序设计】

每个程序可由若干段组成，每一段都可以从“0”开始编址，段内的地址是连续的
分段存储器的逻辑地址由两部分组成

#段号：单元号

#和页式存储管理（段号：单元号）有本质区别。“段号：单元号”是用户程序设计自己设定的。而“页号：单元号”是系统自动切割的，用户并不知道。所以分页存储器是用户编程原则上不可见的，除了性能优化。而分段存储器是用户可控制的

【程序的分段结构】


【段式存储管理的基本思想】

段式存储管理基于可变分区存储管理实现，一个进程要占用多个分区
硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段、附加段），供地址转换使用
存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位

【段式存储管理的地址转换流程】


【段的共享】

通过不通进程段表中的项指向同一个段基址来实现
对共享段的信息必须进行保护，如规定只能读出不能写入，不满足保护条件则产生保护中断

二、段式虚拟存储管理
【段式虚拟存储管理的基本思想】

把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把他们动态装入
段式虚拟存储管理中断的调进调出是由OS自动实现的，对用户透明
与段覆盖基数不同，它是用户控制的主存扩充技术，OS不感知

【段式虚拟存储管理的段表扩充】

段表的扩充

#特征位：00（不在内存）01（在内存）11（共享段）

#存取权限：00（可执行）01（可读）11（可写）

#扩充位：0（固定长）1（可扩充）

#标志位：00（未修改）01（已修改）11（不可移动）



【段式虚拟存储管理的地址转换】


三、段页式存储管理
【段页式存储管理的基本思想】

段式程序设计可以基于页式存储管理实现
每一段不必占据连续的存储空间，可存放在不连续的主存页架中
能够扩充位段页式虚拟存储管理
装入部分段，或者装入段中部分页面

【段页式存储管理的段表和页表】


【段页式存储管的地址转换】


【段页式虚拟存储管理的地址转换】

动态存储管理
为什么需要动态存储管理
程序中需要用变量（各种简单类型变量、数组变量等）保存被处理的数据和各种状态信息，变量在使用之前必须安排好存储：放在哪里、占据多少存储单元，等等，这个工作被称作存储分配。用机器语言写程序时，所有存储分配问题都需要人处理，这个工作琐碎繁杂、很容易出错。在用高级语言写程序时，人通常不需要考虑存储分配的细节，主要工作由编译程序在加工程序时自动完成。这也是用高级语言编程序效率较高的一个重要原因。
C程序里的变量分为几种。外部变量、局部静态变量的存储问题在编译时确定，其存储空间的实际分配在程序开始执行前完成。程序执行中访问这些变量，就是直接访问与之对应的固定位置。对于局部自动变量，在执行进入变量定义所在的复合语句时为它们分配存储。应该看到，这种变量的大小也是静态确定的。例如，局部自动数组的元素个数必须用静态可求值的表达式描述。这样，一个函数在调用时所需的存储量（用于安放该函数里定义的所有自动变量）在编译时就完全确定了。函数定义里描述了所需要的自动变量和参数，定义了数组的规模，这些就决定了该函数在执行时实际需要的存储空间大小。
以静态方式安排存储的好处主要是实现比较方便，效率高，程序执行中需要做的事情比较简单。但这种做法也形成了对写程序方式的一种限制，使某些问题在这个框架里不好解决。举个简单的例子：假设现在要写一个处理一组学生成绩数据的程序，被处理数据需要存储，因此应该定义一个数组。由于每次使用程序时要处理的成绩的项数可能不同，我们可能希望在程序启动后输入一个表示成绩项数的整数（或通过命令行参数提供一个整数，问题完全一样）。对于这个程序，应该怎样建立其内部的数据表示呢？
问题在于写程序时怎样描述数组元素的个数。一种理想方式是采用下面的程序框架：
int n;
...
scanf("%d", &n);
double scores[n];
... /* 读入成绩数据，然后进行处理 */
但是这一做法行不通。这里存在两个问题：首先是变量定义不能出现在语句之后。这个问题好解决，可以引进一个复合语句，把scores的定义放在复合语句里。第二个问题更本质，在上面程序段里，描述数组scores大小的表达式是一个变量，它无法静态求出值。也就是说，这个数组大小不能静态确定，C语言不允许以这种方式定义数组。这个问题用至今讨论过的机制都无法很好解决。目前可能的解决方案有（一些可能性）：
1.         分析实际问题，定义适当大小的数组，无论每次实际需要处理多少数据都用这个数组。前面的许多程序采用了这种做法。如果前期分析正确，这样做一般是可行的。但如果某一次实际需要处理的数据很多，程序里定义数组不够大，这个程序就不能用了（当然，除非使用程序的人有源程序，而且知道如果修改程序，如何编译等等。在现实生活中，这种情况是例外）。
2.         定义一个很大的数组，例如在所用的系统里能定义的最大数组。这样做的缺点是可能浪费大量空间（存储器是计算机系统里最重要的一种资源）。如果在一个复杂系统里，有这种情况的数组不止一个，那就没办法了。如果都定义得很大，系统可能根本无法容纳它们。而在实际计算中，并不是每个数组都真需要那么大的空间。
上面只是一个说明情况的例子。一般情况是：许多运行中的存储需求在写程序时无法确定。通过定义变量的方式不能很好地解决这类问题。为此就需要一种机制，使我们能利用它写出一类程序，其中可以根据运行时的实际存储需求分配适当大小的存储区，以便存放到在运行中才能确定大小的数据组。C语言为此提供了动态存储管理系统。说是“动态”，因为其分配工作完全是在动态运行中确定的，与程序变量的性质完全不同。程序里可以根据需要，向动态存储管理系统申请任意大小的存储块。
现在有了动态存储分配，可以要求系统分配一块存储，但是怎么能在程序里掌握和使用这种存储块呢？对于普通的变量，程序里通过变量名去使用它们。动态分配的存储块无法命名（命名是编程序时的手段，不是程序运行中可以使用的机制），因此需要另辟蹊径。一般的语言里都通过指针实现这种访问，用指针指向动态分配得到的存储块（把存储块的地址存入指针），而后通过对指针的间接操作，就可以去使用存储块了。引用动态分配的存储块是指针的最主要用途之一。
与动态分配对应的是动态释放。如果以前动态分配得到的存储块不再需要了，就应该考虑把它们交回去。动态分配和释放的工作都由动态存储管理系统完成，这是支持程序运行的基础系统（称为程序运行系统）的一部分。这个系统管理一片存储区，如果需要存储块，就可以调用动态分配操作申请一块存储；如果以前申请的某块存储不需要了，可以调用释放操作将它交还管理系统。动态存储管理系统管理的这片存储区通常称为堆（heap）。
7.6.2 C语言的动态存储管理机制
C语言的动态存储管理由一组标准库函数实现，其原型在标准文件<stdlib.h>里描述，需要用这些功能时应包含这个文件。与动态存储分配有关的函数共有四个：
1）存储分配函数malloc()。函数原型是：
void *malloc(size_t n);
这里的size_t是标准库里定义的一个类型，它是一个无符号整型。这个整型能够满足所有对存储块大小描述的需要，具体相当于哪个整型由具体的C系统确定。malloc的返回值为(void *)类型（这是通用指针的一个重要用途），它分配一片能存放大小为n的数据的存储块，返回对应的指针值；如果不能满足申请（找不到能满足要求的存储块）就返回NULL。在使用时，应该把malloc的返回值转换到特定指针类型，赋给一个指针。
例：利用动态存储管理机制，前面提出的问题可以采用如下方式解决：
int n;
double *scores;
...
scanf("%d", &n);
scores = (double *)malloc(n * sizeof(double));
if (scores == NULL) {
    .... /* 出问题时的处理，根据实际情况考虑 */
}
..scores[i] ... *(scores+j) ... /* 读入数据进行处理 */
调用malloc时，应该利用sizeof计算存储块的大小，不要直接写整数，以避免不必要的错误。此外，每次动态分配都必须检查成功与否，并考虑两种情况的处理。
注意，虽然这里的存储块是通过动态分配得到的，但是它的大小也是确定的，同样不允许越界使用。例如上面程序段分配的块里能存n个双精度数据，随后的使用就必须在这个范围内进行。越界使用动态分配的存储块，尤其是越界赋值，可能引起非常严重的后果，通常会破坏程序的运行系统，可能造成本程序或者整个计算机系统垮台。
2）带计数和清0的动态存储分配函数calloc。函数原型是：
void *calloc(size_t n, size_t size);
参数size意指数据元素的大小，n指要存放的元素个数。calloc将分配一块存储，其大小足以存放n个大小各为size的元素，分配之后还把存储块里全部清0（初始化为0值）。如果不能满足要求就返回NULL。
例：前面程序片段里的存储分配也可以用下面语句实现：
scores = (double *)calloc(n, sizeof(double));
注意，malloc对于所分配区域不做任何事情，calloc对整个区域进行初始化，这是两个函数的主要不同点。另外就是两个函数的参数不同，calloc主要是为了分配“数组”。我们可以根据情况选用。
3）动态存储释放函数free。原型是：
void free(void *p);
函数free释放指针p所指的存储块。指针p的值（存储块地址）必须是以前通过动态存储分配函数分配得到的。如果当时p的值是空指针，free就什么也不做。
注意，调用free(p) 不会改变p的值（在函数里不可能改变值参数p），但被p指向的存储块的内容却可能变了（可能由于存储管理的需要）。释放后不允许再通过p去访问已释放的块，否则也可能引起灾难性后果。
为了保证动态存储区的有效使用，在知道某个动态分配的存储块不再用时，就应及时将它释放，这应该成为习惯。释放动态存储块只能通过调用free完成。下面是一个示例：
int fun (...) {
    int *p;
    ... ,..
    p = (int *)malloc(...);
    ...
    free(p);
    return ...;
}
这里的free(p)在fun退出前释放了在函数里分配的存储块。如果没有最后的这个free(p)，函数里分配的这个存储块就可能丢掉。因为fun的退出也是p的存在期结束，此后p保存的信息（动态存储块地址）就找不到，这个块就可能丢掉了[1]。丢失动态分配块的情况称为动态存储的“流失”。对于需要长时间执行的程序，存储流失就可能成为严重问题，可能造成程序执行一段后被迫停止。因此，实际系统不能容忍这种情况的发生。
4）分配调整函数realloc。函数原型是：
void *realloc(void *p, size_t n);
这个函数用于更改以前的存储分配。在调用realloc时，指针变量p的值必须是以前通过动态存储分配得到的指针，参数n表示现在需要的存储块大小。realloc在无法满足新要求时返回NULL，同时也保持p所指的存储块的内容不变。如果能够满足要求，realloc就返回一片能存放大小为n的数据的存储块，并保证该块的内容与原块一致：如果新块较小，其中将存放着原块里大小为n的范围内的那些数据；如果新块更大，原有数据存在新块的前面一部分里，新增的部分不自动初始化。如果分配成功，原存储块的内容就可能改变了，因此不允许再通过p去使用它。
假如要把一个现有的双精度块改为能存放m个双精度数，可以用下面程序段处理：
q = (double *)realloc(p, m * sizeof(double));
if (q == NULL) {
    ... ... /* 分配不成功，p仍指向原块，处理这种情况 */
} 
else {
    p = q;
    ... ... /* 分配成功，通过p可以去用新的存储块 */
}
上面的q是另一个双精度指针。这里没有把realloc的返回值赋给直接p，是为了避免分配失败时丢掉原存储块。如果直接赋值，指针p原来的值就会丢掉。如果当时的分配没有成功，p将被赋空指针值，原来那个块可能就再也找不到了（除非在这次调整前已经让另一个指针指向了它）。
请注意：通过动态分配得到的块是一个整体，只能作为一个整体去管理（无论是释放还是改变大小）。在调用free(p) 或者realloc(p, ...) 时，p当时的值必须是以前通过调用存储分配函数得到的，绝不能对指在动态分配块里其他位置的指针调用这两个函数（更不能对并不指向动态分配块的指针使用它们），那样做的后果不堪设想。
7.6.3 两个程序实例
例：修改筛法程序，令它由命令行参数得到所需的整数范围。如果没有命令行参数，就要求用户输入一个确定范围的整数值。
先考虑main的设计。为了使程序更加清晰，我们可以考虑把筛法计算写成一个函数。这里还有一个小问题：如果用户通过命令行参数给出工作范围，程序就需要从命令行参数字符串计算出对应的整数。为此我们定义如下函数：
int s2int(char s[]);
再利用原来的getnumber函数，这个程序的main可以定义为：
 
enum { LARGEST = 32767 };
 
int main(int argc, char **argv)
{
    int i, j, n, *ns;
 
    if (argc == 2) n = s2int(argv[1]);
    else getnumber("Largest number to test: ", 2, LARGEST, 5, &n);
 
    if (n < 2 || n > LARGEST) {
        printf("Largest number must in range [2, %d]", LARGEST);
        return 1;
    }
 
    if ((ns = (int*)malloc(sizeof(int)*(n+1))) == NULL) {
        printf("No enough memory!/n");
        return 2;
    }
 
    sieve(n, ns);
 
    for(j = 1, i = 2; i <= n; ++i)
        if (ns[i] == 1) {
            printf("%7d%c", i, (j%8 == 7 ? '/n' : ' '));
            ++j;
        }
    putchar('/n');
 
    free(ns);
    return 0;
}
 
主函数被清晰地分为三部分：准备工作，主要处理部分，输出与结束。如果程序得到的范围不合要求，它就打印错误信息并立即结束。正常情况下完成筛法计算并产生输出。


            

            
使用动态存储管理的要点
            
1）必须检查分配的成功与否。人们常用的写法是：
            
if ((p = (... *)malloc(...)) == NULL) {
            
    .. ... /* 对分配未成功情况的处理 */
            
}
            
2）系统对动态分配块的使用不做任何检查。编程序的人需要保证使用的正确性，绝不可以超出实际存储块的范围进行访问。这种越界访问可能造成大灾难。
            
3）一个动态分配块的存在期并不依赖于分配这个块的地方。在一个函数里分配的存储块的存在期与该函数的执行期无关。函数结束时不会自动回收这种存储块，要回收这种块，唯一的方法就是通过free释放（完全由写程序的人控制）。
            
4）如果在函数里分配了一个存储块，并用局部变量指向它，在这个函数退出前就必须考虑如何处理这个块。如果这个块已经没用了，那么就应该把它释放掉；如果这个块还有用（其中保存着有用的数据），那么就应该把它的地址赋给存在期更长的变量（例如全局变量），或者把这个地址作为函数返回值，让调用函数的地方去管理它。
            
5）其他情况也可能造成存储块丢失。例如给一个指向动态存储块的指针赋其他值，如果此前没有其他指针指向这个块，此后就再也无法找到它了。如果一个存储块丢失了，在这个程序随后的运行中，将永远不能再用这个存储块所占的存储。
            
6）计算机系统里的存储管理分很多层次。一个程序运行时，操作系统分给它一部分存储，供它保存代码和数据。其数据区里包括一块动态存储区，由这个程序的动态存储管理系统管理。该程序运行中的所有动态存储申请都在这块空间里分配，释放就是把不用的存储块交还程序的动态存储管理系统。一旦这个程序结束，操作系统就会收回它占用的所有存储空间。所以，这里说“存储流失”是我们程序内部的问题，并不是整个系统的问题。当然，操作系统也是程序，它也有存储管理问题，那是另一个层次的问题。
            
            
        

getnumber可以直接利用已有的定义（这里又可以看到函数的价值），剩下的工作就是定义程序里需要的两个函数。从数字字符串转换产生整数的函数很简单，它顺序算出各数字字符的整数值并将其加入累加值，每处理一个数位都需要将原值乘10：
 

int s2int(char s[]) {
    int n;
    for (n = 0; isdigit(*s); ++s)
        n = 10 * n + (*s - '0');
    return n;
}
 
在这个函数里没有检查计算的溢出问题。如果需要，很容易加进这种检查。这里也可以直接用标准库函数atoi，该函数完成的就是从数字字符串到整数的转换。有关atoi的情况请查阅本书第11章的介绍。
把筛法计算包装为函数的工作很容易完成，下面是函数的定义：
 
void sieve(int lim, int an[]) {
    int i, j, upb = sqrt(lim+1);
 
    an[0] = an[1] = 0; // 建立起初始向量
    for (i = 2; i <= lim; ++i) an[i] = 1;
 
    for (i = 2; i <= upb; ++i)
        if (an[i] == 1) // i是素数
            for (j = i*2; j <= lim; j += i)
                an[j] = 0; // 这些数都是i的倍数，因此不是素数
}
 
把这些函数定义（包括getnumber的定义）放到一起，适当安排函数位置，必要时加入原型。在源文件前部加入适当 #include命令行，整个程序就完成了。
在这个程序里需要存储一批数据，但是数据的数目在写程序时无法确定，因此只能采用动态存储分配的方式。程序里申请了一个大存储块，其中可以存放所需的int值。用指针指向这样得到的存储块，用起来就像是在使用一个int数组。
例：改造第6章的学生成绩统计和直方图生成程序，使之能处理任意多的学生成绩。
本例的重点是讨论一种常见问题的处理技术：通过动态分配的数组，保存事先完全无法确定数量的输入数据。前一个例子是先确定了数据量，而后做一次动态分配。假如直到开始读入数据的时候还不知道有多少数据项，那又该怎么办？下面我们解决这个问题。
在前面的成绩直方图程序用了一个数组，因此也限制了能处理的成绩数。现在我们想修改readscores，由它全权处理输入工作，在输入过程中根据需要申请适当大小的存储块，把输入数据存入其中。这样，readscores结束时就需要返回两项信息：保存数据的动态存储块地址，以及存于其中的数据项数。一个函数只能有一个返回值，另一“返回值”需要通过参数送出来。下面是修改后readscores的原型和main的定义：
 
double* readscores(int* np); /*读入数据，返回动态块地址，通过np送回项数*/
 
int main()
{
    int n;
    double *scores;
    if ((scores = readscores(&n)) == NULL)
        return 1;
    statistics(n, scores);
    histogram(n, scores, HISTOHIGH);
    return 0;
}
 
由于原程序的组织比较合理，在进行当前这个功能扩充时，我们只需要修改其中的输入部分，并对main做很局部的修改，其他部分根本无须任何变动。
现在考虑如何写readscores。一种可行考虑是先做某种初始分配，在发现数据项数太多，当前的分配无法满足需要时进行存储调整。例如把动态数据块的初始大小定为20（或其他合理的大小），随后如何调整是一个值得研究的问题。下面采用的策略是每次调整时把容量加倍，有关不同调整方式的分析在后面的方框中。这样定义出的函数如下：
 
enum { INITNUM = 20 };
 
double* readscores(int* np) {
    unsigned curnum, n;
    double *p, *q, x;
 
    if ((p = (double*)malloc(INITNUM*sizeof(double))) == NULL) {
        printf("No memory. Stop/n");
        *np = 0;
        return NULL;
    }
 
    for(curnum = INITNUM, n = 0; scanf("%lf", &x) == 1; ++n) {
        if (n == curnum) {
            q = (double*)realloc(p, 2*curnum*sizeof(double));
            if (q == NULL) {
                printf("No enough memory. Process %d scores./n", n);
                break;
            }
            p = q; curnum *= 2;
        }
        p[n] = x;
    }
    *np = n;
 
    return p;
}
 


            

            
动态调整策略
            
要实现一个能在使用中根据需要增长的“动态”数组（一个动态分配的，能存储许多元素的存储块可以看成一个“数组”），需要考虑所采用的增长策略。
            
一种简单的想法是设定一个增量，例如10，一旦存储区满时就把存储区扩大10个单元。仔细考虑和计算会发现这样做有很大的缺陷。实际中对存储量的需要常常是逐步增加的。一般说，在遇到存储区满时，实际上需要另外分配一块更大的存储区，并需要把原块里已有的元素复制到新块里。realloc完成这种操作的代价（虽然没有显露出来）通常与已有的元素个数成正比。
            
假设输入过程中执行了一系列扩大存储的动作，如果每加入10个元素做一次复制，把数组从20增加到包含1000个元素，总的复制数将是20+…+980+990 = 49990。这样，加入每个元素平均大约做n/20次复制，n是最后的元素个数。当数组增大到1000000个元素时，每加入一个元素平均要做50000次复制，这个代价比较高。
            
一种合理的增长方式是每次让存储块加倍。假设存储块从1开始增长，增长到1024时所复制元素为1+2+4+…+512 = 1023。进一步增长到1024×1024≈1000000时，元素复制的总次数大约也为1000000次，加入一个元素，平均需要复制一次。可见，增长策略的作用确实很大。当然，如果数组很小，两种策略的差异就不那么明显了。
            
采用后一增长策略也有代价（世界上没有免费的午餐），那就是存储空间。每次加倍后数组中就出现了一大块空区。例如，当数组有513个元素时，空位有511个之多。随着数组的加倍，最大的空位数也差不多增加一倍。也就是说，按照这种方案，最坏情况下浪费了一半空间。而按照第一种增长策略，空闲元素最多只有9个。
            
总结一下，这里也是在时间和空间之间做交易。在计算机科学技术领域里，这种时间与空间交换的事情到处都可以看到。问题是要考虑需求，综合权衡。
            
 
            
            
        

函数里用变量curnum记录当前分配块的大小，用n记录当前存入的数据项数。一旦遇到数据块满而且还有新项时，我们就扩大存储，把容量加倍。
这个函数定义主要显示了在处理类似问题时常用的一种基本技术，其中并没有刻意追求函数的进一步完善。例如，如果读入数据的过程中遇到一个错误数据，这个函数就会立即结束，返回的是至此读入的数据。有关数据检查和处理等都是前面讨论过的问题，进一步修改这个输入函数，使之能合理处理输入数据中的错误，给出有用的出错信息，或者进一步增加其他有用的功能等等的工作并不困难，都留给读者作为进一步的练习。
7.6.4 函数、指针和动态存储
如果需要在函数里处理一组数据，并把处理结果反应到调用函数的地方，最合适的办法就是在函数调用时提供数组的起始位置和元素数目（或者结束位置）。这种传递成组数据的方式在本章和前一章里反复使用。这时函数完全不必知道用的是程序里定义的数组变量，还是动态分配的存储块。例如，我们完全可以用如下方式调用筛法函数：
 
int ns[1000];
 
int main()
{
    int i, j;
    sieve(1000, ns);
    for(j = 1, i = 2; i <= n; ++i)
        if (ns[i] == 1) {
            printf("%7d%c", i, (j%8 ? ' ' : '/n'));
            ++j;
        }
 
    putchar('/n');
    return 0;
}
 
在前一节的筛法程序实例里，我们在主函数里通过动态分配取得存储，而后调用函数sieve，最后还是由main函数释放这块存储。这样，分配和释放的责任位于同一层次，由同一个函数（函数main）完成。这样做最清晰，易于把握，是最好的处理方案。
但也存在一些情况，其中不能采用上述做法，例如上面的直方图程序。程序里定义了一个读入函数，它需要根据输入情况确定如何申请动态存储。这时动态存储的申请在被调用函数readscores的内部，该函数完成向存储块里填充数据的工作，最后把做好的存储块（就像是一个数组）的地址通过返回值送出来。调用函数（main）用类型合适的指针接收这个地址值，而后通过这个指针使用这一存储块里的数据。
首先，这一做法完全正确，因为动态分配的存储块将一直存在到明确调用free释放它为止。虽然上述存储块是在函数readscores里面分配的，但它的生命周期（生存期）并不随该函数的退出而结束。语句：
    scores = readscores(&n);
使scores得到函数readscores的运行中申请来并填充好数据的存储块，在main里继续用这个块是完全没问题的。当然，采用这种方式，readscores就不应该在退出前释放该块。注意：上面的调用除了传递有关的数据外，实际上还有存储管理责任的转移问题。在readscores把一块存储的指针通过返回值送出来时，也把释放这块存储的责任转交给main。这样，我们也可以看出前面的程序里忽略了一件事情，在那里没有释放这一存储块。应做的修改就是在main的最后加一个释放语句（当然，由于main的结束也就是整个程序的结束，未释放的这块存储也不会再有用了。如前所述，在这个程序结束后，操作系统将会收回这个程序占用的全部存储）。
现在考虑readscores的设计里的一个问题。在前面的程序里，readscores通过int指针参数（实参应该是一个int变量的地址）传递实际读入数据的个数。另一种可能做法是让函数返回这一整数值，例如将其原型改成：
int readscores(???);
这样，我们在main里就可以写如下形式的调用：
if (readscores(... ...) <= 0) { ... } /* 产生错误信息并结束程序 */
（这一写法使人想起标准库的输入函数scanf）。如果这样设计函数，调用readscores的地方就需要通过实参取得函数里动态分配的存储块地址。也就是说，要从参数获得一个指针值。问题是，这个函数的参数应该如何定义呢？
答案与其他情况完全一样。如果我们想通过实参取得函数里送出来的一个int值，就要把一个int变量的地址送进函数，要求函数间接地给这个变量赋值。同理，现在需要得到一个指针值，就应该通过实参把这种指针变量的地址送进去，让函数通过该地址给调用时指定的指针变量赋值。这样，修改后的函数readscores的原型应该是：
int readscores(double **dpp);
因为double指针的类型是(double*)，其地址的类型就是指向(double*)的指针，也就是(double**)。调用readscores时应该把这种指针的地址传给它：
if (readscores(&scores) <= 0) { /* 产生错误并结束程序 */ }
由于scores的类型是(double*)，表达式 &scores的类型就是(double**)。函数readscores也需要做相应的修改：
 
int readscores(double **dpp) {
    size_t curnum, n;
    double *p, *q, x;
 
    if ((p = (double*)malloc(INITNUM*sizeof(double))) == NULL) {
        printf("No memory. Stop/n");
        *dpp = NULL;
        return 0;
    }
 
    for(curnum = INITNUM, n = 0; scanf("%lf", &x) == 1; ++n) {
        if (n == curnum) {
            q = (double*)realloc(p, 2*curnum*sizeof(double));
            if (q == NULL) {
                printf("No enough memory. Process %d scores./n", n);
                break;
            }
            p = q; curnum *= 2;
        }
        p[n] = x;
    }
    *dpp = p;
 
    return n;
}
 
这里展示的也是C程序里常用的一种技术。在这一处理方案中，我们同样是把函数里分配的存储块送到函数之外，同时也把管理这一存储块的责任转交给调用函数的程序段。不同的是，这次是通过参数传递存储块的地址。
       在这一节里，我们介绍了指针、函数与动态分配之间的一些关系，并讨论了几种不同的处理技术。只要有可能，在程序里最好使用第一种设计，因为它最清晰，也最不容易出现忘记释放的情况。如果不得已而采用了其他方式，那么就一定要记得存储管理责任的交接问题，并在适当的地方释放动态分配的存储区。



[1] 这种说法也有例外。我们可以在一个函数里申请存储块，而后在函数里把存储块的地址全局的指针变量，或者返回指向这个块的指针值，把这个块交给调用函数的地方用。这些做法也意味着把存储块的“拥有权”交给程序的其他部分，此时就不应该释放它了。