操作系統(tǒng)第四章課件

第四章

存儲器管理第一節(jié)存儲器的層次結(jié)構(gòu)第二節(jié)

程序的裝入和鏈接第三節(jié)

連續(xù)分配存儲管理方式第四節(jié)對換（Swapping）第五節(jié)

基本分頁存儲管理方式第六節(jié)

基本分段存儲管理方式第四章

存儲器管理第一節(jié)存儲器的層次結(jié)構(gòu)序言存儲器：主存（內(nèi)存）、副存（外存）內(nèi)存－進程、外存－文件內(nèi)存管理：地址映射、內(nèi)存分配與回收存儲保護、內(nèi)存擴充(虛擬內(nèi)存)外存管理：文件管理序言存儲器：主存（內(nèi)存）、副存（外存）存儲器的層次結(jié)構(gòu)計算機對存儲器的要求：1.要求存儲器的訪問速度能跟上處理機的運行速度。2.要求存儲器具有非常大的容量。3.要求存儲器的價格便宜?；谝陨先齻€要求，目前計算機系統(tǒng)都采用了多層結(jié)構(gòu)的存儲器系統(tǒng)。存儲器的層次結(jié)構(gòu)計算機對存儲器的要求：多層結(jié)構(gòu)存儲器系統(tǒng)1.存儲器的多層結(jié)構(gòu)通用計算機的存儲器具有3層結(jié)構(gòu)：由低到高分別為：輔存、主存、CPU寄存器。高檔計算機的存儲器結(jié)構(gòu)分為：寄存器、高速緩存、主存儲器、磁盤緩存、固定磁盤、可移動存儲介質(zhì)等6層。存儲器的特點：層次越高，存儲介質(zhì)的訪問速度越快，價格越高，容量越小。存儲器管理系統(tǒng)負責(zé)管理內(nèi)存，外存作為文件管理內(nèi)容。2.可執(zhí)行存儲器指寄存器和主存儲器特點：對可執(zhí)行存儲器訪問速度快，對輔存的訪問需要通過I/O設(shè)備，因此耗費的時間遠高于可執(zhí)行存儲器，一般至少相差3個數(shù)量級。多層結(jié)構(gòu)存儲器系統(tǒng)主存儲器與寄存器主存儲器_內(nèi)存用于保存進程運行時的程序和數(shù)據(jù)，又稱為可執(zhí)行存儲器。CPU一般從主存中取出指令和數(shù)據(jù)分別存放于CPU中的指令寄存器和數(shù)據(jù)寄存器中，反之將寄存器數(shù)據(jù)存入主存中。主存早期容量為數(shù)10到數(shù)百KB，現(xiàn)在高達數(shù)10MB到數(shù)GB。但主存訪問速度低，故引入了寄存器和高速緩存。寄存器寄存器的訪問速度最快，與處理器運行速度相當，但價格非常昂貴，容量也很小。隨著VLSI的發(fā)展，現(xiàn)在的微機系統(tǒng)中，寄存器數(shù)量已達到數(shù)10個到數(shù)百個。主存儲器與寄存器主存儲器_內(nèi)存高速緩存和磁盤緩存1.高速緩存是現(xiàn)代計算機結(jié)構(gòu)中的一個重要部件，介于寄存器和主存之間，用于備份主存中較常用的數(shù)據(jù)，以減少處理機對主存的訪問次數(shù)，從而大幅提高程序執(zhí)行速度。其容量遠大于寄存器，從幾10KB到幾MB，其訪問速度快于主存。特點：由于高速緩存的速度越高，價格越貴，故計算機系統(tǒng)會設(shè)置兩個或多個高級緩存，一級緩存緊靠內(nèi)存，速度最快，容量最小。2.磁盤緩存由于主存的訪問速度遠高于磁盤的訪問速度，為了緩和兩者間速度差異，設(shè)置了磁盤緩存，用于暫時存放頻繁使用的一部分磁盤數(shù)據(jù)和信息，以減少訪問磁盤的次數(shù)。特點：與高速緩存不同，磁盤緩存不是一種實際存在的存儲器，而是利用主存中的一部分存儲空間暫時存放磁盤信息。一個文件數(shù)據(jù)可能會出現(xiàn)在不同層次的存儲器中：輔存—主存（磁盤緩存）高速緩存和磁盤緩存1.高速緩存程序的裝入和鏈接用戶提交的程序需要經(jīng)過以下幾個步驟才能被系統(tǒng)運行：1.編譯2.鏈接3.裝入程序的裝入和鏈接用戶提交的程序需要經(jīng)過以下幾個步驟才能被系統(tǒng)從源程序到程序執(zhí)行編譯：編譯程序由編譯程序（Compiler）將用戶源代碼編譯成若干個目標模塊。鏈接：鏈接程序由鏈接程序（Linker）將編譯后形成的一組目標模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成裝入模塊。裝入：裝入程序由裝入程序（Loader）將裝入模塊復(fù)制到內(nèi)存中。庫匯編編譯主子1子2目標模塊鏈接程序裝入模塊庫主子1子2裝入程序內(nèi)存庫主子1子2從源程序到程序執(zhí)行編譯：編譯程序庫匯編主子1子2目標模塊鏈接程序的裝入就是把鏈接好的裝入模塊裝入“內(nèi)存”。裝入方式絕對裝入：只適用單道程序環(huán)境；裝入內(nèi)存的位置是可知的、固定的，故采用絕對裝入方式，按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存，由于程序的邏輯地址與物理地址一致，故地址無需修改。程序中所使用的物理地址一般設(shè)置為在編譯、匯編時再給出，此前由符號地址代替?？芍囟ㄎ谎b入（靜態(tài)重定位）：適用于多道程序環(huán)境，存在很多的用戶程序編譯所形成的若干個目標模塊，它們的起始地址都是從0開始的邏輯地址，可通過重定位方式裝入內(nèi)存合適的位置，但這會使裝入模塊的邏輯地址與實際裝入內(nèi)存后的物理地址不同，故需要對程序和數(shù)據(jù)的地址進行修改。動態(tài)運行時裝入（動態(tài)重定位）：允許程序在運行時，在內(nèi)存中移動位置。實際上，程序在內(nèi)存中運行時，它在內(nèi)存中的位置可能要經(jīng)常改變。例如：在對換功能系統(tǒng)中，一個進程可能被多次換出，又多次換入。動態(tài)運行時裝入程序：把裝入模塊裝入內(nèi)存后，并不立即把模塊中的邏輯地址轉(zhuǎn)換為物理地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。程序的裝入就是把鏈接好的裝入模塊裝入“內(nèi)存”。重定位的概念重定位概念：把程序裝入內(nèi)存時，修改程序中所有與地址有關(guān)的項。邏輯地址變換為物理地址。重定位的類型靜態(tài)重定位：程序執(zhí)行前，一次性，鏈接裝入程序。動態(tài)重定位：處理機每次訪問主存時，有動態(tài)地址變換機構(gòu)（硬件）自動執(zhí)行。

