存儲器管理負責管理計算機系統(tǒng)中重要的資源---主存儲器。任何程序和數據必須載入到主存中才得以執(zhí)行和處理，因此存儲器管理的優(yōu)劣直接影響系統(tǒng)的性能。

　　主存分為兩部分：一部分是系統(tǒng)區(qū)，用于存放操作系統(tǒng)內核程序和數據結構等。另一部分是用戶區(qū)，用于存放應用程序和數據。

　　計算機系統(tǒng)采用層次結構的存儲系統(tǒng)。以便在容量大小、速度快慢、價格高低等諸多因素中取得平衡。它分為五個層次：寄存器，高速緩存，主存儲器，磁盤，磁帶等五層。寄存器，高速緩存和主存儲器屬于操作系統(tǒng)存儲管理管轄范疇。磁盤和磁帶屬于設備管理的管轄對象。

　　由于程序在執(zhí)行和處理數據時往往存在順序性和局部性，因此在執(zhí)行時并不需要將其全部調入主存，而僅調用當前使用的一部分，其他部分待需要時再逐步調入。基于這個原理操作系統(tǒng)可以向用戶提供比實際主存大得多的存儲空間，可以設計出多級層次式體系結構的存儲子系統(tǒng)。

　　源程序經過編譯，鏈接，裝入三個階段后才能裝入主存執(zhí)行。一個程序可由獨立編寫且具有不同功能的多個源程序模塊組成。由于模塊包含外部引用：指向其他模塊中的數據或函數的地址或包含對庫函數的引用。編譯程序負責記錄引用的發(fā)生位置，編譯或匯編的結果將產生相應的多個目標模塊，每個模塊都附有供引用使用的內部符號表和外部符號表。符號表中依次給出個符號名及在本目標模塊中的名字地址，在模塊被鏈接時進行轉換。

　　鏈接程序的作用是把多個目標模塊鏈接成一個完整的可重定位程序，這需要解析內部和外部符號表，把對符號的引用轉換為數值引用，將對符號引用的程序入口點和數據引用點轉換為數值地址。Linker首先將主程序調入工作區(qū)，然后掃描外部符號表，獲得外部符號。用取得的符號名從標準函數庫或其他庫中找出此符號對應的.o文件，裝入工作區(qū)并拼接到主程序之后作為程序的一部分。

　　磁盤中存儲的代碼模塊使用的是邏輯地址。邏輯地址空間可以是一維的，從0開始線形排列。也可以是二維的，此時整個程序被分為多個段，每段都有不同的段號，段內地址從0開始編址。

　　進程運行時，數據和代碼模塊被裝入物理地址空間，程序和數據的實際地址通常不可能同原來的邏輯地址一致。把邏輯地址轉換為物理地址的過程稱為地址重定位（與基址重定位相區(qū)別）。有兩種方式：

　　1：靜態(tài)地址重定位：由載入程序實現(xiàn)地址轉換，將所有的邏輯地址修改成主存物理地址。地址轉換工作在進程執(zhí)行前一次完成，無須硬件支持，易于實現(xiàn)，但是不允許程序在進程中移動位置。早期的計算機系統(tǒng)使用此方法。

　　2：動態(tài)地址重定位：加載程序將程序的數據和代碼加載到指定的主存區(qū)域后，并不對鏈接器處理過的應用程序的邏輯地址進行修改，但程序在主存的起始地址被置入硬件專用寄存器---重定位寄存器。程序執(zhí)行過程中，每當cpu訪問數據和代碼時，由硬件截取此邏輯地址，并在它被發(fā)送到主存儲器之前加上重定位寄存器的值以便實現(xiàn)地址轉換。這被稱為動態(tài)重定位，地址轉換被推遲到最后的可能時刻--執(zhí)行時才完成。這允許程序在主存中移動，便于程序共享且主存利用率高。

　　為了支持動態(tài)重定位cpu至少要有三個重定位寄存器。將代碼段、數據段和堆棧段分別作為三個可重定位的模塊。Intel x86有6個重定位寄存器。

