應該和之前的筆記編寫時間相差不多，因為檔案建立時間已經超過考試時間，可能某次移動檔案是創造寫吧

作業系統的地位

電腦系統由硬體和軟體兩部分組成。通常把未配置軟體的電腦稱為裸機。直接使用裸機不僅不方便，而且將嚴重降低工作效率和機器的利用率。作業系統 (Operating System) 目的是為了填補人與機器之間的鴻溝，即建立使用者與電腦之間的介面，而為裸機配置的一種系統軟體

作業系統在電腦系統中的地位如下圖所示

從圖中可見，作業系統是裸機上的第一層軟體，是對硬體系統功能的首次擴充。它在電腦系統中佔據重要而特殊的地位，所有其他軟體，如編輯程式、組譯程式、編譯程式、資料庫管理系統等系統軟體，以及大量的應用軟體都是建立在作業系統基礎上的，並得到它的支援和取得它的服務

從使用者角度看，當電腦配置了作業系統後，使用者不再直接使用電腦系統硬體，而是利用作業系統所提供的指令和服務去操縱電腦，作業系統已成為現代電腦系統中必不可少的最重要的系統軟體，因此把作業系統看作是使用者與電腦之間的介面

行程管理

行程管理也稱為處理器管理。在多工批次處理系統和分時系統中有多個並行執行的程式，為了描述系統中程式執行時動態變化的過程引入了行程（Process）。行程是資源分配和獨立運行的基本單位。行程管理重點需要研究各行程之間的並行特性，以及行程之間相互合作與資源競爭產生的問題

程式順序執行的特徵

前趨圖是一個有向無環圖，由節點和有向邊組成，節點代表各程式段的操作，而節點間的有向邊表示兩個程式段操作之間存在的前趨關係。程式段 Pi 和 Pj 的前趨關係表示成 Pi→Pj，其中，Pi 是 Pj 的前趨，Pj 是 Pi 的後繼，其含義是 Pi 執行結束後 Pj 才能執行

下圖為 3 個節點的前趨圖，輸入是計算的前趨，輸入結束才能進行計算；計算是輸出的前趨，計算結束才能輸出

程式順序執行時的主要特徵包括順序性、封閉性和可再現性

程式並行執行的特徵

若在電腦系統中採用多工程式設計技術，則主記憶體中的多道程式可處於並行執行狀態。對於上述有 3 個程式段的作業類別，雖然每個作業有前趨關係的各程式段不能在 CPU 和輸入/輸出各部件並行執行，但是同一個作業內沒有前趨關係的程式段或不同作業的程式段可以分別在 CPU 和各輸入/輸出部件上並行執行。例如，某系統中有一個 CPU、一台輸入設備和一台輸出設備，前趨圖如下

程式並行執行時的特徵如下

1. 失去了程式的封閉性
2. 程式和機器的執行程式的活動不再一一對應
3. 並行程序間的相互制約性

行程的狀態及其狀態間的切換

三態模型

在多工系統中，行程在處理器上交替執行，狀態也不斷地發生變化，因此行程一般有 3 種基本狀態：執行、就緒和阻塞

1. 執行。當一個程式在處理器上執行時，則稱該行程處於執行狀態。顯然，對於單處理器系統，處於執行狀態的行程只有一個
2. 就緒。一個行程獲得了除處理器外的一切所需資源，一旦得到處理器即可執行，則稱此行程處於就緒狀態
3. 阻塞。阻塞也稱等待或睡眠狀態，一個行程正在等待某一事件發生 (例如請求 I/O 等待 I/O 完成等) 而暫時停止執行，這時即使把處理器分配給行程也無法執行，故稱該行程處於阻塞狀態

五態模型

事實上，對於一個實際的系統，行程的狀態及其轉換更複雜。例如，引入新建態和終止態構成了行程的五態模型

行程間的通訊

