存儲器管理

存儲器層次結構

存儲層次至少具有三級：最高層為CPU寄存器，中間為主存，最底層是輔存。

程序的裝入和鏈接

程序裝入方式：

• 絕對裝入方式：絕對裝入程序按照裝入模塊的地址，將程序和數據裝入內存。

• 可重定位方式：在采用可重定位裝入程序將裝入模塊裝入內存后，會使裝入模塊中的所有邏輯地址與實際裝入內存的物理地址不同。

• 動態運行時裝入方式：裝入內存后的所有地址都仍然是相對地址，而將相對地址轉換為絕對地址是在程序真正執行的時候。

程序鏈接方式：

內存管理

內存分配方式

單一連續分配：將內存分為系統區、用戶區，將系統區的內存交給操作系統使用，而用戶區內存分配給用戶使用。

固定分區分配：內存空間被劃分為若干個固定大小的區域，每個分區提供給某個進程使用。

動態分區分配：根據進程實際需要，結合數據結構動態分配內存。

• 位圖：由位圖標記相關分區是否被使用
• 空閑鏈表：由雙向鏈表將空閑區域作為節點相連

相關分配算法

首次適應算法：從頭部順序查找，分配內存使用。

最佳適應算法：空閑區鏈表按照容量大小排序，遍歷空閑區鏈表找到最佳空閑區，分配內存使用。

快速適應算法：擁有多個空閑區鏈表，每個空閑區鏈表存儲一種容量的空閑區，快速找到合適的內存分配使用。

內存回收過程

• 回收區和一塊空閑區相鄰，且回收區在空閑區下邊：將回收區包含進空閑區

• 回收區和一塊空閑區相鄰，且空閑區在回收區下邊：將回收區和空閑區合并，新的空閑區采用回收區的地址

• 回收區在兩塊空閑區中間：將三個區域合并，新的空閑區使用頂部的空閑區地址

• 單獨的回收區：轉為空閑區插入空閑區鏈表

內存存儲管理

頁式存儲管理：將進程邏輯空間等分為若干個頁面，物理內存空間分為若干個物理塊，以頁面為單位將進程裝入物理塊。由頁表記錄進程邏輯空間與物理空間的映射

• 缺點：由于頁面大小的原因，會導致碎片多，單一的頁式存儲也會導致頁表占用內存空間大。
• 優點：符合計算機的存儲管理要求
• 解決方案：采用多級頁表，防止一次頁表的頁表項過大

段式存儲管理：將進程邏輯空間劃分為若干段（非等分），由段表記錄邏輯空間到物理空間的映射。

• 優點：適合用戶需求，滿足程序的共享

段頁式存儲管理：結合了提高內存利用率的分頁管理、滿足用戶需求的分段，將進程先分為段，再分為頁。

頁面置換算法

當發生缺頁異常的時候，需要相關的頁面置換算法。

最優頁面置換算法：將不再需要或者很久以后才需要的頁面置換出去，這是一種理想的置換算法。

先進先出頁面置換算法：由操作系統維護一個所有在當前內存中的頁面的鏈表，缺頁時移除頭部的頁，并且把新的頁添加到表尾。

最近最少使用頁面置換算法：在缺頁中斷時，置換未使用時間最長的頁面。

虛擬地址空間

將物理內存地址暴露給進程的缺點：

• 用戶程序可以尋址內存中的字節，容易破壞操作系統
• 多個用戶程序容易發生沖突，并發困難

虛擬地址空間：創建了一種抽象內存供程序使用。地址空間是進程可以用來尋址內存的地址集。每個進程都有它自己的地址空間，獨立于其他進程的地址空間。

在沒有虛擬內存的計算機上，系統直接將虛擬地址送到內存中線上，讀寫操作都使用同樣地址的物理內存。在使用虛擬地址空間技術時，虛擬地址不會直接發送到內存總線上。相反，會使用 MMU內存管理單元把虛擬地址映射為物理內存地址。

基址寄存器和變址寄存器：采用了虛擬地址空間后，要實際定位到程序的物理內存地址，采用動態重定位方法，使用CPU中的基址寄存器、變址寄存器來對地址空間轉換為物理內存地址。

• 基址寄存器：存儲數據內存的起始位置
• 變址寄存器：存儲應用程序的長度。

---

虛擬地址空間由固定大小的單元組成，這種固定大小的單元稱為 頁(pages)。而相對的，物理內存中也有固定大小的物理單元，稱為 頁框(page frames)。

映射關系由頁表進行管理，如果MMU 注意到該頁面沒有被映射，于是 CPU 會陷入(trap)到操作系統中。這個陷入稱為 缺頁中斷(page fault) 或者是 缺頁錯誤。操作系統會選擇一個很少使用的頁并把它的內容寫入磁盤。

針對虛擬地址到物理地址映射速度優化主要有：TLB（轉換檢測緩沖區）位于MMU里面。

TLB

TLB是一個內存管理單元用于改進虛擬地址到物理地址轉換速度的緩存。

