Data flow and control dependencies between the jobs can constrain the order in which the jobs can be executed such job or task have two main types of dependencies: Mutual exclusion and Precedence constraints. When Job Ji can start only after another job Jk finishes in a task model then such constraint is called precedence constraint. If jobs can execute in any order, they are said to be independent. Similarly when a tasks or job executed without any dependency on other tasks are called independent task or job. For Example: Consider an information server some of the precedence constraint are.

  • Before a query is processed and the requested information retrieved, its authorization to access the information must first be checked.
  • The retrieval job cannot begin execution before the authentication job completes.
  • The communication job that forwards the information to the requester cannot begin until the retrieval job completes.

Similarly, in a radar surveillance system the signal processing task is the producer or track records which the tracker task is the consumer then

  • Each tracker job processes the track records produced by a signal processing job.
  • The tracker job is precedence constrained.

Precedence Graph and Task graph:

Precedence relation on a set of jobs is a relation that determines precedence constrains among individual jobs. It is denoted by a partial order relation (<). A job Ji is a predecessor of another job jk (and jk is a successor of ji) if jk cannot begin execution until the execution of ji completes. This is represented as ji < jk then

  • Ji is an immediate predecessor of jk (and jk is is an immediate successor of ji) if ji < jk and there is no other job jj such that ji < jj < jk
  • Two jobs ji and jk are independent when neither ji < jk nor jk < ji
  • A job with predecessors is ready for execution when the time is at or after its release time and all of its predecessors are

A precedence graph is a directed graph which represents the precedence constraints among a set of jobs J where each vertex represents a job in J. There is a directed edge from vertex Ji to vertex Jk when the job Ji is an immediate predecessor of job Jk. For example, A system contains nine non-preemptable jobs named Ji, for i = 1, 2, ..., 9. J1 is the immediate predecessor of J9, and J4 is the immediate predecessor of J5, J6, J7, and J8. There are no other precedence constraints. For all the jobs, Ji has a higher priority than Jk if i < k. then the precedence graph can be constructed as,

second row represent jobs in a periodic task with phase 2, period 3, and relative deadline 3. The jobs in it are dependent. The first job is the immediate predecessor of the second job, the second job is the immediate predecessor of the third job, etc. The precedence graph of the jobs in this task is a chain. A subgraph’s being a chain indicates that for every pair of jobs Ji and

J k in the subgraph, either Ji < Jk or Jk < Ji . Hence the jobs must be executed in serial order.