行程的描述與控制

2.1 前趨圖與程式的執行

2.1.1 前趨圖

前趨圖是指一個有向無回圈圖，它用于描述行程之間的執行順序，圖中每個節點可以表示一個行程或者程式段，
乃至一條陳述句，節點間的有向邊則表示兩個節點之間存在偏序或前趨關系，沒有前趨的節點稱為初始節點，沒
有后繼的節點稱為終止節點，

 前趨圖不允許有回圈！

如上圖，有前趨關系P1->P2,P1->P3,P1->P4,P2->P5,P3->P5,P4->P6,P4->P7,P5->P8,P6->P8,P7->P9,P8->P9

2.1.2 程式的順序執行

通常，一個程式由若干個程式段組成，每一個成程式段完成特定的功能，他們在執行時都需要按照某種先后次序
順序執行，僅當當前一程式執行完之后，才執行后面的程式或程式段，

順序執行的特征：

• 順序性，處理機嚴格按照程式所規定的執行順序
• 封閉性，程式執行時獨占系統全部資源，因此，系統資源狀態的改變只與當前執行的程式有關，而不受外界因素的影響
• 可再現性，只要初始條件相同，一個程式的多次重復執行會得到相同的結果

2.1.3 程式的并發執行

:是指兩個或多個程式或程式段可在同一時間間隔內同時執行（微觀上看，任意時刻cpu上都只有一個程式執行）

并發執行的特征

程式的并發執行極大的提高了系統的吞吐量和資源利用率，同時也產生了不同于順序執行的新特征：

• 間斷性，由于資源共享和相互合作，并發執行的程式間形成了相互制約的關系，導致程式運行程序中會出現“執行-暫停-執行”的現象
• 失去封閉性，程式在執行時與其他并發執行的程式共享系統資源，因此，資源狀態的改變與其他程式有關，即程式本身的執行環境會受到外界程式的影響
• 不可再現性，同樣的初始條件，一個程式運行多次可能會得到不同的執行結果

2.2 行程的描述

2.2.1行程的定義與特征

行程的并發執行產生的不可再先性，決定了通常程式是不能參與并發執行的，為了使程式能夠正確的并發執行，
并且可以對并發的程式加以描述和控制，作業系統中引入了行程的概念，用行程來表示并發程式的執行，為了
使參與并發執行的每一個程式（含資料）都能獨立的運行，在作業系統中必須為之配置一個專門的資料結構，
稱為行程控制塊（PCB）,PCB，程式段，相關資料段三個部分構成一個行程物體（又稱行程映像），簡稱行程，

行程的定義

下面是幾個較為典型的：

1. 行程是程式的一次執行
2. 行程是一個程式及其資料在處理機上順序執行是所發生的活動
3. 行程是具有獨立功能的程式在一個資料集合上運行的程序，他是系統進行資源分配和調度的基本單位特征

行程的特征：

1. 動態性，動態性是行程最基本的特征，行程是程式的一次執行程序，因此是動態的，行程的動態性還表現在行程有一定生命周期，它必須由創建而產生，由調度而執行，由撤銷而消亡，
2. 并發性，并發性是指多個行程物體存在與記憶體中，并在一段時間內同時執行，并發是引入行程的目的，所以它也是行程最基本的特征，
3. 獨立性，行程物體是一個能夠獨立運行，獨立接受調度，獨立分配資源的基本單位，
4. 異步性，行程可按各自獨立，不可預知的速度向前推進，雖然行程具有異步性，但作業系統必須保證并發執行的結果具有可再現性，

2.2.2 行程的基本狀態及其轉換

行程的三種基本狀態

1. 就緒狀態：行程已經分配到除了CPU之外的所以必備資源，只要獲得CPU，就能立即執行，（如果系統中有許多就緒狀態的行程，就按照一定的策略拍成一個佇列，稱為就緒佇列）
2. 執行狀態：指行程已經獲得CPU，其程式正在執行的狀態，
3. 阻塞狀態：這是指正在執行的行程由于發生某事件（如I/O請求，申請緩沖區失敗）暫時無法繼續執行的狀態，此時引起行程調度，作業系統把處理及分配給另一個就緒行程，從而讓受阻行程處于暫停狀態，一般稱為阻塞狀態，通常系統把阻塞行程排成一個佇列，稱為阻塞佇列，只有等相應的事件完成后，才能去競爭CPU，

