Lectura 17: Concurrencia

#### Software en 6.005

#### Objetivos + Paso de mensajes & memoria compartida + Procesos & hilos+ División de tiempo + Condiciones de carrera # # Concurrencia * Concurrencia * significa que se están realizando varios cálculos al mismo tiempo. La concurrencia está en todas partes en la programación moderna, nos guste o no:+ Múltiples computadoras en una red+ Múltiples aplicaciones que se ejecutan en un equipo+ Múltiples procesadores en un equipo (hoy en día, a menudo, múltiples núcleos de procesador en un solo chip) De hecho, la concurrencia es esencial en la programación moderna:+ Los sitios web deben manejar múltiples usuarios simultáneos.+ Las aplicaciones móviles deben realizar parte de su procesamiento en servidores (“en la nube”).+ Las interfaces gráficas de usuario casi siempre requieren trabajo en segundo plano que no interrumpa al usuario. Por ejemplo, Eclipse compila tu código Java mientras aún lo estás editando.Ser capaz de programar con concurrencia seguirá siendo importante en el futuro. Las velocidades de reloj del procesador ya no aumentan. En cambio, estamos obteniendo más núcleos con cada nueva generación de chips. Así que en el futuro, para que un cálculo funcione más rápido, tendremos que dividir un cálculo en piezas simultáneas.## Dos Modelos para Programación concurrentehay dos modelos comunes para programación concurrente: *memoria compartida* y *paso de mensajes*.

**memoria Compartida.** En el modelo de memoria compartida de concurrencia, los módulos simultáneos interactúan leyendo y escribiendo objetos compartidos en memoria. Otros ejemplos del modelo de memoria compartida: + A y B pueden ser dos procesadores (o núcleos de procesador) en el mismo equipo, que comparten la misma memoria física.+ A y B pueden ser dos programas que se ejecutan en el mismo equipo, compartiendo un sistema de archivos común con archivos que pueden leer y escribir.+ A y B pueden ser dos subprocesos en el mismo programa Java (explicaremos qué es un subproceso a continuación), que comparten los mismos objetos Java.

* * Paso de mensajes.** En el modelo de paso de mensajes, los módulos simultáneos interactúan enviándose mensajes entre sí a través de un canal de comunicación. Los módulos envían mensajes, y los mensajes entrantes a cada módulo se ponen en cola para su manejo. Los ejemplos incluyen:+ A y B pueden ser dos computadoras en una red, que se comunican por conexiones de red.+ A y B pueden ser un navegador web y un servidor web opens A abre una conexión a B, pide una página web y B envía los datos de la página web a A.+ A y B pueden ser un cliente y servidor de mensajería instantánea.+ A y B pueden ser dos programas que se ejecutan en el mismo equipo cuya entrada y salida se han conectado por una tubería, como `ls | grep` escrito en un símbolo del sistema.## Procesos, Subprocesos, Corte de tiempo Los modelos de paso de mensajes y memoria compartida tratan sobre cómo se comunican los módulos simultáneos. Los módulos simultáneos vienen en dos tipos diferentes: procesos y subprocesos.**Proceso**. Un proceso es una instancia de un programa en ejecución que está *aislado* de otros procesos en la misma máquina. En particular, tiene su propia sección privada de la memoria de la máquina.La abstracción del proceso es una * computadora virtual*. Hace que el programa se sienta como si tuviera toda la máquina para sí mismo, como si se hubiera creado una computadora nueva, con memoria nueva, solo para ejecutar ese programa.Al igual que las computadoras conectadas a través de una red, los procesos normalmente no comparten memoria entre ellos. Un proceso no puede acceder a la memoria u objetos de otro proceso en absoluto. Compartir memoria entre procesos es * posible * en la mayoría de los sistemas operativos, pero necesita un esfuerzo especial. Por el contrario, un nuevo proceso está listo automáticamente para el paso de mensajes, ya que se crea con flujos de salida de entrada estándar &, que son el Sistema.fuera `y ‘System.in’ streams que has usado en Java.**Hilo**. Un hilo es un locus de control dentro de un programa en ejecución. Piense en ello como un lugar en el programa que se está ejecutando, además de la pila de llamadas a métodos que llevaron a ese lugar al que será necesario volver.Al igual que un proceso representa un ordenador virtual, la abstracción de subprocesos representa un *procesador virtual*. Hacer un subproceso nuevo simula hacer un procesador nuevo dentro de la computadora virtual representada por el proceso. Este nuevo procesador virtual ejecuta el mismo programa y comparte la misma memoria que otros subprocesos en proceso.Los subprocesos están listos automáticamente para la memoria compartida, porque los subprocesos comparten toda la memoria en el proceso. Necesita un esfuerzo especial para obtener memoria “local de hilo” que sea privada para un solo hilo. También es necesario configurar el paso de mensajes de forma explícita, mediante la creación y el uso de estructuras de datos de cola. Hablaremos sobre cómo hacerlo en una lectura futura.

