The memory that a system uses at runtime must be managed as the creation and deletion of dynamic variables causes the use and re-use of memory. There are two types of blocks of memory, fixed size and varied size. The fixed size records are handled most easily and the varied size records show the use of linked list techniques without using record structures.
The final issue of memory management is the recollection of space that a user is finished with but has not explicitly returned to the system. This is called garbage collection and is an active research issue.
When all the records are the same size, for example in managing disk blocks or when developing a library of routines to handle a data structure of your creation, maintaining the free memory is relatively simple. First the space that is to be used for the structures, the disk or a chunk of memory, is initialized to consist completely of the fixed size blocks that we are dealing with. If it is a record structure as below, treat available space as an array of these
Then the variable FREE, globally available, is set to point to the first record and a linked list called the freelist has been built. This list will be added to and taken from the front of the list. This is simply because it is faster and easier to access the front of a singly linked list.
New and dispose are quite simple and are presented below. The user is required to call dispose for every record that is no longer being used. This is clumsy and a solution is presented under Garbage collection.
thing * Free; struct thing { object foo; thing * next; }; thing space [SPACESIZE]; for(int i = 0; i < SPACESIZE; i++) { space[i].next = &space[i+1]; } // for space[SPACESIZE].next = NULL; Free = space; void new(thing * x) { if(Free == NULL) x = NULL; else x = Free; Free := *Free.next } // new void delete(thing * x) { *x.next = Free; Free = x; } // dispose
When dealing with variable size records, we cannot create a simple free list as above. The linked list of objects will be made out of the objects themselves. They will act like a linked list of records, but will not be of the type record since they will
This is done by storing information sections of the record that are at fixed relative positions from the beginning of the record. For example, the pointer to the next block will be stored in the first two bytes of the block. Thus if we have the address of the beginning of the block, we can get the pointer to the next since it is stored in the address pointer_to_start + 0.
The space we will be dividing up starts out as one large block of storage with the following information in it.
SIZE ACTIVE FLINK BLINK empty space FRONT
The FLINK and BLINK fields are forward and backward pointers. These are initialized to point to themselves. The SIZE field is the number of bytes in the block, minus the size of the SIZE and ACTIVE fields. This is because even while a record is being used, the SIZE and ACTIVE fields are used in it.
Thus, all manipulations of the block of space given to a calling procedure must start after the SIZE and ACTIVE fields. The ACTIVE field is Boolean, indicating whether the block is in use or not. The FRONT field is used to find the front of a record if we are given a pointer to the end of it.
The BLINK,FLINK and FRONT fields are only defined in a block that is not used and is part of the freelist. When a block is allocated, these fields are cleared. When a block is restored, it is inserted at the front of the list and these fields are filled
The reason for the FRONT pointer is to find the physically preceding record. Given a pointer to a block, pointer - 2 is the FRONT pointer and pointer - (value(pointer - 2)) is the front of the block. This enables us to collapse physically adjacent blocks together to create bigger chunks in the freelist. This helps prevent external fragmentation, which is the case where the sum of all the sizes
Internal fragmentation is the case where the blocks handed out are somewhat larger than actually needed. This is done sometimes to prevent the breaking up of blocks into very small pieces, see external fragmentation.