1、15.15.1存儲(chǔ)管理的功能存儲(chǔ)管理的功能5.25.2分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理5.35.3覆蓋與交換技術(shù)覆蓋與交換技術(shù)5.45.4頁式管理頁式管理5.55.5段式管理與段頁式管理段式管理與段頁式管理5.65.6局部性原理和抖動(dòng)問題局部性原理和抖動(dòng)問題6.66.6、UNIXUNIX存儲(chǔ)管理存儲(chǔ)管理第五章、存儲(chǔ)管理第五章、存儲(chǔ)管理 25.4 頁式管理頁式管理一、基本原理：一、基本原理：1）把作業(yè)地址空間劃分為大小相等的頁；）把作業(yè)地址空間劃分為大小相等的頁； 2）把內(nèi)存存儲(chǔ)空間劃分為大小相等的頁面；）把內(nèi)存存儲(chǔ)空間劃分為大小相等的頁面；3）作業(yè)需要）作業(yè)需要m頁存儲(chǔ)，則在內(nèi)存中尋找頁存儲(chǔ)，則在內(nèi)存

2、中尋找m個(gè)空閑頁面分個(gè)空閑頁面分配即可，無須連續(xù)。配即可，無須連續(xù)。1、頁面大小設(shè)置：、頁面大小設(shè)置：1K 4K2、邏輯地址結(jié)構(gòu)設(shè)置：、邏輯地址結(jié)構(gòu)設(shè)置：3、地址變換：頁式虛擬地址、地址變換：頁式虛擬地址 內(nèi)存物理地址內(nèi)存物理地址3二、靜態(tài)頁面管理二、靜態(tài)頁面管理原理：原理：把作業(yè)的全部程序和數(shù)據(jù)在執(zhí)行前裝入內(nèi)存的若干頁面。把作業(yè)的全部程序和數(shù)據(jù)在執(zhí)行前裝入內(nèi)存的若干頁面。1、數(shù)據(jù)結(jié)構(gòu)：、數(shù)據(jù)結(jié)構(gòu)：1）頁表頁表每個(gè)作業(yè)每個(gè)作業(yè)/進(jìn)程一張，記錄邏輯頁號(hào)和物理頁面號(hào)的進(jìn)程一張，記錄邏輯頁號(hào)和物理頁面號(hào)的對(duì)應(yīng)關(guān)系。對(duì)應(yīng)關(guān)系。2）請(qǐng)求表請(qǐng)求表系統(tǒng)一張，記錄所有作業(yè)的申請(qǐng)和分配情況。系統(tǒng)一張，記錄所有作

3、業(yè)的申請(qǐng)和分配情況。3）存儲(chǔ)頁面表存儲(chǔ)頁面表系統(tǒng)一張，記錄內(nèi)存所有頁面的分配情況。系統(tǒng)一張，記錄內(nèi)存所有頁面的分配情況。a）位示圖：）位示圖：每一位代表一頁面：每一位代表一頁面：1 - 已分，已分，0 - 未分未分b）空閑頁面鏈法：）空閑頁面鏈法：每頁首單元存放下一空閑頁面的地址。每頁首單元存放下一空閑頁面的地址。頁號(hào)頁號(hào)頁面號(hào)頁面號(hào)進(jìn)程號(hào)進(jìn)程號(hào)請(qǐng)求頁數(shù)請(qǐng)求頁數(shù) 頁表始址頁表始址頁表長(zhǎng)度頁表長(zhǎng)度狀態(tài)狀態(tài)42、分配與回收：、分配與回收：分配：分配：回收：回收：1）消除請(qǐng)求表的表項(xiàng)；）消除請(qǐng)求表的表項(xiàng)；2）把頁表中各釋放頁）把頁表中各釋放頁面號(hào)插入空閑頁面表中；面號(hào)插入空閑頁面表中；3）釋放頁表空

4、間。）釋放頁表空間。53、地址變換、地址變換 頁表寄存器頁表寄存器 頁表長(zhǎng)度頁表長(zhǎng)度 頁表始址頁表始址頁號(hào)頁號(hào)P 頁內(nèi)地址頁內(nèi)地址W 頁式邏輯地址頁式邏輯地址頁號(hào)頁號(hào)頁面號(hào)頁面號(hào)0pb請(qǐng)請(qǐng) 求求 表表越界越界+* 頁長(zhǎng)頁長(zhǎng)內(nèi)存物理地址內(nèi)存物理地址+64、快表、快表引入原因：引入原因：頁式管理要訪問內(nèi)存兩次，第一次訪問頁表得頁面號(hào)，第頁式管理要訪問內(nèi)存兩次，第一次訪問頁表得頁面號(hào)，第二次根據(jù)得到物理地址訪問，速度慢。二次根據(jù)得到物理地址訪問，速度慢。高速聯(lián)想存儲(chǔ)器（快表）：高速聯(lián)想存儲(chǔ)器（快表）：由半導(dǎo)體存儲(chǔ)器組成，存儲(chǔ)當(dāng)前、最近、經(jīng)常訪問的頁表項(xiàng)；由半導(dǎo)體存儲(chǔ)器組成，存儲(chǔ)當(dāng)前、最近、經(jīng)常訪問的

