計(jì)算機(jī)組成原理

Chapter4

存儲管理南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院主講教師

周建美Mail：zhou.jm@今天雖然主存價(jià)格已相當(dāng)便宜，但主存容量仍然是計(jì)算機(jī)四大硬件資源（CPU、主板、內(nèi)存、顯卡）中最關(guān)鍵而又最緊張的“瓶頸”資源。因此對主存的管理和有效使用仍然是今天操作系統(tǒng)十分重要的內(nèi)容。許多操作系統(tǒng)之間最明顯的區(qū)別特征之一往往是所使用的存儲管理方法不同。如OS/360-MFT采用固定分區(qū)存儲管理技術(shù)，OS/360-MTV是采用可變分區(qū)存儲管理技術(shù)，OS/2，WindowsNT,是采用虛擬存儲管理技術(shù)。主存儲器管理技術(shù)可分為兩大類：實(shí)存儲器管理和虛擬存儲器管理。存儲管理的功能分配和去配：抽象和映射：隔離和共享：存儲擴(kuò)充：本章內(nèi)容存儲器連續(xù)存儲空間分頁式存儲管理分段式存儲管理虛擬存儲管理4.1主存儲器內(nèi)容：存儲器的層次 地址轉(zhuǎn)換與存儲保護(hù)

4.1.1存儲器的層次存儲器的層次(1)寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動(dòng)存儲介質(zhì)存儲器的層次(2)

某臺計(jì)算機(jī)存儲器層次配置CPU中的寄存器100個(gè)字；高速緩存512KB，存取周期15ns；主存儲器128MB，存取周期60ns；磁盤容量20GB，存取周期毫秒級；后援存儲容量1TB，存取周期秒級。

4.1.2地址轉(zhuǎn)換與存儲保護(hù)鏈接動(dòng)態(tài)重定位靜態(tài)重定位…源程序模塊1源程序模塊2源程序模塊n…目標(biāo)代碼1目標(biāo)代碼2目標(biāo)代碼n可重定位目標(biāo)代碼(裝載代碼)(輔存)編譯裝入執(zhí)行程序名字空間邏輯地址空間物理地址空間可執(zhí)行二進(jìn)代碼(主存)庫代碼可執(zhí)行二進(jìn)代碼(主存)

程序的編譯、鏈接、裝入和執(zhí)行

地址轉(zhuǎn)換與存儲保護(hù)邏輯地址（相對地址）與物理地址（絕對地址）邏輯地址空間與物理地址空間地址轉(zhuǎn)換或重定位靜態(tài)重定位與動(dòng)態(tài)重定位存儲保護(hù)4.2連續(xù)存儲空間管理內(nèi)容：固定分區(qū)存儲管理 可變分區(qū)存儲管理 伙伴系統(tǒng)主存不足的存儲管理技術(shù)4.2.1固定分區(qū)存儲管理固定分區(qū)存儲管理固定分區(qū)存儲管理的基本思想：固定分區(qū)存儲管理的數(shù)據(jù)結(jié)構(gòu)：作業(yè)進(jìn)入固定分區(qū)排隊(duì)策略：一是每個(gè)分區(qū)排一個(gè)等待處理的隊(duì)列,等待處理作業(yè)大小不均,導(dǎo)致有的分區(qū)空閑而有的分區(qū)忙碌;二是所有等待處理的作業(yè)排成一個(gè)隊(duì)列,當(dāng)調(diào)度其中一個(gè)進(jìn)入分區(qū)運(yùn)行時(shí),選擇可容納它的最小可用分區(qū),以充分利用主存。固定分區(qū)存儲管理的地址轉(zhuǎn)換和存儲保護(hù)

B下限寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)用戶分區(qū)1用戶分區(qū)2用戶分區(qū)3B+L2上限寄存器<B+L2越界中斷用戶分區(qū)4用戶分區(qū)5用戶分區(qū)64.2.2可變分區(qū)存儲管理可變分區(qū)存儲管理

可變分區(qū)(variablepartition)存儲管理是按作業(yè)的實(shí)際大小來劃分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的，劃分的時(shí)間、大小、位置都是動(dòng)態(tài)的，實(shí)現(xiàn)多個(gè)作業(yè)對內(nèi)存的共享，進(jìn)一步提高內(nèi)存資源利用率。

可變分區(qū)方式主存分配示例

操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)4KB10KB46KB52KB128KB操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)4KB10KB40KB46KB52KB128KB作業(yè)3操作系統(tǒng)作業(yè)1空閑區(qū)4KB10KB40KB128KB作業(yè)3可變分區(qū)存儲管理數(shù)據(jù)結(jié)構(gòu)可變分區(qū)主存分配表可由兩張表格組成：一張稱“已分配區(qū)表”另一張是“未分配區(qū)表”可變分區(qū)的回收算法(1)當(dāng)一個(gè)進(jìn)程X撤離時(shí)，可分成四種情況：(1)其鄰近都有進(jìn)程（A和B），(2)一邊有進(jìn)程（A或B），(3)兩邊均為空閑區(qū)（黑色區(qū)域）。

可變分區(qū)的回收算法(2)

A

X

B

A

B

A

X

A

X

B

B

x

變?yōu)樽優(yōu)樽優(yōu)樽優(yōu)閄終止前X終止后鏈表空閑區(qū)管理方法每個(gè)內(nèi)存空閑區(qū)的開頭單元存放本空閑區(qū)長度及下一個(gè)空閑區(qū)起始地址,所有空閑區(qū)都鏈接起來,系統(tǒng)設(shè)置第一塊空閑區(qū)地址指針,讓它指向第一塊空閑區(qū)地址。申請空閑區(qū);歸還空閑區(qū)?？勺兎謪^(qū)管理的分配算法1）最先適應(yīng)分配算法

2）下次適應(yīng)分配算法3)最優(yōu)適應(yīng)分配算法

4）最壞適應(yīng)分配算法5)快速適應(yīng)分配算法

查找和分配算法比較(1)從搜索空閑區(qū)速度及主存利用率來看,最先適用分配、下次適應(yīng)分配和最佳適應(yīng)算法比最壞適應(yīng)算法性能好。如果空閑區(qū)按從小到大排列,則最先適用分配算法等于最優(yōu)適應(yīng)分配算法。如果空閑區(qū)按從大到小排列,則最先適用分配算法等于最壞適應(yīng)分配算法。查找和分配算法比較(2)空閑區(qū)按從小到大排列時(shí),最先適用分配算法能盡可能使用低地址區(qū),從而高地址空間有較大的空閑區(qū)容納大的作業(yè)。下次適應(yīng)分配算法會(huì)使存儲器空間得到均衡使用。最優(yōu)適應(yīng)分配算法的主存利用率最好,但可能會(huì)導(dǎo)致空閑區(qū)分割下來的部分很小。查找和分配算法比較(3)處理某種作業(yè)序列時(shí),最壞適應(yīng)分配算法可能性能最佳,它選擇最大空閑區(qū),使得分配后剩余下來的空閑區(qū)不會(huì)太小,仍能用于再分配。最先適應(yīng)算法簡單、快速，在實(shí)際的操作系統(tǒng)中用得較多；其次是最佳適應(yīng)算法和下次適應(yīng)算法?？勺兎謪^(qū)地址轉(zhuǎn)換與存儲保護(hù)

基址基址寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)空閑分區(qū)1用戶作業(yè)1空閑分區(qū)2限長限長寄存器<限長越界中斷多對基址/限長寄存器允許一個(gè)進(jìn)程占用兩個(gè)或多個(gè)分區(qū)。規(guī)定某對基址/限長寄存器的區(qū)域是共享的，用來存放共享的程序和常數(shù)，對共享區(qū)域的信息只能讀出不能寫入。進(jìn)程共享的例行程序就可放在限定的公用區(qū)域中,而讓進(jìn)程的共享部分具有相同的基址/限長值。進(jìn)程B虛CPU進(jìn)程A虛CPU物理主存進(jìn)程A私有空間進(jìn)程B私有空間共享區(qū)重定位寄存器1限長寄存器1重定位寄存器2限長寄存器2重定位寄存器1限長寄存器1重定位寄存器2限長寄存器2

多對重定位寄存器支持主存共享4.2.3伙伴系統(tǒng)

兩個(gè)伙伴的大小必須相同，物理地址必須連續(xù)?；驹恚篜241伙伴通過對大塊的物理主存劃分而獲得假如從第0個(gè)頁面開始到第3個(gè)頁面結(jié)束的主存每次都對半劃分，那么第一次劃分獲得大小為2頁的伙伴，如0、1和2、3進(jìn)一步劃分，可以獲得大小為1頁的伙伴，例如0和1，2和301230123伙伴原理伙伴系統(tǒng)原理下面通過一個(gè)例子說明伙伴系統(tǒng)的工作過程。內(nèi)存管理模塊保持有一個(gè)空閑塊鏈表，空閑塊的大小可以為1，2，4，8，…，2n字節(jié)，其中n為計(jì)算機(jī)的有效地址位。例如，對于1M的內(nèi)存，空閑塊的大小可有20個(gè)不同的值，分別為2i個(gè)字節(jié)，其中1i20。初始時(shí)，整個(gè)存儲器是空閑的，鏈表只含有一個(gè)1M字節(jié)的空閑塊?；锇橄到y(tǒng)原理

128k256k384k512k640k768k896k1M

A

128

256512

AB64

256

512

AB64

C

128

512

128B64

C

128

512

128BD

C

128

512

12864D

C

128

512

256

C

128

512

1024伙伴系統(tǒng)原理優(yōu)點(diǎn)：當(dāng)一個(gè)大小為2k個(gè)字節(jié)的塊釋放時(shí)，存儲器管理模塊只需搜索大小為2k字節(jié)的塊，看其是否可以合并，而其它算法則必須搜索所有的空閑塊。因此，伙伴系統(tǒng)速度快。但存儲器利用角度來說，伙伴系統(tǒng)性能很差，其原因是進(jìn)程的大小不一定是2的整數(shù)倍，由此會(huì)造成浪費(fèi)。例如，35K的進(jìn)程要分配64K的內(nèi)存給它，29K的內(nèi)存便浪費(fèi)掉了。這種存儲段內(nèi)的碎片稱之為內(nèi)部碎片，而存儲段間的碎片稱之為外部碎片。4.2.4主存不足的存儲管理技術(shù)

操作系統(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è)4移動(dòng)技術(shù)有關(guān)移動(dòng)問題討論移動(dòng)條件移動(dòng)時(shí)機(jī)移動(dòng)算法對換技術(shù)對換的作用對換進(jìn)程的選擇UNIX對換器Windows對換器覆蓋技術(shù)覆蓋的作用覆蓋的實(shí)現(xiàn)技術(shù)覆蓋技術(shù)的不足

4.3分頁式存儲管理內(nèi)容：分頁式存儲管理的基本原理 快表 分頁式存儲空間的分配和去配 分頁式存儲空間的頁面共享和保護(hù) 多級頁表 反置頁表4.3.1

分頁式存儲管理的基本原理分頁式存儲管理基本原理(1)?為什么要引進(jìn)分頁技術(shù)??基本原理(1)頁框(2)頁面(3)邏輯地址形式(4)頁表和地址轉(zhuǎn)換分頁式存儲管理基本原理(2)作業(yè)的頁面與分給的頁框如何建立聯(lián)系呢？邏輯地址(頁面)如何變換成物理地址(頁框)呢？作業(yè)的物理地址空間由連續(xù)變成分散后，如何保證程序正確執(zhí)行呢？分頁式存儲管理基本原理(3)

