Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-01-07
2001-01-30
Oberley, Alvin E. (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06182152
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to a method for synchronizing concurrent sequential processes by means of assigning intra-process update operations and assigning inter-process adapt operations. Each process can execute a sequence of steps, wherein each step may lead to amending internal state variables, and also to actions on the communication structures between the process in question and one or more other processes. Each such step or action should appear to another process as being atomic: any intermediate state between the initial and the final state of the step should be invisible to all other processes.
In particular, it should be possible to define steps that access local state variables and/or I/O channels, whilst maintaining atomicity of these steps. It should also be possible to achieve condition synchronization by putting constraints on the mutual order between executing steps of different processes, based on arbitrary conditions formulated in terms of the local state variables and I/O channel contents of a particular process.
SUMMARY OF THE INVENTION
Therefore, amongst other things it is an object of the present invention to maintain such atomicity and also to retain such mutual order when required. Now, according to one of its aspects, the invention is characterized by forming at least one subset having an associated plurality from the interactive processes, assigning to the subset an associated I/O channel and to each process of the subset a part of that channel, in that each inter-process operation comprises a first collection of access operations for exchanging information between an asscoiated process of the subset and its in-channel part, and a second collection of adapt operations for in-channel moving of information between the respective parts assigned to the processes of the subset, which adapt operations are each synchronous with a respective receiving process. The conceptual separation so presented can be maintained in a straightforward manner.
Relevant art on the use of low-level semaphoring has been described in U.S. Pat. No. 3,997,875 to the present assignee. This art preserves the above atomicity only for a very particular purpose. Another earlier solution for maintaining condition synchronization is by means of so-called condition variables, that must become true to bring a particular synchronizing operation into action. A known manner to combine the two above features is through communication structures such as mailboxes between concurrent processes, that have been disclosed in U.S. Pat. No. 4,769,771 assigned to the present assignee. Such mailbox encapsulates a set of variables that are shared by two of the processes. The present invention however provides adequate and generally applicable solutions for problems that could not be solved by the prior art.
Advantageously, any change effected by a first process to a channel state of its in-channel part causes an update operation signalling, to render a subsequent adapt operation pending. This renders the steps of a process atomic by definition. In particular, the signalling process maintains a table of all update operations signalled by it; the process that receives the adapt signalling, likewise maintains a table of all signallings so received. The purpose of an update operation is to make the local changes to an I/O channel visible to adapt operations, and signal the adapt operations to other processes connected to the relevant channel(s) such that they can adapt to the changed channel state for so effecting synchronization. The adapt-and-update mechanism is built into the I/O channels that connect the various processes. Thereby, these processes can be rendered invisible to a process designer.
Advantageously, a process terminates its action sequence atomicity by executing any of three synchronizing operators: commit, sync, or wait. Thus, the only way for a process to control the executing of adapt operations is through the synchronization operators discussed hereinafter. The inventor has found that these three operators allow an extremely elementary organization for implementing synchronization primitives, which express the conditions in terms of local variables only.
Advantageously, the method has a compound operator next that executes all pending update operations in a single atomic action, followed by executing all pending adapt operations of a current process. This scheme provides full condition synchronization for arbitrary conditions that are formulated in terms of local variables and communication structures, which represents a fine operational feature.
The invention also relates to a system for effecting synchronization according to the method recited supra. Further advantageous aspects of the invention are recited in dependent Claims.
REFERENCES:
patent: 4569015 (1986-02-01), Dolev et al.
patent: 5363505 (1994-11-01), Maslak et al.
patent: 5867656 (1999-02-01), Iwasaki et al.
patent: 5878225 (1999-03-01), Bilansky et al.
patent: 0201020A2 (1986-12-01), None
patent: WO9510805 (1995-04-01), None
Orfali et al., “Essential Client/Server Survival Guide,” pp. 255-260, 370-372, 1994.
Courtenay III St. John
Oberley Alvin E.
U.S. Philips Corporation
Wieghaus Brian J.
LandOfFree
Method and system for synchronizing concurrent sequential... 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 and system for synchronizing concurrent sequential..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for synchronizing concurrent sequential... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2481841