操作系統複習筆記

期末複習#

第三章進程#

操作系統進行任務調度和資源分配的基本單位
進程包括：
1. 程式碼
- 文本區
1. 程式計數器和處理器的寄存器
2. 堆疊
- 函數參數
- 返回地址
- 局部變數
1. 數據區
- 全局變數
1. 堆
- 動態分配的內存
進程狀態
- 五態模型
  - 新建
  - 就緒：等待分配給處理器
  - 等待：等待某些事件發生
  - 執行中
  - 終止
進程控制塊（PCB）
- 包含的信息有：
  - 進程編號
  - 進程狀態
  - 程式計數器
    - 下一條指令的地址
  - CPU 寄存器
  - CPU 調度信息
  - 內存管理信息
  - 計費信息
  - I/O 狀態信息

進程調度#

調度隊列
1. 作業隊列
- 系統中所有進程的集合
- 當進程 / 作業進入系統時，它們被放入作業隊列
1. 就緒隊列
- 所有在 “（主）內存” 中居住的進程的集合，準備好並 “等待” 執行
1. 設備隊列
- 等待 I/O 設備的進程集合
調度器
1. 長期調度器或作業調度器
- 作業隊列 -> 就緒隊列
- 在 UNIX 和 Windows 等時間共享系統上可能不存在
  - 它們將每個新進程放入內存以供短期調度器使用
1. 短期調度器或 CPU 調度器：進程調度
- 選擇下一個應該執行的進程並分配 CPU
- 由於其執行非常頻繁，因此每次選擇不能耗時太長，否則就會產生開銷
1. 中期調度器或交換
- 交換出：將進程從內存移除到磁碟並減少多道程序的程度
- 交換進：將進程引入內存
上下文切換
- CPU 切換到另一個進程

進程操作#

fork()
- 新進程由原始進程的地址空間的副本組成
- fork () 的返回碼對於子進程為零
- 子進程會複製父進程的地址空間和資源，但不會複製父進程的線程

進程間通信#

共享內存
消息傳遞

名詞解釋：#

多道程序設計：是指始終有一些進程在運行，以最大化 CPU 利用率
時間共享：是指在進程之間如此頻繁地切換 CPU，以便用戶可以與每個進程互動

第四章線程#

進程 vs 線程
- 線程是 CPU 的分配單位
- 進程是資源的分配單位
- 線程是進程中的執行單元
  - 一個進程可以包含多個線程，它們共享相同的地址空間和系統資源，如打開的文件、信號。
  - 每個線程有自己的堆疊空間和執行上下文，但它們在同一進程內共享代碼段、數據段和堆等資源。
多線程編程的好處
1. 響應性
2. 資源共享
3. 經濟性
4. 多處理器架構的利用

多線程模型#

兩種線程
- 用戶線程
  - 由用戶級的線程庫提供
- 內核線程
  - 由操作系統直接提供和管理
內核線程和用戶線程之間的關係
1. 多對一模型
2. 一對一模型
3. 多對多模型
4. 二級模型
  - 主體是多對多模型
  - 一個用戶線程（重要任務）可以綁定到一個內核線程
UNIX 系統中的兩個版本的 fork ()
1. 複製所有線程
  - 如果在 fork () 後不調用 exec ()，則複製所有線程
2. 只複製調用 fork () 系統調用的線程
  - 如果在 fork () 後立即調用 exec ()，則僅複製調用線程

第五章 CPU 調度#

基本概念#

CPU 調度決策可能在進程：
1. 從運行狀態切換到等待狀態
  - I/O 請求的結果
  - 等待子進程之一終止的調用（例如 wait (NULL);）
2. 從運行狀態切換到就緒狀態
  - 當發生中斷時
3. 從等待狀態切換到就緒狀態
  - I/O 完成
4. 終止
非剝奪式
- 一旦 CPU 被分配給一個進程，該進程將保持 CPU 直到釋放 CPU
- 調度只可能發生在情況 1 和 4。
- 簡單，硬件要求低
剝奪式

調度標準#

CPU 利用率
CPU 吞吐量
- 每時間單位完成執行的進程數。
進程周轉時間
- 從提交進程的時間到完成的時間，包括
  - 等待進入內存
  - 等待在就緒隊列中
  - 在 CPU 上執行
  - 進行 I/O
