Scheduling Algorithms in Real-Time Systems Overview

3 Real-Time And embedded systems Lecture 3: Scheduling Algorithms in Real-Time Systems Dr. Mahdi Sadeghizadeh Computer Engineering Department Quchan University of Technology February 2019 1

Outline Scheduling Algorithms Fixed Priority Scheduling Rate Monotonic Scheduling (RM) Earliest Deadline First algorithm (EDF) Domino Effect Least Laxity First algorithm (LLF) Priority Inversion Priority Inheritance 2

Scheduling Algorithms Rate Monotonic Scheduling (RM) Earliest Deadline First algorithm (EDF) Least Laxity First algorithm (LLF) 3

Fixed Priority Scheduling Priorities may assigned by Deadline: shortest deadline highest priority Period: shortest period highest priority Importance Scheduler picks from all ready tasks the one with the highest priority to be dispatched. Benefits: Simple to implement Not much overhead Minimal latency for high priority tasks Drawbacks Inflexible Suboptimal (from analysis point of view) 4

Rate Monotonic Scheduling The RM scheduling algorithm is one of the most widely studied and used in practice. The RM is a uniprocessor static-priority preemptive scheme. They are determined only by the period of the task. If Ti < Tjthen Pi > Pj 5

Rate Monotonic Scheduling The utilization factor of a set of n periodic tasks is defined by: ? ?=1 ?? ?? if: ? necessary condition: ?=1 ?? ?? 1 ? ?? ?? ? (2 1 ? 1) Sufficientcondition: ?=1 Then the RM algorithm will schedule all the tasks to meet their respective deadlines. 6

Rate Monotonic Scheduling Example 1: 0.753 0.779 RM-schedulable Example 2: Not RM-schedulable 7

Rate Monotonic Scheduling Example 3: 0.936 8

Earliest Deadline First algorithm (EDF) Dynamic priorities Scheduler picks task, whose deadline is due next EDF is also called the deadline-monotonic scheduling algorithm. The EDF scheduling algorithm is a priority driven algorithm in which higher priority is assigned to the request that has earlier deadline, and a higher priority request always preempts a lower priority one. EDF is an optimal uniprocessor scheduling algorithm. That is, if EDF cannot feasibly schedule a task set on a uniprocessor, there is no other scheduling algorithm that can. ? necessary and Sufficient condition: ?=1 ???? 1 9

Earliest Deadline First algorithm (EDF) ? ???? 1 ?=1 Advantages: Optimality Reduces number of task switches Optimal if system is not overloaded Drawbacks: Deteriorates badly under overload Needs smarter scheduler Scheduling is more expensive 10

Earliest Deadline First algorithm (EDF) Example: 11

Overload Situations in EDF Domino Effect In case of overhead (U > 1), we can have the domino effect with EDF: it means that all tasks miss their deadlines. An example of domino effect is the following; Domino Effect 12

Least Laxity First algorithm (LLF) In addition to EDF algorithm, there is another optimal dynamic-priority scheduling algorithm, which is the least laxity first (LLF) algorithm. The laxity of a process is defined as the deadline minus remaining computation time. In other words, the laxity of a job is the maximal amount of time that the job can wait and still meet its deadline. The algorithm gives the highest priority to the active job with the smallest laxity. Then the job with the highest priority is executed. While a process is executing, it can be preempted by another whose laxity has decreased to below that of the running process. A problem arises with this scheme when two processes have similar laxities. One process will run for a short while and then get preempted by the other and vice versa. Thus, many context switches occur in the lifetime of the processes. 13

Least Laxity First algorithm (LLF) 14

Example 1: 15

Example 1: The timing diagrams of the schedules provided by the earliest deadline first (EDF), rate monotonic (RM), and least laxity first (LLF) algorithms happen to be the same, as indicated in this Figure. 16

Example 2: 17

Example 2: earliest deadline first algorithm 18

Example 2: rate monotonic algorithm 19

Example 2: least laxity first algorithm 20

Priority Inversion In a preemptive priority based real-time system, sometimes tasks may need to access resources that cannot be shared. For example, a task may be writing to a block in memory. Until this is completed, no other task can access that block, either for reading or for writing. The method of ensuring exclusive access is to guard the critical sections with binary semaphores. When a task seeks to enter a critical section, it checks if the corresponding semaphore is locked. If it is,the task is stopped and cannot proceed further until that semaphore is unlocked. Priority Inversion Happens when task is blocked in acquiring semaphore from held by lower priority task which is preempted by medium priority task. Similar case for server tasks. 21

Priority Inversion 22

Priority Inversion 23

Priority Inheritance When a lower priority task locks a critical section shared with the higher priority task, the priority inheritance protocol is used to prevent a medium priority task from preempting the lower priority task. When lower priority job blocks, it inherits priority of blocked job. GOOD No unbounded priority inversion Simple No prior knowledge required Works with fixed and dynamic priorities. BAD Possible Deadlock. Blocking of jobs not in resource contention. Blocking time could be better Indirection a pain in the neck Although the Priority Inheritance Protocol prevents unbounded blocking of a higher priority task by a lower priority task, it does not guarantee that mutual deadlocks will not occur. 24

Priority Inheritance 25

Thank You 26