第四章 存儲管理

1、廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.14.1 存儲器工作原理存儲器工作原理 4.2 4.2 連續(xù)存儲空間管理連續(xù)存儲空間管理 4.3 4.3 分頁式存儲管理分頁式存儲管理 4.4 4.4 分段式存儲管理分段式存儲管理 4.5 4.5 虛擬存儲管理虛擬存儲管理 第四章第四章 存儲管理存儲管理廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy如何對存儲器加以有效的管理，不僅直接影如何對存儲器加以有效的管理，不僅直接影響到存儲器的利用率，而且還對系統(tǒng)性能有重大響到存儲器的利用率，而且還對系統(tǒng)性能有重大影響。存儲器管理的主要對象是內(nèi)存。影響。存儲器管理的主要對象是內(nèi)存。存儲管理存儲管

2、理的功能的功能: :分配和去配、抽象和映射、隔離與共享分配和去配、抽象和映射、隔離與共享、存儲擴(kuò)充。、存儲擴(kuò)充。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.1.1 存儲器的層次存儲器的層次寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動存儲介質(zhì)4.1 存儲器存儲器訪問速度往上越高訪問速度往上越高容量越往下越大容量越往下越大廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyl如何將一個用戶源程序變成一個可在內(nèi)存中執(zhí)行如何將一個用戶源程序變成一個可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過的程序，通常要經(jīng)過3 3步驟：步驟： : :由編譯程序（由編譯程序（CompilerCompiler）將用戶源代碼編

3、譯）將用戶源代碼編譯成若個目標(biāo)模塊成若個目標(biāo)模塊 （Object ModuleObject Module）。）。: :由鏈接程序（由鏈接程序（LinkerLinker）將編譯后形成的一組）將編譯后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊，形成一個完整的裝入模塊 。: :由裝入程序（由裝入程序（LoaderLoader）將裝入模塊裝入內(nèi)存）將裝入模塊裝入內(nèi)存。 - -程序的裝入和鏈接程序的裝入和鏈接4.1.2 4.1.2 地址轉(zhuǎn)換與存儲保護(hù)地址轉(zhuǎn)換與存儲保護(hù)廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy編輯編輯編譯

4、編譯鏈接鏈接裝入裝入運(yùn)行運(yùn)行廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy1.1.程序編譯程序編譯n源程序經(jīng)過編譯程序或匯編程序的處理來獲得源程序經(jīng)過編譯程序或匯編程序的處理來獲得多個目標(biāo)模塊多個目標(biāo)模塊n處理時編譯程序負(fù)責(zé)記錄模塊內(nèi)引用的發(fā)生位處理時編譯程序負(fù)責(zé)記錄模塊內(nèi)引用的發(fā)生位置置 n目標(biāo)模塊附有供引用使用的內(nèi)部符號表和外部目標(biāo)模塊附有供引用使用的內(nèi)部符號表和外部符號表符號表n符號表給出了各個符號名及在本目標(biāo)模塊中的符號表給出了各個符號名及在本目標(biāo)模塊中的名字地址名字地址，在模塊被鏈接時進(jìn)行轉(zhuǎn)換，在模塊被鏈接時進(jìn)行轉(zhuǎn)換廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy2. 2. 程

5、序鏈接程序鏈接l1)1)靜態(tài)鏈接靜態(tài)鏈接: :在程序裝入之前，先將各目標(biāo)模塊及它們所在程序裝入之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝配模塊，以后不再拆需的庫函數(shù)，鏈接成一個完整的裝配模塊，以后不再拆開。開。l2)2)裝入時動態(tài)鏈接裝入時動態(tài)鏈接: :這是指將用戶源程序編譯后所得到的這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈一組目標(biāo)模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈接方式接方式。la.a.便于修改和更新便于修改和更新lb.b.便于實(shí)現(xiàn)對目標(biāo)模塊的共享便于實(shí)現(xiàn)對目標(biāo)模塊的共享l3)3)運(yùn)行時動態(tài)鏈接運(yùn)行時動態(tài)鏈接: :這是指對某些目標(biāo)

6、模塊的鏈接，是在這是指對某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該程序執(zhí)行中需要該( (目標(biāo)目標(biāo)) )模塊時，才對它進(jìn)行的鏈接。模塊時，才對它進(jìn)行的鏈接。 廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy模塊模塊A Aif x1if x1CALL B;CALL B;elseelseCALL C;CALL C;RETURNRETURN模塊模塊B BCALL C;CALL C;RETURNRETURN模塊模塊C CRETURNRETURN0 0L-1L-10 0M-1M-10 0N-1N-1(a)(a)目標(biāo)模塊目標(biāo)模塊模塊模塊A Aif x1if x1JSR L;JSR L;elseelseJSR

7、 L+M;JSR L+M;RETURNRETURN模塊模塊B BJSR L+M;JSR L+M;RETURNRETURN模塊模塊C CRETURNRETURN0 0L-1L-1L LL+M-1L+M-1L+ML+ML+M+N-1L+M+N-1(b)(b)裝入模塊裝入模塊廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyl三種裝入方式：絕對裝載方式、可重定位裝載方式三種裝入方式：絕對裝載方式、可重定位裝載方式 、動、動態(tài)運(yùn)行時轉(zhuǎn)載方式。態(tài)運(yùn)行時轉(zhuǎn)載方式。1 1、絕對裝載：、絕對裝載：l編譯后，裝入前已產(chǎn)生了絕對地址（內(nèi)存地址），裝載時不編譯后，裝入前已產(chǎn)生了絕對地址（內(nèi)存地址），裝載時不再作地址

8、重定位。再作地址重定位。l絕對地址的產(chǎn)生：（絕對地址的產(chǎn)生：（1 1）由編譯器完成，（）由編譯器完成，（2 2）由程序員編程）由程序員編程完成。完成。l對（對（1 1）而言，編程用符號地址。）而言，編程用符號地址。 l程序每次必須裝入同一內(nèi)存區(qū)；程序員必須事先了解內(nèi)存的程序每次必須裝入同一內(nèi)存區(qū)；程序員必須事先了解內(nèi)存的使用情況，根據(jù)內(nèi)存情況確定程序的邏輯地址；程序的修改使用情況，根據(jù)內(nèi)存情況確定程序的邏輯地址；程序的修改將引起整個程序中指令地址的變動；程序所有的存儲引用（將引起整個程序中指令地址的變動；程序所有的存儲引用（函數(shù)調(diào)用），在裝入之前都必須轉(zhuǎn)換為物理地址，這不利于函數(shù)調(diào)用），在裝入

9、之前都必須轉(zhuǎn)換為物理地址，這不利于存儲共享。存儲共享。3. 3. 程序轉(zhuǎn)載程序轉(zhuǎn)載廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy2、可重定位裝載方式、可重定位裝載方式 (靜態(tài)地址重定位靜態(tài)地址重定位) l目標(biāo)模塊的起始地址通常是從目標(biāo)模塊的起始地址通常是從0開始的，程序開始的，程序中的其它地址也都是相對于起始地址計算的。中的其它地址也都是相對于起始地址計算的。 l由裝載程序?qū)⒀b載模塊裝入內(nèi)存后，裝載模塊由裝載程序?qū)⒀b載模塊裝入內(nèi)存后，裝載模塊中程序所訪問的所有邏輯地址與實(shí)際裝載內(nèi)存中程序所訪問的所有邏輯地址與實(shí)際裝載內(nèi)存的物理地址不同的物理地址不同 ，必須進(jìn)行地址映射，將邏，必須進(jìn)行地址映

10、射，將邏輯地址轉(zhuǎn)換為物理地址。輯地址轉(zhuǎn)換為物理地址。l靜態(tài)重定位技術(shù)靜態(tài)重定位技術(shù)：地址映射在程序裝載時進(jìn)行：地址映射在程序裝載時進(jìn)行，以后不再更改程序地址。，以后不再更改程序地址。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy0100025005000LOAD 1,2500LOAD 1,1250036536510000110001250015000目標(biāo)模塊目標(biāo)模塊裝入內(nèi)存裝入內(nèi)存LOAD j365符號地址符號地址相對地址相對地址絕對地址絕對地址裝入模塊裝入模塊j廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyl3.3. 動態(tài)重定位動態(tài)重定位l在程序運(yùn)行時動態(tài)進(jìn)行程序的地址轉(zhuǎn)換。在程序運(yùn)

11、行時動態(tài)進(jìn)行程序的地址轉(zhuǎn)換。l硬件的支持，即重定位寄存器，用于保存程序硬件的支持，即重定位寄存器，用于保存程序的在內(nèi)存中的起始地址。的在內(nèi)存中的起始地址。l能保證進(jìn)程的可移動性，有效的提高內(nèi)存的使能保證進(jìn)程的可移動性，有效的提高內(nèi)存的使用效率。用效率。l運(yùn)行時重定位有利于多道程序環(huán)境下，進(jìn)程的運(yùn)行時重定位有利于多道程序環(huán)境下，進(jìn)程的換進(jìn)換進(jìn)/ /換出及實(shí)現(xiàn)緊湊技術(shù)。換出及實(shí)現(xiàn)緊湊技術(shù)。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyload 1,2500load 1,2500365365load 1,load 1,250025003653650 01001002500250050005000

12、25002500500005000050000500005010050100+ +52500525005500055000作業(yè)作業(yè)J J處理機(jī)一側(cè)處理機(jī)一側(cè)存儲器一側(cè)存儲器一側(cè)重定位寄存器重定位寄存器( (分區(qū)首地址寄存器分區(qū)首地址寄存器) )相對地址相對地址廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyn4.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 n4.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理 n4.2.3 伙伴系統(tǒng)伙伴系統(tǒng)n4.2.4 主存不足的存儲管理技術(shù)主存不足的存儲管理技術(shù)4.2 4.2 連續(xù)存儲管理連續(xù)存儲管理廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.2.1 固定

13、分區(qū)存儲管理固定分區(qū)存儲管理n分區(qū)管理：分區(qū)管理： 是一種簡單使用的存貯管理方案，是一種簡單使用的存貯管理方案，把內(nèi)存空間靜態(tài)的（動態(tài)的）分割把內(nèi)存空間靜態(tài)的（動態(tài)的）分割成若干大小可以不等的區(qū)域，每個成若干大小可以不等的區(qū)域，每個作業(yè)分配一片連續(xù)的存儲空間，程作業(yè)分配一片連續(xù)的存儲空間，程序一次整體裝入序一次整體裝入n固定式分區(qū)管理：將內(nèi)存空間靜態(tài)的固定式分區(qū)管理：將內(nèi)存空間靜態(tài)的分割成若干大小可以不等的區(qū)域，每分割成若干大小可以不等的區(qū)域，每個分區(qū)只能裝入一道作業(yè)，分區(qū)的個個分區(qū)只能裝入一道作業(yè)，分區(qū)的個數(shù)是內(nèi)存中作業(yè)的最大道數(shù)數(shù)是內(nèi)存中作業(yè)的最大道數(shù)操作系統(tǒng)區(qū)操作系統(tǒng)區(qū)用戶分區(qū)用戶分區(qū)1

14、用戶分區(qū)用戶分區(qū)2用戶分區(qū)用戶分區(qū)3廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy固定分區(qū)存儲管理固定分區(qū)存儲管理( (續(xù)續(xù)) )n劃分分區(qū)的方法：劃分分區(qū)的方法：n分區(qū)大小相等：將內(nèi)存分割成若干個大小相等的區(qū)（太分區(qū)大小相等：將內(nèi)存分割成若干個大小相等的區(qū)（太大造成內(nèi)存的浪費(fèi)，太小不能裝入進(jìn)程運(yùn)行，缺乏靈活大造成內(nèi)存的浪費(fèi)，太小不能裝入進(jìn)程運(yùn)行，缺乏靈活性）性）n分區(qū)大小不等：一部分大的一部分小的，一部分適中的分區(qū)大小不等：一部分大的一部分小的，一部分適中的n注意注意：一個分區(qū)分配了一個作業(yè)后剩余空間便不能再：一個分區(qū)分配了一個作業(yè)后剩余空間便不能再用，這稱為內(nèi)碎片；當(dāng)一個區(qū)域小于一個作

15、業(yè)時便整塊用，這稱為內(nèi)碎片；當(dāng)一個區(qū)域小于一個作業(yè)時便整塊被丟棄，稱為外碎片被丟棄，稱為外碎片廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyn為了記住哪些分區(qū)是空閑分區(qū)，哪些分區(qū)是已分配分區(qū)，為了記住哪些分區(qū)是空閑分區(qū)，哪些分區(qū)是已分配分區(qū)，系統(tǒng)可設(shè)置如下主存分配表：系統(tǒng)可設(shè)置如下主存分配表：分區(qū)分區(qū)號號大小大小(KB)起址起址(KB)狀態(tài)狀態(tài)1824已分配已分配21632已分配已分配33248已分配已分配46480未分配未分配5128144 已分配已分配操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A(7K)A(7K)作業(yè)作業(yè)B(13K)B(13K)作業(yè)作業(yè)C(23K)C(23K)空閑分區(qū)空閑分區(qū)作業(yè)作業(yè)D(

16、80K)D(80K)24K32K48K144K272K80K分區(qū)描述表分區(qū)描述表內(nèi)存分配情況內(nèi)存分配情況碎片碎片廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy固定分區(qū)存儲管理固定分區(qū)存儲管理( (續(xù)續(xù)) )n缺點(diǎn)缺點(diǎn)：n固定分區(qū)存儲管理限制了程序的大小固定分區(qū)存儲管理限制了程序的大小, ,無法運(yùn)行無法運(yùn)行超過分區(qū)大小的程序超過分區(qū)大小的程序n內(nèi)存空間利用率不高內(nèi)存空間利用率不高n不便于程序動態(tài)擴(kuò)充內(nèi)存不便于程序動態(tài)擴(kuò)充內(nèi)存n限制了程序道數(shù)限制了程序道數(shù)n固定分區(qū)存儲管理適合于程序大小和出現(xiàn)頻率已固定分區(qū)存儲管理適合于程序大小和出現(xiàn)頻率已知的情形知的情形廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系

17、kyykyy4.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理按照作業(yè)的大小來劃分分區(qū)，劃分的時間、大小和位置都是按照作業(yè)的大小來劃分分區(qū)，劃分的時間、大小和位置都是動態(tài)的。系統(tǒng)啟動后用戶作業(yè)裝入內(nèi)存之前，整個用戶區(qū)是動態(tài)的。系統(tǒng)啟動后用戶作業(yè)裝入內(nèi)存之前，整個用戶區(qū)是一個大的空閑分區(qū)，隨著作業(yè)的裝入和撤離，內(nèi)存空間被分一個大的空閑分區(qū)，隨著作業(yè)的裝入和撤離，內(nèi)存空間被分成許多大小不一的分區(qū)，有的分區(qū)正被作業(yè)占用，有的分區(qū)成許多大小不一的分區(qū)，有的分區(qū)正被作業(yè)占用，有的分區(qū)是空閑的。當(dāng)一個新的作業(yè)要求裝入時，必須找到一個足夠是空閑的。當(dāng)一個新的作業(yè)要求裝入時，必須找到一個足夠大的空閑區(qū)，如果找到的空

18、閑分區(qū)大于作業(yè)需要量，則把該大的空閑區(qū)，如果找到的空閑分區(qū)大于作業(yè)需要量，則把該空閑分區(qū)分成兩部分，一部分分配給作業(yè)，另一部分作為一空閑分區(qū)分成兩部分，一部分分配給作業(yè)，另一部分作為一個較小的空閑分區(qū)。當(dāng)一個作業(yè)運(yùn)行結(jié)束時，它歸還的分區(qū)個較小的空閑分區(qū)。當(dāng)一個作業(yè)運(yùn)行結(jié)束時，它歸還的分區(qū)如果與其它空閑分區(qū)相鄰，則還要進(jìn)行合并，形成一個大的如果與其它空閑分區(qū)相鄰，則還要進(jìn)行合并，形成一個大的空閑分區(qū)。空閑分區(qū)。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyl一、分區(qū)組織一、分區(qū)組織l1 1空閑分區(qū)表空閑分區(qū)表：在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄：在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個空閑

19、分區(qū)的情況。每個空閑分區(qū)的情況。l2 2空閑分區(qū)鏈：空閑分區(qū)鏈：為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，設(shè)置為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，設(shè)置前向指針和后向指針，通過前、后向鏈接指針將所有的空前向指針和后向指針，通過前、后向鏈接指針將所有的空閑分區(qū)鏈接成一個雙向鏈。閑分區(qū)鏈接成一個雙向鏈。前向前向指針指針分區(qū)分區(qū)信息信息N N個字節(jié)可用個字節(jié)可用后向后向指針指針廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy系統(tǒng)區(qū)系統(tǒng)區(qū)A(8K)B(16K)C(20K)D(28K)E(56K)F(2K)G(40K).024K32K48K68K96K152K154K194K256kA A、B B、C C、D D、E

20、 E、F F、G G任務(wù)陸續(xù)進(jìn)入內(nèi)存進(jìn)任務(wù)陸續(xù)進(jìn)入內(nèi)存進(jìn)行執(zhí)行，行執(zhí)行，T0T0時刻，時刻，A A、C C、E E、G G已經(jīng)完成，請畫出已經(jīng)完成，請畫出當(dāng)前時刻空閑分區(qū)表。當(dāng)前時刻空閑分區(qū)表。如果此時有來了一個如果此時有來了一個15K15K大小大小H H任務(wù)，會分在任務(wù)，會分在哪個空閑分區(qū)里面。哪個空閑分區(qū)里面。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy分區(qū)號分區(qū)號 大小大小(KB)起址起址(KB)狀態(tài)狀態(tài)1824未分配未分配22048未分配未分配35696未分配未分配440154未分配未分配562194未分配未分配空閑分區(qū)表空閑分區(qū)表廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyyky

21、yl1 1最先適應(yīng)算法（首次適應(yīng)算法）。最先適應(yīng)算法（首次適應(yīng)算法）。l每次都從頭開始，尋找第一個滿足需求的空閑分區(qū)。每次都從頭開始，尋找第一個滿足需求的空閑分區(qū)。l特點(diǎn)：找到第一個大小滿足的分區(qū)，劃分。有碎片（外零頭）特點(diǎn)：找到第一個大小滿足的分區(qū)，劃分。有碎片（外零頭），低址內(nèi)存使用頻繁。，低址內(nèi)存使用頻繁。l2 2下次首次適應(yīng)算法（循環(huán)首次適應(yīng)算法）。下次首次適應(yīng)算法（循環(huán)首次適應(yīng)算法）。l與與1 1類似，從上次找到的空閑分區(qū)的下一個開始查找。類似，從上次找到的空閑分區(qū)的下一個開始查找。l特點(diǎn)：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)特點(diǎn)：空閑分區(qū)分布均勻，提高了查找速度；缺乏

22、大的空閑分區(qū)l3 3最佳適應(yīng)算法（最優(yōu)適應(yīng)算法）最佳適應(yīng)算法（最優(yōu)適應(yīng)算法）l分區(qū)按大小遞增排序；分區(qū)釋放時需插入到適當(dāng)位置。分區(qū)按大小遞增排序；分區(qū)釋放時需插入到適當(dāng)位置。l特點(diǎn)：產(chǎn)生無法利用的小碎片。特點(diǎn)：產(chǎn)生無法利用的小碎片。l4. 4. 最壞適應(yīng)算法最壞適應(yīng)算法l掃描整個空閑分區(qū)表或空閑分區(qū)鏈掃描整個空閑分區(qū)表或空閑分區(qū)鏈, ,總是挑選一個最大的空閑總是挑選一個最大的空閑區(qū)分割給作業(yè)使用區(qū)分割給作業(yè)使用l特點(diǎn)：分割剩余的空閑區(qū)不至于太小特點(diǎn)：分割剩余的空閑區(qū)不至于太小二、分區(qū)分配二、分區(qū)分配廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時，需合并相鄰的空當(dāng)進(jìn)程

23、運(yùn)行完畢釋放內(nèi)存時，需合并相鄰的空閑分區(qū)，形成大的分區(qū)，稱為合并技術(shù)。閑分區(qū)，形成大的分區(qū)，稱為合并技術(shù)。（1 1）上鄰空閑區(qū)：合并，改大小）上鄰空閑區(qū)：合并，改大?。? 2）下鄰空閑區(qū)：合并，改大小，首址。）下鄰空閑區(qū)：合并，改大小，首址。（3 3）上、下鄰空閑區(qū)：合并，改大小。）上、下鄰空閑區(qū)：合并，改大小。（4 4）不鄰接，則建立一新表項(xiàng)。）不鄰接，則建立一新表項(xiàng)。三、分區(qū)回收三、分區(qū)回收進(jìn)程進(jìn)程1 1F1F1回收區(qū)回收區(qū)進(jìn)程進(jìn)程2 2進(jìn)程進(jìn)程3 3進(jìn)程進(jìn)程1 1進(jìn)程進(jìn)程2 2回收區(qū)回收區(qū)F2F2進(jìn)程進(jìn)程3 3進(jìn)程進(jìn)程1 1F1F1回收區(qū)回收區(qū)F2F2進(jìn)程進(jìn)程2 2內(nèi)存回收時的情況內(nèi)存回

24、收時的情況F1F1進(jìn)程進(jìn)程1 1回收區(qū)回收區(qū)進(jìn)程進(jìn)程2 2F2F2廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy2.2.地址轉(zhuǎn)換與存儲保護(hù)地址轉(zhuǎn)換與存儲保護(hù)n可變分區(qū)方式采用動態(tài)重定位裝入作業(yè)可變分區(qū)方式采用動態(tài)重定位裝入作業(yè), ,作業(yè)程序作業(yè)程序和數(shù)據(jù)的地址轉(zhuǎn)換由硬件完成和數(shù)據(jù)的地址轉(zhuǎn)換由硬件完成. .硬件設(shè)置兩個控制硬件設(shè)置兩個控制寄存器寄存器: :基址寄存器和限長寄存器基址寄存器和限長寄存器.基址寄存器存放基址寄存器存放分配給作業(yè)使用的分區(qū)的起始地址分配給作業(yè)使用的分區(qū)的起始地址,限長寄存器存放限長寄存器存放作業(yè)占用的連續(xù)存儲空間的長度作業(yè)占用的連續(xù)存儲空間的長度n當(dāng)作業(yè)占有當(dāng)作業(yè)占

25、有CPU運(yùn)行時運(yùn)行時,操作系統(tǒng)把作業(yè)所占分區(qū)操作系統(tǒng)把作業(yè)所占分區(qū)的始址和長度送入基址寄存器和限長寄存器的始址和長度送入基址寄存器和限長寄存器.隨著逐隨著逐條指令的執(zhí)行和數(shù)據(jù)訪問完成地址轉(zhuǎn)換條指令的執(zhí)行和數(shù)據(jù)訪問完成地址轉(zhuǎn)換n當(dāng)邏輯地址小于限長值時，可獲得絕對地址，大當(dāng)邏輯地址小于限長值時，可獲得絕對地址，大于時，不允許訪問于時，不允許訪問廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy基址基址基址寄存器基址寄存器邏輯地址邏輯地址CPUCPU絕對地址絕對地址操作系統(tǒng)區(qū)操作系統(tǒng)區(qū)空閑分區(qū)空閑分區(qū)1 1用戶作業(yè)用戶作業(yè)1 1空閑分區(qū)空閑分區(qū)2 2限長限長限長寄存器限長寄存器 限長限長越界中斷越界

26、中斷廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy動態(tài)分區(qū)特點(diǎn)動態(tài)分區(qū)特點(diǎn)n系統(tǒng)初啟時，整個內(nèi)存只有一個自由塊系統(tǒng)初啟時，整個內(nèi)存只有一個自由塊n需調(diào)入一個作業(yè)時，查找所有的自由塊直到找到一需調(diào)入一個作業(yè)時，查找所有的自由塊直到找到一個滿足要求的并把它分給該作業(yè)個滿足要求的并把它分給該作業(yè)n當(dāng)自由塊較大以至滿足一個作業(yè)的需求后仍有剩余當(dāng)自由塊較大以至滿足一個作業(yè)的需求后仍有剩余則將剩余量構(gòu)成一個新的自由塊交給系統(tǒng)則將剩余量構(gòu)成一個新的自由塊交給系統(tǒng)n當(dāng)一個作業(yè)運(yùn)行完畢并釋放了其所得到的空間時，當(dāng)一個作業(yè)運(yùn)行完畢并釋放了其所得到的空間時，要考慮它上下是否鄰接自由塊，若有合并它們?yōu)橐灰紤]它上

27、下是否鄰接自由塊，若有合并它們?yōu)橐粋€較大的自由塊個較大的自由塊n解決了內(nèi)碎片的問題，但會產(chǎn)生很多較小的外碎片解決了內(nèi)碎片的問題，但會產(chǎn)生很多較小的外碎片（相對的概念）（相對的概念）廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式限制了活動進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)大小不匹配限制了活動進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)大小不匹配時，內(nèi)存空間利用率很低。動態(tài)分區(qū)方式算法復(fù)雜，回收空時，內(nèi)存空間利用率很低。動態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大。伙伴系統(tǒng)方閑分區(qū)時需要進(jìn)

28、行分區(qū)合并等，系統(tǒng)開銷較大。伙伴系統(tǒng)方式是對以上兩種內(nèi)存方式的一種折衷方案。式是對以上兩種內(nèi)存方式的一種折衷方案?；锇橄到y(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為為2 2的的k k次冪，次冪，k k為整數(shù)，為整數(shù)，lkm，其中：，其中：21表示分配的最小表示分配的最小分區(qū)的大小，分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常表示分配的最大分區(qū)的大小，通常2m是整個是整個可分配內(nèi)存的大小?？煞峙鋬?nèi)存的大小。4.2.4 4.2.4 動態(tài)分區(qū)的實(shí)例動態(tài)分區(qū)的實(shí)例伙伴系統(tǒng)伙伴系統(tǒng)廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy當(dāng)需要為進(jìn)程分配一個長度

29、為當(dāng)需要為進(jìn)程分配一個長度為n的存儲空間時，首先計算的存儲空間時，首先計算一個一個i值，使值，使2i1n2i，然后在空閑分區(qū)大小為，然后在空閑分區(qū)大小為2i的空閑分區(qū)的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，表明長度為表明長度為2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i1的空的空閑分區(qū)鏈表中尋找。若存在閑分區(qū)鏈表中尋找。若存在2i1的一個空閑分區(qū)，則把該空閑的一個空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個分區(qū)，這兩個分區(qū)稱為一對伙伴，其中分區(qū)分為相等的兩個分區(qū)，這兩個分區(qū)稱為一對伙伴，其中的一

30、個分區(qū)用于分配，而把另一個加入分區(qū)大小為的一個分區(qū)用于分配，而把另一個加入分區(qū)大小為2i的空閑分的空閑分區(qū)鏈表中。若大小為區(qū)鏈表中。若大小為2i1的空閑分區(qū)也不存在，則需要查找大的空閑分區(qū)也不存在，則需要查找大小為小為2i2的空閑分區(qū)，若找到則對其進(jìn)行兩次分割：第一次，的空閑分區(qū)，若找到則對其進(jìn)行兩次分割：第一次，將其分割為大小為將其分割為大小為2i1的兩個分區(qū)，一個用于分配，一個加入的兩個分區(qū)，一個用于分配，一個加入到大小為到大小為2i1的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為的空閑區(qū)分割為2i的兩個分區(qū)，一個用于分配，一個加入到大的

31、兩個分區(qū)，一個用于分配，一個加入到大小為小為2i的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為2i3的空閑分區(qū)，以此類推。由此可見，在最壞的情況下，可的空閑分區(qū)，以此類推。由此可見，在最壞的情況下，可能需要對能需要對2k的空閑分區(qū)進(jìn)行的空閑分區(qū)進(jìn)行k次分割才能得到所需分區(qū)。次分割才能得到所需分區(qū)。 廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy與一次分配可能要進(jìn)行多次分割一樣，一次回收也可能要與一次分配可能要進(jìn)行多次分割一樣，一次回收也可能要進(jìn)行多次合并，如回收大小為進(jìn)行多次合并，如回收大小為2i的空閑分區(qū)時，若事先已存的空閑分區(qū)時，若事先

32、已存在在2i的空閑分區(qū)時，則應(yīng)將其與伙伴分區(qū)合并為大小為的空閑分區(qū)時，則應(yīng)將其與伙伴分區(qū)合并為大小為2i1的空閑分區(qū)，若事先已存在的空閑分區(qū)，若事先已存在2i1的空閑分區(qū)時，又應(yīng)繼續(xù)與的空閑分區(qū)時，又應(yīng)繼續(xù)與其伙伴分區(qū)合并為大小為其伙伴分區(qū)合并為大小為2i2的空閑分區(qū)，依此類推。的空閑分區(qū)，依此類推。在伙伴系統(tǒng)中，其分配和回收的時間性能取決于查找空在伙伴系統(tǒng)中，其分配和回收的時間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時間。與前面閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時間。與前面所述的多種方法相比較，由于該算法在回收空閑分區(qū)時，需所述的多種方法相比較，由于該算法在回收空閑分區(qū)

33、時，需要對空閑分區(qū)進(jìn)行合并，所以其時間性能比前面所述的分類要對空閑分區(qū)進(jìn)行合并，所以其時間性能比前面所述的分類搜索算法差，但比順序搜索算法好，而其空間性能則遠(yuǎn)優(yōu)于搜索算法差，但比順序搜索算法好，而其空間性能則遠(yuǎn)優(yōu)于前面所述的分類搜索法，比順序搜索法略差。前面所述的分類搜索法，比順序搜索法略差。 廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyn當(dāng)一個新的作業(yè)要求裝入當(dāng)一個新的作業(yè)要求裝入, ,沒有一個空閑分區(qū)能夠滿沒有一個空閑分區(qū)能夠滿足要求足要求, ,但所有空閑分區(qū)之和能夠滿足要求時但所有空閑分區(qū)之和能夠滿足要求時, ,可以移可以移動內(nèi)存作

34、業(yè)動內(nèi)存作業(yè), ,合并這些小的空閑分區(qū)合并這些小的空閑分區(qū), ,使之滿足新來的使之滿足新來的作業(yè)。作業(yè)移動后作業(yè)。作業(yè)移動后, ,要及時修改它們的基址。要及時修改它們的基址。操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)作業(yè)44.2.34.2.3主存不足的存儲管理技術(shù)主存不足的存儲管理技術(shù)- -移動技術(shù)移動技術(shù)廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyl 對換的引入對換的引入l將阻塞進(jìn)程，暫時不用的程序、數(shù)據(jù)換出。將阻塞進(jìn)程，暫時不用的程序、數(shù)據(jù)換出。l將具備運(yùn)行條件的進(jìn)程換入。將具備運(yùn)行條件的進(jìn)程換入。l類型：類型：l整體

35、對換：進(jìn)程對換，解決內(nèi)存緊張整體對換：進(jìn)程對換，解決內(nèi)存緊張l部分對換：頁面對換部分對換：頁面對換/ /分段對換：提供虛存支持分段對換：提供虛存支持l 對換空間管理對換空間管理l外存外存 l對換區(qū)對換區(qū)比比文件區(qū)文件區(qū)側(cè)重于對換速度。側(cè)重于對換速度。l因此，對換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和分配因此，對換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和分配回收類似于動態(tài)分區(qū)分配。回收類似于動態(tài)分區(qū)分配。4.2.34.2.3主存不足的存儲管理技術(shù)主存不足的存儲管理技術(shù)- -對換技術(shù)對換技術(shù)廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyl連續(xù)分配引起連續(xù)分配引起: :碎片碎片l離散分配方式離散分配方式l

36、分頁存儲管理分頁存儲管理l將一個進(jìn)程的邏輯地址空間分成若干個大小相等的頁面將一個進(jìn)程的邏輯地址空間分成若干個大小相等的頁面，把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱，把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為頁框，在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的為頁框，在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以不相鄰接的頁框中。若干個頁分別裝入到多個可以不相鄰接的頁框中。l分段存儲管理分段存儲管理l作業(yè)的地址空間被劃分為若干個段，每個段定義了一組作業(yè)的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。每個段都有自己的名字。邏輯信息。每個段都有自己的名字。 每個段都

37、從每個段都從0開始開始編址，并采用一段連續(xù)的地址空間。段的長度由相應(yīng)的編址，并采用一段連續(xù)的地址空間。段的長度由相應(yīng)的邏輯信息組的長度決定，因而各段長度不等。邏輯信息組的長度決定，因而各段長度不等。 l段頁存儲管理段頁存儲管理l是分段和分頁原理的結(jié)合，即先將用戶程序分成若干個是分段和分頁原理的結(jié)合，即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。段名。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyn4.3.1 分頁式存儲管理的基本原理n4.3.2 快表n4.3.3 分頁式存儲空間的分配和去配n4.3.4 分頁式存

