Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Criterios de reemplazo

2011-06-07T22:22:45Z

Jdsanchez:

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].
El fallo de página se produce cuando se accede a una posición de memoria que esta descargada en disco.

nº fallos pág.
tasa fallos pág = -----------------
nº accesos pág.

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

* Arranque en frío : se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno esta cargado en memoria principal.
* Arranque en caliente : se suponen ya cargadas las páginas de los procesos en memoria principal.

==Criterios==
Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4
Suponiendo arranque en frío
___1____ 2_____3_____4___
memoria principal | | | | |
de 4 marcos |_____|_____|_____|_____|

;1. Criterio de página óptima: Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.
*[[sol_1|Solución]]
;2. Criterio de página pésima: Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.
*[[sol_2|Solución]]
;3. Criterio MRU('''M'''ost '''R'''ecently '''U'''sed): Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.
*[[sol_3|Solución]]
;4. Criterio de selección estocástica (aleatoria): Consiste en seleccionar una página al azar.
;5. Criterio por orden de carga FIFO: Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

;6.Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed): Ofrece dos bits para cada página:
* bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* bit M : Se pone a 1 si la página es modificada (escritura).
Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

# R=0, M=0 .
# R=0, M=1 .
# R=1, M=0 .
# R=1, M=1 .

Claramente deben realizarse periodos de puesta a 0, que no tienen porque ser simultáneamente en R y M.

*[[sol_6|Solución]]

;7.Criterio de 2ª oportunidad: Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Consiste en recorrer la cola hasta encontrar una página con R a 0 (si no hay ninguno, pues al que le toque de la cola) y los procesos que vaya encontrando con R a 1 se les pone R a 0 y se les da una segunda oportunidad poniéndolos al final de la cola (al final de todo, el nuevo elemento llegado).

*[[sol_7|Solución]]

;8.Criterio LRU ('''L'''east '''R'''ecently '''U'''sed): Criterio en contraposición al MRU. En MRU elegíamos aquella página que hubiéramos utilizado más recientemente (la primera de la pila de acceso) mientras que en LRU elegimos como página víctima lo contrario: La última página de la pila. Funciona como una FIFO (por orden de acceso) en la cual se actualizan los valores, poniéndose al final si llegan elementos que ya había en cola.

*[[sol_8|Solución]]

;Criterio del reloj: Igual que el de 2º oportunidad pero mantenemos un puntero a la ultima pagina examinada; se implementa con una lista circular, y un puntero a la ultima pagina examinada, que sera el 1º elemento que examinaremos para el reemplazo.

*[[sol_reloj|Solución]]

;9.Criterio LFU ('''L'''east '''F'''recuently '''U'''sed): Se incrementa un contador de uso por cada acceso, reseteándose si se saca el dato. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

;10.Aproximación discreta LRU: Consiste en LFU + LRU. Se usa el bit R. Se itera periódicamente sobre la lista de páginas si R = 0 entonces aumento el contador; si R está activado se desactiva y el contador se pone a cero. Ante una sustitución: prescindir de la que tiene mayor valor en el contador. Ojito! Cuando llega un elemento, el contador se inicializa a 0, puesto que solo se modifica en los checkpoints, no con cada acceso

*[[sol_9.2|Solución]]

;11.Sustitución por envejecimiento: Se emplea un registro R de n bits que se va desplazando hacia la derecha periódicamente, de forma que la página victima será la que tenga el menor valor en el registro R (en caso de empate se empleao otro criterio). Por cada acceso se pone a 1 el bit más significativo del registro R. Los LSB se pierden al desplazar.

*[[sol_10|Solución]]

En el [[Algoritmos de criterios de reemplazo|Portal de la comunidad]] se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento.
Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --[[Usuario:Alexrdp|Alexrdp]] 16:24 6 jun 2011 (UTC)

--[[Usuario:josvaldia|josvaldia]]Acabo de encontrar un error en los apuntes. En el libro de SS.OO: en aproximacion discreta del LRU en cada exploración, si el bit Restá desactivado, se pone el contador a cero y se desactiva el bit. Cuando hay que sacrificar una página, se elimina aquella cuyo contador tenga el valor mayor. Desde luego fallos de este tipo en los apuntes de una asignatura el dia antes del examen, no se pueden permitir.

Mejoras de tiempos de desplazamiento

2011-06-07T15:20:35Z

Jdsanchez:

;1. FCFS (por orden de llegada "FIFO"): Las peticiones se atienden en el mismo orden en que se reciben.

;2. SSTF (por menor tiempo de búsqueda): Ordeno todo y cojo el lote de ''n'' solicitudes de pista. Si no se llega a las ''n'' peticiones tras un tiempo se pasa a la busqueda. Aplaza las peticiones lejanas indefinidamente cuando ''n'' tiende a ifinito (''n'' -> ∞).

;3. NSCAN(criterio del ascensor): Dentro de cada lote de la lista de accesos, escogemos aquellos sectores que nos permita ascender y descender en la tabla, dando de esta manera prioridad a los sectores que se encuentren en la parte central de la pista.

|
| /\ | /\
| / \ | / \
| / \ | / \
___|/______\|/______\__
|
Nota: La gráfica resultante no tiene por qué ser simétrica, dependerá de los sectores a los que accedamos.
Nota2: El número de sectores integrantes de cada lote será el indicado por la N, ejemplo: 3-SCAN, 4-SCAN, etc.

;4. C-SCAN (Circular-Scan): Da preferencia al ascenso o descenso, y se mantiene. Así se elimina el trato favorable a las partes centrales.

| |
| /| /| /| |\ |\ |\ |
| / | / | / | ó | \ | \ | \ |
| / | / | / | | \ | \ | \ |
___|/___|/___|_/___|_ ___|___\|__ \|___\|_
| |

SO multiprogramables con particiones fijas

2011-06-04T11:44:12Z

Jdsanchez: /* Criterios de asignación */

La memoria se encuentra dividida en particiones, en cada una habrá un proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un procesos necesita mayor memoria que la partición más grande, entonces este no se ejecuta.
*Desperdicio de memoria. Por ejemplo, si los procesos son muy pequeños y las particiones grandes.

=Criterios de asignación=
Se lanza un proceso, y hay que elegir a que partición va (estrategia de espera). Puede haber una cola por partición, o una sola para todas las particiones.

Ej: 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:
_____
|_____| H1 = 8KB
|_____| H2 = 8KB
| |
|_____| H3 = 16KB
| |
| |
| | H4 = 32KB
|_____|

*'''Mejor ajuste estático''': se adjudica cada proceso a la menor partición que quepa. Complejidad: O(1)

[[solución mejor ajuste estático|Ver solución]]

