1 進程模型

進程是對正在運行程序的一個抽象。一個進程就是一個正在執(zhí)行程序的實例，包括程序計數(shù)器，寄存器和變量。每個進程都擁有它自己的虛擬CPU，實際上真正的CPU在進程之間來回切換。對于單核CPU，或者多核CPU的一個核，在同一時刻只能運行一個進程。單個處理器可以被若干進程共享，它使用某種調度算法決定何時停止一個進程的工作，并轉而為另一個進程提供服務。

1.1 進程的狀態(tài)

進程的基本狀態(tài)有以下三個：

• 運行態(tài)：該時刻進程正在占用CPU
• 就緒態(tài)：進程可運行，但因為其他進程正在運行而停止
• 阻塞態(tài)：除非某種外部事件發(fā)生，否則進程不能運行

進程的狀態(tài)與轉換

如上圖，進程在這三個狀態(tài)之間可以有四種可能的轉換關系:

1. 進程為等待輸入而阻塞
2. 調度程序選擇另一個進程
3. 調度程序選擇這個程序
4. 出現(xiàn)有效輸入

1.2 進程的實現(xiàn)模型

操作系統(tǒng)維護了一個進程列表，進程表里的每一項都是當前啟動的進程對應的進程控制塊（PCB）。PCB中包含了進程狀態(tài)的重要信息：程序計數(shù)器PC，堆棧指針，內存分配狀況，打開的文件狀態(tài)，賬號信息，調度信息等等。

PCB中的一些字段

2. 線程

2.1 線程的實現(xiàn)模型

線程是一種輕量級的進程。

• 多個線程擁有共享同一個地址空間和所有可用數(shù)據(jù)的能力。
• 線程比進程更容易創(chuàng)建和銷毀。
• 在大量計算和大量I/O處理過程中，多個線程能夠加快程序執(zhí)行速度。

進程模型基于兩種獨立的概念：資源管理與執(zhí)行調度。引入了線程模型，將資源管理與執(zhí)行調度這兩個功能區(qū)分開來：進程用于把所需資源集中到一起，而線程則是在CPU上被調度執(zhí)行的實體。

2.2 線程的三種實現(xiàn)

操作系統(tǒng)將運行環(huán)境區(qū)分為用戶空間和內核。因此線程可以被創(chuàng)建到不同運行環(huán)境：

2.2.1 在用戶空間中實現(xiàn)

把整個線程包放在用戶空間中，內核對線程包一無所知。從內核角度考慮，就是單進程單線程。線程在一個運行時系統(tǒng)的頂部運行，這個運行時系統(tǒng)是一個管理線程的過程的集合。每個進程有其專用線程表（thread table）。

• 優(yōu)點：用戶線程包可以在不支持線程的操作系統(tǒng)上實現(xiàn)。不需要陷進，不需要上下文切換，不需要對內存高速緩存進行刷新，使得線程調度非常快。允許每個進程有自己定制的調度算法。
• 問題：如何實現(xiàn)阻塞系統(tǒng)調用，使用阻塞調用會阻塞其他的線程。頁面故障問題，如果某個調用跳轉到了一條不在內存的指令上，就會發(fā)生頁面故障，內核由于不知道線程的存在，通常會把整個進程阻塞到I/O完成。如果一個線程開始運行，那么該進程中的其他線程就不能運行，除非第一個線程自動放棄CPU。

2.2.2 在內核中實現(xiàn)線程

此時不需要運行時系統(tǒng)，內核中有用來記錄系統(tǒng)中所有線程的線程表。當一個線程阻塞時，內核根據(jù)其選擇，可以運行同一個進程中的另一個線程或者運行另一個進程中的線程。

• 優(yōu)點：內核很容在線程阻塞時切換到另一個線程執(zhí)行。內核線程不需要任何新的、非阻塞系統(tǒng)調用。
• 問題：在內核中創(chuàng)建或銷毀線程的代價比較大。進程創(chuàng)建問題，一個多線程進程創(chuàng)建新進程出現(xiàn)的問題。當信號到達時，應該由哪一個線程處理。

2.2.3 混合實現(xiàn)

使用內核線程，然后將用戶級線程與某些或者全部內核線程多路復用起來。內核只識別內核線程，并對其進行調度。一些內核線程會被多個用戶級線程多路復用。這一模型能夠帶來最大的靈活度。

3. 進程間通信

進程間通信（Inter Process Communication，IPC）簡要的說有三個問題：

1. 一個進程如何把信息傳遞給另一個。
2. 確保兩個或更多的進程在關鍵活動中不會出現(xiàn)交叉。
3. 保證進程以正確的順序執(zhí)行。

3.1 競爭條件與臨界區(qū)

在一些操作系統(tǒng)中，協(xié)作的進程可能共享一些彼此都能讀寫的公用存儲區(qū)。兩個或多個進程讀寫某些共享數(shù)據(jù)，而最后的結果取決于進程運行的精確時序，稱為競爭條件（race condition）。我們把對共享內存進行訪問的程序片段稱作臨界區(qū)（critical region/section）。

