Designing Real-time Scheduling Algorithm For Mixed-Criticality Sporadic Task Systems

With the rapid development of information technology industry in recently years, the functions of embedded system are increasingly complex, but having various constraints on system size, cost and power. To overcome these problems modern embedded systems usually integrate multiple functions on a shared platform. Mixed-criticality for modem embedded real-time systems designing provides an effective solution. But the designing of real-time scheduling algorithm and the verifying correctness of the system are challenging, gradually becoming academic and industrial research hotspot and difficult.For a limited job system OCBP algorithm has many excellent properties in existing mixed-criticality scheduling policy. LB algorithm extends OCBP to sporadic task model, but pseudo-polynomial time complexity is difficult to accept for embedded systems. Later PLRS reduces the time complexity to the square level through using offline priority plan table and run-time abstract data structures, but it is still high to embedded systems.In response to these deficiencies, this paper proposes a new scheduling algorithm LPA. The main idea is that LPA does not immediately perform the heavy priority adjustment for all tasks when preemption occurs, instead it only lets each task to record this event. Based on the record, LPA performs a lightweight priority adjustment for the jobs of task when a new job is released. This will focus on the priority adjustment and heavy work distributed to each release time for the job, not only reduces the single priority adjustment complexity, but also avoid a lot of redundant computation and improve the run-time scheduling performance.In addition, LB, PLRS algorithm use an upper bound of the maximal busy period to transform unlimited number of jobs into limited number of jobs. Their bound is safe but grossly over-criticality systems. In this paper, we propose an efficient algorithm to compute a tighter upper bound of the maximum busy period size, which reduces the system effectively space complexity, and finally through the experiment also found that by improving the upper bound of a busy period can improve acceptance ratio.