Etiquetas

,

Este artículo es el primer manuscrito del Prefacio y concurrencia del libro que estoy escribiendo Principios y algoritmos de concurrencia. Todo el código de los ejemplos están en Github.

Nota: me gustaría leer opiniones.

Manifiesto

Hace más de veinte años que enseño Concurrencia en las asignaturas de Sistemas Operativos I y II y en Programación Concurrente y Distribuida de la carrera de informática en la Universitat de les Illes Balears. A pesar de la cantidad de notas y presentaciones que elaboré en todos estos años, nunca se me pasó por la cabeza escribir un libro. Ni siquiera el típico libro de apoyo a la asignatura. Es sumamente complicado transmitir las sutilezas y conflictos generados por ejecuciones que no cumplen con la secuencialidad de sus programas. Si ya me resultaba difícil en clases magistrales y prácticas en laboratorio, me parecía tarea imposible escribir un libro.

Pero eso cambió en diciembre de 2014.

Motivación

Javier Candeira, un programador que no estudió informática, estaba trabajando con estructuras concurrentes y quería aprender más. Me preguntó en Twitter qué bibliografía le recomendaba. Me metió en un problema.

Hay buenos libros de texto de Concurrencia, pero además de ser caros –en general superan los 60 €– están muy orientados a la parte formal del problema, no a las aplicaciones prácticas. También suelen usar lenguajes y formalismos poco usados (Promela, Concurrent Pascal, BACI, ADA) que no tienen sentido para un programador que quiere aprender o actualizarse y poder transferir rápidamente esos conocimientos a su lenguaje preferido.

Hay buenos libros de divulgación y actualización (como [Herlihy12]), pero además de caros están especializados y orientados a una audiencia más académica. También hay buenos libros orientados a un lenguaje en particular, pero no explican los orígenes y principios fundamentales de concurrencia.

No hice un extenso análisis de mercado, no obstante, me di cuenta de que me resultaba imposible recomendar un libro. No encontraba uno que explicase concurrencia de la forma que consideraba adecuada para un programador: riguroso y que explique los principios fundamentales pero sin exagerar con las formalidades académicas.

Casi como una broma respondí ‘a ver si tengo que escribirlo en un ebook‘, lo que generó inmediatas peticiones para que lo hiciese.

Así es como surgió este libro: no sabía en lo que me metía. Pensé que lo podría hacer en tres meses con menos de 20 000 palabras, pero acabó teniendo más de 60 000 además de las 10 000 líneas de código en cinco lenguajes diferentes escritos exclusivamente para este libro.

Creo que en el libro logro explicar, con ejemplos en lenguajes modernos y populares, lo que considero fundamental de los principios y algoritmos claves de concurrencia. Es una opinión subjetiva, cada lector tendrá la suya, también quejas de por qué no incluí esa característica tan especial de su lenguaje preferido. Es muy difícil rebatir este tipo de cuestiones. Se necesitaría un ensayo filosófico y seguiría siendo discutible, pero cuento con la ventaja de haber enseñado estos temas durante dos décadas. No solo sé lo que me ha costado dominar ciertos temas, también lo que cuesta transmitir y hacer captar las sutilezas de la programación concurrente.

No se trata de aprender de memoria unos algoritmos, ni de saber exactamente cómo y cuándo usarlos. Se trata de otra forma de pensar la programación. Los programas ya no son una secuencia de instrucciones, se ha de razonar de forma diferente. No se trata de solo este programa, sino de cómo puede interactuar con otros; y cómo afecta la ejecución de esos otros a los resultados de este. Esto no se adquiere en una asignatura ni leyendo un libro durante un fin de semana. Requiere motivación y entrenamiento, pero no cabe duda de la utilidad de un libro que explique los fundamentos y los acompañe con código de demostración.

Mi sensación es que no había un libro pensado para el programador que no tuvo la suerte de una formación universitaria; que quiere actualizarse; o que sencillamente se olvidó de lo que estudió en esa oscura asignatura años atrás y hoy tiene las ganas o la necesidad de recordarlo.

Ante esta situación, y dado que el tiempo para escribir un libro es finito, estuve obligado a filtrar y seleccionar lo fundamental, separar los principios de lo que son derivaciones o metaconstrucciones sobre esos pilares básicos. Hice el esfuerzo, no sé si están todos los que son pero sí sé que los que están son fundamentales.

Escribir un ebook técnico legible

