操作系統(tǒng)陸麗娜版課件5

1、第五章第五章 內(nèi)存管理內(nèi)存管理內(nèi)存管理基礎(chǔ)內(nèi)存管理基礎(chǔ) 內(nèi)存管理概念內(nèi)存管理概念 交換與覆蓋交換與覆蓋 連續(xù)分配管理方式連續(xù)分配管理方式 非連續(xù)分配管理方式非連續(xù)分配管理方式虛擬內(nèi)存管理虛擬內(nèi)存管理 虛擬內(nèi)存基本概念虛擬內(nèi)存基本概念 請(qǐng)求分頁管理方式請(qǐng)求分頁管理方式 頁面置換算法頁面置換算法 頁面分配策略頁面分配策略 抖動(dòng)抖動(dòng) 請(qǐng)求分段管理方式請(qǐng)求分段管理方式 存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，雖然內(nèi)存容量在不斷擴(kuò)大，但內(nèi)存仍是寶貴雖然內(nèi)存容量在不斷擴(kuò)大，但內(nèi)存仍是寶貴資源，如何提高主存儲(chǔ)器利用率，并擴(kuò)充大資源，如何提高主存儲(chǔ)器利用率，并擴(kuò)充大主存，對(duì)主存，對(duì)

2、主存信息實(shí)現(xiàn)有效保護(hù)主存信息實(shí)現(xiàn)有效保護(hù)是存儲(chǔ)器管是存儲(chǔ)器管理主要任務(wù)，也是各種不同理主要任務(wù)，也是各種不同存儲(chǔ)管理方法存儲(chǔ)管理方法的的目標(biāo)。目標(biāo)。外存(secondary storage)DOS核心命令處理程序內(nèi)存(primary storage)快速緩存(cache)寄存器(register)存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)管理的基本概念存儲(chǔ)管理的基本概念存儲(chǔ)管理目的和存儲(chǔ)管理目的和功能功能n主存儲(chǔ)器的分配、回收和地址映射主存儲(chǔ)器的分配、回收和地址映射 內(nèi)存分配的主要任務(wù)是為每一道程序分配內(nèi)存分配的主要任務(wù)是為每一道程序分配內(nèi)存空間，使它們內(nèi)存空間，使它們“各得其所各得其所”，每一道程

3、序，每一道程序完完成后回收內(nèi)存空間。分配時(shí)完成地址變換，地成后回收內(nèi)存空間。分配時(shí)完成地址變換，地址映射是把程序地址空間的相對(duì)地址轉(zhuǎn)換成內(nèi)址映射是把程序地址空間的相對(duì)地址轉(zhuǎn)換成內(nèi)存中的絕對(duì)地址。存中的絕對(duì)地址。存儲(chǔ)保護(hù)存儲(chǔ)保護(hù) 內(nèi)存保護(hù)的任務(wù)是確保每道程序都在內(nèi)存保護(hù)的任務(wù)是確保每道程序都在自己的內(nèi)存空間運(yùn)行，互不干擾。保護(hù)系自己的內(nèi)存空間運(yùn)行，互不干擾。保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯（有意或無意的），統(tǒng)程序區(qū)不被用戶侵犯（有意或無意的），不允許用戶程序讀寫不屬于自己地址空間不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程序的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）。的

4、地址空間）。 存儲(chǔ)管理目的和功能存儲(chǔ)管理目的和功能（續(xù)）（續(xù)）存儲(chǔ)管理目的和功能（續(xù)）存儲(chǔ)管理目的和功能（續(xù)）n提高主存儲(chǔ)器的利用率提高主存儲(chǔ)器的利用率n 減少不可用的存儲(chǔ)空間，允許多道程序減少不可用的存儲(chǔ)空間，允許多道程序動(dòng)態(tài)共享主存。動(dòng)態(tài)共享主存。n內(nèi)存擴(kuò)充內(nèi)存擴(kuò)充 n內(nèi)存擴(kuò)充的任務(wù)是從邏輯上來擴(kuò)充內(nèi)存容內(nèi)存擴(kuò)充的任務(wù)是從邏輯上來擴(kuò)充內(nèi)存容量，使用戶認(rèn)為系統(tǒng)所擁有的內(nèi)存空間遠(yuǎn)量，使用戶認(rèn)為系統(tǒng)所擁有的內(nèi)存空間遠(yuǎn)比其實(shí)際的內(nèi)存空間大的多比其實(shí)際的內(nèi)存空間大的多。對(duì)用戶程序的處理步驟對(duì)用戶程序的處理步驟 庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存 程序的裝入和鏈接程

5、序的裝入和鏈接地址重定位地址重定位n名字空間、地址空間和存儲(chǔ)空間名字空間、地址空間和存儲(chǔ)空間n在源程序中，是通過符號(hào)名來訪問子程序和數(shù)在源程序中，是通過符號(hào)名來訪問子程序和數(shù)據(jù)的，我們把程序中符號(hào)名的集合稱為據(jù)的，我們把程序中符號(hào)名的集合稱為“名字名字空間空間”。匯編語言源程序經(jīng)過匯編，或者高級(jí)。匯編語言源程序經(jīng)過匯編，或者高級(jí)語言源程序經(jīng)過編譯，得到的目標(biāo)程序是以語言源程序經(jīng)過編譯，得到的目標(biāo)程序是以“0”0”作為參考地址的模塊。然后多個(gè)目標(biāo)模塊由連作為參考地址的模塊。然后多個(gè)目標(biāo)模塊由連接程序連接成一個(gè)具有統(tǒng)一地址的裝配模塊，接程序連接成一個(gè)具有統(tǒng)一地址的裝配模塊，以便最后裝入內(nèi)存中執(zhí)行。

6、以便最后裝入內(nèi)存中執(zhí)行。n裝配模塊雖然具有統(tǒng)一的地址空間，但是仍裝配模塊雖然具有統(tǒng)一的地址空間，但是仍是以是以“0”0”作為參考地址，即是浮動(dòng)的。要作為參考地址，即是浮動(dòng)的。要把它裝入內(nèi)存執(zhí)行，就要確定裝入內(nèi)存的實(shí)把它裝入內(nèi)存執(zhí)行，就要確定裝入內(nèi)存的實(shí)際物理地址，并修改程序中與地址有關(guān)的代際物理地址，并修改程序中與地址有關(guān)的代碼，這一過程稱為地址重定位。碼，這一過程稱為地址重定位。n我們把目標(biāo)模塊中的地址稱為相對(duì)地址（或稱我們把目標(biāo)模塊中的地址稱為相對(duì)地址（或稱為為“邏輯地址邏輯地址”），而把相對(duì)地址的集合稱為），而把相對(duì)地址的集合稱為“相對(duì)地址空間相對(duì)地址空間/邏輯地址空間邏輯地址空間”或簡

7、稱為或簡稱為“地址地址空間空間”。n地址空間的程序和數(shù)據(jù)經(jīng)過地址重定位處理后，就變成地址空間的程序和數(shù)據(jù)經(jīng)過地址重定位處理后，就變成了可由了可由CPUCPU直接執(zhí)行的絕對(duì)地址程序。我們把這一地址直接執(zhí)行的絕對(duì)地址程序。我們把這一地址集合稱為集合稱為“絕對(duì)地址空間絕對(duì)地址空間”或或“存儲(chǔ)空間存儲(chǔ)空間”。程序的名。程序的名字空間、地址空間和存儲(chǔ)空間之間的關(guān)系如圖所示：字空間、地址空間和存儲(chǔ)空間之間的關(guān)系如圖所示： 源源 程程 序序相對(duì)目標(biāo)程相對(duì)目標(biāo)程序（裝配模序（裝配模塊）塊）絕對(duì)目標(biāo)程絕對(duì)目標(biāo)程序序名字空間名字空間 地址空間地址空間 相對(duì)地址相對(duì)地址/邏輯地邏輯地址空間址空間存儲(chǔ)空間存儲(chǔ)空間絕對(duì)

8、地址絕對(duì)地址/物理地物理地址空間址空間匯編匯編/編譯編譯鏈接鏈接地址重定位地址重定位裝裝 入入地址重定位（續(xù)地址重定位（續(xù)) )邏輯地址、物理地址和地址映射邏輯地址、物理地址和地址映射地址映射地址映射BA=1000BA=1000Load A 200 3456 。 。 。12001200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560 0100100200200編譯連接編譯連接邏輯地址空間邏輯地址空間n絕對(duì)裝入方式絕對(duì)裝入方式n可重定位裝入方式可重定位裝入方式n動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式n程序的裝入程序的裝入1. 1. 絕

9、對(duì)裝入方式絕對(duì)裝入方式(Absolute Loading Mode)(Absolute Loading Mode) n如果內(nèi)存位置已知，可生成絕對(duì)代碼；如果開如果內(nèi)存位置已知，可生成絕對(duì)代碼；如果開始位置改變，需要重新編譯代碼。始位置改變，需要重新編譯代碼。n程序中所使用的絕對(duì)地址，既可在編譯或匯編程序中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出，時(shí)給出， 也可由程序員直接賦予。也可由程序員直接賦予。n只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置，只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置，適用于單道程序環(huán)境。適用于單道程序環(huán)境。例如：讀卡器，傳感器結(jié)點(diǎn)屬于絕對(duì)裝入方式例如：讀卡器，傳感器結(jié)點(diǎn)屬于絕對(duì)

10、裝入方式n地址變換通常是在裝入時(shí)一次完成的，以后不再地址變換通常是在裝入時(shí)一次完成的，以后不再改變，故又稱為靜態(tài)重定位。改變，故又稱為靜態(tài)重定位。n程序重定位以后就不能在內(nèi)存中移動(dòng)；程序重定位以后就不能在內(nèi)存中移動(dòng)；n要求程序的存儲(chǔ)空間是連續(xù)的，不能把程序存儲(chǔ)要求程序的存儲(chǔ)空間是連續(xù)的，不能把程序存儲(chǔ)到若干個(gè)不連續(xù)的區(qū)域中。到若干個(gè)不連續(xù)的區(qū)域中。2. 2. 可重定位裝入方式可重定位裝入方式(Relocation Loading Mode)(Relocation Loading Mode) 作業(yè)裝入內(nèi)存時(shí)的情況作業(yè)裝入內(nèi)存時(shí)的情況 LOAD 1,2500365LOAD 1,2500365100

11、001100012500150005000250010000作業(yè)地址空間內(nèi)存空間LOAD 1,125003. 3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式(Denamle Run-time Loading)(Denamle Run-time Loading) n在把裝入模塊裝入內(nèi)存后，并不立即把裝入在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此，行。因此， 裝入內(nèi)存后的所有地址都仍是相裝入內(nèi)存后的所有地址都仍是相對(duì)地址。對(duì)地址。 n進(jìn)程在執(zhí)行時(shí)可

12、以在內(nèi)存中移動(dòng)。進(jìn)程在執(zhí)行時(shí)可以在內(nèi)存中移動(dòng)。n需要硬件對(duì)地址映射的支持。需要硬件對(duì)地址映射的支持。n動(dòng)態(tài)重定位動(dòng)態(tài)重定位LOAD 1，25003650：1001002500250026002600程序的地址空間LOAD 1，2500365100001000010100 12500 12500物理地址物理地址內(nèi)存的地址空間重定位寄存器重定位寄存器中央處理器中央處理器CPUCPU指令寄存器指令寄存器LOAD 1,2500LOAD 1,25002500(2500(邏輯地址邏輯地址) )MMU(存儲(chǔ)管理部件)CPU芯片+ +10000n靜態(tài)鏈接靜態(tài)鏈接(Static Linking) (Static

13、 Linking) n程序運(yùn)行之前，將各目標(biāo)模塊及所需庫函數(shù)，程序運(yùn)行之前，將各目標(biāo)模塊及所需庫函數(shù)，鏈接成完整的裝配模塊以后不再拆開，鏈接成完整的裝配模塊以后不再拆開，靜態(tài)靜態(tài)鏈接是在生成可執(zhí)行文件時(shí)進(jìn)行的。鏈接是在生成可執(zhí)行文件時(shí)進(jìn)行的。n動(dòng)態(tài)鏈接動(dòng)態(tài)鏈接(Dynamic Linking) (Dynamic Linking) n裝入內(nèi)存時(shí)，邊裝入邊鏈接裝入內(nèi)存時(shí)，邊裝入邊鏈接n在在裝入或運(yùn)行裝入或運(yùn)行時(shí)進(jìn)行鏈接。時(shí)進(jìn)行鏈接。n程序的鏈接程序的鏈接 1. 1. 靜態(tài)鏈接方式靜態(tài)鏈接方式模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模塊 CReturn；0

14、N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊 在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題：須解決以下兩個(gè)問題： (1) (1) 對(duì)相對(duì)地址進(jìn)行修改。對(duì)相對(duì)地址進(jìn)行修改。 (2) (2) 變換外部調(diào)用符號(hào)：將外部調(diào)用符號(hào)轉(zhuǎn)變換外部調(diào)用符號(hào)：將外部調(diào)用符號(hào)轉(zhuǎn)換為對(duì)定位后的邏輯地址的調(diào)用。換為對(duì)定位后的邏輯地址的調(diào)用。 2. 2. 動(dòng)態(tài)鏈接方式動(dòng)態(tài)鏈接方式n近幾年流行起來的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式，這種鏈接方近幾年流行起來的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式

15、，這種鏈接方式是將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行鏈接，式是將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行鏈接，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由入內(nèi)存時(shí)，立即由OSOS去找到該模塊并將之裝入內(nèi)存，去找到該模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。量的內(nèi)存空間。n

16、通常被鏈接的共享代碼稱為動(dòng)態(tài)鏈接庫通常被鏈接的共享代碼稱為動(dòng)態(tài)鏈接庫(DLL, (DLL, Dynamic-Link Library)Dynamic-Link Library)或共享庫或共享庫(shared library)(shared library)。內(nèi)存管理的存儲(chǔ)保護(hù)功能內(nèi)存管理的存儲(chǔ)保護(hù)功能n上下界保護(hù)和地址檢查機(jī)構(gòu)上下界保護(hù)和地址檢查機(jī)構(gòu)( (靜態(tài)地址定位靜態(tài)地址定位) ) 內(nèi)存管理的功能（續(xù)內(nèi)存管理的功能（續(xù)2 2）n基址、限長寄存器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)（基址、限長寄存器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)（動(dòng)態(tài)動(dòng)態(tài)地址定位地址定位） 這兩中寄存器分別存放運(yùn)行程序在內(nèi)存的起始地址和其總長度。 2.2

17、.交換與覆蓋交換與覆蓋n為什么引入？為什么引入？ 在多道環(huán)境下擴(kuò)充內(nèi)存的方法，解決在較小的存儲(chǔ)空在多道環(huán)境下擴(kuò)充內(nèi)存的方法，解決在較小的存儲(chǔ)空間中運(yùn)行較大程序時(shí)遇到的矛盾間中運(yùn)行較大程序時(shí)遇到的矛盾n覆蓋技術(shù)主要用在早期的操作系統(tǒng)中覆蓋技術(shù)主要用在早期的操作系統(tǒng)中n交換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中，交換技術(shù)的交換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)n交換技術(shù)與覆蓋技術(shù)共同點(diǎn)：交換技術(shù)與覆蓋技術(shù)共同點(diǎn)： 進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進(jìn)行信息交換放在內(nèi)存，內(nèi)外

18、存之間進(jìn)行信息交換2.2.交換與覆蓋（續(xù)交換與覆蓋（續(xù)1 1）n覆蓋技術(shù)覆蓋技術(shù)n指一個(gè)作業(yè)的某些程序段，或幾個(gè)作業(yè)的某些部分指一個(gè)作業(yè)的某些程序段，或幾個(gè)作業(yè)的某些部分輪流使用某一段存儲(chǔ)空間。輪流使用某一段存儲(chǔ)空間。n基本思想是把內(nèi)存中同一區(qū)域，靜態(tài)地分配給一道基本思想是把內(nèi)存中同一區(qū)域，靜態(tài)地分配給一道程序的若干個(gè)子程序或數(shù)據(jù)段，在開始時(shí)只讓一部程序的若干個(gè)子程序或數(shù)據(jù)段，在開始時(shí)只讓一部分程序裝入內(nèi)存，根據(jù)運(yùn)行的情況，交替輪流使用。分程序裝入內(nèi)存，根據(jù)運(yùn)行的情況，交替輪流使用。n和單用戶連續(xù)區(qū)分配、分區(qū)分配技術(shù)配合使用。和單用戶連續(xù)區(qū)分配、分區(qū)分配技術(shù)配合使用。n用戶需要小心設(shè)計(jì)程序的數(shù)

19、據(jù)結(jié)構(gòu)，使其覆蓋模塊用戶需要小心設(shè)計(jì)程序的數(shù)據(jù)結(jié)構(gòu)，使其覆蓋模塊具有相對(duì)獨(dú)立性。具有相對(duì)獨(dú)立性。內(nèi)存管理基礎(chǔ)內(nèi)存管理基礎(chǔ)例例 2.2.交換與覆蓋（續(xù)交換與覆蓋（續(xù)2 2）缺點(diǎn)：缺點(diǎn)： 對(duì)用戶不透明，增加了用戶負(fù)擔(dān)對(duì)用戶不透明，增加了用戶負(fù)擔(dān) 例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上，序的內(nèi)存管理上，MS-DOSMS-DOS的啟動(dòng)過程中，多次的啟動(dòng)過程中，多次使用覆蓋技術(shù)；啟動(dòng)之后，用戶程序區(qū)使用覆蓋技術(shù)；啟動(dòng)之后，用戶程序區(qū)TPATPA的的高端部分與高端部分與COMMAND.COMCOMMAND.COM暫駐模塊也是一種覆暫駐模塊也是一種覆蓋

20、結(jié)構(gòu)蓋結(jié)構(gòu) 2.2.交換與覆蓋（續(xù)交換與覆蓋（續(xù)3 3）n交換技術(shù)交換技術(shù)n當(dāng)內(nèi)存空間緊張時(shí)當(dāng)內(nèi)存空間緊張時(shí)，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)移，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)移到外存，把外存中某些進(jìn)程換進(jìn)內(nèi)存，占據(jù)前者所到外存，把外存中某些進(jìn)程換進(jìn)內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進(jìn)程在內(nèi)存與外存之間的占用的區(qū)域，這種技術(shù)是進(jìn)程在內(nèi)存與外存之間的動(dòng)態(tài)調(diào)度動(dòng)態(tài)調(diào)度n多用于分時(shí)系統(tǒng)中多用于分時(shí)系統(tǒng)中n使用外存做緩存，通過不斷換出換入而運(yùn)行大作業(yè)使用外存做緩存，通過不斷換出換入而運(yùn)行大作業(yè)n分分進(jìn)程交換進(jìn)程交換和和部分交換部分交換（頁面交換和分段交換）（頁面交換和分段交換）n提高內(nèi)存利用率，增加并發(fā)進(jìn)程數(shù)，

21、提高系統(tǒng)效率提高內(nèi)存利用率，增加并發(fā)進(jìn)程數(shù)，提高系統(tǒng)效率n交換使用的技術(shù)較多：交換使用的技術(shù)較多：換出進(jìn)程的選擇、交換時(shí)機(jī)換出進(jìn)程的選擇、交換時(shí)機(jī)的確定、需要一個(gè)盤交換區(qū)及管理、換入回內(nèi)存時(shí)的確定、需要一個(gè)盤交換區(qū)及管理、換入回內(nèi)存時(shí)位置的確定等位置的確定等3.3.連續(xù)分配管理方式連續(xù)分配管理方式（1 1）單一連續(xù)存儲(chǔ)管理）單一連續(xù)存儲(chǔ)管理n基本原理基本原理 n將內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)；將內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)；n內(nèi)存中僅駐留一道程序，整個(gè)系統(tǒng)資源和用戶區(qū)只內(nèi)存中僅駐留一道程序，整個(gè)系統(tǒng)資源和用戶區(qū)只為一個(gè)用戶所獨(dú)占；為一個(gè)用戶所獨(dú)占；n僅適用于單用戶、單任務(wù)操作系統(tǒng)。僅適用于單用戶、單任

22、務(wù)操作系統(tǒng)。 內(nèi)存管理基礎(chǔ)內(nèi)存管理基礎(chǔ)（1 1）單一連續(xù)存儲(chǔ)管理（續(xù)）單一連續(xù)存儲(chǔ)管理（續(xù)1 1）n主存空間的分配與回收主存空間的分配與回收n主存空間的分配主存空間的分配 ：系統(tǒng)區(qū)和用戶區(qū)系統(tǒng)區(qū)和用戶區(qū) n主存空間的回收主存空間的回收 ：運(yùn)行結(jié)束，釋放主存空間：運(yùn)行結(jié)束，釋放主存空間 作業(yè)作業(yè) 1 1裝入程序裝入程序操作系統(tǒng)區(qū)操作系統(tǒng)區(qū)作業(yè)作業(yè)1 1的的程序和數(shù)據(jù)程序和數(shù)據(jù)界限地址界限地址界限地址界限地址+ +邏輯地址邏輯地址內(nèi)存管理基礎(chǔ)內(nèi)存管理基礎(chǔ)（1 1）單一連續(xù)存儲(chǔ)管理（續(xù)）單一連續(xù)存儲(chǔ)管理（續(xù)2 2）n優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)n簡單、易實(shí)現(xiàn)簡單、易實(shí)現(xiàn)n僅適合單道程序，處理機(jī)和內(nèi)存不能充分利用僅適

23、合單道程序，處理機(jī)和內(nèi)存不能充分利用n基本原理基本原理 n預(yù)先把可分配的內(nèi)存空間分割成若干個(gè)連續(xù)區(qū)域，預(yù)先把可分配的內(nèi)存空間分割成若干個(gè)連續(xù)區(qū)域，每一區(qū)域稱為分區(qū)每一區(qū)域稱為分區(qū)n每個(gè)分區(qū)的大小可以相同也可以不同，分區(qū)大小固每個(gè)分區(qū)的大小可以相同也可以不同，分區(qū)大小固定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)n存儲(chǔ)分配：如果有一個(gè)空閑區(qū)，則分配給進(jìn)程存儲(chǔ)分配：如果有一個(gè)空閑區(qū)，則分配給進(jìn)程（2 2）固定分區(qū)存儲(chǔ)管理）固定分區(qū)存儲(chǔ)管理內(nèi)存管理基礎(chǔ)內(nèi)存管理基礎(chǔ)固定分區(qū)存儲(chǔ)管理是最早使用的一種運(yùn)行多道程固定分區(qū)存儲(chǔ)管理是最早使用的一種運(yùn)行多道程序的存儲(chǔ)管理方式。序的

24、存儲(chǔ)管理方式。（2 2）固定分區(qū)存儲(chǔ)管理（續(xù)）固定分區(qū)存儲(chǔ)管理（續(xù)1 1）n主存空間的分配與回收主存空間的分配與回收 n數(shù)據(jù)結(jié)構(gòu)與主存分區(qū)分配表數(shù)據(jù)結(jié)構(gòu)與主存分區(qū)分配表 內(nèi)存管理基礎(chǔ)內(nèi)存管理基礎(chǔ)( (a a) )分區(qū)說明表分區(qū)說明表( (b b) )存儲(chǔ)空間分配表存儲(chǔ)空間分配表分區(qū)號(hào)分區(qū)號(hào)大小大?。↘ K ）起址地址（起址地址（K K）狀態(tài)狀態(tài)1 18 81616JobJob1 12 2161624240 03 316164040JobJob2 24 432325656JobJob3 3操作系統(tǒng)操作系統(tǒng)JobJob1 10 0JobJob2 2JobJob3 30 01616K K2424K

25、K4040K K5656K K（2 2）固定分區(qū)存儲(chǔ)管理（續(xù)）固定分區(qū)存儲(chǔ)管理（續(xù)2 2）固定式分區(qū)表固定式分區(qū)表 ( (a a) )分區(qū)號(hào)分區(qū)號(hào)1 12 23 34 45 5大小大小8 8 KBKB3232 KBKB3232 KBKB120120 KBKB520520 KBKB起始地址起始地址312312 KBKB320320 KBKB352352 KBKB384384 KBKB504504 KBKB狀態(tài)狀態(tài)在使用在使用在使用在使用在使用在使用未用未用未用未用( (b b) )操作系統(tǒng)操作系統(tǒng)504 KB504 KB384 KB384 KB352 KB352 KB320 KB320 KB31

26、2 KB312 KB0 0520 KB520 KB120 KB120 KB32 KB32 KB32 KB32 KB8 KB8 KB312 KB312 KB狀態(tài)欄的值為狀態(tài)欄的值為0，表示未分配，作業(yè)裝入后改成作，表示未分配，作業(yè)裝入后改成作業(yè)名。業(yè)名。固定式分區(qū)舉例固定式分區(qū)舉例 分區(qū)號(hào)分區(qū)號(hào) 分區(qū)容量分區(qū)容量 作業(yè)容量作業(yè)容量 剩余容量剩余容量 1 12 23 34 45 58KB8KB32KB32KB32KB32KB120KB120KB520KB520KB1KB1KB9KB9KB9KB9KB33KB33KB121KB121KB7KB7KB23KB23KB23KB23KB87KB87KB39

27、9KB399KB合合 計(jì)計(jì) 712 KB 712 KB 173 KB 173 KB 539 KB 539 KB 操作系統(tǒng)操作系統(tǒng)504 KB504 KB384 KB384 KB352 KB352 KB320 KB320 KB312 KB312 KB0 0520 KB520 KB120 KB120 KB32 KB32 KB32 KB32 KB8 KB8 KB312 KB312 KBJ1J1J2J2J3J3J4J4J5J5內(nèi)存利用內(nèi)存利用率不高率不高（2 2）固定分區(qū)存儲(chǔ)管理（續(xù)）固定分區(qū)存儲(chǔ)管理（續(xù)3 3）管理特點(diǎn)管理特點(diǎn) n一個(gè)作業(yè)只能裝入一個(gè)分區(qū)。當(dāng)一個(gè)分區(qū)的大小不一個(gè)作業(yè)只能裝入一個(gè)分區(qū)。

28、當(dāng)一個(gè)分區(qū)的大小不能滿足一個(gè)作業(yè)的要求時(shí)，該作業(yè)暫時(shí)不能裝入。能滿足一個(gè)作業(yè)的要求時(shí)，該作業(yè)暫時(shí)不能裝入。n通過對(duì)通過對(duì)“分區(qū)分配表分區(qū)分配表”的改寫，來實(shí)現(xiàn)主存的分配的改寫，來實(shí)現(xiàn)主存的分配與回收。簡單、易行，適合多道程序設(shè)計(jì)。與回收。簡單、易行，適合多道程序設(shè)計(jì)。n當(dāng)分區(qū)較大而作業(yè)較小時(shí)，容易形成碎片，造成主當(dāng)分區(qū)較大而作業(yè)較小時(shí)，容易形成碎片，造成主存空間的浪費(fèi)。存空間的浪費(fèi)。n這種方式分區(qū)總數(shù)固定，也限制了并發(fā)執(zhí)行的作業(yè)這種方式分區(qū)總數(shù)固定，也限制了并發(fā)執(zhí)行的作業(yè)數(shù)目。數(shù)目。 定義：在存儲(chǔ)分配過程中，分配給用戶而未被利用的定義：在存儲(chǔ)分配過程中，分配給用戶而未被利用的 那部分內(nèi)存，稱為

29、內(nèi)存的那部分內(nèi)存，稱為內(nèi)存的“內(nèi)零頭內(nèi)零頭”或或“內(nèi)碎內(nèi)碎片片”作業(yè)進(jìn)入時(shí)有兩種作業(yè)排隊(duì)策略作業(yè)進(jìn)入時(shí)有兩種作業(yè)排隊(duì)策略（3 3）可變分區(qū)存儲(chǔ)管理）可變分區(qū)存儲(chǔ)管理n基本思想基本思想n內(nèi)存不是預(yù)先劃分好分區(qū)的，而是根據(jù)裝入作業(yè)的內(nèi)存不是預(yù)先劃分好分區(qū)的，而是根據(jù)裝入作業(yè)的實(shí)際需要?jiǎng)討B(tài)地劃分存儲(chǔ)空間。分區(qū)的個(gè)數(shù)和大小實(shí)際需要?jiǎng)討B(tài)地劃分存儲(chǔ)空間。分區(qū)的個(gè)數(shù)和大小是不固定的是不固定的n作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配況來決定是否分配n若有足夠的空間，則按需要分割一部分分區(qū)給該若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；進(jìn)程；

30、n否則令其等待內(nèi)存空間否則令其等待內(nèi)存空間（3 3）可變分區(qū)存儲(chǔ)管理（續(xù)）可變分區(qū)存儲(chǔ)管理（續(xù)1 1）n主存空間的分配主存空間的分配n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)n分區(qū)分配表分區(qū)分配表 n空閑分區(qū)表空閑分區(qū)表n分區(qū)分配與回收操作分區(qū)分配與回收操作n動(dòng)態(tài)分配動(dòng)態(tài)分配n三種分配算法：三種分配算法：首次適應(yīng)算法、最佳適應(yīng)算法、首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法最壞適應(yīng)算法（3 3）可變分區(qū)存儲(chǔ)管理（續(xù)）可變分區(qū)存儲(chǔ)管理（續(xù)2 2）可變分區(qū)的分配和回收示例可變分區(qū)的分配和回收示例J1J1J2J2J3J3J4J4J1J1J2J2J3J3J4J4J5J5J6J6分配策略分配策略/算法算法n 首次首次/ /最先適

31、應(yīng)最先適應(yīng)First fitFirst fit：n空白區(qū)按地址大小遞增順序排列。查找分空白區(qū)按地址大小遞增順序排列。查找分區(qū)說明表，找到第一個(gè)滿足申請(qǐng)長度的空區(qū)說明表，找到第一個(gè)滿足申請(qǐng)長度的空閑區(qū)，分配并分割。剩余部分保留在空白閑區(qū)，分配并分割。剩余部分保留在空白區(qū)表中原來的位置。區(qū)表中原來的位置。n最先適應(yīng)算法：盡可能利用存儲(chǔ)器的低地最先適應(yīng)算法：盡可能利用存儲(chǔ)器的低地址部分，因此在低地址部分會(huì)很快地產(chǎn)生址部分，因此在低地址部分會(huì)很快地產(chǎn)生大量碎片。大量碎片。n 最佳適應(yīng)（最優(yōu)）最佳適應(yīng)（最優(yōu)） Best fit Best fit ：n空白區(qū)表中的空白區(qū)按其空白區(qū)表中的空白區(qū)按其容量以遞增

32、容量以遞增的次序的次序排列。當(dāng)要求分配一個(gè)空白區(qū)時(shí)，由小到大排列。當(dāng)要求分配一個(gè)空白區(qū)時(shí)，由小到大順序查找分區(qū)說明表，找到第一個(gè)滿足申請(qǐng)順序查找分區(qū)說明表，找到第一個(gè)滿足申請(qǐng)長度的最小空閑區(qū)，分配并分割。如果有剩長度的最小空閑區(qū)，分配并分割。如果有剩余部分，作為一個(gè)空白區(qū)將其插入適當(dāng)?shù)奈挥嗖糠?，作為一個(gè)空白區(qū)將其插入適當(dāng)?shù)奈恢?；置；n最佳適應(yīng)算法：選擇容量接近的空閑區(qū)來分最佳適應(yīng)算法：選擇容量接近的空閑區(qū)來分配，產(chǎn)生大量碎片。配，產(chǎn)生大量碎片。n 最差適應(yīng)（最壞）最差適應(yīng)（最壞） Worst fit Worst fit ：n空白區(qū)表中的空白區(qū)按其空白區(qū)表中的空白區(qū)按其容量以遞減容量以遞減的次的

33、次序排列。查找分區(qū)說明表，找到第一個(gè)滿序排列。查找分區(qū)說明表，找到第一個(gè)滿足申請(qǐng)長度的空閑區(qū)，分配并分割。剩余足申請(qǐng)長度的空閑區(qū)，分配并分割。剩余部分插入適當(dāng)位置。部分插入適當(dāng)位置。n最差適應(yīng)算法：分割大空閑區(qū)后，還可以最差適應(yīng)算法：分割大空閑區(qū)后，還可以產(chǎn)生較大的空閑區(qū)，空閑區(qū)均勻地減小，產(chǎn)生較大的空閑區(qū)，空閑區(qū)均勻地減小，以避免碎片。以避免碎片。n 唯一最佳適應(yīng)算法（唯一最佳適應(yīng)算法（single best fitsingle best fit）n分區(qū)按大小順序分級(jí)（分區(qū)按大小順序分級(jí)（8KB8KB、16KB16KB、32 32 KBKB、 ）n作業(yè)按請(qǐng)求容量也分成相應(yīng)的存儲(chǔ)級(jí)，僅當(dāng)作業(yè)按

34、請(qǐng)求容量也分成相應(yīng)的存儲(chǔ)級(jí)，僅當(dāng)PDTPDT中相應(yīng)級(jí)的分區(qū)為空閑時(shí)，才進(jìn)行內(nèi)存分中相應(yīng)級(jí)的分區(qū)為空閑時(shí)，才進(jìn)行內(nèi)存分配，即使有更大的分區(qū)空閑也不予以分配。配，即使有更大的分區(qū)空閑也不予以分配。（3 3）可變分區(qū)存儲(chǔ)管理（續(xù)）可變分區(qū)存儲(chǔ)管理（續(xù)3 3）n內(nèi)存回收內(nèi)存回收 當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空 閑塊表閑塊表 考慮：上鄰、下鄰、上下相鄰、上下不相鄰考慮：上鄰、下鄰、上下相鄰、上下不相鄰n “ “碎片碎片”問題問題 經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多小的空經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多小的空閑塊。它們每一個(gè)都很小，不足以滿足

35、分配要求；但閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為其總和滿足分配要求。這些空閑塊被稱為外碎片外碎片 造成存儲(chǔ)資源的浪費(fèi)造成存儲(chǔ)資源的浪費(fèi)申請(qǐng)分配一個(gè)申請(qǐng)分配一個(gè)XKBXKB大小的分區(qū)大小的分區(qū)置空白區(qū)號(hào)置空白區(qū)號(hào)f f =1=1f f 大于最后大于最后一個(gè)空白區(qū)號(hào)？一個(gè)空白區(qū)號(hào)？空白區(qū)可用？空白區(qū)可用？保存空白區(qū)的起始地址保存空白區(qū)的起始地址空白區(qū)空白區(qū) f f的大小的大小x xKBKB空白區(qū)的空白區(qū)的狀態(tài)狀態(tài)= =空項(xiàng)空項(xiàng)修改空白區(qū)的大小修改空白區(qū)的大小和起始地址和起始地址在已分配表中找一個(gè)狀在已分配表中找一個(gè)狀態(tài)態(tài)= =空項(xiàng)的分區(qū)號(hào)空項(xiàng)的分區(qū)號(hào)

36、P P置分區(qū)置分區(qū)P P的大小為的大小為 x xKBKB置分區(qū)起始地址置分區(qū)起始地址置分區(qū)狀態(tài)為已分配置分區(qū)狀態(tài)為已分配返回一個(gè)返回一個(gè)分區(qū)號(hào)分區(qū)號(hào)此次無法分配此次無法分配f f +1 +1 f fY YY YN NN N = =可變式分區(qū)中請(qǐng)求一個(gè)分區(qū)的流程可變式分區(qū)中請(qǐng)求一個(gè)分區(qū)的流程可變式分區(qū)中釋放一個(gè)分區(qū)的流程可變式分區(qū)中釋放一個(gè)分區(qū)的流程 請(qǐng)求釋放請(qǐng)求釋放一個(gè)分區(qū)一個(gè)分區(qū) P P保存分區(qū)保存分區(qū)P P的的大小和起始地址大小和起始地址置分區(qū)的置分區(qū)的狀態(tài)為空項(xiàng)狀態(tài)為空項(xiàng)分區(qū)分區(qū)P P有鄰有鄰接的空白區(qū)接的空白區(qū)? ?修改新空白區(qū)的大小修改新空白區(qū)的大小起始地址和狀態(tài)起始地址和狀態(tài)返回返

37、回修改空白修改空白區(qū)的狀態(tài)區(qū)的狀態(tài)修改新空白區(qū)的修改新空白區(qū)的大小和起始地址大小和起始地址在未分配表在未分配表中找一空表目中找一空表目置新空白區(qū)大小置新空白區(qū)大小和起始地址和起始地址置空白區(qū)狀置空白區(qū)狀態(tài)為可用態(tài)為可用在兩個(gè)空在兩個(gè)空白區(qū)之間白區(qū)之間有一個(gè)有一個(gè)空白區(qū)空白區(qū)N N（4 4）可再定位式分區(qū)分配）可再定位式分區(qū)分配n“碎片碎片”問題解決問題解決 內(nèi)存中存在許多不能充分利用的小空閑區(qū)，降低了多道內(nèi)存中存在許多不能充分利用的小空閑區(qū)，降低了多道程序設(shè)計(jì)的程度，還造成內(nèi)存空間的嚴(yán)重浪費(fèi)。程序設(shè)計(jì)的程度，還造成內(nèi)存空間的嚴(yán)重浪費(fèi)。 緊湊技術(shù)緊湊技術(shù)： 通過在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域

38、合并為大通過在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域的空閑區(qū)域 （又稱：緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)）（又稱：緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)） 問題問題：系統(tǒng)開銷系統(tǒng)開銷 大大 移動(dòng)時(shí)機(jī)移動(dòng)時(shí)機(jī) ？可再定位式分區(qū)分配的靠攏過程 作業(yè)7(256 KB)(a)(b)(c)作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1 (8 KB)OS作業(yè)7 (256 KB)作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1(8 KB)OS01024 KB504 KB352 KB320 KB312 KB888 KB652 KB37

