UC3M _Universidad Carlos III de Madrid_ _ Grado en Ingeniería Informática _ Sistemas Operativos _ coleccion_

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

coleccion-examenes/.DS_Store
__MACOSX/coleccion-examenes/._.DS_Store
coleccion-examenes/2002/exasep2002.doc
UNIVERSIDAD CARLOS III DE MADRID
DEPARTAMENTO DE INFORMÁTICA
Examen de SISTEMAS OPERATIVOS. INGENIERÍA EN INFORMÁTICA. 12-septiembre-2002
Fecha de publicación de las notas: 20-septiembre-2002
 
Fecha de revisión: 23-septiembre-2002 a las 11:30 (laboratorio 2.2B08)
Para la realización del presente examen se dispondrá de 2 horas y media
No se pueden utilizar libros ni apuntes
Ejercicio 1 (4 puntos) Sea el siguiente programa denominado bucle_procesos:
int main (int argc, char **argv) {
 int contador, i, pid;
 contador = atoi(argv[1]);
 i = 0;
 while (i < contador) {
 pid = fork();
 i++;
 } 
a.) Explique qué hace y dibuje un diagrama con la jerarquía de procesos que se origina cuando se ejecuta el mandato bucle_procesos 4.
b.) Explique qué es un proceso zombie y cuándo se producen.
c.) ¿Se generan procesos zombies al ejecutar el mandato anterior? Explique su respuesta.
d.) ¿Qué ocurriría si se ejecutara bucle_procesos 100? Explique la respuesta y modifique el programa para que se solucione el problema existente.
e.) Modifique el programa anterior para que todos los procesos generados puedan compartir el archivo denominado pepe.txt. Explique su solución.
Ejercicio 2 (3 puntos) Sean las dos instrucciones máquina siguientes:
LD R7, A
# Carga en el registro R7 el contenido de la posición de memoria A
SUB B,R7, C
# Resta C a R7 y lo almacena en B. B y C direcciones de memoria
Asumiendo que se ejecutan en un computador con memoria virtual y que cada instrucción y cada operando ocupa una palabra de memoria, conteste a las siguientes preguntas:
a.) ¿Cuántos marcos de página serían necesarios para ejecutar estas instrucciones teniendo en cuenta un modelo de proceso en el que texto y datos están en distintos segmentos? Explique su respuesta. 
b.) ¿Cuántos fallos de página se podrían producir como máximo debidos a la ejecución de las dos instrucciones anteriores? Explique su respuesta.
c.) ¿Qué cambiaría si se usara direccionamiento relativo directo para A, B y C (sumando las direcciones a un registro)? ¿Y si se usara direccionamiento indirecto? 
Ejercicio 3 (3 puntos) El siguiente programa intenta implementar el siguiente mandato: 
dividir f1 f2 f3
Este mandato lee el archivo f1 y crea dos archivos (f2 y f3). En el archivo f2 se escriben los bytes situados en las posiciones pares de f1 y en el archivo f3 los bytes situados en las posiciones impares. Así, si el contenido de f1 es 12121212121212
· El contenido de f2 será 1111111
· El contenido de f3 será 2222222
void main (int argc, char *argv[]) 
{
int fd1, fd2, fd3;
char c;
int size;
int i;
fd1= open(argv[1], O_RDONLY);
fd2= creat(argv[2], 0640);
fd3= creat(argv[3], 0640);
size = lseek(fd1, 0, SEEK_END);
lseek(fd1, 0, SEEK_SET);
if (fork() == 0) {
for ( i = 0; i < size; i = i + 2) {
lseek(fd1, i, SEEK_SET);
read(fd1, &c, 1);
write(fd2, &c, 1);
}
}
else {
for ( i = 1; i < size; i = i + 2) {
lseek(fd1, i, SEEK_SET);
read(fd1, &c, 1);
write(fd3, &c, 1);
}
}
close(fd1);
close(fd2);
close(fd3);
exit(0);
}
Se pide:
a) Suponiendo que el programa es correcto, modifique el programa para que haga un correcto tratamiento de todas las llamadas al sistema.
b) ¿Por qué el programa anterior no consigue el funcionamiento esperado para el mandato dividir? Razone su respuesta.
c) Suponiendo que la implementación sigue utilizando dos procesos, proponga dos modificaciones que resuelvan el problema del apartado b.
coleccion-examenes/2002/Icon
__MACOSX/coleccion-examenes/2002/._Icon
coleccion-examenes/2002/jun2002/2002junrexa.pdf
Uc3m Informática Técnica de Gestión Examen de 26 junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
1. (2,5 puntos) 
 
Las prácticas de algunos alumnos se bloquean con ciertos datos de entrada. Un 
profesor decide realizar un programa que ejecute un comando indicado por parámetro 
que imprima un mensaje de error cuando pase un minuto de ejecución o la salida del 
comando supere el Megabyte de tamaño. 
 
De manera que el programa con un comando bien implementado se ejecutaría: 
 
 
# ./auto_ejec comando_bueno 
entrada 1 
entrada 2 
... 
entrada n 
 
Si el comando se bloquea más de un minuto (60 segundos) la sesión es: 
 
 
#./auto_ejec comando_bloqueado 
entrada 1 
entrada 2 
entrada 3 
ERROR: comando se bloquea. 
 
Si el comando queda en un bucle infinito, la sesión queda: 
 
 
# ./auto_ejec comando_infinito 
entrada 1 
entrada 1 
entrada 1 
... 
ERROR: salida mayor de un mega. 
 
El comando a ejecutar no necesita ningún parámetro. 
 
Para controlar la salida del comando, el profesor piensa en el siguiente diseño: 
 
 
 
 
 
 
 
 
 
 
 
comando auto_eje 
1 0 1 
pipe 
Uc3m Informática Técnica de Gestión Examen de 26 junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
Para implementar el comando el profesor piensa en el siguiente código: 
 
#include <unistd.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <signal.h> 
 
void fin_minuto ( int sno ) ; 
 
int main ( int argc, char *argv[] ) { 
 int err; 
 int pd[2]; 
 pid_t cpid; 
 int leido, leidos; 
 char buf[1024]; 
 
 /* uso */ 
 if (argc < 2){ 
 printf("uso: %s comando\n",argv[0]); 
 exit(1); 
 } 
 
 /* RELLENAR 1 : crear pipe */ 
 
 cpid = fork(); /* fork */ 
 switch (cpid) { 
 case -1: /* error fork */ 
 perror("fork:"); 
 exit(3); 
 break; 
 case 0: 
 /* RELLENAR 2 : conectar salida al pipe */ 
 execvp(argv[1],argv+1); /* ejecutar comando */ 
 perror("execvp:"); 
 exit(4); 
 break; 
 default: 
 /* RELLENAR 3 : conectar entrada del pipe */ 
 signal(SIGALRM, fin_minuto); /* cronometrar 60 segundos */ 
 alarm(60); 
/* RELLENAR 4 : leer y escribir, máximo 1 mega */ 
 alarm(0); /* fin cronómetro */ 
 
 if (leidos >= 1024*1024) /* comprobar leidos */ 
 { 
 printf("ERROR: salida mayor de un mega.\n"); 
 exit(5); 
 } 
 break; 
 } 
 
 /* fin main */ 
 return 0; 
} 
 
void fin_minuto ( int sno ) 
{ 
 /* RELLENAR 5 : imprimir "ERROR: comando se bloquea.\n" y finalizar la ejecución*/ 
} 
 
Se pide ayudar a nuestro profesor, completando las secciones de códigos indicadas a rellenar, 
justificando brevemente. Basta escribir el código distinguiendo las 5 zonas. 
Uc3m Informática Técnica de Gestión Examen de 26 junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
 
2. (2,5 puntos) 
Suponga un sistema con memoria virtual paginada usando dos niveles de tablas de 
páginas, direccionamiento de 32 bits con páginas de 4 kbytes de tamaño. 
Los atributos asociados a las páginas son: M (modificado), X(ejecutable), RO(sólo 
lectura), P(presente) y COW(Copiar en la escritura). Este último atributo indica que si 
na marcada con COW = 1, primero ha de duplicar la página 
y después modificar esta duplica. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A) Se desea que la tabla de segundo nivel ocupe una página, es decir, 4Kbytes. 
 
§ ¿Cuántos bits son necesarios para direccionar esta tabla? 
§ ¿Sería posible incluir esta tabla de 2º nivel en memoria virtual y no en 
 
§ ¿Cuánto ocupa en memoria principal la tabla de nivel 1? 
§ ¿Es posible tener en Memoria virtual la rutina de tratamiento de fallo de 
página? ¿Por qué si? / ¿Por qué no? 
 
B) Se desea implementar la llamada al sistema: 
 
 mm_FastMemCpy ( void * dst, void * src, int npages ) ; 
 
 Para poder tener a partir de la dirección indicada en 'dst' los mismos datos que están 
a partir de 'src'. Se garantizan que ambas direcciones (src y dst) son el comienzo de 
una página y npages es un número de páginas válido. 
 
 
 
 
 
 
 
 
 
 
tabla N1 
 
 
 
 
 
 
 
tabla N2 
 
 
 
 
 
 
 
 
Memoria
Uc3m Informática Técnica de Gestión Examen de 26 junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
 
Nombre y Apellidos NIA 
 
 
 
Se pide: Escriba y describa en pseudocódigo la función descrita, usando la siguiente 
tabla: 
 
 
Pasos Comentario 
Acceder a ... 
 
 
 
Es necesario comprobar ... 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Uc3m Informática Técnica de Gestión Examen de 26 junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
 
3. (2,5 puntos) 
 
 
Cuatro alumnos están jugando en clase en el descanso a un juego de cartas que 
implica coordinación (no saltarse los turnos) y exclusión mutua (mientras uno roba una 
carta o la cambia con el compañero el resto debe esperar a que acabe para no quitarse 
la carta de la mano). 
 
