Algoritmo del banquero

Algoritmo del banquero

El Algoritmo del banquero, en sistemas operativos es una forma de evitar el interbloqueo, propuesta por primera vez por Edsger Dijkstra. Es un acercamiento teórico para evitar los interbloqueos en la planificación de recursos. Requiere conocer con anticipación los recursos que serán utilizados por todos los procesos. Esto último generalmente no puede ser satisfecho en la práctica.

Este algoritmo usualmente es explicado usando la analogía con el funcionamiento de un banco. Los clientes representan a los procesos, que tienen un crédito límite, y el dinero representa a los recursos. El banquero es el sistema operativo.

El banco confía en que no tendrá que permitir a todos sus clientes la utilización de todo su crédito a la vez. El banco también asume que si un cliente maximiza su crédito será capaz de terminar sus negocios y devolver el dinero a la entidad, permitiendo servir a otros clientes.

El algoritmo mantiene al sistema en un estado seguro. Un sistema se encuentra en un estado seguro si existe un orden en que pueden concederse las peticiones de recursos a todos los procesos, previniendo el interbloqueo. El algoritmo del banquero funciona encontrando estados de este tipo.

Los procesos piden recursos, y son complacidos siempre y cuando el sistema se mantenga en un estado seguro después de la concesión. De lo contrario, el proceso es suspendido hasta que otro proceso libere recursos suficientes.

En términos más formales, un sistema se encuentra en un estado seguro si existe una secuencia segura. Una secuencia segura es una sucesión de procesos, ,..., , donde para un proceso , el pedido de recursos puede ser satisfecho con los recursos disponibles sumados los recursos que están siendo utilizados por , donde j < i. Si no hay suficientes recursos para el proceso , debe esperar hasta que algún proceso termine su ejecución y libere sus recursos. Recién entonces podrá tomar los recursos necesarios, utilizarlos y terminar su ejecución. Al suceder esto, el proceso i+1 puede tomar los recursos que necesite, y así sucesivamente. Si una secuencia de este tipo no existe, el sistema se dice que está en un estado inseguro, aunque esto no implica que esté bloqueado.

Así, el uso de este tipo de algoritmo permite impedir el interbloqueo, pero supone una serie de restricciones:

Se debe conocer la máxima demanda de recursos por anticipado.

Los procesos deben ser independientes, es decir que puedan ser ejecutados en cualquier orden. Por lo tanto su ejecución no debe estar forzada por condiciones de sincronización.

Debe haber un número fijo de recursos a utilizar y un número fijo de procesos.

Los procesos no pueden finalizar mientras retengan recursos.

Vídeo explicatorio

Algoritmo del barbero dormilon

Algoritmo del barbero dormilón

En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias sillas para esperar. Cuando no hay clientes, el barbero se sienta en una silla y se duerme. Cuando llega un nuevo cliente, éste o bien despierta al barbero o —si el barbero está afeitando a otro cliente— se sienta en una silla (o se va si todas las sillas están ocupadas por clientes esperando). El problema consiste en realizar la actividad del barbero sin que ocurran condiciones de carrera. La solución implica el uso de semáforos y objetos de exclusión mutua para proteger la sección crítica.

Un semáforo es una variable protegida (o tipo abstracto de datos) que constituye el método clásico para restringir o permitir el acceso a recursos compartidos (por ejemplo, un recurso de almacenamiento) en un entorno de multiprocesamiento. Fueron inventados por Edsger Dijkstra y se usaron por primera vez en el sistema operativo THEOS.

En electrónica y en programación concurrente, se conoce como condición de carrera al error que se produce en programas o circuitos lógicos que no se han construido adecuadamente para su ejecución simultánea con otros procesos.

Vídeo explicatorio

Paralelismo

Paralelismo

El paralelismo se basa en la informática, es una función que realiza el procesador para ejecutar varias tareas al mismo tiempo. Es decir, puede realizar varios cálculos simultáneamente, basado en el principio de dividir los problemas grandes para obtener varios problemas pequeños, que son posteriormente solucionados en el paralelo.

Aplicaciones

El empleo de la computación paralela se convierte cada día en mas grandes y rápida, muchos problemas considerados anteriormente muy largos y costosos se han podido solucionar. El paralelismo se ha utilizado para muchas temáticas diferentes, desde bioinformática para hacer plegamientos de proteínas, hasta economía para hacer simulaciones en matemáticas financieras.

Aplicaciones comerciales. Las aplicaciones para sistemas en paralelo se están expandiendo al ganar impulso el mercado de aplicaciones comerciales estratégicas y entrar en sus fases iniciales el mercado de servidores video.

- Proceso de rendimiento global. Tanto los usuarios técnicos como los comerciales están evaluando los sistemas en paralelo como motores de rendimiento global o throughput.

- Escalamiento para gestión de capacidad. En el mercado comercial, los usuarios están explorando el paralelismo como una forma de ofrecer una gestión de la capacidad optimizada y de bajo riesgo.

