一种多处理器平台上的传感器事务调度算法

计算机工程与科学

一种多处理器平台上的传感器事务调度算法

白天1，李国徽2

（1.湖南理工学院计算机学院，湖南岳阳 414000；
2.华中科技大学计算机科学与技术学院，湖北武汉 430074）

收稿日期:2015-11-20 修回日期:2016-03-29 出版日期:2016-08-25 发布日期:2016-08-25
基金资助:
国家自然科学基金（61173049）;湖南省自然科学基金（2015JJ6044）

A sensor transaction scheduling algorithm on multiprocessor platforms

BAI Tian1,LI Guo-hui2

（1.College of Computer Science,Hunan Institute of Science and Technology,Yueyang 414000;
2.College of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China）

Received:2015-11-20 Revised:2016-03-29 Online:2016-08-25 Published:2016-08-25

摘要/Abstract

摘要：

如何有效地调度传感器事务以维护数据的时态一致性是信息物理融合系统研究中的一个重要问题。已有的调度算法基本上都是针对单处理器平台来设计的。提出一种多处理器平台上的传感器事务调度算法，算法通过合理地分配和调整事务实例执行所需处理器资源来保证数据的时态一致性约束，通过预先计算出全局重复调度序列来降低运行开销，给出了算法的可调度性分析。实验结果表明，该算法具有较高的调度成功率，其产生的更新负载也较低。

关键词: 信息物理融合系统, 传感器事务, 时态一致性, 多处理器调度

Abstract:

How to schedule sensor transactions to maintain data validity is an important research topic for cyber physical systems. Previous studies are generally restricted to uni-processor platforms. We therefore propose a sensor transaction scheduling algorithm on multiprocessor platforms. The algorithm appropriately allocates and adjusts the processors’ resources for each update instance to satisfy temporal consistency constraints. It calculates the global repeating schedule segment off-line in advance to reduce the runtime overhead. The schedulability analysis of the algorithm is also given. Experimental results show that the proposed algorithm performs well in terms of scheduling success ratio and update workload.

Key words: cyber-physical systems, sensor transactions, temporal consistency, multiprocessor scheduling

白天1，李国徽2. 一种多处理器平台上的传感器事务调度算法[J]. 计算机工程与科学.

BAI Tian1,LI Guo-hui2. A sensor transaction scheduling algorithm on multiprocessor platforms [J]. Computer Engineering & Science.

参考文献

［1］Rajkumar R,Lee I,Sha L,et al.Cyber-physical systems:The next computing revolution［C］∥Proc of the 47th ACM/IEEE Design Automation Conference (DAC),2010:731-736.
［2］He Ji-feng. Cyber-physical systems［J］.Communications of the China Computer Federation,2010,6(1):25-29.(in Chinese)
［3］Wang J,Han S,Lam K Y,et al.Maintaining data temporal consistency in distributed real-time systems ［J］.Real-Time Systems,2012,48(4):387-429.
［4］Xiong M,Ramamritham K.Deriving deadlines and periods for real-time update transactions ［J］.IEEE Transactions on Computers,2004,53(5):567-583.
［5］Xiong M,Wang Q,Ramamritham K.On earliest deadline first scheduling for temporal consistency maintenance ［J］.Real-Time Systems,2008,40(2):208-237.
［6］Li J,Xiong M,Lee V C S,et al.Workload-efficient deadline and period assignment for maintaining temporal consistency under EDF［J］.IEEE Transactions on Computers,2013,62(6):1255-1268.
［7］Han S,Chen D,Xiong M,et al.Schedulability analysis of deferrable scheduling algorithms for maintaining real-time data freshness ［J］.IEEE Transactions on Computers,2014,63(4):979-994.
［8］Xiong M, Han S, Chen D, et al.DESH:Overhead reduction algorithms for deferrable scheduling ［J］.Real-Time Systems,2010,44(1-3):1-25.
［9］Wang J,Lam K Y, Han S,et al.An effective fixed priority co-scheduling algorithm for periodic update and application transactions ［J］.Computing,2013,95(10-11):993-1018.
［10］Han S, Lam K Y, Wang J, et al. On co-scheduling of update and control transactions in real-time sensing and control systems:Algorithms,analysis,and performance ［J］.IEEE Transactions on Knowledge and Data Engineering,2013,25(10):2325-2342.
［11］Zhu X,Huang P C,Han S,et al.MinMax: A sampling interval control algorithm for process control systems ［C］∥Proc of IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications,2012:68-77.
［12］Davis R I,Burns A.A survey of hard real-time scheduling for multiprocessor systems ［J］.ACM Computing Surveys,2011,43(4):1-44.
［13］Qos management for embedded databases in multicore-based embedded systems［EB/OL］.［2015-03-16］.http://www.hindawi.com/journals/misy/2015/657252/.
［14］Li J,Chen J,Xiong M,et al.Workload-aware partitioning for maintaining temporal consistency upon multiprocessor platforms［C］∥Proc of the 2011 IEEE 32nd Real-Time Systems Symposium,2011:126-135.
［15］Guan N, Stigge M, Wang Y, et al.New response time bounds for fixed priority multiprocessor scheduling［C］∥Proc of the 30th IEEE Real-Time Systems Symposium,2009:387-397.
附中文参考文献：
［2］何积丰.信息物理融合系统［J］.中国计算机学会通讯,2010,6(1):25-29.

[1]	张晶, 袁振宇. 基于增广混合Petri网的CPS事件建模[J]. 计算机工程与科学, 2020, 42(03): 550-556.
[2]	蒋俊，黄传河，华超，胡海桥，彭晖. 基于软件定义资源的实时控制CPS数据传输机制[J]. J4, 2015, 37(12): 2250-2255.
[3]	曹科宁1,2，李仁发1，张小明1，张鑫龙1. 面向CPS复杂事件流的不确定性研究[J]. J4, 2015, 37(03): 415-421.
[4]	周本海，姚大鹏. 信息物理系统中基于保护阈值的实时调度算法研究[J]. J4, 2015, 37(02): 226-230.