Which of the following is are examples of preemptive scheduling algorithm?

7.4.3 Preemptive scheduling

Preemptive scheduling is the most commonly used scheduling algorithm in real-time systems. Here, the tasks are prioritized and the task with the highest priority among all other tasks gets the CPU time (see Fig. 7.5). If a task with a priority higher than the currently executing task becomes ready to run, the kernel saves the context of the current task and switches to the higher priority task by loading its context. Usually, the highest priority task runs to completion or until it becomes noncomputable, for example, waiting for a resource to become available, or calling a function to delay. At this point, the scheduler determines the task with the highest priority that can run and loads the context of this task and starts executing it. Although the preemptive scheduling is very powerful, care is needed as a programming error can place a high priority task in an endless loop and thus not release the CPU to other tasks. Some multitasking systems employ a combination of round-robin and preemptive scheduling. In such systems, time-critical tasks are usually prioritized and run under preemptive scheduling, whereas the nontime critical tasks run under round-robin scheduling, sharing the left CPU time among themselves.

It is important to realize that in a preemptive scheduler, tasks at the same priorities run under round-robin. In such a system, when a task uses its allocated time, a timer interrupt is generated by the scheduler which saves the context of the current task and gives the CPU to another task with equal priority that is ready to run, provided that there are no other tasks with higher priorities which are ready to run.

The priority in a preemptive scheduler can be static or dynamic. In a static priority system tasks used the same priority all the time. In a dynamic priority-based scheduler, the priority of the tasks can change during their courses of execution.

So far, we have said nothing about how various tasks work together in an orderly manner. In most applications, data and commands must flow between various tasks so that the tasks can co-operate and work together. One very simple way of doing this is through shared data held in RAM where every task can access. Modern RTOS systems, however, provide local task memories and inter-task communication tools such as mailboxes, pipes, and queues to pass data securely and privately between various tasks. In addition, tools such as event flags, semaphores, and mutexes are usually provided for inter-task communication and synchronization purposes and for passing data between tasks.

The main advantage of a preemptive scheduler is that it provides an excellent mechanism where the importance of every task may be precisely defined. On the other hand, it has the disadvantage that a high priority task may starve the CPU such that lower priority tasks can never have the chance to run. This can usually happen if there are programming errors such that the high priority task runs continuously without having to wait for any system resources and never stops.

15.2.2 Preemptive Scheduling

In a preemptive scheduling once the CPU is given to a task it can be taken away, for example when a higher priority task wants the CPU. Preemptive scheduling is used in real-time systems where the tasks are usually configured with different priorities and time critical tasks are given higher priorities. A higher priority task can stop a lower priority one and grab and use the CPU until it releases it. In preemptive scheduling the task contexts are saved so that the tasks can resume their operations from the point they left when they are given back the CPU.

Preemptive scheduling is normally implemented in two different ways: using Round Robin (RR) scheduling, or using interrupt-based (IB) scheduling.

In RR scheduling all the tasks are given equal amount of CPU times and tasks do not have any priorities. When the CPU is to be given to another task, the context of the current task is saved and the next task is started. The task context is restored when the same task gets control of the CPU. RR scheduling has the advantage that all the tasks get equal amount of the CPU time. It is however not suitable in real-time systems since a time critical task cannot get hold of the CPU when it needs to. Also, a long task can be stopped before it completes its operations. Fig. 15.2 shows an example RR type scheduling with three tasks.

In IB scheduling tasks may be given different priorities and the task with the highest priority gets hold of the CPU. Tasks with same priorities are executed with RR type scheduling where they are all given equal amount of CPU time. IB scheduling is best suited to real-time systems where time critical tasks are given higher priorities. The disadvantages of IB scheduling are that it is complex to implement, and also there is too much overhead in terms of context saving and restoring. Fig. 15.3 shows an example IB type scheduling with three tasks where Task1 has the lowest priority and Task2 has the highest priority.

2 Preemptive vs. non-preemptive scheduling

Non-preemptive scheduling is the standard mode of operation in PSE models, see Figure 1. Given a break period br occurring in time window [bbrL, bbrU], task i can either be completely executed before the start of the break or start after the end of the break. In the context of a continuous-time model (Castro et al. 2014a), it can be formulated as an exclusive disjunction featuring starting variable Tsi and duration parameter pi. When using a discrete-time model, break periods help to reduce model size by restricting the domain of task extent 0-1 variables Ni,t. In the example in Figure 2, the break lasts for 5 time intervals, including slots {9, …, 13} (in red). Noting that durations pi in minutes or hours are rounded up to multiples of δ (parameter specifying the length of every slot in the uniform grid), τi = ⌈pi/δ⌉, since the task lasts 5 slots (in grey), it can only start between slots 1 (Ni,1 = 1) and 4 (Ni,4 = 1), if the plan is to end before the break, or at slot 14, if started after the break, i.e. Ti ∈ {1, …, 4, 14}.

