操作系统讲义第四章存储器管理精选PPT.ppt

操作系统讲义第四章存储器管理操作系统讲义第四章存储器管理2023/1/12第四章 存储器管理1第1页，此课件共56页哦主要内容主要内容 4.1 存储器管理的层次结构存储器管理的层次结构 4.2 程序的装入和链接程序的装入和链接 4.3 连续分配方式连续分配方式 4.4 基本分页存储管理方式基本分页存储管理方式 4.5 基本分段存储管理方式基本分段存储管理方式 4.6 虚拟存储器的基本概念虚拟存储器的基本概念 4.7 请求分页存储管理方式请求分页存储管理方式 4.8 页面置换算法页面置换算法 4.9 请求分段存储管理方式请求分段存储管理方式第2页，此课件共56页哦存储器管理概述存储器管理概述 存储器是计算机系统的重要组成部分，随着计算机技存储器是计算机系统的重要组成部分，随着计算机技术的发展，系统软件和应用软件在种类、功能及其所需存术的发展，系统软件和应用软件在种类、功能及其所需存储空间等方面，都在急剧地膨胀，虽然存储器的容量也不储空间等方面，都在急剧地膨胀，虽然存储器的容量也不断扩大，但是仍不能满足现在软件发展的需要，它仍然是断扩大，但是仍不能满足现在软件发展的需要，它仍然是一种紧俏的资源，所以如何有效地管理存储器，不仅影响一种紧俏的资源，所以如何有效地管理存储器，不仅影响到存储器的利用率，而且还对系统性能有重大的影响。到存储器的利用率，而且还对系统性能有重大的影响。存储器管理的主要对象：内存内存。第3页，此课件共56页哦存储器管理概述存储器管理概述p有的作业很大，所要求的内存空间超过内存总容量，有的作业很大，所要求的内存空间超过内存总容量，作业不能全部装入，致使该作业无法运行；作业不能全部装入，致使该作业无法运行；p有大量作业要求运行，但内存不足以容纳所有的作业，只有大量作业要求运行，但内存不足以容纳所有的作业，只能让少数作业装入内存先运行，而将大量作业留在外存等能让少数作业装入内存先运行，而将大量作业留在外存等待。待。显而易见，一种解决办法就是从物理上增加内存的容量，显而易见，一种解决办法就是从物理上增加内存的容量，另一种方法就是从逻辑上扩充内存的容量，也就是利用虚另一种方法就是从逻辑上扩充内存的容量，也就是利用虚拟存储技术解决。拟存储技术解决。如果某存储器管理方式要求一个作业全部装入内存才能够运行，那么就会出现两种情况：第4页，此课件共56页哦4.1 存储器管理的层次结构存储器管理的层次结构速度非常快，能跟上处理机的速度速度非常快，能跟上处理机的速度容量非常大，能容纳所有要运行的作业容量非常大，能容纳所有要运行的作业价格很便宜，不需要花费额外的钱价格很便宜，不需要花费额外的钱 存储器的理想状态：存储器的理想状态：1.多级存储结构多级存储结构 计算机存储层次至少应具有三级：CPU寄存器，主存，辅存。注意注意：存储层次越往上，存储介质的访问速度越快，价格也：存储层次越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。越高，相对存储容量也越小。可移动存储介质可移动存储介质磁盘磁盘磁盘缓存磁盘缓存主存主存高速缓存高速缓存寄存器寄存器CPU存储器主存辅存第5页，此课件共56页哦4.1 存储器管理的层次存储器管理的层次2.主存储器和寄存器主存储器和寄存器p主存储器（简称内存或主存）：主存储器（简称内存或主存）：计算机的主要部件，用于保存进程运行时的程序和数据，可称为可执行存储器；微机和大中型机：数十MB到数GB；嵌入式计算机：数十KB到几MB；CPU和外围设备交换信息的依托；访问速度远低于CPU执行指令的速度。第6页，此课件共56页哦4.1 存储器管理的层次存储器管理的层次2.主存储器和寄存器主存储器和寄存器p寄存器：寄存器：能够与CPU协调工作的计算机部件；微机和大中型机：数十到上百个Word；嵌入式计算机：几个到几十个Word；访问速度快；价格十分昂贵；容量很小。第7页，此课件共56页哦4.1 存储器的层次结构存储器的层次结构3.高速缓存和磁盘缓存高速缓存和磁盘缓存p高速缓存：高速缓存：是计算机中的一个重要部件，其容量大于或远大于寄存器，而比内存小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器；（1）程序执行的局部性原理；（2）速度越高价格越贵，计算机系统中经常设置两级或多级高速缓存；（3）紧靠内存的一级高速缓存速度最高，容量最小，二级缓存容量稍大，速度也稍低。第8页，此课件共56页哦4.1 存储器的层次结构存储器的层次结构3.高速缓存和磁盘缓存高速缓存和磁盘缓存p磁盘缓存：磁盘缓存：并不是实际的存储介质，依托于固定磁盘，提供对主存储器存储空间的扩充。（1）磁盘的I/O速度远低于主存的访问速度；（2）主存也可以看做是辅存的高速缓存；（3）大容量的辅存常常使用磁盘，磁盘数据经常备份到磁带或者可移动的磁盘中，以防止硬盘故障时丢失数据。第9页，此课件共56页哦4.2 程序的装入和链接程序的装入和链接 一个用户源程序要变成一个可在内存中执行的程序都要经过以一个用户源程序要变成一个可在内存中执行的程序都要经过以下几个步骤：下几个步骤：编译：将用户源代码编译成目标代码；编译：将用户源代码编译成目标代码；链接：将目标模块及它们所需要的库函数链接在一起；链接：将目标模块及它们所需要的库函数链接在一起；装入：将装入模块装入内存。装入：将装入模块装入内存。库库链接链接程序程序编译编译程序程序产生产生的目的目标模标模块块装入模块装入模块装入装入程序程序内存内存第一步第一步第二步第二步第三步第三步第10页，此课件共56页哦4.2 程序的装入和链接程序的装入和链接绝对装入方式（绝对装入方式（Absolute Loading Mode）编译时，知道程序所驻留内存的具体位置，编译程序将产生绝对地址的目标代码，这个绝对地址可以在编译或者汇编时给出，也可由程序员赋予。1.程序的装入程序的装入p可重定位装入方式（可重定位装入方式（Relocation Loading Mode）多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存何处，所以目标模块的起始地址通常从0开始，而程序中的其他地址则相对于起始地址计算而成。第11页，此课件共56页哦4.2 程序的装入和链接程序的装入和链接 1.程序的装入程序的装入p动态运行时装入方式（动态运行时装入方式（Dynamic Run-time Loading Mode）装入程序把装入模块装入内存，并不立即把相对地址转换为绝对地址，而是把地址转换推迟到程序真正运行时再执行。0LOAD 1,2500100025005000365LOAD 1,250036510000110001250015000第12页，此课件共56页哦4.2程序的装入和链接程序的装入和链接 2.程序的链接程序的链接p静态链接方式（静态链接方式（Static Linking Mode）(1)对相对地址进行修改；（2）变换外部调用符号模块ACALL B；Return；0L-1模块BCALL C；Return；0M-1模块C Return；0N-1模块ACALL B；Return；0L-1模块BCALL C；Return；L+M-1模块C Return；L+M+N-1LL+M第13页，此课件共56页哦4.2程序的装入和链接程序的装入和链接 2.程序的链接程序的链接p装入时动态链接方式（装入时动态链接方式（Load-time Dynamic Linking Mode）用户源程序编译后所得的目标模块，在装入内存时边装入边链接的，这种方式（1）便于修改和更新（2）便于实现对目标模块的共享。p运行时动态链接方式（运行时动态链接方式（Run-time Dynamic Linking Mode）许多情况下，应用程序每次要运行的模块可能不相同，如果把所有模块都装入非常低效，所以要在运行过程中动态装入所需模块。第14页，此课件共56页哦4.3 连续分配方式连续分配方式 这是一种最简单的存储管理方式，只能用与单用户单任务的操作系统，内存分成系统区和用户区，系统区提供给OS使用，而用户区指除了系统区以外的全部内存空间，提供给用户使用。1.单一连续分配单一连续分配 这是一种最简单的可运行多道程序的存储管理方式，它将内存划为固定大小的区域，每个分区装入一道作业。2.固定分区分配固定分区分配第15页，此课件共56页哦4.3 连续分配方式连续分配方式 2.固定分区分配固定分区分配p分区的划分方法分区大小相等：所有分区大小相等，缺点是缺乏灵活性，程序太小时空间浪费，程序太大时无法运行；分区大小不等：克服了大小相等而缺乏灵活性的缺点，把内存分成多个较小的分区、适量的中等分区及少量的大分区。p内存分配：将分区按照大小进行排队，并为之建立一张分区使用表，其各表项包括每个分区的起始地址、大小以及状态。第16页，此课件共56页哦4.3 连续分配方式连续分配方式 3.动态分区分配动态分区分配p分区分配中的数据结构分区分配中的数据结构空闲分区表；空闲分区链。p分区分配算法分区分配算法首次适应算法：首次适应算法：找到第一个大小能满足要求的空闲空间；循环首次适应算法：循环首次适应算法：从上次找到的空闲分区的下一个开始查找，找到一个能满足要求的空闲分区；最佳适应算法：最佳适应算法：找到一个满足要求、又是最小的空闲分区分配给作业；最坏适应算法：最坏适应算法：挑选一个最大的空闲分区分割给作业；快速适应算法：快速适应算法：将空闲分区根据其容量大小分类，然后根据进程的长度，寻找到能容纳它的最小空闲分区链表，取下第一块进行分配。第17页，此课件共56页哦4.3 连续分配方式连续分配方式分区分配操作分区分配操作 1）分配内存：分配内存：系统利用某种分配算法，从空闲分区链（表）中找系统利用某种分配算法，从空闲分区链（表）中找到所需大小的分区。到所需大小的分区。从头开始查表检索完否？m.sizeu.size？m.size-u.sizesize？从该分区中划出u.Size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN第18页，此课件共56页哦4.3 连续分配方式连续分配方式分区分配操作分区分配操作 2）回收内存：回收内存：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链（表）中找到相应的插入点。a）回收区与插入点的前一个空闲分区F1相邻接，将回收区与插入点前的分区合并，不必为回收分区分配表项，修改前一分区F1的大小；b）回收区与插入点的后一空闲分区F2相邻接，此时可将两分区合并，形成新的空闲分区，回收区的首址作为新空闲区的首址，大小为两者之和;F1回收区回收区F2(a)(b)第19页，此课件共56页哦4.3 连续分配方式连续分配方式分区分配操作分区分配操作 2）回收内存回收内存 c）回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和首址，取消F2表项，大小为三者之和；d）回收区既不与F1邻接，又不与F2邻接，这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据首址插入到空闲链中的适当位置；F1回收区回收区F2(c)(d)第20页，此课件共56页哦4.3 连续分配方式连续分配方式固定分区方式的不足：固定分区方式的不足：限制了活动进程的数目，当进程大小和空闲分区大小不匹配时，空间利用率很低。动态分区方式的不足：动态分区方式的不足：算法复杂，回收空闲分区时需要进行分区合并等，系统开销大。伙伴系统：伙伴系统：上面两种内存方式的一种折衷，伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，lkm，其中 是分配的最小分区的大小，表示分配的最大分区的大小，通常 是整个可分配内存的大小。4.伙伴系统伙伴系统伙伴系统的优点：算法在回收空闲分区时，需要对空闲分区进行合并，伙伴系统的优点：算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面分类搜索算法差，但比顺序搜索算法好，而其空所以其时间性能比前面分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。第21页，此课件共56页哦4.3 连续分配方式连续分配方式哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表。5.哈希算法哈希算法 6.可重定位分区分配可重定位分区分配p动态可重定位：动态可重定位：它的引入是为了解决系统中只有若干个小分区，即使它们容量之和大于要装入的程序，但由于这些分区不相邻接，无法装入该程序的情况。第22页，此课件共56页哦4.3 连续分配方式连续分配方式 6.可重定位分区分配可重定位分区分配操作系统用户程序110KB用户程序330KB用户程序614KB用户程序926KB操作系统用户程序1用户程序3用户程序6用户程序980KB采用的方法：采用的方法：将内存中的所有作业进行移动，使它们全部相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可以把作业装入该区。定义：通过移动内存中作业的位置，把原来多个分散的小分区定义：通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法，称为拼接成一个大分区的方法，称为“拼接拼接”或或“紧凑紧凑”。第23页，此课件共56页哦4.3 连续分配方式连续分配方式 6.可重定位分区分配可重定位分区分配p动态可重定位的实现：动态可重定位的实现：作业装入内存后的所有地址仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时运行。LOAD 1,250036550002500 100 0作业作业J250010000相对地址重定位寄存器+LOAD 1,25003651500012500 1010010000主存主存第24页，此课件共56页哦4.3 连续分配方式连续分配方式 6.可重定位分区分配可重定位分区分配p动态重定位分区分配算法：动态重定位分区分配算法：类似于动态分区分配算法，不过是在算法中增加了紧凑功能，通常在找不到足够大的空闲分区来满足用户需求时进行紧凑。请求分配u.size分区检索空闲分区链（表）找到大于u.size的可用分区否？按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size？无法分配返回紧凑形成连续空闲区修改有关的数据结构否是是否第25页，此课件共56页哦4.3 连续分配方式连续分配方式 7.对换（对换（Swapping）对换的引入的原因：对换的引入的原因：多道程序环境下，内存中的一些进程因某事件而被阻塞运行，却占用大量内存空间，甚至可能所有进程阻塞而迫使CPU停止下来等待的情况；另一方面，许多作业在外存上等待，因无内存而不能运行。p对换的定义：对换的定义：是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出内存上，以便腾出足够的内存空间，再把具备运行条件的进程或进程所需的程序和数据调入内存。第26页，此课件共56页哦4.3 连续分配方式连续分配方式 7.对换（对换（Swapping）p对换空间的管理：对换空间的管理：通常把外存分为文件区和对换区，其中文件区用于存放文件，对换区用于存放从内存换出的进程。p进程的换出与换入进程的换出与换入进程的换出：进程的换出：首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将进程的程序和数据传送到磁盘的对换区上；进程的换入：进程的换入：系统应定时地查看所有进程的状态，找出“就绪”状态但已经换出的进程，将其中换出时间最久的进程作为换入进程，将之换入，直至已无可换入和无可换出进程为止。第27页，此课件共56页哦4.4 基本分页存储管理方式基本分页存储管理方式页面 1）页面和物理块）页面和物理块，适用于批处理系统或者实时性要求不高的系统；2）页面大小）页面大小，能更好地满足紧迫作业，适合于严格的实时系统或者对性能要求较高的批处理和分时系统中。1.页面和页表页面和页表p地址结构：分页地址中的地址结构包括两部分：前一部分是页号P，后一部分为位移量W（或称为页内地址）。位移量W页号P3112110p页表：在分页系统中，允许各个页离散地存储在内存不同的物理块内，但系统要保证进程的正确执行，所以系统又为每个进程建立了一张页面映射表。若给定一个逻辑地址空间中的地址为若给定一个逻辑地址空间中的地址为A，页面的大小为，页面的大小为L，则页号，则页号P和页和页内地址内地址d可按下式求得：可按下式求得：第28页，此课件共56页哦4.4 基本分页存储管理方式基本分页存储管理方式基本的地址变换机构基本的地址变换机构 2.地址变换机构地址变换机构页表长度页表首址当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址（相对地址）分为页号和页内地址两部分，再以页号为索引去检索页表。页表寄存器+页内地址页号（3）逻辑地址L1 b 页表物理地址块号页号0123越界中断第29页，此课件共56页哦4.4 基本分页存储管理方式基本分页存储管理方式具有快表的地址变换机构具有快表的地址变换机构 2.地址变换机构地址变换机构页表长度页表首址在CPU给出有效地址后，由地址变换机构自动将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若找到匹配的页号，就表示要访问的页表项在快表中。页表寄存器+页内地址页号逻辑地址Lb 页表db物理地址块号页号越界中断输入寄存器b 快表块号页号 第30页，此课件共56页哦4.4 基本分页存储管理方式基本分页存储管理方式两级页表两级页表 3.两级和多级页表两级和多级页表P2P1对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，可以支持2的64次方（1884744TB）规模的物理存储空间，一般可以利用三级页表结构来实现。外部页号+页表db物理地址 外部页表 d外部页表寄存器+外部页内地址页内地址逻辑地址p多级页表多级页表第31页，此课件共56页哦4.5 基本分段存储管理方式基本分段存储管理方式方便编程方便编程 通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0开始编址，并且有自己的名字和长度。1.分段存储管理方式的引入分段存储管理方式的引入p信息共享信息共享 在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分页系统中的“页”只是存放信息的物理块，并无完整的意义，不便于实现共享，而段却是信息的逻辑单位。p信息保护信息保护 信息保护同样是对信息的逻辑单位进行保护，因此，分段管理方式能更有效和方便地实现信息保护功能。p动态增长动态增长 实际应用中，往往有些段，特别是数据段，在使用过程中会不断增长，而事先无法确切地知道数据段会增长到多大，这时候其他存储管理方式无法解决这个问题。p动态链接动态链接 在作业运行之前，并不把几个目标程序段链接起来，而是在运行过程中需要调用某段时，才将该段调入内存进行链接。第32页，此课件共56页哦4.5 基本分段存储管理方式基本分段存储管理方式分段分段 在这里，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如出程序段MAIN、子程序段X、数据段D和栈段S等。2.分段系统的基本原理分段系统的基本原理p段表段表 在分段式存储管理系统中，为每个分段分配一个连续的分区，而进程中的每个段可以离散地移入内存中不同的分区中，像分页系统一样，在系统中为每个进程建立一张映射表，称为“段表”。作业空间作业空间（MAIN）=0030K（X）=1020K（D）=2015K（S）=3010K30K20K15K10K40K80K120K150K段段 表表段号 段长 基址0123（MAIN）=030K（X）=120K（D）=215K（S）=310K内存空间内存空间40K80K120K150K第33页，此课件共56页哦4.5 基本分段存储管理方式基本分段存储管理方式分段系统的地址变换过程分段系统的地址变换过程 在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。在进行地址变换时，将逻辑地址中的段号和段表长度TL进行比较。若STL，表示段号太大，访问越界，产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，进而将该段基址d与段内地址相加，得到要访问的内存物理地址。2.分段系统的基本原理分段系统的基本原理段表长度段表长度段表首址段表首址控制寄存器控制寄存器+1002 段号段号S 位移量位移量W主存主存越界中断越界中断6K4K 8K 9200基址基址段长段长1K600500200段号段号0123+82928K82928692第34页，此课件共56页哦4.5 基本分段存储管理方式基本分段存储管理方式分段和分页的主要区别分段和分页的主要区别 分段和分页都采用离散分配方式，且都要通过地址映射机构来实现地址变换，这是它们的相似之处，但是在概念上两者完全不同，主要表现在：2.分段系统的基本原理分段系统的基本原理分页分页分段分段目的提高内存的利用率更好地满足用户需求形式信息的物理单位信息的逻辑单位大小页的大小固定且由系统决定段的长度不固定，由用户编写的程序决定地址空间一维，单一的线性空间二维，包括段名和段内地址 3.信息共享信息共享分段系统的优点：允许多个进程共享一个或多个分段。可重入代码可重入代码是一种允许多个进程同时访问的代码，不允许可重入代码在执行中有任何改变。第35页，此课件共56页哦4.5 基本分段存储管理方式基本分段存储管理方式基本原理：是分段和分页原理的结合，即先将用户程序分成若干个段，基本原理：是分段和分页原理的结合，即先将用户程序分成若干个段，然后再把每个段分成若干个页，并为每个段赋予一个段名。然后再把每个段分成若干个页，并为每个段赋予一个段名。4.段页式存储管理方式段页式存储管理方式段表始址段表大小段表寄存器主存段号状态页表大小页表始址0111213041页号状态存储块#0111213041页表操作系统第36页，此课件共56页哦4.5 基本分段存储管理方式基本分段存储管理方式地址变换过程地址变换过程 4.段页式存储管理方式段页式存储管理方式段表长度段表首址段表寄存器+页号P段号S段超长页表始址页表长度段表0123+页内地址块内地址块号bb页表0123第37页，此课件共56页哦4.6 虚拟存储器的基本概念虚拟存储器的基本概念常规存储器管理方式的特征常规存储器管理方式的特征一次性：作业在运行前要一次性装入内存；驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。1.虚拟存储器的引入虚拟存储器的引入p局部性原理局部性原理 1968年Denning.P指出：程序在执行时将呈现出局部性规律，即在较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域，他提出几个论点：（1）除了少部分转移和过程调用指令，程序大多数情况下是顺序执行的；（2）过程调用会让程序的执行由一部分区域移至另一部分区域；（3）程序中存在许多循环结构，虽然由少数指令构成，但是要多次执行；（4）程序中许多对数据结构（如数组）的操作，往往局限于很小的范围内。第38页，此课件共56页哦4.6 虚拟存储器的基本概念虚拟存储器的基本概念 1.虚拟存储器的引入虚拟存储器的引入p局限性表现局限性表现时间局限性：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行，数据访问也是类似；空间局限性：一旦程序访问了某个存储单元，不久以后，其附近的存储单元也将被访问，即程序某一段时间访问的地址可能集中在一定范围内。p虚拟存储器的定义：是指具有请求调入功能和置换功能，能从逻辑上对内存容虚拟存储器的定义：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。量加以扩充的一种存储器系统。2.虚拟存储器的特征虚拟存储器的特征（1）多次性）多次性 （2）对换性）对换性 （3）虚拟性）虚拟性第39页，此课件共56页哦4.6 虚拟存储器的基本概念虚拟存储器的基本概念 虚拟存储器中，允许将一个作业分多次调入内存，它的实现毫无例外地建立在离散分配的存储管理方式的基础上。（1）请求分页系统）请求分页系统 在基本分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。硬件支持包括(a)请求分页的页表机制(b)缺页中断机构(c)地址变换机构；软件支持：包括用于请求调页的软件和实现页面置换的软件。（2）请求分段系统）请求分段系统 在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。硬件支持包括(a)请求分段的段表机制(b)缺段中断机构(c)地址变换机构软件支持：包括用于请求调段的软件和实现段面置换的软件。3.虚拟存储器的实现方法虚拟存储器的实现方法第40页，此课件共56页哦4.7 请求分页存储管理方式请求分页存储管理方式页表机制页表机制 在请求分页系统中所需要的主要数据结构是页表，其基本作用是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。1.请求分页中的硬件支持请求分页中的硬件支持p缺页中断机构缺页中断机构 当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存，它和一般中断的区别主要表现在：（1）在指令执行期间产生和处理中断信号；（2）一条指令在执行期间，可能产生多次缺页中断。（1）状态位P：标识本段的存取属性是只执行，只读，还是允许读/写;（2）访问字段A：用于记录该段被访问的频繁程度；（3）修改位M：用于表示该页进入内存后是否被修改过；（4）外存始址：指示本段在外存中的起始地址，即起始盘块号。页号物理块号访问字段A修改位M状态位P外存始址第41页，此课件共56页哦4.7 请求分页存储管理方式请求分页存储管理方式 1.请求分页中的硬件支持请求分页中的硬件支持p地址变换机构地址变换机构 开始页号页表长度？CPU检索快表否是访问页表页表项在快表中？页在内存？修改快表修改访问位和修改位形成物理地址地址变换结束保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回内存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表越界中断否是否是是否是产生缺页中断请求调页程序请求访问一页第42页，此课件共56页哦4.7 请求分页存储管理方式请求分页存储管理方式 2.内存分配策略和分配算法内存分配策略和分配算法p最小物理块数的确定最小物理块数的确定 最小物理块数是只能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。p物理块的分配策略物理块的分配策略 1）固定分配局部置换：）固定分配局部置换：为每个进程分配一定数目的物理块，在整个运行期间不再改变；2）可变分配全局置换：）可变分配全局置换：为每个进程分配一定数目的物理块，OS自身也保持一个空闲物理块队列，用于分配给缺页进程；3）可变分配局部置换：）可变分配局部置换：为每个进程分配一定数目的物理块，当缺页时，只允许该进程从内存的页面中选出一页换出，这样不会影响其他进程。第43页，此课件共56页哦4.7 请求分页存储管理方式请求分页存储管理方式 2.内存分配策略和分配算法内存分配策略和分配算法p物理块的分配算法物理块的分配算法 1）平均分配法：平均分配法：将系统中所有可供分配的物理块平均分配给各个进程；2）按比例分配法：按比例分配法：按照进程的大小按比例分配物理块；3）考虑优先级的分配法：考虑优先级的分配法：通常把内存中可供分配的物理块分成两部分，一部分按比例分配给各进程，另一部分则根据各进程的优先级，适当增加其份额，分配给各进程。3.调页策略调页策略p调入页面的时机调入页面的时机 1）预调页策略 2）请求调页策略第44页，此课件共56页哦4.7 请求分页存储管理方式请求分页存储管理方式 3.调页策略调页策略p确定从何处调入页面确定从何处调入页面 请求分页系统中的外存分成两部分：文件区（用于存放文件）和对换区（用户存放对换页面），缺页请求调页时分下列三种情况：1）系统拥有足够的兑换空间，此时可全部从兑换区调入所需页面；2）系统缺少足够的对换区空间，此时不会被修改的文件从文件区调入；3）UNIX方式：凡是未运行过的页面都应从文件区调入，曾经运行过的页面都从对换区调入。p页面调入过程页面调入过程 当程序要访问的页面未在内存时，便向CPU发出缺页中断，中断处理程序会保留CPU环境，分析中断原因并转入中断处理程序，在外村中找到缺页的物理块，如果内存能容纳，则将之调入，否则根据算法选择一页换出，并修改相应的数据结构。第45页，此课件共56页哦4.8 页面置换算法页面置换算法 1.先进先出（先进先出（FIFO）页面置换算法）页面置换算法最早出现的置换算法，总是淘汰最先进入内存的页面。2.最佳（最佳（Optimal）页面置换算法）页面置换算法1966年由Belady提出的，选择的被淘汰的页面都是以后永不使用或者在最长（未来）时间内。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 123 12304304204230230130127127027017 70 70 120 1缺页次数为缺页次数为15次，缺页率次，缺页率:15/20=75%7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 70 70 120 120 3243203201701缺页次数为缺页次数为9次，次，缺页率缺页率:9/20=45%第46页，此课件共56页哦4.8 页面置换算法页面置换算法 3.最近最久未使用（最近最久未使用（LRU）页面置换算法）页面置换算法p地址变换机构地址变换机构 LRU算法选择最近最久未使用的页面予以淘汰。pLRU的硬件支持的硬件支持 1）寄存器：为了记录某个进程在内存中各页的使用情况，需要为每个内存中的页面设置一个寄存器。2）栈：每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。20 34034024320321321021077 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 70 70 120 1缺页次数为缺页次数为12次，缺页率次，缺页率:12/20=60%4.其他页面置换算法其他页面置换算法最少使用置换算法和页面缓冲算法。第47页，此课件共56页哦4.9 请求分段存储管理方式请求分段存储管理方式 1.请求分段中的硬件支持请求分段中的硬件支持p段表机制段表机制 请求分段式管理中所需的主要数据结构是段表。段表项中，除了段名（号）、段长、段在内存中的起始地址外，增加了：（1）存取方式：标识本段的存取属性是只执行，只读，还是允许读/写;（2）访问字段A：用于记录该段被访问的频繁程度；（3）修改位M：用于表示该页进入内存后是否被修改过；（4）存在位P：指示本段是否已调入内存；（5）增补位：用于表示本段在运行过程中是否做过动态增长；（6）外存始址：指示本段在外存中的起始地址，即起始盘块号。段名段名段的段的基址基址段长段长存取存取方式方式访问访问字段字段A修改修改位位M存在存在位位P增补位增补位外存外存始址始址第48页，此课件共56页哦4.9 请求分段存储管理方式请求分段存储管理方式 1.请求分段中的硬件支持请求分段中的硬件支持p缺段中断机构缺段中断机构 在请求分段系统中，当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生缺段中断信号，进入OS后由缺段中断处理程序将所需的段调入内存。虚段S不在内存内存中有合适的空闲区吗？修改段表及内存空区链唤醒请求进程返 回阻塞请求进程淘汰一个或几个实段，以形成一个合适空区空区拼接，以形成一个合适的空区是否否是空区容量总和能满足要求？从外存读入段S第49页，此课件共56页哦4.9 请求分段存储管理方式请求分段存储管理方式 1.请求分段中的硬件支持请求分段中的硬件支持p地址变换机构地址变换机构 请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的，地址变幻时，如果要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能利用段表进行地址变换。访问sww段长？符合存取方式？段S在主存？修改访问字段，如写访问，置修改位=1形成访问主存地址(A)=(主存地址)+(位移量w)返 回分段越界中断处理分段保护中断处理缺段中断处理是否否否是是第50页，此课件共56页哦4.9 请求分段存储管理方式请求分段存储管理方式 2.分段的共享与保护分段的共享与保护p共享段表：为了实现分段共享，可在系统中配置一张共享段表，所有共享共享段表：为了实现分段共享，可在系统中配置一张共享段表，所有共享段都在共享段表中占有一表项。段都在共享段表中占有一表项。.共享段表共享段表段名段名段长段长段长段长内存始址内存始址外存始址外存始址状态状态进程名进程名段号段号进程号进程号存取控制存取控制共享进程计数共享进程计数count p共享进程计数共享进程计数count：为了记录有多少个进程需要共享该分段；p存取控制字段：存取控制字段：为了给不同的进程设置不同的存取权限；p段号：段号：不同的进程可以用不同的段号去共享该段。第51页，此课件共56页哦4.9 请求分段存储管理方式请求分段存储管理方式 2.分段的共享与保护分段的共享与保护p共享段的分配与回收共享段的分配与回收共享段的分配：共享段的分配：共享段内存的分配方法与非共享段的不同，对请求共享段的进程，要系统首先分配一物理区，再把共享段调入，将该区首址填入进程的段表，还须在共享段表中添加一表项，把count置1。共享段的回收：共享段的回收：某进程不需要共享段时，先将段释放，撤销进程段表中共享段的表项，执行count=count-1操作，如果count=0，则系统回收该共享段。第52页，此课件共56页哦4.9 请求分段存储管理方式请求分段存储管理方式 2.分段的共享与保护分段的共享与保护p分段保护分段保护越界检查：越界检查：段表寄存器中存放段表的长度信息，段表中为每个段也设置了段长字段，逻辑地址如果超过段表或者段长，会引发地址越界中断。存取控制检查：存取控制检查：段表中的“存取控制”字段，规定对该段的访问方式：（1）只读；（2）只执行；（3）读/写。环保护机构：环保护机构：功能较完善的保护机制，该机制中，地编号的环具有高优先级。OS核心存在于0环内，某些重要的实用程序和操作系统居于中间环，一般的应用程序安排在外环。一个程序可以访问驻留在相同环或较低特权环中的数据；一个程序可以调用驻留在相同环或较高特权环中的服务。第53页，此课件共56页哦本章小结本章小结1.本章的概念本章的概念 存储器的层次结构存储器的层次结构 动态分区分配算法动态分区分配算法 动态重定位分区分配算法动态重定位分区分配算法 分页系统的地址变换机构和具有快表的地址变换机构分页系统的地址变换机构和具有快表的地址变换机构 分段系统的地址变换过程分段系统的地址变换过程 分页和分段的主要区别分页和分段的主要区别 局部性原理和虚拟存储器的特征局部性原理和虚拟存储器的特征 页面置换算法页面置换算法 请求分页和分段的地址变换过程请求分页和分段的地址变换过程2.本章的重点和难点本章的重点和难点紧凑、对换、页面、快表、虚拟存储器。紧凑、对换、页面、快表、虚拟存储器。第54页，此课件共56页哦本章作业本章作业1.假设有一批作业假设有一批作业A、B、C、D、E、F，它们的大小分别为，它们的大小分别为7KB、18KB、9KB、20KB、35KB、8KB，根据不同的算法把它们分配到如下空闲分区表中。，根据不同的算法把它们分配到如下空闲分区表中。1）首次适应算法首次适应算法3）最佳适应算法最佳适应算法2）循环首次适应算法循环首次适应算法4）最坏适应算法最坏适应算法16KB16KB8KB32KB64KB32KB8KB16KB64KB 第55页，此课件共56页哦本章作业本章作业2.假设物理块数假设物理块数M=3，有一个作业的页面走向为，有一个作业的页面走向为1）采用先进先出采用先进先出FIFO页面置换算法，计算访问过程中所发生的缺页次页面置换算法，计算访问过程中所发生的缺页次数和缺页率；数和缺页率；4、3、2、1、4、3、5、4、3、2、1、5、6、2、