第四章 存儲(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ǔ)管理方式

存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，操作系統(tǒng)中的存儲(chǔ)管理是指對(duì)內(nèi)存的管理，它是操作系統(tǒng)的重要功能之一。充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲(chǔ)基礎(chǔ)盡可能方便用戶使用自動(dòng)裝入用戶程序用戶程序中不必考慮硬件細(xì)節(jié)系統(tǒng)能夠解決程序空間比實(shí)際內(nèi)存空間大的問題存儲(chǔ)器管理的目的：程序的長(zhǎng)度在執(zhí)行時(shí)可以動(dòng)態(tài)伸縮內(nèi)存存取速度快存儲(chǔ)保護(hù)與安全共享與通信及時(shí)了解有關(guān)資源的使用狀況實(shí)現(xiàn)的性能和代價(jià)要合理內(nèi)存空間的管理、分配與回收內(nèi)存共享--代碼共享，數(shù)據(jù)共享通過代碼共享節(jié)省內(nèi)存空間，提高內(nèi)存利用率通過數(shù)據(jù)共享實(shí)現(xiàn)進(jìn)程通信存儲(chǔ)保護(hù)防止地址越界防止操作越權(quán)擴(kuò)充內(nèi)存容量

用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來“擴(kuò)充”內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間，通過虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn)地址映射（重定位）存儲(chǔ)器管理的功能：存儲(chǔ)系統(tǒng)設(shè)計(jì)三個(gè)問題：容量、速度和成本容量：需求無止境速度：能匹配處理器的速度成本問題：成本和其它部件相比應(yīng)在合適范圍之內(nèi)解決方案：采用層次化的存儲(chǔ)體系結(jié)構(gòu)當(dāng)沿著層次下降時(shí)每比特的價(jià)格將下降，容量將增大速度將變慢，處理器的訪問頻率也將下降4.1存儲(chǔ)器的層次結(jié)構(gòu)4.1.1多級(jí)存儲(chǔ)器結(jié)構(gòu)容量愈來愈大訪問數(shù)據(jù)的速度愈來愈慢價(jià)格愈來愈便宜寄存器高速緩存主存磁盤緩存磁盤可移動(dòng)存儲(chǔ)介質(zhì)CPU寄存器主存輔存提高存儲(chǔ)系統(tǒng)效能關(guān)鍵點(diǎn)：程序存儲(chǔ)訪問局部性原理程序執(zhí)行時(shí)，有很多的循環(huán)和子程序調(diào)用，一旦進(jìn)入這樣的程序段，就會(huì)重復(fù)存取相同的指令集合對(duì)數(shù)據(jù)存取也有局部性，在較短的時(shí)間內(nèi)，穩(wěn)定地保持在一個(gè)存儲(chǔ)器的局部區(qū)域,處理器主要和存儲(chǔ)器的局部打交道,在經(jīng)過一段時(shí)間以后，使用的代碼和數(shù)據(jù)集合會(huì)改變?cè)O(shè)計(jì)多級(jí)存儲(chǔ)的體系結(jié)構(gòu)原則：訪問級(jí)別較低存儲(chǔ)器比率小于級(jí)別較高存儲(chǔ)器比率例：假設(shè)兩級(jí)存儲(chǔ)器： 第I級(jí)包含1KB，存取時(shí)間為0.1μs 第II級(jí)包含1MB，存取時(shí)間為1μs存取I級(jí)中的內(nèi)容，直接存取存取II級(jí)，首先被轉(zhuǎn)移到I級(jí)，然后再存取假設(shè)確定內(nèi)容所在位置時(shí)間可以忽略若在I級(jí)存儲(chǔ)器中發(fā)現(xiàn)存取對(duì)象的概率是95%，則平均訪問時(shí)間為：結(jié)果非常接近I級(jí)存儲(chǔ)的存取時(shí)間存儲(chǔ)保護(hù)設(shè)施對(duì)主存中的信息加以嚴(yán)格的保護(hù)，使操作系統(tǒng)及其它程序不被破壞，是其正確運(yùn)行的基本條件之一.

問題：多個(gè)程序同時(shí)在同一臺(tái)機(jī)器上運(yùn)行怎樣才能互不侵犯？為了保證軟件程序只影響程序的內(nèi)部硬件可提供如下功能：界地址寄存器（界限寄存器）存儲(chǔ)鍵1.界地址寄存器（界限寄存器）在CPU中設(shè)置一對(duì)界限寄存器來存放該用戶作業(yè)在主存中的下限和上限地址每當(dāng)CPU要訪問主存，硬件自動(dòng)將被訪問的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否越界如果未越界，則按此地址訪問主存，否則將產(chǎn)生程序中斷——越界中斷（存儲(chǔ)保護(hù)中斷）10005000OSUser1

Jump6000User2將6000與上限地址5000比較，越界則越界中斷10006000下界上界2.存儲(chǔ)鍵每個(gè)存儲(chǔ)塊有一個(gè)由二進(jìn)位組成的存儲(chǔ)保護(hù)鍵一用戶作業(yè)被允許進(jìn)入主存，OS分給它一個(gè)唯一的存儲(chǔ)鍵號(hào)并將分配給該作業(yè)各存儲(chǔ)塊存儲(chǔ)鍵也置成同樣鍵號(hào)當(dāng)OS挑選該作業(yè)運(yùn)行時(shí)，OS將它的存儲(chǔ)鍵號(hào)放入程序狀態(tài)字PSW存儲(chǔ)鍵（“鑰匙”）域中每當(dāng)CPU訪問主存時(shí)，都將該主存塊的存儲(chǔ)鍵與PSW中的“鑰匙”進(jìn)行比較A塊B塊C塊001010100101000存儲(chǔ)鍵取保護(hù)位0－不保護(hù)1－保護(hù)…………001007鑰

Key11只要鍵匹配，存取均可鍵不匹配，則不可存是否可取要看保護(hù)位舉例：存A，取A，均可以(鍵Key匹配)存B，取B，均不可以(鍵不匹配，且取保護(hù))存C，不可以(鍵不匹配)

取C，可以，因取保護(hù)位為0，即不保護(hù)取程序狀態(tài)字4.1程序的裝入和鏈接

在多道程序環(huán)境下，要使程序運(yùn)行，必須創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程第一件事就是將程序和數(shù)據(jù)裝入內(nèi)存。一個(gè)用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程序，通常要進(jìn)行以下處理：（1）編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個(gè)目標(biāo)模塊；（2）鏈接：由鏈接程序?qū)⒛繕?biāo)模塊和相應(yīng)的庫(kù)函數(shù)鏈接成裝入模塊；（3）裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。庫(kù)目標(biāo)程序塊1目標(biāo)程序塊2第一步鏈接程序裝入模塊第二步裝入程序第三步用戶源程序編譯程序……內(nèi)存1.絕對(duì)裝入方式如果在編譯時(shí)，事先知用戶程序在內(nèi)存的駐留位置，則編譯程序在編譯時(shí)就產(chǎn)生絕對(duì)地址的目標(biāo)代碼。裝入程序就直接把裝入模塊中的程序和數(shù)據(jù)裝入到指定的位置，（不需進(jìn)行地址轉(zhuǎn)換）。程序中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出，也可由程序員直接賦予。但在由程序員直接給出絕對(duì)地址時(shí)，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)，再將這些符號(hào)地址轉(zhuǎn)換為絕對(duì)地址。

4.2.1程序的裝入1.名空間、地址空間和存儲(chǔ)空間在我們用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫程序時(shí)，總是通過符號(hào)名來訪問某一單元。我們把程序中由符號(hào)名組成的空間稱為名空間。源程序經(jīng)過匯編或編譯形成的程序，通常是以0為基址進(jìn)行順序編址，這樣的地址表示形式稱為相對(duì)地址,也叫做邏輯地址或虛地址，把該程序邏輯地址組成的集合叫做程序的邏輯地址空間(簡(jiǎn)稱地址空間)。存儲(chǔ)器中每個(gè)具體存儲(chǔ)單元都有不同的編號(hào)，每個(gè)編號(hào)就是一個(gè)物理地址，整個(gè)程序在內(nèi)存中存儲(chǔ)后所占用的物理地址的集合形成程序的物理地址空間(簡(jiǎn)稱存儲(chǔ)空間)。2.重定位（地址映射）裝入方式名空間、地址空間和存儲(chǔ)空間的關(guān)系GotoL1L1：…源程序編譯Goto2…目標(biāo)代碼0123名空間地址空間裝入Gotoa＋2…內(nèi)存(運(yùn)行程序)aa＋1存儲(chǔ)空間…a＋22.地址映射邏輯地址是一個(gè)“虛”的概念，處理機(jī)不能直接訪問邏輯地址，而物理地址則是“實(shí)”的。因而，操作系統(tǒng)必須提供這樣的功能，把程序執(zhí)行時(shí)要訪問的地址空間中的邏輯地址變換成內(nèi)存空間中對(duì)應(yīng)的物理地址。這種把虛地址變換成實(shí)地址的過程稱作地址映射。若用A表示地址空間，用M表示內(nèi)存空間，則地址映射可表示成：f：Ａ→Ｍ(1)靜態(tài)映射：當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。由重定位