Este libro tiene muchos algoritmos y programas completos, mis experiencias con libros electrónicos de este tipo no son las mejores (estoy siendo comedido). La mayoría incluyen ejemplos de programas –con tratamientos de excepciones incluidas– cuyas líneas no alcanzan a mostrarse completas en la pequeña pantalla del lector. Me duele la cabeza de solo recordarlo, hay que hacer un gran esfuerzo para descifrar la parte importante del algoritmo.

Al momento de escribir estas líneas no sé si habrá una versión impresa del libro –no contacté con ninguna editorial–, la intención desde el principio fue hacer un ebook que fuese accesible, compacto y con ejemplos razonablemente fáciles de leer. Fui muy cuidadoso y meticuloso en estos aspectos y creo que el resultado es bueno[1]. En vez de inventar otro pseudocódigo usé directamente Python: es expresivo, fácil de comprender y los programas además son válidos.

Por esa claridad y expresividad muchos ejemplos están escritos en Python. Los programas completos están en cinco lenguajes diferentes (C, Python, Java, Go y ensamblador de ARM). Usé siempre el que me pareció más apropiado para demostrar lo que estaba explicando. En algunos casos traduje el código a Python para explicarlo en el texto, en otros casos usé el lenguaje original pero quitando lo accesorio (como largas listas de argumentos, tratamiento de excepciones y nombres extensos).

De todas formas, me parece importante poder analizar el código completo. Dado que un ebook no tiene las restricciones de un libro físico, todos los programas están disponibles directamente desde el lector. El listado completo de todos los programas está en los apéndices al final del libro (aproximadamente el 30 % del total de contenido del libro) y cada uno de ellos está enlazado desde el texto donde se discute el código simplificado. Ya en el apéndice, justo antes del código, está el enlace al original en Github.

Creo que en este aspecto cumplí los objetivos. Los algoritmos en el texto son legibles –aún en pantallas de teléfonos–, muestran la parte que interesa y no necesitan tres pantallas para leerse. Pero con un clic se puede ver el programa completo sin salir del libro y con otro clic se puede acceder al repositorio para bajarlo a un ordenador.

Sobre el contenido

Intenté que este libro sea compacto e ir directamente al grano sin demasiadas analogías, como es habitual en los libros de texto. A pesar del esfuerzo deliberado por la brevedad, la longitud final es equivalente a más de 200 páginas –descontando el listado de los programas– de un libro impreso. Cada párrafo suele describir completamente una idea o concepto y cada oración es un avance hacia ese objetivo.

La lectura puede dar la sensación de agobio por la rapidez con que se avanza, algo que también me pasaba durante las revisiones y correcciones. Pido disculpas por no saber hacerlo mejor, pero en cierta forma es inevitable si se escribe un texto donde se introducen tantos temas complejos e interdependientes.

Para facilitar la búsqueda da los que quieren profundizar fui cuidadoso con la bibliografía. Aunque intenté que las referencias fuesen siempre a los artículos científicos originales también me tomé el trabajo de buscarlos y añadir enlaces accesibles.

Conocimientos previos requeridos

No se requieren ni se suponen conocimientos de concurrencia. Solo de programación, estructuras de datos básicas (pilas, colas, listas), fundamentos muy básicos de programación orientadas a objetos y comprender lo que es un puntero o referencia a memoria.

El texto comienza desde los conceptos más básicos y avanza gradual e incrementalmente. No hay conceptos importantes que no se expliquen al menos brevemente. Quizás encuentres algunos que no conoces; si no los expliqué es porque son muy fáciles de encontrar.

Los programas están desarrollados y probados en GNU/Linux. Para ejecutarlos y probarlos se necesita acceso a un ordenador con este sistema. No hace falta ser un experto pero sí tener un mínimo de experiencia con comandos básicos de consola.

Los programas

Uno de los requisitos que me impuse fue que todo lo que explicase debía ir acompañado de programas que compilen y funcionen correctamente. Además de estar listados en los apéndices se pueden bajar desde Github. Son libres, puedes hacer con ellos lo que desees, incluso verificar si lo que explico en el libro es verdad.

Otro requisito autoimpuesto fue que todos los programas deberían poder ser compilados y ejecutados en el ordenador más básico posible: cualquier Raspberry Pi con sus distribuciones estándares de GNU/Linux. Están preparados para que funcionen con cualquier distribución relativamente moderna y probados sobre Raspberry Pi 1 y 2 con Debian Jessie y Ubuntu 14.04. Para compilarlos hay que instalar los paquetes del gcc, Golang, Python y el SDK de Java –todos disponibles en cualquier distribución– y ejecutar el comando make en cada uno de los directorios organizados por capítulos.

