stringtranslate.com

Sincronización (informática)

En informática , la sincronización es la tarea de coordinar múltiples procesos para que se unan o se comuniquen 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 monoprocesador. A continuación se mencionan algunas de las principales necesidades de sincronización:

Bifurcaciones y uniones : cuando un trabajo llega a un punto de bifurcación, se divide en N subtrabajos que luego son atendidos por n tareas. Después de ser atendidos, cada subtrabajo espera hasta que todos los demás subtrabajos hayan terminado de procesarse. 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 que se realicen varios otros procesos.

Productor-Consumidor: En una relación productor-consumidor, el proceso del consumidor depende del proceso del productor hasta que se hayan producido los datos necesarios.

Recursos de uso exclusivo: cuando varios procesos dependen de un recurso y necesitan acceder a él al mismo tiempo, el sistema operativo debe asegurarse de que solo un procesador acceda a él en un momento determinado. Esto reduce la concurrencia.

Requisitos

Figura 1 : Tres procesos acceden a un recurso compartido ( sección crítica ) simultáneamente.

La sincronización de subprocesos se define como un mecanismo que garantiza que dos o más procesos o subprocesos concurrentes no ejecuten simultáneamente algún segmento de programa en particular 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 subproceso comienza a ejecutar la sección crítica (segmento serializado del programa), el otro subproceso debe esperar hasta que el primer subproceso termine. Si no se aplican las técnicas de sincronización adecuadas [1] , puede causar una condición de carrera donde los valores de las variables pueden ser impredecibles y variar según los tiempos de los cambios de contexto de los procesos o subprocesos.

Por ejemplo, supongamos que hay tres procesos, a saber, 1, 2 y 3. Los tres se están ejecutando simultáneamente y necesitan compartir un recurso común (sección crítica), como se muestra en la Figura 1. En este caso, se debe utilizar la sincronización para evitar conflictos por el acceso a este recurso compartido. Por lo tanto, cuando los procesos 1 y 2 intentan acceder a ese recurso, este debe asignarse solo a un proceso a la vez. Si se asigna al proceso 1, el otro proceso (proceso 2) debe esperar hasta que el proceso 1 libere ese recurso (como se muestra en la Figura 2).

Figura 2 : Un proceso que accede a un recurso compartido si está disponible, basándose en alguna técnica de sincronización.

Otro requisito de sincronización que debe tenerse en cuenta es el orden en que se deben ejecutar determinados procesos o subprocesos. Por ejemplo, no se puede embarcar en un avión antes de comprar un billete. Del mismo modo, no se pueden consultar los correos electrónicos antes de validar las credenciales adecuadas (por ejemplo, el nombre de usuario y la contraseña). De la misma manera, un cajero automático no prestará ningún servicio hasta que reciba un PIN correcto.

Además de la exclusión mutua, la sincronización también se ocupa de lo siguiente:

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 requiere más tiempo que el cómputo, especialmente en computación distribuida. La reducción de la sincronización atrajo la atención de los científicos informáticos durante décadas. Mientras que se convierte 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) debido 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 después de la aparición de una nueva métrica de referencia, el gradiente conjugado de alto rendimiento (HPCG), [3] para clasificar las 500 mejores supercomputadoras.

Problemas clásicos

Los siguientes son algunos problemas clásicos de sincronización:

Estos problemas se utilizan para probar casi todos los esquemas o primitivos de sincronización recién propuestos.

Sincronización de hardware

Muchos sistemas proporcionan soporte de hardware para el código de sección crítica .

Un sistema monoprocesador o de un solo procesador podría desactivar las interrupciones ejecutando el código que se está ejecutando actualmente sin preempción , lo que es muy ineficiente en sistemas multiprocesador . [4] "La capacidad clave que necesitamos 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. Hay varias formulaciones alternativas de las primitivas de hardware básicas, todas las cuales brindan la capacidad de leer y modificar atómicamente una ubicación, junto con alguna forma de saber 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, incluidas cosas como cerraduras y barreras . En general, los arquitectos no esperan que los usuarios empleen las primitivas de hardware básicas, sino que esperan que los programadores de sistemas las utilicen para construir una biblioteca de sincronización, un proceso que a menudo es complejo y complicado". [5] Muchos equipos modernos proporcionan dichas 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 evitar la interferencia de subprocesos y los errores de consistencia de la memoria es anteponiendo la palabra clave sincronizada a la firma de un método , en cuyo caso se utiliza el bloqueo del objeto declarante para hacer cumplir la sincronización. Una segunda forma es envolver un bloque de código en una sección sincronizada (someObject){...} , que ofrece un control más detallado. Esto obliga a cualquier subproceso a adquirir el bloqueo de someObject antes de poder ejecutar el bloque contenido. El bloqueo se libera automáticamente cuando el subproceso que adquirió el bloqueo abandona este bloque o entra en un estado de espera dentro del bloque. Cualquier actualización de variable realizada por un subproceso en un bloque sincronizado se vuelve visible para otros subprocesos cuando adquieren el bloqueo de manera similar y ejecutan el bloque. Para cualquier implementación, se puede utilizar cualquier objeto para proporcionar un bloqueo porque todos los objetos Java tienen un bloqueo intrínseco o un bloqueo de monitor asociado con ellos cuando se instancian. [6]