在多工環境的系統中存在多個可以並行執行的行程，故行程間必然存在資源共享和相互合作的問題。行程通訊是指各個行程交換資訊的過程

同步與互斥：同步是合作行程間的直接制約問題，互斥是申請臨界資源行程間的間接制約問題

行程間的同步

在電腦系統中，多個行程可以並行執行，每個行程都以各自獨立的、不可預知的速度向前推進，但是需要在某些確定點上協調相互合作行程間的工作。例如，行程 A 向緩衝區送資料的操作，否則行程 B 必須停下來等待行程 A 的操作結束

可見，所謂行程間的同步是指在系統中一些需要相互合作，協同工作的行程，這樣的相互聯繫稱為行程的同步

行程間的互斥

行程的互斥是指系統中多個行程因爭用臨界資源而互斥執行。在多工系統環境中，各行程可以共享各類資源，但有些資源一次只能供一個行程使用，稱為臨界資源 (Critical Resource, CR)，如印表機、共享變數和表格等

臨界區管理的原則

臨界區 (Critical Section, CS) 是行程中對臨界資源實施操作的那段程式。對互斥臨界區管理的 4 條原則如下

1. 有空即進。當無行程處於臨界區時，允許行程進入臨界區，並且只能在臨界區執行有限的時間
2. 無空等待。當有一個行程在臨界區時，其他欲進入臨界區的行程必須等待，以保證行程互斥地存取臨界資源
3. 有限等待。對於要求存取臨界資源的行程，應保證行程能在有限的時間進入臨界區，以免陷入 “飢餓” 狀態
4. 讓權等待。當行程不能進入自己的臨界區時，應立即釋放處理器 (CPU)，以免行程陷入忙等狀態

號誌機制

荷蘭學者 Dijkstra 於 1965 年提出的號誌（Semaphore）機制是一種有效的行程同步與互斥工具。目前，號誌機制有了很大的發展，主要有整數號誌、記錄型號誌和號誌集機制

整數號誌與 PV 操作

號誌是一個整數變數，根據控制對象的不同被賦予不同的值。號誌分為如下兩類

1. 公用號誌。實現行程間的互斥，初值為 1 或資源的數目
2. 私用號誌。實現行程間的同步，初值為 0 或某個正整數

號誌 S 的物理意義：S ≥ 0 表示某資源的可用數，若 S ＜ 0 則其絕對值表示阻塞佇列中等待該資源的行程數

對於系統中的每個行程，其工作的正確與否不僅取決於它自身的正確性，而且與它在執行中能否與其他相關行程正確地實施同步互斥有關。PV 操作是實現行程同步與互斥的常用方法。P 操作和 V 操作是低級通訊原語，在執行期間不可分割。其中 P 操作表示申請一個資源，V 操作表示釋放一個資源

P 操作的定義

S := S - 1，若 S ≥ 0，則執行 P 操作的行程繼續執行；反之，則置該行程為阻塞狀態 (因為無可用資源)，並將其插入阻塞佇列

P 操作可用如下過程表示，其中 Semaphore 表示所定義的變數是號誌

1
2
3
4
5

Procedure P(Var S:Semaphore);
    Begain
        S := S - 1;
        If S < 0 then W(S) {執行P操作的行程插入等待佇列}
    End;

V 操作定義

S := S + 1，若 S ＞ 0 則執行 V 操作的行程繼續執行；反之，則從阻塞狀態喚醒一個行程，並將其插入就緒佇列，然後執行 V 操作的行程繼續

V 操作可用如下行程表示

1
2
3
4
5

Procedure V(Var S:Semaphore);
    Begain
        S := S + 1;
        If S <= 0 then R(S) {從阻塞佇列中喚醒一個行程}
    End;

利用 PV 操作實現行程的互斥

例如以下兩個行程可能會導致 COUNT 的值改變不當

1
2
3
4
5
6
7
8
9

# 1
if 有車通過 then
    COUNT := COUNT + 1;
GOTO L1;

