第四章存儲管理

操作系統(tǒng)教程課件第1頁第四章存儲管理4.1存儲管理概述4.2程序的裝入與鏈接4.3連續(xù)存儲空間管理4.4頁式存儲管理4.5段式存儲管理4.6段頁式存儲管理4.7虛擬存儲管理方式本章小結4.1存儲管理概述存儲器用于存放程序(指令)、操作數(shù)(數(shù)據(jù))以及操作結果。計算機系統(tǒng)中，存儲器一般分為主存儲器和輔助存儲器兩大類。CPU可以直接訪問主存儲器中的指令和數(shù)據(jù)，但不能直接訪問輔助存儲器。在I/O控制系統(tǒng)管理下，輔助存儲器與主存儲器之間可以進行信息傳遞。主存儲器簡稱主存，或稱為內(nèi)存。主存可分為系統(tǒng)區(qū)和用戶區(qū)兩個區(qū)域。存儲管理是對主存中的用戶區(qū)進行管理，其目的是盡可能地方便用戶和提高主存空間的利用率，使主存在成本、速度和規(guī)模之間獲得較好的權衡。操作系統(tǒng)教程課件第2頁4.1.1存儲器的存儲結構在現(xiàn)代計算機系統(tǒng)中，存儲部件通常是采用層次結構來組織，以便在成本、速度和規(guī)模等諸因素中獲得較好的性能價格比。現(xiàn)代通用計算機，存儲層次至少應具有三級：最高層為CPU寄存器，中間層為主存，最底層為輔存。在較高檔的計算機中，還可以根據(jù)具體的功能分工細劃為寄存器、高速緩存、主存儲器、磁盤緩存、磁盤、可移動存儲介質(zhì)等組成操作系統(tǒng)教程課件第3頁4.1.1存儲器的存儲結構如圖4-1所示，在存儲層次中越往上，存儲介質(zhì)的訪問速度越快，價格也越高，相對存儲容量也較小。操作系統(tǒng)教程課件第4頁其中，寄存器、高速緩存、主存儲器和磁盤緩存均屬于操作系統(tǒng)存儲管理的管轄范疇，掉電后它們存儲的信息不再存在。固定磁盤和可移動存儲介質(zhì)屬于設備管理的管轄范疇，它們存儲的信息將被長期保存。而磁盤緩存本身并不是一種實際存在的存儲介質(zhì)，它依托于固定磁盤，提供對主存儲器存儲空間的擴充。圖4-1計算機系統(tǒng)存儲器層次4.1.2存儲管理的功能1．主存空間的分配和去配2．實現(xiàn)地址轉換3．主存空間的共享和保護4．主存空間的擴充

操作系統(tǒng)教程課件第5頁4.2.1物理地址和邏輯地址主存儲器的存儲單元以字節(jié)（每個字節(jié)為8個二進制位）為單位編址，每個存儲單元都有一個地址與其相對應。假定主存儲器的容量為n，則該主存就有n個字節(jié)的存儲空間，其地址編號為0，1，2…，n－1。這些地址稱為主存儲器的“物理地址”（絕對地址），由物理地址所對應的主存空間稱“物理地址空間”。在多道程序設計系統(tǒng)中，主存中同時存放了多個用戶作業(yè)。每次調(diào)入運行時，操作系統(tǒng)將根據(jù)主存的使用情況為用戶分配主存空間。為了方便程序的編制，每個用戶可以認為自己作業(yè)的程序和數(shù)據(jù)存放在一組以“0”地址開始的連續(xù)空間中。用戶程序中所使用的地址稱為“邏輯地址”，由邏輯地址對應的存儲空間稱為“邏輯地址空間”。操作系統(tǒng)教程課件第6頁4.2.2程序的裝入將一個用戶的源程序裝入主存中并執(zhí)行，通常需要經(jīng)過以下幾個步驟：首先編譯，由編譯程序(Compiler)將用戶源代碼編譯成若干個目標模塊（ObjectModule）；然后鏈接，由鏈接程序（Linker）將編譯后形成的一組目標模塊以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊(LoadModule)；最后裝入，由裝入程序(Loader)將裝入模塊裝入主存。如圖4-2所示。操作系統(tǒng)教程課件第7頁4.2.2程序的裝入將一個裝入模塊裝入主存，可以有絕對裝入方式、靜態(tài)重定位裝入方式和動態(tài)重定位裝入方式。1．絕對裝入方式如果在編譯時知道程序駐留在主存的具體位置，則編譯程序將產(chǎn)生物理地址的目標代碼。絕對裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入主存。模塊裝入后，由于程序中的邏輯地址與實際主存的地址完全相同，所以不需要對程序和數(shù)據(jù)的地址進行修改。絕對裝入方式只能將目標模塊裝入到主存儲器事先指定的固定位置，它只適用于單道程序環(huán)境。操作系統(tǒng)教程課件第8頁4.2.2程序的裝入

2．靜態(tài)重定位裝入方式在裝入作業(yè)時，把該作業(yè)中的指令地址和數(shù)據(jù)地址一次性全部轉換成物理地址，這樣在作業(yè)執(zhí)行過程中無需再進行地址轉換工作，這種地址轉換方式稱“靜態(tài)重定位”。而這種作業(yè)裝入的方式稱為“靜態(tài)重定位裝入方式”。如圖4-3所示靜態(tài)重定位裝入的過程。操作系統(tǒng)教程課件第9頁4.2.2程序的裝入

3．動態(tài)重定位裝入方式在裝入作業(yè)時，裝入程序直接把作業(yè)裝入到所分配的主存區(qū)域中。在作業(yè)執(zhí)行過程中，隨著每條指令或數(shù)據(jù)的訪問由硬件地址轉換機制自動地將指令中的邏輯地址轉換成對應的物理地址。這種地址轉換的方式是在作業(yè)執(zhí)行過程中動態(tài)完成的，故稱為“動態(tài)重定位”。而這種作業(yè)裝入的方式稱為“動態(tài)重定位裝入方式”。如圖4-4所示動態(tài)重定位裝入過程。

操作系統(tǒng)教程課件第10頁4.2.2程序的裝入操作系統(tǒng)教程課件第11頁圖4-4動態(tài)重定位4.2.2程序的裝入

采用動態(tài)重定位時，由于裝入主存的作業(yè)仍保持邏輯地址，所以必要時可改變作業(yè)在主存儲器中的存放區(qū)域。作業(yè)在主存中被移動位置后，只需要把新區(qū)域的起始地址代替原來基址寄存器中的地址，這樣，作業(yè)執(zhí)行時，硬件地址轉換機制將按新區(qū)域的起始地址與邏輯地址相加，轉換成新的物理地址，使作業(yè)仍可正確執(zhí)行。

若作業(yè)執(zhí)行時被改變了存儲區(qū)仍能正確運行，則稱程序是可浮動的。采用動態(tài)重定位的系統(tǒng)支持“程序浮動”。而采用靜態(tài)重定位時，由于被裝入主存儲器中的作業(yè)信息都已轉換為物理地址，作業(yè)執(zhí)行過程中，不再進行地址的轉換，故作業(yè)執(zhí)行過程中是不能改變存放位置的，即采用靜態(tài)重定位的系統(tǒng)不支持“程序浮動”。操作系統(tǒng)教程課件第12頁4.2.3程序的鏈接源程序經(jīng)過編譯后，得到一組目標模塊，再通過鏈接程序將這組目標模塊鏈接，形成一個完整的裝入模塊。程序鏈接示意如圖4-5所示。操作系統(tǒng)教程課件第13頁4.2.3程序的鏈接

根據(jù)鏈接時間不同，程序的鏈接可分成如下三種方式：1．靜態(tài)鏈接。在程序運行之前，首先將各個目標模塊以及所需要的庫函數(shù)，鏈接成一個完整的裝入模塊，又稱為可執(zhí)行文件，運行時可直接將它裝入主存。經(jīng)過編譯后得到的目標模塊，每個模塊的起始地址都為“0”，模塊中的地址都是相對于起始地址計算的，在鏈接成一個裝入模塊后，程序中被調(diào)用模塊的起始地址不再是“0”，此時須修改被調(diào)用模塊的邏輯地址，同時每個模塊中使用的外部調(diào)用符號也相應轉變?yōu)檫壿嫷刂?。如圖3-5（b）中，B和C模塊的起始地址分別變更為L和L+M，而原B模塊中的所有邏輯地址都要加上L，原C模塊中的所有邏輯地址都要加上L+M。

操作系統(tǒng)教程課件第14頁4.2.3程序的鏈接

2．裝入時動態(tài)鏈接。用戶源程序經(jīng)編譯后得到的一組目標模塊，在裝入主存時，采用邊裝入邊鏈接的方式，即在裝入一個目標模塊時，若需要調(diào)用一個模塊，則找出該模塊，并將它裝入主存，并修改目標模塊中的邏輯地址。由于采用動態(tài)鏈接的各個目標模塊是分開存放的，操作系統(tǒng)可以方便地將一個目標模塊鏈接到幾個應用模塊上，所以采用動態(tài)鏈接方式，可以容易地實現(xiàn)對目標模塊的修改和更新，同時便于實現(xiàn)對目標模塊的共享。操作系統(tǒng)教程課件第15頁4.2.3程序的鏈接