The goal of preemptive scheduling is to reduce idle times by allowing part of the task to be executed before the break and part after the break, see middle of Figure 3. Since the location of break periods is known a priori, one can easily determine the duration of a task τ¯i,tas a function of its starting point t. In the alternatives illustrated in Figure 3, the duration of the task changes between 5 (non-preemption duration), 10 (one interruption) and 12 (two breaks). The domain of the task is thus wider when allowing for preemption.

18.4.5 Cooperative scheduling

The scheduling strategy just discussed, prioritised pre-emptive scheduling, represents classic RTOS action. It is not without disadvantage, however. The scheduler must hold all context information for all tasks that it pre-empts. This is generally done in one stack per task and is memory-intensive. The context switching can also be time-consuming. Moreover, tasks must be written in such a way that they can be switched at any time during their operation.

An alternative to pre-emptive scheduling is ‘cooperative’ scheduling. Now each task must relinquish, of its own accord, its CPU access at some time in its operation. This sounds like we're blocking out the operating system, but if each task is written correctly this need not be. The advantage is that the task relinquishes control at a moment of its choosing, so it can control its context saving and the central overhead is not required.

Cooperative scheduling is unlikely to be quite as responsive to tight deadlines as pre-emptive scheduling. It does, however, need less memory and can switch tasks quicker. This is very important in the small system, such as one based on a PIC microcontroller.

6.2.2.2 Embedded VMs and Scheduling

VM mechanisms, such as a scheduler within an embedded VM, are one of the main elements that give the illusion of a single processor simultaneously running multiple tasks or threads (see Figure 6.31). A scheduler is responsible for determining the order and the duration of tasks (or threads) to run on the CPU. The scheduler selects which tasks will be in what states (Ready, Running, or Blocked), as well as loading and saving the information for each task or thread.

There are many scheduling algorithms implemented in embedded VMs, and every design has its strengths and tradeoffs. The key factors that impact the effectiveness and performance of a scheduling algorithm include its response time (time for scheduler to make the context switch to a ready task and includes waiting time of task in ready queue), turnaround time (the time it takes for a process to complete running), overhead (the time and data needed to determine which tasks will run next), and fairness (what are the determining factors as to which processes get to run). A scheduler needs to balance utilizing the system's resources – keeping the CPU, I/O, as busy as possible – with task throughput, processing as many tasks as possible in a given amount of time. Especially in the case of fairness, the scheduler has to ensure that task starvation, where a task never gets to run, doesn’t occur when trying to achieve a maximum task throughput.

One of the biggest differentiators between the scheduling algorithms implemented within embedded VMs is whether the algorithm guarantees its tasks will meet execution time deadlines. Thus, it is important to determine whether the embedded VM implements a scheduling algorithm that is non-preemptive or preemptive. In preemptive scheduling, the VM forces a context-switch on a task, whether or not a running task has completed executing or is cooperating with the context switch. Under non-preemptive scheduling, tasks (or threads) are given control of the master CPU until they have finished execution, regardless of the length of time or the importance of the other tasks that are waiting. Non-preemptive algorithms can be riskier to support since an assumption must be made that no one task will execute in an infinite loop, shutting out all other tasks from the master CPU. However, VMs that support non-preemptive algorithms don’t force a context-switch before a task is ready, and the overhead of saving and restoration of accurate task information when switching between tasks that have not finished execution is only an issue if the non-preemptive scheduler implements a cooperative scheduling mechanism.

As shown in Figure 6.32, Jbed contains an earliest deadline first (EDF)-based scheduler where the EDF/Clock Driven algorithm schedules priorities to processes according to three parameters: frequency (number of times process is run), deadline (when processes execution needs to be completed), and duration (time it takes to execute the process). While the EDF algorithm allows for timing constraints to be verified and enforced (basically guaranteed deadlines for all tasks), the difficulty is defining an exact duration for various processes. Usually, an average estimate is the best that can be done for each process.

Under the Jbed RTOS, all six types of tasks have the three variables ‘duration’, ‘allowance’, and ‘deadline’ when the task is created for the EDF scheduler to schedule all tasks (see Figure 6.33 for the method call).

