¿Cómo podría proporcionar seguridad de subprocesos un lenguaje de programación similar a la forma en que Java y C # proporcionan seguridad de memoria?

10

Java y C # proporcionan seguridad de memoria al verificar los límites de la matriz y las desreferencias de puntero.

¿Qué mecanismos podrían implementarse en un lenguaje de programación para evitar la posibilidad de condiciones de carrera y puntos muertos?

mrpyo
fuente
3
Quizás te interese lo que hace Rust: Concurrencia sin miedo con Rust
Vincent Savard
2
Haga que todo sea inmutable, o haga que todo se sincronice con canales seguros. También te puede interesar Go y Erlang .
Theraot
@Theraot "haga todo asíncrono con canales seguros" - desearía poder explicarlo más.
mrpyo
2
@mrpyo no expondría procesos o subprocesos, cada llamada es una promesa, todo se ejecuta simultáneamente (con el tiempo de ejecución programando su ejecución y creando / agrupando subprocesos del sistema detrás de escena según sea necesario), y la lógica que protege el estado está en los mecanismos que transmite información ... el tiempo de ejecución puede serializarse automáticamente mediante la programación, y habría una biblioteca estándar con una solución segura para subprocesos para comportamientos más sutiles, en particular se necesitan productores / consumidores y agregaciones.
Theraot el
2
Por cierto, hay otro enfoque posible: memoria transaccional .
Theraot el

Respuestas:

14

Las carreras ocurren cuando tienes un alias simultáneo de un objeto y, al menos, uno de los alias está mutando.

Por lo tanto, para evitar carreras, debe hacer que una o más de estas condiciones no sean ciertas.

Diversos enfoques abordan diversos aspectos. La programación funcional enfatiza la inmutabilidad que elimina la mutabilidad. El bloqueo / atómica elimina la simultaneidad. Los tipos afines eliminan el alias (Rust elimina el alias mutable). Los modelos de actor generalmente eliminan los alias.

Puede restringir los objetos que pueden tener alias para que sea más fácil asegurarse de evitar las condiciones anteriores. Ahí es donde entran los canales y / o los estilos de paso de mensajes. No se puede alias la memoria arbitraria, solo el final de un canal o cola que está dispuesta para estar libre de carreras. Por lo general, evitando la simultaneidad, es decir, bloqueos o atómicos.

La desventaja de estos diversos mecanismos es que restringen los programas que puede escribir. Cuanto más contundente es la restricción, menos son los programas. Por lo tanto, no funcionan los alias ni la mutabilidad, y son fáciles de razonar, pero son muy limitantes.

Es por eso que Rust está causando tanto revuelo. Es un lenguaje de ingeniería (en comparación con el académico) que admite aliasing y mutabilidad, pero hace que el compilador verifique que no ocurran simultáneamente. Aunque no es lo ideal, permite que una clase más grande de programas se escriba de forma segura que muchos de sus predecesores.

Alex
fuente
11

Java y C # proporcionan seguridad de memoria al verificar los límites de la matriz y las desreferencias de puntero.

Es importante pensar primero en cómo C # y Java hacen esto. Lo hacen al convertir lo que es un comportamiento indefinido en C o C ++ en un comportamiento definido: bloquear el programa . Las desreferencias nulas y las excepciones de índice de matriz nunca deben detectarse en un programa Java o C # correcto; no deberían suceder en primer lugar porque el programa no debería tener ese error.

¡Pero eso es lo que creo que no quieres decir con tu pregunta! Podríamos escribir fácilmente un tiempo de ejecución de "punto muerto seguro" que verifica periódicamente para ver si hay n hilos que se esperan mutuamente y finalizar el programa si eso sucede, pero no creo que eso lo satisfaga.

¿Qué mecanismos podrían implementarse en un lenguaje de programación para evitar la posibilidad de condiciones de carrera y puntos muertos?

