第二章 作業系統的結構和硬體

2.4 中斷及其處理

2.4.1 中斷概念及其型別

中斷：某個事件（電源掉電、定點加法溢位、I/O傳輸結束等）發生時，系統終止現行程式的運行，引出處理該事件的程式對事件進行處理，處理完畢后回傳斷點繼續執行的程序
中斷型別：
按中斷功能分：

1. 輸入輸出中斷
2. 外中斷
3. 機器故障中斷
4. 程式性中斷
5. 訪管中斷

按中斷方式分：

1. 強迫性中斷：輸入輸出中斷、外中斷、機器故障中斷、程式性中斷
2. 自愿中斷：訪管中斷

按中斷來源分：

1. 中斷：處理機外部事件引起的中斷，例：時鐘、磁盤、終端
2. 俘獲：處理機內部事件引起的中斷，例：非法指令、地址越界、浮點溢位、tmp指令，

2.4.2 向量中斷和探詢中斷

向量中斷：當中斷發生時，由中斷源自己引導處理機進入中斷服務程式的中斷程序

中斷向量：該型別中斷的中斷服務例行程式的入口地址和處理器狀態字

兩類不同的中斷機制：向量中斷、探尋中斷

2.4.3 中斷進入

現場：在中斷的那一時刻能確保程式繼續運行的有關資訊

保護現場：當中斷發生時，必須立即把現場資訊保存在主存里，這一作業程序稱為保護現場

恢復現場：在程式重新運行之前，把保留的該程式現場資訊從主存中送至指令計數器、通用暫存器或一些特殊暫存器中，這些作業稱為恢復現場

中斷回應：中央處理機發現已有中斷請求時，中斷現行程式執行，并引出中斷處理程式的程序

• 中斷回應程序：
  ①保留程式斷點及處理機有關資訊
  ②自動轉入相應的中斷處理程式執行
• 中斷回應硬體支持：指令計數器、處理器狀態暫存器、中斷向量表、系統堆疊

2.4.4 軟體中斷處理程序

①保留被中斷程式的現場
②進入相應的中斷服務流程
③恢復被中斷程式的現場

第四章 行程及行程管理

4.2 行程概念

4.2.1 行程定義

行程：一個程式在給定活動空間和初始環境下，在一個處理機上執行的程序（運行→暫停→運行）

行程和程式的區別：
① 程式是靜態的概念，行程是動態的概念
②行程是一個能獨立運行的單位，能與其他行程并行的活動
③行程是競爭系統資源的基本單位
④關聯：行程一定包含一個程式，一個程式可以對應多個行程

4.2.2 行程的狀態及變遷

多任務系統中行程的基本狀態：
①就緒狀態（ready）：行程已獲得除CPU之外的運行所必需的資源，一旦得到CPU的控制權，立即就可以運行
②運行狀態（running）：該行程已獲得運行所必須的資源，它的程式正在處理機上運行
③等待狀態（wait）：行程正等待著某一事件的發生而暫時停止執行，若此時CPU給它控制權也無法執行

行程狀態的變遷（紅線可以無，實際狀態變遷為黑線標注的箭頭）

4.2.2 行程控制塊

行程控制塊：描述行程與其它行程、系統資源的關系以及行程在各個不同時期所處狀態的資料結構，稱為行程控制塊PCB

行程的組成：程式與資料、PCB(行程控制塊)

行程控制塊的主要內容：
①行程識別符號：行程符號名或內部id號
②行程當前狀態：行程處于何種狀態
③當前佇列指標：該項登記了處于同一狀態的下一個行程的PCB地址
④行程優先級：反映了行程要求CPU的緊迫程度
⑤CPU現場保護區：當行程由于某種原因釋放處理機時，CPU現場資訊被保存在PCB的該區域
⑥通信資訊：行程間進行通信時所記錄的有關資訊
⑦家族聯系：本行程與家族的聯系
⑧占用資源清單

行程控制塊的組織——行程佇列結構

4.3 行程控制

4.3.1 行程控制的概念

