操作系統(tǒng)PPT參考課件.ppt

1、第四章 存儲器管理,操作系統(tǒng),Page 1,第四章 存儲器管理,重點 理解重定位的基本概念 掌握動態(tài)分區(qū)分配方式 掌握理解分頁和分段存儲管理方式 理解虛擬存儲器的基本概念 掌握請求分頁系統(tǒng)的基本原理 難點 動態(tài)分區(qū)分配算法 分頁和分段地址轉(zhuǎn)換 請求分頁系統(tǒng)的地址轉(zhuǎn)換及頁面置換算法,Page 2,第四章 存儲器管理,知識點 重定位的基本概念 動態(tài)分區(qū)分配方式及分配算法、分區(qū)保護 分頁存儲管理及地址變換、分段存儲管理及地址變換，信息共享和保護 虛擬存儲器的基本概念、特征，頁面置換技術 請求分頁系統(tǒng)，頁表機制、地址變換及頁面置換算法,Page 3,第四章 存儲器管理,存儲器是計算機系統(tǒng)重要的組成部分

2、 雖然存儲器的容量不斷擴大，但仍不能滿足要求，因此存儲器管理是操作系統(tǒng)的重要工作,Page 4,第四章 存儲器管理,存儲器包括內(nèi)存（主存）和外存（磁盤） 存儲器的功能是保存數(shù)據(jù)，存儲器的發(fā)展方向是高速、大容量和小體積。 內(nèi)存在訪問速度方面的發(fā)展：DRAM、SDRAM、SRAM等； 硬盤技術在大容量方面的發(fā)展：接口標準、存儲密度等； 主存儲器管理技術分為兩大類 實存儲器管理 虛擬存儲器管理,Page 5,第四章 存儲器管理,存儲器的物理組織、多級存儲器 存儲組織是指在存儲技術和CPU尋址技術許可的范圍內(nèi)組織合理的存儲結構。 其依據(jù)是訪問速度匹配關系、容量要求和價格。 “寄存器-內(nèi)存-外存”結構

3、“寄存器-緩存-內(nèi)存-外存”結構； 微機中的存儲層次組織： 訪問速度越慢，容量越大，價格越便宜； 最佳狀態(tài)應是各層次的存儲器都處于均衡的繁忙狀態(tài)（如：緩存命中率正好使主存讀寫保持繁忙）；,Page 6,第四章 存儲器管理,快速緩存： Data Cache TLB(Translation Lookaside Buffer) 內(nèi)存：DRAM, SDRAM等； 外存：軟盤、硬盤、光盤、磁帶等；,Page 7,第四章 存儲器管理,主存儲器管理功能 存儲分配和回收 分配和回收算法及相應的數(shù)據(jù)結構 地址變換和重定位 可執(zhí)行文件生成中的鏈接技術 程序加載(裝入)時的重定位技術 進程運行時硬件和軟件的地址變換

4、技術和機構 存儲共享和保護 代碼和數(shù)據(jù)共享 地址空間訪問權限（讀、寫、執(zhí)行） 存儲器擴充：存儲器的邏輯組織和物理組織； 由應用程序控制：覆蓋； 由OS控制：交換（整個進程空間），虛擬存儲的請求調(diào)入和預調(diào)入（部分進程空間）,Page 8,第四章 存儲器管理,程序的裝入和鏈接 連續(xù)分配方式 基本分頁存儲管理 基本分段存儲管理 虛擬存儲器的基本概念 請求分頁存儲管理方式 頁面置換算法 請求分段存儲管理方式,Page 9,程序的裝入和鏈接,程序的裝入 程序的鏈接,Page 10,程序的裝入,多道程序環(huán)境下，程序要運行必須為之創(chuàng)建進程，而創(chuàng)建進程的第一件事就是分配內(nèi)存 源程序要運行通常經(jīng)過編譯（comp

5、ile）鏈接(link)裝入(load)等幾個步驟,Page 11,4.1 程序的裝入和鏈接,圖 4-1 對用戶程序的處理步驟,Page 12,4.1.1 程序的裝入,1. 絕對裝入方式(Absolute Loading Mode),2. 可重定位裝入方式(Relocation Loading Mode),3. 動態(tài)運行時裝入方式(Dynamic Run-time Loading),Page 13,程序的裝入,絕對裝入方式(Absolute Loading Mode) 事先確定了程序?qū)Ⅰv留在內(nèi)存的什么位置，即在內(nèi)存中的絕對地址 裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實際內(nèi)存地址完全相同，

