Septiembre 2008 (con Soluciones) - DSA-Research

fd1=open(?data/doc/examen?,O_CREATE?); ... Proponer el código del esquema de ejecución de este grafo (1)usando fork() y wait(). ..... pidA = Fork(); exec(?A);.

un extrait du document



Ingeniería Informática. Curso 3º
Sistemas Operativos
Examen Final. PROBLEMAS.
5 de Septiembre de 2008


Es necesario modelar el comportamiento de un ascensor que presta servicio a un edificio de 20 pisos. Dicho ascensor es utilizado por robots para subir a su planta destino. El ascensor se encuentra inicialmente en la planta baja. Los robots afluyen continuamente y van accediendo al ascensor en la planta baja. Cuando hay 5 robots en el ascensor, éste cierra sus puertas; los demás robots tendrán que esperar. Cada robot que consigue acceder al ascensor solicita un piso de destino (por simplicidad consideraremos que cada robot subido al ascensor va un piso diferente).
Una vez ocupado el ascensor al completo, éste se pone en marcha y sube, accediendo a los pisos solicitados en orden de recorrido. El robot que haya llegado a su destino se baja y acaba su operación. Vaciado el ascensor, éste regresa inmediatamente a la planta baja para cargar 5 nuevos robots.
El comportamiento de ambos procesos los podemos esquematizar así:
robot(int piso_destino)ascensor()- Esperar a que haya sitio en el ascensor, y entrar cuando sea posible; - Pulsar piso de destino;
- Notificar al ascensor si ya hay 5 robots
- Esperar a que el ascensor alcanza el piso destino; - BajarIr a planta baja(); // función dada. No implementar
while (true) {
esperar a que entren 5 robots;
for (i=0; i=5)
waitc(A,mutex);
ocupados++;
PISOSB[destino] = TRUE;
if (ocupados==5) signalc(B);
waitc(PISOSA[destino], mutex);
ocupados--;
PISOSB[destino] = FALSE;
signalc(C);
unlock(mutex);while (TRUE) {
lock(mutex);
while (ocupados < 5)
waitc(B, mutex);
p=0;
for (i==0; i id2 de TIN (fd2) -> id3 de TIN

TIN (tabla global)
Entrada N punteros Contador Permisos Puntero a nod-v
Id1: 2 5000 R,W
Id2: 1 0 R,W
Id3: 1 1500 R,W


Visión LÓGICA del estado final de cada fichero:

Examen -> 2000 ‘a’ (BL 0 -1) – blancos hasta 4500 (BL 1,2,3y4) – 500 ‘a’ (BL 4) – blancos hasta 6500 (BL 4, 5 y 6) – 500 ‘c’ (BL6). Total 7 bloques lógicos

Result -> 500 ‘c’ (BL 0) – 1000 ‘b’ (BL 0 y 1). Total 2 bloques lógicos


b) Sistema FAT.

Posible FAT:

0 1 2 3 4 5 6 7 8 9 10 11 12
eof eof 3 eof 5 6 7 8 9 10 eof free free


El bloque FÍSICO 0 contendrá las entradas del directorio “data”:
Nombre fichero Tipo Tamaño Fecha Permisos….. Primer bloque Físico
Doc D --……… 1
Result R 1500 ………………… 2

El bloque FÍSICO 1 contendrá las entradas del directorio “data” :
Nombre fichero Tipo Tamaño Fecha Permisos…..
examen R 7000 ………………… 4


El fichero “result” se almacenará en los bloques físicos 2 y 3. El fichero “examen” ocupará los ficheros físicos 4,5,6,7,8,9 y 10 (si bien, los bloques 6, 7 y 9 contendrán únicamente espacios en blanco).








c) Sistema tipo Unix
Necesitaremos 4 nodos-i:

Nodo-i 3 (relativo al directorio /data) Nodo-i 7 (relativo al directorio /data/doc)
Tipo: D Tipo: D
P. Dir 0: 33 P. Dir 0: 12
P. Dir 1: NULL P. Dir 1: NULL
P. Dir 2: NULL P. Dir 2: NULL
P. Dir 3: NULL P. Dir 3: NULL
P. Ind. : NULL P. Ind. : NULL



Nodo-i 8 (relativo al fichero /data/result) Nodo-i 12 (relativo al fich. /data/doc/examen)
Tipo: R …. Tipo: R
P. Dir 0: 15 P. Dir 0: 40
P. Dir 1: 16 P. Dir 1: 41
P. Dir 2: NULL P. Dir 2: NULL
P. Dir 3: NULL P. Dir 3: NULL
P. Ind. : NULL P. Ind. : 42


Bloques (físicos) de datos ocupados:

Bloque 33 (entradas de /data) Bloque 12 (entradas de …/doc)
. 3 . 7
.. ? .. 3
doc 7 examen 12
result 8

Bloques físicos 15 y 16: contenido de /data/results

Bloques físicos 40 y 41: contenido de los bloques lógicos 0 y 1 de /data/doc/examen

Bloque físico 42 (bloque físico dedicado a albergar punteros a otros bloques físicos)
43
NULL
47
NULL
NULL
…….

Bloque físico 43: contenido del bloque lógico 4 de …/examen
Bloque físico 47: contenido del bloque lógico 6 de …/examen











TEORIA

Cuestión1
a)
Con fork() y wait()pidA = Fork(); exec(“A);
wait(pidA);
pidB = fork(); exec(“B”);
pidC = fork(); exec(“C”);
wait(pidC);
pidE = fork(); exec(“E”);
wait(pidB);
pidD = fork() ; exec(“D”) ;
wait(pidE);
wait(pidD);
pidF = fork() ; exec(“F”);
wait(pidF);
pidG = fork(); exec(“G”);
wait(pidG);
b) Puntos de activación del planificador
Acaba el proceso en ejecución P
P realiza una llamada bloqueante (p.ej, pause())
P causa una excepción que lo bloquea (p.ej., fallo de página mayor)
P desbloquea un proceso más prioritario (p.ej., signal(sem) o msgsend(q,m))
Una interrupción desbloquea un proceso más prioritario que P. (p.ej., fin de temporizador, o de operación de disco o de operación de Terminal)
Una interrupción de reloj marca el fin del quanto de P
P cede el uso de la CPU: yield();
P hace una llamada que rebaja su prioridad y como consecuencia otro proceso resulta más prioritario (p.ej., nice(10))
P crea un hilo más prioritario (p.ej. pthread_create())


