存儲器是計算機系統中最重要的資源之一。因為任何程序和數據以及各種控制用的數據結構都必須占有一定的存儲空間，因此，存儲管理直接影響系統性能。

存儲器由內存和外存組成。內存是由系統實際提供的存儲單元（常指字節）組成的一個連續地址空間，處理器可直接存取。外存（輔存）是指軟盤、硬盤、光盤和磁帶等一些外部存儲部件，常用來存放暫不執行的程序和數據。處理器不能直接訪問外存，需通過啟動 I/O（Input/Output，輸入/輸出）設備才能進行內存、外存交換，其訪問速度慢，但價格便宜， 常用作內存的后援設備。

內存大小由系統硬件決定，存儲容量受到實際存儲單元的限制。虛擬存儲器（簡稱虛存）不考慮實際內存的大小和數據存取的實際地址，只考慮相互有關的數據之間的相對位置，其容量由計算機地址的位數決定。

系統中內存的使用一般分成兩部分，一部分為系統空間，存放操作系統本身及相關的系統程序；另一部分為用戶空間，存放用戶的程序和數據。

存儲管理主要是指對內存儲器的管理，負責對內存的分配和回收、內存的保護和內存的擴充。

存儲管理的目的是盡量提高內存的使用效率。

1 地址變換

由進程中的目標代碼 、 數據等的虛擬地址組成的虛擬空間稱為虛擬存儲器，虛擬存儲器允許用戶用比內存容量大得多的地址空間來編程，以運行比內存實際容量大得多的程序。用戶編程所用的地址稱為邏輯地址 ( 虛地址 ) ，而實際的內存地址則稱為物理地址 ( 實地址 ) 。每次訪問內存時都要進行邏輯地址到物理地址的轉換，這種轉換是由硬件完成的，而內存和外存之間的信息動態調度是由硬件和操作系統兩者配合完成的。

靜態重定位 : 靜態重定位是在虛空間程序執行之前由裝配程序完成地址映射工作。靜態重定位的優點是不需要硬件的支持。 缺點是無法實現虛擬存儲器，必須占用連續的內存空間，且難以做到程序和數據的共享。

動態重定位 : 動態重定位是在程序執行過程中，在 CPU 訪問內存之前，將要訪問的程序或數據地址轉換為內存地址。動態重定位依靠硬件地址變換機構完成，其優點主要有 : 可以對內存進行非連續分配，提供了虛擬存儲器的基礎，有利于程序段的共享 。

2 存儲組織

虛擬存儲器可以分為單一連續分區 、 固定分區 、 可變分區 、 可重定位分區 、 頁式 、 段式 、 段頁式 7 種 。

單一連續分區。把所有用戶區都分配給唯一的用戶作業，當作業被調度時，進程全部進入內存，一旦完成，所有內存恢復空閑，因此，它不支持多道程序設計 。

固定分區。這是支持多道程序設計的最簡單的存儲管理方法，它把內存劃分成若干個固定的和大小不同的分區，每個分區能夠裝入一個作業，分區的大小是固定的，算法簡單，但是容易生成較多的存儲器碎片 。

可變分區。引入可變分區后雖然內存分配更靈活，也提高了內存利用率，但是由于系統在不斷地分配和回收中，必定會出現一些不連續的小的空閑區，盡管這些小的空閑區的總和超過某一個作業要求的空間，但是由于不連續而無法分配， 產生了碎片解決碎片的方法是拼接 ( 緊湊 ) ，即向一個方向 ( 如向低地址端 ) 移動已分配的作業，使那些零散的小空閑區在另一方向連成一片。分區的拼接技術，一方面是要求能夠對作業進行重定位，另一方面系統在拼接時要耗費較多的時間。

可重定位分區。這是克服固定分區碎片問題的一種存儲分配方法，它能夠把相鄰的空閑存儲空間合并成一個完整的空區，還能夠整理存儲器內各個作業的存儲位置，以達到消除存儲碎片和緊縮存儲空間的目的。緊縮工作需要花費大量的時間和系統資源。

另外還有三種存儲組織方式：頁式 、 段式 、 段頁式，下面我們將詳細解讀段頁式存儲管理。

2.1 頁式存儲管理

