1、2023-8-17运行时存储空间管理1概述概述在代码生成前，需要把程序静态的正文和实现这个程序的运行时的活动联系在代码生成前，需要把程序静态的正文和实现这个程序的运行时的活动联系起来，弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义起来，弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义的量是如何存放的，如何去访问它们。的量是如何存放的，如何去访问它们。在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。的。在程序语言中，程序使用的存储单元都由标识符来表示，它们对应的内存地在程序语言中，程
2、序使用的存储单元都由标识符来表示，它们对应的内存地址都是由编译程序在编译时或由其生产目标代码程序运行时进行分配的。址都是由编译程序在编译时或由其生产目标代码程序运行时进行分配的。2023-8-17运行时存储空间管理2活动活动:过程的一次执行。过程的一次执行。活动的生存期：活动的生存期：从执行该过程体第一步操作到最后从执行该过程体第一步操作到最后一步操作之间的操作序列，包括执行一步操作之间的操作序列，包括执行P P时调用其他时调用其他过程花费的时间，不同活动的生存期或者是不重叠过程花费的时间，不同活动的生存期或者是不重叠的，或者是嵌套的。的，或者是嵌套的。递归：递归：如果一个过程在没有退出当前的
3、活动时又开如果一个过程在没有退出当前的活动时又开始其新的活动。始其新的活动。作用域：作用域：一个说明在程序里能起作用的范围。一个说明在程序里能起作用的范围。9.1 目标程序运行时的活动目标程序运行时的活动2023-8-17运行时存储空间管理39.1.1参数传递参数传递z参数参数:形参形参(哑元哑元),实参实参(实元实元)z参数传递参数传递(形实匹配形实匹配)方式方式:(1)传地址传地址 (2)传值传值 (3)传名传名 (4)得结果得结果2023-8-17运行时存储空间管理4组织存储空间应考虑的几个问题组织存储空间应考虑的几个问题过程是否允许递归？过程是否允许递归？当控制从一个过程的活动返回时，
4、对局部名字的值当控制从一个过程的活动返回时，对局部名字的值如何处理？如何处理？过程是否允许引用非局部名字？过程是否允许引用非局部名字？过程调用时，如何传递参数；过程是否可以作为参过程调用时，如何传递参数；过程是否可以作为参数被传递和作为结果被返回数被传递和作为结果被返回?存储空间可否在程序控制下进行动态分配？存储空间可否在程序控制下进行动态分配？存储空间是否必须显示地释放？存储空间是否必须显示地释放？2023-8-17运行时存储空间管理59.2 运行时存储器的划分运行时存储器的划分 9.2.1 运行时存储器的划分运行时存储器的划分 目标代码目标代码 静态数据静态数据 栈栈 堆堆2023-8-1
5、7运行时存储空间管理69.2.2活动记录活动记录 (Activation Record)内容内容:连接数据连接数据,返回地址返回地址,动态链动态链,静态链静态链 形式单元形式单元 局部数据区局部数据区 TOP SP 临临时时变变量量内内情情向向量量局局部部变变量量形形式式单单元元静静态态链链动动态态链链返返回回地地址址2023-8-17运行时存储空间管理79.2.3存储分配策略存储分配策略v静态分配策略静态分配策略：在编译时，对所有数据对象分配固定的：在编译时，对所有数据对象分配固定的 存储单元，且在运行时始终保持不变。存储单元，且在运行时始终保持不变。v栈式动态分配策略栈式动态分配策略：在运
6、行时，把存储器作为一个栈进：在运行时，把存储器作为一个栈进 行管理。行管理。v堆式动态分配策略：堆式动态分配策略：在运行时，把存储器组织成堆结在运行时，把存储器组织成堆结 构，以便用户关于存储空间的申请与构，以便用户关于存储空间的申请与 释放。释放。2023-8-17运行时存储空间管理8如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配策略为策略为运行时不改变绑定，每次过
7、程活动时，一个名字都绑定到同样的存储单元。运行时不改变绑定，每次过程活动时，一个名字都绑定到同样的存储单元。这种性质允许局部名字的值在过程停止活动后仍然这种性质允许局部名字的值在过程停止活动后仍然。即当控制再次进入过。即当控制再次进入过程时，局部名字的值同上一次控制离开时一样。程时，局部名字的值同上一次控制离开时一样。9.3 静态存储分配静态存储分配2023-8-17运行时存储空间管理9u程序是段结构的，即由主程序段和若干子程序段组成。程序是段结构的，即由主程序段和若干子程序段组成。程序程序 主程序段主程序段+若干子程序段若干子程序段u各程序段中定义的名字一般是彼此独立的。各程序段中定义的名字
8、一般是彼此独立的。（除公共块和等价语句说明的名字以外），也即各段的数据对象名的作用域（除公共块和等价语句说明的名字以外），也即各段的数据对象名的作用域在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不同段在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不同段间互相引用、赋值。间互相引用、赋值。u每个数据名所需的存储空间大小都是常量每个数据名所需的存储空间大小都是常量（），且所有数据名的性质是完全确），且所有数据名的性质是完全确定的。定的。像像FORTRANFORTRAN这样的语言这样的语言2023-8-17运行时存储空间管理10这样，整个程序所需数据空间的总量在编译时完
9、全确定，从而每个数据名的地址这样，整个程序所需数据空间的总量在编译时完全确定，从而每个数据名的地址就可静态进行分配。就可静态进行分配。换句话说，一旦存储空间的某个位置分配给了某个数据名（关联起来）之后，在换句话说，一旦存储空间的某个位置分配给了某个数据名（关联起来）之后，在目标程序的整个运行过程中，此位置（地址）就属于该数据名了。目标程序的整个运行过程中，此位置（地址）就属于该数据名了。存储管理的静态性也使得存储管理的静态性也使得 FORTRAN 程序中的各程序段均可程序中的各程序段均可。2023-8-17运行时存储空间管理11【例】一个FORTRAN 77的例子(1)PROGRAM CNSU
10、ME(2)CHARACTER*50 BUF/程序体所拥有的静态量程序体所拥有的静态量BUF(3)INTEGER NEXT/程序体所拥有的静态量程序体所拥有的静态量NEXT(4)CHARACTER C,PRDUCE/程序体所拥有的静态量程序体所拥有的静态量C(5)DATA NEXT/1/,BUF/(6)6 C=PRDUCE()(7)BUF(NEXT:NEXT)=C(8)NEXT=NEXT+1(9)IF(C.EN.)GOTO 6(10)WRITE(*,(A)BUF(11)END(12)CHARACTER FUNCTION PRDUCE()(13)CHARACTER*80 BUFFER(14)INT
11、EGER NEXT(15)SAVE BUFFER,NEXT/PRDUCE函数体所拥有的静态量函数体所拥有的静态量BUFFER,NEXT(16)DATA NEXT/81/(17)IF(NEXT.GT.80)THEN(18)READ(*,(A)BUFFER(19)NEXT=1(20)END IF(21)PRDUCE=BUFFER(NEXT:NEXT)(22)NEXT=NEXT+1(23)END 2023-8-17运行时存储空间管理12consume的活动记录的活动记录produce的活的活动记录动记录2023-8-17运行时存储空间管理13 名字在程序被编译时绑定到存储单元，不需要运名字在程序被编
12、译时绑定到存储单元，不需要运行时的任何支持。行时的任何支持。绑定的生存期是程序的整个运行时间。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。一次离开时的一样。每个活动记录的大小是固定的。每个活动记录的大小是固定的。过程调用时保存信息的地址在编译时也是已知的过程调用时保存信息的地址在编译时也是已知的。特点特点2023-8-17运行时存储空间管理14适于静态存储分配的语言必须满足以下条件适于静态存储分配的语言必须满足以下条件 数组的上下界必须是常数；数组的上下界必须是常数；过程调用不允许递归；过程调用不允许递
13、归；编译时刻无法预先确定哪些递归函数在运行时被编译时刻无法预先确定哪些递归函数在运行时被激活，更难以确定它们的递归深度。激活，更难以确定它们的递归深度。不允许采用动态的数据结构不允许采用动态的数据结构(即在程序运行过程即在程序运行过程中申请和释放的数据结构中申请和释放的数据结构)。2023-8-17运行时存储空间管理15这种分配策略是将整个程序的这种分配策略是将整个程序的。在具有递归结构的语言程序中，每当调用一个过程在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。作结束时就释放这部分空
14、间。栈式动态存储分配策略适用于栈式动态存储分配策略适用于 PASCAL，C，ALGOL 之类具有递归结构的语言的实现。之类具有递归结构的语言的实现。8.3栈式存储分配栈式存储分配2023-8-17运行时存储空间管理16过程所需的数据空间包括两部分：过程所需的数据空间包括两部分：u一部分是生存期在本过程这次活动中的数据对象，一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等；如局部变量、参数单元、临时变量等等；u另一部分则是用以管理过程活动的记录信息。即：另一部分则是用以管理过程活动的记录信息。即：当一次过程调用出现时当一次过程调用出现时，调用该过程的那个过程的活动即
15、被中断，当前机器，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器（返回地址）、寄存器的值等等，也都必须保的状态信息，诸如程序计数器（返回地址）、寄存器的值等等，也都必须保留在栈中。留在栈中。当控制从调用返回时当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活，便根据栈中记录的信息恢复机器状态，使该过程的活动继续进行。动继续进行。2023-8-17运行时存储空间管理179.4 简单的栈式存储分配简单的栈式存储分配 不允许过程的嵌套定义、但允许递归调用不允许过程的嵌套定义、但允许递归调用9.4.1 C的活动纪录的活动纪录内容内容:连接数据：连接数据：老老SP
16、（前一活动记录的地址）（前一活动记录的地址）,返回地址返回地址 参数个数参数个数 形式单元形式单元 过程的局部变量过程的局部变量,数组内量向量数组内量向量,临时的工作单元临时的工作单元 TOP SP 临时变量内情向量简单变量形式单元参数个数返回地址老 SP2023-8-17运行时存储空间管理18过程调用、过程进入、过程返回过程调用、过程进入、过程返回u过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等。器状态等。u过程调用序列过程调用序列过程调用时执行的分配活动记录，把信息填入它的域中的代码。过程调用时执
17、行的分配活动记录，把信息填入它的域中的代码。u过程返回序列过程返回序列过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码的代码u调用序列和返回序列常常都分成两部分，调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中。分处于调用过程和被调用过程中。u即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异也会因实现而异9.4.2 C的过程调用的过程调用,过程进入过程进入,数组空间分配和过程返回数组空间分
18、配和过程返回 中间代码中间代码 目标代码目标代码 说明说明 par Ti (i+3)TOP:=Ti 传值传值 (i+3)TOP:=addr(Ti)传地址传地址 call p,n 1TOP:=SP 3TOP:=n JSP P SP:=TOP+1 1SP:=返回地址返回地址 TOP:=TOP+L return(E)TOP:=SP-1 SP:=0SP X:=2 TOP UJ 0X 无条件转移无条件转移 TOP SP 临临时时变变量量 内内情情向向量量 简简单单变变量量 形形式式单单元元 参参数数个个数数 返返回回地地址址 老老 SP 2023-8-17运行时存储空间管理20简单的栈式存储分配例简单的
19、栈式存储分配例 首先从一种最简单的程序设计语言结构讲起：首先从一种最简单的程序设计语言结构讲起：。全局变量或数组的说明；全局变量或数组的说明；main()/主函数主函数 主程序执行语句主程序执行语句R()/函数函数 R Q()/函数函数 Q 2023-8-17运行时存储空间管理21这种情况下，采用栈式动态分配策略，这种情况下，采用栈式动态分配策略，程序运行时的存储空间程序运行时的存储空间(栈栈)中在某一时刻可能会包含某个过程的几个活动记录中在某一时刻可能会包含某个过程的几个活动记录（某个过程递归调用的情况）；（某个过程递归调用的情况）；另外，同样的一个存储位置，在不同运行时刻可能分配给不同的数
20、据对象。另外，同样的一个存储位置，在不同运行时刻可能分配给不同的数据对象。2023-8-17运行时存储空间管理22u若主函数调用了函数若主函数调用了函数 Q，Q 又调用了又调用了 R，在，在 R 进入运行后的存储结构如图进入运行后的存储结构如图（a）所示。）所示。u若主函数调用了函数若主函数调用了函数 Q，Q 递归调用自己，在递归调用自己，在 Q 第二次进入运行后的存储结第二次进入运行后的存储结构如图（构如图（b）所示。）所示。u若主程序先调用若主程序先调用 Q，且，且 Q 不调用不调用 Q 和和 R，然后主函数接着调用，然后主函数接着调用 R，这时，这时 Q 和和 R 进入运行后的存储结构，
21、先后分别如图（进入运行后的存储结构，先后分别如图（c）和（）和（d）所示。）所示。2023-8-17运行时存储空间管理239.5 嵌套过程语言的栈式实现嵌套过程语言的栈式实现-PASCAL运行时运行时:v 局部变量可采用类同局部变量可采用类同C C的栈式分配的栈式分配v非局部变量可采用非局部变量可采用静态链静态链(存取链存取链)或或DISPLAYDISPLAY表表。PASCAL 语言程序结构的特点是允许过程语言程序结构的特点是允许过程，一个过程可以引用包，一个过程可以引用包围它的任一外层过程所定义的标识（如变量，数组或过程等）。围它的任一外层过程所定义的标识（如变量，数组或过程等）。若不考虑它
22、的若不考虑它的“文件文件”和和“指针指针”类型，采用类型，采用PASCAL的一个子集的一个子集，它的存储分它的存储分配也是采用栈式动态分配策略配也是采用栈式动态分配策略，只是它的过程活动记录中应增设一些内容，用以，只是它的过程活动记录中应增设一些内容，用以。2023-8-17运行时存储空间管理24嵌套过程语言嵌套过程语言PASCAL例例 0 program P;a,x var a,x:integer;1 procedure Q(b:integer);b,i var I:integer;2 procedure R(u,v:integer);u,v var c,d:integer;c,d begi
23、n R(u+1,v)end beginR(1,x)endQ 1 procedure S;c,i var c,I:integer;begin Q(c)endS begin SendP.静态链display2023-8-17运行时存储空间管理259.5.1 非局部名字的访问的实现非局部名字的访问的实现一一.静态链和活动纪录静态链和活动纪录 TOPTOP 临时单元临时单元 内情变量内情变量 简单变量简单变量 形参单元形参单元 形参个数形参个数 静态链静态链 静态链指向嵌套直接外层的过程活动纪录静态链指向嵌套直接外层的过程活动纪录 返回地址返回地址 SP 动态链动态链(老老SP)动态执行时调用该过程的
24、活动记录的首地址动态执行时调用该过程的活动记录的首地址过程的层数是过程名的重要属性过程的层数是过程名的重要属性2023-8-17运行时存储空间管理26P调用调用S、S调用调用Q、Q调用调用R 时的静态链和活动纪录时的静态链和活动纪录 10 9 8 7 6 5 4 3 2 1 0 IC00返返回回地地址址0 xa0返返回回地地址址0TOP 24 23 22 21 20 19 18 SP 17 16 15 14 13 12 11dcv(形形参参)u(形形参参)2（形形参参个个数数）11返返回回地地址址11ib（形形参参）1（参参数数个个数数）0返返回回地地址址5PASCAL程序二二.嵌套层次显示表
25、嵌套层次显示表(display)和活动内容和活动内容连接数据有三项：老连接数据有三项：老SPSP、返回地址、全局、返回地址、全局displaydisplay地址。地址。每进入一个过程后每进入一个过程后,在建立它的活动记录的同时建立一张在建立它的活动记录的同时建立一张displaydisplay表表,有有i+1i+1元元(指针数组指针数组),),由一个非局部量的说明所在的静态层数和相由一个非局部量的说明所在的静态层数和相对活动记录的相对地址可得到对活动记录的相对地址可得到:绝对地址绝对地址=display=display静态层次静态层次+相对地址相对地址 TOPTOP临时单元临时单元 内部向量内
26、部向量 简单变量简单变量 局部局部displaydisplay：本层及静态逐个外层活动记录首地址显示表本层及静态逐个外层活动记录首地址显示表 形参单元形参单元 参数个数参数个数 全局全局displaydisplay：调用该过程的活动记录的局部调用该过程的活动记录的局部displaydisplay首地址首地址 返回地址返回地址 SPSP老老SP(SP(动态链动态链)：动态执行时调用该过程的活动记录的首地址动态执行时调用该过程的活动记录的首地址2023-8-17运行时存储空间管理28P调用调用S、S调用调用Q、Q调用调用R 时的时的Display表和活动记录表和活动记录 12 11 10 disp
27、lay 9 8 7 6 5 4 3 2 1 0 I c 5 0 0 2 全局display 返回地址 0 x a 0-display 返回地址 0 TOP 30 29 28 27 display 26 25 24 23 22 21 SP 20 19 display 18 17 16 15 14 13 d c 20 13 0 v(形参)u(形参)2（形参个数）18 全局 display 返回地址 13 13 0 b（形参）1（参数个数）9 全局 display 返回地址 5 PASCAL程序2023-8-17运行时存储空间管理29Display表的建立P1调用调用P2，P2要知道自己的直接外层要
28、知道自己的直接外层P0的的display表才能建立自己的表才能建立自己的display表；表；P1 调用调用P2时，时，P2要把要把P0的的display表地址传给表地址传给P2；此时，此时，P1要么就是要么就是P0，要么是，要么是P2的直接外层；的直接外层；用用P1的的display表自底向上取表自底向上取I2（P20所在的层数）个单元增加所在的层数）个单元增加P2自己的自己的SP就构就构成成P2的的display表表 P1(p0)p0 P2 P2 P1 P2 P2 2023-8-17运行时存储空间管理309.5.2参数传递的实现参数传递的实现四元式四元式Par Ti的解释：的解释：参数参数
29、T:简单变量简单变量：-(I+3)TOP:=Ti 或或(I+3)TOP:=addrTi 数组：传送首地址或内情向量地址数组：传送首地址或内情向量地址 过程：过程：执行下列过程：执行下列过程：B1 过程过程Ti的入口地址，的入口地址，B2 现行的现行的display地址地址 B1的地址传送给调用过程的地址传送给调用过程Q。标号：标号：B1标号标号Ti的地址的地址 B2 标号标号Ti所在过程中的活动记录地址所在过程中的活动记录地址 B1的地址传送给调用过程的地址传送给调用过程Q,形参：传递形参单元形参：传递形参单元Ti的内容的内容(而不是地址）而不是地址）2023-8-17运行时存储空间管理319
30、.6 堆式动态存储分配堆式动态存储分配 如果一个程序语言提供用户如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制自由地申请数据空间和退还数据空间的机制（如（如+中的中的new，delete，PASCAL的的new，dispose等机制），或者不仅有等机制），或者不仅有过程而且有进程的程序结构的情况下，空间的使用过程而且有进程的程序结构的情况下，空间的使用的原则，那么只有栈式的动态分配方案就不适用了。的原则，那么只有栈式的动态分配方案就不适用了。通常使用一种称为通常使用一种称为。局部名的值在活动结束时必须被保存。局部名的值在活动结束时必须被保存。被调用者的活动生存期超过调用者。被调
31、用者的活动生存期超过调用者。2023-8-17运行时存储空间管理32堆式存储分配示意堆式存储分配示意BAC D可分配空间ABCD使用块记录由于借、还的时间先后不一，因而经过一段时间的运由于借、还的时间先后不一，因而经过一段时间的运行后，这个大空间就必然被分割成的许多小块，这些行后，这个大空间就必然被分割成的许多小块，这些块有些正在使用，有些则是空闲的块有些正在使用，有些则是空闲的(未被使用未被使用)。假定程序运行时有假定程序运行时有一个大的存储空间，一个大的存储空间，需要时就从这个空需要时就从这个空间中借用一块，不间中借用一块，不用时再退还给它。用时再退还给它。2023-8-17运行时存储空间
32、管理33对于堆式存储分配，需要解决两个问题对于堆式存储分配，需要解决两个问题，即当运行程序需要一块空间时应分配哪一块给它；，即当运行程序需要一块空间时应分配哪一块给它；，由于返回堆的不用空间是按任意次序进行的，由于返回堆的不用空间是按任意次序进行的，所以需要研究专门的回收分配策略。所以需要研究专门的回收分配策略。在许多语言中都有显式的堆空间分配和回收语句或函数，如：在许多语言中都有显式的堆空间分配和回收语句或函数，如：PASCAL 语言中的语言中的 new 和和 disposeC 语言中的语言中的 alloc 和和 free以及以及 C+语言中的语言中的 new 和和 delete2023-8
33、-17运行时存储空间管理34堆式存储管理的方法堆式存储管理的方法 当运行程序要求一块体积为当运行程序要求一块体积为 N 的存储空间时应如何分配？从理论上讲，这的存储空间时应如何分配？从理论上讲，这时应从比时应从比 N 稍大一些的空闲块中取出稍大一些的空闲块中取出 N 个单元予以分配，这种做法的目的是个单元予以分配，这种做法的目的是保持较大的空闲块以备将来之需。保持较大的空闲块以备将来之需。但这种方法实现起来难度较大，实际中采用的办法是：但这种方法实现起来难度较大，实际中采用的办法是：扫描空闲块链并在首次遇到的比扫描空闲块链并在首次遇到的比 N 大的空闲块中取出大的空闲块中取出 N 个单元进行分
34、配。个单元进行分配。2023-8-17运行时存储空间管理35如果找不到一块比如果找不到一块比 N 大的空闲块，但所有空闲块的总和却比大的空闲块，但所有空闲块的总和却比 N 大，这时就大，这时就需要用某种方法使这些空闲块拼接在一起，形成一个可分配的连续空间。需要用某种方法使这些空闲块拼接在一起，形成一个可分配的连续空间。如果所有空闲块的总和都不及如果所有空闲块的总和都不及 N 大，则需要采用更复杂的办法，如废品回收大，则需要采用更复杂的办法，如废品回收技术技术(即寻找那些运行程序已不使用但仍未释放的存储块或运行程序目前很少使即寻找那些运行程序已不使用但仍未释放的存储块或运行程序目前很少使用的存储
35、块用的存储块)，把这些存储块回收后再重新分配。，把这些存储块回收后再重新分配。2023-8-17运行时存储空间管理36使用可利用空间表进行动态存储分配的方法使用可利用空间表进行动态存储分配的方法又可分为如下两种：又可分为如下两种：定长块的管理。定长块的管理。划分成大小相同的若干块。划分成大小相同的若干块。变长块的管理。变长块的管理。根据实际需要来分配长度不同的空闲块。根据实际需要来分配长度不同的空闲块。2023-8-17运行时存储空间管理371、定长块管理、定长块管理 最简单的堆式存储管理方法是采用定长块的管理方法，即将堆存储空间在最简单的堆式存储管理方法是采用定长块的管理方法，即将堆存储空间
36、在初始化时就初始化时就划分成大小相同的若干块划分成大小相同的若干块，将各个块通过链表链接起来形成一个单向，将各个块通过链表链接起来形成一个单向线性链表。线性链表。由于各块大小相同，故分配时无需查找，只需将头指针所指的第一块分配给用由于各块大小相同，故分配时无需查找，只需将头指针所指的第一块分配给用户即可，然后头指针指向下一块。户即可，然后头指针指向下一块。同样，当回收时，系统将待回收的存储块插入到表头即完成了该块的回收。同样，当回收时，系统将待回收的存储块插入到表头即完成了该块的回收。2023-8-17运行时存储空间管理38占用占用占用占用占用占用空闲空闲空闲空闲空闲空闲|available占
37、用占用空闲空闲占用占用空闲空闲空闲空闲空闲空闲|available|定长块管理图示定长块管理图示 2023-8-17运行时存储空间管理392、变长块管理、变长块管理 变长块管理方法是一种变长块管理方法是一种堆式存储管理方法，它可以堆式存储管理方法，它可以根据实际需要来根据实际需要来分配长度不同的空闲块分配长度不同的空闲块；对空闲块的管理则可以采用的链表形式。；对空闲块的管理则可以采用的链表形式。系统开始时，存储空间是一完整空间，可利用空间表中只有一个大小为整个存系统开始时，存储空间是一完整空间，可利用空间表中只有一个大小为整个存储空间的空闲块。储空间的空闲块。当系统运行一段时间后，随着分配和回
38、收的进行，可利用空间表中空闲块的大当系统运行一段时间后，随着分配和回收的进行，可利用空间表中空闲块的大小和个数也随之改变。小和个数也随之改变。2023-8-17运行时存储空间管理40若可利用空间表存在多个大于所要求空间的空闲块，若可利用空间表存在多个大于所要求空间的空闲块，可采取以下三种方法之一进行存储分配：可采取以下三种方法之一进行存储分配：从表头开始查找可利用空间表，将找到的从表头开始查找可利用空间表，将找到的第一个第一个满足需满足需要的空闲块或空闲块的一部分分配出去要的空闲块或空闲块的一部分分配出去(当空闲块略大于所要求的空间时，当空闲块略大于所要求的空间时，则整块分配出去则整块分配出去
39、)，而其余部分仍作为一个空闲块留在表中。，而其余部分仍作为一个空闲块留在表中。系统扫描整个可利用空间表，从中找出一块系统扫描整个可利用空间表，从中找出一块不小于要求不小于要求的最小空闲块的最小空闲块予以分配。为了避免每次分配都要扫描整个表，通常将空闲块予以分配。为了避免每次分配都要扫描整个表，通常将空闲块按由小到大的顺序进行排列。这样，所找到的第一个大于或等于所需空间的按由小到大的顺序进行排列。这样，所找到的第一个大于或等于所需空间的空闲块即为所求，无须再扫描整个表。空闲块即为所求，无须再扫描整个表。系统将可利用空间表中。系统将可利用空间表中最大最大的空闲块予以分配的空闲块予以分配(当然也要当
40、然也要求其不小于所需空间的大小求其不小于所需空间的大小)，这种方法应使空闲块按由大到小的顺序排列，这种方法应使空闲块按由大到小的顺序排列，此时表头的空闲块即为所求。此时表头的空闲块即为所求。2023-8-17运行时存储空间管理41最优满足法适用于请求分配的内存大小范围较广的系统；最优满足法适用于请求分配的内存大小范围较广的系统；最差满足法适用于请求分配的内存大小范围较窄的系统；最差满足法适用于请求分配的内存大小范围较窄的系统；首次满足法则适用于事先无法获知请求分配和回收情况的系统。首次满足法则适用于事先无法获知请求分配和回收情况的系统。最优满足法无论分配与回收都需要查表，故最费时间；最优满足法
41、无论分配与回收都需要查表，故最费时间；最差满足法分配时无需查表，但回收时却需查表并根据回收空闲块的大小确定其在最差满足法分配时无需查表，但回收时却需查表并根据回收空闲块的大小确定其在表中应插入的位置；表中应插入的位置；而首次满足法在分配时需要查表，回收时直接插入到表头即可。而首次满足法在分配时需要查表，回收时直接插入到表头即可。2023-8-17运行时存储空间管理429.6.2隐式存储回收隐式存储回收存储块格式：存储块格式：标记标记:对已分配的块跟踪程序中各指针的访问路径，如果对已分配的块跟踪程序中各指针的访问路径，如果某个块被访问过，就给这个块加一个标记。某个块被访问过，就给这个块加一个标记。回收回收:当用户申请得不到满足或空闲块降到某个值时，所当用户申请得不到满足或空闲块降到某个值时，所有未加标记的存储块回收到一起，并插入空闲块链表中，然有未加标记的存储块回收到一起，并插入空闲块链表中，然后消除在存储块中所加的全部标记。后消除在存储块中所加的全部标记。块块长长度度访访问问计计数数标标记记指指针针用用户户使使用用空空间间
