《《操作系统》课件页式存储管理.ppt》由会员分享，可在线阅读，更多相关《《操作系统》课件页式存储管理.ppt（38页珍藏版）》请在三一办公上搜索。
1、第四章 存储管理,页式存储管理页式虚拟存储技术段式存储管理,分区存储管理的缺点,“碎片”问题原因：作业要求连续的存储空间。解决办法：允许作业占据不连续的空间。,基本原理,“等分”内存。把内存划分为大小相同的“块”。把用户作业空间划分为大小相同的“页”。页和块的大小相同。在把作业加载到内存时，页和页之间不再连续。但页内连续。也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要时再加载。,地址变换,逻辑地址：页号+页内地址如何转变为内存物理地址？考虑：物理地址=块号*块长度+块内地址块长度一定，块内地地址与页内地址相同。问题变为：如何根据页号得到块号？页表：,页号,页内地
2、址,页表,地址变换过程,1、根据页号查页表，得到块号。2、根据块号和页内地址计算物理地址。3、例题：,例题：在分页存储管理系统中，用户编程空间共32个页，每页大小为1024B，内存为16KB。假定某一时刻用户页表如下，若逻辑地址为035E（H），求其所对应的物理地址。页号 物理块号 0 5 1 10 2 3 3 7分析：（1）根据题意，页内地址为10位，页号为5位。210=1024，25=32（2）根据给定的逻辑地址得到页号和页内地址。035E（H）=（0000001101011110）2 从左边数10位为页内地址，剩余为页号。页号为0。（3）根据页号查页表，得到块号为5。（4）将块号与块内地
3、址组合为物理地址：E（H）,页表的实现快表,从上述地址变换过程可以看出：CPU每取一条指令或数据，都必须经过页表。因此，页表的每一个表项都是一个动态重定位机构。如何实现页表，将影响系统的效率。方式：硬件实现：用寄存器组。但代价太高，特别是内存很大时，是不可能的。软件实现：将页表放在内存中。每取一条指令，要两次访问内存。,快 表,软硬件结合：将页表中使用最频繁的表项（页表的的一个子集）放在cache中。称为“快表”。cache也称为“联想寄存器”，它不是根据地址而是根据所存信息的全部特征或部分特征进行存取。在这里为页号。若要访问的页在cache中，则只需一次访问内存。若不在，则到内存中去找，同时
4、把新的页表表项写入cache。,例题：对于利用快表且页表存于内存的分页系统，假定CPU的一次访问内存时间为1s，访问快表时间忽略不计。如果85%的地址映射可直接通过快表完成，那么进程完成一次内存读写的平均有效时间是多少？分析：（1）若直接通过快表完成，则只需一次访问内存。（2）若不能，则需要两次访问内存。（3）平均时间=1*85%+2*15%,内 存 分 配,用户需求：需要多少块？内存空闲块的管理：位示图。位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态：0：空闲；1：已分配。,内存分配,块号与字号、字长的关系：系统的字长一定，内存块从0开始编号，则有：块号=字号*
5、字长+位号 字号=块号/字长（取整的意思）位号=块号 MOD 字长,用户作业请求：块数B,扫描位示图，查找为0的位,空闲块数B,N,无法分配,计算块号,建立页表,页式系统的内存保护和共享,保护：在页表上添加一个保护位。在做地址变换时，检查对页面的访问是否合法。共享：根据地址转换过程可知：如果在不同用户的页表中填上相同的页表表项（块号），就能够访问相同的内存空间。,块号,保护位,5 R,12 WR,5,5,5,用户1 用户2 用户3,5,5,页式虚拟存储技术,虚拟存储器：内存扩充技术，为用户提供一个比实际内存大得多的内存空间。实现虚拟的三个三个条件；程序中的哪些页已经加载内存。当要访问的页不在内
6、存时，如何将其掉如内存？若此时内存空间已满，如何选择换出的页？页式虚拟的基本原理：加载作业时，只加载那些最活跃的页，其余的页需要时再加载。“请求调页技术”和“预调页技术”。,一、如何知道哪些已在内存,在页表中添加一个标志位（中断位），标志该页是否已在内存：0：不在 1：在内存 块号 保护位 标志位,当要访问的页不在内存时,发生“缺页中断”。缺页中断的处理过程：保存现场在内存中找到一个空闲块。从磁盘上找到要调入的页。读磁盘到内存。恢复现场。重新调度运行。,在调入内存时，若内存已满,进行“页面替换”：从内存中选择一个页调出内存，为新调入的页让出空间。如果替换的不合适，则发生“抖动”或“颠簸”现象：
7、页在内外存之间频繁地调入调出，系统开销很大。页面替换算法：先进先出法（FIFO）：将最先调入内存的页调出内存。最近最少使用算法（LRU：least recently used）。将最近一段时间内没有用过的页调出内存。,页面替换算法,最近最少使用算法（LFU）：最近一段时间内使用次数最少的页调出内存。为每一个在内存的页设置一个计数器，选择计数器中的值最小的调出。最优算法（OPT）：把将来一段时间内被使用的可能性最小的页调出内存。利用预测方法先来预测将来的使用情况。注意：LRU、LFU之间的区别。,例 题：有一个分页式虚拟存储管理系统，每个进程在内存有3页数据区、1页程序区，刚开始时数据区为空。现
8、有一个进程有以下访问序列：1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系统采用：（1）最近最少使用（LRU）淘汰算法（2）先进先出（FIFO）淘汰算法请计算缺页次数和发生缺页中断后的淘汰页号。分析：（1）采用FIFO方法：将内存中的页按进入的先后次序排队，后来的加入队尾，先来的先出去。,（1）FIFO算法访问队列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 1 5 4 2 2 3 5 1内 存 1 5 5 4 2 2 3 1 5 4 4 2 3 5 1 1 5 4 4 2 3 1 5 5 4 2 3缺页中断 页面替换 1 5 4 2
9、3 1 5 4 3答案：缺页中断的次数为12次，页面替换的次序是：1 5 4 2 3 1 5 4 3。,（2）LRU算法：访问队列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 3 5 4 2 2 3 5 1内 存 1 5 5 1 2 2 2 1 5 4 4 2 3 5 1 1 4 1 1 1 2 1 5 5 4 4 3缺页中断 页面替换 5 4 3 2 1 5 2 4答案：缺页中断的次数为11次，页面替换的次序是：5 4 3 2 1 5 2 4,工作集模型,虚拟存储技术的理论基础。局部性原理：进程往往会不均匀地高度局部化地访问内存。时间局部性：刚刚被
10、访问的页，很可能在不久的将来还要访问。例如：循环；子程序；栈；用户记数和总计的变量等。空间局部性：某个页面被访问，很可能它相临的页也要被访问。例如：数组遍历；代码程序的执行；等等。工作集：进程活跃地访问的页面的集合。,工作集模型（续）,工作集存储管理策略力求把活跃程序的工作集保存在内存中。从上图可以看出：仅当一个进程的全部工作集都在内存时才能运行该作业。,h,W(h),h0,页式存储管理的缺陷,从理论上讲，不同用户共享程序段或数据很简单，只需在不同用户的页表中填上相同的块号，经地址变换后，一定能访问相同的内存空间。但是，由于页的划分是由系统自动进行的，很可能用户要共享的页分布在不同的页中，给共
11、享和保护造成了麻烦。,段式存储管理,用户程序观点：一个程序由若干程序段组成，每一个段具有相对独立的功能。段的概念：一个逻辑意义完整的信息单位。一个程序由若干个段组成。各段长度不同。段式存储管理的原理：作业的地址空间由若干个逻辑分段组成，每个分段有自己的名字，在内存中占据一个连续的区域。但是段和段之间可以是不连续的。思考：采用什么策略为段分配内存？,地址变换,逻辑地址：段号+段内地址注意：该逻辑地址是二维地址。因为段在内存中占据一个连续的区域，如果知道该段在内存中的起始地址，就可以得到物理地址：物理地址=起始地址+段内地址段表：段号 起始地址 长度,地址变换的过程,1、硬件支持：段表基址寄存器和
12、段表长度寄存器。因为段表是保存在内存中的。2、步骤：（1）检查段号是否：段号段表长度寄存器若否，则产生“地址越界”中断。（2）根据段号和段表基址寄存器的值取段表表项，得到段基址和段长度。（3）判断段内地址是否越界：段内地址段长度。（4）物理地址=基址+段内地址,段的共享和保护,共享：在不同用户的段表中添入相同的段表表项。保护：在段表中添加一个保护位。思 考：为什么段式存储管理比页式存储管理更容易实现共享和保护？,段式和页式的问题和优点,页式：解决了碎片问题。但不便于用户作业的共享和保护。由于用户调入的页可能只用到其中的一部分，因此系统的效率不高。段式：很好地解决了共享和保护问题，系统效率高；但
13、由于采用可变分区方式为段分配内存，存在碎片问题。,段页式存储管理,也称为“混合式存储管理”，将页式和段式的优点结合起来。原理：程序先分段，段内再分页。每个段在内存中拥有一个页表。用户看到的是段，即共享时采用段。内存管理采用页，因此消除了碎片。,地址变换,逻辑地址：段号+页号+页内地址段表：段号 页表起始地址页表：页号 块号注意：每一个段都有一个页表。硬件支持：段表基址寄存器和段表长度寄存器。,段号,页号,页内地址,本章小结内存管理功能,内存的分配和回收地址变换内存共享与保护虚拟存储器任何一种管理策略，都需要解决上述问题。解决上述问题的方法，就是存储管理的内容。,本章小结内存管理技术,单道连续存
14、储管理分区存储管理固定分区存储管理可变分区存储管理页式存储管理段式存储管理段页式存储管理,课 后 练 习,1、在一个分页式虚拟存储管理系统中，每个进程在内存中有3个数据区，2个程序区。现有一进程，其数据的第1、2，3页已装入内存。现有一个访问序列：1、3、4、1、2、5、4、3、2、1、4、3、5、1，已知系统采用最近最少使用（LRU）淘汰算法。请给出缺页次数和发生缺页中断后的淘汰页号。,2、现有一个作业，在段式存储管理的系统中已为其分配了主存并建立了段表，如下所示：段号 内存起始地址 长度 0 1760 680 1 1000 160 2 1560 200 3 2800 890（1）说明段式存储管理的地址重定位过程。（2）计算该作业访问0，500，1，300，3，655，5，120时的绝对地址。,在一个页式虚拟存储管理系统中，用户空间有32个页，每页为1KB，主存为16KB。试问：（1）逻辑地址的有效位是多少？（2）物理地址的有效位是多少？（3）假定某时刻为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址2500转变为物理地址。,随堂练习,
