动态分区分配方式课件.ppt

1、第四章 存 储 器 管 理 第四章第四章 存储器管理存储器管理第四章 存 储 器 管 理 本章要点本章要点（1/4） 目标：目标：了解简单存储器的管理方式和它们的了解简单存储器的管理方式和它们的实现方法。实现方法。 重定位的基本概念重定位的基本概念 重定位的实质是什么，如何实现重定位？ 为什么要引入重定位？ 静态重定位适用于何种场合，它有何优缺点？ 动态重定位是为了解决什么问题而引入的？ 在连续分配方式、分页系统和分段系统中，分别是如何实现动态重定位的？第四章 存 储 器 管 理 动态分区分配方式动态分区分配方式 什么是动态内存分配？ 在动态内存分配中如何提高内存利用率？ 造成动态分区分配方式

2、内存浪费的主要原因是什么，它可以通过什么办法加以解决？ 动态分区分配算法可采用哪两种数据结构来描述分区的情况？可采用哪些算法来进行内存的分配和回收？ 在采用不同的分配算法时，系统是如何组织空闲分区表或空闲分区链的，它们又是如何进行分区的分配和回收的。 本章要点本章要点（2/4）第四章 存 储 器 管 理 分页和分段存储管理方式分页和分段存储管理方式 是在什么推动力的作用下，使内存管理由动态分区分配方式发展为分页存储管理方式？ 分页系统是如何将地址空间中的作业划分为若干个页，它又是如何进行内存分配的？ 掌握分页系统逻辑地址的结构。 为了进行逻辑地址到物理地址的转换，分页系统必须为每个作业配置什么

3、样的数据结构并提供哪些硬件支持？ 为什么引入快表可加快分页系统存取指令和数据的速度？本章要点本章要点（3/4）第四章 存 储 器 管 理 分页和分段存储管理方式分页和分段存储管理方式 由分页发展为分段，并进一步发展为段页式存储管理方式的主要推动力是什么？ 分段和段页式系统是如何管理作业的地址空间和内存空间的，它们的地址变换是如何完成的？ 试将分页系统与分段系统加以比较。 为什么分段系统比分页系统更容易实现信息的共享和保护？本章要点本章要点（4/4）第四章 存 储 器 管 理 4.1 4.1 存储器的层次结构存储器的层次结构4.2 4.2 程序的装入和链接程序的装入和链接 4.3 4.3 连续分

4、配存储管理方式连续分配存储管理方式4.4 4.4 对换（对换（SwappingSwapping） 4.5 4.5 分页存储管理方式分页存储管理方式 4.6 4.6 分段存储管理方式分段存储管理方式 本章内容本章内容第四章 存 储 器 管 理 4.1 4.1 存储器的层次结构存储器的层次结构第四章 存 储 器 管 理 理想存储器理想存储器 速度快，能跟上处理机的速度 容量大 价格便宜1、存储器的多层结构、存储器的多层结构4.1.1 多层结构的存储器系统多层结构的存储器系统寄存器高速缓存主存储器磁盘缓存固定磁盘可移动存储介质CPU寄存器主存辅存速度价格存储容量图图4-1 计算机系统计算机系统存储层

5、次示意存储层次示意可执行存储器第四章 存 储 器 管 理 2、可执行存储器、可执行存储器第四章 存 储 器 管 理 主存储器：主存储器：也称内存、主存或可执行存储器 CPU的控制部件只能从主存储器中取得指令和数据； CPU与外围设备交换的信息一般依托于主存储器地址空间。 寄存器寄存器 访问速度最快，完全能与CPU协调工作； 容量小、价格昂贵； 寄存器的长度一般以字（word）为单位。4.1.2 主存储器与寄存器主存储器与寄存器1、主存储器、主存储器2、寄存器、寄存器第四章 存 储 器 管 理 高速缓存：高速缓存： 容量大于寄存器，但比内存小，访问速度快于主存储器 根据程序执行局部性原理，将主存

