Research Of Real-time Scheduling Algorithm For Non-monitoring Mixed-Criticality Systems

With the rapid development of information technology industry, the application of real-time embedded systems is becoming more and more widely. Due to the multiple restrictions of cost, size, power consumption, utilization and other factors of the equipment, integration of multiple functions on a hardware platform has become the current trends of modern embedded systems. The verification method and reliability level are different for different criticality level function application. So the mixed-criticality system which gives different function different critical provides an effective solution for the design of modern real-time system. With the proposed of mixed-criticality system model, the design of real-time scheduling algorithm of mixed-criticality system has become a hot issue in the field of real-time embedded systems.In all of the scheduling algorithms which have been proposed for mixed-criticality systems, OCBP algorithm has many excellent properties and attracts wide attention of scholars in mixed-criticality areas. However, OCBP is only suitable for the system which has limited jobs. To solve this problem, some scholars have proposed LB algorithm. LB algorithm extents OCBP to sporadic task model which is more general in mixed-criticality system using the technology of busy period. However, its time complexity is pseudo-polynomial level which is difficult to accept in terms of embedded system. The later PLRS algorithm uses the priority plan and run-time abstract data structure to reduce the time complexity to square level. But, it is still too high. The LPA algorithm which is proposed recently adjusts priority as late as possible when a job is preempted, thus reducing the time complexity of the algorithm greatly.The offline priority assignment of the LPA algorithm is based on the OCBP algorithm. It is used in self-monitoring system. Self-monitoring system monitors the execution time of the job in the system all the time, which brings serious runtime load, so this paper proposed a mixed-criticality scheduling algorithm LPA* for non-monitoring system. Non-monitoring system needn’t monitor the execution time of the job, which may lead to some job execution overload. However, the low run-time overload makes it easy to apply to the actual system. We propose a precise offline job fixed priority assignment algorithm which improves the resource utilization. And propose mixed-criticality scheduling algorithm LPA* which performs well for non-monitoring system. Experimental results show that LPA* algorithm has significantly resource utilization enhance compared with LPA using the offline priority assignment algorithm proposed in this paper. In particular, LPA* algorithm performance reduction is not obvious for non-monitoring system tasks acceptance ratio, even better than LPA, Vestal algorithm for self-monitoring system tasks. High resource utilization and low scheduling expenses of non-monitoring systems make LPA* algorithm easy to apply to actual embedded system.