第九章 运行时空间组织.ppt

1、目标程序运行时的主动存储分配策略是简单的堆栈存储分配。C语言存储组织过程的执行，主要内容，FORTRAN的子程序)PASCAL/函数C的函数的过程，过程单元、过程和活动的激活(调用)和终止(返回)，以及过程的每次运行(或执行)都称为一个活动。活动是一个动态的概念。除了设计为永不停止的进程(如操作系统等。)或由于设计错误而具有死循环的过程，任何过程的活动都具有有限的寿命。程序单元的执行需要：代码段活动记录(程序单元运行所需的附加信息，如参数、本地数据、返回地址等)。)，运行时内存分区、代码段、静态数据区、堆栈、堆、可静态确定的大小、全局/局部静态变量、活动记录堆栈、动态分配的数据、活动记录、一次

2、执行中管理流程所需的信息。使用连续存储块，该连续存储块称为活动记录。活动记录的结构和内容，指针SP指向堆栈中当前进程的活动记录的起始位置。顶部：活动记录堆栈的顶部。编译以一些单位记录关于数组的信息，称为数组的“内部向量”。形式单位：保存相应实参数的地址或值。dynamic chain:在调用过程之前指向最新活动记录的地址的指针。在运行时，运行堆栈上的每个数据区都根据动态建立的顺序进行链接。链头是栈顶的起始位置。static chain:指向静态直接外层上最新活动记录的地址的指针，用于访问非局部变量。通用存储分配策略、静态分配策略、动态分配策略、堆栈类型动态分配策略、堆类型动态分配策略、存储分配

3、策略、静态分配策略：例如，FORTRAN不允许进程递归地包含具有可变卷的数据对象，或者具有不确定属性的名称因此可以在编译期间完全确定每个数据项的存储空间位置；动态分配策略：如PASCAL，允许进程递归，允许动态应用和释放存储空间。因此，数据项的性质和大小不能在编译时完全确定。例如，允许递归进程和变量数组，名称的作用域和生存期满足子程序结构定义的作用域。动态分配策略，堆栈动态分配策略内存首先申请释放堆动态分配策略内存。在释放时间之前，内存的应用和释放不遵循请求。一般的处理方法是：让正在运行的程序拥有一个大的存储区(称为堆)，在这里申请人从堆中共享一块，在这里释放器将它返回到堆中，动态存储分配简单

4、的堆栈类型，需要：1，没有子程序结构；2.流程定义不允许嵌套；3.允许递归调用该过程。C语言程序结构，全局数据描述Main()数据描述main()main空隙率() R 空隙率()中的数据描述 Q中的数据描述，C语言程序的存储组织，C语言的活动记录，连接数据(两项):旧服务点值的返回地址(即前一活动记录的起始地址)；(2)参数数量；(3)形式单元(存储实参数的值或地址)；(4)过程的局部变量(简单变量)，数组和临时工作单元的内部信息向量。C活动记录，210，堆动态存储分配，堆可变堆空间管理策略，减少释放碎片的技术空间，要求：一种程序语言允许用户自由地申请数据空间和返回数据空间，或者说不仅有一个

5、进程，还有一个进程程序结构。操作：堆提供两个操作，分配操作和释放操作：经过一段时间的运行，这个大空间必须分成许多块，一些被占用，一些无用(空闲)碎片问题，堆动态存储分配。当正在运行的程序需要一个容量为N的空间时，我们应该分配给它哪个块？运行程序需要一个容量为n的空间块，但是发现没有大于n的空闲块，而所有空闲块的总和比n大得多。如果运行程序需要一个n的空间，但是所有空闲块的总和还不够呢也就是说，找到无用但尚未被运行程序释放的被占用的块。堆管理，堆空间管理策略减少碎片技术空间释放，堆空间管理策略，1固定长度块管理2可变长度块管理，1固定长度块管理堆动态存储分配是根据固定长度块最简单的实现。在初始化

6、期间，堆存储空间被分成若干等长的块，每个块被分配一个链域，所有块根据相邻块的顺序被链接到一个链表中，并且可用的指针被用来指向链表中的第一个块。在分配期间，每次分配可用指针所指示的块，然后可用指针指向下一个相邻块。返回时，将返回的块插入链表。考虑到插入的便利性，可以将返回的块插入到由available引用的块之前，然后available指向新返回的块。2、变长块管理除了根据固定长度块进行分配外，还可以根据需要分配不同长度的存储块，可以根据要求进行更改。根据这种方法，存储空间在初始化期间是一个完整的块。根据用户的需求，在分发过程中，首先将满足需求的一小块从整块中分离出来。稍后，当返回时，如果新返回

7、的片段和现有空间可以合并，则它们被合并成一个片段。如果不能与任何空闲块合并，则可以将空闲块链接到一个链表中。当再次进行分配时，从空闲块链表中找出满足要求的块，或者分配整个块，或者从块中分割出一个小块进行分配。如果空闲块表中有几个空闲块满足需求，应该分配哪一个？通常有三种不同的分配策略，在不同的情况下应该采用不同的方法。一般来说，选择时应考虑以下因素：用户需求；请求分配金额的大小分布；分发和发布的频率以及效率对系统的重要性等。(1)首次满足法：只要在空闲块链表中找到满足需求的块，就进行分配。(2)最优满足法：在空闲块链表中分配一个不小于应用块且离应用块最近的空闲块给用户，然后系统在分配前先从头到

8、尾跟踪空闲块链表，然后从中找出一个块。为了避免每次分配时扫描整个链表，空闲块链表空间的大小通常从小到大排序。(3)最差满意度法：将备件块表中不小于应用块且为最大备件的备件全部分配给用户。此时，空闲块列表按照空闲块的大小从大到小排序。只需从链表中删除第一个节点，并将其中一部分分配给用户，而其他部分作为新节点插入到自由块表的适当位置。碎片减少技术，1分配，找到足够大的最小块-需要保持空闲块的大小排序2释放，合并任何相邻的块-搜索所有空闲块表，或其他算法3堆变量收缩在一起，空间释放，1显式释放2隐式(自动)释放，显式释放，编程语言提供的机制，如：帕斯卡：处置：自由程序员必须写显式调用来分配和释放存储

9、。堆分配和释放的C语言描述，#定义null 0 #定义memsize 8096/* ChangeForDifferentSizes */TypeDefDoubalign；typedefunionheader struct union header * next；unsignedusedsizeunsignedfreesizes。Aligna标题；/数据类型头为每个存储块存储簿记信息静态头域内存大小；staticHeader * memptr=空；void*malloc(未指定字节)Header*p，* newpunsignednunitsnunits=(nbytes sizeof(Header

10、)-1/sizeof(Header)1；如果(memptr=NULL)， mem ptr-s . next=mem ptr=mem；memptr-s . usedsize=1；mem ptr-s . freesize=MEMSize-1；对于(p=memptr(p-s.next！=memptr)，newp-s . next=p-s . next；p-s . freesize=0；p-s . next=newp；memptr=newp。返回(void *)(newp 1)；无空隙(空隙* AP)表头*bp，*p，*前一个；bp=(表头*)AP1；for(prev=memptr，p=memp tr-s . next；(p！自动堆管理-隐式存储回收，使用一种需要完全动态的ru的语言垃圾收集，垃圾收集程序-找到所有可以引用的内存，并释放所有未引用的内存。当不再直接或间接地通过指