蒲曉蓉-操作系統(tǒng)原理第3章全-存儲管理

1、內(nèi)存內(nèi)存OS 圖圖3.1 3.1 進程執(zhí)行時的尋址進程執(zhí)行時的尋址當前棧頂當前棧頂進程控制信息進程控制信息程序入口點程序入口點地址值增加地址值增加進程控制塊進程控制塊程序程序棧棧數(shù)據(jù)數(shù)據(jù)訪問數(shù)據(jù)訪問數(shù)據(jù)分支指令分支指令進程映像進程映像 CPUCPU地址管理部件地址管理部件程序指令程序指令物理地址物理地址地址總線地址總線邏輯地址邏輯地址圖圖3.2 CPU3.2 CPU中的地址管理部件工作示意圖中的地址管理部件工作示意圖PCB3 數(shù)據(jù)數(shù)據(jù)代碼代碼PCB2 代碼代碼數(shù)據(jù)數(shù)據(jù)PCB1數(shù)據(jù)數(shù)據(jù)代碼代碼 進程進程1進程進程2進程進程3圖圖3.3 進程之間共享代碼和數(shù)據(jù)進程之間共享代碼和數(shù)據(jù) 8MB8MB8

2、MB8MB8MB操作系統(tǒng)操作系統(tǒng)8MB(a)等長分區(qū)等長分區(qū)圖圖3.4 固定分區(qū)劃分固定分區(qū)劃分操作系統(tǒng)操作系統(tǒng)8MB2MB8MB4MB12MB20MB(b)異長分區(qū)異長分區(qū)圖圖3.4 固定分區(qū)劃分固定分區(qū)劃分 (FFA：First Fit Algorithm)(FFA：First Fit Algorithm)(FFA：First Fit Algorithm)圖圖3.8 利用緊湊技術消除外零頭利用緊湊技術消除外零頭(a) 緊湊之前緊湊之前24MB10MBOS 8MBP7 16MBP2 10MBP4 10MBP6 10MB20MB10MB(b)緊湊以后緊湊以后64MBOS 8MBP7 16MBP

3、2 10MBP4 10MBP6 10MB(NFA: Next-Fit Algorithm) (NFA: Next-Fit Algorithm)(BFA：Best Fit Algorithm) (BFA：Best Fit Algorithm) (WFA：Worst Fit Algorithm)(WFA：Worst Fit Algorithm)(Buddy System) P1 申請申請100KBP2 申請申請200KBP3 申請申請120KBP4 申請申請300KB系統(tǒng)初始狀態(tài)系統(tǒng)初始狀態(tài)P2、P3結束結束P5 申請申請160KBP1執(zhí)行結束執(zhí)行結束P5執(zhí)行結束執(zhí)行結束P4執(zhí)行結束執(zhí)行結束1MB

4、 P1 128KB 256KB 512KB P1 128KB P2 512KB P1 P3 P2 512KB P1 P3 P2 P4 P1 128KB 256KB P4 P1 128KB P5 P4 256KB P5 P4512KB P41MB圖圖3.9 一個伙伴系統(tǒng)的內(nèi)存分配與回收過程一個伙伴系統(tǒng)的內(nèi)存分配與回收過程3.3 程序裝入技術程序裝入技術 可執(zhí)行程序的生成步驟可執(zhí)行程序的生成步驟圖圖3.10 高級程序處理過程高級程序處理過程源程序源程序目標模塊目標模塊編譯編譯庫函數(shù)庫函數(shù)裝入模塊裝入模塊鏈接鏈接編輯編輯執(zhí)行執(zhí)行目標模塊目標模塊內(nèi)存內(nèi)存可執(zhí)行程序的裝入可執(zhí)行程序的裝入 ？如何裝入待執(zhí)

5、行的程序及其所需的數(shù)據(jù)？如何裝入待執(zhí)行的程序及其所需的數(shù)據(jù) ？ 何時將程序的邏輯地址轉換為物理地址何時將程序的邏輯地址轉換為物理地址 3種裝入方式：絕對裝入、重定位裝入和運行種裝入方式：絕對裝入、重定位裝入和運行時動態(tài)裝入。時動態(tài)裝入。 絕對裝入絕對裝入 程序運行之前，按照程序的邏輯地址，程序運行之前，按照程序的邏輯地址，將程序和數(shù)據(jù)裝入內(nèi)存指定的地方。將程序和數(shù)據(jù)裝入內(nèi)存指定的地方。 實現(xiàn)簡單，無須進行邏輯地址到物理地實現(xiàn)簡單，無須進行邏輯地址到物理地址的變換。址的變換。絕對裝入絕對裝入缺點：缺點： 程序每次必須裝入同一內(nèi)存區(qū)；程序每次必須裝入同一內(nèi)存區(qū)； 程序員必須事先了解內(nèi)存的使用情況，

6、根據(jù)內(nèi)程序員必須事先了解內(nèi)存的使用情況，根據(jù)內(nèi)存情況確定程序的邏輯地址；存情況確定程序的邏輯地址； 程序的修改（增加或刪除指令）將引起整個程程序的修改（增加或刪除指令）將引起整個程序中指令地址的變動；序中指令地址的變動； 程序中的所有存儲引用，例如函數(shù)調(diào)用或過程程序中的所有存儲引用，例如函數(shù)調(diào)用或過程調(diào)用等，在裝入之前都必須轉換為物理地址，調(diào)用等，在裝入之前都必須轉換為物理地址，這不利于存儲共享。這不利于存儲共享。重定位裝入重定位裝入 允許將程序裝入與邏輯地址不同的物理允許將程序裝入與邏輯地址不同的物理內(nèi)存空間。即程序可以裝入到內(nèi)存的任內(nèi)存空間。即程序可以裝入到內(nèi)存的任何位置，其邏輯地址與裝入

7、內(nèi)存后的物何位置，其邏輯地址與裝入內(nèi)存后的物理地址無直接關系。理地址無直接關系。 但是，必須進行地址映射，將邏輯地址但是，必須進行地址映射，將邏輯地址轉換為物理地址。轉換為物理地址。 靜態(tài)重定位技術靜態(tài)重定位技術：地址映射在程序裝入：地址映射在程序裝入時進行，以后不再更改程序地址。時進行，以后不再更改程序地址。重定位裝入重定位裝入 有利于程序代碼和數(shù)據(jù)的共享。因為裝入程序有利于程序代碼和數(shù)據(jù)的共享。因為裝入程序時，可以將其中的某些存儲引用的邏輯地址映時，可以將其中的某些存儲引用的邏輯地址映射為內(nèi)存中已有的共享區(qū)的物理地址。射為內(nèi)存中已有的共享區(qū)的物理地址。 但是，靜態(tài)重定位不允許程序在內(nèi)存中移

8、動。但是，靜態(tài)重定位不允許程序在內(nèi)存中移動。這不便于進程交換和緊湊拼接操作，也很難實這不便于進程交換和緊湊拼接操作，也很難實現(xiàn)多道程序環(huán)境下，多個程序同時裝入內(nèi)存的現(xiàn)多道程序環(huán)境下，多個程序同時裝入內(nèi)存的要求。要求。 故，重定位裝入方式只適合于單道程序環(huán)境。故，重定位裝入方式只適合于單道程序環(huán)境。運行時動態(tài)裝入運行時動態(tài)裝入 指，程序的地址轉換不是在裝入時進行，而是指，程序的地址轉換不是在裝入時進行，而是在程序運行時動態(tài)進行。在程序運行時動態(tài)進行。 運行時動態(tài)裝入需要硬件支持，即重定位寄存運行時動態(tài)裝入需要硬件支持，即重定位寄存器，用于保存程序在內(nèi)存中的起始地址。器，用于保存程序在內(nèi)存中的起始