作業(yè)地址空間內(nèi)存空間裝入365LOAD1,2500500025001000365LOAD1,250015000125001000011000365LOAD1,1250015000125001000011000重定位的概念重定位裝入365LOAD1,2500365LO鏈接方式靜態(tài)鏈接：程序在運行之前，先將目標模塊及其所需庫函數(shù)鏈接成一個完整的裝配模塊，以后不再拆開。這種事先進行鏈接的方式即為靜態(tài)鏈接方式。（1）對相對地址進行修改，將目標模塊的相對地址修改為相應(yīng)的裝入模塊相對地址；（2）變換外部的調(diào)用符號，將每個模塊中所用的外部調(diào)用符號也都變換為裝入模塊中的相對地址。鏈接方式靜態(tài)鏈接：程序在運行之前，先將目標模塊及其所需庫函數(shù)程序的鏈接鏈接：把一個程序相關(guān)的一組目標模塊和系統(tǒng)調(diào)用模塊（庫函數(shù)）鏈接形成一個整體——裝入模塊的過程。具體工作：對相對地址的修改；變換外部調(diào)用符號。模塊ACallB;Return;0L-1模塊BCallC;Return;0M-1模塊C……;Return;0N-1鏈接模塊AJSR‘L’;Return;0L-1模塊BJSR‘L+M’;Return;LL+M-1模塊C……;Return;L+ML+M+N-1裝入模塊目標模塊使用的都是相對地址，其起始地址都為0，每個模塊中的地址都是相對于起始地址計算的。長度程序的鏈接鏈接：模塊A0模塊B0模塊C0鏈接模塊A0模塊BL鏈接方式裝入時動態(tài)鏈接：在將目標模塊裝入內(nèi)存時，邊裝入邊鏈接的鏈接方式，即在裝入一個目標模塊時，若發(fā)生一個外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標模塊，并將它裝入內(nèi)存，同時修改目標模塊中的相對地址。優(yōu)點：（1）便于修改和更新，由于各目標模塊是分開存放的，所以要修改或更新各目標模塊就很容易。（2）便于實現(xiàn)對目標模塊的共享，在采用靜態(tài)鏈接方式時，每個應(yīng)用模塊都必須含有其目標模塊的拷貝，無法實現(xiàn)對目標模塊的共享，但采用裝入時動態(tài)鏈接的方式時，OS就很容易將一個目標模塊鏈接到幾個應(yīng)用模塊上，實現(xiàn)多個應(yīng)用程序?qū)υ撃K的共享。鏈接方式裝入時動態(tài)鏈接：在將目標模塊裝入內(nèi)存時，邊裝入邊鏈接鏈接方式運行時動態(tài)鏈接：將對某些模塊的鏈接推遲到程序執(zhí)行時才進行。亦即，在執(zhí)行過程中，當發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊，并將之裝入內(nèi)存，將其鏈接到調(diào)用者模塊上。優(yōu)點：凡在執(zhí)行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅能加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。鏈接方式運行時動態(tài)鏈接：將對某些模塊的鏈接推遲到程序執(zhí)行時才連續(xù)分配存儲管理方式連續(xù)分配方式：為用戶程序分配一個連續(xù)的內(nèi)存空間，即程序中代碼的邏輯地址相鄰體現(xiàn)在內(nèi)存空間分配時，物理地址的相鄰。曾被廣泛應(yīng)用，且現(xiàn)在仍被采用。單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配動態(tài)可重定位分區(qū)分配連續(xù)分配存儲管理方式連續(xù)分配方式：為用戶程序分配一個連續(xù)的內(nèi)單一連續(xù)分配單一連續(xù)分配的基本思想把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)供OS使用，通常放在內(nèi)存的低址部分；系統(tǒng)區(qū)以外的全部內(nèi)存空間是用戶區(qū)，僅裝有一道用戶程序。單一連續(xù)分配的特點只能用于單用戶、單任務(wù)的單道程序環(huán)境的OS中。軟件簡單，硬件要求低（可無需存儲器保護措施）實例CP/M，MS-DOS，RT-11等單用戶OSMS-DOS內(nèi)存分區(qū)CP/M內(nèi)存分配系統(tǒng)參數(shù)區(qū)BIOSCCPBDOS系統(tǒng)區(qū)系統(tǒng)區(qū)單一連續(xù)分配單一連續(xù)分配的基本思想系統(tǒng)參數(shù)區(qū)BIOSCCP固定分區(qū)分配在多道程序環(huán)境中，為了防止裝入內(nèi)存中的多個程序間互相干擾，于是將整個內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，將每個分區(qū)中只裝入一道作業(yè)，即為固定分區(qū)分配。1.劃分分區(qū)的方法（劃分為若干個固定大小的分區(qū)）分區(qū)大小相等：缺乏靈活性：當程序太小會造成內(nèi)存空間浪費，當程序太大又無法滿足其運行。比較適用于一臺計算機同時控制多個相同對象的場合。分區(qū)大小不相等：較上種方法靈活，通常將內(nèi)存劃分為多個較小的分區(qū)、適量中等分區(qū)、少量大分區(qū)。2.內(nèi)存分區(qū)分配分區(qū)使用表（MBT）：分區(qū)號、大小、分區(qū)起址、狀態(tài)分區(qū)按內(nèi)存空間大小排隊當用戶程序要裝入時，由內(nèi)存分配程序檢索分區(qū)使用表，找到滿足要求、尚未分配的分區(qū)，將之分配給它。固定分區(qū)分配在多道程序環(huán)境中，為了防止裝入內(nèi)存中的多個程序間固定分區(qū)分配區(qū)號/鍵大小起址狀態(tài)18K512K正使用232K520K正使用332K552K未使用4128K584K未使用5512K712K正使用…………系統(tǒng)區(qū)分區(qū)1分區(qū)4分區(qū)5分區(qū)2分區(qū)3系統(tǒng)區(qū)作業(yè)3分區(qū)4作業(yè)2作業(yè)1分區(qū)3分區(qū)使用表固定分區(qū)分配區(qū)號/鍵大小起址狀態(tài)18K512K正使用232動態(tài)分區(qū)分配可變分區(qū)分配思想分區(qū)的位置和大小都不固定，應(yīng)作業(yè)的要求而設(shè)置，為之動態(tài)分配內(nèi)存空間。動態(tài)分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)的兩種形式：空閑分區(qū)表（用于記錄每個空閑分區(qū)）、空閑分區(qū)鏈：用于實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的頭部、尾部分別設(shè)置了前向、后向指針，形成了雙向鏈表。分區(qū)號始址大小狀態(tài)12012k空閑24032k空閑310064k空閑4220128k空閑前向后向指針指針N+2N+200分區(qū)大小分區(qū)狀態(tài)動態(tài)分區(qū)分配可變分區(qū)分配思想分區(qū)號始址大小狀態(tài)12012k空分區(qū)分配流程圖分配內(nèi)存分區(qū)大小與所需空間大小“匹配”：M.Size-U.Size≦Size（不再分割的小分區(qū)的尺寸）剩余部分掛接到空閑分區(qū)鏈（表）上。查找空閑分區(qū)鏈表第一項檢索完否？m.size>u.size?m.size-u.size≦size?劃出u.size大小的分區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回將該分區(qū)從鏈表中移出繼續(xù)檢索下一個表項YYYNNN空閑狀態(tài)分區(qū)分區(qū)分配流程圖分配內(nèi)存查找空閑分區(qū)鏈表第一項檢索完否？m.s動態(tài)分區(qū)分配算法首次適應(yīng)算法FF要求：空閑分區(qū)鏈以地址遞增的次序鏈接每次從鏈首開始順序查找第一個大小能滿足要求的空閑分區(qū)，然后劃分，余下的空閑分區(qū)仍留在空閑鏈中優(yōu)先利用地址部分，保留高址部分的大空閑區(qū)碎片較多，每次從低址查找要增加查找的開銷

