操作系統(tǒng)概論第3章 存儲管理

1、重點：各種管理方式下的地址轉(zhuǎn)換；可變分區(qū)方式的主存分配算法以及移動技術(shù)；頁式虛擬存儲管理的實現(xiàn)以及頁面調(diào)度算法存儲器的層次結(jié)構(gòu)： RegisterCache和主存和主存磁盤磁盤處理機直接訪問I/O控制系統(tǒng)的管理 寄存器寄存器:最貴,最快,最小,每個只存儲一個字長,只放臨時的工作數(shù)據(jù)和控制信息 (指令寄存器, 通用寄存器,控制寄存器) 高速緩存高速緩存Cache：少量的、快速、昂貴、易變,以字節(jié)為單位編址 內(nèi)存內(nèi)存RAM：若干兆字節(jié)、中等速度、中等價格、易變 磁盤：磁盤：數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的 內(nèi)存的作用 為什么需要存儲管理？帕金森定律：你給程序再多內(nèi)存你給程序再多內(nèi)存,程序也

2、會程序也會想盡辦法耗光想盡辦法耗光 內(nèi)存管理概述內(nèi)存管理概述由存儲單元（字節(jié)或字）組成的一維連續(xù)地址空由存儲單元（字節(jié)或字）組成的一維連續(xù)地址空間，用來存放當前正在運行的程序的代碼或數(shù)據(jù)，間，用來存放當前正在運行的程序的代碼或數(shù)據(jù)，是程序中指令本身（程序計數(shù)器）所指向的存儲是程序中指令本身（程序計數(shù)器）所指向的存儲空間空間 操作系統(tǒng)的“方便”性便于用戶裝入程序，無須了解底層細節(jié)可實現(xiàn)動態(tài)的存儲空間伸縮，適應不同程序的需要 操作系統(tǒng)的“合理”性合理分配內(nèi)存空間，保證多道程序的順利運行合理保護內(nèi)存空間，防止各種可能的破壞泄漏 操作系統(tǒng)的“有效性”有效保持內(nèi)存空間的可用性，防止對資源的浪費有效實現(xiàn)“

3、小空間大容量”，提高計算機的適應性有效配合CPU的調(diào)度過程，實現(xiàn)系統(tǒng)運行的穩(wěn)定內(nèi)存管理概述內(nèi)存管理概述 內(nèi)存空間的管理、分配和回收內(nèi)存空間的使用情況記錄位圖、分配表、分區(qū)表內(nèi)存空間的分配與回收定長與不定長、靜態(tài)與動態(tài) 內(nèi)存空間的地址映射（轉(zhuǎn)換）物理地址與邏輯地址的差別 內(nèi)存空間的共享和保護內(nèi)存共享內(nèi)存保護：如何防止地址越界或操作越權(quán)？ 內(nèi)存空間的擴充虛擬存儲：如何使用小內(nèi)存空間來運行大的程序？(1) 邏輯地址（相對地址，虛地址）(2) 物理地址（絕對地址，實地址）(3) 地址映射(重定位)地址映射地址映射BA=1000Load A 200 3456 。 。 1200物理地址空間物理地址空間Lo

4、ad A data1data1 3456源程序源程序Load A 200 34560100200編譯連接編譯連接邏輯地址空間邏輯地址空間 用戶的程序經(jīng)過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式，其首地址為0，其余指令中的地址都相對于首地址而編址 不能用邏輯地址在內(nèi)存中讀取信息物理地址（絕對地址，實地址）物理地址（絕對地址，實地址）內(nèi)存中存儲單元的地址，可直接尋址以字節(jié)為單位進行編址 為了保證CPU執(zhí)行指令時可正確訪問存儲單元，需將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址，這一過程稱為重定重定位位110012001300物理地址空間物理地址空間03456.LOAD

5、 A 200.0100200300.LOAD A 2003456邏輯地址空間邏輯地址空間200VR+1000BR 原因: 當程序裝入內(nèi)存時, 操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致, 而CPU執(zhí)行指令時，是按物理地址進行的，所以要進行地址轉(zhuǎn)換地址轉(zhuǎn)換 當用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在連接裝配時由軟件完成） 在作業(yè)裝入過程中隨即進行的地址變換方式稱為靜態(tài)重定位或靜態(tài)地址映射mov r1,500123mov r1,500+m12301005005990mm+100256k-1作業(yè)地址空間作業(yè)地址空間存儲

