SO multiprogramables con particiones fijas

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

  • Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
  • Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

Criterios de asignación

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

Mejor ajuste estático

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

Ejemplo

Dada la siguiente configuración de procesos:

   | H0 |  t  | m(P)|
---------------------
P1 |  0 |  7  |  2  |  
P2 |  1 |  4  |  7  |
P3 |  2 |  5  |  8  |
P4 |  3 |  5  | 15  |
P5 |  4 |  3  |  3  |
P6 |  5 |  2  | 17  |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
|     |
|_____| M3 = 16 u.m.
|     |
|     |
|     | M4 = 32 u.m.
|_____|

La solución sería:

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

Otro ejemplo

Tenemos los siguientes procesos: m(P1) = 6KB, m(P2) = 1KB, m(P3) = 3KB, m(P4) = 31KB, m(P5) = 30KB;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera
consecutiva según el número del proceso y una memoria de 64 KB divididos en 4 huecos como sigue:

Ver solución

Primer ajuste

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

Ver solución

Ejemplo

Dada la siguiente configuración de procesos:

   | H0 |  t  | m(P)|
---------------------
P1 |  0 |  7  |  2  |  
P2 |  1 |  4  |  7  |
P3 |  2 |  5  |  8  |
P4 |  3 |  5  | 15  |
P5 |  4 |  3  |  3  |
P6 |  5 |  2  | 17  |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
|     |
|_____| M3 = 16 u.m.
|     |
|     |
|     | M4 = 32 u.m.
|_____|

La solución sería:

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

Mejor ajuste dinámico

Al quedar libre una partición, se asigna el mayor proceso que quepa en ella. Por tanto, es necesario que los procesos esperen indefinidamente a que la menor partición en la que quepan quede libre. Basta que haya una partición libre para que pueda ser asignado.

El principal inconveniente de este criterio es que los procesos que mayor desperdicio producen van a ser postergados indefinidamente. Complejidad: O(n).

Ejemplo

Dada la siguiente configuración de procesos:

   | H0 |  t  | m(P)|
---------------------
P1 |  0 |  7  |  2  |  
P2 |  0 |  4  |  7  |
P3 |  0 |  5  |  8  |
P4 |  1 |  5  | 15  |
P5 |  1 |  3  |  3  |
P6 |  1 |  2  | 17  |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
|     |
|_____| M3 = 16 u.m.
|     |
|     |
|     | M4 = 32 u.m.
|_____|

La solución sería:

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

Mejor ajuste dinámico con aplazamiento limitado

Es una variante del criterio anterior que evita el aplazamiento indefinido. Cuando queda una partición libre, se selecciona el mayor proceso que quepa en ella, pero se cuenta el nº de veces que un proceso se aplaza. Si se superan esas n veces (umbral), se le da paso.

Ejemplo

Dada la siguiente configuración de procesos:

   | H0 |  t  | m(P)|
---------------------
P1 |  0 |  7  |  2  |  
P2 |  0 |  4  |  7  |
P3 |  0 |  5  |  8  |
P4 |  1 |  5  |  6  |
P5 |  1 |  3  |  7  |
P6 |  1 |  2  |  5  |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
|     |
|_____| M3 = 16 u.m.
|     |
|     |
|     | M4 = 32 u.m.
|_____|

La solución sería:

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

Subparticiones

No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

Partición madre: tipo especial de partición que se puede dividir en múltiples particiones menores.

Otro ejemplo

Métodos de colocación en memoria

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

  • Montaje absoluto: El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.
  • Carga con reubicación: Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.
  • Reubicación dinámica: Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En tiempo de ejecución se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.
    • Reubicación dinámica parcial: Es una variante del anterior, en la que existe también un registro límite.

Mecanismos de protección de memoria

Es necesario proteger el SO frente a procesos; y proteger a los procesos entre sí.

  • Bits de protección : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura
  • Ampliación registros valla : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.