存储管理虚拟存储请求式管理

1,内存的物理组织,物理地址：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址,绝对地址,实地址）,存储单元占8位，称作字节（byte）。物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。,2,程序的逻辑结构,程序地址：用户编程序时所用的地址（或称逻辑地址、虚地址），基本单位可与内存的基本单位相同，也可以不相同。程序地址空间（逻辑地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。,3,4.6虚拟存储器的基本概念,4.6.1虚拟存储器的引入,4.6.2虚拟存储器的实现方法,4.6.1虚拟存储器的特征,4.6.1虚拟存储器引入,1.常规存储器管理方式的特征2.局部性原理3.虚拟存储器定义,5,1.前面讨论的各种存储管理方法虽各有特长，但有一些共同的特点:,首先是“一次性分配”。,其次是“驻留性”。,作业全部信息，必须一次性装入内存,作业信息一旦装入内存便一直驻留到作业运行结束,一方面使大作业的运行受到限制，另一方面又影响了多道程序的实现。,6,2、局部性原理,程序的局部性规律，程序往往会不均匀地高度局部化地访问内存。,7,（1）程序在执行时，在大多数情况下仍是顺序执行的。这种特性使得程序的执行在一段时间内被限制在作业的某一局部范围。,P.Denning有以下一些论点：,（2）过程调用将会使程序的执行轨迹由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。在一段时间内，程序将会被局限于这些过程的范围内运行。,8,（3）程序中存在许多循环结构，它们可以多次重复执行。,fori:=1tonai:=ai+1;,（4）程序中还包括许多对数据结构的处理，它们往往都局限于很小的范围内。,9,局限性的表现：时间，空间（1）时间局限性时间局限性是指最近被访问的存储位置，很可能不久的将来还要被访问。,支持这种现象的是：,(a)循环；,(b)子程序；,(c)栈；,(d)用于计数和总计的变量。,10,（2）空间局限性空间局限性是指存储访问有集成一组的倾向，以致一旦某个位置被访问到，很有可能它附近的位置也要被访问。,支持这种现象的是：,a、数组遍历；,b、代码的顺序执行；,c、程序员倾向于将相关的变量定义相互靠近存放。,11,基于局部性原理，作业没有必要全部装入内存。,如果计算机系统把辅助存储器当做主存储器的扩充，当作业运行时，不是将其全部信息装入内存，而是将必须部分先装入内存，其它部分仍存于辅存中。作业运行过程中随时把需要但又不在内存的信息装入内存，把暂时不用的信息淘汰出去，以确保作业的正确运行。,好象这个计算机系统向他们提供了一个容量很大的主存,12,3、虚拟存储器的定义,所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。,虚拟存储器的大小受计算机系统地址结构和可用外存数量的限制，与实际内存单元的数量无关。,13,4.6.2虚拟存储器的实现方式,离散分配存储管理方式是实现虚拟存储器的基础。,1.分页请求系统2.分段请求系统,14,1、页式虚拟存储系统,是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的分页请求系统。,15,硬件支持：,(1)请求分页的页表机制。,(2)缺页中断机构。,(3)地址变换机构。,软件支持：,(1)实现请求调页的软件。,(2)实现页面置换的软件。,16,2、请求分段系统,这是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。,17,为了实现请求分段，系统要提供硬件支持：,(1)请求分段的段表机制。,(2)缺段中断机构。,(3)地址变换机构。,同样地，请求调段和段的置换功能的实现也需要得到OS的支持。,18,4.6.3虚拟存储器的特征,离散性是虚拟存储器最基本的要求，虚拟性是它的最重要特征，另外虚拟存储器还具有多次性和对换性。,19,1、离散性离散性是指在内存分配时采用离散分配方式。,2、多次性作业分多次装入内存,3、对换性运行时换进换出,4、虚拟性逻辑上扩充内存容量,最基本特性,20,4.7请求分页存储管理方式,请求分页存储管理方式是建立在纯分页基础上的.其基本思想:在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,21,4.7.1请求分页中的硬件支持,一、页表机制二、缺页中断机构三、地址变换机构,页表的作用是实现从用户地址空间中的逻辑地址到内存空间的物理地址的转换。,22,请求页式管理中对地址空间分页，内存分块与基本分页管理一样，但对虚页的管理是不同的。,要访问的页面不在内存中，如何发现和处理这种情况？,这是请求分页存储管理要解决的两个基本问题,23,在纯分页系统中，页表的内容为：,针对第一个问题：如何发现要访问的页面不在内存？扩充页表：,24,针对第二个问题：怎样调入页面？,由地址变换机构产生一个缺页中断信号，OS进行中断处理后，根据该页的外存地址把它从外存调入内存。,引进修改位和访问字段。,25,请求分页系统中，页表项如下：,(1)状态位（驻留位）P:该页是在内存还是在外存(2)访问字段位A：记录本页在一段时间内被访问的次数;根据访问位来决定淘汰哪页（由不同的算法决定）(3)修改位M:该页调入内存后是否在被修改过(4)外存地址:该页在外存上的地址,通常为外存物理块号.,26,在虚拟存储系统中，当一个作业被编译或经链接装配后得到的地址空间，通常存在磁盘上。,外页面表,当一个作业被调度到而装入内存时，系统为它在内存建立一张页表。,27,2、缺页中断机构,在请求分页系统中，当要访问的页面不在内存时，硬件发一个缺页中断，转交OS处理。,28,(1)在指令执行期间产生和处理中断信号。,(2)一条指令在执行期间，可能产生多次缺页中断。,它跟一般的中断有着明显的区别：,29,页面,6,5,4,3,2,1,CopyAToB,B：,A：,30,3、地址变换机构,请求分页系统中的地址变换机构是以分页系统的地址变换机构为基础的，还增加了产生缺页中断、处理缺页中断，置换等功能。,31,在进行地址变换时，首先去检索快表；,如果快表中没有这一页的页表项，再到内存中找页表，根据状态位P来判断该页是否在内存中。,在内存，将该页的页表写入快表；快表满时，调出某页表项，再写入该页的页表项不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存,否则不写,32,图4-25这里仅仅给出一个很粗略的框图，具体的过程是很复杂的。因为作业的副本是以文件形式存于外存上，因而要求页面传输时，必然要涉及到文件系统，此外，还得调用输入输出进程。在多道程序环境下，一个作业在等待传输页时，它处于被阻塞的状态。此时，由系统调度另一作业运行。当页面传输完成后，才把原先被阻塞的那个作业重新置成就绪状态，但要等到再次调度到它时，才能恢复到原先中断的地方继续运行下去。,33,4.7.2内存分配策略和分配算法,在为进程分配物理块时，又要解决三个问题：,1、保证进程正常运行而需要的最少物理块数；,2、进行分配时，物理块数目是固定的还是可变的；（分配策略）,3、是采取平均分配算法还是根据进程的大小按比例分配物理块。,34,1、最小物理块数的确定,最小的物理块数，是指保证进程正常运行所需的最少物理块数。,最少物理块数与指令的格式、功能和寻址方式有关，也就是说与计算机的硬件结构有关。如:单地址指令且直接寻址系统,至少2块指令块/数据块,35,2、物理块的分配策略,1)、固定分配局部置换（FixedAllocation,LocalReplacement）基于进程的类型,为每个进程分配一定数目的物理块(n块),在整个运行其间不变;如缺页:n块中置换一页,以保证该进程在内存中的页面数不变;问题:多少个物理块合适?物理块太多:资源空闲.物理块太少:频繁中断,采取固定和可变分配策略,36,2)、可变分配全局置换,空闲物理块队列,先为每个进程分配一定数目的物理块,OS也保持一个空闲物理块队列,当进程缺页时,由系统从空闲物理块队列取出一个物理块分配给该进程,并将要调入的(缺)页装入内存.仅当空闲物理块队列中的物理块用完时,OS才从内存中任一进程的一页调出.问题:会使被调出页的进程缺页,进而使缺页率增加,影响其它进程的执行.,37,3)、可变分配局部置换,要求保持适当的缺页率,基于进程的类型,为每个进程分配一定数目的物理块,进程如缺页:只从该进程在内存中的页面中换出一页,这样不会影响其它进程;如果进程在运行其间频繁发生缺页中断,则系统再为该进程分配若干个附加物理块,直至进程的缺页率减少到合适为止;若进程的缺页率特别低,可适当减少已分配该进程的物理块数目.,38,3、物理块分配算法,在固定分配策略中，系统在为各个进程分配物理块时，可采取：,1)、平均分配算法,39,系统中多进程页面数的总和为：,每个进程所能分到的物理块数bi=Si/Sm，m为可用的物理总数。,3)、考虑优先权的分配算法,2)、按比例分配算法,，Si为某个进程的页面数。,40,4.7.3调页策略,1、何时调入页面2、从何处调入页面3、页面调入过程,1）预调页策略,2）请求调页策略,用于首次调入,41,2、从何处调入页面,(1)系统拥有足够的对换区空间。,当缺页时，全部从对换区把所需的页面调入内存，使调页速度提高。要求:进程运行前,把进程相关文件拷入对换区,在请求分页系统中,外存分为两部分:文件区和对换区,42,刚开始时，都放在文件区,文件区,对换区,不改,改,外存可能被修改,不会被修改,内存,(2)系统缺少足够的对换区空间。,43,(3)UNIX方式,与进程有关的文件都放在文件区。没有运行过的页面，从文件区调入内存；已经运行过又被换出的页面，放在对换区，下次调入时，从对换区调入。,44,外存物理块号,内存有空：调入内存,不空：换出一页,修改位为1，重新写入外存,修改位为0，不必写入外存,将缺页调入内存,修改页表，写入快表,物理地址,访问数据,3、页面调入过程,45,4.8.1最佳置换算法和先进先出算法,4.8页面置换算法,4.8.2最近最久未用置换算法,4.8.3CLOCK置换算法,4.8.4其他置换算法,46,4.8.1最佳置换算法和先进先出算法,4.8页面置换算法,假定作业p共计n页，而系统分配给它的主存块只有m块（m,n均为正整数，mn），即最多只能容纳m页。如果程序p在运行中成功的访问次数为s,不成功的访问次数为f,那么，其总的访问次数a=s+f，若定义f=f/a，称f为缺页中断率。,缺页中断率:,47,影响缺页中断次数的因素,（1）分配给进程的物理页面数物理页面数多，缺页中断少，反之，则缺页中断多物理页面数多，进程数少（影响系统效率），反之，则进程数多（缺页中断多）根据试验分析：对一共有n页的进程来说，只要能分到n/2块内存空间，就可使系统获得最高效率；,（2）页面本身的大小页面大，进程的页数少，一页的信息就大，缺页中断次数减少；不同的计算机系统，有不同页面大小；,48,例：程序要把128128的数组初值置“0”，数组中每一个元素为一个字，假定页面大小为128个字，数组中的每一行元素存放一页，能供该程序使用的主存块只有1块。初始时第一页在内存；,程序编制方法1：Forj:=1to128Fori:=1to128Aij:=0;按列：缺页中断次数：1281281,程序编制方法2：Fori:=1to128Forj:=1to128Aij:=0;按行：缺页中断次数128-1,（3）程序的编制方法,可见：缺页中断率与程序的局部化程度密切相关。希望编制的程序能经常集中在几个页面上；,49,50,(4)页面淘汰算法理论的页面淘汰算法应该选择的被淘汰页面将是以后永不使用的，或在最长(未来)时间内不再被访问的页面。（OPT算法）。实际上，可以用理论的页面淘汰算法作标准，选择其它较好的页面淘汰算法,页面淘汰算法选择不合适，会使系统“抖动”,51,刚被换出的页很快又被访问，需要重新调入，为此又需再选出一页调出；而刚被换出的页，很快又要被访问，又需把它调入，如此频繁地更换页面，以致一个进程在运行中，把大部分时间花费在完成页面的置换工作上，使得调度页面所需时间比进程实际运行的时间还多.我们称该进程发生了“抖动”。,抖动,52,最佳置换算法是由Relady在1966年提出的，这种算法选择的被淘汰页面，将是永不使用的，或在最长时间内不再被访问的页面。最佳置换算法是指对于任意的内存固定空间m和程序p,有缺页中断率最小。它是一个理论上的算法。,1、最佳置换算法（OPT）,53,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串。,采用最佳置换算法，只发生了6次页面置换，发生了9次缺页中断。缺页率=9/21,54,2、先进先出页面置换算法（FIFO）,这是最早出现的置换算法，这种算法总是淘汰最先进入内存的页面，选择在内存中驻留时间最久的页面予以淘汰。,55,我们来看看采用FIFO算法进行页面置换时的情况。,一共发生了12次页面置换，比最佳置换算法多了1倍。缺页率15/21=3/4，15次页面中断。,56,FIFO的两个实现方法：1.在主存中建立一个有m(m是分配给该作业的存贮块数)个元素的页号表和一个替换指针。Pi(i=0,1,2,m-1)指示在一个内存中的页面的页号。替换指针K指向进入主存最老的那一页。每当一页新页调入后，执行语句：pk=新的页号；k=(k+1)modm;,替换指针,指向最老的一页,2451,页号,57,2.把进入内存的次序建立在存贮分块表中（该表以块号为序，依次登记各块的分配情况）。,012463425657714,块号页号指针,2,替换指针,012634225657714,块号页号指针,6,替换指针,(a)替换之前,(b)替换之后,58,FIFO是根据各个页面调入内存的时间来选择被淘汰页面，但页面调入的先后并不能反映页面的使用情况。FIFO算法只是在按线性顺序访问地址空间才是理想的。未考虑到程序的动态特性。可能引起异常。,59,先进先出置换算法的一个异常现象：对于一些特定的页面访问序列，先进先出置换算法有随着分给的页架数增加，缺页频率也增加的异常现象。,ABCDABEEECDDABCDABBBECCABCDAAABEE+,页面访问序列,ABCDABEABCDE,九次缺页,三个页面,ABCDDDEABCDEABCCCDEABCDABBBCDEABCAAABCDEAB+,页面访问序列,十次缺页,四个页面,60,4.8.2最近最久未使用LRU置换算法,1、LRU（LeastRecentlyUsed）算法的描述,基本思想：基于程序的局部性原理，在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用，反之，已经很久没有使用的页面很有可能在未来较长一段时间内不会使用；因此，在缺页发生时，淘汰掉最久未使用的页；,选择淘汰的页面是最近最久未使用,61,我们用“最近的过去”来直接推断“最近的将来”。,发生了9次页面置换。,标明访问时间,62,2、LRU算法的硬件支持,为了实现LRU算法必须解决：（1）一个进程在内存中的各个页面各有多久时间未被进程访问；（2）如何快速地知道哪一页是最近最久未使用的页面。,63,1、寄存器,为每个在内存中的页面配置一个移位寄存器，表示为：R=Rn-1Rn-2Rn-3R1R2R0,当进程访问某物理块时，要将相应的寄存器的Rn-1位置为1。,定时信号将每隔一定时间将寄存器右移一次，把n位寄存器的数看作是一个无符号的整数，最近最久未使用的页面就对应着具有最小数值的寄存器。,用于记录某进程在内存中各页的使用情况。,64,2、栈,LRU置换算法可用堆栈的方法来实现。,栈中存放当前内存中的页面号，每当访问一页时就调整一次堆栈，总是使最近访问的那页的页面号保持在栈顶，然后根据当前被访问时间的近远，依次排列，栈底总是最近最久未使用的那页的页面号。,淘汰,65,作业固定占用4块主存,例如，某作业按下列页号访问：,66,作业,某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。请分别用FIFO,LRU和OPT算法计算缺页中断次数。,67,4.8.3CLock置换算法,CLock算法就是用得较多的一种LRU近似算法。,68,1、简单的CLock置换算法,这种算法的实质是：当需要置换一页时，选择在最近一段时间内最久未用的页予以淘汰，因此称为最近未用的算法NRU（NotRecentlyUsed）。,69,这种近似算法，要求为每一页设置一位访问位，再将内存中的所有页面都通过指针按FIFO链成一个循环队列。,当某页被访问时，访问位由硬件自动置“1”。我们可以根据访问位的状态来判断各个页面最近使用的情况。如果是“0”，就选择该页换出；若为1，则重新将它置为0，再按照FIFO算法检查下一个页面。,该算法是对FIFO算法的改进，考虑到页面是否被访问。,70,替换指针,总是指向最近被替换的页所在的存储块，缺页时从其后一块开始。,71,2、改进型CLock置换算法,1类（A=0，M=0），最近既未被访问，又未被修改，是最佳淘汰页。,2类（A=0，M=1），最近未被访问，但已被修改，不是很好的淘汰页。,3类（A=1，M=0），最近已被访问，但未被修改，可能再被访问。,既要考虑到页面的使用情况，还要考虑置换代价,4类（A=1，M=1），最近已被访问且被修改，可能再被访问。,根据访问位A和修改位M的组合来确定,72,改进型CLock算法，执行过程可分为以下三步：,（1）从指针的当前位置开始，扫描按先进先出循环队列，寻找A=0且M=0的第一类页面，将符合条件的第一个页面作为淘汰页，在第一次扫描期间A不改变。,73,（2）第一步失败，开始第二轮扫描，寻找A=0且M=1的第二类页面，将符合条件的第一个页面作为淘汰页。将所有经过的页面的访问位置0。,（3）第二步也失败，把指针返回到开始的位置，把所有的访问位A置为0，然后重复第一步，如还是失败，重复第二步，就一定能找到被淘汰的页。,74,改进型Clock算法的特点,该算法与简单Clock算法比较，可减少磁盘的I/O操作次数，但为了找到要淘汰的页面，可能需要经过几轮扫描，使该算法本身的开销有所增加。,75,4.8.4其它置换算法,1、最少使用（LeastFrequentlyUsed）置换算法（LFU）,既可实现LRU，也可实现LFU,为内存中的每个页面设置一个移位寄存器，用来记录页面被访问的频率，淘汰页是最少使用或是访问次数最少的页面。,ri最小的页就是最近一段时间使用最少的页面。,76,2、页面缓冲算法（PageBufferingAlgorithm）,PBA,采用可变分配和局部置换方式，采用FIFO置换算法,实际上,页面在内存中并不做物理上的移动,只是将页表中的表项移到上述链表;这种方法,修改或未修改的页面还在内存中,当该进程需要再次访问这些页面时,花费很小就能使这些页面返回到进程中;当被修改的页面数目达到一定值时,一起写回磁盘上,从而显著减少磁盘I/O的操作次数;,77,1、抖动产生的原因和预防方法,不适当地提高多道程序度，不仅不会提高系统吞吐量，反而会出现“抖动”现象，就是刚被换出页很快要被访问，需重新调入，因此在调入前要先选一页调出；而这个刚被换出的页，很快又要被访问，又要将它调入，如此频繁地更换页面，以致一个进程在运行时，把大部分时间花费在页面置换的工作上，我们称该进程发生了“抖动”。,性能问题分析,78,1、抖动产生的原因,调度程序一旦发现CPU的利用率降低，就立即提高多道程序度，引入新的进程参加运行，以提高CPU的利用率。当新进程进入内存时，由于空闲物理块队列中的物理块都用完了，只能从其它运行进程处去获得物理块，于是又将进一步加剧了另外一些进程的缺页情况，又使等待页面调入/调出的进程数目增多，这又降低了CPU的利用率。,79,那么为了提高CPU的利用率，调度程序又去引入新的进程，这就产生了恶性循环，使缺页率急剧地上升。这时候，运行进程的大部分时间都用于进行页面的换入/换出，几乎不能完成任何有效的工作，我们称这时的进程是处于“抖动”状态。,80,CPU利用率,多道程序度,从图中可看出CPU的利用率和多道程序度之间的关系。开始时，CPU的利用率随着程序度的提高而提高，达到某一峰值后，如果继续增加多道程序度，将产生抖动，从而导致CPU的利用率急