進程的基本概念

• 程序順序執行的特征：

  1）順序性：處理機嚴格按照程序所規定的順序執行，每一步操作必須在下一步操作開始前執行

  2）封閉性：程序在封閉的環境下運行，程序獨占資源，資源的狀態由程序決定，程序一旦開始執行，外界環境不會影響程序的執行結果。

  3）可再現性：只要程序的初始條件和環境相同，程序的執行結果就相同。

• 程序的并發執行的特征：（順序執行會浪費資源）

  1）間斷性：程序共享系統的資源，以及為完成同一個任務共同合作，并發執行的程序之間相互制約，（不是運行完一個在運行另一個）

  2）失去封閉性：各程序共享系統資源，資源的狀態由各程序所決定。

  3）不可再現性：由于失去了封閉性，（即初始的環境狀態和條件相同，程序的執行結果卻可能不同），該特征超級垃圾，必須想辦法避免。

• 進程的概念：

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

• 進程的特征：

  • 結構特征：

    PCB（進程控制塊），與進程共存亡，用于記錄進程的基本情況和活動過程，一般常駐內存
    程序段（一般為需要的時候動態調入內存），描述要完成的功能
    數據段（一般為需要的時候動態調入內存），操作的對象即工作區

  • 動態性：進程最基本的特征，進程不是靜態的，而是動態的，它由創建而產生，由調度（這里主要指進程調度，而不是作業調度）而執行，由撤銷而消亡

  • 并發性：指多個進程實體存于內存中，且能在同一時間段內執行，（這里同操作系統的并發性）

  • 獨立性：進程實體是一個能獨立運行，獨立獲得資源和獨立接收調度的基本單位

  • 異步性：同操作系統的異步性

• 進程的三種基本狀態：

  • 就緒狀態：進程已經分配到除了CPU之外的所有資源，只要獲得CPU便可以立刻執行，處于就緒狀態的進程維持一個就緒隊列。
  • 執行狀態：已經獲得CPU，正在執行的進程。（單處理機系統中，同一時刻只能有一個進程處于執行狀態，多處理機系統中，可以同時有多個進程處于執行態）
  • 阻塞狀態/等待狀態：在執行的過程中由于發生某些事件（I/O請求，申請緩存等），暫時無法執行的進程，是由于進程本身引起的阻塞。處于阻塞狀態的進程可以維持一個阻塞隊列。
  • 進程是自己阻塞自己的，但是阻塞的進程需要其他進程將其喚醒

• 三種基本狀態的轉換：

?

? 就緒—>執行：進程調度，獲得CPU資源

? 執行—>就緒：在分時操作系統中時間片花完

? 執行—>阻塞：I/O請求，申請緩存等，自己被迫進入阻塞狀態

? 阻塞—>就緒：I/O完成，造成阻塞的原因得到解決（又變成只差CPU的狀態）

• 進程的創建狀態和終止狀態

  創建狀態：進程成為就緒狀態之前的狀態

  終止狀態：當一個進程到達了自然結束點，或者遇到無法客服的困難，或者被操作系統所終結等的時候，就進入了終止狀態。

• 掛起操作及引入的原因：

  1）進程被掛起之后處于靜止狀態。

  2）引入的原因：

  • 終端用戶的需要：當終端用戶想要暫停自己程序的運行的時候
  • 父進程請求：當父進程想要掛起某個子進程的時候
  • 負荷調節的需要：當實時系統中的工作負荷較重，系統可以將某些不重要的進程掛起，保證程序的正常運行。
  • 操作系統的需要：操作系統有事需要將某些進程掛起，已檢查運行過程中資源的使用情況

  3）引入掛起操作后，進程的狀態轉換：

  ?

  （1）阻塞態可以通過釋放變為就緒態。活動阻塞釋放變為活動就緒，靜止阻塞釋放變為靜止就緒。

  （2）活動態和靜止態可以進行相互轉換，活動到靜止稱為掛起，靜止到活動可以稱為激活。活動態和靜止態最本質的區別為活動態在內存中，靜止態暫時調出內存，進入外存

  （3由執行態可以直接變為靜止就緒態，即時間片用完，直接調離內存

  （4）靜止態（外存）必須通過激活變為非靜止態（調入內存）才能夠參與進程的三臺轉換。

  4）進程掛起之后不是原封不動的將進程移出內存，而是會先將一些必要的信息寫入外存。再釋放PCB

