Research On Key Issues Of Mixed-Criticality Scheduling

A major trend in modern real-rime embedded systems, including automotive and avionics systems, safety-critical functionalities that must be certified to very high levels of assurance are designed to share a hardware platform with less critical software that are not subject to certification requirements in order to work around SWa P limiting.This kind of real-time scheduling research has yielded some promising techniques for meeting the dual goals of(â…°) being able to certify the safety-critical functionalities under very conservative assumption, and(â…±) ensuring high utilization of platform under less pessimistic assumption. The real-time scheduling of mixed-criticality systems has been recognized to be a challenging problem, where using traditional scheduling techniques cannot meet the two contradictory needs at the same time.In this dissertation, centering on the unbalanced requirement of satisfying the deadlines of safety- critical and non-critical tasks, several key issues have been researched, which include how the time of increasing criticality level and deadlines depending criticality level effect the scheduling of high-critical tasks. And scheduling low-critical tasks after increasing criticality level or re-scheduling low-critical tasks that have been discarded during criticality level switching is to improve high resource utilization. The main contributions of this dissertationare described as follows:(1) In real performing of mixed-criticality system, eventsoccurringout of systems, such as ambient temperaturechanging, trigger the criticality toswitch from low to high criticality level. Based on this fact a feasible schedulability analysis for high-critical task is achieved, considering the time of event triggering critical-level to affect the schedulability of mixed-criticality tasks. A sufficient condition for schedulable high-critical tasks is gained. Based on this schedulable condition an algorithm is designed to exchange priorities between two high-critical tasks at right time to make more high-critical tasks being meet deadlines. Simulation experiments bore out the sufficient schedulable condition and the increasing schedulable tasks percentage using the priority exchange algorithm.(2) A novel implementation scheme is proposed, which is for fixed priority uniprocessor scheduling of mixed criticality tasks with deadlines depended criticality levels. The mixed-criticality workload model is defined, which consisting of independent task set with deadlines as the critical parameter. Considering the low-critical task interference, we raise critical-level in advance(RCLA) to meet every critical deadline of high-critical tasks at cost of limited suspending low-critical tasks. Constrained or arbitrary deadlines of high-critical tasks are always met. Experimental results show the effectiveness of our RCLA algorithm, without being affected by the percentage of high-critical tasks or the ratio of high-critical deadlines to low-critical deadlines.(3) A semi-partitioned scheduling for mixed-criticality tasks is proposed, which perform on homogeneous multi-processors. Both high-critical workloads and low-critical tasks schedulability are taken into account, tasks are assigned to processors. High-critical tasks and most low-critical tasks are fixed tasks running on processors without allowing migration, and yet limited a few low-critical tasks, which is no more than the number of processors, can migrate once between two adjacentprocessors. Two parts of migrated tasks execute on different processors can be synchronized in running-time. Just a few of migrations can led to more schedulable tasks, and every processors allocated to tasks can get upper bound of utilization except the last assigned one. Meanwhile, all of high-critical tasks can be schedulable successfully. The cost of migration in semi-partition scheduling is far lower than in global scheduling. Experiment results prove the superiority of semi-partition mixed criticality tasks. Comparing with partitioned scheduling, semi-partition scheduling can increase the percentage of schedulable tasks by nearly 10%.(4) After increasing criticality level, only high-critical tasks are in scheduling and low-critical tasks are discarded in certifiable mixed-criticality real-time systems. For higher resource utilization lower criticality tasks should be treated positively. Dynamic slacks reclaimed from multiprocessors globally can be allocated low-critical task discared before in accordance with temporal characters. The advantage of our positive dealing to low-critical tasks are verified by the simulating test, which get more acceptable tasks and less discarded tasks than TA, CD or CD-A algorithm.(5) An adaptive decreasing criticality level method is presented, whi ch is a kind of feedback mechanism of a closed-loop. Through the actual execution time of high-critical tasks, we can predict the high-critical load variation trend and the proper moment to decreasing criticality level. So low-critical task can be timely re-scheduled and high-critical task can be always scheduled correctly. Experiment results validate the correctness and safety of the adaptive decreasing criticality level algorithm, improving scheduling performance more than Bailout protocol(BP).