作業系統之行程執行緒篇

1. 行程

1.1 行程的定義與特征

（1）行程是什么？

行程是處于執行程序的程式，是系統分配資源的一個基本單位，

（2）行程的組成

行程由PCB、程式段和資料段組成，

（3）行程的特征

（4）PCB

行程中最重要的就是PCB，

1.2 行程的狀態

行程的相關狀態：

創建狀態(new) ：行程正在被創建，尚未到就緒狀態，
就緒狀態(ready) ：行程已處于準備運行狀態，即行程獲得了除了處理器之外的一切所需資源，一旦得到處理器資源(處理器分配的時間片)即可運行，
運行狀態(running) ：行程正在處理器上上運行(單核 CPU 下任意時刻只有一個行程處于運行狀態)，
阻塞狀態(waiting) ：又稱為等待狀態，行程正在等待某一事件而暫停運行如等待某資源為可用或等待 IO 操作完成，即使處理器空閑，該行程也不能運行，
結束狀態(terminated) ：行程正在從系統中消失，可能是行程正常結束或其他原因中斷退出運行，

1.3 原語實作對行程的控制

（1）什么是行程控制？

行程控制就是實作行程狀態的轉換，

（2）什么是原語？

原語是一種特殊的程式，它具有“執行時必須是一氣呵成的”，

（3）原語為什么用來實作行程的控制？

主要是因為原語的具有執行時必須是一氣呵成的，

（4）相關的原語

行程的創建
行程的終止
行程的阻塞
行程的喚醒
行程的切換

1.4 行程之間的通信

（1）什么是行程的通信？

行程之間進行資訊交換，行程是作業系統進行資源分配的基本單位，

（2）行程間的通信方式：

1. 管道/匿名管道(Pipes) ：用于具有親緣關系的父子行程間或者兄弟行程之間的通信，
2. 有名管道(Names Pipes) : 匿名管道由于沒有名字，只能用于親緣關系的行程間通信，為了克服這個缺點，提出了有名管道，有名管道嚴格遵循先進先出(first in first out)，有名管道以磁盤檔案的方式存在，可以實作本機任意兩個行程通信，
3. 信號(Signal) ：信號是一種比較復雜的通信方式，用于通知接收行程某個事件已經發生；
4. 訊息佇列(Message Queuing) ：訊息佇列是訊息的鏈表,具有特定的格式,存放在記憶體中并由訊息佇列識別符號標識，管道和訊息佇列的通信資料都是先進先出的原則，與管道（無名管道：只存在于記憶體中的檔案；命名管道：存在于實際的磁盤介質或者檔案系統）不同的是訊息佇列存放在內核中，只有在內核重啟(即，作業系統重啟)或者顯示地洗掉一個訊息佇列時，該訊息佇列才會被真正的洗掉，訊息佇列可以實作訊息的隨機查詢,訊息不一定要以先進先出的次序讀取,也可以按訊息的型別讀取.比 FIFO 更有優勢，訊息佇列克服了信號承載資訊量少，管道只能承載無格式字 節流以及緩沖區大小受限等缺，
5. 信號量(Semaphores) ：信號量是一個計數器，用于多行程對共享資料的訪問，信號量的意圖在于行程間同步，這種通信方式主要用于解決與同步相關的問題并避免競爭條件，
6. 共享記憶體(Shared memory) ：使得多個行程可以訪問同一塊記憶體空間，不同行程可以及時看到對方行程中對共享記憶體中資料的更新，這種方式需要依靠某種同步操作，如互斥鎖和信號量等，可以說這是最有用的行程間通信方式，
7. 套接字(Sockets) : 此方法主要用于在客戶端和服務器之間通過網路進行通信，套接字是支持 TCP/IP 的網路通信的基本操作單元，可以看做是不同主機之間的行程進行雙向通信的端點，簡單的說就是通信的兩方的一種約定，用套接字中的相關函式來完成通信程序，

1.5 多執行緒模型

（1）什么是執行緒？

執行緒是輕量級行程，是系統執行、處理機調度的基本單位，

（2）為什么要引入執行緒？

為了增加并發度，減少并發帶來的開銷，

（3）執行緒的實作方式

執行緒的實作分為兩類：用戶級執行緒(User-Level Thread,UTL)和內核級執行緒(Kernel-Level Thread, KTL)，內核級執行緒又稱內核支持的執行緒，

（4）執行緒間的通信方式

1. 互斥量(Mutex)：采用互斥物件機制，只有擁有互斥物件的執行緒才有訪問公共資源的權限，因為互斥物件只有一個，所以可以保證公共資源不會被多個執行緒同時訪問，比如 Java 中的 synchronized 關鍵詞和各種 Lock 都是這種機制，
2. 信號量(Semphares) ：它允許同一時刻多個執行緒訪問同一資源，但是需要控制同一時刻訪問此資源的最大執行緒數量
3. 事件(Event) :Wait/Notify：通過通知操作的方式來保持多執行緒同步，還可以方便的實作多執行緒優先級的比較操

（5）多執行緒模型
1. 多對一模型

2. 一對一模型

3. 多對多模型

2. 處理機調度

2.1 處理機調度的概念與層次

（1）處理機調度的基本概念：

按某一種演算法選擇行程將處理機分配給它，本質就是分配處理機給行程，

（2）調度的三個層次

2.2 行程調度的時機與方式

（1）什么時候進行行程調度？

1. 行程正常終止，主動放棄處理機
2. 分給行程的時間片使用完了，行程被動放棄處理機，

