Provide solution for lab using best fit algorithm

Lab5 Explanation:

This lab is about simulation of different memory allocation techniques we learned in week4 such as (first fit, next fit and other techniques).

Select and simulate one of these techniques for lab4 and select another technique for lab5.


Memory is 256K.

Each unit is 2K. Therefore, there are 128 units that can be allocated to different processes.

A process may request between 3 and 10 units of memory

Number of requests: 10,000

Based on the above assumptions, three constants are defined in the code as follows:

#define NUM_REQUESTS 10000

#define MIN_NUM_UNITS 3

#define MAX_NUM_UNITS 10


A class is defined called Node which has two member variables called process_id and num_units.

Also a list of nodes needs to be defined.

At start all the units are available. We can use -1 as the process_id to represent availability (hole).  The following diagram shows the list at the start where the 128 units is available for allocation. Note however, a process can only ask for up to 10 units of allocation. 






The program uses a random generator function to randomly select between allocation and deallocations.   The deallocations can happen if there is at least one process that memory is allocated for it.

You can keep track of the list of processes that the memory is currently being allocated to them.  Then during the deallocation, you may randomly select one process from this list and deallocate memory for that process.


Each allocation or deallocation is considered as one request.  You must also keep track of number of requests since we want to have 10,000 requests in this simulation.


Each process may request 3 to 10 units of memory. Therefore, number of unit requested by each process is a random number in the range 3 to 10.  You may use a variable called nextProcessId and at the end of each allocation request, you may increment that variable for the next process ID request.


You may use a for loop to check the list to see if there is a hole big enough for the given request as follows:

for (list<Node>::iterator cur = memory_list.begin(); cur != memory_list.end(); ++cur) {

As you check each node, if a node has a process id of -1 and the size of it is equal or greater than the requested number of units then allocation is possible.

You need to modify the list by inserting a node with the given process ID and given number of units requested.  


If process 0 requests 5 units, then the above list becomes:





Next time we do an allocation, we must traverse the list more to find a free location.


As we do deallocations, we will get more than one hole.  If the size of a hole is 1 or2 units, then we have fragments.


You can also define two constants:

#define HOLE_PROCESS_ID -1



There are three performance parameters that your simulation should calculate for the chosen two techniques: average number of external fragments, average allocation time in terms of the average number of nodes traversed in allocation, and the percentage of times an allocation request is denied.


Each time allocation is successful, the number of traversals is returned. You should have a variable to keep track of the total number of traversals. Also you should have a variable to keep track of the number of allocation successes.  These two values can be used to calculate the average of number of nodes traversed. In addition, when there is a successful allocation, your code should find the number of fragments. A variable should keep track of total fragments.


You will submit four separate files to the dropbox for Week 4:

  1. C or C++ program (source code)
  2. Executable file (object)
  3. Instructions to execute the program
  4. Analysis of the results for the chosen allocation/deallocation technique

// ECET360 – iLab 4 skeleton

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iomanip>
#include <list>
#include <vector>
using namespace std;

//Define a class called Node as described in the explanation file

// Allocates num_units units of memory to a process whose id is process_id.
// If successful, it returns the number of nodes traversed in the linked list.
// Otherwise, it returns -1.
// This memory allocator implements FIRST FIT.
int allocate_mem(int process_id, int num_units)
    // TODO: Implement
    return -1;

// Deallocates the memory allocated to the process whose id is process_id.
// It returns 1, if successful, otherwise -1.
int deallocate_mem(int process_id)
    // TODO: Implement
    return -1;

// returns the number of holes (fragments of sizes 1 or 2 units).
int fragment_count()
    // TODO: Implement
    return 0;

#define NUM_REQUESTS 10000
#define MIN_NUM_UNITS 3
#define MAX_NUM_UNITS 10

// The process list is used to track processes with currently allocated memory.
static vector<int> process_list;
static int next_process_id = 0;

// Statistics
static int total_fragments = 0;
static int total_traversals = 0;
static int num_alloc_successes = 0;
static int num_alloc_failures = 0;
static int num_dealloc_successes = 0;

static void print_stats()
    double avg_fragments;   
    double avg_traversals; 
    double denied_percent;
    int num_request_successes = num_alloc_successes + num_dealloc_successes;
    int num_alloc_attempts = num_alloc_successes + num_alloc_failures;

    if (num_request_successes != 0) {
        avg_fragments = (double)total_fragments / (double)num_request_successes;
    } else {
        avg_fragments = 0.0;

    if (num_alloc_successes != 0) {
        avg_traversals = (double)total_traversals / (double)num_alloc_successes;
    } else {
        avg_traversals = 0.0;

    if (num_alloc_attempts != 0) {
        denied_percent = (double)num_alloc_failures * 100.0 /
    } else {
        denied_percent = 0.0;

    cout << “Main Memory Allocation” << endl
         << “———————-” << endl
         << “average number of external fragments = ” << avg_fragments << endl
         << “average allocation time = ” << avg_traversals << endl
         << “percentage of allocation denials = ” << denied_percent << endl;

int main(int argc, char* argv[])
    int i;
    int rand_process_index;
    int rand_num_units;
    int traversals;
    int requests_left = NUM_REQUESTS;

    // Seed random number generator. */

    // Loop until all requests have been performed.
    while (requests_left != 0) {

        // Randomly choose to allocate or deallocate (unless deallocation is impossible)
        if ((process_list.size() == 0) || (rand() % 2)) {
            // Allocate

        } else {
            // Deallocate

            // Randomly choose a process to deallocate
                // Replace the process with the process at the end of the list.
                // Doing this is a lot more efficient than just removing the process since
                // the process list is a vector. If we just removed from the middle of the list
                // the tail end of the list would have to be moved.

    return EXIT_SUCCESS;