Prerrequisito – Asignación de compañeros |
Pregunta del conjunto 1 : escriba un programa para implementar el sistema de compañeros de asignación y desasignación de memoria en los sistemas operativos.
Explicación:
como ya sabemos del Conjunto 1, la asignación se realiza mediante el uso de listas libres. Ahora, para la desasignación, mantendremos una estructura de datos adicional: un mapa (unordered_set en C++, HashMap en Java) con la dirección de inicio del segmento como clave y el tamaño del segmento como valor y lo actualizaremos cada vez que llegue una solicitud de asignación. Ahora, cuando llegue una solicitud de desasignación, primero revisaremos el mapa para ver si es una solicitud válida. Si es así, agregaremos el bloque a la lista libre de bloques de seguimiento de sus tamaños. Luego, buscaremos en la lista gratuita para ver si es amigo .es gratis; si es así, fusionaremos los bloques y los colocaremos en la lista libre encima de ellos (que rastrea bloques del doble del tamaño), de lo contrario no nos fusionaremos y simplemente regresaremos después de eso.
¿Cómo saber qué bloque es el compañero de un bloque dado?
Definamos dos términos : buddyNumber y buddyAddress . El buddyNumber de un bloque se calcula mediante la fórmula:
(base_address-starting_address_of_main_memory)/block_size
Notamos que esto siempre es un número entero, ya que tanto el numerador como el denominador son potencias de 2. Ahora, un bloque será compañero de otro bloque si ambos se formaron por la división del mismo bloque más grande. Por ejemplo, si vienen 4 requests de asignación consecutivas de 16 bytes, terminaremos con los bloques 0-15, 16-31, 32-47, 48-63 donde los bloques 0-15 y 16-31 son amigos (como se formaron dividiendo el bloque 0-32) pero 0-15 y 32-47 no lo son. BuddyAddress de un bloque es el índice de inicio de su bloque de amigos, dado por la fórmula :
block_starting_address+block_size (if buddyNumber is even) block_starting_address-block_size (if buddyNumber is odd)
Por lo tanto, todo lo que tenemos que hacer es encontrar esta dirección de amigo en la lista libre (comparándola con todas las direcciones de inicio en esa lista en particular) y, si está presente, se puede realizar la fusión.
Ejemplos:
Veamos cómo procede el algoritmo rastreando un bloque de memoria de tamaño 128 KB. Inicialmente, la lista libre es: {}, {}, {}, {}, {}, {}, {}, { (0, 127) }
- Solicitud de asignación: 16 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; agregamos 32-63 a la lista de seguimiento de bloques de 32 bytes, pasando 0-31 hacia abajo; se realiza una división más y se devuelve 0-15 al usuario, mientras que 16-31 se agrega a la lista libre de seguimiento de bloques de 16 bytes.
La lista es: {}, {}, {}, {}, { (16, 31) }, { (32, 63) }, { (64, 127) }, {} - Solicitud de asignación: 16 bytes
El segmento de memoria directo 16-31 se asignará como ya existe.
La lista es: {}, {}, {}, {}, {}, { (32, 63) }, { (64, 127) }, {} - Solicitud de asignación: 16 bytes
No se encontró dicho bloque, por lo que recorreremos hasta el bloque 32-63 y lo dividiremos en bloques 32-47 y 48-63; agregaremos 48-63 a la lista de seguimiento de bloques de 16 bytes y devolveremos 32-47 a un usuario.
La lista es: {}, {}, {}, {}, { (48, 63) }, {}, { (64, 127) }, {} - Solicitud de asignación: 16 bytes
El segmento de memoria directo 48-63 se asignará como ya existe.
La lista es: {}, {}, {}, {}, {}, {}, { (64, 127) }, {} - Solicitud de desasignación: StartIndex = 0
Se realizará la desasignación, pero no es posible la fusión, ya que su buddyNumber es 0 y buddyAddress es 16 (a través de la fórmula), ninguno de los cuales está en la lista libre.
La lista es: {}, {}, {}, {}, { (0, 15) }, {}, { (64, 127) }, {} - Solicitud de desasignación: StartIndex = 9
Resultado: solicitud no válida, ya que este segmento nunca se asignó.
La lista es: {}, {}, {}, {}, { (0, 15) }, {}, { (64, 127) }, {} - Solicitud de desasignación: StartIndex = 32
Se realizará la desasignación, pero no es posible la fusión, ya que el número de amigo de los bloques es 0 y 2. La dirección de amigo de los bloques es 16 y 48, respectivamente, ninguno de los cuales está en la lista libre.
La lista es: {}, {}, {}, {}, { (0, 15), (32-47) }, {}, { (64, 127) }, {} - Solicitud de desasignación: StartIndex = 16 Se realizará la desasignación y la fusión de
los bloques 0-15 y 16-31 también se realizará, ya que la dirección de amigo del bloque 16-31 es 0, que está presente en la lista libre de seguimiento de bloques de 16 bytes.
La lista es: {}, {}, {}, {}, { (32-47) }, { (0, 31) }, { (64, 127) }, {}
Figura: Asignación y desasignación del algoritmo Buddy
Implementación:
a continuación se muestra el programa completo.
C++
#include<bits/stdc++.h>
using namespace std;
// Size of vector of pairs
int size;
// Global vector of pairs to track all
// the free nodes of various sizes
vector<pair<int, int>> arr[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 Buddy(int s)
{
// Maximum number of powers of 2 possible
int n = ceil(log(s) / log(2));
size = n + 1;
for(int i = 0; i <= n; i++)
arr[i].clear();
// Initially whole block of specified
// size is available
arr[n].push_back(make_pair(0, s - 1));
}
void allocate(int s)
{
// Calculate index in free list
// to search for block if available
int x = ceil(log(s) / log(2));
// Block available
if (arr[x].size() > 0)
{
pair<int, int> temp = arr[x][0];
// Remove block from free list
arr[x].erase(arr[x].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;
// If not, search for a larger block
for(i = x + 1; i < size; i++)
{
// Find block size greater
// than request
if (arr[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 = arr[i][0];
// Remove first block to split
// it into halves
arr[i].erase(arr[i].begin());
i--;
for(;i >= x; 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);
arr[i].push_back(pair1);
// Push them in free list
arr[i].push_back(pair2);
temp = arr[i][0];
// Remove first free block to
// further split
arr[i].erase(arr[i].begin());
}
cout << "Memory from " << temp.first
<< " to " << temp.second
<< " allocate" << "\n";
mp[temp.first] = temp.second -
temp.first + 1;
}
}
}
void deallocate(int id)
{
// If no such starting address available
if(mp.find(id) == mp.end())
{
cout << "Sorry, invalid free request\n";
return;
}
// Size of block to be searched
int n = ceil(log(mp[id]) / log(2));
int i, buddyNumber, buddyAddress;
// Add the block in free list
arr[n].push_back(make_pair(id,
id + pow(2, n) - 1));
cout << "Memory block from " << id
<< " to "<< id + pow(2, n) - 1
<< " freed\n";
// Calculate buddy number
buddyNumber = id / mp[id];
if (buddyNumber % 2 != 0)
buddyAddress = id - pow(2, n);
else
buddyAddress = id + pow(2, n);
// Search in free list to find it's buddy
for(i = 0; i < arr[n].size(); i++)
{
// If buddy found and is also free
if (arr[n][i].first == buddyAddress)
{
// Now merge the buddies to make
// them one large free memory block
if (buddyNumber % 2 == 0)
{
arr[n + 1].push_back(make_pair(id,
id + 2 * pow(2, n) - 1));
cout << "Coalescing of blocks starting at "
<< id << " and " << buddyAddress
<< " was done" << "\n";
}
else
{
arr[n + 1].push_back(make_pair(
buddyAddress, buddyAddress +
2 * pow(2, n) - 1));
cout << "Coalescing of blocks starting at "
<< buddyAddress << " and "
<< id << " was done" << "\n";
}
arr[n].erase(arr[n].begin() + i);
arr[n].erase(arr[n].begin() +
arr[n].size() - 1);
break;
}
}
// Remove the key existence from map
mp.erase(id);
}
// Driver code
int main()
{
// Uncomment following code for interactive IO
/*
int total,c,req;
cout<<"Enter Total Memory Size (in Bytes) => ";
cin>>total;
initialize(total);
label:
while(1)
{
cout<<"\n1. Add Process into Memory\n
2. Remove Process \n3. Allocation Map\n4. Exit\n=> ";
cin>>c;
switch(c)
{
case 1:
cout<<"Enter Process Size (in Bytes) => ";
cin>>req;
cout<<"\n===>";
allocate(req);
break;
case 2:
cout<<"Enter Starting Address => ";
cin>>req;
cout<<"\n===>";
deallocate(req);
break;
case 3:
print();
break;
case 4:
exit(0);
break;
default:
goto label;
}
}*/
Buddy(128);
allocate(16);
allocate(16);
allocate(16);
allocate(16);
deallocate(0);
deallocate(9);
deallocate(32);
deallocate(16);
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[];
// Hashmap to store the starting
// address and size of allocated segment
// Key is starting address, size is value
HashMap<Integer, Integer> hm;
// Else compiler will give warning
// about generic array creation
@SuppressWarnings("unchecked")
Buddy(int s)
{
size = s;
hm = new HashMap<>();
// 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");
// Store in HashMap
hm.put(temp.lb, temp.ub - temp.lb + 1);
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");
// Store in HashMap
hm.put(temp.lb, temp.ub - temp.lb + 1);
}
void deallocate(int s)
{
// Invalid reference, as this was never allocated
if (!hm.containsKey(s)) {
System.out.println("Sorry, invalid free request");
return;
}
// Get the list which will track free blocks
// of this size
int x = (int)Math.ceil(Math.log(hm.get(s))
/ Math.log(2));
int i, buddyNumber, buddyAddress;
// Add it to the free list
arr[x].add(new Pair(s, s + (int)Math.pow(2, x) - 1));
System.out.println("Memory block from " + s + " to "
+ (s + (int)Math.pow(2, x) - 1) + " freed");
// Calculate it's buddy number and buddyAddress. The
// base address is implicitly 0 in this program, so no
// subtraction is necessary for calculating buddyNumber
buddyNumber = s / hm.get(s);
if (buddyNumber % 2 != 0) {
buddyAddress = s - (int)Math.pow(2, x);
}
else {
buddyAddress = s + (int)Math.pow(2, x);
}
// Search in the free list for buddy
for (i = 0; i < arr[x].size(); i++) {
// This indicates the buddy is also free
if (arr[x].get(i).lb == buddyAddress) {
// Buddy is the block after block
// with this base address
if (buddyNumber % 2 == 0) {
// Add to appropriate free list
arr[x + 1].add(new Pair(s, s
+ 2 * ((int)Math.pow(2, x)) - 1));
System.out.println("Coalescing of blocks starting at "
+ s + " and "
+ buddyAddress + " was done");
}
// Buddy is the block before block
// with this base address
else {
// Add to appropriate free list
arr[x + 1].add(new Pair(buddyAddress,
buddyAddress + 2 * ((int)Math.pow(2, x))
- 1));
System.out.println("Coalescing of blocks starting at "
+ buddyAddress + " and "
+ s + " was done");
}
// Remove the individual segments
// as they have coalesced
arr[x].remove(i);
arr[x].remove(arr[x].size() - 1);
break;
}
}
// Remove entry from HashMap
hm.remove(s);
}
public static void main(String args[]) throws IOException
{
int initialMemory = 0, type = -1, val = 0;
// Uncomment below section for interactive I/O
/*Scanner sc=new Scanner(System.in);
initialMemory = sc.nextInt();
Buddy obj=new Buddy(initialMemory);
while(true)
{
type = sc.nextInt();
if(type==-1)
break;
else if(type==1)
{
val=sc.nextInt();
obj.allocate(val);
}
else
{
val=sc.nextInt();
obj.deallocate(val);
}
}*/
initialMemory = 128;
Buddy obj = new Buddy(initialMemory);
obj.allocate(16);
obj.allocate(16);
obj.allocate(16);
obj.allocate(16);
obj.deallocate(0);
obj.deallocate(9);
obj.deallocate(32);
obj.deallocate(16);
}
}
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;
// Hashmap to store the starting
// address and size of allocated segment
// Key is starting address, size is value
Dictionary<int, int> hm;
// Else compiler will give warning
// about generic array creation
Buddy(int s)
{
size = s;
hm = new Dictionary<int, int>();
// 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");
// Store in Dictionary
hm.Add(temp.lb, temp.ub - temp.lb + 1);
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");
// Store in Dictionary
hm.Add(temp.lb, temp.ub - temp.lb + 1);
}
void deallocate(int s)
{
// Invalid reference,
// as this was never allocated
if (!hm.ContainsKey(s))
{
Console.WriteLine("Sorry, invalid free request");
return;
}
// Get the list which will track free blocks
// of this size
int x = (int)Math.Ceiling(Math.Log(hm[s]) /
Math.Log(2));
int i, buddyNumber, buddyAddress;
// Add it to the free list
arr[x].Add(new Pair(s, s +
(int)Math.Pow(2, x) - 1));
Console.WriteLine("Memory block from " + s +
" to " + (s +
(int)Math.Pow(2, x) - 1) + " freed");
// Calculate it's buddy number and
// buddyAddress. The base address is
// implicitly 0 in this program,
// so no subtraction is necessary for
// calculating buddyNumber
buddyNumber = s / hm[s];
if (buddyNumber % 2 != 0)
{
buddyAddress = s - (int)Math.Pow(2, x);
}
else
{
buddyAddress = s + (int)Math.Pow(2, x);
}
// Search in the free list for buddy
for (i = 0; i < arr[x].Count; i++)
{
// This indicates the buddy is also free
if (arr[x][i].lb == buddyAddress)
{
// Buddy is the block after block
// with this base address
if (buddyNumber % 2 == 0)
{
// Add to appropriate free list
arr[x + 1].Add(new Pair(s, s + 2 *
((int)Math.Pow(2, x)) - 1));
Console.WriteLine("Coalescing of blocks starting at " +
s + " and " + buddyAddress + " was done");
}
// Buddy is the block before block
// with this base address
else
{
// Add to appropriate free list
arr[x + 1].Add(new Pair(buddyAddress,
buddyAddress +
2 * ((int)Math.Pow(2, x)) - 1));
Console.WriteLine("Coalescing of blocks starting at " +
buddyAddress + " and " + s + " was done");
}
// Remove the individual segments
// as they have coalesced
arr[x].RemoveAt(i);
arr[x].RemoveAt(arr[x].Count - 1);
break;
}
}
// Remove entry from Dictionary
hm.Remove(s);
}
// Driver Code
public static void Main(String []args)
{
int initialMemory = 0;
initialMemory = 128;
Buddy obj = new Buddy(initialMemory);
obj.allocate(16);
obj.allocate(16);
obj.allocate(16);
obj.allocate(16);
obj.deallocate(0);
obj.deallocate(9);
obj.deallocate(32);
obj.deallocate(16);
}
}
// This code is contributed by 29AjayKumar
Producción
Memory from 0 to 15 allocate Memory from 16 to 31 allocated Memory from 32 to 47 allocate Memory from 48 to 63 allocated Memory block from 0 to 15 freed Sorry, invalid free request Memory block from 32 to 47 freed Memory block from 16 to 31 freed Coalescing of blocks starting at 0 and 16 was done
Complejidad de tiempo:
como ya se discutió en el conjunto 1, la complejidad de tiempo de la asignación es O(log(n)) . Para la desasignación, en el peor de los casos, todos los bloques asignados pueden ser de tamaño 1 unidad, lo que requerirá tiempo O(n) para escanear la lista en busca de fusión. Sin embargo, en la práctica, es muy poco probable que ocurra tal asignación, por lo que generalmente es mucho más rápido que el tiempo lineal.