6、中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，提高程序执行速度。 磁盘缓存磁盘缓存 存放外部存储器中频繁使用的一部分磁盘数据和信息 利用主存中的存储空间，来暂存从磁盘中读出的信息4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存1、高速缓存、高速缓存2、磁盘缓存、磁盘缓存第四章 存 储 器 管 理 4.2 4.2 程序的装入和链接程序的装入和链接第四章 存 储 器 管 理 程序在成为进程前的准备工作程序在成为进程前的准备工作编辑编译链接装入运行图图4-2 对用户对用户程序的处理步骤程序的处理步骤编译编译Compiler链接链接Linker装入装入Loder第四章 存 储 器 管

7、理 4.2.1 程序的装入程序的装入 在可执行文件装入时需要解决可执行文件中地可执行文件中地址址（指令和数据）和内存地址内存地址的对应对应。由操作系统中的装入程序loader来完成。 装入模块的三种装入方式：装入模块的三种装入方式： 绝对装入方式 可重定位装入方式 动态运行时装入方式第四章 存 储 器 管 理 在可执行文件中记录内存地址，装入时不再作地址重定位，直接定位在上述(即文件中记录的地址)内存地址。 绝对地址的产生：绝对地址的产生： （1）由编译器完成； （2）由程序员编程完成。 对编译器而言，编程用符号地址，在编译或汇编时再将符号地址转换为绝对地址。 优点：优点：装入过程简单。 缺点

8、：缺点：过于依赖于硬件结构，不适于多道程序系统1、绝对装入方式绝对装入方式(Absolute Loading Mode) 第四章 存 储 器 管 理 绝对地址绝对地址LOAD 222410241424JUMP 14242224内存地址内存地址102414242224装入程序装入程序绝对装入模块绝对装入模块1、绝对装入方式绝对装入方式(Absolute Loading Mode) 第四章 存 储 器 管 理 由装入程序根据内存当时的实际使用情况，将装入模块装入到内存的适当地方。 重定位重定位：在装入时对目标程序中的指令和数据地址的修改过程。 静态重定位：静态重定位：地址变换只是在装入时一次完成，

9、以后不再改变。 缺点：缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。2、可重定位装入方式可重定位装入方式(Relocation Loading Mode) 第四章 存 储 器 管 理 图图 4-3 作业装入内存时的情况作业装入内存时的情况 2、可重定位装入方式可重定位装入方式(Relocation Loading Mode) 第四章 存 储 器 管 理 在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换工作推迟到程序真正执行时才进行。因此，装入内存后的所有地址都是逻辑地址。 优点：优点： OS可以将一个程序分散存放于不连续

10、的内存空间，可以移动程序，有利用实现共享。 能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。 缺点：缺点： 需要硬件支持（重定位寄存器），OS实现较复杂。3、动态运行时装入方式动态运行时装入方式(Dynamic Run-time Loading) 第四章 存 储 器 管 理 4.2.2 程序的链接程序的链接 链接程序的功能：链接程序的功能： 是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。 链接方式：链接方式： 静态链接(static-linking) 装入时动态链接(Run-time dynamic-linking

11、) 运行时动态链接(load-time)第四章 存 储 器 管 理 静态链接：静态链接：是在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装入模块，以后不再拆开的链接方式。1、静态链接方式静态链接方式(Static Linking) 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块图图 4-4 程序链接示意图程序链接示意图 第四章 存 储 器 管 理 2、装入时动态链

12、接装入时动态链接(Load-time Dynamic Linking) 用户源程序经编译后所得到的目标模块，是在装入内存时，采用边装入边链接的链接方式。 优点：优点：便于软件版本的修改和更新 便于实现目标模块共享第四章 存 储 器 管 理 3、运行时动态链接运行时动态链接(Run-time Dynamic Linking) 在运行时，若发现一个被调用模块尚未装入内存，由OS去找到该模块，将它装入内存，并把它链接到调用者模块上。通常被链接的共享代码称为动态链接库(DLL)或共享库(shared library)。 优点：优点： 共享：共享：多个进程可以共用一个DLL，节省内存。 部分装入：部分装

13、入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。 便于局部代码修改：便于局部代码修改：即便于代码升级和代码重用； 便于运行环境适应：便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。 缺点：缺点：链接开销、管理开销第四章 存 储 器 管 理 4.3 4.3 连续分配存储管理方式连续分配存储管理方式第四章 存 储 器 管 理 连续分配方式：连续分配方式： 指为一个系统或用户程序分配一个连续的内存空间。 单一连续分配 固定分区分配 动态分区分配 动态重定位分配4.

