《操作系统内存》ppt课件

1、5、内存内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式存储器的多层构造多层构造存储器系统产生的缘由：无法同时满足三个条件：存储器的速度与处置机的速度相匹配由于许多指令涉及存储器访问存储器具有非常大的容量存储器的价钱很廉价存储器的层次构造存储器的层次构造存放器、高速缓存：少量的、非常快速、昂贵、易变；高速缓存是介于存放器和存储器之间的存储器主存储器：GB级、中等速度、中等价钱、易变磁盘缓存：依托于固定磁盘，提供对主存储器存储空间的扩展存放器和主存包括高速缓存、主存储器、磁

2、盘缓存又被称为可执行存储器磁盘、可挪动存储介质：GB级到PB级、低速、价廉、不易变内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式对用户程序的处置步骤绝对装入方式程序中的逻辑地址和实践内存地址一致适用于仅能运转单道程序的小系统程序中的绝对地址可由程序员直接给出要求熟习内存运用数据构造或程序修正后能够要改程序中的很多处地址绝对地址也可由程序编译器转换得出静态重定位装入方式程序中的逻辑地址从0地址开场适用于多道程序环境地址转换在程序装入时一次完成，不再改动动态重定位装入方式静

3、态装入不适用于进程切换，每次换入的内存位置能够不同程序装入时保管相对地址，程序执行时进展地址转换需求重定位存放器加速地址转换程序的静态链接方式在程序运转之前，先将各目的模块及它们所需的库函数，链接成一个完好的装配模块，以后不再拆开。程序的静态链接方式修正各模块的起始地址修正模块中一切涉及相对地址的指令程序装入时的动态链接方式程序编译后所得到的一组目的模块，装入目的模块时，假设发生外部模块调用，装入程序将外部模块调入内存，同时修正目的模块中的相对地址。优点： 便于修正和更新：由于各目的模块是分开存放的。 便于实现对目的模块的共享：OS很容易将一个目的模块，链接到几个运用模块上，实现多个运用程序对

4、该模块的共享。 程序运转时的动态链接方式某些模块有时不需求运转，如异常处置模块。需求用到的模块才进展链接。优点： 加快程序的装入过程：凡在执行过程中未被用到的目的模块，都不会被调入内存和被链接到装入模块上。节省内存空间：仅装入运转所需求的模块。 内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式延续分配存储管理方式延续分配指为一个程序分配一个延续的内存空间。延续分配方式分为四类：单一延续分配固定分区分配动态分区分配动态重定位分区分配单一延续分配单道程序环境下内存分为系统区和

5、用户区系统区仅提供应OS运用，在内存的低址部分用户区仅装有一道用户程序，即整个内存的用户空间由该程序独占缺陷：不支持多道 主存利用率不高 程序的运转受主存容量限制 固定分区分配多道程序环境下整个用户空间划分为假设干个固定大小的区域每个分区中只装入一道作业固定分区分配划分分区的方法分区大小相等：一切的内存分区大小相等，缺陷是缺乏灵敏性. 分区大小不等：存储器分区划分为假设干个大小不等的分区. 固定分区分配内存分配建立分区运用表，记录每个分区的起始地址、大小及形状能否已分配。当用户程序装入时，由内存分配程序根据程序大小检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表

6、项中的形状置为“已分配。 假设未找到大小足够的分区，那么回绝为该用户程序分配内存。 假设每个分区的大小固定，会呵斥存储空间浪费。 固定分区分配动态分区分配根据进程的实践需求动态分配内存空间动态分区分配中的数据构造 动态分区分配算法 分区分配操作动态分区分配动态分区分配中的数据构造 空闲分区表或空闲分区链动态分区分配动态分区分配算法传统的顺序式搜索算法索引式搜索算法动态分区分配分区分配操作分配内存：根据分配算法，从空闲分区表中找到适宜的分区。假设分区大小比恳求空间大超越分区最小极限值，那么对分区进展分割。回收内存：当进程运转终了释放内存时，系统根据回收区的首地址，合并回收进空闲分区表回收区与插入

7、点的前一个空闲分区F1相邻接回收分区与插入点的后一空闲分区F2相邻接回收区同时与插入点的前、后两个分区邻接回收区既不与F1邻接，又不与F2邻接基于顺序搜索的分区分配算法为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。顺序搜索，是指依次搜索空闲分区链上的空闲分区，寻觅一个大小能满足要求的分区。 初次顺应算法：选择分区时总是按地址从高到低搜索。循环初次顺应算法：类似初次顺应法每次分区时，总是从上次查找终了的地方开场。最正确顺应算法：在空闲块表中找到一个不小于恳求的最小空块进展分配 最坏顺应算法：在空闲块表中找到一个不小于恳求的最大空块进展分配基于索引搜索的分区分配算法当系统很大时，系统

