第四章 存儲器管理

第四章存儲器管理4.1存儲器的層次結構4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4基本分頁存儲管理方式4.5基本分段存儲管理方式4.6虛擬存儲器的基本概念4.7請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式

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

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

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

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

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

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

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

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

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

0：B=10000

100：

LOAD1，2500

10100：

LOAD1，12500

2500：

365

12500：

365

2600：12600：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在動態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的空閑分區(qū)來滿足作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)要求時，進行拼接。可重定位分區(qū)分配方式主要特點

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

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

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

2、多級頁表二級頁表

(1)將頁表再進行分頁，并離散地將各個頁表頁面存放在不同的物理塊中，同時也再建立一張頁表（外層頁表）用以記錄頁表頁面對應的物理塊號。

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

…

外部頁表++頁表bd物理地址多級頁表

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

占用

占用

占用

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

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

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

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

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

----覆蓋

----對換

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

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

虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲管理系統(tǒng)，它具有請求頁調(diào)入功能和頁置換功能，能從邏輯上對內(nèi)存容量進行擴充，其邏輯容量由外存容量和內(nèi)存容量之和決定，其運行速度接近于內(nèi)存，成本接近于外存。4.6.2虛擬存儲器的實現(xiàn)方法1、分頁請求系統(tǒng)在分頁系統(tǒng)的基礎上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲器系統(tǒng)。它允許只裝入若干頁的用戶程序和數(shù)據(jù)，便可啟動運行，以后在硬件支持下通過調(diào)頁功能和置換頁功能，陸續(xù)將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面換到外存上，置換時以頁面為單位。

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

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

（1）硬件支持：請求分段的段表機制、缺段中斷機構和地址變換機構

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

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

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

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

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

（1）平均分配算法：平均分配給各個進程。

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

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

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

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

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

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

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

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