1、12022-2-4第第3章章 存儲器管理存儲器管理n考試大綱要求考試大綱要求n（一）（一）內(nèi)存管理基礎(chǔ)內(nèi)存管理基礎(chǔ)1.內(nèi)存管理概念內(nèi)存管理概念程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護。程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護。2.交換與覆蓋交換與覆蓋3.連續(xù)分配管理方式連續(xù)分配管理方式4.非連續(xù)分配管理方式非連續(xù)分配管理方式分頁管理方式；分段管理方式；段頁式管理方式。分頁管理方式；分段管理方式；段頁式管理方式。22022-2-4存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) n多級存儲器結(jié)構(gòu)多級存儲器結(jié)構(gòu)n一般計算機，存儲層次至少應(yīng)具有三級：最高層為一般計算機，存儲層次至少應(yīng)具有三級：最高層

2、為CPU寄存寄存器，中間為主存，最底層是輔存。較高檔計算機中，根據(jù)具器，中間為主存，最底層是輔存。較高檔計算機中，根據(jù)具體功能分為體功能分為6層，如圖層，如圖寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質(zhì)32022-2-4程序的裝入程序的裝入n程序的裝入就是把程序裝入內(nèi)存空間。程序的裝入就是把程序裝入內(nèi)存空間。n采用三種方式采用三種方式u（1）絕對裝入方式：是由裝入程序根據(jù)裝入模塊中）絕對裝入方式：是由裝入程序根據(jù)裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。的地址，將程序和數(shù)據(jù)裝入內(nèi)存。u（2）可重定位方式）可重定位方式：是由裝入程序根據(jù)內(nèi)存當(dāng)前的：是由裝入程序根據(jù)內(nèi)存當(dāng)前的實際使用情況，將裝入模塊

3、裝入到內(nèi)存適當(dāng)?shù)牡胤健嶋H使用情況，將裝入模塊裝入到內(nèi)存適當(dāng)?shù)牡胤?。u（3）動態(tài)運行時裝入方式：動態(tài)運行時的裝入程序，）動態(tài)運行時裝入方式：動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序要真正執(zhí)行時才進行。到程序要真正執(zhí)行時才進行。42022-2-4程序的裝入程序的裝入n絕對裝入方式：是由裝入程序根據(jù)裝入模絕對裝入方式：是由裝入程序根據(jù)裝入模塊中的地址，將程序和數(shù)據(jù)裝入主存塊中的地址，將程序和數(shù)據(jù)裝入主存u若知道程序在內(nèi)存的位置，

4、編譯程序?qū)a(chǎn)生若知道程序在內(nèi)存的位置，編譯程序?qū)a(chǎn)生絕對地址目標(biāo)模塊絕對地址目標(biāo)模塊u絕對地址一般由編譯程序給出絕對地址一般由編譯程序給出u程序被裝入內(nèi)存后，由于程序中的邏輯地址程序被裝入內(nèi)存后，由于程序中的邏輯地址與實際內(nèi)存地址完全相同，所以不允許改變與實際內(nèi)存地址完全相同，所以不允許改變程序和數(shù)據(jù)的地址程序和數(shù)據(jù)的地址u只適于單道環(huán)境只適于單道環(huán)境52022-2-4程序的裝入程序的裝入u可重定位方式可重定位方式：是由裝入程序根據(jù)主存當(dāng)是由裝入程序根據(jù)主存當(dāng)前的實際使用情況，將裝入模塊裝入到主存前的實際使用情況，將裝入模塊裝入到主存適當(dāng)?shù)牡胤?。適當(dāng)?shù)牡胤?。F重定位：在裝入時對目標(biāo)程序中指令重

5、定位：在裝入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程。會使裝入模塊中和數(shù)據(jù)的修改過程。會使裝入模塊中的所有邏輯地址與實際裝入內(nèi)存的物的所有邏輯地址與實際裝入內(nèi)存的物理地址不同理地址不同62022-2-4程序的裝入程序的裝入u靜態(tài)重定位方式靜態(tài)重定位方式：u是指地址轉(zhuǎn)換工作是在程序裝入內(nèi)存時由裝配程序是指地址轉(zhuǎn)換工作是在程序裝入內(nèi)存時由裝配程序完成的。裝配程序根據(jù)將要裝入內(nèi)存的起始地址，完成的。裝配程序根據(jù)將要裝入內(nèi)存的起始地址，對程序模塊中有關(guān)的地址部分進行調(diào)整和修改對程序模塊中有關(guān)的地址部分進行調(diào)整和修改u（物理地址（物理地址=邏輯地址邏輯地址+程序存放在內(nèi)存的起始地程序存放在內(nèi)存的起始地址），一

6、旦確定下來之后不再改變，即靜態(tài)地址重址），一旦確定下來之后不再改變，即靜態(tài)地址重定位是在程序執(zhí)行之前完成的地址轉(zhuǎn)換。定位是在程序執(zhí)行之前完成的地址轉(zhuǎn)換。u它的優(yōu)點：無需硬件支持，容易實現(xiàn)。缺點：程序它的優(yōu)點：無需硬件支持，容易實現(xiàn)。缺點：程序經(jīng)地址重定位后不能再移動，程序在內(nèi)存空間只能經(jīng)地址重定位后不能再移動，程序在內(nèi)存空間只能連續(xù)存儲，程序很難被若干個用戶所共享。連續(xù)存儲，程序很難被若干個用戶所共享。72022-2-4程序的裝入程序的裝入u動態(tài)運行時裝入方式：動態(tài)運行時的裝動態(tài)運行時裝入方式：動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中

7、的相對地址轉(zhuǎn)換為不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序要真正執(zhí)行時才進行。程序要真正執(zhí)行時才進行。F適于多道環(huán)境F允許程序移動，如切換F動態(tài)重定位F需要特殊硬件支持（重定位寄存器）82022-2-4程序的裝入程序的裝入u動態(tài)重定位：動態(tài)重定位：u是指地址轉(zhuǎn)換工作是在程序執(zhí)行期間由硬件變換機是指地址轉(zhuǎn)換工作是在程序執(zhí)行期間由硬件變換機構(gòu)動態(tài)實現(xiàn)地址轉(zhuǎn)換的。構(gòu)動態(tài)實現(xiàn)地址轉(zhuǎn)換的。u物理地址物理地址=邏輯地址邏輯地址+重定位寄存器的內(nèi)容。重定位寄存器的內(nèi)容。u動態(tài)重定位的優(yōu)點：用戶程序在執(zhí)行過程中內(nèi)存可動態(tài)重定位的優(yōu)點：用戶程序在執(zhí)

