Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Página con listado de personas que han contribuido

2012-01-26T21:19:19Z

Javgarang:

A continuación, la lista de usuarios/as de la Universidad de Sevilla que han contribuido a la wiki. Si ponéis tu usuario/a estás solicitando al profesor que evalúe tus contribuciones a la wiki para la subida de notas de hasta 2 puntos posible:

* luigarhor
* rafperper
* sergaralo
* josalgrod1
* felgaroje
* luimunlei
* [https://1984.lsi.us.es/wiki-ssoo/index.php/Usuario:Lorruimor Lorruimor]
* albsolnog
* framorexp
* javgarang

Discos Magnéticos

2012-01-21T13:24:18Z

Javgarang:

== Arquitectura de los discos magnéticos ==

Los discos magnéticos están formados por varios discos (desde 2 hasta 7) de material magnético montados sobre el mismo eje, los cuales se mantienen girando a una velocidad constante. Estos discos están recorridos, cada uno, por 2 cabezales magnéticos que no llegan a tocar el disco (están separados unos 3 nanómetros debido a una delgada capa de aire formada por la rotación del disco, de hecho si lo tocan se produce un error conocido como aterrizaje del cabezal) y que leen y escriben datos en el disco creando puntos de campo magnético.

En esta imagen se muestran los componentes de un disco duro magnético:

[[Archivo:componentes_HD_comentados.png]]

= Partes del disco magnético =

La superficie del disco magnético se divide en la siguientes partes:

* Pista (''track'', en inglés): Zona a la que accede el cabezal si este se queda fijo en una posición y el disco sigue girando. Si el cabezal se tratara de un lápiz, la pista sería la zona que el cabeza dibuja sobre el disco (que se trataría de una circunferencia). Hay que tener en cuenta que las pistas más cercanas al centro del disco son de menor tamaño al tener menor radio la circunferencia.
* Sector: Es una subdivisión de una pista (track) en un disco magnético. Cada sector almacena una cantidad fija de datos.
* Cilindro: Conjunto de sectores a los que el conjunto de cabezales pueden acceder desde una posición. Un cilindro está compuesto por un conjunto de sectores.

[[Archivo:Sin_título.png]][[Archivo:Estructura_disco.png|Estructura de un disco óptico|right]]

= Prestaciones de un disco duro magnético =

Las prestaciones de un disco se pueden medir mediante los siguientes indicadores:

* Capacidad, cantidad de unidades de información que se pueden almacenar en el disco.
* Revoluciones por minuto (RPM), velocidad constante a la que gira el disco magnético.
* Tiempo de arranque del motor, se trata del tiempo que tarda el motor en hacer que el disco comience a girar a velocidad constante.
* Tiempo de accesos, tanto para operaciones de lectura como escritura:
** Tiempo de búsqueda, se trata del tiempo que tarda el cabezal en desplazarse de una pista a otra.
** Demora de rotación, se trata del tiempo que tarda en pasar un sector por delante del cabezal.
** Tiempo de transmisión, se trata del tiempo que toma la transferencia de datos del dispositivo al gestor de dispositivo.

= Recursos multimedia =
http://www.youtube.com/watch?v=Wiy_eHdj8kg&feature=player_embedded

Solución Ejercicio clase Mejor Ajuste Dinámico

2011-12-17T16:49:27Z

Javgarang: correción del ejercicio

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

SO multiprogramables con particiones fijas

2011-12-11T20:38:24Z

Javgarang:

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:

[[solución mejor ajuste estático|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)

[[solución primer ajuste|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|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.

SO multiprogramables con particiones fijas

2011-12-11T20:35:50Z

Javgarang:

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:

[[solución mejor ajuste estático|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)

[[solución primer ajuste|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|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 es 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.

Solución de los ejercicios de concurrencia

2011-11-23T21:26:49Z

Javgarang: corrección de la numeración del tiempo

== Ejercicio 1==

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| #1| | | | | | | | |
H1 |<--|---|---| | | |---|---|---| | | |---|---|-->| | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| #2| #3| #4| #1|
H2 | | | |<--|---|---| | | |---|---|---| | | |---|---|---|---|---|---|---|-->|
| | | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Algunas observaciones:
* Los hilos '''no''' comparten la variable ''i''. Esta variable se trata de una variable local, por tanto, no es una variable que ambos hilos compartan. Únicamente las variables globales son compartidas por dos o más hilos.
* Al ser los cerrojos un control de concurrencia de espera activa, se comprueba continuamente la condición que nos permite acceder a la sección crítica.

--[[Usuario:Pneira|Pneira]] 07:33 10 may 2011 (UTC)

== Ejercicio 2==

| #1| #2| #3| | | | #4| #5| #1| | | | #2| #2| #2| | |
H1 |<--|---|---| | | |---|---|---| | | |---|---|---| | |
| | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #3| #4| | | | #5| #1|
H2 | | | |<--|---|---| | | |---|---|---| | | |---|---|
| | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

| | #2| #3| #4| | | | #5| #1| |
H1 | |---|---|---| | | |---|-->| |
| | | | | | | | | | |
| #2| | | | #3| #4| #5| | | #1|
H2 |---| | | |---|---|---| | |--->
| | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|
17 18 19 20 21 22 23 24 25 26 27

Explicación:

En este ejercicio la implementación de cerrojos no resuelve el problema de concurrencia (véase el instante 22, en el que ambos hilos están en la sección crítica).

El problema se debe, como se comentó en clase, a que la comprobación del valor del cerrojo y el establecimiento de su valor debe ser una '''operación atómica'''. Sin embargo, en el instante de tiempo 17 se comprueba el valor del cerrojo pero no se establece el nuevo valor. Es decir, habría que emplear una operación que evite que quedemos entre la comprobación del valor del cerrojo y su modificación.

--[[Usuario:Pneira|Pneira]] 17:06 23 nov 2011 (UTC)

== Ejercicio 3==
Al tener un quantum de únicamente dos unidades, el planificador cambia de proceso antes de actualizar el valor del cerrojo, lo que provoca que se produzca una situación de concurrencia.

Discusión:Monitores

2011-11-22T19:22:37Z

Javgarang:

== Ejemplo en Java ==

Ejemplo de sincronización mediante monitores con 5 hilos que modifican dos variables. Cada hilo incrementa las dos variables una unidad. El hilo principal va mostrando el contenido de las variables. Si quitamos la clausula synchronized podemos ver como las variables no se incrementan a la vez.

<source lang="java">
public class Principal {
public static void main(String[]args){
RecursoCompartido c = new RecursoCompartido();
for(int i=0;i<5;i++){
new Hilo(c);
}
while(true){
c.mostrar();
try{
Thread.sleep(20);
}catch(InterruptedException e){}
}
}
}
class Hilo extends Thread{
static int i=0;
int h;
RecursoCompartido c;
public Hilo(RecursoCompartido c){
this.setDaemon(true);
this.c=c;
h=i++;
this.start();
}
public void run(){
while(true){
c.incrementar();
//System.out.println("Ahora se está ejecutando el hilo "+h);
try{
sleep(20);
}catch(InterruptedException e){

}
}
}
}

class RecursoCompartido{
private int a = 0;
private int b = 0;

public synchronized void incrementar(){
a++;
b++;
}
public void mostrar(){
System.out.println("a: "+a+"\tb: "+b);
}
}

</source>

Para ejecutar el programa desde la linea de comandos:

1) Copiar todas las clases en un mismo archivo de texto y guardarlo como Principal.java

2) Compilar el codigo con la instrucción "javac Principal.java"

3) Ejecutar el archivo class creado con "java Principal"

4) Para parar el programa usar "Control+c"

Discusión:Monitores

2011-11-22T13:07:10Z

Javgarang:

== Ejemplo en Java ==

Ejemplo de sincronización mediante monitores con 5 hilos que modifican dos variables. Cada hilo incrementa las dos variables una unidad. El hilo principal va mostrando el contenido de las variables. Si quitamos la clausula synchronized podemos ver como las variables no se incrementan a la vez.

<source lang="java">
public class Principal {
public static void main(String[]args){
RecursoCompartido c = new RecursoCompartido();
for(int i=0;i<5;i++){
new Hilo(c);
}
while(true){
c.mostrar();
try{
Thread.sleep(20);
}catch(InterruptedException e){}
}
}
}
class Hilo extends Thread{
static int i=0;
int h;
RecursoCompartido c;
public Hilo(RecursoCompartido c){
this.setDaemon(true);
this.c=c;
h=i++;
this.start();
}
public void run(){
while(true){
c.incrementar();
//System.out.println("Ahora se está ejecutando el hilo "+h);
try{
sleep(20);
}catch(InterruptedException e){

}
}
}
}

class RecursoCompartido{
private int a = 0;
private int b = 0;

public synchronized void incrementar(){
a++;
b++;
}
public void mostrar(){
System.out.println("a: "+a+"\tb: "+b);
}
}

</source>

Para ejecutar el programa desde la linea de comandos:

1) Copiar todas las clases en un mismo archivo de texto y guardarlo como Principal.java

2) Compilar el codigo con la instrucción "javac Princiapal.java"

3) Ejecutar el archivo class creado con "java Principal"

