Ejercicios Capitulo 5

6-) Considere la siguiente gráfica de recursos dirigidos:

a) ¿Está en bloqueo mutuo este sistema?
No
b) ¿Existen procesos bloqueados?
No.
c) ¿Cuál es la gráafica resultante después de la reducción por P1?

d) ¿Qué gráfica resulta después de la reducción por P2?

e) Tanto P1 y P2 han solicitado R2:

1) ¿Cuál es el estado del sistema si la solicitud de P2 se concede antes de la P1?
P1 quedaría bloqueado hasta que P2 termine.
2) ¿Cuál es el estado del sistema si se responde la solicitud de P1 antes de la de P2?
P2 quedaría bloqueado hasta que P1 termine.

7) Considere la siguiente gráfica de recursos dirigidos:

a) ¿Este sistema está completamente en bloqueo mutuo?
No
b) ¿Existen algunos procesos bloqueados?
Si
c) Tres procesos, P1, P2 y P3,solicitan recursos de R2.

1) ¿Qué solicitudes satisfaría usted para minimizar el número de procesos que intervienen en el bloqueo mutuo?
Satisfaceria a P3

2) ¿Qué solicitudes satisfaría para maximizar el número de procesos participantes en el bloqueo mutuo?
A P3 le daria los recursos que necesita

d) ¿Se puede reducir la gráfica en forma parcial o total? Explique su respuesta.
Si, si a P3 se le asignan los recursos que necesita cuando este acabe los otros tendran todos los recursos necesarios para acabar su tarea

e) ¿Se puede resolver el bloqueo mutuo sin seleccionar una víctima? Explique su respuesta.: No, porque los recursos existentes no son suficientes para satisfacer todas las necesidades.

8) Considere un sistema de cómputo con 13 unidades de cinta. Todos los trabajos que se ejecutan en este sistema requieren un máximo de cinco unidades de cinta para completar, pero cada uno se ejecuta durante varios periodos con cuatro unidades y solicita la quinta sólo al final de la ejecución. La corriente de trabajos es sin fin.

a) Si su sistema operativo soporta una política de asignación de dispositivos muy conservadora, no comenzará trabajo alguno, a menos que se le hayan asignado las cintas que va a requerir durante toda su ejecución:

1) ¿Cuál sería el máximo de trabajos que pueden estar activos al mismo tiempo?
2 Trabajos.
2) ¿Cuál es el mínimo y el máximo de unidades de cinta que pueden estar ociosas como resultado de esta política? Pueden estar ociosas 3 unidades de cintas.

3) Explique su respuesta.
Como necesita asignar todas las cintas antes de comenzar la tarea solo podra asignar a 2 tareas y solo se utilizaran 10 cintas a la ves. Por tanto 3 unidades de cintas quedan ociosas.

b) Si su sistema operativo soporta el algoritmo del banquero:

1) ¿ Cual es el máximo de trabajos que pueden estar en progreso al mismo tiempo?
Con este algoritmo pueden haber diversos trabajos en progreso.

2) ¿Cuál es el número mínimo y máximo de unidades de cinta que puede estar ociosas como resultado de esta política?
Pueden haber varias unidades ociosas.

3) Explique su respuesta.
Con este algoritmo el sistema asigna las unidades de cintas en medida que sean necesarias.

9-11) En los tres sistemas descritos en los ejercicios del 9 al 11, donde los dispositivos son del mismo tipo, utilice las definiciones presentadas en el análisis del algoritmo del banquero para responder estas preguntas:

a) Determine las “necesidades restantes” de cada trabajo en cada sistema.
b) Indique si cada sistema es seguro o inseguro.
c) Si el sistema está en estado seguro, liste la secuencia de solicitudes y de liberaciones que permitirá la ejecución total de todos los procesos.
d) Si el sistema está en un estado inseguro, muestre cómo es posible que ocurra un bloqueo mutuo.

9) El sistema A tiene 12 dispositivos y sólo uno está disponible.

b) El sistema está en estado seguro ya que puede satisfacer las necesidades del trabajo No. 1.

