What are precedence graphs?

Precedence graphs are directed acyclic graphsGraphs which does not have a cycle and each node have a direction to another node. (DAGs) that represent several processes' execution hierarchy. It consists of nodes and edges where the nodes represent the processes, and the edges represent the flow of execution.

Precedence graphs are used to ensure that different processes are able to run concurrently without any error or deadlockIt is a situation in which two computer programs sharing the same resource are effectively preventing each other from accessing the resource, resulting in both programs ceasing to function.. The following shows some processes involving certain actions and how their precedence graph is represented:

Explanation

To guarantee concurrency and prevent deadlock in these processes (as one process uses variables of the other process), the precedence relation should be created such that no process is disturbed. P3 can not be executed before variables a and b are assigned some values. Similarly, P4 also can not be processed before the variable c value has been calculated. However, since P1 and P2 are independent of each other, they can be executed concurrently, as shown below:

In the operating system, precedence graphs are used to prevent control flow hijackingIt allows an attacker to subvert a value that is loaded into the program counter of a running program, typically redirecting execution to his own injected code. by analyzing the running code, creating a precedence graph, checking whether the code is following the precedence graph, and not executing some malicious code.