計算機操作系統(tǒng) 第四版 湯小丹 課件 第4章

1、1 1第四章 存 儲 器 管 理第四章第四章 存存 儲儲 器器 管管 理理4.1 存儲器的層次結構4.2 程序的裝入和鏈接4.3 連續(xù)分配存儲管理方式4.4 對換(Swapping)4.5 分頁存儲管理方式4.6 分段存儲管理方式習題2 2第四章 存 儲 器 管 理4.1 存儲器的層次結構在計算機執(zhí)行時，幾乎每一條指令都涉及對存儲器的訪問，因此要求對存儲器的訪問速度能跟得上處理機的運行速度?；蛘哒f，存儲器的速度必須非常快，能與處理機的速度相匹配，否則會明顯地影響到處理機的運行。此外還要求存儲器具有非常大的容量，而且存儲器的價格還應很便宜。 3 3第四章 存 儲 器 管 理4.1.1 多層結構的

2、存儲器系統(tǒng)1. 存儲器的多層結構 對于通用計算機而言，存儲層次至少應具有三級：最高層為CPU寄存器，中間為主存，最底層是輔存。在較高檔的計算機中，還可以根據(jù)具體的功能細分為寄存器、高速緩存、主存儲器、磁盤緩存、固定磁盤、可移動存儲介質等6層。如圖4-1所示。 4 4第四章 存 儲 器 管 理圖4-1 計算機系統(tǒng)存儲層次示意5 5第四章 存 儲 器 管 理2. 可執(zhí)行存儲器在計算機系統(tǒng)的存儲層次中，寄存器和主存儲器又被稱為可執(zhí)行存儲器。對于存放于其中的信息，與存放于輔存中的信息相比較而言，計算機所采用的訪問機制是不同的，所需耗費的時間也是不同的。進程可以在很少的時鐘周期內使用一條load或sto

3、re指令對可執(zhí)行存儲器進行訪問。但對輔存的訪問則需要通過I/O設備實現(xiàn)，因此，在訪問中將涉及到中斷、設備驅動程序以及物理設備的運行，所需耗費的時間遠遠高于訪問可執(zhí)行存儲器的時間，一般相差3個數(shù)量級甚至更多。6 6第四章 存 儲 器 管 理4.1.2 主存儲器與寄存器1. 主存儲器主存儲器簡稱內存或主存，是計算機系統(tǒng)中的主要部件，用于保存進程運行時的程序和數(shù)據(jù)，也稱可執(zhí)行存儲器。 7 7第四章 存 儲 器 管 理2. 寄存器寄存器具有與處理機相同的速度，故對寄存器的訪問速度最快，完全能與CPU協(xié)調工作，但價格卻十分昂貴，因此容量不可能做得很大。 8 8第四章 存 儲 器 管 理4.1.3 高速緩

4、存和磁盤緩存1. 高速緩存高速緩存是現(xiàn)代計算機結構中的一個重要部件，它是介于寄存器和存儲器之間的存儲器，主要用于備份主存中較常用的數(shù)據(jù)，以減少處理機對主存儲器的訪問次數(shù)，這樣可大幅度地提高程序執(zhí)行速度。高速緩存容量遠大于寄存器，而比內存約小兩到三個數(shù)量級左右，從幾十KB到幾MB，訪問速度快于主存儲器。 9 9第四章 存 儲 器 管 理2. 磁盤緩存由于目前磁盤的I/O速度遠低于對主存的訪問速度，為了緩和兩者之間在速度上的不匹配，而設置了磁盤緩存，主要用于暫時存放頻繁使用的一部分磁盤數(shù)據(jù)和信息，以減少訪問磁盤的次數(shù)。但磁盤緩存與高速緩存不同，它本身并不是一種實際存在的存儲器，而是利用主存中的部分

