Schedulability Analysis Algorithms For Distributed Hard Real-Time Systems

With the wide adoption of distributed real-time system in many areas,such as electronics,aerospace,military,automobile electronics,industry production,much attention has been focused on system schedulability analysis algorithm,which is an important verification method for system schedulability. Many researchers have done a lot of research in schedulability analysis algorithm and have achieved many results. Among many approaches of schedulability analysis,worst-case response time based approach has many benefits over other approaches. So much of the theory research has been focused on this approach and it is used in many real world applications.Compared to uni-processor real-time system,distributed real-time system is more complicated and has its own characteristics. In the schedulability analysis of such system,firstly we should account for the overhead of message communication between tasks. Secondly,we should account for the influence of different task synchronization protocols to schedulability analysis algorithm. Lastly,worst-case response time of all the tasks and messages in the system should be analyzed holisticly because they are inter-dependent.Our research in this thesis is divided into two parts. In the first part,our main goal is to derive the overhead of messages communications in distributed real-time systems. In the second part,according to different task synchronization protocols,we derive task transaction worst-case response time analysis algorithms respectively.In the research of the first part,this thesis proposed an improved worst-case response time analysis algorithm of messages based on deferred preemption,and this algorithm solved the completeness of Tindell algorithm. By using a more general message release model,this thesis improved Tindell algorithm again. After carefully accounting for the overlap of message worst-case response time and message delivery time,this thesis also proposed a more accurate end-to-end message worst-case response time anaylsis algorithm. And this thesis also analyzed the characteristics of packet receiving interrupt handler and it's max interference on the other tasks on the same processor with lower priorities. Finally,this thesisproposed a message worst-case response time analysis algorithm for a simplified task model and made performance estimation for these algorithms.In the research of the second part,after a brief introduction of DS(Direct synchronization) and PM(Phase modification) task synchronization protocols,this thesis proposed the task transaction worst-case response time analysis algorithm respectively. Then,considering cons and pros of DS and PM protocols,this thesis proposed a new task synchronization protocol called DS/PM protocol. This new protocol can solve part of problems in previouse two protocols. Finally,this thesis proposed a task tranaction worst-case response time analysis algorithm for DS/PM protocol and made performance estimation for these algorithms.