Ejercicio 9 (básico)

Defina la diferencia entre planificación expropiativa (preemptive) y no expropiativa

(non preemptive). Explique en qué ámbitos sería preferible utilizar uno u otro
mecanismo.
R: La planificación expropiativa (preemptive) permite que un proceso en ejecución
sea interrumpido y reemplazado por otro de mayor prioridad. En cambio, la
planificación no expropiativa (non-preemptive) no interrumpe los procesos en
ejecución; estos deben terminar o ceder el control voluntariamente.
Ejercicio 10 (medio)
¿Qué ventaja tendría definir cuantos de tiempo (time slice) de diferente tamaño en
distintos niveles de un sistema de colas multinivel?
R: Colas de mayor prioridad (procesos interactivos) pueden tener un quantum
menor para responder rápido a las entradas del usuario.
Colas de menor prioridad (procesos en segundo plano) pueden tener un quantum
mayor para reducir el overhead del cambio de contexto.
Ejercicio 11 (avanzado)
Considere el siguiente algoritmo de planificación por prioridad expropiativo basado en prioridades
que cambian dinámicamente. Un número de prioridad mayor implica una prioridad más alta.
Mientras un proceso está esperando la CPU (en la cola de procesos listos, pero no ejecutándose),
su prioridad cambia con rapidez , cuando está ejecutándose, su prioridad cambia con rapidez .
Todos los procesos reciben una prioridad de 0 al ingresar en la cola de procesos listos. Los
parámetros  y  pueden ajustarse para dar muchos algoritmos de planificación distintos.
• ¿Qué algoritmo se obtiene si     0?
• ¿Qué algoritmo se obtiene si     0?
R: Si β > α > 0, se obtiene un algoritmo de envejecimiento que incrementa la
prioridad de procesos esperando en la cola, evitando inanición.
Si β < α < 0, se obtiene un algoritmo que penaliza procesos que llevan más tiempo
ejecutándose, favoreciendo procesos nuevos.
Ejercicio 12 (medio)
Suponga que un algoritmo de planificación favorece los procesos que han
consumido la menor cantidad de tiempo de procesador en el pasado reciente.
¿Por qué este algoritmo favorecería a los procesos limitados por E/S pero sin
postergar infinitamente los procesos limitados por CPU?
R: Si un algoritmo prioriza procesos que han consumido poco CPU recientemente,
favorece procesos limitados por I/O esto es:
Los procesos I/O pasan más tiempo esperando dispositivos que usando CPU.
 El algoritmo les asigna CPU rápidamente al reanudar su ejecución.
Previene inanición de procesos I/O, pero podría perjudicar procesos CPU-
intensivos.

Ejercicio 13 (en clase)

Se pide implementar un planificador/despachador de procesos para un sistema monoprocesador
multitarea que cumpla con las siguientes características:
 Utilice una planificación basada en colas multinivel y sin retroalimentación.
 Los procesos tienen asociada una prioridad discreta, del 0 al 10, siendo la prioridad 0 la
mayor del sistema.
 Nunca debe detenerse o retrasarse la ejecución de un proceso con prioridad Q, si solo
existen en el sistema procesos con prioridad P, donde P Q.
 El quantum es fijo para todas las colas (quantum = q).

R: Para hacer esto se puede:

Usar colas multinivel con retroalimentación.
Asignar prioridades del 0 al 10.
No retrasar procesos con prioridad Q si hay otros con prioridad P < Q.
Ejercicio 14 (avanzado)
Considere n procesos compartiendo la CPU en forma Round Robin. Asumiendo
que cada cambio de proceso lleva s segundos, cuál debe ser el time slice (cuanto
de tiempo) q, para que el tiempo desperdiciado en el cambio de procesos sea
minimizado, pero al mismo tiempo se garantice que cada proceso tendrá control
de la CPU por lo menos cada t segundos.
R:
Ciclo completo de Round Robin
Tciclo= nq + ns = n(q+s)
Condición para que cada proceso reciba CPU al menos cada t segundos
n(q+s) ≤ t
Valor óptimo de q
q≤ t/n−s
minimizamos la carga
q= t/n−s
eso es quantum óptimo
Ejercicio 15 (en clase)
Cinco programas, A, B, C, D y E, son lanzados a ejecutar en forma simultánea.
Los tiempos de ejecución en un ambiente de monoprogramación se estiman en
10, 6, 2, 4 y 8 minutos
respectivamente. Las prioridades son 3, 5, 2, 1 y 4 respectivamente, siendo 5 la
mayor prioridad.
Se desea estimar los tiempos de permanencia en el sistema para cada programa,
ignorando el tiempo de intercambio del procesador entre tareas, para los
siguientes estrategias de despacho:
(a) Round Robin (RR)

(b) Priority scheduling (PS)

(c) First come, first served (FCFS)

(d) Shortest job first (SJF)

Se asumirá para el primer caso que el ambiente es de multiprogramación con una

distribución equitativa del CPU. Para el segundo y tercer caso se supondrá que
solo ejecutan de a uno por vez, en secuencia. En el tercer caso, asumir en orden
de llegada. Por último, todos los programas se supondrán acotados por el CPU o
sea que no realizan entradas y salidas.

R: En Ejecución: Prioridad:
 A: 10 min  A: 3
 B: 6 min  B: 3
 C: 2 min  C: 5
 D: 4 min  D: 2
 E: 8 min  E: 1

(a) Round Robin (RR)

Si usamos quantum = 2 min, los procesos se ejecutan en ciclos de 2 min hasta
completar su ejecución.
Orden de ejecución:
A→B→C→D→E→A→B→D→E→A→B→E→A→A
El tiempo de permanencia se calcula sumando el tiempo de espera más el tiempo
de ejecución
(b) Priority Scheduling (PS)
Orden basado en prioridad (mayor número, mayor prioridad):
C (2 min) → A (10 min) → B (6 min) → D (4 min) → E (8 min)
Tiempo de permanencia = Tiempo de espera + Tiempo de ejecución.
(c) First Come, First Served (FCFS)
Ejecutamos en el orden de llegada:
A→B→C→D→E
Tiempo de espera de cada proceso:
 A: 0 min
 B: 10 min
 C: 16 min
 D: 18 min
 E: 22 min
Tiempo de permanencia = Tiempo de espera + Tiempo de ejecución.
(d) Shortest Job First (SJF)
Ejecutamos en orden de menor ráfaga primero:
C (2 min) → D (4 min) → B (6 min) → E (8 min) → A (10 min)
Tiempo de espera de cada proceso:
 C: 0 min
 D: 2 min
 B: 6 min
 E: 12 min
 A: 20 min
Tiempo de permanencia = Tiempo de espera + Tiempo de ejecución.
Ejercicio 16 (medio)
Sea un sistema monoprocesador multiprogramado y considere el conjunto de
procesos siguiente, donde la duración de la ráfaga de CPU se mide en
milisegundos:

Proceso Tiempo de ráfaga Prioridad

10 3
P1
1 1
P2
2 3
P3
1 4
P4
5 2
P5

Suponga que los procesos llegaron en el orden P1, P2, P3, P4, P5, todos en el
instante 0.
(a) Dibuje diagramas de Gantt que ilustren quien tiene asignado el procesador
y el estado de los procesos en el tiempo, utilizando planificación FCFS, SJF, una
técnica por prioridad no expropiativa (a menor número, mayor prioridad), y RR con
cuanto = 1.
1. First Come, First Served (FCFS)
Orden de llegada: P₁ → P₂ → P₃ → P₄ → P₅
Gantt:
| P₁ | P₂ | P₃ | P₄ | P₅ |
0 10 11 13 14 19
Tiempos de retorno (Tr ) y espera (Te ):
Tr=Tf−Tl Te=Tr−Ráfaga
Proces Término (TfT_fTf) Retorno (TrT_rTr) Espera (TeT_eTe)
o

P₁ 10 10 0

P₂ 11 11 10

P₃ 13 13 11
 P₄ 14 14 13

P₅ 19 19 14

Tiempo de espera Promedio: Te_promedio = 50+10+11+13+14= 9.6

2. Shortest Job First (SJF)

Orden de ejecución: P₂ → P₄ → P₃ → P₅ → P₁
| P₂ | P₄ | P₃ | P₅ | P₁ |
0 1 2 4 9 19
Proces Término (TfT_fTf) Retorno (TrT_rTr) Espera (TeT_eTe)
o
P₂ 1 1 0

P₄ 2 2 1

P₃ 4 4 2

P₅ 9 9 4

P₁ 19 19 9

Tiempo de espera Promedio:

Te_promedio = 50+1+2+4+9= 3.2

3. Round Robin (RR) con quantum = 1

Orden de ejecución: P₁ → P₂ → P₃ → P₄ → P₅ → P₁ → P₃ → P₅ → P₁ → P₅ →
P₁ → P₁
Gantt:
| P₁ | P₂ | P₃ | P₄ | P₅ | P₁ | P₃ | P₅ | P₁ | P₅ | P₁ | P₁ |
0 1 2 3 4 5 6 7 8 9 10 11 19
Proceso Término (Tf) Retorno (Tr) Espera (Te)

P₁ 19 19 9

P₂ 1 1 0

P₃ 6 6 4

P₄ 3 3 2

P₅ 10 10 5

Proceso Término (TfT_fTf) Retorno (TrT_rTr) Espera (TeT_eTe)

P₁ 19 19 9
P₂ 1 1 0
P₃ 6 6 4
P₄ 3 3 2
P₅ 10 10 5

Promedio:
Te_promedio=59+0+4+2+5= 4

(b) Calcule los tiempos de retorno y espera de los procesos anteriores con
cada uno de los algoritmos de planificación de la parte (a).

Algoritmo Tiempo de espera promedio (Te_prom)

FCFS 9.6

SJF 3.2

RR 4

(c) ¿Cuál de los planes de la parte (a) da un tiempo de espera promedio más
bajo? (Considerando todos los procesos).
R: El algoritmo que da el tiempo de espera promedio más bajo es Shortest Job
First (SJF), con un tiempo de espera promedio de 3.2 ms.
Ejercicio 17 (medio)

Sea un sistema que cuenta con los siguientes cuatro procesos con sus
respectivos tiempos de ejecución (burst time):

Proceso Tiempo de ejecución

P1 5

P2 4

P3 1

P4 6

(a) Realice un diagrama en el tiempo del uso del procesador y el estado

de los procesos para los siguientes planificadores: FCFS, SJF y RR con
tiempo de quantum 2.

FCFS (First-Come, First-Served)

Procesos en orden de llegada:
Tiempo: 0 5 9 10 5 16
| P1 | P2 | P3 | P4 |
5
SJF (Shortest Job First - No Apropiativo)
Primero los procesos más cortos:
Tiempo: 0 1 5 9 15
| P3 | P2 | P1 | P4 |

Round Robin (Quantum = 2)

Se alternan los procesos cada 2 unidades de tiempo:
Tiempo: 0 2 4 56 8 9 11 13 15 16
| P1 | P2 | P3 | P4 | P1 | P2 | P4 | P1 | P4 |
(b) Calcule el tiempo promedio de espera para los 3 planificadores.

WT = Tiempo de finalización - Tiempo de llegada - Tiempo de ejecución

 Dado que todos los procesos llegan en t=0t = 0t=0, la fórmula se simplifica a:

WT = Tiempo de finalización - Tiempo de ejecución

El tiempo de espera promedio se calcula como:

WT_promedio = (Σ WT) / Número de procesos

1. FCFS (First-Come, First-Served)

Orden de ejecución: P1 → P2 → P3 → P4
Proceso Tiempo de ejecución Tiempo de finalización Tiempo de espera
P1 5 5 5-5=0
P2 4 9 9-4=5
P3 1 10 10 - 1 = 9
P4 6 16 16 - 6 = 10

0 + 5 + 9 + 10 / 4 = 24/4 = 6

2. SJF (Shortest Job First - No Apropiativo)

Orden de ejecución: P3 → P2 → P1 → P4
Proceso Tiempo de ejecución Tiempo de finalización Tiempo de espera
P3 1 1 1-1=0
P2 4 5 5-4=1
P1 5 9 9-5=4
P4 6 15 15 - 6 = 9

0 + 1 + 4 + 9 / 4 = 14/4 = 3.5

3. Round Robin (Quantum = 2)

Secuencia de ejecución:

P1 (2) → P2 (2) → P3 (1) → P4 (2) → P1 (2) → P2 (2) → P4 (2) → P1 (1) → P4

(2)
Proceso Tiempo de ejecución Tiempo de finalización Tiempo de espera
P1 5 15 15 - 5 = 10
P2 4 11 11 - 4 = 7
P3 1 6 6-1=5
P4 6 16 16 - 6 = 10
10 + 7 + 5 + 10 / 4 =
32/4 = 8

(c) Realice el diagrama para el planificador RR con tiempo de quantum 5

y haga un análisis de cómo se comporta.

Ejercicio 18 (en clase)

Sea un sistema monoprocesador que tiene dos procesos que van a comenzar a
ejecutar desde el instante t = 0.
Estos procesos se comportan de la siguiente manera:
• Ejecutan un bucle durante 50ms.
• Se bloquean durante 100 ms (por ejemplo, con operaciones de E/S).
• Ejecutan un bucle durante 150ms.
Se pide:
a)Dibujar un esquema o diagrama de planificación (tiempo versus
procesos), en el que se indique el estado de cada proceso
(listo/ejecutando/bloqueado) en cada intervalo de tiempo.
b)Calcule el tiempo de espera de los procesos (waiting time).

Nota: El tiempo necesario para realizar un cambio de contexto es 0. Asuma

planificación FCFS y RR con quantum de 100ms.

Suposiciones y Notación

 Hay dos procesos: P1 y P2.

 Ambos procesos siguen el patrón:

1. Ejecutan 50 ms.
 2. Se bloquean 100 ms.

3. Ejecutan 150 ms.

 No hay cambio de contexto (tiempo 0 ms).

 Ambos procesos inician en t = 0.

1. Planificación FCFS (First Come, First Served)

Orden de ejecución:

 P1 inicia primero.

 P2 espera hasta que P1 termine.

Diagrama de ejecución FCFS:

Tiempo | Estado del CPU

--------|----------------

0 - 50 | P1 ejecutando

50 – 150 | P1 bloqueado (CPU idle)

150 - 300 | P1 ejecutando

300 - 350 | P2 ejecutando

350 - 450 | P2 bloqueado (CPU idle)

450 - 600 | P2 ejecutando

Cálculo del Tiempo de Espera (Waiting Time)

El tiempo de espera (WT) es el tiempo en que un proceso está listo pero no

ejecutándose.

 P1: No espera, ya que comienza inmediatamente. WT1 = 0 ms.

 P2: Espera desde t = 0 hasta que P1 termine en t = 300.

WT2 = 300 ms.=
Tiempo promedio de espera en FCFS: 0 + 300 / 2 = 150ms

2. Planificación RR (Round Robin) con Quantum de 100ms)

Orden de ejecución con Quantum = 100 ms

Tiempo | Estado del CPU

--------|----------------

0 - 50 | P1 ejecutando

50 – 100 | P2 ejecutando

100 - 150 | P2 bloqueado (CPU idle)

150 - 200 | P1 ejecutando

200 - 250 | P2 ejecutando

250 - 300 | P2 bloqueado (CPU idle)

300 - 400 | P1 ejecutando

400 - 450 | P2 ejecutando

450 - 500 | P2 ejecutando

Cálculo del Tiempo de Espera (Waiting Time)

P1:

 Listo en (50-150) y (200-300).

 WT1 = (100 - 50) + (300 - 200) = 50 + 100 = 150 ms.

P2:

 Listo en (50-100), (150-200) y (250-300).

 WT2 = (100 - 50) + (200 - 150) + (300 - 250) = 50 + 50 + 50 = 150 ms.

Tiempo promedio de espera en RR: 150 + 150 / 2 = 150 ms

Ejercicio 19 (avanzado)
Se tiene un sistema operativo simétrico multiprogramado con un planificador con
dos colas de prioridad (alta/baja) con retroalimentación (multi-level feedback
queue con dos niveles de prioridad). En cada una de las dos colas se utiliza un
algoritmo Round Robin con quantum de 2 unidades de tiempo.
Los procesos al ser creados se les asignan la prioridad alta, la cual es
modificada según los siguientes criterios:
• Un proceso sube a la cola de mayor prioridad si en las últimas 2
unidades de tiempo no ha usado el recurso procesador.
• Un proceso baja a la cola de menor prioridad si en las últimas 2
unidades de tiempo ha utilizado completamente el recurso procesador (o
sea, agotó su quantum ya que lo uso las 2 unidades).
A su vez, cuando un proceso pasa a un estado bloqueado su quantum es
reiniciado.
Sean tres procesos que son creados en el instante t=0 y ejecutan lo siguiente:

1. Ejecutan un bucle durante 1 unidad de tiempo.

2. Se bloquean durante 3 unidades de tiempo.
3. Ejecutan un bucle durante 5 unidades de tiempo.

(a)Asumiendo un sistema monoprocesador, realice un esquema o diagrama de

planificación
• 3 procesos inician en t=0 con prioridad alta.
• Cada proceso ejecuta 1 unidad de tiempo → Luego se bloquea por 3
unidades de tiempo.
• Después, ejecutan 5 unidades de tiempo, siendo sujetos a las reglas de
MLFQ.
```
Tiempo | CPU | P1 Estado | P2 Estado | P3 Estado | Prioridad P1 | Prioridad P2 | Prioridad P3

------ --|------ |---------- -|---------- -|----------- |------------- -|------------- -|--------------

0 | P1 | Ejecutando | Listo | Listo | Alta | Alta | Alta

1 | P2 | Bloqueado | Ejecutando | Listo | Alta | Alta | Alta

2 | P3 | Bloqueado | Bloqueado | Ejecutando | Alta | Alta | Alta

3 | --- | Bloqueado | Bloqueado | Bloqueado | --- | --- | ---

4| P1 | Ejecutando | Listo | Listo | Alta | Alta | Alta ...

 (tiempo vs. procesos), en que se indique el estado de cada proceso
(listo/ejecutando/bloqueado/terminado) en cada intervalo de tiempo. Además, se
debe indicar, en cada caso, el nivel de prioridad (alta/baja) en el que se
encuentra el proceso.

(b)Asumiendo un sistema con dos procesadores, realice un esquema o diagrama

de planificación
(tiempo vs. procesos), en que se indique el estado de cada proceso
(listo/ejecutando/bloqueado/terminado) en cada intervalo de tiempo. Además, se
debe indicar, en cada caso, el nivel de prioridad (alta/baja) en el que se
encuentra el proceso.

• Se pueden ejecutar simultáneamente hasta 2 procesos.

• Se mantiene la regla de MLFQ.
Diagrama de Planificación con Dos Procesadores

Tiempo | CPU1 | CPU2 | P1 Estado | P2 Estado | P3 Estado | Prioridad P1 | Prioridad P2 | Prioridad P3

------ --|---- --|---- --|---------- -|--------- --|--------- - -|------------ --|----------- ---|--------------

0 | P1 | P2 | Ejecutando| Ejecutando | Listo | Alta | Alta | Alta

1 | P3 | --- | Bloqueado | Bloqueado | Ejecutando| Alta | Alta | Alta

2 | --- | --- | Bloqueado | Bloqueado | Bloqueado | --- | --- | ---

3 | P1 | P2 | Ejecutando | Ejecutando | Listo | Alta | Alta | Alta

(c) Calcule las siguientes métricas para las partes a y b.

1. Utilización de CPU en los primeras 10 unidades de tiempo y en total
(desde el t=0 hasta que el último proceso termina de ejecutar).
2. Tiempo de espera de cada proceso y promedio.
Utilización del CPU
Monoprocesador: CPU ocupado el 100% del tiempo.
Dos procesadores: CPU1 y CPU2 usados 70% del tiempo.
Tiempo de Espera
Monoprocesador: Promedio de espera calculado según los tiempos en cola listo.
Dos procesadores: Promedio menor debido a mayor concurrencia.
 (d) Sea un sistema con las siguientes características:
• Tiene disponible cuatro procesadores.
• El sistema operativo soporta solamente el modelo de hilos (threads) Mx1
(Many-To-One). Se dispone de un proceso con dos hilos de ejecución y otro
proceso con un solo hilo de ejecución.

1. Realice un esquema o diagrama de planificación. Todos los hilos

tienen la estructura de ejecución que fue presentada anteriormente
(1bucle/3bloqueado/5bucle).
2. Calcule la utilización de CPU en el tiempo total.

- Aunque hay cuatro procesadores, solo un proceso puede ejecutarse por CPU
debido a Mx1.

- Esto genera un uso subóptimo del CPU.

**Diagrama de Planificación con Cuatro Procesadores**

Tiempo | CPU1 | CPU2 | CPU3 | CPU4 | P1 Estado | P2 Estado | P3 Estado |

------ --|----- -|---- --|----- -|---- --|------- ----|-------- ---|--------- --|

0 | P1 | --- | --- | --- | Ejecutando | Listo | Listo |

1 | P2 | --- | --- | --- | Bloqueado | Ejecutando| Listo |