　　要將動態(tài)地址重定位與根據重定位段進行的基址重定位區(qū)分開來。基址重定位是當exe或dll沒有加載到其首選基址時，所有涉及對邏輯地址引用的代碼都需要修改成相對于exe或dll實際載入的邏輯地址條件下的偏移地址。它是對邏輯地址進行操作。而當exe或dll被加載到首選基地址時，基址重定位不會發(fā)生。但是任何程序都會進行動態(tài)地址重定位，將邏輯地址轉換為物理地址。

　　在多道程序設計中，可用的主存通常被多個進程共享，必須允許進程所使用的內存因對換或空閑區(qū)收集而被移動，這需要動態(tài)地址重定位支持。無論采取何種重定位方式，通常進程運行時會對需要訪問所有主存地址進行檢查，確保進程僅訪問自己的存儲區(qū)。這就是地址越界保護，它依賴于硬件。除了地址越界保護之外，還要進行訪問權限檢查，如允許讀、寫、執(zhí)行等，從而保證數據的安全性和完整性，這就是信息存取保護。

　　固定分區(qū)存儲管理的基本思想：主存空間被劃分成數目固定不變的分區(qū)，各個分區(qū)大小不等，每個分區(qū)只裝入一個作業(yè)，若多個分區(qū)都裝有作業(yè)則它們可以并發(fā)執(zhí)行。缺點：預先規(guī)定分區(qū)大小使得大作業(yè)無法裝入。作業(yè)很少會恰好填滿分區(qū)，主存利用率不高。

　　可變分區(qū)管理又稱為動態(tài)分區(qū)管理，按照作業(yè)大小來劃分分區(qū)，但劃分的時間、大小、位置都是動態(tài)的。系統(tǒng)把作業(yè)裝入主存時，根據其所需要的主存容量查看是否有足夠的空間。若有，則按需分配一個分區(qū)給此作業(yè)；若無，則令此作業(yè)等待主存資源 。由于分區(qū)大小是按需求而定的，因此分區(qū)數目是可變的。這可以提高主存利用率。

　　用于管理的數據結構由兩張表組成：已分配分區(qū)表和未分配區(qū)表。當裝入新作業(yè)時，從未分配表中找出一個足夠容納它的空閑區(qū)。將此區(qū)分成兩部分，一部分用來裝入作業(yè)，另一部分仍是空閑區(qū)。然后在已分配的表中登記新作業(yè)的起始地址、占用長度，同時修改未分配區(qū)表中空閑區(qū)的長度和起始地址。當作業(yè)撤離時，已分配區(qū)表中的相應狀態(tài)變?yōu)榭眨鴮⑹栈氐姆謪^(qū)登記到未分配區(qū)表中，若有相鄰空閑區(qū)，將其合并后登記。

　　已分配分區(qū)表和未分配分區(qū)表采用鏈表是不錯的選擇。在內部各分區(qū)都可按一定的規(guī)則排列。如按空閑區(qū)大小、地址排列。

　　常用的可變分區(qū)分配算法有以下五種：

　　1：最先適應分配算法：順序查找未分配表找出一個滿足需要的。

　　2：下次適應分配算法：總是從未分配區(qū)的上次掃描結束處順序查找未分配區(qū)表。

　　3：最優(yōu)適應分配算法：掃描整個未分配區(qū)表，從中找出一個能滿足需要的最小分區(qū)進行分配。查找前分區(qū)一般按大小排列。

　　4：最壞適應分配算法：掃描整個未分配分區(qū)表，總是挑選一個最大的空閑區(qū)分割給作業(yè)使用。

　　5：快速適應分配算法：為那些經常使用的長度設立單獨的空閑區(qū)鏈表。

　對可變分區(qū)需采用動態(tài)地址重定位，進程的程序和數據的地址轉換由硬件完成，硬件設置兩個專用控制寄存器：基址寄存器和限長寄存器。基址寄存器存放分配給進程使用的分區(qū)的起始地址，限長寄存器存放進程所占用的連續(xù)存儲空間的長度。當進程占有cpu運行后，操作系統(tǒng)可把分區(qū)的起始地址和長度送入基址寄存器和限長寄存器，在執(zhí)行指令或訪問數據時，由硬件根據基址寄存器進行地址轉換得到絕對地址。