*'''Primer ajuste''': cuando una partición queda libre, se asigna el primer proceso que quepa en ella. Complejidad: O(1)

[[solución primer ajuste|Ver solución]]

*'''Mejor ajuste dinámico''': cuando una partición queda libre, se asigna el mayor proceso que quepa en ella. Complejidad: O(nlog(p))

[[solución ajuste dinámico|Ver solución]]

*'''Mejor ajuste dinamico con aplazamiento limitado''': 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.

*'''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 y se asigna partición madre.
''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 =

*'''Montaje absoluto''': Se asigna una dirección de memoria constante, siendo por tanto este método muy restrictivo. Se utiliza para la carga del sistema operativo.

* '''Carga con reubicación''': Al realizar la carga, se le aplica a las direcciones lógicas del programa un ''offset'' o desplazamiento. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

* '''Reubicación dinámica''': A diferencia de la carga con reubicación, el desplazamiento se asigna en tiempo de ejecución.
** '''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í.

* '''Ampliación bits de protección''' : Se le asocia a cada palabra un bit para comprobar si es de SO o del proceso.

* '''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.

Algoritmo para averiguar interbloqueo

2011-05-10T13:33:23Z

Jdsanchez: /* Algoritmo del Banquero */

== Algoritmo del Banquero ==
La idea genérica del algoritmo es:

1. Buscar un proceso cuya suma recAsig + recDisp >= recMax
2. Suponemos que se asignan dichos recursos y el proceso termina su ejecución.
Sumamos sus recursos al vector recDisp y añadimos el proceso a la lista de finalizados.
3. Repetir primer paso hasta terminar todos los procesos (siendo un estado estable)
o bien hasta el punto en el que no sea posible ninguna asignación de recursos,
existiendo pues interbloqueo.

Ejemplo:

Proceso | Asignados | Maximos | Disponibles
| A B C D E | A B C D E | A B C D E
__________|_____________|___________|___0 0 2 1 1___ //Recursos Disponibles Iniciales
P0 | 1 0 2 1 1 | 1 2 2 1 2 | 1 1 3 2 1 //P3 finalizado
P1 | 2 0 1 1 0 | 2 2 2 1 0 | 2 2 3 3 1 //P2 finalizado
P2 | 1 1 0 1 0 | 2 1 3 1 0 | 3 2 5 4 2 //P0 finalizado
P3 | 1 1 1 1 0 | 1 1 2 2 1 | //P1 finalizado

Pasos:
1. El primer proceso que cumple el paso 1 del algoritmo en esta tabla es P3:
[1 1 1 1 0]+[0 0 2 1 1] >= [1 1 2 2 1]
Lo consideramos terminado y añadimos sus recursos a los disponibles
2. Volvemos a iterar desde P0. El siguiente proceso que puede adquirir los recursos necesarios
es P2. Añadimos sus recursos a la lista de disponibles
3. Ahora nos es posible terminar P0 y por último P1.
4. Hemos logrado terminar todos los procesos sin problemas.

== Algoritmo en C# ==

<source lang="csharp">
int nRecursos;
int nProcesos;
List<List<int>> asignados = new List<List<int>>();
List<List<int>> maximos = new List<List<int>>();
List<int> disponibles = new List<int>();

Random r = new Random();

//Generamos las matrices aleatoriamente
for (int j1 = 0; j1 < nRecursos;j1++)
{
disponibles.Add(r.Next(0, nRecursos));
}
for (int i = 0; i < nProcesos; i++)
{
asignados.Add(new List<int>());
maximos.Add(new List<int>());
for (int j = 0; j < nRecursos; j++)
{
asignados[i].Add(r.Next(0, nRecursos));
maximos[i].Add(r.Next(0, nRecursos));
}
}

bool aux = true;
for (int proc = 0; proc < nProcesos; proc++)
{
aux = true;
for (int recur = 0; recur < nRecursos; recur++)
{
// comprobamos que haya recursos suficientes
aux = (maximos[proc][recur] - asignados[proc][recur] - disponibles[recur]) <= 0;
if (!aux)
{
break;
}
}
if (aux)
{
añadirYeliminar(ref disponibles, ref asignados, proc);
maximos.RemoveAt(proc);
nProcesos--;
proc = -1;
if (nProcesos == 0)
{
Console.WriteLine("Es estado seguro");
Console.ReadLine();
return;
}
}
}
Console.WriteLine("Es interbloqueo");
Console.ReadLine();

}

private static void añadirYeliminar(ref List<int> disponibles, ref List<List<int>> asignados, int proc)
{
for (int k = 0; k < asignados[proc].Count; k++)
{
disponibles[k] += asignados[proc][k];
}
asignados.RemoveAt(proc);
}
</source>

Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente

== Algoritmo en Python ==

<source lang="python">
def comprueba_configuracion(asignados, maximos, disponibles):
finalizados = []
i = 0
while(i < len(asignados)):
if not i in finalizados and puede_progresar(asignados[i], disponibles, maximos[i]):
print('Finaliza P%s\nDisponibles: %s' % (i,disponibles))
libera_recursos(asignados[i], disponibles)
finalizados.append(i) # Marca el proceso Pi como finalizado
i = 0
else:
i += 1

if(len(asignados) == len(finalizados)): # Si todos los procesos finalizan
print('\nEstado seguro para la configuracion de procesos-recursos dada')
else:
print('\nSe produce un interbloqueo')

# Incrementamos la lista de disponibles con los que tenia asignados
def libera_recursos(asignados, disponibles):
for i in range(len(disponibles)):
disponibles[i] += asignados[i]

# Devuelve True si el nº de elementos asignados mas los disponibles son mayores o iguales a los requeridos para continuar
def puede_progresar(asignados, disponibles, maximos):
resultado = True
for i in range(len(maximos)):
if(asignados[i] + disponibles[i] < maximos[i]):
resultado = False
break
return resultado

asignados = [
[1,0,2,1,1],
[2,0,1,1,0],
[1,1,0,1,0],
[1,1,1,1,0]
]
maximos = [
[1,2,2,1,2],
[2,2,2,1,0],
[2,1,3,1,0],
[1,1,2,2,1]
]
disponibles = [0,0,2,1,1]
</source>

Para este ejemplo (visto en clase) la salida sería:

<source lang="python">
>>> comprueba_configuracion(asignados, maximos, disponibles)
Finaliza P3
Disponibles: [0, 0, 2, 1, 1]
Finaliza P2
Disponibles: [1, 1, 3, 2, 1]
Finaliza P0
Disponibles: [2, 2, 3, 3, 1]
Finaliza P1
Disponibles: [3, 2, 5, 4, 2]

Estado seguro para la configuracion de procesos-recursos dada
</source>

== Algoritmo en Java ==
<source lang="java">
public class Comprobaciones {

public static List<Proceso> devuelveLista(List<Proceso> asignados, List<Proceso> necesarios, Disponibles recursos){
List<Proceso> terminados = new ArrayList<Proceso>();
for(int i = 0; i < necesarios.size(); i++){
if(!(terminados.contains(asignados.get(i))) && ejecuta(asignados.get(i), necesarios.get(i), recursos)){
terminados.add(asignados.get(i));
System.out.println("Proceso " + asignados.get(i).getNombre() + " terminado");
for(int j = 0; j < recursos.getDisponibles().size(); j++){
recursos.setDisponible(recursos.getDisponibles().get(j) + asignados.get(i).getRecursosNecesarios().get(j), j);
}
System.out.println("Recursos disponibles: " + recursos.getDisponibles());
i = -1;
}

}
if(terminados.size() == asignados.size()){
System.out.println("Todos los procesos han sido ejecutados sin problemas.");
}
else{
System.out.println("Hay un interbloqueo, no se pueden seguir ejecutando procesos...");
}
return terminados;
}

public static Boolean ejecuta(Proceso asignados, Proceso necesarios, Disponibles disponibles){
// Devuelve True si tiene recursos suficientes...
Boolean ej = true;
for(int i = 0; i < necesarios.getRecursosNecesarios().size(); i++){
if((asignados.getRecursosNecesarios().get(i) + disponibles.getDisponibles().get(i)) < necesarios.getRecursosNecesarios().get(i)){
ej = false;
break;
}
}
return ej;
}

}
</source>
<source lang="java">
public static void main(String[] args) {

List<Proceso> asignados = creaAsignados();
List<Proceso> necesarios = creaNecesarios();
Disponibles disponibles = creaDisponibles();
Comprobaciones.devuelveLista(asignados, necesarios, disponibles);
}
</source>
Resultado:
<pre>
Proceso P4 terminado
Recursos disponibles: [1, 1, 3, 2, 1]
Proceso P3 terminado
Recursos disponibles: [2, 2, 3, 3, 1]
Proceso P1 terminado
Recursos disponibles: [3, 2, 5, 4, 2]
Proceso P2 terminado
Recursos disponibles: [5, 2, 6, 5, 2]
Todos los procesos han sido ejecutados sin problemas.
</pre>
Nota: Las clases lo único que contienen son listas de enteros, y los procesos contienen además los nombres de los mismos.

Monitores

2011-05-09T15:50:58Z

Jdsanchez: /* Definición */

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 implemente 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.

== Fuentes ==
<references/>

Monitores

2011-05-09T15:49:06Z

Jdsanchez: /* Definición */

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 se sitúan de forma independiente y cuando deseen usar el recurso, llamarán a los métodos del monitor que implemente 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.

== Fuentes ==
<references/>

Mensajería

2011-05-04T16:27:05Z

Jdsanchez:

Es una unidad de información que se intercambia entre dos o más procesos.

Mediante los mensajes podemos transmitir información y sincronizar procesos (mediante la espera de un cierto mensaje).

Los sistemas operativos generalmente ofrecen dos llamadas al sistema (o primitivas básicas) para los procesos, enviar y recibir mensajes:

* send(mensaje): Para enviar un mensaje
* receive(mensaje): Para recibir un mensaje

== Destino y fuente ==

* '''Denominación Directa'''
** Se emplea ID para identificar al destinatario.
** Valores especiales: BROADCAST (a todos), MULTICAST (a un grupo).

* '''Denominación Indirecta'''
** Se emplea un elemento intermediario.
** Recurso compartido especial en el sistema: BUZÓN.
** Habiendo intermediarios, hay que comprobar las identidades pues pueden ser falsas/erróneas

== Formas de transmisión ==

* '''Transmisión por copia'''
** ''Directa'': el mensaje se copia de espacio de emisor a espacio de receptor.
** ''Indirecta'': el mensaje se copia de espacio de emisor a espacio (buzón) de SO, y de ahí a espacio de receptor.

* '''Transmisión por referencia'''
** ''Directa'': lo que se copia es un puntero al mensaje
** ''Global'': el emisor crea mensaje en espacio de SO, y se copia a espacio de receptor un puntero al mismo.

* '''Transmisión por copia de escritura''': el mensaje sólo se copia si se modifica por emisor o receptor.

== Formas de comunicación ==

* Comportamiento del emisor, '''send()'''
**Síncrona: el proceso emisor que realiza el send() queda bloqueado hasta que el receptor llama a recv()
**Asíncrona: suponemos capacidad de almacenamiento en el destinatario o en el buzón. Allí acumulamos los mensajes entrantes y el receptor irá leyendo cuando pueda. Es más ágil pero el destinatario/buzón necesita capacidad de almacenamiento, la cual será limitada y los mensajes posteriores pueden caer en saco roto

* Comportamiento del receptor, '''recv()'''
** Bloqueante: un recv() sin mensajes a procesar pasa a estado bloqueado. Si se hace un send() vuelve a estado preparado
** No bloqueante: recv() sin mensajes a procesar devuelve un "prueba más tarde"

== Formato de los mensajes ==

=== Fijo ===

Los procesos acuerdan emplear un formato fijo para sus mensajes.

Ejemplo: Simple Network Time Protocol. Ver http://tools.ietf.org/html/rfc4330, sección 4, Message Format.

1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |Mode | Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Reference Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Originate Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Receive Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Transmit Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Key Identifier (optional) (32) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| |
| Message Digest (optional) (128) |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

=== Variable ===

* Type-Length-Value.

Ejemplo: Usado en Netlink para la codificación de atributos de un mensaje. Ver Communicating between the kernel and user-space in Linux using Netlink Sockets (1984.lsi.us.es/~pablo/docs/spae.pdf).

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length | Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ /
/ Value /
/ /
/////////////////////////////////////////////////////////////////

* Text-based human-readable.

** Comma-Separated Value (CSV): http://en.wikipedia.org/wiki/Comma-separated_values
** Extensible Markup Language (XML): http://en.wikipedia.org/wiki/XML
** JavaScript Object Notation (JSON): http://en.wikipedia.org/wiki/JSON

=== Mixto ===

Los procesos acuerdan emplear mensaje con partes cuyo formato es fijo, como por ejemplo una cabecera inicial, seguido de partes de tamaño variable.

Ejemplo: Internet Protocol (IPv4). Ver http://www.ietf.org/rfc/rfc791.txt, sección 3.1.

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL |Type of Service| Total Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identification |Flags| Fragment Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time to Live | Protocol | Header Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ /
/ Payload /
/ /
/////////////////////////////////////////////////////////////////

== Mensajería a través de la red ==

* Unidad del destinatario
* Fiabilidad en la transmisión
* Formato de los datos (http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/endian.html): Enviar un entero a través de la red puede ser un problema debido a la forma en el que se representan los datos en la memoria dependiente de la arquitectura. Por ejemplo, un PC con arquitectura Intel x86 emplea formato little-endian, mientras que un SPARC de Sun Microsystems (ahora Oracle) emplea big-endian.

** Little Endian: Bytes menos significativo al principio.

<source lang="c">
int main(void)
{
int a = 10, i;
char *p = &a;

for (i=0; i<sizeof(a); i++) {
printf("posición %d: %.2x\n", i, p[i]);
}
}
</source>

Muestra el siguiente resultado en un PC:

posición 0: 0a (n+3)
posición 1: 00 (n+2)
posición 2: 00 (n+1)
posición 3: 00 (n)

** Big Endian: Bytes menos significativo al final.

posición 0: 00 (n)
posición 1: 00 (n+1)
posición 2: 00 (n+2)
posición 3: 0a (n+3)

En Internet se sigue la convención de expresar datos en Big Endian, habría que hacer la conversión. Habría que usar '''ntohl''' (network to host long).

En little-endian, la implementación de ntohl es la siguiente:

#define __constant_ntohl(x) ___constant_swab32((__be32)(x)

Ver /usr/include/linux/byteorder/little_endian.h

mientras que en big-endian es:

#define __constant_ntohl(x) ((__u32)(__be32)(x))

Si empleamos formato textuales, como CSV, XML o JSON, que codifican la información en bytes, no tenemos este problema.

Semáforos

2011-05-04T11:41:40Z

Jdsanchez: /* Semáforos */

= Planificador de procesos: Diagrama de estados simplicado =

Para comprender apropiadamente cómo funcionan los semáforos vamos a recordar el diagrama de estados simplificado que emplea el planificador de procesos del sistema operativo.

|---------------|
pendiente | | recibido
evento ---------> | bloqueado |----------- evento
externo | | | | externo
| |---------------| |
| |
| planificador \/
|--------------| retira CPU |---------------|
| | -------------------> | |
| activo | | preparado |
| | <------------------- | |
|--------------| |---------------|
planificador
asigna CPU

La vida de un proceso pasa por tres estados:

* Activo: el proceso está empleando la CPU, por tanto, está ejecutandose. Hay tantos procesos activos como recurso de procesamiento disponible. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
* Preparado: el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
* Bloqueado: el proceso está pendiente de un evento externo, tales como la espera de finalización de un proceso hijo, una señal, una operación sobre un semáforo o una operación de lectura/escritura.

La transición de activo a preparado y viceversa depende de decisiones tomadas por el planificador del sistema operativo (que emplea algún criterio visto en clases teóricas, tales como el turno rotatorio), el programador no puede interferir en estas decisiones. Mientras que la transición de activo a bloqueado, y de bloqueado a preparado pueden ser controladas por el programador mediante llamadas al sistema.

= Semáforos =

Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra]. Los semáforos nos permiten '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que nos permiten sincronizar la ejecución de dos o más procesos.

Los semáforos son un tipo de datos (TAD) que están compuestos por dos atributos:

* Un contador, que siempre vale >= 0.
* Una lista de procesos, inicialmente vacía.

Son usados para controlar el acceso a ciertas partes de un programa llamadas '''secciones críticas''', en la que se manipulan recursos que deben ser tratados de forma especial.

El valor del semáforo, tanto en su inicialización como a lo largo de la ejecución del proceso, es muy importante ya que será lo que controle el número de procesos accediendo al recurso compartido de manera simultánea.

El tipo mas simple de semáforo es el binario. Pueden tomar como valor 0 o 1 y sólo permite el acceso a un único proceso a la vez.

Los semáforos disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

<source lang="c">
down(semáforo s)
{
si s.contador == 0:
proceso a estado bloqueado
añade proceso a s.lista
sino:
s.contador--
}
</source>

Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.

<source lang="c">
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
</source>

Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Los semáforos son un mecanismo de esperas no ocupadas, lo que significa que permite sincronizar a los procesos de forma que no se desperdician recursos de CPU cuando un cierto no proceso no tiene actividad a realizar (la espera ocupada, también conocida como espera activa, es en la que se queda comprobando la condición hasta verificarla, como el caso de los cerrojos).

'''Granularidad''': número de recursos controlados por un semáforo

'''Problemas''': El uso de semáforos también tiene algunos inconvenientes, entre los que destacan:

* Facilidad para emplearlos incorrectamente.
* Son independientes del lenguaje de programación, y por tanto no hay comprobación ninguna en tiempo de compilación.
* No hay nada que obligue a usarlos.
* Son independientes del recurso compartido al que intentan regular.

'''Ejemplo productor-consumidor''': Supongamos un proceso que produce y otro que consume lo producido. Lo deseable es que el productor actúe primero, y no más de 1 vez consecutiva, puesto que el consumidor consume de 1 en 1.

{|cellpadding="4"
!style="border-style: solid; border-width: 0 1px 1px 1px"|Inicializacion
!style="border-style: solid; border-width: 0 1px 1px 0"|Productor
!style="border-style: solid; border-width: 0 1px 1px 0"|Consumidor
|-
|width="200"|semaforo prod,cons;
|width="90"|while(1){
|width="90"|while(1){
|-
|semaforo_create(cons,0);
|align="center"| down (prod);
|align="center"| down (cons);
|-
|semaforo_create(prod,1);
|align="center"| produce();
|align="center"| consume();
|-
|
|align="center"| up(cons);
|align="center"| up(prod);
|-
|
| }
| }
|}

Semáforos

2011-05-04T11:37:48Z

Jdsanchez: /* Semáforos */

= Planificador de procesos: Diagrama de estados simplicado =

Para comprender apropiadamente cómo funcionan los semáforos vamos a recordar el diagrama de estados simplificado que emplea el planificador de procesos del sistema operativo.

|---------------|
pendiente | | recibido
evento ---------> | bloqueado |----------- evento
externo | | | | externo
| |---------------| |
| |
| planificador \/
|--------------| retira CPU |---------------|
| | -------------------> | |
| activo | | preparado |
| | <------------------- | |
|--------------| |---------------|
planificador
asigna CPU

La vida de un proceso pasa por tres estados:

* Activo: el proceso está empleando la CPU, por tanto, está ejecutandose. Hay tantos procesos activos como recurso de procesamiento disponible. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
* Preparado: el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
* Bloqueado: el proceso está pendiente de un evento externo, tales como la espera de finalización de un proceso hijo, una señal, una operación sobre un semáforo o una operación de lectura/escritura.

La transición de activo a preparado y viceversa depende de decisiones tomadas por el planificador del sistema operativo (que emplea algún criterio visto en clases teóricas, tales como el turno rotatorio), el programador no puede interferir en estas decisiones. Mientras que la transición de activo a bloqueado, y de bloqueado a preparado pueden ser controladas por el programador mediante llamadas al sistema.

= Semáforos =

Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra]. Los semáforos nos permiten '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que nos permiten sincronizar la ejecución de dos o más procesos.

Los semáforos son un tipo de datos (TAD) que están compuestos por dos atributos:

* Un contador, que siempre vale >= 0.
* Una lista de procesos, inicialmente vacía.

Son usados para controlar el acceso a ciertas partes de un programa llamadas '''secciones críticas''', en la que se manipulan recursos que deben ser tratados de forma especial.

El valor del semáforo, tanto en su inicialización como a lo largo de la ejecución del proceso, es muy importante ya que será lo que controle el número de procesos accediendo al recurso compartido de manera simultánea.

El tipo mas simple de semáforo es el binario. Pueden tomar como valor 0 o 1 y sólo permite el acceso a un único proceso a la vez.

Los semáforos disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

<source lang="c">
down(semáforo s)
{
si s.contador == 0:
proceso a estado bloqueado
añade proceso a s.lista
sino:
s.contador--
}
</source>

Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.

<source lang="c">
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
</source>

Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Los semáforos son un mecanismo de esperas no ocupadas, lo que significa que permite sincronizar a los procesos de forma que no se desperdician recursos de CPU cuando un cierto no proceso no tiene actividad a realizar (la espera ocupada, también conocida como espera activa, es en la que se queda comprobando la condición hasta verificarla).

'''Granularidad''': número de recursos controlados por un semáforo

'''Problemas''': El uso de semáforos también tiene algunos inconvenientes, entre los que destacan:

* Facilidad para emplearlos incorrectamente.
* Son independientes del lenguaje de programación, y por tanto no hay comprobación ninguna en tiempo de compilación.
* No hay nada que obligue a usarlos.
* Son independientes del recurso compartido al que intentan regular.

'''Ejemplo productor-consumidor''': Supongamos un proceso que produce y otro que consume lo producido. Lo deseable es que el productor actúe primero, y no más de 1 vez consecutiva, puesto que el consumidor consume de 1 en 1.

{|cellpadding="4"
!style="border-style: solid; border-width: 0 1px 1px 1px"|Inicializacion
!style="border-style: solid; border-width: 0 1px 1px 0"|Productor
!style="border-style: solid; border-width: 0 1px 1px 0"|Consumidor
|-
|width="200"|semaforo prod,cons;
|width="90"|while(1){
|width="90"|while(1){
|-
|semaforo_create(cons,0);
|align="center"| down (prod);
|align="center"| down (cons);
|-
|semaforo_create(prod,1);
|align="center"| produce();
|align="center"| consume();
|-
|
|align="center"| up(cons);
|align="center"| up(prod);
|-
|
| }
| }
|}

Mecanismos de sincronización

2011-05-03T16:12:08Z

Jdsanchez: /* Implementación del control de concurrencia pesimista */

= Optimistas =

Este mecanismo debe emplearse si el programador considera que la frecuencia de acceso a un recurso compartido es baja, es decir, que supone que la probabilidad de coincidencia de dos o más procesos al recurso compartido es baja.

El siguiente ejemplo muestra el código ejecutado por dos hilos: hx y hy de un mismo proceso.

<source lang="c">
int compartida = 1, tmp;
retry:
tmp = compartida; /* almaceno el valor de la variable compartida en una temporal. */
tmp++; /* actualizo la varible temporal. */
if (compartida+1 != tmp) /* compruebo si la variable compartida ha sido modificada */
goto retry; /* mientras operaba con la variable temporal. */
</source>

La principal ventaja es el mayor grado de paralelismo.

Los inconvenientes de este tipo de mecanismo son dos:

* Se consume más memoria, pues hay que realizar una copia del recurso compartido para efectuar la comprobación.
* En situaciones de coincidencia, se tiene que volver a realizar la operación, por tanto, se desperdician recursos de procesamiento.

Por último, si el programador ha empleado una aproximación optimista para una situación en la que la frecuencia de coincidencia es alta, podría darse el caso de que un hilo no progrese en su ejecución de manera indefinida, al tener que volver a reintentar la actualización una y otra vez hasta conseguirlo sin que haya concurrencia.

= Pesimista =
Este mecanismo debe emplear si se considera que la frecuencia de acceso al recurso compartido es alta.

En este mecanismo disponemos de tres partes:

* El protocolo de entrada, en el que se emplea un mecanismo que no permite continuar con la ejecución si otro u otros procesos están accediendo al recurso compartido.
* La sección crítica, en el que se se realizan las operaciones pertinentes con el recurso compartido.
* El protocolo de salida, en el que se vuelve a permitir el acceso al recurso compartido.

El siguiente ejemplo muestra como se implementa el control de concurrencia pesimista para 2 hilos, hx y hy:

<source lang="c">
int compartida = 1;
protocolo_de_entrada(); /* no permito acceso a variable compartida. */
compartida++; /* sección crítica: actualización de la variable compartidad. */
protocolo_de_salida(); /* vuelvo a permitir acceso a la variable compartida. */
</source>

Los protocolos de entrada y salida son, generalmente, operaciones costosas en términos de recursos de procesamiento.

El inconveniente de este mecanismo es:

*Que aunque siempre se pueda implementar, se fuerzan esperas que pueden llegar a ser innecesarias.

Por último, se podría emplear un control de concurrencia pesimista para resolver un problema que se resuelve con un control de concurrencia optimista, pero no al revés.

== Implementación del control de concurrencia pesimista ==

El control de concurrencia pesimista se puede implementar de dos formas mediante:

* Espera ocupada o activa, mediante cerrojos. En este mecanismo se comprueba continuamente la condición que permite franquear en el protocolo de entrada, por tanto, el proceso permanece en estado activo comprobando continuadamente la condición que le permite progresar en su ejecución, tiempo que está siendo desaprovechado por el procesador.
* Espera no ocupada o bloqueante, mediante semáforos, monitores y mensajes. Estos mecanismos hacen que el proceso pase a estado bloqueado cuando no se puede franquear el protocolo de entrada, por tanto, al quedar un proceso que no puede progresar en estado bloqueado, el planificador de procesos tiene que seleccionar a otro proceso.

Planificación de procesos de tiempo real

2011-03-22T17:47:01Z

Jdsanchez: /* Métodos de planificación */

== ¿Qué es un proceso de tiempo real? ==

Proceso de tiempo real se denomina a aquella actividad que debe ser realizada en un plazo de tiempo, si la actividad no es realizada en dicho plazo de tiempo carece de sentido realizarla. Ej: Actividades industriales, videoconferencias, etc

== Clasificación ==

Podemos clasificar los procesos de tiempo real de diferentes maneras:

Segun el plazo de tiempo:
*'''Rígidos(''hard-realtime'')''' : se debe realizar en un plazo de tiempo estricto, sino deja de tener sentido. Si el plazo de tiempo para realizarla es superado el proceso se aborta. Ejemplo: Industriales ( sensores, activadores,...).

*'''Flexibles(''soft-realtime'')''' : es deseable que se cumpla el plazo de tiempo. Ej: Videoconferencia.(Mientras más rapido vaya mejor sera la comunicacion , pero si no , nos adaptamos a ella)

*'''Opcionales''' : conviene hacerla en el plazo de tiempo, pero sino es posible se puede posponer. Ej: actualizacion de una aplicacion/programa instalada en el ordenador.

Según la periodicidad:

*'''Aperiódicas''' : se deben a sucesos externos que deben ser atendidos. El sistema operativo no sabe, a priori, cuando van a llegar ni el tiempo que va a durar. Ej: Notificaciones de errores, Sensores de emergencia en un coche, Ventiladores para refrigeracion.

*'''Periódicas''' : se realizan cada cierto tiempo (actividad repetitiva).A diferencia del anterior el sistema operativo conoce a priori cuando van a llegar y su tiempo de duración Ej: leer una temperatura de un sensor.

== Métodos de planificación ==

Los métodos de planificación a utilizar en SSOO de tiempo real son:

*Planificación apropiativa con prioridad estática: Cada proceso tiene asociado un indice de prioridad y el procesador elige aquel proceso de la lista de preparados con mayor prioridad.

*Planificación de tablas estáticas : se conocen las actividades a realizar y se elabora un plan fijo de ejecución.

*Planificación dinámica: Es muy parecida a la de tablas estaticas , pero tambien admite actividades aperiodicas. Cuando se presenta una actividad aperiodica , el planificador intenta construir un nuevo plan de ejecucion que incluya a todas las actividades. Si no encuentra la solucion que las englobe a todas, rechaza la actividad, que debe ser flexible u opcional. Tambien puede retrasar alguna actividad flexible/opcional.

*Planificación dinámica con un mejor resultado: Las actividades fuera de plazo se abortan. Es muy similar a la anterior, la diferencia mas notable es que en la anterior existe un análisis previo aceptando actividades aperiodicas y en ésta no existe tal analisis.

El siguiente ejemplo emplea planificación apropiativa por prioridades estática con actividades periódicas y aperiódicas:

____|__PA__|_PB__|_PC__|_PD___|
Datos del _H0_|__0___|_1___|_2___|_3*n__|
problema _t__|__2___|_4___|_2___|_1____|
plazo|__3___|_5___|_7___|_3*n+2|
prioridad|__-20_|_0___|_10__|_15___|
(-20 a 19)
UNIX
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
* = el proceso se aborta

| | | | | | | | | | | | | | | | | | | | |
PA <___|___> | | | | | | | | | | | | | | | | | |
PB | < |___|___|___* | | | | | | | | | | | | | | |
PC | | < | | |___|___> | | | | | | | | | | | | |
PD | | | < | * < |___> <___> | <___> | <___> | | | |
Planificador X | X | | X | X | X | | X | | X | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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_|PD1ª_|PD2ª_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1__|_1__|_1__|
de tiempos __T__|_2__|_*__|_4__|_*__|_2__|_1__|
_T/t_|_1__|_*__|_2__|_*__|_2__|_1__|
|
|_> Indice de penalización

Planificación de procesos de tiempo real

2011-03-22T17:42:07Z

Jdsanchez: /* Clasificación */

== ¿Qué es un proceso de tiempo real? ==

Proceso de tiempo real se denomina a aquella actividad que debe ser realizada en un plazo de tiempo, si la actividad no es realizada en dicho plazo de tiempo carece de sentido realizarla. Ej: Actividades industriales, videoconferencias, etc

== Clasificación ==

Podemos clasificar los procesos de tiempo real de diferentes maneras:

Segun el plazo de tiempo:
*'''Rígidos(''hard-realtime'')''' : se debe realizar en un plazo de tiempo estricto, sino deja de tener sentido. Si el plazo de tiempo para realizarla es superado el proceso se aborta. Ejemplo: Industriales ( sensores, activadores,...).

*'''Flexibles(''soft-realtime'')''' : es deseable que se cumpla el plazo de tiempo. Ej: Videoconferencia.(Mientras más rapido vaya mejor sera la comunicacion , pero si no , nos adaptamos a ella)

*'''Opcionales''' : conviene hacerla en el plazo de tiempo, pero sino es posible se puede posponer. Ej: actualizacion de una aplicacion/programa instalada en el ordenador.

Según la periodicidad:

*'''Aperiódicas''' : se deben a sucesos externos que deben ser atendidos. El sistema operativo no sabe, a priori, cuando van a llegar ni el tiempo que va a durar. Ej: Notificaciones de errores, Sensores de emergencia en un coche, Ventiladores para refrigeracion.

*'''Periódicas''' : se realizan cada cierto tiempo (actividad repetitiva).A diferencia del anterior el sistema operativo conoce a priori cuando van a llegar y su tiempo de duración Ej: leer una temperatura de un sensor.

== Métodos de planificación ==

Los métodos de planificación a utilizar en SSOO de tiempo real son:

*Planificación apropiativa con prioridad estática: Cada proceso tiene asociado un indice de prioridad y el procesador elige aquel proceso de la lista de preparados con mayor prioridad.

*Planificación de tablas estáticas : se conocen las actividades a realizar y se elabora un plan fijo de ejecución.

*Planificación dinámica: Es muy parecida a la de tablas estaticas , pero tambien admite actividades aperiodicas.

*Planificación dinámica con un mejor resultado: Las actividades fuera de plazo se abortan. Es muy similar a la anterior, la diferencia mas notable es que en la anterior existe un análisis previo aceptando actividades aperiodicas y en ésta no existe tal analisis.

El siguiente ejemplo emplea planificación apropiativa por prioridades estática con actividades periódicas y aperiódicas:

____|__PA__|_PB__|_PC__|_PD___|
Datos del _H0_|__0___|_1___|_2___|_3*n__|
problema _t__|__2___|_4___|_2___|_1____|
plazo|__3___|_5___|_7___|_3*n+2|
prioridad|__-20_|_0___|_10__|_15___|
(-20 a 19)
UNIX
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
* = el proceso se aborta

| | | | | | | | | | | | | | | | | | | | |
PA <___|___> | | | | | | | | | | | | | | | | | |
PB | < |___|___|___* | | | | | | | | | | | | | | |
PC | | < | | |___|___> | | | | | | | | | | | | |
PD | | | < | * < |___> <___> | <___> | <___> | | | |
Planificador X | X | | X | X | X | | X | | X | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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_|PD1ª_|PD2ª_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1__|_1__|_1__|
de tiempos __T__|_2__|_*__|_4__|_*__|_2__|_1__|
_T/t_|_1__|_*__|_2__|_*__|_2__|_1__|
|
|_> Indice de penalización

Planificación de procesos de tiempo real

2011-03-22T17:41:34Z

Jdsanchez: /* Clasificación */

== ¿Qué es un proceso de tiempo real? ==

Proceso de tiempo real se denomina a aquella actividad que debe ser realizada en un plazo de tiempo, si la actividad no es realizada en dicho plazo de tiempo carece de sentido realizarla. Ej: Actividades industriales, videoconferencias, etc

== Clasificación ==

Podemos clasificar los procesos de tiempo real de diferentes maneras:

Segun el plazo de tiempo:
*'''Rígidos(''hard-realtime'')''' : se debe realizar en un plazo de tiempo estricto, sino deja de tener sentido. Si el plazo de tiempo para realizarla es superado el proceso se aborta. Ejemplo: Industriales ( sensores, activadores,...).

*'''Flexibles(''soft-realtime'')''' : es deseable que se cumpla el plazo de tiempo. Ej: Videoconferencia.(Mientras más rapido vaya mejor sera la comunicacion , pero si no , nos adaptamos a ella)

*'''Opcionales''' : conviene hacerla en el plazo de tiempo, pero sino es posible se puede posponer. (actualizacion de una aplicacion).

Según la periodicidad:

*'''Aperiódicas''' : se deben a sucesos externos que deben ser atendidos. El sistema operativo no sabe, a priori, cuando van a llegar ni el tiempo que va a durar. Ej: Notificaciones de errores, Sensores de emergencia en un coche, Ventiladores para refrigeracion.

*'''Periódicas''' : se realizan cada cierto tiempo (actividad repetitiva).A diferencia del anterior el sistema operativo conoce a priori cuando van a llegar y su tiempo de duración Ej: leer una temperatura de un sensor.

== Métodos de planificación ==

Los métodos de planificación a utilizar en SSOO de tiempo real son:

*Planificación apropiativa con prioridad estática: Cada proceso tiene asociado un indice de prioridad y el procesador elige aquel proceso de la lista de preparados con mayor prioridad.

*Planificación de tablas estáticas : se conocen las actividades a realizar y se elabora un plan fijo de ejecución.

*Planificación dinámica: Es muy parecida a la de tablas estaticas , pero tambien admite actividades aperiodicas.

*Planificación dinámica con un mejor resultado: Las actividades fuera de plazo se abortan. Es muy similar a la anterior, la diferencia mas notable es que en la anterior existe un análisis previo aceptando actividades aperiodicas y en ésta no existe tal analisis.

El siguiente ejemplo emplea planificación apropiativa por prioridades estática con actividades periódicas y aperiódicas:

____|__PA__|_PB__|_PC__|_PD___|
Datos del _H0_|__0___|_1___|_2___|_3*n__|
problema _t__|__2___|_4___|_2___|_1____|
plazo|__3___|_5___|_7___|_3*n+2|
prioridad|__-20_|_0___|_10__|_15___|
(-20 a 19)
UNIX
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
* = el proceso se aborta

| | | | | | | | | | | | | | | | | | | | |
PA <___|___> | | | | | | | | | | | | | | | | | |
PB | < |___|___|___* | | | | | | | | | | | | | | |
PC | | < | | |___|___> | | | | | | | | | | | | |
PD | | | < | * < |___> <___> | <___> | <___> | | | |
Planificador X | X | | X | X | X | | X | | X | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> 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_|PD1ª_|PD2ª_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1__|_1__|_1__|
de tiempos __T__|_2__|_*__|_4__|_*__|_2__|_1__|
_T/t_|_1__|_*__|_2__|_*__|_2__|_1__|
|
|_> Indice de penalización

Multiprogramación

2011-03-22T10:25:47Z

Jdsanchez:

La multiprogramación es una técnica de multiplexación que permite la ejecución simultánea de múltiples procesos en un único procesador. En realidad, esta técnica produce una ilusión de paralelismo, de manera que parece que todos los procesos se están ejecutando a la vez. Sin embargo, hay un único proceso ejecutándose en el procesador a la vez.

Un método para la multiprogramación es el Foreground/Background ( o ejecución jerarquizada) (usado en sistemas por tandas, nunca en interactivos), en él hay un proceso prioritario (el foreground (FG)) que se ejecuta con preferencia de todos los demás, cuando este proceso solicita una operación L/E, mientras el s.o. la realiza, el proceso FG estará bloqueado por esta operación y le cede el control al proceso background 1 (BG), y si éste realiza una operación L/E, al BG2,… Cuando uno de los procesos bloqueados se desbloquea, recibe el control del procesador. Para que este método funcione de forma óptima la mejor forma es colocar los procesos ordenados de mayor a menor cantidad de operaciones L/E.

El siguiente diagrama de ejemplo representa el uso del procesador por tres procesos:

Uso del procesador

proceso A | ---- ---- ----
proceso B | ---- ---- ----
proceso C | ---- ---- ----
planificador | -- -- -- -- -- -- -- --
de procesos |
|______________________________________________________

->
tiempo

Como se puede observar en el ejemplo anterior, los procesos alternan periodos en los que progresan en su actividad, cuando están asignados al procesador, con periodos de inactividad, en los que no progresan en absoluto.

Si los periodos de inactividad son los suficientemente pequeños como para que el usuario del sistema operativo no los note, que en práctica se traduce a periodos de inactividad de menos de 100ms, el efecto causado es una ilusión de paralelismo. En caso contrario dará una sensación de que se producen "saltos".

El '''planificador de procesos''' es la parte del sistema operativo que se encarga de decidir qué proceso emplea el procesador en cada instante, por tanto, es el encargado de implementar la multiprogramación.

Modelos de Diseño de Sistemas Operativos

2011-03-22T10:13:03Z

Jdsanchez: /* Sistemas operativos Micronúcleo */

= 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 que 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 que son:

* Modo supervisor, que permite la ejecución de todo el conjunto de instrucciones que ofrece el procesador.
* 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'', se trata de la parte más esencial del sistema operativo. El núcleo de un sistema operativo opera 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 inglés por ''kernel panic''.

= 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
* Micronúcleos

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

http://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/OS-structure2.svg/1024px-OS-structure2.svg.png

== Sistemas operativos Monolíticos ==

Los sistema operativos monolíticos se caracterizan por emplear un núcleo que implementa la planificación 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 estan fuera del nucleo, como los modulos son independientes unos de otros, si cae alguno de ello los demas 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.

== 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 adopta 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 Maquinas Virtuales

** Rendimiento (KVM + paravirtualizacion 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-03-22T10:12:27Z

Jdsanchez: /* Sistemas operativos Micronúcleo */

= 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 que 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 que son:

* Modo supervisor, que permite la ejecución de todo el conjunto de instrucciones que ofrece el procesador.
* 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'', se trata de la parte más esencial del sistema operativo. El núcleo de un sistema operativo opera 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 inglés por ''kernel panic''.

= 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
* Micronúcleos

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

http://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/OS-structure2.svg/1024px-OS-structure2.svg.png

== Sistemas operativos Monolíticos ==

Los sistema operativos monolíticos se caracterizan por emplear un núcleo que implementa la planificación 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 es que se garantiza el aislamiento de las partes que estan fuera del nucleo, como los modulos son independientes unos de otros, si cae alguno de ello los demas 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.

== 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 adopta 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 Maquinas Virtuales

** Rendimiento (KVM + paravirtualizacion 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).

Planificación de procesos de tiempo real

2011-03-21T19:32:11Z

Jdsanchez: /* Métodos de planificación */

Planificación de procesos de tiempo real

2011-03-21T19:29:48Z

Jdsanchez: /* Métodos de planificación */

Criterios de planificación

2011-03-18T12:43:10Z

Jdsanchez: /* Colas multinivel */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización, P=T/t=(w+t)/t y elige el de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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 disminuyendola 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 la 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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado, clasificándolas según sus características, cada cola recibe un tratamiento distinto.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:29:28Z

Jdsanchez: /* Por prioridades */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización, P=T/t=(w+t)/t y elige el de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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 disminuyendola 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 la 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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:26:18Z

Jdsanchez: /* Por prioridades */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización, P=T/t=(w+t)/t y elige el de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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.

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 la 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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:18:57Z

Jdsanchez: /* Métodos apropiativos */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización, P=T/t=(w+t)/t y elige el de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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.

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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:17:14Z

Jdsanchez: /* Basado en índice de penalización */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización, P=T/t=(w+t)/t y elige el de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

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

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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.

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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:16:21Z

Jdsanchez: /* Basado en índice de penalización */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización, P=T/t=(w+t)/t y elige el de mayor valor. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

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

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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.

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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:14:26Z

Jdsanchez: /* El siguiente, el más corto (Shortest Job First: SJF) */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

== 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización y elige el de mayor valor. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

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

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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.

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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:09:13Z

Jdsanchez: /* Por orden de llegada (First In, First Out: FIFO) */

= 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.

== 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 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

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

Se selecciona el proceso que requiera menos tiempo de ejecución. 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. 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización y elige el de mayor valor. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

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

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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.

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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Criterios de planificación

2011-03-18T12:05:18Z

Jdsanchez: /* El siguiente, el más corto (Shortest Job First: SJF) */

= 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.

== 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 lanzamiento. Su principales ventajas son su facilidad de implementación, y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración 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_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

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

Se selecciona el proceso que requiera menos tiempo de ejecución. 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. 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 lleva más tiempo en estado preparado, sin estar en estado activo. Estima los índices de penalización y elige el de mayor valor. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_2__|_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

Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''2/5'''|_0/4|____|____|
z(8)|_1__|_7/5|_'''5/4'''|_1/3|_2/5|
z(12)|_1__|_7/5|_9/4|_5/3|_'''6/5'''| z = índice de penalización
z(17)|_1__|_7/5|_9/4|'''10/3'''|11/5|
z(20)|_1__|_7/5|_9/4|13/3|11/5|

