操作系統(tǒng)原理：第04章 存儲(chǔ)器管理

2022/11/19第四章存儲(chǔ)器管理第四章

存儲(chǔ)器管理4.1存儲(chǔ)器的層次結(jié)構(gòu)4.2程序的裝入和鏈接 4.3連續(xù)分配方式4.4基本分頁(yè)存儲(chǔ)管理方式4.5基本分段存儲(chǔ)管理方式4.6虛擬存儲(chǔ)器的基本概念4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.8頁(yè)面置換算法4.9請(qǐng)求分段存儲(chǔ)管理方式今天雖然主存價(jià)格已相當(dāng)便宜，但主存容量仍然是計(jì)算機(jī)四大硬件資源中最關(guān)鍵的資源。因此對(duì)主存的管理和有效使用仍然是今天操作系統(tǒng)十分重要的內(nèi)容。許多操作系統(tǒng)之間最明顯的區(qū)別特征之一往往是所使用的存儲(chǔ)管理方法不同。第四章

存儲(chǔ)器管理存儲(chǔ)管理功能存儲(chǔ)分配回收存儲(chǔ)共享存儲(chǔ)保護(hù)存儲(chǔ)擴(kuò)充地址映射分配回收對(duì)象內(nèi)存、外存(相同方法)分配回收時(shí)刻進(jìn)程創(chuàng)建、撤銷(xiāo)、交換、長(zhǎng)度變化目的：節(jié)省內(nèi)存、相互通信內(nèi)容：代碼、數(shù)據(jù)防止地址越界防止操作越權(quán)內(nèi)存、外存結(jié)合，虛擬存儲(chǔ)體系速度接近內(nèi)存，容量相當(dāng)外存邏輯地址=>物理地址硬件支持基址寄存器(base)、限長(zhǎng)寄存器(limit)、快表；4.1存儲(chǔ)器的層次結(jié)構(gòu)4.1.1多級(jí)存儲(chǔ)器結(jié)構(gòu)對(duì)于通用計(jì)算機(jī)而言，存儲(chǔ)層次至少應(yīng)具有三級(jí)：最高層為CPU寄存器，中間為主存，最底層是輔存。在較高檔的計(jì)算機(jī)中，還可以根據(jù)具體的功能分工細(xì)劃為寄存器、高速緩存、主存儲(chǔ)器、磁盤(pán)緩存、固定磁盤(pán)、可移動(dòng)存儲(chǔ)介質(zhì)等。存儲(chǔ)空間的分類(lèi)與性質(zhì)4.1.1多級(jí)存儲(chǔ)器結(jié)構(gòu)4.1.2主存儲(chǔ)器與寄存器1.主存儲(chǔ)器寄存器訪(fǎng)問(wèn)速度最快，完全能與CPU協(xié)調(diào)工作，但價(jià)格卻十分昂貴，因此容量不可能做得很大。寄存器用于加速存儲(chǔ)器的訪(fǎng)問(wèn)速度。用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，也稱(chēng)可執(zhí)行存儲(chǔ)器。CPU的控制部件只能從主存儲(chǔ)器中取得指令和數(shù)據(jù)。2.寄存器4.1.3高速緩存和磁盤(pán)緩存1．高速緩存容量大于或遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個(gè)數(shù)量級(jí)左右。將主存中一些經(jīng)常訪(fǎng)問(wèn)的信息存放在高速緩存中,可大幅度提高程序執(zhí)行速度。2．磁盤(pán)緩存磁盤(pán)的I/O速度遠(yuǎn)低于對(duì)主存的訪(fǎng)問(wèn)速度，因此將頻繁使用的一部分磁盤(pán)數(shù)據(jù)和信息，暫時(shí)存放在磁盤(pán)緩存中，可減少訪(fǎng)問(wèn)磁盤(pán)的次數(shù)。4.2程序的裝入和鏈接用戶(hù)源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序.3.裝入由裝入程序?qū)⒀b入模塊裝入內(nèi)存。1.編譯由編譯程序源代碼編譯成若干個(gè)目標(biāo)模塊2.鏈接由鏈接程序?qū)⒛繕?biāo)模塊和它們所需要的庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊4.2程序的裝入和鏈接……鏈接程序裝入模塊裝入程序第一步第二步第三步編譯程序產(chǎn)生的目標(biāo)模塊庫(kù)地址空間程序的名空間用戶(hù)編程所用的地址稱(chēng)為邏輯地址（或程序地址，或虛地址）。由邏輯地址組成的空間稱(chēng)為邏輯地址空間（或程序地址空間）。內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這種編號(hào)稱(chēng)為內(nèi)存地址（或稱(chēng)為物理地址，絕對(duì)地址）。內(nèi)存地址的集合稱(chēng)為內(nèi)存空間（或物理地址空間）。地址映射LoadA2003456

。。物理地址空間LoadAdata1data13456名空間LoadA2003456編譯連接邏輯地址空間

源程序經(jīng)過(guò)匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程序都是以0為基址順序進(jìn)行編址的，原來(lái)用符號(hào)名訪(fǎng)問(wèn)的單元用具體的數(shù)據(jù)——單元號(hào)取代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱(chēng)為作業(yè)的邏輯地址空間，簡(jiǎn)稱(chēng)邏輯空間。在邏輯空間中每條指令的地址和指令中要訪(fǎng)問(wèn)的操作數(shù)地址統(tǒng)稱(chēng)為邏輯地址。地址空間地址映射LoadA2003456

。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間BA=1000

把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱(chēng)為內(nèi)存地址（物理地址、絕對(duì)地址、實(shí)地址），存儲(chǔ)單元占8位，稱(chēng)作字節(jié)（byte）。物理地址的集合稱(chēng)為物理地址空間（主存地址空間），它是一個(gè)一維的線(xiàn)性空間。4.2.1程序的裝入將一個(gè)模塊裝入內(nèi)存時(shí)，可采用三種方式：絕對(duì)裝入方式重定位裝入方式

動(dòng)態(tài)運(yùn)行時(shí)裝入方式

在多道程序環(huán)境下，要使程序運(yùn)行，必須為之先建立進(jìn)程。創(chuàng)建進(jìn)程的第一件事是將程序和數(shù)據(jù)裝入內(nèi)存。如果在編譯時(shí)知道程序駐留在主存的具體位置,則編譯程序?qū)a(chǎn)生物理地址的目標(biāo)代碼.模塊裝入后,由于程序中的邏輯地址與實(shí)際主存的地址完全相同,故不需要對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改.1絕對(duì)裝入方式絕對(duì)裝入方式只能將目標(biāo)模塊裝入到主存事先指定的固定位置,只適用于單道程序環(huán)境.MoveAX,[2500]543212000210025003000絕對(duì)裝入方式編譯時(shí)產(chǎn)生的絕對(duì)地址MoveAX,[2500]5432120002100250030000內(nèi)存空間FFFF重定位（Relocation）★重定位：在一般情況下，一個(gè)作業(yè)在裝入時(shí)分配到的存儲(chǔ)空間和它的地址空間是不一致的。由于不一致所引起的對(duì)有關(guān)地址部分的調(diào)整過(guò)程，就是我們所說(shuō)的地址重定位。靜態(tài)重定位動(dòng)態(tài)重定位在多道程序環(huán)境下，目標(biāo)模塊的起始地址通常從0開(kāi)始，程序中的其他地址都是相對(duì)于起始地址計(jì)算的。因此應(yīng)采用可重定位裝入方式，根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。靜態(tài)重定位:是在裝入時(shí)由裝配程序一次性完成的，以后不再改變.物理地址=邏輯地址+程序在內(nèi)存的首地址優(yōu)點(diǎn)：無(wú)需硬件支持，容易實(shí)現(xiàn)。缺點(diǎn)：

1.程序經(jīng)地址重定位后不能再移動(dòng)了；

2.程序在內(nèi)存空間只能連續(xù)存儲(chǔ)；2可重定位裝入方式LoadBX,032543210832124LoadBX,13254321100108132244內(nèi)存空間FFFF裝入程序靜態(tài)重定位邏輯地址空間3．動(dòng)態(tài)運(yùn)行時(shí)裝入方式程序執(zhí)行過(guò)程中，當(dāng)訪(fǎng)問(wèn)指令或數(shù)據(jù)時(shí)，才進(jìn)行的地址變換方法，稱(chēng)為動(dòng)態(tài)重定位?？坑布刂纷儞Q機(jī)構(gòu)實(shí)現(xiàn)的?；刂芳拇嫫骱鸵粋€(gè)地址轉(zhuǎn)換線(xiàn)路組成物理地址=邏輯地址+基址寄存器優(yōu)點(diǎn)：可對(duì)內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛存的基礎(chǔ)；有利于程序段的共享。LoadBX,032543210832124

