Soluciones al primer parcial, curso 1997/98
1 (2,50 ptos).
Responda a cada una de las siguientes cuestiones. En la respuesta a cada una emplee como máximo 5 líneas (en caso de utilizar más sólo se evaluará lo expuesto en la 5 primeras).
1.1. Diferencie entre llamada al sistema operativo y función del sistema.
Una llamada al sistema operativo es una implica generalmente el cambio de modo usuario de ejecución a modo sistema e implica que actúe el gestor de llamadas al sistema (parte del núcleo del SO). En cambio, la invocación a una función del sistema no tiene por qué implicar un cambio de modo de ejecución y no produce la invocación al gestor de llamadas al sistema.
1.2. Enumere tres acciones que sólo las pueda llevar a cabo el sistema operativo con el objeto de garantizar el buen funcionamiento del sistema informático.
Cambiar de modo de ejecución entre modo usuario y modo sistema y viceversa, operar con los dispositivos de Entrada/Salida y acceder a cualquier posición de la memoria del sistema.
1.3. En la ejecución de operaciones de Entrada/Salida, ¿qué ventajas aporta el uso de interrupciones frente a su no uso?
Permite que el procesador pueda ser asignado a otra tarea mientras la tarea que la tiene asignada realiza una operación de Entrada/Salida. También facilita el control de las operaciones de Entrada/Salida, pues su uso evita el estar continuamente comprobando el estado de la operación mientras esta se realiza (espera activa).
1.4. Explicar la diferencia entre proceso e hilo de ejecución
Un proceso (en el sentido tradicional) equivale a una tarea con un único hilo; en cambio, un hilo es la unidad básica de ejecución (utilización del procesador) que posee poco estado compartido frente al proceso tradicional, de ahí que la conmutación de contexto es más fácil llevarla a cabo con hilos que con procesos.
1.5. Enumere dos diferencias entre la planificación de procesos a bajo nivel y nivel intermedio.
La planificación a bajo nivel tiene por misión gestionar el procesador o procesadores del sistema, en cambio la planificación de nivel intermedio decide que proceso debe ser suspendido para garantizar el buen funcionamiento del sistema. Otra diferencia es la frecuencia de ejecución de dichas tareas de planificación, la de bajo nivel se lleva a cabo más frecuentemente que la de nivel intermedio.
1.6. ¿Cuando la función UNIX semop (operación sobre un vector de semáforos) provoca el bloqueo del proceso invocador?.
Cuando no se ha especificado el flag IPC_NOWAIT en la invocación a semop y el campo operación es 0 y el valor del semáforo es distinto de 0, o bien, el campo operación es un valor negativo cuyo valor absoluto es mayor que el valor del semáforo.
1.7. ¿Cuándo la función UNIX msgsnd (envío de un mensaje a una cola) provoca el bloqueo del proceso que la invoca?.
Cuando no se ha especificado el flag IPC_NOWAIT en la invocación a msgsnd y se han alcanzado los límites de capacidad de la cola (tamaño en bytes y número máximo de mensajes) de mensajes utilizada.
1.8. ¿Cuándo la función UNIX msgrcv (recepción de un mensaje desde una cola) provoca el bloqueo del proceso invocador?
Cuando no se ha especificado el flag IPC_NOWAIT en la invocación a msgrcv y no existe mensaje alguno del tipo especificado en la invocación.
1.9. Explique en qué consiste la condición de progreso que toda solución al problema de la sección crítica debe cumplir.
La condición establece si ningún proceso se está ejecutando en su sección crítica y hay otros procesos que desean entrar en las suyas, entonces sólo aquellos que no se están ejecutando en su sección restante pueden participar en la decisión de cuál será el siguiente en entrar, y esta decisión no puede postergarse indefinidamente.
1.10. ¿Puede el uso de semáforos dar lugar a un problema de inanición? justifique su respuesta.
Dependerá de la política de gestión de la cola de procesos bloqueados que todo semáforo tiene asociada. Por ejemplo, para una política FIFO este problema no se da, en cambio para una política LIFO (ultimo en llegar primero en salir), sí se podría dar este problema.
2 (1,50 ptos).
Considere el siguiente conjunto de procesos, cuyas duraciones de ráfagas de CPU en milisegundos son:
|
Proceso |
Duración de ráfaga |
Tiempo de llegada |
|
P1 |
4 |
0 |
|
P2 |
2 |
1 |
|
P3 |
3 |
2 |
|
P4 |
1 |
2 |
Calcule los tiempos medios de espera y retorno para las políticas:
- SJF apropiativa
- Round-Robin con cuanto de 3 milisegundos
- SJF apropiativo:
Diagrama de Gantt:
|
P1 |
P2 |
P2 |
P4 |
P3 |
P3 |
P3 |
P1 |
P1 |
P1 |
|
Proceso |
Tiempo de retorno |
Tiempo de espera |
|
P1 |
10 |
6 |
|
P2 |
2 |
0 |
|
P3 |
5 |
2 |
|
P4 |
2 |
1 |
|
Tiempo medio |
4,75 |
2,25 |
o también:
|
P1 |
P2 |
P2 |
P4 |
P1 |
P1 |
P1 |
P3 |
P3 |
P3 |
|
Proceso |
Tiempo de retorno |
Tiempo de espera |
|
P1 |
7 |
3 |
|
P2 |
2 |
0 |
|
P3 |
8 |
5 |
|
P4 |
2 |
1 |
|
Tiempo medio |
4,75 |
2,25 |
- Round-Robin (cuanto 3 milisegundos):
Diagrama de Gant:
|
P1 |
P1 |
P1 |
P2 |
P2 |
P3 |
P3 |
P3 |
P4 |
P1 |
|
Proceso |
Tiempo de retorno |
Tiempo de espera |
|
P1 |
10 |
6 |
|
P2 |
4 |
2 |
|
P3 |
6 |
3 |
|
P4 |
7 |
6 |
|
Tiempo medio |
6,75 |
4,25 |
3 (1,50 ptos).
Suponga un disco de 200 cilindros, numerados de 0 a 199, la cabeza se encuentra atendiendo una petición en el cilindro 52. La cola de solicitudes posee las peticiones (expresadas en número de cilindro):97, 182, 37, 121, 13, 124, 64, 67. ¿Cómo se atenderían las solicitudes anteriores al aplicar las políticas:a) SSTF
b) LOOK
Nota: Cuando requiera asumir un sentido del recorrido de la cabeza en el que se atienden peticiones, asuma el sentido ascendente.
a) SSTF
64, 67, 37, 13, 97, 121, 124, 182
o bien
64, 67, 97, 121, 124, 182, 37, 13
b) LOOK
64, 67, 17, 121,124, 182, 37, 13
4 (2,25 ptos).
Utilizando sólo monitores dar una solución al problema de los filósofos comensales en la que no se puedan producir situaciones de interbloqueo.
type filosofos_comensales = monitor
var estado: array[0..4] of (pensando, hambriento, comiendo);
var palillo: array[0..4] of condition;
Procedure Entry Tomo_Palillo(i:0..4)
Begin
estado[i] := hambriento;
Test(i);
If (estado[i] != comiendo ) Then palillo[i].wait;
End;
Procedure Entry Libero_Palillo(i:0..4)
Begin
estado[i] := pensando;
Test(i-1 mod 5);
Test(i+1 mod 5);
End;
Procedure Test(k:0..4)
Begin
if ( (estado[(k-1) mod 5] != comiendo) and
(estado[k] = hambriento) and
(estado[(k+1) mod 5] != comiendo) ) Then
Begin
estado[k] = comiendo;
palillo[k].signal;
End;
End;
Begin
for j:=0 to 4 do estado[j] := pensando;
End.
5 (2,25 ptos).
Describa algoritmicamente una función que nos informe si un sistema se encuentra en estado de interbloqueo. la función debe devolver el valor 1 si existe interbloqueo y 0 si no existe. En el sistema donde se debe ejecutar la función existen varias posibilidades de un mismo tipo de recurso y los procesos pueden solicitar varias posibilidades de distintos tipos a la vez.
Constantes
M número de tipos de recursos del sistema
N número de procesos
Estructuras de datos
Disponible: Vector de longitud M que indica las disponibilidades de cada tipo de recurso. Dipsonible(j) = k, entonces existen k posibilidades del tipo de recurso j.
Asignado: Matriz de N filas y M columnas que registra el núemro de posibilidades de cada tipo de recurso que cada proceso tiene asignado. Asignado(p,j) = k, entonces el proceso p tiene asignado k posibilidades del tipo j.
Peticiones: Matriz de N filas y M columnas que registra el núemro de posibilidades de cada tipo de recurso que cada proceso solicita. Peticiones(p,j) = k, entonces el proceso p solicita k posibilidades del tipo de recurso j.
Algoritmo:
Trabajo y acabado son vectores de longitud M y N respectivamente.
Trabajo = Disponible
Para p=1 Hasta N Hacer
Si ( Asignado(p) != 0 ) Entonces
Acabado(p) = falso;
Si no
Acabado(p) = verdadero;
Fin si
Fin Para
Paso 2: Encontrar un proceso "p" tal que:
Acabado(p) = falso y Peticiones(p) <= Trabajo
"Si" (no se encuentra un proceso p) "Entonces" ir Paso 4
Trabajo = Trabajo + Asignado(p);
Ir Paso 2
Paso 4: "Si" (existe algún proceso p tal que Acabado(p) = falso) "Entonces"
El sistema está en estado de interbloqueo
"Si no"
El sistema no esta en interbloqueo
"Fin Si"