Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1997-02-28
2001-01-09
Cabeca, John W. (Department: 2752)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S147000, C711S151000, C711S167000
Reexamination Certificate
active
06173375
ABSTRACT:
TECHNICAL FIELD
This invention relates to a system for accessing resources shared by a plurality of processors. More particularly, the invention relates to a method for efficiently accessing a shared memory in a multiple processor computing environment.
BACKGROUND OF THE INVENTION
A data “structure” refers to related data stored in a computer memory location. To enhance operating efficiency, a data structure may be “shared” by a plurality of processors which require the same information to perform various tasks. Synchronizing access to a shared data structure is a great challenge in designing software for computers with multiple processors, and is especially important whenever multiple processors attempt to update information in a data structure. Indeed, without synchronization, the performance of a system including a shared data structure is severely degraded. This is because when one processor performs a data structure update, it is common for the entire data structure to be inaccessible (or “locked”) to other processors. In other words, the non-updating processors must wait until the data structure is “unlocked” before the information contained in the structure can be accessed or updated. Another significant problem affecting the performance of a multiprocessor environment with shared resources is the inability of multiple processors to simultaneously perform updates on discrete data structure events without blocking each other.
Therefore, there is a need for an efficient, non-blocking operation for updating shared data structures while maintaining FIFO behavior in a multiprocessor environment.
SUMMARY OF THE INVENTION
This need is addressed and a technological advance is made in the art by the present invention which provides simultaneous, nonblocking access to shared data structures in a multiprocessor environment. More particularly, the present invention uses information contained in a queue variable to enable multiple processors to perform concurrent updates of discrete events in a shared data structure.
In one preferred embodiment, lock-free multiple processors access a common data structure by identifying and reading queue variables. The queue variable contains information relating to a specific data event in a data structure. More particularly, the queue variable identifies the time at which the data event occurs, the addresses of linked data subevents which occur concurrently and an address pointer for identifying the next time-based data event in the data structure. A processor accesses an address location of a queue variable and stores it in a first register. The address location of the queue variable is read from the processor's first register and is used to access the contents of the queue variable. The contents of the queue variable are stored in a second register of the processor. The second register is accessed to determine the time at which the data event associated with the queue variable occurs, and whether there is a subsequent event in the data structure. Each queue variable in a data structure is traversed until the processor finds the proper point in the data structure to insert a new time-based data event. When the point of insertion is found, the processor updates the queue variable of the preceding time based data event to point to the new time-based data event. The queue variable associated with the new time-based data event is updated to point to the next time-based data event (that is, the time-based data event which occurs immediately after the newly inserted time-based data event) in the data structure. Advantageously, multiple processors may concurrently update time-based data events without blocking each other.
In another preferred embodiment of the present invention, multiple processors use a contention-free locking mechanism to update a shared data structure. Similar to the previous embodiment, a processor accesses and assigns the address location of a queue variable in its first register. The queue variable address is used to access the information associated with the queue variable so it may be stored in the processor's second register. The data stored in the second register is read by the processor to determine the time at which the data event associated with the queue variable occurs, and whether there is a subsequent data event in the data structure. Each queue variable in a data structure is traversed by the processor until the position in the data structure at which the processor wishes to insert a new time-based data event is reached. The processor uses a locking mechanism to lock the data structure up to the point of insertion of the new time-based data event. Just prior to insertion of the new time-based data event, the processor determines whether it is still proper to insert the new data event at this position in the data structure. This query accounts for the possibility of another processor updating the data structure before the new time-based data event has been inserted. After successful insertion of the new time-based data event, the locking mechanism is released. Advantageously, the entire data structure need not be locked and the FIFO behavior of data structures updates is maintained by determining whether a new time-based data event is still proper in view of actions taken by other processors.
REFERENCES:
patent: 4574350 (1986-03-01), Starr
patent: 4709326 (1987-11-01), Robinson
patent: 5226143 (1993-07-01), Baird et al.
patent: 5253344 (1993-10-01), Bostick et al.
patent: 5276847 (1994-01-01), Kohn
patent: 5341491 (1994-08-01), Ramanujan
patent: 5353414 (1994-10-01), Iida et al.
patent: 5430860 (1995-07-01), Capps, Jr. et al.
patent: 5502840 (1996-03-01), Barton
patent: 5524212 (1996-06-01), Somani et al.
patent: 5535365 (1996-07-01), Barriuso et al.
patent: 5553267 (1996-09-01), Herlihy
patent: 5566319 (1996-10-01), Lenz
patent: 5574922 (1996-11-01), James
patent: 5602998 (1997-02-01), Alferness et al.
patent: 5623671 (1997-04-01), Ando et al.
patent: 5729749 (1998-03-01), Ito
patent: 5832262 (1998-11-01), Johnson et al.
patent: 5841973 (1998-11-01), Kessler et al.
patent: 5860126 (1999-01-01), Mittal
patent: 5875485 (1999-02-01), Matsumoto
patent: 5922057 (1999-07-01), Holt
Bataille Pierre-Michel
Cabeca John W.
Lucent Technologies - Inc.
LandOfFree
Method for accessing a shared resource in a multiprocessor... 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 for accessing a shared resource in a multiprocessor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for accessing a shared resource in a multiprocessor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521016