La regla para usar uno u otro lenguaje de programación fue elegir el más apto para el tema en cuestión. Si era una buena opción usaba Python. Para Monitores usé principalmente Java porque es un lenguaje popular que los incluye como construcción sintáctica del lenguaje. Para Canales usé Go por la misma razón, son una construcción del lenguaje.

Hay bastantes ejemplos en C. Lo usé cuando no había opción de hacerlo en otro lenguaje o porque era el más adecuado para ese caso. Mi opinión es que los programadores deben saber C, su gramática es muy sencilla y a la vez está muy próximo a la arquitectura. Pero si no lo sabes no te preocupes, aprenderás un poco sin mucho esfuerzo. Los programas son breves, se usan siempre las mismas funciones y están explicados –a veces línea a línea–.

Usé ensamblador en un único caso, no había otra opción para demostrar el funcionamiento de las instrucciones de sincronización LL/SC. Afortunadamente los procesadores ARM de ambos modelos de Raspberry Pi (ARMv6 y ARMv7) soportan esas instrucciones, no hace falta hardware especial o caro.

En algunos algoritmos hay ejemplos en varios lenguajes diferentes, me pareció oportuno mostrar cómo se hacen en cada uno de ellos, o cómo se pueden construir mecanismos similares (notablemente simular monitores en C y Python). Para los que conozcan un lenguaje mejor que otro puede ser clarificador.

Terminología

Escribí el libro en castellano porque pensé que sería mucho más sencillo que hacerlo en inglés. Ahora pienso que quizás me complicó más. Cuando se trata de bibliografía técnica intento leer siempre el original en inglés por lo que no domino la terminología específica en castellano. He tenido que dedicar mucho tiempo a encontrar las traducciones adecuadas para los nombres técnicos, pero me negué a traducir algunas palabras que son parte de nuestro vocabulario habitual como array, buffer, spinlock, scheduler o commit. Espero haber hecho un trabajo aceptable.

Una parte importante del aprendizaje y entrenamiento de cualquier área de conocimiento es conocer la terminología técnica, esta permite la discusión y transmisión del conocimiento de forma más compacta y sin ambigüedades. Para bien o para mal, la lengua vehicular de la informática es el inglés, por lo que es importante conocer también la terminología técnica en ese idioma. En este aspecto fui cuidadoso de indicar el equivalente en inglés cada vez que introduzco un concepto o definición nueva.

Tampoco es fácil seleccionar una definición en particular. Muchas veces doy varios sinónimos –en castellano y en inglés– porque no hay un consenso universal ni en la comunidad científica. Algunos términos se usan más en un entorno (como lock-free y critical section) y en otros se refieren a lo mismo con palabras diferentes (deadlock-free y mutual exclusion respectivamente), en estos casos inicialmente describo ambos términos en castellano e inglés y los uso indistintamente si se entienden en el contexto.

Los gráficos de tiempos

Los libros no suelen incluir gráficos ni comparaciones de tiempos por una buena razón: la tecnología cambia muy rápidamente y los números aburren. El problema es que se hacen afirmaciones rotundas de eficiencia de estrategias o algoritmos pero sin presentar los datos ni el contexto en que fueron tomadas. Quizás tenían sentido en el momento que se diseñaron esos algoritmos, pero los sistemas SMP han evolucionado y mejorado sustancialmente. Las mejoras notables de hace una década hoy pueden ser inexistentes o residuales.

Hice pruebas y mediciones de todos los ejemplos en diferentes arquitecturas. No fueron mediciones escrupulosas para artículos científicos ni descubrí nada nuevo, no tenía sentido que las incluyera a todas. Pero sí incluí algunos gráficos[2] en secciones donde la eficiencia era el tema central, o cuando los datos desmentían la intuición o suposiciones populares. Pido disculpas si me excedí, no siempre salí triunfante contra mi obstinación de cada afirmación debe ir acompañada de los datos que la soportan.

Para docencia

No fue la intención original pero este libro cubre completamente, y con algo más, los contenidos de concurrencia que se suelen dar en las carreras de informática. Hace unos años estos temas eran una parte de las asignaturas de sistemas operativos. Fue en esta área donde primero aparecieron los problemas de concurrencia, era natural que se explicaran en estas asignaturas.

Pero el área de concurrencia se amplió y profundizó. Ya tiene peso e importancia por sí misma[3] por lo que ya existen asignaturas específicas de programación concurrente. Este libro cubre todos los temas de concurrencia que se dan en esas asignaturas y que sería el equivalente a aproximadamente un semestre.

