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.