計(jì)算機(jī)操作系統(tǒng)第四章-存儲(chǔ)器管理(1-2)要點(diǎn)課件

第四章存儲(chǔ)器管理4.1存儲(chǔ)器的層次結(jié)構(gòu)

4.2程序的裝入和鏈接

4.3連續(xù)分配方式4.4基本分頁(yè)存儲(chǔ)管理方式4.5基本分段存儲(chǔ)管理方式4.6虛擬存儲(chǔ)器的基本概念4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.8頁(yè)面置換算法4.9請(qǐng)求分段存儲(chǔ)管理方式

第四章存儲(chǔ)器管理4.1存儲(chǔ)器的層次結(jié)構(gòu)4.1存儲(chǔ)器的層次結(jié)構(gòu)寄存器、高速緩存、主存儲(chǔ)器和磁盤緩存均屬于操作系統(tǒng)存儲(chǔ)管理的管轄范疇，掉電后它們存儲(chǔ)的信息不再存在。在主存中4.1存儲(chǔ)器的層次結(jié)構(gòu)寄存器、高速緩存、主存儲(chǔ)器和磁盤緩存儲(chǔ)器管理：指內(nèi)存的管理，外存管理在文件部分講述；單道程序系統(tǒng)：內(nèi)存被劃分成兩部分：一部分供OS使用，一部分供當(dāng)前正在執(zhí)行的程序使用。多道程序系統(tǒng)：存儲(chǔ)器的用戶部分必須進(jìn)一步地細(xì)分，以適應(yīng)多個(gè)進(jìn)程的要求。細(xì)分的任務(wù)由操作系統(tǒng)動(dòng)態(tài)實(shí)現(xiàn)，這就是存儲(chǔ)器管理。存儲(chǔ)器管理的目的：一是方便用戶使用，二是提高存儲(chǔ)器的利用率。

基本概念補(bǔ)充存儲(chǔ)器管理：指內(nèi)存的管理，外存管理在文件部分講述；基本概1、存儲(chǔ)器管理功能主存的分配和回收：系統(tǒng)應(yīng)能記住每個(gè)存儲(chǔ)區(qū)的狀態(tài)；實(shí)施存儲(chǔ)器的分配；回收系統(tǒng)或用戶釋放的存儲(chǔ)區(qū)。提高主存利用率：使多道程序能動(dòng)態(tài)地共享主存，最好能共享主存中的信息。[地址轉(zhuǎn)換或重定位]主存保護(hù)：保證進(jìn)入主存的各道作業(yè)都在自己的存儲(chǔ)空間內(nèi)運(yùn)行，互不干擾。由硬件和軟件配合完成。主存擴(kuò)充：借助于虛擬存儲(chǔ)技術(shù)，為用戶提供比主存空間大的地址空間。1、存儲(chǔ)器管理功能主存的分配和回收：系統(tǒng)應(yīng)能記住每個(gè)存儲(chǔ)區(qū)的內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這種編號(hào)稱為內(nèi)存地址（或稱為物理地址，絕對(duì)地址）。內(nèi)存地址的集合稱為內(nèi)存空間（或物理地址空間）。例如，我們常說(shuō)內(nèi)存為：512MB要求用戶用內(nèi)存地址編程是非常困難的，尤其是在多道程序設(shè)計(jì)的環(huán)境中（不知道）。2、地址映射(地址重定位)內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這種編號(hào)稱為內(nèi)存地址（或稱為用戶編程所用的地址稱為邏輯地址（或程序地址，或虛地址），由邏輯地址組成的空間稱為邏輯地址空間（或程序地址空間）。我們把用戶程序裝入內(nèi)存時(shí)，或在程序執(zhí)行時(shí)，對(duì)有關(guān)指令或數(shù)據(jù)地址的修改稱為從程序地址到內(nèi)存地址的地址映射，或稱為地址重定位。用戶編程所用的地址稱為邏輯地址（或程序地址，或虛地址），由邏地址映射LoadA12003456

。。1200物理地址空間LoadAdata1data13456源程序（名空間）LoadA20034560100200編譯連接邏輯地址空間BR=10001100地址映射1200物理地址空間源程序（名空間）0100200編地址映射的方式靜態(tài)地址映射：

1）程序被裝入內(nèi)存時(shí)由操作系統(tǒng)的連接裝入程序完成程序的邏輯地址到內(nèi)存地址的轉(zhuǎn)換；

2）地址轉(zhuǎn)換工作是在程序執(zhí)行前由裝入程序集中一次完成。假定程序裝入內(nèi)存的首地址為BR，程序地址為VR，內(nèi)存地址為MR，則地址映射按下式進(jìn)行：MR=BR+VR地址映射的方式靜態(tài)地址映射：把程序裝入起始地址為1000的內(nèi)存區(qū)…Movr1,[500]…1234…0100500600Movr1,[1500]010001100150016001234…………作業(yè)的地址空間存儲(chǔ)空間裝入程序把程序裝入起始地址為1000的內(nèi)存區(qū)…Movr1,[500靜態(tài)映射優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持，簡(jiǎn)單易實(shí)現(xiàn)，成本低；缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間；一旦程序裝入后不能移動(dòng)；主存利用率低；難以做到程序和數(shù)據(jù)的共享。靜態(tài)映射優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持，簡(jiǎn)單易實(shí)現(xiàn)，成本低；動(dòng)態(tài)地址映射（重定位）動(dòng)態(tài)地址重定位：在程序執(zhí)行的過(guò)程中，每次將要訪問(wèn)的指令或數(shù)據(jù)邏輯地址轉(zhuǎn)換為內(nèi)存地址。動(dòng)態(tài)映射方法：裝入程序把程序和數(shù)據(jù)原樣裝入到已分配的存儲(chǔ)區(qū)中，然后把這個(gè)存儲(chǔ)區(qū)的起始地址送入重定位寄存器中。在程序執(zhí)行時(shí)，再將相對(duì)地址轉(zhuǎn)換成絕對(duì)地址。硬件支持：在動(dòng)態(tài)地址重定位機(jī)構(gòu)中，有一個(gè)基地址寄存器BR和一個(gè)程序地址寄存器VR，一個(gè)內(nèi)存地址寄存器MR。轉(zhuǎn)換過(guò)程：MR=BR+VR動(dòng)態(tài)地址映射（重定位）動(dòng)態(tài)地址重定位：在程序執(zhí)行的過(guò)程中，每把程序裝入起始地址為1000的內(nèi)存區(qū)……1234…0100500599作業(yè)的地址空間010001100150015991234…………存儲(chǔ)空間1000+重定位寄存器邏輯地址VR物理地址MRMOVr1，[500]MOVr1，[500]把程序裝入起始地址為1000的內(nèi)存區(qū)……1234…01005動(dòng)態(tài)地址映射的過(guò)程程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址由系統(tǒng)送入基地址寄存器BR中。在程序執(zhí)行的過(guò)程中，若要訪問(wèn)內(nèi)存，將訪問(wèn)的邏輯地址送入VR中。地址轉(zhuǎn)換機(jī)構(gòu)把VR和BR中的內(nèi)容相加，并將結(jié)果送入MR中，作為實(shí)際訪問(wèn)的地址。動(dòng)態(tài)地址映射的過(guò)程程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址由動(dòng)態(tài)重定位優(yōu)缺點(diǎn)優(yōu)點(diǎn)：1）程序占用的內(nèi)存空間是動(dòng)態(tài)可變的，當(dāng)程序從某個(gè)存儲(chǔ)區(qū)移到另一個(gè)區(qū)域時(shí)，只需要修改相應(yīng)的寄存器BR的內(nèi)容即可；2）一個(gè)程序不一定要求占用一個(gè)連續(xù)的內(nèi)存空間，可以部分地裝入程序運(yùn)行；4）便于多個(gè)進(jìn)程共享同一個(gè)程序的代碼。動(dòng)態(tài)地址重定位的代價(jià)：1）需要硬件的支持；2）實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜。動(dòng)態(tài)重定位優(yōu)缺點(diǎn)優(yōu)點(diǎn)：1）程序占用的內(nèi)存空間是動(dòng)態(tài)可變的，當(dāng)4.2程序的裝入和鏈接（可能產(chǎn)生）可執(zhí)行程序文件編譯鏈接裝入二進(jìn)制內(nèi)存映像程序處理步驟：編譯編譯程序，負(fù)責(zé)檢查語(yǔ)法錯(cuò)，涉及名空間。輸入：源程序；輸出：多個(gè)目標(biāo)模塊；鏈接鏈接程序，負(fù)責(zé)將多個(gè)模塊相關(guān)聯(lián)，涉及邏輯地址空間。輸入：多個(gè)目標(biāo)模塊、庫(kù)函數(shù)；輸出：裝入模塊；裝入：裝入程序，負(fù)責(zé)內(nèi)存分配和地址映射，涉及內(nèi)存空間。輸入：裝入模塊；輸出：可執(zhí)行的二進(jìn)制內(nèi)存映像。過(guò)程或函數(shù)可能分別對(duì)應(yīng)一個(gè)模塊！4.2程序的裝入和鏈接（可能產(chǎn)生）可執(zhí)行程序文件編譯鏈接4.1.2程序的鏈接1.靜態(tài)鏈接方式(StaticLinking)圖4-3程序鏈接示意圖鏈接前，每個(gè)模塊都有各自的相對(duì)起始地址0鏈接后，每個(gè)模塊使用同一個(gè)相對(duì)起始地址0名空間邏輯地址空間在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝入模塊，又稱為可執(zhí)行文件，以后不再拆開(kāi)。解決：對(duì)相對(duì)地址進(jìn)行修改；變換外部調(diào)用符號(hào)不要求！4.1.2程序的鏈接1.靜態(tài)鏈接方式(Static2.裝入時(shí)動(dòng)態(tài)鏈接(LoadtimeDynamicLinking)基本思想：源程序被編譯生成的目標(biāo)模塊，是在裝入內(nèi)存時(shí)，邊裝入邊連接。裝入程序根據(jù)外部模塊調(diào)用而逐個(gè)裝入和連接。裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)便于修改和更新：各個(gè)模塊的修改極易編譯和連接；便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享：將內(nèi)存中的一個(gè)模塊可以連接到多個(gè)程序中。要運(yùn)行的程序都必須在裝入時(shí)，全部連接調(diào)入內(nèi)存。2.裝入時(shí)動(dòng)態(tài)鏈接(LoadtimeDynamicL3.運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)動(dòng)態(tài)鏈接方式：將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才實(shí)施，亦即，在執(zhí)行過(guò)程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。特點(diǎn)如下：特點(diǎn)：凡在執(zhí)行過(guò)程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過(guò)程，而且可節(jié)省大量的內(nèi)存空間。三種鏈接方式的差別相當(dāng)于：靜態(tài)鏈接：上車（相當(dāng)于進(jìn)入內(nèi)存）前集合起來(lái)裝入時(shí)鏈接：上車后開(kāi)車前集合起來(lái)運(yùn)行時(shí)鏈接：開(kāi)車后需要時(shí)集合起來(lái)3.運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLi4.2.1程序的裝入1.絕對(duì)裝入方式(AbsoluteLoadingMode)程序中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出，也可由程序員直接賦予；編譯程序生成的目標(biāo)模塊其邏輯地址與要裝入內(nèi)存的物理地址相同；缺點(diǎn)：?jiǎn)蔚莱绦蚩捎?，多道程序環(huán)境不能用。采用絕對(duì)地址裝入，目前很少使用4.2.1程序的裝入1.絕對(duì)裝入方式(Absolute2.可重定位裝入方式(RelocationLoadingMode)圖4-2作業(yè)裝入內(nèi)存時(shí)的情況又稱靜態(tài)重定位：地址變換在裝入時(shí)一次完成，其后不能移動(dòng)。邏輯地址（相對(duì)地址）物理地址（絕對(duì)地址）LOAD1,125002.可重定位裝入方式(RelocationLoading3.動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DenamleRun-timeLoading)動(dòng)態(tài)運(yùn)行時(shí)裝方式：裝入內(nèi)存后的所有地址都仍是相對(duì)地址；邏輯地址到物理地址的變換要推遲到程序真正執(zhí)行時(shí)才進(jìn)行；地址變換發(fā)生在程序執(zhí)行過(guò)程中（即動(dòng)態(tài)重定位）。為使地址轉(zhuǎn)換不影響程序執(zhí)行速度，必須使用硬件支持。3.動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DenamleRun-time鏈接和裝入的關(guān)系（一）靜態(tài)鏈接會(huì)形成磁盤上的可執(zhí)行文件，而裝入時(shí)動(dòng)態(tài)鏈接和運(yùn)行時(shí)動(dòng)態(tài)鏈接不會(huì)產(chǎn)生磁盤上的可執(zhí)行文件。靜態(tài)鏈接產(chǎn)生的可執(zhí)行文件裝入時(shí)內(nèi)存是連續(xù)分配的，而地址映射既可采用可重定位裝入方式（靜態(tài)重定位）也可以采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式（動(dòng)態(tài)重定位）鏈接和裝入的關(guān)系（一）靜態(tài)鏈接會(huì)形成磁盤上的可執(zhí)行文件，而裝鏈接和裝入間的關(guān)系（二）裝入時(shí)動(dòng)態(tài)鏈接方式可以分別給每個(gè)裝入模塊分配一塊內(nèi)存區(qū)域，因而裝入時(shí)各模塊不一定連續(xù)存放。裝入時(shí)的地址映射既可采用可重定位裝入方式（靜態(tài)重定位鏈接后運(yùn)行前一次性修改邏輯地址為物理地址）也可以采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式（動(dòng)態(tài)重定位運(yùn)行時(shí)動(dòng)態(tài)計(jì)算出邏輯地址到物理地址的映射）鏈接和裝入間的關(guān)系（二）裝入時(shí)動(dòng)態(tài)鏈接方式可以分別給每個(gè)裝入鏈接和裝入間的關(guān)系（三）運(yùn)行時(shí)動(dòng)態(tài)鏈接方式一般情況下后裝入的模塊和原先已裝入的模塊是不連續(xù)存放的。運(yùn)行時(shí)動(dòng)態(tài)鏈接方式的地址變換不可能運(yùn)行前一次性映射地址，即不可能采用靜態(tài)重定位方法，而只能使用動(dòng)態(tài)重定位的方法。鏈接和裝入間的關(guān)系（三）運(yùn)行時(shí)動(dòng)態(tài)鏈接方式一般情況下后裝入的鏈接和裝入間的關(guān)系（四）

鏈接裝入靜態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接連續(xù)或不連續(xù)分配連續(xù)均可一般不連續(xù)靜態(tài)重定位或動(dòng)態(tài)重定位均可均可動(dòng)態(tài)重定位鏈接和裝入間的關(guān)系（四）4.2連續(xù)分配方式4.2.1單一連續(xù)分配特征：最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中；常把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使用。OS用戶區(qū)4.2連續(xù)分配方式4.2.1單一連續(xù)分配特征：最簡(jiǎn)單4.2.2固定分區(qū)分配1.劃分分區(qū)的方法分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。缺點(diǎn)：缺乏靈活性，大作業(yè)無(wú)法運(yùn)行，小作業(yè)浪費(fèi)空間。分區(qū)大小不等，即劃分為小、中、大不等的固定分區(qū)。優(yōu)點(diǎn)：靈活性好。分配方法：將用戶空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中裝入一道作業(yè)；有幾個(gè)分區(qū)，就有幾道并發(fā)的作業(yè)；有空閑分區(qū)時(shí)，可調(diào)入一適當(dāng)大小的作業(yè)；最簡(jiǎn)單的一種多道程序存儲(chǔ)管理方法。4.2.2固定分區(qū)分配1.劃分分區(qū)的方法分區(qū)大小相2.內(nèi)存分配：為了便于內(nèi)存分配，將分區(qū)按照大小排隊(duì)，并建立一個(gè)分區(qū)表。如圖所示。當(dāng)為作業(yè)分配空間時(shí)，分配程序按照此表檢索以合適分區(qū)分配；否則，拒絕分配。缺點(diǎn)：空間浪費(fèi)。圖4-4固定分區(qū)使用表2.內(nèi)存分配：為了便于內(nèi)存分配，將分區(qū)按照大小排隊(duì)，并建4.2.3動(dòng)態(tài)分區(qū)分配1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表。

(2)空閑分區(qū)鏈。圖4-5空閑鏈結(jié)構(gòu)分配思想：根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)的為進(jìn)程分配（切分）內(nèi)存空間，及需要多大，分配多大。提高內(nèi)存的利用率。4.2.3動(dòng)態(tài)分區(qū)分配1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑未分配區(qū)表用空閑區(qū)鏈表表示：0010k10k270k∧00730k730k100k100k100k270k