Se plantea tomar como base esta experiencia para implantar una arquitectura de 
comunicación entre procesos que permita realizar una práctica de inteligencia artificial 
en la que cada alumno codificará su estrategia dentro de las siguientes funciones 
aisladas: 
 
 
Proceso_jugador() 
{ 
while ( 1 ) { 
 Pensar_la_jugada(); // va calculando la mejor opción 
 Jugar(); // intercambia rápidamente las cartas 
} 
} 
 
 
Todos los procesos serán hijos de un proceso principal denominado partida, y por tanto 
heredaran tras el fork y exec correspondiente una serie de semáforos inicializados de la 
siguiente manera: 
 
#define NUMERO_DE_JUGADORES 4 
#define NUMERO_DE_CARTAS 40 
#define SIGUIENTE ((IDENTIFICADOR_DE_JUGADOR + 1) % NUMERO DE JUGADORES) 
Semáforo esperar [NUMERO_DE_JUGADORES]; 
User_ID baraja [NUMERO_DE_CARTAS]; 
 
 
Se pide: 
 
1. Intercalar en el código propuesto para proceso_jugador() las ordenes wait y signal 
necesarias sobre los semáforos esperar[IDENTIFICADOR_DE_JUGADOR] y 
esperar[SIGUIENTE] para asegurar el correcto funcionamiento del mismo, es decir, que 
cada jugador deba esperar a su turno antes de poder ejecutar jugar() 
 
2. ¿Cómo debe estar inicializado el array de semáforos para que el funcione, es 
decir, empiece el primer jugador y ceda el turno al siguiente y así sucesivamente, 
quedando bloqueado cada cual hasta que le toque? 
 
3. En el caso de que jugar() no se ejecute de forma atómica, ya que tendrá que 
modificar al menos dos entradas de la tabla baraja… ¿Habría que incorporar algo para 
garantizar la exclusión mutua en la ejecución de jugar()? De ser necesario, escribir el 
código. De no serlo, explicar por que. 
 
 
Uc3m Informática Técnica de Gestión Examen de 26 junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
 4. (2,5 puntos) 
 
El sistema de ficheros de la figura muestra el resultado del disco /dev/hda3 una vez 
montado sobre el directorio /usr/extra. 
 
Se trata de una partición muy pequeña en la que tan solo hay 10 inodos y 50 sectores 
de datos de 1K cada uno de ellos. 
 
 
 
 
 
 
Sobre ese disco y con CWD /usr/extra, se ejecutan los comandos siguientes: 
 
 rmdir directorio 
 touch fichero1 
 ln fichero1 fichero2 
 ln –s ./fichero2 fichero3 
 
nota: touch actualiza la fecha de un fichero, y si no existe lo crea vacio. 
 
Se pide: 
 
 1.) Dibujar la estructura del disco al finalizar las operaciones indicadas, 
indicando los valores de inodos y bloques según lo mostrado en el dibujo 
 
 2.) ¿Cuántos ficheros de 1K podrían crearse a partir de ese momento? 
 
 3a.) ¿Cuál seria el tamaño máximo de fichero que podríamos crear si en lugar 
de crear muchos de 1K creásemos solo uno pero grande? 
 
 3b.) ¿Cuantos enlaces físicos (o duros) podrían hacerse a ese fichero de tamaño 
 una vez creado el mismo? Explica la respuesta 
 
3c.) ¿Y si en lugar de físicos los quisiésemos simbólicos, cuantos podrían 
crearse? 
 
 
 
 
 i - nodo 1 
d rwxr - xr - x 
L ink - count 2 
T amaño 1 024 
datos 1 1 
 
 i - nodo 0 
d rwxr - xr - x 
L ink - count 3 
T amaño 1 024 
datos 1 0 
 bloque 0 
 
. 0 
.. 0 
directorio 1 
 bloque 1 
 
. 1 
.. 0 
Uc3m Informática Técnica de Gestión Examen de 26 junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
1 SOLUCION 
#include <unistd.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <signal.h> 
 
 
void fin_minuto ( int sno ) ; 
 
int main ( int argc, char *argv[] ) 
{ 
 int err; 
 int pd[2]; 
 pid_t cpid; 
 int leido, leidos; 
 char buf[1024]; 
 
 /* uso */ 
 if (argc < 2) 
 { 
 printf("uso: %s comando\n",argv[0]); 
 exit(1) ; 
 } 
 
 /* pipe */ 
 err = pipe(pd); 
 if (err < 0) 
 { 
 perror("pipe:"); 
 exit(2) ; 
 } 
 
 /* fork */ 
 cpid = fork(); 
 switch (cpid) 
 { 
 case -1: 
 /* error fork */ 
 perror("fork:"); 
 exit(3); 
 break; 
 case 0: 
 /* salida al pipe */ 
 close(pd[0]); 
 close(1); 
 dup(pd[1]); 
 close(pd[1]); 
 
 
 
 
 /* ejecutar comando */ 
 execvp(argv[1],argv+1); 
 perror("execvp:"); 
 exit(4); 
 break; 
 
 default: 
 /* entrada del pipe */ 
 close(pd[1]); 
 close(0); 
 dup(pd[0]); 
 close(pd[0]); 
 
 /* cronometrar 60 segundos */ 
 signal(SIGALRM, fin_minuto); 
 alarm(60); 
 
 /* leer y escribir, máximo 1 mega */ 
 leidos = 0; 
 do { 
 leido = read(0,buf,1024); 
 if (leido <= 0) break; 
 
 write(1,buf,1024); 
 leidos += leido; 
 
 } while(leidos < 1024*1024+1); 
 
/* fin cronómetro */ 
 alarm(0); 
 
/* comprobar leidos */ 
 if (leidos >= 1024*1024) 
 { 
 printf("ERR: salida > mega.\n"); 
 exit(5); 
 } 
 break; 
 } 
 
 /* fin main */ 
 return 0; 
} 
 
 
void fin_minuto ( int sno ) 
{ 
 printf("ERROR: comando se 
bloquea.\n"); 
 exit(6); 
} 
 Informática Técnica de Gestión Examen de junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
 
2 SOLUCION 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A) Se desea que la tabla de segundo nivel ocupe una página, es decir, 4Kbytes. 
 
§ ¿Cuántos bits son necesarios para direccionar esta tabla? 10 
§ ¿Sería posible incluir esta tabla de 2º nivel en memoria virtual y no en 
memoria física? Sí 
§ ¿Cuánto ocupa en memoria principal la tabla de nivel 1? 2^10=4Kb 
§ ¿Es posible tener en Memoria virtual la rutina de tratamiento de fallo de 
página?. ¿Por qué si?. ¿Por qué no?. No, porque si no se encuentra 
presente la rutina de tratamiento de excepción en memoria, quedaría 
en un bucle infinito. 
 
B) mm_FastMemCpy ( void * dst, void * src, int npages ) ; 
 
Pasos Comentario 
Acceder a la tabla de página de Nivel 
1 y Nivel 2 correspondiente a la 
dirección origen. 
Es necesario comprobar que es una 
página válida y asignada al proceso. 
Acceder a la tabla de página de Nivel 
1 y Nivel 2 correspondiente a la 
dirección destino. 
Es necesario comprobar que es una 
página válida y asignada al proceso. 
Copiar tantas entradas como el 
parámetro 'npages' indique, de la 
tabla de Nivel dos en la que está la 
dirección 'src' a la tabla de nivel dos 
en que está la dirección 'dst'. 
Puede realizarse en un bucle o copiando 
la zona de tabla de páginas de nivel dos 
en que están los 'npages' descriptores a 
partir del asociado a 'src'. 
Establecer el atributo COW (Copy On 
Write) a uno 
Permite retrasar la copia de contenidos 
al momento de actualización de datos. 
 
 
 
 
 
 
 
 
tabla N1 
 
 
 
 
 
 
 
tabla N2 
 
 
 
 
 
 
 
 
Memoria 
 
10 
 
10 
 
12 
 Informática Técnica de Gestión Examen de junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
3 SOLUCION 
 
1) 
Proceso_jugador() 
{ 
while ( 1 ) { 
 Pensar_la_jugada(); 
 Wait esperar[IDENTIFICADOR_DE_JUGADOR]; 
 Jugar();
Signal esperar[SIGUIENTE]; 
} 
} 
 
 
2) 
 Semáforo esperar [NUMERO_DE_JUGADORES] = { 1, 0, 0 …. 0 , 0 }; 
 Como no podemos garantizar cual de los jugadores termina primero de pensar la 
jugada, solo un semáforo debe estar sin bloquear (podrían inicializarse todos a cero si 
antes de hacer los fork se hiciese un signal a uno de ellos). 
 
3) 
 No hace falta crear ningún semáforo binario tipo mutex, ya que garantizamos 
con la perfecta secuenciación de accesos a la función jugar() que uno y solo uno entra 
en esa sección critica a la vez. 
 Informática Técnica de Gestión Examen de junio de 2002 
Sistemas Operativos 2001-2002 ssoo2@arcos.inf.uc3m.es 
4 SOLUCION 
 
1. Dibujar la estructura del disco al finalizar las operaciones indicadas. 
 
 
 
 
 
 2. ¿Cuántos ficheros de 1K pueden crearse a partir de ese momento? 
Tantos como i-nodos, y solo quedan 10 – 3 = 7 
 3. ¿Cuál seria el tamaño máximo de fichero que podríamos crear si en lugar de 
crear muchos de 1K creásemos solo uno pero grande? 
Tantos K como bloques libres quedan: 50 - 2 = 48 K 
 4. Cuantos enlaces físicos podrían hacerse a ese fichero de tamaño máximo una 
vez creado el mismo. Explica la respuesta 
En el directorio que existe, pueden introducirse enlaces fisicos con distinto nombre pero 
apuntando al mismo i-nodo hasta que se llene el directorio. 
5. ¿Y si en lugar de físicos los quisiésemos simbólicos, cuantos podrían crearse? 
Ninguno, ya que necesitaríamos al menos un bloque de datos por enlace simbolico, y el 
disco esta ya lleno. 
 
 
 i - nodo 0 
