記憶體管理基礎

記憶體管理概述

存盤管理的主要任務是為多道程式的運行提供良好的環境，方便用戶使用存盤器，提高存盤器的利用率以及邏輯上擴充存盤器，

功能：

• 記憶體的分配和回收
• 地址變換
• 擴充記憶體
• 存盤保護

應用程式的編譯、鏈接與裝入

應用程式從用戶撰寫的源檔案到記憶體中執行的行程，大致分為三個階段：

1. 經編譯層序，將源代碼編譯為若干個目標模塊
2. 通過麗娜姐程式將編譯好的目標模塊以及所需的庫函式鏈接在一起，形成完整的裝入模塊
3. 通過裝入程式將這些裝入模塊裝入記憶體并執行，

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

一些小筆記

名地址：對程式設計者來說，資料的存放地址由資料名稱決定，因此稱為名地址，

相對地址（虛擬地址、邏輯地址）：源程式經過編譯后得到目標代碼，由于編譯程式無法得知代碼駐留在記憶體的實際位置（物理地址），一般總是從0號單元開始編址，并順序分配所有地址單元，并不是真實的記憶體地址，

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

重定位：通過地址轉換將邏輯地址轉換為物理地址的程序，

程式的鏈接有三種方式：

• 靜態鏈接：在程式運行之前，先把各個目標模塊及所需庫連接為一個完整的可執行程式，以后不再擦愛開，
• 裝入時動態鏈接：將應用程式編譯后所得到的一組目標模塊裝入記憶體時采用邊裝入邊鏈接的動態鏈接方式，
• 運行時動態鏈接：直到程式運行程序中需要一些模塊時，才對這些模塊進行鏈接，

程式的裝入也有三種方式：

• 絕對裝入：在編譯時酒直到程式將要駐留的物理地址，編譯層序殘生含有物理地址的目標代碼
• 可重定位裝入：根據記憶體當前情況，將裝入模塊裝入到記憶體的適當位置，地址變換通常在裝入時一次完成，之后不再改變，也稱靜態重定位，
• 動態運行裝入：允許程式運行時在記憶體中移動位置，也稱動態重定位，
  

邏輯地址和物理地址

邏輯地址：由程式產生的與段（與頁無關，因為只有段對用戶可見）相關的便宜地址部分，總是從0號帶能源開始編址，

物理地址：出現在CPU外部地址總線上的尋址物理地址記憶體的地址信號，是邏輯地址變換后的最終結果地址，

記憶體保護

記憶體保護是為了防止一個作業有意或無意地破壞作業系統或其他作業，常用的方法有有界限暫存器和存盤保護鍵方法，

覆寫與交換

覆寫技術：把大的程式劃分為一些列覆寫，每個覆寫是一個相對獨立的程式單位，把程式執行時并不要求同時裝入記憶體的覆寫組成一組，稱為覆寫段，覆寫區大小由覆寫段中最大的覆寫來決定，

交換技術：把暫時不用的某個程式及資料部分（或全部）從記憶體移到外存中；或把指定的程式或資料從外存讀到相應的記憶體中，并將控制權轉交給它，讓其在系統上運行，

連續分配管理方式

內部碎片：指已經分配給作業但不能被利用的記憶體空間

外部碎片：指系統中還沒有分配給作業，但由于碎片太小而無法分配給申請記憶體空間的新行程的存盤塊，

單一連續分配

將記憶體分為兩個連續存盤區域，其中一個存盤區域固定地分配給作業系統使用，通常放在記憶體低地址部分，另一個存盤區域給用戶作業使用，

會產生內部碎片

固定磁區分配

將記憶體空間劃分為若干個固定大小的磁區，每個磁區可以裝入一道程式，

動態磁區分配

為實作動態磁區分配，系統中需設定相應的資料結構來記錄記憶體的使用情況，常用的資料結構形式如下，

• 空閑磁區表：登記系統中的空閑磁區，
• 空閑磁區鏈：用鏈頭指標將記憶體中的空閑磁區鏈接起來，構成空閑磁區鏈，

磁區分配演算法

• 首次適應演算法（First Fit，FF），把空閑磁區按照地址遞增的次序用鏈表串成一個佇列，每次需要為要給行程分配記憶體時都從隊首開始找，順著鏈表直到找到足夠大的空閑磁區，然后按照作業大小從該磁區劃分出一塊記憶體空間分配給請求者，余下的空閑磁區仍然留在空閑磁區表中，
• 下次適應演算法（Next Fit，NF）：即在首次適應演算法的基礎上把佇列改成回圈佇列，不再每次都從隊首開始空閑磁區，而是從上一次找到的空閑磁區的下一個磁區開始找，
• 最佳適應演算法（Best Fit，BF）：要求將空閑磁區按照容量大小遞增的次序排列，
• 最差適應演算法（Worst Fit，WF）：要求將空閑磁區按照容量大小遞減的次序排列，

