Examenes de FSO de varios años resueltos PDF

Preview

Summary

Nombre TitulaciónIMPORTANTE : Las seis preguntas suman 12 puntos. Usted deberá descartar al menos UNA de las preguntas 3, 4, 5 y 6. E s decir, usted puede optar por contestar estos grupos de preguntas: 12345, 12346, 12356, 12456. No se admitirá ninguna otra combinación.Dispone de tres horas y media ...

Description

Calificación

Universidad de Las Palmas de Gran Canaria Facultad de Informática Sistemas Operativos Convocatoria de junio, 26 de junio de 2002

1 2 3 4 5 6

SOLUCI ONES Nombre

Titulación

IMPORTANTE : Las seis preguntas suman 12 puntos. Usted deberá descartar al menos UNA de las preguntas 3, 4, 5 y 6. Es decir, usted puede optar por contestar estos grupos de preguntas: 12345, 12346, 12356, 12456. No se admitirá ninguna otra combinación. Dispone de tres horas y media para completar el examen.

1 (2 puntos)

- Responda, justificando sus respuestas, a las siguientes cuestiones sobre

Nachos: A. La ejecución de la función Yi e l d( ) , ¿provoca siempre el cambio de estado del hilo que la invoca? No. Sólo provoca un cambio de estado (de RUN a READY) si la cola de hilos en estado READY no está vacía. B. ¿Cómo está estructurado internamente un fichero que contiene un programa de usuario ejecutable de Nachos? Contiene tres partes. Primero un bloque cabecera que describe como están estructuradas las dos bloques que le siguen que son: bloque de código y bloque de datos con valores iniciales. El bloque cabecera dice que tamaño y dónde empieza en el archivo cada uno de estos bloques. C. ¿Por qué debemos utilizar un compilador cruzado para compilar un programa de usuario de Nachos y un compilador normal (no cruzado) para compilar los distintos módulos de núcleo? Debido a que los módulos del núcleo se ejecutan en el sistema nativo de la máquina (sistema Linux, por tanto requieren un compilador “normal”) y los programas de usuario se ejecutan en una máquina basada en un microprocesador MIPS (que se simula, por tanto se requiere un compilador “cruzado”).

2 (2 puntos)

Diseñe una solución al primer problema de los lectores y escritores (prioridad para los lectores), con el requisito añadido de que no puede haber más de N lectores simultáneos. Como herramienta de sincronización, utilice monitores. La solución consistirá en el algoritmo que ha de ejecutar un proceso lector, y el que ha de ejecutar un proceso escritor. El código puede estar escrito en cualquier especificación algorítmica.

t y pe Le c t or e s _ Es c r i t or e s = mo ni t o r var Le c t , Es c : c on d i t i on ; n l e c : e n t e r o; e s c r i b i e n d o: b ool e a n a ; pr o c e dur e e nt r y Emp e z a r _ Le c t u r a ( ) be g i n n l e c : =n l e c +1 ; whi l e e s c r i b i e n d o or n l e c >N do Le c t . Wa i t ; e nd; pr o c e dur e e nt r y Te r mi n a r _ Le c t u r a ( ) be g i n n l e c : =n l e c - 1 ; i f n l e c >=N t h e n Le c t . Si g n a l e l s e i f n l e c =0 t h e n Es c . Si g n a l ; end i f ; e nd; pr o c e dur e e nt r y Emp e z a r _ Es c r i t u r a ( ) be g i n whi l e e s c r i b i e n d o or n l e c >0 d o Es c . Wa i t ; Es c r i b i e n d o: =v e r d a d e r o; e nd; pr o c e dur e e nt r y Te r mi n a r _ Es c r i t u r a ( ) be g i n e s c r i b i e n d o: =f a l s o; i f n l e c >0 t h e n Le c t . Br oa d c a s t ; el s e Es c . Si g n a l ; end i f ; e nd; be g i n n l e c : =0 ; e s c r i b i e n d o: =f a l s o; e nd; e nd.

3 (2 puntos) Responda con brevedad a las siguientes cuestiones. A. ¿Qué significa que una política de planificación de CPU sea expulsiva?

Nombre

Ø Que el planificador puede desalojar al proceso que está en CPU. Por ejemplo, para implementar tiempo compartido y tiempo real, es necesaria una planificación expulsiva. B. ¿Con qué finalidad se emplea la técnica de envejecimiento en la planificación del uso del procesador?

Ø Para evitar el riesgo de inanición existente cuando se lleva a cabo una planificación por prioridades. C. Un sistema de memoria virtual ha de escoger a una página víctima. Existen tres páginas candidatas, que sólo se diferencian en el estado del proceso que las posee: hay una página cuyo proceso está en estado de ejecución; otra cuyo proceso está en estado de bloqueo; y el proceso de la tercera página está en estado de preparado. ¿Qué página sería más recomendable escoger como víctima?

Ø Es conocido que la política óptima consiste en escoger como víctima aquella página que más tiempo tarde en usarse. De las tres candidatas, la página que más probablemente tarde en accederse es la del proceso que está en estado de bloqueo. Las otras dos páginas pertenecen a procesos que muy probablemente hagan accesos a memoria en un futuro inmediato, mientras que el proceso bloqueado no hará ningún acceso en tanto persista su situación de bloqueo. Así que esa es la mejor apuesta.

4 (2 puntos)

Considere un sistema de archivos en un disco en el que el tamaño de bloque de sistema de archivos es 512 bytes. Suponga que toda la información de control de cada archivo ya se encuentra en memoria principal. Para las estrategias de asignación de espacio de disco contigua e indexada, especifique los pasos y cálculos a realizar para transformar una dirección de dato de archivo, expresada en forma de desplazamiento desde el comienzo del archivo y longitud del dato, a bloque de sistema de archivos.

Sea: P la posición del primer byte del dato a acceder del fichero con respecto al origen de éste. L la longitud del dato Entonces: 1. Obtenemos el bloque relativo que contiene al primer byte del dato: B0 = Parte entera(P/512) 2. Obtenemos la posición del primer byte del dato en el bloque B0: D0 = Resto(P/512) 3. Obtenemos el bloque relativo que contiene el último byte del dato a acceder. B1 = Parte entera((P+D-1)/512) 4. Obtenemos la posición de este último byte en el bloque B1 D1 = Resto((P+D-1)/512) 5. Obtenemos el número de bloque de sistema de archivo de los bloques B0 y B1: - Para la política contigua DB0 = B0 y DB1 = B1 - Para la política indexada DB0 = INDICES[B0] y DB1 = INDICES[B1]. Siendo INDICE el bloque de índices del archivo.

5 (2 puntos) Considere un sistema de memoria segmentada, sin memoria virtual. Especifique de forma algorítmica los pasos que se deben ejecutar en la traducción de una dirección lógica a dirección física. En su especificación deberá contemplar el uso de los distintos recursos físicos y lógicos requeridos. El formato de la dirección contiene dos campos: segmento (SEG) y desplazamiento en el segmento (DES). Al no disponer de memoria virtual se asume que todo el espacio direccionable está en memoria. 1. Traducción mediante el hardware especial de traducción (que consiste en una serie de registros que representan a un subconjunto de segmentos del espacio direccionable del programa): si el segmento está representado en dicho subconjunto, entonces se obtiene la dirección sumando la dirección base de la zona de memoria que contiene el segmento con el desplazamiento. 2.1. Obtener el comienzo de la tabla de segmentos (registro origen de la tabla de segmentos) 2.2. Verificar que se trata de un segmento válido. Esto se comprueba mediante dos verificaciones. Primero, comparando SEG con el número de entradas de la tabla, si SEG lo supera entonces error por dirección inválida (número de segmento inválido). Segundo que el campo de desplazamiento no supera el tamaño del segmento, si es así entonces error por dirección inválida (desplazamiento en el segmento inválido). 2.3. Acceder a la entrada SEG de la tabla de segmentos y obtener la dirección base del área de memoria que lo contiene. El resultado de la traducción será la suma de esta dirección base con el campo DES.

