操作系统原理：内存分配、回收与地址转换

1.内存空间的分配与回收

由于任何程序及数据必须调入内存后才能执行和直接访问，因此内存管理的首要任务就是当用户需要内存时，系统按照用户程序（进程）对内存需求的大小，依据某种分配算法把一个空闲内存空间分配给用户程序（进程）使用，不需要时再及时回收，以供其他用户程序使用。为此，系统需要考虑如何进行内存分配才能使内存的利用率最高，以及采用什么样的数据结构来记录和管理内存空间的占用与空闲情况。在多道程序设计环境中，内存分配的功能包括制定分配策略、构造分配用的数据结构、响应用户程序的内存分配请求和回收用户程序释放的内存区。

为了有效、合理地使用内存，在设计内存分配与回收算法时，必须考虑以下4个问题。

（1）数据结构。登记内存的使用情况，记录可供分配的内存空闲区大小和起始地址，以供分配和回收内存时使用。

（2）放置策略。决定内存中放置信息（程序或数据）的区域（或位置），即怎样在当前的内存空闲区中选择一个或几个空闲区来放置信息。

（3）调入策略。确定外存中的程序段和数据段在什么时间、以什么样的控制方式进入内存。

（4）淘汰策略。在需要将某个程序段或数据段调入内存却出现内存没有足够空闲区时，由淘汰策略来决定把内存中的哪些程序段和数据段由内存调出（淘汰）放入到外存，以便为调入的程序段或数据段腾出足够的内存空间。

2.地址转换（地址重定位）(www.xing528.com)

程序运行时不能直接使用逻辑地址访问内存中的信息，而必须把程序地址空间中的逻辑地址转换成内存空间中的物理地址，才能完成对内存信息的访问。实现逻辑地址到物理地址转换的方式有以下三种。

（1）编程或编译时产生绝对地址

程序中所使用的绝对地址（物理地址）可以在编译或汇编时形成，也可由用户直接赋予。但由用户直接给出绝对地址不仅要求熟悉内存的使用情况，而且一旦程序被修改就会造成程序中某些地址发生变动，因此要对这些涉及访问地址的指令进行更改，即将指令中的访问地址更改为变动后的地址，否则就会出错。例如，如果预先知道一个用户程序驻留内存的地址将由某处开始，那么产生的编译代码（可执行程序）中的绝对地址都是针对此地址的偏移。但是如果此后该代码存放的内存起始地址发生变动，那么就必须重新修改代码中所有出现在指令中的地址。此外，修改的程序中会引起指令条数和数据的增减，这就会使某些指令中的转移地址和数据的存储地址（都是绝对地址）发生改变。因此，通常的做法是在程序中采用符号地址，然后由编译程序或汇编程序在对该程序编译或汇编时，再将这些符号地址转换为绝对地址。

（2）静态地址转换

静态地址转换就是之前介绍的静态重定位，即在程序装入内存时，一次性完成程序中所有逻辑地址到物理地址的转换。如果在编译时不知道程序将放置于内存的什么位置，那么编译程序在编译该程序时产生的是可重定位代码（起始地址为0）。在这种情况下，最终的地址转换（静态重定位）延迟到装入内存时再完成。如果在内存中代码存放的起始地址发生变动，那么只需根据变动后的起始地址对该代码再次进行静态重定位即可，这种装入方式称为可重定位方式。可重定位方式的地址转换，可以在程序装入内存时到程序运行前的任何时间里一次性完成。在一些早期的系统中都有一个装入程序（也称加载程序），它负责将用户程序装入内存，并将程序中使用的逻辑地址转换成内存物理地址。

（3）动态地址转换

在现代计算机系统中，大都采用了动态地址转换技术（即之前介绍的动态重定位），这种地址转换方式是在程序执行过程中，一旦执行的指令中出现访存地址（逻辑地址）时，就由系统硬件完成这个逻辑地址到内存物理地址的转换。通常是在系统中设置一个重定位寄存器（即前述的基址寄存器BR），其内容由操作系统用特权指令来设置。用户程序运行时，地址转换机构首先判断CPU提供的访存地址（逻辑地址）是否超出了该程序的长度，若越界，则终止该程序的运行；否则将CPU提供的访存地址（逻辑地址），与重定位寄存器中的值（基地址）相加形成要访问的内存物理地址。由于地址转换是在指令执行过程中进行的，因此程序中凡是涉及访存地址的指令，只有当其执行时才进行地址转换，否则不进行地址转换，这样就节省了CPU的时间。