# 2
PRINT COUNT;
COUNT := 0;
GOTO L2;

令號誌互斥 (mutex) 的初值為 1，在進入臨界區之前執行 P 操作鎖定資源，離開臨界區後執行 V 操作，程式碼如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 1
if 有車通過 then
    begin
        P(mutex)
        COUNT := COUNT + 1;
        V(mutex)
    end
GOTO L1;

# 2
begin
    P(mutex)
    PRINT COUNT;
    COUNT := 0;
    V(mutex)
end
GOTO L2;

建議觀看： 【作業系統】行程間通訊—互斥

利用 PV 操作實現行程的同步

行程的同步是由於行程間合作引起的相互制約的問題，要實現行程的同步可用一個號誌與訊息聯繫起來，當號誌的值為 0 時表示希望的訊息未產生，當號誌的值為非 0 時表示希望的訊息已經存在。假定用號誌 S 表示某條訊息，行程可以通過呼叫 P 操作測試訊息是否到達，呼叫 V 操作通知訊息已準備好。最典型的同步問題是單緩衝區的生產者和消費者的同步問題

建議觀看： 【作業系統】行程間通訊—同步

同類資源分配不當引起死結

若系統中有 m 個資源被 n 個行程共享，當每個行程都要求 k 個資源，而 m ＜ nk 時，即資源數小於行程所要求的總數時，可能會引起死結 (Deadlock)

例如，m＝5，n=3，k=3，若系統採用的分配策略是輪流地為每個行程分配，則第一輪系統先為每個行程分配一台，還剩下兩台；第二輪系統再為兩個行程各分配一台，此時，系統中已無可供分配的資源，使得各個行程都處於等待狀態導致系統發生死結

事實上，當 m ≥ n × (k - 1) + 1 時不會發生死結

死結的處理

死結的處理策略主要有四種：鴕鳥策略 (即不理睬策略)、預防策略、避免策略和檢測與解除死結

死結預防

死結預防是採用某種策略限制並行行程對資源的請求，破壞死結產生的 4 個必要條件之一，使系統在任何時刻都不滿足死結的必要條件。預防死結的兩種策略如下：

1. 預先靜態分配法。破壞了 “不可剝奪條件”，預先分配所需資源，保證不等待資源。該方法的問題是降低了對資源的利用率，降低行程的並行程度；有時可能無法預先知道所需資源
2. 資源有序分配法。破壞了 “環路條件”，把資源分類按順序排列，保證不形成環路。該方法存在的問題是限制行程對資源的請求；由於資源的排序佔用系統開銷

死結避免

死結避免是設法破壞產生死結的 4 個必要條件之一，嚴格防止死結的產生。死結避免則不那麼嚴格地限制產生死結的必要條件。最著名的死結避免演算法是 Dijkstra 提出的銀行家演算法，死結避免演算法需要很大的系統開銷

建議觀看： 銀行家演算法

執行緒

傳統的行程有兩個基本屬性：可擁有資源的獨立單位；可獨立排程和分配的基本單位。引入執行緒 (Thread) 的原因是行程在建立、撤銷和切換中，系統必須為之付出較大的時空開銷，故在系統中設置的行程數目不宜過多，行程切換的頻率不宜太高，這就限制了並行程度的提高

引入執行緒後，將傳統行程的兩個基本屬性分開，執行緒作為排程和分配的基本單位，行程作為獨立分配資源的單位。使用者可以通過建立執行緒來完成任務，以減少程式並行執行時付出的時空開銷

這樣，對於擁有資源的基本單位，不用頻繁地切換，進一步提高了系統中各程式的並行程度。需要說明的是，執行緒是行程中的一個實體，是被系統獨立分配和排程的基本單位。執行緒基本上不擁有資源，只擁有一點執行中必不可少的資源 (如程式計數器、一組暫存器和堆疊)，它可與同屬一個行程的其他執行緒共享行程所擁有的全部資源