進程

進程模型

操作系統(tǒng)中最核心的概念是進程：這是對正在運行程序的一個抽象汰聋。
一個進程就是一個正在執(zhí)行程序的實例乾吻，包括程序計數(shù)器枯饿、寄存器和變量的當(dāng)前值擒权。

在多道程序設(shè)計中，一個CPU能在多個進程之間來回快速切換，達到（偽）并行效果爷光。

一個進程是某種類型的一個活動，它有程序、輸入回懦、輸出以及狀態(tài)贫贝。
單個處理器可以被若干進程共享客燕，它使用某種調(diào)度算法決定何時停止一個進程的工作傍妒，并轉(zhuǎn)而為另一個進程提供服務(wù)驱负。

進程創(chuàng)建

以下四種事件可以觸發(fā)進程創(chuàng)建：

• 系統(tǒng)初始化
• 執(zhí)行了正在運行的進程所調(diào)用的進程創(chuàng)建系統(tǒng)調(diào)用（syscall）
• 用戶請求創(chuàng)建一個新進程
• 一個批處理作業(yè)的初始化。

新進程一般都是由于一個已存在的進程執(zhí)行了創(chuàng)建進程的系統(tǒng)調(diào)用而創(chuàng)建咧七。

進程終止

以下四種事件可以觸發(fā)進程終止：

• 正常退出（自愿的） ：進程正常完成其工作而終止任斋。
• 出錯退出（自愿的） ：比如用戶輸入命令行時继阻，輸入一個錯誤參數(shù)等耻涛。
• 嚴重錯誤（非自愿的）: 出現(xiàn)非法指令，引用不存在的內(nèi)存瘟檩，除數(shù)為零時抹缕，段錯誤（page fault）等等。
• 被其他進程殺死（非自愿的）：其讓他進程通過調(diào)用系統(tǒng)調(diào)用墨辛，kill掉進程卓研。

進程層次

在UNIX中。一個進程和它創(chuàng)建的進程（即子進程）構(gòu)成了一顆進程樹睹簇，如下圖奏赘。
UNIX在啟動時會先運行一個init進程，由init進程創(chuàng)建新進程太惠，最終形成了進程樹磨淌，所以在整個系統(tǒng)中，所有的進程都是以init為根節(jié)點的進程樹的成員凿渊。

每個進程和它的子進程共同組成一個進程組梁只。發(fā)給該進程組的信號可以被進程組中的進程分別捕捉。

image

進程狀態(tài)

• 運行態(tài)（此進程實際占用CPU）
• 就緒態(tài)（可運行埃脏，但因其他進程正在運行而暫時停止）
• 阻塞態(tài)（除非某種外部事件發(fā)生搪锣，否則進程不能運行）

image

進程的實現(xiàn)

系統(tǒng)（一般是內(nèi)核）維護著一張進程表（process table）。
每個進程占一個表項彩掐，即進程控制塊（Process Control Block）构舟。
進程控制塊（PCB）包含了進程狀態(tài)的重要信息。如下

image

利用PCB可以在發(fā)生中斷時把進程狀態(tài)的相關(guān)信息記錄下來堵幽，讓下次運行該進程的時的狀態(tài)與上次中斷時的狀態(tài)一致旁壮。就如下圖的過程1。

image

線程

線程模型

進程的模型可以歸納為

• 資源分組處理
• 執(zhí)行

資源分組處理的體現(xiàn)就是進程控制塊（Process Control Block）谐檀。
執(zhí)行的體現(xiàn)就是線程抡谐。

進程與線程的關(guān)系可以在下圖體現(xiàn)：

image

下面這個圖展示出了線程共享和線程獨占的內(nèi)容。

image

線程和進程的區(qū)別

• 調(diào)度 ：在引入線程的操作系統(tǒng)中桐猬，線程是調(diào)度和分配的基本單位 麦撵，進程是資源擁有的基本單位 。把傳統(tǒng)進程的兩個屬性分開溃肪，線程便能輕裝運行免胃，從而可顯著地提高系統(tǒng)的并發(fā)程度。 在同一進程中惫撰，線程的切換不會引起進程的切換羔沙；在由一個進程中的線程切換到另一個進程中的線程時，才會引起進程的切換厨钻。

• 并發(fā)性 ：在引入線程的操作系統(tǒng)中扼雏，不僅進程之間可以并發(fā)執(zhí)行坚嗜，而且在一個進程中的多個線程之間亦可并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性诗充，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量苍蔬。

• 擁有資源 ：不論是傳統(tǒng)的操作系統(tǒng)，還是設(shè)有線程的操作系統(tǒng)蝴蜓，進程都是擁有資源的一個獨立 單位碟绑，它可以擁有自己的資源。 一般地說茎匠，線程自己不擁有系統(tǒng)資源（只有一些必不可少的資源）格仲，但它可以訪問其隸屬進程的資源。

• 系統(tǒng)開銷： 由于在創(chuàng)建或撤消進程時诵冒，系統(tǒng)都要為之分配或回收資源抓狭，因此，操作系統(tǒng)所付出的開銷將顯著地大于在創(chuàng)建或撤消線程時的開銷造烁。 進程切換的開銷也遠大于線程切換的開銷否过。

線程實現(xiàn)

兩種方法：

• 在用戶空間

• 在內(nèi)核空間

  
  
  image

用戶級線程

基本結(jié)構(gòu)：

• 整個操作系統(tǒng)分為兩個部分，內(nèi)核空間和用戶空間惭蟋，進程當(dāng)時是分布在內(nèi)核空間中苗桂，在進程內(nèi)部定義一個運行時系統(tǒng)，這個運行時系統(tǒng)維護線程管理過程告组，多線程運行在這個運行時系統(tǒng)的基礎(chǔ)之上煤伟。
• 每個進程有其專用的線程表，用來跟蹤該進程中的線程木缝。該表由運行時系統(tǒng)管理便锨。當(dāng)線程阻塞后，進程調(diào)用一個運行時系統(tǒng)的過程來檢測是否需要進入阻塞我碟。如果是則放案，它在線程表中保存狀態(tài)信息，查看表中的就緒線程矫俺，并試圖啟動它吱殉。

優(yōu)點：

• 可以在不支持線程的操作系統(tǒng)上實現(xiàn)。
• 由于線程調(diào)度時不需要陷入內(nèi)核厘托，調(diào)用都是本地調(diào)用友雳，速度要比內(nèi)核實習(xí)的快一個數(shù)量級左右
• 允許每個進程有自己定制的調(diào)度算法。

缺點：

• 一個線程陷入阻塞铅匹，就意味著所屬進程的所有線程都阻塞了押赊。
• 因為線程調(diào)度不進入內(nèi)核，所以無法獲取時鐘中斷包斑，所以進程內(nèi)的一個線程不主動放棄CPU流礁，同進程的其他線程是無法獲取CPU使用權(quán)的涕俗。

內(nèi)核級線程

基本結(jié)構(gòu)：

• 線程的創(chuàng)建、撤銷和切換等崇棠，都需要內(nèi)核直接實現(xiàn)，即內(nèi)核了解每一個作為可調(diào)度實體的線程丸卷。
• 這些線程可以在全系統(tǒng)內(nèi)進行資源的競爭枕稀。
• 內(nèi)核空間內(nèi)為每一個內(nèi)核支持線程設(shè)置了一個線程控制塊（PCB），內(nèi)核根據(jù)該控制塊谜嫉，感知線程的存在萎坷，并進行控制。
• 在一定程度上類似于進程沐兰，只是創(chuàng)建哆档、調(diào)度的開銷要比進程小。有的統(tǒng)計是1：10

優(yōu)點：

• 不需要任何新的住闯、非阻塞的系統(tǒng)調(diào)用瓜浸；
• 當(dāng)有多個處理機時，一個進程的多個線程可以同時執(zhí)行比原。

缺點：

• 由內(nèi)核進行調(diào)度插佛，如果線程的操作比較多，就會帶來很大的開銷量窘。

進程間通信

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

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

進程間通信的方式

無名管道

• 它是半雙工的（即數(shù)據(jù)只能在一個方向上流動），具有固定的讀端和寫端冬殃。

• 它只能用于具有親緣關(guān)系的進程之間的通信（也是父子進程或者兄弟進程之間）囚痴。

• 它可以看成是一種特殊的文件，對于它的讀寫也可以使用普通的read审葬、write 等函數(shù)渡讼。但是它不是普通的文件，并不屬于其他任何文件系統(tǒng)耳璧，并且只存在于內(nèi)存中成箫。

  
  
  image

命名管道(FIFO)

它是一種文件類型。

• FIFO可以在無關(guān)的進程之間交換數(shù)據(jù)旨枯，與無名管道不同蹬昌。

• FIFO有路徑名與之相關(guān)聯(lián)，它以一種特殊設(shè)備文件形式存在于文件系統(tǒng)中攀隔。

消息隊列

是消息的鏈接表皂贩，存放在內(nèi)核中栖榨。一個消息隊列由一個標(biāo)識符（即隊列ID）來標(biāo)識。

• 消息隊列是面向記錄的明刷，其中的消息具有特定的格式以及特定的優(yōu)先級婴栽。

• 消息隊列獨立于發(fā)送與接收進程。進程終止時辈末，消息隊列及其內(nèi)容并不會被刪除愚争。