- Impulso del software. Los vendedores de software están comenzando a mostrar un mayor interés en desarrollar aplicaciones paralelas como consecuencia de que cierto número de vendedores de hardware importantes están suministrando productos de proceso en paralelo o han anunciado estrategias para penetrar en este mercado.

Tipos de paralelismo Informática

1. Nivel bit

Se basa en el tamaño de la palabra que es capaz de manejar el procesador:

8 bits

16 bits

32 bits

64 bits .....

Mecanismos de la arquitectura son utilizados entonces para ejecutar este tipo de paralelismo:

Pipelining

Superscalar

Ejecución desordenada

Ejecución especulativa

Renombramiento de registros

Predicción de precedencia de memoria

Predicción de ramificaciones del flujo

3. Nivel de Datos

Este tipo de paralelismo se enfoca en la distribución de los datos entre varios procesadores.

Se conoce también como paralelismo a nivel de lazos (loop-level paralelism).

4. Nivel tarea

Ø En este caso un programa paralelo que ejecuta cálculos distintos sobre el mismo conjunto de datos o sobre datos diferentes.

Ø El paralelismo funcional generalmente no escala con el tamaño del problema.

Ø El paralelismo o procesamiento paralelo ha sido empleado durante muchos años, sobre todo para la computación de alto rendimiento. Teniendo en cuenta las generaciones de procesadores y sus características.

Obtener distintos resultados a partir de un mismo conjunto de datos, por ejemplo:

ü Para un matriz hallar

ü El determinante

ü La traspuesta

ü La inversa

Desventajas

· Requieren de un gran número de ciclos de procesamiento o acceso a una gran cantidad de datos.

· Encontrar un hardware y un software que permitan brindar estas utilidades comúnmente proporciona inconvenientes de costos, seguridad y disponibilidad.

Ventajas

Ø Brinda a las empresas, instituciones y usuarios en general el beneficio de la velocidad

Ø Ventajas competitiva, parvee una mejora de los tiempos para la producción de nuevos productos y servicios.

Ø Colaboración y flexibilidad operacional

Vídeo explicatorio

Concurrencia

Concurrencia de procesos

La concurrencia de procesos se refiere a las situaciones en las que dos o más procesos puedan coincidir en el acceso a un recurso compartido o, dicho de otra forma, que requieran coordinarse en su ejecución. Para evitar dicha coincidencia, el sistema operativo ofrece mecanismos de arbitraje que permiten coordinar la ejecución de los procesos.

El problema del productor y consumidor

Un ejemplo de un problema de concurrencia sería el siguiente: Dados dos procesos A (productor) y B (consumidor), suponiendo que ambos se ejecutan indefinidamente en el tiempo, el proceso A debe recibir tiempo de ejecución antes que B, tras esto, el proceso B debe recibir su oportunidad de ejecución, dando paso de nuevo al proceso A y así sucesivamente, siguiendo un esquema de alternancia estricta.

Mecanismos de arbitraje

Los mecanismos de arbitraje que ofrece el sistema operativo son básicamente dos:

• Mecanismos de sincronización: el sistema operativo ofrece mecanismos que permiten a los procesos coordinar su ejecución para conseguir el objetivo sin que sucedan situaciones no deseadas, como por ejemplo que dos o más procesos coincidan simultáneamente en el acceso a un cierto recurso que no se puede compartir.

• Mecanismos de mensajería: el sistema operativo ofrece mecanismos de comunicación entre procesos mediante mensajes. El intercambio de mensajes entre procesos permite coordinarlos.

Vídeo explicatorio

Semaforos

Semaforos

Un semáforo es una estructura diseñada para sincronizar dos o más threads o procesos, de modo que su ejecución se realice de forma ordenada y sin conflictos entre ellos.

El por qué no se pueden usar directamente otras estructuras mas clásicas, como por ejemplo usar una variable común para decidir si se puede o no acceder a un recurso, se debe a que estamos en un sistema multitarea: hacer esto implicaría realizar una espera activa (un bucle, comprobando constantemente si la variable está o no a 0, y así saber si podemos seguir ejecutando o no). Por otro lado, puede ocurrir algo mucho peor: supongamos que un proceso comprueba la variable, y ve que el recurso está libre, por lo que procedería a cambiar dicha variable de valor y seguir. Pues bien, si justo después de la comprobación pero antes de que cambie el valor se conmuta de tarea (puede pasar, pues el sistema operativo puede hacerlo en cualquier momento), y el nuevo proceso comprueba la variable, como todavía no se ha actualizado, creerá que el recurso está libre, e intentará tomarlo, haciendo que ambos programas fallen. Lo peor del caso es que se tratará de un error aleatorio: unas veces fallará (cuando se produzca cambio de tarea en ese punto) y otras no.

Se empieza por inicializar la posición de memoria a 1 (o al valor correspondiente si ese recurso concreto admite más de un acceso simultáneo). Esto se hace en el inicio del programa principal.

