计算机操作系统-第四章--存储器管理ppt课件.ppt

《计算机操作系统-第四章--存储器管理ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统-第四章--存储器管理ppt课件.ppt（161页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章存储器管理(1)第四章 存储器管理引言引言 存储器的层次结构存储器的层次结构 4.1 4.1 程序的装入和链接程序的装入和链接 4.2 4.2 连续分配方式连续分配方式 第四章 存储器管理 引言引言 存储器的层次结构存储器的层次结构引言1 存储器的层次结构1. 1. 存储器的层次结构存储器的层次结构 在现代计算机系统中，存储器是信息外理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。 存储器的层次结构引言2.各种存储器 高速缓存Cache： 少量的、非常快速、

2、昂贵、易变的 内存RAM： 若干兆字节、中等速度、中等价格、易变的 磁盘： 数百兆或数千兆字节、低速、价廉、不易变的 由操作系统协调这些存储器的使用引言3 存储管理的目的1)主存的分配和管理：当用户需要内存时,系统为之分配相应的存储空间；不需要时，及时回收，以供其它用户使用。2)提高主存储器的利用率：不仅能使多道程序动态地共享主存，提高主存利用率，最好还能共享主存中某个区域的信息。引言3 存储管理的目的（续）3)“扩充”主存容量：为用户提供比主存物理空间大得多的地址空间，以至使用户感觉他的作业是在这样一个大的存储器中运行。4)存储保护：确保多道程序都在各自分配到存储区域内操作，互不干扰，防止一

3、道程序破坏其它作业或系统文件的信息。引言4 基本概念1.1.定位（存储分配）定位（存储分配）：为具体的程序和数据等分配存储单元或存储区工作。2.2.映射：映射：把逻辑地址转换为相应的物理地址的过程。3.3.隔离：隔离：按存取权限把合法区与非法区分隔，实现存储保护。引言4 基本概念名空间 程序员在程序中定义的标识符 程序符号集合 由程序员自定义 没有地址的概念符号指令数据说明I/O说明引言4 基本概念5.5.地址空间地址空间 程序用来访问信息所用地址单元的集合 逻辑（相对）地址的集合 由编译程序生成6.存储空间 主存中物理单元的集合 物理（绝对）地址的集合 由装配程序等生成地址映射地址映射Loa

4、d A 200 3456 。 。1200物理地址空间物理地址空间Load A data1data1 3456源程序源程序Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000图41名空间、地址空间、存储空间引言4 基本概念7.逻辑地址与物理地址 逻辑地址（相对地址，虚地址）： 用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息 物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址 8.存储共享 内存共享：两个或多个进程共用内存中相同区域

5、目的：节省内存空间，提高内存利用率 实现进程通信（数据共享） 共享内容： 代码共享，要求代码为纯代码 数据共享引言4 基本概念引言4 基本概念9.存储保护与安全保护目的： 为多个程序共享内存提供保障,使在内存中的各道程序, 只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程序发生错误时, 不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储保护。）引言4 基本概念1) 存储保护 保护系统程序区不被用户侵犯 （有意或无意的） 不允许用户程序读写不属于自己地址空间的数据 （系统区地址空间，其他用户程序的地址空间）引言4 基本概念 2) 保护过程-防止地

6、址越界 每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。引言4 基本概念10.内存“扩充” 通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来“扩充”内存的容量，使用户得到比实际内存容量大的多的内存空间 具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制第四章 存储器管理 4.1 程序的装入和链接4.1 程序的装入和链接图 4-2

7、-1 对用户程序的处理步骤4.1.1 程序的装入1. 绝对装入方式绝对装入方式程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。 图 4-2-2 作业装入内存时的情况2. 可重定位装入方式4.1.1 程序的装入动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所

8、有地址都仍是相对地址。4.1.1 程序的装入3. 动态运行时装入方式 4.2.2 程序的链接图 4-2-3 程序链接示意图1.静态链接方式2. 装入时动态链接装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。 4.2.2 程序的链接3. 运行时动态链接这种链接方式是将对某些模块的链接推迟到执行时才执行，即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。 4.2.2 程序

