Real-Time Scheduling And Reliability In Cyber-Physical Systems

In recent years,the rapid growth of Cyber-Physical Systems(CPSs)has attracted a lot of interests from both industrial and academic communities.A CPS is a system where phys-ical components and computational components are tightly integrated.Tasks in a CPS gener-ally need to be accomplished correctly in terms of not only functionality but also punctuality.Therefore,CPS may either involve executing tasks on a processor or dispatching packets in a network,also the task patterns and requirements may be different.Real-time scheduling pro-vides the methodology of determining the task execution order on a shared resource in order to make as many tasks in a CPS as possible to meet their deadlines.In this thesis,depending on different applications,we study real-time task and packet scheduling problems in mixed-criticality systems,strictly periodic task systems and real-time wireless networks,respectively.The contributions of this work are as follows.(1)For mixed-criticality real-time systems,we develop new schedulability analysis meth-ods for EDF-VD algorithm.Different from previous methods that analyze each individual criticality level independently,our new analysis looks into system behavior across multiple criticality levels to obtain more precise analysis results.Experiments show that our new anal-ysis method can significantly improve guaranteed schedulability of EDF-VD,especially for systems with more criticality levels.The price paid for improved schedulability is higher anal-ysis complexity,but a combination of our new techniques and previous methods can obtain a good balance between the analysis accuracy and efficiency.(2)For strictly periodic task systems,we propose an efficient method to select time slots for strictly periodic tasks executing their first released instance to make all tasks be schedulable.Our method provides a sufficient condition to check the feasibility of a given task set,and returns the start time assignment if it is feasible.By exploring the relations among task periods,we further present a novel task selection method to improve the possibility of finding feasible start time configurations.Finally,we conduct experiments with randomly generated workload to evaluate the performance of the proposed method.(3)For real-time wireless networks(RTWNs),we introduce a novel distributed dynamic packet scheduling framework,referred to D2-PaS.D2-PaS aims to minimize the number of dropped packets while ensuring that all critical events due to disturbances are handled by their deadlines.D2-PaS builds on a number of observations that help reduce the scheduling over-head,and thus is efficient and scalable.Besides extensive simulation,D2-PaS has been im-plemented on an RTWN testbed to validate its applicability on real hardware.Both testbed measurements and simulation results confirm the effectiveness of D2-PaS.(4)For real-time wireless networks(RTWNs),we present a fully distributed packet scheduling framework called FD-PaS.FD-PaS aims to provide guaranteed fast response to unexpected disturbances while dropping a minimum number of packets for meeting the dead-lines of all critical tasks.To combat the scalability challenge,FD-PaS incorporates several key advances in both algorithm design and data link layer protocol design to enable individual nodes to make on-line decisions locally without any centralized control.Our extensive simula-tion and testbed results have validated the correctness of the FD-PaS design and demonstrated its effectiveness in providing fast response for handling disturbances.In summary,this dissertation studied various real-time task and packet scheduling prob-lems in cyber-physical systems including mixed-criticality systems,strictly periodic task sys-tems and real-time wireless networks.The findings in the thesis provides some theoretical foundations as well as practical insights for CPS design.