操作系統-進程

本篇內容：

• 進程與線程（進程管理）
• 進程狀態切換
• 進程調度演算法
• 進程同步
• 進程通信

（一）進程管理

進程和線程的區別：

• 定義區別：

進程是資源分配的基本單位。進程式控制制塊 (Process Control Block, PCB) 描述進程的基本信息和運行狀態，所謂的創建進程和撤銷進程，都是指對 PCB 的操作。

線程是獨立調度的基本單位。一個進程中可以有多個線程，它們共用進程資源。
例如：QQ 和瀏覽器是兩個進程，瀏覽器進程裡面有很多線程，例如 HTTP 請求線程、事件響應線程、渲染線程等等，線程的併發執行使得在瀏覽器中點擊一個新鏈接從而發起 HTTP 請求時，瀏覽器還可以響應用戶的其它事件。

• 擁有資源區別：

進程是資源分配的基本單位，

線程不擁有資源，線程可以訪問隸屬進程的資源。

• 調度

線程是獨立調度的基本單位，在同一進程中，線程的切換不會引起進程切換，從一個進程中的線程切換到另一個進程中的線程時，會引起進程切換。

• 系統開銷區別：

線程開銷小，進程開銷大

原因：創建或撤銷進程時，系統都要為之分配或回收資源，如記憶體空間、I/O 設備等，所付出的開銷遠大於創建或撤銷線程時的開銷。
在進行進程切換時，涉及當前執行進程 CPU 環境的保存及新調度進程 CPU 環境的設置，而線程切換時只需保存和設置少量寄存器內容，開銷很小

• 通信區別：

線程間:通過直接讀寫同一進程中的數據進行通信;
進程通信:藉助 IPC。

（二）進程狀態

5種狀態：

• 創建狀態：

進程由創建而產生。多個步驟才能創建：
（1）由進程申請一個空白的進程式控制制塊(PCB)，向PCB中填寫控制和管理進程的信；
（2）為該進程分配運行時所必須的資源；
（3）把該進程轉入就緒狀態並插入到就緒隊列中；

• 就緒狀態：

進程已經準備好運行的狀態;進程已分配到除CPU以外所有的必要資源後，只要再獲得CPU，便可立即執行;
即：有執行資格，沒有執行權的進程。（妃子隨時準備好讓皇帝翻牌子的狀態）

• 運行狀態：

進程已經獲取CPU，其進程處於正在執行的狀態。
單處理機的系統中，只有一個進程處於執行狀態,在多處理機系統中，有多個進程處於執行狀態。

• 阻塞狀態：

正在執行的進程由於發生某事件（如I/O請求、申請緩衝區失敗等）暫時無法繼續執行的狀態（阻塞狀態）；
此時引起進程調度，操作系統把處理機分配給另外一個就緒的進程，而讓受阻的進程處於暫停的狀態(阻塞態)；

• 終止狀態：

進程的終止也要通過兩個步驟
（1）等待操作系統進行善後處理，
（2）將其PCB清零，並將PCB空間返還給系統。

狀態切換

• 就緒→執行

就緒狀態的進程，進程調度程式為之分配了處理機後，進程便由就緒狀態轉變成**執行狀態。

• 執行→就緒

執行狀態的進程在其執行過程中，因分配給它的一個時間片已用完而不得不讓出處理機(PCB)，於是進程從執行狀態轉變成就緒狀態。

• 執行→阻塞

正在執行的進程因等待某種事件發生而無法繼續執行時，便從執行狀態變成阻塞狀態。

• 阻塞→就緒

處於阻塞狀態的進程，若其等待的事件已經發生，於是進程由阻塞狀態轉變為就緒狀態

註意：
(1)只有就緒態和運行態可以相互轉換，其它的都是單向轉換。

就緒狀態的進程通過調度演算法從而獲得 CPU 時間，轉為運行狀態；
運行狀態的進程，在分配給它的 CPU 時間片用完之後就會轉為就緒狀態，等待下一次調度。

(2)阻塞狀態是缺少需要的資源從而由運行狀態轉換而來，但是該資源不包括 CPU 時間，缺少 CPU 時間會從運行態轉換為就緒態。

