操作系統(tǒng)課件第四章1

第四章存儲(chǔ)器管理操作系統(tǒng)Page12023/2/3第四章存儲(chǔ)器管理重點(diǎn)理解重定位的基本概念

掌握動(dòng)態(tài)分區(qū)分配方式

掌握理解分頁和分段存儲(chǔ)管理方式

理解虛擬存儲(chǔ)器的基本概念

掌握請(qǐng)求分頁系統(tǒng)的基本原理

難點(diǎn)動(dòng)態(tài)分區(qū)分配算法

分頁和分段地址轉(zhuǎn)換請(qǐng)求分頁系統(tǒng)的地址轉(zhuǎn)換及頁面置換算法Page22023/2/3第四章存儲(chǔ)器管理知識(shí)點(diǎn)重定位的基本概念

動(dòng)態(tài)分區(qū)分配方式及分配算法、分區(qū)保護(hù)分頁存儲(chǔ)管理及地址變換、分段存儲(chǔ)管理及地址變換，信息共享和保護(hù)虛擬存儲(chǔ)器的基本概念、特征，頁面置換技術(shù)

請(qǐng)求分頁系統(tǒng)，頁表機(jī)制、地址變換及頁面置換算法

Page32023/2/3第四章存儲(chǔ)器管理存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)重要的組成部分雖然存儲(chǔ)器的容量不斷擴(kuò)大，但仍不能滿足要求，因此存儲(chǔ)器管理是操作系統(tǒng)的重要工作Page42023/2/3第四章存儲(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ǔ)器管理Page52023/2/3第四章存儲(chǔ)器管理存儲(chǔ)器的物理組織、多級(jí)存儲(chǔ)器存儲(chǔ)組織是指在存儲(chǔ)技術(shù)和CPU尋址技術(shù)許可的范圍內(nèi)組織合理的存儲(chǔ)結(jié)構(gòu)。其依據(jù)是訪問速度匹配關(guān)系、容量要求和價(jià)格?！凹拇嫫?內(nèi)存-外存”結(jié)構(gòu)“寄存器-緩存-內(nèi)存-外存”結(jié)構(gòu)；微機(jī)中的存儲(chǔ)層次組織：訪問速度越慢，容量越大，價(jià)格越便宜；最佳狀態(tài)應(yīng)是各層次的存儲(chǔ)器都處于均衡的繁忙狀態(tài)（如：緩存命中率正好使主存讀寫保持繁忙）；Page62023/2/3第四章存儲(chǔ)器管理快速緩存：DataCacheTLB(TranslationLookasideBuffer)內(nèi)存：DRAM,SDRAM等；外存：軟盤、硬盤、光盤、磁帶等；Page72023/2/3第四章存儲(chǔ)器管理主存儲(chǔ)器管理功能存儲(chǔ)分配和回收分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)地址變換和重定位可執(zhí)行文件生成中的鏈接技術(shù)程序加載(裝入)時(shí)的重定位技術(shù)進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)存儲(chǔ)共享和保護(hù)代碼和數(shù)據(jù)共享地址空間訪問權(quán)限（讀、寫、執(zhí)行）存儲(chǔ)器擴(kuò)充：存儲(chǔ)器的邏輯組織和物理組織；由應(yīng)用程序控制：覆蓋；由OS控制：交換（整個(gè)進(jìn)程空間），虛擬存儲(chǔ)的請(qǐng)求調(diào)入和預(yù)調(diào)入（部分進(jìn)程空間）Page82023/2/3第四章存儲(chǔ)器管理程序的裝入和鏈接