分頁的基本思想是把程序的邏輯空間和內存的物理空間按照同樣的大小劃分成若干頁面，并以頁面為單位進行分配。在頁式存儲管理中，系統中虛地址是一個有序對（頁號，位移）。系統為每一個進程建立一個頁表，其內容包括進程的邏輯頁號與物理頁號的對應關系、狀態等。

頁式系統的動態地址轉換是這樣進行的：當進程運行時，其頁表的首地址已在系統的動態地址轉換機構中的基本地址寄存器中。執行的指令訪問虛存地址（ p， d）時，首先根據頁號 p 查頁表，由狀態可知，這個頁是否已經調入內存。若已調入內存，則得到該頁的內存位置 p2，然后，與頁內相對位移 d 組合，得到物理地址 r。如果該頁尚未調入內存，則產生缺頁中斷，以裝入所需的頁，如圖 1 所示。

頁式虛擬存儲管理是在頁式存儲管理的基礎上實現虛擬存儲器的。首先把作業信息作為副本存放在磁盤上，作業執行時，把作業信息的部分頁面裝入內存儲器，作業執行時若所訪問的頁面已在內存中，則按頁式存儲管理方式進行地址轉換，得到欲訪問的內存絕對地址，若欲訪問的頁面不在內存中，則產生一個“缺頁中斷”，由操作系統把當前所需的頁面裝入內存。

為此，在裝入作業時，就應在該作業的頁表中指出哪些頁已在內存中，哪些頁還沒有裝入內存。可用一個標志位來指示對應頁是否在內存中，比如假設標志位為 1 表示該頁在內存，而標志位為 0 表示該頁尚未裝入內存。為了能方便地從磁盤上找到作業信息的副本，故在頁表中還可指出每一頁副本在磁盤上的位置。

當要裝入一個當前需要的頁面時，如果內存儲器中無空閑塊，則可選擇一個已在內存中的頁面，把它暫時調出內存。若在執行中該頁面被修改過，則把該頁信息重新寫回到磁盤上，否則不必重新寫回磁盤。當一頁被暫時調出內存后，讓出的內存空間用來存放當前需要使用的頁面。以后再使用被調出的頁面時，可用同樣的方法調出另一個頁面而將其再裝入內存。頁面被調出或裝入之后都要對頁表中的相應表目做修改。

2.2 段式存儲管理

段式存儲管理與頁式存儲管理類似。分段的基本思想是把用戶作業按邏輯上有完整意義的段來進行劃分，并以段為單位作為內外存交換的空間尺度。

一個作業是由若干個具有邏輯意義的段（如主程序、子程序、數據段等）組成。分段系統中，容許程序（作業）占據內存中許多分離的分區。每個分區存儲一個程序分段。這樣，每個作業需要幾對界限地址寄存器來判定訪問地址是否越界，實現復雜。在分段存儲系統中常常利用存儲保護鍵實現存儲保護。分段系統中虛地址是一個有序對（段號，位移）。系統為每個作業建立一個段表，其內容包括段號、段長、內存起始地址和狀態等。狀態指出這個段是否已調入內存，即內存起始地址指出這個段，狀態指出這個段的訪問權限。

分段系統的動態地址轉換是這樣進行的：進程執行時，其段表的首地址已在基本地址寄存器中，執行的指令訪問虛存（s， d）（取指令或取操作數）時，首先根據段號 s 查段表，若段已經調入內存，則得到該段的內存起始地址，然后與段內相對地址（段內偏移量 d）相加，得到實際地址。如果該段尚未調入內存，則產生缺段中斷，以裝入所需要的段。段式存儲與頁式存儲的地址轉換方式類似。

段式虛擬存儲管理仍然以段式存儲管理為基礎，為用戶提供比內存實際容量大的虛擬空間。段式虛擬存儲管理把作業中的各個分段信息都保留在磁盤上，當作業可以投入執行時，做如下操作：

首先把當前需要的一段或幾段裝入內存。

作業執行時，如果要訪問的段已經在內存，則按照“段式存儲管理” 中的方式進行地址轉換；如果要訪問的段不在內存中，則產生一個“缺段中斷”，由操作系統把當前需要的段裝入內存。

因此，在段表中應增設段是否在內存的標志以及各段在磁盤上的位置，已在內存中的段仍要指出該段在內存中的起始地址和占用內存區長度。