LoadBX,03254321100108132244內(nèi)存空間FFFF裝入程序作業(yè)的裝入CPU+邏輯地址032100基地址寄存器物理地址LoadBX,03254321100108132244內(nèi)存空間FFFF地址轉(zhuǎn)換動(dòng)態(tài)重定位1324.2.2程序的鏈接根據(jù)鏈接時(shí)間的不同，可把鏈接分成如下三種：(1)靜態(tài)鏈接。(2)裝入時(shí)動(dòng)態(tài)鏈接。(3)運(yùn)行時(shí)動(dòng)態(tài)鏈接。1靜態(tài)鏈接方式在程序運(yùn)行之前，先將各個(gè)目標(biāo)模塊及他們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝入模塊，運(yùn)行時(shí)直接裝入內(nèi)存。這種事先進(jìn)行鏈接，以后不再拆開(kāi)的鏈接方式稱(chēng)之靜態(tài)鏈接。需要解決兩個(gè)問(wèn)題此時(shí)必須修改被調(diào)用模塊的邏輯地址。同時(shí)轉(zhuǎn)變模塊中使用的外部調(diào)用符號(hào)。模塊ACALLB;RETURN模塊BCALLC;RETURN模塊CRETURN0L-10M-10N-1(a)目標(biāo)模塊模塊AJSRL;RETURN模塊BJSRL+M;RETURN模塊CRETURN0L-1LL+M-1L+ML+M+N-1(b)裝入模塊2.裝入時(shí)動(dòng)態(tài)鏈接將用戶(hù)源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。優(yōu)點(diǎn):(1)便于修改和更新(2)便于對(duì)目標(biāo)模塊的共享3.運(yùn)行時(shí)動(dòng)態(tài)鏈接指某些目標(biāo)模塊，當(dāng)在程序執(zhí)行中需要該模塊時(shí)，才對(duì)它進(jìn)行的鏈接。在執(zhí)行過(guò)程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅加快了程序的裝入過(guò)程，而且可節(jié)省大量的內(nèi)存空間。4.3連續(xù)分配方式把主存中的用戶(hù)區(qū)作為一個(gè)連續(xù)區(qū)域或者分成若干個(gè)連續(xù)區(qū)域進(jìn)行管理。可分為：?jiǎn)蔚肋B續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配4.3.1單一連續(xù)分配內(nèi)存分為系統(tǒng)區(qū)和用戶(hù)區(qū)；操作系統(tǒng)占用系統(tǒng)區(qū),其余的主存空間分配給一個(gè)用戶(hù)程序使用。特點(diǎn)：管理簡(jiǎn)單，主存利用率低，不支持多道，程序的運(yùn)行受主存容量限制。在任何時(shí)刻主存中最多只存有一個(gè)作業(yè)。4.3.2固定分區(qū)分配將內(nèi)存劃分成若干個(gè)連續(xù)區(qū)域，稱(chēng)為分區(qū)。每個(gè)分區(qū)的大小可以相同也可以不同，每個(gè)分區(qū)只能存儲(chǔ)一個(gè)程序。(1)分區(qū)大小相等。即使所有的內(nèi)存分區(qū)大小相等。其缺點(diǎn)是缺乏靈活性。(2)分區(qū)大小不等。把內(nèi)存區(qū)劃分成含有多個(gè)較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。2．內(nèi)存分配數(shù)據(jù)結(jié)構(gòu)：分區(qū)使用表為了便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的分區(qū)號(hào)、起始地址、大小及狀態(tài)(是否已分配)。區(qū)號(hào)大小(KB)起址(KB)狀態(tài)18K20K已分配232K28K已分配364K60K已分配4132K124K未分配OS20K28K60K124K256K進(jìn)程A（6K）（a）分區(qū)說(shuō)明表 （b）存儲(chǔ)空間分配情況圖固定分區(qū)使用表進(jìn)程B（25K）進(jìn)程C（36K）2．內(nèi)存分配固定分區(qū)分配算法流程圖要求xk大小的分區(qū)取分區(qū)說(shuō)明表的第一項(xiàng)該分區(qū)空閑嗎？分區(qū)大小xk表結(jié)束嗎？返回分區(qū)號(hào)狀態(tài)位置1無(wú)法分配取下一項(xiàng)NNNYYY固定分區(qū)分配存儲(chǔ)保護(hù)：兩種方法提供上、下界寄存器和地址檢查機(jī)構(gòu)?；芳拇嫫鳌㈤L(zhǎng)度寄存器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)。固定分區(qū)分配優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開(kāi)銷(xiāo)小。可放多道程序缺點(diǎn)：存在零頭（即存在碎片）。分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。4.3.3動(dòng)態(tài)分區(qū)分配工作原理存儲(chǔ)空間的劃分是在裝入作業(yè)時(shí)進(jìn)行的，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來(lái)決定是否分配。且使分區(qū)大小正好適應(yīng)作業(yè)的需要。數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表：序號(hào)，大小，起址，狀態(tài)空閑分區(qū)鏈：在每個(gè)分區(qū)中附上一個(gè)表格信息，狀態(tài)（0，1），大小，指針（空白分區(qū)才有）1．分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)圖空閑鏈結(jié)構(gòu)前向指針N個(gè)字節(jié)可用后向指針N+2N+20（分配標(biāo)識(shí)）00K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分區(qū)分配表：圖分區(qū)分配表0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配98K12K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K

2．分區(qū)分配算法常用的分區(qū)分配算法有以下幾種：首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法快速適應(yīng)算法4.分配算法1)首次適應(yīng)算法算法思想按分區(qū)先后次序，從頭查找，找到符合要求的第一個(gè)分區(qū)。盡可能利用存儲(chǔ)區(qū)低地址空閑區(qū)，盡量在高地址部分保存較大空閑區(qū)，以便一旦有分配大空閑區(qū)要求時(shí)，容易得到滿(mǎn)足。算法實(shí)質(zhì)1）首次適應(yīng)算法1）首次適應(yīng)算法

切割空閑區(qū)有兩種方法：從空閑區(qū)頭開(kāi)始從空閑區(qū)尾開(kāi)始空閑區(qū)大小50KB，首址156KB，申請(qǐng)34KB。從該空閑區(qū)中截取所需大小，修改調(diào)整可用表從空閑區(qū)表第一表目順序查找從可用表中移去該表目，調(diào)整可用表取下一表項(xiàng)無(wú)法分配該空閑區(qū)長(zhǎng)度≥SIZE？該空閑區(qū)長(zhǎng)度=SIZE？表目查完？返回分配起始地址否否否是是是首次適應(yīng)算法1）首次適應(yīng)算法指針10k60k90k20k有四塊空閑區(qū)(從低地址高地址)，來(lái)了一個(gè)作業(yè)需分配19k內(nèi)存。例：1）首次適應(yīng)算法指針10k60k90k20k41k在高地址空閑區(qū)中保持較大空閑區(qū)(每次從10k開(kāi)始分配尋找)。1）首次適應(yīng)算法優(yōu)點(diǎn)分配簡(jiǎn)單，合并相鄰空閑區(qū)也比較容易缺點(diǎn)查找總是從表首開(kāi)始，前面空閑區(qū)往往被分割的很小時(shí)，滿(mǎn)足分配要求的可能性較小，查找次數(shù)較多。針對(duì)這個(gè)問(wèn)題，對(duì)最先適應(yīng)法稍加改進(jìn)，就有了循環(huán)最先適應(yīng)法。2)循環(huán)首次適應(yīng)算法(nextfit)算法的分配和釋放的時(shí)間性能較好，使空閑分區(qū)分布得更均勻，但較大的空閑分區(qū)不易保留。算法思想算法特點(diǎn)按分區(qū)先后次序，從上次分配的分區(qū)起查找(到最后分區(qū)時(shí)再回到開(kāi)頭)，找到符合要求的第一個(gè)分區(qū)。12指針移動(dòng)2)循環(huán)首次適應(yīng)算法(nextfit)3)最佳適應(yīng)算法算法思想

空閑存儲(chǔ)區(qū)管理表采用從小到大的順序結(jié)構(gòu)在所有大于或者等于要求分配長(zhǎng)度的空閑區(qū)中挑選一個(gè)最小的分區(qū)，即對(duì)該分區(qū)所要求分配的大小來(lái)說(shuō)，是最合適的。分配后，所剩余的塊會(huì)最小。算法實(shí)現(xiàn)3)最佳適應(yīng)算法3)最佳適應(yīng)算法優(yōu)點(diǎn)

這種算法最大的缺點(diǎn)是分割后的空閑區(qū)將會(huì)很小，直至無(wú)法使用，而造成浪費(fèi)。缺點(diǎn)

較大的空閑分區(qū)可以被保留示例指針10k20k60k90k來(lái)一個(gè)19k的作業(yè)指針10k20k60k90k1k4)最壞適應(yīng)算法算法思想