進程等待時間
- 進程在就緒隊列中等待的時間。
進程響應時間
- 從提交請求到產生第一次響應 / 結果的時間

調度算法#

先來先服務（FCFS）
- 非剝奪式
- 護航效應
最短作業優先（SJF）
- 最小平均等待時間
- 種類
  1. 剝奪式 SJF 允許剝奪當前執行的進程
  2. 非剝奪式
- 比較適用於長程調度
優先級調度
- 問題：飢餓
- 解決：老化 – 隨著時間推移提高進程的優先級
時間片輪轉（RR）
- 專為時間共享系統設計
- 剝奪式
- 時間片
  - 需要保證 80% 的 CPU 突發 < 時間片
- 響應時間 = 2*(n-1)*q
多級隊列算法
多級反饋隊列算法
- 最通用的調度算法

多處理器調度#

同質 vs. 異質 CPU
- 同質：各處理器都一樣
多處理器調度的方法
- 非對稱多處理
  - 只有一個處理器（主伺服器）擁有所有調度決策，I/O 處理
- 對稱多處理
  - 每個處理器都是自我調度的

第六章進程同步#

競爭條件
- 多個進程同時訪問和操作共享數據的情況。
- 共享數據的最終值取決於哪個進程最後完成。

臨界區問題#

臨界區
- 每個進程都有一段代碼，稱為臨界區，在其中訪問共享數據
- 有幾個共享變數就有幾個臨界區
臨界區問題解決的標準
1. 互斥
2. 進步
3. 有限等待
彼得森解法
- 舉手 + 令牌
硬件基礎解法
- 關中斷
  - 多處理機不適合
- 原子操作

信號量#

信號量 S – 整數變量
- 可以通過非負值初始化
- 只能通過兩個不可分割（原子）操作訪問：P () 和 V ()

P (): 等待操作

wait (S) { 
  while (S.value <= 0) ; 	// no-op
    S.value--;
}

V () 信號操作
```
signal(S){
  S.value++;
}
```
主要問題：忙等待（自旋鎖）
- 優點
  1. 當進程必須等待鎖時，不需要上下文切換
  2. 如果預期鎖持有的時間很短，自旋鎖是有用的
- 缺點
  1. 浪費可以被其他進程有效利用的 CPU 週期
- 解決：修改 wait () 和 signal () 的定義 適用於多處理器系統
  - Wait (): 進程可以阻塞自己而不是忙等待
  - Signal (): 將阻塞進程從等待狀態改變為就緒狀態
實現
1. 在單處理器環境中
- 禁用中斷
1. 在多處理器環境中
- 可以應用臨界區

第七章死鎖#

必要條件
1. 互斥
2. 保持與等待
3. 無剝奪
4. 循環等待

處理死鎖的方法#

預防
- 提供一組方法以確保至少一個必要條件無法成立
- 針對條件 2：全有或全無；沒有資源時才去申請
- 針對條件 3：謙讓；搶奪
- 針對條件 4：順序執行
- 缺點：設備利用率低，降低系統吞吐量。
避免
- 使用附加信息，決定當前請求是否可以滿足或必須延遲
- 方法：
  1. 資源分配圖
    - 有環：處於不安全狀態；可能處於死鎖狀態
  2. 銀行家算法
檢測與恢復
- 方法:
  - 等待圖
    - 不適用於具有每種資源類型多個實例的資源分配系統
  - 銀行家算法
- 何時以及多頻繁地調用檢測算法，取決於：
  - 死鎖發生的頻率？
  - 需要回滾的進程數量？
無視

第八章#

地址可以表示為
1. 符號地址
2. 可重定位地址
3. 絕對地址
地址綁定
- 轉換：
  - 符號地址 -> 可重定位地址：編譯器
  - 可重定位地址 -> 絕對地址：連結編輯器或加載器
- 發生的時期
  1. 編譯時
    - 如果在編譯時已知內存位置，則可以生成絕對代碼
    - 如果在編譯時未知內存位置，必須生成可重定位代碼
  2. 加載時（+ 連結時）
    - 如果在加載時已知內存位置，則可以在此時生成絕對代碼
  3. 執行時
    - 如果在編譯時和加載時未知內存位置，則綁定延遲到運行時
    - 必須在運行時生成絕對代碼

