2003-2004

Project Members: Alok Mooley, Ashwin Rao, Sushant Paithane, Vijay Agashe

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

We partition the pages into movable and unmovable pages. We apply various algorithms, as discussed in the design section to address these various cases of the movable pages.