第五章 存储管理_new

第五章存储管理,存储管理主要研究进程如何占用主存资源。设计操作系统的重要目标之一是提高计算机资源的利用率，而提高计算机资源利用率的根本途径是采用多道程序设计技术。因此，必须合理地管理主存储空间，使尽可能多的进程能够同时存放于主存以竞争CPU，保证CPU和I/O设备足够繁忙。,第五章存储管理,存储管理所研究的内容主要包括三个方面：取：将哪个进程（或进程的某些部分）从辅存调入主存放：研究将取来的进程按何种方式放在主存的什么地方替换：研究将哪个进程（或进程的某部分）暂时从主存移到辅存，以腾出主存空间供其他进程占用。这三方面中，“放”是存储管理的基础。目前，“放”的技术可归结成两类：一类是连续的，即运行的程序和数据必须放在主存的一片连续空间中；另一类是不连续的，即运行的程序和数据可以放在主存的多个不相邻的块中。,第五章存储管理,5.1连续空间分配单道连续分配多道固定划分法多道连续可变划分法5.2不连续空间分配页式管理段式管理段页式管理5.3虚拟内存管理,5.1连续空间分配,在早期的操作系统设计中，都是采用连续空间分配的策略。早期操作系统中还没有引入进程概念，主存分配还是以作业（相当于进程）为单位进行的。,内存空间安排,5.1.1单道连续分配,特点：任一时刻内存只有一道作业，该作业连续存放于内存中。,一、空间划分与保护,操作系统,用户程序,0,a,a+1,n,界地址寄存器,主存,Aa?,cpu,true,false,地址A,终止程序运行,越界检查机构：用户程序每次执行访存指令，硬件越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止其执行。,二、覆盖（overlay）,因内存小于作业的程序空间而引入覆盖。将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。首先将那些即将要用的段放在覆盖区，其他段放在辅存，在需要调用前通过特定系统调用将其调入占用覆盖区，替换覆盖区中原有的段。操作系统提供覆盖系统调用函数，由用户编程序时考虑调用。,例如：某作业各过程间关系如下：,操作系统,固定区(4k),覆盖区(6k),覆盖区(10k),A(4k),E(10k),D(6k),C(4k),B(6k),F(8k),覆盖技术的主要特点是打破了必须将一个作业的全部信息装入主存后才能运行的限制。在一定程度上解决了小主存运行大作业的矛盾。采用覆盖技术是把解决空间不足的问题交给了用户。操作系统提供帮助用户将覆盖段调入主存的系统调用，但用户自己必须说明覆盖段，并安排调入覆盖段，由此可见覆盖技术用户参与过多，会给用户带来麻烦。,基本思想：将处于等待状态(等I/O)或就绪(等CPU)状态的进程从主存换出到辅存，把将要执行的进程移入主存。,三、交换,交换要花费较长的时间。比如，辅存采用磁鼓，平均延迟时间为8ms，传输速度为250000b/s，用户空间为20K，则一次交换活动需要2（8+100020/250000）=179ms。,当作业处于等待状态而准备换出时，应注意该作业是否满足换出条件。如果一个作业正在进行I/O活动则不能换出，否则该作业的I/O数据区将被新换出的作业占用，导致错误。应在I/O活动结束后才能换出。,特点：任一时刻内存可有多道作业，每道作业连续存放于内存.,操作系统,U1,.,Un,5.1.2多道固定划分法,一、空间划分及保护,将用户内存空间分成长度固定的若干块。,用户空间,常用的基本概念,1.物理地址空间和逻辑地址空间物理地址空间（也称内存空间、绝对地址空间或实空间或存储空间）：是指主存中物理单元的集合。这些单元的编号称为物理地址或绝对地址。逻辑地址空间（也称相对地址空间、虚空间或地址空间）：当对源程序进行编译时，编译后一个目标程序所限定的地址范围称为该作业的逻辑地址空间。作业运行时不能按其逻辑地址访问内存单元，而应按相应的物理地址访问，需要进行逻辑地址到物理地址的转换。,2.地址重定位,当一个地址装入与其地址空间不一致的存储空间中，就得要地址变换。也就是说将逻辑地址映射为物理地址，把这种作法叫做地址重定位。,根据对地址变换进行的时间及采用的技术手段的不同，可把地址重定位分为静态重定位和动态重定位两类。静态重定位：是指在程序运行之前由装入程序完成的重定位过程。在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。原地址+目标代码所在主存起始地址动态重定位：是在程序执行过程中，需要硬件地址转换机制实现，在执行访存指令时将“原地址+目标代码所在主存起始地址”后进行访问。,利用一个重定位寄存器。该寄存器的值由调度程序根据作业分配到的存储空间的起始地址来设定。在具有这种地址变换机构的计算机系统中，当作业执行时，不是根据CPU给出的逻辑地址去访问主存，而是将逻辑地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。,静态地址重定位主要优点：无需增加硬件地址变换机构，因而可在一般计算机上实现主要缺点：要求给每个作业分配一个连续的存储空间，且在作业的整个执行期间不能再移动，因而也就不能实现重新分配主存。动态地址重定位主要优点有：用户作业不要求分配连续的存储空间。用户作业在执行过程中，可以动态申请存储空间和在主存中移动。主要缺点有：需要附加的硬件支持。实现存储管理的软件算法比较复杂。,1.上下界寄存器和地址检查机构。当作业被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次执行访存指令时，地址检查机构作越界检查。作业程序要是绝对地址或静态重定位的。,CPU,主存,下界寄存器,上界寄存器,True,True,地址A,FF,程序性异常,地址访问保护有两种方式：,2.基址寄存器、长度寄存器和动态地址转换机构。当作业被调度运行时，将作业所占内存基址及长度送基址、长度寄存器，每次执行访存指令时，先看访问地址是否小于长度，然后+基址进行访存。用户程序代码是动态重定位的。,CPU,主存,基地址寄存器,长度寄存器,+,True,地址A,F,程序性异常,二、作业存储调度,在多道固定划分法下，作业调度一般分为多队列法和单队列法。多队列法是指每个存储区对应一个作业队列，在作业到达后，按作业的大小在对应队列中排队。单队列法是指系统中仅保持一个作业队列。例如：总存储量为32KB，操作系统占10KB，用户空间被划分成长度为4KB、6KB、12KB三块。作业要求的存储量若未超过这三个存储量，则分别进入相应的队列1、队列2、队列3。,二、作业存储调度,OS,4k,6k,12k,OS,4k,6k,12k,.,7k,3k,4k,5k,.,3k,4k,3k,2k,.,5k,6k,.,7k,10k,11k,8k,多队列法,单队列法,三、存储碎片内部碎片：内存某存储区间大于其存放作业空间的部分。外部碎片：内存某存储区间容不下要运行的作业时。,一、管理方法,5.1.3多道连续可变划分法,特点：多道、连续、但不固定划分内存。,系统设置一个空闲块队列，初始状态时队列中只有一个连续的空闲块。作业到达后，以某种策略分配空间。作业撤离时，将释放的空间加入空闲队列。,举例：假设任一时间段内，内存中每一作业的运行时间片相等。,作业到来次序所需存储量运行时间,16010,21005,33020,4708,55015,OS,040256,J1,J2,J3,J4,J5,分配：调度程序为选中的作业分配存储空间，则在可用块集合中按某种策略选择一个大小满足该用户作业要求的可用可分配给用户。分配策略包括首次满足法/最佳满足法/最大满足法，在找到合适的空闲块后，从其中将作业大小的空间分给作业，而剩余部分挂入空闲队列。下面F是空闲块集合;size(k)为块k的大小;size(v)为用户所需空间。if所有属于F的k，均有size(k)2.调整相应的空闲表和已分配表。评价：性能一般但实现比较简单直接，易于释放时合并相邻空间分区。比较容易的满足大作业的需要。完成一次分配平均需要的搜索次数较大，影响了工作效率。,最佳满足算法：,搜索整个空闲区以找出满足要求的最小空闲区。思想：先使用小的空闲区，将大的空闲区留给大作业，所以它总是试图找出最接近实际需要的空闲区。评价：尽可能的保留了较大的空间。产生大量的不用被使用的很小的空闲区。,最大满足算法,总是搜索整个链表以找到够用的最大的空闲区，使分裂出来的小空闲区比较大，因而可以继续使用。评价：分割后产生的空闲区一般仍可以供以后分配使用。工作一段时间后，不能满足大作业对空闲区的请求。,例题：分区存储管理算法题,假定主存中按地址顺序依次有五个空闲区。空闲区大小依次为：15k,28k,10k,226k,110k.现有五个作业J1,J2,J3,J4,J5。他们各需要主存10k,15k,102k,26k,180k。判断用首次满足算法，最大满足算法算法，最佳满足算法能否将这五个作业顺序装入？,内存空闲区示意图：,装入J1后，内存空闲区示意图：,J1,5k,结论：只有最佳满足算法可以。,紧致空间方法,消除了固定分区管理造成的“内碎片”，但是“外碎片”仍然存在。采用移动（紧致）技术。定时的或在内存紧张时，将内存中所有作业移到内存的一端，使其相邻。,经过紧缩后的进程在内存中的位置发生了变化，若不对程序和数据的地址进行修改，在进程就无法运行。要使其运行，必须进行“动态重定位”,连续空间分配小结：,连续存储分配容易出现大段的连续空间因不能容纳作业或进程而不可用。存在许多的存储碎片和空间管理较复杂的问题，主要原因在于连续分配要求把作业或进程放在主存的一片连续区域中。因此，为充分利用存储空间资源，引入了不连续空间分配策略。,分页存储管理是解决存储零头的一种方法。动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。,5.2不连续空间分配5.2.1页式管理,一、空间安排用户编程时所设想的空间和所用的地址叫逻辑空间(地址)内存空间(地址)叫物理空间(地址)，用相同长度为单位对逻辑空间等分出的每个区域叫页，对物理空间等分出的区域叫页帧，辅存所划分出的每个区域叫块。,5.2不连续空间分配5.2.1页式管理,特点：作业(进程)分成页面，内存也划分成页面，将作业(进程)页面不连续地分布到内存页面。,回收：当进程结束时，系统回收它的所有物理页帧放入空闲队列。二、动态地址转换机构因页式方法中逻辑地址与物理地址之间失去自然联系，故要通过页表，并由硬件动态地址转换机构将逻辑地址映射成物理地址才能正确访存。,分配：系统初始时，所有页帧都在空闲队列中，当用户进程被创建时，系统按需要量从空闲队列获得相应量的页帧。,(一)页表由于逻辑地址和物理地址不一致，因此必须把逻辑地址所对应的物理地址登记在一张称为页表的表中，逻辑空间若有n页，页表就应该有n项。页表放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。PCB表中有指针指向页表。,页表的第i项描述第i页，比如某作业由5页组成，分别放在第1号、8号、5号、3号、0号页帧中。,1,8,5,3,0,4,9,8,7,6,5,4,3,2,1,0,3,2,1,0,逻辑空间,页表,页号,物理空间,(二)地址结构分页逻辑地址=P(页号).d(页内位移)分页物理地址=f(页帧号).d(页帧内位移)P=线性逻辑地址/页面大小；d=线性逻辑地址-p*页面大小。在求解逻辑地址对应的物理地址时，首先应分解逻辑地址的页号和页内位移，然后按页号查找对应的页表项,4,3,2,1,0,页号,因此，从逻辑地址转换为物理地址可以这样计算：通过逻辑地址求出P和d将页表始地址加上P得到页表项地址；从页表项中获得该页所驻留的页帧号f；再将f乘页面大小加d就得到所要的物理地址,(三)页面大小的考虑将页面大小取成2的k次幂(k是正整数),获取p和d的除、乘法只要通过位移实现.页面大小为2的k次幂的地址转换原理如下：,Pd,页表始地,f,nk-10,fd,nk-10,+,页表,CPU有一个用于页号页帧号转换的联想存储器。将页表存入联想存储器的地址转换原理如下：联想存储器是一种高速存储体，每一项主要由两部分构成：关键字和值。当输入信息到达后，便同时与联想存储器中各项的关键字进行比较，如果某项关键字与输入信息相同，则输出该项的值。如所有项的关键字与输入信息不匹配，则输出一个特殊信号表示匹配不成功。把页式系统中的页表项放在联想存储器，则其页号为关键字，对应的页帧号为值。将待转换的逻辑地址的页号作为输入，与联想存储器的每一项进行匹配，若匹配成功，输出页帧号。,(四)联想存储器（快速存储器）,Pd,nk-10,fd,nk-10,P2,f2,P1,f1,.,.,P,f,.,.,Pm,fm,关键字值,联想存储器价格昂贵，一般只将一部分页表项放在其中。地址转换：首先把页号送到联想存储器中匹配，若匹配成功，形成物理地址，否则到主存页表中查找页表项来形成物理地址。,地址转换的一般过程(联想存储器可以看成是页表的cache),Pd,nk-10,fd,nk-10,P2,f2,P1,f1,.,.,P,f,.,.,Pm,fm,f,页表始地址,+,页表,联想存储器,命中率：选用8-12项组成的联想存储器，并采用适当的替换策略，在联想存储器中匹配成功的可能性可达80-90%。,三、可用空间管理可用bitmap数组或空闲页帧链来管理可用页帧。（1）若可用页帧总数小于作业（进程）总页数，则拒绝分配，结束。（2）否则，取作业（进程）的下一页P，分配一可用页帧f，将P的内容抄到f中。（3）将f抄到页P的页表项中。（4）若所有页都处理完，则结束，否则转向2。,四、共享与保护在操作系统中，很多代码是可以共享的，如命令解释程序、编译程序、编辑程序等。在连续分配存储空间模式下，共享是不可能的，因为一个作业运行时只能访问一片连续的区域，多个作业显然不能与被共享程序都保持连续。在页式系统中便可实现共享。通过页表可以使几个逻辑空间指向同一个物理空间，实现程序共享。,举例：有3个进程共享编辑程序EDIT，EDIT长度为3页，分别驻留在主存的3、4、6号页帧中。,EDIT1,EDIT2,EDIT3,DATA1,EDIT1,EDIT2,EDIT3,DATA2,EDIT1,EDIT2,EDIT3,DATA3,3,4,6,1,3,4,6,7,3,4,6,10,OS,DATA1,EDIT1,01234567891011,EDIT2,EDIT3,DATA2,DATA3,P1P2P3,页表,每个进程在运行时由自己的页表来进行地址映射，从而实现了多个进程对一个EDIT程序的共享。,存储保护引入页式不连续分配以后，由于共享的出现对存储保护也提出了新的要求。除了仍需要越界保护以外，对共享页还要进行特殊的保护。越界保护：设置页表长度寄存器，查页表前，先检查页号是否越界。操作访问保护：在每个页表项中增设一存储保护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先要比照是否满足该页访问权限的说明，满足则访问，否则报错。,设为每一页表项增加三位，R位表示读权限，W位表示写权限，E位表示执行权限。RWE000不可进行任何操作001可以执行,不可以读写010只可以写011100101110111,5.2.2段式管理,页式管理：对用户而言不自然，用户看待程序是以自然段为单位的。,比如某段只能读，另一段可执行。分页可能把不属于同一段的两块分到一页中。第4页中放入程序段（可执行）和数据段（可读写）各半，从而无法对其进行保护。,段式管理的特点：按作业的自然段将其逻辑空间分成若干段，作业以段为单位分配内存。一、空间安排例如，某用户作业（进程）由主程序、两个子程序、栈和一段数据组成。于是可将这个作业划分为5个段，每段从零开始编址。逻辑地址：段号.段内偏移，记作S,d。编译及装配时把所有地址记成(S,d)的形式。若作业正在运行主程序，则地址形式为（0，d）；一旦调用子程序1，地址变为（1，d）；若访问数据段，地址变为（4，d）。,物理内存空间管理：与多道可变划分法一样，系统以段为单位分配物理内存。,主程序,子程序1,子程序2,栈,数据,逻辑空间,子程序2,主程序,栈,数据,OS,子程序1,物理空间,二、动态地址转换,保护码,段长,本段在内存始地址,由于作业在逻辑空间连续但主存空间不连续，故运行时需要进行地址转换。段表：由如下格式的段表项组成，作业每段由一个段表项表示.作业被划分成n段，段表就应该有n项,段表放于系统空间，进程PCB表中存有段表始地址、段表长度。系统还设置段表始地址寄存器、段表长度寄存器。,段号,保护码,段长,段内存始址,.,.,.,.,保护码,段长,段内存始址,.,.,.,S,d,段表始址,段表长度,+,+,PA,越界,地址转换过程,LA,联想存储器,对于用户而言，段页式管理与段式相同，用户逻辑地址只涉及段号与段内位移。对于物理内存管理而言，它与页式系统相同。系统内的逻辑地址：段号段内位移-段号页号页内位移。记作：S，P，d.,5.2.3段页式管理,特点：将作业分成若干段，每段用页式管理实现内存分配。,一、空间安排,作业空间的内部表示,主程序子程序数据,保护码长度页表始地,OS,段表,页表,主存,作业,段表+页表,二、动态地址转换,三、保护与共享保护与段式管理相同。共享则可以以页为单位，也可以共享页表。,等效访问时间：设访存时间为750ns，搜索联想存储器的时间为50ns，命中率为95%，则95%*(50+750)+5%*(50+750+750+750)=875ns,段表,主程序子程序数据,作业1,主程序子程序数据,作业2,段表,页表,OS,主存,总结“放”连续存放单道连续划分多道连续固定划分多道连续可变划分不连续存放页式存储段式存储段页式存储,5.3.1虚存的基本思想,5.3虚存管理,目的：提供用户进程一个巨大的虚拟存储空间.,手段：通过统一管理主存、辅存，利用辅存实现此虚空间.,系统为进程提供一个比物理内存大得多的虚拟存储空间，虚拟空间大小不受物理内存大小的限制。虚拟空间的容量由系统的有效地址长度决定。假设地址长度为32，按字节寻址，则虚拟存储空间大小为232个字节。,实现页式虚空间的基本方法是：在页式管理的基础上，仅将进程的一部分页放于主存。页表项中注明该页是否在主存。程序执行时，如果访问的页不存主存，根据页表项的指示，将其从辅存调入主存，如果此时无可用的内存空间，则先淘汰若干页帧。,一、页表项结构:,合法位：置上表示该页在内存.修改位：置上表示该页被修改过，在释放或淘汰时应回写辅存。页类型:1、零页时：表示该页在分配物理页帧时应清0页帧空间;2、回写swap区页时:表示在回写时必须分配swap区，并回写到swap空间中。没有设置页类型时，表示按正常方式处理。保护码：R、W、E保护说明。辅存块号：该页所在辅存的块号。页帧号：当合法位置上时代表该页所在内存的页帧号。,5.3.2页式虚存管理,交换区（SWAP）：进程刚建立时，进程页面所在的辅存即程序文件所在的辅存位置。程序文件中一般包含有程序的二进制目标码及数据初始值和初值为0的工作区。程序在进程的运行过程中，数据的初始值页面被调入主存使用，而且存放初始值的主存单元可能被修改。这时，系统不能将修改过的页面回写到执行程序文件中去，因为执行程序中的初始值不能被改变。因此引入了交换区用于存放那些可读写的页面。,还有一种页面，在执行程序文件中被说明是初值为0的工作区，我们称为零页，表示该页的初值为0。这种页面分配主存页帧时不必从辅存获得初始数据，只要在分配页帧时，将页帧清0即可。当回写时，也需要分配交换空间，然后回写到交换空间中。,二、页表建立,分配pid给子进程，分配PCB空间;初始化PCB（进程标识，调度信息）;分配子进程页表空间;拷贝父进程的程序区页表项，使程序共享;,部分复制父进程页表(如UNIX的fork(),初始化页表方法：,在进程创建时建立页表，页表项在初始时，合法位、修改位及页帧号都未置上.,复制父进程的数据区和栈区，为数据区和栈区分配swap空间，复制并修改数据区和栈区页表项内容;继承父进程对其他资源的访问现场;用父进程PCB中现场区初始化子进程的现场区，且保证子进程恢复现场运行从fork（）返回处开始，且fork()返回值为零;将子进程挂到就绪队列;返回子进程pid给父进程.,为执行程序页面建页表项，保护码为可执行，辅存块号即该页所在的文件的辅存块号。（不必回写）为所有初始数据页建页表项，保护码为可读写，页类型说明成回写swap页，辅存块号即该页所在文件的物理块号，待该页回写时，再分配swap区空间，改辅存块号栏并清0页类型。为所有临时数据页建页表项，保护码为可读写，页类型说明成零页，辅存块号栏空，当第一次访问该页时，分配页帧并清0页帧，回写时，再分配swap区空间，填外存块号栏并清0页类型。,用一个可执行的程序文件来初始化页表,在执行虚存访问指令时,由硬件合成物理地址。首先若能在联想存储器中获得该虚页的物理页帧号，则访问之。若要查当前进程页表，须先检查该页页表项的合法位，若置上，则从页表项中获得页帧号，否则要发一个页故障(pagefault)或叫缺页异常，当缺页异常处理完后，重新执行访存指令.联想存储器中的页表项都是合法页的页表项.,三、硬件动态地址转换,1、根据发生页故障的虚地址得到页表项；2、申请一个可用的页帧(根据所采用的替换策略可能需要引起淘汰某一页);3、检查页类型，若为零页，则将页帧清0，将页帧号填入页表项的页帧号一栏，置合法位为1。若非零页，则调用I/O子系统将辅存块号所指的数据读到可用页帧，将页帧号填入页表项中，合法位置1，结束.,四、缺页处理,当硬件执行访存指令产生一个缺页异常时进入缺页异常处理程序：,五、页淘汰页淘汰可以发生在申请页帧时，而现代OS一般都定时进行页淘汰。如何选取被淘汰的页是由页面替换策略决定的，若已决定淘汰页P，则淘汰一页的主要工作有：1、查P页表项的修改位，若未修改，则清0合法位，将页帧送回空闲页帧队列。2、若已修改，则检查类型栏。3、若是零页或回写swap区页，则申请一块swap区空间，将P的辅存块号置上并