14、3 连续连续分配方式分配方式第四章 存 储 器 管 理 4.3.1 单一连续分配单一连续分配 单一连续分配方式单一连续分配方式：内存中仅驻留一道程序，整个内存区为一用户独占。 内存分为两个区域：系统区系统区，用户区用户区。 系统区仅供OS使用，通常位于内存的低端 用户区仅供用户使用，其中只能存放一道作业。 最简单，适用于单用户、单任务的OS。 优点：优点：易于管理。 缺点：缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存第四章 存 储 器 管 理 4.3.2 固定分区分配固定分区分配 又称定长分区或静态分区模式，是满足多道程序设计需要的最简单的存储管理技术

15、 基本思想：基本思想： 给进入主存的用户作业划分一块连续存储区域，把作业装入该连续存储区域，若有多个作业装入主存，则它们可并发执行。 实现：实现： 系统启动时，系统操作员根据作业情况静态地把可分配的主存储器空间（用户空间）分割成若干个连续的区域，每个区域的位置固定，大小可相同也可不同，每个分区在任何时刻最多只装入一道程序执行第四章 存 储 器 管 理 把内存划分为若干个固定大小的连续分区。 分区的划分方法：分区的划分方法： 分区大小相等：分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。 分区大小不等：分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小

16、，分配当前空闲的、适当大小的分区。8 M8 M8 M8 M8 MOperating SystemOperating System8 M12 M8 M8 M6 M4 M2 M固定分区固定分区( (大小相同大小相同) )固定分区固定分区( (多种大小多种大小) )1、划分分区的方法划分分区的方法第四章 存 储 器 管 理 内存分区使用表内存分区使用表 为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表。 分区使用表包括：每个分区的起始地址、大小及状态 作业调度方式作业调度方式 当有一用户程序要装入时，由内存分配程序检索分区使用表，从中找出一个能满足要求的尚未分配的分区，分配给该程

17、序，并将该表项中的状态置为“已分配”。 若未找到大小足够的分区，则拒绝为该用户程序分配内存。2、内存分配内存分配第四章 存 储 器 管 理 特点：特点：适用于多道程序系统和分时系统 支持多个程序并发执行 难以进行内存分区的共享。 比较适合已知程序（作业）大小和出现频率的情形 问题：问题：可能存在内碎片和外碎片。 内碎片：内碎片：占用分区之内未被利用的空间 外碎片：外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。 缺点：缺点： 实际系统运行时，往往无法预知分区大小（太大，等同于“单用户分区模式”） 主存空间利用率仍然较低 无法适应动态扩充主存 分区数目预先确定，限制了多道运行程序的数

18、量3、固定分区、固定分区分配评价分配评价第四章 存 储 器 管 理 图图 4-5 固定分区使用表固定分区使用表操作系统作业A作业B分区号分区号起始地址起始地址长度长度占用标志占用标志112K20K未分配232K32K已分配364K64K已分配4128K128K未分配(a) 分区说明表分区说明表(b) 存储空间分配情况存储空间分配情况20K32K64K128K256K第四章 存 储 器 管 理 4.3.3 动态分区分配动态分区分配 动态分区分配动态分区分配 又称变长分区模式 基本思想：基本思想：按作业的大小划分分区，但划分的时间、大小和位置均动态确定，系统在作业装入主存执行之前并不建立分区。存储

19、空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。第四章 存 储 器 管 理 1、分区分配中的数据结构、分区分配中的数据结构 空闲分区表：空闲分区表：用于记录每个空闲分区的情况。每个空闲分区占 一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。 空闲分区链：空闲分区链：用于实现对空闲分区的分配和链接。前向指针前向指针N个字节可用个字节可用后向指针后向指针N+2N+20（分配标识）（分配标识）0图图 4-7 空闲链结构空闲链结构第四章 存 储 器 管 理 2、动态分区分配算法动态分区分配算法 动态分区分配算法：动态分区分配算法

