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

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

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

掌握理解分頁和分段存儲管理方式

理解虛擬存儲器的基本概念

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

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

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

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

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

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

連續(xù)分配方式基本分頁存儲管理基本分段存儲管理虛擬存儲器的基本概念請求分頁存儲管理方式頁面置換算法請求分段存儲管理方式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)等幾個步驟Page112023/2/34.1程序的裝入和鏈接圖4-1對用戶程序的處理步驟Page122023/2/34.1.1程序的裝入1.絕對裝入方式(AbsoluteLoadingMode)2.可重定位裝入方式(RelocationLoadingMode)3.動態(tài)運(yùn)行時裝入方式(DynamicRun-timeLoading)Page132023/2/3程序的裝入絕對裝入方式(AbsoluteLoadingMode)

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

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

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

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

變換外部調(dià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程序的鏈接裝入時動態(tài)鏈接(LoadtimeDynamicLinking)

將用戶的源程序編譯后所得的一組目標(biāo)模塊在裝入內(nèi)存時采用邊裝入邊鏈接的方式便于修改和更新便于實(shí)現(xiàn)對目標(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)存程序的鏈接裝入時鏈接修改地址Page252023/2/3程序的鏈接運(yùn)行時動態(tài)鏈接(Run-timeDynamicLinking)

應(yīng)用程序在每次運(yùn)行的模塊可能不相同運(yùn)行時動態(tài)鏈接方式將對某些模塊的鏈接推遲到執(zhí)行時才進(jìn)行，即在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被調(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í)行時鏈接修改地址Page272023/2/3第四章存儲器管理程序的裝入和鏈接

連續(xù)分配方式

基本分頁存儲管理基本分段存儲管理虛擬存儲器的基本概念請求分頁存儲管理方式頁面置換算法請求分段存儲管理方式Page282023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配可重定位分區(qū)分配對換（Swapping）Page292023/2/3單一連續(xù)分配連續(xù)分配方式為一個用戶程序分配一個連續(xù)的內(nèi)存空間單一連續(xù)分配是最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中把內(nèi)存分為系統(tǒng)區(qū)：OS使用，通常放在內(nèi)存低址部分用戶區(qū)：用戶可使用的全部內(nèi)存空間存儲器保護(hù)機(jī)構(gòu)不健全，易造成系統(tǒng)破壞優(yōu)點(diǎn)：易于管理缺點(diǎn)：對要求內(nèi)存空間少的程序，造成內(nèi)存浪費(fèi)；程序全部裝入，很少使用的程序部分也占用內(nèi)存Page302023/2/3單一連續(xù)分配用戶程序位于RAM中的操作系統(tǒng)0xFFF...0位于RAM中的操作系統(tǒng)用戶程序0ROM中的設(shè)備驅(qū)動程序用戶程序位于RAM中的操作系統(tǒng)0單一連續(xù)區(qū)存儲管理Page312023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配可重定位分區(qū)分配對換（Swapping）Page322023/2/3固定分區(qū)分配最簡單的可運(yùn)行多道程序的存儲管理方式內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè)劃分分區(qū)的方法分區(qū)大小相等：即使所有的內(nèi)存分區(qū)大小相等太大：浪費(fèi)太?。翰粔蛴梅謪^(qū)大小不等：劃分為多個大、中、小搭配的分區(qū)根據(jù)程序大小決定所使用的分區(qū)大班在大教室、小班在小教室Page332023/2/3內(nèi)存分配分區(qū)的信息根據(jù)分區(qū)使用表管理固定分區(qū)分配20使用界地址寄存器采用靜態(tài)重定位問題：并發(fā)進(jìn)程數(shù)受分區(qū)個數(shù)的制約！出現(xiàn)：有內(nèi)存卻不能運(yùn)行程序或大進(jìn)程無法運(yùn)行！Page342023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配可重定位分區(qū)分配對換（Swapping）Page352023/2/3動態(tài)分區(qū)分配根據(jù)進(jìn)程的實(shí)際需要，動態(tài)地為之分配內(nèi)存空間分配中數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表記錄每個空閑分區(qū)的情況空閑分區(qū)鏈實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接Page362023/2/3動態(tài)分區(qū)分配分區(qū)分配算法

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

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

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

