操作系統(tǒng)章存儲器管理

2024/1/61操作系統(tǒng)第四章存儲器管理院(系):計算機科學與技術(shù)學院研究室:軟件支持技術(shù)教師:王紅濱2024/1/62內(nèi)存(MainMemory或PrimaryMemory或RealMemory)也稱主存,是指CPU能直接存取指令和數(shù)據(jù)的存儲器。圖內(nèi)存在計算機系統(tǒng)中的地位2024/1/63內(nèi)容概述4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念4.6請求分頁存儲管理方式4.7頁面置換算法4.8請求分段存儲管理方式

存儲器是計算機系統(tǒng)重要的組成部分,雖然存儲器的容量不斷擴大,但仍不能滿足要求,因此存儲器管理是操作系統(tǒng)的重要工作,存儲器管理的主要內(nèi)容是內(nèi)存。存儲器是用來存放系統(tǒng)和用戶的程序和數(shù)據(jù),其特點是存取速度快,存儲方式是以新?lián)Q舊,斷電信息丟失。2024/1/644.1程序的裝入和鏈接4.1.1程序的裝入4.1.2程序的鏈接2024/1/654.1程序的裝入和鏈接圖4-2對用戶程序的處理步驟多道程序環(huán)境下,程序要運行必須為之創(chuàng)建進程,而創(chuàng)建進程的第一件事就是分配內(nèi)存源程序要運行通常經(jīng)過編譯(compile)

鏈接(link)

裝入(load)等幾個步驟2024/1/66(1)編譯。 由編譯程序?qū)⒂脩粼创a編譯成若干個目標模塊。(2)鏈接。由鏈接程序?qū)⒕幾g后形成的目標模塊以及它們所需要的庫函數(shù),鏈接在一起,形成一個裝入模塊。(3)裝入。由裝入程序?qū)⒀b入模塊裝入主存的過程。2024/1/674.1.1程序的裝入1.絕對裝入方式2.可重定位裝入方式3.動態(tài)運行時裝入方式2024/1/681.絕對裝入方式(AbsoluteLoadingMode)(適合“單道”)在編譯時,如果知道程序?qū)Ⅰv留在內(nèi)存的什么位置,則編譯程序產(chǎn)生絕對地址的目標代碼裝入模塊被裝入內(nèi)存后,由于程序中的邏輯地址與實際內(nèi)存地址完全相同,故不需對程序和數(shù)據(jù)的地址進行修改程序中所使用的絕對地址,既可在編譯或匯編時給出,也可由程序員直接賦予。但在由程序員直接給出絕對地址時,不僅要求程序員熟悉內(nèi)存的使用情況,而且一旦程序或數(shù)據(jù)被修改后,可能要改變程序中的所有地址。因此,通常是寧可在程序中采用符號地址,然后在編譯或匯編時,再將這些符號地址轉(zhuǎn)換為絕對地址。2024/1/692024/1/6102.可重定位裝入方式(RelocationLoadingMode)(可用于“多道”)絕對裝入方式只能將目標模塊裝入到內(nèi)存中事先指定的位置在多道程序環(huán)境下,不可能預知目標模塊放在內(nèi)存中的地址,因此絕對裝入方式不適合在多道環(huán)境下使用程序中目標模塊的地址通常從0開始,其他地址都是相對于0計算把在裝入時對目標程序中指令和數(shù)據(jù)的修改過程稱為重定位,又因為地址變換通常是在裝入時一次完成的,以后不再改變,故稱為靜態(tài)重定位。靜態(tài)重定位特點:簡單、不能在內(nèi)存中移動、要求連續(xù)。2024/1/611圖4-3作業(yè)裝入內(nèi)存時的情況125002024/1/612如何將程序在內(nèi)存中從10000移動到20000？225002024/1/6133.動態(tài)運行時裝入方式(DenamicRun-timeLoading)(可用于“多道”)可重定位方式不允許程序運行時在內(nèi)存中移動位置裝入程序,在把裝入模塊裝入內(nèi)存后,并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址,而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此,裝入內(nèi)存后的所有地址都仍是相對地址,依靠硬件支持進行地址轉(zhuǎn)換。動態(tài)重定位特點:在內(nèi)存中可移動。2024/1/6144.1程序的裝入和鏈接4.1.1程序的裝入4.1.2程序的鏈接2024/1/6154.1.2程序的鏈接1.靜態(tài)鏈接方式(StaticLinking)在程序運行前,先將各目標模塊及所需的庫函數(shù)鏈接成一個完整的裝入模塊,以后不再拆開在將這幾個目標模塊裝配成一個裝入模塊時,須解決以下兩個問題

(1)對相對地址進行修改

(2)變換外部調(diào)用符號2024/1/616圖4-4程序鏈接示意圖相對地址外部調(diào)用符號2024/1/6172.裝入時動態(tài)鏈接(LoadtimeDynamicLinking)

將用戶的源程序編譯后所得的一組目標模塊在裝入內(nèi)存時采用邊裝入邊鏈接的方式優(yōu)點:(1)便于目標模塊的修改和更新

(2)便于實現(xiàn)對目標模塊的共享2024/1/6182024/1/6193.運行時動態(tài)鏈接(Run-timeDynamicLinking)

應用程序在每次運行的模塊可能不相同,出錯模塊不一定什么時候運行。運行時動態(tài)鏈接方式將對某些模塊的鏈接推遲到執(zhí)行時才去做,即在執(zhí)行過程中,當發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時,立即由OS去找到該模塊并將之裝入內(nèi)存,把它鏈接到調(diào)用者模塊上凡在執(zhí)行過程中未被用到的目標模塊,都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上,這樣不僅可加快程序的裝入過程,而且可節(jié)省大量的內(nèi)存空間2024/1/6202024/1/621內(nèi)容概述4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念4.6請求分頁存儲管理方式4.7頁面置換算法4.8請求分段存儲管理方式2024/1/6224.2連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4伙伴系統(tǒng)4.2.5哈希算法4.2.6可重定位分區(qū)分配4.2.7對換(Swapping)2024/1/6234.2.1單一連續(xù)分配連續(xù)分配方式為一個用戶程序分配一個連續(xù)的內(nèi)存空間單一連續(xù)分配是最簡單的一種存儲管理方式,但只能用于單用戶、單任務的操作系統(tǒng)中采用這種存儲管理方式時,可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分,系統(tǒng)區(qū)僅提供給OS使用,通常是放在內(nèi)存的低址部分;用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間,提供給用戶使用一般情況下無存儲器保護機構(gòu)(早期有)特點:(1)簡單易行,系統(tǒng)開銷小