3．運行時動態(tài)鏈接。在很多情況下，由于應用程序每次運行時的條件不同，需要調(diào)用的模塊有可能是不相同的。如果將所有目標模塊裝入主存，并鏈接在一起，得到一個非常大的裝入模塊，其中可能存在某些目標模塊根本就沒有條件運行，這樣會引起程序裝入時間上和主存空間上的浪費。運行時動態(tài)鏈接是指在程序執(zhí)行過程中當需要該目標模塊時，才把該模塊裝入主存，并進行鏈接。這樣不僅可以加快程序裝入的速度，而且可以節(jié)省大量的主存空間。連續(xù)存儲空間管理，是指把主存儲器中的用戶區(qū)作為一個連續(xù)區(qū)域或者分成若干個連續(xù)區(qū)域進行管理。連續(xù)存儲管理方式可分為單一連續(xù)分配、固定分區(qū)分配以及可變分區(qū)分配等方式。操作系統(tǒng)教程課件第16頁4.3.1單一連續(xù)存儲管理

單一連續(xù)存儲管理是一種最簡單的存儲管理方式。在單一連續(xù)存儲管理方式下，操作系統(tǒng)占用一部分主存空間，其余的主存空間作為一個連續(xù)分區(qū)全部分配給一個作業(yè)使用，即在任何時刻主存儲器中最多只存有一個作業(yè)。這種存儲管理方式適合于單用戶、單任務的操作系統(tǒng)，在個人計算機和專用計算機系統(tǒng)中可采用。圖4-6所示為單一連續(xù)存儲管理的示意圖。操作系統(tǒng)教程課件第17頁4.3.1單一連續(xù)存儲管理

單一連續(xù)存儲管理每次只允許一個作業(yè)裝入主存儲器，因此可以不必考慮作業(yè)在主存中的移動問題，所以當作業(yè)被裝入主存時，系統(tǒng)一般采用靜態(tài)重定位方式進行地址轉換，當然也可以采用動態(tài)重定位方式。單一連續(xù)存儲管理方式下的存儲保護比較簡單，即判斷物理地址≥界限地址，并且物理地址≤主存最大地址，若條件成立，則可執(zhí)行，否則有地址錯誤，形成“地址越界”程序性中斷事件。當采用靜態(tài)重定位裝入方式時，由裝入程序檢查其物理地址是否超過界限地址，若是，則可以裝入；否則，將產(chǎn)生地址錯誤，程序不能裝入。這樣，一個被裝入的作業(yè)，總能保證在用戶區(qū)中執(zhí)行，避免破壞系統(tǒng)區(qū)中的信息，達到“存儲保護”的目的。操作系統(tǒng)教程課件第18頁4.3.1單一連續(xù)存儲管理單一連續(xù)存儲管理方式適用于單道程序系統(tǒng)，在20世紀70年代，由于小型計算機和微型計算機的主存容量有限，這種管理方式曾得到了廣泛應用，例如IBM7094FORTRAN監(jiān)督系統(tǒng)、CP/M系統(tǒng)、DJS0520系統(tǒng)等均采用了單一連續(xù)存儲管理方式，但采用這種管理方式存在幾個主要缺點：①CPU利用率比較低。當正在執(zhí)行的作業(yè)出現(xiàn)某個等待事件時，CPU便處于空閑狀態(tài)。②存儲器得不到充分利用。不管用戶作業(yè)的程序和數(shù)據(jù)量的多少，都是一個作業(yè)獨占主存的用戶區(qū)。③計算機的外圍設備利用率不高。操作系統(tǒng)教程課件第19頁4.3.2固定分區(qū)存儲管理操作系統(tǒng)教程課件第20頁固定分區(qū)存儲管理是預先把主存儲器中的用戶區(qū)分割成若干個連續(xù)區(qū)域，每一個連續(xù)區(qū)域稱為一個分區(qū)，每個分區(qū)的大小可以相同，也可以不同。但是一旦分割完成后，主存儲器中分區(qū)的個數(shù)固定不變，每個分區(qū)的大小固定不變。每個分區(qū)可以裝入一個作業(yè)，不允許一個作業(yè)跨分區(qū)存儲，也不允許多個作業(yè)同時存放在同一個分區(qū)中。因此，固定分區(qū)存儲管理適合多道程序設計系統(tǒng)。圖4-7所示為固定分區(qū)存儲管理方式的示意圖。

4.3.2固定分區(qū)存儲管理

1．空間的分配和去配為了管理各分區(qū)的分配和使用情況，系統(tǒng)需要設置一張“主存分配表”，以說明各分區(qū)的分配情況。一個系統(tǒng)中分區(qū)分配表的長度固定，由主存儲器中分區(qū)的個數(shù)所決定。主存分配表中記錄了各個分區(qū)的起始地址和長度，并為每個分區(qū)設一個狀態(tài)標志位，當狀態(tài)標志位為“0”時，表示該分區(qū)是空閑分區(qū)，當標志位為非“0”時，表示該分區(qū)已被占用。圖4-8表示主存儲器被劃分成四個分區(qū)，每個分區(qū)的大小并不相同，其中分區(qū)1、分區(qū)3和分區(qū)4分別被作業(yè)名為JOBA、JOBB和JOBC的作業(yè)所占用，分區(qū)2為空閑分區(qū)。

操作系統(tǒng)教程課件第21頁4.3.2固定分區(qū)存儲管理操作系統(tǒng)教程課件第22頁圖4-8四個分區(qū)的分區(qū)分配表4.3.2固定分區(qū)存儲管理

當作業(yè)隊列中有作業(yè)要求裝入主存時，存儲管理可采用“順序分配算法”進行主存空間的分配。分配時順序查找主存分配表，選擇標志位為“0”的分區(qū)，將作業(yè)的地址空間大小與該分區(qū)長度進行比較，如果能容納該作業(yè)，則將此分區(qū)分配給該作業(yè)，且在此分區(qū)的占用標志欄中填入該作業(yè)名。如果作業(yè)的地址空間大于此空閑分區(qū)的長度，則重復上述過程繼續(xù)查找，查找空閑區(qū)長度大于等于該作業(yè)的地址空間大小且標志位為“0”的空閑分區(qū)，若有，則分配，否則該作業(yè)暫時不能裝入主存儲器。圖4-9所示給出固定分區(qū)順序分配算法的流程。裝入后的作業(yè)在執(zhí)行結束后必須歸還所占用的分區(qū)。存儲管理根據(jù)作業(yè)名查找主存分配表，找到該作業(yè)所占用的分區(qū)，將該分區(qū)的狀態(tài)標志位重新設置為“0”，表示該分區(qū)現(xiàn)在是空閑區(qū)，可以裝入新的作業(yè)。

操作系統(tǒng)教程課件第23頁4.3.2固定分區(qū)存儲管理操作系統(tǒng)教程課件第24頁圖4-9固定分區(qū)順序分配算法流程4.3.2固定分區(qū)存儲管理

2．地址轉換和存儲保護固定分區(qū)存儲管理下，作業(yè)在執(zhí)行過程中是不會被改變存儲區(qū)域的，因此可以采用靜態(tài)重定位裝入方式裝入作業(yè)。由裝入程序把作業(yè)中的邏輯地址與分區(qū)的下限地址相加，得到對應的物理地址。當一個已經(jīng)被裝入主存的作業(yè)占有處理器運行時，進程調(diào)度程序將該作業(yè)所在分區(qū)的下限地址和上限地址分別存儲在處理器的“下限寄存器”和“上限寄存器”中。處理器執(zhí)行該作業(yè)指令時必須判斷：下限地址≤物理地址<上限地址如果物理地址在上、下限地址范圍內(nèi)，則可按物理地址訪問主存儲器；如果條件不成立，則產(chǎn)生“地址越界”的中斷事件，達到存儲保護的目的。作業(yè)運行結束時，調(diào)度程序選擇另一個可運行的作業(yè)，同時修改下限寄存器和上限寄存器的內(nèi)容，以保證處理器能控制該作業(yè)的正確執(zhí)行。

操作系統(tǒng)教程課件第25頁4.3.2固定分區(qū)存儲管理3．主存空間的利用率固定分區(qū)存儲管理方式總是為作業(yè)分配一個不小于作業(yè)地址空間的分區(qū)，因此在分區(qū)中產(chǎn)生一部分空閑區(qū)域，影響了主存空間的利用率。為了提高主存空間的利用率采用如下幾種方法：（1）根據(jù)經(jīng)常出現(xiàn)的作業(yè)的大小和頻率劃分分區(qū)。（2）劃分分區(qū)時按分區(qū)大小順序排列。（3）按作業(yè)對主存空間的需求量排成多個作業(yè)隊列，規(guī)定每個作業(yè)隊列中的各作業(yè)只能依次裝入對應的分區(qū)中；不同作業(yè)隊列中的作業(yè)分別依次裝入不同的分區(qū)中，不同的分區(qū)中可同時裝入作業(yè)；某作業(yè)隊列為“空”時，該作業(yè)隊列對應的分區(qū)也不能用來裝其他作業(yè)隊列中的作業(yè)。操作系統(tǒng)教程課件第26頁4.3.2固定分區(qū)存儲管理圖4-10為多個作業(yè)隊列的固定分區(qū)法。操作系統(tǒng)教程課件第27頁

