FPTS:一种任务间存在共享资源时的抢占阈值调度算法

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

受到广泛关注的抢占阈值调度算法能够有效减少现场切换次数,防止不必要的任务抢占,降低资源额外消耗,提高任务集合的可调度性.目前该调度算法的研究工作大多围绕独立任务集合展开,在实际实时系统中任务经常需要互斥访问共享资源,任务之间由于资源共享而导致的相关性对于任务集合的优先级分配和抢占阈值分配都有很大的影响.SRP协议是在实时系统中得到广泛应用的资源访问控制协议,具有死锁避免、提前阻塞、共享任务栈等一系列优良特性.将SRP和抢占阈值调度算法结合起来,提出FPTS调度模型,给出相应的可调度性判定公式,考虑在任务之间使用SRP协议时求解任务抢占阈值分配,最后给出计算抢占阈值分配的伪多项式时间算法.

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.