連續(xù)分配方式基本分頁存儲(chǔ)管理基本分段存儲(chǔ)管理虛擬存儲(chǔ)器的基本概念請(qǐng)求分頁存儲(chǔ)管理方式頁面置換算法請(qǐng)求分段存儲(chǔ)管理方式Page92023/2/3程序的裝入和鏈接程序的裝入程序的鏈接Page102023/2/3程序的裝入多道程序環(huán)境下，程序要運(yùn)行必須為之創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程的第一件事就是分配內(nèi)存源程序要運(yùn)行通常經(jīng)過編譯（compile）鏈接(link)裝入(load)等幾個(gè)步驟Page112023/2/34.1程序的裝入和鏈接圖4-1對(duì)用戶程序的處理步驟Page122023/2/34.1.1程序的裝入1.絕對(duì)裝入方式(AbsoluteLoadingMode)2.可重定位裝入方式(RelocationLoadingMode)3.動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DynamicRun-timeLoading)Page132023/2/3程序的裝入絕對(duì)裝入方式(AbsoluteLoadingMode)

事先確定了程序?qū)Ⅰv留在內(nèi)存的什么位置，即在內(nèi)存中的絕對(duì)地址裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，故不需對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改絕對(duì)地址的產(chǎn)生程序員直接賦予。不僅要求程序員熟悉內(nèi)存使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。通常在程序中采用符號(hào)地址，在編譯或匯編時(shí)，再將符號(hào)地址轉(zhuǎn)換為絕對(duì)地址。編譯或匯編時(shí)產(chǎn)生Page142023/2/3程序的裝入可重定位裝入方式(RelocationLoadingMode)

絕對(duì)裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置在多道程序環(huán)境下，不可能預(yù)知目標(biāo)模塊放在內(nèi)存中的地址，因此絕對(duì)裝入方式不適合在多道環(huán)境下使用程序中目標(biāo)模塊的地址通常從0開始，其他地址都是相對(duì)于0計(jì)算——相對(duì)地址把在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的地址修改過程稱為重定位，又因?yàn)榈刂纷儞Q通常是在裝入時(shí)一次完成的，以后不再改變，故稱為靜態(tài)重定位Page152023/2/3程序的裝入作業(yè)裝入內(nèi)存時(shí)的情況缺點(diǎn)：不斷的分配和回收，造成內(nèi)存中小空閑塊很多，總空閑空間量夠，但分配不了辦法：緊湊（移動(dòng)），但該裝入方法不支持Page162023/2/3LOAD1,25003655000250010000作業(yè)地址空間36510000110001250015000內(nèi)存空間LOAD1,1250036520000210002250025000內(nèi)存空間LOAD1,22500將程序加載到10000？程序的裝入將程序移動(dòng)到20000？Page172023/2/3程序的裝入動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DenamicRun-timeLoading)

可重定位方式不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，是在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此，裝入內(nèi)存后的所有地址都仍是相對(duì)地址Page182023/2/3程序的裝入和鏈接程序的裝入程序的鏈接Page192023/2/34.1程序的裝入和鏈接圖4-1對(duì)用戶程序的處理步驟Page202023/2/34.1.2程序的鏈接1.靜態(tài)鏈接方式(StaticLinking)2.裝入時(shí)動(dòng)態(tài)鏈接(Load-timeDynamicLinking)3.運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)Page212023/2/3程序的鏈接靜態(tài)鏈接方式(StaticLinking)

在程序運(yùn)行前，先將各目標(biāo)模塊及所需的庫函數(shù)鏈接成一個(gè)完整的裝配模塊，以后不再拆開在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題對(duì)相對(duì)地址進(jìn)行修改

變換外部調(diào)用符號(hào)Page222023/2/3程序的鏈接模塊

ACALLB；Return；0L－1模塊

BCALLC；Return；0M－1模塊

CReturn；0N－1(a)目標(biāo)模塊(外存)裝入前鏈接修改地址0模塊

AJSR“L”Return；L－1模塊

BJSR“L＋M”Return；LL＋M－1L＋ML＋M＋N－1模塊

CReturn；(b)裝入模塊（外存）Page232023/2/3程序的鏈接裝入時(shí)動(dòng)態(tài)鏈接(LoadtimeDynamicLinking)

將用戶的源程序編譯后所得的一組目標(biāo)模塊在裝入內(nèi)存時(shí)采用邊裝入邊鏈接的方式便于修改和更新便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享Page242023/2/3模塊

ACALLB；Return；0L－1模塊

BCALLC；Return；0M－1模塊