d rwxr - xr - x 
L ink - count 2 
T amaño 1 024 
datos 1 0 
 
 i - nodo 1 
 -rwxr - xr - x 
L ink - count 2 
T amaño 0
 datos 1 
 i-nodo 2 
lrwxrwxrwx 
link-count 1 
tamaño 8 
datos 1 
 bloque 0 
 
. 0 
.. 0 
fichero1 1 
fichero2 1 
fichero3 2 
 bloque 1 
./fichero2 
coleccion-examenes/2002/jun2002/Icon
__MACOSX/coleccion-examenes/2002/jun2002/._Icon
coleccion-examenes/2002/jun2002/ssoo-sol-exa-jun-2002.doc
Sea el archivo correspondiente al buzón de correo del usuario pepe, que es su dueño y cuyo nombre absoluto es /var/spool/mail/alumnos/bupepe. Suponiendo que el nodo-i / está en memoria, responda a las siguientes preguntas:
a.- ¿Cuántos accesos a disco serán necesarios para abrir el archivo, como mínimo?
· / está en memoria. Var está en el primer bloque de datos --> 1 acceso a disco para obtener su entrada + 1 acceso a disco para obtener nodo-i de var 
· Nodo-i var --> 1 acceso a disco para obtener el bloque datos + 1 acceso a disco para obtener nodo-i de spool.
· Nodo-i spool --> 1 acceso a disco para obtener el bloque datos + 1 acceso a disco para obtener nodo-i de mail
· Nodo-i mail --> 3 accesos a disco para obtener el bloque datos + 1 acceso a disco para obtener nodo-i de alumnos
· Nodo-i alumnos --> 2 accesos a disco para obtener el bloque datos + 1 acceso a disco para obtener nodo-i de bupepe
En total: 13 accesos a disco
b.- ¿En que se diferencian stat y fstat?
Si no está abierto se usa la llamada stat:
 ret = stat (nombre, struct stat &estado);
Donde nombre es el nombre del archivo y estado es una estructura en la que devuelve la información de estado del archivo.
Si está abierto se usa la llamada fstat:
 ret = fstat (fd, struct stat &estado);
Donde fd es el descriptor del archivo abiertoy estado es una estructura en la que devuelve la información de estado del archivo.
c.- ¿Si se quieren leer 21 Kbytes del archivo, es necesario comprobar prermisos con stat antes de abrir con O_RD ? Escriba un programa que lea los 21 Kbytes del archivo.
No hace falta usar stat ni fstat, aunque se podría. La razón es que la llamada open cuando se piden los parámetros adecuados de operaciones devuelve un fallo si no se pueden hacer esas operaciones sobre el archivo. 
En este caso, pepe es del grupo de juan y el archivo tiene permisos rwxr-xr-x, lo que significa que los usuarios del grupo de juan lo pueden leer y ejecutar sin problemas. Por tanto la solución sería como la siguiente:
void main (int argc, char **argv) {
 int fd, leidos, i;
 char buffer[1024];
 fd = open(“/var/spoll/mail/alumnos/bupepe”, O_RD);
 if (fd < 0){
 println(“error al abrir el archivo \n”);
 exit (-1);
 }
 for (i = 0; i < 21; i++) {
 leidos = read(fd, buffer, 1024);
 if (leidos ¡= 1024){
 println(“error al leer el archivo \n”);
 exit (-1);
 }
 }
 close (fd);
}
__MACOSX/coleccion-examenes/2002/jun2002/._ssoo-sol-exa-jun-2002.doc
__MACOSX/coleccion-examenes/2002/._jun2002
coleccion-examenes/2002/septiembre2002/.DS_Store
__MACOSX/coleccion-examenes/2002/septiembre2002/._.DS_Store
coleccion-examenes/2002/septiembre2002/2002sept_02_web.doc
Uc3m Informática Técnica de Gestión 
Examen de 16 de septiembre de 2002
1. (3 puntos)
Un sistema de gestión de materias peligrosas se ha automatizado mediante programas concurrentes que mediante controles remotos operan unos robots que las manipulan.
En ocasiones deben entrar en una zona donde hay sustancias inflamables (ZSI). Para ello deben obtener acceso a una sección donde sólo pueden estar dentro simultáneamente un máximo de 5 procesos, para minimizar el riesgo de que choquen.
Dentro de la zona mencionada hay un habitáculo donde un robot puede entrar (y sólo uno) para realizar mezclas peligrosas. El habitáculo de mezclas (HM) sólo se puede abrir desde fuera, por lo que para salir el robot debe esperar a que otro robot quiera utilizar el habitáculo, o llamar a algún robot auxiliar que deberá conseguir entrar en la ZSI y abrir el HM (sin meterse en él, sólo abrir y cerrar).
El código utilizado para dar solución a la mencionada problemática es el siguiente:
Semáforo ZSI = 5;
Semáforo entrar_HM = 1;
Semáforo abrir_puerta = -1;
Int quieren_entrar = 0;
Int quieren_salir=0;
Semáforo mutex = 1;
Robot_manipulador(){
Semáforo ayudame = 0;
Lanza_proceso_asociado(robot_auxiliar);
// cada robot crea un asociado que despertará con un semáforo heredado
while (true){
Prepara_la_mision();
wait(ZSI);
// intenta entrar en la ZSI
manipula_sustancias_peligrosas();
if (es_necesaria_mezcla() ) {
entrar_mezclador();
realiza_la_mezcla();
salir_mezclador();
}
signal(ZSI)
//sale de la ZSI
}
}
robot_auxiliar(){
while(true){
wait(ayudame); 
//hasta que requieran mis servicios
wait(ZSI);
// intenta entrar en la ZSI
auxiliar_abrir_y_cerrar();
signal(ZSI);
//sale de la ZSI
}
}
entrar_mezclador(){
wait(mutex);
quieren_entrar++;
// contabilidad de entrada
signal(mutex);
wait(entrar_HM);
//intenta entrar en el HM
signal(abrir_puerta); 
// el que está dentro puede salir
}
salir_mezclador(){
wait(mutex);
quieren_entrar--;
// contabilidad de entrada
if (quieren_entrar < 1 )
signal(ayudame);
// despierta auxiliar
signal(mutex);
signal(entrar_HM);
//dejo que otro entre
wait (abrir_puerta);
//espera a poder salir del HM
}
auxiliar_abrir_y_cerrar(){
signal(abrir_puerta);
// y crea un hijo que hace un wait(abrir_puerta)
}
// para dejarla otra vez cerrada.
Se pide:
1. En el caso de que nos pueden asegurar que únicamente uno al día entra realmente a la HM y no está allí más de 15 minutos, trazar la ejecución del proceso mezclador1 (y se si auxiliar1 si procede) desde que intentan entrar en HM hasta que sale. Estudiar qué valores toman las variables durante el proceso de entrar y salir.
NOTA: es obligatorio contestar en forma de tabla con el siguiente formato:
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Semáforo abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
		Int quieren_salir
		Explicación
		Inicialmente
		
		1
		-1
		0
		0
		0
Mezclador1
		Entrar_mezclador()
		0
		0
		0
		1
		0
		Bloquea el mutex,
 incrementa quieren_entrar, libera mutex, 
el wait(entrar_HM) no le bloquea y el signal(abrir_puerta) deja abrir_puerta bloqueado.
 Las variables quedan como se indica a la izquierda.
		Mezclador1
		Salir_mezclador()
		
		
		
		
		
		
2. Repetir la traza pero suponiendo que 3 procesos mezcladores seguidos quieren entrar a la HM en el mismo minuto y están dentro 3 minutos cada uno. Los robots auxiliares tardan en llegar un mínimo de 10 minutos.
NOTA: es obligatorio contestar en forma de tabla similar al apartado anterior.
3. Estudiar la siguiente secuencia:
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Semáforo abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
		Int quieren_salir
		Explicación
		inicialmente
		
		1
		-1
		0
		0
		0
		
		Mezclador4
		Entrar_mezclador()
		
		
		
		
		
		
		Mezclador4
		Salir_mezclador()
		
		
		
		
		
		
		Mezclador5
		Entrar_mezclador()
		
		
		
		
		
		
		Mezclador5
		Salir_mezclador()
		
		
		
		
		
		
		Auxiliar4
		Auxiliar_abrir_y_cerrar()
		
		
		
		
		
		
		Auxiliar5
		Auxiliar_abrir_y_cerrar()
		
		
		
		
		
		
¿Qué comportamiento incorrecto ocurrirá a partir de ese momento con la solución propuesta en el enunciado?
4. Reescribir el código de las funciones salir_mezclador() y auxiliar_abrir_y_cerrar() para que el comportamiento sea correcto hasta en este caso extremo descrito en el apartado 3. Para ello se recomienda llevar correctamente la cuenta de cuantos quieren entrar y cuantos quieren salir de la HM, y vincular la realización de los waits y signals sobre abrir_puerta a su necesidad real en ese instante.
2. (2,5 puntos)
El sistema operativo que pretendemos utilizar en nuestro centro de gestión de procesos de control remoto de robots necesita que determinados parámetros sean configurados de antemano por el equipo administrador del sistema. Se le permite seleccionar el tipo de planificador que mejor se adapte a sus necesidades. Para elegirlo nuestros administradores estudian los procesos que más habitualmente se ejecutan y el tiempo que tardan en realizarlo, así como los instantes de llegada.
Al final de este estudio obtienen un juego de pruebas que se adapta más o menos a la dinámica del uso que se va a dar a este computador. Con estos datos realizan una serie de pruebas con diversos algoritmos de planificación, de manera que puedan decidir cual sería el óptimo en nuestro caso. Este juego de prueba es el siguiente:
		PROCESO
		Instante de llegada
		Tiempo de proceso
		A
		0
		3
		B
		1
		5
		C
		3
		2
		D
		9
		5
		E
		12
		5
