操作系统原理第七章.ppt

1、1,第七章 主存管理,2,7.4 页式存储管理7.4.1 页式系统应解决的问题,一、问题的提出 分区存储管理的主要问题是碎片问题，拼接技术消耗大量的CPU时间。 主要原因：用户程序装入内存时整体装入。 为解决这个问题，提出了分页存储管理技术。,3,7.4 页式存储管理7.4.1 页式系统应解决的问题,二、分页的概念 程序地址空间分成大小相等的单位，称为页； 内存地址空间分成与页大小相等的单位，称为块； 程序以页为单位装入内存； 页的大小是为2n ,通常为1KB，2KB，nKB等。,4,7.4 页式存储管理7.4.1 页式系统应解决的问题,5,7.4 页式存储管理7.4.1 页式系统应解决的问题

2、,分页的好处： 没有外碎片，每个内碎片不超过页大小； 实现了由连续存储到非连续存储的飞跃。,6,7.4 页式存储管理7.4.1 页式系统应解决的问题,页式存储管理要解决如下问题： 1、页式存储管理系统的地址映射 2、调入策略 3、淘汰策略 4、放置策略,7,7.4 页式存储管理7.4.2 页式地址变换一、页表,一、页表 页表是页式存储管理的数据结构。 主要包括：页与内存块的对应关系,8,7.4 页式存储管理7.4.2 页式地址变换一、页表,9,7.4 页式存储管理7.4.2 页式地址变换二、虚地址结构,二、程序地址(虚地址、逻辑地址) 组成：页号P、页内地址W。 页的大小是区别页号和页内地址的

3、依据：页内地址占虚地址的低位部分，页号占虚地址的高位部分。 假定页的大小1024字节，虚地址占用2个字节 P W 15 10 9 0,10,7.4 页式存储管理7.4.2 页式地址变换二、虚地址结构,例1：页面大小1KB，虚地址为3BADH，求P和W 例2：页面大小2KB，虚地址为3BADH，求P和W,11,7.4 页式存储管理7.4.2 页式地址变换 二、虚地址结构,例1：页面大小1KB，虚地址为3BADH，求P和W,P = 0EHW = 3ADH,12,7.4 页式存储管理7.4.2 页式地址变换二、虚地址结构,例2：页面大小2KB，虚地址为3BADH，求P和W,P = 07HW = 3A

4、DH,13,7.4 页式存储管理7.4.2 页式地址变换 三、页式地址映射,如何实现虚地址物理地址变换？,14,7.4.2 页式地址变换 三、页式地址映射,页式地址变换,15,7.4 页式存储管理7.4.2 页式地址变换 三、页式地址映射,页大小：2K；机器地址长度：16位,16,7.4 页式存储管理7.4.2 页式地址变换 三、页式地址映射,程序地址：连续； 物理地址：不连续。 页式地址映射：透明实现程序地址到物理地址的转换。,17,7.4 页式存储管理7.4.2 页式地址变换 三、页式地址映射,例： 系统采用页式存储管理，作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，

5、试将虚地址0AFEH转换成内存地址。,18,7.4 页式存储管理7.4.2 页式地址变换 三、页式地址映射,虚地址0AFEH 0000 1010 1111 1110,MR0100 1010 1111 1110 4AFEH,P1 W010 1111 1110,19,7.4 页式存储管理7.4.2 页式地址变换 三、页式地址映射,例： 系统采用页式存储管理，作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145转换成内存地址。,20,7.4 页式存储管理7.4.2 页式地址变换 三、页式地址映射,虚地址 3412 P3412 2048 1 W 3412 mod 2

6、048 1364 MR=9*2048+1364=19796 虚地址3412的内存地址：19796,21,7.4 页式存储管理7.4.2 页式地址变换四、联想存储器,在页式存储技术中，每访问一次内存，要做两次访问内存的工作： 查页表时要作一次访问内存的工作； 根据得到的物理地址，访问内存。 问题： 存取速度降低一倍，将会影响整个系统的使用效率。 解决办法： 采用联想存储器（关联存储器）技术加快查表的速度。,22,7.4.2 页式地址变换四、联想存储器,23,7.4 页式存储管理7.4.3 请调策略一、问题的提出,页式存储管理提高了内存的利用效率，但并不为用户提供虚存； 换句话说，当一个用户程序的