邏輯地址與物理地址空間#

邏輯地址：CPU
- 也稱為虛擬地址
- 重定位地址和邏輯地址沒有直接關係
物理地址：內存單元
邏輯（虛擬）和物理地址在執行時地址綁定方案中有所不同
- 可重定位代碼由 CPU 看到
- 絕對代碼由內存單元看到
內存管理單元（MMU）
- 硬件設備，將虛擬地址映射到運行時的物理地址
動態加載
- 在進程執行之前，並不需要將整個程序和數據加載到物理內存中，直到它被調用
- 好處：
  1. 更好的內存空間利用
  2. 操作系統不需要特殊支持
動態連結
- 連結被推遲到執行時
- 需要操作系統的幫助

連續內存分配#

固定大小的連續分區
- 優勢
  - 實現簡單
  - 開銷小
- 缺點
  - 內部碎片
    - 分配的內存可能大於請求的內存
  - 固定數量的進程
動態連續分區（可變分區）
- 孔 – 可用內存的區塊
- 分配算法
  1. 首次適合：
    - 從頭開始，或者從當前位置開始
  2. 最佳適合
    - 需要搜索整個列表，除非列表按大小排序
    - 產生的剩餘孔可能是最小的
  3. 最差適合
    - 需要搜索整個列表，除非列表按大小排序
    - 小進程多的效果好
- 問題：
  - 外部碎片

碎片解決方案
1. 壓縮
  - 減少外部碎片
  - 隨機內存內容以將所有空閒內存放在一個大塊中
  - 在執行時進行，只有在重定位是動態的情況下才有可能
  - 可能在移動進程和孔時成本高
2. 分頁
3. 分段
連續內存分配的缺點
- 主內存中的碎片
- 磁碟上的壓縮是不可能的

分頁#

幀：將物理內存劃分為固定大小的塊
頁：將邏輯內存劃分為固定大小的塊
- 頁大小等於幀大小
- 尋找 n 個空閒幀以加載大小為 n 頁的程序
將邏輯地址轉換為物理地址
如果地址空間為 2^m 且頁大小為 2^n
- 每個由 CPU 生成的邏輯地址被劃分為：
  1. 頁號 (p: 頁號)
    - 用作頁表的索引
    - 頁表中包含每一頁在物理內存的基地址 (f: 塊號)
    - p = 地址 / 2^n 等於地址的 m-n 位
  2. 頁偏移 (d: 偏移)
    - 與基地址 (f: 塊號) 結合以定義發送到內存單元的物理內存地址
    - d = 地址 %2n 等於地址的 n 位
- 物理地址
  1. 幀號（f: 幀號、塊號)
  2. 頁偏移 (d: 頁偏移、塊偏移)
頁大小的選擇
- 越大：
  - 磁碟 I/O 更有效
  - 頁表大小越小
- 越小：
  - 內部碎片越小
幀表
- 每個物理頁幀有一個條目
  指示
  - 幀是空閒的還是分配給哪個進程
頁表
- 每個進程必須維護一個頁表的副本
- 計算
  - 如果頁表條目長度為 4 字節
    - 可以指向 2^32 個物理頁幀中的一個（1 比特 = 8 字節）
    - 如果幀大小（= 頁大小）為 4KB，則系統可以尋址 2^44 字節（2^32×2^12=16TB）的物理內存
  - 對於 32 位 CPU
    - 頁大小：4k (=2^12)
    - 表大小：2^32/2^12=1M
    - 每個條目的大小：4 字節
    - 頁表的大小為：4 MB
- 位置
  1. 直接存放在寄存器中：
    - 高效且昂貴
    - 當頁表合理小時可以
  2. 存放在主內存中，然後用頁表基址寄存器（PTBR）存放其位置
    - 進程切換時，載入頁表只需要改變 PTBR
    - 每次數據 / 指令訪問需要兩次內存訪問
      - 一次用於頁表
      - 一次用於數據 / 指令
  3. 翻譯後備緩存（TLB）也稱為聯想記憶體
    - 並行查找
    - 僅包含少量頁表條目

頁表結構#

問題：頁表可能過於龐大
解決方案：將頁表劃分為更小的部分
1. 分層分頁
2. 哈希頁表
3. 反向頁表

分層分頁
- 缺陷：
1. 需遍歷，進程太多
2. 可能有共享，而進程號只能填一個
3. 不適用於 64 位
- 好處：
  1. 需要的空間小
哈希頁表
- 哈希表 -> 在鏈表中遍歷匹配
反向頁表

系統中只有一個頁表
每個實際頁（或物理幀）都有一個條目
缺點：
- 當頁引用發生時，增加搜索表所需的時間
- 導致內存共享困難

分段#

用戶對程序的看法：程序是一組段，段是一個邏輯單元，例如：
- 主程序
  - 程序，函數，方法，對象
  - 局部變數，全局變數
  - 公共區塊
  - 堆疊
  - 符號表
  - 數組

第九章虛擬內存#

整個程序不需要在物理內存中。這樣的好處有：
- 程序的大小不再受內存所限制
- 更多程序可以同時運行
- 加載或交換每個用戶程序到內存所需的 I/O 更少，因此程序將開始更快地運行
虛擬內存管理
- 用於描述一種技術的術語，該技術使計算機似乎擁有比實際更多的內存
虛擬內存可以通過以下方式實現：
- 按需分頁
- 按需分段

按需分頁#

思想：僅在需要時將頁帶入內存
- 與交換的分頁系統相似
硬件
- 頁表。需要加一位有效–無效位
  - v -》頁是合法的並且在內存中
- 次級存儲
  - 高速磁碟，交換空間
  - 保存那些不在內存中的頁
頁錯誤
- 訪問標記為無效的頁會導致頁錯誤陷阱
- 處理
  1. 操作系統查看另一個表（PCB）以決定：
    - 無效引用 -> 中止
    - 只是未在內存中（繼續到 2）
  2. 獲取空幀
  3. 將所需頁交換到幀中
  4. 修改頁表，設置驗證位 = v
  5. 重新啟動導致頁錯誤的指令
- 特殊：
  1. 一條指令可產生多個缺頁中斷
  2. 指令重執
  3. 在指令執行時中斷。
- 與普通中斷的對比：
  - 一條指令在執行完後，檢查是否有中斷請求
    - 有：執行中斷
    - 無：執行下一條指令

頁替換#

替換算法

先進先出頁替換
- 貝拉迪異常：更多幀 -> 更多頁錯誤
最優頁替換（OPT）
- 替換最晚才用的頁或後面最長時間用不到的頁
最近最少使用（LRU）算法
- 思想：最近的過去作為近期未來的近似
- 實現：
- 計數器
- 堆疊
LRU 近似算法
1. 附加引用位算法
2. 第二次機會（時鐘）
3. 增強的第二次機會算法
基於計數的頁替換
- 最少使用
- 最多使用
頁緩衝算法
- 頁替換算法的輔助程序

幀的分配#

兩種主要的分配方案
1. 固定分配
  - 平均分配
  - 按比例分配
2. 優先級分配
  - 使用按比例分配方案，使用優先級而不是大小
全局 vs. 本地分配
1. 本地替換
  - 允許進程僅從其自己的分配幀集中選擇。
  - 不能增加分配的幀數
  - 不受外部環境影響
2. 全局替換
  - 允許進程從所有幀的集合中選擇替換幀，即使該幀當前分配給其他進程
  - 可以增加分配的幀數
  - 不能控制其頁錯誤率。
- 一般來說，全局替換更好。

顛簸#

如果一個進程花費更多時間在分頁而不是執行，那麼它就是顛簸的
方法
1. 使用本地替換算法
2. 工作集策略
  - 計算系統中每個進程的工作集大小
3. 頁錯誤頻率（PFF）方案
  - 如果實際率太低，則從進程中移除一個幀
  - 如果實際率太高，則為進程分配另一個幀
  - 如果沒有幀是空的，則暫停它

其他考慮#

頁大小的選擇要考慮到：
1. 內部碎片
2. 頁表的大小
3. I/O 開銷（尋道時間、延遲時間、傳輸時間）
4. 局部性
5. 頁錯誤率
  - 順序訪問：頁大小越大，則缺頁中斷率越小
  - 隨機訪問：頁大小越大，則可能導致更多的分頁操作，因為可以在內存中保留的頁面更少，且每次頁錯誤傳輸的數據更多。
