進程與線程

進程

操作系統中最核心的概念是進程,是對正在運行程序的一個抽象。一個進程就是一個正在被執行程序的實例,包括程序計數器、寄存器和變量的當前值。

系統調用

根據進程訪問資源的特點,可以把進程在系統上的運行分為兩個級別:

  • 用戶態 (user mode): 用戶態運行的進程可以直接讀取用戶程序的數據。
  • 系統態 (kernel mode): 系統態運行的進程或程序幾乎可以訪問計算機的任何資源,不受限制。

進程 v.s. 程序

如果將操作系統內部視為一個廚房,則程序 (適當形式描述的算法) 相當于食譜,輸入的數據相當于食材,CPU 處理器等同于廚師。進程則是指某種類型的活動,比如廚師閱讀食譜,取食材以及烘焙等動作的總和。

進程上下文切換

若幹進程可以共享單個 CPU,單個 CPU 一次只能運行一個進程。處裏器在各個進程之間來回快速切換,在任何一個給定的瞬間僅有一個進程真正在運行。由于 CPU 在各個進程之間來回快速切換,所以每個進程執行及運算的速度是不確定的,當同一進程再次運行時,其運算速度通常不可再現。進程切換的基本順序如下:

  1. 保存當前進程狀態
  2. 切換到高優先級進程 (每個進程包含各自程序)
  3. 切換到原本進程 (從原本進度開始執行)

進程的層次結構

當進程創建了另一進程後,父進程和子進程就以某種形式繼續保持關聯。進程只可以有一個父進程,但是可以有零個、一個、兩個或多個子進程。舉例 UNIX 在啓動時如何初始化自己來說明進程層次的作用:

一個稱為 init 的特殊進程出現在啓動映像中。當他開始運行時,讀入一個說明終端數量的文件。接這,未每個終端創建一個新進程。這些進繩等待用戶登錄。如果有一個用戶登錄成功,該登陸進程就執行一個 shell 準備接收命令。所接收的這些命令會啓動更多的進程,以此累堆,在整個系統中,所以的進程都屬于以 init 為根的一棵樹。

進程的狀態

Process State

  • 創建態 (new): 進程正在被創建,未達到就緒態。四種事件會導致進程創建:

    1. 系統初始化

    2. 正在運行的程序執行創建進程的系統調用

    3. 用戶請求創建一個新進程

    4. 一個批處理作業的初始化

  • 就緒態 (ready): 可運行,但因位其他進程正在運行而戰時終止,一旦得到處裏器資源 (處裏器的時間片) 即可運行。

  • 運行態 (running): 進程實際占用 CPU (單核 CPU 任意時刻只有一個進程處于該狀態)。

  • 阻塞態 (waiting): 又稱為等待狀態,除非某外部事件 (資源可用或 IO 操作完成) 發生,否則即使處裏器空閑,進程也不能運行。

  • 結束態 (terminated): 進程正在從系統上消失,可能是進程正常結束或其他原因造成中斷。四種事件會導致進程終止:

    1. 正常退出(自願)
    2. 出錯退出(自願)
    3. 嚴重錯誤(非自願)
    4. 被其他進程殺死(非自願)

進程的實現

為實現進程模型,操作系統維護著一張表格 (數組 or 鏈表結構),即進程表 (process table)。每個進程占用一個進程表項。該表象包含了進程狀態的重要信息,包括寄存器、程序計數器、堆棧指針和優先級等以及其他在進程由運行態轉換到就緒態或阻塞態時必須保存的信息,從而保證甘進程隨後能再次啓動,就像從未被中斷過一樣。

了解進程表後,就可以對在 CPU 上如何維持多個順序進程的錯覺進行更多的闡述。與每一 I/O 淚關聯的是一個稱作中斷向量 (interrupt vector)的位置。它包含中斷服務程序的入口地址。假設當一個磁盤中斷發生時,某用戶進程正在運行,則中斷硬件將程序計數器、程序狀態字和寄存器等壓入堆棧,計算機隨即跳轉到中段向量所指示的地址。

以下為中斷發生後操作系統最底層的工作順序:

  1. 硬件壓入堆棧程序計數器等

  2. 硬件從中斷向量裝入新的程序技術器

  3. 彙編語言過程保存寄存器值

  4. 彙編語言過程設置新的堆棧

  5. C中斷服務例程運行

  6. 調度程序決定下一個將運行的進程

  7. C過程返回至彙編代碼

  8. 彙編語言過程開始運行新的當前進程

