AADL : About Scheduling Analysis

AADL : about schedulinganalysisScheduling analysis, what is it ?Embedded real-time critical systems havetemporal constraints to meet (e.g. deadline).Many systems are built with operating systemsproviding multitasking facilities Tasks mayhave deadline.But, tasks make temporal constraintsanalysis difficult to do :We must take the task scheduling intoaccount in order to check task temporalconstraints.Scheduling (or schedulability) analysis.page2

SummaryIssues about real-time scheduling analysis :AADL to the rescueBasics on scheduling analysis : fixed-priorityscheduling for uniprocessor architecturesAADL components/properties to schedulinganalysis1.2.3.page3Real-Time scheduling theory1.2.A set of simplified tasks models (to model functions ofthe system)A set of analytical methods (called feasibility tests)Example:Ri Deadline3.pageRi Ci Ri C jj hp ( i ) Pj A set of scheduling algorithms: build the fullscheduling/GANTT diagram4

Real-Time scheduling theory is hard to applyReal-Time scheduling theoryTheoretical results defined from 1974 to 1994:feasibility tests exist for uniprocessor architecturesNow supported at a decent level by POSIX 1003real-time operating systems, ARINC653, Industry demandingYet, hard to usepage5Real-Time scheduling theory is hard to applyRequires strong theoretical knowledge/skillsNumerous theoretical results: how to choose the right one ?Numerous assumptions for each result.How to abstract/model a system to verify deadlines?How to integrate scheduling analysis in the engineeringprocess ?When to apply it ? What about tools ?It is the role of an ADL to hide those detailspage6

AADL to the rescue ?AADL helps modeling a full system, including hardware,task sets, connections, operating system features, All of these elements are mandatory to apply real-timescheduling theoryExamples: an AADL model can includeTask execution time or task deadline or task release timesScheduling parametersHowever, in many cases, the models stay too complexMultiprocessor architectures, shared buffers or buses, page7Summary1.2.3.Issues about real-time scheduling analysis :AADL to the rescueBasics on scheduling analysis : fixed-priorityscheduling for uniprocessor architecturesAADL components/properties to schedulinganalysispage8

Real-time scheduling theory : models of taskTask simplified model: sequence ofstatements data.pageUsual kind of tasks:Independent tasks or dependent tasks.Periodic and sporadic tasks (criticalfunctions) : have several jobs and releasetimesAperiodic tasks (non critical functions) : onlyone job and one release time9Real-time scheduling theory : models of taskUsual parameters of a periodic task i:Period: Pi (duration between two release times). A task starts a jobfor each release time.Deadline to meet: Di, timing constraint to meet.First task release time (first job): Si.Worst case execution time of each job: Ci (or capacity or WCET).Priority: allows the scheduler to choose the task to runpage10

Real-time scheduling theory : models of taskpage11Uniprocessor fixed priority schedulingFixed priority scheduling :Scheduling based on fixed priority priorities do notchange during execution time.Priorities are assigned at design time (off-line).Efficient and simple feasibility tests.Scheduler easy to implement into real-time operatingsystems.Rate Monotonic priority assignment :Optimal assignment in the case of fixed priorityscheduling and uniprocessor.Periodic tasks only.page12

Uniprocessor fixed priority schedulingTwo steps:1.Rate monotonic priority assignment: thehighest priority tasks have the smallest periods.Priorities are assigned off-line (e.g. at design time,before execution).2.Fixed priority scheduling: at any time, run theready task which has the highest priority level.page13Uniprocessor fixed priority schedulingRate Monotonic assignment and preemptivefixed priority scheduling:Assuming VxWorks priority levels (high 0 ; low 255)T1 : C1 6, P1 10, Prio1 0pageT2 : C2 9, P2 30, Prio2 114

Uniprocessor fixed priority schedulingFeasibility/Schedulability tests to predict ondesign-time if deadline will be met:1.Run simulations on hyperperiod [0,LCM(Pi)]. Sufficientand necessary condition.2.Processor utilization factor test: / . (2 -1) (about 69%)Rate Monotonic assignment and preemptive scheduling.Sufficient but not necessary condition.Task worst case response time, noted Ri : delay betweentask release time and task completion time. Any priorityassignment but preemptive scheduling.3.page15Uniprocessor fixed priority schedulingCompute Ri, task i worst case response time:Task i response time task i capacity delay the task ihas to wait for higher priority task j. Or:Ri Ci waiting time due to jj hp ( i )or Ri Ci Ri Cjj hp ( i ) Pj hp(i) is the set of tasks which have a higher priority thantask i.returns the smallest integer not smaller than x.page16

Uniprocessor fixed priority schedulingpage17Uniprocessor fixed priority schedulingExample: T1(P1 7, C1 3), T2 (P2 12, C2 2), T3 (P3 20, C3 5)1 1 3 "1 32 2 222 C2 . 1 2 122 C2 . 1 2 13 3 5333 C3 . 1 12333 C3 . 1 12333 C3 . 1 12333 C3 . 1 12333 C3 . 1 12page182.3 575. 3 5 "2 57. 2 10. 2 13. 2 15. 2 18. 2 18 "3 18

Uniprocessor fixed priority schedulingExample with the AADL case study:“display panel” thread which displays data. P 100, C 20.“receiver” thread which sends data. P 250, C 50.“analyser” thread which analyzes data. P 500, C 150.Processor utilization factor test:U 20/100 150/500 50/250 0.7Bound 3.(2 1) 0.779U Bound deadlines will be met.Task response time: &'(')* ,- 330, &./ 0)'* 0'(,) 20,&-,2,/3,- 70.Run simulations on hyperperiod: [0,LCM(Pi)] [0,500].page19Uniprocessor fixed priority schedulingpage20

Fixed priority and shared resourcesPrevious tasks were independent does notreally exist in true life.Task dependencies :Shared resources.E.g. with AADL: threads may wait for AADL protected datacomponent access.Precedencies between tasks.E.g with AADL: threads exchange data by data portconnections.page21Fixed priority and shared resourcesShared resources are modeled by semaphores for scheduling analysis.We use specific semaphores implementing inheritance protocols:To take care of priority inversion.To compute worst case task waiting time for the access to a sharedresource. Blocking time Bi.Inheritance protocols:PIP (Priority inheritance protocol), can not be used with more thanone shared resource due to deadlock.PCP (Priority Ceiling Protocol) , implemented in most of real-timeoperating systems (e.g. VxWorks).Several implementations of PCP exists: OPCP, ICPP, page22

Fixed priority and shared resourcesWhat is Priority inversion: a low priority task blocks ahigh priority task5 worst case on the shared resource waiting time.page23Fixed priority and shared resourcesICPP (Immediate Ceiling Priority Protocol):Ceiling priority of a resource maximum fixed priority of the taskswhich use it.Dynamic task priority maximum of its own fixed priority and theceiling priorities of any resources it has locked.5 longest critical section ; prevent deadlockspage24

Fixed priority and shared resourcesHow to take into account the waiting time Bi:Processor utilization factor test : ,1 : 9:;: 9 ; . (2 ? 1)Worst case response time :Ri Bi Ci page Ri C jj hp ( i ) Pj 25To conclude on scheduling analysisMany feasibility tests: depending on task, processor, scheduler,shared resource, dependencies, multiprocessor, hierarchical,distributed, R w Ji R Ri Bi Ci i C jj hp ( i ) Pj Ri Ci j hp ( i ) Ri C j max(Ck k hp(i )) Pj Ri Ci Ri C j j hp ( i ) Pj iwi Ci i j hp ( i ) Ri J j C j Pj Many assumptions : require preemptive, fixed priority scheduling,synchronous periodic, independent tasks, deadlines on requests Many feasibility tests . Many assumptions How to choose them?page26

SummaryIssues about real-time scheduling analysis :AADL to the rescueBasics on scheduling analysis : fixed-priorityscheduling for uniprocessor architecturesAADL components/properties to schedulinganalysis1.2.3.page27AADL to the rescue ?Issues:Ensure all required model elements are given for the analysisEnsure model elements are compliant with analysisrequirements/assumptionsAADL helps for the first issue:AADL as a pivot language between tools. Internationalstandard.Close to the real-time scheduling theory: real-time schedulinganalysis concepts can be found. Ex:Component categories: thread, data, processorProperty: Deadline, Fixed Priority, ICPP,Ceiling Priority, page28

Property sets for scheduling analysisProperties related to processor component:Preemptive Scheduler : aadlboolean applies to (processor);Scheduling Protocol:inherit list of Supported Scheduling Protocolsapplies to (virtual processor, processor);-- RATE MONOTONIC PROTOCOL,-- POSIX 1003 HIGHEST PRIORITY FIRST PROTOCOL, .page29Property sets for scheduling analysisProperties related to the threads/datacomponents:Compute Execution Time: Time Rangeapplies to (thread, subprogram, );Deadline: inherit Time Period applies to (thread, );Period: inherit Time applies to (thread, );Dispatch Protocol: Supported Dispatch Protocolsapplies to (thread);-- Periodic, Sporadic, Timed, Hybrid, Aperiodic, Background,.Priority: inherit aadlinteger applies to (thread, , datapage30Concurrency Control Protocol:Supported Concurrency Control Protocols applies to (data);-- None, PCP, ICPP,

Property sets for scheduling analysisExample:Compute Execution Time 31 ms . 50 ms;Deadline 250 ms;process implementation processing.otherssubcomponentsreceiver : thread receiver.impl;analyzer : thread analyzer.impl;target : data target position.impl;.Period 250 ms;processor implementation leon2thread implementation receiver.implpropertiesDispatch Protocol Periodic;end receiver.impl;data implementation target position.implpropertiesConcurrency Control Protocol PRIORITY CEILING PROTOCOL;end target position.impl;page 31propertiesScheduling Protocol RATE MONOTONIC PROTOCOL;Preemptive Scheduler true;end leon2;system implementation radar.simplesubcomponentsmain : process processing.others;cpu : processor leon2;.Cheddar : a framework to accessschedulability of AADL modelsCheddar tool analysis framework (queueing system theory &real-time scheduling theory) internal ADL (architecture description language) various standard ADL parsers (AADL, MARTE UML) simple model editor Two versions :Open source (Cheddar) : educational and research.Commercial product (AADLInspector) : Ellidiss Tech product.Supports : Ellidiss Tech., Conseil régional de Bretagne, BMO,EGIDE/Campus France, Thales Communication, BPI Francepage32

Cheddar : a framework to accessschedulability of AADL modelsDemos:Scheduling analysis of the radar example with Cheddar. And with AADLInspector alsopage33

Issues about real-time scheduling analysis : AADL to the rescue 2. Basics on scheduling analysis : fixed-priority scheduling for uniprocessor architectures 3. AADL components/properties to scheduling analysis page 3 1. A set of simplified tasks models (to model functions of the system) 2. A set of analytical methods (called feasibility tests .