讓人看了流淚的句子：愛(ài)情使人忘記時(shí)間,時(shí)間也使人忘記愛(ài)情

第四章存儲(chǔ)器管理

/i/89.html第四章存儲(chǔ)器管理裝入和鏈接連續(xù)分配方式基本分頁(yè)存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式虛擬存儲(chǔ)器請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)面置換算法請(qǐng)求分段存儲(chǔ)管理方式4.1程序的裝入和鏈接編輯―――編譯―――鏈接―――裝入―――運(yùn)行4.1.1程序的裝入1、絕對(duì)裝入：編譯后，裝入前已產(chǎn)生了絕對(duì)地址（內(nèi)存地址），裝入時(shí)不再作地址重定位。絕對(duì)地址的產(chǎn)生：（1）由編譯器完成，（2）由程序員編程完成。對(duì)（1）而言，編程用符號(hào)地址。2、可重定位裝入：靜態(tài)重定位：裝入時(shí)完成，主要工作是對(duì)相對(duì)地址中的指令和數(shù)據(jù)地址的調(diào)整過(guò)程，例：圖4－23.動(dòng)態(tài)運(yùn)行時(shí)裝入在執(zhí)行時(shí)才完成相對(duì)—絕對(duì)地址的轉(zhuǎn)換，且有硬件的支持,能保證進(jìn)程的可移動(dòng)性。0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作業(yè)地址空間內(nèi)存空間圖4-24.1.2程序的鏈接1、靜態(tài)鏈接

程序運(yùn)行之前，鏈接成完整的裝入模塊a．對(duì)相對(duì)地址的修改b．變換外部調(diào)用符號(hào)2、裝入時(shí)動(dòng)態(tài)鏈接

目標(biāo)模塊在裝入內(nèi)存時(shí)，邊裝入邊鏈接a.便于修改和更新b.便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享3、運(yùn)行時(shí)動(dòng)態(tài)鏈接程序執(zhí)行需要時(shí)，才將某些目標(biāo)模塊進(jìn)行鏈接模塊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)裝入模塊4.2連續(xù)分配方式單一連續(xù)分配用于單用戶，單任務(wù)中分區(qū)式分配固定式動(dòng)態(tài)式動(dòng)態(tài)重定位4.2.1單一連續(xù)分配單用戶單任務(wù)系統(tǒng)區(qū)+用戶區(qū)存貯保護(hù)一般不設(shè)置保護(hù)也可，因單任務(wù)。

用戶程序位于RAM中的操作系統(tǒng)00xfff…用戶程序位于ROM中的操作系統(tǒng)0用戶程序位于RAM中的操作系統(tǒng)0位于ROM中的設(shè)備驅(qū)動(dòng)程序大型機(jī)和小型計(jì)算機(jī)上，現(xiàn)在很少用掌上型計(jì)算機(jī)和嵌入式系統(tǒng)中早期的PC中，BIOS(basicinputoutputsystem)4.2.2固定分區(qū)特點(diǎn)：內(nèi)存劃為n個(gè)分區(qū)，可同時(shí)裝入n個(gè)作業(yè)/任務(wù)。一、分區(qū)大?。合嗟?缺乏靈活性不相等：利用率更高。二、內(nèi)存分配：將分區(qū)按大小排序，建立分區(qū)使用表，并將起始地址、大小、分配標(biāo)識(shí)作記錄檢索分區(qū)使用表找能滿足要求的尚未分配的分區(qū)放到能容納作業(yè)的最小分區(qū)的隊(duì)列中。作業(yè)C作業(yè)B作業(yè)A操作系統(tǒng)20K32K64K128K256K~~~~分配情況已分配1281284已分配64643已分配32322已分配20121狀態(tài)起址（K）大?。↘)分區(qū)號(hào)分區(qū)說(shuō)明表輸入隊(duì)列的組織每個(gè)分區(qū)有獨(dú)立輸入隊(duì)列：小分區(qū)的隊(duì)列長(zhǎng)，大分區(qū)的隊(duì)列空，浪費(fèi)只維護(hù)一個(gè)輸入隊(duì)列：一旦有分區(qū)空閑，就把該分區(qū)能容納的作業(yè)中最接近隊(duì)列前面的作業(yè)調(diào)入分區(qū)：小作業(yè)浪費(fèi)大分區(qū)

