操作系统课件-请求分课件

1、操作系统课件-请求分实存管理 具有整体性、驻留性及连续性三种特性的存储器管理方法，叫实存管理。我们学习过的无论是分区管理，分页管理，或分段管理，还是段页式管理，都属于实存管理。 实存管理的所谓整体性是指一个作业的全部实体在执行之前必须被整个地装入内存，也就是说，如果一个作业的逻辑地址空间大于内存的用户区时就不能执行。操作系统课件-请求分 驻留性是指作业一旦进入内存便一直驻留在内存区直到运行完毕。 连续性，顾名思义，是指给作业分配的一片连续的内存空间。 整体性、驻留性及连续性这三种特性不利于内存空间的有效利用。操作系统课件-请求分虚拟存储器 虚拟存储器（Virtual Memory），简称虚存，

2、是指对内存的虚拟，一种实际并不存在的内存空间，包括一级存储器概念和作业地址空间概念。虚拟并不是无限的，取决于机器的CPU地址结构，虚存容量不能大于外存容量。操作系统课件-请求分请求分页管理请求分页管理 请求分页管理是动态分页管理，是在静态分页管理基础上发展而来的。在简单分页管理中，如果作业所要求的页面数比内存空闲的块数多，则该作业不能装入运行。在虚拟存储器技术的支持下，可以进行请求分页管理。 那么请求分页管理的基本思想是什么？作业要访问的页面不在内存时，该如何处理？如何知道哪些页面在内存，哪些不在？如何决定把作业的哪些页面留在内存中呢？将虚页调入内存时，没有空闲块又怎么处理？ 在虚拟存储系统中

3、，将对逻辑空间和物理空间的考虑截然分开，逻辑空间的容量由系统提供的有效地址长度决定。操作系统课件-请求分 请求分页管理就能实现这种虚存空间，基本方法是在分页管理的基础上，在作业开始执行前，只装入作业的一部分页面到内存，其它的页面在作业执行过程中根据需要，动态地从辅存装入内存。当内存块已经占满时，再根据某种策略交换出部分页面到辅存。 根据作业的执行情况装入作业的部分实体，显然节省了内存空间。 请求分页管理和分页管理的数据结构、地址映射和存储保护、存储分配与回收等都类似，但请求分页管理的实现过程复杂很多，需要由硬件和软件的相互配合才能完成。1. 请求调入及缺页中断处理请求调入及缺页中断处理2. 淘

4、汰算法淘汰算法3. 抖动与工作集抖动与工作集操作系统课件-请求分请求分页存储管理请求分页存储管理铺垫铺垫作业在运行期间的各个阶段，多数作业只使用全作业在运行期间的各个阶段，多数作业只使用全部地址空间的一部分。部地址空间的一部分。例如用户编制的出错处理例如用户编制的出错处理子程序，在作业正常运行情况下不会执行这些程子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。序，没有必要把它们调入内存。即程序中往往会即程序中往往会有一些彼此互斥的部分不是每次运行时都能执行有一些彼此互斥的部分不是每次运行时都能执行到。到。 程序的局部性。程序的局部性。顺序执行的指令和线性结构的数据(如数组

5、)。它们通常被限定在某一连续区域。一旦某一位置被访问后，那么它附近的位置很快也会被访问。操作系统课件-请求分 基于上述情况，就没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为虚拟存储器。操作系统课件-请求分虚拟存储器的概念 P61虚拟存储技术的基本思想是利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，以有效地支持多道程序设计的实现和大型程序运行的需要，

6、增强系统的处理能力。请求分页系统支持虚拟存储技术操作系统课件-请求分 请求分页存储管理请求分页存储管理名词名词作业的逻辑地址空间划分的页，称为虚页虚页主存称为实存实存实存中的块称为实页实页操作系统课件-请求分 请求分页存储管理请求分页存储管理基本原理请求分页系统对地址空间和内存空间的管理采用与分页存储管理系统相同的方式，但是它只将作业的部分页面装入内存，便可开始运行作业，作业的其他部分被存放在辅助存储器上。操作系统课件-请求分请求分页存储管理必须解决的问题请求分页存储管理必须解决的问题一个作业不全部装入，该作业能否开始运行，并运行一段时间？当程序要访问的某页不在内存时，如何发现这种缺页情况？发

