Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2000-02-24
2003-11-18
Homere, Jean R. (Department: 2177)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C707S793000, C707S793000, C711S168000
Reexamination Certificate
active
06651146
ABSTRACT:
TECHNICAL FIELD
The present invention relates, in general, to data processing systems and in particular to the management of lists within a multiprocessor environment.
BACKGROUND INFORMATION
Many data processing systems employ multiple processors for the central processing unit (CPU). These multiple processors may have both dedicated and shared memory resources where data is stored. Shared memory resources are resources where all of the multiple processors may store data which may be read or modified by any of the processors. Since shared memory may be modified by a particular processor and then read or used by another, protocols and methods have been developed to ensure that a particular processor can access the status of particular data.
A data element may have information that defines a block of memory that may contain data accessible by any one of a multiplicity of processors. The actual data within the block of system memory may define the data type (ex. characters, integers, floating point and etc.) and how the information is interpreted. To manage data flow in a computer system, blocks of memory may be managed with addresses defining the block of memory without regard to the actual resident data. A data element comprising a variable, definable location address in a system manager, the beginning address and size of a block of system memory, and pointer addresses (e.g., pointers and next pointers) used to link the data element with other data elements, may be used to manage information in a multiprocessor system. A linked set of data elements is referred to as a list. A list is a collection of data elements that are connected together by pointer addresses that determine how the list is accessed.
A processor may inquire as to the status of the data in a block of system memory referenced by a data element or, alternately, whether the block of system memory referenced by the data element is free to be used by the processor. In this context, a processor may require the use of a storage space referenced by the data element. Memory resource management is one process that may be managed using groups of data elements defining blocks of free memory for use by multiple processors.
A singly linked list is one where the pointer addresses cause the list to be navigated in one direction. A linear list is one where the data elements are linked in a chain of single data elements. The linkages of the linear list comprise the pointer addresses that are loaded by the list managing processes which may be referred to as a list manager.
A data element within a list may have a list address, a data set, and a next pointer. When a data element is assigned to a particular list, it is assigned a list address that defines where it resides in memory containing the list. A data element's list address is referred to as its pointer address or simply its pointer. A data element pointer address is how it is located. The data set of a data element may include a definition of what is being managed and possible information further defining the particular data set. A processor accessing a data element from a list would interpret the data set within the data element. An example of a data set within a data element could be the definition of a block of memory (e.g., the size and starting address of a block of memory). However, artisans of ordinary skill would recognize that the principles of the present invention may by used with any singly liked list independent of the contents of the data set. A data element's next pointer address is the list address linking it to, or pointing to, the next data element in a particular linkage of the list. Linkages of data elements may be realized by, defining a beginning data element, having the beginning data element point to a next data element and finally defining which data element is the last data element. A last data element in a list may be defined by having a data element's next pointer point to a NULL address. A NULL address is one that by convention is indefinite within the list and may signal the list management process that the element is the last data element in the list.
A list, in an embodiment of the present invention, has a header with pointers to the first data element and the last data element in a particular linkage of the list. If the header, or simply the head of a list, points to the pointer (list address) of the first data element in a linkage and the first data element has a next pointer that points to the next element in a linkage and the header also points to the last data element of a list whose next pointer points to a NULL or zero, the list may be considered complete. A NULL in a next pointer may be indicated by placing all zeros in the next pointer and means pointing to no address. A list may have zero or one or more data elements. A list with zero elements would have the first and last pointer in the list head equal to NULL.
The data elements in a list may be manipulated; new data elements may be added, data elements may be removed and data elements may possibly be modified in other ways. However, management of lists within a symmetric multiprocessor system (SMP) where each processor manages its own memory resources may present problems. Since access to a list in an SMP may be requested by any of the multiple processors there is a need to manage the list contention. Contention for a list usually is done with the use of locks that block access of one or more of the contending processors for the list. If one of the processors has access to the list, a mechanism to prevent concurrent access by another processor is typically employed.
If a multiprocessor system with shared memory resources uses a locking protocol to prevent access, the following sequence may be typical:
A processor X requests access to particular List A. Granting access would activate a locking subroutine that locks List A and notifies or indicates to other processors that the list is locked. When processor X releases or unlocks the List A, it does so with an unlocking routine and another processor Y can then access the released list. The locking and unlocking routines may each be ten or more machine instructions long.
In high speed multiprocessor systems there are many times when conflicts between processors for a particular list may occur, however, a protocol that uses locks for list management requires the locking and unlocking routines to be run any time the list is accessed and released whether or not contention occurs. Running the lock and unlock routines may slow many operations in such a multiprocessor system.
An alternate to locking is needed that can deal with contention in list management and does not consume important system time or cycles unless a contention actually occurs.
SUMMARY OF THE INVENTION
The present invention discloses a method of managing a list of data elements in a multiprocessor system without the use of locks. Locks are routines that may be invoked expressly to prevent contention problems when more than one processor accesses a list. An embodiment of the present invention manages lists in a “last in first out” (LIFO) or a “first in first out” (FIFO) protocol by using a set of operations which add data elements to the front or back of a list and remove data elements from the front of a list. Implementing these functions to manage a list also employs an operation that is atomic in the software sense. An atomic operation or instruction does several things immediately without the possibility of being partially done or having another instruction interspersed. An atomic operation of “compare and swap” (CAS) is used in the present invention implementing the functions used to manage a list
The present invention provides improved performance for multiprocessor computer systems by implementing singly linked lists where the atomic operation of CAS is used to implement functions used to manage the list without the use of locks.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the
Srinivas Mysore Sathyanarayana
Vanfleet James William
Whitworth David Blair
Frankeny Richard F.
Homere Jean R.
International Business Machines - Corporation
Tyson Thomas E.
Winstead Sechrest & Minick P.C.
LandOfFree
Method and apparatus for managing access contention to a... 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 managing access contention to a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for managing access contention to a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3114349