計算機操作系統(tǒng)存儲器管理課件

1、計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理1存儲器管理存儲器管理計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理2內(nèi)容提要內(nèi)容提要 存儲器管理的相關(guān)概念存儲器管理的相關(guān)概念 連續(xù)分配方式連續(xù)分配方式 分頁式存儲管理方式分頁式存儲管理方式 分段式存儲管理方式分段式存儲管理方式 虛擬存儲器虛擬存儲器 請求分頁式存儲管理方式請求分頁式存儲管理方式 頁面置換算法頁面置換算法 請求分段式存儲管理方式請求分段式存儲管理方式計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理3存儲器管理存儲器管理 存儲器管理的對象包括內(nèi)存和外存，主存儲器管理的對象包括內(nèi)存和外存，主要討論的是內(nèi)存要討論的是內(nèi)存 計算機內(nèi)存

2、被劃分成兩部分：系統(tǒng)區(qū)和計算機內(nèi)存被劃分成兩部分：系統(tǒng)區(qū)和用戶區(qū)。存儲器的管理主要是針對用戶用戶區(qū)。存儲器的管理主要是針對用戶區(qū)的分配和管理區(qū)的分配和管理 存儲器管理的目的：一是方便用戶使用，存儲器管理的目的：一是方便用戶使用，二是提高存儲器的利用率二是提高存儲器的利用率計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理4存儲器管理的功能存儲器管理的功能 內(nèi)存的分配與回收內(nèi)存的分配與回收 地址轉(zhuǎn)換或重定位地址轉(zhuǎn)換或重定位 存儲器的擴充存儲器的擴充 存儲器共享和保護(hù)存儲器共享和保護(hù)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理5源程序從創(chuàng)建到執(zhí)行的步驟源程序從創(chuàng)建到執(zhí)行的步驟編編譯譯鏈鏈接接裝裝

3、入入計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理6源程序從創(chuàng)建到執(zhí)行的步驟源程序從創(chuàng)建到執(zhí)行的步驟計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理7存儲器管理的相關(guān)概念存儲器管理的相關(guān)概念 物理存儲器中全部物理存儲單元的集物理存儲器中全部物理存儲單元的集合所限定的空間稱為合所限定的空間稱為存儲空間存儲空間 每個存儲單元都有它自己的編號地址，每個存儲單元都有它自己的編號地址，該地址被稱為該地址被稱為絕對地址絕對地址，或，或物理地址物理地址，或?qū)嵉刂坊驅(qū)嵉刂?存儲空間的大小由系統(tǒng)的硬件配置決存儲空間的大小由系統(tǒng)的硬件配置決定定計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理8存儲器管理的相關(guān)概

4、念存儲器管理的相關(guān)概念 用戶源程序經(jīng)編譯鏈接后形成的代碼用戶源程序經(jīng)編譯鏈接后形成的代碼所限定的地址叫做該程序的所限定的地址叫做該程序的地址空間地址空間 地址空間中每個單元的地址稱為地址空間中每個單元的地址稱為相對相對地址地址，或，或邏輯地址邏輯地址，或虛地址，或虛地址計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理9存儲器管理的相關(guān)概念存儲器管理的相關(guān)概念 存儲分配要解決的問題是多道程序之存儲分配要解決的問題是多道程序之間如何共享主存的存儲空間間如何共享主存的存儲空間 解決存儲分配問題的三種方式：直接解決存儲分配問題的三種方式：直接存儲分配方式、靜態(tài)存儲分配方式、存儲分配方式、靜態(tài)存儲分配方

5、式、動態(tài)存儲分配方式動態(tài)存儲分配方式計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理10存儲器管理的相關(guān)概念存儲器管理的相關(guān)概念 把程序地址空間的邏輯地址轉(zhuǎn)換為存儲把程序地址空間的邏輯地址轉(zhuǎn)換為存儲空間的物理地址的工作叫做空間的物理地址的工作叫做地址重定位地址重定位，又叫又叫地址映射地址映射或地址變換或地址變換 地址重定位分地址重定位分靜態(tài)重定位靜態(tài)重定位和和動態(tài)重定位動態(tài)重定位計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理11地址重定位的原因地址重定位的原因 地址空間的邏輯地址往往與分配到的存地址空間的邏輯地址往往與分配到的存儲空間的物理地址不一致，而且不能用儲空間的物理地址不一致，而且不

6、能用邏輯地址在內(nèi)存中讀取信息邏輯地址在內(nèi)存中讀取信息 處理機執(zhí)行用戶程序時，所要訪問的程處理機執(zhí)行用戶程序時，所要訪問的程序和數(shù)據(jù)地址必須是實際的物理地址序和數(shù)據(jù)地址必須是實際的物理地址計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理12靜態(tài)地址重定位靜態(tài)地址重定位 靜態(tài)地址重定位：地址轉(zhuǎn)換工作是在程靜態(tài)地址重定位：地址轉(zhuǎn)換工作是在程序裝入主存時，由靜態(tài)重定位裝入程序序裝入主存時，由靜態(tài)重定位裝入程序集中一次完成集中一次完成 無硬件變換機構(gòu)無硬件變換機構(gòu) 為每個程序分配一個連續(xù)的存儲區(qū)為每個程序分配一個連續(xù)的存儲區(qū) 在程序執(zhí)行期間不能移動，主存利用率在程序執(zhí)行期間不能移動，主存利用率低低 不能

7、做到程序和數(shù)據(jù)的共享不能做到程序和數(shù)據(jù)的共享計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理13靜態(tài)地址重定位過程靜態(tài)地址重定位過程mov r1, 5001234OSmov r1, 15001234010050059901000110015001599裝入程序裝入程序作業(yè)地址空間作業(yè)地址空間存儲空間存儲空間把程序裝入起始地把程序裝入起始地址為址為1000的內(nèi)存區(qū)的內(nèi)存區(qū)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理14動態(tài)地址重定位動態(tài)地址重定位 裝入程序把程序和數(shù)據(jù)原樣裝入到已分裝入程序把程序和數(shù)據(jù)原樣裝入到已分配的存儲區(qū)中，然后把這個存儲區(qū)的起配的存儲區(qū)中，然后把這個存儲區(qū)的起始地址送入

