Data Dependency
As an example, data dependency cannot be captured by a precedence graph. In many realtime systems, jobs communicate via shared data. Oftentimes, the designer chooses not to synchronize producer and consumer jobs. Rather, each producer places the data generated by it in a shared address space to be used by the consumer at any time. In this case, the classical precedence graph should show that the producer and consumer are independent because they are not explicitly constrained to execute in turn.
As an example, in an avionics system, the navigation job updates the location of the airplane periodically. These data are placed in a shared space. Whenever the flight management job needs navigation data, it reads the most current data produced by the navigation job. There is no precedence constraint between the navigation job and the flight management job.
In a task graph, data dependencies among jobs are represented explicitly by datadependency edges among jobs. There is a data-dependency edge from a vertex Ji to vertex Jk in the task graph if the job Jk consumes data generated by Ji or the job Ji sends messages to Jk . A parameter of an edge from Ji to Jk is the volume of data from Ji to Jk . In Chapter 9, we will describe algorithms that partition an application system into modules and assign different modules to different processors for execution. Since the cost of communication between jobs on the same processor is usually much lower than that between jobs on different processors, one of the key factors we need to consider in choosing a partition is the amount of data exchanged among jobs. For this purpose, we will make use of the information provided by the data volume parameter.
The scheduler may not be able to schedule the navigation job and the flight management job independently. To ensure data integrity, some locking mechanism may be in place, and this mechanism allows only one job to access the shared data at a time. This leads to resource contention, which may also constrain the manner in which jobs execute. However, this constraint is imposed on jobs by scheduling and resource accesscontrol algorithms. It is not a precedence constraint because it is not an intrinsic constraint on the execution order of the jobs.
