** The following code is the first-fit algorithm.. Modify the allocate() method
ID: 3760331 • Letter: #
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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.