¿Cómo puedo tener muchos subprocesos simultáneos con solo uno o dos procesadores en mi computadora? Cuando hay más subprocesos que procesadores, la concurrencia se simula mediante **corte de tiempo**, lo que significa que el procesador cambia entre subprocesos. La figura de la derecha muestra cómo tres hilos T1, T2 y T3 pueden estar cortados en el tiempo en una máquina que solo tiene dos procesadores reales. En la figura, el tiempo avanza hacia abajo, por lo que al principio un procesador está ejecutando el hilo T1 y el otro está ejecutando el hilo T2, y luego el segundo procesador cambia a ejecutar el hilo T3. El hilo T2 simplemente se detiene, hasta su siguiente corte de tiempo en el mismo procesador u otro procesador.En la mayoría de los sistemas, el corte de tiempo ocurre de manera impredecible y no determinista, lo que significa que un hilo se puede pausar o reanudar en cualquier momento.

mitx:c613ec53e92840a4a506f3062c994673 Processes & Threads # # Memoria compartida Examplelet’s mira un ejemplo de un sistema de memoria compartida. El objetivo de este ejemplo es mostrar que la programación simultánea es difícil, porque puede tener errores sutiles.

Imagine que un banco tiene cajeros automáticos que utilizan un modelo de memoria compartida, por lo que todos los cajeros automáticos pueden leer y escribir los mismos objetos de cuenta en memoria.Para ilustrar lo que puede salir mal, simplifiquemos el banco a una sola cuenta, con un saldo en dólares almacenado en la variable `saldo`, y dos operaciones de`depósito ” y “retiro” que simplemente agregan o eliminan un dólar: “`java// supongamos que todos los cajeros comparten una sola cuenta bancariaprivado estático int balance = 0;depósito vacío estático privado() { saldo = saldo + 1;}retiro vacío estático privado() { saldo = saldo – 1;} “` Los clientes usan los cajeros para realizar transacciones como esta: “`javadeposit(); // un dólar inwithdraw(); // take it back out` ‘ En este sencillo ejemplo, cada transacción es solo un depósito de un dólar seguido de un retiro de un dólar, por lo que debe dejar el saldo en la cuenta sin cambios. A lo largo del día, cada cajero automático de nuestra red procesa una secuencia de transacciones de depósito/retiro.”‘java / / cada cajero automático realiza un montón de transacciones que / / modifican el saldo, pero lo dejan sin cambios después cashMachine() { for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit (); / / pone un dólar en withdraw(); // take it back out }} “‘ Así que al final del día, independientemente de cuántos cajeros automáticos se estuvieran ejecutando o cuántas transacciones procesáramos, deberíamos esperar que el saldo de la cuenta siga siendo 0.Pero si ejecutamos este código, descubrimos con frecuencia que el saldo al final del día es* no * 0. Si más de una llamada `cashMachine () `se está ejecutando al mismo tiempo, por ejemplo, en procesadores separados en el mismo equipo, entonces` balance ‘ puede no ser cero al final del día. ¿Por qué no?# Hay una cosa que puede pasar. Supongamos que dos cajeros automáticos, A y B, están trabajando en un depósito al mismo tiempo. Así es como el paso deposit() normalmente se divide en instrucciones de procesador de bajo nivel` “‘ obtener saldo (saldo=0)agregar 1 escribir el resultado (saldo=1)“Cuando A y B se ejecutan simultáneamente, estas instrucciones de bajo nivel se entrelazan entre sí (algunas incluso podrían ser simultáneas en algún sentido, pero preocupémonos por el entrelazado por ahora):”‘A obtener balance(balance = 0) A agregar 1 A escribir el resultado (balance=1) B obtener balance (balance=1) B agregar 1 B escribir el resultado (balance=2)“Este entrelazado está bien end terminamos con balance 2, por lo que tanto A como B pusieron un dólar con éxito. Pero qué pasaría si el entrelazado se viera así:“A obtener equilibrio (saldo=0) B obtener equilibrio (saldo=0)A agregar 1 B agregar 1 A escribir el resultado (saldo=1) B escribir el resultado (saldo=1)“El saldo ahora es 1 dollar ¡El dólar de A se perdió! A y B leen el saldo al mismo tiempo, calculan los saldos finales separados y luego se apresuran a almacenar el nuevo saldo, que no tiene en cuenta el depósito del otro.## Condiciones de carrera Este es un ejemplo de una * * condición de carrera**. Una condición de carrera significa que la corrección del programa (la satisfacción de postcondiciones e invariantes) depende del tiempo relativo de los eventos en los cálculos concurrentes A y B. Cuando esto sucede, decimos “A está en una carrera con B.”Algunos entrelazamientos de eventos pueden estar bien, en el sentido de que son consistentes con lo que produciría un solo proceso no concurrente, pero otros entrelazamientos producen respuestas incorrectas, violando postcondiciones o invariantes.## Ajustar el Código No ayudará a que todas estas versiones del código de la cuenta bancaria exhiban la misma condición de carrera: “‘java / / versión 1 depósito de vacío estático privado () {saldo = saldo + 1;} retiro de vacío estático privado () {saldo = saldo-1;} “”” java / / versión 2 depósito de vacío estático privado () {saldo + = 1;} retiro de vacío estático privado () {saldo -= 1;} “””java / / versión 3private static void deposit () {++balance;} private static void withdraw () {balance balance;}“No se puede decir con solo mirar el código Java cómo se va a ejecutar el procesador. No se sabe lo que serán las operaciones indivisibles, las operaciones atómicas. No es atómico solo porque es una línea de Java. No toca la balanza solo una vez, solo porque el identificador de la balanza aparece solo una vez en la línea. El compilador Java, y de hecho el propio procesador, no se compromete a qué operaciones de bajo nivel generará a partir de su código. De hecho, un compilador Java moderno típico produce exactamente el mismo código para las tres versiones.La lección clave es que no se puede decir al mirar una expresión si estará a salvo de las condiciones de carrera.