裝入程序完成，它把分配給目標(biāo)程序的內(nèi)存區(qū)的起始地址B作為基地址，在把該程序裝入指定內(nèi)存區(qū)的同時(shí)，將程序中的所有邏輯地址翻譯成相對(duì)于基地址B的物理地址，即ｆ（ａ）＝Ｂ＋ａ優(yōu)點(diǎn):容易實(shí)現(xiàn)，無需硬件支持，地址重定位由專門設(shè)計(jì)的程序來完成。在早期的操作系統(tǒng)中大多數(shù)都采用這種方法。缺點(diǎn):程序經(jīng)地址重定位后就不能移動(dòng)了，因而不能重新分配內(nèi)存，不利于內(nèi)存的有效利用。

0：B=10000

100：

LOAD1，2500

10100：

LOAD1，12500

2500：

365

12500：

365

2600：12600：

邏輯地址空間物理地址空間例如：LOAD1，2500這條指令是把相對(duì)地址為2500的存儲(chǔ)單元的內(nèi)容365裝入1號(hào)累加器。而這時(shí)內(nèi)容為365的存儲(chǔ)單元的實(shí)際物理地址為12500（起始地址10000+相對(duì)地址2500），所以LOAD1，2500這條指令中的直接地址碼要作相應(yīng)的修改，即改為L(zhǎng)OAD1，12500。

(2)動(dòng)態(tài)映射：指在程序執(zhí)行過程中進(jìn)行地址重定位，即在每次訪問內(nèi)存單元前才進(jìn)行地址變換。動(dòng)態(tài)重定位可使程序不加任何修改就裝入內(nèi)存，但是它需要硬件—重定位寄存器的支持。對(duì)每一個(gè)有效地址都要加上重定位寄存器中的內(nèi)容，以形成絕對(duì)地址。優(yōu)點(diǎn):程序在內(nèi)存中的搬移不會(huì)對(duì)程序的正確執(zhí)行造成影響，使內(nèi)存得以被充分利用。缺點(diǎn):需要附加的硬件支持，實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比較復(fù)雜。03456......LOAD1200......0100200300.........LOAD12003456邏輯地址空間110012001300物理地址空間200有效地址+1000BR10004.2.2程序的鏈接一種事先鏈接方式，即在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝入模塊(執(zhí)行文件)，以后不再拆開。實(shí)現(xiàn)靜態(tài)鏈接應(yīng)解決:1）相對(duì)地址的修改2）變換外部調(diào)用符號(hào)存在問題：1）不便于對(duì)目標(biāo)模塊的修改和更新。2）無法實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。模塊ACALLB;RETURN;模塊BCALLC;RETURN;模塊CRETURN;0L-10M-10N-1目標(biāo)模塊0L-1LL+M-1L+ML+M+N-1模塊CReturn；模塊BJSR“L+M”Return；模塊AJSR“L”Return；裝入模塊1.靜態(tài)鏈接方式指將一組目標(biāo)模塊在裝入內(nèi)存時(shí)，邊裝入邊鏈接的方式。具有便于修改和更新、便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。存在問題：

由于程序運(yùn)行所有可能用的目標(biāo)模塊在裝入時(shí)均全部鏈接在一起，所以將會(huì)把一些不會(huì)運(yùn)行的目標(biāo)模塊也鏈接進(jìn)去。如程序中的錯(cuò)誤處理模塊。2.裝入時(shí)動(dòng)態(tài)鏈接方式在程序運(yùn)行中需要某些目標(biāo)模塊時(shí)，才對(duì)它們進(jìn)行鏈接的方式。具有高效且節(jié)省內(nèi)存空間的優(yōu)點(diǎn)。3.運(yùn)行時(shí)動(dòng)態(tài)鏈接方式單一用戶(連續(xù))分配是一種簡(jiǎn)單的存儲(chǔ)分配方案，主要用于單用戶單任務(wù)操作系統(tǒng)。它的實(shí)現(xiàn)方案如下：(1)內(nèi)存分配：整個(gè)內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)。系統(tǒng)區(qū)是操作系統(tǒng)專用區(qū)，不允許用戶程序直接訪問，一道用戶程序獨(dú)占用戶區(qū).

4.3.1單一用戶存儲(chǔ)管理方案注意:我們所涉及的內(nèi)存分配與回收一般都指用戶區(qū)的分配與回收。進(jìn)程1OS系統(tǒng)區(qū)用戶區(qū)4.3連續(xù)分配方式地址錯(cuò)界限寄存器重定位寄存器(基址)CPU<內(nèi)存邏輯地址YN物理地址+(3)內(nèi)存保護(hù)：通過基址寄存器保證用戶程序不會(huì)從系統(tǒng)區(qū)開始；另外系統(tǒng)需要一個(gè)界限寄存器，里邊存儲(chǔ)程序邏輯地址范圍，若需要進(jìn)行映射的邏輯地址超過了界限寄存器中的值，則產(chǎn)生一個(gè)越界中斷信號(hào)。(2)地址映射：物理地址=用戶區(qū)基地址+邏輯地址。單一連續(xù)分配方案的優(yōu)點(diǎn)是方法簡(jiǎn)單，易于實(shí)現(xiàn)；缺點(diǎn)是它僅適用于單道程序，因而不能使處理機(jī)和內(nèi)存得到充分利用。例：一個(gè)容量為256KB的內(nèi)存，操作系統(tǒng)占用32KB，剩下224KB全部分配給用戶作業(yè)，如果一個(gè)作業(yè)僅需64KB，那么就有160KB的存儲(chǔ)空間被浪費(fèi)。操作系統(tǒng)作業(yè)0KB32KB96KB256KB-1分配給用戶的空間4.3.2固定分區(qū)分配作業(yè)裝入之前，內(nèi)存就被劃分成若干個(gè)分區(qū)。劃分工作可以由系統(tǒng)管理員完成或由操作系統(tǒng)實(shí)現(xiàn)。一旦劃分完成，在系統(tǒng)運(yùn)行期間不再重新劃分，即分區(qū)的個(gè)數(shù)不可變，分區(qū)的大小不可變，且每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)。可將內(nèi)存的用戶區(qū)域劃分成大小相等或不等的分區(qū)。分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)行（處理多個(gè)類型相同的對(duì)象）。分區(qū)大小不等：多個(gè)小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。系統(tǒng)有一張分區(qū)說明表，每個(gè)表目說明一個(gè)分區(qū)的大小、起始地址和是否已分配的使用標(biāo)志。

固定分區(qū)示例例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)（單位字節(jié)）情況如圖所示，現(xiàn)有大小為1K、9K、33K、121K的多個(gè)作業(yè)要求進(jìn)入內(nèi)存，試畫出它們進(jìn)入內(nèi)存后的空間分配情況，并說明主存浪費(fèi)多大？10k20k28k60k180k511k234內(nèi)存分區(qū)圖OS區(qū)號(hào)大小起址狀態(tài)18k20k未分配232k28k未分配3120k60k未分配4331k180k未分配分區(qū)說明表區(qū)號(hào)大小起址狀態(tài)18k20k已分配232k28k已分配3120k60k已分配4331k180k已分配（2）分區(qū)說明表(3)主存浪費(fèi)空間=(8-1)+(32-9)+(120-33)+(331-121)=7+23+87+210=327(k)解：根據(jù)分區(qū)說明表，將4個(gè)分區(qū)依次分配給4個(gè)作業(yè)，同時(shí)修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示：0k20k28k60k180k511k23(1)內(nèi)存分配圖1K9K33K121K4.3.3動(dòng)態(tài)（可變）分區(qū)分配作業(yè)裝入內(nèi)存時(shí)，從可用的內(nèi)存中劃出一塊連續(xù)的區(qū)域分配給它，且分區(qū)大小正好等于該作業(yè)的大小。可變式分區(qū)中分區(qū)的大小和分區(qū)的個(gè)數(shù)都是可變的，而且是根據(jù)作業(yè)的大小和多少動(dòng)態(tài)地劃分。在分配時(shí)，首先找到一個(gè)足夠大的空閑分區(qū)，即這個(gè)空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個(gè)空閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑區(qū)。在回收撤除作業(yè)所占領(lǐng)的分區(qū)時(shí)，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相領(lǐng)接，若是，則加以合并，使之成為一個(gè)連續(xù)的大空間。常用的數(shù)據(jù)結(jié)構(gòu)有內(nèi)存分配表（由已分配區(qū)表和空閑區(qū)表組成）和空閑分區(qū)鏈兩種。0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空J(rèn)1J2J3J40K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配98K12K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98KJ1J2J3J4J5J6可變分區(qū)示例2.分區(qū)分配算法為了將一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)表（鏈）中選出一個(gè)滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個(gè)空閑分區(qū)的容量比作業(yè)申請(qǐng)的空間要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時(shí)修改空閑分區(qū)表（鏈）中相應(yīng)的信息。目前常用分配算法有：首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法快速適應(yīng)法首次適應(yīng)算法（最先適應(yīng)算法）算法

