北大操作系統(tǒng)原理5

第五章存儲(chǔ)管理5.1概述5.2分區(qū)存儲(chǔ)管理5.3頁(yè)式存儲(chǔ)管理5.4段式存儲(chǔ)管理5.5段頁(yè)式存儲(chǔ)管理5.6交換技術(shù)與覆蓋技術(shù)5.7虛擬存儲(chǔ)5.1概述5.1.1存儲(chǔ)體系存儲(chǔ)器的層次結(jié)構(gòu)：Cache主存磁盤

高速緩存Cache：

少量的、非常快速、昂貴、易變的內(nèi)存RAM：

若干兆字節(jié)、中等速度、中等價(jià)格、易變的磁盤：數(shù)百兆或數(shù)千兆字節(jié)、低速、價(jià)廉、不易變的

由操作系統(tǒng)協(xié)調(diào)這些存儲(chǔ)器的使用

重要性：直接存取要求內(nèi)存速度盡量快到與CPU取指速度相匹配，大到能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)，否則CPU執(zhí)行速度就會(huì)受到內(nèi)存速度和容量的影響而得不到充分發(fā)揮

內(nèi)存：

是由存儲(chǔ)單元（字節(jié)或字）組成的一維連續(xù)的地址空間，簡(jiǎn)稱內(nèi)存空間。用來(lái)存放當(dāng)前正在運(yùn)行程序的代碼及數(shù)據(jù)，是程序中指令本身地址所指的、亦即程序計(jì)數(shù)器所指的存儲(chǔ)器內(nèi)存可以分為：系統(tǒng)區(qū)：用于存放操作系統(tǒng)用戶區(qū)：用于裝入并存放用戶程序和數(shù)據(jù)5.1.2存儲(chǔ)管理目的

用戶對(duì)內(nèi)存的使用要求1、充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲(chǔ)基礎(chǔ)2、盡可能方便用戶使用自動(dòng)裝入用戶程序用戶程序中不必考慮硬件細(xì)節(jié)3、系統(tǒng)能夠解決程序空間比實(shí)際內(nèi)存空間大的問(wèn)題4、程序在執(zhí)行時(shí)可以動(dòng)態(tài)伸縮5、內(nèi)存存取速度快6、存儲(chǔ)保護(hù)與安全7、共享與通信8、了解有關(guān)資源的使用狀況9、實(shí)現(xiàn)的性能和代價(jià)

5.1.3存儲(chǔ)管理的任務(wù)

前提:引入多道程序設(shè)計(jì)技術(shù)滿足用戶要求1、內(nèi)存空間的管理、分配與回收記錄內(nèi)存的使用情況——設(shè)置相應(yīng)的內(nèi)存分配表（內(nèi)存分配回收的依據(jù)）內(nèi)存空間劃分問(wèn)題？靜態(tài)或動(dòng)態(tài)，等長(zhǎng)或不等長(zhǎng)內(nèi)存空間的管理、分配與回收

內(nèi)存分配表

位示圖表示法：用一位（bit）表示一個(gè)空閑頁(yè)面（0：空閑，1：占用）0…...110…...第0頁(yè)第1頁(yè)第i頁(yè)

第n-1頁(yè)內(nèi)存空間的管理、分配與回收

空閑頁(yè)面表：包括首頁(yè)面號(hào)和頁(yè)面?zhèn)€數(shù)，連續(xù)若干的頁(yè)面作為一組登記在表中

空閑塊表：空閑塊首址和空閑塊長(zhǎng)度，沒(méi)有記錄的區(qū)域即為進(jìn)程所占用

空閑塊鏈表：將所有的空閑塊鏈成一個(gè)鏈表內(nèi)存空間的管理、分配與回收確定分配算法實(shí)施內(nèi)存分配回收內(nèi)存

分配回收方式:靜態(tài)分配與動(dòng)態(tài)分配內(nèi)存空間的管理、分配與回收

連續(xù)性；離散性駐留性；交換性一次性；多次性2、存儲(chǔ)共享內(nèi)存共享：兩個(gè)或多個(gè)進(jìn)程共用內(nèi)存中相同區(qū)域目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率實(shí)現(xiàn)進(jìn)程通信（數(shù)據(jù)共享）共享內(nèi)容：代碼共享，要求代碼為純代碼數(shù)據(jù)共享3、存儲(chǔ)保護(hù)與安全