c) · El trabajo 1 toma el dispositivo restante, termina y libera los 6.
· El trabajo 2 y 3 toman los dispositivos que necesitan, terminan y liberan los dispositivos. · El trabajo 4 toma los dispositivos necesarios y termina.

10) El sistema B tiene 14 dispositivos y nada más dos están disponibles.

a) El sistema esta en estado inseguro, ya que con solo 2 dispositivos disponibles no puede satisfacer ninguna de las necesidades.

b) Puede ocurrir un bloqueo si cualquiera de los procesos solicita los dispositivos que faltan para continuar con su tarea.

11) El sistema C tiene 12 dispositivos y solamente dos están disponibles.

Ejercicios Capitulo 4

5. El diagrama que sigue (adaptado de Madnick & Donovan, 1974) es un modelo de procesos simplificado de usted, en el cual solamente hay dos estados: dormido y despierto.

Usted efectúa la transición de despierto a dormido cuando está cansado, y de dormido a espierto cuando suena la alarma del reloj.

A) Agregue tres estados adicionales al diagrama (por ejemplo, uno podría ser comer).

B) Enuncie todas las transiciones posibles entre los cinco estados.
Aburrido, hambriento, arreglando la mesa, cansado, alarma de reloj.

6. ¿Cuál es la relación entre el tiempo de retorno, tiempo de ciclo CPU y tiempo de espera? Escriba, si es posible, una ecuación para expresar esta relación.
El tiempo de retorno es el tiempo que un proceso dura en volver, el ciclo de CPU es el tiempo que dura el proceso en realizarse y el tiempo de espera es el tiempo que tiene que esperar el proceso para ser atendido.
Tiempo total del proceso = Tr + Tc + Te

7. Dada la información siguiente:

Dibuje una línea de tiempo para cada uno de los siguientes algoritmos de planificación (puede resultar útil calcular primero en tiempo de inicio y de terminación para cada tarea).

A) FCFS

B) SJN

C) SRT

D) Round robin (con un quantum de tiempo de 2, ignore el cambio por contexto y las esperas naturales).

8. Con la información del ejercicio 7, complete el diagrama calculando el tiempo de espera y el tiempo de retorno para cada uno de los trabajos de los siguientes algoritmos de programación (ignore la carga general por cambio por contexto).

A) FCFS

B) SJN

C) SRT

D) Round robin (con un tiempo de quantum de 2)

Ejercicios Capitulo 3

6. Dado que la memoria principal está compuesta por tres marcos de página para uso público y que un programa solicita páginas de la forma siguiente:d c b a d c e d c b a e
a) Utilice el algoritmo de eliminación de páginas FIFO para analizar el rastreo de página. Para esto, marque con un asterisco (*) las fallas de página. Después calcule las relaciones de falla y de éxito.

Relación de falla = 9/12 = 75%
Relación de éxito = 3/12 = 25%

b) Incremente el tamaño de la memoria de manera que contenga cuatro marcos de página para uso público. Con las solicitudes de página del inciso a) y FIFO, vuelva a analizar el rastreo de página y calcule las relaciones de fallas y éxitos.
Relación de falla = 10/12 = 83%
Relación de éxito = 2/12 = 17%

c) ¿Correspondió el resultado con su intuición? Explique.No, al tener 1 marco de página más que el ejercicio anterior yo pensaba que las fallas de página sería menor.

7. Dado que la memoria principal está compuesta por tres marcos de página para uso público y que un programa solicita páginas en el orden siguiente:a b a c a b d b a c d
a) Utilice el algoritmo de eliminación de páginas FIFO para analizar el rastreo de páginas. Indique las fallas de páginas con un asterisco (*). Después calcule las relaciones de falla y de éxito.
Relación de falla = 5/11 = 45%
Relación de éxito = 6/11 = 55%

b) Con el algoritmo de eliminación de páginas LRU analice el rastreo de páginas y calcule las relaciones de fallas y de éxitos.

Relación de falla = 6/11 = 55%
Relación de éxito = 5/11 = 45%

c) ¿Cuál es mejor? ¿Por qué piensa que es mejor? ¿Se pueden emitir enunciados generales a partir de este ejemplo? ¿Por qué sí o por qué no?Para este caso en particular el mejor algoritmo es el FIFO, ya que en relación de falla fue menor que el LRU. El FIFO obtuvo un mejor rendimiento.

