操作系统第四章ppt课件.ppt

《操作系统第四章ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统第四章ppt课件.ppt（97页珍藏版）》请在三一办公上搜索。

1、第四章 存储器管理,第一节 存储器的层次结构 第二节 程序的装入和链接第三节 连续分配存储管理方式第四节 对换（Swapping）第五节 基本分页存储管理方式第六节 基本分段存储管理方式,序言,存储器：主存（内存）、副存（外存）内存进程、外存文件内存管理： 地址映射、内存分配与回收 存储保护、内存扩充(虚拟内存)外存管理： 文件管理,存储器的层次结构,计算机对存储器的要求：1.要求存储器的访问速度能跟上处理机的运行速度。2.要求存储器具有非常大的容量。3.要求存储器的价格便宜。基于以上三个要求，目前计算机系统都采用了多层结构的存储器系统。,多层结构存储器系统,1.存储器的多层结构通用计算机的存

2、储器具有3层结构：由低到高分别为：辅存、主存、CPU寄存器。高档计算机的存储器结构分为：寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。存储器的特点：层次越高，存储介质的访问速度越快，价格越高，容量越小。存储器管理系统负责管理内存，外存作为文件管理内容。2.可执行存储器指寄存器和主存储器特点：对可执行存储器访问速度快，对辅存的访问需要通过I/O设备，因此耗费的时间远高于可执行存储器，一般至少相差3个数量级。,主存储器与寄存器,主存储器_内存用于保存进程运行时的程序和数据，又称为可执行存储器。CPU一般从主存中取出指令和数据分别存放于CPU中的指令寄存器和数据寄存器中，反之

3、将寄存器数据存入主存中。主存早期容量为数10到数百KB，现在高达数10MB到数GB。但主存访问速度低，故引入了寄存器和高速缓存。寄存器寄存器的访问速度最快，与处理器运行速度相当，但价格非常昂贵，容量也很小。随着VLSI的发展，现在的微机系统中，寄存器数量已达到数10个到数百个。,高速缓存和磁盘缓存,1.高速缓存是现代计算机结构中的一个重要部件，介于寄存器和主存之间，用于备份主存中较常用的数据，以减少处理机对主存的访问次数，从而大幅提高程序执行速度。其容量远大于寄存器，从几10KB到几MB，其访问速度快于主存。特点：由于高速缓存的速度越高，价格越贵，故计算机系统会设置两个或多个高级缓存，一级缓存

4、紧靠内存，速度最快，容量最小。2.磁盘缓存由于主存的访问速度远高于磁盘的访问速度，为了缓和两者间速度差异，设置了磁盘缓存，用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。特点：与高速缓存不同，磁盘缓存不是一种实际存在的存储器，而是利用主存中的一部分存储空间暂时存放磁盘信息。一个文件数据可能会出现在不同层次的存储器中：辅存主存（磁盘缓存）,程序的装入和链接,用户提交的程序需要经过以下几个步骤才能被系统运行：1.编译2.链接3.装入,从源程序到程序执行,编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形

5、成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。,库,程序的装入,就是把链接好的装入模块装入“内存”。装入方式绝对装入：只适用单道程序环境；装入内存的位置是可知的、固定的，故采用绝对装入方式，按照装入模块中的地址，将程序和数据装入内存，由于程序的逻辑地址与物理地址一致，故地址无需修改。程序中所使用的物理地址一般设置为在编译、汇编时再给出，此前由符号地址代替。可重定位装入（静态重定位）：适用于多道程序环境，存在很多的用户程序编译所形成的若干个目标模块，它们的起始地址都是从0开始的逻辑地址，可通过重定位方式装入内存合

6、适的位置，但这会使装入模块的逻辑地址与实际装入内存后的物理地址不同，故需要对程序和数据的地址进行修改。动态运行时装入（动态重定位）：允许程序在运行时，在内存中移动位置。实际上，程序在内存中运行时，它在内存中的位置可能要经常改变。例如：在对换功能系统中，一个进程可能被多次换出，又多次换入。动态运行时装入程序：把装入模块装入内存后，并不立即把模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行。,重定位的概念,重定位概念：把程序装入内存时，修改程序中所有与地址有关的项。逻辑地址变换为物理地址。重定位的类型静态重定位：程序执行前，一次性，链接装入程序。动态重定位：处理机每次

