操作系統(tǒng)第四章存儲器管理

第四章存儲器管理

如何對存儲器加以有效的管理，不僅直接影響到存儲器的利用率，而且還對系統(tǒng)性能有重大影響。存儲器管理的主要對象是內存。本章主要內容4.1存儲器的層次結構4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4對換4.5分頁存儲管理方式4.6分段存儲管理方式4.1存儲器的層次結構4.1.1多級存儲器結構1.存儲器的多層結構2.可執(zhí)行存儲器寄存器和主存儲器又被稱為可執(zhí)行存儲器訪問機制不同，所需耗費的時間不同進程可以在很少的時鐘周期內使用一條load或store指令對可執(zhí)行存儲器進行訪問輔存的訪問通過I/O設備來實現(xiàn)，訪問中將涉及到訪問則中斷、設備驅動程序以及物理設備的運行，所需耗費的時間相差3個數(shù)量級甚至更多。

4.1.2主存儲器與寄存器

1．主存儲器主存儲器(簡稱內存或主存)是計算機系統(tǒng)中一個主要部件，用于保存進程運行時的程序和數(shù)據(jù)，也稱可執(zhí)行存儲器CPU的控制部件只能從主存儲器中取得指令和數(shù)據(jù)，數(shù)據(jù)能夠從主存儲器讀取并將它們裝入到寄存器中，或者相反主存儲器的訪問速度遠低于CPU執(zhí)行指令的速度，引入寄存器和高速緩存。2．寄存器寄存器訪問速度最快，完全能與CPU協(xié)調工作，但價格卻十分昂貴，因此容量不可能做得很大寄存器用于加速存儲器的訪問速度，如用寄存器存放操作數(shù)，或用作地址寄存器加快地址轉換速度等

4.1.3高速緩存和磁盤緩存

1．高速緩存高速緩存是現(xiàn)代計算機結構中的一個重要部件，其容量大于或遠大于寄存器，而比內存約小兩到三個數(shù)量級左右。根據(jù)程序執(zhí)行的局部性原理，將主存中一些經(jīng)常訪問的信息存放在高速緩存中，減少訪問主存儲器的次數(shù)，可大幅度提高程序執(zhí)行速度。進程的程序和數(shù)據(jù)是存放在主存儲器中，每當使用時，被臨時復制到一個速度較快的高速緩存中。當CPU訪問一組特定信息時，首先檢查它是否在高速緩存中，如果已存在，可直接從中取出使用，以避免訪問主存，否則，再從主存中讀出信息。

2．磁盤緩存

由于目前磁盤的I/O速度遠低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。磁盤緩存本身并不是一種實際存在的存儲介質，它依托于固定磁盤，提供對主存儲器存儲空間的擴充，即利用主存中的存儲空間，來暫存從磁盤中讀出(或寫入)的信息。主存也可以看做是輔存的高速緩存一個文件的數(shù)據(jù)可能出現(xiàn)在存儲器層次的不同級別中，例如，一個文件數(shù)據(jù)通常被存儲在輔存中(如硬盤)，當其需要運行或被訪問時，就必須調入主存，也可以暫時存放在主存的磁盤高速緩存中。大容量的輔存常常使用磁盤，磁盤數(shù)據(jù)經(jīng)常備份到磁帶或可移動磁盤組上，以防止硬盤故障時丟失數(shù)據(jù)本章主要內容4.1存儲器的層次結構4.2程序的裝入和鏈接4.2程序的裝入和鏈接如何將一個用戶源程序變成一個可在內存中執(zhí)行的程序，通常要經(jīng)過3步驟：編譯:由編譯程序（Compiler）將用戶源代碼編譯成若個目標模塊。鏈接:由鏈接程序（Linker）將編譯后形成的一組目標模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊。裝入:由裝入程序（Loader）將裝入模塊裝入內存。1.程序的裝入(1)．絕對裝入方式

如果知道程序將駐留在內存的什么位置，那么，編譯程序將產(chǎn)生絕對地址的目標代碼。

絕對裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內存。

由于程序中的邏輯地址與實際內存地址完全相同，故不需對程序和數(shù)據(jù)的地址進行修改。(2)．可重定位裝入方式

