Following are the criteria for task schedulability:

CPU Utilization: The scheduling algorithm must make sure that the CPU utilization is high.

Throughput: This gives an indication of the number of processes executed per unit time. The throughput for a good scheduler must always be higher.

Turnaround time: It is the amount of time taken by a process for completing its execution; it includes the time spent by the process waiting for main memory, time spent in the ready queue, time spent on completing I/O operation and time spent in execution. Good scheduling algorithm must have minimal turnaround time.

Waiting time: It is the amount of time spent by a process in the ready queue waiting to get the CPU time for execution. It should be as minimal as possible.

Response time: It is the time elapsed between the submission of a process and the first response. Good scheduling algorithms have a small response time.

Following are the different scheduling mechanism used in a RTOS:

Non- preemptive scheduling:

In this type of scheduling, task is allowed to run until it terminates or enter the wait state waiting for an I/O or system resource. Various types of non-preemptive scheduling are as follows:

a. First come first served (FCFS)/ FIFO scheduling:

As the name indicates this algorithm allocates CPU time to tasks based on the order in which they enter the ready queue. The first enter process is serviced first. The major drawback of FCFS is that it favors monopoly of a process. A process which does not contain any I/O operation executes till its completion. I/O bound processes have to wait until the completion of CPU bound processes.

b. Last-come first served (LCFS)/LIFO scheduling:

Processes are allocated CPU based on the order in which they enter the CPU. The last entered process is serviced first. LCFS is also not optimal as it also possesses the same drawback as that of FCFS algorithm.

c. Shortest Job First (SJF) Scheduling:

The ready queue is sorted by the CPU every time a process relinquishes (i.e. it terminates or enters wait state for an I/O resource) to pick a process which has least estimated run time. The major drawback is that processes with higher execution time may not get a chance to execute if more and more processes with least execution time enter the ready queue. This is known as starvation.

d. Priority based scheduling:

The priority is assigned to each task based on criteria’s like the shortest job first or the priority can be indicated at time of creation of the task using a number ranging from 0. Priority based non-preemptive scheduling also suffers from starvation which can be tackled using priority based preemptive scheduling.

Preemptive scheduling: In this kind of scheduling the scheduler can preempt (stop temporarily) the current executing task and select another task from the ready queue. When to preempt the task and which task is to be selected from the ready queue is purely based on the scheduling algorithm.

Following are various preemptive scheduling algorithms:

a. Preemptive SJF/ Shortest remaining time scheduling (SRT):

The ready queue is sorted every time a new process enters the ready queue to check for the shortest execution time. The executing task is preempted in case of a new task with shortest time.

b. Round robin scheduling:

In round robin scheduling each process inb the ready queue is executed for a pre-defined time and when the pre-defined time elapses the next process in the ready queue is taken up for execution. Thus round robin scheduling is similar to FCFS however a time slice is added for preemption. Time slice may range from few microseconds to milliseconds.

c. Priority based scheduling:

Priority based preemptive scheduling is similar non preemptive priority based scheduling except for the fact that the executing task is preempted if a high priority task enters the ready queue. Even here the tasks suffer from starvation but this problem can be overcome by gradually raising the priority of processes waiting in the queue. This technique is called ageing.