Requisito previo: Métodos de asignación de particiones
¿Qué es Next Fit?
Next fit es una versión modificada de ‘first fit’ . 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.
¿Cuáles son sus ventajas sobre el primer ajuste?
- El primer ajuste es un algoritmo directo y rápido, pero tiende a cortar una gran parte de las partes libres en partes pequeñas, por lo que los procesos que necesitan una gran parte del bloque de memoria no obtendrían nada, incluso si la suma de todas las partes pequeñas es mayor. requerido que es el llamado problema de fragmentación externa.
- Otro problema del primer ajuste es que tiende a asignar partes de memoria al principio de la memoria, lo que puede dar lugar a más fragmentos internos al principio. Next fit intenta abordar este problema iniciando la búsqueda de la parte libre de partes no desde el inicio de la memoria, sino desde donde finaliza la última vez.
- Next fit es un algoritmo de búsqueda muy rápido y también es comparativamente más rápido que los algoritmos de gestión de memoria First Fit y Best Fit.
Example:
Input : blockSize[] = {5, 10, 20};
processSize[] = {10, 20, 30};
Output:
Process No. Process Size Block no.
1 10 2
2 20 3
3 30 Not Allocated
Algoritmo:
- Ingrese el número de bloques de memoria y sus tamaños e inicialice todos los bloques como libres.
- Ingrese el número de procesos y sus tamaños.
- Comience eligiendo cada proceso y verifique si se puede asignar al bloque actual, si es así, asígnele la memoria requerida y verifique el siguiente proceso pero desde el bloque donde lo dejamos no desde el inicio.
- Si el tamaño del bloque actual es más pequeño, siga revisando los bloques adicionales.
C++
// C/C++ program for next fit
// memory management algorithm
#include <bits/stdc++.h>
using namespace std;
// Function to allocate memory to blocks as per Next fit
// algorithm
void NextFit(int blockSize[], int m, int processSize[], int n)
{
// Stores block id of the block allocated to a
// process
int allocation[n], j = 0;
// Initially no block is assigned to any process
memset(allocation, -1, sizeof(allocation));
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i = 0; i < n; i++) {
// Do not start from beginning
while (j < m) {
if (blockSize[j] >= processSize[i]) {
// allocate block j to p[i] process
allocation[i] = j;
// Reduce available memory in this block.
blockSize[j] -= processSize[i];
break;
}
// mod m will help in traversing the blocks from
// starting block after we reach the end.
j = (j + 1) % m;
}
}
cout << "\nProcess No.\tProcess Size\tBlock no.\n";
for (int i = 0; i < n; i++) {
cout << " " << i + 1 << "\t\t" << processSize[i]
<< "\t\t";
if (allocation[i] != -1)
cout << allocation[i] + 1;
else
cout << "Not Allocated";
cout << endl;
}
}
// Driver program
int main()
{
int blockSize[] = { 5, 10, 20 };
int processSize[] = { 10, 20, 5 };
int m = sizeof(blockSize) / sizeof(blockSize[0]);
int n = sizeof(processSize) / sizeof(processSize[0]);
NextFit(blockSize, m, processSize, n);
return 0;
}
Java
// Java program for next fit
// memory management algorithm
import java.util.Arrays;
public class GFG {
// Function to allocate memory to blocks as per Next fit
// algorithm
static void NextFit(int blockSize[], int m, int processSize[], int n) {
// Stores block id of the block allocated to a
// process
int allocation[] = new int[n], j = 0;
// Initially no block is assigned to any process
Arrays.fill(allocation, -1);
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i = 0; i < n; i++) {
// Do not start from beginning
int count =0;
while (j < m) {
count++; //makes sure that for every process we traverse through entire array maximum once only.This avoids the problem of going into infinite loop if memory is not available
if (blockSize[j] >= processSize[i]) {
// allocate block j to p[i] process
allocation[i] = j;
// Reduce available memory in this block.
blockSize[j] -= processSize[i];
break;
}
// mod m will help in traversing the blocks from
// starting block after we reach the end.
j = (j + 1) % m;
}
}
System.out.print("\nProcess No.\tProcess Size\tBlock no.\n");
for (int i = 0; i < n; i++) {
System.out.print( i + 1 + "\t\t" + processSize[i]
+ "\t\t");
if (allocation[i] != -1) {
System.out.print(allocation[i] + 1);
} else {
System.out.print("Not Allocated");
}
System.out.println("");
}
}
// Driver program
static public void main(String[] args) {
int blockSize[] = {5, 10, 20};
int processSize[] = {10, 20, 5};
int m = blockSize.length;
int n = processSize.length;
NextFit(blockSize, m, processSize, n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for next fit
# memory management algorithm
# Function to allocate memory to
# blocks as per Next fit algorithm
def NextFit(blockSize, m, processSize, n):
# Stores block id of the block
# allocated to a process
# Initially no block is assigned
# to any process
allocation = [-1] * n
j = 0
t = m-1
# pick each process and find suitable blocks
# according to its size ad assign to it
for i in range(n):
# Do not start from beginning
while j < m:
if blockSize[j] >= processSize[i]:
# allocate block j to p[i] process
allocation[i] = j
# Reduce available memory in this block.
blockSize[j] -= processSize[i]
# sets a new end point
t = (j - 1) % m
break
if t == j:
# sets a new end point
t = (j - 1) % m
# breaks the loop after going through all memory block
break
# mod m will help in traversing the
# blocks from starting block after
# we reach the end.
j = (j + 1) % m
print("Process No. Process Size Block no.")
for i in range(n):
print(i + 1, " ", processSize[i],end = " ")
if allocation[i] != -1:
print(allocation[i] + 1)
else:
print("Not Allocated")
# Driver Code
if __name__ == '__main__':
blockSize = [5, 10, 20]
processSize = [10, 20, 5]
m = len(blockSize)
n = len(processSize)
NextFit(blockSize, m, processSize, n)
C#
// C# program for next fit
// memory management algorithm
using System;
using System.Linq;
public class GFG {
// Function to allocate memory to blocks as per Next fit
// algorithm
static void NextFit(int []blockSize, int m,
int []processSize, int n) {
// Stores block id of the block allocated to a
// process
int []allocation = new int[n];
int j = 0;
// Initially no block is assigned to any process
Enumerable.Repeat(-1, n).ToArray();
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i = 0; i < n; i++) {
// Do not start from beginning
while (j < m) {
if (blockSize[j] >= processSize[i]) {
// allocate block j to p[i] process
allocation[i] = j;
// Reduce available memory in this block.
blockSize[j] -= processSize[i];
break;
}
// mod m will help in traversing the blocks from
// starting block after we reach the end.
j = (j + 1) % m;
}
}
Console.Write("\nProcess No.\tProcess Size\tBlock no.\n");
for (int i = 0; i < n; i++) {
Console.Write( i + 1 + "\t\t" + processSize[i]
+ "\t\t");
if (allocation[i] != -1) {
Console.Write(allocation[i] + 1);
} else {
Console.Write("Not Allocated");
}
Console.WriteLine("");
}
}
// Driver program
static public void Main() {
int []blockSize = {5, 10, 20};
int []processSize = {10, 20, 5};
int m = blockSize.Length;
int n = processSize.Length;
NextFit(blockSize, m, processSize, n);
}
}
/*This code is contributed by Rajput-Ji*/
PHP
<?php
// PHP program for next fit
// memory management algorithm
// Function to allocate memory to blocks as per Next fit
// algorithm
function NextFit($blockSize, $m, $processSize, $n)
{
// Stores block id of the block allocated to a
// process
$allocation = array_fill(0, $n, -1);
$j = 0;
// Initially no block is assigned to any process above
// pick each process and find suitable blocks
// according to its size ad assign to it
for ($i = 0; $i < $n; $i++)
{
// Do not start from beginning
while ($j < $m)
{
if ($blockSize[$j] >= $processSize[$i])
{
// allocate block j to p[i] process
$allocation[$i] = $j;
// Reduce available memory in this block.
$blockSize[$j] -= $processSize[$i];
break;
}
// mod m will help in traversing the blocks from
// starting block after we reach the end.
$j = ($j + 1) % $m;
}
}
echo "\nProcess No.\tProcess Size\tBlock no.\n";
for ($i = 0; $i < $n; $i++)
{
echo " ".($i + 1)."\t\t".$processSize[$i]."\t\t";
if ($allocation[$i] != -1)
echo ($allocation[$i] + 1);
else
echo "Not Allocated";
echo "\n";
}
}
// Driver program
$blockSize = array( 5, 10, 20 );
$processSize = array( 10, 20, 5 );
$m = count($blockSize);
$n = count($processSize);
NextFit($blockSize, $m, $processSize, $n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program for next fit
// memory management algorithm
// Function to allocate memory to blocks as per Next fit
// algorithm
function NextFit(blockSize, m, processSize, n) {
// Stores block id of the block allocated to a
// process
let allocation = Array.from({length: n}, (_, i) => -1), j = 0;
// pick each process and find suitable blocks
// according to its size ad assign to it
for (let i = 0; i < n; i++) {
// Do not start from beginning
while (j < m) {
if (blockSize[j] >= processSize[i]) {
// allocate block j to p[i] process
allocation[i] = j;
// Reduce available memory in this block.
blockSize[j] -= processSize[i];
break;
}
// mod m will help in traversing the blocks from
// starting block after we reach the end.
j = (j + 1) % m;
}
}
document.write("\nProcess No. Process Size. Block no." + "<br/>");
for (let i = 0; i < n; i++) {
document.write( i + 1 + Array(20).fill('\xa0').join('') + processSize[i]
+ Array(20).fill('\xa0').join(''));
if (allocation[i] != -1) {
document.write(allocation[i] + 1);
} else {
document.write("Not Allocated");
}
document.write("<br/>");
}
}
// Driver Code
let blockSize = [5, 10, 20];
let processSize = [10, 20, 5];
let m = blockSize.length;
let n = processSize.length;
NextFit(blockSize, m, processSize, n);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
Process No. Process Size Block no. 1 10 2 2 20 3 3 5 1
Este artículo es una contribución de Akash Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA