Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
1998-06-30
2002-02-12
Lee, Thomas (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S054000, C710S056000
Reexamination Certificate
active
06347348
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital systems, such as digital computer systems, digital communication systems and the like, more particularly to arrangements for managing buffers which are used to store data. The buffers may be used, for example, to temporarily store data received from one element of the system prior to being transferred to another element of the system. The invention provides an system and method for efficiently allocating buffers for use in storing data from a pool of empty buffers using one or more FIFOs which contain pointers to empty buffers.
BACKGROUND OF THE INVENTION
In a number of types of digital systems, such as digital computer systems, digital communication systems and the like, data provided by one element of a system, operating as a source is temporarily stored in buffers before being transferred to another element, operating as a destination which is to utilize the data in some manner. For example, in a digital computer system, a source may comprise a process in which data to be transferred to a storage device local to the digital computer system or to another digital computer system, is generated and organized for transmission, and a destination may comprise a process in which the data from the source retrieves the data and actually performs the transfer. In such an illustrative system, the source will provide the data to destination through a buffering arrangement, in which the source stores the data that it generates in a buffer store intermediate the source and destination, from which the destination will retrieve the data for transmission. Storing the data to be transferred in such a buffering arrangement allows the source and destination to operate at different instantaneous rates, irrespective of the rate at which the other is operating. In addition, if multiple sources are providing data for transfer through a single destination, they can all use the same buffering arrangement to provide data to the destination, and, similarly, if a single source is providing data for transfer through multiple destinations, it can use a single buffering arrangement to provide data to all of the destinations.
Conventionally in buffering arrangements, a number of buffers are organized in one or more linked lists. In a linked list, the data associated with, for example, a source or a destination, is stored in a buffer or a series of buffers, with each buffers in a series including pointers which point to the next buffer in the series. In addition, in such a buffering arrangement, a free list is provided with empty buffers, which can be allocated to the lists for the respective sources or destinations when data to be buffered is received in the buffering arrangement. When a source provides data to be buffered in the buffering arrangement, an empty buffer from the free list is allocated for the data, by de-linking it from the free list and linking it to the list associated with the source or destination, after which the data can be stored in the newly-allocated buffer. When the destination retrieves data from a linked list, it retrieves the data from the respective buffers and thereafter links the data from which the buffers have been retrieved to the free list. Both of these processes require manipulating pointers in both the free list and the list associated with the source and destination.
While the use of linked lists is effective, it can be inefficient, particularly in connection with relatively small buffers. For example, the pointers which are used to organize the linked lists take up space in the buffers. In addition, manipulating the pointers when a buffer is allocated to one of the lists when data is received for storage, or returned to the free list when the data is retrieved by a destination, can take some time to perform.
SUMMARY OF THE INVENTION
The invention provides a new and improved system and method for efficiently allocating buffers in a digital data processing system from a pool of empty buffers using one or more FIFOs which contain pointers to empty buffers.
In brief summary, a buffer management subsystem in accordance with the invention receives data from one or more source processes for transfer to one or more destination processes. The buffer management subsystem includes a buffer memory and a buffer pointer FIFO that is associated with one of the destination processes. The buffer pointer FIFO stores pointers to buffers in the buffer memory which are available to be used to store data from the source process(es) for transfer to the respective associated destination process. When data is received from a source process for transfer to a destination process, a buffer pointer is retrieved from the buffer pointer FIFO associated with the destination process and used in storing the data in the buffer pointed to by the buffer pointer. When the data is retrieved from the buffer for transfer to the destination process, the buffer pointer to the buffer is returned to the buffer pointer FIFO.
REFERENCES:
patent: 4715030 (1987-12-01), Koch et al.
patent: 5778180 (1998-07-01), Gentry et al.
patent: 5812775 (1998-09-01), Seters et al.
IBM Technical Disclosure Bulletin, “Buffer Pools: Sharing a Common Resource with Guarantees”, vol. 37, No. 7, Jul. 1994, pp. 95-97.
Bromberg & Sunstein LLP
Lee Thomas
Park Ilwoo
Sun Microsystems Inc.
LandOfFree
Buffer management system having an output control configured... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Buffer management system having an output control configured..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Buffer management system having an output control configured... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2982517