- Managing the free space is easy only
when the space that has to be managed is divided in to units of fixed size.
- If
this is the case, the list of these fixed size units can be kept.
- The first
entry can be returned if it is requested by the client.
- Managing free space
gets difficult when the space to be managed consists of units of variable
sizes.
- This is the case with the memory allocation library at the user level.
- This is also the case in the physical memory where the segmentation is used for
the implementation of the virtual memory.
- In such cases, external
fragmentation is the main problem.
- This leads to the splitting up of the disk
space in to pieces of variable size.
- The next coming requests might fail
because of unavailability of contiguous free space.
- For example, the request
might fail even if 20 bytes are available and the request requires only 15
bytes because this 20 bytes space is non-contiguous.
- Thus, the main problem is
how the free space should be managed while satisfying the variable sized
variables.
How these strategies can manage free space while at the same time
keeping the fragmentation in control.
Low level Mechanisms:
- Most of the
allocator use some common mechanisms as these: coalescing and splitting.
- Here, the free list consists of a set of elements describing about all the free
spaces available in the heap.
- Once a pointer to a space is handed over to the program,
the determination of the pointers to this space becomes somewhat difficult.
- These pointers are stored either in the registers or in the variables at some
point of execution.
- However, this is not the case of garbage collected and
strongly typed languages as a measure for enabling compaction for combating
fragmentation. - Suppose the program makes a request for a single byte of memory.
- In such a case the action performed by the allocator is called splitting.
- Here
a free memory chunk is searched for and split in to two.
- The first one is
returned to the calling request and the second one stays in the list itself.
- This
approach is used in the allocators where small requests are made requesting space
that is of size smaller than the chunk.
- Most of the allocators use a corollary
mechanism called the coalescing of the free space.
- Suppose a small heap is
given and an application calls a function to obtain some memory.
- This function
returns the space available in the middle of the heap.
- All these strategies are
based up on simple policies.
- An ideal allocator is the one that both minimizes
fragmentation and is fast.
- But since it is possible for the stream of free
requests and allocation to be arbitrary, any strategy would go wrong if wrong
inputs are given.
- Thus, the best approach cannot be described.
There are 4
major approaches in this regard:
1. Best fit:
- Simplest
and first searches the list for free chunks of memory that might be bigger
than the size requested.
- The smallest one in the searched ones is returned
and this is known as the best fitting chunk or smallest fitting too.
- One
pass is enough for finding the appropriate block to be returned.
2. Worst fit:
- This one
is just the opposite of the best fit.
- It looks for the largest chunk and
returns the amount requested while keeping the remaining memory space.
3. First fit:
- This one
also looks for the first bigger block and out of it allocates the amount
requested by the thread.
4. Next fit:
- Here, one
extra pointer is kept at the location where the last search was done.
