FINALsep2005

Vista previa del material en texto

Ingeniería en Informática		Examen de septiembre de 2005
Sistemas Operativos 2004-2005		
Examen de SISTEMAS OPERATIVOS. 
XX de septiembre de 2005. X:XX.
Fecha de publicación de las notas: XX-septiembre-2005	 
Fecha de revisión: XX-septiembre-2005 a las XX:XX (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 (2,5 puntos). Dado el siguiente código se pide responder a los siguientes apartados de forma razonada:
	¿Cuál es la salida por pantalla del programa?¿Cuantos procesos se crean?
NOTA: Dibuje un esquema de los procesos para facilitar la labor.
	Si MAX_COUNT=100 razone cual debería ser la salida por pantalla (sin escribir dicha salida). ¿Cuántos procesos se crearían?
	¿Cuál es el problema que resuelve este programa?
	¿Este programa finaliza o ejecuta por siempre? ¿Qué sentido tiene la función sleep?
#define MAX_COUNT 10
int main(void) {
int ret,i,fd[2];
 
pipe(fd);
ret=fork();
if(0==ret) {
 funcion(fd[0]); 
} 
for(i=2;i<=MAX_COUNT;i++ ) {
 write(fd[1],&i,sizeof(int));
}
sleep(5);
}
void funcion (int fIn) {
int ret,i,dat,fd[2];
read(fIn,&dat,sizeof(int)); 
printf(“num: %d\n“,dat);
pipe(fd);
ret=fork();
if(0==ret) {
 funcion(fd[0]); 
} 
while(1) {
 read(fIn,&i,sizeof(int)); 
 if (0 != (i % dat)) { 
 write(fd[1],&i,sizeof(int));
 }
}
}
Ejercicicio 2 (2,5 puntos).
	Usando pseudocódigo e indicando que estructuras del sistema de ficheros y el recorrido a través de los i-nodos: Implementar la funcion inodo_t iname (char * nombre), que, dada una ruta pasada por argumento devuelve el inodo perteneciente a esa ruta. En caso de que no exista esa ruta ó sea incorrecta se deberá devolver la constate ERROR. (1,25 puntos)
	Usando la funcion anterior, implementar la llamada al sistema int link(char *nombre1, char *nombre2) crea un enlace duro (hard link) entre el fichero existente nombre1 y el nuevo apelativo nombre2. Describir en pseudo-código el trabajo del sistema operativo para dar cumplimiento a la llamada link. (1,25 puntos)
Ejercicicio 3 (2,5 puntos). Disponemos de un ordenador que cuenta con las siguientes características, posee una memoria RAM de 64Kbytes, permite usar memoria virtual paginada, con páginas de 8Kbyte de tamaño cada una. El sistema operativo debe estar siempre en memoria y ocupa 16Kbytes. Además el sistema dispone de una memoria swap con preasignación de 128 Kbytes. Con estos datos responda razonadamente a los siguientes apartados:
	¿Cual es el tamaño máximo del espacio lógico de un proceso? ¿Cuál es el tamaño máximo de memoria efectiva que puede disponer un único proceso?
	¿Cuántos bits componen la dirección de memoria física? ¿de que campos se compone y de cuantos bits es cada campo?
	Supongamos que se crea un proceso P1 de 32Kbytes el cual se almacena completamente en RAM, A continuación se crea un proceso P2 de 48 Kbytes el cual se guarda parte en RAM y parte en swap (las direcciones bajas en RAM y las altas en swap). 
A partir de este escenario describa los pasos que realiza el SSOO y el hardware si el proceso P2 solicita la escritura de un bloque de datos de 8Kbytes empezando en la dirección virtual 10240.
NOTA: Se recomienda dibujar un esquema del estado de la memoria RAM y la swap para mayor claridad.
	¿Qué problemas pueden surgir si después de creados P1 y P2 se crea un nuevo proceso P3 de 64Kbytes? ¿Qué solución debería tomar el SSOO en ese caso?
Ejercicicio 4 (2,5 puntos). Se dispone de dos caminos que separan dos sentidos de circulación: Norte y Sur. Ambos caminos convergen en uno solo cuando se trata de cruzar un río. Existen coches que quieren pasar de norte a sur, y de sur a norte. En cualquier momento, sólo pueden atravesar el puente uno o más coches que vayan en el mismo sentido (no se mezclan coches que van en sentidos opuestos).
Implementar una solución mediante semáforos. Explicar si la solución que se propone esta libre de inanición para la circulación de coches en alguno de los dos sentidos.
SOLUCIÓN:
Ejercicio 1: 
1.-
Esquema que muestra la ejecución del programa y los procesos creados
main
F1
F2
F3
F4
F5
fork()
Envia
del
2 al 10
pipe
Leer Nº
num:2
fork()
Envía
los num.
leidos NO
divisibles
entre 2
pipe
Leer Nº
num:3
fork()
Envía
los num.
leidos NO
divisibles
entre 3
pipe
Leer Nº
num:5
fork()
Envía
los num.
leidos NO
divisibles
entre 5
pipe
Leer Nº
num:7
fork()
Envía
los num.
leidos NO
divisibles
entre 7
pipe
Leer Nº
10,9,8,7,6,5,4,3,2
9,7,5,3
7,5
7
 
 La salida por pantalla corresponde con las líneas que escriben los procesos F1, F2, F3 y F4 por tanto la salida será la siguiente: 
num: 2
num: 3
num: 5
num: 7
El numero de procesos creados son 6, 1 del programa principal. 4 que muestran líneas por pantalla y 1 que espera en vano por un número.
2.-
Como se puede ver el programa genera un línea por cada número primo que haya entre 2 y el valor de MAX_COUNT luego la salida para MAX_COUNT=100 se construiría de la siguiente forma:
	num: 2
	………
num: X (siendo X un numero primo entre 2 y 100)
El número de procesos creados será el de números primos que haya entre 2 y 100 y dos mas (el del programa principal y el que espera el último número sin recibirlo).
3.- 
Este programa calcula los números primos que haya entre 2 y el valor de MAX_COUNT.
4.-
El programa termina cuando finalice el primer proceso. El resto de procesos normalmente deberá morir al finalizar su padre, (aunque en algunos sistemas esto no ocurre ya que están configurados de esa forma). El sleep esta puesto para que el programa no termine antes de que finalice la impresión de los valores primos por parte del resto de procesos, si no podría ocurrir que el programa finalice antes de terminar la impresión
Ejercicio 2:
1.-.
inodo_t namei(*char nombre)
{
if (nombre es ruta absoluta)
iaux = inodo del directorio raíz, /;
else
iaux = inodo del directorio actual de trabajo;
while (haya mas componentes en la ruta nombre) {
tomar el siguiente componente de nombre, comp;
if (el inodo iaux no corresponde a un directorio) return(error);
if (el inodo iaux no tiene permiso x de búsqueda) return(error);
buscar el nombre comp en el directorio correspondiente a iaux. //comparaciones con las entradas válidas (pares /nombre,inodo/) hasta localizar comp.
if (comp coincide con alguna entrada del directorio) {
obtener su número de inodo;
comprobar si hay que proceder a un cruce de punto de montaje;
iaux = número de inodo de comp;
} else
return(no hay inodo);
}
return(iaux);
}
2.-
int link(char *nombre1, char *nombre2)
{
inodo1 = namei(nombre1) //Obtener el inodo1 correspondiente al fichero nombre1 [namei];
if ( el campo link de inodo1 es superior a LINK_MAX /* demasiados enlaces */o es un directorio y el uid del proceso no es root){
return(error);
	}
inodo1 = namei(nombre2) // obtener el inodo2 del directorio que contiene el último componente de nombre2 [namei]
if (nombre2 ya existe o pertenece a un sistema de ficheros – volumen – distinto o uid-proceso no tiene permiso de escritura en el directorio inodo2){
return(error);
	}
escribe una nueva entrada en el directorio inodo2 con el par /nombre2:t,inodo1/
incrementa en 1 el campo link de inodo1;
modifica el campo fecha de modificación de inodo del inodo1;
Return(éxito)
}
Ejercicio 3:
1.-
El tamaño máximo del espacio lógico de un proceso depende del tamaño de la dirección virtual, ya que no se conoce ese dato, no se puede calcular este tamaño máximo.
El tamaño máximo de memoria efectiva que puede disponer un único proceso será la memoria RAM disponible para procesos más lo que se pueda añadir de swap. La memoria RAM disponible sera el total menos el reservado para el SSOO (64-16 = 48 Kbytes) en cuanto a la swap ya que es con preasignación primero habrá que contar con la swap que se asigna a las paginas en memoria y el resto será memoria extra, (128 – 48 = 80 Kbytes) Así el maximo de memoria efectiva será (48+80=128Kbytes)
2.-
Dado que la memoriaRAM es de 64 Kbytes (=216) la dirección física será de 16 bits.
Como las paginas son de 8 Kbytes(=213) los bits de la dirección para el desplazamiento dentreo de la página seran 13 bits y el resto para distinguir la página (16-13 = 3 bits)
3 bits
13 bits
N º Page
Offset
3.-
Esquema de la memoria antes de la escritura
Pag. Mem.
Pag. Swap
P100
Reserv (P100) 
P204
P101
Reserv (P101)
P205
P102
Reserv (P102)
P103
Reserv (P103)
P200
Reserv (P200)
P201
Reserv (P201)
SSOO
P202
SSOO
P203
Bloque a escribir (8Kbytes) desde 10240 hasta (10240+8196= 18436)
10240 / 8196 = 1,249 => Pagina 01
18436 / 8196 = 2,249 => Pagina 02
La escritura implica desde la pagina P201 hasta la pagina P202
En primer lugar para escribir en la pagina P201 la MMU traducirá las direcciones virtuales y obtendrá en la tabla de paginas del proceso P2 la entrada correspondiente con la pagina 01. Como esa pagina esta en memoria la MMU realizara la traducción de direcciones y realizara las escrituras en memoria sin ningún problema (la pagina P201 quedaría modificada).
En el momento en que se intente escribir en la primera dirección perteneciente a la pagina P202 la MMU traducirá las direcciones virtuales y obtendrá en la tabla de paginas del proceso P2 la entrada correspondiente con la pagina 02. Como esta pagina no esta en memoria se producirá una excepción de memoria y se ejecutara el código del SSOO asociado con esa excepción. 
El SSOO buscara en la tabla de paginas dicha pagina y comprobará que esta almacenada en swap. Para traerla a memoria es necesario seleccionar una pagina de memoria a sustituir según el algoritmo que tenga asignado (Ej. P100) Dicha pagina deberá ser copiada a swap (si no estaba ya o ha sido modificada) y en su lugar se copiará la pagina solicitada.
Esquema de la memoria después de la escritura
Pag. Mem.
Pag. Swap
P202
P100
P204
P101
Reserv (P101)
P205
P102
Reserv (P102)
P103
Reserv (P103)
P200
Reserv (P200)
P201
Reserv (P201)
SSOO
Reserv(P202)
SSOO
P203
4.-
 P1 +P2 +P3 = 32K + 48K + 64K = 144K mayor que la memoria efectiva (128K)
La solución es que el SSOO impida la creación del nuevo proceso P3 (Error de memoria).
Ejercicio 4:
#include <pthread.h>
#include <semaphore.h>
// Variables compartidas. 
sem_t turno,libre; /* Necesarios para fijar el sen-*/
 /* tido de paso. */
sem_t mutex1; /* Exclusión mutua en el acceso */
 /* a la variable “norte”. */
sem_t mutex2; /* Ídem para la variable “sur”. */
int norte=0; /* Nº de vehículos en dirección */
 /* norte-->sur. */
int sur=0; /* Nº de vehículos en dirección */
 /* sur-->norte. */
void pasar_puente(void) {}
/ Hilo que representa a un vehículo en sentido N-->S */
void *norte_sur(void *arg) {
 sem_wait(&turno); /* Exclusión mutua a la hora de */
 /* pedir el paso. */
 sem_wait(&mutex1); /* S.C. para acceder a “norte”. */
 norte++;
 if (norte==1) /* El primer vehículo del norte */
 sem_wait(&libre); /* no deja pasar a los del sur. */
 sem_post(&mutex1); /* Fin de la S.C. de “norte”. */
 sem_post(&turno); /* Otro hilo podrá pedir paso. */
 pasar_puente(); /* Proceder a cruzar. */
 sem_wait(&mutex1); /* S.C. para acceder a “norte”. */
 norte--;
 if (norte==0) /* Si es el último, permite que */
 sem_post(&libre); /* los del sur pasen. */
 sem_post(&mutex1); /* Fin de la S.C. de “norte”. */
}
// Hilo que representa a un vehículo en sentido S-->N 
void *sur_norte(void *arg) {
 sem_wait(&turno); /* Exclusión mutua a la hora de */
 /* pedir el paso. */
 sem_wait(&mutex2); /* S.C. para acceder a “sur”. */
 sur++;
 if (sur==1) /* El primer vehículo del sur no*/
 sem_wait(&libre); /* deja pasar a los del norte. */
 sem_post(&mutex2); /* Fin de la S.C. de “sur”. */
 sem_post(&turno) ; /* Otro hilo podrá pedir paso. */
 
 pasar_puente(); /* Proceder a cruzar. */
 sem_wait(&mutex2); /* S.C. para acceder a “sur”. */
 sur--;
 if (sur==0) /* Si es el último, permite que */
 sem_post(&libre); /* los del norte pasen. */
 sem_post(&mutex2); /* Fin de la S.C. de “sur”. */
}
main (){
....
 sem_init(&turno, 0, 1); 
 sem_init(&libre, 0, 1); 
 sem_init(&mutex1, 0, 1); 
 sem_init(&mutex2, 0, 1); 
....
}