Se procede a obtener una traza de ejecución de dichos procesos y evaluar cual es el proceso peor tratado, es decir, el que tarda más tiempo en ser ejecutado comparado con el que debería tardar realmente su ejecución. 
Se pide:
 Mostrar los resultados que se obtendrán utilizando los siguientes algoritmos de planificación:
1. FIFO
2. Turno rotatorio con q=1 (cuanto de tiempo) (RR Round Robin)
3. Turno rotatorio con q=4
4. Primero el proceso más corto (SPN Shortest Proces Next)
5. Menor tiempo restante (SRT Shortest Remainin Time, al que le queda menos tiempo por ejecutar)
6. Una vez evaluados los retardos para cada proceso que introduce cada uno de los algoritmos probados, ¿cuál de ellos deberíamos utilizar en nuestro sistema?. Razona tu respuesta
Nota: para la respuesta es obligatorio utilizar la hoja asignada al efecto:
3. (2 puntos)
En el sistema operativo anterior, el gestor de memoria debe permitirnos que sea posible ejecutar concurrentemente los 5 procesos anteriores. Disponemos para ello de un espacio de disco de 131072 bytes (128K) y una memoria física de 32768 bytes (32K). Sabemos que nuestros procesos al ser ejecutados tienen los siguientes parámetros:
		proceso
		código
		pila
		datos
		A
		4096
		2000
		2048
		B
		16384
		8200
		8192
		C
		2048
		1000
		1024
		D
		16384
		8200
		8192
		E
		16384
		8200
		8192
Los datos indican el tamaño en bytes de cada uno de los segmentos que forman parte de la imagen del proceso. Sabiendo que una página no puede contener partes de dos segmentos diferentes (pila, código o datos), hemos de determinar el tamaño de página que debería utilizar nuestro sistema y se barajan dos opciones: páginas de 4096 bytes (4K) o páginas de 512 bytes (1/2K). 
Se pide:
1. ¿Cuál sería la opción más apropiada, 4096 bytes o 512 bytes?. Justifica totalmente la respuesta mostrando todos los cálculos que has necesitado para llegar a dicha conclusión.
2. ¿Cuál es el formato de cada entrada de la Tabla de Páginas con el tamaño de página elegido? Justifica el tamaño de los campos con direcciones. ¿Cuántas entradas hay en la tabla de páginas (filas)?. Puedes añadir los bits que consideres necesarios para el buen funcionamiento del sistema indicando para que van a ser utilizados.
NOTA: si no has sabido contestar la pregunta 1 elige cualquiera de las dos opciones, indícala expresamente y responde con ese dato a esta pregunta.
3. ¿Cuántas Tablas de Páginas habrá en este sistema?
 4. (2,5 puntos)
En la siguiente tabla se muestra esquemáticamente el contenido de un sistema de ficheros tipo UNIX. Algunos de los i-nodos se muestran en la primera fila, y algunos de los bloques de datos en la fila de abajo:
0
1
2
3
4 ….
		drwxr-xr-x
linkcount=2
size=1024
bloque1=0
bloque2=
		-rw-r--r—
linkcount=2
size=1
bloque1=1
bloque2=
		lrwxrwxrwx
linkcount=1
size=1024
bloque1=2
bloque2=
		-rw-r--r—
linkcount=0
size=1024
bloque1=3
bloque2=
		
		
		
		
		
		i-nodos
		. 0
.. 0
caso.txt 1
quiso.txt 1
queso.txt 2
		3
		./quiso.txt
		./coso.txt
		
		
		
		
		
		Datos
El i-nodo correspondiente al directorio raíz es el 0.
Se pide:
1. Mostrar la salida en pantalla que tendrá la ejecución del comando
 
more *
2. Determinar el path absoluto del fichero que ocupa más espacio en el disco, y explicar por qué necesitamos más sectores para él y qué ventajas puede aportar ese gasto extra.
3. Indicar la secuencia de llamadas al sistema necesarias para ejecutar la orden ls /
Indicar la diferencia en el caso de ejecutar ls –l / para obtener tamaños, fechas y permisos de los ficheros.
4. Determinar cual tarda más en salir por pantalla al ejecutar more * suponiendo que hay que recuperar los sectores sin tener inicialmente en bufferes RAM nada. Para ese cálculo suponer que recuperar un sector desde disco tarda 60 milisegundos y si está en caché solo tarda 40 microsegundos.
5. ¿Se puede determinar cual ha sido la secuencia de creación de todos los ficheros?
Explica por qué, hasta el nivel que se pueda suponer con los datos del enunciado.
6. ¿Cómo podemos saber cuantos ficheros se pueden crear todavía en el disco?
		Nombre y Apellidos
		NIA
PROBLEMA 1
1.
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Semáforo abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
		Int quieren_salir
		Explicación
		inicialmente
		
		1
		-1
		0
		0
		0
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
2.
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Semáforo abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
		Int quieren_salir
		Explicación
		inicialmente
		
		1
		-1
		0
		0
		0
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		Nombre y Apellidos
		NIA
3.
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Semáforo abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
Int quieren_salir
		Explicación
		inicialmente
		
		1
		-1
		0
		0
		0
		
		Mezclador4
		Entrar_
mezclador()
		
		
		
		
		
		
		Mezclador4
		Salir_
mezclador()
		
		
		
		
		
		
		Mezclador5
		Entrar_
mezclador()
		
		
		
		
		
		
		Mezclador5
		Salir_
mezclador()
		
		
		
		
		
		
		Auxiliar4
		Auxiliar_
abrir_y_cerrar()
		
		
		
		
		
		
		Auxiliar5
		Auxiliar_
abrir_y_cerrar()
		
		
		
		
		
		
4.
		Nombre y Apellidos
		NIA
PROBLEMA 2
1. FIFO
		Proceso
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		E
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 D
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		C
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 B
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		Tiempo
		 0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: 
		Tiempo en el sistema
tiempo en ejecución
		 A
		B
		C
		D
		E
		media
2. RR q=1
		Proceso
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		E
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 D
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		C
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 B
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		Tiempo
		 0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: 
		Tiempo en el sistema
tiempo en ejecución
		 A
		B
		C
		D
		E
		media
3. RR q= 4
		Proceso
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		E
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 D
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		C
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 B
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		Tiempo
		 0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: 
		Tiempo en el sistema
tiempo en ejecución
		 A
		B
		C
		D
		E
		media
		Nombre y Apellidos
		NIA
4. SPN
		Proceso
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		E
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 D
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		C
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 B
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		Tiempo
		 0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: 
		Tiempo en el sistema
tiempo en ejecución
		 A
		B
		C
		D
		E
		media
5. SRT
		Proceso
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		E
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 D
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		C
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 B
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		Tiempo
		 0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: 
		Tiempo en el sistema
tiempo en ejecución
		 A
		B
		C
		D
		E
		media
6.
SOLUCION
1.
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Sem abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
		Int quieren_salir
		Explicación
		inicialmente
		
		1
		-1
		0
		0
		0
		
		Mezclador1
		Entrar_mezclador()
		0
		0
		0
		1
		0
		Bloquea el mutex, incrementa quieren_entrar, libera mutex, el wait(entrar_HM) no le bloquea a Mezclador1 pero impide que entre nadie más y el signal(abrir_puerta) deja abrir_puerta bloqueado. Las variables quedan como se indica a la izquierda.
		Mezclador1
		Salir_mezclador()
		1
		-1
		1
		0
		0
		Bloquea mutex, decrementa quieren_entrar, no despierta a ningún auxiliar, libera mutex, libera entrar_HM para que entre otro y queda bloqueado para que le abran la puerta y salir
		Auxiliar1
		Auxiliar_abrir_y_cerrar()
		
		0
		0
		
		
		Se despierta para abir la puerta
		Mezclador1
		Salir_mezclador()
		
		
		
		
		
		Se desbloquea
2.
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Semá abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
		Int quieren_salir
		Explicación
		inicialmente
		
		1
		-1
		0
		0
		0
		
		Mezclador1
		Entrar_mezclador()
		0
		0
		0
		1
		0
		Bloquea el mutex, incrementa quieren_entrar, libera mutex, el wait(entrar_HM) no le bloquea a Mezclador1 pero impide que entre nadie más y el signal(abrir_puerta) deja abrir_puerta bloqueado. Las variables quedan como se indica a la izquierda.
		Mezclador2
		Entrar_
mezclador()
		-1
		1
		
		2
		
		Bloquea el mutex, incrementa quieren_entrar, libera mutex,
wait(entrar_HM) le bloquea.
		Mezclador3
		Entrar_
mezclador()
		-2
		2
		
		3
		
		Bloquea el mutex, incrementa quieren_entrar, libera mutex,
wait(entrar_HM) le bloquea.
		Mezclador1
		Salir_
mezclador()
		-1
		1
		
		2
		
		Bloquea el mutex, decrementa quieren_entrar, >1 no hace el signal y libera mutex
Signal (entrar_HM) despierta a mezclador2
 wait (abrir_puerta) lo deja bloqueado para salir.
		Mezclador2
		Salir_
mezclador()
		0
		0
		
		1
		
		Se despierta de entrar_HM y hace un signal(abrir_puerta) para que M1 se vaya.
Que queda bloqueado en abrir_puerta tambien.
		Mezclador3
		Salir_
mezclador()
		1
		-1
		1
		0
		
		Lanza un auxiliar, que nos dicen que tardará más que los tres juntos en estar dentro. El signal(entrar_HM) deja este parámetro a su estado inicial correctamente. Y se bloquea tambien en abrir_puerta.
		Mezclador1
		Salir_
mezclador()
		
		
		
		
		
		Sale definitivamente (simplemente se desbloquea de su última instrucción)
		Mezclador2
		Salir_
mezclador()
		
		
		
		
		
		Sale definitivamente (simplemente se desbloquea de
su última instrucción)
		Auxiliar3
		Abrir_Y_cerrar()
		
		0