為了將一個新作業(yè)裝入內(nèi)存中，須按照一定的分配算法，從空閑分區(qū)表中選出一分區(qū)給該作業(yè)，接下來將介紹四種傳統(tǒng)的順序式搜索算法：循環(huán)首次適應(yīng)算法：對首次適應(yīng)算法的演變，從上次找到的下一個空閑分區(qū)開始找要求：設(shè)置一個起始查找指針采用循環(huán)查找方式內(nèi)存中的空閑分區(qū)分布更均勻減少了查找空閑分區(qū)始的開銷缺乏大的空閑分區(qū)最佳適應(yīng)算法要求：將所有的空閑分區(qū)按其容量從小到大的順序形成一空閑分區(qū)鏈從鏈首開始查找第一個大小適合的空閑分區(qū)第一次找得的是最佳即最恰好適合的分區(qū)能夠避免“大材小用”同時，空閑分區(qū)每次分配切割留下的剩余部分總是最小的，留下大量的難以利用的碎片回收操作較困難最壞適應(yīng)算法要求：將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈每次分配鏈首的第一個空閑分區(qū)每次利用是最大的分區(qū)，空閑分區(qū)每次分配切割留下的剩余部分總是最大的，避免留下大量的難以利用的碎片查詢開銷非常小但缺乏大空閑分區(qū)動態(tài)分區(qū)分配算法首次適應(yīng)算法FF為了將一個新作業(yè)裝動態(tài)分區(qū)分配算法分配算法比較幾種算法各有利弊，到底哪種最好不能一概而論，而應(yīng)針對具體作業(yè)序列來分析。對于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對這一作業(yè)序列是合適的。對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對該作業(yè)序列是不合適的。動態(tài)分區(qū)分配算法分配算法比較例：有作業(yè)序列：作業(yè)A要求20K；作業(yè)B要求28K，作業(yè)C要求30K。要求畫出系統(tǒng)中空閑區(qū)按照首次適應(yīng)算法，最佳適應(yīng)算法、最壞適應(yīng)算法形成的三種空閑分區(qū)隊列，然后分析哪種算法對該序列是合適的？經(jīng)分析可知：最佳適應(yīng)法對這個作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是不合適的。例：有作業(yè)序列：作業(yè)A要求20K；作業(yè)B要求28K，作業(yè)C要練習(xí)有作業(yè)序列：作業(yè)A要求21K；作業(yè)B要求25K，作業(yè)C要求30K，那種分配算法適合該作業(yè)序列？練習(xí)動態(tài)分區(qū)分配算法基于索引搜索的動態(tài)分區(qū)分配算法由于順序搜索的動態(tài)分區(qū)分配算法比較適用于較小的系統(tǒng)。當系統(tǒng)很大時，為了提高搜索空閑分區(qū)的速度，采用基于索引搜索的動態(tài)分區(qū)分配算法：1.快速適應(yīng)算法2.伙伴系統(tǒng)3.哈希算法動態(tài)分區(qū)分配算法基于索引搜索的動態(tài)分區(qū)分配算法快速適應(yīng)算法又稱為分類搜索算法，是將空閑分區(qū)根據(jù)容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，同時在內(nèi)存中設(shè)立一張管理索引表，其中的每一個索引表項對應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭指針。該算法搜索空閑分區(qū)步驟：1.根據(jù)進程的長度，從索引表中找到能容納它的最小空閑區(qū)鏈表2.從鏈表中取下第一塊進行分配即可。該算法不會對分區(qū)產(chǎn)生分割，因此不會產(chǎn)生碎片，查找效率高。缺點：為進程所分配的分區(qū)或多或少存在內(nèi)存空間的浪費?？焖龠m應(yīng)算法又稱為分類搜索算法，是將空閑分區(qū)根據(jù)容量大小進行伙伴系統(tǒng)該算法規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，通常整個可分配內(nèi)存的大小為2的m次方。將它不斷的劃分，按照分區(qū)的大小進行分類，將相同大小的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)雙向鏈表，形成k個空閑分區(qū)鏈表。算法步驟：當需要為進程分配長度為n的存儲空間：1.首先計算一個i值，使2i-1<n<=2i。2.然后若找到2i大小的空閑分區(qū)鏈表，則分配，否則將查找2i+1鏈表，若找到則把該分區(qū)分為兩個相等的分區(qū)，這兩個分區(qū)稱為一對伙伴，其中一個分區(qū)用于分配，而把另一個分區(qū)加入大小為2i的空閑分區(qū)鏈表中，以此類推2的i+2空閑分區(qū)鏈表的分配?；锇橄到y(tǒng)該算法規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的哈希算法在上述分類搜索算法和伙伴系統(tǒng)算法中，都是將空閑分區(qū)根據(jù)分區(qū)大小進行分類，對于每一類具有相同大小的空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表。在為進程分配空間時，需要在一張管理索引表中查找所需空間大小所對應(yīng)的表項，來找到一個空閑分區(qū)。這里面臨一個問題，如果空閑分區(qū)分類較細，則相應(yīng)的索引表項較多，那么會顯著增加搜索索引表的表項的時間開銷。為了解決這個問題，提出了哈希算法。哈希算法在上述分類搜索算法和伙伴系統(tǒng)算法中，都是將空閑分區(qū)根哈希算法哈希算法：利用哈?？焖俨檎业膬?yōu)點，以及空閑分區(qū)在可利用空閑區(qū)表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每個表項記錄了一個對應(yīng)的空閑分區(qū)鏈表表頭指針。當進行空閑分區(qū)分配時，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計算，即得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實現(xiàn)最佳分配策略。哈希算法哈希算法：利用哈希快速查找的優(yōu)點，以及空閑分區(qū)在可利分區(qū)分配操作回收內(nèi)存回收區(qū)與插入點的前一個空閑分區(qū)相鄰接回收區(qū)與插入點的后一個空閑分區(qū)相鄰接；回收區(qū)與插入點的前后兩個空閑分區(qū)相鄰接；回收區(qū)不與任何一個空閑分區(qū)相鄰接；回收區(qū)F1……回收區(qū)F2……回收區(qū)F1F2……分區(qū)分配操作回收內(nèi)存回收區(qū)F1……回收區(qū)F2……回收區(qū)F1F可重定位分區(qū)分配動態(tài)重定位的引入隨著系統(tǒng)接收的作業(yè)的增加，內(nèi)存中連續(xù)的大塊分區(qū)不復(fù)存在，產(chǎn)生了大量的“碎片”。新的作業(yè)無法裝入到每個“碎片”小分區(qū)上運行，但所有碎片的空間總和可能大于需求。通過“拼接”/“緊湊”/“緊縮”/“”澄清“來實現(xiàn)——”程序的浮動“/”