9、的链接 4.2.3 重定位 把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。如下图，作业i经过重定位，把地址集合映射到以1000为始址的内存中，作为作业i的存储空间。1. 重定位的类型 1)1)静态重定位静态重定位: :当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）作业i在执行前一次变址，直到该作业完成退出内存为止。2)2)动态重定位动态重定位 4.2.3 重定位2)动态重定位 在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。 4.2.3 重定位2.动态

10、重定位的实现方式 重定位寄存器重定位寄存器：在执行一条指令取操作数时，要将指令给出的有效地址(500)与重定位寄存器中的内容（1000）相加，得访问地址（1500），从而实现了地址动态修改。 映象方式映象方式：采用页表来描述虚、实页面的对应关系 。 4.2.3 重定位第四章 存储器管理 4.2 连续分配存储管理 4.2.1 单用户存储管理 在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分：系统区、用户区、空闲区。用户占用区是一个连续的存储区所以又称单一连续区存储管理。 单用户系统在一段时间内，只有一个

11、进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0图图 4-3-1 4-3-1 单一连续区存储分配示意图单一连续区存储分配示意图4.2.1 单用户存储管理工作流程 单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地

12、址是否超越，即可达到保护系统的目的。4.2.1 单用户存储管理工作流程(续)4.2.1 单用户存储管理单用户系统缺点 不支持多道。 主存利用率不高。 程序的运行受主存容量限制。4.2.1 单用户存储管理存储保护 自动地址修改例如，存储器的地址空间为，而操作系统位于低址端的内。对于这样的系统，我们给用户一个位的地址空间，并对其每个存储器访问自动加上。如果操作系统占用高址端的，则我们取每一个存储访问，而实际上，其地址为（）。从而实现了对操作系统的保护。4.2.1 单用户存储管理存储保护（续） 页、页寻址通过对每个用户生成的地址左端拼接上一位来实现区与用户区。把操作系统确定在页，而把用户作业放在页。

13、 界限寄存器通过增加界限寄存器，划分区与用户区。4.2.1 单用户存储管理 4.2.2 固定分区分配 分区式管理是满足多道程序的最简单的存储管理方案。它的基本思想是将内存划分成若干个连续区域，称为分区。每个分区只能存储一个程序，而且程序也只能在它所驻留的分区中运行。 预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业 存储分配：如果有一个空闲区, 则分配给进程 4.2.2 固定分区分配1. 固定分区分区分区4分区分区3分区分区2分区分区1操作系统操作系统多个等待队列多个等待队列单个等待队列

14、单个等待队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统图 4-3-2 固定分区示意图4.2.2 固定分区分配 图 4-3-3 固定分区使用表通过设置内存分配表，内存分配简单缺点：内存利用率不高2.内存分配管理 4.2.3 动态分区分配 基本思想：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间 内存管理：设置内存空闲块表记录了空闲区起始地址和长度 内存分配：动态分配 内存回收：当某一块归还后，前后空间合并，修改内存空闲块表 4.2.3 动态分区分配(1) 分区分配表（见图

15、4-3-5）(2)空闲分区链图4-3-4空闲链结构1.分区分配中的数据结构0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分区分配表分区分配表：图4-3-5分区分配表分区分配表0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480

16、K5KJ585K13KJ685K98K4.2.3 动态分区分配1) 分配内存分配内存图4-3-6内存分配流程2. 分区分配操作 4.2.3 动态分区分配图 4-3-7 内存回收时的情况2) 回收内存 4.2.3 动态分区分配 为了实现动态分配，系统设立空闲分区链表：每个空闲块的前后两个单元，放置必要的说明信息和指针。系统只要设立一个链首指针，指向第一个空闲块即可。分配程序可以依照自由块链表，来查找适合的空闲块进行分配。（如下图）3.空闲分区链表 4.2.3 动态分区分配 按空闲块链接的方式不同，可以有以下四种算法： 最佳适应法 最坏适应法 首次适应法 循环首次适应法4.分配算法4.2.3 动态