行程控制的職責：對系統中的行程實施有效的管理，負責行程狀態的改變

行程狀態的變化：

常用的行程控制原語：創建原語、撤銷原語、等待原語、喚醒原語

4.3.2 行程的創建與撤銷

1. 行程創建：create{name,priority}
   name：被創建行程的識別符號
   priority：優先級
   
2. 行程撤銷：kill（或exit）
   

4.3.2 行程等待與喚醒

1. 行程等待：susp(chan)
   chan：行程等待的原因/事件
   
2. 行程喚醒：wakeup(chan)
   chan：行程等待的原因/事件
   

4.4 行程之間的約束關系

4.4.1 行程競爭與合作

行程之間的相互制約關系：
①由于競爭系統資源而引起的間接相互制約關系（競爭系統資源）——由作業系統的資源分配功能來解決
②由于行程之間存在共享資料而引起的直接相互制約關系（行程協作），包括資訊共享和并行處理——由作業系統提供的同步機構來解決

4.4.2 行程互斥的概念

互斥：在作業系統中，當某一行程正在訪問某一存盤區域時，就不允許其它行程來讀出或者修改該存盤區的內容，否則，就會發生后果無法估計的錯誤，行程間的這種相互制約關系稱為互斥，
（1）臨界資源：一次僅允許一個行程使用的資源
注意：

• 例1：行程共享列印機
• 例2：行程共享公共變數

硬體：輸入機、列印機、磁帶機
軟體：公用變數、資料、表格、佇列
（2）臨界區：行程中對公共變數（或存盤區）進行審查與修改的程式段，稱為相對于該公共變數的臨界區

4.4.2 行程同步的概念

行程同步：并發行程在一些關鍵點上可能需要互相等待與互通訊息，這種相互制約的等待與互通訊息稱為行程同步

同步的例子：
（1）病員就診的同步關系
（2）計算行程與列印行程共享單緩沖區的同步問題

4.5 同步機構

4.5.1 鎖和上鎖、開鎖操作

上鎖原語：

演算法 lock
輸入：鎖變數w
輸出：無
{
	test:
	if(w==1)
		goto test;
		else w=1;
}

開鎖原語：

演算法：unlock
輸入：鎖變數w
{
	w=0;
}

改進后的上鎖原語：

演算法 lock
輸入：鎖變數w
輸出：無
{
	while(w==1){
		保護現行行程的CPU現場;
		將現行行程的PCB插入w的等待佇列;
		置該行程為"等待"狀態
		轉行程調度
	}
	w=1;
}

改進后的開鎖原語：

演算法 lock
輸入：鎖變數w
輸出：無
{
	if(w等待佇列不空){
		移出等待佇列首元素;
		將該行程的PCB插入就緒佇列;
		置該行程為"就緒"狀態;
	}
	w=0;
}

4.5.2 信號燈和P、V操作

1.信號燈：一個確定的二元組(s,q)，s:一個非負初值的整型變數，q:一個初始狀態為空的佇列

一個信號燈的建立必須經過說明，即說明信號燈s的意義和初值（初值不能為負值），每個信號燈都有一個佇列，在建立信號燈時，佇列為空，當信號燈的值≥0時，表示綠燈，行程可以繼續；當信號燈的值＜0時，表示紅燈，行程被阻，s的值可以改變以反映資源或并發行程狀態的改變，信號燈的值只能通過P、V操作原語改變，在用戶給出信號燈初值后，信號燈在行程同步程序中的值不能被用戶程式直接修改，信號燈的取值范圍是負整數值、零、正整數值

P、V操作：
（1）P操作
動作：
①s值減1
②若相減結果≥0，則行程繼續執行
③若相減結果＜0，該行程被封鎖，并把它插入到信號燈的等待佇列中，然后轉行程調度程式

演算法 p
輸入：變數s
輸出：無
{
	s--;
	if(s<0){
		保留呼叫行程CPU現場;
		將該行程的PCB插入s的等待佇列;
		置該行程為"等待"狀態;
		轉行程調度;
	}
}