El siguiente problema que enfrentamos con su pregunta es que las "condiciones de carrera", a diferencia de los puntos muertos, son difíciles de detectar. Recuerde, lo que buscamos en seguridad de hilos no es eliminar carreras . ¡Lo que buscamos es corregir el programa sin importar quién gane la carrera ! El problema con las condiciones de carrera no es que dos hilos estén funcionando en un orden indefinido y no sabemos quién va a terminar primero. El problema con las condiciones de carrera es que los desarrolladores olvidan que algunas órdenes de acabado de hilos son posibles y no tienen en cuenta esa posibilidad.

Entonces, su pregunta básicamente se reduce a "¿hay alguna forma en que un lenguaje de programación pueda garantizar que mi programa sea correcto?" y la respuesta a esa pregunta es, en la práctica, no.

Hasta ahora solo he criticado tu pregunta. Permítanme intentar cambiar de marcha aquí y abordar el espíritu de su pregunta. ¿Hay opciones que los diseñadores de idiomas podrían hacer que mitigarían la horrible situación en la que estamos con los subprocesos múltiples?

¡La situación es realmente horrible! Obtener el código multiproceso correcto, particularmente en arquitecturas de modelo de memoria débil, es muy, muy difícil. Es instructivo pensar por qué es difícil:

  • Múltiples hilos de control en un proceso son difíciles de razonar. ¡Un hilo es lo suficientemente difícil!
  • Las abstracciones se vuelven extremadamente permeables en un mundo multiproceso. En el mundo de un solo subproceso, tenemos la garantía de que los programas se comportan como si se ejecutaran en orden, incluso si no se ejecutan en orden. En el mundo multiproceso, ese ya no es el caso; las optimizaciones que serían invisibles en un solo hilo se hacen visibles, y ahora el desarrollador necesita comprender esas posibles optimizaciones.
  • Pero se pone peor. La especificación C # dice que NO se requiere una implementación para tener un orden consistente de lecturas y escrituras que todos los hilos puedan acordar . La idea de que hay "razas" en absoluto, y de que hay un claro ganador, ¡en realidad no es verdad! Considere una situación en la que hay dos escrituras y dos lecturas de algunas variables en muchos hilos. En un mundo sensible podríamos pensar "bueno, no podemos saber quién va a ganar las carreras, pero al menos habrá una carrera y alguien ganará". No estamos en ese mundo sensible. C # permite que múltiples hilos no estén de acuerdo sobre el orden en que ocurren las lecturas y escrituras; no necesariamente hay un mundo consistente que todos estén observando.

Entonces, hay una forma obvia de que los diseñadores de idiomas pueden mejorar las cosas. Abandone las victorias de rendimiento de los procesadores modernos . Haga que todos los programas, incluso los de subprocesos múltiples, tengan un modelo de memoria extremadamente fuerte. Esto hará que los programas multiproceso sean mucho, muchas veces más lentos, lo que funciona directamente en contra de la razón de tener programas multiproceso en primer lugar: para mejorar el rendimiento.

Incluso dejando de lado el modelo de memoria, hay otras razones por las que el subprocesamiento múltiple es difícil:

  • La prevención de puntos muertos requiere un análisis completo del programa; debe conocer el orden global en el que se pueden quitar los bloqueos y aplicar ese orden en todo el programa, incluso si el programa está compuesto por componentes escritos en diferentes momentos por diferentes organizaciones.
  • La herramienta principal que le damos para domar el subprocesamiento múltiple es el bloqueo, pero los bloqueos no se pueden componer .

Ese último punto lleva más explicaciones. Por "composable" quiero decir lo siguiente:

Supongamos que deseamos calcular un int dado un doble. Escribimos una implementación correcta de la computación:

int F(double x) { correct implementation here }

Supongamos que deseamos calcular una cadena dada un int:

string G(int y) { correct implementation here }

Ahora si queremos calcular una cadena dada un doble:

double d = whatever;
string r = G(F(d));

G y F pueden componerse en una solución correcta para el problema más complejo.

Pero las cerraduras no tienen esta propiedad debido a los puntos muertos. Un método correcto M1 que toma bloqueos en el orden L1, L2, y un método correcto M2 que toma bloqueos en el orden L2, L1, no pueden usarse en el mismo programa sin crear un programa incorrecto. Los bloqueos hacen que no se pueda decir "cada método individual es correcto, por lo que todo es correcto".

