Principios y algoritmos de concurrencia: Monitores

Etiquetas

, ,

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

MONITORES

Los monitores evolucionaron a partir de ideas y discusiones entre Dijkstra, Per Brinch-Hansen, Ole-Johan Dahl y C.A.R. Hoare ([Brinch]) como una forma de estructurar a los sistemas operativos usando lenguajes de alto nivel[97]. En 1973 fueron formalizados por Hoare ([Hoare1]) en su notación más conocida. La idea consistía en que el sistema operativo es un conjunto de módulos, schedulers, que asignan recursos compartidos para diversos procesos. Llamaron monitor al conjunto de procedimientos y datos que debía gestionar cada scheduler.

Para evitar los problemas derivados de los accesos concurrentes cada monitor debe asegurar la exclusión mutua de la ejecución de sus procedimientos y sus variables solo debían poder ser accedidos o modificados por estos procedimientos. Brinch Hansen diseñó y desarrolló Concurrent Pascal basado en Pascal y con ideas de Modula67, fue el primer lenguaje concurrente y sirvió para el desarrollo de varios sistemas operativos experimentales y sus ideas se implementaron en otros lenguajes, Modula, Concurrent C, Mesa, ADA…​ y hasta en Java. Este último incluye monitores como construcción nativa del lenguaje como una combinación de métodos y bloques synchronized con las funciones de sincronización wait, notify y notifyAll.

Sigue leyendo

Principios y algoritmos de concurrencia: FUTEX

Etiquetas

,

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

FUTEX

Los mecanismos de sincronización sin espera activa son habitualmente implementados en los sistemas operativos, estos tienen mayor facilidad y capacidad para cambiar el estado de los procesos. Pero las llamadas de sistemas toman un tiempo considerable debido a la interrupción de software y posterior cambio de contexto a ejecución del núcleo. Se puede mejorar el rendimiento si se reducen las llamadas solo a los casos donde hay competencia. Si un proceso es el único que desea entrar a la sección crítica puede en el espacio de usuario, con las instrucciones atómicas que vimos en el capítulo de Soluciones por hardware, sin necesidad de invocar al núcleo.

Sigue leyendo

Principios y algoritmos de concurrencia: Semáforos

Etiquetas

, , , ,

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

(El capítulo FUTEX antes era una sección de éste, como quedaba muy extensa y tenía estructura propia y casi independiente la separé a otro capítulo, ya está casi acabado y lo publicaré en cuanto pueda).

SEMÁFOROS

El concepto de semáforos lo inventó Edsger W. Dijkstra a finales de los años 60 ([Dijkstra74]) -aunque las primeras ideas aparecieron a principios de la misma década ([Dijkstra35])-, fue el primero en solucionar los problemas de sincronización sin espera activa. Está inspirado de las señales visuales ferroviarias[76] que indican si un tren está habilitado para entrar en una vía. Es una construcción sencilla, eficiente y muy utilizada que permite solucionar problemas genéricos de sincronización entre procesos sin esperas activas.

Sigue leyendo

Miles de apps en los móviles: mitos, realidades y las preguntas claves

Etiquetas

, ,

Ayer hice una búsqueda y el primer resultado que me salió fue una página de Linkedin, al ir a ella un aviso en pantalla completa para que instale su app. ¡Cielos! yo sólo quería saber una información muy concreta y que no necesitaba más de unos pocos segundos de lectura. Además esa misma información está disponible en miles de sitios, que haya entrado a Linkedin fue puro accidente. Tengo cuenta en Linkedin desde hace años pero no la uso habitualmente ni tengo la intención de hacerlo: no soy un buscatalentos, no busco ni ofrezco trabajo habitualmente. No tengo intenciones ni ganas de instalar su app en mi teléfono, pero ¿por qué insisten?

Los mitos de las apps

No es nada nuevo ni soy original en lo que voy a comentar. Sin embargo me sigue sorprendiendo la molesta insistencia de muchos sitios web a que sus lectores esporádicos o accidentales instalen una nueva app en su móvil. Los que diseñan o deciden estas estrategias parecen asumir los varios de los siguientes supuestos falsos:

Sigue leyendo

Principios de concurrencia: Spinlocks

Etiquetas

, , , , ,

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

SPINLOCKS

Las soluciones de exclusión mutua anteriores tienen en común una espera activa que continuamente verifica el estado de una variable o registro RMW hasta que el proceso puede entrar a la sección crítica. Estos algoritmos se denominan spinlocks, el de Dekker, Peterson, la panadería o cualquiera de las soluciones de exclusión mutua del capítulo anterior son también spinlocks. Su uso tiene sentido si se cumple una de las siguientes condiciones:

Sigue leyendo

Principios de concurrencia: Soluciones por hardware

Etiquetas

, , , ,

Este artículo es el primer manuscrito del capítulo Soluciones por hardware del libro que estoy escribiendo Principios de concurrencia para programadores. Todo el código de los ejemplos están en Github.

Soluciones por hardware

Hasta ahora hemos visto soluciones al problema de la exclusión mutua sin soporte de hardware y con solo registros de lectura-escritura atómicos, todos ellos son spinlocks pero muy ineficientes. Por un lado por el consumo de memoria, tanto para la solución de dos procesos (Dekker y Peterson) como para N procesos (Panadería) el número de registros necesarios es proporcional al número de procesos máximos que sincronizarán[31]. Esta necesidad de memoria impone una sobrecarga importante para mantener la consistencia de la memoria caché, además del consumo de CPU por la espera activa todos los procesos involucrados tienen que acceder al mismo rango de memoria que los demás. Es una penalización muy importante para sistemas con varios procesadores o núcleos. Por otro lado, si se tiene un único procesador el avance es tan lento que lo que tarda décimas en uno puede tomar horas en otros[32] en el caso de que exista mucha competencia (contention) porque varios procesos desean entrar a la sección crítica de forma casi simultánea.

Desde el inicio se buscaron soluciones por hardware que permitiesen implementar algoritmos de sincronización de forma mucho más eficiente.

Sigue leyendo

Nota rápida sobre el “no hackeo” del cifrado de Telegram

Etiquetas

, ,

Antes que nada, no tengo ni la mínima intención de defender a Telegram, tampoco sé si sus métodos de cifrado son los mejores o no. Se trata simplemente te aclarar unos temas básicos de cifrado para el “drama” que están montando (por ejemplo) a partir del artículo original How I Hacked Telegram’s “Encryption”. (también erróneo por sensacionalista y poor ignorar de dónde está el problema, pero vaya, es cuestión de negocios, supongo).

Sigue leyendo

PIB, gasto y aumento de la deuda

Etiquetas

, , ,

El Producto Interno Bruto son mediciones estadísticas de la actividad económica de los habitantes e instituciones de un país. No hay que olvidar que es un “invento” con diferentes modos de medirlo (producción, ingresos y gastos), que la medición no puede ser perfecta (no se pude medir todo, se usan aproximaciones estadísticas), que con los cambios sociales de las últimas décadas se dejan muchos aspectos sin medir (por ejemplo no se mide el valor que aporta todo el trabajo detrás de la Wikipedia y los beneficios que genera) y tiene sus limitaciones. Aún así es una de las mejoras formas conocidas de medir la “riqueza” o actividad económica de un país que sirve analizar su evolución comparando el resultado de un período a otro. Si los datos se obtienen siempre de la misma forma dan información muy valiosa, casi imprescindible (hasta los presupuestos generales se hacen basados en estimaciones del PIB para el año correspondiente).

Sigue leyendo

Principios de concurrencia: exclusión mutua y algoritmos

Etiquetas

, , , ,

Este artículo incluye dos capítulos, Exclusión mutua y Algoritmos de exclusión mutuadel libro que estoy escribiendo: Principios de concurrencia.

Recordad que:

  • Es un manuscrito, por lo que no ha pasado todavía por el proceso de corrección (que espero contratar o pedir ayuda a un corrector profesional, además de a otros amigos informáticos).
  • Aunque intentaré eliminar todos pueden quedar algunos enlaces relativos que apuntan a otros capítulos del libro y que obviamente no funcionarán.
  • El código fuente de los ejemplos están en Github.
  • Publico estos capítulos parciales porque es una forma de ponerme objetivos más cercanos, de publicar el texto y además de detectar errores o qué temas hay que explicar mejor. Tampoco viene mal un poco de publicidad del futuro libro (que publicaré en Amazon y Google Books).
  • Por si tenéis curiosidad, al libro lo estoy escribiendo para asciidoc/asciidoctor. Para ponerlo aquí genero el HTML con asciidoctor y hago el copipaste sobre el editor de WordPress, como es de esperar, se pierden formato e imágenes, pero eliminé la generación de iconos más guapos para minimizar este problema y que sea legible (en el ebook va con ellos).

EXCLUSIÓN MUTUA

La exclusión mutua es un problema básico y fundamental de sincronización entre procesos[1] con memoria compartida, se trata de asegurar que el acceso a recursos compartidos entre ellos se haga de forma ordenada para asegurar que los valores o estados de esos recursos sean consistentes. Un problema de exclusión mutua muy genérico y naïve pero que ilustra perfectamente el problema: si varios procesos en un ordenador[2] envían diferentes trabajos de impresión se debe asegurar que las páginas no se intercalen, es decir, asegurar la exclusión mutua en el acceso a la impresora.

Sigue leyendo

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 585 seguidores