1 進(jìn)程模型

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

1.1 進(jìn)程的狀態(tài)

進(jìn)程的基本狀態(tài)有以下三個(gè)：

• 運(yùn)行態(tài)：該時(shí)刻進(jìn)程正在占用CPU
• 就緒態(tài)：進(jìn)程可運(yùn)行棘捣，但因?yàn)槠渌M(jìn)程正在運(yùn)行而停止
• 阻塞態(tài)：除非某種外部事件發(fā)生，否則進(jìn)程不能運(yùn)行

進(jìn)程的狀態(tài)與轉(zhuǎn)換

如上圖休建，進(jìn)程在這三個(gè)狀態(tài)之間可以有四種可能的轉(zhuǎn)換關(guān)系:

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

1.2 進(jìn)程的實(shí)現(xiàn)模型

操作系統(tǒng)維護(hù)了一個(gè)進(jìn)程列表乍恐，進(jìn)程表里的每一項(xiàng)都是當(dāng)前啟動(dòng)的進(jìn)程對應(yīng)的進(jìn)程控制塊（PCB）。PCB中包含了進(jìn)程狀態(tài)的重要信息：程序計(jì)數(shù)器PC测砂，堆棧指針茵烈，內(nèi)存分配狀況，打開的文件狀態(tài)砌些，賬號信息呜投，調(diào)度信息等等加匈。

PCB中的一些字段

2. 線程

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

線程是一種輕量級的進(jìn)程。

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

進(jìn)程模型基于兩種獨(dú)立的概念：資源管理與執(zhí)行調(diào)度啥寇。引入了線程模型，將資源管理與執(zhí)行調(diào)度這兩個(gè)功能區(qū)分開來：進(jìn)程用于把所需資源集中到一起洒扎，而線程則是在CPU上被調(diào)度執(zhí)行的實(shí)體辑甜。

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

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

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

把整個(gè)線程包放在用戶空間中袍冷，內(nèi)核對線程包一無所知磷醋。從內(nèi)核角度考慮，就是單進(jìn)程單線程胡诗。線程在一個(gè)運(yùn)行時(shí)系統(tǒng)的頂部運(yùn)行邓线，這個(gè)運(yùn)行時(shí)系統(tǒng)是一個(gè)管理線程的過程的集合。每個(gè)進(jìn)程有其專用線程表（thread table）煌恢。

• 優(yōu)點(diǎn)：用戶線程包可以在不支持線程的操作系統(tǒng)上實(shí)現(xiàn)骇陈。不需要陷進(jìn)，不需要上下文切換症虑，不需要對內(nèi)存高速緩存進(jìn)行刷新，使得線程調(diào)度非彻檠Γ快谍憔。允許每個(gè)進(jìn)程有自己定制的調(diào)度算法。
• 問題：如何實(shí)現(xiàn)阻塞系統(tǒng)調(diào)用主籍，使用阻塞調(diào)用會阻塞其他的線程习贫。頁面故障問題，如果某個(gè)調(diào)用跳轉(zhuǎn)到了一條不在內(nèi)存的指令上千元，就會發(fā)生頁面故障苫昌，內(nèi)核由于不知道線程的存在，通常會把整個(gè)進(jìn)程阻塞到I/O完成幸海。如果一個(gè)線程開始運(yùn)行祟身，那么該進(jìn)程中的其他線程就不能運(yùn)行，除非第一個(gè)線程自動(dòng)放棄CPU物独。

2.2.2 在內(nèi)核中實(shí)現(xiàn)線程

此時(shí)不需要運(yùn)行時(shí)系統(tǒng)袜硫，內(nèi)核中有用來記錄系統(tǒng)中所有線程的線程表。當(dāng)一個(gè)線程阻塞時(shí)挡篓，內(nèi)核根據(jù)其選擇婉陷，可以運(yùn)行同一個(gè)進(jìn)程中的另一個(gè)線程或者運(yùn)行另一個(gè)進(jìn)程中的線程帚称。

