微处理器系统结构与嵌入式系统设计：存储器管理 材料2

《微处理器系统结构与嵌入式系统设计：存储器管理 材料2》由会员分享，可在线阅读，更多相关《微处理器系统结构与嵌入式系统设计：存储器管理 材料2（67页珍藏版）》请在金锄头文库上搜索。

1、存储器管理是指存储器管理是指存储器资源存储器资源（主要指内存（主要指内存)的管理。的管理。存储空间的分配与管理；存储空间的分配与管理；地址重定位地址重定位（逻辑地址与物理地址的对应关系）（逻辑地址与物理地址的对应关系）存储保护存储保护存储空间扩充：存储空间扩充：虚拟存储器技术以及各种调度算虚拟存储器技术以及各种调度算法。法。n n4.1 地址重定位地址重定位n n4.2 分区存储管理分区存储管理n n4.3 覆盖和交换覆盖和交换n n4.4 页面式存储管理页面式存储管理n n4.5 请求式页面存储管理请求式页面存储管理n n4.6 段式存储管理段式存储管理n n4.7 段页式存储管理段页式存储

2、管理4.1 地址重定位地址重定位主存储器分为两部分：主存储器分为两部分：系统区，用户区系统区，用户区存储管理主要存储管理主要管理用户区管理用户区的存储空间的存储空间地址空间和存储空间地址空间和存储空间名空间：名空间：程序中由符号名组成的空间。程序中由符号名组成的空间。逻辑地址（相对地址）：逻辑地址（相对地址）：用户的程序经过汇编或用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地编译后形成目标代码，目标代码通常采用相对地址的形式。相对于址的形式。相对于0 0编址。编址。逻辑地址空间（地址空间）：逻辑地址空间（地址空间）：相对地址的集合。相对地址的集合。物理地址（绝对地址）：物理地址

3、（绝对地址）：主存储器中一系列物理主存储器中一系列物理单元的编号。物理地址可直接寻址。单元的编号。物理地址可直接寻址。物理地址空间（存储空间）：物理地址空间（存储空间）：物理地址的集合。物理地址的集合。逻辑地址逻辑地址（相对地址，虚地址）：用户的程序经过（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。对地址的形式。其首地址为其首地址为0 0，其余指令中的地址都相对于首地址来编址。，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。不能用逻辑地址在内存中读取信息。物理地址物理地址（绝对地

4、址，实地址）：内存中存储单元（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。的地址。物理地址可直接寻址。地址映射地址映射：将用户程序中的逻辑地址转换为运行时：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。由机器直接寻址的物理地址。 逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射地址映射地址映射 1100Load A,1200 3456 。 。 。1200物理地址空间物理地址空间Load A,data1data1 3456源程序源程序Load A,200 34560100200编译连接编译连接逻辑地址

5、空间逻辑地址空间BA=1000地址重定位：地址重定位：实现程序的相对地址空间到绝实现程序的相对地址空间到绝对地址空间之间的映射。对地址空间之间的映射。程序在成为进程前的准备工作程序在成为进程前的准备工作编辑：编辑：编辑：编辑：形成源文件形成源文件( (符号地址符号地址) )编译：编译：编译：编译：形成目标模块形成目标模块( (模块内符号地址解析模块内符号地址解析) )链接：链接：链接：链接：由多个目标模块或程序库生成可执行文件由多个目标模块或程序库生成可执行文件( (模块间符号地址解析模块间符号地址解析) )装入：装入：装入：装入：构造构造PCBPCB，形成进程形成进程( (使用物理地址使用物

6、理地址) )重定位方法：重定位方法：静态重定位静态重定位静态重定位静态重定位动态重定位动态重定位动态重定位动态重定位地址重定位地址重定位优点：优点：容易实现，无需硬件支持。容易实现，无需硬件支持。缺点：缺点： 程序在主存中只能连续分配；程序在主存中只能连续分配； 程序装入内存后不能移动；程序装入内存后不能移动； 对共享的同一程序，各用户必须使用自己对共享的同一程序，各用户必须使用自己的副本，浪费存储空间。的副本，浪费存储空间。在程序执行之前进行地址重定位，即可执行文在程序执行之前进行地址重定位，即可执行文件中装入主存时，由操作系统中的加载程序来件中装入主存时，由操作系统中的加载程序来完成地址映

7、射。完成地址映射。重定位重定位重定位重定位项：项：项：项：程序中涉及直接寻址的每条指令都要程序中涉及直接寻址的每条指令都要进行修改，需要修改的位置称为进行修改，需要修改的位置称为重定位项重定位项。重定位重定位重定位重定位项表：项表：项表：项表：用相对地址给出需修改的位置。列用相对地址给出需修改的位置。列出各个需要重定位的地址单元和相对地址值。出各个需要重定位的地址单元和相对地址值。 静态重定位静态重定位地址映射地址映射 1100Load A,1200 3456 。 。 。1200物理地址空间物理地址空间Load A,data1data1 3456源程序源程序Load A,200 3456010

