Electrical computers and digital processing systems: memory – Address formation – Generating a particular pattern/sequence of addresses
Reexamination Certificate
2000-12-04
2004-07-13
Thai, Tuan V. (Department: 2188)
Electrical computers and digital processing systems: memory
Address formation
Generating a particular pattern/sequence of addresses
C711S200000, C707S793000
Reexamination Certificate
active
06763447
ABSTRACT:
BACKGROUND OF THE INVENTION
Brief Description of the Prior Art
A list is a collection of elements, such as data elements, that are accessed in an explicitly ordered sequential fashion. Common list access operations include the write operation, which receives and stores an element onto the list, and the read operation, which removes and forwards an element from the list. In an environment characterized by multiple thread asynchronous operations, previous list implementations have required that the list be locked for the duration of writing or reading an element. Such operations take an interval of time to complete, and often comprise more than one sequential step. Furthermore, with multiple asynchronous list operations taking place, a new operation may arrive while the sequential steps of a previous operation are in progress. Since the steps of different asynchronous operations are not synchronized, such lists have previously been locked from access by other operations during a list operation to prevent list damage or errors.
In contrast to the conventional approach of locking the list as described above, the lock-free list (LFL) described herein does not need to be locked during multiple asynchronous operations. The invention also may be applied to lock-free queues and lock-free linked lists.
The LFL is a collection of sublists, plus various control means and variables, that inherently protect the list during multiple asynchronous operations without requiring list locking, while provide the same functionality as a single list.
SUMMARY OF THE INVENTION
A lock-free list for use with a computer system is provided. The lock-free list comprises a list storage structure comprising at least two sublists, each of a plurality of list elements being sequentially assignable to one of the at least two sublists in such manner that a plurality of assigned list elements is partitionable across the at least two sublists. A plurality of indicators include; an indicator for indicating whether each of the at least two sublists is empty or in use is provided, an indicator for indicating whether a list element is being removed from each of the at least two sublists, an indicator for recording an order of the at least two sublists into which the plurality of assigned list elements are assigned, and an indicator for recording for each of the at least two sublists, a write address location and a read address location.
In order to operate successfully in the environment characterized by multiple thread asynchronous operations involving the list, the invention allows two or more list accesses, including read or write operations, to occur in a time interval of not less than T time units of each other, including the possibility of simultaneous list accesses, such that errors or list corruption do not occur as a result of the time proximity of the list accesses.
REFERENCES:
patent: 4445176 (1984-04-01), Burk et al.
patent: 4759014 (1988-07-01), Decker et al.
patent: 6078565 (2000-06-01), Ben-Michael et al.
Hersh Clifford L.
Sullivan Herbert W.
Todd Joan
ANTs Software, Inc.
Carr & Ferrell LLP
Thai Tuan V.
Todd Joan
LandOfFree
Lock-free list for use with computer system utilizing FIFO... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lock-free list for use with computer system utilizing FIFO..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock-free list for use with computer system utilizing FIFO... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3234652