EDF多任務調度算法在物聯網數據監控平臺中的應用研究*

李文超

(東營職業學院 東營 257091)

摘  要　在基于物聯網的數據監控平臺中，由于感知層數據采集傳感器具有種類繁多、數量龐大的特點，這就要求位于通信層的數據接收服務器必須要通過一種完善的多任務調度算法來實現對高并發通信的處理，以緩解服務器的通信壓力并保持處理的高效性。本文以物聯網數據監控平臺為出發點，探究通過引入EDF多任務調度算法來實現對高并發通信的處理，對EDF多任務調度算法的算法原理與調度流程進行了深入分析，并通過設計實驗論證算法的有效性。

關鍵詞　多任務調度算法，物聯網，監控平臺

中圖法分類號  TP393                文獻標識碼  A

0 引言

在基于物聯網的數據監控平臺中，由于其感知層數據采集傳感器具有種類繁多、數量龐大的特點，這就要求位于通信層的數據接收服務器必須要通過一種完善的多任務調度算法來實現對高并發通信的處理，以緩解服務器的通信壓力并保持處理的高效性^[1]。在基本的任務處理邏輯中，如果不采用多任務調度算法，那么系統不會自動終止已經運行的線程，一旦一個線程被創建并執行，則這個線程將會一直執行下去直至運行結束^[2]。在運行過程中，如果該線程遇到操作異常或I/O問題，可能會進入阻塞狀態或者中斷退出，一方面大量消耗了運行時間，另一方面操作安全性也得不到保障。為了解決上述問題，本文對EDF（Earliest Deadline First）多任務調度算法進行應用研究。此算法為搶占式調度算法，系統會根據線程優先級的不同實時地切換運行線程，將處理器資源分配給優先級更高的運行線程，以確保處理器利用率最大化^[3]。

1 參數定義

現將EDF多任務調度算法中相關參數定義如下：

1）C_i —— 表示任務i的最壞執行時間，即在最壞的運行狀態下中斷該任務所需要耗費的處理器時間；

2）D_i —— 表示任務i的絕對運行截止時間；

3）T_i —— 表示任務i的運行周期；

4）P_i —— 表示任務i的運行優先級；

5）U_s —— 表示對于周期性任務集合S而言，該任務集運行時對處理器資源的占用率，按照式（1）進行計算：

                                                                 （1）

2 算法原理

EDF多任務調度算法是動態優先級算法，任務優先級在初始時并不具備固定值。在EDF多任務調度算法中，決定任務優先級的只有其絕對運行截止時間D。絕對運行截止時間D與運行優先級P的關系為：

1）若D_i ＜ D_j ，則P_i ＞ P_j ；

2）若D_i ≥ D_j ，則P_i ≤ P_j 。

因此，在EDF多任務調度算法中，處理器總是優先執行絕對運行截止時間最早的任務，這就要求在系統運行過程中要明確當前所有活動任務及其絕對運行截止時間，從而確定下一步需要分配處理器資源的高優先級任務^[4]。對于一個任務集合，對其可用EDF多任務調度算法進行任務調度的必要條件是：該任務集運行時對處理器資源的占用率U_s ＜1。

EDF多任務調度算法的主要步驟為：

1）對當前任務隊列中已處于就緒狀態的任務進行檢查；

2）獲取所有已就緒任務的（絕對）運行截止時間；

3）選擇具有最早截止時間的任務，為其賦予最高優先級^[5]。

3 算法分析

本小節將通過一個具體任務調度實例對EDF多任務調度算法進行分析。現有一個周期性任務集如下表1所示，其中包含T1、T2和T3三個周期性任務。

表1 任務集信息

首先，根據式（1）對該任務集運行時對處理器資源的占用率U_s進行計算：

                                                 （2）

由式（2）可知，該任務集符合使用EDF多任務調度算法進行任務調度的前提條件。該任務集具體任務調度過程如圖1所示（白色代表任務處于掛起狀態，黑色代表任務處于執行狀態）。

圖1 任務調度過程

調度過程分析：

1）（0ms）初始任務集包含T1、T2和T3三個任務，其任務開始時間相同，此時T3任務擁有最早截止時間，故將T3任務優先級調至最高，優先執行T3任務；

2）（10ms）T3任務執行完畢后，此時任務集中還剩T1、T2兩個任務，由于T2任務擁有最早截止時間，故獲得處理器資源開始運行；

3）（20ms）T2任務執行完畢后，此時任務集中只剩T1一個任務，獲得處理器資源開始運行；