The Kaffe open source JVM implements a priority-preemptive-based scheme on top of OS native threads, meaning jthreads are scheduled based upon their relative importance to each other and the system. Every jthread is assigned a priority, which acts as an indicator of orders of precedence within the system. The jthreads with the highest priority always preempt lower-priority processes when they want to run, meaning a running task can be forced to block by the scheduler if a higher-priority jthread becomes ready to run. Figure 6.34 shows three jthreads (1, 2, 3 – where jthread 1 is the lowest priority and jthread 3 is the highest, and jthread 3 preempts jthread 2, and jthread 2 preempts jthread 1).

As with any VM with a priority-preemptive scheduling scheme, the challenges that need to be addressed by programmers include:

JThread starvation, where a continuous stream of high-priority threads keeps lower-priority jthreads from ever running. Typically resolved by aging lower-priority jthreads (as these jthreads spend more time on queue, increase their priority levels).

Priority inversion, where higher-priority jthreads may be blocked waiting for lower-priority jthreads to execute, and jthreads with priorities in between have a higher priority in running, thus both the lower-priority as well as higher-priority jthreads don’t run (see Figure 6.35).

How to determine the priorities of various threads. Typically, the more important the thread, the higher the priority it should be assigned. For jthreads that are equally important, one technique that can be used to assign jthread priorities is the Rate Monotonic Scheduling (RMS) scheme which is also commonly used with relative scheduling scenerios when using embedded OSs. Under RMS, jthreads are assigned a priority based upon how often they execute within the system. The premise behind this model is that, given a preemptive scheduler and a set of jthreads that are completely independent (no shared data or resources) and are run periodically (meaning run at regular time intervals), the more often a jthread is executed within this set, the higher its priority should be. The RMS Theorem says that if the above assumptions are met for a scheduler and a set of ‘n’ jthreads, all timing deadlines will be met if the inequality Σ Ei/Ti ≤ n(21/n – 1) is verified, where

i = periodic jthread

n = number of periodic jthreads

Ti = the execution period of jthread i

Ei = the worst-case execution time of jthread i

Ei/Ti = the fraction of CPU time required to execute jthread i.

So, given two jthreads that have been prioritized according to their periods, where the shortest-period jthread has been assigned the highest priority, the ‘n(21/n – 1)’ portion of the inequality would equal approximately 0.828, meaning the CPU utilization of these jthreads should not exceed about 82.8% in order to meet all hard deadlines. For 100 jthreads that have been prioritized according to their periods, where the shorter period jthreads have been assigned the higher priorities, CPU utilization of these tasks should not exceed approximately 69.6% (100  ×  (21/100 − 1)) in order to meet all deadlines. See Figure 6.36 for additional notes on this type of scheduling model.

Abstract

Modes of operation and mode changes are a useful abstraction to allow configurable real-time systems. Substantial work on the fixed priority preemptive scheduling approach allowed tasks across a mode change to be provided with real-time guarantees. However, the proper configuration of critical parameters such as task’s offsets, despite initial work, remains lacking in the research. Without a method that automates this design step, while assuring that the basic requirements are met, the full adoption of mode changes in real-time systems remains limited to relatively simple systems with limited task sets. In this work, we propose a method to assign offsets to tasks across a mode change that is able to minimize the latency of a mode change using genetic algorithms. Through a number of case studies, using an image-processing application as an example, we both validate the approach as well as show that the method is flexible in that it can accommodate other requirements, such as the minimization of offsets.

Project 7.18 Multitasking

Most complex real-time systems consist of a number of tasks running independently. This requires some form of scheduling and task control mechanisms. For example, consider an extremely simple real-time system that must flash an LED at required intervals and at the same time look for a key input from a keypad. One solution would be to scan the keypad in a loop at regular intervals while flashing the LED at the same time. Although this approach may work for simple systems, in most complex real-time systems, a real-time operating system (RTOS) or a multiprocessing approach are usually employed. Multiprocessing is beyond the scope of this project.

An RTOS is a program that manages system resources, scheduling the execution of various tasks in the system and provides services for intertask synchronization and messaging. There are many books and other sources of reference that describe the operation and principles of various RTOS systems.

Every RTOS consists of a kernel that provides the low-level functions, mainly the scheduling, creation of tasks and intertask resource management. Most complex RTOSs also provide file-handling services, disk input–output operations, interrupt servicing, network management, user management, and so on.

A task is an independent thread of execution in a multitasking system, usually with its own local set of data. A multitasking system consists of a number of independent tasks, each running its own code and communicating with each other to have orderly access to shared resources. The simplest RTOS consists of a scheduler that determines the order in which the tasks should run. This scheduler switches from one task to the next by performing a context switching where the context of the running task is stored and context of the next task is loaded so that execution can continue properly with the next task. Tasks are usually in the form of endless loops, executed in an order determined by the scheduler.

