第4章 存储管理

4.1 概述

操作系统中的存储管理担负着对主存储器空间进行管理的职责。关于辅助存储器控件的管理属于文件系统的范畴。

4.1.1 信息的二级存储

4.1.2 存储管理的功能

主存储器的空间分为两部分：系统区和用户区。系统区用来存放操作系统与硬件的接口信息（如新旧PSW、定时时间、外围设备的工作情况）、操作系统的管理信息和程序、标准子程序等。其余的存储空间都属于用户区，用来存放用户的程序和数据。存储管理是对主存空间的用户区进行管理，其目的是尽可能地方便用户和提高主存空间的利用率。

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

把尚未占用的空间称为空闲区（或称自由区）。

2.实现地址转换

由于用户程序中使用的地址是相对地址（也称逻辑地址），而处理器执行程序时要按主存储器的绝对地址（也称物理地址）访问主存，所以存储管理必须配合硬件进行地址转换工作，把一组相对地址转换成绝对地址，以保证处理器的正确执行。

3.主存空间的共享与保护

4.主存空间的扩充

4.2 重定位

4.2.1 绝对地址和相对地址

主存储器的存储单元以字节为编址单位，每个存储单元都有一个地址与其对应。假定主存储器的容量为n，则该主存储器就有n个存储单元（n个字节的存储空间），其地址编号为：0，1，2，...,n-1。我们把主存空间的地址编号称为主存储器的绝对地址，而与绝对地址对应的主存空间称为物理地址空间。

用户程序中使用的地址称为相对地址，而与相对地址对应的存储空间称为逻辑地址空间。

4.2.2 重定位方式

把相对地址转换为绝对地址的工作称为重定位或地址转换。

重定位的方式可以有静态重定位和动态重定位两种。

1.静态重定位

在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在作业执行前集中一次完成的，所以在作业执行过程中无需在进行地址转换工作。这种定位方式称为静态重定位。

2.动态重定位

动态重定位是由软件和硬件相互配合来实现的。硬件设置一个基址寄存器，当存储管理为作业分配一个主存区域后，装入程序原封不动地把作业装入到所分配的区域中，并把改主存区域的起始地址存入相应作业的进程控制块中。当作业进程被选中去占用处理器时，随同现场信息的恢复，主存区域的起始地址也被存入基址寄存器中。在作业执行过程中，由硬件的地址转换机构动态地进行地址转换。处理器每执行一条指令时只要把相对地址与基址寄存器中的值相加就可得到绝对地址。这种定位方式是在指令执行过程中进行的，所以称为动态重定位。

4.3 单用户连续存储管理

4.3.1 存储空间的分配

单用户连续存储管理是一种最简单的存储管理方式。在这种管理方式下，除操作系统占用的一部分主存空间外，其余剩下的主存空间都分配给一个作业使用，即在任何时刻主存中最多只有一个作业，故适合于单道运行的计算机系统。

采用这种管理方式时，处理器中设置一个界限寄存器（Boundary Registrt），寄存器内容为当前可供用户使用的主存区域的起始地址。

4.3.2 覆盖技术

4.3.3 对换技术

在分时系统中，可用对换（Swapping）方式让多个用户的作业轮流进入主存储器执行。

4.4 固定分区存储管理

4.4.1 基本原理

固定分区存储管理方式是把主存储中可分配的用户区域预先划分成若干个连续区，每个连续区称为一个分区。

4.4.2 主存空间的分配与回收

4.4.3 地址转换和存储保护

4.5 可变分区存储管理

可变分区存储管理不是预先把主存储器中的用户区域划成分区而是在作业要求装入主存储器时，根据作业需要的主存空间大小和当时主存空间使用情况来决定是否可以装入改作业。

4.5.1 主存空间的分配与回收

1.分区的划分

系统初始启动时，主存储器中除操作系统占用部分外，把整个用户区看做一个大的空闲区。当有作业要装入主存储器时，根据作业对主存空间的需要量，从空闲区中划出一个与作业长度一致的分区来装入作业，剩余部分仍为空闲区。当空闲区能满足需求时，作业可装入，当作业对主存空间的需要量超过空闲区长度时，则作业暂时不能装入。

2.主存空间的分配算法

为了便于对主存空间的管理，分区分配表可由两张表格组成，一张是“已分配区表”，另一张是“空闲区表”。已分配区表记录已装入主存的作业在主存中占用分区的始址和长度，在标志位中指出占用该分区的作业名。空闲分区表记录主存中当前可供分配的空闲区的始址和长度，在标志位中指出该分区是尚未分配的空闲区。

可变分区管理方式常用的主存分配算法有最先适应分配算法、最优适应分配算法和最坏适应分配算法。

（1）最先适应分配算法

每次分配时总是顺序查找空闲区表，找到第一个能满足作业长度要求的空闲区，分割这个找到的空闲区，一部分分配给作业，另一部分仍为空闲区。

（2）最优适应分配算法

按作业要求从所有空闲区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。

（3）最坏适应分配算法

这种算法挑选一个最大的空闲区域分配一部分给作业使用，是剩下的部分不至于太小，仍可供分配使用。

3.主存空间的回收算法

当作业执行结束撤离时，应收回主存空间，同时要修改两张表格。先从已分配区表中找出作业占用的分区，把表中相应栏的标志改成“空”，再将归还的分区登记到空闲区表中。

4.5.2 地址转换和存储保护

采用可变分区方式管理时，一般均采用动态地址定位方式装入作业。因此，要有硬件的地址转换机制做支持。硬件设置两个专用的控制寄存器：基址寄存器和限长寄存器，以及一条加法线路、比较线路等。

