A task is said to be schedulable if the total execution time of all the tasks is less than the farthest deadline.

Criteria for selecting scheduling algorithm:

1. CPU Utilisation: Scheduling algorithm should always utilise CPU efficiently.

2. Throughput: It indicates the no. of tasks executed per unit time.

3. Turn around time: Amount of time taken by task for its completion. It include time required to perform various activities such as time spent by task to access memory, time spent in ready queue, time spent for completing I/O operations and time spent in execution.

4. Waiting time: Amount of time spent by task in the 'ready' queue to get CPU time for execution.

5. Response time: time elapsed between creation of a task and the first response.

Various Scheduling Algorithms/Mechanisms/Policies:

1. Real time priority scheduling

• Real time static priority scheduling

• Real time dynamic priority scheduling

Real time static priority scheduling:

• priorities are pre-determined and fixed at design time.

• priorities are not changed while on the run.

• No processor overhead.

• May miss deadlines.

• More context switching

Real time dynamic priority scheduling:

$\to$ EDF

$\to$ LSF

$\to$ RMS/STF/SJF

• Here tasks are given priority in run time.

• No fixed priority.

• Slight processor overhead.

2. Non-preemptive scheduling

In this case, even if a higher priority task enters into the ready state, the task already in running is not preempted or suspended until it completes the execution.

$\to$ FIFO/FCFS(First Come First Serve scheduling)

$\to$ LIFO/LCFS

3. Preemptive scheduling

In this case, the highest priority task (say T2) when enters the ready state is immediately shifted to running state where task T1 with some priority already running. If priority of T2 is greater than T1, then the Task T2 will preempt(suspend) the Task T1 and enter into the running state.

4. Shortest task First/Shortest Job First/rate monotonic scheduling

• This is dynamic scheduling algorithm.

• It schedules the task whose remaining time for execution is least.

(i) Slight processor overhead.

(ii) May miss deadlines.

(iii) Moderate context switching.

(iv) Less starvation of tasks.

Consider the following example:

Total Execution time = 3 + 2 + 3 +4 = 12 - farthest deadline

$\therefore$ tasks are schedulable.

By STF/SJF/RMS

5. Real time static priority

6. EDF - Earliest deadline first

• Dynamic algorithm in which the task priority changes depending upon the deadline.

(i) Slight processor overhead

(ii) Highest possibility of meeting deadlines

(iii) Moderate context switching

(iv) Starvation of tasks possible

7. LSF - Least time first

• Slack time = Deadline - current position/time - remaining time

• Dynamic

• more processor overhead

• less probability of missed deadlines

• moderate context switching

• starvation of tasks possible