《计算机操作系统》学习笔记（三）---存储器管理

一、程序的装入和链接

一个用户的源代码变为一个可执行的程序需要经过三步：首先，由编译程序将源代码编译成若干个目标模块；其次，由链接程序将这些目标模块以及库函数链接成一个完整的装入模块；最后，由装入程序将装入模块装入内存。

程序的装入分绝对装入方式和可重定位装入方式两种；绝对装入是指在装入内存之前已经知道程序的首地址了，装入时只要从该首地址不断向后扩展就行；而可重定位装入是指在装入内存之前根本不知道程序会从哪里开始装入，知道的只有每条语句相对于首地址的位移量，首地址是在装入时确定的，确定之后再根据相对于首地址的位移量得出每条语句的地址。

程序的链接可分为：静态链接，即程序装入之前，已将各目标模块及它们所需的函数库连接成一个完整的装配模块；装入时动态链接，即程序装入时，将各目标模块及它们所需的函数库连接成一个完整的装配模块，即边装入变链接；运行时动态链接，即主程序装入后，在运行之时，需要哪个模块再进行对该模块的链接；

二、储存器的分配方式

1、单一连续分配

把内存分为系统区和用户区两部分，系统区仅提供给OS使用，用户区提供给用户使用，即分配时将整个用户区分配给用户使用；这种方式只用于单用户、单任务的操作系统。

2、固定分区分配

把内存的用户空间划分为若干个固定大小的分区，并为之建立一张分区使用表，当一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将其分配之。

3、动态分区分配

根据进程的是以需要，动态的为之分配内存空间，大小刚适，因而不会浪费存储空间。分区分配中的数据结构包括空闲分区表（利用一张表记录着每个空闲分区的分区序号、分区始址、分区大小）和空闲分区链（使用指针将各个空闲分区连成一条链表）两种。分区分配算法包括首次适应算法（从头开始检测出第一个大小合适的分区分配之）、循环首次适应算法（从上一次分配位置开始检测出第一个大小合适的分区分配之）、最佳适应算法（空闲分区链表为从小到大排序，从头检测出不小于申请分区大小的分区，割下申请分区大小分配之，剩余的插回链表中，容易产生碎片哦）。

4、可重定位分区分配

由于动态分配会造成许多不能使用的小的空闲区，称为“零头”或“碎片”，这时，可以将多个分散在内存中的作业的地址重定位，将它们“拼接”或“紧凑”起来，这样，那些“零头”或“碎片”也就会连接成更大的连续存储空间以便分配之。可重定位分区分配与动态分区分配基本相同，仅仅是前者增加了紧凑功能。

5、对换与覆盖

对换技术：把内存中暂时不能运行的进程或暂时不用的程序和数据，调出到外存上，以便腾出更多的内存空间；

覆盖技术：一个程序被分为若干功能上相对独立的程序段，让那些不会同时执行的程序段共享一块内存。

三、储存器的管理方式

1、分页管理方式

页面与页表：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面；系统又为每个进程建立一张页面映射表，简称页表。

地址变换机构：

基本的：通过逻辑地址的页号与页表寄存器的页表始地址相加，得出该页号在页表中的页表项地址，从该页表项得出与该页号相对应的物理块号首地址，然后让物理块号首地址与逻辑地址的页内地址相加即可得出物理地址。

有快表的：在基本的地址变换机构中增加了“联想寄存器”或“快表”，将部分页表放在快表中，在查找（在快表中的查找不需要与页表始址相加了，是直接一个一个对比查找的）后如果发现快表中没有该页号对应的页表项，再从内存中的页表查找，记得执行过后要将此页表项加入快表中哦。

2、请求分页管理方式

请求分页是建立在基本分页基础上的，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。

（1）硬件支持

页表机制：比基本页表增加了（状态位P，访问字段A，修改位M，外存地址位）；

缺页中断机构：与一般中断不同，它是在指令执行期间产生和处理中断信号的，并且一条指令在执行期间可能要产生多次缺页中断；

地址变换机构：比基本分页系统地址变换机构增加了某些功能，如：产生和处理缺页中断，以及从内存中换出一页功能等等。

（2）内存分配策略

物理块的分配策略包括：

