程序的排程算法

在作業系統，程序是很重要的概念！！！！        

       程序（Process）是計算機中的程式關于某資料集合上的一次運作活動，是系統進行資源配置設定和排程的基本機關，是作業系統結構的基礎。在早期面向程序設計的計算機結構中，程序是程式的基本執行實體；在當代面向線程設計的計算機結構中，程序是線程的容器。程式是指令、資料及其組織形式的描述，程序是程式的實體。

        引入程序的目的，在多道程式系統出現後，為了刻畫系統内部出現的動态情況，描述系統内部各道程式的活動規律引進的一個概念,所有多道程式設計作業系統都建立在程序的基礎上。

程序的特性：

           動态性：程序的實質是程式在多道程式系統中的一次執行過程，程序是動态産生，動态消亡的。

          并發性：任何程序都可以同其他程序一起并發執行

          獨立性：程序是一個能獨立運作的基本機關，同時也是系統配置設定資源和排程的獨立機關；

          異步性：由于程序間的互相制約，使程序具有執行的間斷性，即程序按各自獨立的、不可預知的速度向前推進

今天主要是學習程序的排程算法：

（1）先進先出算法（FIFO）

          算法總是把處理機配置設定給最先進入就緒隊列的程序，一個程序一旦分得處理機，便一直執行下去，直到該程序完成或阻塞時，才釋放處理機。

例如，有三個程序P1、P2和P3先後進入就緒隊列，它們的執行期分别是21、6和3個機關時間，

執行情況如下圖：

對于P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。

可見，FIFO算法服務品質不佳，容易引起作業使用者不滿，常作為一種輔助排程算法。

（2）短程序優先

          最短CPU運作期優先排程算法(SCBF--Shortest CPU Burst First)

          該算法從就緒隊列中選出下一個“CPU執行期最短”的程序，為之配置設定處理機。

例如，在就緒隊列中有四個程序P1、P2、P3和P4，它們的下一個執行 期分别是16、12、4和3個機關時間，執行情況如下圖：

P1、P2、P3和P4的周轉時間分别為35、19、7、3，平均周轉時間為16。

該算法雖可獲得較好的排程性能，但難以準确地知道下一個CPU執行期，而隻能根據每一個程序的執行曆史來預測。

（3）輪轉法

         前幾種算法主要用于批處理系統中，不能作為分時系統中的主排程算法，在分時系統中，都采用時間片輪轉法。

         簡單輪轉法：系統将所有就緒程序按FIFO規則排隊，按一定的時間間隔把處理機配置設定給隊列中的程序。這樣，就緒隊列中所有程序均可獲得一個時間片的處理機而運作。

         多級隊列方法：将系統中所有程序分成若幹類，每類為一級。

（4）多級回報隊列

多級回報隊列方式是在系統中設定多個就緒隊列，并賦予各隊列以不同的優先權。

下面主要談到Linux中的程序排程方法

Linux 下的排程方法類似于上述算法：

1，SCHED_OTHER 分時排程政策，

2，SCHED_FIFO實時排程政策，先到先服務

3，SCHED_RR實時排程政策，時間片輪轉

   SHCED_RR和SCHED_FIFO的不同：

   當采用SHCED_RR政策的程序的時間片用完，系統将重新配置設定時間片，并置于就緒隊列尾。放在隊列尾保證了所有具有相同優先級的RR任務的排程公平。

   SCHED_FIFO一旦占用cpu則一直運作。一直運作直到有更高優先級任務到達或自己放棄。

如果有相同優先級的實時程序（根據優先級計算的排程權值是一樣的）已經準備好，FIFO時必須等待該程序主動放棄後才可以運作這個優先級相同的任務。而RR可以讓每個任務都執行一段時間。

  相同點：

   RR和FIFO都隻用于實時任務。

   建立時優先級大于0(1-99)。

   按照可搶占優先級排程算法進行。

   就緒态的實時任務立即搶占非實時任務。

  所有任務都采用linux分時排程政策時。

  1，建立任務指定采用分時排程政策，并指定優先級nice值(-20~19)。

  2，将根據每個任務的nice值确定在cpu上的執行時間(counter)。

  3，如果沒有等待資源，則将該任務加入到就緒隊列中。

  4，排程程式周遊就緒隊列中的任務，通過對每個任務動态優先級的計算(counter+20-nice)結果，選擇計算結果最大的一個去運作，當這個時間片用完後(counter減至0)或者主動放棄cpu時，該任務将被放在就緒隊列末尾(時間片用完)或等待隊列(因等待資源而放棄cpu)中。

  5，此時排程程式重複上面計算過程，轉到第4步。

  6，當排程程式發現所有就緒任務計算所得的權值都為不大于0時，重複第2步。

  所有任務都采用FIFO時，

  1，建立程序時指定采用FIFO，并設定實時優先級rt_priority(1-99)。

  2，如果沒有等待資源，則将該任務加入到就緒隊列中。

  3，排程程式周遊就緒隊列，根據實時優先級計算排程權值(1000+rt_priority)，選擇權值最高的任務使用cpu，該FIFO任務将一直占有cpu直到有優先級更高的任務就緒(即使優先級相同也不行)或者主動放棄(等待資源)。

  4，排程程式發現有優先級更高的任務到達(高優先級任務可能被中斷或定時器任務喚醒，再或被目前運作的任務喚醒，等等)，則排程程式立即在目前任務堆棧中儲存目前cpu寄存器的所有資料，重新從高優先級任務的堆棧中加載寄存器資料到cpu，此時高優先級的任務開始運作。重複第3步。

  5，如果目前任務因等待資源而主動放棄cpu使用權，則該任務将從就緒隊列中删除，加入等待隊列，此時重複第3步。

  所有任務都采用RR排程政策時

  1，建立任務時指定排程參數為RR，并設定任務的實時優先級和nice值(nice值将會轉換為該任務的時間片的長度)。

  3，排程程式周遊就緒隊列，根據實時優先級計算排程權值(1000+rt_priority)，選擇權值最高的任務使用cpu。

  4，如果就緒隊列中的RR任務時間片為0，則會根據nice值設定該任務的時間片，同時将該任務放入就緒隊列的末尾。重複步驟3。

  5，目前任務由于等待資源而主動退出cpu，則其加入等待隊列中。重複步驟3。

  系統中既有分時排程，又有時間片輪轉排程和先進先出排程

  1，RR排程和FIFO排程的程序屬于實時程序，以分時排程的程序是非實時程序。