A continuación, cada vez que un thread o un proceso quiera acceder a dicho recurso (por ejemplo, un fichero), hará primero una petición con la primera de las llamadas disponibles. Cuando el S.O. ejecuta esa llamada, comprueba el valor que hay en la posición de memoria del semáforo, y si es distinta de cero, se limita a restarle 1 y devolver el control al programa; sin embargo, si ya es cero, duerme al proceso que hizo la petición y lo mete en la cola de procesos, en espera de que el semáforo se ponga a un valor distinto de cero.

Por último, cuando el proceso ha terminado el acceso al recurso, usa la segunda llamada para liberar el semáforo. Cuando el S.O. la ejecuta, comprueba si la cola del semáforo está vacia, en cuyo caso se limita a incrementar el valor del semáforo, mientras que si tiene algún proceso, lo despierta, de modo que vuelve a recibir ciclos de CPU y sigue su ejecución. Si había varios procesos en espera, se irán poniendo en marcha uno tras otro a medida que el anterior va liberando el semáforo. Cuando termina el último, el semáforo se vuelve a poner a 1. Se trata, por tanto, del mismo proceso que seguiríamos con la variable, pero con la ventaja de que es un mecanismo estandar para todos los procesos, y como es una operacion atómica (esto es, que durante su ejecución no se admiten cambios de tarea), no surje el problema de que una conmutación pueda producir errores aleatorios.

Vemos que la primera vez que un proceso usa el semáforo, este tiene valor 1, por lo que pasa a cero y el proceso puede acceder al recurso. Si durante ese tiempo otro proceso quiere acceder también, al usar el semáforo, este tiene valor cero, por lo que el S.O. deja de darle ciclos de CPU. Cuando el primer proceso ha terminado, libera el recurso, con lo que el S.O. puede comprobar que el segundo proceso está esperando, por lo que le vuelve a dar ciclos. En este punto, el proceso sigue como si nunca hubiese sido detenido. Este tipo de semáforos son los de Exclusión mútua, o Mutex.

Vídeo explicatorio

Inanición

Inanición

En informática, inanición (starvation en inglés) es un problema relacionado con los sistemas multitarea, donde a un proceso o un hilo de ejecución se le deniega siempre el acceso a un recurso compartido. Sin este recurso, la tarea a ejecutar no puede ser nunca finalizada.

La inanición no es sinónimo de interbloqueo, aunque el interbloqueo produce la inanición de los procesos involucrados . La inanición puede (aunque no tiene porqué) acabar, mientras que un interbloqueo no puede finalizar sin una acción del exterior.

Un caso de inanición la ilustra perfectamente la paradoja conocida como la cena de los filósofos de Edsger Dijkstra cuando se da el caso de que todos los filósofos cogen el tenedor a la vez.

La utilización de prioridades en muchos sistemas operativos multitarea podría causar que procesos de alta prioridad estuvieran ejecutándose siempre y no permitieran la ejecución de procesos de baja prioridad, causando inanición en estos. Es más, si un proceso de alta prioridad está pendiente del resultado de un proceso de baja prioridad que no se ejecuta nunca, entonces este proceso de alta prioridad también experimenta inanición (esta situación se conoce como inversión de prioridades). Para evitar estas situaciones los planificadores modernos incorporan algoritmos para asegurar que todos los procesos reciben un mínimo de tiempo de CPU para ejecutarse.

Vídeo explicatorio cena de filósofos

Bloqueo mutuo

En sistemas operativos, el bloqueo mutuo (también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo permanente de un conjunto de procesos  o hilos de ejecución en un sistema concurrente que compiten por recursos del sistema o bien se comunican entre ellos. A diferencia de otros problemas de concurrencia de procesos, no existe una solución general para los interbloqueos.

Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.

En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock sobre ese recurso). El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.

Condiciones necesarias

También conocidas como condiciones de Coffman por su primera descripción en 1971 en un artículo escrito por E. G. Coffman.

Estas condiciones deben cumplirse simultáneamente y no son totalmente independientes entre ellas.

Sean los procesos P0, P1, ..., Pn y los recursos R0, R1, ..., Rm:

Condición de exclusión mutua: existencia de al menos de un recurso compartido por los procesos, al cual sólo puede acceder uno simultáneamente.

Condición de retención y espera: al menos un proceso Pi ha adquirido un recurso Ri, y lo retiene mientras espera al menos un recurso Rj que ya ha sido asignado a otro proceso.

Condición de no expropiación: los recursos no pueden ser expropiados por los procesos, es decir, los recursos sólo podrán ser liberados voluntariamente por sus propietarios.

Condición de espera circular: dado el conjunto de procesos P0...Pm(subconjunto del total de procesos original),P0 está esperando un recurso adquirido por P1, que está esperando un recurso adquirido por P2,... ,que está esperando un recurso adquirido por Pm, que está esperando un recurso adquirido por P0. Esta condición implica la condición de retención y espera.

Vídeo explicativo