CReturn；0N－1外存0模塊

AJSR“L”Return；L－1模塊

BJSR“L＋M”Return；LL＋M－1L＋ML＋M＋N－1模塊

CReturn；內(nèi)存程序的鏈接裝入時(shí)鏈接修改地址Page252023/2/3程序的鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)

應(yīng)用程序在每次運(yùn)行的模塊可能不相同運(yùn)行時(shí)動(dòng)態(tài)鏈接方式將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行，即在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間Page262023/2/3模塊

ACALLB；Return；0L－1模塊

BCALLC；Return；0M－1模塊

CReturn；0N－1外存0模塊

AJSR“L”Return；L－1內(nèi)存執(zhí)行時(shí)鏈接修改地址Page272023/2/3第四章存儲(chǔ)器管理程序的裝入和鏈接

連續(xù)分配方式

基本分頁存儲(chǔ)管理基本分段存儲(chǔ)管理虛擬存儲(chǔ)器的基本概念請(qǐng)求分頁存儲(chǔ)管理方式頁面置換算法請(qǐng)求分段存儲(chǔ)管理方式Page282023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配對(duì)換（Swapping）Page292023/2/3單一連續(xù)分配連續(xù)分配方式為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間單一連續(xù)分配是最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中把內(nèi)存分為系統(tǒng)區(qū)：OS使用，通常放在內(nèi)存低址部分用戶區(qū)：用戶可使用的全部?jī)?nèi)存空間存儲(chǔ)器保護(hù)機(jī)構(gòu)不健全，易造成系統(tǒng)破壞優(yōu)點(diǎn)：易于管理缺點(diǎn)：對(duì)要求內(nèi)存空間少的程序，造成內(nèi)存浪費(fèi)；程序全部裝入，很少使用的程序部分也占用內(nèi)存Page302023/2/3單一連續(xù)分配用戶程序位于RAM中的操作系統(tǒng)0xFFF...0位于RAM中的操作系統(tǒng)用戶程序0ROM中的設(shè)備驅(qū)動(dòng)程序用戶程序位于RAM中的操作系統(tǒng)0單一連續(xù)區(qū)存儲(chǔ)管理Page312023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配對(duì)換（Swapping）Page322023/2/3固定分區(qū)分配最簡(jiǎn)單的可運(yùn)行多道程序的存儲(chǔ)管理方式內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只裝入一道作業(yè)劃分分區(qū)的方法分區(qū)大小相等：即使所有的內(nèi)存分區(qū)大小相等太大：浪費(fèi)太?。翰粔蛴梅謪^(qū)大小不等：劃分為多個(gè)大、中、小搭配的分區(qū)根據(jù)程序大小決定所使用的分區(qū)大班在大教室、小班在小教室Page332023/2/3內(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)行！Page342023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配對(duì)換（Swapping）Page352023/2/3動(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)對(duì)空閑分區(qū)的分配和鏈接Page362023/2/3動(dòng)態(tài)分區(qū)分配分區(qū)分配算法

首次適應(yīng)算法FF

循環(huán)首次適應(yīng)算法最佳適應(yīng)算法最差適應(yīng)算法Page372023/2/3動(dòng)態(tài)分區(qū)分配分區(qū)分配算法

首次適應(yīng)算法FF

