面向CPS节点操作系统的混合调度系统研究与设计

doi:10.3969/j.issn.1000-436X.2013.12.010

摘要/Abstract

摘要：

针对CPS 物联性、互联性和智联性的新挑战，设计了具有实时性、灵活性及适应性特点的面向CPS 节点操作系统的混合调度系统。在深入研究事件驱动与多线程两种调度机制本质区别的基础上，设计了协作式多线程和混合栈管理相结合的带有适配器机制的混合编程模型以及支持事件与线程2种任务类型的混合调度模型，并采用合理的实时算法加以实现验证。实验测试表明本调度系统在实时性能指标上明显优于 TinyOS，更符合 CPS的属性要求。

关键词: 物理信息融合系统, 节点操作系统, 调度系统, 编程模型

Abstract:

In accordance with the new characteristics of physical,internet and intelligence of CPS,a hybrid scheduling system was designed for CPS node operating system with real-time performance,flexibility,and adaptability.Based on the in-depth study of the intrinsic differences between event-driven scheduling mechanism and multithreaded one,a hybrid programming model was designed that combines collaborative multithread and hybrid stack management using adapter mechanism.A hybrid scheduling model was also designed that supports both event and thread task types.Reasonable real-time algorithms were implemented for verification.Experimental results show that the real-time per-formance of the scheduling system is obviously better than that of TinyOS,thus it is better suited for CPS than TinyOS does.

Key words: cyber physical systems, node operating system, scheduling system, programming model

杜晓舟,曹晨红,乔建忠,林树宽. 面向CPS节点操作系统的混合调度系统研究与设计[J]. 通信学报, 2013, 34(12): 84-93.

Xiao-zhou DU,Chen-hong CAO,Jian-zhong QIAO,Shu-kuan LIN. Research and design of hybrid scheduling system of node operating system for cyber physical systems[J]. Journal on Communications, 2013, 34(12): 84-93.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

图10

参考文献 30