20、：为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中，选出一分区分配给该作业。第四章 存 储 器 管 理 3、分区分配操作分区分配操作 (1) 分配内存分配内存 图图 4-8 内存分配流程内存分配流程第四章 存 储 器 管 理 (2) 回收内存（四种情况）回收内存（四种情况） 图图 4-9 内存回收时的情况内存回收时的情况 F1XBF2AXAXBF1XF1BF2AFXBF11243AF23、分区分配操作分区分配操作 第四章 存 储 器 管 理 图图 4-10 内存回收流程内存回收流程 F1 X BF1B1F2A XF2A2A X BFX B4A第四章 存 储 器 管 理

21、4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法 常用分配算法：常用分配算法： 首次适应（FF）算法 循环首次适应（NF）算法 最佳适应（BF）算法 最坏适应（WF）算法 适用范围：适用范围： 不太大的系统 系统中通常只设有一个空闲分区链第四章 存 储 器 管 理 要求：要求：空闲分区链以地址递增的次序链接算法：算法：从链首开始顺序搜索，直至找到一个大小能满足要求的空闲分区，从该分区中划出一块能放下作业的空间给请求者，剩下的空闲分区仍留在空闲链中。若未找到大小大于作业要求的大小，则分配失败。缺点：缺点：低地址不断被划分，留下许多难以利用的、很小的空闲分区；因为每次查找都

22、是从低地址开始，从而增加可用空闲分区查找的开销。0KB100KB180KB190KB280KB330KB390KB410KB512KB阴影部分表示已占阴影部分表示已占用块，空白部分表用块，空白部分表示空闲块示空闲块申请申请40K内存内存 1、首次适应算法首次适应算法（first fit, FF） 第四章 存 储 器 管 理 算法：算法：不从链首开始查找，从上次找到的空闲分区的下一空闲分区开始查找要求：要求：设置查找指针，指示下一次起始查询的空闲分区 采用循环查找方式 优点：优点：减少了查找空闲分区的开销缺点：缺点：缺乏大的空闲分区0KB100KB180KB190KB280KB330KB390K

23、B410KB512KB该算法是由首次适应算法演变而成的。该算法是由首次适应算法演变而成的。2、循环首次适应算法循环首次适应算法（next fit, NF） 第四章 存 储 器 管 理 算法：算法：将能满足要求、又是最小的空闲分区分配给作业要求：要求：将空闲分区按容量从小到大形成空闲分区链。缺点：缺点：留下许多难以利用的小空闲区0KB100KB180KB190KB280KB330KB390KB410KB512KB3、最佳适应算法最佳适应算法（best fit, BF） 第四章 存 储 器 管 理 算法：算法：查找时只要看第一个分区能否满足作业要求要求：要求：将空闲分区按容量从大到小形成空闲分区链

24、。缺点：缺点：会使存储器中缺乏大的空闲分区0KB100KB180KB190KB280KB330KB390KB410KB512KB4、最坏适应算法最坏适应算法（worst fit, WF） 优点：优点：产生碎片的几率最小；对中、小作业有利；查找效率很高第四章 存 储 器 管 理 引自操作系统概念第9版P363Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization. Neither fir

25、st fit nor best fit is clearly better than the other in terms of storage utilization, but first fit is generally faster.基于顺序搜索的动态基于顺序搜索的动态分区分配算法的评价分区分配算法的评价第四章 存 储 器 管 理 例：例：采用动态分区分配方式管理内存，内存空采用动态分区分配方式管理内存，内存空间为间为640K，高端，高端40K为系统区。当前用为系统区。当前用户内存区空闲。对下列的请求序列：作业户内存区空闲。对下列的请求序列：作业1申请申请130K、作业、作业2申请申请6

26、0K、作业、作业3申申请请100K、作业、作业2释放释放60K、作业、作业4申请申请200K、作业、作业3释放释放100K、作业、作业1释放释放130K、作业、作业5申请申请140K、作业、作业6申请申请60K、作业、作业7申请申请50K、作业、作业6释放释放60K。画图表示出最佳适应算法进行内存分配和画图表示出最佳适应算法进行内存分配和回收后内存的实际情况回收后内存的实际情况 作业作业2作业作业3作业作业4作业作业5作业作业6作业作业7第四章 存 储 器 管 理 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法 常用分配算法：常用分配算法： 快速适应（QF）算法 伙伴

