SWE30001 - Deterministic Scheduling.pdf

Deterministic Scheduling Overview Timing behavior of software Priority-based scheduling Earliest Deadline First Assignment (EDF) Rate-Monotonic Priority Assignment (RMA) References Alan C. Shaw, “Real-Time Systems and Software”, John Wiley & Sons, Inc., 2001...

Deterministic Scheduling Overview Timing behavior of software Priority-based scheduling Earliest Deadline First Assignment (EDF) Rate-Monotonic Priority Assignment (RMA) References Alan C. Shaw, “Real-Time Systems and Software”, John Wiley & Sons, Inc., 2001 C. L. Liu and James W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, Journal of the ACM, Vol. 20, No. 1, January 1973, pp. 46-61. John L. Lehoczky and Liu Sha, “The Rate-Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior”, Proceedings of Real-Time Systems Symposium, December 1989, pp. 166-171. © 207 Limitations of Cyclic Schedulers Cyclic schedulers are very ef cient, however, a prominent shortcoming of cyclic schedulers is that nding a suitable frame size as well as a feasible schedule can be very complex when the number of processes is large. In addition, in almost every frame some processing time is wasted (the frame size is larger than all process execution times) resulting is sub-optimal schedules. 4 5 4 5 4 5 4 4,5,20 T1 T2 T1 T2 T4 T1 T3 T2 T1 T2 T1 0 2 4 6 8 10 12 14 16 18 20 © 208 fi fi Event-Driven Schedulers Event-driven schedulers overcome the shortcomings of cyclic schedulers. In addition, event-driven schedulers can handle aperiodic and sporadic processes more pro ciently. However, event-driven schedulers are less ef cient as they deploy more complex scheduling algorithms. As a result, event-driven schedulers are less suitable for embedded systems and are invariably being used predominantly in moderate and large-sized applications having many processes. In event-driven scheduling, the scheduling points are de ned by process completion and process arrival events. This class of schedulers is normally preemptive, higher priority processes when becoming ready, preempt any lower priority process that may be running. © 209 fi fi fi Time as a Resource When designing a real-time system, at system level, time is explicitly treated as a resource in form of hardware processors that must be allocated to real-time computations. A set of computations is said to be schedulable on one or more processors if there exist enough processor cycles, that is, enough time, to execute all the computations. An approach to analyze and decide whether or not a given task set is schedulable is deterministic scheduling - deterministic because input data and results are not statistical. © 210 Assumption and Candidate Algorithms We are given one or more processors and a set of processes with information and constraints about their behavior and requirements. The information usually includes process activation time, deadlines, and execution times. The problem is then to devise a policy for allocating the processes to the processors. Such a policy or its implementation is called a scheduler or scheduling algorithm, and the detailed assignment of processes to processors is a schedule. If an algorithm is able to allocate the processes so that all constraints are met, then the resulting schedule is said to be feasible. An optimal algorithm is one that will produce a feasible schedule if it exists. © 211 Foreground-Background Scheduler A foreground-background scheduler is a simple priority-driven preemptive scheduler in which period processes run in the foreground and sporadic, aperiodic, and non-critical processes run in the background. A background process can run when none of the foreground processes is ready. In other words, background processes run at the lowest priority. Consider a set of periodic processes SP = { Pi = (ci,τi,di) | 1 ≤ i ≤ n } and background process PB with a computation time cB. A feasible deadline dB for PB (or its completion time) is given by ⌧B dB = P n ci 1 ⌧i AAACKnicdVDLSgMxFM34tr6qLt0ERXBjmZlaHwuhVgRxpWBV6NQhk2Y0mGSG5I5QhvkMv8GNv+LGhSJu/QK/wNQqqOiBwOGcc7m5J0oFN+C6z87A4NDwyOjYeGlicmp6pjw7d2KSTFPWpIlI9FlEDBNcsSZwEOws1YzISLDT6Gq3559eM214oo6hm7K2JBeKx5wSsFJY3umEDbyNg1gTmgdAsrBR5B5exYHJZCC45GDCnG97xXmuis8cDXnRD/OiCMtLbsV1a9X1GnYrnu/V1jYtWXOrW76PPWv1sFQ/Hj+o37ztHYblh6CT0EwyBVQQY1qem0I7Jxo4FawoBZlhKaFX5IK1LFVEMtPOP04t8LJVOjhOtH0K8If6fSIn0piujGxSErg0v72e+JfXyiDebOdcpRkwRfuL4kxgSHCvN9zhmlEQXUsI1dz+FdNLYtsA227JlvB1Kf6fnPgVr1rxj2wbDdTHGFpAi2gFeWgD1dE+OkRNRNEtukeP6Mm5cx6cZ+elHx1wPmfm0Q84r+9QS6rl i=1 When any foreground process is executing, the background process waits. The background process can only be executed outside the average processor utilization of the foreground periodic processes. © 212  Priority-Based Scheduling P2 P2 P1 P1 P1 P1 P1 0 2 4 6 8 10 Consider two periodic processes P1 = (1,2,2) and P2 = (2,5,5) that share a single processor. Suppose that the processes have xed scheduling priorities, π1 and π2, respectively, with π1 > π2. These processes are scheduled when ready according to priority, highest priority rst and processes are not preempted during execution. A feasible schedule is shown above. © 213 fi fi Missed Deadline deadline missed P2 P1 0 2 4 6 8 10 If the priorities are reversed (π1 < π2), a feasible schedule is no longer possible. Process P1 misses its deadline as P2 at time 0 consumes two units of time. © 214 How should we assign priorities? © 215 Earliest Deadline First Assignment In Earliest Deadline First (EDF) scheduling, at every scheduling point the process having the shortest deadline is taken up for scheduling. Necessary and suf cient condition: A set of periodic processes is EDF schedulable if it satis es n X ck U= 1 tk AAACGHicdVDBSisxFM2o71mrPqsu3QRFcNU3qaB1IRRd6FLBqtCpQybNaGiSGZI7QhnmB9y5cOOvuHGhiEvd+TNixvrgKXrgXg7n3EtyT5RKYcH3X7yR0bFfv8crE9XJqek/M7XZuUObZIbxNktkYo4jarkUmrdBgOTHqeFURZIfRf3t0j8658aKRB/AIOVdRU+1iAWj4KSw9reNN3FgMxVIoQTYMO9vkuIk1wUOYkNZzsJ+kYNrOJAck7C25Nd93yeE4JKQ9TXfkY2NZoM0MSkth6XWzsX2a3D5tBfWnoNewjLFNTBJre0QP4VuTg0IJnlRDTLLU8r69JR3HNVUcdvN3w8r8LJTejhOjCsN+F39fyOnytqBitykonBmv3ql+J3XySBudnOh0wy4ZsOH4kxiSHCZEu4JwxnIgSOUGeH+itkZdXmAy7LqQvh3Kf6ZHDbqZLXe2HdpbKEhKmgBLaIVRNA6aqFdtIfaiKErdIPu0L137d16D97jcHTE+9iZR5/gPb8BHw+kPQ== k=1 Whenever a new process arrives, sort the ready queue, which may be O(n2), so that the process closest to the end of its period is assigned the highest priority. Preempt the running process if it is not placed in the rst position of the queue. © 216 fi fi fi τi ≠ di EDF is an optimal scheduling algorithm. EDF can schedule a process set if any scheduling algorithm can. We generally assume that the period and the deadline of a process coincide. In many practical situations, however, τi ≠ di. If di < τi, U ≤ 1 is no longer a suf cient condition. For these kinds of systems, we work with densities rather than utilization. The density of a process is de ned to be δi = ci/min(τi, di). The density of a system is n X AAACMnicdVBNaxRBEO2JX8nGj40ec2lcAhFkmQ6abA6BEHPQWwQ3CWyvQ09vTdJMd8/QXRNYmvlNXvwlAQ96MIhXf4Q9yQoq+qDg8V4VVfXyWiuPafo5Wbp1+87de8srvdX7Dx4+6q89PvZV4ySMZaUrd5oLD1pZGKNCDae1A2FyDSd5+arzTy7AeVXZdzivYWrEmVWFkgKjlPXf8EPQKOge5b4xXCuj0Geh3GPt+2BbXjghg8zKNnAj8NyZYJRtNzmKJiuf01lWPmsp10BZ1h+kwzRNGWO0I2xnO41kd3e0xUaUdVbEgCxwlPUv+aySjQGLUgvvJyytcRqEQyU1tD3eeKiFLMUZTCK1woCfhuuXW7oRlRktKhfLIr1Wf58Iwng/N3ns7O72f3ud+C9v0mAxmgZl6wbByptFRaMpVrTLj86UA4l6HomQTsVbqTwXMSWMKfdiCL8+pf8nx1tDtj18+fbFYP9gEccyWSdPySZhZIfsk9fkiIyJJB/IJ/KVXCUfky/Jt+T7TetSsph5Qv5A8uMn6b6rKg== ck = 1 min(⌧k , dk ) k=1 Δ is the schedulable condition for EDF. © 217 fi fi Example Consider a set of processes: P1 = (25,150,100), P2 = (10,50,30), and P3 = (50,200,150): 3 AAACn3icdVHdahQxGM2Mf3X9W/VSL6KLUKksydTpbi8KpQoKiqzgtpWd7ZDJZtowSWZIMsIS8lo+iHe+jZntKmvRD75wcs53SHJSNIIbi9DPKL52/cbNW1u3e3fu3rv/oP/w0bGpW03ZlNai1qcFMUxwxaaWW8FOG82ILAQ7Kao3nX7yjWnDa/XFLhs2l+Rc8ZJTYgOV979nb5mwBB7AzLQyE1xya3JXHWB/5nZ9VmpCHc0r7zJJ7IWWTnLltzNL2rx6BRd59dJ35tVcknqHEfJwZ01g5N3uxj4NexyWP45RuhMMXXeDG0IySq8wGAdv4mEmGMR5f4CGCCGMMewAHu2hAPb3xwkeQ9xJoQZgXZO8/yNb1LSVTFkqiDEzjBo7d0RbTgXzvaw1rCG0IudsFqAikpm5W+Xr4YvALGBZ69DKwhW76XBEGrOURZjsQjJXtY78lzZrbTmeO66a1jJFLw8qWwFtDbvPgguuGbViGQChmoe7QnpBQho2fGkvhPD7pfD/4DgZ4r1h+vn14PBoHccWeAKeg22AwQgcgvdgAqaARk+jo+hD9DF+Fr+LP8WTy9E4Wnseg78q/voLtxHHmA== X ck 25 10 50 75 + 100 + 100 275 11 = = + + = = = 1 min(⌧k , dk ) 100 30 150 300 300 12 k=1 Hence, this process set is EDF schedulable. Note, LCM(100, 30, 150) = 300. That is, the scheduling pattern repeats every 300 time units. © 218  Advantages and Disadvantages of EDF EDF works for all types of processes: periodic and non- periodic. It is simple and works nicely in theory Simple scheduling test: Δ ≤ 1. It is optimal. Best CPU utilization. Dif cult to implement in practice due to dynamic priority assignment (requires on-line sorting of ready queue). Non-stable: If any process fails to meet its deadline, the system is not predictable, any instance of any process may fail. © 219 fi Critical Instant t1 t1+Tm … t2 t2+Ti t2+2Ti t2+kTi t2+(k+1)Ti Pi Pi Pi Pi t2+Ci t2+Ti+Ci t2+2(Ti+Ci) t2+k(Ti+Ci) A critical instant for a process is de ned to be an instant at which a request for that process will have the largest response time. A critical instant for any process occurs whenever the process is requested simultaneously with requests for all higher priority processes [Liu&Layland]. Let P1, P2, …, Pm denote a set of priority-ordered processes with Pm being the process with the lowest priority. Consider a particular request for Pm that occurs at t1. Suppose that between t1 and t1+Tm, the time at which a subsequent request for Pm occurs, requests for Pi, i < m, occur at t2, t2+Ti, …, t2+kTi. Clearly, the preemption of Pm by Pi will cause a certain delay in the completion of the request Pm that occurred at t1, unless the request for Pm is completed before t2. Moving t2 will not speed up Pm. Moreover, the delay is at maximum when t1 =©t2. 220 fi Simple Test for Priority Assignment P1 P1 P1 P1 P1 P1 P2 P2(1) P2(2) 0 1 2 3 4 5 0 1 2 3 4 5 Consider two periodic processes P1 = (1,2,2) and P2 = (1,5,5). If π1 > π2, then a scheduling algorithm is feasible and c2 can even be increased to 2. If π1 < π2, then a scheduling algorithm is also feasible, but c1 and c2 cannot be increased beyond 1. P2 P1 0 1 2 3 4 5 © 221 Scheduling of Two Processes Let P1 and P2 two periodic processes and τ1 and τ2 their respective request periods, with τ1 < τ2. If we let P1 be the higher priority process, then the following inequality must be satis ed (critical instant): b⌧2 /⌧1 cc1 + c2  ⌧2 AAACG3icdVDLSgMxFM3UV62vUZduQosgFOpkBNvuim5cVrAP6JSSSTNtaGYyJBmhlP6FCzf+ihsXirgSXPRvzLQVVPQuksM553LvPX7MmdKOM7MyK6tr6xvZzdzW9s7unr1/0FQikYQ2iOBCtn2sKGcRbWimOW3HkuLQ57Tljy5TvXVLpWIiutHjmHZDPIhYwAjWhurZrscDLoSEnsZJzz2dfwh6csESg4vmdaHH6dLTswtOyXEchBBMASqfOwZUqxUXVSBKJVOFWt4r3s1q43rPfvf6giQhjTThWKkOcmLdnWCpGeF0mvMSRWNMRnhAOwZGOKSqO5nfNoXHhunDwOwSiEjDOfu9Y4JDpcahb5wh1kP1W0vJv7ROooNKd8KiONE0IotBQcKhFjANCvaZpETzsQGYSGZ2hWSIJSbaxJkzIXxdCv8HTbeEzkrutUnjAiwqC45AHpwABMqgBq5AHTQAAffgETyDF+vBerJerbeFNWMtew7Bj7I+PgFTa6Kw (1) If we let P2 be the higher priority process, then the following inequality must be satis ed: c 1 + c 2  ⌧1 AAAB/XicdVDLSgMxFM34rPU1PnDjJlgEQSiTEWy7K3XjsgX7gM4wZNK0Dc08SDJCHYq/4saFom79Ab/AnRu/xUyroKIHLhzOuZd77/FjzqSyrDdjbn5hcWk5t5JfXVvf2DS3tlsySgShTRLxSHR8LClnIW0qpjjtxILiwOe07Y/OMr99SYVkUXihxjF1AzwIWZ8RrLTkmbvEQ/AYEs+GDqfQUTjxkGcWrKJlWQghmBFUOrU0qVTKNipDlFkahepe45091l7qnvnq9CKSBDRUhGMpu8iKlZtioRjhdJJ3EkljTEZ4QLuahjig0k2n10/goVZ6sB8JXaGCU/X7RIoDKceBrzsDrIbyt5eJf3ndRPXLbsrCOFE0JLNF/YRDFcEsCthjghLFx5pgIpi+FZIhFpgoHVheh/D1KfyftOwiOinaDZ1GDcyQA/vgABwBBEqgCs5BHTQBAVfgBtyBe+PauDUejKdZ65zxObMDfsB4/gDQdJc/ (2) Since b⌧2 /⌧1 cc1 + b⌧2 /⌧1 cc2  b⌧2 /⌧1 c⌧1  ⌧2 AAACYnichVHLSgMxFM2M1kd9tNWlLkKLIBTqZATb7opuXCrYB3RKyaSZNpiZDElGGEr/wi9z58qNH2JmxoKI0rvJueecS25O/JgzpR3n3bK3tks7u3v75YPDo+NKtXYyUCKRhPaJ4EKOfKwoZxHta6Y5HcWS4tDndOg/32X68IVKxUT0pNOYTkI8j1jACNaGmlZTjwdcCAk9jZOpe5UfCHqyYInBTbjJ4xoH3eBat5kxN0yrDaflOA5CCGYAtW8cA7rdjos6EGWSqUav7jVf33vpw7T65s0ESUIaacKxUmPkxHqyxFIzwumq7CWKxpg84zkdGxjhkKrJMo9oBS8MM4OBWSQQkYY5+3NiiUOl0tA3zhDrhfqtZeRf2jjRQWeyZFGcaBqR4qIg4VALmOUNZ0xSonlqACaSmV0hWWCJiTa/UjYhrF8K/wcDt4WuW+6jSeMWFLUHzkAdXAIE2qAH7sED6AMCPqySdWxVrE+7bNfs08JqW98z3/267PMvdla3zA== (2) implies (1). In other words, whenever τ1 < τ2 and c1 and c2 are such that the process schedule is feasible with P2 at higher priority than P1, it is also feasible with P1 at higher priority than P2, but the opposite is not true. © 222 fi fi Rate-Monotonic Priority Assignment A “reasonable” rule of priority assignment is to assign priorities to processes according to their request rates, independent of their running times. Speci cally, processes with higher request rates will have higher priorities. This is rate-monotonic priority assignment. Such a priority assignment is optimum in the sense that no other xed priority assignment rule can schedule a process set which cannot be scheduled by the rate-monotonic priority assignment. © 223 fi fi  Utilization-Based Analysis of RMA Necessary condition: A set of periodic processes is RMA schedulable if it satis es n X ck U= 1 tk AAACGHicdVDBSisxFM2o71mrPqsu3QRFcNU3qaB1IRRd6FLBqtCpQybNaGiSGZI7QhnmB9y5cOOvuHGhiEvd+TNixvrgKXrgXg7n3EtyT5RKYcH3X7yR0bFfv8crE9XJqek/M7XZuUObZIbxNktkYo4jarkUmrdBgOTHqeFURZIfRf3t0j8658aKRB/AIOVdRU+1iAWj4KSw9reNN3FgMxVIoQTYMO9vkuIk1wUOYkNZzsJ+kYNrOJAck7C25Nd93yeE4JKQ9TXfkY2NZoM0MSkth6XWzsX2a3D5tBfWnoNewjLFNTBJre0QP4VuTg0IJnlRDTLLU8r69JR3HNVUcdvN3w8r8LJTejhOjCsN+F39fyOnytqBitykonBmv3ql+J3XySBudnOh0wy4ZsOH4kxiSHCZEu4JwxnIgSOUGeH+itkZdXmAy7LqQvh3Kf6ZHDbqZLXe2HdpbKEhKmgBLaIVRNA6aqFdtIfaiKErdIPu0L137d16D97jcHTE+9iZR5/gPb8BHw+kPQ== k=1 Suf cient condition: A set of periodic processes is RMA schedulable (Liu&Layland criterion) if n X ck U=  n(21/n 1) tk AAACJXicdVBNaxsxENW6zUfdNHHaYy6ioeAe4q42EDvQQKgP6TGFOgl4nUUra2NhSbtIswEj9g/0lr+QS/9KLzk4lEBP/Sel2riFprQPZni8N4M0Ly2ksBCG34LGo8dLyyurT5pP156tb7Q2n5/YvDSMD1guc3OWUsul0HwAAiQ/KwynKpX8NJ32a//0khsrcv0RZgUfKXqhRSYYBS8lrbcDfIBjW6pYCiXAJm56QKpzpyscZ4Yyx5Jp5cA3HEuOdTs6d+SNd3cweZ20tsNOGIaEEFwT0t0LPdnf70Wkh0lteWwfHn3q/4iv5sdJ6zYe56xUXAOT1NohCQsYOWpAMMmrZlxaXlA2pRd86KmmituRu7+ywq+8MsZZbnxpwPfqnxuOKmtnKvWTisLE/u3V4r+8YQlZb+SELkrgmi0eykqJIcd1ZHgsDGcgZ55QZoT/K2YT6sMBH2zTh/D7Uvx/chJ1yG4n+uDTeIcWWEVb6CVqI4K66BC9R8dogBi6Rl/QHN0Gn4Ob4GtwtxhtBL92XqAHCL7/BFJoqEE= k=1 U ≤ 0.692 as n → ∞. © 224 fi fi Liu&Layland Condition Achievable Utilization under RMA 1.0 0.9 Utilization U ≤ 0.692 as n → ∞ 0.8 0.7 0 25 50 75 100 Processes © 225 Examples Consider a set of processes: P1 = (20,100,100), P2 = (30,150,150), and P3 = (60,200,200): 3 X ck 20 30 60 2 2 3 7 U= = + + = + + = 1 tk 100 150 200 10 10 10 10 AAACh3icdZHfTtswFMadwAZ0fyhwuRtraNI0pM5OoC0XSAwutksmrYDUdJHjOmDVTiLbQaqsvAB3e4G903a3l5mwG9gAbUdK9J3f9x05Oc4qwbVB6FcQLi0/ebqyutZ59vzFy/XuxuapLmtF2YiWolTnGdFM8IKNDDeCnVeKEZkJdpbNjr1/dsWU5mXxxcwrNpHkouA5p8Q4lHa/j+ABTHQtE8ElNzq1swPcfLVxA5NcEWppOmuscS+fW5AINRYj1MCdWxB7sHcP9B2IfOLPiJ/46z9q47a9Cw/aNhEM4rS7jXoIIYwx9AIP+siJ/f1hhIcQe8vV9uHH6+PfybcfJ2n3ZzItaS1ZYaggWo8xqszEEmU4FazpJLVmFaEzcsHGThZEMj2xiz028I0jU5iXyj2FgQt6f8ISqfVcZi4pibnUjz0P/+WNa5MPJ5YXVW1YQduD8lpAU0J/KXDKFaNGzJ0gVHH3rZBeErcM466u45Zw96fw/+I06uG4F3122zgCba2CV+A1eAswGIBD8AmcgBGgwXLwLoiD3XAtfB/2w2EbDYPbmS3woMIPNxrjwxI= k=1 with 3(21/3 - 1) = 0.78. We have 0.7 < 0.78. Set is schedulable. Consider a set of processes: P1 = (20,100,100), P2 = (30,150,150), and P3 = (90,200,200): X3 ck 20 30 90 4 4 9 17 U= = + + = + + = = 0.85 tk 100 150 200 20 20 20 20 AAACiXicdZHRatswFIZlr2u7dFuz9XI3omUw2AiS0zTOoFCWi/Wyg6UtxJmRFbkVkWwjyYMg/AK76xv0ldq7vsyYlDS0K9sBm/98/3+QfZRVgmuD0F0QPlt7vr6x+aK19fLV6+32m7enuqwVZSNailKdZ0QzwQs2MtwIdl4pRmQm2Fk2G3r/7CdTmpfFdzOv2ESSi4LnnBLjUNq+HsFDmOhaJoJLbnRqZ4e4+WG7DUxyRail6ayxxr18bkEi1FiMUAM/3oOuB71HYOBA5BOrkX3fP/hP2sGyXYVxf9WjTtxL23uogxDCGEMvcP8AOTEYxBGOIfaWq72jr7+Gv5Orm5O0fZtMS1pLVhgqiNZjjCozsUQZTgVrWkmtWUXojFywsZMFkUxP7GKTDXzvyBTmpXJPYeCCPp6wRGo9l5lLSmIu9VPPw39549rk8cTyoqoNK+jyoLwW0JTQXwuccsWoEXMnCFXcfSukl8Stw7jLa7klrP4U/l+cRh3c7UTf3Da+gGVtgndgF3wAGPTBETgGJ2AEaLAefAp6wUG4FeIwDj8vo2FwP7MD/qpw+AeyRsMS k=1 We have 0.85 > 0.78. Set is not schedulable according to Liu and Layland criterion. © 226  Response-Time Analysis If a process set satis es the Liu and Layland criterion (utilization), then it is guaranteed to be RMA schedulable. However, even if a process set fails to satisfy the Liu and Layland criterion, it still may be RMA schedulable if all processes meet their respective deadlines. The worst-case scenario is the critical instant: all processes are released at the same time resulting in the largest response time of the lowest-priority process. However, if the processes meet their rst deadlines (the rst periods), then they will do so in the future [Lehoczky&Sha]. © 227 fi fi fi Calculating the Slowest Response Pm Pm Pm Pi Pi Pi 0 Tm Consider the processes Pi and Pm arriving at the same time instant 0. During the rst instance of Pm, three instances of process Pi occur, forcing Pm to wait as Pi has a higher priority. l⌧ m The exact number of times Pi occurs is given by ⌧. Since m i Pi’s execution time is ci, the total execution ltime required AAACFnicdVBLSwMxGMzWV62vqkcvwSJ4sexuW60XqRVEPFWwD+guSzbNtqHZB0lWKEt/hQf9J+LFgyJexZv/xmyroKIDIcPMfCTfuBGjQur6u5aZmZ2bX8gu5paWV1bX8usbLRHGHJMmDlnIOy4ShNGANCWVjHQiTpDvMtJ2hyep374iXNAwuJSjiNg+6gfUoxhJJTn5PatO+8ximFAGLY8jnFgSxY4/nt50DNMEt3iacPIFvajrldJ+BepFwzQq5aoiZb10aJrQUFaKQu3otHxzd3zecPJvVi/EsU8CiRkSomvokbQTxCXFjIxzVixIhPAQ9UlX0QD5RNjJZK0x3FFKD3ohVyeQcKJ+n0iQL8TId1XSR3Igfnup+JfXjaVXtRMaRLEkAZ4+5MUMyhCmHcEe5QRLNlIEYU7VXyEeINWNVE3mVAlfm8L/ScssGqWieaHaqIMpsmALbINdYIADUANnoAGaAINrcA8ewZN2qz1oz9rLNJrRPmc2wQ9orx9MYKMM ⌧m m due to process Pi before the deadline of Pm is ⇥ ci. AAACIXicdVDLSsNAFJ3UV62vqks3g0VwVZK01bqRqiDiSsHWQlPCZDqpg5MHMzdCCf0Od278CH/AjQtF3Ik/48QoqOiFYQ7nnMu993ix4ApM89UoTExOTc8UZ0tz8wuLS+XllY6KEklZm0Yikl2PKCZ4yNrAQbBuLBkJPMHOvcuDTD+/YlLxKDyDUcz6ARmG3OeUgKbcctPZ50PhCMq4wI4vCU0dIIkbjPOfj3HmkI7MHcADpjB1uVuumFXTbNS2GtisWrbVqDc1qJu1HdvGlpayqrR2D+vXd3vHJ275xRlENAlYCFQQpXqWGUM/JRI4FWxcchLFYkIvyZD1NAyJHtRPPy4c4w3NDLAfSf1CwB/s946UBEqNAk87AwIX6reWkX9pvQT8Zj/lYZwAC2k+yE8EhghnceEBl4yCGGlAqOR6V0wviI4JdKglHcLXpfh/0LGrVq1qn+o09lFeRbSG1tEmstA2aqEjdILaiKIbdI8e0ZNxazwYz8ZLbi0Ynz2r6EcZb++pbKdj ⌧i © 228 fi Worst-Case Response Time For a process set {P1, P2, …, Pm} and an associated priority assignment π1 > π2 > … > πm, the time for which process Pm will have to wait due to interference by all its higher priority processes is X1⇣l m ⌧m m ⌘ ⇥ck ⌧k AAACS3icdVBBaxNBFJ5Nra1pa6MevQyGQj007G6Sth6E0hzqMYJJC5l0mZ3MJsPO7C4zb4Ww7B/ozX/lpYd680948VARESfZBFT0wfA+vu97vDdfmElhwHU/O7WNB5sPt7Yf1Xd29x7vN548HZo014wPWCpTfRVSw6VI+AAESH6VaU5VKPllGPcW+uV7ro1Ik3cwz/hY0WkiIsEoWCpohMTkikihBJigiF975XWhjrwSk3Mxlfhw1YlkXNgWacoKAjQPVFn1eG0lurKAUNxgFsRLXuOXQaPptly32z7uYrfl+V63c2pBx22/8n3sWWlRzbOLm95P8uGuHzQ+kUnKcsUTYJIaM/LcDMYF1SCY5GWd5IZnlMV0ykcWJtQuHBfLLEp8YJkJjlJtXwJ4yf4+UVBlzFyF1qkozMzf2oL8lzbKITodFyLJcuAJqxZFucSQ4kWweCI0ZyDnFlCmhb0Vsxm1eYGNv25DWP8U/x8M/ZbXbvlvbRrnqKpt9By9QIfIQyfoDL1BfTRADH1EX9A9+ubcOl+d786PylpzVjPP0B9V2/wF+fK3IA== k=1 For process Pm to meet its rst deadline (τm = dm), we require X1⇣l m ⌧m m ⌘ cm + ⇥ck  ⌧m