7、现后应如何处理？缺页时，所需的页面从何处装入？装入到何处？若此时实存中没有空闲块应怎么办？操作系统课件-请求分一个作业不全部装入，该作业能否开始运行，并运行一段时间？作业在运行期间的各个阶段，多数作业只使用全部地址作业在运行期间的各个阶段，多数作业只使用全部地址空间的一部分。例如用户编制的出错处理子程序，在作空间的一部分。例如用户编制的出错处理子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们业正常运行情况下不会执行这些程序，没有必要把它们调入内存。调入内存。即程序中往往会有一些即程序中往往会有一些彼此互斥彼此互斥的部分不是的部分不是每次运行时都能执行到。每次运行时都能执行到。 程序

8、的局部性。程序的局部性。顺序执行的指令和线性结构的数据(如数组)。它们通常被限定在某一连续区域。一旦某一位置被访问后，那么它附近的位置很快也会被访问。 因此，没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。操作系统课件-请求分当程序要访问的某页不在内存时，如何发现当程序要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？这种缺页情况？发现后应如何处理？地址变换机构检测到虚页的状态为1，由硬件产生缺页中断，转去中断处理操作系统课件-请求分 所需的页面从何

9、处装入？ 在请求分页管理系统中，当一个作业完成编译链接后，所形成的装配模块通常以文件形式存入作为辅存的磁盘上，当该页需要装入实存时，就从磁盘上调进来。为此，需建立一个作业的辅助页表，也称为外页表。虚页号辅存地址操作系统课件-请求分 新调入的页面装入何处？新调入的页面装入何处？ 实存中有空闲实页，直接将其装入。实存中有空闲实页，直接将其装入。 空闲已满，则必须淘汰（页面置换算法）实存中的某一页。空闲已满，则必须淘汰（页面置换算法）实存中的某一页。 被淘汰的页，以后可能还要用，是否需要写回辅存，被淘汰的页，以后可能还要用，是否需要写回辅存，这取决于该页进入实存后是否被修改，如未被修改，因辅这取决于

10、该页进入实存后是否被修改，如未被修改，因辅存上已有副本则不必写回辅存。否则，要重新写回辅存。存上已有副本则不必写回辅存。否则，要重新写回辅存。因此页表中还可以增加一个因此页表中还可以增加一个“修改位修改位”，以反映该页是否，以反映该页是否已被修改过。已被修改过。 为了便于系统管理页面置换，增加为了便于系统管理页面置换，增加“引用位引用位”，表示该，表示该页最近是否被访问过。页最近是否被访问过。操作系统课件-请求分虚页号 主存块号 改变位 引用位 状态位 辅存地址 0/11该页已被修改过0该页未被修改0/11最近已被访问过主存块号0/10在内存1不在内存辅助页表 虚页号辅存地址保护信息扩充后的P

11、MT表操作系统课件-请求分图 缺页中断的发生及其处理 执行一条指令形成有效地址计算页号该页在实存吗？缺页中断入口有空闲的实页码？出页修改PMT MBTC=1？复制到辅存取出保存的页号入页找出磁盘地址修改PMT MBT表重新执行被中断的指令取下一条指令取数据完成该指令硬件软件YNNYYN抖动/系统颠簸操作系统课件-请求分q抖动抖动/系统颠簸系统颠簸 出页：将某一页从实存移到辅存出页：将某一页从实存移到辅存 入页：将某一页从辅存调入实存入页：将某一页从辅存调入实存 这种反复进行入页和出页的现象称为这种反复进行入页和出页的现象称为“抖动抖动/系统颠簸系统颠簸”操作系统课件-请求分 先进先出算法先进先

12、出算法(FIFO)淘汰驻留主存时间最长的页面淘汰驻留主存时间最长的页面最近最久未用置换算法最近最久未用置换算法(LRU)淘汰在最近一段时间最久未用的页面淘汰在最近一段时间最久未用的页面最近最不常用算法最近未使用算法页面置换算法/淘汰算法操作系统课件-请求分1. 先进先出算法（FIFO算法） 这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。 操作系统课件-请求分2最近最久未使用页面置换算法（ Least Recently Used/ LRU算法）这种算法的基本思想是，如果某一页被访问了，那么它很可能马上