安裝更快的硬碟，或多個控制器與多個硬碟
- 隨著磁碟瓶頸被更快的響應和更多的吞吐量消除，CPU 將更快地獲取更多數據

第十章文件系統介面#

文件
- 文件是記錄在次級存儲上的相關信息的命名集合
- 六個基本操作
  1. 創建
  2. 讀取 / 寫入 / 尋找
  3. 刪除
  4. 截斷：擦除文件的內容，但保留其屬性，除了長度
- 輔助操作
  - 打開 (F):
    1. 在磁碟上搜索目錄結構以查找條目 F
    2. 將目錄條目複製到打開文件表中
    3. 分配文件描述符
  - 關閉 (F):
    1. 將打開文件表中的目錄條目複製到磁碟上的目錄結構中
    2. 釋放文件描述符

訪問方法#

文件中的信息可以以
1. 順序訪問
2. 直接訪問
3. 其他訪問
  - 涉及為文件構建索引

目錄結構#

符號表
- 目錄可以被視為一個符號表，將文件名轉換為其目錄條目
標準
1. 效率
2. 命名
3. 分組
結構
1. 單級目錄
2. 雙級目錄
  - 優點
    - 高效搜索
  - 缺點
    - 無法分組
    - 難以在不同用戶之間共享文件
3. 樹狀結構目錄
  - 優點
    - 高效搜索
    - 分組能力
  - 缺點
    - 難以在不同用戶之間共享文件
4. 無環圖目錄
  - 樹狀結構目錄 + 共享子目錄或文件
  - 創建一個新的目錄條目稱為鏈接以實現共享
  - 難點是避免在添加新鏈接時形成循環
5. 一般圖目錄
  - 將鏈接添加到現有的樹狀結構目錄
  - 無環圖目錄更好
硬鏈接
- ln /usr/local/python3 python
- 目錄中僅存儲指向文件數據的指針
- 允許一個文件被多個目錄引用。
- 無法用來鏈接目錄，也不能跨文件系統
- 通過ls -i查看是否為硬鏈接
軟鏈接
- “快捷方式”
- 軟鏈接也是一個文件
- ln -s ../p24 p24
- 目錄從 “樹” 變為 “圖”，仍然是有環圖
ACL: 訪問控制列表
- 每個文件或目錄都有一個 ACL

文件系統實現#

文件系統組織為多層
1. 應用程序
2. 邏輯文件系統
  - FCB: 文件控制塊
3. 文件組織模塊
4. 基本文件系統
5. I/O 控制
6. 設備

分配方法#

分配方法是指如何為文件分配磁碟塊
連續分配
- 每個文件佔用磁碟上的一組連續塊
- 支持順序訪問和直接訪問（隨機訪問）
- 問題：
  1. 外部碎片
  2. 文件無法增長
鏈接分配
- 每個文件是一個磁碟塊的鏈接列表：塊可以隨意散佈在磁碟上
- 優點
  1. 容易實現
  2. 無外碎片
  3. 文件增長方便
- 缺點：
  1. 無隨機訪問
  2. 可靠性差
  3. 慢（鏈表保存在磁碟上，因此需要多次查詢）
- 改進：文件分配表（FAT）
  - 將鏈表信息放到一個單獨的 FAT 表中，而不是各個數據塊中，並進行備份
索引分配
- 將所有指針集中到一個位置：索引塊
- 解決大文件的方案
  1. 鏈接方案
    - 鏈接索引表的塊
  2. 多級索引
  3. 組合方案
    - 一部分是直接指針，一部分是多重間接塊
- 標準
  1. 存儲利用效率
  2. 數據塊訪問時間
  - 連續分配：適合已知大小的文件
  - 鏈接分配：適合存儲利用
  - 索引分配：訪問時間取決於索引結構、文件大小、塊位置

空間管理#

空間列表的實現
1. 位向量
  - 優點
    - 實現簡單
    - 高效查找第一個空閒塊
  - 缺點
    - 位圖需要額外空間
    - 除非整個向量保存在主內存中，否則效率低