7、访问主存时，有动态地址变换机构（硬件）自动执行。,链接方式,静态链接：程序在运行之前，先将目标模块及其所需库函数链接成一个完整的装配模块，以后不再拆开。这种事先进行链接的方式即为静态链接方式。（1）对相对地址进行修改，将目标模块的相对地址修改为相应的装入模块相对地址；（2）变换外部的调用符号，将每个模块中所用的外部调用符号也都变换为装入模块中的相对地址。,程序的链接,链接：把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体装入模块的过程。具体工作：对相对地址的修改；变换外部调用符号。,链接,目标模块使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的

8、。,长度,链接方式,装入时动态链接：在将目标模块装入内存时，边装入边链接的链接方式，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，同时修改目标模块中的相对地址。优点：（1）便于修改和更新，由于各目标模块是分开存放的，所以要修改 或更新各目标模块就很容易。（2）便于实现对目标模块的共享，在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享，但采用装入时动态链接的方式时，OS就很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。,链接方式,运行时动态链接：将对某些模块的链接推迟到程

9、序执行时才进行。亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块，并将之装入内存，将其链接到调用者模块上。优点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅能加快程序的装入过程，而且可节省大量的内存空间。,连续分配存储管理方式,连续分配方式：为用户程序分配一个连续的内存空间，即程序中代码的逻辑地址相邻体现在内存空间分配时，物理地址的相邻。曾被广泛应用，且现在仍被采用。单一连续分配固定分区分配动态分区分配动态可重定位分区分配,单一连续分配,单一连续分配的基本思想把内存分为系统区和用户区，系统区供OS使用，通常放在内存的低址部分；系

10、统区以外的全部内存空间是用户区，仅装有一道用户程序。单一连续分配的特点只能用于单用户、单任务的单道程序环境的OS中。软件简单，硬件要求低（可无需存储器保护措施）实例CP/M，MS-DOS，RT-11等单用户OS,固定分区分配,在多道程序环境中，为了防止装入内存中的多个程序间互相干扰，于是将整个内存用户空间划分为若干个固定大小的区域，将每个分区中只装入一道作业，即为固定分区分配。1.划分分区的方法（划分为若干个固定大小的分区）分区大小相等：缺乏灵活性：当程序太小会造成内存空间浪费，当程序太大又无法满足其运行。比较适用于一台计算机同时控制多个相同对象的场合。分区大小不相等：较上种方法灵活，通常将内

11、存划分为多个较小的分区、适量中等分区、少量大分区。2.内存分区分配分区使用表（MBT）：分区号、大小、分区起址、状态分区按内存空间大小排队当用户程序要装入时，由内存分配程序检索分区使用表，找到满足要求、尚未分配的分区，将之分配给它。,固定分区分配,分区使用表,动态分区分配,可变分区分配思想分区的位置和大小都不固定，应作业的要求而设置，为之动态分配内存空间。动态分区分配的数据结构的两种形式：空闲分区表（用于记录每个空闲分区）、空闲分区链：用于实现对空闲分区的分配和链接，在每个分区的头部、尾部分别设置了前向、后向指针，形成了双向链表。,分区大小,分区状态,分区分配流程图,分配内存分区大小与所需空间

12、大小“匹配”：M.Size - U.Size Size （不再分割的小分区的尺寸）剩余部分挂接到空闲分区链（表）上。,空闲状态分区,动态分区分配算法,首次适应算法FF要求：空闲分区链以地址递增的次序链接每次从链首开始顺序查找第一个大小能满足要求的空闲分区，然后划分，余下的空闲分区仍留在空闲链中优先利用地址部分，保留高址部分的大空闲区碎片较多，每次从低址查找要增加查找的开销,为了将一个新作业装入内存中，须按照一定的分配算法，从空闲分区表中选出一分区给该作业，接下来将介绍四种传统的顺序式搜索算法：,循环首次适应算法：对首次适应算法的演变，从上次找到的下一个空闲分区开始找要求：设置一个起始查找指针采