6、空間存儲空間m+500重定位重定位裝入程序裝入程序 在程序運行過程中要訪問數(shù)據(jù)時再進行地址變換（即在逐條指令執(zhí)行時完成地址映射。一般為了提高效率，此工作由硬件地址映射機制來完成。硬件支持，軟硬件結(jié)合完成） 硬件上需要一對寄存器的支持在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪問自動地連續(xù)地進行地址映射mov r1,5001230100500599作業(yè)地址空間作業(yè)地址空間0 mov r1 , 500 1231000256k-1存儲空間存儲空間110015001600重定位寄存器重定位寄存器 1000500邏輯地址邏輯地址+ 靜態(tài)地址映射靜態(tài)地址映射 動態(tài)地址映射動態(tài)地址映射 在作業(yè)裝入過程中 在程序執(zhí)

7、行期間 進行地址映射 進行地址映射 需軟件 需硬件地址變換機構(gòu) 重定位裝入程序 重定位寄存器 需花費較多CPU時間 地址變換快 不靈活 靈活 單用戶系統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)存，故內(nèi)存分配管理十分簡單，內(nèi)存利用率低 內(nèi)存分為兩個區(qū)域，一個供操作系統(tǒng)使用，一個供用戶使用 單道運行的計算機系統(tǒng) 存儲保護:界限寄存器 分時系統(tǒng):對換方式 靜態(tài)定位方式 最簡單的管理方式（只有分配與回收）最簡單的管理方式（只有分配與回收）操作系統(tǒng)和用戶程序共享操作系統(tǒng)和用戶程序共享RAMRAM除了嵌入式系統(tǒng)外，其他的計算機不再使用這種方式除了嵌入式系統(tǒng)外，其他的計算機不再使用這種方式內(nèi)存管理概述內(nèi)存管理概述用戶

8、程序用戶程序RAM中的OS用戶程序用戶程序ROM中的OS用戶程序用戶程序RAM中的OSROM：DEV早期大型機早期大型機使用的內(nèi)存使用的內(nèi)存管理方式管理方式少數(shù)掌上電腦少數(shù)掌上電腦和嵌入式系統(tǒng)和嵌入式系統(tǒng)使用的內(nèi)存管使用的內(nèi)存管理方式理方式早期早期PC使用使用的內(nèi)存管理方的內(nèi)存管理方式（式（MS-DOS)系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)，系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)，分區(qū)大小可以相等，也可以不等。一分區(qū)大小可以相等，也可以不等。一個進程占據(jù)一個分區(qū)個進程占據(jù)一個分區(qū)固定分區(qū)固定分區(qū)可變分區(qū)可變分區(qū) 每個分區(qū)的大小可以相同也可以不同,但分區(qū)個數(shù)固定不變 每個分區(qū)裝一個且只能裝一個作業(yè) 存儲分配：

9、如果有一個空閑區(qū), 則分配給進程 如何實現(xiàn)內(nèi)存的分配與回收？已知內(nèi)存分區(qū)數(shù)為已知內(nèi)存分區(qū)數(shù)為N N，已知進程數(shù)為，已知進程數(shù)為M M，如何分配內(nèi)存？，如何分配內(nèi)存？關(guān)于回收：關(guān)于回收：OSOS維護的內(nèi)存分區(qū)表中應該有哪些信息？維護的內(nèi)存分區(qū)表中應該有哪些信息？ 內(nèi)存地址映射與存儲保護重定位問題與保護：物理地址和邏輯地址的映射關(guān)系重定位問題與保護：物理地址和邏輯地址的映射關(guān)系 內(nèi)存空間的擴充,提高主存空間利用率使用固定分區(qū)的形式可以實現(xiàn)內(nèi)存的擴充嗎？使用固定分區(qū)的形式可以實現(xiàn)內(nèi)存的擴充嗎？ 如何知道那個分區(qū)被占用,那個空閑分區(qū)分配表分區(qū)分配表: :說明各區(qū)的分配和使用情況說明各區(qū)的分配和使用情況

10、 分區(qū)分配表分區(qū)號分區(qū)號, ,起始位置起始位置, ,長度長度, ,占用標志占用標志 內(nèi)存的分配和回收修改標志位修改標志位分區(qū)號分區(qū)號 起始地址起始地址長度長度占用標志占用標志 地址轉(zhuǎn)換:靜態(tài)重定位(在調(diào)入內(nèi)存時直接修在調(diào)入內(nèi)存時直接修改指令改指令) 存儲保護: 引入界限寄存器(下限寄存器,上限寄存器) 下限寄存器=絕對地址上限寄存器 每個作業(yè)占用一個分區(qū),且只占用一部分 提高主存利用率: 根據(jù)經(jīng)常出現(xiàn)的作業(yè)的大小和數(shù)量來劃分分區(qū) 劃分分區(qū)時,按分區(qū)的大小順序排列.找到一個能滿足作業(yè)要求的最小空閑分區(qū)分配給作業(yè). 按作業(yè)對主存要求排成多個隊列:能有效防止小作業(yè)進入大分區(qū)分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分

