第一章 作業系統引論

什么是作業系統

1. 定義
   作業系統是一組能有效地組織和管理計算機硬體和軟體資源，合理地對各類作業進行調度，以及方便用戶使用的程式的集合，（作業系統是一類程式的集合）
2. 從外部看OS

• 用戶環境觀點（計算機用戶的觀點）
• 虛擬機器觀點（應用程式員的觀點）

3. 從內部看OS

• 資源管理觀點（OS開發者觀點一）
• 作業組織觀點（OS開發者觀點二）
  

作業系統的目標和作用

1. 目標

• 有效性
• 方便性
• 可擴充性
• 開放性

2. 作用

• OS作為用戶與計算機硬體系統之間的介面
• OS作為計算機系統資源的管理者（四大管理：行程管理、存盤管理、設備管理、檔案管理）
• OS實作了對計算機資源的抽象

作業系統的發展程序

1. 人工操作方式
2. 脫機輸入輸出方式
3. 單道批處理系統（自動性、順序性、單道性）
4. 多道批處理系統（調度性、無序性、多道性）
5. 分時系統（多路性、獨立性、及時性、互動性）
6. 實時系統（實時性和可靠性、多路性、獨立性、互動性）
7. 通用作業系統

• 微機作業系統

1. 單用戶單任務作業系統（CP/M、MS-DOS）
2. 單用戶多任務作業系統（Windows98以及以前版本的Windows）
3. 多用戶多任務作業系統 （UNIX、Windows XP以及以后版本的Windows）

• 網路作業系統

8. 其他作業系統（MPS…）

作業系統的基本特征

1. 現代OS的兩個基本特征（慕課版）

• 任務¹共行

從宏觀上來看，任務共行是指系統中有多個任務同時運行
從微觀上來看，任務共行是指單處理器系統中的任務并發或多處理系統中的任務并行

• 資源共享

從宏觀上看，資源共享是指多個任務可以同時使用系統中的軟硬體資源
從微觀上看，資源共享是指多個任務可以交替互斥地使用系統中的某個資源

2. 作業系統的基本特征（所學習版）

• 并發性（最重要）
• 共享性
• 虛擬性
• 異步性

并發性和共享性是作業系統的兩個最基本特征，二者互為存在條件，

作業系統的主要功能

處理機管理

1. 行程控制
2. 行程同步
3. 行程通信
4. 行程調度

存盤器管理

1. 記憶體分配
2. 記憶體保護
3. 地址映射
4. 記憶體擴充

設備管理

1. 緩沖管理
2. 設備分配
3. 設備處理
4. 虛擬設備

檔案管理

1. 檔案存盤空間的管理
2. 目錄管理
3. 檔案的讀寫管理
4. 檔案的共享與保護

用戶介面

1. 用戶介面
2. 程式介面

作業系統的結構設計

作業系統的結構設計發展

1. 無結構
2. 模塊化
3. 分層式
4. 微內核

常見的OS總體結構風格

大多數現代OS其總體結構包含兩類子系統：1.用戶介面子系統；2.基礎平臺子系統；它們之間具有單向性，

1. 常見的基礎平臺子系統結構風格

• 分層結構風格
• 分級結構風格
• 分塊結構風格
• 單模式²結構風格
• 多模式結構風格

2. 雙模式基礎平臺子系統

• 核外子系統（User Mode）
• 核內子系統（Kernel Mode）

---

第二章 行程的描述與控制

現代OS中行程和執行緒的概念

行程：是資源分配的和獨立運行的基本單位，
執行緒：是系統調度的基本單位，

前驅圖和程式執行

1. 前驅圖
   有向無回圈圖（DAG ），描述一個程式的各部分（程式段或陳述句）間的依賴關系，或者是一個大的計算的各個子任務間的因果（前后）
   關系，前趨圖中的每個結點可以表示一條陳述句、一個程式段或一個行程，結點間的有向邊表示兩個結點之間存在的偏序關系或前趨關系“→ ”，沒有前趨的結點稱為初始結點，沒有后繼的結點稱為終止結點，此外，每個結點還具有一個權值，用于表示該結點所含有的程式量或結點的執行時間，
2. 程式順序執行

• 順序性
• 封閉性
• 可再現性

3. 程式并發執行

• 異步性
• 失去封閉性
• 不可再現性
  

行程的描述

行程的定義

行程是程式在一個資料集合上的運行程序，是系統進行資源分配和調度的一個獨立單位，
擴：行程物體：程式段+資料段+PCB

行程的特征

• 動態性
• 并發性
• 獨立性
• 異步性

行程和程式的區別

程式是指令的有序集合，是靜態的，其存在是無生命周期的，而行程由程式段、資料段、PCB組成，是動態的，有生命周期的，

行程的狀態模型

1. 二狀態模型
   Running
   Not-Running
2. 三狀態模型
   Running
   Ready
   Block
3. 五狀態模型
   Running
   Ready
   Block
   New
   Exit
4. 七狀態模型
   Running
   Ready
   Block
   Ready，Suspend
   Block，Suspend
   New
   Exit

掛起需要用到Swapping技術；

如何區分阻塞Or掛起？

• 行程是否等待事件，阻塞與否
• 行程是否被換出記憶體，掛起與否

行程控制塊PCB

1. 定義：
   是作業系統為了管理和控制行程的運行，而為每一個行程定義的一個資料結構，它記錄了系統管理行程所需的全部資訊，
2. 位置：
   常駐記憶體，存放在作業系統中專門開辟的PCB區內，
3. 作用：
   a. 作為獨立運行基本單位的標志，行程存在的唯一標志，系統根據PCB而感知相關行程的存在，
   b. 能實作間斷性運行方式，保護現場
   c. 提供行程管理所需要的資訊
   d. 提供行程調度所需要的資訊
   e. 實作與其他行程的同步和通信
4. 內容：
   a. 行程識別符號
   b. 處理機狀態
   c. 行程調度資訊
   d. 行程控制資訊

行程控制

作業系統內核的功能

1. 支撐功能

• 中斷處理
• 時鐘管理
• 原語³操作

2. 資源管理功能

• 行程管理
• 存盤器管理
• 設備管理

行程的層次結構

• 子行程可繼承父行程的所有資源
• 子行程撤銷時要把資源歸還給父行程
• 父行程撤銷時也必須撤銷所有子行程

引起行程創建的事件

用戶登錄、作業調度、提供服務、應用請求

行程創建流程

• 為行程分配一個唯一標識號
• 為行程分配空間
• 初始化PCB
• 建立鏈接
• 建立或擴展其他資料結構

引起行程結束的事件

正常、例外、外界干預

行程的終止程序

• 根據PID找到PCB，讀出該行程的狀態
• 若該行程為執行狀態，則終止其執行，調度新行程執行
• 若該行程有子孫行程，則立即終止其所有子孫行程
• 將該行程的全部資源，或歸還其父行程，或歸還系統
• 將被終止行程的PCB從所在佇列中移出，等待其他程式來搜集資訊

行程的阻塞與喚醒

阻塞是主動的，喚醒是被動的

行程的掛起與激活

掛起是由行程自己或其父行程調 Suspend 原語完成，激活是由父行程或用戶行程請求激活指定行程，系統利用 Active 原語將指定行程激活，

執行緒相關

1. 當引入執行緒后，執行緒是系統調度的基本單位，行程是資源分配的基本單位，而不再是一個可執行的物體，
2. 行程與執行緒的存在方式
   
3. 行程與執行緒的比較
   

行程同步

定義

是指對多個相關行程在執行次序上進行協調，他的目的是使系統中諸行程之間能有效地共享資源和相互合作，從而使程式的執行具有可再現性，

機制

硬體機制、信號量機制、管程機制

制約關系

• 直接制約關系（行程同步）
• 間接制約關系（行程互斥）
  

臨界資源

臨界資源是一次只允許一個行程使用的資源，需要行程采用互斥方式訪問；訪問臨界資源的那一段代碼叫做臨界區（CS區），

同步機制規則

• 空閑讓進
• 忙則等待
• 有限等待
• 讓權等待

硬體機制

• 關中斷
• TS指令
• Swap指令
  不符讓權等待（造成了忙等）

信號量機制

操作：P、V操作
原語：wait、signal（必須成對存在）
類別：資源信號量、互斥信號量
資源信號量：申請/歸還資源，可以初始化為一個正整數（>=0 表示可用資源數 <0表示被阻塞的行程數）
互斥信號量：申請/釋放使用權，常初始化為1
注意事項：兩個wait操作相鄰的話，順序很重要！同步wait必須在互斥wait前面！wait，signal成對出現，當為互斥操作時，處于同一行程，否則不在同一行程；使用PV不當，會產生死鎖；

管程機制

定義：一個資料結構和在該資料結構上能被并發行程所執行的一組操作，這組操作能使行程同步和改變管程中的資料，
管程規定每次只準許一個行程執行，從而實作了行程互斥，保證了管程共享變數的資料完整性，