空閑分區(qū)（鏈）按地址遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí),從空閑分區(qū)表/鏈?zhǔn)组_始順序查找,直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。區(qū)號(hào)大小起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表解：按首次適應(yīng)算法，

申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k，起始地址160K；

申請(qǐng)作業(yè)30k，分配1號(hào)分區(qū)，剩下分區(qū)為2k，起始地址50K；

申請(qǐng)作業(yè)7k，分配2號(hào)分區(qū)，剩下分區(qū)為1k，起始地址59K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。區(qū)號(hào)大小起址12k50k21k59k320k160k4331k180k(2)該算法分配后的空閑分區(qū)表0k20k50k52k59k60k160k180k511k(1)內(nèi)存分配圖首次適應(yīng)算法的特點(diǎn)

優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū),從而保留了高地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區(qū)的開銷。循環(huán)首次適應(yīng)算法算法要求

又稱為下次適應(yīng)算法，由首次適應(yīng)算法演變而來。在為作業(yè)分配內(nèi)存空間時(shí),不再每次從空閑分區(qū)表/鏈?zhǔn)组_始查找,而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找,直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表/鏈中。區(qū)號(hào)大小起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表解：按循環(huán)首次適應(yīng)算法，申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k,起始地址160K；

申請(qǐng)作業(yè)30k，分配4號(hào)分區(qū)，剩下分區(qū)為301k，起始地址210K；申請(qǐng)作業(yè)7k，分配1號(hào)分區(qū)，剩下分區(qū)為25k，起始地址27K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下:例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按循環(huán)首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。區(qū)號(hào)大小起址12k27k21k52k320k160k4131k210k(2)該算法分配后的空閑分區(qū)表算法特點(diǎn)

使存儲(chǔ)空間的利用更加均衡，不致使小的空閑區(qū)集中在存儲(chǔ)區(qū)的一端，但這會(huì)導(dǎo)致缺乏大的空閑分區(qū)。

0k20k27k52k60k160k180k210k511k(1)內(nèi)存分配圖最佳適應(yīng)算法算法要求：

總是把滿足要求的、又是最小的空閑分區(qū)分給作業(yè)。為了加速尋找，空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表/鏈中。例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按最佳適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。區(qū)號(hào)大小起址18k52k232k20k3120k60k4331k180k分配前的空閑分區(qū)表內(nèi)存分區(qū)

0k20k52k60k180k511k2134解：按最佳適應(yīng)算法，分配前的空閑分區(qū)表如上表。

申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k,起始地址160K；

申請(qǐng)作業(yè)30k，分配2號(hào)分區(qū)，剩下分區(qū)為2k，起始地址50K；

申請(qǐng)作業(yè)7k，分配1號(hào)分區(qū)，剩下分區(qū)為1k，起始地址59K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：區(qū)號(hào)大小起址18k52k320k160k232k20k4331k180k作業(yè)100K分配后的空閑分區(qū)表區(qū)號(hào)大小起址22k50k18k52k320k160k4331k180k作業(yè)30K分配后的空閑分區(qū)表區(qū)號(hào)大小起址11k59k22k50k320k160k4331k180k作業(yè)7K分配后的空閑分區(qū)表(2)該算法分配后的空閑分區(qū)表0k20k52k60k180k511k(1)內(nèi)存分配圖50K59K160K180K區(qū)號(hào)大小起址11k59k22k50k320k160k4331k180k算法特點(diǎn)

若存在與作業(yè)大小一致的空閑分區(qū),則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，,從而保留了大的空閑分區(qū),但空閑區(qū)一般不可能正好和它申請(qǐng)的內(nèi)存空間大小一樣,因而將其分割成兩部分時(shí),往往使剩下的空閑區(qū)非常小,從而在存儲(chǔ)器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。最壞適應(yīng)算法算法要求

總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用，空閑分區(qū)表/鏈按容量大小遞減的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個(gè)比之大的空閑分區(qū)為止。剩下的空閑仍留在空閑分區(qū)表/鏈中。區(qū)號(hào)大小起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。區(qū)號(hào)大小起址1231k280k2120k60k332k20k48k52k作業(yè)100K分配后的空閑分區(qū)表區(qū)號(hào)大小起址1201k310k2120k60k332k20k48k52k作業(yè)30K分配后的空閑分區(qū)表區(qū)號(hào)大小起址1194k317k2120k60k332k20k48k52k作業(yè)7K分配后的空閑分區(qū)表解：按最壞適應(yīng)算法，分配前的空閑分區(qū)表如上表。

申請(qǐng)作業(yè)100k，分配1號(hào)分區(qū)，剩下分區(qū)為231k,起始地址280K；

申請(qǐng)作業(yè)30k，分配1號(hào)分區(qū)，剩下分區(qū)為201k，起始地址310K；

申請(qǐng)作業(yè)7k，分配1號(hào)分區(qū)，剩下分區(qū)為194k，起始地址317K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：區(qū)號(hào)大小起址1194k317k2120k60k332k20k48k52k(2)該算法分配后的空閑分區(qū)表30k20k52k60k180k511k(1)內(nèi)存分配圖20K52K60K280K310K317K算法特點(diǎn)總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配而劃分，當(dāng)有大作業(yè)到來時(shí)，其存儲(chǔ)空間的申請(qǐng)往往會(huì)得不到滿足。快速適應(yīng)算法（分類搜索法）算法要求

將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，每一類相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，每一表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型，并記錄頭指針。進(jìn)程根據(jù)自己的長(zhǎng)度，尋找能容納它的最小空閑區(qū)鏈表，取下第一塊進(jìn)行分配即可。3.分區(qū)分配操作_分配內(nèi)存和回收內(nèi)存（1）分配內(nèi)存系統(tǒng)利用某種分配算法，從空閑分區(qū)表/鏈中找到所需大小的分區(qū)。分區(qū)的切割：設(shè)請(qǐng)求的分區(qū)大小為u.size，空閑分區(qū)的大小為m.size,若m.size-u.sizesize(size是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說明多余部分大小，可不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者；否則，從該分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)表/鏈中，然后，將分配區(qū)的首址返回給調(diào)用者。

分配流程圖如下：從頭開始查表從該分區(qū)中劃出u.size大小的分區(qū)檢索完否？返回m.size>u.sizem.size-u.sizesize將該分區(qū)分配給請(qǐng)求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回將該分區(qū)從分區(qū)表/鏈中移出繼續(xù)檢索下一個(gè)表項(xiàng)YYYNNN內(nèi)存分配流程圖（2）回收內(nèi)存當(dāng)作業(yè)執(zhí)行結(jié)束時(shí)，應(yīng)回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個(gè)大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息?；厥辗謪^(qū)與已有空閑分區(qū)的相鄰情況有以下四種：1）回收分區(qū)上鄰接一個(gè)空閑分區(qū),合并后首地址為空閑分區(qū)的首地址,大小為二者之和。2）回收分區(qū)下鄰接一個(gè)空閑分區(qū),合并后首地址為回收分區(qū)的首地址,大小為二者之和。3）回收分區(qū)上下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。4）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填寫分區(qū)大小等信息。4.3.6可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入