38、儲空間的頁面共享和保護(hù)n4.3.5 多級頁表4.3 4.3 分頁存儲管理分頁存儲管理廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.3.1 分頁式存儲管理的基本原理分頁式存儲管理的基本原理l將一個進(jìn)程的邏輯地址空間分成若干個大小相等的區(qū)，將一個進(jìn)程的邏輯地址空間分成若干個大小相等的區(qū)，稱為稱為頁面頁面或頁，相應(yīng)地，也把內(nèi)存空間分成與頁面相同或頁，相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為大小的若干個存儲塊，稱為頁框頁框，在為進(jìn)程分配內(nèi)存時，在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以不相鄰接的頁框中。不

39、相鄰接的頁框中。n對頁框和頁面都加以編號，從對頁框和頁面都加以編號，從0 0開始，如第開始，如第0 0號、第號、第1 1號等號等l由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為的碎片，稱之為“頁內(nèi)碎片頁內(nèi)碎片”或稱為或稱為“內(nèi)零頭內(nèi)零頭”。 廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyl1.1.頁面頁面l頁面和頁框：邏輯空間和內(nèi)存空間頁面和頁框：邏輯空間和內(nèi)存空間l由機(jī)器的地址結(jié)構(gòu)決定由機(jī)器的地址結(jié)構(gòu)決定l頁太大，頁內(nèi)碎片大。頁太大，頁內(nèi)碎片大。l頁太?。喉摫砜赡芎荛L，換入頁太?。喉摫砜赡芎荛L，換入/ /出效率低出效率低l2

40、.2.地址結(jié)構(gòu)地址結(jié)構(gòu) 31 31 12 1112 11 0 0邏輯地址邏輯地址A A；頁大?。豁摯笮(L(設(shè)為設(shè)為4096)4096)；頁內(nèi)偏移；頁內(nèi)偏移d dP=(int)A/L d=A mod LP=(int)A/L d=A mod L如：如： A A8210B. 8210B. 則則P=2, d=18 P=2, d=18 分頁存儲管理分頁存儲管理頁號頁號P P 頁內(nèi)位移頁內(nèi)位移d d 廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy3 3、頁表、頁表0 0頁頁1 1頁頁2 2頁頁3 3頁頁4 4頁頁5 5頁頁n n頁頁0 02 21 13 32 26 63 38 84 49 95 5

41、n n0 01 12 23 34 45 56 67 78 89 9用戶程序用戶程序頁表頁表頁面號頁面號 頁框號頁框號內(nèi)存內(nèi)存廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy地址轉(zhuǎn)換地址轉(zhuǎn)換 l由頁表完成邏輯頁號由頁表完成邏輯頁號物理頁框號的映射。物理頁框號的映射。l一、基本地址變換機(jī)構(gòu)：一、基本地址變換機(jī)構(gòu)：l越界保護(hù)越界保護(hù)l每個進(jìn)程對應(yīng)一頁表，其信息（如長度、始址）放在每個進(jìn)程對應(yīng)一頁表，其信息（如長度、始址）放在PCBPCB中，執(zhí)行時將其首地址裝入中，執(zhí)行時將其首地址裝入頁表寄存器頁表寄存器。n二、地址轉(zhuǎn)換的過程二、地址轉(zhuǎn)換的過程n進(jìn)程運(yùn)行前系統(tǒng)把頁表基址存入頁表基址寄存器進(jìn)程運(yùn)行前系

42、統(tǒng)把頁表基址存入頁表基址寄存器n運(yùn)行時硬件自動將邏輯地址分成兩部分，頁號運(yùn)行時硬件自動將邏輯地址分成兩部分，頁號P和頁內(nèi)位和頁內(nèi)位移移dn找到頁表基址后，按頁號找到頁表基址后，按頁號P作為索引查頁表，得到頁框號，作為索引查頁表，得到頁框號，根據(jù)公式完成地址轉(zhuǎn)換根據(jù)公式完成地址轉(zhuǎn)換物理地址物理地址 = 頁框號頁框號塊長塊長 + 頁內(nèi)位移頁內(nèi)位移廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy分頁系統(tǒng)地址轉(zhuǎn)換分頁系統(tǒng)地址轉(zhuǎn)換頁表始址頁表始址頁表長度頁表長度頁號頁號(3) 頁內(nèi)地址頁內(nèi)地址(342)(342)頁表寄存器頁表寄存器邏輯地址邏輯地址(12630)(12630)越界中斷越界中斷5頁框號頁

43、框號頁表頁表頁號頁號0123物理地址物理地址68155頁號頁號01236815廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.3.2 快表快表n由于頁表放在內(nèi)存中，這樣，由于頁表放在內(nèi)存中，這樣，CPUCPU每存取一個數(shù)據(jù)時，每存取一個數(shù)據(jù)時，需要兩次訪問內(nèi)存需要兩次訪問內(nèi)存n一次訪問頁表取得物理塊號以形成物理地址一次訪問頁表取得物理塊號以形成物理地址n第二次根據(jù)物理地址存取數(shù)據(jù)第二次根據(jù)物理地址存取數(shù)據(jù), ,速度降低了一倍速度降低了一倍n為了提高速度為了提高速度, ,在存儲管理部件中增設(shè)一個專用的高在存儲管理部件中增設(shè)一個專用的高速緩沖存儲器速緩沖存儲器, ,用來存放最近訪問過的部分頁

44、表用來存放最近訪問過的部分頁表, ,這種這種相聯(lián)存儲器稱為快表；快表昂貴，不易過多。相聯(lián)存儲器稱為快表；快表昂貴，不易過多。n如如Intel80486Intel80486的快表為的快表為3232個單元個單元廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy具有快表的分頁系統(tǒng)地址轉(zhuǎn)換具有快表的分頁系統(tǒng)地址轉(zhuǎn)換頁表始址頁表始址頁表長度頁表長度頁號頁號(2) 頁內(nèi)地址頁內(nèi)地址(342)(342)頁表寄存器頁表寄存器邏輯地址邏輯地址越界中斷越界中斷5頁框號頁框號頁表頁表頁號頁號0123物理地址物理地址6815相相聯(lián)聯(lián)存存儲儲器器快表快表501268頁框號頁框號頁號頁號廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)

45、系 kyykyyn有了快表有了快表, ,根據(jù)頁號查找對應(yīng)的物理塊號時：根據(jù)頁號查找對應(yīng)的物理塊號時：n首先查找快表，若找到則將物理塊號和頁內(nèi)地址（也是首先查找快表，若找到則將物理塊號和頁內(nèi)地址（也是塊內(nèi)地址）拼接形成物理地址塊內(nèi)地址）拼接形成物理地址 n若在快表中未找到物理塊號，則再查找內(nèi)存頁表，獲取若在快表中未找到物理塊號，則再查找內(nèi)存頁表，獲取物理塊號，一方面形成物理地址，另一方面將該表項(xiàng)抄到物理塊號，一方面形成物理地址，另一方面將該表項(xiàng)抄到快表中，以備下次再次訪問該頁面快表中，以備下次再次訪問該頁面 n有的系統(tǒng)查快表和查內(nèi)存頁表是同時進(jìn)行的，一旦從快有的系統(tǒng)查快表和查內(nèi)存頁表是同時進(jìn)行的

