? 2022 新年第一篇，獻給了 OS
每個考點已配對：詳細決議 + 詳細例題

---

---

PUBG ??

---

一、考試形式

● 10 道單選 —— 10 × 1(分)

● 10 道填空 —— 10 × 2(分)

● 30分的簡答題(概念與計算)

● 4 道綜合計算題 —— 10 × 4(分)

◆ 補充說明：總共有 5 種綜合計算題，只選其中的四種進行考察，后文有講解，

---

二、考察點

1.?? —— 多道程式系統

2.???? —— 行程及其實作

3.???????? —— 處理器調度 + 作業的管理和調度

4.?? —— 并發行程

5.???????? —— 信號量與 P、V 操作

6.?????????? —— 死鎖

7.?? —— 重定位

8.???? —— 可變磁區

9.?????? —— 頁式存盤管理

10.?? —— 段氏存盤管理

11.?????? —— 頁面置換演算法

12.?? —— I/O 控制方式

13.????—— 緩沖技術

14.???????? —— 驅動調度技術

15.?? —— 設備獨立性

16.?????? —— 檔案的物理結構與存盤設備

17.?? —— 檔案存盤空間的管理

● 注：以上內容已覆寫 80% ~ 90% 的考試內容，

---

---

---

三、考試重點的排序 + 簡單分析

序號	重點	內容
1	?????????? —— 死鎖	【占了整張試卷的高分值，填空 + 選擇 + 10分大題】 【死鎖的定義、產生的原因、4個必要條件、處理死鎖的3種方法(對比、優缺點)】 【死鎖的應用】 【大題就是銀行家演算法，需注意格式、中間變數、表格】
2	???????? —— 信號量與 P、V 操作	【填空題 + 10分大題】 【行程的同步與互斥，理解清楚】 【主要看記錄型信號量，其他型別也要看看】 【注：語法可以用類C語言、PV的順序一定不能錯】
3	???????? —— 驅動調度技術	【這里有一道綜合的 10分大題】 【4種調度演算法、讀取步驟、磁盤結構、特點】
4	???????? —— 處理器調度 + 作業的管理和調度	【這里有一個兩級調度的大題，比如說上課寫的那種，10分大題】
5	?????? —— 頁面置換演算法	【 一道 10分大題，3種置換演算法要掌握：FIFO、LRU、OPT，并會計算缺頁中斷率】
6	?????? —— 檔案的物理結構與存盤設備	【可能有混合索引的復雜計算，考試難點】 【地址如何計算、映射怎么實作、一次鏈接？二次鏈接？】
7	?????? —— 頁式存盤管理	【基本分頁是面向系統的，也會產生碎片】 【頁式地址轉換：頁表項、頁內位移位、邏輯地址轉換為物理地址(填空選擇)】
8	???? —— 行程及其實作	【三態模型的概念、個數、轉換流程，概念簡答題】 【什么是行程控制塊(PCB)，描述了哪些資訊？】
9	???? —— 可變磁區	【4種磁區演算法，要能用語言描述、優缺點(背)、特點，】
10	???? —— 緩沖技術	【為什么要引入緩沖技術？】 【有時間看看這 4 個緩沖】
11	?? —— 多道程式系統	【設計的概念 → 目的是什么？概念簡答題】
12	?? —— 并發行程	【引入的目的 → 看樣例，看并發可能會導致什么錯誤出現？】
13	?? —— 重定位	【動態重定位的優缺點】
14	?? —— 段氏存盤管理	【了解分段和分頁在概念上的區別 → 更少的碎片】
15	?? —— I/O 控制方式	【4種方式出現的時間段、發展的驅動力是什么？概念簡答題】
16	?? —— 設備獨立性	【考簡答題，概念，如何實作？概念簡答題】
17	?? —— 檔案存盤空間的管理	【引入的原因、功能，了解一下位示圖法，填空選擇】

● 注：以上內容已覆寫 80% ~ 90% 的考試內容，接下來將對其一一進行講解，

---

---

---

四、一紙，一筆，一個晚上，一個奇跡 ?

1、?????????? —— 死鎖

【占了整張試卷的高分值，填空 + 選擇 + 10分大題】
【大題就是銀行家演算法，需注意格式、中間變數、表格】
【死鎖的定義、死鎖產生的原因、4個必要條件、處理死鎖的3種方法、3 種方法的對比與優缺點、死鎖的應用】

● 相關內容全部都在這里面，銀行家演算法可以看下一篇(寫得更詳細)，鏈接： 【作業系統⑩】——行程死鎖【銀行家演算法+詳細樣例 行程死鎖的預防機制、避免機制、檢測與解決】.
【都要看，這是大考點 】

● 關于銀行家演算法，小編已用C++實作，并附加有一個詳細的樣例，鏈接：《銀行家演算法——C++實作 [開源代碼 + 詳細決議]》.

● 重點標注一下上面 “灰色模塊” 里的內容：

① 死鎖的定義：系統中(兩個或者)多個行程無限期地等待永遠不會滿足的條件，處于停滯狀態，稱為行程死鎖，

② 死鎖產生的原因：
??[1] 系統資源不足，
??[2] 行程運行推進的順序不合適，
??[3] 資源分配不當，

③ 產生死鎖的4個必要條件：
??[1] 互斥使用(資源獨占)：指行程對所分配到的資源進行排它性使用，即在一段時間內某資源只由一個行程占用，如果此時還有其它行程請求資源，則請求者只能等待，直至占有資源的行程用畢釋放，

??[2] 不可強占(不可剝奪)：資源申請者不能強行地從資源占有者手中奪取資源，資源只能由占有者自愿釋放，

??[3] 請求保持(部分分配，占有申請)：行程在申請新資源的同時保持對原有資源的占有，

??[4] 回圈等待(環路等待條件)：指在發生死鎖時，必然存在一個行程——資源的環形鏈，即行程集合 {P0，P1，P2，···，Pn} 中的 P0 正在等待一個 P1 占用的資源；P1 正在等待 P2 占用的資源，……，Pn 正在等待已被 P0 占用的資源，

④ 處理死鎖的3種方法：
● 死鎖的處理策略：為使系統不發生死鎖，必須設法破壞產生死鎖的4個必要條件之一，或者允許死鎖產生，但當死鎖發生時能檢測出死鎖，并有能力實作恢復，

??[1] 預防死鎖：設定某些限制條件，破壞產生死鎖的4個必要條件中的一個或幾個，以防止發生死鎖，

??[2] 避免死鎖：在資源的動態分配程序中，用某種方法防止系統進入不安全狀態，從而避免死鎖，(銀行家演算法)

??[3] 死鎖的檢測及解除：無需采取任何限制性措施，允許行程在運行程序中發生死鎖，通過系統的檢測機構及時地檢測出死鎖的發生，然后采取某種措施解除死鎖，

◆ 補充說明：預防死鎖和避免死鎖都屬于事先預防策略，但預防死鎖的限制條件比較嚴格，實作起來較為簡單，但往往導致系統的效率低，資源利用率低；避免死鎖的限制條件相對寬松，資源分配后需要通過演算法來判斷是否進入不安全狀態，實作起來較為復雜，

⑤ 處理死鎖 3 種方法的對比與優缺點：

專案	資源分配策略	主要優點	主要缺點
死鎖的預防	保守分配，寧可資源閑置(即保證死鎖不會發生)	適用于做突發式處理的行程，不需要進行剝奪	效率低，行程初始化的時間會延長；剝奪次數過多；不便靈活申請新資源
死鎖的避免	是 “預防” 和 “檢測” 的折中(通過銀行家演算法判斷，在運行程序中是否可能有死鎖產生)	不需要進行剝奪	必須知道將來的資源需求；行程不能被長時間阻塞
死鎖的檢測與解除	定期檢測是否有死鎖的發生，若有則采取某種措施解除死鎖	不會延長行程初始化的時間，允許對死鎖進行現場處理	通過剝奪解除死鎖會造成損失

⑥ 死鎖的應用：
??[1] 生產者-消費者問題
??[2] 經典的讀寫問題
??[3] 經典的獨木橋問題

---

2、???????? —— 信號量與 P、V 操作

【填空題 + 10分大題】
【行程的同步與互斥，理解清楚】
【主要看記錄型信號量，其他型別也要看看】
【注：語法可以用類 C 語言、PV 的順序一定不能錯】

● “行程的同步與互斥” 的重點內容都在： 【作業系統⑥】——行程聯系與臨界區管理【同步與互斥 Dekker演算法 TS指令 SWAP指令】.
【主要看 “一、行程聯系” 】

● “PV操作” 的重點內容全部都在這里面： 【作業系統⑦】——信號量與PV操作(上)【生產者消費者經典問題】.
【注：里面的每一道例題(都是記錄型信號量)，小編都已補充詳細的注釋】

◆ 補充說明：關于 PV操作，如果能掌握【作業系統⑥】文章里面的大部分例題，考試完全 OK 的，

● 關于 “PV操作” 的其他型別信號量(比如AND型信號量)在這里面： 【作業系統⑧】——信號量與PV操作(下)【哲學家進餐問題 AND型信號量 信號量集機制】.

● 下面補充兩道關于 PV操作 的例題來練手：

題目①：若有一個檔案 F，供行程共享，現把行程分成 A、B 兩組，規定同組的行程可以同時讀檔案 F，但當有 A 組（或 B 組）的行程在讀檔案 F 時，不允許 B 組（或 A 組）的行程讀檔案 F，現定義兩個計數器 c1 和 c2 分別記錄 A 組和 B 組中讀檔案 F 的行程數，當用 P、V 操作進行管理時需要三個信號量 S1、S2、Sab 才能保證正確的并發執行，試寫出對應的程式，

● 題目關鍵字提取：【分析主要看代碼和后面的 “代碼說明”】
??[1] “A 組某人讀檔案 F”，
??[2] “B 組某人讀檔案 F”，
??[3] “同組的人可以同時讀檔案 F”，
??[4] “非同組的人不可以同時讀檔案 F”，

● 代碼如下：

/* 基于 C 語言寫的偽代碼 */
semaphore c1 = 0, c2 = 0;	// c1、c2 分別是 A、B 組的計數器
semaphore S1 = 1, S2 = 1;	// S1、S2 分別是計數器 c1、c2 的互斥信號量
semaphore Sab = 1;			// Sab 是 a、b 兩組間的互斥信號量
while(true)
{
	"A組行程 Ai():"		// i = 1, 2, 3, ..., a
	while(true)
	{
		P(S1);
        if( c1 == 0 )
        	P(Sab);
        c1 = c1 + 1;
        V(S1);
        讀檔案 F;
        P(S1);
        c1 = c1 - 1;
        if( c1 == 0 )
			V(Sab);
        V(S1);		
	}
	
	"B組行程 Bj():"		// j = 1, 2, 3, ..., b
	while(true)
	{
		P(S2);
        if( c2 == 0 )
        	P(Sab);
        c2 = c2 + 1;
        V(S2);
        讀檔案 F;
        P(S2);
        c2 = c2 - 1;
        if( c2 == 0 )
			V(Sab);
        V(S2);	
	}
}

◆ 代碼說明：
??① 因為只有一個檔案 F，所以 S1 和 S2 都只能初始化為 1，
??② A、B 組的計數器 c1、c2 一開始都初始化為0，是因為一開始 A 組和 B 組都沒有人在讀檔案，
??③ 每次要對 c1、c2 兩個進行操作時，都必須要用 P、V 組合操作，
??④ 小編自己寫的類 C 語言(如果有不對的地方，歡迎評論指出)，考試要求什么偽代碼語言都可以，包括 Pascal，

題目②：有橋如下圖，車流如箭頭所示，橋上不允許兩車交會，但允許同方向多輛車依次通行(即橋上可以有多個同方向的車)，請用 P、V 操作實作交通管理以防止橋上堵塞，

● 題目分析 —— 其實和上面一道題類似，可以這么理解
??[1] “有一車向左方向駛去” → “A 組某人讀檔案 F”，
??[2] “有一車向右方向駛去” → “B 組某人讀檔案 F”，
??[3] “橋上可以有多個同方向的車” → “同組的人可以同時讀檔案 F”，
??[4] “橋上不允許兩車交會” → “非同組的人不可以同時讀檔案 F”

● 分析清楚后，問題便迎刃而解，代碼如下：

/* 基于 C 語言寫的偽代碼 */
semaphore c1 = 0, c2 = 0;	// c1、c2 分別是 左方向L、右方向R 組的計數器
semaphore S1 = 1, S2 = 1;	// S1、S2 分別是計數器 c1、c2 的互斥信號量
semaphore mutex = 1;		// mutex 是 左方向L、右方向R 兩組間的互斥信號量
while(true)
{
	"左方向開車組的行程 Li():"		// i = 1, 2, 3, ..., a
	while(true)
	{
		P(S1);
        if( c1 == 0 )
        	P(mutex);
        c1 = c1 + 1;
        V(S1);
        Li(以從左到右的方向駛去);
        P(S1);
        c1 = c1 - 1;
        if( c1 == 0 )
			V(mutex);
        V(S1);		
	}
	
	"右方向開車組的行程 Rj():"	// j = 1, 2, 3, ..., b
	while(true)
	{
		P(S2);
        if( c2 == 0 )
        	P(mutex);
        c2 = c2 + 1;
        V(S2);
        Li(以從右到左的方向駛去);
        P(S2);
        c2 = c2 - 1;
        if( c2 == 0 )
			V(mutex);
        V(S2);	
	}
}

---

3、???????? —— 驅動調度技術

【這里有一道綜合的 10分大題】
【4種調度演算法、讀取步驟、磁盤結構、特點】

● “4種調度演算法” 的重點內容和例題都在： 【作業系統學習筆記?】——設備管理(上) [直接查詢、中斷方式、DMA方式、緩沖技術、驅動調度技術與演算法].
【主要看 “五、驅動調度技術”，“讀取步驟、磁盤結構” 都在里面 】

◆ 補充說明：這里的大題可能很綜合，熟悉4種調度演算法的同時，務必要了解清楚 “磁盤的物理結構”、“磁盤的訪問時間”，

● 重點標注一下上面 “灰色模塊” 里的內容：

① 4種調度演算法的特點：

專案	含義	特點
先來先服務演算法（FCFS）	根據行程請求訪問磁盤的先后次序進行調度	此演算法的優點是公平、簡單，且每個行程的請求都能依次得到處理，不會出現某一行程的請求長期得不到滿足的情況，但會致使平均尋道時間長，
最短尋道時間優先（SSTF）	總是先執行查找時間最短的那個磁盤請求，	較 “先來先服務” 演算法有較好的性能，但是本演算法存在 “饑餓” 現象，隨著源源不斷靠近當前磁頭位置讀寫請求的到來，使早來的但距離當前磁頭位置遠的讀寫請求服務被無限期推遲，
掃描演算法（SCAN）	每次總是選擇沿臂的移動方向最近的那個柱面，如果沿這個方向沒有訪問的請求時，就改變臂的移動方向，這非常類似于電梯的調度規則，	掃描演算法克服了 “饑餓” 這一缺點，掃描演算法偏愛那些最接近里面或靠外的請求，對最近掃描跨過去的區域回應會較慢，
回圈掃描演算法（CSCAN）	移動臂總是從0號柱面至最大號柱面順序掃描，然后，直接回傳0號柱面重復進行，歸途中不再服務，構成了一個回圈，這就減少了處理新來請求的最大延遲，	這減少了處理新來請求的最大延遲，