8、0200编译连接编译连接逻辑地址空间逻辑地址空间BA=1000静态重定位静态重定位可执行文件在内存中的重定位可执行文件在内存中的重定位说明：重定位表中说明：重定位表中列出列出所有修改的位置。如：重定位表的所有修改的位置。如：重定位表的150150表示相对地址表示相对地址150150处的内容为相对地址处的内容为相对地址( (即即100100为从为从0 0起头的相起头的相对位置对位置) )。在装入时，要依据重定位后的起始位置。在装入时，要依据重定位后的起始位置(2000)(2000)修改修改相对地址。相对地址。重定位修改：重定位表中的重定位修改：重定位表中的150-150-绝对地址绝对地址2150

9、(=2000+150)2150(=2000+150)内容修改：内容内容修改：内容100100变成变成2100(=100+2000)2100(=100+2000)。jmp150100150.RelocationTable0jmp15021002150.2000优点：优点：OSOS可以将一个程序分散存放于不连续的内存空间；可以将一个程序分散存放于不连续的内存空间；可以移动程序。可以移动程序。有利用实现共享。有利用实现共享。缺点：缺点：需要硬件支持（通常是需要硬件支持（通常是CPUCPU），是虚拟），是虚拟存储的基础。存储的基础。在程序运行期间进行重定位，装入和执行时通过硬件在程序运行期间进行重定位

10、，装入和执行时通过硬件地址变换机构，完成虚拟地址到实际内存地址的变换地址变换机构，完成虚拟地址到实际内存地址的变换 动态重定位动态重定位动态重定位动态重定位0100200300.LOAD A,2003456逻辑地址空间110012001300物理地址空间200VR+1000BR（基址寄存器）（基址寄存器）LOAD A,2003456缺点缺点：不能充分使用存储空间。：不能充分使用存储空间。4.2分区存储管理分区存储管理基本思想：基本思想：将主存储空间划分成若干个连续将主存储空间划分成若干个连续的存储区，称为的存储区，称为分区分区。每个分区只能存储一。每个分区只能存储一道程序，一个程序只能访问其所

11、在分区的存道程序，一个程序只能访问其所在分区的存储单元。储单元。内存分为两个连续区域：系统区，用户内存分为两个连续区域：系统区，用户区。应用程序装入到用户区，可使用用区。应用程序装入到用户区，可使用用户区全部空间。户区全部空间。最简单，适用于单道程序设计的最简单，适用于单道程序设计的OSOS。优点优点：易于管理。：易于管理。缺点缺点：对要求内存空间少的程序，造成：对要求内存空间少的程序，造成内存浪费（空闲存储区）。内存浪费（空闲存储区）。4.2分区存储管理分区存储管理单一连续区存储管理单一连续区存储管理适用于单道程序系统适用于单道程序系统单一连续区存储管理单一连续区存储管理0H7FFFHFFF

12、FFH操作系统操作系统用户程序区用户程序区08000H界限寄存器界限寄存器中断矢量表中断矢量表空闲区空闲区基本思想：基本思想：把内存分为一些大小相等或不等连续把内存分为一些大小相等或不等连续区域区域分区分区(partition)，每个分区只能每个分区只能驻留一个程序驻留一个程序。操作系统占用其中一个分区。操作系统占用其中一个分区。特点：特点：适用于多道程序系统和分时系统适用于多道程序系统和分时系统支持多个程序并发执行支持多个程序并发执行问题：问题：存在存在碎片（小得难以使用的分区）问题，碎片（小得难以使用的分区）问题，可能存在可能存在内部碎片内部碎片和和外部碎片外部碎片。内部碎片：内部碎片：占

13、用分区之内未被利用的空间占用分区之内未被利用的空间外部碎片外部碎片：占用分区之间难以利用的空闲分区（通常：占用分区之间难以利用的空闲分区（通常是小空闲分区）。是小空闲分区）。分区存储管理分区存储管理分区大小相等分区大小相等：只适合于多个相同程序的：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。并发执行（处理多个类型相同的对象）。分区大小不等：分区大小不等：多个小分区、适量的中等多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。分配当前空闲的、适当大小的分区。把内存划分为若干个固定大小的连续分区把内存划分为若

14、干个固定大小的连续分区。一旦划分好，在系统运行期间不再重新划分。一旦划分好，在系统运行期间不再重新划分。 固定分区固定分区(fixed partitioning)固定分区固定分区(大小相同大小相同)固定分区固定分区(多种大小多种大小)优点：优点：简单易于实现，开销小。简单易于实现，开销小。缺点：缺点：内部碎片造成浪费内部碎片造成浪费分区总数固定，限制了并发执行的程序数目。分区总数固定，限制了并发执行的程序数目。采用的数据结构：采用的数据结构：分区表分区表(分区说明表分区说明表)记记录分区的大小和使用情况录分区的大小和使用情况Operating System空闲分区空闲分区 分区分区5作业作业C

15、 分区分区4分区分区3分区分区2分区分区1空闲分区空闲分区 作业作业B 作业作业A 00000H08000H0A000H12000H1A000H3A000H区号区号起始地址起始地址大小大小使用使用标志标志作业作业大小大小108000H8KY6K20A000H32KY24K312000H32KN41A000H128KY118K53A000H512KN内存分区说明表内存分区说明表动态分区动态分区：在装入作业和处理过程中，按其：在装入作业和处理过程中，按其要求的内存容量以及当时的内存资源使用情要求的内存容量以及当时的内存资源使用情况，将一块大小与所要求相近的存储区分配况，将一块大小与所要求相近的存储

