第四章存儲管理(上)存儲管理概述(

)內存管理的基本原理(

)Windows的內存管理外存管理的基本原理Windows的外存管理高速緩存管理的基本原理Windows的高速緩存管理1存儲體系存儲管理的功能邏輯地址和物理地址重定位技術存儲管理概述2存儲體系高速緩存：DataCacheTLB(TranslationLookasideBuffer)內存：DRAM,SDRAM等；外存：軟盤、硬盤、光盤、磁帶等；外存(secondarystorage)DOS核心命令處理程序內存(primarystorage)高速緩存(cache)寄存器(register)3存儲管理的功能存儲分配和回收：分配和回收算法及相應的數據結構。地址變換：可執行文件生成中的鏈接技術程序加載(裝入)時的重定位技術進程運行時硬件和軟件的地址變換技術和機構存儲共享和保護：代碼和數據共享地址空間訪問權限（讀、寫、執行）存儲器擴充：存儲器的邏輯組織和物理組織；由應用程序控制：覆蓋；由OS控制：交換（整個進程空間），虛擬存儲的請求調入和預調入（部分進程空間）4地址映射BA=10003456

。

。

。1200物理地址空間movax,data1data13456源程序movax,[200]34560100200編譯連接邏輯地址空間邏輯地址和物理地址movax,[1200]100011006重定位技術重定位：在可執行文件裝入時需要解決可執行文件中地址（指令和數據）和內存地址的對應。由操作系統中的裝入程序來完成。重定位方法：絕對裝入可重定位裝入動態裝入7絕對裝入(absoluteloading)優點：裝入過程簡單。缺點：過于依賴于硬件結構，不適于多道程序系統。在可執行文件中記錄內存地址，裝入時直接定位在上述(即文件中記錄的地址)內存地址。8可重定位裝入(relocatableloading)優點：不需硬件支持，可以裝入有限多道程序缺點：一個程序通常需要占用連續的內存空間，程序裝入內存后不能移動。不易實現共享。在可執行文件中，列出各個需要重定位的地址單元和相對地址值。當用戶程序被裝入內存時，一次性實現邏輯地址到物理地址的轉換，以后不再轉換（一般在裝入內存時由軟件完成）。即：裝入時根據所定位的內存地址去修改每個重定位地址項，添加相應偏移量。9動態裝入(dynamicrun-timeloading)優點：OS可以將一個程序分散存放于不連續的內存空間，可以移動程序，有利用實現共享。能夠支持程序執行中產生的地址引用，如指針變量（而不僅是生成可執行文件時的地址引用）。缺點：需要硬件支持（通常是CPU），OS實現較復雜。它是虛擬存儲的基礎。在可執行文件中記錄虛擬內存地址，裝入和執行時通過硬件地址變換機構，完成虛擬地址到實際內存地址的變換。10單一連續區存儲管理分區存儲管理頁式和段式存儲管理虛擬存儲器內存管理的基本原理11單一連續區存儲管理內存分為兩個區域：系統區，用戶區。應用程序裝入到用戶區，可使用用戶區全部空間。最簡單，適用于單用戶、單任務的OS。優點：易于管理。缺點：對要求內存空間少的程序，造成內存浪費；程序全部裝入，很少使用的程序部分也占用內存。用戶程序操作系統0xFFF…F0x000…012把內存分為一些大小相等或不等的分區(partition)，每個進程占用一個或幾個分區。操作系統占用其中一個分區。特點：適用于多道程序系統和分時系統支持多個程序并發執行難以進行內存分區的共享。問題：可能存在內碎片和外碎片。內碎片：占用分區之內未被利用的空間外碎片：占用分區之間難以利用的空閑分區（通常是小空閑分區）。分區存儲管理13固定分區(fixedpartitioning)分區大小相等：只適合于多個相同程序的并發執行（處理多個類型相同的對象）。分區大小不等：多個小分區、適量的中等分區、少量的大分區。根據程序的大小，分配當前空閑的、適當大小的分區。把內存劃分為若干個固定大小的連續分區。14固定分區(大小相同)固定分區(多種大小)15動態分區(dynamicpartitioning)動態創建分區：在裝入程序時按其初始要求分配，或在其執行過程中通過系統調用進行分配或改變分區大小。優點：沒有內碎片。缺點：有外碎片。16動態分區(dynamicpartitioning)17分區分配算法尋找某個空閑分區，其大小需大于或等于程序的要求。若是大于要求，則將該分區分割成兩個分區，其中一個分區為要求的大小并標記為“占用”，而另一個分區為余下部分并標記為“空閑”。分區的先后次序通常是從內存低端到高端。18最先匹配法(first-fit)：按分區的先后次序，從頭查找，找到符合要求的第一個分區該算法的分配和釋放的時間性能較好，較大的空閑分區可以被保留在內存高端。但隨著低端分區不斷劃分而產生較多小分區，每次分配時查找時間開銷會增大。下次匹配法(next-fit)：按分區的先后次序，從上次分配的分區起查找（到最后分區時再回到開頭），找到符合要求的第一個分區該算法的分配和釋放的時間性能較好，使空閑分區分布得更均勻，但較大的空閑分區不易保留。最佳匹配法(best-fit)：找到其大小與要求相差最小的空閑分區從個別來看，外碎片較小，但從整體來看，會形成較多外碎片。較大的空閑分區可以被保留。最壞匹配法(worst-fit)：找到最大的空閑分區基本不留下小空閑分區，但較大的空閑分區不被保留。分區分配算法19頁式和段式存儲管理簡單頁式簡單段式段頁式頁式和段式存儲管理是通過引入進程的邏輯地址，把進程地址空間與實際存儲位置分離，從而增加存儲管理的靈活性。20簡單頁式(simplepaging)1.簡單頁式管理的基本原理將程序的邏輯地址空間和物理內存劃分為固定大小的頁或頁面(pageorpageframe)，程序加載時，分配其所需的所有頁，這些頁不必連續。需要CPU的硬件支持。2122優點：沒有外碎片，每個內碎片不超過頁大小。一個程序不必連續存放。便于改變程序占用空間的大小。即隨著程序運行而動態生成的數據增多，地址空間可相應增長。缺點：程序全部裝入內存。232.簡單頁式管理的數據結構進程頁表：每個進程有一個頁表，描述該進程占用的物理頁面及邏輯排列順序；邏輯頁號（本進程的地址空間）－>物理頁面號（實際內存空間）；物理頁面表：整個系統有一個物理頁面表，描述物理內存空間的分配使用狀況。數據結構：位示圖，空閑頁面鏈表；請求表：整個系統有一個請求表，描述系統內各個進程頁表的位置和大小，用于地址轉換，也可以結合到各進程的PCB里；243.簡單頁式管理的地址變換指令所給出地址分為兩部分：邏輯頁號，頁內偏移地址查進程頁表，得物理頁號－>物理地址為縮短查找時間，可以將頁表從內存裝入到快表(TLB,TranslationLookasideBuffer)，按內容查找(associativemapping)，即邏輯頁號－>物理頁號邏輯地址25頁式地址變換ProgramPagingMainMemoryLogicalAddressRegisterPageTablePageFrameOffsetP#Frame#PageTablePtrPage#OffsetFrame#Offset+26簡單段式(simplesegmentation)1.簡單段式管理的基本原理將程序的地址空間劃分為若干個段(segment)，程序加載時，分配其所需的所有段（內存分區），這些段不必連續；物理內存的管理采用動態分區。27程序通過分段(segmentation)劃分為多個模塊，如代碼段、數據段、共享段。可以分別編寫和編譯可以針對不同類型的段采取不同的保護可以按段為單位來進行共享，包括通過動態鏈接進行代碼共享優點：沒有內碎片，外碎片可以通過內存緊縮來消除。便于改變進程占用空間的大小。缺點：進程全部裝入內存。28B0SA0NY0LX0PM0K邏輯段號01234進程的地址空間10003200500060008000PKSLN主存K

