作業系統之進程管理科普

簡介

本文主要介紹作業系統中進程管理的邏輯，主要包含了典型的進程排程演算法，進程和執行緒的關係，進程之間互斥和同步演算法幾塊。

基礎知識

進程排程和管理是作業系統知識中非常重要的一環。

每個進程都有如下三個狀態：

1. 就緒
2. 執行
3. 阻塞

一般來說，一個進程一開始處於就緒狀態，等待CPU選擇他執行了之後，就進入了執行狀態，當進程出現IO操作之後，就進入阻塞狀態。也有可能是時間片用光了，從執行狀態進入就緒狀態等待CPU排程。

普通排程演算法

FCFS

First Come First Service。FIFO方式的排程策略，先來後到的服務方式。

這種方式的優勢是實現簡單，也是最容易想到的排程方案。但是有兩個重大問題：

1. 對短進程的執行不利

   短進程必須等到前面長進程執行完畢了之後才能執行，可能會等待較長時間。

2. 對IO密集型執行不利

   IO密集型比短進程還慘。還不容易排隊等到他執行了，結果沒執行一會兒就因為IO阻塞去了，等IO操作完畢了之後，還得重新排隊。

   所以這個演算法對IO密集型的進程執行效率是極其低下的。

RR

Round Robin。輪詢排程演算法為每個進程分配固定的時間片，時間片用完了就必須重新到隊尾去排隊。

這樣的設計解決了FCFS的第一個問題，相對而言也部分解決了第2個問題。

但是對IO密集型進程依然解決得不太好，有一個優化的方案就是設計兩個佇列，將因為IO阻塞的進程單獨放一個佇列，在選擇下一個執行進行的時候對這個佇列的進程提權。

FCFS還有另外一個比較複雜的問題就是如何選擇時間片。時間片過長就退化成FCFS演算法了，過短又會造成切換開銷太大。

Prediction

基於預測的演算法。這類預測演算法都是假設我們知道每個進程總共所需要的時間，以及IO占比資訊。

假設我們能收集到這些資訊，可以有如下幾種排程演算法：

1. 最短執行時間優先
2. 最短剩餘時間優先
3. 綜合已經執行時間和剩餘時間來排序

但是在真實世界中，一般這個資訊是無法預測的。即使是同一個進程，之前執行的情況對當前執行的進程也不一定有參考價值。比如cat程式，不同引數對執行時間影響很大。

Feedback

這個是基於Prediction來優化的。如果說Prediction是需要預測將來進程還需要多少資源的話，Feedback演算法就是基於已經消耗了的資源來判斷優先順序。

一般來說，也就是執行時間越長，優先順序越低的排程演算法。

Unix排程演算法

老版排程演算法

這是2.6版本之前的排程演算法，該演算法採用優化的RR演算法，每個進程的優先順序演算法如下：

p(i) = base(i)+nice(i)+cpu(i)

其中base和nice值都是靜態固定的，可以由使用者指定的。

cpu是隨著進程佔用CPU時間越長權重就越低的調整因子，該因子調整邏輯如下：

cpu(i) = cpu(i-1)/2

也就是每次進程被選中排程一遍之後，下次對應的cpu因子的值都會被除以2，降低下次執行的權重。

新版排程演算法

核心2.6版本之後重寫了排程演算法。也叫O(1)演算法。

該演算法針對普通進程，設定了100~139共40個優先順序，進程屬於哪個優先順序的計算跟老版排程演算法類似。系統再儲存了一個點陣圖，每個點陣圖代表一個優先順序是否有等待的進程。然後每次都選擇優先順序最高的且有進程的那個佇列選取第一個進程來執行。

SMP的排程

對於多處理器的處理，跟上面的排程演算法類似，只是在選擇出進程之後，需要再判斷一下給哪個CPU合適。

一般來說，考慮到CPU的本地cache，所以盡量將進程排程到之前執行的CPU上執行。當然，考慮到CPU本身的均衡性，所以肯定還是會有遷移的工作。

執行緒相關

使用者執行緒&核心執行緒

執行緒從一開始誕生就有兩個分類：使用者級執行緒 和 核心級執行緒。

我們在Linux上常見的是核心級執行緒, 即執行緒排程相關操作都在核心裡實現, 不太常見的是使用者級執行緒。

使用者級執行緒的優勢是：

1. 執行緒切換成本低，不用核心操作
2. 使用者可以自定義執行緒排程策略
3. 跟作業系統無關，可以很快移植到另外一台機器上

但是使用者執行緒也有如下問題：

1. 一個執行緒的阻塞會影響其他執行緒，因為作業系統看不到別的執行緒
2. 不能很好的利用多核能力，因為作業系統會把一個核心進程放到一個CPU上

目前Linux上只使用核心級執行緒, Solaris上面兩者都提供。

執行緒切換

一個進程的上下文主要有如下幾個部分的資訊構成：

1. 程式計數器
2. 暫存器資訊
3. 棧資訊

一個進程切換的過程包含：

1. 儲存當前進程的上下文
2. 將當前進程加入作業系統對應佇列
3. 通過排程演算法選擇另外一個進程
4. 調整虛存對映
5. 載入新進程的上下文

但是執行緒切換就不一樣了，之需要切換PC暫存器指向的程式碼地址就好，其他操作都不用做，所以執行緒切換的成本比進程切換低多了。

互斥和同步

簡介

當多個進程需要對同一個資源進行存取的時候, 為了避免同時使用這個資源造成的混亂, 所以需要考慮進程間的互斥。

典型的互斥實現方案如下:

方案	介紹
中斷禁用	殺敵一千, 自損八百。雖然能實現互斥, 但是大大降低了處理器的執行效率。而且再多處理器體系結構中, 他還不能達到互斥
專用機器指令	往往是通過一個不可中斷的指令, 用於原子修改記憶體中的值, 常見的兩個指令是testset和exchange, 其對應的demo程式碼如下圖。該方案的好處是實現簡單, 壞處是使用了忙等待, 可能出現飢餓, 可能死鎖, 需要作業系統層進行管理和避免

死鎖的避免

死鎖出現有4個必要條件:

1. 互斥: 資源只能同時被一個進程使用
2. 佔有且等待: 一個進程在等待別的資源的時候, 將繼續佔有其擁有的資源
3. 非搶佔: 不能強行搶占別人佔有的資源
4. 迴圈等待: 在滿足如上3個條件的情況下, 出現迴圈等待即出現死鎖

要避免死鎖也是從這4個條件上下手:

1. 互斥: 這個是為了資源功能正常運轉, 無法避免
2. 佔有且等待: 讓進程一開始就申請所有資源才能執行。問題是效率低下, 進程可能要等待很長時間, 資源可能被控制很長時間, 程式也需要最開始就知道需要使用哪些資源;
3. 非搶佔: 根據進程優先順序讓申請資源的進程釋放自己之前擁有的資源或者搶佔別的進程的資源, 靠譜, 唯一的問題在於資源的使用不一定有那麼容易的儲存和恢復(很多硬體不像處理器那樣可以隨意切換使用進程的)
4. 迴圈等待: 給資源定義一個序列, 進程只能按照序列申請資源, 會導致進程執行效率大大降低, 所以主流做法是如下兩種

如上幾種避免辦法都有各種各樣的問題, 所以一般不採用, 現在採用最多的方案還是從第4點出發, 只不過不預先避免, 而是動態探測:

1. 如果一個進程啟動或者新增資源需求會導致死鎖, 則不允許此分配

   典型的演算法如銀行家演算法, 此方法的弊端是需要知道一個進程將來所需要佔用的資源

2. 允許所有請求, 週期性的進行檢測死鎖

   動態檢測, 執行效率高, 但是如果出現死鎖頻率比較高, 則系統執行效率會比較低。

綜合所有的死鎖避免的方法的對比如下:

程式設計介面

多進程之間的互斥與同步方案有了如上提到的系列硬體支援之後, 就需要考慮作業系統對有並行程式設計的程式設計師們提供的程式設計介面了。

號誌

號誌是在記憶體中維護了一個int, 每次操作對該int進行++或者--。

對操作者提供了兩個介面:

1. semWait

   該介面檢查int值, 如果該值大於0, 就將該值--, 並進入臨界區; 否則就阻塞檢測該值知道大於0;

2. semSignal

   該介面將int值++, 並通知受阻的所有進程。通知哪個進程有的採用FIFO策略, 有的採用隨機策略。

管程

號誌的方式比較靈活, 讓程式設計師可以任意控制臨界區以及互動設計, 大部分現在程式也都採用了類似的方案, 這是一個相對底層但是功能強大的方案。

但是有人提出了號誌的操作分散, 在模組中任何位置都可能出現, 造成程式編寫和維護困難, 也容易出bug, 所以在70年代, 有人提出了管程的概念, 筆者在實際工作中尚未使用管程來實現進程間互斥和同步。

管程底層跟號誌類似, 只是他把所有加鎖解鎖的邏輯全部封裝在一個類裡面, 所有關於該臨界資源的操作都在這個類中以函數的方式呈現, 除了這個類之外其他任何地方都看不到鎖。這樣就實現了鎖相關邏輯集中在一個地方。

在一個類裡面可以有多把鎖, 跟號誌類似, 針對每把鎖, 在該類的函數裡可以用類似semWait和semSignal的介面等待該鎖或者釋放該鎖。

訊息傳遞

訊息傳遞的方式跟鎖又有些不一樣??, 因為進程間同步互斥不外乎就是阻塞和交換資訊兩類, 而訊息傳遞提供的API就是最底層的API, 把其他邏輯都交給了上層由程式設計師控制。

其提供的API如下:

1. send(destination, message)

   傳送請求

2. receive(source, message)

   接收請求

根據兩個介面是否阻塞, 一般又分成如下幾類:

1. send和receive都阻塞

   一般用於進程間緊密同步的時候使用

2. send不阻塞, receive阻塞

   比較常見的方式, send之後可以繼續做別的事情, 但是receive這頭在收到相關資訊之前, 必須阻塞直到相關資訊確認才能繼續。

3. send和receive都不阻塞

   比較少見。

一般現在在分散式系統涉及到跨機器寫作的時候, 會使用該方式來做進程間的同步和互斥。

本文永久更新連結地址：http://www.linuxidc.com/Linux/2015-08/122170.htm