第二章：程序管理

概念：一個具有一定獨立功能的程式對某個資料集合的一次動态執行過程和資源配置設定過程。 

相關元素：代碼、資料、程序表

程序和程式的差別和聯系：

    ·程序是動态的，程式是靜态的

    ·程序是暫時的，程式是永久的

    ·程式和程序都包含代碼資料，程序還還有程序表

    ·程式經過多建立，可以對應不同的程序

    ·一個程序通過系統調用，可以被多個程式所調用

 性質：

    ·動态性 

    ·并發性

    ·獨立性

   ·異步性

 程序的三種主要狀态：

    ·運作狀态

    ·阻塞狀态：由于各種原因，程序放棄處理機的運作，而且不再期望被調用進行處理。

      阻塞分為兩種：

        ·被迫阻塞

         ·自我阻塞

   ·就緒狀态：準備好資源等待由排程器排程進入運作狀态

 三種狀态之間的轉換：

   ·運作狀态 --> 阻塞狀态

   ·運作狀态 --> 就緒狀态

   ·就緒狀态 --> 運作狀态

   ·阻塞狀态 --> 就緒狀态

 程序控制：

   ·程序建立：

       首先查找系統的PCB表（程序控制表），查詢有無空的PCB表，如果有 ，則申請一個，并對其進行初始化。初始化的項目有程序辨別符（PID）、程序狀态和運作程式的起    始位址等。如果申請不成功，要麼繼續等待有空閑PCB表時繼續申請，要麼傳回建立失敗資訊。

   ·程序的建立：

     申請空白程序表—>為新程序配置設定資源—>初始化程序表—>如果程序就緒隊列能夠接納新程序，便将程序插入就緒隊列。

 建立程序的典型事件：

   ·使用者登入 

   ·作業排程 

   ·提供服務

   ·應用請求

 程序撤銷：

    撤銷原語首先檢查PCB連結清單，尋找索要撤銷的程序是否存在，如果找到了相應的表項，則撤銷原語就釋放該程序占用的資源并回收對應的PCB資料結構， 如果該程序還有子進     程，則程序撤銷原語必須先撤銷子程序的PCB表并釋放其占用的資源。

 程序撤銷的情況：

    ·正常結束（自願的）

    ·異常結束

        ·普通錯誤退出（自願的）

       ·緻命錯誤退出（非自願的）

   ·外界幹預（非自願的）

 程序阻塞：

     程序阻塞原語先停止處理機并同時儲存該程序的處理現場，然後将阻塞程序插入到等待隊列中，再将控制權交給排程程式，排程程式會按排程算法從就緒隊列中選擇一個進        程投入運作。

 程序喚醒：

      喚醒原語将被喚醒的程序從相應的等待隊列移除，并将其PCB中狀态置為就緒狀态，并将其送入就緒隊列。此時，喚醒原語既可以從排程程式處直接傳回，也可以轉向程序        排程程式，由排程程序選擇一個合适的程序去運作。

     程序由運作狀态變為阻塞狀态時，是這個程序自己調用阻塞原語去完成的，而程序由阻塞狀态到就緒狀态卻是另一個程序調用喚醒原語實作的，一般情況下，這個程序與被        喚醒程序是具有一定相關性的并發程序。

 可能引起阻塞和喚醒的事件：

     ·請求系統服務

     ·啟動某種操作

     ·新資料尚未到達

     ·無新工作可做

 程序挂起：

     挂起原語将程序交換到外存儲區挂起，釋放其在記憶體中占用的資源，改寫PCB，傳回系統。

 程序激活：

     激活原語将程序從外存儲區交換到記憶體，進行記憶體重定位，改寫PCB程序狀态資訊，記憶體非配資訊，程式計數器等，傳回激活原語調用處。當激活後程序處于就緒狀态時，        傳回後，控制權将交還給排程程式，重新排程。

 程序組織：

    ·程序實體：

   ·程式：也稱正文，描述程序所要完成的功能，特指二進制的指令代碼。

   ·資料集合：程式運作時所需要的資料結構，包括常數、變量、堆、資料棧     等。

   ·程序控制子產品：

        ·程序控制子產品包含了程序的描述資訊、控制資訊和資源資訊，是程序動态特性的集中反映。

        ·程序控制資訊包括：程序的基本資訊和處理機管理資訊

        ·程序記憶體資源配置設定

       ·程序裝置和檔案的配置設定使用情況程序同信：程序之間的資訊交換工作稱為程序間的同信

   ·P、V操作稱為低級操作

  ·進階通信的方式可分為三類：

      ·共享記憶體 

      ·消息傳遞

     ·管道機制

 線程：

    特性：

         ·輕型實體（容易建立和撤銷）

        ·獨立排程和配置設定的基本機關

        ·可并發執行

        ·共享程序資源

        ·适應硬體發展

 排程：

     概念：程序的數量多于處理機的個數，競争處理機。 配置設定處理機的任務由程序排程機完成，由程序配置設定程式具體實施。用一定的算法，動态的把處理機配置設定給程序，使之                       能公平、合理和高效的 運作。

                    排程是分層次的，一個作業從送出開始，直到完成，往往要經曆多級排程。

     程序排程：又稱為微觀排程，是指決定就緒隊列中那個程序将獲得處理機，并實際将處理機配置設定給該程序的操作。

 引起程序排程的典型事件：

      ·正在運作的程序發生某事件而不能再繼續運作

     ·運作中的程序因提出輸入/輸出請求而暫停運作

     ·在程序同信或同步過程中運作了某種原語操作，如P操作

     ·在可搶先式排程中，有一個比目前程序優先級更高的程序進入就緒隊列

     ·在時間片輪轉算法中，時間片用完

 分派程式：分派程式完成程序的切換，是實際操作者：主要為上下文切換

  排程的基本準則包括：

      ·處理機使用率

      ·吞吐量 

      ·周轉時間

  排程方式：

      ·可搶先 

     ·不可搶先

  排程的典型算法：

      ·先來先服務（FCFS）

      ·短作業或短進（線）程優先（SJF&SPF）

      ·時間片輪轉排程算法（RR）

      ·高優先級優先排程算法

      ·高響應比優先排程（HRRN）算法：

     響應比Rp=（等待時間+預計運作時間）

            預計運作時間=（響應時間/預計運作時間）

     ·多級回報隊列排程算法

  同步與互斥：

    概念：

    ·間接互相制約：源于資源共享-互斥

    ·直接互相制約：源于程序合作-同步

     ·臨界資源：一次隻允許一個程序實用的資源稱為臨界資源

            臨界區：在每個程序中，通路臨街資源的那段代碼稱為臨界區

  同步與互斥的基本準則：

      ·空閑則進 ·遇忙等待 ·有限等待 ·讓權等待

  實作臨界區互斥的基本方法：

     ·軟體實作方法

     ·硬體實作方法

  信号量：信号量的值是可變的，由初始化和P、V操作來改變

  ·P(S)操作的定義：

     --S.Q；        //表示申請一個資源

      If(S.Q<0) //若沒有空閑資源

    {

         調用程序進入等待隊列S.Q；

         阻塞調用程序；

     } 

  ·V(S)操作的定義：

       --V(S)； //表示釋放一個資源

      If(S.Q < 0) 若有程序處于阻塞狀态

     {

         從等待隊列S.Q中取出一個程序P；

        程序P進入就緒隊列；

     }

    ·同步時：P、V操作一定會是一組，即同時出現

    ·互斥時：P、V操作一定是分開的

