Browse Prior Art Database

PARALLELISM IN MONITORS USING ALLOW CLAUSES

IP.com Disclosure Number: IPCOM000128006D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 8 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Edward A. Schneider: AUTHOR [+3]

Abstract

An extension to Hoare's monitors, which permits concurrent access to shared. data, is described. It is shown that scheduling policies prohibited by monitors, such as concurrent reading of a data structure, are now possible. Also, it is possible to give the programmer control over whether or not other processes should be allowed entry into the monitor during a nested call to another monitor. Several restrictions to the use of parallelism are shown to be necessary to preserve data integrity. Finally, an extension to the suggested implementation for sequential monitors is given. The implementation is "fair" in the sense that if the monitor becomes empty an infinite number of times, no process will wait forever trying to enter. Index of Terms: Parallel programming, monitors, synchronization, concurrent access, process, interference, deadlock,: fair scheduling.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PARALLELISM IN MONITORS USING ALLOW CLAUSES

by Edward A. Schneider

Technical Report #78-5 June, 1978 This work was supported in part by Iowa State University Research Grant 405-21-25.

ABSTRACT

An extension to Hoare's monitors, which permits concurrent access to shared. data, is described. It is shown that scheduling policies prohibited by monitors, such as concurrent reading of a data structure, are now possible. Also, it is possible to give the programmer control over whether or not other processes should be allowed entry into the monitor during a nested call to another monitor. Several restrictions to the use of parallelism are shown to be necessary to preserve data integrity. Finally, an extension to the suggested implementation for sequential monitors is given. The implementation is "fair" in the sense that if the monitor becomes empty an infinite number of times, no process will wait forever trying to enter. Index of Terms: Parallel programming, monitors, synchronization, concurrent access, process, interference, deadlock,: fair scheduling.

TABLE OF CONTENT'S Page Abstract ii

1. Introduction 1 2. Para11e1,Access 3

3. Allow Clause 7

4. Restrictions 9 5. Implementation 13 6. Conclusion 16 References

Introduction

In a system of parallel processes, it is desirable to insure the integrity of shared data. One useful tool is the data module based on the class concept in SIMULA67[1]. A module describes the structure of a data aggregate and also contains the implementation of the operations which may legally be used on the data. For example, a data module for a stack might describe the stack as an array and the index of the top element. Operations to push and pop the stack would also be provided. Data modules promote the integrity of the shared data by re-quiring that all accesses be done through the supplied operations. Thus, a process can push or pop a stack but it can't modify an arbi-trary element of the array used to implement the stack. The effect of this requirement is that accessing errors and modifications to the implementation are localized to the module. The module also. allows the processes which use it to treat it as an abstraction and to ignore the implementation details. Another requirement for data integrity is that only one process at a time can be allowed access to a data module. If several processes are allowed to simultaneously write, the result could be an arbitrary interleaving of information. Likewise, if a process is allowed to read some data while another is updating it; a mixture of old and new information could be received. If a process attempts to ,access the shared data while another process is using it, the access must be delayed until the data is no longer being used. It is also

Iowa State University Page 1 Dec 31, 1978

Page 2 of 8

PARALLELISM IN MONITORS USING ALLOW CLAUSES

frequently necessary to restrict the order in which data module ope...