非連續分配管理方式

基本分頁存盤管理方式

分頁原理

在分頁存盤管理中，用戶作業的地址空間被劃分成若干個大小相等的區域，稱為頁或頁面，相應地，將主存的存盤空間也分成與頁面大小星等的區域，稱為塊或物理塊，可以將作業中的任意一頁放到主存的任意一塊中，

分頁存盤管理系統中的邏輯地址包含兩部分：頁號P，業內位移W，

頁表

頁面和物理塊的映射關系，

基本地址變換機構

具有快表的地址變換機構

頁的共享和保護：使共享用戶地址空間中的頁指向相同的物理塊，地址越界保護，訪問控制資訊保護，

基本分段存盤管理方式

在分段存盤管理系統中，作業的地址空間由若干個邏輯分段組成，每個分段式一組邏輯意義上相對玩真的資訊集合，每個分段都有子集的名字，每個分段都從0開始編址，并采用一段連續的地址空間，

分段管理系統的邏輯地址結構由段號S和段內位移W組成，

段表及地址映射

分頁與分段的區別

頁是資訊的物理單位；段是資訊的邏輯單位，

頁的大小固定且由系統決定；段的長度不固定，

分頁系統中作業的地址空間是一維的；分段系統中作業的地址空間是二維的，

分頁系統有內部碎片，無外部碎皮；分段系統中無內部碎片，有外部碎片，

基本段頁式存盤管理方式

作業的地址空間首先被分成若干個邏輯分段，每段都有自己的段號，然后再將每一段分成若干個大小固定的頁，、

虛擬記憶體管理

基本概念

區域性原理

大多數程式執行時，再一個較短的時間內僅使用程式代碼的一部分，相應地，程式所訪問的存盤空間也局限于某個區域，這就是程式執行的區域性原理，表現為：時間區域性、空間區域性，

常用的虛擬存盤管理技術有請求分頁存盤管理、請求分段存盤管理和請求段頁式存盤管理，

請求分頁存盤管理方式

請求分頁原理

作業運行之前，只要將當前需要的一部分頁面裝入主存，便可以啟動作業運行，在作業運行程序中，若索要訪問的頁面不在主存中，則通過調頁功能將其調入，同時還可以通過置換演算法將暫時不用的頁面置換到外存上，以騰出記憶體空間，

請求分頁=基本分頁+請求調頁功能+頁面置換功能

頁表結構

頁表中個欄位的作用如下

• 頁號和物理號：進行地址變換所必須的欄位
• 狀態位：用于判斷頁面是否存在主存中，
• 訪問欄位：用于記錄頁面在一段時間內被訪問的次數，
• 修改位：用于表示頁面調入記憶體后是否被修改過，
• 外存地址：用于指出頁面在外存上的存放地址，

缺頁中斷與地址變換

頁面置換演算法

用來選擇患處頁面的演算法，

最佳置換（OPT）演算法

在預知一個行程的頁面號參考串的情況下，沒看此都淘汰以后不再使用的或以后最遲別使用的頁面，無法實作，只能作為一個標注來衡量其他置換演算法的優劣，

先進先出（FIFO）演算法

每次總是淘汰最先進記憶體的頁面，也就是淘汰在記憶體駐留時間最長的頁面，

最近最少使用（LRU）演算法

選擇最近最長時間沒有被使用的頁面語意淘汰，

在常用的頁面置換演算法中，LRU演算法最接近最佳置換演算法，

時鐘置換（CLOCK）演算法（最近未使用（NRU）演算法）

CLOCK維護一個記憶體中所有頁面的回圈鏈表，當程式需要訪問鏈表中存在的頁面時，該頁面的訪問位就被置為1；否則，若程式要訪問的頁面沒有在鏈表中，那就需要淘汰一個記憶體中的頁面，于是一個指標就從上次別淘汰頁面的下一個位置開始順序遍歷鏈表，當這個指標指向的頁面的訪問位為1時，就把該訪問位清零，指標再向下移動，當指標指向的頁面的訪問位為0時，淘汰這一頁面，

改進型時鐘（CLOCK）演算法

在訪問位為0的行程間有限淘汰沒有修改過的頁面，

與簡單CLOCK演算法相比，減少了磁盤I/O次數，但增加了掃描次數，

作業集與頁面的分配策略

作業集是最近n次記憶體訪問的頁面的集合，

頁面分配策略：固定分配區域置換、可變分配全域置換、可變分配區域變換，

頁面調入策略：請求調頁策略、預調頁策略，

抖動現象

FIFO置換演算法的缺頁率可能會隨著所分配的物理塊數的增加而增加，這種現象就是Belady例外，

產生Belady例外的原因：FIFO演算法的置換特征預行程訪問記憶體的動態特征相矛盾，被置換的頁面并不是行程不會訪問的，

LRU永遠不會出現Belady例外，

抖動現象：若選用的頁面置換演算法不合適，可能會出現這種現象：剛被淘汰的頁面，過后不久又要訪問，并且調入不久后又調出，如此反復，使得系統吧大部分時間用在了頁面的調入調出上，而幾乎不能完成任何有效的作業，這種現象稱為抖動，

記憶體管理間的對比與一些計算方法

記憶體管理方式之間的比較

離散分配方式的比較

記憶體管理方式的比較

記憶體管理計算中地址的處理

十六進制、八進制、二進制對應的后最分別為字母H、O、B，

在請求分頁系統中，若將邏輯地址轉換為物理地址，處理程序如下：

• 將其他進制轉化為二進制，方便處理，
• 求出頁號，頁號為邏輯地址與頁面大小的商，二進制下為地址高位，
• 求出頁內位移，業內位移為邏輯地址與頁面大小的余數，二進制下為地址低位，（把地址平均分,前面的叫高位,后面的叫低位）
• 根據題意產生頁表，通過查找頁表得到對應頁的記憶體塊或頁框號，
• 若給出的是記憶體塊號，則用記憶體塊號誠意塊大小，加上基址，再加上頁內位移得到物理地址，
• 若給出的是頁框號，則用頁框號與頁內位移進行拼接，得到物理地址，
• 將二進制表示的物理地址根據題目要求轉換為十六進制或十進制，

基本分頁管理方式中有效訪問時間的計算

有效訪問時間（EAT）指給定邏輯地址找到記憶體中對應物理地址單元中的資料所有的的時間，

沒有塊表的情況

訪存一次所需時間為t，有效訪問時間分為：查找頁表找到對應頁表項，需要訪存一次，消耗時間t；通過對應頁表項中的物理地址訪問對應記憶體單元，需要訪存一次，消耗時間t，

因此，EAT=t+t=2t，

存在快表的的情況

設訪問快表的時間為a，訪存一次時間為t，快表命中率為b，則有效訪問時間分為：查找對應頁表項的平均時間a*b+（t+a)(1-b），其中，a表示快表命中所需查找時間；t+a表示查找快表未命中時，需要再次訪存讀取頁表找到對應頁表項，兩種情況的概率分別為b和1-b，可以計算得到期望值，即平均時間，通過頁表項中的物理地址訪存一次取出所需資料，消耗時間t，因此，EAT=a*b+(t+a)(1-b)+t，

請求分頁管理方式中有效訪問時間的計算

與基本分頁管理方式相比，多了缺頁中斷的情況，需要耗費而外的時間，因此計算有效訪問時間時，要將缺頁這種情況考慮進去，

• 訪問的頁在主存中，且訪問頁在快表中，則EAT=查找快表時間+根據物理地址訪存時間=a+t，
• 訪問的頁在主存中，但不在快表中，則EAT=查找快表時間+查找頁表時間+修改快表時間（題目未給出則忽略不計）+根據物理地址訪存時間=a+t+a+t=2（a+t），
• 訪問的頁不在主存中（此時也不可能在快表中），即發生缺頁，設處理缺頁中斷的時間未T（包括將該頁調入主存，更新頁表和快表的時間），則EAT=查找快表時間+查找頁表時間+處理缺頁時間（通常包括了跟新頁表和快表時間）+查找快表時間+根據物理地址訪存時間=a+t+T+a+t=T+2（a+t），

然后加入缺頁率和命中快表的概率，將上述3中情況組合起來，形成完整的有效訪問呢時間計算公式，設命中快表的概率為d，缺頁率為f，則

EAT=查找快表時間+d*根據物理地址訪存時間+（1-d）*[查找頁表時間+f*（處理缺頁時間+查找快表時間+根據物理地址訪存時間）+（1-f）*(修改快表時間+根據物理地址訪存)]=a+d*t+(1-d)[t+f(T+a+t)+(1-f)(a+t)].

快表訪問和修改時間，若沒有說明則默認沒有快表，將命中率和訪問時間變為0即可，如忽略訪問和修改快表的時間，則將a變為0即可，

關于處理缺頁中斷時間T的計算，若題中沒有說明被置換出的頁面是否被修改，則缺頁中斷時間統一為T，若分修改和未修改的情況，設被修改的概率為n，處理被修改的頁面的時間為T1，處理未修改的頁面的時間為T2，則T=n*T1+(1-n)T2.