4）（40ms）T1任務執行完畢后，此時任務集中含有T2、T3兩個任務，其中T3任務擁有最早截止時間，故T3任務獲得處理器資源開始運行；

5）（50ms）T3任務執行完畢后，此時任務集中包含T1、T2兩個任務，由于T2任務擁有最早截止時間，故T2任務獲得處理器資源開始運行；

6）（60ms）T2任務執行完畢后，此時任務集中包含T1、T3兩個任務，其中T3任務擁有最早截止時間，故T3任務獲得處理器資源開始運行；

7）（70ms）T3任務執行完畢后，此時任務集中只剩T1一個任務，獲得處理器資源開始運行；

8）（90ms）T1任務執行完畢，此時任務集中含有T2、T3兩個任務，其中T3任務擁有最早截止時間，故T3任務獲得處理器資源開始運行；

9）（100ms）T3任務執行完畢后，此時任務集中包含T1、T2兩個任務，由于T2任務擁有最早截止時間，故T2任務獲得處理器資源開始運行；

10）（110ms）T2任務執行完畢后，此時任務集中只剩T1一個任務，獲得處理器資源后開始運行；

11）（120ms）T1任務尚未運行完畢，但此時T3任務新加入任務集，任務集中所含的T1、T2和T3三個任務中T3具備最早截止時間，故掛起任務T1并將處理器資源分配給T3優先執行；

12）（130ms）T3任務執行完畢后，此時任務集中包含掛起的任務T1和新建的任務T2，由于T1任務擁有最早截止時間，故T1任務獲得處理器資源開始運行；

13）（140ms）T1任務執行完畢后，此時任務集中只剩T2一個任務，獲得處理器資源后開始運行。

值得注意的是，在此調度過程的第120ms時，盡管T1任務尚未運行完畢，但此時周期性任務T3新加入任務集，而且在任務集中所包含的T1、T2和T3三個任務中，任務T3具備最早截止時間，所以要對任務T1進行掛起操作并將處理器資源分配給T3優先執行。

此調度方案充分保證了對處理器資源的高效利用，是一種最優的單處理器動態調度算法，非常適用于在物聯網監控平臺中進行數據采集端的請求處理操作。

4 實驗對比分析

對于面向物聯網的數據監控平臺，其多任務處理主要包括對心跳數據和傳感器實體信息數據的處理兩種操作，通過統計多次實際任務操作時間取平均值，估算出單個心跳數據任務的執行時間約為100ms（接收心跳包并完成確認），單個傳感器實體信息數據處理任務的執行時間約為500ms（接收傳感器數據并寫入至數據庫）。監控平臺數據處理為I/O密集型任務，單任務處理的CPU占用率較低，據式（1）可知符合使用EDF多任務調度算法進行任務調度優化的條件要求。

通過程序模擬一個任務集合，其中包括心跳數據任務500個，傳感器實體信息數據處理任務100個，對面向物聯網的數據監控平臺使用EDF多任務調度算法進行多任務調度優化，并與不采用任何多任務調度算法情況下的任務處理時間進行對比，共進行10次實驗，實驗結果如圖2所示。

圖2 多任務優化對比分析

分析實驗結果可知，不采用任何多任務調度算法的任務集運行時間總體維持在100s~120s區間，采用EDF多任務調度算法的任務集運行時間大致維持在60s~80s區間，大大提升了多任務處理的執行效率。

5 結束語

本文以物聯網數據監控平臺為出發點，探究通過引入EDF多任務調度算法來實現對高并發通信的處理，以緩解服務器通信壓力并保持處理的高效性。本文對EDF多任務調度算法的算法原理和調度流程進行了深入分析，并通過設計實驗論證了此算法的有效性，證實此調度方案充分保證了對處理器資源的高效利用，非常適用于在物聯網數據監控平臺中進行數據采集端的請求處理操作，為物聯網數據監控平臺的通信優化提供了切實可行的思路。

參考文獻

[1]何琨. 多任務調度問題的研究與實現[D].華中科技大學,2006.

[2]同愛麗. 實時多任務調度方法研究與應用[D].西北工業大學,2006.

[3]李琦,巴巍. 兩種改進的EDF軟實時動態調度算法[J]. 計算機學報,2011,05:943-950.

[4]袁暋,檀明,周晶晶. EDF調度算法可調度性分析方法的改進研究[J]. 計算機應用研究,2013,08:2429-2431.