(2)資源利用率低(一次只能裝入一個作業(yè))2024/1/624圖單一連續(xù)分配系統(tǒng)區(qū)用戶區(qū)2024/1/6254.2連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4伙伴系統(tǒng)4.2.5哈希算法4.2.6可重定位分區(qū)分配4.2.7對換(Swapping)2024/1/6264.2.2固定分區(qū)分配最簡單的可運行多道程序的存儲管理方式將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域,每個分區(qū)中只裝入一道作業(yè)1.劃分分區(qū)的方法(1)分區(qū)大小相等即使所有的內(nèi)存分區(qū)大小相等分區(qū)太大浪費分區(qū)太小不夠用(2)分區(qū)大小不等劃分為多個大、中、小搭配的分區(qū)根據(jù)程序大小決定所使用的分區(qū)大班在大教室、小班在小教室2024/1/627圖4-5固定分區(qū)使用表2.內(nèi)存分配按分區(qū)使用表進行分配,依分區(qū)大小排序。20未分區(qū)使用表2K作業(yè)2024/1/628圖固定分區(qū)分配2024/1/629管理特點(1)一個作業(yè)只能裝入一個分區(qū),不能裝入兩個或多個相鄰的分區(qū)。一個分區(qū)只能裝入一個作業(yè),當分區(qū)大小不能滿足作業(yè)的要求時,該作業(yè)暫時不能裝入。(2)通過對“分區(qū)使用表”的改寫,來實現(xiàn)主存的分配與回收。作業(yè)在執(zhí)行時,不會改變存儲區(qū)域,所以采用靜態(tài)地址重定位方式。此方法易于實現(xiàn),系統(tǒng)開銷小。(3)當分區(qū)較大作業(yè)較小時,仍然浪費許多主存空間,很難避免內(nèi)部碎片。并且分區(qū)總數(shù)固定,限制了并發(fā)執(zhí)行的作業(yè)數(shù)目。2024/1/6304.2連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4伙伴系統(tǒng)4.2.5哈希算法4.2.6可重定位分區(qū)分配4.2.7對換(Swapping)2024/1/631圖動態(tài)分區(qū)分配內(nèi)存使用情況示意圖4.2.3動態(tài)分區(qū)分配可變分區(qū)分配2024/1/632根據(jù)進程的實際需要,動態(tài)地為之分配內(nèi)存空間1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表:記錄每個空閑分區(qū)的情況…2024/1/633圖4-6空閑鏈結(jié)構(gòu)1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)…空閑分區(qū)鏈實現(xiàn)對空閑分區(qū)的分配和鏈接狀態(tài)0為空閑可用1為已分配分區(qū)大小2024/1/634為什么作業(yè)4分配到352KB地址空間上？2024/1/6352.分區(qū)分配算法(1)首次適應算法FF空閑分區(qū)鏈以地址遞增順序鏈接分配時從鏈首開始查找,找到一個大小可滿足的空閑分區(qū),劃出一塊給請求者可能會造成在低地址部分很多難以利用的小空閑分區(qū)優(yōu)點:(1)分配算法簡單(2)優(yōu)先利用低址部分,保留了高址的大空閑區(qū),為大作業(yè)裝入提供條件。缺點:每次從鏈首開始,增加了查找開銷,并且留下許多難以利用的”碎片”(外碎片)2024/1/6362.分區(qū)分配算法(1)首次適應算法FF(2)循環(huán)首次適應算法該算法是由首次適應算法演變而成的空閑分區(qū)鏈以地址遞增順序鏈接,鏈表為循環(huán)鏈表每次分配時從上一次找到空閑分區(qū)的下一個空閑區(qū)開始優(yōu)點:使空閑分區(qū)分布均勻,減少查找空閑分區(qū)開銷缺點:會缺乏大的空閑分區(qū)2024/1/6372.分區(qū)分配算法(1)首次適應算法FF(2)循環(huán)首次適應算法(3)最佳適應算法每次分配時,把能滿足要求、又是最小的分區(qū)分配給作業(yè)空閑分區(qū)鏈以大小遞增順序鏈接從頭開始,第一次找到滿足要求的空閑分區(qū),必然是最優(yōu)的,避免了“大材小用”宏觀上看,會在存儲器中留直許多難以利用的小分分區(qū)特點:解決了大作業(yè)的分配問題;每次總是最小的,容易產(chǎn)生不可利用的空閑區(qū)(“小碎片”);收回主存時,要按分區(qū)大小遞增順序插入到空閑區(qū)表中。2024/1/6382.分區(qū)分配算法(1)首次適應算法FF(2)循環(huán)首次適應算法(3)最佳適應算法(4)最差(壞)適應算法每次分配時,把能滿足要求、又是最大的分區(qū)分配給作業(yè)空閑分區(qū)鏈以大小遞減順序鏈接可以保證不出現(xiàn)太小的“碎片”特點:不會產(chǎn)生過多的碎片;影響大作業(yè)的分配;收回主存時,要按大小遞減的順序插入到空閑區(qū)表中。2024/1/6392.分區(qū)分配算法(1)首次適應算法FF(2)循環(huán)首次適應算法(3)最佳適應算法(4)最差(壞)適應算法(5)快速適應算法(分類搜索法)按照分區(qū)大小設(shè)置多個空閑分區(qū)鏈，增加一個索引表，可以快速對應到一個空閑分區(qū)鏈上?？臻e分區(qū)鏈分類：常用的大小分類，如2KB,4KB,8KB特點:分配速度快,不進行分區(qū)分割;存在一定的主存浪費;典型的以空間換時間的作法。2024/1/6403.分區(qū)分配操作1)分配內(nèi)存圖4-7內(nèi)存分配流程需求大小空閑大小2024/1/641圖4-8內(nèi)存回收時的情況2)回收內(nèi)存進程運行完釋放內(nèi)存時,系統(tǒng)根據(jù)回收區(qū)的首地址,從空閑鏈表區(qū)找到相應的插入點,有以下幾種情況回收區(qū)與插入點的前一個空閑分區(qū)相鄰接回收區(qū)與插入點的后一個空閑分區(qū)相鄰接

回收區(qū)同時與插入點的前、后兩個分區(qū)相鄰接回收區(qū)不與任何空閑區(qū)鄰接2024/1/642圖動態(tài)分區(qū)分配方式中釋放一個分區(qū)的流程不標準的流程圖2024/1/643管理特點分區(qū)的長度不是預先固定的,而是按作業(yè)的實際需求來劃分的。分區(qū)的個數(shù)也不是預先確定的,而是由裝入的作業(yè)數(shù)決定的。分區(qū)的大小由作業(yè)的大小來定,提高了主存的使用效率。在主存分配過程中,會產(chǎn)生許多“外碎片”?！巴馑槠笔侵感〉臒o法使用的主存空間。使主存空間仍有一定的浪費。2024/1/6444.2連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4伙伴系統(tǒng)4.2.5哈希算法4.2.6可重定位分區(qū)分配4.2.7對換(Swapping)2024/1/6454.2.4伙伴系統(tǒng)1.伙伴算法原理2.伙伴算法實例3.伙伴算法結(jié)論2024/1/6461.伙伴算法原理Linux采用伙伴(buddy)算法對物理內(nèi)存進行管理通過不斷地平分較大的空閑內(nèi)存塊來獲得較小的空閑內(nèi)存塊，直到獲得所需的內(nèi)存塊；當內(nèi)存釋放時，盡可能的合并空閑內(nèi)存塊。其中內(nèi)存塊分配與合并都采用以2的冪次方為單位。所謂“伙伴”，就是指在空閑塊被分裂時，由一個大塊內(nèi)存分裂出來的兩個小塊內(nèi)存,互稱“伙伴”算法采用位圖和空閑鏈表作為輔助工具，其中位圖用來跟蹤內(nèi)存塊的使用情況，空閑鏈表用來維護內(nèi)存中沒有使用的內(nèi)存塊2024/1/6472.伙伴算法實例

用伙伴算法管理一個64KB內(nèi)存，要求最小的分配請求單元是2KB

內(nèi)存的每個分配單元是2KB，設(shè)置位圖中的每一位對應其中的每一個分配單元，“1”表示占用，“0”表示未占用，空閑鏈表對應于64KB的容量，共６項2024/1/648圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表初始狀態(tài)2KB2024/1/6492.伙伴算法實例 續(xù)假設(shè)請求需要分配8KB的內(nèi)存算法先將64KB分為內(nèi)存32KB的A和A’，再將A分為內(nèi)存為16KB的B和B’，然后再將B分為內(nèi)存8KB的C和C’且在此過程中將A’，B’，C’分別加入到相應大小的空閑鏈表中，最后將起始為０的地址塊C返回給用戶,將位圖相應的位置置1完成分配任務2024/1/650圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表初始狀態(tài)2KB2024/1/651圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表整個內(nèi)存分成A和A’A’A申請8KB2024/1/652圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表A分成B和B’A’BB’申請8KB2024/1/653圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表B分成C和C’A’CB’申請8KBC’分配C給用戶2024/1/654圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表B分成C和C’A’CB’申請8KBC’分配C給用戶2024/1/6552.伙伴算法實例 續(xù)假設(shè)接下來又要申請一個2KB的空間，算法執(zhí)行過程如下：首先檢查空閑鏈表，若發(fā)現(xiàn)2KB的空閑鏈表為空，那么算法將上面的塊C’分成大小為4KB的D和D’，D分為2KB的E和E’，其中D’和E’分別加入到4KB和2KB的空閑鏈表中，最后將E返回給用戶，將位圖中的相應位置置為12024/1/656圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表B分成C和C’A’CB’申請2KBC’2024/1/657圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表C’分成D和D’A’CB’申請2KBD’D2024/1/658圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000011110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’申請2KBD’EE’分配E給用戶2024/1/659圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000111110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’申請2KBD’EE’分配E給用戶2024/1/660

如果用戶又要申請一個大小為16KB的內(nèi)存空間，算法的執(zhí)行過程同上，但這時搜索空閑鏈表時，發(fā)現(xiàn)正好有一個16KB的空閑塊，該算法首先從16KB的空閑鏈表中刪除B’，并將B’的地址返回給用戶，同時將位圖相應位置“1”2.伙伴算法實例 續(xù)2024/1/661圖伙伴算法2KB4KB8KB16KB32KB64KB00000000000111110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’申請16KBD’EE’2024/1/662圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000111110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’申請16KBD’EE’分配B’給用戶2024/1/6632.伙伴算法實例 續(xù)伙伴算法如何釋放內(nèi)存的呢？假設(shè)首先被釋放的是大小為8KB的C塊，算法首先檢查C’，C’正處于使用狀態(tài)，不會合并，因此算法將C塊加入到8KB的空閑鏈表中。算法釋放內(nèi)存時，其相應的位圖會被清零。2024/1/664圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000111110000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’釋放8KB的C塊D’EE’C’正處于使用狀態(tài)無法合并C’2024/1/665圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000100000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’釋放8KB的C塊D’EE’2024/1/6662.伙伴算法實例 續(xù)伙伴算法如何釋放內(nèi)存的呢？如果接下來又釋放了大小為2KB的E塊，發(fā)現(xiàn)伙伴E’空閑，將E和E‘合并，得到大小為4KB的D塊，又發(fā)現(xiàn)D的伙伴D’空閑，合并得到大小為8KB的C‘塊，又發(fā)現(xiàn)C’的伙伴C處于空閑狀態(tài)，將C和C‘合并，并添加到16KB的空閑鏈表中。算法釋放內(nèi)存時，其相應的位圖會被清零。2024/1/667圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000100000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’釋放2KB的E塊D’EE’2024/1/668圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’釋放2KB的E塊D’EE’E’正處于空閑狀態(tài)E和E’合并2024/1/669圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’釋放2KB的E塊D’DD’正處于空閑狀態(tài)D和D’合并2024/1/670圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’CB’釋放2KB的E塊C’C正處于空閑狀態(tài)C和C’合并2024/1/671圖伙伴算法2KB4KB8KB16KB32KB64KB11111111000000000000000000000000位圖0KB8KB16KB32KB64KB內(nèi)存塊0KB8KB16KB32KB64KB空閑鏈表D’分成E和E’A’BB’釋放2KB的E塊2024/1/6723.伙伴算法結(jié)論當需要為進程分配一個長度為n的存儲空間時，首先計算一個i值，使2i-1<n≤2i，在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找，否則在2i+1找，等分后分配，依次類推。2024/1/6734.2連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4伙伴系統(tǒng)4.2.5哈希算法4.2.6可重定位分區(qū)分配4.2.7對換(Swapping)2024/1/6744.2.5哈希算法引入原因：上述的分類搜索法和伙伴系統(tǒng)中，都是把空閑分區(qū)進行分類，再查找這些分類的分區(qū)上會使時間性能下降。原理：哈希算法就是利用哈?？焖俨檎业膬?yōu)點，對索引表進行快速查找。2024/1/6754.2連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4伙伴系統(tǒng)4.2.5哈希算法4.2.6可重定位分區(qū)分配4.2.7對換(Swapping)2024/1/6764.2.6可重定位分區(qū)分配圖4-9緊湊的示意1.可重定位的引入連續(xù)分配存在的問題

必須有足夠大的連續(xù)空間才能分配“拼接”或“緊湊”的引入來了31K程序2024/1/677缺點:(1)緊湊增加主機的開銷

(2)緊湊修改空閑分區(qū)表移動條件:無內(nèi)外存信息交換2024/1/678圖4-10可重定位示意圖2.可重定位的實現(xiàn)作業(yè)裝入內(nèi)存后的所有地址仍是相對地址,將相對地址轉(zhuǎn)換成物理地址的工作在指令執(zhí)行時進行地址變換過程是在程序執(zhí)行期間,隨著每條指令和數(shù)據(jù)的訪問而自動進行的。真正訪問地址=相對地址+重定位寄存器中地址需要有硬件地址變換機構(gòu)的支持2024/1/6793.可重定位分區(qū)分配算法圖4-11可分區(qū)分配算法流程圖2024/1/680可重定位分區(qū)分配法的優(yōu)缺點優(yōu)點:可以消除碎片,能夠分配更多的分區(qū),有助于多道程序設(shè)計,提高內(nèi)存的利用率。缺點:緊湊花費了大量CPU時間;2024/1/6814.2連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4伙伴系統(tǒng)4.2.5哈希算法4.2.6可重定位分區(qū)分配4.2.7對換(Swapping)2024/1/682圖對換兩個進程2024/1/6834.2.7對換(Swapping)1.對換的引入所謂“對換”,是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù),調(diào)出到外存上,以便騰出足夠的內(nèi)存空間,再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù),調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施如果對換是以整個進程為單位,稱為“整體對換”或“進程對換”如果對換是以“頁”或“段”為單位進行的,則稱為“頁面對換”或“分段對換”,又統(tǒng)稱為“部分對換”,這種對換方法是實現(xiàn)請求分頁及請求分段式存儲器的基礎(chǔ),其目的是為了支持虛擬存儲系統(tǒng)。2024/1/6842.對換空間的管理在具有對換功能的OS中,通常把外存分為文件區(qū)和對換區(qū)文件區(qū)管理的主要目標是提高文件存儲空間的利用率,采取離散分配方式。外存中對換區(qū)主要存放從內(nèi)存中換出的進程,對換空間管理的主要目標是提高進程換入和換出的速度。為了能對對換區(qū)中的空閑盤塊進行管理,在系統(tǒng)中應配置相應的數(shù)據(jù)結(jié)構(gòu),以記錄外存的使用情況。其形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似,即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應包含兩項,即對換區(qū)的首址及其大小,它們的單位是盤塊號和盤塊數(shù)對換區(qū)的分配采用連續(xù)分配方式,分配算法可以是首次適應算法、循環(huán)首次適應算法或最佳適應算法2024/1/6853.進程的換出與換入(1)進程的換出 ①選出被換出的進程選擇原則:ⅰ先“阻塞”或“睡眠”的進程,后“就緒”

ⅱ優(yōu)先級低的進程

ⅲ在內(nèi)存最長的進程的進程換出

ⅳ最近最久未使用進程②進程換出過程系統(tǒng)首先選擇處于“阻塞”狀態(tài)且優(yōu)先級最低的進程作為換出進程,然后啟動盤塊,將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯誤,便可回收該進程所占用的內(nèi)存空間,并對該進程的進程控制塊做相應的修改。2024/1/6863.進程的換出與換入(1)進程的換出(2)進程的換入系統(tǒng)應定時地查看所有進程的狀態(tài),從中找出(PCB集合中)“就緒”狀態(tài)且已換出的進程,將其中換出時間(換出到磁盤上)最久的進程作為換入進程,申請內(nèi)存,若成功將之換入,否則在換出某些進程,騰出足夠內(nèi)存,在換入。2024/1/687內(nèi)容概述4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式

4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念4.6請求分頁存儲管理方式4.7頁面置換算法4.8請求分段存儲管理方式2024/1/688離散分配方式連續(xù)分配方式要求為一個進程分配連續(xù)的內(nèi)存空間(整體裝入),分形成許多“碎片”而浪費,“緊湊”操作會付出相當大的代價如果允許一個進程直接分散地裝入到許多不相鄰接的分區(qū)中,稱為離散分配方式離散分配方式有分頁存儲管理方式、分段存儲管理方式和段頁存儲管理方式2024/1/689將用戶作業(yè)的地址空間分成若干個大小相同的區(qū)域,稱為頁面或頁,并為每個頁從“0”開始編號;相應地,主存空間也分成與頁大小相同的若干個存儲塊,或稱為物理塊或頁框(frame),并且采用同樣的方式為它們進行編號,從0開始:0塊,1塊,…,n-1塊。以便將碎片限制在較小的范圍內(nèi)。不再需要進行空閑區(qū)域的合并拼接。程序的邏輯地址由頁號和頁內(nèi)地址組成,頁號的長度決定了分頁的多少,頁內(nèi)地址的長度決定了頁面的大小。在為作業(yè)分配主存時,以塊為單位將作業(yè)中的若干頁分別裝入多個可以不相鄰接的塊中。作業(yè)執(zhí)行時根據(jù)邏輯地址中的頁號找到它所在的塊號,再確定當前指令要訪問的主存的物理地址。分頁存儲管理方式2024/1/690分頁的概念程序地址空間分成大小相等的頁面,同時把內(nèi)存也分成與頁面大小相等的塊,當一個用戶程序裝入內(nèi)存時,以頁面為單位進行分配。頁面的大小是為2n,通常為1KB,2KB,nKB等。2024/1/6914.3.1頁面與頁表4.3.2地址變換機構(gòu)4.3.3兩級和多級頁表4.3基本分頁存儲管理方式2024/1/6924.3.1頁面與頁表1.頁面1)頁面和物理塊分頁存儲管理,是將一個進程的邏輯地址空間分成若干個大小相等的片,稱為頁面或頁,并為各頁加以編號,從0開始,如第0頁、第1頁等也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊,稱為物理塊或頁框(frame),也同樣為它們加以編號,如0＃塊、1＃塊等等在為進程分配內(nèi)存時,以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片,稱之為“頁內(nèi)碎片”由編譯系統(tǒng)或用戶2024/1/693圖4-12頁表的作用3.頁表分頁系統(tǒng)中,將進程的每一頁離散地存儲在內(nèi)存的任一物理塊中,為每個進程建立一張頁面映像表,簡稱頁表作用:是實現(xiàn)從頁號到物理塊號的地址映射。通常沒有存頁號,要連續(xù)分配2024/1/6942024/1/695

2)頁面大小在分頁系統(tǒng)中的頁面其大小應適中,由硬件決定,即由機器的地址結(jié)構(gòu)所決定。頁面若太小,一方面雖然可使內(nèi)存碎片減小,從而減少了內(nèi)存碎片的總空間,有利于提高內(nèi)存利用率,但另一方面也會使每個進程占用較多的頁面,從而導致進程的頁表過長,占用大量內(nèi)存;此外,還會降低頁面換進換出的效率如果選擇的頁面較大,雖然可以減少頁表的長度,提高頁面換進換出的速度,但卻又會使頁內(nèi)碎片增大。因此,頁面的大小應選擇得適中,且頁面大小應是2的冪,通常為512B~8KB2024/1/6962.地址結(jié)構(gòu)分頁地址包括頁號和頁內(nèi)地址(頁內(nèi)位移量),其地址結(jié)構(gòu)如下:頁號P頁內(nèi)相對地址(位移量W)3112110

對某特定機器,其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中的地址為A,頁面的大小為L,則頁號P和頁內(nèi)地址d可按下式求得:220=1M212=4KB2024/1/697例:系統(tǒng)頁面大小為1KB,邏輯地址為2170B,求頁號與頁內(nèi)地址。頁號P=INT[2170/1024]=2頁內(nèi)地址d=2170mod1024=122B第0頁0~1023第1頁1024~2047第2頁2048~30712024/1/6984.3.1頁面與頁表4.3.2地址變換機構(gòu)4.3.3兩級和多級頁表4.3基本分頁存儲管理方式2024/1/6994.3.2地址變換機構(gòu)1.基本地址變換機構(gòu)用于實現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換,將邏輯地址中的頁號轉(zhuǎn)換為內(nèi)存中的物理塊號,通過頁表來完成頁表大多駐留在內(nèi)存中,在系統(tǒng)中設(shè)置頁表寄存器PTR(Page–TableRegister),在其中存放頁表在內(nèi)存中的始址和頁表的長度進程未執(zhí)行時,頁表的始址和頁表長度存放在本進程的PCB中,當調(diào)度程序調(diào)度到某進程時,才將這兩個數(shù)據(jù)裝入頁表寄存器2024/1/6100圖4-13分頁系統(tǒng)的地址變換機構(gòu)以頁號查頁表,得到對應頁裝入內(nèi)存的塊號內(nèi)存地址＝物理塊號×頁大?。搩?nèi)地址bw訪問兩次內(nèi)存2024/1/61012.具有快表的地址變換機構(gòu)由于頁表是存放在內(nèi)存中,因此每次CPU存取一個數(shù)據(jù)要兩次訪問內(nèi)存即,查頁表時要作一次訪問內(nèi)存的工作,然后是訪問程序要求訪問的內(nèi)存,這樣,存取速度降低一倍,將會影響整個系統(tǒng)的使用效率。為提高地址變換速度,在地址變換機構(gòu)中增設(shè)一個具有并行查尋能力的高速緩沖寄存器,又稱為“聯(lián)想寄存器”(AssociativeMemory)或“快表”,用以存放當前訪問的那些頁表項,價格貴?？毂硗ǔ？纱娣?6-512個表項,命中率可達90％以上2024/1/6102圖4-14具有快表的地址變換機構(gòu)2024/1/6103例題例1:有一系統(tǒng)采用分頁存儲管理,有一作業(yè)大小是8KB,頁大小為2KB,依次裝入內(nèi)存的第7、9、A、5,試將邏輯地址0AFEH字節(jié),1ADDH字節(jié)轉(zhuǎn)換成內(nèi)存地址。答:邏輯地址0AFEH字節(jié)0000101011111110P＝1W＝01011111110字節(jié)內(nèi)存地址＝0100101011111110

＝4AFEH字節(jié)2024/1/6104例題邏輯地址1ADDH字節(jié)0001101011011101P＝3W＝01011011101字節(jié)內(nèi)存地址＝0010101011011101＝2ADDH字節(jié)2024/1/6105例題例2:有一系統(tǒng)采用分頁存儲管理,有一作業(yè)大小是8KB,頁大小為2KB,依次裝入內(nèi)存的第7、9、10、5塊,試將邏輯地址7145字節(jié),3412字節(jié)轉(zhuǎn)換成內(nèi)存地址。2024/1/6106例題邏輯地址7145字節(jié)P＝INT[7145/2048]＝3W＝7145mod2048

＝1001字節(jié)內(nèi)存地址=5*2048=11241字節(jié)邏輯地址7145字節(jié)的內(nèi)存地址是:11241字節(jié)2024/1/6107例題邏輯地址3412字節(jié)P＝INT[3412/2048]＝1W＝3412mod2048

＝1364字節(jié)內(nèi)存地址=9*2048=19796字節(jié)邏輯地址3412字節(jié)的內(nèi)存地址是:19796字節(jié)2024/1/61084.3.1頁面與頁表4.3.2地址變換機構(gòu)4.3.3兩級和多級頁表4.3基本分頁存儲管理方式2024/1/61094.3.3兩級和多級頁表現(xiàn)代的大多數(shù)計算機系統(tǒng),都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下,頁表就變得非常大,要占用相當大的內(nèi)存空間例如,對于一個具有32位邏輯地址空間的分頁系統(tǒng),若規(guī)定頁面大小為4KB即212B,則在每個進程頁表中的頁表項可達1M(220)個之多。每個頁表項占用4個字節(jié)(32bit),故每個進程僅僅其頁表就要占用4MB的內(nèi)存空間,而且還要求是連續(xù)的。頁號P偏移量W3112110220=1M2024/1/6110可以采用兩個方法來解決這一問題①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題②只將當前需要的部分頁表項調(diào)入內(nèi)存,其余的頁表項仍駐留在磁盤上,需要時再調(diào)入2024/1/61111.兩級頁表(Two-LevelPageTable)

可利用將頁表分頁,并離散地將各個頁面分別存放在不同的物理塊中,同樣要為離散分配的頁表再建立一張頁表,稱為外層頁表(OuterPageTable),每個頁表項中記錄了頁表頁面的物理塊號210=1024210=1024212=4KB2024/1/6112圖4-15兩級頁表結(jié)構(gòu)兩級頁表結(jié)構(gòu)每個物理塊為4KB,恰好放一個1頁頁表(1024個項,每項4B),共需1024個這樣的塊0表示沒有裝入內(nèi)存1表示在內(nèi)存2024/1/6113圖4-16具有兩級頁表的地址變換機構(gòu)外層頁表始址頁表始址物理塊2024/1/61142.多級頁表對于32位的機器,采用兩級頁表結(jié)構(gòu)是合適的;但對于64位的機器,如果頁面大小仍采用4KB即212B,那么還剩下52位,假定仍按物理塊的大小(210位)來劃分頁表,則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項,要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級頁表,將外層頁表再進行分頁,也是將各分頁離散地裝入到不相鄰接的物理塊中,再利用第2級的外層頁表來映射它們之間的關(guān)系對于64位的計算機,如果要求它能支持264(=1844744TB)規(guī)模的物理存儲空間,則即使是采用三級頁表結(jié)構(gòu)也是難以辦到的;而在當前的實際應用中也無此必要2024/1/6115具有64位地址的分頁存儲管理242=4096G210=1024212=4KB632024/1/6116分頁存儲管理方案的評價(1)采用動態(tài)地址變換會增加計算機成本和降低處理機的速度。

(2)各種表格要占用一定容量的主存空間,而且還要花費一部分處理機時間用來建立和管理這些表格。

(3)雖然說外碎片消除了,但每個作業(yè)的最后一頁一般都有不能充分利用的空閑區(qū)。

(4)存儲擴充問題仍未得到解決。2024/1/6117內(nèi)容概述4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式

4.5虛擬存儲器的基本概念4.6請求分頁存儲管理方式4.7頁面置換算法4.8請求分段存儲管理方式2024/1/61184.4基本分段存儲管理方式在分段存儲管理方式中,作業(yè)的地址空間被劃分為若干個段,每個段定義了一組邏輯信息。它以段為單位分配主存,每段分配一個連續(xù)的主存空間,但各段之間不要求連續(xù)。由于各段的長度不一樣,所以分配的內(nèi)存空間大小也不一樣。供用戶使用的邏輯地址為段號(段名)+段內(nèi)地址。在裝入作業(yè)時,用一張段表記錄每個分段在主存中的起始地址和長度。若裝入作業(yè)的某段信息找不到足夠大的空閑區(qū),可采用移動技術(shù),合并分散的空閑區(qū)。主存的分配與回收類似于動態(tài)分區(qū)分配,采用動態(tài)重定位。2024/1/61194.4基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式2024/1/61204.4.1分段存儲管理方式的引入分頁存儲管理的主要目的是為了提高內(nèi)存利用率,分段存儲管理的主要目的是為了滿足用戶在編程和使用上的要求分段管理的主要目的方便編程(這是主要的因素)用戶作業(yè)通常按邏輯關(guān)系分若干個段如LOAD1,[A]|<D>;STORE1,[B]|<C>;信息共享程序與數(shù)據(jù)的共享是以信息的邏輯單位為基礎(chǔ)信息保護動態(tài)增長動態(tài)鏈接2024/1/61214.4基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式2024/1/61224.4.2分段系統(tǒng)的基本原理1.分段分段存儲管理方式中,作業(yè)的地址空間被分成若干個段(segment),每個段定義了一組邏輯信息分段地址中的地址具有如下結(jié)構(gòu)分段方式已得到許多編譯程序的支持段號段內(nèi)地址3116150216=64K216=64K2024/1/61232.段表在分段存儲管理系統(tǒng)中,為每個分段分配一個連續(xù)的分區(qū),而進程中的各個段可以離散地移入內(nèi)存中的不同的分區(qū)中系統(tǒng)為每個進程建立一張段映射表,簡稱為“段表”每個段在段表中占一個表項,其中記錄了該段在內(nèi)存中的起始地址(又稱為“基址”)和段的長度實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。2024/1/6124圖4-17利用段表實現(xiàn)地址映射缺點:外碎片類似可重定位分區(qū)分配2024/1/6125圖4-18分段系統(tǒng)的地址變換過程3.地址變換機構(gòu)訪問兩次內(nèi)存還要檢查段內(nèi)地址與段長是否越界,越界發(fā)中斷2024/1/61264.分頁和分段的主要區(qū)別頁是信息的物理單位,分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位,它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要頁的大小固定且由系統(tǒng)決定(由機器硬件決定),一個系統(tǒng)只有一種大小的頁面;而段的長度卻不固定,決定于用戶所編寫的程序分頁的作業(yè)地址空間是一維的,即單一的線性地址空間,程序員只需利用一個記憶符,即可表示一個地址;而分段的作業(yè)地址空間則是二維的,程序員在標識一個地址時,既需給出段名,又需給出段內(nèi)地址相同:都是采用離散分配方式,且都要通過地址映射機構(gòu)實現(xiàn)地址變換。2024/1/61274.4基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式2024/1/61284.4.3信息共享分段存儲的一個優(yōu)點是易于實現(xiàn)段的共享,即允許若干個進程共享一個或多個分段分頁系統(tǒng)中雖然也能實現(xiàn)程序和數(shù)據(jù)的共享,但遠不如分段系統(tǒng)方便可重入代碼(ReentrantCode)又稱為“純代碼”(PureCode)是一種允許多個進程同時訪問的代碼?？芍厝氪a是一種不允許任何進程對它進行修改的代碼

(1)程序在執(zhí)行時可能改變的部分,拷貝到該局部數(shù)據(jù)區(qū)。

(2)程序執(zhí)行時,只對該數(shù)據(jù)區(qū)(屬于該進程私有)中的內(nèi)容進行修改,而不去改變共享的代碼。2024/1/6129圖4-19分頁系統(tǒng)中共享editor的示意圖2024/1/6130圖4-20分段系統(tǒng)中共享editor的示意圖2024/1/6131分段管理特點(1)段長可以根據(jù)需要動態(tài)增長。這樣,便于對具有完整邏輯功能的信息段共享,便于實現(xiàn)程序的動態(tài)鏈接。(2)存在外碎片問題,若采用“緊湊”技術(shù)合并空閑區(qū),會增加系統(tǒng)開銷。(3)段的大小受主存可用空閑區(qū)大小的限制。2024/1/61324.4基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式2024/1/61334.4.4段頁式存儲管理方式1.基本原理是分段和分頁原理的結(jié)合將用戶程序分成若干個段,并為每一段賦予一個段名,再把每一段分成若干個頁,把主存分成與頁大小相同的塊,每段分配與其頁數(shù)相同的主存塊,主存塊可以連續(xù),也可以不連續(xù)。段頁式管理中,邏輯地址由段號、段內(nèi)頁號及頁內(nèi)地址三部分所組成2024/1/6134圖4-21段頁式地址結(jié)構(gòu)2024/1/6135圖4-22利用段表和頁表實現(xiàn)地址映射2024/1/61362.地址變換過程圖4-23段頁式系統(tǒng)中的地址變換機構(gòu)訪問三次內(nèi)存2024/1/6137段頁式管理特點根據(jù)程序情況把程序分成若干段,再根據(jù)頁面大小把每一段分成若干頁,主存仍然分成與頁大小相等的塊。分配主存時,把程序的每一段的頁分配到主存塊中。這種分配方式既照顧到了用戶共享和使用方便的需求,又考慮到了主存的利用率,提高了系統(tǒng)的性能。這種分配方式比分頁管理的空間浪費要多。程序各段的最后一頁都有可能浪費一部分空間。另外段表和頁表占用空間,都比分頁和分段多一些,這樣就增加了硬件成本、系統(tǒng)的復雜性和開銷。2024/1/6138內(nèi)容概述4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念