空閑分區(qū)鏈以地址遞增順序鏈接分配時從鏈?zhǔn)组_始查找，找到一個大小可滿足的空閑分區(qū)，劃出一塊給請求者優(yōu)點(diǎn)：簡單；優(yōu)先利用低地址空閑區(qū)，保留高地址大空閑區(qū)缺點(diǎn)：會造成在低地址部分很多難以利用的小空閑分區(qū)，查找效率低循環(huán)首次適應(yīng)算法每次分配時從上一次找到空閑分區(qū)的下一個空閑區(qū)開始查找優(yōu)點(diǎn)：減少查找空閑分區(qū)開銷，空閑分區(qū)分布更均勻缺點(diǎn)：缺乏大的空閑區(qū)Page382023/2/3動態(tài)分區(qū)分配最佳適應(yīng)算法空閑區(qū)按容量由小到大排序每次分配時，把能滿足要求、又是最小的分區(qū)分配給作業(yè)優(yōu)點(diǎn)：不缺乏大的空閑區(qū)缺點(diǎn)：會在存儲器中留直許多難以利用的小分區(qū)——“零頭（或碎片）”；查找效率低最差適應(yīng)算法空閑區(qū)按容量由大到小排序每次分配時，把能滿足要求、又是最大的分區(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動態(tài)分區(qū)分配分區(qū)分配操作分配內(nèi)存從頭開始查表檢索完否？m.size＞u.size?m.size－u.size≤size?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個表項(xiàng)將該分區(qū)從鏈中移出YNNYYN解決碎片問題Page402023/2/3動態(tài)分區(qū)分配分區(qū)分配操作回收內(nèi)存進(jìn)程運(yùn)行結(jié)束釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首地址，把它插入到空閑鏈表中。根據(jù)回收區(qū)的位置，有四種情況需處理：回收區(qū)與插入點(diǎn)的前一個空閑分區(qū)相鄰接回收區(qū)與插入點(diǎn)的后一個空閑分區(qū)相鄰接回收區(qū)同時與插入點(diǎn)的前、后兩個分區(qū)相鄰接回收區(qū)不與任何空閑區(qū)鄰接Page412023/2/3動態(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動態(tài)分區(qū)分配分區(qū)式存儲管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：便于動態(tài)申請內(nèi)存便于共享內(nèi)存便于動態(tài)鏈接缺點(diǎn)： 碎片問題(外碎片)，要求連續(xù)的內(nèi)存空間，內(nèi)存利用率不高，受實(shí)際內(nèi)存容量限制Page442023/2/3動態(tài)分區(qū)分配碎片問題經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片造成存儲資源的浪費(fèi)碎片問題的解決緊湊技術(shù)：通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域（緊縮技術(shù)，緊致技術(shù)，浮動技術(shù)，搬家技術(shù)）問題：開銷大；移動時機(jī)Page452023/2/3連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配可重定位分區(qū)分配對換（Swapping）Page462023/2/34.2.4可重定位分區(qū)分配1.動態(tài)重定位的引入80kb用戶程序9用戶程序6用戶程序3用戶程序1操作系統(tǒng)緊湊Page472023/2/3可重定位分區(qū)分配動態(tài)重定位的引入連續(xù)分配存在的問題

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

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

對換（也稱交換）技術(shù)，最早用在單用戶系統(tǒng)，在內(nèi)存中僅駐留一道用戶作業(yè)。所有其它作業(yè)都駐留在外存的后備隊(duì)列上，只調(diào)入一個作業(yè)進(jìn)入內(nèi)存運(yùn)行；此作業(yè)的時間片用完時，該作業(yè)調(diào)至外存，再將后備隊(duì)列上的另一個作業(yè)調(diào)入內(nèi)存；也讓它運(yùn)行一個時間片的時間，然后又將它調(diào)出，再調(diào)下一個作業(yè)進(jìn)入內(nèi)存。因?yàn)槠湫侍?，其CPU大約有一半的時間，都處于空閑狀態(tài)。Page542023/2/3對換（Swapping）對換的引入

所謂“對換”，是指把內(nèi)存中暫時不能運(yùn)行的進(jìn)程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施如果對換是以整個進(jìn)程為單位，稱為“整體對換”或“進(jìn)程對換”如果對換是以“頁”或“段”為單位進(jìn)行的，則稱為“頁面對換”或“分段對換”，又統(tǒng)稱為“部分對換”Page552023/2/34.2.5對換(Swapping)1.對換的引入

對換是以整個進(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)程的換入。Page562023/2/3對換（Swapping）對換空間的管理外存中對換區(qū)主要存放從內(nèi)存中換出的進(jìn)程，對換空間管理的主要目標(biāo)是提高進(jìn)程換入和換出的速度對換區(qū)中空閑盤塊的管理：在系統(tǒng)中配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，記錄外存的使用情況。形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應(yīng)包含兩項(xiàng)，即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)對換區(qū)的分配采用連續(xù)分配方式，分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法Page572023/2/32.對換空間的管理

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

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

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

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

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

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

