第5章 存储管理.ppt

,DOS,Windows9X,WindowsNT,Linux,UNIX,WindowsCE,第5章存储管理,本课程内容,第一章绪论第二章操作系统用户界面第三章进程管理第四章处理机调度第五章存储管理第七章文件系统第八章设备管理,5.1存储管理的功能,一存储器1存储器的层次结构在现代计算机系统中，存储器是信息处理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。,高速缓存Cache：少量的、非常快速、昂贵、易变的内存RAM：若干兆字节、中等速度、中等价格、易变的磁盘：数百兆或数千兆字节、低速、价廉、不易变的由操作系统协调这些存储器的使用,存储器,主存（内部存储器，磁芯存储器）,辅存（外存）磁盘、磁鼓、磁带、软盘,主存,系统区（OS标准子程序）,用户区（用户程序、数据）,2主存储器的物理组织，多级存储器,高速缓存,主存,外存,7,二.主存的分区共享,（一）主存共享特征主存如何？装入一片连续的内存区域。即空间分片。大小不等的区域分区存储管理分段存储管理大小相等的片页式存储管理两者结合段页式存储管理如何表示数据的地址？,8,（二）基本概念1.逻辑地址(程序地址、相对地址、虚地址)用户程序中的地址(指令地址或操作数地址)均为逻辑地址。2.逻辑空间(程序空间、作业的地址空间)用户程序中所有的逻辑地址的集合对应的空间。,9,3.物理地址(绝对地址、实地址)物理地址是计算机主存单元的真实地址，又称绝对地址或实地址。4.物理空间（主存空间）物理地址的集合所对应的空间组成了主存空间。,5.区域由一组连续、递增的物理地址：n，n+1，nm所对应的、主存空间的一个子集。,10,1.地址的变换（映射）；2.主存分配；3.存储保护；4.主存扩充。,三.主存管理功能,11,（一）地址变换（映射）1.为什么要进行地址变换当进程在处理机上运行时，程序中所要访问的指令或数据的逻辑地址，通常与主存空间中的实际地址是不同的。这种情况可用图来说明。,12,2.什么是地址变换将程序空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址变换。.地址变换的方式(1)在程序中使用物理地址在程序编写或程序编译时完成虚、实地址间的变换。,优点：访问速度快缺点：程序只能在确定机器的确定装入点运行。在多道环境无法实现。为什么？,Movr1,1500,13,(2)静态地址变换在作业装入过程中随即进行的地址变换，称为静态重定位或静态地址变换。,优点：访问速度快；可在任意装入点和其他机器上运行。缺点：装入后不能在机器内浮动。,14,(3)动态地址变换在程序执行期间，随着每条指令和数据的访问，自动地进行地址变换。,优点：程序在内存可移动，可动态增加内存；程序可放在多个不连续的内存区域,且可仅装入部分程序运行；便于多进程共享同一个程序的副本。,15,3.静态地址变换与动态地址变换的区别静态地址变换动态地址变换在作业装入过程中在程序执行期间进行地址变换进行地址变换需软件需硬件地址变换机构重定位装入程序重定位寄存器地址变换不灵活地址变换灵活程序不能换出换入程序能换出换入地址访问快地址访问慢,16,（二）主存扩充1.问题的提出从计算机一出现，主存的容量就显得十分紧张，表现：用户程序的空间主存空间某个用户程序的空间主存空间如何使用户程序在一个较小的主存空间上执行呢？,2.解决问题的思路例：在进行编辑时，只有在屏幕的窗口中才能进行编辑，因此可将窗口看作是一个编辑器。当文档比窗口大时，我们是如何进行编辑的呢？,这个可滚动的窗口就是虚拟编辑器。思路：,17,3.实现方法(1)覆盖技术：无调用关系的部分程序段，在内、外存之间交换。,大多数程序执行时，在一段时间内频繁使用的仅是程序的某一部分。因此，只需装入程序的部分内容，它也能正确地执行。即：程序空间不受主存空间大小的限制。,18,(2)程序的所有内容均可在内、外存之间交换程序的全部代码和数据存放在辅存中；将当前执行涉及到的那部分代码和数据放入主存中；在程序执行中，当所需信息不在主存时，由操作系统和硬件相配合，从辅存中调入信息到主存。形式有二种：,19,4.什么是虚拟存储器由操作系统和硬件相配合，完成信息在主存和辅存之间的交换，从而为用户提供了一个其存储容量比实际主存大得多的存储器。由于这个存储器在物理上并不存在，故称为虚拟存储器，简称为虚存(是一种技术)。提问：(1)虚拟存储器的容量是有限的吗？(2)虚存的最大容量本质上由什么来决定？,20,5.虚拟存储器的特征逻辑地址与物理地址分开程序空间与主存空间分开(或程序空间不受主存空间的限制)信息在主存和辅存之间交换6.实现虚拟存储器的物质基础有相当容量的辅存。足以存放多个用户作业的地址空间有一定容量的主存。存放运行进程的当前信息地址变换机构,21,（三）主存分配主存分配的功能又包括：1.构造分配用的数据结构如主存资源信息块：等待队列头指针自由主存队列头指针主存分配程序地址2.制定各种策略(1)主存分配策略(2)放置策略当有多个空闲区时，选择哪个、或哪些空闲区进行分配。,22,(3)调入策略决定信息装入主存的时机预调：在访问前将信息调入主存请调：当需要信息时，才将信息调入主存(4)淘汰策略当主存中没有可用的空闲区时，决定将哪些信息从主存中移走。即确定淘汰已占用的内存区的原则。3.实施主存的分配与回收申请：主存的大小；返回：主存的首地址,23,（四）存储保护1.什么是存储保护在多用户环境中，主存储器按区域分配给各用户程序使用。为了互不影响，必须保证：每道程序只能在给定的存储区域内、进行指定的活动，这种措施叫做存储保护。2.存储保护方法通常的存储保护方法有：(1)界地址保护：让不让访问(2)存储键保护：让不让、及允许如何访问,24,3.界地址保护(1)上、下界保护,设置上下界寄存器内容判断是否越界,若下界寄存器物理地址D上界寄存器：允许访问否则：发生越界中断,25,()基址、限长保护,设置基址、限长寄存器内容判断是否越界,若0逻辑地址限长寄存器：允许访问否则：发生越界中断,4.存储键保护,关键是建立：进程存储区,允许的访问,PSW,Write()；,5.2分区存储管理5.2.1分区管理基本原理1.固定分区法固定分区把主存分成若干个固定大小的存储区。,OS,20K,28K,60K,124K,256K,进程A（6K）,进程B（25K）,进程C（36K）,2.动态分区法因为固定分区主存利用率不高，使用起来不灵活，所以出现了可变分区的管理技术。动态分区原则：存储空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。,OS,进程A,进程B,进程C,进程D,OS,进程A,进程B,进程C,OS,进程A,进程B,OS,进程A,进程E（50K）,进程F（16K）,进入内存,进程B（16K）,进程D（124K）,完成,内存分配变化过程,3.可用表、自由链、请求表,可用表,自由链,请求表,31,4.分区分配机构（1）分区描述器每个分区都有一个分区描述器，通常就在该分区的首部。结构为：,flag：空闲区；1已分配区size：分区大小next：空闲区队列的勾链字(已分配区的此项为空）,32,（2）自由主存(或空闲区)的队列结构,5.2.2分区的分配与回收一.固定分区时的分配与回收当用户要程序装入执行时,通过请求表提出内存分配要求和所要求的内存空间大小.到可用空间表中找，若剩大于等于的空间,就分配,若小于,不要它进入主存。,二.动态分区时的分配与回收对于请求表中要求内存长度,分配程序从可用表和自有链中找出合适的空闲区。分配空间区之后,更新可用表或自由链。进程或作业释放内存资源时,和相邻的空间区进行链合并,更新可用表或自由链。,要求Xk大小分区,取分区说明表第一项,状态位置正在使用,取下一表项,无法分配,该分区空闲？,分区长度Xk?,表结束？,返回分区号,否,否,否,是,是,是,固定分区分配算法,三.分配算法动态分区的分配方法从可用表或自由链中寻找空闲区的方法有三种1.最先适应算法（首次适应算法）2.最佳适应算法3.最坏适应算法,36,1.首次适应算法(1)什么是首次适应算法首次适应算法是指：将作业装入到主存从低地址开始的，第一个足够装入它的空闲区中。(2)首次适应算法的例,(3)特点尽量利用存储器的低地址部分的空闲区，而尽可能地保存在高地址部分的大空闲区。,从该空闲区中截取所需大小，修改调整可用表,从空闲区表第一表目顺序查找,从可用表中移去该表目，调整可用表,取下一表项,无法分配,该空闲区长度SIZE？,该空闲区长度=SIZE？,表目查完？,返回分配起始地址,否,否,否,是,是,是,最先适应算法,38,2.最佳适应算法(1)什么是最佳适应算法最佳适应算法是将输入的作业放置到主存中与它所需大小最接近(或剩余区最小)的空闲区中。(2)最佳适应算法的例,(3)特点尽可能地保存大的空闲区。,39,3.最坏适应算法(1)什么是最坏适应算法最坏适应算法是将输入的作业放置到主存中主存中最不适合它(或剩余区最大)的空闲区中。(2)最坏适应算法的例,(3)特点尽可能地使剩余块最大。,40,4.关于三种分配的讨论作业A要求18KB；作业B要求25KB；作业C要求30KB。,用首次适应算法、最佳适应算法、最坏适应算法来处理该作业序列，看哪种算法合适。,41,18KB；25KB；30KB。,42,18KB；25KB；30KB。,43,18KB；25KB；30KB。,44,如何评价算法的性能？可用用户是否满意来评价。具体为：若一种算法能满足某种作业序列的所有分配要求，则称该算法对此种作业序列是合适的。结论：三种算法，都只对特定的作业序列合适。,45,（一）分区回收回收：应合并空闲块，分为四种情况,四.动态分区时的回收与拼接,46,回收分区r上邻空闲区,r与f1合并成为一个大的空闲区f1,回收分区r下邻空闲区,r与f2合并成为一个大的空闲区f2前指针要变化,47,回收分区r上、下邻空闲区,r,f1,r与f1、f2合并成为一个大的空闲区f1要摘除后分区,f1,回收分区r不邻空闲区,r,作业1作业2,f,r成为一个新的空闲区f,f2,f2,48,（二）碎片问题及拼接技术1.什么是碎片问题在已分配区之间存在着的一些不能被利用的极小空闲区。,2.如何解决碎片问题(1)规定剩余分区的阀值(2)采用拼接技术指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。,49,解决碎片问题的图示,3.产生碎片的原因(1)各个作业的程序空间大小不同，产生大小不同的区(无法解决)。(2)每个作业都要求一片连续的内存区域。4.分区存在的问题(1)存在碎片，降低了内存的利用率。(而拼接碎片占用大量的CPU时间)(2)无足够大的内存空闲区时，作业无法装入。怎么解决？5.解决办法:将内存划分成多个大小相等的单位区域。(1)允许将一个作业存放在多个不连续的单位区域中，以消除碎片。(2)允许只装入一个作业的部分内容，以提供虚存。,5.3交换与覆盖,图示,1.交换技术与覆盖技术,在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现,共同点：进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换不同点：如何控制交换？,2.交换与覆盖异同点,3.覆盖技术,把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖,对用户不透明，增加了用户负担目前这一技术用于小型系统中的系统程序的内存管理上MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构,4.覆盖技术的缺点,5.交换技术,当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中,1.选择原则:将哪个进程换出/内存？2.交换时机的确定3.交换时需要做哪些工作？4.换入回内存时位置的确定,6.交换技术实现中的几个问题,将哪个进程换出内存？例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的。需要特殊考虑的是：任何等待I/O进程中存在的问题。解决：从不换出处于等待I/O状态的进程有些I/O进程因DMA而不能换出内存或换出前需要操作系统的特殊帮助。,7.选择原则,何时需发生交换？例子：只要不用就换出（很少再用）只在内存空间不够或有不够的危险时换出,8.交换时机的确定,需要一个盘交换区：必须足够大以存放所有用户程序所有内存映像的拷贝；必须对这些内存映像直接存取。,9.交换时需要做哪些工作,换出后再换入的内存位置一定要在换出前的原来位置上吗？受地址“绑定”技术的影响，即绝对地址产生时机的限制。,10.换入回内存时位置的确定,与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段,11.覆盖与交换的比较,54页式管理5.4.1页式管理的基本原理分页存储管理是解决存储零头的一种方法。动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。,65,一.页式系统的基本概念1.页面：程序的地址空间被等分成大小相等的片，称为页面(简称页)，又称为虚页。2.主存块（物理块）：主存被等分成与页大小相等的片，称为主存块(简称块)，又称为实页。.内存分配用户程序以页为单位，分配主存块。块之间可以不连续。,66,4.作业页面与主存块的关系,5.分页式存储器的逻辑地址页号和页内地址地址结构确定了主存储器的分页大小,也决定了主存储块大小.,5,10,2,5,32（页）,2,10,1024（每页1024字节）,在分配存储空间时,总是以块为单位来分配.例如,一个作业的地址空间有M页,那么只需要分配给他M个块的存储空间,每一页分别装入一个存储块即可.并不需要这些块是连续的.以上这些问题需要一个地址映射.,6.页长页面(或块)的大小称为页长。页长通常为：512B(1000000000)4k(1000000000000)1k(10000000000)8k(10000000000000)2k(100000000000)等提问：(1)页长值有何特点？(2)为什么？(3)能否太大、太小？太大：类似于固定分区太小：页面交换频繁另外，也是为了提高内存的利用率。当程序大小为512k时，若页长为1k，则内存的利用率最高(99.8%)。,70,二.页式地址变换提问：分区存储管理是如何实现地址变换的？物理地址基址寄存器（分区首址）逻辑地址页式系统只用一个基址寄存器行不行？1.页表记录每一个页面与内存块之间地址对应关系的地址变换机构，称为页面映像表。简称为页表。,页表：由页号和内存块号组成，指出逻辑地址中页号与主存中块号的对应关系页号-作业地址空间的页序号内存块号-内存空间的块序号,页表,2.请求表,请求表用来确定作业或进程的虚拟空间的各页在内存中的实际关系.系统必须知道每个作业或进程页表起始地址和长度,以进行内存分配和地址变换.,3.位示图法（存储页面表）一个系统只有一张存储页面表.它指出内存各块是否被分配,以及来分配块的总数.,19183210,若内存被分配为1024个块,内存单元长20比特.1024/20=52个单元.描述了1024个块是否分配.,74,5.分页存储映像的例子,提问：如何由逻辑地址，得到页号、页内位移？再得到块号、块内位移（页内位移？）？,75,6.逻辑地址结构设CPU给出的逻辑地址长度为16位，页面大小为1KB时。形成页号、页内位移的逻辑结构如下：,如何由逻辑地址得到页号、页内位移呢？例如逻辑地址：00000000000000000000110000000010注意：逻辑地址仍是一维地址。页号和页内位移是由系统自动产生(因为页长是2的整数次方)，对用户是不可见(透明)的。,虚拟地址,物理地址,7620,1024*7+452=7620,7.页的地址变换,77,7.页的地址变换,78,页式地址变换的步骤将访问地址2500，送逻辑地址寄存器；由分页机构自动地把逻辑地址分为两部分：页号p(2)、页内相对位移w(452)；根据页表始址寄存器给出的页表始地址，以页号为索引，得到第2页所对应的块号b(7)；最后，将块号b和页内位w拼接在一起，就形成了访问主存的物理地址(7620)。,79,(2)页表的实现有二种基本的方式：页表在主存中：每次存取需访问主存二次，存储速度延长一倍。页表在高速缓冲存储器中：地址变换速度快，但成本较高。综合：将当前使用的部分页表项放到高速缓冲存储器中，称其为快表。命中率？816个高速缓冲存储器，命中率：8597%地址变换的实现：,80,81,页式系统是如何提供虚存的呢？三.请求分页1.两种页式系统(1)简单页式系统装入一个作业的全部页面后才能运行(不提供虚存)。(2)请求分页系统只装入一个作业的部分页面即可运行(提供虚存)。2.页面调入的方式(1)预调：问题是几乎无法预测以后要访问的页面。(2)请调：当发现所需访问的页面不在主存时再调入。效果：对页面是请调，而对部分指令可能是预调。为什么？如：页长为1K时，每页包含512条指令。,四.动态页式管理动态页式管理是在分页存储管理基础上发展起来的，指导思想：在作业运行之前，不限定把作业的整个地址空间全部装入主存，而只要求当前需要的一部分装入主存即可。这样，对作业地址空间，当其作业的大小超过主存可用空间时，用户无需考虑覆盖结构，页式存储管理就是实现单段式虚拟存储器的一个具体方案。这个方案可以为每个用户提供一个虚拟存储器。其虚拟空间比主存的空间大。这对编制大型程序来说，带来了很多方便。,具有这种存储功能的存储系统，一般称它为虚拟存储系统，一个虚拟存储系统可以运行多个虚拟存储器。一个作业的地址空间就存于一个虚拟存储器中。由于在一个作业投入运行前，并没有把它的整个地址空间装入主存，因此，在作业运行过程中，必然会到要访问的虚页，不在主存中。怎么发现和如何处理这种这种情况？这是实现请求分页存储管理所要解决的二个基本问题。虚拟存储器是系统为了满足用户对存储器容量的巨大需求而采取用软件技术虚设的一个很大的存储空间，使用户编制程序不必考虑主存储器的容量。,动态页式管理分为请求页式管理和预调入式管理。由于请求也是只让进程或作业的部分程序和数据驻留在内存中，因此，在执行过程中，不可避免地会出现某些虚页不在内存中的问题以及怎样处理这种情况，是请求页式管理必须解决的两个基本问题。,85,五.淘汰策略1.什么是淘汰策略当要调入某个页面，而又没有空闲内存块时，用来选择换出哪一页的规则称为淘汰策略，或称置换算法。2.扩充页表功能,改变位表示某页是否被修改过若为“0”表示未被修改过；为“1”表示已被修改过；引用位标识某页最近是否被访问过(可不要)若为“0”表示最近未被访问过；为“1”表示已被访问。它们的用途？,86,3.颠簸(thrashing)指导致系统效率急剧下降的，主存和辅存之间频繁的页面置换现像。又称为“抖动”。4.页面淘汰算法如何淘汰一些页面，而又保证进程的工作集在内存以避免抖动？(1)置换方式全局置换：在内存的所有页面之间进行置换。局部置换：为每个进程规定允许的最大内存页面数，进程在自己的内存页面之间进行置换。(2)页面置换算法的衡量：用缺页中断率:f=访问失败次数访问总次数=F/(S+F)通常：缺页中断率，是置换算法、允许的最大内存页面数和程序特性的函数。即：f=(R，M，P),87,(3)先进先出置换算法(FIFO算法)总是选择在主存中居留时间最长(即最老)的一页淘汰。实现：用一数组,评价：容易实现，适用于线性顺序访问的地址空间(如：指令代码等)。效率最差(程序中大量的是循环、子程序调用等),页面走向,内存块数,缺页记数,缺页率=F/M=12/17=70.5%,缺页记数F=12，访问页面数M=17,页面走向,内存块数,缺页记数,缺页率=F/M=9/17=52.9%,缺页记数F=9，访问页面数M=17,页面走向,内存块数,缺页记数,缺页率=F/M=9/12=75%,缺页记数F=9，访问页面数M=12,页面走向,内存块数,缺页记数,缺页率=F/M=10/12=83.3%,缺页记数F=10，访问页面数M=12,采用FIFO算法还会产生一种奇怪现象，直观上，分配给的作业的实页越多，进程执行时发生的缺页中断率就越小，但对FIFO算法这个结论并不是绝对的在某些情况下，当分配的页面多反而导致更多的缺页中断，这种现象称为FIFO异常现象或称Belady现象。,93,0,(4)最近最久未使用淘汰算法(LRU算法)选择最长时间未被使用的那一页淘汰掉。实现：采用队列结构(可用链表或堆栈来实现)。被访问的页面插入队尾(若已在队中，先抽出)，淘汰的页面为队首元素。评价：缺页中断率低，但要维护队列。例：某进程允许有3个内存页面，画出内存页队列并计算缺页中断数。初始装入第0页。以后访问的页号为：内存页队列缺页中断数,0,页面淘汰数？523,1,2,1,2,3,4,5,1、,2、,0、,3、,0、,4、,2,页面走向,内存块数,缺页记数,缺页率=F/M=9/12=83.3%,缺页记数F=10，访问页面数M=12,95,(5)LRU近似算法从最久未被使用的一批页面中，选择某一页淘汰。实现：在页中加引用位，淘汰引用位为0的。页被访问时，引用位置1；而引用位置0可用多种方法。(a)每隔一段时间将所有内存页面的引用位置0。问题：时间间隔选多大？(b)每个进程的内存页面号放在数组中，用替换指针选择被淘汰页。淘汰时：引用位为0被淘汰；否则，引用位改为,0,0,1,例如：装入第8页,问题：是否总能选择一页淘汰？,(6)最不经常使用淘汰算法(LFU算法)选择某段时间以来，访问次数最少的那一页淘汰掉。实现：在页表中设置一记数器。页被访问时，页表中的记数器加1。淘汰时，选择记数器值最小的。评价：效率同LRU算法接近。且不需增加另外的结构。问题：记数器会溢出吗？如果会溢出，怎么处理？定期置0?,97,(7)最佳算法(OPT算法)仅将以后不用(或很长时间后才用)的页面淘汰掉。即保证进程的工作集在内存可能性：统计表明，当页长为1KB时，只要有10个内存页面即可做到。问题：无法预测那些页以后不用。评价：难于实现，但可用来衡量其他的置换算法。,页面走向,内存块数,缺页记数,缺页率=F/M=7/12=58.3%,缺页记数F=7，访问页面数M=12,六.存储保护一种是地址越界保护，另一种是通过页表控制对内存信息的操作方式提供保护。地址越界保护可由地址变换机构中的控制寄存器的值页表长度和所要访问的虚地址相比较完成。存取控制保护的实现则是在页表增加相应的保护位即可。,七.页式管理的优缺点(P127),优点：,缺点：,1.有效地解决了碎片问题2.既提高了主存的利用率，又有利于组织多道程序执行,1.要求有相应的硬件支持，增加了机器成本。2.增加了系统开销。3.可能产生抖动现象。4.每个作业或进程的最后一页内总有一部分空间得不到利用。,页式存储管理方案小结,优点：解决了碎片问题便于管理缺点：不易实现共享不便于动态连接,5.5段式与段页式管理作业的逻辑地址空间：分段情况下要求每个作业的地址空间按照程序的自然逻辑关系分成若干段，每个段有自己的段名。,作业A,0,2K,0,0.5k,0,300,0,200,103,5.5.1段式存储管理,一.段式地址空间1.什么是段段是程序中自然划分的一组逻辑意义完整的信息集合。DOS中分段的实例：代码段、数据段、栈段。2.作业地址空间由若干个逻辑段组成，每个段有自己的名称（或标识）。另外，每个段又都是一个独立的一维地址空间。因此，分段的程序是一个二维线性空间。3.内存的分配以段为单位，分配相应的内存区域，内存区域之间可以不连续。且可仅装入部分段。,104,.段的二维逻辑地址形式,与页不同，段对用户是可见的,5.段表,段表每个作业一个，这个段表实施段保护，提供虚存。存取方式读/写、只读、执行。,106,二.段式地址变换,段式地址变换的步骤如下：取出程序地址(S，W)。如W0或WL，则地址越界。否则，用S检索段表，得到段的内存首地址B(BW)即为所需的内存地址。,107,三.分段和分页的区别1.分段是信息的逻辑划分，而页分是地址空间的物理划分(没有逻辑含义)。2.页的大小是固定的，由机器结构决定；而段长是可变的，由用户决定(段的最大长度由段号S的位数决定)。3.分段对用户是可见的，而分页对用户是不可见的。页式系统中，无页内位移W的溢出(溢出将自动加入到页号中去)；而段式系统中，段内位移W的溢出将产生主存越界。,提问：,(1)如何实现段的共享？(2)内存是否存在碎片？如何解决呢？,四.段的共享与保护在多道程序系统中，尤其在分时系统中，数据共享是很重要的，在分段系统中，个共享进程应能访问被共享的段，所以共享的方法是使这些共享用户的逻辑空间中的段指向相同的段号，在共享中必须小心处理的一个问题是共享段的保护问题。,段的共享,5.5.2段页式存储管理分段结构具有逻辑上清晰的优点，但它的一个致命弱点是每个段必须占据主存储器的连续区域，于是，要装入一个分段时可能要移动已在主存储器中的信息，为了克服这个缺点，可兼用分段和分页的方法，构成段页式存储管理。每个作业仍按逻辑分段，但对每一段不是按单一的连续整体存放到存储器中，而是把每个段再分成若干个页面，每一段不必占据连续的主存空间，可把它按页存放在不连续的主存块中。,112,1.基本思想：将段作为独立的程序再分页。即：内存分块，程序分段(二维空间)。系统将每个段再划分为多个页面，就形成了段页式存储管理。段页式地址结构中一个用户程序的地址空间：,2.段页式管理的实现原理1虚地址的构成一个进程中所包含的具有独立逻辑功能的程序和数据仍被划分为段，并有各自的段号S。把段划成若干个页，和页式系统一样。,段号,页号,页内地址,（2）段表和页表在段页式系统中,每个分段又被分成若干个固定大小的页面，那么每个段又必须建立一张页表把段中的虚页变换成内存中的实际页面。显然，与页式管理时相同，页表中也要有相应的实现缺页中断处理和页面保护等功能表项。每个段有一个页表，段表中应有专项指出该段所对应页表的页表始址和页表长度。,115,2.段页式系统中段表、页表与主存的关系,段表地址寄存器,段表长度起始地址,spd,物理地址,P+d,p,虚拟地址,联想存储器,段页式地址变换,段表,S段的页表,117,3.段页式地址变换的步骤给出访问地址：段号S、段内位移SW；由分页机构段将段内位移SW分为两部分：该段内的页号P、页内位移w；由段号S查段表，得到该段的页表始址；查页表，找到页号P所对应的块号b；最后，将块号b和页内位移量w拼接在一起，就形成了访问主存的物理地址。4.缺段：生成该段的页表。5.缺页：调入该页。,（3）动态地址变换过程关键问题仍是如何将二维虚地址映射成一维实地址，为了实现动态地址变换。（a)段页式系统必须为每个作业建立一张段表，段表表目中的地址部分指出该段的页表在主存的始址。(b)为每个段建立一张页表，每个表目指示该页所在主存的页面号。(c)每个作业有一个段表地址寄存器，指示它的段表所在位置和段表长度。(d)设置快速联想寄存器，存放当前最常用的段号S，页号P和对应的内存页面与其它控制用栏目。,查找方法:如果所访问的段或页在快速联想寄存器中，则系统不再访问内存中的段表、页表。把快速联想寄存器中的值与页内相对地址D拼接起来得到内存地址。若快速联想寄存器中没有，才去通过段表、页表进行内存地址查找。,5.6局部性原理,程序局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面。时间局部性：一条指令被执行了，则在不久的将来它可能再被执行。空间局部性：若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。,121,页面故障率,内存页面的比率,1,1,122,问题：从最佳的角度来看，内存应放多少页面，以及那些页面呢？(1)工作集的概念一个进程的工作集是指：该进程最近活跃地访问的页面集合。其定义为：W(t,h)=页i页i属于N，并且在时刻t之前的一段时间h内被访问其中：N为进程可访问的页面集合。(2)工作集的大小设当前的时刻为t0，将来的某一时刻为t0+t，则有：,123,t0+t,t0,h0,工作集W的大小,过去访问次数h,意义：用h0代替任意的h；当前工作集预测下一工作集。Donovan根据实验建议：h010000次访问涉及的页数(2)如何确定最近活跃地访问的页面集合?在介绍页面淘汰时介绍,124,中断位i标识该页是否在主存若i=1，表示此页不在主存若i=0，表示该页在主存。辅存地址该页面在辅存的位置,3.请求分页系统需解决的问题(1)怎样发现所访问的页面在不在主存？(2)当发现所需访问的页面不在主存时如何处理?4.扩充页表功能.,125,5.缺页的处理例：设某作业允许占用的最多主存块数为m=3，当程序执行指令：movr1，2120时,0,1KB,0,1KB,2KB,4KB1,主存,作业2地址空间,2KB,3KB,4KB,5KB,6KB,7KB,8KB,9KB,10KB1,0,2,1,4,2,作业2页表,os,os,作业3第1页,作业3第0页,作业2第1页,作业2第0页,作业1第0页,作业1第1页,3,页号辅存地址中断位块号,0,0,1,1,地址,地址,地址,地址,movr1,2120addr1,3410,006251,006802,3KB,