13、用循环查找方式内存中的空闲分区分布更均匀减少了查找空闲分区始的开销缺乏大的空闲分区,最佳适应算法要求：将所有的空闲分区按其容量从小到大的顺序形成一空闲分区链从链首开始查找第一个大小适合的空闲分区第一次找得的是最佳即最恰好适合的分区能够避免“大材小用”同时，空闲分区每次分配切割留下的剩余部分总是最小的，留下大量的难以利用的碎片回收操作较困难,最坏适应算法要求：将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链每次分配链首的第一个空闲分区每次利用是最大的分区，空闲分区每次分配切割留下的剩余部分总是最大的，避免留下大量的难以利用的碎片查询开销非常小但缺乏大空闲分区,动态分区分配算法,分配算法比较

14、几种算法各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。,例：有作业序列：作业A要求20K；作业B要求28K，作业C要求30K。要求画出系统中空闲区按照首次适应算法，最佳适应算法、最坏适应算法形成的三种空闲分区队列，然后分析哪种算法对该序列是合适的？经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。,练习有作业序列：作业A要求21K；作业B要

15、求25K，作业C要求30K，那种分配算法适合该作业序列？,动态分区分配算法,基于索引搜索的动态分区分配算法由于顺序搜索的动态分区分配算法比较适用于较小的系统。当系统很大时，为了提高搜索空闲分区的速度，采用基于索引搜索的动态分区分配算法：1.快速适应算法2.伙伴系统3.哈希算法,快速适应算法,又称为分类搜索算法，是将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头指针。该算法搜索空闲分区步骤：1.根据进程的长度，从索引表中找到能容纳它的最小空闲区

16、链表2.从链表中取下第一块进行分配即可。该算法不会对分区产生分割，因此不会产生碎片，查找效率高。缺点：为进程所分配的分区或多或少存在内存空间的浪费。,伙伴系统,该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂，通常整个可分配内存的大小为2的m次方。将它不断的划分，按照分区的大小进行分类，将相同大小的所有空闲分区，单独设立一个空闲分区双向链表，形成k个空闲分区链表。算法步骤：当需要为进程分配长度为n的存储空间：1.首先计算一个i值，使2i-1n=2i。2.然后若找到2i大小的空闲分区链表，则分配，否则将查找2i+1链表，若找到则把该分区分为两个相等的分区，这两个分区称为一对伙伴，其中一

17、个分区用于分配，而把另一个分区加入大小为2i的空闲分区链表中，以此类推2的i+2空闲分区链表的分配。,哈希算法,在上述分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找所需空间大小所对应的表项，来找到一个空闲分区。这里面临一个问题，如果空闲分区分类较细，则相应的索引表项较多，那么会显著增加搜索索引表的表项的时间开销。为了解决这个问题，提出了哈希算法。,哈希算法,哈希算法：利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为

18、关键字的哈希表，该表的每个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。,分区分配操作,回收内存回收区与插入点的前一个空闲分区相邻接回收区与插入点的后一个空闲分区相邻接；回收区与插入点的前后两个空闲分区相邻接；回收区不与任何一个空闲分区相邻接；,可重定位分区分配,动态重定位的引入随着系统接收的作业的增加，内存中连续的大块分区不复存在，产生了大量的“碎片”。新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。通过“拼接”/“紧凑”/“紧缩”/“

19、”澄清“来实现”程序的浮动“/” 动态重定位“。,紧凑,可重定位分区分配,动态重定位的实现由于动态运行时装入方式是将相对地址转换为绝对地址的工作推迟到程序指令要真正执行时进行，为使地址转换不影响到指令的执行速度，需要有硬件地址变换机构的支持，即需在系统中增设一个重定位寄存器，用它来存放程序在内存中的起始地址。程序运行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。动态重定位：地址变换过程是在程序执行期间，随着每条指令或数据的访问自动进行的，故称为。,优缺点分析优点：消除了“碎片”，提高了内存利用率，同时提高了系统效率。缺点：需要动态重定位“硬件”机构支持，增加了系统成本，并

