操作系統(tǒng)內(nèi)存ppt課件

1、5、內(nèi)存內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式存儲(chǔ)器的多層結(jié)構(gòu)多層結(jié)構(gòu)存儲(chǔ)器系統(tǒng)產(chǎn)生的原因：無(wú)法同時(shí)滿足三個(gè)條件：存儲(chǔ)器的速度與處理機(jī)的速度相匹配因?yàn)樵S多指令涉及存儲(chǔ)器訪問(wèn)）存儲(chǔ)器具有非常大的容量存儲(chǔ)器的價(jià)格很便宜存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)寄存器、高速緩存：少量的、非常快速、昂貴、易變；高速緩存是介于寄存器和存儲(chǔ)器之間的存儲(chǔ)器主存儲(chǔ)器：GB級(jí)、中等速度、中等價(jià)格、易變磁盤緩存：依托于固定磁盤，提供對(duì)主存儲(chǔ)器存儲(chǔ)空間的擴(kuò)充寄存器和主存包括高速緩存、主存儲(chǔ)器、

2、磁盤緩存又被稱為可執(zhí)行存儲(chǔ)器磁盤、可移動(dòng)存儲(chǔ)介質(zhì)：GB級(jí)到PB級(jí)、低速、價(jià)廉、不易變內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式對(duì)用戶程序的處理步驟絕對(duì)裝入方式程序中的邏輯地址和實(shí)際內(nèi)存地址一致適用于僅能運(yùn)行單道程序的小系統(tǒng)程序中的絕對(duì)地址可由程序員直接給出要求熟悉內(nèi)存使用數(shù)據(jù)結(jié)構(gòu)或程序修改后可能要改程序中的很多處地址絕對(duì)地址也可由程序編譯器轉(zhuǎn)換得出靜態(tài)重定位裝入方式程序中的邏輯地址從0地址開始適用于多道程序環(huán)境地址轉(zhuǎn)換在程序裝入時(shí)一次完成，不再改變動(dòng)態(tài)重定位裝入方式

3、靜態(tài)裝入不適用于進(jìn)程切換，每次換入的內(nèi)存位置可能不同程序裝入時(shí)保留相對(duì)地址，程序執(zhí)行時(shí)進(jìn)行地址轉(zhuǎn)換需要重定位寄存器加速地址轉(zhuǎn)換程序的靜態(tài)鏈接方式在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝配模塊，以后不再拆開。程序的靜態(tài)鏈接方式修改各模塊的起始地址修改模塊中所有涉及相對(duì)地址的指令程序裝入時(shí)的動(dòng)態(tài)鏈接方式程序編譯后所得到的一組目標(biāo)模塊，裝入目標(biāo)模塊時(shí)，若發(fā)生外部模塊調(diào)用，裝入程序?qū)⑼獠磕K調(diào)入內(nèi)存，同時(shí)修改目標(biāo)模塊中的相對(duì)地址。優(yōu)點(diǎn)： 便于修改和更新：因?yàn)楦髂繕?biāo)模塊是分開存放的。 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享：OS很容易將一個(gè)目標(biāo)模塊，鏈接到幾個(gè)應(yīng)用模塊上，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)?/p>

4、該模塊的共享。 程序運(yùn)行時(shí)的動(dòng)態(tài)鏈接方式某些模塊有時(shí)不需要運(yùn)行，如異常處理模塊。需要用到的模塊才進(jìn)行鏈接。優(yōu)點(diǎn)： 加快程序的裝入過(guò)程：凡在執(zhí)行過(guò)程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上。節(jié)省內(nèi)存空間：僅裝入運(yùn)行所需要的模塊。 內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式連續(xù)分配存儲(chǔ)管理方式連續(xù)分配指為一個(gè)程序分配一個(gè)連續(xù)的內(nèi)存空間。連續(xù)分配方式分為四類：?jiǎn)我贿B續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配單一連續(xù)分配單道程序環(huán)境下內(nèi)存分為系統(tǒng)區(qū)和