保護(hù)目的：為多個(gè)程序共享內(nèi)存提供保障,使在內(nèi)存中的各道程序,只能訪問(wèn)它自己的區(qū)域，避免各道程序間相互干攏，特別是當(dāng)一道程序發(fā)生錯(cuò)誤時(shí),不致于影響其他程序的運(yùn)行。通常由硬件完成保護(hù)功能，由軟件輔助實(shí)現(xiàn)。（特權(quán)指令不能完成存儲(chǔ)保護(hù)。）存儲(chǔ)保護(hù)

保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯（有意或無(wú)意的）不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）保護(hù)過(guò)程防止地址越界每個(gè)進(jìn)程都有自己獨(dú)立的進(jìn)程空間，如果一個(gè)進(jìn)程在運(yùn)行時(shí)所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。即當(dāng)程序要訪問(wèn)某個(gè)內(nèi)存單元時(shí)，由硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理保護(hù)過(guò)程防止地址越界一般由硬件提供一對(duì)寄存器：

基址寄存器：存放起始地址

限長(zhǎng)寄存器：存放長(zhǎng)度（上界寄存器/下界寄存器）保護(hù)過(guò)程防止操作越權(quán)

對(duì)于允許多個(gè)進(jìn)程共享的存儲(chǔ)區(qū)域，每個(gè)進(jìn)程都有自己的訪問(wèn)權(quán)限。如果一個(gè)進(jìn)程對(duì)共享區(qū)域的訪問(wèn)違反了權(quán)限規(guī)定，則發(fā)生操作越權(quán)即讀寫保護(hù)4內(nèi)存“擴(kuò)充”通過(guò)虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn)

用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來(lái)"擴(kuò)充"內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間內(nèi)存“擴(kuò)充”具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來(lái)統(tǒng)一使用。通過(guò)這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時(shí)不受內(nèi)存限制5地址映射（地址重定位，地址變換）(1)邏輯地址（相對(duì)地址，虛地址）(2)物理地址（絕對(duì)地址，實(shí)地址）(3)地址映射地址映射LoadA2003456。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間BA=1000(1)邏輯地址（相對(duì)地址，虛地址）用戶的程序經(jīng)過(guò)匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為0，其余指令中的地址都相對(duì)于首地址而編址不能用邏輯地址在內(nèi)存中讀取信息(2)物理地址（絕對(duì)地址，實(shí)地址）內(nèi)存中存儲(chǔ)單元的地址，可直接尋址(3)地址映射為了保證CPU執(zhí)行指令時(shí)可正確訪問(wèn)存儲(chǔ)單元，需將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接尋址的物理地址，這一過(guò)程稱為地址映射03456......LOADA200......0100200300.........LOADA2003456邏輯地址空間110012001300物理地址空間200VR+1000BR

原因:當(dāng)程序裝入內(nèi)存時(shí),操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致,而CPU執(zhí)行指令時(shí)，是按物理地址進(jìn)行的，所以要進(jìn)行地址轉(zhuǎn)換靜態(tài)重定位當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時(shí)由軟件完成）動(dòng)態(tài)重定位在程序運(yùn)行過(guò)程中要訪問(wèn)數(shù)據(jù)時(shí)再進(jìn)行地址變換（即在逐條指令執(zhí)行時(shí)完成地址映射。一般為了提高效率，此工作由硬件地址映射機(jī)制來(lái)完成。硬件支持，軟硬件結(jié)合完成）硬件上需要一對(duì)寄存器的支持5.1.4各種存儲(chǔ)管理方案單一用戶（連續(xù)區(qū)）存儲(chǔ)管理：?jiǎn)斡脩粝到y(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)存，故內(nèi)存分配管理十分簡(jiǎn)單，內(nèi)存利用率低。內(nèi)存分為兩個(gè)區(qū)域，一個(gè)供操作系統(tǒng)使用，一個(gè)供用戶使用用戶程序位于RAM中的操作系統(tǒng)0xFFF...0位于RAM中的操作系統(tǒng)用戶程序0ROM中的設(shè)備驅(qū)動(dòng)程序用戶程序位于RAM中的操作系統(tǒng)05.2分區(qū)存儲(chǔ)管理方案系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)，分區(qū)大小可以相等，也可以不等。一個(gè)進(jìn)程占據(jù)一個(gè)分區(qū)固定分區(qū)可變分區(qū)5.2.1固定分區(qū)預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)連續(xù)區(qū)域，稱為一個(gè)分區(qū)。每個(gè)分區(qū)的大小可以相同也可以不同，如圖所示。但分區(qū)大小固定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)存儲(chǔ)分配：如果有一個(gè)空閑區(qū),則分配給進(jìn)程分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)多個(gè)等待隊(duì)列單個(gè)等待隊(duì)列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)固定分區(qū)內(nèi)存管理：設(shè)置內(nèi)存分配表內(nèi)存分配：內(nèi)存回收：簡(jiǎn)單缺點(diǎn)：內(nèi)存利用率不高分區(qū)號(hào)起始地址長(zhǎng)度狀態(tài)進(jìn)程名5.2.2可變分區(qū)1、基本思想內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來(lái)決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待主存空間2、內(nèi)存管理設(shè)置內(nèi)存空閑塊表——記錄了空閑區(qū)起始地址和長(zhǎng)度3、內(nèi)存分配動(dòng)態(tài)分配4、內(nèi)存回收當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空閑塊表內(nèi)存分配：三種分配算法首先適配算法：當(dāng)接到內(nèi)存申請(qǐng)時(shí)，查空閑塊表，找到第一個(gè)不小于請(qǐng)求的空塊，將其分割并分配（特點(diǎn)：簡(jiǎn)單、快速分配）最佳適配算法：接到內(nèi)存申請(qǐng)時(shí)，在空閑塊表中找到一個(gè)不小于請(qǐng)求的最小空塊進(jìn)行分配（特點(diǎn)：用最小空間滿足要求）最壞適配算法：

接到內(nèi)存申請(qǐng)時(shí)，在空閑塊表中找到一個(gè)不小于請(qǐng)求的最大空塊進(jìn)行分配（特點(diǎn)：當(dāng)分割后空閑塊仍為較大空塊）0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配98K12K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K碎片問(wèn)題：經(jīng)過(guò)一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片

造成存儲(chǔ)資源的浪費(fèi)碎片問(wèn)題的解決：緊湊技術(shù)：通過(guò)在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域（緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)）

問(wèn)題：開(kāi)銷大；移動(dòng)時(shí)機(jī)

討論：分區(qū)的保護(hù)：設(shè)置界地址寄存器保護(hù)鍵優(yōu)點(diǎn)：

便于動(dòng)態(tài)申請(qǐng)內(nèi)存便于共享內(nèi)存便于動(dòng)態(tài)鏈接缺點(diǎn)： 碎片問(wèn)題(外碎片)，內(nèi)存利用率不高受實(shí)際內(nèi)存容量限制5.3段式存儲(chǔ)管理5.3.1基本思想（工作原理）...0S工作區(qū)段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N數(shù)組[A]12345...操作系統(tǒng).....B0SA0NY0LX0PM0K邏輯段號(hào)01234作業(yè)1的地址空間10003200500060008000PKSLN主存K

3200P1500L6000N8000S5000長(zhǎng)度段地址01234操作系統(tǒng)用戶程序劃分按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段，每個(gè)程序段都有一個(gè)段名，且有一個(gè)段號(hào)。段號(hào)從0開(kāi)始，每一段也從0開(kāi)始編址，段內(nèi)地址是連續(xù)的邏輯地址內(nèi)存劃分內(nèi)存空間被動(dòng)態(tài)的劃分為若干個(gè)長(zhǎng)度不相同的區(qū)域，這些區(qū)域被稱為物理段，每個(gè)物理段由起始地址和長(zhǎng)度確定段號(hào)段內(nèi)地址內(nèi)存分配

以段為單位分配內(nèi)存，每一個(gè)段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機(jī)分割，需要多少分配多少），但各段之間可以不連續(xù)存放5.3.2管理段表：它記錄了段號(hào)，段的首（地）址和長(zhǎng)度之間的關(guān)系每一個(gè)程序設(shè)置一個(gè)段表，放在內(nèi)存屬于進(jìn)程的現(xiàn)場(chǎng)信息段號(hào)012段首址段長(zhǎng)度58K20K100K110K260K140K空閑塊管理：記錄了空閑區(qū)起始地址和長(zhǎng)度內(nèi)存的分配算法：首先適配；最佳適配；最壞適配5.3.3硬件支持系統(tǒng)設(shè)置一對(duì)寄存器段表始址寄存器：用于保存正在運(yùn)行進(jìn)程的段表的始址段表長(zhǎng)度寄存器：用于保存正在運(yùn)行進(jìn)程的段表的長(zhǎng)度（例如上圖的段表長(zhǎng)度為3）

Cl

Cb+段號(hào)S

段內(nèi)地址d比較比較b+d段表S>=Cl快表物理地址段表始址寄存器段表長(zhǎng)度寄存器邏輯地址lb...Slb地址越界d>=1d>=1地址映射及存儲(chǔ)保護(hù)機(jī)制地址越界地址越界比較介于內(nèi)存與寄存器之間的存儲(chǔ)機(jī)制，它又叫快表用途：保存正在運(yùn)行進(jìn)程的段表的子集（部分表項(xiàng)）特點(diǎn)：按內(nèi)容并行查找相聯(lián)（聯(lián)想）存儲(chǔ)器（associativememory）

TLB（Translationlookasidebuffers）引入快表的作用：

為了提高地址映射速度快表項(xiàng)目：段號(hào)；段始址；段長(zhǎng)度；標(biāo)識(shí)（狀態(tài)）位；訪問(wèn)位（淘汰位）快表淘汰問(wèn)題？段的共享？段的保護(hù)？?jī)?yōu)點(diǎn)：便于動(dòng)態(tài)申請(qǐng)內(nèi)存管理和使用統(tǒng)一化便于共享便于動(dòng)態(tài)鏈接缺點(diǎn)：產(chǎn)生碎片思考：與可變分區(qū)存儲(chǔ)管理方案的相同點(diǎn)與不同點(diǎn)？5.4頁(yè)式存儲(chǔ)管理5.4.1基本思想（工作原理）1.用戶程序劃分把用戶程序按邏輯頁(yè)劃分成大小相等的部分，稱為頁(yè)。從0開(kāi)始編制頁(yè)號(hào)，頁(yè)內(nèi)地址是相對(duì)于0編址邏輯地址用戶程序的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。一般，一頁(yè)的大小為2的整數(shù)次冪，因此，地址的高位部分為頁(yè)號(hào)，低位部分為頁(yè)內(nèi)地址頁(yè)號(hào)頁(yè)內(nèi)地址0111231頁(yè)號(hào)P頁(yè)內(nèi)位移量W編號(hào)0~1048575相對(duì)地址0~4095內(nèi)存空間：按頁(yè)的大小劃分為大小相等的區(qū)域，稱為內(nèi)存塊（物理頁(yè)面，頁(yè)框）內(nèi)存分配：

以頁(yè)為單位進(jìn)行分配，并按作業(yè)的頁(yè)數(shù)多少來(lái)分配。邏輯上相鄰的頁(yè)，物理上不一定相鄰...01234560123456作業(yè)的地址空間頁(yè)框（物理塊）頁(yè)號(hào)頁(yè)表主存中頁(yè)框（物理塊）.......5.4.2管理1.頁(yè)表：系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁(yè)表，頁(yè)表給出邏輯頁(yè)號(hào)和具體內(nèi)存塊號(hào)相應(yīng)的關(guān)系頁(yè)表放在內(nèi)存，屬于進(jìn)程的現(xiàn)場(chǎng)信息2.空塊管理——位示圖3.內(nèi)存的分配與回收0310/10/10/10/10/1017……空閑塊數(shù)……空塊管理——位示圖計(jì)算一個(gè)作業(yè)所需要的總塊數(shù)N查位示圖，看看是否還有N個(gè)空閑塊如果有足夠的空閑塊，則頁(yè)表長(zhǎng)度設(shè)為N，可填入PCB中；申請(qǐng)頁(yè)表區(qū)，把頁(yè)表始址填入PCB依次分配N個(gè)空閑塊，將塊號(hào)和頁(yè)號(hào)填入頁(yè)表修改位示圖5.4.3硬件支持1．系統(tǒng)設(shè)置一對(duì)寄存器：