空閑區(qū)鏈head∧∧空閑區(qū)大小未分配區(qū)表用空閑區(qū)鏈表表示：0010k10k270k∧0072.分區(qū)分配算法首次適應(yīng)算法FF：空閑分區(qū)按地址遞增成鏈表；每次分配從鏈?zhǔn)滓来尾檎乙豢臻g首次滿足作業(yè)的空閑分區(qū)；再?gòu)脑摲謪^(qū)中切出與作業(yè)等量的空間分之，余者掛到鏈表中；若找不到滿足作業(yè)空間要求的空閑分區(qū)，分配失敗。

優(yōu)缺點(diǎn)：低地址部分將產(chǎn)生多個(gè)較小的空閑分區(qū)（碎片），增加分配開(kāi)銷。問(wèn)題：如何從空閑分區(qū)表或鏈表中，選擇一分區(qū)分配個(gè)作業(yè)，常用的算法如下：2.分區(qū)分配算法首次適應(yīng)算法FF：空閑分區(qū)按地址遞增成2.分區(qū)分配算法循環(huán)首次適應(yīng)算法：該算法是由首次適應(yīng)算法演變而成的，區(qū)別僅是從上次已分配分區(qū)的下一個(gè)分區(qū)依次查找首次滿足作業(yè)的空閑分區(qū)，并從中劃分出作業(yè)需要的分區(qū)。

