四章节存储器管理.ppt

《四章节存储器管理.ppt》由会员分享，可在线阅读，更多相关《四章节存储器管理.ppt（87页珍藏版）》请在三一文库上搜索。

1、第四章 存储器管理,4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式,4.1 程序的装入和链接,图 4-1 对用户程序的处理步骤,4.1.1 程序的装入,1. 绝对装入方式 (单道系统中),程序中所使用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。 通常是在编译或汇编时，再将这些符号地址转换为绝对地址。,2. 可重定位装入方式(Relocation Loading Mode),图 4-2 作业装入内存时的情况,3

2、. 动态运行时装入方式(Denamle Run-time Loading),动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址， 而是把这种地址转换推迟到程序真正要执行时才进行。 因此， 装入内存后的所有地址都仍是相对地址。,4.1.2 程序的链接,1. 静态链接方式(Static Linking),图 4-3 程序链接示意图,在将这几个目标模块装配成一个装入模块时，须解决以下两个问题： (1) 对相对地址进行修改。 (2) 变换外部调用符号。,2. 装入时动态链接(Loadtime Dynamic Linking),目标模块是边装入内存边链接的。 优点

3、： 便于修改和更新。 （目标模块是分开存放的） (2) 便于实现对目标模块的共享。 （一个目标模块可链接到几个应用模块 ）,3. 运行时动态链接(Run-time Dynamic Linking),在执行过程中，当发现一个被调用模块尚未装入内存时，再装入内存， 把它链接到调用者模块上。 未被用到的目标模块，都不会被调入内存和被链接到装入模块上，（如：错误处理用的目标模块） 优点：加快程序的装入过程，可节省大量的内存空间。,4.2 连续分配方式,4.2.1 单一连续分配 （单用户、单任务）,把内存分为系统区和用户区两部分 系统区仅提供给OS使用，通常是放在内存的低址部分； 用户区是指除系统区以外

4、的全部内存空间， 提供给用户使用。,4.2.2 固定分区分配,1. 划分分区的方法,分区大小相等。 程序太小时浪费内存，程序太大时可能不足以装入。 (2) 分区大小不等。 多个较小的分区，适量的中等分区，少量大分区,2. 内存分配,图 4-4 固定分区使用表,4.2.3 动态分区分配,1. 分区分配中的数据结构,空闲分区表。 表目：序号，始址 大小 (2) 空闲分区链。,图 4-5 空闲链结构,2. 分区分配算法,首次适应算法FF。 以地址递增的次序链接空闲分区 分配内存时，从链首顺序查找，找到为止，若找不到则分配失败 优点：优先利用低址，从而保留高址的大空间 缺点：低址不断利用，留下碎片；增

5、加查找开销 (2) 循环首次适应算法，该算法是由首次适应算法演变而成的。 由首次适应算法演变而来，只是从上次找到的空闲分区的下一个开始查找 采用循环查找的方式 优点：空闲分区的分布得更均匀；缺点：会缺乏大空闲分区； (3) 最佳适应算法。 找到满足要求，又是最小的空闲分区 从小到大形成一空闲分区链 但切割剩余部分是最小的,3. 分区分配操作,1) 分配内存,图 4-6 内存分配流程,2) 回收内存（四种情况）,图 4-7 内存回收时的情况,4.2.4 可重定位分区分配,1. 动态重定位的引入（要求连续空间，移动后的程序须重定位）,图 4-8 紧凑的示意,2. 动态重定位的实现,动态装入方式中，

6、内存中的作业仍是相对地址，在程序执行时，才转换为绝对地址 为加快转换速度，增设重定位寄存器，用于存放起始地址 在小分区“拼凑”时，不需对程序作任何修改,2. 动态重定位的实现,图 4-9 动态重定位示意图,3. 动态重定位分区分配算法,图 4-10 动态分区分配算法流程图,4.2.5 对换(Swapping),1. 对换的引入,所谓“对换”， 是指把内存中暂时不能运行的进程或数据，调出到外存上，再把已具备运行条件的进程或数据，调入内存。 对换是提高内存利用率的有效措施。,2. 对换空间的管理,在外存中设一对换区，用于存放换出的进程 进程在对换区中驻留是短暂的，对换是频繁的，故采用连续分配方式，

7、以提高速度 对换区的分配同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。,3. 进程的换出与换入,(1) 进程的换出。 1、系统首先选择处于阻塞状态且优先级最低的进程作为换出进程， 2、将该进程的程序和数据传送到磁盘的对换区上。 3、若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的PCB做相应的修改。,(2) 进程的换入。 将换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。,4.3 基本分页存储管理方式,4.3.1 页面与页表,1. 页面 1) 页

8、面和物理块 页面或页：将进程的逻辑地址空间分成若干个大小相等的片，并为各页从0开始加以编号。 (物理)块或页框(frame)：把内存空间分成与页面相同大小的若干个存储块，加以编号。 在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。 “页内碎片”：由于进程的最后一页经常装不满一块而形成了不可利用的碎片。,2) 页面大小 页面若太小： 内存碎片减小 但会导致进程的页表过长，占用更多的内存； 还会降低页面换进换出的效率。 若页面较大： 虽然可以减少页表的长度，提高页面换进换出的速度， 但却又会使页内碎片增大。 合适的页面大小： 应是2的幂，通常为512 B8 K

9、B。,2. 地址结构,分页地址中的地址结构如下：,31,12,11,0,对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A(2170)，页面的大小为L(1024)，则页号P(2)和页内地址d(122)可按下式求得：,3. 页表（每个进程一个页表，将页号转换为块号）,图 4-11 页表的作用,4.3.2 地址变换机构,1. 基本的地址变换机构（始址和长度是平时放在PCB中，运行时调入寄存器）,图 4-12 分页系统的地址变换机构,2. 具有快表的地址变换机构 (一次访存),图 4-13 具有快表的地址变换机构,快表也叫“联想寄存器”，IBM系统中也称“TLB” CPU给出有效地

10、址，先查快表，若找到则直接读物理块，若没找到则找内存中的页表，并把表项送到快表中，若快表满则找不再需要的页表项换出。,4.3.3 两级和多级页表,一般计算机系统逻辑地址空间(232264)，页表就变得非常大，要占很大内存空间。 如，一个32位逻辑地址空间的分页系统，页面大小为4 KB即212 B，则每个进程页表中的页表项可达1兆个。每个页表项占一个字节， 其页表就要占用1MB的内存空间，而且还要求是连续的。 可以采用这样两个方法来解决这一问题： 采用离散分配方式来解决难以找到一块连续的大内存空间的问题： 只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入。,1. 两级

11、页表(Two-Level Page Table),逻辑地址结构可描述如下：,图 4-14 两级页表结构,图 4-15 具有两级页表的地址变换机构,两级页表采用离散分配空间的方法，但并没有减少页表所占空间。 故采用只将当前需要的页表调入内存，以后再根据需要陆续调入。 在外层页表中增设一个状态位S，若为0表示页表不在内存，若为1表示在内存。,2. 多级页表 对于64位的机器，如果页面大小仍采用4 KB，此时在外层页表中可能有4096 G个页表项， 要占用16384 GB的连续内存空间。 必须采用多级页表，将外层页表再进行分页。 对于64位的计算机，如果要求它能支持2(=1844744 TB)规模的

12、物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入,引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要： 1) 方便编程 （按逻辑关系分段） 2) 信息共享 （以段为逻辑单位，便于共享，如函数） 3) 信息保护 4) 动态增长 （便于段（数据段）的增长） 5) 动态链接 （目标程序）段动态链接,4.4.2 分段系统的基本原理,1. 分段,分段地址中的地址具有如下结构：,31 16 15 0,按主程序，子程序，数据，栈等分段 每段从0开始编号，段长不定,为每一个段分配一个连续分区

13、 各个段离散地放在内存中不同的分区中 建立一段表，用于从逻辑段到物理内存区的映射 段表中的表项存放段的基址和段的长度 段表通常放在内存中,2. 段表,图 4-16 利用段表实现地址映射,图 4-17 分段系统的地址变换过程,3. 地址变换机构,4. 分页和分段的主要区别,(1) 页是信息的物理单位，分页是为实现离散分配方式，分页仅仅是由于系统管理的需要而不是用户的需要。 段则是信息的逻辑单位，它含有一组其意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。,(2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的； 而段的长度却不固定，通常由编

14、译程序在对源程序进行编译时，根据信息的性质来划分。 (3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。,4.4.3 信息共享,图 4-18 分页系统中共享editor的示意图,图 4-19 分段系统中共享editor的示意图,4.4.4 段页式存储管理方式,1. 基本原理,图 4-20 作业地址空间和地址结构,图 4-21 利用段表和页表实现地址映射,2. 地址变换过程,图 4-22 段页式系统中的地址变换机构,4.5 虚拟存储器的基本概念,4.5.1

15、虚拟存储器的引入,1. 常规存储器管理方式的特征,一次性。(全部装入，但浪费空间) (2) 驻留性。 （长期驻留，直到结束）,2. 局部性原理,早在1968年， Denning.P就曾指出： (1) 程序执行时，除了少部分的转移和过程调用指令外， 在大多数情况下仍是顺序执行的。 (2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域， 但经研究看出，过程调用的深度在大多数情况下都不超过5。 (3) 程序中存在许多循环结构，这些虽然只由少数指令构成， 但是它们将多次执行。 (4) 程序中还包括许多对数据结构的处理， 如对数组进行操作， 它们往往都局限于很小的范围内。,局限性又表现在下述

16、两个方面： (1) 时间局限性。某条指令或数据一旦执行或访问，则不久以后该指令可能再次执行或访问。 典型原因：是由于在程序中存在着大量的循环操作。 (2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即访问可能集中在一定范围内 典型情况：程序的顺序执行。,3. 虚拟存储器定义,所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。 其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本接近于外存。 虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、 中、 小型机器和微型机

17、中。,4.5.2 虚拟存储器的实现方法,1. 分页请求系统,（1）硬件支持。 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构； 缺页中断机构，即要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存； 地址变换机构。(增加了产生和处理缺页中断和换出功能),4.5.3 虚拟存储器的特征,多次性（作业分多次调入内存） 对换性（允许换入换出） 虚拟性 （从逻辑上扩充内存容量）,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持,1. 页表机制,访问字段A：被访问的次数或多长时间没被访问。,2. 缺页中断机构,图 4-23 涉及6

18、次缺页中断的指令,缺页中断与其他中断的区别： 1、在指令执行期间产生和处理中断信号。 2、一条指令在执行期间可能产生多次缺页中断。（右图6次）,3. 地址变换机构,图 4-24 请求分页中的地址变换过程,4.6.2 内存分配策略和分配算法,1. 最小物理块数的确定,是指能保证进程正常运行所需的最小物理块数。少于此值时，进程将无法运行。 最少物理块数与计算机的硬件结构有关，取决于指令格式、 功能和寻址方式。 单地址指令且采用直接寻址方式，则所需的最少物理块数为2，指令+数据。 间接寻址，则至少要求有三个物理块。指令长度可能跨页 源地址和目标地址所涉及的区域也都可能跨两个页面。,2. 物理块的分配

19、策略,在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时， 也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。 1) 固定分配局部置换(固定块数，不够换出，块数太多太少都不好) 2) 可变分配全局置换 (先分几块，不够再从系统空闲块中分，空闲块用完，再从全局选换出的块) 3) 可变分配局部置换(先分几块，从局部换，缺页率高时增块，反之减块),3. 物理块分配算法,1) 平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个进程。 例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。未考虑到各进程本身的大小。如有

20、一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。,2) 按比例分配算法 根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为： 又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有： b应该取整，它必须大于最小物理块数。,3) 考虑优先权的分配算法 为重要的、紧迫的作业多分配内存空间。 通常把内存中可分配块分成两部分： 一部分按比例地分配给；另一部分则按优先权分。 有的系统中，如重要的实时控制系统，则可能是完全按优先权分。,4.6.3

21、 调页策略,1. 何时调入页面,预调页策略 预测不久会被访问的页预先调入(成功率只有50% ) ， 每次调入多页，减少开销，一般用于首次调入 2) 请求调页策略 发现不在内存再调入。每次调入一页，开销大,2. 从何处调入页面,在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。 对换区是采用连续分配方式，而文件区是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。 缺页时，应从何处将所缺页调入，可分成如下三种情况： (1) 系统拥有足够的对换区空间，可全部从对换区调入所需页面，以提高调页速度。在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。,(

22、2) 系统缺少足够的对换区空间，凡不会被修改的文件，都直接从文件区调入；换出这些页面时不必换出，以后再调入时，仍从文件区直接调入。可能被修改的文件，换出时须调到对换区，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。曾经运行过被换出到对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，某进程所请求的页面有可能已被其它进程调入内存，就无须再从对换区调入。,3. 页面调入过程 所要页面未在内存时，向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后， 转入缺页中断处理程序。该程序通过