8、重定位寄存器中。在程序執(zhí)始地址送入重定位寄存器中。在程序執(zhí)行時，再將相對地址轉(zhuǎn)換成絕對地址行時，再將相對地址轉(zhuǎn)換成絕對地址 主存利用率高主存利用率高 程序不必占有連續(xù)的存儲空間程序不必占有連續(xù)的存儲空間 便于多用戶共享同一程序便于多用戶共享同一程序計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理15動態(tài)地址重定位過程動態(tài)地址重定位過程mov r1, 5001234OSmov r1, 15001234010050059901000110015001599作業(yè)地址空間作業(yè)地址空間存儲空間存儲空間把程序裝入起始地把程序裝入起始地址為址為1000的內(nèi)存區(qū)的內(nèi)存區(qū)+1000重定位重定位寄存器寄存器計算機

9、操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理16程序的裝入方式程序的裝入方式 絕對裝入方式絕對裝入方式 可重定位方式可重定位方式 動態(tài)運行時裝入方式動態(tài)運行時裝入方式計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理17連續(xù)分配方式連續(xù)分配方式 連續(xù)分配是指為一個用戶程序分配連續(xù)分配是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間，這種方式曾被廣一個連續(xù)的內(nèi)存空間，這種方式曾被廣泛地應(yīng)用于早期的操作系統(tǒng)中。泛地應(yīng)用于早期的操作系統(tǒng)中。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理18連續(xù)分配的兩種方式連續(xù)分配的兩種方式 單一連續(xù)分配方式單一連續(xù)分配方式 分區(qū)式分配方式分區(qū)式分配方式計算機操作系統(tǒng)存儲器管

10、理計算機操作系統(tǒng)存儲器管理19連續(xù)分配方式的類型連續(xù)分配方式的類型連續(xù)分配連續(xù)分配單一連續(xù)分配存儲管理單一連續(xù)分配存儲管理分區(qū)管理分區(qū)管理固定分區(qū)存儲管理固定分區(qū)存儲管理動態(tài)分區(qū)存儲管理動態(tài)分區(qū)存儲管理計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理20單一連續(xù)分配方式單一連續(xù)分配方式 一種最簡單的存儲管理方式一種最簡單的存儲管理方式 只能用于單用戶、單任務(wù)的操作系統(tǒng)中只能用于單用戶、單任務(wù)的操作系統(tǒng)中 在這種管理方式下，內(nèi)存區(qū)分為在這種管理方式下，內(nèi)存區(qū)分為系統(tǒng)區(qū)系統(tǒng)區(qū)和和用戶區(qū)用戶區(qū)兩部分，系統(tǒng)區(qū)僅供操作系統(tǒng)兩部分，系統(tǒng)區(qū)僅供操作系統(tǒng)使用，用戶區(qū)提供給用戶使用使用，用戶區(qū)提供給用戶使用 不

11、支持虛擬存儲方式不支持虛擬存儲方式 優(yōu)點是管理簡單，易于實現(xiàn)存儲保護(hù)優(yōu)點是管理簡單，易于實現(xiàn)存儲保護(hù)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理21單一連續(xù)分配方式的缺點單一連續(xù)分配方式的缺點 系統(tǒng)的存儲空間浪費較大系統(tǒng)的存儲空間浪費較大 當(dāng)正在執(zhí)行的程序因等待某個事件，當(dāng)正在執(zhí)行的程序因等待某個事件，如等待外部設(shè)備輸入數(shù)據(jù)，處理機就如等待外部設(shè)備輸入數(shù)據(jù)，處理機就處于空閑狀態(tài)處于空閑狀態(tài) 限制了用戶程序和系統(tǒng)程序的可重入限制了用戶程序和系統(tǒng)程序的可重入性，因而主存中的程序和數(shù)據(jù)不能被性，因而主存中的程序和數(shù)據(jù)不能被共享共享 系統(tǒng)的外圍設(shè)備也只有一個程序使用，系統(tǒng)的外圍設(shè)備也只有一個程序使

12、用，因此外圍設(shè)備的利用率低因此外圍設(shè)備的利用率低計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理22地址映射和地址保護(hù)地址映射和地址保護(hù)CPU邏輯地址邏輯地址界限寄界限寄存器存器+重定位重定位寄存器寄存器內(nèi)存內(nèi)存物理地址物理地址地址錯地址錯是是否否計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理23分區(qū)存儲管理思想分區(qū)存儲管理思想 基本思想：將主存的用戶可用區(qū)劃分成基本思想：將主存的用戶可用區(qū)劃分成若干個大小不等的區(qū)域，每個進(jìn)程占據(jù)若干個大小不等的區(qū)域，每個進(jìn)程占據(jù)一個區(qū)域或多個區(qū)域，從而實現(xiàn)多道程一個區(qū)域或多個區(qū)域，從而實現(xiàn)多道程序設(shè)計環(huán)境下各并發(fā)進(jìn)程共享主存空間序設(shè)計環(huán)境下各并發(fā)進(jìn)程共享主

13、存空間計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理24固定分區(qū)管理固定分區(qū)管理 一種最簡單的可運行多道程序的存儲管一種最簡單的可運行多道程序的存儲管理方式理方式 將內(nèi)存用戶空間劃分為若干個固定大小將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，每個分區(qū)只裝入一道作業(yè)，這的區(qū)域，每個分區(qū)只裝入一道作業(yè)，這樣允許有幾道作業(yè)并發(fā)運行樣允許有幾道作業(yè)并發(fā)運行 當(dāng)有空閑分區(qū)時，便可從外存的后備作當(dāng)有空閑分區(qū)時，便可從外存的后備作業(yè)隊列中選擇一個適當(dāng)大小的作業(yè)裝入業(yè)隊列中選擇一個適當(dāng)大小的作業(yè)裝入該分區(qū)該分區(qū)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理25分區(qū)的方法分區(qū)的方法 分區(qū)大小相等：所有的內(nèi)存分

14、區(qū)大小相分區(qū)大小相等：所有的內(nèi)存分區(qū)大小相等，缺點是缺乏靈活性等，缺點是缺乏靈活性 分區(qū)大小不等：把內(nèi)存區(qū)劃分成含有多分區(qū)大小不等：把內(nèi)存區(qū)劃分成含有多個較小的分區(qū)、適量的中等分區(qū)及少量個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣，可根據(jù)程序的大小為的大分區(qū)。這樣，可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)之分配適當(dāng)?shù)姆謪^(qū)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理26內(nèi)存分配內(nèi)存分配 為了便于內(nèi)存分配，通常將這些為了便于內(nèi)存分配，通常將這些分區(qū)根據(jù)它們的大小排隊，并為之建分區(qū)根據(jù)它們的大小排隊，并為之建立一張分區(qū)使用表。表項中包含每個立一張分區(qū)使用表。表項中包含每個分區(qū)的起始地址、大小及狀態(tài)

