Allocation/Deallocation of Memory
Memory is essential for the functioning of a computer—for programs to load and run, and for information to be generated and stored in a retrievable format. The allocation and deallocation of memory by a memory allocator is essential for efficient performance.
A memory allocator is mechanical. Generally, there are two types of allocators within a computer, a kernel level allocator and a user-space allocator. A memory allocator's task is to respond to a memory request based on its knowledge of the amount and location of free and used memory. Memory can be allocated in dislocated chunks. Fragmentation is avoided, as dedication of a discrete section of memory is preferred. This process can be difficult, however, as the allocator can only respond to the request for allocation and deallocation. It cannot bundle smaller packets of memory into the desired size or disperse memory into smaller packets.
Reducing memory fragmentation is important to the design and implementation of a memory allocator. When a client makes a request for memory, the allocator responds by searching for free memory. The request is satisfied only if a block of memory the size of the request or larger is located.
The inefficient allocation or deallocation of memory can be detrimental to computer performance. The presence of wasted memory in a block of allocated memory is called internal fragmentation. This occurs because the size that was requested in that region was smaller than the size of the block of memory that was allocated. The result is a block of unusable memory, which is considered allocated when, in fact, the block of memory is not being used. The reverse situation is called external fragmentation, when blocks of memory are freed, leaving holes in memory that are not contiguous. If these holes are not large, they may not be usable because further requests for memory may call for larger blocks. Both internal and external fragmentation results in unusable memory.
Memory allocation and deallocation is a process that has several layers of applications. If one application fails, another operates to attempt to resolve the request. This whole process is called dynamic memory management in the C programming language.
Memory is allocated to applications using an operating subsystem called malloc. The malloc subsystem controls heap, a region of memory to which memory allocation and deallocation occurs. Another function, the reallocation of memory, also is under the control of malloc. In malloc, the allocation of memory is performed by two subroutines, malloc and calloc. Deallocation is performed by the free subroutine, and reallocation is performed by the subroutine known as realloc.
The heap is comprised of blocks of allocated memory and freed memory. Allocation of memory is parceled out from the freed pool. An allocation is completed by first moving a block of memory from the freed pool, then returning to the free pool a pointer to the block. This does not mean that the blocks of memory are physically relocated. Rather, by programming commands, regions of memory are changed in state from free to in-use. Thus, the size of the heap does not change. The functionality of the heap does change.
In the process of allocation, the number of bytes (a unit of informational size) required to fulfill a request for memory is calculated using a specific equation. The required memory is then obtained from a binary tree. A binary tree is a repository of free space in the heap. The tree is sorted vertically by length and horizontally by address. In allocation, the leftmost region of the tree that fulfills the memory request is identified as being in-use. If this block turns out to be larger than needed, it is divided into two blocks, one of the size needed, and the other the remainder. This second block, called the runt, is returned to the tree, or more correctly is identified as being free, for future allocation. The first block is used to fulfill the memory request. If this process of tree searching fails to locate a block of sufficient size for the memory request, the heap can be expanded, a block the size of the acquired extension is added to the free tree and allocation continues as described above.
In deallocation, those memory blocks that have been deallocated are returned to the binary tree at its base. Thus, a binary tree can be envisioned as a sort of river of information, with deallocated memory flowing in at the base and allocated memory flowing out from the tips.
Garbage collection is another term associated with deallocation of memory. Garbage collection refers to an automated process that determines what memory a program is no longer using, and the subsequent recycling of that memory. The automation of garbage collection relieves the user of time-consuming and error-prone tasks. There are a number of algorithms for the garbage collection process. These operate independently of malloc.
This is the complete article, containing 803 words
(approx. 3 pages at 300 words per page).