（2）什么時候不能進行行程調度？

（2）行程的剝奪方式

• 所謂行程調度方式，是指當某個行程正在處理機上執行時，若有某個更為重要或緊迫的行程需要處理，即有優先權更高的行程進入就緒佇列，此時應如何分配處理機，
  
  （3）行程的切換
  

2.3行程調度的相關演算法

1. 先到先服務(FCFS)調度演算法 : 從就緒佇列中選擇一個最先進入該佇列的行程為之分配資源，使它立即執行并一直執行到完成或發生某事件而被阻塞放棄占用 CPU 時再重新調度，
2. 短作業優先(SJF)的調度演算法 : 從就緒佇列中選出一個估計運行時間最短的行程為之分配資源，使它立即執行并一直執行到完成或發生某事件而被阻塞放棄占用 CPU 時再重新調度，
3. 時間片輪轉調度演算法 : 時間片輪轉調度是一種最古老，最簡單，最公平且使用最廣的演算法，又稱 RR(Round robin)調度，每個行程被分配一個時間段，稱作它的時間片，即該行程允許運行的時間，
4. 多級反饋佇列調度演算法 ：前面介紹的幾種行程調度的演算法都有一定的局限性，如短行程優先的調度演算法，僅照顧了短行程而忽略了長行程 ，多級反饋佇列調度演算法既能使高優先級的作業得到回應又能使短作業（行程）迅速完成，，因而它是目前被公認的一種較好的行程調度演算法，UNIX 作業系統采取的便是這種調度演算法，
5. 優先級調度 ： 為每個流程分配優先級，首先執行具有最高優先級的行程，依此類推，具有相同優先級的行程以 FCFS 方式執行，可以根據記憶體要求，時間要求或任何其他資源要求來確定優先級，

3. 行程的同步與互斥

3.1 行程同步與互斥的基本概念

（1）行程同步

行程同步又稱直接制約關系

（2）行程互斥

1. 行程互斥又稱間接制約關系
2. 當一個行程對臨界資源進行訪問時，其他行程不能對該臨界資源進行訪問，必須等待占有該臨界資源的行程釋放該臨界資源，其他行程才能對其進行訪問，

（3）為了禁止兩個行程同時訪問臨界資源，需要滿足以下規則

3.2 行程互斥的軟硬體實作方法

（1）單標志法

（2）雙標志先檢查法

（3）雙標志后檢查法

（4）Peterson演算法

3.3 信號量機制

（1）什么時信號量機制？

（2）整型信號量機制

（3）記錄型信號量機制

（4）信號量機制實作行程互斥

（5）信號量機制實作行程同步

• 想象一下四則運算的順序，加減乘除；

• 要想理解這一部分知識，必須知道P、V操作的內部實作原理
  

（6）信號量機制實作行程前驅

3.4 管程

（1）為什么引入管程？

引入管程的原因是為了實作行程的同步與互斥，

（2）管程的組成和特征

（3）Java中類似于管程的機制

個人認為Java中的鎖機制和同步器與管程的原理十分相似，

package com.xiao.test.sync;

//第一步：創建資源類，設定相關的屬性和操作方法
class Ticket{
    //票數
    private int number = 30;

    //使用synchronized實作并發操作
    //買票
    public synchronized void sale(){
        if(number > 0){
            System.out.println(Thread.currentThread().getName() + " 賣出: " + (number --) + " 還剩:" + number);
        }
    }

}

public class saleTicket {
    public static void main(String[] args) {
        Ticket ticket = new Ticket();

        new Thread(()->{
            for(int i = 1; i <= 40; i ++){
                ticket.sale();
            }
        },"AA").start();

        new Thread(()->{
            for(int i = 1; i <= 40; i ++){
                ticket.sale();
            }
        },"BB").start();

        new Thread(()->{
            for(int i = 1; i <= 40; i ++){
                ticket.sale();
            }
        },"CC").start();
    }
}

synchronized為獨占鎖，且是重量級鎖，當一個執行緒獲取到該鎖，才有權限訪問它所修飾的代碼，只有占有該鎖的執行緒釋放了該鎖之后其他執行緒才能獲取該鎖進行對相應代碼的執行，

4. 死鎖

1. 什么是死鎖？

執行緒死鎖描述的是這樣一種情況：多個執行緒同時被阻塞，它們中的一個或者全部都在等待某個資源被釋放，由于執行緒被無限期地阻塞，因此程式不可能正常終止，

2. 產生死鎖的條件

1. 互斥條件：該資源任意一個時刻只由一個執行緒占用，
2. 請求與保持條件：一個行程因請求資源而阻塞時，對已獲得的資源保持不放，
3. 不剝奪條件:執行緒已獲得的資源在未使用完之前不能被其他執行緒強行剝奪，只有自己使用完畢后才釋放資源，
4. 回圈等待條件:若干行程之間形成一種頭尾相接的回圈等待資源關系，

3. 如何預防死鎖？

1. 破壞請求與保持條件 ：一次性申請所有的資源，
2. 破壞不剝奪條件 ：占用部分資源的執行緒進一步申請其他資源時，如果申請不到，可以主動釋放它占有的資源，
3. 破壞回圈等待條件 ：靠按序申請資源來預防，按某一順序申請資源，釋放資源則反序釋放，破壞回圈等待條件，

4. 如何避免死鎖？

避免死鎖就是在資源分配時，借助于演算法（比如銀行家演算法）對資源分配進行計算評估，使其進入安全狀態，