Detail View

In real-time systems, it is important that the execution of the function not only produces the correct results but also that the results must be made on time. That is, there are real-time properties that need to be satisfied, and if the execution results of a function with real-time attributes are not produced in a timely manner, they are the same as the wrong results.
Real-time systems, with these properties, also exist in safety-critical domains, and the real-time properties can eventually be linked directly to safety.
In addition, as previously implemented hardware functions are now implemented in software, there are many multiprocessor-applied systems because more functions and capabilities are demanded.
The use of multiprocessors has many advantages, but also increases the complexity of predicting system behavior.
Therefore, it is important to accurately predict the behavior of the system through schedulability analysis and to create a system that satisfies real-time properties.

We propose the schedulability analysis of a real-time system through constraint solving approach, that is, by treating scheduling problem as constraint satisfaction problem.
In order to apply our proposed approach, we define the system model and identify constraints for schedulability analysis in the system model.
Once the system model definition and constraints identification are done, we encode these into the form of simple, clear, and strict logical expressions using first-order logic.
In doing so, we create a set of constraints that let us know whether a given set of tasks can be scheduled.
The set of constraints is then used with a set of tasks as input to the constraint solver to obtain solutions for the set of tasks that satisfies all of the constraints.
The constraint solver returns a model of interpretation if all of the constraints are satisfied, otherwise, it returns Unsatisfiable.

We claim that our proposed approach has contributions on the following aspects.
1) A method for transforming scheduling problems in a real-time system into a set of constraints of simple, clear, and strict logical expressions is proposed,
2) A way to prove that a real-time schedulability can be analyzed by showing satisfiability of such a set of constraints is presented.

Abstract
Contents........................................................................................i
List of Figures.................................................................................iv
List of Tables..................................................................................vi
1 Introduction.................................................................................1
1.1 Real-time System and Schedulability.............................................2
1.2 Constraint Satisfaction Problem....................................................2
1.3 Satisfiability Modulo Theory.........................................................4
1.4 Motivation and Goal...................................................................5
1.5 Contribution of Thesis..................................................................5
1.6 Organization..............................................................................6

2 Previous Researches on Schedulability Analysis...................................7
2.1 Researches for a Uniprocessor System Environment..........................7
2.2 Researches for a Multiprocessor System Environment.......................8

3. Constraint-based Schedulability Analysis of Real-time system.............10
3.1 System Model..........................................................................11
3.2 Encoding Constraints.................................................................18
3.3 Implementation and Experiments................................................25

4 Schedulability analysis with extended task behavior model.................31
4.1 System Model..........................................................................32
4.2 Encoding Constraints.................................................................34
4.3 Implementation and Experiments................................................39

5 Exetension to multiprocessor system environment.............................44
5.1 System Model..........................................................................45
5.2 Encoding Constraints.................................................................48
5.3 Implementation and Experiments................................................53

6 Conclusion............................................................................... ..59

Appendices.................................................................. ................61
A Framework for Uniprocessor environment (State-based)....................62
B Framework for Multiprocessor environment (Execution-based)............67

Bibliography..................................................................................71

국문초록

Acknowledgement