-1
		0
		
		
		Libera_abrir_puerta, y crea un hijo que vuelva a dejar el semáforo a -1.
		Mezclador3
		Salir_
mezclador()
		1
		-1
		0
		0
		0
		Se desbloquea y se va
3.
		Proceso
		Líneas que ejecuta
		Semáforo entrar_HM
		Semáforo abrir_puerta
		Semáforo ayudame
		Int quieren_entrar
		Int quieren_salir
		Explicación
		inicialmente
		
		1
		-1
		0
		0
		0
		
		Mezclador4
		Entrar_
mezclador()
		0
		0
		0
		1
		0
		
		Mezclador4
		Salir_
mezclador()
		1
		-1
		1
		0
		0
		
		Mezclador5
		Entrar_
mezclador()
		0
		0
		1
		1
		0
		
		Mezclador5
		Salir_
mezclador()
		1
		-1
		2
		0
		
		
		Auxiliar4
		Auxiliar_
abrir_y_cerrar()
		
		0
		1
		
		
		
		Auxiliar5
		Auxiliar_
abrir_y_cerrar()
		
		1
		0
		
		
		
 Puede entrar uno, pero al salir cree necesitar un auxiliar. Realmente sale porque otro de dentro entra dejándole ir. Este segundo también cree que necesita un auxiliar. Pero si ambos auxiliares hacen el signal(abrir_puerta), la dejan abierta para el siguiente mezclador que entre porque dejan el valor interno del semáforo a 2.
4. 
Entrar_mezclador(){
// no se ve afectado por cambio alguno
wait(mutex);
quieren_entrar++;
signal(mutex);
wait(entrar_HM);
//intenta entrar en el HM
signal(abrir_puerta); 
// el que está dentro puede salir
}
salir_mezclador(){
wait(mutex);
quieren_entrar--;
quieren_salir++;
if (quieren_entrar < 1 )
signal(ayudame);
// despertar auxiliar
signal(mutex);
signal(entrar_HM);
//le dejo para que entre
wait (abrir_puerta);
//espera para salir del HM
wait(mutex);
quieren_salir--;
signal(mutex);
}
auxiliar_abrir_y_cerrar(){
wait (mutex)
if (quieren_entrar <1){
// si hay ya alguien encolado: no hago falta
if (quieren_salir){
// y no sea que otro auxiliar ya lo haya dejado salir
signal(abrir_puerta);
}
}
signal(mutex);
}
SOLUCION 2:
1. FIFO
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		E
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		
		D
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		C
		
		
		
		 
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		B
		
		 
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: C
		Tiempo en el sistema
Tiempo en ejecución
		 A 3/3=1
		B 7/5=1,4
		C 7/2=3,5
		D 6/5=1,2
		E 8/5=1,6
		Media 1,74
2. Round Robin q=1
		E
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		
		D
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		
		
		
		C
		
		
		
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		B
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		A
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: C 
		Tiempo en el sistema
tiempo en ejecución
		 A 6/3=2
		B 10/5=2
		C 5/2=2,5
		D 9/5=1,8
		E 8/5=1,6
		Media 1,98
3. Round Robin q=4
		E
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		
		D
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		
		
		C
		
		
		
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		B
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: C 
		Tiempo en el sistema
tiempo en ejecución
		 A 3/3=1
		B 9/5=1,8
		C 6/2=3
		D 10/5=2
		E 8/5=1,6
		Media 1,88
4. SPN
		E
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		
		D
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		C
		
		
		
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		B
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: B
		Tiempo en el sistema
tiempo en ejecución
		 A 3/3=1
		B 9/5=1,8
		C 2/2=1
		D 6/5=1,2
		E 8/5=1,6
		Media 1,32
5. SRT
		E
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		
		D
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		C
		
		
		
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		B
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		A
		 
		 
		 
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		 
		0
		1
		2
		3
		4
		5
		6
		7
		8
		9
		10
		11
		12
		13
		14
		15
		16
		17
		18
		19
		20
		Proceso peor tratado: B
		Tiempo en el sistema
tiempo en ejecución
		 A 3/3=1
		B 9/5=1,8
		C 2/2=1
		D 6/5=1,2
		E 8/5=1,6
		Media 1,32
6. Para este conjunto de procesos, los algoritmos de planificación SPN y SRT obtienen los mismos resultados, y son los mejores de los 5 algoritmos probados, luego cualquiera de ellos sería el que deberíamos utilizar en nuestro sistema.
SOLUCION 3 :
1. NP = número de páginas que necesito
		proceso
		código
		NP4096
		NP512
		pila
		NP4096
		NP512
		datos
		NP4096
		NP512
		A
		4096
		1
		8
		2000
		1
		4
		2048
		1
		4
		B
		16384
		4
		32
		8200
		3
		17
		8192
		2
		16
		C
		2048
		1
		4
		1000
		1
		2
		1024
		1
		2
		D
		16384
		4
		32
		8200
		3
		17
		8192
		2
		16
		E
		16384
		4
		32
		8200
		3
		17
		8192
		2
		16
Con páginas de 4096 bytes necesitamos para poder ejecutar los 5 procesos cargar en memoria:
1+4+1+4+4+1+3+1+3+3+1+2+1+2+2 = 33 páginas
Puesto que el sistema tiene un espacio de direcciones de 131072, el número de páginas posibles sería:
131072 / 4096 = 217 / 212 = 25 = 32 páginas.
Para poder ejecutar los procesos necesitamos 33 páginas al menos, y solo tenemos capacidad para 32.
Con páginas de 512 bytes necesitamos para poder ejecutar los 5 procesos cargar en memoria:
8+32+4+32+32+4+17+2+17+17+4+16+2+16+16 = 219 páginas
Puesto que el sistema tiene un espacio de direcciones de 131072, el número de páginas posibles sería:
131072 / 512 = 217 / 29 = 28 = 256 páginas.
Para poder ejecutar los procesos necesitamos 219 páginas al menos, y disponemos de 256 luego si es posible ejecutar estos procesos.
Elegiremos pues páginas de 512 bytes.
2.
El número de marcos de que disponemos en el sistema es:
32768 / 512 = 215 / 29 = 26 necesitamos 6 bits para hacer referencia al marco de página.
		marco de página 
		P/A
		R
		M
		RO
		...
		6 bits
		1 bit
		1 bit
		1 bit
		1 bit
		1 bit
Cada proceso tiene su propia tabla de páginas, luego el número de entradas en la tabla de páginas dependerá de cual de los procesos (A, B, C, D o E) sea al que nos referimos. Para el proceso A, necesitaremos 16 entradas, tantas como páginas forman parte del proceso.
3. Serían al menos 5 tablas de página, una para cada proceso. 
SOLUCION 4 :
1. La salida por pantalla será
3
3
3
2. /queso.txt ya que además del bloque de datos con el contenido real necesita un bloque para almacenar el path, y consume un i-nodo además de la entrada en el directorio como el resto.
3. 
		ls /
opendir /
readdir .
readdir ..
readdir caso.txt
readdir quiso.txt
readdir queso.txt
closedir /
		ls –l /
opendir /
readdir .
readdir ..
readdir caso.txt
stats caso.txt
readdir quiso.txt
stats quiso.txt
readdir queso.txt
stats queso.txt
closedir /
4.
		caso.txt
		Leer i-nodo 0 60ms
Leer / 60 ms
Leer i-nodo 1 60 ms
Leer bloque 1 60 ms
		quiso.txt
		Leer i-nodo 0 40µs
Leer / 40µs
Leer i-nodo 1 40µs
Leer bloque 1 40µs
		queso.txt
		Leer i-nodo 0 40µs
Leer / 40µs
Leer i-nodo 2 60 ms
Leer bloque 2 60 ms
Leer i-nodo 0 40µs
Leer / 40µs
Leer i-nodo 1 40µs
Leer bloque 1 40µs
Tarda más al principio porque el acceso a disco es órdenes de magnitud más lento que el acceso a RAM.
5. queso.txt es un enlace simbólico a quiso.txt, luego primero tuvo que existir quiso para que se pudiese ejecutar la orden ln –s.
En cuanto a caso.txt y quiso.txt, deberíamos tener acceso a la fecha de creación. No obstante el orden de creación será el de introducción en el directorio, por lo que parece que primero se creó caso.txt y luego se usó la orden ln para crear quiso.txt.
6. La información de cuantos i-nodos hay está en el superbloque y bastaría restar los ocupados, pero además hay un mapa para indicar cuales están ocupados y cuales libres.
Sistemas Operativos 2001-2002 16 de 16 v 1.2 
ssoo2@arcos.inf.uc3m.es
__MACOSX/coleccion-examenes/2002/septiembre2002/._2002sept_02_web.doc
coleccion-examenes/2002/septiembre2002/exasep2002.doc
UNIVERSIDAD CARLOS III DE MADRID
DEPARTAMENTO DE INFORMÁTICA
Examen de SISTEMAS OPERATIVOS. INGENIERÍA EN INFORMÁTICA. 12-septiembre-2002
Fecha de publicación de las notas: 20-septiembre-2002
 
