Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-03-03
2001-12-11
Butler, Dennis M. (Department: 2182)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C713S502000
Reexamination Certificate
active
06330619
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for synchronization of processes in multiprocessor systems.
2. Description of the Related Art
A known problem in data processing systems having a plurality of processes is that of synchronization of the processes. Until now, common memory locations, called semaphores, have been used for this purpose. However, these have to be handled by specific machine instructions which cannot be interrupted or make the interruption identifiable. This problem has been dealt with in a large number of publications, for example in Section 2.2 “Interprocess Communication” of the book “Operating Systems: Design and Implementation” by Andrew S. Tanenbaum, Prentice-Hall 1987.
However, particularly in multiprocessor systems, there is a problem in providing a suitable, non-interruptable instruction. Furthermore, conventional programming languages do not support such instructions. Synchronization methods are thus also known in which the only requirement is for a loading instruction as other memory instruction to be carried out automatically. The methods known for this purpose are described, by way of example, in Section 3 of the book “Principles of Concurrent and Distributed Programming” by M. Ben-Ari, Prentice-Hall 1990, ISBN 0-13-711821-X.
The methods described there achieve the object that an item of equipment can only ever be used by one process at any given time, and all the other processes wait for their “turn in line”.
However, when multiprocessor systems are being started, a different type of problem arises in the phase synchronization of concurrently running processes. In this case, the starting processes on the individual processors can admittedly run simultaneously, but they comprise a plurality of phases which are intended to run as simultaneously as possible, although no starting process is intended to commence the next phase before all the other processes have completed the current phase.
SUMMARY OF THE INVENTION
An object of the invention is thus to provide an operating method which allows the phase of a number of concurrently running processes in microprocessor systems to be synchronized, as far as possible without any specific instruction being required.
The invention achieves this object and other objects by assigning each process, before it starts, its own memory word, which can be changed only by this process but can be read by all the other processes involved. This memory word is incremented twice for each synchronization step. Before each incrementation, a process waits until the memory word assigned to it is less than or equal to the values in the other memory words.
REFERENCES:
patent: 4325120 (1982-04-01), Colley et al.
patent: 5278975 (1994-01-01), Ishihata et al.
patent: 5448732 (1995-09-01), Matsumoto
patent: 5561784 (1996-10-01), Chen et al.
patent: 5958019 (1999-09-01), Hagersten et al.
Polychronopoulos, “Compiler Optimizations for Enhancing Parallelism and Their Impact on Architecture Design”, IEEE Transactions on Computers, vol. 37, No. 8, Aug. 1988, pp. 991-1004.
Ben-Ari, “Principles of Concurrent and Distributed Programming”, Technion—Israel Institute of Technology, Chapter 3, Prentice-Hall 1990.
Tanenbaum, “Operating Systems: Design and Implementation”, Chapter 2.2: “Interprocess Communications”, Prentice Hall 1987.
IBM Technical Disclosure Bulletin, “Barrier Synchronization Using Fetch-and-Add and Broadcast”, vol. 34, No. 8, Jan. 1992.
Arenstorf et al., “Comparing Barrier Algorithms”, Parallel Computing, vol. 12, No. 2, 1989, pp. 157-180.
Herlihy et al., “Lock-Free Garbage Collection for Multiprocessors”, IEEE Transactions on Parallel and Distributed Systems vol. 3, No. 3, 1992, pp. 304-311.
Butler Dennis M.
Schiff & Hardin & Waite
Siemens Nixdorf Informationssysteme Aktiengesellschaft
LandOfFree
Method of synchronization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of synchronization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of synchronization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598266