Although there exists many variations of scheduling algorithms in use, the three most commonly used algorithms are as follows:

Cooperative scheduling,

Round-robin scheduling,

Preemptive scheduling.

Cooperative Scheduling

This is perhaps the simplest algorithm (Figure 7.150) where tasks voluntarily give up the central processing unit (CPU) usage when they have nothing useful to do, or when they are waiting for some resources to become available (e.g. a key to be pressed and a timer to expire). This algorithm has the disadvantage that certain tasks can use excessive CPU times, and thus not allow some other important tasks to run when needed. Cooperative scheduling is used in simple multitasking systems with no time critical applications. A variation of the pure cooperative scheduling is to prioritize the tasks and run the highest priority computable task when the CPU becomes available. As we shall see in an example project later, cooperative scheduling can easily be implemented in microcontrollers using the switch statement.

Figure 7.150. Cooperative Scheduling.

Round-robin Scheduling

Round-robin scheduling (Figure 7.151) allocates each task an equal share of the CPU time. In its simplest form, tasks are in a circular queue and when a task's allocated CPU time expires, the task is put to the end of the queue and the new task is taken from the front of the queue. Round-robin scheduling is not very satisfactory in many real-time applications where each task can have varying amounts of CPU requirements depending upon the complexity of processing required. One variation of the pure round-robin scheduling is to provide priority-based scheduling, where tasks with the same priority levels receive equal amounts of CPU time. It is also possible to allocate different maximum CPU times to each task. An example project is given later on the use of round-robin scheduling.

Figure 7.151. Round-robin Scheduling.

Preemptive Scheduling

This is the most commonly used and the most complex scheduling algorithm used in real-time systems. Here, the tasks are prioritized, and the task with the highest priority among all other tasks gets the CPU time (Figure 7.152). If a task with a priority higher than the currently executing task becomes ready to run, the scheduler saves the context of the current task and switches to the higher priority task by loading its context. Usually, the highest priority task runs to completion or until it becomes noncomputable (e.g. waiting for a resource to be available). Although the preemptive scheduling is very powerful, care is needed as an error in programming can place a high priority task in an endless loop and thus not release the CPU to other tasks. Some real-time systems employ a combination of round-robin and preemptive scheduling. In such systems, time critical tasks are usually prioritized and run under preemptive scheduling, whereas less time-critical tasks run under the round-robin scheduling, sharing the left CPU time among themselves.

Figure 7.152. Preemptive Scheduling.

There are many commercially available, shareware, and open-source RTOS software for the PIC microcontrollers. Brief details of some popular RTOS systems are given below.

Salvo (www.pumpkininc.com) is a low-cost, event driven, priority-based, multitasking RTOS designed for microcontrollers with limited data and program memories. Salvo can be used for many microcontroller families and it supports large number of compilers, such as Keil C51, Hi-Tech 8051, Hi-Tech PICC-18, MPLAB C18, and many others. A demo version (Salvo Lite) is available for evaluation purposes. The Pro version is the top model aimed for professional applications, supporting unlimited number of tasks with priorities, event flags, semaphores, message queues, and many more features.

CCS compiler (www.ccsinfo.com) from Custom Computer services Inc supports a cooperative RTOS with a number of functions to start and terminate tasks, to send messages between tasks, to synchronize tasks using semaphores, and so on.

CMX-Tiny+ (www.cmx.com) supports large number of microcontrollers. This is a preemptive RTOS with a large number of features such as event-flags, cyclic timers, message queues, and semaphores. Although CMX-Tiny+ is a sophisticated RTOS, it has the disadvantage that the cost is relatively high.

PICos18 (www.picos18.com) is an open-source preemptive RTOS for the PIC18 microcontrollers. The full documentation and the source code are provided free of charge for people wishing to use the product.

