profesioal

Universidad del Valle Sede Yumbo

ALGORITMOS DE
PLANIFICACIÓN

Sistemas Operativos
Ing.Andrea Martínez Rivera

Criterios de Planificación








Utilización de la CPU: Lo que busca el algoritmo es
que nuestra CPU sea utilizada el mayor tiempo posible.
Podemos tener 1, 2 ó más CPU.
Tasa de procesamiento: Esta nos indica el número
de procesos que podemos ejecutar enun determinado
tiempo.
Tiempo de ejecución: El tiempo en el que el
proceso se va a ejecutar.
Tiempo de espera: Son los intervalos en que el
proceso va a esperar para que le asignen la CPU
Tiempo de respuesta: El tiempo en que se va a
demorar en dar respuesta a la solicitud del usuario.

ALGORITMOS DE PLANIFICACIÓN
Los algoritmos pueden ser clasificados en:
 No Expulsivos: Las tareas NOson
expulsadas del procesador antes de concluir
su ejecución. Ej. FIFO, SJF.
 Expulsivos: Las
tareas pueden ser
expulsadas del procesador antes de concluir
su ejecución.
Ej: SRTF, Round Robin,
planificación basada en prioridades.
Sistemas Operativos
Ing.Andrea Martínez Rivera

FIFO o FCFS
(First Input First Output) ó (First Come
First Served)
 Los procesos se ejecutan en elorden de
llegada, el primero que llega se empieza a
ejecutar y los siguientes deben esperar su
turno para poder empezar a ejecutarse.
 Es el algoritmo más sencillo
 Tiempo de espera promedio bastante
largo.


Planificación de la CPU-FIFO o FCFS
Proceso

Tiempo de
llegada

Tiempo de
Ejecución

P1

0

7

P2

2

4

P3

3

3

P4

5

2

Diagrama de Gantt
p10

p2

7

T.Espera : (T.F.Proc-T.Lleg-T.E)
P1=(7-0-7)= 0
P2=(11-2-4)= 5
P3=(14-3-3)=8
P4=(16-5-2)=9
T.P.E = (0+5+8+9)/4= 22/4
T.P.E = 5.5

p3

11

p4

14

16

T.Retorno = (T.F.P-T.Llegada)
P1= (7-0) = 7
P2=(11-2) = 9
P3=(14-3) = 11
P4=(16-5)=11
T.P.R = (7+9+11+11)/4 = 9.5

REPRESENTACION GRAFICA TIPO CRONOGRAMA
P1

P2
P3
P4

0 1

2

3 4

5

6

78 9 10 11 12 13 14 15 16

Tiempo de espera de cada proceso
Tiempo de uso de la CPU

FIFO
Proceso

Tiempo de
llegada

Tiempo de
Ejecución

P1

5

6

P2

2

4

P3

0

3

P4

3

7

P3
0

P2
3

T.Espera
P1=(20-5-6)=9
P2=(7-2-4)=1
P3=(3-0-3)=0
P4=(14-3-7)=4
T.E=(9+1+0+4) = 14
Pro.T.E=14/4 = 3,5 ms

P4
7

P1
14

T.Retorno
P1=(20-5)=15P2=(7-2)= 5
P3=(3-0)=3
P4=(14-3)=11
P.T.R=(34/4)=8.5

20

EJERCICIO
Proceso

Tiempo de llegada

Tiempo de Ejecución

P1

0

4

P2

3

3

P3

3

2

P4

4

3

P5

7

1

•Muestre la planificación FIFO mediante un diagrama de Gantt
•Indique los tiempos de espera y respuesta.

SJF (Shortest Job First)
Este algoritmo asocia con cada proceso la
duración de lasiguiente ráfaga de CPU del
proceso.
 Seleccionar el proceso con menor tiempo
de ejecución
 En caso de empate, aplicar FIFO.
 No es aplicable si se desconoce la duración
de los procesos
 Punto fuerte: Minimizar tiempo de espera.


Sistemas Operativos
Ing.Andrea Martínez Rivera



Ejemplo:
Proceso

Tiempo de llegada

Tiempo de Ejecución

P1

0

7

P2

2

4P3

3

3

P4

5

2

Diagrama de Gantt
p1

0

p4

7

p3

9

p2

12

16

Tiempo de Espera

P1= (7-0-7)= 0

Tiempo Medio Espera= (0+10+6+2)/4 = 18/4= 4.5 ms

P2= (16-2-4)=10

Tiempo Retorno= (7+14+9+4)= 34/4 = 8.5 ms

P3=(12-3-3)=6
P4=(9-5-2)= 2

REPRESENTACION GRAFICA TIPO CRONOGRAMA
P1

P2
P3
P4

0 1

2

3 4

5

6

7

8 9 10 11 12 13 1415 16

Tiempo de espera de cada proceso
Tiempo de uso de la CPU

Proceso

Tiempo de llegada

Tiempo de Ejecución

P1

0

4

P2

0

3

P3

3

2

P4

3

3

P5

7

1

• Muestre la planificación SJF mediante un diagrama de Gantt

•Indique los tiempos de espera y respuesta.

Planificación por prioridad
Cada proceso tiene asignada una
prioridad(número...