5、存儲空間暫時存放從磁盤中讀出(或寫入)的信息。主存也可以看作是輔存的高速緩存，因為，輔存中的數(shù)據(jù)必須復制到主存方能使用，反之，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存。10 10第四章 存 儲 器 管 理4.2 程序的裝入和鏈接用戶程序要在系統(tǒng)中運行，必須先將它裝入內存，然后再將其轉變?yōu)橐粋€可以執(zhí)行的程序，通常都要經過以下幾個步驟：(1) 編譯，由編譯程序(Compiler)對用戶源程序進行編譯，形成若干個目標模塊(Object Module)；(2) 鏈接，由鏈接程序(Linker)將編譯后形成的一組目標模塊以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊(Load Module)；(

6、3) 裝入，由裝入程序(Loader)將裝入模塊裝入內存。圖4-2示出了這樣的三步過程。本節(jié)將扼要闡述程序(含數(shù)據(jù))的鏈接和裝入過程。11 11第四章 存 儲 器 管 理圖4-2對用戶程序的處理步驟12 12第四章 存 儲 器 管 理4.2.1 程序的裝入為了闡述上的方便，我們先介紹一個無需進行鏈接的單個目標模塊的裝入過程。該目標模塊也就是裝入模塊。在將一個裝入模塊裝入內存時，可以有如下三種裝入方式：1. 絕對裝入方式(Absolute Loading Mode)當計算機系統(tǒng)很小，且僅能運行單道程序時，完全有可能知道程序將駐留在內存的什么位置。此時可以采用絕對裝入方式。用戶程序經編譯后，將產生

7、絕對地址(即物理地址)的目標代碼。 13 13第四章 存 儲 器 管 理2. 可重定位裝入方式(Relocation Loading Mode)絕對裝入方式只能將目標模塊裝入到內存中事先指定的位置，這只適用于單道程序環(huán)境。而在多道程序環(huán)境下，編譯程序不可能預知經編譯后所得到的目標模塊應放在內存的何處。因此，對于用戶程序編譯所形成的若干個目標模塊，它們的起始地址通常都是從0開始的，程序中的其它地址也都是相對于起始地址計算的。 14 14第四章 存 儲 器 管 理圖4-3作業(yè)裝入內存時的情況15 15第四章 存 儲 器 管 理3. 動態(tài)運行時的裝入方式(Dynamic Run-time Loadi

8、ng)可重定位裝入方式可將裝入模塊裝入到內存中任何允許的位置，故可用于多道程序環(huán)境。但該方式并不允許程序運行時在內存中移動位置。 16 16第四章 存 儲 器 管 理4.2.2 程序的鏈接1. 靜態(tài)鏈接(Static Linking)方式在程序運行之前，先將各目標模塊及它們所需的庫函數(shù)鏈接成一個完整的裝配模塊，以后不再拆開。在圖4-4(a)中示出了經過編譯后所得到的三個目標模塊A、B、C，它們的長度分別為L、M和N。在模塊A中有一條語句CALL B，用于調用模塊B。在模塊B中有一條語句CALL C，用于調用模塊C。B和C都屬于外部調用符號，在將這幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個

9、問題： (1) 對相對地址進行修改。(2) 變換外部調用符號。 17 17第四章 存 儲 器 管 理圖4-4程序鏈接示意圖18 18第四章 存 儲 器 管 理2. 裝入時動態(tài)鏈接(Load-time Dynamic Linking)這是指將用戶源程序編譯后所得到的一組目標模塊，在裝入內存時，采用邊裝入邊鏈接的鏈接方式。即在裝入一個目標模塊時，若發(fā)生一個外部模塊調用事件，將引起裝入程序去找出相應的外部目標模塊，并將它裝入內存，還要按照圖4-4所示的方式修改目標模塊中的相對地址。裝入時動態(tài)鏈接方式有以下優(yōu)點：(1) 便于修改和更新。(2) 便于實現(xiàn)對目標模塊的共享。 19 19第四章 存 儲 器

10、管 理3. 運行時動態(tài)鏈接(Run-time Dynamic Linking)在許多情況下，應用程序在運行時，每次要運行的模塊可能是不相同的。但由于事先無法知道本次要運行哪些模塊，故只能是將所有可能要運行到的模塊全部都裝入內存，并在裝入時全部鏈接在一起。顯然這是低效的，因為往往會有部分目標模塊根本就不運行。比較典型的例子是作為錯誤處理用的目標模塊，如果程序在整個運行過程中都不出現(xiàn)錯誤，則顯然就不會用到該模塊。2020第四章 存 儲 器 管 理4.3 連續(xù)分配存儲管理方式4.3.1 單一連續(xù)分配在單道程序環(huán)境下，當時的存儲器管理方式是把內存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，它通常

11、是放在內存的低址部分。而在用戶區(qū)內存中，僅裝有一道用戶程序，即整個內存的用戶空間由該程序獨占。這樣的存儲器分配方式被稱為單一連續(xù)分配方式。21 21第四章 存 儲 器 管 理4.3.2 固定分區(qū)分配1. 劃分分區(qū)的方法可用下述兩種方法將內存的用戶空間劃分為若干個固定大小的分區(qū)： (1) 分區(qū)大小相等(指所有的內存分區(qū)大小相等)。(2) 分區(qū)大小不等。2222第四章 存 儲 器 管 理2. 內存分配為了便于內存分配，通常將分區(qū)按其大小進行排隊，并為之建立一張分區(qū)使用表，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)(是否已分配)，如圖4-5所示。 2323第四章 存 儲 器 管 理圖4-5 固定分

12、區(qū)使用表2424第四章 存 儲 器 管 理4.3.3 動態(tài)分區(qū)分配1. 動態(tài)分區(qū)分配中的數(shù)據(jù)結構 常用的數(shù)據(jù)結構有以下兩種形式： 空閑分區(qū)表，在系統(tǒng)中設置一張空閑分區(qū)表，用于記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，表目中包括分區(qū)號、分區(qū)大小和分區(qū)始址等數(shù)據(jù)項，如圖4-6所示。 空閑分區(qū)鏈。為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分設置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針，在分區(qū)尾部則設置一后向指針。通過前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個雙向鏈，如圖4-7所示。 2525第四章 存 儲 器 管 理 圖4-6 空閑分區(qū)表 2626第四章 存 儲

13、 器 管 理 圖4-7 空閑鏈結構 2727第四章 存 儲 器 管 理2. 動態(tài)分區(qū)分配算法為把一個新作業(yè)裝入內存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。由于內存分配算法對系統(tǒng)性能有很大的影響，故人們對它進行了較為廣泛而深入的研究，于是產生了許多動態(tài)分區(qū)分配算法。 2828第四章 存 儲 器 管 理3. 分區(qū)分配操作1) 分配內存系統(tǒng)應利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設請求的分區(qū)大小為u.size，表中每個空閑分區(qū)的大小可表示為m.size。 2929第四章 存 儲 器 管 理圖4-8內存分配流程3030第四章 存 儲 器 管 理2)

14、 回收內存 當進程運行完畢釋放內存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應的插入點，此時可能出現(xiàn)以下四種情況之一： (1) 回收區(qū)與插入點的前一個空閑分區(qū)F1相鄰接，見圖4-9(a)。此時應將回收區(qū)與插入點的前一分區(qū)合并，不必為回收分區(qū)分配新表項，而只需修改其前一分區(qū)F1的大小。(2) 回收分區(qū)與插入點的后一空閑分區(qū)F2相鄰接，見圖4-9(b)。此時也可將兩分區(qū)合并，形成新的空閑分區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。31 31第四章 存 儲 器 管 理(3) 回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接，見圖4-9(c)。此時將三個分區(qū)合并，使用F1的表項和F1的首址

15、，取消F2的表項，大小為三者之和。(4) 回收區(qū)既不與F1鄰接，又不與F2鄰接。這時應為回收區(qū)單獨建立一個新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當位置。圖4-10示出了內存回收時的流程。3232第四章 存 儲 器 管 理圖4-9 內存回收時的情況3333第四章 存 儲 器 管 理圖4-10 內存回收流程3434第四章 存 儲 器 管 理4.3.4 基于順序搜索的動態(tài)分區(qū)分配算法1. 首次適應(first fit，F(xiàn)F)算法我們以空閑分區(qū)鏈為例來說明采用FF算法時的分配情況。FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內存時，從鏈首開始順序查找，直至找到一個大小能滿

16、足要求的空閑分區(qū)為止。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內存空間，分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈首直至鏈尾都不能找到一個能滿足要求的分區(qū)，則表明系統(tǒng)中已沒有足夠大的內存分配給該進程，內存分配失敗，返回。3535第四章 存 儲 器 管 理2. 循環(huán)首次適應(next fit，NF)算法為避免低址部分留下許多很小的空閑分區(qū)，以及減少查找可用空閑分區(qū)的開銷，循環(huán)首次適應算法在為進程分配內存空間時，不再是每次都從鏈首開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直至找到一個能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內存空間分配給作業(yè)。 3636第四章 存

17、 儲 器 管 理3. 最佳適應(best fit，BF)算法所謂“最佳”是指，每次為作業(yè)分配內存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。 3737第四章 存 儲 器 管 理4. 最壞適應(worst fit，WF)算法由于最壞適應分配算法選擇空閑分區(qū)的策略正好與最佳適應算法相反：它在掃描整個空閑分區(qū)表或鏈表時，總是挑選一個最大的空閑區(qū)，從中分割一部分存儲空間給作業(yè)使用，以至于存儲器中缺乏大的空閑分區(qū)，故把它稱為是最壞適應算法。 3838第四章 存 儲 器 管 理4.3.5 基于索引搜

18、索的動態(tài)分區(qū)分配算法1. 快速適應(quick fit)算法該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設立一個空閑分區(qū)鏈表，這樣系統(tǒng)中存在多個空閑分區(qū)鏈表。同時，在內存中設立一張管理索引表，其中的每一個索引表項對應了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。 3939第四章 存 儲 器 管 理2. 伙伴系統(tǒng)(buddy system)該算法規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪(k為整數(shù)，lkm)。通常2m是整個可分配內存的大小(也就是最大分區(qū)的大小)。假設系統(tǒng)的可利用空間容量為2m 個字，則系統(tǒng)開始運行時

19、，整個內存區(qū)是一個大小為2m的空閑分區(qū)。在系統(tǒng)運行過程中，由于不斷地劃分，將會形成若干個不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)按分區(qū)的大小進行分類。對于具有相同大小的所有空閑分區(qū)，單獨設立一個空閑分區(qū)雙向鏈表，這樣，不同大小的空閑分區(qū)形成了k個空閑分區(qū)鏈表。4040第四章 存 儲 器 管 理在伙伴系統(tǒng)中，對于一個大小為2k，地址為x的內存塊，其伙伴塊的地址則用buddyk(x)表示，其通式為：)22 xMOD(若2x0)2xMOD(若2x(x)buddyk1kk1kkk 41 41第四章 存 儲 器 管 理3. 哈希算法在上述的分類搜索算法和伙伴系統(tǒng)算法中，都是將空閑分區(qū)根據(jù)分區(qū)大小進行分類，對于每

20、一類具有相同大小的空閑分區(qū)，單獨設立一個空閑分區(qū)鏈表。在為進程分配空間時，需要在一張管理索引表中查找到所需空間大小所對應的表項，從中得到對應的空閑分區(qū)鏈表表頭指針，從而通過查找得到一個空閑分區(qū)。如果對空閑分區(qū)分類較細，則相應索引表的表項也就較多，因此會顯著地增加搜索索引表的表項的時間開銷。4242第四章 存 儲 器 管 理4.3.6 動態(tài)可重定位分區(qū)分配 1. 緊湊連續(xù)分配方式的一個重要特點是，一個系統(tǒng)或用戶程序必須被裝入一片連續(xù)的內存空間中。當一臺計算機運行了一段時間后，它的內存空間將會被分割成許多小的分區(qū)，而缺乏大的空閑空間。即使這些分散的許多小分區(qū)的容量總和大于要裝入的程序，但由于這些分

21、區(qū)不相鄰接，也無法把該程序裝入內存。 4343第四章 存 儲 器 管 理圖4-11 緊湊的示意4444第四章 存 儲 器 管 理2. 動態(tài)重定位在4.2.1節(jié)中所介紹的動態(tài)運行時裝入的方式中，作業(yè)裝入內存后的所有地址仍然都是相對(邏輯)地址。而將相對地址轉換為絕對(物理)地址的工作被推遲到程序指令要真正執(zhí)行時進行。為使地址的轉換不會影響到指令的執(zhí)行速度，必須有硬件地址變換機構的支持，即須在系統(tǒng)中增設一個重定位寄存器，用它來存放程序(數(shù)據(jù))在內存中的起始地址。程序在執(zhí)行時，真正訪問的內存地址是相對地址與重定位寄存器中的地址相加而形成的。 4545第四章 存 儲 器 管 理圖4-12動態(tài)重定位示意

22、圖4646第四章 存 儲 器 管 理3. 動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本上相同，差別僅在于：在這種分配算法中，增加了緊湊的功能。通常，當該算法不能找到一個足夠大的空閑分區(qū)以滿足用戶需求時，如果所有的小的空閑分區(qū)的容量總和大于用戶的要求，這時便須對內存進行“緊湊”，將經“緊湊”后所得到的大空閑分區(qū)分配給用戶。如果所有的小的空閑分區(qū)的容量總和仍小于用戶的要求，則返回分配失敗信息。 4747第四章 存 儲 器 管 理圖4-13 動態(tài)分區(qū)分配算法流程圖4848第四章 存 儲 器 管 理4.4 對換(Swapping)對換技術也稱為交換技術，最早用于麻省理工學院的單用

23、戶分時系統(tǒng)CTSS中。由于當時計算機的內存都非常小，為了使該系統(tǒng)能分時運行多個用戶程序而引入了對換技術。系統(tǒng)把所有的用戶作業(yè)存放在磁盤上，每次只能調入一個作業(yè)進入內存，當該作業(yè)的一個時間片用完時，將它調至外存的后備隊列上等待，再從后備隊列上將另一個作業(yè)調入內存。這就是最早出現(xiàn)的分時系統(tǒng)中所用的對換技術。現(xiàn)在已經很少使用。4949第四章 存 儲 器 管 理4.4.1 多道程序環(huán)境下的對換技術1. 對換的引入在多道程序環(huán)境下，一方面，在內存中的某些進程由于某事件尚未發(fā)生而被阻塞運行，但它卻占用了大量的內存空間，甚至有時可能出現(xiàn)在內存中所有進程都被阻塞，而無可運行之進程，迫使CPU停止下來等待的情況

24、；另一方面，卻又有著許多作業(yè)，因內存空間不足，一直駐留在外存上，而不能進入內存運行。顯然這對系統(tǒng)資源是一種嚴重的浪費，且使系統(tǒng)吞吐量下降。 5050第四章 存 儲 器 管 理2. 對換的類型在每次對換時，都是將一定數(shù)量的程序或數(shù)據(jù)換入或換出內存。根據(jù)每次對換時所對換的數(shù)量，可將對換分為如下兩類：(1) 整體對換。(2) 頁面(分段)對換。 51 51第四章 存 儲 器 管 理4.4.2 對換空間的管理 1. 對換空間管理的主要目標在具有對換功能的OS中，通常把磁盤空間分為文件區(qū)和對換區(qū)兩部分。1) 對文件區(qū)管理的主要目標2) 對對換空間管理的主要目標5252第四章 存 儲 器 管 理2. 對換