8、行過程中內(nèi)存可移動，程序不必連續(xù)存放在內(nèi)存中，可以放在不同移動，程序不必連續(xù)存放在內(nèi)存中，可以放在不同區(qū)域，若干個用戶可以共享同一程序段或數(shù)據(jù)段。區(qū)域，若干個用戶可以共享同一程序段或數(shù)據(jù)段。缺點：需要附加硬件支持，實行存儲管理的軟件算缺點：需要附加硬件支持，實行存儲管理的軟件算法比較復(fù)雜。法比較復(fù)雜。92022-2-4程序的鏈接程序的鏈接 n鏈接程序的功能是將經(jīng)過編譯或匯編后所得到鏈接程序的功能是將經(jīng)過編譯或匯編后所得到的一組目標(biāo)模塊以及它們所需要的庫函數(shù)，裝的一組目標(biāo)模塊以及它們所需要的庫函數(shù)，裝配成一個完整的裝入模塊。配成一個完整的裝入模塊。n實現(xiàn)鏈接的方法有實現(xiàn)鏈接的方法有三種三種u靜態(tài)

9、鏈接：事先進行鏈接，以后不再拆開的鏈接方式靜態(tài)鏈接：事先進行鏈接，以后不再拆開的鏈接方式u裝入時動態(tài)鏈接：用戶源程序經(jīng)編譯后所得到的目標(biāo)裝入時動態(tài)鏈接：用戶源程序經(jīng)編譯后所得到的目標(biāo)模塊，是在裝入內(nèi)存時，邊裝入邊鏈接的。模塊，是在裝入內(nèi)存時，邊裝入邊鏈接的。u運行時動態(tài)鏈接：某些目標(biāo)模塊的鏈接，是在程序執(zhí)運行時動態(tài)鏈接：某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該（目標(biāo)）模塊時，才對它進行鏈接行中需要該（目標(biāo)）模塊時，才對它進行鏈接102022-2-4內(nèi)存保護內(nèi)存保護 內(nèi)存保護就是防止各用戶程序運行時相互內(nèi)存保護就是防止各用戶程序運行時相互被破壞被破壞,最重要的就是不能破壞操作系統(tǒng)最重要的就是不能

10、破壞操作系統(tǒng).（1）界地址寄存器保護法）界地址寄存器保護法（2）訪問授權(quán)保護）訪問授權(quán)保護112022-2-42.交換與覆蓋交換與覆蓋 n采用交換與覆蓋技術(shù)是為了節(jié)省內(nèi)存。采用交換與覆蓋技術(shù)是為了節(jié)省內(nèi)存。n交換就是系統(tǒng)根據(jù)需要把主存中暫時不運行的交換就是系統(tǒng)根據(jù)需要把主存中暫時不運行的某個（或某些）進程的部分或全部信息移到外某個（或某些）進程的部分或全部信息移到外存，而把外存中的某個（或某些）進程移到相存，而把外存中的某個（或某些）進程移到相應(yīng)的主存區(qū)，并使其投入運行應(yīng)的主存區(qū)，并使其投入運行n覆蓋就是指一個作業(yè)（或進程）或多個作業(yè)覆蓋就是指一個作業(yè)（或進程）或多個作業(yè)（或進程）的若干程序段

11、或數(shù)據(jù)段共享主存的（或進程）的若干程序段或數(shù)據(jù)段共享主存的某個區(qū)域。實現(xiàn)方法是將一個作業(yè)（或進程）某個區(qū)域。實現(xiàn)方法是將一個作業(yè)（或進程）劃分成若干個相互獨立的段，將不同時運行的劃分成若干個相互獨立的段，將不同時運行的程序段或數(shù)據(jù)段組成覆蓋。程序段或數(shù)據(jù)段組成覆蓋。122022-2-43.連續(xù)分配方式連續(xù)分配方式 u連續(xù)分配方式：為一個用戶程序分連續(xù)分配方式：為一個用戶程序分配一個連續(xù)的內(nèi)存空間配一個連續(xù)的內(nèi)存空間F單一連續(xù)分配F固定分區(qū)分配 F動態(tài)分區(qū)分配F動態(tài)重定位分區(qū)分配132022-2-4連續(xù)分配方式連續(xù)分配方式 u單一連續(xù)分配單一連續(xù)分配142022-2-4連續(xù)分配方式連續(xù)分配方式

12、u固定分區(qū)分配固定分區(qū)分配F將內(nèi)存中的用戶空間劃分為若干個固定大小將內(nèi)存中的用戶空間劃分為若干個固定大小的區(qū)域的區(qū)域F每個分區(qū)中只裝入一道作業(yè)，一個作業(yè)也只每個分區(qū)中只裝入一道作業(yè)，一個作業(yè)也只能裝入一個分區(qū)中，這樣可以裝入多個作業(yè)，能裝入一個分區(qū)中，這樣可以裝入多個作業(yè)，使它們并發(fā)執(zhí)行。當(dāng)有一個空閑分區(qū)時，便使它們并發(fā)執(zhí)行。當(dāng)有一個空閑分區(qū)時，便可從外存的后備隊列中，選擇一個適當(dāng)大小可從外存的后備隊列中，選擇一個適當(dāng)大小的作業(yè)裝入該分區(qū)；當(dāng)該作業(yè)運行完時，又的作業(yè)裝入該分區(qū)；當(dāng)該作業(yè)運行完時，又可從后備隊列中選擇另一個作業(yè)裝入該分區(qū)可從后備隊列中選擇另一個作業(yè)裝入該分區(qū)（分區(qū)大小可以相同也可

13、以不同）。（分區(qū)大小可以相同也可以不同）。 152022-2-4固定分區(qū)分配的管理特點固定分區(qū)分配的管理特點 n（1）一個作業(yè)只能裝入一個分區(qū)，不能裝入兩個）一個作業(yè)只能裝入一個分區(qū)，不能裝入兩個或多個相鄰的分區(qū)。一個分區(qū)只能裝入一個作業(yè)，或多個相鄰的分區(qū)。一個分區(qū)只能裝入一個作業(yè)，當(dāng)分區(qū)大小不能滿足作業(yè)的要求時，該作業(yè)暫時不當(dāng)分區(qū)大小不能滿足作業(yè)的要求時，該作業(yè)暫時不能裝入。能裝入。n（2）通過對）通過對“分區(qū)使用表分區(qū)使用表”的改寫，來實現(xiàn)主存的改寫，來實現(xiàn)主存的分配與回收。作業(yè)在執(zhí)行時，不會改變存儲區(qū)域，的分配與回收。作業(yè)在執(zhí)行時，不會改變存儲區(qū)域，所以采用靜態(tài)地址重定位方式。此方法易于

14、實現(xiàn)，所以采用靜態(tài)地址重定位方式。此方法易于實現(xiàn)，系統(tǒng)開銷小。系統(tǒng)開銷小。n（3）當(dāng)分區(qū)較大作業(yè)較小時，仍然浪費許多主存）當(dāng)分區(qū)較大作業(yè)較小時，仍然浪費許多主存空間空間(內(nèi)零頭）。并且分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)內(nèi)零頭）。并且分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的作業(yè)數(shù)目。行的作業(yè)數(shù)目。162022-2-4動態(tài)分區(qū)分配動態(tài)分區(qū)分配n動態(tài)分區(qū)存儲管理的基本思想是：動態(tài)分區(qū)存儲管理的基本思想是：在作業(yè)要求裝入內(nèi)存儲器時，如果當(dāng)在作業(yè)要求裝入內(nèi)存儲器時，如果當(dāng)時內(nèi)存儲器中有足夠的存儲空間滿足時內(nèi)存儲器中有足夠的存儲空間滿足該作業(yè)的需求，那么就劃分出一個與該作業(yè)的需求，那么就劃分出一個與作業(yè)相對地址空間同樣大小