15、（是否分區(qū)的起始地址、大小及狀態(tài)（是否已分配）。已分配）。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理27固定分區(qū)使用表固定分區(qū)使用表分區(qū)號分區(qū)號大小大小(KB)地址地址(K)狀態(tài)狀態(tài)1234153050100304575125已分配已分配已分配已分配已分配已分配已分配已分配操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A作業(yè)作業(yè)B作業(yè)作業(yè)C0125K45K75K30K計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理28連續(xù)分配方式的優(yōu)缺點連續(xù)分配方式的優(yōu)缺點 優(yōu)點：簡單優(yōu)點：簡單 缺點：內(nèi)存利用不充分。因為作業(yè)的大缺點：內(nèi)存利用不充分。因為作業(yè)的大小不可能剛好等于某個分區(qū)的大小，絕小不可能剛好等于某個分區(qū)的大

16、小，絕大多數(shù)已分配的分區(qū)中，都有一部分存大多數(shù)已分配的分區(qū)中，都有一部分存儲空間被浪費掉了，這個被浪費的空間儲空間被浪費掉了，這個被浪費的空間叫做叫做內(nèi)存碎片內(nèi)存碎片計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理29動態(tài)分區(qū)分配動態(tài)分區(qū)分配 系統(tǒng)初始化時，除了操作系統(tǒng)中常駐系統(tǒng)初始化時，除了操作系統(tǒng)中常駐主存部分以外，只存在一個空閑分區(qū)主存部分以外，只存在一個空閑分區(qū) 分配程序根據(jù)進(jìn)程的大小動態(tài)的劃分分配程序根據(jù)進(jìn)程的大小動態(tài)的劃分分區(qū)分區(qū) 特點是：各分區(qū)的大小是不定的；內(nèi)特點是：各分區(qū)的大小是不定的；內(nèi)存中分區(qū)的數(shù)目也是不定的。存中分區(qū)的數(shù)目也是不定的。計算機操作系統(tǒng)存儲器管理計算機操作系

17、統(tǒng)存儲器管理30動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表，用來記錄內(nèi)存中每個空空閑分區(qū)表，用來記錄內(nèi)存中每個空閑分區(qū)的情況：包括分區(qū)序號，分區(qū)閑分區(qū)的情況：包括分區(qū)序號，分區(qū)始址，分區(qū)大小等數(shù)據(jù)項始址，分區(qū)大小等數(shù)據(jù)項 空閑分區(qū)鏈，將所有的空閑分區(qū)鏈結(jié)空閑分區(qū)鏈，將所有的空閑分區(qū)鏈結(jié)成一個雙向鏈表成一個雙向鏈表計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理31分區(qū)分配算法分區(qū)分配算法 首次適應(yīng)算法首次適應(yīng)算法FFFF 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法 最佳適應(yīng)算法最佳適應(yīng)算法計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理32首次適應(yīng)算法首次適應(yīng)算法 要求空閑分區(qū)按地址遞

18、增的次序排要求空閑分區(qū)按地址遞增的次序排列。當(dāng)進(jìn)行內(nèi)存分配時，從空閑區(qū)鏈鏈列。當(dāng)進(jìn)行內(nèi)存分配時，從空閑區(qū)鏈鏈?zhǔn)组_始順序查找，直到找到第一個能滿首開始順序查找，直到找到第一個能滿足其大小要求的空閑區(qū)為止。分一塊給足其大小要求的空閑區(qū)為止。分一塊給請求者，余下部分仍留在空閑鏈中。請求者，余下部分仍留在空閑鏈中。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理33首次適應(yīng)算法的特點首次適應(yīng)算法的特點 優(yōu)先利用低地址部分的空閑分區(qū)，保優(yōu)先利用低地址部分的空閑分區(qū)，保留了高地址部分的大空閑區(qū)留了高地址部分的大空閑區(qū) 低地址端可能留下許多很小的空閑分低地址端可能留下許多很小的空閑分區(qū)，而每次查找是從低地址

19、部分開始，區(qū)，而每次查找是從低地址部分開始，會增加查找開銷會增加查找開銷計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理34循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法 由首次適應(yīng)算法演化而來。在為進(jìn)由首次適應(yīng)算法演化而來。在為進(jìn)程分配內(nèi)存空間時，不再每次都從鏈?zhǔn)壮谭峙鋬?nèi)存空間時，不再每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)，從中劃分一個能滿足要求的空閑分區(qū)，從中劃分出一塊與請求大小相等的內(nèi)存空間分配出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。給作業(yè)。計算機操作系統(tǒng)存儲器管理計

20、算機操作系統(tǒng)存儲器管理35循環(huán)首次適應(yīng)算法的特點循環(huán)首次適應(yīng)算法的特點 使內(nèi)存中的空閑分區(qū)分布得更均勻，使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時的開銷從而減少了查找空閑分區(qū)時的開銷 缺乏大的空閑分區(qū)缺乏大的空閑分區(qū)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理36最佳適應(yīng)算法最佳適應(yīng)算法 要掃描所有的空閑分區(qū)，以獲得能要掃描所有的空閑分區(qū)，以獲得能滿足進(jìn)程需求的且為最小的空閑區(qū)。如滿足進(jìn)程需求的且為最小的空閑區(qū)。如果該空閑分區(qū)大于作業(yè)的大小，則將剩果該空閑分區(qū)大于作業(yè)的大小，則將剩余空閑區(qū)仍留在空閑區(qū)鏈表中?？蓮男∮嗫臻e區(qū)仍留在空閑區(qū)鏈表中?？蓮男〉酱髮臻e區(qū)排序，方便查找。