16、区分配给作业。给作业。优点：优点：没有内部碎片。没有内部碎片。缺点：缺点：有外部碎片。有外部碎片。 动态分区动态分区(dynamic partitioning)Operating System128 K896 KOperating SystemProcess 1320 K576 KOperating SystemProcess 1320 KProcess 2224 K352 KOperating SystemProcess 1320 KProcess 2Process 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3224 K288

17、K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProcess 4128 K96 K分区的数据结构分区的数据结构：分区表，或分区链表：分区表，或分区链表可以只记录可以只记录空闲分区空闲分区，也可以同时记录空闲和占，也可以同时记录空闲和占用分区用分区单一分区表中，单一分区表中，表项数目表项数目随着内存的分配和释放随着内存的分配和释放而动态改变，表长难以确定，分配回收分区时降而动态改变，表长难以确定，分配回收分区时降低查找速度。低查找速度。分区表可以划分为两个表：分区表可以划分为两个表：空闲分区表空闲分区表，使用分使用分区表区表。从而减小每

18、个表长度。空闲分区表（一般。从而减小每个表长度。空闲分区表（一般常用链表结构）中按不同分配算法相应对常用链表结构）中按不同分配算法相应对表项排表项排序序。分区分配和释放算法分区分配和释放算法动态分区管理：动态分区管理：分区分配算法：分区分配算法：寻找寻找某个空闲分区，其大小某个空闲分区，其大小需大于或等于程序的要求。需大于或等于程序的要求。分区释放算法：分区释放算法：需要将相邻的空闲分区需要将相邻的空闲分区合并合并成一个空闲分区。成一个空闲分区。(这时要解决的问题是：这时要解决的问题是：合并条件合并条件的判断和的判断和合并时机合并时机的选择的选择)分区分配算法和释放算法：分区分配算法和释放算法

19、：最先匹配法最先匹配法(first-fit)：按分区的先后次序，从头按分区的先后次序，从头查找，找到符合要求的第一个分区查找，找到符合要求的第一个分区该算法的分配和释放的时间性能较好，较大的空闲分区可该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。查找时间开销会增大。最佳匹配法最佳匹配法(best-fit)：找到其大小与要求相差最小找到其大小与要求相差最小的空闲分区的空闲分区从个别来看，外部碎片较小，但从整体来看，会形成较多从个别来看

20、，外部碎片较小，但从整体来看，会形成较多外部碎片。较大的空闲分区可以被保留。外部碎片。较大的空闲分区可以被保留。最差匹配法最差匹配法(worst-fit)：找到最大的空闲分区找到最大的空闲分区基本不留下小空闲分区，但较大的空闲分区不被保留。基本不留下小空闲分区，但较大的空闲分区不被保留。分区分配算法分区分配算法基本思想：基本思想：分配算法与可变分区分配基本算分配算法与可变分区分配基本算法基本相同，并对作业进程分区进行搬迁，法基本相同，并对作业进程分区进行搬迁，以形成大的连续的空闲分区。以形成大的连续的空闲分区。特点：特点：解决外部碎片问题的简单有效的方法解决外部碎片问题的简单有效的方法对占用分

21、区进行内存数据搬移占用对占用分区进行内存数据搬移占用CPU时间时间如果对占用分区中的程序进行如果对占用分区中的程序进行“浮动浮动”，则其，则其重定位需要硬件支持（提供基址界限寄存器重定位需要硬件支持（提供基址界限寄存器对）。对）。实现空闲分区拼接的时机：实现空闲分区拼接的时机：每个分区释放后，每个分区释放后，或内存分配找不到满足条件的空闲分区时或内存分配找不到满足条件的空闲分区时动态重定位式分区分配动态重定位式分区分配基本思想：基本思想：一个作业由一些相对独立的程序段和一个作业由一些相对独立的程序段和数据段组成，每个段占用一个连续分区，而相应数据段组成，每个段占用一个连续分区，而相应的各分区之

22、间不要求是连续的。的各分区之间不要求是连续的。特点：特点：有效地解决外部碎片问题有效地解决外部碎片问题要求：要求：相应的语言编译器能在作业的每个段内生成有效地址相应的语言编译器能在作业的每个段内生成有效地址（各段相对于（各段相对于0编址）编址）系统内设置多对基址界限寄存器系统内设置多对基址界限寄存器。优点：优点：可以实现分区共享可以实现分区共享诸进程可以共享数据分区。诸进程可以共享数据分区。多重分区存储管理多重分区存储管理不拼接而解决碎片问题不拼接而解决碎片问题引入：引入：其目标是在较小的可用内存中运行较大其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管的程序。常用于

23、多道程序系统，与分区存储管理配合使用。理配合使用。基本思想基本思想: :一个作业的若干程序段，或几个作一个作业的若干程序段，或几个作业的某些部分共享同一存储区。业的某些部分共享同一存储区。优点优点：解决小主存容量与大作业之间的矛盾。：解决小主存容量与大作业之间的矛盾。缺点缺点：实现覆盖管理的系统开销较大。：实现覆盖管理的系统开销较大。4.3 覆盖和交换覆盖和交换覆盖覆盖(overlay)注：注：另一种覆盖方法：另一种覆盖方法：(100K)A(20K)占一个分区：占一个分区：20K；B(50K)、D(20K)和和E(40K)共用一个分区：共用一个分区：50K；F(30K)和和C(30K)共用一个