20、轻度降低了程序执行速度，“紧凑”处理增加了系统开销。,可重定位分区分配算法,对换（Swapping）,早期，在单用户分时系统中出现的对换技术为：系统把所有的用户作业存放在磁盘上，每次只能调入一个作业进入内存，当该作业的一个时间片用完时，将它调至外存的后备队列上等待，再从后备队列上将另一个作业调入内存。多道环境下存在的问题：1.内存中大量的进程因事件未发生而被阻塞，但却占用了大量的内存空间。2.又存在许多的作业因内存空间的不足，一直驻留在外存上，而不能进入内存运行。这些都使得系统的吞吐量下降，造成了系统资源的浪费，为了解决这个问题，在系统中添加了对换设施。,对换技术,对换技术（Swapping）

21、:用于解决内存不足的问题，改善内存利用率，提高系统吞吐量。指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换的类型_根据每次对换时，所对换的程序或数据的数量，可将对换分为如下两类：如果对换是以整个进程为单位，便称之为“整体对换”或“进程对换”，广泛用于多道程序中，作为处理机中级调度。如果对换是以进程的一个“页面”或“分段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又称为“部分对换”。这种对换方法是实现后面将介绍的请求分页和请求分段式存储管理的基础，其目的是为支持虚拟存储系统。,进程

22、对换技术,进程对换技术（Swapping）对换的时机：创建新进程而内存不足时。对换空间的管理：外存分为文件区和对换区，前者存放文件，采用离散分配；后者存放换出的进程，采用连续分配，以提高进程换入、换出的对换速度。对换区空闲盘块管理中的数据结构：记录外存中对换区的空闲盘块的使用情况，使用空闲分区表包括对换区的首址及其大小分别用盘块号和盘块数表示。对换空间的分配与回收对换分区的分配：连续分配方式，因而对换空间的分配与回收与动态分区分配雷同。其分配算法可以是首次适应算法、循环首次适应算法、最佳适应算法。对换区的回收可分为：1.回收分区与插入点的前一个空闲分区F1相邻接；2.回收分区与插入点的后一个空

23、闲分区F2相邻接；3.回收分区同时与插入点的前、后两个分区邻接；4.回收分区既不与F1邻接，又不与F2邻接。,进程对换技术（Swapping）当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间时，便调用对换进程。进程的换出：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，申请对换空间，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上，并回收该进程占用的内存空间，修改该进程的PCB。进程的换入：找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将之换入，直至无可换入的进程或无可换出的进程或无足够内存换入进程为止，此时对换进程才停止。,第五节基本分页

24、存储管理方式,由于采用连续分配方式会形成很多的碎片，虽然可以使用紧凑方法改善但开销太大，于是促使人们产生了分散分配方式的思想（如果将一个进程直接分散地装入到许多不相邻接的分区中，便可充分地利用内存空间）。根据离散分配时，所分配地址空间的单位不同，可将离散分配分为三种：1. 分页存储管理方式。 2. 分段存储管理方式。 3. 段页式存储管理方式。页面与页表地址变换机构两级和多级页表基本分页的特点,页面与页表,页面页面：分页存储管理将进程的逻辑地址分成若干个页并且按照顺序编号。物理块：相应把内存的物理地址空间分为若干个块加以编号。页面大小：选择适当的页面大小一般为2n 范围：1KB 8KB分散分配

25、方法：将程序划分成多个页并且分别装入到多个可以不相邻接的物理块中。分页地址的地址结构（对特定机器固定）逻辑地址物理地址页内地址：0-11，即页面大小为4K,页号P：12-31,即地址空间1M个页若给定一个逻辑地址空间中的地址为A,页面大小为L,则页号和页内地址？页表数据结构：页号、块号、存取控制项页表的作用：实现从页号到物理块号的地址映射。,页面与页表,页面页面和物理块（页框/架）：顺序编号，页内碎片页面大小：2n Bytes 一般在：512B 8/32K地址结构逻辑地址物理地址页表数据结构：页号、块号、存取控制项页表的作用：实现从页号到物理块号的地址映射。,逻辑地址空间,地址变换机构,为了将