8、中的内存分区能够会很多，相应的空闲分区链就能够很长，这时采用顺序搜索分区方法能够会很慢。 快速顺应算法：一样容量的分区运用一个空闲分区链表，一切链表的头指针经过一张管理索引表访问。根据进程长度从索引表中找到适宜的空闲分区链表从链表中取第一块分区进展分配，不对分区进展分割时间性能比顺序搜索高，空间利用存在浪费基于索引搜索的分区分配算法同伴系统：初始内存是一个大小为2m的空闲分区，分区可以对半分割，分区大小均为2 的k次幂。假设恳求长度为n的内存空间2i-1i，那么把空闲块分为2j-1、2j-2、2i、2i的块，并把其中2i的块分配给进程。假设回收大小为2i的空闲块，要查询能否存在另一个大小为2i

9、的空闲块，假设有那么需合并成2i+1的空闲块。时间性能高于顺序搜索，低于快速顺应算法。空间利用率优于快速顺应算法，低于顺序搜索。多处置机系统中广泛运用。基于索引搜索的分区分配算法哈希算法：改良上述两种索引搜索方法。缘由：“根据恳求空间查找对应的空闲分区链表表头指针这个操作当表项多时速度慢算法先构造一张以空闲分区大小为关键字的哈希表，再根据所需空闲分区大小，经过哈希函数计算，得到在哈希表中的位置，从而得到呼应的空闲分区链表。可重定位分区分配延续分配方式的特点：一个程序必需装入一片延续的内存空间。当计算机运转一段时间后，内存空间将会分割成许多小分区，缺乏大的空闲空间。装入大作业的方法：挪动内存中的

10、一切作业使之相邻。这样把原来分散的多个小分区拼接成一个大分区，就可把大作业装入。 技术需求：紧凑、动态重定位、动态重定位分区分配算法 可重定位分区分配紧凑可重定位分区分配动态重定位可重定位分区分配 前往分区号和首地址动态重定位分区分配算法 内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式对换又称为交换技术，在内存和外存间交换数据，用于处理内存太小的问题。早期的分时系统中的对换技术：一切的用户作业放在磁盘上，每次调一个作业进内存，当时间片用完后再调至外存的后备队列，再从后备

11、队列中调另一个作业进内存。已废弃。多道程序环境多道程序环境：内存中的某些进程由于某事件尚未发生而被阻塞运转，但占用大量内存空间，甚至能够出现内存中一切进程都被阻塞。某些进程因内存空间缺乏，不断不能运转把内存中暂时不能运转的进程或者暂时不用的程序和数据换出到外存上；再把已具备运转条件的进程或进程所需求的程序和数据换入内存。 对换的类型 整体对换：即处置机中级调度。以进程为对换单位。页面分段对换 ：以进程的 “页面或“分段为单位进展对换。为实现进程对换，系统必需实现的功能: 对换空间管理进程的换出进程的换入对换空间管理在具有对换功能的OS中，通常把硬盘空间分为文件区和对换区两部分。文件区占大部分，

12、访问频率低。交换区占小部分，用于存放内存中换出的进程。对换空间管理的主要目的：文件区管理的主要目的：首先是提高文件存储空间的利用率，然后才是提高对文件的访问速度对换空间管理的主要目的：是提高进程换入和换出的速度，然后才是提高文件存储空间的利用率.对换空间管理对换区空闲盘块管理中的数据构造与内存在动态分区分配方式中所用数据构造类似，即同样可以用空闲分区表或空闲分区链。在空闲分区表的每个表目中，应包含两项：对换区的首址及其大小，分别用盘块号和盘块数表示。对换空间管理对换空间的分配与回收由于对换分区的分配采用的是延续分配方式，因此对换空间的分配与回收，与动态分区方式时的内存分配与回收方法雷同。分配算

13、法可以是初次顺应算法、循环初次顺应算法或最正确顺应算法等.进程的换出选择被换出的进程 首先选择处于阻塞形状或睡眠形状的进程其次选择优先级最低的进程 进程换出过程 恳求对换空间。假设恳求胜利就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。假设传送过程未出现错误，那么回收进程所占用的内存空间，并对进程控制块和内存分配表等数据构造做相应的修正。假设内存中还有阻塞进程，那么继续执行换出过程。进程的换入 对换进程将定时执行换入操作查看PCB集合中一切进程的形状，为“就绪已换出且换出时间最久的进程恳求内存；假设恳求胜利，那么将进程调入内存；假设失败，那么需先将内存中的某些进程换出，腾出足够的内存空间

