Job-Class-Level Fixed Priority Scheduling of Weakly-Hard Real-Time Systems

Many cyber-physical applications including sensing and control operations can tolerate a certain degree of timing violations as long as the number of the violations are predictably bounded. The notion of weakly-hard real-time systems has been studied to capture this effect, but existing work reveals limitations for practical use due the restrictions imposed on timing model and the high complexity of analysis. In this paper, we propose a new job-class-level fixed-priority preemptive scheduler and its schedulability analysis framework for sporadic tasks with weakly-hard real-time constraints. Our proposed scheduler employs the meet-oriented classification of jobs of a task in order to reduce the worst-case temporal interference imposed on other tasks. Under this approach, each job is associated with a "job-class" that is determined by the number of deadlines previously met (with a bounded number of consecutively-missed deadlines). This approach also allows decomposing the complex weakly-hard schedulability problem into two sub-problems that are easier to solve: (1) analyzing the response time of a job with each job-class, which can be done by an extension of the existing task-level analysis, and (2) finding possible job-class patterns, which can be modeled as a simple reachability tree. Experimental results indicate that our scheduler outperforms prior work in terms of task schedulability and analysis time complexity. We have also implemented a prototype of a job-class-level scheduler in the Linux kernel running on Raspberry Pi with acceptably-small runtime overhead.

I. Introduction

The performance and stability of embedded and cyber-physical applications depends not only on the precision of computation but also on the physical instant at which the output is generated [23], [24]. Since Liu and Layland’s seminal work [28], real-time systems with hard deadlines have been extensively studied and have shown their effectiveness in satisfying all deadlines under any circumstance. However, in practical systems, there are many components that are tolerant to some deadline misses without affecting their functional correctness, if the number of misses is predictably controlled and bounded. This observation has motivated the development of weakly-hard real-time systems to improve resource efficiency [5], and this paper focuses on the scheduling problem of tasks with weakly-hard constraints.