Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Evaluame mis contribuciones a la wiki

2013-02-12T16:32:02Z

Danayaher:

A continuación, indica tu nombre y apellidos:

* Juan Carlos Roldán Salvador IS-G1
* Daniel Ayala Hernández IS-G1
* Daniel de los Reyes Leal IS-G1
* Olga Minerva Moreno Martín IS-G1
* Vanessa Chipirrás Navalón IC
* Alejandro Sánchez Medina IS-G1
* Francisco Javier Borrego Cejudo IC-G2
* Samuel Martin Arenas IC-G2
* Álvaro Fernández García IS-G1
* Rafael Gomez Galbarro GIC2
*María Pérez Reina IS-G1

Estructura típica de dispositivo E/S

2013-01-21T10:30:42Z

Danayaher:

En general, la estructura típica de un dispositivo de entrada/salida está dividida en tres partes:

* '''Adaptador de Entrada/Salida del ordenador, o interfaz del bus:''' Se encarga de traducir las señales al dialecto empleado por el bus del ordenador. Algunos ejemplos de interfaces de este tipo son los buses PCI, PCMCIA, USB, PCI-express o SATA entre muchos otros.
* '''Control del dispositivo, o puerto de lectura/escritura:''' Ofrece una interfaz que es empleada por el gestor de dispositivos para gobernar el dispositivo, que dispone de:
**Registros de órdenes
**Registros de estado
**Registros de lectura/escritura, o alternativamente una pequeña memoria propia.
* '''Adaptador de Entrada/Salida del dispositivo, o interfaz del dispositivo:''' Se encarga de traducir las señales al dialecto empleado por el dispositivo.

Cuanto más elaborado sea el puerto de lectura/escritura, mayor rendimiento se puede llegar a alcanzar, puesto que el gestor de dispositivo será más sencillo (y eso implica menor número de instrucciones a ejecutar en el gestor de dispositivo).

La conexión existente entre el procesador y el dispositivo de E/S queda resumida de la siguiente manera:

[[Archivo:DispLE.jpg|Estructura del dispositivo]]

= Gestor de dispositivos =

El gestor de dispositivo, popularmente conocido por la palabra inglesa ''driver'', es la parte del sistema operativo que se encarga de gobernar un cierto dispositivo o una familia de dispositivos de naturaleza similar. El gestor de dispositivo se trata de una pieza de software que conoce los detalles de bajo nivel del dispositivo. De esta manera el driver hace uso del conjunto de instrucciones que ofrece el puerto de E/S, los registros de estado y de lectura
y escritura, para gobernar el dispositivo. Si el fabricante del dispositivo no ofrece un ''driver'' para un cierto sistema operativo, el dispositivo y los recursos que ofrece no puede ser gestionado por el sistema operativo. Por lo general el fabricante de un dispositivo desarrolla el gestor de dispositivo para los sistemas operativos mayoritarios (i.e. Windows y Linux) para asegurar que su dispositivo alcanza la mayor cuota de usuarios posibles.

Los gestores de dispositivos representan en torno al 70% de los sistemas operativos<ref>Construction of a Highly Dependable Operating System, Proc. 6th European Dependable Computing Conference (EDCC-6), pp. 3-12, Oct. 2006</ref>. Por lo general, en los sistemas operativos monolíticos se ejecutan en el espacio del núcleo del sistema operativo por razones de rendimiento. Por tanto, se ejecutan en modo privilegiado, así un error de programación en un ''driver'' lleve a un cuelgue completo del sistema con casi total seguridad. Se estima que en torno al 85% de cuelgues de Microsoft Windows XP <ref>Recovering Device Drivers, Proc. OSDI '04, pp. 1-16, 2004</ref>se debe a errores de programación en ''drivers''.

No obstante, en sistemas operativos convencionales como Windows, Linux y Mac, existen mecanismos que permiten ejecutar ''drivers'' como procesos de usuario, tal y como sucede en sistemas operativo de tipo micronúcleo. De esta manera, un error de programación no produce el cuelgue del sistema completo. No obstante, dichos gestores de dispositivos se limitan a dispositivos particularmente lentos en los que la tasa de transferencia de datos es baja y los tiempos de respuesta del dispositivo son altos, por ejemplo, los gestores de dispositivos para lectores de tarjetas inteligentes (smartcards, lo que incluye las tarjetas SIM que se emplean en telefonía móvil) en Linux funcionan en espacio de usuario.

==DMA==
'''DMA''' (''Direct memory access'') es un dispositivo capaz de '''transferir datos''' entre la memoria principal y el dispositivo de E/S. El procesador le ordena hacer transferencias, y cuando termina, produce una interrupción.

Pueden estar '''integrados''' tanto en el sistema como en el propio dispositivo.

Frecuentemente son '''multicanal''', por lo que se pueden tener varias transferencias en curso simultáneamente.

Pueden soportar transferencias de memoria a memoria.

==Notas==
<references/>

Archivo:DispLE.jpg

2013-01-21T10:29:36Z

Danayaher:

Archivo:DispLE.svg

2013-01-21T10:27:15Z

Danayaher:

Usuario:Danayaher

2013-01-20T17:32:24Z

Danayaher: Página creada con 'Daniel Ayala Hernández Ingeniería Informática del Sowftware asignatura de SO cursada durante curso 2012-2013'

Daniel Ayala Hernández

Ingeniería Informática del Sowftware asignatura de SO cursada durante curso 2012-2013

Mejoras en la demora de rotación

2013-01-20T11:23:50Z

Danayaher:

Para mejorar los tiempos de espera asociados a la demora de rotación se pueden ordenar el acceso a los sectores de peticiones que se encuentren el mismo cilindro de manera que se pueda acceder a las posiciones una detrás de otra sin tener que dar vueltas de sobra. A continuación, las diferentes estrategias:
==Intercalado de sectores==
Esto se basa en que los tiempos de lectura/escritura y transmisión de los datos no son despreciables, con lo que cuando el dispositivo lee unos datos en un sector, mientras que espera a que se transmitan, el disco ha seguido girando y posiblemente se encuentre en otro sector. Por tanto, si los colocamos consecutivamente tendremos que esperar toda una vuelta para acceder al siguiente. Sin embargo, colocándolos de manera alterna, podemos evitar dar la vuelta completa al disco, y esperar una fracción del disco. Esto puede lograrse partiendo de la numeración natural e insertando un escalado de valor n, el cual puede llevarse a cabo durante el formateo o por software en el propio gestor.
Cuando el intercalado es de valor n, significa que hay una distancia de n sectores entre los anteriores sectores consecutivos.

===Ejemplo===
[[Archivo:Sdf.png]]

Si el intercalado se implementa en el gestor mediante software, se debe utilizar una tabla que convierta la dirección lógica del sector (NLS) en su dirección física (NFS). Esta tabla es dependiente del dispositivo, y por tanto debería estar almacenada en el mismo.

==Ordenación circular==
De manera parecida al método anterior vamos a alterar el orden en que vamos a leer los sectores. Si bien una petición más urgente o más antigua nos interesa satisfacerla antes, se dispondrán al principio del orden de lectura/escritura. Es imprescindible saber la posición inicial del cabezal para saber qué sectores se visitarán antes, y en función de este, se organiza el orden.

===Ejemplo===
[[Archivo:SSOOrot2.jpg]]
==Transferencia de pista completa==
La mayor parte de las veces que se accede a un sector en una pista, se accede después a otro sector que tenga adyacente en la pista. Para solucionar este retraso ocasionado por dar una vuelta completa al disco se planea que nada mas llegue el cabezal a la pista deseada empiece a transferir hasta que acabe la pista completa.
Los datos no solicitados se guardan en caché hasta que en un futuro próximo sean pedidos.
De este modo, nos anticipamos a la petición del sector n+1.
Este método es sólo útil para lectura, ya que es una información que se guarda en memoria.

FAT

2013-01-20T11:19:59Z

Danayaher:

El sistema de archivos FAT (File Allocation Table, tabla de asignación de archivos) utiliza junto a la tabla de entrada de ficheros una tabla, llamada tabla de asignación de ficheros (o tabla FAT).
FAT es un sistema de archivos sencillo, lo que lo hace muy popular en la gestión de discos y otras memorias secundarias externas y que sea aceptado por todos los sistemas operativos existentes (por lo que también es utilizado como mecanismo de intercambio de ficheros entre sistemas operativos distintos y coexistentes en el mismo equipo).
Sin embargo FAT tiene bastantes desventajas:
*Tiende a dejar fragmentos de los ficheros tras borrarlos, lo que con el tiempo ralentiza las operaciones L/E.
*No es redundante a fallos (ante fallos, como fallos eléctricos, puede dejar el sistema en un estado incongruente).
*Fue diseñado para ficheros de tamaño reducido.
*No soporta permisos de seguridad.