線程

需要線程的主要原因:

  1. 在許多應用中同時發生著多種活動。其種某些活動隨著時間的推移會被阻塞。通過將這些應用程序分解成可以準並行的多個線程,程序設計會更加簡單。
  2. 由于線程比進程更輕量級,所以他們比進程更快更容易創建,也更容易撤銷。
  3. 性能問題。多個線程都是 CPU 密集型的,那麽並不能獲得性能上的增強,但是如果存在這大量的計算和大量的 I/O 處裏,擁有多個線程允許這些活動彼此重疊進行,從而加快應用程序執行的速度。

進程 v.s. 線程

線程是進程劃分成更小的運行單位,一個進程在其執行的過程中可以産生多個線程。線程和進程最大的不同在于基本上各進程是獨立的,而各線程則不一定,因為同一進程中的線程有可能會互相影響 (沒有保護),多個線程可以共享公共內存,對彼此進行讀寫。進程執行開銷大,但利于資源的管理與保護,線程則相反。

多線程

線程給進程模型中增加了一項內容,即在同一進程環境中,允許彼此之間有較大獨立性的多個線程執行。在同一進程中並行運行多個線程 (多個線程共享同一各地址空間和資源),是對在同一計算機上並行運行多個進程 (多個進程共享物理內存、磁盤等資源)的模擬。多線程是用來描述在同一各進程中允許多個線程的情形 (允許線程切換在納秒級完成)。

線程狀態

Thread State

  • 創建 (New): 創建線程
  • 就緒 (Ready): 可以被調度執行
  • 運行 (Running): 擁有 CPU 並且是活躍的
  • 阻塞 (Blocking): 等待某個釋放它的事件
  • 終止 (Dead): 不可被調度執行

進程間通信 (Inter Process Communication, IPC)

進程間通信主要需要解決三個問題:

  1. 一個進程如何把信息傳遞給另一個
  2. 確保兩個或更多的進程在關鍵活動中不會出現交叉
  3. 保證線程的正確順序

競爭條件

兩個或多個進程讀寫某些共享數據,而最後的結果取決于進程運行的時序,稱為競爭條件 (race condition)。比如一機器有許多槽位並且進程 A 與進程 B 開始如下操作:

  1. 進程 A 先運行,發現槽位3為空並且進行標記,此時發生時鍾中斷, CPU 認為 A 已經運行足夠長時間,決定切換到進程 B 運行。
  2. 進程 B 運行,同樣發現槽位3為空並且進行標記。
  3. 進程 B 繼續運行,將文件存儲到槽位3。
  4. 進程 A 接著從上次中斷的地方開始運行,同樣將文件存儲到槽位3,覆蓋掉 B 的文件。
  5. 此結果將會造成 B 永遠得不到結果。

臨界區

對共享內存進行訪問的程序片段稱為臨界區域 (critical region)臨界區 (critical section) 。要避免競爭條件,需要滿足以下四個條件:

  1. 任何兩個進程不能同時處于其臨界區
  2. 不對 CPU 的速度和數量作任何假設
  3. 臨界區外運行的進程不得阻塞其他進程
  4. 不得使進程無限期等待進入臨界區

忙等待的互斥

要避免造成上述錯誤,要找出某種途徑來阻止多個進程同時寫共享數據,即確保當一個進程在使用一個共享變量或文件時,其他進程不能做同樣的操作 or 不會進入臨界區,該動作稱為互斥 (mutual exclusion)。要實現互斥有以下幾種方案:

  1. 屏蔽中斷: 每個進程在進入臨界區後立即屏蔽所有中斷,並在要離開之前再打開中斷。屏蔽中斷後,時鍾中斷也會被屏蔽。CPU 只有發生時鍾中斷或其他中斷時才會進行進程切換,代表在屏蔽中斷之後 CPU 將不會被切換到其他進程。這樣一但某個進程屏蔽中斷之後,它就可以檢查和修改共享內存,而不必擔心其他進程介入。屏蔽中斷對于操作系統本身而言是一項很有用的技術,但對于用戶進程不是一種合適的互斥機制。

  2. 鎖變量: 設0表示臨界區內沒有進程,1表示已經有某個進程進入臨界區。一個共享 (鎖) 變量,其初始值為0,當一個進程想進入其臨界區時,它首先測試這把鎖,如果鎖值為0,則該進程將其設置為1並進入臨界區。若這把鎖的值已經為1,則該進程將等待直到其值變為0。

  3. 嚴格輪換法: 該方案要求兩個進程嚴格地輪流進入臨界區,任何一各進程都不可能在一輪中執行兩次。設整型變量 turn 初始值為0,用于記錄輪到哪個進程進入臨界區,並檢查或更新共享內存。開始時,進程0檢查 turn, 發現值為0,于是進入臨界區。進程1也發現其值為0,所以在一個等待循環中不停地測試 turn, 看其值何時變為1。