4) Para parar el programa usar "Control+c"

Discusión:Monitores

2011-11-22T13:06:17Z

Javgarang: Instrucciones para ejecutar el programa desde la línea de comandos

== Ejemplo en Java ==

Ejemplo de sincronización mediante monitores con 5 hilos que modifican dos variables. Cada hilo incrementa las dos variables una unidad. El hilo principal va mostrando el contenido de las variables. Si quitamos la clausula synchronized podemos ver como las variables no se incrementan a la vez.

<source lang="java">
public class Principal {
public static void main(String[]args){
RecursoCompartido c = new RecursoCompartido();
for(int i=0;i<5;i++){
new Hilo(c);
}
while(true){
c.mostrar();
try{
Thread.sleep(20);
}catch(InterruptedException e){}
}
}
}
class Hilo extends Thread{
static int i=0;
int h;
RecursoCompartido c;
public Hilo(RecursoCompartido c){
this.setDaemon(true);
this.c=c;
h=i++;
this.start();
}
public void run(){
while(true){
c.incrementar();
//System.out.println("Ahora se está ejecutando el hilo "+h);
try{
sleep(20);
}catch(InterruptedException e){

}
}
}
}

class RecursoCompartido{
private int a = 0;
private int b = 0;

public synchronized void incrementar(){
a++;
b++;
}
public void mostrar(){
System.out.println("a: "+a+"\tb: "+b);
}
}