27、系统 哈希算法 适用范围：适用范围： 大、中型系统第四章 存 储 器 管 理 算法：算法：根据进程长度，寻找能容纳它的最小空闲区链表，并取下第一块进行分配。要求：要求：将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表每个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。缺点：缺点：分区归还主存时算法复杂，系统开销较大；分配空闲分区时是以进程为单位，一个分区只属于一个进程，存在一定的浪费，且空闲分区划分越细，浪费越严重。1、快速适应（快速适应（quick fit）算法（分类搜索法）算法（分类搜索法

28、） 优点：优点：查找效率高；既能保留大的分区，也不会产生内存碎片。第四章 存 储 器 管 理 伙伴系统：伙伴系统：内存分区的大小为2k字节，l=k=m，其中：2l表示分配的最小分区的大小，而2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。空闲分区按分区的大小进行分类，对具有相同大小的所有空闲分区单独设立一个空闲分区双向链表，不同大小的空闲分区形成了k个空闲分区链表。 一个大小为2k，地址为x的内存块，其伙伴块的地址为buddyk(x)2、伙伴系统（伙伴系统（buddy system）112 (mod20)( )2 (mod22 )kkkkkkxxbuddyxxx若若第四章 存 储

29、 器 管 理 伙伴系统的分配算法：伙伴系统的分配算法： 当有一个进程申请K字节时，首先计算一个i值，使2i-1n=2i，然后在空闲分区大小为2i的空闲分区链表中查找：若找到，则把该空闲分区分配给进程；否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i+1的空闲分区链表中寻找，若存在2i+1的空闲分区，则把该空闲分区分为相等的两个分区，其中一个分区用于分配，另一个则加入分区大小为2i的空闲分区链表中。若不存在2i+1的空闲分区，则查找2i+2的空闲分区 伙伴系统的回收：伙伴系统的回收： 当一个进程释放内存时，回收过程需要查找该分区的伙伴是否也空闲，如果空闲，则与伙伴合并起来形成一个大分区

30、。一次回收也可能要进行多次合并。 2、伙伴系统（伙伴系统（buddy system）第四章 存 储 器 管 理 伙伴系统分配举例：伙伴系统分配举例： 假设内存的大小最初为256 KB，内核请求21KB的内存。2、伙伴系统（伙伴系统（buddy system）伙伴系统分配图伙伴系统分配图第四章 存 储 器 管 理 分类搜索算法与伙伴系统算法的缺点：分类搜索算法与伙伴系统算法的缺点：选择合适空闲链表的开销比较大，时间性能受影响。 哈希算法：哈希算法：利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，表的每一个表项记录了一个对应的空

31、闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从而得到相应的空闲分区链表，实现最佳分配策略。3、哈希（哈希（Hash）算法）算法第四章 存 储 器 管 理 4.3.6 可重定位分区分配可重定位分区分配 引入紧凑的原因引入紧凑的原因 连续式分配中，总量大于作业大小的多个小分区不能容纳作业。 紧凑紧凑 通过作业移动将原来分散的小分区拼接成一个大分区。 作业的移动需重定位。1、紧凑紧凑 图图 4-11 紧凑的示意紧凑的示意 第四章 存 储 器 管 理 2、动态重定位动态重定位 什么是动态运行时装入方式？什么是动态运行时装入方式？ 动态重定位

32、：动态重定位：地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的。 动态重定位需要硬件地址变换机构的支持。动态重定位需要硬件地址变换机构的支持。第四章 存 储 器 管 理 2、动态重定位动态重定位 图图 4-12 动态重定位示意图动态重定位示意图 load 1,2500load 1,2500365365load 1,load 1,250025003653650 0100100250025005000500025002500100001000010000100001010010100+ +12500125001500015000作业作业J J处理机一侧处理机一侧存储器一侧存储器一