==Estructura==

Se dispone de la tabla de asignación de ficheros (File Allocation Table, de ahí las siglas FAT) en la que cada entrada de la tabla representa un bloque del disco. Cada entrada puede tener uno de los siguientes valores:

*Bloque libre: FREE
*Bloque defectuoso: BAD
*Último bloque de un archivo: EOF
*Cualquier otro número: bloque asignado, y el número es el número del siguiente bloque
*Entradas 0 y 1: reservadas

[[Archivo:Fat.png|Estructura FAT|center|border|600px]]

Nota: Si alguien quiere editar la imagen para mejorarla: [[https://docs.google.com/drawings/d/1CJlmPagvZl989yUOR41GBqZBL2afKt3gxxvYVkf57NU/edit?hl=en_US| Editar imagen]] --[[Usuario:Robertomartin|Robertomartin]] 12:19 6 jun 2011 (UTC)

==FAT 12==

La versión inicial de FAT se conoce ahora como '''FAT12'''. Es un sistema de archivos para disquete, por lo que tiene varias limitaciones:

* No soporta anidación de carpeta.
* Las direcciones de bloque solamente contienen 12 bits. Esto complica la implementación.
* El tamaño del disco se almacena como una cuenta de 16 bits expresada en sectores, lo que limita el espacio manejable a 32 megabytes.

En aquella época, el habitual disquete (5,25 pulgadas en una sola cara) constaba de 40 pistas con 8 sectores por pista, resultando en una capacidad inferior a 160 kilobytes. Este límite excedía la capacidad en más de un orden de magnitud, y al mismo tiempo, permitía encajar todas las estructuras de control en la primera pista. Por tanto, se evitaba el movimiento de los cabezales en las operaciones de lectura y escritura. Estos límites fueron superados en los años posteriores.

Con el propósito de soportar el reciente IBM PC, que disponía de un disco duro de 10 megabytes, MS-DOS 2.0, y carpetas anidadas, simplemente se utilizaron clusters de 8 kilobytes en el disco duro. El formato de FAT en sí mismo no cambió.

En 1984, IBM lanzó el PC AT, con 20 megabytes de disco duro. Al mismo tiempo, Microsoft lanzó MS-DOS 3.0. Las direcciones de los cluster fueron ampliadas a 16 bits, permitiendo un número mayor de clusters (65.536 exactamente). Por tanto, soportaba mayores tamaños de sistema de archivos. A pesar de todo, no hubo mejoras en el límite máximo de 32 megabytes.

MS-DOS 3.0 también incorporó soporte a disquetes de alta densidad de 5,25 pulgadas (1,2 megabytes de capacidad), con 15 sectores por pista, y en consecuencia, más espacio para FAT. Esto probablemente forzó una dudosa optimización del tamaño del clúster, que bajó de dos sectores a sólo uno. El efecto global fue una reducción significativa de los tiempos de lectura y escritura frente a los disquetes de doble densidad.

==FAT 16==

En 1987 apareció lo que hoy se conoce como el formato '''FAT16'''. Se eliminó el contador de sectores de 16 bits. El tamaño de la partición ahora estaba limitado por la cuenta de sectores por clúster, que era de 8 bits. Esto obligaba a usar clusters de 32 Kbytes con los usuales 512 bytes por sector. Así que el límite definitivo de FAT16 se situó en los 2 gigabytes.

Esta mejora estuvo disponible en 1988 gracias a MS-DOS 4.0. Mucho más tarde, Windows NT aumentó el tamaño máximo del cluster a 64 kilobytes gracias al "truco" de considerar la cuenta de clusters como un entero sin signo. No obstante, el formato resultante no era compatible con otras implementaciones de la época, y además, generaba mas fragmentación interna (se ocupaban clusters enteros aunque solamente se precisaran unos pocos bytes). Windows 98 fue compatible con esta extensión en lo referente a lectura y escritura. Sin embargo, sus utilidades de disco no eran capaces de trabajar con ella.

==FAT 32==

FAT32 fue la respuesta para superar el límite de tamaño de FAT16 al mismo tiempo que se mantenía la compatibilidad con MS-DOS en modo real. Microsoft decidió implementar una nueva generación de FAT utilizando direcciones de cluster[http://es.wikipedia.org/wiki/Cl%C3%BAster_%28sistema_de_archivos%29] de 32 bits (aunque sólo 28 de esos bits se utilizaban realmente).

En teoría, esto debería permitir aproximadamente 268.435.538 clusters, arrojando tamaños de almacenamiento cercanos a los ocho terabytes. Sin embargo, debido a limitaciones en la utilidad ScanDisk de Microsoft, no se permite que FAT32 crezca más allá de 4.177.920 clusters por partición (es decir, unos 124 gigabytes). Posteriormente, Windows 2000 y XP situaron el límite de FAT32 en los 32 gigabytes. Microsoft afirma que es una decisión de diseño, sin embargo, es capaz de leer particiones mayores creadas por otros medios.

FAT32 apareció por primera vez en Windows 95 OSR2. Era necesario reformatear para usar las ventajas de FAT32. Curiosamente, DriveSpace 3 (incluido con Windows 95 y 98) no lo soportaba. Windows 98 incorporó una herramienta para convertir de FAT16 a FAT32 sin pérdida de los datos. Este soporte no estuvo disponible en la línea empresarial hasta Windows 2000.

El '''tamaño máximo de un archivo en FAT32''' es 4 gigabytes (2^32−1 bytes), ya que el campo que indica el tamaño de un archivo ocupa 32 bits. Esto resulta engorroso para aplicaciones de captura y edición de video, ya que los archivos generados por éstas superan fácilmente ese límite.

http://www.pjrc.com/tech/8051/ide/fat32.html

Tipos de errores en discos magnéticos

2013-01-20T11:15:41Z

Danayaher:

Los errores típicos relacionados con los discos duros magnéticos pueden ser:

* '''Permanentes''': La unidad se encuentra mal en algún sentido. No existe forma “tradicional” de acceder a ellos. En los discos magnéticos existen dos estrategias para tratar estos errores:
# Archivo que contiene todos los sectores defectuosos.
# Mantener en una tabla aquellos bloques defectuosos (p.e. FAT).
* '''Transitorios''': Errores temporales del dispositivo. Por ejemplo, caídas de tensión. La solución consiste en reintentar acceder al dispositivo un nº finito de veces, antes de declarar el error permanente. También existen rutinas de checksum (dispersión, como CRC) para detectarlos.
*Errores de '''programación''': Cuando el error se encuentra en el propio código del ''driver''. La solución pasa por esperar que se ofrezca una nueva versión del ''driver'' que solucione el problema.
*Errores de '''localización''': Tras mover el cabezal a un cilindro, se comprueba que el cabezal no está en el cilindro deseado. Se puede reintentar o recalibrar el cabezal.
*Errores de '''controlador''': El controlador está basado en un microprocesador y por tanto es posible que se bloquee. Si tras resetear no se arregla el problema, es posible que el controlador esté dañado.

Diseño modular E/S

2013-01-20T11:04:44Z

Danayaher:

La idea clave de esta arquitectura en capas es hacer independiente al proceso del dispositivo. Por lo general, en ingeniería del software, la independencia del proveedor es una propiedad muy deseable.

[[Archivo:diseño modular.jpg|center|x400px]]

Esta abstracción permite:

* Hacer a los procesos independientes de los dispositivos de E/S. Esto es deseable en cuanto a que el fabricante del dispositivo podría dejar de fabricar el dispositivo, por tanto, el proceso tendría que ser reescrito para soportar el nuevo dispositivo. De igual manera, si el dispositivo para el que está diseñado el proceso que conoce los detalles de bajo nivel no está disponible en el sistema, nuestro proceso quedaría inservible.
* Forzar a que un proceso tenga que pasar por el sistema operativo, que es quien garantiza que el reparto de recursos es equitativo. Si un proceso dispone de acceso directo a un dispositivo, podría adoptar un comportamiento ''abusón'' de manera que no permitiera a otros procesos emplearlo.

'''Nota''': el SSI es una subrutina de manejo de interrupciones.

Archivo:Diseño modular.jpg

2013-01-20T11:02:19Z

Danayaher:

Mejoras de tiempos de desplazamiento

2013-01-20T11:00:52Z

Danayaher:

La mayor parte del tiempo que se tarda en realizar una búsqueda en un disco magnético corresponde al de desplazamiento, es decir, el tiempo que el cabezal tarda en moverse al cilindro en el que se encuentra su objetivo. Si se debe de atender varias peticiones, el orden en el que se atienden puede ser tal que el recorrido total sea más corto (aunque también es importante que haya una varianza pequeña y no se les de demasiada preferencia a algunos cilindros). Esta sección recoge varios de los criterios posibles.

== FCFS (por orden de llegada "FIFO") ==

Las peticiones se atienden en el mismo orden en que se reciben. Tiene el inconveniente de que se realizan muchos desplazamientos del cabezal, especialmente si se realizan accesos consecutivos a bloques muy alejados entre sí.

== SSTF (Shortest Seek Time First) ==

También conocido como atención por menor tiempo de búsqueda: Ordena todas las solicitudes y selecciona el lote de las ''n'' primeras. Si no se llega a las ''n'' peticiones tras un tiempo se realiza la búsqueda. Su mayor desventaja es que aplaza las peticiones lejanas indefinidamente cuando ''n'' tiende a infinito (''n'' -> ∞).

== N-SCAN (criterio del ascensor) ==

Se escoge un sentido preferente: ascendente o descendente. El cabezal, en ese sentido, atiende todas las peticiones que puede, una detrás de otra, en orden ascendente/descendente hasta llegar a la última de las peticiones del lote. Luego, el cabezal hace lo mismo en el otro sentido, hasta llegar a la última.

|
| /\ | /\
| / \ | / \
| / \ | / \
___|/______\|/______\__
|

Como se puede observar, el cabezal pasa con más frecuencia por la parte central, y el tiempo máximo que puede tardar en llegar a estas es menor que el de los extremos. Por tanto, hay una descompensación a favor de las partes centrales, que puede ser remediada con el siguiente criterio.

Nota: La gráfica resultante no tiene por qué ser simétrica, dependerá de los sectores a los que accedamos.

Nota2: El número de sectores integrantes de cada lote será el indicado por la N, ejemplo: 3-SCAN, 4-SCAN, etc.

== C-SCAN (Circular-Scan) ==

La primera parte es igual: se escoge un sentido y se van atendiendo las peticiones que se pueden en ese sentido una detrás de otra hasta llegar a la última. Al llegar a la última, en vez de recorrer en el sentido opuesto, el cabezal se mueve a la más lejana en el sentido y vuelve a realizar el recorrido en el sentido preferente. Así se elimina el trato favorable a las partes centrales, con el coste de reducir el tiempo medio de atención del conjunto de peticiones

| |
| /. /. /. |\ .\ .\ .
| / . / . / . ó | \ . \ . \ .
| / . / . / . | \ . \ . \ .
___|/___./___._/___._ ___|___\.__ \.___\._
| |

Algún alma caritativa sube los ejemplos de clase antes del parcial??

No copié los datos, pero eran algo similar a esto:

== Ejemplos ==

Orden de acceso: 3, 80, 15, 45, 1, 79, 4

=== Solución FCFS ===

80 x
| / \ x
| / \ / \
50 / \ / \
| / \ x / \
| / \ / \ / \
20 / x \ / \
| x \ / x
___|/___________________x______________
|
| 3 80 15 45 1 79 4

=== Solución 3N-SCAN ===

80 x| |
| / |x |
| / | \ |
50 / | \ |
| / | x |
| / | \ |
20 x | \ |
| x | \ |x
___|/________|_______x|__
|
| 3 15 80|79 45 1|4

Página Principal

2013-01-20T10:43:25Z

Danayaher:

Bienvenido al wiki de la asignatura de Sistemas Operativos del departamento de Lenguajes y Sistemas Informáticos de la Universidad de Sevilla. ¡Contribuye!

= Novedades y noticias =

* Comienza el curso 2012/2013 --[[Usuario:Pneira|Pneira]] 15:01 28 sep 2012 (UTC)
* Primer control de evaluación continua del grupo GC2 el viernes 9 de noviembre --[[Usuario:Pneira|Pneira]] 16:47 26 oct 2012 (UTC)
* Segundo control de evaluación continua del grupo GC2 el viernes 14 de diciembre --[[Usuario:Pneira|Pneira]] 16:13 28 nov 2012 (UTC)
* Tercer control de evaluación continua del grupo GC2 el viernes 21 de diciembre --[[Usuario:Pneira|Pneira]] 15:10 12 dic 2012 (UTC)
* Notas del grupo de inglés disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/english.txt aquí] --[[Usuario:Pneira|Pneira]] 16:48 11 ene 2013 (UTC)
* Notas de los controles 1, 2 y 3 del grupo GIC2 disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/gic2.pdf aquí]. La revisión es el miércoles después de clase, a partir de las 17h30 --[[Usuario:Pneira|Pneira]] 20:41 11 ene 2013 (UTC)
* Notas del control 1,2,3 y 4 del grupo GIS1 disponibles pinchando [http://1984.lsi.us.es/~pablo/notas/gis1-final.pdf aquí]. --[[Usuario:Pneira|Pneira]] 14:46 16 ene 2013 (UTC)
* Revisión de controles el viernes 18 de enero después del control 4 --[[Usuario:Pneira|Pneira]] 19:16 17 ene 2013 (UTC)
* Si quieres que se te tenga en cuenta la posible subida de nota por contribuciones realizadas a la wiki, pincha [[Evaluame mis contribuciones a la wiki|aquí]]. --[[Usuario:Pneira|Pneira]] 19:23 17 ene 2013 (UTC)
* Notas del grupo de inglés del control 2, 3 y 4, pincha [http://1984.lsi.us.es/~pablo/notas/english.txt aquí]. --[[Usuario:Pneira|Pneira]] 10:04 18 ene 2013 (UTC)

= Unidades didácticas =

A continuación encontrarás las unidades didácticas que forman parte de la asignatura.

== Introducción a los Sistemas Operativos ==

* 1.1. [[Qué es un Sistema Operativo|Qué es un sistema operativo]]
* 1.2. [[Introducción histórica|Breve introducción histórica a los sistemas operativos]]
* 1.3. [[Tipos de Sistemas Operativos|Tipos de sistemas operativos]]

== Fundamentos de Sistemas Operativos ==

* 2.1. [[Organización básica de un ordenador]]
* 2.2. [[Modos de operación de la CPU|Modos de operación de la CPU]]
* 2.3. [[Interrupciones y excepciones|Interrupciones y excepciones]]
* 2.4. [[Arranque del sistema|Arranque del sistema]]
* 2.5. [[Componentes básicos de un sistema operativo|Componentes básicos de un sistema operativo]]
* 2.6. [[Conceptos básicos|Conceptos básicos]]
* 2.7. [[Llamadas al sistema|Llamadas al sistema]]
* 2.8. [[Ejercicios fundamentos Sistemas Operativos|Ejercicios]]

== Modelos de diseño de Sistemas Operativos ==

* 3.1. [[Modelos de Diseño de Sistemas Operativos|Modelos de diseño de sistemas operativos]]
* 3.2. [[Virtualización]]
* 3.3. [[Ejercicios 3|Ejercicios]]

== Procesos ==
* 4.1. [[Multiprogramación|La multiprogramación]]
* 4.2. [[Estados de los procesos|Estados de los procesos]]
* 4.3. [[Planificador de procesos|El planificador de procesos]]
* 4.4. [[Comportamiento de los procesos|El comportamiento de los procesos según el planificador]]
* 4.5. [[Bloque de control de procesos|El bloque de control del proceso]]
* 4.6. [[Conmutación de procesos|La conmutación de procesos]]
* 4.7. [[Hilos|Hilos]]
* 4.8. [[Ejercicios Procesos|Ejercicios]]

== Planificación de Procesos ==
* 5.1 [[Planificación de procesos|La planificación de procesos]]
* 5.2 [[Índices de evaluación|Índices de evaluación de la planificación de procesos]]
* 5.3 [[Criterios de planificación|Criterios de planificación]]
* 5.4 [[Planificadores de sistemas operativos existentes|Planificadores de sistemas operativos existentes]]
* 5.5 [[Planificación de procesos de tiempo real|La planificación de procesos de tiempo real]]
* 5.6 [[Planificación en sistemas multiprocesadores|La planificación de procesos en sistemas multiprocesadores]]
* 5.7 [[Ejercicios otros aspectos de la planificación|Ejercicios]]
* 5.8 [[Ejercicios planificación de procesos|Ejercicios]]

== Concurrencia de procesos ==

* 6.1 [[Concurrencia de procesos|Concurrencia de procesos]]
* 6.2 [[Mecanismos de sincronización|Control optimista y pesimista de la concurrencia]]
* 6.3 [[Cerrojos|Cerrojos]]
* 6.4 [[Ejercicio de concurrencia de procesos|Ejercicios]]

== Semáforos y comunicación ==

* 7.1 [[Semáforos|Semáforos]]
* 7.2 [[Monitores|Monitores]]
* 7.3 [[Mensajería|Mensajería]]
* 7.4 [[Ejercicios sincronización y comunicación|Ejercicios]]

== Interbloqueo ==

* 8.1 [[Definición de interbloqueo|Definición]]
* 8.2 [[Condiciones para el interbloqueo y estrategias de resolución|Modelado y Estrategias]]
* 8.3 [[Algoritmo para averiguar interbloqueo|Algoritmo del banquero]]
* 8.4 [[Ejercicios]]

== Segmentación y paginación ==

* 9.1 [[Introducción|Introducción]]
* 9.2 [[SO multiprogramables con particiones variables|SO multiprogramables con particiones variables]]
* 9.3 [[Segmentacion|Segmentación]]
* 9.4 [[Paginación|Paginación]]
* 9.5 [[Sistema combinado|Sistema combinado]]
* 9.6 [[Memoria virtual con multiprogramacion|Memoria virtual con multiprogramación]]
* 9.7 [[Ejercicios administración de memoria contigua|Ejercicios (Administración de memoria contigua)]]
* 9.8 [[Ejemplo de segmentación, paginación y combinado|Ejercicios (Segmentación, paginación y sistemas combinados)]]

== Memoria virtual ==

* 10.1 [[Memoria Virtual|Introducción]]
* 10.2 [[Criterios de reemplazo|Criterios de reemplazo]]
* 10.3 [[Ejercicios memoria virtual|Ejercicios]]

== Entrada/Salida ==

* 11.1 [[EstructuraES|Estructura dispositivo E/S]]
* 11.2 [[GestionES|Modos de gestionar dispositivos E/S]]
* 11.3 [[Diseño modular E/S|Diseño modular E/S]]
* 11.4 [[Ejercicios de Entrada/Salida|Ejercicios]]

== Gestión L/E ==

* 12.1 [[Discos Magnéticos|Discos Magnéticos]]
* 12.2 [[Mejoras de tiempos de desplazamiento|Mejoras de tiempos de desplazamiento]]
* 12.3 [[Mejoras en la demora de rotación|Mejoras en la demora de rotación]]
* 12.4 [[Tipos de errores en discos magnéticos|Tipos de errores en discos magnéticos]]
* 12.5 [[Ejercicios Gestión L/E|Ejercicios]]

== Administración de archivos ==

* 13.1 [[Introducción en la administración de archivos|Introducción en la administración de archivos]]
* 13.2 [[FAT|FAT]]
* 13.3 [[EXT2 |EXT2]]
* 13.4 [[Ejercicios Administración Ficheros|Ejercicios]]

== Anexo ==

Esta sección contiene información interesante pero que no pertenece al temario de la asignatura.

* Todo lo que siempre has querido saber sobre el protocolo SSH está [[SSH|aquí]].

Mejoras de tiempos de desplazamiento

2013-01-20T10:41:25Z

Danayaher: Mejoras de tiempos de búsqueda trasladada a Mejoras de tiempos de desplazamiento: Título impreciso

== FCFS (por orden de llegada "FIFO") ==

Las peticiones se atienden en el mismo orden en que se reciben. Tiene el inconveniente de que se realizan muchos desplazamientos del cabezal, especialmente si se realizan accesos consecutivos a bloques muy alejados entre sí.

== SSTF (Shortest Seek Time First) ==

También conocido como atención por menor tiempo de búsqueda: Ordena todas las solicitudes y selecciona el lote de las ''n'' primeras. Si no se llega a las ''n'' peticiones tras un tiempo se realiza la búsqueda. Su mayor desventaja es que aplaza las peticiones lejanas indefinidamente cuando ''n'' tiende a infinito (''n'' -> ∞).

== N-SCAN (criterio del ascensor) ==

Dentro de cada lote de la lista de accesos, escogemos aquellos sectores que nos permita ascender y descender en la tabla, dando de esta manera prioridad a los sectores que se encuentren en la parte central de la pista.

|
| /\ | /\
| / \ | / \
| / \ | / \
___|/______\|/______\__
|
Nota: La gráfica resultante no tiene por qué ser simétrica, dependerá de los sectores a los que accedamos.

Nota2: El número de sectores integrantes de cada lote será el indicado por la N, ejemplo: 3-SCAN, 4-SCAN, etc.

== C-SCAN (Circular-Scan) ==

Da preferencia al ascenso o descenso, y se mantiene. Así se elimina el trato favorable a las partes centrales.

| |
| /| /| /| |\ |\ |\ |
| / | / | / | ó | \ | \ | \ |
| / | / | / | | \ | \ | \ |
___|/___|/___|_/___|_ ___|___\|__ \|___\|_
| |

Algún alma caritativa sube los ejemplos de clase antes del parcial??

No copié los datos, pero eran algo similar a esto:

== Ejemplos ==

Orden de acceso: 3, 80, 15, 45, 1, 79, 4

=== Solución FCFS ===

80 x
| / \ x
| / \ / \
50 / \ / \
| / \ x / \
| / \ / \ / \
20 / x \ / \
| x \ / x
___|/___________________x______________
|
| 3 80 15 45 1 79 4

=== Solución 3N-SCAN ===

80 x| |
| / |x |
| / | \ |
50 / | \ |
| / | x |
| / | \ |
20 x | \ |
| x | \ |x
___|/________|_______x|__
|
| 3 15 80|79 45 1|4

Mejoras de tiempos de búsqueda

2013-01-20T10:41:25Z

Danayaher: Mejoras de tiempos de búsqueda trasladada a Mejoras de tiempos de desplazamiento: Título impreciso

#REDIRECCIÓN [[Mejoras de tiempos de desplazamiento]]

Evaluame mis contribuciones a la wiki

2013-01-17T20:27:31Z

Danayaher:

A continuación, indica tu nombre y apellidos:

* Manuel Pérez Gutierrez
* Juan De Lucas Rodríguez
* Juan Carlos Roldán Salvador
* Daniel Ayala Hernández

Discos Magnéticos

2013-01-15T20:58:41Z

Danayaher:

== Arquitectura de los discos magnéticos ==

Los discos magnéticos están formados por varios discos (desde 2 hasta 7) de material magnético montados sobre el mismo eje, los cuales se mantienen girando a una velocidad constante. Estos discos están recorridos, cada uno, por 2 cabezales magnéticos que no llegan a tocar el disco (están separados unos 3 nanómetros debido a una delgada capa de aire formada por la rotación del disco, de hecho si lo tocan se produce un error conocido como aterrizaje del cabezal) y que leen y escriben datos en el disco creando puntos de campo magnético.

En esta imagen se muestran los componentes de un disco duro magnético:

[[Archivo:componentes_HD_comentados.png]]

= Partes del disco magnético =

La superficie del disco magnético se divide en la siguientes partes:

* Pista (''track'', en inglés): Zona a la que accede el cabezal si este se queda fijo en una posición y el disco sigue girando. Si el cabezal se tratara de un lápiz, la pista sería la zona que el cabezal dibuja sobre el disco (que se trataría de una circunferencia). Hay que tener en cuenta que las pistas más cercanas al centro del disco son de menor tamaño al tener menor radio la circunferencia.
* Sector: Es una subdivisión de una pista (track) en un disco magnético. Cada sector almacena una cantidad fija de datos.
* Cilindro: Conjunto de sectores a los que el conjunto de cabezales pueden acceder desde una posición. Un cilindro está compuesto por un conjunto de sectores.

[[Archivo:cilindro.jpg]][[Archivo:Estructura_disco.png|Estructura de un disco óptico|right]]

= Prestaciones de un disco duro magnético =

Las prestaciones de un disco se pueden medir mediante los siguientes indicadores:

* Capacidad, cantidad de unidades de información que se pueden almacenar en el disco.
* Revoluciones por minuto (RPM), velocidad constante a la que gira el disco magnético.
* Tiempo de arranque del motor, se trata del tiempo que tarda el motor en hacer que el disco comience a girar a velocidad constante.
* Tiempo de accesos, tanto para operaciones de lectura como escritura:
** Tiempo de búsqueda, se trata del tiempo que tarda el cabezal en desplazarse de una pista a otra.
** Demora de rotación, se trata del tiempo que tarda en pasar un sector por delante del cabezal.
** Tiempo de transmisión, se trata del tiempo que toma la transferencia de datos del dispositivo al gestor de dispositivo.

= Recursos multimedia =
http://www.youtube.com/watch?v=Wiy_eHdj8kg&feature=player_embedded

Archivo:Cilindro.jpg

2013-01-15T20:54:13Z

Danayaher:

Criterios de reemplazo

2013-01-13T17:36:16Z

Danayaher:

La evaluación se hace en base a la '''tasa de fallos de página''', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

* Arranque en frío: se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno está cargado en memoria principal.
* Arranque en caliente: se suponen ya cargadas las páginas de los procesos en memoria principal.

== Criterio de página óptima (OPT, MIN) ==

Este es un criterio teórico que viene a establecer la cota inferior de la tasa de ''fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4
Suponiendo arranque en frío
___1_____2_____3_____4___
memoria principal | | | | |
de 4 marcos |_____|_____|_____|_____|

*[[sol_1|Solución]]

Otra forma de evaluar la eficiencia de un criterio de selección de página víctima es observando su curva paracorde, que relaciona el nº de fallos de página con el nº de marcos. La de un buen criterio se aproximará a la curva del criterio óptimo, y la de uno malo, a la del criterio al azar, o incluso pésimo.

[[Archivo:Curvas paracordes.jpg]]

En el siguiente ejemplo real se compara la efectividad de varios criterios en varios programas:

[[Archivo:img26.png]]

== Criterio de página pésima (MAX)==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse. También implica tener conocimiento de futuro, por lo que no es implementable en la práctica.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico, serviría para aproximar la cota media de la ''tasa de fallos de página''. Consiste en seleccionar una página al azar.

Dado que su implementación es trivial, cualquier algoritmo que de resultados similares a este será un mal criterio, pues seguro que su eficiencia será menor que la de no implementar ningún criterio y seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso. Es una aproximación implementable en la práctica del criterio MAX, pudiendo así compararlo con otros criterios. Según el principio de localidad, mientras más recientemente se haya accedido a una página, más probable es que vuelva a accederse a ella. Por ello, este criterio es muy deficiente, siendo su curva cercana a la pésima:

[[Archivo:MRU.jpg]]

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola.

El inconveniente de este criterio es que las páginas más usadas son las que más tiempo deberían permanecer en memoria, y son las más atacadas. No se debe suponer que, si las páginas “dejarán de ser necesarias”, implica que “ya no sean necesarias”.
Además, se produce la anomalía de Belady, efecto que consiste en la posibilidad de tener más fallos de página al aumentar el número de marcos en la memoria física:

[[Archivo:FIFO.jpg]]

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, el bit R se pondrá a 1 ante cualquier tipo de acceso, y el bit M se pondrá a 1 sólo ante eventos de escritura.

Para seleccionar la página víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:

# R=0, M=0
# R=0, M=1
# R=1, M=0
# R=1, M=1

Periódicamente se pone a cero el bit R.

[[Archivo:LRU.jpg]]

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la combinación de los criterios FIFO y NRU, pero sin emplear el bit M de NRU. Cuando hay que seleccionar una página víctima, se recorre la lista de páginas por orden de carga en memoria hasta encontrar alguna que tenga el bit R a 0. Durante la iteración, si se encuentra una cuyo bit R valga 1, se pone a 0, se retira de la lista y se añade al final (para darle una segunda oportunidad). Cuando se añade una nueva página, se añade al final de la cola con el bit R a 1.

[[Archivo:Segunda Oportunidad.jpg]]

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada, de manera que para dar la 2ª oportunidad a una página, sólo hemos de poner su bit R a 0 y pasar al siguiente.

*[[sol_reloj|Solución]]

==Criterio de la 3ª oportunidad (Método Multics)==
Es otra variante del criterio NRU, en la que se mantiene una lista ordenanda por orden de carga. Ante una sustitución, la primera candidata es la más antigua.

Si dicha página tiene el bit R a 1, se pone a 0 y se pasa al final de la lista (recibe una segunda oportunidad).

Si dicha página tiene el bit R a 0, existen dos casos:
*Si tiene el bit M a 1, se pone a 0 y se pasa al final de la lista.
*Si tiene el bit M a 0, se selecciona como página víctima.

[[Archivo:Tercera oportunidad.jpg]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el '''orden de acceso''' a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero. Es inviable en la práctica, pues supone mantener contadores de tamaños muy grande, uno por cada página en memoria, y por cada acceso a memoria podría ser necesario ejecutar una rutina que actualice la lista.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

Se tiene un bit R y un contador por cada marco. Cuando una página es cargada a un marco, se carga con su bit R a 1 y su contador inicial a 0. Cuando pasa un período determinado de tiempo (viene dado en el enunciado) se itera sobre toda la lista de páginas, y pueden ocurrir dos cosas:
* '''Si su bit R está a 1''': Se ponen su bit R a cero y su contador se incrementa.
* '''Si su bit R está a 0''': No se hace nada.

Cuando hay que seleccionar una página víctima, se escoge aquella cuyo contador sea más pequeño. En caso de empate, habrá que establecer un criterio de desempate.

*[[sol_9.2|Solución]]

== Sustitución por envejecimiento ==

Se emplea un registro R de N bits, asociado a cada página. Por cada acceso se pone a 1 el bit más significativo. Periódicamente se desplaza hacia la derecha el registro R. La página víctima será la que tenga el menor valor en el registro R (en caso de empate se emplea otro criterio). La información que contienen los bits menos significativos se pierden al realizar desplazamientos. Este criterio permite mantener un historial de acceso a las páginas, para seleccionar como víctima aquella que lleve más tiempo sin ser accedida.

*[[sol_10|Solución]]

= Implementaciones =

En el [[Algoritmos de criterios de reemplazo|Portal de la comunidad]] se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento.
Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --[[Usuario:Alexrdp|Alexrdp]] 16:24 6 jun 2011 (UTC)

Archivo:Tercera oportunidad.jpg

2013-01-13T17:03:35Z

Danayaher:

Archivo:Segunda Oportunidad.jpg

2013-01-13T17:02:56Z

Danayaher:

Archivo:LRU.jpg

2013-01-13T17:02:35Z

Danayaher:

Archivo:FIFO.jpg

2013-01-13T17:02:11Z

Danayaher:

Archivo:MRU.jpg

2013-01-13T17:02:01Z

Danayaher:

Archivo:Img26.png

2013-01-13T16:55:38Z

Danayaher: Fuente: http://static.usenix.org/event/usenix05/tech/general/full_papers/jiang/jiang_html/html.html

Fuente: http://static.usenix.org/event/usenix05/tech/general/full_papers/jiang/jiang_html/html.html

Archivo:Curvas paracordes.jpg

2013-01-13T16:55:04Z

Danayaher:

Sistema combinado

2013-01-13T16:41:18Z

Danayaher:

Consiste en combinar la segmentación y la paginación. La idea fundamental consiste en definir segmentos que están compuestos por N páginas. De ahí que reciba el nombre de '''segmentación paginada'''.

<center>[[Archivo:Sistema combinado.jpg]]</center>

Por tanto, cualquier segmento ocupa, como mínimo una página de memoria.

Por una parte, la segmentación proporciona ventajas hacia los procesos: Organización de datos y código, mecanismos de protección, compartición de datos y código, y optimización en el espacio ocupado. Por otra parte, la paginación facilita el uso de la memoria virtual, y genera dispersión en memoria. Además como la paginación es transparente, se puede usar paginación bajo un sistema segmentado sin problema.

Los procesos emplean direcciones lógica de memoria segmentada, que son traducidas a direcciones lógicas páginadas, que a su vez deben de ser traducidas a direcciones físicas. Por tanto, cualquier acceso a memoria supone un total de tres accesos a memoria. Uno para acceder a la tabla de segmentos, otro para acceder a la tabla de páginas y, por último, otro más para acceder a la dirección física. Aquí hay un ejemplo de la arquitectura IA32: <center>
[[Archivo:Arquitecturaia32.jpg]]</center>

Archivo:Sistema combinado.jpg

2013-01-13T16:39:19Z

Danayaher:

Segmentación

2013-01-13T16:26:13Z

Danayaher:

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

[[Archivo:Segmentos.png|725px]]

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: Se puede hacer que 2 segmentos se superpongan de manera que compartan direcciones de memoria física con direcciones lógicas diferentes. Para evitar problemas de concurrencia, debe de indicarse explícitamente que una porción de memoria puede ser compartida. De esta manera, procesos diferentes pueden compartir información y código usando la memoria común.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan.

*Gestión compleja, sobretodo por su tamaño variable

*Permite la carga de segmentos a petición, de manera que no se disponga de todos los segmentos en memoria principal, que se puedan descargar a disco (en la zona de intercambio o swap) en base a un cierto criterio (ver [[Intro | Memoria virtual]]). Esta zona de intercambio puede ser:
**Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar
**Un fichero oculto de tamaño fijo o variable dependiendo de la configuración dada por el usuario (Windows).

=Mecanismos=
Los diferentes mecanismos que nos ofrece la segmentación de memoria son los siguientes.
==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio (ver [[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser:

* Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar

* Un fichero oculto de tamaño fijo o variable dependiendo de la configuracion dada por el usuario (Windows).

==Formas de uso de los descriptores==
En cuanto a aspectos materiales, se plantea el problema de que no es habitual que la tabla de segmentos quepa en el dispositivo de traducción (MMU), por lo que se almacena la tabla en memoria, y el MMU contiene su dirección. El problema es que esta técnica hace que el tiempo de acceso se duplique, al haber un primer acceso al MMU y un segundo acceso a la dirección efectiva. Se plantean dos soluciones no excluyentes:
* '''Uso de registros descriptores de segmento en MMU:'''
<blockquote>
En MMU nos encontraremos varios registros que pueden contener descriptores, en los que se copiarán los que se vayan a usar en un futuro inmediato. Hay dos tipos de registros:
*Registros de propósito general:
Registros sobre los que se cargan los próximos descriptores a usar, y dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria (y necesitan más bits para hacer referencia al descriptor)
 - Las que hacen referencia a un descriptor en MMU (y necesitan menos bits para referir al descriptor)
*Registros especializados:
Registros capaces de albergar a un descriptor concreto, como el DS (Para manejo de datos), SS (Para manipulación de pila) o el CS (Para instrucciones de salto y llamadas a rutinas). También existen dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria
 - Las que no hacen referencia a ningún descriptor, y emplean descriptores de MMU, según el tipo de instrucción
</blockquote>

* '''Uso de descriptores en memoria asociativa (Cache):'''
<blockquote>
La MMU contiene una memoria asociativa indexada por número de descriptor. Para cada acceso, se busca en la memoria asociativa el número de descriptor, y si no está, se carga a esta (Si se llena la memoria asociativa se lleva a cabo reemplazo). Este tipo de memoria es transparente, por lo que se puede usar en conjunción con registros descriptores de segmento en MMU.
</blockquote>

Condiciones para el interbloqueo y estrategias de resolución

2012-12-08T19:48:34Z

Danayaher:

== Condiciones para que se produzca interbloqueo ==

Según [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman], para que se pueda producir un interbloqueo se tienen que dar las siguientes cuatro condiciones:

* '''Exclusión mutua''': cada recurso está asignado a un único proceso de manera exclusiva.
* '''Retención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos y esperar a que se le asignen sin liberar antes alguno de los recursos que ya tenia asignados.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita. Ni siquiera el sistema operativo puede expropiárselo.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

* Omisión
* Detección y recuperación
* Prevención
* Predicción

Que se detallan a continuación.

=== Omisión ===

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

=== Detección y Recuperación ===

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

* ''Grafo de relación recursos-procesos'': Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.Esta técnica se basa en recorrer el grafo yendo de un nodo a otro, por lo que si se consigue volver al nodo de partida estaremos en un recorrido circular. Para que este tipo de error sea detectado usamos algoritmos de detección, se lanzan cuando se solicita un recurso ocupado, es decir, hay una nueva arista dentro de nuestro grafo y debemos comprobar que no da lugar a un recorrido cíclico.

Un ejemplo de grafo en el que se detecta un ciclo es el siguiente:

[[Archivo:deteccion_ciclo.png]]

* ''Matrices de relación recursos-procesos'': Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.
2 Tipos:

-''Matrices binarias de relación:''
Una matriz binaria de relación es aquella que representa una relación R entre dos conjuntos, en la cual el primero de estos dos tiene múltiples asignaciones a elementos del segundo.

El método consiste en, aplicando matrices binarias de relación, utilizar el cierre transitivo para determinar si algún proceso está relacionado consigo mismo a través de otros, señalando así la existencia de ciclos. El procedimiento sería:

1.- Formar la matriz de espera (W: PR): Los procesos P están a la espera de recursos R.

2.- Formar la matriz de asignación (A: RP): Los recursos R están asignados a procesos P.

3.- Formar la matriz de procesos a la espera de procesos (T: WxA): Producto cartesiano de ambas matrices.

4.- Hallar el cierre transitivo de la matriz T: Que se puede obtener, por ejemplo, aplicando el Algoritmo de Warshall (algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución). El algoritmo es el siguiente:

Warshall(T, n){
for (k=1 to n){
for (i=1 to n){
for (j=1 to n){
Tij = Tij ⋁ (Tik ⋀ Tkj)
}
}
}
}

Donde n es la dimensión de la matriz T

5.- Si hay procesos que tengan un 1 en la diagonal principal, forman parte de algún ciclo.

Se trata de un método fácil de implementar, ya que solo se realizan operaciones con matrices y bucles, algo muy sencillo para una máquina. Sim embargo, tiene dos inconvenientes:+
* El número de operaciones a realizar es muy alto teniendo en cuenta el tamaño que pueden alcanzar las matrices de recursos
* Solo se puede usar cuandosolo existe una instancia de cada recurso

-''Detección matricial'':
Método matricial que trata aquellos casos en los que hay múltiples instancias equivalentes de un mismo tipo de recurso. Aísla grupos de procesos que no pueden proseguir la ejecución porque no pueden ver satisfechas sus peticiones pendientes.
Usan un método iterativo que:

1.-Marca procesos cuyas peticiones puedan satisfacerse con el actual vector de recursos disponibles.

2.-Suma al vector de disponibles los recursos asignados a los procesos marcados.

3.-Si todos los procesos están marcados: no hay interbloqueo.

4.-Si en una iteración no se marcan procesos: los procesos que quedan están interbloqueados.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

* ''Eliminación'': El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho proceso, si no es suficiente se eliminarán procesos hasta que se rompa el ciclo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos.Sin embargo, de una manera u otra el trabajo realizado por el proceso se pierde, algo que en algunos casos resulta inadmisible, como en sistemas en tiempo real. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales. Aplicar el criterio de selección y eliminar procesos cuando el número de procesos es relativamente bajo puede solucionar el interbloqueo, pero si se da un bloqueo de por ejemplo, centenares de procesos, es una situación prácticamente inmanejable.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso (durante el tiempo necesario) para deshacer el interbloqueo(hemos de asegurarnos de que el proceso no se desbloquea al romperse el interbloqueo). Por ejemplo, supongamos que el recurso es una impresora: podríamos retirarle la asignación a un proceso P1 cuando este terminase de imprimir una página, asignarle la impresora a otro proceso P2 y volver a asignársela a P1 cuando P2 haya terminado su ejecución. El problema es que este método solo es posible dependiendo de la naturaleza del proceso. Con frecuencia es imposible recuperarse de esta manera ya que los recursos no pueden ser apropiados.

* ''Puntos de conformidad'',''sincronismo'' o ''checkpoints'': Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar, y no todos los recursos permiten almacenar y recuperar su estado. Además, puede darse el caso de que el estado del proceso sea externo al sistema (Como en el caso de una conexión a Base de Datos

=== Prevención ===

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman] estableció como interbloqueo. Dichas estrategias son:

* ''Supresión de exclusión mutua'': Un proceso no puede tener acceso exclusivo a un recurso. No siempre es posible, y puede que lo único que haga sea cambiar el problema de sitio. Es una solución drástica, inviable. Por ejemplo, permitir que dos procesos usaran a la vez una impresora sería caótico.
* ''Supresión de retención y espera'' (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos. El aprovechamiento de recursos puede mejorarse mediante una programación más elaborada, dividiendo la ejecución del proceso en distintas fases y gestionando los recursos para cada una de ellas. Sin embargo, muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse.
* ''Supresión de no apropiación'' (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones.
* ''Supresión de espera circular'' (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos. De esta manera, se ordenan los procesos y se solicitan en ese orden. Por ejemplo: tenemos un proceso A y otro B, de manera que ambos hacen uso de los recursos X e Y. En el siguiente caso, no pedirían los recursos en el mismo orden:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(Y)
|-
| down(Y)||down(X)
|-
| …||…
|-
| up(Y)||up(X)
|-
| up(X)||up(Y)
|}

Si se ejecuta la instrucción down(X) de A, se conmuta a B y se ejecuta down(Y), se producirá un interbloqueo, ya que ambos estarán esperando a que el otro libere el recurso que necesitan.
Sin embargo, si pedimos los recursos siempre en el mismo orden de la siguiente forma:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(X)
|-
| down(Y)||down(Y)
|-
| …||…
|-
| up(Y)||up(Y)
|-
| up(X)||up(X)
|-
|
|}

Se puede comprobar que es imposible que se de un interbloqueo como en el caso anterior, ocurriendo lo mismo con cualquier número de procesos y recursos.

El principal inconveniente radica en que a veces, debido a la variedad y al número de recursos y procesos, es imposible encontrar un orden que satisfaga a todos los procesos.

=== Predicción ===

El sistema operativo observa la evolución que siguen los procesos, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que suceda, adopta una trayectoria de ejecución nueva para los procesos involucrados de manera que se garantice que no va a suceder un interbloqueo.

Condiciones para el interbloqueo y estrategias de resolución

2012-12-08T18:31:59Z

Danayaher:

== Condiciones para que se produzca interbloqueo ==

Según [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman], para que se pueda producir un interbloqueo se tienen que dar las siguientes cuatro condiciones:

* '''Exclusión mutua''': cada recurso está asignado a un único proceso de manera exclusiva.
* '''Retención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos y esperar a que se le asignen sin liberar antes alguno de los recursos que ya tenia asignados.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita. Ni siquiera el sistema operativo puede expropiárselo.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

* Omisión
* Detección y recuperación
* Prevención
* Predicción

Que se detallan a continuación.

=== Omisión ===

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

=== Detección y Recuperación ===

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

* ''Grafo de relación recursos-procesos'': Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.Esta técnica se basa en recorrer el grafo yendo de un nodo a otro, por lo que si se consigue volver al nodo de partida estaremos en un recorrido circular. Para que este tipo de error sea detectado usamos algoritmos de detección, se lanzan cuando se solicita un recurso ocupado, es decir, hay una nueva arista dentro de nuestro grafo y debemos comprobar que no da lugar a un recorrido cíclico.

Un ejemplo de grafo en el que se detecta un ciclo es el siguiente:

[[Archivo:deteccion_ciclo.png]]

* ''Matrices de relación recursos-procesos'': Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.
2 Tipos:

-''Matrices binarias de relación:''
Una matriz binaria de relación es aquella que representa una relación R entre dos conjuntos, en la cual el primero de estos dos tiene múltiples asignaciones a elementos del segundo.

El método consiste en, aplicando matrices binarias de relación, utilizar el cierre transitivo para determinar si algún proceso está relacionado consigo mismo a través de otros, señalando así la existencia de ciclos. El procedimiento sería:

1.- Formar la matriz de espera (W: PR): Los procesos P están a la espera de recursos R.

2.- Formar la matriz de asignación (A: RP): Los recursos R están asignados a procesos P.

3.- Formar la matriz de procesos a la espera de procesos (T: WxA): Producto cartesiano de ambas matrices.

4.- Hallar el cierre transitivo de la matriz T: Que se puede obtener, por ejemplo, aplicando el Algoritmo de Warshall (algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución). El algoritmo es el siguiente:

Warshall(T, n){
for (k=1 to n){
for (i=1 to n){
for (j=1 to n){
Tij = Tij ⋁ (Tik ⋀ Mkj)
}
}
}
}

Donde n es la dimensión de la matriz T

5.- Si hay procesos que tengan un 1 en la diagonal principal, forman parte de algún ciclo.

Se trata de un método fácil de implementar, ya que solo se realizan operaciones con matrices y bucles, algo muy sencillo para una máquina. Sim embargo, tiene dos inconvenientes:+
* El número de operaciones a realizar es muy alto teniendo en cuenta el tamaño que pueden alcanzar las matrices de recursos
* Solo se puede usar cuandosolo existe una instancia de cada recurso

-''Detección matricial'':
Método matricial que trata aquellos casos en los que hay múltiples instancias equivalentes de un mismo tipo de recurso. Aísla grupos de procesos que no pueden proseguir la ejecución porque no pueden ver satisfechas sus peticiones pendientes.
Usan un método iterativo que:

1.-Marca procesos cuyas peticiones puedan satisfacerse con el actual vector de recursos disponibles.

2.-Suma al vector de disponibles los recursos asignados a los procesos marcados.

3.-Si todos los procesos están marcados: no hay interbloqueo.

4.-Si en una iteración no se marcan procesos: los procesos que quedan están interbloqueados.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

* ''Eliminación'': El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho proceso, si no es suficiente se eliminarán procesos hasta que se rompa el ciclo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos.Sin embargo, de una manera u otra el trabajo realizado por el proceso se pierde, algo que en algunos casos resulta inadmisible, como en sistemas en tiempo real. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales. Aplicar el criterio de selección y eliminar procesos cuando el número de procesos es relativamente bajo puede solucionar el interbloqueo, pero si se da un bloqueo de por ejemplo, centenares de procesos, es una situación prácticamente inmanejable.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso (durante el tiempo necesario) para deshacer el interbloqueo(hemos de asegurarnos de que el proceso no se desbloquea al romperse el interbloqueo). Por ejemplo, supongamos que el recurso es una impresora: podríamos retirarle la asignación a un proceso P1 cuando este terminase de imprimir una página, asignarle la impresora a otro proceso P2 y volver a asignársela a P1 cuando P2 haya terminado su ejecución. El problema es que este método solo es posible dependiendo de la naturaleza del proceso. Con frecuencia es imposible recuperarse de esta manera ya que los recursos no pueden ser apropiados.

* ''Puntos de conformidad'',''sincronismo'' o ''checkpoints'': Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar, y no todos los recursos permiten almacenar y recuperar su estado. Además, puede darse el caso de que el estado del proceso sea externo al sistema (Como en el caso de una conexión a Base de Datos

=== Prevención ===

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman] estableció como interbloqueo. Dichas estrategias son:

* ''Supresión de exclusión mutua'': Un proceso no puede tener acceso exclusivo a un recurso. No siempre es posible, y puede que lo único que haga sea cambiar el problema de sitio. Es una solución drástica, inviable. Por ejemplo, permitir que dos procesos usaran a la vez una impresora sería caótico.
* ''Supresión de retención y espera'' (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos. El aprovechamiento de recursos puede mejorarse mediante una programación más elaborada, dividiendo la ejecución del proceso en distintas fases y gestionando los recursos para cada una de ellas. Sin embargo, muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse.
* ''Supresión de no apropiación'' (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones.
* ''Supresión de espera circular'' (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos. De esta manera, se ordenan los procesos y se solicitan en ese orden. Por ejemplo: tenemos un proceso A y otro B, de manera que ambos hacen uso de los recursos X e Y. En el siguiente caso, no pedirían los recursos en el mismo orden:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(Y)
|-
| down(Y)||down(X)
|-
| …||…
|-
| up(Y)||up(X)
|-
| up(X)||up(Y)
|}

Si se ejecuta la instrucción down(X) de A, se conmuta a B y se ejecuta down(Y), se producirá un interbloqueo, ya que ambos estarán esperando a que el otro libere el recurso que necesitan.
Sin embargo, si pedimos los recursos siempre en el mismo orden de la siguiente forma:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(X)
|-
| down(Y)||down(Y)
|-
| …||…
|-
| up(Y)||up(Y)
|-
| up(X)||up(X)
|-
|
|}

Se puede comprobar que es imposible que se de un interbloqueo como en el caso anterior, ocurriendo lo mismo con cualquier número de procesos y recursos.

El principal inconveniente radica en que a veces, debido a la variedad y al número de recursos y procesos, es imposible encontrar un orden que satisfaga a todos los procesos.

=== Predicción ===

El sistema operativo observa la evolución que siguen los procesos, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que suceda, adopta una trayectoria de ejecución nueva para los procesos involucrados de manera que se garantice que no va a suceder un interbloqueo.

Condiciones para el interbloqueo y estrategias de resolución

2012-12-08T18:31:02Z

Danayaher:

== Condiciones para que se produzca interbloqueo ==

Según [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman], para que se pueda producir un interbloqueo se tienen que dar las siguientes cuatro condiciones:

* '''Exclusión mutua''': cada recurso está asignado a un único proceso de manera exclusiva.
* '''Retención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos y esperar a que se le asignen sin liberar antes alguno de los recursos que ya tenia asignados.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita. Ni siquiera el sistema operativo puede expropiárselo.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

* Omisión
* Detección y recuperación
* Prevención
* Predicción

Que se detallan a continuación.

=== Omisión ===

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

=== Detección y Recuperación ===

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

* ''Grafo de relación recursos-procesos'': Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.Esta técnica se basa en recorrer el grafo yendo de un nodo a otro, por lo que si se consigue volver al nodo de partida estaremos en un recorrido circular. Para que este tipo de error sea detectado usamos algoritmos de detección, se lanzan cuando se solicita un recurso ocupado, es decir, hay una nueva arista dentro de nuestro grafo y debemos comprobar que no da lugar a un recorrido cíclico.

Un ejemplo de grafo en el que se detecta un ciclo es el siguiente:

[[Archivo:deteccion_ciclo.png]]

* ''Matrices de relación recursos-procesos'': Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.
2 Tipos:

-''Matrices binarias de relación:''
Una matriz binaria de relación es aquella que representa una relación R entre dos conjuntos, en la cual el primero de estos dos tiene múltiples asignaciones a elementos del segundo.

El método consiste en, aplicando matrices binarias de relación, utilizar el cierre transitivo para determinar si algún proceso está relacionado consigo mismo a través de otros, señalando así la existencia de ciclos. El procedimiento sería:

1.- Formar la matriz de espera (W: PR): Los procesos P están a la espera de recursos R.

2.- Formar la matriz de asignación (A: RP): Los recursos R están asignados a procesos P.

3.- Formar la matriz de procesos a la espera de procesos (T: WxA): Producto cartesiano de ambas matrices.

4.- Hallar el cierre transitivo de la matriz T: Que se puede obtener, por ejemplo, aplicando el Algoritmo de Warshall (algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución). El algoritmo es el siguiente:

Warshall(T, n){
for (k=1 to n){
for (i=1 to n){
for (j=1 to n){
Tij = Tij ⋁ (Tik ⋀ Mkj)
}
}
}
}

Donde n es la dimensión de la matriz T

5.- Si hay procesos que tengan un 1 en la diagonal principal, forman parte de algún ciclo.

Se trata de un método fácil de implementar, ya que solo se realizan operaciones con matrices y bucles, algo muy sencillo para una máquina. Sim embargo, tiene dos inconvenientes:+
* El número de operaciones a realizar es muy alto teniendo en cuenta el tamaño que pueden alcanzar las matrices de recursos
* Solo se puede usar cuandosolo existe una instancia de cada recurso

-''Detección matricial'':
Método matricial que trata aquellos casos en los que hay múltiples instancias equivalentes de un mismo tipo de recurso. Aísla grupos de procesos que no pueden proseguir la ejecución porque no pueden ver satisfechas sus peticiones pendientes.
Usan un método iterativo que:

1.-Marca procesos cuyas peticiones puedan satisfacerse con el actual vector de recursos disponibles.

2.-Suma al vector de disponibles los recursos asignados a los procesos marcados.

3.-Si todos los procesos están marcados: no hay interbloqueo.

4.-Si en una iteración no se marcan procesos: los procesos que quedan están interbloqueados.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

* ''Eliminación'': El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho proceso, si no es suficiente se eliminarán procesos hasta que se rompa el ciclo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos.Sin embargo, de una manera u otra el trabajo realizado por el proceso se pierde, algo que en algunos casos resulta inadmisible, como en sistemas en tiempo real. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales. Aplicar el criterio de selección y eliminar procesos cuando el número de procesos es relativamente bajo puede solucionar el interbloqueo, pero si se da un bloqueo de por ejemplo, centenares de procesos, es una situación prácticamente inmanejable.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso (durante el tiempo necesario) para deshacer el interbloqueo(hemos de asegurarnos de que el proceso no se desbloquea al romperse el interbloqueo). Por ejemplo, supongamos que el recurso es una impresora: podríamos retirarle la asignación a un proceso P1 cuando este terminase de imprimir una página, asignarle la impresora a otro proceso P2 y volver a asignársela a P1 cuando P2 haya terminado su ejecución. El problema es que este método solo es posible dependiendo de la naturaleza del proceso. Con frecuencia es imposible recuperarse de esta manera ya que los recursos no pueden ser apropiados.

* ''Puntos de conformidad'',''sincronismo'' o ''checkpoints'': Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar, y no todos los recursos permiten almacenar y recuperar su estado. Además, puede darse el caso de que el estado del proceso sea externo al sistema (Como en el caso de una conexión a Base de Datos

=== Prevención ===

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman] estableció como interbloqueo. Dichas estrategias son:

* ''Supresión de exclusión mutua'': Un proceso no puede tener acceso exclusivo a un recurso. No siempre es posible, y puede que lo único que haga sea cambiar el problema de sitio. Es una solución drástica, inviable. Por ejemplo, permitir que dos procesos usaran a la vez una impresora sería caótico.
* ''Supresión de retención y espera'' (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos. El aprovechamiento de recursos puede mejorarse mediante una programación más elaborada, dividiendo la ejecución del proceso en distintas fases y gestionando los recursos para cada una de ellas. Sin embargo, muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse.
* ''Supresión de no apropiación'' (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones. De esta manera, se ordenan los procesos y se solicitan en ese orden. Por ejemplo: tenemos un proceso A y otro B, de manera que ambos hacen uso de los recursos X e Y. En el siguiente caso, no pedirían los recursos en el mismo orden:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(Y)
|-
| down(Y)||down(X)
|-
| …||…
|-
| up(Y)||up(X)
|-
| up(X)||up(Y)
|}

Si se ejecuta la instrucción down(X) de A, se conmuta a B y se ejecuta down(Y), se producirá un interbloqueo, ya que ambos estarán esperando a que el otro libere el recurso que necesitan.
Sin embargo, si pedimos los recursos siempre en el mismo orden de la siguiente forma:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| down(X)||down(X)
|-
| down(Y)||down(Y)
|-
| …||…
|-
| up(Y)||up(Y)
|-
| up(X)||up(X)
|-
|
|}

Se puede comprobar que es imposible que se de un interbloqueo como en el caso anterior, ocurriendo lo mismo con cualquier número de procesos y recursos.

El principal inconveniente radica en que a veces, debido a la variedad y al número de recursos y procesos, es imposible encontrar un orden que satisfaga a todos los procesos.
* ''Supresión de espera circular'' (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos.

=== Predicción ===

El sistema operativo observa la evolución que siguen los procesos, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que suceda, adopta una trayectoria de ejecución nueva para los procesos involucrados de manera que se garantice que no va a suceder un interbloqueo.

Archivo:Deteccion ciclo.png

2012-12-08T18:07:18Z

Danayaher: subió una nueva versión de «Archivo:Deteccion ciclo.png»

Ejemplo de grafo en el que se da un ciclo.

Archivo:Deteccion ciclo.png

2012-12-08T18:03:40Z

Danayaher: Ejemplo de grafo en el que se da un ciclo.

Ejemplo de grafo en el que se da un ciclo.