14、后，再将进程调入。假设还有可换入的进程，那么继续执行换入过程，直到再无“就绪且换出形状的进程，或已无足够的内存来换入进程。内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式离散存储管理方式延续分配的存储管理方式 存在碎片问题。运用“紧凑技术可以处理这个问题，但时间代价较高。离散分配：给一个进程分配许多不相邻的分区。离散分配的类型分页：内存空间分成固定大小的物理块frame，如1KB 。用户程序的地址空间分为同样大小的区域，称为页。从0开场编制页号，页内地址是相对于0编址。分

15、段：用户程序分成大小不同的段，每段定义一组相对完好的信息。存储器分配以段为单位。段页式：目前的主流方式，具有两者的优点。分页存储管理的根本方法页：用户程序的地址空间，分为假设干个固定大小的区域，称为“页物理块：内存空间分为假设干个物理块或页框，页和块的大小一样页面大小 ：小的页面可以减少内存碎片，添加进程的页表长度，占用大量内存，降低页面换进换出的效率。大的页面可以减少页表长度，提高页面换进换出的效率，添加页内碎片。 建议的大小：4KB或8KB分页存储管理的根本方法地址构造31 12 11 0对某特定机器，其地址构造是一定的。假设给定一个逻辑地址空间中的地址为A，页面的大小为L，那么页号P和页

16、内地址d可按下式求得： (/) PINT A LdA MOD L页号P位移量W操作系统的内存寻址才干操作系统操作系统内存寻址内存寻址普通32位Windows3GB运用PAE技术的32位Windows2003Standard：32GBEnterprise：64GB64位WindowsXPEdition：128GB64位Windows2021Standard：32GBEnterprise：2TB64位Windows7/Vista旗舰版：192GB64位操作系统实际值264B1T=240分页存储管理的根本方法页表列出了作业的逻辑地址与其在主存中的物理地址间的对应关系。一个页表中包含假设干个表目，表目

17、的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。页表的每一个表目除了包含指向页框的指针外，还包括一个存取控制字段。分页存储管理的根本方法根本的地址变换机构分页存储管理的根本方法具有快表的地址变换机构两级页表对于32位的分页系统，设页面大小为4KB，那么每个进程的页表中，最多可以有1M个页表项，占1MB延续内存空间。可采用两个方法来处理这一问题：采用离散分配方式来处理难以找到一块延续的大内存空间的问题只将当前需求的部分页表项调入内存，其他的页表项仍驻留在磁盘上，需求时再调入两级页表两级页表构造两级页表假设要减少页表占用的内存空间，仅把当前需求的一批列表调入内存。两级列表下，外

18、层列表调入内存，页表只需调入几页，外层列表添加形状位S，0表示页表不在内存，需求的情况下产生中断并将页表调入内存。多级页表64位计算机假设按两级列表，那么外层页号占用42位，需求占用16384G延续内存空间。运用多级页表将外层页表再次分页，将各页离散地装入到不相邻的物理块中，再利用二级外层页表映射关系。64位计算机即使运用三级页表也不适宜，目前寻址的存储器空间减少为45位。哈希页表虚拟地址中的虚拟页码经过哈希函数转换到哈希表中。把虚拟页码和链表中每一个元素的第一个域作比较，假设匹配，那么第二个域作为物理地址的页码。哈希页表反向页表通常情况，每个进程都有一张页表，需求占用很多内存空间。反向页表对

19、于每个物理内存页只需一个条目，包含了保管在内存页中的虚拟页码和所属进程号。64MB的机器，假设页面大小为4KB，那么反置页表只占用64KB空间。针对查询速度慢的问题，可以运用哈希表和快表加速。反向页表内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式分段式存储管理在分页存储系统中，作业的地址空间是一维线性的，这破坏了程序内部天然的逻辑构造，呵斥共享、维护困难。引入分段存储管理方式， 主要是为了满足用户和程序员的下述需求：方便编程信息共享 信息维护动态增长 动态链接 分段系统

