Memory allocation algorithm

Experiment 4 memory allocation algorithm

1, Experimental purpose

Write a program to simulate the allocation of memory;
Through experiments, we can understand how to realize the allocation and recovery of main memory space under the dynamic partition management mode;

2, Background knowledge

A good computer system should not only have a sufficient container, high access speed, stable and reliable main memory, but also be able to reasonably allocate and use these storage spaces;
When the user applies for the main memory space, n the storage management must analyze the usage of the main memory space according to certain policies * * (first adaptation, best adaptation, first cycle adaptation) * * according to the requirements of the applicant, and find out enough free areas to allocate to the applicant.
When the job withdraws or actively returns the main memory resources, the storage management shall recover the main memory space occupied by the job or return part of the main memory space.
The realization of main memory allocation and recovery is related to the management mode of main memory.

3, Experimental content

In the dynamic partition management mode, different allocation algorithms are used to realize main memory allocation and recycling.
Add test cases to verify the correctness of the program:
- Reassign a job, assuming that the size of job 4 is 6k;
- Delete an assigned job (job 3);
- Delete an assigned job (job 2);
It is necessary to display or print the initial value of the idle area description table and the change after each allocation or recycling.

4, Experimental steps

The variable partition method divides the partitions according to the main memory space required by the job. When a job is to be loaded, check whether there is enough free space according to the main memory required by the job. If so, divide a partition according to the required amount and allocate it to the job; If not, the job cannot be loaded. With the loading and evacuation of jobs, the main memory space is divided into many partitions. Some partitions are occupied by jobs, while others are idle. For example:
In order to explain which areas are free and can be used to load new jobs, there must be a description table of empty areas:

Where, starting address -- indicates the starting address of the main memory of a free area.
- Length - indicates the length of a continuous free area starting from the starting address;
- State - there are two states. One is the "unallocated" state, which indicates that the corresponding area of a certain length indicated by the starting address is a free area; The other is the "empty table entry" status, which means that the corresponding registration item in the table is blank and can be used to register a new free area (for example, after the operation is evacuated, the area occupied by it becomes a free area. Find a "empty table entry" column to register the address and length of the return area and modify the status). Due to the variable number of partitions, there should be an appropriate number of registration columns with "empty table item" in the description table of free area, otherwise the table "overflows" and cannot be registered.
- The above description registration form is filled in after the main memory area occupied by the three jobs loaded according to the example in prompt (1).
When a new job requires loading into main memory, you must check the free area description table to find a large enough free area. Sometimes the found free area may be larger than the job demand. At this time, the original free area should be divided into two parts: one part is allocated to the job; The other part becomes a smaller free area. In order to minimize the "fragmentation" caused by segmentation, when the job request is loaded, the free area of the low address part of the main memory shall be used as much as possible, and the high address part shall be saved as much as possible with a large continuous free area, so as to facilitate the loading of large-scale jobs. Therefore, in the free area description table, each free area is registered according to its address order, that is, the starting address of each subsequent free area is always larger than the former. In order to facilitate searching, you can also make the table "compact". Always focus the "empty table entry" column on the back of the table.
The main memory space is allocated by the first adaptation algorithm or the cyclic first adaptation algorithm or the best adaptation algorithm. Because this experiment simulates the allocation of main memory, when the main memory area is allocated to the job, the loader loading job is not actually started, but the output "allocation" is used instead. (that is, output the current free area description table and its memory allocation table).
When a job is evacuated after execution, the area occupied by the job shall be returned. If the returned area is adjacent to other free areas, it shall be combined into a larger free area and registered in the free area description table. For example, in the case listed in prompt (1), if job 2 withdraws and returns the occupied main memory area, it shall form a large free area together with the upper and lower adjacent free areas and register it in the free area description table.
Please design the program of main memory allocation and recycling according to the first adaptation algorithm or cyclic first adaptation algorithm or best adaptation algorithm. Then, according to the assumption in (1), three jobs have been loaded into the main memory and two free areas are formed to determine the initial value of the idle description table. There is an existing job 4 requiring 6K main memory to apply for loading into main memory; Then evacuate from operation 3; Re operation 2 evacuation. Please allocate and recycle the main memory for them, and display or print the initial value of the free area description table and the changes after each allocation or recycling.

5, Test data file format

