Wiki de Sistemas Operativos - Contribuciones del usuario [es]

SO multiprogramables con particiones fijas

2011-12-07T15:29:47Z

Angbergal: /* Ejemplo */ Terminada la solución del ejemplo

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

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

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

= Criterios de asignación =

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

== Mejor ajuste estático ==

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

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

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

La solución sería:

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

=== Otro ejemplo ===

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

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

== Primer ajuste ==

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

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

Dada la siguiente configuración de procesos:

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

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

La solución sería:

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

== Mejor ajuste dinámico ==

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

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

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

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

La solución sería:

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

== Mejor ajuste dinámico con aplazamiento limitado ==

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

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

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

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

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | < | | | | | | |---|---|---|---> | | | | | | | |

P5 | < | | | |---|---|---> | | | | | | | | | | | |

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

== Subparticiones ==

No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco 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 =

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

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método es más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

** '''Reubicación dinámica parcial''': Es una variante del anterior, en la que existe también un registro límite.

= Mecanismos de protección de memoria =

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

Mensajería

2011-11-16T16:12:45Z

Angbergal: /* Denominación Directa */

Un mensaje es un contenedor que se emplear para intercambiar información entre dos o más procesos. Los mensajes tienen un cierto formato generalmente compuesto por una cabecera, que contiene metainformación tales como la fuente y el destinatario, y un cuerpo, que contiene información específica.

Los mecanismos de mensajería se refiere al conjunto de funcionalidades que permiten al sistema operativo realizar la entrega de un mensaje a uno o varios procesos. Mediante dicho mecanismo también es posible resolver problemas de concurrencia.

Los sistemas operativos generalmente ofrecen dos llamadas al sistema para que un proceso pueda enviar y recibir mensajes:

* <tt>send (mensaje)</tt>: Para enviar un mensaje
* <tt>receive (mensaje)</tt>: Para recibir un mensaje

== Formas de identificación ==

Para identificar la fuente y el destino de nuestro mensaje se pueden emplear dos estrategias.

=== Denominación Directa ===

En este caso se emplea un ID que permite identificar a la fuente y al destinatario de manera unívoca en el sistemas, por ejemplo, el PID de un proceso. La denominación directa permite tres configuraciones:

* ''Unicast'', de manera que la comunicación sucede entre una fuente y un destinatario.
* ''Broadcast'', el emisor envía un mensaje a '''todos''' los procesos existentes en el sistema.
* ''Multicast'', el emisor envía un mensaje a un grupo de procesos, siendo un grupo un subconjunto de procesos existentes en el sistema. El sistema operativo debe ofrecer llamadas al sistema que permitan a los procesos crear grupos y suscribirse a ellos.

El principal inconveniente de la denominación directa es que se pierde el mensaje si el destino no se encuentra.

=== Denominación Indirecta ===

Se emplea un elemento intermediario denominado ''buzón''. El sistema operativo ofrece llamadas al sistema que permiten la creación y destrucción de buzones, por ejemplo, '''CreateMailbox''' y '''DestroyMailbox'''. Una vez creado el buzón, se emplea éste para realizar la comunicación entre procesos.

El sistema operativo debe de comprobar que la identidad de la fuente de un mensaje es correcta, de lo contrario un proceso podría suplantar la identidad de otro.

== Formas de transmisión ==

Distinguimos tres formas de transmisión: Transmisión por copia, transmisión por referencia y transmisión por copia en caso de escritura.

=== Transmisión por copia ===

Si se emplea ''denominación directa'', al invocar el receptor la llamada ''recv'', el mensaje se copia de espacio de memoria del emisor al espacio de receptor. Esta forma de implementar la transmisión tiene un coste de orden lineal <math>O(n)</math>.

Si se emplea ''denominación indirecta'', al invocar ''send'' el emisor, el mensaje se copia del espacio de emisor al espacio del buzón, que se encuentra en el espacio de memoria del sistema operativo. Una vez que el receptor invoca ''receive'', se copia el mensaje al espacio de memoria que el receptor ha habilitado para almacenar el mensaje.

=== Transmisión por referencia ===

Es una mejora frente a la transmisión por copia.

* ''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 una estructura de datos con capacidad de almacenamiento limitada, dependiente del proceso destinatario o en el buzón del SO. Al ser enviados, los mensajes irán encolándose para que el proceso receptor pueda gestionarlos cuando pueda. De esta manera se aumenta el rendimiento pero se requiere de políticas adicionales de tratamiento de los mensajes si la capacidad de almacenamiento de la estructura de datos se ve sobrepasada(PE, eliminación de mensajes, realocalización de memoria, etc..)