d) Definamos el “uso más reciente” (MRU) como un algoritmo de eliminación de página, que suprime de la memoria la página de uso mas reciente. Analice el rastreo de página utilizando las solicitudes de página de antes y calcule las relaciones de fallas y de éxitos.

Relación de falla = 6/11 = 55%
Relación de éxito = 5/11 = 45%

e) ¿Cuál de los tres algoritmos de eliminación de página es el mejor y por qué lo cree así?Para este ejemplo el algoritmo FIFO ya que entre los 3 es el que menos fallas de página obtuvo.

8. Para implementar un LRU, cada página necesita un bit de referencia. Si deseamos implantar un algoritmo de eliminación de páginas de uso menos frecuente (LFU), en que la página que se usa menos se quita de la memoria, ¿qué tendría que añadir a las tablas? ¿Qué modificaciones de software se requieren para dar apoyo a ese nuevo algoritmo?

Se les debería añadir a las tablas una columna en la que se apunte la frecuencia del uso de las páginas. Al software se le debería modificar para que calculara la frecuencia de el uso de las páginas: Veces usadas/Tiempo transcurrido desde inicio de página hasta tiempo actual del calculo.

9. Dado que la memoria principal está compuesta por cuatro marcos de página para uso público, utilice la tabla siguiente para responder todas las partes de este problema:

a) ¿El contenido de qué marco de página intercambiaría FIFO?intercambiaría la página # 2 que fue la que más rápido se cargó en la memoria.
b) Ahora, ¿el contenido de qué marco de página intercambiaría LRU?intercambiaría la página # 0 que se ha usado menos recientemente.
c) ¿El contenido de qué marco de página intercambiaría MRU?intercambiaría la página # 3 que fue la que se usó más recientemente.
d) Por último, ¿el contenido de qué marco de página intercambiaría LFU?con la información de la tabla no podría decir cual intercambiaría

10. Dado que la memoria principal está compuesta por cuatro marcos de página y que un programa se ha dividido en ocho páginas (0-7):

a) ¿Cuántas fallas de página ocurrirán utilizando FIFO, con una lista de solicitudes de: 0, 1, 7, 2, 3, 2, 7, 1, 0, 3 si los cuatro marcos de página están vacíos al inicio?

Ocurrirían seis fallas de página

b) ¿Cuántas fallas de página se presentarán en las mismas condiciones pero utilizando LRU?

Ocurrirían seis fallas de página

11. Dadas tres subrutinas de 700, 200 y 500 palabras respectivamente, si se utiliza la segmentación, la memoria total necesaria es la suma de los tres tamaños (si las tres rutinas se cargan). Sin embargo, si se usa la paginación se pierde algo de espacio de almacenamiento, porque las subrutinas rara vez llenan la última página y esto produce fragmentación interna. Determine la cantidad total de memoria desperdiciada debido a la fragmentación interna cuando las tres subrutinas se cargan en la memoria, utilizando cada uno de los siguientes tamaños de páginas:
a) 200 palabras

Se desperdician 200 palabras en la memoria

b) 500 palabras

Se desperdicio 400 palabras en memoria

c) 600 palabras Se desperdician 800 palabras en la memoria

d) 700 palabras Se desperdician 700 palabras en memoria

Administración de dispositivos

La administración de dispositivos comprende 4 funciones básicas:

* Controlar el estado de cada dispositivo (como unidades de cinta, unidades de disco, impresoras, graficadotes y terminales)
* Utilizar políticas preestablecidas para determinar que proceso obtendrá un dispositivo y durante cuanto tiempo.
* Asignar los dispositivos.
* Desasignarlos en dos niveles: en el nivel de procesos cuando se ejecute un comando de entrada/salida y el dispositivo se libera de manera permanente.

Los dispositivos periféricos del sistema generalmente entran en una de tres clases:

* Dedicados
* Compartidos
* Virtuales