（三）進程調度演算法

不同環境的調度演算法目標不同，因此需要針對不同環境來討論調度演算法。

三種不同系統

批處理系統、互動式系統、實時系統

1.批處理系統

沒有太多的用戶操作，調度演算法目標是保證吞吐量和周轉時間

• 先來先服務（FCFS）：非搶占式，按請求順序調度；利於長作業，不利於短作業；
  （**缺點：**短作業必須等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長）
• 短作業優先：非搶占式，按估計運行時間最短的順序進行調度（時間最短的最先調度，次短的第二，依次下去。缺點：長作業有可能會餓死，處於一直等待短作業執行完畢的狀態。因為如果一直有短作業到來，那麼長作業永遠得不到調度。）
• 最短剩餘時間優先：當一個新的作業到達時，其整個運行時間與當前進程的剩餘時間作比較。如果新的進程需要的時間更少，則掛起當前進程，運行新的進程。否則新的進程等待。

2.互動式系統

有大量的用戶交互操作，調度演算法的目標是快速地進行響應。

• 時間片輪轉
  所有就緒進程按先來先服務原則排隊，第一個排隊的先執行一個時間片的時間，時間到了後，這個同學就排到隊伍最後面去，讓第二個人開始也執行一個時間片，時間到了就排到隊列末尾去，這樣依次執行下去。（類似輪流和CPU玩，每人5分鐘這樣子）
  效率問題：和時間片的大小有很大關係，時間片太小，進程切換得太頻繁，在進程切換上就會花過多時間，時間片太長，實時性得不到保證；
• 優先順序調度：為每個進程分配一個優先順序，按優先順序進行調度;(防止低優先順序的永遠等不到調度，可隨時間的推移增加等待進程的優先順序)
• 多級反饋隊列:設置了多個隊列，每個隊列時間片大小都不同，例如 1,2,4,8,…。進程在第一個隊列沒執行完，就會被移到下一個隊列。
  

3.實時系統

實時系統要求一個請求在一個確定時間內得到響應
硬實時： 必須滿足絕對的截止時間；
軟實時： 可以容忍一定的超時；

（四）進程同步

四個概念：臨界區、同步和互斥、信息量、管程
1.臨界區： 對臨界資源進行訪問的那段代碼稱為臨界區；

為了互斥訪問臨界資源，每個進程在進入臨界區之前，需要先進行檢查；

2.同步與互斥：

• 同步：多個進程因為合作產生的直接制約關係，使得進程有一定的先後執行關係;
• 互斥：多個進程在同一時刻只有一個進程能進入臨界區

3.信息量
信號量（Semaphore）是一個整型變數，可以對其執行 down 和 up 操作，也就是常見的 P 和 V 操作。

• down: 信號量 > 0 ，執行 -1 操作；信號量 = 0，進程睡眠，等待信號量大於 0；
• up: 對信號量執行 +1 操作，喚醒睡眠的進程讓其完成 down 操作；
  如果信號量的取值只能為 0 或者 1，那麼就成為了 互斥量（Mutex） ，0 表示臨界區已經加鎖，1 表示臨界區解鎖。

4.管程
概念： 是一個資源管理模塊，其中包含了共用資源的數據結構，以及由對該共用數據結構實施操作的一組過程（方法）所組成的資源管理程式。

使用信號量機制實現的生產者消費者問題需要客戶端代碼做很多控制，而管程把控制的代碼獨立出來，不僅不容易出錯，也使得客戶端代碼調用更容易。

• 重要特性： 在一個時刻只能有一個進程使用管程。進程在無法繼續執行的時候不能一直占用管程，否則其它進程永遠不能使用管程。
  

（五）經典同步問題

生產者和消費者問題

問題描述：使用一個緩衝區來保存物品，只有緩衝區沒有滿，生產者才可以放入物品；

解析：因為緩衝區屬於臨界資源，因此需要使用一個互斥量 mutex 來控制對緩衝區的互斥訪問。

為了同步生產者和消費者的行為，需要記錄緩衝區中物品的數量。數量可以使用信號量來進行統計，這裡需要使用兩個信號量：empty 記錄空緩衝區的數量，full 記錄滿緩衝區的數量。其中，empty 信號量是在生產者進程中使用，當 empty 不為 0 時，生產者才可以放入物品；full 信號量是在消費者進程中使用，當 full 信號量不為 0 時，消費者才可以取走物品。

