Download E - dia/UPM

E. U. de Informática
Departamento de Informática Aplicada
Examen Final de Sistemas Operativos I
17 de junio de 2005
EJERCICIO 2 (3,5 puntos)
Tiempo estimado: 60 min.
En un ordenador monoprocesador se tiene un sistema operativo multiproceso con las siguientes
estructuras de datos (entre otras):
#define maxProcesos 50
typedef int idProceso ;
typedef struct {
idProceso pid ;
int
estado ;
int
prioridad ;
.....
} descriptorProceso ;
/* Identificador de proceso */
/* Estado del proceso */
/* prioridad del proceso */
descriptorProceso procesos[maxProcesos] ; /* Tabla de Procesos */
idProceso enEjecucion ;
/* Proceso en ejecución */
colaProcesos preparados ;
Como se observa hay un campo prioridad en el descriptor de proceso, que determina la prioridad
del proceso. Dicho campo se utiliza en la planificación de la CPU, que se realiza mediante el
algoritmo de planificación por prioridades expulsor aplicando Round-Robin con rodajas de 20
milisegundos entre los procesos de la misma prioridad. Dicho planificador selecciona como
siguiente proceso a ejecutar, el primero de la cola de preparados que tenga la mayor prioridad
(mayor valor del campo prioridad) de todos los procesos de la cola de preparados,
concediéndole una rodaja de CPU de 20 milisegundos. Al terminar la rodaja (si el proceso no se
bloquea antes) o al prepararse un proceso más prioritario, el proceso en ejecución se pone al final de
la cola de preparados, para a continuación invocarse de nuevo al planificador.
1) [2 puntos] Realizar el seguimiento (en el sistema operativo anterior) de la ejecución de los
procesos, A, B, C, D y E, que se describen en la siguiente tabla, donde se indica su instante t de
llegada al sistema, su prioridad inicial y el código que ejecutan. Todos los tiempos se expresan
en milisegundos.
Proceso: A
t=0
prioridad = 3
CPU(9,9)
Bajar(Sem_1)
CPU(19,9)
Subir(Sem_1)
CPU(19,9)
Bajar(Sem_1)
CPU(9,9)
Terminar
Proceso: B
Proceso: C
Proceso: D
Proceso: E
t=0
t=0
t = 70
t = 95
prioridad = 3
prioridad = 7
prioridad = 5
prioridad = 1
(Inicialmente el semáforo Sem_1 vale 1 y el semáforo Sem_2 vale 0)
CPU(9,9)
Bajar(Sem_1)
CPU(20)
E/S(40)
CPU(9,9)
Terminar
CPU(10)
E/S(100)
CPU(9,9)
Subir(Sem_2)
CPU(9,9)
PonerPrioridad(3)
CPU(9,9)
Terminar
CPU(10)
E/S(50)
CPU(9,9)
Terminar
CPU(9,8)
PonerPrioridad(5)
Bajar(Sem_2)
CPU(29,8)
Subir(Sem_1)
Terminar
Inicialmente (t = 0) los procesos A, B y C llegan a la cola de preparados en ese orden, es decir:
C
7
B
3
A
3
IMPORTANTE: Tener en cuenta las aclaraciones a la vuelta de la hoja.
ACLARACIONES para realizar el seguimiento:
Los procesos utilizan la CPU o realizan E/S durante el tiempo indicado entre paréntesis.
También realizan a veces llamadas al sistema (Bajar, Subir, Terminar y PonerPrioridad) en los
lugares que se indica. Bajar y Subir corresponden a las primitivas de manejo de los semáforos
(es decir las análogas a wait y post), Terminar corresponde a la llamada al sistema para terminar
un proceso, y PonerPrioridad corresponde a una llamada al sistema que permite que el proceso
que la ejecuta cambie su prioridad estableciéndola al valor indicado como parámetro.
El tiempo de ejecución propio de todas esas llamadas al sistema es de 0,1 milisegundos.
Para evitar cualquier ambigüedad se supone que por defecto las llamadas al sistema (y las
interrupciones que no son del reloj) no provocan un cambio del proceso en ejecución. No
obstante, las llamadas al sistema (y las interrupciones) SÍ que provocan un cambio del proceso
en ejecución cuando bloquean al proceso en ejecución o cuando por algún motivo el proceso en
ejecución resulta ser menos prioritario que algún proceso de la cola de procesos preparados.
2) [0,75 puntos] Calcular para cada uno de los procesos A, B, C, D y E del apartado 1 el tiempo
medio que tiene que esperar en la cola de preparados hasta que el planificador le asigna la CPU.
3) [0,75 puntos] Explicar cómo puede utilizarse la llamada al sistema PonerPrioridad anterior
para implementar la exclusión mutua en este sistema operativo entre procesos de prioridad
menor o igual que (por ejemplo) 5. Detallar cómo se implementaría el protocolo de entrada en la
región crítica (Entrar_RC5) y el protocolo de salida de la región crítica (Salir_RC5) para un
proceso de prioridad 5. ¿Hasta qué punto es satisfactoria esta solución en comparación con los
métodos de inhibición de interrupciones y los semáforos?
E. U. de Informática
Departamento de Informática Aplicada
Examen Final de Sistemas Operativos I
17 de junio de 2005
Apellidos ...................................................................................................................
Nombre ......................................................................................................................
Nº de matrícula ..........................................................................................................
EJERCICIO 2
Nº Orden
HOJA DE RESPUESTAS
1) Seguimiento de la ejecución de los procesos, A, B, C, D y E:
En ejecución
Preparado
En espera/Bloqueado
E
D
C
B
A
10
Llegan
A, B y C
20
40
80
60
llega D
90
100
120
140
160
180
200
llega E
2) Calcular para cada uno de los procesos A, B, C, D y E del apartado 1 el tiempo medio que tiene
que esperar en la cola de preparados hasta que el planificador le asigna la CPU (TMEP).
TMEP(A) =
TMEP(B) =
TMEP(C) =
TMEP(D) =
TMEP(E) =
3) Explicar cómo puede utilizarse la llamada al sistema PonerPrioridad anterior para implementar
la exclusión mutua en este sistema operativo entre procesos de prioridad menor o igual que (por
ejemplo) 5. Detallar cómo se implementaría el protocolo de entrada en la región crítica
(Entrar_RC5) y el protocolo de salida de la región crítica (Salir_RC5) para un proceso de
prioridad 5.
¿Hasta qué punto es satisfactoria esta solución en comparación con los métodos de inhibición de
interrupciones y los semáforos?