Storage allocation and garbage collection using liberate space tokens

摘要

A parallel storage allocation method and device in which each space in a memory section that is available for use is associated with a respective allocator and stores an identifier for the respective allocator, data identifying allocators not in use is stored, and a list of allocators associated with spaces which are available for use is maintained. Each time a memory space is no longer in use a check is made to determine the allocator identifier of any already free space which can be combined with the memory space that is no longer in use. A liberate space token is generated which includes a first identifier corresponding to an allocator which is not in use and a second identifier which corresponds to any already free space to be combined. If the list of allocators relative to available space does not contain the allocator having the second identifier, the allocator having the first identifier is entered in the list with details of the no longer in use space. If the list does not contain the allocator having the second identifier, the space that is no longer in use is combined with the space to which the second identifier relates and then the allocator having the first identifier is entered in the list with details of the combined space.