HOME > 상세정보

상세정보

Constraint-based schedulability analysis in real-time systems

Constraint-based schedulability analysis in real-time systems

자료유형
학위논문
개인저자
이혁 李奕
서명 / 저자사항
Constraint-based schedulability analysis in real-time systems / Hyuk Lee
발행사항
Seoul :   Graduate School, Korea Unversity,   2019  
형태사항
vi, 76장 : 도표 ; 26 cm
기타형태 저록
Constraint-based Schedulability Analysis in Real-Time Systems   (DCOLL211009)000000083086  
학위논문주기
학위논문(박사)-- 고려대학교 대학원: 컴퓨터·전파통신공학과, 2019. 2
학과코드
0510   6YD36   354  
일반주기
지도교수: 최진영  
부록: A. Framework for uniprocessor environment(State-based), B. Framework for multiprocessor environment (Execution-based)  
서지주기
참고문헌: 장 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

전자정보

No. 원문명 서비스
1
Constraint-based schedulability analysis in real-time systems (59회 열람)
PDF 초록 목차
No. 소장처 청구기호 등록번호 도서상태 반납예정일 예약 서비스
No. 1 소장처 과학도서관/학위논문서고/ 청구기호 0510 6YD36 354 등록번호 123060839 도서상태 대출가능 반납예정일 예약 서비스 B M
No. 2 소장처 과학도서관/학위논문서고/ 청구기호 0510 6YD36 354 등록번호 123060840 도서상태 대출가능 반납예정일 예약 서비스 B M
No. 3 소장처 세종학술정보원/5층 학위논문실/ 청구기호 0510 6YD36 354 등록번호 153081434 도서상태 대출가능 반납예정일 예약 서비스
No. 소장처 청구기호 등록번호 도서상태 반납예정일 예약 서비스
No. 1 소장처 과학도서관/학위논문서고/ 청구기호 0510 6YD36 354 등록번호 123060839 도서상태 대출가능 반납예정일 예약 서비스 B M
No. 2 소장처 과학도서관/학위논문서고/ 청구기호 0510 6YD36 354 등록번호 123060840 도서상태 대출가능 반납예정일 예약 서비스 B M
No. 소장처 청구기호 등록번호 도서상태 반납예정일 예약 서비스
No. 1 소장처 세종학술정보원/5층 학위논문실/ 청구기호 0510 6YD36 354 등록번호 153081434 도서상태 대출가능 반납예정일 예약 서비스

컨텐츠정보

초록

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