5、用戶區(qū)系統(tǒng)區(qū)僅提供給OS使用，在內(nèi)存的低址部分用戶區(qū)僅裝有一道用戶程序，即整個(gè)內(nèi)存的用戶空間由該程序獨(dú)占缺點(diǎn)：不支持多道 主存利用率不高 程序的運(yùn)行受主存容量限制 固定分區(qū)分配多道程序環(huán)境下整個(gè)用戶空間劃分為若干個(gè)固定大小的區(qū)域每個(gè)分區(qū)中只裝入一道作業(yè)固定分區(qū)分配劃分分區(qū)的方法分區(qū)大小相等：所有的內(nèi)存分區(qū)大小相等，缺點(diǎn)是缺乏靈活性. 分區(qū)大小不等：存儲(chǔ)器分區(qū)劃分為若干個(gè)大小不等的分區(qū). 固定分區(qū)分配內(nèi)存分配建立分區(qū)使用表，記錄每個(gè)分區(qū)的起始地址、大小及狀態(tài)是否已分配）。當(dāng)用戶程序裝入時(shí)，由內(nèi)存分配程序依據(jù)程序大小檢索該表，從中找出一個(gè)能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項(xiàng)

6、中的狀態(tài)置為“已分配”。 若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。 若每個(gè)分區(qū)的大小固定，會(huì)造成存儲(chǔ)空間浪費(fèi)。 固定分區(qū)分配動(dòng)態(tài)分區(qū)分配根據(jù)進(jìn)程的實(shí)際需要?jiǎng)討B(tài)分配內(nèi)存空間動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 動(dòng)態(tài)分區(qū)分配算法 分區(qū)分配操作動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表或空閑分區(qū)鏈動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配算法傳統(tǒng)的順序式搜索算法索引式搜索算法動(dòng)態(tài)分區(qū)分配分區(qū)分配操作分配內(nèi)存：根據(jù)分配算法，從空閑分區(qū)表中找到合適的分區(qū)。若分區(qū)大小比請(qǐng)求空間大超過(guò)分區(qū)最小極限值），則對(duì)分區(qū)進(jìn)行分割?；厥諆?nèi)存：當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首地址，合并回收進(jìn)空閑分區(qū)表回收區(qū)與插入點(diǎn)的前一

7、個(gè)空閑分區(qū)F1相鄰接回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接回收區(qū)既不與F1鄰接，又不與F2鄰接基于順序搜索的分區(qū)分配算法為了實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配，通常是將系統(tǒng)中的空閑分區(qū)鏈接成一個(gè)鏈。順序搜索，是指依次搜索空閑分區(qū)鏈上的空閑分區(qū)，尋找一個(gè)大小能滿足要求的分區(qū)。 首次適應(yīng)算法：選擇分區(qū)時(shí)總是按地址從高到低搜索。循環(huán)首次適應(yīng)算法：類似首次適應(yīng)法每次分區(qū)時(shí)，總是從上次查找結(jié)束的地方開始。最佳適應(yīng)算法：在空閑塊表中找到一個(gè)不小于請(qǐng)求的最小空塊進(jìn)行分配 最壞適應(yīng)算法：在空閑塊表中找到一個(gè)不小于請(qǐng)求的最大空塊進(jìn)行分配基于索引搜索的分區(qū)分配算法當(dāng)系統(tǒng)很大時(shí)，系統(tǒng)中的內(nèi)存分

8、區(qū)可能會(huì)很多，相應(yīng)的空閑分區(qū)鏈就可能很長(zhǎng)，這時(shí)采用順序搜索分區(qū)方法可能會(huì)很慢。 快速適應(yīng)算法：相同容量的分區(qū)使用一個(gè)空閑分區(qū)鏈表，所有鏈表的頭指針通過(guò)一張管理索引表訪問(wèn)。根據(jù)進(jìn)程長(zhǎng)度從索引表中找到合適的空閑分區(qū)鏈表從鏈表中取第一塊分區(qū)進(jìn)行分配，不對(duì)分區(qū)進(jìn)行分割時(shí)間性能比順序搜索高，空間利用存在浪費(fèi)基于索引搜索的分區(qū)分配算法伙伴系統(tǒng)：初始內(nèi)存是一個(gè)大小為2m的空閑分區(qū)，分區(qū)可以對(duì)半分割，分區(qū)大小均為2 的k次冪。若申請(qǐng)長(zhǎng)度為n的內(nèi)存空間2i-1i，則把空閑塊分為2j-1、2j-2、2i、2i的塊，并把其中2i的塊分配給進(jìn)程。若回收大小為2i的空閑塊，要查詢是否存在另一個(gè)大小為2i的空閑塊，若有則

