上篇部落格介紹了處理機排程的相關知識——我的作業系統複習——處理機排程，本篇開始講跟處理機打交道最多的計算機部件——存儲器。存儲器包括常說的記憶體和外存。存儲器管理，一般指的是記憶體管理。外存也屬于存儲器，不過應該算作檔案管理。
一、存儲器層次分類
存儲器按存儲層次分可以分為三類，分别是寄存器、主存、輔存。寄存器位于CPU内，主存又稱記憶體，輔存即硬碟。仔細劃分的話，主存還可以分為高速緩存、主存、磁盤緩存。如下圖所示，層次越往上，存儲媒體通路速度越快，價格越貴、相對存儲容量也越貴。寄存器和主存這裡大概說一說，輔存（外存）就留到檔案系統的時候再說。
（1）寄存器
寄存器位于CPU内，是CPU的組成部分。它是計算機系統内CPU通路速度最快的存儲部件，完全能與CPU協調工作。不過價格太貴，隻能做得很小。寄存器是用來存放系統最常通路的資料，如，指令寄存器用來存放從記憶體讀到的正在執行的指令，程式計數器存放下一條指令所在單元的位址。其本質就是用來存放供CPU最頻繁通路的一批資料。寄存器就是為了解決CPU通路主存速度過慢的問題。通常，CPU從主存讀取資料，放入寄存器内，以便頻繁通路。
（2）主存
主存即記憶體。CPU可以通過指令直接存取主存中的資料，是以CPU對主存的通路速度也很快，不過這個速度也遠低于CPU的執行速度。為了解決這個問題，引入了寄存器和高速緩存。高速緩存是什麼？高速緩存也是屬于記憶體，不過它與通常的主存的實作形式不同，它一般是由靜态存儲晶片(SRAM)組成，通路速度比主存高得多， 接近于CPU的速度。而主存通常使用動态MOS随機讀寫存儲器DRAM組成，速度比SRAM快得多。高速緩存的作用就是存放主存中一些經常被通路的資訊。磁盤緩存的本質就是主存劃分的一個小區域，為了減少CPU透過I/O讀取磁盤機的次數，提升磁盤I/O的效率，用一塊區域來儲存存取較頻繁的磁盤内容。
二、程式的裝入和連結
程式裝入就是把程式和資料放入記憶體。程式也不是一開始就有的。這裡指的程式是最終在記憶體中運作的子產品——裝入子產品。那麼一份源代碼是怎麼變成可運作的程式的呢？學過C、C++的同學對這個最了解。首先是把源代碼用編譯程式編譯成目标子產品，每一份源代碼檔案對應一個目标子產品。然後用連結程式将目标子產品和程式所需要的庫函數連結起來，變成一個可運作的程式。這個可運作的程式，實質是編譯連結後的機器指令，CPU可以運作這些機器指令。程式運作時，裝入子產品将其放入記憶體并運作。其中，将這些機器指令何其指向的資源裝入記憶體有3種方式：
（1）裝入：
1）絕對裝入方式（Absolute Loading Mode）
程式中使用的位址是直接指向記憶體的絕對位址，那麼在把程式裝入記憶體的時候，不需要對程式位址做任何修改，這種裝入方式就叫做絕對裝入方式。絕對裝入方式隻能将程式裝入到記憶體中指定的位置，它隻适合單道處理環境，這樣就不會有記憶體沖突了。
2）可重定位裝入方式（Relocation Loading Mode）
可重定位裝入方式指的是，将程式裝入記憶體的時候，将程式位址都相對于記憶體目前位址偏移。這時程式中的位址都是相對位址。值得注意的是，裝入時對程式中指令和資料位址的修改過程叫做重定位。
3）動态運作時裝入方式（Dynamic Run-time Loading）
如果程式在運作時位置需要改變，應該采用動态運作時裝入方式。動态運作時裝入方式指的是程式中的相對位址并不在裝入時就轉換成記憶體中的絕對位址，而是等到真正運作的時候才會轉換。
（2）連結：
與程式裝入相對應的是程式的連結方式。程式的連結方式也有3種方式，分别是靜态連結方式、裝入時動态連結和運作時動态連結。分别對應的是程式連結時的3個時間。其中靜态連結是程式的目标子產品在裝入之前就連結好，而裝入時動态連結，顧名思義，就是目标子產品實在裝入記憶體的時候動态的進行連結，這種方式連結的程式的目标子產品是分開存放的，若一個目标子產品需要連結給其他多個子產品是非常友善的。而在靜态連結方式中要實作這個功能，需要其他多個子產品都含有該子產品的拷貝。
三、記憶體配置設定方式——連續配置設定方式
将記憶體配置設定給程式，最典型的方式就是将一個連續的記憶體空間配置設定給程式，這就是連續配置設定方式。這種配置設定方式細分可以分為單一連續配置設定、固定分區配置設定、動态分區配置設定和動态重定位分區配置設定。需要了解的是，前面的程式裝入記憶體的過程就是典型的記憶體配置設定。就是說，記憶體的配置設定通常可能是動态，在程式運作過程中，通常伴随着動态的記憶體建立和記憶體回收，其中還涉及到很多緩存、優化之類的政策。在各種記憶體配置設定和回收的過程中，會産生很多空餘碎片。記憶體配置設定就是要盡可能利用記憶體空間，避免記憶體浪費。
（1）單一連續配置設定
這種配置設定方式就是簡單的把記憶體分為系統區和使用者區，系統區給作業系統用，使用者區給使用者用。這種配置設定方式非常簡單，并未考慮多使用者記憶體沖突和多任務記憶體沖突的情況，是以隻适用于單使用者、單任務的OS。值得注意的是，系統區通常是配置設定在記憶體的低址部分。
（2）固定分區配置設定
這種配置設定方式就是将記憶體劃分為若幹固定大小的區域，區域的大小是事先劃分好的，每個區域裝入一道作業、程式，這樣多任務記憶體沖突的問題就解決了。這種劃分方法适用于多道批處理系統——多任務并發的情況。但是，由于每個分區大小固定，存儲空間的浪費是必然的。
（3）動态分區配置設定
這種配置設定方式就是根據程序的實際需要，動态的配置設定記憶體空間。這種配置設定方式有3個問題需要注意。1、需要有一種資料結構來描述空閑分區和已配置設定分區的情況。2、需要按照一定的配置設定算法從空閑分區中選擇空間來配置設定。3、需要有合适的分區配置設定和記憶體回收操作：
1）描述空閑分區的資料結構：
有2種資料結構可以描述空閑分區的資料結構，分别是空閑分區表和空閑分區鍊。其中，分區表很容易了解，分區鍊指的是通過在空閑分區的首尾設定2個指向其他空閑分區的指針，形成一個空閑分區的鍊，用來記錄空閑的分區。
2）分區配置設定算法：
-
- 首次适應算法（first fit）：分區鍊以位址遞增的次序連結；配置設定記憶體時，從鍊首開始，查找到一個大小能滿足要求的空閑分區就停止。這個算法說白了就先配置設定記憶體的低址部分，再配置設定高址部分。
- 循環首次适應算法（next fit）：這個配置設定算法與首次适應算法的差別在于，它配置設定記憶體時，不是從鍊首開始查找，而是從上次找到的空閑分區的下一個分區開始查找。
- 最佳适應算法（best fit）: 分區鍊以從小到大的順序連結；配置設定記憶體時，從鍊首開始，查找到一個能滿足要求的空閑分區就停止。
- 最壞适應算法（worst fit）: 分區鍊以從大到小的順序連接配接；與最佳适應算法相反，每次都挑最大的空閑區來配置設定。
- 快速适應算法（quick fit）: 将空閑區根據大小進行分類，每一種類别單獨設立一個連結清單。同時，用一個管理索引表來管理這些連結清單。那麼配置設定記憶體的時候隻需要查詢管理索引表就行了，無需周遊連結清單，速度非常快。缺點是，這個算法需要一直維護着連結清單和管理索引表，需要一定系統開銷。
3）記憶體配置設定和回收：
在配置設定空閑分區的時候，值得注意的是，通常空閑分區會有一個“不可再分割的剩餘分區大小”的屬性，規定了，當空閑分區所剩屬性小于它的時候，分區不允許再繼續分割，分區也将從空閑分分區連結清單中移除。
記憶體回收的時候，值得注意的是，若回收的記憶體區與某個空閑分區相鄰接，那麼需要将它們合并。否則，需要為回收區建立新的空閑分區。
4）夥伴系統：
我們知道1G的記憶體有220個位元組，有224個字。那麼根據指數，最多分為24個空閑分區連結清單。假設一個應用程式申請2MB的記憶體，2MB即215個字的大小，這時候查找大小為215的空閑分區連結清單，若找不到，那麼查找大小為216的空閑分區連結清單，若216的空閑分區連結清單存在，那麼把它分成2個，一個配置設定給請求，另一個配置設定為215的空閑分區連結清單，若若216的空閑分區連結清單不存在，那麼繼續往後查找，以此類推。
（4）可重定位分區配置設定
由于程式、資源間會有很多碎片，浪費了記憶體空間，可重定位分區配置設定就是為了解決這個問題，它可以直接移動記憶體中的程式、資源，使記憶體變得緊湊，同時也不影響程式的正常運作。可重定位分區配置設定要求程式的裝入方式是動态運作時裝入方式。程式裝入記憶體後，所有位址仍舊是相對位址，直到運作時才會轉變為絕對位址。程式在寄存器中有一個重定位寄存器，用來存放程式在硬碟中的實際位址的首位址。那麼将程式在記憶體中的絕對位址移動，隻需要移動後，改變重定位寄存器的值即可。這我們經常用的“磁盤碎片清理”就是一樣的效果。
（5）對換
對換是一個需要了解一下的概念。還記得前面我們講程序排程的時候，有一個特殊的排程類型，叫做中級排程。中級排程就是讓暫時不能運作的程序挂起，釋放記憶體資源，并把它們調到外存上去等待，這種操作，在記憶體看來，就叫對換。以程序為機關的對換叫程序對換。對換的情況下，外存中必須配置設定一定的區域用來存放對換的記憶體資源，叫做對換區。這個對換區本質是虛拟存儲器，這個後面會講。
四、記憶體配置設定方式——離散配置設定方式
連續的配置設定方式會産生很多碎片。離散的配置設定方式是将程序、資源裝入不相鄰的多個分區的記憶體配置設定方式。這種配置設定方式按照配置設定的機關是“頁”還是“段”，分為分頁存儲管理、分段存儲管理以及段頁式存儲管理。
（1）分頁存儲管理
分頁存儲管理是根據程式作業中的“頁”為機關離散配置設定記憶體的管理。
1）頁面（頁）。
分頁存儲管理的記憶體配置設定機關是頁。什麼是頁？頁就是一段指定大小的記憶體塊。分頁存儲管理就是按照一定大小把程序的邏輯位址空間分成若幹份，每一份就是一個頁，把他們編号。然後按照頁的大小把記憶體分為若幹實體塊，并編号。頁的大小通常是512B到8KB之間。
2）頁表。
每一個程序都有一張頁表，用來記錄程序的頁号對應的實體塊号。程序運作時，CPU會根據程式的邏輯位址和頁号大小從頁表找到實際的實體塊和實際的實體位址。頁表是經常被CPU通路的，CPU經常需要先通路頁表再根據頁表的位址通路記憶體，是以一般會設定一個“聯想寄存器”，又稱“塊表”，存放最近頻繁通路的頁表。如果系統的記憶體特别大，頁表中頁面的邏輯位址就會特别大，就需要用多層的頁表結構來對應實體塊号。這種情況下，CPU會根據程式的邏輯位址和頁面大小從多層的外部頁表找到指定的頁表，再從頁表中找到實際的實體塊和實體位址。
（2）分段存儲管理
分段存儲管理是根據程式作業中的“段”為機關離散配置設定記憶體的管理。
1）段。
段指的是程式、作業中的一組邏輯資訊。例如：全局變量可以設為一個段；每個函數的局部變量可以設為一個段；每個函數的代碼部分可以設定為一個段。這樣做有什麼意義呢？相當于将程式中的這種邏輯資訊根據大小離散的存儲在記憶體中，而對于邏輯資訊本身而言，他們在記憶體中是連續的，不會被分割的，這樣有利于對邏輯資訊的處理，如資訊共享、資訊保護等。
2）段表。
與頁表類似的，每個程序都有一張段表，用來記錄程式中每個段對應的實體位置。段表中每個記錄都記錄了段的實體位址和段的長度。同樣，由于段表經常需要被通路，有些系統會把段表放在寄存器中。
（PS：值得注意的是，運作時動态連結要求記憶體使用分段存儲管理。）
（3）段頁式存儲管理
段頁式存儲管理是根據“段”為機關，再将“段”細分為“頁”，以這個為機關離散配置設定記憶體的管理。原理與分頁、分段存儲管理類似。
五、虛拟存儲器管理
對于記憶體的連續配置設定方式，上文有一個“對換”的概念，就是将暫時不用的記憶體資源從記憶體中移出，放到外存的對換區中。當需要該記憶體資源的時候，需要及時能夠把該記憶體資源從外存中移入記憶體。這裡的對換區其實就是虛拟存儲器。講到虛拟存儲器有需要了解一下程式執行的局部性原理，總結下來就是：
- 程式的執行過程中，大部分的指令是執行一次或很少執行的，CPU主要是在執行一小部分指令。
- 程式的執行過程中，大部分資源是很少被通路的。
是以，程式一次性裝入記憶體，而實際上大部分記憶體資源是被浪費的。基于這種情況，沒必要把所有資源都一次性裝入記憶體。僅需要将程式目前需要的運作的段（頁）裝入記憶體即可。如果程式運作時通路到記憶體中不存在的段（頁），這種現象叫“缺段”（卻頁），這時候需要根據一定算法從外存的虛拟存儲區将缺失的資源立即裝入記憶體。
這裡有一個補充知識，見http://zhidao.baidu.com/question/86215203.html：
至于頁表的問題是這樣的，在系統初始化時，是直接對實體記憶體進行通路的，不經過頁表，這是的工作模式叫實模式，等頁表在記憶體中建立好了，再切換的保護模式，在保護模式就出現了虛拟位址向實體位址轉譯的過程了。
CPU有兩種工作模式，一個是實模式，就是直接通路實體記憶體，不分頁的。另一個是保護模式，就是分頁的，而且存在虛拟位址。保護模式下又有特權模式和使用者模式兩種。關系是這樣子的。
我給你講，隻要發生缺頁中斷，就會陷入核心，隻是就進入了特權模式，控制權交給了作業系統，這一系列過程都是硬體完成的。至于換頁使軟體完成的，就是作業系統負責調頁。MMU隻是負責把虛拟位址轉譯成實體位址，他隻能做這個，純硬體實作的。作業系統有調頁算法，就是在空閑的頁找出來一個，把需要的内容從磁盤讀出來，放到記憶體裡，然後讓程序重新運作那條指令。一切繼續，就像沒有缺頁過一樣。如果沒有空閑的，就把最不經常使用的一頁替換掉。
參考：《計算機作業系統(湯子瀛)》
/**
* ————————如果覺得本博文還行，别忘了推薦一下哦，謝謝！
* 作者：錢書康
* 歡迎轉載，請保留此段聲明。
* 出處：http://www.cnblogs.com/zrtqsk/
*/