Page 126 - DCAP608_REAL TIME SYSTEMS

Unit 12: Priority-driven Scheduling of Periodic Tasks

Notes
Example: (2, 0.9) and (5, 2.3, 3)

Figure 12.2: Example of Maximum Schedulable Utilization

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

Theorem: A system T of independent, preemptible tasks can be feasibly scheduled on one
processor if its density is equal to or less than 1. The condition in this theorem is not necessary
for a system to be feasible, a system can be feasible when its density is greater than 1, e.g.
(2, 0.6, 1) and (5, 2.3).

Self Assessment

Fill in the blanks:

11. A scheduling algorithm can feasibly schedule any set of ……………… on a processor if the
total utilization of the tasks is equal to or less than the schedulable utilization of that
algorithm.

12. If the scheduler were to follow the ……………… strictly, it would have to monitor the
slacks of all ready jobs and compare them with the slack of the execution job.



Case Study Rugby Union Scheduling

n this study we examine the problem of producing sports leagues that are round-robin
in structure. Such structures occur when we have n teams (or competitors) in a league,
Iand each team is required to play all other teams exactly m times within a fixed
number of rounds. Examples include the Six Nations Rugby Championship (where n = 6
and m = 1), the England and Wales County Cricket Championship (n = 9, m = 2), and most
European and South American national soccer leagues. In practice the most common
league structures are single and double round-robins, where m = 1 and 2 respectively.
It has been known for many years that valid round-robin schedules using the minimal m
(n¡1) rounds can be constructed for any positive integer n. It is also known that the number
of distinct round-robin schedules grows exponentially with n, since this gore is
monotonically related to the number of non-isomorphic one-factorizations of a complete
graph with n vertices (which is also known to increase exponentially with n). Such a
growth rate implies that, for non-trivial problems, examining all possible schedules in
order to identify the one that best is the needs of the user will not always be possible in
reasonable time (in practice, non-trivial values for n would appear to be anything above
10 when m = 1.) Recent work on round-robin scheduling problems has tended to focus on
the use of metaheuristic-based approaches, which have shown to be effective for exploring
the large search spaces associated with such problems [1, 3, 10, and 12]. The strategy used
in such methods is to apply a two-stage scheme, whereby a valid round-robin schedule is

Contd...

LOVELY PROFESSIONAL UNIVERSITY 121