9、地址。 程序被執(zhí)行時，通過重定位寄存器內(nèi)的起始物程序被執(zhí)行時，通過重定位寄存器內(nèi)的起始物理地址和指令或數(shù)據(jù)的邏輯地址計算其物理地理地址和指令或數(shù)據(jù)的邏輯地址計算其物理地址。址。 運行時動態(tài)裝入有利于多道程序環(huán)境下，進程運行時動態(tài)裝入有利于多道程序環(huán)境下，進程的換進的換進/換出及實現(xiàn)緊湊技術。換出及實現(xiàn)緊湊技術。 可執(zhí)行程序的鏈接形成可執(zhí)行程序的鏈接形成 ？ 目標模塊如何鏈接成裝入模塊呢目標模塊如何鏈接成裝入模塊呢 靜態(tài)鏈接靜態(tài)鏈接 動態(tài)鏈接動態(tài)鏈接：裝入時動態(tài)鏈接和運行時動：裝入時動態(tài)鏈接和運行時動態(tài)鏈接態(tài)鏈接 靜態(tài)鏈接靜態(tài)鏈接 指，程序被裝入內(nèi)存之前，必須完全鏈接成一指，程序被裝入內(nèi)存之前，

10、必須完全鏈接成一個裝入模塊，將其中的存儲引用全部轉換為相個裝入模塊，將其中的存儲引用全部轉換為相對地址跳轉語句。并將多個目標模塊鏈接成為對地址跳轉語句。并將多個目標模塊鏈接成為一個模塊，使裝入模塊中的每一條指令具有相一個模塊，使裝入模塊中的每一條指令具有相對于整個模塊的第一條語句的邏輯地址。對于整個模塊的第一條語句的邏輯地址。 靜態(tài)鏈接生成的裝入模塊可以采用重定位裝入靜態(tài)鏈接生成的裝入模塊可以采用重定位裝入或運行時動態(tài)裝入方式?；蜻\行時動態(tài)裝入方式。 靜態(tài)鏈接需要花費大量的處理機時間。而其中靜態(tài)鏈接需要花費大量的處理機時間。而其中的很多模塊將不會運行，浪費存儲空間和處理的很多模塊將不會運行，浪

11、費存儲空間和處理機時間。機時間。 鏈接鏈接圖圖3.11 目標模塊鏈接成裝入模塊目標模塊鏈接成裝入模塊模塊模塊1if x 1 thencall mm1elsecall mm2模塊模塊mm1模塊模塊mm2(a) 目標模目標模塊塊模塊模塊1if x 1 thenelse模塊模塊mm1模塊模塊mm2(b) 裝入模裝入模塊塊？執(zhí)行？執(zhí)行？執(zhí)行？執(zhí)行動態(tài)鏈接動態(tài)鏈接 指，不用事先鏈接所有目標模塊形成一指，不用事先鏈接所有目標模塊形成一個完備的裝入模塊，而是生成一個含有個完備的裝入模塊，而是生成一個含有未被鏈接的外部模塊引用的裝入模塊，未被鏈接的外部模塊引用的裝入模塊，這些外部模塊可以在裝入時鏈接，或運這些

12、外部模塊可以在裝入時鏈接，或運行時鏈接。行時鏈接。裝入時動態(tài)鏈接裝入時動態(tài)鏈接 指，當系統(tǒng)裝入含有未鏈接的外部模塊引用的指，當系統(tǒng)裝入含有未鏈接的外部模塊引用的裝入模塊時，每當遇到一個外部模塊引用，則裝入模塊時，每當遇到一個外部模塊引用，則查找相應的目標模塊。將其裝入內(nèi)存，并將模查找相應的目標模塊。將其裝入內(nèi)存，并將模塊內(nèi)的指令地址轉換為相對于整個裝入模塊起塊內(nèi)的指令地址轉換為相對于整個裝入模塊起始地址的相對地址。始地址的相對地址。 優(yōu)點：有利于目標模塊的更新與升級；有利于優(yōu)點：有利于目標模塊的更新與升級；有利于代碼共享；有利于擴充軟件的功能，可以將擴代碼共享；有利于擴充軟件的功能，可以將擴充

13、部分作為動態(tài)鏈接模塊。充部分作為動態(tài)鏈接模塊。 但是，可能鏈接一些不會執(zhí)行的模塊，浪費存但是，可能鏈接一些不會執(zhí)行的模塊，浪費存儲空間和處理機時間。儲空間和處理機時間。運行時動態(tài)鏈接運行時動態(tài)鏈接 指，外部模塊引用直至程序執(zhí)行時才裝入內(nèi)存，指，外部模塊引用直至程序執(zhí)行時才裝入內(nèi)存，并鏈接到裝入模塊中，進行地址轉換。并鏈接到裝入模塊中，進行地址轉換。 可以解決靜態(tài)鏈接和裝入時動態(tài)鏈接都面臨的可以解決靜態(tài)鏈接和裝入時動態(tài)鏈接都面臨的存儲空間和處理機時間浪費問題，不需要執(zhí)行存儲空間和處理機時間浪費問題，不需要執(zhí)行的模塊就不會裝入內(nèi)存。的模塊就不會裝入內(nèi)存。 廣泛用于事務處理系統(tǒng)，如航空售票系統(tǒng)、銀廣

14、泛用于事務處理系統(tǒng)，如航空售票系統(tǒng)、銀行管理系統(tǒng)等。行管理系統(tǒng)等。 操作系統(tǒng)自身的一些特殊處理例程，如錯誤處操作系統(tǒng)自身的一些特殊處理例程，如錯誤處理例程，也無需事先全部裝入內(nèi)存。理例程，也無需事先全部裝入內(nèi)存。3.4 簡單存儲管理技術簡單存儲管理技術 簡單存儲簡單存儲 相對于虛擬存儲而言，指為了實現(xiàn)簡單，執(zhí)行相對于虛擬存儲而言，指為了實現(xiàn)簡單，執(zhí)行之前，操作系統(tǒng)必須將待執(zhí)行的程序全部裝入之前，操作系統(tǒng)必須將待執(zhí)行的程序全部裝入內(nèi)存。內(nèi)存。 然而，現(xiàn)代操作系統(tǒng)大都支持虛擬存儲功能，然而，現(xiàn)代操作系統(tǒng)大都支持虛擬存儲功能，允許進程裝入部分程序即可開始執(zhí)行，其余部允許進程裝入部分程序即可開始執(zhí)行，

15、其余部分保留在外存。當執(zhí)行所需的部分不在內(nèi)存時，分保留在外存。當執(zhí)行所需的部分不在內(nèi)存時，中斷進程執(zhí)行，使之阻塞等待，直到相應部分中斷進程執(zhí)行，使之阻塞等待，直到相應部分裝入內(nèi)存。裝入內(nèi)存。？ 程序在內(nèi)存中如何組織程序在內(nèi)存中如何組織 連續(xù)存儲連續(xù)存儲 : 需要內(nèi)存中的一塊連續(xù)的、需要內(nèi)存中的一塊連續(xù)的、足夠大的分區(qū)。足夠大的分區(qū)。 如果內(nèi)存中沒有足夠大的連續(xù)空閑分區(qū)，如果內(nèi)存中沒有足夠大的連續(xù)空閑分區(qū)，但存在總量足夠的獨立小分區(qū)，即但存在總量足夠的獨立小分區(qū)，即外零外零頭頭。系統(tǒng)要么拒絕分配空間，要么采用。系統(tǒng)要么拒絕分配空間，要么采用緊湊技術緊湊技術拼接外零頭。拼接外零頭。 非連續(xù)存儲非連