7、页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。 即用户程序将受到物理内存大小的限制。 为了解决这个问题，提出请求分页存储管理技术。,24,7.4 页式存储管理7.4.3 请调策略二、请求分页概念,当一个用户程序调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行； 在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求； 系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。,25,7.4 页式存储管理7.4.3 请调策略三、请求分页要解决的问题,1、如何发现执行的程序或访问的数据不在内存； 2、程序或数据什么时候调入

8、内存：调入策略； 3、当一些页调入内存时，内存没有空闲内存时，将淘汰哪些页：淘汰策略。,26,7.4 页式存储管理7.4.3 请调策略四、数据结构,页表增加相应内容：该页是否在内存，在外存的位置，在内存的时间长短等。 中断位：0 表示该页在内存，1表示该页不在内存 引用位：0 表示最近没有进程访问，1表示最近有进程访问 修改位：0 该页调入内存后没有修改，1页调入内存后修改过,27,7.4 页式存储管理7.4.3 请调策略四、数据结构,28,7.4 页式存储管理7.4.3 请调策略五、调入策略,1、预调 系统根据作业（进程）运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运

9、行的过程中就不会出现缺页中断。 这样方法从表面上看起来很好，但系统无法预计系统中作业的运行情况，难以实现。 2、请调 进程在执行过程中，发现要访问的内容不在内存，向系统提出调入请求，系统响应用户的请求。,29,7.4 页式存储管理7.4.3 请调策略五、调入策略,缺页中断 在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。 操作系统收到此中断信号后，调出缺页中断程序，根据页表中给出的外存地址，将该页调入内存： 如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应表项； 若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。,30,7

10、.4 页式存储管理7.4.3 请调策略五、调入策略,缺页中断与普通中断的比较： 相同： 保护CPU现场中断处理恢复现场 不同： 缺页中断在指令执行期间产生和处理，而不是在指令执行完毕后。所缺页面调入之后，重新执行被中断的指令。 一条指令的执行可能产生多次缺页中断。,31,7.4 页式存储管理7.4.4 淘汰策略,一、置换算法 用来选择淘汰哪一页的规则叫做置换算法。 二、颠簸 抖动。系统频繁做页面置换操作。 置换算法应尽可能减少抖动现象的发生。,32,假定程序p共有n页，系统分配给它的内存只有m块。 1mn 访问的页在内存，称访问成功，否则为失败。 a=s+f a:访问的总次数 s：访问成功的次