（2）V操作
動作：
①s值加1
②若相加結果＞0，則行程繼續執行
③若相加結果≤0，從信號燈等待佇列移出一個行程，解除它的等待狀態然后回傳本行程繼續執行

演算法 v
輸入：變數s
輸出：無
{
	s++;
	if(s<=0){
		移出等待佇列首元素;
		將該行程的PCB插入就緒佇列;
		置該行程為"就緒"狀態
	}
}

4.6 行程互斥與同步的實作

4.6.1 上鎖原語和開鎖原語實作行程互斥

在用戶程式中，訪問臨界資源的前后必須增加上鎖原語和開鎖原語，任何欲進入臨界區的行程，必須先執行上鎖原語，若上鎖原語順利進行，則行程可以進入臨界區，在完成對臨界資源的訪問后再執行開鎖原語，以釋放臨界資源，

4.6.2 信號燈實作行程互斥

對于兩個并發行程，互斥信號燈的值僅取1、0、-1三個值
若mutex=1，表示沒有行程進入臨界區
若mutex=0，則表示有一個行程進入臨界區
若mutex=-1，表示一個行程進入臨界區，另一個行程等待進入

4.6.3 行程同步的實作

行程流圖：圖的連接描述了行程間開始和結束的次序的次序約束

順序：

并行：

共享緩沖區的合作行程同步：

（1）分析同步關系：
①當buf內有新資料時，IOP行程才能列印；當buf內有空位置時，CP行程才能把下一個計算結果資料送入buf
②當CP行程把計算結果送入buf時，要給IOP發訊息，當IOP行程將buf中的資料取出后，要給CP發訊息

（2）設定兩個信號燈S_a和S_b，S_a表示緩沖區是否有可列印的結果，賦予初值為0（原因：列印行程在執行前先執行P(S_a)操作，若P操作后S_a結果小于0，則無可列印的結果，行程被阻；反之，若S_a為0，則證明有可列印的結果，則繼續執行列印操作）；S_b表示緩沖區有無空位置存放新的資訊，賦予初值為1（原因：當計算出來的結果要放入緩沖區之前，需要做一步P(S_b)操作判斷緩沖區是否有空位置，若P操作后的S_b為0，則可以繼續，反之，若S_b為負數，則行程被阻，等待列印行程從緩沖區取走資訊后將它喚醒），列印行程將緩沖區資料取走后，便對S_b進行V(S_b)操作，告知緩沖區資訊已被取走，可以存放新的資訊，

4.6.4 生產者——消費者問題

生產者：當有界緩沖區無空位置，要等待；向有界緩沖區放入物品后，要發訊息
消費者：當有界緩沖區無物品，要等待；從有界緩沖區取出物品，要發訊息

生產者——消費者問題解法：
（1）信號燈設定：

• S_b：表示慷訓沖區的數目，初值=n
  S_a：表示滿緩沖區（即資訊）的數目，初值=0（兩個同步信號燈）
• mutex：表示有界緩沖區是否被占用，初值=1（一個互斥信號燈）
  （2）同步描述：
  

4.8 執行緒概念及特點

4.8.1 執行緒的概念

執行緒可以用一個現場（context）來表示，現場由程式計數器、暫存器組和所要求的狀態字符組成

執行緒可以這樣描述：
①執行緒是行程中的一條執行路徑
②它有自己私用的堆疊和處理機執行環境
③它共享父行程的主存
④它是單個行程所創建的許多個同時存在的執行緒中的一個

行程與執行緒區別：行程是任務調度單位，也是系統資源的分配單位；而執行緒是行程中的一條執行路徑，當系統支持多執行緒處理時，執行緒是任務調度的單位，但不是系統資源的分配單位

4.8.1 執行緒的特點與狀態

執行緒的狀態變遷：

第五章 資源分配與調度

5.1 資源管理概述

5.1.1&&5.1.2

作業系統對資源區分兩種不同的概念
①物理資源——系統中那些物理、可實際使用的資源
②虛擬資源——邏輯資源，是經過作業系統改造的、用戶看到的，使用方便的虛資源

