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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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