9、需合并成2i+1的空閑塊。時(shí)間性能高于順序搜索，低于快速適應(yīng)算法。空間利用率優(yōu)于快速適應(yīng)算法，低于順序搜索。多處理機(jī)系統(tǒng)中廣泛應(yīng)用。基于索引搜索的分區(qū)分配算法哈希算法：改良上述兩種索引搜索方法。原因：“根據(jù)申請(qǐng)空間查找對(duì)應(yīng)的空閑分區(qū)鏈表表頭指針這個(gè)操作當(dāng)表項(xiàng)多時(shí)速度慢算法先構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，再根據(jù)所需空閑分區(qū)大小，通過(guò)哈希函數(shù)計(jì)算，得到在哈希表中的位置，從而得到響應(yīng)的空閑分區(qū)鏈表。可重定位分區(qū)分配連續(xù)分配方式的特點(diǎn)：一個(gè)程序必須裝入一片連續(xù)的內(nèi)存空間。當(dāng)計(jì)算機(jī)運(yùn)行一段時(shí)間后，內(nèi)存空間將會(huì)分割成許多小分區(qū)，缺乏大的空閑空間。裝入大作業(yè)的方法：移動(dòng)內(nèi)存中的所有作業(yè)使之相鄰。這

10、樣把原來(lái)分散的多個(gè)小分區(qū)拼接成一個(gè)大分區(qū)，就可把大作業(yè)裝入。 技術(shù)需求：緊湊、動(dòng)態(tài)重定位、動(dòng)態(tài)重定位分區(qū)分配算法 可重定位分區(qū)分配緊湊可重定位分區(qū)分配動(dòng)態(tài)重定位可重定位分區(qū)分配 返回分區(qū)號(hào)和首地址動(dòng)態(tài)重定位分區(qū)分配算法 內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式對(duì)換又稱為交換技術(shù)，在內(nèi)存和外存間交換數(shù)據(jù)，用于解決內(nèi)存太小的問(wèn)題。早期的分時(shí)系統(tǒng)中的對(duì)換技術(shù)：所有的用戶作業(yè)放在磁盤上，每次調(diào)一個(gè)作業(yè)進(jìn)內(nèi)存，當(dāng)時(shí)間片用完后再調(diào)至外存的后備隊(duì)列，再?gòu)暮髠潢?duì)列中調(diào)另一個(gè)作業(yè)進(jìn)

11、內(nèi)存。已廢棄。多道程序環(huán)境多道程序環(huán)境：內(nèi)存中的某些進(jìn)程由于某事件尚未發(fā)生而被阻塞運(yùn)行，但占用大量?jī)?nèi)存空間，甚至可能出現(xiàn)內(nèi)存中所有進(jìn)程都被阻塞。某些進(jìn)程因內(nèi)存空間不足，一直不能運(yùn)行把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)換出到外存上；再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)換入內(nèi)存。 對(duì)換的類型 整體對(duì)換：即處理機(jī)中級(jí)調(diào)度。以進(jìn)程為對(duì)換單位。頁(yè)面分段對(duì)換 ：以進(jìn)程的 “頁(yè)面或“分段為單位進(jìn)行對(duì)換。為實(shí)現(xiàn)進(jìn)程對(duì)換，系統(tǒng)必須實(shí)現(xiàn)的功能: 對(duì)換空間管理進(jìn)程的換出進(jìn)程的換入對(duì)換空間管理在具有對(duì)換功能的OS中，通常把硬盤空間分為文件區(qū)和對(duì)換區(qū)兩部分。文件區(qū)占大部分，訪問(wèn)頻率低。交換區(qū)占

12、小部分，用于存放內(nèi)存中換出的進(jìn)程。對(duì)換空間管理的主要目標(biāo)：文件區(qū)管理的主要目標(biāo)：首先是提高文件存儲(chǔ)空間的利用率，然后才是提高對(duì)文件的訪問(wèn)速度對(duì)換空間管理的主要目標(biāo)：是提高進(jìn)程換入和換出的速度，然后才是提高文件存儲(chǔ)空間的利用率.對(duì)換空間管理對(duì)換區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表的每個(gè)表目中，應(yīng)包含兩項(xiàng)：對(duì)換區(qū)的首址及其大小，分別用盤塊號(hào)和盤塊數(shù)表示。對(duì)換空間管理對(duì)換空間的分配與回收由于對(duì)換分區(qū)的分配采用的是連續(xù)分配方式，因而對(duì)換空間的分配與回收，與動(dòng)態(tài)分區(qū)方式時(shí)的內(nèi)存分配與回收方法雷同。分配算法可以是首次適應(yīng)算法