目的：①方便用戶使用 ②資源可動態分配，提高資源利用率

5.2 資源管理的機制和策略

5.2.1&&5.2.2

資源分配策略：在眾多個請求者中選一個滿足條件的請求者原則

資源分配策略具體如何體現？
體現在資源請求佇列的排序原則上
（1）先請求先服務策略
①排序原則——按請求的先后次序排序：每一個新產生的請求均排在資源請求佇列的隊尾，
②資源可用時的處理：資源可用時，取資源請求佇列隊首元素，將該資源分配給請求者，
（2）優先調度策略
①排序原則——按請求的優先級高低排序

• 對每一個行程制定一個優先級
• 按優先級的高低排序——每一個新產生的請求按對應行程的優先級高低插入到佇列的相應位置，

（3）針對設備特性的調度策略
調度目標：當有大量的I/O請求時，降低完成這些I/O服務的總時間

如何確定移動臂磁盤組中磁盤塊的物理位置

5.3 死鎖

5.3.1 死鎖的定義與例子

死鎖：兩個或多個并發行程中，如果每個行程持有某種資源而又都等待著別的行程釋放它或它們現在保持著的資源，否則就不能向前推進，此時稱這一組行程為死鎖，

5.3.2 引起死鎖的原因和必要條件

引起死鎖的原因：
①系統資源不足
②行程推進順序非法

產生死鎖的必要條件
①互斥條件——涉及的資源是非共享的，即為臨界資源
②不剝奪條件——行程所獲得的資源在未使用完畢之前，不能被其它行程強行奪走
③部分分配——行程每次申請它所需要的一部分資源，在等待新資源的同時，行程繼續占用已分配到的資源
④環路條件——存在一種行程的回圈鏈，鏈中的每一個行程已獲得的資源同時被鏈中下一個行程所請求

5.3.3 系統模型和死鎖的處理

（1）資源請求矩陣：
在時刻t資源請求矩陣
d(t)=
d₁₁ d₁₂ … d_1m
d₂₁ d₂₂ … d_2m
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
d_n1 d_n2 … d_nm

d_ij表示行程p_i還需要j類資源的數目

（2）資源分配矩陣：
在時刻t資源分配矩陣
a(t)=
a₁₁ a₁₂ … a_1m
a₂₁ a₂₂ … a_2m
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
a_n1 a_n2 … a_nm

a_ij表示行程p_i已占用j類資源的數目

（3）什么情況下系統是安全的
當行程請求某類資源時，行程對該類資源的最大需求量小于當前時刻系統所擁有的該類資源的數目，那么滿足行程的這次請求，系統是安全的

系統的安全狀態描述：按某種順序，并發行程都能達到獲得全部資源而順序完成的序列稱為安全序列，能找到安全序列的狀態為安全狀態，

5.3.4 解決死鎖問題的策略

為了使系統不發生死鎖，必須要破壞產生死鎖的四個必要條件之一

①采用資源靜態分配方法預防死鎖
②采用資源動態分配、有控分配方法來避免死鎖
③當死鎖發生時檢測出死鎖，并設法修復
④忽略死鎖，一旦發生死鎖便重啟系統（這種方法被絕大多數作業系統所采用）

5.3.5 死鎖的預防

死鎖的預防分為靜態預防和動態避免

死鎖的靜態預防就是采用資源預先分配方式，系統在應用程式進入系統前分配它所需要的所有資源，當資源一旦分配給該應用程式后，在其整個運行期間這些資源為它獨占，

5.3.6 死鎖的避免

死鎖的動態避免就是采用資源動態分配的方式
①有序資源分配方法：系統中所有資源都給一個唯一的編號，所有分配請求必須以上升的次序進行，當遵守上升次序的規則時，若資源可用，則予以分配；否則，請求者等待，
②銀行家演算法：申請者事先說明對各類資源的最大需求量，在行程活動期間動態申請某類資源時，由系統審查現有該類資源的數目是否能滿足當前行程的最大需求量，如能滿足就予以分配，否則拒絕，

