EDF多任務(wù)調(diào)度算法在物聯(lián)網(wǎng)數(shù)據(jù)監(jiān)控平臺(tái)中的應(yīng)用研究*

李文超

(東營(yíng)職業(yè)學(xué)院 東營(yíng) 257091)

摘  要　在基于物聯(lián)網(wǎng)的數(shù)據(jù)監(jiān)控平臺(tái)中，由于感知層數(shù)據(jù)采集傳感器具有種類繁多、數(shù)量龐大的特點(diǎn)，這就要求位于通信層的數(shù)據(jù)接收服務(wù)器必須要通過(guò)一種完善的多任務(wù)調(diào)度算法來(lái)實(shí)現(xiàn)對(duì)高并發(fā)通信的處理，以緩解服務(wù)器的通信壓力并保持處理的高效性。本文以物聯(lián)網(wǎng)數(shù)據(jù)監(jiān)控平臺(tái)為出發(fā)點(diǎn)，探究通過(guò)引入EDF多任務(wù)調(diào)度算法來(lái)實(shí)現(xiàn)對(duì)高并發(fā)通信的處理，對(duì)EDF多任務(wù)調(diào)度算法的算法原理與調(diào)度流程進(jìn)行了深入分析，并通過(guò)設(shè)計(jì)實(shí)驗(yàn)論證算法的有效性。

關(guān)鍵詞　多任務(wù)調(diào)度算法，物聯(lián)網(wǎng)，監(jiān)控平臺(tái)

中圖法分類號(hào)  TP393                文獻(xiàn)標(biāo)識(shí)碼  A

0 引言

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

1 參數(shù)定義

現(xiàn)將EDF多任務(wù)調(diào)度算法中相關(guān)參數(shù)定義如下：

1）C_i —— 表示任務(wù)i的最壞執(zhí)行時(shí)間，即在最壞的運(yùn)行狀態(tài)下中斷該任務(wù)所需要耗費(fèi)的處理器時(shí)間；

2）D_i —— 表示任務(wù)i的絕對(duì)運(yùn)行截止時(shí)間；

3）T_i —— 表示任務(wù)i的運(yùn)行周期；

4）P_i —— 表示任務(wù)i的運(yùn)行優(yōu)先級(jí)；

5）U_s —— 表示對(duì)于周期性任務(wù)集合S而言，該任務(wù)集運(yùn)行時(shí)對(duì)處理器資源的占用率，按照式（1）進(jìn)行計(jì)算：

                                                                 （1）

2 算法原理

EDF多任務(wù)調(diào)度算法是動(dòng)態(tài)優(yōu)先級(jí)算法，任務(wù)優(yōu)先級(jí)在初始時(shí)并不具備固定值。在EDF多任務(wù)調(diào)度算法中，決定任務(wù)優(yōu)先級(jí)的只有其絕對(duì)運(yùn)行截止時(shí)間D。絕對(duì)運(yùn)行截止時(shí)間D與運(yùn)行優(yōu)先級(jí)P的關(guān)系為：

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

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

因此，在EDF多任務(wù)調(diào)度算法中，處理器總是優(yōu)先執(zhí)行絕對(duì)運(yùn)行截止時(shí)間最早的任務(wù)，這就要求在系統(tǒng)運(yùn)行過(guò)程中要明確當(dāng)前所有活動(dòng)任務(wù)及其絕對(duì)運(yùn)行截止時(shí)間，從而確定下一步需要分配處理器資源的高優(yōu)先級(jí)任務(wù)^[4]。對(duì)于一個(gè)任務(wù)集合，對(duì)其可用EDF多任務(wù)調(diào)度算法進(jìn)行任務(wù)調(diào)度的必要條件是：該任務(wù)集運(yùn)行時(shí)對(duì)處理器資源的占用率U_s ＜1。

EDF多任務(wù)調(diào)度算法的主要步驟為：

1）對(duì)當(dāng)前任務(wù)隊(duì)列中已處于就緒狀態(tài)的任務(wù)進(jìn)行檢查；

2）獲取所有已就緒任務(wù)的（絕對(duì)）運(yùn)行截止時(shí)間；

3）選擇具有最早截止時(shí)間的任務(wù)，為其賦予最高優(yōu)先級(jí)^[5]。

