Feasibility Analysis of Non-Preemptive Periodic Systems from Infeasibility Perspective

Abstract

Due to simple implementation, non-preemptive scheduling has the advantage over preemptive counterpart when it comes to deployment of real-time systems. Accordingly, many feasibility techniques have been established to answer schedulability of the task set for non-preemptive case. The time complexity of exact condition for non-preemptive under dynamic priority assignment is of pseud-polynomial nature. Recently, efforts are made to decrease the computation cost of existing exact solutions. However, the time complexity class remains the same. In such systems, feasibility is tested by starting with highest priority task and test continues in that order until the last task is analyzed in the set. Normally, higher priority tasks rarely miss the deadline and hence, when a system is determined infeasible, it is mainly because of the low priority tasks as these tasks are assigned low priorities and can claim CPU time only when there is no pending higher priority task in the queue. In this study, we propose a mechanism that reduces the computation cost of feasibility for non-preemptive earliest deadline first scheduling algorithm by testing the infeasibility of the system in reverse priority order. In worst case, the proposed technique is not inferior for a system with low utilization that scans a task set from feasibility perspectives. On the other hand, our test exhibits better performance when the system infeasibility is tested for the system demanding higher CPU utilization. Our experimental results show that the overall computation cost, especially for the larger task sets with higher CPU demands, is significantly reduced with the proposed solution by evaluating a system from infeasibility perspective.