第22講 第四章總復(fù)習(xí)

河北科技師范學(xué)院大專課程

操作系統(tǒng)第二十二講主講人：曾曉寧2023/1/31第4章內(nèi)存管理4.1內(nèi)存管理功能4.2分區(qū)管理4.3頁(yè)式管理4.4段式管理4.5段頁(yè)式管理2023/1/314.1內(nèi)存管理功能4.1.1內(nèi)存的分配與回收(重點(diǎn)是研究?jī)?nèi)存分配給多個(gè)用戶使用和各種分配算法）4.1.2地址重定位（研究各種地址變換機(jī)構(gòu)以及靜態(tài)和動(dòng)態(tài)重定方法）4.1.3內(nèi)存的共享與保護(hù)（研究保護(hù)各類程序、數(shù)據(jù)區(qū)的方法）4.1.4虛擬存儲(chǔ)器（主要研究虛擬存儲(chǔ)器和各種調(diào)度算法）2023/1/31靜態(tài)重定位和動(dòng)態(tài)重定位地址重定位：目標(biāo)程序只有通過鏈接、裝入內(nèi)存才能運(yùn)行，當(dāng)程序裝入內(nèi)存時(shí)，每道程序不可能都從內(nèi)存空間的0地址開始裝入。因此，程序的邏輯地址與分配到的內(nèi)存的物理地址不一致，為使程序能正確運(yùn)行，必須將程序的邏輯地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中的物理地址，這一過程稱為地址重定位。有靜態(tài)重定位和動(dòng)態(tài)重定位兩種方式；2023/1/31(1)靜態(tài)地址重定位/靜態(tài)地址映射靜態(tài)地址重定位：是指當(dāng)目標(biāo)程序被裝入內(nèi)存時(shí)，由重定位裝入程序，一次性完成邏輯地址到物理地址的轉(zhuǎn)換。在程序執(zhí)行之前由操作系統(tǒng)完成的。在運(yùn)行過程中，不再進(jìn)行地址轉(zhuǎn)換。是由重定位裝入程序按照公式：

物理地址=邏輯地址+起始地址把目標(biāo)程序中所有的邏輯地址轉(zhuǎn)換成物理地址；2023/1/31(2)動(dòng)態(tài)地址重定位是指把目標(biāo)程序裝入內(nèi)存時(shí)，并不立即把邏輯地址轉(zhuǎn)達(dá)換為物理地址，而是在程序運(yùn)行過程中，當(dāng)CPU訪問程序和數(shù)據(jù)時(shí)，才進(jìn)行地址轉(zhuǎn)換。2023/1/314.2分區(qū)管理

