Page 82 - DCAP608_REAL TIME SYSTEMS

Unit 7: Commonly used Algorithm to Real-time Scheduling

Below, we give the cycle conserving extensions of the RM and EDF schedulers Notes
Cycle_Conserving_RM:
assume fj is the frequency set by the static scaling algorithm
select_frequency:
set sm to the maximum cycles until the next deadline
use lowest frequency fi such that
(d1+ … +dn) / sm d” fi/fm
upon task_release(Ti):
set c_lefti to Ci
set cm to the maximum cycles until the next deadline
set sj to sm × fi/fm
allocate_cycles(sm)
select_frequency
upon task_completion(Ti):
set c_lefti to 0
set di to 0
select_frequency
during_task_execution(Ti):
decrement c_lefti and di
allocate_cycles(k):
for i=1 to n, Ti “ { T1, … Tn | P1 d” … d” Pn } // tasks sorted by period
if c_lefti < k
set di equal to c_lefti
set k equal to k-c_lefti
else
set di equal to k
set k equal to 0
Cycle_Conserving_EDF:
select_frequency:
use lowest frequency fi such that
(U1+ … +Un d” fi/f1)
upon task_release(Ti):
set Ui to Ci/Pi
select_frequency
upon task_completion(Ti):
set Ui to ci/Pi where ci equals the actual cycles used in the invocation
select_frequency
Prism Models

For this case study, we consider a processor with three operating frequencies, 1, 0.75 and
0.5, with corresponding voltages 5,4 and 3. The task set is of size three with the following
parameters:

Contd...

LOVELY PROFESSIONAL UNIVERSITY 77