Page 135 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes 8. One of the features of the ……………… time is that it is not a continuous function of
system parameters.
9. ……………… often require that the worst-case response times do not exceed a given
deadline.
10. One of the most intuitive policies consists of assigning ……………… to the tasks, so that at
each instant in time the resource is gr anted to the highest priority task requiring it at that
instant.



Case Study Simulation-based Multi-pass Scheduling

ulti-pass approach is one methodology for rule selection which is to combine a
rule-based expert system to select several scheduling rules in a real-time
Menvironment through the test which scheduling rule is the best. Wu and Wysk
developed a simulator control mechanism that evaluates the candidate dispatching rules
and uses various criteria to select the best control strategy for a given time period. Wu and
Wysk presented an MPS algorithm that includes a mechanism controller and a flexible
simulator. MPS algorithms are defined as scheduling algorithms that solve the scheduling
problem of selecting the best dispatching rule among a set of rules. Combinations of
dispatching rules over a system’s production cycle can produce higher throughput than a
single rule alone. Cho and Wysk used neural networks to recommend candidate rules for
MPS, used inductive learning and genetic algorithms to build the relationship between
shop conditions and rules; some modified techniques using neural networks and production
rules have also been used for identifying this relationship.

MPS frameworks consist of five components: (1) recommendation of rules for each problem
type, (2) generation of all rule combinations, (3) simulation, (4) evaluation and ranking of
rule combinations and (5) scheduling. Whenever the decision-making rules need to be
changed, a set of promising rules for resolving each problem type is recommended. A few
different types of scheduling problem may occur during the next scheduling period, so all
rule combinations must be generated, and each must be evaluated using simulation. The
best rule combination is chosen and conveyed to the scheduling component. One method
of MPS uses a nested partitioning (NP) method and an optimal computing budget allocation
(OCBA) method to reduce the computational load without the loss of throughput.
Questions:
1. Describe the various approaches of multi-pass scheduling.

2. Explain the different components of multi-pass scheduling frameworks.
Source: orsc.edu.cn/apiems/public/Abstracts/315.doc

13.3 Summary

 Algorithm will schedule in order to fulfil every deadline.
 A system of periodic tasks is simply periodic if the period of each task is an integer
multiple of the period of the other tasks.

 Depending on the assigned priority, a task can have longer or shorter response time,
which is the time, elapsed from request of the resource to the completion of the task.

130 LOVELY PROFESSIONAL UNIVERSITY