例：
擁有某類資源10個，現有P、Q、R共享該類資源，申請該類資源的需求量如下，

行程	最大需求量	已占有資源	現申請資源個數
P	8	4	1
Q	4	2	1
R	9	2	1

已占有的資源總數：4+2+2=8個
還剩下的資源數：10-8=2個
計算行程還需要的資源數：
P：8-4=4個
Q：4-2=2個
R：9-2=7個
∵現擁有2個剩余資源數
又∵Q還需要的資源數為2×1=2個（乘的1為現申請的資源個數）
∴只有Q符合條件，分配給Q

5.3.7 死鎖的檢測與忽略

第六章 處理機調度

6.1 處理機的多級調度

（1）批處理系統中的處理機調度
分兩級：作業調度和行程調度

作業調度：又稱為宏觀調度，任務——對存放在輔存設備上的大量作業，以一定的策略進行挑選，分配主存等必要的資源，建立作業對應的行程，使其投入運行，

行程調度：微觀調度，任務——對進入主存的所有行程，確定哪個行程在什么時候獲得處理機，使用多長時間

（2）多任務系統中的處理機調度
多任務系統包括：分時作業系統、個人計算機作業系統

多任務系統中最小活動單位：行程

多任務系統中的行程調度：系統提供行程調度程式，其功能是當處理機空閑時，以某種策略選擇一個就緒行程去運行，并分配處理機時間
（3）多執行緒系統中的處理機調度
處理機的分配單位：執行緒

多執行緒系統中的執行緒調度：系統提供執行緒調度程式，其功能是當處理機空閑時，以某種策略選擇一個就緒執行緒去運行，并分配處理機時間

6.2 作業調度

6.2.1 作業的狀態

作業的狀態：
后備狀態：作業所需的程式、資料、操作說明書已存放在磁盤上，等待調度
執行狀態：作業所需的資訊已進入主存，開始運行
完成狀態：作業計算完成，退出系統

作業狀態的變遷：

6.2.2 作業調度的功能

6.2.3 作業控制塊

作業名——作業的名字
資源要求——容量、外部設備等
資源使用情況——已經占用的主存的地址、大小、 哪臺設備等
作業型別——控制方式、作業型別
作業優先級——占用CPU、占用系統運行的優先級
作業狀態——后備、執行、完成狀態

6.2.4 調度演算法性能的衡量

周轉時間 t_i：一個作業提交給計算機系統到該作業的結果回傳給用戶所需要的時間，說明作業 i 在系統中停留時間的長短
t_i公式：t_i = t_ci - t_si
t_i：作業 i 的周轉時間
t_ci：作業 i 的完成時間
t_si：作業 i 的提交時間

平均周轉時間 t ：（周轉時間 t 時間越短越好）
t = 1 n ∑ i = 1 n t i t=\frac{1}{n} \quad\sum_{i=1}^n t_i\quad t=n1?i=1∑n?ti?

帶權周轉時間 w_i ：一個作業的周轉時間與其運行時間的比值，（說明作業 i 在系統中相對等待時間）
w i = t i t r i w_i=\frac{t_i}{tri} \quad wi?=triti??
w_i ：作業 i 的帶權周轉時間
t_ri ：作業 i 的實際執行時間

平均帶權周轉時間 w ：
w = 1 n ∑ i = 1 n w i w=\frac{1}{n} \quad\sum_{i=1}^n w_i\quad w=n1?i=1∑n?wi?

6.2.5 作業調度演算法

例：

作業	提交時間	執行時間	開始時間	完成時間	周轉時間	帶權周轉時間
1	8.00	2.00	-	-	-	-
2	8.50	0.50	-	-	-	-
3	9.00	0.10	-	-	-	-
4	9.50	0.20	-	-	-	-

（1）先來先服務調度演算法（FCFS）
①策略：按作業來到的先后次序進行調度
②特點：簡單、易實作

解：