26、用户地址空间中的逻辑地址转换为内存空间中的物理地址，在系统中必须设置地址变换机构。将逻辑地址中的页号转变为内存中的物理块号，需借助于页表。,基本的地址变换机构页表存放在内存系统区的一个连续空间中；PCB和页表寄存器PTR中存有页表的首地址；查询页表：页表首地址+页号x表项长度；地址映射从逻辑地址到物理地址的变换过程。,具有快表的地址变换机构联想寄存器并行查询；空间大小： 几K到几百K ，部分表项（16512个）；快表与页表同时访问；地址映射过程。,分析：统计表明，从快表中找到所需页表项的机率达90以上。同时，考虑到快表的速度是内存速度的数倍或数十倍，那么相对于内存速度，访问页表的时间可以忽略不

27、计。也就是说页地址变换机构造成的速度损失达到了可接受的程度。,例：设页长为1K，程序地址字长为16位，用户程序空间和页表如图。,硬件能自动分离出页号和页内地址，但我们只能通过计算才能得到。,两级和多级页表,两级页表解决大页表占用大的连续存储空间的问题；将大页表进行分页，让每个页面大小与内存物理块大小相同（1024）然后按照离散分配的方式存放在不同的物理块中。此时也要再建立一个外层页表用于记录页表页面的物理块号。若地址空间为32位，页面大小为4K，一级页表有1MB的页表项，二级页表：外1KB页表，1KB项逻辑地址结构：外层页号（P1）+外层页内地址(P2)+页内地址(d)多级页表,基本分页的特点

28、,优点：存在页内碎片，但碎片相对较小，内存利用率较高；实现了离散分配，消除了程序浮动；便于存储访问控制，有利于代码共享。“可重入代码”纯代码：执行中不可改变。缺点：需要专门的硬件支持，尤其“快表”；内存访问的效率下降。不足：不能实现真正的共享，不支持动态链接。,第六节基本分段存储管理方式,基本分段管理思想的引入基本原理地址变换分段与分页的主要区别信息共享段页式存储管理方式,分段存储管理思想的引入,OS由单道向多道系统发展的同时，其存储管理方式便由单一连续分配发展到固定分区分配。为了能适应不同大小的用户程序要求，又从固定分区分配发展到动态分区分配。又为了提高内存的利用率，又从连续分配方式发展到离

29、散分配方式分页存储管理方式。为了满足用户在编程和使用上多方面的要求，又引入了分段存储管理方式，是当今所有存储管理方式的基础。,分段存储管理思想的引入,具体地说，分段存储管理方式符合用户和程序员如下多方面的需要：方便编程：用户将作业按逻辑分段，其中每个逻辑地址都是由段名（段号）和段内偏移量（段内地址）共同来决定，这不仅可以方便用户编程，也可以使程序非常直观： LOAD 1，A |D； STORE 1，B |C；将分段A中D单元内的值读入寄存器1。将寄存器1中的值存入B分段的C单元中。,分段存储管理思想的引入,信息共享：是以信息的逻辑单位（main函数、子函数、数据等逻辑关系）为基础，来实现对程序

30、和数据的共享。信息保护：同样以信息的逻辑单位为基础，根据逻辑有效和方便地实现信息保护功能；例如我们希望子函数A仅允许进程执行，不允许读写操作，只需在该段上标上只执行标志即可。但是在分页系统中，函数A可能要占几个页面，其中第一页和最后一页还会装有其他程序段的数据，这些数据又允许进程读写，这就很难实现对页面统一保护。,分段存储管理思想的引入,动态增长：分段存储管理方法能很好的应对数据段的动态增长。动态链接：针对目标模块运行时动态链接：系统只将真正要运行的目标程序装入内存，首先将主程序和需要用到的目标程序装入内存。这些目标程序和目标模块都是以逻辑段为单位的，所以分段存储管理方式非常适合动态链接。,分

31、段系统的基本原理,在分段存储管理方式中，作业的地址空间被划分为若干个段，每段定义了一组逻辑信息，每段都是从0开始编址，并采用一个连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因此各段长度不相等。分段系统中逻辑地址结构：二维地址（段号，段内地址） 31 16 15 0允许一个作业由64K个段，一个段的最大长度为64KB段表（段映射表）段号、段基地址（段在内存中的起址）、段长等段表寄存器：段表始址和段表长度利用段表实现逻辑段地址到物理地址的映射,基本原理,图. 利用段表实现地址映射,地址变换及变换机构,基本分段管理的地址变换与基本分页管理的变换机构和过程类似。段表寄存器存放段表的起始地址和