管程：

      一個管程定義了一個資料結構和能為并發程序所運作的一組操作，這組操作能同步程序和改變管程的的資料。 

     經典的同步問題：

           ·生産者-消費者問題

           ·讀者-寫者問題 ·哲學家問題

死鎖：

    概念：系統中兩個或兩個以上的程序無限期的互相等待永遠不會發生的條 件，系統處于一種停止狀态，這種情況稱為死鎖。

    死鎖産生的原因：

         ·程序推進的書序不當

         ·對互斥資源配置設定不當

   産生死鎖的四個必要條件（必須全部具備）：

         ·互斥條件：任意時刻隻允許一個程序使用資源

        ·非剝奪條件：程序已經占用的資源，不會被強制剝奪

        ·占用并請求資源：程序占有部分資源，并申請更多的資源，且不會主動釋放已占有的資源

      ·循環等待：請求資源的程序形成了循環

    死鎖的處理政策：

         ·忽略死鎖

         ·死鎖的檢測與恢複

         ·死鎖的避免

        ·死鎖的預防

   死鎖預防：

          條件              方法

          ----------------------------------------------------

         互斥             虛拟裝置假擺脫

         占有并等待       一次配置設定全部資源

         非剝奪           主動放棄

         循環等待          有序配置設定資源

   死鎖避免：

         ·安全狀态 

         ·不安全狀态

   死鎖的檢測：

         ·資源配置設定圖算法

        ·資源矩陣算法

   死鎖的解除：

        ·資源剝奪法

        ·程序撤銷法 

       ·程序回退法

       ·重新啟動系統