Реализация всех методов распределения разделов в управлении памятью

Опубликовано: 6 Января, 2022

Предварительное условие: методы распределения разделов в управлении памятью
При распределении разделов, когда имеется более одного раздела, свободно доступных для размещения запроса процесса, необходимо выбрать раздел. Чтобы выбрать конкретный раздел, необходим метод распределения разделов. Метод распределения разделов считается лучшим, если он позволяет избежать внутренней фрагментации.

Рассмотрим следующие данные для процесса:

№ процесса	Размер процесса
1	88
2	192
3	277
4	365
5	489

Рассмотрим следующие данные для слотов памяти:

Номер блока памяти.	Размер блока памяти
1	400
2	500
3	300
4	200
5	100

Ниже представлены различные схемы распределения разделов с их реализацией с учетом приведенных выше данных.

1. Первая посадка

Этот метод хранит список свободных / занятых заданий, упорядоченный по расположению памяти, от низкого до высокого порядка памяти. В этом методе первое задание запрашивает первую доступную память с пространством, превышающим или равным ее размеру. Операционная система не ищет подходящий раздел, а просто распределяет задание на ближайший доступный раздел памяти достаточного размера.

Ниже представлена реализация алгоритма первого подбора:

 // C++ program for the implementation
 // of the First Fit algorithm
 #include <iostream>
 #include <queue>
 #include <vector>
 using namespace std;
 
// Process Class
 class process {
 public :
    // Size & number of process
    size_t size;
    pid_t no;
 };
 
// Memory Class
 class memory {
 public :
    size_t size;
 
    // Number of memory & queue of space
    // occupied by process
    pid_t no;
    queue<process> space_occupied;
 
    // Function to push process in a block
    void push( const process p)
    {
        if (p.size <= size) {
            space_occupied.push(p);
            size -= p.size;
        }
    }
 
    // Function to pop and return the
    // process from the block
    process pop()
    {
        process p;
 
        // If space occupied is empty
        if (!space_occupied.empty()) {
            p = space_occupied.front();
            space_occupied.pop();
            size += p.size;
            return p;
        }
    }
 
    // Function to check if block is
    // completely empty
    bool empty()
    {
        return space_occupied.empty();
    }
 };
 
// Function to get data of processess
 // allocated using first fit
 vector<memory> first_fit(vector<memory> memory_blocks,
                         queue<process> processess)
 {
    int i = 0;
    bool done, done1;
    memory na;
    na.no = -10;
    while (!processess.empty()) {
        done = 0;
        for (i = 0; i < memory_blocks.size(); i++) {
            done1 = 0;
            if (memory_blocks.at(i).size
                >= processess.front().size) {
                memory_blocks.at(i).push(processess.front());
                done = 1;
                done1 = 1;
                break ;
            }
        }
 
        // If process is done
        if (done == 0 && done1 == 0) {
            na.size += processess.front().size;
            na.push(processess.front());
        }
 
        // pop the process
        processess.pop();
    }
    if (!na.space_occupied.empty())
        memory_blocks.push_back(na);
    return memory_blocks;
 }
 
// Function to display the allocation
 // of all processess
 void display(vector<memory> memory_blocks)
 {
    int i = 0, temp = 0;
    process p;
    cout << "+-------------+--------------+--------------+"
         << endl;
    cout << "| Process no. | Process size | Memory block |"
         << endl;
    cout << "+-------------+--------------+--------------+"
         << endl;
 
    // Traverse memory blocks size
    for (i = 0; i < memory_blocks.size(); i++) {
 
        // While memory block size is not empty
        while (!memory_blocks.at(i).empty()) {
            p = memory_blocks.at(i).pop();
            temp = to_string(p.no).length();
            cout << "|" << string(7 - temp / 2 - temp % 2, ' ' )
                 << p.no << string(6 - temp / 2, ' ' )
                 << "|" ;
 
            temp = to_string(p.size).length();
            cout << string(7 - temp / 2 - temp % 2, ' ' )
                 << p.size
                 << string(7 - temp / 2, ' ' ) << "|" ;
 
            temp = to_string(memory_blocks.at(i).no).length();
            cout << string(7 - temp / 2 - temp % 2, ' ' );
 
            // If memory blocks is assigned
            if (memory_blocks.at(i).no != -10) {
                cout << memory_blocks.at(i).no;
            }
 
            // Else memory blocks is assigned
            else {
                cout << "N/A" ;
            }
            cout << string(7 - temp / 2, ' ' )
                 << "|" << endl;
        }
    }
    cout << "+-------------+--------------+--------------+"
         << endl;
 }
 
