View
61
Download
0
Category
Preview:
DESCRIPTION
s
Citation preview
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 1/63
Sistemas
Operativos I Ing. Jorge Garza Murillo
Sesión 8
1
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 2/63
Ejerciciosde scheduling
de procesos
(CPU Scheduling)
2
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 3/63
Conceptos clave
Tiempos: Tiempo de CPU / Ráfaga de CPU Terminación Llegada
Parámetros (para la política de Scheduling): Prioridad Quantum
Cambio de contexto
3
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 4/63
Conceptos clave
Criterios de comparación (métricas): Turnaround Tiempo de espera Throughput
Tipos de política de scheduling: Expropiativas No expropiativas
4
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 5/63
Clasificación de políticas descheduling
Scheduling
Expropiativo No expropiativo
RRMLFQ
SRT
SJF
HRN
FCFS
SJFExpropiativo
Priority Priority
5
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 6/63
Nota importante
En todos los ejercicios, se pide calcular elturnaround promedio para la secuencia deprocesos dada.
En algunos casos, también se pidecalcular el tiempo promedio de espera.
6
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 7/63
1. Utilizando Round-Robin con Q = 1 (Expropiat ivo)
Nota - La letra representa el JOB y el númeroentre paréntesis su RÁFAGA DE CPU.
Ejercicios
t = 0 A (5) t = 2 D (2) t = 3 E (4) t = 5 G (1)
B (3) F (3)
C (1)
JOB
en elCPU A B C A B D E F A B G D E F A E F A E
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
TiempoLlegadas
Llegadas:
7
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 8/63
TT TLL TU
TT - tiempo de terminación, TLL - tiempo de llegada,
TU - turnaround
0 C (1) B (3)
1 A (4) C (1)
2 D (2) B (2) A (4)
3 F (3) E (4) D (2) B (2)
4 A (3) F (3) E (4) D (2)5 G (1) B (1) A (3) F (3) E (4)
6 D (1) G (1) B (1) A (3) F (3)
7 E (3) D (1) G (1) B (1) A (3)
Tiempo Cola de listos CPU
A (5)
B (3)
C (1)
A (4)
B (2)D (2)
E (4)
F (3)
C
B
G
D
FA
E
3 0 3
10 0 10
11 5 6
12 2 10
17 3 1418 0 18
19 3 16
TU promedio = 77 / 7 = 11
RR . . . . . . . . .
En este ejemplo, se le da prioridad para formarse en la cola de listos al
proceso que sale del CPU sobre el que llega a la cola de listos (nuevo)
8
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 9/63
•¿Cuál sería el tiempo de espera promedio?
JOB
A B C A B D E F A B G D E F A E F A E1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
TiempoLlegadas
Tiempo de espera (sacado directamente de la gráfica)
A
B
C
DE
F
G
2 + 4 + 5 + 2 = 13
1 + 2 + 4 = 7
2 = 2
3 + 5 = 8
3 + 5 + 2 + 2 = 12
4 + 5 + 2 = 11
5 = 5
Tiempo de esperapromedio = 58/7 = 8.2
Otra forma de calcularlo sería:T. Espera = Turnaround – T. de CPU
Ej.: T. de espera de A = 18 – 5 = 13
9
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 10/63
2. Usando SRT (Shortest Remaining Time)
Expropiativo, Q = 1
t = 0 A (5) t = 2 D (2) t = 3 E (4) t = 5 G (1)
B (3) F (3)
C (1)
C B D D B G B F E A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
TiempoLlegadas
10
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 11/63
TT TLL TU
C
D
G
B
F
E
A
1 0 1
4 2 2
6 5 1
7 0 7
10 3 7
14 3 11
19 0 19
T = 48 / 7 = 6.85
Longitud Máxima de la cola de listos = 4
0
1
2
3
4
5
6
A (5) B (3)
A (5)
A (5) B (2)
A (5) E (4) F (3) B (2)
A (5) E (4) F (3)
A (5) E (4) F (3) B (1)
A (5) E (4) F (3)
C (1)
B (3)
D (2)
D (1)
B (2)
G (1)
B (1)
Tiempo Cola de listos CPU
SRT . . . . . . . . . . .
En este ejemplo, se le da
prioridad para formarse en
la cola de listos al proceso
que llega a la cola de
listos (nuevo) sobre el
que sale del CPU11
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 12/63
• Calcule el tiempo de espera promedio
C B D D B G B F E A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
TiempoLLegadas
Tiempo de espera
A
B
CD
E
F
G
14 = 14
1 + 2 + 1 = 4
0 = 00 = 0
7 = 7
4 = 4
0 = 0
Tiempo de esperapromedio = 29/7 = 4.1
12
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 13/63
IMPORTANTE
• Si no nos dan criterios claros y específicos, para lasolución no será relevante si se da prioridad paraformarse en la cola de listos al proceso nuevo que llegapor primera vez a listos o al que ya estaba en el sistema,lo importante es utilizar siempre el mismo criterio, esdecir; ser consistente.
• Es decir; para probar el funcionamiento de cualquiera delos algoritmos, ambos criterios pueden ser igualmenteválidos, tomando como base la consistencia mencionada.
13
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 14/63
3. Usando FIFO (no expropiativo)
t = 0 A (5) t = 2 D (2) t = 3 E (4) t = 5 G (1)
B (3) F (3)C (1)
Tiempo
A B C D E F G
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1718 19 20 21
A
B
C
D
E
F
G
5 0 5
8 0 8
9 0 9
11 2 9
15 3 12
18 3 15
19 5 14
Orden TT TLL TU (turnaround)
TU promedio = 72/7= 10.2
14
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 15/63
4. SJF vs SRT
A(8) B(4) C(3) D(7) E(4) ---> Llegadas
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23Tiempo
A C B D E
8 11 15 22 26
SJF (no expropiativo), sin cambio de contexto
SJF con cambio de contexto = 2
A C B DE
8 10 13 15 19 21 25 27 34
CC CC CC CC
15
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 16/63
SRT (igual a SJF expropiativo), CC = 2
JOB SJF SRT
A
B
CD
E
(8 - 0) = 8
(19 - 2) = 17
(13 - 6) = 7(34 - 14) = 20
(25 - 16) = 9
TU Prom. = 12.2
(29 - 0) = 29
(8 - 2) = 6
(13 - 6) = 7(38 - 14) = 24
(22 - 16) = 6
TU Prom. = 14.4
A(8) C(3) D(7) E(4)LLEGADAS
B(4)
A CB E
0 2 4 6 8 10 13 15 16 18 22 24 29 31 38
CC CC CC A CC CC CCA D
16
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 17/63
Anexos
17
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 18/63
CPU scheduling
También conocido como: Asignación del CPU
Asignación del procesador
Planificación del procesador
Calendarización del procesador
18
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 19/63
Ready
5
1, 4, 9
2, 3, 5, 6, 7, 8
3, 5, 10
5
Running
Waiting
Determinar qué proceso
se asigna a qué procesador
CPU
Scheduling
CPU Scheduling
Ready
=
19
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 20/63
( 1 ) Prioridad
( 2 ) Quantum( 3 ) I/O Bound,
CPU Bound
( 4 ) Políticas de
Asignacióndel CPU
( 5 ) Criterios decomparación
entre políticas
( 6 ) Cambio de contexto
( 7 ) Interrupciones( 8 ) Expropiativo
y No Expropiativo
( 9 ) Postergación
indefinida
(10 ) Deadlock
• Algunos aspectos a considerar en relacióna CPU Scheduling
CPU Scheduling
20
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 21/63
Administración del procesador
Objetivos Conocer las distintas disciplinas para
administrar el CPU, y su funcionamiento.
Conocer los conceptos:CPU-bound process & I/O-bound process
Quantum, prioridad, throughput, turnaround
21
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 22/63
Administración del procesador
Conocer los distintos componentesdel administrador del procesador.
Aplicar lo anterior a problemas tipo.
22
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 23/63
Administración del procesador
Scheduler Parte del sistema operativo encargada de
administrar:
La entrada de jobs al sistema.Suspender / activar los procesos dependiendo.de las cargas del sistema.Seleccionar el procesoal que se le asigna el CPU.
23
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 24/63
Administración del procesador
El Scheduler se divide en 3 partes:
Scheduler de alto nivel Job
Scheduler
Scheduler intermedio
Scheduler de bajo nivel Dispatcher
24
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 25/63
Actividades específicas de cada nivel de Scheduler
Jobs esperandoentrar
Job esperandoiniciación
Procesossuspendidos esperando
su (re) activación
Procesosactivos
Procesoscorriendo
Job entra
Iniciación del job
suspenderactivar
Despacho
Terminó
Asigna los recursos para el proceso,ejemplo memoria
Decide el nivel de multiprogramación
JobSchedulero schedulerde largoplazo
Schedulerintermedio
Decide qué proceso pasa a listos
Suspender y reactivar procesos
Selecciona - en base a la política de
Scheduling - qué proceso entra al CPU
Realiza el cambio de contexto
block o
quantumagotado
CPUSchedulero schedulerde cortoplazo
25
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 26/63
Criterios de Scheduling
Entre los criterios que se utilizan paracomparar los distintos algoritmos deplanificación del CPU (CPU Scheduling
Algorithms)
Podemos mencionar:
26
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 27/63
Criterios de Scheduling
Utilización del CPU. Consisteen registrar/monitorear el % del tiempoque el CPU esta ocupado.
Típicamente varía en un rango que vadesde un 40% para un sistema con una
carga de procesos ligera, hasta un 100%para un sistema intensivamente utilizado.
27
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 28/63
Criterios de Scheduling
Throughput.
Se define comoel número de procesos que son
completamente terminados en un intervalo detiempo.
Algunos ejemplos:
50 procesos por hora,2500 procesos por día,10 transacciones por segundo, etc.
28
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 29/63
Criterios de Scheduling
Turnaround time Esta es una medida de comparación que
incorpora
el punto de vista de un procesoen particular.
Tiene varias definiciones comúnmente
aceptadas:
29
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 30/63
Criterios de Scheduling
Es el tiempo total de estanciade un proceso en el sistema computacional;es decir,
es el tiempo desde que llegael proceso hasta que termina.
Es el tiempo transcurrido desde que se envíaun proceso a ejecutar (por ejemplo desde una
terminal), hasta que éste termina.
30
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 31/63
Criterios de Scheduling
Es la suma de todos los tiemposde un proceso; es decir: Turnaround time =
Tiempo de espera en colas + tiempo de CPU(ready, waiting, etc).
31
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 32/63
Criterios de Scheduling
Waiting time Se define como el tiempo total
invertido por un proceso esperando
en colas.Response time Para sistemas interactivos, esta
medida generalmente complementa alturnaround time.
32
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 33/63
Criterios de Scheduling
Se define como el tiempo transcurridodesde que se inicia una transacción(proceso) hasta que se empieza a recibir
una respuesta.
33
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 34/63
Criterios de Scheduling
Varios ejemplos: Hacer una consulta en Internet, consultar los
datos de un empleado en una terminal,
teclear un comando para listar los procesosen cola de impresión, etc.
34
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 35/63
Políticas de scheduling
• Clasificación de políticas de schedulingScheduling
Expropiativo No expropiativo
RRMLFQ
SRT
SJF
HRN
FCFS
SJFExpropiativo
Priority Priority
35
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 36/63
Políticas de “scheduling”
de procesosNo expropiativo (nonpreemptive) Una vez que el CPU ha sido asignado a un
proceso, el proceso mantiene el control del
CPU hasta que termina o hasta que pasaal estado de bloqueado (liberael control por sí mismo).
36
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 37/63
Políticas de “scheduling”
de procesosExpropiativo (preemptive) El proceso que controla el CPU,
no decide cuando va a perder
el control de él. Dependede la política de Scheduling.
El hecho de que sea preemptive permiteusuarios interactivos en el sistema, perorequiere más tiempo de administración(cambios de contexto, más memoria, etc).
37
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 38/63
Políticas de “scheduling”
de procesosOtros factores que impactan las políticasde Scheduling: Uso de prioridades (estáticas, dinámicas, $).
Uso de tiempos estimados de ejecución.
38
lí d h d l
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 39/63
Políticas de schedulingNo expropiativo
FCFS – First Come, First Served
Bloqueado
Cola de listosC B A
Terminaejecución
CPU
I/O
39
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 40/63
FCFS
Al liberarse el CPU, éste se asigna alprimer proceso en la cola de listos.
Los procesos se colocan en la colade listos según su orden de llegada.
40
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 41/63
FCFS
Si el proceso se bloquea por I/Oantes de terminar su ejecución, eldespachador selecciona el siguienteproceso en la cola de listos paraque entre a ejecución.
41
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 42/63
FCFS
Casi siempre se utiliza como segundaopción.
Favorece trabajos largos que utilizanmucho CPU.
42
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 43/63
(se agotó el Quantum)
Políticas de scheduling
RR –
Round Robin (Expropiativo)Bloqueado
Cola de listos
C B A CPU Termina
CPU
I/O
Expropiación
43
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 44/63
RR
El CPU se asigna al primer procesoen la cola de listos.
Los procesos se colocan en la colade listos según su orden de llegadaEl proceso al agotar su Quantum
regresa a la cola de listos.
44
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 45/63
RR
Si el proceso se bloquea por I/O, seselecciona el siguiente proceso de lacola de listos para que entre aejecución.Esta técnica es efectiva en ambientesde tiempo compartido, donde esimportante optimizar el tiempo derespuesta.
45
Round Robin
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 46/63
C B A X
a) Si termina XC B A
b) Si se bloquea X lista de bloqueados
C B A Xc) Si X agota su quantum
X C B A
Round Robin
Cola de listos En ejecución
El proceso que está en ejecución, no se interrumpedebido a la llegada de jobs con mayor prioridad
46
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 47/63
Round Robin
Efectos del cambio en el tamaño delquantum
Quantum Es el tiempo máximo que se le permite
ejecutar a un proceso cada vez que se le
asigna el CPU.
47
Round Robin Efectos del cambio
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 48/63
Round Robin.- Efectos del cambioen el tamaño del quantum
Q= 2 unidades Q (Quantum)CC= 1 unidad CC (Cambio de contexto)
Proceso A Necesita 3 unidades
de tiempo del CPUProceso B Necesita 1.5 unidades
de tiempo del CPU
A B
B
CC 1 2 3 4 5 5.5 6.5 7.5
A
A
48
Round Robin
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 49/63
Round Robin
En 18 unidades de tiempo sólo 9 fueron
de trabajo productivo 50% de eficiencia
Q = 1 CC = 1 A = 3 B = 4, C = 2
Tiempo de CPU requerido
B Acc cc
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
CBcc A cc B cc A Bcc Ccc cc cc
A B C
(A, B llegan en t = 0,C llega en t = 10)
49
Round Robin
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 50/63
Tiempo de CPU requerido
En 13 unidades de tiempo sólo
9 fueron para trabajo productivo 70% de eficiencia
Si quantum muy grande Tiende a FCFS
Si quantum muy pequeño demasiado
overhead en CC
B C
CB
cc C A
A
cccc1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
B
Q = 3 CC = 1 A = 3 B = 4, C = 2
Round Robin
(A, B llegan en t = 0,C llega en t = 10)
50
SJF - Shortest Job First (No expropiativo)
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 51/63
CC = 1tiempo actual = 4
no haymás llegadas
• Favorece jobs cortos
• Puede provocar postergación indefinida
0 1 2 3 4 6 11 17 24
TIEMPO
Sale X
X D A B C
D A B C
CC CC CCCC
SJF Shortest Job First (No expropiativo)Selecciona al proceso con tiempo estimado de ejecución
más pequeño
A 3 4B 2 5
C 1 6D 3 2
Tiempoestimadoejecución
Tiempollegada
Job(proceso)
51
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 52/63
• Selecciona para ejecución al proceso con mayorprioridad basado en la siguiente ecuación:
• Disminuye el problema de SJF con procesos querequieren mucho tiempode ejecución.
HRN Scheduling
HRN-Highest-Response-ratio-Next scheduling(No expropiativo)
Tiempo estimado de ejecuciónPrioridad=
Tiempoen cola
+Tiempo estimadode ejecución
52
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 53/63
HRN Scheduling
• La gráfica en la siguiente página muestra
los cálculos de prioridad en t = 3, t = 10 yt = 13 que es donde ocurren los cambiosde contexto.
Job T.Ll. T.Ej. A 3 4B 2 5
C 1 6D 3 2
CC = 1Tiempo = 4
53
HRN Scheduling
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 54/63
1 2 3 10 13
saleX
C D A B
X C D A B
PA = 4 + 0 = 14
PB = 5 + 1 = 1.25
PC = 6 + 2 = 1.336
PD = 2 + 0 = 12
PA = 4 + 7 = 2.754
PB = 5 + 8 = 2.65
PD = 2 + 7 = 4.52
PA = 4 + 10 = 3.54
PB = 5 + 11 = 3.2
5
HRN Scheduling
54
SRT
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 55/63
SRTShortest Remaining Time (Expropiativo)
Selecciona para ejecución el proceso contiempo estimado restante de ejecuciónmás pequeño.
Si durante su ejecución llega otroproceso, cuyo tiempo estimado deejecución es menor que lo que le falta al
proceso que está corriendo, entonces sereemplaza a éste en el CPU por elproceso más corto.
55
SRT
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 56/63
SRT
1 2 3 4 5 6 7 8 9 10
D E D
E D
Nuevallegada
Tiempo
de llegada
t = 0
CC = 1
ABCDE
56
642
00
002
(Este gráfico no muestra
la solución completa)
Tiempo estimado
de ejecución
Procesos
56
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 57/63
8 9 10 11 12
D D X otro procesoD X
llega X
• Siguiendo con el ejemplo anterior,
suponga que en la unidad de tiempo 8llega un proceso X con tiempo estimadode ejecución de 3/4.
57
X D
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 58/63
En t = 8 al proceso D le faltaba 1 unidad paracompletar su ejecución. Si comparamos estagráfica y la de la página anterior; podemosconcluir que en este caso particular reemplazarel proceso D por el X fue más costoso en tiempo
que no reemplazarlo.
•Esta estrategia es útil en sistemas operativos “time sharing”.
8 9 10 11 12 13
D X D otro proceso
X D
58
Variaciones al
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 59/63
Variaciones alesquema de RR
RR con prioridades estáticas. Selecciona al (job) proceso con mayor
prioridad, el orden de la fila se establece deacuerdo con la prioridad del job.
RR con prioridad dinámica. La prioridad cambia respecto al tiempo.
59
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 60/63
Bloqueado
Nota: sólo hay un CPU
FCFS
RR CPU
CPU
CPU
Expropiación
Expropiación
PROCESOTERMINADO
MLFQ (Multilevel Feedback Queue)-Expropiativo
Procesosbloqueados
por I / O
RR
60
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 61/63
La diferencia entre las filas radica en: Los procesos en filas superiores tienen más
prioridad.
Los procesos en filas inferiores tienenquantum más grande.
61
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 62/63
1.e
Si un proceso de la fila 2 se estáejecutando, y en ese momento llegaotro a una fila superior, el procesode la fila 2 es reemplazado. (Ocurre
la Expropiación) En esta política se le da un trato
preferencial a los procesos I/O bound. Los procesos CPU bound son
penalizados (reciben menosprioridad).
62
7/18/2019 SO s08 Ejercicios de Scheduling de Procesos
http://slidepdf.com/reader/full/so-s08-ejercicios-de-scheduling-de-procesos 63/63
Varios materiales
presentados en la sesión,fueron tomados en partede autores como:
Abraham Silberschatz &
Peter Baer Galvin, William Stallings,
Dr. David Garzae Ing. Jorge Garza.
Recommended