Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Criterios de planificación

2011-11-03T17:19:45Z

Manalerod: /* 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 por lotes, 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 acceder al procesador lo antes posible, por tanto, se les da oportunidad de ejecución por orden de llegada por delante de los procesos en la cola de procesos preparados. De esta manera, se evita que los procesos recién lanzados queden postergados indefinidamente.

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__|_7__|_9__|_6__|_12_| z = índice de penalización
_z__|_7/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 menor 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|

Índices de evaluación

2011-11-02T15:26:39Z

Manalerod: /* ¿Cómo se evalúa un criterio de planificación? */

= ¿Cómo se evalúa un criterio de planificación? =

En base a los siguientes parámetros:

* '''Throughput''' (tasa de transferencia, en castellano), indica la cantidad de procesos en estado activo por unidad de tiempo. Un throughput alto es un indicador de un buen planificador (se mide en nºprocesos/segundo).
* '''Latencia''', indica el tiempo que tarda un planificador de procesos en seleccionar qué proceso pasa a estado activo. Si el planificador toma mucho tiempo en decidir qué proceso pasa a estado activo, se dice que la latencia será alta (se mide en segundos).

Un buen planificador ofrecerá un throughput alto y una latencia baja.

Además, existen otros índices que nos permiten evaluar el planificador:

* '''Tiempo de ejecución''' (tejecución): Unidades de tiempo que requiere el proceso para finalizar su ejecución.
* '''Tiempo de terminación''' (Tterminación): Diferencia entre el instante de lanzamiento y el instante de terminación.
* '''Tiempo perdido''': T-t . Es el tiempo durante el cual un proceso no está asignado al procesador.
* '''Tiempo de inactividad''': Tiempo durante el cual el procesador está ocioso (''idle'', en inglés), es decir, que no tienen ningún proceso asignado.
* '''Tiempo del sistema''': Tiempo empleado por el [[planificador de procesos|planificador]] para la conmutación de procesos.
* '''Tiempo de espera''': Tiempo desde el instante de lanzamiento hasta que el proceso pasa a estado preparado (se suele despreciar).
* '''Índice de penalización''': <math>\frac{T}{t} = \frac{H_f-H_0}{t} = x</math>. Indica que un proceso ha tardado x-1 veces más en ejecutarse que si hubiera tenido el procesador en exclusividad y sin que se hubiese producido ningún bloqueo. Nótese que el índice de penalización crece rápidamente para procesos cuyo tiempo de ejecución es pequeño, mientras que para procesos con tiempo de ejecución mayores, lo hace de manera más suave.

Suponga el siguiente ejemplo, en el que hay dos procesos <math>P_x</math> y <math>P_y</math>, para ilustrar los índices definidos:

< indica que el proceso está preparado
> indica que el proceso ha finalizado su ejecución
$ indica que al proceso se le ha retirado el procesador
X indica la ejecución del planificador para la conmutación

| | | | | | |
Px <---|---$ |---> | |
Py | | <---> | | |
planificador | | X X | | |
|___|___|___|___|___|___|___
0 1 2 3 4 5 6

tiempo ->

Para el proceso Px:

* t = 3 : Indica que el proceso Px requiere 3 unidades de tiempo para ejecutarse.
* T = 4 : unidades de tiempo desde que se lanza hasta que se finaliza el proceso Px
* T-t = 1 : unidades de tiempo durante la cual el proceso Px no está asignado al procesador, por tanto, no progresa en su actividad.
* x = 4/3 = 1.34 : el proceso Px ha tardado un 34% de tiempo más en ejecutarse que si lo hubiera tenido en exclusividad (al tener que haber que compartido el procesador con Py).

En el ejemplo anterior, los tiempos de espera y del sistema se suponen despreciables (en la práctica no lo son, aunque son muy pequeños con respecto a los ilustrados).

Modelos de Diseño de Sistemas Operativos

2011-10-28T14:36:01Z

Manalerod: /* Tipos de Sistemas Operativos */

= 2.5. Modelos de Diseño de SSOO =

== Modos de operación del procesador ==