• 進程管理中的數據結構

  • 操作系統中用于管理控制的數據結構：內存表，設備表，文件表，進程表（程序控制快PCB）

  • 進程控制塊PCB的作用：

    1）作為獨立運行基本單位的標志

    2）能實現間斷性的運行方式

    3）提供進程管理所需要的全部信息

    4）提供進程調度所需要的全部信息

    5）實現與其他進程的同步和通信

  • 進程控制塊中的信息：

    進程標識符：唯一表示一個進程，有兩種：

    1）外部標識符：方便用戶對進程的訪問，通常有數字和字母組成

    2）內部標識符：方便系統對進程的訪問，每一個進程有一個唯一的數字標識符。

    處理機狀態：（主要指的是處理機中寄存器的狀態）

    1）通用寄存器：又稱為用戶寄存器，用戶的程序可以訪問，用于暫存信息，一般為8~32個

    2）指令計數器：存放了將要訪問的下一條指令的地址。

    3）程序狀態字（PSW?）：含有狀態信息，條件碼，執行方式（指在系統還是用戶狀態下執行），中斷屏蔽標志（允不允許在執行的過程中被打斷）

    4）用戶棧指針：每個用戶進程都有系統棧，用于存放過程和系統調用參數及調用地址。

    進程調度信息

    1）進程狀態：指明了進程的當前狀態

    2）進程優先級：即一個整數，用于描述進程使用CPU的優先級，數字越大，優先級越高

    3）其他信息：與采用的進程調度算法有關

    4）事件：指進程由執行狀態變為阻塞狀態所等待發生的事件。

    進程控制信息

    1）程序和數據的地址：由于程序段和數據段并不是常駐內存的，而是使用的時候才調入，因此需要保存其地址

    2）進程同步和通信機制：

    3）資源清單：一張清單列出了該進程在運行期間所需的全部資源（除了CPU資源），另一張列出了分配到該進程的資源的清單。

    4）鏈接指針：給出了本進程（PCB）所在隊列中的下一個進程的PCB的首地址。

  • 進程控制塊的組織方式：

    線性方式：不重要

    鏈接方式：類似靜態鏈表，把具有同一狀態的PCB用其中的鏈接字鏈接成一個隊列

  ?

  ?

  注：進程資源的分配并不是在該進程執行之前將該進程所需的資源全部分配給他，而是在其執行的過程中進行動態的分配。

進程與程序的區別與關系

• 進程與程序的區別：
  • 進程是一個動態的概念（有 “ 生命 ” ），程序是靜態的概念。
  • 進程可以具有并行性（在多處理器的系統中），但是程序沒有
  • 進程是競爭系統資源的基本單位
• 進程與程序的關系：
  • 一個程序對應多個進程，一個進程又可以為多個程序服務。

進程控制

1.基本知識

• 進程控制是進程管理中最基本的功能，主要包括進程的創建，進程的終止和運行中的進程的狀態轉換等功能。進程控制一般是由OS的內核中的原語來實現的。

2.進程的創建

• 進程的層次結構

• 進程圖

• 引起進程創建的事件

  1）用戶登錄：在分時系統中，用戶成功登錄，系統將為該用戶分配新的進程

  2）作業調度：在多道批處理系統中，作業調度程序將某些作業調度內存，并且為他們創建進程

  3）提供服務：運行中的用戶程序提出某種請求

  4）應用請求：由用戶進程自己創建，幫助自己完成特定的任務