對(duì)隊(duì)列進(jìn)行搜索，一旦有分區(qū)空閑，就取該分區(qū)所能容納的最大的一個(gè)作業(yè)運(yùn)行：對(duì)小作業(yè)不利

至少保留一個(gè)小分區(qū)，允許小作業(yè)運(yùn)行，而不至于為小作業(yè)分配大分區(qū)規(guī)定一個(gè)作業(yè)至多允許被跳過(guò)的次數(shù)，之后就不能被跳過(guò)了

操作系統(tǒng)分區(qū)1分區(qū)2分區(qū)3分區(qū)40100k200k400k700k800k操作系統(tǒng)分區(qū)1分區(qū)2分區(qū)3分區(qū)44.2.3動(dòng)態(tài)分區(qū)分配（比固定式分區(qū)有改善）根據(jù)進(jìn)程需要，動(dòng)態(tài)地為之分配內(nèi)存空間一、數(shù)據(jù)結(jié)構(gòu)1．空閑分區(qū)表2．空閑分區(qū)鏈4.2.3動(dòng)態(tài)分區(qū)分配二、分配算法1．首次適應(yīng)算法FF。要求：分區(qū)按低址――高址鏈接特點(diǎn)：找到第一個(gè)大小滿足的分區(qū)，劃分。有外零頭，低址內(nèi)存使用頻繁。2．循環(huán)首次適應(yīng)算法。從1中上次找到的空閑分區(qū)的下一個(gè)開(kāi)始查找。特點(diǎn)：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)。3．最佳適應(yīng)算法分區(qū)按大小遞增排序；分區(qū)釋放時(shí)需插入到適當(dāng)位置。4.2.3動(dòng)態(tài)分區(qū)分配三、分區(qū)分配1．分配：請(qǐng)求分區(qū)u.size空閑分區(qū)m.size內(nèi)存回收時(shí)的情況2．回收：（1）上鄰空閑區(qū)：合并，改大?。?）下鄰空閑區(qū)：合并，改大小，首址。（3）上、下鄰空閑區(qū)：合并，改大小。（4）不鄰接，則建立一新表項(xiàng)。4.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入連續(xù)式分配中，總量大于作業(yè)大小的多個(gè)小分區(qū)不能容納作業(yè)。緊湊通過(guò)作業(yè)移動(dòng)將原來(lái)分散的小分區(qū)拼接成一個(gè)大分區(qū)。緊湊10KB用戶程序3

必須對(duì)移動(dòng)了的作業(yè)進(jìn)行重定位。動(dòng)態(tài)（因作業(yè)已經(jīng)裝入，隨著對(duì)指令或數(shù)據(jù)的訪問(wèn)自動(dòng)進(jìn)行）2、動(dòng)態(tài)重定位的實(shí)現(xiàn)0100250050002500100001000010100+1250015000作業(yè)J處理機(jī)一側(cè)存儲(chǔ)器一側(cè)重定位寄存器相對(duì)地址主存動(dòng)態(tài)分區(qū)分配算法流程圖4.2.5對(duì)換1對(duì)換的引入將阻塞進(jìn)程，暫時(shí)不用的程序，數(shù)據(jù)換出。將具備運(yùn)行條件的進(jìn)程換入。類型：整體對(duì)換：進(jìn)程對(duì)換，解決內(nèi)存緊張部分對(duì)換：頁(yè)面對(duì)換/分段對(duì)換：提供虛存支持操作系統(tǒng)A操作系統(tǒng)AB操作系統(tǒng)ABC操作系統(tǒng)BC操作系統(tǒng)DC操作系統(tǒng)ACD內(nèi)存分配情況隨著進(jìn)程進(jìn)出而變化4.2.5對(duì)換2對(duì)換空間的管理外存對(duì)換區(qū)比文件區(qū)側(cè)重于對(duì)換速度。因此，對(duì)換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和分配回收類似于可變化分區(qū)分配。4.2.5對(duì)換3換出與換入1）換出a．選出被換出進(jìn)程： 因素：優(yōu)先級(jí)，駐留時(shí)間，進(jìn)程狀態(tài)b．換出過(guò)程：對(duì)于共享段：計(jì)數(shù)減1，是0則換出，否則不換修改PCB和MCB（或內(nèi)存分配表）2）換入：a．選擇換入進(jìn)程：優(yōu)先級(jí)，換出時(shí)間等。b．申請(qǐng)內(nèi)存。c．換入4.3基本分頁(yè)存儲(chǔ)管理連續(xù)分配引起:碎片碎片問(wèn)題的解決：緊湊方式,消耗系統(tǒng)開(kāi)銷。換一種思路：離散分配

允許將一個(gè)進(jìn)程直接分散的裝入到許多不相鄰的分區(qū)中分頁(yè)分段段頁(yè)1).頁(yè)面(page)進(jìn)程的邏輯空間分成若干個(gè)大小相等的頁(yè)面，編號(hào)內(nèi)存空間分為同等大小的物理塊(frame)，編號(hào)頁(yè)面大小要適中：頁(yè)太?。簝?nèi)存碎片小，頁(yè)表可能很長(zhǎng)，換入/出效率低頁(yè)太大：頁(yè)內(nèi)碎片大。2的冪4.3.1頁(yè)面與頁(yè)表2).地址結(jié)構(gòu)邏輯地址A頁(yè)面大小L頁(yè)號(hào)P和頁(yè)內(nèi)地址d:

P=INT[A/L]d=[A]modL如：L=1024B,A＝2170B.則P=2,d=12216 1211 0為每個(gè)進(jìn)程建立一張頁(yè)面映像表

進(jìn)程邏輯地址內(nèi)存中對(duì)應(yīng)的塊號(hào)函數(shù)，實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射存取控制字段讀/寫(xiě)/執(zhí)行3).頁(yè)表用戶程序頁(yè)表頁(yè)號(hào)塊號(hào)內(nèi)存

4.3.2地址變換機(jī)構(gòu)實(shí)現(xiàn)：邏輯頁(yè)號(hào)——物理塊號(hào)的映射，借助頁(yè)表完成。1、基本地址變換機(jī)構(gòu)：

每個(gè)進(jìn)程對(duì)應(yīng)一頁(yè)表，其信息（如長(zhǎng)度、始址）放在PCB中，執(zhí)行時(shí)將其首地址和頁(yè)表長(zhǎng)度裝入頁(yè)表寄存器。越界保護(hù)將十進(jìn)制的邏輯地址1023，4500轉(zhuǎn)換為物理地址以十進(jìn)制的邏輯地址1023為例，畫(huà)出地址轉(zhuǎn)換圖例：已知某分頁(yè)系統(tǒng)，內(nèi)存容量為64KB，每頁(yè)為1KB。對(duì)一個(gè)4頁(yè)大的作業(yè)，其調(diào)入內(nèi)存的頁(yè)面對(duì)應(yīng)的物理塊號(hào)如下表：1）對(duì)上述邏輯地址，可先計(jì)算出它們的頁(yè)號(hào)和頁(yè)內(nèi)地址，然后通過(guò)頁(yè)表轉(zhuǎn)換成對(duì)應(yīng)的物理地址：1023：1023/1K=頁(yè)號(hào)0，頁(yè)內(nèi)地址1023，物理快號(hào)2，則物理地址為：2*1K+1023=30714500：4500/1K=頁(yè)號(hào)4，頁(yè)內(nèi)地址404，頁(yè)號(hào)>頁(yè)表長(zhǎng)度，則越界中斷401023210232467≤2.具有快表的地址變換機(jī)構(gòu)不具快表，則需兩次訪問(wèn)內(nèi)存。（1）訪問(wèn)頁(yè)表，得到物理地址（2）訪問(wèn)物理地址，得到所需內(nèi)容降低1/2的性能，發(fā)現(xiàn)只有少量的頁(yè)表表項(xiàng)被反復(fù)讀取解決辦法：設(shè)置一硬件設(shè)備，將虛擬地址直接映射到物理地址，速度提高。聯(lián)想寄存器（快表）快表貴，不能太多。2.具有快表的地址變換機(jī)構(gòu)