## Reordenarlo es incluso peor que eso, de hecho. La condición de carrera en el saldo de la cuenta bancaria se puede explicar en términos de diferentes divisiones de operaciones secuenciales en diferentes procesadores. Pero de hecho, cuando usas múltiples variables y múltiples procesadores, ni siquiera puedes contar con que los cambios en esas variables aparezcan en el mismo orden.Este es un ejemplo` “‘ javaprivate boolean ready = false; private int answer = 0; / / computeAnswer se ejecuta en un threadprivate void computeAnswer () {answer = 42; ready = true;} / / useAnswer se ejecuta en un threadprivate void useAnswer () {while (!listo) { Thread.yield ();} if (answer = = 0) lanza una nueva excepción de tiempo de ejecución (“¡la respuesta no estaba lista!`);} “`Tenemos dos métodos que se ejecutan en subprocesos diferentes. ‘computeAnswer’ hace un cálculo largo, finalmente se le ocurre la respuesta 42, que coloca en la variable de respuesta. Luego establece la variable` ready ‘ en true, para indicar al método que se ejecuta en el otro hilo, `useAnswer`, que la respuesta está lista para que la use. Mirando el código ` ‘respuesta’ se establece antes de listo, así que una vez que` useAnswer `ve` listo `como verdadero, entonces parece razonable que pueda asumir que la` respuesta ‘ será 42, ¿verdad? No es así.El problema es que los compiladores y procesadores modernos hacen muchas cosas para que el código sea rápido. Una de esas cosas es hacer copias temporales de variables como answer y ready en un almacenamiento más rápido (registros o cachés en un procesador), y trabajar con ellas temporalmente antes de almacenarlas en su ubicación oficial en la memoria. El storeback puede ocurrir en un orden diferente al que se manipularon las variables en el código. Esto es lo que podría estar pasando debajo de las portadas (pero expresado en sintaxis Java para dejarlo claro). El procesador está creando efectivamente dos variables temporales, ‘tmpr’ y ‘tmpa’, para manipular los campos listos y responder:”‘javaprivate void computeAnswer () {boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; // <? ¿qué sucede si useAnswer () se intercala aquí? // ready está configurado, pero la respuesta no. answer = tmpa;} “‘ mitx:2bf4beb7ffd5437bbbb9c782bb99b54e Condiciones de carrera## Ejemplo de paso de mensajes

