** The following code is the first-fit algorithm.. Modify the allocate() method

Question

 ** The following code is the first-fit algorithm.. Modify the allocate() method to implement a best-fit algorithm instead   public class HeapManager {   static private final int NULL = -1; // our null link   public int[] memory; // the memory we manage   private int freeStart; // start of the free list       /**    * HeapManager constructor.    * @param initialMemory the int[] of memory to manage    */   public HeapManager(int[] initialMemory) {     memory = initialMemory;     memory[0] = memory.length; // one big free block     memory[1] = NULL; // free list ends with it     freeStart = 0; // free list starts with it   }    /**    * Allocate a block and return its address.    * @param requestSize int size of block, > 0    * @return block address    * @throws OutOfMemoryError if no block big enough    */   public int allocate(int requestSize) {     int size = requestSize + 1; // size including header      // Do first-fit search: linear search of the free      // list for the first block of sufficient size.      int p = freeStart; // head of free list     int lag = NULL;     while (p != NULL && memory[p] < size) {       lag = p; // lag is previous p       p = memory[p + 1]; // link to next block     }     if (p == NULL) // no block large enough       throw new OutOfMemoryError();     int nextFree = memory[p + 1]; // block after p      // Now p is the index of a block of sufficient size,     // lag is the index of p's predecessor in the     // free list, or NULL, and nextFree is the index of     // p's successor in the free list, or NULL.      // If the block has more space than we need, carve     // out what we need from the front and return the     // unused end part to the free list.      int unused = memory[p]-size; // extra space in block     if (unused > 1) { // if more than a header's worth       nextFree = p + size; // index of the unused piece       memory[nextFree] = unused; // fill in size        memory[nextFree+1] = memory[p+1]; // fill in link       memory[p] = size; // reduce p's size accordingly     }      // Link out the block we are allocating and done.      if (lag == NULL) freeStart = nextFree;     else memory[lag + 1] = nextFree;     return p+1; // index of useable word (after header)   }    /**    * Deallocate an allocated block.  This works only if    * the block address is one that was returned by    * allocate and has not yet been deallocated.    * @param address int address of the block    */   public void deallocate(int address) {     int addr = address - 1; // real start of the block      // Find the insertion point in the sorted free list     // for this block.      int p = freeStart;     int lag = NULL;     while (p != NULL && p < addr) {       lag = p;       p = memory[p + 1];     }      // Now p is the index of the block to come after     // ours in the free list, or NULL, and lag is the     // index of the block to come before ours in the     // free list, or NULL.      // If the one to come after ours is adjacent to it,     // merge it into ours and restore the property     // described above.      if (addr + memory[addr] == p) {       memory[addr] += memory[p]; // add its size to ours       p = memory[p + 1]; //     }      if (lag == NULL) { // ours will be first free       freeStart = addr;       memory[addr + 1] = p;     }     else if (lag+memory[lag]==addr) { // block before is                                    // adjacent to ours       memory[lag] += memory[addr]; // merge ours into it       memory[lag + 1] = p;     }     else { // neither, just a simple insertion       memory[lag + 1] = addr;       memory[addr + 1] = p;     }   } } 

Explanation / Answer

public class HeapManager {
   static private final int NULL = -1; // our null link
   public int[] memory; // the memory we manage
   private int freeStart; // start of the free list

   /**
   * HeapManager constructor.
   *
   * @param initialMemory
   * the int[] of memory to manage
   */
   public HeapManager(int[] initialMemory) {
       memory = initialMemory;
       memory[0] = memory.length; // one big free block
       memory[1] = NULL; // free list ends with it
       freeStart = 0; // free list starts with it
   }

   /**
   * Allocate a block and return its address.
   *
   * @param requestSize
   * int size of block, > 0
   * @return block address
   * @throws OutOfMemoryError
   * if no block big enough
   */
   public int allocate(int requestSize) {
int size = requestSize + 1; // size including header

// Do first-fit search: linear search of the free
// list for the first block of sufficient size.

int p = freeStart; // head of free list
int lag = NULL;
int max = NULL;
int maxP = NULL;
while (p != NULL) { // search all blocks and find the one with the maximum available allocation
lag = p; // lag is previous p
if(memory[p] > max && memory[p] >= size){
   // if current block has more size than the currentMax store
   // store this as max and store p as maxP
   max = memory[p];
   maxP = p;
}
p = memory[p + 1]; // link to next block
}
p = maxP; // set p to maxP
if (p == NULL) // no block large enough
throw new OutOfMemoryError();
int nextFree = memory[p + 1]; // block after p

// Now p is the index of a block of sufficient size,
// lag is the index of p's predecessor in the
// free list, or NULL, and nextFree is the index of
// p's successor in the free list, or NULL.

// If the block has more space than we need, carve
// out what we need from the front and return the
// unused end part to the free list.

int unused = memory[p]-size; // extra space in block
if (unused > 1) { // if more than a header's worth
nextFree = p + size; // index of the unused piece
memory[nextFree] = unused; // fill in size
memory[nextFree+1] = memory[p+1]; // fill in link
memory[p] = size; // reduce p's size accordingly
}

// Link out the block we are allocating and done.

if (lag == NULL) freeStart = nextFree;
else memory[lag + 1] = nextFree;
return p+1; // index of useable word (after header)
}

   /**
   * Deallocate an allocated block. This works only if the block address is
   * one that was returned by allocate and has not yet been deallocated.
   *
   * @param address
   * int address of the block
   */
   public void deallocate(int address) {
       int addr = address - 1; // real start of the block

       // Find the insertion point in the sorted free list
       // for this block.

       int p = freeStart;
       int lag = NULL;
       while (p != NULL && p < addr) {
           lag = p;
           p = memory[p + 1];
       }

       // Now p is the index of the block to come after
       // ours in the free list, or NULL, and lag is the
       // index of the block to come before ours in the
       // free list, or NULL.

       // If the one to come after ours is adjacent to it,
       // merge it into ours and restore the property
       // described above.

       if (addr + memory[addr] == p) {
           memory[addr] += memory[p]; // add its size to ours
           p = memory[p + 1]; //
       }

       if (lag == NULL) { // ours will be first free
           freeStart = addr;
           memory[addr + 1] = p;
       } else if (lag + memory[lag] == addr) { // block before is
                                               // adjacent to ours
           memory[lag] += memory[addr]; // merge ours into it
           memory[lag + 1] = p;
       } else { // neither, just a simple insertion
           memory[lag + 1] = addr;
           memory[addr + 1] = p;
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.