空閑區(qū)按由大到小排序分配時(shí)選取所有空閑區(qū)中最大的一塊，把剩余的塊再變成一個(gè)新的空閑區(qū)。其依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割了一部分后可能仍是一個(gè)較大的空閑區(qū)。避免了空閑區(qū)越分越小的問(wèn)題。算法實(shí)現(xiàn)4)最壞適應(yīng)算法示例指針90k60k20k10k71k指針90k60k20k10k來(lái)一個(gè)19k的作業(yè)4)最壞適應(yīng)算法優(yōu)點(diǎn)分配時(shí)，產(chǎn)生的空白區(qū)可供以后使用。只需查找一次，就可成功，分配算法很快。缺點(diǎn)最后剩余分區(qū)會(huì)越來(lái)越小，無(wú)法運(yùn)行大程序5）快速適應(yīng)算法算法思想

對(duì)于每一類(lèi)具有相同容量的所有空閑分區(qū)，設(shè)立一個(gè)空閑分區(qū)鏈表。再設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一個(gè)空閑分區(qū)鏈表。

是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類(lèi)，在進(jìn)行內(nèi)存分配的時(shí)候，不需要對(duì)分區(qū)進(jìn)行切割。算法實(shí)現(xiàn)5）快速適應(yīng)算法該算法的優(yōu)點(diǎn)：查找效率高。不會(huì)對(duì)任何分區(qū)分割，能保留大的分區(qū)。也不會(huì)產(chǎn)生內(nèi)存碎片。該算法的缺點(diǎn)：在分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開(kāi)銷(xiāo)較大。一個(gè)分區(qū)只屬于一個(gè)進(jìn)程，存在空間浪費(fèi)。3．分區(qū)分配操作1)分配內(nèi)存設(shè)請(qǐng)求的分區(qū)大小為u.size，表中每個(gè)空閑分區(qū)的大小表示為m.size，若m.size-u.sizesize(規(guī)定的不再切割的分區(qū)大小)，將整個(gè)分區(qū)分配給請(qǐng)求者，否則從分區(qū)中按請(qǐng)求的大小劃出一塊內(nèi)存空間分配出去，余下部分留在空閑鏈中，將分配區(qū)首址返回給調(diào)用者。從頭開(kāi)始查表檢索完否？m.Size>u.size?m.size-u.size<=size?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YNNYYN

2)回收內(nèi)存當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí),可能出現(xiàn)以下四種情況之一：(1)回收區(qū)與前一個(gè)空閑分區(qū)相鄰。(2)回收分區(qū)與后一空閑分區(qū)相鄰。(3)回收區(qū)同時(shí)與前、后兩個(gè)分區(qū)鄰。(4)回收區(qū)前后都不鄰空閑區(qū)。圖內(nèi)存回收時(shí)的情況4.3.4伙伴系統(tǒng)固定分區(qū)和動(dòng)態(tài)分區(qū)方式都有不足之處。伙伴系統(tǒng)方式是對(duì)以上兩種內(nèi)存方式的一種折衷方案?；锇橄到y(tǒng)規(guī)定，無(wú)論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)，l≤k≤m，其中：21表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。當(dāng)把一個(gè)存儲(chǔ)塊分為大小相等的兩半時(shí)，則它們互為伙伴。[大小為2k的伙伴的首地址之間的關(guān)系](0)0000(8)100000000100100011002323222222222121000000104.3.4伙伴系統(tǒng)標(biāo)志位：

tag=1占用塊

0空閑塊202k2m0km0k0knodesizefirst按k值索引，相同k值的塊構(gòu)成子表(雙鏈表)4.3.4伙伴系統(tǒng)

分配算法1)計(jì)算k值：k=log2n2)從子表k開(kāi)始找可用的塊

2.1)k子表有，取出分配，結(jié)束；

2.2)否則，若從k向下找到i(i>k)子表有可用塊

(起始地址為p)，則取出2k分配，剩余的塊大小2i-12i-2......2k

起始地址p+2i-1p+2i-2......p+2k

插入相應(yīng)的子表。p2i分配2k2i-12i-2回收時(shí)，只有伙伴才合并，并將合并后的新空閑塊加入上一級(jí)大小的空閑塊鏈表中。4.3.5哈希算法哈希算法就是利用哈希快速查找的優(yōu)點(diǎn)，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表。當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過(guò)哈希函數(shù)計(jì)算，即得到在哈希表中的位置。4.3.5哈希算法算法思想

構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表。根據(jù)所需空閑分區(qū)大小，通過(guò)哈希函數(shù)計(jì)算，即得到在哈希表中的位置。利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，實(shí)現(xiàn)快速查找定位分區(qū)。算法實(shí)現(xiàn)

優(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)存容量限制分區(qū)式存儲(chǔ)管理的優(yōu)缺點(diǎn)

碎片問(wèn)題經(jīng)過(guò)一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿(mǎn)足分配要求；但其總和滿(mǎn)足分配要求。這些空閑塊被稱(chēng)為碎片造成存儲(chǔ)資源的浪費(fèi)碎片問(wèn)題解決的方法：(I)將程序裝入分散存儲(chǔ)區(qū)中–––多重分區(qū)(II)將碎片集中(緊湊或拼接)–––動(dòng)態(tài)重定位分區(qū)分配問(wèn)題：開(kāi)銷(xiāo)大；移動(dòng)時(shí)機(jī)4.3.6可重定位分區(qū)分配1．動(dòng)態(tài)重定位的引入在連續(xù)分配方式中，必須把一個(gè)系統(tǒng)或用戶(hù)程序裝入一連續(xù)的內(nèi)存空間。緊湊技術(shù)：通過(guò)在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域（緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)）如果在系統(tǒng)中只有若干個(gè)小的分區(qū)，它們?nèi)萘康目偤痛笥谝b入的程序，怎么辦？1．動(dòng)態(tài)重定位的引入緊湊2．動(dòng)態(tài)重定位的實(shí)現(xiàn)

作業(yè)裝入內(nèi)存后的所有地址都仍然是相對(duì)地址。將相對(duì)地址轉(zhuǎn)換為物理地址的工作，被推遲到程序指令要真正執(zhí)行時(shí)進(jìn)行。當(dāng)系統(tǒng)對(duì)內(nèi)存進(jìn)行了“緊湊”而使若干程序從內(nèi)存的某處移至另一處時(shí)，只要用該程序在內(nèi)存的新起始地址，去置換原來(lái)的起始地址即可。2．動(dòng)態(tài)重定位的實(shí)現(xiàn)load1,2500365load1,25003650100250050002500100001000010100+1250015000作業(yè)J處理機(jī)一側(cè)存儲(chǔ)器一側(cè)重定位寄存器相對(duì)地址3.動(dòng)態(tài)重定位分區(qū)分配算法動(dòng)態(tài)重定位分區(qū)的優(yōu)缺點(diǎn)優(yōu)點(diǎn):解決了可變分區(qū)分配所引入的“外零頭”問(wèn)題。消除內(nèi)存碎片，提高內(nèi)存利用率。缺點(diǎn):提高硬件成本，緊湊時(shí)花費(fèi)ＣＰＵ時(shí)間。1．對(duì)換(Swapping)的引入4.3.7對(duì)換對(duì)換：不能運(yùn)行的進(jìn)程調(diào)出到外存，程序、數(shù)據(jù)。具備運(yùn)行條件的進(jìn)程調(diào)入內(nèi)存，程序和數(shù)據(jù)。對(duì)換是提高內(nèi)存利用率的有效措施。1．對(duì)換實(shí)現(xiàn)：通過(guò)中級(jí)調(diào)度。分類(lèi)：進(jìn)程對(duì)換：以整個(gè)進(jìn)程為單位；頁(yè)/段對(duì)換：虛存管理技術(shù)；為了實(shí)現(xiàn)進(jìn)程對(duì)換，系統(tǒng)必須能實(shí)現(xiàn)三方面的功能：對(duì)換空間的管理、進(jìn)程的換出，以及進(jìn)程的換入。對(duì)2、對(duì)換空間管理外存：是提高進(jìn)程換入和換出的速度。為此，采取的是連續(xù)分配方式。分為文件區(qū)和對(duì)換區(qū)。對(duì)對(duì)換空間管理的主要目標(biāo)：3．進(jìn)程的換出與換入(1)進(jìn)程的換出系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將之換入。每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無(wú)足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。(2)進(jìn)程的換入3．進(jìn)程的換出與換入(1)進(jìn)程的換出(2)進(jìn)程的換入4.4基本分頁(yè)存儲(chǔ)管理方式造成這樣問(wèn)題的主要原因是用戶(hù)程序裝入內(nèi)存時(shí)是整體裝入的，為解決這個(gè)問(wèn)題，提出了分頁(yè)存儲(chǔ)管理技術(shù)。分區(qū)存儲(chǔ)管理的主要問(wèn)題是碎片問(wèn)題。4.4.1頁(yè)面與頁(yè)表--頁(yè)面1)頁(yè)面和物理塊在分頁(yè)系統(tǒng)中的頁(yè)面其大小應(yīng)適中。頁(yè)面大小應(yīng)是2的冪，通常為512B～8KB。頁(yè)框(塊f)：把主存空間劃分成與頁(yè)相同的片。