由裝入程序將裝入模塊裝入內存后，裝入模塊中程序所訪問的所有邏輯地址與實際裝入內存的物理地址不同，必須進行變換。把在裝入時對目標程序中指令和數(shù)據(jù)的變換過程稱為重定位。因為地址變換是在裝入時一次完成的，以后不再改變，故稱為靜態(tài)重定位。采用靜態(tài)重定位方法將程序裝入內存,稱為可重定位裝入方式。(3)．動態(tài)運行時裝入方式

裝入程序將目標模塊裝入內存后，并不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序執(zhí)行時進行，在硬件地址變換機構的支持下，隨著對每條指令或數(shù)據(jù)的訪問自動進行地址變換，故稱為動態(tài)重定位。2.程序的鏈接★源程序經(jīng)過編譯后，得到一組目標模塊，再利用鏈接程序將其鏈接形成裝入模塊。根據(jù)鏈接時間的不同，可把鏈接分成如下三種：(1)、靜態(tài)鏈接方式。在程序運行之前，先將各目標模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝配模塊（又稱執(zhí)行模塊），以后不再拆開。

事先進行鏈接的方式稱為靜態(tài)鏈接方式。①對相對地址進行修改目標模塊中，使用的都是相對地址，其起始地址都為0，在鏈接成一個裝入模塊時修改模塊的相對地址。

如把原B中的所有相對地址都加上L，把原C中所有相對地址都加上L＋M。②變換外部引用地址將每個模塊中所用的外部調用符號也都變換為相對地址。例如將callB變換為JSR“L”(2)、裝入時動態(tài)鏈接

是指將用戶源程序編譯后所得到的一組目標模塊，在裝入內存時，采用邊裝入邊鏈接的鏈接方式。

在裝入一個目標模塊時，若發(fā)生一個外部模塊調用事件，將引起裝入程序去找出相應的外部目標模塊，并將它裝入內存

即分別裝入各模塊，并且在裝入的過程中修改相對地址和外部引用地址。裝入時動態(tài)鏈接方式有以下優(yōu)點：

①便于修改和更新若采用動態(tài)鏈接方式，由于各目標模塊是分開存放的，所以要修改或更新各目標模塊，是件非常容易的事。②便于實現(xiàn)對目標模塊的共享在采用裝入時動態(tài)鏈接方式時，OS則很容易將一個目標模塊鏈接到幾個應用模塊上，實現(xiàn)多個應用程序對該模塊的共享。(3)、運行時動態(tài)鏈接 各模塊被獨立裝入系統(tǒng)，而且也不進行鏈接，運行時發(fā)現(xiàn)引用的地址是相對地址或者外部地址時，才發(fā)起鏈接，尋找正確的引用地址。

優(yōu)點：凡在執(zhí)行過程中未被用到的目標模塊，都不會被調入內存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內存空間。該方法是目前最常使用的鏈接方式。本章主要內容4.1存儲器的層次結構4.2程序的裝入和鏈接4.3連續(xù)分配方式4.3連續(xù)分配方式連續(xù)分配方式，是指為一個用戶程序分配一個連續(xù)的內存空間。連續(xù)分配方式有四種：單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配可重定位分區(qū)分配(湯子瀛)4.3.1單一連續(xù)分配這是最早、最簡單的一種存儲分配方式。它規(guī)定整個內存的用戶區(qū)中只駐留一個用戶的一個程序，因此該方式只適用于單用戶、單任務的操作系統(tǒng)。4.3.1單一連續(xù)分配為了防止OS的代碼和數(shù)據(jù)被用戶進程所破壞，把內存分為系統(tǒng)區(qū)和用戶區(qū)兩部分：系統(tǒng)區(qū)：僅提供給0S使用，通常是放在內存的低址部分；用戶區(qū)：是指除系統(tǒng)區(qū)以外的全部內存空間，提供給唯一的用戶使用，存放用戶程序和數(shù)據(jù)。優(yōu)缺點：簡單、內存利用率低。4.3.2分區(qū)管理-固定分區(qū)分配

固定分區(qū)分配思想：將內存用戶空間劃分為若干個固定大小的區(qū)域，每個區(qū)域稱為一個分區(qū)（region），在每個分區(qū)中只裝入一道作業(yè)，從而支持多道程序并發(fā)設計。(1)．分區(qū)大小