動態(tài)重定位“。OS區(qū)Job2Job4Job3Job1Job5Job6Job7“零頭”碎片OS區(qū)Job2Job4Job3Job1Job5Job6Job7OS區(qū)Job2Job4Job3Job1Job5Job6Job7“零頭”碎片緊湊可重定位分區(qū)分配動態(tài)重定位的引入OS區(qū)Job4Job3Job可重定位分區(qū)分配動態(tài)重定位的實現(xiàn)由于動態(tài)運行時裝入方式是將相對地址轉(zhuǎn)換為絕對地址的工作推遲到程序指令要真正執(zhí)行時進行，為使地址轉(zhuǎn)換不影響到指令的執(zhí)行速度，需要有硬件地址變換機構(gòu)的支持，即需在系統(tǒng)中增設(shè)一個重定位寄存器，用它來存放程序在內(nèi)存中的起始地址。程序運行時，真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而形成的。動態(tài)重定位：地址變換過程是在程序執(zhí)行期間，隨著每條指令或數(shù)據(jù)的訪問自動進行的，故稱為。處理機一側(cè)存儲器一側(cè)作業(yè)J

內(nèi)存365LOAD1,2500500025001000365LOAD1,2500150001250010000110002500相對地址10000重定位寄存器可重定位分區(qū)分配動態(tài)重定位的實現(xiàn)365LOAD1,2500優(yōu)缺點分析優(yōu)點：消除了“碎片”，提高了內(nèi)存利用率，同時提高了系統(tǒng)效率。缺點：需要動態(tài)重定位“硬件”機構(gòu)支持，增加了系統(tǒng)成本，并輕度降低了程序執(zhí)行速度，“緊湊”處理增加了系統(tǒng)開銷?？芍囟ㄎ环謪^(qū)分配算法動態(tài)重定位分區(qū)分配算法流程查找空閑分區(qū)鏈表找到可用分區(qū)？按動態(tài)分區(qū)方式進行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首址進行緊湊形成連續(xù)空閑區(qū)YYNN請求分配u.size分區(qū)空閑分區(qū)總和≥？修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)無法分配返回可重定位分區(qū)分配算法查找空閑分區(qū)鏈表找到可用分區(qū)？按動態(tài)分區(qū)對換（Swapping）早期，在單用戶分時系統(tǒng)中出現(xiàn)的對換技術(shù)為：系統(tǒng)把所有的用戶作業(yè)存放在磁盤上，每次只能調(diào)入一個作業(yè)進入內(nèi)存，當該作業(yè)的一個時間片用完時，將它調(diào)至外存的后備隊列上等待，再從后備隊列上將另一個作業(yè)調(diào)入內(nèi)存。多道環(huán)境下存在的問題：1.內(nèi)存中大量的進程因事件未發(fā)生而被阻塞，但卻占用了大量的內(nèi)存空間。2.又存在許多的作業(yè)因內(nèi)存空間的不足，一直駐留在外存上，而不能進入內(nèi)存運行。這些都使得系統(tǒng)的吞吐量下降，造成了系統(tǒng)資源的浪費，為了解決這個問題，在系統(tǒng)中添加了對換設(shè)施。對換（Swapping）早期，在單用戶分時系統(tǒng)中出現(xiàn)的對換技對換技術(shù)對換技術(shù)（Swapping）:用于解決內(nèi)存不足的問題，改善內(nèi)存利用率，提高系統(tǒng)吞吐量。指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存。對換的類型_根據(jù)每次對換時，所對換的程序或數(shù)據(jù)的數(shù)量，可將對換分為如下兩類：如果對換是以整個進程為單位，便稱之為“整體對換”或“進程對換”，廣泛用于多道程序中，作為處理機中級調(diào)度。如果對換是以進程的一個“頁面”或“分段”為單位進行的，則分別稱之為“頁面對換”或“分段對換”，又稱為“部分對換”。這種對換方法是實現(xiàn)后面將介紹的請求分頁和請求分段式存儲管理的基礎(chǔ)，其目的是為支持虛擬存儲系統(tǒng)。對換技術(shù)對換技術(shù)（Swapping）:用于解決內(nèi)存不足的問題進程對換技術(shù)進程對換技術(shù)（Swapping）對換的時機：創(chuàng)建新進程而內(nèi)存不足時。對換空間的管理：外存分為文件區(qū)和對換區(qū)，前者存放文件，采用離散分配；后者存放換出的進程，采用連續(xù)分配，以提高進程換入、換出的對換速度。對換區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)：記錄外存中對換區(qū)的空閑盤塊的使用情況，使用空閑分區(qū)表－－包括對換區(qū)的首址及其大小分別用盤塊號和盤塊數(shù)表示。對換空間的分配與回收對換分區(qū)的分配：連續(xù)分配方式，因而對換空間的分配與回收與動態(tài)分區(qū)分配雷同。其分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法。對換區(qū)的回收可分為：1.回收分區(qū)與插入點的前一個空閑分區(qū)F1相鄰接；2.回收分區(qū)與插入點的后一個空閑分區(qū)F2相鄰接；3.回收分區(qū)同時與插入點的前、后兩個分區(qū)鄰接；4.回收分區(qū)既不與F1鄰接，又不與F2鄰接。進程對換技術(shù)進程對換技術(shù)（Swapping）進程對換技術(shù)（Swapping）當一進程由于創(chuàng)建子進程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間時，便調(diào)用對換進程。進程的換出：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，申請對換空間，然后啟動磁盤，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上，并回收該進程占用的內(nèi)存空間，修改該進程的PCB。進程的換入：找出“就緒”狀態(tài)但已換出的進程，將其中換出時間最久的進程作為換入進程，將之換入，直至無可換入的進程或無可換出的進程或無足夠內(nèi)存換入進程為止，此時對換進程才停止。進程對換技術(shù)（Swapping）第五節(jié)