2. 鏈接列表（空閒列表）
  - 優點
    - 無空間浪費
  - 缺點
    - 遍歷列表時效率低
3. 分組
- 第一個空閒塊存儲 n 個空閒塊的地址
- 更容易找到大量空閒塊

大容量存儲系統#

磁碟的結構
- 磁碟盤
- 磁道
- 扇區
  - 每個磁道被劃分為幾個扇區
- 圓柱
  - 是在一個臂位置的磁道集合
CLV vs. CAV
1. CLV : 恆定線性速度
  - CD-ROM， DVD-ROM
  - 最外層區域的磁道包含更多扇區
2. CAV : 恆定角速度
  - 磁碟
  - 為保持數據速率恆定，從內部磁道到外部磁道的位元密度減少

磁碟調度#

訪問時間
1. 尋道時間是磁碟臂移動到包含所需扇區的圓柱所需的時間
  - 尋道時間  尋道距離
2. 旋轉延遲
  - 等待磁碟旋轉所需扇區到達磁碟頭
磁碟帶寬
- 總傳輸字節數 / 從第一次請求服務到最後一次傳輸完成的總時間

FCFS 調度
SSTF：最短尋道時間優先（SSTF）
- 最短尋道時間優先
- 問題：
  - 往返跑 --- 距離很短，但速度不一定很快
  - 可能導致某些請求的飢餓
SCAN

有時稱為電梯算法

C-SCAN（循環掃描）

磁碟頭從磁碟的一端移動到另一端，服務請求
當它到達另一端時，立即返回磁碟的開頭，而不在返回途中服務任何請求
回途不載客

LOOK / C-LOOK

類似於 SCAN/C-SCAN
臂僅移動到每個方向的最後請求，然後立即反向，而不必先到達磁碟的末端。
選擇
性能取決於請求的數量和類型
- SCAN 和 C-SCAN 在對磁碟施加重負載的系統中表現更好
- SSTF 或 LOOK 是默認算法的合理選擇

磁碟管理#

磁碟格式化
- 低級格式化（物理格式化）
  - 將磁碟劃分為磁碟控制器可以讀取和寫入的扇區
- 邏輯格式化
  - 創建文件系統
  - 為文件系統構建元數據結構

RAID 結構#

廉價磁碟冗餘陣列（過去）
獨立磁碟冗餘陣列（現在）
- 用於其更高的可靠性和更高的數據傳輸速率（性能）
級別
1. RAID 0
  - 在塊級別進行數據條帶化的磁碟陣列，但沒有任何冗餘
2. RAID 1
  - 磁碟鏡像
3. RAID 2
  - 位級條帶化或字節級條帶化
  - 記憶體風格的錯誤更正碼（ECC）
4. RAID 3
  - 位交錯奇偶校驗
5. RAID 4
  - 塊交錯奇偶校驗組織
6. RAID 5
  - 塊交錯分佈奇偶校驗

常用單詞#

simultaneously : 同時地
idle : 空閒，懶
reside : 位於，居住
uni-processor : 單處理器
interleave: 交織
allocation : 分配
dashed line ：虛線
minuscule : 微小的
concrete : 具體的
mandatory: 強制的
mediate : 調解
strip : 脫掉；條

操作系統複習筆記

期末複習#

第三章 進程#

進程調度#

進程操作#

進程間通信#

名詞解釋：#

第四章 線程#

多線程模型#

第五章 CPU 調度#

基本概念#

調度標準#

調度算法#

多處理器調度#

第六章 進程同步#

臨界區問題#

信號量#

第七章 死鎖#

處理死鎖的方法#

第八章#

邏輯地址與物理地址空間#

連續內存分配#

分頁#

頁表結構#

分段#

第九章 虛擬內存#

按需分頁#

頁替換#

幀的分配#

顛簸#

其他考慮#

第十章 文件系統介面#

訪問方法#

目錄結構#

文件系統實現#

分配方法#

空間管理#

大容量存儲系統#

磁碟調度#

磁碟管理#

RAID 結構#

常用單詞#

第三章進程#

第四章線程#

第六章進程同步#

第七章死鎖#

第九章虛擬內存#

第十章文件系統介面#