Los bloques sincronizados de Java , además de permitir la exclusión mutua y la coherencia de la memoria, permiten la señalización, es decir, el envío de eventos desde los subprocesos que han adquirido el bloqueo y están ejecutando el bloque de código a los que están esperando 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. Este tipo de construcción se conoce como monitor de sincronización .

.NET Framework también utiliza primitivas de sincronización. [7] "La sincronización está diseñada para ser cooperativa, exigiendo que cada subproceso siga el mecanismo de sincronización antes de acceder a recursos protegidos para obtener resultados consistentes. El bloqueo, la señalización, los tipos de sincronización ligeros, spinwait y las operaciones interconectadas son mecanismos relacionados con la sincronización en .NET". [8]

Muchos lenguajes de programación admiten la sincronización y se han escrito lenguajes completos especializados para el desarrollo de aplicaciones integradas donde la sincronización estrictamente determinista es primordial.

Implementación

Bloqueo giratorio

Otra forma eficaz de implementar la sincronización es mediante el uso de bloqueos de giro. Antes de acceder a cualquier recurso compartido o fragmento de código, cada procesador comprueba una bandera. Si la bandera se restablece, entonces el procesador activa la bandera y continúa ejecutando el hilo. Pero, si la bandera está activada (bloqueada), los hilos seguirían girando en un bucle y seguirían comprobando si la bandera está activada o no. Pero los bloqueos de giro son eficaces sólo si la bandera se restablece para ciclos inferiores, de lo contrario puede provocar problemas de rendimiento, ya que desperdicia muchos ciclos de procesador en espera. [9]

Barreras

Las barreras son sencillas de implementar y brindan una buena capacidad de respuesta. Se basan en el concepto de implementar ciclos de espera para brindar sincronización. Considere tres subprocesos que se ejecutan simultáneamente, comenzando desde la barrera 1. Después del tiempo t, el subproceso 1 alcanza la barrera 2, pero aún tiene que esperar a que los subprocesos 2 y 3 lleguen a la barrera 2, ya que no tiene los datos correctos. Una vez que todos los subprocesos llegan a la barrera 2, todos comienzan de nuevo. Después del tiempo t, el subproceso 1 llega a la barrera 3, pero tendrá que esperar a los subprocesos 2 y 3 y a los datos correctos nuevamente.

Por lo tanto, en la sincronización de barrera de múltiples subprocesos siempre habrá algunos subprocesos que terminarán esperando a otros subprocesos, como en el ejemplo anterior, el subproceso 1 sigue esperando a los subprocesos 2 y 3. Esto da como resultado una degradación grave del rendimiento del proceso. [10]

La función de espera de sincronización de barrera para el hilo i se puede representar como:

(Wbarrera)i=f ((Tbarrera)i, (Rhilo)i)

Donde Wbarrier es el tiempo de espera de un hilo, Tbarrier es el número de hilos que han llegado y Rthread es la tasa de llegada de hilos. [11]

Los experimentos muestran que el 34% del tiempo total de ejecución se gasta esperando otros subprocesos más lentos. [10]

Semáforos

Los semáforos son mecanismos de señalización que permiten que uno o más subprocesos o procesadores accedan a una sección. Un semáforo tiene un indicador que tiene un valor fijo asociado y cada vez que un subproceso desea acceder a la sección, disminuye el indicador. De manera similar, cuando el subproceso abandona la sección, el indicador se incrementa. Si el indicador es cero, el subproceso no puede acceder a la sección y se bloquea si elige esperar.

Algunos semáforos solo permiten un hilo o proceso en la sección de código. Estos semáforos se denominan semáforos binarios y son muy similares a Mutex. En este caso, si el valor del semáforo es 1, se permite el acceso al hilo y, si el valor es 0, se deniega el acceso. [12]

Fundamentos matemáticos

La sincronización era originalmente un concepto basado en procesos mediante el cual se podía obtener un bloqueo en un objeto. Su uso principal era en bases de datos. Hay dos tipos de bloqueos (de archivos) : de solo lectura y de lectura y escritura. Los bloqueos de solo lectura pueden obtenerse mediante muchos procesos o subprocesos. Los bloqueos de lectura y escritura son exclusivos, ya que solo pueden ser utilizados por un único proceso o subproceso a la vez.