在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個(gè)小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。例：如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，不相鄰，但總?cè)萘繛?0KB，如果現(xiàn)有一作業(yè)要求分配40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的容量均小于40KB，故此作業(yè)無法裝入內(nèi)存。這種內(nèi)存中無法被利用的存儲(chǔ)空間稱為“零頭”或“碎片”。根據(jù)碎片出現(xiàn)的情況分為以下兩種：操作系統(tǒng)作業(yè)A20KB作業(yè)B30KB作業(yè)C15KB作業(yè)D25KB系統(tǒng)中的碎片os用戶程序p4p1p20k20k56k65k125k135k內(nèi)部碎片內(nèi)部碎片內(nèi)部碎片25KB作業(yè)D15KB作業(yè)C30KB作業(yè)B20KB作業(yè)A操作系統(tǒng)外部碎片外部碎片外部碎片外部碎片內(nèi)部碎片外部碎片內(nèi)部碎片：指分配給作業(yè)的存儲(chǔ)空間中未被利用的部分。如固定分區(qū)中存在的碎片。外部碎片：指系統(tǒng)中無法利用的小的空閑分區(qū)。如動(dòng)態(tài)分區(qū)中存在的碎片。碎片問題的解決方法拼接或緊湊或緊縮技術(shù)將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)存中的位置發(fā)生了變化，這就必須對(duì)其地址加以修改或變換即稱為重定位），使本來分散的多個(gè)小空閑分區(qū)連成一個(gè)大的空閑區(qū)。如圖所示。這種通過移動(dòng)作業(yè)從把多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)的方法稱為拼接或緊湊或緊縮。拼接時(shí)機(jī)：分區(qū)回收時(shí)；當(dāng)找不到足夠大的空閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)。操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C作業(yè)D20KB30KB90KB15KB25KB2.動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位可使程序不加任何修改就裝入內(nèi)存，但是它需要硬件—重定位寄存器的支持。對(duì)每一個(gè)有效地址都要加上重定位寄存器中的內(nèi)容，以形成絕對(duì)地址。03456......LOAD1200......0100200300.........LOAD12003456邏輯地址空間110012001300物理地址空間200有效地址+1000BR1000動(dòng)態(tài)重定位分區(qū)分配算法流程圖有大于x的空閑分區(qū)嗎？返回分區(qū)號(hào)空閑分區(qū)總和大于x嗎？拼接并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)返回修改有關(guān)數(shù)據(jù)結(jié)構(gòu)按動(dòng)態(tài)分區(qū)分配方式進(jìn)行分配YYNN無法分配，返回請(qǐng)求分配一個(gè)大小為x的分區(qū)3.動(dòng)態(tài)重定位分區(qū)分配算法

在動(dòng)態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的空閑分區(qū)來滿足作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)，進(jìn)行拼接?？芍囟ㄎ环謪^(qū)分配方式主要特點(diǎn)

可以充分利用存儲(chǔ)區(qū)中的“零頭/碎片”，提高主存的利用率。但若“零頭/碎片”過多，則拼接頻率過高會(huì)使系統(tǒng)開銷加大。4.3.7覆蓋技術(shù)與交換技術(shù)1.覆蓋技術(shù)引入：其目標(biāo)是在較小的可用內(nèi)存中運(yùn)行較大的程序。常用于多道程序系統(tǒng)，與分區(qū)存儲(chǔ)管理配合使用。原理：一個(gè)程序的幾個(gè)代碼段或數(shù)據(jù)段，按照時(shí)間先后來占用公共的內(nèi)存空間。將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存；可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平時(shí)存放在外存中（覆蓋文件），在需要用到時(shí)才裝入到內(nèi)存；不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到內(nèi)存，從而可以相互覆蓋。(即不同時(shí)用的模塊可共用一個(gè)分區(qū))缺點(diǎn)：編程時(shí)必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度。從外存裝入覆蓋文件，以時(shí)間延長(zhǎng)來?yè)Q取空間節(jié)省。A20KD20KE40KC30KB50KF30K作業(yè)X的調(diào)用結(jié)構(gòu)作業(yè)X的常駐區(qū)A（20K）覆蓋區(qū)0（50K）覆蓋區(qū)1（40K）BCDEF注：另一種覆蓋方法：(100K)A(20K)占一個(gè)分區(qū)：20K；B(50K)、D(20K)和E(40K)共用一個(gè)分區(qū)：50K；F(30K)和C(30K)共用一個(gè)分區(qū)：30K；Total:190KTotal:110K2.交換技術(shù)引入：多個(gè)程序并發(fā)執(zhí)行，可以將暫時(shí)不能執(zhí)行的程序送到外存中，從而獲得空閑內(nèi)存空間來裝入新程序，或讀入保存在外存中而目前到達(dá)就緒狀態(tài)的進(jìn)程。交換單位為整個(gè)進(jìn)程的地址空間。常用于多道程序系統(tǒng)或小型分時(shí)系統(tǒng)中，與分區(qū)存儲(chǔ)管理配合使用。又稱作"對(duì)換"或"滾進(jìn)/滾出(roll-in/roll-out)"；程序暫時(shí)不能執(zhí)行的可能原因：處于阻塞狀態(tài)，低優(yōu)先級(jí)（確保高優(yōu)先級(jí)程序執(zhí)行）；原理：暫停執(zhí)行內(nèi)存中的進(jìn)程，將整個(gè)進(jìn)程的地址空間保存到外存的交換區(qū)中（換出swapout），而將外存中由阻塞變?yōu)榫途w的進(jìn)程的地址空間讀入到內(nèi)存中，并將該進(jìn)程送到就緒隊(duì)列（換入swapin）。返回優(yōu)點(diǎn)：增加并發(fā)運(yùn)行的程序數(shù)目，并且給用戶提供適當(dāng)?shù)捻憫?yīng)時(shí)間；編寫程序時(shí)不影響程序結(jié)構(gòu)缺點(diǎn)：對(duì)換入和換出的控制增加處理機(jī)開銷；程序整個(gè)地址空間都進(jìn)行傳送，沒有考慮執(zhí)行過程中地址訪問的統(tǒng)計(jì)特性?？紤]的問題：程序換入時(shí)的重定位；減少交換中傳送的信息量，特別是對(duì)大程序；對(duì)外存交換區(qū)空間的管理：如動(dòng)態(tài)分區(qū)方法；4.4基本分頁(yè)存儲(chǔ)管理方式我們把邏輯地址空間劃分為一些相等的片，這些片稱為頁(yè)或頁(yè)面。物理地址空間也被劃分為同樣大小的片，稱為塊。這樣用戶程序進(jìn)入內(nèi)存時(shí)，就可以一頁(yè)對(duì)應(yīng)存入到一個(gè)塊中。對(duì)整個(gè)程序來說，只有可能在最后一塊存在碎片（稱為頁(yè)內(nèi)碎片），而且碎片大小不會(huì)超過一塊，所以內(nèi)存利用率可以大大提高。用戶程序的邏輯地址:4.4.1頁(yè)面與頁(yè)表頁(yè)號(hào)頁(yè)內(nèi)地址頁(yè)面(或塊)的大小由系統(tǒng)硬件地址結(jié)構(gòu)規(guī)定，通常是2的冪，例如512B，1KB、2KB等。這樣的規(guī)定可以使地址映射容易實(shí)現(xiàn)。頁(yè)面不能過大，也不能過小。過小會(huì)造成頁(yè)面過多，增加了系統(tǒng)開銷；過大又會(huì)造成頁(yè)內(nèi)碎片太大，內(nèi)存利用率不高。早期的頁(yè)面大小一般都在512B～4KB，隨著計(jì)算機(jī)性能的提高，現(xiàn)在一般在2KB～8KB，甚至有的系統(tǒng)支持多種頁(yè)面大小。例：對(duì)于一個(gè)32位的地址結(jié)構(gòu)，如果頁(yè)面大小為4KB，則頁(yè)內(nèi)地址由0～11這12位表示，剩余12～31在表示頁(yè)號(hào)（頁(yè)內(nèi)地址）例：在頁(yè)面大小為4KB的系統(tǒng)中，若邏輯地址為28024，則可求得頁(yè)號(hào)為6，頁(yè)內(nèi)偏移量為3448。而計(jì)算機(jī)內(nèi)部如何得到頁(yè)號(hào)和頁(yè)內(nèi)地址呢？28024的二進(jìn)制用32位表示為：(00000000000000000110110101111000)2，因?yàn)轫?yè)面大小為4KB，則取低12位為頁(yè)內(nèi)地址，剩余高位是頁(yè)號(hào)。把這兩部分換算為十進(jìn)制，我們可以驗(yàn)算出通過上述公式計(jì)算的結(jié)果的正確性。000000000000000001101101011110002802463448系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁(yè)表，記錄了進(jìn)程每個(gè)頁(yè)號(hào)及其對(duì)應(yīng)的存儲(chǔ)塊號(hào)。整個(gè)系統(tǒng)一張存儲(chǔ)分塊表，記錄每個(gè)存儲(chǔ)塊及其狀態(tài)（已分配或空閑）。當(dāng)有一個(gè)進(jìn)程進(jìn)入系統(tǒng)時(shí)，為頁(yè)表分配一個(gè)存儲(chǔ)區(qū)，然后搜索存儲(chǔ)分塊表，查看有哪些存儲(chǔ)塊是空閑的，如有空閑的存儲(chǔ)塊，則將存儲(chǔ)塊號(hào)填入頁(yè)表。當(dāng)該進(jìn)程所需的塊數(shù)都分配完后，系統(tǒng)便可按照頁(yè)表的內(nèi)容對(duì)該進(jìn)程進(jìn)行處理。當(dāng)某個(gè)進(jìn)程因?yàn)榻Y(jié)束或者其它一些原因退出系統(tǒng)，則歸還原來所占用的物理塊。首先修改存儲(chǔ)分塊表，將歸還的物理塊塊號(hào)在表中的狀態(tài)欄改為空閑標(biāo)志，然后釋放該進(jìn)程頁(yè)表所占用的空間。管理上的考慮頁(yè)表、存儲(chǔ)分塊表及其關(guān)系頁(yè)號(hào)012塊號(hào)103920號(hào)頁(yè)表1號(hào)頁(yè)表頁(yè)號(hào)01塊號(hào)953…塊號(hào)0…狀態(tài)0…31……91101……存儲(chǔ)分塊表由于頁(yè)和塊大小是一致的，每頁(yè)的頁(yè)內(nèi)地址與物理塊的塊內(nèi)單元地址也完全一致，所以在邏輯地址到物理地址的映射中，主要從一個(gè)頁(yè)找到對(duì)應(yīng)的內(nèi)存塊，而這種頁(yè)與塊的對(duì)應(yīng)關(guān)系是頁(yè)表記錄的。每個(gè)進(jìn)程調(diào)度時(shí)，從該進(jìn)程PCB中取得頁(yè)表始址和頁(yè)表長(zhǎng)度（頁(yè)表長(zhǎng)度指頁(yè)表的項(xiàng)數(shù)），裝入到系統(tǒng)中設(shè)置的頁(yè)表寄存器內(nèi)。4.4.2地址變換機(jī)構(gòu)1．動(dòng)態(tài)地址映射機(jī)構(gòu)分頁(yè)式地址變換過程例：頁(yè)大小為1024B，給定邏輯地址3795，即得出頁(yè)號(hào)為3，頁(yè)內(nèi)地址為723。頁(yè)表始址頁(yè)表長(zhǎng)度＋頁(yè)表寄存器＞頁(yè)號(hào)3頁(yè)內(nèi)地址723越界中斷①①②②11×1024＋723頁(yè)號(hào)塊號(hào)01615425311……RR＋iR＋3i……365……物理地址11987④11987內(nèi)存內(nèi)存中的頁(yè)表邏輯地址3795③③①頁(yè)號(hào)3與頁(yè)表寄存器中的頁(yè)表長(zhǎng)度比較判斷是否越界，如果越界，則轉(zhuǎn)錯(cuò)誤中斷處理，否則轉(zhuǎn)②；②頁(yè)表中該項(xiàng)在內(nèi)存中的對(duì)應(yīng)地址=頁(yè)表始地址R+頁(yè)號(hào)3×頁(yè)表項(xiàng)長(zhǎng)度i，訪問該地址R+3i，得到物理塊號(hào)11；③11(頁(yè)號(hào))×1024(頁(yè)大小)+723(頁(yè)內(nèi)地址)=11987(物理地址)；④訪問內(nèi)存11987單元，得到需要的數(shù)據(jù)365。頁(yè)表存放在內(nèi)存中，每條指令都必須兩次訪問內(nèi)存儲(chǔ)器，增加了指令執(zhí)行的機(jī)器時(shí)間，影響了計(jì)算機(jī)的速度。一次是訪問頁(yè)表，由頁(yè)號(hào)找到對(duì)應(yīng)的物理塊號(hào)；另一次是在物理地址中實(shí)際存取所要的數(shù)據(jù)或指令。為了加快查表速度，在地址映射機(jī)構(gòu)中加入一組高速寄存器(8個(gè)或16個(gè))，構(gòu)成了一個(gè)容量較小的存儲(chǔ)器，稱之為聯(lián)想存儲(chǔ)器（也稱快表）。在聯(lián)想存儲(chǔ)器中，存放正在運(yùn)行進(jìn)程的當(dāng)前最常用的頁(yè)號(hào)和相應(yīng)塊號(hào)，這個(gè)聯(lián)想存儲(chǔ)器具有并行查詢能力，使地址轉(zhuǎn)換時(shí)間大大下降。2.快表的引入(聯(lián)想存儲(chǔ)器)引入快表的地址映射頁(yè)表始址頁(yè)表長(zhǎng)度＋頁(yè)表寄存器＞頁(yè)號(hào)頁(yè)內(nèi)地址越界中斷①①⑥③b…365……物理地址④內(nèi)存邏輯地址頁(yè)號(hào)塊號(hào)b…內(nèi)存⑥頁(yè)號(hào)塊號(hào)b…⑦②⑦快表⑤由于對(duì)程序和數(shù)據(jù)的訪問往往帶有局限性，所以快表的命中率可以達(dá)到90%左右。例:假設(shè)檢索聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問內(nèi)存的時(shí)間為100ns，訪問聯(lián)想存儲(chǔ)器的的命中率為85%，則CPU存取一個(gè)數(shù)據(jù)的平均時(shí)間為T=0.85*120+0.15*200=132ns，如果不引入聯(lián)想存儲(chǔ)器，訪問2次主存，將達(dá)200ns。問題

