Constraint-Based Schedulability Analysis in Multiprocessor Real-Time Systems

Abstract

As the demand for more functions and capabilities in the system increases, the application of multiprocessors has brought advantages in many ways. Many systems now have multiprocessors, and safety-critical systems with real-time properties are no exception. In these systems where the satisfaction of real-time properties is directly linked to the safety of life, the predictability of the behavior is very important, and the behavior of the system can be predicted using the schedulability analysis. In this paper, we propose the schedulability analysis of a real-time system in a homogeneous multiprocessor environment through constraint solving approach. First, the constraints that must be satisfied in order for the system to function properly were derived. These include the constraints of the task behavior, the scheduling behavior, and the operating conditions of a homogeneous multiprocessor environment. Once all the constraints were identified, they were encoded in the form of first-order logic expressions. The encoded constraints are then entered into a constraint solver along with a set of tasks. Finally, the solver provides a schedulable answer if the set of tasks satisfies all the constraints.

Keywords

• Constraint satisfaction problem
• satisfiability modulo theories
• real-time schedulability analysis
• multiprocessor schedulability analysis