13、、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法等.進(jìn)程的換出選擇被換出的進(jìn)程 首先選擇處于阻塞狀態(tài)或睡眠狀態(tài)的進(jìn)程其次選擇優(yōu)先級(jí)最低的進(jìn)程 進(jìn)程換出過(guò)程 申請(qǐng)對(duì)換空間。若申請(qǐng)成功就啟動(dòng)磁盤，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換區(qū)上。若傳送過(guò)程未出現(xiàn)錯(cuò)誤，則回收進(jìn)程所占用的內(nèi)存空間，并對(duì)進(jìn)程控制塊和內(nèi)存分配表等數(shù)據(jù)結(jié)構(gòu)做相應(yīng)的修改。若內(nèi)存中還有阻塞進(jìn)程，則繼續(xù)執(zhí)行換出過(guò)程。進(jìn)程的換入 對(duì)換進(jìn)程將定時(shí)執(zhí)行換入操作查看PCB集合中所有進(jìn)程的狀態(tài)，為“就緒已換出且換出時(shí)間最久的進(jìn)程申請(qǐng)內(nèi)存；如果申請(qǐng)成功，則將進(jìn)程調(diào)入內(nèi)存；如果失敗，則需先將內(nèi)存中的某些進(jìn)程換出，騰出足夠的內(nèi)存空間后，再將進(jìn)程調(diào)入。若還有可換入的進(jìn)程

14、，則繼續(xù)執(zhí)行換入過(guò)程，直到再無(wú)“就緒且換出狀態(tài)的進(jìn)程，或已無(wú)足夠的內(nèi)存來(lái)?yè)Q入進(jìn)程。內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式離散存儲(chǔ)管理方式連續(xù)分配的存儲(chǔ)管理方式 存在碎片問(wèn)題。使用“緊湊技術(shù)可以解決這個(gè)問(wèn)題，但時(shí)間代價(jià)較高。離散分配：給一個(gè)進(jìn)程分配許多不相鄰的分區(qū)。離散分配的類型分頁(yè)：內(nèi)存空間分成固定大小的物理塊frame，如1KB ）。用戶程序的地址空間分為同樣大小的區(qū)域，稱為頁(yè)。從0開始編制頁(yè)號(hào)，頁(yè)內(nèi)地址是相對(duì)于0編址。分段：用戶程序分成大小不同的段，每段定義

15、一組相對(duì)完整的信息。存儲(chǔ)器分配以段為單位。段頁(yè)式：目前的主流方式，具有兩者的優(yōu)點(diǎn)。分頁(yè)存儲(chǔ)管理的基本方法頁(yè)：用戶程序的地址空間，分為若干個(gè)固定大小的區(qū)域，稱為“頁(yè)”物理塊：內(nèi)存空間分為若干個(gè)物理塊或頁(yè)框，頁(yè)和塊的大小相同頁(yè)面大小 ：小的頁(yè)面可以減少內(nèi)存碎片，增加進(jìn)程的頁(yè)表長(zhǎng)度，占用大量?jī)?nèi)存，降低頁(yè)面換進(jìn)換出的效率。大的頁(yè)面可以減少頁(yè)表長(zhǎng)度，提高頁(yè)面換進(jìn)換出的效率，增加頁(yè)內(nèi)碎片。 建議的大?。?KB或8KB分頁(yè)存儲(chǔ)管理的基本方法地址結(jié)構(gòu)31 12 11 0對(duì)某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)P和頁(yè)內(nèi)地址d可按下式求得： (/) PINT A

16、 LdA MOD L頁(yè)號(hào)P位移量W操作系統(tǒng)的內(nèi)存尋址能力操作系統(tǒng)操作系統(tǒng)內(nèi)存尋址內(nèi)存尋址普通32位Windows3GB使用PAE技術(shù)的32位Windows2019Standard：32GBEnterprise：64GB64位WindowsXPEdition：128GB64位Windows2019Standard：32GBEnterprise：2TB64位Windows7/Vista旗艦版：192GB64位操作系統(tǒng)理論值264B（1T=240）分頁(yè)存儲(chǔ)管理的基本方法頁(yè)表列出了作業(yè)的邏輯地址與其在主存中的物理地址間的對(duì)應(yīng)關(guān)系。一個(gè)頁(yè)表中包含若干個(gè)表目，表目的自然序號(hào)對(duì)應(yīng)于用戶程序中的頁(yè)號(hào)，表目中的

17、塊號(hào)是該頁(yè)對(duì)應(yīng)的物理塊號(hào)。頁(yè)表的每一個(gè)表目除了包含指向頁(yè)框的指針外，還包括一個(gè)存取控制字段。分頁(yè)存儲(chǔ)管理的基本方法基本的地址變換機(jī)構(gòu)分頁(yè)存儲(chǔ)管理的基本方法具有快表的地址變換機(jī)構(gòu)兩級(jí)頁(yè)表對(duì)于32位的分頁(yè)系統(tǒng)，設(shè)頁(yè)面大小為4KB，則每個(gè)進(jìn)程的頁(yè)表中，最多可以有1M個(gè)頁(yè)表項(xiàng)，占1MB連續(xù)內(nèi)存空間?？刹捎脙蓚€(gè)方法來(lái)解決這一問(wèn)題：采用離散分配方式來(lái)解決難以找到一塊連續(xù)的大內(nèi)存空間的問(wèn)題只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入兩級(jí)頁(yè)表兩級(jí)頁(yè)表結(jié)構(gòu)兩級(jí)頁(yè)表若要減少頁(yè)表占用的內(nèi)存空間，僅把當(dāng)前需要的一批列表調(diào)入內(nèi)存。兩級(jí)列表下，外層列表調(diào)入內(nèi)存，頁(yè)表只需調(diào)入幾頁(yè)，外層列表增加

18、狀態(tài)位S，0表示頁(yè)表不在內(nèi)存，需要的情況下產(chǎn)生中斷并將頁(yè)表調(diào)入內(nèi)存。多級(jí)頁(yè)表64位計(jì)算機(jī)若按兩級(jí)列表，則外層頁(yè)號(hào)占用42位，需要占用16384G連續(xù)內(nèi)存空間。使用多級(jí)頁(yè)表將外層頁(yè)表再次分頁(yè)，將各頁(yè)離散地裝入到不相鄰的物理塊中，再利用二級(jí)外層頁(yè)表映射關(guān)系。64位計(jì)算機(jī)即使使用三級(jí)頁(yè)表也不適合，目前尋址的存儲(chǔ)器空間減少為45位。哈希頁(yè)表虛擬地址中的虛擬頁(yè)碼通過(guò)哈希函數(shù)轉(zhuǎn)換到哈希表中。把虛擬頁(yè)碼和鏈表中每一個(gè)元素的第一個(gè)域作比較，如果匹配，則第二個(gè)域作為物理地址的頁(yè)碼。哈希頁(yè)表反向頁(yè)表通常情況，每個(gè)進(jìn)程都有一張頁(yè)表，需要占用很多內(nèi)存空間。反向頁(yè)表對(duì)于每個(gè)物理內(nèi)存頁(yè)只有一個(gè)條目，包含了保存在內(nèi)存頁(yè)中的

19、虛擬頁(yè)碼和所屬進(jìn)程號(hào)。64MB的機(jī)器，若頁(yè)面大小為4KB，則反置頁(yè)表只占用64KB空間。針對(duì)查詢速度慢的問(wèn)題，可以使用哈希表和快表加速。反向頁(yè)表內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式分段式存儲(chǔ)管理在分頁(yè)存儲(chǔ)系統(tǒng)中，作業(yè)的地址空間是一維線性的，這破壞了程序內(nèi)部天然的邏輯結(jié)構(gòu)，造成共享、保護(hù)困難。引入分段存儲(chǔ)管理方式， 主要是為了滿足用戶和程序員的下述需要：方便編程信息共享 信息保護(hù)動(dòng)態(tài)增長(zhǎng) 動(dòng)態(tài)鏈接 分段系統(tǒng)的基本原理分段地址中的地址具有如下結(jié)構(gòu)：段表段號(hào)段內(nèi)地址

20、31 16 15 0段號(hào)012段首址段長(zhǎng)度58K20K100K110K260K140K分段系統(tǒng)的基本原理分段管理中作業(yè)與段表、存儲(chǔ)空間的關(guān)系分段系統(tǒng)的基本原理地址變換機(jī)構(gòu)分頁(yè)和分段的區(qū)別頁(yè)是信息的物理單位，與操作系統(tǒng)管理有關(guān)，與用戶無(wú)關(guān)。段是信息的邏輯單位，包含程序中相對(duì)完整的信息。每個(gè)系統(tǒng)中頁(yè)的大小固定且由系統(tǒng)決定，由硬件直接實(shí)現(xiàn)。段的長(zhǎng)度不固定，決定于每個(gè)程序，通常由編譯程序根據(jù)源程序信息劃分。信息共享分頁(yè)和分段系統(tǒng)都能實(shí)現(xiàn)信息共享，即多個(gè)進(jìn)程共享一個(gè)或多個(gè)分段。一個(gè)多用戶系統(tǒng)，同時(shí)接納40個(gè)用戶，他們都執(zhí)行一個(gè)文本編輯程序Text Editor）。文本編輯程序包含160KB的代碼和40K