16、續(xù)存儲：允許進程的程序和數(shù)據(jù)分：允許進程的程序和數(shù)據(jù)分別裝在內(nèi)存的不同分區(qū)中。別裝在內(nèi)存的不同分區(qū)中。 必須登記一個進程分到的所有分區(qū)的位必須登記一個進程分到的所有分區(qū)的位置、大小、使用情況（如是否共享等）置、大小、使用情況（如是否共享等）等信息。等信息。 常用的非連續(xù)存儲技術：分頁存儲技術、常用的非連續(xù)存儲技術：分頁存儲技術、分段存儲技術及其結合。分段存儲技術及其結合。圖圖3.12 內(nèi)存的連續(xù)存儲與非連續(xù)存儲內(nèi)存的連續(xù)存儲與非連續(xù)存儲OS進程進程P基地址基地址(a)連續(xù)存儲連續(xù)存儲進程進程P（2）OS進程進程P（1）進程進程P（n）進程的組成進程的組成基地址基地址長度長度P(1)260420

17、0P(2)1240300P(n)6500300(b)非連續(xù)存儲非連續(xù)存儲連續(xù)存儲管理連續(xù)存儲管理 最簡單的存儲管理技術最簡單的存儲管理技術 要求系統(tǒng)配置專門的硬件實現(xiàn)快速地址要求系統(tǒng)配置專門的硬件實現(xiàn)快速地址轉換和存儲保護。轉換和存儲保護。 處理機硬件處理機硬件 基址寄存器基址寄存器(Base register) 界限寄存器界限寄存器(Bounds register)連續(xù)存儲管理連續(xù)存儲管理 基址寄存器基址寄存器：存放當前執(zhí)行進程所在分區(qū)的物：存放當前執(zhí)行進程所在分區(qū)的物理存儲單元的起始地址。理存儲單元的起始地址。 界限寄存器界限寄存器：存放當前執(zhí)行進程所在分區(qū)最后：存放當前執(zhí)行進程所在分區(qū)最

18、后一個物理存儲單元的地址，限定進程的執(zhí)行范一個物理存儲單元的地址，限定進程的執(zhí)行范圍，保護其他進程不被非法訪問。圍，保護其他進程不被非法訪問。 基址寄存器和界限寄存器被多個進程共享，只基址寄存器和界限寄存器被多個進程共享，只有當前執(zhí)行進程才使用它們。有當前執(zhí)行進程才使用它們。 裝入時，進程分區(qū)的基地址值和分區(qū)的最后一裝入時，進程分區(qū)的基地址值和分區(qū)的最后一個物理存儲單元的地址值，分別填入該進程個物理存儲單元的地址值，分別填入該進程PCB的相應字段中。的相應字段中。 當進程被調(diào)度執(zhí)行時，將當進程被調(diào)度執(zhí)行時，將PCB中對應的進程基中對應的進程基地址值寫入基址寄存器中，并將進程獲得的內(nèi)地址值寫入基

19、址寄存器中，并將進程獲得的內(nèi)存分區(qū)最大地址值，填入界限寄存器中。存分區(qū)最大地址值，填入界限寄存器中。 當進程被交換出當進程被交換出/換入內(nèi)存時，上述兩個地址換入內(nèi)存時，上述兩個地址值也會發(fā)生改變。值也會發(fā)生改變。 地址映射與存儲保護地址映射與存儲保護 邏輯地址轉換成物理地址邏輯地址轉換成物理地址 取基址寄存器中的值，加上邏輯地址值，生取基址寄存器中的值，加上邏輯地址值，生成一個物理地址成一個物理地址 地址越界檢查地址越界檢查 取界限寄存器中的值，與第一步計算的結果取界限寄存器中的值，與第一步計算的結果進行比較。如果生成的物理地址超出了界限范進行比較。如果生成的物理地址超出了界限范圍，產(chǎn)生一個中

20、斷，報告地址越界。否則，繼圍，產(chǎn)生一個中斷，報告地址越界。否則，繼續(xù)該指令的執(zhí)行。續(xù)該指令的執(zhí)行。程序部分程序部分數(shù)據(jù)部分數(shù)據(jù)部分內(nèi)存內(nèi)存基址寄存器基址寄存器加法器加法器邏輯地址邏輯地址界限寄存器界限寄存器比較器比較器越界中斷越界中斷物理地址物理地址圖圖3.13 連續(xù)存儲管理的地址轉換和越界檢查連續(xù)存儲管理的地址轉換和越界檢查 簡單分頁存儲管理簡單分頁存儲管理 連續(xù)存儲：存在外零頭，浪費存儲空間。連續(xù)存儲：存在外零頭，浪費存儲空間?！熬o湊緊湊”需要系統(tǒng)額外開銷。需要系統(tǒng)額外開銷。 非連續(xù)存儲：允許將一個進程的程序和非連續(xù)存儲：允許將一個進程的程序和數(shù)據(jù)離散存儲在多個獨立的分區(qū)中，消數(shù)據(jù)離散存儲

21、在多個獨立的分區(qū)中，消除了外零頭。除了外零頭。 基本原理基本原理 分頁存儲管理技術是一種特殊的固定分分頁存儲管理技術是一種特殊的固定分區(qū)方法。區(qū)方法。 系統(tǒng)事先將物理內(nèi)存劃分成許多尺寸相系統(tǒng)事先將物理內(nèi)存劃分成許多尺寸相等的等的頁框頁框 (Page Frame)，并將進程分，并將進程分割成許多大小相同的割成許多大小相同的頁面頁面 (Page)，頁面，頁面與頁框大小相同。與頁框大小相同。 分區(qū)分區(qū)：進程的邏輯地址空間是連續(xù)的、一維的、：進程的邏輯地址空間是連續(xù)的、一維的、線性地址，進程的每一條指令和數(shù)據(jù)的地址相線性地址，進程的每一條指令和數(shù)據(jù)的地址相對于第一條語句的地址而定。對于第一條語句的地址

22、而定。 分頁分頁：進程被分割成許多頁面。每個頁面內(nèi)的：進程被分割成許多頁面。每個頁面內(nèi)的指令和數(shù)據(jù)是連續(xù)的，它們的地址相對于其所指令和數(shù)據(jù)是連續(xù)的，它們的地址相對于其所屬頁的第一條語句的地址，稱為屬頁的第一條語句的地址，稱為頁內(nèi)偏移量頁內(nèi)偏移量。 邏輯地址被分為兩部分：邏輯地址被分為兩部分：頁號頁號和和頁內(nèi)偏移量頁內(nèi)偏移量 頁號頁號頁內(nèi)偏移量頁內(nèi)偏移量15 10 9 0圖圖3.14 分頁管理的邏輯地址表示分頁管理的邏輯地址表示 當一個進程被裝入物理內(nèi)存時，系統(tǒng)將當一個進程被裝入物理內(nèi)存時，系統(tǒng)將為該進程的每個頁面分配一個獨立的頁為該進程的每個頁面分配一個獨立的頁框?？?。 同一個進程的多個頁面不