基本分頁存儲管理方式

由于采用連續(xù)分配方式會形成很多的碎片，雖然可以使用緊湊方法改善但開銷太大，于是促使人們產(chǎn)生了分散分配方式的思想（如果將一個進程直接分散地裝入到許多不相鄰接的分區(qū)中，便可充分地利用內(nèi)存空間）。根據(jù)離散分配時，所分配地址空間的單位不同，可將離散分配分為三種：1.分頁存儲管理方式。

2.分段存儲管理方式。3.段頁式存儲管理方式。頁面與頁表地址變換機構(gòu)兩級和多級頁表基本分頁的特點第五節(jié)

基本分頁存儲管理方式由于采用連續(xù)頁面與頁表頁面頁面：分頁存儲管理將進程的邏輯地址分成若干個頁并且按照順序編號。物理塊：相應(yīng)把內(nèi)存的物理地址空間分為若干個塊加以編號。頁面大?。哼x擇適當?shù)捻撁娲笮　话銥?n

范圍：1KB~8KB分散分配方法：將程序劃分成多個頁并且分別裝入到多個可以不相鄰接的物理塊中。分頁地址的地址結(jié)構(gòu)（對特定機器固定）

邏輯地址

物理地址頁內(nèi)地址：0-11，即頁面大小為4K,頁號P：12-31,即地址空間1M個頁若給定一個邏輯地址空間中的地址為A,頁面大小為L,則頁號和頁內(nèi)地址？頁表數(shù)據(jù)結(jié)構(gòu)：頁號、塊號、存取控制項頁表的作用：實現(xiàn)從頁號到物理塊號的地址映射。頁號P位移量W物理塊號P頁內(nèi)地址d頁面與頁表頁面頁號P位移量W物理塊號P頁內(nèi)地址d頁面與頁表頁面頁面和物理塊（頁框/架）：順序編號，頁內(nèi)碎片頁面大?。?nBytes一般在：512B~8/32K地址結(jié)構(gòu)

邏輯地址

物理地址頁表數(shù)據(jù)結(jié)構(gòu)：頁號、塊號、存取控制項頁表的作用：實現(xiàn)從頁號到物理塊號的地址映射。頁號P位移量W物理塊號P頁內(nèi)地址d01234567891110內(nèi)存第0頁第1頁第2頁第3頁第4頁第5頁第6頁用戶作業(yè)塊號頁號1051169453327120頁表01234567891110內(nèi)存第0頁第1頁第2頁第3頁第4頁第5頁第6頁用戶作業(yè)02K-1第2頁（頁長2K）02K-14號頁架（頁長2K）第0頁第1頁第2頁第3頁第4頁第5頁第6頁第0頁第1頁第2頁第3頁第4頁第5頁第6頁邏輯地址空間頁面與頁表頁面頁號P位移量W物理塊號P頁內(nèi)地址d012345地址變換機構(gòu)為了將用戶地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中的物理地址，在系統(tǒng)中必須設(shè)置地址變換機構(gòu)。將邏輯地址中的頁號轉(zhuǎn)變?yōu)閮?nèi)存中的物理塊號，需借助于頁表?；镜牡刂纷儞Q機構(gòu)頁表存放在內(nèi)存系統(tǒng)區(qū)的一個連續(xù)空間中；PCB和頁表寄存器PTR中存有頁表的首地址；查詢頁表：頁表首地址+頁號x表項長度；地址映射——從邏輯地址到物理地址的變換過程。具有快表的地址變換機構(gòu)聯(lián)想寄存器——并行查詢；空間大?。簬譑到幾百K，部分表項（16~512個）；快表與頁表同時訪問；地址映射過程。頁表始址頁表長度頁表寄存器﹥頁表塊號頁號5332712052018物理地址32018邏輯地址越界中斷頁表始址頁表長度頁表寄存器﹥頁表塊號頁號5332712031250物理地址21250邏輯地址越界中斷快表塊號頁號2051145320輸入寄存器分析：

統(tǒng)計表明，從快表中找到所需頁表項的機率達90％以上。同時，考慮到快表的速度是內(nèi)存速度的數(shù)倍或數(shù)十倍，那么相對于內(nèi)存速度，訪問頁表的時間可以忽略不計。也就是說頁地址變換機構(gòu)造成的速度損失達到了可接受的程度。地址變換機構(gòu)為了將用戶地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中的例：設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖。

硬件能自動分離出頁號和頁內(nèi)地址，但我們只能通過計算才能得到。例：設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如兩級和多級頁表兩級頁表解決大頁表占用大的連續(xù)存儲空間的問題；將大頁表進行分頁，讓每個頁面大小與內(nèi)存物理塊大小相同（1024）然后按照離散分配的方式存放在不同的物理塊中。此時也要再建立一個外層頁表用于記錄頁表頁面的物理塊號。若地址空間為32位，頁面大小為4K，一級頁表有1MB的頁表項，二級頁表：外1KB頁表，1KB項邏輯地址結(jié)構(gòu)：

外層頁號（P1）+外層頁內(nèi)地址(P2)+頁內(nèi)地址(d)多級頁表外部頁表塊號頁號321078110110頁表分頁11223120211130……01231121131011……外部頁表外部頁表寄存器物理地址外部頁號P1外部頁內(nèi)地址P2邏輯地址頁內(nèi)地址d…………頁表兩級和多級頁表兩級頁表外部頁表塊號頁號32107811011基本分頁的特點優(yōu)點：存在頁內(nèi)碎片，但碎片相對較小，內(nèi)存利用率較高；實現(xiàn)了離散分配，消除了程序浮動；便于存儲訪問控制，有利于代碼共享?！翱芍厝氪a”——純代碼：執(zhí)行中不可改變。缺點：需要專門的硬件支持，尤其“快表”；內(nèi)存訪問的效率下降。不足：不能實現(xiàn)真正的共享，不支持動態(tài)鏈接。基本分頁的特點優(yōu)點：第六節(jié)