* Comportamiento del receptor, '''recv()'''
** ''Bloqueante'': una llamada a recv() sin mensajes a procesar pasa el proceso llamante a estado bloqueado. Un send() de otro proceso que añada un mensaje a la cola del proceso bloqueado hace que éste pase a estado preparado.
** ''No bloqueante'': una llamada a recv() sin mensajes a procesar devuelve un mensaje de error, pero la ejecución del proceso llamante continúa.

== Formato de los mensajes ==

=== Fijo ===

Los procesos acuerdan emplear un formato fijo para sus mensajes.

'''Ejemplo''': Simple Network Time Protocol.<ref> Véase http://tools.ietf.org/html/rfc4330, sección 4, Message Format.</ref>

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.<ref>Ver Communicating between the kernel and user-space in Linux using Netlink Sockets (http://1984.lsi.us.es/~pablo/docs/spae.pdf)</ref>
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align="center" style="background:DarkSlateBlue; color:white"|'''Type-Length-Value'''
! width="15 px" style="background:#efefef;" | 0
! width="15 px" style="background:#efefef;" | 1
! width="15 px" style="background:#efefef;" | 2
! width="15 px" style="background:#efefef;" | 3
! width="15 px" style="background:#efefef;" | 4
! width="15 px" style="background:#efefef;" | 5
! width="15 px" style="background:#efefef;" | 6
! width="15 px" style="background:#efefef;" | 7
! width="15 px" style="background:#efefef;" | 8
! width="15 px" style="background:#efefef;" | 9
! width="15 px" style="background:#efefef;" | 10
! width="15 px" style="background:#efefef;" | 11
! width="15 px" style="background:#efefef;" | 12
! width="15 px" style="background:#efefef;" | 13
! width="15 px" style="background:#efefef;" | 14
! width="15 px" style="background:#efefef;" | 15
! width="15 px" style="background:#efefef;" | 16
! width="15 px" style="background:#efefef;" | 17
! width="15 px" style="background:#efefef;" | 18
! width="15 px" style="background:#efefef;" | 19
! width="15 px" style="background:#efefef;" | 20
! width="15 px" style="background:#efefef;" | 21
! width="15 px" style="background:#efefef;" | 22
! width="15 px" style="background:#efefef;" | 23
! width="15 px" style="background:#efefef;" | 24
! width="15 px" style="background:#efefef;" | 25
! width="15 px" style="background:#efefef;" | 26
! width="15 px" style="background:#efefef;" | 27
! width="15 px" style="background:#efefef;" | 28
! width="15 px" style="background:#efefef;" | 29
! width="15 px" style="background:#efefef;" | 30
! width="15 px" style="background:#efefef;" | 31

|-
| colspan=16, align="center"| Length
| colspan=16, align="center"| Type
|-
| colspan=32, align="center"| 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).<ref>Ver http://www.ietf.org/rfc/rfc791.txt, sección 3.1.</ref>

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

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

==Referencias==
<references/>

Criterios de planificación

2011-11-02T16:04:52Z

Angbergal: /* Turno rotatorio con compensación */

=4.3.1 Métodos no apropiativos =

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

== Estocástico ==

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

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

== Con conocimiento del futuro ==

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

Ejemplo:

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

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

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

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

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

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

Ejemplo:

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

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

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

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

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

Ejemplo:

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

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

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

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

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

Ejemplo:

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

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

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

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

=4.3.2 Métodos apropiativos =

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

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

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

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

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

Ejemplo:

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

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

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

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

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

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

El orden es siempre O(n).

Ejemplo:

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

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

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

== Turno rotatorio ==

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

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

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

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

Puesto que el reparto del procesador es estricto, los procesos recién lanzados deben acceder al procesador lo antes posible, por tanto, se les da oportunidad de ejecución por orden de llegada por delante de los procesos en la cola de procesos preparados. De esta manera, se evita que los procesos recién lanzados queden postergados indefinidamente.

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

Ejemplo:

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

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

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

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

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

Ejemplo:

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

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

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

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

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

== Colas multinivel ==

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

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

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

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

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

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

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

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

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

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

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

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

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

Ejemplo:

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

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

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