頁(yè)表始址寄存器頁(yè)表長(zhǎng)度寄存器2．相聯(lián)存儲(chǔ)器——快表快表表項(xiàng)：頁(yè)號(hào)；內(nèi)存塊號(hào)；標(biāo)識(shí)位；淘汰位p’頁(yè)表地址越界

l比較P>=1pp’...快表

b+頁(yè)號(hào)p頁(yè)內(nèi)地址dP’d物理地址頁(yè)表地址寄存器頁(yè)表長(zhǎng)度寄存器邏輯地址地址映射機(jī)制5.4.6優(yōu)缺點(diǎn)優(yōu)點(diǎn)：解決了碎片問(wèn)題便于管理缺點(diǎn)：不易實(shí)現(xiàn)共享不便于動(dòng)態(tài)連接思考：頁(yè)的共享？頁(yè)的保護(hù)？5.5段頁(yè)式存儲(chǔ)管理5.5.1產(chǎn)生背景及基本思想背景：結(jié)合了二者優(yōu)點(diǎn)克服了二者的缺點(diǎn)基本思想：

用戶程序劃分：按段式劃分（對(duì)用戶來(lái)講，按段的邏輯關(guān)系進(jìn)行劃分；對(duì)系統(tǒng)講，按頁(yè)劃分每一段）邏輯地址：內(nèi)存劃分：按頁(yè)式存儲(chǔ)管理方案內(nèi)存分配：以頁(yè)為單位進(jìn)行分配段號(hào)段內(nèi)地址頁(yè)號(hào)頁(yè)內(nèi)地址5.5.2管理1.段表：記錄了每一段的頁(yè)表始址和頁(yè)表長(zhǎng)度2.頁(yè)表：記錄了邏輯頁(yè)號(hào)與內(nèi)存塊號(hào)的對(duì)應(yīng)關(guān)系（每一段有一個(gè)，一個(gè)程序可能有多個(gè)頁(yè)表）3.空塊管理：同頁(yè)式管理4.分配：同頁(yè)式管理5.5.3硬件支持段表始址寄存器

段表長(zhǎng)度寄存器

相聯(lián)存儲(chǔ)器（快表）5.6交換技術(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)

交換技術(shù)與覆蓋技術(shù)共同點(diǎn)：進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進(jìn)行信息交換不同點(diǎn)：如何控制交換？5.6.1覆蓋技術(shù)把程序劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段（內(nèi)存“擴(kuò)大”了）覆蓋：一個(gè)作業(yè)的若干程序段，或幾個(gè)作業(yè)的某些部分共享某一個(gè)存儲(chǔ)空間一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作系統(tǒng)完成自動(dòng)覆蓋A8KE4KF10KC10KB8KD12K作業(yè)X的調(diào)用結(jié)構(gòu)作業(yè)X的常駐區(qū)

A（8K）覆蓋區(qū)0（10K）覆蓋區(qū)1（12K）BCDEF

缺點(diǎn)：對(duì)用戶不透明，增加了用戶負(fù)擔(dān)

例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上，MS-DOS的啟動(dòng)過(guò)程中，多次使用覆蓋技術(shù)；啟動(dòng)之后，用戶程序區(qū)TPA的高端部分與COMMAND.COM暫駐模塊也是一種覆蓋結(jié)構(gòu)5.6.2交換技術(shù)當(dāng)內(nèi)存空間緊張時(shí)，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)移到外存，把外存中某些進(jìn)程換進(jìn)內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進(jìn)程在內(nèi)存與外存之間的動(dòng)態(tài)調(diào)度。多用于分時(shí)系統(tǒng)中

交換技術(shù)實(shí)現(xiàn)中的幾個(gè)問(wèn)題：

1、選擇原則即：將哪個(gè)進(jìn)程換出/內(nèi)存？例子：分時(shí)系統(tǒng)，時(shí)間片輪轉(zhuǎn)法或基于優(yōu)先數(shù)的調(diào)度算法，在選擇換出進(jìn)程時(shí)，要確定換出的進(jìn)程是要長(zhǎng)時(shí)間等待的需要特殊考慮的是：任何等待I/O的進(jìn)程中存在的問(wèn)題解決：從不換出處于等待I/O狀態(tài)的進(jìn)程有些I/O進(jìn)程因DMA而不能換出內(nèi)存或換出前需要操作系統(tǒng)的特殊幫助

2、交換時(shí)機(jī)的確定何時(shí)需發(fā)生交換？例子：只要不用就換出（很少再用）只在內(nèi)存空間不夠或有不夠的危險(xiǎn)時(shí)換出3、交換時(shí)需要做哪些工作？需要一個(gè)盤交換區(qū)：必須足夠大以存放所有用戶程序的所有內(nèi)存映像的拷貝；必須對(duì)這些內(nèi)存映像的直接存取4、換入回內(nèi)存時(shí)位置的確定換出后再換入的內(nèi)存位置一定要在換出前的原來(lái)位置上嗎？受地址“綁定”技術(shù)的影響，即絕對(duì)地址產(chǎn)生時(shí)機(jī)的限制

與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)；而且，交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。此外，覆蓋只能覆蓋那些與覆蓋段無(wú)關(guān)的程序段5.7虛擬存儲(chǔ)連續(xù)性；離散性駐留性；交換性一次性；多次性以CPU時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)5.7.1概述

1、問(wèn)題的提出程序大于內(nèi)存程序暫時(shí)不執(zhí)行或運(yùn)行完是否還要占用內(nèi)存

虛擬存儲(chǔ)器的基本思想是：程序、數(shù)據(jù)、堆棧的大小可以超過(guò)內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)交換虛擬存儲(chǔ)器支持多道程序設(shè)計(jì)技術(shù)CPUMMU內(nèi)存磁盤控制器總線虛擬地址物理地址MMU：內(nèi)存管理單元XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虛地址空間物理地址空間}虛頁(yè)頁(yè)框1514131211109

87654321000000000000000011110000101100000000000001111001000111010011010100010000000000100110000000000100110在/不在內(nèi)存頁(yè)表虛地址8196物理地址245802、程序局部性原理在一段時(shí)間內(nèi)一個(gè)程序的執(zhí)行往往呈現(xiàn)出高度的局部性，表現(xiàn)在時(shí)間與空間兩方面時(shí)間局部性：一條指令被執(zhí)行了，則在不久的將來(lái)它可能再被執(zhí)行空間局部性：若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)，與該存儲(chǔ)單元相鄰的單元可能被使用3、虛擬存儲(chǔ)技術(shù)虛存：把內(nèi)存與外存有機(jī)的結(jié)合起來(lái)使用，從而得到一個(gè)容量很大的“內(nèi)存”，這就是虛存實(shí)現(xiàn)思想：當(dāng)進(jìn)程運(yùn)行時(shí)，先將一部分程序裝入內(nèi)存，另一部分暫時(shí)留在外存，當(dāng)要執(zhí)行的指令不在內(nèi)存時(shí)，由系統(tǒng)自動(dòng)完成將它們從外存調(diào)入內(nèi)存工作目的：提高內(nèi)存利用率5.7.2虛擬頁(yè)式存儲(chǔ)管理1、基本工作原理在進(jìn)程開(kāi)始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入一個(gè)或零個(gè)頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面2、頁(yè)表表項(xiàng)頁(yè)號(hào)、駐留位、內(nèi)存塊號(hào)、外存地址、訪問(wèn)位、修改位 駐留位（中斷位）：表示該頁(yè)是在內(nèi)存還是在外存訪問(wèn)位：根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決定）修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò)頁(yè)號(hào)中斷位內(nèi)存塊號(hào)外存地址訪問(wèn)位修改位3、缺頁(yè)中斷（PageFault）在地址映射過(guò)程中，在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)不在內(nèi)存，則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去如果內(nèi)存中有空閑塊，則分配一頁(yè)，將新調(diào)入頁(yè)裝入內(nèi)存，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)，若該頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫回外存4、頁(yè)面淘汰算法先進(jìn)先出頁(yè)面淘汰算法（FIFO）

選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)并淘汰之第二次機(jī)會(huì)淘汰算法(SCR)

按照先進(jìn)先出算法選擇某一頁(yè)面，檢查其訪問(wèn)位，如果為0，則淘汰該頁(yè)，如果為1，則給第二次機(jī)會(huì)，并將訪問(wèn)位置0理想淘汰算法—最佳頁(yè)面算法（OPT）

淘汰以后不再需要的或最遠(yuǎn)的將來(lái)才會(huì)用到的頁(yè)面最近最少使用頁(yè)面淘汰算法（LRU）

選擇最后一次訪問(wèn)時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)并淘汰之即淘汰沒(méi)有使用的時(shí)間最長(zhǎng)的頁(yè)實(shí)現(xiàn)代價(jià)很高時(shí)間戳或硬件方法LRU的軟件解決方案：最不經(jīng)常使用（NFU）

選擇訪問(wèn)次數(shù)最少的頁(yè)面淘汰之實(shí)現(xiàn)：軟件計(jì)數(shù)器，一頁(yè)一個(gè)，初值為0。每次時(shí)鐘中斷時(shí)，計(jì)數(shù)器加R。發(fā)生缺頁(yè)中斷時(shí)，選擇計(jì)數(shù)器值最小的一頁(yè)淘汰改進(jìn)：計(jì)數(shù)器在加R前先右移一位

R位加到計(jì)數(shù)器的最左端稱為老化算法最近未使用頁(yè)面淘汰算法（NRU）

選擇在最近一段時(shí)間內(nèi)未使用過(guò)的一頁(yè)并淘汰之實(shí)現(xiàn)：設(shè)置兩位訪問(wèn)位（R），修改位（M）

啟動(dòng)一個(gè)進(jìn)程時(shí)，R、M置0

R被定期清零發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)檢查R，M：

第0類：無(wú)訪問(wèn)，無(wú)修改第1類：無(wú)訪問(wèn)，有修改第2類：有訪問(wèn)，無(wú)修改第3類：有訪問(wèn)，有修改操作系統(tǒng)隨機(jī)從編號(hào)最小的非空類中選擇一頁(yè)淘汰例子1：計(jì)算缺頁(yè)次數(shù)某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5FIFO432143543215頁(yè)1432143555211頁(yè)243214333522頁(yè)34321444355

xxxxxxx

x

x共缺頁(yè)中斷9次

LRU432143543215頁(yè)1432143543215頁(yè)243214354321頁(yè)34321435432

xxxxxxx

xxx共缺頁(yè)中斷10次

OPT432143543215頁(yè)1432111555211頁(yè)243333333555頁(yè)34444444444

xxxx

x

xx

共缺頁(yè)中斷7次例子2：計(jì)算缺頁(yè)次數(shù)

某程序在內(nèi)存中分配m頁(yè)初始為空，頁(yè)面走向?yàn)?，2，3，4，1，2，5，1，2，3，4，5。當(dāng)m=3，m=4時(shí)缺頁(yè)中斷分別為多少？用FIFO算法例子2：計(jì)算缺頁(yè)次數(shù)m=3時(shí)，缺頁(yè)中斷9次m=4時(shí)，缺頁(yè)中斷10次注：FIFO頁(yè)面淘汰算法會(huì)產(chǎn)生異常現(xiàn)象（Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁(yè)面數(shù)增加時(shí)，缺頁(yè)次數(shù)反而增加5、影響缺頁(yè)次數(shù)的因素(1)分配給進(jìn)程的物理頁(yè)面數(shù)(2)頁(yè)面本身的大小(3)程序的編制方法(4)頁(yè)面淘汰算法例子3：內(nèi)存分配一頁(yè)，初始時(shí)第一頁(yè)在內(nèi)存；頁(yè)面大小為128個(gè)整數(shù)；矩陣A128X128按行存放程序編制方法1：