Fecha de revisión: 23-septiembre-2002 a las 11:30 (laboratorio 2.2B08)
Para la realización del presente examen se dispondrá de 2 horas y media
No se pueden utilizar libros ni apuntes
Ejercicio 1 (4 puntos) Sea el siguiente programa denominado bucle_procesos:
int main (int argc, char **argv) {
 int contador, i, pid;
 contador = atoi(argv[1]);
 i = 0;
 while (i < contador) {
 pid = fork();
 i++;
 } 
a.) Explique qué hace y dibuje un diagrama con la jerarquía de procesos que se origina cuando se ejecuta el mandato bucle_procesos 4.
b.) Explique qué es un proceso zombie y cuándo se producen.
c.) ¿Se generan procesos zombies al ejecutar el mandato anterior? Explique su respuesta.
d.) ¿Qué ocurriría si se ejecutara bucle_procesos 100? Explique la respuesta y modifique el programa para que se solucione el problema existente.
e.) Modifique el programa anterior para que todos los procesos generados puedan compartir el archivo denominado pepe.txt. Explique su solución.
Ejercicio 2 (3 puntos) Sean las dos instrucciones máquina siguientes:
LD R7, A
# Carga en el registro R7 el contenido de la posición de memoria A
SUB B,R7, C
# Resta C a R7 y lo almacena en B. B y C direcciones de memoria
Asumiendo que se ejecutan en un computador con memoria virtual y que cada instrucción y cada operando ocupa una palabra de memoria, conteste a las siguientes preguntas:
a.) ¿Cuántos marcos de página serían necesarios para ejecutar estas instrucciones teniendo en cuenta un modelo de proceso en el que texto y datos están en distintos segmentos? Explique su respuesta. 
b.) ¿Cuántos fallos de página se podrían producir como máximo debidos a la ejecución de las dos instrucciones anteriores? Explique su respuesta.
c.) ¿Qué cambiaría si se usara direccionamiento relativo directo para A, B y C (sumando las direcciones a un registro)? ¿Y si se usara direccionamiento indirecto? 
Ejercicio 3 (3 puntos) El siguiente programa intenta implementar el siguiente mandato: 
dividir f1 f2 f3
Este mandato lee el archivo f1 y crea dos archivos (f2 y f3). En el archivo f2 se escriben los bytes situados en las posiciones pares de f1 y en el archivo f3 los bytes situados en las posiciones impares. Así, si el contenido de f1 es 12121212121212
· El contenido de f2 será 1111111
· El contenido de f3 será 2222222
void main (int argc, char *argv[]) 
{
int fd1, fd2, fd3;
char c;
int size;
int i;
fd1= open(argv[1], O_RDONLY);
fd2= creat(argv[2], 0640);
fd3= creat(argv[3], 0640);
size = lseek(fd1, 0, SEEK_END);
lseek(fd1, 0, SEEK_SET);
if (fork() == 0) {
for ( i = 0; i < size; i = i + 2) {
lseek(fd1, i, SEEK_SET);
read(fd1, &c, 1);
write(fd2, &c, 1);
}
}
else {
for ( i = 1; i < size; i = i + 2) {
lseek(fd1, i, SEEK_SET);
read(fd1, &c, 1);
write(fd3, &c, 1);
}
}
close(fd1);
close(fd2);
close(fd3);
exit(0);
}
Se pide:
a) Suponiendo que el programa es correcto, modifique el programa para que haga un correcto tratamiento de todas las llamadas al sistema.
b) ¿Por qué el programa anterior no consigue el funcionamiento esperado para el mandato dividir? Razone su respuesta.
c) Suponiendo que la implementación sigue utilizando dos procesos, proponga dos modificaciones que resuelvan el problema del apartado b.
__MACOSX/coleccion-examenes/2002/septiembre2002/._exasep2002.doc
coleccion-examenes/2002/septiembre2002/Icon
__MACOSX/coleccion-examenes/2002/septiembre2002/._Icon
__MACOSX/coleccion-examenes/2002/._septiembre2002
__MACOSX/coleccion-examenes/._2002
coleccion-examenes/2003/exa-junio2003.doc
UNIVERSIDAD CARLOS III DE MADRID
DEPARTAMENTO DE INFORMÁTICA
Examen de SISTEMAS OPERATIVOS. INGENIERÍA EN INFORMÁTICA. 
3 de junio de 2003
Fecha de publicación de las notas: 9-junio-2003
 
Fecha de revisión: 12-junio-2003 a las 11:30 (laboratorio 2.2B08)
Para la realización del presente examen se dispondrá de 2 horas y media
No se pueden utilizar libros ni apuntes
Teoría 1. 1 punto
Exponga brevemente las relaciones entre grado de multiprogramación y memoria principal en los casos de sistemas sin memoria virtual y sistemas con memoria
virtual.
Teoría 2. 1 punto
En una máquina que se utiliza como servidor web se ha detectado que el grado de utilización del procesador es del 98%. ¿Qué medidas recomendaría para aumentar el rendimiento global del sistema?
Problema 1. 2,5 puntos
En un determinado sistema operativo los procesos se ejecutan en función de su prioridad. Cuando varios procesos tienen la misma prioridad se utiliza una política FIFO. En la siguiente tabla se especifica para cada proceso, su prioridad, su tiempo de llegada, el tiempo que necesitan para ejecutarse.
		PROCESOS
		PRIORIDAD
		T. DE LLEGADA
		T DE EJECUCIÓN
		P1
		2
		0
		500
		P2
		3
		200
		300
		P3
		1
		300
		400
		P4
		3
		500
		1000
		P5
		2
		700
		600
Se desea calcular:
a) El tiempo que cada proceso se mantiene en espera desde su llegada al sistema hasta que finaliza.
b) El tiempo de retorno de cada proceso (tiempo transcurrido desde que el proceso llega hasta que finaliza su ejecución).
c) El tiempo medio de espera y el tiempo medio de retorno.
Realice estos cálculos para las dos situaciones siguientes:
1. Planificación sin expulsión.
2. Planificación con expulsión.
Problema 2. 2,5 puntos
Una memoria virtual dispone de 9 marcos para programas. En ese momento se está ejecutando el proceso P1, que tiene concedidos 3 marcos y piden memoria los procesos P2 y P3 de 100 Kb y 50 Kb respectivamente. Se realiza un reparto de los marcos libres de forma proporcional al tamaño de los procesos y ambos entran en ejecución. Cuando el proceso P3 demanda por primera vez la página 3 el proceso P1 termina y sus marcos se reparten tren los procesos P2 y P3 de forma proporcional a sus tamaños.
a) Determine cuantos marcos de página corresponden a cada proceso en cada instante.
b) Determine cuantos fallos de página se producen en el proceso P3 si la secuencia de petición de páginas es la siguiente: 
1,2,1,5,2,3,7,6,5,4,3,7,5,6,4,3,2,1,5,4,2,7
Compare los resultados de este apartado para las políticas FIFO y LRU.
Problema 3. 3 puntos
Sea un programa que ejecuta sobre una máquina UNIX y que realiza las siguientes operaciones sobre un determinado fichero: 
        int fd; 
        ... 
        fd = creat( "shared”, 0755 ); 
        ... 
        fork(); 
        fork(); ... 
        /* Padre */ 
                write( fd, "Soy P\n”, 6 ); 
                write( fd, "Adiós\n”, 6 ); 
                exit(1); 
       /* Hijo 1 */ 
                write( fd, "Soy H1\n”, 7 ); 
                lseek( fdm 1024, SEEK_CUR ); /* Desde posición actual */ 
                exit(1); 
       /* Hijo 2 */ 
                write( fd, "Soy H2\n”, 7 ); 
                exit(1);
Conteste a las siguientes preguntas: 
a) ¿Cuál sería el tamaño final del fichero? ¿Sería distinto si el lseek se realizara en último lugar? 
b) ¿Cuál sería el contenido final del fichero (examine las diferentes posibilidades)?
c) ¿Qué estructuras de datos permiten relacionar los descriptores de fichero de los procesos con los nodos-i? Dibuje claramente estas estructuras reflejando los tres procesos y el fichero del ejemplo. 
coleccion-examenes/2003/Icon
__MACOSX/coleccion-examenes/2003/._Icon
coleccion-examenes/2003/sol-junio2003.doc
UNIVERSIDAD CARLOS III DE MADRID
DEPARTAMENTO DE INFORMÁTICA
Examen de SISTEMAS OPERATIVOS. INGENIERÍA EN INFORMÁTICA. 
3 de junio de 2003
Fecha de publicación de las notas: 9-junio-2003
 
Fecha de revisión: 12-junio-2003 a las 11:30 (laboratorio 2.2B08)
Para la realización del presente examen se dispondrá de 2 horas y media.
No se pueden utilizar libros ni apuntes.
Debe contestar cada ejercicio en hojas separadas, numeradas de forma independiente.
Teoría 1. [1 punto]
Exponga brevemente las relaciones entre grado de multiprogramación y memoria principal en los casos de sistemas sin memoria virtual y sistemas con memoria virtual.
Sección 3.2.3 del libro de texto (página 82)
Teoría 2. [1 punto]
En una máquina que se utiliza como servidor web se ha detectado que el grado de utilización del procesador es del 98%. ¿Qué medidas recomendaría para aumentar el rendimiento global del sistema?
En presencia de memoria virtual un rendimiento del procesador cercano al 100% indica que no se está produciendo hiperpaginación. De hecho, el sistema podría albergar más procesos en memoria, por lo que un incremento de memoria no incrementaría el rendimiento del sistema.
La medida más aconsejable es sustituir el procesador por otro de mayor velocidad o bien incrementar el número de procesadores (si es posible).
Problema 1. [2,5 puntos]
En un determinado sistema operativo los procesos se ejecutan en función de su prioridad. Cuando varios procesos tienen la misma prioridad se utiliza una política FIFO. En la siguiente tabla se especifica para cada proceso, su prioridad, su tiempo de llegada, el tiempo que necesitan para ejecutarse.
		PROCESOS
		PRIORIDAD
		T. DE LLEGADA
		T DE EJECUCIÓN
		P1
		2
		0
		500
		P2
		3
		200
		300
		P3
		1
		300
		400
		P4
		3
		500
		1000
		P5
		2
		700
		600
Se desea calcular:
a) El tiempo que cada proceso se mantiene en espera desde su llegada al sistema hasta que finaliza. 
b) El tiempo de retorno de cada proceso (tiempo transcurrido desde que el proceso llega hasta que finaliza su ejecución). 
c) El tiempo medio de espera y el tiempo medio de retorno.
Realice estos cálculos para las dos situaciones siguientes:
1. Planificación sin expulsión.
2. Planificación con expulsión.
En el caso de planificación sin expulsión una vez que un proceso adquiere la CPU no la libera hasta que no ha finalizado su ejecución. La traza de la ejecución sería:
		T
		P1
		P2
		P3
		P4
		P5
		
		Cons.
		Pend.
		Cons.
		Pend.
		Cons.
		Pend.
		Cons.
		Pend.
		Cons.
		Pend.
		0
		0
		500
		0
		0
		0
		0
		0
		0
		0
		0
		200
		200
		300
		0
		300
		0
		0
		0
		0
		0
		0
		300
		300
		200
		0
		300
		0
		400
		0
		0
		0
		0
		500
		500
		0
		0
		300
		0
		400
		0
		1000
		0
		0
		700
		500
		0
		0
		300
		200
		200
		0
		1000
		0
		600
		900
		500
		0
		0
		300
		400
		0
		0
		1000
		0
		600
		1500
		500
		0
		0
		300
		400
		0
		0
		1000
		600
		0
		1800
		500
		0
		300
		0
		400
		0
		0
		1000
		600
		0
		2800
		500
		0
		300
		0
		400
		0
		1000
		0
		600
		0