1、分頁存儲管理

2、分段存儲管理

3、段頁式存儲管理

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

連續(xù)分配方式

基本分頁存儲管理

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

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

對某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號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，求頁號與頁內(nèi)偏移量頁號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)程的每一頁離散地存儲在內(nèi)存的任一物理塊中，為每個進(jìn)程建立一張頁面映像表，簡稱頁表

作用：實(shí)現(xiàn)頁號到物理塊號的映射Page802023/2/3頁面與頁表頁表列出了用戶程序的邏輯地址與其在主存中的物理地址間的對應(yīng)關(guān)系。一個頁表中包含若干個表目，表目的自然序號對應(yīng)于用戶程序中的頁號，表目中的塊號是該頁對應(yīng)的物理塊號。頁表的每一個表目除了包含指向頁框的指針外，還包括一個存取控制字段。表目也稱為頁描述子。Page812023/2/3頁面與頁表進(jìn)程A頁表00頁號塊號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頁號塊號132637…………Page822023/2/3基本分頁存儲管理頁面與頁表地址變換機(jī)構(gòu)兩級和多級頁表Page832023/2/3地址變換機(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–TableRegister)，在其中存放頁表在內(nèi)存中的始址和頁表的長度進(jìn)程未執(zhí)行時，頁表的始址和頁表長度存放在本進(jìn)程的PCB中，當(dāng)調(diào)度程序調(diào)度到某進(jìn)程時，才將這兩個數(shù)據(jù)裝入頁表寄存器Page842023/2/3地址變換機(jī)構(gòu)地址結(jié)構(gòu)例如：32位地址，0~11為偏移量，12~31為頁號，最大可以有1M（220）頁，每頁4KB（212）。3112110Page852023/2/34.3.2地址變換機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)

每個進(jìn)程對應(yīng)一頁表，其信息（如長度、始址）放在PCB中，執(zhí)行時將其首地址裝入頁表寄存器。當(dāng)進(jìn)程要訪問某個進(jìn)程邏輯地址中的數(shù)據(jù)時，分為頁號和頁內(nèi)地址兩部分；如果頁號大于或等于頁表長度，則表示本次所訪問的地址已經(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)換成頁號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)Page892023/2/32.具有快表的地址變換機(jī)構(gòu)

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

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

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

例：有一頁式系統(tǒng)，其頁表存放在主存中：①如果對主存的一次存取需要1.5μs,試問實(shí)現(xiàn)一次頁面訪問的存取時間是多少?②如果系統(tǒng)加有快表,平均命中率為85%,當(dāng)頁表項(xiàng)在快表中時,其查找時間忽略為0,試問此時的存取時間是多少?Page932023/2/3答：若頁表存放在主存中，則要實(shí)現(xiàn)一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁面數(shù)據(jù)?！鲰摫碓谥鞔娴拇嫒≡L問時間

=1.5*2=3(μs)■增加快表后的存取訪問時間

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)Page942023/2/3基本分頁存儲管理頁面與頁表地址變換機(jī)構(gòu)兩級和多級頁表Page952023/2/3兩級和多級頁表兩級和多級頁表

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