也稱連續(xù)分配方式，是指程序裝入的內(nèi)存空間必須是連續(xù)的，操作系統(tǒng)占用一個(gè)區(qū)域，其它區(qū)域供系統(tǒng)中的多個(gè)進(jìn)程共享，這種方法稱為分區(qū)存儲(chǔ)管理。 這是最簡(jiǎn)單的一種存儲(chǔ)管理,按分區(qū)劃分的時(shí)機(jī)可分為4.2.1單分區(qū)4.2.2固定分區(qū)4.2.3可變分區(qū)2023/1/314.2.1單分區(qū)基本思想：在任一時(shí)刻，只有一個(gè)進(jìn)程存在，且這個(gè)進(jìn)程總是從用戶區(qū)的起始地址開始連續(xù)存放，從裝入到執(zhí)行完畢，獨(dú)占整個(gè)用戶區(qū)。適用于單用戶單任務(wù)的OS。2023/1/314.2.2固定分區(qū)基本思想：把內(nèi)存空間劃分成若干個(gè)固定大小的連續(xù)存儲(chǔ)區(qū)，稱為分區(qū)。每個(gè)分區(qū)只能裝入一道程序，內(nèi)存被劃分成幾個(gè)分區(qū)，就允許裝入幾道程序。2023/1/31內(nèi)存不事先進(jìn)行劃分，而是在裝入程序時(shí)，根據(jù)裝入程序的實(shí)際需要來(lái)分配內(nèi)存空間，這樣，內(nèi)存分區(qū)的個(gè)數(shù)、各分區(qū)的大小、在內(nèi)存中活動(dòng)的內(nèi)存?zhèn)€數(shù)都是隨時(shí)間變化的。4.2.3可變分區(qū)2023/1/31系統(tǒng)啟動(dòng)后，整個(gè)用戶區(qū)是一個(gè)完整的大空閑區(qū)。當(dāng)要裝入一個(gè)程序時(shí)，系統(tǒng)從空閑區(qū)中按需要?jiǎng)澐忠粋€(gè)分區(qū)分配給該程序。內(nèi)存空間經(jīng)過多次分配和回收后原來(lái)一塊大的空閑區(qū)被分割成了若干個(gè)占用區(qū)和空閑區(qū)。此時(shí)，如果要裝入一個(gè)程序，系統(tǒng)則根據(jù)需求和內(nèi)存空間的使用情況來(lái)決定是否分配。若能找到一個(gè)滿足程序需要的空閑區(qū)，則從該空閑區(qū)中劃出一塊與程序大小相同的區(qū)域分配給它；剩下的區(qū)域又形成一個(gè)較小的空閑區(qū)；若有相鄰的空閑區(qū)，則合并成一個(gè)較大的空閑區(qū)。2023/1/31空閑分區(qū)鏈在每個(gè)空閑分區(qū)的起始單元設(shè)置兩個(gè)域，一個(gè)域用于存放空閑分區(qū)的大??；另一個(gè)域存放指向下一個(gè)空閑分區(qū)起始地址的指針。操作系統(tǒng)開辟一個(gè)單元，存放第1個(gè)空閑分區(qū)的起始地址，這個(gè)單元被稱為“鏈?zhǔn)字羔槨?。最后一個(gè)空閑分區(qū)的next中存放標(biāo)志“NULL”表明它是最后一個(gè)。這樣就可以把所有的空閑分區(qū)按一定規(guī)則排列鏈接成一個(gè)鏈表。2023/1/31常用的內(nèi)存分配算法當(dāng)裝入一個(gè)程序時(shí)，按一定的分配算法，從空閑分區(qū)鏈中查找滿足需求的空閑分區(qū)進(jìn)行分配，常用的分配算法有以下4種：（1）首次適應(yīng)算法（2）循環(huán)首次適應(yīng)算法（3）最佳適應(yīng)算法（4）最壞適應(yīng)算法2023/1/31方面算法排序方法開始位置確定依據(jù)首次適應(yīng)法地址從小到大鏈?zhǔn)椎谝粋€(gè)大小能滿足要求的循環(huán)首次適應(yīng)法地址從小到大上次找到的下一個(gè)分區(qū)第一個(gè)大小能滿足要求的最佳適應(yīng)算法長(zhǎng)度從小到大鏈?zhǔn)鬃罴训?、第一個(gè)大小能滿足要求的、最壞適應(yīng)算法長(zhǎng)度從大到小鏈?zhǔn)组L(zhǎng)度最大的2023/1/31回收區(qū)不與任何空閑區(qū)相鄰：將回收區(qū)作為一個(gè)空閑區(qū)節(jié)點(diǎn)，直接插入到空閑分區(qū)鏈的適當(dāng)位置?；厥諈^(qū)與后空閑區(qū)相鄰：則把回收區(qū)合并到后空閑分區(qū)，不必為回收區(qū)創(chuàng)建新節(jié)點(diǎn)，只需把后空閑分區(qū)節(jié)點(diǎn)的起始地址改為回收區(qū)的首地址，大小為二者大小之和。分區(qū)的回收2023/1/31回收區(qū)與前空閑區(qū)相鄰：將回收區(qū)與前空閑區(qū)合并為一個(gè)空閑區(qū)。不必為回收區(qū)創(chuàng)建新節(jié)點(diǎn)，其首址仍為前空閑區(qū)首址，大小改為回收區(qū)大小與空閑區(qū)大小之和?；厥諈^(qū)與前后兩個(gè)空閑區(qū)相鄰：將這三個(gè)區(qū)合為一個(gè)空閑區(qū)，其首址為前空閑區(qū)首址，大小為這三個(gè)區(qū)大小之和，并刪除原后空閑區(qū)節(jié)點(diǎn)。2023/1/31覆蓋技術(shù)與交換技術(shù)在多道環(huán)境下擴(kuò)充內(nèi)存的方法，用以解決在較小的存儲(chǔ)空間中運(yùn)行較大程序時(shí)遇到的矛盾；覆蓋技術(shù)主要用在早期的操作系統(tǒng)中交換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)；2023/1/31頁(yè)式管理允許將程序分散地裝入到內(nèi)存中若干個(gè)不連續(xù)的空閑分區(qū)中，可以全部裝入，也可以部分裝入。即有效地解決了碎片問題，又能充分利用內(nèi)存空間，提高了內(nèi)存利用率。4.3頁(yè)式管理2023/1/31