Para determinar el tiempo de retorno habrá que restar el momento en que el proceso ha terminado del momento en el que el proceso se ha iniciado:
inicio
fin
retorno
T
T
T
-
=
Para determinar el tiempo de espera habrá que deducir del tiempo de retorno el tiempo que efectivamente el proceso ha pasado en ejecución:
ejecucion
retorno
espera
T
T
T
-
=
		Proceso
		Tiempo de retorno
		Tiempo de espera
		P1
		500 – 0 = 500
		500 – 500 = 0
		P2
		1800 – 200 = 1600
		1600 – 300 = 1300
		P3
		900 – 300 = 600
		600 – 400 = 200
		P4
		2800 – 500 = 2300
		2300 – 1000 = 1300
		P5
		1500 – 700 = 800
		800 – 600 = 200
		Media
		5800/5 = 1160
		3000/5 = 600
En el caso de planificación con expulsión un proceso liberará la CPU si llega a la cola de procesos otro proceso con mayor prioridad.
La traza de ejecución sería:
		T
		P1
		P2
		P3
		P4
		P5
		
		Cons.
		Pend.
		Cons.
		Pend.
		Cons.
		Pend.
		Cons.
		Pend.
		Cons.
		Pend.
		0
		0
		500
		0
		0
		0
		0
		0
		0
		0
		0
		200
		200
		300
		0
		300
		0
		0
		0
		0
		0
		0
		300
		300
		200
		0
		300
		0
		400
		0
		0
		0
		0
		500
		300
		200
		0
		300
		200
		200
		0
		1000
		0
		0
		700
		300
		200
		0
		300
		400
		0
		0
		1000
		0
		600
		900
		500
		0
		0
		300
		400
		0
		0
		1000
		0
		600
		1500
		500
		0
		0
		300
		400
		0
		0
		1000
		600
		0
		1800
		500
		0
300
		0
		400
		0
		0
		1000
		600
		0
		2800
		500
		0
		300
		0
		400
		0
		1000
		0
		600
		0
Los tiempos de retorno y de espera para cada proceso serán:
		Proceso
		Tiempo de retorno
		Tiempo de espera
		P1
		900 – 0 = 900
		900 – 500 = 400
		P2
		1800 – 200 = 1600
		1600 – 300 = 1300
		P3
		700 – 300 = 400
		400 – 400 = 0
		P4
		2800 – 500 = 2300
		2300 – 1000 = 1300
		P5
		1500 – 700 = 800
		800 – 600 = 200
		Media
		6000/5 = 1200
		3200 / 5 = 640
Problema 2. [2,5 puntos]
Una memoria virtual dispone de 9 marcos para programas. En ese momento se está ejecutando el proceso P1, que tiene concedidos 3 marcos y piden memoria los procesos P2 y P3 de 100 Kb y 50 Kb respectivamente. Se realiza un reparto de los marcos libres de forma proporcional al tamaño de los procesos y ambos entran en ejecución. Cuando el proceso P3 demanda por primera vez la página 3 el proceso P1 termina y sus marcos se reparten tren los procesos P2 y P3 de forma proporcional a sus tamaños.
a) Determine cuantos marcos de página corresponden a cada proceso en cada instante.
b) Determine cuantos fallos de página se producen en el proceso P3 si la secuencia de petición de páginas es la siguiente: 
1,2,1,5,2,3,7,6,5,4,3,7,5,6,4,3,2,1,5,4,2,7
Compare los resultados de este apartado para las políticas FIFO y LRU. 
a) Cuando los procesos P2 y P3 piden memoria el número de marcos libres es 6 pues 3 marcos están asignados al proceso P1. Como el reparto es proporcional al tamaño de los procesos, se tendrá
		Proceso
		Tamaño
		Factor
		Marcos asignados
		P2
		100
		100/150 = 0,67
		0,67 * 6 = 4,02 = 4
		P3
		50
		50/150 = 0,33
		0,33 * 6 = 1,98 = 2
Cuando el proceso P1 termina se reparten sus 3 marcos entre los procesos P2 y P3.
		Proceso
		Factor
		Nuevos Marcos
		Total Marcos
		P2
		0,67
		0,67 * 3 = 2,01 = 2
		6
		P3
		0,33
		0,33 * 3 = 0,99 = 1
		3
b) La secuencia de peticiones del proceso P3 se puede dividir en dos partes. La primera parte está formada por la secuencia de peticiones anteriores a la primera petición de la página 3, ya que durante este periodo P3 tiene asignados 2 marcos de página. La segunda parte está formada por el resto de la secuencia y durante este tiempo el proceso P3 tiene asignados 3 marcos de página.
Si se aplica la política FIFO se tiene:
		Referencia
		1
		2
		1
		5
		2
		M1
		1
		1
		1
		5
		5
		M2
		-
		2
		2
		2
		2
		Fallo
		*
		*
		
		*
		
Y cuando se adquiere el tercer fallo de página:
		Referencia
		3
		7
		6
		5
		4
		3
		7
		5
		6
		4
		3
		M1
		5
		5
		6
		6
		6
		3
		3
		3
		6
		6
		6
		M2
		2
		7
		7
		7
		4
		4
		4
		5
		5
		5
		3
		M3
		3
		3
		3
		5
		5
		5
		7
		7
		7
		4
		4
		Fallo
		*
		*
		*
		*
		*
		*
		*
		*
		*
		*
		*
		Referencia
		2
		1
		5
		4
		2
		7
		M1
		2
		2
		2
		4
		4
		4
		M2
		3
		3
		5
		5
		5
		7
		M3
		4
		1
		1
		1
		2
		2
		Fallo
		*
		*
		*
		*
		*
		*
Así el número de fallos con política FIFO es de 20.
Si se aplica LRU:
		Referencia
		1
		2
		1
		5
		2
		M1
		1+
		1
		1+
		1
		2+
		M2
		-
		2+
		2
		5+
		5
		Fallo
		*
		*
		
		*
		*
Y cuando se adquiere el tercer fallo de página:
		Referencia
		3
		7
		6
		5
		4
		3
		7
		5
		6
		4
		3
		M1
		2
		2
		6+
		6
		6
		3+
		3
		3
		6+
		6
		6
		M2
		5
		7+
		7
		7
		4+
		4
		4
		5+
		5
		5
		3+
		M3
		3+
		3
		3
		5+
		5
		5
		7+
		7
		7
		4+
		4
		Fallo
		*
		*
		*
		*
		*
		*
		*
		*
		*
		*
		*
		Referencia
		2
		1
		5
		4
		2
		7
		M1
		2+
		2
		2
		4+
		4
		4
		M2
		3
		3
		5+
		5
		5
		7+
		M3
		4
		1+
		1
		1
		2
		2
		Fallo
		*
		*
		*
		*
		*
		*