32、段表长度；越界访问控制逻辑地址的段号与段表长度比较；段内地址与段表中保存的段长比较；,分段与分页的主要区别,页是信息的物理单位，段是信息的逻辑单位，分页是系统管理的需要，分段是用户的需要；页的大小固定，由系统确定；段的大小动态变化，决定于用户编程的需要；分页系统中的逻辑地址空间是一维的，分段系统中的是二维的。分页系统中不易实现“共享”和“动态链接” ，分段则很容易。,信息共享,假设一个多用户系统，可同时接纳40个用户，每个用户都执行一个文本编辑程序。如果编辑程序包括160KB编辑代码区，40KB数据区，则需要约8MB内存空间，若160KB是可重入的，则该代码能被共享，故就只需（160+40*4

33、0）KB内存空间。在分页系统中，假定页面为4KB，则编辑代码段划分为40个页面，对应40个页表项，数据区划分为10个页面，对应10个页表项。,1.分页系统中对程序和数据的共享,信息共享,2.分段系统中程序和数据的共享,使实现共享变得非常容易,基本分段的特点,优点： 便于动态申请内存 管理和使用统一化 便于共享 便于动态链接缺点：产生碎片思考：与动态分区存储管理方案的相同点与不同点？,段页式存储管理方式,基本思想结合分页和分段技术；发挥出分页和分段管理方式各自的优点。原理对内存进行分页（物理块/页架）；对用户作业先分段，各段再分页。地址结构与地址变换段号、段内页号、页内地址三部分段表和页表,段号

34、，段内页号，页内地址,段页式存储管理的特点,段页式存储管理的优缺点同时具备分段和分页管理的优点：分散存储，内存利用率较高；便于代码或数据共享，支持动态链接等。访问效率下降：一次访问转换成了三次访问。1.访问内存中的段表，从中取得页表始址。2.访问内存中的页表，从中取出物理块号并与页内地址一起构成数据的物理地址。3.根据物理地址从内存中取出数据。通过在地址变换机构中增设一个高速缓冲寄存器来解决速度问题。,第五章虚拟存储器_页面置换算法,虚拟存储器的引入虚拟存储器的定义物理上不存在，但可以使用（访问）；允许作业部分装入，需要时再临时装入所需的部分，直到作业退出，某些部分也有可能没被装入过。虚拟存储

35、器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。,虚拟存储器的特征,离散性：离散存储多次性一个作业被分成多次调入内存运行；对换性允许在作业的运行过程中进行换进、换出；虚拟性能从逻辑上扩充内存容量，使用户“看到”的内存容量远大于实际大小。该特征是以上两个特征为基础的。,内存分配策略和分配算法,具体的物理块（页架）的分配策略固定分配局部置换：进程占据的内存页架数不变；缺页时，只能与该进程在内存的页面置换；由进程类型、程序员或程序管理员确定每个进程分得的物理块数但分配时，难于确定某个进程的页架数。,可变分配全局置换：最易实现，空闲页架由OS管理空闲物理块队列先为每个进

36、程分配一定的物理块缺页时，由系统从空闲物理块队列中取一块当空闲物理块完时，便与内存中的一页置换，该页可能是任一进程中的页,可变分配局部置换根据进程类型或程序员的要求，为每个进程先分配一定数目的物理块缺页时，只与该进程在内存的一页置换当进程缺页率较高或较低时，能由OS对其占据的页架数加以调整,内存分配策略和分配算法,物理块的分配算法平均分配算法将系统中所有可供分配的页架，平均分配给各个进程。按比例分配算法根据进程的大小按比例分配页架的算法。考虑优先权的分配算法优先权高的一次分得的页架数多。,调页策略,何时调入页面的问题预调页策略：通常运用于首次调入内存时 预先调入若干个预计在不久后将执行的页面