5、頁表項(xiàng)；查詢頁面號(hào)時(shí)，同時(shí)查快表：查詢頁面號(hào)時(shí)，同時(shí)查快表：在快表中，得頁面號(hào)，停止查頁表；在快表中，得頁面號(hào)，停止查頁表；不在快表中，把查頁表所得結(jié)果填入快表。不在快表中，把查頁表所得結(jié)果填入快表。特點(diǎn)：特點(diǎn)：需硬件得支持，開銷大，但可換取訪問速度的提高。需硬件得支持，開銷大，但可換取訪問速度的提高。75、靜態(tài)頁式管理的優(yōu)缺點(diǎn)、靜態(tài)頁式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：較好解決碎片問題，限制了碎片的大小和數(shù)量，提高較好解決碎片問題，限制了碎片的大小和數(shù)量，提高了內(nèi)存利用率。了內(nèi)存利用率。缺點(diǎn)：缺點(diǎn)：1）動(dòng)態(tài)地址變換開銷大，以時(shí)間換取空間；）動(dòng)態(tài)地址變換開銷大，以時(shí)間換取空間；2）出現(xiàn)頁內(nèi)碎片（每個(gè)作業(yè)

6、末頁中）；）出現(xiàn)頁內(nèi)碎片（每個(gè)作業(yè)末頁中）；3）作業(yè)仍需全部裝入內(nèi)存，作業(yè)大小受限制，沒有實(shí)現(xiàn)）作業(yè)仍需全部裝入內(nèi)存，作業(yè)大小受限制，沒有實(shí)現(xiàn)內(nèi)存內(nèi)存“擴(kuò)充擴(kuò)充”。8三、動(dòng)態(tài)頁式管理（請(qǐng)求頁式）三、動(dòng)態(tài)頁式管理（請(qǐng)求頁式）原理：原理：作業(yè)在允許前可以不全部裝入內(nèi)存，對(duì)即將執(zhí)行的作業(yè)在允許前可以不全部裝入內(nèi)存，對(duì)即將執(zhí)行的部分動(dòng)態(tài)裝入。部分動(dòng)態(tài)裝入。預(yù)調(diào)入方式：預(yù)調(diào)入方式：對(duì)外存中調(diào)入頁的順序分析、預(yù)測(cè)，把預(yù)計(jì)即將被訪問的若干頁提對(duì)外存中調(diào)入頁的順序分析、預(yù)測(cè)，把預(yù)計(jì)即將被訪問的若干頁提前調(diào)入內(nèi)存；前調(diào)入內(nèi)存；一次調(diào)入幾頁，缺頁中斷少，效率高；一次調(diào)入幾頁，缺頁中斷少，效率高；要求預(yù)測(cè)準(zhǔn)確，否則

7、效率反而低。要求預(yù)測(cè)準(zhǔn)確，否則效率反而低。請(qǐng)求頁式：請(qǐng)求頁式：當(dāng)被訪問的指令或數(shù)據(jù)不在內(nèi)存時(shí)，才發(fā)生缺頁中斷，將其所在頁當(dāng)被訪問的指令或數(shù)據(jù)不在內(nèi)存時(shí)，才發(fā)生缺頁中斷，將其所在頁調(diào)入；調(diào)入；容易實(shí)現(xiàn)，但經(jīng)常缺頁容易實(shí)現(xiàn)，但經(jīng)常缺頁 中斷，系統(tǒng)開銷大。中斷，系統(tǒng)開銷大。兩兩 種種 方方 式式91、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu) 頁表：頁表：2、地址變換機(jī)構(gòu)：、地址變換機(jī)構(gòu)： （基本同前）（基本同前）缺頁中斷缺頁中斷 地址變換地址變換缺頁中斷機(jī)構(gòu)：缺頁中斷機(jī)構(gòu)：1）發(fā)生在指令執(zhí)行期；）發(fā)生在指令執(zhí)行期；2）一條指令的執(zhí)行期可能發(fā)生多次缺頁中斷。）一條指令的執(zhí)行期可能發(fā)生多次缺頁中斷。頁號(hào)頁號(hào)頁面號(hào)頁面號(hào) 中斷

8、位中斷位外存始址外存始址 改變位改變位 訪問位訪問位10取指令取指令/數(shù)據(jù)數(shù)據(jù)是否在內(nèi)存？是否在內(nèi)存？ 缺頁中斷缺頁中斷，保護(hù)，保護(hù)CPU現(xiàn)場(chǎng)現(xiàn)場(chǎng)有無空閑頁面有無空閑頁面 選擇一頁選擇一頁淘汰置換淘汰置換調(diào)入所需頁調(diào)入所需頁地址變換地址變換得到實(shí)際地址得到實(shí)際地址執(zhí)行執(zhí)行3、管理流程、管理流程YYNN114、置換算法、置換算法功能：功能：缺頁中斷但內(nèi)存無空閑頁面時(shí)，選擇哪一個(gè)缺頁中斷但內(nèi)存無空閑頁面時(shí)，選擇哪一個(gè)頁面調(diào)出外存騰出空頁面？頁面調(diào)出外存騰出空頁面？抖動(dòng)現(xiàn)象：抖動(dòng)現(xiàn)象：由于置換算法選擇不當(dāng)，使剛換出的頁由要由于置換算法選擇不當(dāng)，使剛換出的頁由要馬上調(diào)入內(nèi)存，調(diào)入不久由被換出，使頁面調(diào)

9、馬上調(diào)入內(nèi)存，調(diào)入不久由被換出，使頁面調(diào)度過于頻繁，花銷增大。度過于頻繁，花銷增大。1）隨機(jī)淘汰算法）隨機(jī)淘汰算法2）輪轉(zhuǎn)法）輪轉(zhuǎn)法3）最近最久未用頁面置換算法）最近最久未用頁面置換算法4）理想型淘汰算法）理想型淘汰算法121）隨機(jī)淘汰算法：）隨機(jī)淘汰算法：原理：原理：隨機(jī)選擇任意一個(gè)頁面的內(nèi)容換出外存。隨機(jī)選擇任意一個(gè)頁面的內(nèi)容換出外存。特點(diǎn)：特點(diǎn)：簡(jiǎn)單，針對(duì)性不強(qiáng)。簡(jiǎn)單，針對(duì)性不強(qiáng)。132）輪轉(zhuǎn)法和先進(jìn)先出算法：）輪轉(zhuǎn)法和先進(jìn)先出算法：原理：原理：輪轉(zhuǎn)法：輪轉(zhuǎn)法：把滿頁面順序連接起來，缺頁時(shí)依次換出鏈把滿頁面順序連接起來，缺頁時(shí)依次換出鏈上頁面，不管駐留內(nèi)存的長(zhǎng)短。上頁面，不管駐留內(nèi)存的長(zhǎng)

10、短。先進(jìn)先出算法：先進(jìn)先出算法：把頁面按駐留內(nèi)存時(shí)間長(zhǎng)短鏈接，置把頁面按駐留內(nèi)存時(shí)間長(zhǎng)短鏈接，置換指針指向最久頁面，換出該指針指向頁面，調(diào)入頁換指針指向最久頁面，換出該指針指向頁面，調(diào)入頁入鏈尾。入鏈尾。特點(diǎn)：特點(diǎn)：基于基于CPU按線性順序訪問地址空間的思想，忽略按線性順序訪問地址空間的思想，忽略了非線性訪問的情況，效率不一定高。了非線性訪問的情況，效率不一定高。Belady現(xiàn)象：現(xiàn)象：作業(yè)可用頁面數(shù)增多，缺頁次數(shù)反而增加作業(yè)可用頁面數(shù)增多，缺頁次數(shù)反而增加。14一進(jìn)程有一進(jìn)程有5頁，訪問順序是：頁，訪問順序是：1-2-3-4-1-2-5-1-2-3-4-5可用可用3個(gè)頁面時(shí)：缺頁個(gè)頁面時(shí)：缺

11、頁9次次123412512345111444555555222111113333332222244可用可用4個(gè)頁面時(shí)：缺頁個(gè)頁面時(shí)：缺頁10次次12341251234511111155554422222211115333333222244444433315123412512345111111111333222222222443444555555可用可用4個(gè)頁面時(shí)，個(gè)頁面時(shí)，最近最久未用頁面置換算法：最近最久未用頁面置換算法：123412512345111111111115222222222223333555544444444333可用可用3個(gè)頁面時(shí)，理想型淘汰算法：個(gè)頁面時(shí)，理想型淘汰算法：

12、163）最近最久未用頁面置換算法：）最近最久未用頁面置換算法：原理：原理：某頁剛被訪問，則可能馬上還要被訪問；若長(zhǎng)期不被某頁剛被訪問，則可能馬上還要被訪問；若長(zhǎng)期不被訪問，則近期也不會(huì)被訪問；因此選擇自上次訪問到現(xiàn)在訪問，則近期也不會(huì)被訪問；因此選擇自上次訪問到現(xiàn)在期間最長(zhǎng)的頁面淘汰。期間最長(zhǎng)的頁面淘汰。實(shí)施：實(shí)施：每個(gè)頁表項(xiàng)增加一個(gè)訪問位，記錄上次訪問以來經(jīng)歷每個(gè)頁表項(xiàng)增加一個(gè)訪問位，記錄上次訪問以來經(jīng)歷的時(shí)間的時(shí)間t，選擇，選擇t最大的頁面淘汰。最大的頁面淘汰。近似算法：近似算法：最不經(jīng)常使用頁面淘汰算法最不經(jīng)常使用頁面淘汰算法訪問位：記錄上次缺頁至今頁面的訪問次數(shù)；訪問位：記錄上次缺頁至