// Driver Code
 int main()
 {
    // Declare memory blocks
    vector<memory> memory_blocks(5);
 
    // Declare first fit blocks
    vector<memory> first_fit_blocks;
 
    // Declare queue of all processess
    queue<process> processess;
    process temp;
 
    // Set sample data
    memory_blocks[0].no = 1;
    memory_blocks[0].size = 400;
 
    memory_blocks[1].no = 2;
    memory_blocks[1].size = 500;
 
    memory_blocks[2].no = 3;
    memory_blocks[2].size = 300;
 
    memory_blocks[3].no = 4;
    memory_blocks[3].size = 200;
 
    memory_blocks[4].no = 5;
    memory_blocks[4].size = 100;
 
    temp.no = 1;
    temp.size = 88;
 
    // Push the process
    processess.push(temp);
 
    temp.no = 2;
    temp.size = 192;
 
    // Push the process
    processess.push(temp);
 
    temp.no = 3;
    temp.size = 277;
 
    // Push the process
    processess.push(temp);
 
    temp.no = 4;
    temp.size = 365;
 
    // Push the process
    processess.push(temp);
 
    temp.no = 5;
    temp.size = 489;
 
    // Push the process
    processess.push(temp);
 
    // Get the data
    first_fit_blocks = first_fit(memory_blocks, processess);
 
    // Display the data
    display(first_fit_blocks);
    memory_blocks.clear();
    memory_blocks.shrink_to_fit();
    first_fit_blocks.clear();
    first_fit_blocks.shrink_to_fit();
    return 0;
 }

Выход:

+ ------------- + -------------- + -------------- +
| № процесса | Размер процесса | Блок памяти |
+ ------------- + -------------- + -------------- +
| 1 | 88 | 1 |
| 2 | 192 | 1 |
| 3 | 277 | 2 |
| 4 | 365 | N / A |
| 5 | 489 | N / A |
+ ------------- + -------------- + -------------- +

2. Next Fit

Следующая подгонка - это модифицированная версия «первой подгонки». Он начинается с первого подходящего для поиска свободного раздела, но при следующем вызове он начинает поиск с того места, где он остановился, а не с начала. Эта политика использует перемещающийся указатель. Указатель перемещается по цепочке памяти для поиска следующего соответствия. Это помогает избежать использования памяти всегда с начала (начала) свободной цепочки блоков.

Ниже представлена реализация алгоритма Next Fit:

 // C++ program for the implementation
 // of the Next Fit algorithm
 #include <iostream>
 #include <queue>
 #include <vector>
 using namespace std;
 
// Process Class
 class process {
 public :
    // Size & number of process
    size_t size;
    pid_t no;
 };
 
// Memory Class
 class memory {
 public :
    size_t size;
 
    // Number of memory & queue of space
    // occupied by process
    pid_t no;
    queue<process> space_occupied;
 
    // Function to push process in a block
    void push( const process p)
    {
        if (p.size <= size) {
            space_occupied.push(p);
            size -= p.size;
        }
    }
 
    // Function to pop and return the
    // process from the block
    process pop()
    {
        process p;
 
        // If space occupied is empty
        if (!space_occupied.empty()) {
            p = space_occupied.front();
            space_occupied.pop();
            size += p.size;
            return p;
        }
    }
 
    // Function to check if block is
    // completely empty
    bool empty()
    {
        return space_occupied.empty();
    }
 };
 
// Function to get data of processess
 // allocated using Next Fit
 vector<memory> next_fit(vector<memory> memory_blocks,
                        queue<process> processess)
 {
    int i = 0;
    bool done, done1;
    memory na;
    na.no = -10;
 
    // Loop till process is empty
    while (!processess.empty()) {
        done1 = 0;
 
        // Traverse memory_blocks
        for (i = 0; i < memory_blocks.size(); i++) {
            done = 0;
 
            // If process is not empty
            if (!processess.empty() && memory_blocks.at(i).size >= processess.front().size) {
                memory_blocks.at(i).push(processess.front());
                done = 1;
                done1 = 1;
                processess.pop();
            }
        }
        if (!processess.empty() && done == 0 && done1 == 0) {
            na.size += processess.front().size;
            na.push(processess.front());
            processess.pop();
        }
    }
 
    // If space is not occupied push
    // the memory_blocks na
    if (!na.space_occupied.empty()) {
        memory_blocks.push_back(na);
    }
 
    return memory_blocks;
 }
 
