Hola, hoy encontré esta página Edsger Dijkstra, el pensador informático , vale la pena darle una leída, me permito copiarla en caso de que el blog original desaparezca
Tomado del Blog original:
BIOGRAFÍA
· Edsger Wybe Dijkstra, nacido en Rotterdam, Países Bajos el 11 de mayo de 1930, fue un científico de la computación de los Países Bajos y falleció en Nuenen, Países Bajos el 6 de agosto de 2002, después de una larga lucha contra el cáncer.
· Dijkstra estudió física teórica en la Universidad de Leiden. Trabajó como investigador para Burroughs Corporation a principios de los años 1970. En la Universidad de Texas en Austin, Estados Unidos, ocupó el Schlumberger Centennial Chair in Computer Sciences. Se retiró en 2000.
· Entre sus contribuciones a las ciencias de la computación está la solución del problema del camino más corto, también conocido como el algoritmo de Dijkstra, la notación polaca inversa y el relacionado algoritmo shunting yard, THE multiprogramming system, el algoritmo del banquero y la construcción del semáforo para coordinar múltiples procesadores y programas.
· El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
· La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
· El problema de los filósofos cenando es un problema clásico de las ciencias de la computación propuesto por Edsger Dijkstra en 1965 para representar el problema de la sincronización de procesos en un sistema operativo. Cabe aclarar que la interpretación está basada en pensadores chinos, quienes comían con dos palillos, donde es más lógico que se necesite el del comensal que se siente al lado para poder comer.
· Cinco filósofos se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su izquierda y derecha. Si cualquier filósofo coge un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger el otro tenedor, para luego empezar a comer.
· Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.
· Si todos los filósofos cogen el tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en la misma situación (esperando que alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este bloqueo mutuo se denomina interbloqueo o deadlock.
· El problema consiste en encontrar un algoritmo que permita que los filósofos nunca se mueran de hambre.
Algunas posibles soluciones
· Por turno cíclico
Se empieza por un filósofo, que si quiere puede comer y después pasa su turno al de la derecha. Cada filósofo sólo puede comer en su turno. Problema: si el número de filósofos es muy alto, uno puede morir de hambre antes de su turno.
· Varios turnos
Se establecen varios turnos. Para hacerlo más claro supongamos que cada filósofo que puede comer (es su turno) tiene una ficha que después pasa a la derecha. Si por ejemplo hay 7 comensales podemos poner 3 fichas en posiciones alternas (entre dos de las fichas quedarían dos filósofos).
Se establecen turnos de tiempo fijo. Por ejemplo cada 5 minutos se pasan las fichas (y los turnos) a la derecha.
En base al tiempo que suelen tardar los filósofos en comer y en volver a tener hambre, el tiempo de turno establecido puede hacer que sea peor solución que la anterior. Si el tiempo de turno se aproxima al tiempo medio que tarda un filósofo en comer esta variante da muy buenos resultados. Si además el tiempo medio de comer es similar al tiempo medio en volver a tener hambre la solución se aproxima al óptimo.
· Colas de tenedores
Cuando un filósofo quiere comer se pone en la cola de los dos tenedores que necesita. Cuando un tenedor está libre lo toma. Cuando toma los dos tenedores, come y deja libre los tenedores.
Visto desde el otro lado, cada tenedor sólo puede tener dos filósofos en cola, siempre los mismos.
Esto crea el problema comentado de que si todos quieren comer a la vez y todos empiezan tomando el tenedor de su derecha se bloquea el sistema (deadlock).
· Resolución de conflictos en colas de tenedores
Cada vez que un filósofo tiene un tenedor espera un tiempo aleatorio para conseguir el segundo tenedor. Si en ese tiempo no queda libre el segundo tenedor, suelta el que tiene y vuelve a ponerse en cola para sus dos tenedores.
Si un filósofo A suelta un tenedor (porque ha comido o porque ha esperado demasiado tiempo con el tenedor en la mano) pero todavía desea comer, vuelve a ponerse en cola para ese tenedor. Si el filósofo adyacente B está ya en esa cola de tenedor (tiene hambre) lo toma y si no vuelve a cogerlo A.
Es importante que el tiempo de espera sea aleatorio o se mantendrá el bloqueo del sistema.
· El portero del comedor
Se indica a los filósofos que abandonen la mesa cuando no tengan hambre y que no regresen a ella hasta que vuelvan a estar hambrientos (cada filósofo siempre se sienta en la misma silla). La misión del portero es controlar el número de filósofos en la sala, limitando su número a n-1 (n es el numero de filósofos), pues si hay n-1 comensales seguro que al menos uno puede comer con los dos tenedores.
· 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.
· 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.
Bueno, dejé estos tres casos para no hacer tan largo y engorroso el post. Por último les dejo una información sobre el premio Dijkstra
· El Premio Edsger W. Dijkstra es una distinción que se entrega a los autores de artículos destacados en los principios de computación distribuida. Su nombre es en reconocimiento del cientista de computación Edsger W. Dijkstra. Los artículos seleccionados deben significar un aporte importante en la teoría o práctica del área de la computación distribuida, al menos durante los últimos 10 años. Es otorgado anualmente en el Simposium en Principios de Computación Distribuida de la Association for Computing Machinery, y una vez finalizado el Congreso se publica una descripción con las contribuciones del artículo.
· Durante los tres primeros años, el premio se llamó PODC Influential Paper Award.
GANADORES
· 2000 – Leslie Lamport por su artículo sobre relojes lógicos.
· 2001 – Michael J. Fischer, Nancy A. Lynch y Michael S. Paterson, por demostrar la imposibilidad de consensos usando comunicación asincrónica.
· 2002 – Edsger W. Dijkstra por su artículo que establece el principio de autoestabilización.
· 2003 – Maurice Herlihy por su artículo que resuelve y universaliza el consenso en sistemas de memoria compartida distribuida.
· 2004 – Robert G. Gallager, P. A. Humblet y P. M. Spira, por su algoritmo de distribución para encontrar un árbol spanning mínimo.1
· 2005 – Marshal Pease, Robert Shostak y Leslie Lamport, por su artículo de tolerancia a fallos bizantinos.
· 2006 – John M. Mellor-Crummey y Michael L. Scott, por su algoritmo de exclusión mutua.
· 2007 – Cynthia Dwork, Nancy A. Lynch y Larry Stockmeyer, por su artículo que resuelve el consenso en sistemas