20、的根本原理分段地址中的地址具有如下构造：段表段号段内地址31 16 15 0段号012段首址段长度58K20K100K110K260K140K分段系统的根本原理分段管理中作业与段表、存储空间的关系分段系统的根本原理地址变换机构分页和分段的区别页是信息的物理单位，与操作系统管理有关，与用户无关。段是信息的逻辑单位，包含程序中相对完好的信息。每个系统中页的大小固定且由系统决议，由硬件直接实现。段的长度不固定，决议于每个程序，通常由编译程序根据源程序信息划分。信息共享分页和分段系统都能实现信息共享，即多个进程共享一个或多个分段。一个多用户系统，同时接纳40个用户，他们都执行一个文本编辑程序Text

21、Editor。文本编辑程序包含160KB的代码和40KB的数据区。假设160KB的代码是可重入的，那么只需1760KB内存。分页系统中的共享分段系统中的共享段页式存储管理方式分页系统以页面作为内存分配的根本单位，能有效提高内存利用率分段系统是以段作为内存分配的根本单位，能更好地满足用户需求段页式存储管理方式既具有分段系统的便于实现、分段可共享、易于维护、可动态链接等一系列优点，又能像分页系统那样，很好地处理内存的外部碎片问题。地址映射地址变换过程内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务

22、集恳求分段存储管理方式常规存储器管理方式的特征一次性：作业必需全部装入内存后才干开场运转。这一特征导致了：当作业要求的内存空间超越内存总容量，会导致该作业无法运转当大量作业要求运转时，由于每次只能装入少量作业，导致多道程序度下降。驻留性：作业被装入内存后，不断驻留在内存中，直至作业运转终了。部分性原理大多数情况下除转移和过程调用，程序顺序执行。过程调用将会使程序的执行轨迹，由一部分区域转至另一部分区域。程序中存在许多循环构造，这些虽然只由少数指令构成，但是它们将多次执行。程序中包括许多对数据构造的处置，如对数组进展操作，它们往往都局限于很小的范围内。部分性原理的表现时间部分性：程序中的某条指令

23、被执行，不久以后能够再次执行；某数据被访问，不久以后能够再次被访问。空间部分性：程序访问某个存储单元，不久之后附近的存储单元也将被访问。即程序在一段时间内所访问的地址，能够集中在一定的范围之内。虚拟存储器的根本任务情况程序运转前，仅须将当前需求的少数页面或段装入内存，其他部分暂留在硬盘上。程序运转时，假设需求的页段尚未调入内存称为缺页或缺段，就发出中断恳求，把页段调入内存。假设内存已满，先利用页段的置换功能，将内存中暂时不用的页段调至硬盘上，再将要访问的页段调入内存。虚拟存储器的定义具有恳求调入功能和置换功能，能从逻辑上对内存容量加以扩展的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决

24、议，其运转速度接近于内存速度，而每位的本钱却又接近于外存。虚拟存储器的特征多次性：程序和数据分多次调入内存对换性：暂不运用的程序和数据换出内存虚拟性：逻辑上扩展内存容量虚拟存储器的实现方法恳求分页系统用户程序只需装入少数页面即可运转，经过调页功能及页面置换功能把即将要运转的页面调入内存，把暂不运转的页面换到外存中恳求分段系统 类似恳求分页系统，置换以段为单位。由于段的长度可变，故实现比恳求分页系统难。Intel80386以上CPU芯片支持段页式虚拟存储器系统。内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算

25、法“抖动与任务集恳求分段存储管理方式硬件支持恳求页表机制形状位P：1bit，用于指示该页能否已调入内存访问字段A：记录本页在一段时间内被访问的次数，或本页最近已有多长时间未被访问修正位M：标识该页在调入内存后能否被修正外存地址：用于指出该页在外存上的地址，通常是物理块号页号页号物理块号物理块号形状位形状位P P访问字段访问字段A A修正位修正位M M外存地址外存地址硬件支持缺页中断机构在指令执行期间，假设恳求的页面不在内存时触发缺页中断一条指令在执行期间，能够产生多次缺页中断硬件支持地址变换机构内存分配最小物理块数确实定进程多时，进程在内存中能分配到的物理块少，缺页率上升，会降低进程的执行速度

26、。最小物理块数：能保证进程正常运转所需的最小物理块数。每条指令需求的物理块数与指令的复杂程度有关。直接寻址MOV AX,2000H2块存放器间接寻址 MOV EAX, EBX3块内存分配内存分配战略进程分配的物理进程分配的物理块数量块数量缺页时的置换战缺页时的置换战略略固定分配部分置换固定与本进程的页面交换可变分配全局置换可变与空闲块和一切进程页面交换可变分配部分置换可变与本进程的页面交换，假设频繁缺页那么添加物理块内存分配物理块分配算法平均分配算法按比例分配算法：根据进程的大小思索优先权的分配算法：内存物理块一部分按比例分配，另一部分根据进程优先权分配页面调入战略页面调入时机预调页战略：将要