39、6 KB作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1 (8 KB)OS 只要改變浮動(dòng)寄存器的內(nèi)容利用浮動(dòng)寄存器進(jìn)行地址變換 L 1，352 K + 980001557100352 KB352 KB + 50352 KB + 9800376 KB352 KB + 9800-32 KB+L 1，352 KB + 980001557100320KB320 KB + 50320 KB + 9800344 KB計(jì)算地址地址變換有效地址浮動(dòng)寄存器再定位寄存器或稱為浮動(dòng)寄存器實(shí)現(xiàn)地址變換：320k-352K=-32K當(dāng)執(zhí)行每條指令時(shí)，由CPU計(jì)算出有效地址，在訪問操作數(shù)之前，

40、將浮動(dòng)寄存器的內(nèi)容與計(jì)算出的有效地址相加，得到實(shí)際的物理地址。即在移到新的位置后作業(yè)的指令和數(shù)據(jù)都沒有改變，在執(zhí)行時(shí)利用浮動(dòng)寄存器自動(dòng)完成地址變換的。例如：指令L 1,352KB+9800的執(zhí)行，仍將位于320KB+9800處的數(shù)據(jù)01557100取至1號(hào)寄存器。可再定位式分區(qū)分配算法流程可再定位式分區(qū)分配算法流程 請(qǐng)求分配請(qǐng)求分配一個(gè)大小為一個(gè)大小為x xKBKB 的分區(qū)的分區(qū)有大于有大于x xKBKB 的空白區(qū)的空白區(qū)嗎？嗎？空白區(qū)的總空白區(qū)的總和和x xKBKB執(zhí)行靠攏操作執(zhí)行靠攏操作并修改狀態(tài)表并修改狀態(tài)表分配一個(gè)分區(qū)并修分配一個(gè)分區(qū)并修改狀態(tài)表改狀態(tài)表返回一個(gè)返回一個(gè)分區(qū)號(hào)分區(qū)號(hào)此時(shí)

41、無此時(shí)無法分配法分配Y YY YN NN N（5 5）分區(qū)的保護(hù)措施）分區(qū)的保護(hù)措施 作業(yè)作業(yè) 2 2的分區(qū)的分區(qū)60 KB60 KB124 KB124 KB256 KB256 KB0 060 KB60 KB基址寄存器基址寄存器64 KB64 KB限長寄存器限長寄存器作業(yè)作業(yè) 2 2的分區(qū)的分區(qū)60 KB60 KB124 KB124 KB256 KB256 KB0 060 KB60 KB下界寄存器下界寄存器124 KB124 KB上界寄存器上界寄存器使用界地址保戶和存儲(chǔ)鍵保護(hù)使用界地址保戶和存儲(chǔ)鍵保護(hù)n總結(jié)總結(jié)n分區(qū)存儲(chǔ)管理要求把作業(yè)的地址空間裝入到連續(xù)的存分區(qū)存儲(chǔ)管理要求把作業(yè)的地址空間裝入

42、到連續(xù)的存儲(chǔ)空間內(nèi)儲(chǔ)空間內(nèi)n在動(dòng)態(tài)分區(qū)的存儲(chǔ)管理中，常常由于存在一些不足以在動(dòng)態(tài)分區(qū)的存儲(chǔ)管理中，常常由于存在一些不足以裝入任何作業(yè)的小的分區(qū)而浪費(fèi)掉部分存儲(chǔ)空間裝入任何作業(yè)的小的分區(qū)而浪費(fèi)掉部分存儲(chǔ)空間- -碎片碎片n采用采用“內(nèi)存緊湊內(nèi)存緊湊”技術(shù)可以解決碎片問題，但要移動(dòng)技術(shù)可以解決碎片問題，但要移動(dòng)大量指令和數(shù)據(jù)，花費(fèi)處理機(jī)時(shí)間，代價(jià)比較高。大量指令和數(shù)據(jù)，花費(fèi)處理機(jī)時(shí)間，代價(jià)比較高。如何改進(jìn)？如何改進(jìn)？非連續(xù)分配管理非連續(xù)分配管理 4.4.非連續(xù)分配管理方式非連續(xù)分配管理方式（1 1）簡單分頁存儲(chǔ)管理）簡單分頁存儲(chǔ)管理n基本思想基本思想n等分內(nèi)存等分內(nèi)存 把內(nèi)存存儲(chǔ)空間劃分成大小相等

43、的單位，稱為存儲(chǔ)把內(nèi)存存儲(chǔ)空間劃分成大小相等的單位，稱為存儲(chǔ)塊，或頁框（塊，或頁框（Page FramePage Frame）n用戶邏輯地址空間分頁用戶邏輯地址空間分頁 把用戶邏輯地址空間劃分成大小相等的單位，稱為把用戶邏輯地址空間劃分成大小相等的單位，稱為 頁面或頁（頁面或頁（PagePage）。給各頁從）。給各頁從0 0開始編制頁號(hào)，開始編制頁號(hào)，頁頁 內(nèi)地址是相對(duì)于內(nèi)地址是相對(duì)于0 0編址編址 （1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)1 1）n邏輯地址的表示邏輯地址的表示n用戶的邏輯地址從基址用戶的邏輯地址從基址0 0開始編址，即是相對(duì)地址。開始編址，即是相對(duì)地址。n每個(gè)相對(duì)

44、地址用一個(gè)數(shù)對(duì)（每個(gè)相對(duì)地址用一個(gè)數(shù)對(duì)（p,wp,w）表示，）表示，p p是頁號(hào)，是頁號(hào)，w w是頁內(nèi)地址，是該頁內(nèi)的偏移量是頁內(nèi)地址，是該頁內(nèi)的偏移量2 21010=1K=1K2 21111=2K=2K2 21212=4K=4Kn邏輯地址與頁號(hào)及頁內(nèi)偏移地址之間的邏輯地址與頁號(hào)及頁內(nèi)偏移地址之間的PageNoPageNo = INT = INTAddrAddr/ /PageLengthPageLength PageOffset PageOffset = = AddrAddr MOD MOD PageLengthPageLength舉例：對(duì)于舉例：對(duì)于1KB1KB頁面，若給定邏輯地址頁面，若給

45、定邏輯地址2170B2170B，則，則 PageNoPageNo = 2= 2，PageOffset PageOffset = 122= 122n頁的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。頁的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。一頁的大小為一頁的大小為2 2的整數(shù)次冪的整數(shù)次冪，地址的高位部分為，地址的高位部分為頁號(hào)，低位部分為頁內(nèi)地址頁號(hào)，低位部分為頁內(nèi)地址n頁面大小選擇頁面大小選擇n由機(jī)器的地址結(jié)構(gòu)所決定由機(jī)器的地址結(jié)構(gòu)所決定n頁面大頁面大/ /小評(píng)析小評(píng)析n2 210-10-2 21212KBKB之間之間例例 設(shè)一個(gè)邏輯地址空間有設(shè)一個(gè)邏輯地址空間有8 8頁，每頁頁，每頁10241

46、024字節(jié)，字節(jié)，映射到映射到3232塊的物理內(nèi)存上。試問：塊的物理內(nèi)存上。試問：（1 1）邏輯地址空間需要多少位來表示？）邏輯地址空間需要多少位來表示？（2 2）物理地址空間需要多少位來表示？）物理地址空間需要多少位來表示？（1 1）邏輯地址空間需要）邏輯地址空間需要1313位來表示。其中頁號(hào)需要位來表示。其中頁號(hào)需要3 3位，因?yàn)槲?，因?yàn)? 23 3=8=8；頁內(nèi)地址需要；頁內(nèi)地址需要1010位，因?yàn)槲?，因?yàn)? 21010=1024=1024。（2 2）物理地址空間需要）物理地址空間需要1515位來表示。其中塊號(hào)需要位來表示。其中塊號(hào)需要5 5位，因?yàn)槲唬驗(yàn)? 25 5=32=32；塊內(nèi)