固定分配局部置换，即为每个进程固定分配一定数目的物理块，页面置换时，只能从该进程在内存的n个页面中选出一个进行置换；

可变分配全局置换，即先为每个进程固定分配一定数目的物理块，OS也保持一个空闲物理块队列，当哪个进程缺页时，OS再为之分配，直至用完再进行置换，置换时，可以选择全部进程的所有页中的一页进行置换；

可变分配局部置换，即先为每个进程固定分配一定数目的物理块，OS也保持一个空闲物理块队列，当哪个进程缺页时，OS再为之分配，直至用完再进行置换，置换时，只能选择请求调页的那个进程的其中一页进行置换。

（3）内存分配算法

物理块的分配算法包括：

平局分配算法，即将系统中所有可供分配的物理块，平均分配各个进程；

按比例分配算法，即根据进程的大小按比例分配物理块给各个进程；

考虑优先权的分配算法，一部分按比例地分配给各进程，另一部分即根据各进程的优先级，适当地增加相应份额后，分配给各进程。

（4）页面置换策略

在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页的对换区，通常由于对换区常使用连续分配方式，而文件区采用离散分配方式，所以对换区的磁盘I/O速度比文件区的高。

*系统有足够对换区空间，可以全部从对换区调入所需页面；

*系统没有足够对换区空间，不会被修改的页面，从文件区调入，会被修改的，从对换区调入；

*UNIX方式，未运行过的页面，从文件区调入，曾经运行过的，从对换区调入。

（5）页面置换算法

*最佳置换算法（Optimal）：所选择的被淘汰页面，将是以后永不使用或最长时间不被访问的页面；

*先进先出置换算法（FIFO）：先进的页面先被置换；

*最近最久未使用置换算法（LRU）：每个页面增加一个访问字段，记录该页面有多久没被访问过了，最近最久未使用的页面先被置换；

*Clock置换算法：每个页面增加两个访问字段A和M，A记录最近是否被访问（0表示未被访问），M记录是否被修改（0表示未被修改）；分三步寻找淘汰页面：第一步首先寻找（A=0，M=0）的页面，第二步寻找（A=0，M=1）的页面，并将所有A置0，第三步重复第一步，必要时重复第二步，此时一定能找到淘汰页面（A=0，M=0）或（A=0，M=1）；

3、分段管理方式

段与段表：将一个作业按照逻辑关系分成若干个段，称为段；系统又为每个进程建立一张段映射表，简称段表。

地址变换机构：通过逻辑地址的段号与段表寄存器的段表始地址相加，得出该段号在段表中的段表项，从而得出该段号相对应内存的基址，根据内存的基址与通过逻辑地址的段内地址可得出物理地址。

4、请求分段管理方式

请求分段也是建立在基本分段基础上的。

（1）硬件支持

段表机制：比基本段表增加了（状态位P，访问字段A，修改位M，外存地址位，存取方式，增补位）；

缺段中断机构：同样是在指令执行期间产生和处理中断信号的，并且一条指令在执行期间可能要产生多次缺段中断，但分段信息是逻辑单位，不可能出现一条指令或一组信息被分割在两个分段中；

地址变换机构：比基本分段系统地址变换机构增加了某些功能，如：产生和处理缺段中断，以及从内存中换出一段功能等等。

（2）分段的共享和保护

可在系统中配置一张共享段表，所有共享段在该段表中占有一个表项，每个表项包括共享进程计数，即该段有多少个进程在共享；存取控制字段，即不同进程可以有不同的存取权限；段号，即不同进程可以以不同的段号去共享该段；还有段长，内存始地址，存在位等信息。

分段保护包括越界检查和存取控制检查。

5、分页与分段的主要区别

（1）页是信息的物理单位，而段则是信息的逻辑单位；

（2）页的大小固定且有系统决定，而段的长度不定，用户编写的程序不同而不同；

（3）分页的作业地址是一维的，而分段的作业地址空间则是二维的，程序员在标识一个地址时，既得给出段名，又得给出段内地址。

6、段页式管理方式

段页式既能够像分页系统一样有效地提高了内存的利用率，又能够像分段系统一样很好地满足用户需要：如图

地址变换机构：

 

摘自 Linuxer's Blog