27、访问的页面预先调入内存。假设命中率高目前只需50%，那么一次预调多页的效率高于恳求调页战略。恳求调页战略：需求的页面调入内存。一次调入一页，主流选择。页面调入战略页面调入过程保管CPU环境。假设内存足够，将缺页调入内存，并修正页表。假设内存已满，那么按照某种置换算法，从内存中选出待换页，假设该页修正位为1，那么写回磁盘。再把缺页调入内存，并修正存在位为1，将页表项写入快表。缺页调入内存后，即可经过页表读取其在内存中的物理地址。页面的调入过程对用户透明。内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动

28、与任务集恳求分段存储管理方式最正确置换算法实际算法，最低的缺页率。无法实现。换出的页面是以后永不运用的， 或者是在最长时间内不再被访问的页面。先进先出置换算法FIFO换出的页面在内存中驻留时间最长最近最久未运用算法LRU换出的页面是最后一次访问时间间隔当前时间最长的一页。需求用硬件来实现最久未运用页的搜索。实践效果比较好。LRU置换算法的硬件支持方法一：存放器为内存中的每个页面配置移位存放器，把n位存放器上的数看成一个整数，定期右移，置换数值最小的存放器对应的页。LRU置换算法的硬件支持方法二：栈堆栈中保管最近访问的页号。当进程访问某页时，把该页号从栈中取出，放在栈顶。需求换出时，取栈底的页面

29、。Clock置换算法LRU算法需求硬件支持，本钱较高Clock算法是LRU的近似算法，又称为最近未用算法NRU, Not Recently Used算法原理：内存中一切页面以指针相连每个页面都有一位访问标志进程访问页面那么把页面的访问标志置为1选择换出页面时，按指针顺序访问，假设为0那么换出，假设为1那么置为0。Clock置换算法改良的Clock置换算法思索换出本钱：假设换出页面已被修正，那么需写回磁盘。优先换出未运用过且未修正正的页面。页面包含访问位A和修正位M。交换优先级：(0,0)(0,1)(1,0)(1,1)改良的Clock置换算法算法步骤：根据指针顺序寻觅A=0且M=0的页面，将满足

30、条件的第一个页面作为淘汰页。假设未找到适宜页面，那么重新开场寻觅A=0且M=1的页面，将满足条件的第一个页面作为淘汰页，将一切扫描过页面的访问位都置0。假设未找到适宜页面，那么跳转至1。页面缓冲影响页面置换开销的要素：页面置换算法：降低缺页率写回磁盘的频率：需求写回的页面暂存在已修正换出页面链表中，积累到一定数量后一同写磁盘已修正换出页面的重新利用：处于已修正换出页面链表的页面假设再次访问，可直接从链表中读取内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式抖动景象系统同时

31、运转太多进程时，分配给每个进程的物理块太少，运转时频繁缺页，导致进程大多数时间用于页面切换，处置机利用率趋于0。这种景象称为颠簸或抖动。任务集进程发生缺页率的时间间隔，与进程获得的物理块数有关。任务集基于程序运转时的部分性原理，程序在一段时间内会局限于访问较少的一些页面，这些页面被称为活泼页面。任务集w(t, )指进程在时间间隔(t-, t)中援用页面的集合。( , )( ,1)w tw t 抖动的预防方法进程缺页时，只能与本进程的页面切换。利用任务集，在处置机调入新进程前，检测内存页面能否够用。“L=S准那么：L是两次缺页事件之间的平均时间，S是平均缺页效力时间，L=S时，存储器和处置机都可

32、达较高利用率。暂停优先级低的进程、大进程或者执行时间长的进程。内存存储器的层次构造程序的装入和链接延续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述恳求分页存储管理方式页面置换算法“抖动与任务集恳求分段存储管理方式恳求分段存储管理以分段为单位进展换入换出程序只需求调入几个分段即可运转当访问段不在内存中时，可恳求系统将缺的段调入内存恳求分段中的硬件支持恳求段表机制存取方式：运用程序中段是信息的逻辑单位，可根据信息的属性实施维护，如只执行、只读、允许读/写访问字段A：记录该段被访问的频繁程度，供置换页面时参考修正位M：记录该段进入内存后能否被修正，供置换页面时参考存在位P：记录该段能否已调入内存，供程序访问时参考增补位：表示该段在运转过程中能否动态增长外存始址：表示该段在外存中的起始地址，即起始盘块号段名段名段长段长段的段的基址基址存取存取