17、分区分配 接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配 为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。 特点：用最小空间满足要求1)最佳适应算法4.2.3 动态分区分配OS8K空闲区24K空闲区B（16K）64K空闲区D（124K）24K64K8KFree有一作业J,大小为人12KB,现需调入内存最佳适应算法4.2.3 动态分区分配OS8K空闲区J(12K)B（16K）64K空闲区D（124K）12K8KFree有一作业J,大小为人12KB,现需调入内存64K最佳适应算法4.2.3 动态分区分配 接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行分配

18、，与最佳适应法相反，它在作业选择存储块时，总是寻找最大的空白区。 特点：当分割后空闲块仍为较大空块2)最坏适应算法4.2.3 动态分区分配OS8K空闲区24K空闲区B（16K）64K空闲区D（124K）24K64K8KFree有一作业J,大小为人12KB,现需调入内存最坏适应算法4.2.3 动态分区分配OS8K空闲区24K空闲区B（16K）D（124K）52K8KFree有一作业J,大小为人12KB,现需调入内存最坏适应算法12K24K 4.2.3 动态分区分配3)首次适应法： 为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。4)循环首次适应法

19、 类似首次适应法每次分区时，总是从上次查找结束的地方开始，找到一个足够大的空白区分配。4.2.3 动态分区分配OS8K空闲区24K空闲区B（16K）64K空闲区D（124K）24K64K8KFree有一作业J,大小为人12KB,现需调入内存 系统回收分区的主要步骤：1检查回收分区是否与空闲区邻接，如邻接则加以合并；2修改说明表 释放区邻接的分区情况可能是：释放区邻接的是另一释放区邻接的分区情况可能是：释放区邻接的是另一进程的已分配区，或者是空闲区。进程的已分配区，或者是空闲区。 下面以首次适应法说明了下面以首次适应法说明了系统回收该进程占用区系统回收该进程占用区存在存在的四种可能情况。设进程的

20、释放区为的四种可能情况。设进程的释放区为R R，与，与R R相邻的两相邻的两个空闲区分别为个空闲区分别为F1F1和和F2F2。R R的首地址送的首地址送LOC，R R的的尾地尾地址送址送LOC1，R的大小送的大小送SIZE。 4.2.3 动态分区分配回收内存:(a)若释放区若释放区R与与F1相邻接，即其低地址部分邻接相邻接，即其低地址部分邻接一空闲区。将一空闲区。将R与与F1合并，合并后的空闲区仍记为合并，合并后的空闲区仍记为F1。空闲区F1 进程P低地址高地址占用区2低地址高地址占用区2空闲区F1(a)合并后如何判断释放区如何判断释放区R 是否与某个空闲区相邻呢？只要是否与某个空闲区相邻呢？

21、只要从链首开始查找即可：从链首开始查找即可：若若F1的首地址的首地址+F1的大小的大小=R R的的首地址，说明首地址，说明R与与F1相邻接相邻接。只要修改。只要修改F1的大小的大小= F1的大小的大小+LOC，其它参数不变和在链中的位置不变。，其它参数不变和在链中的位置不变。(b)若释放区若释放区R与与F2相邻接，即其高地址部相邻接，即其高地址部分邻接一空闲区。将分邻接一空闲区。将R与与F2合并，合并合并，合并后的空闲区记仍记为后的空闲区记仍记为F2。若若LOC+SIZE=F2的首地址，说明的首地址，说明R与与F2相邻接。相邻接。需修改需修改F2的首地址的首地址=LOC，F2的大小的大小= F

