《4.5虚拟存储管理》由会员分享，可在线阅读，更多相关《4.5虚拟存储管理（83页珍藏版）》请在金锄头文库上搜索。
1、4.5 4.5 虚拟存储虚拟存储4.5.1 虚拟存储管理的概念4.5.2 请求分页虚拟存储管理4.5.3 请求分段虚拟存储管理4.5.4 请求段页式虚拟存储管理14.5.1 虚拟存储管理的概念(1)为什么要引入虚拟存储器?“部分装入、部分对换” 虚拟存储器的定义： 在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器”。 2虚拟存储管理的概念(2) 虚拟存储器的概念图 虚拟地址空间处理器虚地址 存储管理部件实地址主存辅存物理地址空间3虚拟存储管理的概念(3) 程序的局部性原理： 指程序在执行过程中的一个较短时间内，
2、所执行的指令地址或操作数地址分别局限于一定的存储区域中。又可细分时间局部性和空间局部性。4虚拟存储管理的概念(4) 第一第一，程序中只有少量分支和过程调用，大都是顺序执行的指令。 第二，第二，程序包含若干循环，是由相对较少的指令组成，在循环过程中，计算被限制在程序中很小的相邻部分中。第三第三，很少出现连续的过程调用，相反，程序中过程调用的深度限制在小范围内，一段时间内，指令引用被局限在很少几个过程中。 第四第四，对于连续访问数组之类的数据结构，往往是对存储区域中相邻位置的数据的操作。 第五第五，程序中有些部分是彼此互斥的，不是每次运行时都用到的，如出错处理程序。5虚拟存储管理的概念(5)实现虚
3、拟存储器必须解决好以下有关问题：主存辅存统一管理问题逻辑地址到物理地址的转换问题部分装入和部分对换问题虚拟存储管理主要采用以下技术实现： 请求分页虚拟存储管理 请求分段虚拟存储管理请求段页式虚拟存储管理64.5.2分页式虚拟存储系统1分页式虚拟存储系统的硬件支撑CPUMMU内存CPU把逻辑地址送至MMUMMU把物理地址送至内存 MMU的位置、功能和16个4KB页面情况下MMU的内部操作CPU送入的逻辑地址(8196) 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0MMU送出的物理地址(24580) 0 010
4、1 1 001 1 2 110 1 3 000 1 4 100 1 5 011 1 6 000 0 7 000 0 8 101 1 9 000 0页号 页框号 在主存否7MMU主要功能(1)管理硬件页表基址寄存器。(2)分解逻辑地址。(3)管理快表TLB。(4)访问页表。(5)发出缺页中断或越界中断，并将控制权交给内核存储管理处理。(6)设置和检查页表中各个特征位。82请求分页虚拟存储系统的基本原理(1)分页式虚拟存储系统是将作业信息的副本存放在磁盘中，当作业被调度投入运行时，不把作业的程序和数据全部装入主存，而仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再把它们动
5、态地装入 。 9请求分页虚拟存储系统的基本原理(2)怎样才能发现页面不在内存中呢?怎样处理这种情况呢?采用的办法是：扩充页表的内容，增加驻留标志位和页面辅存的地址等信息。10 页式虚拟存储管理页表扩展页号 驻留标志 页框号 辅存地址 其它标志11请求分页虚存地址转换过程(1) 逻辑空间地址主存(用户区)CPU逻辑地址快表主存(系统区)运行进程页表辅存缺页中断处理分解地址访问MMU查快表命中不命中页表命中发缺页中断调页装入、改表查页表运行进程页表基址装入快表运行进程映象进程切换时装入物理地址页框 页内地址页号 页内地址12请求分页虚存地址转换过程(2)查快表有登记无登记查页表登记入快表发缺页中断
6、在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统硬件逻辑地址无13请求页式虚拟存储系统优缺点 优点：作业的程序和数据可按页分散存放在内存中，减少移动开销，有效解决了碎片问题;既有利于改进主存利用率，又有利于多道程序运行。 缺点：要有硬件支持，要进行缺页中断处理，机器成本增加，系统开销加大。143 页面装入策略和清除策略(1) 页面装入主存，有两种策略：请页式调度:需要访问程序和数据时，才把所在页面装入主存。缺点是处理缺页中断和调页的系统开销较大。预调式调度:系统
7、预测进程将要使用的页面，使用前预先调入主存，每次调入若干页面，而不是仅调一页。缺点是如果调入的一批页面中多数未被使用，则效率就很低了，可见预调页要建立在预测的基础上。15页面装入策略和清除策略(2)清除策略请页式清除是仅当一页选中被替换，且之前它又被修改过，才把这个页面写回辅存。请页式清除，写出一页是在读进新页前进行的，要成双操作，引起进程等待两次I/O操作，会降低CPU使用效率。预清除，写出页仍在内存中，直到页替换算法选中一页从内存中移出，成批地把页面写出，但如若刚写出了很多页面，在被替换前，其中大部分又被更改，预清除就毫无意义。 16页面装入策略和清除策略页面装入策略和清除策略(4)(4)
8、页缓冲策略策略如下:仅清除淘汰的页面，并使清除操作和替换操作不必成双进行。在页缓冲中，淘汰了的页面进入两个队列：修改页面和非修改页面队列。修改页面队列中的页的不时地成批写出并加入到非修改页面队列; 非修改页面队列中的页面，当它被再次引用时回收，或者淘汰掉以作替换。174 4页面分配策略页面分配策略：考虑因素考虑因素系统为进程分配主存，需考虑因素: 分给进程的空间越小，同一时间处于内存的进程就越多，至少有一个进程处于就绪态的可能性就越大如果进程只有小部分在主存里，即使局部性很好，缺页中断率还会相当因程序的局部性原理，分给进程的内存超过一定限度后，再增加内存空间，不会明显降低进程的缺页中断率。18
9、页面分配策略页面分配策略进程保持页框数固定不变，称固定分配;进程分得的页框数可变，称可变分配。固定分配：进程创建时，根据进程类型和程序员的要求决定页框数，只要有一个缺页中断产生，进程就会有一页被替换。可变分配：进程执行的某阶段缺页率较高，说明目前局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前局部性较好，可减少分给进程的页框数。19页面分配策略页面分配策略：分析分析固定分配缺少灵活性，而可变分配的性能会更好些，被许多操作系统采用。采用可变分配策略的困难在于操作系统要经常监视活动进程的行为和进程缺页中断率的情况，会增加系统的开销。20页面替换策略：局部替换和全局部替换和全局替换局替换如
10、果页面替换算法的作用范围是整个系统，称全局页面替换算法，它可以在运行进程间动态地分配页框。如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法，它实际上需要为每个进程分配固定的页框。 21固定分配和局部替换策略配合使用进程分得的页框数不变，发生缺页中断，只能从进程的页面中选页替换，保证进程的页框总数不变。策略难点：应给每个进程分配多少页框?给少了，缺页中断率高;给多了，使内存中能同时执行的进程数减少，进而造成处理器和其它设备空闲。采用固定分配算法，系统把页框分配给进程，采用：1)平均分配2)按比例分配3)优先权分配22可变分配和全局替换策略配合使用 先每个进程分配一定数目页框，os保留
11、若干空闲页框，进程发生缺页中断时，从系统空闲页框中选一个给进程，这样产生缺页中断进程的内存空间会逐渐增大，有助于减少系统的缺页中断次数。 系统拥有的空闲页框耗尽时 ，会从内存中选择一页淘汰，该页可以是内存中任一进程的页面，这样又会使那个进程的页框数减少，缺页中断率上升。23可变分配和局部替换配合使用 其实现要点如下:(1)新进程装入主存时，根据应用类型、程序要求，分配给一定数目页框，可用请页式或预调式完成这个分配。(2)产生缺页中断时，从该进程驻留集中选一个页面替换。(3)不时重新评价进程的分配，增加或减少分配给进程的页框以改善系统性能。245 页面替换策略 页面替换页面替换 页面淘汰算法 “
12、抖动”(Thrashing)现象 25影响缺页中断率的因素(1)(1) 假定作业p共计n页，系统分配给它的主存块只有m块（mn）。如果作业p在运行中成功的访问次数为s， 不成功的访问次数为F，则总的访问次数为：A = S + F 又定义：f = F / A26影响缺页中断率的因素(2)(2) 称f为缺页中断率。影响缺页中断率f的因素有： (1)主存页框数。 (2)页面大小。 (3)页面替换算法。 (4)程序特性。27影响缺页中断率的因素(3)(3) 程序要将128128的数组置“0”。分给的主存只一块，页面尺寸为每页128个字，数组中的元素每行存放在一页中。若程序如下：Var Var A: A
13、: array1.128 array1.128 of of array array 1.128 of integer;1.128 of integer; for j := 1 to 128 for j := 1 to 128 do for i := 1 to 128 do for i := 1 to 128 do Aij:=0 do Aij:=028影响缺页中断率的因素(4)(4) 如果重新编制程序如下：Var A: array1.128 of array1.128 of integer; for j := 1 to128 do for i := 1 to 128 do Aij := 0 总共
14、产生（1281）次缺页中断。29一个理论算法(最佳替换算法)调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。Belady算法（Optimal） ，可用来作为衡量各种具体算法的标准。301）随机页面替换算法要淘汰的页面是由一个随机数产生程序所产生的随机数来确定，选择一个不常使用的页面会使系统性能较好，但这种调度算法做不到这一点，虽很简单但效率却低。312)先进先出页面替换算法（FIFO)基于程序总是按线性顺序来访问物理空间这一假设。算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。 32FIFO实现技术系统中设置一张具
15、有m个元素的页号表，它是个数：P0， P1， ， Pm-1 组成的数组，每个Pi (i =0，1，m-1) 存储一个在主存中的页面的页号。用指针k指示当前调入新页时应淘汰的那一页在页号表中的位置。每当调入一个新页后，执行Pk := 新页的页号;k := （k+1）mod m;33FIFO另一个实现算法引入指针链成队列，只要把进入主存的页面按时间的先后次序链接，新进入的页面从队尾入队，淘汰总是从队列头进行。343）最近最少用页面替换算法LRU算法淘汰的页面是在最近一段时间里较久未被访问的那页。根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上
16、使用到。35LRU算法实现：页面淘汰队列(1)队列中存放当前在主存中的页号，每当访问一页时就调整一次，使队列尾总指向最近访问的页，队列头就是最近最少用的页。发生缺页中断时总淘汰队列头所指示的页；执行一次页面访问后，需要从队列中把该页调整到队列尾。36LRU算法实现：页面淘汰队列(2)访问页号 页面淘汰序列 被淘汰页面 4 4 3 4 3 0 4 3 0 4 3 0 4 1 0 4 1 3 1 0 4 1 2 4 1 2 0 3 1 2 3 4 2 1 3 237LRU算法实现：标志位法每页设置一个引用标志位R，访问某页时，由硬件将页标志位R置1，隔一定时间t将所有页的标志R均清0。发生缺页中断
17、时，从标志位R为0的页中挑选一页淘汰。挑选到要淘汰的页后，也将所有页的标志位R清0。 38LRU算法实现：多位寄存器法例如，r寄存器共有四位，页面P0、P1、P2在T1、T2、T3时刻的r寄存器内容如下： 页面 时刻 T1 T2 T3 P0 1000 0100 1010 P1 1000 1100 0110 P2 0000 1000 010039LRU算法实现：多位计数器法每个页面设置一个多位计数器，又叫最不常用页面替换算法LFU。每当访问一页时，就使它对应的计数器加。当发生缺页中断时，可选择计数值最小的对应页面淘汰，并将所有计数器全部清。 40LRU算法实现：多位计时器法为每个页面设置一个多位
18、计时器，每当页面被访问时，系统的绝对时间记入计时器。比较各页面的计时器的值，选最小值的未使用的页面淘汰，因为，它是最“老”的未使用的页面。414)第二次机会页面替换算法(1) 改进FIFO算法，把FIFO与页表中的”引用位”结合起来使用： 检查FIFO中的队首页面(最早进入主存的页面)，如果它的”引用位”是0，这个页面既老又没有用，选择该页面淘汰; 42第二次机会页面替换算法(2) 如果”引用位”是1，说明它进入主存较早，但最近仍在使用。把它的”引用位”清0，并把这个页面移到队尾，把它看作是一个新调入的页。 算法含义：最先进入主存的页面，如果最近还在被使用的话，仍然有机会作为像一个新调入页面一
19、样留在主存中。435）时钟页面替换算法(ClockPolicy)(1) 算法实现要点(1)： 一个页面首次装入主存，其“引用位”置1 。主存中的任何页面被访问时， ”引用位”置1。淘汰页面时，从指针当前指向的页面开始扫描循环队列，把遇到的”引用位”是1的页面的”引用位”清0，跳过这个页面; 把所遇到的”引用位”是0的页面淘汰掉，指针推进一步。44时钟页面替换算法(Clock Policy)(2) 算法实现要点(2)：扫描循环队列时，如果遇到的所有页面的”引用位”为1，指针就会绕整个循环队列一圈，把碰到的所有页面的”引用位”清0;指针停在起始位置，并淘汰掉这一页，然后，指针推进一步。45时钟页面
20、替换算法的一个例子 Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一个帧指针n012345678一个页替换前的缓冲区状态Page9 use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=1Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0n012345678下一页替换后的缓冲区状态第1页框46时钟页面替换改进算法
21、(1)把”引用位”和”修改位”结合起来使用，共组合成四种情况：(1)最近没有被引用，没有被修改(r=0，m=0)(2)最近被引用，没有被修改(r=1，m=0)(3)最近没有被引用，但被修改(r=0，m=1)(4)最近被引用过，也被修改过(r=1，m=1)47时钟页面替换改进算法(2) 步1：选择最佳淘汰页面，从指针当前位置开始，扫描循环队列。扫描过程中不改变”引用位”，把迂到的第一个r=0，m=0的页面作为淘汰页面。步2：如果步1失败，再次从原位置开始，查找r=0且m=1的页面，把把迂到的第一个这样的页面作为淘汰页面，而在扫描过程中把指针所扫过的页面的”引用位”r置0。48时钟页面替换改进算法
22、(3) 步3：如果步2失败，指针再次回到了起始位置，由于此时所有页面的”引用位”r均己为0，再转向步1操作，必要时再做步2操作，这次一定可以挑出一个可淘汰的页面。49UNIX SVR4双指针clock算法引用位前指针和后指针两个指针扫描页表的速度两个指针之间时间间隔的选择 50一个例子，计算缺页中断次数和被淘汰页面(1)假设采用固定分配策略，进程分得三个页框，执行中按下列次序引用5个独立的页面: 2 3 2 1 5 2 4 5 3 2 5 2。 51一个例子，计算缺页中断次数和被淘汰页面(2) 性能比较 OPT F(1) F(2) F(4)LRU F(3) F(1) F(2) F(4)CLOC
23、K F(2) F(3) F(1) F(5) F(4) FIFO F(1) F(3) F(1) F(5) F(2) F(4)52计算缺页中断实例(1) 假设固定分配，运行FORTRAN程序，共有0.25106次页面引用，页面大小为256个字。分给进程的页框数分别为6、8、10、12和14。FIFO所产生的缺页中断基本上是Opt的2倍，Clock则比较接近于LRU。53计算缺页中断实例(2) 051015202535403006686101214 FIFO CLOCK LRU OPT分配的页数每千次访问的缺页中断数546 6请求分页虚拟存储管理的几个请求分页虚拟存储管理的几个设计问题设计问题(1)
24、(1)页面大小页面大小 .从页表大小考虑 .从主存利用率考虑 .从读写一个页面所需时间考虑 55最佳页面尺寸(1) 假定S表示用户作业程序的字节数平均长度，P表示以字节为单位的页面长度，且有SP，页表项需要e个字节。作业的页表长度为S/P，占用了Se/P个字节的页表空间，作业的最后一页，浪费的主存平均为P/2字节。对一个作业而言： 浪费的存储字=页表使用的主存空间+内部碎片=Se/P+P/256最佳页面尺寸(2) 页面较小时页表占用空间多(因Se/P较大)，页面较大时内部碎片浪费多(因P/2较大)。现对P求一阶导数并令其为0，得到 -Se/P2+1/2=0 那么，可以得出最优页面尺寸 P=开根
25、号2Se 时，浪费的存储字节最少，称P为最佳 页面尺寸。对于S=128KB，每个页表项e=8B时，最优页面尺寸是1448字节 57著名操作系统选择的页面尺寸Atlas为 512字(每字48位)、IBM370系列机为2048或4096字节、VAX为 512字节、IBM as/400为512字节、Intel 486和Motorola68040为4096字节。58(2)工作集模型(1)P.J.Denning认为，应该将处理机调度和主存管理结合起来进行考虑，并在1968年提出了工作集模型。工作集-“在未来的时间间隔内，一个进程运行时所需访问的页面集”。59工作集模型(2)时间过渡工作集过渡工作集第2个
26、工作集第1个工作集过渡工作集第3个工作集第4个工作集工作集页面数工作集的演变过程(1)60工作集和工作集窗口(1) 用W(t， )表示从时刻t-到时刻t之间所访问的不同页面的集合，t是进程实际耗用的时间，可以通过执行的指令周期来计算; 是时间窗口尺寸，通过窗口来观察进程的行为。W(t， )就是作业在时刻t的工作集，表示在最近个实际时间单位内进程所引用过的页面的集合;61工作集和工作集窗口(2) W(t， )表示工作集中的页面数目，称工作集尺寸。如果系统能随W(t， )的大小来分配主存块，就既能有效利用主存，又可使缺页中断尽量少地发生，或者说程序要有效运行，其工作集必须在主存中。 62工作集和工
27、作集窗口(3) 工作集W是t的函数，随时间不同，工作集也不同。其一是不同时间的工作集包含的页面数可能不同；其二是不同时间的工作集包含的页面可能不同。工作集W又是工作集窗口尺寸的函数，而且工作集尺寸W（t，）是工作集窗口尺寸的非递减函数。63工作集和工作集窗口(4)241518232417182418171715241724182415 2418 1523 1824 2317 2418 1724 1818 2417 181715 1724 1517 2424 1718 242415 2418 15 2423 18 1524 23 1817 24 2318 17 24 * * * *15 17 1
28、824 15 17 * *18 24 172415 2418 15 2423 18 15 24 *17 24 23 18 * * * * *15 17 18 24 * * * *2415 2418 15 2423 18 15 24 *17 24 23 18 15 * * * * * * * * * *5234窗口大小页面访问序列64正确选择工作集窗口尺寸如果过大，甚至把作业地址空间全包括在内，就成了实存管理; 如果过小，则会引起频繁缺页，降低了系统的效率。 65通过工作集概念来指导确定驻留集的大小(1)监视每个进程的工作集。(2)定期地从一个进程驻留集中删去那些不在工作集中的页。(3)仅当一个
29、进程的工作集在主存即驻留集包含了它的工作集时，进程才能执行。66页面故障率是分配页框数的函数67页面故障率（Page Fault Frequency）包括LRU在内的一大类页面替换算法的故障率随着分配的页框数的增加而减少PFF试图把页面故障率保持在一个可接受的范围内。68(3)页面交换区替换算法要挑选页面淘汰出主存，但被淘汰出去的页面可能很快使用，又要被重新装入主存。操作系统必须保存被淘汰的页面，例如UNIX使用交换区临时保存页面，系统初始化时，保留一定盘空间作交换区。69(4)锁定主存页如果采用全局替换策略，锁住正在做I/O操作的内存页面，保证它不被移出，可以在页表项中增加锁定位来做到这一点
30、。另一种解决方法是在核心内的缓冲区完成I/O，然后，把数据复制到用户的页面。70(5) 写时复制(1)写时复制(copy-on-write)是存储管理节省物理内存(页框)的一种页面级优化技术，已被UNIX和Windows等采用，能减少主存页面内容的复制操作，减少相同内容页面在主存的副本数目。71(5) (5) 写时复制写时复制(2)(2)原始数据原始数据原始数据进程地址空间物理地址空间原始数据原始数据原始数据进程地址空间物理地址空间原始数据原始数据原始数据进程地址空间原始数据原始数据原始数据进程地址空间页面2副本 页面1页面2页面3页面1页面2页面3724.5.3请求分段虚拟存储系统分段式虚拟
31、存储系统把作业的所有分段的副本都存放在辅助存储器中，当作业被调度投入运行时，首先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把它们装入。 73段式虚拟存储管理的段表扩展(1) 段号扩充位主存始址特征存取权限辅存始址标志限长74段式虚拟存储管理的段表扩展(2) 特征位: 00(不在内存)；01(在内存)；11(共享段)；存取权限: 00(可执行)；01(可读)；11(可写)；扩充位: 0(固定长)；1(可扩充)；标志位: 00(未修改)；01(已修改)；11(不可移动)；75请求分段虚存管理的地址转换S段在内存否是BS段长度发越界中断是否形成绝对地址继续执行指令移动或调出分
32、段S段末端相邻空闲区长度满足要求地址错S段可扩充是装入S段重新启动指令调整S段段表及主存分配表操作系统硬件否符合存取权限发保护中断是否发缺段中断非法存取否主存中有满足S段长度的连续空闲区是否是移动或调出分段764.5.4请求段页式虚拟存储管理段式存储是基于用户程序结构的存储管理技术，有利于模块化程序设计，便于段的扩充、动态链接、共享和保护，但会生成段内碎片浪费存储空间页式存储是基于系统存储器结构的存储管理技术， 存储利用率高，便于系统管理，但不易实现存储共享、保护和动态扩充把两者结合起来就是段页式存储管理 771、虚地址以程序的逻辑结构划分成段(段页式存储管理的段式特征)2、实地址划分成位置固
33、定、大小相等的页框(段页式存储管理的页式特征)3、将每一段的线性地址空间划分成与页框大小相等的页面，于是形成了段页式存储管理的特征。4、逻辑地址形式为：请求段页式存储管理的基本原理段号(s) 段内页号 (p) 页内位移(d)78请求段页式存储管理的数据结构 段页式存储管理的数据结构包括：作业表：登记进入系统中的所有作业及该作业段表的起始地址，段表：至少包含这个段是否在内存，以及该段页表的起始地址，页表：包含该页是否在主存(中断位)、对应主存块号。79请求段页式存储管理的动态地址转换(1) 从逻辑地址出发，先以段号s和页号p作索引去查快表，如果找到，那么立即获得页p的页框号p，并与位移d一起拼装
34、得到访问主存的实地址，从而完成了地址转换。80请求段页式存储管理的动态地址转换(2)若查快表失败，就要通过段表和页表作地址转换了，用段号s作索引，找到相应表目，由此得到s段的页表起址s，再以p作索引得到s段p页对应的表目，得到页框号p;这时一方面把s段p页和页框号p置换进快表，另一方面用p和d生成主存实地址，从而完成地址转换。81请求段页式存储管理的动态地址转换(3)如查段表时，发现s段不在主存，产生“缺段中断”，引起系统查找s段在辅存的位置，将该段页表调入主存；如查页表时，发现s段的p页不在主存，产生“缺页中断”，引起系统查找s段p页在辅存的位置，并将该页调入主存，当主存已无空闲页框时，就会导致淘汰页面。82请求段页式存储管理的动态 地址转换(3) 段表控制寄存器段表始址 段表长度段号s 页号p 位移d段超长?页框号 位移段表页表83