Entonces, ¿qué podemos hacer, como diseñadores de idiomas?

Primero, no vayas allí. Múltiples hilos de control en un programa es una mala idea, y compartir memoria entre hilos es una mala idea, así que no lo pongas en el lenguaje o tiempo de ejecución en primer lugar.

Esto aparentemente no es un iniciador.

Volvamos nuestra atención a la pregunta más fundamental: ¿por qué tenemos múltiples hilos en primer lugar? Hay dos razones principales, y se combinan en la misma cosa con frecuencia, aunque son muy diferentes. Están combinados porque ambos tratan sobre la gestión de la latencia.

  • Creamos hilos, erróneamente, para gestionar la latencia de E / S. Necesita escribir un archivo grande, acceder a una base de datos remota, lo que sea, crear un subproceso de trabajo en lugar de bloquear su subproceso de interfaz de usuario.

Mala idea. En su lugar, use la asincronía de un solo subproceso a través de las rutinas. C # hace esto maravillosamente. Java, no tan bien. Pero esta es la forma principal en que la actual cosecha de diseñadores de idiomas está ayudando a resolver el problema de la creación de hilos. El awaitoperador en C # (inspirado en los flujos de trabajo asíncronos de F # y otras técnicas anteriores) se está incorporando a más y más lenguajes.

  • Creamos subprocesos, adecuadamente, para saturar las CPU inactivas con un trabajo computacionalmente pesado. Básicamente, estamos usando hilos como procesos ligeros.

Los diseñadores de idiomas pueden ayudar creando características de lenguaje que funcionen bien con paralelismo. Piense en cómo LINQ se extiende tan naturalmente a PLINQ, por ejemplo. Si es una persona sensata y limita sus operaciones TPL a operaciones vinculadas a la CPU que son altamente paralelas y no comparten memoria, puede obtener grandes ganancias aquí.

qué más podemos hacer?

  • Haga que el compilador detecte los errores más descabellados y conviértalos en advertencias o errores.

C # no te permite esperar en un candado, porque esa es una receta para los callejones sin salida. C # no le permite bloquear un tipo de valor porque eso siempre es lo incorrecto; bloqueas la caja, no el valor. C # le advierte si alias un volátil, porque el alias no impone semántica de adquirir / liberar. Hay muchas más formas en que el compilador podría detectar problemas comunes y prevenirlos.

  • Diseñe características de "pozo de calidad", donde la forma más natural de hacerlo es también la forma más correcta.

C # y Java cometieron un gran error de diseño al permitirle usar cualquier objeto de referencia como monitor. Eso fomenta todo tipo de malas prácticas que hacen que sea más difícil rastrear puntos muertos y más difícil evitarlos estáticamente. Y desperdicia bytes en cada encabezado de objeto. Se debe requerir que los monitores se deriven de una clase de monitor.

  • Se invirtió una gran cantidad de tiempo y esfuerzo de Microsoft Research en un intento de agregar memoria transaccional de software a un lenguaje similar a C #, y nunca lograron que funcionara lo suficientemente bien como para incorporarlo al lenguaje principal.

STM es una idea hermosa, y he jugado con implementaciones de juguetes en Haskell; le permite componer soluciones correctas de manera mucho más elegante a partir de piezas correctas que las soluciones basadas en cerraduras. Sin embargo, no sé lo suficiente sobre los detalles para decir por qué no se pudo hacer que funcione a escala; pregúntale a Joe Duffy la próxima vez que lo veas.

  • Otra respuesta ya mencionó la inmutabilidad. Si tiene la inmutabilidad combinada con rutinas eficientes, puede crear características como el modelo de actor directamente en su idioma; piensa en Erlang, por ejemplo.

Se ha investigado mucho sobre lenguajes basados ​​en cálculo de procesos y no entiendo muy bien ese espacio; intente leer algunos documentos sobre usted mismo y vea si tiene alguna idea.

  • Facilite a terceros escribir buenos analizadores