---

4、???????? —— 處理器調度 + 作業的管理和調度

【這里有一個兩級調度的大題，比如說上課寫的那種，10分大題】

● “4種調度演算法” 的重點內容和樣例都在： 【作業系統學習筆記?】——設備管理(上) [直接查詢、中斷方式、DMA方式、緩沖技術、驅動調度技術與演算法].
【先看看下面的 “補充說明” ，再主要看 “四、單道環境下的調度” 和 “五、多道環境下的調度” 】

◆ 補充說明：“四、單道環境下的調度” 里面的例題是 “一級調度”，而 “五、多道環境下的調度” 的例題是 “兩級調度”， 【并不是 “多道” 造成的 “兩級” ，而是因為：作業被 CPU 處理時，不僅需要考慮進入記憶體(一級)，還要考慮在記憶體中送進 CPU 的次序(二級)】

● 關于行程調度演算法，小編已用C++實作：《行程調度演算法——C++實作 [FCFS, SJF, HPF, HRN + 開源代碼]》. 【2021/1/3前，更新出來】

---

5、?????? —— 頁面置換演算法

【 一道 10分大題，3種頁面置換演算法要掌握：FIFO、LRU、OPT，并會計算缺頁中斷率】

● “3種頁面置換演算法” 的重點內容都在： 【作業系統?】——存盤管理(下)【分段存盤管理 虛擬存盤管理 段頁式存盤管理方案 頁面置換演算法 OPT FIFO LRU】.
【主要看 “7.3 頁面置換演算法” ，樣例可以看下面這一篇】

● 關于“頁面置換演算法”，小編已用C/C++實作，并都附加了詳細的樣例：《頁面置換演算法——C/C++實作 [ OTP, FIFO, LRU, LFU + 開源代碼 + 詳細決議]》.

---

6、?????? —— 檔案的物理結構與存盤設備

【可能有混合索引的復雜計算，考試難點】
【地址如何計算、映射怎么實作、一次鏈接？二次鏈接？】

● “混合索引” 的重點內容和樣例都在： 【作業系統學習筆記 ? 完結篇】——檔案管理 [ 檔案系統 + 索引檔案的詳細樣例 ].
【主要看 “4.1.3 索引檔案 —— 樣例” 】

● 下面補充三道的例題來練手：【上文 4.1.3 索引檔案 —— 樣例 中的樣例是最難的】

例題①：檔案系統采用多重結構搜索檔案內容，設塊長為 512B，每個塊號占 3B，如果不考慮邏輯塊號在物理塊中所占的位置，分別求二級索引和三級索引時可尋址的檔案最大長度，

解：
因為塊長為512B，且每個塊號占3B，則一個物理塊可放：512 / 3 ≈ 170.67，向下取整即為 170個(物理塊)地址，所以：
一級索引時可尋址的檔案最大長度：170 × 512 = 87040B (約為87KB)
二級索引時可尋址的檔案最大長度：170 × 170 × 512 = 14796800B (約為14.7MB)
三級索引時可尋址的檔案最大長度：170 × 170 × 170 × 512 = 2515456000B (約為2.5GB)

例題②：某系統中磁盤的每個盤塊大小為 1KB，外存分配方法采用中的混合索引結構，其中索引節點中直接地址 6 項，一級索引地址 2 項，二級索引地址 1 項，每個盤塊號占用 4 個位元組，請問該系統中允許的檔案最大長度是多少?

解：
因為，該系統中磁盤的每個盤塊大小為1KB，且每個盤塊號占用4個位元組，
故一個物理塊可放：1KB / 4B ≈ 256個(物理塊)地址，

因為，索引節點中直接地址有6項，一級索引地址2項，二級索引地址1項，
所以該系統中允許的檔案最大長度： 6 × 1 K B + 2 × 256 × 1 K B + 1 × 25 6 2 × 1 K B = 66 , 054 K B ( 約 為 66 M B ) 6×1KB+2×256×1KB+1×256^2×1KB=66,054KB(約為66MB) 6×1KB+2×256×1KB+1×2562×1KB=66,054KB(約為66MB)

例題③：存放在某個磁盤上的檔案系統，采用混合索引分配方式，其 FCB 中共有 13 個地址項，第 0～9 個地址項為直接地址，第 10 個地址項為一次間接地址，第 11 個地址項為二次間接地址，第 12 個地址項為三次間接地址，如果每個盤塊的大小為 4K 位元組，若盤塊號需要用 4 個位元組來描述，請問該系統中允許的檔案最大長度是多少?

解：
因為，每個盤塊的大小為4K位元組，且每個盤塊號需要用4個位元組，
所以，一個物理塊可放：4KB / 4B ≈ 1024個(物理塊)地址，
因為，索引節點中直接地址有10項、一級索引地址1項、二級索引地址1項、二級索引地址1項，
所以該系統中允許的檔案最大長度： ( 10 + 1 × 1024 + 1 × 102 4 2 + 1 × 102 4 3 ) × 4 K B = 4 , 299 , 165 , 736 K B ( 約 為 4.3 T B ) (10 + 1×1024+1 × 1024^2 + 1× 1024^3)× 4KB=4,299,165,736KB(約為4.3TB) (10+1×1024+1×10242+1×10243)×4KB=4,299,165,736KB(約為4.3TB)

---

7、?????? —— 頁式存盤管理

【基本分頁是面向系統的，也會產生碎片】
【頁式地址轉換：頁表項、頁內位移位、邏輯地址轉換為物理地址(填空選擇)】

● “頁式存盤管理” 的重點內容和樣例都在： 【作業系統?】——存盤管理(上)【磁區存盤管理 分頁存盤管理+詳細樣例】.
【主要看 “三、頁式存盤管理（也稱分頁存盤管理）” 】

◆ 補充說明：上文的 “三、頁式存盤管理（也稱分頁存盤管理）” 中的四道例題務必要掌握，

● 重點標注一下上面 “灰色模塊” 里的內容：

① 分頁與分段的主要區別：
??[1] 段是資訊的邏輯單位，它是根據用戶的需要劃分的，因此段對用戶是可見的，而頁是資訊的物理單位，是為了管理主存的方便而劃分的，對用戶是不可見的(透明的)，

??[2] 頁的大小固定不變，由系統決定，而段的大小是不固定的，它由其完成的功能決定，

??[3] 段式向用戶提供的是二維地址空間，而頁式向用戶提供的是一維地址空間，其頁號和頁內偏移是機器硬體的功能，

??[4] 由于段是資訊的邏輯單位，因此便于存貯保護和資訊的共享，而頁的保護和共享受到限制，

② 分頁存盤的優點和缺點：【分頁存盤是由 “固定磁區存盤管理方案” 演化而來的】
??● 優點：解決了碎片問題、便于管理，
??● 缺點：不易實作共享、不便于動態連接，

③ 分段存盤的優點和缺點：【分頁存盤是由 “可變磁區存盤管理方案” 演化而來的，】
??● 優點：便于動態申請記憶體、段表長度較短、便于共享、便于動態鏈接，
??● 缺點：產生碎片、不易擴展，

? 這里再補充一道較難一點的例題（網易筆試題） —— 有用戶態行程 A，其虛擬記憶體頁為 1KB，A 占用了 64 頁，記憶體大寫為 128KB，A 行程將記憶體的頁面和物理記憶體塊的編號對應關系如下：

頁面編號	物理記憶體塊編號
0	4
1	9
2	5
3	8

請根據以上資訊回答如下問題，并給出計算程序︰

1. 虛擬地址為 015D 對應的物理地址是多少?
2. 物理地址為 113C 對應的虛擬地址為多少?
3. 行程 A 有一作業長度為 8 頁，試圖訪問虛擬地址 2A3D 并保存整型 1 到該地址對應的物理地址空間，之后又嘗試從該地址讀取保存的資料，請問 A 行程這兩次記憶體訪問程序能否正常執行? 并解釋原因，

解：
（1）對于虛擬地址(即邏輯地址) 015 D = 1 × 1 6 2 + 5 × 16 + 13 = 349 015D = 1×16^2+5×16+13=349 015D=1×162+5×16+13=349 【這一步操作是將 16進制 → 10進制】
??故頁號 = int ( 349 / 1024 ) = 0，頁內位移 = 349 mod 1024 = 349，【1024的來頭：因為題目告訴了其虛擬記憶體頁為 1KB = 1024B】
??查頁表第 0 頁在第 4 塊，所以物理地址為 1024 × 4＋349＝4445
??所以，虛擬地址為 015D 對應的物理地址是 115D，【和題目一樣，最終也→ 16進制】

（2）對于物理地址 113 C = 1 × 1 6 3 + 1 × 1 6 2 + 3 × 16 + 12 = 4412 113C = 1×16^3+1×16^2+3×16+12=4412 113C=1×163+1×162+3×16+12=4412 【這一步操作也是將 16進制 → 10進制】
??故物理記憶體塊號 = int ( 4412 /1024 ) = 4，頁內位移 = 4412 mod 1024 = 316，
??查頁表發現，第 4 塊對應 第 0 頁，所以物理地址為 1024 × 0＋316＝316，
??所以，物理地址為 113C 對應的虛擬地址為 013C，【和題目一樣，最終也→ 16進制】

（3）對于虛擬地址(即邏輯地址) 2 A 3 D = 2 × 1 6 3 + 10 × 1 6 2 + 3 × 16 + 13 = 10813 2A3D = 2×16^3+10×16^2+3×16+13=10813 2A3D=2×163+10×162+3×16+13=10813
??故頁號 = int (10813 / 1024 ) = 10，頁內位移 = 349 mod 1024 = 573，
??因該頁號超過頁表長度，即 10 > 4，故該虛擬地址非法， 故 A 行程這兩次記憶體訪問程序不能正常執行，

◆ 補充說明：如果忘了16進制是怎么 → 10進制的話，可以參考這篇，鏈接: 【計算機與UNIX匯編原理①】——計算機基礎【原碼 補碼 反碼 移碼 BCD碼 計算機系統的基本組成等】. 的 “（3）十進制數→二進制數”（原理類似），

---

8、???? —— 行程及其實作