基本分段存儲管理方式基本分段管理思想的引入基本原理地址變換分段與分頁的主要區(qū)別信息共享段頁式存儲管理方式第六節(jié)

基本分段存儲管理方式基本分段管理思想的引入分段存儲管理思想的引入OS由單道向多道系統(tǒng)發(fā)展的同時，其存儲管理方式便由單一連續(xù)分配發(fā)展到固定分區(qū)分配。為了能適應(yīng)不同大小的用戶程序要求，又從固定分區(qū)分配發(fā)展到動態(tài)分區(qū)分配。又為了提高內(nèi)存的利用率，又從連續(xù)分配方式發(fā)展到離散分配方式——分頁存儲管理方式。為了滿足用戶在編程和使用上多方面的要求，又引入了分段存儲管理方式，是當今所有存儲管理方式的基礎(chǔ)。分段存儲管理思想的引入OS由單道向多道系統(tǒng)發(fā)展的同時，其存儲分段存儲管理思想的引入具體地說，分段存儲管理方式符合用戶和程序員如下多方面的需要：方便編程：用戶將作業(yè)按邏輯分段，其中每個邏輯地址都是由段名（段號）和段內(nèi)偏移量（段內(nèi)地址）共同來決定，這不僅可以方便用戶編程，也可以使程序非常直觀：LOAD1，[A]|〈D〉；STORE1，[B]|〈C〉；將分段A中D單元內(nèi)的值讀入寄存器1。將寄存器1中的值存入B分段的C單元中。分段存儲管理思想的引入具體地說，分段存儲管理方式符合用戶和程分段存儲管理思想的引入信息共享：是以信息的邏輯單位（main函數(shù)、子函數(shù)、數(shù)據(jù)等邏輯關(guān)系）為基礎(chǔ)，來實現(xiàn)對程序和數(shù)據(jù)的共享。信息保護：同樣以信息的邏輯單位為基礎(chǔ)，根據(jù)邏輯有效和方便地實現(xiàn)信息保護功能；例如我們希望子函數(shù)A僅允許進程執(zhí)行，不允許讀寫操作，只需在該段上標上只執(zhí)行標志即可。但是在分頁系統(tǒng)中，函數(shù)A可能要占幾個頁面，其中第一頁和最后一頁還會裝有其他程序段的數(shù)據(jù)，這些數(shù)據(jù)又允許進程讀寫，這就很難實現(xiàn)對頁面統(tǒng)一保護。分段存儲管理思想的引入信息共享：是以信息的邏輯單位（main分段存儲管理思想的引入動態(tài)增長：分段存儲管理方法能很好的應(yīng)對數(shù)據(jù)段的動態(tài)增長。動態(tài)鏈接：針對目標模塊運行時動態(tài)鏈接：系統(tǒng)只將真正要運行的目標程序裝入內(nèi)存，首先將主程序和需要用到的目標程序裝入內(nèi)存。這些目標程序和目標模塊都是以邏輯段為單位的，所以分段存儲管理方式非常適合動態(tài)鏈接。分段存儲管理思想的引入動態(tài)增長：分段存儲管理方法能很好的應(yīng)對分段系統(tǒng)的基本原理在分段存儲管理方式中，作業(yè)的地址空間被劃分為若干個段，每段定義了一組邏輯信息，每段都是從0開始編址，并采用一個連續(xù)的地址空間。段的長度由相應(yīng)的邏輯信息組的長度決定，因此各段長度不相等。分段系統(tǒng)中邏輯地址結(jié)構(gòu)：二維地址（段號，段內(nèi)地址）

3116150允許一個作業(yè)由64K個段，一個段的最大長度為64KB段表（段映射表）段號、段基地址（段在內(nèi)存中的起址）、段長等段表寄存器：段表始址和段表長度利用段表實現(xiàn)邏輯段地址到物理地址的映射段號段內(nèi)地址分段系統(tǒng)的基本原理在分段存儲管理方式中，作業(yè)的地址空間被劃分基本原理內(nèi)存第0段第1段第2段第3段用戶作業(yè)段表基址段長150K35K500K9K300K20K100K42K3210段號第0段第1段第2段第3段圖.利用段表實現(xiàn)地址映射基本原理內(nèi)存第0段第1段第2段第3段用戶作業(yè)段表基址段長15地址變換及變換機構(gòu)基本分段管理的地址變換與基本分頁管理的變換機構(gòu)和過程類似。段表寄存器存放段表的起始地址和段表長度；越界訪問控制邏輯地址的段號與段表長度比較；段內(nèi)地址與段表中保存的段長比較；段表始址段表長度段表寄存器﹥153705物理地址段號3105邏輯地址越界中斷段表基址段長150K35K500K9K300K20K100K42K3210段號內(nèi)存地址變換及變換機構(gòu)基本分段管理的地址變換段表始址段表長度段表分段與分頁的主要區(qū)別頁是信息的物理單位，段是信息的邏輯單位，分頁是系統(tǒng)管理的需要，分段是用戶的需要；頁的大小固定，由系統(tǒng)確定；段的大小動態(tài)變化，決定于用戶編程的需要；分頁系統(tǒng)中的邏輯地址空間是一維的，分段系統(tǒng)中的是二維的。分頁系統(tǒng)中不易實現(xiàn)“共享”和“動態(tài)鏈接”，分段則很容易。分段與分頁的主要區(qū)別頁是信息的物理單位，段是信息的邏輯單位，信息共享假設(shè)一個多用戶系統(tǒng)，可同時接納40個用戶，每個用戶都執(zhí)行一個文本編輯程序。如果編輯程序包括160KB編輯代碼區(qū)，40KB數(shù)據(jù)區(qū)，則需要約8MB內(nèi)存空間，若160KB是可重入的，則該代碼能被共享，故就只需（160+40*40）KB內(nèi)存空間。在分頁系統(tǒng)中，假定頁面為4KB，則編輯代碼段劃分為40個頁面，對應(yīng)40個頁表項，數(shù)據(jù)區(qū)劃分為10個頁面，對應(yīng)10個頁表項。1.分頁系統(tǒng)中對程序和數(shù)據(jù)的共享信息共享假設(shè)一個多用戶系統(tǒng)，可同時接納40個用戶，每個用戶都信息共享內(nèi)存段表基址段長180K100K300K20K100K42K210段號第0段Job1數(shù)據(jù)用戶1編輯進程……第0段Job2數(shù)據(jù)用戶2編輯進程……基址段長380K30K300K20K100K42K210段號第0段Job1數(shù)據(jù)……Job2數(shù)據(jù)2.分段系統(tǒng)中程序和數(shù)據(jù)的共享使實現(xiàn)共享變得非常容易信息共享內(nèi)存段表基址段長180K100K300K20K100基本分段的特點優(yōu)點：便于動態(tài)申請內(nèi)存管理和使用統(tǒng)一化便于共享便于動態(tài)鏈接缺點：產(chǎn)生碎片思考：與動態(tài)分區(qū)存儲管理方案的相同點與不同點？基本分段的特點優(yōu)點：段號S段內(nèi)頁號P頁內(nèi)地址W段頁式存儲管理方式基本思想結(jié)合分頁和分段技術(shù)；發(fā)揮出分頁和分段管理方式各自的優(yōu)點。原理對內(nèi)存進行分頁（物理塊/頁架）；對用戶作業(yè)先分段，各段再分頁。地址結(jié)構(gòu)與地址變換段號、段內(nèi)頁號、頁內(nèi)地址三部分段表和頁表主程序段數(shù)據(jù)段子程序段段號S段內(nèi)頁號P頁內(nèi)地址W段頁式存儲管理方式基本思想主程序段段表始址段表長度段表寄存器邏輯地址頁號P頁內(nèi)地址段號S﹥段表塊號塊內(nèi)地址物理地址越界中斷頁表xxxx2xxxx1xxxx0頁表始址段號210頁表始址段號……段表始址段表長度段表13021110頁表始址頁表長度狀態(tài)段號段表寄存器頁表03121110存儲塊號狀態(tài)頁號頁表1110存儲塊號狀態(tài)頁號段號，段內(nèi)頁號，頁內(nèi)地址段表始址段表長度段表寄存器邏輯地址頁號P頁內(nèi)地址段號S﹥段表段頁式存儲管理的特點段頁式存儲管理的優(yōu)缺點同時具備分段和分頁管理的優(yōu)點：分散存儲，內(nèi)存利用率較高；便于代碼或數(shù)據(jù)共享，支持動態(tài)鏈接等。訪問效率下降：一次訪問轉(zhuǎn)換成了三次訪問。1.訪問內(nèi)存中的段表，從中取得頁表始址。2.訪問內(nèi)存中的頁表，從中取出物理塊號并與頁內(nèi)地址一起構(gòu)成數(shù)據(jù)的物理地址。3.根據(jù)物理地址從內(nèi)存中取出數(shù)據(jù)。通過在地址變換機構(gòu)中增設(shè)一個高速緩沖寄存器來解決速度問題。段頁式存儲管理的特點段頁式存儲管理的優(yōu)缺點第五章