24、分区：共用一个分区：30K；覆盖技术不存在调用关系的模块不必同时装入到内存，从而可以相互覆不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。盖。(即即不同时用的模块可共用一个分区不同时用的模块可共用一个分区)缺点：缺点：编程时必须划分程序模块和确定程序模块之编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空从外存装入覆盖文件，以时间延长来换取空间节省。间节省。引入：解决主存容量不足的矛盾。引入：解决主存容量不足的矛盾。多个程序并发执多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而行，可以将暂

25、时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作系统中，与分区存储管理配合使用。又称作“对换对换”或或“滚进滚进/ /滚出滚出(roll-in/roll-out)”(roll-in/roll-out)”。基本思想基本思想: :暂停执行内存中的进程，将整个进程的地暂停执行内存中的进程，将整个进程的地址空间保存到外存

26、的交换区中（换出址空间保存到外存的交换区中（换出swap outswap out），），而将外存中由阻塞变为就绪的进程的地址空间读入而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入到内存中，并将该进程送到就绪队列（换入swap swap inin）。）。交换交换(swapping)优点优点：增加并发运行的程序数目，并且给用户提供：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构。适当的响应时间；编写程序时不影响程序结构。缺点缺点： 对换入和换出的控制增加处理机开销；程序整个地对换入和换出的控制增加处理机开销；程序整个地址空间都进行

27、传送，没有考虑执行过程中地址访问址空间都进行传送，没有考虑执行过程中地址访问的统计特性。的统计特性。考虑的问题：考虑的问题：程序换入时的重定位；程序换入时的重定位；减少交换中传送的信息量，特别是对大程序；减少交换中传送的信息量，特别是对大程序；对外存交换区空间的管理：如动态分区方法；对外存交换区空间的管理：如动态分区方法；覆盖与交换的区别覆盖与交换的区别：l 覆盖由用户解决空间不足覆盖由用户解决空间不足l 交换由系统解决空间不足交换由系统解决空间不足引入：引入：避开作业的连续性要求，将一个作业存放在避开作业的连续性要求，将一个作业存放在 不连续的存储空间中，以很好地不连续的存储空间中，以很好地

28、解决碎片解决碎片问题。问题。基本思想基本思想:系统把内存物理空间等分为若干大小相等、系统把内存物理空间等分为若干大小相等、位置固定的位置固定的块（或帧）块（或帧）。将程序的逻辑地址空间划分。将程序的逻辑地址空间划分为与块大小相同的为与块大小相同的页或页面页或页面(page or page frame)，程序加载时，分配其所需的所有块，这些块不必连续。程序加载时，分配其所需的所有块，这些块不必连续。需要需要CPU的硬件支持。的硬件支持。4.4 页面式存储管理页面式存储管理地址空间分成大小相同的部分地址空间分成大小相同的部分 页页存贮空间分成大小相同的部分存贮空间分成大小相同的部分 块块( (页帧

29、页帧) )页大小块大小页大小块大小 页表页表(PMT) ：又称页面映象表，记录一个作业程序的页记录一个作业程序的页号所对应的内存块号。号所对应的内存块号。 需要需要CPU的硬件支持。的硬件支持。页号块号块号012238分分配配时时页页对对应应块块，但但不不要求连续要求连续页表包括：页号，块号页帧页帧1919Operating System作业作业2 2（页（页0 0） 00000H00000H0B000H0B000H0A800H0A800H0B800H0B800H0C000H0C000H0E000H0E000H作业作业1 1（页（页0 0） 作业作业2 2（页（页2 2） 作业作业1 1（页（

30、页1 1） 作业作业2 2（页（页1 1） 作业作业3 3（页（页0 0） 物理地址空间物理地址空间页帧页帧0 0页帧页帧2020页帧页帧2121页帧页帧2222页帧页帧2323页帧页帧2424页帧页帧2525页帧页帧2626页帧页帧2727页帧页帧28280C800H0C800H0D000H0D000H0D800H0D800H0 01 1逻辑地址空间逻辑地址空间作业作业1(4K)1(4K)0 01 1作业作业2(5K)2(5K)2 20 0作业作业3(1.8K)3(1.8K)0 01 1页表页表0 01 12 20 0页帧号页帧号222220202525212124242727页面式存储管理

31、硬件页面式存储管理硬件地址变换：地址变换：指令所给出地址分为两部分：逻指令所给出地址分为两部分：逻辑页号，页内偏移地址辑页号，页内偏移地址查进程页表，得物查进程页表，得物理页号理页号物理地址物理地址页面大小：页面大小：通常是几通常是几KB到几十到几十KB（取（取2的幂）。的幂）。 小小内部碎片小；大内部碎片小；大页表短，管理开销小，页表短，管理开销小，交换时对外存交换时对外存I/O效率高。效率高。页式地址变换分页存储管理算法分页存储管理算法 作业表：作业表：记录每个作业的状态和资源使用情况，包记录每个作业的状态和资源使用情况，包括页表起始地址、页表长度。括页表起始地址、页表长度。 空闲块表：空

