sistemas operativos - etsisi.upm.es · a continuación se presenta una selección de problemas que...

E.U. de Informática-U.P.M. Sistemas Operativos

Febrero 2007

SISTEMAS OPERATIVOS

Problemas escogidos


i

A continuación se presenta una selección de problemas que han sido objeto de examen de Sistemas

Operativos en cursos anteriores.

La tabla siguiente refleja, agrupados por temas, los problemas seleccionados, la convocatoria en la que se

pusieron, así como un breve comentario de los aspectos sobre los que se pregunta y referencia a la página

de este documento donde aparece el enunciado.

Tema Ejer. Fecha Comentario Página

Procesos

2 31/01/95 Seguimiento sencillo de RR, SJF y prioridades 1

3 18/01/97 Cálculo de tiempo de retorno, rendimiento y eficiencia 3

2 10/09/03 Threads en nivel de usuario y de S.O. (aptdos. 1, 2c, 3) 4

3 02/09/99 Implementar dormirse (segundos) 6

2 08/09/04 Seguimiento de política de planificación tipo tiempo real 7

2 15/12/04 Programación de rutinas de planificación tipo tiempo real 8

3 12/12/01 Planificación tipo Linux 10

2 14/12/05 Políticas de planificación para sistemas interactivos 13

Memoria

2 8/06/04 Cálculos sobre particiones variables y paginación 15

3 17/09/01 Organización general de la paginación 16

3 02/07/01 Paginación y organizar área swap con lista encadenada 17

2 12/12/01 Tabla de Páginas de dos niveles 19

3 14/06/03 Tabla de Páginas Invertida 21

3 15/12/04 Introducción a la segmentación 22

E/S

12 (cap.5 Tanen.) Tiempos de transferencia en una red xx

14 (cap.5 Tanen.) Estructura de un disco: cilindros, pistas y sectores xx

20 (cap.5 Tanen.) Tiempos de lectura en disco flexible xx

24 (cap.5 Tanen.) Algoritmos de planificación de disco (1) xx

25 (cap.5 Tanen.) Algoritmos de planificación de disco (2) xx

3 17/06/05 Accesos a disco 23

Ficheros

3 13/09/96 Sistema de tipo UNIX y creación de estructura 24

3 25/06/97 Similar al anterior mezclando MS/DOS y UNIX 26

3 10/12/03 UNIX tratando caché de bloques 28

3 14/12/05 Accesos a bloques de disco correspondientes a un fichero 29


1

E. U. de Informática Departamento de Informática Aplicada

Examen Final de Sistemas Operativos I 31 de Enero de 1995

EJERCICIO 2 (4 puntos) Tiempo estimado: 60m.

Disponemos de un sistema con multiprogramación implementado con un solo procesador en el cual se

ejecutan los tres procesos descritos a continuación:

Proceso P1

Instante de llegada: 0

Prioridad: Baja

Estructura del proceso: 27 mseg de utilización de U.C.P.,

seguidos de 10 mseg de acceso a E/S

y finalizando con 5 mseg de U.C.P.

Proceso P2


Prioridad: Media




Proceso P3


Prioridad: Alta




No se debe olvidar que además de estos procesos, existe un proceso “ocioso” cuyo fin es utilizar la U.C.P.

mientras no la necesite ningún otro proceso. Además, vamos a considerar que el tiempo necesario para

efectuar el cambio de contexto es nulo.

El objeto de este ejercicio es analizar el comportamiento de los distintos procesos en función de diferentes

políticas de planificación de U.C.P. Para la respuesta se utilizarán los gráficos proporcionados en la hoja

de respuestas.

Teniendo en cuenta todo lo anterior, se pide completar los gráficos (sombreando los instantes en que cada

proceso está utilizando el procesador) correspondientes a cada una de las siguientes políticas de

planificación:

1.- Round-Robin (expulsora) con rodajas de tiempo de 10 mseg.

2.- Más-Corto-Primero (no expulsora). Considerando el tiempo total de U.C.P.

3.- Prioridades (no expulsora).

4.- Prioridades (expulsora).


2

SISTEMAS OPERATIVOS I 31 de enero de 1995

Hoja de Respuestas del EJERCICIO 2

APARTADO 3

0 5 10

15

20

25 30

35

40

45

50

55

60

65

70

75 80

85

90

95

tiempo (mseg.)

OCIOSO

P3

P2

P1

APARTADO 1

APARTADO 2

APARTADO 4

0 5 10

15

20

25 30

35

40

45

50

55

60

65

70

75 80

85

90

95

tiempo (mseg.)

OCIOSO

P3

P2

P1

0 5 10

15

20

25 30

35

40

45

50

55

60

65

70

75 80

85

90

95

tiempo (mseg.)

OCIOSO

P3

P2

P1

0 5 10

15

20

25 30

35

40

45

50

55

60

65

70

75 80

85

90

95

tiempo (mseg.)

OCIOSO

P3

P2

P1


3


Examen Final de Sistemas Operativos I 18 de enero de 1997

EJERCICIO 3 (3,5 puntos) Tiempo estimado: 1h 30 m. Un entorno monoprocesador soporta un sistema operativo multiproceso que solo está ejecutando procesos

con código y datos idénticos. Cada proceso requiere N periodos de tiempo T para completar su ejecución.

En cada periodo de tiempo T, emplea la primera mitad en realizar E/S y la segunda mitad en ejecutarse en

el procesador. El algoritmo de planificación empleado es Round-Robin con una rodaja de tiempo de T/2.

Sean las siguientes definiciones:

TIEMPO DE RETORNO (Rt ): tiempo total necesario para que un proceso se ejecute

completamente.

TIEMPO MEDIO DE RETORNO (RT ): media aritmética de los tiempos de retorno de cada proceso.

RENDIMIENTO ( R ): número de procesos terminados por periodo de tiempo T.

EFICIENCIA ( E ): porcentaje de tiempo en el que la cpu está activa.

SE PIDE:

1. Suponiendo que

todos los procesos pueden realizar simultáneamente operaciones de E/S

se considera que el tiempo empleado en cambio de contexto en despreciable

el valor de N puede tomar valores pequeños.

Indicar el tiempo medio de retorno RT , el rendimiento R por periodo de tiempo T y la eficiencia E,

en función de N y T, cuando en el sistema se están ejecutando:

a) 1 proceso

b) 2 procesos

c) 4 procesos

2. Calcular el valor de la eficiencia para los tres casos anteriores si:

a) N= 4

b) N=16

3. Analice los resultados obtenidos con respecto a la eficiencia.


4


Examen Final de Sistemas Operativos I 10 de Septiembre de 2003

EJERCICIO 2 (puntuación 3´5 puntos) Tiempo Estimado: 60 m

Se cuenta con un sistema operativo multiproceso tradicional, en el que cada proceso cuenta con un único hilo de

ejecución o thread. Sin embargo, se pretende que los procesos de usuario puedan ser multihilo, es decir, cuenten

con varios threads de ejecución. Para conseguirlo, se proporciona una biblioteca, por encima del sistema operativo,

que ofrece funciones para crear y destruir threads, así como para establecer la política de planificación de dichos

threads dentro del proceso, como se puede ver en la siguiente figura:

En este modelo, cuando el sistema operativo asigna al proceso de usuario una porción de procesador mediante la

política planificación Round Robin, dentro del proceso se reparte dicho tiempo entre los threads creados, según la

política de planificación local establecida en la biblioteca, en este caso es FIFO.

Además, todas las estructuras necesarias para mantener los threads de un proceso se crean dentro del espacio del