22、2的大小的大小+SIZE。占用区1进程P 空闲区F2空闲区F2占用区1低地址高地址低地址高地址(b)合并后 (c) 若释放区若释放区R的高、低地址部分都邻接一个的高、低地址部分都邻接一个空闲区。应将三个分区合并为一个大空闲区，空闲区。应将三个分区合并为一个大空闲区，并记为并记为F1。 先将先将R与与F2合并，记为合并，记为F2。再将。再将F 2与与F1合并，并将合并，并将F2从链中删除。从链中删除。 若若F1的首地址的首地址+SIZE=LOC且且LOC+SIZE=F2的首地址，说明的首地址，说明R与与F1,F2同时相邻接。同时相邻接。需需F1的大小的大小= F1的大小的大小+SIZE+F2的大

23、小。的大小。空闲区空闲区F1 释放区释放区R空闲区空闲区F2空闲区空闲区F1合并后合并后(d)若释放区若释放区R上下都不邻接空闲区，将上下都不邻接空闲区，将其插入空闲区链的适当位置即可。记为其插入空闲区链的适当位置即可。记为空闲块空闲块F3 占用区占用区F1 释放区释放区R占用区占用区F2空闲区空闲区F3释放释放后后4.2.3 动态分区分配 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片 造成存储资源的浪费碎片问题的解决碎片问题的解决 紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域 （紧

24、缩技术，紧致技术，浮动技术，搬家技术） 问题：开销大；移动时机5.碎片问题优点： 便于动态申请内存 便于共享内存 便于动态链接缺点：碎片问题(外碎片)，内存利用率不高，受实际内存容量限制6.分区式存储管理的优缺点4.2.3 动态分区分配 4.2.4 可重定位分区分配1. 动态重定位的引入动态重定位的引入图 4-3-1 紧凑的示意图 4-3-2 动态重定位示意图2. 动态重定位的实现4.2.4 可重定位分区分配4.2.4 可重定位分区分配图 4-3-3 动态分区分配算法流程图3. 动态重定位分区分配算法 4.2.4 可重定位分区分配 优点:解决了可变分区分配所引入的“外零头”问题。消除内存碎片，

25、提高内存利用率。 缺点:提高硬件成本，紧凑时花费时间。4.可重定位分区的优缺点 4.2.4 可重定位分区分配 为了防止一首作业有意或无意地破坏操作系统或其它作业。一般说来，没有硬件支持，实现有效的存储保护是困难的。通常采取： 界限寄存器方式 保护键方式 两种措施，或二者兼而有之。5.分区的保护4.2.4 可重定位分区分配 一般由硬件提供一对寄存器： 基址寄存器：存放起始地址 限长寄存器：存放长度 （上界寄存器/下界寄存器）保护过程-防止地址越界4.2.4 可重定位分区分配 相对地址 限长寄存器的值 则产生访问地址界中断基址、限长寄存器保护4.2.5 4.2.5 交换交换 在多道环境下扩充内存的

26、方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾 交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现1.交换技术引入4.2.5 4.2.5 交换交换 当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中2. 交换技术1.选择原则:将哪个进程换出/内存？2.交换时机的确定3.交换时需要做哪些工作？4.换入回内存时位置的确定 4.2.5 4.2.5 交换交换3.交换技术实现中的几个问题 将哪个进程换出/内存？ 例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择

27、换出进程时，要确定换出的进程是要长时间等待的 需要特殊考虑的是：任何等待I/O进程中存在的问题 解决：从不换出处于等待I/O状态的进程 有些I/O进程因DMA而不能换出内存或换出前需要操作系统的特殊帮助4.2.5 4.2.5 交换交换4.选择原则 何时需发生交换？ 例子：只要不用就换出（很少再用）只在内存空间不够或有不够的危险时换出4.2.5 4.2.5 交换交换5. 交换时机的确定 需要一个对换分区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取. 对换分区的分配是采用连续分配方式,与动态分区内存分配与回收算法雷同.4.2.5 4.2.5 交换交换6. 交换时