</source>

Para ejecutar el programa desde la linea de comandos:

1) Copiar todas las clases en un mismo archivo de texto y guardarlo como Principal.java
2) Compilar el codigo con la instrucción "javac Princiapal.java"
3) Ejecutar el archivo class creado con "java Principal"
4) Para parar el programa usar "Control+c"

Cerrojos

2011-11-15T20:23:08Z

Javgarang: corrección de la explicación del ejemplo de implementación de cerrojo

= Ejemplo de implementación =

El siguiente código sería un posible ejemplo del uso de control de concurrencia mediante cerrojos:

<source lang="c">
int cerrojo = 0; /* Inicializamos la variable cerrojo. Esto sería sólo válido para
hilos, ya que los procesos no comparten espacio de memoria */

while(cerrojo == 1); // Protocolo de
cerrojo = 1; // entrada

... // Sección crítica

cerrojo = 0; // Protocolo de salida
</source>

Sin embargo, esto es problemático: Supongamos que tenemos únicamente un proceso con dos hilos (Hx y Hy) y el planificador retire al hilo Hx justo antes de ejecutarse la instrucción ''cerrojo = 1;''. El hilo Hy ejecuta su código, entra en la sección crítica (Esto puede ocurrir ya que cerrojo sigue a 0) y el planificador le retira el uso del procesador dentro de ésta. A continuación, se le vuelve a asignar el procesador a Hx.

De esta forma, tenemos a dos hilos ejecutando código de la sección crítica. Para evitar este problema, debemos implementar los protocolos de entrada y salida de forma que se ejecuten en una sola instrucción, con lo cual o el planificador retira el uso del procesador antes de esta instrucción, o sino lo retira después de haberla ejecutado.

= Cerrojos mediante instrucciones atómicas =

Podemos implementar cerrojos mediante instrucciones especiales de comprobación y puesta a 0 y 1.

<source lang="c">
int cerrojo = 0;

void lock() {
while (__sync_lock_test_and_set(&cerrojo, 1));
}

void unlock() {
__sync_lock_release(&cerrojo);
}
</source>

El método lock comprueba mediante __sync_locktest_and_set(&cerrojo,1) el valor del cerrojo: si es 0, cambia el valor del cerrojo a 1 y devuelve 0, por tanto, se sale del while y entra en sección crítica; si es 1, devuelve 1 y continúa comprobando el valor, por tanto, no entra en situación crítica hasta que cambie el valor del cerrojo.

El método unlock, mediante _sync_lock_release(&cerrojo), cambia el valor del cerrojo a 0.

* http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html
* http://stackoverflow.com/questions/1383363/is-my-spin-lock-implementation-correct-and-optimal

Monitores

2011-11-15T12:47:30Z

Javgarang:

Idea desarrollada en los años 70 Brinch-Hansen y Hoare <ref>http://java.sun.com/developer/Books/performance2/chap4.pdf</ref>que notaron los siguientes problemas con respecto al uso de los semáforos:

* Los semáforos son difíciles de usar. Es frecuente que el programador cometa errores al emplearlos.
* El compilador no asiste al programador en el desarrollo de programas concurrentes mediante semáforos, pues no ofrece ningún tipo de validación en tiempo de compilación.
* No hay nada que obligue a usarlos. Puede suceder que el programador los necesite y lo desconozca
* Son independientes del recurso compartido

Los monitores tienen que estar integrados en el lenguaje de programación.

== Definición ==
Un monitor es una estructura del lenguaje cuyas principales características son:

* Los datos son privados.
* Ofrecen una serie de métodos públicos para acceder a dichos datos.
* En cada momento sólo puede haber un proceso activo en algún método del monitor, es decir, ejecutando código de esos métodos públicos del monitor. Seria equivalente a decir que el recurso que queremos compartir se declara como monitor. Los procesos que usan el monitor son independientes unos de otros y cuando deseen usar el recurso, llamarán a los métodos del monitor que implementen la operación que se desea ejecutar.

Permiten organizar procesos en espera mediante:

* Variables de condición: lista de procesos inicialmente vacía.
* Primitivas: ''wait(c)'', añade el proceso p invocante a c y proceso p bloquea; ''signal(c)'', selecciona a uno de los procesos en c y lo pone en preparado.

<source lang="java">

class recursoCompartido {

public int get(void);
public void set(int valor);
private int recursoCompartido;
private Semaforo s = 1;

public int get(void){
int ret;
down(s);
ret = recursoCompartido;
up(s);
return ret;
}

public void set(int valor){
down(s);
recursoCompartido = valor;
up(s);
}
}

</source>

Como vemos, los monitores se implementan con semáforos, son una abstracción de los mismos.

== Ejemplo en Java ==

Ejemplo de sincronización mediante monitores con 5 hilos que modifican dos variables. Cada hilo incrementa las dos variables una unidad. El hilo principal va mostrando el contenido de las variables. Si quitamos la clausula synchronized podemos ver como las variables no se incrementan a la vez.

<source lang="java">
public class Principal {
public static void main(String[]args){
Cont c=new Cont();
for(int i=0;i<5;i++){
new Hilo(c);
}
while(true){
c.mostrar();
try{
Thread.sleep(20);
}catch(InterruptedException e){}
}
}
}
class Hilo extends Thread{
static int i=0;
int h;
Cont c;
public Hilo(Cont c){
this.setDaemon(true);
this.c=c;
h=i++;
this.start();
}
public void run(){
while(true){
c.incrementar();
//System.out.println("Ahora se está ejecutando el hilo "+h);
try{
sleep(20);
}catch(InterruptedException e){

}
}
}
}

class Cont{
int a=0;
int b=0;
synchronized public void incrementar(){
a++;
b++;
}
public void mostrar(){
System.out.println("a: "+a+"\tb: "+b);
}
}

</source>

== Fuentes ==
<references/>

Monitores

2011-11-15T12:43:52Z

Javgarang:

Idea desarrollada en los años 70 Brinch-Hansen y Hoare <ref>http://java.sun.com/developer/Books/performance2/chap4.pdf</ref>que notaron los siguientes problemas con respecto al uso de los semáforos:

* Los semáforos son difíciles de usar. Es frecuente que el programador cometa errores al emplearlos.
* El compilador no asiste al programador en el desarrollo de programas concurrentes mediante semáforos, pues no ofrece ningún tipo de validación en tiempo de compilación.
* No hay nada que obligue a usarlos. Puede suceder que el programador los necesite y lo desconozca
* Son independientes del recurso compartido

Los monitores tienen que estar integrados en el lenguaje de programación.

== Definición ==
Un monitor es una estructura del lenguaje cuyas principales características son:

* Los datos son privados.
* Ofrecen una serie de métodos públicos para acceder a dichos datos.
* En cada momento sólo puede haber un proceso activo en algún método del monitor, es decir, ejecutando código de esos métodos públicos del monitor. Seria equivalente a decir que el recurso que queremos compartir se declara como monitor. Los procesos que usan el monitor son independientes unos de otros y cuando deseen usar el recurso, llamarán a los métodos del monitor que implementen la operación que se desea ejecutar.

Permiten organizar procesos en espera mediante:

* Variables de condición: lista de procesos inicialmente vacía.
* Primitivas: ''wait(c)'', añade el proceso p invocante a c y proceso p bloquea; ''signal(c)'', selecciona a uno de los procesos en c y lo pone en preparado.

<source lang="java">

class recursoCompartido {

public int get(void);
public void set(int valor);
private int recursoCompartido;
private Semaforo s = 1;

public int get(void){
int ret;
down(s);
ret = recursoCompartido;
up(s);
return ret;
}

public void set(int valor){
down(s);
recursoCompartido = valor;
up(s);
}
}

</source>

Como vemos, los monitores se implementan con semáforos, son una abstracción de los mismos.

== Ejemplo en Java ==

Ejemplo de sincronización mediante monitores en el que 5 hilos modifican dos variables. El hilo principal va mostrando el contenido de las variables. Si quitamos la clausula synchronized podemos ver como las variables no se modifican a la vez.

<source lang="java">
public class Principal {
public static void main(String[]args){
Cont c=new Cont();
for(int i=0;i<5;i++){
new Hilo(c);
}
while(true){
c.mostrar();
try{
Thread.sleep(20);
}catch(InterruptedException e){}
}
}
}
class Hilo extends Thread{
static int i=0;
int h;
Cont c;
public Hilo(Cont c){
this.setDaemon(true);
this.c=c;
h=i++;
this.start();
}
public void run(){
while(true){
c.incrementar();
//System.out.println("Ahora se está ejecutando el hilo "+h);
try{
sleep(20);
}catch(InterruptedException e){

}
}
}
}

class Cont{
int a=0;
int b=0;
synchronized public void incrementar(){
a++;
b++;
}
public void mostrar(){
System.out.println("a: "+a+"\tb: "+b);
}
}

</source>

== Fuentes ==
<references/>

Criterios de planificación

2011-10-31T18:04:12Z

Javgarang: Correción de los tiempos en los que saltan los planificadores en los ejemplos y corrección del ejemplo turno rotatorio con compensación

=4.3.1 Métodos no apropiativos =

El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real.
En los métodos no apropiativos, si el proceso se bloquea o entra en estado bloqueado, el procesador quedará sin uso durante todo ese tiempo, pues estaba dedicado/reservado para ése proceso.

== Estocástico ==

Se selecciona aleatoriamente el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitividad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

== Por orden de llegada (First In, First Out: FIFO) ==

Se selecciona el proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que presentarán un alto índice de penalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_| t = tiempo de ejecución
Cálculos _t__|_3__|_5__|_2__|_5__|_5__| T = tiempo de terminación (Instante de
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| terminación - Instante de lanzamiento)
_z__|_1__|_7/5|_7/2|_6/5|_8/5| z = índice de penalización

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones.
Para procesos largos puede presentar un índice de penalización elevado: Si se tienen muchos procesos cortos, el de mayor duración puede quedar en espera indefinidamente. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
planif. &---|---|---&---|---&---|---|---|---|---&---|---|---|---|---&---|---|---|---|---&
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|

== Basado en índice de penalización ==