空閑分區(qū)鏈以地址遞增順序鏈接分配時(shí)從鏈?zhǔn)组_始查找，找到一個(gè)大小可滿足的空閑分區(qū)，劃出一塊給請(qǐng)求者優(yōu)點(diǎn)：簡(jiǎn)單；優(yōu)先利用低地址空閑區(qū)，保留高地址大空閑區(qū)缺點(diǎn)：會(huì)造成在低地址部分很多難以利用的小空閑分區(qū)，查找效率低循環(huán)首次適應(yīng)算法每次分配時(shí)從上一次找到空閑分區(qū)的下一個(gè)空閑區(qū)開始查找優(yōu)點(diǎn)：減少查找空閑分區(qū)開銷，空閑分區(qū)分布更均勻缺點(diǎn)：缺乏大的空閑區(qū)Page382023/2/3動(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)，最佳最差（每次分配后剩下小碎片，難再分，不得不經(jīng)常壓縮內(nèi)存，反而浪費(fèi)CPU）Page392023/2/3動(dòng)態(tài)分區(qū)分配分區(qū)分配操作分配內(nèi)存從頭開始查表檢索完否？m.size＞u.size?m.size－u.size≤size?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YNNYYN解決碎片問題Page402023/2/3動(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ū)鄰接Page412023/2/3動(dòng)態(tài)分區(qū)分配空閑區(qū)回收區(qū)回收區(qū)空閑區(qū)空閑區(qū)回收區(qū)空閑區(qū)回收區(qū)情況1情況2情況3情況4Page422023/2/32)回收內(nèi)存回收區(qū)F1F2回收區(qū)F2回收區(qū)F1回收區(qū)回收區(qū)Page432023/2/3動(dòng)態(tài)分區(qū)分配分區(qū)式存儲(chǔ)管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：便于動(dòng)態(tài)申請(qǐng)內(nèi)存便于共享內(nèi)存便于動(dòng)態(tài)鏈接缺點(diǎn)： 碎片問題(外碎片)，要求連續(xù)的內(nèi)存空間，內(nèi)存利用率不高，受實(shí)際內(nèi)存容量限制Page442023/2/3動(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ī)Page452023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配對(duì)換（Swapping）Page462023/2/34.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入80kb用戶程序9用戶程序6用戶程序3用戶程序1操作系統(tǒng)緊湊Page472023/2/3可重定位分區(qū)分配動(dòng)態(tài)重定位的引入連續(xù)分配存在的問題

必須有足夠大的連續(xù)空間才能分配解決方法：“拼接”或“緊湊”的引入Page482023/2/3可重定位分區(qū)分配動(dòng)態(tài)重定位的實(shí)現(xiàn)作業(yè)裝入內(nèi)存后的所有地址仍是相對(duì)地址，將相對(duì)地址轉(zhuǎn)換成物理地址的工作在指令執(zhí)行時(shí)進(jìn)行需要有硬件地址變換機(jī)構(gòu)的支持Page492023/2/33.動(dòng)態(tài)重定位分區(qū)分配算法

動(dòng)態(tài)重定位分區(qū)分配算法，與動(dòng)態(tài)分區(qū)分配算法基本上相同；差別僅在于：在這種分配算法中，增加了“緊湊”功能，通常是在找不到足夠大的空閑分區(qū)來滿足用戶需求時(shí)，進(jìn)行緊湊。圖4-10示出了動(dòng)態(tài)重定位分區(qū)分配算法框圖。Page502023/2/3可重定位分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配算法在一個(gè)分區(qū)釋放后立即移動(dòng)當(dāng)請(qǐng)求得不到滿足時(shí)再移動(dòng)Page512023/2/3可重定位分區(qū)分配可重定位分區(qū)的優(yōu)缺點(diǎn)優(yōu)點(diǎn):解決了可變分區(qū)分配所引入的“外零頭”問題。消除內(nèi)存碎片，提高內(nèi)存利用率。缺點(diǎn):提高硬件成本，緊湊時(shí)花費(fèi)ＣＰＵ時(shí)間。Page522023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配對(duì)換（Swapping）Page532023/2/34.2.5對(duì)換(Swapping)1.對(duì)換的引入

對(duì)換（也稱交換）技術(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)。Page542023/2/3對(duì)換（Swapping）對(duì)換的引入

所謂“對(duì)換”，是指把內(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)存。對(duì)換是提高內(nèi)存利用率的有效措施如果對(duì)換是以整個(gè)進(jìn)程為單位，稱為“整體對(duì)換”或“進(jìn)程對(duì)換”如果對(duì)換是以“頁”或“段”為單位進(jìn)行的，則稱為“頁面對(duì)換”或“分段對(duì)換”，又統(tǒng)稱為“部分對(duì)換”Page552023/2/34.2.5對(duì)換(Swapping)1.對(duì)換的引入

