Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-15
2003-06-17
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06581063
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital data processing systems, and in particular to software data structures commonly known as linked lists.
BACKGROUND OF THE INVENTION
A modern computer system typically comprises a central processing unit (CPU) and supporting hardware necessary to store, retrieve and transfer information, such as communication buses and memory. It also includes hardware necessary to communicate with the outside world, such as input/output controllers or storage controllers, and devices attached thereto such as keyboards, monitors, tape drives, disk drives, communication lines coupled to a network, etc. The CPU is the heart of the system. It executes the instructions which comprise a computer program and directs the operation of the other system components.
From the standpoint of the computer's hardware, most systems operate in fundamentally the same manner. Processors are capable of performing a limited set of very simple operations, such as arithmetic, logical comparisons, and movement of data from one location to another. But each operation is performed very quickly. Programs which direct a computer to perform massive numbers of these simple operations give the illusion that the computer is doing something sophisticated.
The fact that computer systems are employed in a great variety of tasks is attributable largely to the abundance and variety of software which directs the execution of computer processors. Over the years, software has evolved and grown more sophisticated, just as hardware has. Although a particular software application may be very specialized, there are certain common techniques and structures which are repeatedly used by those skilled in the art. One way in which software may be improved, and with it the computer systems of which software is an essential part, is by making improvements to these commonly used software techniques and structures.
Software designers are well aware of the need to structure data, i.e., to arrange data in a logical manner so that it can be retrieved and manipulated without undue effort. The structure of data to be used by a software application is one of the first things to be determined in planning and developing the application. Although almost any custom data structure may be created, several common types of data structures are used over and over again by software designers. One of the most ubiquitous is the linked list, which may be singly linked or doubly linked.
A linked list is a collection of data elements, wherein each element in the collection contains a reference to the next element in the collection. A single element may contain only a single variable in addition to the reference, or may be a complex data structure containing data of many different types, such as text strings, numeric data, pointers, etc., or may be a dummy which contains nothing in addition to the reference. The reference is typically a pointer to the memory address of the next list element, but it may take the form of an array index or some other quantity, from which an address or other location of the next element can be derived. For simplicity, the reference within a linked list element is herein referred to as a “pointer”, whether it directly points to an address, or indirectly indexes something from which an address is obtained as noted above. The addresses or other storage references of linked list elements are not required to observe any ordering, and therefore it is possible to insert an element into or remove an element from a linked list without re-assigning all or a substantial number of elements in the list. It is merely necessary to alter the pointers of adjacent elements. A linked list may be singly linked, having forward pointers running in only one direction, or doubly linked, having both forward and backward pointers.
Care must be taken when updating a linked list in a multitasking environment. If multiple concurrently executing threads attempt to simultaneously modify the same linked list, or a single thread tries to modify the list while another is traversing it, results could be unpredictable and data could be corrupted. This problem is particularly acute where a single CPU supports hardware multithreading, or where multiple CPUs execute multiple threads concurrently, all accessing a common memory.
In the case of a singly-linked list, it may be possible in some environments to update a list through use of certain types of atomic operations. However, this approach is not feasible in all environments, and is not generally applicable to doubly linked lists, which require that pointers in two different list elements be updated. A more general solution typically employed is a system of locks. A task wishing to update a linked list typically obtains an exclusive lock on the list, meaning that other tasks are precluded from accessing the list until the update is complete. A task wishing to traverse a list without modifying it may obtain a shared lock, preventing other tasks from modifying the list but not necessarily preventing traversal.
The use of locks is simple and effective, but has the potential to affect performance. It may take some time to traverse a list, searching for a particular element. During this time, all other processes are precluded from modifying the list, and, depending on the type of lock, may be precluded from traversing the list as well. For small lists, and those which are used in isolated applications, this is not likely to be a problem. But there are likely to be some large and frequently accessed lists, e.g., a list used to maintain the state of tasks in the operating system. Exclusive locking of such lists may become a performance bottleneck. Such bottlenecks are more likely in a system employing multiple CPUs.
A need exists for a method of updating linked lists without the drawbacks of prior art methods, and particularly, for a method of updating linked lists including doubly linked lists in a multiprocessor environment which is less disruptive of tasks executing in other processors.
SUMMARY OF THE INVENTION
In accordance with the present invention, a linked list has an associated auxiliary data structure, containing external references to the linked list which are used by updating tasks. The auxiliary data structure is used to block subsets of the linked list from being altered by other tasks, thus allowing concurrent updates of discrete subsets.
In the preferred embodiment, linked list maintenance is accomplished using object-oriented (OO) programming techniques. Preferably, the list is a doubly-linked list. The auxiliary data structure is an object called SharedList, which comprises iterator objects, including inspector objects and mutator objects, blocker objects and view objects. Iterator objects are used by clients to access the linked list externally. An inspector object is a type of iterator object which traverses the list without changing it; a mutator object is a type of iterator object which can alter the list, and may also traverse the list. Both inspectors and mutators have associated view objects, which contain the pointers to the actual list elements. Mutators (but not inspectors) also have associated blocker objects, which block access to selected list elements. In operation, a mutator object blocks off a portion of the linked list by altering pointers so that they point to the blocker object, the blocker object containing additional pointers by-passing the blocked list portion. Other inspectors may thereafter traverse the list through the by-passed portion, although mutators traversing a list wait at the blocked portion.
By blocking only a relatively small portion of a large linked list, multiple tasks may concurrently access different list elements and perform separate list updates, thus improving performance, particularly where multiple processors are used. Specifically, in the preferred embodiment, by blocking at the level of individual list elements as opposed to the entire list, multiple mutators may simultaneously traverse and alter diff
Metjahic Safet
Nguyen Merilyn
Truelson Roy W.
LandOfFree
Method and apparatus for maintaining a linked list 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 apparatus for maintaining a linked list, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maintaining a linked list will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3128787