13、今頁面的訪問次數(shù)；缺頁時(shí)選訪問位值最小的淘汰，而后全部清零。缺頁時(shí)選訪問位值最小的淘汰，而后全部清零。最近未用頁面淘汰算法最近未用頁面淘汰算法周期性對(duì)所有訪問位置周期性對(duì)所有訪問位置0（未訪），一個(gè)周期內(nèi)被訪問，（未訪），一個(gè)周期內(nèi)被訪問，置置1；缺頁時(shí)，再訪問位為；缺頁時(shí)，再訪問位為0的頁面中選擇淘汰。的頁面中選擇淘汰。174）理想型淘汰算法：）理想型淘汰算法：原理：原理：欲知進(jìn)程訪問頁的順序，把當(dāng)前頁后不欲知進(jìn)程訪問頁的順序，把當(dāng)前頁后不再出現(xiàn)的頁或離當(dāng)前頁最遠(yuǎn)的頁（最長(zhǎng)時(shí)間再出現(xiàn)的頁或離當(dāng)前頁最遠(yuǎn)的頁（最長(zhǎng)時(shí)間不訪問）淘汰。不訪問）淘汰。特點(diǎn)：特點(diǎn)：無法實(shí)現(xiàn)，僅作為比較、評(píng)價(jià)其它算法無法

14、實(shí)現(xiàn)，僅作為比較、評(píng)價(jià)其它算法的一個(gè)標(biāo)準(zhǔn)。的一個(gè)標(biāo)準(zhǔn)。185、動(dòng)態(tài)頁式管理優(yōu)缺點(diǎn)、動(dòng)態(tài)頁式管理優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：1）“擴(kuò)充擴(kuò)充”內(nèi)存，作業(yè)不需全裝入，有效利用內(nèi)存，提高內(nèi)存，作業(yè)不需全裝入，有效利用內(nèi)存，提高并發(fā)程度；并發(fā)程度；2）便于共享公共信息：通過頁表連接；）便于共享公共信息：通過頁表連接；3）基本解決碎片問題。）基本解決碎片問題。缺點(diǎn)：缺點(diǎn)：1）地址變換、缺頁中斷機(jī)構(gòu)需要軟硬件的支持，開銷大；）地址變換、缺頁中斷機(jī)構(gòu)需要軟硬件的支持，開銷大；2）置換算法不當(dāng)容易產(chǎn)生）置換算法不當(dāng)容易產(chǎn)生“抖動(dòng)抖動(dòng)”現(xiàn)象；現(xiàn)象；3）仍存在頁內(nèi)碎片。）仍存在頁內(nèi)碎片。19頁式管理評(píng)價(jià)頁式管理評(píng)價(jià)1、解決外

15、碎片，出現(xiàn)少量?jī)?nèi)碎片；、解決外碎片，出現(xiàn)少量?jī)?nèi)碎片；2、動(dòng)態(tài)頁式管理擴(kuò)充了內(nèi)存；、動(dòng)態(tài)頁式管理擴(kuò)充了內(nèi)存；3、開銷大，以時(shí)間換取空間。、開銷大，以時(shí)間換取空間。頁式管理的局限頁式管理的局限 數(shù)據(jù)的動(dòng)態(tài)變化？數(shù)據(jù)的動(dòng)態(tài)變化？ 編譯鏈接的方便？編譯鏈接的方便？ 程序或數(shù)據(jù)的共享？程序或數(shù)據(jù)的共享？ 邏輯空間的限制？邏輯空間的限制？20215.5 段式管理與段頁式管理段式管理與段頁式管理（一）段式管理（一）段式管理一、基本原理一、基本原理1、引入、引入分區(qū)和分頁管理分區(qū)和分頁管理 ： 一維線性空間，空間不連續(xù)，邏輯關(guān)系連續(xù)；一維線性空間，空間不連續(xù)，邏輯關(guān)系連續(xù)； 難于共享公共子程序和數(shù)據(jù)。難于共享

16、公共子程序和數(shù)據(jù)?？紤]把邏輯功能上獨(dú)立的程序和數(shù)據(jù)自成一段存儲(chǔ)?？紤]把邏輯功能上獨(dú)立的程序和數(shù)據(jù)自成一段存儲(chǔ)。222、原理、原理把邏輯上獨(dú)立的信息定義為一段，每段有段名、段把邏輯上獨(dú)立的信息定義為一段，每段有段名、段號(hào)，段內(nèi)從號(hào)，段內(nèi)從0開始編址，形成一維線性空間，段長(zhǎng)不固開始編址，形成一維線性空間，段長(zhǎng)不固定；定；每個(gè)作業(yè)由若干段構(gòu)成，地址空間是二維的：每個(gè)作業(yè)由若干段構(gòu)成，地址空間是二維的：段號(hào)段號(hào)S段內(nèi)地址段內(nèi)地址W233、分段與分頁的區(qū)別、分段與分頁的區(qū)別分分 頁頁分分 段段“頁頁”是信息的物理單位，是信息的物理單位，大小固定。大小固定?！岸味巍笔切畔⒌倪壿媶挝?，是信息的邏輯單位，長(zhǎng)度

17、不定。長(zhǎng)度不定。分頁對(duì)用戶不透明，主要針分頁對(duì)用戶不透明，主要針對(duì)內(nèi)存管理。對(duì)內(nèi)存管理。分段用戶可見，便于信息的分段用戶可見，便于信息的共享。共享。一維線性地址空間，頁間邏一維線性地址空間，頁間邏輯地址連續(xù)。輯地址連續(xù)。二維線性地址空間，段間邏二維線性地址空間，段間邏輯地址不連續(xù)，段內(nèi)連續(xù)。輯地址不連續(xù)，段內(nèi)連續(xù)。24二、段式管理的實(shí)現(xiàn)二、段式管理的實(shí)現(xiàn)1、數(shù)據(jù)結(jié)構(gòu)：、數(shù)據(jù)結(jié)構(gòu)：1）段表：段表： （每個(gè)作業(yè)一個(gè)）（每個(gè)作業(yè)一個(gè)）記錄作業(yè)中每段的基本情況。記錄作業(yè)中每段的基本情況。2）內(nèi)存分配表：內(nèi)存分配表： （系統(tǒng)一張）（系統(tǒng)一張）記錄內(nèi)存空閑區(qū)的情況。記錄內(nèi)存空閑區(qū)的情況?？臻e區(qū)表、空閑區(qū)鏈

18、空閑區(qū)表、空閑區(qū)鏈3）作業(yè)表：作業(yè)表： （系統(tǒng)一張）（系統(tǒng)一張）記錄每個(gè)作業(yè)的段表起始地址和長(zhǎng)度。記錄每個(gè)作業(yè)的段表起始地址和長(zhǎng)度。段號(hào)段號(hào)始址始址 長(zhǎng)度長(zhǎng)度 存取方式存取方式 內(nèi)內(nèi)/外存外存 訪問位訪問位修改位修改位25262、分配與回收、分配與回收訪問段在內(nèi)存？訪問段在內(nèi)存？缺段中斷缺段中斷有無空閑區(qū)裝該段？有無空閑區(qū)裝該段？選一段選一段/幾段淘汰到外存幾段淘汰到外存調(diào)入該段調(diào)入該段地址變換地址變換NNYY回收：回收：修改該段表項(xiàng)修改該段表項(xiàng)回收區(qū)插入內(nèi)回收區(qū)插入內(nèi)存分配表存分配表27缺段中斷處理過程缺段中斷處理過程28相關(guān)算法相關(guān)算法空閑區(qū)分配算法：空閑區(qū)分配算法：1、最先適應(yīng)算法最先適

19、應(yīng)算法2、最佳適應(yīng)算法、最佳適應(yīng)算法3、最壞適應(yīng)算法、最壞適應(yīng)算法淘汰置換算法：淘汰置換算法：1、輪轉(zhuǎn)法輪轉(zhuǎn)法2、先進(jìn)先出算法、先進(jìn)先出算法3、最近最久未用段置換算法：、最近最久未用段置換算法： 最不經(jīng)常使用段淘汰算法最不經(jīng)常使用段淘汰算法 最近未用段淘汰算法最近未用段淘汰算法29算法比較算法比較碎片碎片大空閑區(qū)大空閑區(qū)搜索釋放速度搜索釋放速度最先適應(yīng)法最先適應(yīng)法低址多低址多有有快快（一般不排序）（一般不排序）循環(huán)首次適循環(huán)首次適應(yīng)算法應(yīng)算法分布均勻分布均勻無無最佳適應(yīng)法最佳適應(yīng)法 小碎片多小碎片多有有較慢較慢（鏈重排）（鏈重排）最壞適應(yīng)法最壞適應(yīng)法少少無無30地址變換地址變換313、地址變換

20、、地址變換 段表寄存器段表寄存器 段表長(zhǎng)度段表長(zhǎng)度 段表始址段表始址段號(hào)段號(hào)S 段內(nèi)地址段內(nèi)地址W 段式邏輯地址段式邏輯地址段號(hào)段號(hào)始址始址0S？K作作 業(yè)業(yè) 表表越界越界+內(nèi)存物理地址內(nèi)存物理地址+快表快表323、段的共享、段的共享1）一個(gè)副本，多個(gè)進(jìn)程享用，節(jié)省存儲(chǔ)空間；）一個(gè)副本，多個(gè)進(jìn)程享用，節(jié)省存儲(chǔ)空間；2）共享段的程序和數(shù)據(jù)不允許修改；）共享段的程序和數(shù)據(jù)不允許修改；3）對(duì)每個(gè)共享段設(shè)置共享進(jìn)程計(jì)數(shù)）對(duì)每個(gè)共享段設(shè)置共享進(jìn)程計(jì)數(shù)count：分配：第一個(gè)共享請(qǐng)求，將段調(diào)入內(nèi)存，分配：第一個(gè)共享請(qǐng)求，將段調(diào)入內(nèi)存， count加加1；其后的請(qǐng)求，；其后的請(qǐng)求，只需對(duì)只需對(duì)count加加

