Algoritmo de primer ajuste para la gestión de memoria: se asigna la primera partición de memoria que es suficiente para acomodar el proceso.
Ya hemos discutido el algoritmo de primer ajuste usando arreglos en este artículo . Sin embargo, aquí vamos a ver otro enfoque utilizando una lista enlazada donde también es posible eliminar los Nodes asignados.
Ejemplos:
Input: blockSize[] = {100, 500, 200}
processSize[] = {417, 112, 426, 95}
Output:
Block of size 426 can't be allocated
Tag Block ID Size
0 1 417
1 2 112
2 0 95
After deleting block with tag id 0.
Tag Block ID Size
1 2 112
2 0 95
3 1 426
Enfoque: la idea es usar el bloque de memoria con una identificación de etiqueta única. Cada proceso de diferentes tamaños recibe una identificación de bloque, lo que significa a qué bloque de memoria pertenecen, y una identificación de etiqueta única para eliminar un proceso en particular para liberar espacio. Cree una lista gratuita de tamaños de bloque de memoria dados y una lista asignada de procesos.
Crear una lista asignada:
cree una lista asignada de tamaños de proceso dados al encontrar el primer bloque de memoria con tamaño suficiente para asignar memoria. Si no se encuentra el bloque de memoria, simplemente imprímalo. De lo contrario, cree un Node y agréguelo a la lista vinculada asignada.
Borrar proceso:
Cada proceso recibe una identificación de etiqueta única. Elimine el Node de proceso de la lista vinculada asignada para liberar espacio para otros procesos. Después de eliminar, use la identificación del bloque del Node eliminado para aumentar el tamaño del bloque de memoria en la lista libre.
A continuación se muestra la implementación del enfoque:
C++
// C++ implementation of the First
// sit memory management algorithm
// using linked list
#include <bits/stdc++.h>
using namespace std;
// Two global counters
int g = 0, k = 0;
// Structure for free list
struct free {
int tag;
int size;
struct free* next;
}* free_head = NULL, *prev_free = NULL;
// Structure for allocated list
struct alloc {
int block_id;
int tag;
int size;
struct alloc* next;
}* alloc_head = NULL, *prev_alloc = NULL;
// Function to create free
// list with given sizes
void create_free(int c)
{
struct free* p
= (struct free*)malloc(sizeof(struct free));
p->size = c;
p->tag = g;
p->next = NULL;
if (free_head == NULL)
free_head = p;
else
prev_free->next = p;
prev_free = p;
g++;
}
// Function to print free list which
// prints free blocks of given sizes
void print_free()
{
struct free* p = free_head;
cout << "Tag\tSize\n";
while (p != NULL) {
cout << p->tag << "\t" << p->size << "\n";
p = p->next;
}
}
// Function to print allocated list which
// prints allocated blocks and their block ids
void print_alloc()
{
struct alloc* p = alloc_head;
cout << "Tag\tBlock ID\tSize\n";
while (p != NULL) {
cout << p->tag << "\t " << p->block_id << "\t\t"
<< p->size << "\n";
p = p->next;
}
}
// Function to allocate memory to
// blocks as per First fit algorithm
void create_alloc(int c)
{
// create node for process of given size
struct alloc* q
= (struct alloc*)malloc(sizeof(struct alloc));
q->size = c;
q->tag = k;
q->next = NULL;
struct free* p = free_head;
// Iterate to find first memory
// block with appropriate size
while (p != NULL) {
if (q->size <= p->size)
break;
p = p->next;
}
// Node found to allocate
if (p != NULL) {
// Adding node to allocated list
q->block_id = p->tag;
p->size -= q->size;
if (alloc_head == NULL)
alloc_head = q;
else {
prev_alloc = alloc_head;
while (prev_alloc->next != NULL)
prev_alloc = prev_alloc->next;
prev_alloc->next = q;
}
k++;
}
else // Node found to allocate space from
cout << "Block of size " << c
<< " can't be allocated\n";
}
// Function to delete node from
// allocated list to free some space
void delete_alloc(int t)
{
// Standard delete function
// of a linked list node
struct alloc *p = alloc_head, *q = NULL;
// First, find the node according
// to given tag id
while (p != NULL) {
if (p->tag == t)
break;
q = p;
p = p->next;
}
if (p == NULL)
cout << "Tag ID doesn't exist\n";
else if (p == alloc_head)
alloc_head = alloc_head->next;
else
q->next = p->next;
struct free* temp = free_head;
while (temp != NULL) {
if (temp->tag == p->block_id) {
temp->size += p->size;
break;
}
temp = temp->next;
}
}
// Driver Code
int main()
{
int blockSize[] = { 100, 500, 200 };
int processSize[] = { 417, 112, 426, 95 };
int m = sizeof(blockSize) / sizeof(blockSize[0]);
int n = sizeof(processSize) / sizeof(processSize[0]);
for (int i = 0; i < m; i++)
create_free(blockSize[i]);
for (int i = 0; i < n; i++)
create_alloc(processSize[i]);
print_alloc();
// Block of tag id 0 deleted
// to free space for block of size 426
delete_alloc(0);
create_alloc(426);
cout << "After deleting block"
<< " with tag id 0.\n";
print_alloc();
}
Java
// Java implementation of the First
// sit memory management algorithm
// using linked list
public class GFG {
// Two global counters
static int g = 0, k = 0;
// Structure for free list
static class free {
int tag;
int size;
free next;
}
static free free_head = null;
static free prev_free = null;
// Structure for allocated list
static class alloc {
int block_id;
int tag;
int size;
alloc next;
}
static alloc alloc_head = null;
static alloc prev_alloc = null;
// Function to create free
// list with given sizes
static void create_free(int c)
{
free p = new free();
p.size = c;
p.tag = g;
p.next = null;
if (free_head == null)
free_head = p;
else
prev_free.next = p;
prev_free = p;
g++;
}
// Function to print free list which
// prints free blocks of given sizes
static void print_free()
{
free p = free_head;
System.out.println("Tag\tSize");
while (p != null) {
System.out.println(p.tag + "\t" + p.size);
p = p.next;
}
}
// Function to print allocated list which
// prints allocated blocks and their block ids
static void print_alloc()
{
alloc p = alloc_head;
System.out.println("Tag\tBlock ID\tSize");
while (p != null) {
System.out.println(p.tag + "\t " + p.block_id
+ "\t\t" + p.size);
p = p.next;
}
}
// Function to allocate memory to
// blocks as per First fit algorithm
static void create_alloc(int c)
{
// create node for process of given size
alloc q = new alloc();
q.size = c;
q.tag = k;
q.next = null;
free p = free_head;
// Iterate to find first memory
// block with appropriate size
while (p != null) {
if (q.size <= p.size)
break;
p = p.next;
}
// Node found to allocate
if (p != null) {
// Adding node to allocated list
q.block_id = p.tag;
p.size -= q.size;
if (alloc_head == null)
alloc_head = q;
else {
prev_alloc = alloc_head;
while (prev_alloc.next != null)
prev_alloc = prev_alloc.next;
prev_alloc.next = q;
}
k++;
}
else // Node found to allocate space from
System.out.println("Block of size " + c
+ " can't be allocated");
}
// Function to delete node from
// allocated list to free some space
static void delete_alloc(int t)
{
// Standard delete function
// of a linked list node
alloc p = alloc_head, q = null;
// First, find the node according
// to given tag id
while (p != null) {
if (p.tag == t)
break;
q = p;
p = p.next;
}
if (p == null)
System.out.println("Tag ID doesn't exist");
else if (p == alloc_head)
alloc_head = alloc_head.next;
else
q.next = p.next;
free temp = free_head;
while (temp != null) {
if (temp.tag == p.block_id) {
temp.size += p.size;
break;
}
temp = temp.next;
}
}
// Driver Code
public static void main(String[] args)
{
int blockSize[] = { 100, 500, 200 };
int processSize[] = { 417, 112, 426, 95 };
int m = blockSize.length;
int n = processSize.length;
for (int i = 0; i < m; i++)
create_free(blockSize[i]);
for (int i = 0; i < n; i++)
create_alloc(processSize[i]);
print_alloc();
// Block of tag id 0 deleted
// to free space for block of size 426
delete_alloc(0);
create_alloc(426);
System.out.println("After deleting block"
+ " with tag id 0.");
print_alloc();
}
}
// This code is contributed by Lovely Jain
Python3
# Python3 implementation of the First
# sit memory management algorithm
# using linked list
# Two global counters
g = 0; k = 0
# Structure for free list
class free:
def __init__(self):
self.tag=-1
self.size=0
self.next=None
free_head = None; prev_free = None
# Structure for allocated list
class alloc:
def __init__(self):
self.block_id=-1
self.tag=-1
self.size=0
self.next=None
alloc_head = None;prev_alloc = None
# Function to create free
# list with given sizes
def create_free(c):
global g,prev_free,free_head
p = free()
p.size = c
p.tag = g
p.next = None
if free_head is None:
free_head = p
else:
prev_free.next = p
prev_free = p
g+=1
# Function to print free list which
# prints free blocks of given sizes
def print_free():
p = free_head
print("Tag\tSize")
while (p != None) :
print("{}\t{}".format(p.tag,p.size))
p = p.next
# Function to print allocated list which
# prints allocated blocks and their block ids
def print_alloc():
p = alloc_head
print("Tag\tBlock ID\tSize")
while (p is not None) :
print("{}\t{}\t{}\t".format(p.tag,p.block_id,p.size))
p = p.next
# Function to allocate memory to
# blocks as per First fit algorithm
def create_alloc(c):
global k,alloc_head
# create node for process of given size
q = alloc()
q.size = c
q.tag = k
q.next = None
p = free_head
# Iterate to find first memory
# block with appropriate size
while (p != None) :
if (q.size <= p.size):
break
p = p.next
# Node found to allocate
if (p != None) :
# Adding node to allocated list
q.block_id = p.tag
p.size -= q.size
if (alloc_head == None):
alloc_head = q
else :
prev_alloc = alloc_head
while (prev_alloc.next != None):
prev_alloc = prev_alloc.next
prev_alloc.next = q
k+=1
else: # Node found to allocate space from
print("Block of size {} can't be allocated".format(c))
# Function to delete node from
# allocated list to free some space
def delete_alloc(t):
global alloc_head
# Standard delete function
# of a linked list node
p = alloc_head; q = None
# First, find the node according
# to given tag id
while (p != None) :
if (p.tag == t):
break
q = p
p = p.next
if (p == None):
print("Tag ID doesn't exist")
elif (p == alloc_head):
alloc_head = alloc_head.next
else:
q.next = p.next
temp = free_head
while (temp != None) :
if (temp.tag == p.block_id) :
temp.size += p.size
break
temp = temp.next
# Driver Code
if __name__ == '__main__':
blockSize = [100, 500, 200]
processSize = [417, 112, 426, 95]
m = len(blockSize)
n = len(processSize)
for i in range(m):
create_free(blockSize[i])
for i in range(n):
create_alloc(processSize[i])
print_alloc()
# Block of tag id 0 deleted
# to free space for block of size 426
delete_alloc(0)
create_alloc(426)
print("After deleting block with tag id 0.")
print_alloc()
Producción:
Block of size 426 can't be allocated Tag Block ID Size 0 1 417 1 2 112 2 0 95 After deleting block with tag id 0. Tag Block ID Size 1 2 112 2 0 95 3 1 426
Publicación traducida automáticamente
Artículo escrito por sarthak_eddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA