En informática , la serialización de tokens es un concepto de control de concurrencia que surge del desarrollo continuo de DragonFly BSD . Según Matthew Dillon , son más parecidos a los SPL , excepto que un token funciona en varias CPU, mientras que los SPL solo funcionan dentro del dominio de una sola CPU.
Los tokens de serialización permiten a los programadores escribir código multiprocesador seguro sin que ellos mismos o los subsistemas de nivel inferior necesiten estar al tanto de cada entidad que también puede tener el mismo token.
Comparación con exclusión mutua (mutex)
Los tokens y los mecanismos de exclusión mutua (mutex) son bloqueos . A diferencia de los mutex, los tokens no excluyen que otros subprocesos accedan al recurso mientras están bloqueados o inactivos. Un hilo que comparte recursos con otros hilos se puede detener e iniciar por una variedad de razones:
- Timeslicing: el programador del espacio de usuario (EE. UU.) Intenta asegurarse de que todos los subprocesos tengan una oportunidad justa de ejecutarse, por lo que ejecuta cada subproceso durante un breve período de tiempo (un intervalo de tiempo) y luego cambia a otro subproceso.
- Ejecución concurrente: en computadoras multiprocesador, un subproceso puede ejecutarse exactamente al mismo tiempo que otro subproceso en una CPU diferente.
- Preferencia: un hilo puede adelantarse a un hilo de menor prioridad, como una interrupción de hardware o hilos de kernel livianos .
- Bloqueo voluntario: un hilo puede dormir si tiene que esperar por algo, no tiene trabajo que hacer o llama a una función que bloquea. Incluso la llamada para adquirir un candado puede bloquearse.
La siguiente tabla resume las propiedades de los tokens y las exclusiones mutuas.
Serializar tokens | Mutexes | |
---|---|---|
Timeslicing | Obras | Obras |
Ejecución concurrente | Obras | Obras |
Derecho preferente de compra | Obras | Obras |
Bloqueo voluntario | Falla | Obras |
Evita el estancamiento | sí | No |
Evita la inversión de prioridades | sí | No |
Problemas como el punto muerto y la inversión de prioridades pueden ser muy difíciles de evitar y requieren coordinación en muchos niveles del kernel. Debido a que el bloqueo con tokens no tiene un punto muerto y los tokens adquiridos no necesitan ser atómicos cuando se bloquean operaciones posteriores, permite un código mucho más simple que los mutex.
... Si observa FreeBSD-5, notará que FreeBSD-5 pasa con mutex en la pila de subrutinas con bastante frecuencia, para permitir que un nivel de procedimiento muy profundo libere temporalmente un mutex para cambiar, bloquear o negociar con un punto muerto. Hay una gran cantidad de contaminación de código en FreeBSD-5 debido a esto (donde algunos procedimientos deben conocer las exclusiones mutuas de otros procedimientos no relacionados para que funcionen correctamente).
- Matthew Dillon
Ejemplo
El siguiente pseudocódigo y explicaciones ilustran cómo funciona la serialización de tokens.
Hilo A | Hilo B | Acción |
---|---|---|
lwkt_gettoken (T1);iter = list1.head; | ...lwkt_gettoken (T1); // bloques// esperando el token T1 | A adquiere el token T1 y lo usa para obtener acceso sincronizado a list1, que es compartido por ambos hilos. |
lwkt_gettoken (T2); // bloques | // esperando el token T1 | La llamada de A a lwkt_gettoken (T2) es una función de bloqueo, por lo que A se queda dormido y pierde temporalmente sus tokens. Se despertará cuando el programador vea que tanto T1 como T2 están disponibles. |
// esperando T1 y T2 | list1.head = list1.head.next;lwkt_releasetoken (T1); | B adquiere T1 y modifica list1. Tenga en cuenta que el "iter" de A todavía apunta al antiguo encabezado de la lista. |
// obtén la nueva versión de la cabeza:iter = list1.head; // hacer una nueva lista:while (iter! = null) { list2.tail = iter; iter = iter.next;}lwkt_releasetoken (T1);lwkt_releasetoken (T2); | El planificador ve que tanto T1 como T2 están disponibles, por lo que despierta el subproceso A. Dado que A se codificó correctamente, actualiza su iterador con el nuevo encabezado de list1 y realiza algunas operaciones de no bloqueo en él. Tenga en cuenta que habría sido mejor que A simplemente pidiera ambos tokens al principio. |
Técnica anterior en el kernel de Darwin
Mac OS X 's Darwin núcleo utiliza una técnica similar (llamado un embudo ) para serializar el acceso a la BSD porción del núcleo.