MicroC/OS-II (http://micrium.com) is a preemptive RTOS, which has been ported to many microcontrollers, including the PIC family. This is a very sophisticated RTOS, providing semaphores, mailboxes, event-flags, timers, memory management, message queues, and many more.

FreeRTOS (www.freertos.org) is an open-source RTOS that can be used in microcontroller-based projects. This is a preemptive RTOS but can be configured for cooperative or hybrid operations.

Finally, OSA-RTOS (http://picosa.narod.ru) is freeware RTOS for PIC microcontrollers. The full source code and documentation are available and can be downloaded. OSA is a cooperative multitasking RTOS, offering many features such as semaphores, data queues, mutexes, memory pools, system services, and many more.

Hardware-software scheduling

Scheduling enables hardware and software resource sharing. On the process level, there are several scheduling policies derived from RTOSs,28 for example, static table-driven, priority-based preemptive scheduling, and various other dynamic plan-based policies that have not yet been applied to codesign.

Priority-based preemptive scheduling is the classic approach of commercial RTOSs. Process priorities are determined a priori (static priority) or at runtime (dynamic priority). They are used in reactive as well as dataflow systems with sufficiently coarse process granularity. Dynamic priority assignment requires a runtime scheduler process that assigns priorities according to process deadlines. This increases component utilization, in particular for reactive systems, but makes timing verification harder.

In static (table-driven) scheduling, the order of process execution is determined at design time. It has been used for periodic process scheduling, where a static schedule exists for the least common multiple (LCM) of all process periods.29 The process sequence can be stored in a schedule table, but the processes can also be merged into a sequence to use the compiler (or the synthesis tool) to minimize context switching overhead,30 usually at the cost of a larger program. This is the domain of small processes, where context switching times are significant compared with the process execution times. Static scheduling can also combine with preemptive scheduling. Processes communicating with static data flow triggered by the same event can be clustered and scheduled statically, while the process clusters are scheduled preemptively. This allows for local dataflow optimization, including pipelining and buffering.

In recent years, static scheduling has also been used in event-driven reactive systems. A first approach is to adapt the sequence of executions in a static schedule to the input events and data.17 A second approach is to collect all parts of a process activated by the same event in one static thread of operations,31 which can then be statically scheduled into a single process. Both scheduling approaches can be combined and used as a basis for process merging in event-driven systems.

Complex embedded architectures require distributed scheduling policies for hardware and software parts such as scheduling, which is optimized for several communicating hardware and software components. Communication, especially in context with processing, has drawn little attention in RTOS research or has been treated pessimistically.12 This treatment is not acceptable for highly integrated embedded systems, where communication and buffering have a major impact on performance, power consumption, and cost. Global approaches to distributed scheduling of communicating processes have been proposed for preemptive12 and static scheduling.29

Instead of a uniform scheduling policy, components or subsystems may use different policies, especially when combining different but compatible system types; but the policies must be compatible. An example is the TOSCA system.9 It uses static priority scheduling for software implementation of concurrent finite-state machines, while the hardware side does not share resources, thus avoiding hardware scheduling. In the POLIS system,8,18 software scheduling is even less constrained. A more complicated approach32 proposes static priority (rate monotonic)28 software scheduling combined with interrupt-activated, shared-hardware coprocessors in a robot control system. Notably, out of these global policies, only the static uniform approach supports global buffering between components, which is explained by the complex behavior of preemptive scheduling.

Exploiting process semantics, such as mutually exclusive process execution and conditional communication,32,33 can improve scheduling efficiency. In static scheduling, this knowledge can optimize utilization,33 while in preemptive scheduling, it can help to verify timing constraints and to optimize communication.

A major problem of static scheduling is data-dependent process execution found not only in software execution, but also in hardware with conditional control flow. Since non-preemptive scheduling must assume worst-case behavior, data-dependent timing leads to lower average system performance. One approach is to resort to dynamic scheduling with local buffers, even in purely static dataflow applications.34

The variety of process models of computation and scheduling policies (and their possible combinations) is a challenge to design space exploration and cosynthesis. It requires design representations that allow the mixing and matching of different models of computation for scheduling. Software reuse and object-oriented design imply that critical system parts that the designer knows in detail will combine with less familiar legacy code.

Priority Inversion

Finally, no discussion of RTOS scheduling would be complete without mentioning priority inversion.

In a preemptive scheduling system, it is possible for a high-priority thread T1 to block while it calls a low-priority thread T3 to perform a critical function before T1 continues. However, the low-priority thread T3 could be preempted by a medium priority thread T2. Now T2 is free to run until it blocks (assuming it does) before allowing T3 to resume completing its operation and allowing T1 to resume execution. The upshot is the high-priority thread T1 is blocked and becomes dependent on T2 to complete before it can resume execution.

osThreadSetPriority(t_phaseD, osPriorityHigh); //raise the priority of thread phaseD

 osSignalSet(t_phaseD,0x001); //trigger it to run// Call task four to write to the LCD

 osSignalWait(0x01,osWaitForever); //wait for thread phase D to complete

osThreadSetPriority(t_phaseD,osPriorityBelowNormal); //lower its priority

The answer to this problem is priority elevation. Before T1 calls T3, it must raise the priority of T3 to its level. Once T3 has completed its priority can be lowered back to its initial state.

Which of the following is a preemptive scheduling algorithm?

What is preemptive priority scheduling with example?

Is an example of non preemptive scheduling algorithm?

Which is preemptive scheduling?