實(shí)現(xiàn)方法：起始循環(huán)指針+循環(huán)空閑分區(qū)鏈表最佳適應(yīng)算法：空閑鏈表依照空間大小排列，每次從鏈?zhǔn)诪樽鳂I(yè)找一個(gè)大小最合適的分區(qū)分配。

缺點(diǎn)：最佳適應(yīng)必將產(chǎn)生最小的空閑碎片。④最壞適應(yīng)算法(worstfit)：總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用，其優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對(duì)中、小作業(yè)有利，同時(shí)最壞適應(yīng)分配算法查找效率很高。2.分區(qū)分配算法循環(huán)首次適應(yīng)算法：該算法是由首次適應(yīng)算3.分區(qū)分配操作分配內(nèi)存操作 分配操作如左圖所示3.分區(qū)分配操作分配內(nèi)存操作回收內(nèi)存操作

回收的分區(qū)有4種情況：與前、后、前后空分區(qū)相鄰，如下圖所示。圖4-7內(nèi)存回收時(shí)的情況回收內(nèi)存操作圖4-7內(nèi)存回收時(shí)的情況當(dāng)回收分區(qū)與前后空閑分區(qū)均不相鄰時(shí)，為回收分區(qū)建立一個(gè)空閑分區(qū)結(jié)點(diǎn)，并插入鏈表適當(dāng)位置。回收分區(qū)…………當(dāng)回收分區(qū)與前后空閑分區(qū)均不相鄰時(shí)，為回收分區(qū)建立一個(gè)空閑分4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入：動(dòng)態(tài)回收碎片，將小而不可用的空閑分區(qū)拼接成較大的一個(gè)空閑分區(qū)。移動(dòng)作業(yè)分區(qū)，必然要重定位。圖4-8緊湊的示意4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入：動(dòng)2.動(dòng)態(tài)重定位的實(shí)現(xiàn)：作業(yè)在內(nèi)存中仍保持邏輯地址，在執(zhí)行時(shí)再實(shí)施重定位。具體過(guò)程如下圖。圖4-9動(dòng)態(tài)重定位示意圖2.動(dòng)態(tài)重定位的實(shí)現(xiàn)：作業(yè)在內(nèi)存中仍保持邏輯地址，在執(zhí)行時(shí)再3.動(dòng)態(tài)重定位分區(qū)分配算法：在動(dòng)態(tài)分區(qū)算法增加了回收碎片的功能。圖4-10動(dòng)態(tài)分區(qū)分配算法流程圖3.動(dòng)態(tài)重定位分區(qū)分配算法：在動(dòng)態(tài)分區(qū)算法增加了回收碎片的作業(yè)4-1P142：4、5、6作業(yè)4-1P142：4、5、64.2.5對(duì)換(Swapping)1.對(duì)換的引入對(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)存的利用率。進(jìn)程對(duì)換：如果對(duì)換是以整個(gè)進(jìn)程為單位進(jìn)行的，則稱為進(jìn)程對(duì)換或整體對(duì)換；頁(yè)面對(duì)換：如果對(duì)換是以頁(yè)或段為單位進(jìn)行的，稱為頁(yè)面對(duì)換或分段對(duì)換，統(tǒng)稱部分對(duì)換。在實(shí)現(xiàn)虛擬存儲(chǔ)系統(tǒng)時(shí)候，依靠頁(yè)面或分段對(duì)換。4.2.5對(duì)換(Swapping)1.對(duì)換的引入對(duì)2.對(duì)換空間的管理實(shí)現(xiàn)進(jìn)程對(duì)換系統(tǒng)必須具備三個(gè)功能：對(duì)換空間管理、進(jìn)程的換出和進(jìn)程的換入。首先研究對(duì)換空間管理：將外存磁盤空間劃分為文件區(qū)和對(duì)換區(qū)：文件區(qū)用于存放文件，管理以提高存儲(chǔ)空間的利用率為目的；后者用于存儲(chǔ)對(duì)換的進(jìn)程，故應(yīng)以提高對(duì)換速度為目標(biāo)。對(duì)換去空間管理：建立對(duì)換區(qū)空閑空間分區(qū)表（鏈）數(shù)據(jù)結(jié)構(gòu)。其形式與內(nèi)存動(dòng)態(tài)分區(qū)分配方式中的空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表項(xiàng)中應(yīng)包含兩項(xiàng)，對(duì)換區(qū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)。2.對(duì)換空間的管理實(shí)現(xiàn)進(jìn)程對(duì)換系統(tǒng)必須具備三個(gè)功能：對(duì)換2.對(duì)換空間的管理對(duì)換區(qū)分配：采用連續(xù)分配，雷同內(nèi)存動(dòng)態(tài)分區(qū)方式的分配算法：可用首次適應(yīng)算法，循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法。對(duì)換區(qū)回收：也與內(nèi)存動(dòng)態(tài)分區(qū)回收算法雷同，要考慮回收區(qū)與前后地址相鄰（磁盤塊號(hào)）分區(qū)的合并。2.對(duì)換空間的管理對(duì)換區(qū)分配：采用連續(xù)分配，雷同內(nèi)存動(dòng)態(tài)3.進(jìn)程的換出與換入進(jìn)程的換出：每當(dāng)創(chuàng)建一新進(jìn)程而又無(wú)足夠的內(nèi)存空間時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。換出過(guò)程：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，并將該進(jìn)程的程序和數(shù)據(jù)安全傳送到磁盤的對(duì)換區(qū)上；然后回收該進(jìn)程所占用的內(nèi)存空間，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改（該什么？）。進(jìn)程的換入：系統(tǒng)定時(shí)找出“靜止就緒”狀態(tài)的進(jìn)程，并將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程換入，直至已無(wú)可換入的進(jìn)程3.進(jìn)程的換出與換入進(jìn)程的換出：每當(dāng)創(chuàng)建一新進(jìn)程而又無(wú)4.3基本分頁(yè)存儲(chǔ)管理方式問(wèn)題：由于為進(jìn)程連續(xù)分配內(nèi)存空間，將產(chǎn)生大量碎片；為了利用碎片必須將其合并，又需要系統(tǒng)開(kāi)銷。能否給進(jìn)程離散（不連續(xù)）地分配內(nèi)存空間，解決這些問(wèn)題？離散分配：當(dāng)前使用最多的內(nèi)存分配方式是分頁(yè)管理方式和分段管理方式；分頁(yè)是頁(yè)面為單位進(jìn)行內(nèi)存分配，分段方式是以段為單位進(jìn)行內(nèi)存分配。基本分頁(yè)（段）存儲(chǔ)管理方式：如果分頁(yè)或分段存儲(chǔ)管理方式中不具備頁(yè)面或分段對(duì)換功能，將其稱之為基本分頁(yè)或基本分段存儲(chǔ)管理方式。4.3基本分頁(yè)存儲(chǔ)管理方式問(wèn)題：由于為進(jìn)程連續(xù)分配內(nèi)存4.3.1頁(yè)面與頁(yè)表1.頁(yè)面與物理塊頁(yè)面：將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁(yè)面或頁(yè)，并為各頁(yè)順序編號(hào)為0、1、2、…、n。物理塊：把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為(物理)塊或頁(yè)框(frame)，也同樣為它們加以編號(hào)，如0＃塊、1＃塊等等。內(nèi)存分配原理：在為進(jìn)程分配內(nèi)存時(shí)，以頁(yè)面為單位給進(jìn)程離散分配與頁(yè)面數(shù)等量的物理塊，并分別裝入到相應(yīng)的物理塊中（全部裝入）

