Detection and resolution of deadlocks in concurrent processes using process algebra

• Main Author: Chua, Caslon L.
• Format: text
• Language: English
• Published: Animo Repository 1993
• Subjects: Algorithms; Electronic data processing > Distributed processing; Programming (Mathematics); Simulation methods; Algebra; Databases and Information Systems; Graphics and Human Computer Interfaces; Numerical Analysis and Scientific Computing; Programming Languages and Compilers
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/1501; https://animorepository.dlsu.edu.ph/cgi/viewcontent.cgi?article=8339&context=etd_masteral
• Institution: De La Salle University

The proponent extends Process Algebra (PA) in terms of its components and how it is constructed. This algebra allows an expression to contain a set of finite operands known as atomic actions and a finite set of operators which individually denote either a sequential or an alternate composition. Both of these operators are considered primitive operators. In order to evaluate these operators, axioms are formulated to include the resolution of parallel and left-merge operators that are necessary to represent processes in a distributed environment. An algorithm, which uses PA as the mathematical model, to detect and resolve a deadlock for concurrent processes in a distributed system environment is also presented. The key idea of the algorithm is to have a controller in each site maintain a table of all the processes in a particular site availing themselves of a specific resource. Since a process has to submit to the site controller the duration of the process as well as an interval indicating its earliest and latest start times, the site controller can eventually construct a picture, called a process graph, of its schedule. Such a picture allows the controller to determine if a deadlock exists among the scheduled processes. The main problem involves a scheme to detect whether a deadlock, if any, exists. Moreover, if a deadlock exists, the algorithm determines which among the processes should be aborted. The selection of such a process is dictated by the objective of affecting as small a number of processes as possible.