虛擬存儲器_頁面置換算法虛擬存儲器的引入虛擬存儲器的定義物理上不存在，但可以使用（訪問）；允許作業(yè)部分裝入，需要時再臨時裝入所需的部分，直到作業(yè)退出，某些部分也有可能沒被裝入過。虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。第五章

虛擬存儲器_頁面置換算法虛擬存儲器的引入虛擬存儲器的特征離散性：離散存儲多次性一個作業(yè)被分成多次調(diào)入內(nèi)存運行；對換性允許在作業(yè)的運行過程中進行換進、換出；虛擬性能從邏輯上擴充內(nèi)存容量，使用戶“看到”的內(nèi)存容量遠大于實際大小。該特征是以上兩個特征為基礎(chǔ)的。虛擬存儲器的特征離散性：離散存儲內(nèi)存分配策略和分配算法具體的物理塊（頁架）的分配策略固定分配局部置換：進程占據(jù)的內(nèi)存頁架數(shù)不變；缺頁時，只能與該進程在內(nèi)存的頁面置換；由進程類型、程序員或程序管理員確定每個進程分得的物理塊數(shù)但分配時，難于確定某個進程的頁架數(shù)?？勺兎峙淙种脫Q：最易實現(xiàn)，空閑頁架由OS管理－空閑物理塊隊列先為每個進程分配一定的物理塊缺頁時，由系統(tǒng)從空閑物理塊隊列中取一塊當空閑物理塊完時，便與內(nèi)存中的一頁置換，該頁可能是任一進程中的頁可變分配局部置換根據(jù)進程類型或程序員的要求，為每個進程先分配一定數(shù)目的物理塊缺頁時，只與該進程在內(nèi)存的一頁置換當進程缺頁率較高或較低時，能由OS對其占據(jù)的頁架數(shù)加以調(diào)整內(nèi)存分配策略和分配算法具體的物理塊（頁架）的分配策略可變分配內(nèi)存分配策略和分配算法物理塊的分配算法平均分配算法將系統(tǒng)中所有可供分配的頁架，平均分配給各個進程。按比例分配算法根據(jù)進程的大小按比例分配頁架的算法?？紤]優(yōu)先權(quán)的分配算法優(yōu)先權(quán)高的一次分得的頁架數(shù)多。內(nèi)存分配策略和分配算法物理塊的分配算法調(diào)頁策略何時調(diào)入頁面的問題預(yù)調(diào)頁策略：通常運用于首次調(diào)入內(nèi)存時預(yù)先調(diào)入若干個預(yù)計在不久后將執(zhí)行的頁面預(yù)測不準：約為50％請求調(diào)頁策略：進程運行中發(fā)生缺頁現(xiàn)象時每次僅調(diào)入一頁，系統(tǒng)開銷大，增加了磁盤I/O的啟動頻率從何處調(diào)入頁面的問題外存分為：“文件區(qū)”和“對換區(qū)”系統(tǒng)有足夠的對換空間：進程的所有文件都從文件區(qū)復(fù)制到對換區(qū)系統(tǒng)缺少足夠?qū)Q空間：不被修改的文件始終直接從文件區(qū)調(diào)入；可能被修改的部分在換出時須調(diào)到對換區(qū)，以后需要時均從對換區(qū)調(diào)入UNIX方式：第一次運行到的頁面都從文件區(qū)調(diào)入，被換出的頁面放在對換區(qū)，下次調(diào)入就從對換區(qū)調(diào)入，對于已在內(nèi)存的共享頁面無須調(diào)入頁面的調(diào)入過程響應(yīng)缺頁中斷→保存CPU環(huán)境→查找頁表（快表）→得到該頁在外存中的塊號→啟動磁盤IO讀入；如果內(nèi)存已滿，先置換，再調(diào)入；最后修改頁表（快表）對應(yīng)項的內(nèi)容。調(diào)頁策略何時調(diào)入頁面的問題從何處調(diào)入頁面的問題頁面的調(diào)入過程第七節(jié)