25、區(qū)空閑盤塊管理中的數(shù)據(jù)結構為了實現(xiàn)對對換區(qū)中的空閑盤塊的管理，在系統(tǒng)中應配置相應的數(shù)據(jù)結構，用于記錄外存對換區(qū)中的空閑盤塊的使用情況。其數(shù)據(jù)結構的形式與內存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結構相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表的每個表目中，應包含兩項：對換區(qū)的首址及其大小，分別用盤塊號和盤塊數(shù)表示。5353第四章 存 儲 器 管 理3. 對換空間的分配與回收由于對換分區(qū)的分配采用的是連續(xù)分配方式，因而對換空間的分配與回收與動態(tài)分區(qū)方式時的內存分配與回收方法雷同。其分配算法可以是首次適應算法、循環(huán)首次適應算法或最佳適應算法等。具體的分配操作也與圖4-8中內存的分配過程相同。 54

26、54第四章 存 儲 器 管 理4.4.3 進程的換出與換入1. 進程的換出對換進程在實現(xiàn)進程換出時，是將內存中的某些進程調出至對換區(qū)，以便騰出內存空間。換出過程可分為以下兩步：(1) 選擇被換出的進程。(2) 進程換出過程。 5555第四章 存 儲 器 管 理2. 進程的換入對換進程將定時執(zhí)行換入操作，它首先查看PCB集合中所有進程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進程。當有許多這樣的進程時，它將選擇其中已換出到磁盤上時間最久(必須大于規(guī)定時間，如2s)的進程作為換入進程，為它申請內存。如果申請成功，可直接將進程從外存調入內存；如果失敗，則需先將內存中的某些進程換出，騰出足夠的內存空間后，