作業	提交時間	執行時間	開始時間	完成時間	周轉時間	帶權周轉時間
1	8.00	2.00	8.00	10.00	2.00	1
2	8.50	0.50	10.00	10.50	2.00	4
3	9.00	0.10	10.50	10.60	1.60	16
4	9.50	0.20	10.60	10.80	1.30	6.5

平均周轉時間 t = 1.725
平均帶權周轉時間 w = 6.875

（2）短作業優先調度演算法
①策略：按作業運行時間的長短進行調度
②特點：易實作，效率較高

解：
①8.00時刻作業1來到，正常執行

作業	提交時間	執行時間	開始時間	完成時間	周轉時間	帶權周轉時間
1	8.00	2.00	8.00	10.00	2.00	1
2	8.50	0.50	-	-	-	-
3	9.00	0.10	-	-	-	-
4	9.50	0.20	-	-	-	-

②按執行時間選擇作業3（優先選擇執行時間短的執行）

作業	提交時間	執行時間	開始時間	完成時間	周轉時間	帶權周轉時間
1	8.00	2.00	8.00	10.00	2.00	1
2	8.50	0.50	-	-	-	-
3	9.00	0.10	10.00	10.10	1.10	11
4	9.50	0.20	-	-	-	-

③重復②的程序，因為0.20<0.50，選擇作業4

作業	提交時間	執行時間	開始時間	完成時間	周轉時間	帶權周轉時間
1	8.00	2.00	8.00	10.00	2.00	1
2	8.50	0.50	-	-	-	-
3	9.00	0.10	10.00	10.10	1.10	11
4	9.50	0.20	10.10	10.30	0.80	4

④最后運行作業2

作業	提交時間	執行時間	開始時間	完成時間	周轉時間	帶權周轉時間
1	8.00	2.00	8.00	10.00	2.00	1
2	8.50	0.50	10.30	10.80	2.30	4.6
3	9.00	0.10	10.00	10.10	1.10	11
4	9.50	0.20	10.10	10.30	0.80	4

最后得出，
平均周轉時間 t = 1.55
平均帶權周轉時間 w= 5.15

比較（1）（2）的 t 和 w ，明顯短作業優先調度演算法較先來先服務調度演算法好，但短作業優先調度演算法存在缺陷，即若有一個長作業有可能永遠得不到調度，

第七章 主存管理

7.1 主存管理概述

7.1.1 && 7.1.2

物理地址：計算機主存單元的真實地址
主存空間：物理地址的集合所對應的空間
邏輯地址：用戶的程式地址（指令地址或運算元地址）
程式地址空間：用戶程式所有的邏輯地址集合對應的空間

存盤空間就是系統擁有的主存空間，若主存由m個存盤單元，則存盤單元編號是0~(m-1)，

程式的地址空間由程式的地址結構決定
①程式的一維地址結構：確定線性地址空間中的指令地址或運算元地址只需要一個資訊
②程式的二維地址結構（一個程式由若干個分段組成，每個分段是一個連續的地址區，則程式的地址空間由若干個分段組成）：確定地址空間中的指令地址或運算元地址需要兩個資訊，一個是該資訊所在的分段，另一個是該資訊在段內的偏移量

7.2 主存管理的功能

7.2.1 虛擬存盤器

虛擬存盤器：由作業系統和硬體相配合實作的主存和輔存之間資訊的動態調度，這樣的計算機系統為用戶提供了一個其存盤容量比實際主存大得多的存盤器

實作虛擬存盤器的物質基礎：
①有相當容量的輔存——足以存放應用程式的虛地址空間
②有一定容量的主存——存放進入主存的多行程的資訊
③地址變換機構

7.2.2 地址映射

地址映射：將程式地址空間中使用的邏輯地址變成主存中的物理地址的程序

動態地址映射：在程式執行期間，隨著每條指令和資料的訪問自動連續地進行地址映射
動態地址映射硬體支持：重定位暫存器

7.2.3 主存分配

主存分配功能包括：
①制定分配策略、構造分配用的資料結構，
②回應主存分配請求、
③決定用戶程式的主存位置并將程式裝入記憶體