三種狀態的轉換

對于單個行程而言，任何時刻，它只能處于三種狀態之一，而隨著行程自身的推進和外界環境條件的變化，他的狀態可以動態的轉換，如下圖：

創建狀態

創建行程是通過創建原語完成的，被創建的行程叫做紫禁城，創建子行程的行程叫做父行程，
行程創建原語的主要任務是創建行程控制塊PCB

行程創建的程序：

1. 先從PCB集合中申請一個空白PCB
2. 為行程分配記憶體等資源，并根據父行程提供的引數和分配到的資源的情況來對PCB進行初始化
3. 將新行程插入就緒佇列

終止狀態

當行程完成任務或者遇到異常情況和外界干預需要結束時，應通過行程終止原語來終止行程，

行程終止的實質時識訓PCB,具體程序如下：

1. 找到要終止的行程的PCB
2. 若該行程正在執行，則終止它的執行，，并設定重新調度標志
3. 終止屬于該行程的所有子行程
4. 釋放終止行程的全部資源
5. 將終止行程移除它所在的佇列并識訓PCB

2.2.3 掛起操作和行程狀態的轉換

當該操作作用于某個行程時，該行程將被掛起，意味著此時行程處于靜止狀態，
如果行程正在執行，他將暫停執行，如果本來就處于就緒狀態，那么此行程將
暫時不接受調度，與掛起操作對應的是激活操作，

掛起操作的引入

• 終端用戶的需要，用戶在運行自己程式時若想暫停自己的程式，可將其掛起使之停下來，
• 父行程請求，以便考察和修改子行程，或者協調各子行程之間的活動
• 負荷調節的需要，當實時系統的作業負荷較重，可能影響到實時任務的控制時，可由系統將不重要的行程掛起，以保證系統正常運行
• 作業系統的需要，作業系統有時希望掛起某些行程，以便檢查運行中的資源使用情況或者記賬

引入原語操作后三個行程狀態的轉換

2.2.4 行程管理中的資料結構

行程控制塊PCB

為了便于系統描述和管理行程的運行，在OS核心為每個行程專門定義一個資料結構——行程控制塊，
PCB作為行程物體的一部分，記錄了OS所需的，用于描述當前情況以及行程運行的全部資訊，是OS
中最重要的記錄型資料結構，

PCB的作用是將程式變成可并發執行的行程，PCB是行程存在的唯一標志，
當處理機被中斷時，這些資訊必須保存到PCB中，以便進行重新執行時能從斷點處繼續執行

行程控制塊包含的資訊

• 行程識別符號，用于唯一的標識一個行程，一個行程通常有兩種識別符號：
  （1）外部識別符號：為了方便用戶對行程的訪問，需要為每一個行程設定一個外部識別符號，由創建者提供，通常由數字，字母組成，
  (2) 內部識別符號，為了方便系統對行程的使用，在OS中又設定了內部識別符號，賦予每一個行程唯一的數字識別符號，它通常是一個行程的序號，

• 處理機狀態：處理機狀態資訊也稱處理機的背景關系，主要由處理機的各種暫存器的內容組成，它用于CPU切換時保存現場資訊和恢復現場資訊，

• 行程調度資訊：主要包括行程的狀態優先級，等待和使用CPU的時間總和等資訊，用作行程調度和對換的依據，

• 行程控制資訊：具體包括程式和資料的地址，行程同步和同通信資訊，資源清單和行程佇列指標等，

  在一個系統中，通常有許多PCB，他們構成PCB集合，為了方便管理，
  系統通常用線性方式或者鏈接方式或者索引方式將這些PCB組織起來，
  

2.3 行程控制

行程控制是行程管理最基本的功能，主要包括創建新行程，終止已完成的行程，將因發生
例外情況而無法運行的行程至于阻塞狀態，負責行程運行中的狀態轉換等功能，
行程控制一般是通過OS原語來實作的，

