Prerrequisito: sistema de compañeros
Pregunta: escriba un programa para implementar el sistema de compañeros de asignación de memoria en los sistemas operativos.
Explicación:
el sistema de compañeros se implementa de la siguiente manera: se mantiene en todo momento una lista de Nodes libres, de todas las diferentes potencias de 2 posibles (por lo tanto, si el tamaño total de la memoria es de 1 MB, tendríamos 20 listas libres para rastrear). uno para bloques de tamaño 1 byte, 1 para 2 bytes, el siguiente para 4 bytes y así sucesivamente).
Cuando llega una solicitud de asignación, buscamos el bloque más pequeño que sea más grande que él. Si se encuentra un bloque de este tipo en la lista libre, se realiza la asignación (por ejemplo, la solicitud es de 27 KB y la lista libre que rastrea bloques de 32 KB tiene al menos un elemento), de lo contrario, recorremos la lista libre hacia arribahasta que encontremos un bloque lo suficientemente grande. Luego seguimos dividiéndolo en dos bloques: uno para agregar a la siguiente lista libre (de menor tamaño), otro para recorrer el árbol hasta llegar al objetivo y devolver el bloque de memoria solicitado al usuario. Si no es posible tal asignación, simplemente devolvemos nulo.
Ejemplo:
Veamos cómo procede el algoritmo rastreando un bloque de memoria de tamaño 128 KB. Inicialmente, la lista libre es: {}, {}, {}, {}, {}, {}, {}, { (0, 127) }
- Solicitud: 32 bytes
No se encontró tal bloque, por lo que recorremos hacia arriba y dividimos el bloque 0-127 en 0-63, 64-127; agregamos 64-127 a la lista de seguimiento de bloques de 64 bytes y pasamos 0-63 hacia abajo; nuevamente se divide en 0-31 y 32-63; dado que hemos encontrado el tamaño de bloque requerido, agregamos 32-63 a la lista de seguimiento de bloques de 32 bytes y devolvemos 0-31 al usuario.
La lista es: {}, {}, {}, {}, {}, { (32, 63) }, { (64, 127) }, {} - Solicitud: 7 bytes
No se encontró tal bloque: divida el bloque 32-63 en dos bloques, a saber, 32-47 y 48-63; luego divida 32-47 en 32-39 y 40-47; finalmente, devuelva 32-39 al usuario (se produce una fragmentación interna de 1 byte) La
lista es: {}, {}, {}, { (40, 47) }, { (48, 63) }, {}, { (64) , 127) }, {} - Solicitud: 64 bytes
El segmento de memoria directo 64-127 se asignará como ya existe.
La lista es: {}, {}, {}, { (40, 47) }, { (48, 63) }, {}, {}, {} - Solicitud: 56 bytes
Resultado: No asignado
El resultado será el siguiente:
Figura: Buddy Allocation-128 muestra la dirección de inicio del siguiente bloque posible (si el tamaño de la memoria principal aumenta alguna vez)
Implementación –
C++
#include<bits/stdc++.h>
using namespace std;
// Size of vector of pairs
int size;
// Global vector of pairs to store
// address ranges available in free list
vector<pair<int, int>> free_list[100000];
// Map used as hash map to store the starting
// address as key and size of allocated segment
// key as value
map<int, int> mp;
void initialize(int sz)
{
// Maximum number of powers of 2 possible
int n = ceil(log(sz) / log(2));
size = n + 1;
for(int i = 0; i <= n; i++)
free_list[i].clear();
// Initially whole block of specified
// size is available
free_list[n].push_back(make_pair(0, sz - 1));
}
void allocate(int sz)
{
// Calculate index in free list
// to search for block if available
int n = ceil(log(sz) / log(2));
// Block available
if (free_list[n].size() > 0)
{
pair<int, int> temp = free_list[n][0];
// Remove block from free list
free_list[n].erase(free_list[n].begin());
cout << "Memory from " << temp.first
<< " to " << temp.second << " allocated"
<< "\n";
// map starting address with
// size to make deallocating easy
mp[temp.first] = temp.second -
temp.first + 1;
}
else
{
int i;
for(i = n + 1; i < size; i++)
{
// Find block size greater than request
if(free_list[i].size() != 0)
break;
}
// If no such block is found
// i.e., no memory block available
if (i == size)
{
cout << "Sorry, failed to allocate memory \n";
}
// If found
else
{
pair<int, int> temp;
temp = free_list[i][0];
// Remove first block to split it into halves
free_list[i].erase(free_list[i].begin());
i--;
for(; i >= n; i--)
{
// Divide block into two halves
pair<int, int> pair1, pair2;
pair1 = make_pair(temp.first,
temp.first +
(temp.second -
temp.first) / 2);
pair2 = make_pair(temp.first +
(temp.second -
temp.first + 1) / 2,
temp.second);
free_list[i].push_back(pair1);
// Push them in free list
free_list[i].push_back(pair2);
temp = free_list[i][0];
// Remove first free block to
// further split
free_list[i].erase(free_list[i].begin());
}
cout << "Memory from " << temp.first
<< " to " << temp.second
<< " allocated" << "\n";
mp[temp.first] = temp.second -
temp.first + 1;
}
}
}
// Driver code
int main()
{
// Uncomment following code for interactive IO
/*
int total,c,req;
cin>>total;
initialize(total);
while(true)
{
cin>>req;
if(req < 0)
break;
allocate(req);
}*/
initialize(128);
allocate(32);
allocate(7);
allocate(64);
allocate(56);
return 0;
}
// This code is contributed by sarthak_eddy
Java
import java.io.*;
import java.util.*;
class Buddy {
// Inner class to store lower
// and upper bounds of the allocated memory
class Pair
{
int lb, ub;
Pair(int a, int b)
{
lb = a;
ub = b;
}
}
// Size of main memory
int size;
// Array to track all
// the free nodes of various sizes
ArrayList<Pair> arr[];
// Else compiler will give warning
// about generic array creation
@SuppressWarnings("unchecked")
Buddy(int s)
{
size = s;
// Gives us all possible powers of 2
int x = (int)Math.ceil(Math.log(s) / Math.log(2));
// One extra element is added
// to simplify arithmetic calculations
arr = new ArrayList[x + 1];
for (int i = 0; i <= x; i++)
arr[i] = new ArrayList<>();
// Initially, only the largest block is free
// and hence is on the free list
arr[x].add(new Pair(0, size - 1));
}
void allocate(int s)
{
// Calculate which free list to search to get the
// smallest block large enough to fit the request
int x = (int)Math.ceil(Math.log(s) / Math.log(2));
int i;
Pair temp = null;
// We already have such a block
if (arr[x].size() > 0)
{
// Remove from free list
// as it will be allocated now
temp = (Pair)arr[x].remove(0);
System.out.println("Memory from " + temp.lb
+ " to " + temp.ub + " allocated");
return;
}
// If not, search for a larger block
for (i = x + 1; i < arr.length; i++) {
if (arr[i].size() == 0)
continue;
// Found a larger block, so break
break;
}
// This would be true if no such block was found
// and array was exhausted
if (i == arr.length)
{
System.out.println("Sorry, failed to allocate memory");
return;
}
// Remove the first block
temp = (Pair)arr[i].remove(0);
i--;
// Traverse down the list
for (; i >= x; i--) {
// Divide the block in two halves
// lower index to half-1
Pair newPair = new Pair(temp.lb, temp.lb
+ (temp.ub - temp.lb) / 2);
// half to upper index
Pair newPair2 = new Pair(temp.lb
+ (temp.ub - temp.lb + 1) / 2, temp.ub);
// Add them to next list
// which is tracking blocks of smaller size
arr[i].add(newPair);
arr[i].add(newPair2);
// Remove a block to continue the downward pass
temp = (Pair)arr[i].remove(0);
}
// Finally inform the user
// of the allocated location in memory
System.out.println("Memory from " + temp.lb
+ " to " + temp.ub + " allocated");
}
public static void main(String args[]) throws IOException
{
int initialMemory = 0, val = 0;
// Uncomment the below section for interactive I/O
/*Scanner sc=new Scanner(System.in);
initialMemory = sc.nextInt();
Buddy obj = new Buddy(initialMemory);
while(true)
{
val = sc.nextInt();// Accept the request
if(val <= 0)
break;
obj.allocate(val);// Proceed to allocate
}*/
initialMemory = 128;
// Initialize the object with main memory size
Buddy obj = new Buddy(initialMemory);
obj.allocate(32);
obj.allocate(7);
obj.allocate(64);
obj.allocate(56);
}
}
C#
using System;
using System.Collections.Generic;
public class Buddy
{
// Inner class to store lower
// and upper bounds of the
// allocated memory
class Pair
{
public int lb, ub;
public Pair(int a, int b)
{
lb = a;
ub = b;
}
}
// Size of main memory
int size;
// Array to track all
// the free nodes of various sizes
List<Pair> []arr;
// Else compiler will give warning
// about generic array creation
Buddy(int s)
{
size = s;
// Gives us all possible powers of 2
int x = (int)Math.Ceiling(Math.Log(s) /
Math.Log(2));
// One extra element is added
// to simplify arithmetic calculations
arr = new List<Pair>[x + 1];
for (int i = 0; i <= x; i++)
arr[i] = new List<Pair>();
// Initially, only the largest block is free
// and hence is on the free list
arr[x].Add(new Pair(0, size - 1));
}
void allocate(int s)
{
// Calculate which free list to search
// to get the smallest block
// large enough to fit the request
int x = (int)Math.Ceiling(Math.Log(s) /
Math.Log(2));
int i;
Pair temp = null;
// We already have such a block
if (arr[x].Count > 0)
{
// Remove from free list
// as it will be allocated now
temp = (Pair)arr[x][0];
arr[x].RemoveAt(0);
Console.WriteLine("Memory from " + temp.lb +
" to " + temp.ub + " allocated");
return;
}
// If not, search for a larger block
for (i = x + 1; i < arr.Length; i++)
{
if (arr[i].Count == 0)
continue;
// Found a larger block, so break
break;
}
// This would be true if no such block
// was found and array was exhausted
if (i == arr.Length)
{
Console.WriteLine("Sorry, failed to" +
" allocate memory");
return;
}
// Remove the first block
temp = (Pair)arr[i][0];
arr[i].RemoveAt(0);
i--;
// Traverse down the list
for (; i >= x; i--)
{
// Divide the block in two halves
// lower index to half-1
Pair newPair = new Pair(temp.lb, temp.lb +
(temp.ub - temp.lb) / 2);
// half to upper index
Pair newPair2 = new Pair(temp.lb + (temp.ub -
temp.lb + 1) / 2, temp.ub);
// Add them to next list which is
// tracking blocks of smaller size
arr[i].Add(newPair);
arr[i].Add(newPair2);
// Remove a block to continue
// the downward pass
temp = (Pair)arr[i][0];
arr[i].RemoveAt(0);
}
// Finally inform the user
// of the allocated location in memory
Console.WriteLine("Memory from " + temp.lb +
" to " + temp.ub + " allocated");
}
// Driver Code
public static void Main(String []args)
{
int initialMemory = 0;
initialMemory = 128;
// Initialize the object with main memory size
Buddy obj = new Buddy(initialMemory);
obj.allocate(32);
obj.allocate(7);
obj.allocate(64);
obj.allocate(56);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Inner class to store lower
// and upper bounds of the allocated memory
class Pair
{
constructor(a, b)
{
this.lb = a;
this.ub = b;
}
}
let size;
let arr;
function Buddy(s)
{
size = s;
// Gives us all possible powers of 2
let x = Math.ceil(Math.log(s) / Math.log(2));
// One extra element is added
// to simplify arithmetic calculations
arr = new Array(x + 1);
for(let i = 0; i <= x; i++)
arr[i] =[];
// Initially, only the largest block is free
// and hence is on the free list
arr[x].push(new Pair(0, size - 1));
}
function allocate(s)
{
// Calculate which free list to search to get the
// smallest block large enough to fit the request
let x = Math.floor(Math.ceil(
Math.log(s) / Math.log(2)));
let i;
let temp = null;
// We already have such a block
if (arr[x].length > 0)
{
// Remove from free list
// as it will be allocated now
temp = arr[x].shift();
document.write("Memory from " + temp.lb +
" to " + temp.ub + " allocated<br>");
return;
}
// If not, search for a larger block
for(i = x + 1; i < arr.length; i++)
{
if (arr[i].length == 0)
continue;
// Found a larger block, so break
break;
}
// This would be true if no such block was
// found and array was exhausted
if (i == arr.length)
{
document.write("Sorry, failed to " +
"allocate memory<br>");
return;
}
// Remove the first block
temp = arr[i].shift(0);
i--;
// Traverse down the list
for(; i >= x; i--)
{
// Divide the block in two halves
// lower index to half-1
let newPair = new Pair(temp.lb,
temp.lb +
Math.floor(
(temp.ub -
temp.lb) / 2));
// half to upper index
let newPair2 = new Pair(temp.lb +
Math.floor(
(temp.ub -
temp.lb + 1) / 2),
temp.ub);
// Add them to next list which is
// tracking blocks of smaller size
arr[i].push(newPair);
arr[i].push(newPair2);
// Remove a block to continue
// the downward pass
temp = arr[i].shift(0);
}
// Finally inform the user
// of the allocated location in memory
document.write("Memory from " + temp.lb +
" to " + temp.ub + " allocated<br>");
}
// Driver code
let initialMemory = 0, val = 0;
// Uncomment the below section for interactive I/O
/*Scanner sc=new Scanner(System.in);
initialMemory = sc.nextInt();
Buddy obj = new Buddy(initialMemory);
while(true)
{
val = sc.nextInt();// Accept the request
if(val <= 0)
break;
obj.allocate(val);// Proceed to allocate
}*/
initialMemory = 128;
// Initialize the object with main memory size
Buddy(initialMemory);
allocate(32);
allocate(7);
allocate(64);
allocate(56);
// This code is contributed by rag2127
</script>
Producción:
Memory from 0 to 31 allocated Memory from 32 to 39 allocated Memory from 64 to 127 allocated Sorry, failed to allocate memory
Complejidad de tiempo:
si el tamaño de la memoria principal es n , tenemos un número de registro (n) de diferentes potencias de 2 y, por lo tanto, elementos de registro (n) en la array (llamada arr en el código) rastreando listas libres. Para asignar un bloque, solo necesitamos atravesar la array una vez hacia arriba y una vez hacia abajo, por lo que la complejidad del tiempo es O(2log(n)) o simplemente O(logn)