• 消息隊列可以實現(xiàn)消息的隨機查詢,消息不一定要以先進先出的次序讀取,也可以按消息的類型讀取。

信號量（semaphore）

它是一個計數(shù)器挤聘。信號量用于實現(xiàn)進程間的互斥與同步轰枝，而不是用于存儲進程間通信數(shù)據(jù)。

• 信號量用于進程間同步组去，若要在進程間傳遞數(shù)據(jù)需要結(jié)合共享內(nèi)存鞍陨。

• 信號量基于操作系統(tǒng)的 PV 操作，程序?qū)π盘柫康牟僮鞫际窃硬僮鳌?/p>

• 每次對信號量的 PV 操作不僅限于對信號量值加 1 或減 1从隆，而且可以加減任意正整數(shù)诚撵。

• 支持信號量組。

共享內(nèi)存

指兩個或多個進程共享一個給定的存儲區(qū)键闺。

• 共享內(nèi)存是最快的一種 IPC砾脑，因為進程是直接對內(nèi)存進行存取。

• 因為多個進程可以同時操作艾杏，所以需要進行同步韧衣。

• 信號量+共享內(nèi)存通常結(jié)合在一起使用，信號量用來同步對共享內(nèi)存的訪問购桑。

調(diào)度

進程行為

幾乎所有進程的（磁盤）I/O請求或計算都是交替突發(fā)的畅铭。
CPU不停頓地運行一段時間，然后發(fā)出一個系統(tǒng)調(diào)用以便讀寫文件勃蜘。
在完成系統(tǒng)調(diào)用之后硕噩，CPU又開始計算，直到它需要讀取更多的數(shù)據(jù)或?qū)懜嗟臄?shù)據(jù)為止缭贡。

• CPU密集型

• I/O密集型

  
  
  [Y2X59Y2@WL9RBCAKML`5]F.png

何時調(diào)度

1. 搶占式：給每個進程分配一個時間片炉擅，用完換下一個進程
2. 非搶占式：進程運行知道阻塞才換下一個進程

• 在創(chuàng)建一個新進程后，需要決定是運行父進程還是運行子進程阳惹。
• 在一個進程退出時必須做出調(diào)度決策谍失。
• 當(dāng)一個進程阻塞在I/O和信號量上或者由于其他原因阻塞時，必須選擇另一個進程運行莹汤。
• 在一個I/O中斷發(fā)生時快鱼，必須做出調(diào)度決策。

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

X0$OZJ70)IDZ}C1E}QXP@{I.png

調(diào)度算法

• 批處理

  • 先來先服務(wù)（非搶占式）

    • 用一個單鏈表隊列記錄所有就緒進程，從尾部加入就緒進程抹竹，從首部執(zhí)行進程线罕。

    • 缺點：對I/O密集型進程不友好，每次阻塞都要排到隊尾窃判，執(zhí)行完成時間相對長钞楼。

  • 最短作業(yè)優(yōu)先（非搶占式）

    • 已知進入就緒隊列的進程執(zhí)行時間

    • 對進程排序，使進程的平均周轉(zhuǎn)時間（即從進程進入隊列到進程完成的時間）最小袄琳。

    • <a> t = (4A + 3B + 2C + D)
      <b> t = (4B + 3C + 2D + A)
      所以時間最長的A最末尾询件。
      

      X0$OZJ70)IDZ}C1E}QXP@{I.png

  • 最短剩余時間優(yōu)先（搶占式）

    • 最短作業(yè)優(yōu)先的搶占式版本

    • 每次選擇剩余運行時間最短的進程運行

• 交互式

  • 輪轉(zhuǎn)調(diào)度

    • 維護一個就緒進程隊列，每個進程分配固定的時間片長度跨蟹，用完就回到隊尾雳殊。

    • 時間片長度過短橘沥，進程調(diào)度消耗太大窗轩；過長，則平均周轉(zhuǎn)時間過長座咆。通常設(shè)為20ms-50ms痢艺。

      
      
      X0$OZJ70)IDZ}C1E}QXP@{I.png

  • 優(yōu)先級調(diào)度

    • 優(yōu)先級高的先運行

      
      
      X0$OZJ70)IDZ}C1E}QXP@{I.png

    • 多級隊列

    • 最短進程優(yōu)先

    • 保證調(diào)度

    • 彩票調(diào)度

    • 公平分享調(diào)度

• 實時

  • 硬實時（hard real time）調(diào)度：調(diào)度機制確保一個關(guān)鍵任務(wù)能在指定時間前完成

  • 軟實時（soft real time）調(diào)度：調(diào)度機制盡量給予關(guān)鍵任務(wù)最高優(yōu)先級，盡量在指定時間前完成