若邏輯地址空間很大，則劃分的頁(yè)就很多，頁(yè)表就很大，其占用的存儲(chǔ)空間（要求連續(xù)）就大，實(shí)現(xiàn)較難。解決問題的方法

1、只將當(dāng)前需用的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的需用時(shí)再調(diào)入。

2、多級(jí)頁(yè)表二級(jí)頁(yè)表

(1)將頁(yè)表再進(jìn)行分頁(yè)，并離散地將各個(gè)頁(yè)表頁(yè)面存放在不同的物理塊中，同時(shí)也再建立一張頁(yè)表（外層頁(yè)表）用以記錄頁(yè)表頁(yè)面對(duì)應(yīng)的物理塊號(hào)。

4.4.3多級(jí)頁(yè)表兩級(jí)頁(yè)表結(jié)構(gòu)174210781011…6411151141468……012n012102301210230121023第0頁(yè)頁(yè)表第1頁(yè)頁(yè)表第n頁(yè)頁(yè)表0121141151468內(nèi)存空間外部頁(yè)表(2)邏輯地址：(3)地址轉(zhuǎn)換p1p2d頁(yè)表頁(yè)面號(hào)頁(yè)號(hào)頁(yè)內(nèi)偏移地址dp2p1頁(yè)表頁(yè)面號(hào)頁(yè)號(hào)頁(yè)內(nèi)地址外部頁(yè)表寄存器…

…

外部頁(yè)表++頁(yè)表bd物理地址多級(jí)頁(yè)表

將外層頁(yè)表再進(jìn)行分頁(yè)，也將各外層頁(yè)表頁(yè)面離散地存放在不同的物理塊中，再利用第2級(jí)的外層頁(yè)表來記錄它們之間的對(duì)應(yīng)的關(guān)系。邏輯地址：p1p2d外層頁(yè)表頁(yè)面號(hào)頁(yè)表頁(yè)面號(hào)頁(yè)號(hào)頁(yè)內(nèi)偏移地址p3便于多道程序設(shè)計(jì)，提高了內(nèi)存的利用率，而不必像動(dòng)態(tài)分區(qū)分配那樣執(zhí)行緊湊操作。分頁(yè)存儲(chǔ)管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：采用動(dòng)態(tài)地址映射會(huì)增加計(jì)算機(jī)成本和降低處理機(jī)的速度。各種表格要占用一定容量的內(nèi)存空間，而且還要花費(fèi)一部分處理機(jī)時(shí)間來建立和管理這些表格。雖然消除了大量碎片，但每個(gè)作業(yè)的最后一頁(yè)一般都有不能充分利用的空白區(qū)存儲(chǔ)擴(kuò)充問題仍未得到解決。當(dāng)沒有足夠空間能裝下整個(gè)作業(yè)地址空間時(shí)，該作業(yè)還是無法運(yùn)行。缺點(diǎn)：1．把作業(yè)地址空間中使用的邏輯地址變成內(nèi)存中物理地址稱為（）。A.加載B.重定位C.物理化D.邏輯化3．在內(nèi)存分配的“最佳適應(yīng)法”中，空閑塊是按（）。A.始地址從小到大排序B.始地址從大到小排序C.塊的大小從小到大排序D.塊的大小從大到小排序4．分區(qū)管理和分頁(yè)管理的主要區(qū)別是（）。A.分區(qū)管理中的塊比分頁(yè)管理中的頁(yè)要小B.分頁(yè)管理有地址映射而分區(qū)管理沒有C.分頁(yè)管理有存儲(chǔ)保護(hù)而分區(qū)管理沒有D.分區(qū)管理要求一道程序存放在連續(xù)的空間內(nèi)而分頁(yè)管理沒有這種要求。2．在可變分區(qū)存儲(chǔ)管理中的緊湊技術(shù)可以()。A.集中空閑區(qū)B.增加主存容量C.縮短訪問時(shí)間D.加速地址轉(zhuǎn)換BACD5．設(shè)內(nèi)存的分配情況如下圖所示。若要申請(qǐng)一塊40K字節(jié)的內(nèi)存空間，若采用最佳適應(yīng)算法，則所得到的分區(qū)首址為（）。A.100KB.190KC.330KD.410K占用

