PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22A presentation for Brian Evans’ Embedded Software ClassBy Nate FormanLiaison Technology Inc. 3/30/2000For Real-Time Scheduling3/2000 Rate Monotonic Analysis, Nate FormanAgenda• Introduction• Anatomy of a Task• Rate Monotonic Principles and Tests• Extended Rate Monotonic Analysis• Demonstration• Mars Pathfinder Mission3/2000 Rate Monotonic Analysis, Nate FormanIntroduction• Rate Monotonic refers to assigning priorities as a monotonic function of the rate (frequency of occurrence) of those processes.• Rate Monotonic Scheduling (RMS) can be accomplished based upon rate monotonic principles.• Rate Monotonic Analysis (RMA) can be performed statically on any hard real-time system concept to decide if the system is schedulable.3/2000 Rate Monotonic Analysis, Nate FormanAnatomy of a Task123timeTask Execution Time (C) End Of Period (T = Period Length)3/2000 Rate Monotonic Analysis, Nate FormanRate Monotonic Assumptions• All tasks are periodic • Task switching is instantaneous• Tasks account for all processor execution time• Tasks become ready to execute precisely at the beginning of their periods and relinquish the CPU only when execution is complete3/2000 Rate Monotonic Analysis, Nate FormanRate Monotonic Assumptions (2)• Task interactions are not allowed • Task deadlines are always at the end of the period• Tasks with shorter periods are assigned higher priorities; no other criteria are considered for priority assignment• Task execution is always consistent with rate monotonic priority: a lower priority task never executes when a higher priority task is ready3/2000 Rate Monotonic Analysis, Nate FormanUtilization Bound (UB) TestProcessor Utilization for a task, iUi = CiTiUtilization Bound for n tasks U(n) = n(2 - 1)1nResults:• If Ui ≤ U(n) then the set of tasks is schedulable.• If Ui > 1 then the set of tasks is unschedulable.• If U(n) < Ui ≤ 1 then the test is inconclusive.3/2000 Rate Monotonic Analysis, Nate FormanUB Test ExampleTaskExecution Time (C)Period (T)140 100240 1503100 350U(3) = 3(21/3 – 1) = 0.779U1 = 40 / 100 = 0.4U2 = 40 / 150 = 0.267U3 = 100 / 350 = 0.286Utotal = 0.953Result:U1+2 = 0.667, schedulable.However, 0.779 < 0.953 < 1Therefore, inconclusive for 3.3/2000 Rate Monotonic Analysis, Nate FormanResponse Time (RT) TestTheorem: If a task meets its first deadline with worst-case task phasing, that deadline will always be met.For the response time for task i, find the least fixed-point of the following recurrence:a0 = Cjj H + {i}an+1 = Ci + Cjj HanTjwhere H is the set of tasks with higher priority than task i.3/2000 Rate Monotonic Analysis, Nate FormanRT Test ExampleTaskExecution Time (C)Period (T)140 100240 1503100 350a0 = Cj = 40 + 40 + 100 = 180j H + {i}a1 = C3 + Cj = 100 + (2 * 40) + (2 * 40) = 260j H180Tja2 = C3 + Cj = 100 + (3 * 40) + (2 * 40) = 300j H260Tja3 = C3 + Cj = 100 + (3 * 40) + (2 * 40) = 300j H300Tja2 = a3 = 300300 < 3 = 3503 is schedulable.3/2000 Rate Monotonic Analysis, Nate FormanExtensions to RMA• Aperiodic task handling• Preperiod task deadlines (Di = deadline for task i)• Nonzero task switching times (S = task switch time)• Interrupt handling for top-priority tasks• Task blocking and interaction through shared resources (Bi = blocking time for task i)3/2000 Rate Monotonic Analysis, Nate FormanSporadic Servers• A conceptual task that uses its execution budget handling incoming aperiodic tasks • Its execution budget is only replenished after a period where it is completely consumed instead of after every period’s end.• Avoids deferred execution effect and reduces aperiodic tasks to the same model as periodic tasks3/2000 Rate Monotonic Analysis, Nate FormanPriority Inversion• A high priority task is ready to execute, but a lower priority task continues execution because it holds a lock on a shared resource that the high priority task needs. • Unbounded priority inversion occurs when a system allows tasks with lower priority than the blocked task to preempt the blocking task.3/2000 Rate Monotonic Analysis, Nate FormanPriority Inversion (2)• To successfully share resources, a system needs two properties: freedom from mutual deadlock, and bounded priority inversion.• The combination of priority inheritance and the priority ceiling protocol guarantee the above properties.Priority Inheritance: When a task blocks the execution of other, higher priority tasks, it executes at the highest priority of all of the tasks it blocks.3/2000 Rate Monotonic Analysis, Nate FormanPriority Ceiling Protocol• Priority Ceiling: of a binary semaphore is the highest priority of all of the tasks that may lock it. • A task attempting to a execute critical section is blocked unless its priority is higher than the priority ceilings of all of the locked semaphores in the system. • The task holding the lock on the highest priority ceiling semaphore inherits the priorities of tasks blocked in this way.3/2000 Rate Monotonic Analysis, Nate FormanExtended UB Testfor i = Di / Ti, redefine utilization bound:U(n, i) = n ((2i)1/n – 1) + 1 – i,0.5 < i ≤ 1i,i ≤ 0.53/2000 Rate Monotonic Analysis, Nate FormanExtended UB Test (2)+ ++Ci + 2STiTiBifi = j HnCj + 2STj (Ck + 2S)k H1Ti1Updated processor utilization:where Hn is the set of higher priority tasks that can preempt task imore than once (shorter periods) and H1 are higher priority tasks that can preempt task i only once (longer periods)Compare each fi to its utilization bound, U(n, i). The results canbe interpreted as before.3/2000 Rate Monotonic Analysis, Nate FormanExtended RT TestTheorem: If a task meets its first deadline with worst-case task phasing, that deadline will always be met.The above theorem still stands although the deadline is Di instead of Ti. For the response time find the least fixed-point of the recurrence below:a0 = Bi + (Cj + 2S)j H + {i}an+1 = Bi + Ci + 2S + (Cj + 2S)j HanTjwhere H is the set of tasks with higher priority than task i.3/2000 Rate Monotonic Analysis, Nate FormanWhat really happened on Mars?(the first
View Full Document
Unlocking...