考研笔记-计算机之操作系统:存储器管理(内存分配)

表-存储器分配方式分类

分类依据

分配类型

分配方式

适用环境

关系

分配的内存空间是否连续

连续分配

同一进程（程序）分配的内存空间连续

非虚拟存储器的内存分配

连续分配只能使用静态分配，离散分配可以使用静态分配（非虚拟存储器）或动态分配（虚拟存储器）

离散分配

同一进程（程序）分配的内存空间不连续

非虚拟、虚拟存储器的内存分配

内存空间的分配是否一次完成

静态分配

同一进程（程序）的内存空间的分配一次完成

非虚拟存储器的内存分配

动态分配

同一进程（程序）的内存空间的分配分为多次

虚拟存储器的内存分配

表-存储器内存分配

非虚拟存储器内存分配

（程序一次全部装入后才可运行，即只能使用静态分配方式）

连续分配（一个程序占用的全部内存空间必须连续）

单一连续分配

内存分为系统区和用户区，系统区供OS使用，用户区供用户使用。适用于单道程序环境。

分区

（每个分区只装入一道作业，每道作业只占一个分区）

适用于单道程序环境。

固定分区

分区大小相等

分区大小不等

可变分区（或称动态分区）

内存分配

顺序搜索（在分配分区时，分区可动态分割，无内碎片，有外碎片）

首次适应。空闲分区链表按地址递增的次序连接，每次从链首开始查找

循环首次适应。空闲分区链表按地址递增的次序连接，每次从上次找到的空闲分区的下一分区开始查找

最佳适应。空闲分区链表按分区大小从小到大的次序连接，每次从链首开始查找

最坏适应。空闲分区链表按分区大小从大到小的次序连接，每次从链首开始查找

分类搜索（根据分区大小设立不同的空闲分区链表，分配分区时不再划分，无外碎片，有内碎片）

快速适应。每次根据分区的大小从相应的链表中分配

内存回收

1) 空闲分区表中，回收区与插入点的前一元素对应的空闲分区在内存中的物理位置相邻，则将回收区与插入点的前一分区合并，并修改前一分区的大小；

2) 空闲分区表中，回收区与插入点的后一元素对应的空闲分区在内存中的物理位置相邻，则将回收区与插入点的后一分区合并，并修改后一分区的大小和首地址；

3) 空闲分区表中，回收区与插入点的前、后元素对应的两个空闲分区在内存中的物理位置均相邻，则将三个分区合并，并修改前一分区的大小为三个分区大小之和，同时删除后一分区对应的表项；

4) 空闲分区表中，回收区与插入点的前、后元素对应的空闲分区在内存中的物理位置均不相邻，则为该回收区新建一表项，并插入插入点。

伙伴系统（特殊的可变分区）

原理

无论已分配分区还是空闲分区，其大小均为2的k次幂，k为整数且l≤k≤m，其中：2^l表示分配的最小分区的大小，2^m表示分配的最大分区的大小，通常2^m是整个可分配内存的大小。

假设系统的可用空间容量为2^m个字，则系统开始运行时，整个内存区是一个大小为2^m的空闲分区。在系统运行过程中，由于不断的划分（分配和回收），可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k（0≤k≤m）个空闲分区链表。

内存分配

当需要为进程分配一个长度为n的内存空间时，首先计算一个i值，使2^i-1 <n≤2ⁱ，然后在空闲分区大小为2ⁱ的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2ⁱ的空闲分区已经耗尽，则在分区大小为2ⁱ⁺¹的空闲分区链表中寻找。若存在2ⁱ⁺¹的一个空闲分区，则把该空闲分区分为大小相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而将另一个加入分区大小为2ⁱ的空闲分区链表中。若大小为2ⁱ⁺¹的空闲分区也不存在，则需查找大小为2ⁱ⁺²的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2ⁱ⁺¹的两个分区，一个用于分配，一个加入到大小为2ⁱ⁺¹的空闲分区链表中；第二次，将第一次用于分配的空闲分区分割为大小为2ⁱ的两个分区，一个用于分配，一个加入到大小为2ⁱ的空闲链表中。若仍找不到，则继续查找大小为2ⁱ⁺³的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2^k的空闲分区进行k次分割才能得到所需分区。

内存回收

与一次分配可能要进行多次分割一样，一次回收也可能进行多次合并，如回收大小为2ⁱ的空闲分区时，若事先已存在大小为2ⁱ的空闲分区，且该分区与将要回收的分区的物理位置相邻，则应将其与伙伴分区合并为大小为2ⁱ⁺¹的空闲分区，若事先已存在大小为2ⁱ⁺¹的空闲分区，且该分区与新合并的分区的物理位置相邻，又应继续与其伙伴分区合并为大小为2ⁱ⁺²的空闲分区，以此类推。

动态重定位分区

分区紧凑。与动态分区的区别是，在找不到足够大的空闲分区时，可通过动态重定位进行分区紧凑

离散分配（一个程序占用的全部内存空间可以不连续）

基本分页

地址空间分页；内存空间按页分块。（面向内存）

块和区均是对内存空间的划分（是物理划分）。页和段均是对地址空间的划分（是逻辑划分）。