// Function to display the allocation
 // of all processess
 void display(vector<memory> memory_blocks)
 {
    int i = 0, temp = 0;
    process p;
    cout << "+-------------+--------------+--------------+"
         << endl;
    cout << "| Process no. | Process size | Memory block |"
         << endl;
    cout << "+-------------+--------------+--------------+"
         << endl;
 
    // Traverse memory blocks size
    for (i = 0; i < memory_blocks.size(); i++) {
 
        // While memory block size is not empty
        while (!memory_blocks.at(i).empty()) {
            p = memory_blocks.at(i).pop();
            temp = to_string(p.no).length();
            cout << "|" << string(7 - temp / 2 - temp % 2, ' ' )
                 << p.no << string(6 - temp / 2, ' ' )
                 << "|" ;
 
            temp = to_string(p.size).length();
            cout << string(7 - temp / 2 - temp % 2, ' ' )
                 << p.size
                 << string(7 - temp / 2, ' ' ) << "|" ;
 
            temp = to_string(memory_blocks.at(i).no).length();
            cout << string(7 - temp / 2 - temp % 2, ' ' );
 
            // If memory blocks is assigned
            if (memory_blocks.at(i).no != -10) {
                cout << memory_blocks.at(i).no;
            }
 
            // Else memory blocks is assigned
            else {
                cout << "N/A" ;
            }
            cout << string(7 - temp / 2, ' ' )
                 << "|" << endl;
        }
    }
    cout << "+-------------+--------------+--------------+"
         << endl;
 }
 
// Driver Code
 int main()
 {
    // Declare memory blocks
    vector<memory> memory_blocks(5);
 
    // Declare next fit blocks
    vector<memory> next_fit_blocks;
 
    // Declare queue of all processess
    queue<process> processess;
    process temp;
 
    // Set sample data
    memory_blocks[0].no = 1;
    memory_blocks[0].size = 400;
 
    memory_blocks[1].no = 2;
    memory_blocks[1].size = 500;
 
    memory_blocks[2].no = 3;
    memory_blocks[2].size = 300;
 
    memory_blocks[3].no = 4;
    memory_blocks[3].size = 200;
 
    memory_blocks[4].no = 5;
    memory_blocks[4].size = 100;
 
    temp.no = 1;
    temp.size = 88;
 
    // Push the process
    processess.push(temp);
    temp.no = 2;
    temp.size = 192;
 
    // Push the process
    processess.push(temp);
    temp.no = 3;
    temp.size = 277;
 
    // Push the process
    processess.push(temp);
    temp.no = 4;
    temp.size = 365;
 
    // Push the process
    processess.push(temp);
    temp.no = 5;
    temp.size = 489;
 
    // Push the process
    processess.push(temp);
 
    // Get the data
    next_fit_blocks = next_fit(memory_blocks,
                               processess);
 
    // Display the data
    display(next_fit_blocks);
    memory_blocks.clear();
    memory_blocks.shrink_to_fit();
    next_fit_blocks.clear();
    next_fit_blocks.shrink_to_fit();
    return 0;
 }

Выход:

+ ------------- + -------------- + -------------- +
| № процесса | Размер процесса | Блок памяти |
+ ------------- + -------------- + -------------- +
| 1 | 88 | 1 |
| 2 | 192 | 2 |
| 3 | 277 | 3 |
| 4 | 365 | N / A |
| 5 | 489 | N / A |
+ ------------- + -------------- + -------------- +

3. Наихудший вариант

Worst Fit выделяет процесс в раздел, который является самым большим из свободно доступных разделов, доступных в основной памяти. Если большой процесс выполняется на более позднем этапе, тогда в памяти не будет места для его размещения.

Ниже представлена реализация алгоритма наихудшего соответствия:

 // C++ program for the implementation
 // of the Worst Fit algorithm
 #include <iostream>
 #include <queue>
 #include <vector>
 using namespace std;
 
// Process Class
 class process {
 public :
    // Size & number of process
    size_t size;
    pid_t no;
 };
 
// Memory Class
 class memory {
 public :
    size_t size;
 
    // Number of memory & queue of space
    // occupied by process
    pid_t no;
    queue<process> space_occupied;

                    
                                            C++
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИС++ Std против Stl
20 Февраля, 2023
C++ функция __builtin_popcount()
20 Февраля, 2023
Как получить доступ к элементам в наборе по индексу в С++?
20 Февраля, 2023
Строка С++ для плавающей/двойной и наоборот
20 Февраля, 2023
Преобразование шестнадцатеричной строки в целое число со знаком в С++
20 Февраля, 2023
C++ функция getenv()
20 Февраля, 2023
Вложенный, если в C++
20 Февраля, 2023
C++ вектор структур
20 Февраля, 2023

                    < PROGLER >

                

                    Общее
Контакты
Политика конфиденциальности

                    Обучение
Блог

                

                © progler.ru 2024. Все права защищены.
            