[1]	EDWARD A L , SANJIT A S . Introduction to embedded systems,a cyber-physical systems approach[EB/OL]. .
[2]	MARBURGER J H , KVAMME E F , SCALISE G , et al. Leadership under Challenge:Information Technology R＆D in a Competitive World.An Assessment of the Federal Networking and Information technology R＆D Program[R]. 2007.
[3]	李建中，高宏，于博 . 信息物理融合系统(CPS)的概念、特点、挑战和研究进展[R]. 2010. LI J Z , GAO H , YU B . The Concept,Characteristics,Challenges and Research Progress of CPS[R]. 2010.
[4]	李仁发，谢勇，李蕊等. 信息—物理融合系统若干关键问题综述[J]. 计算机研究与发展， 2012,49(6):1149-1161. LI R F , XIE Y , LI R , et al. Survey of cyber-physical systems[J]. Jour-nal of Computer Research and Development, 2012,49(6):1149-1161.
[5]	LEE E A . CPS foundations[A]. Proceedings of the 47th Design Auto-mation Conference[C]. Anaheim,California,USA, 2010.737-742.
[6]	MALKHI D , CORBATO F J , EMERSON E A , et al. Systems archi-tecture,design,engineering,and verification-the practice in research and research in practice[A]. ACM Turing Centenary Celebration[C]. New York,NY,USA, 2012.
[7]	WU F J , KAO Y F , TSENG Y C . From wireless sensor networks to-wards cyber physical systems[J]. Pervasive and Mobile Computing, 2011,7(4):397-413.
[8]	LEVIS P , MADDEN S , POLASTRE J , et al. Ambient Intelligence[M]. Berlin Heidelberg:Springer, 2005.
[9]	DUNKELS A , GRONVALL B , VOIGT T . Contiki-a lightweight and flexible operating system for tiny networked sensors[A]. Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks[C]. Tampa,FL,USA, 2004.455-462.
[10]	HAN C C , KUMAR R , SHEA R , et al. A dynamic operating system for sensor nodes[A]. Proceedings of the 3rd International Conference on Mobile Systems,Applications,and Services[C]. Seattle,WA,USA, 2005.163-176.
[11]	BHATTI S , CARLSON J , DAI H , et al. MANTIS OS:an embedded multithreaded operating system for wireless micro sensor platforms[J]. Mobile Networks and Applications, 2005,10(4):563-579.
[12]	ESWARAN A , ROWE A , RAJKUMAR R . Nano-rk:an energy-aware resource-centric rtos for sensor networks[A]. Proceedings of the 26th IEEE Real-Time Systems Symposium(RTSS 2005)[C]. Miami,FL,USA, 2005.256-265.
[13]	LORINCZ K , RONG C B , WATERMAN J , et al. Pixie:an operating system for resource-aware programming of embedded sensors[A]. Fifth Annual IEEE International Conference on Pervasive Comput ng and Communications Workshops[C]. Charlottesville,Virg nia,USA, 2008.267-271.
[14]	CAO Q , ABDELZAHER T , STANKOVIC J , et al. The liteos operat-ing system:towards unix-like abstractions for wireless sensor net-works[A]. Proceedings of the 7th International Conference on Infor-mation Processing in Sensor Networks[C]. St Louis,Missouri,USA, 2008.233-244.
[15]	CHA H , CHOI S , JUNG I , et al. RETOS:resilient,expandable,and threaded operating system for wireless sensor networks[A]. Proceed-ings of the 6th International Conference on Information Processing in Sensor Networks[C]. Cambridge,MA,USA, 2007.148-157.
[16]	DONG W , CHEN C , LIU X , et al. SenSpire OS:a predictable,flexible,and efficient operating system for wireless sensor networks[J]. IEEE Transactions on Computers, 2011,60(12):1788-1801.
[17]	DU X Z , QIAO J Z , LIN S K , et al. The design of node operating system for cyber physical systems[J]. Procedia Engineering, 2012,29:3717-3721.
[18]	SUGIHARA R , GUPTA R K . Programming models for sensor net-works:A survey[J]. ACM Transactions on Sensor Networks(TOSN), 2008,4(2):8.
[19]	BERNAUER A , R?MER K , SANTINI S , et al. Threads2events:an automatic code generation approach[A]. Proceedings of 6th Work-shop on Hot Topics in Embedded Networked Sensors[C]. Killarney,Ireland, 2010.8-12 .
[20]	MOUBARAK M , WATFA M K . Guide to Wireless Sensor Net-works[M]. London:Springer, 2009.
[21]	MCCARTNEY W P , SRIDHAR N . Abstractions for safe concurrent programming in networked embedded systems[A]. Proceedings of the 4th International Conference on Embedded Networked Sensor Sys-temsp[C]. Boulder,CO,USA, 2006.167-180.
[22]	WELSH M , MAINLAND G . Programming sensor networks using abstract regions[A]. NSDI[C]. San Francisco,California,USA, 2004.3.
[23]	KLUES K , LIANG C J M , PAEK J , et al. TOSThreads:thread-safe and non-invasive preemption in TinyOS[A]. Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems[C]. Berkeley,California,USA, 2009.127-140.
[24]	DUNKELS A , SCHMIDT O , VOIGT T , et al. Protothreads:simplify-ing event-driven programming of memory-constrained embedded sys-tems[A]. Proceedings of the 4th International Conference on Embed-ded Networked Sensor Systems[C]. Boulder,Colorado,USA, 2006.29-42.
[25]	TRUMPLER E , HAN R . A systematic framework for evolving Ti-nyOS[A]. Proceedings of the Third IEEE Workshop on Embedded Networked Sensors[C]. Cambridge,MA,USA, 2006.61-65.
[26]	DONG W , CHEN C , LIU X , et al. FIT:a flexible,lightweight,and real-time scheduling system for wireless sensor platforms[J]. IEEE Transactions on Parallel and Distributed Systems, 2010,21(1):126-138.
[27]	KOPJAK J , KOVáCS J . Event-driven control program models run-ning on embedded systems[A]. Proceedings of the 6th IEEE Interna-tional Symposium on Applied Computational Intelligence and Infor-matics(SACI)[C]. Timisoara,Romania, 2011.323-326.
[28]	CHU R , GU L , LIU Y , et al. Versatile stack management for multi-tasking sensor networks[A]. Proceedings of the 30th International Conference on Distributed Computing Systems(ICDCS)[C]. Genoa,Italy, 2010.388-397.
[29]	ADYA A , HOWELL J , THEIMER M , et al. Cooperative task manage-ment without manual stack management[A]. Proceedings of USENIX 2002 Annual Technical Conference[C]. Monterey,CA,USA, 2002.289-302.
[30]	KESKIN U , BRIL R J , LUKKIEN J J . Exact response-time analysis for fixed-priority preemption-threshold scheduling[A]. Proceedings of the 15th Conference on Emerging Technologies and Factory Automa-tion (ETFA)[C]. Bilbao,Spain, 2010.1-4.

	本地任务		转发任务
任务	执行时间/ms	周期/ms	任务	执行时间/ms	截止期/ms
T_l1	40	200	T_t1	60	160
T_l2	80	300	T_t2	80	200
T_l3	120	400	T_t3	100	240
T_l4	160	500	—	—	—
T_l5	200	500	—	—	—