21、1。釋放：釋放： count減減1，當(dāng)，當(dāng)count=0時(shí)，可以被淘汰出內(nèi)存。時(shí)，可以被淘汰出內(nèi)存。334、段的保護(hù)、段的保護(hù)1）地址越界保護(hù)：）地址越界保護(hù)：每段設(shè)置段表寄存器，記錄該段始址和長(zhǎng)度，每條每段設(shè)置段表寄存器，記錄該段始址和長(zhǎng)度，每條指令執(zhí)行前判斷是否越界。指令執(zhí)行前判斷是否越界。2）存取方式控制保護(hù)：）存取方式控制保護(hù)：段表項(xiàng)中設(shè)段表項(xiàng)中設(shè)“存取方式存取方式”一項(xiàng)，規(guī)定進(jìn)程訪問該段的權(quán)一項(xiàng)，規(guī)定進(jìn)程訪問該段的權(quán)限：限：共享段：共享段：賦予共享該段的進(jìn)程不同的權(quán)限；賦予共享該段的進(jìn)程不同的權(quán)限；非共享段：非共享段：對(duì)過程段只調(diào)用，對(duì)數(shù)據(jù)段只讀或特定用戶寫。對(duì)過程段只調(diào)用，對(duì)數(shù)據(jù)段

22、只讀或特定用戶寫。34三、段式管理的優(yōu)缺點(diǎn)三、段式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：1、便于程序的模塊化處理；、便于程序的模塊化處理；2、便于共享分段；、便于共享分段；3、實(shí)現(xiàn)了內(nèi)存的擴(kuò)充。、實(shí)現(xiàn)了內(nèi)存的擴(kuò)充。4、便于實(shí)現(xiàn)動(dòng)態(tài)鏈接；、便于實(shí)現(xiàn)動(dòng)態(tài)鏈接；5、段長(zhǎng)可以動(dòng)態(tài)增長(zhǎng)，便于處理變化的數(shù)據(jù)結(jié)構(gòu)；、段長(zhǎng)可以動(dòng)態(tài)增長(zhǎng)，便于處理變化的數(shù)據(jù)結(jié)構(gòu)；缺點(diǎn)：缺點(diǎn)：1、碎片較多，影響內(nèi)存利用率；、碎片較多，影響內(nèi)存利用率；2、分段段長(zhǎng)受內(nèi)存可用空間的限制；、分段段長(zhǎng)受內(nèi)存可用空間的限制；3、硬件支持多，開銷大；、硬件支持多，開銷大；4、采用拼接手段，增加難度；、采用拼接手段，增加難度；5、段長(zhǎng)可以動(dòng)態(tài)變化，對(duì)外存的管

23、理帶來難度。、段長(zhǎng)可以動(dòng)態(tài)變化，對(duì)外存的管理帶來難度。35（二）段頁式存儲(chǔ)管理（二）段頁式存儲(chǔ)管理一、基本原理：一、基本原理：1、引入：、引入：分頁管理分頁管理分段管理分段管理優(yōu)優(yōu)點(diǎn)點(diǎn)管理存儲(chǔ)空間上的優(yōu)點(diǎn)：管理存儲(chǔ)空間上的優(yōu)點(diǎn)：克服碎片，提高內(nèi)存利用率?？朔槠?，提高內(nèi)存利用率。邏輯調(diào)用上的優(yōu)點(diǎn)邏輯調(diào)用上的優(yōu)點(diǎn)：反映邏輯結(jié)構(gòu)，便于段的共享、反映邏輯結(jié)構(gòu)，便于段的共享、動(dòng)態(tài)增長(zhǎng)和保護(hù)。動(dòng)態(tài)增長(zhǎng)和保護(hù)。缺缺點(diǎn)點(diǎn)難于共享：難于共享：共享某程序段時(shí)，需要進(jìn)行共享某程序段時(shí)，需要進(jìn)行多次頁間鏈接。多次頁間鏈接。內(nèi)存利用率不高：內(nèi)存利用率不高：段長(zhǎng)受內(nèi)存空間限制，存在碎段長(zhǎng)受內(nèi)存空間限制，存在碎片問題。片

24、問題。結(jié)結(jié) 分頁管理內(nèi)存分頁管理內(nèi)存合合 分段管理外存分段管理外存362、段頁式管理原理、段頁式管理原理把進(jìn)程分為若干邏輯上獨(dú)立的段；（程序員可見）把進(jìn)程分為若干邏輯上獨(dú)立的段；（程序員可見）每段分為若干頁，每段內(nèi)容可以分頁存儲(chǔ)；（系統(tǒng)自動(dòng)完成）每段分為若干頁，每段內(nèi)容可以分頁存儲(chǔ)；（系統(tǒng)自動(dòng)完成）內(nèi)存分為大小相同的頁面，存儲(chǔ)某段的某頁；內(nèi)存分為大小相同的頁面，存儲(chǔ)某段的某頁；段號(hào)段號(hào)S段內(nèi)頁號(hào)段內(nèi)頁號(hào)P頁內(nèi)偏址頁內(nèi)偏址d0 7 8 11 12 23段內(nèi)偏址段內(nèi)偏址WP = W/頁長(zhǎng)頁長(zhǎng) d = W mod 頁長(zhǎng)頁長(zhǎng)37二、段頁式管理的實(shí)現(xiàn)二、段頁式管理的實(shí)現(xiàn)1、數(shù)據(jù)結(jié)構(gòu)：、數(shù)據(jù)結(jié)構(gòu)：1）作業(yè)

25、表：作業(yè)表：系統(tǒng)一張系統(tǒng)一張2）段表：段表：作業(yè)一張作業(yè)一張3）頁表：頁表：每段一張每段一張4）空閑頁面表：空閑頁面表：位示圖位示圖/空閑頁面鏈空閑頁面鏈段號(hào)段號(hào)頁表始址頁表始址頁表長(zhǎng)度頁表長(zhǎng)度其它其它頁號(hào)頁號(hào)頁面號(hào)頁面號(hào)內(nèi)內(nèi)/外存外存訪問位訪問位修改位修改位外存始址外存始址38段表始址段表始址 段表長(zhǎng)度段表長(zhǎng)度 作業(yè)表作業(yè)表段表寄存器段表寄存器段段號(hào)號(hào)其其它它頁表頁表長(zhǎng)度長(zhǎng)度頁表頁表始址始址0410241210282310300段頁表段頁表0 101 112 173 141段頁表段頁表2段頁表段頁表0 121 180 191 212 23102410271028102910301032101

26、1121314151617181920212223段段 表表392、動(dòng)態(tài)訪問、分配、調(diào)入：、動(dòng)態(tài)訪問、分配、調(diào)入：403、地址變換、地址變換 作業(yè)表作業(yè)表 段表寄存器段表寄存器 段段號(hào)號(hào)頁表頁表始址始址S始址始址+SPd邏邏 輯輯 地地 址址段表始址段表始址段表長(zhǎng)度段表長(zhǎng)度段表段表頁頁號(hào)號(hào)頁面頁面號(hào)號(hào)P頁面頁面號(hào)號(hào)P內(nèi)存物理地址內(nèi)存物理地址*頁長(zhǎng)頁長(zhǎng)頁表頁表快表快表41三、段頁式管理的優(yōu)缺點(diǎn)三、段頁式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：具有請(qǐng)求頁式和分段管理的全部?jī)?yōu)點(diǎn)。具有請(qǐng)求頁式和分段管理的全部?jī)?yōu)點(diǎn)。內(nèi)存利用率、擴(kuò)充程度、便于共享、模塊化。內(nèi)存利用率、擴(kuò)充程度、便于共享、模塊化。缺點(diǎn)：缺點(diǎn)：軟硬件開銷大

27、：缺段中斷、缺頁中斷、地址變換軟硬件開銷大：缺段中斷、缺頁中斷、地址變換管理表格占據(jù)存儲(chǔ)空間大：段表、頁表管理表格占據(jù)存儲(chǔ)空間大：段表、頁表42各存儲(chǔ)管理方法的比較各存儲(chǔ)管理方法的比較1、內(nèi)存利用率、內(nèi)存利用率 碎片多少？非連續(xù)存放？部分裝入？碎片多少？非連續(xù)存放？部分裝入？2、內(nèi)存擴(kuò)充、內(nèi)存擴(kuò)充 全裝？全裝？3、信息共享、信息共享 方便？方便？4、軟硬件開銷、軟硬件開銷 大??？大??？5、虛擬地址空間、虛擬地址空間 一維？二維？一維？二維？6、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu) 哪些表格？哪些表格？435.6 局部性原理和抖動(dòng)問題局部性原理和抖動(dòng)問題局部性原理：局部性原理：在一段時(shí)間內(nèi)，在一段時(shí)間內(nèi)，CPU總

28、是集中地訪問程序中的某一部總是集中地訪問程序中的某一部分，而不是隨機(jī)地對(duì)程序所有部分具有平均訪問概率。分，而不是隨機(jī)地對(duì)程序所有部分具有平均訪問概率。內(nèi)存大小與內(nèi)外內(nèi)存大小與內(nèi)外存交換頻率關(guān)系存交換頻率關(guān)系抖動(dòng)：抖動(dòng)：內(nèi)外存頻繁交換造成內(nèi)外存頻繁交換造成輸入輸出處理時(shí)間增輸入輸出處理時(shí)間增加，使系統(tǒng)性能大大加，使系統(tǒng)性能大大下降。下降。44解決抖動(dòng)問題的辦法解決抖動(dòng)問題的辦法1、擴(kuò)大工作集：不讓缺頁進(jìn)程換出。、擴(kuò)大工作集：不讓缺頁進(jìn)程換出。2、選擇適合的淘汰算法。、選擇適合的淘汰算法。45存儲(chǔ)管理總結(jié)存儲(chǔ)管理總結(jié)分區(qū)分區(qū)分頁分頁分段分段段頁段頁靜態(tài)靜態(tài)動(dòng)態(tài)動(dòng)態(tài)靜態(tài)靜態(tài)動(dòng)態(tài)動(dòng)態(tài)碎片問題碎片問題非

