操作系统 内存管理

内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式分页存储管理方式分段存储管理段页式存储管理存储器的层次结构存储器是计算机系统的重要组成部分容量、价格和速度之间的矛盾内存、外存；易失性和永久性内存，是稀缺资源在现代计算机系统中，存储通常采用层次结构来组织多级存储器结构主存与寄存器高速缓存和磁盘缓存多级存储器结构StoragesystemsinacomputersystemcanbeorganizedinahierarchySpeed,accesstimeCostperbitVolatility主存vs.寄存器Same:AccessdirectlyforCPURegisternameMemoryaddressDifferent:accessspeedRegister,onecycleoftheCPUclockMemory,Manycycles(2ormore)Disadvantage:CPUneedstostallfrequently&thisisintolerableRemedyCache高级缓冲技术cachingCachingCopyinginformationintofasterstoragesystemWhenaccessing,firstcheckinthecache,ifIn:useitdirectlyNotin:getfromupperstoragesystem,andleaveacopyinthecacheUsingofcachingRegistersprovideahigh-speedcacheformainmemoryInstructioncache&datacacheMainmemorycanbeviewedasafastcacheforsecondarystorage……Magneticdisks磁盘Transfertime传输时间TT≈datasize*TransferrateTransferrate≈(nM/s)-1≈(nByte/us)-1≈1/nus/BytePositioningtime定位时间Seektime寻道TsRotationallatency旋转延迟TRTP≈Ts+TR≈mmsTTVS.TPPleaseStoredataclosely内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式分页存储管理方式分段存储管理段页式存储管理程序执行的基础知识VonNeumannarchitecture冯·诺依曼体系结构ProgrammustbebroughtintomemoryMainmemoryisusuallytoosmallProcessProgrammustbeplacedwithinaprocessforittobeexecuted作业池UserprogramsWheretoplacetheprogramseveralsteps（图）地址的类型Absoluteaddress绝对地址AddressseenbythememoryunitPhysicaladdress物理地址Logicaladdress逻辑地址GeneratedbytheCPUVirtualaddress虚拟地址Whencantheabsoluteaddresscanbedecided?Addressbinding地址的绑定Addressbinding地址绑定,thebindingofinstructionsanddatatomemory,可以在三种时刻进行CompiletimeIfmemorylocationknownapriori,absolutecodecanbegenerated;mustrecompilecodeifstartinglocationchanges.LoadtimeMustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime.ExecutiontimeBindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother.Needhardwaresupportforaddressmaps(e.g.,baseandlimitregisters)Memory-ManagementUnit(MMU)Hardwaredevice,逻辑地址物理地址Relocationregister重定位寄存器AddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemoryE.g.MS-DOSon80x86Userprogramdealswithlogicaladdresses,itNEVERseestherealphysicaladdresses.是否需要将进程的所有代码和数据一次性装入？Shallweputtheentireprogram&dataofaprocessinphysicalmemorybeforetheprocesscanbeexecuted?ForbettermemoryspaceutilizationDynamicloadingDynamiclinkingOverlaysSwapping…程序的装入绝对装入方式可重定位装入方式动态运行时装入方式绝对装入方式编译时，产生absolutecode，即使用绝对地址的代码装入时，必须装入到指定的地址无需对程序和数据的地址进行修改适用于单道系统可重定位装入方式大多数情况下，不能预知装入地址，只能在装入时确定编译时，产生可重定位代码，即使用相对地址的代码装入时，必须重定位通常把在装入时对目标程序中指令和数据的修改过程称为重定位。由于地址变换是在装入时一次性完成的，以后不再改变，故称为静态重定位可用于多道系统动态运行时重定位有时候，程序会在内存中移动位置例如对换需要能支持在运行过程中动态改变程序在内存中的位置方法：推迟重定位时机即从相对地址到绝对地址的转换推迟到程序真正执行时才进行因此，装入内存中的代码和数据的地址仍然是相对地址需要重定位寄存器的支持动态运行时装入方式根据程序运行的局部性，让程序及其数据在需要时才被装入Bettermemory-spaceutilization;unusedroutineisneverloaded.UsefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcasesErrorroutineNospecialsupportfromOSisrequiredimplementedthroughprogramdesignDuetotheusers程序的链接多个源程序编译多个目标模块；库。需要链接成可装入模块根据链接时间的不同静态链接方式：装入前很早就链接装入时动态链接：边装入，边链接运行时动态链接：运行时才链接静态链接方式静态链接方式：在程序运行之前，先将各目标模块以及它们所需要的库函数，链接成一个完整的装配模块，以后不再拆开。各目标模块内：相对地址存在目标模块之间的调用关系外部调用符号要解决的问题：修改相对地址：多个相对地址空间一个统一的相对地址空间变换外部调用符号装入时动态链接在装入时，根据外部模块调用事件，使用装入程序去寻找相应的外部目标模块，并装入，在装入时，修改相对地址优点：便于修改和更新便于实现对目标模块的共享运行时动态链接程序的每次运行，可能要执行的目标模块集是不同的全部装入？按需装入？运行时动态链接将对某些模块的链接推迟到程序执行时才进行需要操作系统配合优点：程序运行前的装入速度加快；省空间作业：从一个源程序到一个在内存中可执行的程序，一般需要哪几个步骤？有哪几种地址类型？有哪几种程序装入方式和链接方式？内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式分页存储管理方式分段存储管理段页式存储管理连续内存分配方式（contiguousmemoryallocation）连续分配存储管理方式单一连续固定分区动态分区对换内存通常被划分为两个分区（partitions）:系统区：常驻操作系统，通常位于内存低端用户区：提供给用户（进程）使用，常位于内存高端连续内存分配是指：从用户区中为每个进程分配一个单独的、连续的内存空间。主要有以下两种方式单一连续分配方式多分区式分配方式固定分区式动态分区式（可变分区式）单一连续分配方式最简单只能用于单用户、单任务系统存储保护机制存储管理单元，MMU或者不采用任何存储保护机制出于信任，或采用再启动方式，多分区式分配方式支持多道程序，用户区被进一步划分为若干个分区每一个分区装载一个进程多道程序度与分区的个数有关根据分区大小是固定的还是可变的固定分区方式大小固定；等大小or不等大小动态分区方式（可变分区方式）动态&可变：内存的划分是动态的，分区的大小随进程的大小确定，分区的数目随系统的运行而不断变化固定分区分配方式支持多道程序，用于60年代IBM－360的MFT中分区的划分方法，两种等大小不等大小但分区的大小一旦确定就不再发生变化分配算法：按大小顺序建立分区使用 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 0分区号大小（KB）起始地址(K)状态11530已分配23045已分配35075已分配4100125已分配操作系统作业A作业B作业C30K45K75K125K225K固定分区使用表分配算法缺点内存利用率低定义：内部碎片和外部碎片内部碎片：已经分配出去但得不到利用的存储区域外部碎片：不能被利用的小分区解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ：动态分区动态分区分配方式能根据进程实际需要的内存大小，动态分配能减少内部碎片关键数据结构：记录内存的使用情况，特别是空闲内存分配算法分配和回收操作数据结构空闲分区表，占用额外的空间空闲分区链，利用空闲分区序号分区大小起始地址状态前向指针N个字节可用后向指针N＋2N＋200分区分配算法在将一个新作业装入内存时，要从空闲分区表或空闲分区链中，选出一个分区分配给该作业，有三种常见的分配算法首次适应算法FF：FirstFit循环首次适应算法最佳适应算法：BestFit=smallest最差适应算法：WorstFist＝largest思考在一个系统中内存有如下的空闲区，10KB，4KB，20KB，18KB，7KB，9KB，12KB，以及15KB。在分别使用首次适应，最佳适应，最差适应以及循环首次适应算法，对下列3个连续空间分配，得到的空闲分区分别是什么？12KB10KB9KB分区分配操作分配设请求的分区大小为u.size；利用某种分配算法，找到待分配的分区，大小为m.size根据上述分区分配算法，有m.size>u.size判断m.size-u.size与min_size的大小min_size为事先约定的最小分区大小>，分割，分割出来的分配出去，余下的加入空闲数据结构否则，直接分配将分配到的分区的首地址返回可以看出，动态分区分配方式中内部碎片最大不超过min_size回收，要考虑合并向前合并只需修改前一个空闲分区表项中的大小向后合并（图）只需修改后一个空闲分区表项中的起始地址和大小与前后同时合并修改前一个空闲分区表项中的大小，并取消后一个分区表项无相邻空闲分区，无需合并建立一个新的表项，填写相关信息，插入上述过程中，根据链表的维护规则，可能需要调整相应表项在空闲链表中的位置动态分区分配分析随着分配的进行，空闲分区可能分散在内存的各处尽管有回收，但内存仍然被划分的越来越碎，形成大量的外部碎片OSprocess5process8process2OSprocess5process2OSprocess5process2OSprocess5process9process2process9process10解决方案之一：紧凑Compaction针对外部碎片：采用紧凑的方法紧凑：通过移动进程在内存中的位置，把多个分散的小分区拼成大分区需要动态重定位技术支持动态重定位分区分配算法：引入紧凑和动态重定位技术的动态分区分配算法基本与动态分区分配算法相同思考紧凑的时间开销：若计算机读一个32位的时间是10ns，那么紧凑128MB的空间需要多长时间？Swapping对换最早用于MIT的CTSS中单用户＋时间片＋对换对换是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存能提高内存利用率对换的单位：进程：整体对换；进程对换页、段：部分对换对换技术需要实现三个方面的功能对换空间的管理进程的换出进程的换入Backingstore，对换空间Fastdisk,largeenoughtoaccommodatecopiesofallmemoryimagesforallusers;mustprovidedirectaccesstothesememoryimages.为提高速度，考虑连续分配方式，忽略碎片问题需提供数据结构对空闲盘块进行管理方法类似动态分区分配方法进程的换出第一步：选择被换出的进程SomeapproachesRRscheduling:swappedoutwhenaquantumexpiresPriority-basedscheduling:Rollout,rollinLower-priorityprocessisswappedoutsohigher-priorityprocesscanbeloadedandexecuted.第二步：换出确定要换出的内容非共享的程序和数据段的换出共享的程序和数据段的换出：计数器申请对换空间，换出，并修改相关数据结构进程的换入第一步：选择被换入的进程考虑“静止就绪状态”的进程＋其他原则第二部：申请内存并换入申请成功申请失败：利用对换技术腾出内存SchematicViewofSwappingSwapping(cont.)ContextswitchSwappedin&outcosttoomuchAssume:processsize1MB,disktransferrate5MB/sec,averagelatency8msTransfertime=1MB/(5MB/sec)=1/5sec=200msSwaptime=208msSwapout&in=416MajorpartofswaptimeistransfertimeForRRscheduling,timequantumshould>>416msProblemsexistforpendingI/Oprocessesswapping内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（DiscreteMemoryAllocation）分页存储管理方式碎片<页分段存储管理从逻辑上进行分段段页式存储管理内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（DiscreteMemoryAllocation）分页存储管理方式碎片<页分段存储管理从逻辑上进行分段段页式存储管理分页存储管理方式1）将一个进程的地址空间分成若干个大小相等的片，称为页面或页（pages）2）内存空间也分成与页大小相同的若干个存储块，称为物理页或页框（pageframes）序号：0，1，……，n大小：取2的幂，512~8192B地址结构页内偏移：相对于页（页框）的起始地址的相对地址页（页框）号S对于32位地址长度若页（页框）的大小为4KB，则需要使用低端12位表示页内偏移剩余的高端20位可以表示220个页（页框），1M个页（页框）号p页（页框）内偏移d0111231计算页（页框）号和页（页框）内偏移的方法：地址：A页（页框）大小：L页（页框）号p＝A整除L页（页框）内偏移d＝AmodL考虑L是2的幂，不妨设为2N，则p＝A右移N位，即取A的高（32－N)位d＝A的低端N位必须在进程的逻辑地址空间和内存的物理地址空间之间建立一个映射关系使用页表每个进程都拥有各自的页面映射表，即页表按序号，进程地址空间中的每个页在页表中都有一个页表项表示页表项中记录的对应的物理页框的序号可以实现从页号到页框号的映射页表示意图页表的例子Pagesize=4BPhysicalmemory=32B8framesLogicalmemory=16B4pagesLogicaladdress9=2*4+1p=2,d=1Page2isstoredinframe1Physicaladdress=1*4+1=5思考下列10进制虚拟地址，分别计算页面大小为4KB和8KB时的页号和页内偏移200003276860000思考根据左图，计算出以下虚拟地址对应的物理地址2041008300地址变换机构使用专门的（软）硬件将用户地址空间中的逻辑地址转换为内存空间中的物理地址基本的地址变换机构具有快表的地址变换机构基本的地址变换机构Pagetableiskeptinmainmemory,&Page-TableBaseRegister(PTBR)PointstothepagetablecurrentlyusedPage-tablelengthregister(PRLR)IndicatessizeofthepagetableContextswitch+>3bEffectivememory-accesstime,timeneededforeverydata/instructionaccess需要2次访存Accessthepagetable&Accessthedata/instructionSolution:Aspecialfast-lookuphardwarecachecalledassociativeregistersortranslationlook-asidebuffers(TLBs)联想存储器，快表AssociativeregistersEachregister:akey&avalueParallelsearch(highspeed)Expensive,typically8~2048entriesAddresstranslation(A´,A´´)IfA´isinassociativeregister,getframe#out.Otherwisegetframe#frompagetableinmemory联想存储器，快表TLBmiss（TLB缺失）IfthepagenumberisnotintheassociativeregistersGet&storeHitratio（命中率）ThepercentageoftimesthatapagenumberisfoundintheassociativeregistersContextswitchTLBflushedTLBreplacementalgorithm具有块表的地址变换机构+>EffectiveAccessTime有效存取时间设：AssociativeLookup=timeunit;memorycycletime=ttimeunit;Hitratio=EffectiveAccessTime(EAT)EAT=(t+)+(2t+)(1–)=2t+–tIf(20ns),t(100ns),1(80%),2(98%):TLBhit:20+100=120nsTLBmiss:20+100+100=220nsEAT1=120*0.8+220*0.2=140nsEAT2=120*0.98+220*0.02=122ns思考从页表中读取数据的时间开销是5ns，从块表中读取数据的开销则是1ns，为使平均开销降为1ns，则块表的命中率至少为多少？MemoryProtection内存保护Ifpagesize2n,page&frameisalignedat2n,so…MemoryprotectionimplementedbyassociatingprotectionbitwitheachframeProvidereadonly,read-write,execute-onlyprotectionor…Valid-invalid“valid”:theassociatedpageisintheprocess’logicaladdressspace,andisthusalegalpage.“invalid”:thepageisnotintheprocess’logicaladdressspace.Valid/invalidbitexampleAddressspace214Pagesize2KBProcesssize(0~10468)Page5hasinternalfragmentationPTLR=6Page6&7areinvalid104861024012287两级和多级页表考虑：地址空间：32位；页大小4KB；有220即1M个页需要页表项：1M个假设，每个页表项使用32位表示，需要4MB的空间解决方案：进一步离散两级页表对页表分页，建立外层页表（页目录）则上述4MB的页表，进一步分为1K个页需要1K个页目录项假设每个页目录项使用32位表示，需要4KB因此，逻辑地址wherep1isanindexintotheouterpagetable,andp2isthedisplacementwithinthepageoftheouterpagetable.pagenumberpageoffsetp1p2d101012两级页表举例具有两级页表的地址变换机构++多级页表及其性能Levelnumber=L,effectmemoryaccessestime=(L+1)t考虑高速缓存技术：Cachehitrateof98percentyields:effectiveaccesstime=0.98×120+0.02×520=128nanoseconds.whichisonlya28percentslowdowninmemoryaccesstime.内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（DiscreteMemoryAllocation）分页存储管理方式碎片<页分段存储管理从逻辑上进行分段段页式存储管理分段存储管理方式引入分段的目的，是为了满足用户在编程和使用上的需求（逻辑上）在用户看来：Aprogramisacollectionofsegments.Asegmentisalogicalunitsuchas:mainprogram,procedure,function,method,Objectlocalvariables,globalvariables,commonblock,stack,symboltable逻辑地址空间AcollectionofsegmentseachsegmentTwodimensionaladdressspaceAlogicaladdressCompilerautomaticallyconstructssegmentsreflectingtheinputprogram.PascalcompilerFORTRANcompilerCcompiler,suchasgcc,…段号段内地址3116150Logicalviewofsegmentation分段的硬件支持段表2-Dlogicaladdress1-Dphysicaladdresses;每个段表项包括段在内存中的基地址段的长度Segment-tablebaseregister(STBR)Pointstothesegmenttable’slocationinmemory.Segment-tablelengthregister(STLR)Indicatesnumberofsegmentsusedbyaprogram;Segmentnumbersislegalifs4300+53=43533200+852=4052Howabout?分段的好处Relocation，可重定位，方便编程Dynamic,bysegmenttableSharingsharedsegmentssamesegmentnumberProtectionUsesegmenttableentryProtectionbitRead-only,execute-only,read/writeValidationbit,0illegalsegmentProtection&sharingatsegmentlevel动态增长动态链接段的共享关于代码的重入可重入代码，又称为“纯代码”，是一种允许多个进程同时访问的代码。绝对不允许可重入代码在执行中有任何改变针对段的内存管理由于段长不固定，采用动态分区管理方式分配：首次适应、最佳适应等等由于大小不固定，存在外部碎片可能要考虑“紧凑”由于采用动态分区管理方式内部碎片很少内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（DiscreteMemoryAllocation）分页存储管理方式碎片<页分段存储管理从逻辑上进行分段段页式存储管理段页式存储管理方式考虑在分段的基础上分页与单纯的分段相比在段表项中存放的不是段的起始地址，而是段所对应的页表的起始地址段页式举例：IA32体系结构中的段页机制IA32是基于分段的，分页可选常见的段寄存器如：CS,DS,ES,FS,GS,SSIA32使用全局描述符表GDT或者局部描述符表LDT每个描述符描述一个段，包括段大小、访问权限、基地址等使用段选择子索引一个段IA32的地址表示为，段：段内偏移Linearaddress=segmentbase+segmentoffset在不使用分页机制的情况下，线性地址就是物理地址否则，线性地址通过页表机制转换成物理地址IA32addresstranslation2-levelpagetable作业什么是内部碎片；什么是外部碎片画出最基本的分页地址变换机构。分页和分段的主要区别是什么？