= Métodos apropiativos =

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

== 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, se le asigna el procesador, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. 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.

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|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 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 '''quantuam''' 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''', como sucede con proceso cuyo comportamiento está limitado por operaciones de entrada/salida, se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). 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.
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== 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 establecen varias colas de procesos en estado preparado.

=====En el caso de MINIX (micronucleo) son cuatro colas=====

*1ª) 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.
*2ª) En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
*3ª) Esta cola esta reservada a los procesos e usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
**3ª.a) Cola de procesos interactivos, limitados por E/S.
**3ª.b) Cola de procesos intensivos (o por bloques), 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 procesosde gestion de dispositivos se degrade la eficiencia del sistema.

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

== Colas multinivel con realimentación (feedback)==
Estas son una variante de las colas multinivel en las que los procesos pueden ascender o descender de una cola a otra según su comportamiento, es decir si un proceso no utiliza completamente su ventana de tiempo se le ascenderá a una cola mas prioritaria, sin embargo si este proceso varia su comportamiento realizando tareas mas intensivas este descenderá a otra cola con menor prioridad. (Esto da prioridad a procesos limitados por E/S).

=====Planificador de LINUX 2.6=====
Este planificador posee 140 prioridades (de 0 a 139), de 0 a 99 son para tiempo real y para el resto de procesos que no son de tiempo real de 100 a 139 basadas en el Nice(de -20 a 19).

Posee un mapa de bits (140 bits), 1 bit para cada prioridad en la que implementan distintas estructuras SCHED_FIFO y SCHED_RR ambas para tiempo real y el resto SCHED_OTHER. Esta ultima estructura posee el número de procesos preparados y dos colas, una para los porcesos pendientes y otra para los que ya han consumido su ''quantum''. Cuando un proceso solo consume una parte de su ''quantum'' es insertado al final de la cola de pendientes con lo que le queda de su ventana de tiempo(es decir, si ha consumido el 25% la siguiente vez que se asignado al procesador solo tendra el 75% del ''quantum''), y si consume totalmente su tiempo de asignación al procesador este pasa a la cola de consumido hasta que este totalmente vacía la cola de pendientes. (Esto se hace para compensar los procesos más interactivos)

Esquema de estructura de SCHED_OTHER:

struct{
int num_procesos_preparados
cola pendientes
cola consumido_quantum
}

Usuario:Jdsanchez

2011-02-21T18:09:18Z

Jdsanchez: Nombre

Jose David Sanchez Jimenez