Computer Science ›› 2016, Vol. 43 ›› Issue (Z11): 523-528, 535.doi: 10.11896/j.issn.1002-137X.2016.11A.118

Previous Articles     Next Articles

Analyzing Scheduling Based on Priority in Concurrent Systems

ZHU Zhen-yu, ZHANG Shi, JIANG Jian-min, WU Ya-zhou and YANG Qi-fan   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Due to the complexity of the concurrent system,it is difficult for engineers to develop a complex system as a whole directly.They often apply informal principles,such as modular,stepwise refinement and information hiding,to guide system development.These guidelines are abstract and can’t guarantee the correct decomposition of system.In this paper,we focused on the system decomposition method based on priority,proposed a method to decompose the system,and proved its correctness.First,we modeled system with an event-based behavioral model.Next,based on such a model,we formally defined the schedule,the scheduling policy and the correctness of a scheduling policy.After that,we proposed a method for decomposing schedule policy,and proved the method’s correctness.Finally,according to the decentralized method,we developed a toolkit,which supports event-based behavioral model,for modeling system and decomposition of scheduling policy.An experiment demonstrates that these results may help engineers to design correct and efficient schedule policies in a system to realize decomposition.

Key words: Priority,Scheduling policy,Decomposition,Correctness

[1] Wing J,et al.Cyber-Physical Systems Summit summary report[R].the April 2008 CPS Summit,St.Louis,MO,2008
[2] Alur R,Courcoubetis C,et al.The algorithmic analysis of hybrid systems[J].Theoretical Computer Science,1995,138:3-34
[3] Bliudze S,Sifakis J.The algebra of connectors:structuring interaction in BIP[C]∥EMSOFT.ACM,2007:11-20
[4] Eidson J C,Lee E A,Matic S,et al.Distributed Real-Time Software for Cyber-Physical Systems[J].Proceedings of the IEEE,2012,100(1):45-59
[5] Jiang J,Zhang S,et al.Configuring business process models[J].ACM SIGSOFT Software Engineering Notes,2013,38(4):1-10
[6] Jiang J,Zhu H,et al.Configuration of Services based on Virtualization[C]∥TASE.2014:178-184
[7] Tan Y,Vuran M C,Goddard S,et al.A concept lattice-based event model for cyber-physical systems[C]∥ICCPS.2010:50-60
[8] Talcott C.Cyber-Physical Systems and Events[M].Software-Intensive Systems and New Computing Paradigms.Berlin,Heidelberg:Springer-Verlag,2008:101-115
[9] Bornot S,Ga G,Sifakis G J.On the construction of live timed systems[M].Graf S,Schwartzbach M.eds.,2000:109-126
[10] Altisen K,Gssler G,Sifakis J.Scheduler modeling based on the controller synthesis paradigm[J].Journal of Real-Time Systems,Special Issue on Control Theoretical Approaches to Real-time Computing,2002,23(1/2):55-84
[11] Zhang F,Szwaykowska K,Wolf W,et al.Task scheduling for control oriented requirements for cyber physical systems[C]∥Real-Time Systems Symposium.2008:47-56
[12] Li Q.Scheduling in Cyber-Physical Systems[J].Dissertations,2012:91
[13] Li Q,Negi R.Maximal scheduling in wireless ad hoc networks with hypergraph interference models[J].IEEE Transactions on Vehicular Technology,2012,61(1):297-310
[14] Tang Q,Gupta S K S,Varsamopoulos G.A Unified Methodology for Scheduling in Distributed Cyber-Physical Systems.ACM Trans[J].Embedded Comput.Syst.,2012,11(S2):57
[15] Hennessy M,Lin H.Symbolic Bisimulations[J].Theor.Comput.Sci.,1995,138(2):353-389
[16] Jiang J,Zhang S,et al.Modeling and analyzing mixed communications in service-oriented trustworthy software[J].Science China Information Science,2012,55(12):2738-2756
[17] Lanese I,Bedogni L,Di Felice M.Internet of things:a process calculus approach[J].SAC,2013:1339-1346
[18] Winskel G,Nielsen M.Models for Concurrency,Handbook ofLogic in Computer Science,Semantic Modelling[J].Oxford Science Publications,Oxford,1995,4:1-148
[19] Jiang J,Zhang S,et al.Configuring business process models[J].ACM SIGSOFT Software Engineering Notes,2013,38(4):1-10
[20] Jiang J,Zhang S,et al.Message Dependency-Based Adaptation of Services[J].APSCC,2011:442-449
[21] Finkel A,Leroux J.Recent and simple algorithms for Petri nets[J].Software & Systems Modeling,2015,4(2):719-7251
[22] Folschette M,Paulevé L,Magnin M,et al.Sufficient Conditions for Reachability in Automata Networks with Priorities[J].Theoretical Computer Science,2015,608:66-83

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .