計算機操作系統(tǒng)之存儲器管理（要點梳理~）
存儲器的層次結構
多層結構的存儲器系統(tǒng)
1.存儲器的多層結構。
存儲層次至少應具有三級：最高層為 CPU 寄存器，中間為主存，最底層是輔存。還可以根據(jù)具體的功能分工細劃為寄存器、高速緩存、主存儲器、磁盤緩存、固定磁盤、可移動存儲介質等 6 層。在存儲層次中越往上，存儲介質的訪問速度越快，價格也越高，相對存儲容量也越小。
寄存器、高速緩存、主存儲器和磁盤緩存均屬于操作系統(tǒng)存儲管理的管轄范疇，掉電后它們存儲的信息不再存在。固定磁盤和可移動存儲介質屬于設備管理的管轄范疇，它們存儲的信息將被長期保存。
2.可執(zhí)行存儲器。
寄存器和主存儲器又被稱為可執(zhí)行存儲器。
主存儲器與寄存器
1.主存儲器
主存儲器簡稱內(nèi)存或主存。由于主存儲器的訪問速度遠低于 CPU 執(zhí)行指令的速度，為緩和這一矛盾，在計算機系統(tǒng)中引入了寄存器和高速緩存。
2.寄存器
寄存器具有與處理機相同的速度。主要用于存放處理機運行時的數(shù)據(jù)。如用寄存器存放操作數(shù)，或用作地址寄存器加快地址轉換速度等。
高速緩存和磁盤緩存
1.高速緩存
高速緩存是介于寄存器和存儲器之間的存儲器，主要用于備份主存中較常用的數(shù)據(jù)。其容量遠大于寄存器，而比內(nèi)存約小兩到三個數(shù)量級左右。
根據(jù)程序執(zhí)行的局部性原理(即程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分)，將主存中一些經(jīng)常訪問的信息存放在高速緩存中。當 CPU 訪問一組特定信息時，首先檢查它是否在高速緩存中，在則直接取出使用，否則再從主存中讀取。
2.磁盤緩存
由于目前磁盤的 I/O 速度遠低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。但磁盤緩存與高速緩存不同，它本身并不是一種實際存在的存儲介質，而是利用主存中的部分存儲空間暫存從磁盤中讀出(或寫入)的信息。
【文章福利】小編推薦自己的Linux內(nèi)核技術交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ? ? ??
程序的裝入和鏈接
用戶程序要在系統(tǒng)中運行，必須先將它裝入內(nèi)存，然后再將其轉變?yōu)橐粋€可以執(zhí)行的程序，通常都要經(jīng)過以下幾個步驟：
編譯，由編譯程序將用戶源代碼編譯成若干個目標模塊。
鏈接，由鏈接程序將編譯后形成的一組目標模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊。
裝入，由裝入程序將裝入模塊裝入內(nèi)存。
程序的裝入
1.絕對裝入方式
僅能運行單道程序時可以采用該種方式。裝入模塊被裝入內(nèi)存后，程序中的邏輯地址與實際內(nèi)存地址完全相同。
2.可重定位裝入方式
采用可重定位裝入方式，根據(jù)內(nèi)存的當前情況，將裝入模塊裝入到內(nèi)存的適當位置。值得注意的是，在采用可重定位裝入程序將裝入模塊裝入內(nèi)存后，會使裝入模塊中的所有邏輯地址與實際裝入內(nèi)存的物理地址不同。通常是把在裝入時對目標程序中指令和數(shù)據(jù)地址的修改過程稱為重定位。又因為地址變換通常是在裝入時一次完成的，以后不再改變，故稱為靜態(tài)重定位。
3.動態(tài)運行時裝入方式
動態(tài)運行時的裝入程序在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行時才進行。因此，裝入內(nèi)存后的所有地址都仍是相對地址。為使地址轉換不影響指令的執(zhí)行速度，這種方式需要一個重定位寄存器的支持。
程序的鏈接
1.靜態(tài)鏈接方式
在程序運行之前，先將各目標模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝配模塊，以后不再拆開。在將這幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個問題：
1）對相對地址進行修改。這是因為在由編譯程序所產(chǎn)生的所有目標模塊中，使用的都是相對地址，其起始地址都為 0，每個模塊中的地址都是相對于起始地址計算的。
2）變換外部調用符號。將每個模塊中所用的外部調用符號也都變換為相對地址。
這種先進行鏈接所形成的一個完整的裝入模塊，又稱為可執(zhí)行文件。
2.裝入時動態(tài)鏈接
指用戶源程序經(jīng)編譯后所得的目標模塊，在裝入內(nèi)存時采用邊裝入邊鏈接的鏈接方式。這樣便于裝入前修改和更新，以及實現(xiàn)對目標模塊的共享。
3.運行時動態(tài)鏈接
將對某些模塊的鏈接推遲到程序執(zhí)行時才進行鏈接，亦即，在執(zhí)行過程中，當發(fā)現(xiàn)一個被調用模塊尚未裝入內(nèi)存時，立即由 OS 去找到該模塊并將之裝入內(nèi)存，把它鏈接到調用者模塊上。凡在執(zhí)行過程中未被用到的目標模塊，都不會被調入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。
連續(xù)分配存儲管理方式
為了能將用戶程序裝入內(nèi)存，必須為它分配一定大小的內(nèi)存空間。
1.單一連續(xù)分配
只能用于單道程序環(huán)境下，整個內(nèi)存的用戶空間由一個程序獨占。
2.固定分區(qū)分配
將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)。
3.劃分分區(qū)的方法
分區(qū)大小相等、分區(qū)大小不等。
4.內(nèi)存分配
通常將分區(qū)按大小進行排隊，并為之建立一張分區(qū)使用表，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)(是否已分配)。當有一用戶程序要裝入時，由內(nèi)存分配程序檢索該表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項中的狀態(tài)置為“已分配”。
動態(tài)分區(qū)分配
又稱可變分區(qū)分配。
動態(tài)分區(qū)分配中的數(shù)據(jù)結構。
常用的數(shù)據(jù)結構有以下兩種形式：
空閑分區(qū)表，表目：分區(qū)號、分區(qū)大小、分區(qū)始址、狀態(tài)。
空閑分區(qū)鏈，在每個分區(qū)的起始部分設置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針；在分區(qū)尾部則設置一后向指針，以及前后都重復設置狀態(tài)位和分區(qū)大小表目。通過前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個雙向鏈。
動態(tài)分區(qū)分配算法。
順序式搜索算法、索引式搜索算法。
分區(qū)分配操作。
1）分配內(nèi)存：
系統(tǒng)應利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設請求的分區(qū)大小為 u.size，表中每個空閑分區(qū)的大小可表示為 m.size。若 m.size-u.size≤size(size 是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說明多余部分太小，可不再切割，將整個分區(qū)分配給請求者；否則(即多余部分超過 size)，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)鏈(表)中。然后，將分配區(qū)的首址返回給調用者。
2）回收內(nèi)存：
當進程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應的插入點，此時可能出現(xiàn)以下四種情況之一：
①回收區(qū)與插入點的前一個空閑分區(qū)相鄰接，此時應將回收區(qū)與插入點的前一分區(qū)合并。
②回收分區(qū)與插入點的后一空閑分區(qū)相鄰接，此時也可將兩分區(qū)合并。
③回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接，此時將三個分區(qū)合并。
④回收區(qū)既不與前一個鄰接，又不與后一個鄰接，這時應為回收區(qū)單獨建立一新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當位置。
基于順序搜索的動態(tài)分區(qū)分配算法
順序搜索，是指依次搜索空閑分區(qū)鏈上的空閑分區(qū)，去尋找一個其大小能滿足要求的分區(qū)。
碎片：內(nèi)存空間不斷被劃分，會留下許多難以利用的、很小的空閑分區(qū)。
首次適應算法。
要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時，從鏈首開始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止，缺點是低址部分會不斷被劃分，形成碎片。
循環(huán)首次適應算法。
在為進程分配內(nèi)存空間時，不再是每次都從鏈首開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找。實現(xiàn)可通過設置一起始查尋指針，用于指示下一次起始查尋的空閑分區(qū)，并采用循環(huán)查找方式。缺點缺乏大的空閑分區(qū)。
最佳適應算法。
總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。缺點產(chǎn)生許多碎片。
最壞適應算法。
在掃描整個空閑分區(qū)表或鏈表時，總是挑選一個最大的空閑區(qū)，分割一部分空間給作業(yè)使用。要求將所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈，查找時只要看第一個分區(qū)能否滿足作業(yè)要求即可。缺點缺乏大的空閑分區(qū)。
基于索引搜索的動態(tài)分區(qū)分配算法
快速適應算法。
又稱為分類搜索法。是將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設立一個空閑分區(qū)鏈表，同時在內(nèi)存中設立一張管理索引表，該表的每一個表項對應了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。
該算法僅需要根據(jù)進程的長度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進行分配即可。在分配過程中，不會對任何分區(qū)產(chǎn)生分割。
伙伴系統(tǒng)。
規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為 2 的 k 次冪（k 為整數(shù)，l≤k≤m）。通常 2^m是整個可分配內(nèi)存的大小。
對于每一類具有相同大小的所有空閑分區(qū)，單獨設立一個空閑分區(qū)雙向鏈表。
當需要為進程分配一個長度為 n 的存儲空間時，首先計算一個 i 值，使 2^(i-1) < n ≤ 2^i，然后在空閑分區(qū)大小為 2^i 的空閑分區(qū)鏈表中查找。若找到則直接分配。否則，則在分區(qū)大小為 2^(i+1) 的空閑分區(qū)鏈表中尋找。若存在 2^(i+1) 的一個空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個分區(qū)，這兩個分區(qū)稱為一對伙伴，其中的一個分區(qū)用于分配，而把另一個加入分區(qū)大小為 2^i 的空閑分區(qū)鏈表中。若仍然找不到，依次類推去尋找更高1次冪的分區(qū)。
與一次分配可能要進行多次分割一樣，一次回收也可能要進行多次合并，如回收大小為 2^i的空閑分區(qū)時，若事先已存在回收塊所對應的2^i伙伴塊的空閑分區(qū)時，則應將其與伙伴分區(qū)合并為大小為2^(i+1)的空閑分區(qū)，若事先已存在新合并空閑塊對應的2^(i+1)伙伴塊的空閑分區(qū)時，依次類推合并。
對于一個大小為2^k，地址為x的內(nèi)存塊，其伙伴塊的地址則用buddy k (x)表示，其通式為：
if(x MOD 2^(k+1) == 0) { buddy k (x) = x + 2^k; } else if(x MOD 2^(k+1) == 2^k) { buddy k (x) = x - 2^k; }
哈希算法。
構造一張以空閑分區(qū)大小為關鍵字的哈希表，該表的每一個表項記錄了一個對應的空閑分區(qū)鏈表表頭指針。
動態(tài)可重定位分區(qū)分配
緊湊。
在連續(xù)分配方式中，必須把一個系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。當一臺計算機運行了一段時間后，它的內(nèi)存空間將會被分割成許多小的分區(qū)，而缺乏大的空閑分區(qū)。
通過移動內(nèi)存中作業(yè)的位置，以把原來多個分散的小分區(qū)拼接成一個大分區(qū)的方法，稱為“拼接”或“緊湊”。由于經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化。為此，在每次“緊湊”后，都必須對移動了的程序或數(shù)據(jù)進行重定位。
動態(tài)重定位。
在動態(tài)運行時裝入的方式中，作業(yè)裝入內(nèi)存后的所有地址都仍然是相對(邏輯)地址，將相對地址轉換為物理地址的工作，被推遲到程序指令要真正執(zhí)行時進行。
地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問借助重定位寄存器自動進行的，故稱為動態(tài)重定位。當系統(tǒng)對內(nèi)存進行了“緊湊”而使若干程序從內(nèi)存的某處移至另一處時，不需對程序做任何修改，只要用該程序在內(nèi)存的新起始地址，去置換原來的起始地址即可。
動態(tài)重定位分區(qū)分配算法。
動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本上相同，差別僅在于：在這種分配算法中，增加了緊湊的功能。
對換
多道程序環(huán)境下的對換技術
對換的引入。
所謂“對換”，是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)調出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)調入內(nèi)存。
對換的類型。
1）整體對換。
處理機中級調度實際上就是存儲器的對換功能。其目的用于解決內(nèi)存緊張問題。由于中級調度是以進程為單位的，故又稱之為“進程對換”或“整體對換”。
2）頁面(分段)對換。
以進程的一個“頁面”或“分段”為單位進行的，分別稱為“頁面對換”、“分段對換”，又統(tǒng)稱為“部分對換”。
在此，我們只介紹進程對換，而分頁或分段對換將放在虛擬存儲器中介紹。
對換空間的管理
對對換空間管理的主要目標。
在具有對換功能的 OS 中，通常把外存分為文件區(qū)和對換區(qū)。
1）對文件區(qū)管理的主要目標。
是提高文件存儲空間的利用率，為此，對文件區(qū)采取離散分配方式。
2）對對換區(qū)管理的主要目標。
對換操作較頻繁。故是提高進程換入和換出的速度。為此，采取的是連續(xù)分配方式，較少考慮外存中的碎片問題。
對換空間空閑盤塊管理中的數(shù)據(jù)結構。
與動態(tài)分區(qū)分配方式中的數(shù)據(jù)結構相似，即空閑分區(qū)表或空閑分區(qū)鏈。在每個表目中包含兩項：對換區(qū)的首址及其大小，分表用盤塊號和盤塊數(shù)表示。
對換空間的分配與回收。
與動態(tài)分區(qū)分配方式中內(nèi)存分配與回收方法雷同。
進程的換出與換入
進程的換出。
換出過程：
1）選擇被換出的進程。首先選擇處于阻塞或睡眠狀態(tài)的進程，如果有多個，則選擇優(yōu)先級最低的進程。在有的系統(tǒng)除了考慮優(yōu)先級，還需考慮進程在內(nèi)存的駐留時間。如果系統(tǒng)中已無阻塞進程且內(nèi)存仍不足時，則選擇優(yōu)先級最低的就緒進程換出。
2）進程換出過程。只能換出非共享的程序和數(shù)據(jù)段，對于共享的只要還有進程需要，就不能換出。在進行換出時，①需要申請對換空間。②若申請成功，就啟動磁盤，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。③若傳送成功，便可回收該進程所占的內(nèi)存空間，并對該進程的PCB和內(nèi)存分配表等進行相應的修改，若還有可換出進程，則繼續(xù)換出，直至內(nèi)存中再無阻塞進程為止。
進程的換入。
定時執(zhí)行換入操作。找出“就緒”狀態(tài)但已換出的進程，將其中換出時間最久的進程作為換入進程，為它申請內(nèi)存。若申請成功則調入，若失敗則需先將內(nèi)存中的某些進程換出，再將進程換入。直到外存中再無“就緒且換出”狀態(tài)的進程為止，或者已無足夠的內(nèi)存來換入進程時，對換進程停止換入。
分頁存儲管理方式
基于允許將一個進程直接分散地裝入到許多不相鄰接的分區(qū)中，則無須再進行“緊湊” 的思想而產(chǎn)生了離散分配方式。分為以下三種：
1）分頁存儲管理方式：將用戶程序的地址空間分為若干個固定大小的區(qū)域，稱為“頁”或者“頁面”。也將內(nèi)存空間分為若干個物理塊或頁框，頁和框的大小相同。
2）分段存儲管理方式：把用戶程序的地址空間分為若干個大小不同的段。分配以段為單位。
3）段頁式存儲管理方式：是分頁和分段兩種存儲方式相結合的產(chǎn)物。
分頁存儲管理的基本方法
頁面和物理塊。
1）頁面：將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號。相應地，也把內(nèi)存的物理空間分成若干個塊，并為各塊加以編號。在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”。
2）頁面大?。喉撁娴拇笮x擇適中，且頁面大小應是 2 的冪，通常為 1 KB～8 KB。
地址結構。
邏輯地址的地址結構如下：
含有兩部分：前一部分為頁號 P，后一部分為位移量 W(或稱為頁內(nèi)地址)。圖中的地址長度為 32 位，其中 0～11 位為頁內(nèi)地址，即每頁的大小為 4 KB；12～31 位為頁號，即地址空間最多允許有 1 M 頁?？梢娤到y(tǒng)中允許的最大進程為4kb * 2^20 = 4GB。
對于某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為 A，頁面的大小為 L，則頁號 P 和頁內(nèi)地址 d 可按下式求得：
其中，INT 是整除函數(shù)，MOD 是取余函數(shù)。例如，其系統(tǒng)的頁面大小為 1 KB，設 A = 2170 B，則由上式可以求得 P = 2，d = 122。
頁表。
為保證進程的正確運行，即能在內(nèi)存中找到每個頁面所對應的物理塊。為此，系統(tǒng)又為每個進程建立了一張頁面映像表，簡稱頁表。在進程地址空間內(nèi)的所有頁，依次在頁表中有一頁表項，其中記錄了相應頁在內(nèi)存中對應的物理塊號?？梢姡摫淼淖饔檬菍崿F(xiàn)從頁號到物理塊號的地址映射。
地址變換機構
實現(xiàn)從邏輯地址到物理地址的轉換。由于頁內(nèi)地址和物理地址是一一對應的(例如，對于頁面大小是 1 KB 的頁內(nèi)地址是 0～1023，其相應的物理塊內(nèi)的地址也是 0～1023，無須再進行轉換)，因此，地址變換機構的任務實際上只是將邏輯地址中的頁號，轉換為內(nèi)存中的物理塊號。又因為頁面映射表的作用就是用于實現(xiàn)從頁號到物理塊號的變換，因此，地址變換任務是借助于頁表來完成的。
基本的地址變換機構。
頁表大多駐留在內(nèi)存中。在系統(tǒng)中只設置一個頁表寄存器 PTR，在其中存放頁表在內(nèi)存的始址和頁表的長度。平時，進程未執(zhí)行時，頁表的始址和頁表長度存放在本進程的 PCB 中。當調度程序調度到某進程時，才將這兩個數(shù)據(jù)裝入頁表寄存器中。因此，在單處理機環(huán)境下，雖然系統(tǒng)中可以運行多個進程，但只需一個頁表寄存器。
當進程要訪問某個邏輯地址中的數(shù)據(jù)時，分頁地址變換機構會自動地將有效地址(相對地址)分為頁號和頁內(nèi)地址兩部分，再以頁號為索引去檢索頁表。查找操作由硬件執(zhí)行。在執(zhí)行檢索之前，先將頁號與頁表長度進行比較，如果頁號大于或等于頁表長度，則表示本次所訪問的地址已超越進程的地址空間。于是，這一錯誤將被系統(tǒng)發(fā)現(xiàn)并產(chǎn)生一地址越界中斷。若未出現(xiàn)越界錯誤，則將頁表始址與頁號和頁表項長度的乘積相加，便得到該表項在頁表中的位置，于是可從中得到該頁的物理塊號，將之裝入物理地址寄存器中。與此同時，再將有效地址寄存器中的頁內(nèi)地址送入物理地址寄存器的塊內(nèi)地址字段中。這樣便完成了從邏輯地址到物理地址的變換。
具有快表的地址變換機構。
由于頁表是存放在內(nèi)存中的，這使CPU在每存取一個數(shù)據(jù)時，都要兩次訪問內(nèi)存。第一次是訪問內(nèi)存中的頁表，從中找到指定頁的物理塊號，再將塊號與頁內(nèi)偏移量W拼接，以形成物理地址。第二次訪問內(nèi)存時，才是從第一次所得地址中獲得所需數(shù)據(jù)。
為了提高地址變換速度，可在地址變換機構中增設一個具有并行查尋能力的特殊高速緩沖寄存器，又稱為“聯(lián)想寄存器”，或稱為“快表”，在 IBM 系統(tǒng)中又取名為 TLB，用以存放當前訪問的那些頁表項。此時的地址變換過程是：在 CPU 給出有效地址后，由地址變換機構自動地將頁號 P 送入高速緩沖寄存器，并將此頁號與高速緩存中的所有頁號進行比較，若其中有與此相匹配的頁號，便表示所要訪問的頁表項在快表中。于是，可直接從快表中讀出該頁所對應的物理塊號，并送到物理地址寄存器中。如在塊表中未找到對應的頁表項，則還須再訪問內(nèi)存中的頁表，找到后，把從頁表項中讀出的物理塊號送地址寄存器；同時，再將此頁表項存入快表的一個寄存器單元中，亦即，重新修改快表。但如果聯(lián)想寄存器已滿，則 OS 必須找到一個老的且已被認為不再需要的頁表項，將它換出。
由于成本的關系，快表不可能做得很大，通常只存放 16～512 個頁表項，如果頁面大小為4kb，那么支持的最大進程為2 MB，這對中、小型作業(yè)來說，已有可能把全部頁表項放在快表中。據(jù)統(tǒng)計，從快表中能找到所需頁表項的機率可達 90%以上。
訪問內(nèi)存的有效時間
從進程發(fā)出指定邏輯地址的訪問請求，經(jīng)過地址變換，到在內(nèi)存中找到對應的實際物理地址單元并取出數(shù)據(jù)，所需要花費的總時間，稱為內(nèi)存的有效訪問時間(EAT)。
假設訪問一次內(nèi)存的時間為t，在基本分頁存儲管理方式中，有效訪問時間分為第一次訪問內(nèi)存時間(即查找頁表對應的頁表項所耗費的時間t)與第二次訪問內(nèi)存時間(即訪問頁表項中的物理塊號與頁內(nèi)地址所拼接成的實際物理地址所耗費的時間t)之和： EAT = t + t = 2t；
在快表中查找到所需表項存在著命中率的問題。所謂命中率，是指使用快表并在其中成功查找到所需頁面的表項的比率。
則：EAT = а×λ + (t+λ)(1-а) + t = 2t + λ - t×а；
上式中，λ表示查找快表所需要的時間，а表示命中率，t表示訪問一次內(nèi)存所需要的時間。
兩級和多級頁表
現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間，因此頁表就變得非常大，要占用相當大的內(nèi)存空間。因為每個頁表項占用一個字節(jié)，故頁表長度 * 1字節(jié)就是頁表所占的內(nèi)存空間大小。且頁表內(nèi)存空間還要求是連續(xù)的，顯然這是不現(xiàn)實的。解決方法：
(1) 對于頁表所需的內(nèi)存空間，可采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題；
(2) 只將當前需要的部分頁表項調入內(nèi)存，其余的頁表項仍駐留在磁盤上，需要時再調入。
兩級頁表。
將頁表進行分頁，然后離散地將各個頁面分別存放在不同的物理塊中。也要為離散分配的頁表再建立一張頁表，稱為外層頁表，在每個頁表項中記錄了頁表頁面的物理塊號。
以前面的 32 位邏輯地址空間為例來說明，當頁面大小為 4 KB 時，采用兩級頁表結構時，再對頁表進行分頁，使每頁中包含 2^10 (即 1024)個頁表項，最多允許有 2^10個頁表分頁。此時的邏輯地址結構如下：
在頁表的每個表項中存放的是進程的某頁在內(nèi)存中的物理塊號，而在外層頁表的每個頁表項中，所存放的是某頁表分頁的在內(nèi)存中的物理塊號?？梢岳猛鈱禹摫砗晚摫磉@兩級頁表，來實現(xiàn)從進程的邏輯地址到內(nèi)存中物理地址間的變換。在地址變換機構中同樣需要增設一個外層頁表寄存器，用于存放外層頁表的始址，并利用邏輯地址中的外層頁號，找到指定頁表分頁的始址，再根據(jù)外層頁內(nèi)地址找到指定的頁表項，再從該頁表項中讀出該頁在內(nèi)存中的物理塊號。
雖然解決了對大頁表無需大片連續(xù)存儲空間的問題，但并未解決用較少的內(nèi)存空間去存放大頁表的問題。只用離散分配空間的辦法并未減少頁表所占用的內(nèi)存空間。解決方法是把當前需要的一批頁表項調入內(nèi)存，以后再根據(jù)需要陸續(xù)調入。在采用兩級頁表結構的情況下，對于正在運行的進程，必須將其外層頁表調入內(nèi)存，而對頁表則只需調入一頁或幾頁。為了表征某頁的頁表是否已經(jīng)調入內(nèi)存，還應在外層頁表項中增設一個狀態(tài)位 S，其值若為 0，表示該頁表分頁尚未調入內(nèi)存；否則，
說明其分頁已在內(nèi)存中。進程運行時，地址變換機構根據(jù)邏輯地址中的外層頁號 P1，去查找外層頁表；若所找到的頁表項中的狀態(tài)位為 0，則產(chǎn)生一中斷信號，請求 OS 將該頁表分頁調入內(nèi)存。關于請求調頁的詳細情況，這是下一章虛擬存儲器中的知識。
多級頁表。
對于 32 位的機器，采用兩級頁表結構是合適的；但對于 64 位的機器，必須采用多級頁表，將外層頁表再進行分頁。
反置頁表
反置頁表的引入
在現(xiàn)代計算機系統(tǒng)中，通常允許一個進程的邏輯地址空間非常大，因此就需要有許多的頁表項，而因此也會占用大量的內(nèi)存空間。 引入反置頁表，一般頁表的頁表項是按頁號進行排序的，頁表項中的內(nèi)容是物理塊號。而反置頁表則是為每一個物理塊設置一個頁表項，并按物理塊的編號排序。其中的內(nèi)容是頁號和其所隸屬進程的標識符。
地址變換。
利用反置頁表進行地址變換時，是根據(jù)進程標識符和頁號，去檢索反置頁表。如果檢索到與之匹配的頁表項，則該頁表項(中)的序號i便是該頁所在的物理塊號，可用該塊號與頁內(nèi)地址一起構成物理地址送內(nèi)存地址寄存器。
在反置頁表可能只包含已經(jīng)調入內(nèi)存中的頁面，并未包含尚未調入內(nèi)存的頁面。因此還必須為每個進程建立一個外部頁表。當發(fā)現(xiàn)所需之頁面不在內(nèi)存時，因在外部頁表中包含了各個頁面在外存的物理地址，通過它可將所需之頁面調入內(nèi)存。
當內(nèi)存容量很大時，也表項的數(shù)目還是會非常大的。要利用進程標識符和頁號去檢索這樣大的一個線性表是相當費時的?？衫肏ash算法來進行檢索，可以很快找到在反置頁表中相應頁表項，不過可能會出現(xiàn)所謂的“地址沖突”。
分段存儲管理方式
如果說推動存儲管理方式從固定分區(qū)到動態(tài)分區(qū)分配，進而又發(fā)展到分頁存儲管理方式的主要動力，是提高內(nèi)存利用率，那么，引入分段存儲管理方式的目的，則主要是為了滿足用戶(程序員)在編程和使用上多方面的要求。
分段存儲管理方式的引入
方便編程。
通常，用戶把自己的作業(yè)按照邏輯關系劃分為若干個段。程序員們都迫切地需要訪問的邏輯地址是由段名(段號)和段內(nèi)偏移量(段內(nèi)地址)決定的。
信息共享。
實現(xiàn)對程序和數(shù)據(jù)的共享時，是以信息的邏輯單位為基礎的。分頁系統(tǒng)中的“頁”只是存放信息的物理單位(塊)，并無完整的意義。而段卻是信息的邏輯單位，因此可以為該被共享過程建立一個獨立的段，極大地簡化了共享的實現(xiàn)。
信息保護。
信息保護同樣是對信息的邏輯單位進行保護的。在分頁系統(tǒng)中，一個函數(shù)可能要占用若干個頁面，而且其中的第一個和最后一個頁面還會裝有其它程序段的數(shù)據(jù)，它們可能有著不同的保護屬性。
動態(tài)增長。
動態(tài)鏈接。
運行時動態(tài)鏈接要求的是以目標程序(即段)作為鏈接的基本單位，因此，分段存儲管理方式非常適合動態(tài)鏈接。
分段系統(tǒng)的基本原理
分段。
作業(yè)的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。每個段都從 0 開始編址，并采用一段連續(xù)的地址空間。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。整個作業(yè)的地址空間由于是分成多個段，因而呈現(xiàn)出二維特性。其邏輯地址由短號和段內(nèi)地址組成。
段表。
在分段式存儲管理系統(tǒng)中，則是為每個分段分配一個連續(xù)的分區(qū)，而進程中的各個段可以離散地移入內(nèi)存中不同的分區(qū)中。在系統(tǒng)中為每個進程建立一張段映射表，簡稱“段表”。每個段在表中占有一個表項，其中記錄了該段在內(nèi)存中的起始地址(又稱為“基址”)和段的長度?？梢?，段表是用于實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。
地址變換機構。
為了實現(xiàn)從進程的邏輯地址到物理地址的變換功能，在系統(tǒng)中設置了段表寄存器，用于存放段表始址和段表長度 TL。在進行地址變換時，系統(tǒng)將邏輯地址中的段號與段表長度TL 進行比較。若 S>TL，表示段號太大，是訪問越界，于是產(chǎn)生越界中斷信號；若未越界，則根據(jù)段表的始址和該段的段號，計算出該段對應段表項的位置，從中讀出該段在內(nèi)存的起始地址，然后，再檢查段內(nèi)地址 d 是否超過該段的段長 SL。若超過，即 d>SL，同樣發(fā)出越界中斷信號；若未越界，則將該段的基址與段內(nèi)地址相加，即可得到要訪問的內(nèi)存物理地址。
像分頁系統(tǒng)一樣，當段表放在內(nèi)存中時，每要訪問一個數(shù)據(jù)，都須訪問兩次內(nèi)存，從而極大地降低了計算機的速率。解決的方法也和分頁系統(tǒng)類似，再增設一個聯(lián)想存儲器，用于保存最近常用的段表項。
分頁和分段的主要區(qū)別。
相似之處：
兩者都采用離散分配方式，且都要通過地址映射機構來實現(xiàn)地址變換。
不同：
1）頁是信息的物理單位，分頁是為了提高內(nèi)存的利用率。段則是信息的邏輯單位，分段的目的是為了能更好地滿足用戶的需要。
2）頁的大小固定且由系統(tǒng)決定。而段的長度卻不固定，決定于用戶所編寫的程序。
3）分頁中用戶程序的的邏輯地址空間是一維的，分頁完全是系統(tǒng)的行為，只需要一個記憶符即可表示一個地址。而分段中用戶程序的邏輯地址空間是二維的，在標識一個地址時，既需給出段名， 又需給出段內(nèi)地址（正是因為段的大小不固定導致的）。
信息共享
分頁系統(tǒng)中對程序和數(shù)據(jù)的共享。
雖然也能實現(xiàn)對程序和數(shù)據(jù)的共享，但遠不如分段系統(tǒng)來得方便。
分段系統(tǒng)中對程序和數(shù)據(jù)的共享。
可重入代碼又稱為“純代碼”，是一種允許多個進程同時訪問的代碼?？芍厝氪a是一種不允許任何進程對它進行修改的代碼。但事實上，大多數(shù)代碼在執(zhí)行時都可能有些改變。為此，在每個進程中，都必須配以局部數(shù)據(jù)區(qū)，把在執(zhí)行中可能改變的部分拷貝到該數(shù)據(jù)區(qū)，這樣，程序在執(zhí)行時，只需對該數(shù)據(jù)區(qū)(屬于該進程私有)中的內(nèi)容進行修改，并不去改變共享的代碼，這時的可共享代碼即成為可重入碼。
段頁式存儲管理方式
基本原理。
段頁式系統(tǒng)的基本原理是分段和分頁原理的結合，即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。在段頁式系統(tǒng)中，其地址結構由段號、段內(nèi)頁號及頁內(nèi)地址三部分所組成。
為了實現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)中需要同時配置段表和頁表。段表的內(nèi)容與分段系統(tǒng)略有不同，它不再是內(nèi)存始址和段長，而是頁表始址和頁表長度。即一個分段對應一個頁表。
地址變換過程。
為了便于實現(xiàn)地址變換，須配置一個段表寄存器，其中存放段表始址和段長TL。進行地址變換時，首先利用段號S，將它與段長TL進行比較。若S?<?TL，表示未越界，于是利用段表始址和段號來求出該段所對應的段表項在段表中的位置，從中得到該段的頁表始址，并利用邏輯地址中的段內(nèi)頁號P來獲得對應頁的頁表項位置，從中讀出該頁所在的物理塊號b，再利用塊號b和頁內(nèi)地址來構成物理地址。
在段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，須三次訪問內(nèi)存。第一次訪問是訪問內(nèi)存中的段表，從中取得頁表始址；第二次訪問是訪問內(nèi)存中的頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問才是真正從第二次訪問所得的地址中，取出指令或數(shù)據(jù)。
解決方法仍類似快表。在地址變換機構中增
設一個高速緩沖寄存器。每次訪問它時，都須同時利用段號和頁號去檢索高速緩存，若找到匹配的表項，便可從中得到相應頁的物理塊號，用來與頁內(nèi)地址一起形成物理地址；若未找到匹配表項，則仍須再三次訪問內(nèi)存。