①分區(qū)大小相等。當程序太小時，會造成內存空間的浪費。當程序太大時，一個分區(qū)又不足以裝入該程序，致使該程序無法運行。②分區(qū)大小不等?？砂褍却鎱^(qū)劃成含有多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。(2)．分區(qū)分配

1、如何知道哪些分區(qū)可以分配？

采用分區(qū)描述表記錄每個分區(qū)的狀態(tài)信息，如下圖所示。4.3.2分區(qū)管理-固定分區(qū)分配內存分配情況分區(qū)編號大小（KB）起始地址（KB）狀態(tài)13030分配24060分配330100分配440130未分配540170分配作業(yè)D空閑分區(qū)作業(yè)C作業(yè)B作業(yè)A操作系統(tǒng)03060100130170210分區(qū)描述表2、如何分配各分區(qū)？

當有作業(yè)要裝入內存時，內存分配程序檢索分區(qū)描述表，從中找出尚未使用的最接近大小的分區(qū)分配給該作業(yè)，然后修改分區(qū)的狀態(tài)；如果找不到合適的分區(qū)就拒絕為該作業(yè)分配內存。 當程序運行完成時，系統(tǒng)回收內存資源，并修改分區(qū)描述表中分區(qū)的狀態(tài)。4.3.2分區(qū)管理-固定分區(qū)分配4.3.2分區(qū)管理-固定分區(qū)分配固定分區(qū)式分配的優(yōu)缺點：可運行多道程序的存儲管理方式。存在“內零頭”會造成存儲空間的浪費。內零頭——在分區(qū)內沒有利用的部分稱為內零頭。4.3.3分區(qū)管理-動態(tài)分區(qū)方式

動態(tài)分區(qū)分配思想：分區(qū)數(shù)量和大小都不固定，根據(jù)進程的實際需要，動態(tài)地為之分配內存空間。(1)分區(qū)組織記錄系統(tǒng)中各空閑分區(qū)的情況，以便分配時能找到可以分配的空間。①空閑分區(qū)表。在系統(tǒng)中設置一張空閑分區(qū)表，用于記錄每個空閑分區(qū)的情況（包含空閑分區(qū)號、分區(qū)大小、起始地址）。②空閑分區(qū)鏈表。為了實現(xiàn)對空閑分區(qū)的分配和鏈接，設置前向指針和后向指針，通過前、后向鏈接指針將所有的空閑分區(qū)鏈接成一個雙向鏈?？臻e分區(qū)鏈表當分區(qū)被分配出去以后，把狀態(tài)位由“0”改為“1”(2)分區(qū)分配算法 ①首次匹配(首次適應算法FF)：要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內存時，從鏈首開始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止。 優(yōu)缺點：為大作業(yè)分配大的內存空間創(chuàng)造了條件。低址部分不斷被劃分，會留下許多難以利用的、很小的空閑分區(qū)。②循環(huán)匹配(循環(huán)首次適應算法):

將所有的空閑分區(qū)構成一個循環(huán)鏈表。每次查找時不是從頭開始，而是從上次結束位置開始。 優(yōu)缺點：能使內存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時的開銷，但這樣會缺乏大的空閑分區(qū)。③最佳匹配(最佳適應算法):

總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”

該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。從頭開始查找，將表中第一個大于所需求空間大小的空閑區(qū)分配給作業(yè)。優(yōu)缺點：為大作業(yè)分配大的內存空間創(chuàng)造了條件。每次分配后所切割下來的剩余部分總是最小的，這樣，在存儲器中會留下許多難以利用的小空閑區(qū)。4.最壞適應算法

與最佳適應算法相反，選擇一個最大的空閑區(qū)，分割一部分給作業(yè)使用，缺乏大的空閑分區(qū)。優(yōu)點：剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的可能性最小，有利于中，小作業(yè)；

查找效率很高。

3．分區(qū)分配操作

在動態(tài)分區(qū)存儲管理方式中，主要的操作是分配內存和回收內存。（1）分配內存系統(tǒng)應利用某種分配算法，從空閑分區(qū)鏈中找到所需大小的分區(qū)。Size是事先規(guī)定的不再切割的剩余分區(qū)的大小。（3）分區(qū)回收