4.6請求分頁存儲管理方式4.7頁面置換算法4.8請求分段存儲管理方式2024/1/6139問題的提出在程序的某次運行,執(zhí)行了這部分程序就不會執(zhí)行另一部分程序。當把作業(yè)全部裝入主存后,作業(yè)執(zhí)行時實際上只使用部分信息,甚至有些部分在作業(yè)執(zhí)行的整個過程中都不會被使用到(局部性原理)。是否需要一次性地將作業(yè)全部裝入？作業(yè)是否需要長期地駐留在主存？不少學者已進行了廣泛的研究,這些研究結(jié)果為虛擬存儲器的實現(xiàn)奠定了基礎(chǔ)。2024/1/61404.5虛擬存儲器的基本概念4.5.1虛擬存儲器的引入4.5.2虛擬存儲器的實現(xiàn)方法4.5.3虛擬存儲器的特征2024/1/6141連續(xù)分配離散分配(基本)分頁(基本)分段段頁式方便程序裝入提高內(nèi)存利用率2024/1/61424.5.1虛擬存儲器的引入作業(yè)裝入內(nèi)存時可能會出現(xiàn)如下問題(1)作業(yè)太大,因無足夠內(nèi)存而不能裝入,無法運行。(2)無足夠內(nèi)存滿足大量作業(yè)運行的要求。只能將少量作業(yè)裝入內(nèi)存讓它們先運行,而將大量作業(yè)留在外存上等待。解決方法:(1)增加內(nèi)存容量(從物理上增加內(nèi)存容量),成本加大。(2)邏輯上擴充內(nèi)存容量,即采用虛擬存儲技術(shù)。2024/1/61431.常規(guī)存儲器管理方式的特征(1)一次性要求作業(yè)全部裝入內(nèi)存才能運行(2)駐留性作業(yè)裝入內(nèi)存后便一直駐留內(nèi)存,直至運行結(jié)束2024/1/61442.局部性原理

早在1968年,Denning.P就曾指出:程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律,即在一較短的時間內(nèi),程序的執(zhí)行僅局限于某個部分;相應地,它所訪問的存儲空間也局限于某個區(qū)域。提出論點如下: (1)程序執(zhí)行時,除了少部分的轉(zhuǎn)移和過程調(diào)用指令外,在大多數(shù)情況下仍是順序執(zhí)行的。

(2)過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域,但經(jīng)研究看出,過程調(diào)用的深度在大多數(shù)情況下都不超過5。

(3)程序中存在許多循環(huán)結(jié)構(gòu),這些雖然只由少數(shù)指令構(gòu)成,但是它們將多次執(zhí)行。

(4)程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理,如對數(shù)組進行操作,它們往往都局限于很小的范圍內(nèi)。2024/1/6145

局限性又表現(xiàn)在下述兩個方面:(1)時間局限性。如果程序中的某條指令一旦執(zhí)行,則不久以后該指令可能再次執(zhí)行;如果某數(shù)據(jù)被訪問過,則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時間局限性的典型原因,是由于在程序中存在著大量的循環(huán)操作。

(2)空間局限性。一旦程序訪問了某個存儲單元,在不久之后,其附近的存儲單元也將被訪問,即程序在一段時間內(nèi)所訪問的地址,可能集中在一定的范圍之內(nèi),其典型情況便是程序的順序執(zhí)行。2024/1/61463.虛擬存儲器定義虛擬存儲器是指具有請求調(diào)入功能和置換功能,能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定(由地址結(jié)構(gòu)決定的)其運行速度接近于內(nèi)存速度,而每位的成本卻又接近于外存。虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù),故被廣泛地應用于大、中、小型機器和微型機中。書上2024/1/61474.5虛擬存儲器的基本概念4.5.1虛擬存儲器的引入4.5.2虛擬存儲器的實現(xiàn)方法4.5.3虛擬存儲器的特征2024/1/6148虛擬存儲器的實現(xiàn)都是建立在離散分配的存儲管理方式基礎(chǔ)上的主要有請求分頁系統(tǒng)和請求分段系統(tǒng)兩種方式2024/1/61494.5.2虛擬存儲器的實現(xiàn)方法1.請求分頁系統(tǒng)在分頁系統(tǒng)的基礎(chǔ)上增加了請求調(diào)頁功能和頁面置換功能(1)硬件支持請求分頁的頁表機制,它是在純分頁的頁表機制上增加若干項而形成的,作為請求分頁的數(shù)據(jù)結(jié)構(gòu);缺頁中斷機構(gòu),即每當用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時便產(chǎn)生一缺頁中斷,以請求OS將所缺的頁調(diào)入內(nèi)存;地址變換機構(gòu),它同樣是在純分頁地址變換機構(gòu)的基礎(chǔ)上發(fā)展形成的(2)實現(xiàn)請求分頁的軟件用于實現(xiàn)請求調(diào)頁的軟件和實現(xiàn)頁面置換的軟件2024/1/61502.請求分段系統(tǒng) 在分段系統(tǒng)的基礎(chǔ)上,增加了請求調(diào)段及分段置換功能(1)硬件支持請求分段的段表機制缺段中斷機構(gòu)地址變換機構(gòu)(2)軟件支持用于實現(xiàn)請求調(diào)段的軟件和實現(xiàn)分段置換的軟件2024/1/61514.5虛擬存儲器的基本概念4.5.1虛擬存儲器的引入4.5.2虛擬存儲器的實現(xiàn)方法4.5.3虛擬存儲器的特征2024/1/61524.5.3虛擬存儲器的特征1.離散性離散性是指在主存分配時采用離散分配方式。2.多次性

一個作業(yè)被分成多次調(diào)入內(nèi)存運行3.對換性允許在作業(yè)的運行過程中進行換進、換出4.虛擬性能夠從邏輯上擴充內(nèi)存容量,使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。2024/1/6153內(nèi)容概述4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念4.6請求分頁存儲管理方式

4.7頁面置換算法4.8請求分段存儲管理方式2024/1/61544.6請求分頁存儲管理方式4.6.1請求分頁中的硬件支持4.6.2內(nèi)存分配策略和分配算法4.6.3調(diào)頁策略2024/1/61554.6.1請求分頁中的硬件支持1.頁表機制它是在分頁存儲管理系統(tǒng)上增加了請求調(diào)頁功能、頁面置換功能所形成的分頁式虛擬存儲管理系統(tǒng)。每個頁表(增加了四個字段),如下:

狀態(tài)位P

用于指示該頁是否已調(diào)入內(nèi)存訪問字段A

用于記錄本頁在一段時間內(nèi)被訪問的次數(shù),或記錄本頁在最近多長時間未被訪問修改位M

