操作系统 虚拟内存.ppt

1、内容提要,虚存技术的引入和虚拟存储器的定义、特征 虚拟存储器的实现 请求分页 请求分段,内容提要,虚存技术的引入和虚拟存储器的定义、特征 虚拟存储器的实现 请求分页 请求分段,需求,指令必须被装载到内存中运行 上一讲的解决方案 To place the entire logical address in physical memory Overlays（覆盖） Dynamic loading Dynamic linking 然而 有的作业很大；作业个数很多 若从物理上扩展内存，代价太高 思路：从逻辑上扩展内存,虚存技术的引入,程序的局部性原理，1968，Denning 时间局部性、空间局部性

2、思路： 部分装入、按需装入、置换 虚拟存储器： 是指具有请求调度功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统 逻辑容量：从系统角度看：内存容量外存容量从进程角度看：地址总线宽度范围内；内存容量外存容量 运行速度：接近内存 每位成本：接近外存,Virtual memory diagram,Some pages in memory, Some pages in disk,虚拟存储器的特征,多次性：最重要的特征 一个作业被分成多次装入内存运行 对换性 允许在进程运行的过程中，（部分）换入换出 虚拟性 逻辑上的扩充 虚拟性是以多次性和对换性为基础的。 多次性和对换性是建立在离散分配的基

3、础上的,内容提要,虚存技术的引入和虚拟存储器的定义、特征 虚拟存储器的实现 请求分页 请求分段,虚拟存储器的实现,请求分页 以分页技术为基础，加上 请求调页（pager）功能和页面置换功能 与对换相比，页面置换中换入换出的基本单位是页，而不是整个进程 请求分段 以分段技术为基础,请求分页,请求分页的硬件支持 请求分页的内存分配策略和分配算法 调页策略 页面置换算法 请求分页的性能分析和改进,请求分页,请求分页的硬件支持 请求分页的内存分配策略和分配算法 调页策略 页面置换算法 请求分页的性能分析和改进,请求分页的硬件支持,页表机制 缺页中断机构 地址变换机构 对比“基本分页存储管理技术”,请求

4、分页中的页表机制,页表是请求分页系统中所需要的主要数据结构，是前面所讲页表的扩展，增加了： 存在位P：表示对应的页是否已经装入内存 访问字段A：记录访问情况，供换出时参考 修改位M：记录修改情况，供换出时参考 外存地址：记录在外存上的地址，供换入时参考,请求分页中的缺页中断机构,当一个进程试图访问标记为 “not present”的页面时，会发生缺页异常. Page fault trap（缺页异常） Exact exception (trap)Restart the process in exactly the same place and state. Re-execute the inst

5、ruction which triggered the trap. 一条指令在执行期间可能产生多次缺页异常,One instruction use 100 ns) Effective Access Time (EAT) EAT = (1 p)ma + ppage fault time,Page fault time,Page fault overhead Service the page-fault interrupt (1100us) (May be) swap some pages out Read in the page (24ms,寻道，旋转，传输) Restart overhead

6、(1100us) Restart the process Page fault time may be 25ms,性能举例,Page fault time = 25ms ma = 100ns Then EAT = 100(1-p)+25106p = 100 + 24,999,900p If p=1/1000, then EAT =25,099.9 ns If needs EAT 110ns, then 100+24,999,900p110that is p 10/24,999,90010/25,000,000 =1/2,500,000 =410-7 Page fault rage p must

7、 be smaller than 410-7,请求分页,请求分页的硬件支持 请求分页的内存分配策略和分配算法 调页策略 页面置换算法 请求分页的性能分析和改进,内存分配策略,为进程分配内存时，涉及3个主要问题 最小物理块数的确定 物理块的分配策略 物理块的分配算法,最小物理块数的确定,Determined by ISA(Instruction-Set Architecture ) We must have enough frames to hold all the different pages that any single instruction can reference Example

8、: IBM 370 6 pages to handle MVC instruction: instruction is 6 bytes, might span 2 pages. 2 pages to handle from; 2 pages to handle to. How about maximum number?,物理块的分配策略,分配策略： Fixed allocation The No. of frames allocated to a process is fixed Variable allocation The No. of frames allocated to a proc

9、ess is variable as the process running 置换策略： 全局 vs. 局部 两者结合： 固定分配局部置换 可变分配全局置换 可变分配局部置换,物理块的分配算法,1、平均分配算法： The simplest way to split m frames among n processes is to give each one an equal share: m/n frames each 2、按比例分配算法（举例）： Allocate frames to each process according to the size of each process. 3、

10、考虑优先级的分配算法 在按比例分配算法中，考虑将size（部分）换成优先级,Example:,请求分页,请求分页的硬件支持 请求分页的内存分配策略和分配算法 调页策略 页面置换算法 请求分页的性能分析和改进,请求分页,请求分页的硬件支持 请求分页的内存分配策略和分配算法 调页策略 页面置换算法 请求分页的性能分析和改进,页面置换算法,Free page frame is managed by OS using free-frame-list What happens if there is no free frame? Page replacement,Page-Replacement Alg

11、orithms,目标：尽可能降低缺页率 Different algorithms are evaluated by calculating the number of page faults they cause on a reference string. A reference string is a sequence of addresses referenced by a program.,Example,An address reference string: 0100 0432 0101 0612 0102 0103 0104 01010611 0103 0104 0101 061

12、0 0102 0103 01040101 0609 0102 0105 Assuming page size = 100 B, then its corresponding page reference string is: 1 4 1 6 1 6 1 6 1 6 1,11 pages,Example (contd),缺页多少次? 取决于可用物理页框的个数 若物理页框数3，则 1 4 1 6 1 6 1 6 1 6 1 1, 4, 6 3 次缺页 若只有1个物理页框，那么每次访问一个新的页都会导致发生缺页: 11 次缺页,Page faults vs. the number of frames

13、,随着物理页框个数的增加，缺页次数下降,Number of frames,Number of page faults,页面置换算法,假定， 访问序列为： 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 有3个物理页框 介绍如下算法 FIFO page replacement Optimal page replacement LRU page replacement LRU approximation page replacement counting-based page replacement page buffering algorithm,First-In

14、-First-Out (FIFO) Algorithm,置换时，选择“the oldest one” 最简单，但性能不是很好,缺页15次，置换12次,Beladys Anomaly,“增加物理页框，能降低缺页次数”不是真理！ 考虑访问序列: 1 2 3 4 1 2 5 1 2 3 4 5 物理页框数为4时 1 1 1 1 1 1 5 5 5 5 4 4 2 2 2 2 2 2 1 1 1 1 5 3 3 3 3 3 3 2 2 2 2 4 4 4 4 4 4 3 3 3 物理页框数为3时 1 1 1 4 4 4 5 5 5 5 5 5 2 2 2 1 1 1 1 1 3 3 4 3 3 3 2

15、 2 2 2 2 4 4,Page fault: 10 Page replacement: 6,Page fault: 9 Page replacement: 6,Graph,Number of frames,Number of page faults,Optimal Algorithm 最优算法,置换在未来最长时间内不会被使用的页面（如果是未来永远不会使用的，最好） 保证最少缺页率 缺点：必须预先知道进程在未来的行为 very difficult to implement 因此，常用于进行置换算法比较时,缺页9次，置换6次,LRU algorithm,LRU = Least Recently

16、 Used 最近最久未使用 Replace the page that has not been used for the longest period of time.,缺页12次，置换9次,LRU implementation,Hard to implement efficiently: Use an extra counter (time-of-use) field in a page replace the oldest page Store a stack of page numbers replace the bottom page,使用计数器的LRU,为每个页配备一个计数器cou

17、nter; CPU必须具备一个逻辑时钟或者计数器 当某个页被访问时, 将当前时钟值填写到counter中 存在更新的系统开销 当需要置换时，必须搜索所有的counter来确定置换哪个页面 存在搜索的系统开销,使用栈的LRU,利用一个特殊的栈来保存当前使用的各个页面的页面号 栈的大小就是物理页框的个数 每当页面被访问时 若页面号不在栈中，将页面号压入栈顶 处于最下方的页面号，被压出栈 若页面号已经在栈中，则将其从栈中移出，然后压入栈顶 不必搜索,LRU with stack (graph),Also need hardware assistance,LRU the problems,Few ma

18、chines have sufficient hardware to support LRU so approximate it with the available hardware Many systems have a reference bit in each page With each page associate a bit, initially = 0 When page is referenced bit set to 1.(read/write) It is easy to replace the one which is 0 (if one exists). But we

19、 do not know the order,思考,考虑4个页框和8个页面的情况，页框初始为空，访问序列为0172327103时，会产生多少次缺页？LRU呢？,LRU近似算法,Three variants Additional-reference-bits algorithm Second-chance algorithm Enhanced Second-chance algorithm,Second chance algorithm,每个页设置一个访问位（reference bit） Inspect the pages in a FIFO manner Start from current

20、oldest (FIFO) page; If the page has reference bit = 0, replace it, exit; Set its reference bit to 0; give the page a second chance Loop back to step 1. 这个算法可以用在页表上，将页表看成一个循环队列，此时算法被称为Clock算法,Second chance algorithm (contd),0,1,1,0,1,1,ref. bits,pages,Next victim,later,0,0,0,0,1,1,pages,Next victim,r

21、ef. bits,The clock page replacement algorithm.,The Clock Page Replacement Algorithm,Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639,改进型Second-Chance Algorithm,+ modify bit Four page classes （访问位，修改位） (0, 0) best page to replace (0, 1) not quite as good (1, 0) probably be used again soon (1, 1) probably be used again soon, and be dirty Replace the first