23、必存放在連續(xù)同一個進程的多個頁面不必存放在連續(xù)的多個頁框中。的多個頁框中。例如例如 假設內(nèi)存能提供假設內(nèi)存能提供16個空閑頁框，進程個空閑頁框，進程P1被分被分割成割成4個頁面，裝入內(nèi)存中的個頁面，裝入內(nèi)存中的0號至號至3號頁框。號頁框。進程進程P2被分割成被分割成3個頁面，裝入個頁面，裝入4號至號至6號頁號頁框。進程框。進程P3被裝入被裝入7號至號至12號頁框，如圖號頁框，如圖3.15(a)所示。所示。 此時，進程此時，進程P4請求分配請求分配5個頁框大小的存儲空個頁框大小的存儲空間，但內(nèi)存只有間，但內(nèi)存只有3個空閑頁框。于是，將暫時個空閑頁框。于是，將暫時不運行的不運行的P2交換出內(nèi)存，如

24、圖交換出內(nèi)存，如圖3.15(b)所示。所示。 然后，再將然后，再將P4裝入裝入4、5、6、13、14號頁號頁框，如圖框，如圖3.15(c)所示。所示。 圖圖3.15 進程裝入到離散的頁框中進程裝入到離散的頁框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5頁框號頁框號 內(nèi)存內(nèi)存(a) 依次裝入依次裝入P1、P2、P3P1P2P3空閑空閑0123456789101112131415P1.2P1.1P1.0P1.3P3.0P3.1P3.2P3.3P3.4P3.5頁框號頁框號 內(nèi)存內(nèi)存(b) 換出換

25、出P2P1空閑空閑P3空閑空閑0123456789101112131415P1.2P1.1P1.0P1.3P4.0P4.1P4.2P3.0P3.1P3.2P3.3P3.4P3.5P4.3P4.4頁框號頁框號 內(nèi)存內(nèi)存(c) 裝入裝入P4P1P4P3空閑空閑P4數(shù)據(jù)結構：頁表數(shù)據(jù)結構：頁表 頁表：系統(tǒng)為每個進程建立一張頁面映頁表：系統(tǒng)為每個進程建立一張頁面映射表。射表。 用于記載進程的各頁面到物理內(nèi)存中頁用于記載進程的各頁面到物理內(nèi)存中頁框的映射信息?？虻挠成湫畔?。 進程的每個頁面依次對應頁表中的一個進程的每個頁面依次對應頁表中的一個表項，其中包含相應頁在內(nèi)存中對應的表項，其中包含相應頁在內(nèi)存中

26、對應的物理頁框號和頁面存取控制權限等字段。物理頁框號和頁面存取控制權限等字段。頁號頁號頁框號頁框號00112233進程進程P1頁表頁表頁號頁號頁框號頁框號0-1-2-進程進程P2頁表頁表頁號頁號頁框號頁框號071829310411512進程進程P3頁表頁表頁號頁號頁框號頁框號041526313414進程進程P4頁表頁表圖圖3.16 進程進程P1、P2、P3、P4的頁表的頁表數(shù)據(jù)結構：頁框表數(shù)據(jù)結構：頁框表 空閑頁框表：登記系統(tǒng)中剩下的空閑頁空閑頁框表：登記系統(tǒng)中剩下的空閑頁框情況框情況圖圖3.17 空閑頁框表空閑頁框表151413地址變換地址變換 硬件機制，實現(xiàn)邏輯地址到物理地址的轉換硬件機制

27、，實現(xiàn)邏輯地址到物理地址的轉換 分頁系統(tǒng)中的地址變換過程如下：分頁系統(tǒng)中的地址變換過程如下：（1） 根據(jù)邏輯地址根據(jù)邏輯地址,計算出頁號和頁內(nèi)偏移計算出頁號和頁內(nèi)偏移量；量；（2） 用頁號檢索頁表，查找指定頁面對應用頁號檢索頁表，查找指定頁面對應的頁框號；的頁框號；（3） 根據(jù)頁框號和頁內(nèi)偏移量，計算出物根據(jù)頁框號和頁內(nèi)偏移量，計算出物理地址。理地址。頁表寄存器頁表寄存器 頁表寄存器：實現(xiàn)快速地址映射，存儲執(zhí)行進頁表寄存器：實現(xiàn)快速地址映射，存儲執(zhí)行進程的頁表起始地址。程的頁表起始地址。 頁表寄存器設置在處理機硬件中。頁表寄存器設置在處理機硬件中。 當進程被創(chuàng)建時，其頁表起始地址記載于進程當進

28、程被創(chuàng)建時，其頁表起始地址記載于進程PCB中。中。 當進程被調(diào)度執(zhí)行時，頁表的起始地址將從該當進程被調(diào)度執(zhí)行時，頁表的起始地址將從該進程的進程的PCB中取出，并填入頁表寄存器中。中取出，并填入頁表寄存器中。 進行地址變換時，處理機從頁表寄存器中查找進行地址變換時，處理機從頁表寄存器中查找頁表的地址。頁表的地址。頁號頁號 偏移量偏移量邏輯地址邏輯地址物理地址物理地址頁框號頁框號 偏移量偏移量頁表寄存器頁表寄存器頁表起始地址頁表起始地址內(nèi)存內(nèi)存頁框號頁框號頁表頁表地址轉換地址轉換程序程序+偏偏移移量量圖圖3.18 分頁系統(tǒng)的地址變換過程分頁系統(tǒng)的地址變換過程頁框頁框大頁表大頁表 大邏輯地址空間，頁

29、表非常大，需要占大邏輯地址空間，頁表非常大，需要占用相當大的內(nèi)存空間。用相當大的內(nèi)存空間。 比如，比如，32位邏輯地址空間，假設頁面大位邏輯地址空間，假設頁面大小為小為4KB（212），則），則4GB（232）的）的邏輯地址空間將被劃分成邏輯地址空間將被劃分成220個頁面。個頁面。大頁表大頁表 若采用一級頁表，則其內(nèi)將包含若采用一級頁表，則其內(nèi)將包含1兆（兆（220）個頁表項。若按字節(jié)尋址，一個頁表項占個頁表項。若按字節(jié)尋址，一個頁表項占4B，則一級頁表需要占用則一級頁表需要占用4MB（222）內(nèi)存空間。）內(nèi)存空間。 不可能將不可能將4MB的頁表保存在一個連續(xù)區(qū)中。的頁表保存在一個連續(xù)區(qū)中。

30、那么，如何處理大頁表的存儲與檢索呢？那么，如何處理大頁表的存儲與檢索呢？ 二級頁表二級頁表 將一個大頁表全部保存在內(nèi)存中。將一個大頁表全部保存在內(nèi)存中。 首先，將其分割，并離散地存儲在內(nèi)存的多個首先，將其分割，并離散地存儲在內(nèi)存的多個頁框中。頁框中。 為之建立二級頁表，記錄被分割的各個頁面存為之建立二級頁表，記錄被分割的各個頁面存儲在哪些頁框中，也稱為外層頁表（儲在哪些頁框中，也稱為外層頁表（Outer Page Table）。）。 對于對于4GB的進程，若采用二級頁表，則對應的的進程，若采用二級頁表，則對應的二級頁表結構如圖：二級頁表結構如圖： 4GB的用戶進程的用戶進程4MB的一級頁表的一