對(duì)換是以整個(gè)進(jìn)程為單位，便稱之為“整體對(duì)換”或“進(jìn)程對(duì)換”，解決內(nèi)存緊張問題；對(duì)換是以“頁”或“段”為單位，則分別稱之為“頁面對(duì)換”或“分段對(duì)換”，又統(tǒng)稱為“部分對(duì)換”；為了實(shí)現(xiàn)進(jìn)程對(duì)換，系統(tǒng)必須能實(shí)現(xiàn)以下三方面的功能：（1）對(duì)換空間的管理；（2）進(jìn)程的換出；（3）進(jìn)程的換入。Page562023/2/3對(duì)換（Swapping）對(duì)換空間的管理外存中對(duì)換區(qū)主要存放從內(nèi)存中換出的進(jìn)程，對(duì)換空間管理的主要目標(biāo)是提高進(jìn)程換入和換出的速度對(duì)換區(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)，即對(duì)換區(qū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)對(duì)換區(qū)的分配采用連續(xù)分配方式，分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法Page572023/2/32.對(duì)換空間的管理

由于對(duì)對(duì)換區(qū)的分配，是采用連續(xù)分配方式，對(duì)換區(qū)的回收操作也可分為下述四種情況，即：（1）回收區(qū)與插入點(diǎn)的前一分區(qū)F1相鄰接；（2）回收區(qū)與插入點(diǎn)的后一分區(qū)F2相鄰接；（3）回收區(qū)還同時(shí)與F1和F2二個(gè)分區(qū)相鄰接；（4）回收區(qū)的前、后沒有與之相鄰接的空閑分區(qū)。對(duì)這幾種情況的處理方法也與動(dòng)態(tài)分區(qū)分配式的方法相同?；厥諈^(qū)F1F2回收區(qū)F2回收區(qū)F1回收區(qū)回收區(qū)Page582023/2/3對(duì)換（Swapping）進(jìn)程的換出與換入進(jìn)程的換出系統(tǒng)先選擇處于“阻塞”狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換區(qū)上。若傳送未出現(xiàn)錯(cuò)誤，便回收其所占用的內(nèi)存空間，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改進(jìn)程的換入系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止Page592023/2/3可重定位分區(qū)分配可重定位分區(qū)的優(yōu)缺點(diǎn)優(yōu)點(diǎn):解決了可變分區(qū)分配所引入的“外零頭”問題。消除內(nèi)存碎片，提高內(nèi)存利用率。缺點(diǎn):提高硬件成本，緊湊時(shí)花費(fèi)ＣＰＵ時(shí)間。Page602023/2/3可重定位分區(qū)分配多重分區(qū)即一個(gè)程序可以占據(jù)主存中不連續(xù)的多個(gè)分區(qū)——可以解決碎片問題支持結(jié)構(gòu)化程序設(shè)計(jì)，操作系統(tǒng)往往把一道作業(yè)分成若干片段如子程序、主程序、數(shù)據(jù)組等。需要硬件支持（多對(duì)界地址寄存器，重定位寄存器）管理復(fù)雜Page612023/2/3可重定位分區(qū)分配多重分區(qū)

Page622023/2/3分區(qū)的保護(hù)

為了防止一道作業(yè)有意或無意地破壞操作系統(tǒng)或其它作業(yè)。一般說來，沒有硬件支持，實(shí)現(xiàn)有效的存儲(chǔ)保護(hù)是困難的。通常采取：界限寄存器方式保護(hù)鍵方式兩種措施，或二者兼而有之?？芍囟ㄎ环謪^(qū)分配Page632023/2/3保護(hù)過程——防止地址越界一般由硬件提供一對(duì)寄存器：基址寄存器：存放起始地址限長(zhǎng)寄存器：存放長(zhǎng)度（上界寄存器/下界寄存器）可重定位分區(qū)分配Page642023/2/3界限寄存器保護(hù)60K>訪問地址

>=124K則產(chǎn)生訪問地址界中斷可重定位分區(qū)分配Page652023/2/3基址、限長(zhǎng)寄存器保護(hù)相對(duì)地址