3 算法分析

本小節(jié)將通過(guò)一個(gè)具體任務(wù)調(diào)度實(shí)例對(duì)EDF多任務(wù)調(diào)度算法進(jìn)行分析。現(xiàn)有一個(gè)周期性任務(wù)集如下表1所示，其中包含T1、T2和T3三個(gè)周期性任務(wù)。

表1 任務(wù)集信息

首先，根據(jù)式（1）對(duì)該任務(wù)集運(yùn)行時(shí)對(duì)處理器資源的占用率U_s進(jìn)行計(jì)算：

                                                 （2）

由式（2）可知，該任務(wù)集符合使用EDF多任務(wù)調(diào)度算法進(jìn)行任務(wù)調(diào)度的前提條件。該任務(wù)集具體任務(wù)調(diào)度過(guò)程如圖1所示（白色代表任務(wù)處于掛起狀態(tài)，黑色代表任務(wù)處于執(zhí)行狀態(tài)）。

圖1 任務(wù)調(diào)度過(guò)程

調(diào)度過(guò)程分析：

1）（0ms）初始任務(wù)集包含T1、T2和T3三個(gè)任務(wù)，其任務(wù)開(kāi)始時(shí)間相同，此時(shí)T3任務(wù)擁有最早截止時(shí)間，故將T3任務(wù)優(yōu)先級(jí)調(diào)至最高，優(yōu)先執(zhí)行T3任務(wù)；

2）（10ms）T3任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中還剩T1、T2兩個(gè)任務(wù)，由于T2任務(wù)擁有最早截止時(shí)間，故獲得處理器資源開(kāi)始運(yùn)行；

3）（20ms）T2任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中只剩T1一個(gè)任務(wù)，獲得處理器資源開(kāi)始運(yùn)行；

4）（40ms）T1任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中含有T2、T3兩個(gè)任務(wù)，其中T3任務(wù)擁有最早截止時(shí)間，故T3任務(wù)獲得處理器資源開(kāi)始運(yùn)行；

5）（50ms）T3任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中包含T1、T2兩個(gè)任務(wù)，由于T2任務(wù)擁有最早截止時(shí)間，故T2任務(wù)獲得處理器資源開(kāi)始運(yùn)行；

6）（60ms）T2任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中包含T1、T3兩個(gè)任務(wù)，其中T3任務(wù)擁有最早截止時(shí)間，故T3任務(wù)獲得處理器資源開(kāi)始運(yùn)行；

7）（70ms）T3任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中只剩T1一個(gè)任務(wù)，獲得處理器資源開(kāi)始運(yùn)行；

8）（90ms）T1任務(wù)執(zhí)行完畢，此時(shí)任務(wù)集中含有T2、T3兩個(gè)任務(wù)，其中T3任務(wù)擁有最早截止時(shí)間，故T3任務(wù)獲得處理器資源開(kāi)始運(yùn)行；

9）（100ms）T3任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中包含T1、T2兩個(gè)任務(wù)，由于T2任務(wù)擁有最早截止時(shí)間，故T2任務(wù)獲得處理器資源開(kāi)始運(yùn)行；

10）（110ms）T2任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中只剩T1一個(gè)任務(wù)，獲得處理器資源后開(kāi)始運(yùn)行；

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

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

13）（140ms）T1任務(wù)執(zhí)行完畢后，此時(shí)任務(wù)集中只剩T2一個(gè)任務(wù)，獲得處理器資源后開(kāi)始運(yùn)行。

值得注意的是，在此調(diào)度過(guò)程的第120ms時(shí)，盡管T1任務(wù)尚未運(yùn)行完畢，但此時(shí)周期性任務(wù)T3新加入任務(wù)集，而且在任務(wù)集中所包含的T1、T2和T3三個(gè)任務(wù)中，任務(wù)T3具備最早截止時(shí)間，所以要對(duì)任務(wù)T1進(jìn)行掛起操作并將處理器資源分配給T3優(yōu)先執(zhí)行。

此調(diào)度方案充分保證了對(duì)處理器資源的高效利用，是一種最優(yōu)的單處理器動(dòng)態(tài)調(diào)度算法，非常適用于在物聯(lián)網(wǎng)監(jiān)控平臺(tái)中進(jìn)行數(shù)據(jù)采集端的請(qǐng)求處理操作。

4 實(shí)驗(yàn)對(duì)比分析

對(duì)于面向物聯(lián)網(wǎng)的數(shù)據(jù)監(jiān)控平臺(tái)，其多任務(wù)處理主要包括對(duì)心跳數(shù)據(jù)和傳感器實(shí)體信息數(shù)據(jù)的處理兩種操作，通過(guò)統(tǒng)計(jì)多次實(shí)際任務(wù)操作時(shí)間取平均值，估算出單個(gè)心跳數(shù)據(jù)任務(wù)的執(zhí)行時(shí)間約為100ms（接收心跳包并完成確認(rèn)），單個(gè)傳感器實(shí)體信息數(shù)據(jù)處理任務(wù)的執(zhí)行時(shí)間約為500ms（接收傳感器數(shù)據(jù)并寫入至數(shù)據(jù)庫(kù)）。監(jiān)控平臺(tái)數(shù)據(jù)處理為I/O密集型任務(wù)，單任務(wù)處理的CPU占用率較低，據(jù)式（1）可知符合使用EDF多任務(wù)調(diào)度算法進(jìn)行任務(wù)調(diào)度優(yōu)化的條件要求。

通過(guò)程序模擬一個(gè)任務(wù)集合，其中包括心跳數(shù)據(jù)任務(wù)500個(gè)，傳感器實(shí)體信息數(shù)據(jù)處理任務(wù)100個(gè)，對(duì)面向物聯(lián)網(wǎng)的數(shù)據(jù)監(jiān)控平臺(tái)使用EDF多任務(wù)調(diào)度算法進(jìn)行多任務(wù)調(diào)度優(yōu)化，并與不采用任何多任務(wù)調(diào)度算法情況下的任務(wù)處理時(shí)間進(jìn)行對(duì)比，共進(jìn)行10次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 多任務(wù)優(yōu)化對(duì)比分析

分析實(shí)驗(yàn)結(jié)果可知，不采用任何多任務(wù)調(diào)度算法的任務(wù)集運(yùn)行時(shí)間總體維持在100s~120s區(qū)間，采用EDF多任務(wù)調(diào)度算法的任務(wù)集運(yùn)行時(shí)間大致維持在60s~80s區(qū)間，大大提升了多任務(wù)處理的執(zhí)行效率。

5 結(jié)束語(yǔ)

本文以物聯(lián)網(wǎng)數(shù)據(jù)監(jiān)控平臺(tái)為出發(fā)點(diǎn)，探究通過(guò)引入EDF多任務(wù)調(diào)度算法來(lái)實(shí)現(xiàn)對(duì)高并發(fā)通信的處理，以緩解服務(wù)器通信壓力并保持處理的高效性。本文對(duì)EDF多任務(wù)調(diào)度算法的算法原理和調(diào)度流程進(jìn)行了深入分析，并通過(guò)設(shè)計(jì)實(shí)驗(yàn)論證了此算法的有效性，證實(shí)此調(diào)度方案充分保證了對(duì)處理器資源的高效利用，非常適用于在物聯(lián)網(wǎng)數(shù)據(jù)監(jiān)控平臺(tái)中進(jìn)行數(shù)據(jù)采集端的請(qǐng)求處理操作，為物聯(lián)網(wǎng)數(shù)據(jù)監(jiān)控平臺(tái)的通信優(yōu)化提供了切實(shí)可行的思路。

參考文獻(xiàn)

[1]何琨. 多任務(wù)調(diào)度問(wèn)題的研究與實(shí)現(xiàn)[D].華中科技大學(xué),2006.

[2]同愛(ài)麗. 實(shí)時(shí)多任務(wù)調(diào)度方法研究與應(yīng)用[D].西北工業(yè)大學(xué),2006.

[3]李琦,巴巍. 兩種改進(jìn)的EDF軟實(shí)時(shí)動(dòng)態(tài)調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào),2011,05:943-950.

[4]袁暋,檀明,周晶晶. EDF調(diào)度算法可調(diào)度性分析方法的改進(jìn)研究[J]. 計(jì)算機(jī)應(yīng)用研究,2013,08:2429-2431.