作業系統原理第六章（程序排程）

一、排程/分派結構

      排程：依照完全确定的政策将一批程序進行排序

      分派：從就緒隊列中移出一個程序并給它提供處理機的使用權

      排程程式負責将一個程序插入到就緒隊列中，并按一定原則保持隊列結構；分派程式将程序下從就緒隊列中移出并建立該程序執行的機器狀态。

二、程序排程的功能和排程準則

      1.程序排程的功能：

                記錄和保持系統中所有程序的有關情況和狀态特征；

                決定配置設定政策；

               實施處理機的配置設定和回收；

         程序排程的時機：

             程序完成其任務時；

              在一次管理程式調用之後，該調用使現行程式暫時不能繼續運作時；

             在一次出錯陷入之後，該陷入使現行程序在出錯處理時被挂起；

             在分時系統中，當程序使用完規定的時間片，時鐘中斷使該程序讓出處理機時；

             在采用可剝奪排程方式的系統中，當具有更優先級的程序要處理機時。

       2.程序排程準則：

                      CPU使用率：40%（輕負荷系統）-----90%（重負荷系統）

                      吞吐量：一個時間單元内所完成的程序數量

                      周轉時間：在批處理系統中，從作業進入系統到完成的時間間隔（所有時間段之和）

                      響應時間：從聯機使用者向計算機發出一個指令到計算機執行完該指令，并将相應執行結果傳回給使用者所需時間。

                      等待時間：程序在就緒隊列中所花費的時間

        3.排程方式：

                      非剝奪方式：若有更高優先級的程序進入就緒隊列時，仍然讓正在執行的程序繼續執行，知道該程序完成或者進入“阻塞”“完成”狀态的時候，才把處理機配置設定給具有更高優先級的程序；

                      可剝奪方式：若有更高優先級的程序進入就緒隊列時，立即暫停正在執行的程序，把處理機配置設定給它；

          可搶占政策：（U,V）标志

                      U=1:該程序可搶占另一程序              U=0:該程序不可搶占另一程序

                      V=1:該程序可被另一程序搶占            V=0:該程序不可被另一程序搶占

  三、典型排程算法：

         1.先來先服務排程：按照作業進入系統的時間先後次序來挑選作業，先進入系統的作業優先被運作

                      容易實作，效率不高

                      隻考慮作業的等待時間，沒考慮作業的運作時間長短，不利于短作業

          2.短作業優先排程：參考運作時間，選取運作時間最短的作業投入運作

                      容易實作，效率不高

                     忽視了作業的等待時間，一個早來但是長的作業可能在長時間内得不到排程，容易出現資源“饑餓”現象。

           3.響應比高者優先排程：排程作業時計算作業清單中每個作業的響應比，選擇響應比高的優先投入運作

                      響應比=響應時間/運作時間 =1+等待時間/運作時間

                       等待時間相同，有利于短作業；運作時間相同，有利于等待時間很長的作業

           4.優先數排程算法：根據程序優先數，将CPU配置設定給最高的程序

                       程序優先數=靜态優先數+動态優先數

                       靜态優先數：程序建立時給定，整個程序運作期間不會變動

                       動态優先數：在程序運作期間可以改變

                                   靜态優先數的确定：根據程序所需要的資源來計算；

                                                                  基于程式運作時間的估計；

                                                                  基于程序的類型。

                                  動态優先數的确定：當程序使用CPU超過一定數值時，降低優先數；

                                                                 當程序進行IO操作時，增加優先數；

                                                                 當程序等待時間超過一定數值時，增加優先數。

           5.循環輪轉排程法：把所有就緒程序按先進先出原則排成隊列，新來的程序加到隊列末尾；程序以時間片q為機關輪流使用CPU，剛剛運作了一個時間片的程序排到隊列末尾，等待下一輪排程；邏輯上是環形的。

                         優點：公平性（每個就緒程序獲得CPU的機會均等）

                                    互動性（每個程序等待一定時間後就可以重新獲得CPU）

                         若時間片太大，互動性差，甚至退化為先進先出排程算法；

                         若時間片太小，程序切換頻繁，系統開銷增加。

                         改進：時間片的大小可變（可變時間片輪轉排程法）

                                   組織多個就緒隊列（多重時間片循環輪轉 ）