Etiquetas
Hay un tema que se estudia en todas las carreras de informática, el de «sincronización, concurrencia y exclusión mutua entre procesos». Surgió en la década de 1950 cuando empezaron a desarrollarse los primeros sistemas con multiprogramación. Aunque surgió como problemática de sistemas operativos se ha convertido en un tema de general y fundamental en informática. Todas las carreras de informática incluyen su estudio tanto en las asignaturas de sistemas operativos como en otras específicas de programación concurrente.
El tema de concurrencia (y su hermano más complejo «programación distribuida») es un típico tema de «ciencias de la computación», donde se estudian los algoritmos y se prueban formalmente que funcionan: se demuestra que aseguran exclusión mutua, que no produce inanición (starvation), ni interbloqueos (deadlocks). No es simple enseñar estos temas y sus soluciones obligan a pensar de otro manera, un programa ya no es una serie secuencial de instrucciones, sino que se mete por medio una intercalación «no controlada» y no determinística de otras instrucciones de procesos independientes.
El tema de exclusión mutua es un tema relativamente sencillo de demostrar, por ejemplo este código que suma una variable desde cero hasta 99.999.999 (cien millones menos uno), pero no lo hace de una forma tradicional, sino que son dos hilos (threads) los que la incrementan individualmente. Podéis compilarlo y probarlo (no olvidéis de compilarlo con la opción -pthread), veréis que produce unos errores enormes. El problema es que dos procesos diferentes acceden al mismo recurso compartido (la variable count) y se «pierden» operaciones debido a las interrupciones e intercalaciones.
Este caso es muy estudiado y todas las asignaturas comienzan con algo similar, es la exclusión mutua entre [solo] dos procesos. Así se estudian los «cuatro intentos» para solucionarlo, luego el algoritmo de Dekker y finalmente el de Peterson (aquí los tenéis a todos).
Así se puede demostrar formalmente que funciona correctamente, que asegura exclusión mutua y tal y cual. Pero si lo implementas (aquí lo tenéis listo para compilar y ejecutar con el ejemplo anterior) y lo pruebas en cualquier ordenador moderno verás que… falla como escopeta de feria.
¿Qué pasó? ¿Falla la teoría? ¿Fallan las demostraciones? ¿Los teóricos de las ciencias de la computación no sirven para nada?
Actualización: la respuesta.
Ninguna de ellas, este es un típico ejemplo donde la teoría se distanció de la «realidad», o mejor dicho, donde la evolución tecnológica de los microprocesadores modernos hace que las técnicas de concurrencia que dábamos por buenas (y que lo son formalmente y con todos los modelos de computación y/o de lenguajes «tradicionales») ya no funcionen. Es la diferencia entre hacer «sólo ciencia» y la «ingeniería» (es decir, resolver problemas que te impone la realidad, no tan perfecta como la teoría).
Tampoco es para los ingenieros se feliciten y miren por encima del hombro a los teóricos, porque la mayoría de «ingenieros» tampoco saben explicar o resolver este problema, muchas veces ni siquiera son capaces de identificarlo (no, si estás leyendo este blog no eres de la «media», eres bastante friki y al menos lo habrás oído, o sabrás buscar rápidamente en la Wikipedia o Stackoverflow 😉 ).
Si no tienes idea de qué está pasando, ya lo explicaré en un comentario (si nadie lo hace antes), pero mientras tanto puedes ir probando este otro código que sí funciona y sólo difiere en una línea con el anterior.
Sólo quería recordar que aún en ciencias tan «formales» como la informática la teoría no siempre funciona en la práctica, que el tema de concurrencia tiene sus complejidades no siempre a la vista, que un buen ingeniero debe saber reconocer esos problemas y poder solucionarlo, y que esto exige que conozcamos bastante de detalles del hardware y microprocesadores actuales.
No es nada simple, lleva su tiempo, y tendemos a pensar que lo sabemos todo. O que la «ingeniería informática» consiste en saber liderar sprints de Scrums con postits de colores fosforitos.
PS: Por estas cosas, entre muchas, la informática es apasionante.
Ricardo Galli, de software 
El switch de compilación es -lpthread, no -pthread. (Sí, aquí un friki que está haciendo correr este código a las tres y media)
Pingback: Ciencias de la computación e ingeniería, y [algunas de] sus diferencias
@lvps100vm
No sé en qué sistema estás compilando, pero en la mayoría de GNU/Linux te sale que el recomendado es -pthread (p.e. man pthread_create) y también sale en el manual del gcc:
-pthread
Adds support for multithreading with the pthreads library. This option sets flags for both the preprocessor and linker.
(i.e. al poner -lpthread sólo pones la opción para el linker, no para el preprocesador).
pues ya puedes ir olvidándote de que otros compartan esa pasión contigo, principalmente por que nadie querrá ponerse a estudiar una carrera cuyo titulo vale menos que el papel higiénico…piensa en el ultimo hit en Madrid sobre meterles programación a los chavales de instituto. ¿Para que una consultora va a contratar a un ingeniero si puede explotar a un adolescente de 16 años con 2 años de programación, que a su vez nunca tendrá que lidiar con esos problemas teóricos que planteas?
@Jorge
Ya tuvo que salir la costumbre llorica informática de echar las culpas a otros, incluso sacando el tema de programación en institutos (cosa que a mí me alegra) cuando estamos hablando de cosas de nuestra profesión.
No tenemos, o no tenéis remedio 😦
Por cierto, ¿sabes por qué pasa esto?
Mirando el codigo que has puesto que se supone que debe de funcionar, pero no lo hace ( http://pastebin.com/3MezNGbQ ) creo que es debido a que las diferentes funciones se ejecutan sin tener en cuenta que la multitarea del hardware puede detener un proceso (o funcion) a medias y dar paso a la ejecución del otro thread. Es una hipotesis, no lo certifico pues no lo he probado. 😀
Supongo que por eso, en el segundo ejemplo se llama a una funcion que sincroniza los turnos. Es decir, que no continua hasta que no se ha competado la funcion de incrimento.
supongo que tambien se podria implementar de manera interna con alguna variable que hiciera de semaforo, sin complicar mucho el codigo.
va por ahi?
incremento, queria decir. 😛
No he mirado los algoritmos de los que hablas, pero sí que conozco un poco el problema. Hacer que tus hilos se sincronicen no es una solución escalable cuando el «particionamiento» (aquí, número de hilos) aumenta. Es preferible usar otras estrategias que no utilicen variables compartidas como lo que se hace en la programación funcional. Recomiendo un vistado del Teorema CAP: http://es.wikipedia.org/wiki/Teorema_CAP
@Jorge
A mi me gusta programar. Hice la ingeniería técnica de informática porque tenía que estudiar una carrera, pero ya sabía programar algo desde los 15 años. No entiendo por qué no darles esa oportunidad ahora, algunos podrían descubrir su futuro como yo hice.
¿Que alguien contrata sin tener la carrera? Pues quizá porque no lo necesita, o no sabe dónde se mete. No entiendo la apropiación del conocimiento con colegiados, corporativismo y cosas así. Esto me recuerda a los taxistas con sus caras licencias y a uber, todos sabemos donde va a terminar todo esto con los años.
Tengo ya 44 años y sigo estudiando, sorprendiéndome, sintiendo ganas de rehacer todo lo hecho anteriormente por el mero hecho de hacerlo mejor, en definitiva es apasionante.
@Jorge si tu problema es que una consultora contrate a gente de instituto tienes un problema de lo que son las ciencias de la computación y la ingeniería informatica. Si crees que un chaval de instituto te va a quitar el trabajo quizas tu trabajo no vale nada y es lo mejor profesionalmente que te puede pasar.
@chemacortes
Es verdad que hay problemas de la sobrecarga por las esperas activas (por eso se utilizan mecanismos con bloqueos, como semáforos, synchronized en Java, o monitores -wait()+notify() en Java-).
Pero eso no es el problema que comento, no falla por eso (ni la espera activa debería ser causa de fallo). Tiene que ver con las optimizaciones en procesadores modernos (y la memoria caché, pero no es lo habitual en la mayoría de vuestros ordenadores).
Sobre el CAP, eso es para bases de datos distribuidas, relacionados con algoritmos distribuidos, que son mucho más complejos que estos (de «memoria compartida»).
Creo que el problema es que aunque las variables estén compartidas entre los hilos, sus modificaciones no se «llevan a memoria» en cada modificación; simplemente se modifican en la cache asociada al core en el que corre el hilo. La instrucción de sincronización hace que todas las modificaciones que hay en la cache se pasen a memoria.
Por cierto, en Java creo que con el volatile ya habría suficiente para que el sistema funcionase correctamente.
OK. Ya decía que no había entrado en profundidad a revisar el código. Me ha recordado mucho a un artículo que leí en la revista Queue de la ACM y que ya hablaba de los problemas de las caches en multihilo y que fue lo que me motivó a buscar alternativas como la FP: http://queue.acm.org/detail.cfm?id=2088916
El teorema CAP es aplicable a cualquier proceso distribuido, no sólo a base de datos. En el ejemplo que pones, estaríamos hablando de un contador que no puede ser coherente y estar disponible a la vez, una especie de «Principio de Incertidumbre» de la concurrencia que se hace más evidente a medida que crece el particionado.
Creo que el problema es que en cada thread, las líneas 18 y 19 no dependen del resultado de la línea 17, por lo que el resultado de esta última es susceptible de ser ejecutada en paralelo con las otras dos. Eso puede hacer que el orden efectivo de ejecución del código sea 18, 19, 17
Si eso ocurriese en ambos threads, los dos entrarían en la zona crítica (porque ninguno de los dos puso el estado a 1 antes de que el otro chequease)
La línea 19 sí depende de la 18 por lo que, en principio, el sync se debería poder poner entre la 17 y la 18, en vez de entre la 18 y la 19 como has puesto.
Llego al trabajo, me pongo a limpiar el correo y me encuentro una entrada interesante que me hace pensar (o divertir) un rato. Luego la productividad, por responsabilidad del autor del blog baja.
@jorge || @ Miguel A. Guillen
El problema respecto al trabajo es que muchas veces los ingenieros en informática en un arrebato de desesperación económica pretenden quitarle el trabajo a los chavales de 16 años del instituto.
Cuando un programa corto, tiene cierta sofisticación y debe ser robusto, normalmente el programador sin nociones de ingeniería fracasa. Puede que en una primera presentación de el pego, pero cuando se bloquea, no responde en el tiempo requerido o simplemente desborda el ordenador es cuando no se puede negar la evidencia.
Tengo muchos clientes que se dedican a realizar automatización de instalaciones industriales, la mayoría en Visual Basic sin objetos, ni hilos. El resultado son auténticos bodrios, que cuestan un montón de horas y que acaban con la paciencia del cliente final. Algunos clientes acaban tan quemados que no quieren saber nada de automatización y prefieren un proceso manual.
***
Por las palabras de Gallir entiendo que algunos procesadores modernos al optimizar el código hacen que las instrucciones no se ejecuten en el orden correcto y eso hace que los programas fallen. Me sorprende, pues desde mi punto de vista es como si esa optimización estuviese mal implementada.
Imagino que se referirá a procesadores CISC tipo Intel que traducen las instrucciones a otro código más simple que es el que se cachea y optimiza. Cuando he leído sobre el tema me parece algo excesivamente complejo y no termino de verle el sentido.
Me pregunto si estos fallos producidos por optimización del código en el procesador ¿ocurre en todas las arquitecturas?
Aclaro que a mi en ingeniería informática (hace ya unos años) siquiera me mencionaron esa posibilidad.
No tiene por qué ser el procesador. El propio compilador te la puede liar igual.
Lo que ocurre lo explica aquí bastante bien:
http://en.wikipedia.org/wiki/Memory_barrier
La instrucción __sync_synchronize() hace precisamente lo que se dice en la wikipedia: asegura que las instrucciones antes del sync han sido ejecutadas una vez acaba la ejecución del sync, de esta manera evitas problemas por la reordenación de las instrucciones que hacen los últimos procesadores por temas de rendimiento.