註意，不能先對緩衝區進行加鎖，再測試信號量。也就是說，不能先執行 down(mutex) 再執行 down(empty)。如果這麼做了，那麼可能會出現這種情況：生產者對緩衝區加鎖後，執行 down(empty) 操作，發現 empty = 0，此時生產者睡眠。消費者不能進入臨界區，因為生產者對緩衝區加鎖了，消費者就無法執行 up(empty) 操作，empty 永遠都為 0，導致生產者永遠等待下，不會釋放鎖，消費者因此也會永遠等待下去。

讀者和寫者問題

允許多個進程同時對數據進行讀操作，但是不允許讀和寫以及寫和寫操作同時發生。

一個整型變數 count 記錄在對數據進行讀操作的進程數量，一個互斥量 count_mutex 用於對 count 加鎖，一個互斥量 data_mutex 用於對讀寫的數據加鎖。

哲學家進餐問題

問題描述：五個哲學家圍著一張圓桌，每個哲學家面前放著食物。哲學家的生活有兩種交替活動：吃飯以及思考。當一個哲學家吃飯時，需要先拿起自己左右兩邊的兩根筷子，並且一次只能拿起一根筷子。

錯誤解法：如果所有哲學家同時拿起左手邊的筷子，那麼就無法拿起右手邊的筷子，造成死鎖。

正確解法: 兩個約束條件

• 必須同時拿起左右兩根筷子;
• 必須在左右兩個另鄰居都沒有進餐的情況下才允許進餐;

（六）進程通信

進程同步和進程通信的區別:

進程通信是為了達到進程同步目的的一種手段。為了讓進程同步，進程間必須通信，傳輸一些進程同步所需要的信息。

五個概念：管道、FIFO、消息隊列、信號量、共用存儲、套接字

1.管道（匿名管道）

定義： 把一個進程連接到另一個進程的一個數據流成為一個"管道"；
用途： 把一個進程的輸出通過管道連接到另一個進程的輸入；
本質：內核的一塊緩存；
創建 ： 通過pipe函數創建，fd(0)用於讀，fd(1)用於寫。
特點：

• 只支持半雙工通信（單向）；
• 只能在父子進程或兄弟進程中使用；
• 管道內部自帶同步機制：子進程寫一條，父進程讀一條；
• 當進程退出之時，管道也隨之釋放，與文件保持一致；
• 管道的生命周期尾隨進程，進程結束管道就沒了；

實現原理：

單進程通信原理

父子進程通信原理

2.FIFO（命名管道）

概念： 本質上是一個管道文件，可以通過命令創建也可以通過函數創建，用戶可以看到；
特點：

• 可以進行不相干進程間的通信;
• 命名管道是一個文件，對於文件的相關操作對其同樣適用;

FIFO 常用於客戶-伺服器應用程式中，FIFO 用作匯聚點，在客戶進程和伺服器進程之間傳遞數據。

3.消息隊列

優點（與FIFO比較）

• 消息隊列可以獨立於讀寫進程存在，避免了 FIFO 中同步管道的打開和關閉時可能產生的困難；
• 避免了 FIFO 的同步阻塞問題，不需要進程自己提供同步方法；
• 讀進程可以根據消息類型有選擇地接收消息，而不像 FIFO 那樣只能預設地接收。

4.信號量

是一個計數器,用於為多個進程提供對共用數據對象的訪問.

5.共用存儲

允許多個進程共用一個給定的存儲區。因為數據不需要在進程之間複製，所以這是最快的一種 IPC。

需要使用信號量用來同步對共用存儲的訪問。

多個進程可以將同一個文件映射到它們的地址空間從而實現共用記憶體。另外 XSI 共用記憶體不是使用文件，而是使用記憶體的匿名段。

6.套接字

可用於不同機器間的進程通信;

@聲明和致謝

本篇博客為個人學習筆記,大部分內容來自該博主cyc2018,另有部分來自其他一些博客文章,在此表示感謝!