?動(dòng)態(tài)重定位技術(shù)，讓程序的指令執(zhí)行時(shí)動(dòng)態(tài)地進(jìn)行地址變換，給每個(gè)頁面設(shè)立重定位寄存器，重定位寄存器的集合便稱頁表（pagetable）。

?頁表：操作系統(tǒng)為每個(gè)用戶作業(yè)建立的，用來記錄程序頁面和主存對應(yīng)頁框的對照表。

?頁表控制寄存器：當(dāng)前運(yùn)行作業(yè)的頁表起址和頁表長。

?作業(yè)表：登記每個(gè)作業(yè)的頁表地址。分頁式存儲管理基本原理(4)

塊號1…。。。塊號2塊號第0頁…。。。第1頁頁號作業(yè)名BA頁表始址XXXXXX頁表長度XXXX作業(yè)表頁表…。。?！?。。…。。。

頁表和作業(yè)表的一般格式頁式存儲管理的地址轉(zhuǎn)換和存儲保護(hù)

物理地址邏輯地址01··pb···頁表CPUpdbd主存分頁存儲管理的地址轉(zhuǎn)換頁表基址寄存器4.3.2快表相聯(lián)存儲器和快表相聯(lián)存儲器快表的格式采用相聯(lián)存儲器后地址轉(zhuǎn)換采用相聯(lián)存儲器的地址轉(zhuǎn)換假定訪問主存時(shí)間為100毫微秒，訪問相聯(lián)存儲器時(shí)間為20毫微秒，相聯(lián)存儲器為32個(gè)單元時(shí)快表命中率可達(dá)90%，按邏輯地址存取的平均時(shí)間為：（100＋20）×90%＋(100+100)×(1-90%)＝128毫微秒比兩次訪問主存的時(shí)間200毫微秒下降近四成。4.3.3分頁式存儲空間

的分配和去配分頁式存儲空間的分配和去配位示圖法鏈表方法分配算法主存分配的位示圖和鏈表方法4.3.4分頁存儲空間的

頁面共享和保護(hù)分頁存儲管理能實(shí)現(xiàn)多作業(yè)共享程序和數(shù)據(jù)(1)數(shù)據(jù)共享程序共享分頁存儲管理能實(shí)現(xiàn)多作業(yè)共享程序和數(shù)據(jù)(2)共享信息的保護(hù)問題標(biāo)志位保護(hù)方法鍵保護(hù)方法4.3.5多級頁表多級頁表多級頁表的概念多級頁表的具體做法邏輯地址結(jié)構(gòu)邏輯地址到物理地址轉(zhuǎn)換過程多級頁表的概念(1)

頁表存儲開銷太大書P252多級頁表的概念(2)多級頁表概念：頁表和頁面一樣也進(jìn)行分頁，內(nèi)存僅存放當(dāng)前使用的頁表,暫時(shí)不用部分放在磁盤上,待用到時(shí)再行調(diào)進(jìn)。具體做法：把整個(gè)頁表進(jìn)行分頁,分成一張張小頁表(稱為頁表頁),小頁表的大小與頁框相同，為進(jìn)行索引查找,應(yīng)該為這些小頁表建一張頁目錄表,其表項(xiàng)指出小頁表所在頁框號及相關(guān)信息。

多級頁表的概念(3)系統(tǒng)為每個(gè)進(jìn)程建一張頁目錄表,它的每個(gè)表項(xiàng)對應(yīng)一個(gè)頁表頁,而頁表頁的每個(gè)表項(xiàng)給出了頁面和頁框的對應(yīng)關(guān)系。頁目錄表是一級頁表,頁表頁是二級頁表。邏輯地址結(jié)構(gòu)有三部分組成：頁目錄、頁表頁和位移。多級頁表地址轉(zhuǎn)換過程(1)頁目錄表控制寄存器指出當(dāng)前運(yùn)行進(jìn)程的頁目錄表內(nèi)存所在地址,由頁目錄表起址加上“頁目錄位移(dir)”作索引,可找到某個(gè)頁表頁在內(nèi)存頁框的地址,以“頁表頁位移(page)”作索引,找到頁表頁的頁表項(xiàng),而該表項(xiàng)中包含了頁面對應(yīng)的頁框號,頁框號和”頁內(nèi)位移(offset)”便可生成物理地址。多級頁表地址轉(zhuǎn)換過程(2)

B

offset

dirpageoffsetBF進(jìn)程一級頁表進(jìn)程二級頁表物理地址邏輯地址頁目錄表控制寄存器解決頁表頁占用內(nèi)存空間的問題進(jìn)程運(yùn)行涉及頁面的頁表頁應(yīng)放在主存,其他頁表頁使用時(shí)再調(diào)入,在頁目錄表中增加特征位,指示對應(yīng)的頁表頁是否已調(diào)入內(nèi)存,地址轉(zhuǎn)換機(jī)構(gòu)根據(jù)邏輯地址中的dir,去查頁目錄表對應(yīng)表項(xiàng),如未調(diào)入,應(yīng)產(chǎn)生一個(gè)”缺頁表頁”中斷信號，請求操作系統(tǒng)將頁表頁調(diào)入主存。多級頁表結(jié)構(gòu)的本質(zhì)多級不連續(xù)導(dǎo)致多級索引。以二級頁表為例，用戶程序的頁面不連續(xù)存放，要有頁面地址索引，該索引是進(jìn)程頁表；進(jìn)程頁表又是不連續(xù)存放的多個(gè)頁表頁，故頁表頁也要頁表頁地址索引，該索引就是頁目錄。頁目錄項(xiàng)是頁表頁的索引，而頁表頁項(xiàng)是進(jìn)程程序的頁面索引。4.3.6反置頁表反置頁表(1)IPT是為內(nèi)存中的每一個(gè)物理塊建立一個(gè)頁表并按照塊號排序,該表每個(gè)表項(xiàng)包含正在訪問該頁框的進(jìn)程標(biāo)識、頁號及特征位,用來完成主存頁框到訪問進(jìn)程的頁號、即物理地址到邏輯地址的轉(zhuǎn)換。反置頁表(2)

頁框號位移進(jìn)程標(biāo)識頁號位移進(jìn)程標(biāo)識頁號特征位鏈指針序號反置頁表物理地址邏輯地址··哈希函數(shù)哈希表反置頁表及其地址轉(zhuǎn)換反置頁表(3)反置頁表地址轉(zhuǎn)換過程如下:邏輯地址給出進(jìn)程標(biāo)識和頁號,用它們?nèi)ケ容^IPT,若整個(gè)反置頁表中未能找到匹配的頁表項(xiàng),說明該頁不在主存,產(chǎn)生請頁中斷,請求操作系統(tǒng)調(diào)入;否則，該表項(xiàng)的序號便是頁框號,塊號加上位移,便形成物理地址。4.4分段式存儲管理內(nèi)容：程序的分段結(jié)構(gòu) 分段式存儲管理的基本原理 段的共享和保護(hù) 分段和分頁的比較4.4.1程序的分段結(jié)構(gòu)程序的分段結(jié)構(gòu)分段存儲管理引入的主要原因模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)分頁存儲管理——一維地址結(jié)構(gòu)分段存儲管理——二維地址結(jié)構(gòu)模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)

子程序段X數(shù)組段A┇call[X]∣<E>(調(diào)用X段的入口E)┇call[Y]∣<F>(調(diào)用Y段的入口F)┇load1,[A]∣<G>(調(diào)用數(shù)組段A[G])┇主程序段E：┅┅┅┅┅┅F：┅┅┅┅┅┅子程序段YG：┅┅┅┅┅┅工作區(qū)段4.4.2分段式存儲管理的基本原理分段式存儲管理的基本原理(1)

?兩維邏輯地址段號：段內(nèi)地址

?作業(yè)表和段表

?段式存儲管理的地址轉(zhuǎn)換和存儲保護(hù)分段式存儲管理的基本原理(2)

XXX…XXX始址第0段第1段段號作業(yè)名BA段表始址XXXXXX表段長度XXXX作業(yè)表段表………XXX…XXX長度第2段分段式存儲管理的基本原理(3)

段控制寄存器

段表始址段表長度

段號s位移d

段長基址物理地址越界?段表4.4.3段的共享段的共享多對基址/限長寄存器段的共享，是通過不同作業(yè)段表中的項(xiàng)指向同一個(gè)段基址來實(shí)現(xiàn)。幾道作業(yè)共享的例行程序就可放在一個(gè)段中，只要讓各道作業(yè)的共享部分有相同的基址/限長值。對共享段的信息必須進(jìn)行保護(hù)。4.4.4分段和分頁的比較分段和分頁的比較(1)分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶可見，段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何主存地址開始。分段方式中，源程序(段號，段內(nèi)位移)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。分段和分頁的比較(2)分頁是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無關(guān)，用戶不可見，頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始。分頁方式中，源程序(頁號，頁內(nèi)位移)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)。4.5虛擬存儲管理內(nèi)容：虛擬存儲管理的概念 請求分頁虛擬存儲管理 請求分段虛擬存儲管理 請求段頁式虛擬存儲管理4.5.1虛擬存儲器的概念虛擬存儲管理的概念(1)為什么要引入虛擬存儲器?虛擬存儲器的基本思路。“部分裝入、部分對換”。虛擬存儲管理的概念(2)虛擬存儲器的定義：在具有層次結(jié)構(gòu)存儲器的計(jì)算機(jī)系統(tǒng)中，采用自動(dòng)實(shí)現(xiàn)部分裝入和部分對換功能，為用戶提供一個(gè)比物理主存容量大得多的，可尋址的一種“主存儲器”。虛擬存儲管理的概念(3)虛擬存儲器是為擴(kuò)大主存而采用的一種設(shè)計(jì)技巧，它的容量與主存大小無直接關(guān)系，而受限于計(jì)算機(jī)的地址結(jié)構(gòu)及可用的輔助存儲器的容量。

虛擬存儲器的概念圖邏輯地址空間處理器虛地址存儲管理部件實(shí)地址主存輔存物理地址空間虛擬存儲管理的概念(4)作業(yè)信息不全部裝入主存，能否保證作業(yè)的正確運(yùn)行？回答是肯定的,1968年P(guān).Denning研究了程序執(zhí)行時(shí)的局部性原理。程序的局部性原理程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。又可細(xì)分時(shí)間局部性和空間局部性。程序的局部性原理（續(xù)）第一，程序中只有少量分支和過程調(diào)用，大都是順序執(zhí)行的指令。第二，程序包含若干循環(huán)，是由相對較少的指令組成，在循環(huán)過程中，計(jì)算被限制在程序中很小的相鄰部分中。程序的局部性原理（續(xù)）第三，很少出現(xiàn)連續(xù)的過程調(diào)用，相反，程序中過程調(diào)用的深度限制在小范圍內(nèi)，一段時(shí)間內(nèi)，指令引用被局限在很少幾個(gè)過程中。第四，對于連續(xù)訪問數(shù)組之類的數(shù)據(jù)結(jié)構(gòu)，往往是對存儲區(qū)域中相鄰位置的數(shù)據(jù)的操作。第五，程序中有些部分是彼此互斥的，不是每次運(yùn)行時(shí)都用到的，如出錯(cuò)處理程序。實(shí)現(xiàn)虛擬存儲器必須解決的問題

?主存輔存統(tǒng)一管理問題、

?邏輯地址到物理地址的轉(zhuǎn)換問題、

?部分裝入和部分對換問題。虛擬存儲管理實(shí)現(xiàn)技術(shù)

?請求分頁虛擬存儲管理

?請求分段虛擬存儲管理

?請求段頁式虛擬存儲管理4.5.2請求分頁虛擬存儲管理分頁式虛擬存儲系統(tǒng)分頁式虛擬存儲系統(tǒng)的硬件支撐(1)

主存管理單元MMU完成邏輯地址到物理地址的轉(zhuǎn)換功能，它接受虛擬地址作為輸入，物理地址作為輸出，直接送到總線上，對內(nèi)存單元進(jìn)行尋址。分頁式虛擬存儲系統(tǒng)的硬件支撐(2)

CPUMMU內(nèi)存CPU把邏輯地址送至MMUMMU把物理地址送至主存

MMU的位置、功能和16個(gè)4KB頁面情況下MMU的內(nèi)部操作CPU送入的邏輯地址(8196)0010000000000100

110000000000100MMU送出的物理地址00101100112110130001410015011160000700008101190000…頁號頁框號在主存否MMU主要功能(1)管理硬件頁表基址寄存器。(2)分解邏輯地址。(3)管理快表TLB。(4)訪問頁表。(5)發(fā)出缺頁中斷或越界中斷，并將控制權(quán)交給內(nèi)核存儲管理處理。(6)設(shè)置和檢查頁表中各個(gè)特征位。請求分頁虛擬存儲系統(tǒng)的基本原理(1)分頁式虛擬存儲系統(tǒng)是將作業(yè)信息的副本存放在磁盤中，當(dāng)作業(yè)被調(diào)度投入運(yùn)行時(shí)，不把作業(yè)的程序和數(shù)據(jù)全部裝入主存，而僅裝入立即使用的頁面，在執(zhí)行過程中訪問到不在主存的頁面時(shí)，產(chǎn)生缺頁中斷，再把它們動(dòng)態(tài)地裝入。

請求分頁虛擬存儲系統(tǒng)的基本原理(2)怎樣才能發(fā)現(xiàn)頁面不在內(nèi)存中呢?怎樣處理這種情況呢?采用的辦法是：擴(kuò)充頁表的內(nèi)容,增加駐留標(biāo)志位和頁面輔存的地址等信息。

頁式虛擬存儲管理頁表擴(kuò)展(1)頁號駐留標(biāo)志

頁框號

輔存地址其它標(biāo)志

頁式虛擬存儲管理頁表擴(kuò)展(2)駐留標(biāo)志位(又稱中斷位)修改位（Modified）引用位（Renferenced）請求分頁虛存地址轉(zhuǎn)換過程邏輯空間地址主存(用戶區(qū))CPU邏輯地址快表主存(系統(tǒng)區(qū))運(yùn)行進(jìn)程頁表輔存缺頁中斷處理①分解地址③⑤訪問MMU②查快表③命中④不命中⑤頁表命中⑦發(fā)缺頁中斷⑧調(diào)頁⑨裝入、改表④查頁表運(yùn)行進(jìn)程頁表基址⑥裝入快表運(yùn)行進(jìn)程映象進(jìn)程切換時(shí)裝入物理地址頁框

頁內(nèi)地址頁號頁內(nèi)地址查快表有登記無登記查頁表登記入快表發(fā)缺頁中斷在主存在輔存形成絕對地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場調(diào)整頁表和主存分配表裝入所需頁面主存有空閑塊保護(hù)現(xiàn)場有選擇調(diào)出頁面該頁是否修改未修改已修改把該頁寫回輔存相應(yīng)位置操作系統(tǒng)硬件邏輯地址無請求頁式虛擬存儲系統(tǒng)的優(yōu)缺點(diǎn)

?優(yōu)點(diǎn)：作業(yè)的程序和數(shù)據(jù)可按頁分散存放在內(nèi)存中，減少移動(dòng)開銷，有效解決了碎片問題；既有利于改進(jìn)主存利用率，又有利于多道程序運(yùn)行。

?缺點(diǎn)：要有硬件支持，要進(jìn)行缺頁中斷處理，機(jī)器成本增加，系統(tǒng)開銷加大。頁面裝入策略和清除策略

頁面裝入策略決定何時(shí)把頁面裝入主存，有兩種策略：

?請頁式調(diào)度

