Hispanopedia WikiEn informática , la sincronización es la tarea de coordinar múltiples procesos para que se unan o establezcan una conexión en un punto determinado, con el fin de llegar a un acuerdo o comprometerse con una determinada secuencia de acciones.
Motivación
La necesidad de sincronización no surge únicamente en sistemas multiprocesador, sino en cualquier tipo de proceso concurrente, incluso en sistemas de un solo procesador. A continuación, se mencionan algunas de las principales necesidades de sincronización:
Bifurcaciones y uniones : Cuando una tarea llega a un punto de bifurcación, se divide en N subtareas, cada una atendida por N tareas. Tras ser atendida, cada subtarea espera hasta que todas las demás hayan terminado su procesamiento. Luego, se vuelven a unir y abandonan el sistema. Por lo tanto, la programación paralela requiere sincronización, ya que todos los procesos paralelos esperan a que se ejecuten otros procesos.
Relación productor-consumidor: En una relación productor-consumidor, el proceso del consumidor depende del proceso del productor hasta que se hayan generado los datos necesarios.
Recursos de uso exclusivo: Cuando varios procesos dependen de un recurso y necesitan acceder a él simultáneamente, el sistema operativo debe garantizar que solo un procesador acceda a él en un momento dado. Esto reduce la concurrencia.
Requisitos
La sincronización de hilos se define como un mecanismo que garantiza que dos o más procesos o hilos concurrentes no ejecuten simultáneamente un segmento de programa específico conocido como sección crítica . El acceso de los procesos a la sección crítica se controla mediante técnicas de sincronización. Cuando un hilo comienza a ejecutar la sección crítica (segmento serializado del programa), el otro hilo debe esperar hasta que el primero finalice. Si no se aplican las técnicas de sincronización adecuadas [ 1 ] , puede producirse una condición de carrera en la que los valores de las variables pueden ser impredecibles y variar según los tiempos de cambio de contexto de los procesos o hilos.
Por ejemplo, supongamos que hay tres procesos: 1, 2 y 3. Los tres se ejecutan simultáneamente y necesitan compartir un recurso común (sección crítica), como se muestra en la Figura 1. Se debe utilizar la sincronización para evitar conflictos al acceder a este recurso compartido. Por lo tanto, cuando los procesos 1 y 2 intentan acceder a dicho recurso, este debe asignarse a un solo proceso a la vez. Si se asigna al proceso 1, el otro proceso (proceso 2) debe esperar hasta que el proceso 1 libere el recurso (como se muestra en la Figura 2).
Otro requisito de sincronización que debe tenerse en cuenta es el orden en que deben ejecutarse los procesos o hilos específicos. Por ejemplo, no se puede abordar un avión sin haber comprado el billete. Del mismo modo, no se pueden consultar los correos electrónicos sin antes validar las credenciales correspondientes (por ejemplo, nombre de usuario y contraseña). De igual forma, un cajero automático no prestará ningún servicio hasta que reciba el PIN correcto.
Además de la exclusión mutua, la sincronización también aborda lo siguiente:
- Interbloqueo , que ocurre cuando muchos procesos esperan un recurso compartido (sección crítica) que está siendo utilizado por otro proceso. En este caso, los procesos simplemente siguen esperando y no se ejecutan más;
- inanición , que ocurre cuando un proceso está esperando para entrar en la sección crítica, pero otros procesos monopolizan la sección crítica y el primer proceso se ve obligado a esperar indefinidamente;
- La inversión de prioridad se produce cuando un proceso de alta prioridad se encuentra en la sección crítica y es interrumpido por un proceso de prioridad media. Esta violación de las reglas de prioridad puede ocurrir en determinadas circunstancias y puede tener graves consecuencias en los sistemas en tiempo real.
- La espera activa se produce cuando un proceso consulta con frecuencia si tiene acceso a una sección crítica. Esta consulta frecuente consume tiempo de procesamiento que otros procesos podrían utilizar.
Minimización
Uno de los desafíos para el diseño de algoritmos de exaescala es minimizar o reducir la sincronización. La sincronización consume más tiempo que el cálculo, especialmente en la computación distribuida. La reducción de la sincronización ha sido objeto de atención por parte de los científicos informáticos durante décadas. Sin embargo, se ha convertido en un problema cada vez más significativo recientemente a medida que aumenta la brecha entre la mejora de la computación y la latencia. Los experimentos han demostrado que las comunicaciones (globales) debidas a la sincronización en computadoras distribuidas ocupan una parte dominante en un solucionador iterativo disperso. [ 2 ] Este problema está recibiendo cada vez más atención tras la aparición de una nueva métrica de referencia, el Gradiente Conjugado de Alto Rendimiento (HPCG), [ 3 ] para clasificar las 500 supercomputadoras más potentes.
Problemas
Los siguientes son algunos problemas clásicos de sincronización:
- El problema del productor-consumidor (también llamado problema del búfer limitado);
- El problema de los lectores-escritores ;
- El problema de los filósofos comensales .
Estos problemas se utilizan para probar prácticamente todos los esquemas o primitivos de sincronización que se proponen recientemente.
Arriba
Los costos de sincronización pueden afectar significativamente el rendimiento en entornos de computación paralela , donde la fusión de datos de múltiples procesos puede generar costos sustancialmente más altos —a menudo en dos o más órdenes de magnitud— que el procesamiento de los mismos datos en un solo hilo, principalmente debido a la sobrecarga adicional de la comunicación entre procesos y los mecanismos de sincronización. [ 4 ] [ 5 ] [ 6 ]
Sincronización de hardware
Muchos sistemas proporcionan soporte de hardware para el código de secciones críticas .
Un sistema de un solo procesador o uniprocesador podría deshabilitar las interrupciones ejecutando el código en ejecución sin expropiación , lo cual es muy ineficiente en sistemas multiprocesador . [ 7 ] "La capacidad clave que requerimos para implementar la sincronización en un multiprocesador es un conjunto de primitivas de hardware con la capacidad de leer y modificar atómicamente una ubicación de memoria. Sin dicha capacidad, el costo de construir primitivas de sincronización básicas será demasiado alto y aumentará a medida que aumente el número de procesadores. Existen varias formulaciones alternativas de las primitivas de hardware básicas, todas las cuales proporcionan la capacidad de leer y modificar atómicamente una ubicación, junto con alguna forma de determinar si la lectura y la escritura se realizaron atómicamente. Estas primitivas de hardware son los bloques de construcción básicos que se utilizan para construir una amplia variedad de operaciones de sincronización a nivel de usuario, incluyendo elementos como bloqueos y barreras . En general, los arquitectos no esperan que los usuarios empleen las primitivas de hardware básicas, sino que esperan que los programadores del sistema las utilicen para construir una biblioteca de sincronización, un proceso que suele ser complejo y delicado." [ 8 ] Muchos dispositivos de hardware modernos proporcionan tales instrucciones atómicas, dos ejemplos comunes son: test-and-set , que opera en una sola palabra de memoria, y compare-and-swap , que intercambia el contenido de dos palabras de memoria.
Soporte en lenguajes de programación
En Java , una forma de prevenir la interferencia entre hilos y los errores de consistencia de memoria es anteponiendo la palabra clave `synchronized` a la firma de un método . En este caso, se utiliza el bloqueo del objeto declarante para garantizar la sincronización. Otra forma es encapsular un bloque de código en una sección `synchronized(someObject){...}` , que ofrece un control más preciso. Esto obliga a cualquier hilo a adquirir el bloqueo de `someObject` antes de poder ejecutar el bloque contenido. El bloqueo se libera automáticamente cuando el hilo que lo adquirió abandona el bloque o entra en un estado de espera dentro del mismo. Las actualizaciones de variables realizadas por un hilo en un bloque `synchronized` se hacen visibles para otros hilos cuando estos también adquieren el bloqueo y ejecutan el bloque. En ambos casos, se puede utilizar cualquier objeto para proporcionar un bloqueo, ya que todos los objetos Java tienen un bloqueo intrínseco o un bloqueo de monitor asociado al instanciarse. [ 9 ]
Los bloques sincronizados de Java , además de permitir la exclusión mutua y la consistencia de la memoria, habilitan la señalización, es decir, el envío de eventos desde los hilos que han adquirido el bloqueo y están ejecutando el bloque de código a aquellos que esperan el bloqueo dentro del bloque. Por lo tanto, las secciones sincronizadas de Java combinan la funcionalidad de los mutex y los eventos para garantizar la sincronización. Esta estructura se conoce como monitor de sincronización .
El .NET Framework también utiliza primitivas de sincronización. [ 10 ] "La sincronización está diseñada para ser cooperativa, exigiendo que cada hilo siga el mecanismo de sincronización antes de acceder a los recursos protegidos para obtener resultados consistentes. El bloqueo, la señalización, los tipos de sincronización ligeros, spinwait y las operaciones interbloqueadas son mecanismos relacionados con la sincronización en .NET." [ 11 ]
Muchos lenguajes de programación admiten la sincronización, e incluso se han escrito lenguajes especializados completos para el desarrollo de aplicaciones integradas , donde la sincronización estrictamente determinista es primordial.
Implementación
cierres giratorios
Otra forma eficaz de implementar la sincronización es mediante el uso de spinlocks. Antes de acceder a cualquier recurso compartido o fragmento de código, cada procesador comprueba un indicador. Si el indicador está desactivado, el procesador lo activa y continúa ejecutando el hilo. Pero si el indicador está activado (bloqueado), los hilos entrarían en un bucle infinito comprobando continuamente si el indicador está activado o no. Los spinlocks solo son eficaces si el indicador se desactiva para ciclos bajos; de lo contrario, pueden provocar problemas de rendimiento, ya que se desperdician muchos ciclos del procesador esperando. [ 12 ]
Barreras
Las barreras son fáciles de implementar y ofrecen una buena capacidad de respuesta. Se basan en el concepto de implementar ciclos de espera para lograr la sincronización. Consideremos tres hilos ejecutándose simultáneamente, comenzando desde la barrera 1. Después de un tiempo t, el hilo 1 llega a la barrera 2, pero aún debe esperar a que los hilos 2 y 3 lleguen a ella, ya que no dispone de los datos correctos. Una vez que todos los hilos llegan a la barrera 2, vuelven a comenzar. Después de un tiempo t, el hilo 1 llega a la barrera 3, pero tendrá que esperar nuevamente a que los hilos 2 y 3 lleguen y dispongan de los datos correctos.
Por lo tanto, en la sincronización de barrera de múltiples hilos siempre habrá algunos hilos que terminarán esperando a otros hilos, como en el ejemplo anterior, donde el hilo 1 espera a los hilos 2 y 3. Esto resulta en una degradación severa del rendimiento del proceso. [ 13 ]
La función de espera de sincronización de barrera para el i -ésimo hilo se puede representar como:
(Wbarrera)i=f ((Tbarrera)i, (Rhilo)i)
Donde Wbarrier es el tiempo de espera para un hilo, Tbarrier es el número de hilos que han llegado y Rthread es la tasa de llegada de hilos. [ 14 ]
Los experimentos muestran que el 34% del tiempo total de ejecución se emplea en esperar a otros hilos más lentos. [ 13 ]
Semáforos
Los semáforos son mecanismos de señalización que permiten a uno o más hilos/procesadores acceder a una sección. Un semáforo tiene un indicador con un valor fijo asociado. Cada vez que un hilo intenta acceder a la sección, decrementa dicho indicador. Del mismo modo, cuando el hilo abandona la sección, el indicador se incrementa. Si el indicador es cero, el hilo no puede acceder a la sección y se bloquea si decide esperar.
Algunos semáforos permiten el acceso a una sola rama o proceso en la sección de código. Estos semáforos se denominan semáforos binarios y son muy similares a los mutex. En este caso, si el valor del semáforo es 1, se permite el acceso a la rama, y si el valor es 0, se deniega el acceso. [ 15 ]
Transacción distribuida
En las arquitecturas orientadas a eventos , las transacciones síncronas se pueden lograr mediante el uso del paradigma de solicitud-respuesta y se pueden implementar de dos maneras: [ 16 ]
Fundamentos matemáticos
La sincronización era originalmente un concepto basado en procesos, mediante el cual se podía obtener un bloqueo sobre un objeto. Su uso principal se daba en las bases de datos. Existen dos tipos de bloqueo (de archivos) : de solo lectura y de lectura-escritura. Los bloqueos de solo lectura pueden ser obtenidos por varios procesos o hilos. Los bloqueos de lectura-escritura son exclusivos, ya que solo pueden ser utilizados por un único proceso o hilo a la vez.
Si bien los bloqueos se diseñaron para bases de datos de archivos, los datos también se comparten en memoria entre procesos e hilos. En ocasiones, se bloquea más de un objeto (o archivo) simultáneamente. Si no se bloquean al mismo tiempo, pueden superponerse, provocando una excepción de interbloqueo.
Java y Ada solo tienen bloqueos exclusivos porque se basan en hilos y dependen de la instrucción de procesador de comparación e intercambio .
El monoide histórico proporciona una base matemática abstracta para las primitivas de sincronización . Además, existen numerosos instrumentos teóricos de nivel superior, como los cálculos de procesos y las redes de Petri , que pueden construirse sobre el monoide histórico.
Ejemplos
A continuación se muestran algunos ejemplos de sincronización con respecto a diferentes plataformas. [ 17 ]
En Windows
Windows proporciona:
- máscaras de interrupción , que protegen el acceso a los recursos globales (sección crítica) en sistemas monoprocesador;
- los spinlocks , que impiden que, en sistemas multiprocesador, el hilo spinlocking sea interrumpido;
- despachadores dinámicos , que actúan como mutexes , semáforos , eventos y temporizadores .
En Linux
Linux proporciona:
- semáforos ;
- bloqueo de giro ;
- barreras ;
- mutex ;
- bloqueos de lectura-escritura , para la sección más larga de códigos a los que se accede con mucha frecuencia pero que no cambian muy a menudo;
- leer-copiar-actualizar (RCU). [ 18 ]
La activación y desactivación de la preemptividad del kernel sustituyó a los spinlocks en los sistemas monoprocesador. Antes de la versión 2.6 del kernel, Linux desactivaba las interrupciones para implementar secciones críticas cortas. Desde la versión 2.6 en adelante, Linux es totalmente preemptivo.
En Solaris
Solaris proporciona:
- semáforos
- variables de condición
- mutex adaptativos : semáforos binarios que se implementan de manera diferente según las condiciones [ 19 ].
- bloqueos de lectores-escritores
- torniquetes – cola de hilos que esperan el bloqueo adquirido [ 20 ]
En Pthreads
Pthreads es una API independiente de la plataforma que proporciona:
- mutexes;
- variables de condición;
- bloqueos lector-escritor;
- bloqueos de giro;
- barreras .
Véase también
- Futuros y promesas , mecanismos de sincronización en paradigmas puramente funcionales
- Barrera de la memoria
Referencias
- ↑ Gramoli, V. (2015). Más de lo que jamás quisiste saber sobre sincronización: Synchrobench, midiendo el impacto de la sincronización en algoritmos concurrentes (PDF) . Actas del 20.º Simposio ACM SIGPLAN sobre Principios y Práctica de la Programación Paralela. ACM. págs. 1–10 .
- ↑ Shengxin, Zhu y Tongxiang Gu y Xingping Liu (2014). "Minimizing synchronizations in sparse iterative solvers for distributed supercomputers" . Computers & Mathematics with Applications . 67 (1): 199– 209. doi : 10.1016/j.camwa.2013.11.008 . hdl : 10754/668399 .
- ↑ "HPCG Benchmark" .
- ↑ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (29 de julio de 2008). Conceptos de sistemas operativos . Wiley. ISBN 978-0470128725.
- ↑ Organización y diseño de computadoras, edición MIPS: La interfaz hardware/software (Serie Morgan Kaufmann de arquitectura y diseño de computadoras) . Morgan Kaufmann. 2013. ISBN 978-0124077263.
- ↑ Programación paralela: técnicas y aplicaciones con estaciones de trabajo en red y ordenadores paralelos . Pearson. 2005. ISBN 978-0131405639.
- ↑ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (11 de julio de 2008). «Capítulo 6: Sincronización de procesos». Conceptos de sistemas operativos (octava edición). John Wiley & Sons. ISBN 978-0-470-12872-5.
- ↑ Hennessy, John L.; Patterson, David A. (30 de septiembre de 2011). «Capítulo 5: Paralelismo a nivel de subprocesos». Arquitectura de computadoras: Un enfoque cuantitativo (Quinta ed.). Morgan Kaufmann. ISBN 978-0-123-83872-8.
- ↑ "Bloqueos intrínsecos y sincronización" . Los tutoriales de Java . Oracle . Consultado el 10 de noviembre de 2023 .
- ↑ "Descripción general de las primitivas de sincronización" . Microsoft Learn . Microsoft. Septiembre de 2022. Consultado el 10 de noviembre de 2023 .
- ↑ Rouse, Margaret (19 de agosto de 2011). "Sincronización" . Techopedia . Consultado el 10 de noviembre de 2023 .
- ↑ Massa, Anthony (2003). Desarrollo de software embebido con ECos . Pearson Education Inc. ISBN 0-13-035473-2.
- 1 2 Meng, Jinglei; Chen, Tianzhou; Pan, Ping; Yao, Jun; Wu, Minghui (2014). "Un mecanismo especulativo para la sincronización de barreras". 2014 IEEE Intl Conf on High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS) . pp. 858–865 . doi : 10.1109/HPCC.2014.148 . ISBN 978-1-4799-6123-8.
- ↑ Rahman, Mohammed Mahmudur (2012). "Sincronización de procesos en procesadores multinúcleo y multiprocesador". Conferencia Internacional de Informática, Electrónica y Visión (ICIEV) de 2012. pp. 554–559 . doi : 10.1109/ICIEV.2012.6317471 . ISBN 978-1-4673-1154-0. S2CID 8134329 .
- ↑ Li, Yao, Qing, Carolyn (2003). Conceptos de tiempo real para sistemas embebidos . CMP Books. ISBN 978-1578201242.
{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace ) - ↑ Richards, Mark (2020). Fundamentos de la arquitectura de software: Un enfoque de ingeniería . O'Reilly Media. ISBN 978-1492043454.
- ↑ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (7 de diciembre de 2012). «Capítulo 5: Sincronización de procesos». Conceptos de sistemas operativos (novena ed.). John Wiley & Sons. ISBN 978-1-118-06333-0.
- ↑ "¿Qué es RCU, fundamentalmente? [ LWN.net ] " . lwn.net .
- ↑ "Sondas de bloqueo adaptativas" . Documentación de Oracle .
- ↑ Mauro, Jim. "Torniscos y herencia de prioridad - SunWorld - Agosto de 1999" . sunsite.uakom.sk .
- Schneider, Fred B. (1997). Sobre programación concurrente . Springer-Verlag New York, Inc. ISBN 978-0-387-94942-0.
Enlaces externos
- Anatomía de los métodos de sincronización de Linux en IBM developerWorks
- El pequeño libro de las señales de semáforo , de Allen B. Downey
- Necesidad de sincronización de procesos
- Concurrencia (informática)
- Comunicación mediada por ordenador
- Sincronización