6、故不需對程序和數(shù)據(jù)的地址進行修改 絕對地址的產(chǎn)生 程序員直接賦予。不僅要求程序員熟悉內(nèi)存使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。通常在程序中采用符號地址，在編譯或匯編時，再將符號地址轉(zhuǎn)換為絕對地址。 編譯或匯編時產(chǎn)生,Page 14,程序的裝入,可重定位裝入方式(Relocation Loading Mode) 絕對裝入方式只能將目標模塊裝入到內(nèi)存中事先指定的位置 在多道程序環(huán)境下，不可能預知目標模塊放在內(nèi)存中的地址，因此絕對裝入方式不適合在多道環(huán)境下使用 程序中目標模塊的地址通常從0開始，其他地址都是相對于0計算相對地址 把在裝入時對目標程序中指令和數(shù)據(jù)的地址修改過

7、程稱為重定位，又因為地址變換通常是在裝入時一次完成的，以后不再改變，故稱為靜態(tài)重定位,Page 15,程序的裝入,作業(yè)裝入內(nèi)存時的情況,缺點：不斷的分配和回收，造成內(nèi)存中小空閑塊很多，總空閑空間量夠，但分配不了 辦法：緊湊（移動），但該裝入方法不支持,Page 16,將程序加載到10000？,程序的裝入,將程序移動到20000？,Page 17,程序的裝入,動態(tài)運行時裝入方式(Denamic Run-time Loading) 可重定位方式不允許程序運行時在內(nèi)存中移動位置 動態(tài)運行時的裝入程序，是在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序

8、真正要執(zhí)行時才進行。因此，裝入內(nèi)存后的所有地址都仍是相對地址,Page 18,程序的裝入和鏈接,程序的裝入 程序的鏈接,Page 19,4.1 程序的裝入和鏈接,圖 4-1 對用戶程序的處理步驟,Page 20,4.1.2 程序的鏈接,1. 靜態(tài)鏈接方式(Static Linking),2. 裝入時動態(tài)鏈接(Load-time Dynamic Linking),3. 運行時動態(tài)鏈接(Run-time Dynamic Linking),Page 21,程序的鏈接,靜態(tài)鏈接方式(Static Linking) 在程序運行前，先將各目標模塊及所需的庫函數(shù)鏈接成一個完整的裝配模塊，以后不再拆開 在將這

9、幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個問題 對相對地址進行修改 變換外部調(diào)用符號,Page 22,程序的鏈接,Page 23,程序的鏈接,裝入時動態(tài)鏈接(Loadtime Dynamic Linking) 將用戶的源程序編譯后所得的一組目標模塊在裝入內(nèi)存時采用邊裝入邊鏈接的方式 便于修改和更新 便于實現(xiàn)對目標模塊的共享,Page 24,程序的鏈接,Page 25,程序的鏈接,運行時動態(tài)鏈接(Run-time Dynamic Linking) 應用程序在每次運行的模塊可能不相同 運行時動態(tài)鏈接方式將對某些模塊的鏈接推遲到執(zhí)行時才進行，即在執(zhí)行過程中，當發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，

10、立即由OS去找到該模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上 凡在執(zhí)行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間,Page 26,Page 27,第四章 存儲器管理,程序的裝入和鏈接 連續(xù)分配方式 基本分頁存儲管理 基本分段存儲管理 虛擬存儲器的基本概念 請求分頁存儲管理方式 頁面置換算法 請求分段存儲管理方式,Page 28,連續(xù)分配方式,單一連續(xù)分配 固定分區(qū)分配 動態(tài)分區(qū)分配 可重定位分區(qū)分配 對換（Swapping）,Page 29,單一連續(xù)分配,連續(xù)分配方式為一個用戶程序分配一個連續(xù)的內(nèi)存空間 單一連續(xù)分配

