Compiler Design - Modify Code: Memory Management project Given FirstFit, please
ID: 3891102 • Letter: C
Question
Compiler Design - Modify Code:
Memory Management project
Given FirstFit, please finish BestFit and WorstFit
-------------------------------------------------------------------------------------
//FirstFit.hpp
#ifndef FIRSTFIT_HPP
#define FIRSTFIT_HPP
#include "Policy.hpp"
class FirstFit : public Policy
{
public:
void* onMalloc(int size);
void onFree(void* address);
};
#endif // !FIRSTFIT_HPP
-------------------------------------------------------------------------------------
//FirstFit.cpp
#include "stdafx.h"
#include "FirstFit.hpp"
#include "MemoryStructure.hpp"
#include "ScheduleProcessor.hpp"
#include "defines.hpp"
#include <thread>
int defragmentPrepareEnd(int target_size);
int defragmentPrepareFront(int target_size);
void* FirstFit::onMalloc(int size)
{
MemoryStructure* ms = MemoryStructure::getInstance();
while(true)
{
void* prev_end = 0;
for(int i = 0; i < ms->getAllocationListSize(); i++)
{
Allocation alloc = ms->getAllocation(i);
if((int)alloc.addr - (int)prev_end >= size)
{
ASSERT(ms->allocate(prev_end, size));
return prev_end;
}
prev_end = (void*)((int)alloc.addr + (int)alloc.size);
}
if(MAX_MEMORY_CAP - (int)prev_end >= size)
{
ASSERT(ms->allocate(prev_end, size));
return prev_end;
}
if(!defragmentPrepareEnd(size)) defragmentPrepareFront(size);
}
}
void FirstFit::onFree(void* address)
{
MemoryStructure* ms = MemoryStructure::getInstance();
for(int i = 0; i < ms->getAllocationListSize(); i++)
{
Allocation alloc = ms->getAllocation(i);
if(alloc.addr == address)
{
ASSERT(ms->deallocate(address));
return;
}
}
printf("DE Error : allocation not found! (%d, %p) ", address, address);
exit(1);
}
int defragmentPrepareEnd(int target_size)
{
printf("*** Fast defragmentation!! Target Size : %d ", target_size);
std::this_thread::sleep_for(std::chrono::milliseconds(300));
MemoryStructure* ms = MemoryStructure::getInstance();
int last_cap = MAX_MEMORY_CAP;
// Retry until threshold
for(int search_length = ms->getAllocationListSize(); search_length; search_length--)
{
// Move while moving allocation succeeds
for(bool succeeded = true; succeeded;)
{
succeeded = false;
Allocation alloc_from = ms->getAllocation(search_length - 1);
void* prev_end = 0;
// Search for the space to move on
for(int i = 0; i < search_length; i++)
{
Allocation alloc_front_to = ms->getAllocation(i);
// Found the space
if((int)alloc_front_to.addr - (int)prev_end >= alloc_from.size)
{
ScheduleProcessor::getInstance()->notifyAddressChange(alloc_from.addr, prev_end);
// Move allocation
ASSERT(ms->migrate(alloc_from.addr, prev_end));
succeeded = true;
break;
}
prev_end = (void*)((int)alloc_front_to.addr + alloc_front_to.size);
}
// Check if the space is enough
Allocation last_alloc = ms->getAllocation(search_length - 1);
if(last_cap - (int)last_alloc.addr - last_alloc.size >= target_size)
{
printf("good! %d at %d ", search_length - 1, last_alloc.addr);
return true;
}
}
last_cap = (int)ms->getAllocation(search_length - 1).addr;
}
return false;
}
int defragmentPrepareFront(int target_size)
{
printf("*** Fast defragmentation failed. Slow defragmentation.... ");
std::this_thread::sleep_for(std::chrono::milliseconds(300));
MemoryStructure* ms = MemoryStructure::getInstance();
void* prev_end = 0;
for(int i = 0; i < ms->getAllocationListSize(); i++)
{
Allocation alloc_from = ms->getAllocation(i);
int rem_space = (int)alloc_from.addr - (int)prev_end;
if(rem_space > 0)
{
if(rem_space >= target_size) return 1;
ScheduleProcessor::getInstance()->notifyAddressChange(alloc_from.addr, prev_end);
// Move allocation
ASSERT(ms->migrate(alloc_from.addr, prev_end));
}
prev_end = (void*)((int)prev_end + alloc_from.size);
}
return 0;
}
-------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------
//BestFit.hpp
#ifndef BESTFIT_HPP
#define BESTFIT_HPP
#include "Policy.hpp"
class BestFit : public Policy
{
public:
void* onMalloc(int size);
void onFree(void* address);
};
#endif // !BESTFIT_HPP
-------------------------------------------------------------------------------------
//BestFit.cpp
#include "stdafx.h"
#include "BestFit.hpp"
#include "MemoryStructure.hpp"
#include "ScheduleProcessor.hpp"
#include "defines.hpp"
void* BestFit::onMalloc(int size)
{
// Here to be implemented
return (void*)0x60000000;
}
void BestFit::onFree(void* address)
{
// Here to be implemented
}
-------------------------------------------------------------------------------------
//WorstFit .hpp
#ifndef WORSTFIT_HPP
#define WORSTFIT_HPP
#include "Policy.hpp"
class WorstFit : public Policy
{
public:
void* onMalloc(int size);
void onFree(void* address);
};
#endif // !WORSTFIT_HPP
-------------------------------------------------------------------------------------
//WorstFit.cpp
#include "stdafx.h"
#include "WorstFit.hpp"
#include "MemoryStructure.hpp"
#include "ScheduleProcessor.hpp"
#include "defines.hpp"
void* WorstFit::onMalloc(int size)
{
// Here to be implemented
return (void*)0x60000000;
}
void WorstFit::onFree(void* address)
{
// Here to be implemented
}
Explanation / Answer
Hello,
As you stated, Below is the code for Worst fit and Best fit.
Worst Fit:
#include<bits/stdc++.h>
using namespace std;
void WFit(int BlkSize[], int m, int SizeOfProcess[], int n)
{
int Alloc[n];
memset(Alloc, -1, sizeof(Alloc));
for (int i=0; i<n; i++)
{
int WorstIndex = -1;
for (int j=0; j<m; j++)
{
if (BlkSize[j] >= SizeOfProcess[i])
{
if (WorstIndex == -1)
WorstIndex = j;
else if (BlkSize[WorstIndex] < BlkSize[j])
WorstIndex = j;
}
}
if (WorstIndex != -1)
{
Alloc[i] = WorstIndex;
BlkSize[WorstIndex] -= SizeOfProcess[i];
}
}
cout << " Process_Num: Process_Size: Block_Num. ";
for (int i = 0; i < n; i++)
{
cout << " " << i+1 << " " << SizeOfProcess[i] << " ";
if (Alloc[i] != -1)
cout << Alloc[i] + 1;
else
cout << "Not Allocated";
cout << endl;
}
}
int main()
{
int BlkSize[] = {300, 200, 500, 600, 100};
int SizeOfProcess[] = {112, 426, 212, 417};
int m = sizeof(BlkSize)/sizeof(BlkSize[0]);
int n = sizeof(SizeOfProcess)/sizeof(SizeOfProcess[0]);
WFit(BlkSize, m, SizeOfProcess, n);
return 0 ;
}
Best Fit:
#include<bits/stdc++.h>
using namespace std;
void BFit(int BlkSize[], int m, int SizeOfProcess[], int n)
{
int Alloc[n];
memset(Alloc, -1, sizeof(Alloc));
for (int i=0; i<n; i++)
{
int BestIndex = -1;
for (int j=0; j<m; j++)
{
if (BlkSize[j] >= SizeOfProcess[i])
{
if (BestIndex == -1)
BestIndex = j;
else if (BlkSize[BestIndex] > BlkSize[j])
BestIndex = j;
}
}
if (BestIndex != -1)
{
Alloc[i] = BestIndex;
BlkSize[BestIndex] -= SizeOfProcess[i];
}
}
cout << " Process_Num. Process_Size Block_Num. ";
for (int i = 0; i < n; i++)
{
cout << " " << i+1 << " " << SizeOfProcess[i] << " ";
if (Alloc[i] != -1)
cout << Alloc[i] + 1;
else
cout << "Not Allocated";
cout << endl;
}
}
int main()
{
int BlkSize[] = {300, 200, 500, 600, 100};
int SizeOfProcess[] = {112, 426,212, 417};
int m = sizeof(BlkSize)/sizeof(BlkSize[0]);
int n = sizeof(SizeOfProcess)/sizeof(SizeOfProcess[0]);
BFit(BlkSize, m, SizeOfProcess, n);
return 0 ;
}
If you need to make any change in the code, you can absolutely make it.
Hope, I have solved your problem.
Thank you :) Have a pleasant day :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.