操作系統(tǒng)原理：第五章 存儲器管理學(xué)習(xí)輔導(dǎo)資料

第五章存儲器管理5.1知識點匯總1、存儲器的層次操作系統(tǒng)的內(nèi)存管理功能，使之操作系統(tǒng)中負(fù)責(zé)管理內(nèi)存使用的那部分功能子集，又稱主存管理。 在現(xiàn)代計算機(jī)系統(tǒng)中，存儲器是信息外理的來源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種存儲裝置，都無法同時從速度與容量兩方面，滿足用戶的需求。實際上它們組成了一個速度由快到慢，容量由小到大的存儲裝置層次。圖5-1三級存儲器結(jié)構(gòu)2、內(nèi)存管理的目的主存的分配和管理：當(dāng)用戶需要內(nèi)存時,系統(tǒng)為之分配相應(yīng)的存儲空間；不需要時，及時回收，以供其它用戶使用。提高主存儲器的利用率：不僅能使多道程序動態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個區(qū)域的信息?！皵U(kuò)充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個大的存儲器中運行。(虛擬內(nèi)存技術(shù))存儲保護(hù)：確保多道程序都在各自分配到存儲區(qū)域內(nèi)操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。 程序的各個階段：編輯―――編譯―――鏈接―――裝入―――運行1).編輯階段：創(chuàng)建源文件2).編譯階段：生成目標(biāo)文件3).連接階段：生成可執(zhí)行文件4).裝入階段：重定位，裝入內(nèi)存5).運行階段：得到結(jié)果圖5-2程序的各個階段3、存儲器管理的功能存儲器管理的功能：內(nèi)存分配、地址映射、內(nèi)存保護(hù)、內(nèi)存擴(kuò)充。4、存儲器有關(guān)概念地址空間：程序用來訪問信息所用地址單元的集合。邏輯（相對）地址的集合。由編譯程序生成存儲空間：主存中物理單元的集合物理（絕對）地址的集合由裝配程序等生成（1）邏輯地址（相對地址，虛地址）用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式，其首地址為0，其余指令中的地址都相對于首地址而編址。不能用邏輯地址在內(nèi)存中讀取信息（2）物理地址（絕對地址，實地址）：內(nèi)存中各物理單元的地址是從統(tǒng)一的基地址順序編址。（3）重定位：把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程。又稱地址映射。1）絕對裝入：編譯后，裝入前已產(chǎn)生了絕對地址（內(nèi)存地址），裝入時不再作地址重定位。絕對地址的產(chǎn)生：（1）由編譯器完成，編程時使用符號地址（2）由程序員編程完成。 程序中所使用的絕對地址，可在編譯或匯編時給出，也可由程序員直接賦予。但在由程序員直接給出絕對地址時，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。2）靜態(tài)重定位：是在目標(biāo)程序裝入內(nèi)存時，由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的地址進(jìn)行修改，即把程序的邏輯地址都改成實際的內(nèi)存地址。重定位在程序裝入時一次完成。圖5-3程序靜態(tài)運行3) 動態(tài)運行時裝入：（動態(tài)重定位）在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此，裝入內(nèi)存后的所有地址都仍是相對地址。 圖5-4動態(tài)重定位示意圖 （4）程序的鏈接 1）靜態(tài)鏈接：對相對地址的修改，變換外部調(diào)用符號。 圖5-5程序的靜態(tài)鏈接2）裝入時動態(tài)鏈接：便于修改和更新，便于實現(xiàn)對目標(biāo)模塊的共享。（DLL動態(tài)鏈接庫） 3）運行時動態(tài)鏈接：這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行，即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。4)碎片：內(nèi)存中容量太小、無法被利用的小分區(qū)。5、內(nèi)存管理技術(shù)-分區(qū)管理三種基本的存儲管理技術(shù)：分區(qū)法、可重定位分區(qū)法和對換技術(shù)（1）分區(qū)法：把內(nèi)存劃分成若干分區(qū)，每個分區(qū)里容納一個作業(yè)。1）固定分區(qū)模式（定長分區(qū)模式）：是將內(nèi)存用戶區(qū)域劃分為幾個固定大小的區(qū)域，在系統(tǒng)運行過程中，每個區(qū)域任意時刻只存放一個程序，且連續(xù)完整存放。 通過設(shè)置內(nèi)存分配表，內(nèi)存分配簡單，但內(nèi)存利用率不高 分區(qū)的分配策略： 最先適配，任何時刻只要一個分區(qū)變成空閑的，隊列中的第一個可裝入的作業(yè)就被裝入執(zhí)行，經(jīng)常把大分區(qū)分給小作業(yè)。 最優(yōu)適配，一旦某分區(qū)變成空閑，便尋找可裝入的最大作業(yè)，有待大作業(yè)而其實小作業(yè)，與優(yōu)待小作業(yè)的處理機(jī)調(diào)度算法相互抵觸。 固定分區(qū)在內(nèi)存利用率上存在的問題：分區(qū)經(jīng)常沒有被填滿。因為分區(qū)的大小是固定的，所以分給進(jìn)程的多余存儲空間將被浪費。被浪費的空間成為內(nèi)部存儲碎片。存在所有空閑分區(qū)總合夠，但每個空閑分區(qū)太小而無法裝入的現(xiàn)象。多道并行的程序數(shù)量受到分區(qū)數(shù)量的限制。2)動態(tài)分區(qū) 將內(nèi)存用戶區(qū)劃分為若干個分區(qū)，每個分區(qū)內(nèi)任意時刻只有一個程序，且為連續(xù)完整存放。但劃分的實際、大小和位置時動態(tài)的，即在系統(tǒng)運行從開機(jī)到關(guān)機(jī)這段時間內(nèi)，各分區(qū)的大小、位置等劃分情況，是根據(jù)用戶程序的來去而變化的。 動態(tài)分區(qū)的策略：=1\*GB3①必須維持一張內(nèi)存空閑區(qū)表和已分配區(qū)表來動態(tài)地跟蹤記錄內(nèi)存空閑塊和已用塊的分布情況。圖5-6內(nèi)存動態(tài)分區(qū)=2\*GB3②分配策略最先適配。為作業(yè)選擇分區(qū)時總是按地址從高到低搜索，只要找到可以容納該作業(yè)的空白塊，就把該空白塊分配給該作業(yè)。下次適配。總是從上次查找結(jié)束的地方開始，找到一個足夠大的空白區(qū)分配。最佳適配。接到內(nèi)存申請時，在空閑塊表中找到一個不小于請求的最小空塊進(jìn)行分配，為作業(yè)選擇分區(qū)時總是尋找其大小最接近于作業(yè)所要求的存儲區(qū)域。特點：用最小空間滿足要求。最壞適配。接到內(nèi)存申請時，在空閑塊表中找到一個不小于請求的最大空塊進(jìn)行分配，與最佳適應(yīng)法相反，它在作業(yè)選擇存儲塊時，總是尋找最大的空白區(qū)。特點：當(dāng)分割后空閑塊仍為較大空塊快速適配=3\*GB3③分配多大的空閑塊恰好分配法：分配大小正好是進(jìn)程所需要的長度，適合無動態(tài)擴(kuò)充要求的進(jìn)程。預(yù)留空間法：分的大小大于進(jìn)程的長度，適用于由動態(tài)擴(kuò)充要求的進(jìn)程?？勺兎謪^(qū)模式的特點相對于固定分區(qū)模式，工作復(fù)雜化了。相對于固定分區(qū)模式，提高地內(nèi)存空間利用率，但仍存在空間的浪費，。主要是外部存儲碎片，也存在內(nèi)部存儲碎片。 外部存儲碎片。小的分不出去的空閑塊。以及黨內(nèi)存所有空閑塊長度之和足夠裝入一個進(jìn)程，但各個空閑塊長度都不夠裝入該進(jìn)程時，稱這些空閑塊為外部存儲碎片。 內(nèi)部存儲碎片。在已分配給某個進(jìn)程的空間中，未被使用而被浪費的部分空間，稱為內(nèi)部碎片。6、虛擬存儲器（1）虛擬存儲器：是由操作系統(tǒng)提供的一個假想的特大存儲器（2）虛擬存儲器的基本特征：1)虛擬擴(kuò)充：不是物理上，而是邏輯上擴(kuò)充了內(nèi)存容量2)部分裝入：每個作業(yè)不是全部一次性地裝入內(nèi)存，而是只裝入一部分3)離散分配：不必占用連續(xù)的空間，而是“見縫插針”。4)多次對換：所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存（3）虛擬存儲器受到的限制：1)指令中表示地址的字長2)外存的容量7、頁式內(nèi)存管理將內(nèi)存固定劃分為等長的頁面（物理頁，frame）。將程序也劃分為等長的頁（邏輯頁，logicalframe）。將程序的各頁裝入內(nèi)存各空閑的頁面。程序的邏輯編址是一維連續(xù)編址，即邏輯頁是連續(xù)的。而存放到內(nèi)存中的物理頁時則不一定是連續(xù)的。 頁模式分為：靜態(tài)（實存）頁式，要求程序要一次全部裝入。動態(tài)（虛存）頁式，程序可以不一次性全部裝入。 在頁式管理中，程序的邏輯地址分為頁號和頁內(nèi)偏移兩部分。（1）實存頁式的基本工作過程與結(jié)構(gòu) 由于內(nèi)存空閑頁面是動態(tài)隨機(jī)分布的，所以需要一個數(shù)據(jù)結(jié)構(gòu)來隨時記錄內(nèi)存中哪些頁面是空閑的，稱為內(nèi)存頁表。通常采用位圖的方式記錄內(nèi)存的使用情況。 圖5-7內(nèi)存頁表由于一個程序的所有頁對應(yīng)的內(nèi)存頁面時隨即分散的，因此存在運行時動態(tài)重定位的需要，這就需要為每個進(jìn)程建立一張表，反映該進(jìn)程在內(nèi)存的分布情況，稱為進(jìn)程頁表。其中列出了作業(yè)的邏輯地址與其在主存中的物理地址間的對應(yīng)關(guān)系。表中的每一行稱為頁描述子 圖5-8進(jìn)程頁表當(dāng)一個要建立一個進(jìn)程時。首先要得到進(jìn)程所需長度（頁數(shù)）。然后將空閑頁分配給該進(jìn)程，將使用到的空閑頁號記錄到進(jìn)程頁表，并修改內(nèi)存頁表。（2）虛存頁式的基本工作過程與結(jié)構(gòu) 虛存技術(shù)：虛存是為提高內(nèi)存利用率而提出的一種技術(shù)。在一個操作系統(tǒng)下，不要求任一用戶進(jìn)程所實際占用的內(nèi)存空間都大于等于該用戶進(jìn)程的邏輯地址空間。而且這種功能的實現(xiàn)對用戶透明，則稱該操作系統(tǒng)實現(xiàn)了虛存技術(shù)。 具體做法：在外存中劃分出一塊做為虛擬內(nèi)存。跟內(nèi)存統(tǒng)一編址，并劃分頁。當(dāng)進(jìn)程建立時，部分頁放入真實內(nèi)存的物理頁中，部分頁放在虛擬內(nèi)存的頁中。在進(jìn)程頁表中有一項表明該頁在內(nèi)存還是在虛擬內(nèi)存中。查詢進(jìn)程頁表，可以確定要訪問的頁是否在內(nèi)存，若不在，則發(fā)生缺頁中斷。將頁調(diào)入內(nèi)存。然后再次訪問該頁。 當(dāng)要將頁調(diào)入內(nèi)存時，發(fā)現(xiàn)內(nèi)存不足，有三種應(yīng)對策略。1）、等待，等待其他進(jìn)程執(zhí)行完畢釋放內(nèi)存，然后取得內(nèi)存再執(zhí)行。2）、拒絕，將進(jìn)程撤銷，以后再執(zhí)行。3）、淘汰，將已經(jīng)分配在內(nèi)存空間中，不再使用的頁或近期不在使用的頁，釋放。這稱為淘汰技術(shù)。頁淘汰的工作通常由一個系統(tǒng)進(jìn)程來完成，稱為頁淘汰進(jìn)程。被淘汰的頁，被放在外存中，以后需要時再調(diào)入內(nèi)存。在外存中專門存放淘汰頁的外存區(qū)域稱為盤交換區(qū)(swaparea,swapplace)。 淘汰策略有：FIFO，在內(nèi)存中時間最長的頁最先被淘汰。在內(nèi)存時間最長的頁，很可能是最長被訪問的頁。LRU，最近最少使用頁被淘汰。每次訪存都要對相應(yīng)頁做時間標(biāo)記，開銷很大。NRU，最近未使用頁被淘汰（時鐘算法）。（3）虛存的作用1）、解決了大程序在小空間內(nèi)運行的問題。用戶所使用的邏輯空間可以比實際內(nèi)存空間大得多。2）、提高了內(nèi)存的利用率，增加了多道數(shù)，提高了CPU的利用率和系統(tǒng)吞吐量。一個進(jìn)程的一次執(zhí)行中，未執(zhí)行或未訪問的那些代碼頁和數(shù)據(jù)頁，不會進(jìn)入內(nèi)存。3）、相對于交換技術(shù)，虛存減少了裝入或交換所需的I/O量。虛存每次換入換出是以頁為單位，而交換技術(shù)則是整個進(jìn)程空間。4）、相對于覆蓋技術(shù)，程序員不必自己劃分覆蓋塊，簡化了編程任務(wù)。5）、使用戶不必考慮空間大小，不必考慮實際地址。（4）進(jìn)程頁表的實現(xiàn)進(jìn)程頁表的存放1）、進(jìn)程頁表完全放在內(nèi)存中（完全內(nèi)存方案） 需要為每個進(jìn)程建立一個進(jìn)程頁表基址寄存器。每次訪問內(nèi)存時，根據(jù)進(jìn)程頁表的基址寄存器值，及邏輯頁號，訪問當(dāng)前進(jìn)程的進(jìn)程頁表。 每次訪存，實際上執(zhí)行了兩次訪存，一次是訪問進(jìn)程頁表，讀出頁描述子。第二次才是訪問所要訪問的頁。這意味著，用戶程序的執(zhí)行時間將增長一倍，使總的處理速度明顯下降。2）、進(jìn)程頁表完全放在一組寄存器中（完全快表方案） 將進(jìn)程頁表完全放在一組高速寄存器中（稱為快表）。與上一個方案比，程序執(zhí)行速度快了一倍。但高速寄存器成本較高，容量有限，不適用于大進(jìn)程地址空間。3）、進(jìn)程頁表全部放在寄存器中，但部分正在使用的內(nèi)容放在寄存器中（部分快表方案） 為了解決前面的問題，采用一組高速寄存器，存放當(dāng)前訪問過的頁的頁描述子。每次訪問主存時，首先查找快表，若找到所需的頁描述子，則快速形成物理地址。否則從頁表中查找后形成物理地址，同時把頁描述子寫入快表。如果設(shè)計得當(dāng)，快表的命中率可以很高。進(jìn)程頁表兩級結(jié)構(gòu) 現(xiàn)代的大多數(shù)計算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。 例如：一個32位的系統(tǒng)，一個進(jìn)程的虛擬空間可達(dá)2GB，當(dāng)頁長為4KB時，該空間內(nèi)有2的19次方個頁。假如每個物理頁的頁號要4B,則該進(jìn)程的頁表，需要占用2MB的空間即512頁。 因此將進(jìn)程頁表設(shè)計成兩級結(jié)構(gòu)，分為頁目錄(外層頁)和頁表頁。圖5-9進(jìn)程兩級頁表邏輯地址結(jié)構(gòu)如下圖：（5）大而稀疏內(nèi)存使用 之前討論的進(jìn)程虛址空間（邏輯地址空間）都是連續(xù)編址的。這樣不適應(yīng)用戶程序中多處動態(tài)伸縮的需要。要適應(yīng)這種需要，進(jìn)程虛址空間就必須采用不連續(xù)編址。 通常有三種不連續(xù)編址方案：段式，段頁式，頁式稀疏編址。頁式下，進(jìn)程虛址空間的稀疏編址，稱為大而稀疏內(nèi)存使用。用戶程序可以隨意的指定其數(shù)據(jù)和代碼的虛址空間，可以不連續(xù)。 稀疏編址通常都是基于二級頁表結(jié)構(gòu)為前提。表現(xiàn)為虛址的怠惰建立風(fēng)格。在二級頁表中表現(xiàn)為頁表頁的不一次性裝入（怠惰建立風(fēng)格）。無法從頁表中獲知哪個虛址已被使用。因此要實現(xiàn)稀疏編址需要建立一個數(shù)據(jù)結(jié)構(gòu)來標(biāo)識已用的虛址范圍。 在頁式中存在三次怠惰。第一次，稀疏編址，以怠惰風(fēng)格分配虛址。第二次，二級頁表結(jié)構(gòu)中，頁表頁的怠惰分配。第三次，發(fā)生缺頁中斷時，怠惰地建立進(jìn)程的某一頁。 三次怠惰都是基于盡量少占用空間資源的思想。（6）頁分配策略 1）、何時分配與裝入（fetch策略） 立即調(diào)頁是指在進(jìn)程開始執(zhí)行前，即進(jìn)程建立時分配與裝入。 請求調(diào)頁是指在實際訪問某頁時才通過發(fā)生缺頁中斷，由缺頁中斷處理程序分配與裝入該頁（怠惰）?？赡苋表撝袛啻螖?shù)過多，導(dǎo)致大大減慢進(jìn)程執(zhí)行速度。 預(yù)先調(diào)頁是指由操作系統(tǒng)根據(jù)一定的算法，動態(tài)預(yù)測將來最近時間內(nèi)最可能要訪問哪些頁，并在這些也被實際訪問前就預(yù)先分配裝入。 虛存頁式大都采用后兩種，而實存頁式都用立即調(diào)頁。 2）、寫時復(fù)制 進(jìn)程的創(chuàng)建時，通常的做法是為自進(jìn)程重新分配物理空間，并把福進(jìn)程空間的內(nèi)容全盤復(fù)制到子進(jìn)程空間中，其開銷非常大。為了降低進(jìn)程創(chuàng)建的開銷，提出了寫時復(fù)制技術(shù)：不復(fù)制父進(jìn)程的空間，而是復(fù)制父進(jìn)程的頁表，使父進(jìn)程和子進(jìn)程共享物理空間，并將這個共享空間的訪問權(quán)限設(shè)置為只讀，當(dāng)福進(jìn)程和子進(jìn)程的某一方進(jìn)行寫操作時，發(fā)生一個異常，這時才將要寫的頁進(jìn)行復(fù)制，這樣一來某些不被改變的頁不被復(fù)制，降低了開銷。（7）頁長和頁簇化 注意：頁長指的是物理空間中劃分的頁的長度。頁面長指的是邏輯空間中劃分的頁的長度。 頁（面）長通常是2的整數(shù)次冪，這可以簡化地址映射過程中的邏輯地址分解和物理地址計算。 頁（面）長的確定主要考慮：頁面大，則內(nèi)部碎片就大。浪費存儲空間和相應(yīng)的I/O帶寬，且啟動時間長，但進(jìn)程頁表小，快表(TLB)項數(shù)少，快表命中率提高，因此減少了頁調(diào)入調(diào)出次數(shù)。 頁面長度是由CPU硬件規(guī)定的。不同CPU規(guī)定的頁長不同，如：512b,1kb,2kb,4kb,8kb等等。目前4kb是最常見的。而且同一CPU規(guī)定的頁長可能多個，這時操作系統(tǒng)通過CPU中的寄存器設(shè)置來指定頁長。 一般情況下，頁長與頁面長是一樣的，但實際上操作系統(tǒng)頁面長可以是頁長的整數(shù)倍，即用幾個相鄰的頁組成一個頁面（稱為一簇），并把這樣的頁面做為最小的分配和映射的邏輯單元。這稱為簇化技術(shù)。 頁簇化，減小了頁面管理代價。由于每一簇實際上是幾個頁，所以每次調(diào)頁都是幾個頁同時調(diào)，減少了調(diào)頁的I/O操作次數(shù)和缺頁中斷次數(shù)。 頁簇化實際上是預(yù)先調(diào)頁的一種情況。即預(yù)先調(diào)入與所缺頁相鄰的一些頁。（8）工作集和顛簸 工作集:在進(jìn)程運行的某一時刻，為確保進(jìn)程能執(zhí)行下去，在物理存儲中必須有的最少頁面數(shù)。 一個進(jìn)程在不同時刻需要不同的工作集，當(dāng)一個進(jìn)程訪問一個不在其工作集中的地址時就會發(fā)生缺頁中斷。當(dāng)內(nèi)存負(fù)擔(dān)過重時，進(jìn)程所分配到的物理存儲小于最小工作集，導(dǎo)致連續(xù)地，過多地產(chǎn)生缺頁中斷。并頻繁產(chǎn)生剛淘汰的頁很快又被調(diào)入的情況，稱為抖動（顛簸）. 出現(xiàn)顛簸的時候，幾乎所有的CPU時間都用于頁的調(diào)入調(diào)出，而不是用于正常的程序執(zhí)行。 系統(tǒng)對顛簸的處理通常是，選中一個或若干個進(jìn)程，整個調(diào)出內(nèi)存，直至有足夠空閑頁面，不再顛簸為止。 如果一個系統(tǒng)不斷發(fā)生顛簸現(xiàn)象，說明該系統(tǒng)沒有安裝足夠的內(nèi)存。8、分段存儲管理技術(shù)（1）、特點將用戶程序空間按邏輯劃分為幾個部分，每一部分稱為一段，每個段內(nèi)連續(xù)編址，段間則不一定兩續(xù)編址。每個程序的邏輯地址空間是二維編址的（段號和段內(nèi)偏移），這需要便衣程序的支持，但對高級語言程序員通常是透明的。以段為單位，劃分進(jìn)程空間，連續(xù)完整存放。即，段內(nèi)是連續(xù)存放，段間不連續(xù)存放。段模式分實存段式與虛存段式兩種，進(jìn)程在建立的時候要求全部裝入內(nèi)存，則是實存段式，否則為虛存段式。段式和頁式著兩種不連續(xù)模式的區(qū)別在于，如何劃分程序的邏輯地址空間。頁式是等長劃分，是非邏輯的，硬性的，固定的劃分。段式是不等長劃分，是邏輯的，按照程序的語義和結(jié)構(gòu)進(jìn)行的，自然的劃分。分頁與分段的區(qū)別分頁信息的物理單位大小一樣，由系統(tǒng)固定地址空間是一維的分段信息的邏輯單位大小不等，由用戶確定地址空間是二維的（2）、用戶內(nèi)存觀點 用戶將程序看作一個帶有許多子例程，過程，函數(shù)或模塊的主程序，還可能有各種數(shù)據(jù)結(jié)構(gòu)，表，殊足，棧，變量等。每個模塊或數(shù)據(jù)元素通過名字存取。這些元素中的每個都是變長的。各段中的指令或數(shù)據(jù)，由他們相對于段首的位移確定。 段式就是支持這種用戶內(nèi)存觀點的一種內(nèi)存管理模式。一個邏輯地址空間是多個段的集合，每個段有一個名字和一個長度，地址由段名和段內(nèi)位移兩部分組成。 每個段可有其邏輯意義及功能，使得便于 1）方便編程； 2）分段共享； 3）分段保護(hù)； 4）動態(tài)鏈接； 5）動態(tài)增長；（如數(shù)據(jù)段的增長）（3）、段式的實現(xiàn) 首先，將一個用戶程序劃分為多個段。因此要每個進(jìn)程要維護(hù)一個進(jìn)程段表，該表中記錄段的邏輯段號，段長度，段地址，其他信息。 以段為單位按照可變分區(qū)模式管理。因此與可變分區(qū)模式一樣，系統(tǒng)中要維護(hù)一張內(nèi)存空閑塊表。P165圖3.29 段式下邏輯地址由段號和段內(nèi)偏移兩部分組成。 段的劃分除了考慮段長和段數(shù)因素外，還應(yīng)考慮保護(hù)要求與共享要求。通常段式下一個進(jìn)程的地址空間包含：代碼段。數(shù)據(jù)段。棧段。共享內(nèi)存段。其他段。（4）、段式的內(nèi)存空間利用率和可變分區(qū)相比，仍然存在外部存儲碎片。與頁式比，同樣是不連續(xù)，但不連續(xù)程度沒有頁式高。虛存段式下，不用到的段，不會進(jìn)入內(nèi)存，且用完不再用的，能調(diào)出內(nèi)存，從而節(jié)約內(nèi)存空間段式下也可以通過代碼段共享來節(jié)省內(nèi)存空間。（5）、段式存儲的保護(hù)、共享、內(nèi)存擴(kuò)充和評價 段式下的保護(hù)機(jī)制除了根據(jù)段長進(jìn)行越界檢查之外，還可以在進(jìn)程段表中增加權(quán)限位指出每段是只讀的，可寫的，只執(zhí)行的燈，每次通過進(jìn)程段表進(jìn)行地址映射時，都檢查此次內(nèi)存訪問是否符合該段的權(quán)限定義。 把保護(hù)要求不同的放在不同段，這樣就充分實現(xiàn)了一個程序中不同內(nèi)容的不容保護(hù)要求。比如把一個只讀數(shù)據(jù)定義為單獨一段。 對于殊足這樣需要越界保護(hù)的結(jié)構(gòu)也單獨一段，自然實現(xiàn)了數(shù)組越界的保護(hù)。段式的共享 通過不同的進(jìn)程段表中的某一條記錄，指向同一個段地址來實現(xiàn)。段式的動態(tài)擴(kuò)充 由于在邏輯編址上，采用了段號和段內(nèi)偏移，二維的編址方式，使得段式可以實現(xiàn)多處伸縮。每個段的動態(tài)伸縮方式與可變分區(qū)類似，手是否有相鄰空閑塊的限制。對段式的評價 內(nèi)存利用率比可變分區(qū)好，比頁式差；保護(hù)和共享比之前所談到的其他模式都好。9段頁式存儲管理 段頁式是段式與頁式的結(jié)合。利用了二者的優(yōu)點，互補(bǔ)了二者的缺點。 段頁式：將內(nèi)存劃分為等長的頁，將每個用戶程序先劃分為段，再將每段劃分為頁面，頁內(nèi)必須連續(xù)完整存放，但頁間可以不連續(xù)，也不一定要求所有的頁都進(jìn)入內(nèi)存。 段頁式的實現(xiàn) 每個進(jìn)程一張進(jìn)程段表，記錄進(jìn)程中各個段的頁表位置。 每個段一張該段的頁表，存放該段存放在內(nèi)存中的各個頁的位置。 段頁式的評價 基本上結(jié)合了段式和頁式的優(yōu)點，克服了二者的缺點。 段頁式的內(nèi)存利用率比段式高，比頁式低。段頁式消除了段式中的外部碎片，但和頁式一樣存在內(nèi)部碎片，其內(nèi)部碎片比頁式多，頁式是平均每個程序有半頁的內(nèi)部碎片，而段頁式是平均每段有半頁內(nèi)部碎片。 段頁式的共享和保護(hù)實現(xiàn)與段式一樣好，比頁式好。 段頁式的動態(tài)擴(kuò)充比段式和頁式都要好，既不受邏輯編址相鄰的限制，也不受物理相鄰的限制。 段頁式的表空間支出（進(jìn)程段表，每個段的頁表）高，地址映射時間等管理代價比段式與頁式都高。10、動態(tài)頁式管理中的頁面置換算法（1）先進(jìn)先出法（FIFO）：將最先進(jìn)入內(nèi)存的頁換出內(nèi)存。例如內(nèi)存塊數(shù)量為3時，采用FIFO頁面置換算法，下面頁面走向情況下，缺頁次數(shù)是多少？70120304230321201701772222444000777000333222111001110003332221

∴缺頁次數(shù)=15次(2).最佳置換法（OPT）：將將來不再被使用或是最遠(yuǎn)的將來才被訪問的頁例如內(nèi)存塊數(shù)量為3時，采用OPT頁面置換算法，下面頁面走向情況下，缺頁次數(shù)是多少？70120304230321201701772222227000040001133311∴缺頁次數(shù)=9次(3).最近最少使用置換法（LRU）：將最近一段時間里最久沒有使用過的頁面換出內(nèi)存。例如內(nèi)存塊數(shù)量為3時，采用LRU頁面置換算法，下面頁面走向情況下，缺頁次數(shù)是多少？70120304230321201701772224440111000000333001133222227∴缺頁次數(shù)=12次(4).最近未使用置換法（NUR）：是LRU近似方法，比較容易實現(xiàn)，開銷也比較小。實現(xiàn)方法：在存儲分塊表的每一表項中增加一個引用位，操作系統(tǒng)定期地將它們置為0。當(dāng)某一頁被訪問時，由硬件將該位置1。需要淘汰一頁時，把該位為0的頁淘汰出去，因為最近一段時間里它未被訪問過。5.2例題解析例5.2解引入邏輯地址有如下原因：物理地址的程序只有裝入程序所規(guī)定的內(nèi)存空間上才能正確執(zhí)行，如果程序所規(guī)定內(nèi)存空間不空閑或不存在，程序都無法執(zhí)行；使用物理地址編程意味著由程序員分配內(nèi)存空間，這在多道程序系統(tǒng)中，勢必造成程序所占內(nèi)存空間的相互沖突；在多道程序系統(tǒng)中，程序員門無法事先協(xié)商每個程序所應(yīng)占的內(nèi)存空間的位置，系統(tǒng)也無法保證程序執(zhí)行時，它所需的內(nèi)存空間都空閑?；谏鲜鲈?，必須引入一個統(tǒng)一的、在編程時使用的地址，它能夠在程序執(zhí)行時根據(jù)所分配的內(nèi)存空間將其轉(zhuǎn)換為對應(yīng)的物理地址，這個地址就是邏輯地址。邏輯地址的引入為內(nèi)存的共享、保護(hù)和擴(kuò)充提供方便。例5.2實現(xiàn)容易，無需增加硬件地址變換機(jī)構(gòu)；一般要求為每個程序分配一個連續(xù)的存儲區(qū)；在重定位過程中，裝入內(nèi)存的代碼發(fā)生了改變；在程序執(zhí)行期間不在發(fā)生地址的變換；在程序執(zhí)行期間不能移動，且難以做到程序和數(shù)據(jù)的共享，其內(nèi)存利用率低。例5.2動態(tài)重定位的實現(xiàn)要依靠硬件地址變換機(jī)構(gòu)，且存儲管理的軟件算法比較復(fù)雜；程序代碼是按原樣裝入內(nèi)存的，在重定位的過程中也不發(fā)生變化，重定位產(chǎn)生的物理地址存放在內(nèi)存地址寄存器中，因此不會改變代碼；同一代碼中的同一邏輯地址，每執(zhí)行一次都需要重位一次；只要改變基地址，就可以很容易地實現(xiàn)代碼在內(nèi)存中的移動；動態(tài)重定位可以將程序分配到不連續(xù)的存儲區(qū)中；實現(xiàn)虛擬存儲器需要動態(tài)重定位技術(shù)的支持；盡管動態(tài)重定位需要硬件支持，但他支持程序浮動，便于利用零散的內(nèi)存空間，利于實現(xiàn)信息共享和虛擬存儲，所以現(xiàn)代計算機(jī)大都采用動態(tài)重定位。例5.2（1）便于軟件版本的修改和更新在采用裝入時動態(tài)鏈接方式時，要修改或更新各個目標(biāo)模塊，是件非常容易的事，但對于經(jīng)靜態(tài)鏈接以裝配在一起的裝入模塊，如果要修改或更新其中的某個目標(biāo)模塊時，則要求重新打開裝入模塊，這不僅是低效的，而且對于普通用戶是不可能的。（2）便于實現(xiàn)目標(biāo)模塊共享若采用裝入時動態(tài)鏈接方式，OS能夠?qū)⒁粋€目標(biāo)模塊鏈接到幾個應(yīng)用程序中去。即實現(xiàn)多個應(yīng)用程序?qū)υ撃K的共享；然而，采用靜態(tài)鏈接方式時每個應(yīng)用模塊都必須含有該目標(biāo)模塊的拷貝，則無法實現(xiàn)共享。例5.2解覆蓋技術(shù)與虛擬存儲技術(shù)的本質(zhì)不同是：虛擬存儲器對于程序員時透明的，不需要程序員了解程序結(jié)構(gòu)、覆蓋的區(qū)域、時機(jī)，不需要精心的設(shè)計程序及其數(shù)據(jù)結(jié)構(gòu)，所有的操作由操作系統(tǒng)自動完成。覆蓋的程序段的最大長度要受到物理內(nèi)存容量的限制，而虛擬存儲器的最大長度不受物理內(nèi)存容量的限制，只受計算機(jī)地址結(jié)構(gòu)的限制。交換技術(shù)與虛存中使用的調(diào)入調(diào)出技術(shù)相同和不同之處：主要相同點是都要在內(nèi)存與外存之間交換信息；主要區(qū)別在于交換技術(shù)換出換進(jìn)一般是整個進(jìn)程(proc結(jié)構(gòu)和共享正文段除外)，因此一個進(jìn)程的大小受物理存儲器的限制；而虛存中使用的調(diào)入調(diào)出技術(shù)在內(nèi)存與外存之間來回傳遞的是存儲頁或存儲段，而不是整個進(jìn)程，從而使得進(jìn)程映射具有了更大的靈活性，且允許進(jìn)程的大小比可用的物理存儲空間大的多。例5.2.7有一計算機(jī)系統(tǒng)，內(nèi)存容量為段號段內(nèi)地址2920190求其虛擬存儲器的實際容量？解虛擬內(nèi)存的實際大小由系統(tǒng)的邏輯地址結(jié)構(gòu)、主存輔存容量共同決定。虛擬內(nèi)存容量的理論值是210*220=1G；最大段內(nèi)地址為220=1M，遠(yuǎn)大于內(nèi)存容量，其段長超過512K的內(nèi)存容量，故最大實際段長為512k而不是1M所以可計算虛擬存儲容量為210*512K=210*0.5M=0.5G。0.5G<2G，因此虛擬存儲器的實際容量是0.5G例5.2解在段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，需三次訪問內(nèi)存。第一次訪問，是訪問內(nèi)存中的段表，從中取得頁表始址；第二次訪問，是訪問內(nèi)存中的頁表，從中取出邏輯頁面對應(yīng)的內(nèi)存物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問，才是真正從第二次訪問所得的地址中，取出指令或數(shù)據(jù)。例5.2解實存管理的方法主要分成：用戶程序需要占用連續(xù)的內(nèi)存空間，如分區(qū)存儲管理；用戶程序不需要占用連續(xù)的內(nèi)存空間，如分頁、分段、段頁等管理，一個用戶程序在內(nèi)存可能是不連續(xù)的，如果它有不只一頁或一段的話。例5.2.解“鏈接”（link），本應(yīng)是編譯系統(tǒng)的任務(wù)，但是，隨著程序執(zhí)行方式的改進(jìn)，當(dāng)出現(xiàn)了“動態(tài)鏈接”之后，“程序鏈接”就不僅僅是編譯系統(tǒng)的事情，它還需要OS的支持。程序的靜態(tài)鏈接，指的是在程序裝入內(nèi)存之前，由鏈接程序?qū)⒁丫幾g好的多個目標(biāo)模塊（.obj文件）鏈成一個統(tǒng)一的可執(zhí)行文件。其特點是：①鏈接好的可執(zhí)行文件可以重復(fù)使用和執(zhí)行；②被鏈接的模塊一般不可能再拆開，因而不便修改和更新；③不便于多個程序共享某些模塊，需使用同一模塊的多個程序需分別將該模塊鏈入自己的程序空間。裝入時動態(tài)鏈接，指的是在程序加載入內(nèi)存（準(zhǔn)備執(zhí)行）時，由OS中的裝入程序（如exec()）將存放在盤上的諸多目標(biāo)模塊邊裝入邊在內(nèi)存鏈接成一個統(tǒng)一的可執(zhí)行程序。其特點是：①鏈接好的可執(zhí)行程序只存在于內(nèi)存，因而每次執(zhí)行都要重新鏈接；②被鏈接的諸目標(biāo)模塊在盤上是各自獨立存放的，因而便于修改；③便于共享，當(dāng)多個程序需使用同一模塊時，該模塊在內(nèi)存只需一個副本。執(zhí)行時動態(tài)鏈接，是把程序的鏈接推遲到程序執(zhí)行時根據(jù)執(zhí)行的需要動態(tài)地裝入和鏈接。它除了有與“裝入時動態(tài)鏈接”相同的特點外，還有一個顯著的特點，是不會將本次執(zhí)行中不需要的模塊（如錯誤處理模塊）裝入內(nèi)存，從而減少時空開銷。當(dāng)然，它也增加了鏈接的復(fù)雜性，且需要一定的硬件支持。動態(tài)鏈接需要OS的支持和服務(wù)。例5.2解“重定位”，在實際上指的是這樣相互聯(lián)系的兩件事情：一是確定一個待執(zhí)行程序在內(nèi)存中的位置；二是將程序中的邏輯地址轉(zhuǎn)換成物理地址。說它們是相互聯(lián)系的，是因為后一件事情是由前一件事情決定的。靜態(tài)重定位，指的是在程序裝入時實現(xiàn)的重定位。具體的講，就是將程序裝入內(nèi)存后，立即根據(jù)其裝入位置將程序中需重定位的邏輯地址轉(zhuǎn)換成物理地址，包括指令地址、數(shù)據(jù)地址、子程序入口地址等。這種“定位”的特點是“定位”之后，內(nèi)存中的代碼發(fā)生了變化，程序不能在內(nèi)存移動，CPU按物理地址運行程序。動態(tài)重定位，是在程序執(zhí)行的過程中，根據(jù)執(zhí)行的需要動態(tài)地裝入、鏈接和定位。它不是根據(jù)程序在內(nèi)存的位置立即將指令和數(shù)據(jù)的邏輯地址轉(zhuǎn)換成物理地址，而是把這種位置信息送入一個稱之為“地址映射機(jī)構(gòu)”的硬件中，然后，CPU按邏輯地址執(zhí)行程序。在執(zhí)行中，由“映射機(jī)構(gòu)”將邏輯地址及時地轉(zhuǎn)換成正確的訪存物理地址。這種定位方法的主要特點是重定位后，內(nèi)存中的代碼沒有發(fā)生了變化，允許程序在執(zhí)行的過程中在內(nèi)存移動位置，這只要更換“映射機(jī)構(gòu)”中的啟址信息就可將同一程序映射到內(nèi)存不同的地方。這種位置移動對提高內(nèi)存空間的利用率是有好處的。例5.2解空間分配的“邊界要求”，指的是要求所分得的空間的起始地址落在所分得空間的大小的整數(shù)倍上。例如，若要求分一個4K大的空間，則實際分得的空間的起始地址應(yīng)是0，4K，8K，12K，…；有的系統(tǒng)之所以有這種要求，主要是為了便于機(jī)器的判斷和管理。例如，在分頁存儲管理系統(tǒng)內(nèi)，每一個頁面在內(nèi)存的起始地址都應(yīng)是頁面大小的整數(shù)倍，這樣才能正確地將一個地址劃分成頁號和頁內(nèi)位移量兩部分，并正確地實現(xiàn)分頁管理下的地址映射；又如，若為一個數(shù)組分配空間，則所分空間的起始地址也應(yīng)落在數(shù)組元素個數(shù)（假定一個元素需要偶數(shù)個字節(jié)）的整數(shù)倍上，這樣就可以根據(jù)當(dāng)前地址算出當(dāng)前處理的是第幾個元素，并且，當(dāng)數(shù)組中的所有元素都處理一遍后，此時地址的低部分會與數(shù)組起始地址的低部分相同，這樣，機(jī)器就很容易判斷該數(shù)組已處理完一遍。例5.2.解這是因為用于地址變換的頁表或段表也是存放在內(nèi)存的，為了將CPU給出的邏輯地址變成物理地址，首先就要訪問內(nèi)存的頁表和段表，然后，根據(jù)形成的物理地址再取指令或數(shù)據(jù)，這就要兩次訪存。解決這一問題的辦法是提供一個稱之為“快表”的硬件，用以存放當(dāng)前運行進(jìn)程的頁表或段表的部分內(nèi)容，“快表”的訪問時間很快，因此可以節(jié)約訪問頁表和段表的時間。存儲器訪問具有時間和空間的“局部性”，因此快表的命中率一般可達(dá)70%到90%；頁表和段表是在系統(tǒng)執(zhí)行過程中，每時每刻都需要訪問的，因此，訪問時間的微小縮短，其累計節(jié)約的時間卻可以達(dá)到很大。例5.2.14在分頁存儲管理系統(tǒng)中，存取一次內(nèi)存的時間是8us，查詢一次快表的時間是1us，缺頁中斷的時間是求對某一數(shù)據(jù)進(jìn)行一次次存取可能需要的時間？現(xiàn)連續(xù)對同一頁面上的數(shù)據(jù)進(jìn)行4次連續(xù)讀取，求每次讀取數(shù)據(jù)可能需要的時間?解當(dāng)系統(tǒng)對數(shù)據(jù)進(jìn)行存取時，有3種可能性。所存取的數(shù)據(jù)的頁面在內(nèi)存，其頁表項已經(jīng)存儲到快表，此時存取數(shù)據(jù)的時間是：查詢快表的時間+存取內(nèi)存數(shù)據(jù)的時間=1us+8us=9us所存取的數(shù)據(jù)的頁面在內(nèi)存，但是其頁表項沒有存儲到快表，沒有命中快表，此時存取數(shù)據(jù)的時間是：查詢頁表的時間+存取內(nèi)存數(shù)據(jù)的時間=8us+8us=16us所存取的數(shù)據(jù)的頁面不在內(nèi)存，發(fā)生缺頁中斷，此時存取數(shù)據(jù)的時間是：查詢頁表的時間+缺頁中斷的時間+查詢頁表的時間+存取內(nèi)存數(shù)據(jù)的時間=8us+20us+8us+8us=44us當(dāng)對某一數(shù)據(jù)進(jìn)行4次連續(xù)讀取時：第1次可能的時間為：1us+8us=9us；8us+8us=16us；8us+20us+8us+8us。②第2次時，對應(yīng)頁面的頁表項已經(jīng)交換到快表中。因為存取是連續(xù)的，不存在頁面被淘汰的可能性，所以第2次、第3次、第4次的存取時間是一樣的，消耗的時間為1us+8us=9us。例5.2解在分頁和分段存儲管理系統(tǒng)中，多個進(jìn)程并發(fā)運行，共享同一內(nèi)存塊里的程序或數(shù)據(jù)是可行的。為了實現(xiàn)共享，必須在各共享者的段表或頁表中分別有指向共享內(nèi)存塊的表目。對分段式系統(tǒng)，被共享的程序或數(shù)據(jù)可作為單獨的一段。在物理上它是一段，在不同的進(jìn)程中，可以對應(yīng)不同的邏輯段，相對來說比較易于實現(xiàn)。對分頁管理，則要困難的多。首先，必須保證被共享的程序或數(shù)據(jù)占有整數(shù)塊，以便與非共享部分分開。其次，由于共享程序或數(shù)據(jù)被多個進(jìn)程訪問，所以每個進(jìn)程對共享程序或數(shù)據(jù)的訪問都應(yīng)該是有限制條件的。因此，從共享和保護(hù)的實現(xiàn)上來看，須共享的程序段或數(shù)據(jù)段是一個邏輯單位，而分段存儲管理中被共享的程序或數(shù)據(jù)作為一個整體（一段）,實現(xiàn)共享和保護(hù)就要方便得多。分段系統(tǒng)的共享是通過兩個（或多個）進(jìn)程的段表之相應(yīng)表目都指向同一個物理段，并設(shè)置共享計數(shù)來實現(xiàn)的。每段設(shè)置訪問方式，就可以實現(xiàn)段的保護(hù)。例5.2解主要是因為段是一個有意義的邏輯整體，如主程序、子程序、數(shù)據(jù)表格、工作空間等，就如書本上的一章或一個自然段。而頁只是一個物理尺寸，不一定有完整的意義，如書本上的一頁。程序共享當(dāng)然希望被共享的對象是一個有意義的整體，如一個子程序；至于程序保護(hù)，指的是每個進(jìn)程都應(yīng)按所擁有的存取權(quán)訪問不同的程序，而存取權(quán)(R,W,E等)當(dāng)然對一個有完整意義的對象才更有意義。所以就共享和保護(hù)而言，分段管理比分頁管理更有意義。例5.2解從原理上講，單道程序設(shè)計系統(tǒng)也可實現(xiàn)虛存管理，但從實際上看，虛存主要是應(yīng)用在多道程序設(shè)計系統(tǒng)中。虛存的實現(xiàn)需要程序的動態(tài)重定位技術(shù)的支持，因為程序的對換會導(dǎo)致同一部分程序多次進(jìn)出內(nèi)存并有可能在內(nèi)存中不斷地移動位置。虛存與程序的動態(tài)鏈接沒有必然的因果關(guān)系，但程序的動態(tài)鏈接可以避免無用的程序進(jìn)入內(nèi)存，使虛存的效率提高實現(xiàn)；虛存需要覆蓋和交換技術(shù)的支持，但覆蓋和交換與虛存是不同的概念。在實存管理下覆蓋和交換是一種可以節(jié)省內(nèi)存的技術(shù)，對用戶是不透明，覆蓋和交換的區(qū)由程序結(jié)構(gòu)和程序員決定。而在虛存下的交換和覆蓋對程序員是透明的，操作是由OS根據(jù)某種算法決定的。例5.2.18解頁面置換算法的異?，F(xiàn)象，也叫Belady異常，是在局部置換前提下的一種現(xiàn)象。所謂局部置換，指的是當(dāng)一進(jìn)程創(chuàng)建時，分給其一定數(shù)量的頁面（例如8頁），然后，在運行過程中，若該進(jìn)程需調(diào)入新頁且須置換一個頁面時，則只能置換其自己的一個頁面而不能置換別的進(jìn)程的頁面。頁面置換的異?，F(xiàn)象，是指在一定置換算法和一定頁面走向下，分給進(jìn)程的頁面數(shù)增多其頁面失效率反而增加這樣一種情況。這種異常，只在一定的算法和一定的頁面走向下才會出現(xiàn)。許多算法，如OPT.和LRU，在任何情況下都不會有異?，F(xiàn)象。LRU之所以不會有“異?！?，是因為最近的過去使用的n個頁面一定在最近的過去使用的n+1個頁面之中。例5.2解抖動現(xiàn)象，是在虛存管理下，用于頁面（在內(nèi)、外存之間）對換的時間比程序的有效運行時間還要多的這樣一種現(xiàn)象。它可以是一進(jìn)程內(nèi)部的局部性抖動，也可以是整個系統(tǒng)的全局性抖動。造成這種情況固然與置換算法和頁面走向有關(guān)，但其根本原因是多道系統(tǒng)內(nèi)的進(jìn)程數(shù)太多，從而分給每個進(jìn)程的頁面數(shù)太少。因此，解決這一問題的最有效的辦法是減少系統(tǒng)內(nèi)的進(jìn)程數(shù)。Denning于1980年提出了“L=S準(zhǔn)則”，即調(diào)整系統(tǒng)內(nèi)的進(jìn)程數(shù)，使得產(chǎn)生缺頁的平均間隔時間（L）等于系統(tǒng)處理進(jìn)程缺頁的平均時間（S）。理論和實踐表明，此時的CPU利用率最高。例5.2.20有這樣一種頁面置換算法，它給每一個內(nèi)存塊(塊與頁大小相等若某進(jìn)程分得4個內(nèi)存塊，現(xiàn)對1、2、3、4、5、3、4、1、6、7、8、7、8、9、7、8、9、5、4、5、4、2，解答如下問題：求在上述算法下的頁面失效數(shù)；求在OPT.算法下的頁面失效數(shù)。解（1）求解過程如下表所示頁面號√1√2√3√4√534√1√6√7√878√9789√5√454√2B11111555555888888888882B222222211111199999999B33333336666666665555B4444444777777777444C11111222222333333333334C2011111122222233333333C30011111122222222233333C40001111112222222223333注：打“√”的表示缺頁，共有13次缺頁。說明：在上面的求解過程中，B1～B4表示進(jìn)程分得的4個塊號，C1～C4表示與這4塊對應(yīng)的計數(shù)器；表中的每一列記錄了每一塊當(dāng)前裝入的頁面及其計數(shù)器的值。（2）在OPT.算法下的頁面失效次數(shù)為11。例5.2.21在可變分區(qū)分配的存儲管理方案中，基于鏈表的存儲分配算法有哪幾種？它們的思想是什么？解：在可變式分區(qū)分配的存儲管理方案中，基于鏈表的存儲分配算法主要有三種：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法和最佳適應(yīng)算法。（1）首次適應(yīng)算法在首次適應(yīng)算法中，每個空白區(qū)按其位置的順序鏈在一起，即每個后繼的空白區(qū)其起始地址總是比前者的大。當(dāng)系統(tǒng)要分配一個存儲塊時，就按照空白塊鏈的順序，一次查詢，直到找到第一個滿足要求的空白塊為止。由這種算法確定的空白塊其大小不一定剛好滿足要求。如果找到的這個空白區(qū)比要求的大，則把它分成兩個分區(qū)，一個為已分配分區(qū)，其大小剛好等于所要求的；另一個仍然為空白塊，且留在鏈中原來的位置上。若是在空白鏈中從頭到尾找一遍，找不到滿足要求的空白塊，則返回“暫不能分配”。系統(tǒng)在回收一個分區(qū)時，首先檢查該分區(qū)是否有鄰接的空白塊，如果有，則應(yīng)將這個分區(qū)與之合并，并將該空白塊保留在鏈中原來的位置。如果回收的分區(qū)不和空白塊鄰接，則應(yīng)根據(jù)其起始地址大小，把它插在鏈中的相應(yīng)位置上。首次適應(yīng)算法的實質(zhì)是，盡可能地利用存儲器低地址部分的空白塊，盡量保存在高地址部分的大空白塊。其優(yōu)點在于：當(dāng)需要一個較大的分區(qū)時，便有希望找到足夠大的空白塊以滿足要求。其缺點是：在回收一個分區(qū)時，需要花費較多的時間去查找鏈表，確定它的位置。（2）循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法與首次適應(yīng)算法類似，只是在每次分配分區(qū)時，系統(tǒng)不是從第一個空白塊開始查找，而是從上次分配的空白塊處查找。當(dāng)查找至鏈尾時，便從鏈?zhǔn)桌^續(xù)查找，直到找完整個鏈表。在系統(tǒng)回收一個分區(qū)時，為了減少在插入一個空白區(qū)時查詢鏈表的時間，如果這個分區(qū)不和空白塊鄰接，則把它插入到前向指針鏈的最后一個空白塊后；如果有空白塊相鄰，則根據(jù)情況作相應(yīng)處理。由此可見，這些空白塊在鏈中的位置沒有一定的規(guī)則。這種循環(huán)首次適應(yīng)算法的實質(zhì)是，使得小的空白塊均勻地分布在可用存儲空間內(nèi)。這樣，當(dāng)回收一個分區(qū)時，它和一個較大空白塊相鄰的可能性比較大，因而合并后可得到大的空白塊。和首次適應(yīng)算法相比，它產(chǎn)生過小空白塊的現(xiàn)象比較小。（3）最佳適應(yīng)算法在最佳適應(yīng)算法中，空白塊按大小順序鏈在一起。系統(tǒng)在尋找空白塊時，總是從最小的一個開始。這樣，第一次找到的滿足要求的空白塊必然是最適合的，因為它最接近于要求的大小。這種算法的優(yōu)點是：如果存儲空間中具有正好是所要求大小的空白塊，則必然被選中；如果不存在這樣的空白塊，也只對比要求稍大的空白塊劃分，而絕不會去劃分一個更大的空白塊。此后，遇到有大的存儲要求時，就比較容易滿足了。最佳適應(yīng)算法的缺點在于：尋找一個較大空白塊時花費的時間較長；回收一個分區(qū)時，把它插入到空白塊鏈中合適的位置上也較為費時；此外，由于每次都劃分一個與要求大小最接近的空白塊，使得系統(tǒng)中小的空白塊較多。其實質(zhì)是，在系統(tǒng)中尋找與要求的空間大小最接近的一個空白塊。例5.2.22在虛擬頁式存儲系統(tǒng)為什么要引入缺頁中斷？缺頁中斷實現(xiàn)由哪幾部分組成，并分別說明其實現(xiàn)方法。解頁式虛存管理是在頁式存儲管理的基礎(chǔ)上實現(xiàn)虛擬存儲器的，作業(yè)在執(zhí)行時并不是所有的頁均放在主存，若欲訪問的頁面不在主存，則須由操作系統(tǒng)把當(dāng)前所需頁面從輔存裝入主存。這一過程就交由中斷系統(tǒng)完成，稱為缺頁中斷。缺頁中斷由缺頁處理和頁淘汰組成，缺頁處理過程如下：中斷觸發(fā)：在地址變換過程中，當(dāng)查詢頁表時，發(fā)現(xiàn)邏輯頁面不在內(nèi)存，即其狀態(tài)位為0，則發(fā)生缺頁中段。頁面調(diào)入：OS在頁表中找到對應(yīng)頁面的輔存地址，進(jìn)行頁面的淘汰，將所缺頁調(diào)入內(nèi)存；修改頁表：將該頁面的內(nèi)存地址填入頁表，修改狀態(tài)位為1；缺頁中斷結(jié)束，恢復(fù)現(xiàn)場，重新執(zhí)行指令。頁面淘汰處理如下：如果內(nèi)存有空閑的頁面，直接調(diào)入外存的頁面，修改頁表；（2）如果內(nèi)存沒有空間，根據(jù)頁面淘汰算法，在內(nèi)存中找到可淘汰的頁面；（3）如果被淘汰頁面修改位為0，則直接調(diào)入外存頁面將其覆蓋，修改頁表；（4）如果被淘汰頁面修改位為1，則要申請一塊交換空間，將該內(nèi)存的內(nèi)容保存到交換區(qū)中，然后將輔存的頁面調(diào)入其中，修改頁表。例5.2.23何謂虛擬機(jī)存儲器，并舉一例說明操作系統(tǒng)如何實現(xiàn)虛擬內(nèi)存的？解虛擬存儲器通過把主、輔存統(tǒng)一起來管理，給用戶造成一種仿佛系統(tǒng)內(nèi)有巨大主存供用戶使用的假象。例如頁式存儲管理，一道作業(yè)被劃分成若干頁，其中較活躍的幾頁放在內(nèi)存，而其余不活躍的頁被放在輔存，當(dāng)需要訪問輔存內(nèi)的頁時，就可通過頁面調(diào)度將其調(diào)入內(nèi)存運行；但用戶感覺不到這種變化，他會以為作業(yè)的所有部分都存在于主存。這樣可以讓更多的作業(yè)進(jìn)入主存，提高系統(tǒng)的效率。例5.2.24在內(nèi)存管理中，“內(nèi)零頭”和“外零頭”各指的是什么？在固定式分區(qū)分配、可變式分區(qū)分配、頁式虛擬存儲系統(tǒng)、段式虛擬存儲系統(tǒng)中，各會存在何種零頭？為什么？解內(nèi)零頭（又稱內(nèi)部碎片）：給一個作業(yè)分配的存儲單元長度為n，該塊存儲的作業(yè)長度為m，則剩下的長度為（n-m）的空間，成為該單元的內(nèi)部碎片；若存儲單元長度為n，在該系統(tǒng)所采用的調(diào)度算法下，較長時間內(nèi)無法選出一道長度不超過該塊的作業(yè)，則稱該塊為外零頭（外部碎片）。在固定式分區(qū)分配中兩種零頭均會存在，因為空間劃分是固定的，無論作業(yè)長短，存儲單元均不會隨之變化，若作業(yè)短而存儲塊長則產(chǎn)生內(nèi)零頭，若作業(yè)長而存儲塊短則產(chǎn)生外零頭。在可變式分區(qū)分配中只有外零頭而無內(nèi)零頭，因為空間劃分是依作業(yè)長度進(jìn)行的，是要多少給多少，但剩下的部分太短而無法再分，則稱為外零頭。頁式虛存中會存在內(nèi)零頭而無外零頭，因存儲空間與作業(yè)均分為等長單元，所以不存在無法分配的單元，但作業(yè)長度并不剛好為頁面大小的整數(shù)倍，因此在最后一頁會有剩余空間，即為內(nèi)零頭。段式虛存中會存在外零頭而無內(nèi)零頭，因段式的空間劃分類似于可變分區(qū)分配，根據(jù)段長分配，要多少給多少，但會剩余小空間無法分配，則為外零頭。例5.2.25常用的內(nèi)存信息保護(hù)方法有哪幾種？它們各自的特點是什么？解常用的內(nèi)存保護(hù)方法有硬件法、軟件法和軟硬件結(jié)合保護(hù)法三種。界地址保護(hù)法，即上下界保護(hù)法，是一種常用的