En informática , un bloqueo de tickets es un mecanismo de sincronización, o algoritmo de bloqueo , que es un tipo de spinlock que utiliza "tickets" para controlar qué hilo de ejecución puede entrar en una sección crítica .
El concepto básico de un sistema de gestión de colas de tickets es similar al del sistema de gestión de colas de tickets. Este es el método que utilizan muchas panaderías y tiendas de delicatessen para atender a los clientes en el orden en que llegan, sin hacerlos hacer cola. Generalmente, hay algún tipo de dispensador del que los clientes sacan tickets numerados secuencialmente al llegar. El dispensador suele tener un cartel encima o cerca que dice algo como "Tome un número". También suele haber un cartel dinámico, normalmente digital, que muestra el número de ticket que se está atendiendo en ese momento. Cada vez que el siguiente número de ticket (cliente) está listo para ser atendido, el cartel de "Ahora atendiendo" se incrementa y se anuncia el número. Esto permite que todos los clientes que esperan sepan cuántas personas todavía están delante de ellos en la cola o fila.
Al igual que este sistema, un bloqueo de ticket es un mecanismo basado en colas FIFO (primero en entrar, primero en salir) . Agrega el beneficio de la equidad de la adquisición de bloqueos y funciona de la siguiente manera: hay dos valores enteros que comienzan en 0. El primer valor es el ticket de la cola, el segundo es el ticket de salida de la cola. El ticket de la cola es la posición del hilo en la cola, y el ticket de salida de la cola es el ticket, o la posición de la cola, que ahora tiene el bloqueo (Ahora en servicio).
Cuando llega un hilo, obtiene de forma atómica el ticket de la cola y luego lo incrementa. La atomicidad de esta operación es necesaria para evitar que dos hilos puedan obtener simultáneamente el mismo número de ticket. Luego compara su valor de ticket, antes del incremento, con el valor del ticket de la cola. Si son iguales, el hilo puede entrar en la sección crítica. Si no son iguales, entonces otro hilo ya debe estar en la sección crítica y este hilo debe esperar o ceder. Cuando un hilo sale de la sección crítica controlada por el bloqueo, incrementa de forma atómica el ticket de la cola. Esto permite que el siguiente hilo en espera, el que tenga el siguiente número de ticket secuencial, entre en la sección crítica. [1]
El concepto de equidad en la adquisición de bloqueos se aplica al orden en el que los subprocesos adquieren un bloqueo con éxito. [2] Si se implementa algún tipo de equidad, se evita que un subproceso quede inactivo durante mucho tiempo debido a la incapacidad de adquirir un bloqueo en favor de otros subprocesos. Sin garantías de equidad, puede surgir una situación en la que un subproceso (o varios subprocesos) pueden tardar un tiempo desproporcionadamente largo en ejecutarse en comparación con otros. A continuación, se presentará un ejemplo sencillo para mostrar cómo un subproceso podría retrasarse excesivamente debido a una falta de equidad en la adquisición de bloqueos.
Supongamos un caso en el que tres subprocesos, cada uno de los cuales se ejecuta en uno de tres procesadores, ejecutan el siguiente pseudocódigo que utiliza un bloqueo sin tener en cuenta la imparcialidad.
mientras ( 1 ) { bloquear { … sección crítica … } desbloquear } Supongamos ahora que la disposición física de los tres procesadores, P1, P2 y P3, da como resultado un tiempo de acceso a la memoria no uniforme a la ubicación de la variable de bloqueo compartida. El orden de aumento del tiempo de acceso a la variable de bloqueo para los tres procesadores es P1 < P2 < P3. Por lo tanto, P1 siempre es el más favorecido a la hora de adquirir el bloqueo, seguido de P2, y P3 es el más desfavorecido. La siguiente ilustración de la ejecución del pseudocódigo anterior por parte de estos tres procesadores muestra cómo esta situación conduce a la inanición de subprocesos en ausencia de una garantía de imparcialidad.
Inicialmente, la cerradura está libre y los tres procesadores intentan adquirir la cerradura simultáneamente (Tiempo 1). Debido a que P1 tiene el tiempo de acceso más rápido a la cerradura, la adquiere primero y entra en la sección crítica. P2 y P3 ahora giran mientras P1 está en la sección crítica (Tiempo 2). Al salir de la sección crítica (Tiempo 3), P1 ejecuta un desbloqueo, liberando la cerradura. Como P2 tiene un acceso más rápido a la cerradura que P3, adquiere la cerradura a continuación y entra en la sección crítica (Tiempo 4). Mientras P2 está en la sección crítica, P1 intenta adquirir la cerradura una vez más, pero no puede (Tiempo 5), lo que lo obliga a girar y esperar junto con P3. Una vez que P2 termina la sección crítica y emite un desbloqueo, tanto P1 como P3 intentan adquirirla simultáneamente una vez más (Tiempo 6). Pero P1, con su tiempo de acceso más rápido, gana nuevamente, ingresando así a la sección crítica (Tiempo 7). Este patrón de P3 siendo incapaz de obtener el bloqueo continuará indefinidamente hasta que P1 o P2 dejen de intentar adquirirlo.
Esto ilustra la necesidad de garantizar cierto nivel de imparcialidad en la adquisición de bloqueos en determinadas circunstancias. No todos los bloqueos tienen mecanismos que garanticen algún nivel de imparcialidad, lo que deja abierta la posibilidad de situaciones similares a la ilustrada anteriormente. Consulte la sección Comparación de bloqueos a continuación para ver ejemplos de bloqueos que no implementan ninguna garantía de imparcialidad.
En un sistema de arquitectura de memoria no uniforme (NUMA) es importante tener una implementación de bloqueo que garantice cierto nivel de equidad en la adquisición de bloqueo. El bloqueo de ticket es una implementación de spinlock que agrega este atributo deseado. El siguiente pseudocódigo [1] [3] muestra las operaciones para inicializar el bloqueo, adquirir el bloqueo y liberarlo. Una llamada a ticketLock_acquire precedería a la sección crítica del código y ticketLock_release la seguiría. Cada procesador mantendrá un registro de su turno a través del valor de my_ticket de cada procesador.
El ejemplo de pseudocódigo de Yan Solihin se muestra en el diagrama siguiente. [1]
ticketLock_init ( int * próximo_ticket , int * ahora_servido ) { * ahora_servido = * próximo_ticket = 0 ; }ticketLock_adquirir ( int * próximo_ticket , int * ahora_servido ) { mi_boleto = fetch_and_inc ( próximo_boleto ); mientras ( * ahora_servido != mi_ticket ) {} }ticketLock_release ( int * ahora_servido ) { +++ ahora_servido ;}Siguiendo el pseudocódigo anterior, podemos ver que cada vez que un procesador intenta adquirir un bloqueo con ticketLock_acquire(), se llama a fetch_and_inc , que devuelve el valor actual de next_ticket al hilo privado my_ticket e incrementa el next_ticket compartido. Es importante tener en cuenta que la búsqueda y el incremento se realizan de forma atómica, por lo que no se permiten otros intentos de acceso simultáneos. Una vez que se ha recibido my_ticket, cada hilo girará en el bucle while mientras now_serving no sea igual a su my_ticket. Una vez que now_serving se vuelve igual al my_ticket de un hilo determinado, se les permite regresar desde ticketLock_acquire() e ingresar a la sección crítica del código. Después de la sección crítica del código, el hilo realiza ticketLock_release() que incrementa now_serving. Esto permite que el hilo con el siguiente my_ticket secuencial salga de ticketLock_acquire() e ingrese a la sección crítica. [3] Dado que los valores de my_ticket se adquieren en el orden en que el hilo llega al bloqueo, se garantiza que la adquisición posterior del bloqueo también se realice en este mismo orden. Por lo tanto, se garantiza la imparcialidad de la adquisición del bloqueo, lo que aplica un orden FIFO.
La siguiente tabla muestra un ejemplo de bloqueo de ticket en acción en un sistema con cuatro procesadores (P1, P2, P3, P4) que compiten por el acceso a la sección crítica. Siguiendo con la columna "Acción", se puede observar el resultado basado en el pseudocódigo anterior. Para cada fila, los valores de las variables que se muestran son los que se obtienen después de que se hayan completado las acciones indicadas. El punto clave que se debe tener en cuenta en el ejemplo es que los intentos iniciales de los cuatro procesadores para adquirir el bloqueo dan como resultado que solo el primero en llegar lo consiga. Todos los intentos posteriores, mientras el primero aún mantiene el bloqueo, sirven para formar la cola de procesadores que esperan su turno en la sección crítica. A continuación, cada uno obtiene el bloqueo por turno, lo que permite que el siguiente en la fila lo adquiera cuando el titular anterior se va. Observe también que otro procesador puede llegar en cualquier momento durante la secuencia de adquisición/liberación de bloqueos por parte de otros procesadores, y simplemente espera su turno.
El primer paso, antes de utilizar el bloqueo, es la inicialización de todas las variables de bloqueo (Fila 1). Tener next_ticket y now_serving inicializados a 0 garantiza que el primer hilo que intente obtener el bloqueo obtendrá el ticket 0, adquiriendo así el bloqueo debido a que su ticket coincide con now_serving. Entonces, cuando P1 intenta adquirir el bloqueo, lo logra inmediatamente y next_ticket se incrementa a 1 (Fila 2). Cuando P3 intenta adquirir el bloqueo, obtiene 1 para su my_ticket, next_ticket se incrementa a 2 y debe esperar ya que now_serving sigue siendo 0 (Fila 3). A continuación, cuando P2 intenta adquirir el bloqueo, obtiene 2 para su my_ticket, next_ticket se incrementa a 3 y también debe esperar debido a que now_serving sigue siendo 0 (Fila 4). P1 ahora libera el bloqueo incrementando now_serving a 1, lo que permite a P3 adquirirlo debido a que su valor my_ticket es 1 (Fila 5). Ahora P3 libera el bloqueo, incrementando now_serving a 2, lo que permite que P2 lo adquiera (Fila 6). Mientras P2 tiene el bloqueo, P4 intenta adquirirlo, obtiene un valor de my_ticket de 3, incrementa next_ticket a 4 y debe esperar ya que now_serving sigue siendo 2 (Fila 7). Cuando P2 libera el bloqueo, incrementa now_serving a 3, lo que permite que P4 lo obtenga (Fila 8). Finalmente, P4 libera el bloqueo, incrementando now_serving a 4 (Fila 9). Ningún subproceso que esté esperando actualmente tiene este número de ticket, por lo que el próximo subproceso que llegue obtendrá 4 para su ticket y adquirirá el bloqueo de inmediato.
La implementación del kernel de Linux puede tener una latencia menor que los algoritmos de bloqueo de giro basados en pruebas y configuraciones o intercambio más simples en las máquinas modernas. Considere la tabla a continuación al comparar varios tipos de bloqueos basados en giros. Los mecanismos de bloqueo más básicos tienen una latencia sin contención menor que los mecanismos de bloqueo avanzados. [1]
El bloqueo de tickets fue introducido por Mellor-Crummey y Scott en 1991. [3] Este algoritmo fue introducido en el kernel de Linux en 2008 debido a sus ventajas, [5] pero fue omitido en entornos paravirtualizados donde tenía desventajas. [6] A partir de julio de 2010 [actualizar], se está trabajando para permitir el uso de bloqueos de tickets en la paravirtualización. [7] A partir de marzo de 2015, este tipo de esquema de bloqueo ha sido reutilizado por Red Hat Enterprise Linux en su sistema. [8]