FPTS: A Fixed-Priority Preemption Threshold Scheduling Algorithm in the Presence of Resources Sharing

Fixed-priority with preemption threshold (FPPT) is an important form of real-time scheduling algorithm, which fills the gap between fixed-priority preemptive (FPP) and fixed-priority non-preemptive (FPNP). FPPT can prevent tasks from unnecessary task preemption, reduce the additional memory usage, and improve the schedulability of task set. In real-world real-time applications, access to exclusively-shared resources is a very common operation, and therefore shared resources management in FPPT is necessary. The correlations between tasks, resulting from the shared resources, have a great influence on the priority assignment and preemption threshold assignment of task set. However, current research on FPPT real-time scheduling techniques focuses on the time guarantees of independent real-time tasks rather than the complexity coming from exclusively-shared resources. Stack resource protocol (SRP) is well-known resource access and control protocol in real-time systems, and has many nice features such as deadlock avoidance, earlier blocking, shared run-time stack and so on. Proposed in this paper is a new FPTS scheduling paradigm, which integrates FPPT with SRP, including the new critical instant, preemption threshold assignment and appropriate schedulability analysis, based on response time analysis. Furthermore, an algorithm to compute the feasible preemption threshold assignment is presented, and the proofs for the correctness of these algorithms are also presented.