Abstract
This project aims at defragmenting active memory,i.e.,
physical memory or RAM. The Buddy Allocator allocates pages in chunks which are multiples of
powers of 2 times the native page size. Thus, AMD aims to form
higher
order blocks of memory by reallocating lower order blocks of memory by way
of
copies from initially allocated blocks of memory to the free blocks. The
previously allocated blocks are mapped in page tables. These page tables
have
to be made to point to the newly allocated blocks. This can be achieved by
reverse mapping (rmap). Thus, freeing the previously allocated blocks &
remapping the newly allocated blocks will result in free blocks, which are
coalesced to form blocks of the higher order. Repeating this process
recursively
will result in blocks of the desired higher order.
Thus, AMD is a last ditch effort before swapping. It is faster
than swapping because it involves only RAM copies, whereas swapping involves
the slowwer disk accesses.
Whenever we encounter a failure for an order N, we know that the buddy bitmap for that order has to contain all zeroes, with all zeroes indicating that both the buddies for that order are allocated. Thus, the only way to defrag for this order is to go to order N-1 & then use this order for forming blocks of order N. By observing the bitmap for order N-1, we encounter the following cases :-
- 0: Two 1's found, both of whose allocated buddies are of order N-1
- 1: Two 1's found, one of order N-1 and other not of order N-1
- 2: Two 1's found, both of whose orders != N-1
- 3: Only one 1 found which is not of order N-1
- 4: Only one 1 found which is of order N-1
- 5: No 1's found