Requisito previo: Métodos de asignación de particiones en la administración de memoria
En Asignación de particiones , cuando hay más de una partición disponible libremente para acomodar una solicitud de proceso, se debe seleccionar una partición. Para elegir una partición en particular, se necesita un método de asignación de partición. Un método de asignación de particiones se considera mejor si evita la fragmentación interna.
Considere los siguientes datos para el proceso:
| Nro. de proceso | Tamaño del proceso |
|---|---|
| 1 | 88 |
| 2 | 192 |
| 3 | 277 |
| 4 | 365 |
| 5 | 489 |
Considere los siguientes datos para las ranuras de memoria:
| Número de bloque de memoria | Tamaño del bloque de memoria |
|---|---|
| 1 | 400 |
| 2 | 500 |
| 3 | 300 |
| 4 | 200 |
| 5 | 100 |
A continuación se muestran los diversos esquemas de asignación de particiones con su implementación con respecto a los datos proporcionados anteriormente.
1. Primer ajuste
Este método mantiene la lista de trabajos libres/ocupados organizada por ubicación de memoria, de orden bajo a memoria de orden alto. En este método, el primer trabajo reclama la primera memoria disponible con espacio mayor o igual a su tamaño. El sistema operativo no busca la partición adecuada, sino que simplemente asigna el trabajo a la partición de memoria más cercana disponible con tamaño suficiente.
A continuación se muestra la implementación del algoritmo First Fit :
// 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;
}
Producción:
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 1 | 88 | 1 | | 2 | 192 | 1 | | 3 | 277 | 2 | | 4 | 365 | N/A | | 5 | 489 | N/A | +-------------+--------------+--------------+
2. Siguiente ajuste
El siguiente ajuste es una versión modificada de ‘primer ajuste’. Comienza como el primer ajuste para encontrar una partición libre, pero cuando se le llama la próxima vez, comienza a buscar desde donde lo dejó, no desde el principio. Esta política hace uso de un puntero itinerante. El puntero se mueve a lo largo de la string de memoria para buscar el siguiente ajuste. Esto ayuda a evitar el uso de la memoria siempre desde la cabeza (comienzo) de la string de bloques libre.
A continuación se muestra la implementación del algoritmo 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;
}
Producción:
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 1 | 88 | 1 | | 2 | 192 | 2 | | 3 | 277 | 3 | | 4 | 365 | N/A | | 5 | 489 | N/A | +-------------+--------------+--------------+
3. Peor ajuste
Worst Fit asigna un proceso a la partición que es lo suficientemente grande entre las particiones disponibles gratuitamente en la memoria principal. Si un proceso grande llega en una etapa posterior, la memoria no tendrá espacio para acomodarlo.
A continuación se muestra la implementación del algoritmo de peor ajuste :
// 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;
// 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 Worst Fit
vector<memory> worst_fit(vector<memory> memory_blocks,
queue<process> processess)
{
int i = 0, index = 0, max;
memory na;
na.no = -10;
// Loop till process queue is not empty
while (!processess.empty()) {
max = 0;
// Traverse the memory_blocks
for (i = 0; i < memory_blocks.size(); i++) {
if (memory_blocks.at(i).size >= processess.front().size
&& memory_blocks.at(i).size > max) {
max = memory_blocks.at(i).size;
index = i;
}
}
if (max != 0) {
memory_blocks.at(index).push(processess.front());
}
else {
na.size += processess.front().size;
na.push(processess.front());
}
// Pop the current process
processess.pop();
}
// If space is not occupied
if (!na.space_occupied.empty()) {
memory_blocks.push_back(na);
}
// Return the memory
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 worst fit blocks
vector<memory> worst_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
worst_fit_blocks = worst_fit(memory_blocks,
processess);
// Display the data
display(worst_fit_blocks);
memory_blocks.clear();
memory_blocks.shrink_to_fit();
worst_fit_blocks.clear();
worst_fit_blocks.shrink_to_fit();
return 0;
}
Producción:
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 3 | 277 | 1 | | 1 | 88 | 2 | | 2 | 192 | 2 | | 4 | 365 | N/A | | 5 | 489 | N/A | +-------------+--------------+--------------+
4. Mejor ajuste
Este método mantiene la lista de disponibilidad ordenada por tamaño, de menor a mayor. En este método, el sistema operativo primero busca en toda la memoria de acuerdo con el tamaño del trabajo dado y lo asigna a la partición libre más cercana en la memoria, lo que le permite usar la memoria de manera eficiente. Aquí los trabajos están en el orden del trabajo más pequeño al trabajo más grande.
A continuación se muestra la implementación del algoritmo Best Fit :
// C++ program for the implementation
// of the Best 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 Best Fit
vector<memory> best_fit(vector<memory> memory_blocks,
queue<process> processess)
{
int i = 0, min, index = 0;
memory na;
na.no = -10;
// Loop till processe is not empty
while (!processess.empty()) {
min = 0;
// Traverse the memory_blocks
for (i = 0; i < memory_blocks.size(); i++) {
if (memory_blocks.at(i).size >= processess.front().size && (min == 0 || memory_blocks.at(i).size < min)) {
min = memory_blocks.at(i).size;
index = i;
}
}
if (min != 0) {
memory_blocks.at(index).push(processess.front());
}
else {
na.size += processess.front().size;
na.push(processess.front());
}
// Pop the processe
processess.pop();
}
// If space is no occupied then push
// the current memory na
if (!na.space_occupied.empty()) {
memory_blocks.push_back(na);
}
// Return the memory_blocks
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 best fit blocks
vector<memory> best_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 processe to queue
processess.push(temp);
temp.no = 2;
temp.size = 192;
// Push the processe to queue
processess.push(temp);
temp.no = 3;
temp.size = 277;
// Push the processe to queue
processess.push(temp);
temp.no = 4;
temp.size = 365;
// Push the processe to queue
processess.push(temp);
temp.no = 5;
temp.size = 489;
// Push the processe to queue
processess.push(temp);
// Get the data
best_fit_blocks = best_fit(memory_blocks,
processess);
// Display the data
display(best_fit_blocks);
memory_blocks.clear();
memory_blocks.shrink_to_fit();
best_fit_blocks.clear();
best_fit_blocks.shrink_to_fit();
return 0;
}
Producción:
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 4 | 365 | 1 | | 5 | 489 | 2 | | 3 | 277 | 3 | | 2 | 192 | 4 | | 1 | 88 | 5 | +-------------+--------------+--------------+
Publicación traducida automáticamente
Artículo escrito por jaspreetsinghpal18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA