操作系统复习4_存储器管理.pdf

《操作系统复习4_存储器管理.pdf》由会员分享，可在线阅读，更多相关《操作系统复习4_存储器管理.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 存储器管理 4.1 存储器的层次结构存储器应容量大,便宜,速度跟上处理器 4.1.1 多级存储器结构 通常有三层，细分为六层，如图 4-1，越往上，速度越快，容量越小，价格越贵。寄存器和主存又称可执行存储器，进程可直接用指令访问，辅存只能用 I/O 访问。4.1.2 主存储器与寄存器 1.主存储器-内存，保存进程运行时的程序和数据。CPU 与外围设备交换的信息一般也依托于主存储器地址空间。为缓和访存速度远低于 CPU 执行指令的速度，在计算机系统中引入了寄存器和高速缓存。2.寄存器-与 CPU 协调工作，用于加速存储器的访问速度，如用寄存器存放操作数，或用地址寄存器加快地址转换速度等。

2、4.1.3 高速缓存和磁盘缓存 1.高速缓存-根据程序执行的局部性原理将主存中一些经常访问的信息(程序、数据、指令等)存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。2.磁盘缓存-将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读/写入的信息。4.2 程序的装入和链接 多道程序运行，需先创建进程。而创建进程第一步是将程序和数据装入内存。将源程序变为可在内存中执行的程序，通常都要经过以下几个步骤：编译-若干个目标模块；链接-链接目标模块和库函数，形成装入模块；装

3、入-将装入模块装入内存。图 4-2 对用户程序的处理步骤 寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU 寄存器主存辅存库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存4.2.1 程序的装入无需连接的单目标模块装入（理解装入方式）1.绝对装入方式(Absolute Loading Mode)-只适用单道程序环境 如果知道程序的内存位置，编译将产生绝对地址的目标代码，按照绝对地址将程序和数据装入内存。由于程序的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。绝对地址：可在编译时给出或由程序员直接赋予。若由程序员直接给出，不利于程序或数据修改，因此，通常

4、是在程序中采用符号地址，然后在编译或汇编时转换为绝对地址。2.可重定位装入方式(Relocation Loading Mode)-适于多道程序环境 多道程序环境下，编译程序不能预知目标模块在内存的位置。目标模块的起始地址是 0，其它地址也都是相对于 0 计算的。此时应采用可重定位装入方式，根据内存情况，将模块装入到内存的适当位置，如图 4-3 作业装入内存时的情况。3.动态运行时装入方式(Dynamic Run-time Loading)-适于多道程序环境 可重定位装入方式并不允许程序运行时在内存中移动位置。但是，在运行过程中它在内存中的位置可能经常要改变，此时就应采用动态运行时装入方式。动态

5、运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正执行时才进行。因此，装入内存后的所有地址都仍是相对地址。问题：程序装入内存后修改地址的时机是什么？4.3 连续分配方式 4.3.3 动态分区分配根据进程需要动态分配内存 1.分区分配中的数据结构 (1)空闲分区表用若干表目记录每个空闲分区的分区序号、分区始址及分区的大小等数据项。(2)空闲分区链-为实现对空闲分区的分配和链接，在每分区起始部分，设置前向指针，尾部则设置一后向指针。为检索方便，在分区前、后向指针中，重复设置状态位和分区大小表LOAD 1,2500365LOAD

6、1,2500365100001100012500150005000250010000作业地址空间内存空间目。当分区被分配后，把状态位由“0”改为“1”时，前、后向指针失去意义。图 4-5 空闲链结构 2.分区分配算法（P123）1）首次适应算法(first-fit)空闲分区链以地址递增次序链接 每次按分区链的次序从头查找，找到符合要求的第一个分区。2)循环首次适应算法FF 算法的变种 从上次找到的空闲分区位置开始循环查找，找到后，修改起始查找指针。3)最佳适应算法空闲分区按容量从小到大排序 把能满足要求的、最小的空闲分区分配给作业 4)最坏适应算法空闲分区按容量从大到小排序 挑选最大的空闲区分

7、给作业使用；5)快速适应算法根据容量大小设立多个空闲分区链表 3.分区分配操作 1.分配内存 请求分区 u.size;空闲分区 m.size;m.size-u.sizesize，说明多余部分太小,不再切割，将整个分区分配给请求者；否则从该分区中划分一块请求大小的内存空间，余下部分仍留在空闲分区链。如图 4-6 内存分配流程。2.回收内存(1)回收区与插入点的前一空闲分区 F1 相邻：合并，修改 F1 大小。(2)回收区与后一空闲分区 F2 相邻：合并，修改首地址和大小。(3)回收区同时与前、后两个分区邻接：合并，修改 F1 大小，取消 F2。(4)回收区不邻接：新建表项，填写首地址和大小，并插

8、入链表。如图 前向指针N20N个字节可用后向指针N20 图 4-6 内存分配流程 4.3.6 可重定位分区分配 1动态重定位的引入 例：在内存中有四个互不邻接的小分区，容量分别为 10KB、30KB、14KB 和 26KB。若现有一作业要获得 40KB 的内存空间，因连续空间不足作业无法装入。可采用的一种解决方法是：通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑。由于用户程序在内存中位置的变化，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。图 4-8 紧凑的示意 4.3.7 对换（即中级调度）1.对换(Swapping)的引入 从头开始

9、查表检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出u.size 大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a)紧凑前(b)紧凑后“活动阻塞”进程占用内存空间；外存上的就绪作业不能进入内存运行。所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间；再把已具备运行条件的进程或所需要的程序和数据，调入内存

10、。对换是提高内存利用率的有效措施。根据对换单位可分为：进程对换、页面对换和分段对换。为了能实现对换，系统应具备以下三方面功能：对换空间的管理、进程的换出与换入 2.进程的换出与换入(1)进程的换出 选择阻塞且优先级最低的进程，将它的程序和数据传送到磁盘对换区上。回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。(2)进程的换入 找出“就绪”但已换出到磁盘上时间最久的进程作为换入进程，将之换入，直至已无可换入的进程。4.4 基本分页存储管理方式 前面的连续分配方案会形成许多“碎片”，“紧凑”方法可以解决碎片但开销大。是否允许进程离散装入？离散单位不同，称分页式存储和分段式存储。不具

11、备对换功能称为“基本分页式”，支持虚拟存储器功能称为“请求基本分页式”。4.4.1 页面与页表 1.页面 1)页面和物理块-将进程的逻辑地址空间分成若干个大小相等的片，称为页面，并为各页编号。相应地把内存空间分成与页面相同大小的若干个存储块，称为物理块，也同样编号。分配时，将进程中的页装入到物理块中，最后一页经常装不满一块而形成“页内碎片”。2)页面大小-页面的大小应选择适中。页面太小，内存碎片减小，利用率高；但页表过长，占大量内存。页面较大，页表长度小；但页内碎片大。因此，页面的大小应选择得适中，且页面大小应是 2 的幂，通常为 512 B8 KB。2.地址结构 分页地址中的地址结构如下：3

12、1 12 11 0 它含有两部分：页号P(1231位,最多有1M页)和页内位移量W(011位,每页的大小4KB)；对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为 A，页面的大小为 L，则页号 P 和页内地址 d 可按下式求得：页号 P 位移量 W MODLAdLAINTP3.页表-实现从页号到物理块号的地址映射 用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存0123456789104.4.2 地址变换机构 任务：将逻辑地址转换为物理地址；页内地址变换:因页内地址与物理地址一一对应,可直接转换；页号变换：页表可实现从逻辑地址中页号到内

13、存中物理块号的变换；1基本的地址变换机构 a.页表功能可由一组专门的寄存器实现(原理)；b.页表大多驻留内存，系统中只设置一页表寄存器来存放页表在内存的始址和页表长度(实际操作)；c.进程未执行时，页表始址和长度存放在 PCB 中。执行时才将这两个数据装入页表寄存器中(过程)。图 4-12 分页系统的地址变换机构 2.具有快表的地址变换机构 a.仅用页表寄存器时，CPU 每存取一数据要两次访问内存(页表-地址变换-数据)；b.为提高地址变换速度，可在地址变换机构中增设一具有并行查寻能力的特殊高速缓冲寄存器用以存放当前访问的那些页表项，称为“快表”。c.-在 CPU 给出逻辑地址，将页号 P 送

14、入快表 -页号匹配，读物理块号后送物理地址寄存器 -无匹配页号，再访问内存中页表，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入到快表中。-如快表已满，则 OS 须找到一换出页表项换出。为什么增加“快表”？为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表“快表”有何缺点？页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址3 图 4-13 具有快表的地址变换机构 4.5 基本分段存储管理方式 4.5.1 分段存储管理方式的引入（

15、为什么引入）推动内存从固定分配到动态分配直到分页存储，主要动力是内存利用率，而引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：1)方便编程-把作业按逻辑关系划分为若干段，每段有自己的名字和长度，并从 0 开始编址。LOAD 1,A|;STORE 1,B|2)信息共享-段是信息的逻辑单位。为实现共享，存储管理应与用户程序分段的组织方式相适应。3)信息保护-对信息的逻辑单位进行保护，应分段管理。4)动态增长-分段存储能解决数据段使用过程中动态增长。5)动态链接-运行过程中动态调入以段为单位的目标程序。4.5.2 分段系统的基本原理 1.分段 作业划分为若干段，如图 4-16，每个

16、段用段号来代替段名，地址空间连续。段的长度由逻辑信息长度决定，因而各段长度不等。其逻辑地址由段号(段名)和段内地址所组成，结构如下：31 16 15 0 该地址结构中，允许一个作业最多有 64K 个段，每个段的最大长度为 64KB。编译程序能自动根据源程序产生若干个段。2.段表 段号 段内地址 页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址每个段一个连续分区，各段可以离散存入不同分区。为每个进程建立一张段映射表(段表),其中每段占一个表项，记录该段在内存中的始址(又称为“基址”)和段长度。常将段表放在内存中。图 4-16 利用段表实现

17、地址映射 3.分页和分段的主要区别 (1)页是信息的物理单位，分页是为提高内存的利用率，是为满足系统管理的需要。段则是信息的逻辑单位，分段是为了能更好地满足用户的需要。(2)页的大小固定且分页由系统硬件实现；而段的长度不固定，通常由编译程序根据信息的性质来划分。(3)分页的作业地址空间是一维的，程序只需一个地址记忆符；而分段的作业地址空间是二维的，程序员既需给出段名，又需给出段内地址。4.5.3 信息共享 可重入代码(纯代码):允许多个进程同时访问的代码。绝对不允许可重入代码在执行中改变,因此，不允许任何进程修改它。4.5.4 段页式存储管理方式 1.基本原理-将分段(满足用户需求)和分页(内

18、存利用率高)结合，先将用户程序分成若干个段，再把每个段分成若干个页,图 4-20 给出作业地址空间结构，作业有三个段，页面大小4KB。图 4-20 作业地址空间和地址结构 作业空间(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间012304K8K12K15K16K子 程 序 段04K8K数 据 段04K8K10K12K(a)段 号(S)段 内 页 号(P)页 内 地 址(W)(b)主 程 序 段 图 4-2

19、1 利用段表和页表实现地址映射 4.6 虚拟存储器的基本概念 前面各种存储器管理方式共同点：它们要求将一个作业全部装入内存后方能运行，于是出现了下面这样两种情况：(1)有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行。(2)有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业 装入内存让它们先运行，而将其它大量的作业留在外存上等待。4.5.1 虚拟存储器的引入 1.常规存储器管理方式的特征(1)一次性。将作业全部装入内存后方能运行，此外有许多作业在每次运行时，并非其全部程序和数据都要用到。一次性装入，造成了对内存空间的浪费。(2)

20、驻留性。作业装入内存后一直驻留，直至运行结束。尽管因故等待或很少运行，都仍将继续占用宝贵的内存资源。现在要研究的问题是：一次性及驻留性在程序运行时是否必需。2.局部性原理 早在 1968 年，Denning.P 就曾指出：(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。(2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过 5。(3)程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。(4)程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。局限性主要表

21、现在下述两个方面：(1)时间局限性由于循环操作的存在。如果程序中的指令或数据一旦执行，则不久以后可能再次访问。段号 状态 页表大小 页表始址0111213041页号 状态存储块#0111213041操作系统主存页表段表段表大小 段表始址段表寄存器(2)空间局限性由于程序的顺序执行。程序在一段时间内所访问的地址，可能集中在一定的范围之内。3.虚拟存储器定义-基于局部性原理 程序运行前，仅须将要运行的少数页面或段装入内存便可启动，运行时，如果需要访问的页(段)尚未调入内存(缺页或缺段)，用 OS 提供请求调页(段)功能调入。如果此时内存已满，则还须再利用页(段)的置换功能，将内存中暂时不用的页(段

22、)调至外存，腾出足够的内存空间后，再将要访问的页(段)调入。所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上扩充内存容量的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存，成本接近于外存。4.6.3 虚拟存储器的特征 1)多次性-一个作业被分成多次调入内存运行，最初装入部分程序和数据，运行中需要时，再将其它部分调入。2)对换性-允许在作业的运行过程中进行换进、换出。换进和换出能有效地提高内存利用率。3)虚拟性-从逻辑上扩充内存容量，使用户所看到远大于实际内存容量。这是虚拟存储器最重要的特征和最重要的目标。4)离散性-是以上三个特性的基础，在内存分配时采用

23、离散分配的方式。备注：虚拟性是以多次性和对换性为基础的，而多次性和对换性又必须建立在离散分配的基础上。4.7 请求分页存储管理方式 4.6.1 请求分页中的硬件支持-页表、缺页中断和地址变换 请求分页系统是在分页的基础上，增加了“请求调页”和“页面置换”功能，每次调入和换出基本单位都是长度固定的页，实现比请求分段简单。1页表机制-将用户地址空间中的逻辑地址变换为内存空间中的物理地址，因只将部分调入内存，需增设若干项。在请求分页系统中的每个页表项如下所示：(1)状态位 P：该页是否已调入内存，供访问时参考。(2)访问字段 A：记录一段时间内本页被访问的频率，供选择换出页时参考。(3)修改位 M：

24、页在调入内存后是否被修改过，供置换页面时参考。(4)外存地址：指出该页在外存上的地址，即物理块号，供调入该页时参考。4.7.2 内存分配策略和分配算法 1.最小物理块数的确定（*）是指能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关。对于某些简单的机器，所需的最少物理块数为 2，分别用于存放指令和数据，间接寻址时至少要有三块。页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址 对于某些功能较强的机器，因其指令本身、源地址和目标地址都可能跨两个页面，至少要为每个进程分配 6 个物理块，以装入这些

25、页面。2.物理块的分配策略 请求分页系统的两种内存分配策略：即固定和可变分配策略；两种置换策略：即全局置换和局部置换。可组合出以下三种策略。1)固定分配局部置换(Fixed Allocation,Local Replacement)-每进程分配一定数目的物理块，在整个运行期间都不再改变，换入换出都限于这些物理块。每个进程物理块难以确定，太多太少都不好 2)可变分配全局置换(Variable Allocation,Global Replacement)-每进程分配一定数目的物理块，OS 保持一空闲物理块队列。进程缺页时，摘下一空闲块，并将该页装入。3)可变分配局部置换(Variable Allo

26、cation,Local Replacemen)每进程分配一定数目的物理块。进程缺页时，只允许从该进程内存页中选出一页换出。若缺页中断频繁，再为该进程分配若干物理块，直至缺页率减少；若缺页率特低，则减少该进程的物理块数，应保证缺页率无明显增加。3.物理块分配算法 1)平均分配算法将所有可供分配的物理块，平均分配给各个进程。例如，有 100 个物理块，5 个进程，每进程可分 20 个物理块。未考虑到各进程本身的大小。2)按比例分配算法根据进程的大小按比例分配物理块。共 n 个进程，每进程页面数为si，则页面数的总和为：设可用的物理块为 m，每进程分到的物理块数为 bi，有：3)考虑优先权的分配算