4.5.3 移动技术

把作业从一个存储区域移到另一个存储区域的工作称为移动。采用移动技术有两个目的。

1.集中分散的空闲区

2.便于作业动态扩充主存

把操作系统所占用的系统资源和所需处理器的时间称为系统开销。

4.6 页式存储管理

4.6.1 页式存储管理的基本原理

页式存储管理是把主存器分成大小相等的许多区，每个区称为一块。与此对应，编址程序的相对地址也分成页，页的大小与块的大小相等。

采用分页式存储管理时，相对地址由两部分组成：页号和页内地址。

作业执行时根据相对地址中的页号找到该页所占的主存块号，再确定当前指令应访问的主存绝对地址。

页式存储管理必须解决两个关键的问题：第一，怎样知道主存储器中哪些块已被占用，哪些块是空闲的；第二，作业信息被分散存放后如何保证作业的正确执行。

4.6.2 页式主存空间的分配与回收

页式存储管理把主存储器的可分配区域按页面大小分成若干块，主存空间按块为单位进行分配。可用一张主存分配表来记录已分配的块和尚未分配的块以及当前剩余的空闲块数。由于块的大小是固定的，所以可以用一张“位示图”来构成主存分配表。

块号=字号*字长+位号

假定归还块的块号为i，则在位示图中对应的位置为：

字号=[i/字长]，位号=i mod 字长

其中,[]表示取i被字长除后商的整数部分，而mod表示取其余数部分。

4.6.3 页表和地址转换

1.页表

当主存中空闲块数能满足作业要求时，存储管理就找出这些空闲块分配给作业，同时，为作业建立一张页表，指出相对地址中页号与主存中块号的对应关系。

2.地址转换

页式存储管理采用动态重定位方式装入作业，作业执行时由硬件的地址转换机构来完成从相对地址到绝对地址的转换工作。

绝对地址=块号*块长+页内地址

3.快表

页式存储管理中的页表一般是存放在主存储器中的。

利用高速缓冲存储器存放页表的一部分，把存放在高速缓冲存储器中的部分页表称为快表。通常把用来存放快表的高速缓冲存储器称为相联存储器（associative memory）。

4.7 虚拟存储管理

4.7.1 什么是虚拟存储器

虚拟存储器实际上是为扩大主存容量而采用的一种管理技巧。

4.7.2 虚拟存储器的工作原理

工作原理：把作业信息保留在磁盘上，当要求装入时，只将其中一部分先装入主存储器，作业执行过程中，若要访问的信息不在主存中，则再设法把这些信息装入主存。

4.7.3 页式虚拟存储器的实现

1.实现原理

2.页面调度

采用某种算法选择一页暂时调用，把它存放到磁盘上去，让出主存空间，用来存放当前要使用的页面这一过程称为页面的调度。

页面调度算法

（1）最佳调度算法（Optimal，缩写为OPT）

这是一种理想的调度算法。总是把以后不再访问的页面或距当前最长时间后在访问的页面调出。

（2）先进先出调度算法（First In First Out，缩写为FIFO）

总是把先进入主存储器的页面先调出

（3）最近最久未使用调度算法（Least Recently Used，缩写为LRU）

距当前最长时间内没有使用过的页面先调出。

（4）最近最不经常使用的调度算法（Least Frequently Used）

在最近一段时间内使用次数最少的页面先调出。

3.缺页中断率

如果作业执行中访问页面的总次数为A，其中有F次访问的页面尚未装入主存，故产生了F次缺页中断。现定义缺页中断率f如下：

f=F/A

影响缺页中断率的因素如下：

（1）分配给作业的主存块数

（2）页面大小

（3）程序的编制方法

（4）页面调度算法

4.7.4 多级页表

4.8 UNIX系统的页式虚拟存储管理

4.8.1 UNIX的虚拟地址结构

UNIX采用页式虚拟存储管理，并把编程序时用的地址称为虚拟地址。

UNIX把进程的地址空间分成三个区段，它们是系统区段、程序区段和控制区段。

操作系统在系统区段运行，所以当进程调用操作系统功能而转入核心态运行时就要访问系统区段。正文段和非共享程序都在程序区段。控制区段中是用户栈、核心栈、user区等。系统区段中的程序和数据常驻主存，其余两个区段中的信息可随执行情况在主存和磁盘对换区之间换进/换出。

每个进程都用虚拟地址访问主存单元。每个虚拟地址的最高两位（第31和30位）表示访问的是那个区段；最低9位（第8~0位）表示页内地址，也即每个页面由512个字节组成，UNIX把它称为字节偏移量；其余21位（第20~9位）表示页号。

4.8.2 UNIX的页表和地址转换

UNIX把进程的地址分成三个区段后，必须为每个区段建立一张页表。UNIX把主存块称为物理页，用物理页号表示主存块号。

4.8.3 UNIX的页面调度

为了提高系统的效率，UNIX采取了如下的一些优化措施。

（1）一个正在与外围设备交换信息的页面或一个正在被装入的页面是不能被替换的。

（2）页面调度采用二次机会页面替换算法。

（3）为了装入一个新页而要调出一页时，要检查被调出页的修改位标志。若该页被修改过，则调出时必须把该页的内容写回磁盘上，否则就不必写回磁盘，以减少输入/输出的传递。

（4）系统中有一个2号进程，UNIX把它称为页面守护进程，它的作用是保证有足够的空闲物理页可供使用。