Print the initial values and running results when the program is running. The requirements are as follows:

Print the initial status of the idle area description table, the application amount of job 4 and the status of the idle area description table after allocation for job 4;
Then print the return amount of job 3 and job 2 and the description table of the free area occupied by job 3 and job 2 in main memory.

6, Experimental environment preparation

A computer running Windows operating system;
Clion is installed and the MinGW environment is configured

7, Experimental records

Data structure description:

id is used to record the job number, os or empty partition is represented by 0;
begin indicates the starting address of the partition;
Length indicates the length of the partition;
State indicates the state of the partition;
In order to facilitate the output, the output stream function is constructed;

struct area{
    int id;
    int begin;
    int length;
    string state;

    area(int id, int begin, int length, const string &state) : id(id), begin(begin), length(length), state(state) {}

    area() {}

    friend ostream &operator<<(ostream &os, const area &area) {
        os << setw(10) << area.begin << setw(10) << area.length << setw(10) << area.state;
        return os;
    }
};

Initial condition of Construction:

void init(){
    area os(0,0, 5, "os");
    area work1(1,5, 5, "Assignment 1");
    area work3(3, 10, 4, "Assignment 3");
    area empty1(0, 14, 12, "Free area");
    area work2(2, 26, 6, "Assignment 2");
    area empty2(0, 32, 96, "Free area");
    Memory_allocation_table.push_back(os);
    Memory_allocation_table.push_back(work1);
    Memory_allocation_table.push_back(work3);
    Memory_allocation_table.push_back(empty1);
    Memory_allocation_table.push_back(work2);
    Memory_allocation_table.push_back(empty2);
}

First adaptation algorithm:

string insert_word_first(int size){//First adaptation algorithm
    string state_code = "allocation failed";
    for(list<area>::iterator iter = Memory_allocation_table.begin(); iter != Memory_allocation_table.end(); iter++){
        if(iter->state == "Free area" || iter->state == "Empty table item"){
            //Empty area
            if(iter->length > size){
                //Extra space
                area next(0, iter->begin + size, iter->length - size, "Free area");
                iter->id = count;
                iter->length = size;
                iter->state = "task" + to_string(count++);
                Memory_allocation_table.insert(++iter, next);
                iter--;
                state_code == "Allocation succeeded";
                break;
            }
            else if(iter->length == size){
                //The space is just right
                iter->id = count;
                iter->state = "task" + to_string(count++);
                state_code == "Allocation succeeded";
                break;
            }
        }
    }
    return state_code;
}

Best fit algorithm:

string insert_word_best(int size){//Best fit algorithm
    string state_code = "allocation failed";
    list<area>::iterator best = Memory_allocation_table.begin();
    int bestsize = 0;
    for(list<area>::iterator iter = Memory_allocation_table.begin(); iter != Memory_allocation_table.end(); iter++){
        if(iter->state == "Free area" || iter->state == "Empty table item"){
            //Empty area
            if(iter->length >= size){
                //Enough space
                if(iter->length - size < bestsize - size || bestsize == 0){
                    //Better
                    best = iter;
                    bestsize = iter->length;
                }
            }
        }
    }
    if(best->length > size){
        //Extra space
        area next(0, best->begin + size, best->length - size, "Free area");
        best->id = count;
        best->length = size;
        best->state = "task" + to_string(count++);
        Memory_allocation_table.insert(++best, next);
        state_code == "Allocation succeeded";
    }
    else if(best->length == size){
        //The space is just right
        best->id = count;
        best->state = "task" + to_string(count++);
        state_code == "Allocation succeeded";
    }
    return state_code;
}

Cyclic first adaptation algorithm