頁(yè)內(nèi)碎片：由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁(yè)內(nèi)碎片”。4.3.1頁(yè)面與頁(yè)表1.頁(yè)面與物理塊舉例：如左圖所示，按照基本分頁(yè)存儲(chǔ)管理方式為進(jìn)程分配內(nèi)存空間。設(shè)頁(yè)面大小為1KB舉例：如左圖所示，按照基本分頁(yè)存儲(chǔ)管理方式為進(jìn)程分配內(nèi)存空間頁(yè)面大小設(shè)定：在分頁(yè)系統(tǒng)中的頁(yè)面其大小應(yīng)適中，且頁(yè)面大小應(yīng)是2的冪，通常為512B~8KB。頁(yè)面大小利弊：若頁(yè)面太小，內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，提高內(nèi)存利用率；但另一方面也會(huì)使每個(gè)進(jìn)程占用較多的頁(yè)面，從而導(dǎo)致進(jìn)程的頁(yè)表過(guò)長(zhǎng)，占用大量?jī)?nèi)存等；若頁(yè)面較大，可以減少頁(yè)表的長(zhǎng)度，節(jié)省內(nèi)存，但卻又會(huì)使頁(yè)內(nèi)碎片增大。頁(yè)面大小設(shè)定：在分頁(yè)系統(tǒng)中的頁(yè)面其大小應(yīng)適中，且頁(yè)面大小應(yīng)是2、邏輯地址結(jié)構(gòu)頁(yè)號(hào)頁(yè)內(nèi)地址0111231頁(yè)號(hào)P頁(yè)內(nèi)位移量W編號(hào)0~1048575相對(duì)地址0~4095最大頁(yè)面數(shù)：