Se selecciona el proceso que tendrá el índice de penalización <math>I_p=\frac{T}{t}=\frac{H_f-H_0}{t}</math> de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es <math>O(n)</math>.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>
planif.&---|---|---&---|---|---|---|---&---|---|---|---&---|---|---&---|---|---|---|---&
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''7/5'''|_1__|____|____|
z(8)|_1__|_7/5|_'''9/4'''|_4/3|_7/5|
z(12)|_1__|_7/5|_9/4|_'''8/3'''|11/5| z = índice de penalización
z(15)|_1__|_7/5|_9/4|_8/3|'''14/5'''|
z(20)|_1__|_7/5|_9/4|_8/3|14/5|

=4.3.2 Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Se emplea fundamentalmente en sistemas operativos [[Multiprogramación|multiprogramables]].

Con métodos apropiativos, la decisión de planificación tiene lugar si:

* El proceso activo pasa a estado bloqueado.
* El proceso activo termina su ejecución.
* Se lanza un nuevo proceso.
* El proceso activo agota el tiempo máximo de asignación del procesador (veáse ''Turno Rotatorio'').

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución. Si hay un proceso en estado preparado que requiere menos tiempo de ejecución del que le falta al actual, se le retira el procesador al actual proceso y se le asigna al nuevo. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
Planif.|---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---&
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__| z = índice de penalización
_z__|_1__|_8/5|_1__|14/8|_1__|

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* '''Índice estático''': Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
* '''Índice dinámico''': Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos, aumentándola cuando un proceso está a la espera o disminuyéndola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige al recién llegado; si no, lo inserta en la cola según su prioridad.
Cuando hay varios procesos con la misma prioridad se pueden aplicar diversos criterios, como seguir el orden de llegada a la cola de preparados, o el que necesite menos tiempo para acabar entre otros.

El orden es siempre O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| p = prioridad estática
_p__|_0__|-20_|_4__|_10_|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Planif. |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---&---|---|---|---|---|
-------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_6__|_4__|_6__|_12_| z = índice de penalización
_z__|_3__|_1__|_3__|12/7|

== Turno rotatorio ==

=== Turno rotatorio estricto (Round Robin: RR) ===

En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado ''quantum'', tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.

El tamaño del ''quantum'' es fundamental para determinar el comportamiento de este criterio de planificación.
Si el ''quantum'' empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, si el ''quantum'' empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos'', puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .

Si un proceso bloquea antes de consumir su ''quantum'' '''se le retira el procesador''' y se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.

Puesto que el reparto del procesador es estricto, los procesos recién lanzados deben de acceder al procesador lo antes posible, por tanto, se añaden inicialmente al principio de la cola. Si son varios los procesos que han sido lanzados, se ejecutaran por orden de llegada.

Este criterio se puede implementar con una cola, de manera que el orden de complejidad en la selección del proceso que pasa a estado activo es <math>O(1)</math>. Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| quantum = 1 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
Pc |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<xxx|---|---|---|xxx|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|
$ $---$---$---$---$---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_10_|_5__|_12_| z = índice de penalización
_z__|_5/2|10/4|_5/2|12/7|

=== Turno rotatorio con compensación ===

Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su '''quantum''', se reinserta en el 25% de la cola, contando desde el principio (dispondrá de otro quantum completo).
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_| Pa y Pc bloquean cada 1 unidad de tiempo
Datos del _H0_|_0__|_1__|_2__|_3__| El bloqueo se resuelve tras 2 unidades de tiempo
problema _t__|_2__|_4__|_2__|_7__| quantum = 2 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxxxxxx|---|---|---|---|---|xxxxxxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|xxxxxxx|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
$ $---$---|---$---$---$---|---$---$---|---$---|---$---|---$---$---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_9__|_6__|_12_| z = índice de penalización
_z__|_5/2|_9/4|_6/2|12/7|

=== Turno rotatorio con quantum dependiente del número de procesos ===

Otra variante se trata de emplear un '''quantum''' proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.

== Colas multinivel ==

En este tipo de criterio se mantienen múltiples colas con los procesos en estado preparado. Los procesos se clasifican en las colas según sus características, cada cola recibe un tratamiento distinto.

Un ejemplo sería el siguiente, compuesto de cuatro colas:

# Esta primera cola es para procesos que poseen mayor tiempo de ejecución, son los gestores de interrupción y los gestores de dispositivos (drivers). Hay que tomar los datos y almacenarlos en memoria lo antes posible para poder recoger más, aunque se posponga el procesamiento de dichos datos.
# En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
# Esta cola esta reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
## Cola de procesos interactivos, limitados por E/S.
## Cola de procesos por lotes, limitados por el procesador.

Las colas tienen prioridad según su número, por ejemplo mientras que haya procesos preparados en la primera cola, no se mira la segunda. Esto puede dar lugar a que si hay muchos procesos de gestión de dispositivos se degrade la eficiencia del sistema.

La primera cola esta implementada con una FIFO(no apropiativo), mientras que las colas 2 y 3 se basan en un sistema de RR (turno rotatorio).

=== Colas multinivel con realimentación (feedback)===

Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:

* Los procesos interactivos tienen más oportunidades de emplear el procesador.
* Los procesos por lotes disponen del procesador durante más tiempo.

Los procesos se asignan al procesador por turnos rotatorios, empleando un ''quantum'' dependiente de la cola en la que se encuentren. Los procesos que consumen el ''quantum'' asignado completamente un número determinado de veces pasan a colas en las que se asignan ''quantum'' mayores. Nótese que los procesos que no consumen su ''quantum'' muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con ''quantum'' menores, se les dan más oportunidades de ejecución.

Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:

* En la primera cola se le asignan un ''quantum'' de 2 unidades de tiempo a los procesos.
* En la segunda cola se le asignan un ''quantum'' de 1 unidad de tiempo a los procesos.

Si un proceso no consume el ''quantum'' asignado dos veces, pasa a la cola en la que en la se le asignan ''quantum'' de 1 unidad de tiempo.

Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con ''quantum'' de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un ''quantum'' de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un ''quantum'' de 1 unidad de tiempo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_| Pa y Pc bloquean cada 1 unidad de tiempo
Datos del _H0_|_0__|_1__|_2__|_3__| El bloqueo se resuelve tras 2 unidades de tiempo
problema _t__|_2__|_4__|_2__|_7__|
Colas multinivel: 1. Procesos interactivos (quantum = 1 unidad de tiempo)
2. Procesos por lotes (quantum = 2 unidad de tiempo)
Inicialmente todos los procesos van a la cola 2
Los procesos que no consuman su quantum al menos una vez pasan a la cola 1
Las colas implementan turno rotatorio estricto

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxxxxxx|---|---|---|---|---|xxxxxxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|xxx|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|xxxxxxx|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
$ $---$---|---$---$---$---|---$---$---|---$---|---$---|---$---$---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_4__|_9__|_6__|_12_| z = índice de penalización
_z__|_4/2|_9/4|_6/2|12/7|

Criterios de planificación

2011-10-25T18:02:45Z

Javgarang: Ejemplo cola multinivel con realimentacion

=4.3.1 Métodos no apropiativos =

El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real.
En los métodos no apropiativos, si el proceso se bloquea o entra en estado bloqueado, el procesador quedará sin uso durante todo ese tiempo, pues estaba dedicado/reservado para ése proceso.

== Estocástico ==

Se selecciona aleatoriamente el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitividad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

== Por orden de llegada (First In, First Out: FIFO) ==

Se selecciona el proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que presentarán un alto índice de penalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_| t = tiempo de ejecución
Cálculos _t__|_3__|_5__|_2__|_5__|_5__| T = tiempo de terminación (Instante de
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| terminación - Instante de lanzamiento)
_z__|_1__|_7/5|_7/2|_6/5|_8/5| z = índice de penalización

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones.
Para procesos largos puede presentar un índice de penalización elevado: Si se tienen muchos procesos cortos, el de mayor duración puede quedar en espera indefinidamente. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
planif. &---|---|---&---|---&---|---|---|---|---&---|---|---|---|---&---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|

== Basado en índice de penalización ==

Se selecciona el proceso que tendrá el índice de penalización <math>I_p=\frac{T}{t}=\frac{H_f-H_0}{t}</math> de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es <math>O(n)</math>.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>
planif.&---|---|---&---|---|---|---|---&---|---|---|---&---|---|---&---|---|---|---|---|
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''7/5'''|_1__|____|____|
z(8)|_1__|_7/5|_'''9/4'''|_4/3|_7/5|
z(12)|_1__|_7/5|_9/4|_'''8/3'''|11/5| z = índice de penalización
z(15)|_1__|_7/5|_9/4|_8/3|'''14/5'''|
z(20)|_1__|_7/5|_9/4|_8/3|14/5|