【三態模型的概念、轉換流程，概念簡答題】
【什么是行程控制塊(PCB)，描述了哪些資訊？】

● “行程及其實作” 的重點概念和內容在： 【作業系統③】——行程及其實作【運行態 就緒態 等待態等 PCB 行程控制塊 行程要素】.
【主要看 “四、行程的狀態和轉換” 和 “五、行程控制塊(非常重要的一小節)” 】

◆ 注：這種一般是會考概念，復習考點都在上面的“四、行程的狀態和轉換” 和 “五、行程控制塊(非常重要的一小節)” 里了，

● 重點標注一下上面 “灰色模塊” 里的內容：

① 最基本的三種行程狀態的概念是什么？
答：
[1] 運行態(Runing)：行程當前占有CPU，并在在CPU上運行，
[2] 就緒態(Ready)：<1> 一個行程已經具備運行條件，但沒有分配CPU，暫時不能運行，<2> 當調度給該行程CPU時，立即可以運行，
[3] 等待態(Blocked)：<1> 有時也叫作 “阻塞態、封鎖態、睡眠態” ，<2> 當前行程因等待某事件的發生而暫時不能運行的狀態，<3> 即使這時CPU空閑，該行程也不能運行，

② 三態模型的轉換流程是什么？
答：如下圖所示，

[1] 就緒 一一> 運行：在調度程式時，一旦調度到這個行程的時候，就發生這件事(這個行程就由就緒態切換到了運行態)，
[2] 運行 一一> 就緒：運行行程用完了CPU分給它的時間片時發生，
[3] 運行 一一> 等待：發生情況有： ① 作業系統尚未完成某項服務，② 這個行程對某項資源的訪問不能得到滿足，③ 初始化I/O且須等待結果，④ 等待某一行程提供輸入，
[4] 等待 一一> 運行：等待的事件得到滿足時發生，

③ 什么是行程控制塊(PCB)的概念是什么？
答：行程控制塊 (Process Control Block，PCB) 是系統為了管理行程而設定的專門的資料結構，用來記錄行程的外部特征，描述行程的變化程序，

④ 行程控制塊(PCB)描述了哪些資訊？
答：
??[1] 行程識別符號 (process ID)：具有唯一性，通常是一串整數，
??[2] 行程名：通常是執行的檔案名，不唯一，
??[3] 用戶識別符號 (user ID)：記錄下這個行程是由哪一個用戶所創建的，
??[4] 行程的組關系：它有多種表現形式，比如說記錄同一個用戶創建的行程可以算成一組，記錄的就是這樣一組關系，

◆ 補充說明：如需更生動、可視化地了解這些，可以看這篇文章的 《【作業系統③】——行程及其實作》的 “五、行程控制塊(非常重要的一小節)”，

---

9、???? —— 可變磁區

【4種磁區演算法，要能用語言描述、優缺點(背)，】

● “行程及其實作” 的重點概念和內容在： 【作業系統?】——存盤管理(上)【磁區存盤管理 分頁存盤管理+詳細樣例】.
【主要看 “2.2 可變磁區”和“2.3 分配演算法（也稱磁區演算法）”】

● 弄一張表來對比著看吧：【特點 = 優點 + 缺點】

專案	演算法原理語言描述	優點	缺點
首次適應演算法（first fit）	優先利用記憶體中低址部分的空閑磁區，從而保留了高址部分的大空閑區，這為以后到達的大作業分配大的記憶體空間創造了條件，	實作簡單，且低址部分不斷被劃分，會留下許多難以利用的，很小的空閑磁區，稱為碎片，而每次查找又都是從低址部分開始的，這無疑又會增加查找可用空閑磁區時的開銷，	可能將低地址處大的空閑區分割成許多小的空閑區，形成許多不連續的“碎片”，(而每次查找又都是從低址部分開始的，這會導致)碎片長度可能不能滿足作業要求，降低了記憶體利用率，
回圈首次適應演算法（next fit）	在首次適應演算法的基礎上進行了點改進，該演算法不再每次都從開始位置找查，而是在上一次找到的位置接著往下找，	使存盤空間的利用更加均衡，不致使小的空閑區集中在存盤區的一端，	這會導致系統缺乏大的空閑區，
死鎖的檢測與解除	空閑磁區按容量遞增次序連接接，每次分配記憶體時順序查找空閑磁區表，找到大小能夠滿足要求的第一個空閑磁區，	(每次分配給檔案都)盡可能地選擇了最適合的磁區空間，	但也因此產生大量的不能被使用的很小的空閑區，因此這種方法會產生很多的外部碎片，所以該演算法分配效果不一定是最佳的，
最壞適應演算法（worst fit）	和最佳適應演算法類似，只不是將空閑磁區按容量遞減的次序連接，每次分配記憶體時順序查找空閑磁區表，找到大小能夠滿足要求的第一個空閑磁區，	與最佳適應演算法的缺點相比，該演算法優先使用最大的連續空閑區，這樣分配后的空閑區就不會太小，更方便使用，	當有大作業來臨時，其對存盤空間的申請往往得不到滿足，

---

10、???? —— 緩沖技術

【為什么要引入緩沖技術？】
【有時間看看那 4 個緩沖】