31、級頁表4KB的二級頁表的二級頁表圖圖3.19 4GB進程的二級頁表結構進程的二級頁表結構多級頁表多級頁表 對于某些機器，二級頁表也可能非常大?？梢詫τ谀承C器，二級頁表也可能非常大?？梢圆捎枚嗉夗摫恚瑢ν鈱禹摫碓龠M行分頁，將各采用多級頁表，對外層頁表再進行分頁，將各個頁面離散地存儲到不相鄰接的物理頁框中個頁面離散地存儲到不相鄰接的物理頁框中 雖然，對大頁表而言，多級頁表方法消除了對雖然，對大頁表而言，多級頁表方法消除了對較大的連續(xù)內(nèi)存空間的需要，但并未解決大頁較大的連續(xù)內(nèi)存空間的需要，但并未解決大頁表占用較大的內(nèi)存空間的問題，建立多及頁表表占用較大的內(nèi)存空間的問題，建立多及頁表反而會增加額外的

32、存儲空間。反而會增加額外的存儲空間。大頁表大頁表 最好的解決辦法是采用最好的解決辦法是采用虛擬存儲技術虛擬存儲技術，內(nèi)存中，內(nèi)存中僅裝入頁表的一部分。僅裝入頁表的一部分。 即只將當前需要的部分頁表項裝入內(nèi)存，其余即只將當前需要的部分頁表項裝入內(nèi)存，其余頁表項駐留在磁盤上，需要時再將它們裝入內(nèi)頁表項駐留在磁盤上，需要時再將它們裝入內(nèi)存。存。 若采用多級頁表，對于正在運行的進程，必須若采用多級頁表，對于正在運行的進程，必須將其外層頁表調(diào)入內(nèi)存，而內(nèi)層頁表只需調(diào)入將其外層頁表調(diào)入內(nèi)存，而內(nèi)層頁表只需調(diào)入幾頁就可以了。幾頁就可以了。反置頁表反置頁表(Inverted Page Table) 一般情況下

33、，系統(tǒng)從進程的角度為每個進程建一般情況下，系統(tǒng)從進程的角度為每個進程建立一張頁表，頁表的表項按頁號排序。立一張頁表，頁表的表項按頁號排序。 這種方法可能導致一個大進程的頁表太大，占這種方法可能導致一個大進程的頁表太大，占據(jù)大量的內(nèi)存空間。據(jù)大量的內(nèi)存空間。 反置頁表反置頁表：從內(nèi)存的角度建立頁表，整個系統(tǒng)：從內(nèi)存的角度建立頁表，整個系統(tǒng)只有一張頁表。頁表的表項基于內(nèi)存中的每一只有一張頁表。頁表的表項基于內(nèi)存中的每一個物理頁框設置，頁表項按頁框號的順序排序。個物理頁框設置，頁表項按頁框號的順序排序。其中還必須包含頁框?qū)捻撎柤捌潆`屬進程其中還必須包含頁框?qū)捻撎柤捌潆`屬進程的標識符等信息。的

34、標識符等信息。 反置頁表反置頁表 通常，反置頁表需要包含成千上萬個表項，利通常，反置頁表需要包含成千上萬個表項，利用進程用進程ID和頁號檢索其中某一個表項的速度很和頁號檢索其中某一個表項的速度很慢。慢。 可以根據(jù)進程可以根據(jù)進程ID和頁號構建和頁號構建Hash表。表。Hash表表的每一項指向反置頁表中的某一項。的每一項指向反置頁表中的某一項。 但是，可能會出現(xiàn)多個邏輯地址被映射到一個但是，可能會出現(xiàn)多個邏輯地址被映射到一個Hash表項的情況。需要通過鏈接指針將多個表項的情況。需要通過鏈接指針將多個沖突的映射鏈接起來。沖突的映射鏈接起來。 一般，沖突的表項一般只有一項，或兩項。一般，沖突的表項一

35、般只有一項，或兩項。 地址變換地址變換 首先，以進程首先，以進程ID和頁號為參數(shù)，代入和頁號為參數(shù)，代入Hash函函數(shù)進行計算。數(shù)進行計算。 然后，根據(jù)計算結果，檢索反置頁表。若檢索然后，根據(jù)計算結果，檢索反置頁表。若檢索完整個反置頁表都未找到與之匹配的表項，表完整個反置頁表都未找到與之匹配的表項，表明此頁尚未裝入內(nèi)存。明此頁尚未裝入內(nèi)存。 若系統(tǒng)支持虛擬存儲技術，則產(chǎn)生請求調(diào)頁中若系統(tǒng)支持虛擬存儲技術，則產(chǎn)生請求調(diào)頁中斷。若系統(tǒng)不支持虛擬存儲技術，則表示地址斷。若系統(tǒng)不支持虛擬存儲技術，則表示地址出錯。出錯。 當檢索到反置頁表中的對應表項時，將其中的當檢索到反置頁表中的對應表項時，將其中的頁

36、框號與邏輯地址中的偏移量相加，構成物理頁框號與邏輯地址中的偏移量相加，構成物理地址。地址。 物理地址物理地址偏移量偏移量頁框號頁框號邏輯地址邏輯地址偏移量偏移量頁號頁號HashHash表表頁號頁號 進程進程ID指針指針頁框號頁框號反置頁表反置頁表圖圖3.20 利用反置頁表進行地址變換利用反置頁表進行地址變換 快表快表 分頁系統(tǒng)：處理機每次存取指令或數(shù)據(jù)至少需分頁系統(tǒng)：處理機每次存取指令或數(shù)據(jù)至少需要訪問兩次物理內(nèi)存要訪問兩次物理內(nèi)存 第一次訪問頁表，第二次存取指令或數(shù)第一次訪問頁表，第二次存取指令或數(shù)據(jù)據(jù) 為了提高地址變換速度，為進程頁表設置一個為了提高地址變換速度，為進程頁表設置一個專用的高

37、速緩沖存儲器，稱為快表、專用的高速緩沖存儲器，稱為快表、TLB(Translation Lookaside Buffer)，或聯(lián)，或聯(lián)想存儲器（想存儲器（Associative Memory） 快表的工作原理快表的工作原理 快表的工作原理類似于系統(tǒng)中的數(shù)據(jù)高速緩存快表的工作原理類似于系統(tǒng)中的數(shù)據(jù)高速緩存(cache)，其中專門保存當前進程最近訪問過，其中專門保存當前進程最近訪問過的一組頁表項。的一組頁表項。 根據(jù)根據(jù)局部性原理局部性原理，在一個很短的時間段內(nèi)，程，在一個很短的時間段內(nèi)，程序的執(zhí)行總是局部于某一個范圍。序的執(zhí)行總是局部于某一個范圍。 即，進程最近訪問過的頁面在不久的將來還可即，進

38、程最近訪問過的頁面在不久的將來還可能被訪問。能被訪問。分頁系統(tǒng)地址轉換分頁系統(tǒng)地址轉換 通過根據(jù)邏輯地址中的頁號，查找快表中是否通過根據(jù)邏輯地址中的頁號，查找快表中是否存在對應的頁表項。存在對應的頁表項。 若快表中存在該表項，稱為命中（若快表中存在該表項，稱為命中（hit），?。〕銎渲械捻摽蛱?，加上頁內(nèi)偏移量，計算出物出其中的頁框號，加上頁內(nèi)偏移量，計算出物理地址。理地址。 若快表中不存在該頁表項，稱為命中失敗，則若快表中不存在該頁表項，稱為命中失敗，則再查找頁表，找到邏輯地址中指定頁號對應的再查找頁表，找到邏輯地址中指定頁號對應的頁框號。同時，更新快表，將該表項插入快表頁框號。同時，更新