采用多個作業(yè)隊列的固定分區(qū)法可以有效地防止小作業(yè)占用大分區(qū)，從而減少了閑置的主存空間量。但是如果分區(qū)劃分不合適，則會造成某個作業(yè)隊列經(jīng)常為空隊列，使對應分區(qū)經(jīng)常無作業(yè)被裝入，反而使分區(qū)的利用率不高。所以采用多個作業(yè)隊列的固定分區(qū)法時，可結合作業(yè)的大小和出現(xiàn)的頻率劃分分區(qū)，以達到更好的空間利用率。

4.3.3可變分區(qū)存儲管理

可變分區(qū)存儲管理并不是預先將主存儲器中的用戶區(qū)域劃分成若干個固定分區(qū)，而是在作業(yè)要求裝入主存時，根據(jù)作業(yè)需要的地址空間的大小和當時主存空間的實際使用情況決定是否為該作業(yè)分配一個分區(qū)。如果有足夠的連續(xù)空間，則按需要分割一部分空間分區(qū)給該作業(yè)；否則令其等待主存空間。所以，在可變分區(qū)存儲管理中，主存儲器中分區(qū)的大小是可變的，根據(jù)作業(yè)的實際需求進行分區(qū)的劃分；主存中分區(qū)的個數(shù)是可變的，隨著裝入主存的作業(yè)數(shù)量而變化；主存中的空閑分區(qū)個數(shù)也隨著作業(yè)的裝入與撤離而發(fā)生變化。圖4-11是可變分區(qū)存儲管理方式的存儲空間分配示意圖。操作系統(tǒng)教程課件第28頁4.3.3可變分區(qū)存儲管理操作系統(tǒng)教程課件第29頁圖4-11可變分區(qū)存儲分配與回收示意圖4.3.3可變分區(qū)存儲管理

1．空間的分配和去配系統(tǒng)初始時，把主存中整個用戶區(qū)看作一個大的空閑分區(qū)。當作業(yè)要求裝入主存時，系統(tǒng)根據(jù)作業(yè)對主存空間的實際需求量進行分配。圖4-11（a）給出了作業(yè)被裝入時主存空間分配的情況。裝入主存儲器中的作業(yè)執(zhí)行結束后，它所占用的分區(qū)被收回，成為一個新的空閑區(qū)，可以用來裝入新的作業(yè)。隨著作業(yè)不斷的裝入和作業(yè)執(zhí)行完后的撤離，主存儲區(qū)被分成若干分區(qū)，其中有的分區(qū)被作業(yè)占用，有的分區(qū)空閑。圖4-11（b）給出了作業(yè)被裝入、執(zhí)行結束后撤離的主存空間分配情況。4.3.3可變分區(qū)存儲管理1.可變分區(qū)數(shù)據(jù)結構采用可變分區(qū)存儲管理方式管理諸存儲空間時，主存中已占用分區(qū)和空閑區(qū)的數(shù)目和大小都是可變的。為了實現(xiàn)可變分區(qū)存儲管理，系統(tǒng)必須設置相應的數(shù)據(jù)結構，用來描述空閑分區(qū)和已分配分區(qū)的情況，為系統(tǒng)空間分配提供依據(jù)。常用的數(shù)據(jù)結構有以下兩種形式。（1）分區(qū)表。系統(tǒng)設置“空閑分區(qū)表”和“已分配分區(qū)表”，用來描述空閑分區(qū)和已分配分區(qū)的情況，為系統(tǒng)空間分配提供依據(jù)。已分配分區(qū)表記錄已裝入的作業(yè)在主存空間中占用分區(qū)的始址和長度，用標志位指出占用該分區(qū)的作業(yè)名。空閑分區(qū)表記錄主存中可供分配的空閑分區(qū)的始址和長度，用標志位指出該分區(qū)是未分配的空閑分區(qū)。操作系統(tǒng)教程課件第31頁4.3.3可變分區(qū)存儲管理

圖4-12為可變分區(qū)存儲管理方式的主存分配表。系統(tǒng)按一定的規(guī)則組織主存分配表，當作業(yè)要求裝入時，從空閑分區(qū)表查找一個長度大于作業(yè)要求的空閑分區(qū)。操作系統(tǒng)教程課件第32頁4.3.3可變分區(qū)存儲管理

（2）分區(qū)鏈。為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分，設置一些用于控制分區(qū)分配的信息，以及用于鏈接前一個分區(qū)的前向指針；在分區(qū)尾部則設置一后向指針，通過前、后向鏈接指針，可以將所有的空閑分區(qū)聯(lián)結成一個雙向鏈。為了檢索的方便，在分區(qū)尾部重復設置狀態(tài)位和分區(qū)大小表目。如圖4-13所示。操作系統(tǒng)教程課件第33頁4.3.3可變分區(qū)存儲管理

2.可變分區(qū)分配算法將一個作業(yè)裝入主存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一個分區(qū)分配給該作業(yè)?？勺兎謪^(qū)存儲管理常用的空間分配算法有：“最先適應”分配算法、“最優(yōu)適應”分配算法和“最壞適應”分配算法。以下以空閑分區(qū)表為例說明各種算法。操作系統(tǒng)教程課件第34頁4.3.3可變分區(qū)存儲管理

（1）最先適應分配算法最先適應分配算法在主存空間分配時，總是順序查找空閑分區(qū)表，選擇第一個滿足作業(yè)地址空間要求的空閑分區(qū)進行分割，一部分分配給作業(yè)，而剩余部分仍為空閑分區(qū)。最先適應分配算法實現(xiàn)簡單，但是經(jīng)過若干次作業(yè)的裝入與撤離后，有可能把較大的主存空間分割成若干個小的、不連續(xù)的新空閑分區(qū)，這些空閑分區(qū)的長度可能比較小，不能滿足主存再次分配的需要，從而使主存空間的利用率大大降低，這些空閑分區(qū)稱為“碎片”。操作系統(tǒng)教程課件第35頁4.3.3可變分區(qū)存儲管理

（2）最優(yōu)適應分配算法 最優(yōu)適應分配算法總是選擇一個滿足作業(yè)地址空間要求的最小空閑分區(qū)進行分配，這樣每次分配后總能保留下較大的分區(qū)，使裝入大作業(yè)時比較容易獲得滿足。在實現(xiàn)過程中，空閑分區(qū)按其長度以遞增順序登記在空閑分區(qū)表中。這樣，系統(tǒng)分配時順序查找空閑分區(qū)表，找到的第一個滿足作業(yè)空間要求的空閑分區(qū)一定是能夠滿足該作業(yè)要求的所有分區(qū)中的最小一個分區(qū)。采用最優(yōu)適應分配算法，每次分配后分割的剩余空間總是最小的，這樣形成的“碎片”非常“零散”，往往難以再次分配使用，從而影響了主存空間的利用率。操作系統(tǒng)教程課件第36頁4.3.3可變分區(qū)存儲管理（3）最壞適應分配算法最壞適應分配算法與最優(yōu)適應分配算法相反，總是選擇一個滿足作業(yè)地址空間要求的最大空閑分區(qū)進行分割，按作業(yè)需要的空間大小進行分配給作業(yè)使用后，剩余部分的空間不致于太小，仍然可以供系統(tǒng)再次分配使用。這種分配算法對中小型作業(yè)是有利的。實現(xiàn)最壞適應分配算法時，空閑分區(qū)按其長度以遞減順序登記在空閑分區(qū)表中。系統(tǒng)分配時順序查找空閑分區(qū)表，表中的第一個登記項即對應著當前主存的最大空閑分區(qū)。同樣，當作業(yè)歸還主存空間時，則需要按分區(qū)的大小按遞減順序登記到空閑分區(qū)表的適當位置。操作系統(tǒng)教程課件第37頁4.3.3可變分區(qū)存儲管理操作系統(tǒng)教程課件第38頁圖4-14可變分區(qū)分配算法示例4.3.3可變分區(qū)存儲管理裝入的作業(yè)執(zhí)行結束后，它所占據(jù)的分區(qū)將被回收，回收后的空閑分區(qū)登記在空閑分區(qū)表中，用來裝入新的作業(yè)?；厥湛臻g時應檢查是否存在與回收區(qū)相鄰的空閑分區(qū)，如果有，則將其合并成為一個新的空閑分區(qū)進行登記管理。一個回收區(qū)可能存在上鄰空閑分區(qū)，也可能存在下鄰空閑分區(qū)，或既存在上鄰又存在下鄰空閑分區(qū)，或既無上鄰又無下鄰空閑分區(qū)，如圖4-15所示。假定作業(yè)歸還的分區(qū)始址為S，長度為L。操作系統(tǒng)教程課件第39頁4.3.3可變分區(qū)存儲管理操作系統(tǒng)教程課件第40頁圖4-15主存回收示意圖4.3.3可變分區(qū)存儲管理圖4-16給出了合并下鄰/上鄰空閑分區(qū)的回收算法流程。