表示該頁在調(diào)入內(nèi)存后是否被修改過外存地址該頁在外存上的地址,通常是物理塊號頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址2024/1/61562.缺頁中斷機構(gòu)在請求分頁系統(tǒng)中,每當所要訪問的頁面不在內(nèi)存時,便產(chǎn)生一缺頁中斷缺頁中斷與一般中斷的區(qū)別在指令執(zhí)行期間產(chǎn)生和處理中斷信號一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷2024/1/6157圖4-24涉及6次缺頁中斷的指令2024/1/61583.地址變換機構(gòu)圖4-25請求分頁中的地址變換過程2024/1/61594.6請求分頁存儲管理方式4.6.1請求分頁中的硬件支持4.6.2內(nèi)存分配策略和分配算法4.6.3調(diào)頁策略2024/1/61604.6.2內(nèi)存分配策略和分配算法1.最小物理塊數(shù)的確定是指能保證進程正常運行所需的最小物理塊數(shù)。當系統(tǒng)為進程分配的物理塊數(shù)少于此值時,進程將無法運行進程應獲得的最少物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān),取決于指令的格式、功能和尋址方式對于某些簡單的機器,若是單地址指令且采用直接尋址方式,則所需的最少物理塊數(shù)為2。其中,一塊是用于存放指令的頁面,另一塊則是用于存放數(shù)據(jù)的頁面如果該機器允許間接尋址時,則至少要求有三個物理塊對于某些功能較強的機器,其指令長度可能是兩個或多于兩個字節(jié),因而其指令本身有可能跨兩個頁面,且源地址和目標地址所涉及的區(qū)域也都可能跨兩個頁面,可能至少需要6個物理塊2024/1/61612.物理塊的分配策略

在請求分頁系統(tǒng)中,可采取兩種內(nèi)存分配策略,即固定和可變分配策略。在進行置換時,也可采取兩種策略,即全局置換和局部置換。于是可組合出以下三種適用的策略固定分配局部置換 為每個進程分配固定頁數(shù)的內(nèi)存空間,在整個運行期間不再改變。分配頁數(shù)少,會頻繁缺頁中斷;分配頁數(shù)多,浪費資源,內(nèi)存中運行作業(yè)少?？勺兎峙渚植恐脫Q 為每個進程分配一定量的內(nèi)存空間。若運行中頻繁缺頁中斷,則再增加若干物理塊,直至缺頁率減少到適當值為止。反之,若缺頁率很低,則減少物理塊可變分配全局置換 先為每個進程分配一定量物理塊,OS有一個空閑物理塊隊列,某進程缺頁時從空閑隊列取塊裝頁,當空閑隊列為空后,OS再調(diào)出某一進程的頁,置換2024/1/61623.物理塊分配算法(1)平均分配算法這是將系統(tǒng)中所有可供分配的物理塊,平均分配給各個進程例如,當系統(tǒng)中有100個物理塊,有5個進程在運行時,每個進程可分得20個物理塊。這種方式貌似公平,但實際上是不公平的,因為它未考慮到各進程本身的大小。如有一個進程其大小為200頁,只分配給它20個塊,這樣,它必然會有很高的缺頁率;而另一個進程只有10頁,卻有10個物理塊閑置未用2024/1/6163(2)按比例分配算法

這是根據(jù)進程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進程,每個進程的頁面數(shù)為Si,則系統(tǒng)中各進程頁面數(shù)的總和為:

又假定系統(tǒng)中可用的物理塊總數(shù)為m,則每個進程所能分到的物理塊數(shù)為bi,將有:b應該取整,它必須大于最小物理塊數(shù)。2024/1/6164(3)考慮優(yōu)先權(quán)的分配算法

在實際應用中,為了照顧到重要的、緊迫的作業(yè)能盡快地完成,應為它分配較多的內(nèi)存空間通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分:一部分按比例分配給各進程;另一部分則根據(jù)各進程的優(yōu)先權(quán),適當?shù)卦黾悠湎鄳蓊~后,分配給各進程在有的系統(tǒng)中,如重要的實時控制系統(tǒng),則可能是完全按優(yōu)先權(quán)來為各進程分配其物理塊的2024/1/61654.6請求分頁存儲管理方式4.6.1請求分頁中的硬件支持4.6.2內(nèi)存分配策略和分配算法4.6.3調(diào)頁策略2024/1/61664.6.3調(diào)頁策略1.何時調(diào)入頁面(1)預調(diào)頁策略采用一種以預測為基礎(chǔ)的預調(diào)頁策略,將那些預計在不久之后便會被訪問的頁面預先調(diào)入內(nèi)存,在連續(xù)分配時,一次調(diào)入若干相鄰的頁。這樣方法從表面上看起來很好,但系統(tǒng)無法預計系統(tǒng)中作業(yè)的運行情況,難以實現(xiàn),成功率50%。(2)請求調(diào)頁策略當進程在運行中需要訪問某部分程序和數(shù)據(jù)時,若發(fā)現(xiàn)其所在的頁面不在內(nèi)存,便提出請求,由OS將其所需頁面調(diào)入內(nèi)存目前的虛擬存儲中大多采用此種策略2024/1/61672.從何處調(diào)入頁面在請求分頁系統(tǒng)中的外存分為兩部分:用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。對換區(qū)的磁盤I/O速度比文件區(qū)的高每當發(fā)生缺頁請求時,系統(tǒng)應從何處將缺頁調(diào)入內(nèi)存,可分成如下三種情況(1)系統(tǒng)擁有足夠的對換區(qū)空間,這時可以全部從對換區(qū)調(diào)入所需頁面,以提高調(diào)頁速度。在進程運行前,文件由文件區(qū)->對換區(qū)。(2)系統(tǒng)缺少足夠的對換區(qū)空間,這時凡是不會被修改的文件,都直接從文件區(qū)調(diào)入。凡是會被修改的文件,都直接從對換區(qū)調(diào)入。(3)UNIX方式。開始時,由于與進程有關(guān)的文件都放在文件區(qū),故凡是未運行過的頁面,都應從文件區(qū)調(diào)入。換出到對換區(qū),以后再調(diào)入就從對換區(qū)調(diào)入。2024/1/61683.頁面調(diào)入過程每當程序所要訪問的頁面未在內(nèi)存時,便向CPU發(fā)出一缺頁中斷,中斷處理程序首先保留CPU環(huán)境,分析中斷原因后,轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表,得到該頁在外存的物理塊后,如果此時內(nèi)存能容納新頁,則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存,然后修改頁表。如果內(nèi)存已滿,則須先按照某種置換算法從內(nèi)存中選出一頁準備換出。如果該頁未被修改過,可不必將該頁寫回磁盤;但如果此頁已被修改,則必須將它寫回磁盤,然后再把所缺的頁調(diào)入內(nèi)存,并修改頁表中的相應表項,置其存在位為“1”,并將此頁表項寫入快表中。在缺頁調(diào)入內(nèi)存后,利用修改后的頁表,去形成所要訪問數(shù)據(jù)的物理地址,再去訪問內(nèi)存數(shù)據(jù)。整個頁面的調(diào)入過程對用戶是透明的。2024/1/6169請求分頁存儲管理方式的特點優(yōu)點:不需要程序段和數(shù)據(jù)在內(nèi)存中連續(xù)存放,便于有效利用內(nèi)存;提供了內(nèi)外存統(tǒng)一管理的虛擬存儲技術(shù),擴大了內(nèi)存空間。缺點