Así el número de fallos con política LRU es de 21.
Problema 3. [3 puntos]
Sea un programa que ejecuta sobre una máquina UNIX y que realiza las siguientes operaciones sobre un determinado fichero: 
        int fd; 
        ... 
        fd = creat( "shared”, 0755 ); 
        ... 
        fork(); 
        fork(); ... 
        /* Padre */ 
                write( fd, "Soy P\n”, 6 ); 
                write( fd, "Adiós\n”, 6 ); 
                exit(1); 
       /* Hijo 1 */ 
                write( fd, "Soy H1\n”, 7 ); 
                lseek( fd, 1024, SEEK_CUR ); /* Desde posición actual */ 
                exit(1); 
       /* Hijo 2 */ 
                write( fd, "Soy H2\n”, 7 ); 
                exit(1);
Conteste a las siguientes preguntas: 
a) ¿Cuál sería el tamaño final del fichero? ¿Sería distinto si el lseek se realizara en último lugar?
b) ¿Cuál sería el contenido final del fichero (examine las diferentes posibilidades)?
c) ¿Qué estructuras de datos permiten relacionar los descriptores de fichero de los procesos con los nodos-i? Dibuje claramente estas estructuras reflejando los tres procesos y el fichero del ejemplo.
a) El tamaño del fichero depende del orden relativo de ejecución de las operaciones entre los distintos procesos.
Tamaños posibles son: 26, 1024
Si el lseek se realiza en último lugar el tamaño sería 26 porque lseek solamente cambia el valor del puntero, pero el tamaño del archivo no se modifica hasta que no se realiza una escritura.
b) Existen diversas posibilidades en cuanto al contenido del archivo. Las cinco operaciones sobre el archivo se pueden ejecutar en cualquier orden que cumpla las siguientes restricciones.
La sentencia:
write( fd, "Soy P\n”, 6 ); 
debe ejecutarse antes que la sentencia:
write( fd, "Adiós\n”, 6 ); 
Además, la sentencia:
write( fd, "Soy H1\n”, 7 ); 
debe ejecutarse antes que la sentencia:
lseek( fd 1024, SEEK_CUR ); /* Desde posición actual */ 
Como ejemplo se muestran a continuación dos posibilidades.
Posibilidad 1:
Soy P
Adiós
Soy H2
Soy H1
<eof>
Posibilidad 2:
Soy P
Adiós
Soy H1
<1024 bytes a 0>
Soy H2
<eof>
c) Dentro del BCP (bloque de control de procesos) cada proceso mantiene una tabla con los descriptores de los archivos abiertos. Cada entrada apunta a una entrada de la tabla de archivos donde se almacena el puntero al nodo-i y la posición dentro del archivo.
Tabla de archivos 
abiertos. Padre
0
1
2
3
4
fd
Tabla de archivos 
abiertos. H2
0
1
2
3
4
fd
Tabla de archivos 
abiertos. H1
0
1
2
3
4
fd
Tabla intermedia 
de nodos-i y posiciones
Tabla de 
nodos-i
Nodo-i
Posición
_1116065270.unknown
_1116080554.unknown
_1116065177.unknown
coleccion-examenes/2003/sol-sep-2003.doc
UNIVERSIDAD CARLOS III DE MADRID
DEPARTAMENTO DE INFORMÁTICA
Examen de SISTEMAS OPERATIVOS. INGENIERÍA EN INFORMÁTICA. 
11 de septiembre de 2003. 9:30.
Fecha de publicación de las notas: 19-septiembre-2003
 
Fecha de revisión: 22-septiembre-2003 a las 15:30 (laboratorio 2.2B08)
Para la realización del presente examen se dispondrá de 2 horas y media
No se pueden utilizar libros ni apuntes
Teoría 1. (1 punto).
Describa el ciclo de vida de un proceso y los estados que puede atravesar durante el mismo. Dibuje el grafo de los mismos.
Teoría 2. (1 punto).
Describa la estructura de un archivo en UNIX. 
Problema 1. (2 puntos)
Escriba un programa en C que cree un proceso padre que genere 10 hijos y espere por todos. Cuando todos los hijos hayan terminado, el padre debe terminar la ejecución. Todos los procesos hijo son iguales: arrancan y se duermen una cantidad de tiempo aleatoria entre 1 y 10 segundos. 
Nota: La función rand() devuelve un número aleatorio entre 0 y el entero mayor. Úsela para calcular el tiempo a dormir.
#include <stdio.h>
void hijo(int t) {
 sleep(t);
}
int main() {
 const int MAX_PROC = 10;
 int i, pid, estado, tiempo;
 int pids[MAX_PROC];
 for (i=0;i<MAX_PROC;i++) {
 tiempo
= rand() % 10 + 1;
 pid = fork();
 switch (pid) {
 case -1: /* error en fork */
 fprintf(stderr, "Error en la creación de proceso hijo\n");
 exit(-1);
 case 0: /* proceso hijo */
 hijo(tiempo);
 printf("proceso %d finalizado\n", i);
 exit(0);
 default: /* proceso padre */
 pids[i] = pid;
 break;
 }
 }
 for (i=0;i<MAX_PROC;i++) {
 waitpid(pids[i], &estado, 0);
 printf("Proceso %d esperado\n", i);
 }
 return 0;
}
Problema 2. (3 puntos)
Sea un sistema de memoria virtual sin preasignación de swap y que usa la técnica del almacenamiento intermedio (buffering) de páginas. En dicho sistema se pretenden estudiar los distintos estados por los que va pasando una página de un proceso durante la ejecución del mismo, dependiendo del segmento al que pertenezca la página. Para ello vamos a considerar como estado de una página en un determinado momento, el lugar de donde la obtendría el proceso al accederla en ese instante. Se distinguen, por lo tanto, los siguientes estados: 
· Del fichero (F). 
· De la memoria principal asignada al proceso (P). 
· De la lista de páginas modificadas (M) (almacenamiento intermedio). 
· De la lista de páginas libres (L) (almacenamiento intermedio). 
· Del dispositivo de swap (S). 
Asimismo, para analizar las transiciones entre estados, se considerarán, al menos, los siguientes eventos: 
· Fallo de página (F). 
· Extracción (XT): se le quita la página al proceso pasando el marco al almacenamiento intermedio. 
· Expulsión (XP): se elimina la página de la memoria principal liberando el marco. 
· Escritura de la página al dispositivo o fichero (W) permaneciendo en el almacenamiento intermedio. 
Por último, las transiciones entre estados, además de estar dirigidas por estos eventos, podrán depender de condiciones tales como que la página haya sido modificada o no. 
Se pide dibujar, para los tipos de páginas que se plantean a continuación, el diagrama de estados que muestra todos los estados en los que puede estar una página, indicando con flechas los eventos y/o condiciones que producen las transiciones. En cada caso, se usarán los estados y eventos que sean pertinentes, y se explicarán los aspectos más relevantes de cada diagrama identificando cuando se producen operaciones de acceso al disco. 
a) Una página de código. 
b) Una página de datos con valor inicial. ¿Se podrían servir del fichero ejecutable sucesivos fallos asociados a una misma página de este tipo? 
c) Una página de datos sin valor inicial. Una de las situaciones que se debe considerar es el caso de una página de este tipo que se accede por primera vez con una lectura y que se expulsa sin haber realizado más accesos sobre la misma. 
Solución 
a) Las páginas de código no se modifican por lo que nunca pasarán a la lista de páginas modificadas del almacenamiento intermedio. Además, debido a ello, no se almacenarán en el dispositivo de swap sino que los fallos de página se servirán directamente del fichero ejecutable. El diagrama de estados correspondiente a una página de código sería el siguiente: 
Donde las transiciones se corresponden con los siguientes eventos e implican las siguientes operaciones: 
1.    Evento F: Se trae la página del ejecutable (F) a memoria principal (P). Se produce un acceso de lectura al fichero ejecutable. 
2.    Evento XT: El algoritmo de reemplazo le quita la página al proceso pasándola al almacenamiento intermedio. Puesto que las páginas de código no se modifican, pasará a la lista de páginas libres (L). 
3.    Evento F:  Se recupera la página de la lista de páginas libres del almacenamiento intermedio (L). Gracias a la técnica del almacenamiento intermedio se ha podido servir un fallo de página sin realizar operaciones de E/S al disco. 
4.    Evento XP:  Se elimina la página del almacenamiento intermedio liberando el marco para que pueda usarse para otra página. Se transita al estado F ya que el siguiente fallo de página deberá servirse del fichero ejecutable. 
b) Una página de datos con valor inicial se servirá la primera vez desde el ejecutable y posteriormente desde el dispositivo de swap , ya que las modificaciones que se produzcan sobre la página no deben reflejarse en el fichero ejecutable. En realidad, se podrían servir del ejecutable varios fallos asociados a una misma página de este tipo mientras que dicha página no haya sido modificada conservando el mismo contenido inicial. El diagrama de estados correspondiente a una página de este tipo sería el siguiente: 
Donde las transiciones se corresponden con los siguientes eventos e implican las siguientes operaciones: 
1.    Evento F: Se trae la página del ejecutable (F) a memoria principal (P). Se produce un acceso de lectura al fichero ejecutable. 
2.    Evento XT y la página no se ha modificado (bit M igual a 0): El algoritmo de reemplazo le quita la página al proceso pasándola a la lista de páginas libres (L). 
3.    Evento F:  Se recupera la página de la lista de páginas libres del almacenamiento intermedio (L). 
4.    Evento XT y la página se ha modificado (bit M igual a 1): El algoritmo de reemplazo le quita la página al proceso pasándola a la lista de páginas modificadas (M). 
5.    Evento F:  Se recupera la página de la lista de páginas modificadas del almacenamiento intermedio (M). 
6.    Evento W: Las páginas que están en la lista de modificadas se van escribiendo de forma agrupada al swap. Este evento indica que ha finalizado la operación de escritura en el disco de una determinada página y que, por lo tanto, debe pasar a la lista de páginas libres (L). Nótese que, al tratarse de un sistema sin preasignación de swap, la primera vez que se produzca esta situación, no habrá una copia en el disco para esa página por lo que en ese momento habrá que reservar espacio para la misma. 
7.    Evento XP y hay copia en swap de la página:  Se elimina la página del almacenamiento intermedio liberando el marco para que pueda usarse para otra página. Se transita al estado S ya que el siguiente fallo de página deberá servirse de la copia en el dispositivo de swap. Nótese que en este momento no hay que escribir sobre la copia en swap ya que dicha copia se actualizó cuando esta página pasó por la lista de páginas modificadas (M). 
8.    Evento F: Se trae la página del dispositivo de swap (S) a memoria principal (P). Se produce un acceso de lectura a dicho dispositivo. 
9.    Evento XP y no hay copia en swap de la página: La no existencia de una copia de la página en swap indica que la página no se ha modificado y, por lo tanto, su contenido es idéntico al inicial por lo que el siguiente fallo de página podría servirse del ejecutable. Esta transición implica la eliminación de la página del almacenamiento intermedio y el cambio al estado F. 
c) Una página que pertenece a la región de datos sin valor inicial  no está almacenada en el ejecutable. Únicamente aparece en la cabecera del mismo el tamaño de dicha región. Cuando se produce el primer fallo de página, se busca un marco libre y, por razones de confidencialidad de la información, se rellena con ceros. En el caso de que dicha página rellena con ceros sea expulsada sin modificarse (situación poco probable pero posible), habría que reservarla espacio de swap puesto que necesita un lugar para almacenarse al no estar incluida en el ejecutable.  El diagrama resultante sería muy similar al del apartado anterior y presentaría el siguiente aspecto: 
Donde las transiciones se corresponden con los siguientes eventos e implican las siguientes operaciones: 
1.    Evento F: Se busca un marco libre en memoria principal (P) y se rellena con ceros. 
2.    Evento XT y la página no se ha modificado (bit M igual a 0): El algoritmo de reemplazo le quita la página al proceso pasándola a la lista de páginas libres (L). 
3.    Evento F:  Se recupera la página de la lista de páginas libres del almacenamiento intermedio (L). 
4.