Veamos cómo funciona la programación concurrente y paralela en .Net, utilizando el problema de los filósofos como ejemplo. Dicho plan, desde la sincronización de hilos / procesos, hasta el modelo de actores (en las siguientes partes). El artículo puede ser útil para un primer conocido o para actualizar sus conocimientos.
¿Por qué ser capaz de hacer esto? Los transistores alcanzan su tamaño mínimo, la ley de Moore se basa en la limitación de la velocidad de la luz y, por lo tanto, se observa un crecimiento en cantidad, se pueden hacer más transistores. Al mismo tiempo, la cantidad de datos está creciendo y los usuarios esperan una reacción inmediata de los sistemas. En tal situación, la programación "normal", cuando tenemos un hilo en ejecución, ya no es efectiva. Es necesario resolver de alguna manera el problema de la ejecución simultánea o competitiva. Además, este problema existe en diferentes niveles: a nivel de flujos, a nivel de procesos, a nivel de máquinas en la red (sistemas distribuidos). .NET tiene tecnologías probadas y de alta calidad para resolver estos problemas de manera rápida y efectiva.
Desafío
Edsger Dijkstra planteó este problema a sus alumnos ya en 1965. La redacción establecida es esta. Hay un número (generalmente cinco) de filósofos y tantos tenedores. Están sentados en la mesa redonda, con tenedores en el medio. Los filósofos pueden comer de sus platos con comida interminable, pensar o esperar. Para comer al filósofo, debes tomar dos tenedores (el último comparte el tenedor con el primero). Para tomar y poner un tenedor: dos acciones separadas. Todos los filósofos callan. La tarea es encontrar un algoritmo tal que todos piensen y estén hartos incluso después de 54 años.
Primero, intentemos resolver este problema usando el espacio compartido. Los tenedores están sobre la mesa y los filósofos los toman cuando están y los vuelven a poner. Hay problemas con la sincronización, ¿cuándo exactamente tomar los enchufes? ¿Qué hacer si no hay enchufe? y otros. Pero primero, vamos a lanzar a los filósofos.
Para iniciar subprocesos, use el grupo de subprocesos a través del método Task.Run :
var cancelTokenSource = new CancellationTokenSource(); Action<int> create = (i) => RunPhilosopher(i, cancelTokenSource.Token); for (int i = 0; i < philosophersAmount; i++) { int icopy = i;
Grupo de subprocesos creado para optimizar la creación y eliminación de subprocesos. Este grupo tiene una cola de tareas y el CLR crea o elimina subprocesos según el número de estas tareas. Un grupo para todos los dominios de aplicación. Este grupo debe usarse casi siempre, porque no necesita molestarse en crear, eliminar hilos, sus colas, etc. Es posible sin un grupo, pero luego debe usar el Thread directamente, es aconsejable para casos en los que necesita cambiar la prioridad de un hilo, cuando tenemos una operación larga, para el primer plano de un hilo, etc.
Y la clase System.Threading.Tasks.Task simplemente hace que sea fácil trabajar con este grupo de subprocesos (o incluso prescindir de él). Es una operación asincrónica. En términos generales, este es el mismo Thread , pero con todo tipo de comodidades: la capacidad de iniciar tareas después de un bloque de otras tareas, devolverlas de las funciones, es conveniente interrumpirlas y muchas más. etc. Son necesarios para admitir construcciones asíncronas / en espera (patrón asincrónico basado en tareas, azúcar sintáctico para esperar la operación IO). Hablaremos de esto nuevamente.
CancelationTokenSource se necesita aquí para que el hilo en sí mismo pueda ser terminado por la señal del hilo que llama.
Problemas de sincronización
Filósofos bloqueados
Ok, podemos crear hilos, intentemos almorzar:
Aquí intentamos primero tomar las horquillas izquierda y luego la derecha, y si funciona, entonces comemos y volvemos a colocarlas. Tomar un tenedor es atómico, es decir dos transmisiones no pueden tomar una al mismo tiempo (incorrectamente: la primera lee que el enchufe está libre, la segunda también, la primera toma, la segunda toma). Para hacer esto, Interlocked.CompareExchange , que debe implementarse utilizando una instrucción de procesador ( TSL , XCHG ), que bloquea una pieza de memoria para lectura y escritura secuencial atómica. Y SpinWait es equivalente a una construcción while(true) con solo un poco de "magia": el subproceso ocupa el procesador ( Thread.SpinWait ), pero a veces transfiere el control a otro subproceso ( Thread.Yeild ) o se queda dormido ( Thread.Sleep ).
Pero esta solución no funciona, porque los flujos pronto serán bloqueados (para mí en un segundo): todos los filósofos toman su bifurcación izquierda, pero no la correcta. La matriz de horquillas tiene valores: 1 2 3 4 5.
En la figura, hilos de bloqueo (punto muerto). El verde indica ejecución, el rojo indica sincronización y el gris indica suspensión. Los diamantes indican la hora de inicio de la tarea.
El hambre de los filósofos
Aunque no es necesario pensar especialmente en la comida, debes obligar a cualquiera a abandonar la filosofía. Tratemos de simular la situación de los flujos de ayuno en nuestro problema. El hambre es cuando la corriente funciona, pero sin un trabajo significativo, en otras palabras, es el mismo punto muerto, solo que ahora la corriente no duerme, pero está buscando activamente algo para comer, pero no hay comida. Para evitar bloqueos frecuentes, volveremos a enchufar si no pudimos tomar otro.
En este código, es importante que dos de cada cuatro filósofos se olviden de poner el tenedor izquierdo. Y resulta que comen más alimentos, mientras que otros comienzan a morir de hambre, aunque los flujos tienen la misma prioridad. Aquí realmente no mueren de hambre, porque los filósofos malos a veces vuelven a poner los tenedores. Resulta que los buenos comen unas 5 veces menos que los malos. Entonces, un pequeño error en el código conduce a una caída en el rendimiento. Aquí vale la pena señalar que una situación rara es posible cuando todos los filósofos toman la bifurcación izquierda, no hay derecha, ponen la izquierda, esperan, vuelven a girar a la izquierda, etc. Esta situación también es inanición, más como un punto muerto. No pude repetirlo. A continuación se muestra una imagen de una situación en la que dos filósofos malos tomaron ambos tenedores y dos buenos filósofos están muriendo de hambre.
Aquí puede ver que los hilos a veces se despiertan e intentan obtener un recurso. Dos de los cuatro núcleos no hacen nada (el gráfico verde en la parte superior).
La muerte del filósofo
Bueno, otro problema que puede interrumpir la gloriosa cena de los filósofos es si uno de ellos muere repentinamente con tenedores en sus manos (y lo enterrarán así). Luego los vecinos se quedarán sin almuerzo. Puede NullReferenceException código de muestra para este caso usted mismo, por ejemplo, NullReferenceException lanza una NullReferenceException después de que el filósofo toma los tenedores. Y, por cierto, la excepción no se procesará y el código de llamada simplemente no la detectará (para esto, AppDomain.CurrentDomain.UnhandledException , etc.). Por lo tanto, los manejadores de errores son necesarios en los propios subprocesos y con la terminación correcta.
Camarero
Bueno, ¿cómo resolvemos este problema con puntos muertos, hambre y muerte? Permitiremos que solo un filósofo se bifurque, agregue la exclusión mutua de flujos para este lugar. Como hacerlo Supongamos que un mesero se para al lado de los filósofos y da permiso a un filósofo para que tome tenedores. ¿Cómo hacemos a este camarero y cómo los filósofos le hacen preguntas interesantes?
La forma más simple es cuando los filósofos simplemente le piden constantemente al camarero que acceda a los tenedores. Es decir ahora los filósofos no esperarán un enchufe cercano, sino que esperarán o preguntarán a un mesero. Primero, usamos solo Espacio de usuario para esto, en él no usamos interrupciones para llamar a ningún procedimiento desde el núcleo (sobre ellos a continuación).
Soluciones de espacio de usuario
Aquí haremos lo mismo que solíamos hacer con un tenedor y dos filósofos, giraremos en un ciclo y esperaremos. Pero ahora serán todos filósofos y como si solo un tenedor, es decir podemos decir que solo habrá ese filósofo que tomó este "tenedor dorado" del camarero. Para esto usamos SpinLock.
private static SpinLock spinLock = new SpinLock();
SpinLock es un bloqueador, con, en términos generales, el mismo while(true) { if (!lock) break; } while(true) { if (!lock) break; } , pero con aún más "magia" que en SpinWait (que se usa allí). Ahora sabe contar a los que están esperando, ponerlos a dormir un poco y más. etc. En general, hace todo lo posible para optimizar. Pero debemos recordar que este sigue siendo el mismo ciclo activo que consume recursos del procesador y mantiene un hilo que puede conducir al hambre si uno de los filósofos se convierte en una prioridad sobre otros, pero no tiene un tenedor dorado (problema de inversión prioritaria). Por lo tanto, lo usamos solo para cambios muy breves en la memoria compartida, sin sorpresas en llamadas de terceros, bloqueos anidados, etc.
Figura para SpinLock . Las corrientes están constantemente "luchando" por el tenedor dorado. Las fallas ocurren: en la figura, el área seleccionada. Los núcleos no se utilizan por completo: solo alrededor de 2/3 de estos cuatro hilos.
Otra solución aquí sería usar solo Interlocked.CompareExchange con la misma expectativa activa, como se muestra en el código anterior (en filósofos hambrientos), pero esto, como ya se mencionó, podría conducir teóricamente al bloqueo.
Sobre Interlocked vale la pena decir que no solo hay CompareExchange , sino también otros métodos para la lectura y escritura atómica. Y al repetir los cambios en caso de que otro hilo logre hacer sus cambios (leer 1, leer 2, escribir 2, escribir 1 es malo), puede usarse para cambios complejos de un valor (patrón de cualquier cosa entrelazada).
Soluciones en modo kernel
Para evitar perder recursos en un bucle, veamos cómo puede bloquear una transmisión. En otras palabras, continuando con nuestro ejemplo, veremos cómo el camarero duerme al filósofo y lo despierta solo cuando es necesario. Primero, veamos cómo hacer esto a través del modo kernel del sistema operativo. Todas las estructuras allí a menudo resultan ser más lentas que las del espacio de usuario. Varias veces más lento, por ejemplo, AutoResetEvent puede ser 53 veces más lento que SpinLock [Richter]. Pero con su ayuda, puede sincronizar procesos en todo el sistema, gestionados o no.
La construcción principal aquí es el semáforo propuesto por Dijkstroy hace más de medio siglo. Un semáforo es, en términos simples, un número entero positivo controlado por un sistema, y dos operaciones en él: aumentar y disminuir. Si la reducción no funciona, cero, entonces el hilo de llamada está bloqueado. Cuando el número es incrementado por algún otro hilo / proceso activo, entonces los hilos se saltan, y el semáforo nuevamente disminuye por el número de pasados. Puedes imaginar trenes en un cuello de botella con un semáforo. .NET ofrece varios diseños con características similares: AutoResetEvent , ManualResetEvent , Mutex y Semaphore . Usaremos AutoResetEvent , esta es la más simple de estas construcciones: solo dos valores son 0 y 1 (falso, verdadero). Su método WaitOne() bloquea el hilo de llamada si el valor era 0, y si es 1, luego baja a 0 y lo omite. Y el método Set() aumenta a 1 y omite una espera, que nuevamente baja a 0. Actúa como un torniquete en el metro.
Complicaremos la solución y usaremos la cerradura para cada filósofo, y no para todos a la vez. Es decir ahora puede haber varios filósofos a la vez, y ninguno. Pero nuevamente bloqueamos el acceso a la mesa para tomar los tenedores correctamente, evitando carreras (condiciones de carrera).
Para comprender lo que está sucediendo aquí, considere el caso en que el filósofo no tomó los tenedores, entonces sus acciones serán así. Está esperando el acceso a la mesa. Habiéndolo recibido, intenta tomar los tenedores. No funcionó. Da acceso a la mesa (exclusión mutua). Y pasa su "torniquete" ( AutoResetEvent ) (al principio están abiertos). Entra nuevamente en el ciclo, porque No tiene tenedores. Trata de tomarlos y se detiene en su torniquete. Un vecino más afortunado a la derecha o a la izquierda, después de haber terminado de comer, desbloquea a nuestro filósofo, "abriendo su torniquete". Nuestro filósofo lo pasa (y se cierra detrás de él) por segunda vez. Intenta por tercera vez tomar los tenedores. Buena suerte Y pasa su torniquete a cenar.
Cuando hay errores aleatorios en dicho código (siempre existen), por ejemplo, un vecino se especifica incorrectamente o se AutoResetEvent el mismo objeto AutoResetEvent para todos ( Enumerable.Repeat ), entonces los filósofos esperarán a los desarrolladores, porque Encontrar errores en dicho código es una tarea bastante difícil. Otro problema con esta solución es que no garantiza que ningún filósofo se muera de hambre.
Soluciones híbridas
Examinamos dos enfoques para la sincronización cuando permanecemos en modo de usuario y giramos en un bucle y cuando bloqueamos un hilo a través del núcleo. El primer método es bueno para cerraduras cortas, el segundo para cerraduras largas. A menudo, primero debe esperar brevemente a que cambie una variable en el bucle y luego bloquear el hilo cuando la espera es larga. Este enfoque se implementa en el llamado diseños híbridos Aquí hay las mismas construcciones que para el modo kernel, pero ahora con un bucle en modo usuario: SemaphorSlim , ManualResetEventSlim , etc. La construcción más popular aquí es Monitor , porque C # tiene una sintaxis de lock conocida. Monitor es el mismo semáforo con un valor máximo de 1 (mutex), pero con soporte para esperar en un bucle, recursión, patrón de Variable de condición (al respecto a continuación), etc. Veamos una solución con él.
Aquí bloqueamos nuevamente toda la mesa para acceder a las horquillas, pero ahora desbloqueamos todos los flujos a la vez, y no a los vecinos cuando alguien termina de comer. Es decir primero, alguien come y bloquea a los vecinos, y cuando este termina, pero quiere volver a comer de inmediato, entra en la cerradura y despierta a sus vecinos, porque Su tiempo de espera es más corto.
Así evitamos los callejones sin salida y el hambre de algún filósofo. Usamos un ciclo para una espera corta y bloqueamos el flujo para una larga. Desbloquear todo a la vez funciona más lentamente que si solo el vecino estuviera desbloqueado, como en la solución con AutoResetEvent , pero la diferencia no debería ser grande, porque los hilos deben permanecer en modo de usuario primero.
El lock sintaxis tiene sorpresas desagradables. Recomiendan usar Monitor directamente [Richter] [Eric Lippert]. Uno de ellos es que el lock siempre sale de Monitor , incluso si hubo una excepción, y luego otro subproceso puede cambiar el estado de la memoria compartida. En tales casos, a menudo es mejor ir al punto muerto o de alguna manera completar el programa de manera segura. Otra sorpresa es que Monitor usa bloques de sincronización ( SyncBlock ), que están en todos los objetos. Por lo tanto, si selecciona el objeto incorrecto, puede obtener fácilmente un punto muerto (por ejemplo, si realiza un bloqueo en la cadena interna). Siempre usamos un objeto oculto para esto.
El patrón de condición variable le permite implementar de manera más concisa la expectativa de una condición compleja. En .NET, está incompleto, en mi opinión, porque en teoría debería haber varias colas en varias variables (como en los hilos de Posix), y no en un bloqueo. Entonces uno podría hacerlos para todos los filósofos. Pero de esta forma, le permite reducir el código.
Muchos filósofos o async / await
Ok, ahora podemos bloquear efectivamente los hilos. Pero, ¿qué pasa si tenemos muchos filósofos? 100? 10000? Por ejemplo, recibimos 100,000 solicitudes a un servidor web. Crear una secuencia para cada solicitud será una sobrecarga, porque tantos hilos no se ejecutarán en paralelo. Solo se ejecutarán tantos núcleos lógicos (tengo 4). Y todos los demás simplemente tomarán recursos. Una solución a este problema es el patrón asíncrono / espera. Su idea es que una función no contenga una secuencia, si necesita esperar a que continúe. Y cuando hace esto, algo sucede, reanuda su ejecución (¡pero no necesariamente en el mismo hilo!). En nuestro caso, esperaremos el enchufe.
SemaphoreSlim tiene un método WaitAsync() para esto. Aquí hay una implementación que usa este patrón.
async / await , Task . , , Task. , , . , , , , . . async / await .
. 100 4 , 8 . Monitor 4 , . 4 2. async / await 100, 6.8 . , 6 . Monitor .
Conclusión
, .NET . , , , . . , , , TPL Dataflow, Reactive , Software Transaction .
Fuentes