23、查找页表，得到该页在外存的块后，若此时内存有空，则启动磁盘I/O将所缺之页调入内存，然后修改页表。若内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，不必写回磁盘；但如果此页已被修改， 则必须将它写回磁盘，然后再把所缺的页调入内存， 并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表， 去形成所要访问数据的物理地址，再去访问内存数据。,4.7 页面置换算法,4.7.1 最佳置换算法和先进先出置换算法,1. 最佳(Optimal)置换算法 其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访

24、问的页面。 采用最佳置换算法，通常可保证获得最低的缺页率。,假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串： 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-25 利用最佳页面置换算法时的置换图,2. 先进先出(FIFO)页面置换算法,图 4-26 利用FIFO置换算法时的置换图,4.7.2 最近最久未使用(LRU)置换算法,1. LRU(Least Recently Used)置换算法的描

25、述,图 4-27 LRU页面置换算法,2. LRU置换算法的硬件支持,1) 寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为,R=Rn-1Rn-2Rn-3 R2R1R0,定时将寄存器右移一位，n位整数最小的为最近最久未使用的页面，某页被访问则将Rn-1置1 下例中，3页最久未被访问,图 4-28 某进程具有8个页面时的LRU访问情况,2) 栈,图 4-29 用栈保存当前使用页面时栈的变化情况,栈底就是最近最久未用的页号,4.7.3 Clock置换算法,1. 简单的Clock置换算法,图 4-30 简单Clock置换算法的流程和示例,按FIFO形成

26、循环队列，某页被访问时置1。 换页时，若是0则换出；若是1则重新置0。,2. 改进型Clock置换算法,由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。,其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找第一类页面，将所遇到的第一个页面作

27、为所选中的淘汰页。在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，则开始第二轮扫描，寻找第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。 (3) 重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。,4.7.4 其它置换算法,最少使用(LFU： Least Frequently Used)置换算法 2. 页面缓冲算法(PBA： Page Buffering Algorithm),4.8 请求分段存储管理方式,4.8.1 请求分段中的硬件支持,1. 段表机制,增补位：表示本段在运行中，是否做过动态增长,在段表项中，

28、 除了段名(号)、 段长、 段在内存中的起始地址外， 还增加了以下诸项： (1) 存取方式。存取属性，如执行，只读，读/写 (2) 访问字段A。 (3) 修改位M。 (4) 存在位P。 (5) 增补位。是否做过动态增长； (6) 外存始址。,2. 缺段中断机构,图 4-31 请求分段系统中的中断处理过程,3. 地址变换机构,图 4-32 请求分段系统的地址变换过程,4.8.2 分段的共享与保护,1. 共享段表 （系统中配置一共享段表）,图 4-33 共享段表项,2. 共享段的分配与回收,1) 共享段的分配 在为共享段分配内存时，第一个请求该共享段的进程，为该共享段分配一物理区，共享段调入该区，

29、修改进程的段表，还须在共享段表中增加一表项，填写有关数据，把count置1； 当其它进程需调用该共享段时，该段在内存，只需修改调用进程的段表；然后在共享段表中，填上调用进程的进程名、存取控制等，再执行count=count+1操作，以表明有两个进程共享该段。,2) 共享段的回收 当共享此段的某进程不再需要该段时，应将该段释放， 包括撤消在共享段表中该进程所对应的表项，以及执行count=count-1操作。 若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项， 表明此时已没有进程使用该段；否则(减1结果不为0)， 则只是取消调用者进程在共享段表中的有关记录。,3. 分段保护,越界检查 2) 存取控制检查 只读 (2) 只执行 (3) 读/写 3) 环保护机构 一个程序可以访问驻留在相同环或较低特权环中的数据。 一个程序可以调用驻留在相同环或较高特权环中的服务。,图 4-34 环保护机构,