例：有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中：①如果對(duì)主存的一次存取需要1.5μs,試問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間是多少?②如果系統(tǒng)加有快表,平均命中率為85%,當(dāng)頁(yè)表項(xiàng)在快表中時(shí),其查找時(shí)間忽略為0,試問(wèn)此時(shí)的存取時(shí)間是多少?答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問(wèn)需兩次訪問(wèn)主存：一次是訪問(wèn)頁(yè)表，確定所存取頁(yè)面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁(yè)面數(shù)據(jù)?！鲰?yè)表在主存的存取訪問(wèn)時(shí)間=1.5*2=3(μs)■增加快表后的存取訪問(wèn)時(shí)間=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)4.3.3兩級(jí)和多級(jí)頁(yè)表頁(yè)表可能很大，將其離散存放在不同頁(yè)塊中。建一“外部頁(yè)表”來(lái)管理這些離散頁(yè)表塊。相當(dāng)于單級(jí)頁(yè)表中的頁(yè)表寄存器，一般應(yīng)常駐內(nèi)存。每項(xiàng)記錄頁(yè)表始址，且增加存在位。64位機(jī)器頁(yè)表一般>3級(jí)，最外層頁(yè)表常駐。4.4基本分段存儲(chǔ)管理為了滿足用戶（程序員）在編程和使用上的要求即多重定位分區(qū)管理4.4.1引入

每個(gè)段可有其邏輯意義及功能，使得便于（1）方便編程；（2）分段共享；（3）分段保護(hù)；（4）動(dòng)態(tài)鏈接；（5）動(dòng)態(tài)增長(zhǎng)；（如數(shù)據(jù)段的增長(zhǎng)）4.4.2分段系統(tǒng)的基本原理分段地址空間被劃分為若干個(gè)段，每段定義了一組邏輯信息。段號(hào)+段內(nèi)地址。段表：Mapping:邏輯段物理內(nèi)存區(qū)每段分配一個(gè)連續(xù)分區(qū)，各段離散在不同分區(qū)中地址變換機(jī)構(gòu)：分頁(yè)與分段區(qū)別：（1）頁(yè)是信息的物理單位，段是邏輯單位（2）頁(yè)長(zhǎng)度固定，段長(zhǎng)度不固定（由用戶指定）（3）一維與二維(Main)=030K(X)=120K(D)=230K(S)=330K40K80K120K150K04.4.3信息共享段式系統(tǒng)易于共享例：圖4-18及4-19分頁(yè)與分段共享比較可重入碼（純代碼）各個(gè)進(jìn)程應(yīng)保留局部數(shù)據(jù)區(qū)40個(gè)用戶，程序中160K代碼，40K數(shù)據(jù),每頁(yè)4K,則代碼40個(gè)頁(yè)面，數(shù)據(jù)區(qū)10個(gè)頁(yè)面進(jìn)程1進(jìn)程2頁(yè)表頁(yè)表主存分頁(yè)系統(tǒng)中共享editor分段系統(tǒng)中共享editor4.4.4段頁(yè)式存儲(chǔ)管理一、基本原理先將用戶程序分成若干段，再把每個(gè)段分成若干頁(yè)，并為每一段賦予一個(gè)段名段號(hào)(S)分頁(yè)的優(yōu)點(diǎn)：提高內(nèi)存利用率分段的優(yōu)點(diǎn)：方便和滿足用戶04K8K12K15K04K8K04K8K10K段內(nèi)頁(yè)號(hào)(P)頁(yè)內(nèi)地址(W)主程序段子程序段數(shù)據(jù)段