● “緩沖技術” 的重點概念和內容在： 【作業系統學習筆記?】——設備管理(上) [直接查詢、中斷方式、DMA方式、緩沖技術、驅動調度技術與演算法].
【主要看 “四、緩沖技術”】

● 重點標注一下上面 “灰色模塊” 里的內容：

為什么要參考（/采用）緩沖技術？
答：
[1] 為了改善 CPU 與外設之間速度不匹配的矛盾，
[2] 為了減少 I/O 對 CPU 的中斷次數和放寬對 CPU 中斷回應時間的要求，
[3] 為了提高 CPU 和 I/O 設備的并行性，

---

11、?? —— 多道程式系統

【設計的概念 → 目的是什么？概念簡答題】

● “多道程式系統階段” 的重點概念和內容在： 【作業系統②】——作業系統的發展與分類、作業系統的結構設計【分時作業系統 整體式 層次式】.
【主要看 “2、批處理階段” 】

● 重點標注一下上面 “灰色模塊” 里的內容：

① 多道程式系統設計的概念是什么？
答：多道程式系統設計是指允許多個程式（作業）同時進入一個計算機系統的記憶體儲器并啟動進行交替計算的方法，

② 多道程式系統設計的目的是什么？
答：為了改善 CPU 與外設之間速度不匹配的矛盾，減少 I/O 對 CPU 的中斷次數，提高 CPU 和 I/O 設備的并行性，在作業系統中普遍采用了緩沖技術，

---

12、?? —— 并發行程

【引入的目的，并發(看樣例)可能會導致什么錯誤出現？】

● “并發行程” 的重點概念和內容在： 【作業系統⑥】——行程聯系與臨界區管理【同步與互斥 Dekker演算法 TS指令 SWAP指令】.
【主要看 “2、并發環境與并發行程” 和 “3、與時間有關的不確定性” → 與時間有關的錯誤】

● 重點標注一下上面 “灰色模塊” 里的內容：

① 并發行程引入的目的是什么？
答：并發行程能共享計算機資源，這能使資源利用率大幅提升，CPU和其他資源更能保持“忙碌”狀態，系統吞吐量增大，

② 并發可能會導致什么錯誤出現？
答：與時間有關的錯誤，由于共享資源的原因，加上行程并發執行的隨機性，一個行程對另一個行程的影響是不可預測的，這時就可能導致并發行程交替使用共享資源時出現 “與時間有關的錯誤”，

---

13、?? —— 重定位

【動態重定位的優缺點，】

● “動態重定位” 的重點概念和內容在： 【作業系統?】——存盤管理(上)【磁區存盤管理 分頁存盤管理+詳細樣例】.
【主要看 “1.4 地址重定位”】

● 重點標注一下上面 “灰色模塊” 里的內容：

① 靜態重定位和動態重定位分別的優缺點是什么？

專案	描述	優點	缺點
靜態重定位	在程式裝入記憶體后，且在運行前，一次將需要轉換的邏輯地址轉換為物理地址的操作，	無須增加硬體地址轉換機構，便于實作程式的靜態連接，	[1] 程式的存盤空間只能是連續的一篇區域，而且在重定位之后就不能移動，這不利于記憶體空間的有效使用， [2] 各個用戶行程很難共享記憶體中的同一程式副本，
動態重定位	在程式運行期間，每次訪問記憶體之前都要進行的操作，它是靠硬體地址變換機制實作的，	[1] 程式占用的記憶體空間動態可變，也不必連續存放在一起， [2] 比較容易實作幾個行程對同一程式副本的共享使用，	需要附加的硬體支持，增加了機器成本，而且實作存盤管理的軟體演算法比較復雜，

---

14、?? —— 段氏存盤管理

【了解分段和分頁在概念上的區別 → 更少的碎片，】

● 這個考點和前面的 “7、?????? —— 頁式存盤管理” 是相對而言的，

● “段氏存盤管理” 的重點概念和內容在： 【作業系統?】——存盤管理(下)【分段存盤管理 虛擬存盤管理 段頁式存盤管理方案 頁面置換演算法 OPT FIFO LRU】.
【主要看 “四、分頁和分段存盤的比較”】

● 重點標注一下上面 “灰色模塊” 里的內容：

① 分頁與分段的主要區別：
??[1] 段是資訊的邏輯單位，它是根據用戶的需要劃分的，因此段對用戶是可見的，而頁是資訊的物理單位，是為了管理主存的方便而劃分的，對用戶是不可見的(透明的)，

??[2] 頁的大小固定不變，由系統決定，而段的大小是不固定的，它由其完成的功能決定，

??[3] 段式向用戶提供的是二維地址空間，而頁式向用戶提供的是一維地址空間，其頁號和頁內偏移是機器硬體的功能，

??[4] 由于段是資訊的邏輯單位，因此便于存貯保護和資訊的共享，而頁的保護和共享受到限制，

② 分頁存盤的優點和缺點：【分頁存盤是由 “固定磁區存盤管理方案” 演化而來的】
??● 優點：解決了碎片問題、便于管理，
??● 缺點：不易實作共享、不便于動態連接，

③ 分段存盤的優點和缺點：【分頁存盤是由 “可變磁區存盤管理方案” 演化而來的，】
??● 優點：便于動態申請記憶體、段表長度較短、便于共享、便于動態鏈接，
??● 缺點：產生碎片、不易擴展，

---

15、?? —— I/O 控制方式

【4種方式出現的時間段、發展的驅動力是什么？概念簡答題】

● “I/O 控制方式” 的重點概念和內容在： 【作業系統學習筆記?】——設備管理(上) [直接查詢、中斷方式、DMA方式、緩沖技術、驅動調度技術與演算法].
【主要看 “三、I/O 控制方式”】

● 重點標注一下上面 “灰色模塊” 里的內容：

① I/O 控制方式的 4 種方式出現的時間段：
答：程式直接查詢控制方式、中斷方式、DMA方式、通道方式，

② I/O 控制方式發展的驅動力是什么？：
答：盡可能減少主機對外設的干預，即盡可能把主機從繁雜的 I/O 控制中解脫出來，以便有更多時間進行其他處理，

---

16、?? —— 設備獨立性

【考簡答題，概念，如何實作？概念簡答題】

● “設備獨立性” 的重點概念和內容在： 【作業系統學習筆記?】——設備管理(下) [ 設備分配、虛擬設備——SPOOLing ].
【主要看 “2.4 設備的獨立性”】

● 重點標注一下上面 “灰色模塊” 里的內容：

① 設備獨立性的概念是什么？
答：用戶行程獨立于具體使用的物理設備，（也就是說，行程只需用邏輯設備名稱請求使用某類設備就可以了，當系統中有多臺該類設備時，系統可將其中任一臺分配給請求行程，而無需僅局限于某一臺設備，）

② 設備獨立性如何實作的？
答：系統通過設定一張邏輯設備表 LUT，將應用程式(或用戶程式)中所使用的邏輯設備名稱映射為物理設備名(來實作設備的獨立性)，

---

17、?? —— 檔案存盤空間的管理

【引入的原因、功能，了解一下位示圖法，填空選擇】

● “檔案存盤空間的管理” 的重點概念和內容在： 【作業系統學習筆記 ? 完結篇】——檔案管理 [ 檔案系統 + 索引檔案的詳細樣例 ].
【主要看 “五、檔案存盤空間的管理”，位示圖法在也在里面】

● 幾種常用的檔案存盤空間的管理方法：空閑區表法、空閑鏈表法、位示圖法，

● 重點標注一下上面 “灰色模塊” 里的內容：

① 檔案存盤空間的管理引入的原因？
答：為了為新創建的檔案合理地分配存盤空間，

② 檔案存盤空間的管理的功能是什么？
答：它采取連續分配方式或離散分配方式來進行對檔案存盤空間的管理，前者具有較高的檔案分配速度，但可能產生較多的外存碎片；后者能有效地利用外存空間，但分配速度慢，

? 最后補充一道綜合性的例題 —— 假設一個磁盤有 100 個柱面，每個柱面有 10 個磁道，每個盤面被分為 8 個扇區，柱面、磁頭和扇區的編號均從 0 開始，現用字長為 16 位的位示圖來管理磁盤空間，位示圖的字號、位號從 0 開始編號，
（1）每個柱面有多少個存盤塊？該磁盤組共有多少個存盤塊？
（2）求位示圖中字號為 7、位號為 3 的二進制位對應塊的物理塊號？
（3）給出該物理塊的物理地址（柱面號、磁頭號、扇區號）?
（4）洗掉檔案歸還第 21 柱面第 7 磁道第 3 扇區，對應的物理塊號是多少？位示圖中應修改第幾字第幾位？

解：
（1）因為每個柱面有 10 個磁道，每個盤面被分為 8 個扇區，故每個柱面有 10 × 8 = 80 個存盤塊，
??又因為磁盤有 100 個柱面，故磁盤共有 80 × 100 = 8000 個存盤塊，

（2）位示圖中字號為 7、位號為 3 的二進制位對應塊的塊號為 7 × 16 + 3 = 115，

（3）計算柱面號：115 / 80 = 1，計算柱面余數：115 mod 80 = 35，【注：“mod” 是求余】
??計算磁道號：35 / 8 = 4，計算扇區號：35 mod 8 = 3，
??故該物理塊的柱面號是 1，磁頭號是 4，扇區號是 3，

（4） 塊號 =（21柱面第7磁道第3扇區）21 × 80 + 7 × 8 + 3 = 1739
??位示圖中對應的字號： i = 1739 / 16 = 108 i=1739/16=108 i=1739/16=108
??位示圖中對應的位號： j = 1739 ? m o d ? 16 = 11 j=1739 \, mod \,16=11 j=1739mod16=11
??所以，對應的物理塊號是 1739，位示圖中應修改第 108 字第 11 位，

好了，終于完工啦！ 🚧，

---

五、參考附錄

[1] 《作業系統A》
上課用的慕課
鏈接: https://www.icourse163.org/course/NJUPT-1003219004?from=searchPage.

[2] 《作業系統教程——人民郵電出版社》
上課用的教材

[3] 其他題源參考網站：多級索引例題、分頁式存盤管理及地址轉換例題、位示圖例題

---

本想簡單寫一寫的…列個目錄什么的…
但創作良心過不去，就寫了這么多…
?? ??

新年第一篇????
???2022/1/1?????