Page 96 - DCAP608_REAL TIME SYSTEMS

Unit 9: Concept of Clock-driven Scheduling

A constraint enforced by this structure is that scheduling decisions are made periodically, rather Notes
than at arbitrary times. The scheduling decision times partition the timeline into intervals
called frames. Each frame has length f which is the frame size. Scheduling decisions are made
only at the beginning of every frame so there is no preemption in a frame. Phase is always a
multiple of frame size. Scheduler also carries out monitoring and enforcement actions at the
beginning of each frame to check whether every job scheduled in the frame has indeed been
released and ready for execution.
Frame Size constraints:
 The frames should be sufficiently longs so that every job can start and complete its execution
within a frame (no preemption).
 Possible If we make the frame size f larger than the execution time of every task Ti
(Constraint 1).

 The frame size would be chosen so that it divides H. This condition is met if f divides the
period pi of at least one task T .
i
 (p /f ) – p /f = 0 for at least one i (Constraint 2). Thus there are an integer number of
i i
frames in each hyperperiod.
 F is the number of frames in a hyperperiod.
 A hyperperiod that begins at the beginning of (kF+1)st frame, for any k =0,1… is called a
major cycle.
 To make it possible for the scheduler to determine whether every job completes by its
deadline, we want the frame size to be sufficiently small so that between the release time
and deadline of every job, there is at least one frame (Constraint 3).

 The figure below illustrates the suitable range of f for a task.
 When f is in this range, there is at least one frame between the release time and deadline
of every job in the task.

 Now, the figure given below constraints the frame size to be no less than 2. As hyper
period is 20; 2, 4, 5, 10 are possible frame sized.
 However only 2 satisfies (p /f ) – p /f = 0.
i i
 If we have (15, 1, 14), (20, 2, 26), and (22, 3) we must have only 3, 4, 5.
Figure 9.3: General Structure Cyclic Schedules

Source: ansari.szabist-isb.edu.pk/RTS/RTS0508.ppt

Job Slices

At times the constraints cannot be met, for example, (4,1), (5,2,7), (20,5). For constraint 1 we must
have f>= 5 but for constraint 3 we must have f<=4. Now we are forced to partition each job in a
task that has a large execution time into slices (sub jobs) with smaller execution times (IN
message transmission, divide message into several segments, when job is computational divide

LOVELY PROFESSIONAL UNIVERSITY 91