• 優(yōu)點(diǎn)：內(nèi)核很容在線程阻塞時(shí)切換到另一個(gè)線程執(zhí)行。內(nèi)核線程不需要任何新的秽澳、非阻塞系統(tǒng)調(diào)用闯睹。
• 問題：在內(nèi)核中創(chuàng)建或銷毀線程的代價(jià)比較大。進(jìn)程創(chuàng)建問題担神，一個(gè)多線程進(jìn)程創(chuàng)建新進(jìn)程出現(xiàn)的問題楼吃。當(dāng)信號到達(dá)時(shí)，應(yīng)該由哪一個(gè)線程處理杏瞻。

2.2.3 混合實(shí)現(xiàn)

使用內(nèi)核線程所刀，然后將用戶級線程與某些或者全部內(nèi)核線程多路復(fù)用起來。內(nèi)核只識別內(nèi)核線程捞挥，并對其進(jìn)行調(diào)度浮创。一些內(nèi)核線程會被多個(gè)用戶級線程多路復(fù)用。這一模型能夠帶來最大的靈活度砌函。

3. 進(jìn)程間通信

進(jìn)程間通信（Inter Process Communication斩披，IPC）簡要的說有三個(gè)問題：

1. 一個(gè)進(jìn)程如何把信息傳遞給另一個(gè)。
2. 確保兩個(gè)或更多的進(jìn)程在關(guān)鍵活動(dòng)中不會出現(xiàn)交叉讹俊。
3. 保證進(jìn)程以正確的順序執(zhí)行垦沉。

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

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

3.2 互斥

互斥（mutual exclusion）：即以某種手段確保當(dāng)一個(gè)進(jìn)程在使用一個(gè)共享變量或文件時(shí)，其他進(jìn)程不能做同樣的操作这溅。

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

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

• Peterson解法：

  
  
  完成互斥的Peterson解法

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

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

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

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

3.3 信號量

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

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

如果不需要信號量的計(jì)數(shù)能力烙心，則可以使用信號量的一個(gè)簡化版本，稱為互斥量（mutex）乏沸∫穑互斥量實(shí)現(xiàn)簡單，常用于實(shí)現(xiàn)用戶空間線程包蹬跃〕妆瘢互斥量有兩個(gè)狀態(tài)：解鎖和加鎖。

互斥量的加鎖和解鎖操作

3.4 管程

管程（monitor）是一種高級同步原語蝶缀，是用來簡化程序和減少死鎖丹喻。一個(gè)管程是一個(gè)由過程，變量翁都，及數(shù)據(jù)結(jié)構(gòu)等組成的一個(gè)集合碍论，它們組成一個(gè)特殊的模塊或軟件包。管程是語言特性柄慰，C語言不支持鳍悠。Java中的管程是synchronized。

3.5 消息傳遞

上面的技術(shù)都是用來解決訪問公共內(nèi)存的一個(gè)或多個(gè)CPU上的互斥問題坐搔。但若無法共享內(nèi)存藏研，則無法使用上面的那些方法，因而需要使用消息傳遞（message passing）的方法來解決概行。消息傳遞使用send和receive兩條原語在進(jìn)程間通信蠢挡。

3.6 屏障

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

4 調(diào)度算法

當(dāng)多個(gè)進(jìn)程或線程同時(shí)競爭一個(gè)CPU是堡称，就需要操作系統(tǒng)來選擇下一個(gè)要運(yùn)行的進(jìn)程瞎抛，完成選擇工作的這一部分程序稱為調(diào)度程序（scheduler）艺演，該程序使用的算法稱為調(diào)度算法（scheduling algorithm）。

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

調(diào)度算法的目標(biāo)：

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

常用調(diào)度算法：

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

• 策略和機(jī)制分離原則：將調(diào)度算法以某種形式參數(shù)化认烁，而參數(shù)可以由用戶進(jìn)程填寫肿男。

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