3.2 互斥

互斥（mutual exclusion）：即以某種手段確保當一個進程在使用一個共享變量或文件時，其他進程不能做同樣的操作。

實現(xiàn)忙等待的互斥（即CPU輪詢等待）：

• 屏蔽中斷 ： 不適合多核CPU
• 鎖變量：無效
• 嚴格輪換法：無效

• Peterson解法：

  
  
  完成互斥的Peterson解法

• TSL指令：test and set lock，是CPU級別的原子指令，即該指令結束之前，其他處理器不允許訪問該內存。執(zhí)行TSL指令的CPU將鎖住內存總線，需要硬件支持。

  
  
  用TSL指令進入和離開臨界區(qū)

由于忙等待會浪費CPU資源，而且會產(chǎn)生優(yōu)先級反轉問題，所以一般會使用sleep和wakeup這兩個系統(tǒng)調用。以下是使用了這兩個系統(tǒng)調用后的生產(chǎn)者-消費者問題示例：

生產(chǎn)者-消費者問題

3.3 信號量

信號量（semaphore）是Dijkstra在1965年提出的一種方法，使用一個整型變量來累計喚醒次數(shù)。使用兩種操作：down和up來修改信號量。修改信號量的操作是原子操作。

使用信號量實現(xiàn)的生產(chǎn)者-消費者問題

如果不需要信號量的計數(shù)能力，則可以使用信號量的一個簡化版本，稱為互斥量（mutex）?；コ饬繉崿F(xiàn)簡單，常用于實現(xiàn)用戶空間線程包。互斥量有兩個狀態(tài)：解鎖和加鎖。

互斥量的加鎖和解鎖操作

3.4 管程

管程（monitor）是一種高級同步原語，是用來簡化程序和減少死鎖。一個管程是一個由過程，變量，及數(shù)據(jù)結構等組成的一個集合，它們組成一個特殊的模塊或軟件包。管程是語言特性，C語言不支持。Java中的管程是synchronized。

3.5 消息傳遞

上面的技術都是用來解決訪問公共內存的一個或多個CPU上的互斥問題。但若無法共享內存，則無法使用上面的那些方法，因而需要使用消息傳遞（message passing）的方法來解決。消息傳遞使用send和receive兩條原語在進程間通信。

3.6 屏障

屏障（barrier） 是適用于一組進程的同步機制。在應用中將程序劃分成若干段，且規(guī)定除非所有進程都就緒準備進入下一個階段，否則任何進程都不能進入下一個階段。通過在每個階段結尾安置屏障來實現(xiàn)這種行為。

4 調度算法

當多個進程或線程同時競爭一個CPU是，就需要操作系統(tǒng)來選擇下一個要運行的進程，完成選擇工作的這一部分程序稱為調度程序（scheduler），該程序使用的算法稱為調度算法（scheduling algorithm）。

• 進程行為分為兩種：計算密集型和I/O密集型
• 進程調度的時機：
  • 創(chuàng)建新進程時，需要決定是運行父進程還是運行子進程
  • 在一個進程推出時，需要作出調度決策
  • 當進程阻塞在I/O和信號量上或其他原因阻塞時，必須選擇另一個進程運行
  • 在一個I/O中斷發(fā)生時，必須做出調度決策
• 進程調度運行環(huán)境分類：批處理、交互式、實時

調度算法的目標：

• 所有系統(tǒng)：
  • 公平：給每個進程公平的CPU份額
  • 策略強制執(zhí)行：保證規(guī)定的策略被執(zhí)行
  • 平衡：保持系統(tǒng)的所有部分都忙碌
• 批處理系統(tǒng)
  • 吞吐量：每小時最大作業(yè)數(shù)
  • 周轉時間：從提交到終止間的最小時間
  • CPU利用率：保持CPU始終忙碌
• 交互式系統(tǒng)
  • 響應時間：快速響應請求
  • 均衡性：滿足用戶的期望
• 實時系統(tǒng)：
  • 滿足截止時間：避免丟失數(shù)據(jù)
  • 可預測性：在多媒體系統(tǒng)中避免品質降低

常用調度算法：

• 批處理
  • 先來先服務
  • 最短作業(yè)優(yōu)先
  • 最短剩余時間優(yōu)先
• 交互式
  • 輪轉調度
  • 優(yōu)先級調度
  • 多級隊列
  • 最短進程優(yōu)先
  • 保證調度
  • 彩票調度
  • 公平分享調度
• 實時
  • 判斷是否可以在指定時間執(zhí)行完所有任務

• 策略和機制分離原則：將調度算法以某種形式參數(shù)化，而參數(shù)可以由用戶進程填寫。

參考： 《現(xiàn)代操作系統(tǒng)》第4版