？各取所長(zhǎng)4.4.4段頁(yè)式存儲(chǔ)管理二、地址變換段表寄存器：存放段表始址和段長(zhǎng)段表寄存器段表頁(yè)表主存利用段表和頁(yè)表實(shí)現(xiàn)地址映射4.4.4段頁(yè)式存儲(chǔ)管理二、地址變換段表寄存器：存放段表始址和段長(zhǎng)段號(hào)S與段長(zhǎng)進(jìn)行比較，越界？未越界，則用段表始址和段號(hào)S求段表項(xiàng)的位置，讀出該段的頁(yè)表始址用段內(nèi)頁(yè)號(hào)P求頁(yè)表項(xiàng)的位置，讀出物理塊號(hào)b用塊號(hào)b和頁(yè)內(nèi)地址W構(gòu)成物理地址段表寄存器段表頁(yè)表++>段超長(zhǎng)段頁(yè)式系統(tǒng)的地址變換機(jī)構(gòu)4.4.4段頁(yè)式存儲(chǔ)管理三次訪內(nèi)存操作訪問(wèn)內(nèi)存中的段表，得頁(yè)表始址訪問(wèn)內(nèi)存中的頁(yè)表，得到物理地址訪問(wèn)物理地址，得到所需內(nèi)容為提高速度，在地址變換機(jī)構(gòu)中增設(shè)一高速緩沖寄存器（Cache）4.5虛擬存儲(chǔ)器怎么辦？

增加物理內(nèi)存or邏輯上增加內(nèi)存全部裝入內(nèi)存后才能運(yùn)行？大作業(yè)：超出內(nèi)存容量？作業(yè)多：不能全部容納4.5.1虛擬存儲(chǔ)器的引入1.常規(guī)存儲(chǔ)管理的特征：一次性（指全部裝入）不是所有的程序和數(shù)據(jù)都能用到，一次性裝入是一種浪費(fèi)駐留性（指駐留在內(nèi)存不換出）I/O等待或僅運(yùn)行一次的進(jìn)程長(zhǎng)期占據(jù)內(nèi)存資源是一種浪費(fèi)

問(wèn)題：是否需要一次性將作業(yè)全部裝入作業(yè)是否需要長(zhǎng)期地駐留在內(nèi)存4.5.1虛擬存儲(chǔ)器的引入2.局部性原理程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律：即在一較短時(shí)間內(nèi)，程序的執(zhí)行僅限于某個(gè)部分；相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過(guò)程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。過(guò)程調(diào)用將會(huì)使程序的執(zhí)行有一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域，在大多數(shù)情況下，過(guò)程調(diào)用的深度都不超過(guò)5。循環(huán)結(jié)構(gòu)將執(zhí)行多次程序中對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，往往都局限于小的范圍內(nèi)。局部性表現(xiàn)時(shí)間局部性：（循環(huán)）指令一旦執(zhí)行，不久以后可能再次執(zhí)行；數(shù)據(jù)結(jié)構(gòu)被訪問(wèn)，則不久以后可能再次被訪問(wèn)空間局部性：（順序）一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，不久之后，其附近的存儲(chǔ)單元也被訪問(wèn)4.5.1虛擬存儲(chǔ)器的引入3、虛擬存貯器基于局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒(méi)有必要全部裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁(yè)面或段，先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤(pán)上。

