批作業排程算法

目錄

• 批作業排程算法
  • 首先理清概念：
  • 常用的作業排程算法：

​ 作業周轉時間 = 完成時間 - 送出時間

​ 作業的帶權周轉時間 = 作業的周轉時間 / 運作時間

​ 平均周轉時間 = 各作業的帶權周轉時間之和 / 作業數目

• 先來先服務算法（First Come Serve ， FCFS）

  是按作業進入系統的先後次序進行排程，即每次排程都在後被作業中選擇一個最先進入隊列的作業

  特點：實作簡單，有利于長作業，不利于短作業**

  示例：

起始：

作業	送出時間	運作時間(min)	開始時間	結束時間	周轉時間 Ti /min	帶權周轉時間 Wi /min
J1	8:00	60
J2	8:50	30
J3	9:00	12
J4	9:10	6

第一輪：

1. 先選擇先來的，即先送出的 J1 ：8：00 ，将其作為第一個開始的，由于他前面沒有等待隊列，是以它的開始時間為：

   8：00。

2. 結束時間為開始時間加上運作時間：

   8：00 + 60min = 9：00

3. 周轉時間為：完成時間(結束時間) - 送出時間 =

   9:00

   -

   8:00

   = 60min
4. 帶權周轉時間 : 作業的周轉時間 / 運作時間 =

   60

   /

   60

   = 1

						帶權周轉時間 Wi
			8：00	9：00		1

第二輪：

1. 由于按照先來先選擇的算法，選l擇第二的， J1 ：8：50 ，将其作為第二，由于他還需要等待他前面的完成了才到他，是以它的開始時間為：

   9：00。

2. 結束時間為：開始時間 + 運作時間 =

   9：00 + 30min = 9：30

3. 9:30

   8:50

   = 40min

4. 40

   30

   = 4/3

				9：30	40	4/3

剩下的以此類推。。。

最終為：

				9：42	42	21/6
				9：48	38	19/3

平均周轉時間 = 各作業的帶權周轉時間之和 / 作業數目

​ = (1+4/3+21/6+19/)/4 ≈ 3.0417

• 最短作業優先（Shortest Job First SJF）

  總是選擇估計計算時間最短的作業投入運作

  特點：克服了FCFS 偏愛長作業的缺點，易于實作，會使系統平局周轉時間最短，系統吞吐量大；缺點是：1）需要預先知道作業所需的CPU時間 2）護士了作業等待時間，容易出現饑餓想象

1. 由于J1是最先來的，此時沒有别的等待隊列，故先進行J1 ，是以它的開始時間為：

   8：00。

2. 8：00 + 60min = 9：00

3. 9:00

   8:00

   = 60min

4. 60

   60

1. 選取在第一輪執行結束之後的時間之前

   9：00

   提前的作業中運作時間最低段的作為第二輪作業，即：在

   J2：8：50

   與

   J3：9：00

   中選取運作時間最短的，即J3.是以第二輪的開始時間為：

   9：00。

2. 9：00 + 12min = 9：12

3. 9:12

   9:00

   = 12min

4. 12

   12

				9：12

第三輪：

1. 選取在第二輪執行結束之後的時間之前

   9：12

   J2：8：50

   J4：9：10

   中選取運作時間最短的，即J4.是以第二輪的開始時間為：

   9：12。

2. 9：12 + 6min = 9：18

3. 9:18

   9:10

   = 8min

4. 8

   6

				9：18	8

同理可得第四輪結果為：

					58	29/15

​ = (1+29/15+1+4/3)/4 ≈ 1.3167

• 響應比高者優先算法（Highest Response Ratio First ,HRRF）

  計算後備作業隊列中每個作業的響應比，然後挑選響應比最高者。

  其中響應比計算公式為：\(\frac {作業的響應時間}{作業的運作時間}\) = \(\frac {作業的等待時間+作業的運作時間}{作業的運作時間}\)= 1+ \(\frac {作業的等待時間}{作業的運作時間}\)

  特點：即考慮作業的等待時間，有考慮作業的運作時間，是介于上述兩種算法的折中算法。缺點是每次都要計算各道的作業響應比，有一定的時間開銷。

  1. 首先還是一樣的先執行第一個送出的作業J1，是以送出時間時間即為運作時間：

     8：00

     ，

  2. 8：00 + 60min = 9：00

  1. 9:00

     8:00

  2. 60

     60

  3. 更新第一輪結束時間之前送出的作業的等待時間。

     顯然，滿足條件（在結束時間9：00之前送出作業的）有J2,J3

     ​ 等待時間為：

     上個作業結束時間

     該作業送出時間

     ​ 顯然，J1 = 0

     ​ J2 = 9：00 - 8：50 = 10

     ​ J3 = 9：00 - 9：00 = 0

					等待時間/min
			10

1. 首先在滿足條件（在第一輪完成時間之前送出的作業）中選取響應比最大的作為第二輪作業任務
   • J2 = 1 + 10/30
   • J3 = 1 + 0/12

   顯然，響應比：J2 > J3

   是以選取J2作為第二輪的任務，其開始時間為

   第一輪結束時間

   ：9：00

2. 9：00 + 30min = 9：30

1. 8：50

   9:30

2. 40

   30

3. 更新第二輪結束時間之前送出的作業的等待時間。

   顯然，滿足條件（在結束時間9：30之前送出作業的）有J3,J4

   上個作業結束時間

   該作業送出時間

   ​ J3 = 9：30 - 9：00 = 30

   ​ J4 = 9：30 - 9：10 = 20

   ​

			20

1. 首先在滿足條件（在第二輪完成時間之前送出的作業）中選取響應比最大的作為第二輪作業任務
   • J3 = 1 + 30/12
   • J4 = 1 + 20/6

   顯然，響應比：J4 > J3

   是以選取J4作為第三輪的任務，其開始時間為

   第二輪結束時間

   ：9：30

2. 9：30 + 6min = 9：36

1. 9：36

   9:10

   = 26min

2. 26

   6

   = 13/3
3. 顯然，滿足條件（在結束時間9：36之前送出作業的）有J3

   上個作業結束時間

   該作業送出時間

   ​ J3 = 9：36 - 9：00 = 36

			36
				9：36		26	13/3

同理可得第四輪結果：

						48	4