21、B的數(shù)據(jù)區(qū)。如果160KB的代碼是可重入的，則只需1760KB內(nèi)存。分頁(yè)系統(tǒng)中的共享分段系統(tǒng)中的共享段頁(yè)式存儲(chǔ)管理方式分頁(yè)系統(tǒng)以頁(yè)面作為內(nèi)存分配的基本單位，能有效提高內(nèi)存利用率分段系統(tǒng)是以段作為內(nèi)存分配的基本單位，能更好地滿足用戶需要段頁(yè)式存儲(chǔ)管理方式既具有分段系統(tǒng)的便于實(shí)現(xiàn)、分段可共享、易于保護(hù)、可動(dòng)態(tài)鏈接等一系列優(yōu)點(diǎn)，又能像分頁(yè)系統(tǒng)那樣，很好地解決內(nèi)存的外部碎片問(wèn)題。地址映射地址變換過(guò)程內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式常規(guī)存儲(chǔ)器管理方式的特征一次性：作

22、業(yè)必須全部裝入內(nèi)存后才能開始運(yùn)行。這一特征導(dǎo)致了：當(dāng)作業(yè)要求的內(nèi)存空間超過(guò)內(nèi)存總?cè)萘?，?huì)導(dǎo)致該作業(yè)無(wú)法運(yùn)行當(dāng)大量作業(yè)要求運(yùn)行時(shí)，由于每次只能裝入少量作業(yè)，導(dǎo)致多道程序度下降。駐留性：作業(yè)被裝入內(nèi)存后，一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。局部性原理大多數(shù)情況下除轉(zhuǎn)移和過(guò)程調(diào)用），程序順序執(zhí)行。過(guò)程調(diào)用將會(huì)使程序的執(zhí)行軌跡，由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域。程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。程序中包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。局部性原理的表現(xiàn)時(shí)間局部性：程序中的某條指令被執(zhí)行，不久以后可能再次執(zhí)行；某數(shù)據(jù)被訪問(wèn)，不久以后可

23、能再次被訪問(wèn)?？臻g局部性：程序訪問(wèn)某個(gè)存儲(chǔ)單元，不久之后附近的存儲(chǔ)單元也將被訪問(wèn)。即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍之內(nèi)。虛擬存儲(chǔ)器的基本工作情況程序運(yùn)行前，僅須將當(dāng)前需要的少數(shù)頁(yè)面或段裝入內(nèi)存，其余部分暫留在硬盤上。程序運(yùn)行時(shí)，若需要的頁(yè)段尚未調(diào)入內(nèi)存稱為缺頁(yè)或缺段），就發(fā)出中斷請(qǐng)求，把頁(yè)段調(diào)入內(nèi)存。若內(nèi)存已滿，先利用頁(yè)段的置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)段調(diào)至硬盤上，再將要訪問(wèn)的頁(yè)段調(diào)入內(nèi)存。虛擬存儲(chǔ)器的定義具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存

24、。虛擬存儲(chǔ)器的特征多次性：程序和數(shù)據(jù)分多次調(diào)入內(nèi)存對(duì)換性：暫不使用的程序和數(shù)據(jù)換出內(nèi)存虛擬性：邏輯上擴(kuò)充內(nèi)存容量虛擬存儲(chǔ)器的實(shí)現(xiàn)方法請(qǐng)求分頁(yè)系統(tǒng)用戶程序只需裝入少數(shù)頁(yè)面即可運(yùn)行，通過(guò)調(diào)頁(yè)功能及頁(yè)面置換功能把即將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，把暫不運(yùn)行的頁(yè)面換到外存中請(qǐng)求分段系統(tǒng) 類似請(qǐng)求分頁(yè)系統(tǒng)，置換以段為單位。由于段的長(zhǎng)度可變，故實(shí)現(xiàn)比請(qǐng)求分頁(yè)系統(tǒng)難。Intel80386以上CPU芯片支持段頁(yè)式虛擬存儲(chǔ)器系統(tǒng)。內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式硬件支持請(qǐng)求頁(yè)表機(jī)制