13、又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。 实现这种算法可通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面。 不太实用操作系统课件-请求分 性能分析性能分析为了尽可能地减少缺页中断的次数，应从程序设计的质量页面的大小主存的容量页面置换算法等几方面来考虑。操作系统课件-请求分程序设计的质量(主要指程序的局部化程度)程序的局部化程度包括时间局部化和空间局部化时间局部化是指一旦某个位置-数据或指令-被访

14、问了，它常常很快又要再次被访问。这可通过循环、经常用到的变量和子程序等程序结构来实现。空间局部化是指一旦某个位置被访问到，那么它附近的位置很快也要用到。这可以尽量采用顺序的指令列、线形的数据结构来实现。局部化程度随程序而异，一般来说，总希望编制的程序具有较高的局部化程度。这样，程序执行时可经常集中在几个页面上进行访问，以减少缺页中断的次数。操作系统课件-请求分 页面的大小 页面大小应根据实际情况实际情况来确定，它和计算机的性能以及用户的要求都有关系。 页面大，页表小，占用空间小，缺页中断次数少，但换页时间长，页内碎片也大，浪费空间 页面小时，正好相反操作系统课件-请求分l 主存的容量 一个作业

15、的执行所产生缺页的次数是存放页面的实际存储容量的函数。当存储容量达到某一程度时，缺页中断的次数的减少就不明显了。 试验分析表明：对所有程序来说，要使之有效地工作，它在主存中的页面数不低于它的总页面数的一半。操作系统课件-请求分图 存储容量与缺页中断次数的关系 016KB32KB48KB64KB80KB96KB112KB100020003000400050006000700080009000MF24 KB932132 KB512648 KB245664 KB129580 KB69696 KB441112 KB329128 KB271160 KB144192 KB62缺页次数 F主存大小M操作系统

16、课件-请求分4页面置换算法性能三个参数：页面走向：每个作业的虚页调入实存的顺序，称为页面轨迹， 或页面走向，用P表示。主存容量：是指分配给作业的主存块数，M表示。置换算法：包括FIFO，LRU等操作系统课件-请求分例例 1 设页面走向为P=4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5，主存容量M=3，置换算法采用FIFO，求访问过程中发生缺页中断的次数和缺页率？假设开始时，主存未装入任何块 。表1 FIFO性能分析例(M=3) 缺页中断次数F=9缺页率f=9/12=75%P行表示页面走向，M行表示在主存中的页面号，其中带有+ +的表示新调入页面，在M行的各列按调入的顺序

17、排列，带有圆圈的数字表示下一时刻将被淘汰页面，F行表示是否引起缺页中断，带+号的表示引起缺页中断。操作系统课件-请求分 例例 2 设M=4，其余同例 1。则缺页中断次数和缺页率？ 表2 FIFO性能分析例(M=4) 缺页中断次数F=10缺页率f=10/12=83%操作系统课件-请求分由表1，表2得出：对于FIFO算法，内存增加，缺页率反而增加！异常现象异常现象（Belady异常）异常）操作系统课件-请求分 例例 3 设页面走向如上，M=3，置换算法为LRU，则缺页中断次数和 缺页率？ 由于采用LRU算法，M中各列按访问的时间顺序排列，最近被访问的页面在最前。表3LRU性能分析例(M=3) 缺页

18、中断次数F=10， 缺页率f=10/12=83%。 操作系统课件-请求分例例 4 设M=4，其余同例 3，则缺页中断次数和 缺页率？表4LRU性能分析例(M=4) 操作系统课件-请求分34操作系统课件-请求分 由表 3， 表 4 可得如下事实： 设G(P, M, t)表示当页面走向为P，主存容量为M，在时刻t的页面集合，对于LRU算法，存在如下关系，即 ), 1,(),(tMPGtMPG成立。即对于任何时刻t(t=1, 2, , 12),G(P, M, t)所选中的页号必定包含在G(P, M+1, t)之中。这种关系说明了增加主存容量不会增加缺页中断次数，然而对FIFO算法， 此关系并不成立。 操作系统课件