21、到大對空閑區(qū)排序，方便查找。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理37最佳適應(yīng)算法的特點最佳適應(yīng)算法的特點 因為分配分區(qū)要查找整個鏈表，所以因為分配分區(qū)要查找整個鏈表，所以比首次適應(yīng)算法效率低比首次適應(yīng)算法效率低 因為它可能把主存劃分得更小，成為因為它可能把主存劃分得更小，成為無用的碎片，所以它比首次適應(yīng)要浪無用的碎片，所以它比首次適應(yīng)要浪費更多的存儲空間費更多的存儲空間計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理38分區(qū)分配操作分區(qū)分配操作 分配內(nèi)存分配內(nèi)存 回收內(nèi)存回收內(nèi)存計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理39分配內(nèi)存操作分配內(nèi)存操作 利用某種算法，從空閑分區(qū)中

22、找到所利用某種算法，從空閑分區(qū)中找到所需大小的分區(qū)需大小的分區(qū) 若找到的空閑分區(qū)和請求的分區(qū)的差若找到的空閑分區(qū)和請求的分區(qū)的差值大于事先規(guī)定的不再切割的剩余分值大于事先規(guī)定的不再切割的剩余分區(qū)的大小，則將空閑分區(qū)一分為二，區(qū)的大小，則將空閑分區(qū)一分為二，一部分分配給進(jìn)程，另一部分仍作為一部分分配給進(jìn)程，另一部分仍作為空閑區(qū)留在表中空閑區(qū)留在表中 將分配區(qū)的首址返回給調(diào)用者將分配區(qū)的首址返回給調(diào)用者計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理40回收內(nèi)存時遇到的情況回收內(nèi)存時遇到的情況F1回收區(qū)回收區(qū)回收區(qū)回收區(qū)回收區(qū)回收區(qū)F1F2F2計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理41分

23、區(qū)管理的優(yōu)點分區(qū)管理的優(yōu)點 實現(xiàn)了多道程序共享主存實現(xiàn)了多道程序共享主存 實現(xiàn)分區(qū)管理的系統(tǒng)設(shè)計相對簡單，實現(xiàn)分區(qū)管理的系統(tǒng)設(shè)計相對簡單，不需要更多的系統(tǒng)軟硬件開銷不需要更多的系統(tǒng)軟硬件開銷 實現(xiàn)存儲保護(hù)的手段也比較簡單實現(xiàn)存儲保護(hù)的手段也比較簡單計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理42分區(qū)管理的缺點分區(qū)管理的缺點 主存利用不夠充分。系統(tǒng)中總有一部主存利用不夠充分。系統(tǒng)中總有一部分存貯空間得不到利用，這部分被浪分存貯空間得不到利用，這部分被浪費的空間叫內(nèi)存碎片費的空間叫內(nèi)存碎片 沒有實現(xiàn)主存的擴充問題。沒有實現(xiàn)主存的擴充問題。 當(dāng)作業(yè)的當(dāng)作業(yè)的地址空間大于存儲空間時，作業(yè)無法地址空

24、間大于存儲空間時，作業(yè)無法運行。也即作業(yè)的地址空間受實際存運行。也即作業(yè)的地址空間受實際存儲空間限制儲空間限制計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理43可重定位分區(qū)分配原理可重定位分區(qū)分配原理 如果作業(yè)請求的存儲空間大于系統(tǒng)如果作業(yè)請求的存儲空間大于系統(tǒng)中任何一個分區(qū)，但小于這些分區(qū)容量中任何一個分區(qū)，但小于這些分區(qū)容量的總和時，利用動態(tài)重定位方法，移動的總和時，利用動態(tài)重定位方法，移動內(nèi)存中的所有作業(yè)，使它們在內(nèi)存相鄰內(nèi)存中的所有作業(yè)，使它們在內(nèi)存相鄰接。這樣，我們不需要對作業(yè)做任何修接。這樣，我們不需要對作業(yè)做任何修改，只要用該作業(yè)在內(nèi)存的新起始地址，改，只要用該作業(yè)在內(nèi)存的新起

25、始地址，去置換原來的起始地址即可。去置換原來的起始地址即可。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理44緊湊緊湊 這種通過移動內(nèi)存中作業(yè)的位置，這種通過移動內(nèi)存中作業(yè)的位置，把原來多個分散的小的空閑分區(qū)拼接成把原來多個分散的小的空閑分區(qū)拼接成一個大空閑分區(qū)的方法，稱為一個大空閑分區(qū)的方法，稱為“拼接拼接”或或“緊湊緊湊”。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理45緊湊的示意圖緊湊的示意圖操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序1用戶程序用戶程序2用戶程序用戶程序3用戶程序用戶程序410K30K14K26K操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序1用戶程序用戶程序2用戶程序用戶程序3用戶程序用

26、戶程序480K計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理46動態(tài)重定位的實現(xiàn)動態(tài)重定位的實現(xiàn)LOAD1,25003650100250050002500相對地址10000重定位寄存器LOAD1,250036510000101001250015000作業(yè)J處理機一側(cè)存儲器一側(cè)主存計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理47動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)分配算法請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首批空閑分區(qū)總和u.size?進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否計算機

27、操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理48擴充內(nèi)存擴充內(nèi)存的方法的方法 覆蓋覆蓋 對換對換計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理49覆蓋技術(shù)覆蓋技術(shù) 覆蓋是指一個作業(yè)中的若干程序段或數(shù)覆蓋是指一個作業(yè)中的若干程序段或數(shù)據(jù)段共享主存的某個區(qū)域據(jù)段共享主存的某個區(qū)域 覆蓋技術(shù)解決在小的存儲空間運行大作覆蓋技術(shù)解決在小的存儲空間運行大作業(yè)的問題業(yè)的問題 覆蓋技術(shù)可以覆蓋技術(shù)可以讓那些不會同時執(zhí)行的程讓那些不會同時執(zhí)行的程序段共用同一個主存區(qū)序段共用同一個主存區(qū) 程序執(zhí)行時，把不要求同時裝入主存的程序執(zhí)行時，把不要求同時裝入主存的程序段組成一組，即程序段組成一組，即覆蓋段覆蓋段，并分配同

