存储管理5请求页式管理请求段式管理.ppt

1,第四章存储器管理,4.6 虚拟存储器 4.7 请求分页存储管理方式4.8 页面置换算法 4.9 请求分段存储管理,2,复习,虚拟存储器的引入,程序的局部性规律，程序往往会不均匀地高度局部化地访问内存。,这种特性使得程序的执行在一段时间内被限制在作业的某一局部范围。,（1）时间局限性:最近被访问的存储位置，很可能不久的将来还要被访问。,(2)空间局限性:存储访问有集成一组的倾向，以致一旦某个位置被访问到，很有可能它附近的位置也要被访问。,3,虚拟存储器的定义？,所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。,虚拟存储器的大小受计算机系统地址结构和可用外存数量的限制，与实际内存单元的数量无关。,4,页式虚拟存储系统,分页系统的基础上，增加了请求调页功能、页面置换功能所形成的分页请求系统。,请求分段系统,在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。,5,4.7 请求分页存储管理方式,在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,请求分页存储管理方式是建立在纯分页基础上的.其基本思想是？,6,4.7.1 请求分页中的硬件支持,一、页表机制的改进,(1)状态位（驻留位）P:该页是在内存还是在外存(2)访问字段位A：记录本页在一段时间内被访问的次数;根据访问位来决定淘汰哪页（由不同的算法决定）(3)修改位M:该页调入内存后是否在被修改过(4)外存地址:该页在外存上的地址,通常为外存物理块号.,7,2、缺页中断机构,在请求分页系统中，当要访问的页面不在内存时，硬件发一个缺页中断，转交OS处理。,3、地址变换机构,请求分页系统中的地址变换机构是以分页系统的地址变换机构为基础的，还增加了产生缺页中断、处理缺页中断，置换等功能。,8,4.7.2 内存分配策略和分配算法,物理块的分配策略,1)、固定分配局部置换,2)、可变分配全局置换,3)、可变分配局部置换,9,4.7.3 调页策略,1、何时调入页面,1、预调页策略,2、请求调页策略,用于首次调入,10,最佳置换算法和先进先出算法,4.8 页面置换算法,假定作业p共计n页，而系统分配给它的主存块只有m块（m,n均为正整数，mn），即最多只能容纳m页。如果程序p在运行中成功的访问次数为s,不成功的访问次数为f,那么，其总的访问次数a=s+f，若定义f=f/a，称f 为缺页中断率。,缺页中断率:,11,影响缺页中断次数的因素,（1）分配给进程的物理页面数物理页面数多，缺页中断少，反之，则缺页中断多物理页面数多，进程数少（影响系统效率），反之，则进程数多（缺页中断多）根据试验分析：对一共有n页的进程来说，只要能分到n/2块内存空间，就可使系统获得最高效率；,（2）页面本身的大小页面大，进程的页数少，一页的信息就大，缺页中断次数减少；不同的计算机系统，有不同页面大小；,12,例：程序要把128128的数组初值置“0”，数组中每一个元素为一个字，假定页面大小为128个字，数组中的每一行元素存放一页，能供该程序使用的主存块只有1块。初始时第一页在内存；,程序编制方法1：For j:=1 to 128 For i:=1 to 128 Aij:=0;按列：缺页中断次数：1281281,程序编制方法2：For i:=1 to 128 For j:=1 to 128 Aij:=0;按行：缺页中断次数 128-1,（3）程序的编制方法,可见：缺页中断率与程序的局部化程度密切相关。希望编制的程序能经常集中在几个页面上；,13,14,(4)页面淘汰算法理论的页面淘汰算法应该选择的被淘汰页面将是以后永不使用的，或在最长(未来)时间内不再被访问的页面。（OPT算法）。实际上，可以用理论的页面淘汰算法作标准，选择其它较好的页面淘汰算法,页面淘汰算法选择不合适，会使系统“抖动”,15,刚被换出的页很快又被访问，需要重新调入，为此又需再选出一页调出；而刚被换出的页，很快又要被访问，又需把它调入，如此频繁地更换页面，以致一个进程在运行中，把大部分时间花费在完成页面的置换工作上，使得调度页面所需时间比进程实际运行的时间还多.我们称该进程发生了“抖动”。,抖动,16,最佳置换算法是由Relady在1966年提出的，这种算法选择的被淘汰页面，将是永不使用的，或在最长时间内不再被访问的页面。“最佳”是指对于任意的内存固定空间m和程序 p,缺页中断率最小。它是一个理论上的算法。,1、最佳置换算法（OPT）,17,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串。,采用最佳置换算法，只发生了6次页面置换，发生了9次缺页中断。缺页率=9/21,18,2、先进先出页面置换算法（FIFO）,这是最早出现的置换算法，这种算法总是淘汰最先进入内存的页面，选择在内存中驻留时间最久的页面予以淘汰。,19,采用FIFO算法进行页面置换时的情况。,一共发生了12次页面置换，比最佳置换算法多了1倍。缺页率15/21=3/4，15次页面中断。,20,FIFO是根据各个页面调入内存的时间来选择被淘汰页面，但页面调入的先后并不能反映页面的使用情况。FIFO算法只是在按线性顺序访问地址空间才是理想的。未考虑到程序的动态特性。可能引起异常。,21,先进先出置换算法的一个异常现象：对于一些特定的页面访问序列，先进先出置换算法有随着分给的页架数增加，缺页频率也增加的异常现象。,A B C D A B E E E C D D A B C D A B B B E C C A B C D A A A B E E+,页面访问序列,A B C D A B E A B C D E,九次缺页,三个页面,A B C D D D E A B C D E A B C C C D E A B C D A B B B C D E A B C A A A B C D E A B+,页面访问序列,十次缺页,四个页面,22,4.8.2 最近最久未使用LRU置换算法,1、LRU（Least Recently Used）算法的描述,基本思想：基于程序的局部性原理，在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用，反之，已经很久没有使用的页面很有可能在未来较长一段时间内不会使用；因此，在缺页发生时，淘汰掉最久未使用的页；,选择淘汰的页面是最近最久未使用,23,我们用“最近的过去”来直接推断“最近的将来”。,发生了9次页面置换。,标明访问时间,24,2、LRU算法的硬件支持,为了实现LRU算法必须解决：（1）一个进程在内存中的各个页面各有多久时间未被进程访问；（2）如何快速地知道哪一页是最近最久未使用的页面。需要两类硬件之一：寄存器 或 栈,25,1、寄存器,为每个在内存中的页面配置一个移位寄存器，表示为：R=Rn-1Rn-2Rn-3R1R2R0,当进程访问某物理块时，要将相应的寄存器的Rn-1位置为1。,定时信号将每隔一定时间将寄存器右移一次，把n位寄存器的数看作是一个无符号的整数，最近最久未使用的页面就对应着具有最小数值的寄存器。,用于记录某进程在内存中各页的使用情况。,26,2、栈,LRU置换算法可用堆栈的方法来实现。,栈中存放当前内存中的页面号，每当访问一页时就调整一次堆栈，总是使最近访问的那页的页面号保持在栈顶，然后根据当前被访问时间的近远，依次排列，栈底总是最近最久未使用的那页的页面号。,淘汰,27,作业固定占用4块主存,例如，某作业按下列页号访问：,28,4.8.3 CLock置换算法,CLock算法就是用得较多的一种LRU近似算法。,1、简单的CLock置换算法,当需要置换一页时，选择在最近一段时间内最久未用的页予以淘汰，因此称为最近未用的算法NRU（Not Recently Used）。,29,这种近似算法，要求为每一页设置一位访问位，再将内存中的所有页面都通过指针按FIFO链成一个循环队列。,当某页被访问时，访问位由硬件自动置“1”。根据访问位的状态来判断各个页面最近使用的情况。如果是“0”，就选择该页换出；若为1，则重新将它置为0，再按照FIFO算法检查下一个页面。,30,替换指针,总是指向最近被替换的页所在的存储块，缺页时从其后一块开始。,31,2、改进型CLock置换算法,1类（A=0，M=0），最近既未被访问，又未被修改，是最佳淘汰页。,2类（A=0，M=1），最近未被访问，但已被修改，不是很好的淘汰页。,3类（A=1，M=0），最近已被访问，但未被修改，可能再被访问。,既要考虑到页面的使用情况，还要考虑置换代价,4类（A=1，M=1），最近已被访问且被修改，可能再被访问。,根据访问位A和修改位M的组合来确定,32,改进型CLock算法，执行过程可分为以下三步：,（1）从指针的当前位置开始，扫描按先进先出循环队列，寻找A=0且M=0的第一类页面，将符合条件的第一个页面作为淘汰页，在第一次扫描期间A不改变。,33,（2）第一步失败，开始第二轮扫描，寻找A=0且M=1的第二类页面，将符合条件的第一个页面作为淘汰页。将所有经过的页面的访问位置0。,（3）第二步也失败，把指针返回到开始的位置，把所有的访问位A置为0，然后重复第一步，如还是失败，重复第二步，就一定能找到被淘汰的页。,34,改进型Clock算法的特点,该算法与简单 Clock算法比较，可减少磁盘的I/O操作次数，但为了找到要淘汰的页面，可能需要经过几轮扫描，使该算法本身的开销有所增加。,35,4.8.4 其它置换算法,1、最少使用（Least Frequently Used）置换算法（LFU）,既可实现LRU，也可实现LFU,为内存中的每个页面设置一个移位寄存器，用来记录页面被访问的频率，淘汰页是最少使用或是访问次数最少的页面。,ri最小的页就是最近一段时间使用最少的页面。,36,2、页面缓冲算法（Page Buffering Algorithm）,PBA,采用可变分配和局部置换方式，采用FIFO置换算法,实际上,页面在内存中并不做物理上的移动,只是将页表中的表项移到上述链表;这种方法,修改或未修改的页面还在内存中,当该进程需要再次访问这些页面时,花费很小就能使这些页面返回到进程中;当被修改的页面数目达到一定值时,一起写回磁盘上,从而显著减少磁盘I/O的操作次数;,37,1、抖动产生的原因和预防方法,不适当地提高多道程序度，不仅不会提高系统吞吐量，反而会出现“抖动”现象，就是刚被换出页很快要被访问，需重新调入，因此在调入前要先选一页调出；而这个刚被换出的页，很快又要被访问，又要将它调入，如此频繁地更换页面，以致一个进程在运行时，把大部分时间花费在页面置换的工作上，我们称该进程发生了“抖动”。,性能问题分析,38,1、抖动产生的原因,调度程序一旦发现CPU的利用率降低，就立即提高多道程序度，引入新的进程参加运行，以提高CPU的利用率。当新进程进入内存时，由于空闲物理块队列中的物理块都用完了，只能从其它运行进程处去获得物理块，于是又将进一步加剧了另外一些进程的缺页情况，又使等待页面调入/调出的进程数目增多，这又降低了CPU的利用率。,39,那么为了提高CPU的利用率，调度程序又去引入新的进程，这就产生了恶性循环，使缺页率急剧地上升。这时候，运行进程的大部分时间都用于进行页面的换入/换出，几乎不能完成任何有效的工作，我们称这时的进程是处于“抖动”状态。,40,CPU利用率,多道程序度,从图中可看出CPU的利用率和多道程序度之间的关系。开始时，CPU的利用率随着程序度的提高而提高，达到某一峰值后，如果继续增加多道程序度，将产生抖动，从而导致CPU的利用率急剧下降。,41,2、抖动的预防,核心问题:选择合适的页面置换算法。分配给进程合适的物理页面数。调整多道程序度。,1、采取局部置换策略,2、在CPU调度程序中引入工作集算法,3、挂起若干进程,页面淘汰算法不合理分配给进程的物理页面数太少,42,4.9 请求分段存储管理方式,请求分段系统是在分段系统的基础上，增加了请求调段及分段置换功能后形成的，以分段作为换入、换出的单位。需要硬件支持共享与保护,43,4.9.1 请求分段中的硬件支持,请求分段管理需要的硬件支持:段表机制、缺段中断机构、地址变换机构。,44,1、段表机制,请求分段的段表项,（1）存取方式：用于标识本分段的存取属性是只执行、只读，还是允许读/写。,45,（2）访问字段A：用于记录该段被访问的频繁程度。,（3）修改位M：用于表示该页进入内存后，是否已被修改过。,（4）存在位P：用于指示本段是否已调入内存。,46,（5）增补位：这是请求分段式管理中特有的字段，用于表示本段在运行过程中，是否进行过动态增长。,（6）外存始址：指示本段在外存中的起始地址，即起始盘块号。,47,2、缺段中断机构,阻塞请求进程,虚段不在内存,从外存读入段,修改段表及内存空区链,唤醒请求,返回,空间容量总和能否满足？,淘汰一个或几个实段，以形成一个合适空区,空间拼接，以形成一个合适的空区,否,否,是,是,48,3、地址变换机构,有效地址,分段系统的地址变换机构中应用增加缺段中断请求以及处理等功能。,49,访问SW,W段长,符合存取方式,段S在内存,修改访问字段，如写访问，置修改位=1,形成访问主存地址(A)=(内存始址)+(位移量W),返回,分段越界中断处理,分段保护中断处理,缺段中断处理,N,N,N,Y,Y,Y,50,4.9.2 分段共享与保护,进程1,段表,editor,data1,段长基址,160 80,40 240,editor,data2,段长基址,160 80,40 380,80,240,editor,data1,data2,380,420,280,分段管理容易实现共享,51,一、共享段表,共享段表,段名,段长,内存始址,状态,外存始址,共享进程计数count,状态,进程名,进程号,段号,存取控制,共享段表项,在系统中配置一张共享段表，每个共享段在共享段表中都有一个表项，记录共享段的段号、段长、内存始址、存在位等，以及共享这个分段的每个进程的情况。,52,1、共享进程计数count,整型变量count是为了记录有多少个进程需要共享该分段。,2、存取控制字段,3、段号,对于同一个共享段，不同的进程可用不同的段号去共享该段。,53,2、共享段的分配与回收,1、共享段的分配,分配：,第一个进程,以后的进程,分配内存空间，调入共享段，进程的段表加一该共享段的表项，在共享段表中加一个表项，置count=1。,进程的段表加一该共享段的表项，在共享段表中加该进程的有关内容，置count=count+1。,54,2、共享段的回收,回收：,取消进程段表中有关共享段的表项,回收物理内存,取消共享段表中有关共享段的相应表项。,count-1=0,count-10,取消进程段表中有关共享段的表项,取消共享段表中有关该进程的相应内容。,55,3、分段保护,在分段系统中，各个分段在逻辑上是独立的，因此信息保护也是比较容易实现的。一般采用以下方法来进行分段保护：,段表：段长,段表寄存器：段表长度,1、越界检查,56,2、存取控制检查,在段表的每个表项中，都设置了一个“存取控制”字段来规定对该段的访问方式。,通常的访问方式有：（1）只读：只允许读访问。（2）只执行：只允许执行，不允许读，也不允许写。（3）读/写：允许进行读写访问。,作业2,说明请求分段系统中的缺段中断处理过程。,57,