分页虚拟内存有什么用

第八讲虚拟存储器中国科学技术大学计算机系陈香兰xlanchen@ustc.
edu.
cnFall2013内容提要虚存技术的引入和虚拟存储器的定义、特征虚拟存储器的实现请求分页请求分段内容提要虚存技术的引入和虚拟存储器的定义、特征虚拟存储器的实现请求分页请求分段需求指令必须被装载到内存中运行上一讲的解决方案ToplacetheentirelogicaladdressinphysicalmemoryOverlays(覆盖)DynamicloadingDynamiclinking然而有的作业很大;作业个数很多若从物理上扩展内存,代价太高思路:从逻辑上扩展内存虚存技术的引入程序的局部性原理,1968,Denning时间局部性、空间局部性思路:部分装入、按需装入、置换虚拟存储器:是指具有请求调度功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统逻辑容量:从系统角度看:内存容量+外存容量从进程角度看:地址总线宽度范围内;内存容量+外存容量运行速度:接近内存每位成本:接近外存VirtualmemorydiagramSomepagesinmemory,Somepagesindisk虚拟存储器的特征多次性:最重要的特征一个作业被分成多次装入内存运行对换性允许在进程运行的过程中,(部分)换入换出虚拟性逻辑上的扩充虚拟性是以多次性和对换性为基础的.
多次性和对换性是建立在离散分配的基础上的内容提要虚存技术的引入和虚拟存储器的定义、特征虚拟存储器的实现请求分页请求分段虚拟存储器的实现请求分页以分页技术为基础,加上请求调页(pager)功能和页面置换功能与对换相比,页面置换中换入换出的基本单位是页,而不是整个进程请求分段以分段技术为基础请求分页请求分页的硬件支持请求分页的内存分配策略和分配算法调页策略页面置换算法请求分页的性能分析和改进请求分页请求分页的硬件支持请求分页的内存分配策略和分配算法调页策略页面置换算法请求分页的性能分析和改进请求分页的硬件支持页表机制缺页中断机构地址变换机构对比"基本分页存储管理技术"请求分页中的页表机制页表是请求分页系统中所需要的主要数据结构,是前面所讲页表的扩展,增加了:存在位P:表示对应的页是否已经装入内存访问字段A:记录访问情况,供换出时参考修改位M:记录修改情况,供换出时参考外存地址:记录在外存上的地址,供换入时参考请求分页中的缺页中断机构当一个进程试图访问标记为"notpresent"的页面时,会发生缺页异常.
Pagefaulttrap(缺页异常)Exactexception(trap)Restarttheprocessinexactlythesameplaceandstate.
Re-executetheinstructionwhichtriggeredthetrap.
一条指令在执行期间可能产生多次缺页异常Oneinstruction&pagefault缺页异常可能在任何一次访存操作中产生一条指令可能产生多次缺页.
取值时存取操作数时图中将产生6次缺页中断请求分页中的地址转换机构在前面所讲的分页地址转换结构中,增加了缺页中断的处理缺页时,立即"陷入"操作系统,开始处理异常Pagefaulttrap陷入Checkthatreferenceisvalid检查访存的有效性Findafreememoryframe分配空闲物理页框Readdesiredpagefromdisk装入Changevalidbitofpagetov设置页面的有效位Restartinstructionthatwasinterruptedbythetrap返回并重新执行被中断的指令(引起缺页的指令)Page-faulthandlingphysicalmemoryLoadMOSfreeframepagetable④bringinmissingpage③pageisonbackingstore②trap⑥restartinst.
①reference⑤resetpagetableiv恢复进程的执行BeforeOShandlingthepagefault,thestateoftheprocessmustbesaved(保存现场)e.
g.
recorditsregistervalues,PCThesavedstateallowstheprocesstoberesumedfromthelinewhereitwasinterrupted.
(恢复现场)注意:要区分引起缺页的两种情况非法访问:导致进程终止缺页访问:装入或者换入按需调页的性能令p=PageFaultRate(0p1.
0)ifp=0,nopagefaultsifp=1,everyreferenceisafault令ma=memoryaccesstime(typically10~200ns;use100ns)EffectiveAccessTime(EAT)EAT=(1–p)*ma+p*pagefaulttimeRecall:page-faulthandlingTraptoOSSavecontextPagefaultReferenceislegalThen,whereonthediskRequesttoreadWaiting(scheduling&switch)InterruptfromthediskSavecontextFromdiskSetpage-table(scheduling,atlastswitchback)Restorecontext&restarttheinterruptedinstructionDiskI/O……I/OendINTRPagefaulttimePagefaultoverheadServicethepage-faultinterrupt(1~100us)(Maybe)swapsomepagesoutReadinthepage(24ms=8ms+15ms+1ms)Restartoverhead(1~100us)RestarttheprocessPagefaulttimemaybe25ms性能举例Pagefaulttime=25msma=100nsThenEAT=100(1-p)+25*106*p=100+24,999,900pIfp=1/1000,thenEAT=25,099.
9nsIfneedsEAT<110ns,then100+24,999,900p<110thatisp<10/24,999,900<10/25,000,000=1/2,500,000=4*10-7Pagefaultragepmustbesmallerthan4*10-7降低缺页处理时间TokeepthefaulttimelowSwapspace,fasterthenfilesystemOnlydirtypageisswappedout,orDemandpagingonlyfromtheswapspace,orInitiallydemandpagingfromthefilesystem,swapouttoswapspace,andallsubsequentpagingfromswapspaceKeepthefaultrateextremelylowLocalizationofprogramexecutingTime,space请求分页请求分页的硬件支持请求分页的内存分配策略和分配算法调页策略页面置换算法请求分页的性能分析和改进内存分配策略为进程分配内存时,涉及3个主要问题最小物理块数的确定物理块的分配策略物理块的分配算法最小物理块数的确定DeterminedbyISA(Instruction-SetArchitecture)WemusthaveenoughframestoholdallthedifferentpagesthatanysingleinstructioncanreferenceExample:IBM370–6pagestohandleMVCinstruction:instructionis6bytes,mightspan2pages.
2pagestohandlefrom;2pagestohandleto.
Howaboutmaximumnumber物理块的分配策略分配策略:FixedallocationTheNo.
offramesallocatedtoaprocessisfixedVariableallocationTheNo.
offramesallocatedtoaprocessisvariableastheprocessrunning置换策略:全局vs.
局部两者结合:固定分配局部置换可变分配全局置换可变分配局部置换物理块的分配算法1、平均分配算法:Thesimplestwaytosplitmframesamongnprocessesistogiveeachoneanequalshare:m/nframeseach2、按比例分配算法(举例):Allocateframestoeachprocessaccordingtothesizeofeachprocess.
3、考虑优先级的分配算法在按比例分配算法中,考虑将size(部分)换成优先级Example:请求分页请求分页的硬件支持请求分页的内存分配策略和分配算法调页策略页面置换算法请求分页的性能分析和改进调页策略调入页面的时机预调页策略请求调页策略确定从何处调入页面,三种情况对换空间(only)文件(未运行过的、未修改过的)两者相结合:UNIX方式页面调入过程透明缺页中断请求分页请求分页的硬件支持请求分页的内存分配策略和分配算法调页策略页面置换算法请求分页的性能分析和改进页面置换算法FreepageframeismanagedbyOSusingfree-frame-listWhathappensifthereisnofreeframePagereplacementPageReplacement页面置换Preventover-allocationofmemorybymodifyingpage-faultserviceroutinetoincludepagereplacementPageReplacement(cont.
)physicalPage-ReplacementAlgorithms目标:尽可能降低缺页率Differentalgorithmsareevaluatedbycalculatingthenumberofpagefaultstheycauseonareferencestring.
Areferencestringisasequenceofaddressesreferencedbyaprogram.
ExampleAnaddressreferencestring:01000432010106120102010301040101061101030104010106100102010301040101060901020105Assumingpagesize=100B,thenitscorrespondingpagereferencestringis:1416161616111pages01000432010106120102010301040101061101030104010106100102010301040101060901020105Example(cont'd)缺页多少次取决于可用物理页框的个数若物理页框数≥3,则141616161611,4,63次缺页若只有1个物理页框,那么每次访问一个新的页都会导致发生缺页:11次缺页Pagefaultsvs.
thenumberofframes随着物理页框个数的增加,缺页次数下降NumberofframesNumberofpagefaults页面置换算法假定,访问序列为:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1有3个物理页框介绍如下算法FIFOpagereplacementOptimalpagereplacementLRUpagereplacementLRUapproximationpagereplacementcounting-basedpagereplacementpagebufferingalgorithmFirst-In-First-Out(FIFO)Algorithm置换时,选择"theoldestone"最简单,但性能不是很好缺页15次,置换12次Belady'sAnomaly"增加物理页框,能降低缺页次数"不是真理!
!
!
考虑访问序列:123412512345物理页框数为4时111111555544222222111153333332222444444333物理页框数为3时111444555555222111113343332222244Pagefault:10Pagereplacement:6Pagefault:9Pagereplacement:6GraphNumberofframesNumberofpagefaultsOptimalAlgorithm最优算法置换在未来最长时间内不会被使用的页面(如果是未来永远不会使用的,最好)保证最少缺页率缺点:必须预先知道进程在未来的行为verydifficulttoimplement因此,常用于进行置换算法比较时缺页9次,置换6次LRUalgorithmLRU=LeastRecentlyUsed最近最久未使用Replacethepagethathasnotbeenusedforthelongestperiodoftime.
缺页12次,置换9次LRUimplementationHardtoimplementefficiently:Useanextracounter(time-of-use)fieldinapagereplacetheoldestpageStoreastackofpagenumbersreplacethebottompage使用计数器的LRU为每个页配备一个计数器counter;CPU必须具备一个逻辑时钟或者计数器当某个页被访问时,将当前时钟值填写到counter中存在更新的系统开销当需要置换时,必须搜索所有的counter来确定置换哪个页面存在搜索的系统开销使用栈的LRU利用一个特殊的栈来保存当前使用的各个页面的页面号栈的大小就是物理页框的个数每当页面被访问时若页面号不在栈中,将页面号压入栈顶处于最下方的页面号,被压出栈若页面号已经在栈中,则将其从栈中移出,然后压入栈顶不必搜索LRUwithstack(graph)AlsoneedhardwareassistanceLRU–theproblemsFewmachineshavesufficienthardwaretosupportLRUsoapproximateitwiththeavailablehardwareManysystemshaveareferencebitineachpageWitheachpageassociateabit,initially=0Whenpageisreferencedbitsetto1.
(read/write)Itiseasytoreplacetheonewhichis0(ifoneexists).
ButwedonotknowtheorderLRU近似算法ThreevariantsAdditional-reference-bitsalgorithmSecond-chancealgorithmEnhancedSecond-chancealgorithmSecondchancealgorithm每个页设置一个访问位(referencebit)InspectthepagesinaFIFOmannerStartfromcurrentoldest(FIFO)page;Ifthepagehasreferencebit=0,replaceit,exit;Setitsreferencebitto0;givethepageasecondchanceLoopbacktostep1.
这个算法可以用在页表上,将页表看成一个循环队列,此时算法被称为Clock算法Secondchancealgorithm(cont'd)011011ref.
bitspagesNextvictimlater000011pagesNextvictimref.
bits改进型Second-ChanceAlgorithm+modifybitFourpageclasses(访问位,修改位)(0,0)–bestpagetoreplace(0,1)–notquiteasgood(1,0)–probablybeusedagainsoon(1,1)–probablybeusedagainsoon,andbedirtyReplacethefirstpageencounteredinthelowestnonemptyclass.
Scanfor(0,0)Scanfor(0,1),&setreferencebitsto0Loopbacktostep1基于访问次数的算法对每个页面统计访问次数LFUAlgorithm最少使用置换算法LFU=LeastFrequentlyUsedreplacespagewithsmallestcountSuffersfromthesituationinwhichapageisusedheavilyduringtheinitialphaseofaprocess,butthenisneverusedagain页面缓冲算法结合可变分配和局部置换置换算法可以比较简单例如FIFO从局部将被淘汰的页面置换出去但并不真正从内存中消失而是暂时保存在两个链表上对于未修改过的,保存在空闲链表上对于修改过的,保存在待写出链表上,定期或者定量的写出后,才挂到空闲链表上当需要一个页面被换入时,首先看是否能从空闲链表或者待写出链表上找到可以降低换入换出代价(特别是磁盘I/O)垃圾再利用请求分页请求分页的硬件支持请求分页的内存分配策略和分配算法调页策略页面置换算法请求分页的性能分析和改进请求分页系统的性能分析和改进抖动产生抖动的原因和抖动的预防Thrashing抖动当一个进程在请求调页上花费的时间比有效执行时间还要多时,认为发生了抖动.
即,过于频繁的页面换入换出现象原因:不恰当的多道程序度考虑这样的情况:请求调页,需要I/O,导致进程进入等待状态若使用全局置换策略,相互抢占物理页框若所有的进程都在进行请求调页,则系统会发现CPU利用率很低为了提高CPU利用率,OS将考虑进一步增加多道程序度----可能会调入更多的作业!
!
!