Cycle saving technique for managing linked lists

Details Cycle saving technique for managing linked lists Cycle saving technique for managing linked lists

2000-01-07

2003-06-24

Gaffin, Jeffrey (Department: 2182)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C370S230000, C370S236000, C370S390000

Reexamination Certificate

active

06584518

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to a method and system for managing memory devices and in particular to a method and system for providing enhanced queueing efficiency within a data storage device. More particularly, the present invention relates to an improved memory linking method and system whereby storage block addresses and data objects are strategically associated, such that the number of system cycles required to enqueue or dequeue to or from a data storage system is reduced.
2. Description of the Related Art
A “linked list” is known in both the hardware memory and software arts as a chain of items which each point to the next item in the linked list in a sequential manner. Such a list of elements or nodes comprise an ordered data structure which is held together by the use of pointers. Within this context, a “pointer” is a variable that comprises the memory location (memory address) of the data block to which it points in sequence. A singly linked list is comprised of data blocks which include a single pointer to the next sequential block. Each of the data blocks in a double linked list includes two pointers—one pointing to the following block and the other pointing to the preceding block. In a circular-linked list, the last data block points to the first data block.
Referring to
FIG. 1
, there is depicted a conventional memory management system
100
. As seen in
FIG. 1
, memory management system
100
includes a linked list
105
having serially linked storage blocks
108
,
110
, and
112
. In this three-block linked list, storage block
108
is the first storage block (hereinafter referred to as the “head”) within the series, and storage block
112
is the last storage block (hereinafter referred to as the “tail”).
Memory management system
100
further includes a head register
102
, a tail register
104
, and a count register
106
which function as boundary and parametric guides for linked list
105
. Head register
102
tracks head block
108
from which data objects within linked list
105
are dequeued. Count register
106
maintains a count of the number of storage blocks within linked list
105
. This count is updated for each enqueueing or dequeueing operation performed by memory management system
100
. Tail register
104
tracks tail block
112
prior to a conventional data enqueue operation such as that described as follows.
A typical enqueueing process is initiated by a request to memory management system
100
to add a data object
126
to linked list
105
. In response to the data enqueue request, the address of tail block
112
is read from tail register
104
. An address register (not depicted) for free pool
130
is then accessed to obtain the address of an available storage block
114
within free pool
130
. The address of storage block
114
will become a new tail pointer
121
which is written into pointer field
120
of old tail block
112
. A second write operation is then required to write data object
126
into the data field of new tail block
114
. A data enqueueing operation within memory management system
100
thus requires accessing and writing to two physically separate memory locations which is costly in terms of processing overhead.
It would therefore be desirable to provide a method and system for reducing the number of processing cycles required to queue data to or from a linked list data storage device.
SUMMARY OF THE INVENTION
A method and system are disclosed for queueing data within a data storage device including a set of storage blocks each having an address, a pointer field, and a data field. This set of storage blocks comprises a linked list of associated storage blocks and also a free pool of available storage blocks. The storage device further includes a tail register for tracking an empty tail block from which a data object is enqueued into the linked list. A request to enqueue a data object into the linked list is received within the data storage system. In response to the data enqueue request, an available storage block from the free pool is selected and associated with the tail register. A single write operation is then required to write the data object into the data field of a current tail block and to write the address of the selected storage block into the pointer field of the current tail block, such that the selected storage block becomes a new tail block to which the tail register points.


REFERENCES:
patent: 5530897 (1996-06-01), Meritt
patent: 5634015 (1997-05-01), Chang et al.
patent: 5781549 (1998-07-01), Dai
patent: 5872769 (1999-02-01), Caldara et al.
patent: 6349097 (2002-02-01), Smith
patent: 6445680 (2002-09-01), Moyal

Affiliated with

Also associated with

Rating

Cycle saving technique for managing linked lists does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cycle saving technique for managing linked lists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cycle saving technique for managing linked lists will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3123004