TLB是位于內存中的頁表的cache，如果沒有TLB，則每次取數據都需要兩次訪問內存,即查頁表獲得物理地址和取數據.

虛擬內存

交換技術：針對于內存不足以程序運行的情況，有兩種方式，第一種是交換，將進程放入內存中執行后，再把它放回磁盤。故空閑進程會存放在磁盤中。第二種是虛擬內存。

虛擬存儲器，是指具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統。

具有多次性、對換性和虛擬性三大主要特征。

• 多次性：多次性是指一個作業被分成多次調入內存運行

• 對換性：對換性是指允許在作業的運行過程中進行換進、換出

• 虛擬性：虛擬性是指能夠從邏輯上擴充內存容量

虛擬內存主要由虛擬存儲器實現，具體內存管理也大體一樣，分為：請求分頁、請求分段、請求段頁式，

相關置換算法：

• 先進先出算法(FIFO)

• 最不經常使用算法(LFU)

• 最近最少使用算法(LRU)

文件系統

文件系統存儲在磁盤中。大部分的磁盤能夠劃分出一到多個分區，叫做磁盤分區。每個分區都有獨立的文件系統，每塊分區的文件系統可以不同。磁盤的 0 號分區稱為 主引導記錄(MBR)，用來引導(boot) 計算機。在 MBR 的結尾是分區表(partition table)。

當計算機開始引 boot 時，BIOS 讀入并執行 MBR。

引導塊

MBR 做的第一件事就是確定活動分區， 讀入引導塊(boot block) 并執行。引導塊中的程序將加載分區中的操作系統。為了一致性，每個分區都會從引導塊開始，即使引導塊不包含操作系統。引導塊占據文件系統的前 4096 個字節，從磁盤上的字節偏移量 0 開始。引導塊可用于啟動操作系統。

超級塊

超級塊 的大小為 4096 字節，從磁盤上的字節偏移 4096 開始。超級塊包含文件系統的所有關鍵參數

• 文件系統的大小
• 文件系統中的數據塊數
• 指示文件系統狀態的標志
• 分配組大小

在計算機啟動或者文件系統首次使用時，超級塊會被讀入內存。

空閑空間塊

用位圖或者鏈表管理空閑塊。

inode

索引節點。它是一個數組的結構，每個文件有一個 inode，inode 非常重要，它說明了文件的方方面面。

• 模式/權限（保護）
• 所有者 ID
• 組 ID
• 文件大小
• 文件的硬鏈接數
• 上次訪問時間
• 最后修改時間
• inode 上次修改時間

文件分為兩部分，索引節點和塊。一旦創建后，每種類型的塊數是固定的。

文件的實現

連續分配：按照連續數據塊進行分配。

• 優點：實現簡單、高性能
• 缺點：碎片問題

鏈表分配：按照鏈表方式分配數據塊，節點的是磁盤指針

• 優點：充分利用數據塊
• 缺點：不支持隨機訪問，IO代價大

inode：給每個文件賦予一個稱為 inode(索引節點) 的數據結構，每個文件都與一個 inode 進行關聯，inode 由整數進行標識。只有在文件打開時，其 inode 才會在內存中。

* 文件的字節數* 文件擁有者的User ID* 文件的Group ID* 文件的讀、寫、執行權限* 文件的時間戳，共有三個：ctime指inode上一次變動的時間，mtime指文件內容上一次變動的時間，atime指文件上一次打開的時間。* 鏈接數，即有多少文件名指向這個inode* 文件數據block的位置

目錄的實現

目錄項提供了查找文件磁盤塊所需要的信息。目錄系統的主要功能就是 將文件的 ASCII 碼的名稱映射到定位數據所需的信息上。

對于采用 inode 的系統，每個目錄項，由兩部分組成：所包含文件的文件名，以及該文件名對應的inode號碼。

共享文件

硬鏈接：多個文件名指向同一個inode號碼。【inode鏈接數會發生變化】

ln 源文件 目標文件

軟鏈接：文件A和文件B的inode號碼雖然不一樣，但是文件A的內容是文件B的路徑。

ln -s 源文文件或目錄 目標文件或目錄

磁盤調度算法：

• 先來先服務：磁盤臂按照FIFO原則移動
• 最短路徑優先：磁盤臂按照最短路徑優先原則移動
• 電梯算法：磁盤臂向一端移動后回來

提升性能

• 高速緩存：塊高速緩存、緩沖區高速緩存
• 塊提前讀：提前預讀下一個塊【針對順序讀取的文件】
• 減少磁盤臂運動：把有可能順序訪問的塊放在一起，當然最好是在同一個柱面上，從而減少磁盤臂的移動次數

IO

I/O 分為兩種：物理I/O 和 邏輯I/O(Logical I/O)。

物理 I/O 通常是從磁盤等存儲設備實際獲取數據。邏輯 I/O 是對存儲器（塊，緩沖區）獲取數據。