39、快表，將該表項插入快表中。并計算物理地址中。并計算物理地址圖圖3.21 具有快表的分頁系統(tǒng)地址變換過程具有快表的分頁系統(tǒng)地址變換過程頁號頁號 偏移量偏移量邏輯地址邏輯地址物理地址物理地址頁框號頁框號 偏移量偏移量偏偏移移量量內(nèi)存內(nèi)存快表快表頁框號頁框號頁表頁表頁框頁框TLB命中命中命中失敗命中失敗頁面與頁框大小頁面與頁框大小 分頁系統(tǒng)中，頁面分頁系統(tǒng)中，頁面 = 頁框。頁框的大小頁框。頁框的大小由計算機的硬件邏輯定義。通常，頁框由計算機的硬件邏輯定義。通常，頁框的大小是的大小是2的冪次個字節(jié)，且常在的冪次個字節(jié)，且常在512B（29）4KB（212）之間，典型的頁）之間，典型的頁框大小為框大小

40、為1KB。 將頁框大小設置為將頁框大小設置為2的冪次，可以簡化處的冪次，可以簡化處理機中地址變換硬件邏輯的設計與實現(xiàn)。理機中地址變換硬件邏輯的設計與實現(xiàn)。頁面與頁框大小頁面與頁框大小 影響頁面與頁框大小的主要因素：頁內(nèi)零頭、影響頁面與頁框大小的主要因素：頁內(nèi)零頭、地址轉換速度和頁面交換效率。地址轉換速度和頁面交換效率。 較小的頁面較小的頁面有利于減少內(nèi)零頭，從而有利于提有利于減少內(nèi)零頭，從而有利于提高內(nèi)存的利用率。然而，高內(nèi)存的利用率。然而，較小的頁面較小的頁面也將導致也將導致頁表過大，從而降低處理機訪問頁表時的命中頁表過大，從而降低處理機訪問頁表時的命中率率(Hit Rate)。 塊越大，內(nèi)

41、塊越大，內(nèi)/外存之間的數(shù)據(jù)交換效率越高。外存之間的數(shù)據(jù)交換效率越高。因此，對于支持交換技術的系統(tǒng)，因此，對于支持交換技術的系統(tǒng)，較大的頁面較大的頁面有利于提高頁面換進有利于提高頁面換進/換出內(nèi)存的效率。換出內(nèi)存的效率。對分頁存儲管理的評價對分頁存儲管理的評價 徹底消除了外零頭徹底消除了外零頭,僅存在很少的內(nèi)零頭僅存在很少的內(nèi)零頭, 提高提高了內(nèi)存利用率。了內(nèi)存利用率。 分頁操作由系統(tǒng)自動進行分頁操作由系統(tǒng)自動進行,一個頁面不能實現(xiàn)一個頁面不能實現(xiàn)某種邏輯功能。用戶看到的邏輯地址是一維的，某種邏輯功能。用戶看到的邏輯地址是一維的，無法調(diào)試執(zhí)行其中的某個子程序或子函數(shù)。無法調(diào)試執(zhí)行其中的某個子程序

42、或子函數(shù)。 采用分頁技術不易于實現(xiàn)存儲共享，也不便于采用分頁技術不易于實現(xiàn)存儲共享，也不便于程序的動態(tài)鏈接。程序的動態(tài)鏈接。簡單分段存儲管理簡單分段存儲管理 基于模塊化程序設計時，常常需要將一個大任基于模塊化程序設計時，常常需要將一個大任務劃分成若干相對獨立的子任務，對應于子任務劃分成若干相對獨立的子任務，對應于子任務編寫子程序，稱為段務編寫子程序，稱為段(Segment)。 每個子程序可以獨立地編輯、編譯、鏈接和執(zhí)每個子程序可以獨立地編輯、編譯、鏈接和執(zhí)行。行。 各個子程序由實現(xiàn)的功能決定，長度各不相同。各個子程序由實現(xiàn)的功能決定，長度各不相同。執(zhí)行時，根據(jù)實際需要，將若干子程序鏈接成執(zhí)行時

43、，根據(jù)實際需要，將若干子程序鏈接成一個大程序。一個大程序。基本原理基本原理 程序由若干邏輯段組成，每個段有自己的名字程序由若干邏輯段組成，每個段有自己的名字和長度。程序的邏輯地址是由段名（段號）和和長度。程序的邏輯地址是由段名（段號）和段內(nèi)偏移量決定。每個段的邏輯地址從段內(nèi)偏移量決定。每個段的邏輯地址從0開始開始編址編址 段號段號段內(nèi)偏移量段內(nèi)偏移量15 10 9 0圖圖3.22 分段管理的邏輯地址表示分段管理的邏輯地址表示 系統(tǒng)采用動態(tài)劃分技術，將物理內(nèi)存動系統(tǒng)采用動態(tài)劃分技術，將物理內(nèi)存動態(tài)地劃分成許多尺寸不相等的分區(qū)。態(tài)地劃分成許多尺寸不相等的分區(qū)。 當一個進程被裝入物理內(nèi)存時，系統(tǒng)將當

44、一個進程被裝入物理內(nèi)存時，系統(tǒng)將為該進程的每一段獨立地分配一個分區(qū)。為該進程的每一段獨立地分配一個分區(qū)。同一進程的多個段不必存放在連續(xù)的多同一進程的多個段不必存放在連續(xù)的多個分區(qū)中。個分區(qū)中。分段系統(tǒng)的基本數(shù)據(jù)結構分段系統(tǒng)的基本數(shù)據(jù)結構 段表段表 : 每個進程建立一個，用于描述進程的分每個進程建立一個，用于描述進程的分段情況，記載進程的各個段到物理內(nèi)存中分區(qū)段情況，記載進程的各個段到物理內(nèi)存中分區(qū)的映射情況。其中包含段號、段長、段基址以的映射情況。其中包含段號、段長、段基址以及對本段的存取控制權限等信息。及對本段的存取控制權限等信息。 空閑分區(qū)表空閑分區(qū)表 : 用于記載物理內(nèi)存中的空閑分區(qū)用于

45、記載物理內(nèi)存中的空閑分區(qū)情況情況圖圖3.23 分段存儲示例分段存儲示例 P2.1P1.0P1.2P1.1P2.0(a) 分段存儲分段存儲0500100執(zhí)行執(zhí)行存取控制存取控制段基址段基址段長段長段號段號1200800只讀只讀2200 1000執(zhí)行執(zhí)行(b) 進程進程P1的段表的段表0100 1200執(zhí)行執(zhí)行存取控制存取控制段基址段基址段長段長段號段號1200600執(zhí)行執(zhí)行(c) 進程進程P2的段表的段表地址變換和存儲保護地址變換和存儲保護 （1） 根據(jù)邏輯地址中的段號檢索進程段表，根據(jù)邏輯地址中的段號檢索進程段表，獲得指定段對應的段表項；獲得指定段對應的段表項；（2） 判斷是否地址越界。比較邏

46、輯地址中判斷是否地址越界。比較邏輯地址中的段內(nèi)偏移量與段表項中的段長，若超過段的的段內(nèi)偏移量與段表項中的段長，若超過段的長度，則產(chǎn)生存儲保護中斷（該中斷將由操作長度，則產(chǎn)生存儲保護中斷（該中斷將由操作系統(tǒng)進行處理）；否則，轉（系統(tǒng)進行處理）；否則，轉（3）；）；（3）把邏輯地址中的段內(nèi)偏移量與段表表項中）把邏輯地址中的段內(nèi)偏移量與段表表項中的段基址相加，從而得到物理地址。的段基址相加，從而得到物理地址。 段表寄存器段表寄存器 段表同樣被保存在物理內(nèi)存中。段表同樣被保存在物理內(nèi)存中。 段表寄存器段表寄存器 ：實現(xiàn)快速地址變換，用來存放實現(xiàn)快速地址變換，用來存放當前執(zhí)行進程的段表在物理內(nèi)存中的起始

47、地址。當前執(zhí)行進程的段表在物理內(nèi)存中的起始地址。 當創(chuàng)建進程，將進程的程序和數(shù)據(jù)裝入內(nèi)存時，當創(chuàng)建進程，將進程的程序和數(shù)據(jù)裝入內(nèi)存時，系統(tǒng)為之建立段表，并將段表的起始地址填入系統(tǒng)為之建立段表，并將段表的起始地址填入進程的進程的PCB中。中。 當進程被調(diào)度執(zhí)行時，取出其當進程被調(diào)度執(zhí)行時，取出其PCB中的段表首中的段表首址，填入段表寄存器中。址，填入段表寄存器中。 圖圖3.24 分段系統(tǒng)的地址變換過程分段系統(tǒng)的地址變換過程內(nèi)存內(nèi)存物理地址物理地址段基址段基址+偏移量偏移量偏偏移移量量段號段號 偏移量偏移量邏輯地址邏輯地址段表寄存器段表寄存器段表起始地址段表起始地址+段表段表段長段長 段基址段基址

48、+越界越界判斷判斷中斷中斷越界越界正常正常段段段段分段系統(tǒng)的快表分段系統(tǒng)的快表 在分段系統(tǒng)中，為了訪問內(nèi)存中的一條指令或在分段系統(tǒng)中，為了訪問內(nèi)存中的一條指令或數(shù)據(jù)，需要兩次訪問內(nèi)存：數(shù)據(jù)，需要兩次訪問內(nèi)存： 第一次，訪問內(nèi)存中的段表，獲得對應段的起始第一次，訪問內(nèi)存中的段表，獲得對應段的起始地址。根據(jù)段的起始地址和段內(nèi)偏移量，計算出物理地址。根據(jù)段的起始地址和段內(nèi)偏移量，計算出物理地址。地址。 第二次，根據(jù)物理地址，訪問對應存儲單元的指第二次，根據(jù)物理地址，訪問對應存儲單元的指令或數(shù)據(jù)。令或數(shù)據(jù)。 為了提高處理機的效率，類似分頁系統(tǒng)的快表，為了提高處理機的效率，類似分頁系統(tǒng)的快表，可以為分段

49、系統(tǒng)增加一個快表，用于保存最近可以為分段系統(tǒng)增加一個快表，用于保存最近使用過的段表項。使用過的段表項。 對分段系統(tǒng)的評價對分段系統(tǒng)的評價 有效消除了內(nèi)零頭，提高了存儲利用率。有效消除了內(nèi)零頭，提高了存儲利用率。 允許子程序獨立編譯和修改，而不需要重新編允許子程序獨立編譯和修改，而不需要重新編譯或鏈接其它相關子程序。譯或鏈接其它相關子程序。 容易實現(xiàn)存儲共享。容易實現(xiàn)存儲共享。 具有較高的安全保障。具有較高的安全保障。 很容易滿足程序段的動態(tài)增長需要很容易滿足程序段的動態(tài)增長需要 。分頁與分段技術的比較分頁與分段技術的比較 都采用非連續(xù)存儲，由地址映射實現(xiàn)地址變換。都采用非連續(xù)存儲，由地址映射實

50、現(xiàn)地址變換。 不同主要表現(xiàn)在：不同主要表現(xiàn)在：（1） 頁是信息的物理單位，大小固定。段是信息的頁是信息的物理單位，大小固定。段是信息的邏輯單位，各段的長度不固定。每一段都具有一定邏邏輯單位，各段的長度不固定。每一段都具有一定邏輯含義。輯含義。（2） 分頁的地址空間是一維的，邏輯地址的劃分由分頁的地址空間是一維的，邏輯地址的劃分由機器硬件實現(xiàn)，對用戶透明。分段的地址空間是二維機器硬件實現(xiàn)，對用戶透明。分段的地址空間是二維或多維的，程序員知道段名和段內(nèi)偏移量。或多維的，程序員知道段名和段內(nèi)偏移量。（3）分頁活動源于系統(tǒng)管理物理內(nèi)存的需要，在系統(tǒng)內(nèi)）分頁活動源于系統(tǒng)管理物理內(nèi)存的需要，在系統(tǒng)內(nèi)部進行

51、，由系統(tǒng)實施，用戶看不見。分段活動源于用部進行，由系統(tǒng)實施，用戶看不見。分段活動源于用戶進行模塊化程序設計的需要，在系統(tǒng)外部進行，由戶進行模塊化程序設計的需要，在系統(tǒng)外部進行，由用戶實施，用戶是知道的。用戶實施，用戶是知道的。 簡單段頁式存儲管理簡單段頁式存儲管理 基本思想：采用分段方法組織用戶程序，采用基本思想：采用分段方法組織用戶程序，采用分頁方法分配和管理內(nèi)存。分頁方法分配和管理內(nèi)存。 即，用戶程序可以用模塊化思想進行設計，一即，用戶程序可以用模塊化思想進行設計，一個用戶序由若干段構成。系統(tǒng)將內(nèi)存劃分成固個用戶序由若干段構成。系統(tǒng)將內(nèi)存劃分成固定大小的頁框，并將程序的每一段分割成若干定大

52、小的頁框，并將程序的每一段分割成若干頁以后裝入內(nèi)存執(zhí)行時。頁以后裝入內(nèi)存執(zhí)行時。邏輯地址邏輯地址 在段頁式系統(tǒng)中，進程的每一段被進一步分割在段頁式系統(tǒng)中，進程的每一段被進一步分割成頁面，段內(nèi)代碼和數(shù)據(jù)地址不再連續(xù)。成頁面，段內(nèi)代碼和數(shù)據(jù)地址不再連續(xù)。 邏輯地址由邏輯地址由3部分組成：段號、段內(nèi)頁號、頁部分組成：段號、段內(nèi)頁號、頁內(nèi)偏移量，如圖內(nèi)偏移量，如圖段號段號段內(nèi)頁號段內(nèi)頁號頁內(nèi)偏移量頁內(nèi)偏移量圖圖3.25 段頁式系統(tǒng)的邏輯地址結構段頁式系統(tǒng)的邏輯地址結構數(shù)據(jù)結構數(shù)據(jù)結構 用于管理的數(shù)據(jù)結構：段表、頁表，如圖用于管理的數(shù)據(jù)結構：段表、頁表，如圖圖圖3.26 段頁式系統(tǒng)的數(shù)據(jù)結構段頁式系統(tǒng)的

53、數(shù)據(jù)結構段段0段段1段段2用戶程序用戶程序段表段表03頁表首址頁表首址頁表長度頁表長度段號段號12內(nèi)存內(nèi)存 OS 0頁號頁號 頁框號頁框號12頁號頁號 頁框號頁框號頁表頁表段表寄存器段表寄存器 段表寄存器段表寄存器：加速地址變換，用于存放：加速地址變換，用于存放執(zhí)行進程段表的起始地址。執(zhí)行進程段表的起始地址。地址變換地址變換 首先，從段表寄存器從獲得進程段表的起始地首先，從段表寄存器從獲得進程段表的起始地址，根據(jù)該地址，查找進程的段表。址，根據(jù)該地址，查找進程的段表。 然后，根據(jù)邏輯地址指定的段號檢索段表，找然后，根據(jù)邏輯地址指定的段號檢索段表，找到對應段的頁表起始地址。到對應段的頁表起始地址