• ==進程的創建過程：==OS調用進程創建原語Create創建一個新進程

  1）申請空白PCB：新進程獲得一個唯一的數字標識符（對于操作系統）

  2）為新進程分配器運行所需的資源：包括物理資源和邏輯資源

  3）初始化進程控制塊PCB：

  （1）初始化標識符信息：系統分配的標識符信息裝入PCB

  （2）初始化處理機狀態信息：主要為一些寄存器

  （3）初始化處理機控制信息：一般初始化為就緒狀態

  （4）如果進程就緒隊列允許，將進程插入就緒隊列

3.進程的終止

• 引起進程終止的事件：

  1）正常結束

  2）異常結束：1）越界錯誤（訪問自己范圍外的），2）保護錯誤（訪問自己無權利訪問的）3）非法指令：試圖運行不存在的指令，4）特權指令；5）運行超時；6）等待超時；7）算術運算錯；8）I/O故障

  3）外界的干預：1）操作員或者操作系統干預；2）父進程的請求（父進程的權利大于子進程）3）父進程的終止：當父進程終止時，其所有子進程也應當終止。

• ==進程終止的過程：==OS調用進程終止原語

  1）根據要終止的進程的標識符，搜索出該進程的PCB，從中獲得該進程所處的狀態

  2）如果該進程正處于執行狀態，立刻終止該進程，并且置調度標志為真，表示在該進程結束后應該進行重新調度（即不要讓CPU空閑）

  3）若該進程有子孫進程，讓其所有子孫進程都終止。

  4）被終止進程所擁有的所有資源歸還給父進程或者操作系統

  5）將終止進程的PCB從所在隊列中移除，等待其他程序來收集信息。

4.進程的阻塞與喚醒

• 引起進程阻塞和喚醒的事件：阻塞和喚醒是相對應的

  1）向系統請求共享資源失敗

  2）等待某種操作的完成

  3）新數據尚未到達

  4）等待新任務的到達

• 進程阻塞的過程：進程通過調用阻塞原語block==將自己==阻塞

  1）進入block后立即停止執行

  2）保存現場

  3）將進程控制塊中的現行狀態改為阻塞，并將PCB插入阻塞隊列

  4）轉調度程序，進行重新調度

• 進程喚醒的過程：當阻塞的進程所期待的事件發生時，有關進程（不是本身）調用喚醒原語wakeup，將等待該事件的進程喚醒。喚醒之后進入就緒隊列。

  1）將被阻塞的進程從等待該事件的阻塞隊列中移除

  2）將PCB的現行狀態由阻塞改為就緒

  3）然后再將該PCB插入就緒隊列中

  4）轉進程調度或者返回

• block原語和wakeup原語是一對作用剛好相反的原語，必須成對使用。

5.進程的掛起與激活

• 進程的掛起過程：當出現了引起進程掛起的事件之后，OS利用掛起原語將指定的進程掛起（即調出內存）

  首先檢查進程的狀態（不同的狀態采取不同的處理方式），若該進程正處于活動就緒狀態，將其改為靜止就緒態；若該進程處于活動阻塞狀態，將該進程改為靜止阻塞狀態；若該進程處于執行狀態，將其改為靜止就緒狀態，調度程序重新進行調度。

• 進程的激活過程：

  1）首先將進程從外存調入內存，

  2）檢查進程所處的狀態，如果進程處于靜止就緒，將其改為活動就緒，如果處于靜止阻塞，將其改為活動阻塞

  3）檢查進程的優先級，如果優先級高，可以進行搶占當前運行進程的資源

4.進程同步

1.進程同步的基本概念

• 進程同步的目的：1）按照一定的規則共享系統資源；2）對多個相關進程在執行次序上進行協調，是程序具有可再現性。

• 兩種形式的制約關系：

  1）間接相互制約關系：多個進程在并發執行時，由于共享系統的臨界資源而相互制約，如磁帶機，打印機，表格等。（互斥）

  2）直接相互制約關系：多個進程為完成同一任務而相互合作（同步）

• **臨界資源：**一次僅允許一個進程使用的共享資源。例如打印機，磁帶機，表格等。

• 互斥和同步的概念：

  1）互斥：并發的多個進程由于競爭同一資源而產生的相互排斥的關系

  2）同步：進程間共同完成一項任務時直接發生相互作用的關系

• 臨界區：每個進程中訪問臨界資源的那段代碼

/*一個訪問臨界資源的循環進程*/
while(true)
{進入區：//對欲訪問的臨界資源進行檢查，查看其是否正被訪問，如果此刻臨界資源未被訪問，進程便可以進入臨界區對臨界資源進行訪問，并設置它正被訪問的標志，如果此刻臨界資源正被訪問，則不能進入臨界區。即后邊的wait（）操作臨界區：//執行臨界資源的那段代碼退出區：//將臨界區正被訪問的標志恢復為未被訪問的標志，signal（）操作剩余區：//除上述三個區之外的代碼叫做剩余區
}

• 同步機制應遵循的原則：

  1）空閑讓進

  2）忙則等待

  3）有限等待：不能一直等

  4）讓權等待：進程不能進入臨界區，就應當釋放==處理機==，讓權指讓出處理機

2.硬件同步機制

3.信號量機制：Dijkstra提出

• 信號量：

  • 是一種數據結構
  • 值與相應資源的使用情況有關
  • 僅與P，V操作有關，P，V代表兩種原子操作，P為等候原語wait（S）,V為釋放原語signal（S）。
  • wait操作即在申請資源，signal操作是釋放資源
  • wait操作其實就是進入臨界區之前的進入區，signal操作是從臨界區出來之后的退出區
  • 原子操作的特點，操作一開始執行，半中間不可以打斷，原語即為原子操作。

• 整型信號量

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

  /*等候原語*/
  wait(S){while(S <= 0);  //當S<=0的時候便一直處于等待狀態，直到獲得相應的資源，不符合讓權等待的原則      S--;     //獲得資源后，資源的數目減一，S表示該類資源可用的數目      
  }/*釋放原語*/
  signal(S){S++;      //釋放資源后，資源的數目加一     
  }

  • 優缺點：

    優點：實現簡單

    缺點：違背了同步機制中的讓權等待原則，浪費資源（只要S<=0，就會等待）

• **記錄型信號量：**當前用的最多的

  • 特點：采用了記錄型的數據結構

  /*記錄型數據結構*/
  typedef struct{int value;      //>=0的時候，表示系統中可用資源的數量，<0的時候其絕對值表示因為該資源而阻塞的進程的數目struct process_control_block *list;    //維持阻塞隊列的指針
  }semaphore;/*等待原語*/
  wait(semaphopre *S){S->value--;    //一個進程過來，首先將S->value--；if(S->value < 0){     //<0表示資源已經用光，將該進程加入阻塞隊列block(S->list);}
  }/*釋放原語*/
  signal(semaphore *S){S->value++;      //釋放資源，S->value++；if(S->value <= 0){      //S->value++之后，還<=0，直接喚醒一個阻塞的進程，喚醒的進程擁有了該資源的使用權（不需要再次執行P操作），然后進入就緒隊列。如果>0，直接將資源釋放即可wakeup(S->list);}
  }

  • wait操作：每次都相當于進程請求一個單位的該類資源

    signal操作：每次都相當于釋放一個單位資源

  • 當S->value的初值為1的時候，表示只允許一個進程訪問臨界資源，信號量轉化為互斥型信號量

  • 優點：通過維持阻塞隊列的指針，使得滿足了讓權等待的原則，彌補了整型信號量的缺點

  • **缺點：**只適用于對單一資源的管理，如果一個進程需要請求多類資源的時候，很容易產生死鎖。