大部分物理IO(physical I/O) 是異步的。CPU 傳輸完成后會轉而做其他事情，等到中斷發生后，CPU 才會回到傳輸這件事情上來。

比較條件同步傳輸異步傳輸

概念	塊頭序列開始	它分別在字符前面和后面使用開始位和停止位。
傳輸方式	以塊或幀的形式發送數據	發送字節或者字符
同步方式	同步時鐘	無
傳輸速率	同步傳輸比較快	異步傳輸比較慢
時間間隔	同步傳輸通常是恒定時間	異步傳輸時間隨機
開銷	同步開銷比較昂貴	異步傳輸開銷比較小
是否存在間隙	不存在	存在
實現	硬件和軟件	只有硬件
示例	聊天室，視頻會議，電話對話等。	信件，電子郵件，論壇

緩沖

通常情況下，從一個設備發出的數據不會直接到達最后的設備。其間會經過一系列的校驗、檢查、緩沖等操作才能到達。優點：先到達緩沖區，從而消除緩沖區填滿速率和緩沖區過載。

共享和獨占

有些 I/O 設備能夠被許多用戶共同使用，但是某些設備必須具有獨占性，即只允許單個用戶使用完成后才能讓其他用戶使用。

此時采用**SPOOLing技術（假脫機技術）**將物理設備虛擬為多個邏輯設備，在隊列中調用設備，從而實現共享。

一共有三種控制 I/O 設備的方法

• 使用程序控制 I/O
• 使用中斷驅動 I/O
• 使用 DMA 驅動 I/O

使用程序控制 I/O

使用程序控制 I/O 又被稱為 可編程I/O，它是指由 CPU 在驅動程序軟件控制下啟動的數據傳輸，來訪問設備上的寄存器或者其他存儲器。CPU 會發出命令，然后等待 I/O 操作的完成。由于 CPU 的速度比 I/O 模塊的速度快很多，因此可編程 I/O 的問題在于，CPU 必須等待很長時間才能等到處理結果。CPU 在等待時會采用輪詢(polling)或者 忙等(busy waiting) 的方式，結果，整個系統的性能被嚴重拉低。

CPU 請求 I/O 操作

I/O 模塊執行響應

I/O 模塊設置狀態位

CPU 會定期檢查狀態位

I/O 不會直接通知 CPU 操作完成

I/O 也不會中斷 CPU

CPU 可能會等待或在隨后的過程中返回

使用中斷驅動 I/O

在 CPU 等待 I/O 設備的同時，能夠做其他事情，等到 I/O 設備完成后，它就會產生一個中斷，這個中斷會停止當前進程并保存當前的狀態。

CPU 進行讀取操作

I/O 設備從外圍設備獲取數據，同時 CPU 執行其他操作

I/O 設備中斷通知 CPU

CPU 請求數據

I/O 模塊傳輸數據

使用DMA的 I/O

DMA即直接內存訪問，它意味著 CPU 授予 I/O 模塊權限在不涉及 CPU 的情況下讀取或寫入內存。即 IO 過程不需要 CPU 的參與。由于 DMA 設備可以直接在內存之間傳輸數據，而不是使用 CPU 作為中介，因此可以緩解總線上的擁塞。DMA 通過允許 CPU 執行任務，同時 DMA 系統通過系統和內存總線傳輸數據來提高系統并發性。

中斷處理程序

中斷處理程序步驟：

保存所有沒有被中斷硬件保存的寄存器

為中斷服務程序設置上下文環境，可能包括設置 TLB、MMU 和頁表

為中斷服務程序設置棧

對中斷控制器作出響應，如果不存在集中的中斷控制器，則繼續響應中斷

把寄存器從保存它的地方拷貝到進程表中

運行中斷服務程序，它會從發出中斷的設備控制器的寄存器中提取信息

操作系統會選擇一個合適的進程來運行。如果中斷造成了一些優先級更高的進程變為就緒態，則選擇運行這些優先級高的進程

為進程設置 MMU 上下文，可能也會需要 TLB，根據實際情況決定

加載進程的寄存器，包括 PSW 寄存器

開始運行新的進程

設備驅動程序

操作系統通常會將驅動程序歸為 字符設備 和 塊設備

提供 I/O 設備到設備控制器轉換的過程的代碼稱為 設備驅動程序(Device driver)

設備驅動程序接受到讀寫請求后，會檢查當前設備是否在使用，如果設備在使用，請求被排入隊列中，等待后續的處理。如果此時設備是空閑的，驅動程序會檢查硬件以了解請求是否能夠被處理。在傳輸開始前，會啟動設備。等待設備就緒完成，再進行實際的控制。控制設備就是對設備發出指令。

設備控制器的主要主責是控制一個或多個 I/O 設備，以實現 I/O 設備和計算機之間的數據交換。

設備控制器接收從 CPU 發送過來的指令，繼而達到控制硬件的目的。

了解更多知識干貨，🙋?♂?關注公眾號：學編程的文若

總結

以上是生活随笔為你收集整理的程序员不得不学的操作系统知识（三）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。