A buffer-based method for storage allocation in an object-oriented system

As some object-oriented computing systems support the object type buffer by hardware, it is reasonable to base their free storage management on a set of buffers, each containing free storage blocks of a specific length. Then memory space can normally be allocated and deallocated by simple buffer read and write operations. More complex routines have to be executed only when a buffer full or buffer empty exception is raised. Their task is to clear a buffer position or to insert a storage descriptor into the buffer, respectively. An algorithm that handles such exceptions by splitting and recombination of free blocks and relocation of objects is described. The algorithm is tuned by a set of parameters that specify the amount of descriptors the buffers may hold immediately after exception handling. As a consequence, each buffer receives a moderate number of descriptors, so that the probability of further exceptions is reduced. Moreover, the parameters control the tradeoff between relocation costs and resulting storage fragmentation. The performance of the algorithm is evaluated by an analytical and a simulation model, and methods to find optimal parameter values are described