Scheduling Algorithms

Scheduling is the process of allocating the CPU to the process.

1) FCFS(First Come First Served):

        It is the Simplest CPU Scheduling algorithm.
        The process that request the CPU first will get the CPU Access.
        Averaging waiting time is long.
        It is Non Preemptive.

2) Shortest Job First(SJF):
        If two processes have the same length next CPU burst, FCFS scheduling is used.
        SJF is optimal – gives minimum average waiting time for a given set of processes.

3) Round Robin Scheduling: The Round Robin is designed for time sharing systems.
         Each process gets a small unit of CPU time (time quantum or time slice ), usually 10-100 milliseconds.       

        After this time has elapsed,the process is preempted and added to the end of the ready queue.

        That is, after the time slice is expired an interrupt will occur and a context switch.

4) Priority Scheduling: Priority Number is associated with each process.
        The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority).
        Equal priority processes are scheduled in FCFS.

Both FCFS and SJF are not useful for timesharing environments, because they are non preemptive.
SJF gives less average waiting time than FCFS.

Scheduling Algorithms in RTOS

  Based on scheduling algorithms, scheduler decides the task execution. 

There are two types

·         Preemptive priority based scheduling:

o   Most real time kernels use this scheduling by default.

o   Real-time kernels generally support 256 priority levels, in which 0 is the highest and 255 thelowest. Some kernels appoint the priorities in reverse order,

o   Tasks are assigned Priority levels when they are created, task priority can be changed dynamically using kernel provided calls.

o     With a preemptive priority-based scheduler, each task has a priority, and the highest-priority task runs first.

o   Task 1 ispreempted by higher-priority task 2, which is then preempted by task 3. When task 3 completes,task 2 resumes; likewise, when task 2 completes, task 1 resumes.

·         Round Robin scheduling:

o   Round-robin scheduling provides each task an equal share of the CPU execution time.

o   Which uses time slicing toachieve equal allocation of the CPU for tasks of the same priority.

o     A run-time counter tracks the time slice for each task, incrementing onevery clock tick. When one task’s time slice completes, the counter is cleared, and the task isplaced at the end of the cycle.

If a task in a round-robin cycle is preempted by a higher-priority task, its run-time count is savedand then restored when the interrupted task is again eligible for execution. This idea is illustratedin Figure, in which task 1 is preempted by a higher-priority task 4 but resumes where it left offwhen task 4 completes.

RTOS Features

1)    Multithreading and preemptability:The schedulershould be able to preempt any task in the system and allocate the resource to the task that needs it most even at peakload.

2)    Thread Priority: All the tasks are assigned priority level to facilitate preemption. The highest priority task that is ready to run will be the task that will be running.

3)    Inter Task communication and synchronization:For multiple tasks to communicate in a timely manner and to ensure data integrity among each other, reliable and

sufficient inter-task communication and synchronization mechanisms are required.

4)    Priority inheritance: Should priority inversion this is required       

5)    Short Latencies:

·         Task switching Latency: The time needed to save the context of currently executing task and switching to another task.

·         Interrupt Latency:The time elapsed between execution of the last instruction of the interrupted task and the firstinstruction in the interrupt handler.

·         Interrupt dispatch Latency:The time from the last instruction in the interrupt handler to the next task scheduled torun.

Different Types of RTOS

Hard Real time:Hard real time systems are the ones in which critical deadlines are met strictly. Missing a deadline means failure of the system.

Ex: Mission critical systems like missile launching systems.

Firm Real time:If missing its deadline makes the result useless, but missing does

not cause serious damage

Soft Real Time:In Soft real time systems, occasional missing of deadlines (small delays) are acceptable and not considered as failure. Rather it is considered as performances degrade.

Ex: Cell phones

RTOS vs General OS

RTOS is an operating system that supports real time applications by providing logically correct results within the deadline required. Basic structure is similar to general OS but, in addition, it provides mechanisms to allow real time scheduling of tasks.

Though real time operating systems may or may not increase the speed of execution, they  can provide much more precise and predictable timing characteristics than general OS.

General OS:Operating System (OS) is a system program that provides an interface between hardware and application programs. OS is commonly equipped with features like: Multitasking, Synchronization, Interrupt and Event Handling, Input/ Output,\Inter-task Communication, Timers and Clocks and Memory Management to fulfill its primary role of managing the hardware resources to meet the demands of application programs.

RTOS: Generally used for embedded systems

OS: Desktop PCs.etc.

Determinism: The main difference between general os and real time OS is the “Deterministic” timing behavior in the RTOS.OS consume only known and expected amounts of time.

General OS: Non deterministic.

Scheduling in RTOS is Time based

Scheduling in OS is Process based.

RTOS uses priority based preemptive scheduling, which allows high priority threads to meet their deadlines consistently.

In RTOS: All kernel operations are preemptible.