28、需要做哪些工作 换出后再换入的内存位置一定要在换出前的原来位置上吗？ 受地址“绑定”技术的影响，即绝对地址产生时机的限制4.2.5 4.2.5 交换交换7.换入回内存时位置的确定第四章 存储器管理 4.3 4.3 基本分页存储管理基本分页存储管理 引言引言 页式存储管理的引入 在动态分区的存储空间中， 存在“零头”问题。尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高。 分页：把用户程序按逻辑页划分成大小相等的部分，称为页或虚页。从0开始编制页号，页内地址是相对于0编址。引言 内存块 块：内存按页的大小划分为大小相等的区域，称为内存块（物理页面，页框） 内

29、存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻，通过页表把作业的各个页面与物理块对应起来。 4.3.1 页面与页表页面与页表 1. 1.页面和物理块页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。4.3.1 页面与页表页面与页表分页地址中的地址结

30、构如下：页号P位移量W3112110对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：P=INTA/LW=AMODL其中，INT是整除函数，MOD是取余函数。例：系统页面大小为KB，设A2170B，则P=2,W=1222. 地址结构 4.3.1 页面与页表页面与页表 列出了作业的逻辑地址与其在主存中的物理地址间的对应关系。 页面大小:页面的大小应选择得适中，且页面大小应是2的幂，通常为512B8KB 一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。 页表的每一个表目除了包含指

31、向页框的指针外，还包括一个存取控制字段。 表目也称为页描述子。3.页表 4.3.1 页面与页表页面与页表分页管理中页与页框的对应关系示意图4.3.2 地址变换机构 1. 基本的地址变换机构基本的地址变换机构 图4-4-2分页系统的地址变换机构 4.3.2 地址变换机构 例如指令 LOAD 1,2500 的地址变换过程如下： 假设页面大小为1KB,页表起始地址为10002.地址变换过程页表长度页表长度 页表始址页表始址 3 1k2452虚拟地址页号页号 页面号页面号 0 2 1 3 2 88452OS物理地址 86441024*8+452=8644 4.3.2 地址变换机构 把虚拟地址2500转

32、换成页号P=2，位移量W=452； 如果页号2大于页表大小，则中断；否则继续； 页号2与页表起址1000运算（1000+2*20，设页描述子大小为20）得到页描述子地址为1040； 从页描述子中读取块号8； 根据页描述子的“存取控制”判断该指令是否被允许访问内存，如果不允许，则中断；否则继续； 块号8与位移量452运算（8*1024+452=8644，1024为页面大小）得到物理地址8644； 把数字1写进内存地址8644单元中。地址变换过程（续）4.3.2 地址变换机构 如果把页表放在主存中，无疑会影响系统的性能。这是因为每次访问主存，首先必须访问页表，读出页描述子，之后根据形成的实际地址再

33、访问主存，这样使访问主存的次数加倍，因而使总的处理速度明显下降。 为了解决这个问题人们采用一组硬件寄存器，存放当前访问过的页的页描述子， 每次访问主存时，首先查找快表，若找到所需的页描述子，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页描述子写入快表。如果设计得当，快表的命中率可以很高。 3.快表4.3.2 地址变换机构图 4-4-3 具有快表的地址变换机构具有快表的地址变换机构4.4.3 两级和多级页表 现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。页表就变得非常大，要占用相当大的内存空间。可采用两个方法来解决这一问题：采用离散分配方式来解决难以找到一块连

34、续的大内存空间的问题：只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。4.4.3 两级和多级页表 逻辑地址结构可描述如下：1. 两级页表图4-4-4两级页表结构外部页表外部页表REG外部页号外部页号外部页内地址外部页内地址页内地址页内地址虚拟地址虚拟地址页表地址页表地址.外部页表（每进程一个）外部页表（每进程一个）块号块号.页表页表代码或数据代码或数据.内存块内存块二级页表结构及地址映射二级页表结构及地址映射+4.4.3 两级和多级页表 32位 进程页表多大？设：页面大小为4KB 用户空间 2GB则：一个进程最大为: 219= 2GB/ 4KB页设：每个内存块号 4