27、再將進程調入。5656第四章 存 儲 器 管 理4.5 分頁存儲管理方式(1) 分頁存儲管理方式。(2) 分段存儲管理方式。(3) 段頁式存儲管理方式。 5757第四章 存 儲 器 管 理4.5.1 分頁存儲管理的基本方法1. 頁面和物理塊(1) 頁面。(2) 頁面大小。 5858第四章 存 儲 器 管 理2. 地址結構分頁地址中的地址結構如下：5959第四章 存 儲 器 管 理對某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內地址d可按下式求得：6060第四章 存 儲 器 管 理3. 頁表在分頁系統(tǒng)中，允許將進程的各個頁離散地存儲在內存的任一

28、物理塊中，為保證進程仍然能夠正確地運行，即能在內存中找到每個頁面所對應的物理塊，系統(tǒng)又為每個進程建立了一張頁面映像表，簡稱頁表。 61 61第四章 存 儲 器 管 理圖4-14 頁表的作用6262第四章 存 儲 器 管 理4.5.2 地址變換機構1. 基本的地址變換機構進程在運行期間，需要對程序和數(shù)據(jù)的地址進行變換，即將用戶地址空間中的邏輯地址變換為內存空間中的物理地址，由于它執(zhí)行的頻率非常高，每條指令的地址都需要進行變換，因此需要采用硬件來實現(xiàn)。頁表功能是由一組專門的寄存器來實現(xiàn)的。一個頁表項用一個寄存器。 6363第四章 存 儲 器 管 理圖4-15 分頁系統(tǒng)的地址變換機構6464第四章

29、存 儲 器 管 理2. 具有快表的地址變換機構由于頁表是存放在內存中的，這使CPU在每存取一個數(shù)據(jù)時，都要兩次訪問內存。第一次是訪問內存中的頁表，從中找到指定頁的物理塊號，再將塊號與頁內偏移量W拼接，以形成物理地址。第二次訪問內存時，才是從第一次所得地址中獲得所需數(shù)據(jù)(或向此地址中寫入數(shù)據(jù))。因此，采用這種方式將使計算機的處理速度降低近1/2。可見，以此高昂代價來換取存儲器空間利用率的提高，是得不償失的。6565第四章 存 儲 器 管 理圖4-16 具有快表的地址變換機構6666第四章 存 儲 器 管 理4.5.3 訪問內存的有效時間從進程發(fā)出指定邏輯地址的訪問請求，經過地址變換，到在內存中找

30、到對應的實際物理地址單元并取出數(shù)據(jù)，所需要花費的總時間，稱為內存的有效訪問時間(Effective Access Time，EAT)。假設訪問一次內存的時間為t，在基本分頁存儲管理方式中，有效訪問時間分為第一次訪問內存時間(即查找頁表對應的頁表項所耗費的時間t)與第二次訪問內存時間(即將頁表項中的物理塊號與頁內地址拼接成實際物理地址所耗費的時間t)之和：EAT=t+t=2t6767第四章 存 儲 器 管 理在引入快表的分頁存儲管理方式中，通過快表查詢，可以直接得到邏輯頁所對應的物理塊號，由此拼接形成實際物理地址，減少了一次內存訪問，縮短了進程訪問內存的有效時間。但是，由于快表的容量限制，不可能

31、將一個進程的整個頁表全部裝入快表，所以在快表中查找到所需表項存在著命中率的問題。所謂命中率，是指使用快表并在其中成功查找到所需頁面的表項的比率。這樣，在引入快表的分頁存儲管理方式中，有效訪問時間的計算公式即為： EAT=+(t+)(1)+t=2t+t上式中，表示查找快表所需要的時間，表示命中率，t表示訪問一次內存所需要的時間。6868第四章 存 儲 器 管 理可見，引入快表后的內存有效訪問時間分為查找到邏輯頁對應的頁表項的平均時間+(t+)(1-)，以及對應實際物理地址的內存訪問時間t。假設對快表的訪問時間為20ns(納秒)，對內存的訪問時間t為100ns，則下表中列出了不同的命中率與有效訪問

32、時間的關系：6969第四章 存 儲 器 管 理4.5.4 兩級和多級頁表1. 兩級頁表(Two-Level Page Table)針對難于找到大的連續(xù)的內存空間來存放頁表的問題，可利用將頁表進行分頁的方法，使每個頁面的大小與內存物理塊的大小相同，并為它們進行編號，即依次為0#頁、1#頁，n#頁，然后離散地將各個頁面分別存放在不同的物理塊中。同樣，也要為離散分配的頁表再建立一張頁表，稱為外層頁表(Outer Page Table)，在每個頁表項中記錄了頁表頁面的物理塊號。 7070第四章 存 儲 器 管 理圖4-17兩級頁表結構71 71第四章 存 儲 器 管 理為了方便實現(xiàn)地址變換，在地址變換

