¿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.

Imagino que exista un conjunto de memoria "banderas", diciendo:

• bloqueo A se lleva a cabo por hilo 1
• bloqueo B está en manos de hilo 3
• cerradura C no se lleva a cabo por cualquier
hilo
• etc

Pero, ¿cómo está el acceso a estas banderas sincronizado entre los hilos? Algo así como este ejemplo ingenuo sólo se 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

• En la práctica, estos tienden a ser implementada con CAS y LL/SC. (... y algo girando antes de renunciar a la porción de tiempo del hilo - generalmente llamando a una función del kernel que cambia el contexto.)
• Si solo necesita un spinlock, la wikipedia le da un ejemplo que comercializa CAS para el bloqueo con el 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, se hace uso de una operación atómica que puede escribir un registro en la memoria y devolver el contenido anterior de que la ranura de memoria en un solo paso . (Para aclarar un poco más: el bloqueo prefijo afirma la señal #LOCK que asegura que la CPU actual tiene acceso exclusivo a la memoria en las CPUs de hoy no necesariamente se lleva a cabo de esta manera, pero el efecto es el mismo por.. utilizando xchg nos aseguramos de que no vamos a llegar adelantó en algún lugar entre la lectura y la escritura, ya que las instrucciones no serán interrumpidos a mitad de camino. Así que si teníamos un imaginario reg0 mov bloqueo, mem mem/bloqueo mov, reg1 par (que nos no lo hacen), que no sería bastante ser el mismo -. podría tener preferencia justo entre los dos MOV)
• en arquitecturas actuales, como se señala 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 sólo se tienen que utilizar estas primitivas, sino también dar cuenta de la coherencia de caché/memoria garantizado por la arquitectura.
• Puede haber matices de implementación también. Considerando, por ejemplo, un spinlock:
  • en lugar de una aplicación ingenua, que es mejor usar, por ejemplo, un TTAS spin-lock with some exponential backoff,
  • en una CPU con rosca-Hyper, probablemente debería emitir pause instrucciones que sirven como pistas de que estás girando - por lo que el núcleo está ejecutando en el que puede hacer algo útil durante este
  • realmente debería dar arriba en el hilado y dió el control a otros hilos después de un tiempo
  • etc ...
• este sigue siendo el modo de usuario - si está escribiendo un núcleo, que podría tener algunas otras herramientas que se pueden utilizar, así (ya que usted es el que planifica los hilos y maneja/habilita/deshabilita las interrupciones).

Answer 2

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

También ha habido siempre un prefijo lock que podría aplicarse a cualquiera una sola instrucción 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 ejemplo usando xchg para implementar un spinlock http://en.wikipedia.org/wiki/Spinlock

Cuando se empezaron a construir múltiples CPU y sistemas Core después de varios, se necesitan sistemas más sofisticados para asegurar que la cerradura y xchg habría sincronizar todos los subsistemas de memoria, incluida la memoria caché l1 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 se proporciona una lista de instrucciones "polvorientas" que permiten el prefijo lock. http://pdos.csail.mit.edu/6.828/2007/readings/i386/LOCK.htm

Answer 3

me gusta pensar de sincronización de subprocesos como de abajo hacia arriba, donde el procesador y el sistema operativo proporcionan constructo que son primitivos a más sofisticado

A nivel procesador que tiene CAS y LL/SC que le permiten realizar una prueba y almacena en una sola operación atómica ... también tienes otras construcciones de procesador que te permiten deshabilitar y habilitar la interrupción (sin embargo se consideran peligrosas ... en ciertas circunstancias no tienes otra opción que usarlas)

El sistema operativo

proporciona la capacidad de cambiar de contexto entre las tareas que pueden suceder cada vez que un subproceso ha utilizado su intervalo de tiempo ... o puede suceder por otros motivos (voy a llegar a eso)

luego hay construcciones de alto nivel como mutexes que utiliza estos mecanismos primitivos proporcionados por el procesador (creo que gira el mutex) ... que esperará continuamente por la condición para convertirse en verdadera y controles para que la condición atómicamente

entonces estos mutex hilado puede usar la funcionalidad proporcionada por el sistema operativo (cambio de contexto y el sistema de llamadas como rendimiento, que se renuncia al control a otro hilo) y nos da mutexes

estas construcciones se utilizan además por constructos de nivel superior como variables condicionales (que pueden hacer un seguimiento de cuántos hilos están esperando el mutex y que rosca para permitir primero cuando el mutex esté disponible)

Estas construcciones que se pueden utilizar además para proporcionar sincronización más sofisticado construye ... ejemplo: semáforos, etc.