系統(tǒng)設(shè)計硬核知識（3）——操作系統(tǒng)的存儲管理

暖帶未來街QAZ 2020-04-11

展開全文

存儲器是計算機系統(tǒng)中最重要的資源之一。因為任何程序和數(shù)據(jù)以及各種控制用的數(shù)據(jù)結(jié)構(gòu)都必須占有一定的存儲空間,，因此,，存儲管理直接影響系統(tǒng)性能。

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

內(nèi)存大小由系統(tǒng)硬件決定，存儲容量受到實際存儲單元的限制,。虛擬存儲器（簡稱虛存）不考慮實際內(nèi)存的大小和數(shù)據(jù)存取的實際地址,，只考慮相互有關(guān)的數(shù)據(jù)之間的相對位置，其容量由計算機地址的位數(shù)決定,。

系統(tǒng)中內(nèi)存的使用一般分成兩部分，一部分為系統(tǒng)空間,，存放操作系統(tǒng)本身及相關(guān)的系統(tǒng)程序,；另一部分為用戶空間，存放用戶的程序和數(shù)據(jù),。

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

存儲管理的目的是盡量提高內(nèi)存的使用效率,。

1 地址變換

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

靜態(tài)重定位 : 靜態(tài)重定位是在虛空間程序執(zhí)行之前由裝配程序完成地址映射工作,。靜態(tài)重定位的優(yōu)點是不需要硬件的支持。缺點是無法實現(xiàn)虛擬存儲器,，必須占用連續(xù)的內(nèi)存空間,，且難以做到程序和數(shù)據(jù)的共享。
動態(tài)重定位 : 動態(tài)重定位是在程序執(zhí)行過程中,，在 CPU 訪問內(nèi)存之前,，將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換為內(nèi)存地址。動態(tài)重定位依靠硬件地址變換機構(gòu)完成,，其優(yōu)點主要有 : 可以對內(nèi)存進行非連續(xù)分配,，提供了虛擬存儲器的基礎(chǔ)，有利于程序段的共享 ,。

2 存儲組織

虛擬存儲器可以分為單一連續(xù)分區(qū) ,、固定分區(qū) 、可變分區(qū) ,、可重定位分區(qū) ,、頁式、段式 ,、段頁式 7 種 ,。

單一連續(xù)分區(qū)。把所有用戶區(qū)都分配給唯一的用戶作業(yè),，當作業(yè)被調(diào)度時,，進程全部進入內(nèi)存，一旦完成,，所有內(nèi)存恢復(fù)空閑,，因此，它不支持多道程序設(shè)計 ,。
固定分區(qū),。這是支持多道程序設(shè)計的最簡單的存儲管理方法，它把內(nèi)存劃分成若干個固定的和大小不同的分區(qū),，每個分區(qū)能夠裝入一個作業(yè),，分區(qū)的大小是固定的，算法簡單,，但是容易生成較多的存儲器碎片 ,。
可變分區(qū)。引入可變分區(qū)后雖然內(nèi)存分配更靈活,，也提高了內(nèi)存利用率,，但是由于系統(tǒng)在不斷地分配和回收中,，必定會出現(xiàn)一些不連續(xù)的小的空閑區(qū)，盡管這些小的空閑區(qū)的總和超過某一個作業(yè)要求的空間,，但是由于不連續(xù)而無法分配,，產(chǎn)生了碎片解決碎片的方法是拼接 ( 緊湊 ) ，即向一個方向 ( 如向低地址端 ) 移動已分配的作業(yè),，使那些零散的小空閑區(qū)在另一方向連成一片,。分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進行重定位,，另一方面系統(tǒng)在拼接時要耗費較多的時間,。
可重定位分區(qū)。這是克服固定分區(qū)碎片問題的一種存儲分配方法,，它能夠把相鄰的空閑存儲空間合并成一個完整的空區(qū),，還能夠整理存儲器內(nèi)各個作業(yè)的存儲位置，以達到消除存儲碎片和緊縮存儲空間的目的,。緊縮工作需要花費大量的時間和系統(tǒng)資源,。

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

2.1 頁式存儲管理

分頁的基本思想是把程序的邏輯空間和內(nèi)存的物理空間按照同樣的大小劃分成若干頁面,，并以頁面為單位進行分配,。在頁式存儲管理中，系統(tǒng)中虛地址是一個有序?qū)Γ撎?，位移）,。系統(tǒng)為每一個進程建立一個頁表，其內(nèi)容包括進程的邏輯頁號與物理頁號的對應(yīng)關(guān)系,、狀態(tài)等,。

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

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

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

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

2.2 段式存儲管理

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

一個作業(yè)是由若干個具有邏輯意義的段（如主程序,、子程序、數(shù)據(jù)段等）組成,。分段系統(tǒng)中,，容許程序（作業(yè)）占據(jù)內(nèi)存中許多分離的分區(qū)。每個分區(qū)存儲一個程序分段,。這樣,，每個作業(yè)需要幾對界限地址寄存器來判定訪問地址是否越界，實現(xiàn)復(fù)雜,。在分段存儲系統(tǒng)中常常利用存儲保護鍵實現(xiàn)存儲保護,。分段系統(tǒng)中虛地址是一個有序?qū)Γǘ翁枺灰疲?。系統(tǒng)為每個作業(yè)建立一個段表,，其內(nèi)容包括段號、段長,、內(nèi)存起始地址和狀態(tài)等,。狀態(tài)指出這個段是否已調(diào)入內(nèi)存，即內(nèi)存起始地址指出這個段,，狀態(tài)指出這個段的訪問權(quán)限,。

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

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

首先把當前需要的一段或幾段裝入內(nèi)存。
作業(yè)執(zhí)行時,，如果要訪問的段已經(jīng)在內(nèi)存,，則按照“段式存儲管理” 中的方式進行地址轉(zhuǎn)換,；如果要訪問的段不在內(nèi)存中，則產(chǎn)生一個“缺段中斷”,，由操作系統(tǒng)把當前需要的段裝入內(nèi)存,。

因此，在段表中應(yīng)增設(shè)段是否在內(nèi)存的標志以及各段在磁盤上的位置,，已在內(nèi)存中的段仍要指出該段在內(nèi)存中的起始地址和占用內(nèi)存區(qū)長度,。

作業(yè)執(zhí)行要訪問的段時，由硬件的地址轉(zhuǎn)換模塊查段表,。若該段在內(nèi)存中,，則立即把邏輯地址轉(zhuǎn)換成絕對地址；若該段不在內(nèi)存中,，則形成“缺段中斷”,，由操作系統(tǒng)處理這個中斷。

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

2.3 段頁式存儲管理

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

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

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

段頁式虛擬存儲管理結(jié)合了段式和頁式的優(yōu)點，但增加了設(shè)置表格（段表,、頁表）和查表等開銷,，段頁式虛擬存儲器一般只在大型計算機系統(tǒng)中使用。

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

3 存儲管理

在虛擬存儲器的管理中,，涉及載入 ( 調(diào)入 ) ,、放置 ( 放入分區(qū) ) 和置換 ( swapping ) 等管理內(nèi)容。

調(diào)入策略 : 即何時將一頁或一段從外存中調(diào)入內(nèi)存,，通常有兩種策略,，一種是請求調(diào)入法,，即需要使用時才調(diào)入；另一種是先行調(diào)入法,，即將預(yù)計要使用的頁 / 段先行調(diào)入內(nèi)存,。
放置策略 : 也就是調(diào)入后，放在內(nèi)存中的什么位置,，這與內(nèi)存管理基本上是一致的。
置換策略 : 由于實際內(nèi)存是小于虛存的,，因此可能會發(fā)生內(nèi)存已滿,，但需要使用的頁并不在內(nèi)存中的情況 ( 稱為缺頁中斷 ) 。這時就需要進行置換,，即將一些內(nèi)存中的某些頁放到外存中,，騰出空間。這一過程稱為 swapping ,。

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

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

一個好的調(diào)度算法應(yīng)減少或避免抖動現(xiàn)象,。常用的頁面調(diào)度算法（置換算法）有：

最優(yōu)（OPT）算法,。選擇不再使用或最遠的將來才被使用的頁，這是理想的算法,，但是難以實現(xiàn),。
隨機（RAND）算法。隨機地選擇需要被淘汰的頁,，開銷小,，但是可能選中立即就要訪問的頁。
先進先出（FIFO ）算法,。調(diào)出在內(nèi)存駐留時間最長的頁,，但可能淘汰掉頻繁使用的頁,。該算法簡單，易實現(xiàn),?？梢园蜒b入內(nèi)存的那些頁的頁號按進入的先后順序排成隊列，每次總是調(diào)出隊首的頁,，當裝入一個新頁后,，把新頁的頁號排到隊尾。
最近最少使用（Least Recently Used,， LRU）算法,。選擇離當前時間最近的一段時間內(nèi)使用得最少的頁。這個算法的主要理論依據(jù)是,，如果某個頁被訪問了,，則它可能馬上就要被訪問；反之,，如果某個頁長時間未被訪問,，則它在最近一段時間也不會被訪問。

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

具體分析如下：

當要訪問頁面 1 時，發(fā)生缺頁中斷,，系統(tǒng)載入頁面 4,；
接著，當訪問頁面 2 與 3時,，連續(xù)發(fā)生缺頁中斷,，系統(tǒng)載入頁面 2與頁面 3；這時,，進程所擁有的三個主存頁都已占滿,。
當要訪問頁面 4 時，應(yīng)用 FIFO 算法,，移除最先進入主存的頁面 1,，然后載入頁面 4,。
之后的頁面，都以 FIFO 算法為基礎(chǔ),，進行類似處理,。表 1 中的紅色，就表示發(fā)生缺頁中斷時,，載入主存的頁號,。

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

可以發(fā)現(xiàn),，訪問 12 個頁面時,，共發(fā)生 9 次缺頁中斷，缺頁率為 9/12=0.75,。

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

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

可以發(fā)現(xiàn)，訪問 12 個頁面時,，共發(fā)生 10 次缺頁中斷,，缺頁率為 10/12=0.833。

也就是說,，在這個示例中,，給予進程的主存頁面數(shù)越多，缺頁中斷次數(shù)反而會增加的異?，F(xiàn)象,。

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

4 局部性原理

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

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

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

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

工作集的大小依賴于工作集窗口的大小,，在進程執(zhí)行時，工作集會發(fā)生變化,。有時,，當進程進入另一個完全不同的執(zhí)行階段時，工作集會出現(xiàn)顯著的變化,。不過在一個進程的執(zhí)行過程中,，工作集的大小處于穩(wěn)定狀態(tài)的時間基本上占絕大多數(shù)。

另一種控制抖動的技術(shù)是控制缺頁率,。操作系統(tǒng)規(guī)定缺頁率的上下限,，當一個進程的缺頁率高于上限時，表明該進程需要更大的內(nèi)存空間,，則分配較多的內(nèi)存頁面給它,，當進程的缺頁率低于下限時，表明該進程占用的內(nèi)存空間過大,，可以適當?shù)厥栈厝舾蓛?nèi)存頁面,。