In order to share the task execution environment (CPU, memory, etc..), operating systems provide means to organize the access to these resources. Depending on requirements, the operating system can provide means to achieve multitasking which allows to share the cpu such that several tasks seem to be executing in parallel. Or, to achieve deterministic execution of prioritized tasks, or a combination of both.

The allocation of execution environment to running tasks is defined as scheduling. The major scheduling algorithms are as follows :

A plain Round Robin scheduling algorithm (when there is no notion of task priority) attempts to share the CPU fairly among all ready tasks. Round-robin scheduling uses time slicing to achieve fair allocation of the CPU to all tasks. Each task executes for a defined interval called quantum or time slice.

A preemptive priority-based scheduler preempts the CPU when a task has a higher priority than the current task running. Thus, the kernel ensures that the CPU is always allocated to the highest priority task that is ready to run. This means that if a task– with a higher priority than that of the current task– becomes ready to run, the kernel immediately saves the current task’s context, and switches to the context of the higher priority task. For example, in the figure below, task t1 is preempted by higher-priority task t2, which in turn is preempted by t3. When t3 completes, t2 continues executing. When t2 completes execution, t1 continues executing.

The disadvantage of this scheduling algorithm is that, when multiple tasks of equal priority must share the processor, if a single task is never blocked, it can usurp the processor. Thus, other equal-priority tasks are never given a chance to run. When combined with Round-robin scheduling, the problem is solved.

A Prioritized Round Robin scheduling algorithm attempts to share the CPU fairly among all ready tasks of the same priority. Round-robin scheduling uses time slicing to achieve fair allocation of the CPU to all tasks with the same priority. Each task, in a group of tasks with the same priority, executes for a defined interval or time slice.

The figure below shows round-robin scheduling for three tasks of the same priority: t1, t2, and t3. Task t2 is preempted by a higher priority task t4 but resumes at the count where it left off when t4 is finished.

As long as higher priority tasks are still not completed, the CPU will not be allocated to lower priority tasks. Only tasks of similar or higher priority can preempt a running task.

• "VxWorks Programmer’s Guide"
• Process scheduling in the linux kernel

Labels: embedded