Date of Publication

4-30-1993

Document Type

Master's Thesis

Degree Name

Master of Science in Computer Science

Subject Categories

Databases and Information Systems | Graphics and Human Computer Interfaces | Numerical Analysis and Scientific Computing | Programming Languages and Compilers

College

College of Computer Studies

Department/Unit

Computer Science

Thesis Adviser

Manuel Lopez

Defense Panel Chair

Mitch Andaya

Defense Panel Member

Kelsey Hartigan Go
Peter Fernandez

Abstract/Summary

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.

Abstract Format

html

Language

English

Format

Print

Accession Number

TG02161

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

58 leaves, 28 cm.

Keywords

Algorithms; Electronic data processing--Distributed processing; Programming (Mathematics); Simulation methods; Algebra

Upload Full Text

wf_yes

Download

Share

COinS