ALGOTRITMOS DE PLANIFICACIÓN

 

FIFO:

 

FIRST-COME, FIRST SERVED (FCFS)

 

La política más simple de planificación es la FCFS. A medida que un proceso pasa al estado listo, este es agregado a la cola de listos. Cuando el proceso que actualmente está ejecutando cesa su ejecución entonces el proceso más viejo en la cola es seleccionado para correr. La implementación de esta política es a través de colas FIFO (First-In, First-Out). Cuando el CPU está libre, éste es asignado al proceso que está en la cabeza de la cola.

 

FCFS es un algoritmo nonpreemptive, pues una vez que el CPU es asignado a un proceso, este lo mantiene hasta que espontáneamente lo suelta, ya sea porque el proceso finalizó o por algún requerimiento de E/S.

 

El tiempo de espera bajo esta política tiende a ser alto. Además , tiende a favorecer aquellos procesos que requieren más tiempo de CPU (CPU-bound). Consideren el caso donde tenemos una colección de procesos. Uno de ellos utiliza más CPU que los otros, y el resto de los procesos requieren más trabajo de E/S (I/O-bound). Cuando el proceso CPU-bound ejecuta, los otros procesos esperan. Algunos de estos estarán en las colas de los dispositivos de E/S pero eventualmente en algún instante pasarán a la cola de procesos listos. En este momento, muchos de los dispositivos de E/S estarán ociosos. Cuando el proceso en ejecución deje el estado Running, los procesos I/O-bound pasarán a ejecutar y rápidamente volverán a bloquearse en espera de E/S. Si el proceso CPU-boundse encuentra bloqueado, entonces el procesador estará ocioso. Por lo tanto, FCFS puede ocasionar un uso indeficiente tanto del procesador como de los dispositivos de E/S.

 

 

 

Proceso

Tiempo de llegada

Tiempo de Servicio

Tiempo de Comienzo

Tiempo de Finalización

Turnaround

Tiempo de Espera

A

0

1

0

1

1

0

B

1

100

1

101

100

0

C

2

1

101

102

100

101-2=99

D

3

100

102

202

199

102-3=99

Promedio

 

 

 

 

100

49.50

 

 

Proceso

Tiempo de llegada

Tiempo de Servicio

Tiempo de Comienzo

Tiempo de Finalización

Turnaround

Tiempo de Espera

B

0

100

0

100

100

0

D

1

100

100

200

199

100-1=99

A

2

1

200

201

201-2=199

200-2=198

C

3

1

201

202

202-3=199

201-3=198

Promedio

 

 

 

 

232

123.50

 

 

El tiempo promedio de espera bajo una política FCFS generalmente no es mínimo y puede variar sustancialmente si hay mucha diferencia entre las duraciones de ciclo de los procesos.

 

En el segundo ejemplo, se presenta un efecto convoy donde los procesos esperan a que un proceso grande deje el CPU

 

ROUND ROBIN(TURNO PRIORITARIO)

 

Una manera rápida de reducir la penalización que los procesos cortos sufren con FCFS es usar expropiación basada en un reloj. Una interrupción de reloj es generada a intervalos periódicos. Cuando ocurre la interrupción, el proceso en ejecución es colocado en la cola de procesos listos y el próximo trabajo es seleccionado basado en el esquema FCFS. A cada proceso se le da un trozo de tiempo.

La principal decisión de diseño que surge con Round Robin es el tamaño del trozo o quantum. Si el quantum es muy corto, entonces los procesos se moverán a través del sistema rápidamente. Por otro lado, hay un cierto overhead o desperdicio de tiempo envuelto con el manejo de la interrupción de reloj y las funciones de planificación y despacho. Por lo tanto quanta muy pequeños deberían evitarse. Una alternativa es usar un quantum de tiempo que sea un poco más grande que el tiempo promedio requerido para una interacción típica.

Round Robin es particularmente efectivo para sistemas generales de tiempo compartido. Se implementa con una cola FIFO de procesos. Nuevos procesos son agregados al final de la cola, y toma el proceso que se encuentra en la cabeza de la cola. Actualiza el timer para que interrumpa después del quantum de tiempo.

El desempeño de este algoritmo dependerá del tamaño del quantum. Si el quantum es infinito entonces degenera en FCFS. Si el quantum es muy pequeño entonces Round Robin es llamado compartición de CPU y en teoría pareciera que cada proceso tiene su propio procesador corriendo a 1/n la velocidad del procesador real.

Bajo este esquema es importante considerar el efecto del cambio de contexto.

 

Round Robin (RR q=3)

Proceso

Tiempo de llegada

Tiempo de Servicio

Tiempo de Comienzo

Tiempo de Finalización

Turnaround

Tiempo de Espera

A

0

8

0, 12, 21

3, 15, 23

23

15

B

1

4

3, 15

6, 16

16-1=15

11

C

2

9

6, 16, 23

9, 19, 26

26-2=24

15

D

3

5

9, 19

12,21

21-3=18

11

Promedio

 

 

 

 

20

13

 

 

PRIORIDAD:

 

En muchos sistemas, los procesos tienen prioridades asignadas, y el planificador escogerá aquel proceso con mayor prioridad.

Cuando un proceso debe ser seleccionado, el planificador por prioridades seleccionará aquel proceso que tenga mayor prioridad. Si hay más de un proceso entonces se deberá seguir alguna política de selección.

Un problema que presenta un esquema de planificación por prioridades puro es que los procesos con la prioridad más baja pueden sufrir de inanición o bloqueo indefinido. Un proceso que está listo para correr pero espera porque siempre hay procesos con prioridad más alta.

Para evitar este problema, se puede ir incrementando gradualmente la prioridad de los procesos (envejecimiento).

SJF es un caso especial de planificación por Prioridad, donde la prioridad es el inverso del valor estimado del próximo ciclo de CPU ( a menor ciclo, mayor prioridad).

 

Proceso

Tiempo de llegada

Prioridad

Tiempo de Servicio

Tiempo de Comienzo

Tiempo de Finalización

Turnaround

Tiempo de Espera

A

0

2

8

0

8

8

0

B

1

1

4

22

26

26-1=25

22-1=21

C

2

4

9

8

17

17-2=15

8-2= 6

D

3

2

5

17

22

22-3=19

17-3=14

Promedio

 

 

 

 

 

16.75

10.25

 

Este algoritmo puede ser preemptive y nonpreemptive. En el caso de preemptive, cuando un proceso llega a la cola de procesos listos, su prioridad es comparada con la prioridad del proceso que está corriendo. Si la prioridad del nuevo proceso es mayor, entonces se atiende al nuevo proceso.

 

 

SHORTEST-JOB-FIRST (SJF)

 

Este algoritmo selecciona al proceso con el próximo tiempo de ejecución más corto. Un proceso corto saltará a la cabeza de la cola. La ejecución de un proceso consiste en ciclos de ejecución de CPU y ciclos de espera por E/S. El algoritmo selecciona aquel proceso cuyo próximo ciclo de ejecución de CPU sea menor. El problema está en conocer dichos valores, pero podemos predecirlos usando la información de los ciclos anteriores ejecutados.

 

SJF

Proceso

Tiempo de llegada

Tiempo de Servicio

Tiempo de Comienzo

Tiempo de Finalización

Turnaround

Tiempo de Espera

A

0

8

0

8

8

0

B

1

4

8

12

12-1=11

8-1=7

C

2

9

17

26

26-2=24

17-2=15

D

3

5

12

17

17-3=14

12-3=9

Promedio

 

 

 

 

14.25

10.33

 

FCFS

Proceso

Tiempo de llegada

Tiempo de Servicio

Tiempo de Comienzo

Tiempo de Finalización

Turnaround

Tiempo de Espera

A

0

8

0

8

8

0

B

1

4

8

12

12-1=11

8-1=7

C

2

9

12

21

21-2=19

12-2=10

D

3

5

21

26

26-3=23

21-3=18

Promedio

 

 

 

 