6 (2 puntos) Suponga un sistema con 5 procesos, P0 a P4, y 3 tipos de recursos A, B, y C. El tipo de recurso A tiene 2 ejemplares, B tiene 10 ejemplares y C tiene 6 ejemplares. En cierto instante, el sistema se encuentra en el siguiente estado: Asignados Solicitudes A B C A B C P0 1 0 0 0 0 0 P1 0 2 0 0 2 2 P2 0 3 3 0 0 0 P3 P4

1 0

2 0

1 2

0 0

1 0

0 2

¿Hay interbloqueo en el sistema? Justifique su respuesta.

El sistema no está en un estado de interbloqueo. Para demostrarlo aplicamos el algoritmo de detección visto en clase y vemos que podemos encontrar una secuencia ordenada de procesos en la que lo que pide cada proceso puede ser satisfecho por lo disponible más lo asignado a los procesos que están antes que él en la secuencia.

Calificación 1 2 3 4 5 6

Universidad de Las Palmas de Gran Canaria Escuela Universitaria de Informática Sistemas Operativos Convocatoria de junio, año 2002 21 de junio de 2002

SOLUCI ONES Nombre

Titulación

IMPORTANTE : Las seis preguntas suman 12 puntos. Usted deberá descartar al menos UNA de las preguntas 3, 4, 5 y 6. Es decir, usted puede optar por contestar estos grupos de preguntas: 12345, 12346, 12356, 12456. No se admitirá ninguna otra combinación. Dispone de tres horas y media para completar el examen.

1 (2 puntos) Describa mediante un esquema todos los estados por los que atraviesa un hilo en Nachos y las transiciones entre ellos, indicando cuál es el tipo de evento que produce cada transición.

Diagrama de estados hilo = new T hread(“mihilo”)

hilo-> Fork(funcion, param) JUST_CREATE D

scheduler-> Run(hilo)

RE ADY

RUNNING

currentThread-> Yield ( ) scheduler-> ReadyToRun(hilo)

currentThread -> Sleep ( )

BLOCKED

delete threadToBeDestroyed

“hilo finalizado”

1. El primer estado por el que pasa un hilo es el de “recién creado” (JUST_CREATED):

hilo = new Thread(“mihilo”); En este punto, al hilo aún no se le ha creado una pila ni se sabe el código que va a ejecutar. 2. En el momento en que se realiza la operación: hilo->Fork(funcion, param) El hilo pasa a la cola de preparados (estado “READY”), pendiente únicamente de que se le asigne la CPU para su ejecución (ya se le ha creado la pila y se ha indicado el código que ejecutará - funcion). 3. El hilo creado (en adelante “mihilo”) pasará a estado “RUNNING”, es decir, “en ejecución” cuando el planificador le ceda la CPU: scheduler->Run(hilo) situación que puede venir provocada bien porque otro hilo ceda voluntariamente la CPU (recuerden que la política de planificación de hilos del Nachos es no expulsiva) o bien porque otro hilo en ejecución termine o quede bloqueado a la espera de algún evento, situaciones ambas en las que el planificador toma el siguiente de la cola de preparados. En ambos casos “mihilo” debe ser evidentemente el primero de la cola de preparados. 4. Estando en ejecución (RUNNING), un hilo puede pasar a diferentes estados: “READY”: un hilo estando en ejecución pasará a la cola de preparados si voluntariamente cede la CPU (currentThread->Yield) y siempre que existan otros hilos en la cola de preparados, ya que de lo contrario permanecerá en el mismo estado, es decir, en ejecución. “BLOCKED”: se pasará a estado “bloqueado” cuando se invoca: currentThread->Sleep() Esto se puede deber a dos razones: la primera es que el hilo necesite esperar a que ocurra algún evento o condición (por ejemplo, pasará a este estado un hilo que ejecute una operación wait sobre una variable condición). La segunda situación por la que un hilo pasa a estado bloqueado se debe a la forma en que un hilo finaliza. En Nachos, la terminación de un hilo provoca que este pase a estado bloqueado, de forma que sea el siguiente hilo que entre en ejecución el encargado de liberar la memoria del hilo finalizado (una variable global, threadToBeDestroyed, apunta al hilo finalizado). 5. Por último señalar que para pasar del estado “bloqueado” al estado “preparado” se debe producir el evento o condición de desbloqueo (para el caso comentado en el que el hilo quedó bloqueado al realizar una operación wait sobre una variable condición, el desbloqueo y consecuentemente el paso a estado preparado se producirá cuando otro hilo ejecute una operación signal o broadcast sobre dicha variable condición)