>限長(zhǎng)寄存器的值則產(chǎn)生訪問地址界中斷可重定位分區(qū)分配Page662023/2/3防止操作越權(quán)對(duì)于允許多個(gè)進(jìn)程共享的存儲(chǔ)區(qū)域，每個(gè)進(jìn)程都有自己的訪問權(quán)限。如果一個(gè)進(jìn)程對(duì)共享區(qū)域的訪問違反了權(quán)限規(guī)定，則發(fā)生操作越權(quán)即讀寫保護(hù)可重定位分區(qū)分配Page672023/2/3保護(hù)鍵方式可重定位分區(qū)分配Page682023/2/34.3基本分頁存儲(chǔ)管理方式

連續(xù)分配方式會(huì)形成許多“碎片”，通過“緊湊”方法將碎片拼接成可用的大塊空間，但須為此付出很大開銷。根據(jù)離散分配時(shí)所用基本單位的不同，又可把離散分配方式分以下三種：

1、分頁存儲(chǔ)管理

2、分段存儲(chǔ)管理

3、段頁式存儲(chǔ)管理

Page692023/2/3存儲(chǔ)器管理連續(xù)分配方式離散分配方式分頁存儲(chǔ)管理分段存儲(chǔ)管理基本分頁存儲(chǔ)管理請(qǐng)求分頁存儲(chǔ)管理基本分段存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理基本分頁存儲(chǔ)管理基本分段存儲(chǔ)管理請(qǐng)求分頁存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理段頁式存儲(chǔ)管理虛擬存儲(chǔ)器頁面置換算法Page702023/2/3第四章存儲(chǔ)器管理程序的裝入和鏈接

連續(xù)分配方式

基本分頁存儲(chǔ)管理

基本分段存儲(chǔ)管理虛擬存儲(chǔ)器的基本概念請(qǐng)求分頁存儲(chǔ)管理方式頁面置換算法請(qǐng)求分段存儲(chǔ)管理方式Page712023/2/34.3基本分頁存儲(chǔ)管理方式

在分頁存儲(chǔ)管理的方式中，如果不具備頁面對(duì)換功能，則稱為基本的（純）分頁管理方式，它不具有支持實(shí)現(xiàn)虛擬存儲(chǔ)器的功能，它要求把每個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。Page722023/2/3基本分頁存儲(chǔ)管理頁面與頁表地址變換機(jī)構(gòu)兩級(jí)和多級(jí)頁表Page732023/2/3離散分配方式連續(xù)分配方式要求為一個(gè)進(jìn)程分配連續(xù)的內(nèi)存空間，會(huì)形成許多“碎片”，盡管采用“緊湊”技術(shù)可以解決這個(gè)問題，但要為移動(dòng)大量信息花去不少的處理機(jī)時(shí)間，代價(jià)較高如果允許一個(gè)進(jìn)程直接分散地裝入到許多不相鄰接的分區(qū)中，稱為離散分配方式離散分配方式有分頁存儲(chǔ)管理方式和分段存儲(chǔ)管理方式分頁：把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁或虛頁。從0開始編制頁號(hào)，頁內(nèi)地址是相對(duì)于0編址。Page742023/2/3頁面與頁表頁面頁面和物理塊頁面：將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁，并加以編號(hào)，從0開始編制頁號(hào)，頁內(nèi)地址是相對(duì)于0編址。物理塊：內(nèi)存按頁的大小劃分為大小相等的區(qū)域，稱為物理塊（物理頁面，頁框(frame)，幀），同樣加以編號(hào)，如0＃塊、1＃塊等等在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”Page752023/2/3頁面與頁表頁面頁面大小頁面的大小應(yīng)選擇的適中，且頁面大小應(yīng)是2的冪，通常為512B~8KB頁面若太小雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率，但也會(huì)使每個(gè)進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長(zhǎng)，占用大量?jī)?nèi)存；此外，還會(huì)降低頁面換進(jìn)換出的效率如果選擇的頁面較大雖然可以減少頁表的長(zhǎng)度，提高頁面換進(jìn)換出的速度，但卻又會(huì)使頁內(nèi)碎片增大。Page762023/2/3