用戶程序的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。一般，一頁(yè)的大小為2的整數(shù)次冪；分頁(yè)時(shí)，系統(tǒng)自動(dòng)將邏輯地址分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，地址的高位部分為頁(yè)號(hào)，低位部分為頁(yè)內(nèi)地址。頁(yè)號(hào)頁(yè)內(nèi)地址0111231頁(yè)號(hào)P頁(yè)內(nèi)位移量W每頁(yè)大小：212=4KB地址空間中最多有：210=1M頁(yè)2023/1/31設(shè)邏輯地址為n位頁(yè)內(nèi)地址為m位則每頁(yè)大小為2m最多包含2n-m頁(yè)mn-mn2023/1/31邏輯地址A（已知）頁(yè)面大小L（已知）頁(yè)號(hào)P頁(yè)內(nèi)地址d頁(yè)面大小L邏輯地址0A則P=[A/L]d=AmodL邏輯地址/每頁(yè)大小=商…..余數(shù)商：頁(yè)號(hào)余數(shù)：頁(yè)內(nèi)地址2023/1/31計(jì)算時(shí)要注意：若給出的地址為16進(jìn)制，則將其轉(zhuǎn)換為二進(jìn)制，然后，根據(jù)頁(yè)長(zhǎng)及邏輯地址的長(zhǎng)度，分別取出邏輯地址的高幾位和低幾位就得到頁(yè)號(hào)及頁(yè)內(nèi)地址。如頁(yè)長(zhǎng)為2K，邏輯地址為16位，則高5位為頁(yè)號(hào)，低11位為頁(yè)內(nèi)地址。若給出的地址為10進(jìn)制，則用公式：

邏輯/頁(yè)長(zhǎng)商為頁(yè)號(hào)，余數(shù)為頁(yè)內(nèi)地址。如程序地址為8457，