proceso, incluida una tabla de bloques de control de threads (Tabla de BCT`s).

Hay que destacar que, al crear los threads en el nivel de usuario, estos threads no existen para el sistema operativo:

para el núcleo la unidad de planificación es el proceso.

Suponiendo que el sistema operativo utiliza Round Robin con una porción de tiempo de 100 ms y que se crean

simultáneamente dos procesos P1 y P2 (estando P1 el primero en la cola de preparados) cuyo código es el

siguiente:

P1 P2

(1) Usa cpu (50 ms) Usa cpu (30 ms) (2) Hace una llamada al sistema bloqueante (100 ms) (3) Usa cpu (10 ms) (4) Usa cpu (30 ms)

Se pide:

1) Dibuje el cronograma relativo a los procesos P1, P2 y el proceso ocioso para los casos siguientes:

a) El proceso P1 es monohilo.

b) El proceso P1 tiene dos hilos: el hilo P1A ejecuta las tres primeras instrucciones (1, 2 y 3) y el hilo P1B

ejecuta la última (4). Se supone que P1A está antes que P1B en la cola de preparados.

Proceso de

usuario

BCT´s

T1

T2

Pn … P1

Cola de preparados

BCP´s

P1

…

Pn

cpu

Sistema

Operativo

Round

Robin

FIFO

Proceso de

usuario P1

Thread 2 Thread 1


5

2) Ahora se desea que la gestión de threads se haga desde dentro del sistema operativo, para que la unidad mínima

de planificación sea el thread y no el proceso, por lo que es necesario modificar el núcleo, tal como se ve en la

figura:

a) Indique todos los campos de las estructuras que introduciría o modificaría para que el núcleo pueda

soportar threads.

b) Proponga las especificaciones de las llamadas al sistema que permitan crear y destruir threads.

c) Repita el cronograma para el proceso P1 multihilo y P2, siendo el orden inicial en la cola de preparados

P1A, P1B y P2.

3) Explique razonadamente qué ventajas e inconvenientes ve en el uso de los threads:

a) Implementados en el espacio de usuario.

b) Implementados dentro del sistema operativo.

Tn … T2 T1

Cola de preparados

BCP´s

P1

…

Pn

cpu

Sistema

Operativo

Round

Robin

Proceso de

usuario P1

?

T2 T1


6


Examen Final de Sistemas Operativos I 2 de Septiembre de 1999

EJERCICIO 3 (4 puntos) Tiempo: 60 min.

En un sistema monoprocesador, se desea implementar la parte del Sistema Operativo que permite que los procesos

se duerman durante un cierto tiempo. En concreto, dar soporte a la llamada al sistema cuyo perfil es el siguiente:

PROCEDURE dormirse (segundos: in POSITIVE);

Cuando un proceso ejecute esta llamada, el Sistema Operativo debe garantizar que el proceso en cuestión se

duerme (deja la posesión de la UCP) durante al menos los segundos indicados, tomando control lo antes posible

una vez transcurrido dicho tiempo y respetando siempre la política de planificación del sistema.

Se dispone de una interrupción periódica que sucede cada 100 milisegundos, cuya rutina de tratamiento asociada

denominaremos rutinaReloj.

Para la gestión de procesos, el Sistema Operativo tiene, entre otras, las estructuras de datos siguientes: maxProcesos : constant := 50;

type idProceso is INTEGER range 0..maxProcesos;

type descriptorProceso is

record

pid : idProceso; -- El identificador del proceso

siguiente: idProceso; -- Para encadenar descriptores en colas

-- Resto de campos

end record;

type colaProcesos is

record

primero: idProceso := 0;

ultimo : idProceso := 0;

end record;

procesos : array [1..maxProcesos] of descriptorProceso;

enEjecucion: idProceso; -- Identificador del proceso en ejecucion

preparados : colaProcesos;

Se pide:

1. Indica qué nuevas estructuras de datos y/o modificaciones a las ya existentes, introducirías para dar soporte a

este servicio que permite dormirse a los procesos.

2. Describe las acciones que ejecutará el Sistema Operativo desde que toma control debido a que un proceso

llama a “dormirse”, hasta que devuelve el control al siguiente proceso a ejecutar. Se puede mezclar lenguaje

formal tipo Ada con expresiones informales del tipo: “se salva el estado del proceso en ejecución”, “se mete al

proceso en ejecución en la cola de preparados”, etc.

3. Describe, con el mismo nivel de detalle que en el punto anterior (2), las acciones que ejecutará la rutina del

Sistema Operativo “rutinaReloj”, supuesto que la misma sólo se utiliza para poder dar soporte a “dormirse”.

4. Supuesta planificación mediante “Round-Robin” con rodajas de tiempo de 500 milisegundos y que un proceso

ejecuta “dormirse (5)”, indica (lo más aproximado que puedas) cuál es el tiempo máximo que dicho proceso

estará bloqueado y cuál es el tiempo máximo que puede transcurrir desde que el proceso se duerme hasta que

dicho proceso vuelve a tener la UCP. Razónalo.

5. Responde a lo mismo que en (4) pero suponiendo ahora planificación por prioridades.

Nota: En los apartados 1, 2 y 3 no se trata de implementar la solución más eficaz, basta con una que funcione de

forma razonable.


7


Examen Final de Sistemas Operativos I 8 de septiembre de 2004

EJERCICIO 2 (3,5 puntos) Tiempo estimado: 50 min. Sea un sistema de planificación de procesos por prioridades expulsor. A cada proceso se le asigna una prioridad fija

cuando se crea que consiste en un número entero positivo; a mayor valor, mayor prioridad. Sean tres procesos A, B

y C con prioridades 33, 25 y 20 respectivamente. Estos procesos tienen que ejecutarse periódicamente cada 30, 40

y 50 ms. respectivamente. Esto quiere decir que, por ejemplo, el proceso A debe ejecutarse una vez entre los

instantes 0 y 30 ms.; otra vez entre los instantes 30 y 60 ms; y así sucesivamente. En cada activación el proceso A

consume 10 ms. de CPU, el proceso B consume 15 ms. y el proceso C consume 5 ms.

Nota: En el instante t = 0, los tres procesos A, B y C están preparados y ninguno de ellos realizará operaciones de

E/S.

SE PIDE:.

1) Dibuje un diagrama de tiempos (hasta el instante t=110) donde se aprecie los periodos de tiempo (para cada

proceso) en los que se está ejecutando. ¿Qué proceso se está ejecutando en el intervalo 25..30? ¿Y en el

intervalo 70..75? ¿Y en el intervalo 90..95?

2) Suponga ahora que el tiempo de ejecución para el proceso A es de 15 ms. en lugar de 10 ms.

(manteniéndose igual el resto de los datos). Dibuje un diagrama de tiempos (hasta el instante t=60) donde

se aprecie los periodos de tiempo (para cada proceso) en los que se está ejecutando. ¿Qué proceso se está

ejecutando en el intervalo 15..20? ¿Y en el intervalo 30..35? ¿Y en el intervalo 45..50?

3) En las condiciones del apartado 2, suponga ahora que cambiamos el planificador tal que el nuevo

planificador (con política expulsora) selecciona al proceso cuyo fin de periodo está más próximo a vencer.

Dibuje un diagrama de tiempos (hasta el instante t=85) donde se aprecie los periodos de tiempo (para cada

proceso) en los que se está ejecutando. ¿Qué proceso se está ejecutando en el intervalo 35..40? ¿Y en el

intervalo 50..55? ¿Y en el intervalo 80..85?


8


Examen Final de Sistemas Operativos I 15 de diciembre de 2004

EJERCICIO 2 (3.5 puntos) Tiempo estimado: 60 m

Queremos diseñar el planificador de procesos de un sistema operativo que se va a utilizar para soportar

específicamente procesos multimedia. En este tipo de sistemas las aplicaciones se caracterizan por tener que

ejecutarse dentro de unos rangos de velocidad determinados, por ejemplo, un proceso encargado de

visualizar un vídeo deberá ejecutarse de una forma más o menos continua, sin parones ni acelerones. Para

ello, al crear un proceso se realiza una reserva de CPU al sistema operativo.

En esta reserva se especifican dos parámetros: Tiempo de Cómputo (C) y Periodo (P). El sistema operativo

deberá encargarse de ejecutar este proceso durante

C unidades de tiempo (u.t.) cada P u.t. La ejecución

de las C u.t. puede hacerse en cualquier punto del

intervalo, pero siempre dentro de las P u.t. Además,

la ejecución de las C u.t. no tiene por qué ser

consecutiva. Las C u.t. de un proceso tendrán como

plazo máximo para finalizar el siguiente instante de

activación del proceso.

No obstante, para evitar sobrecargas, el sistema tiene que controlar que la necesidad de CPU de todos los

procesos existentes cumpla la condición:

donde Ci y Pi son los parámetros de reserva de cómputo de los procesos y N es el

número de procesos existentes en el sistema.

Si no se va a cumplir esta condición, al intentar hacer la reserva el sistema operativo devolverá el valor –1

como código de error.

El sistema operativo va a seguir una planificación expulsora EDF (Earlest Deadline First). En esta

planificación el sistema operativo elige como siguiente proceso a ejecutar aquel que tenga más próximo el

siguiente plazo de ejecución, es decir, aquel cuya siguiente activación esté más próxima.

Se pide:

1) A continuación se especifica una lista de acciones (desordenadas) que tiene que realizar en algún

momento el sistema operativo y que están relacionadas con la gestión de procesos:

Seleccionar al siguiente proceso en ejecutar

Desbloquear a los procesos que les toca activarse

Crear un descriptor de proceso

Comprobar si se han cumplido las C u.t. del proceso que está en ejecución

Actualizar la variable del sistema Instante_Actual, que contiene la hora actual del sistema

Comprobar la necesidad de CPU de los procesos

Estas acciones se llevarán a cabo dentro de diversas rutinas del sistema operativo. Especifique cuáles serán

dichas rutinas, indicando para cada una de ellas:

Nombre de la rutina

Motivo de activación de dicha rutina

Acciones (ordenadas) de la lista anterior que tiene que llevar a cabo

Completar la rutina con otras acciones que considere necesarias y que no están incluidas en la

lista (con un nivel de detalle similar)

Pu.t.

Ejecución del proceso

Pu.t. Pu.t.

Cu.t. Cu.t. Cu.t.

1 Pi

Ci

i=1

N


9

2) Dadas las siguientes estructuras de datos.

maxProcesos : constant := 50; type idProcesos is INTEGER range 0..maxProcesos; type descriptorProceso is record pid : idProceso; -- Identificador de proceso siguiente : idProceso; -- Apunta al siguiente elemento, para formar una lista tiempoComputo : integer; -- Tiempo de computo reservado periodo : integer; -- Periodo indicado en la reserva siguienteActivacion : integer; -- Instante de la siguiente activación para el proceso credito : integer; -- Unidades de tiempo que le queda al proceso por ejecutar durante su activación actual end record; type colaProcesos is record primero : id Proceso := 0; ultimo : idProceso := 0; end record; procesos : array [0..maxProcesos] of descriptorProceso: enEjecucion : idProceso; -- Identificador del proceso en ejecución preparados : colaProcesos; dormidos : colaProcesos; instanteActual : integer; -- Reloj creciente que marca el instante actual

Detalle de forma algorítmica las siguientes acciones:

Comprobar que se han cumplido las C u.t. del proceso que está en ejecución

Desbloquear a los procesos que les toca activarse

Crear un descriptor de proceso

Comprobar la necesidad de CPU de los procesos

Seleccionar al siguiente proceso en ejecutar

NOTA: Para especificar operaciones de insertar/sacar elementos de listas no hará falta detallar a nivel de

punteros. Bastará con indicar en seudocódigo qué operación se realiza, con qué elemento y en qué lista.


10



EJERCICIO 3 (3’5 puntos) Tiempo estimado: 75 m

Tenemos un sistema operativo con un algoritmo de planificación similar al de linux, tal y como se

describe a continuación.

El sistema dispone de dos algoritmos de planificación, uno para procesos de tiempo compartido y otro

para procesos de tiempo real. Cada proceso puede acogerse a cualquiera de estas dos políticas de

planificación.

Para los procesos de tiempo compartido se utiliza un algoritmo basado en créditos. Cada proceso dispone

de un número de créditos, de tal manera que para seleccionar el siguiente proceso a ejecutarse, se elige al

que tiene más créditos acumulados. Cada vez que se produce una interrupción de reloj, el proceso en

ejecución pierde un crédito; cuando su número de créditos llega a cero, pierde la CPU y se selecciona otro

proceso.

Cuando no queda ningún proceso preparado con créditos, el sistema vuelve a asignar créditos a todos los

procesos del sistema en función de su prioridad según la regla siguiente:

Créditos = (Créditos_Restantes / 2) + Prioridad.

Para los procesos de tiempo real, el sistema siempre concede la CPU al proceso de mayor prioridad,

implementando dos algoritmos por prioridad expulsores: FIFO y Round Robin. Cada proceso de tiempo

real debe indicar a cual de los dos se acoge. En el algoritmo FIFO no se le quita la CPU a no ser que pase

a preparado un proceso de mayor prioridad. En el algoritmo Round Robin, la CPU se reparte en idénticas

rodajas de tiempo entre los procesos que tengan la misma prioridad.

El sistema solo ejecutará un proceso de tiempo compartido si no hay ningún proceso de tiempo real

preparado para ejecutar.

1.- (0.7 ptos.) Dadas las siguientes estructuras de datos, indica qué nuevas estructuras de datos y/o

modificaciones a las ya existentes introducirías para dar soporte al algoritmo de planificación descrito,

teniendo en cuenta que las estructuras de datos deben permitir accesos eficientes a la información.

const maxProcesos = 50;

type idProceso = 0..maxProcesos;

descriptorProceso = record

pid : idProceso;

siguiente : idProceso;

end;

colaProcesos = record

primero : id Proceso := 0;

ultimo : idProceso := 0;

end;

var procesos : array [1..maxProcesos] of descriptorProceso:

enEjecucion : idProceso; (* Id. del proceso en ejecución *)

preparados : colaProcesos;


11

2.- (0.5 ptos.) El efecto de la ejecución de algunas rutinas puede (no siempre) provocar la realización de un cambio

de contexto. Rellena la siguiente tabla indicando, para cada una de las rutinas de la primera columna y para los dos

algoritmos de planificación indicados en la primera fila:

SÍ: si en algunas circunstancias puede provocar un cambio de contexto

NO: si nunca provocarán cambio de contexto

Round Robin

(puro)

Algoritmo descrito

similar a linux

Subir (Semaforo)

Bajar (Semaforo)

Rutina Tratam. Interrup. por finalización de E/S

Crear_Proceso

Dormir (Lapso_Tiempo)

3.- (0.8 ptos.) Supongamos que las rodajas de tiempo del sistema son de 2 unidades de tiempo (u.t.). En el

sistema existen, en un momento dado, los procesos indicados en la siguiente tabla, para los cuales se

indica las unidades de tiempo de CPU que necesitan y entre paréntesis el número de unidades de tiempo

que están bloqueados en espera de E/S. Por ejemplo, P1 necesita inicialmente 4 u.t de CPU, a

continuación se bloquea durante 10 u.t y finalmente necesita 4 u.t. más de CPU. Además, se especifica el

tipo de proceso que es cada uno.

Tiempos Tipo de Proceso

P1 4 (10) 4 Tiempo Real FIFO con prioridad 20

P2 3 (3) 3 Tiempo Real Round Robin con prioridad 10

P3 3 (3) 3 Tiempo Real Round Robin con prioridad 10

P4 4 (2) 2 Tiempo Compartido

(prioridad 20 > prioridad 10)

Dibuja un cronograma que indique el orden en que se ejecutarán los procesos, suponiendo que todos están

preparados en el instante cero y que el orden de llegada ha sido P1, P2, P3 y P4.

4.- (0.7 ptos.) Supongamos que en el sistema existen los procesos indicados en la siguiente tabla.


P1 5 (7) 5 (7) 5 Tiempo Real con prioridad 20 y FIFO

P2 4 (3) 2 Tiempo Real con prioridad 10 y Round Robin

P3 Tcpu-P3 Tiempo Real con prioridad 10 y Round Robin

P4 3 Tiempo Compartido

Sabemos que:

el tiempo de retorno de P2 es MENOR que el tiempo de retorno de P1

el tiempo de retorno de P3 es MENOR que el tiempo de retorno de P1

entendiendo por tiempo de retorno el tiempo que un proceso tarda en ejecutarse completamente.

Calcula el tiempo máximo de CPU que puede llegar a tener el proceso P3 (máximo Tcpu-P3) para que se

cumplan las dos condiciones anteriores. Razona la respuesta.


12

5.- (0.8 ptos.) Sabemos que en el sistema se produce una interrupción de reloj cada 2 u.t. Con cada

interrupción de reloj se finaliza una rodaja de tiempo para los procesos de tiempo compartido.

Supongamos que en el sistema existen los procesos indicados en la siguiente tabla, donde Créditos (Pn)

indica el número de créditos que tiene el proceso Pn.


P1 5 (20) 8 Tiempo Real con prioridad 20 y FIFO

P2 3 (6) 2 Tiempo Real con prioridad 10 y Round Robin

P3 22 Tiempo Compartido con Créditos(P3)

P4 5 Tiempo Compartido con Créditos(P4)

Considerando la siguiente situación:

Créditos (P3) es MAYOR que los Créditos (P4)

el proceso P4 tiene suficientes créditos para acabar su ejecución antes de que se le agoten

el tiempo de retorno de P4 es menor que el tiempo de retorno de P1

indica el número máximo de Créditos(P3) para que se cumpla la situación descrita. Razona la respuesta.


13



EJERCICIO 2 (3,5 PUNTOS) Tiempo estimado: 60 Minutos Queremos tener un sistema operativo que soporte la gestión de procesos convencionales (pesados) y

procesos ligeros (threads) en un sistema monoprocesador. Para ello debemos disponer de las siguientes

llamadas, todas ellas ejecutadas por el núcleo del sistema operativo:

Crear_Thread (Nombre_Procedimiento: Puntero_a_Procedimiento,

P: Prioridad) return Identificador_de_thread

Crea un nuevo thread que ejecuta el código contenido en el procedimiento que se indica como parámetro. A

dicho thread se le asigna la prioridad del proceso padre incrementada con el valor de P.

Crear_Proceso (Nombre_Fichero: Tira_Caracteres,

P: Prioridad) return Identificador_de_Proceso

Crea un nuevo proceso que ejecuta el código contenido en el fichero que se indica como parámetro. A

dicho proceso se le asigna la prioridad del proceso padre incrementada con el valor de P. Además, se crea

un thread que corresponderá a la ejecución del programa principal del proceso.

Además disponemos de las siguientes llamadas al sistema Esperar_Fin_Thread (IdThread: Identificador_de_Thread)

Esperar_Fin_Proceso (IdProceso: Identificador_de_Proceso)

En cualquier caso, a mayor número P mayor será la prioridad del proceso.

El tiempo consumido por las cuatro llamadas al sistema anteriormente descritas no es significativo.

Tenemos los procesos de las figuras 1 y 2, compuestos por los fragmentos de código desde A1 hasta C6 y

las operaciones de E/S que tardan en realizarse el tiempo especificado entre paréntesis. Sabemos que cada

uno de estos fragmentos de código tiene un tiempo de CPU de 100 unidades de tiempo y no realizan

llamadas al sistema. Inicialmente se crea el proceso A.

1.- Supongamos que se trata de un sistema interactivo, por lo que desechamos los algoritmos propios de

los sistemas Batch y decidimos considerar sólo los algoritmos de planificación propios de los sistemas

interactivos. En el conjunto de procesos de la figura 1:

a.- Indique dos de estos algoritmos que hagan que comience a ejecutarse A3 antes que B1 y C1.

b.- Indique dos de estos algoritmos que hagan que comience a ejecutarse B1 antes que C1.

c.- Indique uno de estos algoritmos que haga que comience a ejecutarse C1 antes que B1.

Para todos los casos justifique la respuesta.

2.- Supongamos que queremos dar mayor ventaja a los procesos más interactivos.

a.- Proponga un algoritmo basado en prioridades que permita que el proceso B finalice su ejecución

antes que el proceso C en el conjunto de procesos de la figura 1. Explique de forma clara y concisa el

funcionamiento de dicho algoritmo.

b.- Dibuje un cronograma que muestre el orden en que se ejecutarían los procesos siguiendo dicho

algoritmo.

3.- Explique la ventaja que tiene la implementación de threads a nivel de sistema operativo (kernel) en

vez de hacerlo a nivel de biblioteca de usuario. Dibuje un cronograma a partir del conjunto de procesos

de la figura 2, donde se vea un caso concreto que demuestre dicha ventaja. El cronograma se deberá

completar hasta la finalización de todos los threads contenidos en los procesos B y C. Además se deberá

indicar la política de planificación que se ha elegido para realizar dicho cronograma.


14

Figura 1

Proceso A

(* Programa principal *)

A1

IdB := CrearProceso (B, 1)

A2

IdC := CrearProceso (C, 2)

A3

Esperar_FinProceso (IdB)

Esperar_Fin_Proceso (IdC)

Proceso B


B1

E/S (200)

B2

E/S (200)

B3

Proceso C


C1

C2

C3

E/S (100)

C4

C5

C6

Figura 2

Proceso A


A1

IdB := CrearProceso (B, 1)

A2

IdC := CrearProceso (C, 2)

A3

Esperar_FinProceso (IdB)

Esperar_Fin_Proceso (IdC)

Proceso B

Procedure x1

B1

Procedure x2

B2


Idx1 := CrearThread (x1, 0)

Idx2 := Crearthread (x2, 1)

B0

Esperar_Fin_Thread (Idx1)

Esperar_Fin_Thread (Idx2)

B4

Proceso C

Procedure y1

C1

E/S (250)

C2

Procedure y2

C3


Idy1 := CrearThread (y1, 2)

Idy2 := Crearthread (y2, 1)

C0

Esperar_Fin_Thread (Idy1)

Esperar_Fin_Thread (Idy2)

C4


15


Examen Final de Sistemas Operativos I 8 de Junio de 2004

EJERCICIO 2 (3,5 puntos) Tiempo: 60 min.

Un ordenador tiene una memoria de 64MB. El sistema operativo gestiona la memoria por intercambio (swapping)

con particiones variables. El tamaño medio de los procesos es de 3MB y el tamaño medio de los huecos es de 2MB.

Por término medio, existen la mitad de huecos que de procesos. Este ordenador dispone de un disco que tiene 2048

cilindros, 24 pistas por cilindro, 256 sectores por pista y 512 bytes por sector. El tiempo medio de posicionamiento

es de 6‟9 ms. y el tiempo de rotación es de 8‟33 ms. Este ordenador es capaz de copiar 4 bytes en 40 nanosegundos

(de memoria a memoria).

(NOTA: cada respuesta debe incluir el desarrollo que ha llevado a la misma. No se aceptan respuestas en las que

sólo figure el resultado final).

Responder, de forma razonada, a las cuestiones siguientes:

1. [0‟7] Calcule cuál será, por término medio, el grado de multiprogramación.

2. [0‟2] Si por término medio un proceso pasa el 80% de su vida esperando por una entrada/salida, calcule la

utilización de la CPU si el grado de multiprogramación es el calculado en el apartado 1. (No considere el

tiempo que un proceso está esperando en el estado de preparado).

3. [0‟7] Suponga que existen 8 huecos (no adyacentes) de 2MB cada uno. Uno de tales huecos se encuentra en

el extremo superior de la memoria disponible para los procesos de usuario mientras que otro de esos huecos

se encuentra en el extremo inferior de dicha memoria. Ahora es necesario cargar (desde disco) un nuevo

proceso (de 3MB) en memoria y no se debe expulsar a ninguno de los ya cargados. Calcule el tiempo total

para ubicar en memoria a este nuevo proceso supuesto que el proceso se encuentra en sectores distribuidos

aleatoriamente por todo el disco. (Cuando se compacta se debe generar un único hueco a partir de todos los

huecos existentes. En los cálculos trabaje con una precisión de 3 decimales).

4. [0‟2] Si la unidad de asignación es de 4KB, calcule el tamaño (en bytes) del mapa de bits que mantiene la

información sobre memoria libre/ocupada.

Suponga ahora que sobre el ordenador anterior el sistema operativo gestiona una memoria virtual por paginación

con un tamaño de página de 8KB. La CPU genera direcciones virtuales de 32 bits. Indique:

5. [0‟2] Longitud (en bytes) de una entrada a la tabla de páginas. Cada entrada mantendrá un número de

marco, un bit de presencia/ausencia, un bit de ensuciado y un bit de referencia.

6. [0‟2] Tamaño de la tabla de páginas (en bytes).

7. [0‟3] Tamaño de la tabla invertida de páginas (en bytes).

8. [0,3] Si las páginas virtuales 0, 1 y 2 están cargadas en los marcos de página 4, 6 y 7 respectivamente, ¿cuál

es la dirección física correspondiente a la dirección virtual 8193 (decimal)?

9. [0,7] Suponga que la MMU utiliza una TLB. El tiempo de acceso a la TLB es de 0‟1 microsegundo, el

tiempo de acceso a la tabla de páginas es de 10 microsegundos y el tiempo de acceso a una palabra en

RAM es de 1 microsegundo. ¿Cuánto tiempo se tarda en, dada una dirección virtual, acceder a la dirección

física correspondiente si: a) la búsqueda se resuelve en la TLB; b) la búsqueda se resuelve en la tabla de

páginas? (Suponga que la TLB no está llena).


16


Examen Final de Sistemas Operativos I 17 de Septiembre 2001

EJERCICIO 3 ( 3,5 puntos) Tiempo estimado: 60m.

Se desea implementar una gestión de memoria virtual mediante paginación en un equipo informático. El bus de

direcciones es de 32 bits. La unidad mínima direccionable es un byte. La cantidad de memoria RAM (real)

instalada en el equipo puede ser variable. La cantidad mínima de memoria es de 4 MB y se puede incrementar en

potencias de 2 (es decir 4 MB, 8 MB, 16MB, 32MB,etc..., hasta un máximo). El tamaño de la página es de 4KB y

el del descriptor de página de 3 bytes. Se desea poder controlar si se ha accedido a una página, si se ha modificado,

así como también poder protegerla de lectura, escritura y ejecución.

Con estos datos en principio, supuesto que se dispone de suficiente memoria secundaria para dar soporte a la

memoria virtual y para un espacio de direccionamiento único se pide:

1) Especifique los formatos de dirección lógica (virtual) y de descriptor de página.

2) Escriba el tamaño de la tabla de páginas (en bytes)

3) Escriba la cantidad máxima de memoria real que puede manejar este Sistema (en bytes).

Para dar soporte a la memoria virtual se dispone de un dispositivo de almacenamiento secundario de 8GB, pero que

sólo tiene disponibles 2GB para memoria virtual. Estos 2GB están asignados a un fichero que se usará para guardar

las páginas. Los bloques de datos de este fichero no tienen por qué ser contiguos.

Cuando una página no se encuentra en memoria real, el campo “Número de marco” del descriptor de página guarda

el número de bloque del dispositivo de almacenamiento secundario donde reside la página. La numeración de

bloques del disco comienza en „1‟, así que se reserva el numero „0‟ para indicar que la página no tiene ningún

bloque asignado.

Con esta nueva información se pide:

4) Escriba la cantidad de memoria virtual máxima de la que se podría disponer (en bytes).

5) Escriba el tamaño que debería tener el bloque de almacenamiento secundario para dar soporte a la misma

(en bytes).

6) Describa un posible esquema de asignación de páginas a bloques, es decir, qué páginas se guardarían en los

bloques.

En principio se pensó en guardar la tabla de páginas completa en memoria y que las páginas que ocupase esta tabla

no pudieran ser seleccionables por el algoritmo de sustitución de páginas; de este modo la MMU podría resolver

fácilmente la traducción de páginas, yendo directamente con cada dirección a la tabla de páginas en memoria.

Debido al gran gasto de memoria se opta finalmente por que la tabla de paginas no tenga que estar completamente

en memoria principal, sino que pueda estar también paginada. Se pide:

7) Indique si modificaría o no la MMU para dar soporte a esta opción y en su caso en qué consistiría esta

modificación.

8) Describa en líneas generales cómo funcionaría la traducción de una dirección con esta opción.


17


Examen Final de Sistemas Operativos I 2 de julio de 2001


Se desea implementar un sistema operativo con multiprogramación (gestionando un máximo de 128

procesos) y memoria virtual paginada. Se debe tener en cuenta lo siguiente:

CPU con 32 bits para su conexión al bus de direcciones y un Registro de Reubicación.

Un disco de 2GB y sectores de 1KB, para usarlo en exclusiva como soporte de la memoria virtual.

Páginas de 4KB y Tabla de Páginas completa residiendo en Memoria Principal.

Un único espacio de direcciones virtuales para todos los procesos y lo más grande que se pueda.

La memoria virtual, en un momento dado, tiene el aspecto de la figura siguiente:

Una representación lógica de la lista doblemente encadenada sería la siguiente:

Donde el elemento “H1” describe el primer trozo de la memoria (primer hueco que abarca las páginas 0,

1 y 2), el elemento “Pi” describe el trozo de memoria virtual ocupado por un proceso (el Pi que abarca las

páginas 3, 4 y 5) y así sucesivamente.

Como no se desea trabajar con memoria dinámica, se decide implementar la lista anterior con un array de

un tamaño predeterminado (en principio el de la máxima fragmentación “número de trozos” en que puede

estar dividida la memoria virtual).

Para completar la implementación, se dispondrá de la variable “primero” que indicará cuál es el primer

elemento de la lista, de forma que la representación del estado de la memoria virtual de la figura mediante

el array podría ser la siguiente:

Donde sólo se indica el puntero al siguiente para no complicar el dibujo. Las posiciones del array no

utilizadas para describir los trozos actuales en que está fragmentada la memoria, se han expresado con

rectángulos sombreados.

Puede observarse que las tres primeras páginas están vacías (primer hueco H1), las tres páginas

siguientes están ocupadas por el proceso Pi, las cuatro siguientes están libres y las cinco

siguientes están ocupadas por el proceso Pk, y el resto de páginas se supone que están libres.

Se trata, entre otras cuestiones, de analizar si es más eficiente en ocupación de memoria el

gestionar la memoria virtual libre y ocupada mediante un mapa de bits o una única lista

doblemente encadenada tal que:

Los elementos de la lista (que incluye tanto la descripción de zonas de memoria libre

“huecos” como las ocupadas por procesos), están ordenados por dirección

Se usa el algoritmo NEXT FIT (siguiente que sirva) para asignar memoria a un

proceso.

H3

H1

H2

Pi

Pk

primero H1 Pi H2 Pk H3

N 0 1 2 3 4 5 6 7 primero

Pk

2

H1 H2 H3 Pi


18

Se pide:

1. Razonar sobre la eficiencia de memoria del mapa de bits frente a la lista encadenada:

a. Indicar razonadamente cuál sería el tamaño del mapa de bits expresado en bytes.

b. Recordando que el sistema puede gestionar un máximo de 128 procesos concurrentemente, razonar

si el número máximo de trozos en que puede estar dividida la memoria virtual es 256 ó 257.

c. Indicar los campos (con su significado) que tendría cada elemento del array de la lista.

d. Supuesto que los campos anteriores tienen que ocupar cada uno de ellos un número de bytes entero

(1, 2, 3, etc.) y eligiendo siempre el valor menor para poder representar cada campo, indicar el

tamaño total (en bytes) que ocuparía el array donde se implementaría la lista encadenada.

2. Indicar qué información debería guardarse en el descriptor de cada proceso (tanto para el caso del

mapa de bits como el de lista encadenada) para que cuando un proceso termine, pueda liberarse la

zona de memoria virtual ocupada por el proceso. Poner como ejemplo el caso del proceso Pk de la

figura.

3. Cuando un proceso termina, en el caso de gestión con mapa de bits, básicamente habría que hacer:

Poner a 1 los bits del mapa de bits que se correspondan con las páginas ocupadas por el proceso

Poner en la Tabla de Páginas, P=0 en todos los descriptores de las páginas ocupadas por el

proceso

Invalidar las entradas de la caché de la MMU que tengan descriptores de páginas del proceso

Liberar el descriptor utilizado para gestionar el proceso

Indicar de forma parecida (solo que para el caso de gestión mediante lista encadenada), qué deberá

hacer el sistema operativo cuando se desee crear un proceso cuyo ejecutable resida en el Sistema de

Ficheros (por ejemplo en /ejemplos/ejecutable.exe). En el caso de utilizar una expresión del estilo: “se

inicializa tal variable”, deberá concretarse a qué valor se inicializa. NO CONSIDERAR LOS

CASOS DE ERROR.

4. Indicar (también para lista encadenada) qué deberá hacer el sistema operativo si decide compactar la

Memoria Virtual. Poner como ejemplo el caso de la figura en la que tan sólo existen el proceso Pi y

Pk.


19

E.U. de Informática Departamento de Informática Aplicada

Examen final de Sistemas Operativos I 12 de diciembre de 2001

EJERCICIO 2. (puntuación 3’5 puntos) Tiempo Estimado 60 m

Un sistema operativo usa un sistema de memoria virtual paginada con direcciones virtuales de 32 bits y

con páginas de 4KB. La tabla de páginas reside completamente en memoria principal, siendo el tamaño

del descriptor de cada entrada de la tabla de páginas de 32 bits.

El espacio virtual es único por proceso, aunque ningún proceso llega a necesitar más de 16 MB. De este

espacio, 12 MB se utilizan para almacenar el área de código más el área de datos a partir de la dirección

virtual 0. Los 4 MB restantes se destinan al espacio de pila, que se almacena comenzando en la dirección

virtual más alta y creciendo hacia direcciones bajas.

1. ¿Cuánto ocupa la tabla de páginas? (0,25 puntos)

2. ¿Cuál es la ocupación útil (entradas ocupadas) en % de la tabla de páginas? (0,25 puntos)

Posteriormente, se decide usar un sistema de tablas de dos niveles, como se muestra a continuación.

Una dirección virtual se interpreta de la siguiente manera: Los 10 bits de mayor peso sirven para

seleccionar la entrada de la tabla de primer nivel. Esta entrada contiene el número del marco donde reside

la tabla de páginas de segundo nivel. Los 10 bits siguientes se usan para seleccionar una entrada de la

tabla de segundo nivel. Esta entrada contiene el número del marco donde está cargada la página. Una vez

localizado el marco, solo hace falta sumarle los 12 bits del desplazamiento de la dirección virtual.

Tabla de páginas

de primer nivel

Tablas de páginas

de segundo nivel

Marcos de

página

marco

Entrada de 1er

nivel Entrada de 2º nivel Desplazamiento

10 bits 10 bits 12 bits


20

Supuesto un proceso de este sistema, que ocupa como máximo 16 MB, y sabiendo que la tabla de primer

nivel siempre está cargada en memoria durante la ejecución del proceso, mientras que las tablas de

segundo nivel se cargan bajo demanda, responda razonadamente a las siguientes preguntas:

3. ¿Qué tamaño tiene cada una de las tablas? (0,25 puntos)

4. ¿Cuántas tablas de segundo nivel utiliza el proceso? ¿Qué índices se ocupan de la tabla de primer

nivel? (0,5 puntos)

5. ¿Cuánto espacio de memoria se necesita para almacenar simultáneamente todas las tablas necesarias?

(0,25 puntos)

6. ¿Qué ventaja tiene este sistema con respecto al de una sola tabla de páginas? (0,25 puntos)

7. ¿Qué inconveniente presenta este modelo si la MMU no dispone de TLB? (0,25 puntos)

El registro base de la tabla de páginas del proceso (RBTP) indica que la tabla de primer nivel está cargada

a partir de la dirección física $F2000. La dirección física tiene un tamaño de 24 bits.

El formato de descriptor, que ocupa 32 bits, tanto de la tabla de primer nivel como de las de segundo

nivel, es el siguiente:

Nº de marco (12 bits) Reservado (19 bits) Bit de presencia

En un momento dado, el contenido de ciertas direcciones de memoria principal, en hexadecimal, es el

siguiente:

Dir. Física 4 BYTES

$0F2000 100F...1

$0F2100 1F30...4

$0F2FFC 0F40...1

$0F3000 0C8F...0

$0F30C8 1013...5

$0F3FFC 1013...4

$0F4000 0F42...1

$0F4C78 1F52...1

$0F4FFC 0F41...8

$1F5000 A041...8

8. Dada la dirección virtual $FFF1E703, describa detalladamente los pasos que hay que seguir y las

direcciones involucradas, para traducir la anterior dirección virtual en una dirección física. ¿Qué

dirección física ha obtenido? (1,5 puntos).


21


Examen Final de Sistemas Operativos I 14 de junio de 2003


Se desea implementar un sistema operativo con multiprogramación y memoria virtual paginada con las

características siguientes:

Un único espacio de memoria virtual de 4GB a compartir por todos los procesos que se creen.

El bus de datos es de 32 bits.

MMU con caché interna (TLB) de 64 entradas que incluyen los bits R (Referenciada) y M (Modificada).

Una memoria principal de 512MB.

Páginas de 8KB.

Tabla de Páginas Invertida cargada completamente en memoria principal.

Mapa de Bits para llevar el control de la memoria virtual libre y ocupada.

Algoritmo LRU (aproximado) como política de sustitución de páginas.

Una Tabla de Páginas Invertida tiene una entrada por cada marco de memoria. Cada entrada indica, entre

otras cosas, la página que está cargada en el marco correspondiente.

Responder, de forma razonada, a las cuestiones siguientes:

1. Indicar el formato (campos con su significado y tamaño en bits) de un descriptor de la Tabla de

Páginas Invertida (supuesto que cada descriptor debe ocupar un número entero de bytes) y

calcular el tamaño en bytes de dicha tabla.

2. Indicar el tamaño en bytes que ocupa el Mapa de Bits que lleva el control de la memoria virtual

libre y ocupada.

3. Indicar el tipo de estructura de datos que se crea más aconsejable para llevar el control de la

memoria principal libre y ocupada (marcos de página) de forma que se agilice la búsqueda de un

marco libre cuando se produzca falta de página. Calcular el tamaño en bytes de esta estructura

supuesto que una variable o campo de una estructura debe ocupar un número entero de bytes.

4. Cuando se utiliza únicamente una Tabla de Páginas clásica (no invertida y no multinivel) que está

cargada en memoria principal y una MMU que cuenta con RBTP (Registro Base de la Tabla de

Páginas) así como su correspondiente TLB, el número máximo de accesos a memoria principal

cuando se intenta acceder a una dirección virtual que pertenece a una página presente en memoria

principal es de tres. Indicar cuándo se produce esta situación y a qué se deben los tres accesos.

5. Cuando se utiliza una Tabla de Páginas Invertida, como en nuestro caso, la situación descrita en el

punto anterior (4), en general, no puede resolverse con tan sólo tres accesos a memoria principal.

Indicar por qué y cuál podría ser (con los datos del enunciado) el número máximo de accesos a

memoria principal.

6. Para poder implementar, de forma aproximada, el algoritmo de sustitución de páginas LRU, se

dispone de una interrupción periódica (sea “intLRU”) que hace que tome control el Sistema

Operativo (a través de la rutina de tratamiento de dicha interrupción). Se supone que cuando

sucede “intLRU”, la MMU vuelca el contenido de la TLB en una zona de memoria conocida por

el Sistema Operativo (sea “tablaTLB” definido como un array de 64 descriptores con el formato

del apartado 1).

a. Indicar someramente en qué podría consistir la aproximación al algoritmo LRU.

b. Indicar qué estructuras de datos podrían modificarse o añadirse para soportar la

aproximación al algoritmo LRU descrita en 6.a.

c. Indicar en pseudocódigo el contenido de la rutina de tratamiento de la interrupción

“intLRU”.


22


Examen Final de Sistemas Operativos I 15 de Diciembre de 2004

EJERCICIO 3 (3,5 puntos) Tiempo Estimado: 60 m

Un sistema operativo ofrece a los usuarios un esquema de gestión de memoria en donde el espacio lógico de un

proceso consiste en una colección de bloques de tamaño variable, denominados segmentos, repartidos por la

memoria física. Ahora, la imagen de un proceso se divide en segmentos (por ejemplo: de código, de datos y de

pila). Cada segmento ocupa un bloque en memoria principal de tal forma que las direcciones lógicas que genera la

cpu son del tipo <Número de segmento, desplazamiento>. Como se puede ver en la figura, la

traducción de la dirección lógica (s,d) a una dirección física df se realiza con la ayuda de una tabla de

segmentos por proceso, que reside en memoria principal. El número de segmento s es el índice en la tabla de

segmentos para obtener la entrada que contiene la dirección física b donde comienza el segmento, a la cual se le

suma el desplazamiento d para obtener df.

cpu ds ds

b

Memoria física

b

+

Tabla de segmentos

df

Base

Se pide:

1. Explique por qué es posible el acceso a direcciones fuera de un segmento.

2. Indique qué modificaciones propone al modelo anterior para que se controlen los accesos indebidos. Dibuje

de nuevo la figura con las modificaciones propuestas.

3. Si el mapa (en decimal) de segmentos de un proceso en la memoria física es el mostrado a continuación,

indique qué valores tendrían los elementos de la tabla de segmentos supuesto el punto 2.

s0 s3 s2 s4 s1

1400

2400

3200

4300

4700

5700

6300

6700

0000

4. Escriba las tablas de segmentos de dos procesos en donde se vea que comparten el bloque contenido en el

segmento 2. ¿Tienen que llamarse con igual número de segmento en los dos procesos?

5. Justifique si este modelo de gestión de memoria sufre de fragmentación externa y/o interna.

Se modifica el esquema de la figura de tal manera que los segmentos están paginados en disco, por lo que

ahora la memoria principal está dividida en marcos. Cada segmento cuenta con una tabla de páginas. El

contenido de la tabla de segmentos se modifica ya que la entrada de un segmento s, no contiene la dirección de

inicio del segmento b, sino la dirección de comienzo de la tabla de páginas tp del segmento.

6. Explique y dibuje un esquema parecido al de la primera figura en donde se vea la traducción de una

dirección <s,d> en una dirección física.

7. Justifique si este modelo sufre de fragmentación externa y/o interna.

8. En el caso de que no existiera TLB, ¿cuántos accesos a memoria como mínimo hay que realizar con este

esquema? Justifique la respuesta.


23



EJERCICIO 3 (3,5 puntos) Tiempo Estimado: 60 m

Sea un disco que tiene 1200 cilindros, 16 pistas por cilindro, 56 sectores por pista, 512 bytes por sector y una velocidad de

6000 rpm (revoluciones por minuto). Está formateado con interleaving=1. Entre dos sectores adyacentes hay un espacio de

relleno (gap) de 1/8 el tamaño del sector; es decir, después del último byte de un sector y antes del primer byte del siguiente,

hay 64 bytes de relleno (ver figura).

sector 1 sector 2sector 29 sector 30 sector 28 sector 56……..

gap

El tiempo de posicionamiento del brazo viene dado por la expresión t = 1 + (0,5 * d) (expresado en milisegundos) siendo d la

distancia en cilindros desde el origen al destino.

Notas:

Para todos los apartados, inicialmente la cabeza lectora/grabadora se supone situada en el cilindro 0 y al principio

del sector 1.

La numeración de cilindros y pistas empieza por 0 y la de sectores por 1.

El cylinder skew (sesgo) es de 0

SE PIDE:

1) [1 punto] Calcule la mínima velocidad de transferencia (del controlador a memoria) que requiere este disco. Es decir (y en

relación con la figura anterior) en el tiempo que tardan en pasar por debajo de la cabeza lectora/grabadora: el gap del

sector 1, el sector 29 y el gap del sector 29, se ha tenido que transferir el sector 1 desde el buffer de la controladora hasta

memoria. Suponga que el bus está siempre disponible para realizar la transferencia y que el tiempo de comprobación del

checksum es despreciable. Exprese el resultado en bits por segundo. En los cálculos opere con la mayor precisión decimal

posible.

2) [1 punto] En un momento dado, en la cola de peticiones de disco existen las siguientes dos peticiones (por orden de

llegada):

1. Cilindro 49, pista 0, sector 15

2. Cilindro 49, pista 10, sector 44

Calcule el tiempo total invertido en completarlas siguiendo el algoritmo FCFS. Tenga en cuenta los tiempos de

posicionamiento, espera de rotación y transferencia (suponga la misma velocidad de transferencia que la calculada en el

apartado anterior). La distribución de sectores en una pista de 56 sectores con interleaving=1 es: 1, 29, 2, 30, 3, 31, 4, 32,

5, 33, 6, 34, 7, 35, 8, 36, 9, 37, 10, 38, 11, 39, 12, 40, 13, 41, 14, 42, 15, 43, 16, 44, 17, 45, 18, 46, 19, 47, 20, 48, 21, 49,

22, 50, 23, 51, 24, 52, 25, 53, 26, 54, 27, 55, 28, 56.

3) [1,5 puntos] Se cambia el disco por otro similar en el que la función de tiempo de posicionamiento viene dada por la

expresión t = 0,8*d (expresado en milisegundos) y el número de sectores ha cambiado a 50 por pista (manteniéndose igual

el resto de datos). La distribución de sectores en una pista de 50 sectores con interleaving=1 es: 1, 26, 2, 27, 3, 28, 4, 29, 5,

30, 6, 31, 7, 32, 8, 33, 9, 34, 10, 35, 11, 36, 12, 37, 13, 38, 14, 39, 15, 40, 16, 41, 17, 42, 18, 43, 19, 44, 20, 45, 21, 4 6, 22,

47, 23, 48, 24, 49, 25, 50. Se pide:

1. Determinar el orden en el que se atenderán las siguientes dos peticiones de disco pendientes aplicando el

siguiente algoritmo de planificación del brazo de disco: “la siguiente petición a atender es aquella que se

encuentre más cerca: se tarde menos en llegar al cilindro y sector solicitado”. Petición 1: cilindro 0, pista 6,

sector 21; Petición 2: cilindro 5, pista 3, sector 16

2. Para cada petición, indique el tiempo necesario para posicionarse sobre el cilindro, pista y sector solicitados.


24

E.U. de Informática Departamento de Informática Aplicada

Examen Final de Sistemas Operativos I 13 de septiembre de 1996

PROBLEMA 3 (3´5 PUNTOS) 75 Minutos

Se dispone de un sistema de ficheros de un determinado sistema operativo (tipo UNIX) con bloques de

1Kbyte, soportado por un disco de 64Mbytes, que tiene las siguientes características :

1. El formato lógico del disco tiene la estructura :

Bloque de

autoarranque

Superbloque

Nodos-i

Mapa de bits

de nodos-i

Mapa de bits

de bloques

Bloques de

datos

...... ... ... ...

Bloque de autoarranque (bloque 0): reservado para el sistema

Superbloque (bloque 1) : que contiene la descripción de la estructura del sistema de ficheros. Entre

otras cosas, en nuestro caso indica que existen 10.000 nodos-i.

Mapa de bits de nodos-i : para saber qué nodos-i están asociados a algún fichero y cuáles están

libres (el i-nodo 0 aparece como asignado desde que se formatea el disco. No se utiliza para ningún

fichero)

Mapa de bits de bloques : para controlar los bloques libres y asignados del disco (el bit 0 indica si

el bloque 0 está asignado o libre, el 1 si el bloque 1 está asignado o libre,...)

Nodos-i : con la siguiente estructura :

2. Tanto los nodos-i como los bloques de datos se asignan de forma ascendente.

3. Las entradas de un directorio ocupan 16 bytes. Cada entrada consta de dos campos :

Número de

nodo-i

Nombre del

fichero

2 bytes 14 bytes

Características

del fichero

7 bloques

directos

Indirecto simple

Indirecto doble

El tamaño de un nodo-i es de 32 bytes y el de una

dirección de bloque es de 2 bytes. Puede haber más de

un nodo-i en un bloque de disco. Aunque el nodo-i 0

no se utiliza, los 32 primeros bytes del primer bloque

de nodos-i están reservados para él.


25

Cuando se crea un directorio, este siempre consta de las entradas “.” y “..”, que hacen referencia al propio

directorio y al directorio padre respectivamente.

Suponiendo que el disco está vacío, INDICAR:

a) Número de bloques que ocupa el mapa de bits de bloques

b) Número de bloques que ocupa el mapa de bits de i-nodos

c) Numero de bloques que ocupan los nodos-i

d) Tamaño máximo que podría tener un fichero que colgase directamente del directorio raíz

En un momento dado se crea la siguiente jerarquía de directorios en el disco :

d1

a

d2

b

/ -> fecha de creación : 1-enero-96

d1 -> fecha de creación : 2-enero-96

d2 -> fecha de creación : 5-enero-96

a -> fecha de creación : 3-enero-96 ; tamaño : 1026 bytes

b -> fecha de creación y tamaño : 10-enero-96 ; tamaño : 7170 bytes

Teniendo en cuenta las fechas de creación de cada uno de los directorios y ficheros (creados de

forma secuencial), INDICAR :

e) En qué bloques de datos se encontrará la información de cada uno de ellos y qué número de i-nodo

tienen asociado.


26




Se pretende comparar ciertos aspectos de las implementaciones del sistema de ficheros en sistemas

operativos del tipo Unix y MS-DOS. En cada uno de los sistemas, el formateo lógico de un mismo disco

daría como resultado respectivamente las estructuras lógicas que se describen a continuación. El tamaño

del bloque, para ambos sistemas, es de 1Kb.

Bloque de

autoarranque

FAT Bloques de

entradas del

Directorio Raíz

Bloques de

datos

...... ... ... 0 1 n 1 1 2

Entre otras informaciones, el bloque de autoarranque contiene:

Máximo nº entradas que puede contener el directorio raíz

Número de bloques que ocupa la FAT

Una entrada de directorio, ocupa 32 bytes y presenta el siguiente aspecto:

Primer bloque

de datosNombre del

fichero

Tipo del

fichero:

D/F

Tamaño en

bloques

FAT 0 1 2 3 4 5 6 7 8 … n-2 n-1 n

Los dos primeros bloques de datos (0 y 1) están reservados por el sistema, por lo que la primera entrada

útil es la 2. Una entrada con un 0 indica bloque libre, y con la marca <EOF>, fin de fichero.

UNIX:

Bloque de

autoarranque

Superbloque

Nodos-i

Mapa de bits

de nodos-i

Mapa de bits

de bloques

Bloques de

datos

...... ... ... ... m 1 0

MS-DOS

El Tipo de fichero indica

si es un directorio (D) o

un fichero (F).


27

Bloque de autoarranque: reservado para el sistema

Superbloque: contiene, entre otras cosas, el número máximo de nodos-i.

Mapa de bits de nodos-i: indica nodos-i que están libres o asociados a ficheros. Los nodos-i se

numeran desde 0, pero el primer nodo-i útil es el 1, ya que el 0 no se utiliza.

Mapa de bits de bloques: indica bloques libres y asignados del área de datos del disco, comenzando

desde el bloque 0.

Nodos-i: ocupan 32 bytes y las entradas de directorio 16 bytes, tal y como se ve a continuación:

Indirecto simple

Indirecto doble

7 bloques

directos

Permisos rwx

Propietario

Fechas

Tamaño en

bloques

Tanto los nodos-i como los bloques de datos se asignan de forma ascendente.

En ambos sistemas, al crear un directorio se incluyen siempre las entradas “.” y “..”, que hacen referencia al propio

directorio y al directorio padre respectivamente.

Se pide:

1. Para cada sistema, indique el número máximo de ficheros o directorios que se pueden crear.

2. Sea el siguiente árbol, cuyo orden de creación ha sido /, d1, d2, a y b. Los ficheros a y b ocupan 1

bloque de datos cada uno.

d1

a

d2

b

a) En el caso de MS-DOS, rellene las estructuras mostradas en la hoja de respuestas con el contenido

de las entradas significativas de la FAT (las que indican bloques ocupados) y el contenido de cada

uno de los directorios, incluido el directorio raíz. (Los bloques del directorio raíz numérelos DR1,

DR2, …etc.).

b) En el caso de Unix, muestre, igualmente, el contenido de los nodos-i ocupados y el contenido de

cada uno de los directorios, incluido el directorio raíz.

3) Explicar razonadamente para ambos sistemas cuál sería el mínimo número de bloques que hay que leer

(indicar cuáles) para obtener el contenido del fichero /d2/b, supuesto conjuntamente que:

a) En MS-DOS la FAT está ya cargada memoria.

b) En Unix se accede al nodo-i correspondiente para leer el contenido de un fichero o directorio.

c) En ambos sistemas, no hay ningún tipo de información almacenada en memoria de ningún fichero o

directorio.

Nº de nodo-i Nombre del fichero

Entrada de directorio


28




Tenemos un sistema de ficheros tipo unix con las siguientes características: disco de 32Gbytes, bloques de 512

bytes, i-nodos de 64 bytes con 6 punteros directos y 2 indirectos simples, los i-nodos se almacenan en los bloques

de disco del 100 al 20.100, el mapa de i-nodos ocupa los bloques del 20.101 al 20.140. El sistema operativo carga

en memoria el i-nodo de un fichero cuando se realiza la operación de abrir fichero sobre él y lo mantiene hasta que

se cierra el fichero.

a) Se quiere controlar la ocupación de todo el disco mediante un mapa de bits que se almacenará a

partir del bloque 22.000. Calcula el tamaño que debería tener (en bytes) e indica qué bloques

ocupará.

En el sistema anterior tenemos un fichero, cuya ruta completa es “/lrod/btxai”, que ocupa 4600 bytes. Los

directorios “/” y “lrod” tiene asignados los i-nodos 1 y 5 respectivamente y los bloques de datos 40.000 y 40.001

respectivamente. Inicialmente solo está cargado en memoria el i-nodo de “/”. El fichero “btxai” tiene asignado el i-

nodo 12 y los bloques lógicos que contienen los datos de este fichero están almacenados en los siguientes bloques

físicos:

Nº Bloque lógico 0 1 2 3 4 5 6 7 8

Nº Bloque físico 81000 81002 81003 54500 54501 54502 77600 77601 77602

Si se necesita algún otro bloque para la gestión de la información del fichero se utilizan los bloques físicos a partir

del 99.000.

b) Suponemos que el sistema no tiene ningún buffer en memoria para almacenar un bloque leído del

disco; es decir, después de leer un bloque coge la información necesitada, la entrega y desecha dicho

bloque. Indica a qué bloques del disco van a acceder las llamadas open, lseek y read del programa 1.

Se deberá especificar el orden en que se accede a ellos y cuántas veces se va a realizar la lectura y/o

escritura del bloque en el disco.

Para mejorar el tiempo de acceso se decide implementar una cache para bloques de disco. Esta cache consistirá en

un buffer en memoria principal que contiene los últimos 5 bloques de disco a los que se ha hecho referencia,

siguiendo una política FIFO para la sustitución de bloques. A continuación se indican algunos aspectos del

funcionamiento de la cache de bloques:

- Varios procesos pueden estar accediendo simultáneamente a un mismo bloque. El sistema no expulsará de la

cache a un bloque que está siendo utilizado en un momento dado.

- El sistema operativo tiene un proceso que periódicamente actualiza en el disco el contenido de los bloques

cargados en la cache que considera necesarios.

- En el sistema puede haber distintas particiones con tamaño de bloque físico distinto. Se desea que el sistema de

cache de bloques sirva para almacenar bloques procedentes de distintas particiones.

c) Supongamos que para gestionar la cache de bloques el sistema tiene un descriptor para cada uno de

los 5 buffers que la componen. Indica qué campos debe contener un descriptor de buffer y la utilidad

de cada uno de los campos.

Programa 1

df = open(“/lrod/btxai”) /* abre el fichero */

lseek (df, 2304) /* avanza el puntero del fichero 2304 bytes */

for i = 1 to 512 do

read (df, destino, 4) /* lee 4 bytes a partir de la posición actual */

destino = destino + 4 /* y los deja en destino */

... /* trabaja con los datos */

end for;

close (df);


29



EJERCICIO 3 (puntuación 3’5 puntos) Tiempo Estimado 60 m

Un sistema operativo trabaja sobre un disco que cuenta con las siguientes características: 600 cilindros,

16 pistas por cilindros, 36 sectores por pista, 512 bytes por sector. La numeración de cilindros, pistas y

sectores comienza en 0. Inicialmente, la cabeza lectora/grabadora está situada en el cilindro 0, pista 0,

sector 0. La velocidad de rotación es de 6000 revoluciones por minuto. El tiempo de posicionamiento

entre cilindros consecutivos es de 1 ms. La controladora cuenta con un buffer interno de 512 bytes donde

almacena los bits que se van leyendo según pasan por debajo de la cabeza lectora/grabadora y cuando

finaliza la lectura de un sector comienza a transferirlo a la memoria RAM. El factor de interleaving es de

4, es decir entre dos sectores lógicamente consecutivos se intercalan otros cuatro. La distribución de

sectores en una pista sería la siguiente:

0,29,22,15,8,1,30,23,16,9,2,31,24,17,10,3,32,25,18,11,4,33,26,19,12,5,34,27,20,13,6,35,28,21,14,7.

El tiempo de transferencia de un sector almacenado en el buffer del controlador a memoria principal

coincide con el de la lectura de un sector.

El driver de disco del sistema operativo define bloques físicos cuyo tamaño coincide con el del sector.

Los numera desde 0 de manera secuencial, de tal forma que ofrece una visión del disco como una

secuencia lineal de bloques. Así, por ejemplo, el bloque 35 se sitúa en el cilindro 0, pista 0 y sector 35. El

bloque físico 36 se sitúa en el cilindro 0, pista 1, sector 0, etc. El factor de interleaving solo es visible al

controlador y es transparente al driver del disco, que ve los sectores del disco como si fuesen

consecutivos.

Por otra parte, el sistema de ficheros mantiene un árbol en que un fichero datos.txt tiene como primer

bloque de datos el bloque físico 7.

Se pide:

1. Indique en qué cilindro pista y sector se sitúan los bloques 40 y 43600.

2. Si el sistema de ficheros utiliza el sistema de almacenamiento contiguo para los bloques de un

fichero. ¿Cuánto tiempo se empleará en leer los dos primeros bloques del fichero datos.txt?

Considere que este tiempo está formado por el tiempo de posicionamiento + tiempo de latencia +

tiempo de transferencia desde el disco a la controladora + tiempo de transferencia desde la

controladora a la memoria principal.

3. Repita el apartado anterior si el sistema de ficheros utiliza la tabla FAT siguiente:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 …

3 14 L Eof 40 72 300 L L Eof … 5 33 …

L = bloque libre.

Eof = fin de fichero.

sistemas operativos - etsisi.upm.es · a continuación se presenta una selección de problemas que...

Documents