¿De quién es el sistema tecnológico central la tecnología de programación paralela?
Antes de que expire la Ley de Moore, mejorar el rendimiento del procesador mediante el aumento de la frecuencia, el hyper-threading de hardware y otras tecnologías pueden satisfacer las necesidades de las aplicaciones. A medida que el aumento de la frecuencia principal se acerca al muro de la velocidad de la luz, la Ley de Moore comienza a expirar gradualmente y la integración de múltiples núcleos se convierte en el método principal para mejorar el rendimiento del procesador. Hoy en día es difícil ver procesadores de un solo núcleo en el mercado, lo que demuestra esta tendencia de desarrollo. Para aprovechar al máximo las ricas ventajas de los recursos informáticos de múltiples núcleos, la programación paralela en múltiples núcleos es inevitable. El kernel de Linux es un escenario típico de programación paralela de múltiples núcleos. Pero la programación paralela en sistemas multinúcleo presenta muchos desafíos.
Desafíos de la programación paralela de múltiples núcleos
Las computadoras convencionales actualmente son todas de arquitectura von Neumann, que es un modelo informático de memoria compartida * * *, que no es compatible con la computación paralela. La siguiente figura es una arquitectura típica de hardware de computadora.
En esta arquitectura, existen las siguientes características de diseño:
Múltiples núcleos de CPU mejoran la potencia informática del procesador;
Múltiples niveles de caché mejoran el acceso a la CPU Eficiencia de la memoria principal;
Cada CPU tiene memoria local (NUMA), lo que mejora aún más la eficiencia del acceso de la CPU a la memoria principal;
El módulo de búfer de almacenamiento mejora la latencia de respuesta de escritura de caché Problemas que causan pausas de escritura;
El módulo de cola no válida mejora el retraso de las respuestas no válidas y envía respuestas inmediatamente después de colocar comandos no válidos en la cola;
El DMA periférico admite el acceso directo a la memoria principal, mejora la CPU eficiencia;
Estas características de diseño del sistema de hardware también introducen muchos problemas, los más importantes son la coherencia de la caché y la ejecución desordenada.
La coherencia de la caché se resuelve mediante el protocolo de coherencia de la caché MESI, que está garantizado por el hardware y es transparente al software. El protocolo MESI garantiza que todas las CPU modifiquen variables individuales en una única línea de caché en el mismo orden, pero no garantiza que las modificaciones de diferentes variables se produzcan en el mismo orden en todas las CPU. Esto crea confusión. No solo eso, hay muchas razones para el desorden:
Los retrasos en el procesamiento causados por buffers de almacenamiento pueden causar caos;
Los retrasos en el procesamiento causados por colas no válidas pueden causar caos;
La optimización de la compilación causará desorden;
Las tecnologías de optimización del hardware de la CPU, como la predicción de bifurcaciones y la multicanalidad, causarán desorden;
DMA periférico causará desorden en los datos;
Esta situación hace que incluso las operaciones ++ simples no puedan garantizar la atomicidad. Estos problemas deben resolverse mediante nuevos medios técnicos de programación paralela multinúcleo.
Tecnologías clave para la programación paralela de múltiples núcleos
Tecnología de bloqueo
El kernel de Linux proporciona una variedad de mecanismos de bloqueo, como bloqueos de giro, semáforos y exclusión mutua. y leer Bloqueos de escritura, bloqueos secuenciales, etc. A continuación se muestra una comparación simple de varios bloqueos. Los detalles de implementación y uso no se ampliarán aquí. Puede consultar los capítulos relevantes del libro "Diseño e implementación del kernel de Linux".
Bloqueo de giro, sin suspensión, sin sobrecarga de cambio de contexto de proceso, se puede usar cuando el contexto de interrupción y la sección crítica son pequeños.
Semáforo, puede suspenderse, admite múltiples entidades concurrentes; la sección crítica al mismo tiempo se puede usar en situaciones donde puede ocurrir el sueño o la sección crítica es muy larga;
Mutuamente excluyentes, similar a un semáforo, pero solo admite que un solo cuerpo concurrente ingrese a la sección crítica al mismo tiempo;
Bloqueo de lectura y escritura, admite lectura simultánea, escritura/lectura/escritura mutuamente excluyentes, la lectura retrasará la escritura, es fácil de leer y adecuado para situaciones orientadas a la lectura;
Bloqueo secuencial, admite lectura simultánea, escritura/lectura y escritura son mutuamente excluyentes, retrasa la lectura al escribir, es fácil de escribir, adecuado para situaciones orientadas a la escritura;
Aunque la tecnología de bloqueo puede brindar protección efectiva contra la competencia bajo ejecución paralela, el paralelismo de los bloqueos se puede expandir. Tiene un rendimiento deficiente y no puede aprovechar al máximo las ventajas de rendimiento de los núcleos múltiples. Si la granularidad del bloqueo es demasiado gruesa, limitará la escalabilidad. Si la granularidad es demasiado fina, provocará una enorme sobrecarga del sistema, dificultará el diseño y fácilmente provocará un punto muerto. Además de la mala escalabilidad de la concurrencia y los interbloqueos, los bloqueos también pueden introducir muchos otros problemas, como pánico en los bloqueos, bloqueos en vivo, inanición, bloqueos injustos, inversión de prioridad, etc. Sin embargo, existen técnicas o pautas que pueden abordar o reducir el riesgo de estos problemas.
Utilice bloqueos ordenados uniformemente (jerarquía de bloqueos) para resolver problemas de interbloqueo.
La regresión exponencial resuelve problemas de bloqueo vivo/inanición.
Los bloqueos de rango (bloqueo de árbol) resuelven el problema. problema del grupo de alarma de bloqueo;
La herencia de prioridad resuelve el problema de la inversión de prioridad;
Tecnología atómica
La tecnología atómica resuelve principalmente el problema de la caché y la memoria Inconsistencias y La ejecución fuera de orden daña los accesos atómicos. Las principales primitivas atómicas en el kernel de Linux son:
ACCESS_ONCE(), READ_ONCE() y WRITE_ONCE(): prohíben al compilador optimizar el acceso a los datos y obligan a que los datos se obtengan de la memoria en lugar del caché;
p>
Barrera (): barrera de memoria de acceso desordenada, que limita la optimización desordenada del compilador;
Smb_wmb(): barrera de memoria de escritura, actualización del búfer de almacenamiento, limitar la optimización desordenada del compilador y la CPU;
Smb_rmb(): lee la barrera de la memoria, actualiza la cola no válida, limita la optimización desordenada del compilador y la CPU;
Smb_mb(): lee y escribe la barrera de la memoria, actualiza el almacenamiento al mismo tiempo. Los buffers y las colas no válidas limitan la optimización desordenada del compilador y la CPU;
Atomic_inc ()/atómica_read(), etc. :Operación atómica entera;
Estrictamente hablando, como software de sistema, la implementación del kernel de Linux se ve muy afectada por el hardware, y diferentes hardware tienen diferentes modelos de memoria. Por lo tanto, a diferencia de los lenguajes de alto nivel, no existe un modelo unificado para la semántica de las primitivas atómicas en el kernel de Linux. Por ejemplo, en la CPU ARM64 de SMP, la implementación de barrera, smb_wmb y smb_rmb es la misma que smb_mb, y todas son volátiles (memoria ("::").
Además, vale la pena mencionar que la primitiva atomic_inc() necesita actualizar el caché para garantizar la atomicidad, pero la propagación de líneas de caché en sistemas multinúcleo requiere mucho tiempo y su escalabilidad paralela en sistemas multinúcleo es pobre.
Tecnología sin bloqueo
La tecnología atómica mencionada anteriormente es una de las tecnologías sin bloqueo. Además, la tecnología sin bloqueo también incluye RCU, indicadores de peligro, etc. Cabe mencionar que estas tecnologías sin bloqueos se basan en barreras de memoria.
Los punteros peligrosos se utilizan principalmente para la gestión del ciclo de vida de los objetos, de forma similar al recuento de referencias, pero tienen una mejor escalabilidad paralela que el recuento de referencias.
RCU es adecuado para muchos escenarios y puede ser reemplazado por bloqueos de lectura y escritura, recuento de referencias, recolectores de basura y espera a que terminen las cosas, lo que tiene una mejor escalabilidad paralela. Sin embargo, RCU también tiene algunos escenarios que no son aplicables, como escribir puntos clave; personas a cargo de áreas clave y áreas clave durmiendo;
Pero todas las primitivas sin bloqueo solo pueden resolver el problema de la escalabilidad paralela en el lado de lectura, y la escalabilidad paralela en el lado de escritura solo se puede resolver mediante tecnología de segmentación de datos.
Tecnología de segmentación de datos
Dividir estructuras de datos y reducir los datos compartidos es la forma fundamental de resolver la escalabilidad paralela. Las estructuras de datos compatibles con particiones (es decir, compatibles con paralelos) incluyen:
matriz
tabla hash
árbol Radix)/matriz dispersa
Saltar listas
El uso de estas estructuras de datos fácilmente particionables nos ayudará a mejorar la escalabilidad paralela mediante la partición de datos.
Además de utilizar estructuras de datos adecuadas, también son importantes pautas de segmentación razonables:
Separación de lectura y escritura: separación de datos basados en lectura y datos basados en escritura;
Segmentación de ruta: divide los datos según rutas de ejecución de código independientes;
Partición especial: vincula datos actualizados con frecuencia a CPU/subprocesos específicos;
División de propiedad: divide la estructura de datos según al número de CPU/subprocesos y divida los datos en por CPU/por subproceso;
Entre las cuatro reglas de división, la división de propiedad es la más exhaustiva.
Estos contenidos de programación paralela multinúcleo cubren básicamente todas las tecnologías clave de la programación concurrente del kernel de Linux. Por supuesto, existen muchas otras tecnologías de programación paralela que no se han aplicado al kernel de Linux, como las tecnologías de programación funcional paralela sin efectos secundarios (Erlang/Go, etc.). ), paso de mensajes, MapReduce, etc.