Facultad de Ciencias

Departamento de Computación

SISTEMAS OPERATIVOS
PROBLEMAS RESUELTOS

Prof. Raúl Monge A. Mayo 2007

Pregunta Nº1
Un sistema computacional que incorpora DMA permite una realización eficiente de la
multiprogramación. Si un proceso en promedio usa sólo el 23% de su tiempo la CPU y el
resto está en entrada y salida (E/S) y suponiendo que toda operación de E/S se realiza por
DMA. ¿Estime qué utilización del procesador y del canal de DMA se logra, si se tiene un
grado de multiprogramación de 6 procesos?

Se tiene:

Ucpu (1) = 0,23

Ue/s(1) = 0,77

Se demuestra que:

Ucpu(n) = 1 – Ue/s(1)6

Udma(n) = 1 – Ucpu (1)6

Luego:

Ucpu(6) = 1 – 0,776 = 0,792

Udma(6) = 1 – 0,236 = 1,000

Problema Nº2
Suponga que se tiene el siguiente conjunto de procesos:

Proceso Tiempo de Llegada Tiempo de Proceso

1 0 3

2 1 5

3 3 2

4 9 5

5 12 5
 Facultad de Ciencias
Departamento de Computación

Analice cuál es el tiempo de tránsito para cada proceso y calcule el tiempo de tránsito promedio para todos los
procesos en los siguientes casos:
a) FCFS (First Come First Serve)
b) Round-Robin con quantum de tiempo q = 1
c) SRTF (Shortest Remaining Time First), con expropiación

RESPUESTA:

a) FCFS (First Come First Serve)

El tiempo de tránsito en FCFS está dado por la duración del proceso y del momento en el que comienza a
ejecutarse, por lo cual se puede resumir los resultados de una ejecución FCFS para el presente caso en la
siguiente tabla:

Proceso Duración Llegada Inicio Salida T. Tránsito

Proceso 1 3 0 0 2 3
Proceso 2 5 1 3 7 7
Proceso 3 2 3 8 9 7
Proceso 4 5 9 10 14 6
Proceso 5 5 12 15 19 8
Promedio 31/5 = 6,2

En donde Llegada marca el tiempo de llegada del proceso a la cola, y Salida marca la última unidad de
tiempo en el cual el proceso hace abandono del planificador. El tiempo de Tránsito se obtiene por la
siguiente expresión:
T. Tránsito = (T. Salida - T. Llegada) + 1

b) Round-Robin con quantum de tiempo q = 1

Para el desarrollo de este problema se considera una mayor prioridad en el ingreso a la cola listo de los
procesos que vienen llegando, por sobre aquellos procesos que vienen terminando su cuanto de tiempo. A
continuación se presenta una tabla con el comportamiento de los procesos ante esta política de
ordenamiento:

Tiempo Cola procesos Procesador Observaciones

0 P1 Llega Proceso 1
1 P1 P2 Llega Proceso 2
2 P2 P1
3 P1 P3 P2 Llega Proceso 3
4 P2 P1 P3
5 P3 P2 P1 Sale Proceso 1
6 P3 P2 P2
7 P2 P3 Sale Proceso 3
8 P2
9 P2 P4 Llega Proceso 4
10 P4 P2 Sale Proceso 2
11 P4
12 P4 P5 Llega Proceso 5
13 P5 P4
14 P4 P5
15 P5 P4
16 P4 P5
17 P5 P4 Sale Proceso 4
18 P5
19 P5 Sale Proceso 5
 Facultad de Ciencias
Departamento de Computación

Con los resultados de la tabla anterior se puede generar la siguiente tabla que contiene la
información solicitada:

Proceso T. Llegada T. Salida T. Tránsito

Proceso 1 0 5 6
Proceso 2 1 10 10
Proceso 3 3 7 5
Proceso 4 9 17 9
Proceso 5 12 19 8
Promedio 38/5 = 7,6

c) SRTF (Shortest Remaining Time First ), con expropiación

En SRTF el proceso con un tiempo restante de duración inferior es el primero, para poder desarrollar este
esquema, se presenta la siguiente tabla que resume el comportamiento de estos procesos ante esta política:

Tiempo Cola de Procesos Procesador Observaciones

0 P1 Llega Proceso 1
1 P2 P1 Llega Proceso 2
2 P2 P1 Sale Proceso 1
3 P2 P3 Llega Proceso 3
4 P2 P3 Sale Proceso 3
5 P2
6 P2
7 P2
8 P2
9 P4 P2 Sale Proceso 1, Llega Proceso 4
10 P4
11 P4
12 P5 P4 Llega Proceso 5
13 P4
14 P4 Sale Proceso 4
15 P5
16 P5
17 P5
18 P5
19 P5 Sale Proceso 5

De la tabla anterior ya se puede obtener la información necesaria para generar la siguiente tabla resumen con los
tiempos de tránsito para cada proceso así como el tiempo de tránsito promedio:

Proceso T. Llegada T. Salida T. Tránsito

Proceso 1 0 2 3
Proceso 2 1 9 9
Proceso 3 3 4 2
Proceso 4 9 14 6
Proceso 5 12 19 8
Promedio 28/5 = 5,6
 Facultad de Ciencias
Departamento de Computación

Pregunta N°3
Suponga que se tiene un monitor que permite sincronizar dos procesos de la siguiente manera.
• El primer proceso va incrementando periódicamente una variable protegida en una cierta cantidad
positiva constante igual a ∆t.
• El segundo proceso llama al monitor en algún instante con un parámetro T, instante en que se
iguala a 0 la variable protegida. Este proceso permanece bloqueado hasta que la variable supere el
valor de T, después de una o más llamadas del primer proceso.

Especifique e implemente el monitor. El mecanismo anterior representa un timer que permite

bloquear al segundo proceso en una cantidad T de tiempo y el primer proceso lleva el ritmo del paso
del tiempo.

// INTERFAZ
const int delta = ??; // definir valor entre llamados

monitor Timer {
int Time;
public:
void tic(); /* se llama cada vez que transcurre delta */
void sleep(int T); /* permite bloquearse por un tiempo T */
Timer(); /* el constructor */
}

// Implementando el monitor:

monitor Timer {
int Time;
condition sync;
int timeout;
boolean activo;
public:
void tic() {
if (activo) {
Time += delta;
if (time >= timeout) {
sync.signal;
activo = FALSE;
}
}
}

void sleep(int T) {
Time = 0;
Timeout = T;
activo = TRUE;
Sync.wait;
}

Timer() {
Time = 0;
Activo = FALSE;
}
}
 Facultad de Ciencias
Departamento de Computación

Problema N°4
Se tiene un grupo de procesos “trabajadores” capaces de procesar órdenes de trabajo provenientes de
diferentes clientes. En general, un trabajador trabaja en un ciclo de espera por una orden de trabajo
(ocioso), recibirla desde un cliente (sincronizarse) y procesarla (ocupado). Un cliente sólo debe
esperar en la entrega de una orden cuando no existen trabajadores ociosos. Un trabajador permanece
ocioso si no existen más órdenes que procesar.

Escriba en C (pseudo-código) un monitor capaz de coordinar la entrega de una orden de trabajo entre
un cliente y un trabajador, distribuyendo las órdenes en los trabajadores ociosos en orden FIFO.

a) Especifique la interfaz del monitor y en pseudo-código el comportamiento de un cliente y un

trabajador. Documente adecuadamente para entender su significado.

/****************************************************
La siguiente interfaz posee dos operaciones
1) procesarOrden: utilizada por clientes para
enviar una orden de trabajo
2) solicitarOrden: utilizada por trabajadores
para esperar la asignación de una nueva
orden de trabajo (modo ocioso)

**************************************************/
monitor CoordinadorTareas {
void procesarOrden (Trabajo t); // clientes
Trabajo solicitarOrden (); // trabajadores
}

/* coordinador: Instancia compartida del

monitor */

shared CoordinadorTareas coordinador;

void Cliente {
Trabajo t;

while (1) {
producir una orden de trabajo t;
coordinador.procesar(t);
}
}

void Trabajador {
Trabajo t;

while (1) {
t = Coordinador.solicitarOrden();
procesar t;
}
}
 Facultad de Ciencias
Departamento de Computación

b) Especifique un programa principal que permita hacer partir “m” trabajadores y “n”
clientes.

main () {
for (int i=0; i<m; i++)
fork Trabajador();
for (int i=0; i<n; i++)
fork Cliente();
}

c) Especifique el monitor, explicando cuáles variables de condición usará para sincronizar

procesos y escribiendo el código de cada procedimiento utilizado.

monitor CoordinadorTareas {
condition nuevoTrabajo; // para que un trabajador se sincronice
condition trabajadorOcioso; // para sincronizar a los clientes
Trabajo trabajos[m]; // para entregar un trabajo a un trabajador
int ocupados; // número de trabajos en espera
int lleno; // próximo trabajo a consumir
int vacio; // próximo espacio libre

void procesarOrden (Trabajo t) {

if (ocupados ==m)
trabajadorOcioso.wait();
trabajos[vacio] = t;
vacio = (vacio++)%m;
ocupados++;
nuevoTrabajo.signal(); // despierta a un posible trabajador
}

Trabajo solicitarOrden () {
Trabajo t;

if (ocupados==0)
nuevoTrabajo.wait();
t = trabajos[lleno];
lleno = (lleno++)%m
ocupados--;
trabajadorOcioso.signal(); // despierta a un cliente si lo hubiera
return t;
}
}

CoordinadorTareas () { // inicialización
ocupados = lleno = vacio = 0;
}