• AND型信號量：解決記錄型信號量會發生的死鎖的問題

  • 當一個進程需要兩個或者更多的共享資源來完成一個目標的時候，多個進程之間可能會發生阻塞（剛開始前半部分資源占有了，但是后半部分資源無法獲得，自己再阻塞自己，即發生了死鎖）
  • AND的解決思想：將一個進程運行過程中所需要的全部資源一次性都分給他，待進程使用完之后，在一起進行釋放。（即一起申請，一起釋放）

  /*等候原語：全分配*/
  Swait(S1, S2, …, Sn){While(TRUE){//多類資源同時滿足的時候才進行分配，先判斷再分配。if (S1 >=1 and … and Sn>=1 ){for( i=1 ;i<=n; i++) Si - -;break;}else{Place the process in the waiting queue associated with the first Si found with Si <1,and set the progress count of this process to the beginning of Swait operation	（將即將阻塞的進程掛到第一個不能滿足他的資源的阻塞隊列，然后設置該進程的起始地址為Swait操作的開始）}}
  }/*釋放原語：全釋放*/
  Ssignal(S1, S2, …, Sn){while(TRUE){    for (i=1; i<=n; i++) {Si++ ;Remove all the process waiting in the queue associated with Si into the ready queue（將因為該資源得不到滿足而阻塞的所有進程都從阻塞隊列釋放進入就緒隊列，重新進行排隊）}}
  }

  注意：

  1）在分配資源的時候首先判斷是否所有資源均全部滿足相應的條件，滿足才進行分配。

  2）釋放的時候是將因為該資源得不到滿足而阻塞的所有進程都從阻塞隊列釋放進入就緒隊列，重新進行排隊，因為OS需要根據調度算法重新選取新的進程占據CPU

• 信號量集

Swait(S1, t1, d1; …; Sn, tn, dn)if (S1>= t1 and … and Sn>= tn) thenfor i:=1 to n doSi:= Si - di ;endforelsePlace the executing process in the waiting queue of the first Si with Si < ti and set its program counter to the beginning of the Swait Operationendif

注意：

1）繼承了AND型信號量的思想，先判斷是否所有所需資源均滿足條件。滿足才進行分配。

2）引入了下限值的概念。Si表示可用的資源的數量；ti表示想要分配資源成功至少需要的該資源的數目（ti（下限值）包括兩部分，一部分是系統執行該進程所需，另一部分是該進程所請求的，因此一般大于di）；di表示該進程所請求的該類資源的數目。

4.信號量的應用

1、利用信號量實現進程互斥

semaphore  mutex =1;beginparbeginprocess 1: beginrepeatwait(mutex);critical sectionsignal(mutex);remainder sectionuntil false;endprocess 2: beginrepeatwait(mutex);critical sectionsignal(mutex);remainder sectionuntil false; endparend        end

注意：

1）利用信號量實現進程互斥地訪問某種資源。首先應將mutex設為1

2）wait操作和signal操作必須成對地出現，如果缺少wait操作可能會造成系統的混亂；如果缺少signal操作，那么該資源永遠不會得到釋放，因該資源而被阻塞的進程也將永遠不會被喚醒。

2、利用信號量實現前驅關系圖（進程同步）

如下圖：

semaphore  a, b, c, d, e, f, g = 0, 0, 0, 0, 0, 0, 0;beginparbeginbegin  S1; signal(a); signal(b); end;begin  wait(a); S2; signal(c); signal(d); end;begin  wait(b); S3; signal(e); end;begin  wait(c); S4; signal(f); end;begin  wait(d); S5; signal(g); end;begin  wait(e); wait(f); wait(g); S6; end;parendend

注意：

1）信號量的初值必須被設置為0，必須等某個進程之前的進程完之后，釋放資源，后邊的進程才能夠執行。