4.3.3可變分區(qū)存儲管理

2．地址轉換和存儲保護采用可變分區(qū)存儲管理方式，一般均采用動態(tài)重定位方式裝入作業(yè)。為使地址的轉換不影響到指令的執(zhí)行速度，必須有硬件地址轉換機構的支持。硬件地址轉換機構包括兩個專用控制寄存器：基址寄存器和限長寄存器，以及一些加法、比較線路等?；芳拇嫫饔脕泶娣抛鳂I(yè)所占分區(qū)的起始地址，限長寄存器用來存放作業(yè)所占分區(qū)長度。

4.3.3可變分區(qū)存儲管理正在運行的作業(yè)所占分區(qū)的起始地址和長度被送入基址寄存器和限長寄存器中。執(zhí)行過程中，處理器每執(zhí)行一條指令都要將該指令的邏輯地址與限長寄存器中的值進行比較，當邏輯地址小于限長值時，則把邏輯地址與基址寄存器的值相加就可得到對應的物理地址。當邏輯地址大于限長寄存器中的限長值時，表示欲訪問的地址超出了所分配的分區(qū)范圍，這時形成一個“地址越界”的程序性中斷事件，達到存儲保護的目的。圖4-17示出了可變分區(qū)存儲管理的地址轉換示例。操作系統(tǒng)教程課件第43頁4.3.3可變分區(qū)存儲管理

3移動技術采用可變分區(qū)存儲管理主存時，可采用移動技術使分散的空閑分區(qū)集中起來以容納新的作業(yè)，如圖4-18所示。

移動技術為作業(yè)執(zhí)行過程中擴充主存空間提供方便，一道作業(yè)在執(zhí)行中要求增加主存量時，只要適當移動鄰近的作業(yè)就可增加它所占的分區(qū)長度。移動可以集中分散的空閑分區(qū)，提高主存空間的利用率，移動也為作業(yè)動態(tài)擴充主存空間提供了方便。但是，采用移動技術時必須注意：（1）移動會增加系統(tǒng)開銷。（2）移動是有條件的。操作系統(tǒng)教程課件第45頁4.3.3可變分區(qū)存儲管理采用移動技術時應該盡量減少移動的作業(yè)數(shù)和信息量，以降低系統(tǒng)的開銷、提高系統(tǒng)的效率。圖4-19給出了兩種作業(yè)裝入主存的方式。操作系統(tǒng)教程課件第46頁4.3.4覆蓋與交換技術覆蓋技術和交換技術是在多道環(huán)境下用來擴充主存的兩種方法。這兩種技術都是用來解決主存容量不足及有效利用主存的方法。覆蓋技術主要用于早期的操作系統(tǒng)中，而交換技術在現(xiàn)代操作系統(tǒng)中仍有較強的生命力。單一連續(xù)存儲管理和分區(qū)存儲管理對作業(yè)的大小都有嚴格的限制，當作業(yè)要求運行時，系統(tǒng)將作業(yè)的全部信息一次裝入主存，并一直駐留在主存直至運行結束。當作業(yè)的大小大于主存可用空間時，該作業(yè)就無法運行，這就限制了計算機系統(tǒng)上開發(fā)較大程序的可能。覆蓋和交換技術是解決大作業(yè)與小主存矛盾的兩種存儲管理技術，他們實質(zhì)上是對主存進行了邏輯擴充。操作系統(tǒng)教程課件第47頁4.3.4覆蓋與交換技術覆蓋技術的基本思想是一個程序不需要把所有的指令和數(shù)據(jù)都裝入主存。可以把程序劃為若干功能上相對獨立的程序段，讓那些不會同時執(zhí)行的程序段共享一塊主存。這樣使用戶看起來好像主存擴大了，從而達到了主存擴充的目的。將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐主存；可選部分（不常用功能）在其他程序模塊中實現(xiàn)，平時存放在外存中（覆蓋文件），在需要用到時才裝入到主存；不存在調(diào)用關系的模塊不必同時裝入到主存，從而可以相互覆蓋(即不同時用的模塊可共用一個分區(qū))。把可以相互覆蓋的程序段叫做覆蓋，可共享的主存區(qū)叫做覆蓋區(qū)。操作系統(tǒng)教程課件第48頁4.3.4覆蓋與交換技術操作系統(tǒng)教程課件第49頁圖4-20覆蓋技術示意圖4.3.4覆蓋與交換技術為了實現(xiàn)覆蓋管理，系統(tǒng)必須提供相應的覆蓋管理控制程序。當作業(yè)裝入運行時，由系統(tǒng)根據(jù)用戶提供的覆蓋結構進行覆蓋處理。當程序中引用當前尚未裝入覆蓋區(qū)的覆蓋中的例程時，則調(diào)用覆蓋管理控制程序，請求將所需的覆蓋裝入覆蓋區(qū)中，系統(tǒng)響應請求，并自動將所需覆蓋裝入主存覆蓋區(qū)中。覆蓋技術打破了必須將一個作業(yè)的全部信息裝入主存后才能運行的限制。在一定程度上解決了小主存運行大作業(yè)的矛盾。但是，采用覆蓋技術編程時必須劃分程序模塊和確定程序模塊之間的覆蓋關系，增加了編程復雜度；從外存裝入覆蓋文件，是以時間延長來換取空間節(jié)省。操作系統(tǒng)教程課件第50頁交換最早用在麻省理工學院的兼容分時系統(tǒng)CTSS中，其基本思想是把主存中暫時不能運行的進程或暫時不使用的程序和數(shù)據(jù)換出到外存，以騰出足夠的主存空間，把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)換入主存。交換技術并不要求程序員做特殊的工作。交換完全由操作系統(tǒng)進行，整個過程對進程是透明的。交換的對象可以是整個進程，此時成為“整體交換”或“進程交換”。圖4-21為作業(yè)交換的示意圖。操作系統(tǒng)教程課件第51頁4.3.4覆蓋與交換技術4.3.4覆蓋與交換技術實現(xiàn)交換技術需要后援存儲器，通常是硬盤，它必須具備兩個顯著的特征：數(shù)據(jù)傳輸快，容量足夠大。交換技術主要是在進程或作業(yè)之間進行，而覆蓋則主要是在同一個作業(yè)或進程內(nèi)進行。

操作系統(tǒng)教程課件第52頁4.4頁式存儲管理

連續(xù)分配方式要求作業(yè)一次性、連續(xù)裝入在主存空間，對空間的要求較高，而且可能形成很多“碎片”，雖然可以通過移動技術將零散的空閑分區(qū)匯集成可用的大塊空間，但需要增加系統(tǒng)的額外開銷。如果采用不連續(xù)存儲的方式，把邏輯地址連續(xù)的作業(yè)分散存放到幾個不連續(xù)的主存區(qū)域中，并能保證作業(yè)的正確執(zhí)行。這樣既可充分利用主存空間，減少主存的碎片，又可避免移動所帶來的額外開銷。操作系統(tǒng)教程課件第53頁4.4.1基本原理

頁式存儲管理是把主存儲器劃分成大小相等的若干區(qū)域，每個區(qū)域稱為一塊，并對它們加以順序編號，如0#塊、1#塊等等。與此對應，用戶程序的邏輯地址空間劃分成大小相等的若干頁，同樣為它們加以順序編號，從0開始，如第0頁、第1頁等。頁的大小與塊的大小相等。分頁式存儲管理的邏輯地址由兩部分組成：頁號和頁內(nèi)地址。其格式為：操作系統(tǒng)教程課件第54頁頁內(nèi)地址W頁號P31121104.4.2存儲空間的分配與去配

分頁式存儲管理把主存空間劃分成若干塊，以塊為單位進行主存空間的分配。由于塊的大小是固定的，系統(tǒng)可以采用一張主存分配表來記錄已分配的塊、尚未分配的塊以及當前剩余的空閑塊總數(shù)。最簡單的辦法可用一張“位示圖”來記錄主存的分配情況。例如主存的用戶區(qū)被劃分成512塊，則可用字長為32位的16個字的位示圖來構成一張主存分配表，位示圖中的每一位與一個物理塊對應，用0/1表示對應塊的占用標志（空閑/已占用），另用一個字節(jié)記錄當前系統(tǒng)的剩余空閑塊總數(shù)，如圖4-22所示。操作系統(tǒng)教程課件第55頁4.4.2存儲空間的分配與去配操作系統(tǒng)教程課件第56頁進行主存分配時，首先查看空閑塊總數(shù)是否能夠滿足作業(yè)要求，若不能滿足，則不進行分配；若能滿足，則從位示圖中找出為“0”的位，并且將其占用標志置為“1”，并從空閑塊總數(shù)中減去本次占用的塊數(shù)，按找到的位計算出對應的塊號，建立該作業(yè)的頁表，并把作業(yè)裝入對應的物理塊中。4.4.2存儲空間的分配與去配