28、，并分配同一個主存區(qū)（覆蓋區(qū)）。覆蓋段與覆蓋一個主存區(qū)（覆蓋區(qū)）。覆蓋段與覆蓋區(qū)一一對應(yīng)。區(qū)一一對應(yīng)。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理50覆蓋技術(shù)舉例覆蓋技術(shù)舉例例：一個作業(yè)由六個程序段組成，下圖給出了例：一個作業(yè)由六個程序段組成，下圖給出了各程序段之間的邏輯調(diào)用關(guān)系。各程序段之間的邏輯調(diào)用關(guān)系。主程序主程序(30K)P1 (8K)P2 (10K)P11 (15K)P21 (20K)P22 (25K)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理51內(nèi)存分配的覆蓋結(jié)構(gòu)內(nèi)存分配的覆蓋結(jié)構(gòu)OS主程序主程序 (30K)覆蓋區(qū)覆蓋區(qū)0 (10K)覆蓋區(qū)覆蓋區(qū)1 (25K)P1P2P1

29、1P21P22計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理52覆蓋技術(shù)覆蓋技術(shù) 當(dāng)執(zhí)行程序引用當(dāng)前尚未裝入覆蓋區(qū)的當(dāng)執(zhí)行程序引用當(dāng)前尚未裝入覆蓋區(qū)的覆蓋中的例程時，則調(diào)用覆蓋管理控制覆蓋中的例程時，則調(diào)用覆蓋管理控制程序，請求將所需的覆蓋段裝入覆蓋區(qū)程序，請求將所需的覆蓋段裝入覆蓋區(qū)中，系統(tǒng)響應(yīng)請求，并自動將所需覆蓋中，系統(tǒng)響應(yīng)請求，并自動將所需覆蓋裝入主存覆蓋區(qū)中裝入主存覆蓋區(qū)中 覆蓋技術(shù)的關(guān)鍵是提供正確的覆蓋結(jié)構(gòu)。覆蓋技術(shù)的關(guān)鍵是提供正確的覆蓋結(jié)構(gòu)。通常覆蓋技術(shù)主要用于系統(tǒng)程序的主存通常覆蓋技術(shù)主要用于系統(tǒng)程序的主存管理上管理上 特點：打破了必須將一個作業(yè)的全部信特點：打破了必須將一個

30、作業(yè)的全部信息裝入主存后才能運行的限制息裝入主存后才能運行的限制計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理53交換技術(shù)交換技術(shù) 交換技術(shù)是指系統(tǒng)根據(jù)需要把主存中暫交換技術(shù)是指系統(tǒng)根據(jù)需要把主存中暫時不運行的某個時不運行的某個( (或某些或某些) )作業(yè)部分或全作業(yè)部分或全部移到外存，而把外存中的某個部移到外存，而把外存中的某個( (或某或某些些) )作業(yè)移到相應(yīng)的主存，并使其投入作業(yè)移到相應(yīng)的主存，并使其投入運行運行 用輔存作為交換區(qū)，讓多用戶程序在較用輔存作為交換區(qū)，讓多用戶程序在較小的存儲空間中通過不斷地?fù)Q入小的存儲空間中通過不斷地?fù)Q入/ /換出換出而得到運行。而得到運行。計算機操作

31、系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理54交換的時機交換的時機 作業(yè)的進(jìn)程用完時間片或等待輸入輸出作業(yè)的進(jìn)程用完時間片或等待輸入輸出 作業(yè)要求擴充存貯而得不到滿足時作業(yè)要求擴充存貯而得不到滿足時計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理55交換技術(shù)的關(guān)鍵交換技術(shù)的關(guān)鍵 設(shè)法減少每次交換的信息量。為此，常設(shè)法減少每次交換的信息量。為此，常將作業(yè)的副本保留在外存，每次換出時，將作業(yè)的副本保留在外存，每次換出時，僅換出那些修改過的信息即可僅換出那些修改過的信息即可 交換主要是在作業(yè)或進(jìn)程之間進(jìn)行，而交換主要是在作業(yè)或進(jìn)程之間進(jìn)行，而覆蓋則可以在同一個或不同作業(yè)間進(jìn)行覆蓋則可以在同一個或不同作業(yè)

32、間進(jìn)行 交換打破了一個程序一旦進(jìn)入主存便一交換打破了一個程序一旦進(jìn)入主存便一直運行到結(jié)束的限制直運行到結(jié)束的限制計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理56離散分配方式的分類離散分配方式的分類 分頁存儲管理分頁存儲管理 分段存儲管理分段存儲管理 段頁式存儲管理段頁式存儲管理計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理57分頁存儲管理方式分頁存儲管理方式 在分區(qū)存儲管理中，要求作業(yè)放在一個在分區(qū)存儲管理中，要求作業(yè)放在一個連續(xù)的存儲區(qū)域，因而會產(chǎn)生碎片連續(xù)的存儲區(qū)域，因而會產(chǎn)生碎片 要解決碎片問題，系統(tǒng)就要花費很高的要解決碎片問題，系統(tǒng)就要花費很高的代價去拼接它們代價去拼接它們 頁式

33、存儲管理的引入，是為了頁式存儲管理的引入，是為了解決碎片解決碎片問題問題計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理58實現(xiàn)原理實現(xiàn)原理 將一個進(jìn)程的邏輯地址空間分成將一個進(jìn)程的邏輯地址空間分成若干個大小相等的若干個大小相等的頁頁，同時把內(nèi)存空，同時把內(nèi)存空間以與頁相等的大小劃分為大小相等間以與頁相等的大小劃分為大小相等的內(nèi)存塊（物理塊），這些內(nèi)存塊為的內(nèi)存塊（物理塊），這些內(nèi)存塊為系統(tǒng)中的任何進(jìn)程所共享。在為進(jìn)程系統(tǒng)中的任何進(jìn)程所共享。在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的分配內(nèi)存時，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以不相鄰若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于

34、進(jìn)程的最后一頁接的物理塊中。由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為碎片，稱之為“頁內(nèi)碎片頁內(nèi)碎片”。 計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理59頁面和物理塊頁面和物理塊 頁面：進(jìn)程的邏輯地址空間分成若干個頁面：進(jìn)程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各大小相等的片，稱為頁面或頁，并為各頁加以編號，從頁加以編號，從0 0開始開始 物理塊：內(nèi)存空間被分成與頁面相同大物理塊：內(nèi)存空間被分成與頁面相同大小的若干個存儲塊，稱為物理塊或內(nèi)存小的若干個存儲塊，稱為物理塊或內(nèi)存塊，塊， 也同樣為它們加以編號，如也同樣為它們加