頁面置換算法最佳置換算法先進先出FIFO算法最近最久未使用（LRU）置換算法最少使用（LFU）置換算法頁面緩沖置換算法第七節(jié)

頁面置換算法最佳置換算法頁面置換算法在進程運行過程中，若其所要訪問的頁面不在內(nèi)存，但內(nèi)存已無空閑空間時，為保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送到磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。一個好的頁面置換算法應(yīng)具有較低的頁面更換頻率。頁面置換算法在進程運行過程中，若其所要訪問的頁面不在內(nèi)存，但最佳置換（OPT）算法選擇以后永遠（相比之下，最長時間）不會被使用的頁淘汰出去。特點：理論上，性能最佳；實際上，無法實現(xiàn)；通常只用在研究其它算法時，做參考評價。最佳置換（OPT）算法選擇以后永遠（相比之下，最長時間）不會例假定系統(tǒng)未某進程分配了三個物理塊號，有以下的頁面號引用串（為了簡便起見，假設(shè)采用的是最佳置換算法策略）70120304230321201701777220000113缺頁中斷9次，置換6次例假定系統(tǒng)未某進程分配了三個物理塊號，有以下的頁面號引用串（先進先出FIFO選擇最先進入系統(tǒng)的頁淘汰出去特點：實現(xiàn)簡單與進程實際的運行不相適應(yīng)先進先出FIFO選擇最先進入系統(tǒng)的頁淘汰出去例假定系統(tǒng)未某進程分配了三個物理塊號，有以下的頁面號引用串（為了簡便起見，假設(shè)采用的是FIFO先進先出置換策略）頁的位置不表示頁的真實存儲地址，僅為了表示即將淘汰頁的方便70120304230321201701701223701127001缺頁15次，置換12次例假定系統(tǒng)未某進程分配了三個物理塊號，有以下的頁面號引用串（最近最久未使用（LRU）置換算法選擇最近最久未被使用（訪問）的頁淘汰出去。特點：性能較好，實現(xiàn)復(fù)雜，需要硬件支持（每頁配置一個寄存器、棧），增加系統(tǒng)負擔。最近最久未使用（LRU）置換算法選擇最近最久未被使用（訪問）LRU的硬件支持寄存器系統(tǒng)為每頁設(shè)置一個移位寄存器R，每當訪問這一頁時，將該頁對應(yīng)的寄存器R最高位置1，以后每個時間間隔將所有的R右移一位，當淘汰一頁時就選擇R值最小的頁。也就是說R值越小，其對應(yīng)的頁就是最久未使用的頁。顯然，R的位數(shù)越多越精確。但系統(tǒng)硬件成本也就越高。棧設(shè)置一個特殊的棧保存當前使用的各個頁面的頁面號；當一個頁面被訪問時，首先檢查棧中是否有與剛壓入棧頂?shù)捻撎栂嗤?，若有，則從棧中抽出；最后就將它的頁號壓入棧頂。這樣可保證棧中無相同的頁號。當系統(tǒng)要淘汰一頁時，總是從棧底取出一個頁號淘汰，即淘汰的頁是最久未使用的。LRU的硬件支持寄存器棧例假定系統(tǒng)為某進程分配了三個物理塊號，有以下的頁面號引用串（為了簡便起見，假設(shè)采用的是最近最久未使用LRU策略）70120304230321201701701237010702

棧缺頁12次，置換9次例假定系統(tǒng)為某進程分配了三個物理塊號，有以下的頁面號引用串（例某程序在內(nèi)存中分配三個塊，訪問頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、LRU、OPT算法分別計算缺頁次數(shù)，置換次數(shù)？假設(shè)開始時所有頁均不在內(nèi)存例某程序在內(nèi)存中分配三個塊，訪問頁的走向為4，3，2，1，4FIFO4，3，2，1，4，3，5，4，3，2，1，5432143555211432143335224321444355缺頁9次，置換6次FIFO4，3，2，1，4，3，5，4，3，2，LRU4，3，2，1，4，3，5，4，3，2，1，5432143543215432143543214321435432缺頁10次，置換7次LRU4，3，2，1，4，3，5，4，3，2，1OPT4，3，2，1，4，3，5，4，3，2，1，5444444444222333333333112111555555缺頁7次，置換4次OPT4，3，2，1，4，3，5，4，3，2，1練習(xí)

某程序在內(nèi)存中分配4個塊，訪問頁的順序為4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分別計算缺頁次數(shù)，置換次數(shù)？假設(shè)開始時所有頁均不在內(nèi)存練習(xí) 某程序在內(nèi)存中分配4個塊，訪問頁的順序為4，3，2，1LRU4，3，2，1，4，3，5，4，3，2，1，5432143543215432143543214321435432432111543缺頁中斷8次LRU4，3，2，1，4，3，5，4，3，2，1，54321OPT4，3，2，1，4，3，5，4，3，2，1，5444444444411333333333332222222222111555555缺頁中斷6次OPT4，3，2，1，4，3，5，4，3，2，1，54444FIFO置換算法的異常

有一虛擬存儲系統(tǒng)，采用先進先出的頁面淘汰算法。在內(nèi)存中為每個進程分配3塊。進程執(zhí)行時使用頁號的順序為432143543215(1)

該進程運行時總共出現(xiàn)幾次缺頁。(2)

若每個進程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。FIFO置換算法的異常 有一虛擬存儲系統(tǒng)，采用先進先出的頁面M=34，3，2，1，4，3，5，4，3，2，1，5432143555211432143335224321444355缺頁9次，置換6次M=34，3，2，1，4，3，5，4，3，2，1M=44，3，2，1，4，3，5，4，3，2，1，5432111543215432221543214333215432444321543缺頁10次，置換6次FIFO頁面淘汰算法會產(chǎn)生異?，F(xiàn)象（Belady現(xiàn)象），即：當分配給進程的物理頁面數(shù)增加時，缺頁次數(shù)反而增加M=44，3，2，1，4，3，5，4，3，2，1，54321影響缺頁次數(shù)的因素分配給進程的物理塊數(shù)頁面的大小編程方法頁面置換算法影響缺頁次數(shù)的因素分配給進程的物理塊數(shù)例內(nèi)存分配一物理塊，初始時矩陣數(shù)據(jù)均不在內(nèi)存；頁面大小為128個整數(shù)；矩陣A128X128按行存放。下面兩個程序執(zhí)行時訪問數(shù)據(jù)將分別會產(chǎn)生多少次缺頁中斷？程序1：forj:=1to128fori:=1to128A[i,j]:=0;程序2：fo