?預(yù)調(diào)式調(diào)度頁面裝入策略—請頁式調(diào)度需要訪問程序和數(shù)據(jù)時(shí)，才把所在頁面裝入主存。根據(jù)局部性原理,一段時(shí)間后,缺頁中斷會(huì)下降到很低水平,程序進(jìn)入相對平穩(wěn)階段。缺點(diǎn)是處理缺頁中斷和調(diào)頁的系統(tǒng)開銷較大，每次僅調(diào)一頁,增加了磁盤I/O次數(shù)。頁面裝入策略—預(yù)調(diào)式調(diào)度系統(tǒng)預(yù)測進(jìn)程將要使用的頁面,使用前預(yù)先調(diào)入主存,每次調(diào)入若干頁面,而不是僅調(diào)一頁。一次調(diào)入多頁能減少磁盤I/O啟動(dòng)次數(shù),節(jié)省尋道和搜索時(shí)間。如果調(diào)入的一批頁面中多數(shù)未被使用,則效率就很低了，可見預(yù)調(diào)頁要建立在預(yù)測的基礎(chǔ)上。頁面清除策略考慮何時(shí)把一個(gè)修改過的頁面寫回輔存儲器：請頁式清除和預(yù)約式清除。請頁式清除：僅當(dāng)一頁選中被替換,且之前它又被修改過，才把這個(gè)頁面寫回輔存。預(yù)約式清除：對所有更改過的頁面，在需要之前就把它們都寫回輔存，可成批進(jìn)行。頁面清除策略的缺點(diǎn)預(yù)約式清除：寫出頁仍在內(nèi)存中,直到頁替換算法選中一頁從內(nèi)存中移出。成批地把頁面寫出，但如若剛寫出了很多頁面，在被替換前，其中大部分又被更改，預(yù)清除就毫無意義。請頁式清除：寫出一頁是在讀進(jìn)新頁前進(jìn)行的，要成雙操作,引起進(jìn)程等待兩次I/O操作，會(huì)降低CPU使用效率。頁面清除策略—頁緩沖策略策略如下：僅清除淘汰的頁面，并使清除操作和替換操作不必成雙進(jìn)行。在頁緩沖中，淘汰了的頁面進(jìn)入兩個(gè)隊(duì)列：修改頁面和非修改頁面隊(duì)列。修改頁面隊(duì)列中的頁不時(shí)地成批寫出并加入到非修改頁面隊(duì)列;非修改頁面隊(duì)列中的頁面，當(dāng)它被再次引用時(shí)回收，或者淘汰掉以作替換。頁面分配策略：考慮因素系統(tǒng)為進(jìn)程分配主存,需考慮因素:①分給進(jìn)程的空間越小,同一時(shí)間處于內(nèi)存的進(jìn)程就越多，至少有一個(gè)進(jìn)程處于就緒態(tài)的可能性就越大②如果進(jìn)程只有小部分在主存里,即使局部性很好,缺頁中斷率還會(huì)相當(dāng)高③因程序的局部性原理，分給進(jìn)程的內(nèi)存超過一定限度后，再增加內(nèi)存空間,不會(huì)明顯降低進(jìn)程的缺頁中斷率。頁面分配策略：固定分配進(jìn)程保持頁框數(shù)固定不變，稱固定分配;進(jìn)程創(chuàng)建時(shí)，根據(jù)進(jìn)程類型和程序員的要求決定頁框數(shù),只要有一個(gè)缺頁中斷產(chǎn)生,進(jìn)程就會(huì)有一頁被替換。頁面分配策略：可變分配進(jìn)程分得的頁框數(shù)可變,稱可變分配;進(jìn)程執(zhí)行的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進(jìn)程目前的局部性較好，可減少分給進(jìn)程的頁框數(shù)。頁面分配策略：分析固定分配缺少靈活性，而可變分配的性能會(huì)更好些，被許多操作系統(tǒng)采用。采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視活動(dòng)進(jìn)程的行為和進(jìn)程缺頁中斷率的情況,會(huì)增加系統(tǒng)的開銷。

頁面替換策略：局部替換和全局替換如果頁面替換算法的作用范圍是整個(gè)系統(tǒng)，稱全局頁面替換算法，它可以在運(yùn)行進(jìn)程間動(dòng)態(tài)地分配頁框。如果頁面替換算法的作用范圍局限于本進(jìn)程，稱為局部頁面替換算法，它實(shí)際上需要為每個(gè)進(jìn)程分配固定的頁框。 固定分配和局部替換策略配合使用(1) 進(jìn)程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進(jìn)程的頁面中選頁替換，保證進(jìn)程的頁框總數(shù)不變。策略難點(diǎn)：應(yīng)給每個(gè)進(jìn)程分配多少頁框?給少了,缺頁中斷率高；給多了,使內(nèi)存中能同時(shí)執(zhí)行的進(jìn)程數(shù)減少，進(jìn)而造成處理器和其它設(shè)備空閑。固定分配和局部替換策略配合使用(2)采用固定分配算法，系統(tǒng)把頁框分配給進(jìn)程，可采用的方式：①平均分配，②按比例分配,③優(yōu)先權(quán)分配,。可變分配和全局替換策略配合使用

?先為每個(gè)進(jìn)程分配一定數(shù)目頁框，OS保留若干空閑頁框，進(jìn)程發(fā)生缺頁中斷時(shí)，從系統(tǒng)空閑頁框中選一個(gè)給進(jìn)程。這樣產(chǎn)生缺頁中斷進(jìn)程的內(nèi)存空間會(huì)逐漸增大，有助于減少系統(tǒng)的缺頁中斷次數(shù)。

?系統(tǒng)擁有的空閑頁框耗盡時(shí)，會(huì)從內(nèi)存中選擇一頁淘汰，該頁可以是內(nèi)存中任一進(jìn)程的頁面，這樣又會(huì)使那個(gè)進(jìn)程的頁框數(shù)減少，缺頁中斷率上升。

?難點(diǎn)：P.263可變分配和局部替換配合使用其實(shí)現(xiàn)要點(diǎn)如下:(1)新進(jìn)程裝入主存時(shí)，根據(jù)應(yīng)用類型、程序要求，分配給一定數(shù)目頁框，可用請頁式或預(yù)調(diào)式完成這個(gè)分配。(2)產(chǎn)生缺頁中斷時(shí),從該進(jìn)程駐留集中選一個(gè)頁面替換。(3)不時(shí)重新評價(jià)進(jìn)程的分配，增加或減少分配給進(jìn)程的頁框以改善系統(tǒng)性能。頁面替換策略（重點(diǎn)）

?頁面替換

?頁面淘汰算法

?“抖動(dòng)”(Thrashing)現(xiàn)象

影響缺頁中斷率的因素(1)

假定作業(yè)p共計(jì)n頁，系統(tǒng)分配給它的主存塊只有m塊（１≤m≤n）。如果作業(yè)p在運(yùn)行中成功的訪問次數(shù)為s，不成功的訪問次數(shù)為F，則總的訪問次數(shù)Ａ為：A=S+F

又定義：f=F/A

稱f為缺頁中斷率。影響缺頁中斷率的因素(2)

影響缺頁中斷率f的因素有：

(1)主存頁框數(shù)。

(2)頁面大小。

(3)頁面替換算法。

(4)程序特性。全局頁面替換策略1)最佳頁面替換算法OPT2)先進(jìn)先出頁面替換算法FIFO3)最近最少用頁面替換算法LRU4)第二次機(jī)會(huì)頁面替換算法SCR5)時(shí)鐘頁面替換算法Clock