47、地址需要；塊內(nèi)地址需要1010位，因?yàn)槲?，因?yàn)? 21010=1024=1024。（1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)2 2）n主存空間的分配與回收主存空間的分配與回收 n內(nèi)存分配原則內(nèi)存分配原則n作業(yè)的邏輯地址是連續(xù)的，用戶在編制程序時(shí)仍作業(yè)的邏輯地址是連續(xù)的，用戶在編制程序時(shí)仍只須使用順序的地址，而不必考慮如何去分頁。只須使用順序的地址，而不必考慮如何去分頁。n由地址轉(zhuǎn)換機(jī)構(gòu)和操作系統(tǒng)管理來決定頁面和主由地址轉(zhuǎn)換機(jī)構(gòu)和操作系統(tǒng)管理來決定頁面和主存分塊的大小。存分塊的大小。n用戶進(jìn)程在主存空間中的每個(gè)頁框內(nèi)的地址是連用戶進(jìn)程在主存空間中的每個(gè)頁框內(nèi)的地址是連續(xù)的，但頁框和頁框

48、之間的地址可以不連續(xù)。續(xù)的，但頁框和頁框之間的地址可以不連續(xù)。 存儲(chǔ)地址由連續(xù)到離散的變化，存儲(chǔ)地址由連續(xù)到離散的變化，即分配時(shí)，即分配時(shí)，邏輯上相鄰的頁，物理上不一定相鄰的快邏輯上相鄰的頁，物理上不一定相鄰的快 （1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)3 3）n采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu) n頁表頁表：系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁表，頁表給出邏輯：系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁表，頁表給出邏輯頁號(hào)和具體內(nèi)存塊號(hào)相應(yīng)的關(guān)系。頁號(hào)和具體內(nèi)存塊號(hào)相應(yīng)的關(guān)系。頁表放在內(nèi)存，屬頁表放在內(nèi)存，屬于進(jìn)程的現(xiàn)場信息于進(jìn)程的現(xiàn)場信息n作業(yè)表作業(yè)表：也叫主存分配表，包括作業(yè)名，作業(yè)對(duì)應(yīng)頁：也叫主存分配表，包括

49、作業(yè)名，作業(yè)對(duì)應(yīng)頁表的起始地址和頁表的長度。內(nèi)存中的每個(gè)作業(yè)在作表的起始地址和頁表的長度。內(nèi)存中的每個(gè)作業(yè)在作業(yè)表中有一個(gè)登記項(xiàng)。整個(gè)系統(tǒng)只有一張作業(yè)表。業(yè)表中有一個(gè)登記項(xiàng)。整個(gè)系統(tǒng)只有一張作業(yè)表。n位示圖位示圖：空閑塊管理。頁式存儲(chǔ)管理以塊為單位分配：空閑塊管理。頁式存儲(chǔ)管理以塊為單位分配主存空間，由于塊的大小是固定的，所以只要在主存主存空間，由于塊的大小是固定的，所以只要在主存分配表中指出哪些塊已分配和哪些塊未分配以及當(dāng)前分配表中指出哪些塊已分配和哪些塊未分配以及當(dāng)前剩余的空閑塊數(shù)。最簡單的辦法是用一張剩余的空閑塊數(shù)。最簡單的辦法是用一張“位示圖位示圖”構(gòu)成主存分配表。構(gòu)成主存分配表。 0

50、 0頁頁1 1頁頁2 2頁頁3 3頁頁4 4頁頁5 5頁頁n n頁頁用戶程序用戶程序0 012121 113132 216163 318184 419195 51717n n頁表頁表頁號(hào)頁號(hào)塊號(hào)塊號(hào)第第1212塊塊第第1313塊塊第第1414塊塊第第1515塊塊第第1616塊塊第第1717塊塊第第1818塊塊第第1919塊塊內(nèi)存內(nèi)存（1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)3 3）作業(yè)作業(yè)2 2( (0 0頁頁) )操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)2 2( (1 1頁頁) )作業(yè)作業(yè)3 3( (0 0頁頁) )作業(yè)作業(yè)1 1( (0 0頁頁) )作業(yè)作業(yè)1 1( (1 1頁頁) )作業(yè)作業(yè)2

51、 2( (2 2頁頁) )0 05 51 16 60 01 12 22 24 47 70 08 8作業(yè)作業(yè)1 1作業(yè)作業(yè)2 2作業(yè)作業(yè)3 31 KB1 KB2 KB2 KB0 00 01 KB1 KB2 KB2 KB0 03 KB3 KB1 KB1 KB0 0邏輯地址空間邏輯地址空間頁面變換表頁面變換表物理地址空間物理地址空間頁號(hào)頁號(hào) 塊號(hào)塊號(hào)1 KB1 KB2 KB2 KB3 KB3 KB4 KB4 KB5 KB5 KB6 KB6 KB7 KB7 KB8 KB8 KB9 KB9 KB10 KB10 KB（1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)4 4）（1 1）簡單分頁存儲(chǔ)管理（續(xù)

52、）簡單分頁存儲(chǔ)管理（續(xù)5 5）空閑塊管理空閑塊管理位示圖位示圖塊號(hào)字長塊號(hào)字長字號(hào)位號(hào)字長字號(hào)位號(hào)字長i ij j （i i和和j j的編號(hào)都是從的編號(hào)都是從0 0開始）開始） （1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)6 6）n內(nèi)存的分配與回收內(nèi)存的分配與回收n計(jì)算一個(gè)進(jìn)程所需要的總塊數(shù)計(jì)算一個(gè)進(jìn)程所需要的總塊數(shù)N Nn查位示圖：是否還有查位示圖：是否還有N N個(gè)空閑塊個(gè)空閑塊n如果有足夠的空閑塊，則頁表長度設(shè)為如果有足夠的空閑塊，則頁表長度設(shè)為N N，可填，可填入入PCBPCB中；申請(qǐng)頁表區(qū)，把頁表始址填入中；申請(qǐng)頁表區(qū)，把頁表始址填入PCB PCB n依次分配依次分配N N個(gè)空

53、閑塊，將塊號(hào)和頁號(hào)填入頁表個(gè)空閑塊，將塊號(hào)和頁號(hào)填入頁表n修改位示圖修改位示圖請(qǐng)求分配請(qǐng)求分配x xKBKB的地址空間的地址空間計(jì)算所需塊數(shù)計(jì)算所需塊數(shù)N NN N=x xKB/4KBKB/4KB有有N N個(gè)可個(gè)可用的塊？用的塊？在作業(yè)表中找空表目置頁在作業(yè)表中找空表目置頁表長度表長度= =N N，狀態(tài)，狀態(tài)= =已分配已分配分配該作業(yè)的分配該作業(yè)的PMTPMT 表，并在表，并在作業(yè)表中登記該作業(yè)表中登記該P(yáng)MTPMT 的始址的始址檢查內(nèi)存分塊表，分配檢查內(nèi)存分塊表，分配N N個(gè)可個(gè)可用存儲(chǔ)塊，在每塊的狀態(tài)欄用存儲(chǔ)塊，在每塊的狀態(tài)欄內(nèi)填入作業(yè)序號(hào)，再將存儲(chǔ)內(nèi)填入作業(yè)序號(hào)，再將存儲(chǔ)塊號(hào)填入塊號(hào)填

