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

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