操作系统_虚拟内存_CCH1012963.pptx
Silberschatz,Galvin,and Gagne 1999 10.1Module10:VirtualMemory Background（背景）DemandPaging（请求页式）PerformanceofDemandPaging（请求页式的性能）PageReplacement（页置换）Page-ReplacementAlgorithms（页置换算法）AllocationofFrames（页框的分配）Thrashing（颠簸）OtherConsiderations（其他考虑）DemandSegmenation（请求段式）Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.2Background Virtualmemoryseparationofuserlogicalmemoryfromphysicalmemory.（虚拟内存物理内存和用户逻辑内存的区分）局部性原理(principleoflocality)时间局部性，空间局部性 Onlypartoftheprogramneedstobeinmemoryforexecution（只有部分运行的程序需要在内存中）.Logicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace（因此，逻辑地址空间能够比物理地址空间大）.Needtoallowpagestobeswappedinandout（必须允许页面能够被换入和换出）.Virtualmemorycanbeimplementedvia（虚拟内存能够通过以下手段来执行）:Demandpaging（请求页式）Demandsegmentation（请求段式）Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.3（1）虚拟存储器的基本概念1.虚拟存储器的引入1)局部性原理 在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中还包括许多对数据结构的处理，如对连续的存储空间数组的访问，往往局限于很小的范围内。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.4局限性表现为：时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.5Background虚拟存储的基本原理根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上 程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用OS所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。如果内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.6Background引入虚拟存储技术的好处可在较小的可用内存中执行较大的用户程序可在内存中容纳更多程序并发执行不必影响编程时的程序结构（与覆盖技术比较）提供给用户可用的虚拟内存空间通常大于物理内存(realmemory)Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.7Background虚拟存储技术的特征l 离散性：指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。l 多次性：指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。l 对换性：指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。l 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.8Backgroundpage0.Page nVirtual memoryMemorymapPhysicalmemoryApplied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.9虚拟存储器实现方式1)请求分页系统：在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页（而非全部程序）的用户程序和数据，就可以启动运行，以后再通过调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。2)请求分段系统：在分段系统的基础上，增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段（而非全部段）的用户程序和数据，就可以启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换以段为单位。3)请求段页式系统：它是在段页式系统的基础上，增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.10DemandPaging Bringapageintomemoryonlywhenitisneeded（只有在一个页需要的时候才把它换入内存）.LessI/Oneeded（需要很少的I/O）Lessmemoryneeded（需要很少的内存）Fasterresponse（快速响应）Moreusers（多用户）Pageisneeded（需要页）referencetoit（查阅此页）invalidreference（无效的访问）abort（中止）not-in-memory（不在内存）bringtomemory（换入内存）取页-将哪部分装入内存 置页-将调入的页放在什么地方 淘汰-内存不足时，将哪些页换出内存。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.11请求分页存储管理方式1.请求分页中的硬件支持它是在纯分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。1)请求分页的页表机制它是在纯分页的页表机制上形成的，由于只将应用程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如图所示。页号 物理块号 状态位P 访问字段A 修改位M 外存地址Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.12其中各字段说明如下：状态位（存在位P）：用于指示该页是否已调入内存，供程序访问时参考。访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.13请求分页中的硬件支持2）缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。与一般中断的主要区别在于：缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.14请求分页中的硬件支持3)地址变换机构 请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等，下图给出了请求分页系统的地址变换过程。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.15 缺页中断处理 是 否 否 是 是 否 产生缺页中 否 是 断请求调页 是开始（程序请求访问一页)越界中断CPU检索快表页表项是否在快表中？访问页表页是否在内存中？修改快表修改访问位和修改位形成物理地址 地址变换结束保留CPU现场 从外存中找到缺页 页号页表长度？内存满否？选择一页换出 该页是否被修改？将该页写回外存 将一页从外存换入内存 修改页表 CPU从外存读缺页 启动I/O硬件 Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.16Valid-InvalidBit Witheachpagetableentryavalidinvalidbitisassociated(1 in-memory,0 not-in-memory)（在每一个页表的表项有一个有效-无效位相关联，1表示在内存，0表示不内存）Initiallyvalidinvalidbutissetto0onallentries（在所有的表项，这个位被初始化为0）.Exampleofapagetablesnapshot（一个页表映象的例子）.Duringaddresstranslation,ifvalidinvalidbitinpagetableentryis0（在地址转换中，如果页表表项位的值是0）pagefault（缺页）.1111000Frame#valid-invalid bitpage tableApplied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.17PageFault Ifthereiseverareferencetoapage,firstreferencewilltraptoOS（如果有对一个页的访问，第一个访问要陷入OS）pagefault（缺页）OSlooksatanothertabletodecide（OS查看另一个表来决定）:Invalidreference（无效引用）abort（终止）.Justnotinmemory（仅仅不在内存）.Getemptyframe（得到空的页框）.Swappageintoframe（把页换入页框）.Resettables,validationbit=1（重新设置页表，把位设为1）.Restartinstruction（重启指令）:LeastRecentlyUsed（最近未使用）blockmove（块移动）autoincrement/decrementlocation（区域自动增长/缩减）Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.18StepsinhandlingapagefaultLoad M i Free frameOperatingsystemPagetable1reference6 Restart instruction5 Reset page table3 page is on backing store2 trapPhysical memory4 bring in missing pageApplied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.19Whathappensifthereisnofreeframe?1.wecheckaninternaltable(usuallykeptwiththeprocesscontrolblock)forthisprocess,todeterminewhetherthereferencewasavalidorinvalidmemoryaccess.2.ifthereferencewasinvalid,weterminatetheprocess.Ifitwasvalid,butwehavenotyetbroughtinthatpage,wenowageitin.3.wefindafreeframe(bytakingonefromthefree-framelist,forexample)4.wescheduleadiskoperationtoreadthedesiredpageintothenewlyallocatedframe.5whenthediskreadiscomplete,wemodifytheinternaltablekeptwiththeprocessandthepagetabletoindicatethatthepageisnowinmemory 6.Werestarttheinstructionthatwasinterruptedbytheillegaladdresstrap.theprocesscannowaccessthepageasthoughithadalwaysbeeninmemoryApplied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.20Whathappensifthereisnofreeframe?Page replacement find some page in memory,but not really in use,swap it out（页置换找到内存中并没有使用的一些页，换出）.Algorithm（算法）Performance（性能）want an algorithm which will result in minimum number of page faults（找出一个导致最小缺页数的算法）.Same page may be brought into memory several times（同一个页可能会被装入内存多次）.Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.21调入策略、分配策略和清除策略调入策略(fetchpolicy)(1)请求调页(demandpaging)(2)预调页(prepaging)分配策略(assignmentpolicy)清除策略(cleaningpolicy)请求清除(demandcleaning)预清除(precleaning)Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.22页面调入策略 为能使进程运行，必须事先将一部分要执行的程序和数据调入内存。1)调入页面的时机预调页策略：是一种主动的缺页调入策略，即将那些预计在不久的将来会被访问的程序或数据所在的页面，预先调入内存。由于预测的准确率不高（50%），所以这种策略主要用于进程的首次调入。有的系统将预调页策略用于请求调页，Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.23页面调入策略请求调页策略：是指当进程在运行中发生缺页时，就立即提出请求，由系统将缺页调入内存。目前的虚拟存储器中，大多采用此策略。但这种策略在调页时须花费较大的系统开销，如需频繁启动磁盘I/O。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.24页面调入策略2)从何处调入页面在虚拟存储系统中，外存（硬盘）常常被分成两部分；文件区（用于存放文件）和对换区（用于存放对换页面）。通常，对换区（连续分配）的磁盘I/O速度比文件区（离散分配）要高。每当进程发出缺页请求时，系统应从何处将缺页调入内存呢？在UNIX系统中，对于从未运行过的页面，都应从硬盘文件区调入；对于曾经运行过而又被换出的页面，可以从对换区调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.25PerformanceofDemandPaging Apagefaultcausethefollowingsequencetooccur:1.Traptotheoperatingsystem 2.Savetheuserregistersandprocessstate 3.Determinethattheinterruptwasapagefault 4.Checkthatthepagereferencewaslegalanddeterminethelocationofthepageonthedisk 5.Issueareadfromthedisktoafreeframe:a.Waitinaqueueforthisdeviceuntilthereadrequestisserviced.b.Waitforthedevicesseekand/orlatencytime c.Beginthetransferofthepagetoafreeframe 6.Whilewaiting,allocatethecputosomeuser(cpuschedulingoperation)7.Interruptfromthedisk(I/Ocompleted)8.Savetheregistersandprocessstatefortheotheruser(ifstep6executed)9.Determinethattheinterruptwasfromthedisk 10.Correctthepagetableandothertablestoshowthatthedesiredpageisnowinmemory 11.Waitforthecputobeallocatedtothisprocessagain 12Restoretheuserregisters,processstate,andnewpagetable,thenresumetheinterruptedinstruction.Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.26缺页率l假定作业Ji共有m页，系统分配给它的主存块为n块，这里mn。开始时，主存没有装入任何一页的信息。如果作业Ji在运行中成功访问的次数为S，不成功的访问次数为F(产生缺页中断的次数)，则作业执行过程中总的访问次数为A.A=S（成功访问的次数）+F（不成功的访问次数）作业Ji执行过程中的缺页率f=F/A。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.27PerformanceofDemandPaging PageFaultRate0 p 1.0（缺页率0 p 1.0）ifp=0nopagefaults（如果p=0，没有缺页）ifp=1,everyreferenceisafault（每次访问都缺页）EffectiveAccessTime(EAT)（有效存取时间）EAT=(1p)xmemoryaccess+p(pagefaultoverhead+swappageout+swappagein+restartoverhead)Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.28DemandPagingExample Memoryaccesstime=1microsecond（存取内存的时间）50%ofthetimethepagethatisbeingreplacedhasbeenmodifiedandthereforeneedstobeswappedout（50%的时间，所置换的页被修改，因此需要被换出）.SwapPageTime=10msec（交换页的时间）EAT=(1p)x1+p(10)=1+9P(inmsec)Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.29PageReplacement Preventover-allocationofmemorybymodifyingpage-faultserviceroutinetoincludepagereplacement（通过修改缺页服务例程，来包含页置换，防止分配过多）.Usemodify(dirty)bittoreduceoverheadofpagetransfersonlymodifiedpagesarewrittentodisk（修改（脏）位来防止页面转移过多只有被修改的页面才写入磁盘）.Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemorylargevirtualmemorycanbeprovidedonasmallerphysicalmemory（页置换完善了逻辑内存和物理内存的划分在一个较小的物理内存基础之上可以提供一个大的虚拟内存.Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.30Page-ReplacementAlgorithms Wantlowestpage-faultrate（需要一个最小的缺页率）.Evaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstring（通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数）.Inallourexamples,thereferencestringis（在所有的例子中，访问序列是）1,2,3,4,1,2,5,1,2,3,4,5.Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.31Page-ReplacementAlgorithms1.最佳算法(OPT,optimal)2.最近最久未使用算法(LRU,LeastRecentlyUsed)3.先进先出算法(FIFO)Belady现象4.轮转算法(clock)最近未使用算法(NRU,NotRecentlyUsed)5.最不常用算法(LFU,LeastFrequentlyUsed)Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.32先进先出（FIFO）置换算法Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.33先进先出（FIFO）置换算法Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.34First-In-First-Out(FIFO)Algorithm Reference string:1,2,3,4,1,2,5,1,2,3,4,5 3 frames(3 pages can be in memory at a time per process)4 frames FIFO Replacement Beladys Anomaly（FIFO算法可能会产生Belady异常）more frames less page faults（页就是更多的页框相反会产生更多的缺页）1231234125349 page faults1231235124510 page faults44 3Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.35页面置换算法.最佳（Optimal）置换算法 它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.36页面置换算法 例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下图所示，进程运行时先将7，0，1三个页面装入内存。当进程访问页面2时，产生缺页中断，此时OS根据最佳置换算法，页面7将在第18次才被访问，是三页中将最久不被访问的页面，所以被淘汰。接着访问页面0时，发现已在内存中，而不会产生缺页中断，以此类推。从图可以看出，采用最佳置换算法，只发生了6次页面置换。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.37最佳（Optimal）置换算法发生了6次面置换，9次缺页中断。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.38OptimalAlgorithm Replace page that will not be used for longest period of time（被置换的页将是之后最长时间不被使用的页）.4 frames example 1,2,3,4,1,2,5,1,2,3,4,5 How do you know this?（怎样知道的）Used for measuring how well your algorithm performs（用来衡量你的算法的效率）.12346 page faults45Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.39最近最久未使用置换算法Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.40LeastRecentlyUsed(LRU)Algorithm Reference string:1,2,3,4,1,2,5,1,2,3,4,5 Counter implementation（计数器的实现）Every page entry has a counter;every time page is referenced through this entry,copy the clock into the counter（每一个页表项有一个计数器，每次页通过这个表项被访问，把记录拷贝到计数器中）.When a page needs to be changed,look at the counters to determine which are to change（当一个页需要改变是，查看计数器来觉得改变哪一个页0.）12354435Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.41LRUAlgorithm(Cont.)Stackimplementationkeepastackofpagenumbersinadoublelinkform（栈实现在一个双链表中保留一个记录页数目的栈）:Pagereferenced（被访问的页）:T moveittothetop（移到栈顶）T requires6pointerstobechanged（需要改变6个指针）Nosearchforreplacement（没有为置换进行查找）Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.42LRU近似算法这种算法，只要在存储分块表（或页表）中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问过的页面其引用位为0。因此，可根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页，如图所示的算法。图是这种近似算法的一个例子。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.43LRU近似算法 Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.44 LRU近似算法举例Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.45LRUApproximationAlgorithms Referencebit（访问位）Witheachpageassociateabit,initially-=0（每个页都与一个位相关联，初始值位0）Whenpageisreferencedbitsetto1（当页是访问位是设位1）.Replacetheonewhichis0(ifoneexists).Wedonotknowtheorder,however（，如果存在的话置换位为0的页。然而我们并不知道这个置换顺序）.Secondchance（二次机会）Needreferencebit.（需要访问位）Clockreplacement.（时钟置换）Ifpagetobereplaced(inclockorder)hasreferencebit=1.Then（如果将要（以顺时针）交换的访问位是1，则）:T setreferencebit0（把访问位设位0）.T leavepageinmemory（把页留在内存中）.T replacenextpage(inclockorder),subjecttosamerules（以同样的规则，替换下一个页）.Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.46CountingAlgorithms Keepacounterofthenumberofreferencesthathavebeenmadetoeachpage.（用一个计数器记录对每一个页的访问次数。）LFUAlgorithm:replacespagewithsmallestcount（以最小的计数置换一个页）.MFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused（以下面的观点为基础，最小计数的页也许刚刚被换入和使用）.Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.47AllocationofFrames Eachprocessneedsminimumnumberofpages（每个进程所需要的最少的页的数目）.Example:IBM3706pagestohandleSSMOVEinstruction:instructionis6bytes,mightspan2pages.2pagestohandlefrom.2pagestohandleto.Twomajorallocationschemes（两个主要的分配策略）.fixedallocation（固定分配）priorityallocation（优先分配）Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.48页面分配1)最少物理块数在为进程分配物理块时，首先应该考虑的问题是：能保证进程能正常运行所需的最少物理块数（称为最小物理块数）。若系统为某进程所分配的物理块数少于此值时，进程将无法运行，这取决于指令的格式、功能和寻址方式。Applied Operating System ConceptsSilberschatz,Galvin,and Gagne 1999 10.49页面分配2)页面的分配和置换策略在请求分页系统中，可采取两种分配策略固定和可变分配策略。在进行置换时，也可采取两种策略全局置换和局部置换。于是可组合成以下三种策略：固定分配局部置换策略：它基于进程的类型（交互型或批处理型等），或根据程序员、系统管理员的建议