46、，一旦從快表中找到了對應(yīng)項(xiàng)，則立即停止對內(nèi)存頁表的查找表中找到了對應(yīng)項(xiàng)，則立即停止對內(nèi)存頁表的查找n當(dāng)快表已滿且要登記新頁時，需要淘汰舊快表項(xiàng)，最簡當(dāng)快表已滿且要登記新頁時，需要淘汰舊快表項(xiàng)，最簡單的策略是單的策略是“先進(jìn)先出先進(jìn)先出”廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy 例：有一分頁式系統(tǒng)，其頁表存放在主存中：例：有一分頁式系統(tǒng)，其頁表存放在主存中： 如果對主存的一次存取需要如果對主存的一次存取需要10ns,10ns,試問實(shí)現(xiàn)試問實(shí)現(xiàn)一次頁面訪問的存取時間是多少一次頁面訪問的存取時間是多少? ? 如果系統(tǒng)加有快表如果系統(tǒng)加有快表, ,平均命中率為平均命中率為85%,85%,當(dāng)頁

47、當(dāng)頁表項(xiàng)在快表中時表項(xiàng)在快表中時, ,其查找時間為其查找時間為2ns, 2ns, 試問此試問此時的存取時間是多少時的存取時間是多少? ?廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy答：若頁表存放在主存中，則要實(shí)現(xiàn)一次頁面訪問需兩次答：若頁表存放在主存中，則要實(shí)現(xiàn)一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁面數(shù)據(jù)。址（稱為定位）。第二次才根據(jù)該地址存取頁面數(shù)據(jù)。 頁表在主存的存取訪問時間頁表在主存的存取訪問時間 =10=10* *2=20(ns)2=20(ns) 增加快表后的存取訪

48、問時間增加快表后的存取訪問時間 =0.85=0.85* *12+(1-0.85)12+(1-0.85)* *（2+102+10* *2 2）=13.4(ns)=13.4(ns)廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.3.3 4.3.3 分頁式存儲空間的分配和去配分頁式存儲空間的分配和去配n位示圖由一些二進(jìn)制位組成,每一位對應(yīng)一個內(nèi)存物理塊,位值表示所對應(yīng)的物理塊是否已分配出去.分配和回收物理塊時只需修改位值即可n鏈表方法111110001111111111001111110001110000000111111111110000001111111111100000011廣州商學(xué)院計

49、算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.3.4 分頁式存儲空間的共享與保護(hù)分頁式存儲空間的共享與保護(hù)n分頁存儲管理在實(shí)現(xiàn)共享時分頁存儲管理在實(shí)現(xiàn)共享時,必須區(qū)分?jǐn)?shù)據(jù)共享和程序共享必須區(qū)分?jǐn)?shù)據(jù)共享和程序共享,實(shí)實(shí)現(xiàn)數(shù)據(jù)共享時現(xiàn)數(shù)據(jù)共享時,允許不同的作業(yè)對共享的數(shù)據(jù)頁使用不同的頁允許不同的作業(yè)對共享的數(shù)據(jù)頁使用不同的頁號號,只要讓各自頁表中的有關(guān)表目指向共享的數(shù)據(jù)信息塊就行只要讓各自頁表中的有關(guān)表目指向共享的數(shù)據(jù)信息塊就行了了n實(shí)現(xiàn)程序共享時實(shí)現(xiàn)程序共享時,由于頁式存儲結(jié)構(gòu)要求邏輯地址空間是連續(xù)由于頁式存儲結(jié)構(gòu)要求邏輯地址空間是連續(xù)的的,所以程序運(yùn)行前它們的頁號就確定了所以程序運(yùn)行前它們的頁號就

50、確定了.對共享的程序必須規(guī)對共享的程序必須規(guī)定一個統(tǒng)一的頁號定一個統(tǒng)一的頁號.當(dāng)共享程序的作業(yè)數(shù)增多時當(dāng)共享程序的作業(yè)數(shù)增多時,要規(guī)定一個統(tǒng)要規(guī)定一個統(tǒng)一的頁號是困難的一的頁號是困難的n實(shí)現(xiàn)信息保護(hù)的辦法是在頁表中增加一些標(biāo)志位實(shí)現(xiàn)信息保護(hù)的辦法是在頁表中增加一些標(biāo)志位,用來指出該用來指出該頁的信息可讀頁的信息可讀/寫寫只讀只讀只可執(zhí)行只可執(zhí)行不可訪問等不可訪問等廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.3.5 多級頁表多級頁表n現(xiàn)代的大多數(shù)計算機(jī)系統(tǒng)，都支持非常大的邏輯地址現(xiàn)代的大多數(shù)計算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間空間(232264)。在這樣的環(huán)境下，頁表就變得非常大，。

51、在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。要占用相當(dāng)大的內(nèi)存空間。n例如，對于一個具有例如，對于一個具有32位邏輯地址空間的分頁系統(tǒng)，位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為規(guī)定頁面大小為4 KB，則在每個進(jìn)程頁表中的頁表項(xiàng)可，則在每個進(jìn)程頁表中的頁表項(xiàng)可達(dá)達(dá)1兆個之多，又因?yàn)槊總€頁表項(xiàng)占用兆個之多，又因?yàn)槊總€頁表項(xiàng)占用4個字節(jié)，個字節(jié)， 故每故每個進(jìn)程僅僅其頁表就要占用個進(jìn)程僅僅其頁表就要占用4 MB的內(nèi)存空間，而且還的內(nèi)存空間，而且還要求是連續(xù)的。要求是連續(xù)的。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy多級頁表（續(xù)）多級頁表（續(xù)）n多級頁表實(shí)現(xiàn)方法多級頁表實(shí)現(xiàn)方法n

52、 （1）把整個頁表進(jìn)行分頁，分成一張張小頁表）把整個頁表進(jìn)行分頁，分成一張張小頁表(稱為頁表稱為頁表頁或頁目錄表頁或頁目錄表)，小頁表的大小與頁框相同，為進(jìn)行索引查，小頁表的大小與頁框相同，為進(jìn)行索引查找，為這些小頁表建一張頁目錄表，其表項(xiàng)指出小頁表所在找，為這些小頁表建一張頁目錄表，其表項(xiàng)指出小頁表所在頁框號及相關(guān)信息頁框號及相關(guān)信息n （2）系統(tǒng)為每個進(jìn)程建一張頁目錄表，它的每個表項(xiàng)對應(yīng)）系統(tǒng)為每個進(jìn)程建一張頁目錄表，它的每個表項(xiàng)對應(yīng)一個頁表頁，而頁表頁的每個表項(xiàng)給出了頁面和頁框的對應(yīng)一個頁表頁，而頁表頁的每個表項(xiàng)給出了頁面和頁框的對應(yīng)關(guān)系關(guān)系,頁目錄表是一級頁表，頁表頁是二級頁表頁目錄表