220=1M個(gè)頁(yè)面大?。?/p>

212=4KB邏輯空間：

0~232-1一維的，并針對(duì)程序員2、邏輯地址結(jié)構(gòu)頁(yè)號(hào)頁(yè)內(nèi)地址011邏輯地址空間中的地址為A，頁(yè)面大小為L(zhǎng)，則有：P=INT[A/L]d=[A]MODL例：A=2170B，L=1KB時(shí)，則有P=2，d=122邏輯地址空間中的地址為A，頁(yè)面大小為L(zhǎng)，則有：3、頁(yè)表分頁(yè)存儲(chǔ)管理方式按照進(jìn)程頁(yè)面的多少，為進(jìn)程離散分配相同數(shù)量的物理塊，為了記錄每一頁(yè)所分配的物理塊，必須為每個(gè)進(jìn)程建立一個(gè)頁(yè)表每個(gè)進(jìn)程一個(gè)頁(yè)表，每個(gè)頁(yè)面一個(gè)表項(xiàng)；表項(xiàng)：頁(yè)號(hào)：0、1、2、…、n；塊號(hào)：離散分配形成；存取控制：讀寫控制3、頁(yè)表

頁(yè)表示意圖圖4-11頁(yè)表的作用頁(yè)表示意圖圖4-11頁(yè)表的作用基本分頁(yè)系統(tǒng)多進(jìn)程內(nèi)存分配示意圖基本分頁(yè)系統(tǒng)多進(jìn)程內(nèi)存分配示意圖4.3.2地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)：實(shí)現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換。由于頁(yè)內(nèi)地址與塊內(nèi)地址一一對(duì)應(yīng)，所以地址轉(zhuǎn)換關(guān)鍵是將邏輯地址中的頁(yè)號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。轉(zhuǎn)換機(jī)構(gòu)設(shè)施：頁(yè)表寄存器：存放進(jìn)程頁(yè)表在內(nèi)存中的起地址和頁(yè)表長(zhǎng)度（進(jìn)程不執(zhí)行時(shí)放在PCB中，執(zhí)行時(shí)調(diào)入寄存器中）；物理地址寄存器：存放轉(zhuǎn)換后的物理地址（內(nèi)存地址）；查找表項(xiàng)：表項(xiàng)地址=頁(yè)表起始地址+頁(yè)號(hào)*表項(xiàng)長(zhǎng)度；地址轉(zhuǎn)換過(guò)程如下圖。