11、是最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中 把內(nèi)存分為 系統(tǒng)區(qū)：OS使用，通常放在內(nèi)存低址部分 用戶區(qū)：用戶可使用的全部內(nèi)存空間 存儲器保護機構不健全，易造成系統(tǒng)破壞 優(yōu)點：易于管理 缺點：對要求內(nèi)存空間少的程序，造成內(nèi)存浪費；程序全部裝入，很少使用的程序部分也占用內(nèi)存,Page 30,單一連續(xù)分配,用戶程序,位于,RAM,中的,操作系統(tǒng),0,xFFF,.,0,位于,RAM,中的,操作系統(tǒng),用戶程序,0,ROM,中的,設備驅(qū)動程序,用戶程序,位于,RAM,中的,操作系統(tǒng),0,單一連續(xù)區(qū)存儲管理,Page 31,連續(xù)分配方式,單一連續(xù)分配 固定分區(qū)分配 動態(tài)分區(qū)分配 可重定

12、位分區(qū)分配 對換（Swapping）,Page 32,固定分區(qū)分配,最簡單的可運行多道程序的存儲管理方式 內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè) 劃分分區(qū)的方法 分區(qū)大小相等： 即使所有的內(nèi)存分區(qū)大小相等 太大：浪費 太?。翰粔蛴?分區(qū)大小不等： 劃分為多個大、中、小搭配的分區(qū) 根據(jù)程序大小決定所使用的分區(qū) 大班在大教室、小班在小教室,Page 33,內(nèi)存分配 分區(qū)的信息根據(jù)分區(qū)使用表管理,固定分區(qū)分配,20,使用界地址寄存器 采用靜態(tài)重定位,問題：并發(fā)進程數(shù)受分區(qū)個數(shù)的制約！ 出現(xiàn)：有內(nèi)存卻不能運行程序或大進程無法運行！,Page 34,連續(xù)分配方式,單一連續(xù)分配

13、固定分區(qū)分配 動態(tài)分區(qū)分配 可重定位分區(qū)分配 對換（Swapping）,Page 35,動態(tài)分區(qū)分配,根據(jù)進程的實際需要，動態(tài)地為之分配內(nèi)存空間 分配中數(shù)據(jù)結構 空閑分區(qū)表 記錄每個空閑分區(qū)的情況 空閑分區(qū)鏈 實現(xiàn)對空閑分區(qū)的分配和鏈接,Page 36,動態(tài)分區(qū)分配,分區(qū)分配算法 首次適應算法FF 循環(huán)首次適應算法 最佳適應算法 最差適應算法,Page 37,動態(tài)分區(qū)分配,分區(qū)分配算法 首次適應算法FF 空閑分區(qū)鏈以地址遞增順序鏈接 分配時從鏈首開始查找，找到一個大小可滿足的空閑分區(qū)，劃出一塊給請求者 優(yōu)點：簡單；優(yōu)先利用低地址空閑區(qū)，保留高地址大空閑區(qū) 缺點：會造成在低地址部分很多難以利用的

14、小空閑分區(qū)，查找效率低 循環(huán)首次適應算法 每次分配時從上一次找到空閑分區(qū)的下一個空閑區(qū)開始查找 優(yōu)點：減少查找空閑分區(qū)開銷，空閑分區(qū)分布更均勻 缺點：缺乏大的空閑區(qū),Page 38,動態(tài)分區(qū)分配,最佳適應算法 空閑區(qū)按容量由小到大排序 每次分配時，把能滿足要求、又是最小的分區(qū)分配給作業(yè) 優(yōu)點：不缺乏大的空閑區(qū) 缺點：會在存儲器中留直許多難以利用的小分區(qū)“零頭（或碎片）”；查找效率低 最差適應算法 空閑區(qū)按容量由大到小排序 每次分配時，把能滿足要求、又是最大的分區(qū)分配給作業(yè) 優(yōu)點：剩余的空間最大化，不出現(xiàn)太小的“零頭” 缺點：缺乏大的空閑區(qū),首次適應被認為最好、最快，其次是循環(huán)，最佳最差（每次分

15、配后剩下小碎片，難再分，不得不經(jīng)常壓縮內(nèi)存，反而浪費CPU）,Page 39,動態(tài)分區(qū)分配,分區(qū)分配操作 分配內(nèi)存,解決碎片問題,Page 40,動態(tài)分區(qū)分配,分區(qū)分配操作 回收內(nèi)存 進程運行結束釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首地址，把它插入到空閑鏈表中。根據(jù)回收區(qū)的位置，有四種情況需處理： 回收區(qū)與插入點的前一個空閑分區(qū)相鄰接 回收區(qū)與插入點的后一個空閑分區(qū)相鄰接 回收區(qū)同時與插入點的前、后兩個分區(qū)相鄰接 回收區(qū)不與任何空閑區(qū)鄰接,Page 41,動態(tài)分區(qū)分配,Page 42,2) 回收內(nèi)存,回收區(qū),F1,F2,回收區(qū),F2,回收區(qū),F1,回收區(qū),回收區(qū),Page 43,動態(tài)分區(qū)分配,分區(qū)式存