53、是一級頁表，頁表頁是二級頁表n （3）邏輯地址結(jié)構(gòu)有三部分組成：頁目錄、頁表頁和位移）邏輯地址結(jié)構(gòu)有三部分組成：頁目錄、頁表頁和位移 廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy B offset目錄位移 頁表頁位移 頁內(nèi)位移BF進(jìn)程一級頁表進(jìn)程二級頁表物理地址邏輯地址頁目錄表控制寄存器廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyn4.4.1 程序分段結(jié)構(gòu)程序分段結(jié)構(gòu)n4.4.2 分段式存儲管理的基本原理分段式存儲管理的基本原理n4.4.3 段的共享和保護(hù)段的共享和保護(hù)n4.4.4 分段和分頁的比較分段和分頁的比較4.4 分段式存儲

54、管理分段式存儲管理廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyn基于模塊化的程序設(shè)計，通常將一個大任務(wù)分成基于模塊化的程序設(shè)計，通常將一個大任務(wù)分成若干個相對獨(dú)立的子任務(wù)，對應(yīng)于子任務(wù)編寫子若干個相對獨(dú)立的子任務(wù)，對應(yīng)于子任務(wù)編寫子程序，稱為段。程序，稱為段。n各個子程序可以獨(dú)立的編輯、編譯、鏈接和執(zhí)行各個子程序可以獨(dú)立的編輯、編譯、鏈接和執(zhí)行n各個子程序由實(shí)現(xiàn)的功能決定，長度各不相同。各個子程序由實(shí)現(xiàn)的功能決定，長度各不相同。執(zhí)行時，根據(jù)實(shí)際需要將各個子程序鏈接成一個執(zhí)行時，根據(jù)實(shí)際需要將各個子程序鏈接成一個大程序。大程序。4.4.1 程序分段結(jié)構(gòu)程序分段結(jié)構(gòu)- -分段存儲管理的引入分

55、段存儲管理的引入廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.4.2 分段式存儲管理的基本原理分段式存儲管理的基本原理 段號 段內(nèi)偏移量l在分段存儲管理方式中，作業(yè)的地址空間被劃分為在分段存儲管理方式中，作業(yè)的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。若干個段，每個段定義了一組邏輯信息。 l每個段都有自己的名字。每個段都有自己的名字。 l每個段都從每個段都從0 0開始編址，并采用一段連續(xù)的地址空開始編址，并采用一段連續(xù)的地址空間。段的長度由相應(yīng)的邏輯信息組的長度決定，因間。段的長度由相應(yīng)的邏輯信息組的長度決定，因而各段長度不等。整個作業(yè)的地址空間，由于是分而各段長度不等。整個

56、作業(yè)的地址空間，由于是分成多個段，因而是二維的，亦即，其邏輯地址由段成多個段，因而是二維的，亦即，其邏輯地址由段號（段名）和段內(nèi)地址所組成。號（段名）和段內(nèi)地址所組成。l分段地址中的地址具有如下結(jié)構(gòu)：分段地址中的地址具有如下結(jié)構(gòu)：廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy作業(yè)空間作業(yè)空間（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k內(nèi)存空間內(nèi)存空間30k 40k20k 80k 15k 120k 10k 150k 段長段長 段首址段首址段號段號0123段表段表段表：為每個分段分配一個連續(xù)的分區(qū)，而進(jìn)程中的段表：為每個分段分配一個連續(xù)的分區(qū)，而進(jìn)程中的各個段

57、可以離散地移入內(nèi)存中不同的分區(qū)中。各個段可以離散地移入內(nèi)存中不同的分區(qū)中。廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy段表始址段表始址段表長度段表長度段號段號（2)100段表寄存器段表寄存器邏輯地址邏輯地址越界中斷越界中斷122980物理地址物理地址分段系統(tǒng)地址變換機(jī)構(gòu)分段系統(tǒng)地址變換機(jī)構(gòu)30k 40k20k 80k 15k 120k 10k 150k 段長段長 段首址段首址段號段號0123段表段表廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy例題例題對以下段表,請將邏輯地址(0,137),(1,4000),(2,3600),(5,230) 轉(zhuǎn)換成物理地址.段號段號起始地址起始地址

58、段長段長050K10KB160K3KB2120K5KB370K8KB4150K4KB廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy4.4.3 段的共享和保護(hù)段的共享和保護(hù)n段的共享是通過不同作業(yè)段表中的項(xiàng)指向同一個段基址來實(shí)現(xiàn)的n于是，幾道作業(yè)共享的程序就可放在一個段中，只要讓各道作業(yè)的共享部分有相同的基址/限長值就可以了n必須對共享段的信息進(jìn)行存取控制和保護(hù)廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyyed1ed2ed40data1_1data1_10021122406041615070ed1ed2ed40data1_1data1_10data2_1data2_10進(jìn)程進(jìn)程1進(jìn)程進(jìn)程

59、2頁表頁表頁表頁表ed1ed2ed40data2_1data2_10主存分頁系統(tǒng)中共享分頁系統(tǒng)中共享editor02112240604161廣州商學(xué)院計算機(jī)系廣州商學(xué)院計算機(jī)系 kyykyy分段系統(tǒng)中共享分段系統(tǒng)中共享editoreditordata1editordata2段長段長基址基址1608040240段長段長基址基址1608040380editordata1data2在分段系統(tǒng)中，實(shí)現(xiàn)共享則容易得多，只需在每個進(jìn)程在分段系統(tǒng)中，實(shí)現(xiàn)共享則容易得多，只需在每個進(jìn)程的段表中為文本編輯程序設(shè)置一個段表項(xiàng)。的段表中為文本編輯程序設(shè)置一個段表項(xiàng)。進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2段表段表廣州商學(xué)院計算機(jī)系廣州

60、商學(xué)院計算機(jī)系 kyykyy4.4.4 分段和分頁的比較分段和分頁的比較n分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定定,用戶可見；分頁是信息的物理單位，與源程序的用戶可見；分頁是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無關(guān)，用戶不可見。邏輯結(jié)構(gòu)無關(guān)，用戶不可見。n段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何主存地址開始；頁長由系統(tǒng)確定，頁面只能以頁大主存地址開始；頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始。小的整倍數(shù)地址開始。n分段方式中分段方式中,源程序源程序(段號段號,段內(nèi)位移段內(nèi)位移)經(jīng)連結(jié)裝配后