占用

占用

占用

┇000K100K180K190K280K330K390K410K512K-1C一個(gè)用戶作業(yè)的程序按其邏輯結(jié)構(gòu)可劃分為若干段，例如主程序段、子程序段、數(shù)據(jù)段、堆棧段等。這些段中的每一段在邏輯上都是完整的，因此每一段都是一組邏輯信息，有自己的名字，且都有一段連續(xù)的地址空間。在分段式存儲(chǔ)管理中，段名用段號(hào)代替，段地址從0開始編址，因?yàn)楦鞫蔚倪壿嬓畔?nèi)容不同，所以段長(zhǎng)度不同。這樣用段號(hào)和段內(nèi)地址構(gòu)成用戶程序的邏輯地址。當(dāng)一個(gè)用戶程序裝入內(nèi)存時(shí)，系統(tǒng)為每個(gè)段分配一個(gè)連續(xù)的內(nèi)存區(qū)域，而各個(gè)段之間可以離散存放。4.5.2分段系統(tǒng)的基本原理段號(hào)段內(nèi)地址4.5基本分段存儲(chǔ)管理方式地址映射機(jī)構(gòu)段表分段式地址變換過程段表始址段表長(zhǎng)度段表寄存器＞段號(hào)3段內(nèi)地址723越界中斷①①邏輯地址＋②②段號(hào)段長(zhǎng)2000段基址16K400154K15025K90038K……8K＋723…365………③④8K8915物理地址內(nèi)存中的段表內(nèi)存3號(hào)段③例：給定邏輯地址中段號(hào)為3，段內(nèi)地址為723分頁(yè)和分段的主要區(qū)別分頁(yè)是出于系統(tǒng)管理的需要，分段是出于用戶應(yīng)用的需要。一條指令或一個(gè)操作數(shù)可能會(huì)跨越兩個(gè)頁(yè)的分界處，而不會(huì)跨越兩個(gè)段的分界處。頁(yè)大小是系統(tǒng)固定的，而段大小則通常不固定。邏輯地址表示：分頁(yè)是一維的，各個(gè)模塊在鏈接時(shí)必須組織成同一個(gè)地址空間；分段是二維的，各個(gè)模塊在鏈接時(shí)可以每個(gè)段組織成一個(gè)地址空間。通常段比頁(yè)大，因而段表比頁(yè)表短，可以縮短查找時(shí)間，提高訪問速度。返回4.5.3信息共享分頁(yè)系統(tǒng)中共享editor的示意圖例:一個(gè)多用戶系統(tǒng)可同時(shí)容納40個(gè)用戶，都執(zhí)行一個(gè)文本編輯程序（160KB代碼和40KB數(shù)據(jù)區(qū)），代碼是可重入的假定頁(yè)面大小為4KB。分段系統(tǒng)中共享editor的示意圖editor進(jìn)程1data1進(jìn)程2editordata2段表段長(zhǎng)基址16080402401608040380editordata1…data280240280380420方便了用戶編程。多個(gè)邏輯段形成作業(yè)這種組織方式，使用戶可以清晰地設(shè)計(jì)和了解程序的結(jié)構(gòu)。便于實(shí)現(xiàn)程序和數(shù)據(jù)的共享與保護(hù)。程序的動(dòng)態(tài)鏈接實(shí)現(xiàn)方便。通常一個(gè)源程序經(jīng)過編譯后所形成的若干個(gè)目標(biāo)程序，還需再經(jīng)過鏈接，形成可執(zhí)行代碼后才能運(yùn)行，這種在裝入時(shí)進(jìn)行的鏈接稱為靜態(tài)鏈接。動(dòng)態(tài)鏈接是指在作業(yè)運(yùn)行之前，并不把幾個(gè)目標(biāo)程序段都鏈接起來，而是先將主程序?qū)?yīng)的目標(biāo)程序裝入內(nèi)存并啟動(dòng)運(yùn)行，當(dāng)運(yùn)行過程中又需要調(diào)用某段時(shí)，再將該段（目標(biāo)程序）調(diào)入內(nèi)存并鏈接起來。所以，動(dòng)態(tài)鏈接是以段為基礎(chǔ)的。應(yīng)用中會(huì)發(fā)生數(shù)據(jù)動(dòng)態(tài)增長(zhǎng)的情況，而且這種增長(zhǎng)是無法預(yù)知的，采用分段管理可以很好地解決這個(gè)問題。分段存儲(chǔ)管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：缺點(diǎn)：有碎片問題。4.5.4段頁(yè)式存儲(chǔ)管理方式在段頁(yè)式存儲(chǔ)管理系統(tǒng)中，處理機(jī)給出的有效地址被劃分為三部分：段號(hào)、段內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)地址。段頁(yè)式存儲(chǔ)管理中，記錄邏輯地址到物理地址的映射表包括段表和頁(yè)表。它們的結(jié)構(gòu)和映射功能如圖所示。段號(hào)S段內(nèi)頁(yè)號(hào)P頁(yè)內(nèi)位移量W

段號(hào)頁(yè)表長(zhǎng)度頁(yè)表始址03122段表頁(yè)號(hào)0塊號(hào)120段的頁(yè)表頁(yè)號(hào)0塊號(hào)11段的頁(yè)表內(nèi)存系統(tǒng)區(qū)例:給定某個(gè)邏輯地址中，段號(hào)為2，段內(nèi)地址為6015，若系統(tǒng)規(guī)定塊大小為1KB，則采用段頁(yè)式管理，該邏輯地址表示：段號(hào)為2，段內(nèi)頁(yè)號(hào)為5，頁(yè)內(nèi)地址為895。其地址變換過程如圖所示。段表始址段表長(zhǎng)度段表寄存器＞越界中斷①①＋②②段號(hào)頁(yè)表長(zhǎng)度0頁(yè)表始址12③內(nèi)存＋16頁(yè)號(hào)塊號(hào)…頁(yè)表段號(hào)2頁(yè)號(hào)5頁(yè)內(nèi)地址895…③16895……365…物理地址17279內(nèi)存內(nèi)存邏輯地址④⑤①段號(hào)2與段表寄存器中存放的段表長(zhǎng)度比較以判斷是否越界，如果越界，則轉(zhuǎn)錯(cuò)誤中斷處理，否則轉(zhuǎn)②；②段表始地址+段號(hào)×段表項(xiàng)長(zhǎng)度，就得到屬于該段的頁(yè)表始地址和頁(yè)表長(zhǎng)度；③頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行越界檢查，頁(yè)表始地址+頁(yè)號(hào)×頁(yè)表項(xiàng)長(zhǎng)度，就得到內(nèi)存頁(yè)表中記錄的該頁(yè)對(duì)應(yīng)的物理塊號(hào)16；④16(塊號(hào))×1024(塊大小)+895(頁(yè)內(nèi)地址)=17279(一個(gè)物理地址號(hào))；⑤訪問內(nèi)存17279單元，得到需要的數(shù)據(jù)365。采用段頁(yè)式存儲(chǔ)管理，從邏輯地址到物理地址的變換過程中要三次訪問內(nèi)存，一次是訪問段表，一次是訪問頁(yè)表，再一次是訪問內(nèi)存物理地址。這就是說，當(dāng)訪問內(nèi)存中的一條指令或數(shù)據(jù)時(shí)，至少要訪問內(nèi)存三次，這將使程序的執(zhí)行速度大大降低。為此，可以像在分頁(yè)存儲(chǔ)管理中那樣，使用聯(lián)想存儲(chǔ)器的方法來加快查表速度。4.6虛擬存儲(chǔ)器的基本概念常規(guī)存儲(chǔ)管理方式的共同點(diǎn)：要求一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。問題：

(1)有的作業(yè)很大,所需內(nèi)存空間大于內(nèi)存總?cè)萘?使作業(yè)無法運(yùn)行。

(2)有大量作業(yè)要求運(yùn)行，但內(nèi)存容量不足以容納下所有作業(yè)，只能讓一部分先運(yùn)行，其它在外存等待。解決方法

（1）增加內(nèi)存容量。（2）從邏輯上擴(kuò)充內(nèi)存容量

----覆蓋

----對(duì)換

----虛擬存儲(chǔ)器4.6.1虛擬存儲(chǔ)器的引入常規(guī)存儲(chǔ)器管理方式的特征（1）一次性：作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存。將導(dǎo)致上述兩問題。（2）駐留性：作業(yè)裝入內(nèi)存后，便一直駐留內(nèi)存，直至作業(yè)運(yùn)行結(jié)束。局部性原理