35、以編號，如0 0塊、塊、1 1塊等等塊等等計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理60頁面大小頁面大小 在分頁系統(tǒng)中的頁面其大小應(yīng)適中。頁在分頁系統(tǒng)中的頁面其大小應(yīng)適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，面若太小，一方面雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，從而減少了內(nèi)存碎片的總空間， 有利于提高有利于提高內(nèi)存利用率，但另一方面也會使每個進(jìn)程占內(nèi)存利用率，但另一方面也會使每個進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長，用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存；占用大量內(nèi)存； 此外，還會降低頁面換進(jìn)換此外，還會降低頁面換進(jìn)換出的效率。然而，如果選擇的頁面較大，

36、雖出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進(jìn)換出然可以減少頁表的長度，提高頁面換進(jìn)換出的速度，但卻又會使頁內(nèi)碎片增大。因此，的速度，但卻又會使頁內(nèi)碎片增大。因此，頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2 2的冪，通常為的冪，通常為512 B8 KB512 B8 KB。 計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理61頁面地址結(jié)構(gòu)頁面地址結(jié)構(gòu)分頁地址結(jié)構(gòu)如下：分頁地址結(jié)構(gòu)如下：頁頁 號號 P位移量位移量W3112110 對某特定機器，其地址結(jié)構(gòu)是一定的。對某特定機器，其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中的地址為若給定

37、一個邏輯地址空間中的地址為A A，頁，頁面的大小為面的大小為L L，則頁號，則頁號P P和頁內(nèi)地址和頁內(nèi)地址d d可按下可按下式求得：式求得： MODLAdLAINTP計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理62頁表的結(jié)構(gòu)頁表的結(jié)構(gòu)頁號頁號用戶程序用戶程序0 0頁頁1 1頁頁2 2頁頁3 3頁頁4 4頁頁5 5頁頁n n頁頁0 02 21 13 32 26 63 38 84 45 59 90 01 12 23 34 45 56 67 78 89 91010塊號塊號內(nèi)存內(nèi)存頁表頁表計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理63地址變換機構(gòu)地址變換機構(gòu)頁表寄存器頁表寄存器頁表始址頁表

38、始址頁表長度頁表長度頁號頁號頁內(nèi)地址頁內(nèi)地址1 10 0b b頁表頁表1 1邏輯地址邏輯地址L L頁號頁號塊號塊號2 23 3物理地址物理地址越界中斷越界中斷計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理64地址變換舉例地址變換舉例頁表寄存器頁表寄存器5005007 70 0100100頁表頁表邏輯地址邏輯地址L L每頁大小每頁大小10241024內(nèi)存地址：內(nèi)存地址：5 51024+100=52201024+100=52200 01 12 23 34 45 56 65 57 79 91515131310101616500500500+0=500500+0=5005 5100100計算機操作系

39、統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理65快表和聯(lián)想寄存器快表和聯(lián)想寄存器 為了提高存取速度，可在地址變換機構(gòu)為了提高存取速度，可在地址變換機構(gòu)中增設(shè)一個具有并行查找能力的高速緩中增設(shè)一個具有并行查找能力的高速緩沖寄存器組，又叫沖寄存器組，又叫聯(lián)想存儲器聯(lián)想存儲器，用來存，用來存放頁表的一部分（放頁表的一部分（快表快表）。）。 聯(lián)想存貯器的存取速度比主存高，但造聯(lián)想存貯器的存取速度比主存高，但造價也高，只能少量采用。整個系統(tǒng)通常價也高，只能少量采用。整個系統(tǒng)通常只要用只要用8 81616個寄存器就可使程序執(zhí)行個寄存器就可使程序執(zhí)行速度大大提高。速度大大提高。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)

40、存儲器管理66快表的結(jié)構(gòu)快表的結(jié)構(gòu)頁號頁號塊號塊號訪問位訪問位狀態(tài)位狀態(tài)位訪問位：指示該頁最近是否被訪問過。訪問位：指示該頁最近是否被訪問過。0 0表表示沒有被訪問，示沒有被訪問，1 1表示訪問過；表示訪問過；狀態(tài)位：指示該寄存器是否被占用。狀態(tài)位：指示該寄存器是否被占用。0 0表示表示空閑，空閑，1 1表示占用。表示占用。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理67具有快表的地址變換機構(gòu)具有快表的地址變換機構(gòu)頁表寄存器頁表寄存器頁表始址頁表始址頁表長度頁表長度頁號頁號頁內(nèi)地址頁內(nèi)地址b b頁表頁表邏輯地址邏輯地址L L頁號頁號塊號塊號物理地址物理地址越界中斷越界中斷頁號頁號 塊號塊號

41、b b輸入寄存器輸入寄存器b bd d計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理68分段存儲管理方式的引入分段存儲管理方式的引入 方便編程方便編程 分段共享分段共享 分段保護(hù)分段保護(hù) 動態(tài)鏈接動態(tài)鏈接 動態(tài)增長動態(tài)增長計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理69分段的原理分段的原理 每個作業(yè)的地址空間按照程序自身的邏每個作業(yè)的地址空間按照程序自身的邏輯關(guān)系劃分成若干段，每個段都有自己輯關(guān)系劃分成若干段，每個段都有自己的段名的段名 每個段的地址空間都是從每個段的地址空間都是從“0”0”開始編開始編址的一維地址空間址的一維地址空間 作業(yè)的地址空間是二維地址空間作業(yè)的地址空間是二維地址