3200P1500L6000N8000S5000長度

段地址01234操作系統292.簡單段式管理的數據結構進程段表：描述組成進程地址空間的各段，可以是指向系統段表中表項的索引。每段有段基址(baseaddress)和段長度系統段表：系統內所有占用段空閑段表：內存中所有空閑段，可以結合到系統段表中303.簡單段式管理的地址變換Base+dProgramSegmentationMainMemoryLogicalAddressRegisterSegmentTableSegmentdS#LengthBaseSegTablePtrSeg#Offset=dSegmentTable++31頁式管理和段式管理的比較分頁是出于系統管理的需要，分段是出于用戶應用的需要。一條指令或一個操作數可能會跨越兩個頁的分界處，而不會跨越兩個段的分界處。頁大小是系統固定的，而段大小則通常不固定。邏輯地址表示：分頁是一維的，各個模塊在鏈接時必須組織成同一個地址空間；分段是二維的，各個模塊在鏈接時可以每個段組織成一個地址空間。通常段比頁大，因而段表比頁表短，可以縮短查找時間，提高訪問速度。32虛擬存儲器(VIRTUALMEMORY)局部性原理虛擬存儲器的原理虛擬存儲技術的種類頁面調度策略置換算法33局部性原理局部性原理(principleoflocality)：指程序在執行過程中的一個較短時期，所執行的指令地址和指令的操作數地址，分別局限于一定區域。還可以表現為：時間局部性：一條指令的一次執行和下次執行，一個數據的一次訪問和下次訪問都集中在一個較短時期內；空間局部性：當前指令和鄰近的幾條指令，當前訪問的數據和鄰近的數據都集中在一個較小區域內。34虛擬存儲器的原理在程序裝入時，不必將其全部讀入到內存，而只需將當前需要執行的部分頁或段讀入到內存，就可讓程序開始執行。在程序執行過程中，如果需執行的指令或訪問的數據尚未在內存（稱為缺頁或缺段），則由處理器通知操作系統將相應的頁或段調入到內存，然后繼續執行程序。另一方面，操作系統將內存中暫時不使用的頁或段調出保存在外存上，從而騰出空間存放將要裝入的程序以及將要調入的頁或段。只需程序的一部分在內存就可執行。35引入虛擬存儲技術的好處大程序：可在較小的可用內存中執行較大的用戶程序；大的用戶空間：提供給用戶可用的虛擬內存空間通常大于物理內存(realmemory)并發：可在內存中容納更多程序并發執行；36虛擬存儲技術的種類虛擬頁式虛擬段式段頁式37虛擬頁式(virtualpaging)需要在進程頁表中添加若干項標志位：存在位（presentbit，內存頁和外存頁），修改位(modifiedbit)訪問統計：在近期內被訪問的次數，或最近一次訪問到現在的時間間隔外存地址在簡單頁式存儲管理的基礎上，增加請求調頁和頁面置換功能。對進程頁表的修改38虛擬頁式的進程頁表39虛擬段式(virtualsegmentation)需要在進程段表中添加若干項：標志位：存在位(presentbit)，修改位(modifiedbit/dirtybit)，增長位（該段是否增長過，在虛擬頁式中沒有該位）訪問統計：如使用位(usebit)存取權限：如讀R，寫W，執行X外存地址地址變換和缺段中斷：指令和操作數必定不會跨越在段邊界上在簡單段式存儲管理的基礎上，增加請求調段和段置換功能。40虛擬段式管理的段表41段頁式(combinedpagingandsegmentation)存儲管理的分配單位是：段，頁邏輯地址的組成：段號，頁號，頁內偏移地址。地址變換：先查段表，再查該段的頁表。缺段中斷和缺頁中斷。是虛擬頁式和虛擬段式存儲管理的結合。42虛擬段頁式管理中的段表和頁表43段頁式地址變換44頁面調度請求調頁(demandpaging)：只調入發生缺頁時所需的頁面。優點：容易實現。缺點：對外存I/O次數多，開銷較大預調頁(prepaging)：在發生缺頁需要調入某頁時，一次調入該頁以及相鄰的幾個頁。優點：提高調頁的I/O效率。缺點：基于預測，若調入的頁在以后很少被訪問，則效率低。常用于程序裝入時的調頁。1.調入策略(fetchpolicy)調入策略確定在外存中的頁面調入時機。在虛擬頁式管理中有兩種常用策略。452.分配策略(assignmentpolicy)在虛擬段式管理中，如何對物理內存進行分配，可采用最佳適應、最先適應等。在虛擬頁式和段頁式管理中，地址變換最后通過頁表進行，因此不必考慮分配策略。463.清除策略(cleaningpolicy)請求清除(demandcleaning)：該頁被置換時才調出，把清除推遲到最后一刻。缺點：調入所缺頁面之前還要調出已修改頁面，缺頁進程的等待時間較長，預清除(precleaning)：該頁被置換之前就調出，因而可以成批調出多個頁面。缺點：可能形成不必要的開銷。已修改頁面被調出之后仍停留在內存，如果這些頁面被置換之前就被再次修改，則這些頁面可以返還到進程的常駐集，而之前所做的調出操作就成為不必要的開銷。這種策略發展成為頁面緩沖算法(pagebuffering)。在虛擬頁式管理中，何時將已修改頁面調出到外存上。有兩種常用清除策略：474.置換算法(replacementpolicy)需要調入頁面時，選擇內存中哪個物理頁面被置換。目標：把未來不再使用的或短期內較少使用的頁面調出，通常只能在局部性原理指導下依據過去的統計數據進行預測；頁面鎖定(framelocking)：用于描述必須常駐內存的操作系統的關鍵部分或時間關鍵(time-critical)的應用進程。實現方法為在頁表中加上鎖定標志位(lockbit)。48最佳算法(OPT,optimal)最近最久未使用算法(LRU,LeastRecentlyUsed)先進先出算法(FIFO)輪轉算法(clock)最不常用算法(LFU,LeastFrequentlyUsed)頁面緩沖算法(pagebuffering)置換算法491.最佳算法(OPT,optimal)選擇“未來不再使用的”或“在離當前最遠位置上出現的”頁面被置換。這是一種理想情況，是實際執行中無法預知的，因而不能實現。可用作性能評價的依據。502.最近最久未使用算法

(LRU,LeastRecentlyUsed)一個特殊的棧：把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。每個頁面設立移位寄存器：被訪問時左邊最高位置1，定期右移并且最高位補0，于是寄存器數值最小的是最久未使用頁面。選擇內存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關系，硬件開銷太大。硬件機構如：513.先進先出算法(FIFO)選擇建立最早的頁面被置換。可以通過鏈表來表示各頁的建立時間先后。性能較差:較早調入的頁往往是經常被訪問的頁，這些頁在FIFO算法下被反復調入和調出。并且可能出現Belady現象。Belady現象：采用FIFO算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現分配的頁面數增多，缺頁率反而提高的異常現象。52Belady現象進程P有5頁,程序訪問頁的順序為：1,2,3,4,1,2,5,1,2,3,4,5；如果在內存中分配3