Una de las carencias más importantes en la docencia de Concurrencia es que no se suelen enseñar temas que avanzaron mucho en los últimos años: memoria transaccional, diseño de algoritmos de spinlocks con instrucciones de hardware y las interfaces de los sistemas operativos para la programación de primitivas de sincronización como FUTEX. Es razonable esa carencia, el tiempo es finito y no suelen estar incluidos en los libros de texto de sistemas operativos ni de programación concurrente. Creo que los dos últimos temas mencionados son complejos –quizás para posgrados- pero importantes, por eso dediqué un capítulo a cada uno de ellos con ejemplos de las técnicas y algoritmos más usados.

Capítulos

1. Procesos y concurrencia
Es la introducción a concurrencia, procesos e hilos y cómo son gestionados y planificados por el sistema operativo. Describe el problema del intercalado y cómo es el responsable de los problemas de concurrencia. Me parece que es un capítulo sencillo de entender y de lectura fácil pero importante: define con precisión qué es la programación concurrente.
2. Exclusión mutua
Describe las soluciones por software al problema fundamental de concurrencia, la exclusión mutua. Comienza con los casos más sencillos para dos procesos hasta acabar en soluciones genéricas. Su objetivo también es enseñar cómo se razonan, diseñan y evalúan los programas concurrentes. Si tienes experiencia con programación concurrente y conoces el algoritmo de la panadería podrías saltarte este capítulo, pero si no tienes experiencia o no recuerdas los requisitos y sus razones, es de lectura obligatoria.
3. La realidad del hardware moderno
Las soluciones por software no funcionan si no se tiene en cuenta la evolución y funcionamiento de los procesadores modernos, arquitecturas de multiprocesamiento y modelos de coherencia de la memoria caché. De lectura obligada si no sabes por qué los procesadores no aseguran la consistencia secuencial, o qué son las barreras de memoria.
4. Soluciones por hardware
Se describen las instrucciones de hardware diseñadas para facilitar la sincronización de procesos, cómo usarlas para solucionar la exclusión mutua con spinlocks básicos, los problemas ocultos y sus soluciones. Salvo la última parte, donde se discute y soluciona el problema ABA, no me parece un capítulo muy complejo pero sí muy pedagógico de por qué y cómo se diseñan y usan las operaciones atómicas de los procesadores.
5. Spinlocks avanzados
Es quizás el capítulo más complejo, trata temas que habitualmente no aparecen en los libros de texto (quizás por la complejidad). Avanza en el tema de spinlock, explica cómo hacer más eficientes los spinlocks simples, implementaciones de listas sin bloqueos y los algoritmos más complejos desarrollados recientemente. Es de lectura obligada para los que pretenden convertirse en programadores de sistemas operativos, de sistemas empotrados, o de los que tienen que trabajar con estructuras concurrentes (muy usadas en bases de datos, máquinas virtuales o intérpretes de lenguajes).
6. Semáforos
Con este comienza una segunda parte bien diferenciada. En los capítulos previos se tratan algoritmos con espera activa, a partir de este se estudian las soluciones para evitar esas esperas activas haciendo que los procesos se bloqueen cuando no deben continuar. La construcción de semáforos fue la primera en este sentido, la inventó Dijkstra a finales de la década de 1960 y es sin duda un pilar fundamental de todas las construcciones posteriores para sincronización de procesos. No me parece un capítulo complejo pero sí define muchos conceptos fundamentales, de lectura obligada aunque creas que sabes de semáforos.
7. FUTEX
Es una interfaz del núcleo Linux diseñada específicamente para que las librerías implementen mecanismos de sincronización de procesos de forma muy eficiente. Quizás este es el segundo capítulo en complejidad, pero me parece relevante porque enseña cómo se programan a bajo nivel las primitivas de sincronización que usan las librerías más importantes (incluidas POSIX Threads) y máquinas virtuales. Dado que es una interfaz de interacciones complejas entre el núcleo y procesos de usuario, es difícil encontrar buena documentación de introducción. Este capítulo llena ese hueco. No es necesario leerlo para comprender los otros pero es uno de los que más disfruté escribiendo.
8. Monitores
La construcción de monitores se inventó para solucionar los mismos problemas de sincronización que los semáforos pero de una forma más estructurada. A pesar de que es una construcción sintáctica de un lenguaje tan popular como Java pocos programadores lo conocen. Quizás se deba a que en los libros de texto se enseñan monitores con el casi desaparecido Concurrent Pascal o ADA y se sedimenta la idea de que es un concepto antiguo o abandonado. Al final del capítulo se hacen comparaciones de rendimiento para matar algunos mitos y suposiciones erróneas. Creo que la lectura es bastante accesible, de interés para todos los programadores, especialmente los que programan en Java o con las librerías POSIX Threads (las variables de condición surgieron de los monitores).
9. Canales
Los canales están basados en el concepto de comunicación de procesos secuenciales que inventó Hoare en 1978. Es un modelo genérico de computación de procesos independientes que se comunican y sincronizan únicamente a través de mensajes[4]. Los canales ofrecen las mismas posibilidades de sincronización que semáforos y monitores, además permiten la comunicación sin compartir memoria por lo que facilita la implementación de procesos independientes que pueden ejecutarse en paralelo. Erlang es un lenguaje que se basa en el modelo CSP. En 2010 se publicó la primera versión de Go, también basado en los mismos conceptos y considerado por algunos como el mejor lenguaje concurrente. Es muy probable que en tu vida profesional debas programar en un lenguaje que use canales. Al final del capítulo se muestran ejemplos sencillos pero que son claves de computación en paralelo y distribuida con canales. El capítulo es fácil de leer, con todos sus ejemplos en Go (interesante también para los que quieran aprender Go o los patrones básicos de concurrencia con canales).
10. Memoria transaccional
Estuve a punto de no escribir este capítulo, iba a ser solo una sección en el epílogo. Cuando acabé los demás y me informé de los avances en los últimos dos años me di cuenta que el libro habría quedado incompleto sin una buena explicación de memoria transaccional. Todo parece indicar que será el mecanismo más conveniente para aplicaciones concurrentes, gracias al soporte de los nuevos procesadores y el esfuerzo de los desarrolladores de librerías y compiladores. Creo que este capítulo quedó muy redondo, introduce el tema desde cero pero explica hasta los detalles de implementación por hardware y las mejores prácticas y patrones de programación.