32、闲块表：页记录内存空闲块的帧号。以链表形式组页记录内存空闲块的帧号。以链表形式组织内存空闲块。织内存空闲块。建立进程时，作业调度程序调用存储管理程序为作建立进程时，作业调度程序调用存储管理程序为作业进程分配存储空间。按作业请求的内存容量业进程分配存储空间。按作业请求的内存容量size计计算要分配的块数算要分配的块数N=size/size_page(上取整上取整)一个作业终止时，系统调用存储管理程序，回收该一个作业终止时，系统调用存储管理程序，回收该作业释放的物理页，修改空闲存储块链表。作业释放的物理页，修改空闲存储块链表。引入：引入：向用户提供大容量存储器，把内存和外存统向用户提供大容量存储器

33、，把内存和外存统一考虑，外存作为存储信息的主要媒介，内存作为处一考虑，外存作为存储信息的主要媒介，内存作为处理机需要访问的数据缓冲区。理机需要访问的数据缓冲区。基本思想基本思想:运行一个作业程序时，并不要求把该作业运行一个作业程序时，并不要求把该作业的全部程序和数据都装入内存，可只把目前要执行的的全部程序和数据都装入内存，可只把目前要执行的几页调入内存的空闲存储块，其余部分仍保存在外存，几页调入内存的空闲存储块，其余部分仍保存在外存，以后根据作业程序运行情况需要时再调入内存。以后根据作业程序运行情况需要时再调入内存。4.5 请求式页面存储管理请求式页面存储管理需解决的问题：需解决的问题：提供一

34、种机制，检测访问的页是否在内存，若不在，为之提供一种机制，检测访问的页是否在内存，若不在，为之分配一物理页，修改页表项，并将逻辑页调入到物理页。分配一物理页，修改页表项，并将逻辑页调入到物理页。选择淘汰算法。选择淘汰算法。分页故障处理分页故障处理 活动页：活动页：某一时刻驻留在内存的页，称为进程的活某一时刻驻留在内存的页，称为进程的活动页。动页。 非活动页：非活动页：某一时刻驻留在外存的页。某一时刻驻留在外存的页。作业的页表项包括该页是否在内存的信息。作业的页表项包括该页是否在内存的信息。 存在位存在位p=1:该逻辑页在内存该逻辑页在内存 p=0:该逻辑页在外存，对该逻辑页的任何访该逻辑页在外

35、存，对该逻辑页的任何访问都将产生问都将产生“缺页故障缺页故障”中断。中断。作业进程欲访问一条不在内存物理页中的指令或操作业进程欲访问一条不在内存物理页中的指令或操作数时，由地址变换机构硬件产生作数时，由地址变换机构硬件产生“缺页故障缺页故障”中中断，断，并由缺页故障中断处理程序实现物理页的调入、并由缺页故障中断处理程序实现物理页的调入、调出操作。调出操作。淘汰算法淘汰算法当外存上某页信息需调入内存而内存中当外存上某页信息需调入内存而内存中又无空闲存储块时，则需按某种淘汰算又无空闲存储块时，则需按某种淘汰算法从内存中选择一页将其内容淘汰。法从内存中选择一页将其内容淘汰。淘汰算法不合理将产生淘汰算

36、法不合理将产生抖动现象抖动现象刚刚被调出的页马上又被要求调入。被调出的页马上又被要求调入。最佳淘汰算法：最佳淘汰算法：从内存中淘汰永远不再使用从内存中淘汰永远不再使用的页；如这样的页不存在，则选择最长时间的页；如这样的页不存在，则选择最长时间不再被访问的页为淘汰页。不再被访问的页为淘汰页。老页：老页：某时刻前，进程访问过的所有页某时刻前，进程访问过的所有页新页：新页：某时刻，进程正在对某页进行第一次访问。某时刻，进程正在对某页进行第一次访问。自然页流：自然页流：老页中以后还要访问的页和新页构成老页中以后还要访问的页和新页构成进程的使用页集，使用页集的变动为进程的进程的使用页集，使用页集的变动为

37、进程的自然自然页流页流。特点：仅有理论意义，实际不可实现特点：仅有理论意义，实际不可实现明确知道各将来时刻对各页的访问情况，很难。明确知道各将来时刻对各页的访问情况，很难。内存容量有限，使得某些页过早淘汰。内存容量有限，使得某些页过早淘汰。先进先出先进先出FIFO算法：算法：采用先调入内存的页面采用先调入内存的页面先被淘汰的策略；即总选择驻留内存时间最先被淘汰的策略；即总选择驻留内存时间最长的一页淘汰。长的一页淘汰。原因：原因：最早调入的页面不再使用的可能性要比最最早调入的页面不再使用的可能性要比最近调入的要大。近调入的要大。以调入内存的时间先后顺序组织一个进程现行使以调入内存的时间先后顺序组