當進程運行完畢釋放內存時，需合并相鄰的空閑分區(qū)，形成大的分區(qū)，稱為合并技術。需要合并的情況有如下圖所示的三種，不論哪種情況，只需修改相應的分區(qū)信息來完成合并即可?；厥辗謪^(qū)前有空閑分區(qū)回收分區(qū)后有空閑分區(qū)回收分區(qū)前后都有空閑分區(qū)4.3.4動態(tài)分區(qū)示例-快速適應算法該算法又稱為分類搜索法空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設立一個空閑分區(qū)鏈表內存中設立一張管理索引表，該表的每一個表項對應了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針?？臻e分區(qū)的分類是根據(jù)進程常用的空間大小進行劃分，如2KB、4KB、8KB等，對于其它大小的分區(qū)，如7KB這樣的空閑區(qū)，既可以放在8KB的鏈表中，也可以放在一個特殊的空閑區(qū)鏈表中。優(yōu)點：查找效率高，僅需要根據(jù)進程的長度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進行分配即可。進行空閑分區(qū)分配時，不會對任何分區(qū)產(chǎn)生分割，所以能保留大的分區(qū)，滿足對大空間的需求，也不會產(chǎn)生內存碎片。缺點：分區(qū)歸還主存時算法復雜，系統(tǒng)開銷較大。分配空閑分區(qū)時是以進程為單位，一個分區(qū)只屬于一個進程，因此在為進程所分配的一個分區(qū)中，或多或少地存在一定的浪費?？臻e分區(qū)劃分越細，浪費則越嚴重，整體上會造成可觀的存儲空間浪費，這是典型的以空間換時間的作法。4.3.5分區(qū)管理-動態(tài)分區(qū)示例-伙伴系統(tǒng)伙伴系統(tǒng)是一種不需要緊湊的動態(tài)分區(qū)算法?；锇橄到y(tǒng)是內存塊管理機制，采用二進制數(shù)的方式來分配和回收空間。提高回收空間時合并空閑分區(qū)的速度，Linux操作系統(tǒng)使用該算法分配和回收頁面塊。優(yōu)點：分配和回收內存速度快，且不會產(chǎn)生很多小碎片。缺點：內存利用率不高，分配的內存大小為2的冪，假如只需要65個頁面，也需要分配128個頁面的塊，從而浪費了63個頁面，即產(chǎn)生內部碎片。4.3.5伙伴系統(tǒng)伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)，l≤k≤m，其中：21

表示分配的最小分區(qū)的大小，2m

表示分配的最大分區(qū)的大小，通常2m是整個可分配內存的大小。假設系統(tǒng)的可利用空間容量為2m個字，則系統(tǒng)開始運行時，整個內存區(qū)是一個大小為2m的空閑分區(qū)。在系統(tǒng)運行過程中，由于不斷的劃分，可能會形成若干個不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進行分類，對于每一類具有相同大小的所有空閑分區(qū)，單獨設立一個空閑分區(qū)雙向鏈表。不同大小的空閑分區(qū)形成了k(0≤k≤m)個空閑分區(qū)鏈表當需要為進程分配一個長度為n的存儲空間時，首先計算一個i值，使2i-1<n≤2i，然后在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進程。否則，表明長度為2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i+1的空閑分區(qū)鏈表中尋找。若存在2i+1

的一個空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個分區(qū)，這兩個分區(qū)稱為一對伙伴，其中的一個分區(qū)用于分配，而把另一個加入分區(qū)大小為2i的空閑分區(qū)鏈表中。若大小為2i+1的空閑分區(qū)也不存在，則需要查找大小為2i+2的空閑分區(qū)若找到則對其進行兩次分割：第一次，將其分割為大小為2i+1

