New Topic/Question
Reply
I am stumbling through my assignment this week. The objective is to create a best-fit and worst fit algorithm in the code below. The methods have already been created in the class, but they are empty and doing nothing...I need some guidance as to how to approach these. There does not appear to be a lot of tutorials on these algorithms. Any guidance would be much appreciated. Here is what I have so far:
#pragma once
#include "MemoryManager.h"
#include <iostream>
using namespace std;
MemoryManager::MemoryManager(int size, int selection)
{
// Get the chunk of memory to manage
memory = new char[size];
memorySize = size;
// Set up the free block list overlaying the start of the free blocks
free = (blockInfo *)memory;
free->size = size;
free->ai.next = 0;
// Store which algorithm is to be used for allocations
selectedAlgorithm = selection;
// Initialize statistics
deallocsNotFound = 0;
predecessorsCoalesced = 0;
successorsCoalesced = 0;
numAllocs = 0;
numBlksSrchd = 0;
}
MemoryManager::~MemoryManager()
{
// Give the memory back to the system
delete [] memory;
}
char * MemoryManager::allocate(int & size)
{
char *addr;
if(selectedAlgorithm == FIRSTFIT)
addr = firstFit(size);
else if(selectedAlgorithm == BESTFIT)
addr = bestFit(size);
else
addr = worstFit(size);
// Add this allocation to the list of allocated blocks
if(addr != 0)
al.add(addr, size);
// Return the address of the allocated block to the user
return addr;
}
void MemoryManager::deallocate(char * addr)
{
// Find and remove the allocation information in the allocation list
int size = al.remove(addr);
// Must get positive size or the deallocation address was never allocated
if(size <= 0)
{
deallocsNotFound++;
return;
}
// Create the blockInfo structure at the start of the block being deallocated
blockInfo *ptr = (blockInfo *)addr;
blockInfo *pred = 0;
ptr->size = size;
ptr->ai.next = 0;
// Find the place in the free list to insert this block
// Blocks are inserted in sorted order so adjacent blocks can be coalesced
if(addr < (char *)free)
{
// This free block has a lower address than the first block
// in the free list so put this block at the head of the list
ptr->ai.next = free;
free = ptr;
}
else
{
// Block to be inserted after the first block
// so the first block in the list is the initial predecessor
pred = free;
// Traverse the list to find which block will precede the block being added
while(pred->ai.next != 0 && addr > pred->ai.addr)
pred = pred->ai.next;
// Connect the block to the predecessor
ptr->ai.next = pred->ai.next;
pred->ai.next = ptr;
}
// Coalese this block with its neighbors if possible!
coalesce(ptr, pred);
}
// Try to combine a free block with its list successor and predecessor
void MemoryManager::coalesce(blockInfo *ptr, blockInfo *pred)
{
// Is the end of this block the same address as the start of the next block?
if ((ptr->ai.next != 0) && (((char *)ptr) + ptr->size) == ptr->ai.addr)
{
successorsCoalesced++;
ptr->size += ptr->ai.next->size; // Add next block's size to this block
ptr->ai.next = ptr->ai.next->ai.next; // Point to next block's successor
}
// Is the end of the previous block the same address as this block?
if (pred != 0 && (((char *)pred) + pred->size) == (char *)ptr)
{
predecessorsCoalesced++;
pred->size += ptr->size; // Add this block's size to the predecessor
pred->ai.next = ptr->ai.next; // Predecessor points to this block's successor
}
}
// Allocate memory using the first fit algorithm to locate free space
// Size is a reference because if leftover amount in block is too small
// we will allocate the entire block and update the size
char * MemoryManager::firstFit(int & size)
{
char * addr;
int leftover;
blockInfo * ptr = free; // Get the head of the free list
blockInfo * pred = 0; // Predecessor is initially 0
numAllocs++;
do
{
numBlksSrchd++; // Keep track of how many blocks we search
if (ptr->size >= size) // Is this block big enough for this request?
{
// Calculate the amount of memory left over after we allocate the amount requested
leftover = ptr->size - size;
// If leftover amount is too small we will just allocate the entire block
if (leftover > sizeof(blockInfo) + MINSIZE)
{
// Plenty leftover, so allocate size bytes from the end of the free block
addr = (char *)ptr + ptr->size - size; // Starting address of allocated space
// Reduce the size of the free block by the size of the allocation
ptr->size -= size;
}
else
{
// Leftover too small, so allocate the entire block - remove it from the free list
size = ptr->size; // Update the size of the allocation
addr = (char *)ptr; // Address of the allocation is the block address
if(pred == 0)
{
// We are allocating the first block, so free must change
free = free->ai.next;
}
else
{
// Make the predecessor block point to the next block
pred->ai.next = ptr->ai.next;
}
}
return addr;
}
else
{
// Current block is too small, so go to next block
pred = ptr;
ptr = ptr->ai.next;
}
} while (ptr != 0);
// No block was found, so return null.
size = 0;
return 0;
}
char * MemoryManager::bestFit(int & size)
{
return 0;
}
char * MemoryManager::worstFit(int & size)
{
return 0;
}
// Output some statistics which characterize the operation of the memory manager
void MemoryManager::reportStats()
{
int numBlocks = 0; // Current number of blocks in the free list
int freeMem = 0; // Current amount of free memory
al.reportStats(); // Report the current allocation statistics
// Output data about block coalescing and failed deallocations
cout << "\nSuccessors coalesed: " << successorsCoalesced << " Predecessors coalesed: " << predecessorsCoalesced
<< " Deallocations not found " << deallocsNotFound << endl;
// Traverse the free list, count the blocks and sum the free memory space
blockInfo *tmp = free;
while(tmp != 0)
{
numBlocks++;
freeMem += tmp->size;
tmp = tmp->ai.next;
}
// Output info on current free list, including average block size
cout << "\nFree blocks: " << numBlocks << " Free memory: " << freeMem << " Average block: " << freeMem/numBlocks << endl;
// Output info on how many blocks were searched to fill the allocation requests
cout << "\nAverage free list search length = " << numBlksSrchd/numAllocs << endl;
}
// Output the current free list, one block per line
// To be used for debugging purposes
void MemoryManager::printList()
{
blockInfo *ptr = free;
while(ptr != 0)
{
cout << ptr << "\t" << ptr->size << "\t" << ptr->ai.next << "\t" << (blockInfo *)((char *)ptr + ptr->size) << endl;
ptr = ptr->ai.next;
}
}
// Search the free list to verify it is in sorted order
// To be used for debugging purposes
void MemoryManager::listCheck(int num)
{
blockInfo *ptr = free;
while(ptr->ai.next != 0)
{
if (ptr > ptr->ai.next)
{
// If the list is out of order, dump the list and loop forever!
cout << "List out of order! " << num << "\n";
printList();
while(1);
}
ptr = ptr->ai.next;
}
}
MultiQuote
| 