Los dispositivos dedicados: se asignan sólo a un trabajo a la vez y le sirven todo el tiempo que está activo. La desventaja de los dispositivos dedicados es que se asignan a un usuario durante todo el tiempo que dure el trabajo que realiza, esto podría resultar ineficiente y es aun más ineficiente si el dispositivo no se utiliza el 100% del tiempo.

Los dispositivos compartidos: estos se puede asignar a más de un proceso. Se puede compartir cualquier dispositivo de almacenamiento de acceso directo al entrelazar sus solicitudes, en estos casos el administrador de dispositivos tiene que controlar esta acción con bastante cuidado.

Los dispositivos virtuales: son una combinación de los dispositivos dedicados y los compartidos; son dispositivos dedicados transformados en dispositivos compartidos.

Los medios de almacenamiento se dividen en dos grupos:

* Medios de almacenamiento de acceso secuencial
* Dispositivos de almacenamiento de acceso directo

Medios de almacenamiento de acceso secuencial.
El primer medio de almacenamiento fue el papel, pero su volumen y su precio hicieron que este medio resultara inaceptable para sistemas grandes. La cinta magnética se desarrollo para los primeros sistemas de cómputo de almacenamiento secundario rutinario. Estos almacenan los registros en secuencia, uno después del otro. Este almacenamiento depende de la forma en que se decida almacenar los registros, esto es, en forma individual o en bloques. Si se almacena en forma individual después de cada registro le sigue un espacio que separa a cada registro almacenado, espacio entre registros (IRG, es aproximadamente de ½ pulgada de largo), sin importar el tamaño de los registros que separa. Esta forma es poco eficiente cuando los registros que se almacenan son de poco tamaño, ya que se pierde mucho en los IRG. La otra forma de almacenamiento de registros es la de bloques, que consiste en agrupar los registros en bloques antes de registrarlos en la cinta. A esto se le llama “bloquear” y se lleva a cabo al crear el archivo. Los registros en un bloque son almacenados de forma secuencial, uno después del otro, y cada bloque es separado por un espacio que separa los diferentes bloques (IBG, al igual que el IRG es aproximadamente ½ pulgada de largo).

Dispositivos de almacenamiento de acceso directo (DASD).
Estos son los dispositivos que pueden leer o escribir en un lugar específico en un disco (también se conocen como dispositivos de almacenamiento de acceso aleatorio). Por lo general se agrupan en dos categorías principales:
a) Con cabezas de lectura y escritura fijas
b) Con cabezas de lectura y escritura móviles

DASD de cabeza fija.
Los primeros DASD eran tambores registrables magnéticamente. Estos eran en forma de una lata de café gigante, cubierta con película magnética y formato, de manera que las pistas corren a su alrededor. Los tambores de cabeza fija eran muy rápidos ya que utilizaban una cabeza de lectura/escritura para cada pista, pero también su valor era muy costoso y no contenían tantos datos como otros DASD, lo cual hizo que su popularidad descendiera.

DASD de cabeza móvil.
Los tambores de cabeza móvil sólo tienen unas cuantas cabezas de lectura/escritura que se mueven de una pista a otra para cubrir la superficie del tambor. Mientras menos cabezas móviles tenga el tambor, menos es su valor.

Almacenamiento óptico en disco.
Las unidades de disco óptico utilizan un rayo láser para leer y escribir los discos de varias capas. El rayo láser que utiliza es de alta intensidad para quemar perforaciones (indentaciones) y pistas (áreas planas) en el disco que representan unos y ceros, respectivamente.

Tecnología CD-ROM.
El CD-ROM fue el primer dispositivo de almacenamiento óptico de acceso directo de uso común y se usó por primera vez para almacenar bases de datos muy grandes, trabajos de consulta, softwares, entre otros.

Tecnología CD-GRABABLE.
Las unidades de CD-R graban los datos en discos ópticos utilizando una técnica de escribir una vez. Después de almacenar una cantidad de datos finita en un disco no es posible borrarlos o modificarlos.

Tecnología CD-REGRABABLE.
Las unidades de CD-RW pueden leer un CD-ROM estándar así como los discos CD-R y CD-RW. En esta última es posible escribir y reescribir datos en los discos con un rayo láser de baja energía sobre la superficie, esta caliente lo suficiente para borrar las perforaciones que almacenan datos y el disco vuelve a su estado original.