作業執行要訪問的段時，由硬件的地址轉換模塊查段表。若該段在內存中，則立即把邏輯地址轉換成絕對地址；若該段不在內存中，則形成“缺段中斷”，由操作系統處理這個中斷。

處理的辦法是，查內存分配表，找出一個足夠大的連續區以容納該分段，如果找不到足夠大的連續區則檢查空閑區的總和，若空閑區總和能滿足該段要求，那么進行適當移動將分散的空閑區集中起來；若空閑區總和不能滿足該段要求，可把內存中的一段或幾段調出，然后把當前要訪問的段裝入內存中。段被移動、調出和裝入后都要對段表中的相應屬性進行修改。新的段被裝入后應讓作業重新執行被中斷的指令，這時就能找到要訪問的段，也可以繼續執行下去。

2.3 段頁式存儲管理

段頁式管理是段式和頁式兩種管理方法結合的產物，綜合了段式組織與頁式組織的特點，根據程序模塊分段，段內再分頁，內存被分劃成定長的頁。段頁式系統中虛地址形式是（段號、 頁號、頁內偏移），如圖 2 所示。系統為每個進程建立一個段表，為每個段建立一個頁表。段頁式管理采用段式分配、頁式使用的方法，便于動態連接和存儲的動態分配。這種存儲管理能提高內存空間的利用率。

段式虛擬管理還是以段為單位分配內存空間，整段的調出、裝入，有時還要移動，這些都增加了系統的開銷。如果按段頁式存儲管理的方式，把每一段再分成若干頁面，那么，每一段不必占用連續的存儲空間；甚至當內存塊不夠時，可只將一段中的部分頁面裝入內存，這種管理方式稱為“段頁式虛擬存儲管理”。

段頁式虛擬存儲管理為每一個裝入內存的作業建立一張段表，還要為每一段建立頁表。段表中指出該段的頁表存放位置及長度，頁表中應指出該段的各頁在磁盤上的位置以及頁是否在內存中。若在內存中，則填上占用的內存塊號。作業執行時按段號查段表，找到相應的頁表再根據頁號查頁表，由標志位判定該頁是否已在內存，若是，則進行地址轉換；否則進行頁面調度。地址轉換過程如圖 3 所示。

段頁式虛擬存儲管理結合了段式和頁式的優點，但增加了設置表格（段表、頁表）和查表等開銷，段頁式虛擬存儲器一般只在大型計算機系統中使用。

常見的虛存組織比較說明如下：

3 存儲管理

在虛擬存儲器的管理中，涉及載入 ( 調入 ) 、 放置 ( 放入分區 ) 和置換 ( swapping ) 等管理內容。

調入策略 : 即何時將一頁或一段從外存中調入內存，通常有兩種策略，一種是請求調入法，即需要使用時才調入；另一種是先行調入法，即將預計要使用的頁 / 段先行調入內存。

放置策略 : 也就是調入后，放在內存中的什么位置，這與內存管理基本上是一致的。

置換策略 : 由于實際內存是小于虛存的，因此可能會發生內存已滿，但需要使用的頁并不在內存中的情況 ( 稱為缺頁中斷 ) 。這時就需要進行置換，即將一些內存中的某些頁放到外存中，騰出空間。這一過程稱為 swapping 。

當內存中無空閑塊時，為了裝入一個頁面而必須按某種算法從已在內存的頁中選擇一頁，將它暫時調出內存，讓出內存空間以存放所需裝入的頁面，這個工作稱為“頁面調度”。

如何選擇調出的頁面是很重要的，如果采用了一個不合適的算法，就會出現這樣的現象：剛被調出的頁面又立即要用，因而又要把它裝入，而裝入不久又被選中調出，調出不久又被裝入，如此反復，使調度非常頻繁。這種現象稱為“抖動”。

一個好的調度算法應減少或避免抖動現象。常用的頁面調度算法（置換算法）有：

最優（OPT）算法。選擇不再使用或最遠的將來才被使用的頁，這是理想的算法，但是難以實現。

隨機（RAND）算法。隨機地選擇需要被淘汰的頁，開銷小，但是可能選中立即就要訪問的頁。