37、预测不准：约为50请求调页策略：进程运行中发生缺页现象时 每次仅调入一页，系统开销大，增加了磁盘I/O的启动频率,从何处调入页面的问题外存分为：“文件区” 和“对换区”系统有足够的对换空间：进程的所有文件都从文件区复制到对换区系统缺少足够对换空间：不被修改的文件始终直接从文件区调入；可能被修改的部分在换出时须调到对换区，以后需要时均从对换区调入UNIX方式：第一次运行到的页面都从文件区调入，被换出的页面放在对换区，下次调入就从对换区调入，对于已在内存的共享页面无须调入,页面的调入过程响应缺页中断保存CPU环境查找页表（快表） 得到该页在外存中的块号启动磁盘IO读入；如果内存已满，先置换，再调入

38、；最后修改页表（快表）对应项的内容。,第七节页面置换算法,最佳置换算法先进先出FIFO算法最近最久未使用（LRU）置换算法最少使用（LFU）置换算法页面缓冲置换算法,页面置换算法,在进程运行过程中，若其所要访问的页面不在内存，但内存已无空闲空间时，为保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。一个好的页面置换算法应具有较低的页面更换频率。,最佳置换（OPT）算法,选择以后永远（相比之下，最长时间）不会被使用的页淘汰出去。特点：理论上，性能最佳；实际上，无法实现；通常只用在研究

39、其它算法时，做参考评价。,例,假定系统未某进程分配了三个物理块号，有以下的页面号引用串（为了简便起见，假设采用的是最佳置换算法策略）,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,缺页中断9次，置换6次,先进先出FIFO,选择最先进入系统的页淘汰出去特点：实现简单与进程实际的运行不相适应,例,假定系统未某进程分配了三个物理块号，有以下的页面号引用串（为了简便起见，假设采用的是FIFO先进先出置换策略）,页的位置不表示页的真实存储地址，仅为了表示即将淘汰页的方便,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,缺页15次，置换12

40、次,最近最久未使用（LRU）置换算法,选择最近最久未被使用（访问）的页淘汰出去。特点：性能较好，实现复杂，需要硬件支持（每页配置一个寄存器、栈），增加系统负担。,LRU的硬件支持,寄存器系统为每页设置一个移位寄存器R，每当访问这一页时，将该页对应的寄存器R最高位置1，以后每个时间间隔将所有的R右移一位，当淘汰一页时就选择R值最小的页。也就是说R值越小，其对应的页就是最久未使用的页。显然，R的位数越多越精确。但系统硬件成本也就越高。,栈设置一个特殊的栈保存当前使用的各个页面的页面号；当一个页面被访问时，首先检查栈中是否有与刚压入栈顶的页号相同的，若有，则从栈中抽出；最后就将它的页号压入栈顶。这样

41、可保证栈中无相同的页号。当系统要淘汰一页时，总是从栈底取出一个页号淘汰，即淘汰的页是最久未使用的。,例,假定系统为某进程分配了三个物理块号，有以下的页面号引用串（为了简便起见，假设采用的是最近最久未使用LRU策略）,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,栈,缺页12次，置换9次,例,某程序在内存中分配三个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分别计算缺页次数，置换次数？假设开始时所有页均不在内存,FIFO,4 ，3， 2，1，4，3， 5，4，3， 2， 1，5,缺页9次，置换6次,LRU,4

42、 ，3， 2，1，4，3， 5，4，3， 2， 1，5,缺页10次，置换7次,OPT,4 ，3， 2，1，4，3， 5，4，3， 2， 1，5,缺页7次，置换4次,练习,某程序在内存中分配4个块，访问页的顺序为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别计算缺页次数，置换次数？假设开始时所有页均不在内存,LRU,4，3，2，1，4，3，5，4，3，2，1，5,缺页中断8次,OPT,4，3，2，1，4，3，5，4，3，2，1，5,缺页中断6次,FIFO置换算法的异常,有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为