38、织一个进程现行使用的内存储块为用的内存储块为FIFO队列队列优点：优点：仅在程序按线性顺序访问地址空间时才是理仅在程序按线性顺序访问地址空间时才是理想的。想的。缺点：缺点：未考虑程序运行时的动态特性。未考虑程序运行时的动态特性。可能导致程序中常被访问的页，因其在内存中驻留时间最可能导致程序中常被访问的页，因其在内存中驻留时间最长而被淘汰。长而被淘汰。最近最少使用最近最少使用LRU(Least Recently Used) 算法：算法：选择最近很长时间未被访问的一页淘汰。选择最近很长时间未被访问的一页淘汰。原因：原因：若一页刚被访问过，很可能最近还要被访若一页刚被访问过，很可能最近还要被访问；若

39、一页最近很长时间未被引用，则最近访问问；若一页最近很长时间未被引用，则最近访问的可能性极小。的可能性极小。按照各页最近一次的访问时间进行排序按照各页最近一次的访问时间进行排序缺点：缺点：每访问一次要进行一次排序，系统开销大，每访问一次要进行一次排序，系统开销大，难以实现。难以实现。近似近似LRU算法（第二次机会淘汰算法）算法（第二次机会淘汰算法）举例：举例：设某作业占有设某作业占有7个页面，如果在主存中只允许装入个页面，如果在主存中只允许装入4个工作页面个工作页面(即工作集为即工作集为4)，作业运行时，实际访，作业运行时，实际访问页面的顺序是问页面的顺序是1， 2， 3， 6， 4， 7， 3

40、， 2， 1， 4， 7， 5， 6， 5， 2， 1。用。用FIFO与与LRU页面调度页面调度算法，列出各自的页面淘汰顺序和缺页中断次数。算法，列出各自的页面淘汰顺序和缺页中断次数。(假设开始的假设开始的4个页面已装入主存个页面已装入主存) FIFO： 页面淘汰顺序页面淘汰顺序：1 2 3 6 4 7 缺页中断次数：缺页中断次数：6次次 LRU： 页面淘汰顺序页面淘汰顺序： 1 2 6 4 7 3 2 1 4 7 缺页中断次数：缺页中断次数： 10次次 注：假定前面四页注：假定前面四页1 2 3 6 已在主存已在主存最少使用最少使用LFU(Least Frequently Used) 算法：

41、算法：淘汰在现在时刻之前某一段时间内访问频率淘汰在现在时刻之前某一段时间内访问频率最低的页。最低的页。原因：原因：过去一段时间最经常访问的页，将来访问过去一段时间最经常访问的页，将来访问的可能性最大。的可能性最大。特点：特点：需要为每个内存页面设置一个需要为每个内存页面设置一个“访问次数计数器访问次数计数器” ，每，每当页面被访问时，该页面的访问计数器加当页面被访问时，该页面的访问计数器加1；应禁止淘汰最近一个时间间隔内调入内存的新页；应禁止淘汰最近一个时间间隔内调入内存的新页；发生缺页中断时，淘汰计数值最小的页面，并将所有计发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零。数清零。请求

42、调页请求调页(demand paging)：只调入发生只调入发生缺页时缺页时所所需的页面。需的页面。优点：容易优点：容易实现实现。缺点：对外存缺点：对外存I/O次数次数多，多，开销开销较大较大预调页预调页(prepaging)：在发生缺页需要调入某页在发生缺页需要调入某页时，时，一次调入该页以及相邻的几个页一次调入该页以及相邻的几个页。优点：提高调页的优点：提高调页的I/O效率效率。缺点：基于预测，若调入的页在以后很少被访问，则缺点：基于预测，若调入的页在以后很少被访问，则效率效率低。常用于低。常用于程序装入时程序装入时的调页。的调页。调入策略确定在外存中的页面调入策略确定在外存中的页面调入时

43、机调入时机。在虚拟页式。在虚拟页式管理中有两种常用策略。管理中有两种常用策略。分页虚拟存储管理调入策略分页虚拟存储管理调入策略 (fetch policy)存储保护的目的：存储保护的目的：保护保护系统程序区系统程序区不被用户侵犯（有意或无意的）不被用户侵犯（有意或无意的）不允许用户程序读写不允许用户程序读写不属于自己地址空间的数据不属于自己地址空间的数据（系统（系统区地址空间，其他用户程序的地址空间）区地址空间，其他用户程序的地址空间）1. 存储保护存储保护由于存储保护由于存储保护检查检查是针对每个是针对每个存储访问操作存储访问操作进行的，进行的，必须由相应的处理器必须由相应的处理器硬件机构支

44、持硬件机构支持。页面的共享与保护页面的共享与保护存储保护类型存储保护类型界限保护界限保护（上界寄存器（上界寄存器/下界寄存器或基址寄存器下界寄存器或基址寄存器/限长寄存限长寄存器）：所有访问地址必须在上下界之间；每个进程都有自己器）：所有访问地址必须在上下界之间；每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址空间之外，则发生地址越界地址越界。访问方式保护访问方式保护（保护键）：通过保护键匹配来判断（保护键）：通过保护键匹配来判断存储访问存储访问方式方式是否合法。对于允许多个进程共享的存储区域，每个