33、侧重定位寄存器重定位寄存器相对地址相对地址第四章 存 储 器 管 理 3、动态重定位分区分配算法动态重定位分区分配算法 图图 4-11 动态分区分配算法流程图动态分区分配算法流程图 第四章 存 储 器 管 理 4.4 4.4 对换（对换（SwappingSwapping）第四章 存 储 器 管 理 4.4.1 多道程序环境下的对换技术多道程序环境下的对换技术 对换：对换：是指把内存中暂不能运行的进程，或暂时不用的程序和数据换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据换入内存。 整体对换（进程对换）整体对换（进程对换）：以整个进程为单位 进行对换，广泛用于

34、分时系统中，用于解决内存紧张问题，提高内存利用率。 部分对换部分对换 （页面对换或分段对换）（页面对换或分段对换）：以“页”或“段”为单位进行对换。是实现请求分页和请求分段式存储管理的基础，目的是为了支持虚拟存储系统。1、对换的引入对换的引入 2、对换的类型对换的类型 第四章 存 储 器 管 理 对换空间的管理：对换空间的管理：把外存空间分为文件区和对换区 文件区：文件区：存放文件 管理目标：管理目标：提高文件存储空间的利用率 采用离散分配方式 对换区：对换区：存放从内存中换出的进程 管理目标：管理目标：提高进程换入、换出的速度 管理策略采用连续分配方式，较少考虑外存中的碎片问题。4.4.2

35、对换空间的管理对换空间的管理1、对换空间管理的主要目标对换空间管理的主要目标第四章 存 储 器 管 理 数据结构：数据结构：对对换区的空闲盘进行管理。 空闲分区表：盘块号、盘块数 空闲分区链 对换空间的分配与回收：对换空间的分配与回收：与动态分区方式时的内存分配与回收方法雷同。 分配算法：FF、NF、BF、WF等 回收操作：4种情况2、对换区空闲盘块管理中的数据结构对换区空闲盘块管理中的数据结构3、对换空间的分配与回收对换空间的分配与回收第四章 存 储 器 管 理 选择被换出进程：选择被换出进程：因素：处于阻塞状态，且优先级最低；考虑在内存驻留时间。 换出过程：换出过程：对进程换出时只能换出非

36、共享的程序和数据段。先申请对换空间；启动磁盘，并将换出进程的程序和数据传送到磁盘的对换区；若传送过程无错误，则回收对换进程所占用的内存空间，并修改对换进程的PCB；若内存中还有换出的进程，则继续执行换出过程，直至无阻塞进程为止。4.4.3 进程的换出与换入进程的换出与换入1、进程的换出进程的换出第四章 存 储 器 管 理 查看可换入的进程查看可换入的进程查看PCB Set：“就绪”、已换出 选择换入进程选择换入进程换出时间、优先级 申请内存申请内存申请成功：直接将进程从外存调入内存申请失败：先换出内存中的某些进程，再将进程调入2、进程的换入进程的换入第四章 存 储 器 管 理 4.5 4.5

37、分页存储管理方式分页存储管理方式第四章 存 储 器 管 理 基本思想：基本思想： 允许作业存放在若干个不相邻的分区中，既可免去移动内存信息而产生的工作量，又可充分利用主存空间，尽量减少主存碎片。 离散分配方式：离散分配方式：将一个进程直接分散地分配到许多不相邻的分区中。 离散分配三种方式：离散分配三种方式： 分页存储管理（考虑存储器利用率） 分段存储管理（考虑用户要求） 段页式存储管理(考虑存储器利用率和用户要求) 分页存储管理方式：分页存储管理方式：在分页存储管理方式中，如果不具备页面对换功能，则是基本分页存储管理方式，或称为纯分页存储管理方式。 不具有支持实现虚拟存储器的功能 要求把每个作

38、业全部装入内存后方能运行第四章 存 储 器 管 理 4.5.1 页面与页表页面与页表 页面：页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面(page)或页。 页框：页框：把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框( frame) 内存的分配以块为单位，并允许将一个进程的若干页分别装入到多个不相邻的物理块中。 页内碎片页内碎片的形成。1、页面和物理块页面和物理块第四章 存 储 器 管 理 页面大小页面大小1）页面小：）页面小： 优点：优点：使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率； 缺点：缺点：使每个进程占用较多的页面，从而导致进程