42、空間 每一個邏輯地址均由兩部分組成：段號每一個邏輯地址均由兩部分組成：段號和段內(nèi)地址和段內(nèi)地址段號段號段內(nèi)地址段內(nèi)地址計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理70段表段表作業(yè)空間(MAIN) 0030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段長 基址段號(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表內(nèi)存空間0123計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理71分段系統(tǒng)的地址轉(zhuǎn)換過程分段系統(tǒng)的地址轉(zhuǎn)換過程控制寄存器段表始址段表長度2100段號S越界1 K段長

43、600段號01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理72分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別 頁是信息的物理單位，段則是信息的頁是信息的物理單位，段則是信息的邏輯單位；邏輯單位； 頁的大小固定且由系統(tǒng)硬件決定，段頁的大小固定且由系統(tǒng)硬件決定，段的長度則不固定，大小取決于用戶所的長度則不固定，大小取決于用戶所編寫的程序；編寫的程序； 分頁的作業(yè)地址空間是一維的，而分分頁的作業(yè)地址空間是一維的，而分段的作業(yè)地址空間是二維的。段的作業(yè)地址空間是二維的。計算機操作系統(tǒng)存儲器管理計算機操作

44、系統(tǒng)存儲器管理73分段系統(tǒng)的共享示意圖分段系統(tǒng)的共享示意圖在分段系統(tǒng)中，為實現(xiàn)共享，只需為文本編輯程在分段系統(tǒng)中，為實現(xiàn)共享，只需為文本編輯程序設(shè)置一個段表項，如下圖：序設(shè)置一個段表項，如下圖：進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2段表段表段長段長基址基址editoreditorData 1Data 2editorData 1Data 21608016080804040240380240280380420計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理74可重入代碼可重入代碼 可重入代碼，又稱純代碼，是一可重入代碼，又稱純代碼，是一種允許多個進(jìn)程同時訪問的代碼。為種允許多個進(jìn)程同時訪問的代碼。為使各個進(jìn)程執(zhí)行的

45、代碼完全相同，絕使各個進(jìn)程執(zhí)行的代碼完全相同，絕不允許可重入代碼在執(zhí)行中有任何改不允許可重入代碼在執(zhí)行中有任何改變。變。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理75段頁式存儲管理原理段頁式存儲管理原理 段頁式系統(tǒng)的基本原理是分段和段頁式系統(tǒng)的基本原理是分段和分頁原理的組合，即先將用戶程序分分頁原理的組合，即先將用戶程序分為若干個段，把每個段分成若干個頁，為若干個段，把每個段分成若干個頁，并為每個段賦予一個段名。并為每個段賦予一個段名。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理76作業(yè)地址空間和地址結(jié)構(gòu)作業(yè)地址空間和地址結(jié)構(gòu)主程序段主程序段子程序段子程序段數(shù)據(jù)段數(shù)據(jù)段段號段號段內(nèi)頁

46、號段內(nèi)頁號頁內(nèi)地址頁內(nèi)地址04K8K12K15K16K04K8K8K4K010K12K計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理77利用段表和頁表實現(xiàn)地址映射利用段表和頁表實現(xiàn)地址映射段號 狀態(tài) 頁表大小頁表始址0111213041頁號 狀態(tài) 存儲塊#0111213041操作系統(tǒng)主存頁表段表段表大小段表始址段表寄存器計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理78地址變換機構(gòu)地址變換機構(gòu)段表寄存器段表始址段表長度段號S頁號P段超長段表0123頁內(nèi)地址頁表0123b塊號 b塊內(nèi)地址頁表始址頁表長度計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理79存儲管理遇到的兩種情況存儲管理遇到的兩

47、種情況 作業(yè)很大，要求的內(nèi)存空間超過了內(nèi)存作業(yè)很大，要求的內(nèi)存空間超過了內(nèi)存總量，致使作業(yè)無法運行總量，致使作業(yè)無法運行 大量作業(yè)要運行，內(nèi)存容量不足以容納大量作業(yè)要運行，內(nèi)存容量不足以容納所有作業(yè)，這時只能將少數(shù)作業(yè)裝入內(nèi)所有作業(yè)，這時只能將少數(shù)作業(yè)裝入內(nèi)存，其他大量作業(yè)留在外存上存，其他大量作業(yè)留在外存上計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理80局部性原理局部性原理 在一段時間，進(jìn)程集中在一組子在一段時間，進(jìn)程集中在一組子程序或循環(huán)中執(zhí)行，導(dǎo)致所有的存儲程序或循環(huán)中執(zhí)行，導(dǎo)致所有的存儲器訪問局限于進(jìn)程地址空間的一個固器訪問局限于進(jìn)程地址空間的一個固定子集（進(jìn)程的工作集）。定子集（

48、進(jìn)程的工作集）。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理81虛擬存儲器的定義虛擬存儲器的定義 虛擬存儲器是指具有請求調(diào)入虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。存容量加以擴充的一種存儲器系統(tǒng)。虛擬存儲器的邏輯容量由內(nèi)存和外虛擬存儲器的邏輯容量由內(nèi)存和外存之和來確定，其運行速度接近于存之和來確定，其運行速度接近于內(nèi)存速度，而每位的成本接近于外內(nèi)存速度，而每位的成本接近于外存。存。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理82引入虛擬存儲器的好處引入虛擬存儲器的好處 運行大程序運行大程序 大的用戶空間大的用

49、戶空間 并發(fā)并發(fā) 易于開發(fā)易于開發(fā)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理83虛擬存儲器的特征虛擬存儲器的特征 離散性離散性 多次性多次性 對換性對換性 虛擬性虛擬性計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理84虛擬存儲器的實現(xiàn)方式虛擬存儲器的實現(xiàn)方式 分頁請求系統(tǒng)分頁請求系統(tǒng) 請求分段系統(tǒng)請求分段系統(tǒng)計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理85實現(xiàn)請求分頁實現(xiàn)請求分頁( (段段) )的硬件支持的硬件支持 請求分頁請求分頁( (段段) )的頁的頁( (段段) ) 表機制表機制 缺頁缺頁( (段段) )中斷機構(gòu)中斷機構(gòu) 地址變換機構(gòu)地址變換機構(gòu)計算機操作系統(tǒng)存儲器管理計算機

50、操作系統(tǒng)存儲器管理86虛擬存儲器的定義虛擬存儲器的定義 請求分頁存儲管理方式是建立請求分頁存儲管理方式是建立在純分頁基礎(chǔ)上的，是目前常用的在純分頁基礎(chǔ)上的，是目前常用的一種實現(xiàn)虛擬存儲器的方式。由于一種實現(xiàn)虛擬存儲器的方式。由于它換進(jìn)換出的基本單位是固定長度它換進(jìn)換出的基本單位是固定長度的頁面，所以請求分頁管理方式實的頁面，所以請求分頁管理方式實現(xiàn)起來相對容易。現(xiàn)起來相對容易。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理87頁表機制頁表機制 在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結(jié)構(gòu)仍然在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結(jié)構(gòu)仍然是頁表。其基本作用是將用戶地址空間的邏輯地是頁表。其基本作用是將用戶地址空

51、間的邏輯地址轉(zhuǎn)換為內(nèi)存空間的物理地址。址轉(zhuǎn)換為內(nèi)存空間的物理地址。頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M 外存地址外存地址計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理88實現(xiàn)請求分頁實現(xiàn)請求分頁( (段段) )的硬件支持的硬件支持 在請求分頁系統(tǒng)中，每當(dāng)要訪問的在請求分頁系統(tǒng)中，每當(dāng)要訪問的頁面不在內(nèi)存時，要產(chǎn)生一個缺頁中斷。頁面不在內(nèi)存時，要產(chǎn)生一個缺頁中斷。它是一種特殊的中斷，主要表現(xiàn)在：它是一種特殊的中斷，主要表現(xiàn)在： 在指令執(zhí)行期間產(chǎn)生和處理中斷信號在指令執(zhí)行期間產(chǎn)生和處理中斷信號 一條指令在執(zhí)行期間，可產(chǎn)生多次缺頁一條指令在執(zhí)行期間，可產(chǎn)生

52、多次缺頁中斷中斷計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理89請求分頁系統(tǒng)地址變換機構(gòu)請求分頁系統(tǒng)地址變換機構(gòu)缺頁中斷處理保留 CPU 現(xiàn)場從外存中找到缺頁內(nèi)存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS 命令 CPU 從外存讀缺頁啟動 I/O 硬件將一頁從外存換入內(nèi)存修改頁表否是是否頁表項在快表中？CPU 檢索快表訪問頁表否頁在內(nèi)存？修改訪問位和修改位形成物理地址地址變換結(jié)束否頁號頁表長度?開始程序請求訪問一頁產(chǎn)生缺頁中斷請求調(diào)頁修改快表是越界中斷是是計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理90頁面分配的三個問題頁面分配的三個問題 保證進(jìn)程正常運行所需的最少物理塊數(shù)保證進(jìn)

53、程正常運行所需的最少物理塊數(shù)的確定的確定 分配的物理塊數(shù)是固定的還是可變的分配的物理塊數(shù)是固定的還是可變的 分配的物理塊數(shù)是采取平均分配算法還分配的物理塊數(shù)是采取平均分配算法還是根據(jù)進(jìn)程大小按比例予以分配是根據(jù)進(jìn)程大小按比例予以分配計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理91頁面分配和置換策略頁面分配和置換策略 固定分配局部置換固定分配局部置換 可變分配全局置換可變分配全局置換 可變分配局部置換可變分配局部置換計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理92頁面分配算法頁面分配算法 平均分配算法平均分配算法 按比例分配算法按比例分配算法 考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法計算

54、機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理93按比例分配算法按比例分配算法若系統(tǒng)中有若系統(tǒng)中有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，則，則系統(tǒng)中的頁面數(shù)總和為：系統(tǒng)中的頁面數(shù)總和為：又設(shè)系統(tǒng)中可用的物理塊總數(shù)為又設(shè)系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程，則每個進(jìn)程能分到的物理塊數(shù)為能分到的物理塊數(shù)為bi，則有：，則有：計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理94按比例分配算法按比例分配算法 在實際應(yīng)用中，為了照顧重要的、緊迫的作在實際應(yīng)用中，為了照顧重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采用的方法

55、就是把內(nèi)存可供分配的物理塊分通常采用的方法就是把內(nèi)存可供分配的物理塊分為兩部分：一部分按比例分配給各進(jìn)程；另一部為兩部分：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，分配給各進(jìn)程。分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，分配給各進(jìn)程。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理95何時調(diào)入頁面何時調(diào)入頁面 為了確定系統(tǒng)將進(jìn)程運行時所缺的為了確定系統(tǒng)將進(jìn)程運行時所缺的頁面調(diào)入內(nèi)存的時機，可采取兩種策略：頁面調(diào)入內(nèi)存的時機，可采取兩種策略： 預(yù)調(diào)頁策略預(yù)調(diào)頁策略 請求調(diào)頁策略請求調(diào)頁策略計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理96何處調(diào)入頁面何處調(diào)入頁面 在請求分頁系統(tǒng)中，把外存分為在請求

56、分頁系統(tǒng)中，把外存分為兩部分：一部分是文件區(qū)，用于存放兩部分：一部分是文件區(qū)，用于存放文件；另一部分是對換區(qū)，用于存放文件；另一部分是對換區(qū)，用于存放對換頁面。對換頁面。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理97頁面置換算法頁面置換算法 通常，把選擇換出的頁面的算法稱為頁面置通常，把選擇換出的頁面的算法稱為頁面置換算法換算法(Page-Replacement Algorithms)。置換。置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)乃闼惴ǖ暮脡膶⒅苯佑绊懴到y(tǒng)的性能，不適當(dāng)?shù)乃惴赡軐?dǎo)致進(jìn)程發(fā)生法可能導(dǎo)致進(jìn)程發(fā)生“抖動抖動”。 一個好的頁面置換算法，應(yīng)具有較低的頁面一個好的頁面置換算法