的兩個分區(qū)，一個用于分配，一個加入到大小為2i+1的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為2i的兩個分區(qū)，一個用于分配，一個加入到大小為2i的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為2i+3的空閑分區(qū)，以此類推。在最壞的情況下，可能需要對2k的空閑分區(qū)進行k次分割才能得到所需分區(qū)一次回收也可能要進行多次合并，如回收大小為2i的空閑分區(qū)時，若事先已存在2i的空閑分區(qū)時，則應將其與伙伴分區(qū)合并為大小為2i+1的空閑分區(qū)若事先已存在2i+1的空閑分區(qū)時，又應繼續(xù)與其伙伴分區(qū)合并為大小為2i+2的空閑分區(qū)。在當前的操作系統(tǒng)中，普遍采用基于分頁和分段機制的虛擬內存機制，該機制較伙伴算法更為合理和高效在多處理機系統(tǒng)中，伙伴系統(tǒng)仍不失為一種有效的內存分配和釋放的方法4.3.5哈希算法哈希算法就是利用哈?？焖俨檎业膬?yōu)點，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構造一張以空閑分區(qū)大小為關鍵字的哈希表，該表的每一個表項記錄了一個對應的空閑分區(qū)鏈表表頭指針。當進行空閑分區(qū)分配時，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計算，即得到在哈希表中的位置，從中得到相應的空閑分區(qū)鏈表，實現(xiàn)最佳分配策略。4.3.6分區(qū)管理-緊湊與動態(tài)重定位上述的各種動態(tài)分區(qū)的分配算法都不可避免的產(chǎn)生大量無法利用的碎片，這些無法利用的空閑分區(qū)稱為“外部碎片”。緊湊技術——將內存中的所有作業(yè)進行移動，使它們全都相鄰接，這樣，可把原來分散的多個小分區(qū)合成一個大分區(qū)的方法，稱為緊湊。要獲得40KB的內存空間動態(tài)重定位的實現(xiàn)設置重定位寄存器，存放數(shù)據(jù)在內存中的起始地址真正的訪問地址=相對地址+重定位寄存器的地址地址變換在訪問時自動進行，所以稱為動態(tài)重定位。動態(tài)重定位分區(qū)分配算法啟動緊湊的時機：1.載入大程序，而無可用空間時，系統(tǒng)自動啟動緊湊，2.發(fā)現(xiàn)碎片較多，系統(tǒng)比較空閑時。動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本上相同差別僅在于：在這種分配算法中，增加了緊湊的功能，通常，在找不到足夠大的空閑分區(qū)來滿足用戶需求時進行緊湊。本章主要內容4.1存儲器的層次結構4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4對換4.4對換

4.4.1多道程序環(huán)境下的對換技術

1．對換的引入所謂“對換”，是指把內存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調出到外存上，以便騰出足夠的內存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調入內存。對換是提高內存利用率的有效措施。2.對換的類型如果對換是以整個進程為單位，便稱之為“整體對換”或“進程對換”。中級調度如果對換是以進程的一個“頁”或“段”為單位進行的，則分別稱之為“頁面對換”或“分段對換”，又統(tǒng)稱為“部分對換”。它是實現(xiàn)請求分頁和請求分段式存儲管理的基礎，其目的是為了支持虛擬存儲系統(tǒng)為了實現(xiàn)進程對換，系統(tǒng)必須能實現(xiàn)三方面的功能：對換空間的管理進程的換出進程的換入2．對換空間的管理

在具有對換功能的OS中，通常把外存分為文件區(qū)和對換區(qū)。進程在對換區(qū)中駐留的時間是短暫的、對換操作又較頻繁.對換空間管理的目標：提高進程換入和換出的速度。3．進程的換出與換入

（1）進程的換出

系統(tǒng)選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。然后回收該進程所占用的內存空間，并對該進程的進程控制塊做相應的修改。（2）進程的換入（一般由調度程序實現(xiàn)）系統(tǒng)定時地查看所有進程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進程；將其中換出時間最久的進程作為換入進程；有能滿足進程需要的內存時可將之換入。

注意：為了避免頻繁的換進換出，設置換出的一個時間限制。例如在內存至少駐留2秒鐘才能換出。本章主要內容4.1存儲器的層次結構4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4對換4.5分頁存儲管理方式思考：連續(xù)分配方式有什么優(yōu)缺點？有沒有更好的分配方式？4.5分頁存儲管理方式離散分配方式:為進程分配空間不要求具有連續(xù)的空間,可以是多個分離的空間為進程占用。采用離散分配方式的存儲管理有：分頁存儲管理段式存儲管理段頁式存儲管理（一）分頁存儲管理1.頁面和物理塊分頁存儲管理：將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁。相應地，也把內存空間分成與頁面相同大小的若干個存儲塊，稱為（物理）塊或頁框。在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內碎片”或稱為“內零頭”。（1）頁面大小頁面?。簻p小內存碎片，提高內存利用率；頁表過長，占用內存頁面大，可以減少頁表的長度，提高頁面換進換出的速度；會使頁內碎片增大。頁面的大小應選擇得適中，且頁面大小應是2的冪，通常為512B～8KB。（2）空間的組織地址空間為程序限定的空間。物理空間為內存限定空間。在頁式管理系統(tǒng)中將地址空間分成大小相同頁面。將內存空間分成與頁面相同大小的存儲塊。32位機的分頁存儲邏輯地址結構:頁號頁內偏移量3112110圖3.13分頁管理的邏輯地址表示2．地址結構地址長度32位，0~11位為頁內地址，即每頁大小為4KB，12~31位為頁號，地址空間最多允許有1M頁給定邏輯地址空間為A，頁面大小為L，則頁號P和頁內地址d的計算公式為

