《存儲(chǔ)管理》PPT課件.ppt

2019/7/3,1,計(jì)算機(jī)組成 和 操作系統(tǒng),第5章 存儲(chǔ)管理,5.1 存儲(chǔ)器概述,5.2 高速緩沖存儲(chǔ)器,5.3 內(nèi)存分配方式,5.1 存儲(chǔ)器概述,5.1.1 存儲(chǔ)器的分類 5.1.2 存儲(chǔ)器的性能指標(biāo) 5.1.3 存儲(chǔ)器的組成與工作原理 5.1.4 存儲(chǔ)器的層次結(jié)構(gòu),4,5.1.1 存儲(chǔ)器分類,按存儲(chǔ)器的器件和存儲(chǔ)介質(zhì)分類 按存取方式分類 按存儲(chǔ)器在計(jì)算機(jī)中的作用分類,5,1. 按存儲(chǔ)器的器件和存儲(chǔ)介質(zhì)分類,半導(dǎo)體存儲(chǔ)器：由半導(dǎo)體器件組成 雙極型存儲(chǔ)器、MOS型半導(dǎo)體集成電路存儲(chǔ)器 速度快、功耗低 磁存儲(chǔ)器：由磁性材料做成 磁芯、磁帶、磁盤等 容量大，速度慢、體積大 光存儲(chǔ)器：用光學(xué)材料根據(jù)光學(xué)原理存儲(chǔ)信息 CD-ROM、DVD-ROM 便于攜帶，廉價(jià)，易于保存,6,順序存儲(chǔ)器（SAM） 所存儲(chǔ)的內(nèi)容只能按某種順序存取 存取所需時(shí)間與物理位置有關(guān) 順序存儲(chǔ)器的平均存取周期較長(zhǎng)，一般用于輔存 隨機(jī)存儲(chǔ)器（RAM） 存儲(chǔ)器中的任意存儲(chǔ)單元都能隨機(jī)存取 存取所需時(shí)間與物理位置無(wú)關(guān) 主存主要由RAM組成,2.按存取方式分類,7,直接存取存儲(chǔ)器（DAM） 介于隨機(jī)和順序之間 隨機(jī)定位信息塊，但對(duì)信息塊是順序讀寫 只讀存儲(chǔ)器 (ROM) 存儲(chǔ)器內(nèi)容是預(yù)置的，固定的，無(wú)法改寫 信息可長(zhǎng)期保存,2.按存取方式分類（續(xù)）,8,主存儲(chǔ)器 速度快，容量小，價(jià)格高 目前主要采用半導(dǎo)體存儲(chǔ)器 輔助存儲(chǔ)器 速度低，容量大，價(jià)格便宜 目前主要有磁盤、光盤、閃存、磁盤陣列 高速緩沖存儲(chǔ)器 Cache 放置在兩個(gè)訪問(wèn)速度不一樣的存儲(chǔ)部件之間，用來(lái)暫存信息和數(shù)據(jù),3.按存儲(chǔ)器在計(jì)算機(jī)中的作用分類,9,存儲(chǔ)容量：一般以字節(jié)為單位。 存取速度：取數(shù)時(shí)間和存取周期。 價(jià)格：用單位存儲(chǔ)空間的價(jià)格來(lái)衡量。 可靠性：用平均無(wú)故障時(shí)間來(lái)衡量。,5.1.2 主存儲(chǔ)器的主要性能指標(biāo),10,5.1.3 存儲(chǔ)器組成與工作原理,存儲(chǔ)器的組成,存儲(chǔ)單元及其編址,5.1.3 存儲(chǔ)器組成與工作原理,主存的組成和工作原理,分析：速度越快，成本較高。 為了獲得好的性能/價(jià)格比，計(jì)算機(jī)中各種存儲(chǔ)器組成一個(gè)層狀的塔式結(jié)構(gòu)，取長(zhǎng)補(bǔ)短，協(xié)調(diào)工作 工作過(guò)程： 1）CPU運(yùn)行時(shí)，需要的操作數(shù)大部分來(lái)自寄存器 2）如需要從(向)存儲(chǔ)器中取(存) 數(shù)據(jù)時(shí)，先訪問(wèn)cache，如在，取自cache 3）如操作數(shù)不在cache，則訪問(wèn)RAM，如在RAM中，則取自RAM 4）如操作數(shù)不在RAM，則訪問(wèn)硬盤，操作數(shù)從硬盤中讀出RAM cache,5.1.4 存儲(chǔ)器的層次結(jié)構(gòu),13,5.2 高速緩沖存儲(chǔ)器,為什么需要高速緩存？ CPU與存儲(chǔ)器之間的速度無(wú)法匹配 解決之道 采用高速器件提高速度 增加字長(zhǎng)，在每個(gè)存儲(chǔ)周期中存取多個(gè)字 增加cache,14,高速緩存的理論依據(jù)程序局部性原理 程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域，包括： 時(shí)間局部性 指令的執(zhí)行和數(shù)據(jù)的訪問(wèn)集中在一個(gè)較短時(shí)期內(nèi) 空間局部性 指令的執(zhí)行和數(shù)據(jù)的訪問(wèn)集中在一個(gè)較小區(qū)域內(nèi)。,15,程序局部性原理的具體體現(xiàn)： 程序在執(zhí)行時(shí)，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過(guò)程調(diào)用指令。 程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。 程序中存在相當(dāng)多對(duì)一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。,5.2.1 Cache系統(tǒng)的基本結(jié)構(gòu),Cache系統(tǒng)組成 Cache 地址映像與變換機(jī)構(gòu) Cache替換策略和更新策略,16,17,5.2.2 cache系統(tǒng)的工作原理,5.2.2 cache系統(tǒng)的工作原理,1.直接映像（direct mapping）,主存和Cache 中字塊的對(duì)應(yīng)關(guān)系采用直接映像函數(shù)為： j=i mod 2c 其中，j 是Cache 的字塊號(hào)，i是主存的字塊號(hào)。在這種映像關(guān)系中，主存的第0塊，第2c塊，第2c+1塊，只能映像到Cache的第0塊，而主存的第1塊，第2c+1塊，第2c+1+1塊，只能映像到Cache 的第1 塊。,直接映像的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單,直接映像方式的缺點(diǎn)是不夠靈活,5.2.2 cache系統(tǒng)的工作原理,2全相聯(lián)映像(fully associative mapping),主存地址分為兩段：主存字段標(biāo)記mtc 位、塊內(nèi)地址b 位 Cache 地址也分為兩段：塊地址c 位、塊內(nèi)地址b 位。 主存塊內(nèi)地址與Cache地址塊內(nèi)地址相同,全相聯(lián)映像方式的優(yōu)點(diǎn)是可以靈活地進(jìn)行塊的分配，塊的沖突率低，Cache 的利用率高。但這是一個(gè)理想的方案。實(shí)際上由于它的成本太高而不能采用,5.2.2 cache系統(tǒng)的工作原理,3. 組相聯(lián)映像（set associative mapping）,組相聯(lián)映像方式是直接映像和全相聯(lián)映像方式的一種折中方案。,組相聯(lián)映像把主存地址劃分成4 段 Cache 地址分為三段,5.3 內(nèi)存分配方式,5.3.1 連續(xù)分配存儲(chǔ)管理方式 5.3.2 分頁(yè)式存儲(chǔ)管理 5.3.3 段式存儲(chǔ)管理 5.3.4 段頁(yè)式存儲(chǔ)管理 5.3.5 虛擬存儲(chǔ)管理 5.3.6 各種存儲(chǔ)分配策略的比較,21,22,補(bǔ)充:程序的裝入與鏈接,編譯 源代碼目標(biāo)代碼 鏈接 目標(biāo)代碼+所需庫(kù)函數(shù)=裝入模塊 裝入 將裝入模塊裝入內(nèi)存，該過(guò)程也叫做地址重定位，也稱地址映射,地址空間：源程序經(jīng)編譯后得到的目標(biāo)程序，存在于它所限定的地址范圍內(nèi)，此范圍稱地址空間。地址空間是邏輯地址的集合。 存儲(chǔ)空間：指主存中一系列存儲(chǔ)信息的物理單元的集合，這些單元的編號(hào)稱為物理地址。存儲(chǔ)空間是物理地址的集合。,程序的裝入方式,重定位（地址映射）： 把用戶程序中的相對(duì)地址（邏輯地址）轉(zhuǎn)換為主存中的絕對(duì)地址（物理地址）過(guò)程。 靜態(tài)重定位： 編譯時(shí)產(chǎn)生相對(duì)地址，裝入程序確定要裝入模塊的地址，并在裝入時(shí)進(jìn)行重定位，程序運(yùn)行中不允許在內(nèi)存移動(dòng)。 動(dòng)態(tài)重定位 編譯時(shí)產(chǎn)生相對(duì)地址，裝入程序在把裝入模塊裝入內(nèi)存時(shí)，不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是推遲到程序要真正執(zhí)行時(shí)才進(jìn)行。,靜態(tài)重定位示意圖,動(dòng)態(tài)重定位示意圖,程序的鏈接方式,靜態(tài)鏈接 對(duì)相對(duì)地址進(jìn)行修改 變換外部調(diào)用符號(hào) 裝入時(shí)動(dòng)態(tài)鏈接 在裝入內(nèi)存時(shí)，邊裝入邊鏈接 便于軟件版本的修改和更新 便于實(shí)現(xiàn)目標(biāo)模塊共享 運(yùn)行時(shí)動(dòng)態(tài)鏈接 運(yùn)行時(shí)，用到哪個(gè)模塊，再鏈接哪個(gè)模塊，用不到的模塊可不裝入內(nèi)存。,程序的鏈接,28,連續(xù)分配是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。分為： 單一連續(xù)分配 固定分區(qū) 可變分區(qū),5.3.1 連續(xù)分配存儲(chǔ)管理,單一連續(xù)分配,應(yīng)用范圍：?jiǎn)斡脩?、單任?wù)操作系統(tǒng)。如：CP/M、DOS2.0以下。 操作系統(tǒng)的任務(wù)就是將系統(tǒng)程序和用戶程序分開(kāi)。 方法：用基址-限長(zhǎng)寄存器。,固定分區(qū)存儲(chǔ)管理,方法 分區(qū)在系統(tǒng)啟動(dòng)后劃分好，以后不能改變。 應(yīng)用范圍： 多道程序設(shè)計(jì)系統(tǒng)最簡(jiǎn)單的一種方式。如：60年代的IBM360上的MFT。 劃分分區(qū)方法 分區(qū)大小相等 分區(qū)大小不等 缺點(diǎn) 內(nèi)存利用率低,可變分區(qū)存儲(chǔ)管理,方法 分區(qū)的大小和個(gè)數(shù)隨系統(tǒng)的運(yùn)行而不斷改變,可變分區(qū)分配數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表 空閑分區(qū)鏈 可變分區(qū)分配算法 首次適應(yīng)法 下次適應(yīng)法 最佳適應(yīng)法 最壞適應(yīng)法 可變分區(qū)的分配和回收操作,可變分區(qū)存儲(chǔ)管理,條件 空閑分區(qū)鏈以存儲(chǔ)空間地址遞增的次序鏈接。 優(yōu)點(diǎn) 釋放時(shí)，因不改變?cè)搮^(qū)在隊(duì)列中的位置，因此速度快。 保證高地址有空閑空間，可留給大作業(yè)。 缺點(diǎn) 常用大空閑區(qū)適應(yīng)小作業(yè)，從而留下小空閑區(qū)，且這些小空閑區(qū)在鏈表的前面，影響分配速度。,可變分區(qū)分配算法,最佳適應(yīng)法,首次適應(yīng)法,下次適應(yīng)法,最壞適應(yīng)法,條件 空閑分區(qū)鏈以存儲(chǔ)空間地址遞增的次序連接成循環(huán)鏈，為進(jìn)程分配存儲(chǔ)空間時(shí)，不是從隊(duì)首開(kāi)始找，而是從上次找到的空閑空間的下一個(gè)空閑分區(qū)開(kāi)始找。 優(yōu)點(diǎn) 存儲(chǔ)空間利用均衡。 缺點(diǎn) 沒(méi)有了較大空閑空間，使大作業(yè)無(wú)法運(yùn)行。,條件 空閑分區(qū)鏈以存儲(chǔ)空間大小遞增的次序拉鏈。 優(yōu)點(diǎn) 若存儲(chǔ)空間中存在與申請(qǐng)大小相等的空閑區(qū)，則必然被選中，否則選一個(gè)稍大的空閑區(qū)，而避免毀掉更大的空閑區(qū)。 缺點(diǎn) 小碎片增加碎片問(wèn)題嚴(yán)重。 回收時(shí)，將空閑區(qū)插入適當(dāng)?shù)奈恢觅M(fèi)時(shí)。,條件 空閑分區(qū)鏈以存儲(chǔ)空間大小遞減的次序拉鏈。 優(yōu)點(diǎn) 分配后，剩下的空閑區(qū)還好用。 申請(qǐng)時(shí)，查找容易，因此速度快。 缺點(diǎn) 當(dāng)有大作業(yè)時(shí)，可能就沒(méi)有空間可用了。,可變分區(qū)內(nèi)存的回收,回收分區(qū)與前面一個(gè)（低地址）空閑分區(qū)F1相鄰接，圖（a） 回收分區(qū)與后面一個(gè)（高地址）空閑分區(qū)F2相鄰接，圖（b） 回收分區(qū)與前、后兩個(gè)空閑分區(qū)F1和F2均相鄰，圖（c） 回收分區(qū)不與其它空閑分區(qū)相鄰接,離散分配方式的引入,連續(xù)分配方式帶來(lái)的問(wèn)題是會(huì)在存儲(chǔ)空間中產(chǎn)生許多“碎片”。 能否將進(jìn)程分配到許多不相鄰的分區(qū)中呢？由此產(chǎn)生離散分配方式。 分頁(yè)存儲(chǔ)管理方式 存儲(chǔ)管理的需要 分段存儲(chǔ)管理方式 用戶編程的需要,基本原理 將進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁(yè)面或頁(yè)； 內(nèi)存空間分成與頁(yè)大小相等的若干個(gè)存儲(chǔ)塊，稱為物理塊或頁(yè)框。 在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位，將進(jìn)程中的若干頁(yè)分別裝入多個(gè)可以不相鄰的塊中。,5.3.2 分頁(yè)式存儲(chǔ)管理,頁(yè)面的大小由機(jī)器的地址結(jié)構(gòu)決定的。 頁(yè)面的大小的權(quán)衡 頁(yè)面較小-內(nèi)存碎片??；頁(yè)表過(guò)長(zhǎng)，占用較大內(nèi)存空間。 頁(yè)面較大-頁(yè)表短，占用較少內(nèi)存；內(nèi)存碎片大。 通常頁(yè)面的大小要適中，在512KB4MB之間。,頁(yè)面大小的選擇,邏輯地址被分為兩部分： 頁(yè)號(hào) 頁(yè)內(nèi)位移 例如邏輯地址1500的二進(jìn)制形式為0000 0101 1101 1100 由于頁(yè)的大小為1024B，故頁(yè)內(nèi)位移占10位，剩下6位為頁(yè)號(hào) 邏輯地址1500對(duì)應(yīng)的頁(yè)號(hào)為1（二進(jìn)制為0000 01） 頁(yè)內(nèi)位移為476（二進(jìn)制為01 1101 1100）,頁(yè)式存儲(chǔ)管理邏輯地址結(jié)構(gòu),頁(yè)式存儲(chǔ)管理地址變換機(jī)構(gòu),快表,由于頁(yè)表放在內(nèi)存，使得CPU存取一個(gè)數(shù)據(jù)時(shí)，要兩次訪問(wèn)內(nèi)存，為了提高速度，增設(shè)快表（高速緩存）。,方便編程 分段共享 分段保護(hù) 動(dòng)態(tài)鏈接 動(dòng)態(tài)增長(zhǎng),引入原因,5.3.3 段式存儲(chǔ)管理,段式存儲(chǔ)管理的基本原理,整個(gè)作業(yè)的地址空間被分成若干個(gè)段，每個(gè)段采用一段連續(xù)的地址空間，段的長(zhǎng)度由相應(yīng)的邏輯信息的長(zhǎng)度決定。,段式存儲(chǔ)管理地址變換機(jī)構(gòu),分頁(yè)和分段的區(qū)別,分頁(yè)和分段的目的 頁(yè)是信息的物理單位，分頁(yè)是系統(tǒng)管理的需要，而不是用戶的需要。 段是信息的邏輯單位，它含一組意義完整的信息。分段是為了更好地滿足用戶的要求。 頁(yè)和段長(zhǎng)度 頁(yè)的大小固定，由系統(tǒng)確定。 段的長(zhǎng)度不固定，決定于用戶所編寫的程序。 地址空間 分頁(yè)的作業(yè)地址空間是一維的，即單一的線性地址空間。 分段的作業(yè)地址空間是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，需給出段名和段內(nèi)地址。,段的共享與保護(hù),頁(yè)共享與段共享的比較 由于段是信息的邏輯單位，用戶易于實(shí)現(xiàn)對(duì)段的共享，也容易對(duì)段進(jìn)行保護(hù)。 而頁(yè)雖也可共享，但不方便。 舉例 例如有一個(gè)多用戶系統(tǒng)，可同時(shí)容納40個(gè)用戶，它們都執(zhí)行一個(gè)文本編輯程序，該文本編輯程序含有160KB的代碼和40KB的數(shù)據(jù)， 如不共享，共需160*40+40*40=8MB的內(nèi)存空間來(lái)支持40個(gè)用戶。 若代碼是可重入的，則無(wú)論是分頁(yè)系統(tǒng)還是分段系統(tǒng)都可以共享該代碼段，因此內(nèi)存只需留一個(gè)文本編輯程序，所需空間為160+40*40=1760KB。,頁(yè)的共享,注意： 頁(yè)的共享要求作業(yè)地址空間的共享頁(yè)必須具有相同的頁(yè)號(hào)。,使用分頁(yè)系統(tǒng)，每個(gè)頁(yè)面的大小是4KB，則代碼段占160/4=40個(gè)頁(yè)面，數(shù)據(jù)段占40/4=10個(gè)頁(yè)面,段的共享,使用分段系統(tǒng)，不要求段號(hào)相同。,實(shí)現(xiàn)段的共享數(shù)據(jù)結(jié)構(gòu),共享進(jìn)程計(jì)數(shù)：記錄了共享某段的進(jìn)程個(gè)數(shù)，設(shè)置整型變量count。 存取控制：對(duì)于一個(gè)共享，不同的進(jìn)程可以有不同的存取控制權(quán)限。 段號(hào)：對(duì)于同一共享段，不同的進(jìn)程可以使用不同的段號(hào)去共享該段。,分段的分配與回收,分配,回收,對(duì)第一個(gè)請(qǐng)求使用該共享段的進(jìn)程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時(shí)將該區(qū)的始址填入該進(jìn)程的段表的相應(yīng)項(xiàng)中。 在共享段表中增加一表項(xiàng)，填寫有關(guān)數(shù)據(jù)，置count=1；當(dāng)其他進(jìn)程要調(diào)用該共享段時(shí)，無(wú)需再分配內(nèi)存，只需在調(diào)用進(jìn)程的段表中增加一表項(xiàng)，在共享段表中，填加進(jìn)程的名字等項(xiàng)目，令count加1。,當(dāng)進(jìn)程不使用某共享段時(shí)，刪除共享段表中有關(guān)該進(jìn)程的項(xiàng)目，令count減1，當(dāng)count=0時(shí)，回收該共享段的物理內(nèi)存，刪除共享段表中對(duì)應(yīng)項(xiàng)。,分頁(yè)系統(tǒng)能有效地提高內(nèi)存的利用率解決外部碎片問(wèn)題。 分段系統(tǒng)則能更好地滿足用戶編程的需要解決段的共享、動(dòng)態(tài)連接等問(wèn)題。 將兩者結(jié)合起來(lái)，汲取兩著的優(yōu)點(diǎn)，產(chǎn)生段頁(yè)式存儲(chǔ)管理。,5.3.4 段頁(yè)式存儲(chǔ)管理,段頁(yè)式地址變換機(jī)構(gòu),頁(yè)的大?。?KB 5*4KB+500B =20980,52,前面所介紹的各種存儲(chǔ)器管理方式，都要求將一個(gè)作業(yè)全部裝入內(nèi)存方能運(yùn)行，因而難以適應(yīng)： 作業(yè)的尺寸大于實(shí)際內(nèi)存的容量； 有大量的作業(yè)等待運(yùn)行，但實(shí)際內(nèi)存容量不足以使其全部裝入； 為解決此類問(wèn)題，引入了虛擬存儲(chǔ)器，其理論依據(jù)是進(jìn)程運(yùn)行的局部性原理。,5.3.5 虛擬存儲(chǔ)管理,53,1.虛擬存儲(chǔ)技術(shù) 虛擬存儲(chǔ)器是一種借助于外存空間，從而允許一個(gè)進(jìn)程在其運(yùn)行過(guò)程中部分地裝入內(nèi)存的技術(shù)。 2.虛擬存儲(chǔ)的基本原理 程序部分裝入 在程序執(zhí)行過(guò)程中產(chǎn)生缺頁(yè)或缺段，請(qǐng)求調(diào)入 將暫時(shí)不使用的頁(yè)或段置換到到外存 3.虛擬存儲(chǔ)器的實(shí)現(xiàn)方式 建立在離散分配存儲(chǔ)管理方式的基礎(chǔ)上。,54,基本分頁(yè)系統(tǒng)+請(qǐng)求調(diào)