东北大学实时系统.ppt
《东北大学实时系统.ppt》由会员分享,可在线阅读,更多相关《东北大学实时系统.ppt(63页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Real-Time SystemsNan Guan Nan Guan(关楠)(关楠)(关楠)(关楠)Computing EvolutionMainframe computing(60s-70s)Large computers to execute big data processing applicationsDesktop computing&Internet(80s-90s)One computer at every desk to do business/personal activitiesEmbedded Systems(since 00s)Numerous computing de
2、vices in every place/person“Invisible”part of the environmentMillions for desktops vs.billions for embedded processorsEmbedded Systems“Computer systems that are embedded into physical objectes ”98%computers in the world are embedded systemsMarket share3Embedded SystemsReal-Time SystemsReal-Time Syst
3、ems:“The correctness of the computation does not only depend on the logical results,but also the time when the results are produced.”Real-Time Systems are common in Embedded SystemsInteraction between computers and the physical worldReal-Time SystemsReal-Time SystemsReal-Time SystemsReal-Time System
4、sReal-Time SystemsWe need to guarantee that all timing constraints are satisfied under any circumstance,BEFORE run-timeHow to do this?How about using a very fast processor?How about executing it and measuring the time?(Testing)11ThestoryaboutasheepinScotland12ThestoryaboutthePathfinderonMarsWhat do
5、we learn?Testing is inadequate13What do we learn?Testing is inadequate,especially for real-time embedded systemsNeed to simulate the stimulus and feedback from the physical world14EventheNASALabfails,thenhowaboutyourproject?What do we learn?Difficult to fix the error,even if it is exposed in testing
6、Difficult to reproduceDifficult to explain15Timing AnalysisHow to rigorously verify the timing correctness?An extremely difficult problem 16Real-Time Computing TechnologySome leading countries USAGermanySwedenFranceItaly 17Research in Real-Time SystemsConferencesRTSS:IEEE Real-Time Systems Symposium
7、RTAS:IEEE Real-Time and Technology and Applications SymposiumECRTS:Euromicro Conference on Real-time SystemsJournal:Journal of Real-Time Systems18More details about Real-Time Systems in the following19Hard vs Soft Real-Time Systems Definition based on functional criticalityHARD:The failure to meet t
8、he timing constraints has disastrous consequencesBraking system,collision detection,etc.SOFT:A few misses of deadlines do no serious harm,and only the systems overall performance degradesVideo playback,etc.Problem:how serious is serious?-A design propertyHard vs Soft Real-Time Systems Definition bas
9、ed on validationValidation:A demonstration by a provably correct,efficient procedure or by exhaustive simulation and testingHARD:The user require the validation that the system always meets the timing constraintsSOFT:No validation is required,or only a demonstration that the job meet some statistica
10、l constraint sufficesDesirable Properties of RT Systems(1)Predictabilitythe system behavior is known before it is put into operation e.g.Response times,deadlock freedom,etc.Analyzabilityeasy to analyze if the system can meet all the deadlines Cost optimalitye.g.Energy consumption,memory blocks,etc.D
11、esirable Properties of RT Systems(2)Maintainabilitymodular structure to ease system modification Robustnessmust not collapse when subject to peak load,exception,manage all possible scenarios Fault tolerancehardware and software failures should not cause the system to crash Why Achieving Predictabili
12、ty is Hard?Challenges from hardware featuresCache sharing,processor pipelines,multicores,DMA.Interrupt handling may introduce unbounded delays Resource sharing:priority inversionMemory management(static allocation may not be enough,dynamic data structures e.g.Queue),no virtual memory Communication d
13、elays in a distributed environment Why Achieving Predictability is Hard?Challenges from software featuresDifficult to calculate the worst case execution time for tasks(theoretically impossible,halting problem)Bounded loops e.g.For-loops only Complex synchronization patterns between tasks:potential d
14、eadlocks(formal verification)Multi-tasking,tasks that share resources Misconceptions about RT ComputingReal-time computing is fast computingReal-time system research is performance engineeringReal-time is time sharingOverall Structure of a RT SystemHardware(CPU,I/O device etc)a clock!A real time OS(
15、function as standard OS,with predictable behavior and well-defined functionality)A collection of RT tasks/processes(share recourses,communicate/synchronizeA Real-Time Control System2023/2/2628A Real-Time Control SystemSelection of the sampling periodThe digital world is discrete!The responsiveness o
16、f the overall systemThe dynamic behavior of the plant:keep oscillation small and the system under controlFurther:Multirate SystemsThe example of fly-by-wire avionicsTiming constraintsFinishcontrollawcomputationforeachsmallestsamplingperiods!Further:Multirate SystemsFor exampleThe sampling rates of A
17、,B,and C are 180Hz,90Hz,30Hz resp.The sampling periods are“harmonic”Dothefollowingineach1/180secondcycle:DoADoBonceevery2cyclesDoConceevery6cyclesOutputcommandsWaituntilthebeginningofthenextcycleFurthermore:A Car ControllerActivities of a car control system.Let C=worst case execution time T=(samplin
18、g)period D=deadlineControl requirementsConstruct a controller meeting all the deadlines!ObjectsCTDSpeed measurement4205ABS control104040Fuel injection408080Others,e.g.audio,air conditonningSoft deadlinesThe Overall SystemTiming AnalysisSoftware system is complexTiming AnalysisUsually performed botto
19、m-upProgram Level Analysisto bound the worst-case execution time(WCET)of each individual task assuming fully dedicated hardwareSystem Level Analysisthe WCET information of individual tasks is gathered,to investigate the contention of processing capacity among different tasks in a multitasking enviro
20、nmentProgram Level36Execution Time of a ProgramExecution times of programs are intrinsically variable!Void signal_processing()read_signal(&curr_signal);if(curr_signal threshold)signal_transformation();/some+-*/ops.elseerror_handling_routine();/complex error handling operationsThe Distribution of Exe
21、cution TimesDistributionBCETPossible Execution TimeWCETPredicted Upper BoundObservedBCETObserved WCETObserved Execution TimeExecution TimeWorst-Case GuaranteeThe Quality of Static AnalysisSafetyThe estimated upper bound should always enclose the WCETTightness(Precision)The estimated upper bound shou
22、ld be as close as possible to the actual WCETMain objective:to minimize system over-provisioningComplexityThere is always a trade-off between analysis efficiency and precisionSystem Level40Real-Time SchedulingA Simple Task ModelNon periodic/Aperiodic Tasks Appear once only 3 parameters:A:arriving ti
23、me C:computing time(resource requirement)D:deadline(relative deadline)42Constraints on TasksTiming constraints:deadline for each task,Relative to arriving time Absolute deadline Precedence constraints Precedence graphs Input/output relation Resource constraints Mutual exclusion Resource access proto
24、cols 43Scheduling Problems Given a set of tasks(ready queue)Check if all deadlines can be met with a given schedule(schedulability check)Construct a”feasible”schedule to meet all deadlines Construct an optimal schedule e.g.minimizing response times 44Tasks with the Same Arrival Time Assume a list of
25、 tasks(A,C1,D1)(A,C2,D2).(A,Cn,Dn)that arrive at the same time i.e.A How to find a feasible schedule?(there may be many feasible schedules)EDFEDF(Earliest-Deadline-First)order tasks with non-decreasing deadlines.Jackson 1955 Example:(0,1,10)(0,2,3)(0,3,5)Schedule:(0,2,3)(0,3,5)(0,1,10)46EDF:Schedula
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 东北大学 实时 系统
限制150内