操作系统学习笔记 第四章：存储器管理（王道考研）
本文章基于網課： 2019 王道考研 操作系統
考試復習推薦資料：操作系統復習總結 - 百度文庫 (baidu.com)
需要相關電子書的可以關注我的公眾號
BaretH后臺回復操作系統
第一章：操作系統概述
第二章：進程管理
第三章：處理機調度與死鎖
后續章節陸續推出…
四、存儲器管理
- 4.1 內存基礎知識
- 4.1.1 什么是內存
- 4.1.2 程序運行原理
- 4.1.3 裝入三種方式
- 4.1.4 鏈接的三種方式
- 4.2 內存管理的功能
- 4.2.1 內存空間的分配與回收
- 4.2.1 內存空間的擴充
- 4.2.3 地址轉換
- 4.2.4 內存保護
- 4.3 連續分配管理方式
- 4.3.1 單一連續分配
- 4.3.2 固定分區分配
- 4.3.3 動態分區分配
- 4.4 動態分區分配算法
- 4.4.1 首次適應算法
- 4.4.2 最佳適應算法
- 4.4.3 最壞適應算法
- 4.4.4 鄰近適應算法
- 4.5 非連續分配管理方式
- 4.5.1 分頁存儲管理
- -- 基本地址變換機構
- -- 具有快表的地址變換機構
- -- 兩級頁表
- 4.5.2 分段存儲管理
- 4.5.3 段頁式存儲管理
- 4.6 內存空間擴充技術
- 4.6.1 覆蓋技術
- 4.6.2 交換技術
- 4.6.3 虛擬內存
- -- 請求分頁管理方式
- -- 頁面置換算法
- -- 頁面分配策略
- 4.7 磁盤的結構
- 4.7.1 磁盤、磁道、扇區
- 4.7.2 如何在磁盤中讀/寫數據
- 4.7.3 盤面、柱面
- 4.7.4 磁盤的物理地址
- 4.7.5 磁盤的分類
- 4.8 磁盤調度算法
- 4.8.1 先來先服務算法（FCFS）
- 4.8.2 最短尋找時間優先算法（SSTF）
- 4.8.3 掃描算法（SCAN）
- 4.8.4 LOOK調度算法
- 4.8.5 循環掃描算法（C-SCAN）
- 4.8.6 C-LOOK調度算法
- 4.9 減少延遲時間的方法
- 4.9.1 交替編號
- 4.9.2 磁盤地址結構的設計
- 4.9.3 錯位命名
- 4.10 磁盤管理
- 4.10.1 磁盤初始化
- 4.10.2 引導塊
- 4.10.3 壞塊的管理
4.1 內存基礎知識
4.1.1 什么是內存
內存(Memory)是計算機的重要部件之一，也稱內存儲器和主存儲器，它用于暫時存放CPU中的運算數據，與硬盤等外部存儲器交換的數據，它的輸入輸出速度遠大于硬盤。為了緩和CPU與硬盤之間的速度差異，程序執行前必須要放在內存中才能被CPU處理
常用內存數量單位：
4.1.2 程序運行原理
當我們編寫好一個程序執行時，會經過編譯、鏈接、裝入三個步驟
編譯就是將我們編寫好的源代碼文件由編譯程序編譯成若干目標模塊，實際就是將高級語言翻譯為低級語言鏈接就是在編譯為目標模塊后，再由鏈接程序將其與所需的庫函數鏈接在一起，形成一個完整的裝入模塊，鏈接后形成完整的邏輯地址裝入又稱裝載，就是由裝入程序將裝入模塊加載到內存中運行，此時會完成邏輯地址到物理地址的映射
經歷上述三個步驟后，程序會被翻譯成一條一條的指令，實際運行的就是這一條條的指令，指令由操作碼+操作數組成，比如下圖x=x+1會被翻譯成三條指令，其中第一個參數為操作碼，后面兩個參數為操作數地址
上圖中指令的操作數部門使用了變量x的實際物理地址，但通常指令中操作數的地址一般使用邏輯地址，而程序執行的第三步裝入就是完成邏輯地址到物理地址映射的過程，邏輯地址和物理地址的描述如下圖所示
4.1.3 裝入三種方式
一個程序的執行往往通過編譯–》鏈接–》裝入三個步驟，
裝入過程通常完成邏輯地址到物理地址的映射，通常有以下三種方式
1?? 絕對裝入：編程時，直接確定內存地址
2?? 靜態重定位：編程時使用邏輯地址，當程序被裝入內存時，一次性實現邏輯地址到物理地址的轉換，以后不再轉換
3?? 動態重定位：編程時使用邏輯地址，在程序真正執行過程中要訪問數據時再進行地址變換（即在逐條指令執行時完成地址映射。一般為了提高效率，此工作由硬件地址映射機制來完成。硬件支持，軟硬件結合完成）
4.1.4 鏈接的三種方式
一個程序的執行往往通過編譯–》鏈接–》裝入三個步驟，鏈接過程將編譯出的目標模塊其與所需的庫函數鏈接在一起，形成一個完整的裝入模塊，通常分為以下三種方式
1?? 靜態鏈接：在程序運行之前，先將各目標模塊及它們所需的庫函數鏈接成一個完整的可執行程序，以后不再拆開
2?? 動態鏈接：將用戶源程序編譯后所得到的一組目標模塊，在裝入內存時，采用邊裝入邊鏈接的方式
3?? 運行時動態鏈接：對某些目標模塊的鏈接，是在程序執行中需要該目標模塊時才進行的；其優點是便于修改和更新，便于實現對目標模塊的共享
4.2 內存管理的功能
4.2.1 內存空間的分配與回收
我們知道操作系統作為系統資源的管理者，當然也需要對內存進行管理，那么它要管些什么呢？
- 各種進程想要投入運行時都需要將進程所需要的數據加載到內存中，然而內存中有些區域是已經分配出去，有些區域是空閑的，那操作系統怎么管理記錄哪些區域是空閑哪些是非空閑呢？
- 如果有新的進程想要投入內存中運行，那么該進程相關的數據需要放入內存當中，但是內存中有很地方可以進行存放，那么到底放在哪個位置呢？
- 如果有進程運行結束了，那么該進程占有的內存空間如何回收呢？
這些問題都是需要操作系統來負責的，因此內存管理的第一件事就是由操作系統來負責內存空間分配與回收
4.2.1 內存空間的擴充
比如電腦里裝了一個60GB的游戲，按理來說游戲程序運行之前需要把60GB的數據全部加載到內存中，但是內存只有4GB，游戲是如何運行的呢？除此之外，計算機中經常會碰到內存空間不夠進程使用的問題，因此進程管理的第二件事就是操作系統需要提供某種技術從邏輯上對內存空間進行擴充，也就是虛擬技術——操作系統的虛擬性，將物理上很小的內存拓展為邏輯上很大的內存
4.2.3 地址轉換
為了使編程更方便，程序員寫程序時應該只需要關注指令、數據的邏輯地址。而邏輯地址到物理地址的轉換（這個過程稱為地址重定位）應該由操作系統負責，這樣就保證了程序員寫程序時不需要關注物理內存的實際情況。因此內存管理的第三件事就是操作系統提供地址轉換功能，負責程序的邏輯地址到物理地址的轉換
實現地址轉換的方法對應著三種裝入方式：
- 絕對裝入：在編譯時產生絕對地址，該方式只適用于單道程序階段（此時還沒操作系統，由編譯器負責）
- 可重定位裝入：在裝入時將邏輯地址轉換為物理地址，由裝入程序完成，裝入程序是操作系統的一部分，這種方法適用于早期的多道批處理系統
- 動態運行裝入：程序運行時才將邏輯地址轉換為物理地址，此方式需要重定位寄存器，是現代操作系統采用的方式（頁式存儲、段式存儲大量采用該方式）
4.2.4 內存保護
投入內存中運行的進程應只能訪問自己進程的內存空間，如果能隨便訪問其他進程的內存空間，對其數據進行修改，則會影響其他進程的運行。因此內存管理的第四件事就是操作系統需要提供內存保護功能，保證各個進程在各自存儲空間內運行互不干擾，只能訪問自己對應的內存空間
內存保護可以采用兩種方式：
-
方式一：在cpu中設置一對上、下限寄存器，分別用于存放進程的上下限地址。當進程1想要訪問某內存單元時，CPU會根據指令當中想要訪問的內存地址和上下限寄存器中的兩個地址進行對比，只有在這兩地址之間，才允許進程1進行訪問
-
方式二：采用重定位寄存器（又稱基址寄存器）和屆地址寄存器（又稱限長寄存器）進行越界檢查；重定位寄存器存放進程的起始物理地址，屆地址寄存器存放進程的最大邏輯地址。進程需要訪問某內存單元時，首先判斷待訪問單元的邏輯地址是否小于屆地址寄存器中的值，是的話則合法，否則越界拋出異常；合法的話會與重定位寄存器中的值相加得到實際的物理地址然后進行訪問
4.3 連續分配管理方式
內存管理的第一件事就是由操作系統負責內存空間的分配與回收，具體的實現分為兩種方式：連續分配管理方式和非連續分配管理方式，所謂連續分配就是指為用戶進程分配的必須是一個連續的內存空間。
4.3.1 單一連續分配
4.3.2 固定分區分配
那么操作系統怎么記錄各個分區空閑和分配的情況呢？通過需要建立一個分區說明表的數據結構，來實現各個分區的分配與回收
4.3.3 動態分區分配
處于固定分區分配的缺點引入了動態分區分配的方式
但是隨之而來也產生了3個問題：
-
系統要用什么樣的數據結構記錄內存的使用情況？
-
當很多個空閑分區都能滿足需求時，應該選擇哪個分區進行分配？
-
如何進行分區的分配與回收操作？
系統會檢查是否有空閑分區與回收區相鄰，如果有，則修改空閑分區表/空閑分區鏈中相應的內容將他們合并
關于動態分區分配內存碎片的問題，動態分區分配沒有內部碎片，但是有外部碎片
- 內部碎片，分配給某進程的內存區域中，有些部分沒有用上。
- 外部碎片，是指內存中的某些空閑分區由于太小而難以利用。
4.4 動態分區分配算法
4.4.1 首次適應算法
4.4.2 最佳適應算法
4.4.3 最壞適應算法
4.4.4 鄰近適應算法
4.5 非連續分配管理方式
對于支持多道程序的兩種連續分配方式：
- 固定分區分配：缺乏靈活性，會產生大量的內部碎片，內存的利用率很低
- 動態分區分配：會產生很多的外部碎片，雖然可用
緊湊技術來解決，但是會耗費很大的時間代價
基于連續分配管理方式存在的缺點，我們能不能允許將一個進程分散的裝入不相鄰的分區中，這樣能夠更高效充分的利用內存，無需再緊湊，從而引入了非連續分配管理方式，所謂非連續就是為用戶進程分配的可以是一些分散的內存空間
非連續分配管理方式分為三種：基本分頁存儲管理、基本分段存儲管理、段頁式存儲管理
4.5.1 分頁存儲管理
那么具體是怎么實現的呢？其中最重要的部分就是地址轉換
那么如何計算頁號和偏移量呢？對于我們而言
而對于計算機而言，為了方便計計算，頁面大小一般設置為2的整數冪
因此計算機中的分頁存儲管理的邏輯地址結構是固定的，分為頁號和頁面偏移量兩部分
現在我們知道了頁號以及頁面內部偏移量，那么怎么知道頁號對應內存中的起始地址呢，這就引入了頁表，用于記錄進程頁面和實際存放的內存塊之間的關系
– 基本地址變換機構
例題：
– 具有快表的地址變換機構
具有塊表的地址變換機構是基本地址變換機構根據局部性原理的改進版本，那么什么是局部性原理呢？
了解完局部性原理之后，我們來看看快表的概念
– 兩級頁表
1?? 單級頁表存在的問題
- 問題一：為了根據頁號查詢頁表，頁表必須連續存放，因此當頁表很大時，需要占用很多個連續的頁框，比如這里需要專本給進程分配2^10連續的頁框來存放頁表
- 問題二：沒有必要讓整個頁表常駐內存，因為進程在一段時間內可能只需要訪問某幾個特定的頁面
2?? 問題一解決方案：兩級頁表
3?? 問題二解決方案
4?? 需要注意的細節
4.5.2 分段存儲管理
在內存的系統區當中，存在著許多用于管理軟硬件系統資源的數據結構，比如PCB，當一個進程要上處理機運行之前，進程切換相關的內核程序會將進程的運行環境恢復，其中包含一個很重要的硬件寄存器——段表寄存器，其中存放段表地址和段表長度。因此段表地址和段表長度在進程還沒有上處理機運行的時候存放在PCB中，被運行后存放在段表寄存器中。
當一個進程需要訪問某邏輯單元的過程如下圖所示：
分頁和分段的對比：
兩者的最大區別是分頁中每個頁面的長度是相同的，不需要對頁面偏移量進行越界檢查，而分段每個段的長度是不同的，一定要對段內偏移量與段長對比進行越界檢查
4.5.3 段頁式存儲管理
4.6 內存空間擴充技術
操作系統內存管理的第二件事就是對內存空間進行擴充，具體有三種技術實現，分別是
覆蓋技術、交換技術、虛擬存儲技術
4.6.1 覆蓋技術
早期的計算機內存很小，比如IBM推出的第一臺PC機最大只支持1MB大小的內存。因此經常會出現內存大小不夠的情況。后來人們引入了覆蓋技術，用來解決“程序大小超過物理內存總和”的問題
4.6.2 交換技術
隨之而來有三個問題
4.6.3 虛擬內存
虛擬技術的提出基于局部性原理
– 請求分頁管理方式
請求分頁管理方式是在基本分頁管理方式基礎上進行拓展而實現的虛擬內存管理技術
– 頁面置換算法
最佳置換算法可以保證最低的缺頁率，但實際上，只有在進程執行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統無法?前預判頁面訪問序列。因此，最佳置換算法是無法實現的。
– 頁面分配策略
4.7 磁盤的結構
4.7.1 磁盤、磁道、扇區
4.7.2 如何在磁盤中讀/寫數據
4.7.3 盤面、柱面
4.7.4 磁盤的物理地址
4.7.5 磁盤的分類
4.8 磁盤調度算法
我們一般通過一次磁盤讀寫操作的時間衡量磁盤性能由，一次磁盤讀寫操作的時間由尋找（尋道）時間、延遲時間和傳輸時間決定
磁盤調度算法對一次磁盤讀/寫操作需要的時間有很大的影響，因此要選擇合適的磁盤調度算法對磁盤的整體性能有很大的影響，常見的磁盤調度算法如下圖所示：
4.8.1 先來先服務算法（FCFS）
4.8.2 最短尋找時間優先算法（SSTF）
4.8.3 掃描算法（SCAN）
4.8.4 LOOK調度算法
解決了掃描算法的第一個缺點：
4.8.5 循環掃描算法（C-SCAN）
解決了掃描算法的第二個缺點：
4.8.6 C-LOOK調度算法
4.9 減少延遲時間的方法
4.9.1 交替編號
4.9.2 磁盤地址結構的設計
4.9.3 錯位命名
4.10 磁盤管理
4.10.1 磁盤初始化
4.10.2 引導塊
4.10.3 壞塊的管理
總結
以上是生活随笔為你收集整理的操作系统学习笔记 第四章：存储器管理（王道考研）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 操作系统学习笔记 第三章：处理机调度与死
- 下一篇： 操作系统学习笔记 第五章：文件管理（王道