25、狀態(tài)位P：1bit，用于指示該頁(yè)是否已調(diào)入內(nèi)存訪問(wèn)字段A：記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪問(wèn)修改位M：標(biāo)識(shí)該頁(yè)在調(diào)入內(nèi)存后是否被修改外存地址：用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)頁(yè)號(hào)頁(yè)號(hào)物理塊號(hào)物理塊號(hào)狀態(tài)位狀態(tài)位P P訪問(wèn)字段訪問(wèn)字段A A修改位修改位M M外存地址外存地址硬件支持缺頁(yè)中斷機(jī)構(gòu)在指令執(zhí)行期間，若請(qǐng)求的頁(yè)面不在內(nèi)存時(shí)觸發(fā)缺頁(yè)中斷一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷硬件支持地址變換機(jī)構(gòu)內(nèi)存分配最小物理塊數(shù)的確定進(jìn)程多時(shí)，進(jìn)程在內(nèi)存中能分配到的物理塊少，缺頁(yè)率上升，會(huì)降低進(jìn)程的執(zhí)行速度。最小物理塊數(shù)：能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。每條

26、指令需要的物理塊數(shù)與指令的復(fù)雜程度有關(guān)。直接尋址MOV AX,2000H2塊寄存器間接尋址 MOV EAX, EBX3塊內(nèi)存分配內(nèi)存分配策略進(jìn)程分配的物理進(jìn)程分配的物理塊數(shù)量塊數(shù)量缺頁(yè)時(shí)的置換策缺頁(yè)時(shí)的置換策略略固定分配局部置換固定與本進(jìn)程的頁(yè)面交換可變分配全局置換可變與空閑塊和所有進(jìn)程頁(yè)面交換可變分配局部置換可變與本進(jìn)程的頁(yè)面交換，若頻繁缺頁(yè)則增加物理塊內(nèi)存分配物理塊分配算法平均分配算法按比例分配算法：根據(jù)進(jìn)程的大小考慮優(yōu)先權(quán)的分配算法：內(nèi)存物理塊一部分按比例分配，另一部分根據(jù)進(jìn)程優(yōu)先權(quán)分配頁(yè)面調(diào)入策略頁(yè)面調(diào)入時(shí)機(jī)預(yù)調(diào)頁(yè)策略：將要訪問(wèn)的頁(yè)面預(yù)先調(diào)入內(nèi)存。若命中率高目前只有50%），則一次預(yù)調(diào)

27、多頁(yè)的效率高于請(qǐng)求調(diào)頁(yè)策略。請(qǐng)求調(diào)頁(yè)策略：需要的頁(yè)面調(diào)入內(nèi)存。一次調(diào)入一頁(yè)，主流選擇。頁(yè)面調(diào)入策略頁(yè)面調(diào)入過(guò)程保留CPU環(huán)境。若內(nèi)存足夠，將缺頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表。若內(nèi)存已滿，則按照某種置換算法，從內(nèi)存中選出待換頁(yè)，若該頁(yè)修改位為1，則寫回磁盤。再把缺頁(yè)調(diào)入內(nèi)存，并修改存在位為1，將頁(yè)表項(xiàng)寫入快表。缺頁(yè)調(diào)入內(nèi)存后，即可通過(guò)頁(yè)表讀取其在內(nèi)存中的物理地址。頁(yè)面的調(diào)入過(guò)程對(duì)用戶透明。內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式最佳置換算法理論算法，最低的缺頁(yè)率。無(wú)法實(shí)現(xiàn)。

28、換出的頁(yè)面是以后永不使用的， 或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。先進(jìn)先出置換算法FIFO）換出的頁(yè)面在內(nèi)存中駐留時(shí)間最長(zhǎng)最近最久未使用算法LRU）換出的頁(yè)面是最后一次訪問(wèn)時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)。需要用硬件來(lái)實(shí)現(xiàn)最久未使用頁(yè)的搜索。實(shí)際效果比較好。LRU置換算法的硬件支持方法一：寄存器為內(nèi)存中的每個(gè)頁(yè)面配置移位寄存器，把n位寄存器上的數(shù)看成一個(gè)整數(shù)，定期右移，置換數(shù)值最小的寄存器對(duì)應(yīng)的頁(yè)。LRU置換算法的硬件支持方法二：棧堆棧中保存最近訪問(wèn)的頁(yè)號(hào)。當(dāng)進(jìn)程訪問(wèn)某頁(yè)時(shí)，把該頁(yè)號(hào)從棧中取出，放在棧頂。需要換出時(shí)，取棧底的頁(yè)面。Clock置換算法LRU算法需要硬件支持，成本較高Clock算法是LR