15、的分區(qū)分作業(yè)相對地址空間同樣大小的分區(qū)分配給它。配給它。172022-2-4采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) n為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來記錄內(nèi)存的使用情況。的數(shù)據(jù)結(jié)構(gòu)，用來記錄內(nèi)存的使用情況。比如空閑分區(qū)的情況，為作業(yè)分配內(nèi)存空比如空閑分區(qū)的情況，為作業(yè)分配內(nèi)存空間提供依據(jù)。常用的有空閑分區(qū)表和空閑間提供依據(jù)。常用的有空閑分區(qū)表和空閑分區(qū)鏈。分區(qū)鏈。182022-2-4分區(qū)分配算法分區(qū)分配算法 n（1）首次適應(yīng)分配算法（）首次適應(yīng)分配算法（FF）n（2）循環(huán)首次適應(yīng)分配算法（）循環(huán)首次適應(yīng)分配算法（NF）n（2）最佳適應(yīng)分配算法（最佳

16、適應(yīng)分配算法（BF）n（3）最壞適應(yīng)分配算法（最壞適應(yīng)分配算法（WF）192022-2-4(1)(1)首次適應(yīng)法首次適應(yīng)法n要求空閑區(qū)按要求空閑區(qū)按首址遞增的次序組織的次序組織空閑區(qū)表（隊列）。空閑區(qū)表（隊列）。n分配：當(dāng)進程申請大小為分配：當(dāng)進程申請大小為SIZESIZE的內(nèi)存時，系的內(nèi)存時，系統(tǒng)從空閑區(qū)鏈的鏈?zhǔn)组_始查詢，直到首次找統(tǒng)從空閑區(qū)鏈的鏈?zhǔn)组_始查詢，直到首次找到等于或大于到等于或大于SIZESIZE的空閑區(qū)。從該區(qū)中劃出的空閑區(qū)。從該區(qū)中劃出大小為大小為SIZESIZE的分區(qū)分配給進程，余下的部分的分區(qū)分配給進程，余下的部分仍作為一個空閑區(qū)留在空閑區(qū)鏈中，但要修仍作為一個空閑區(qū)留在

17、空閑區(qū)鏈中，但要修改其首址和大小。改其首址和大小。n若找不到滿足要求的，則分配失敗，返回。若找不到滿足要求的，則分配失敗，返回。202022-2-4分析分析n注意：每次分配和回收后空閑區(qū)鏈都要按首址遞增的次序排序。優(yōu)點：優(yōu)點：n這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。閑區(qū)。n缺點缺點u容易產(chǎn)生過多的小地址碎片；降低了主存空間利用率。容易產(chǎn)生過多的小地址碎片；降低了主存空間利用率。u每次查找都是從低址開始，增加了查找的開銷每次查找都是從低址開始，增加了查找的開銷n改進改進u采用循環(huán)首次適應(yīng)算法。采用循環(huán)首次

18、適應(yīng)算法。212022-2-4（2 2）循環(huán)首次適應(yīng)算法）循環(huán)首次適應(yīng)算法n不是每次都從鏈?zhǔn)组_始找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)。n設(shè)置查尋指針；n循環(huán)查找方式n使內(nèi)存中的空閑分區(qū)分布得更均勻，減少了查找時的開銷，但會缺乏大的空閑分區(qū)。222022-2-4（3 3）最佳適應(yīng)法）最佳適應(yīng)法n所謂最佳就是每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免大材小用。n要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)鏈。232022-2-4最佳適應(yīng)法最佳適應(yīng)法優(yōu)點：優(yōu)點：n在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū)，必定會被選中，

19、而首次適應(yīng)法則不一定。n若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。缺點：缺點：n空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲區(qū)的大量浪費。242022-2-4（4 4）最壞適應(yīng)算法）最壞適應(yīng)算法n掃描整個空閑分區(qū)表，或鏈表，總是挑選一個最大的空閑區(qū)分割給作業(yè)使用。n要求按空閑區(qū)大小從大到小的次序組成空閑區(qū)鏈。n優(yōu)點：可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對中、小作業(yè)有利。n缺點：缺乏大的空閑分區(qū)，不利于大作

20、業(yè)。252022-2-4可重定位分區(qū)分配可重定位分區(qū)分配 n在連續(xù)分配中，必須把一個系統(tǒng)或用戶程序在連續(xù)分配中，必須把一個系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。裝入一連續(xù)的內(nèi)存空間。n不能被利用的小分區(qū)稱為不能被利用的小分區(qū)稱為“零頭零頭”或或“碎碎片片”。n將主存中的所有作業(yè)進行移動，使它們相鄰將主存中的所有作業(yè)進行移動，使它們相鄰接。這樣，原來分散的多個小分區(qū)便拼接成接。這樣，原來分散的多個小分區(qū)便拼接成一個大分區(qū)，從而就可以把作業(yè)裝入該區(qū)。一個大分區(qū)，從而就可以把作業(yè)裝入該區(qū)。n這種通過移動，把多個分散的小分區(qū)拼接成這種通過移動，把多個分散的小分區(qū)拼接成大分區(qū)的方法被稱為大分區(qū)的方法被稱為

21、“拼接拼接”或或“緊湊緊湊”，改變作業(yè)在主存中位置的工作稱為改變作業(yè)在主存中位置的工作稱為“移動移動”。262022-2-4連續(xù)分配方式比較連續(xù)分配方式比較作業(yè)個數(shù)內(nèi)部碎片外部碎片解決碎片方法相同點提高作業(yè)道數(shù)單一連續(xù)分配1有無無一個程序需全部、連續(xù)裝入內(nèi)存中。對換固定分區(qū)分配N（分區(qū)數(shù)）有無無動態(tài)分區(qū)分配不定無有緊湊272022-2-4非連續(xù)分配方式非連續(xù)分配方式n分頁管理方式n分段管理方式n段頁式管理方式282022-2-44.4.1頁面與頁表頁面與頁表 作業(yè)空間 頁表 內(nèi)存 頁表寄存器 0 1 2 3 0 1 2 3 4 5 6 7 ： 0 1 2 3 作業(yè)地址空間劃分成連續(xù)的作業(yè)地址空

22、間劃分成連續(xù)的大小相同的大小相同的頁面頁面內(nèi)存劃分成連續(xù)的大小相等內(nèi)存劃分成連續(xù)的大小相等的的塊塊（也稱為（也稱為頁框頁框） 頁面的大小與內(nèi)存塊的頁面的大小與內(nèi)存塊的大小大小完全完全相同相同作業(yè)進入內(nèi)存時其不同的作業(yè)進入內(nèi)存時其不同的頁面頁面對應(yīng)對應(yīng)于內(nèi)存中不同的于內(nèi)存中不同的塊，連續(xù)頁面可以塊，連續(xù)頁面可以對應(yīng)不對應(yīng)不連續(xù)連續(xù)的塊。的塊。 292022-2-4（1）分頁管理方式）分頁管理方式n頁面（用戶程序劃分）頁面（用戶程序劃分）把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁（page） 。從0開始編制頁號，頁內(nèi)地址是相對于0編址302022-2-4n內(nèi)存空間內(nèi)存空間按頁的大小劃分為大小相

23、等的區(qū)域，稱為塊或內(nèi)存塊（物理頁面，頁框） 在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進程的最后一頁經(jīng)常不滿一塊而形成了不可利用的碎片稱之為“頁內(nèi)碎片”邏輯上相鄰的頁，物理上不一定相鄰邏輯上相鄰的頁，物理上不一定相鄰312022-2-4n地址結(jié)構(gòu)地址結(jié)構(gòu)用戶程序的劃分是由系統(tǒng)自動完成的，對用戶是用戶程序的劃分是由系統(tǒng)自動完成的，對用戶是透明的。一般，一頁的大小為透明的。一般，一頁的大小為2的整數(shù)次冪，因的整數(shù)次冪，因此，地址的高位部分為此，地址的高位部分為頁號頁號，低位部分為，低位部分為頁內(nèi)地頁內(nèi)地址址頁號頁號 頁內(nèi)地址頁內(nèi)地址0111231頁號

24、頁號P頁內(nèi)位移量頁內(nèi)位移量W編號編號01048575相對地址相對地址04095322022-2-4頁表頁表n將頁號和頁內(nèi)地址轉(zhuǎn)換成內(nèi)存地址，必須要有一個數(shù)據(jù)結(jié)構(gòu)，用來登記頁號和塊的對應(yīng)關(guān)系和有關(guān)信息。n這樣的數(shù)據(jù)結(jié)構(gòu)稱為頁表。n頁表的作用就是實現(xiàn)從頁號到物理塊號的地址映射。332022-2-4頁表內(nèi)容頁表內(nèi)容n頁表包含以下幾個表項：頁表包含以下幾個表項：n頁號：登記程序地址空間的頁號。n塊號：登記相應(yīng)的頁所對應(yīng)的內(nèi)存塊號n其它：登記與存儲信息保護有關(guān)的信息。頁號塊號其它05165213342022-2-4地址變換機構(gòu)地址變換機構(gòu)n地址變換機構(gòu)的任務(wù)是實現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換。即把程序地址

25、轉(zhuǎn)換成內(nèi)存地址，這個轉(zhuǎn)換過程是在程序執(zhí)行過程中完成的，是動態(tài)地址映射。n在現(xiàn)代計算機系統(tǒng)中，由系統(tǒng)提供的地址映射硬件來完成地址映射工作。352022-2-4例例n設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖。362022-2-4計算時要注意：若給出的地址字為16進制，則將其轉(zhuǎn)換為二進制，然后，根據(jù)頁長及程序地址字的長度，分別取出程序地址字的高幾位和低幾位就得到頁號及頁內(nèi)地址。如頁長為2K，程序地址字為16位，則高5位為頁號，低11位為頁內(nèi)地址。372022-2-4若給出的地址字為10進制，則用公式： 程序地址字/頁長 商為頁號，余數(shù)為頁內(nèi)地址。如程序地址為8457， 頁長為4KB

26、，則8457/4096可得：商為2，余數(shù)為256。382022-2-4快表和聯(lián)想存儲器快表和聯(lián)想存儲器n在前述的頁地址變換過程中有一個嚴(yán)重的問題，那就是每一次對內(nèi)存的訪問都要訪問頁表，頁表是放在內(nèi)存中的，也就是說每一次訪問內(nèi)存的指令至少要訪問兩次內(nèi)存，運行速度要下降一半。n第一次訪問內(nèi)存中的頁表，從中找到指定頁的物理塊號，再將塊號與頁內(nèi)偏移量W拼接，形成物理地址n第二次訪問內(nèi)存時，才是從第一次所得地址中獲得所需數(shù)據(jù)（獲向此地址中寫入數(shù)據(jù)）392022-2-4n解決這個問題的一種方法是把頁表放在一組快速存儲器中（Cache），從而加快訪問內(nèi)存的速度。我們把這種快速存儲器組成的頁表稱為快表，把存放

27、在內(nèi)存中的頁表稱為慢表。n快表又叫聯(lián)想存儲器（associative memory）或 TLB（Translation lookaside buffers）用以存放當(dāng)前訪問的那些頁表項402022-2-4p頁表頁表地址越界地址越界 L比較比較P=Lpp. . .快表快表 b+頁號頁號p 頁內(nèi)地址頁內(nèi)地址dPd物理地址物理地址頁表地址寄存器頁表地址寄存器頁表長度寄存器頁表長度寄存器邏輯地址邏輯地址地址映射機制地址映射機制412022-2-4兩級頁表和多級頁表兩級頁表和多級頁表n當(dāng)頁表項很多時，僅采用一級頁表需要大片連續(xù)空間，可將頁表也分頁，并對頁表所占的空間進行索引形成外層頁表。由此構(gòu)成二級頁表

28、。n更進一步可形成多級頁表。 422022-2-4二級頁表結(jié)構(gòu)及地址映射二級頁表結(jié)構(gòu)及地址映射101110780121742n第0頁頁表1460121023第1頁頁表114115011023外部頁表012345671141151468第n頁頁存空間432022-2-4頁式存儲管理方案小結(jié)頁式存儲管理方案小結(jié)n優(yōu)點：解決了碎片問題優(yōu)點：解決了碎片問題便于管理便于管理可以使程序和數(shù)據(jù)存放在不連續(xù)的主存空間可以使程序和數(shù)據(jù)存放在不連續(xù)的主存空間n缺點：不易實現(xiàn)共享缺點：不易實現(xiàn)共享不便于動態(tài)連接不便于動態(tài)連接頁表都有可能占用較大的存儲空間。頁表都有可能占用較大的存儲空間。要

29、求有相應(yīng)的硬件支持，從而增加了系統(tǒng)要求有相應(yīng)的硬件支持，從而增加了系統(tǒng)成本，也增加了系統(tǒng)開銷成本，也增加了系統(tǒng)開銷442022-2-4（2 2）分段管理方式）分段管理方式n引入段式管理方式主要是為了滿足用戶和引入段式管理方式主要是為了滿足用戶和程序員的需要程序員的需要u方便用戶：用戶希望邏輯分段方便用戶：用戶希望邏輯分段u信息共享信息共享u信息保護信息保護u動態(tài)增長動態(tài)增長u動態(tài)連接動態(tài)連接452022-2-4分段系統(tǒng)基本原理分段系統(tǒng)基本原理分段分段n用戶程序劃分 按程序自身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內(nèi)也從0開始編址，段內(nèi)地址是連