Nombre

2 (2 puntos) Implemente las operaciones de un semáforo general utilizando un monitor.

t y pe Se ma f or o ( Va l or _ I n i c i a l ) = moni t o r var b l oq u e a d o: c on d i t i on ; s : e n t e r o; pr o c e dur e e nt r y P( ) be g i n whi l e s =0 t h e n b l oq u e a d o. Wa i t ; s : =s - 1 ; e nd; pr o c e dur e e nt r y V( ) be g i n s : =s +1 ; b l oq u e a d o. Si g n a l ; e nd; be g i n s : = Va l or _ I n i c i a l ; e nd; e nd.

3 (2 puntos)

La tabla inferior muestra una carga de procesos. Represente con un diagrama de Gantt la planificación de estos procesos y obtenga los tiempos de retorno y de espera al aplicar las siguientes políticas:

-

Primero el más corto con expropiación Round-Robin con cuanto de 2 u.t.

TL: tiempo de llegada

Proceso

TL D

D: duración

P0

0

4

P1

1

1

P2

1

2

P3

2

2

Primero el más corto (SJF) con expropiación P0 P1 P2 P2 P3 P3 P0 P0 P0 Proceso

Tiempo de espera

Tiempo de retorno

P0

5

9

P1

0

1

P2

1

3

P3

2

4

Media

2

4,25

Round-Robin (Q = 2 u.t.): admite dos posibilidades (en realidad cuatro, puesto que al llegar P1 y P2 en el mismo instante, es posible colocar primero en la cola cualquiera de los dos) Solución A: P0 P0 P1 P2 P2 P3 P3 P0 P0 Proceso

Tiempo de espera

Tiempo de retorno

P0

5

9

P1

1

2

P2

2

4

P3

3

5

2,75

5

Media Solución B:

P0 P0 P1 P2 P2 P0 P0 P3 P3 Proceso

Tiempo de espera

Tiempo de retorno

P0

3

7

P1

1

2

P2

2

4

P3 Media

5

7

2,75

5

Nombre

4 (2 puntos) Considere un sistema de gestión de memoria paginada de un solo nivel, sin memoria virtual. Especifique de forma algorítmica los pasos que se deben ejecutar en la traducción de una dirección lógica a una dirección física. En su especificación deberá explicar el uso de los distintos recursos físicos y lógicos requeridos.

El formato de la dirección contiene dos campos: página (PAG) y desplazamiento en la página (DES). Al no disponer de memoria virtual se asume que todo el espacio direccionable está en memoria. 1. Traducción mediante el hardware especial de traducción (TLB): si la página está representada en dicha tabla, entonces se obtiene la dirección sumando la dirección base del marco de página que la contiene con el desplazamiento. 2. Traducción mediante la tabla de páginas. 2.1. Obtener el comienzo de la tabla de páginas (registro origen de la tabla de páginas) 2.2. Verificar que se trata de una página válida. Esto se comprueba comparando PAG con el número de entradas de la tabla, si PAG lo supera entonces error por dirección inválida. 2.3. Acceder a la entrada PAG de la tabla de páginas y obtener la dirección base del marco de página que la contiene. El resultado de la traducción será la suma de esta dirección base con el campo DES.

5 (2 puntos) Se tiene un sistema con 5 procesos, P0 a P4, y 3 tipos de recursos A, B, y C. El tipo de recurso A tiene 10 ejemplares, B tiene 6 ejemplares y C tiene 2 ejemplares. Suponga que en el instante T0 el sistema se encuentra en el siguiente estado:

P0 P1 P2 P3 P4

Asignados Solicitudes A B C A B C 0 0 1 0 0 0 2 0 0 2 2 0 3 3 0 0 0 0 2 1 1 1 0 0 0 2 0 0 2 0