16、儲管理的優(yōu)缺點 優(yōu)點： 便于動態(tài)申請內(nèi)存 便于共享內(nèi)存 便于動態(tài)鏈接 缺點： 碎片問題(外碎片)，要求連續(xù)的內(nèi)存空間，內(nèi)存利用率不高，受實際內(nèi)存容量限制,Page 44,動態(tài)分區(qū)分配,碎片問題 經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片 造成存儲資源的浪費 碎片問題的解決 緊湊技術：通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域 （緊縮技術，緊致技術，浮動技術，搬家技術） 問題：開銷大；移動時機,Page 45,連續(xù)分配方式,單一連續(xù)分配 固定分區(qū)分配 動態(tài)分區(qū)分配 可重定位分區(qū)分配 對換（S

17、wapping）,Page 46,4.2.4 可重定位分區(qū)分配,1. 動態(tài)重定位的引入,80kb,用戶程序9,用戶程序6,用戶程序3,用戶程序1,操作系統(tǒng),緊湊,Page 47,可重定位分區(qū)分配,動態(tài)重定位的引入 連續(xù)分配存在的問題 必須有足夠大的連續(xù)空間才能分配 解決方法：“拼接”或“緊湊”的引入,Page 48,可重定位分區(qū)分配,動態(tài)重定位的實現(xiàn) 作業(yè)裝入內(nèi)存后的所有地址仍是相對地址，將相對地址轉(zhuǎn)換成物理地址的工作在指令執(zhí)行時進行 需要有硬件地址變換機構的支持,Page 49,3. 動態(tài)重定位分區(qū)分配算法,動態(tài)重定位分區(qū)分配算法，與動態(tài)分區(qū)分配算法基本上相同； 差別僅在于：在這種分配算法中

18、，增加了“緊湊”功能，通常是在找不到足夠大的空閑分區(qū)來滿足用戶需求時，進行緊湊。圖4-10示出了動態(tài)重定位分區(qū)分配算法框圖。,Page 50,可重定位分區(qū)分配,動態(tài)重定位分區(qū)分配算法 在一個分區(qū)釋放后立即移動 當請求得不到滿足時再移動,Page 51,可重定位分區(qū)分配,可重定位分區(qū)的優(yōu)缺點 優(yōu)點:解決了可變分區(qū)分配所引入的“外零頭”問題。消除內(nèi)存碎片，提高內(nèi)存利用率。 缺點:提高硬件成本，緊湊時花費時間。,Page 52,連續(xù)分配方式,單一連續(xù)分配 固定分區(qū)分配 動態(tài)分區(qū)分配 可重定位分區(qū)分配 對換（Swapping）,Page 53,4.2.5 對換(Swapping),1. 對換的引入,對

19、換（也稱交換）技術，最早用在單用戶系統(tǒng)，在內(nèi)存中僅駐留一道用戶作業(yè)。所有其它作業(yè)都駐留在外存的后備隊列上，只調(diào)入一個作業(yè)進入內(nèi)存運行；此作業(yè)的時間片用完時，該作業(yè)調(diào)至外存，再將后備隊列上的另一個作業(yè)調(diào)入內(nèi)存；也讓它運行一個時間片的時間，然后又將它調(diào)出，再調(diào)下一個作業(yè)進入內(nèi)存。因為其效率太低，其CPU大約有一半的時間，都處于空閑狀態(tài)。,Page 54,對換（Swapping）,對換的引入 所謂“對換”，是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施 如果對換是

20、以整個進程為單位，稱為“整體對換”或“進程對換” 如果對換是以“頁”或“段”為單位進行的，則稱為“頁面對換”或“分段對換”，又統(tǒng)稱為“部分對換”,Page 55,4.2.5 對換(Swapping),1. 對換的引入,對換是以整個進程為單位，便稱之為“整體對換”或“進程對換”，解決內(nèi)存緊張問題； 對換是以“頁”或“段”為單位，則分別稱之為“頁面對換”或“分段對換”，又統(tǒng)稱為“部分對換”； 為了實現(xiàn)進程對換，系統(tǒng)必須能實現(xiàn)以下三方面的功能：（1）對換空間的管理；（2）進程的換出；（3）進程的換入。,Page 56,對換（Swapping）,對換空間的管理 外存中對換區(qū)主要存放從內(nèi)存中換出的進程，