11、區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)多個輸入隊列多個輸入隊列單個輸入隊列單個輸入隊列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)700K400K100K0 可能出現(xiàn)的作業(yè)大小 作業(yè)頻率 劃分不當:某個作業(yè)隊列長期為空,影響分區(qū)的使用效率 基本思想： 內(nèi)存不是預先劃分好的 作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配 若有足夠的空間，則按需要分割一部分分區(qū)給該進程；否則令其等待內(nèi)存空間- 分區(qū)的長度不是預先確定的，按需劃分- 分區(qū)的個數(shù)也不是預先確定的，是由裝入的作業(yè)數(shù)決定的 內(nèi)存的分配 根據(jù)作業(yè)對主存的需要量，從空閑區(qū)劃出一個與作業(yè)一致長度的分區(qū)來裝入作業(yè)，剩余部分認為空

12、閑區(qū) 當空閑區(qū)能滿足需求時，作業(yè)可裝入；超過，作業(yè)暫時不能轉(zhuǎn)入 20KB 0 os 作業(yè)作業(yè)1 作業(yè)作業(yè)2 作業(yè)作業(yè)3 作業(yè)作業(yè)4 52KB66KB130KB230KB256KB 1主存主存20KB 0 os 作業(yè)作業(yè)1 作業(yè)作業(yè)2 作業(yè)作業(yè)3 52KB66KB130KB256KB 1主存主存20KB 0 os 作業(yè)作業(yè)1 52KB256KB 1主存主存 0 os 256KB 1主存主存20KB20KB 0 os 作業(yè)作業(yè)1 作業(yè)作業(yè)2 52KB66KB256KB 1主存主存作業(yè)作業(yè)1申請申請 32KB作業(yè)作業(yè)2申請申請 14KB作業(yè)作業(yè)3申請申請 64KB作業(yè)作業(yè)4申請申請 100KB作業(yè)作

13、業(yè)5申請申請 50KB 內(nèi)存的回收： 當作業(yè)結(jié)束時，它的占用分區(qū)被收回。這個空閑區(qū)又可以根據(jù)新作業(yè)的大小重新用于分配，所以主存中的已占分區(qū)和空閑區(qū)的數(shù)目和大小都是在變化的 可以用 “空閑區(qū)表”來記錄和管理：記錄空閑區(qū)的起始地址和長度 20KB 0 os 作業(yè)作業(yè)1 作業(yè)作業(yè)2 作業(yè)作業(yè)3 作業(yè)作業(yè)4 52KB66KB130KB230KB256KB 1主存主存20KB 0 os 作業(yè)作業(yè)1 作業(yè)作業(yè)2 作業(yè)作業(yè)3 作業(yè)作業(yè)4 52KB66KB130KB230KB256KB 1主存主存20KB 0 os 作業(yè)作業(yè)1 作業(yè)作業(yè)2 作業(yè)作業(yè)3 作業(yè)作業(yè)4 52KB66KB130KB230KB256KB

14、 1主存主存作業(yè)作業(yè)2完成完成作業(yè)作業(yè)4完成完成 分區(qū)的分配與回收分區(qū)的分配與回收 1. 分區(qū)分配分區(qū)分配 用戶請求分配一個主存塊 分區(qū)分配程序在空閑塊隊列中找一個滿足找一個滿足用戶需要的空閑塊；用戶需要的空閑塊； 若找到，以空閑塊與請求的主存塊大小之間的關(guān)系進行相應的處理，并返回所分配區(qū)域的首址； 否則，告之不能滿足要求 主存分配策略主存分配策略 首次匹配(最先適應分配算法) 最佳匹配(最優(yōu)適應分配算法) 最壞匹配(最壞適應分配算法) 首次適應算法首次適應算法 (1) 什么是首次適應算法什么是首次適應算法 首次適應算法是將輸入的作業(yè)放置到主存里第一個足夠裝入它的可利用的空閑區(qū)中 (2) 特點