頁(yè)長(zhǎng)為4KB，則8457/4096可得：商為2，余數(shù)為256。2023/1/31思想：要求程序全部裝入內(nèi)存后，才能開始運(yùn)行。在裝入程序時(shí)，首先把程序劃分成若干個(gè)大小相等的頁(yè)面，然后系統(tǒng)按塊為單位，將程序的每一頁(yè)分散地裝入到內(nèi)存的物理塊中；一個(gè)程序有多少頁(yè)，就給它分配多少物理塊，且這些物理塊可以不連續(xù)。靜態(tài)頁(yè)式管理2023/1/31頁(yè)表頁(yè)面系統(tǒng)為了能在內(nèi)存中找到每個(gè)頁(yè)面對(duì)應(yīng)的物理塊而為進(jìn)程建立一張頁(yè)面映像表，簡(jiǎn)稱頁(yè)表。頁(yè)表作用：實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。記錄了頁(yè)面與內(nèi)存物理塊之間的對(duì)應(yīng)關(guān)系。包含頁(yè)號(hào)和塊號(hào)兩項(xiàng)內(nèi)容。2023/1/31地址轉(zhuǎn)換分頁(yè)中的地址映射其實(shí)與通常的地址映射的概念是一樣的，即把程序地址轉(zhuǎn)換成內(nèi)存地址，這個(gè)轉(zhuǎn)換過程是在程序執(zhí)行過程中完成的，是動(dòng)態(tài)地址映射。在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，由系統(tǒng)提供的地址映射硬件來(lái)完成地址映射工作。2023/1/31實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換。實(shí)際上是把邏輯地址中的頁(yè)號(hào)，轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。地址變化任務(wù)是借助于頁(yè)表來(lái)完成的?；救蝿?wù)2023/1/31越界中斷頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表寄存器頁(yè)號(hào)塊號(hào)邏輯地址頁(yè)號(hào)P塊號(hào)P’頁(yè)號(hào)P頁(yè)內(nèi)地址W物理地址塊號(hào)P’塊內(nèi)地址W＞頁(yè)表地址轉(zhuǎn)換過程：2023/1/31解決這個(gè)問題的一種方法是把最近訪問過的頁(yè)表放在一組快速存儲(chǔ)器中（Cache），從而加快訪問內(nèi)存的速度。把這種快速存儲(chǔ)器組成的頁(yè)表稱為快表，用于存放最近訪問過的的頁(yè)表項(xiàng)。快表又叫聯(lián)想存儲(chǔ)器；快表2023/1/31頁(yè)式虛存管理在靜態(tài)頁(yè)式管理的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能來(lái)實(shí)現(xiàn)虛擬存儲(chǔ)器功能。頁(yè)式虛存管理中，進(jìn)程開始運(yùn)行之前，不是裝入全部頁(yè)面，而是只裝入立即使用的那部分頁(yè)面，其余的頁(yè)面在外存中。在進(jìn)程運(yùn)行過程中，當(dāng)需要訪問的頁(yè)面不在內(nèi)存中時(shí)，則將它們從外存調(diào)入內(nèi)存，動(dòng)態(tài)的裝入這些頁(yè)面。如果此時(shí)內(nèi)存已滿，則需要根據(jù)某種算法，淘汰某個(gè)頁(yè)面，以便裝入需要的頁(yè)面。2023/1/31駐留位：用來(lái)標(biāo)識(shí)該頁(yè)是否在內(nèi)存，為1表示在內(nèi)存，為0表示不在內(nèi)存；外存地址：表示該頁(yè)在外存的位置，供調(diào)入該頁(yè)時(shí)參考；訪問字段：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問的次數(shù)，或記錄本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪問，供選擇換出頁(yè)面時(shí)參考。修改位：用于表示該頁(yè)在內(nèi)存中是否被修改過，為0表示沒被修改過，為1表示被修改過。決定了是否需要再將該頁(yè)寫入外存。也可用于頁(yè)面淘汰。頁(yè)號(hào)駐留位物理塊號(hào)外存地址訪問字段修改位2、擴(kuò)充頁(yè)表2023/1/313、缺頁(yè)中斷在頁(yè)式虛存管理系統(tǒng)中，可以通過查詢頁(yè)表中的駐留位來(lái)確定該頁(yè)是否在內(nèi)存。當(dāng)所要訪問的頁(yè)面不在內(nèi)存時(shí)，便產(chǎn)生缺頁(yè)中斷，根據(jù)頁(yè)表中的外存地址找到該頁(yè)在外存中的位置。再將該頁(yè)從外存調(diào)入內(nèi)存。2023/1/315、內(nèi)存分配策略在頁(yè)式虛存管理系統(tǒng)中，給進(jìn)程分配內(nèi)存空間可以采用固定分配和可變分配兩種策略。固定分配：在創(chuàng)建進(jìn)程時(shí)，根據(jù)進(jìn)程類型或程序員的要求，系統(tǒng)為每個(gè)進(jìn)程在內(nèi)存中分配一定數(shù)目的物理塊；且在進(jìn)程運(yùn)行期間不再改變。有平均分配算法、按比例分配算法、優(yōu)先級(jí)分配可變分配：先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊；在進(jìn)程運(yùn)行中，發(fā)現(xiàn)缺頁(yè)時(shí)，可在內(nèi)存中再找一個(gè)空閑塊分配給該進(jìn)程；即進(jìn)程分得的物理塊數(shù)可動(dòng)態(tài)地改變。2023/1/316、頁(yè)面置換策略1）在進(jìn)行頁(yè)面置換時(shí)，可以采用以下兩種策略：①全局置換是指當(dāng)進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，且此時(shí)內(nèi)存空間已滿時(shí)，由OS從內(nèi)存中按照某種頁(yè)面置換算法選擇一頁(yè)調(diào)出內(nèi)存，該頁(yè)可以是內(nèi)存中任一進(jìn)程的頁(yè)。②局部置換當(dāng)進(jìn)程產(chǎn)生缺頁(yè)中斷時(shí)，只能從該進(jìn)程在內(nèi)存的物理塊中選擇一頁(yè)換出，始終保持分配給該進(jìn)程的物理塊數(shù)不變。2023/1/312）頁(yè)面置換策略通常要和內(nèi)存分配策略配合使用，一般有以下3種組合：①固定分配局部置換策略②可變分配全局置換策略③可變分配局部置換策略2023/1/31頁(yè)面置換算法1．最佳置換算法（OPT算法）2．先進(jìn)先出頁(yè)面置換算法（FIFO算法）3．最近最少使用頁(yè)面置換算法（LRU算法）4．Clock置換算法(LRU近似算法)2023/1/311．最佳置換算法（OPT算法）思想：置換以后不再被訪問或在以后最遲才會(huì)訪問的頁(yè)。特點(diǎn)：本算法可以保證最低的缺頁(yè)率，但由于無(wú)法預(yù)知哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問的。因而該算法是無(wú)法實(shí)現(xiàn)的。但是，可把它作為一種評(píng)價(jià)標(biāo)準(zhǔn)，比較其他實(shí)用方法的優(yōu)劣，所以，最優(yōu)算法只具有理論上的意義。2023/1/312．先進(jìn)先出算法（FIFO算法）思想：總是先淘汰最先進(jìn)入內(nèi)存的頁(yè)面即選擇內(nèi)存中駐時(shí)間最長(zhǎng)的頁(yè)面予以淘汰；即先進(jìn)入內(nèi)存的頁(yè)面先被置換掉。理由：最先進(jìn)入內(nèi)存的頁(yè)面不再被訪問的可能性最大。