P=INT[A/L]d=[A]MODLINT:整除函數(shù)MOD取余函數(shù)例：頁面大小為1KB，A=2170，則P=2，d=122。頁號P位移量w在分頁系統(tǒng)中，允許將進程的每一頁離散地存儲在內存的任一物理塊中，但系統(tǒng)應能保證進程的正確運行，即能在內存中找到每個頁面所對應的物理塊。系統(tǒng)又為每個進程建立了一張頁面映像表，簡稱頁表。在頁表的表項中設置一存取控制字段，用于對該存儲塊中的內容加以保護。3．頁表頁表的作用：實現(xiàn)從頁號到物理塊號的地址映射。示例假設內存能提供16個空閑頁框，進程P1被分割成4個頁面，裝入內存中的0號至3號頁框。進程P2被分割成3個頁面，裝入4號至6號頁框。進程P3被裝入7號至12號頁框，如圖4.14(a)所示。此時，進程P4請求分配5個頁框大小的存儲空間，但內存只有3個空閑頁框。于是，將暫時不運行的P2交換出內存，如圖4.15(b)所示。然后，再將P4裝入4、5、6、13、14號頁框，如圖4.15(c)所示。

圖4.14進程裝入到離散的頁框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5頁框號內存(a)依次裝入P1、P2、P3P1P2P3空閑0123456789101112131415P1.2P1.1P1.0P1.3P3.0P3.1P3.2P3.3P3.4P3.5頁框號內存(b)換出P2P1空閑P3空閑0123456789101112131415P1.2P1.1P1.0P1.3P4.0P4.1P4.2P3.0P3.1P3.2P3.3P3.4P3.5P4.3P4.4頁框號內存(c)裝入P4P1P4P3空閑P4頁號頁框號00112233進程P1頁表頁號頁框號0-1-2-進程P2頁表頁號頁框號071829310411512進程P3頁表頁號頁框號041526313414進程P4頁表圖4.15進程P1、P2、P3、P4的頁表各進程的頁表結構及其內容地址變換硬件機制，實現(xiàn)邏輯地址到物理地址的轉換。在系統(tǒng)中只設置一個頁表寄存器PTR，在其中存放當前運行的進程的頁表在內存中的起始地址，和此進程的頁表長度。當進程真正投入運行時，從進程控制表中讀出其頁表起始地址，并用它設置頁表寄存器，以后地址轉換時直接從PTR中獲得頁表的起始地址。4.5.2地址變換機構分頁系統(tǒng)中的地址變換過程如下：（1）

根據(jù)邏輯地址,計算出頁號和頁內偏移量；（2）從PTR中得到頁表首址，然后檢索頁表，查找指定頁面對應的頁框號；（3）用頁框號乘以頁面大小獲得其對應的起始地址，并將其送入物理地址的高端。（4）將頁內偏移量送入物理地址低端，形成完整的物理地址。地址變換機構圖頁號≥頁表長度越界中斷;頁表始址與頁號和頁表項長度的乘積相加該表項在頁表中的位置該頁的物理塊號物理地址寄存器中2．具有快表的地址變換機構分頁系統(tǒng)：處理機每次存取指令或數(shù)據(jù)至少需要訪問兩次物理內存