33、機構中，同樣需要增設一個外層頁表寄存器，用于存放外層頁表的始址，并利用邏輯地址中的外層頁號作為外層頁表的索引，從中找到指定頁表分頁的始址，再利用P2作為指定頁表分頁的索引，找到指定的頁表項，其中即含有該頁在內存的物理塊號，用該塊號P和頁內地址d即可構成訪問的內存物理地址。圖4-18示出了兩級頁表時的地址變換機構。7272第四章 存 儲 器 管 理圖4-18具有兩級頁表的地址變換機構7373第四章 存 儲 器 管 理2. 多級頁表對于32位的機器，采用兩級頁表結構是合適的，但對于64位的機器，采用兩級頁表是否仍然合適，須做以下簡單分析。如果頁面大小仍采用4 KB即212 B，那么還剩下52位，假

34、定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，要占用16384 GB的連續(xù)內存空間。 7474第四章 存 儲 器 管 理4.5.5 反置頁表(Inverted Page Table)1. 反置頁表的引入在分頁系統(tǒng)中，為每個進程配置了一張頁表，進程邏輯地址空間中的每一頁，在頁表中都對應有一個頁表項。在現(xiàn)代計算機系統(tǒng)中，通常允許一個進程的邏輯地址空間非常大，因此就需要有許多的頁表項，而因此也會占用大量的內存空間。 7575第四章 存 儲 器 管 理2. 地址變換在利用反置頁表進行地址變換時，是根據(jù)進程標識符和頁號，去檢索反置頁表。

35、如果檢索到與之匹配的頁表項，則該頁表項(中)的序號i便是該頁所在的物理塊號，可用該塊號與頁內地址一起構成物理地址送內存地址寄存器。若檢索了整個反置頁表仍未找到匹配的頁表項，則表明此頁尚未裝入內存。對于不具有請求調頁功能的存儲器管理系統(tǒng)，此時則表示地址出錯。對于具有請求調頁功能的存儲器管理系統(tǒng)，此時應產生請求調頁中斷，系統(tǒng)將把此頁調入內存。7676第四章 存 儲 器 管 理4.6 分段存儲管理方式存儲管理方式隨著OS的發(fā)展也在不斷地發(fā)展。當OS由單道向多道發(fā)展時，存儲管理方式便由單一連續(xù)分配發(fā)展為固定分區(qū)分配。 7777第四章 存 儲 器 管 理4.6.1 分段存儲管理方式的引入1. 方便編程通

36、常，用戶把自己的作業(yè)按照邏輯關系劃分為若干個段，每個段都從0開始編址，并有自己的名字和長度。因此，程序員們都迫切地需要訪問的邏輯地址是由段名(段號)和段內偏移量(段內地址)決定的，這不僅可以方便程序員編程，也可使程序非常直觀，更具可讀性。例如，下述的兩條指令便使用段名和段內地址： LOAD 1，A |D； STORE 1，B |C；7878第四章 存 儲 器 管 理2. 信息共享在實現(xiàn)對程序和數(shù)據(jù)的共享時，是以信息的邏輯單位為基礎的。比如，為了共享某個過程、函數(shù)或文件。分頁系統(tǒng)中的“頁”只是存放信息的物理單位(塊)，并無完整的邏輯意義，這樣，一個可被共享的過程往往可能需要占用數(shù)十個頁面，這為實

37、現(xiàn)共享增加了困難。 7979第四章 存 儲 器 管 理3. 信息保護信息保護同樣是以信息的邏輯單位為基礎的，而且經常是以一個過程、函數(shù)或文件為基本單位進行保護的。 8080第四章 存 儲 器 管 理4. 動態(tài)增長 在實際應用中，往往存在著一些段，尤其是數(shù)據(jù)段，在它們的使用過程中，由于數(shù)據(jù)量的不斷增加，而使數(shù)據(jù)段動態(tài)增長，相應地它所需要的存儲空間也會動態(tài)增加。然而，對于數(shù)據(jù)段究竟會增長到多大，事先又很難確切地知道。對此，很難采取預先多分配的方法進行解決。 81 81第四章 存 儲 器 管 理5. 動態(tài)鏈接在4.2.2節(jié)中我們已對運行時動態(tài)鏈接做了介紹。為了提高內存的利用率，系統(tǒng)只將真正要運行的目