30、續(xù)的。段的長度由相應(yīng)的邏輯信息組的長度決定，因而各段長度不等。n邏輯地址：由段號和段內(nèi)地址組成段號 段內(nèi)地址462022-2-4n內(nèi)存劃分內(nèi)存劃分內(nèi)存空間被動態(tài)的劃分為若干個長度不相內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，稱為物理段，每個物理段由起同的區(qū)域，稱為物理段，每個物理段由起始地址和長度確定始地址和長度確定n內(nèi)存分配內(nèi)存分配以段為單位分配內(nèi)存，每一個段在內(nèi)存中以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少），分配多少），但各段之間可以不連續(xù)存放但各段之間可以不連續(xù)存放472022-2-4n段表段表段映射表。每個

31、程序有一個段表段映射表。每個程序有一個段表程序的每個段在表中占有一個表項，其中程序的每個段在表中占有一個表項，其中記錄了該段在內(nèi)存中的起始地址和段的長記錄了該段在內(nèi)存中的起始地址和段的長度?？煞旁趦?nèi)存中，也可放在寄存器中。度?？煞旁趦?nèi)存中，也可放在寄存器中。段表是用于實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的段表是用于實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。映射。段號段號012段首址段首址段長度段長度58K20K100K110K260K140K482022-2-43 3、地址變換機構(gòu)、地址變換機構(gòu)段地址映射過程為：n系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和段表長度TL。n取出段號S和段內(nèi)位移W。n若STL，段號太大

32、越界。n根據(jù)段表始址找到段表，查找段號為S的表目，得到該段在內(nèi)存的起始地址。n檢查段內(nèi)地址d是否起過該段的段長SL。若超過越界。n把段首地址與段內(nèi)位移相加，形成內(nèi)存物理地址。492022-2-4地址變換機構(gòu)地址變換機構(gòu)控制寄存器段表始址段表長度2100段號S越界1 K段長600段號01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址502022-2-4n同頁地址變換一樣，在段地址變換過程中，也有兩次訪問內(nèi)存的問題。為了加快訪問內(nèi)存的速度也可采用快速存儲器組成快表。512022-2-4 Cl Cb+段號段號S S 段內(nèi)地址段內(nèi)地址d比較比較比

33、較比較b + d段段表表S= Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表長度寄存器段表長度寄存器邏輯地址邏輯地址Lb.SLb地址越界地址越界d=Ld=L地址映射及存儲保護機制地址映射及存儲保護機制地址越界地址越界地址越界地址越界比較比較522022-2-4段式存儲管理方案小結(jié)段式存儲管理方案小結(jié)優(yōu)點：優(yōu)點：便于動態(tài)申請內(nèi)存便于動態(tài)申請內(nèi)存管理和使用統(tǒng)一化管理和使用統(tǒng)一化便于共享便于共享便于動態(tài)鏈接便于動態(tài)鏈接缺點：產(chǎn)生外部碎片缺點：產(chǎn)生外部碎片532022-2-4（3 3） 段頁式存儲管理方式段頁式存儲管理方式產(chǎn)生背景產(chǎn)生背景:結(jié)合頁式段式優(yōu)點，克服二者的缺點結(jié)合頁式段式優(yōu)點

34、，克服二者的缺點n基本原理基本原理n地址變換過程地址變換過程542022-2-4基本原理基本原理n用戶程序劃分用戶程序劃分按段式劃分（對用戶來講，按段的邏輯關(guān)系進行按段式劃分（對用戶來講，按段的邏輯關(guān)系進行劃分；對系統(tǒng)講，按頁劃分每一段）劃分；對系統(tǒng)講，按頁劃分每一段）n邏輯地址邏輯地址n內(nèi)存劃分內(nèi)存劃分按頁式存儲管理方案按頁式存儲管理方案n內(nèi)存分配內(nèi)存分配以頁為單位進行分配以頁為單位進行分配段號段號段內(nèi)地址段內(nèi)地址頁號頁號頁內(nèi)地址頁內(nèi)地址552022-2-4n段表：記錄了每一段的頁表始址和頁表長度段表：記錄了每一段的頁表始址和頁表長度n頁表：記錄了邏輯頁號與內(nèi)存塊號的對應(yīng)關(guān)頁表：記錄了邏輯頁

35、號與內(nèi)存塊號的對應(yīng)關(guān)系（每一段有一個，一個程序可能有多個頁系（每一段有一個，一個程序可能有多個頁表）表）n內(nèi)存分配管理：同頁式管理內(nèi)存分配管理：同頁式管理地址變換過程地址變換過程 562022-2-4段號 狀態(tài) 頁表大小 頁表始址0111213041頁號 狀態(tài)存儲塊#0111213041操作系統(tǒng)主存頁表段表段表大小 段表始址段表寄存器圖 4-21 利用段表和頁表實現(xiàn)地址映射 572022-2-4地址變換過程地址變換過程圖 4-22 段頁式系統(tǒng)中的地址變換機構(gòu)段表寄存器段表始址段表長度段號S頁號P段超長段表0123頁內(nèi)地址頁表0123b塊號 b塊內(nèi)地址頁表始址頁表長度582022-2-4n在段頁

36、式系統(tǒng)中，為了獲得一條指令數(shù)據(jù)，在段頁式系統(tǒng)中，為了獲得一條指令數(shù)據(jù)，須三次訪問內(nèi)存。須三次訪問內(nèi)存。1、訪問內(nèi)存中的段表，從中取得頁表始址、訪問內(nèi)存中的段表，從中取得頁表始址2、訪問內(nèi)存中的頁表，從中取出該頁所在的、訪問內(nèi)存中的頁表，從中取出該頁所在的物理塊號，將該塊號與頁內(nèi)地址一起形成指物理塊號，將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址令或數(shù)據(jù)的物理地址3、從物理地址中取出指令或數(shù)據(jù)。、從物理地址中取出指令或數(shù)據(jù)。快表快表地址變換過程地址變換過程 592022-2-4總結(jié)總結(jié)n固定分區(qū)的分配方式會產(chǎn)生內(nèi)零頭，因為是找出一個滿足作業(yè)要求的空閑分區(qū)分配給作業(yè)，大小不一定剛好合適，分區(qū)中有

37、一部分存儲空間會被浪費。n在可變式分區(qū)分配中，是按照作業(yè)的大小找出一個分區(qū)來分配如果大于作業(yè)申請的空間，則一分為二，剩下的一分部作為系統(tǒng)的空閑分區(qū)，有可能很小無法利用而成為外零頭。602022-2-4總結(jié)總結(jié)n為了解決外零頭的問題，提出了離散的分配方式，在分頁式存儲管理中，存儲空間被分面與頁大小相等的物理塊，作業(yè)的大小不可能都是物理塊的整數(shù)倍，因此在作業(yè)的最后一頁中有可能有部分空間未被利用，屬于內(nèi)零頭。n分段式存儲管理中，其內(nèi)存分配方式類似于動態(tài)分區(qū)的分配，因此會產(chǎn)生外零頭。n段頁式存儲管理中，其內(nèi)存分配方式類似于頁式的分配，因此會產(chǎn)生內(nèi)零頭。612022-2-4（二）（二） 虛擬內(nèi)存管理虛擬