—第一次訪問頁表，第二次存取指令或數(shù)據(jù)為了提高地址變換速度，為進程頁表設置一個專用的高速緩沖存儲器，稱為快表、TLB(TranslationLookasideBuffer)，或聯(lián)想存儲器（AssociativeMemory）快表不可能做得很大，通常只存放16～512個頁表項?？毂淼墓ぷ髟砜毂淼墓ぷ髟眍愃朴谙到y(tǒng)中的數(shù)據(jù)高速緩存(cache)，其中專門保存當前進程最近訪問過的一組頁表項。進程最近訪問過的頁面在不久的將來還可能被訪問。分頁系統(tǒng)地址轉換通過根據(jù)邏輯地址中的頁號，查找快表中是否存在對應的頁表項。若快表中存在該表項，稱為命中（hit），取出其中的頁框號，加上頁內偏移量，計算出物理地址。若快表中不存在該頁表項，稱為命中失敗，則再查找頁表，找到邏輯地址中指定頁號對應的頁框號。同時，更新快表，將該表項插入快表中。并計算物理地址.具有快表的地址變換過程：

企圖少訪問一次內存4.5.3訪問內存的有效時間從進程發(fā)出指定邏輯地址的訪問請求，經(jīng)過地址變換，到在內存中找到對應的實際物理地址單元并取出數(shù)據(jù)，所需花費的總時間引入快表后：：命中率；：查找快表所需時間；：訪問一次內存所需時間；示例命中率有效訪問時間022050170801409013098122=20ns,t=100ns結論：引入快表后，CPU訪問數(shù)據(jù)的時間明顯減少4.5.4兩級和多級頁表

現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間，頁表就變得非常大，又因為每個頁表項占用一個字節(jié)，故每個進程僅僅其頁表就要占用大的內存空間，而且還要求是連續(xù)的。

顯然這是不現(xiàn)實的大頁表

大邏輯地址空間，頁表非常大，需要占用相當大的內存空間。比如，32位邏輯地址空間，假設頁面大小為4KB（212），則4GB（232）的邏輯地址空間將被劃分成220個頁面。大頁表

若采用一級頁表，則其內將包含1兆（220）個頁表項。若按字節(jié)尋址，一個頁表項占4B，則一級頁表需要占用4MB（222）內存空間。不可能將4MB的頁表保存在一個連續(xù)區(qū)中。那么，如何處理大頁表的存儲與檢索呢？

可以采用這樣兩個方法來解決這一問題：①采用離散分配方式來解決難以找到一塊連續(xù)的大內存空間的問題，（即引入兩級頁表）；②只將當前需要的部分頁表項調入內存，其余的頁表項仍駐留在磁盤上，需要時再調入。1．兩級頁表將頁表再進行分頁，并離散地將各個頁面分別存放在不同的物理塊中，為離散分配的頁面再建立一張頁表，稱為外層頁表，在每個頁表項中記錄了頁表頁面的物理塊號。若采用一級頁表結構，應具有20位的頁號，即頁表項應有1兆個。在采用兩級頁表結構時，邏輯地址結構可描述如下：

當頁面大小為4KB時(12位)，在采用兩級頁表結構時，再對頁表進行分頁，使每頁中包含210(即1024)個頁表項，最多允許有210個頁表分頁；或者說，外層頁表中的外層頁內地址P2為10位，外層頁號P1也為10位（1M=1K*1K)頁表的每個表項中存放的是進程的某頁在內存中的物理塊號;

1#頁存放在4#物理塊中外層頁表的每個頁表項中，所存放的是某頁表分頁的首址,第0#頁表是存放在第1011#物理塊中利用外層頁表和頁表這兩級頁表，來實現(xiàn)從進程的邏輯地址到內存中物理地址間的變換。在地址變換機構中同樣需要增設一個外層頁表寄存器，用于存放外層頁表的始址，并利用邏輯地址中的外層頁號，作為外層頁表的索引，從中找到指定頁表分頁的始址，再利用P2作為指定頁表分頁的索引，找到指定的頁表項，其中即含有該頁在內存的物理塊號，用該塊號和頁內地址d即可構成訪問的內存物理地址。2．多級頁表對于64位的機器，采用兩級頁表仍然有困難，必須采用多級頁表，將外層頁表再進行分頁，也就是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關系，來實現(xiàn)分頁存儲管理。頁面與頁框大小影響頁面與頁框大小的主要因素：頁內零頭、地址轉換速度和頁面交換效率。較小的頁面有利于減少內零頭，從而有利于提高內存的利用率。然而，較小的頁面也將導致頁表過大，從而降低處理機訪問頁表時的命中率(HitRate)。塊越大，內/外存之間的數(shù)據(jù)交換效率越高。因此，對于支持交換技術的系統(tǒng)，較大的頁面有利于提高頁面換進/換出內存的效率。對分頁存儲管理的評價徹底消除了外零頭,僅存在很少的內零頭,提高了內存利用率。分頁操作由系統(tǒng)自動進行,一個頁面不能實現(xiàn)某種邏輯功能。用戶看到的邏輯地址是一維的，無法調試執(zhí)行其中的某個子程序或子函數(shù)。采用分頁技術不易于實現(xiàn)存儲共享，也不便于程序的動態(tài)鏈接。本章主要內容4.1存儲器的層次結構4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4對換4.5分頁存儲管理方式4.6分段存儲管理方式4.6分段存儲管理方式