27、法为了照顾重要、紧迫的作业尽快完成，为它分配较多的空间。通常采取：把可供分配的物理块分成两部分：一部分按比例分给各进程；另一部分根据优先权分给各进程。有的系统是完全按优先权来分配。4.7.3 调页策略 1.何时调入页面 1)预调页策略(缺页前)：页面存放连续，用预测法一次调入多个相邻页，预测成功率仅为 50。2)请求调页策略(缺页时)：运行中，发现不在内存，立即请求，由 OS 调入。2.从何处调入页面 请求分页系统中外存分为两部分：文件区和对换区。这样，当发生缺页请求时，系统应从何处将缺页调入内存：(1)系统拥有足够的对换区，可以全部从对换区调入所需页面。在进程运行前，须将有关的文件拷贝到对换

28、区。(2)系统缺少足够的对换区，这时凡是不会被修改的文件，都直接从文件区调入，由于它们未被修改而不必换出。但对于可能被修改的部分，换出时调到对换区，以后需要时，再从对换区调入。(3)UNIX 方式。凡是未运行过的页面，都应从文件区调入；曾运行过但已换出的页面，放在对换区，下次应从对换区调入。niiSS1mSSbii4.8 页面置换算法 当进程运行时，所访问的页面不在内存而需要将他们调入内存，但内存无空闲时，需要选择一页面换出到对换区，选择算法即页面置换算法。算法评价：页面置换频率低，调出页面将不会或很少访问。4.8.1 最佳置换算法和先进先出置换算法 1.最佳(Optimal)置换算法 由 B

29、elady 于 1966 年提出的一种理论上的算法。原理：其所选择的被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。特点：通常可获得最低的缺页率，但由于进程运行不可预知而无法实现，用来评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：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 予以淘汰。共发生 6 次页面置换。图 4-25 利用最佳页面置换算法时的置换图 2.先进先出(FIF

30、O)页面置换算法-总是置换最先进入内存的页面。用 FIFO 算法共发生 12 次页面置换。该算法与进程的实际运行规律不相符，有些页面经常被访问(全局变量，常用函数)。图 4-26 利用 FIFO 置换算法时的置换图 4.8.2 最近最久未使用(Least Recently Used LRU)置换算法 1.LRU 置换算法-在无法预测各页面将来使用情况下，利用“最近过去”作为“最近将来”的近似选择最近最久未使用的页面予以淘汰。用 LRU 算法共发生 9 次页面置换。引用率70770170122010320304243230321201201770101页框(物理块）203 图 4-27 LRU

31、页面置换算法 2.LRU 置换算法的硬件支持(*)LRU 算法比较好，但为了快速知道哪一页是最近最久未使用的页面，需要硬件支持：寄存器或栈。1)寄存器 为了记录某进程在内存中各页的使用情况，须为每个页面配置一个移位寄存器，可表示为：原理：进程访问某物理块时，先将寄存器的 Rn-1 位设成 1。此时，定时信号将每隔一定时间将寄存器右移一位。若将 n 位寄存器的数看做是一整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。例：某进程在内存中有 8 个页面，为每页面配置一 8 位寄存器时的 LRU 访问情况，如图 4-28 图 4-28 某进程具有 8 个页面时的 LRU 访问情

32、况 2)栈-利用栈来保存当前使用的各页面的页面号。原理：每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，6 随着进程的访问，栈中页面号的变化情况如图 4-29 所示。在访问页面 6 时发生了缺页，此时页面 4 是最近最久未被访问的页，应将它置换出去。LRU 算法较好，但 要求较多硬件支持，实际使用接近 LRU 算法Clock 算法。图 4-29 用栈保存当前使用页面时栈的变化情况 引用率70770170122010323104430230321013201770201页框23042042302301271270114474707407047170410174010741210742120741210742621076