Aunque los bloqueos se derivaron para bases de datos de archivos, los datos también se comparten en la memoria entre procesos y subprocesos. A veces, se bloquea más de un objeto (o archivo) a la vez. Si no se bloquean simultáneamente, pueden superponerse y provocar una excepción de bloqueo.

Java y Ada solo tienen bloqueos exclusivos porque están basados ​​en subprocesos y dependen de la instrucción del procesador de comparación e intercambio .

El monoide histórico proporciona una base matemática abstracta para las primitivas de sincronización . También hay muchos dispositivos teóricos de nivel superior, como los cálculos de procesos y las redes de Petri , que se pueden construir sobre el monoide histórico.

Ejemplos

A continuación se presentan algunos ejemplos de sincronización con respecto a diferentes plataformas. [13]

En Windows

Windows proporciona:

En Linux

Linux proporciona:

La habilitación y deshabilitación de la preempción del núcleo reemplazó a los bloqueos de giro en los sistemas monoprocesador. Antes de la versión 2.6 del núcleo, Linux deshabilitaba la interrupción para implementar secciones críticas cortas. Desde la versión 2.6 y posteriores, Linux es completamente preemptivo.

En Solaris

Solaris ofrece:

En Pthreads

Pthreads es una API independiente de la plataforma que proporciona:

Véase también

Referencias

  1. ^ Gramoli, V. (2015). Más de lo que alguna vez quiso saber sobre sincronización: Synchrobench, midiendo el impacto de la sincronización en algoritmos concurrentes (PDF) . Actas del 20.º Simposio SIGPLAN de la ACM sobre principios y práctica de la programación paralela. ACM. pp. 1–10.
  2. ^ Shengxin, Zhu y Tongxiang Gu y Xingping Liu (2014). "Minimización de sincronizaciones en solucionadores iterativos dispersos para supercomputadoras distribuidas". Computers & Mathematics with Applications . 67 (1): 199–209. doi : 10.1016/j.camwa.2013.11.008 .
  3. ^ "Punto de referencia HPCG".
  4. ^ 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.
  5. ^ Hennessy, John L.; Patterson, David A. (30 de septiembre de 2011). "Capítulo 5: Paralelismo a nivel de subproceso". Arquitectura informática: un enfoque cuantitativo (quinta edición). Morgan Kaufmann. ISBN 978-0-123-83872-8.
  6. ^ "Bloqueos intrínsecos y sincronización". Tutoriales de Java . Oracle . Consultado el 10 de noviembre de 2023 .
  7. ^ "Descripción general de las primitivas de sincronización". Microsoft Learn . Microsoft. Septiembre de 2022 . Consultado el 10 de noviembre de 2023 .
  8. ^ Rouse, Margaret. «Sincronización». Techopedia . Consultado el 10 de noviembre de 2023 .
  9. ^ Massa, Anthony (2003). Desarrollo de software integrado con ECos . Pearson Education Inc. ISBN 0-13-035473-2.
  10. ^ ab Meng, Chen, Pan, Yao, Wu, Jinglei, Tianzhou, Ping, Jun. Minghui (2014). "Un mecanismo especulativo para la sincronización de barreras". Conferencia internacional IEEE de 2014 sobre informática y comunicaciones de alto rendimiento (HPCC), 6.º simposio internacional IEEE de 2014 sobre seguridad y protección del ciberespacio (CSS) y 11.ª conferencia internacional IEEE de 2014 sobre software y sistemas integrados (ICESS) .{{cite journal}}: CS1 maint: multiple names: authors list (link)
  11. ^ Rahman, Mohammed Mahmudur (2012). "Sincronización de procesos en procesadores multiprocesadores y multinúcleo". Conferencia internacional sobre informática, electrónica y visión (ICIEV) de 2012. págs. 554–559. doi :10.1109/ICIEV.2012.6317471. ISBN 978-1-4673-1154-0.S2CID8134329  .​
  12. ^ Li, Yao, Qing, Carolyn (2003). Conceptos de tiempo real para sistemas integrados . Libros CMP. ISBN 978-1578201242.{{cite book}}: CS1 maint: multiple names: authors list (link)
  13. ^ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (7 de diciembre de 2012). "Capítulo 5: Sincronización de procesos". Conceptos de sistemas operativos (novena edición). John Wiley & Sons. ISBN 978-1-118-06333-0.
  14. ^ "¿Qué es RCU, fundamentalmente? [LWN.net]". lwn.net .
  15. ^ "Sondas de bloqueo adaptativas". Oracle Docs .
  16. ^ Mauro, Jim. "Molinetes y herencia prioritaria - SunWorld - agosto de 1999". sunsite.uakom.sk .

Enlaces externos