Tecnología DVD.
Esta tecnología de disco de video digital (DVD) utiliza un láser infrarrojo para leer el disco, que puede contener el equivalente de 13 discos CD-ROM.
Tiempo de acceso requerido.
Según si un dispositivo DASD tiene cabezas fijas o móviles, tres factores pueden afectar el lapso requerido para tener acceso a un archivo:

* El tiempo de búsqueda
* El tiempo de latencia
* El tiempo de transferencia

El tiempo de búsqueda es el más lento de los tres. Este es el intervalo requerido para colocar la cabeza de lectura/escritura sobre las pistas apropiadas. Este período no se aplica en dispositivos de cabeza fija.

El tiempo de latencia o retardo rotacional. Es el lapso necesario para girar el DASD hasta que el registro requerido pase por debajo de la cabeza de lectura/escritura.

El tiempo de transferencia. Es el más rápido de los tres, es cuando los datos realmente son transferidos del almacenamiento secundario a la memoria principal.

Dispositivos de cabeza fija. Estos dispositivos pueden tener acceso a un registro al conocer sus números de pista y de registro. El tiempo requerido para el acceso a los datos depende de dos factores:

1) La velocidad de rotación, aunque varía de un dispositivo a otro es constante en cada uno.
2) La posición del registro en relación con la posición de la cabeza de lectura/escritura.

El tiempo total de acceso es la suma del lapso de búsqueda más el periodo de transferencia.

Tiempo de búsqueda (retardo rotacional)
+ Tiempo de transferencia (transferencia de datos)
= Tiempo de acceso

Ya que los DASD giran continuamente, hay tres posiciones básicas para el registro requerido relativo a la posición de la cabeza de lectura/escritura:

1) La mejor de la situación posible es cuando el registro se encuentra al lado de la cabeza de lectura/escritura cuando se ejecuta el comando de entrada/salida; esto da un retardo rotacional igual a cero.

2) La situación promedio es cuando el registro se encuentra en el otro extremo de la cabeza de lectura/escritura al momento que se ejecuta el comando de entrada/salida; esto da un retardo rotacional de t/2.

3) La peor de la situación es cuando el registro acaba de pasar por la cabeza de lectura/escritura cuando se ejecuta el comando de entrada/salida, con un retardo rotacional de t, ya que este necesita de una rotación completa para que el registro se coloque debajo de la cabeza.

Dispositivos de cabeza móvil.
Estos dispositivos agregan el tercer elemento temporal al cálculo del periodo de acceso: el lapso requerido para mover el brazo a su posición bajo la pista adecuada o tiempo de búsqueda.

Tiempo de búsqueda (movimiento del brazo)
Tiempo de latencia (retardo rotacional)
+ Tiempo de transferencia (transferencia de datos)
= Tiempo de acceso

El tiempo más largo entre los componentes del tiempo de acceso de esta ecuación es el de búsqueda. El tiempo de latencia y de transferencia es el mismo para los DASD de cabeza fija como para los de cabeza móvil.

Los dispositivos de cabeza móvil son más comunes que los de cabeza fija porque su costo es menor y tienen mayor capacidad, aun cuando el tiempo de recuperación es más largo.

Componentes de subsistema de entrada/salida.
Los componentes del subsistema de entrada/salida son: canales, unidad de control, dispositivos de entrada/salida.

Los canales de entrada/salida. Son unidades programables colocadas entre el CPU y las unidades de control. Estos controlan la velocidad rápida del CPU con la lenta del dispositivo entrada/salida y permite la superposición de operaciones de entrada/salida con las operaciones del procesador.

La unidad de control de entrada/salida es quien interpreta las señales que el canal envía para cada función. En la mayor parte de los sistemas una sola unidad de control está fija para varios dispositivos similares.

Al inicio de un comando de entrada/salida, la información que pasa del CPU al canal es:

1. Comando de entrada/salida (READ, WRITE, REWIND, etc..)
2. Número del canal
3. Dirección del registro físico que se va a transferir (desde el almacenamiento secundario o hacia él)
4. Dirección de inicio del buffer a partir del cual se va a transferir el registro o hacia el cual se va a mandar.