54、入 PMTPMT 表表返回返回本次無法分配本次無法分配N NY Y分頁存儲(chǔ)分配算法流程分頁存儲(chǔ)分配算法流程 （1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)7 7）n地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 由硬件實(shí)現(xiàn)，操作系統(tǒng)配合。由硬件實(shí)現(xiàn)，操作系統(tǒng)配合。 關(guān)鍵在于頁號(hào)到物理塊號(hào)的轉(zhuǎn)變關(guān)鍵在于頁號(hào)到物理塊號(hào)的轉(zhuǎn)變n系統(tǒng)設(shè)置一對(duì)寄存器系統(tǒng)設(shè)置一對(duì)寄存器n頁表始址寄存器頁表始址寄存器 用于保存正在運(yùn)行進(jìn)程的頁表的始址用于保存正在運(yùn)行進(jìn)程的頁表的始址n頁表長度寄存器頁表長度寄存器 用于保存正在運(yùn)行進(jìn)程的頁表的長度用于保存正在運(yùn)行進(jìn)程的頁表的長度n地址變換過程地址變換過程 見下圖見下圖地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)

55、位移量位移量進(jìn)程進(jìn)程地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)內(nèi)存內(nèi)存有效地址有效地址頁表寄存器頁表寄存器塊號(hào)塊號(hào)頁框頁框頁頁號(hào)號(hào)塊號(hào)塊號(hào)頁號(hào)頁號(hào)塊號(hào)塊號(hào)位移量位移量+ +頁表始址頁表始址 頁表長度頁表長度頁表頁表物理地址物理地址塊號(hào)塊號(hào)位移量位移量PCBPCB頁表始址頁表始址頁表長度頁表長度 越界中斷越界中斷1 12 23 34 45 5紅線部分的工紅線部分的工作在進(jìn)程被調(diào)作在進(jìn)程被調(diào)度時(shí)由調(diào)度程度時(shí)由調(diào)度程序完成序完成絕對(duì)地址計(jì)算：絕對(duì)地址計(jì)算：塊號(hào)塊號(hào)塊長頁內(nèi)地址塊長頁內(nèi)地址 頁表始址頁表始址頁表長度頁表長度頁表寄存器頁表寄存器頁號(hào)頁號(hào)(3)(3)邏輯地址寄存器邏輯地址寄存器BlockNoBlockNo頁

56、表頁表BlockNoBlockNo物理地址寄存器物理地址寄存器+ +越界中斷越界中斷頁號(hào)頁號(hào)物理塊號(hào)物理塊號(hào)0 01 12 23 3地址變換例地址變換例1 1n頁式存儲(chǔ)系統(tǒng)的邏輯地址是由頁號(hào)和頁內(nèi)地址兩部分頁式存儲(chǔ)系統(tǒng)的邏輯地址是由頁號(hào)和頁內(nèi)地址兩部分組成，地址變換過程如圖所示。假定頁面的大小為組成，地址變換過程如圖所示。假定頁面的大小為8K8K，計(jì)算圖中所示的十進(jìn)制邏輯地址計(jì)算圖中所示的十進(jìn)制邏輯地址96129612經(jīng)過地址變換后，經(jīng)過地址變換后，形成的物理地址形成的物理地址a a應(yīng)為多少？應(yīng)為多少？ 地址變換例地址變換例2 2 某分頁系統(tǒng)的邏輯地址為某分頁系統(tǒng)的邏輯地址為1616位，其中高

57、位，其中高6 6位為頁號(hào)，低位為頁號(hào)，低1010位為頁內(nèi)地址。請(qǐng)問：位為頁內(nèi)地址。請(qǐng)問： （1 1）這樣的地址結(jié)構(gòu)一頁有多少字節(jié)？邏輯地址）這樣的地址結(jié)構(gòu)一頁有多少字節(jié)？邏輯地址可有多少頁？一個(gè)作業(yè)最大的使用空間是多少？可有多少頁？一個(gè)作業(yè)最大的使用空間是多少？ （2 2）邏輯地址）邏輯地址23182318、40964096、850850對(duì)應(yīng)的頁號(hào)、頁對(duì)應(yīng)的頁號(hào)、頁 內(nèi)地址分別是多少？內(nèi)地址分別是多少？ （1 1）簡單分頁存儲(chǔ)管理（續(xù)）簡單分頁存儲(chǔ)管理（續(xù)8 8）n相聯(lián)存儲(chǔ)器相聯(lián)存儲(chǔ)器快表快表 用途用途：為了提高地址映射速度：為了提高地址映射速度( (兩次讀內(nèi)存兩次讀內(nèi)存) ) 保存正在運(yùn)行進(jìn)

58、程的頁表的子集（部分頁保存正在運(yùn)行進(jìn)程的頁表的子集（部分頁 表項(xiàng)）表項(xiàng)） 特點(diǎn)特點(diǎn)：按內(nèi)容并行查找：按內(nèi)容并行查找 快表表項(xiàng)快表表項(xiàng)： 頁號(hào)；內(nèi)存塊號(hào)；頁號(hào)；內(nèi)存塊號(hào)；n具有塊表地址變換過程具有塊表地址變換過程 見下圖見下圖 n頁表空間問題頁表空間問題n現(xiàn)代計(jì)算機(jī)系統(tǒng)支持非常大的邏輯地址空間現(xiàn)代計(jì)算機(jī)系統(tǒng)支持非常大的邏輯地址空間(2(23232226464) )，頁表變得龐大。例如，對(duì)于具有頁表變得龐大。例如，對(duì)于具有3232位邏輯地址空間的分位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為頁系統(tǒng)，規(guī)定頁面大小為4KB4KB即即2 21212B B，則每個(gè)進(jìn)程頁表，則每個(gè)進(jìn)程頁表的頁表項(xiàng)可達(dá)的頁表項(xiàng)可

59、達(dá)1M1M個(gè)；若同時(shí)設(shè)定頁表項(xiàng)大小為個(gè)；若同時(shí)設(shè)定頁表項(xiàng)大小為4B4B，則每，則每個(gè)進(jìn)程僅頁表便需占用個(gè)進(jìn)程僅頁表便需占用4MB 4MB 內(nèi)存空間，且要求是連續(xù)的。內(nèi)存空間，且要求是連續(xù)的。n解決方案解決方案 多級(jí)頁表多級(jí)頁表( (頁表分頁及對(duì)換頁表分頁及對(duì)換) )或反置頁表或反置頁表 一個(gè)簡單的解決方法是使用兩層分頁方法，就是將頁表再一個(gè)簡單的解決方法是使用兩層分頁方法，就是將頁表再分頁，如下圖所示。分頁，如下圖所示。分頁存儲(chǔ)管理方案的評(píng)價(jià)分頁存儲(chǔ)管理方案的評(píng)價(jià) n采用動(dòng)態(tài)地址變換會(huì)增加計(jì)算機(jī)硬件成本和采用動(dòng)態(tài)地址變換會(huì)增加計(jì)算機(jī)硬件成本和 降低處理機(jī)的速度。降低處理機(jī)的速度。n各種表格要占

60、用一定容量的主存空間，各種表格要占用一定容量的主存空間， 而且而且還要花費(fèi)一部分處理機(jī)時(shí)間用來建立和管理這還要花費(fèi)一部分處理機(jī)時(shí)間用來建立和管理這些表格。些表格。n雖然說碎片消除了，但每個(gè)作業(yè)的最后一頁一雖然說碎片消除了，但每個(gè)作業(yè)的最后一頁一般都有不能充分利用的空白區(qū)般都有不能充分利用的空白區(qū)( (內(nèi)碎片內(nèi)碎片) )。n存儲(chǔ)擴(kuò)充問題仍未得到解決。存儲(chǔ)擴(kuò)充問題仍未得到解決。（2 2）段式存儲(chǔ)管理）段式存儲(chǔ)管理 段式存儲(chǔ)管理方式的引入主要是為了滿足程序段式存儲(chǔ)管理方式的引入主要是為了滿足程序員在編程和使用上的要求。員在編程和使用上的要求。n基本思想基本思想n 用戶程序劃分用戶程序劃分 按程序自身