對(duì)某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁面的大小為L(zhǎng)，則頁號(hào)P和頁內(nèi)地址d可按下式求得：

例如：其系統(tǒng)的頁面大小為1KB，設(shè)A=2170B，則由下式可以求得P=，d=。2.地址結(jié)構(gòu)分頁地址中的地址結(jié)構(gòu)如下：3112110頁內(nèi)地址212=4*2104KB220=210*2101M21222048-122Page772023/2/3頁面與頁表例：系統(tǒng)頁面大小為1KB，邏輯地址為2170，求頁號(hào)與頁內(nèi)偏移量頁號(hào)P=INT[2170/1024]=2頁內(nèi)偏移量d=2170mod1024=122第0頁0~1023第1頁1024~2047第2頁2048~3071表示為(2,122)Page782023/2/3頁面與頁表主存分配把用戶程序的任一頁分配到內(nèi)存中的任一物理塊，從而實(shí)現(xiàn)非連續(xù)的內(nèi)存分配。問題如何管理、如何進(jìn)行地址變換。Page792023/2/3頁面與頁表頁表分頁系統(tǒng)中，將進(jìn)程的每一頁離散地存儲(chǔ)在內(nèi)存的任一物理塊中，為每個(gè)進(jìn)程建立一張頁面映像表，簡(jiǎn)稱頁表

作用：實(shí)現(xiàn)頁號(hào)到物理塊號(hào)的映射Page802023/2/3頁面與頁表頁表列出了用戶程序的邏輯地址與其在主存中的物理地址間的對(duì)應(yīng)關(guān)系。一個(gè)頁表中包含若干個(gè)表目，表目的自然序號(hào)對(duì)應(yīng)于用戶程序中的頁號(hào)，表目中的塊號(hào)是該頁對(duì)應(yīng)的物理塊號(hào)。頁表的每一個(gè)表目除了包含指向頁框的指針外，還包括一個(gè)存取控制字段。表目也稱為頁描述子。Page812023/2/3頁面與頁表進(jìn)程A頁表00頁號(hào)塊號(hào)1124354859…………程序A00程序A11程序B02程序B13程序A24程序A35程序B26程序B37程序A48內(nèi)存程序A59程序A0頁1頁2頁3頁4頁5頁n頁程序B0頁1頁2頁3頁4頁5頁m頁進(jìn)程B頁表02頁號(hào)塊號(hào)132637…………Page822023/2/3基本分頁存儲(chǔ)管理頁面與頁表地址變換機(jī)構(gòu)兩級(jí)和多級(jí)頁表Page832023/2/3地址變換機(jī)構(gòu)基本地址變換機(jī)構(gòu)實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，將邏輯地址中的頁號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)，通過頁表來完成頁表的實(shí)現(xiàn)寄存器：變換速度快、成本高，適應(yīng)小型系統(tǒng)。頁表駐留在內(nèi)存：速度較低、成本低，適應(yīng)大系統(tǒng)。頁表大多駐留在內(nèi)存中，在系統(tǒng)中設(shè)置頁表寄存器PTR(Page–TableRegister)，在其中存放頁表在內(nèi)存中的始址和頁表的長(zhǎng)度進(jìn)程未執(zhí)行時(shí)，頁表的始址和頁表長(zhǎng)度存放在本進(jìn)程的PCB中，當(dāng)調(diào)度程序調(diào)度到某進(jìn)程時(shí)，才將這兩個(gè)數(shù)據(jù)裝入頁表寄存器Page842023/2/3地址變換機(jī)構(gòu)地址結(jié)構(gòu)例如：32位地址，0~11為偏移量，12~31為頁號(hào)，最大可以有1M（220）頁，每頁4KB（212）。3112110Page852023/2/34.3.2地址變換機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)

