First Fit, Best Fit and Worst Fit
- Best fit: The allocator places a process in the smallest block of unallocated memory in which it will fit. For example, suppose a process requests 12KB of memory and the memory manager currently has a list of unallocated blocks of 6KB, 14KB, 19KB, 11KB, and 13KB blocks. The best-fit strategy will allocate 12KB of the 13KB block to the process.
- Worst fit: The memory manager places a process in the largest block of unallocated memory available. The idea is that this placement will create the largest hold after the allocations, thus increasing the possibility that, compared to best fit, another process can use the remaining space. Using the same example as above, worst fit will allocate 12KB of the 19KB block to the process, leaving a 7KB block for future use.
- First fit: There may be many holes in the memory, so the operating system, to reduce the amount of time it spends analyzing the available spaces, begins at the start of primary memory and allocates memory from the first hole it encounters large enough to satisfy the request. Using the same example as above, first fit will allocate 12KB of the 14KB block to the process.
Some Code is given Below. Email me if You need more help.
For Example of Memory has Size of 5 and each block has different Width
Int Memory[5];
Memory[0]=7;
Memory[1]=4;
Memory[2]=9;
Memory[3]=2;
Memory[4]=6;
//*********************** Memory Allocation Algorithms Below
class MemAllocation{ // Parent class for all algorithms to achieve polymorphism
public:
// Pure Virtual Function to achieve polymorphism in design
virtual bool GetMemory(int mem[],int reqMem,int memSize)=0;
};
class FirstFit: public MemAllocation{ // inheriting MemAllocation to achieve Late(Dynamic) Binding
public:
FirstFit(){} // constructor for First fit algorithm
virtual bool GetMemory(int mem[], int reqMem,int memSize){ // Polymorphic function
// Below is the first fit algorithm to access memory available
// Choose first block that can satisfy request
for(int i=0;i< memSize;i++){
if(mem[i] >= reqMem){
mem[i] = mem[i]-reqMem;
return true;
}
}
return false;
}
};
class BestFit: public MemAllocation{
int bestAvail;
public:
BestFit(){} // Best Fit constuctor
virtual bool GetMemory(int mem[],int reqMem,int memSize){ // inheriting MemAllocation to achieve Late(Dynamic) Binding
bestAvail=99999;
int bestAvailIndex=-1;
// Below is the code for Best Fir algorithm
// Search the whole list on each allocation
// Choose the smallest block
// Can stop if exact match found
for(int i=0;i< memSize;i++){
if(mem[i] == reqMem){ // if exact size memory found
mem[i]=0;
return true;
}else if(mem[i] > reqMem){
// doSomeThingHere
if((mem[i]- reqMem) < bestAvail){
bestAvailIndex = i;
bestAvail= mem[i]- reqMem ;
}
}
} // for Loop ends here
if(bestAvailIndex != -1){
mem[bestAvailIndex] = mem[bestAvailIndex] - reqMem;
return true; // returns true if every thing is fine
}else{
return false;
}
}
};
class WorstFit: public MemAllocation { // inheriting MemAllocation to achieve Late(Dynamic) Binding
int bestAvail;
public:
WorstFit(){} // constructor for worsr fit algorithm
virtual bool GetMemory(int mem[],int reqMem,int memSize){
bestAvail=-1;
int bestAvailIndex=-1;
// Below is the code for worst fit algorithm.
// Choose largest block (most leftover space)
for(int i=0;i< memSize;i++){
if(mem[i] >= reqMem){
// doSomeThingHere
if((mem[i]- reqMem) > bestAvail){
bestAvailIndex = i;
bestAvail= mem[i]- reqMem ;
}
}
} // for Loop ends here
if(bestAvailIndex != -1){
mem[bestAvailIndex] = mem[bestAvailIndex] - reqMem;
return true;
}else{
return false;
}
}
};
