Module9 MemoryManagement Background 背景 LogicalversusPhysicalAddressSpace 邏輯與物理地址空間 ContiguousAllocation 連續分配 Paging 分頁 Segmentation 分段 SegmentationwithPaging 段頁式 Swapping 交換 存儲層次結構 Background Background Programmustbebroughtintomemoryandplacedwithinaprocessforittobeexecuted 程序必需放入一個進程 并且送入內存才能被執行 Inputqueue collectionofprocessesonthediskthatarewaitingtobebroughtintomemoryforexecution 輸入隊列 磁盤上等待進入內存并執行的進程的集合 Userprogramsgothroughseveralstepsbeforebeingexecuted 用戶程序在執行之前必需經歷很多步驟 Background 源程序 編譯 目標模塊 庫 鏈接程序 裝入模塊 裝入程序 內存 Logicalvs PhysicalAddressSpace 重定位Theconceptofalogicaladdressspacethatisboundtoaseparatephysicaladdressspaceiscentraltopropermemorymanagement 邏輯地址空間的概念同物理地址空間相關聯 它是正確內存管理的中心 Logicaladdress generatedbytheCPU alsoreferredtoasvirtualaddress 邏輯地址 由CPU產生 也叫做虛擬空間 Physicaladdress addressseenbythememoryunit 物理地址 內存設備所讀入的地址 Logicalandphysicaladdressesarethesameincompile timeandload timeaddress bindingschemes logical virtual andphysicaladdressesdifferinexecution timeaddress bindingscheme 邏輯和物理地址在編譯時期和裝入時期的地址綁定策略是相同的 而在執行時間的地址綁定策略是不同的 BindingofInstructionsandDatatoMemory Compiletime 編譯時期 Ifmemorylocationknownapriori absolutecodecanbegenerated mustrecompilecodeifstartinglocationchanges 如果內存位置已知 可生成絕對代碼 如果開始位置改變 需要重新編譯代碼 Loadtime 裝入時期 Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime 如果存儲位置在編譯時不知道 則必須生成可重定位代碼 Executiontime 執行時期 Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother Needhardwaresupportforaddressmaps e g baseandlimitregisters 如果進程在執行時可以在內存中移動 則地址綁定要延遲到運行時 需要硬件對地址映射的支持 例如基址和限長寄存器 Addressbindingofinstructionsanddatatomemoryaddressescanhappenatthreedifferentstages 指令和數據綁定到內存地址可以在三個不同的階段發生 地址重定位 將程序裝入到與其地址空間不一致的物理空間 所引起的一系列地址變換過程 靜態地址重定位在裝入一個作業時 把作業中的指令地址全部轉換為絕對地址 在作業執行過程中就無須再進行地址轉換工作 動態地址重定位 動態地址重地位是在程序執行過程中 在CPU訪問內存之前 將要訪問的程序或數據地址轉換成內存地址 動態重定位依靠硬件地址變換機構完成 Memory ManagementUnit MMU Hardwaredevicethatmapsvirtualtophysicaladdress 硬件把虛擬地址映射到物理地址 InMMUscheme thevalueintherelocationregisterisaddedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory 在MMU策略中 基址寄存器中的值在其送入內存的時候被加入到用戶進程所產生的每個地址中 Theuserprogramdealswithlogicaladdresses itneverseestherealphysicaladdresses 用戶程序所對應到的是邏輯地址 物理地址對它從來都不可見 Memory ManagementUnit MMU Overlays Keepinmemoryonlythoseinstructionsanddatathatareneededatanygiventime 只是在內存中保留那些在特定時間所需要的指令和數據 Neededwhenprocessislargerthanamountofmemoryallocatedtoit 當進程比所分配的內存大時 覆蓋是必需的 Implementedbyuser nospecialsupportneededfromoperatingsystem programmingdesignofoverlaystructureiscomplex 由用戶執行 不需要操作系統的特別支持 覆蓋結構的程序設計很復雜 要求用戶清楚地了解程序的結構 并指定各程序段調入內存的先后次序 它是一種早期的主存擴充的方式 Overlays DynamicLoading Routineisnotloadeduntilitiscalled 例程在調用之前并不執行 Bettermemory spaceutilization unusedroutineisneverloaded 更好的內存空間利用率 沒有被使用的例程不被載入 Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases 當需要大量的代碼來處理不經常發生的事情時是非常有用的 Nospecialsupportfromtheoperatingsystemisrequiredimplementedthroughprogramdesign 不需要操作系統的特別支持 通過程序設計實現 DynamicLinking Linkingpostponeduntilexecutiontime 鏈接被推遲到執行時期 Smallpieceofcode stub usedtolocatetheappropriatememory residentlibraryroutine 小的代碼片 存根 用來定位合適的保留在內存中的庫程序 Stubreplacesitselfwiththeaddressoftheroutine andexecutestheroutine 存根用例程地址來替換自己 以及執行例程 Operatingsystemneededtocheckifroutineisinprocesses memoryaddress 操作系統需要檢查例程是否在進程的內存空間 Swapping Aprocesscanbeswappedtemporarilyoutofmemorytoabackingstore andthenbroughtbackintomemoryforcontinuedexecution 一個進程可以暫時被交換到內存外的一個備份區 隨后可以被換回內存繼續執行 Backingstore fastdisklargeenoughtoaccommodatecopiesofallmemoryimagesforallusers mustprovidedirectaccesstothesememoryimages 備份區 是一個固定的足夠大的可以容納所有用戶內存映像的拷貝 可以提供對這些內存映像的直接存取 由操作系統控制 利用外存空間 進程交換區 通過對進程實體的整體交換 來滿足用戶進程的內存需要 它的主要特點是打破了進程運行的駐留性 Swapping Rollout rollin swappingvariantusedforpriority basedschedulingalgorithms lower priorityprocessisswappedoutsohigher priorityprocesscanbeloadedandexecuted 滾入 滾出 交換由于基于優先級的算法而不同 低優先級的進程被換出 這樣高優先級的進程可以被裝入和執行 Majorpartofswaptimeistransfertime totaltransfertimeisdirectlyproportionaltotheamountofmemoryswapped 交換時間的主要部分是轉移時間 總的轉移時間直接同交換的內存的數量成比例 Modifiedversionsofswappingarefoundonmanysystems i e UNIXandMicrosoftWindows 在許多系統如 UNIX Windows中 可以找到一些被修正過的交換措施 SchematicViewofSwapping ContiguousAllocation Mainmemoryusuallydividedintotwopartitions 主存通常被分為兩部分 Residentoperatingsystem usuallyheldinlowmemorywithinterruptvector 為操作系統保留的部分 通常用中斷矢量保存在內存低端 Userprocessesthenheldinhighmemory 用戶進程保存在內存高端 ContiguousAllocation 連續分配方式 為一個程序分配一段連續的內存空間 主要有 單獨分區管理方式 多分區管理方式 是一種可用于多道程序的較簡單的存儲管理方式 又分為 固定分區方式可變分區方式Single partitionallocation 單獨分區分配 Relocation registerschemeusedtoprotectuserprocessesfromeachother andfromchangingoperating systemcodeanddata 基址寄存器策略由來保護用戶進程 同其他進程和改變的操作系統代碼和數據分開 Relocationregistercontainsvalueofsmallestphysicaladdress limitregistercontainsrangeoflogicaladdresses eachlogicaladdressmustbelessthanthelimitregister 基址寄存器包含最小物理地址的值 限長寄存器包含邏輯地址的范圍 每個邏輯地址必需比限長寄存器的值小 ContiguousAllocation 固定分區 FixedPartitioning 分配 固定式分區是在作業裝入之前 內存就被劃分成若干個固定大小的連續分區 劃分工作可以由系統管理員完成 也可以由操作系統實現 一旦劃分完成 在系統運行期間不再重新劃分 即分區的個數不可變 分區的大小不可變 所以 固定式分區又稱為靜態分區 劃分分區的方法如下 分區大小相等 只適用于多個相同程序的并發執行 處理多個類型相同的對象 缺乏靈活性 分區大小不等 多個小分區 適量的中等分區 少量的大分區 根據程序的大小 分配當前空閑的 適當大小的分區 固定分區 大小相同 固定分區 多種大小 固定分區 FixedPartitioning 分配 一般將內存的用戶區域劃分成大小不等的分區 可適應不同大小的作業的需要系統有一張分區說明表 每個表目說明一個分區的大小 起始地址和是否已分配的使用標志分區說明表和內存分配圖如下所示 分區說明表 內存分配圖 固定分區分配 優點 易于實現 開銷小 缺點 分區大小固定 內碎片分區總數固定 限制并發執行的進程數目 采用的數據結構 分區表 記錄分區的大小和使用情況 ContiguousAllocation Cont Multiple partitionallocation 多分區分配 Hole blockofavailablememory holesofvarioussizearescatteredthroughoutmemory 分區 可用的內存塊 不同大小的分區分布在整個內存中 Whenaprocessarrives itisallocatedmemoryfromaholelargeenoughtoaccommodateit 當一個進程到來的時候 它將從一個足夠容納它分區中分配內存 Operatingsystemmaintainsinformationabout 操作系統包含以下信息 a allocatedpartitions 分配的分區 b freepartitions hole 空的分區 OS process5 process8 process2 OS process5 process2 OS process5 process2 OS process5 process9 process2 process9 process10 空閑分區的管理 空閑分區表 前向指針 后向指針 空閑分區鏈 ContiguousAllocation Cont DynamicStorage AllocationProblem First fit 首先適應 Allocatethefirstholethatisbigenough 分配最先找到的合適的分區 Best fit 最佳適應 Allocatethesmallestholethatisbigenough mustsearchentirelist unlessorderedbysize Producesthesmallestleftoverhole 搜索整個序列 找到適合條件的最小的分區進行分配 Worst fit 最差適應 Allocatethelargesthole mustalsosearchentierlist Producesthelargestleftoverhole 搜索整個序列 尋找最大的分區進行分配 Howtosatisfyarequestofsizenfromalistoffreeholes 怎樣從一個空的分區序列中滿足一個申請需要 First fitandbest fitbetterthanworst fitintermsofspeedandstorageutilization 在速度和存儲的利用上 首先適應和最佳適應要比最差適應好 首次適應算法 FirstFit 從空閑分區表的第一個表目開始查找 把找到的第一個滿足要求的空閑區分配給作業 目的在于減少查找時間 通常將空閑分區表 空閑區鏈 中的空閑分區要按地址由低到高進行排序 特點 分配和釋放的時間性能較好 較大的空閑分區可以被保留在內存高端 隨著低端分區不斷劃分而產生較多小分區 每次分配時查找時間開銷會增大 在系統不斷地分配和回收中 必定會出現一些不連續的小的空閑區 稱為外碎片 雖然可能所有碎片的總和超過某一個作業的要求 但是由于不連續而無法分配 最佳適應算法 BestFit 從全部空閑區中找出能滿足作業要求的 且最小的空閑分區 能使碎片盡量小為提高查找效率 空閑分區表 空閑區鏈 中的空閑分區要按從小到大進行排序 自表頭開始查找到第一個滿足要求的自由分區分配特點 從個別來看 外碎片較小 但從整體來看 會形成較多無法利用的碎片 較大的空閑分區可以被保留 ContiguousAllocation Cont Fragmentation Externalfragmentation 外碎片 totalmemoryspaceexiststosatisfyarequest butitisnotcontiguous 整個內存空間用來滿足一個請求 但它不是連續的 Internalfragmentation 內碎片 allocatedmemorymaybeslightlylargerthanrequestedmemory thissizedifferenceismemoryinternaltoapartition butnotbeingused 分配的內存可能比申請的內存大一點 這兩者之間的差別是內部不被使用的簇 緊縮Reduceexternalfragmentationbycompaction 通過壓縮來減少外碎片 Shufflememorycontentstoplaceallfreememorytogetherinonelargeblock 把一些小的空閑內存結合成一個大的塊 Compactionispossibleonlyifrelocationisdynamic andisdoneatexecutiontime 只有重置是動態的時候 才有可能進行壓縮 壓縮在執行時期進行 I Oproblem I O問題 LatchjobinmemorywhileitisinvolvedinI O 當I O的時候 把工作鎖定在內存中 DoI OonlyintoOSbuffers 只對操作系統的緩沖區進行I O Fragmentation 實現緊湊的技術必須獲得硬件支持 只有具有動態重定位硬件機構的計算機系統 才有可能采用動態重定位可變分區管理技術 系統的硬件包括重定位寄存器和加法器 Paging 分頁存儲管理是解決存儲碎片的一種方法 Logicaladdressspaceofaprocesscanbenoncontiguous processisallocatedphysicalmemorywheneverthelatterisavailable 進程的邏輯地址空間可能是不連續的 如果有可用的物理內存 它將分給進程 Dividephysicalmemoryintofixed sizedblockscalledframes sizeispowerof2 between512bytesand8192bytes 把物理內存分成大小固定的塊 Dividelogicalmemoryintoblocksofsamesizecalledpages 把邏輯內存也分為固定大小的塊 叫做頁 Keeptrackofallfreeframes 保留一個頁的記錄 Torunaprogramofsizenpages needtofindnfreeframesandloadprogram 運行一個有N頁大小的程序 需要找到N個空的頁框讀入程序 Setupapagetabletotranslatelogicaltophysicaladdresses 建立一個頁表 把邏輯地址轉換為物理地址 Internalfragmentation 內碎片 AddressTranslationScheme AddressgeneratedbyCPUisdividedinto CPU產生的地址被分為 Pagenumber p 頁號 usedasanindexintoapagetablewhichcontainsbaseaddressofeachpageinphysicalmemory 它包含每個頁在物理內存中的基址 用來作為頁表的索引 Pageoffset d 偏移 combinedwithbaseaddresstodefinethephysicalmemoryaddressthatissenttothememoryunit 同基址相結合 用來確定送入內存設備的物理內存地址 Forgivenlogicaladdressspace2mandpagesize2n pagenumber pageoffset p d m n n AddressTranslationArchitecture 地址結構 圖中的地址長度為32位 允許地址空間的大小最多為1M個頁 P A L 整除 W AMODL 取余 程序經過編譯鏈接后形成邏輯地址 對某特定機器其地址結構是一定的 若給定一個邏輯地址為A 十進制 頁面大小為L 則頁號P和頁內地址W可按下式求得 PagingExample PagingExample ImplementationofPageTable Pagetableiskeptinmainmemory 頁表被保存在主存中 Page tablebaseregister PTBR pointstothepagetable 頁表基址寄存器指向頁表 Page tablelengthregister PRLR indicatessizeofthepagetable 頁表限長寄存器表明頁表的長度 Inthisschemeeverydata instructionaccessrequirestwomemoryaccesses Oneforthepagetableandoneforthedata instruction 在這個機制中 每一次的數據 指令存取需要兩次內存存取 一次是存取頁表 一次是存取數據 Thetwomemoryaccessproblemcanbesolvedbytheuseofaspecialfast lookuphardwarecachecalledassociativeregistersortranslationlook asidebuffers TLBs 通過一個聯想寄存器 可以解決兩次存取的問題 ImplementationofPageTable AssociativeRegister Associativeregisters parallelsearch 聯想寄存器 并行查找 Addresstranslation A A 地址轉換 IfA isinassociativeregister getframe out 如果A 在聯想寄存器中 把頁框 取出來 Otherwisegetframe frompagetableinmemory 否則從內存中的頁表中取出頁框 Page Frame EffectiveAccessTime AssociativeLookup timeunit 聯想寄存器的查找需要時間 Assumememorycycletimeis1microsecond 假設內存一次存取要1微秒 Hitration percentageoftimesthatapagenumberisfoundintheassociativeregisters rationrelatedtonumberofassociativeregisters 命中率 在聯想寄存器中找到頁號的比率 比率與聯想寄存器的大小有關 Hitratio EffectiveAccessTime EAT 有效存取時間 EAT 1 2 1 2 EffectiveAccessTime 例如 假設檢索聯想存儲器的時間為20ns 訪問內存的時間為100ns 訪問聯想存儲器的命中率為85 則CPU存取一個數據的平均時間 T 0 85 120 0 15 220 135ns 訪問時間只增加35 如果不引入聯想存儲器 其訪問將延長一倍 達200ns 頁式地址變換 虛地址 邏輯地址 程序地址 以十六進制 八進制 二進制的形式給出將虛地址轉換成二進制的數 按頁的大小分離出頁號和位移量 低位部分是位移量 高位部分是頁號 虛地址以十進制數給出頁號 虛地址 頁大小位移量 虛地址mod頁大小以頁號查頁表 得到對應頁裝入內存的塊號內存地址 塊號 頁大小 位移量 舉例 例1 有一系統采用頁式存儲管理 有一作業大小是8KB 頁大小為2KB 依次裝入內存的第7 9 A 5塊 試將虛地址0AFEH 1ADDH轉換成內存地址 虛地址0AFEH0000101011111110P 1W 01011111110MR 0100101011111110 4AFEH虛地址1ADDH0001101011011101P 3W 01011011101MR 0010101011011101 2ADDH MemoryProtection Memoryprotectionimplementedbyassociatingprotectionbitwitheachframe 內存的保護由與每個頁框相連的保護位來執行 Valid invalidbitattachedtoeachentryinthepagetable 有效 無效位附在頁表的每個表項中 valid indicatesthattheassociatedpageisintheprocess logicaladdressspace andisthusalegalpage 有效 表明相關的頁在進程的邏輯地址空間 以及是一個合法的頁 invalid indicatesthatthepageisnotintheprocess logicaladdressspace 無效 表明頁不在進程的邏輯地址空間中 MemoryProtection Two LevelPage TableScheme 將頁表進行分頁 每個頁面的大小與內存物理塊的大小相同 并為它們進行編號 可以離散地將各個頁面分別存放在不同的物理塊中 為此再建立一張頁表 稱為外層頁表 頁表目錄 即第一級頁表 其中的每個表目是存放某個頁表的物理地址 第二級才是頁表 其中每個物理塊上的頁表叫做頁表分頁 其中的每個表目所存放的才是頁的物理塊號 Two LevelPage TableScheme Two LevelPagingExample Alogicaladdress on32 bitmachinewith4Kpagesize isdividedinto 一個邏輯地址被分為 apagenumberconsistingof20bits 一個20位的頁號 apageoffsetconsistingof12bits 一個12位的偏移 Sincethepagetableispaged thepagenumberisfurtherdividedinto 頁表頁被分為 a10 bitpagenumber 一個10位的頁號 a10 bitpageoffset 一個10位的偏移 Thus alogicaladdressisasfollows 因此 一個邏輯地址表示如下 wherepiisanindexintotheouterpagetable andp2isthedisplacementwithinthepageoftheouterpagetable pagenumber pageoffset pi p2 d 10 10 12 Address TranslationScheme Address translationschemeforatwo level32 bitpagingarchitecture 一個兩級32位分頁結構的地址轉換機制 MultilevelPagingandPerformance Sinceeachlevelisstoredasaseparatetableinmemory coveringalogicaladdresstoaphysicalonemaytakefourmemoryaccesses 由于每一級都分開的以表的形式存儲在內存中 把一個邏輯地址轉換為一個物理地址可能要進行4次內存存取 Eventhoughtimeneededforonememoryaccessisquintupled cachingpermitsperformancetoremainreasonable 盡管每次內存存取的時間是很大的 高速緩存使執行的時間還是可以接受的 Cachehitrateof98percentyields 如果緩存的命中率有98 則 effectiveaccesstime 0 98x120 0 02x520 128nanoseconds whichisonlya28percentslowdowninmemoryaccesstime 這只把內存存取時間降低了28 InvertedPageTable Oneentryforeachrealpageofmemory 一個內存中頁的表項 Entryconsistsofthevirtualaddressofthepagestoredinthatrealmemorylocation withinformationabouttheprocessthatownsthatpage 表項包含真正內存地址的頁的虛擬地址 它包括擁有這個頁的進程的信息 Decreasesmemoryneededtostoreeachpagetable butincreasestimeneededtosearchthetablewhenapagereferenceoccurs 減少內存需要儲存每個頁表 但是當訪問一個頁時 尋找頁表需要增加時間 Usehashtabletolimitthesearchtoone oratmostafew page tableentries 使用哈希表來減少搜索 InvertedPageTableArchitecture SharedPages Sharedcode 共享代碼 Onecopyofread only reentrant codesharedamongprocesses i e texteditors compilers windowsystems 一個只讀 可再入 代碼可由進程共享 Sharedcodemustappearinsamelocationinthelogicaladdressspaceofallprocesses 共享代碼出現在所有進程的邏輯地址空間的相同位置 Privatecodeanddata 私有代碼和數據 Eachprocesskeepsaseparatecopyofthecodeanddata 每個進程保留一個代碼和數據的私有拷貝 Thepagesfortheprivatecodeanddatacanappearanywhereinthelogicaladdressspace 私有代碼和數據的頁可以出現在邏輯地址空間的任何地方 SharedPagesExample Segmentation Memory managementschemethatsupportsuserviewofmemory 內存管理機制支持用戶觀點的內存 Aprogramisacollectionofsegments Asegmentisalogicalunitsuchas 一個程序是一些段的集合 一個段是一個邏輯單位 如 mainprogram procedure function localvariables globalvariables commonblock stack symboltable arrays LogicalViewofSegmentation userspace physicalmemoryspace SegmentationHardware SegmentationArchitecture Logicaladdressconsistsofatwotuple 一個邏輯地址是兩個向量的集合 Segmenttable mapstwo dimensionalphysicaladdresses eachtableentryhas 段表 映射二維物理地址 每個表項包括 base containsthestartingphysicaladdresswherethesegmentsresideinmemory 基址 包括內存中段物理地址的起始地址 limit specifiesthelengthofthesegment 限長 指定段的長度 Segment tablebaseregister STBR pointstothesegmenttable slocationinmemory 段表基址寄存器指向段表在內存中的地址 Segment tablelengthregister STLR indicatesnumberofsegmentsusedbyaprogram 段表限長寄存器表明被一個程序所使用的段的數目 segmentnumbersislegalifs STLR SegmentationArchitecture Cont Relocation 重定位 dynamic 動態 bysegmenttable 由段表來執行 Sharing 共享 sharedsegments 共享的段 samesegmentnumber 同樣的段號 Allocation 分配 firstfit bestfit 首先 最佳適配 externalfragmentation 外碎片 SegmentationArchitecture Cont Protection Witheachentryinsegmenttableassociate 保護 每個段表的表項有 validationbit 有效位 0 illegalsegmentread write executeprivileges 讀 寫 執行權利 Protectionbitsassociatedwithsegments codesharingoccursatsegmentlevel 保護位同段相聯系 在段的級別進行代碼共享 Sincesegmentsvaryinlength memoryallocationisadynamicstorage allocationproblem 由