Cuestión 2.

a) Ventaja VERSION 1: reduce la espera activa al permitir que otros procesos preparados para ejecutarse tengan la posibilidad de ser planificados mientras dure la espera activa por el cerrojo
Ventaja VERSION 2: la operación test-and-set supone un doble acceso indivisible a la dirección de memoria del “cerrojo” – una para leer su contenido y otra para escribir (un 1) en él. Con esta versión, mientras la espera activa detecte que el valor del cerrojo es 1 solo realizará operaciones de lectura de memoria, ahorrando así los ciclos de escritura.

b)
ThreadsProcesos emparentadosProcesos no emparentadosSincronizaciónMutex, varcondSemáforos_anónimosSemáforos con nombreComunicaciónMemoria_compartidaPipes anónimos,
Memoria compartidaPipes con nombre
Memoria compartida
Paso de mensajes

Cuestión 3.
El fichero ejecutable tiene una estructura fija en la que se incluyen secciones (código, datos con valor inicial) que se convertirán en regiones de memoria. En el fichero existe una Tabla de Secciones que marca el comienzo y tamaño de cada sección dentro del fichero.
Una biblioteca estática ya está incluída en el fichero ejecutable, por tanto no modifica el mapa de memoria durante la ejecución del proceso (formará parte de la región de código y de la región de datos)
Sin embargo, en el caso de una biblioteca dinámica, el código necesario se incluirá en el mapa de memoria del proceso cuando éste haga uso de una función de la biblioteca o durante la carga del programa (creándose nuevas regiones de forma dinámica).
Fallo de página -> excepción
-> (asumiendo dirección de usuario) el S.O. comprueba la dirección virtual para saber si está en una región válida del mapa del proceso (podría ser una expansión de pila)
-> Buscar en la(s) listas asociadas al buffering si el contenido aún reside en memoria (fallo menor). Si es así, no hay que buscar marco libre. Sólo modificar la TP del proceso para que la página apunte a ese marco y ponerla como válida.
-> Si no está en memoria, habría que traerla a memoria desde el dispositivo de respaldo. Como se usa buffering, tenemos un marco libre seguro.
-> No es necesario emplear ninguna política de reemplazamiento de página. Ese proceso está desacoplado del tratamiento del fallo gracias al buffering.
c) Falso. Los hilos comparten el mismo espacio virtual. De hecho, comparten prácticamente todas las regiones (excepto la pila, pero todas las pilas residen en el mismo espacio virtual).


Cuestión 4.

Reloj del sistema, funciona con una batería y mantiene la fecha y hora con el sistema apagado. El reloj temporizador produce interrupciones periódicamente, que se utilizarán para distintos propósitos (temporizadores, estadísticas, planificación)
Ninguno de los dos, aunque su programación se realiza escribiendo en registros de E/S y usa interrupciones para notificar sus eventos. Pero no tiene sentido pensar en un acceso aleatorio (de tamaño fijo) o secuencial al dispositivo.
Sí. Es un contador que, al llegar a 0, produce una interrupción.
Sí (para planificaciones tipo round-robin)


Falso. En esos casos es contraproducente
Cierto.

Se usa RAID5 por la distribución de bloques de paridad entre discos. Para una escritura, leeremos el bloque del disco destino, lo modificaremos (escritura); leeremos el disco que contenga el bloque de paridad correspodiente, recalcularemos la paridad y escribiremos de nuevo el bloque (otra escritura).

Cuestión 5.
a. Fichero regular -> lseek aplicable. EOF: final de fichero
Directorio -> lseek: no. EOF: final de la lista de entradas
Tubería -> lseek: no. EOF: se devuelve en una lectura si no hay escritores en el extremo de escritura
Enlace simbólico -> lseek: no (no sobre el enlace; sí si el fichero enlazado es regular). EOF: depende del fichero apuntado
Dispositivo (bloques o caracteres) -> lseek: no. EOF: Depende del dispositivo

b. La lectura de un i-nodo de disco incluiría parte de la información del fichero. Para directorios, puede incluir la lista de muchos de sus ficheros, evitando una segunda lectura. La desventaja es que traemos más datos potencialmente inútiles por cada lectura de nodo-i. Además, si el fichero está vacío, desperdiciaremos esos 512 bytes.
En el caso mejor para el tratamiento de la ruta propuesta bastaría con 3 lecturas (los nodos-i de home, pepe y practica2) para conocer el número de nodo-i de “prog.c” (con otra lectura, tendríamos el nodo-i de prog.c)

A

C

E

G

B

D

F