4．6．1分段存儲管理方式的引入

引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一系列需要：1）方便編程

例如，下述的兩條指令便是使用段名和段內地址：

LOAD1，[A]|〈D〉；//將分段A中D單元內的值讀入寄存器1；

STORE1，[B]|〈C〉；//將寄存器1的內容存入B分段的C單元中。

2）信息共享：在實現(xiàn)對程序和數(shù)據(jù)的共享時，是以信息的邏輯單位為基礎的。3）信息保護：分段管理方式能更有效和方便地實現(xiàn)信息保護功能。4）動態(tài)增長：分段存儲管理方式卻能較好地解決數(shù)據(jù)段增長。5）動態(tài)鏈接：運行時，先將主程序所對應的目標程序裝入內存并啟動運行，當運行過程中又需要調用某段時，才將該段調入內存并進行鏈接。它要求以段為單位進行管理。

4.6.2分段系統(tǒng)的基本原理

1．分段在分段存儲管理方式中，作業(yè)的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。每個段都有自己的名字。每個段都從0開始編址，并采用一段連續(xù)的地址空間。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。整個作業(yè)的地址空間，由于是分成多個段，因而是二維的，亦即，其邏輯地址由段號（段名）和段內地址所組成。分段地址中的地址具有如下結構：段號段內地址3116150允許一個作業(yè)最長有64K個段，每個段的最大長度為64KB。2．段表在系統(tǒng)中為每個進程建立一張段映射表，簡稱“段表”。每個段在表中占有一個表項，其中記錄了該段在內存中的起始地址（又稱為“基址”）和段的長度。段表是用于實現(xiàn)從邏輯段到物理內存區(qū)的映射。

X：子程序段D：數(shù)據(jù)段S：棧段3．地址變換機構段號＞段表長度->越界；段內地址>段長->越界像分頁系統(tǒng)一樣，當段表放在內存中時，每要訪問一個數(shù)據(jù)，都須訪問兩次內存，從而極大地降低了計算機的速率。解決的方法增設一個聯(lián)想存儲器，用于保存最近常用的段表項。段比頁大，段表項的數(shù)目比頁表項少，聯(lián)想存儲器也相對較小，便可以顯著地減少存取數(shù)據(jù)的時間比起沒有地址變換的常規(guī)存儲器的存取速度來僅慢約10%～15%4．分頁和分段的主要區(qū)別：（1）頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內存的外零頭，提高內存的利用率。分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要.

段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。（2）頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內地址兩部分，是由機器硬件實現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；段的長度不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據(jù)信息的性質來劃分。

（3）分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址；分段的作業(yè)地址空間是二維的，程序員在標識一個地址時，既需給出段名，又需給出段內地址。4.6.3信息共享分段系統(tǒng)的一個突出優(yōu)點，是易于實現(xiàn)段的共享，即允許若干個進程共享一個或多個分段，且對段的保護也十分簡單易行。在分頁系統(tǒng)中，實現(xiàn)代碼共享應在每個進程的頁表中都建立相同個頁表項和占用相同的頁號。例子有一個多用戶系統(tǒng)，可同時接納40個用戶，他們都執(zhí)行一個文本編輯程序(TextEditor)。如果文本編輯程序有160KB的代碼和另外40KB的數(shù)據(jù)區(qū)，則總共需有8MB的內存空間來支持40個用戶。