24 RTOS: Scheduling policies-1
Dr K. Vani
In this module, basic concepts of scheduling and types of scheduling policies will be discussed. Context switching and preemption scheduling will also be explained in detail in this module.
1.Basic Concepts
Maximum CPU utilization is obtained with multiprogramming by keeping several processes in memory at one time. Scheduling of the CPU among these processes is one of the fundamental issues in an operating system. The Process execution consists of a cycle of a CPU time burst and an I/O time burst. When a process executes, it alternates between these two states (i.e., CPU burst and I/O burst). Each and every time a running process waits, another process can take over the use of the CPU. A CPU scheduler determines which process can take over the use of the CPU.
1.1 CPU Scheduler
The CPU scheduler selects from among the processes in memory that are ready to execute and allocates the CPU to one of them. The process of choosing the order of running processes is known as scheduling. Scheduling states are given as follows: waiting, ready, or executing.One process must be executing on the CPU at any time. The scheduling by OS is explained in detail in the figure 1.1 shown below.
The CPU scheduling is affected by the following set of circumstances:
1. A process switches from the running to waiting state.
2. A process switches from the running to ready state.
3. A process switches from the waiting to ready state.
4. A process switches from the running to terminated state.
Consider that a process is in running state. If an interrupt occurs, it moves to the ready state and if the interrupt process is completed, the scheduler dispatches from the ready state to the running state. If the process is in running state and in requirement of I/O or needs to wait for an event, the scheduler moves it to the waiting state. Once the I/O or event are ready/available, the process is moved to the ready state. Once the process is completed, it is moved to the terminated state.
2. Scheduling policy in RTOS:
Each task in an embedded application has an infinite loop from start to finish.To achieve efficient CPU utilization a multitasking RTOS uses an orderly transfer of control from one code entity to another. To accomplish this the RTOS must monitor the system resources and the execution state of each code entity, and it must ensure that each entity receives the control of the CPU in a timely manner.The key word here is work in a timely manner.
A real-time system that does not perform a required operation at the correct time is said to have failed. That failure can have consequences that range from benign to catastrophic. The response time for a request of kernel services and the execution time of these services must be fast and predictable. In an RTOS, the application program code has to be designed to ensure that all its needs are detected and processed. Real-time applications usually consist of several tasks (also can be called processes or threads) that require control of system resources at varying times due to external or internal events. Each task must compete with all other tasks for control of system resources such as memory, execution time, or peripheral devices.
The developer uses the scheduling models in the RTOS to manage this “competition” between the tasks. The program code can be compute-bound (heavily dependent on CPU resources) or I/O-bound (heavily dependent on access to external devices). Program code that is I/O bound or compute bound is not allowed to monopolize a system resource if more important tasks requires the same resource.
Scheduling policies determine how the processes are selected for execution. Scheduling policies can also deliver higher CPU utilization. Right scheduling policies meet all the timing requirements and also properly utilize the CPU.
Some of the scheduling policies are discussed in detail.
2.1. Simple Scheduling
A very simple scheduling policy is known as cyclo static scheduling or sometimes as Time Division Multiple Access Scheduling. Time Division Multiple Access divides the time into equal-sized time slots over an interval equal to the length of the hyper-period H. Processes always run in the same time slot. It is depending on the deadlines for some of the processes. Some time slots will be empty. Since the time slots are of equal size, some short processes may have time left over in their time slot. Utilization is used as a schedulability measure.The total CPU time of all the processes must be less than the hyper-period. An example of Time division multiple access is shown in Figure 1.2. It shows three processes scheduled using TDMA.
Another scheduling policy that is slightly more sophisticated is round robin. Round robin uses the same hyperperiod as cyclostatic.
2.2 Round robin
Here also, the processes are scheduled in a cyclic fashion. However, if a process does not have any useful work to do, the round-robin scheduler moves on to the next process in order to fill the time slot with useful work.
Example: All three processes execute during the first hyper-period, but during the second one, P1 has no useful work and is skipped. The processes are always executed in the same order and are shown in Figure 1.3.
2.3.Pre-emptive Scheduling
Pre-emption is a mechanism to stop a current process and provide service to another process. In a preemptive model, the tasks can be forcibly suspended. This is initiated by an interrupt on the CPU. OS schedules such that the higher priority task, when ready, preempts a lower priority by blocking the current running task. It solves the problem of large worst case latency for higher priority tasks.
In the preemptive scheduling model, a task must be in one of four states:
● Running –In this state, the task is in control of the CPU.
●Ready – In this state, the task is not blocked and is ready to receive control of the CPU when the scheduling policy indicates it is the highest priority task in the system that is not blocked.
Inactive and blocked are the two waiting states.
● Inactive – In Inactive state, the task is blocked and requires initialization in order to become ready.
● Blocked – In blocked state, the task is waiting for something to happen or for a resource to become available.
There must be a way of interrupting the operation of the lesser task and granting the resource to the more important one. Then the highest-priority task ready to run is always given control of the CPU. If an ISR makes a higher-priority task ready, the higher-priority task is resumed (instead of the interrupted task). Most commercial real-time kernels are preemptive.
Example of pre-emptive scheduling is shown in figure 1.4. In this, each task has a priority relative to all the other tasks. The most critical task is assigned the highest priority. The highest priority task that is ready to run gets control of the processor. A task runs until it yields, terminates, or blocks. Each task has its own memory stack. Before a task can run it must load its context from its memory stack (this can take many cycles). If a task is preempted it must save its current state/context; this context is restored when the task is given control of the processor. Thus context switch is an important aspect in preemptive scheduling, and is discussed in detail below.
2.3.1 Why we use Pre-emptive Scheduling
The reason for the use of Pre-emptive scheduling is to reduce the limitations in cooperative and cyclic scheduling of tasks.
Cooperative scheduling: It waits for the running task to get finished and then schedules each ready task. A long execution time of a low- priority task lets a high priority task wait until the low-priority task finishes.
Cyclic scheduling: Assume that the cooperative scheduler is cyclic, without having a predefined time slice. Consider that an interrupt for service occurs from the first task, just at the beginning of the second task. Then the first task service waits till all other remaining listed or queued tasks finish. Worst case latency equals the sum of execution times of all tasks.
2.3.2 Advantage of Preemptive Scheduler:
The advantage of preemptive scheduler is that, the execution of the highest-priority task is deterministic and the task-level response time will be minimized.
2.3.3 Disadvantage of Preemptive Scheduler:
It should not use non-reentrant functions unless exclusive access to these functions is ensured.
2.4.Context Switch
The set of registers that define a process is known as its context. The switching from one process register set to another register set is known as context switching. The data structure that holds the state of the process is known as the process control block (PCB). That is, the context of a process is represented in the PCB. The time it takes is dependent on the hardware support. The context-switch time is overhead, the system won’t do any useful work while switching.
2.4.1 Context Switch between processes
Context switch between two processes is shown in Figure 1.5 given below. Here the process is first switched from the user space to kernel space while switching between two processes P0 and P1.
Context switch between the processes are shown in figure 1.6. For switching, first the process P0 gives interrupt or system call to save the state into process control Block PCB0. At that time the process P1 is in the idle state. Then the process P0 will enter into reload state of PCB1. Then the process P0 enters into idle state, P1 enters into executing state. After that it transfers the control to process P0 then it goes to save state into PCB1. Then the control is transferred to the reload state of PCB0. Next, the process P0 starts executing.
2.4.2 Time slice mechanism for multitasking
On each context switch, a task is selected by the kernel’s scheduler from the ‘ready’ list and is put into the run state. It is then executed until another context switch occurs. This is normally signaled by a periodic interrupt from a timer. In such cases the task is simply switched out and put back on the ‘ready’ list, awaiting its next slot. Alternatively, the execution can be stopped by the task executing certain kernel commands. It could suspend itself, where it remains present in the system but no further execution occurs. It could become dormant, awaiting a start command from another task, or even simply waiting for a server task within the operating system to perform a special function for it. The time slice mechanism for multitasking operating system is shown in figure 1.7 below.
The diagram shown below gives a simplified state diagram for a typical real-time operating system which uses this time slice mechanism.
When the context switching occurs, the CPU register contents are stored in task A’s table. Then the next task( task B) is identified and task B’s register contents are loaded into the processor registers. Now the processor starts executing task B.This sequence of operations is illustrated in figure 1.8.
2.4.2 Steps in Context Switch
The following are the steps to perform context switch.
● First save context of the processor including program counter and other registers.
● Update the PCB of the running process with its new state and other associate information.
● Move PCB to appropriate queue – ready, blocked.
● Select another process for execution.
● Update PCB of the selected process.
● Restore CPU context from that of the selected process.
2.4.3 Example of Context Switch
Figure 1.9 shows the situation when context switch occurs in the system during I/O request.
Consider that there are three processes P1, P2 and P3. Assume that the process P3 is in running state. Suddenly when an I/O request is received, the scheduler loads the corresponding device driver, and then switches to process P1. When the time slice of P1 is exceeded, it schedules P2. While P2 is executing, an interrupt (corresponding to the previous I/O request) occurs. Hence, a context switch occurs and interrupt service routine for I/O request is executed. After finishing the interrupt service, context switch again occurs to resume the previous process P2.
3. Summary
In this module scheduling policies have been discussed along with their advantages and limitations. Context Switch is also discussed in detail here.
4. References
1. Galvin and silberschatz, “Operating System Concepts”, New York-Wiley-2012.
2. Steve heath, “Embedded Systems Design”, ELSEVIER (second edition) – 2005.
3. https://doc.micrium.com/display/osiidoc/Real-Time+Systems+Concepts#Real-TimeSystemsConcepts.