Algorithms for mutual exclusion
The problem of mutual exclusion - or of defining fundamental operations so that it is possible to resolve conflicts resulting from several concurrent processes sharing the resources of a computer system - has emerged over the last 20 years as a prime example of the difficulties associated with parallel or distributed programming. The implementation of a mutual exclusion mechanism, therefore, is a very real phenomenon that faces every designer of operating systems as well as applications programmers who use services provided by computer systems built around several processing units, or linked by a network.This book presents a remarkable survey of a vast field of concrete and highly complex research on algorithms for parallel or distributed control. Since parallelism makes it difficult to understand the behavior or to analyze the properties of algorithms that can solve these problems, all of the algorithms have been rewritten in a single language and restructured so that they are easy to understand and compare. The book systematically stresses the principles guiding their design, provides arguments to prove their validity and gives quantitative data allowing their assessment. Contents: Preface. The Nature of Control Problems in Parallel Processing. The Mutual Exclusion Problem in a Centralized Framework: Software Solutions. The Mutual Exclusion Problem in a Centralized Framework: Hardware Solutions. The Mutual Exclusion Problem in a Distributed Framework: Solutions Based on State Variables. The Mutual Exclusion Problem in a Distributed Framework: Solutions Based on Message Communication. Two Further Control Problems.M. Raynal is a professor, Department Informatique, IRISA-Université de Rennes 1, France. Algorithms for Mutual Exclusion is included in the Scientific Computation Series, edited by Dennis Gannon.
What people are saying - Write a review
We haven't found any reviews in the usual places.
after-you Agrawala's algorithm array assumption attempting to enter auth authi avoidance of deadlock avoids deadlock blocked bolt boolean Brinch Hansen buff buffer Carvalho and Roucairol Chapter clock Comm communication computer networks concurrent concurrent programming conflict-code cooperation critical section defined Dekker's algorithm delay Dijkstra Dijkstra's algorithm distributed algorithms Distributed Computing enddo endif enter its critical enter the critical execution fairness favourable reply finds flag finite guarantees mutual exclusion implemented in-cs initialized to false input/output instruction Lamport's language memory location mutex mutual exclusion problem mutual exclusion protocol neighbour left neighbour right number of messages number of processes passive Peterson's algorithm possible postlude primitives procedure process Pi processors programming PROOF proposed queue reachability reader repdeferred resource respect rflag Ricart and Agrawala's semaphore shared variable solution starvation synchronization timestamping mechanism token total ordering true update variable flag variable turn wait flag