=4.3.2 Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Se emplea fundamentalmente en sistemas operativos [[Multiprogramación|multiprogramables]].

Con métodos apropiativos, la decisión de planificación tiene lugar si:

* El proceso activo pasa a estado bloqueado.
* El proceso activo termina su ejecución.
* Se lanza un nuevo proceso.
* El proceso activo agota el tiempo máximo de asignación del procesador (veáse ''Turno Rotatorio'').

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución. Si hay un proceso en estado preparado que requiere menos tiempo de ejecución del que le falta al actual, se le retira el procesador al actual proceso y se le asigna al nuevo. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
Planif.|---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---|
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__| z = índice de penalización
_z__|_1__|_8/5|_1__|14/8|_1__|

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* '''Índice estático''': Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
* '''Índice dinámico''': Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos, aumentándola cuando un proceso está a la espera o disminuyéndola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige al recién llegado; si no, lo inserta en la cola según su prioridad.
Cuando hay varios procesos con la misma prioridad se pueden aplicar diversos criterios, como seguir el orden de llegada a la cola de preparados, o el que necesite menos tiempo para acabar entre otros.

El orden es siempre O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| p = prioridad estática
_p__|_0__|-20_|_4__|_10_|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Planif. |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---|---|---|---|---|---|
-------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_6__|_4__|_6__|_12_| z = índice de penalización
_z__|_3__|_1__|_3__|12/7|

== Turno rotatorio ==

=== Turno rotatorio estricto (Round Robin: RR) ===

En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado ''quantum'', tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.

El tamaño del ''quantum'' es fundamental para determinar el comportamiento de este criterio de planificación.
Si el ''quantum'' empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, si el ''quantum'' empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos'', puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .

Si un proceso bloquea antes de consumir su ''quantum'' '''se le retira el procesador''' y se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.

Puesto que el reparto del procesador es estricto, los procesos recién lanzados deben de acceder al procesador lo antes posible, por tanto, se añaden inicialmente al principio de la cola.

Este criterio se puede implementar con una cola, de manera que el orden de complejidad en la selección del proceso que pasa a estado activo es <math>O(1)</math>. Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| quantum = 1 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
Pc |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<xxx|---|---|---|xxx|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|
$ $---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_10_|_5__|_12_| z = índice de penalización
_z__|_5/2|10/4|_5/2|12/7|

=== Turno rotatorio con compensación ===

Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su '''quantum''', se reinserta en el 25% de la cola, contando desde el principio (dispondrá de otro quantum completo).
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_| Pa y Pc bloquean cada 1 unidad de tiempo
Datos del _H0_|_0__|_1__|_2__|_3__| El bloqueo se resuelve tras 2 unidades de tiempo
problema _t__|_2__|_4__|_2__|_7__| quantum = 2 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxxxxxx|---|---|---|---|---|xxxxxxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---<xxxxxxx|---|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
$ $---$---|---$---$---|---$---$---$---|---$---|---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_8__|_8__|_12_| z = índice de penalización
_z__|_7/2|_9/4|_6/2|11/7|

=== Turno rotatorio con quantum dependiente del número de procesos ===

Otra variante se trata de emplear un '''quantum''' proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.

== Colas multinivel ==

En este tipo de criterio se mantienen múltiples colas con los procesos en estado preparado. Los procesos se clasifican en las colas según sus características, cada cola recibe un tratamiento distinto.

Un ejemplo sería el siguiente, compuesto de cuatro colas:

# Esta primera cola es para procesos que poseen mayor tiempo de ejecución, son los gestores de interrupción y los gestores de dispositivos (drivers). Hay que tomar los datos y almacenarlos en memoria lo antes posible para poder recoger más, aunque se posponga el procesamiento de dichos datos.
# En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
# Esta cola esta reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
## Cola de procesos interactivos, limitados por E/S.
## Cola de procesos por lotes, limitados por el procesador.

Las colas tienen prioridad según su número, por ejemplo mientras que haya procesos preparados en la primera cola, no se mira la segunda. Esto puede dar lugar a que si hay muchos procesos de gestión de dispositivos se degrade la eficiencia del sistema.

La primera cola esta implementada con una FIFO(no apropiativo), mientras que las colas 2 y 3 se basan en un sistema de RR (turno rotatorio).

=== Colas multinivel con realimentación (feedback)===

Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:

* Los procesos interactivos tienen más oportunidades de emplear el procesador.
* Los procesos por lotes disponen del procesador durante más tiempo.

Los procesos se asignan al procesador por turnos rotatorios, empleando un ''quantum'' dependiente de la cola en la que se encuentren. Los procesos que consumen el ''quantum'' asignado completamente un número determinado de veces pasan a colas en las que se asignan ''quantum'' mayores. Nótese que los procesos que no consumen su ''quantum'' muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con ''quantum'' menores, se les dan más oportunidades de ejecución.

Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:

* En la primera cola se le asignan un ''quantum'' de 2 unidades de tiempo a los procesos.
* En la segunda cola se le asignan un ''quantum'' de 1 unidad de tiempo a los procesos.

Si un proceso no consume el ''quantum'' asignado dos veces, pasa a la cola en la que en la se le asignan ''quantum'' de 1 unidad de tiempo.

Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con ''quantum'' de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un ''quantum'' de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un ''quantum'' de 1 unidad de tiempo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_| Pa y Pc bloquean cada 1 unidad de tiempo
Datos del _H0_|_0__|_1__|_2__|_3__| El bloqueo se resuelve tras 2 unidades de tiempo
problema _t__|_2__|_4__|_2__|_7__|
Colas multinivel: 1. Procesos interactivos (quantum = 1 unidad de tiempo)
2. Procesos por lotes (quantum = 2 unidad de tiempo)
Inicialmente todos los procesos van a la cola 2
Los procesos que no consuman su quantum al menos una vez pasan a la cola 1
Las colas implementan turno rotatorio estricto

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxxxxxx|---|---|---|---|---|xxxxxxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|xxx|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|xxxxxxx|---|---|---|xxxxxxxxxxxxxxxxxxx>---|---|---|---|---|
$ $---$---|---$---$---$---|---$---$---|---$---|---$---|---$---$---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_4__|_9__|_6__|_12_| z = índice de penalización
_z__|_4/2|_9/4|_6/2|12/7|