指程序在執(zhí)行時(shí)呈現(xiàn)出局部性規(guī)律，即在一較短時(shí)間內(nèi)，程序的執(zhí)行僅限于某個(gè)部分，相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域。局部性又表現(xiàn)為時(shí)間局部性(由于大量的循環(huán)操作，某指令或數(shù)據(jù)被訪問后，則不久可能會(huì)被再次訪問)和空間局部性（如順序執(zhí)行，指程序在一段時(shí)間內(nèi)訪問的地址，可能集中在一定的范圍之內(nèi)）。虛擬存儲(chǔ)器的概念基于局部性原理，程序在運(yùn)行之前，沒有必要全部裝入內(nèi)存，僅須將當(dāng)前要運(yùn)行的頁(yè)（段）裝入內(nèi)存即可。運(yùn)行時(shí)，如訪問的頁(yè)（段）在內(nèi)存中，則繼續(xù)執(zhí)行，如訪問的頁(yè)未在內(nèi)存中（缺頁(yè)或缺段），則利用OS的請(qǐng)求調(diào)頁(yè)（段）功能，將該頁(yè)（段）調(diào)入內(nèi)存。如內(nèi)存已滿，則利用OS的頁(yè)（段）置換功能，按某種置換算法將內(nèi)存中的某頁(yè)（段）調(diào)至外存，從而調(diào)入需訪問的頁(yè)。

虛擬存儲(chǔ)器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)管理系統(tǒng)，它具有請(qǐng)求頁(yè)調(diào)入功能和頁(yè)置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充，其邏輯容量由外存容量和內(nèi)存容量之和決定，其運(yùn)行速度接近于內(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)。它允許只裝入若干頁(yè)的用戶程序和數(shù)據(jù)，便可啟動(dòng)運(yùn)行，以后在硬件支持下通過調(diào)頁(yè)功能和置換頁(yè)功能，陸續(xù)將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面換到外存上，置換時(shí)以頁(yè)面為單位。

系統(tǒng)須設(shè)置相應(yīng)的硬件支持和軟件：

（1）硬件支持：請(qǐng)求分頁(yè)的頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)。（2）軟件：請(qǐng)求調(diào)頁(yè)功能和頁(yè)置換功能的軟件。2、分段請(qǐng)求系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段功能及分段置換功能，所形成的段式虛擬存儲(chǔ)器系統(tǒng)。它允許只裝入若干段的用戶程序和數(shù)據(jù)，便可啟動(dòng)運(yùn)行，以后在硬件支持下通過請(qǐng)求調(diào)段功能和分段置換功能，陸續(xù)將要運(yùn)行的段調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的段換到外存上，置換時(shí)以段為單位。系統(tǒng)須設(shè)置相應(yīng)的硬件支持和軟件：

（1）硬件支持：請(qǐng)求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)

（2）軟件：請(qǐng)求調(diào)段功能和段置換功能的軟件4.6.3虛擬存儲(chǔ)器的特征1、多次性多次是虛擬存儲(chǔ)器最重要的特征。指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行。2、對(duì)換性對(duì)換性指允許在作業(yè)運(yùn)行過程中進(jìn)行換進(jìn)、換出。換進(jìn)、換出可提高內(nèi)存利用率。3、虛擬性虛擬性是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。虛擬性是虛擬存儲(chǔ)器所表現(xiàn)出來的最重要的特征，也是實(shí)現(xiàn)虛擬存儲(chǔ)器最重要的目標(biāo)。注：虛擬性以多次性和對(duì)換性為基礎(chǔ)，而多次性和對(duì)換性又是離散分配為基礎(chǔ)。4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式在簡(jiǎn)單頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能。1.對(duì)頁(yè)表的修改狀態(tài)位（中斷位）：表示該頁(yè)是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁(yè)（由不同的算法決定）修改位：表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁(yè)都在外存上保留一份副本，因此，若未被修改，在置換該頁(yè)時(shí)就不需將該頁(yè)寫回到外存上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁(yè)重寫到外存上，以保證外存中所保留的始終是最新副本頁(yè)號(hào)塊號(hào)狀態(tài)位訪問字段修改位外存地址在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OS將所缺頁(yè)調(diào)入內(nèi)存。2．缺頁(yè)中斷機(jī)構(gòu)與一般中斷的主要區(qū)別在于：缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號(hào)。缺頁(yè)中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。3.地址變換機(jī)構(gòu)開始頁(yè)號(hào)>頁(yè)表長(zhǎng)度？CPU檢索快表NNY頁(yè)表項(xiàng)在快表中？訪問頁(yè)表頁(yè)在內(nèi)存？修改訪問位和修改位修改快表形成物理地址地址變換結(jié)束越界中斷程序請(qǐng)求訪問一頁(yè)YN缺頁(yè)中斷處理Y保留CPU現(xiàn)場(chǎng)內(nèi)存滿嗎？將一頁(yè)從外存換入內(nèi)存OS命令CPU從外存讀缺頁(yè)啟動(dòng)I/O硬件Y從外存中找到缺頁(yè)選擇一頁(yè)換出該頁(yè)被修改否？將該頁(yè)寫回外存修改頁(yè)表NYN4.7.2內(nèi)存分配策略和分配算法在請(qǐng)求分頁(yè)系統(tǒng)中，為進(jìn)程分配內(nèi)存時(shí)，將涉及以下三個(gè)問題：1、最小物理塊數(shù)的確定最小物理塊數(shù)指能保證進(jìn)程正常運(yùn)行所需的最小的物理塊數(shù)，與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。2、物理塊的分配策略

（1）固定分配局部置換：為每個(gè)進(jìn)程分配固定數(shù)目n的物理塊，在整個(gè)運(yùn)行中都不改變。如出現(xiàn)缺頁(yè)，則從中置換一頁(yè)。

（2）可變分配全局置換：分配固定數(shù)目的物理塊，但OS自留一空閑塊隊(duì)列，若發(fā)現(xiàn)缺頁(yè)，則從空閑塊隊(duì)列中分配一空閑塊與該進(jìn)程，并調(diào)入缺頁(yè)于其中。當(dāng)空閑塊隊(duì)列用完時(shí)，OS才從內(nèi)存中任選擇一頁(yè)置換。

（3）可變分配局部置換：分配一定數(shù)目的物理塊，若發(fā)現(xiàn)缺頁(yè)，則從該進(jìn)程的頁(yè)面中置換一頁(yè)，根據(jù)該進(jìn)程缺頁(yè)率高低，則可增加或減少物理塊。

3、物理塊分配算法在采用固定分配策略時(shí)，將系統(tǒng)中可供分配的所有物理塊分配給各個(gè)進(jìn)程，可采用以下幾種算法：

（1）平均分配算法：平均分配給各個(gè)進(jìn)程。

（2）按比例分配算法：根據(jù)進(jìn)程的大小按比例分配給各個(gè)進(jìn)程。

（3）考慮優(yōu)先權(quán)的分配算法：將系統(tǒng)提供的物理塊一部分根據(jù)進(jìn)程大小先按比例分配給各個(gè)進(jìn)程，另一部分再根據(jù)各進(jìn)程的優(yōu)先權(quán)適當(dāng)增加物理塊數(shù)。4.7.3頁(yè)面調(diào)入策略

調(diào)入策略決定什么時(shí)候?qū)⒁粋€(gè)頁(yè)面由外存調(diào)入內(nèi)存，從何處將頁(yè)面調(diào)入內(nèi)存。何時(shí)調(diào)入頁(yè)面

預(yù)調(diào)頁(yè)策略：將那些預(yù)計(jì)在不久便被訪問的頁(yè)預(yù)先調(diào)入內(nèi)存。這種調(diào)入策略提高了調(diào)頁(yè)的效率，減少了I/O次數(shù)。但由于這是一種基于局部性原理的預(yù)測(cè)，若預(yù)調(diào)入的頁(yè)面在以后很少被訪問，則造成浪費(fèi)，故這種方式常用于程序的首次調(diào)入。請(qǐng)求調(diào)頁(yè)策略：當(dāng)進(jìn)程運(yùn)行中訪問的頁(yè)出現(xiàn)缺頁(yè)時(shí)，則發(fā)出缺頁(yè)中斷，提出請(qǐng)求調(diào)頁(yè)，由OS將所需頁(yè)調(diào)入內(nèi)存。這種策略實(shí)現(xiàn)簡(jiǎn)單，應(yīng)用于目前的虛擬存儲(chǔ)器中，但易產(chǎn)生較多的缺頁(yè)中斷，且每次調(diào)一頁(yè)，系統(tǒng)開銷較大，容易產(chǎn)生抖動(dòng)現(xiàn)象。從何處調(diào)入頁(yè)面

