Embedded system scheduling Algorithm .pptx

Embedded Algorithms:
Embedded system scheduling (power optimised scheduling algorithm)

1. Marathwada Mitramandal’s COLLEGE OF ENGINEERING Karvenagar, Pune Accredited with ‘A++’ Grade by NAAC Presentation On Subject: 410241 :Design and Analysis of Algorithms By Dr. Swati Shekapure Department of Computer Engineering

2. Content Embedded Algorithms: Embedded system scheduling (power optimised scheduling algorithm)

3. Embedded system scheduling algorithms From digital camera to mobile phones, embedded systems can be found in every aspect of our life. In recent years, embedded systems have become more and more resource intensive because of the increase demand for real-time and quality-of-service(QoS) requirements. There is a urgent need to design a system that can meet the functional and timing requirements.

4. Embedded system scheduling algorithms Embedded systems - Computer systems that are designed to perform a small or specific set of tasks, often in. At the bare minimum embedded systems are single CPU systems with a relatively small and fixed amount of memory but they can also include other IC’s or I/O devices which interface with the main CPU. Scheduling - A function of an operating system which manages which process will get to run next on the CPU, and how long processes or tasks get to run on the CPU.

5. Embedded system scheduling algorithms On embedded systems real-time processes must execute before a certain time and sometimes they are performing atomic operations, which cannot be disrupted once they start. These types of processes create the necessity to use non-preemptive scheduling algorithms and the need to choose processes in an order that will optimize system efficiency. Real time - Used to characterize a time constraint of a task of process. Embedded systems sometimes have to be able to execute real time tasks depending on the use of the embedded system. EDF - a dynamic scheduling algorithm used in real-time operating systems. It assigns priority to process that has the earliest deadline.

6. Embedded system scheduling algorithms

7. Embedded system scheduling algorithms There are several known real-time algorithms for embedded systems. They are Earliest Deadline First (EDF), Least laxity first (LLF) and Rate Monotonic Scheduling (RMS).

8. Embedded system scheduling algorithms In EDF, tasks are scheduled by the order of deadline. In LLF, tasks are scheduled by the order of laxity. EDF and LLF do not work very well in situations that soft real-time applications compete with higher priority applications. In RMS, tasks are scheduled by static priority that is determined by duration. The shorter the job duration is, the higher its priority is. It guarantees time restraints up to 70% CPU load. When the load is above 70%, it does not support dynamic systems very well.

9. Embedded system scheduling algorithms In EDF, tasks are scheduled by the order of deadline. In LLF, tasks are scheduled by the order of laxity. EDF and LLF do not work very well in situations that soft real-time applications compete with higher priority applications. In RMS, tasks are scheduled by static priority that is determined by duration. The shorter the job duration is, the higher its priority is. It guarantees time restraints up to 70% CPU load. When the load is above 70%, it does not support dynamic systems very well.

10. Embedded system scheduling algorithms Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution.

11. Embedded system scheduling algorithms EDF is an optimal scheduling algorithm on preemptive uniprocessors, in the following sense: if a collection of independent jobs, each characterized by an arrival time, an execution requirement and a deadline, can be scheduled (by any algorithm) in a way that ensures all the jobs complete by their deadline, the EDF will schedule this collection of jobs so they all complete by their deadline.

12. Embedded system scheduling algorithms U = 1/4 +2/6 +3/8 = 0.25 + 0.333 +0.375 = 0.95 = 95% As processor utilization is less than 1 or 100% so task set is surely schedulable by EDF. Task Release time(ri) Execution Time(Ci Deadline (Di) Time Period(Ti) T1 1 4 4 T2 2 6 6 T3 3 8 8

13. Embedded system scheduling algorithms At t=0 all the tasks are released, but priorities are decided according to their absolute deadlines so T1 has higher priority as its deadline is 4 earlier than T2 whose deadline is 6 and T3 whose deadline is 8, that’s why it executes first. At t=1 again absolute deadlines are compared and T2 has shorter deadline so it executes and after that T3 starts execution but at t=4 T1 comes in the system and deadlines are compared, at this instant both T1 and T3 has same deadlines so ties are broken randomly so we continue to execute T3.

14. Embedded system scheduling algorithm 3. At t=6 T2 is released, now deadline of T1 is earliest than T2 so it starts execution and after that T2 begins to execute. At t=8 again T1 and T2 have same deadlines i.e. t=16, so ties are broken randomly an T2 continues its execution and then T1 completes. Now at t=12 T1 and T2 come in the system simultaneously so by comparing absolute deadlines, T1 and T2 has same deadlines therefore ties broken randomly and we continue to execute T3. 4. At t=13 T1 begins it execution and ends at t=14. Now T2 is the only task in the system so it completes it execution.

15. Embedded system scheduling algorithm 5. At t=16 T1 and T2 are released together, priorities are decided according to absolute deadlines so T1 execute first as its deadline is t=20 and T3’s deadline is t=24.After T1 completion T3 starts and reaches at t=17 where T2 comes in the system now by deadline comparison both have same deadline t=24 so ties broken randomly ant we T continue to execute T3. 6. At t=20 both T1 and T2 are in the system and both have same deadline t=24 so again ties broken randomly and T2 executes. After that T1 completes it execution. In the same way system continue to run without any problem by following EDF algorithm.

16. Wrap Up What do mean by Randomised and Approximate algorithms? What are the different Embedded system scheduling algorithms?