基本分段和基本分页方式下，程序（进程）在地址空间上是连续的，从0号页（或段）开始使用，且页（段）号是连续递增（非间断）的；但映射到内存空间中则是任意的（可连续、可离散）。

段页分配方式下，程序（进程）在地址空间上段内是连续的，段间可能是不连续的，因为段页分配方式下的基本分配单位为页，不同段之间的页号是连续的，但页内地址可能出现断裂（每一页仅属于一个段）。

基本分段

地址空间分段；内存空间按段分区（动态）。（面向程序）

段页

地址空间分段，段再分页；内存空间按页分块

分页与分段的区别

1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，分页仅仅是由于系统管理的需要而不是用户的需要；段是信息的逻辑单位，含有一组意义相对完整的信息，可消减内存的内零头，分段的目的是更好满足用户的需要。

2) 页的大小固定统一（故在进行逻辑地址到物理地址的变换中，物理地址是通过页的物理地址与页内地址拼接实现的），且由系统决定；段的长度不固定（故在进行逻辑地址到物理地址的变换中，物理地址是通过段的物理地址与页内地址相加实现的），决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

3) 分页的作业地址空间是一维的（因为各页长度相等），即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；分段的作业地址空间则是二维的（因为各段长度不相等），程序员在标识一个地址时，既需给出段名，又需给出段内地址。

虚拟存储器内存分配

（仅有离散分配方式。程序的运行可分多次装入，即只能使用动态分配方式）

请求分段

请求分页

OPT

理论上的算法。每次选择的淘汰页面是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。常用该算法去评价其他算法。

FIFO

每次选择的淘汰页面是最先进入内存的页面，即在内存中驻留时间最久的页面。

LRU

(Least Recently Used)最近最久未使用。选择最近最久未使用的页面予以淘汰（用最近的过去作为最近的将来的近似）。考虑所有的页面距各自最近的一次访问的时长（即次数固定为一次，看时间的长短）。

CLOCK

NRU

（Not Recently Used）最近未使用算法。所有页面通过链接指针链接成一个循环队列。每个页面附设一个访问位，当被访问时其访问位置1。选择淘汰页面时，若页面的访问位为0，则将其换出；若为1，将其置为0，暂不换出，再按FIFO算法检查下一页面，当检查到队列的最后一个页面时，若其访问位仍为1，则返回队首去检查第一个页面。循环一趟后必可找到一个访问位为0的页面。

改进CLOCK

置换时考虑的因素为使用情况（访问位A）和置换代价（修改位M），访问位的权重高于修改位的权重（即相对于修改位优先考虑访问位，

(A=0,M=0)>(A=0,M=1)>(A=1,M=0)>(A=1,M=1)）。

算法：

1) 从指针所指示的当前位置开始进行第一轮循环队列扫描，寻找A=0且M=0的页面，将所遇到的第一个页面选为淘汰页，若没有找到则转入2)。（第一轮扫面期间不改变访问位A）

2) 进行第二轮扫描，寻找A=0且M=1的页面，将所遇到的第一个页面选为淘汰页，若没有找到则转入1)。（第二轮扫面期间将所有扫描过的页面的访问位A复0）

扫描期间（所有轮次）修改位不变；第一轮访问位不变，第二轮访问位复0（第二轮扫描过的），因为算法第一轮和第二轮已覆盖了M=0和1两种情况，故只需将A复为0，算法第二遍一定可以找到符合条件的页面。

LFU

(Least Frequently Used)最少使用置换算法。考虑最近一段固定时间内各个页面被访问的次数（即时间固定，看次数的多少）。

PBA

(Page Buffering Algorithm)页面缓存算法。采用可变分配和局部置换方式，置换算法采用FIFO。算法规定将一个被淘汰（被淘汰的原因不是内存空间不够）页面放入两个链表中的一个，若页面未被修改，则将其放入空闲链表中，若页面已修改，则将其放入已修改链表中。当置换未修改的页面时，并不将它换出内存，而是将该页面所在的物理块挂在自由页链表的末尾；当置换已修改的页面时，并不将它换出内存，而是将该页面所在的物理块挂在修改页链表的末尾，当被修改的页面数达到一定值时，再将它们一起写回磁盘。

段页式虚拟

请求分页系统

内存分配策略

固定分配

每个进程拥有的物理块数在运行期间不变。

可变分配

每个进程拥有的物理块数在运行期间可变。

页面置换策略

局部置换

每次换出的页面均是该进程的页面。

全局置换

每次换出的页面可以是内存的任意一个页面。

三种策略（固定分配与全局置换矛盾，进程拥有的物理块数会改变）

固定分配，局部置换

某进程缺页时，只能将该进程的页面换出。

可变分配，局部置换

某进程缺页时，①先将该进程的页面换出；②当进程缺页太频繁时，OS为该进程分配若干附加物理块，直至该进程的缺页频率降到适当程度为止；若某进程的缺页率较低时，也可适当减少分配其的物理块数。

可变分配，全局置换

某进程缺页时，①先从空闲物理块队列中取物理块分配给该进程；②当空闲物理块分配完时，可将任一进程的页面换出。

缺页时考虑解决方案的优先级

局部置换>额外分配>全局置换（即先考虑局部置换，再考虑额外分配，最后考虑全局置换）。