2022/11/19第四章存儲器管理第四章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，在進(jìn)行內(nèi)存分配的時(shí)候，不需要對分區(qū)進(jìn)行切割。算法實(shí)現(xiàn)5）快速適應(yīng)算法該算法的優(yōu)點(diǎn)：查找效率高。不會對任何分區(qū)分割，能保留大的分區(qū)。也不會產(chǎn)生內(nèi)存碎片。該算法的缺點(diǎn)：在分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開銷較大。一個(gè)分區(qū)只屬于一個(gè)進(jìn)程，存在空間浪費(fèi)。3．分區(qū)分配操作1)分配內(nèi)存設(shè)請求的分區(qū)大小為u.size，表中每個(gè)空閑分區(qū)的大小表示為m.size，若m.size-u.sizesize(規(guī)定的不再切割的分區(qū)大小)，將整個(gè)分區(qū)分配給請求者，否則從分區(qū)中按請求的大小劃出一塊內(nèi)存空間分配出去，余下部分留在空閑鏈中，將分配區(qū)首址返回給調(diào)用者。從頭開始查表檢索完否？m.Size>u.size?m.size-u.size<=size?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關(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ū)和動態(tài)分區(qū)方式都有不足之處。伙伴系統(tǒng)方式是對以上兩種內(nèi)存方式的一種折衷方案?；锇橄到y(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)，l≤k≤m，其中：21表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。當(dāng)把一個(gè)存儲塊分為大小相等的兩半時(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開始找可用的塊

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í)，只有伙伴才合并，并將合并后的新空閑塊加入上一級大小的空閑塊鏈表中。4.3.5哈希算法哈希算法就是利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表。當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計(jì)算，即得到在哈希表中的位置。4.3.5哈希算法算法思想

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

優(yōu)點(diǎn)：便于動態(tài)申請內(nèi)存便于共享內(nèi)存便于動態(tài)鏈接缺點(diǎn)：碎片問題(外碎片)，內(nèi)存利用率不高，受實(shí)際內(nèi)存容量限制分區(qū)式存儲管理的優(yōu)缺點(diǎn)

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

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

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

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

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

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

頁號頁內(nèi)地址（位移量）

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

塊號

存取控制頁描述符+如果頁號>頁表長度，則中斷，否則繼續(xù).如果訪問非法，則中斷，否則繼續(xù)。頁號位移量虛擬地址

LA

塊號位移量物理地址頁表始址長度頁表寄存器PTR頁表

塊號存取控制頁表項(xiàng)頁號

01

...塊號位移量

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

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

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

1)方便編程

2)信息共享

3)信息保護(hù)

4)動態(tài)增長

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

邏輯地址

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

分段管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：便于動態(tài)申請內(nèi)存管理和使用統(tǒng)一化便于共享便于動態(tài)鏈接缺點(diǎn)：產(chǎn)生碎片思考：與可變分區(qū)存儲管理方案的相同點(diǎn)與不同點(diǎn)？4.5.4段頁式存儲管理分頁優(yōu)點(diǎn)：提高內(nèi)存利用率分段優(yōu)點(diǎn)：滿足用戶需要。因此可以將兩者結(jié)合成一種新的存儲管理方式系統(tǒng)稱為“段頁式系統(tǒng)”。結(jié)合了段式與頁式二者優(yōu)點(diǎn)克服了二者的缺點(diǎn)

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

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

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

駐留性。作業(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)地，它所訪問的存儲空間也局限于某個(gè)區(qū)域。具體地表現(xiàn)為：時(shí)間局部性和空間局部性2．局部性原理①時(shí)間的局限性，如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；某個(gè)數(shù)據(jù)被訪問，則不久以后該數(shù)據(jù)可能被再次訪問。②空間的局限性，一旦程序訪問了某個(gè)存儲單元，在不久以后，其附近的存儲單元也被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址可能集中在一定的范圍內(nèi)。3．虛擬存儲器的定義具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存進(jìn)行擴(kuò)充的一種存儲器系統(tǒng)，其邏輯容量由內(nèi)存和外存容量之和決定，其運(yùn)行速度接近于內(nèi)存的速度，而成本接近于外存。虛擬存儲器：虛擬存儲是一種性能非常優(yōu)越的存儲器管理技術(shù)3．虛擬存儲器的定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