38、標程序裝入內存，也就是說，動態(tài)鏈接在作業(yè)運行之前，并不是把所有的目標程序段都鏈接起來。當程序要運行時，首先將主程序和它立即需要用到的目標程序裝入內存，即啟動運行。而在程序運行過程中，當需要調用某個目標程序時，才將該段(目標程序)調入內存并進行鏈接。 8282第四章 存 儲 器 管 理4.6.2 分段系統(tǒng)的基本原理 1. 分段在分段存儲管理方式中，作業(yè)的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。例如，有主程序段MAIN、子程序段X、數(shù)據(jù)段D及棧段S等，如圖4-19所示。 分段地址中的地址具有如下結構：8383第四章 存 儲 器 管 理2. 段表在前面所介紹的動態(tài)分區(qū)分配方式中，系統(tǒng)為整

39、個進程分配一個連續(xù)的內存空間。而在分段式存儲管理系統(tǒng)中，則是為每個分段分配一個連續(xù)的分區(qū)。進程中的各個段，可以離散地裝入內存中不同的分區(qū)中。為保證程序能正常運行，就必須能從物理內存中找出每個邏輯段所對應的位置。 8484第四章 存 儲 器 管 理圖4-19 利用段表實現(xiàn)地址映射8585第四章 存 儲 器 管 理3. 地址變換機構為了實現(xiàn)進程從邏輯地址到物理地址的變換功能，在系統(tǒng)中設置了段表寄存器，用于存放段表始址和段表長度TL。在進行地址變換時，系統(tǒng)將邏輯地址中的段號與段表長度TL進行比較。若STL，表示段號太大，是訪問越界，于是產生越界中斷信號。若未越界，則根據(jù)段表的始址和該段的段號，計算出

40、該段對應段表項的位置，從中讀出該段在內存的起始地址。然后，再檢查段內地址d是否超過該段的段長SL。若超過，即dSL，同樣發(fā)出越界中斷信號。若未越界，則將該段的基址d與段內地址相加，即可得到要訪問的內存物理地址。圖4-20示出了分段系統(tǒng)的地址變換過程。8686第四章 存 儲 器 管 理圖4-20 分段系統(tǒng)的地址變換過程8787第四章 存 儲 器 管 理4. 分頁和分段的主要區(qū)別(1) 頁是信息的物理單位。(2) 頁的大小固定且由系統(tǒng)決定。(3) 分頁的用戶程序地址空間是一維的。 8888第四章 存 儲 器 管 理4.6.3 信息共享1. 分頁系統(tǒng)中對程序和數(shù)據(jù)的共享在分頁系統(tǒng)中，雖然也能實現(xiàn)對程

41、序和數(shù)據(jù)的共享，但遠不如分段系統(tǒng)來得方便。我們通過一個例子來說明這個問題。 8989第四章 存 儲 器 管 理圖4-21 分頁系統(tǒng)中共享editor的示意圖9090第四章 存 儲 器 管 理2. 分段系統(tǒng)中程序和數(shù)據(jù)的共享在分段系統(tǒng)中，由于是以段為基本單位的，不管該段有多大，我們都只需為該段設置一個段表項，因此使實現(xiàn)共享變得非常容易。我們仍以共享editor為例，此時只需在(每個)進程1和進程2的段表中，為文本編輯程序設置一個段表項，讓段表項中的基址(80)指向editor程序在內存的起始地址。圖4-22是分段系統(tǒng)中共享editor的示意圖。91 91第四章 存 儲 器 管 理圖4-22 分段系統(tǒng)中共享editor的示意圖9292第四章 存 儲 器 管 理4.6.4 段頁式存儲管理方式1. 基本原理段頁式系統(tǒng)的基本原理是分段和分頁原理的結合，即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。圖4-23(a)示出了一個作業(yè)地址空間的結構。該作業(yè)有三個段：主程序段、子程序段和數(shù)據(jù)段；頁面大小為 4