Scheduling 1 EE249 What s the problem Have some work to do know subtasks 2 Have limited resources Have some constraints to meet Want to optimize quality EE249 Outline Overview shop scheduling data flow scheduling real time scheduling OS scheduling Real time scheduling RTOS generation scheduling Communication Data flow scheduling pure Petri nets 3 EE249 Shop scheduling Single job one time finite and known amount of work multiple resources of different kind often minimize lateness could add release precedence deadlines SOLUTION compute the schedule APPLICATION manufacturing 4 EE249 Data flow scheduling Single job repeatedly known amount of work simple subtasks multi processor max throughput min latency SOLUTION code generation APPLICATION signal processing 5 EE249 Data flow scheduling variants Work data dependent BDF FCPN Resources many different execution units HLS Goal min code min buffers min resources 6 EE249 Real time scheduling Fixed number of repeating jobs each job has fixed work job is a sub task processor s meet individual deadlines SOLUTION choose policy let RTOS implement it APPLICATION real time control 7 EE249 RT scheduling variants Work sporadic or event driven tasks variable data dependent work coordination between tasks mutual exclusion precedence Goal event loss input or output correlation freshness soft deadlines 8 EE249 OS scheduling Variable number of random tasks know nothing about sub tasks processor other computer resources progress of all tasks average service time SOLUTION OS implements time slicing APPLICATION computer systems 9 EE249 Outline Overview shop scheduling data flow scheduling real time scheduling OS scheduling Real time scheduling RTOS generation Scheduling Communication Data flow scheduling pure Petri nets 10 EE249 RTOS functions Enable communication between software tasks hardware and other system resources Coordinate software tasks keep track which tasks are ready to execute decide which one to execute scheduling 11 EE249 Outline Implementing communication through events Coordination classic scheduling results reactive model of real time systems conservative scheduling analysis priority assignment 12 EE249 The scheduling problem Given estimates on execution times of each task timing constraints Find an execution ordering of tasks that satisfies constraints A schedule needs to be constructed validated 13 EE249 Off line vs on line scheduling Plus side simpler lower overhead highly predictable Minus side bad service to urgent tasks independent of actual requests 14 EE249 Scheduling Algorithms off line pre run time static round robin e g C1 C2 C3 C4 C1 C2 C3 C4 C1 C2 C3 C4 static cyclic e g C1 C2 C3 C2 C4 C1 C2 C3 C2 C4 C1 C2 on line run time dynamic static priority dynamic priority preemptive or not 15 EE249 Static priority scheduling synthesis priority assignment RMS LL73 analysis Audsley 91 16 EE249 Rate Monotonic Scheduling Liu Layland 73 consider systems consisting of tasks enabled periodically with fixed run time that should be executed before enabled again scheduled preemptively with statically assigned priorities 17 EE249 Rate Monotonic Scheduling giving higher priority to tasks with shorter period RMS is optimal if any other static priority assignment can schedule it them RMS can do it too 18 define utilization as sum of Ei Ti any set of n tasks with utilization of less than n 21 n 1 is schedulable for n 2 3 n 21 n 1 0 83 0 78 ln 2 0 69 EE249 Static Priority Schedule Validation Audsley 91 for a task in Liu Layland s model find its worst case execution time k i i n i i i time run time i period i 19 WCET i period i EE249 Audsley s algorithm let Ei s be run times Ti s periods how much can i be delayed by a higher priority task k each execution delays it by Ek while i is executing k will be executed ciel WCETi Tk 20 WCETi Ei SUMk i ciel WCETi Tk Ek EE249 Solving implicit equation iteration WCETi 0 Ei WCETi n 1 Ei SUMk i ciel WCETi n Tk Ek will converge if processor utilization if less than 1 21 EE249 Dynamic priority Earliest deadline first at each moment schedule a task with the least time before next occurrence 22 LL have shown that for their model EDF schedules any feasible set of tasks EE249 What s wrong with LL model Liu Layland model yields strong results but does not model reactivity well Our model models reactivity directly abstracts functionality allows efficient conservative schedule validation 23 EE249 Computation Model 20 10 24 1 2 5 2 3 2 2 1 4 1 System is a network of internal and external tasks External tasks have minimum times between execution Internal tasks have priorities and run times EE249 Computation Model 20 10 25 1 2 5 2 3 2 2 1 4 1 External task execute at random respecting the lower bound between executions Execution of a task enables all its successors Correct if no events are lost EE249 Schedule Validation To check correctness check whether internal events can be lost priority analysis check whether external events can be lost bound WCET 26 EE249 Validation for Internal Events i k Simple if priority of i is less than k then i k cannot be lost i 27 k EE249 More general if fan ins of i form a tree such that leaves have lower priority than non leaves and k then i k cannot be lost Validation for External Events Compute a bound on the period of time a processor executes task of priority i or higher i busy period i i i i i i i i busy period 28 i busy period WCET i EE249 time Bounding i busy Period i busy period is bounded by initial workload at priority level i or higher caused by execution of some task i workload at priority level i or higher caused by execution of external tasks during the i busy period 29 can find by simulation workload at priority level i or higher caused by execution of a single task can bound the number of occurrences of external tasks in a given period need to solve a fix point equation EE249 System Network of CFSMs F B C C F G C G CFSM1 C A F G 1 C CFSM2 C C B A B C B A 0 B CFSM3 30 EE249 Implementations CFSMs can be implemented in hardware HW CFSMs in software SW CFSMs by built in peripherals e g timer MP CFSMs 31 EE249 Events SW to SW for every event RTOS maintains global values local flags x CFSM2 x emit x 3 CFSM1 CFSM3 x 32 detect x 3 EE249 Events atomicity problems TASK 1 detect x TASK 2 TASK 3 emit x if detect x then emit y detect y 33 TASK 1 detects y AND NOT x which is never true to avoid need atomic detects EE249 Events SW to SW for atomicity always read from frozen others always
View Full Document
Unlocking...