　　當邏輯地址小于限長值時，邏輯地址加上基址寄存器的值就可以獲得絕對地址。當邏輯地址大于限長值時表示進程所訪問的地址超過所分得的區(qū)域，此時不允許訪問。

　　C語言的程序會被編譯成至少三個段：代碼段，數據段，堆棧段。Intel x86平臺提供專用的存放段基址的寄存器：代碼段寄存器CS在指令執(zhí)行期間重定位指令地址；堆棧段寄存器SS為棧指令執(zhí)行重定位地址；數據段寄存器DS在指令執(zhí)行周期內重定位其他地址。提供多對基址、限長寄存器的機器中，允許一個進程占用兩個或多個分區(qū)。可規(guī)定某對基址、限長寄存器的區(qū)域是共享的，用來存放共享的程序和數據。

　　可變分區(qū)中常常出現(xiàn)分散的小空閑區(qū)，稱之為碎片。當在分區(qū)表中找不到足夠大的空閑區(qū)來裝入進程時，可采用移動技術把已在主存中的進程分區(qū)連接到一起，使分散的空閑區(qū)匯集成片。這就是移動技術。第一種方法是把所有當前占用的分區(qū)移動到主存一端。第二種是也是把占用分區(qū)移動到另一端，但是當產生足夠大的空閑區(qū)就停止移動。

　　分區(qū)方式管理存儲器，每道程序要求占用主存的一個或多個連續(xù)存儲區(qū)域，這樣不僅導致主存中產生碎片，而且處理器的開銷太大。分頁存儲管理允許程序存放到若干不相鄰的空閑塊中，既可以免除移動信息工作也可充分利用主存空間。

　　進程邏輯地址空間分成大小相等的區(qū)，每個分區(qū)成為頁面或頁，頁號從0開始依次編號。 把主存物理地址空間分成大小相等的區(qū)，每個區(qū)是一個物理塊或頁框。頁框大小與頁面大小相等。

　　與此對應分頁存儲器的邏輯地址由兩部分組成：頁號和頁內位移。邏輯地址是連續(xù)的，用戶在編制程序時仍使用相對地址，不必考慮如何分頁，由硬件地址轉換機構和操作系統(tǒng)的管理需要來決定頁面尺寸，從而確定主存的分塊大小。進程在主存中的每個頁框內的地址是連續(xù)的，但頁框之間的地址可以不連續(xù)。

　　頁表用于是操作系統(tǒng)為進程建立的，是程序頁面和主存對應頁框的對照表。頁表中的每一欄指明程序中的一個頁面和分得頁框之間的對應關系。從數學角度來看，頁表表示一個函數，其變量是頁面號，函數值為頁框號，通過頁表可以把邏輯地址中的邏輯頁面替換成物理頁框。進程頁表存放在內存中，系統(tǒng)設置了專門的硬件：頁表基址寄存器（一對，地址和長度），存放當前運行進程頁表的起始地址 ，以加快地址轉換速度。

　　進程運行前由系統(tǒng)把它的頁表基地址送入頁表基址寄存器，運行時借助于硬件的地址轉換，按頁面動態(tài)地址重定位。當cpu獲得邏輯地址后，由硬件按設定的頁面尺寸分成兩部分：頁號和頁內位移。先從頁表基地址寄存器找到頁表基地址，再用頁號作為索引查找頁表，得到對應的頁框號。根據

　　物理地址=頁框號*塊長+頁內位移。

　　計算出欲訪問的主存單元。雖然進程存放在若干不連續(xù)的頁框中，

　　但在執(zhí)行過程中總能按正確的物理地址進行存取。

　　按照給定邏輯地址進行讀寫操作時，至少訪問兩次主存：一次訪問頁面，另一個根據物理地址訪問指令或數據。為了提高運算速度，設置了專門的硬件，用來存放進程最近訪問的部分頁表項，被稱為轉換后援緩沖或快表。對快表的訪問速度遠快于主存，但造價高，且只能存儲幾十個頁表項。塊表項包含頁號及對應的頁框號，它通過并行匹配對所有快表項進行查找。如果找不到，再查主存中的頁表，同時將頁號即頁框號登記到快表中。當塊表快滿時，需要淘汰舊的塊表項，最簡單的策略是先進先出。

　　通過快表實現(xiàn)主存訪問的比率成為命中率。快表與高速緩存不同，前者記錄最近轉換的頁號即頁框號，后者保存最近實際訪問的指令或數據的副本。

　　分頁存儲管理能實現(xiàn)多個進程共享程序和數據，共享頁面信息可大大提高主存空間的利用率。實現(xiàn)頁面共享必須區(qū)分數據共享和程序共享。實現(xiàn)數據共享時，允許不同進程對共享的數據頁面用不同的頁號，只要讓各自頁表中的有關表項指向共享的數據頁框。實現(xiàn)程序共享時，由于指令包含指向其他指令或數據的地址，進程依賴于這些地址才能執(zhí)行，所以，不同進程正確執(zhí)行共享代碼頁面，必須為它們在所有邏輯地址空間中指定同樣的頁號。實現(xiàn)信息共享必須解決共享信息的保護問題，通常的做法是在頁表中增加標志位，指出此頁的訪問模式。進程訪問時核對訪問模式，當模式不符時拋出異常。

　　分頁存儲管理是實存管理，必須為進程分配足夠的主存空間，裝入其全部信息，否則進程無法運行。把進程的全部信息裝入主存后，實際上并非同時使用，有些部分甚至從不使用，這是對主存資源的一種浪費。于是提出一種想法：不必裝入進程的全部信息，僅將當前使用部分先裝入主存，其余部分存放在磁盤中，待使用時由系統(tǒng)自動將其裝進來，這就是虛擬存儲管理技術的基本思路。

　　當進程被創(chuàng)建時，代碼段和數據段部分數據被調入內存。如果處理器訪問的程序或數據不在內存，系統(tǒng)自動將這部分信息從磁盤裝入，這叫做部分裝入。若此時內存沒有足夠的空閑空間，便把主存中暫時不用的信息移至磁盤，這叫做部分替換。在具有層次存儲結構的計算機系統(tǒng)中，自動實現(xiàn)部分裝入和部分替換功能，能從邏輯上為用戶提供一個比實際物理存儲器大得多的、可尋址的“主存儲器”，這被稱為虛擬存儲器。它對用戶隱蔽內部細節(jié)。虛擬地址空間等同于實際物理主存加部分硬盤區(qū)域的存儲空間。引用基礎是：程序執(zhí)行的局部性原理：某存儲單元被使用后，其相鄰的存儲單元也很快被使用---空間局部性。最近訪問過的程序代碼和數據很快被訪問---時間局部性。

　　虛擬存儲器是基于程序局部性原理的一種假想的而非物理存在的存儲器，其主要任務是：基于程序局部性特點，當進程使用某部分地址空間時，保證將相應部分加載至主存中。這種將物理空間和邏輯空間分開編制、互相隔離，但又統(tǒng)一管理和使用的計數為用戶編程提供了極大地方便。

虛擬存儲管理與對換有很大區(qū)別。兌換技術以進程為單位，當所需的主存空間大于當前系統(tǒng)的擁有量時，進程無法對換進主存工作。而虛擬存儲管理以頁或段為單位，即使進程所需主存空間大于當前系統(tǒng)擁有的主存總量，仍然能夠正常運行。

　　操作系統(tǒng)的存儲管理依靠底層硬件MMU（主存管理部件）來完成，它提供地址轉換和存儲保護的功能。

　　每當進程上下文發(fā)生切換時，系統(tǒng)負責把要運行的進程的頁表基地址裝入頁表寄存器，此頁表便成為活動頁表。MMU只對頁表基址寄存器所指出的活動頁表進行操作。然后將邏輯地址分解為頁面號和頁內位移，以便進行地址轉換。對快表的管理設計兩個方面：一是直接查找快表，找到相應的頁框后去拼接物理地址。二是裝入表目和清除表目，每次發(fā)生快表查找不命中的情況后，待缺頁中斷處理結束，把相應的頁面和頁框號裝入。