頁(yè)面(頁(yè)P(yáng))：把每個(gè)作業(yè)(進(jìn)程)虛擬(邏輯)地址空間劃分成若干大小相等的片.2)頁(yè)面大小2．地址結(jié)構(gòu)用戶(hù)程序中的邏輯地址包括頁(yè)號(hào)和頁(yè)內(nèi)地址（頁(yè)內(nèi)位移）

區(qū)分頁(yè)號(hào)和頁(yè)內(nèi)地址的依椐是頁(yè)的大小，頁(yè)內(nèi)地址占邏輯地址的低位部分，頁(yè)號(hào)占邏輯地址的高位部分。分頁(yè)地址中的地址結(jié)構(gòu)如下：2．地址結(jié)構(gòu)分頁(yè)地址中的地址結(jié)構(gòu)確定了主存儲(chǔ)器的分頁(yè)大小,也決定了頁(yè)面大小.

頁(yè)號(hào)P頁(yè)內(nèi)地址(偏移量)31 1211 0若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面大小為L(zhǎng)，則頁(yè)號(hào)P和頁(yè)內(nèi)地址d可按下式求得：

P=INT[A/L]d=[A]MODL例如：假定頁(yè)面大小1024字節(jié)，虛地址共占用2個(gè)字節(jié)(16位)

頁(yè)號(hào)頁(yè)內(nèi)地址（位移量）

PW1510902．地址結(jié)構(gòu)2．地址結(jié)構(gòu)3．頁(yè)表頁(yè)號(hào)塊號(hào)021326為了能在內(nèi)存中找到每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立了一張頁(yè)面映象表，即頁(yè)表頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射頁(yè)表由頁(yè)號(hào)和塊號(hào)組成，指出邏輯地址中頁(yè)號(hào)與主存中物理塊號(hào)的對(duì)應(yīng)關(guān)系3.頁(yè)表0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)n頁(yè)021326384950123456789用戶(hù)程序頁(yè)表頁(yè)號(hào)塊號(hào)內(nèi)存頁(yè)表位于內(nèi)存4.4.2地址變換機(jī)構(gòu)通過(guò)硬件的地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換工作。地址轉(zhuǎn)換機(jī)構(gòu)的任務(wù)實(shí)際上是將邏輯地址中的頁(yè)號(hào)轉(zhuǎn)換成為主存中的物理塊號(hào)。頁(yè)表是硬件地址轉(zhuǎn)換的依據(jù)。頁(yè)式存儲(chǔ)管理采用動(dòng)態(tài)重定位方式裝入方式。物理地址=塊號(hào)*塊長(zhǎng)+頁(yè)內(nèi)地址1．基本的地址變換機(jī)構(gòu)頁(yè)表始址頁(yè)表長(zhǎng)度＋頁(yè)號(hào)(3)頁(yè)內(nèi)地址頁(yè)表寄存器邏輯地址>越界中斷1b塊號(hào)頁(yè)表頁(yè)號(hào)0123物理地址頁(yè)號(hào)

塊號(hào)

存取控制頁(yè)描述符+如果頁(yè)號(hào)>頁(yè)表長(zhǎng)度，則中斷，否則繼續(xù).如果訪(fǎng)問(wèn)非法，則中斷，否則繼續(xù)。頁(yè)號(hào)位移量虛擬地址

LA

塊號(hào)位移量物理地址頁(yè)表始址長(zhǎng)度頁(yè)表寄存器PTR頁(yè)表

塊號(hào)存取控制頁(yè)表項(xiàng)頁(yè)號(hào)

01

...塊號(hào)位移量

1．基本的地址變換機(jī)構(gòu)有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。虛地址3412P＝3412％2048＝1d＝3412mod2048

＝1364MR=9*2048+1364=19796虛地址3412的內(nèi)存地址是：19796虛地址7145P＝7145％2048＝3d＝7145mod2048

＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：112412．具有快表的地址變換機(jī)構(gòu)執(zhí)行一次訪(fǎng)內(nèi)操作至少要訪(fǎng)問(wèn)主存兩次。增加一個(gè)具有并行查詢(xún)功能的高速緩沖存儲(chǔ)器，存放在高速緩沖存儲(chǔ)器中的頁(yè)表叫快表，他是用來(lái)存放當(dāng)前訪(fǎng)問(wèn)最頻繁的少數(shù)活動(dòng)頁(yè)面的頁(yè)表項(xiàng)。解決方法第一次訪(fǎng)頁(yè)表第二次是根據(jù)地址取數(shù)據(jù)或指令。具有快表的地址變換機(jī)構(gòu)頁(yè)表始址頁(yè)表長(zhǎng)度＋頁(yè)號(hào)頁(yè)內(nèi)地址頁(yè)表寄存器邏輯地址>越界中斷1b塊號(hào)頁(yè)表頁(yè)號(hào)bd物理地址輸入寄存器b頁(yè)號(hào)塊號(hào)快表現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232～264)。頁(yè)表就變得非常大。4.4.3兩級(jí)和多級(jí)頁(yè)表(2)只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)仍駐留在磁盤(pán)上，需要時(shí)再調(diào)入。解決方法：(1)采用離散分配方式來(lái)解決難以找到一塊連續(xù)的大內(nèi)存空間的問(wèn)題；將頁(yè)表進(jìn)行分頁(yè)，并離散地將各個(gè)頁(yè)面分別存放在不同的物理塊中，同樣也要為離散分配的頁(yè)表再建立一張頁(yè)表，稱(chēng)為外層頁(yè)表。1．兩級(jí)頁(yè)表兩級(jí)頁(yè)表外層頁(yè)號(hào) 外層頁(yè)內(nèi)地址 頁(yè)內(nèi)地址31222112110外層頁(yè)表頁(yè)表1．兩級(jí)頁(yè)表………012345671141151468內(nèi)存空間…641第0頁(yè)頁(yè)表012…1023115114第1頁(yè)頁(yè)表012…10231468第n頁(yè)頁(yè)表012…1023174210781011012n外部頁(yè)表兩級(jí)分頁(yè)結(jié)構(gòu)1．兩級(jí)頁(yè)表外部頁(yè)表寄存器外部頁(yè)表頁(yè)表db物理地址++dP2P1邏輯地址外部頁(yè)號(hào)外部頁(yè)內(nèi)地址頁(yè)內(nèi)地址具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)：二級(jí)頁(yè)表地址變換需三次訪(fǎng)問(wèn)主存兩級(jí)頁(yè)表對(duì)32位機(jī)器適用，64位呢？ 頁(yè)面大小為4KB即212B，還剩52位，按物理塊大小212位來(lái)劃分頁(yè)表，則剩余40位用于外層頁(yè)號(hào)，此時(shí)外層頁(yè)表可能有1024G個(gè)頁(yè)表項(xiàng)，要占用4096GB的連續(xù)存儲(chǔ)空間

2．多級(jí)頁(yè)表解決方法：采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)行分頁(yè)。

例:在一個(gè)分頁(yè)式存儲(chǔ)管理系統(tǒng)中,某作業(yè)的頁(yè)表如下所示。已知頁(yè)面大小為1024B,試將邏輯地址1011,2148,3000,4000,5012轉(zhuǎn)化為相應(yīng)的物理地址.頁(yè)號(hào)塊號(hào)021321364.5基本分段存儲(chǔ)管理方式在分頁(yè)存儲(chǔ)系統(tǒng)中，作業(yè)的地址空間是一維線(xiàn)性的，這破壞了程序內(nèi)部天然的邏輯結(jié)構(gòu),造成共享、保護(hù)的困難。一個(gè)用戶(hù)程序往往由幾個(gè)程序段（主程序、子程序和函數(shù)）所組成，當(dāng)一個(gè)程序裝入內(nèi)存時(shí)，按段進(jìn)行分配，每個(gè)段的大小是不相等的。4.5.1分段式存儲(chǔ)管理的引入引入分段存儲(chǔ)管理方式，主要是為了滿(mǎn)足用戶(hù)和程序員的下述需要：

1)方便編程

2)信息共享

3)信息保護(hù)

4)動(dòng)態(tài)增長(zhǎng)

5)動(dòng)態(tài)鏈接...0S工作區(qū)段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N數(shù)組[A]12345...4.5.2分段系統(tǒng)的基本原理

1.分段