圖4-12分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)4.3.2地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)：實(shí)現(xiàn)邏輯地址計(jì)算機(jī)操作系統(tǒng)第四章-存儲(chǔ)器管理(1-2)要點(diǎn)課件[例]說(shuō)明運(yùn)行進(jìn)程的地址變換過(guò)程。如下圖所示，進(jìn)程程序地址空間共有7個(gè)頁(yè)，每頁(yè)的大小為1024。其對(duì)應(yīng)的主存塊在頁(yè)表中已列出。假定頁(yè)表在主存始址為500。若該程序從第0頁(yè)開(kāi)始運(yùn)行，且現(xiàn)程序計(jì)數(shù)器內(nèi)容為：0100程序計(jì)數(shù)器：邏輯地址[例]說(shuō)明運(yùn)行進(jìn)程的地址變換過(guò)程。0100程序計(jì)數(shù)器：邏輯頁(yè)表寄存器程序計(jì)數(shù)器50070(頁(yè)號(hào)）100（頁(yè)內(nèi)地址）>+頁(yè)表5（內(nèi)存塊號(hào)）100（頁(yè)內(nèi)地址）12345012345657915131016500每頁(yè)的大小為1024內(nèi)存地址：5×1024+100=5220500+0=500頁(yè)表寄存器程序計(jì)數(shù)器50070(頁(yè)號(hào)）10例：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。例：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為虛地址7145P＝7145％2048＝3W＝7145mod2048

＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241虛地址3412P＝3412％2048＝1W＝3412mod2048

＝1364MR=9*2048+1364=19796虛地址3412的內(nèi)存地址是：19796虛地址7145虛地址34122、具有快表的地址變換機(jī)構(gòu)問(wèn)題：兩次訪問(wèn)內(nèi)存(頁(yè)表，數(shù)據(jù))，運(yùn)行速度下降一半；解決方法：聯(lián)想存儲(chǔ)器，快表，存放當(dāng)前訪問(wèn)的頁(yè)表項(xiàng)；思路：將已訪問(wèn)的頁(yè)號(hào)的頁(yè)表項(xiàng)放入快表，方便下次訪問(wèn)，提高訪問(wèn)速度，爭(zhēng)取一次訪問(wèn)內(nèi)存；聯(lián)想存儲(chǔ)器：通常只要設(shè)定8～16個(gè)寄存器作為聯(lián)想存儲(chǔ)器，即可使程序執(zhí)行速度大大提高。2、具有快表的地址變換機(jī)構(gòu)

具有快表的地址變換過(guò)程示意圖圖4-13具有快表的地址變換機(jī)構(gòu)具有快表的地址變換過(guò)程示意圖圖4-13具有快表的地4.3.3兩級(jí)和多級(jí)頁(yè)表問(wèn)題：現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對(duì)于一個(gè)具有32位邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面大小為4KB即212B，則在每個(gè)進(jìn)程頁(yè)表中的頁(yè)表項(xiàng)可達(dá)1兆個(gè)之多，而且還要求是連續(xù)的。解決辦法：①采用離散分配方式存放頁(yè)表；②使用對(duì)換方式調(diào)入、調(diào)出頁(yè)表。4.3.3兩級(jí)和多級(jí)頁(yè)表問(wèn)題：現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，1.兩級(jí)頁(yè)表(Two-LevelPageTable)邏輯地址結(jié)構(gòu)可描述如下：頁(yè)面大小為4K（12位），每頁(yè)包含1024個(gè)頁(yè)表項(xiàng)（P2，占10位）；總共有1024個(gè)分頁(yè)（P1，占10位））1.兩級(jí)頁(yè)表(Two-LevelPageTable)圖4-14兩級(jí)頁(yè)表結(jié)構(gòu)圖4-14兩級(jí)頁(yè)表結(jié)構(gòu)圖4-15具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)二級(jí)頁(yè)表地址轉(zhuǎn)換過(guò)程示意圖圖4-15具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)二級(jí)頁(yè)表地址轉(zhuǎn)換過(guò)

2.多級(jí)頁(yè)表