Forj:=1to128Fori:=1to128A[i,j]:=0;程序編制方法2：

Fori:=1to128Forj:=1to128A[i,j]:=0;5.7.3性能問(wèn)題1、顛簸（抖動(dòng)）在虛存中，頁(yè)面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng)原因：頁(yè)面淘汰算法不合理分配給進(jìn)程的物理頁(yè)面數(shù)太少2、工作集（WorkingSet）模型

基本思想：根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時(shí)間內(nèi)總是集中訪問(wèn)一些頁(yè)面，這些頁(yè)面稱為活躍頁(yè)面，如果分配給一個(gè)進(jìn)程的物理頁(yè)面數(shù)太少了，使該進(jìn)程所需的活躍頁(yè)面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過(guò)程中將頻繁發(fā)生中斷如果能為進(jìn)程提供與活躍頁(yè)面數(shù)相等的物理頁(yè)面數(shù)，則可減少缺頁(yè)中斷次數(shù)工作集：對(duì)于給定的訪問(wèn)序列選取定長(zhǎng)的區(qū)間，稱為工作集窗口，落在工作集窗口中的頁(yè)面集合稱為工作集內(nèi)容取決于頁(yè)的三個(gè)因素：訪頁(yè)序列特性時(shí)刻Ti

窗口長(zhǎng)度(△)例：26157775162341234443434441327||t1||t2

ws(t1)={1,2,5,6,7}

ws(t2)={3,4}5.7.4虛擬段式存儲(chǔ)管理1、段表內(nèi)容增加：特征位（在/不在內(nèi)存，是否可共享），存取權(quán)限位（讀，寫，執(zhí)行），標(biāo)志位（是否修改過(guò)，能否移動(dòng)），擴(kuò)充位（固定長(zhǎng)/可擴(kuò)充）2、越界中斷處理進(jìn)程在執(zhí)行過(guò)程中，有時(shí)需要擴(kuò)大分段，如數(shù)據(jù)段。由于要訪問(wèn)的地址超出原有的段長(zhǎng)，所以發(fā)越界中斷。操作系統(tǒng)處理中斷時(shí)，首先判斷該段的“擴(kuò)充位”，如可擴(kuò)充，則增加段的長(zhǎng)度；否則按出錯(cuò)處理3、缺段中斷處理檢查內(nèi)存中是否有足夠的空閑空間

①若有，則裝入該段，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，中斷返回

②若沒(méi)有，檢查內(nèi)存中空閑區(qū)的總和是否滿足要求，是則應(yīng)采用緊縮技術(shù)，轉(zhuǎn)①

；否則，淘汰一（些）段，轉(zhuǎn)①4、段的動(dòng)態(tài)鏈接大型程序：若干程序段，若干數(shù)據(jù)段一些熟知的事實(shí)：進(jìn)程的某些程序段在進(jìn)程運(yùn)行期間可能根本不用互斥執(zhí)行的程序段沒(méi)有必要同時(shí)駐留內(nèi)存有些程序段執(zhí)行一次后不再用到

靜態(tài)鏈接：為了程序正確執(zhí)行，必須由連接裝配程序把它們連接成一個(gè)可運(yùn)行的目標(biāo)程序，并在程序運(yùn)行前都裝入內(nèi)存。問(wèn)題：花費(fèi)時(shí)間，浪費(fèi)空間（1）段的動(dòng)態(tài)鏈接在程序開(kāi)始運(yùn)行時(shí)，只將主程序段裝配好并調(diào)入內(nèi)存，其它各段的裝配是在主程序段的運(yùn)行過(guò)程中逐步完成。每當(dāng)需要調(diào)用一個(gè)新段時(shí)，再將這個(gè)新段裝配好，并與主程序段鏈接頁(yè)式存儲(chǔ)管理：難以完成動(dòng)態(tài)鏈接，其邏輯地址是一維的（2）鏈接間接字和鏈接中斷機(jī)器指令：直接尋址，間接尋址LOAD100LOAD100600600800直接尋址間接尋址100100數(shù)據(jù)間接字?jǐn)?shù)據(jù)

采用間接尋址時(shí)，間接地址指示的單元的內(nèi)容稱為間接字，在間接字中，