38、內(nèi)存管理 n考試大綱要求考試大綱要求n1.虛擬內(nèi)存基本概念虛擬內(nèi)存基本概念2.請求分頁管理方式請求分頁管理方式3.頁面置換算法頁面置換算法最佳置換算法（最佳置換算法（OPT）；先進先出置換算法）；先進先出置換算法（FIFO）；最近最少使用置換算法（）；最近最少使用置換算法（LRU）；）；時鐘置換算法（時鐘置換算法（CLOCK）。）。4.頁面分配策略頁面分配策略5.抖動抖動抖動現(xiàn)象；工作集。抖動現(xiàn)象；工作集。622022-2-41 虛擬內(nèi)存基本概念虛擬內(nèi)存基本概念程序局部性原理程序局部性原理時間局部性時間局部性一條指令被執(zhí)行了，則在不久的將來它可能一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行，

39、再被執(zhí)行，如果某數(shù)據(jù)被訪問過， 則不久以后該數(shù)據(jù)可能再次被訪問。（循環(huán)操作）（循環(huán)操作）空間局部性空間局部性若某一存儲單元被使用，則在一定時間內(nèi)，若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用，與該存儲單元相鄰的單元可能被使用，即程序即程序在一段時間內(nèi)所訪問的地址，可能集中在一定在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)。的范圍之內(nèi)。（程序順序執(zhí)行）（程序順序執(zhí)行）632022-2-4虛擬存儲器的定義虛擬存儲器的定義 n虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)。具體地說，存便可運行作業(yè)的存儲器系統(tǒng)。具體地

40、說，所謂虛擬存儲器是指具有請求調(diào)入功能和所謂虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對主存容量進行擴置換功能，能從邏輯上對主存容量進行擴充的一種存儲器系統(tǒng)。實際上，用戶所看充的一種存儲器系統(tǒng)。實際上，用戶所看到的大容量只是一種感覺，是虛的，故而到的大容量只是一種感覺，是虛的，故而得名虛擬存儲器。得名虛擬存儲器。642022-2-42.請求分頁式存儲管理請求分頁式存儲管理 n它是建立在純分頁基礎(chǔ)上的，增加了請求調(diào)它是建立在純分頁基礎(chǔ)上的，增加了請求調(diào)頁功能、頁面置換功能所形成的請求分頁存頁功能、頁面置換功能所形成的請求分頁存儲管理系統(tǒng)。儲管理系統(tǒng)。n把作業(yè)分成大小相等的若干頁，把主存

41、分成把作業(yè)分成大小相等的若干頁，把主存分成與頁大小相等的若干塊；對每個作業(yè)限定分與頁大小相等的若干塊；對每個作業(yè)限定分給它的主存塊數(shù)，先把作業(yè)的部分頁裝入主給它的主存塊數(shù)，先把作業(yè)的部分頁裝入主存的這些塊中，在作業(yè)運行時再裝入所需要存的這些塊中，在作業(yè)運行時再裝入所需要的頁。的頁。652022-2-4采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) n（1）頁表）頁表u頁表用來記錄作業(yè)的分配情況頁表用來記錄作業(yè)的分配情況。n（2）缺頁中斷機構(gòu)）缺頁中斷機構(gòu)u在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在主存時，便要產(chǎn)生一次缺頁中斷，請求操作將主存時，便要產(chǎn)生一次缺頁中斷，請求操作

42、將所缺的頁調(diào)入主存。所缺的頁調(diào)入主存。（3）地址變換機構(gòu)）地址變換機構(gòu)662022-2-4頁表表項頁表表項頁號、內(nèi)存塊號、狀態(tài)位、訪問位、修改位、頁號、內(nèi)存塊號、狀態(tài)位、訪問位、修改位、外存地址外存地址n狀態(tài)位狀態(tài)位P：表示該頁是否已調(diào)入內(nèi)存，供：表示該頁是否已調(diào)入內(nèi)存，供程序訪問時參考程序訪問時參考n訪問位訪問位A：用于記錄本頁在一段時間內(nèi)被：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)或最近已有多長時間未被訪問，訪問的次數(shù)或最近已有多長時間未被訪問，供選擇換出頁面時參考供選擇換出頁面時參考頁號頁號 內(nèi)存塊號內(nèi)存塊號 狀態(tài)位狀態(tài)位P訪問位訪問位A修改位修改位M外存地址外存地址672022-2-4頁表

43、表項頁表表項頁號、內(nèi)存塊號、駐留位、外存地址、訪問頁號、內(nèi)存塊號、駐留位、外存地址、訪問位、修改位位、修改位n修改位：查看此頁是否在內(nèi)存中被修改過，修改位：查看此頁是否在內(nèi)存中被修改過，供置換頁面時參考。供置換頁面時參考。n外存地址：該頁存放在外存上的地址。供外存地址：該頁存放在外存上的地址。供調(diào)入該頁時參考。調(diào)入該頁時參考。頁號頁號 內(nèi)存塊號內(nèi)存塊號 狀態(tài)位狀態(tài)位P訪問位訪問位A修改位修改位M外存地址外存地址682022-2-4缺頁中斷（缺頁中斷（Page Fault）機構(gòu)機構(gòu)n缺頁中斷機構(gòu)缺頁中斷機構(gòu)u在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在主存時，在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在

44、主存時，便要產(chǎn)生一次缺頁中斷，請求操作將所缺的頁調(diào)入主存。便要產(chǎn)生一次缺頁中斷，請求操作將所缺的頁調(diào)入主存。缺頁中斷作為中斷，它同樣需要經(jīng)歷諸如缺頁中斷作為中斷，它同樣需要經(jīng)歷諸如保護保護CPU環(huán)境環(huán)境、分析中斷原因分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進行處理轉(zhuǎn)入缺頁中斷處理程序進行處理、恢復(fù)恢復(fù)CPU環(huán)境環(huán)境等幾個步驟。等幾個步驟。692022-2-4n缺頁中斷同一般中斷的區(qū)別？缺頁中斷同一般中斷的區(qū)別？缺頁中斷同一般中斷都是中斷，缺頁中斷同一般中斷都是中斷，相同點是：保護現(xiàn)場相同點是：保護現(xiàn)場中斷處理中斷處理恢復(fù)現(xiàn)場恢復(fù)現(xiàn)場不同點：不同點：n在指令執(zhí)行期間產(chǎn)生和處理中斷信號。一般中斷是在指令