經典行程同步的同步問題

生產者消費者問題

資源信號量：full=0、empty=n（分別表示滿緩沖區的數目、慷訓沖區的數目）
互斥資源量：mutex=1
核心演算法表示：

哲學家進餐問題

互斥資源量：五個

可能會出現死鎖，改進如下：

讀者寫者問題

1. 讀者優先：
   共享變數：readcount，當前讀者個數，初值為0
   互斥信號量：Rmutex=1（讀互斥）、Wmutex=1（寫互斥）
   
2. 寫者優先
   共享變數：readcount，當前讀者個數，初值為0
   互斥信號量：Rmutex=1（讀互斥）、Wmutex=1（寫互斥）、S=1（讀寫互斥）
   

行程通信

1. 共享存盤器系統
2. 訊息傳遞系統

• 直接通信方式：訊息緩沖通信
• 間接通信方式：信箱通信方式

3. 管道通信（共享檔案通信）
4. 客戶機-服務器系統

---

第三章 處理機調度與死鎖

處理機調度的層次和調度演算法的目標

按照層次劃分

高級調度 外《----》內
中級調度 外《----》內 但PCB在內
低級調度 記憶體之中

按OS型別劃分

批處理調度、分時調度、實時調度、多處理機調度

調度演算法的共同目標

• 資源利用率

C P U 利 用 率 = C P U 有 效 工 作 時 間 / 有 效 時 間 + 空 閑 等 待 時 間 CPU利用率=CPU有效作業時間/有效時間+空閑等待時間 CPU利用率=CPU有效工作時間/有效時間+空閑等待時間

• 公平性（防止行程饑餓）
• 平衡性（CPU型行程和I/O型行程）
• 策略強制執行（搶占）

批處理系統的目標

• 平均周轉時間

周轉時間：駐外存等待調度時間+駐記憶體等待調度時間+執行時間+阻塞時間=結束時間-到達時間
平均周轉時間= 1 n ∑ i = 0 n T i \frac{1} {n} \displaystyle \sum^{n}_{i=0} T_i n1?i=0∑n?Ti?
平均周轉時間可以衡量不同調度演算法對相同作業流的調度性能，
帶權周轉時間= 1 n ∑ i = 0 n T i T s \frac{1} {n} \displaystyle \sum^{n}_{i=0} \frac{T_i} {T_s} n1?i=0∑n?Ts?Ti??
帶權周轉時間越小越好

• 系統吞吐量
• 處理機利用率高

分時系統的目標

• 回應時間快
• 均衡性

實時系統的目標

• 截止時間保障
• 可預測性

作業調度（高級調度）

作業與作業步

Job是指，計算機用戶在一次上機程序中要求計算機系統為其所做的作業的集合；作業中的每項相對獨立的作業稱為作業步；
一個典型的作業可分為三個作業步：1.編譯作業步 2.連結裝配作業步 3.運行作業步

作業運行的三階段和三狀態

• 收容階段 后備狀態
• 運行階段 執行狀態
• 完成階段 停止狀態

FCFS（先來先服務）

基本思想：按行程（作業）進入就緒（后備）佇列的先后次序來分配處理機（為其創建行程），
調度方式：非剝奪
優點：簡單、有利于CPU繁忙型作業
缺點：I/O不利、短作業不利

SJF（最短作業優先）

基本思想：從后備作業中選擇一個或若干個估計運行時間最短的作業，將他們調入記憶體運行
調度方式：非剝奪
優點：有效降低作業的平均等待時間、提高了吞吐量
缺點：長作業不利、不考慮緊迫性、作業執行時間、剩余時間僅為估計

PSA（優先級調度演算法）

• 靜態優先級
• 動態優先級

HRRN（高回應比優先演算法）

基本思想： 既考慮了作業的等待時間，也考慮了作業的運行時間，是一種動態優先級調度演算法，
優先權=等待時間+要求服務時間/要求服務時間

行程調度（低級調度）

行程調度任務

1. 保存處理機的現場資訊
2. 按某種演算法選取行程
3. 把處理器分配給行程

行程調度機制

1. 排隊器
2. 分派器
3. 背景關系切換器

行程調度方式

1. 非搶占式
   優點：簡單、系統開銷小
   缺點：不適用于分時系統和實時系統
2. 搶占式
   搶占原則：優先權原則、短行程優先原則、時間片原則

SRT（最短剩余時間優先）

基本思想：它總是選擇預期剩余時間最短的行程，只要新行程就緒，且有更短的剩余時間，調度程式就可能搶占當前正在運行的行程
方式：搶占式
優點：搶占
缺點：必須記錄過去的服務時間，從而增加了開銷，

RR（時間輪轉調度演算法）

基本思想：系統將所有就緒行程按FCFS的原則，排成一個佇列依次調度，把 CPU 分配給隊首行程，并令其執行一個時間片，通常為
10-100ms，時間片用完后，系統的計時器發出時鐘中斷，該行程將被剝奪 CPU并插入就緒佇列末尾，
優點：非常公平
行程切換時機：

1. 若一個時間片尚未用完行程便已經完成，就立即再調度就緒佇列中隊首行程運行，并啟動一個新的時間片，
2. 如果在一個時間片用完時行程尚未運行完畢，則剝奪 CPU，調度程式把它送往就緒佇列的末尾，
   回應時間T = 時間片q × 就緒佇列行程數n
   時間片的選擇：略大于一次典型的互動所需要的時間（在一個時間片內能完成80%左右的行程）

MFQ（多級反饋佇列調度演算法）

1. 基本思想
   
   

實時調度

實作實時調度的基本條件

1. 提供必要的調度資訊
2. 系統處理能力強
3. 采用搶占式的調度機制
4. 具有快速切換機制

實時調度演算法的分類

1. 按實時任務性質

• 硬實時
• 軟實時

2. 按調度方式

• 非搶占
• 搶占

EDF（最早截止時間優先演算法）

1. 非搶占式
   
2. 搶占式
   

LLF（最低松弛度優先演算法）

基本思想：演算法是根據任務緊急（或松弛）的程度，來確定任務的優先級，任務的緊急度越高，其優先級越高，并使之優先執行，
方式：搶占式
松弛度 = 必須完成時間 - 本身剩余運行時間 - 當前時間

優先級倒置

1. 原因
   高優先級行程（或執行緒）被低優先級行程（或執行緒）延遲或阻塞，臨界資源
2. 解決方法
   
   

死鎖概述

死鎖定義

死鎖是指兩個或兩個以上的行程在執行程序中，因爭奪資源而造成的一種互相等待的現象，若無外力作用，它們都將無法推進下去，此時稱系統處于死鎖狀態，這些永遠在互相等待的行程稱為死鎖行程，
擴：饑餓是指一個行程一直得不到資源⁴

死鎖產生原因

1. 競爭不可搶占資源引起死鎖
2. 競爭可消耗資源引起死鎖
3. 行程間推進順序不當引起死鎖

死鎖產生的條件

1. 互斥條件
2. 請求和保持條件
3. 不可剝奪條件
4. 環路等待條件
   前三個是必要條件、最后一個是前三個條件產生的結果

處理死鎖的方法

1. 鴕鳥方法
2. 預防死鎖（破壞四個條件中的一個或幾個）
3. 避免死鎖
4. 檢測死鎖
5. 解除死鎖

避免死鎖（銀行家演算法）

1. 定義
   在資源的動態分配程序中, 采用某種策略防止系統進入不安全狀態⁵, 從而避免發生死鎖，（確保系統不進入不安全狀態），
   并非所有不安全狀態都是死鎖狀態，只要系統處于安全狀態，則可避免進入死鎖狀態，

2. 銀行家演算法
   實質：設法保證系統動態分配資源后不進入不安全狀態，以避免可能產生的死鎖，
   前提條件：要求行程必須預先提出自己的最大資源請求數量，這一數量不能超過系統資源的總量，系統資源的總量是一定的，
   資料結構：
   
   

演算法描述：


自然語言描述:
系統提出請求后，先判斷請求是否合法，如果合法，則嘗試修改，判斷修改后是否存在安全狀態，如果存在則確認修改，
如何判斷是否存在安全狀態：
當前系統可用資源分配給某個行程后，可以完成該行程，并釋放該行程資源，回圈直至全部完成；

死鎖的檢測與解除

1. 資源分配圖
   重要結論：如果資源分配圖中不存在環路，則系統中不存在死鎖；反之，如果資源分配圖中存在環路，則系統中可能存在死鎖，也可能不存在死鎖，
2. 死鎖定理
   

死鎖的解除

• 資源剝奪法
• 撤銷行程法

---

第四章 存盤器管理

存盤器的層次結構

程式的裝入和鏈接

如何從源程式變為在記憶體中可執行的程式

1. 編譯
2. 鏈接
3. 裝入
   

程式的裝入方式

1. 絕對裝入方式
2. 可重定位⁶裝入方式

3. 動態運行時裝入方式

程式的鏈接方式

1. 靜態鏈接
2. 裝入時動態鏈接
3. 運行時動態鏈接

存盤管理技術-磁區（連續）

固定磁區

1. 定義
   系統初始啟動時將記憶體劃分為數目固定、尺寸固定的多個磁區，這些磁區的尺寸可以相等也可以不等，
2. 條件
   系統需建立一張磁區說明表或使用表，以記錄磁區號、磁區大小、磁區的起始地址及狀態（已分配或未分配），
3. 流程
   當某個用戶程式要裝入記憶體時，通常將磁區按大小進行排隊，由記憶體分配程式檢索磁區說明表，從表中找出一個滿足要求的尚未分配的磁區分配該程式，同時修改說明表中相應磁區的狀態；若找不到大小足夠的磁區，則拒絕為該程式分配記憶體，程式執行完畢，釋放占用的磁區，管理程式修改說明表中相應磁區的狀態為未分配，實作記憶體資源的回收，
4. 缺點
   作業的大小并不一定與某個磁區大小相等，從而使一部分存盤空間被浪費，產生內零頭⁷，所以主存的利用率不高，磁區尺寸固定,系統無法運行大程式；磁區數目固定,使活動行程的數目受限，

動態磁區

1. 定義
   動態磁區分配是一種動態劃分存盤器的磁區方法，記憶體不是預先劃分好的，作業裝入時，根據作業的需求和記憶體空間的使用情況來決定是否分配，
2. 條件
   系統需要建立空閑磁區表（和空閑磁區鏈），用來登記系統中的空閑磁區（磁區號、磁區起始地址、磁區大小及狀態），以及需要特定的磁區分配演算法；
3. 流程
   
   
4. 缺點
   容易產生外零頭⁸，需要較好的匹配演算法支持，

5. 分配演算法
   a.基于順序搜索的動態磁區分配演算法

• 首次適應演算法
• 回圈首次適應演算法
• 最佳適應演算法
• 最壞適應演算法
  b.基于索引搜索的動態磁區分配演算法
• 快速適應演算法
• 伙伴系統
• 哈希演算法

6. 涉及到的暫存器（存盤保護）

• 基址暫存器
• 界限暫存器

7. 覆寫與對換
   覆寫可減少一個行程運行所需的空間，對換可讓整個行程暫存于外存中，讓出記憶體空間，
   覆寫是由程式員實作的，作業系統根據程式員提供的覆寫結構來完成程式段之間的覆寫，對換技術不要求程式員給出程式段之間的覆寫結構，
   覆寫技術主要在同一個作業或行程中進行，對換主要在作業或行程之間進行，

存盤管理技術-分頁（離散）

簡單分頁

虛擬存盤分頁

存盤管理技術-分段（離散）

簡單分段

虛擬存盤分段

---

第五章 虛擬存盤器

---

第六章 輸入輸出系統

---

第七章 檔案管理

---

第八章 磁盤存盤器的管理

---

---

1. 所謂任務（Task）是指，計算機在某個資源集合上所做的一次相對獨立的計算程序， ??

2. 所謂模式，簡單地說，就是程式在運行程序中使用的、由硬體體系結構提供的CPU特權模式， ??

3. 由若干條指令組成的，用于完成一定功能的一個程序，是一個不可分割的基本單位，執行程序中不許中斷， ??

4. 資源分類 可重用資源和消耗性資源、可搶占資源和不可搶占資源 ??

5. 安全狀態指在某一時刻，系統能按某種行程順序 (p1,p2,…，pn) 來為每個行程 Pi 分配其資源，直到滿足每個行程對資源的最大需求，使每個行程都可順利地完成，則稱此時的系統狀態為安全狀態，稱序列 (p1,p2,…，pn) 為安全序列，若某一時刻系統中不存在這樣一個安全序列，則稱此時的系統狀態為不安全狀態， ??

6. 重定位：由于一個作業裝入到與其地址空間不一致的存盤空間所引起的，需對其有關地址部分進行調整的程序就稱為重定位（實質是一個地址變換程序/地址映射程序），分為靜態、動態兩種方式；靜：軟體實作，動：軟硬（暫存器支持）結合， ??

7. 內零頭是指分配給作業的存盤空間中未被利用的部分， ??

8. 外零頭是指系統中無法利用的小存盤塊， ??