　　請求分頁虛擬存儲管理是將進程信息的副本存放在輔助存儲器中，當它被調度投入運行時，并不把程序和數據全部裝入主存，僅裝入當前使用的頁面，訪問到不在主存的頁面時再動態(tài)的把所需的信息裝入。請求分頁：當需要執(zhí)行某條指令或使用某個數據而發(fā)現(xiàn)它們不在主存時，產生缺頁中斷，系統(tǒng)從磁盤把此指令或數據所在的頁面裝入。

　　請求分頁虛擬存儲管理屬于虛擬存儲，與分頁實存管理不同，僅讓當前使用部分裝入，必然會發(fā)生某些頁面不在主存的情況，為了標記頁面是否在主存中，所采用的方法為：擴充頁表項的內容，增加駐留標志位，又稱頁失效異常位，用來指處頁面是否裝入主存。當訪問一個頁面時，如果某頁的駐留標識為1，表示此頁已經在主存中，可被正常訪問。如果某頁的駐留標識為0，不能立即訪問，產生缺頁中斷，操作系統(tǒng)根據磁盤地址將這個頁面調入主存，然后重新啟動相應指令。

　　頁面裝入策略決定何時把頁面裝入主存，有兩種策略：

　　1：請頁式，僅當需要訪問程序和數據時，通過缺頁中斷并由缺頁中斷處理程序分配頁框，把所需頁面裝入主存。

　　2：預調式，裝入主存的頁面并非缺頁中斷請求的頁面，是由操作系統(tǒng)依據某種算法，動態(tài)預測進程最可能要訪問的那些頁面。

　　頁面清除策略與裝入策略相對應，要考慮何時把修改過的頁面寫回輔助存儲器，常用的算法是：

　　1：請頁式清除，僅當一頁被選中進行替換且被修改過，才把它寫回磁盤。

　　2：預約式清除，對于所有更改過的頁面，在需要替換之前把它們都寫回磁盤。

　　在多道程序設計中，屬于不同進程的頁面被分散存放在主存頁框中，當發(fā)生缺頁中斷時，如果已無空閑頁框，系統(tǒng)要選擇一個駐留頁面進行淘汰。

　　頁面替換有兩種策略：

　　1：局部替換，頁面替換算法局限于進程自身。

　　2：全局替換，頁面替換算法的作用范圍是整個系統(tǒng)。

　　全局替換算法有以下幾種算法：

　　1：最佳頁面替換算法（optimal replacement ，OPT）：當要調入一頁而必須淘汰舊頁時，應該淘汰以后不再訪問的頁，或距現(xiàn)在最長時間后要訪問的頁。它所產生的缺頁數最少。這只是一種理想的情況。

　　2：先進先出頁面替換算法（FIFO）

　　基于程序總是按線形順序來訪問物理空間這一假設，總是淘汰最先調入主存的頁面，即淘汰在主存中駐留時間最長的頁面。

　　3：最近最少使用頁面替換算法（Least Recently Used ，LRU）

　　淘汰的頁面是在最近一段時間內最久未被訪問的那一頁。

　　4：第二次機會頁面替換（Second Chance Replacement ，SCR）

　　此算法是將FIFO算法與頁表中的引用位結合起來使用，實現(xiàn)思想：首先檢查FIFO頁面隊列中的隊首，這是最早進入主存的頁面，如果其引用位是0，那么這個頁面不僅入隊時間長，而且沒有使用。如果引用位為1，說明它進入主存的時間較早，但最近仍在使用，于是將其引用位歸0，置于隊尾，把它看成新調入的頁，再給一次機會。

　　5：時鐘頁面替換算法（Clock policy replacement）

相關鏈接：

內功修煉之操作系統(tǒng)學習（處理器管理）

內功修煉之操作系統(tǒng)學習（同步、通信及死鎖）