¿El sistema se encuentra en interbloqueo? Justifique la respuesta. El sistema no está en interbloqueo

El sistema no está en un estado de interbloqueo. Para demostrarlo aplicamos el algoritmo de detección visto en clase y vemos que podemos encontrar una secuencia ordenada de procesos en la que lo que pide cada proceso puede ser satisfecho por lo disponible más lo asignado a los procesos que están antes que él en la secuencia.

6 (2 puntos)

Un sistema de archivos utiliza una política de asignación de espacio indexada. En este sistema, los bloques de datos de un archivo, ¿se pueden ubicar de forma contigua? ¿Es necesario que los bloques estén ubicados de forma contigua? ¿Da igual que lo estén? Justifique con mucha claridad su respuesta. ¿Cambiaría en algo su contestación si la asignación de espacio fuera enlazada?

La asignación indexada permite que los bloques de datos de un archivo se encuentren dispersos por el disco, pero evidentemente no obliga a ello. Así que los bloques de un archivo indexado pueden estar contiguos. Sin embargo, no es indiferente el que los bloques estén contiguos. Los accesos secuenciales al archivo serán más eficientes en ese caso, porque el desplazamiento de los cabezales del disco será menor, comparado con el recorrido que tendría que hacer el cabezal si los bloques estuvieran desperdigados por la superficie del disco. La contigüidad ocasiona un menor tiempo de acceso. En el mejor caso, todos los bloques del archivo estarían en un mismo cilindro y la cabeza lectora no tendría que hacer ningún movimiento para leer el archivo completo. Si la asignación de espacio fuera enlazada, la respuesta sería similar. Incluso tendría más impacto en el rendimiento el hecho de que los bloques estén contiguos, ya que en la asignación enlazada cualquier acceso al archivo, ya sea secuencial o ya sea directo, exige recorrer los enlaces de los bloques. Si los bloques están contiguos, el cabezal del disco hará un recorrido más pequeño.

Calificación

1

Fac. de Informática / Escuela Univ. Informática SISTEMAS OPERATIVOS

2

Examen Parcial 26 de abril de 2008

4

Nombre

3

*** S O L U C I O N E S ***

Titulación

Dispone de tres horas para realizar el examen

1 (2.5 puntos) Se propone la siguiente solución al problema de los lectores/escritores: Variables compartidas Semaphore mutex1(1), mutex2(1); Semaphore lectores(1), escritores(1); Int n_lectores=0; int n_escritores=0; Procesos Lectores() { While (true) { Lectores.wait(); Mutex1.wait(); n_lectores++; if (n_lectores==1) escritores.wait(); mutex1.signal(); lectores.signal();

Procesos Escritores() { While (true) { Mutex2.wait(); n_escritores++; if (n_escritores==1) lectores.wait(); mutex2.signal(); escritores.wait(); Escritura en el recurso

Lectura del recurso Escritores.signal(); Mutex2.wait(); n_escritores--; if (n_escritores==0) lectores.signal(); mutex2.signal();

Mutex1.wait(); n_lectores--; if (n_lectores==0) escritores.signal(); mutex1.signal(); } }

} }

a) ¿Cumple esta solución las especificaciones básicas del problema, es decir, permite la lectura simultánea de varios lectores e impide que puedan acceder al recurso lectores y escritores o múltiples escritores en un instante dado? Razona la respuesta indicando trazas concretas que apoyen tus argumentos. (1.5p) b) ¿A quién da preferencia el algoritmo anterior: a los lectores, a los escritores o no establece ninguna preferencia? ¿Es posible la inanición de algún tipo de proceso? (1p) Solución: a) Sí. Se trata de una solución que cumple las especificaciones básicas del problema. Se puede ver fácilmente que si un lector entra, cierra el paso a los escritores al realizar una operación wait sobre el semáforo “escritores”. Esto hace que en caso de algún intento de escritura por parte de algún escritor, dicho escritor quedará bloqueado en la operación de wait sobre el semáforo “escritores”. Del mismo modo, si existe un escritor escribiendo en el recurso, los lectores quedarán blo...