43、4 3 2 1 4 3 5 4 3 2 1 5(1)该进程运行时总共出现几次缺页。(2)若每个进程在内存有4块，又将产生几次缺页。,M=3,4 ，3， 2，1，4，3， 5，4，3， 2， 1，5,缺页9次，置换6次,M=4,4，3，2，1，4，3，5，4，3，2，1，5,缺页10次，置换6次,FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加,影响缺页次数的因素,分配给进程的物理块数页面的大小编程方法页面置换算法,例,内存分配一物理块，初始时矩阵数据均不在内存；页面大小为128个整数；矩阵A128X128按行存放。下面两个程序执行时访

44、问数据将分别会产生多少次缺页中断？,程序1：for j:=1 to 128 for i:=1 to 128 Ai,j:=0;,程序2：for i:=1 to 128 for j:=1 to 128 Ai,j:=0;,128*128,128,最少使用（LFU）置换算法,选择在最近时期使用最少的页面淘汰。需要为内存中的每个页架设置一个移位寄存器，用来记录该页面被访问的频率。每次访问某页时，便将该移位寄存器的最高位置1，此后每隔一定时间自动右移一位。类似LRU,页面缓冲置换算法PBA,消除频繁的磁盘I/O空闲页面链表，不需写回磁盘，装入新页面时，在该表中选择一个页架。已修改页面链表，该链表中的页面数

45、达到一定数目时，才集中写回到磁盘上。,第八节请求分段存储管理方式,以基本分段内存管理为基础，程序运行前，只需先调入部分分段，便启动执行。其它分段在需要时，通过缺段中断处理程序临时调入。请求分段中的硬件支持请求分段中的分段共享请求分段中的分段保护,请求分段中的硬件支持,请求段表机制段号（名）、段长、段的基址、外存始址增加：存取方式：标识存取属性只读、只执行、读/写访问字段A：记录该段被访问得频度，提供给置换算法选择换出页面时参考修改位M：表示该页在进入内存后是否被修改过存在位P：指示本段是否已调入内存增补位：本段在运行过程中是否做过动态增长,缺段中断机构以信息分段为单位操作。由于分段不定长，处理

46、较缺页中断复杂。,N,地址变换机构在基本分段系统地址变换机构的基础上形成，增加了分段不在内存时的缺段中断请，若分段不在内存中，必先将所缺段调入内存，然后利用段表进行地址变换。,请求分段中的分段共享,分段存储管理方式便于实现分段的共享和保护，为了实现分段的共享还应配置相应的数据结构共享段表。共享段表记录了共享段的段名/号、段长、内存始址、存在位、外存始址、共享进程计数器记录了共享此分段的各进程信息：进程名/号、段号、存取控制（P187）共享段的分配与回收共享段的分配共享段的回收,请求分段中的分段共享,共享段分配在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再

47、把共享段调入该区，同时将该区的始址填入到请求进程的段表的相应项中，还须在共享段表中增加一表项，填写请求使用该共享段的进程名、段号和存取控制等有关数据，把count置为1，当有其它进程需要调用该共享段时，无需再为该段分配内存，需执行count=count+1操作等。共享段回收当共享此段的某进程不再需要该段时，应将该段释放，撤销在该进程段表中共享段所对应的表项，执行count-1操作，若结果为0，表示此时已没有进程使用该段，则须由系统回收该共享段的物理内存。,请求分段中的分段保护,越界检查段表寄存器：段表始址、段表长度段号段表长度、段长段内地址存取控制检查存取控制字段（访问方式）只读、只执行、读/

48、写环保护机构P188可以访问驻留在相同环或较低特权环中的数据；可以调用驻留在相同环或较高特权环中的服务。,课堂作业（综合）,1、某程序在内存中分配3块内存，初始为空，访问页的走向为2，3，2，1，5，2，4，5，3，2，5，2，用FIFO和LRU算法分别计算缺页次数,2、有一页式系统，其页表存放在主存中。(1)如果对主存的一次存取要3us，问实现一次页面访问要多长时间。(2)如系统有快表，平均命中率为97%，假设访问快表的时间忽略为0，问此时一次页面访问平均要多长时间。,3、在分页存储管理系统（16位）中，有一作业大小为4页，页面大小为2K，页表如下：试借助地址变换图（即要求画出地址变换图）求出逻辑地址4635所对应的物理地址。,