定義：具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)系統(tǒng)。實(shí)質(zhì)：以時(shí)間換空間，但時(shí)間犧牲不大。虛擬大小由內(nèi)存容量和外存容量之和決定。4.5.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)，毫無(wú)例外地都是建立在離散分配存儲(chǔ)管理方式的基礎(chǔ)上的。？？連續(xù)分配方式需要?jiǎng)討B(tài)重定位4.5.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方式一、請(qǐng)求分頁(yè)系統(tǒng)在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。以頁(yè)為單位進(jìn)行置換需硬件：（1）請(qǐng)求分頁(yè)的頁(yè)表機(jī)制（2）缺頁(yè)中斷機(jī)構(gòu)（3）地址變換機(jī)構(gòu)需實(shí)現(xiàn)請(qǐng)求分頁(yè)機(jī)制的軟件（置換軟件等）二、請(qǐng)求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上，增加請(qǐng)求調(diào)段功能和分段置換功能。以段為單位進(jìn)行置換需硬件：（1）請(qǐng)求分段的段表結(jié)構(gòu)（2）缺段中斷機(jī)構(gòu)（3）地址變換機(jī)構(gòu)需實(shí)現(xiàn)請(qǐng)求分段機(jī)制的軟件（置換軟件等）三、段頁(yè)式虛擬存儲(chǔ)器4.5.3虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器最基本的特征是離散性，在此基礎(chǔ)上又形成了多次性及對(duì)換性的特征。其所表出來(lái)的最重要的特征是虛擬性。1、離散性離散性是指在內(nèi)存分配是采用離散分配方式，這是其他幾個(gè)特征的基礎(chǔ)。沒(méi)有離散性，也就不可能實(shí)現(xiàn)虛擬存儲(chǔ)器。2、多次性多次性是指一個(gè)作業(yè)被分成多次地調(diào)入內(nèi)存運(yùn)行3、對(duì)換性對(duì)換性是指允許在作業(yè)的運(yùn)行過(guò)程中換進(jìn)、換出。換進(jìn)、換出能有效地提高內(nèi)存利用率4、虛擬性虛擬性是指能夠從邏輯上擴(kuò)允內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)現(xiàn)內(nèi)存容量。4.6請(qǐng)求分頁(yè)存儲(chǔ)管理在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。以頁(yè)為單位進(jìn)行置換——長(zhǎng)度固定實(shí)現(xiàn)簡(jiǎn)單，最常用需硬件：（1）請(qǐng)求分頁(yè)的頁(yè)表機(jī)制（2）缺頁(yè)中斷機(jī)構(gòu)（3）地址變換機(jī)構(gòu)一、頁(yè)表機(jī)制頁(yè)表項(xiàng)：二、缺頁(yè)中斷機(jī)構(gòu)：

每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OS將所缺之頁(yè)調(diào)入內(nèi)存。4.6.1請(qǐng)求分頁(yè)中的硬件支持涉及6次缺頁(yè)中斷的指令6543214.6.1請(qǐng)求分頁(yè)中的硬件支持三、地址變換機(jī)構(gòu)比簡(jiǎn)單分頁(yè)機(jī)制，增加了缺頁(yè)中斷處理和頁(yè)面置換過(guò)程：先檢索快表，如果找到該頁(yè)，則修改頁(yè)表項(xiàng)中的訪問(wèn)位、修改位等，再計(jì)算形成物理地址；如果未找到，則應(yīng)再到內(nèi)存中去查找頁(yè)表，看其頁(yè)表項(xiàng)中的狀態(tài)位P，確定該頁(yè)是否調(diào)入內(nèi)存。如果：（1）該頁(yè)已經(jīng)調(diào)入內(nèi)存：應(yīng)將此頁(yè)的頁(yè)表項(xiàng)寫(xiě)入快表，當(dāng)快表已滿時(shí)，應(yīng)先調(diào)出一個(gè)按某種算法所確定的頁(yè)的頁(yè)表項(xiàng)，然后再寫(xiě)入該頁(yè)的頁(yè)表項(xiàng)。（2）該頁(yè)尚未調(diào)入內(nèi)存，這時(shí)便應(yīng)產(chǎn)生缺頁(yè)中斷，請(qǐng)求OS從外存中把該頁(yè)調(diào)入內(nèi)存。4.6.2內(nèi)存分配策略和分配算法一、最小物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。單地址指令且采用直接尋址方式，最小物理塊數(shù)為2允許間接尋址時(shí)，則至少要求有3個(gè)物理塊。

