How do you write a C plus plus code for first fit worst fit best fit algorithms?

Answer 1

The following program shows one method of implementing first-fit, best-fit and worst-fit algorithms. There's a lot of code but it can be broken down into 4 major classes: process, processes, partition and partitions. In the real-world, the partition class would allocate memory to itself and assign one or more processes to that memory (keeping track of which process is where). Likewise, the process class would represent an actual process. However, to keep things simple, we're just modelling these objects to show how the algorithms work in terms of allocating a process to a partition based upon the size of the process and the available bytes in a partition.

The process class simply stores an ID and the size of the process (in bytes). The processes class is really nothing more than a wrapper for an embedded vector of processes. Similarly, the partition class holds an ID, the size of the partition and an embedded processes class to keep track of which processes it holds. The partitions class is also nothing more than a wrapper for an embedded vector of partitions.

In the main function we can see how these classes are used. First, 5 partitions are allocated sizes of 4096, 2048, 1024, 512 and 256 bytes. In the real-world partitions would be equal size, however we can imagine that they were all 4096 bytes to begin with and that these sizes represent what is currently available. We then create 10 processes from 2048 down to 4 bytes in size. We then randomise the order of both collections to give a more realistic example (the IDs tell us the order in which they were actually created).

The key to allocating the processes to the partitions is the processes::allocate function, where we pass a reference to the processes to be allocated, along with the method (first, best or worst).

With first-fit, we simply take each process in turn and allocate it to the first partition that is large enough. Since the processes and partitions were randomised to begin with, they could be placed in any order. However, note that the largest process (process 1 with 2048 bytes) can only be placed in partition 1 (4096 bytes) or partition 2 (2048 bytes), but can only be placed in partition 2 if there no other processes occupying that partition. Partition 1 is capable of holding all 10 processes at once, so there should never be the situation where a process cannot be allocated (in the real-world it can happen, in which case you would need to try and add a new partition).

With best-fit, we're looking for the partition that leaves the least free bytes for each process. To achieve this we sort the processes in descending order of size. We also sort the partitions in ascending order of size before each process is allocated to a partition. By sorting the collections in this manner, we can re-use the first-fit algorithm, which will always finds the smallest partition that will accept the process.

With worst-fit we do the same thing as we did with best-fit, except we reverse the order. Processes are sorted in ascending order of size and partitions in descending order of size. Again, this allows us to use the first-fit algorithm to find the largest partition that will accept the process.

In other words, we use the same algorithm for all three, the only difference being the order of the processes and partitions.

In the real-world, of course, we'd allocate just one process at a time rather than a collection of processes all at once. Thus the only difference with best-fit and worst-fit is that we do not need to sort the processes at all, but we must still sort the partitions based upon the current available bytes (but not for first-fit). We achieve this by totalling the size of the current processes within that partition and subtract that sum from the partition size. However, in the real world processes may be deallocated in any sequence, which will leave non-contiguous gaps in the partition. We get around that problem by allocating sub-partitions to those gaps, thus every partition is really a tree of sub-partitions that starts out with one node (the root). In order to locate the best or worst fit we must 'flatten' the trees by creating a vector for all the nodes and sub-nodes and then sort that vector by the size of each node. This is well beyond the scope of the answer of course, however the program below contains enough information to be able to apply first, best and worst-fit to any vector, regardless of its source.

Program code

#include

#include

#include

#include

#include

// forward declarations

class process_class;

class processes_class;

class partition_class;

class partitions_class;

std::ostream& operator<< (std::ostream& os, const process_class& process);

std::ostream& operator<< (std::ostream& os, const processes_class& processes);

std::ostream& operator<< (std::ostream& os, const partition_class& partition);

std::ostream& operator<< (std::ostream& os, const partitions_class& partitions);

// enumerations

enum fitness {

first = 0,

best = 1,

worst = 2

};

// the process class

class process_class

{

private:

static unsigned s_id;

unsigned m_id;

unsigned m_bytes;

public:

process_class (unsigned bytes): m_bytes (bytes), m_id (++s_id) {}

bool operator< (const process_class& rhs) { return (m_bytes < rhs.m_bytes); }

unsigned get_id () const { return (m_id); }

unsigned get_bytes () const { return (m_bytes); }

};