每個(gè)段定義了一組邏輯信息，主程序段，子程序段，數(shù)據(jù)段等兩維邏輯地址：段號(hào)＋段內(nèi)地址分段地址中的地址具有如下結(jié)構(gòu)：段號(hào)段內(nèi)地址31161502.段表為了實(shí)現(xiàn)段的邏輯地址到物理地址的轉(zhuǎn)換，系統(tǒng)為每個(gè)進(jìn)程設(shè)置了一張段表；它記錄了段號(hào)，段的首（地）址和長(zhǎng)度之間的關(guān)系。段號(hào)012段首址段長(zhǎng)度58K20K100K110K260K140K2.段表作業(yè)空間（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k段長(zhǎng)基址30k40k20k80k15k120k10k150k段號(hào)0123內(nèi)存空間040K80K120K150K3.地址變換機(jī)構(gòu)從邏輯地址到物理地址的轉(zhuǎn)換工作過(guò)程：將邏輯地址中的段號(hào)與段表長(zhǎng)度進(jìn)行比較，若超過(guò)了段表長(zhǎng)度則產(chǎn)生越界中斷；根據(jù)段號(hào)和段表始址計(jì)算出該段在段表中的位置。檢查段內(nèi)位移是否超過(guò)該段的段長(zhǎng)；將該段在內(nèi)存中的起始地址與邏輯地址的段內(nèi)位移相加即得到要訪(fǎng)問(wèn)的物理地址。段表長(zhǎng)度段表始址控制寄存器物理地址<+越界中斷分段系統(tǒng)的地址變換機(jī)構(gòu)1002段號(hào)S位移量W段表92002008K5004K6006K1K段長(zhǎng)基址段號(hào)0123+82928K82928692主存段號(hào)內(nèi)存起始地址段長(zhǎng)02105002100904193895段號(hào)段內(nèi)位移043025004112532例：在一個(gè)段式存儲(chǔ)管理系統(tǒng)中，其段表如表所示。

邏輯地址

段表試求表所示中的邏輯地址所對(duì)應(yīng)的物理地址？4.分頁(yè)和分段的主要區(qū)別(1)頁(yè)是信息的物理單位，段則是信息的邏輯單位(2)頁(yè)的大小固定且由系統(tǒng)決定，而段的長(zhǎng)度卻不固定(3)分頁(yè)的作業(yè)地址空間是一維的，即單一的線(xiàn)性地址空間，分段的作業(yè)地址空間則是二維的4.5.3信息共享分段易于實(shí)現(xiàn)段的共享，即允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段。段的共享，是通過(guò)不同段表中的段表項(xiàng)指向同一個(gè)段基址來(lái)實(shí)現(xiàn)。對(duì)共享段的信息必須進(jìn)行保護(hù)分頁(yè)系統(tǒng)中雖然也能實(shí)現(xiàn)程序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)方便。圖分頁(yè)系統(tǒng)中共享editor的示意圖data10…data1ed40…ed2ed1進(jìn)程1data10…data1ed40…ed2ed1進(jìn)程270…6160…2221頁(yè)表80…7160…2221頁(yè)表data10…data1data10…data1ed40…ed2ed1…021226061707180主存圖分段系統(tǒng)中共享editor的示意圖data1editor進(jìn)程1data2editor進(jìn)程22404080160基址段長(zhǎng)段表3804080160基址段長(zhǎng)段表data2…data1editor80240280380420主存可重入代碼可重入代碼又稱(chēng)為“純代碼”，是一種允許多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)的代碼。為使各個(gè)進(jìn)程所執(zhí)行的代碼完全相同，絕對(duì)不允許可重入代碼在執(zhí)行中有任何改變。在每個(gè)進(jìn)程中，都必須配以局部數(shù)據(jù)區(qū)，把在執(zhí)行中可能改變的部分拷貝到該數(shù)據(jù)區(qū)，這時(shí)的可共享代碼即成為可重入碼。

分段管理的優(yōu)缺點(diǎn)優(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)？4.5.4段頁(yè)式存儲(chǔ)管理分頁(yè)優(yōu)點(diǎn)：提高內(nèi)存利用率分段優(yōu)點(diǎn)：滿(mǎn)足用戶(hù)需要。因此可以將兩者結(jié)合成一種新的存儲(chǔ)管理方式系統(tǒng)稱(chēng)為“段頁(yè)式系統(tǒng)”。結(jié)合了段式與頁(yè)式二者優(yōu)點(diǎn)克服了二者的缺點(diǎn)

1．基本原理作業(yè)仍按邏輯分段，但對(duì)每一段不是按單一的連續(xù)整體存放到存儲(chǔ)器中，而是把每個(gè)段再分成若干個(gè)頁(yè)面，每一段不必占據(jù)連續(xù)的主存空間，可把它按頁(yè)存放在不連續(xù)的主存塊中。04K8K12K15K16K主程序段04K8K子程序段04K8K12K10K數(shù)據(jù)段1．基本原理

內(nèi)存劃分：按頁(yè)式存儲(chǔ)管理方案內(nèi)存分配：以頁(yè)為單位進(jìn)行分配地址結(jié)構(gòu)：頁(yè)內(nèi)地址(W)段內(nèi)頁(yè)號(hào)(P)段號(hào)(S)1．基本原理段頁(yè)式存儲(chǔ)管理為每一個(gè)裝入主存的作業(yè)建立一張段表,每個(gè)段又被分成若干個(gè)固定大小的頁(yè)面，那么每個(gè)段又必須建立一張頁(yè)表把段中的虛頁(yè)變換成內(nèi)存中的實(shí)際頁(yè)面。每個(gè)段有一個(gè)頁(yè)表，段表中應(yīng)有專(zhuān)項(xiàng)指出該段所對(duì)應(yīng)頁(yè)表的頁(yè)表始址和頁(yè)表長(zhǎng)度。段號(hào)狀態(tài)頁(yè)表長(zhǎng)度頁(yè)表始址01510

212段表大小段表始址段表控制寄存器頁(yè)號(hào)狀態(tài)塊號(hào)011211192121304115段表、頁(yè)表與內(nèi)存關(guān)系內(nèi)存空間頁(yè)表頁(yè)表段表頁(yè)號(hào)狀態(tài)塊號(hào)012911302．地址變換過(guò)程地址變換過(guò)程Q：為了獲得一條指令或者數(shù)據(jù)，需要訪(fǎng)問(wèn)內(nèi)存幾次？段頁(yè)式存儲(chǔ)管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：連續(xù)空間分配與不連續(xù)空間分配方式都屬于實(shí)存管理技術(shù)。不存在外碎片、段可動(dòng)態(tài)增長(zhǎng)、便于共享和控制存取訪(fǎng)問(wèn)。硬件成本增加、軟件復(fù)雜性和管理開(kāi)銷(xiāo)增加、存在內(nèi)碎片。缺點(diǎn)：4.6虛擬存儲(chǔ)器的基本概念前面的各種存儲(chǔ)器管理方式有一個(gè)共同的特點(diǎn)，即它們都要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行：(1)有的作業(yè)很大，其所要求的內(nèi)存空間超過(guò)了內(nèi)存總?cè)萘俊?2)有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)。1．常規(guī)存儲(chǔ)器管理方式的特征

駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。一次性。要求將作業(yè)全部裝入內(nèi)存后方能運(yùn)行，即作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存。2．局部性原理局部性原理：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪(fǎng)問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。具體地表現(xiàn)為：時(shí)間局部性和空間局部性2．局部性原理①時(shí)間的局限性，如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；某個(gè)數(shù)據(jù)被訪(fǎng)問(wèn)，則不久以后該數(shù)據(jù)可能被再次訪(fǎng)問(wèn)。②空間的局限性，一旦程序訪(fǎng)問(wèn)了某個(gè)存儲(chǔ)單元，在不久以后，其附近的存儲(chǔ)單元也被訪(fǎng)問(wèn)，即程序在一段時(shí)間內(nèi)所訪(fǎng)問(wèn)的地址可能集中在一定的范圍內(nèi)。3．虛擬存儲(chǔ)器的定義具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)，其邏輯容量由內(nèi)存和外存容量之和決定，其運(yùn)行速度接近于內(nèi)存的速度，而成本接近于外存。虛擬存儲(chǔ)器：虛擬存儲(chǔ)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)3．虛擬存儲(chǔ)器的定義

實(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)存利用率。4.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1．分頁(yè)請(qǐng)求系統(tǒng)這是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。1)硬件支持①請(qǐng)求分頁(yè)的頁(yè)表機(jī)制；②缺頁(yè)中斷機(jī)構(gòu)；③地址變換機(jī)構(gòu)。2)實(shí)現(xiàn)請(qǐng)求分頁(yè)的軟件4.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法2．請(qǐng)求分段系統(tǒng)這是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后所形成的段式虛擬存儲(chǔ)系統(tǒng)。系統(tǒng)同樣需要必要的硬件支持：(1)請(qǐng)求分段的段表機(jī)制。(2)缺段中斷機(jī)構(gòu)。(3)地址變換機(jī)構(gòu)。4.6.3虛擬存儲(chǔ)器的特征多次性：一個(gè)作業(yè)分成多次調(diào)入主存運(yùn)行；對(duì)換性：每個(gè)作業(yè)不是全部一次性地裝入內(nèi)存，將當(dāng)前不運(yùn)行的程序、數(shù)據(jù)調(diào)至外存盤(pán)交換區(qū)；虛擬性：虛存是從邏輯上擴(kuò)充內(nèi)存容量，使用戶(hù)編程所用到的地址空間遠(yuǎn)大于實(shí)際內(nèi)存容量。4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式基本思想作業(yè)運(yùn)行的過(guò)程中，頁(yè)面只有需要時(shí)才請(qǐng)求被換入內(nèi)存，而暫不運(yùn)行的頁(yè)面置換到外存，從而減少對(duì)換時(shí)間和所需內(nèi)存數(shù)量，增加多道程序的道數(shù)。換入和換出是以頁(yè)面為基本單位。