在請(qǐng)求分頁(yè)系統(tǒng)中，通常將外存分成了文件區(qū)和對(duì)換區(qū)，文件區(qū)按離散分配方式存放文件，對(duì)換區(qū)按連續(xù)分配方式存放對(duì)換頁(yè)。

對(duì)換區(qū)：系統(tǒng)有足夠的對(duì)換區(qū)空間，運(yùn)行前可將與進(jìn)程相關(guān)的文件從文件區(qū)復(fù)制至對(duì)換區(qū)，以后缺頁(yè)時(shí)，全部從對(duì)換區(qū)調(diào)頁(yè)。文件區(qū)：系統(tǒng)沒有足夠的對(duì)換區(qū)空間，凡是不會(huì)被修改的文件，每次都直接從文件區(qū)調(diào)頁(yè)。文件區(qū)、對(duì)換區(qū)：系統(tǒng)沒有足夠的對(duì)換區(qū)空間，對(duì)可能會(huì)修改的文件第一次調(diào)頁(yè)直接從文件區(qū)，換出時(shí)換至對(duì)換區(qū)，以后從對(duì)換區(qū)調(diào)頁(yè)。UNIX方式：凡未運(yùn)行過的頁(yè)面均從文件區(qū)調(diào)頁(yè)，運(yùn)行過的頁(yè)面和換出的頁(yè)面均從對(duì)換區(qū)調(diào)頁(yè)。4.8頁(yè)面置換算法發(fā)生了6次面置換，9次缺頁(yè)中斷。4.8.1最佳（OPT:Optimal）置換算法它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)面置換出去。但是要確定哪一個(gè)頁(yè)面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，目前來說是很難估計(jì)的，所以該算法通常用來評(píng)價(jià)其它算法。例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。頁(yè)面引用70120304230321201701777222222222222227770000004440000000000物理塊1111333333331111111缺頁(yè)xxxxxxxxx物理塊2物理塊3(2)先進(jìn)先出（FIFO）置換算法

算法的基本思想是，總是先淘汰那些駐留在內(nèi)存時(shí)間最長(zhǎng)的頁(yè)面，即先進(jìn)入內(nèi)存的頁(yè)面先被淘汰。這種算法實(shí)現(xiàn)起來比較簡(jiǎn)單，性能最差。會(huì)出現(xiàn)BeLady異常現(xiàn)象。BeLady異常：一般來說，如果分給進(jìn)程的頁(yè)框數(shù)增加，則缺頁(yè)的頻率應(yīng)該減少。但這個(gè)結(jié)論并不普遍成立，對(duì)于某些頁(yè)面訪問序列，F(xiàn)IFO有隨著分給的頁(yè)框數(shù)增加，缺頁(yè)頻率也增加的異?，F(xiàn)象。利用FIFO算法對(duì)上例進(jìn)行頁(yè)面置換的結(jié)果如下:發(fā)生了12次面置換，15次缺頁(yè)中斷。頁(yè)面引用70120304230321201701701223042300012227017011230423330111270物理塊1700123042223000127缺頁(yè)xxxxxxxxxxxxx物理塊2物理塊3xxBeLady異?，F(xiàn)象9104.8.2最近最久未使用置換算法

（LRU：LeastRecentlyUsed）該算法是選擇最近最久未使用的頁(yè)面予以淘汰，系統(tǒng)在每個(gè)頁(yè)面設(shè)置一個(gè)“計(jì)時(shí)”標(biāo)記，用以記錄這個(gè)頁(yè)面自上次被訪問以來所經(jīng)歷的時(shí)間T，當(dāng)要淘汰一個(gè)頁(yè)面時(shí)，選擇T最大的頁(yè)面。但在實(shí)現(xiàn)時(shí)需要硬件的支持。利用LRU算法對(duì)上例進(jìn)行頁(yè)面置換的結(jié)果如下:發(fā)生了9次面置換，12次缺頁(yè)中斷。頁(yè)面引用70120304230321201701701203042303212017017012030423032120170物理塊1701223042203312017缺頁(yè)xxxxxxxxx物理塊2物理塊3xxxＮＲＵ是一種最為流行的、低開銷的ＬＲＵ近似算法。它所依據(jù)的理由是：在最近一段時(shí)間內(nèi)未使用過的頁(yè)在最近的將來不大可能被使用。在具體實(shí)現(xiàn)中，系統(tǒng)為每個(gè)頁(yè)增加兩個(gè)硬件位(用軟件模擬)：（4）最近未使用算法ＮＲＵ（NotRecentlyUsed）設(shè)置修改位的意義在于，如果被淘汰的頁(yè)沒被修改過，由于每頁(yè)在外存都有副本，因此不必把它再寫回外存，否則必須寫回外存。顯然最好的選擇是淘汰沒修改過的頁(yè)，這樣可以減少系統(tǒng)開銷。初始時(shí)，所有實(shí)頁(yè)的引用位和修改位都置為０，當(dāng)訪問某頁(yè)時(shí)，該頁(yè)的引用位置為１，一旦修改了某頁(yè)，便置其修改位為１。當(dāng)要淘汰時(shí)按下列頁(yè)類的次序選擇:首先選擇１類實(shí)頁(yè)進(jìn)行淘汰，然后次之。為了避免到某一時(shí)刻大多數(shù)甚至所有實(shí)頁(yè)的引用位都為１，從而無法區(qū)別哪一頁(yè)最應(yīng)該被淘汰，系統(tǒng)需要周期性地（設(shè)周期為ｔ）將所有引用位都置０。１類：未引用過，未修改過２類：未引用過，修改過３類：引用過，未修改過４類：引用過，修改過(1)分配給進(jìn)程的物理頁(yè)面數(shù)(2)頁(yè)面本身的大小(3)程序的編制方法5.影響缺頁(yè)次數(shù)的因素(4)頁(yè)面淘汰算法例：一程序把128*128的數(shù)組置初值0，每個(gè)元素為一個(gè)字。假定每頁(yè)128個(gè)字，數(shù)組每一行元素存放在一頁(yè)中，只有一塊內(nèi)存，初始時(shí)第一頁(yè)在內(nèi)存。程序編制方法1：Forj:=1to128Fori:=1to128A[i,j]:=0;128*128-1次缺頁(yè)中斷程序編制方法2：Fori:=1to128Forj:=1to128A[i,j]:=0;128-1次缺頁(yè)中斷5.7.4性能問題1.顛簸（抖動(dòng)）操作系統(tǒng)會(huì)對(duì)CPU的工作情況進(jìn)行監(jiān)督，如果發(fā)現(xiàn)CPU出現(xiàn)空閑，它會(huì)調(diào)入新的進(jìn)程來增加多道程序度，保持CPU的高利用率。但是在采用全局置換的方式下，它會(huì)導(dǎo)致其它進(jìn)程的某些頁(yè)被置換出內(nèi)存，而該進(jìn)程執(zhí)行時(shí)會(huì)因此產(chǎn)生缺頁(yè)，所以它又會(huì)置換另外進(jìn)程的頁(yè)，由此造成連鎖反應(yīng)，使得整個(gè)系統(tǒng)中頁(yè)面置換頻繁發(fā)生。在每次置換過程中，都需要啟動(dòng)磁盤I/O，這種低速的延遲操作會(huì)造成CPU等待，操作系統(tǒng)發(fā)現(xiàn)CPU空閑后，又開始增加多道程序度……于是整個(gè)系統(tǒng)就在進(jìn)行頻繁的頁(yè)面置換，這種狀況就稱為“抖動(dòng)”，它會(huì)嚴(yán)重地影響到系統(tǒng)的性能。抖動(dòng)的發(fā)生CPU利用率抖動(dòng)多道程序度為了減少抖動(dòng)的產(chǎn)生，保證系統(tǒng)性能，可以采用局部置換的方法。發(fā)生缺頁(yè)的進(jìn)程不能置換其它進(jìn)程的物理塊，只能從系統(tǒng)為自己所分配的地址空間中置換。這樣當(dāng)一個(gè)進(jìn)程發(fā)生抖動(dòng)時(shí)，不會(huì)造成其它進(jìn)程后繼抖動(dòng)，將抖動(dòng)的影響限制在一個(gè)小的范圍內(nèi)。但是，這種方法有一定的局限性，因?yàn)榘l(fā)生抖動(dòng)的進(jìn)程會(huì)因?yàn)轭l繁進(jìn)行磁盤I/O而形成一個(gè)等待隊(duì)列，這個(gè)等待隊(duì)列也會(huì)造成正常的進(jìn)程置換頁(yè)面時(shí)間的增加，從而影響CPU的吞吐量。為了預(yù)防抖動(dòng)，應(yīng)該給進(jìn)程盡可能提供一段時(shí)間所需的所有頁(yè)面，但系統(tǒng)又如何得知到底需要哪些頁(yè)面呢？有多種技術(shù)