Después de trabajar en Microsoft en Roslyn, trabajé en Coverity, y una de las cosas que hice fue conseguir que el analizador utilizara Roslyn. Al tener un análisis léxico, sintáctico y semántico preciso proporcionado por Microsoft, podríamos concentrarnos en el arduo trabajo de escribir detectores que encontraron problemas comunes de subprocesos múltiples.

  • Elevar el nivel de abstracción

Una razón fundamental por la que tenemos carreras y puntos muertos y todo eso es porque estamos escribiendo programas que dicen qué hacer , y resulta que todos somos basura en escribir programas imperativos; la computadora hace lo que le dices y le decimos que haga las cosas mal. Muchos lenguajes de programación modernos se centran cada vez más en la programación declarativa: diga qué resultados desea y deje que el compilador descubra la forma eficiente, segura y correcta de lograr ese resultado. Nuevamente, piense en LINQ; queremos que digas from c in customers select c.FirstName, lo que expresa una intención . Deje que el compilador descubra cómo escribir el código.

  • Use computadoras para resolver problemas de la computadora.

Los algoritmos de aprendizaje automático son mucho mejores en algunas tareas que los algoritmos codificados a mano, aunque, por supuesto, hay muchas compensaciones que incluyen corrección, tiempo necesario para entrenar, sesgos introducidos por un mal entrenamiento, etc. Pero es probable que una gran cantidad de tareas que actualmente codificamos "a mano" pronto sean susceptibles de soluciones generadas por máquina. Si los humanos no escriben el código, no escriben errores.

Lamento que haya estado divagando un poco allí; Este es un tema enorme y difícil y no ha surgido un consenso claro en la comunidad de PL en los 20 años que llevo siguiendo el progreso en este espacio problemático.

Eric Lippert
fuente
"Entonces, su pregunta básicamente se reduce a" ¿hay alguna forma de que un lenguaje de programación pueda garantizar que mi programa sea correcto? "Y la respuesta a esa pregunta es, en la práctica, no". - en realidad, es bastante posible - se llama verificación formal, y aunque es inconveniente, estoy bastante seguro de que se realiza de manera rutinaria en software crítico, por lo que no lo llamaría poco práctico. Pero que ser un diseñador del lenguaje probablemente sabe esto ...
mrpyo
66
@ mrpyo: estoy muy consciente. Hay muchos problemas. Primero: una vez asistí a una conferencia formal de verificación donde un equipo de investigación de MSFT presentó un nuevo resultado emocionante: pudieron extender su técnica para verificar programas multiproceso de hasta veinte líneas de longitud y ejecutar el verificador en menos de una semana. Esta fue una presentación interesante, pero no me sirvió de nada; Tenía un programa de 20 millones de líneas para analizar.
Eric Lippert el
@mrpyo: Segundo, como mencioné, un gran problema con las cerraduras es que un programa hecho de métodos seguros para subprocesos no es necesariamente un programa seguro para subprocesos. La verificación formal de los métodos individuales no necesariamente ayuda, y el análisis de todo el programa es difícil para los programas no triviales.
Eric Lippert el
66
@mrpyo: Tercero, el gran problema con el análisis formal es que, ¿qué estamos haciendo fundamentalmente? Estamos presentando una especificación de precondiciones y postcondiciones y luego verificamos que el programa cumpla con esa especificación. Excelente; en teoría eso es totalmente factible. ¿En qué idioma está escrita la especificación? Si hay un lenguaje de especificación inequívoco y verificable, entonces escribamos todos nuestros programas en ese idioma y compilemos eso . ¿Por qué no hacemos esto? ¡Porque resulta que también es realmente difícil escribir programas correctos en el lenguaje de especificaciones!
Eric Lippert el
2
Es posible analizar una solicitud de corrección utilizando precondiciones / postcondiciones (por ejemplo, usando Contratos de codificación). Sin embargo, dicho análisis solo es factible con la condición de que las condiciones sean componibles, lo que no son bloqueos. También notaré que escribir un programa de una manera que permita el análisis requiere una disciplina cuidadosa. Por ejemplo, las aplicaciones que no se adhieren estrictamente al Principio de sustitución de Liskov tienden a resistir el análisis.
Brian