45、執(zhí)行期間產(chǎn)生和處理中斷信號。一般中斷是一條指令完成后中斷，缺頁中斷是一條指令執(zhí)行時，一條指令完成后中斷，缺頁中斷是一條指令執(zhí)行時，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時所產(chǎn)生的中發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時所產(chǎn)生的中斷斷n一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。如指令可一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。如指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。能訪問多個內(nèi)存地址，這些地址在不同的頁中。702022-2-4下圖用數(shù)字標(biāo)出了缺頁中斷的處理過程：下圖用數(shù)字標(biāo)出了缺頁中斷的處理過程：根據(jù)當(dāng)前執(zhí)行指令中的虛擬地根據(jù)當(dāng)前執(zhí)行指令中的虛擬地址，形成數(shù)對：（頁號，頁內(nèi)址，形成數(shù)對：（頁號，頁內(nèi)位移）。

46、用頁號去查頁表，判位移）。用頁號去查頁表，判斷該頁是否在內(nèi)存儲器中斷該頁是否在內(nèi)存儲器中若該頁的若該頁的R位（缺頁中斷位）為位（缺頁中斷位）為“0”，表示當(dāng)前該頁不在內(nèi)存，于，表示當(dāng)前該頁不在內(nèi)存，于是產(chǎn)生缺頁中斷，讓操作系統(tǒng)的中是產(chǎn)生缺頁中斷，讓操作系統(tǒng)的中斷處理程序進行中斷處理。斷處理程序進行中斷處理。中斷處理程序去查存儲分塊表，尋中斷處理程序去查存儲分塊表，尋找一個空閑的內(nèi)存塊；查頁表，得找一個空閑的內(nèi)存塊；查頁表，得到該頁在輔助存儲器上的位置，并到該頁在輔助存儲器上的位置，并啟動磁盤讀信息。啟動磁盤讀信息。把從磁盤上讀出的信息裝入到分配把從磁盤上讀出的信息裝入到分配的內(nèi)存塊中。的內(nèi)存塊

47、中。n根據(jù)分配存儲塊的信息，修改頁表中相應(yīng)的表目內(nèi)容，即將表目根據(jù)分配存儲塊的信息，修改頁表中相應(yīng)的表目內(nèi)容，即將表目中的中的R位設(shè)置成為位設(shè)置成為“1”，表示該頁已在內(nèi)存中，在，表示該頁已在內(nèi)存中，在B位填入所分位填入所分配的塊號。另外，還要修改存儲分塊表里相應(yīng)表目的狀態(tài)。配的塊號。另外，還要修改存儲分塊表里相應(yīng)表目的狀態(tài)。n由于產(chǎn)生缺頁中斷的那條指令并沒有執(zhí)行，由于產(chǎn)生缺頁中斷的那條指令并沒有執(zhí)行，所以在完成所需頁面的裝入工作后，應(yīng)該返回所以在完成所需頁面的裝入工作后，應(yīng)該返回原指令重新執(zhí)行。這時再執(zhí)行時，由于所需頁原指令重新執(zhí)行。這時再執(zhí)行時，由于所需頁面已在內(nèi)存，因此可以順利執(zhí)行下去。

48、面已在內(nèi)存，因此可以順利執(zhí)行下去。712022-2-4頁面調(diào)入策略頁面調(diào)入策略 n（1）何時調(diào)入）何時調(diào)入n（2）何處調(diào)入）何處調(diào)入n（3）頁面調(diào)入過程頁面調(diào)入過程722022-2-4何時調(diào)入何時調(diào)入 n（1）預(yù)調(diào)入）預(yù)調(diào)入n采用一種以預(yù)測為基礎(chǔ)的調(diào)入策略，將預(yù)計不久要采用一種以預(yù)測為基礎(chǔ)的調(diào)入策略，將預(yù)計不久要使用的頁調(diào)入主存。使用的頁調(diào)入主存。n缺點：預(yù)計不準(zhǔn)缺點：預(yù)計不準(zhǔn)n場合：進程的首次調(diào)入場合：進程的首次調(diào)入n（2）請求調(diào)入）請求調(diào)入n當(dāng)發(fā)生缺頁時，提出請求，由系統(tǒng)調(diào)入當(dāng)發(fā)生缺頁時，提出請求，由系統(tǒng)調(diào)入n優(yōu)點：命中率優(yōu)點：命中率100%，實現(xiàn)簡單，實現(xiàn)簡單n缺點：開銷大，每次只調(diào)入一

49、頁缺點：開銷大，每次只調(diào)入一頁n場合：大多數(shù)場合：大多數(shù)732022-2-4何處調(diào)入何處調(diào)入n磁盤分對換區(qū)和文件區(qū)，有不同。磁盤分對換區(qū)和文件區(qū)，有不同。n（1）磁盤有足夠的對換區(qū)時，全部從對換區(qū)）磁盤有足夠的對換區(qū)時，全部從對換區(qū)調(diào)入頁面。運行前拷入對換區(qū)調(diào)入頁面。運行前拷入對換區(qū)n（2）磁盤無足夠的對換區(qū)時，修改過的部分）磁盤無足夠的對換區(qū)時，修改過的部分從對換區(qū)調(diào)入頁面，沒修改的部分從文件區(qū)從對換區(qū)調(diào)入頁面，沒修改的部分從文件區(qū)調(diào)入。調(diào)入。n（3）UNIX方式：運行過的頁面從對換區(qū)調(diào)方式：運行過的頁面從對換區(qū)調(diào)入，未運行的頁面從文件區(qū)調(diào)入入，未運行的頁面從文件區(qū)調(diào)入742022-2-4頁

50、面調(diào)入過程頁面調(diào)入過程n保護現(xiàn)場保護現(xiàn)場n轉(zhuǎn)中斷處理程序轉(zhuǎn)中斷處理程序n查頁表，找到頁的外存地址查頁表，找到頁的外存地址n內(nèi)存未滿則調(diào)入，修改頁表內(nèi)存未滿則調(diào)入，修改頁表n內(nèi)存已滿，則先置換。被置換的頁若被修改內(nèi)存已滿，則先置換。被置換的頁若被修改過，則寫入磁盤。過，則寫入磁盤。n將缺頁調(diào)入內(nèi)存，修改頁表和快表將缺頁調(diào)入內(nèi)存，修改頁表和快表n再訪內(nèi)存再訪內(nèi)存752022-2-43.頁面置換算法頁面置換算法n（1）最佳置換算法）最佳置換算法（OPT）n（2）先進先出置換算法（）先進先出置換算法（FIFO）n（3）最近最久未使用算法（最近最久未使用算法（LRU）n（4）Clock置換算法置換算法7

51、62022-2-4最佳置換算法最佳置換算法n理想淘汰算法理想淘汰算法最佳頁面算法（最佳頁面算法（OPT） 選擇以后永不使用的， 或許是在最長(未來)時間內(nèi)不再被訪問的頁面淘汰。采用最佳置換算法，通常可保證獲得最低的缺頁率。772022-2-4最佳置換算法最佳置換算法n假定系統(tǒng)為某進程分配了三個物理塊， 并考慮有以下的頁面號引用串：n7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1n 進程運行時， 先將7，0，1三個頁面裝入內(nèi)存。 以后， 當(dāng)進程要訪問頁面2時， 將會產(chǎn)生缺頁中斷。此時OS根據(jù)最佳置換算法， 將選擇頁面7予以淘汰。引用率707701701220103