指令長(zhǎng)度≥2，源地址和目的地址涉及的區(qū)域跨頁(yè)面，則至少要求6個(gè)

4.6.2內(nèi)存分配策略和分配算法二、物理塊的分配策略分配策略：固定和可變分配策略。置換策略：全局置換和局部置換。于是可組合出以下三種頁(yè)面分配和置換策略。1．固定分配局部置換。缺點(diǎn)：難以確定固定分配的頁(yè)數(shù).(少：頻繁缺頁(yè)，置換率高多：浪費(fèi))2.可變分配全局置換預(yù)先分配好，缺頁(yè)時(shí)從系統(tǒng)空閑隊(duì)列里取出分配，用完時(shí)選一頁(yè)調(diào)出置換3.可變分配局部置換根據(jù)進(jìn)程的缺頁(yè)率進(jìn)行頁(yè)面數(shù)調(diào)整，進(jìn)程之間相互不會(huì)影響。三、分配算法1．平均分配算法將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程：沒(méi)考慮進(jìn)程大小2．按進(jìn)程大小比例分配算法：系統(tǒng)中各進(jìn)程頁(yè)面數(shù)的總和為：

每個(gè)進(jìn)程所能分配到的物理塊數(shù)為bi：

3．考慮優(yōu)先權(quán)分配算法把可供分配的物理塊分成：一部分按比例地分給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。

4.6.3調(diào)頁(yè)策略1.調(diào)入時(shí)機(jī)：預(yù)調(diào)：采用一種以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，預(yù)計(jì)在不久之后便會(huì)被訪問(wèn)的程序或數(shù)據(jù)所在的頁(yè)面，預(yù)先調(diào)入內(nèi)存

成功率50％請(qǐng)求調(diào)：當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序的數(shù)據(jù)時(shí)，發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，需立即提出請(qǐng)求，由系統(tǒng)將其所需頁(yè)面調(diào)入內(nèi)存。較費(fèi)系統(tǒng)開(kāi)銷各有優(yōu)劣4.6.3調(diào)頁(yè)策略2．從何處調(diào)頁(yè)：對(duì)換區(qū)空間足夠大：全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。為此，在進(jìn)程運(yùn)行前，將進(jìn)程有關(guān)文件從文件區(qū)拷貝到對(duì)換區(qū)。對(duì)換區(qū)空間不夠大：不會(huì)被修改的文件，直接從文件區(qū)調(diào)入；可能被修改的部分，換出時(shí)須先調(diào)到對(duì)換區(qū)，需要時(shí)從對(duì)換區(qū)調(diào)入。UNIX方式：與進(jìn)程有關(guān)的文件放在文件區(qū)，未運(yùn)行過(guò)的頁(yè)面，從文件區(qū)調(diào)入；運(yùn)行過(guò)的而又被換出的頁(yè)面，放在對(duì)換區(qū)，下次調(diào)入時(shí)從對(duì)換區(qū)調(diào)入。3.頁(yè)面調(diào)入過(guò)程所需頁(yè)面未在內(nèi)存時(shí)，缺頁(yè)中斷，查找頁(yè)表得到該頁(yè)外存物理塊號(hào)，再找置換頁(yè)（回寫(xiě)問(wèn)題），完成調(diào)入，改頁(yè)表目的：減少對(duì)換量，提高系統(tǒng)性能4.7.1最佳置換算法和先進(jìn)先出算法一、最佳置換算法（理論上的）4.7頁(yè)面置換算法缺頁(yè)率：6/124.7頁(yè)置換算法二、先進(jìn)先出算法FIFO缺頁(yè)率：9/124.7.2最近最久未用LRU置換將“最近的過(guò)去”，作為“最近的將來(lái)”。選擇最近最久未使用的頁(yè)面予以淘汰所要解決的問(wèn)題有：一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁(yè)面各有多久時(shí)間未被進(jìn)程訪問(wèn)；如何快速地知道哪一頁(yè)最近最久未使用的頁(yè)面硬件支持：

1．位移寄存器：（定時(shí)右移） R=R