1）最佳替換算法(一個(gè)理論算法)調(diào)入一頁而必須淘汰一個(gè)舊頁時(shí)，所淘汰的頁應(yīng)該是以后不再訪問的頁或距現(xiàn)在最長時(shí)間后再訪問的頁。Belady算法（Optimal），可用來作為衡量各種具體算法的標(biāo)準(zhǔn)。2)先進(jìn)先出頁面替換算法（FIFO)基于程序總是按線性順序來訪問物理空間這一假設(shè)。算法總是淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時(shí)間最長的那一頁（常駐的除外）。FIFO實(shí)現(xiàn)技術(shù)系統(tǒng)中設(shè)置一張具有m個(gè)元素的頁號表，它是Ｍ個(gè)數(shù)：P[0],P[1],…,P[m-1]

組成的數(shù)組，每個(gè)P[i](i=0,1,…m-1)存儲一個(gè)在主存中的頁面的頁號。用指針k指示當(dāng)前調(diào)入新頁時(shí)應(yīng)淘汰的那一頁在頁號表中的位置。每當(dāng)調(diào)入一個(gè)新頁后，執(zhí)行P[k]:=新頁的頁號;k:=（k+1）modm;FIFO另一個(gè)實(shí)現(xiàn)算法引入指針鏈成隊(duì)列，只要把進(jìn)入主存的頁面按時(shí)間的先后次序鏈接,新進(jìn)入的頁面從隊(duì)尾入隊(duì),淘汰總是從隊(duì)列頭進(jìn)行。3）最近最少用頁面替換算法LRU算法淘汰的頁面是在最近一段時(shí)間里較久未被訪問的那頁。根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時(shí)間里未被使用的頁面，可能不會(huì)馬上使用到。LRU算法實(shí)現(xiàn)：頁面淘汰隊(duì)列(1)隊(duì)列中存放當(dāng)前在主存中的頁號，每當(dāng)訪問一頁時(shí)就調(diào)整一次，使隊(duì)列尾總指向最近訪問的頁，隊(duì)列頭就是最近最少用的頁。發(fā)生缺頁中斷時(shí)總淘汰隊(duì)列頭所指示的頁；執(zhí)行一次頁面訪問后，需要從隊(duì)列中把該頁調(diào)整到隊(duì)列尾。LRU算法實(shí)現(xiàn)：頁面淘汰隊(duì)列(2)例：給某作業(yè)分配了三塊主存，該作業(yè)依次訪問的頁號為：4，3，0，4，1，1，2，3，2。當(dāng)訪問這些頁時(shí)，頁面淘汰序列變化情況如下LRU算法實(shí)現(xiàn)：頁面淘汰隊(duì)列(3)訪問頁號頁面淘汰序列被淘汰頁面

443430430430410413104124120312342132LRU算法實(shí)現(xiàn)：標(biāo)志位法每頁設(shè)置一個(gè)引用標(biāo)志位R，訪問某頁時(shí)，由硬件將頁標(biāo)志位R置1，隔一定時(shí)間t將所有頁的標(biāo)志R均清0。發(fā)生缺頁中斷時(shí)，從標(biāo)志位R為0的頁中挑選一頁淘汰。挑選到要淘汰的頁后，也將所有頁的標(biāo)志位R清0。LRU算法實(shí)現(xiàn)：多位計(jì)數(shù)器法每個(gè)頁面設(shè)置一個(gè)多位計(jì)數(shù)器，又叫最不常用頁面替換算法LFU。每當(dāng)訪問一頁時(shí)，就使它對應(yīng)的計(jì)數(shù)器加１。當(dāng)發(fā)生缺頁中斷時(shí)，可選擇計(jì)數(shù)值最小的對應(yīng)頁面淘汰，并將所有計(jì)數(shù)器全部清０。

LRU算法實(shí)現(xiàn)：多位計(jì)時(shí)器法為每個(gè)頁面設(shè)置一個(gè)多位計(jì)時(shí)器，每當(dāng)頁面被訪問時(shí)，系統(tǒng)的絕對時(shí)間記入計(jì)時(shí)器。比較各頁面的計(jì)時(shí)器的值，選最小值的未使用的頁面淘汰，因?yàn)椋亲睢袄稀钡奈词褂玫捻撁妗?)第二次機(jī)會(huì)頁面替換算法(1)

改進(jìn)FIFO算法,把FIFO與頁表中的”引用位”結(jié)合起來使用：檢查FIFO中的隊(duì)首頁面(最早進(jìn)入主存的頁面),如果它的”引用位”是0,這個(gè)頁面既老又沒有用，選擇該頁面淘汰;如果”引用位”是1,說明它進(jìn)入主存較早，但最近仍在使用。把它的”引用位”清0,并把這個(gè)頁面移到隊(duì)尾，把它看作是一個(gè)新調(diào)入的頁。第二次機(jī)會(huì)頁面替換算法(2)算法含義：最先進(jìn)入主存的頁面，如果最近還在被使用的話,仍然有機(jī)會(huì)作為像一個(gè)新調(diào)入頁面一樣留在主存中。5)時(shí)鐘頁面替換算法

(ClockPolicy)(1)算法實(shí)現(xiàn)要點(diǎn)(1)：一個(gè)頁面首次裝入主存，其“引用位”置1。主存中的任何頁面被訪問時(shí),”引用位”置1。淘汰頁面時(shí),從指針當(dāng)前指向的頁面開始掃描循環(huán)隊(duì)列，把遇到的”引用位”是1的頁面的”引用位”清0，跳過這個(gè)頁面;把所遇到的”引用位”是0的頁面淘汰掉，指針推進(jìn)一步。時(shí)鐘頁面替換算法

(ClockPolicy)(2)算法實(shí)現(xiàn)要點(diǎn)(2)：掃描循環(huán)隊(duì)列時(shí)，如果遇到的所有頁面的”引用位”為1，指針就會(huì)繞整個(gè)循環(huán)隊(duì)列一圈，把碰到的所有頁面的”引用位”清0；指針停在起始位置，并淘汰掉這一頁，然后，指針推進(jìn)一步。時(shí)鐘頁面替換算法的一個(gè)例子