主存管理存盤器的策略：
①放置策略
②調入策略
③淘汰策略

7.2.4 存盤保護

存盤保護：有硬體（軟體配合）保證每個程式只能在給定的存盤區域內活動

7.3 磁區存盤管理及存在的問題

7.3.1 動態磁區存盤管理技術

7.3.2 磁區分配機構

flag：分配標志，空閑區為0，分配區為非0數值
size：磁區大小，
next：勾鏈字，空閑區中，指向下一個空閑磁區，分配區中，為0

7.3.3 磁區分配與放置策略

常用的放置策略：首次適應演算法、最佳適應演算法、最壞適應演算法
（1）首次適應演算法：將輸入的程式放置到主存里第一個足夠入它的地址最低的空閑區中
空閑區佇列結構：空閑區地址由高到低排序
特點：盡可能利用存盤器中低地址的空閑區，而盡量保存高地址的空閑區

（2）最佳適應的演算法：將輸入的程式放置到主存中與它所需大小最接近的空閑區中
空閑區的佇列結構：空閑區大小由小到大排序
特點：盡可能利用存盤器中小的空閑區，而盡量保存大的空閑區

（3）最壞適應演算法：將輸入的程式放置到主存中與它所需大小差距最大的空閑區中
空閑區佇列結構：空閑區大小由大到小排序
特點：盡可能利用存盤器中大的空閑區

7.3.4 碎片問題及拼接技術

拼接技術：移動存盤器中某些已分配區中的資訊，使本來分散的空閑區連成一個很大的空閑區

拼接技術缺點：
①消耗系統資源
②當系統進行拼接時，它必須停止所有其他的作業
③拼接需要消耗大量的系統資源

7.4 頁式存盤管理

7.4.1 頁式系統應解決的問題

頁面：程式的地址空間被等分成大小相等的片，成為面
主存塊：主存被分成大小相等的片

7.4.2 頁式地址的變換

頁表：為了實作從地址空間到物理主存的映像，系統建立了頁與主存塊之間對應關系的資料結構，該頁面稱為頁面映像表，簡稱頁表

頁表組成：高速緩沖存盤器、主存區

當CPU給出的地址長度為16位，頁面大小為1KB時，在分頁系統中地址結構的格式為：

頁號6位，頁內位移10位
虛存大小：2¹⁰ × 2⁶ = 2¹⁶

當CPU給出的地址長度為32位，頁面大小為4KB時，在分頁系統中地址結構的格式為：

頁號20位，頁內位移12位
虛存大小：2²⁰ × 2¹² = 2³²

頁式地址變換步驟：（詳細見課本）
①CPU給出運算元地址（為2500）
②由分頁機構自動把邏輯地址分為兩部分，得到頁號p和頁內相對位移w（p=2,w=452，轉換成二進制）
③根據頁表始址暫存器指示的頁表始地址，以頁號為索引，找到第2頁對應的塊號（為7）
④將塊號b和頁內位移量w拼接在一起，就形成了訪問主存的物理地址（7×1024+452=7620）

7.4.3 請調頁面的機制

擴充頁表功能：

中斷位 i ——標識該頁是否在主存，若i=1，表示該頁不在主存；若i=0，表示該頁在主存
輔存地址——該頁面在輔存的位置

7.4.4 淘汰機制與策略

淘汰策略：用來選擇淘汰哪一頁的規則叫置換策略，也叫淘汰演算法

參考位——表示該頁最近是否被訪問，若為0，該頁沒有被訪問；若為1，該頁已被訪問
改變位——表示該頁是否被修改，若為0，該頁未被修改；若為1，該頁已被修改

7.4.5 幾種置換演算法

（1）先進先出演算法（FIFO演算法）：總是選擇在主存中居留時間最長（即最早進入主存）的一頁淘汰，
思路：
建立一個頁面進入主存的先后次序表
建立一個替換指標，指向最早進入主存的頁面
當需要置換一頁時，選擇替換指標指向的那一頁，然后調整替換指標的內容