Un último apunte. Estructuré los capítulos de la forma en que me pareció más lógica y en nivel de abstracción creciente, pero no significa que debas leerlo en ese orden. Si tienes nula experiencia en concurrencia, o en hardware, podrías dejar para el final la lectura de 3. La realidad del hardware moderno, 4. Soluciones por hardware, 5. Spinlocks avanzados y 7. FUTEX (en este orden). Cada capítulo es de complejidad también creciente, no te sientas mal si hay partes que debes releer o dejar para más adelante. Hay temas que son muy complejos, también me costó aprenderlos y todavía más explicarlos en un texto relativamente breve para todo lo que abarca.

De todas formas, aprender requiere esfuerzo personal e intelectual proporcional a la complejidad de lo estudiado. Si requiere poco esfuerzo no es conocimiento, es entretenimiento. O charlatanería.

Fe de erratas

Este libro está autoeditado y no fue revisado por editores ni correctores profesionales. Aunque revisé meticulosamente varias veces cada capítulo, publiqué los manuscritos en mi blog y antes de publicarse pasó por la revisión de varias personas, seguro que tiene errores. Pido disculpas por adelantado y me comprometo a actualizarlo con las correcciones en todas las plataformas en las que lo haya publicado.

Si tenéis consultas o encontráis errores, mi apodo es gallir en casi todas las redes sociales.

Licencia

Creo que el conocimiento debe estar accesible a todos y que es un honor tener lectores interesados en tu obra, independientemente de cómo la obtuvieron. Por eso este libro se distribuye sin DRM y tiene una licencia Creative Commons que te autoriza a dar copias a novios, amigos, compañeros, y cuñados. Las únicas condiciones son que no lo hagas con fines comerciales y no plagies ni modifiques el contenido.

Aunque puedes copiarlo gratuitamente, este libro me costó mucho esfuerzo, tiempo y algo de dinero. No sé por qué, pero se me ocurrió ahora mismo que debo recordarte que se vende a un precio ridículamente bajo y si lo compras online te resultará más cómodo que copiar ficheros desde el ordenador al lector o tablet.

[1] Como las notas son algo menos formales he de ser honesto: nunca vi un libro electrónico con tanto código tan legible como este.

[2] Los datos crudos están en Github.

[3] Algunos consideramos que es clave en la formación, forma parte de los principios fundamentales de la informática.

[4] Otros modelos de más alto nivel, como actores o agentes asíncronos son similares y/o derivados de CSP.