52、20304243230321201201770101頁框(物理塊）203782022-2-4先進先出頁面置換算法先進先出頁面置換算法n先進先出（先進先出（FIFO）是人們最容易想到的頁面淘汰算法。是人們最容易想到的頁面淘汰算法。其做法是當(dāng)要進行頁面淘汰時，總是把最早進入內(nèi)存其做法是當(dāng)要進行頁面淘汰時，總是把最早進入內(nèi)存的頁面作為淘汰的對象。的頁面作為淘汰的對象。引用率70770170122010323104430230321013201770201頁框2304204230230127127011792022-2-4n最近最久未用（最近最久未用（LRU）置換算法的著眼點是在要進置換算法的著眼點是

53、在要進行頁面置換時，檢查這些頁面的被訪問時間，總是行頁面置換時，檢查這些頁面的被訪問時間，總是把最長時間未被訪問過的頁面置換出去。這是一種把最長時間未被訪問過的頁面置換出去。這是一種基于程序局部性原理的置換算法。也就是說，該算基于程序局部性原理的置換算法。也就是說，該算法認為如果一個頁面剛被訪問過，那么不久的將來法認為如果一個頁面剛被訪問過，那么不久的將來被訪問的可能性就大；否則被訪問的可能性就小。被訪問的可能性就大；否則被訪問的可能性就小。最近最久未使用（最近最久未使用（LRU）置換算法）置換算法802022-2-4引用率70770170122010320304403230321132201

54、710701頁框4024320321021. LRU(Least Recently Used)置換算法的描述置換算法的描述 4.7.2 最近最久未使用（最近最久未使用（LRU）置換算法）置換算法812022-2-44.7.3 Clock4.7.3 Clock置換算法置換算法 1. 簡單的簡單的Clock置換算法置換算法 圖 4-30 簡單Clock置換算法的流程和示例 入口查尋指針前進一步，指向下一個表目頁面訪問位 0?選擇該頁面淘汰是返回置頁面訪問位“ 0”否塊號頁號訪問位指針0124034215650711替換指針822022-2-4832022-2-42. 改進型改進型Clock置換算法

55、置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問， 又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問， 但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有可能再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改， 該頁可能再被訪問。 842022-2-4 其執(zhí)行過程可分成以下三步： (1) 從指針?biāo)甘镜漠?dāng)前位置開始， 掃描循環(huán)隊列， 尋找A=0且M=0的第一類頁面， 將所遇到的第一個頁面作為所選中的淘汰頁。 在第一次掃描期間不改變訪問位A。

56、(2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。 (3) 如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。 然后重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁。 852022-2-44、頁面分配策略、頁面分配策略 內(nèi)存分配策略：固定和可變內(nèi)存分配策略：固定和可變置換策略：全局和局部置換策略：全局和局部組合成組合成3種合適的策略：種合適的策略：n固定分配局部置換固定分配局部置換n可變分配全

57、局置換可變分配全局置換1.可變分配局部置換可變分配局部置換862022-2-45.工作集工作集由于程序的局部性原理，進程在一段由于程序的局部性原理，進程在一段時間內(nèi)集中訪問一些固定頁面的子集稱為時間內(nèi)集中訪問一些固定頁面的子集稱為該進程的工作集。該進程的工作集。為了減少進程訪問中的缺頁次數(shù)，為為了減少進程訪問中的缺頁次數(shù)，為每個進程分配一定數(shù)量的頁框作為工作集每個進程分配一定數(shù)量的頁框作為工作集使用。使用。872022-2-45.抖動抖動n采用某個淘汰算法淘汰一頁時，如果算法選擇采用某個淘汰算法淘汰一頁時，如果算法選擇不當(dāng)，就會出現(xiàn)這樣的現(xiàn)象：剛被淘汰的頁面不當(dāng)，就會出現(xiàn)這樣的現(xiàn)象：剛被淘汰的

58、頁面馬上又要用，因而要把它調(diào)入。調(diào)入不久再被馬上又要用，因而要把它調(diào)入。調(diào)入不久再被淘汰，淘汰不久再次裝入。如此反復(fù)，使整個淘汰，淘汰不久再次裝入。如此反復(fù)，使整個系統(tǒng)處于頻繁地調(diào)入調(diào)出狀態(tài)，大降低系統(tǒng)的系統(tǒng)處于頻繁地調(diào)入調(diào)出狀態(tài)，大降低系統(tǒng)的處理效率，這種現(xiàn)象叫抖動。處理效率，這種現(xiàn)象叫抖動。n如果分配給進程的物理塊號數(shù)與當(dāng)前工作集大如果分配給進程的物理塊號數(shù)與當(dāng)前工作集大小一致，可以有效避免抖動現(xiàn)象。在實際中，小一致，可以有效避免抖動現(xiàn)象。在實際中，可以通過調(diào)整淘汰算法，或者根據(jù)缺頁率的大可以通過調(diào)整淘汰算法，或者根據(jù)缺頁率的大小動態(tài)的分配給進程物理頁塊，都可以防止抖小動態(tài)的分配給進程物理

59、頁塊，都可以防止抖動的發(fā)生。動的發(fā)生。882022-2-4第第4章章 文件管理文件管理n（一） 文件系統(tǒng)基礎(chǔ)1. 文件概念2. 文件邏輯結(jié)構(gòu)順序文件；索引文件；索引順序文件。3. 目錄結(jié)構(gòu)文件控制塊和索引節(jié)點；單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)；樹形目錄結(jié)構(gòu)；圖形目錄結(jié)構(gòu)。4. 文件共享5. 文件保護訪問類型；訪問控制。892022-2-41 1 文件概念文件概念n文件文件是指具有文件名的若干相關(guān)元素的集合。是指具有文件名的若干相關(guān)元素的集合。元素元素通常是記錄。通常是記錄。記錄記錄是一組有意義的是一組有意義的數(shù)據(jù)數(shù)據(jù)項項集合。集合。n文件類型文件類型902022-2-4文件操作文件操作n用戶通過文件

60、系統(tǒng)所提供的系統(tǒng)調(diào)用實施對文件的操作。n1、最基本的文件操作有：創(chuàng)建、刪除、讀、寫、截斷文件和設(shè)置文件的讀、寫位置912022-2-4文件操作文件操作2、文件的“打開”和“關(guān)閉”操作所謂“打開”，是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開文件表的一個表目中，并將該表目的編號(或稱為索引)返回給用戶。以后，當(dāng)用戶再要求對該文件進行相應(yīng)的操作時，便可利用系統(tǒng)所返回的索引號向系統(tǒng)提出操作請求。系統(tǒng)這時便可直接利用該索引號到打開文件表中去查找，從而避免了對該文件的再次檢索。這樣不僅節(jié)省了大量的檢索開銷，也顯著地提高了對文件的操作速度。如果用戶已不再需要對該文件實施相應(yīng)