Para entender los modelos de diseño de los sistemas operativos, tenemos que hacer referencia a los modos de ejecución del procesador. El modo de ejecución del procesador indica qué conjunto de instrucciones y a qué recursos del procesador se puede acceder en un cierto instante de tiempo.

En la actualidad, un procesador ofrece como mínimo dos modos de operación(ejecución) que son:

* '''Modo supervisor''', que permite la ejecución de todo el conjunto de instrucciones que ofrece el procesador (no tiene ninguna relación con el modo "root" o administrador de algunos sistemas operativos).
* '''Modo usuario''', que tiene algunas restricciones de acceso a aspectos del procesador o de ejecución de instrucciones.

== Núcleo del sistema operativo ==

El núcleo del sistema operativo, también conocido por la terminología inglesa ''kernel'', es la parte más esencial del sistema operativo. Se trata de la capa visible del software más baja del sistema que provee y gestiona de forma segura los recursos del sistema a través de las llamadas al sistema.

El núcleo de un sistema operativo suele operar en modo supervisor. Al operar en dicho modo un error de programación en el núcleo del sistema operativo puede resultar en un error fatal del cual el sistema sólo puede recuperarse mediante el reinicio del sistema. A tal error fatal también se le conoce en los sistemas operativos UNIX por la locución inglesa ''[http://es.wikipedia.org/wiki/Kernel_panic kernel panic]'' y en los sistemas operativos Windows por el nombre de ''[http://www.google.es/url?sa=t&source=web&cd=1&ved=0CCwQFjAA&url=http%3A%2F%2Fes.wikipedia.org%2Fwiki%2FPantalla_azul_de_la_muerte&ei=s02WTqvCCMjHtAaxuJyBBA&usg=AFQjCNE2tZra15VdohxjrhSogTQZOVedKg Pantallazo azul o BSOD]''.

== Tipos de Sistemas Operativos ==

Los sistemas operativos se pueden clasificar en base a la cantidad de funcionalidad implementada en su núcleo. En general distinguimos dos tipos de sistemas operativos:

* '''Monolíticos:''' son núcleos de gran tamaño (muchas líneas de código) con un alto número de funcionalidades, las cuales normalmente son compiladas junto al núcleo en el mismo momento.
* '''Micronúcleos:''' son núcleos de pequeño tamaño que fueron compilados sólo con las necesidades más básicas del sistema operativo. El resto de funcionalidades son añadidas mediante la adición de módulos externos al núcleo, lo que les proporciona flexibilidad y facilidad de ampliación en detrimento del desempeño necesario para la gestión dinámica de éstos.
* '''Pico/Nanonúcleos:''' se puede considerar un subtipo de Micronúcleo, son núcleos muy pequeños y flexibles, incluso mas pequeños que los Micronúcleos. Se usan en sistemas muy específicos, como satélites, en los que ya se sabe los procesos que se van a realizar. Son muy fiables.

No obstante, existen tipologías híbridas o que acentúan algunos aspectos, que también detallamos en esta sección.

[[Imagen:OS-structure2.svg|880px| Comparativa de distribución de funcionalidades entre distintos tipos de SO]]

=== Sistemas operativos Monolíticos ===

Los sistema operativos monolíticos se caracterizan por emplear un núcleo que implementa la planificación de procesos, el sistema de comunicación de procesos, el sistema de sincronizacion de procesos, la administración de la memoria principal, la administración de ficheros y la gestión de los dispositivos de entrada/salida. Por tanto, a mayor funcionalidad implementada en el núcleo, mayor número de líneas de código que se ejecutan en modo supervisor.

Los sistemas operativos monolíticos son los predominantes hoy día, algunos ejemplos son:

* Sistemas operativos UNIX, tales como FreeBSD, NetBSD y OpenBSD.
* Sistemas operativos GNU/Linux.
* DOS, tales como MS-DOS y DR-DOS.

Como inconveniente, al emplear un núcleo que incluye gran parte de las funcionalidades básicas del sistema operativo, dispone de un alto número de líneas de código ejecutándose en modo supervisor. Por ello, un error de programación en el núcleo puede provocar un ''kernel panic''. Además el hecho de añadir nuevas funcionalidades provocaría una nueva recompilación del núcleo llevando a reiniciar el sistema para que se apliquen los nuevos cambios.

Como principal ventaja, los sistemas operativo monolíticos ofrecen un alto rendimiento puesto que las peticiones entre los diferentes componentes se reducen a invocaciones de funciones.

=== Sistemas operativos Micronúcleo ===

También conocidos como sistemas operativos exokernel o exonúcleo, se caracterizan por disponer de un núcleo que implementa únicamente:

* Planificación de procesos
* Mecanismo de comunicación entre procesos
* Gestión de interrupciones

Además, existen procesos servidores que están fuera del núcleo, que se ejecutan en modo usuario del procesador, y que implementan la:

* Administración de memoria principal
* Administración de ficheros
* Gestión de dispositivos de entrada/salida.

Siguiendo este esquema, cuando un proceso cualquiera solicita un servicio a través de una llamada al sistema, el micronúcleo canaliza la petición al proceso servidor correspondiente. Dicha comunicación se realiza mediante mensajería.

La principal ventaja de los sistemas operativos micronúcleo es que, al ejecutar menos líneas de código en modo supervisor, de manera intuitiva son más fiables. Otras ventajas son que se garantiza el aislamiento de las partes que están fuera del núcleo, como los módulos son independientes unos de otros, si cae alguno de ello los demás no se ven afectados y pueden seguir funcionando.

Sin embargo, el principal problema que presentan es el rendimiento, puesto que cualquier petición requiere mensajería, que lleva consigo un coste extra debido a la construcción de los mensajes, el reparto y la interpretación. Son estos problemas relacionados con el rendimiento los que hacen que no existan sistemas operativos micronúcleo desplegables en productivo, a excepción de Minix 2, que tiene propósitos educativos. Otro ejemplo de micronúcleo es Symbian OS.

=== Sistemas basados en Máquinas Virtuales ===

Implementan el material (hardware) en el software. Algunos sistemas operativos ofrecen técnicas de paravirtualización.

'''Paravirtualización:''' técnica de programación que ofrecen algunos SO anfitrión para facilitar la virtualización y el rendimiento de máquinas virtuales. Ofrecen llamadas directas al sistema
o acceso a una API especial del anfitrión para acceder directamente a los recursos. Observamos que se deposita una gran confianza en los procesos de la VM por motivos de rendimiento.

* Ventajas de las Máquinas Virtuales
** Ahorro de coste material.
** Se pueden tener diferentes SO en un mismo sistema.
** Se adapta a las necesidades de usuario.
** Se puede deslocalizar la máquina virtual (deslocalización: migrar a otro SO sin sufrir ningún cambio ).

* Desventajas de las Máquinas Virtuales
** Rendimiento (KVM + paravirtualización 10%).
** Punto único de fallos(si falla algún componente y las aplicaciones están montadas en él provoca un fallo general).

== Otro material a consultar ==

El estudiante puede encontrar el siguiente material de interés para complementar sus conocimientos:

* Debate entre Linus Torvalds, creador del núcleo Linux, que sigue el paradigma monolítico y Andrew S. Tanembaum, creador de Minux, que sigue el modelo micronúcleo: http://oreilly.com/catalog/opensources/book/appa.html (en inglés).

Modelos de Diseño de Sistemas Operativos

2011-10-28T14:35:48Z

Manalerod: /* Tipos de Sistemas Operativos */

= 2.5. Modelos de Diseño de SSOO =

== Modos de operación del procesador ==

Para entender los modelos de diseño de los sistemas operativos, tenemos que hacer referencia a los modos de ejecución del procesador. El modo de ejecución del procesador indica qué conjunto de instrucciones y a qué recursos del procesador se puede acceder en un cierto instante de tiempo.

En la actualidad, un procesador ofrece como mínimo dos modos de operación(ejecución) que son:

* '''Modo supervisor''', que permite la ejecución de todo el conjunto de instrucciones que ofrece el procesador (no tiene ninguna relación con el modo "root" o administrador de algunos sistemas operativos).
* '''Modo usuario''', que tiene algunas restricciones de acceso a aspectos del procesador o de ejecución de instrucciones.

== Núcleo del sistema operativo ==

El núcleo del sistema operativo, también conocido por la terminología inglesa ''kernel'', es la parte más esencial del sistema operativo. Se trata de la capa visible del software más baja del sistema que provee y gestiona de forma segura los recursos del sistema a través de las llamadas al sistema.

El núcleo de un sistema operativo suele operar en modo supervisor. Al operar en dicho modo un error de programación en el núcleo del sistema operativo puede resultar en un error fatal del cual el sistema sólo puede recuperarse mediante el reinicio del sistema. A tal error fatal también se le conoce en los sistemas operativos UNIX por la locución inglesa ''[http://es.wikipedia.org/wiki/Kernel_panic kernel panic]'' y en los sistemas operativos Windows por el nombre de ''[http://www.google.es/url?sa=t&source=web&cd=1&ved=0CCwQFjAA&url=http%3A%2F%2Fes.wikipedia.org%2Fwiki%2FPantalla_azul_de_la_muerte&ei=s02WTqvCCMjHtAaxuJyBBA&usg=AFQjCNE2tZra15VdohxjrhSogTQZOVedKg Pantallazo azul o BSOD]''.

== Tipos de Sistemas Operativos ==

Los sistemas operativos se pueden clasificar en base a la cantidad de funcionalidad implementada en su núcleo. En general distinguimos dos tipos de sistemas operativos:

* '''Monolíticos:''' son núcleos de gran tamaño (muchas líneas de código) con un alto número de funcionalidades, las cuales normalmente son compiladas junto al núcleo en el mismo momento.
* '''Micronúcleos:''' son núcleos de pequeño tamaño que fueron compilados sólo con las necesidades más básicas del sistema operativo. El resto de funcionalidades son añadidas mediante la adición de módulos externos al núcleo, lo que les proporciona flexibilidad y facilidad de ampliación en detrimento del desempeño necesario para la gestión dinámica de éstos.
* '''Pico/Nanonúcleos:'''Se puede considerar un subtipo de Micronúcleo, son núcleos muy pequeños y flexibles, incluso mas pequeños que los Micronúcleos. Se usan en sistemas muy específicos, como satélites, en los que ya se sabe los procesos que se van a realizar. Son muy fiables.

No obstante, existen tipologías híbridas o que acentúan algunos aspectos, que también detallamos en esta sección.

[[Imagen:OS-structure2.svg|880px| Comparativa de distribución de funcionalidades entre distintos tipos de SO]]

=== Sistemas operativos Monolíticos ===

Los sistema operativos monolíticos se caracterizan por emplear un núcleo que implementa la planificación de procesos, el sistema de comunicación de procesos, el sistema de sincronizacion de procesos, la administración de la memoria principal, la administración de ficheros y la gestión de los dispositivos de entrada/salida. Por tanto, a mayor funcionalidad implementada en el núcleo, mayor número de líneas de código que se ejecutan en modo supervisor.

Los sistemas operativos monolíticos son los predominantes hoy día, algunos ejemplos son:

* Sistemas operativos UNIX, tales como FreeBSD, NetBSD y OpenBSD.
* Sistemas operativos GNU/Linux.
* DOS, tales como MS-DOS y DR-DOS.

Como inconveniente, al emplear un núcleo que incluye gran parte de las funcionalidades básicas del sistema operativo, dispone de un alto número de líneas de código ejecutándose en modo supervisor. Por ello, un error de programación en el núcleo puede provocar un ''kernel panic''. Además el hecho de añadir nuevas funcionalidades provocaría una nueva recompilación del núcleo llevando a reiniciar el sistema para que se apliquen los nuevos cambios.

Como principal ventaja, los sistemas operativo monolíticos ofrecen un alto rendimiento puesto que las peticiones entre los diferentes componentes se reducen a invocaciones de funciones.

=== Sistemas operativos Micronúcleo ===

También conocidos como sistemas operativos exokernel o exonúcleo, se caracterizan por disponer de un núcleo que implementa únicamente:

* Planificación de procesos
* Mecanismo de comunicación entre procesos
* Gestión de interrupciones

Además, existen procesos servidores que están fuera del núcleo, que se ejecutan en modo usuario del procesador, y que implementan la:

* Administración de memoria principal
* Administración de ficheros
* Gestión de dispositivos de entrada/salida.

Siguiendo este esquema, cuando un proceso cualquiera solicita un servicio a través de una llamada al sistema, el micronúcleo canaliza la petición al proceso servidor correspondiente. Dicha comunicación se realiza mediante mensajería.

La principal ventaja de los sistemas operativos micronúcleo es que, al ejecutar menos líneas de código en modo supervisor, de manera intuitiva son más fiables. Otras ventajas son que se garantiza el aislamiento de las partes que están fuera del núcleo, como los módulos son independientes unos de otros, si cae alguno de ello los demás no se ven afectados y pueden seguir funcionando.

Sin embargo, el principal problema que presentan es el rendimiento, puesto que cualquier petición requiere mensajería, que lleva consigo un coste extra debido a la construcción de los mensajes, el reparto y la interpretación. Son estos problemas relacionados con el rendimiento los que hacen que no existan sistemas operativos micronúcleo desplegables en productivo, a excepción de Minix 2, que tiene propósitos educativos. Otro ejemplo de micronúcleo es Symbian OS.

=== Sistemas basados en Máquinas Virtuales ===

Implementan el material (hardware) en el software. Algunos sistemas operativos ofrecen técnicas de paravirtualización.

'''Paravirtualización:''' técnica de programación que ofrecen algunos SO anfitrión para facilitar la virtualización y el rendimiento de máquinas virtuales. Ofrecen llamadas directas al sistema
o acceso a una API especial del anfitrión para acceder directamente a los recursos. Observamos que se deposita una gran confianza en los procesos de la VM por motivos de rendimiento.

* Ventajas de las Máquinas Virtuales
** Ahorro de coste material.
** Se pueden tener diferentes SO en un mismo sistema.
** Se adapta a las necesidades de usuario.
** Se puede deslocalizar la máquina virtual (deslocalización: migrar a otro SO sin sufrir ningún cambio ).

* Desventajas de las Máquinas Virtuales
** Rendimiento (KVM + paravirtualización 10%).
** Punto único de fallos(si falla algún componente y las aplicaciones están montadas en él provoca un fallo general).

== Otro material a consultar ==

El estudiante puede encontrar el siguiente material de interés para complementar sus conocimientos:

* Debate entre Linus Torvalds, creador del núcleo Linux, que sigue el paradigma monolítico y Andrew S. Tanembaum, creador de Minux, que sigue el modelo micronúcleo: http://oreilly.com/catalog/opensources/book/appa.html (en inglés).

Ejercicios Procesos

2011-10-18T14:10:09Z

Manalerod: /* Ejercicio 1 */

Se muestran a continuación una serie de ejercicios relacionados con el temario de procesos.

Para ver las soluciones a los ejercicios, ir hacia [[solución de los ejercicios de procesos]].

== Ejercicio 1 ==
''[Este ejercicio fue parte del Primer Control de Evaluación Contínua en el curso 2010/11, del 23 de marzo de 2011]''
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
! width="50" style="background:#efefef;" | Proceso
! width="50" style="background:#efefef;" | H0
! width="50" style="background:#efefef;" | t
|-
| PA
| 0
| 3
|-
| PB
| 1
| 5
|-
| PC
| 2
| 6
|}

Considerando que una unidad de tiempo es de 50 ms, PA cada unidad de tiempo pasa a estado bloqueante por dos unidades y PC cada dos unidades de tiempo pasa a bloqueante una unidad, catalogue los procesos A,B y C según su comportamiento (en base a la clasificación de tipos de procesos vista en clase). (''[[Solución de los ejercicios de procesos#Ejercicio 1|Ver solución]]'')