簡單Clock置換算法的流程和示例入口查尋指針前進(jìn)一步，指向下一個(gè)表目頁面訪問位=0?選擇該頁面淘汰是返回置頁面訪問位＝“0”否塊號頁號訪問位指針0124034215650711替換指針Page9use=1Page19Use=1Page1Use=1Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page222Use=0Page33Use=1下一個(gè)幀指針n-1012345678一個(gè)頁替換前的緩沖區(qū)狀態(tài)第1頁框...下一頁替換后的緩沖區(qū)狀態(tài)Page9use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=0Page556Use=1Page13Use=0Page67Use=1Page222Use=0Page33Use=1.n012345678..2321524532522*Clock算法：缺頁次數(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．簡單的Clock置換算法在改進(jìn)型Clock算法中首選置換頁面：既是未使用過的頁面；又是未修改的頁面由訪問位A和修改位M可以組合成四種類型的頁面：(1)最近沒有被引用,沒有被修改(A=0,M=0)(2)最近沒有被引用,但被修改(A=0,M=1)(3)最近被引用,沒有被修改(A=1,M=0)(4)最近被引用過,也被修改過(A=1,M=1)2．改進(jìn)型Clock置換算法置換步驟：步3：如果步2失敗，再轉(zhuǎn)向步1操作。2．改進(jìn)型Clock置換算法步1：從指針當(dāng)前位置開始,掃描循環(huán)隊(duì)列。把找到的第一個(gè)A=0,M=0的頁面作為淘汰頁面，未找到，轉(zhuǎn)步2。步2：查找A=0且M=1的頁面，把找到的第一個(gè)這樣的頁面作為淘汰頁面，所有經(jīng)過的頁面的訪問位A置0。4.8.4其它置換算法1、最少使用置換算法把到當(dāng)前為止被訪問次數(shù)最少的頁面淘汰。每頁設(shè)置訪問計(jì)數(shù)器，每當(dāng)頁面被訪問時(shí)，該頁面的訪問計(jì)數(shù)器加1；發(fā)生缺頁中斷時(shí)，淘汰計(jì)數(shù)值最小的頁面，并將所有計(jì)數(shù)清零；2．頁面緩沖算法它是對FIFO算法的發(fā)展，通過被置換頁面的緩沖，有機(jī)會找回剛被置換的頁面；設(shè)置兩個(gè)鏈表，空閑鏈表和已修改頁面鏈表。用FIFO選擇被置換頁如果被置換頁沒有發(fā)生修改，將它直接放入空閑鏈表否則放入到已修改頁面的鏈表中。2．頁面緩沖算法需要調(diào)入新的物理頁面時(shí)，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項(xiàng)所指的頁面?？臻e頁面和已修改頁面，仍停留在內(nèi)存中一段時(shí)間，如果這些頁面被再次訪問，只需較小開銷。當(dāng)已修改頁面達(dá)到一定數(shù)目后，再將它們一起調(diào)出到外存，然后將它們歸入空閑頁面鏈表。頁面置換算法比較0510152025354030068101214FIFOCLOCK

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

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

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

返回4.9.2分段的共享與保護(hù)1．共享段表為了實(shí)現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表，所有各共享段都在共享段表中占有一表項(xiàng)。表項(xiàng)中記錄了共享段的段號、段長、內(nèi)存始址、存在位等信息，并記錄了共享此分段的每個(gè)進(jìn)程的情況。1．共享段表段名段長內(nèi)存始址狀態(tài)外存始址共享進(jìn)程計(jì)數(shù)count狀態(tài)進(jìn)程名進(jìn)程號段號存取控制………………共享段表1．共享段表(3)段號。對于一個(gè)共享段，不同的進(jìn)程可以各用不同的段號去共享該段。(2)存取控制字段。對于一個(gè)共享段，應(yīng)給不同的進(jìn)程以不同的存取權(quán)限。(1)共享進(jìn)程計(jì)數(shù)count。記錄有多少個(gè)進(jìn)程需要共享該分段，特設(shè)置了一個(gè)整型變量count。2．共享段的分配與回收1)共享段的分配第一個(gè)請求以后其它進(jìn)程使用該共享段申請內(nèi)存分區(qū)，調(diào)入，修改共享段表相應(yīng)內(nèi)容；在本進(jìn)程段表中填入該共享段的物理地址；然后在共享段表中增加一表目，填入相應(yīng)內(nèi)容2．共享段的分配與回收2)共享段的回收撤消在該進(jìn)程段表中共享段所對應(yīng)的表項(xiàng)，以及執(zhí)行count:=count-1操作。若count結(jié)果為0，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對應(yīng)的表項(xiàng)。3．分段保護(hù)越界檢查2)存取控制檢查3)環(huán)保護(hù)機(jī)構(gòu)段號與段表長度進(jìn)行比較段內(nèi)地址與段長進(jìn)行比較(1)只讀(2)只執(zhí)行(3)讀/寫(1)可以訪問在相同環(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、考慮下述頁面走向：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í)，試問LRU、FIFO、OPT這三種置換算法的缺頁次數(shù)各是多少？（注意，所有內(nèi)存塊最初都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁。）時(shí)47分31秒內(nèi)存塊數(shù)為3,FIFO算法頁面蹤跡圖％

％＝

缺頁率為＝

80

100

2016

*

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

％＝

缺頁率為＝

75

100

2015

*

2363