由于每一塊的大小相等，在位示圖中查找到一個為“0”的位后，根據(jù)它所在的字號、位號，按如下公式可計算出對應的塊號：塊號＝字號×字長＋位號當一個作業(yè)執(zhí)行結束時，則應該收回作業(yè)所占的主存塊。根據(jù)歸還的塊號計算出該塊在位示圖中對應的位置，將占用標志修改為“0”，同時把歸還塊數(shù)加入到空閑塊總數(shù)中。假定歸還塊的塊號為i，則在位示圖中對應的位置為：字號＝[i/字長]，位號＝imod字長其中[]表示對i除以字長后取其整數(shù)，而mod表示對i除以字長后取其余數(shù)部分。

操作系統(tǒng)教程課件第57頁4.4.3頁表與地址轉換在分頁式存儲管理系統(tǒng)中，允許將作業(yè)的每一頁離散地存儲在主存的物理塊中，但系統(tǒng)必須能夠保證作業(yè)的正確運行，即能在主存中找到每個頁面所對應的物理塊。為此，系統(tǒng)為每個作業(yè)建立了一張頁面映像表，簡稱頁表。頁表實現(xiàn)了從頁號到主存塊號的地址映像。作業(yè)中的所有頁（0~n）依次地在頁表中記錄了相應頁在主存中對應的物理塊號，如圖4-23所示。頁表的長度由進程或作業(yè)擁有的頁面數(shù)決定。操作系統(tǒng)教程課件第58頁4.4.3頁表與地址轉換操作系統(tǒng)教程課件第59頁圖4-23頁表示意圖4.4.3頁表與地址轉換操作系統(tǒng)教程課件第60頁頁式存儲管理采用動態(tài)重定位方式裝入作業(yè)，作業(yè)執(zhí)行時通過硬件的地址轉換機構實現(xiàn)從用戶空間中的邏輯地址到主存空間中物理地址的轉換工作。由于頁內(nèi)地址和物理塊內(nèi)的地址是一一對應的。因此，地址變換機構的任務，實際上是將邏輯地址中的頁號，轉換成為主存中的物理塊號。頁表是硬件進行地址轉換的依據(jù)。4.4.3頁表與地址轉換

調(diào)度程序在選擇作業(yè)后，將選中作業(yè)的頁表始址送入硬件設置的頁表控制寄存器中。地址轉換時，只要從頁表寄存器中就可找到相應的頁表。當作業(yè)執(zhí)行時，分頁地址變換機構會自動將邏輯地址分為頁號和頁內(nèi)地址兩部分，以頁號位索引檢索頁表，如果頁表中無此頁號，則產(chǎn)生一個“地址錯”的程序性中斷事件；如果頁表中有此頁號，則可得到對應的主存塊號，再按邏輯地址中的頁內(nèi)地址計算出欲訪問的主存單元的物理地址。因為塊的大小相等，所以物理地址=塊號×塊長＋頁內(nèi)地址圖4-24給出分頁式存儲管理的地址變換機構示例。操作系統(tǒng)教程課件第61頁4.4.3頁表與地址轉換操作系統(tǒng)教程課件第62頁圖4-24分頁系統(tǒng)的地址變換機構示意圖4.4.4快表由于頁表是存放在主存儲器中的，這樣取一個數(shù)據(jù)或指令至少需要訪問主存兩次以上。第一次是訪問主存中的頁表，查找到指定頁面所對應的物理塊號，將塊號與頁內(nèi)地址拼接，計算出數(shù)據(jù)或指令的物理地址。第二次訪問主存時，根據(jù)第一次得到的物理地址進行數(shù)據(jù)的存取操作。為了提高存取速度，可以設想把頁表存放在一組寄存器中，但寄存器成本太高，數(shù)量有限，不可行。通常在地址變換機構中增設一個具有并行查找能力的小容量高速緩沖寄存器，又稱“相聯(lián)寄存器”。利用高速緩沖寄存器存放頁表的一部分，把存放在高速緩沖寄存器中的這部分頁表稱“快表”?？毂碇械怯浟水斍皥?zhí)行程序中最常用的頁號與主存中塊號的對應關系，圖4-25給出具有快表的地址變換機構示例。操作系統(tǒng)教程課件第63頁4.4.4快表操作系統(tǒng)教程課件第64頁圖4-25具有快表的地址變換機構示意圖4.4.5頁的共享與保護

采用頁式存儲管理能方便地實現(xiàn)程序和數(shù)據(jù)的共享。在多道程序系統(tǒng)中，編譯程序、編輯程序、解釋程序、公共子程序、公共數(shù)據(jù)等都是可共享的，這些共享的信息在主存儲器中只需要保留一個副本，大大提高了主存空間的利用率。在實現(xiàn)共享時，必須區(qū)分數(shù)據(jù)的共享和程序的共享。實現(xiàn)數(shù)據(jù)共享時，可允許不同的作業(yè)對共享的數(shù)據(jù)頁采用不同頁號，只需要將各自的有關表目指向共享的數(shù)據(jù)信息塊即可。而實現(xiàn)程序共享時，由于頁式存儲結構要求邏輯地址空間是連續(xù)的，所以在程序運行前它們的頁號是確定的。操作系統(tǒng)教程課件第65頁4.4.5頁的共享與保護圖4-26所示給出了兩個作業(yè)共享一個程序和一個數(shù)據(jù)段的情況。操作系統(tǒng)教程課件第66頁4.5段式存儲管理

用戶編制的程序是由若干段組成的：一個程序可以由一個主程序、若干子程序、符號表、棧以及數(shù)據(jù)等若干段組成。每一段都有獨立、完整的邏輯意義，每一段程序都可獨立編制，且每一段的長度可以不同。段式存儲管理支持用戶的分段觀點，具有邏輯上的清晰和完整性，它以段為單位進行存儲空間的管理。操作系統(tǒng)教程課件第67頁4.5.1原理每個作業(yè)由若干個相對獨立的段組成，每個段都有一個段名，為了實現(xiàn)簡單，通常可用段號代替段名，段號從“0”開始，每一段的邏輯地址都從“0”開始編址，段內(nèi)地址是連續(xù)的，而段與段之間的地址是不連續(xù)的。其邏輯地址由段號和段內(nèi)地址兩部分所組成：操作系統(tǒng)教程課件第68頁段內(nèi)地址W段號S31161504.5.2空間的分配與去配

分段式存儲管理是在可變分區(qū)存儲管理方式的基礎上發(fā)展而來的。在分段式存儲管理方式中，以段為單位進行主存分配，每一個段在主存中占有一個連續(xù)空間，但各個段之間可以離散地存放在主存不同的區(qū)域中。為了使程序能正常運行，即能從主存中正確找出每個段所在的分區(qū)位置，系統(tǒng)為每個進程建立一張段映射表，簡稱“段表”。每個段在表中占有一個表項，記錄該段在主存儲器中的起始地址和長度，如圖4-27所示。段表實現(xiàn)了從邏輯段到主存空間之間的映射。操作系統(tǒng)教程課件第69頁4.5.2空間的分配與去配操作系統(tǒng)教程課件第70頁圖4-27段的裝入示意圖4.5.2空間的分配與去配

如果在裝入某段信息時找不到滿足該段地址空間大小的空閑區(qū)，則可采用移動技術合并分散的空閑區(qū)，以利于大作業(yè)的裝入。當采用分段式存儲管理的作業(yè)執(zhí)行結束后，它所占據(jù)的主存空間將被回收，回收后的主存空間登記在空閑分區(qū)表中，可以用來裝入新的作業(yè)。系統(tǒng)在回收空間時同樣需要檢查是否存在與回收區(qū)相鄰的空閑分區(qū)，如果有，則將其合并成為一個新的空閑分區(qū)進行登記管理。段表存放在主存儲器中，在訪問一個數(shù)據(jù)或指令時至少需要訪問主存兩次以上。為了提高對段表的存取速度，通常增設一個相聯(lián)寄存器，利用高速緩沖寄存器保存最近常用的段表項。

操作系統(tǒng)教程課件第71頁4.5.3地址轉換與存儲保護

段式存儲管理采用動態(tài)重定位方式裝入作業(yè)，作業(yè)執(zhí)行時通過硬件的地址轉換機構實現(xiàn)從邏輯地址到物理地址的轉換工作，段表的表目起到了基址寄存器和限長寄存器的作用，是硬件進行地址轉換的依據(jù)。圖4-28給出分段式存儲管理的地址變換示例。

操作系統(tǒng)教程課件第72頁4.5.4段的共享

由于段是按邏輯意義來劃分的，可以按段名進行訪問，因此分段式存儲管理系統(tǒng)的一個突出優(yōu)點，是可以方便地實現(xiàn)段的共享，即允許若干個進程共享一個或多個段。為實現(xiàn)某段代碼的共享，在分段式存儲管理系統(tǒng)中，各個進程對共享段使用相同的段名，在各自的段表中填入共享段的起始地址，并置以適當?shù)淖x寫控制權，即可做到共享一個邏輯上完整的主存段信息。例如一個多用戶系統(tǒng)，可同時接納40個用戶，他們都需要執(zhí)行一個文本編輯程序（TextEditor）。如果文本編輯程序有160KB的代碼和40KB的數(shù)據(jù)區(qū)，則總共需要8MB的主存空間來支持40個用戶的訪問。如果160KB的代碼是可重入的，則該代碼只需要在主存中保留一份文本編輯程序的副本，此時所需要的主存空間僅為1760KB（40×40+160），只需要在每個進程的段表中為文本編輯程序設置一個段表項。

操作系統(tǒng)教程課件第73頁4.5.4段的共享操作系統(tǒng)教程課件第74頁圖4-29段的共享示意圖4.5.4段的共享

在多道程序設計系統(tǒng)中，由于進程的并發(fā)執(zhí)行，一個程序段為多個進程共享時，有可能出現(xiàn)多次同時重復執(zhí)行該段程序的情況，而該共享程序段的指令和數(shù)據(jù)在執(zhí)行過程中是不能被修改的。此外，共享段也有可能被置換出主存，顯然，一個正在被某個進程使用或即將被某個進程使用的共享段是不應該置換出主存的，因此可以在段表中設置共享位來判別該段是否正在被某個進程調(diào)用。操作系統(tǒng)教程課件第75頁4.5.5分頁和分段存儲管理的主要區(qū)別分頁和分段系統(tǒng)都采用離散分配主存方式，都需要通過地址映射機構來實現(xiàn)地址變換，有許多相似之處。但兩者又是完全不同的。具體表現(xiàn)如下。①頁是信息的物理單位，是系統(tǒng)管理的需要而不是用戶的需要；而段則是信息的邏輯單位，它含有一組意義相對完整的信息，分段是為了更好地滿足用戶的需要。②頁的大小固定且由系統(tǒng)決定，因而一個系統(tǒng)只能有一種大小的頁面；而段的長度卻不固定，由用戶所編寫的程序決定，通常由編譯程序對源程序進行編譯時根據(jù)信息的性質(zhì)來劃分。③分頁式作業(yè)的地址空間是一維的，頁間的邏輯地址是連續(xù)的；而分段式作業(yè)的地址空間則是二維的，段間的邏輯地址是不連續(xù)的。操作系統(tǒng)教程課件第76頁4.6段頁式存儲管理

段式存儲管理支持了用戶的觀點，但每段必須占據(jù)主存儲器的連續(xù)區(qū)域，有可能需要采用移動技術匯集主存空間，為此，兼用分段和分頁的方法，構成可分頁的段式存儲管理，通常被稱為是“段頁式存儲管理”。段頁式存儲管理兼顧了段式在邏輯上的清晰和頁式在管理上方便的優(yōu)點。用戶對作業(yè)采用分段組織，每段獨立編程，在主存空間分配時，再把每段分成若干個頁面，這樣每段不必占據(jù)連續(xù)的主存空間，可把它按頁存放在不連續(xù)的主存塊中。段頁式存儲管理的邏輯地址格式如下：操作系統(tǒng)教程課件第77頁4.6段頁式存儲管理

段頁式存儲管理為每一個裝入主存的作業(yè)建立一張段表，且對每一段建立一張頁表。段表的長度由作業(yè)分段的個數(shù)決定，段表中的每一個表目指出本段頁表的始址和長度。頁表的長度則由對應段所劃分的頁面數(shù)所決定，頁表中的每一個表目指出本段的邏輯頁號與主存物理塊號之間的對應關系。段頁式存儲管理中段表、頁表之間的關系如圖4-30所示。操作系統(tǒng)教程課件第78頁4.6段頁式存儲管理

執(zhí)行指令時，地址機構根據(jù)邏輯地址中的段號查找段表，得到該段的頁表始址，然后根據(jù)邏輯地址中的頁號查找該頁表，得到對應的主存塊號，由主存塊號與邏輯地址中的頁內(nèi)地址形成可訪問的物理地址。如果邏輯地址中的段號超出了段表中的最大段號或者頁號超出了該段頁表中的最大頁號，都將形成“地址越界”的程序性中斷事件?？梢钥闯?，由邏輯地址到物理地址的變換過程中，需要三次訪問主存，第一次是訪問主存中的段表，獲得該段對應頁表的始址，第二次是訪問頁表，獲得指令或數(shù)據(jù)的物理地址，最后再按物理地址存取信息。段頁式存儲管理的地址轉換機構如圖4-31所示。操作系統(tǒng)教程課件第79頁4.6段頁式存儲管理操作系統(tǒng)教程課件第80頁圖4-31段頁式存儲管理的地址轉換機構示意圖4.7虛擬存儲管理方式前面所介紹的各種存儲管理方式具有一個共同的特點，即作業(yè)必須一次性全部裝入主存空間后才能運行，直至作業(yè)運行結束后才釋放所占有的全部主存資源。這樣就會出現(xiàn)以下情況：（1）當主存空間不能滿足作業(yè)地址空間要求時，作業(yè)就不能裝入主存，無法運行。（2）當有大量作業(yè)要求運行時，由于主存容量有限，只能將少數(shù)作業(yè)裝入主存運行，而其他作業(yè)留在輔存上等待。

操作系統(tǒng)教程課件第81頁4.7虛擬存儲管理方式

早在1968年，Denning.P就曾指出：程序執(zhí)行時呈現(xiàn)出局部性特征，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；而它所訪問的存儲空間也局限在某個區(qū)域中。局限性表現(xiàn)在時間局限性和空間局限性兩方面。（１）時間局限性：如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問，則不久以后該數(shù)據(jù)可能再次被訪問。例如程序中存在著的大量的迭代循環(huán)、臨時變量和子程序調(diào)用等。（２）空間局限性：一旦程序訪問了某個存儲單元，在不久以后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)。例如對數(shù)組、表或數(shù)據(jù)堆棧進行操作。

4.7.1虛擬存儲器基于局部性原理，可以把作業(yè)信息保存在磁盤上，當作業(yè)請求裝入時，只需將當前運行所需要的一部分信息先裝入主存，作業(yè)執(zhí)行過程時，如果所要訪問的信息已調(diào)入主存，則可繼續(xù)執(zhí)行；如果信息尚未裝入主存，再將這些信息調(diào)入主存，使程序繼續(xù)執(zhí)行；如果此時主存已滿，無法再裝入新的信息，則系統(tǒng)將主存中暫時不用的信息置換到磁盤上，騰出主存空間后，再將所需要的信息調(diào)入主存，使程序繼續(xù)執(zhí)行。這樣，可使一個大的用戶程序得以在比較小的主存空間中運行，也可以在主存中同時裝入更多的作業(yè)使它們并發(fā)執(zhí)行。這不僅使主存空間能充分地被利用，而且用戶編制程序時可以不必考慮主存儲器的實際容量，允許用戶的邏輯地址空間大于主存的實際容量。從用戶的角度來看，好像計算機系統(tǒng)提供了一個容量很大的主存儲器，我們稱它為“虛擬存儲器”。

操作系統(tǒng)教程課件第83頁4.7.1虛擬存儲器虛擬存貯器指一種實際上并不存在的虛假存貯器，它是系統(tǒng)為了滿足應用對存貯器容量的巨大需求而構造的一個非常大的地址空間。它使用戶在編程時無需擔心存貯器之不足，好像有一個無限大的存貯器供其使用一樣。虛擬存儲器是建立在離散分配的存儲管理方式的基礎上，它允許將一個作業(yè)分多次調(diào)入主存。虛擬存儲器實際上是為了擴大主存容量而采用的一種設計技巧，虛擬存儲器的容量由計算機的地址結構和輔助存儲器的容量所決定，與實際主存儲器的容量無關，其邏輯容量由主存和輔存容量之和決定，其運行速度接近于主存儲器的速度，而每位的成本卻又接近輔助存儲器?？梢?，虛擬存儲技術是一種性能非常優(yōu)越的存儲器管理技術。操作系統(tǒng)教程課件第84頁4.7.1虛擬存儲器

虛擬存儲器具有離散性、多次性、對換性和虛擬性四大主要特征。1、離散性2、多次性3、對換性4、虛擬性

操作系統(tǒng)教程課件第85頁4.7.2請求分頁式存儲管理請求分頁式存儲管理是在頁式存儲管理的基礎上，增加請求分頁功能和頁面置換功能實現(xiàn)的虛擬存儲系統(tǒng)。請求分頁式存儲管理允許作業(yè)只裝入部分頁面，就啟動運行，在執(zhí)行過程中，如果所要訪問的頁已調(diào)入主存，則進行地址轉換，得到欲訪問的主存物理地址；如果所要訪問的頁面不在主存中，則產(chǎn)生一個“缺頁中斷”，如果此時主存能容納新頁，則啟動磁盤I/O將其調(diào)入主存；如果主存已滿，則通過頁面置換功能將當前所需的頁面調(diào)入。操作系統(tǒng)教程課件第86頁4.7.2請求分頁式存儲管理

1.請求分頁式存儲的管理為了實現(xiàn)請求分頁和頁面置換功能，系統(tǒng)必須提供必要的硬件支持和相應的軟件支持。一般需要以下支持：

◆請求分頁的頁表機制

◆缺頁中斷機構

◆地址變換機構

◆頁面置換算法

操作系統(tǒng)教程課件第87頁4.7.2請求分頁式存儲管理（1）頁表機制請求分頁式存儲管理的主要依據(jù)就是頁表。由于只是將作業(yè)的部分頁面調(diào)入主存，其余部分仍存放在輔助存儲器上，因此必須指出哪些頁面已在主存，哪些頁面還沒有裝入。為此需要將頁表增加若干項，修改后的頁表格式如下所示：操作系統(tǒng)教程課件第88頁4.7.2請求分頁式存儲管理

（2）缺頁中斷機構請求分頁式存儲管理中，當所要訪問的頁面不在主存時，則由硬件發(fā)出一個缺頁中斷，操作系統(tǒng)必須處理這個中斷，將所需要的頁面調(diào)入主存，圖4-32給出缺頁中斷處理的流程。在處理缺頁中斷的過程中，同樣需要保護現(xiàn)場、分析中斷源、轉入中斷處理程序進行處理、恢復現(xiàn)場等步驟，但缺頁中斷又與一般的中斷有著明顯的區(qū)別，主要表現(xiàn)在：操作系統(tǒng)教程課件第89頁4.7.2請求分頁式存儲管理操作系統(tǒng)教程課件第90頁圖4-32缺頁中斷處理流程4.7.2請求分頁式存儲管理

在處理缺頁中斷的過程中，同樣需要保護現(xiàn)場、分析中斷源、轉入中斷處理程序進行處理、恢復現(xiàn)場等步驟，但缺頁中斷又與一般的中斷有著明顯的區(qū)別，主要表現(xiàn)在：1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號。通常，CPU在一條指令結束后接收中斷請求并響應。而缺頁中斷則是在指令執(zhí)行期間，所要訪問的指令或數(shù)據(jù)不在主存時所產(chǎn)生和處理的。2）一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷。操作系統(tǒng)教程課件第91頁4.7.2請求分頁式存儲管理

3）地址變換機構在請求分頁式存儲管理中，當作業(yè)訪問某頁時，硬件的地址轉換機構首先查找快表，若找到，并且其狀態(tài)位為“1”，則按指定的物理塊號進行地址轉換，得到其對應的物理地址；若該頁的狀態(tài)位為“0”，則由硬件發(fā)出一個“缺頁中斷”，按照頁表中指出的輔存地址，由操作系統(tǒng)將其調(diào)入主存，并在頁表中填上其分配的物理塊號，修改狀態(tài)位、訪問位，對于寫指令，置修改位為“1”，然后按頁表中的物理塊號和頁內(nèi)地址形成物理地址，圖4-34給出請求分頁式存儲管理中的地址變換過程。如果在快表中未找到該頁的頁表項時，則到主存中查找頁表，若該頁尚未調(diào)入主存，系統(tǒng)產(chǎn)生缺頁中斷，請求操作系統(tǒng)將該頁面調(diào)入，同時將此頁表項寫入快表。

操作系統(tǒng)教程課件第92頁4.7.2請求分頁式存儲管理操作系統(tǒng)教程課件第93頁圖4-34請求式分頁存儲管理地址變換過程4.7.2請求分頁式存儲管理

2．頁面置換算法在作業(yè)運行過程中，如果所要訪問的頁面不在主存中，需要把他們調(diào)入主存，但主存中已沒有空閑空間時，為了保證作業(yè)的運行，系統(tǒng)必須按一定的算法選擇一個已在主存中的頁面，將它暫時調(diào)出主存，讓出主存空間，用來存放所需調(diào)入的頁面，這個工作稱為“頁面置換”。選擇換出頁面的算法稱為“頁面置換算法”。剛被調(diào)出的頁面又立即要用，因而又要把它調(diào)入，而調(diào)入不久又被選中調(diào)出，調(diào)出不久又被調(diào)入，如此反復，使調(diào)度非常頻繁，以至于大部分時間都花費在來回調(diào)度上。這種現(xiàn)象稱為“抖動”或稱“顛簸”。一個好的置換算法應該盡可能地減少和避免抖動現(xiàn)象的發(fā)生。

操作系統(tǒng)教程課件第94頁4.7.2請求分頁式存儲管理

（1）最佳置換算法（OPT）最佳置換算法選擇被淘汰的頁面將是以后永遠不再使用，或者是在將來最長時間內(nèi)不再被訪問的頁面，這樣，產(chǎn)生的缺頁中斷次數(shù)將會是最少的。采用最佳置換算法通?？色@得最低的缺頁中斷率，但這是一種理想化的算法，無法實現(xiàn)。但是這個算法可以作為衡量其它算法的標準。操作系統(tǒng)教程課件第95頁4.7.2請求分頁式存儲管理假定某進程共有8頁，且系統(tǒng)為之分配了三個物理塊，并有以下頁面調(diào)度序列：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1采用最佳置換算法，只發(fā)生了9次頁面置換，缺頁中斷率為45%。操作系統(tǒng)教程課件第96頁4.7.2請求分頁式存儲管理

（2）先進先出頁面置換算法（FIFO）先進先出頁面置換算法認為剛被調(diào)入的頁面在最近的將來被訪問的可能很大，而在主存中駐留時間最長的頁面在最近的將來被訪問的可能性最小。因此，F(xiàn)IFO算法總是淘汰最先進入主存的頁面，即淘汰在主存中駐留時間最長的頁面。FIFO算法只需要把裝入主存的頁面按調(diào)入的先后次序鏈接成一個隊列，并設置一個替換指針，指針始終指向最先裝入主存的頁面，每次頁面置換時，總是選擇替換指針所指示的頁面調(diào)出。操作系統(tǒng)教程課件第97頁4.7.2請求分頁式存儲管理圖4-36給出了以OPT算法中的例子采用FIFO算法時保留在主存中頁面變化的情況。采用FIFO置換算法一共發(fā)生了15次頁面置換，缺頁中斷率為75%，頁面淘汰的順序為7，0，1，2，3，0，4，2，3，0，1，2。FIFO算法簡單，易實現(xiàn)，但效率不高。操作系統(tǒng)教程課件第98頁4.7.2請求分頁式存儲管理先進先出算法存在一種異?，F(xiàn)象。一般來說，對于任一個作業(yè)，系統(tǒng)分配給它的主存物理塊數(shù)越接近于它所要求的頁面數(shù)，則發(fā)生缺頁中斷的次數(shù)會越少，如果一個作業(yè)獲得它所要求的全部物理塊數(shù)，則不會發(fā)生缺頁中斷現(xiàn)象。但是，采用FIFO算法時，在未給作業(yè)分配滿足它所要求的頁面時，有時會出現(xiàn)這樣的奇怪現(xiàn)象：分配的物理塊數(shù)增多，而缺頁中斷次數(shù)反而增加。這種現(xiàn)象稱之為Belady現(xiàn)象。操作系統(tǒng)教程課件第99頁4.7.2請求分頁式存儲管理操作系統(tǒng)教程課件第100頁4.7.2請求分頁式存儲管理

（3）最近最少用頁面置換算法（LRU）最近最少用頁面置換算法總是選擇最近一段時間內(nèi)最長時間沒有被訪問過的頁面調(diào)出。LRU的提出基于程序執(zhí)行的局部性原理，即認為那些剛被訪問的頁面，可能在最近的將來還會經(jīng)常訪問它們，而那些在較長時間里未被訪問的頁面，一般在最近的將來不會再訪問。為了記錄頁面自上次被訪問以來所經(jīng)過的時間，需要在頁表中增加一個“引用位”標志，在每次被訪問后將引用位置零，重新計時，這樣，在發(fā)生缺頁中斷需要調(diào)入新的頁面時，通過檢查頁表中各頁的引用位，選擇計時最長時間沒有被訪問過的頁面淘汰，并且把主存中所有頁面的引用位全部清零，重新計時。

操作系統(tǒng)教程課件第101頁圖4-39所示為在OPT算法的例子中采用LRU算法時，保留在主存中頁面的變化情況。該進程執(zhí)行過程中，共產(chǎn)生了12次缺頁中斷，缺頁中斷率為60%，頁面淘汰的順序為7，1，2，3，0，4，0，3，2。操作系統(tǒng)教程課件第102頁4.7.2請求分頁式存儲管理4.7.2請求分頁式存儲管理

LRU近似算法（時鐘置換算法Clock）是在頁表中為每一頁增加一個引用位信息，當該頁被訪問時，由硬件將它的引用位信息置為1，操作系統(tǒng)選擇一個時間周期T，每隔一個周期T，將頁表中所有頁面的引用位信息置0，這樣，在時間周期T內(nèi)，被訪問過的頁面的引用位為1，而沒有被訪問過的頁面的引用位仍為0。當產(chǎn)生缺頁中斷時，可以從引用位為0的頁面中選擇一頁調(diào)出，同時將所有頁面的引用位信息全部重置0。這種近似算法的實現(xiàn)比較簡單，但關鍵在于時間周期T大小的確定。T太大，可能所有的引用位都變成1，找不出最近最少使用的頁面淘汰；T太小，引用位為0的頁面可能很多，而無法保證所選擇的頁面是最近最少使用的。操作系統(tǒng)教程課件第103頁4.7.2請求分頁式存儲管理

淘汰一個頁面時，如果該頁面已被修改過，必須將它重新寫回磁盤；但如果淘汰的是未被修改過的頁面，就不需要寫盤操作了，這樣看來淘汰修改過的頁面比淘汰未被修改過的頁面開銷要大。如果把頁表中的“引用位”和“修改位”結合起來使用可以改進時鐘頁面替換算法，它們一共組合成四種情況：（1）最近沒有被引用，沒有被修改（r=0，m=0）（2）最近被引用，沒有被修改（r=1，m=0）（3）最近沒有被引用，但被修改（r=0，m=1）（4）最近被引用過，也被修改過（r=1，m=1）操作系統(tǒng)教程課件第104頁4.7.2請求分頁式存儲管理

改進的時鐘頁面替換算法就是掃描隊列中的所有頁面，尋找一個既沒有被修改且最近又沒有被引用過的頁面，把這樣的頁面挑出來作為首選頁面淘汰是因為沒有被修改過，淘汰時不用把它寫回磁盤。如果第一步?jīng)]找到這樣的頁面，算法再次掃描隊列，欲尋找一個被修改過但最近沒有被引用過的頁面；雖然淘汰這種頁面需寫回磁盤，但依據(jù)程序局部性原理，這類頁面一般不會被馬上再次使用。如果第二步也失敗了，則所有頁面已被標記為最近未被引用，可進入第三步掃描。Macintosh的虛存管理采用了這種策略，其主要優(yōu)點是沒有被修改過的頁面會被優(yōu)先選出來，淘汰這種頁面時不必寫回磁盤，從而節(jié)省時間，但查找一個淘汰頁面可能會經(jīng)過多輪掃描，算法的實現(xiàn)開銷較大。操作系統(tǒng)教程課件第105頁4.7.2請求分頁式存儲管理（4）最近最不常用頁面置換算法（LFU）最近最不常用置換算法總是選擇被訪問次數(shù)最少的頁面調(diào)出，即認為在過去的一段時間里被訪問次數(shù)多的頁面可能經(jīng)常需要訪問。一種簡單的實現(xiàn)方法是為每一頁設置一個計數(shù)器，頁面每次被訪問后其對應的計數(shù)器加1，每隔一定的時間周期T，將所有計數(shù)器全部清零。這樣，在發(fā)生缺頁中斷時，選擇計數(shù)器值最小的對應頁面淘汰，顯然它是最近最不常用的頁面，同時把所有計數(shù)器清零。這種算法實現(xiàn)比較簡單，但代價很高，同時有一個關鍵問題是如何選擇一個合適的時間周期T。

操作系統(tǒng)教程課件第106頁4.7.2請求分頁式存儲管理

3．缺頁中斷率分析虛擬存儲系統(tǒng)解決了有限主存貯器的容量限制問題，能使更多的作業(yè)同時多道運行，從而提高系統(tǒng)的效率，但缺頁中斷處理需要系統(tǒng)的額外開銷，影響系統(tǒng)效率，因此應盡可能減少缺頁中斷的次數(shù)，降低缺頁中斷率。假定一個作業(yè)共有n頁，系統(tǒng)分配給它的主存塊是m塊（m、n均為正整數(shù)，且1≤m≤n）。因此，該作業(yè)最多有m頁可同時被裝入主存。如果作業(yè)執(zhí)行中訪問頁面的總次數(shù)為A，其中有F次訪問的頁面尚未裝入主存，故產(chǎn)生了F次缺頁中斷。現(xiàn)定義：f＝F/A，則f稱為“缺頁中斷率”。

操作系統(tǒng)教程課件第107頁4.7.2請求分頁式存儲管理缺頁中斷率與缺頁中斷的次數(shù)有關。因此影響缺頁中斷率的因素有：（1）分配給作業(yè)的主存塊數(shù)系統(tǒng)分配給作業(yè)的主存塊數(shù)多，則同時裝入主存的頁面數(shù)就多，那么缺頁中斷次數(shù)就少，缺頁中斷率就低，反之，缺頁中斷率就高。圖4-40示出了處理器的利用率與多道程序之間的關系。操作系統(tǒng)教程課件第108頁4.7.2請求分頁式存儲管理

圖4-41所示存儲容量與缺頁中斷次數(shù)的關系。

圖中可以看出，主存物理塊數(shù)增加到臨界值以后，即使再增加較多的物理塊，進程的缺頁中斷次數(shù)也不再明顯減少。大多數(shù)程序都有這樣一個特定點，在這個特定點以后再增加主存容量，缺頁中斷次數(shù)的減少并不明顯。操作系統(tǒng)教程課件第109頁4.7.2請求分頁式存儲管理程序在運行時對頁面的訪問是不均勻的，即往往在某段時間內(nèi)訪問僅局限于較少的若干頁面，如果能夠預知程序在某段時間間隔內(nèi)要訪問哪些頁面，并能將它們提前調(diào)入主存，將會大大地降低缺頁率，從而減少置換工作，提高CPU的利用率。對于給定的訪問序列選取定長的時間間隔(⊿

)，稱為工作集窗口，落在工作集窗口中的頁面集合稱為工作集。即工作集是指在某段時間間隔里，進程實際要訪問的頁面的集合。把某進程在時間t的工作集記為w(t,⊿),把變量⊿稱為工作集“窗口尺寸”。操作系統(tǒng)教程課件第110頁4.7.2請求分頁式存儲管理

假如有以下頁面訪問序列，窗口尺寸⊿=9：26157775162341234443434441327|-----------||-----------|⊿t1⊿t2則t1時刻的工作集w(t1)={1,2,5,6,7}；t2時刻的工作集w(t2)={3,4}操作系統(tǒng)教程課件第111頁4.7.2請求分頁式存儲管理

在有些操作系統(tǒng)中，如Windows，虛擬存儲管理程序為每一個進程分配固定數(shù)量的物理塊，并且這個數(shù)目可以進行動態(tài)的調(diào)整。這個數(shù)目就是由每個進程的工作集來確定，并且根據(jù)主存的負荷和進程的缺頁情況動態(tài)地調(diào)整其工作集。當每個工作集都已達到最小值時，虛存管理程序跟蹤進程的缺頁數(shù)量，根據(jù)主存中自由頁面數(shù)量可以適當增加其工作集的大小。操作系統(tǒng)教程課件第112頁（2）頁面的大小頁面的大小影響頁表的長度、頁表的檢索時間、置換頁面的時間、可能的頁內(nèi)零頭的大小等，對缺頁中斷的次數(shù)也有一定的影響。如果劃分的頁面大，一個作業(yè)的頁面數(shù)就少，頁表所占用的主存空間少且查表速度快，在系統(tǒng)分配相同主存塊的情況下，發(fā)生缺頁中斷的次數(shù)減少，降低了缺頁中斷率，但是一次換頁需要的時間延長，可能產(chǎn)生的頁內(nèi)零頭所帶來的空間浪費較大。反之，頁面小，一次換頁需要的時間就短，可能產(chǎn)生的頁內(nèi)零頭少，空間利用率提高，但是一個作業(yè)的頁面數(shù)多，頁表所占用的主存空間長且查表速度慢，在系統(tǒng)分配相同主存塊的情況下，發(fā)生缺頁中斷的次數(shù)增多，增加了缺頁中斷率。

操作系統(tǒng)教程課件第113頁4.7.2請求分頁式存儲管理

（3）程序編制方法程序編制的方法不同，對缺頁中斷的次數(shù)也有很大影響。缺頁中斷率與程序的局部化程度密切相關。一般，希望編制的程序能經(jīng)常集中在幾個頁面上進行訪問，以減少缺頁中斷次數(shù)，降低缺頁中斷率。例如，一個程序要將128×128數(shù)組置初值“0”?，F(xiàn)假設分配給該程序的主存塊數(shù)只有一塊，頁面的大小為每頁128個字，數(shù)組中每一行元素存放在一頁中。開始第一頁已經(jīng)調(diào)入主存。操作系統(tǒng)教程課件第114頁4.7.2請求分頁式存儲管理4.7.2請求分頁式存儲管理若程序如下，則產(chǎn)生（128*128-1）次缺頁中斷。intA［128］［128］;for(j=0;j<128;j++)for(i=0;i<128;i++)A［i］［j］=0;

如果重新編制這個程序：intA［128］［128］;for(i=0;i<128;i++)for(j=0;j<128;j++)A［i］[j］=0;則總共產(chǎn)生（128-1）次缺頁中斷。操作系統(tǒng)教程課件第115頁4.7.2請求分頁式存儲管理

（4）頁