15、特點 空閑區(qū)地址由低到高排序 盡可能地利用存儲器中低地址的空閑區(qū)，而盡量保存高地址的空閑區(qū) 最佳適應算法最佳適應算法 (1) 什么是最佳適應算法什么是最佳適應算法 最佳適應算法是將輸入的作業(yè)放置到主存中與它所需大小最接近的空閑區(qū)中 (2) 特點特點 空閑區(qū)大小由小到大排序 盡可能地利用存儲器中小的空閑區(qū)，而盡量保存大的空閑區(qū) 最壞適應算法最壞適應算法 (1) 什么是最壞適應算法什么是最壞適應算法 最壞適應算法是將輸入的作業(yè)放置到主存中最不適合它的空閑區(qū)中 (3) 特點特點 空閑區(qū)大小由大到小排序 盡可能地利用存儲器中大的空閑區(qū)2. 分區(qū)回收分區(qū)回收 回收主存塊的四種情況回收主存塊的四種情況 r

16、 上鄰空閑區(qū)上鄰空閑區(qū)rf1作業(yè)作業(yè)2 r 上下鄰空閑區(qū)上下鄰空閑區(qū)rf1f2 r 上下鄰已分配區(qū)上下鄰已分配區(qū)r作業(yè)作業(yè)1作業(yè)作業(yè)2 r 下鄰空閑區(qū)下鄰空閑區(qū)r作業(yè)作業(yè)1f2 回收分區(qū)回收分區(qū)r 上鄰空閑區(qū)上鄰空閑區(qū) rf1作業(yè)作業(yè)2 f1作業(yè)作業(yè)2r與與 f1 合并合并成為一個大的空閑區(qū)成為一個大的空閑區(qū)f1 回收分區(qū)回收分區(qū)r 下鄰空閑區(qū)下鄰空閑區(qū)r與與 f2 合并合并成為一個大的空閑區(qū)成為一個大的空閑區(qū)f2 作業(yè)作業(yè)1f2 r作業(yè)作業(yè)1f2SS+LSS 回收分區(qū)回收分區(qū)r 上、下鄰空閑區(qū)上、下鄰空閑區(qū)r與與 f1 、 f1 合并合并成為一個大的空閑區(qū)成為一個大的空閑區(qū)f1 回收分區(qū)回收

17、分區(qū)r 上、下鄰分配區(qū)上、下鄰分配區(qū)r 成為一個成為一個新的空閑區(qū)新的空閑區(qū) f rf1f2 f1 r作業(yè)作業(yè)1作業(yè)作業(yè)2 f作業(yè)作業(yè)1作業(yè)作業(yè)2 采用動態(tài)重定位方式裝入作業(yè)，也就是每讀一條指令，都要變換一次地址 變換要靠硬件支持，主要是兩個寄存器：基址寄存器,限長寄存器以及加法線路，比較線路 基址寄存器基址寄存器則存放作業(yè)所占分區(qū)的起始地址，限長寄存器限長寄存器存放作業(yè)所占分區(qū)的最大地址，這兩個值確定了一個分區(qū)的位置和大小 P49 圖313 轉(zhuǎn)換時根據(jù)將邏輯地址加上基址寄存器中的值就得到了絕對地址 基址寄存器內(nèi)容絕對地址33級，最外層頁表常駐內(nèi)級，最外層頁表常駐內(nèi)存存 有利于主存的利用 地址

18、轉(zhuǎn)換時,增加訪問主存的次數(shù),影響執(zhí)行速度 使用高速緩存來加速一一. 段式地址空間段式地址空間 1. 什么是段什么是段 分段是程序中自然劃分的一組邏輯意義完整的信息集合 分段的例：代碼分段、數(shù)據(jù)分段、棧段 2. 作業(yè)地址空間作業(yè)地址空間 由若干個邏輯分段組成，每個分段有自己的名字，對于一個分段而言，它是一個連續(xù)的地址區(qū) 3. 段式地址空間段式地址空間 code_addr4KB10代碼分段data_addr3KB10數(shù)據(jù)分段stack_addr2KB10棧段 段 號 s 段 內(nèi) 位 移 w二二. 段式地址變換段式地址變換 長度 基址 L B s w -B+w第S段段號段內(nèi)位移段式地址變換的步驟如下： 取出程序地址(s，w) 用s檢索段表 如w0或wL則主存越界 (Bw)即為所需主存地址三三. 頁式系統(tǒng)與段式系統(tǒng)的區(qū)別頁式系統(tǒng)與段式系統(tǒng)的區(qū)別 1. 用戶地址空間的區(qū)別用戶地址空間的區(qū)別 頁式系統(tǒng)中用戶地址空間 一維地址空間一維地址空間 段式系統(tǒng)中用戶地址空間 二維地址空間維地址空間 2. 分段與頁面的區(qū)別分段與頁面的區(qū)別 分段分段 頁面頁面 信