الفهرس 
IntroductionOnly 14 pages are availabe for public view
 |  | from | 16 |  |  |
| | | from | 16 | | |
Abstract
Real-time systems have become increasingly important in a growing number of application domains. In a real-time system, the task is the unit of work to be scheduled and executed, tasks must produce logically correct results by their deadlines In the real life, tasks usually don’t need to be executed in a sequential order Rather, certain precedence constraints must be handled between tasks along with timing-constraints to provide correct scheduling and consequently correct execution. In traditional precedence-constrained scheduling, a task is ready to execute when all its predecessors are completed. Such a task is called an AND task. In many applications, there are tasks that are ready to execute when one or some but not all of their predecessors are completed. Those tasks are called OR tasks. The resultant task system, containing both AND & OR tasks, is said to have AND/OR precedence constraints. Directed Acyclic Graphs DAGs are used to represent these systems.
This thesis studies systems that involve tasks having precedence constraints among them and mainly focuses on tasks with AND/OR precedence constraints. As real-time systems depend on timing-constraints, the thesis introduces a way to combine both precedence constraints and timing constraints into the same scheduling problem. Timing constraints here are on the form of a global End-to-End Deadline BED between a start node and an end node of the AND/OR graph representing the task system. A proposed Imprecise Computation Technique ICT is introduced to maximize the solution quality within the available time. ICT is motivated by the fact that one can trade off precision with timeliness; it prevents the total processing time of the system from stretching over the BED. To examine and evaluate this proposed imprecise scheduling solution, a Random Graph Generator algorithm R(iG is created to provide a wide range of random DAGs to be used in the simulation experiments.