29、連續(xù)存放非連續(xù)存放全部裝入全部裝入內(nèi)存利用率內(nèi)存利用率擴(kuò)充內(nèi)存擴(kuò)充內(nèi)存方便共享方便共享461、P139：5.132、對(duì)訪問串：、對(duì)訪問串：1、2、3、4、1、2、3、5、1、2、3、4、5指出在駐留集大小分別為指出在駐留集大小分別為3和和4時(shí)，使用時(shí)，使用FIFO、LRU替換算法和理想淘汰算法的缺頁次數(shù)。替換算法和理想淘汰算法的缺頁次數(shù)。作作 業(yè)業(yè) 二二473、某虛存的用戶編程空間為、某虛存的用戶編程空間為32頁，每頁長(zhǎng)頁，每頁長(zhǎng)1KB，內(nèi)，內(nèi)存容量存容量16KB。若某時(shí)刻該用戶已調(diào)入內(nèi)存的頁的虛頁號(hào)與。若某時(shí)刻該用戶已調(diào)入內(nèi)存的頁的虛頁號(hào)與物理頁面號(hào)對(duì)照表如下表所示。物理頁面號(hào)對(duì)照表如下表所

30、示。求出虛地址求出虛地址0A8C(H）、）、18C5(H)相對(duì)應(yīng)的物理單元相對(duì)應(yīng)的物理單元地址，若不在內(nèi)存，則表明地址，若不在內(nèi)存，則表明“無法得地址無法得地址”。（注：。（注：H表示表示16進(jìn)制，結(jié)果也用進(jìn)制，結(jié)果也用16進(jìn)制表示）進(jìn)制表示）虛頁號(hào)虛頁號(hào)物理頁面物理頁面081724310486.6、UNIX存儲(chǔ)管理存儲(chǔ)管理一、空間的劃分：一、空間的劃分： （VAX-11）虛擬空間劃分為虛擬空間劃分為4個(gè)功能區(qū)，虛存尋址范圍：個(gè)功能區(qū)，虛存尋址范圍：0 232 - 1 。P0（程序區(qū)）（程序區(qū)）P1（控制區(qū)）（控制區(qū)）核心區(qū)核心區(qū)保留區(qū)保留區(qū)進(jìn)程空間進(jìn)程空間系統(tǒng)空間系統(tǒng)空間0230231231

31、 + 230232虛擬存儲(chǔ)器虛擬存儲(chǔ)器512字節(jié)一頁，共字節(jié)一頁，共223 - 1 頁。頁。物理存儲(chǔ)器物理存儲(chǔ)器512字節(jié)一個(gè)頁面，共字節(jié)一個(gè)頁面，共221 - 1 個(gè)頁面。個(gè)頁面。每個(gè)區(qū)有各自頁表。每個(gè)區(qū)有各自頁表。頁表的長(zhǎng)度和起始地址記錄在長(zhǎng)度寄存器和基址寄存器中。頁表的長(zhǎng)度和起始地址記錄在長(zhǎng)度寄存器和基址寄存器中。0001101149地址結(jié)構(gòu)地址結(jié)構(gòu)虛頁號(hào)虛頁號(hào)頁內(nèi)偏移量頁內(nèi)偏移量分分 區(qū)區(qū)頁面號(hào)頁面號(hào)頁內(nèi)偏移量頁內(nèi)偏移量?jī)?nèi)存內(nèi)存外存外存存取存取權(quán)限權(quán)限修改修改位位訪問位訪問位年齡位年齡位物理物理頁面號(hào)頁面號(hào)虛擬地址：虛擬地址：內(nèi)存地址：內(nèi)存地址：頁表項(xiàng)組成：頁表項(xiàng)組成：31 9 8 0

32、31 30 9 8 031 30 27 26 25 21 20 050核心區(qū)核心區(qū)虛址空間虛址空間與與內(nèi)存空間內(nèi)存空間的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系核心正文段核心正文段數(shù)據(jù)段數(shù)據(jù)段核心頁表核心頁表內(nèi)存位示圖頁表內(nèi)存位示圖頁表0#進(jìn)程頁表進(jìn)程頁表其他專用區(qū)頁表其他專用區(qū)頁表諸進(jìn)程頁表諸進(jìn)程頁表核心正文段核心正文段數(shù)據(jù)段數(shù)據(jù)段核心頁表核心頁表和和進(jìn)程頁表進(jìn)程頁表內(nèi)存位示圖內(nèi)存位示圖0#進(jìn)程頁表進(jìn)程頁表0#進(jìn)程堆棧進(jìn)程堆棧進(jìn)程可用物理空間進(jìn)程可用物理空間I/O專用區(qū)專用區(qū)023151內(nèi)存中核心頁表和進(jìn)程頁表的關(guān)系內(nèi)存中核心頁表和進(jìn)程頁表的關(guān)系52二、內(nèi)存的分配和釋放二、內(nèi)存的分配和釋放1、進(jìn)程頁表的分配：、進(jìn)程頁表的分配：特點(diǎn)：特點(diǎn)：連續(xù)存放，變化少。連續(xù)存放，變化少。方式：方式：最先適應(yīng)算法（地址由低到高）最先適應(yīng)算法（地址由低到高）實(shí)施：實(shí)施：sptalloc - malloc，sptfree - mfree532、P0和和P1區(qū)的分配區(qū)的分配memall和釋放和釋放memfree ：位示圖記錄頁面的分配回收情況，大小由內(nèi)存大小和頁面位示圖記錄頁面的分配回收情況，大小由內(nèi)存大小和頁面長(zhǎng)