21、對換空間管理的主要目標是提高進程換入和換出的速度 對換區(qū)中空閑盤塊的管理：在系統(tǒng)中配置相應的數(shù)據(jù)結構，記錄外存的使用情況。形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結構相似，即用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應包含兩項， 即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù) 對換區(qū)的分配采用連續(xù)分配方式，分配算法可以是首次適應算法、循環(huán)首次適應算法或最佳適應算法,Page 57,2. 對換空間的管理,由于對對換區(qū)的分配，是采用連續(xù)分配方式，對換區(qū) 的回收操作也可分為下述四種情況，即： （1）回收區(qū)與插入點的前一分區(qū)F1相鄰接； （2）回收區(qū)與插入點的后一分區(qū)F2相鄰接； （3）回

22、收區(qū)還同時與F1和F2二個分區(qū)相鄰接； （4）回收區(qū)的前、后沒有與之相鄰接的空閑分區(qū)。 對這幾種情況的處理方法也與動態(tài)分區(qū)分配式的方法相同。,回收區(qū),F1,F2,回收區(qū),F2,回收區(qū),F1,回收區(qū),回收區(qū),Page 58,對換（Swapping）,進程的換出與換入 進程的換出 系統(tǒng)先選擇處于“阻塞”狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動盤塊，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送未出現(xiàn)錯誤，便回收其所占用的內(nèi)存空間，并對該進程的進程控制塊做相應的修改 進程的換入 系統(tǒng)應定時地查看所有進程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進程，將其中換出時間(換出到磁盤上)最久的進程作為換入

23、進程，將之換入，直至已無可換入的進程或無可換出的進程為止,Page 59,可重定位分區(qū)分配,可重定位分區(qū)的優(yōu)缺點 優(yōu)點:解決了可變分區(qū)分配所引入的“外零頭”問題。消除內(nèi)存碎片，提高內(nèi)存利用率。 缺點:提高硬件成本，緊湊時花費時間。,Page 60,可重定位分區(qū)分配,多重分區(qū) 即一個程序可以占據(jù)主存中不連續(xù)的多個分區(qū)可以解決碎片問題 支持結構化程序設計，操作系統(tǒng)往往把一道作業(yè)分成若干片段如子程序、主程序、數(shù)據(jù)組等。 需要硬件支持（多對界地址寄存器，重定位寄存器） 管理復雜,Page 61,可重定位分區(qū)分配,多重分區(qū),Page 62,分區(qū)的保護 為了防止一道作業(yè)有意或無意地破壞操作系統(tǒng)或其它作業(yè)。

24、一般說來，沒有硬件支持，實現(xiàn)有效的存儲保護是困難的。通常采?。?界限寄存器方式 保護鍵方式 兩種措施，或二者兼而有之。,可重定位分區(qū)分配,Page 63,保護過程防止地址越界 一般由硬件提供一對寄存器： 基址寄存器：存放起始地址 限長寄存器：存放長度 （上界寄存器/下界寄存器）,可重定位分區(qū)分配,Page 64,界限寄存器保護 60K 訪問地址 =124K 則產(chǎn)生訪問地址界中斷,可重定位分區(qū)分配,Page 65,基址、限長寄存器保護 相對地址 限長寄存器的值 則產(chǎn)生訪問地址界中斷,可重定位分區(qū)分配,Page 66,防止操作越權 對于允許多個進程共享的存儲區(qū)域，每個進程都有自己的訪問權限。如果一

25、個進程對共享區(qū)域的訪問違反了權限規(guī)定，則發(fā)生操作越權 即讀寫保護,可重定位分區(qū)分配,Page 67,保護鍵方式,可重定位分區(qū)分配,Page 68,4.3 基本分頁存儲管理方式,連續(xù)分配方式會形成許多“碎片”，通過“緊湊”方法將碎片拼接成可用的大塊空間，但須為此付出很大開銷。 根據(jù)離散分配時所用基本單位的不同，又可把離散分配方式分以下三種： 1、分頁存儲管理 2、分段存儲管理 3、段頁式存儲管理,Page 69,存儲器管理,連續(xù)分配方式,離散分配方式,分頁存儲管理,分段存儲管理,基本分頁存儲管理,請求分頁存儲管理,基本分段存儲管理,請求分段存儲管理,基本分頁存儲管理,基本分段存儲管理,請求分頁存