string insert_word_next_first(int size){//Cyclic first adaptation algorithm
    string state_code = "allocation failed";
    list<area>::iterator iter;
    for(iter = pre; iter != Memory_allocation_table.end(); iter++){
        if(iter->state == "Free area" || iter->state == "Empty table item"){
            //Empty area
            if(iter->length > size){
                //Extra space
                area next(0, iter->begin + size, iter->length - size, "Free area");
                iter->id = count;
                iter->length = size;
                iter->state = "task" + to_string(count++);
                Memory_allocation_table.insert(++iter, next);
                iter--;
                state_code == "Allocation succeeded";
                pre = iter;
                break;
            }
            else if(iter->length == size){
                //The space is just right
                iter->id = count;
                iter->state = "task" + to_string(count++);
                state_code == "Allocation succeeded";
                pre = iter;
                break;
            }
        }
    }
    if(state_code == "allocation failed"){
        for(iter = Memory_allocation_table.begin(); iter != pre; iter++){
            //Start from scratch
            if(iter->state == "Free area" || iter->state == "Empty table item"){
                //Empty area
                if(iter->length > size){
                    //Extra space
                    area next(0, iter->begin + size, iter->length - size, "Free area");
                    iter->id = count;
                    iter->length = size;
                    iter->state = "task" + to_string(count++);
                    Memory_allocation_table.insert(++iter, next);
                    iter--;
                    state_code == "Allocation succeeded";
                    pre = iter;
                    break;
                }
                else if(iter->length == size){
                    //The space is just right
                    iter->id = count;
                    iter->state = "task" + to_string(count++);
                    state_code == "Allocation succeeded";
                    pre = iter;
                    break;
                }
            }
        }
    }
    return state_code;
}

Remove job

void remove(int workid){
    for(list<area>::iterator iter = Memory_allocation_table.begin(); iter != Memory_allocation_table.end(); iter++){
        if(iter->id == workid){
            list<area>::iterator iter_front = --iter;
            iter++;
            list<area>::iterator iter_back = ++iter;
            iter--;
            //Both front and back are empty
            if((iter_front->state == "Free area" || iter_front->state == "Empty table item") && (iter_back->state == "Free area" || iter_back->state == "Empty table item")){
                iter_front->length = iter_front->length + iter->length + iter_back->length;
                iter_front->state = "Empty table item";
                Memory_allocation_table.erase(iter);
                Memory_allocation_table.erase(iter_back);
            }
            //Front empty
            else if(iter_front->state == "Free area" || iter_front->state == "Empty table item"){
                iter_front->length = iter_front->length + iter->length;
                iter_front->state = "Empty table item";
                Memory_allocation_table.erase(iter);
            }
            //Back space
            else if(iter_back->state == "Free area" || iter_back->state == "Empty table item"){
                iter->length = iter->length + iter_back->length;
                iter->state = "Empty table item";
                Memory_allocation_table.erase(iter_back);
            }
            //Neither front nor back is empty
            else{
                iter->state = "Empty table item";
            }
            break;
        }
    }
}

Running results (the results are too long to be displayed in pictures and copied directly):
1. First adaptation algorithm:
  
  First adaptation algorithm:
  Initialization table:
  Address length status
  0 5 os
  5 operation 1
  10.4 operation 3
  14.12 free area
  26 6 operation 2
  32 96 free area
  
  Assign job 4 (6k):
  Address length status
  0 5 os
  5 operation 1
  10.4 operation 3
  14 6 operation 4
  20.6 free area
  26 6 operation 2
  32 96 free area
  
  Remove job 3:
  Address length status
  0 5 os
  5 operation 1
  10.4 empty table items
  14 6 operation 4
  20.6 free area
  26 6 operation 2
  32 96 free area
  
  Remove job 2:
  Address length status
  0 5 os
  5 operation 1
  10.4 empty table items
  14 6 operation 4
  20 108 empty table items
  
  The process has ended with exit code 0
2. Best fit algorithm:
  
  Best fit algorithm:
  Initialization table:
  Address length status
  0 5 os
  5 operation 1
  10.4 operation 3
  14.12 free area
  26 6 operation 2
  32 96 free area
  
  Assign job 4 (13k):
  Address length status
  0 5 os
  5 operation 1
  10.4 operation 3
  14.12 free area
  26 6 operation 2
  32 13 operation 4
  45 83 free area
  
  Remove job 3:
  Address length status
  0 5 os
  5 operation 1
  10.16 empty table items
  26 6 operation 2
  32 13 operation 4
  45 83 free area
  
  Remove job 2:
  Address length status
  0 5 os
  5 operation 1
  10.22 empty table items
  32 13 operation 4
  45 83 free area
  
  The process has ended with exit code 0