先進先出（FIFO ）算法。調出在內存駐留時間最長的頁，但可能淘汰掉頻繁使用的頁。該算法簡單，易實現。可以把裝入內存的那些頁的頁號按進入的先后順序排成隊列，每次總是調出隊首的頁，當裝入一個新頁
后，把新頁的頁號排到隊尾。

最近最少使用（Least Recently Used， LRU）算法。選擇離當前時間最近的一段時間內使用得最少的頁。這個算法的主要理論依據是，如果某個頁被訪問了，則它可能馬上就要被訪問；反之，如果某個頁長時間未被訪問，則它在最近一段時間也不會被訪問。

另外，使用 FIFO 算法時，在未給予進程分配足夠的頁面時，有時會出現給予進程的頁面數越多，缺頁次數反而增加的異常現象，這稱為 Belady 現象。例如，若某個進程訪問頁面的順序 ( 稱頁面訪問序列 ) 是 1,2,3,4,1,2,5,1,2,3,4,5，當進程擁有3個主存頁面時，發生缺頁率比擁有4個主存頁面時要小。

具體分析如下：

當要訪問頁面 1 時，發生缺頁中斷，系統載入頁面 4；

接著，當訪問頁面 2 與 3時，連續發生缺頁中斷，系統載入頁面 2與頁面 3；這時，進程所擁有的三個主存頁都已占滿。

當要訪問頁面 4 時，應用 FIFO 算法，移除最先進入主存的頁面 1，然后載入頁面 4。

之后的頁面，都以 FIFO 算法為基礎，進行類似處理。表 1 中的紅色，就表示發生缺頁中斷時，載入主存的頁號。

表 1 使用 FIFO 算法發生的缺頁過程，進程擁有 3 個主存頁

可以發現，訪問 12 個頁面時，共發生 9 次缺頁中斷，缺頁率為 9/12=0.75。

如果進程擁有 4 個主存頁，那么使用 FIFO 算法發生的缺頁過程，分析方法與之前類似：

表 2 使用 FIFO 算法發生的缺頁過程，進程擁有 4 個主存頁

可以發現，訪問 12 個頁面時，共發生 10 次缺頁中斷，缺頁率為 10/12=0.833。

也就是說，在這個示例中，給予進程的主存頁面數越多，缺頁中斷次數反而會增加的異常現象。

Belady 現象的原因是 FIFO 算法的置換特征與進程訪問內存的動態特征是矛盾的，即被置換的頁面并不是進程不會訪問的，因而 FIFO 并不是一個好的置換算法。

4 局部性原理

存儲管理策略的基礎是局部性原理，即進程往往會不均勻地高度局部化地訪問內存。局部性分為時間局部性和空間局部性。

時間局部性是指最近訪問存儲位置，很可能不久的將來還要訪問 ；

空間局部性是指存儲訪問有成組的傾向；當訪問了某個位置后，很可能也要訪問其附近的位置。

根據局部性原理的特征性， Denning 闡述了程序性能的工作集理論。工作集是進程頻繁訪問的頁面的集合。工作集理論指出，為使進程有效地運行，它的頁面工作集應駐留內存中。否則，由于進程頻繁地從外存請求頁面，而出現稱為 “ 顛簸 ” ( 抖動 ) 的過度的頁面調度活動。此時，處理頁面調度的時間超過了程序的執行時間。顯然，此時 CPU 的有效利用率會急速下降。

通常用兩種等價的方法確定進程的工作集，一種是將工作集確定為在定長的頁面訪問序列 ( 工作集窗口 ) 中的頁面集合；另一種是將工作集確定為在定長時間間隔中涉及頁面的集合。

工作集的大小依賴于工作集窗口的大小，在進程執行時，工作集會發生變化。有時，當進程進入另一個完全不同的執行階段時，工作集會出現顯著的變化。不過在一個進程的執行過程中，工作集的大小處于穩定狀態的時間基本上占絕大多數。

另一種控制抖動的技術是控制缺頁率。操作系統規定缺頁率的上下限，當一個進程的缺頁率高于上限時，表明該進程需要更大的內存空間，則分配較多的內存頁面給它，當進程的缺頁率低于下限時，表明該進程占用的內存空間過大，可以適當地收回若干內存頁面。