11、数 f：访问失败的次数,7.4 页式存储管理7.4.5 几种置换算法一、最佳算法,33,7.4 页式存储管理7.4.5 几种置换算法一、最佳算法,缺页中断率： f = f/a f可表示成： f f(r,m,p） f与以下因素有关： r: 调度算法； m:内存固定空间大小； p:程序。,34,7.4.5 几种置换算法一、最佳算法,最佳算法： 对于任何m和p，可以找出r(调度算法)，使得缺页中断率f最小。 即：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。 这种算法是不可能实现的。 但其理论可作为衡量各种具体算法的标准。,35,7.4 页式存储管

12、理7.4.5 几种置换算法二、先进先出算法,先进先出算法： 先进入内存的页，先退出内存。 实质： 淘汰在内存驻留时间最长的页。 思想： 最早调入内存的页，不再被使用的可能性比近期调入内存的大。 这种算法简单，实现容易。,36,7.4 页式存储管理7.4.5 几种置换算法二、先进先出算法,问题： 采用FIFO算法，分配的页面数增多，缺页率会减少吗？,37,7.4 页式存储管理7.4.5 几种置换算法二、先进先出算法,进程P有5页，访问页的顺序：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；,后,先,38,

13、7.4 页式存储管理7.4.5 几种置换算法二、先进先出算法,如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；,后,先,39,7.4 页式存储管理7.4.5 几种置换算法二、先进先出算法,Belady现象 采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。 Belady现象的原因 FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。,40,7.4 页式存储管理7.4.5 几种置换算法二、先进先出算法,FIFO算法的Belady现象,41,7.4 页式存储管理7.4.5

14、几种置换算法三、最久未使用算法（LRU算法）,算法实质： 当需要淘汰一页时，选择最长时间未使用的页。 思想： 如果某页被访问，可能马上还要被访问； 相反，如果某页长时间未被访问，它可能最近也不可能被访问。,42,7.4 页式存储管理7.4.5 几种置换算法三、最久未使用算法（LRU算法）,算法的实现（软件）： 设置一个活动页面栈； 当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。 淘汰一页时，总是从栈底抽出一个页号，它就是最久未使用的。,43,7.4 页式存储管理7.4.5 几种置换算法四、算法示例：先进先出算法,已依次调入内存的页：1、2、4，每个进程占3

15、个内存块。 执行顺序：1，2，4，5，2，3，5，1，4，5,缺页中断率f = 5 / 10 = 50%,44,7.4 页式存储管理7.4.5 几种置换算法四、算法示例：LRU算法,已依次调入内存的页：1、2、4，每个进程占3个内存块。 执行顺序：1，2，4，5，2，3，5，1，4，5,缺页中断率f = 4 / 10 = 40%,45,7.4 页式存储管理7.4.6 页式系统的存储保护,1、越界保护 访问页号满足判别式为合法访问，否则非法： 0页号用户程序的总页数 2、存取控制 在页表中增加存取控制位，表示该页的存取控制权限，如r表示可读，w表示可读可写，e表示可执行。,46,7.5 段式系统

16、,一个用户程序往往由几个程序段（主程序、子程序和函数）组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。 程序地址的组成：S：W 例: S1：XXXX S2：XXXX S3：XXXX,47,7.5 段式系统,48,7.5 段式系统,段式地址变换,49,7.5 段式系统,段式地址变换举例,50,7.5 段式系统,段表结构？,51,7.5 段式系统,页式管理和段式管理的比较： 分页是出于系统管理的需要，分段是出于用户应用的需要。 页大小是系统固定的，而段大小则通常不固定。 逻辑地址表示： 分页是一维的，各个模块在链接时必须组织成同一个地址空间； 分段是二维的，各个模块在链接时可以每

17、个段组织成一个地址空间。 通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。,52,7.6 段页式系统,段页式系统： 在段式系统中，若段内分页，称为段页式系统。 地址结构： 段号s，页号p和页内相对地址d。,53,段表、页表与内存的关系,54,7.6 段页式系统,段页式地址变换,55,地址变换过程： 由虚拟地址到物理地址经过三次访问： 第一次：访问段表，得到页表起始地址； 第二次：访问页表，得到主存块号； 第三次：将主存块号和页内位移组合，得到物理地址。 如何提高效率？,7.6 段页式系统,56,地址变换过程： 采用联想寄存器机制。 快速联想寄存器：存放当前最常用的段号s、页号p

18、和对应的内存块号。 地址变换：在通过段表、页表进行内存地址查找的同时，根据快速联想寄存器查找其段号和页号。 找到，直接把快速联想寄存器中的值与页内相对地址d拼接起来得到物理地址。 经验表明：在快速联想寄存器中装有1/10左右的段号、页号及页面的段页式管理系统，可以通过快速联想寄存器找到90%以上的所要访问的内存地址。,7.6 段页式系统,57,段页式地址变换过程（联想寄存器机制）,7.6 段页式系统,58,7.7 UNIX系统存储管理7.7.1 概述,早期UNIX系统采用对换技术实现虚拟存储管理。 进程的存储映象可以在内存和交换区之间传递，称为对换； 目前主要采用请求分页与对换相结合的存储管理

19、。,59,7.7 UNIX系统存储管理7.7.2 对换空间的管理,功能： 对换设备上的空间管理； 将进程换入内存； 将进程换出内存。,60,7.7 UNIX系统存储管理7.7.2 对换空间的管理,系统盘的结构：,61,7.7 UNIX系统存储管理7.7.3 对换进程,对换进程就是0号进程，它一个永远处于核心态的进程。其任务是将进程的映象在内存和对换区之间传递。,62,7.7 UNIX系统存储管理7.7.3 对换进程,（一）进程换入 当内存空闲时，0号进程将对换区中处于就绪状态进程的映象调入内存，直到内存满，或者是对换区中已经没有处于就绪状态的进程。 调入就绪进程的依据：进程在对换区中驻留的时间。 每次调入一个在对换区中驻留时间最长的进程映象进入内存。,63,7.7 UNIX系统存储管理7.7.3 对换进程,（二）进程换出 当内存空间不足时，0号进程将内存中某些进程换到对换区。 不能换出的进程： 核心态的进程（UNIX核心） 处于创建状态的进程 上锁的进程 在