Revisión del 20:38 27 dic 2011

En este tipo de sistemas, las particiones para cada proceso se van creando a medida que son asignadas al procesador. Tiene como ventaja principal que evitamos el desperdicio de memoria dentro de cada bloque ya que cada uno está hecho a medida para el proceso que contiene. Por el contrario, una vez que un proceso ha concluido, su partición se queda en desuso y sería necesario aplicar algoritmos de desfragmentación de memoria(supone un alto coste de rendimiento) para poder unificar todas las partes que han quedado libres y así reciclar las particiones que quedaron huérfanas. Otra forma de obtener particiones de mayor tamaño es unificar dos o más huecos adyacentes en uno sólo.

Ejemplo:

 _                                 _
|_| P1 = 3KB                      |_| P1 = 3KB   
|_| P2 = 1KB                      |_| P2 = 1KB
|_| P3 = 6KB    => Finaliza P3 => |_| Libre = 6KB
| |                               | |
|_| P4 = 31KB                     |_| P4 = 31KB
| |                               | |
|_| Libre = 21KB                  |_| Libre = 21KB

Si un nuevo proceso P5 requiriese 24KB de memoria, no podrían serle asignados, ya que los huecos no son contiguos y para disponer de los 27KB libres en total habría que realizar previamente una desfragmentación.

Elementos de administración

• Mapas de bits: Dividiendo la memoria en bloques (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia ya que cuanto mayores sean menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

• Listas de control: Se almacena en una lista el tamaño de los huecos y las posiciones de memoria entre las que se encuentran comprendidos, así como su estado (asignado o libre).

Criterios de asignación

Primer ajuste

Consiste en asignar el primer hueco disponible que tenga un espacio suficiente para almacenar el programa. Las dos principales desventajas son su alto desperdicio interno, y el elevado uso de las primeras posiciones de memoria. Este último inconveniente repercute negativamente en la circuitería, debido a que se produce un mayor desgaste en dichas posiciones.

Ejemplo: Suponiendo una memoria principal de 32 KB.

    | H0 | t | M |
-------------------
P1  | 0  | 5 | 6 |
P2  | 1  | 3 | 6 |
P3  | 2  | 5 | 8 |
P4  | 3  | 1 | 7 |
P5  | 4  | 2 | 7 |
P6  | 5  | 2 | 5 |

Solución:

                        0-5
            P1  <---|---|---|---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |    
                          6-11
            P2  |   <---|---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |       
                                12-19
            P3  |   |   <---|---|---|---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |       
                            20-26    
            P4  |   |   |   <--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |      
                                  20-26
            P5  |   |   |   |   <---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   
                                       0-4             
            P6  |   |   |   |   |   <---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   
           -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
                0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20

Siguiente ajuste

Se continúa a partir de la posición de la última asignación realizada.Es muy probable que haya un hueco a partir de esa posición, reduciendo la longitud de la búsqueda. De esta forma se resuelve el inconveniente de usar en exceso las primeras posiciones de la memoria. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

Ejemplo: Suponiendo una memoria principal de 32 KB.

   | H0 | t | M |
-------------------
P1  | 0  | 5 | 6 |
P2  | 1  | 3 | 6 |
P3  | 2  | 5 | 8 |
P4  | 3  | 1 | 7 |
P5  | 4  | 2 | 7 |
P6  | 5  | 2 | 5 |

Solución:

                       0-5
           P1  <---|---|---|---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |    
                         6-11
           P2  |   <---|---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |       
                               12-19
           P3  |   |   <---|---|---|---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |       
                           20-26    
           P4  |   |   |   <--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |      
                                 20-26
           P5  |   |   |   |   <---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   |   
                                     27-31             
           P6  |   |   |   |   |   <---|--->   |   |   |   |   |   |   |   |   |   |   |   |   |   
          -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
               0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20

DUDA:

Es evidente que cuando llega el P5 se necesitan 7 unidades de memoria, y éstas no están disponibles en el hueco de 27 a 31 (ahí solo hay 4) por lo que da la vuelta, vuelve a comenzar y lo asigna al primero que encuentra, que resulta ser casualmente, el 20-26. --fernandoenzo 22:14 19 dic 2011 (UTC)

Mejor ajuste

Consiste en asignarle al proceso el hueco con menor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja menos espacio sin utilizar. Su mayor inconveniente es su orden de complejidad (orden lineal, O(n)) debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente). Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante sera del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

Peor ajuste

Al contrario que el criterio anterior, se busca el hueco con mayor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar, y se corta de él el trozo necesario (así la porción sobrante será del mayor tamaño posible y será más aprovechable). Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste (debido a la longitud de las búsquedas) y la fragmentación no resulta demasiado eficiente.

Ajuste rápido

Mediante listas de control, se agrupan los huecos disponibles según su tamaño (0 < t < 10, 10 < t < 20, etc.). De esta manera, cuando se necesite un hueco, se seleccionarán los del grupo del tamaño que corresponda. En el caso de que haya varios huecos disponibles, se seleccionará uno en base a cualquiera de los criterios anteriores. Cuando se encuentre un hueco lo suficientemente grande se cortará la parte necesaria y se deja el resto en la lista que le corresponda.

Organización de los huecos en el ajuste rápido:

 Punteros a listas       Lista de huecos
    según tamaño
 __________________     
|                  |     _____     _____     _____
|    0 < t < 10    |--->|_____|-->|_____|-->|_____|  
|__________________|    
|                  |     _____     _____ 
|   10 < t < 20    |--->|_____|-->|_____| 
|__________________| 
|                  |
|       ...        |
|__________________|
|                  |     _____
|      t < 200     |--->|_____|
|__________________|

Método de los compañeros

Es una variante del ajuste rápido, en el que los huecos se dividen en potencias de 2: 2¹, 2², ..., 2^k. No es un método usado en la práctica, ya que al realizar redondeos a potencias de 2, se produce un elevado desperdicio interno.