HOME > Detail View

Detail View

Constraint-based schedulability analysis in real-time systems

Constraint-based schedulability analysis in real-time systems

Material type
학위논문
Personal Author
이혁 李奕
Title Statement
Constraint-based schedulability analysis in real-time systems / Hyuk Lee
Publication, Distribution, etc
Seoul :   Graduate School, Korea Unversity,   2019  
Physical Medium
vi, 76장 : 도표 ; 26 cm
기타형태 저록
Constraint-based Schedulability Analysis in Real-Time Systems   (DCOLL211009)000000083086  
학위논문주기
학위논문(박사)-- 고려대학교 대학원: 컴퓨터·전파통신공학과, 2019. 2
학과코드
0510   6YD36   354  
General Note
지도교수: 최진영  
부록: A. Framework for uniprocessor environment(State-based), B. Framework for multiprocessor environment (Execution-based)  
Bibliography, Etc. Note
참고문헌: 장 71-76
이용가능한 다른형태자료
PDF 파일로도 이용가능;   Requires PDF file reader(application/pdf)  
비통제주제어
Constraint satiafaction problem , Satisfiability modulo theories , Real-time schedulability analysis,,
000 00000nam c2200205 c 4500
001 000045978547
005 20190416152426
007 ta
008 181231s2019 ulkd bmAC 000c eng
040 ▼a 211009 ▼c 211009 ▼d 211009
041 0 ▼a eng ▼b kor
085 0 ▼a 0510 ▼2 KDCP
090 ▼a 0510 ▼b 6YD36 ▼c 354
100 1 ▼a 이혁 ▼g 李奕
245 1 0 ▼a Constraint-based schedulability analysis in real-time systems / ▼d Hyuk Lee
260 ▼a Seoul : ▼b Graduate School, Korea Unversity, ▼c 2019
300 ▼a vi, 76장 : ▼b 도표 ; ▼c 26 cm
500 ▼a 지도교수: 최진영
500 ▼a 부록: A. Framework for uniprocessor environment(State-based), B. Framework for multiprocessor environment (Execution-based)
502 1 ▼a 학위논문(박사)-- ▼b 고려대학교 대학원: ▼c 컴퓨터·전파통신공학과, ▼d 2019. 2
504 ▼a 참고문헌: 장 71-76
530 ▼a PDF 파일로도 이용가능; ▼c Requires PDF file reader(application/pdf)
653 ▼a Constraint satiafaction problem ▼a Satisfiability modulo theories ▼a Real-time schedulability analysis
776 0 ▼t Constraint-based Schedulability Analysis in Real-Time Systems ▼w (DCOLL211009)000000083086
900 1 0 ▼a Lee, Hyuk, ▼e
900 1 0 ▼a 최진영 ▼g 崔振榮, ▼e 지도교수
945 ▼a KLPA

Electronic Information

No. Title Service
1
Constraint-based schedulability analysis in real-time systems (59회 열람)
View PDF Abstract Table of Contents
No. Location Call Number Accession No. Availability Due Date Make a Reservation Service
No. 1 Location Science & Engineering Library/Stacks(Thesis)/ Call Number 0510 6YD36 354 Accession No. 123060839 Availability Available Due Date Make a Reservation Service B M
No. 2 Location Science & Engineering Library/Stacks(Thesis)/ Call Number 0510 6YD36 354 Accession No. 123060840 Availability Available Due Date Make a Reservation Service B M
No. 3 Location Sejong Academic Information Center/Thesis(5F)/ Call Number 0510 6YD36 354 Accession No. 153081434 Availability Available Due Date Make a Reservation Service M
No. Location Call Number Accession No. Availability Due Date Make a Reservation Service
No. 1 Location Science & Engineering Library/Stacks(Thesis)/ Call Number 0510 6YD36 354 Accession No. 123060839 Availability Available Due Date Make a Reservation Service B M
No. 2 Location Science & Engineering Library/Stacks(Thesis)/ Call Number 0510 6YD36 354 Accession No. 123060840 Availability Available Due Date Make a Reservation Service B M
No. Location Call Number Accession No. Availability Due Date Make a Reservation Service
No. 1 Location Sejong Academic Information Center/Thesis(5F)/ Call Number 0510 6YD36 354 Accession No. 153081434 Availability Available Due Date Make a Reservation Service M

Contents information

Abstract

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.

Table of Contents

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