Non-preemptive scheduling

Non preemptive scheduling consists in executing the jobs until completion, without allowing its suspension for the execution of higher priority jobs.

Main characteristics/ advantages:

• Very simple to implement, as it is not necessary to save the intermediate job’s state.

• Stack size much lower (equal to the stack size of the task with higher requirements + interrupt service routines).

• No need for any synchronization protocol to access shared resources, since tasks execute inherently with mutual exclusion.

Main characteristics/ disadvantages:

• Penalizes the system schedulability, mainly when there are tasks with long execution times.

• This penalization may be excessive when, simultaneously, the system has tasks with high activation rates (short periods).

• The penalization can be seen as a blocking on the access of a shared resource, in the case the CPU.

Sometimes the use of offsets may turn a system schedulable.

However, finding these offset is usually is very complex ...

Computation of the Rwci with fixed priorities:

• The feasibility analysis must be adapted and becomes more complex.

• In non-preemptive scheduling the longest response time does not necessarily coincide with the first job after the critical instant.

  • Self-pushing phenomenon: high priority jobs activated during the first instance of τi are pushed ahead to the following jobs of τi, which may experience higher interference.

Therefore the response time analysis must be performed until the processor finishes executing all tasks with priority greater than or equal to Pi : Level-i Active Period (Li)

Li is the smallest value for which Li(s) = Li(s − 1)

For a generic task τi we must compute the response time for all jobs τi, k, where k=1, ...Ki and

The starting times of the relevant jobs can be computed as follows:

Since once started a job cannot be preempted, the finishing time is

And finally the worst-case response time is

Exercise

Given the task set below, compute the worst-case response time, without preemption, of each tasks.

Assume RM priority assignment.

Is the task set schedulable without preemption? And with preemption?