26、儲管理,請求分段存儲管理,段頁式存儲管理,虛擬存儲器,頁面置換算法,Page 70,第四章 存儲器管理,程序的裝入和鏈接 連續(xù)分配方式 基本分頁存儲管理 基本分段存儲管理 虛擬存儲器的基本概念 請求分頁存儲管理方式 頁面置換算法 請求分段存儲管理方式,Page 71,4.3 基本分頁存儲管理方式,在分頁存儲管理的方式中，如果不具備頁面對換功能，則稱為基本的（純）分頁管理方式，它不具有支持實現(xiàn)虛擬存儲器的功能，它要求把每個作業(yè)全部裝入內(nèi)存后方能運行。,Page 72,基本分頁存儲管理,頁面與頁表 地址變換機構 兩級和多級頁表,Page 73,離散分配方式,連續(xù)分配方式要求為一個進程分配連續(xù)的內(nèi)存

27、空間，會形成許多“碎片”，盡管采用“緊湊”技術可以解決這個問題，但要為移動大量信息花去不少的處理機時間，代價較高 如果允許一個進程直接分散地裝入到許多不相鄰接的分區(qū)中，稱為離散分配方式 離散分配方式有分頁存儲管理方式和分段存儲管理方式 分頁：把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁或虛頁。從0開始編制頁號，頁內(nèi)地址是相對于0編址。,Page 74,頁面與頁表,頁面 頁面和物理塊 頁面：將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并加以編號，從0開始編制頁號，頁內(nèi)地址是相對于0編址。 物理塊：內(nèi)存按頁的大小劃分為大小相等的區(qū)域，稱為物理塊（物理頁面，頁框(frame)，幀

28、），同樣加以編號，如0塊、1塊等等 在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”,Page 75,頁面與頁表,頁面 頁面大小 頁面的大小應選擇的適中，且頁面大小應是2的冪，通常為512 B8 KB 頁面若太小 雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間， 有利于提高內(nèi)存利用率，但也會使每個進程占用較多的頁面，從而導致進程的頁表過長，占用大量內(nèi)存； 此外，還會降低頁面換進換出的效率 如果選擇的頁面較大 雖然可以減少頁表的長度，提高頁面換進換出的速度，但卻又會使頁內(nèi)碎片增大。,

29、Page 76,對某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址d可按下式求得：,例如：其系統(tǒng)的頁面大小為1KB，設A=2170B，則由下式可以求得P= ，d= 。,2. 地址結構,分頁地址中的地址結構如下：,31,12,11,0,頁內(nèi)地址 212=4*210 4KB,220=210*210 1M,2,122,2048,-,122,Page 77,頁面與頁表,例：系統(tǒng)頁面大小為1KB，邏輯地址為2170，求頁號與頁內(nèi)偏移量 頁號 P=INT2170/1024=2 頁內(nèi)偏移量d=2170 mod 1024 =122 第0頁 01023 第1

30、頁 10242047 第2頁 20483071 表示為(2,122),Page 78,頁面與頁表,主存分配 把用戶程序的任一頁分配到內(nèi)存中的任一物理塊，從而實現(xiàn)非連續(xù)的內(nèi)存分配。 問題 如何管理、如何進行地址變換。,Page 79,頁面與頁表,頁表 分頁系統(tǒng)中，將進程的每一頁離散地存儲在內(nèi)存的任一物理塊中，為每個進程建立一張頁面映像表，簡稱頁表,作用：實現(xiàn)頁號到物理塊號的映射,Page 80,頁面與頁表,頁表 列出了用戶程序的邏輯地址與其在主存中的物理地址間的對應關系。 一個頁表中包含若干個表目，表目的自然序號對應于用戶程序中的頁號，表目中的塊號是該頁對應的物理塊號。 頁表的每一個表目除了包含

