第2章　進程的描述與控制

2.1　復習筆記

一、前趨圖和程序執行

1前趨圖

（1）定義

前趨圖是指一個有向無循環圖，可記為DAG，它用于描述進程之間執行的先后順序。

（2）圖形表示

前趨圖如圖2-1所示。

圖2-1　前趨圖

2程序的執行

（1）程序順序執行時的特征

①順序性。

②封閉性。

③可再現性。

（2）程序并發執行時的特征

①間斷性。

②失去封閉性。

③不可再現性。

二、進程的描述

1進程的定義和特征

（1）進程的定義

對于進程的定義，從不同的角度可以有不同的定義，其中較典型的定義有：

①進程是程序的一次執行。

②進程是一個程序及其數據在處理機上順序執行時所發生的活動。

③進程是具有獨立功能的程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立單位。

（2）進程的特征

①動態性

動態性是進程的最基本的特征。

②并發性。

③獨立性。

④異步性。

（3）進程實體

通常，進程實體由程序控制塊（PCB）、程序段、數據段三部分組成。

2進程的狀態及轉換

（1）進程有三種基本狀態：就緒狀態、執行狀態、阻塞（等待）狀態。圖2-2示出了基本狀態的轉換圖。

圖2-2　進程的三種基本狀態及轉換

（2）引入進程的創建狀態和終止狀態后，圖2-3示出了進程的五種狀態及轉換關系圖。

圖2-3　進程的五種狀態及轉換

3掛起操作和進程狀態的轉換

（1）當掛起操作作用于某個進程時，該進程將被掛起，意味著此時該進程處于靜止狀態。如果進程正在執行，它將暫停執行。若原本處于就緒狀態，則該進程此時暫不接受調度。與掛起操作對應的操作是激活操作。

（2）引入掛起原語操作后三個進程狀態的轉換

①活動就緒→靜止就緒。

②活動阻塞→靜止阻塞。

③靜止就緒→活動就緒。

④靜止阻塞→活動阻塞。

（3）引入掛起操作后五個進程狀態的轉換如圖2-4所示。

圖2-4　具有創建、終止和掛起狀態的進程狀態圖

4進程控制塊（PCB）

（1）概念

PCB是一記錄型數據結構，它作為進程實體的一部分，記錄了操作系統所需的、用于描述進程的當前情況以及管理進程運行的全部信息。

（2）進程控制塊中的信息

（3）進程控制塊的組織方式

①線性方式。

②鏈接方式。

③索引方式。

三、進程控制

進程控制是進程管理中最基本的功能，主要包括創建新進程、終止已完成的進程、將因發生異常情況而無法繼續運行的進程置于阻塞狀態、負責進程運行中的狀態轉換等功能。

四、進程同步

1進程同步的基本概念

（1）進程同步機制的主要任務

對多個相關進程在執行次序上進行協調，使并發執行的諸進程之間能按照一定的規則（或時序）共享系統資源，并能很好地相互合作，從而使程序的執行具有可再現性。

（2）臨界資源

一次僅允許一個進程使用的資源稱為臨界資源。

（3）臨界區

將在每個進程中訪問臨界資源的那段代碼稱為臨界區。

（4）同步機制應遵循的規則

①空閑讓進。

②忙則等待。

③有限等待。

④讓權等待。

2硬件同步機制

（1）關中斷。

（2）利用Test-and-Set指令實現互斥。

（3）利用Swap指令實現進程互斥。

3信號量機制

（1）整型信號量

①定義

把整型信號量定義為一個用于表示資源數目的整型量S。

②描述

通過兩個標準的原子操作wait（S）和signal（S）來訪問S，兩個操作一直被分別稱為P、V操作。wait和signal操作可描述如下：

wait(S)
{
  while(S<=0); /*do no-op*/
  S--;
}
signal(S)
{
  S++;
}

（2）記錄型信號量

①定義

記錄型信號量機制采用了記錄型的數據結構，是一種不存在“忙等”現象的進程同步機制。

②描述

typedef struct
{
  int value; //代表資源數目的整型變量
  struct process_control_block *list; //一個鏈接所有等待進程的進程鏈表指針
}semaphore;
wait(S)和signal(S)操作可描述如下：
wait(semaphore *S)
{
  S->value--;
  if(S->value<0)
    block(S->list);
}
signal(semaphore *S)
{
  S->value++;
  if(S->value<=0)
    wakeup(S->list);
}