需要解決的問(wèn)題系統(tǒng)需要解決下面三個(gè)問(wèn)題：系統(tǒng)如何獲知進(jìn)程當(dāng)前所需頁(yè)面不在主存。當(dāng)發(fā)現(xiàn)缺頁(yè)時(shí)，如何把所缺頁(yè)面調(diào)入主存。當(dāng)主存中沒(méi)有空閑的頁(yè)框時(shí)，為了要接受一個(gè)新頁(yè)，需要把老的一頁(yè)淘汰出去，根據(jù)什么策略選擇欲淘汰的頁(yè)面。4.7.1請(qǐng)求分頁(yè)中的硬件支持1.頁(yè)表機(jī)制頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪(fǎng)問(wèn)字段A修改位M外存地址指示該頁(yè)是否已調(diào)入內(nèi)存記錄本頁(yè)在一段時(shí)間內(nèi)被訪(fǎng)問(wèn)的次數(shù)，或記錄本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)，供選擇換出頁(yè)面時(shí)參考該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)，供置換頁(yè)面時(shí)參考指出該頁(yè)在外存上的地址，供調(diào)入該頁(yè)時(shí)參考查頁(yè)表時(shí)，當(dāng)該頁(yè)不在主存時(shí)，則引起一個(gè)缺頁(yè)中斷,它與一般的中斷相比，主要區(qū)別表現(xiàn)在：

1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)；

2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷(為什么？)B:A:指令TOBCopyA頁(yè)面6543212.缺頁(yè)中斷機(jī)構(gòu)

3．地址變換機(jī)構(gòu)1、存儲(chǔ)保護(hù)檢查：頁(yè)號(hào)>頁(yè)表長(zhǎng)度？是，越界中斷；否則2；2、查快表：找到，修改訪(fǎng)問(wèn)位，對(duì)于寫(xiě)操作置修改位，并形成物理地址訪(fǎng)問(wèn)；若未找到，轉(zhuǎn)3；3、查頁(yè)表狀態(tài)位：在主存，將表目寫(xiě)入快表；否則，缺頁(yè)中斷。地址變換過(guò)程請(qǐng)求訪(fǎng)問(wèn)一頁(yè)頁(yè)號(hào)頁(yè)表長(zhǎng)越界中斷表項(xiàng)在快表中CPU檢索快表訪(fǎng)問(wèn)頁(yè)表頁(yè)在內(nèi)存YNYNY修改快表修改訪(fǎng)問(wèn)位和修改位形成物理地址N缺頁(yè)中斷地址變換過(guò)程缺頁(yè)中斷處理外存中找到所需頁(yè)面有空頁(yè)框嗎N選擇淘汰的頁(yè)面更新頁(yè)表、快表Y該頁(yè)修改過(guò)Y把該頁(yè)寫(xiě)回外存N保留CPU現(xiàn)場(chǎng)裝入新頁(yè)按邏輯地址查快表該頁(yè)在快表中有登記?形成物理地址繼續(xù)執(zhí)行指令是發(fā)缺頁(yè)中斷查頁(yè)表否該頁(yè)在主存中形成物理地址將該頁(yè)登記入快表是保護(hù)現(xiàn)場(chǎng)主存有空閑塊?裝入所需要的頁(yè)調(diào)整頁(yè)表和主存分配表恢復(fù)現(xiàn)場(chǎng)重啟被中斷的指令是選擇調(diào)出的頁(yè)該頁(yè)被修改?將該頁(yè)寫(xiě)回輔存相應(yīng)位置否否是缺頁(yè)中斷處理流程硬件處理操作系統(tǒng)處理4.7.2內(nèi)存分配策略和分配算法虛存請(qǐng)求分頁(yè)管理在為進(jìn)程分配內(nèi)存時(shí)，必須考慮三個(gè)問(wèn)題：第一，確定保證進(jìn)程正常運(yùn)行所需要的最小的物理塊數(shù)；第二，物理塊的分配策略；

第三，確定采用何種分配算法來(lái)進(jìn)行頁(yè)面分配1．最小物理塊數(shù)的確定保證進(jìn)程正常運(yùn)行所需最小的物理塊數(shù)，與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，其值取決于指令的格式、功能和尋址方式。采用直接尋址：最小物理塊數(shù)為2；（存放指令的頁(yè)和存放數(shù)據(jù)的頁(yè)）采用間接尋址：最小物理塊數(shù)為3；

2．物理塊的分配策略1)固定分配局部置換

2)可變分配全局置換3)可變分配局部置換根據(jù)進(jìn)程的類(lèi)型，為每個(gè)進(jìn)程分配固定數(shù)目的內(nèi)存頁(yè)框，整個(gè)運(yùn)行期間不再改變。這種策略的難點(diǎn)在于，為每個(gè)進(jìn)程分配的頁(yè)框數(shù)N難以確定。操作系統(tǒng)自身保持一個(gè)空閑物理塊隊(duì)列；當(dāng)某進(jìn)程發(fā)生缺頁(yè)中斷時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中取出一塊分配給該進(jìn)程；但當(dāng)進(jìn)程缺頁(yè)時(shí)，只允許從該進(jìn)程的頁(yè)面中選出一頁(yè)換出。若進(jìn)程缺頁(yè)中斷頻繁，則系統(tǒng)須為該進(jìn)程追加分配若干物理塊。3．物理塊分配算法平均分配算法按比例分配算法n個(gè)進(jìn)程,進(jìn)程的頁(yè)面數(shù)為Si,物理塊總數(shù)為m,每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi

3)考慮優(yōu)先權(quán)的分配算法一部分按比例地分配；另一部分則根據(jù)優(yōu)先權(quán)4.7.3調(diào)頁(yè)策略1．調(diào)入頁(yè)面的時(shí)機(jī)（2）預(yù)調(diào)(prepaging)將要訪(fǎng)問(wèn)時(shí)調(diào)入(根據(jù)程序順序行為，不一定準(zhǔn)）（根據(jù)空間局部性，目前：成功率≤50％）

（1）請(qǐng)調(diào)(demandpaging)發(fā)生缺頁(yè)中斷時(shí)調(diào)入（較費(fèi)系統(tǒng)開(kāi)銷(xiāo)）

預(yù)調(diào)必須輔以請(qǐng)調(diào)。

2．確定從何處調(diào)入頁(yè)面外存：文件區(qū)、對(duì)換區(qū)從何處將缺頁(yè)調(diào)入內(nèi)存，分成三種情況：系統(tǒng)擁有足夠的對(duì)換區(qū)空間：系統(tǒng)缺少足夠的對(duì)換區(qū)空間：UNIX方式：若系統(tǒng)擁有足夠的對(duì)換區(qū)空間，則可全部從對(duì)換區(qū)調(diào)入所需頁(yè)面如果系統(tǒng)缺少足夠的對(duì)換區(qū)空間，對(duì)于不被修改的文件，則直接從文件區(qū)調(diào)入；對(duì)于可能被修改的文件，則從交換區(qū)調(diào)入；UNIX系統(tǒng)中，凡未運(yùn)行過(guò)的頁(yè)面都從文件區(qū)調(diào)入；對(duì)曾經(jīng)運(yùn)行過(guò)而又被換出的頁(yè)面，則從交換區(qū)調(diào)入3．頁(yè)面調(diào)入過(guò)程★缺頁(yè)中斷★保留CPU環(huán)境★缺頁(yè)中斷處理★訪(fǎng)問(wèn)內(nèi)存數(shù)據(jù)整個(gè)頁(yè)面的調(diào)入過(guò)程對(duì)用戶(hù)是透明的。邏輯地址空間物理地址空間3．頁(yè)面調(diào)入過(guò)程工作原理012345678...…012CPUOS缺頁(yè)中斷缺頁(yè)中斷處理子程序3頁(yè)表4.8頁(yè)面置換算法當(dāng)出現(xiàn)要訪(fǎng)問(wèn)的頁(yè)面不在內(nèi)存，內(nèi)存空間又不足的情況下，系統(tǒng)需淘汰一頁(yè)。用來(lái)選取淘汰哪一頁(yè)的規(guī)則，叫置換算法。最佳置換算法先進(jìn)先出置換算法最近最久未用置換算法Clock置換算法

4.8.1最佳置換算法和先進(jìn)先出置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法?；舅枷耄?.最佳置換算法選擇從當(dāng)前時(shí)刻開(kāi)始以后不在使用的頁(yè)面淘汰，如果沒(méi)有這類(lèi)頁(yè)，則選擇最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪(fǎng)問(wèn)的頁(yè)面淘汰。1.最佳置換算法例：一個(gè)有5個(gè)頁(yè)面的進(jìn)程，在內(nèi)存為它分配3個(gè)物理塊，其頁(yè)面訪(fǎng)問(wèn)順序如下：2，3，2，1，5，2，4，5，3，2，5，2進(jìn)程運(yùn)行時(shí)，會(huì)依次將2，3，1三個(gè)頁(yè)面裝入內(nèi)存。以后，當(dāng)進(jìn)程要訪(fǎng)問(wèn)頁(yè)面5時(shí)，將會(huì)產(chǎn)生缺頁(yè)中斷。此時(shí)OS根據(jù)最佳置換算法，將選擇頁(yè)面予以淘汰。232152453252223231235435235OTP算法：缺頁(yè)次數(shù)=6232354354352352351.最佳置換算法％％＝缺頁(yè)率為＝50100126×優(yōu)點(diǎn)：使得頁(yè)面調(diào)入調(diào)出的次數(shù)達(dá)到最小，這是一種理想情況。缺點(diǎn)：實(shí)際上無(wú)法實(shí)現(xiàn)，因?yàn)橄到y(tǒng)無(wú)法預(yù)知未來(lái)頁(yè)面的訪(fǎng)問(wèn)情況。因此只能用作理論上性能評(píng)價(jià)的標(biāo)準(zhǔn)。1.最佳置換算法2．先進(jìn)先出(FIFO)頁(yè)面置換算法思想：選擇最早調(diào)入內(nèi)存的頁(yè)面淘汰。出發(fā)點(diǎn)：近期調(diào)入的頁(yè)面被再次訪(fǎng)問(wèn)的概率要大于早期調(diào)入的頁(yè)面。問(wèn)題：事實(shí)上并非所有的時(shí)候都這樣。此時(shí)FIFO算法的性能較差。這里，我們?nèi)杂蒙厦娴睦?，但采用FIFO算法進(jìn)行頁(yè)面置換232152453252FIFO算法：缺頁(yè)次數(shù)=9223232315315215245243243243543522．先進(jìn)先出(FIFO)頁(yè)面置換算法％％＝缺頁(yè)率為＝75100129×

采用FIFO算法還會(huì)產(chǎn)生一種奇怪現(xiàn)象。在某些情況下，當(dāng)分配的物理塊數(shù)增多反而導(dǎo)致更多的缺頁(yè)中斷，這種現(xiàn)象稱(chēng)為FIFO異?，F(xiàn)象或稱(chēng)Belady現(xiàn)象。（根本原因就是沒(méi)有考慮程序執(zhí)行的動(dòng)態(tài)特征）某進(jìn)程共有5頁(yè),依次訪(fǎng)問(wèn)頁(yè)面的序列為：1，2，3，4，1，2，5，1，2，3，4，5；當(dāng)系統(tǒng)為該進(jìn)程分配的物理塊數(shù)為3和4時(shí)，它們的缺頁(yè)情況如下表。2．先進(jìn)先出(FIFO)頁(yè)面置換算法123412555344123412225331234111255123444512345123334512341222345123111234512123412512345+++++++++++++++++++4.8.2最近最久未使用置換算法基本思想：每次選擇內(nèi)存中離當(dāng)前時(shí)刻最久未使用過(guò)的頁(yè)面淘汰。理由：如果某頁(yè)被訪(fǎng)問(wèn)了，則它可能馬上還要被訪(fǎng)問(wèn)，反之如果該頁(yè)很長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)，則它在最近一段時(shí)間內(nèi)也不會(huì)被訪(fǎng)問(wèn)。根據(jù)：局部性原理。232152453252223231251254352LRU算法：缺頁(yè)次數(shù)=7354232512543523524.8.2最近最久未使用置換算法％％＝缺頁(yè)率為＝58.3100127×2．LRU置換算法的硬件支持LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。寄存器棧每個(gè)頁(yè)面設(shè)立移位寄存器,進(jìn)程訪(fǎng)問(wèn)某物理塊時(shí),要將相應(yīng)寄存器的最高位置成1。每隔一定時(shí)間將寄存器右移一位。用棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)，當(dāng)進(jìn)程訪(fǎng)問(wèn)某頁(yè)面時(shí)，將該頁(yè)面的頁(yè)面號(hào)從棧中移出，壓入棧頂。某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪(fǎng)問(wèn)情況1)寄存器

R0R1R2R3R4R5R6R7R實(shí)頁(yè)0001011110011110011010110101010110001000010101011001100101001000123456782)棧假定現(xiàn)有一進(jìn)程所訪(fǎng)問(wèn)的頁(yè)面的頁(yè)面號(hào)序列為：44747040740714710470147012470214701270126470710121263012634.8.3

Clock置換算法要實(shí)現(xiàn)LRU算法，需要付出很大的系統(tǒng)開(kāi)銷(xiāo)。1．簡(jiǎn)單的Clock置換算法Clock算法只要在頁(yè)表中設(shè)一個(gè)“引用位”，當(dāng)頁(yè)表中的某一頁(yè)被訪(fǎng)問(wèn)時(shí)，該位由硬件自動(dòng)置1，并由頁(yè)面管理軟件周期性把所有引用位置0。當(dāng)需要置換一頁(yè)面時(shí)，選擇其引用位為0的頁(yè)1．簡(jiǎn)單的Clock置換算法

簡(jiǎn)單Clock置換算法的流程和示例入口查尋指針前進(jìn)一步，指向下一個(gè)表目頁(yè)面訪(fǎng)問(wèn)位=0?選擇該頁(yè)面淘汰是返回置頁(yè)面訪(fǎng)問(wèn)位＝“0”否塊號(hào)頁(yè)號(hào)訪(fǎng)問(wèn)位指針0124034215650711替換指針Page9use=1Page19Use=1Page1Use=1Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page222Use=0Page33Use=1下一個(gè)幀指針n-1012345678一個(gè)頁(yè)替換前的緩沖區(qū)狀態(tài)第1頁(yè)框...下一頁(yè)替換后的緩沖區(qū)狀態(tài)Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page556Use=1Page13Use=0Page67Use=1Page222Use=0Page33Use=1.n012345678..2321524532522*Clock算法：缺頁(yè)次數(shù)=82*3*2*3*2*3*1*5*2*15*2*4*5*2*4*3*243*2*43*2*5*3*2*5*1*3*2

1*3

2

1

3

2

1

3

5*1．簡(jiǎn)單的Clock置換算法在改進(jìn)型Clock算法中首選置換頁(yè)面：既是未使用過(guò)的頁(yè)面；又是未修改的頁(yè)面由訪(fǎng)問(wèn)位A和修改位M可以組合成四種類(lèi)型的頁(yè)面：(1)最近沒(méi)有被引用,沒(méi)有被修改(A=0,M=0)(2)最近沒(méi)有被引用,但被修改(A=0,M=1)(3)最近被引用,沒(méi)有被修改(A=1,M=0)(4)最近被引用過(guò),也被修改過(guò)(A=1,M=1)2．改進(jìn)型Clock置換算法置換步驟：步3：如果步2失敗，再轉(zhuǎn)向步1操作。2．改進(jìn)型Clock置換算法步1：從指針當(dāng)前位置開(kāi)始,掃描循環(huán)隊(duì)列。把找到的第一個(gè)A=0,M=0的頁(yè)面作為淘汰頁(yè)面，未找到，轉(zhuǎn)步2。步2：查找A=0且M=1的頁(yè)面，把找到的第一個(gè)這樣的頁(yè)面作為淘汰頁(yè)面，所有經(jīng)過(guò)的頁(yè)面的訪(fǎng)問(wèn)位A置0。4.8.4其它置換算法1、最少使用置換算法把到當(dāng)前為止被訪(fǎng)問(wèn)次數(shù)最少的頁(yè)面淘汰。每頁(yè)設(shè)置訪(fǎng)問(wèn)計(jì)數(shù)器，每當(dāng)頁(yè)面被訪(fǎng)問(wèn)時(shí)，該頁(yè)面的訪(fǎng)問(wèn)計(jì)數(shù)器加1；發(fā)生缺頁(yè)中斷時(shí)，淘汰計(jì)數(shù)值最小的頁(yè)面，并將所有計(jì)數(shù)清零；2．頁(yè)面緩沖算法它是對(duì)FIFO算法的發(fā)展，通過(guò)被置換頁(yè)面的緩沖，有機(jī)會(huì)找回剛被置換的頁(yè)面；設(shè)置兩個(gè)鏈表，空閑鏈表和已修改頁(yè)面鏈表。用FIFO選擇被置換頁(yè)如果被置換頁(yè)沒(méi)有發(fā)生修改，將它直接放入空閑鏈表否則放入到已修改頁(yè)面的鏈表中。2．頁(yè)面緩沖算法需要調(diào)入新的物理頁(yè)面時(shí)，將新頁(yè)面內(nèi)容讀入到空閑頁(yè)面鏈表的第一項(xiàng)所指的頁(yè)面?？臻e頁(yè)面和已修改頁(yè)面，仍停留在內(nèi)存中一段時(shí)間，如果這些頁(yè)面被再次訪(fǎng)問(wèn)，只需較小開(kāi)銷(xiāo)。當(dāng)已修改頁(yè)面達(dá)到一定數(shù)目后，再將它們一起調(diào)出到外存，然后將它們歸入空閑頁(yè)面鏈表。頁(yè)面置換算法比較0510152025354030068101214FIFOCLOCK

LRUOPT分配的頁(yè)數(shù)每千次訪(fǎng)問(wèn)的缺頁(yè)中斷數(shù)影響缺頁(yè)次數(shù)的因素(1)分配給進(jìn)程的物理頁(yè)面數(shù)(2)頁(yè)面本身的大小(3)程序的編制方法(4)頁(yè)面淘汰算法性能問(wèn)題顛簸（抖動(dòng)）:頁(yè)面淘汰算法不合理分配給進(jìn)程的物理頁(yè)面數(shù)太少

在虛存中，頁(yè)面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱(chēng)為顛簸或抖動(dòng)原因：

工作集（WorkingSet）模型對(duì)一個(gè)作業(yè)來(lái)說(shuō)，當(dāng)分配給它的頁(yè)面數(shù)目小于某一個(gè)數(shù)值時(shí)，其缺頁(yè)中斷次數(shù)急劇增加，甚至出現(xiàn)頁(yè)面抖動(dòng)現(xiàn)象；而高于這個(gè)頁(yè)面數(shù)時(shí)，缺頁(yè)中斷次數(shù)不會(huì)明顯減少。此時(shí)我們稱(chēng)這個(gè)頁(yè)面數(shù)范圍為頁(yè)面的“工作集”。影響工作集的因素作業(yè)的特征（結(jié)構(gòu)、大小、訪(fǎng)問(wèn)數(shù)據(jù)的規(guī)律等）作業(yè)的運(yùn)行時(shí)間段等4.9請(qǐng)求分段存儲(chǔ)管理方式與請(qǐng)求分頁(yè)系統(tǒng)類(lèi)似，在分段的基礎(chǔ)上增加請(qǐng)求調(diào)段功能和段置換功能，便可形成具有虛擬存儲(chǔ)器功能的請(qǐng)求分段系統(tǒng)。為實(shí)現(xiàn)請(qǐng)求分段式存儲(chǔ)管理,需要有一定的硬件和相應(yīng)的軟件支持。段表機(jī)制缺段中斷機(jī)構(gòu)地址變換機(jī)構(gòu)4.9.1請(qǐng)求分段中的硬件支持1．段表機(jī)制系統(tǒng)要為每一個(gè)作業(yè)建立一張段表。段表是進(jìn)行段調(diào)度的主要依據(jù)。其一般格式為：段名段長(zhǎng)段的基址存取方式訪(fǎng)問(wèn)字段A修改位M存在位P增補(bǔ)位外存始址標(biāo)志本分段的存取屬性記錄該段被訪(fǎng)問(wèn)的頻繁程度（與分頁(yè)相應(yīng)字段同）該段在調(diào)入內(nèi)存后是否被修改過(guò)，供置換時(shí)參考指示本段是否已調(diào)入內(nèi)存，供程序訪(fǎng)問(wèn)時(shí)參考本段在運(yùn)行過(guò)程中，是否做過(guò)動(dòng)態(tài)增長(zhǎng)本段在外存中的起始地址2．缺段中斷機(jī)構(gòu)在請(qǐng)求分段系統(tǒng)中，若進(jìn)程訪(fǎng)問(wèn)的段尚未調(diào)入內(nèi)存，缺段中斷機(jī)制產(chǎn)生缺段中斷信號(hào)，中斷處理程序根據(jù)信號(hào)調(diào)入所需段。和缺頁(yè)中斷機(jī)制類(lèi)似，在一條指令執(zhí)行期間可能產(chǎn)生多次中斷。和缺頁(yè)中斷機(jī)制不同的是，指令和操作數(shù)必定不會(huì)跨越段邊界上；虛段S不在內(nèi)存阻塞請(qǐng)求進(jìn)程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空區(qū)鏈喚醒請(qǐng)求進(jìn)程返回空區(qū)容量總和能否滿(mǎn)足？空區(qū)拼接，以形成一個(gè)合適的空區(qū)淘汰一個(gè)或幾個(gè)實(shí)段，以形成一個(gè)合適空區(qū)否否是是3．地址變換機(jī)構(gòu)請(qǐng)求分段系統(tǒng)中的地址變換機(jī)構(gòu)是在分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上形成的。在地址變換時(shí)，若發(fā)現(xiàn)所要訪(fǎng)問(wèn)的段不在內(nèi)存，必須先將所缺的段調(diào)入內(nèi)存，并修改段表，然后才能再利用段表進(jìn)行地址變換。為此，在地址變換機(jī)構(gòu)中又增加了某些功能，如缺段中斷的請(qǐng)求及處理等。訪(fǎng)問(wèn)[S][W]W段長(zhǎng)分段越界中斷處理符合存取方式NYY分段保護(hù)中斷處理段S在主存N缺段中斷處理NY修改訪(fǎng)問(wèn)位、修改位形成物理地址

返回4.9.2分段的共享與保護(hù)1．共享段表為了實(shí)現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表，所有各共享段都在共享段表中占有一表項(xiàng)。表項(xiàng)中記錄了共享段的段號(hào)、段長(zhǎng)、內(nèi)存始址、存在位等信息，并記錄了共享此分段的每個(gè)進(jìn)程的情況。1．共享段表段名段長(zhǎng)內(nèi)存始址狀態(tài)外存始址共享進(jìn)程計(jì)數(shù)count狀態(tài)進(jìn)程名進(jìn)程號(hào)段號(hào)存取控制………………共享段表1．共享段表(3)段號(hào)。對(duì)于一個(gè)共享段，不同的進(jìn)程可以各用不同的段號(hào)去共享該段。(2)存取控制字段。對(duì)于一個(gè)共享段，應(yīng)給不同的進(jìn)程以不同的存取權(quán)限。(1)共享進(jìn)程計(jì)數(shù)count。記錄有多少個(gè)進(jìn)程需要共享該分段，特設(shè)置了一個(gè)整型變量count。2．共享段的分配與回收1)共享段的分配第一個(gè)請(qǐng)求以后其它進(jìn)程使用該共享段申請(qǐng)內(nèi)存分區(qū)，調(diào)入，修改共享段表相應(yīng)內(nèi)容；在本進(jìn)程段表中填入該共享段的物理地址；然后在共享段表中增加一表目，填入相應(yīng)內(nèi)容2．共享段的分配與回收2)共享段的回收撤消在該進(jìn)程段表中共享段所對(duì)應(yīng)的表項(xiàng)，以及執(zhí)行count:=count-1操作。若count結(jié)果為0，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對(duì)應(yīng)的表項(xiàng)。3．分段保護(hù)越界檢查2)存取控制檢查3)環(huán)保護(hù)機(jī)構(gòu)段號(hào)與段表長(zhǎng)度進(jìn)行比較段內(nèi)地址與段長(zhǎng)進(jìn)行比較(1)只讀(2)只執(zhí)行(3)讀/寫(xiě)(1)可以訪(fǎng)問(wèn)在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)。(2)可以調(diào)用在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。3．分段保護(hù)圖環(huán)保護(hù)機(jī)構(gòu)

練習(xí)1、考慮下述頁(yè)面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6當(dāng)內(nèi)存塊數(shù)量分別為3，5時(shí)，試問(wèn)LRU、FIFO、OPT這三種置換算法的缺頁(yè)次數(shù)各是多少？（注意，所有內(nèi)存塊最初都是空的，凡第一次用到的頁(yè)面都產(chǎn)生一次缺頁(yè)。）時(shí)47分31秒內(nèi)存塊數(shù)為3,FIFO算法頁(yè)面蹤跡圖％

％＝

缺頁(yè)率為＝

80

100

2016

*

27637637637162162162561541342342312312161212342156212376321236++++ +++ + + + + +++++415321613213216內(nèi)存塊數(shù)為3,LRU算法頁(yè)面蹤跡圖％

％＝

缺頁(yè)率為＝

75

100

2015

*

2363