Page9use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一個(gè)幀指針n012345678一個(gè)頁替換前的緩沖區(qū)狀態(tài)Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=1Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0n012345678下一頁替換后的緩沖區(qū)狀態(tài)第1頁框時(shí)鐘頁面替換改進(jìn)算法(1)把”引用位”和”修改位”結(jié)合起來使用，共組合成四種情況：(1)最近沒有被引用,沒有被修改(r=0,m=0)(2)最近被引用,沒有被修改(r=1,m=0)(3)最近沒有被引用,但被修改(r=0,m=1)(4)最近被引用過,也被修改過(r=1,m=1)時(shí)鐘頁面替換改進(jìn)算法(2)

步1：選擇最佳淘汰頁面，從指針當(dāng)前位置開始,掃描循環(huán)隊(duì)列。掃描過程中不改變”引用位”，把遇到的第一個(gè)r=0,m=0的頁面作為淘汰頁面。步2：如果步1失敗，再次從原位置開始，查找r=0且m=1的頁面，把遇到的第一個(gè)這樣的頁面作為淘汰頁面，而在掃描過程中把指針?biāo)鶔哌^的頁面的”引用位”r置0。時(shí)鐘頁面替換改進(jìn)算法(3)

步3：如果步2失敗，指針再次回到了起始位置，由于此時(shí)所有頁面的”引用位”r均己為0，再轉(zhuǎn)向步1操作，必要時(shí)再做步2操作，這次一定可以挑出一個(gè)可淘汰的頁面。例子：計(jì)算缺頁中斷次數(shù)和被淘汰頁面(1)假設(shè)采用固定分配策略，進(jìn)程分得三個(gè)頁框,執(zhí)行中按下列次序引用5個(gè)獨(dú)立的頁面:232152453252。例子：計(jì)算缺頁中斷次數(shù)和被淘汰頁面(2)232152453252tailhead232152453252例子：計(jì)算缺頁中斷次數(shù)和被淘汰頁面(3)

C

O

K

F(2)

F

F

F(2)

F(3)

F(1)

F(5)

F(2)

F(4)

2

2

2

2

3

1

5

5

2

2

4

3

3

3

3

1

5

2

2

4

4

3

5

I

O

1

5

2

4

4

3

3

5

2

F(3)

F(1)

F(5)

F(4)

2*

2*

2*

2*

5*

5*

5*

5*

3*

3*

3*

3*

→

3*

3*

3*

3

2*

2*

2*

2

2*

2

2*

L

→

C

→

→

1*

→

1

→

1

→

4*

→

4*

→

4

→

4

→

5*

→

5*

232152453252232152453252例子：計(jì)算缺頁中斷次數(shù)和被淘汰頁面(4)

性能比較

OPTF(1)F(2)F(4)+3次LRUF(3)F(1)F(2)F(4)+3次CLOCKF(2)F(3)F(1)F(5)F(4)+3次FIFOF(1)F(3)F(1)F(5)F(2)F(4)+3次局部頁面替換算法1)局部最佳頁面替換算法

2)工作集模型和工作集置換算法3)模擬工作集替換算法4)缺頁頻率替換算法1)局部最佳頁面替換算法實(shí)現(xiàn)思想：進(jìn)程在時(shí)刻t訪問某頁面，如果該頁面不在主存中，導(dǎo)致一次缺頁，把該頁面裝入一個(gè)空閑頁框。不論發(fā)生缺頁與否，算法在每一步要考慮引用串，如果該頁面在時(shí)間間隔(t,t+τ)內(nèi)未被再次引用，那么就移出頁面；否則，該頁被保留在進(jìn)程的駐留集中，直到再次被引用。

示例：P271圖4.232)工作集模型和工作集置換算法

進(jìn)程工作集指“在某一段時(shí)間間隔內(nèi)進(jìn)程運(yùn)行所需訪問的頁面集合”。實(shí)現(xiàn)思想：工作集模型用來對局部最佳頁面替換算法進(jìn)行模擬實(shí)現(xiàn)，不向前查看頁面引用串，而是基于程序局部性原理向后看，在任何給定時(shí)刻，一個(gè)進(jìn)程不久的將來所需主存頁框數(shù)，可通過考查其過去最近的時(shí)間內(nèi)的主存需求做出估計(jì)。示例：P272圖4.243)模擬工作集替換算法老化(Aging)算法例如，時(shí)間間隔T定為1000次存儲器引用，頁面P在時(shí)刻t+0時(shí)寄存器為“1000”，在時(shí)刻t+1000時(shí)寄存器為“0100”，在時(shí)刻t+2000時(shí)寄存器為“0010”，在時(shí)刻t+3000時(shí)寄存器為“0001”，在時(shí)刻t+4000時(shí)寄存器為“0000”，此時(shí)，頁面p被移出工作集，時(shí)間戳算法若t_off>t_max，把頁面從工作集中移出

4)缺頁頻率替換算法缺頁頻率替換算法根據(jù)連續(xù)的缺頁之間的時(shí)間間隔來對缺頁頻率進(jìn)行測量，每次缺頁時(shí)，利用測量時(shí)間調(diào)整進(jìn)程工作集尺寸。規(guī)則：如果本次缺頁與前次缺頁之間的時(shí)間超過臨界值τ，那么，所有在這個(gè)時(shí)間間隔內(nèi)沒有引用的頁面都被移出工作集。示例：P273圖4.25請求分頁虛擬存儲管理的幾個(gè)設(shè)計(jì)問題1)頁面大小

.從頁表大小考慮

.從主存利用率考慮

.從讀寫一個(gè)頁面所需時(shí)間考慮

.最佳頁面尺寸頁面

2)頁面交