2.3.1 作業系統內核

為了防止OS本身及其關鍵資料遭到應用程式有意或者無意破壞，通常將處理機的執行狀態分為系統態和用戶態兩種：
1.系統態：又稱管態或者內核態，具有較高的特權，能執行一切指令，訪問所有暫存器和存盤區，傳統的OS都在系統態運行，
2.用戶態：又稱為目態，具有較低特權的執行狀態，僅能執行指定指令，訪問指定的暫存器和存盤區，

支撐功能

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

資源管理功能

1. 行程管理：如行程的調度與分派，行程的創建與撤銷
2. 存盤器管理：實作地址轉換，記憶體分配與回收的功能，以及實作記憶體保護與對換功能
3. 設備管理：對各類設備驅動程式的管理，用于緩和I/O與CPU速度不匹配的矛盾的緩沖管理等

2.3.2 行程的創建

導致一個行程去創建另一個行程的典型事件有分時系統的用戶登錄和批處理系統的作業調度.創建
行程是通過創建原語完成的，被創建的行程稱為子行程，而創建子行程的行程稱為父行程，子進
又可以繼續創建子行程，從而形成一個有向的行程樹，即行程圖，

行程的創建

行程創建原語的主要任務是創建行程控制塊PCB，具體操作程序是：

1. 先從PCB集合中申請一個空白PCB，為新行程申請獲得唯一的數字識別符號，并從PCB集合中索取一個空白PCB
2. 為行程分配記憶體等資源，包括物理和邏輯資源，
3. 根據父行程提供的引數和分配到的資源情況對PCB進行初始化
   （1）：初始化標識資訊，將系統分配的識別符號和父行程識別符號填入PCB
   （2）：初始化處理機狀態
   (3）：初始化處理機控制資訊（行程狀態）
4. 如果行程就緒佇列能接納新行程，將行程插入就緒佇列

引起創建行程的事件

1. 用戶登錄，分時系統中，登陸成功后，系統將為該用戶創建一個新行程，并把它插入就緒佇列中，
2. 作業調度，在多道批處理系統中，當作業調度程式按照一定演算法調度到某個作業時，便將他們裝入記憶體，為他們創建行程，并把他們插入就緒佇列中，
3. 提供服務，當用戶程式提出請求時，系統將專門創建一個行程來提供用戶所需要的服務
4. 應用請求，

2.3.3行程的終止

引起行程終止的事件

1. 正常結束，行程任務已完成，準備退出運行，
2. 例外結束，（越界錯，非法指令，保護錯，特權指令錯，運行超時，等待超時，算術運算錯，I/O故障）
3. 外界干預，是指行程應外界請求而終止（包括操作員或者作業系統干預，父行程請求，因父行程終止，所有子行程也應該結束，

行程的終止程序

1. 根據被終止行程的識別符號，從PCB集合中檢索出該行程的PCB，從中讀出該行程的狀態
2. 若被終止行程正處于執行狀態，應立即終止該行程的執行，并置調度標識為真，用于指示該行程終止后重新進行調度
3. 若該行程還有子行程，還應終止它的所有子行程，以防子行程成為不可控程式
4. 將被終止行程所擁有的全部行程，或者將他們歸還給父行程，或者歸還給系統
5. 將被終止行程的PCB從所在佇列中移除，等待其他程式來收集資訊

行程的阻塞和喚醒

當正在執行的行程需要等待某種事件或本身無新作業做時，應呼叫阻塞原語將自己從執行
狀態轉換成阻塞狀態，
具體程序：停止行程執行，將其狀態改為阻塞狀態，并把它的PCB插入相應的阻塞佇列中，

當阻塞行程所等待的事件完成時，應呼叫喚醒原語將它從阻塞狀態轉換成就緒狀態，
具體操作：在阻塞佇列中移出該行程PCB,并將其設定為就緒狀態，插入就緒佇列中， 

注：關于行程同步和消費者-生產者問題將在下一篇文章專門總結，
希望大家多多支持，小白在此給大家鞠躬了