57、，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會訪更換頻率。從理論上講，應(yīng)將那些以后不再會訪問的頁面換出，或把那些在較長時間內(nèi)不會再被問的頁面換出，或把那些在較長時間內(nèi)不會再被訪問的頁面調(diào)出。訪問的頁面調(diào)出。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理98最佳置換算法最佳置換算法 最佳置換算法是由最佳置換算法是由BeladyBelady于于19661966年提出的一種理論上的算法。其選擇年提出的一種理論上的算法。其選擇的頁面，將是永不使用的，或者是在的頁面，將是永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面。最長時間內(nèi)不再被訪問的頁面。 對于固定分配頁面方式，采用最對于固定分配頁

58、面方式，采用最佳置換算法可保證獲得最低的缺頁率。佳置換算法可保證獲得最低的缺頁率。計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理99最佳頁面置換算法舉例最佳頁面置換算法舉例 假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：慮有以下的頁面號引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理100最佳頁面置換算法舉例最佳頁面置換算法舉例 假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：慮有以下的頁面號引用串：

59、77 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理101最佳頁面置換算法舉例最佳頁面置換算法舉例 假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：慮有以下的頁面號引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理102最佳頁面置換算法舉例最佳頁面置換算法舉例 假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：慮有以下的頁面號引

60、用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理103最佳頁面置換算法舉例最佳頁面置換算法舉例 假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：慮有以下的頁面號引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12計算機操作系統(tǒng)存儲器管理計算機操作系統(tǒng)存儲器管理104最佳頁面置換算法舉例最佳頁面置換算法舉例 假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：慮有