// initialise static member

unsigned process_class::s_id = 0;

// insertion operator overload

std::ostream& operator<< (std::ostream& os, const process_class& process)

{

os << "Process " << std::setw (2) << process.get_id() << " (" << std::setw (4) << process.get_bytes() << " bytes)";

return (os);

}

// the processes class

class processes_class

{

private:

std::vector m_vect;

static bool compare (process_class* a, process_class* b) {

return (a->get_bytes() < b->get_bytes()); }

public:

processes_class()

: m_vect () {}

processes_class (const processes_class& other)

: m_vect (other.m_vect) {}

processes_class& operator= (const processes_class& rhs)

{

m_vect = rhs.m_vect;

return (*this);

}

unsigned get_bytes() const

{

unsigned bytes = 0;

for (std::vector::const_iterator it=m_vect.begin(); it!=m_vect.end(); ++it)

bytes += (*it)->get_bytes();

return (bytes);

}

unsigned size() const {return (m_vect.size()); }

void sort_up() { std::sort (m_vect.begin(), m_vect.end(), &processes_class::compare); }

void sort_down() { std::sort (m_vect.rbegin(), m_vect.rend(), &processes_class::compare); }

void unsort()

{

unsigned size = m_vect.size();

for (unsigned i=1; i

{

unsigned rnd = rand() % --size + i;

std::swap (*m_vect[i-1], *m_vect[rnd]);

}

}

void swap (processes_class& rhs) {

std::swap (m_vect, rhs.m_vect); };

// vector iterators and other helpers

std::vector::const_iterator begin() const { return (m_vect.begin());}

std::vector::iterator begin() { return (m_vect.begin());}

std::vector::const_iterator end() const { return (m_vect.end());}

std::vector::iterator end() { return (m_vect.end());}

std::vector::const_reverse_iterator rbegin() const { return (m_vect.rbegin());}

std::vector::reverse_iterator rbegin() { return (m_vect.rbegin());}

std::vector::const_reverse_iterator rend() const { return (m_vect.rend());}

std::vector::reverse_iterator rend() { return (m_vect.rend());}

bool empty() { return (m_vect.empty()); };

void pop_back() { m_vect.pop_back(); }

std::vector::reference back() { return (m_vect.back()); };

std::vector::const_reference back() const { return (m_vect.back()); };

void push_back(process_class* process) { m_vect.push_back (process); }

};

// insertion operator overload

std::ostream& operator<<(std::ostream& os, const processes_class& processes)

{

os << "Processes: " << processes.size() << '\n' << std::endl;

for (std::vector::const_iterator current_process=processes.begin();

current_process!=processes.end(); ++current_process)

{

const process_class& process = **current_process;

os << process << std::endl;

}

return (os);

}

// the partition class

class partition_class

{

private:

static unsigned s_id;

unsigned m_id;

unsigned m_bytes;

processes_class m_processes;

void swap (partition_class& rhs)

{

std::swap (m_id, rhs.m_id);

std::swap (m_bytes, rhs.m_bytes);

m_processes.swap (rhs.m_processes);

}

public:

partition_class (unsigned bytes)

: m_bytes(bytes), m_id(++s_id) {}

partition_class(const partition_class& other)

: m_bytes (other.m_bytes), m_id (other.m_id), m_processes (other.m_processes) {}

partition_class& operator= (const partition_class& rhs)

{

m_bytes = rhs.m_bytes;

m_id = rhs.m_id;

m_processes = rhs.m_processes;

return (*this);

}

unsigned get_id() const { return (m_id); }

unsigned get_bytes() const { return (m_bytes - m_processes.get_bytes()); }

void allocate(process_class& process)

{

std::cout << process << " allocated to " << *this;

m_processes.push_back (&process);

std::cout << " leaving " << std::setw(4) << get_bytes() << " bytes free" << std::endl;

}

void deallocate_all()

{

while (!m_processes.empty())

m_processes.pop_back();

}

};

// initialise static member

unsigned partition_class::s_id = 0;

// insertion operator overload

std::ostream& operator<< (std::ostream& os, const partition_class& partition)

{

os << "Partition " << partition.get_id() << " (" << std::setw(4) << partition.get_bytes() << " bytes)";

return (os);

}

// forward declarations

class partitions_class;

std::ostream& operator<< (std::ostream& os, const partitions_class& partition);

// the partitions class

class partitions_class

{

private:

std::vector m_vect;

partitions_class (const partitions_class&); // disabled

partitions_class& operator= (const partitions_class&); // disabled

static bool compare (partition_class& a, partition_class& b) {

return (a.get_bytes() < b.get_bytes()); }

public:

partitions_class () {}

void sort_up() { std::sort (m_vect.begin(), m_vect.end(), &partitions_class::compare); }

void sort_down() { std::sort (m_vect.rbegin(), m_vect.rend(), compare); }

void unsort()

{

unsigned size = m_vect.size();

for (unsigned i=1; i

{

unsigned rnd = rand() % --size + i;

std::swap (m_vect[i-1], m_vect[rnd]);

}

}

void allocate (processes_class& processes, fitness fit)

{

switch(fit)

{

case (first):

std::cout << "First Fit\n" << std::endl;

break;

case (best):

std::cout << "Best Fit\n" << std::endl;

processes.sort_down();

break;

case (worst):

std::cout << "Worst Fit\n" << std::endl;

processes.sort_up();

break;

}

// loop through processes

for (std::vector::iterator current_process=processes.begin(); current_process!=processes.end(); ++current_process)

{

// dereference the current process

process_class& process = **current_process;

// initialise a flag

bool flag = false;

// for best and worst fit only, sort the partitions according to remaining bytes

switch(fit)

{

case (best): sort_up(); break;

case (worst): sort_down(); break;

}

// loop through partitions

for (std::vector::iterator current_partition=begin(); current_partition!=end(); ++current_partition)

{

// dereference the current partition

partition_class& partition = *current_partition;

// will the process fit within the current partition?

if (process.get_bytes() <= partition.get_bytes())

{

// yes!

partition.allocate (process);

flag = true;

break;

}

}

// unable to allocate the current process

if (!flag)

std::cout << process << " cannot be allocated!" << std::endl;

}

std::cout << std::endl;

}

void deallocate()

{

for (std::vector::iterator current_partition=begin(); current_partition!=end(); ++current_partition)

current_partition->deallocate_all();

}

// vector iterators and other helpers

std::vector::const_iterator begin() const { return (m_vect.begin()); }

std::vector::iterator begin() { return (m_vect.begin()); }

std::vector::const_iterator end() const { return (m_vect.end()); }

std::vector::iterator end() { return (m_vect.end()); }

std::vector::const_reverse_iterator rbegin() const { return (m_vect.rbegin()); }

std::vector::reverse_iterator rbegin() { return (m_vect.rbegin()); }

std::vector::const_reverse_iterator rend() const { return (m_vect.rend()); }

std::vector::reverse_iterator rend() { return (m_vect.rend()); }

unsigned size() const { return (m_vect.size()); }

void push_back (partition_class partition) { m_vect.push_back (partition); }

};

// insertion operator overload

std::ostream& operator<< (std::ostream& os, const partitions_class& partitions)

{

os << "Memory partitions: " << partitions.size() << '\n' << std::endl;

for (std::vector::const_iterator current_partition=partitions.begin();

current_partition!=partitions.end(); ++current_partition)

{

const partition_class& partition = *current_partition;

os << partition << std::endl;

}

return (os);

}

int main()

{

// seed the random number generator

srand ((unsigned) time (NULL));

// instantiate partitions and processes

partitions_class partitions;

processes_class processes;

// assign decreasing memory sizes to 5 partitions

unsigned memory = 8192;

for (unsigned partition=0; partition<5; ++partition)

partitions.push_back (partition_class (memory>>=1));

// assign decreasing memory sizes to 10 processes

memory = 4096;

for (unsigned proc=0; proc<10; ++proc)

processes.push_back (new process_class (memory>>=1));

// unsort (randomise) the partitions and processes

partitions.unsort();

processes.unsort();

// print them

std::cout << partitions << std::endl;

std::cout << processes << std::endl;

// exercise the algorithms

partitions.allocate (processes, first);

partitions.deallocate ();

partitions.allocate (processes, best);

partitions.deallocate ();

partitions.allocate (processes, worst);

partitions.deallocate ();

// tidy up

while (!processes.empty())

{

delete (processes.back());

processes.pop_back();

}

std::cout << std::endl;

}

Example output

Memory partitions: 5

Partition 5 ( 256 bytes)

Partition 3 (1024 bytes)

Partition 2 (2048 bytes)

Partition 4 ( 512 bytes)

Partition 1 (4096 bytes)

Processes: 10

Process 3 ( 512 bytes)

Process 6 ( 64 bytes)

Process 8 ( 16 bytes)

Process 2 (1024 bytes)

Process 10 ( 4 bytes)

Process 4 ( 256 bytes)

Process 7 ( 32 bytes)

Process 1 (2048 bytes)

Process 9 ( 8 bytes)

Process 5 ( 128 bytes)

First Fit

Process 3 ( 512 bytes) allocated to Partition 3 (1024 bytes) leaving 512 bytes free

Process 6 ( 64 bytes) allocated to Partition 5 ( 256 bytes) leaving 192 bytes free

Process 8 ( 16 bytes) allocated to Partition 5 ( 192 bytes) leaving 176 bytes free

Process 2 (1024 bytes) allocated to Partition 2 (2048 bytes) leaving 1024 bytes free

Process 10 ( 4 bytes) allocated to Partition 5 ( 176 bytes) leaving 172 bytes free

Process 4 ( 256 bytes) allocated to Partition 3 ( 512 bytes) leaving 256 bytes free

Process 7 ( 32 bytes) allocated to Partition 5 ( 172 bytes) leaving 140 bytes free

Process 1 (2048 bytes) allocated to Partition 1 (4096 bytes) leaving 2048 bytes free

Process 9 ( 8 bytes) allocated to Partition 5 ( 140 bytes) leaving 132 bytes free

Process 5 ( 128 bytes) allocated to Partition 5 ( 132 bytes) leaving 4 bytes free

Best Fit

Process 1 (2048 bytes) allocated to Partition 2 (2048 bytes) leaving 0 bytes free

Process 2 (1024 bytes) allocated to Partition 3 (1024 bytes) leaving 0 bytes free

Process 3 ( 512 bytes) allocated to Partition 4 ( 512 bytes) leaving 0 bytes free

Process 4 ( 256 bytes) allocated to Partition 5 ( 256 bytes) leaving 0 bytes free

Process 5 ( 128 bytes) allocated to Partition 1 (4096 bytes) leaving 3968 bytes free

Process 6 ( 64 bytes) allocated to Partition 1 (3968 bytes) leaving 3904 bytes free

Process 7 ( 32 bytes) allocated to Partition 1 (3904 bytes) leaving 3872 bytes free

Process 8 ( 16 bytes) allocated to Partition 1 (3872 bytes) leaving 3856 bytes free

Process 9 ( 8 bytes) allocated to Partition 1 (3856 bytes) leaving 3848 bytes free

Process 10 ( 4 bytes) allocated to Partition 1 (3848 bytes) leaving 3844 bytes free

Worst Fit

Process 10 ( 4 bytes) allocated to Partition 1 (4096 bytes) leaving 4092 bytes free

Process 9 ( 8 bytes) allocated to Partition 1 (4092 bytes) leaving 4084 bytes free

Process 8 ( 16 bytes) allocated to Partition 1 (4084 bytes) leaving 4068 bytes free

Process 7 ( 32 bytes) allocated to Partition 1 (4068 bytes) leaving 4036 bytes free

Process 6 ( 64 bytes) allocated to Partition 1 (4036 bytes) leaving 3972 bytes free

Process 5 ( 128 bytes) allocated to Partition 1 (3972 bytes) leaving 3844 bytes free

Process 4 ( 256 bytes) allocated to Partition 1 (3844 bytes) leaving 3588 bytes free

Process 3 ( 512 bytes) allocated to Partition 1 (3588 bytes) leaving 3076 bytes free

Process 2 (1024 bytes) allocated to Partition 1 (3076 bytes) leaving 2052 bytes free

Process 1 (2048 bytes) allocated to Partition 1 (2052 bytes) leaving 4 bytes free