Comunicación entre dispositivos.
Para que un sistema de cómputo ocupado funcione eficientemente el administrador de dispositivos se apoya en varias características auxiliares y existen tres problemas por resolver:

1. Necesita saber qué componentes están ocupados y cuáles están libres
2. Debe ser capaz de aceptar las solicitudes que llegan durante el tráfico pesado de entrada/salida
3. Debe aceptar la disparidad de velocidades entre el CPU y los dispositivos de entrada/salida.

El primero se resuelve estructurando la interacción entre las unidades. Los dos últimos problemas se manejan colocando en memorias intermedias los registros y la cola de solicitudes.

Para saber cuando una operación ha terminado se usa una bandera de hardware que debe probar el CPU. Esta bandera esta formada por 3 bits y esta se encuentra en el Channel Status Word (CSW). Cada bit representa uno de los componentes del subsistema de entrada/salida. Cada bit cambia de cero a uno para indicar que la unidad ha pasado de libre a ocupada y esta bandera puede ser accesada por cualquier componente para saber antes de seguir adelante con la siguiente operación de entrada/salida si la trayectoria esta libre para su uso.

Dos maneras de realizar esta prueba son la encuesta y el uso de interrupciones.

* La encuesta utiliza una instrucción especial de máquina para probar la bandera. Esta manera tiene de desventaja que el CPU pierde tiempo en probar si un canal esta libre o no y si tarda en efectuar este procedimiento podría que el dispositivo se deje de usar por un tiempo ya que el CPU cree que todavía esta en uso.
* El uso de interrupciones es una forma más eficiente de probar las banderas. Ya que un mecanismo de hardware la prueba como parte de cada instrucción de máquina que ejecuta el CPU.

Acceso directo a la memoria (DMA). Es una técnica de entrada/salida que permite que una unidad de control tenga acceso directo a la memoria principal. Para esto el CPU envía suficiente información a la unidad de control y así se evita la intervención del CPU y puede continuar con otra tarea, mientras la unidad de control completa la transferencia.

Buffers. (también llamados memorias intermedias) son áreas temporales de almacenamiento que se encuentran en localidades convenientes en el sistema: memoria principal, canales y unidades de control. Estos se utilizan mucho para sincronizar mejor el movimiento de datos entre los dispositivos de entrada/salida relativamente lentos y un CPU muy rápido.

Administración de las solicitudes de entrada/salida.
El administrador de dispositivos divide la tarea en tres partes, cada una manejada por un componente especifico de softwares del subsistema de entrada/salida:

* El controlador de tráfico de entrada/salida.
* El planificador de entrada/salida.
* El manejador de dispositivos de entrada/salida.

El controlador de tráfico de entrada/salida vigila el estado de los dispositivos, unidades de control y canales

Estrategias de búsqueda de manejo de dispositivos.

Una estrategia de búsqueda para el manejador de dispositivos de entrada/salida es la política predeterminada que utiliza para dar acceso al dispositivo a los diversos procesos que puedan estar esperándolo; define el orden en el cual los procesos obtienen el dispositivo, y la meta es mantener el tiempo de búsqueda en un mínimo.

Algunas estrategias de búsquedas más comunes:

* Primeras llegadas, primeros servicios (FCFS).
* Tiempo más breve de búsqueda primero (SSTF).
* SCAN y sus variaciones, LOOK, N-Step SCAN, C-SCAN, y C-LOOK.

Todo algoritmo de programación debe efectuar lo siguiente:

* Minimizar el movimiento del brazo.
* Llevar al mínimo el tiempo medio de respuesta.
* Minimizar la variación del tiempo de respuesta.

RAID

Es un juego de unidades físicas de disco considerado como una unidad lógica por el sistema operativo. Se introdujo para cerrar la brecha cada vez más grande entre procesadores más rápidos y unidades del disco más lentas.

Los investigadores de la University of California en Berkeley propusieron la tecnología RAID. Ellos tomaros las siglas de Redundant Array of Inexpensive Disk (Arreglo redundante de discos económicos).