4經典同步問題-生產者-消費者問題

問題描述：一組生產者進程和一組消費者進程共享一個初始為空、大小為n個單元的緩沖區。只有當緩沖區沒滿時，生產者才可以把消息放入緩沖區，否則必須等待；只有當緩沖區不空時，消費者才可以從中取出消息，否則必須等待。由于緩沖區是臨界資源，只允許一個生產者放入消息或者一個消費者從中取出消息，不允許同時訪問緩沖區。

信號量設置：定義信號量mutex為互斥信號量，初值為1，用于表示互斥訪問緩沖區；信號量empty用于表示當前緩沖區中可用空間大小，初值為n；信號量full用于表示當前緩沖區中已用空間大小，初值為0。

程序描述：

semaphore mutex=1;
semaphore empty=n;
semaphore full=0;
producer()

{ //生產者進程
  while(true)
  {
    //生產一個消息
    p(empty); //申請緩沖區中的一個空單元
    p(mutex); //申請訪問緩沖區
    //將消息放入緩沖區
    v(mutex); //釋放互斥信號量
    v(full); //緩沖區中滿單元數加一
  }
}
consumer()
{ //消費者進程
  while(true)
  {
    p(full); //申請從緩沖區中的滿單元取出消息
    p(mutex); //申請訪問緩沖區
    //將消息取出緩沖區
    v(mutex); //釋放互斥信號量
    v(empty); //緩沖區中空單元數加一
  }
}

5管程機制

（1）定義

一個管程定義了一個數據結構和能為并發進程所執行（在該數據結構上）的一組操作，這組操作能同步進程和改變管程中的數據。

（2）組成

①管程的名稱；

②局部于管程的共享數據結構說明；

③對該數據結構進行操作的一組過程；

④對局部于管程的共享數據設置初始值的語句。

五、進程通信

1進程通信的概念

（1）進程通信的定義

進程通信是指進程之間的信息交換。

（2）進程通信的分類

進程通信可分為高級進程通信和低級進程通信兩種。

2高級進程通信的類型

（1）共享存儲器系統

①基于共享數據結構的通信方式。

②基于共享存儲區的通信方式。

（2）管道通信系統

（3）消息傳遞系統（Message passing system）

①直接通信方式。

②問接通信方式。

（4）客戶機-服務器系統（Client-Server system）

六、線程的基本概念

1線程的引入

（1）進程的兩個基本屬性

①進程是一個可擁有資源的獨立單位；

②進程同時又是一個可獨立調度和分派的基本單位。

（2）線程引入原因

減少程序并發執行所需付出的時空開銷，使操作系統具有更好的并發性。

2線程與進程的比較

（1）調度的基本單位

①在傳統的OS中，進程是作為獨立調度和分派的基本單位，因而進程是能獨立運行的基本單位。

②而在引入線程的OS中，已把線程作為調度和分派的基本單位，因而線程是能獨立運行的基本單位。

（2）并發性

不同進程之間、在一個進程中的多個線程之間或者不同進程中的線程之間都能并發執行。

（3）擁有資源

①進程是系統中擁有資源的一個基本單位。

②線程本身并不擁有系統資源，而是僅有一點必不可少的、能保證獨立運行的資源。

（4）獨立性

在同一進程中的不同線程之間的獨立性要比不同進程之間的獨立性低得多。

（5）系統開銷

①創建或撤消進程時所付出的開銷明顯大于線程創建或撤消時所付出的開銷。

②線程的切換代價也遠低于進程的切換代價。

3線程的狀態和線程控制塊

（1）線程運行的三個狀態：執行狀態，就緒狀態，阻塞狀態。

（2）線程控制塊TCB

線程控制塊通常有這樣幾項信息：

①線程標識符；

②一組寄存器；

③線程運行狀態；

④優先級；

⑤線程專有存儲區；

⑥信號屏蔽；

⑦堆棧指針。

【說明】在多線程OS中，線程作為獨立運行（或稱調度）的基本單位；而進程仍是資源分配的基本單位。

七、線程的實現方式

1內核支持線程KST

2用戶級線程ULT

3組合方式

組合方式下包括三種不同的模型，如圖2-5所示。

圖2-5　多線程模型