特點(diǎn)：算法簡(jiǎn)單，容易實(shí)現(xiàn)，只要把內(nèi)存中的頁(yè)面，按進(jìn)入內(nèi)存的先后次序排成一個(gè)隊(duì)列，新進(jìn)入的頁(yè)面排在隊(duì)尾，淘汰頁(yè)面時(shí)，總是從隊(duì)首進(jìn)行。但它會(huì)淘汰經(jīng)常訪問的頁(yè)面，不適應(yīng)進(jìn)程實(shí)際運(yùn)行的規(guī)律。很少使用。2023/1/313．最近最少使用頁(yè)面置換算法（LRU算法）思想：根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策，當(dāng)需要置換一頁(yè)時(shí)，選擇最近一段時(shí)間最長(zhǎng)時(shí)間沒有被訪問的頁(yè)面予以淘汰。這種算法考慮了程序設(shè)計(jì)的局部性原理。如果某一頁(yè)被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁(yè)很長(zhǎng)時(shí)間沒有被訪問，那么最近也不太可能會(huì)被訪問。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過去”作為“最近的將來(lái)”的近似，選擇最近最久未使用的頁(yè)面予以淘汰。2023/1/31思想：每頁(yè)設(shè)置一位訪問位。在進(jìn)程的頁(yè)表中增加一個(gè)指針項(xiàng)，將內(nèi)存中的頁(yè)面鏈接成一個(gè)循環(huán)隊(duì)列，并用一個(gè)指針指向循環(huán)隊(duì)列中下一個(gè)將被置換的頁(yè)面。當(dāng)把一個(gè)頁(yè)面調(diào)入內(nèi)存，或訪問某頁(yè)時(shí)，將該頁(yè)面對(duì)應(yīng)頁(yè)表中的訪問位置為1。4．Clock轉(zhuǎn)換算法（LRU近似算法）2023/1/31在淘汰頁(yè)面時(shí)，從指針?biāo)傅漠?dāng)前位置開始，掃描循環(huán)隊(duì)列：若訪問位為1，則重新置為0，跳過該頁(yè)；若訪問位是0，則淘汰該頁(yè)，指針推進(jìn)一個(gè)位置；若循環(huán)隊(duì)列中所有頁(yè)面的訪問位均為1，則把它們?nèi)恐刂脼?，指針重新指向起始位置，并淘汰該頁(yè)，然后指針推進(jìn)一個(gè)位置。2023/1/315、改進(jìn)的clock置換算法淘汰頁(yè)面時(shí)，由于內(nèi)存中的每一頁(yè)在外存上都有一份副本，所以，若淘汰頁(yè)未被修改過，則不需要再將該頁(yè)寫到外存上；否則，必須將該頁(yè)重新寫回到磁盤。這樣淘汰未被修改的頁(yè)面，可以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；因此，可以同時(shí)使用頁(yè)表中的訪問位和修改位來(lái)對(duì)clock轉(zhuǎn)換算法進(jìn)行改進(jìn)。選擇未使用過的頁(yè)同時(shí)又是未修改過的頁(yè)面。（A=0、M=0）2023/1/31以段為單位進(jìn)行存儲(chǔ)管理的，首先要把用戶程序按一定的邏輯關(guān)系劃分成若干個(gè)段，且每個(gè)段具有完整的邏輯意義。每個(gè)程序段都有一個(gè)段名，每一段段內(nèi)也從0開始編址，段內(nèi)地址是連續(xù)的，而段與段的地址不一定連續(xù)，且各段長(zhǎng)度也不一定相等。4.4段式管理2023/1/312、邏輯地址結(jié)構(gòu)在用戶程序中，可通過段名和段內(nèi)符號(hào)名來(lái)確定一個(gè)地址。例如，給出（A，X）可確定一個(gè)地址。程序經(jīng)過編譯之后，段名用一個(gè)段號(hào)來(lái)代替，段內(nèi)符號(hào)名轉(zhuǎn)換成段內(nèi)地址。2023/1/31所以，邏輯地址由段號(hào)和段內(nèi)地址兩部分組成，是一個(gè)二維地址結(jié)構(gòu)。描述如下：段號(hào)段內(nèi)地址假定地址長(zhǎng)度為32位，其中段號(hào)占24~31位，段內(nèi)地址占0~23位，在該地址結(jié)構(gòu)中，用戶程序最多可分成256段，每段的長(zhǎng)度最大可達(dá)16MB。