連續測試一個變量到某個值出現為止,稱為忙等待 (busy waiting)。由于這種方式浪費 CPU 時間,所以通常應該避免。只有在有理由認為等待時間是非常短的情形下,才使用忙等待。用于忙等待的鎖稱為自旋鎖 (spin lock),也是互斥鎖的一種表現形式

盡管該算法避免了所有的競爭條件,但由于違反了條件3 – 臨界區外運行的進程不得阻塞其他進程,所以不能作為一個很好的備選方案。

  1. Peterson 解法: 在使用共享變量 (即進入臨界區) 之前,各疙進程使用其進程號0或1作為參數來調用 enter_region。該調用在需要時將使進程等待。直到能安全地進入臨界區。在完成對共享變量的操作之後,進城將調用 leave_region,表示操作以完成,若其他的進程希望進入臨界區,現在就可以進入。

  2. TSL 指令: 該方案需要硬件支持。某些計算機中,特別是那些設計為多處裏器的計算機,都有一條指令: TSL RX, LOCK,稱為測試並加鎖 (test and set lock),它將一個內存字 lock 讀到寄存器 RX 中,然後再該內存地址上存一個非零值。讀字和寫字操作保證是不可分割的,即該指令結束之前其他處裏器均不允許訪問該內存字。執行 TSL 指令的 CPU 將鎖住內存總線,以禁止其他 CPU 在本指令結束之前訪問內存。與屏蔽中斷不同的是,屏蔽中斷無法阻止處裏器2在處裏器1的讀操作與寫操作之間訪問內存字,鎖住存儲總線則可以。

睡眠 (sleep) 與喚醒 (wakeup)

Peterson 解法與 TSL 解法都是正確的,但他們都有忙等待的缺點,他們本質上是這樣的,當一個進程想進入臨界區時,先檢查是否允許進入,若不允許,則該進程將原地等待,直到允許為止。這種方法不僅浪費 CPU 時間,而且還可能引起優先級反轉問題 (priority inversion problem)

優先級反轉問題 (priority inversion problem): 考慮一台計算機有兩個進程,A進程優先級較高,B較低。調度規則規定,只要A處于就緒態它就可以運行。在某一時刻,B處于臨界區中,此時A變到就緒態,準備運行。現在A開始忙等待,但由于當A就序時B不會被調度,也就無法離開臨界區,所以A將永遠忙等待下去。

接下來則引入 sleepwakeup,他們在進程無法進入臨界區時將其阻塞,而非忙等待。

生産者 - 消費者 (producer-consumer) 問題
兩個進程共享一個公共的固定大小的緩衝區,其中一個是生産者,將信息放入緩衝區,另一個是消費者,從緩衝區中取出信息。當緩衝區已滿,而此時生産者還想向其中放入一個新的數據項的情況。其解決辦法是讓生産者睡眠 (sleep),待消費者從緩衝區中取出一個或多個數據項時再喚醒它,反之亦然。

信號量 (semaphore)

信號量是一個計數器,有相較于互斥量更多的取值空間。不單單可以實現線程間的互斥,更可以用于較為複雜的進程同步 (synchronization,亦可稱為同步鎖的一種)。這種通信方式主要用于解決與同步相關的問題並避免競爭條件。

互斥量 or 互斥鎖 (mutex)

信號量的簡化版本,可以說是信號量再僅取值 0/1 時的特例,僅適用于管理共享資源或一小段代碼。互斥量是一個可以處于兩態之一的變量: 解鎖或加鎖 (二元鎖機制)。當一個線程 (或進程) 需要訪問臨界區時,調用 mutex_lock。如果該互斥量當前是解鎖的 (即臨界區可用),此調用成功,調用線程可以自由進入該臨界區。如果該互斥量已經加鎖,調用線程將被阻塞,直到再臨界區中的線程完成並調用 mutex_unlock。如果多個線程被阻塞再該互斥量上,將隨機選擇一個線程並允許它獲得鎖。采用互斥對象機制,只有擁有互斥對象的線程才有訪問公共資源的權限。因為互斥對象只有一個,所以可以保證公共資源不會被多個線程同時訪問

調度

對調度的定義如下:

當計算機系統是多道程序設計系統時,通常就會有多個進程或線程同時競爭 CPU。指要有兩個或更多的進程處于就緒狀態,這種情形就會發生。如果只有一個 CPU 可用,那麽就必須選擇下一個要運行的進程。再操作系統中,完成選擇工作的這一部份稱為調度程序 (scheduler),該程序使用的算法稱為調度算法 (scheduling algorithm)

盡管有些不同,但許多適用于進程調度的處裏方法同樣也是用于線程調度。

何時調度

需要調度處裏的各種情形:

  1. 在創建一個新進程之後,需要決定是運行父進程還是子進程

  2. 在一個進程退出時必須做出調度決策

  3. 當一個進程阻塞在 I/O 和信號量上或由于其它原因阻塞時,必須選擇另一個進程運行

  4. 在一個 I/O 中斷發生時,必須做出調度決策

如果硬件時中提供周期性中斷,可以在每個或 n 個時鍾中斷時做出調度決策。根據如何處裏時鍾中斷,可以把調度算法分為兩大類:

  • 非搶占式: 挑選一個進程,然後讓進程運行直至被阻塞或釋放 CPU。即使該進程運行很久,它也不會被強迫挂起。這樣做的結果是,在時鍾中斷發生時不會進行調度。在處裏完時鍾中斷後,如果沒有更高優先級的進程等待,則被中斷的進程會繼續執行。

  • 搶占式: 挑選一個進程,並且讓該進程運行某個固定時段的最大值,如果該時段結束時,該進程仍在運行,他就被挂起,而調度程序挑選另一個進程運行。

常見進程調度算法

  • 先到先服務 (First Come First Served, FCFS): 從就緒隊列中選擇一個最先進入該隊列的進程為其分配資源,使它立即執行並一直執行到完成或發生某事件而被阻塞,放棄占用 CPU 時再重新調度。
  • 最短作業優先 (Shortest Job First, SJF): 從就緒隊列中選出一個估計運行時間最短的進程為其分配資源,使它立即執行並一直執行到完成或發生某事件而被阻塞,放棄占用 CPU 時再重新調度。
  • 最短剩余時間優先 (Shortest Remaining Time First, SRTS): 調度程序總是選擇剩余運行時間最短的那個進程運行。
  • 時間片輪轉調度 (Round-Robin, RR): 最古老,最簡單,最公平且使用最廣的算法,每個進程被分配一個時間段,稱作它的時間片,即該進程允許運行的時間。
  • 優先級調度 (Priority Based Scheduling): 為每個流程分配優先級,首先執行具有最高優先級的進程。具有相同優先級的進程以 FCFS 的方式執行。可以根據內存要求,時間要求或任何其他資源要求來確定優先級。
  • 多級反饋隊列調度算法 (Multi-level Feedback Queue, MFQ): 該算法既能使高優先級的作業得到響應又能使短作業 (進程) 迅速完成,因而他是目前被公認的一種較好的進程調度算法,UNIX 便是采用這種算法
  • 最短進程優先 (Shortest Process First, SPF): 優先運行最短的作業以達到響應時間最短,該算法雖然照顧了短進程卻忽略了長進程。
  • 彩票調度 (Lottery Scheduling): 向進程提供各種系統資源 (如 CPU 時間) 的彩票 (可以給重要的進程額外的彩票)。一旦需要做出一項調度決策時,就隨機收出一張彩票,擁有該彩票的進程獲得該資源。
  • 公平共享調度 (Completely Fair Scheduling): 在調度處裏之前考慮誰擁有該進程。在這種模式下,每個進程分配到 CPU 時間的一部份,而調度程序以一種強制的方式選擇進程。如果兩個用戶都得到 50% 的 CPU 時間保證,那麽無論一個用戶有多少進程存在,每個用戶都會得到應有的 CPU 份額。