SchedulingWhat’s the problem?OutlineShop schedulingData-flow schedulingData-flow scheduling variantsReal-time schedulingRT scheduling variantsOS schedulingSlide 10RTOS functionsSlide 12The scheduling problemOff-line vs. on-line schedulingScheduling AlgorithmsStatic priority schedulingRate Monotonic SchedulingSlide 18Static Priority Schedule ValidationAudsley’s algorithmSolving implicit equationDynamic priorityWhat’s wrong with LL model?Computation ModelSlide 25Schedule ValidationValidation for Internal EventsValidation for External EventsBounding i-busy PeriodSystem: Network of CFSMsImplementationsEvents: SW to SWEvents: atomicity problemsSlide 34Events: HW to SWEvents: interruptsEvents: SW to HWEvents: SW to/from MPCoordinationExperimentsOpen ProblemsSlide 42Slide 43Data-flow graphsSchedule implementationSlide 46Slide 47Slide 48Data-flow scheduling goalsThroughput boundScheduling heuristicsInter-iteration constraintsList schedulingSlide 54Slide 55Slide 56Slide 57Slide 58Static data flowLoop schedulingLoop scheduling and code sizeBuffer sizeSlide 63Other scheduling modelsEE2491 SchedulingEE2492 What’s the problem?Have some work to do–know subtasksHave limited resourcesHave some constraints to meetWant to optimize qualityEE2493 OutlineOverview–shop scheduling–data-flow scheduling–real-time scheduling–OS schedulingReal-time schedulingRTOS generation– scheduling–CommunicationData-flow scheduling–pure –Petri netsEE2494 Shop schedulingSingle job, one timefinite and known amount of workmultiple resources of different kindoften minimize lateness–could add release, precedence, deadlines, ...SOLUTION: compute the scheduleAPPLICATION: manufacturingEE2495 Data-flow schedulingSingle-job, repeatedlyknown amount of work–simple subtasksmulti-processormax. throughput, min. latencySOLUTION: code generationAPPLICATION: signal processingEE2496 Data-flow scheduling variantsWork–data dependent (BDF, FCPN)Resources–many different execution units (HLS)Goal–min. code, min. buffers, min. resourcesEE2497 Real-time schedulingFixed number of repeating jobseach job has fixed work–job is a sub-taskprocessor(s)meet individual deadlinesSOLUTION: choose policy, let RTOS implement itAPPLICATION: real-time controlEE2498 RT scheduling variantsWork–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, ...EE2499 OS schedulingVariable number of random tasksknow nothing about sub-tasksprocessor + other computer resourcesprogress of all tasks, average service timeSOLUTION: OS implements time-slicingAPPLICATION: computer systemsEE24910 OutlineOverview–shop scheduling–data-flow scheduling–real-time scheduling–OS schedulingReal-time schedulingRTOS generation–Scheduling–CommunicationData-flow scheduling–pure –Petri netsEE24911 RTOS functionsEnable communication between software tasks, hardware and other system resourcesCoordinate software tasks–keep track which tasks are ready to execute–decide which one to execute: schedulingEE24912 OutlineImplementing communication through eventsCoordination:–classic scheduling results–reactive model of real-time systems–conservative scheduling analysis–priority assignmentEE24913 The scheduling problemGiven:–estimates on execution times of each task–timing constraintsFind:–an execution ordering of tasks that satisfies constraintsA schedule needs to be:–constructed–validatedEE24914 Off-line vs. on-line schedulingPlus side:–simpler–lower overhead–highly predictableMinus side–bad service to urgent tasks–independent of actual requestsEE24915 Scheduling Algorithmsoff-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 notEE24916 Static priority schedulingsynthesis:–priority assignment –RMS [LL73]analysis– Audsley 91EE24917 Rate Monotonic SchedulingLiu -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 prioritiesEE24918 Rate Monotonic Schedulinggiving higher priority to tasks with shorter period (RMS) is optimal–if any other static priority assignment can schedule it, them RMS can do it toodefine utilization as sum of Ei/Ti any set of n tasks with utilization of less than n(21/n-1) is schedulablefor n=2,3,…. n(21/n-1) = 0.83, 0.78, … ln(2)=0.69EE24919 Static Priority Schedule ValidationAudsley [91]:for a task in Liu-Layland’s model find its worst case execution timei i iik nrun time iWCET iperiod i period itimeiEE24920 Audsley’s algorithmlet 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)WCETi = Ei + SUMk>i ciel(WCETi/ Tk)* EkEE24921 Solving implicit equationiteration–WCETi,0 = Ei –WCETi,n+1 = Ei + SUMk>i ciel(WCETi,n/ Tk)* Ekwill converge if processor utilization if less than 1EE24922 Dynamic priorityEarliest deadline first:–at each moment schedule a task with the least time before next occurrenceLL have shown that for their model, EDF schedules any feasible set of tasksEE24923 What’s wrong with LL model?Liu-Layland model yields strong results but does not model reactivity wellOur model:–models reactivity directly–abstracts functionality–allows efficient conservative schedule validationEE24924 Computation ModelSystem is a network of internal and external tasksExternal tasks have minimum times between executionInternal tasks have priorities and run times20101,2 5,2 3,22,1 4,1EE24925 Computation Model20101,2 5,2 3,22,1 4,1External task execute at random, respecting the lower bound between executionsExecution of a task enables all its successorsCorrect if no events are lostEE24926 Schedule ValidationTo check correctness:–check whether internal events can be lost –priority analysis–check whether external events can be lost –bound WCETEE24927 Validation for Internal
View Full Document
Unlocking...