资源简介

The Best R&D Courses
存储器管理
4.1 存储器的层次结构
　　在计算机执行时，几乎每一条指令都涉及对存储器的访问，因此要求对存储器的访问速度能跟
得上处理机的运行速度。或者说，存储器的速度必须非常快，能与处理机的速度相匹配，否则会明
显地影响到处理机的运行。此外还要求存储器具有非常大的容量，而且存储器的价格还应很便宜。
The Best R&D Courses
存储器管理
4.1.1 多层结构的存储器系统
　　1. 存储器的多层结构
　 对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底
层是辅存。在较高档的计算机中，还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁
盘缓存、固定磁盘、可移动存储介质等6层。如图4-1所示。
The Best R&D Courses
存储器管理
图4-1 计算机系统存储层次示意
The Best R&D Courses
存储器管理
　　2. 可执行存储器
　　在计算机系统的存储层次中，寄存器和主存储器又被称为可执行存储器。对于存放于其中的信
息，与存放于辅存中的信息相比较而言，计算机所采用的访问机制是不同的，所需耗费的时间也是
不同的。进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进行访问。但对辅
存的访问则需要通过I/O设备实现，因此，在访问中将涉及到中断、设备驱动程序以及物理设备的运
行，所需耗费的时间远远高于访问可执行存储器的时间，一般相差3个数量级甚至更多。
The Best R&D Courses
存储器管理
4.1.2 主存储器与寄存器
　　1. 主存储器
　　主存储器简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，
也称可执行存储器。
　　2. 寄存器
　　寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与CPU协调工作，但价
格却十分昂贵，因此容量不可能做得很大。
The Best R&D Courses
存储器管理
4.1.3 高速缓存和磁盘缓存
　　1. 高速缓存
　　高速缓存是现代计算机结构中的一个重要部件，它是介于寄存器和存储器之间的存储器，主要
用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可大幅度地提高程序执
行速度。高速缓存容量远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访
问速度快于主存储器。
The Best R&D Courses
存储器管理
　　2. 磁盘缓存
　　由于目前磁盘的I/O速度远低于对主存的访问速度，为了缓和两者之间在速度上的不匹配，而设
置了磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。但
磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间
暂时存放从磁盘中读出(或写入)的信息。主存也可以看作是辅存的高速缓存，因为，辅存中的数据必
须复制到主存方能使用，反之，数据也必须先存在主存中，才能输出到辅存。
The Best R&D Courses
存储器管理
　　　　4.2 程序的装入和链接
　　用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通
常都要经过以下几个步骤：
　　(1) 编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object
Module)；
　　(2) 链接，由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一
起，形成一个完整的装入模块(Load Module)；
　　(3) 装入，由装入程序(Loader)将装入模块装入内存。
　　图4-2示出了这样的三步过程。本节将扼要阐述程序(含数据)的链接和装入过程。
The Best R&D Courses
存储器管理
图4-2　对用户程序的处理步骤
The Best R&D Courses
存储器管理
4.2.1 程序的装入
　　为了阐述上的方便，我们先介绍一个无需进行链接的单个目标模块的装入过程。该目标模块也
就是装入模块。在将一个装入模块装入内存时，可以有如下三种装入方式：
　　1. 绝对装入方式(Absolute Loading Mode)
　　当计算机系统很小，且仅能运行单道程序时，完全有可能知道程序将驻留在内存的什么位置。
此时可以采用绝对装入方式。用户程序经编译后，将产生绝对地址(即物理地址)的目标代码。
The Best R&D Courses
存储器管理
　　2. 可重定位装入方式(Relocation Loading Mode)
　　绝对装入方式只能将目标模块装入到内存中事先指定的位置，这只适用于单道程序环境。而在
多道程序环境下，编译程序不可能预知经编译后所得到的目标模块应放在内存的何处。因此，对于
用户程序编译所形成的若干个目标模块，它们的起始地址通常都是从0开始的，程序中的其它地址也
都是相对于起始地址计算的。
The Best R&D Courses
存储器管理
图4-3　作业装入内存时的情况
The Best R&D Courses
存储器管理
　　3. 动态运行时的装入方式(Dynamic Run-time Loading)
　　可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境。但该
方式并不允许程序运行时在内存中移动位置。
The Best R&D Courses
存储器管理
4.2.2 程序的链接
　　1. 静态链接(Static Linking)方式
　　在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再
拆开。在图4-4(a)中示出了经过编译后所得到的三个目标模块A、B、C，它们的长度分别为L、M和
N。在模块A中有一条语句CALL B，用于调用模块B。在模块B中有一条语句CALL C，用于调用模
块C。B和C都属于外部调用符号，在将这几个目标模块装配成一个装入模块时，须解决以下两个问
题：
　　(1) 对相对地址进行修改。
　　(2) 变换外部调用符号。
The Best R&D Courses
存储器管理
图4-4　程序链接示意图
The Best R&D Courses
存储器管理
　　2. 装入时动态链接(Load-time Dynamic Linking)
　　这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接
方式。即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外
部目标模块，并将它装入内存，还要按照图4-4所示的方式修改目标模块中的相对地址。装入时动态
链接方式有以下优点：
　　(1) 便于修改和更新。
　　(2) 便于实现对目标模块的共享。
The Best R&D Courses
存储器管理
　　3. 运行时动态链接(Run-time Dynamic Linking)
　　在许多情况下，应用程序在运行时，每次要运行的模块可能是不相同的。但由于事先无法知道
本次要运行哪些模块，故只能是将所有可能要运行到的模块全部都装入内存，并在装入时全部链接
在一起。显然这是低效的，因为往往会有部分目标模块根本就不运行。比较典型的例子是作为错误
处理用的目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。
The Best R&D Courses
存储器管理
　　　4.3 连续分配存储管理方式
4.3.1 单一连续分配
　　在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提
供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内
存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。
The Best R&D Courses
存储器管理
4.3.2 固定分区分配
　　1. 划分分区的方法
　　可用下述两种方法将内存的用户空间划分为若干个固定大小的分区：
　　(1) 分区大小相等(指所有的内存分区大小相等)。
　　(2) 分区大小不等。
The Best R&D Courses
存储器管理
　　2. 内存分配
　　为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项
包括每个分区的起始地址、大小及状态(是否已分配)，如图4-5所示。
The Best R&D Courses
存储器管理
图4-5 固定分区使用表
The Best R&D Courses
存储器管理
4.3.3 动态分区分配
　　1. 动态分区分配中的数据结构
　　常用的数据结构有以下两种形式：① 空闲分区表，在系统中设置一张空闲分区表，用于记录每
个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项，
如图4-6所示。② 空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一
些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。
通过前、后向链接指针，可将所有的空闲分区链接成一个双向链，如图4-7所示。
The Best R&D Courses
存储器管理
图4-6 空闲分区表
The Best R&D Courses
存储器管理
图4-7 空闲链结构
The Best R&D Courses
存储器管理
　　2. 动态分区分配算法
　　为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区
分配给该作业。由于内存分配算法对系统性能有很大的影响，故人们对它进行了较为广泛而深入的
研究，于是产生了许多动态分区分配算法。
The Best R&D Courses
存储器管理
　　3. 分区分配操作
　　1) 分配内存
　　系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为
u.size，表中每个空闲分区的大小可表示为m.size。
The Best R&D Courses
存储器管理
　　2) 回收内存
　　当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此
时可能出现以下四种情况之一：
　　(1) 回收区与插入点的前一个空闲分区F1相邻接，见图4-9(a)。此时应将回收区与插入点的前一
分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
　　(2) 回收分区与插入点的后一空闲分区F2相邻接，见图
4-9(b)。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小
为两者之和。
The Best R&D Courses
存储器管理
　　(3) 回收区同时与插入点的前、后两个分区邻接，见图
4-9(c)。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
　　(4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区
的首址和大小，并根据其首址插入到空闲链中的适当位置。图4-10示出了内存回收时的流程。
The Best R&D Courses
存储器管理
图4-9 内存回收时的情况
The Best R&D Courses
存储器管理
　　　　　4.4 对换(Swapping)
　　对换技术也称为交换技术，最早用于麻省理工学院的单用户分时系统CTSS中。由于当时计算机
的内存都非常小，为了使该系统能分时运行多个用户程序而引入了对换技术。系统把所有的用户作
业存放在磁盘上，每次只能调入一个作业进入内存，当该作业的一个时间片用完时，将它调至外存
的后备队列上等待，再从后备队列上将另一个作业调入内存。这就是最早出现的分时系统中所用的
对换技术。现在已经很少使用。
The Best R&D Courses
存储器管理
4.4.1 多道程序环境下的对换技术
　　1. 对换的引入
　　在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却
占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞，而无可运行之进程，迫使
CPU停止下来等待的情况；另一方面，却又有着许多作业，因内存空间不足，一直驻留在外存上，
而不能进入内存运行。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。
The Best R&D Courses
存储器管理
　　2. 对换的类型
　　在每次对换时，都是将一定数量的程序或数据换入或换出内存。根据每次对换时所对换的数量，
可将对换分为如下两类：
　　(1) 整体对换。
　　(2) 页面(分段)对换。
The Best R&D Courses
存储器管理
4.4.3 进程的换出与换入
　　1. 进程的换出
　　对换进程在实现进程换出时，是将内存中的某些进程调出至对换区，以便腾出内存空间。换出
过程可分为以下两步：
　　(1) 选择被换出的进程。
　　(2) 进程换出过程。
The Best R&D Courses
存储器管理
　　2. 进程的换入
　　对换进程将定时执行换入操作，它首先查看PCB集合中所有进程的状态，从中找出“就绪”状
态但已换出的进程。当有许多这样的进程时，它将选择其中已换出到磁盘上时间最久(必须大于规定
时间，如2 s)的进程作为换入进程，为它申请内存。如果申请成功，可直接将进程从外存调入内存；
如果失败，则需先将内存中的某些进程换出，腾出足够的内存空间后，再将进程调入。
The Best R&D Courses
存储器管理
　　　　4.5 分页存储管理方式
　　(1) 分页存储管理方式。
　　(2) 分段存储管理方式。
　　(3) 段页式存储管理方式。
The Best R&D Courses
存储器管理
4.5.1 分页存储管理的基本方法
　　1. 页面和物理块
　　(1) 页面。
　　(2) 页面大小。
The Best R&D Courses
存储器管理
　　2. 地址结构
　　分页地址中的地址结构如下：
31 12 11 0
页号 P 位移量 W
The Best R&D Courses
存储器管理
对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则
页号P和页内地址d可按下式求得：
P INT A L
， d = [A] MOD L

The Best R&D Courses
存储器管理
　　3. 页表
　　在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够
正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像
表，简称页表。
The Best R&D Courses
存储器管理
图4-14 页表的作用
The Best R&D Courses
存储器管理
4.5.2 地址变换机构
　　1. 基本的地址变换机构
　　进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为
内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此需要采
用硬件来实现。页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器。
The Best R&D Courses
存储器管理
图4-15 分页系统的地址变换机构
The Best R&D Courses
存储器管理
　　2. 具有快表的地址变换机构
　　由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访
问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。
第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这
种方式将使计算机的处理速度降低近1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是
得不偿失的。
The Best R&D Courses
存储器管理
图4-16 具有快表的地址变换机构
The Best R&D Courses
存储器管理
4.5.3 访问内存的有效时间
　　从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单
元并取出数据，所需要花费的总时间，称为内存的有效访问时间(Effective Access Time，EAT)。
假设访问一次内存的时间为t，在基本分页存储管理方式中，有效访问时间分为第一次访问内存时间
(即查找页表对应的页表项所耗费的时间t)与第二次访问内存时间(即将页表项中的物理块号与页内地
址拼接成实际物理地址所耗费的时间t)之和：
EAT = t + t = 2t
The Best R&D Courses
存储器管理
　　在引入快表的分页存储管理方式中，通过快表查询，可以直接得到逻辑页所对应的物理块号，
由此拼接形成实际物理地址，减少了一次内存访问，缩短了进程访问内存的有效时间。但是，由于
快表的容量限制，不可能将一个进程的整个页表全部装入快表，所以在快表中查找到所需表项存在
着命中率的问题。所谓命中率，是指使用快表并在其中成功查找到所需页面的表项的比率。这样，
在引入快表的分页存储管理方式中，有效访问时间的计算公式即为：
EAT=а×λ+(t+λ)(1—а)+t=2t+λ—t×а
上式中，λ表示查找快表所需要的时间，а表示命中率，t表示访问一次内存所需要的时间。
The Best R&D Courses
存储器管理
　　可见，引入快表后的内存有效访问时间分为查找到逻辑页对应的页表项的平均时间
а × λ + (t + λ)(1 - а)，以及对应实际物理地址的内存访问时间t。假设对快表的访问时间λ为
20 ns(纳秒)，对内存的访问时间t为100 ns，则下表中列出了不同的命中率а与有效访问时间的关系：
命中率 (%) 有效访问时间
а EAT
0 220
50 170
80 140
90 130
98 122
The Best R&D Courses
存储器管理
4.5.4 两级和多级页表
　　1. 两级页表(Two-Level Page Table)
　　针对难于找到大的连续的内存空间来存放页表的问题，可利用将页表进行分页的方法，使每个
页面的大小与内存物理块的大小相同，并为它们进行编号，即依次为0# 页、1# 页，…，n# 页，然
后离散地将各个页面分别存放在不同的物理块中。同样，也要为离散分配的页表再建立一张页表，
称为外层页表(Outer Page Table)，在每个页表项中记录了页表页面的物理块号。
The Best R&D Courses
存储器管理
图4-17　两级页表结构
The Best R&D Courses
存储器管理
　　为了方便实现地址变换，在地址变换机构中，同样需要增设一个外层页表寄存器，用于存放外
层页表的始址，并利用逻辑地址中的外层页号作为外层页表的索引，从中找到指定页表分页的始址，
再利用P2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该
块号P和页内地址d即可构成访问的内存物理地址。图4-18示出了两级页表时的地址变换机构。
The Best R&D Courses
存储器管理
图4-18　具有两级页表的地址变换机构
The Best R&D Courses
存储器管理
　　2. 多级页表
　　对于32位的机器，采用两级页表结构是合适的，但对于64位的机器，采用两级页表是否仍然合
适，须做以下简单分析。如果页面大小仍采用4 KB即212 B，那么还剩下52位，假定仍按物理块的
大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表
项，要占用16 384 GB的连续内存空间。
The Best R&D Courses
存储器管理
　　　4.6 分段存储管理方式
　　存储管理方式随着OS的发展也在不断地发展。当OS由单道向多道发展时，存储管理方式便由单
一连续分配发展为固定分区分配。
The Best R&D Courses
存储器管理
4.6.1 分段存储管理方式的引入
　　1. 方便编程
　　通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都从0开始编址，并有自己的名
字和长度。因此，程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决
定的，这不仅可以方便程序员编程，也可使程序非常直观，更具可读性。例如，下述的两条指令便
使用段名和段内地址：
　　　 LOAD 1，[A] |〈D〉；
　　　 STORE 1，[B] |〈C〉；
The Best R&D Courses
存储器管理
　　2. 信息共享
　　在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。比如，为了共享某个过程、函
数或文件。分页系统中的“页”只是存放信息的物理单位(块)，并无完整的逻辑意义，这样，一个可
被共享的过程往往可能需要占用数十个页面，这为实现共享增加了困难。
The Best R&D Courses
存储器管理
　　3. 信息保护
　　信息保护同样是以信息的逻辑单位为基础的，而且经常是以一个过程、函数或文件为基本单位
进行保护的。
The Best R&D Courses
存储器管理
4.6.2 分段系统的基本原理
　　1. 分段
　　在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例
如，有主程序段MAIN、子程序段X、数据段D及栈段S等，如图4-19所示。
　　分段地址中的地址具有如下结构：
段号 段内地址
31 16 15 0
The Best R&D Courses
存储器管理
　　2. 段表
　　在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式
存储管理系统中，则是为每个分段分配一个连续的分区。进程中的各个段，可以离散地装入内存中
不同的分区中。为保证程序能正常运行，就必须能从物理内存中找出每个逻辑段所对应的位置。
The Best R&D Courses
存储器管理
图4-19 利用段表实现地址映射
The Best R&D Courses
存储器管理
3. 地址变换机构
　　为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表
始址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL，
表示段号太大，是访问越界，于是产生越界中断信号。若未越界，则根据段表的始址和该段的段号，
计算出该段对应段表项的位置，从中读出该段在内存的起始地址。然后，再检查段内地址d是否超过
该段的段长SL。若超过，即d>SL，同样发出越界中断信号。若未越界，则将该段的基址d与段内地
址相加，即可得到要访问的内存物理地址。图4-20示出了分段系统的地址变换过程。
The Best R&D Courses
存储器管理
图4-20 分段系统的地址变换过程
The Best R&D Courses
存储器管理
　　4. 分页和分段的主要区别
　　(1) 页是信息的物理单位。
　　(2) 页的大小固定且由系统决定。
　　(3) 分页的用户程序地址空间是一维的。
The Best R&D Courses
存储器管理
　　2. 分段系统中程序和数据的共享
　　在分段系统中，由于是以段为基本单位的，不管该段有多大，我们都只需为该段设置一个段表
项，因此使实现共享变得非常容易。我们仍以共享editor为例，此时只需在(每个)进程1和进程2的段
表中，为文本编辑程序设置一个段表项，让段表项中的基址(80)指向editor程序在内存的起始地址。
图4-22是分段系统中共享editor的示意图。
The Best R&D Courses
存储器管理
4.6.4 段页式存储管理方式
　　1. 基本原理
　　段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段
分成若干个页，并为每一个段赋予一个段名。图4-23(a)示出了一个作业地址空间的结构。该作业有
三个段：主程序段、子程序段和数据段；页面大小为 4 KB。在段页式系统中，其地址结构由段号、
段内页号及页内地址三部分所组成，如图4-23(b)所示。
图4-23 作业地址空间和地址结构
The Best R&D Courses
存储器管理
　　在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。
段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。图4-24示
出了利用段表和页表进行从用户地址空间到物理(内存)空间的映射。
The Best R&D Courses
存储器管理
图4-24 利用段表和页表实现地址映射
The Best R&D Courses
存储器管理
　　2. 地址变换过程
　　在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长
TL。进行地址变换时，首先利用段号S，将它与段长TL进行比较。若S < TL，表示未越界，于是利
用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用
逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b
和页内地址来构成物理地址。
The Best R&D Courses

展开更多......

收起↑