45、进是否合法。对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生反了权限规定，则发生操作越权操作越权(即读写保护即读写保护)。对每个内存。对每个内存区域指定一个键值和若干禁止的访问方式，进程中也指定键区域指定一个键值和若干禁止的访问方式，进程中也指定键值，如果访问时键值不匹配而且是被禁止的访问方式，则出值，如果访问时键值不匹配而且是被禁止的访问方式，则出错；错；环保护环保护：处理器状态分为多个环：处理器状态分为多个环(ring)，分别具有不同的分别具有不同的存存储访问特权级别储访问特权

46、级别(privilege)，通常是级别高的在内环，编号通常是级别高的在内环，编号小（如小（如0环）级别最高；可访问同环或更低级别环的环）级别最高；可访问同环或更低级别环的数据数据；可；可调用同环或更高级别环的调用同环或更高级别环的服务服务。共享页面共享页面：在物理页面表中有引用计数。：在物理页面表中有引用计数。只能共享只能共享不被修改的页面不被修改的页面。这。这对用户应用是透明对用户应用是透明的，完全由的，完全由操作系统控制，目的在于操作系统控制，目的在于减少系统内的物理页面总减少系统内的物理页面总数数。当共享页从内存中淘汰或重新装入内存时，共享该页的所当共享页从内存中淘汰或重新装入内存时，共

47、享该页的所有作业进程的页表中的相应页表项必须被同时更新。有作业进程的页表中的相应页表项必须被同时更新。写时复制写时复制(copy on write)：如果一个进程要改写共享页面，如果一个进程要改写共享页面，则先把该页面复制一份，让该进程访问复制后的页面，而则先把该页面复制一份，让该进程访问复制后的页面，而让其他进程访问复制前的页面。让其他进程访问复制前的页面。通过通过引用计数引用计数(reference count)来描述存储区的共享，来描述存储区的共享，引用计数表示引用计数表示共享它的进程的数目共享它的进程的数目：2.存储共享存储共享页式管理是把内存视为一维线性空间；而段式页式管理是把内存视

48、为一维线性空间；而段式管理是把内存视为管理是把内存视为二维空间二维空间，与进程逻辑相一与进程逻辑相一致致。 段式存储管理基本思想：段式存储管理基本思想：将程序的地址空间划分为将程序的地址空间划分为若干个段若干个段(segment)，程序加载时，分配其所需的所有段（内存分程序加载时，分配其所需的所有段（内存分区），这些段区），这些段不必连续不必连续；物理内存的管理采用；物理内存的管理采用动态分区动态分区。需要需要CPU的硬件支持的硬件支持。4.6 段式存储管理段式存储管理地址结构如下：地址结构如下：段号S段内位移量d通过通过段表实现逻辑地址到物理地址的映射段表实现逻辑地址到物理地址的映射段表结构

49、：段表结构：该段在内存中的首地址；段长；访问权限，该段在内存中的首地址；段长；访问权限，段存在位（该段是否在内存）段存在位（该段是否在内存）段表中各表项按段号从小到大顺序排列段表中各表项按段号从小到大顺序排列B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1 的地址空间的地址空间10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度 段地址段地址01234操作系统操作系统地址转换地址转换段式地址变换的步骤段式地址变换的步骤：(1) (1) 分段寻址硬件把分段寻址硬件把cpucpu产生的程序逻辑产生的程序逻辑

50、地址划分为段号地址划分为段号s s和段内地址和段内地址d d，( (s s，d)d)(2) (2) 用用S S检索段表检索段表，得到段基地址，得到段基地址B(3) (3) 如如d0d0或或d d 段表长度段表长度L L则则产生产生越界越界异异常中断常中断(4) (4) ( (B+d)B+d)即为所需内存地址即为所需内存地址程序通过分段程序通过分段(segmentation)划分为多个模块，如划分为多个模块，如代码段、数据段、共享段。代码段、数据段、共享段。可以分别可以分别编写和编译编写和编译可以针对不同类型的段采取不同的可以针对不同类型的段采取不同的保护保护可以按段为单位来进行可以按段为单位来

51、进行共享共享，包括通过动态链接进行代码，包括通过动态链接进行代码共享共享优点：优点：没有内部碎片，外部碎片可以通过内存拼接来消除。没有内部碎片，外部碎片可以通过内存拼接来消除。便于改变进程占用空间的大小。便于改变进程占用空间的大小。便于模块化，便于处理共享问题。便于模块化，便于处理共享问题。缺点：缺点：进程全部装入内存。进程全部装入内存。段的最大长度受限于主存空间，开销大。段的最大长度受限于主存空间，开销大。页式管理和段式管理的比较页式管理和段式管理的比较分页是出于分页是出于系统管理系统管理的需要，分段是出于的需要，分段是出于用户应用用户应用的需要。的需要。一条指令或一个操作数可能会跨越两个页

52、的分界处，而一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。不会跨越两个段的分界处。页大小页大小是系统固定的，而是系统固定的，而段大小段大小则通常不固定。则通常不固定。逻辑地址表示：逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地分页是一维的，各个模块在链接时必须组织成同一个地址空间；址空间；分段是二维的，各个模块在链接时可以每个段组织成一分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。个地址空间。通常段比页大，因而段表比页表短，可以缩短查找通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。时间，提高访问速度。 段的共享与保护段的

