multithreading - instrucciones - lenguaje maquina pdf

¿Cómo se implementa la sincronización de subprocesos en el nivel de lenguaje ensamblador?

Question

Si bien estoy familiarizado con los conceptos de programación simultánea, como mutexes y semáforos, nunca he entendido cómo se implementan en el nivel de lenguaje ensamblador.

Me imagino que hay un conjunto de "banderas" de memoria que dicen:

• el bloqueo A está retenido por el hilo 1
• el bloqueo B está retenido por el hilo 3
• el bloqueo C no está retenido por ningún hilo
• etc

Pero, ¿cómo se sincroniza el acceso a estos indicadores entre hilos? Algo como este ingenuo ejemplo solo crearía una condición de carrera:

 mov edx, [myThreadId]
wait:
cmp [lock], 0
jne wait
mov [lock], edx
; I wanted an exclusive lock but the above
; three instructions are not an atomic operation :(

Answer 1

La arquitectura x86 ha tenido durante mucho tiempo una instrucción llamada xchg que intercambiará el contenido de un registro con una ubicación de memoria. xchg siempre ha sido atómico.

También ha habido siempre un prefijo de lock que se podría aplicar a cualquier instrucción individual para hacer esa instrucción atómica. Antes de que existieran sistemas multiprocesador, todo lo que realmente se hacía era evitar que se entregara una interrupción en el medio de una instrucción bloqueada. (xchg estaba implícitamente bloqueado).

Este artículo tiene un código de muestra que usa xchg para implementar un spinlock spinlock

Cuando se comenzaron a construir sistemas multi-CPU y posteriores de múltiples núcleos, se necesitaban sistemas más sofisticados para asegurar que lock y xchg sincronizaran todos los subsistemas de memoria, incluida la caché de 1L en todos los procesadores. Aproximadamente en esta época, una nueva investigación sobre algoritmos de bloqueo y sin cerrojo mostró que el CompareAndSet atómico era un primitivo más flexible, por lo que las CPU más modernas lo tienen como una instrucción.

Adición: En los comentarios, andras suministró una lista de instrucciones "polvorientas" que permiten el prefijo de lock . http://pdos.csail.mit.edu/6.828/2007/readings/i386/LOCK.htm

Answer 2

Me gusta pensar en la sincronización de subprocesos como un proceso ascendente donde el procesador y el sistema operativo proporcionan construcciones que son primitivas a las más sofisticadas

En el nivel de procesador tiene CAS y LL / SC que le permiten realizar una prueba y almacenar en una sola operación atómica ... también tiene otras construcciones de procesador que le permiten desactivar y habilitar la interrupción (sin embargo, se consideran peligrosas). . bajo ciertas circunstancias, no tiene otra opción que usarlos)

El sistema operativo proporciona la capacidad de cambiar de contexto entre las tareas que pueden suceder cada vez que un hilo ha utilizado su porción de tiempo ... o puede suceder por otros motivos (voy a llegar a eso)

luego hay construcciones de nivel superior como mutexes que usa estos mecanismos primitivos provistos por el procesador (creo que gira el mutex) ... que esperará continuamente a que la condición se vuelva verdadera y verificará esa condición atómicamente

entonces estos mutex en rotación pueden usar la funcionalidad provista por OS (cambio de contexto y llamadas al sistema como rendimiento que renuncia al control a otro hilo) y nos da mutexes

estos constructos son utilizados además por constructos de nivel superior como variables condicionales (que pueden realizar un seguimiento de cuántos subprocesos están esperando el mutex y qué subproceso permitir primero cuando el mutex esté disponible)

Estas construcciones pueden utilizarse para proporcionar construcciones de sincronización más sofisticadas ... ejemplo: semáforos, etc.

Answer 3

• En la práctica, estos tienden a implementarse con CAS y LL/SC . (... y algo de spinning antes de renunciar a la porción de tiempo del hilo, usualmente llamando a una función kernel que cambia el contexto).
• Si solo necesitas un spinlock , wikipedia te da un ejemplo que intercambia CAS por lock con prefijo xchg en x86 / x64. Entonces, en un sentido estricto, un CAS no es necesario para crear un spinlock, pero todavía se necesita algún tipo de atomicidad. En este caso, utiliza una operación atómica que puede escribir un registro en la memoria y devolver el contenido anterior de esa ranura de memoria en un solo paso . (Para aclarar un poco más: el prefijo de bloqueo afirma la señal #LOCK que asegura que la CPU actual tiene acceso exclusivo a la memoria. En las CPU de hoy en día no se lleva a cabo necesariamente de esta manera, pero el efecto es el mismo. Usando xchg nos aseguramos de que no seamos apropiadamente en algún lugar entre la lectura y la escritura, ya que las instrucciones no se interrumpirán a la mitad. Así que si tuviéramos un bloqueo imaginario mov reg0, mem / bloqueo mov mem, reg1 par (que no) , eso no sería lo mismo, podría adelantarse solo entre los dos movs).
• En las arquitecturas actuales, como se señaló en los comentarios, en su mayoría terminan usando las primitivas atómicas de la CPU y los protocolos de coherencia proporcionados por el subsistema de memoria.
• Por esta razón, no solo tiene que usar estas primitivas, sino también tener en cuenta la coherencia / memoria garantizada por la arquitectura.
• Puede haber matices de implementación también. Considerando, por ejemplo, un spinlock:
  • en lugar de una implementación ingenua, probablemente debería usar, por ejemplo, un bloqueo de giro TTAS con un retroceso exponencial ,
  • en una CPU Hyper-Threaded, probablemente debería emitir instrucciones de pause que sirvan como pistas de que está girando, de modo que el núcleo en el que se está ejecutando pueda hacer algo útil durante este proceso.
  • en realidad deberías dejar de girar y controlar el rendimiento de otros hilos después de un tiempo
  • etc ...
• este sigue siendo el modo de usuario: si está escribiendo un kernel, es posible que tenga otras herramientas que también puede usar (ya que usted es el que planifica los hilos y maneja / habilita / deshabilita las interrupciones).