20.33

11.66

 

El SJF es probablemente optimal pues da el mínimo tiempo promedio de espera. El problema está en conocer la duración del próximo requerimiento de CPU para cada proceso. Esta duración puede predecirse suponiendo que el próximo ciclo puede ser similar a los anteriores.

 

Este algoritmo puede ser preemptive o no. Cuando un nuevo proceso llega a la cola de procesos listos mientras otro se está ejecutando, el nuevo proceso puede tener el ciclo de duración de CPU más corto que lo que falta por ejecutar del proceso actual. En el caso de un esquema preemptive, el CPU será asignado al proceso que acaba de llegar a la cola. Este algoritmo se conoce como Shortest Remaining Time First (SRTF).

 

http://www.ldc.usb.ve/~spd/Docencia/ci-3821/Tema4/node8.html

 

Algoritmo de Planificación SJF en C

SJF

http://www.utpl.edu.ec/blog/sistemasoperativos/category/algoritmos-de-planificacion/

 

 

 

 

 ALGORITMO SRTF (“SHORTEST REMAINING TIME FIRST”)

_ Asociar a cada proceso el tiempo de ráfaga de CPU restante.

Seleccionar el proceso con menor ráfaga de CPU restante.

En caso de empate, aplicar FCFS.

_ Algoritmo expulsivo: Realizar cambio de contexto si llega un proceso a la

cola de procesos listos con ráfaga de CPU menor que el tiempo restante

del proceso en ejecución.

_ Óptimo al minimizar el tiempo medio de espera.

 

 http://www3.uji.es/~castillo/ii11/teoria/TraspasTema3.pdf

 

 

COLAS MÚLTIPLES:

 

 

Colas multinivel con realimentación:

_ Varias colas para los procesos listos.

_ Un proceso se mueve de una cola a otra.

_ Sistema de colas definido por:

_ Número de colas.

_ Algoritmo de planificación de cada cola.

_ Cola en la que entrará un proceso al llegar a preparado.

_ Planificación entre colas.

_ Método para determinar la realimentación:

_ Cuándo promover un proceso a una cola de mayor prioridad.

_ Cuándo degradar un proceso a una cola de menor prioridad.

 

Colas multinivel sin realimentación:

_ Varias colas para los procesos listos.

_ Cada cola tiene su propio algoritmo de planificación.

_ Sistema de colas definido por:

_ Número de colas.

_ Algoritmo de planificación de cada cola.

_ Planificación entre colas.

_ Prioridad a cada cola.

_ Cuantum de CPU a cada cola, que se reparte entre los

procesos de cada cola.


EJEMPLOS DE C++:

#include <stdlib.h>

#include <iostream.h>

struct estudiante {

char nombre [20];

int edad;

estudiante *enlace;

};

estudiante *cabeza=NULL;

estudiante *cola=NULL;

void insertar(char *nombre, int edad);

void presentarlista();

int main()

{
char continua = ’s’;

char nombre [20];

int edad;

while (continua == ’s’){

cout<< “Ingrese el nombre y la edad del estudiante”<> nombre >> edad;

insertar(nombre, edad);

cout<> continua;

}

presentarlista();
system(”PAUSE”);
return 0;

}

void insertar(char *nombre, int edad) {

if (cabeza == NULL) { // Si no hay ningún nodo en la lista

cabeza = new estudiante;

cola = cabeza;

}
else { // Si ya hay nodos en la lista

cola->enlace = new estudiante;

cola = cola->enlace;

}
// strcpy (cola->nombre, nombre);

cola->edad = edad;

cola->enlace = NULL;

}

// Rutina que presenta la lista ingresada

void presentarlista(){

estudiante *recorrer=cabeza; // variable auxiliar

while (recorrer != NULL) { // si aun hay elementos en la lista

// presentar el nombre y la edad

cout<< “Nombre: “<nombre << ” edad: “<edad <enlace;

}
}

 

http://www.utpl.edu.ec/blog/sistemasoperativos/category/algoritmos-de-planificacion/

 

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: