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

Опубликовано: 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;

РЕКОМЕНДУЕМЫЕ СТАТЬИ