31、指向頁框的指針外，還包括一個存取控制字段。 表目也稱為頁描述子。,Page 81,頁面與頁表,Page 82,基本分頁存儲管理,頁面與頁表 地址變換機構 兩級和多級頁表,Page 83,地址變換機構,基本地址變換機構 實現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，將邏輯地址中的頁號轉(zhuǎn)換為內(nèi)存中的物理塊號，通過頁表來完成 頁表的實現(xiàn) 寄存器：變換速度快、成本高，適應小型系統(tǒng)。 頁表駐留在內(nèi)存：速度較低、成本低，適應大系統(tǒng)。 頁表大多駐留在內(nèi)存中，在系統(tǒng)中設置頁表寄存器PTR(Page Table Register)，在其中存放頁表在內(nèi)存中的始址和頁表的長度 進程未執(zhí)行時，頁表的始址和頁表長度存放在本進程的PC

32、B中，當調(diào)度程序調(diào)度到某進程時，才將這兩個數(shù)據(jù)裝入頁表寄存器,Page 84,地址變換機構,地址結構 例如：32位地址，011為偏移量，1231為頁號，最大可以有1M（220）頁，每頁4KB （212） 。,31,12,11,0,Page 85,4.3.2 地址變換機構,1. 基本的地址變換機構,每個進程對應一頁表，其信息（如長度、始址）放在PCB中，執(zhí)行時將其首地址裝入頁表寄存器。 當進程要訪問某個進程邏輯地址中的數(shù)據(jù)時，分為頁號和頁內(nèi)地址兩部分； 如果頁號大于或等于頁表長度，則表示本次所訪問的地址已經(jīng)超越進程的地址空間。,Page 86,地址變換機構,Page 87,地址變換機構,地址變換

33、過程,指令 LOAD 1,2500 的地址變換過程（塊大小為1024B）,Page 88,地址變換過程 把虛擬地址2500轉(zhuǎn)換成頁號P=2，位移量W=452； 如果頁號2大于頁表大小，則中斷；否則繼續(xù)； 頁號2與頁表起址1000運算（1000+2*20，設頁描述子大小為20）得到頁描述子地址為1040； 從頁描述子中讀取塊號8； 根據(jù)頁描述子的“存取控制”判斷該指令是否被允許訪問內(nèi)存，如果不允許，則中斷；否則繼續(xù)； 塊號8與位移量452運算（8*1024+452=9644，1024為頁面大?。┑玫轿锢淼刂?644； 執(zhí)行LOAD操作。,地址變換機構,Page 89,2. 具有快表的地址變換機構

34、,由于頁表是存放在內(nèi)存中的，這使CPU每次要存取一個數(shù)據(jù)時，都要兩次訪問內(nèi)存。 第一次是訪問內(nèi)存中的頁表，從中找到該頁的物理塊號，將此塊號與頁內(nèi)偏移量W拼接以形成物理地址。 第二次訪問內(nèi)存時，才是從第一步所得地址中獲得所需數(shù)據(jù)（或向此地址中寫入數(shù)據(jù)），并將此頁號與高速緩存中的所有頁碼進行比較。,Page 90,地址變換機構,具有快表的地址變換機構 由于頁表是存放在內(nèi)存中，因此每次CPU存取一個數(shù)據(jù)要兩次訪問內(nèi)存 為提高地址變換速度，在地址變換機構中增設一個具有并行查詢能力的高速緩沖寄存器，又稱為“聯(lián)想寄存器”（Associative Memory）或“快表”，用以存放當前訪問的那些頁表項 快表

35、通?？纱娣?6-512個表項，如果設計得當，命中率可達90以上,Page 91,地址變換機構,Page 92,例：有一頁式系統(tǒng)，其頁表存放在主存中： 如果對主存的一次存取需要1.5s,試問實現(xiàn)一次頁面訪問的存取時間是多少? 如果系統(tǒng)加有快表,平均命中率為85%,當頁表項在快表中時,其查找時間忽略為0, 試問此時的存取時間是多少?,Page 93,答：若頁表存放在主存中，則要實現(xiàn)一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁面數(shù)據(jù)。 頁表在主存的存取訪問時間 =1.5*2=3(s) 增加快表后的存取訪問時間 =0.85*1.5+(1-0.85)*2*1.5=1.725(s),Page 94,基本分頁存儲管理,頁面與頁表 地址變換機構 兩級和多級頁表,Page 95,兩級和多級頁表,兩級和多級頁表 現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間(232264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當大的內(nèi)存空間 例如，對于一個具有32位邏輯地址空間的分頁系統(tǒng)，若規(guī)定頁面大小為4 KB即212 B，