每個(gè)進(jìn)程對(duì)應(yīng)一頁表，其信息（如長(zhǎng)度、始址）放在PCB中，執(zhí)行時(shí)將其首地址裝入頁表寄存器。當(dāng)進(jìn)程要訪問某個(gè)進(jìn)程邏輯地址中的數(shù)據(jù)時(shí)，分為頁號(hào)和頁內(nèi)地址兩部分；如果頁號(hào)大于或等于頁表長(zhǎng)度，則表示本次所訪問的地址已經(jīng)超越進(jìn)程的地址空間。Page862023/2/3地址變換機(jī)構(gòu)Page872023/2/3地址變換機(jī)構(gòu)地址變換過程指令LOAD1,2500的地址變換過程（塊大小為1024B）Page882023/2/3地址變換過程把虛擬地址2500轉(zhuǎn)換成頁號(hào)P=2，位移量W=452；如果頁號(hào)2大于頁表大小，則中斷；否則繼續(xù)；頁號(hào)2與頁表起址1000運(yùn)算（1000+2*20，設(shè)頁描述子大小為20）得到頁描述子地址為1040；從頁描述子中讀取塊號(hào)8；根據(jù)頁描述子的“存取控制”判斷該指令是否被允許訪問內(nèi)存，如果不允許，則中斷；否則繼續(xù)；塊號(hào)8與位移量452運(yùn)算（8*1024+452=9644，1024為頁面大小）得到物理地址9644；執(zhí)行LOAD操作。地址變換機(jī)構(gòu)Page892023/2/32.具有快表的地址變換機(jī)構(gòu)

由于頁表是存放在內(nèi)存中的，這使CPU每次要存取一個(gè)數(shù)據(jù)時(shí)，都要兩次訪問內(nèi)存。

第一次是訪問內(nèi)存中的頁表，從中找到該頁的物理塊號(hào)，將此塊號(hào)與頁內(nèi)偏移量W拼接以形成物理地址。

第二次訪問內(nèi)存時(shí)，才是從第一步所得地址中獲得所需數(shù)據(jù)（或向此地址中寫入數(shù)據(jù)），并將此頁號(hào)與高速緩存中的所有頁碼進(jìn)行比較。Page902023/2/3地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)由于頁表是存放在內(nèi)存中，因此每次CPU存取一個(gè)數(shù)據(jù)要兩次訪問內(nèi)存為提高地址變換速度，在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查詢能力的高速緩沖寄存器，又稱為“聯(lián)想寄存器”（AssociativeMemory）或“快表”，用以存放當(dāng)前訪問的那些頁表項(xiàng)快表通?？纱娣?6-512個(gè)表項(xiàng)，如果設(shè)計(jì)得當(dāng)，命中率可達(dá)90％以上Page912023/2/3地址變換機(jī)構(gòu)頁表寄存器頁表始址頁表長(zhǎng)度＞頁號(hào)頁內(nèi)地址＋邏輯地址L越界中斷塊號(hào)b頁表頁號(hào)頁號(hào)輸入寄存器塊號(hào)bb快表d物理地址具有快表的地址變換機(jī)構(gòu)Page922023/2/3

例：有一頁式系統(tǒng)，其頁表存放在主存中：①如果對(duì)主存的一次存取需要1.5μs,試問實(shí)現(xiàn)一次頁面訪問的存取時(shí)間是多少?②如果系統(tǒng)加有快表,平均命中率為85%,當(dāng)頁表項(xiàng)在快表中時(shí),其查找時(shí)間忽略為0,試問此時(shí)的存取時(shí)間是多少?Page932023/2/3答：若頁表存放在主存中，則要實(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)Page942023/2/3基本分頁存儲(chǔ)管理頁面與頁表地址變換機(jī)構(gòu)兩級(jí)和多級(jí)頁表Page952023/2/3兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表

現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間例如，對(duì)于一個(gè)具有32位邏輯地址空間的分頁系統(tǒng)，若規(guī)定頁面大小為4KB即212B，則在每個(gè)進(jìn)程頁表中的頁表項(xiàng)可達(dá)1M(220)個(gè)之多。若每個(gè)表項(xiàng)占用4