29、U的近似算法，又稱為最近未用算法NRU, Not Recently Used）算法原理：內(nèi)存中所有頁(yè)面以指針相連每個(gè)頁(yè)面都有一位訪問(wèn)標(biāo)志進(jìn)程訪問(wèn)頁(yè)面則把頁(yè)面的訪問(wèn)標(biāo)志置為1選擇換出頁(yè)面時(shí)，按指針順序訪問(wèn)，若為0則換出，若為1則置為0。Clock置換算法改進(jìn)的Clock置換算法考慮換出成本：若換出頁(yè)面已被修改，則需寫回磁盤。優(yōu)先換出未使用過(guò)且未修改過(guò)的頁(yè)面。頁(yè)面包含訪問(wèn)位A和修改位M。替換優(yōu)先級(jí)：(0,0)(0,1)(1,0)(1,1)改進(jìn)的Clock置換算法算法步驟：根據(jù)指針順序?qū)ふ褹=0且M=0的頁(yè)面，將滿足條件的第一個(gè)頁(yè)面作為淘汰頁(yè)。若未找到合適頁(yè)面，則重新開始尋找A=0且M=1的頁(yè)面，將

30、滿足條件的第一個(gè)頁(yè)面作為淘汰頁(yè)，將所有掃描過(guò)頁(yè)面的訪問(wèn)位都置0。若未找到合適頁(yè)面，則跳轉(zhuǎn)至1。頁(yè)面緩沖影響頁(yè)面置換開銷的因素：頁(yè)面置換算法：降低缺頁(yè)率寫回磁盤的頻率：需要寫回的頁(yè)面暫存在已修改換出頁(yè)面鏈表中，積累到一定數(shù)量后一起寫磁盤已修改換出頁(yè)面的重新利用：處于已修改換出頁(yè)面鏈表的頁(yè)面若再次訪問(wèn)，可直接從鏈表中讀取內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式抖動(dòng)現(xiàn)象系統(tǒng)同時(shí)運(yùn)行太多進(jìn)程時(shí)，分配給每個(gè)進(jìn)程的物理塊太少，運(yùn)行時(shí)頻繁缺頁(yè)，導(dǎo)致進(jìn)程大多數(shù)時(shí)間用于頁(yè)面切換，處

31、理機(jī)利用率趨于0。這種現(xiàn)象稱為顛簸或抖動(dòng)。工作集進(jìn)程發(fā)生缺頁(yè)率的時(shí)間間隔，與進(jìn)程獲得的物理塊數(shù)有關(guān)。工作集基于程序運(yùn)行時(shí)的局部性原理，程序在一段時(shí)間內(nèi)會(huì)局限于訪問(wèn)較少的一些頁(yè)面，這些頁(yè)面被稱為活躍頁(yè)面。工作集w(t, )指進(jìn)程在時(shí)間間隔(t-, t)中引用頁(yè)面的集合。( , )( ,1)w tw t 抖動(dòng)的預(yù)防方法進(jìn)程缺頁(yè)時(shí)，只能與本進(jìn)程的頁(yè)面切換。利用工作集，在處理機(jī)調(diào)入新進(jìn)程前，檢測(cè)內(nèi)存頁(yè)面是否夠用。“L=S原則：L是兩次缺頁(yè)事件之間的平均時(shí)間，S是平均缺頁(yè)服務(wù)時(shí)間，L=S時(shí)，存儲(chǔ)器和處理機(jī)都可達(dá)較高利用率。暫停優(yōu)先級(jí)低的進(jìn)程、大進(jìn)程或者執(zhí)行時(shí)間長(zhǎng)的進(jìn)程。內(nèi)存存儲(chǔ)器的層次結(jié)構(gòu)程序的裝入和鏈

32、接連續(xù)分配存儲(chǔ)管理方式對(duì)換分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式虛擬存儲(chǔ)器概述請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法“抖動(dòng)與工作集請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理以分段為單位進(jìn)行換入換出程序只需要調(diào)入幾個(gè)分段即可運(yùn)行當(dāng)訪問(wèn)段不在內(nèi)存中時(shí)，可請(qǐng)求系統(tǒng)將缺的段調(diào)入內(nèi)存請(qǐng)求分段中的硬件支持請(qǐng)求段表機(jī)制存取方式：應(yīng)用程序中段是信息的邏輯單位，可根據(jù)信息的屬性實(shí)施保護(hù)，如只執(zhí)行、只讀、允許讀/寫訪問(wèn)字段A：記錄該段被訪問(wèn)的頻繁程度，供置換頁(yè)面時(shí)參考修改位M：記錄該段進(jìn)入內(nèi)存后是否被修改，供置換頁(yè)面時(shí)參考存在位P：記錄該段是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考增補(bǔ)位：表示該段在運(yùn)行過(guò)程中是否動(dòng)態(tài)增長(zhǎng)外存始址：表示該段在外存中的起始地址，即起始盤塊號(hào)段名段名段長(zhǎng)段長(zhǎng)段的段的基址基址存