① 頁號表實作：
頁號表記錄頁面進入主存先后次序：2→4→5→1

當要調入第6頁時，將第2頁改為6，替換指標指向第4頁

②存盤分塊表實作：
存盤分塊表記錄頁面進入主存先后次序：4→5→1→2

替換指標內的數為所要替換的塊號
指標指向先后次序的下一個頁號，值為該頁號所對應的塊號

當要調入第8頁時，置換第4頁，先后次序：5→1→2→8
得到：

（2）最久未使用淘汰演算法（LRU演算法）：選擇最長時間未被使用的淘汰
①用頁號堆疊實作最久未使用演算法：
頁面訪問軌跡：4→5→1→2→5→6
頁號堆疊中，堆疊頂是剛被訪問過的頁號

②LRU近似演算法

7.5 段氏和段頁式存盤管理

7.5.1 段氏地址結構

7.5.2 段氏地址的變換

7.5.3 擴充段表功能

7.5.4 段頁式存盤管理

第八章 設備管理

8.1 設備管理概述

8.1.1 設備管理的功能

設備分類：
①存盤設備：存盤資訊的設備，又叫塊設備，如磁盤、磁鼓
②輸入輸出設備：將資訊從計算機外部輸入到機內或反之，又叫字符設備，如鍵盤、顯示幕、列印機
③通信設備：負責計算機之間的資訊傳輸，如調制解調器、網卡等

設備功能：
①狀態跟蹤
②設備分配
③設備控制

8.1.2 設備獨立性

設備獨立性：用戶在程式中使用的設備與實際使用的設備無關，也就是在用戶程式中僅使用邏輯設備名

邏輯設備名：用戶自己指定的設備名（或設備號），它是暫時的、可更改的

物理設備名：系統提供的設備的標準名稱，它是永久的，不可更改的

邏輯設備描述器：記錄了邏輯設備與物理設備的對應關系，內容包括——設備邏輯名、設備物理名、設備控制塊dcb指標、設備描述器佇列指標

在用戶程式中定義邏輯設備：
使用高級語言提供的指派陳述句，通過指派一個邏輯設備名（通道號）來定義一個設備或檔案
如：fd₁=open("/dev/ip" , mode)
n=write(fd₁,buf₁,count)
第一個陳述句是將fd₁（檔案描述符）與列印機ip以一定的模式（讀或寫）鏈接
第二個陳述句在列印機上輸出n個位元組的資訊

設備獨立性優點：
①方便用戶
②提高設備利用率
③提高系統可適應性和可擴展性

8.1.3 設備控制塊

設備控制塊：系統為每一臺設備配置了一個用來記錄設備的硬體特性、連接和使用情況的資料結構

設備控制塊的內容
設備名
設備屬性
指向命令轉換表的指標
在I/O總線上的設備地址
設備狀態
當前用戶行程指標
I/O請求佇列指標

8.2 緩沖技術

8.2.1 緩沖概述

緩沖：緩沖技術是兩種不同速度的設備之間傳輸資訊時平滑傳輸程序的常用手段

緩沖類別：
①緩沖器
②軟體緩沖

緩沖技術解決的問題：
①解決速度差異的問題
②協調傳輸資料大小不一致的問題
③應用程式的拷貝語意問題

8.2.2 常用的緩沖技術

常用的緩沖技術：
①雙緩沖
②緩沖池：由主存中的一組緩沖區組成，每個緩沖區的大小一般等于物理記錄的大小

8.3 設備分配

8.3.1 設備分配概述

外部設備分兩類：
獨占設備——一般采用靜態分配
共享設備——一般采用動態分配

I/O設備分配演算法：
①先請求先服務：設備請求佇列按行程發出此I/O請求的先后次序排序
②優先級最高者優先：設備請求佇列按行程發出此I/O請求的優先級高低排序

常用的設備分配技術：獨享分配、共享分配、虛擬分配

8.3.2 獨享分配

8.3.3 共享分配

8.3.4 虛擬分配