Page 101 - DCAP608_REAL TIME SYSTEMS

Real Time Systems Sandeep Kumar, Lovely Professional University

Notes Unit 10: Working of Clock-driven Scheduling

CONTENTS
Objectives
Introduction

10.1 Improving the Average Response Time of Aperiodic Jobs
10.2 Scheduling Sporadic Jobs
10.3 Summary

10.4 Keywords
10.5 Review Questions
10.6 Further Readings

Objectives

After studying this unit, you will be able to:

 Introduce clock driven scheduling
 Describe Improving the Average Response Time of Aperiodic Jobs
 Explain Scheduling Sporadic Jobs

 Analyse maximum execution time of each sporadic job.
Introduction

In clock driven scheduling, a schedule of jobs is computed off-line. All scheduling decisions are
made a priori. In clock driven scheduling, schedule is static, finite (but generally is applied
cyclically). The run-time scheduler is driven by a hardware timer and simply follows this
schedule. There is minimal runtime overhead. Behaviour is completely predictable and some
variation can be accommodated using multiple tables which apply to different operational
modes of the system. In this unit, we will discuss the working of clock driven scheduling.

10.1 Improving the Average Response Time of Aperiodic Jobs

There is no advantage to complete a job before its hard deadline. So far the jobs are scheduled in
the background after all the jobs slices with hard deadlines scheduled in each frame are completed.
Strategy of delaying aperiodic jobs is not a good one if hard deadlines are competing early. The
sooner the aperiodic jobs complete, the more responsive the system is.
One way is to execute aperiodic jobs ahead of the periodic jobs whenever possible. This approach
is called slack stealing. For this scheme to work, every periodic job slice must be scheduled in a
frame that ends no later than its deadline.
Let the total amount of time allocated to all the slices scheduled in the frame k be x . The slack
k
time available in the frame is equal to f – x at the beginning of the frame. If the aperiodic job
k
queue is nonempty at this time, the cycle executive can let aperiodic jobs execute for this amount
of time without causing any job to miss its deadline. When an aperiodic job executes ahead of
slices of periodic tasks, it consumes the slack in the frame. After y units of slack time are used by
aperiodic jobs, the available slack is reduced to f-x – y. The cyclic executive can let aperiodic jobs
k

96 LOVELY PROFESSIONAL UNIVERSITY