3. Cyclic first adaptation algorithm
  
  Loop first adaptation algorithm:
  Initialization table:
  Address length status
  0 5 os
  5 operation 1
  10.4 operation 3
  14.12 free area
  26 6 operation 2
  32 96 free area
  
  Assign job 4 (6k):
  Address length status
  0 5 os
  5 operation 1
  10.4 operation 3
  14 6 operation 4
  20.6 free area
  26 6 operation 2
  32 96 free area
  
  Remove job 3:
  Address length status
  0 5 os
  5 operation 1
  10.4 empty table items
  14 6 operation 4
  20.6 free area
  26 6 operation 2
  32 96 free area
  
  Remove job 2:
  Address length status
  0 5 os
  5 operation 1
  10.4 empty table items
  14 6 operation 4
  20 108 empty table items
  
  The process has ended with exit code 0

8, Experiment complete source code

#include <iostream>
#include <list>
#include <string>
#include <iomanip>

using namespace std;
struct area{
    int id;
    int begin;
    int length;
    string state;

    area(int id, int begin, int length, const string &state) : id(id), begin(begin), length(length), state(state) {}

    area() {}

    friend ostream &operator<<(ostream &os, const area &area) {
        os << setw(10) << area.begin << setw(10) << area.length << setw(10) << area.state;
        return os;
    }
};
int count = 4;//For job count
list<area> Memory_allocation_table;
list<area>::iterator pre = Memory_allocation_table.begin();
string insert_word_first(int size){//First adaptation algorithm
    string state_code = "allocation failed";
    for(list<area>::iterator iter = Memory_allocation_table.begin(); iter != Memory_allocation_table.end(); iter++){
        if(iter->state == "Free area" || iter->state == "Empty table item"){
            //Empty area
            if(iter->length > size){
                //Extra space
                area next(0, iter->begin + size, iter->length - size, "Free area");
                iter->id = count;
                iter->length = size;
                iter->state = "task" + to_string(count++);
                Memory_allocation_table.insert(++iter, next);
                iter--;
                state_code == "Allocation succeeded";
                break;
            }
            else if(iter->length == size){
                //The space is just right
                iter->id = count;
                iter->state = "task" + to_string(count++);
                state_code == "Allocation succeeded";
                break;
            }
        }
    }
    return state_code;
}
string insert_word_best(int size){//Best fit algorithm
    string state_code = "allocation failed";
    list<area>::iterator best = Memory_allocation_table.begin();
    int bestsize = 0;
    for(list<area>::iterator iter = Memory_allocation_table.begin(); iter != Memory_allocation_table.end(); iter++){
        if(iter->state == "Free area" || iter->state == "Empty table item"){
            //Empty area
            if(iter->length >= size){
                //Enough space
                if(iter->length - size < bestsize - size || bestsize == 0){
                    //Better
                    best = iter;
                    bestsize = iter->length;
                }
            }
        }
    }
    if(best->length > size){
        //Extra space
        area next(0, best->begin + size, best->length - size, "Free area");
        best->id = count;
        best->length = size;
        best->state = "task" + to_string(count++);
        Memory_allocation_table.insert(++best, next);
        state_code == "Allocation succeeded";
    }
    else if(best->length == size){
        //The space is just right
        best->id = count;
        best->state = "task" + to_string(count++);
        state_code == "Allocation succeeded";
    }
    return state_code;
}
string insert_word_next_first(int size){//Cyclic first adaptation algorithm
    string state_code = "allocation failed";
    list<area>::iterator iter;
    for(iter = pre; iter != Memory_allocation_table.end(); iter++){
        if(iter->state == "Free area" || iter->state == "Empty table item"){
            //Empty area
            if(iter->length > size){
                //Extra space
                area next(0, iter->begin + size, iter->length - size, "Free area");
                iter->id = count;
                iter->length = size;
                iter->state = "task" + to_string(count++);
                Memory_allocation_table.insert(++iter, next);
                iter--;
                state_code == "Allocation succeeded";
                pre = iter;
                break;
            }
            else if(iter->length == size){
                //The space is just right
                iter->id = count;
                iter->state = "task" + to_string(count++);
                state_code == "Allocation succeeded";
                pre = iter;
                break;
            }
        }
    }
    if(state_code == "allocation failed"){
        for(iter = Memory_allocation_table.begin(); iter != pre; iter++){
            //Start from scratch
            if(iter->state == "Free area" || iter->state == "Empty table item"){
                //Empty area
                if(iter->length > size){
                    //Extra space
                    area next(0, iter->begin + size, iter->length - size, "Free area");
                    iter->id = count;
                    iter->length = size;
                    iter->state = "task" + to_string(count++);
                    Memory_allocation_table.insert(++iter, next);
                    iter--;
                    state_code == "Allocation succeeded";
                    pre = iter;
                    break;
                }
                else if(iter->length == size){
                    //The space is just right
                    iter->id = count;
                    iter->state = "task" + to_string(count++);
                    state_code == "Allocation succeeded";
                    pre = iter;
                    break;
                }
            }
        }
    }
    return state_code;
}
void remove(int workid){
    for(list<area>::iterator iter = Memory_allocation_table.begin(); iter != Memory_allocation_table.end(); iter++){
        if(iter->id == workid){
            list<area>::iterator iter_front = --iter;
            iter++;
            list<area>::iterator iter_back = ++iter;
            iter--;
            //Both front and back are empty
            if((iter_front->state == "Free area" || iter_front->state == "Empty table item") && (iter_back->state == "Free area" || iter_back->state == "Empty table item")){
                iter_front->length = iter_front->length + iter->length + iter_back->length;
                iter_front->state = "Empty table item";
                Memory_allocation_table.erase(iter);
                Memory_allocation_table.erase(iter_back);
            }
            //Front empty
            else if(iter_front->state == "Free area" || iter_front->state == "Empty table item"){
                iter_front->length = iter_front->length + iter->length;
                iter_front->state = "Empty table item";
                Memory_allocation_table.erase(iter);
            }
            //Back space
            else if(iter_back->state == "Free area" || iter_back->state == "Empty table item"){
                iter->length = iter->length + iter_back->length;
                iter->state = "Empty table item";
                Memory_allocation_table.erase(iter_back);
            }
            //Neither front nor back is empty
            else{
                iter->state = "Empty table item";
            }
            break;
        }
    }
}
void init(){
    area os(0,0, 5, "os");
    area work1(1,5, 5, "Assignment 1");
    area work3(3, 10, 4, "Assignment 3");
    area empty1(0, 14, 12, "Free area");
    area work2(2, 26, 6, "Assignment 2");
    area empty2(0, 32, 96, "Free area");
    Memory_allocation_table.push_back(os);
    Memory_allocation_table.push_back(work1);
    Memory_allocation_table.push_back(work3);
    Memory_allocation_table.push_back(empty1);
    Memory_allocation_table.push_back(work2);
    Memory_allocation_table.push_back(empty2);
}
void printMemorytable(){
    cout << setw(10) << "Starting address" << setw(10) << "length" << setw(10) << "state" << endl;
    for(list<area>::iterator iter = Memory_allocation_table.begin(); iter != Memory_allocation_table.end(); iter++){
        cout  << *iter << endl;
    }
    cout << endl;
}
int main() {
//    Cout < < "first adaptation algorithm: \ n";
//    init();
//    Cout < < "initialization table: \ n";
//    printMemorytable();
//
//    Cout < < "assign job 4 (6k): \ n";
//    insert_word_first(6);
//    printMemorytable();
//
//    Cout < < "remove job 3: \n";
//    remove(3);
//    printMemorytable();
//
//    Cout < < "remove job 2: \n";
//    remove(2);
//    printMemorytable();
//    cout << "-----------------\n";

    cout << "Best fit algorithm: \n";
    init();
    cout << "Initialization table: \n";
    printMemorytable();

    cout << "Assign job 4 (6) k): \n";
    insert_word_best(13);
    printMemorytable();

    cout << "Remove job 3: \n";
    remove(3);
    printMemorytable();

    cout << "Remove job 2: \n";
    remove(2);
    printMemorytable();
//    cout << "-----------------\n";

//    Cout < < "loop first adaptation algorithm: \ n";
//    init();
//    Cout < < "initialization table: \ n";
//    printMemorytable();
//
//    Cout < < "assign job 4 (6k): \ n";
//    insert_word_next_first(6);
//    printMemorytable();
//
//    Cout < < "remove job 3: \n";
//    remove(3);
//    printMemorytable();
//
//    Cout < < "remove job 2: \n";
//    remove(2);
//    printMemorytable();
    return 0;
}

Keywords: C++ Algorithm Operating System

Added by grandadevans on Wed, 01 Dec 2021 13:53:42 +0200

Programming VIP