35、字节则：进程页表 219 /(4KB/4B)=512页 结论：一个进程的页表的各页之间可以不连续存放 解决：页表本身使用地址索引页目录多级页表第四章 存储器管理 4.4 4.4 分分段存储管理段存储管理4.4.1 分段式存储管理的引入 在分页存储系统中，作业的地址空间是一维线性的，这破坏了程序内部天然的逻辑结构,造成共享、保护的困难。引入分段存储管理方式，主要是为了满足用户和程序员的下述需要：1)方便编程2)信息共享3)信息保护4)动态增长5)动态链接.0S工作区段工作区段B主程序段主程序段M.0EP子程序段子程序段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段

36、子程序段Y0116N数组数组A12345.4.4.2 分段系统的基本原理 1. 分段分段 分段地址中的地址具有如下结构：段号段内地址31161504.4.2 分段系统的基本原理 它记录了段号，段的首（地）址和长度之间的关系 每一个程序设置一个段表，放在内存,属于进程的现场信息段号段号012段首址段首址段长度段长度58K20K100K110K260K140K2.2.段表操作系统操作系统.B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度

37、 段地址段地址01234操作系统操作系统分段管理中作业分段管理中作业i i与段表、存储空间的关系与段表、存储空间的关系 4.4.2 分段系统的基本原理 系统设置一对寄存器 段表始址寄存器： 用于保存正在运行进程的段表的始址 段表长度寄存器： 用于保存正在运行进程的段表的长度（例如上图的段表长度为3）3. 硬件支持4.4.2 分段系统的基本原理 图 4-5-2 分段系统的地址变换过程4. 地址变换机构ClCb+段号段号S S 段内地址段内地址d比较比较比较比较b + d段段表表S= Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑地址lb.Slb地

38、址越界地址越界d=1d=1地址映射及存储保护机制地址越界地址越界地址越界地址越界比较比较4.4.2 分段系统的基本原理 (1)页是信息的物理单位，段则是信息的逻辑单位(2)页的大小固定且由系统决定，而段的长度却不固定(3)分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间则是二维的4. 分页和分段的主要区别 4.5.3 信息共享 图 4-5-3 分页系统中共享editor的示意图图4-5-4分段系统中共享editor的示意图 分段管理的优缺点 优点：便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？4.4.4 段页

39、式存储管理 1.1.产生背景：产生背景： 结合了段式与页式二者优点 克服了二者的缺点4.4.4 段页式存储管理用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配段号段号段内地址段内地址页号页号页内地址页内地址2.基本思想4.4.4 段页式存储管理1.段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）3.空块管理：同页式管理4.分配：同页式管理3. 管 理4.4.4 段页式存储管理 一个程序首先被划分成若干程序段，每一段给

40、予不同的分段标识符然后，对每一分段又分成若干个固定大小的页面。如下图(a)所示，系统中的一个作业的地址空间结构页面尺寸为字节，该作业有三个分段，第一段为15K字节，占4页，最后一页只有1K未用；其它段同理。未足一页大小的补为一页。4. 地址空间4.4.4 段页式存储管理 1.作业地址空间:如图（a）所示2.地址结构如图（b）所示作业的地址空间和地址结构4.4.4 段页式存储管理5.地址映射4.4.4 段页式存储管理6. 地址变换 4.4.4 段页式存储管理 从控制寄存器读取段表始址，找到段表； 段号段表始址 得到段描述子地址； 从段描述子读取页表始址，找到页表； 页号页表始址 得到页描述子地址

41、； 从页描述子读取物理块号； 物理块号页内位移量 得到物理地址。 上述的地址变换至少要访问主存三次，这将使执行程序的速度大大降低。为了解决上述问题，可以采取前边讲过的“快表”技术。地址变换（续）4.4.4 段页式存储管理7.段页式存储管理算法第四章 存储器管理 4.54.5 虚拟存储器虚拟存储器 4.5.1 虚拟存储器的引入问题的提出 :程序大于内存 程序暂时不执行或运行完是否还要占用内存 虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换 虚拟存储器支持多道程序设计技术 4.5

