存储管理
1.程序的链接和装入
1）源程序装入主存的步骤：
- 编译：由编译程序（Compiler）将用户源代码编译成若干目标模块；
- 链接：由链接程序（Linker）将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块；
- 装入：由装入程序（Loader）将装入模块装入主存
2）程序的链接方式：
- 静态链接：在程序运行前，将各个目标模块以及所需的库函数链接成一个完整的装入模块，又称为可执行文件。
- 装入时动态链接：在装入主存时，采用边装入边链接的方式。即在装入一个目标模块时，若需要调用另一个模块，则找出该模块，将它装入主存，并修改目标模块的逻辑地址。
- 运行时动态链接：指在程序执行过程中当需要该目标模块时，才把它装入主存并进行链接，而不是把所有模块一起装入主存。
3）装入主存的方式：
- 绝对装入方式：如果在编译时就知道程序驻留在主存的具体位置，则编译程序将产生物理地址的目标代码。绝对装入程序按照装入模块的地址，将程序和数据装入主存。模块装入后，由于程序中的逻辑地址和与实际主存地址一致，所以不需要进行地址修改。只适合于单道程序环境。
- 静态重定位装入：在装入作业时，把作业中的指令地址和数据地址一次性全部转换成物理地址，这样在作业执行过程中无无需再进行地址转换。
- 动态重定位装入：在装入时，直接把作业装入主存中。在作业执行时，随着每条指令的访问，由硬件地址转换机制自动将指令中的逻辑地址换成物理地址。地址转换机制由一个基地址寄存器和一个地址转换线路组成。在该方式下，作业可以改变存储区域，则成程序是可浮动的。
2.连续的存储管理
1）单一连续存储管理
- 特点：操作系统占用一部分主存空间，其余的主存空间作为一个连续分区全部分配给一个作业使用，即任何时刻主存中最多只有一个作业。适合于单用户，单任务操作系统。
- 缺点：CPU利用率比较低；存储器得不到充分利用；计算机外围设备利用率不高
2）固定分区存储管理：
- 特点：预先把主存的用户区分割成若干连续区域，每一个连续区域成为一个分区，每个分区大小不一定相同。分割完成后，大小不能改变。每个分区只可以装入一个作业，不允许作业跨分区存储。
- 空间的分配和去配：系统设置一直主存分配表以说明各分区的分配情况。该表长度由分区个数决定，记录了各个分区的起始地址和长度，并为每个分区设置一个状态标志位。当标志为0时，该分区为空闲。
3）可变分区存储管理：
- 特点：根据作业所需空间大小和当时主存空间的实际情况决定是否为该作业分配一个分区。主存的分区大小是可变的，根据作业实际需求进行分区划分。
- 空间分配和去配：当作业要求装入主存，系统根据作业对主存空间的实际需求量进行分配。若空闲分区大小为m，作业所需空间为n，m-n<=size（size为系统事先规定不可再分割的剩余分区的大小），则将整个空闲分区分配个作业；否则从空闲分区中分割出一个分区给作业；若m<n，则不能装入。
- 可变分区数据结构：
a。分区表：设置空闲分区表和已分配分区表。表记录起始地址，长度，标志位（指出该分区分配情况）。
b。分区链：在每个分区的起始部分设置用于控制分区分配的信息以及用于链接前一个分区的前向指针；在分区尾部设置一个后向指针，将所有空闲分区形成双项链。 - 可变分区分配算法：
a。最先适应分配算法：总是按顺序查找空闲分配表，选择第一个满足作业空间大小的分区进行分割。（最好最快）
b。最优适应分配算法：总是选择一个满足作业空间大小的最小空闲分区进行分配。（性能最差）
c。最坏适应分配算法：总是选择一个满足作业空间大小的最大空闲分区进行分配。 - 空间回收：检查是否存在与回收区相邻的空闲分区，有则合并。
a。上有空闲或下有空闲：空闲区数不变，合并为一个空闲区，修改空闲区的起始地址或长度。
b。上，下都有空闲：空闲区数-1
c。上，下都没有空闲：空闲区数+1 - 移动技术：将分散的空闲区集中起来以容纳新的作业，提高空间利用率。
4）覆盖技术和交换技术：在多道程序环境下用来扩充主存的方式。
- 覆盖技术：一个程序不需要把所有的指令和数据都装入主存。程序被划为若干功能相对独立的程序段，让这些不会同时执行的程序段共享一块主存。将程序的必要部分的代码和数据常驻主存，可选部分平时放在外存，需要才装入主存。所以主存分为常驻区和覆盖区（可多个）。主要在同一个进程或作业内进行
- 交换技术：把主存中暂时不能运行的进程或暂时不使用的程序和数据换出到外存，以腾出空间把已具备运行条件的进程或进程所需的程序和数据换入主存。主要是进程或作业之间进行。
3.页式存储管理
1）基本原理：把主存划分成大小相等的若干区域，每个区域称为一块，并加以顺序编号。用户逻辑地址由两部分组成：页号和页内地址。地址长度32位为例：块大小为2^12=4KB，逻辑地址有2^20页。
2）存储空间的分配与去配：采用“位示图”来记录主存的分配情况。图中的每一位与一个物理块对应，用0/1表示占用情况，另用一个字节记录当前系统的剩余空闲块总数。根据所在字号，位号，得到块号：块号=字号 * 字长 + 位号。回收时，根据块号，得到字号=块号/字长，位号=块号%字长。
3）页表与地址转换： 系统给作业分页，建立一张页面映像表，简称页表。它实现了页号到块号的地址映像。分页式存储管理采用动态重定位方式装入作业。根据页号，获取块号，再按逻辑地址的页内地址计算出物理地址。
物理地址 = 块号 * 块长 + 页内地址
4）快表：在地址变换机构中增设一个具有并行查找能力的小容量高速缓冲寄存器，又称为相联寄存器。在该寄存器中存放页表的一部分，该部分的页表成为快表。
4.段式存储管理
1）基本原理：每个作业由若干个相对独立段组成，段号从0开始，每一段的逻辑地址也从0开始。段内地址是连续的，而段与段之间的地址可以是不连续的。段式存储管理的逻辑地址由段号和段内地址两部分组成：
2）空间的分配和去配：以段为单位进行主存分配，每个段占有一个连续空间，但各个段之间可以离散地存放在主存的不同区域。系统为每个进程建立一直段映射表，简称段表。每个段在表中占一个表项，记录该段在主存的起始地址和长度。如果装入时没有满足该段空间大小的空闲区，则可采用移动技术合并分散的空闲区。执行结束后，把回收的主存空间登记在空闲区表中。
3）地址转换：采用动态重定位装入作业。段表的表目起到了基址寄存器和限长寄存器的作用。
5.分页和分段存储管理的主要区别
- 页是信息的物理单位，是系统管理的需要而不是用户；段是信息的逻辑单位，它含有一组意义相对完整的信息，更好满足用户需要。
- 页的大小固定且系统决定；段的长度不固定，有用户程序决定
- 分页式作业的地址空间是一维的，页间逻辑地址是连续的；分段式作业的地址空间是二维的，段间逻辑地址是不连续的。
6.段页式存储管理
用户对作业采用分段组织，在主存空间分配时，把每段分成若干页面，这样每段不必占据连续的主存空间，可把它按页存放在不连续的主存块。逻辑地址格式：
段页式存储管理的地址转换机构：
7.虚拟存储管理
1）局部性原理：程序的执行仅局限于某个部分，而它所访问的存储空间也局限在某个区域中。表现在两个方面：时间局限性，空间局限性。
- 时间局限性：某条指令一旦执行，在不久以后该指令可能再次执行。
- 空间局限性：一旦程序访问了某个存储单元，在不久以后其附近的存储单元也将被访问。
2）虚拟存储管理基本原理：基于局部性原理，可以把作业信息保存在磁盘上，当作业请求装入时，只需将当前运行所需要的一部分信息先装入主存。作业执行过程中，如果所访问信息已调入主存，则可继续执行；如果没有装入，则将信息装入，继续执行；如果此时主存已满，则系统将主存暂时不用的信息置换到磁盘上。
3）四大特征：离散性，多次性（最重要特效），对换性，虚拟性
8.请求分页式存储管理
1）调入方式：当需要访问的数据和指令不在主存中，从而发生缺页中断，于是系统将外存中的相应页面调入主存。
2）页表机制：
| 页号 | 物理块号 | 状态位 | 访问字段 | 修改位 | 辅存地址 |
- 状态位：该页是否已调入主存，是则为1
- 物理块号：当状态位为1时，指出该页在主存中的占用块
- 辅存地址：当状态位为0时，之处该页在磁盘上的地址
- 访问字段：记录该页在一段时间内被访问的次数或记录该页多久没有被访问
- 修改位：表示该页在调入贮存后是否被修改，由于作业在辅存中保留一份备份，若没有被修改则不用回写。
3）缺页中断机制和地址变换机制：
4）页面置换策略：
- 固定分配局部置换策略：为每个进程分配一定数目的主存物理块，在整个运行期间不变。如果发送缺页，则只能从该进程在主存的n个页面中选一页换出，保证分配给该进程的主存空间不变。
- 可变分配局部置换：为每个进程分配一定数目的主存物理块，只能从该进程在主存的n个页面中选一页换出。当一个进程的缺页率高时，为该进程分配若干附加物理块，直到缺页率减少到适当程度；若缺页率特别低时，可适当减少物理块数。
- 可变分配全局置换：为每个进程分配一定数目的主存物理块，系统保持一个空闲块队列。当一个进程发生缺页时，从队列中取出一块，分配给该进程。当空闲物理块队列为空时，系统才从主存中选择页面置换。
5）“颠簸”现象：刚被调出的页面又要把它调入，刚刚调入的页面又要调出，如此反复使调度频繁，以至于大部分时间花费在来回调度上的现象。（也叫“抖动”）
6）页面置换算法：
- 最佳置换算法（OPT）：被淘汰的页面将以后永远不再使用，或者在将来最长时间内不再被访问。该算法是理想化算法，是作为衡量其他算法的标准
- 先进先出算法（FIFO）：淘汰最先注入的页面。
- 最近最少用算法（LRU）：选择最近一段时间内最长时间没有被访问的页面调出。在页表增加引用位，每次被访问就置0，重新计时。检查页表各页的引用位，选择最长时间没有被访问的页面淘汰，把页面所有引用位清零。
- 时钟置换算法（Clock）：相当于LRU近似算法。系统选择一个时间周期T，每个一个T就把引用位清零。在T内，被访问的页面引用位为1，没有的仍为0。缺页时，还根据修改位来选择淘汰。淘汰顺序：没有被修改，没有被引用；没有被修改，有引用；有被修改，没有被引用；有修改，有引用。
- 最近最不常用置换算法（LFU）：选择访问次数最少的页面调出
注：部分图片来源与百度