Algorithm for the Freeing of Buffers Acquired in (Contiguous) Storage Blocks
Original Publication Date: 2001-Dec-16
Included in the Prior Art Database: 2003-Jun-20
Computing software frequently encounters situations in which the demand for resource (particularly storage) can occur quite explosively; e.g. when there is a sudden (unpredictable) need to transmit a large amount of data through a network, implying that (storage) buffers are required to house this information during the sending and receiving operations. To prevent the need for excessive, and expensive, forays through the operating system platform (e.g. GETMAIN), software subsystems acquire multiple buffers in a single block of requested storage; however the subsystems do treat each buffer (relatively) autonomously. Each storage block contributes a number of buffers to the overall storage pool. Also a subsystem does not necessarily release a buffer after its immediate use, but retains it and simply marks it available for potential subsequent usage. (Note that even if a buffer is available, the storage block itself cannot be released until all the buffers in that storage block are each marked as available.) Thus, after a period of operation a subsystem can have a significant number of buffers available for re-use, typically distributed across many storage blocks. In this way the subsystem has some capacity to absorb a "burst" in demand for storage, which by its nature is at a time when the subsystem is busy, by first utilising the accumulated stock of this resource. Inevitably there will be situations which require the storage blocks acquired by the subsystem to be released back to the operating system (e.g. FREEMAIN). This entails determining which storage blocks are eligible for release (i.e. containing only buffers which are marked as free). Obviously the ideal condition is to maximise the number of storage blocks eligible for release, by concentrating the non-free buffers into a smallest possible number of storage blocks. In addition, the buffer acquisition and release mechanism needs to be accommodate very large numbers of buffers (and therefore of storage blocks) without causing noticeable performance degradation, entailing that the cost of obtaining and returning a buffer to the storage pool is small in instruction count terms (irrespective of the number of elements, very large or very small, in the storage pool).