42、.1 虚拟存储器的引入1常规存储管理方式的特征是：一次性、驻留性。2局部性原理：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。 程序局部性原理 在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面 时间局部性： 一条指令被执行了，则在不久的将来它可能再被执行 空间局部性： 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用 4.5.1 虚拟存储器的引入2. 局部性原理4.5.1 虚拟存储器的引入 具有请求调入功能和自换功能,能从逻辑上对内存容量进行扩充的存储器系统。虚拟存储器就

43、是一个地址空间，且具有比实存大得多的容量。3. 虚拟存储器的定义 4.5.1 虚拟存储器的引入 对用户：指令地址部分所限定的比实存大得多的地址实间。 对系统：借助于各种表格机构，体现虚拟实间。 3 虚拟存储器（续） 4.5.1 虚拟存储器的引入 一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址长度为32位，则程序可以寻址范围是0(232)-1 ，即虚存容量为 4GB。 虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。4. 虚拟存储器的容量4.5.2 虚拟存储器的实现方法虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存

44、”，这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率1.虚拟存储技术4.5.2 虚拟存储器的实现方法2.虚拟存储技术实现方式1)分页请求系统在分页系统的基础上,增加了请求调页功能和页面置换功能.2)请求分段系统在分段系统的基础上,增加了请求调段及分段置换功能. 4.5.3. 虚拟存储器的特征1 离散性2 交换性3 多次性 以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术第四章 存储器管理 4.6 请求分页存储管理请求分页存储管理引言 请求式分页存储管理引入 请

45、求式分页也称虚拟页式存储管理 与纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面4.6.1 请求分页中的硬件支持 页号、驻留位、内存块号、外存地址、访问位、修改位、（存取控制、辅存地址） 中断位：表示该页是在内存还是在外存 访问位：表示该页最近被访问过，根据访问位来决定淘汰哪页 修改位：查看此页是否在内存中被修改过页号页号中断位中断位 内存块号内存块号外存地址外存地址访问位访问位 修改位修改位1. 页表机制 4.6.1

46、 请求分页中的硬件支持 查页表时，当存在位指示该页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。如下图所示。2.地址变换与缺页中断 4.6.1 请求分页中的硬件支持3.请求分页存储管理地址变换流程 4.6.2 内存分配策略和分配算法1.最小物理块数的确定最小物理块数：是指能保证进程正常运行所需的最小物理块数。取决于计算机的硬件结构2 物理块的分配策略1)固定分配局部置换2)可变分配全局置换3)可变分配局部置换 4.6.2 内存分配策略和分配算法3 物理块分配算法

47、1)平均分配算法2)按比例分配算法3)考虑优先权的分配算法 4.6.3 调页策略何时调入页面预掉页策略、请求调页策略从何调入页面页面调入过程4.7 .页面置换算法 当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。 最佳置换算法 先进先出置换算法 最近最久未用置换算法 近似的LRU算法（NRU算法） 4.74.7.1.最佳置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个物理块，

48、并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。利用最佳页面置换算法时的置换图4.7.2 先进先出(FIFO)页面置换算法利用FIFO置换算法时的置换图置换时选择在内存中驻留时间最长的页并淘汰之 4.7.3 最近最久未使用(LRU)置换算法 LRU页面置换算法 选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高（时间戳或硬件方法） LRU置换算法的硬件支持

49、1) 寄存器寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为:R=Rn-1Rn-2Rn-3R2R1R0某进程具有8个页面时的LRU访问情况2) 栈用栈保存当前使用页面时栈的变化情况 LRU置换算法的硬件支持 4.7.4 Clock置换算法 1) 简单的简单的Clock置换算法置换算法(近似的近似的LRULRU算法）算法） 简单Clock置换算法的流程和示例2) 改进型Clock置换算法 由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被

50、访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。4.7.4 Clock置换算法 其执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即