53、共享与保护共享段共享段：被连接或被释放一次则对引用计数加：被连接或被释放一次则对引用计数加1或或减减1，计数减至，计数减至0则可将该共享段删除；目的在于进则可将该共享段删除；目的在于进程间的程间的信息交流信息交流。段的保护：段的保护：段表限制段表限制；访问权限控制；访问权限控制；特权级。特权级。 一个作业进程的所有分段的副本都保存在外存上；一个作业进程的所有分段的副本都保存在外存上；分段虚拟存储管理分段虚拟存储管理 当作业进程开始运行，系统仅把需要的一段或数段当作业进程开始运行，系统仅把需要的一段或数段调入内存调入内存 其它段在引用时才装入其它段在引用时才装入 当进程运行时引用不在内存中的分段

54、时，产生缺段当进程运行时引用不在内存中的分段时，产生缺段故障中断故障中断 按动态重定位分区分配内存，不够时拼接；超过总按动态重定位分区分配内存，不够时拼接；超过总的空闲分区容量，则淘汰相应段的空闲分区容量，则淘汰相应段优点：优点： 程序中各段可以分别独立编写。程序中各段可以分别独立编写。 便于动态装入和链接。便于动态装入和链接。 便于实现分段存储保护。便于实现分段存储保护。 易实现分段信息共享。易实现分段信息共享。缺点：缺点： 段的最大长度受限于主存空间；段的最大长度受限于主存空间； 段作为整体调入、调出内存的段作为整体调入、调出内存的开销大，降低了系开销大，降低了系统工作效率。统工作效率。

55、采用动态分区，存在外部碎片，采用动态分区，存在外部碎片，内存浪费。内存浪费。是虚拟页式和虚拟段式存储管理的结合。是虚拟页式和虚拟段式存储管理的结合。4.7 段页式存储管理段页式存储管理 为了获得分段在逻辑上的优点和分页在管理存为了获得分段在逻辑上的优点和分页在管理存储空间方面的优点采用段页式存贮管理。储空间方面的优点采用段页式存贮管理。 1. 将逻辑地址空间以段划分段式特征将逻辑地址空间以段划分段式特征 2. 将物理地址空间以页划分页式特征将物理地址空间以页划分页式特征 3. 每一段的地址空间划分为页每一段的地址空间划分为页存储管理的存储管理的分配单位分配单位是：段，页是：段，页逻辑地址逻辑地

56、址的组成：段号，页号，页内偏移地址。的组成：段号，页号，页内偏移地址。 将段内地址将段内地址d分为段内页号和页内偏移地址两部分。分为段内页号和页内偏移地址两部分。地址变换地址变换：先查段表，再查该段的页表。缺段中：先查段表，再查该段的页表。缺段中断和缺页中断断和缺页中断。地址结构：地址结构：SPWS：段号P：页号W：页内偏移地址d虚拟段页式管理中的段表和页表虚拟段页式管理中的段表和页表段页式地址变换段页式地址变换优点：优点：具有分段存储管理和分页存储管理的全部优点具有分段存储管理和分页存储管理的全部优点；为用户提供了大量的虚拟存储空间，提高内存为用户提供了大量的虚拟存储空间，提高内存的利用率。

57、的利用率。对大、中型计算机来说，是使用最广泛、最灵对大、中型计算机来说，是使用最广泛、最灵活的一种存储管理。活的一种存储管理。缺点：缺点：增加了硬件成本、系统复杂性和管理上的开销增加了硬件成本、系统复杂性和管理上的开销；表格占用了大量的存储空间；表格占用了大量的存储空间；仍存在内部碎片，存在系统颠簸的危险。仍存在内部碎片，存在系统颠簸的危险。本章的重要概念及相关要求本章的重要概念及相关要求了解存储管理的目的和功能；了解虚拟存储器、地了解存储管理的目的和功能；了解虚拟存储器、地了解存储管理的目的和功能；了解虚拟存储器、地了解存储管理的目的和功能；了解虚拟存储器、地址重定位等概念；址重定位等概念；

58、址重定位等概念；址重定位等概念；分区存储管理：了解分区存储的各种方式（固定、分区存储管理：了解分区存储的各种方式（固定、分区存储管理：了解分区存储的各种方式（固定、分区存储管理：了解分区存储的各种方式（固定、可变、浮动、多重分区）；存储可变、浮动、多重分区）；存储可变、浮动、多重分区）；存储可变、浮动、多重分区）；存储“扩充扩充扩充扩充”技术：覆技术：覆技术：覆技术：覆盖与交换；盖与交换；盖与交换；盖与交换；页式存储管理：掌握分页管理的原理，利用页式存储管理：掌握分页管理的原理，利用页式存储管理：掌握分页管理的原理，利用页式存储管理：掌握分页管理的原理，利用PMTPMTPMTPMT实现实现实现实现地址变换；掌握请求式分页机制、页面淘汰算法；地址变换；掌握请求式分页机制、页面淘汰算法；地址变换；掌握请求式分页机制、页面淘汰算法；地址变换；掌握请求式分页机制、页面淘汰算法；了解段式存储管理的特点；了解段页式存储管理的了解段式存储管理的特点；了解段页式存储管理的了解段式存储管理的特点；了解段页式存储管理的了解段式存储管理的特点；了解段页式存储管理的优点。优点。优点。优点。