54、。 再根據(jù)邏輯地址中指定的頁號檢索該頁表，找再根據(jù)邏輯地址中指定的頁號檢索該頁表，找到對應頁所在的頁框號。到對應頁所在的頁框號。 最后，用頁框號加上邏輯地址中指定的頁內(nèi)偏最后，用頁框號加上邏輯地址中指定的頁內(nèi)偏移量，形成物理地址。移量，形成物理地址。 圖圖3.27 段頁式系統(tǒng)的地址變換過程段頁式系統(tǒng)的地址變換過程段表段表頁表首址頁表首址段號段號頁內(nèi)偏移量頁內(nèi)偏移量邏輯地址邏輯地址段內(nèi)頁號段內(nèi)頁號+物理地址物理地址頁框號頁框號+頁內(nèi)偏移量頁內(nèi)偏移量頁表頁表頁框號頁框號+偏偏移移量量內(nèi)存內(nèi)存頁框頁框頁框頁框頁框頁框段表寄存器段表寄存器段表起始地址段表起始地址快表快表 第一次，訪問段表，從中獲得該段

55、的頁表首址；第一次，訪問段表，從中獲得該段的頁表首址； 第二次，訪問頁表，從中取出邏輯地址指定的第二次，訪問頁表，從中取出邏輯地址指定的頁面所在的頁框號，并將該頁框號和頁內(nèi)偏移頁面所在的頁框號，并將該頁框號和頁內(nèi)偏移量相加，形成指令或數(shù)據(jù)的物理地址；量相加，形成指令或數(shù)據(jù)的物理地址； 第三次訪問內(nèi)存，根據(jù)前面計算的物理地址，第三次訪問內(nèi)存，根據(jù)前面計算的物理地址，取出對應存儲單元的指令或數(shù)據(jù)。取出對應存儲單元的指令或數(shù)據(jù)。 可以在地址變換機構中增設一個高速緩沖寄存可以在地址變換機構中增設一個高速緩沖寄存器，其中保存最近使用過的頁號及其所屬的段器，其中保存最近使用過的頁號及其所屬的段號。號。具有

56、快表的地址轉換具有快表的地址轉換 首先，利用段號和頁號檢索該高速緩沖寄存器。首先，利用段號和頁號檢索該高速緩沖寄存器。 若找到匹配的表項，則可以從中獲得相應頁面若找到匹配的表項，則可以從中獲得相應頁面的頁框號，加上頁內(nèi)偏移量，形成物理地址。的頁框號，加上頁內(nèi)偏移量，形成物理地址。 若該高速緩沖寄存器中未包含對應表項，則需若該高速緩沖寄存器中未包含對應表項，則需要訪問段表及頁表，計算出物理地址以后，從要訪問段表及頁表，計算出物理地址以后，從相應存儲單元獲取指令或數(shù)據(jù)相應存儲單元獲取指令或數(shù)據(jù)。 對段頁式存儲管理方式的評價對段頁式存儲管理方式的評價 綜合了分段和分頁技術的優(yōu)點，既能有效地利綜合了分

57、段和分頁技術的優(yōu)點，既能有效地利用存儲空間，又能方便用戶進行程序設計。用存儲空間，又能方便用戶進行程序設計。 但是，實現(xiàn)段頁式存儲管理系統(tǒng)需要增加硬件但是，實現(xiàn)段頁式存儲管理系統(tǒng)需要增加硬件成本，系統(tǒng)的復雜度和管理開銷也大大增加。成本，系統(tǒng)的復雜度和管理開銷也大大增加。 因此，段頁式存儲管理技術適合于大、中型計因此，段頁式存儲管理技術適合于大、中型計算機系統(tǒng)，不太適合小型、微型計算機系統(tǒng)。算機系統(tǒng)，不太適合小型、微型計算機系統(tǒng)。3.5 虛擬存儲管理技術虛擬存儲管理技術 簡單存儲：要求將一個進程所需的程序和數(shù)據(jù)簡單存儲：要求將一個進程所需的程序和數(shù)據(jù)全部裝入內(nèi)存方可執(zhí)行。全部裝入內(nèi)存方可執(zhí)行。

58、這樣的系統(tǒng)存在兩個很嚴重的問題。這樣的系統(tǒng)存在兩個很嚴重的問題。 其一，對于大進程，如果其所需內(nèi)存空間超過了內(nèi)存其一，對于大進程，如果其所需內(nèi)存空間超過了內(nèi)存的最大容量，則無法運行。的最大容量，則無法運行。 其二，對于多道程序系統(tǒng)，由于每一個進程需要全部其二，對于多道程序系統(tǒng)，由于每一個進程需要全部裝入內(nèi)存，使同時駐留內(nèi)存的進程數(shù)量受到限制。雖裝入內(nèi)存，使同時駐留內(nèi)存的進程數(shù)量受到限制。雖然也可以通過提高內(nèi)存容量來解決，但是代價太高。然也可以通過提高內(nèi)存容量來解決，但是代價太高。 如果能將一部分價格較低的外存空間當作內(nèi)存如果能將一部分價格較低的外存空間當作內(nèi)存使用，從邏輯上擴充內(nèi)存容量。那么，

59、將獲得使用，從邏輯上擴充內(nèi)存容量。那么，將獲得更高的性價比。更高的性價比。虛擬存儲技術的理論依據(jù)虛擬存儲技術的理論依據(jù) 程序執(zhí)行的局部性原理：程序的執(zhí)行總是呈現(xiàn)局程序執(zhí)行的局部性原理：程序的執(zhí)行總是呈現(xiàn)局部性。即，在一個較短的時間段內(nèi)，程序的執(zhí)行部性。即，在一個較短的時間段內(nèi)，程序的執(zhí)行僅限于某個部分；相應的，它所訪問的存儲空間僅限于某個部分；相應的，它所訪問的存儲空間也局限于某個區(qū)域。也局限于某個區(qū)域。 因此，只要保證進程執(zhí)行所需的部分程序和數(shù)據(jù)因此，只要保證進程執(zhí)行所需的部分程序和數(shù)據(jù)駐留在內(nèi)存，一段時間內(nèi)進程都能順利執(zhí)行。駐留在內(nèi)存，一段時間內(nèi)進程都能順利執(zhí)行。實現(xiàn)虛擬存儲的一般過程實現(xiàn)

60、虛擬存儲的一般過程 進程運行之前，僅需要將一部分頁面或段裝入進程運行之前，僅需要將一部分頁面或段裝入內(nèi)存，便可啟動運行，其余部分暫時保留在磁內(nèi)存，便可啟動運行，其余部分暫時保留在磁盤上。盤上。 進程運行時，如果它所需要訪問的頁面（段）進程運行時，如果它所需要訪問的頁面（段）已經(jīng)裝入內(nèi)存，則可以繼續(xù)執(zhí)行下去；已經(jīng)裝入內(nèi)存，則可以繼續(xù)執(zhí)行下去； 如果其所需要訪問的頁面（段）尚未裝入內(nèi)存，如果其所需要訪問的頁面（段）尚未裝入內(nèi)存，則發(fā)生缺頁（段）中斷，進程阻塞。則發(fā)生缺頁（段）中斷，進程阻塞。 此時，系統(tǒng)將啟動請求調(diào)頁（段）功能，將進此時，系統(tǒng)將啟動請求調(diào)頁（段）功能，將進程所需的頁（段）裝入內(nèi)存。