39、的页表过长，占用大量内存；还会降低页面换进换出的效率。2）页面大：）页面大： 优点：优点：可以减少页表的长度，提高页面换进换出的速度， 缺点：缺点：会使页内碎片增大 结论：结论：页面的大小应选择得适中，且页面大小应是2的幂，通常为1KB8 KB。1、页面和物理块页面和物理块第四章 存 储 器 管 理 分页地址结构：分页地址结构：页号页号+页内地址页内地址 一页的大小为2的整数次幂 地址的高位部分为页号 低位部分为页内地址2、地址结构地址结构32位地址位地址页面大小为：212=4KB空间最多允许有1M页：220=1M第四章 存 储 器 管 理 页号页号P和页内地址和页内地址d的求法的求法设A 逻

40、辑地址空间中的地址 L 页面大小 则 页号页号P = INT A / L 页内地址页内地址d = A MOD L 例 ：A = 2170 B L = 1 KB P = INT A / L = INT 2170/1024 = 2 d = A MOD L = 2170 MOD 1024 =1222、地址结构地址结构第四章 存 储 器 管 理 第四章 存 储 器 管 理 3、页表页表 图图 4-14 页表的作用页表的作用 页表页表由中存放着块号，通常还包括一存取控制字段。 作用：作用：实现从页号到物理块号的地址映射 系统为每个进程建立的一张页面映射表。第四章 存 储 器 管 理 4.5.2 地址变换

41、机构地址变换机构 任务：任务：实现从逻辑地址到物理地址的转换 利用页面映射表，实现将逻辑地址中页号，转换为内存中的物理块号。1、基本的地址变换机构基本的地址变换机构 通过设置页表寄存器实现，其中： 对于较小系统，页表的功能可以由一组专门的寄存器来实现，一个页表项用一个寄存器，具有很高的访问速度。但寄存器成本较高。 现代计算机页表都很长，因此页表驻留在内存中。只在系统中配置一个页表寄存器(PTR)，用于存放运行进程的页表始址和页表长度。第四章 存 储 器 管 理 图图 4-15 分页系统的地址变换机构分页系统的地址变换机构 页表始址+页号*页表项长度1、基本的地址变换机构基本的地址变换机构 N第

42、四章 存 储 器 管 理 例：某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址3500转换为物理地址的地址转换图逻辑地址逻辑地址3500：1.页号=3500/1K=32.页内地址=3500 MOD 1024=428，3.查页表找到对应得物理块为7，物理地址=7*1K+428=7596第四章 存 储 器 管 理 问题的提出：问题的提出：由于页表是存放在内存中的，这使CPU每次要存取一个数据时，都要两次访问内存。使计算机的处理速度降低近1/2。 “联想存储器联想存储器“或或“快表快表”：为了提高地址的变换速

43、度，在地址变换机构中，增设的一个具有并行查寻能力的特殊高速缓冲存储器。 快表作用：快表作用：存放当前访问的那些页表项。 快表效果：快表效果：取决于对快表的访问命中率。 快表的大小：快表的大小：通常存放16-512个页表项。2、具有快表的地址变换机构具有快表的地址变换机构 第四章 存 储 器 管 理 图图 4-16 具有快表的地址变换机构具有快表的地址变换机构 2、具有快表的地址变换机构具有快表的地址变换机构 第四章 存 储 器 管 理 4.5.3 访问内存的有效时间访问内存的有效时间 内存的有效访问时间内存的有效访问时间(EAT)：从进程发出指定逻辑地址的访问请求，经过地址变换，到内存中找到对

44、应的实际物理地址单元并取出数据，所需花费的总时间。 假定访问一次内存的时间为t，为查找快表所需要的时间，a为快表的命中率，则： 基本分页存储管理方式中：EAT=2t 引入快表的分页存储管理方式中： EAT=a +(t+ )(1-a)+t=2t+ -t a第四章 存 储 器 管 理 例：在一个引入了快表的分页存储系统中，页表放在内存中，多数活动页表项都可以存在快表中。假定一次内存访问时间是100ns，查找快表的时间为20ns，若快表的命中率是85，则访问内存的有效时间为多少？若快表的命中率为50，那么访问内存的有效时间为多少？解：当快表的命中率为解：当快表的命中率为85时，有效存取时间为：时，有

45、效存取时间为： EAT=0.8520(100+20)(10.85) 100135ns当快表的命中率为当快表的命中率为50时，有效存取时间为：时，有效存取时间为： EAT=0. 520(100+20)(10.5) 100170ns第四章 存 储 器 管 理 4.5.4 两级和多级页表两级和多级页表 现代大多数计算机系统，都支持非常大的逻辑地址空间，页表非常大，要占用相当大的内存空间。 例如32位的逻辑地址空间的分页系统，规定页面大小为4KB（占12位），则在每个进程页表中的页表项可达1M（20位）个，占4MB（每个页表项占4B）的内存空间，而且要求连续存放。 一般采用下面两个方法来解决这一问题。

46、1）对页表所需的存储空间，采用离散的分配方式；2）只将当前需要的部分页表项调入内存，其余的表项仍驻留在磁盘上，需要时再调入。第四章 存 储 器 管 理 方法：方法：针对难以找到大的连续内存空间以存放页表的问题，采用将页表进行分页的办法，使每个页面的大小与内存物理块的大小相同，并进行编号。 实现了离散地将每个页表的页面分别放在不同的物理块中的目的。 外层页表外层页表（Outer Page Table）：为离散分配的页表页面建立的一张页表，该页表的每个页表项中记录了页表页面的物理块号。1、两级页表两级页表(Two-Level Page Table) 图图 4-17 两级页表逻辑地址结构两级页表逻辑

47、地址结构 第四章 存 储 器 管 理 图图 4-18 两级页表结构两级页表结构 012102301210230121023第0页页表第1页页表第n页页表1461141151468012n101117421078017263451141151468外部页表1、两级页表两级页表(Two-Level Page Table) 第四章 存 储 器 管 理 具有两级页表的地址变换机构图具有两级页表的地址变换机构图 外部页号P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址1、两级页表两级页表(Two-Level Page Table) 第四章 存 储 器 管 理 对于32机器

48、采用两级页表结构是合适的，但对于64位机器需采用三级、四级页表结构。 2、多级页表多级页表第四章 存 储 器 管 理 4.5.5 反置页表反置页表 反置页表的引入：反置页表的引入：现代计算机系统，进程的逻辑地址空间很大，为减少页表占用的内存空间，所以引入了反置页表。 反置页表：反置页表：为每个物理块设置一个页表项，内容包括页号和页号隶属进程的标识符，并将它们按物理块的编号排序。1、反置页表的引入反置页表的引入第四章 存 储 器 管 理 根据进程标识符和页号检索反置页表 检索到匹配的页表项，则该页表项的序号i与页内地址就直接拼接成物理地址。 未检索到，则表明此页未装入内存。2、地址变换地址变换反

49、置页表地址变换示意图反置页表地址变换示意图 第四章 存 储 器 管 理 例：例：某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、4500转换为物理地址。1）逻辑地址）逻辑地址1023：1023/1K得页号为得页号为0，页内地址为，页内地址为1023，查页表找到对应得物理块为查页表找到对应得物理块为2，故物理地址为，故物理地址为2*1K+1023=3071。2）逻辑地址）逻辑地址2500：2500/1K得页号为得页号为2，页内地址为，页内地址为452，查页表找到对应得物理块为，查页表找

50、到对应得物理块为6，故物理地址为，故物理地址为6*1K+452=6596。3）逻辑地址）逻辑地址4500：4500/1K得页号为得页号为4，页内地址为，页内地址为404，页号大于页表长度，产生越界中断，页号大于页表长度，产生越界中断第四章 存 储 器 管 理 例：某系统有224字节的内存，固定分区的大小为216字节，1）进程表中的每个表项至少要用多少位来记录分配给进程的分区？2）界限寄存器必须要有多少位？答：答：1）224字节字节/ 216字节字节= 28字节，因此需要字节，因此需要8位来存储位来存储28个个分区中的一个。分区中的一个。 2）固定分区的大小为）固定分区的大小为216字节，故最大