Subject : Microcontroller and Embedded Programming

Topic : Embedded/Real Time Operating System

Difficulty : Medium

Task scheduling algorithms :

The process of deciding which task will utilize the cpu time is called task scheduling. The scheduling of the task may be on the basis of their priorities. The priority assignment mechanism for the tasks can be either static or dynamic. In the case of static priority assignment the priority of task is assigned as soon as the task is created, thereafter the priorities cannot be changed. In dynamic assigning the priorities of the task can be changed during the runtime.

The various scheduling algorithms followed are:

1. First in first out (FIFO): In this algorithm simply the task that came in first in the ready to run state will go out first into the running state. The task that goes out of the running state goes to the ready to run state. Fig 11.5.a shows the movement of the task in the ready to run and running state

Fig 11.5.a Advantage – it is very easy to implement Disadvantage – we cannot have any priority mechanisms, in real time examples each task has a different priority and it is to be implemented, but using FIFO we cannot implement priority based scheduling.

2. Round robin scheduling: In this case each task gets their turn after all the task are given their time slots. Thus it can be said that it is a time slicing wherein the time for each time slot is same and is given tasks one by one. The CPU time utilization for three tasks according to round robin is shown in fig 11.5.b. In this example, it is assumed that the time slots are 5 milliseconds each.

The switching of tasks occurs in the following case:

1. current task has completed its work before the completion of its time slot
2. current task has no work to be done

3. current task has completed the time slice allocated to it

   ● advantage – very easy to implement

   ● disadvantage – all the tasks are considered at same level

3. Round robin scheduling with priority :

• It is modified version of round robin scheduling mechanism

• In this case the tasks are given priorities based on their significance and deadlines. Thus task with higher priority can interrupt the processor and utilize the CPU time

• If multiple tasks have same priority then round robin scheduling will be used for them. But whenever a higher priority task occurs, it will be executed first. The CPU will suspend the task it was executing and will execute higher priority task.

• For example, bar code scanner can use this scheduling algorithm. This method can be used in soft real time systems.

4. Shortest job first (SJF) scheduling:

● In this case the task with the shortest execution time is executed first. This ensures less number of tasks in the ready state. Thus it can be said that the priority is higher for a task with lesser execution time and the priority of the task is lesser for the task with higher execution time.

● Disadvantage – if there were too many short execution time tasks, then the task with more execution time will never be executed.

● Advantage – the implementation of this scheduling method is also simpler as just the execution time of each of the tasks is ready to run state are to be compared to decide which task will be executed by the processor.

5. Non preemptive scheduling:

● This scheduling mechanism can be implemented in any of the previously seen scheduling mechanisms that have the concept of priority.

● As the name says in this case if a task (say task 1) is in running state and another task (say task 2) with higher priority enters into the ready to run state, the earlier task i.e. task 1 continues with the execution until its time slice and the higher priority task i.e. task 2 has to wait for its turn. The fig 11.5.c shows an example of non-pre-emptive scheduling.

6. Preemptive scheduling:

● This scheduling can be implemented on any of the scheduling mechanisms having concept of priority.

● As the name says in this case if a task (say task 1) is in running state and another task (say task 2) with higher priority enters into the ready to run state , the earlier task i.e. task 1 has to release the CPU and the later task i.e. task 2 will get the execution.

● Thus the higher priority task will get the CPU as soon as it enters into the ready to run state, and this higher priority task will enter to running state. The fig 11.5.d shows an example of preemptive scheduling.