LIMITED PREEMPTIVE SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 265

Note that the algorithm is optimal in the sense that if a preemption threshold assign-
ment exists that can make the system schedulable, the algorithm will always find an
assignment that ensures schedulability.

Given a task set that is feasible under preemptive scheduling, another interesting prob-
lem is to determine the thresholds that limit preemption as much as possible, without
jeopardizing the schedulability of the task set. The algorithm shown in Figure 8.10,
proposed by Saksena and Wang [SW00], tries to increase the threshold of each task
up to the level after which the schedule would become infeasible. The algorithm con-
siders one task at the time, starting from the highest priority task.

Algorithm: Assign Maximum Preemption Thresholds
Input: A task set T with { C i ,T i ,D i ,P i } , ∀ τ i ∈T

Output: Thresholds θ i , τ i ∈T

// Assumes that the task set is preemptively feasible

∀

begin

(1)

for ( i := 1 to n ) do

(2)

θ i = P i ;

(3)

k = i ; // priority level k (4)

schedulable := TRUE;

(5)

while ((schedulable := TRUE) and ( k> 1)) do

(6)

k = k − 1; // go to the higher priority level

(7)

θ i = P k ; // set threshold at that level

(8)

Compute R k by Equation (8.15);

(9)

if ( R k >D k ) then

// system not schedulable

(10)

schedulable := FALSE;

(11)

θ i = P k +1 ; // assign the previous priority level

(12)

end (13)

end

(14)

end

(15)

end

(16)

Figure 8.10 Algorithm for assigning the maximum preemption thresholds.