Ahora veamos el enfoque de paso de mensajes de nuestro ejemplo de cuenta bancaria.Ahora no solo los módulos de cajeros automáticos, sino que las cuentas también son módulos. Los módulos interactúan enviándose mensajes entre sí. Las solicitudes entrantes se colocan en una cola para ser manejadas de una en una. El remitente no deja de trabajar mientras espera una respuesta a su solicitud. Maneja más solicitudes de su propia cola. La respuesta a su solicitud eventualmente regresa como otro mensaje.Desafortunadamente, el paso de mensajes no elimina la posibilidad de condiciones de carrera. Supongamos que cada cuenta admite operaciones de “obtener saldo” y “retirar”, con los mensajes correspondientes. Dos usuarios, en el cajero automático A y B, están tratando de retirar un dólar de la misma cuenta. Primero revisan el saldo para asegurarse de que nunca retiren más de lo que la cuenta tiene, porque los sobregiros desencadenan grandes penalizaciones bancarias:“obtener saldo si el saldo es >= 1 y luego retirar 1 “‘ El problema es nuevamente el entrelazamiento, pero esta vez el entrelazamiento de los *mensajes* enviados a la cuenta bancaria, en lugar de las *instrucciones* ejecutadas por A y B. Si la cuenta comienza con un dólar en ella, ¿qué entrelazamiento de mensajes engañará a A y B para que piensen que ambos pueden retirar un dólar, por lo tanto, el sobregiro de la cuenta?Una lección aquí es que debe elegir cuidadosamente las operaciones de un modelo de paso de mensajes. “retirar fondos si son suficientes” sería una mejor operación que simplemente “retirar”.## La concurrencia es difícil de probar y depurar Si no le hemos persuadido de que la concurrencia es complicada, aquí está lo peor. Es muy difícil descubrir las condiciones de carrera con pruebas. E incluso una vez que una prueba ha encontrado un error, puede ser muy difícil localizarlo en la parte del programa que lo causa.Los errores de concurrencia exhiben una reproducibilidad muy pobre. Es difícil hacer que sucedan de la misma manera dos veces. La intercalación de instrucciones o mensajes depende del momento relativo de los eventos que están fuertemente influenciados por el entorno. Los retrasos pueden ser causados por otros programas en ejecución, otro tráfico de red, decisiones de programación del sistema operativo, variaciones en la velocidad del reloj del procesador, etc. Cada vez que ejecuta un programa que contiene una condición de carrera, puede obtener un comportamiento diferente. Este tipo de errores son * * heisenbugs**, que no son deterministas y difíciles de reproducir, a diferencia de un “bohrbug”, que aparece repetidamente cada vez que lo miras. Casi todos los errores en la programación secuencial son bohrbugs.Un heisenbug puede incluso desaparecer cuando intenta mirar con `println` o `depurador`! La razón es que la impresión y la depuración son mucho más lentas que otras operaciones, a menudo entre 100 y 1000 veces más lentas, que cambian drásticamente el tiempo de las operaciones y el entrelazado. Así que insertando una simple declaración de impresión en la cashMachine (): “‘ javaprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {deposit (); / / poner un dólar en retirar (); / / sacarlo de nuevo del sistema.fuera.println (balance); // hace que el error desaparezca! }}“`…y de repente, el saldo es siempre 0, según se desee, y el error parece desaparecer. Pero solo está enmascarado, no realmente arreglado. Un cambio en el tiempo en otro lugar del programa puede hacer que el error regrese repentinamente.La concurrencia es difícil de conseguir. Parte del objetivo de esta lectura es asustarte un poco. En las siguientes lecturas, veremos formas basadas en principios de diseñar programas simultáneos para que estén más seguros de este tipo de errores.mitx: 704b9c4db3c6487c9f1549956af8bfc8 Pruebas de concurrencia # # Resumen + Concurrencia: múltiples cálculos que se ejecutan simultáneamente + Memoria compartida & paradigmas de paso de mensajes + Procesos & hilos + Proceso es como una computadora virtual; hilo es como un procesador virtual + Condiciones de carrera + Cuando la corrección del resultado (postcondiciones e invariantes) depende del tiempo relativo de los eventos.Estas ideas se conectan a nuestras tres propiedades clave de un buen software, principalmente de malas maneras. La concurrencia es necesaria, pero causa serios problemas de corrección. Trabajaremos en arreglar esos problemas en las próximas lecturas.+ * * A salvo de insectos.** Los errores de concurrencia son algunos de los errores más difíciles de encontrar y corregir, y requieren un diseño cuidadoso para evitarlos.+ **Fácil de entender.** Predecir cómo el código concurrente podría intercalarse con otro código concurrente es muy difícil de hacer para los programadores. Es mejor diseñar de tal manera que los programadores no tengan que pensar en eso. + **Listo para el cambio.** No es particularmente relevante aquí.