В информатике блокировка тикетов — это механизм синхронизации или алгоритм блокировки , представляющий собой тип спин-блокировки , который использует «билеты» для управления тем, какому потоку выполнения разрешено входить в критическую секцию .
Основная концепция билетного замка похожа на систему управления очередью билетов. Это метод, который многие пекарни и гастрономы используют для обслуживания клиентов в порядке их прибытия, не заставляя их стоять в очереди. Обычно есть некий тип диспенсера, из которого клиенты по прибытии вытягивают последовательно пронумерованные билеты. Диспенсер обычно имеет знак над ним или рядом с ним, на котором написано что-то вроде «Пожалуйста, возьмите номер». Также обычно есть динамический знак, обычно цифровой, который отображает номер билета, который в данный момент обслуживается. Каждый раз, когда следующий номер билета (клиент) готов к обслуживанию, знак «Сейчас обслуживается» увеличивается и номер называется. Это позволяет всем ожидающим клиентам знать, сколько людей еще впереди них в очереди или очереди.
Как и эта система, блокировка тикета — это механизм на основе очереди «первым пришел — первым вышел» (FIFO) . Он добавляет преимущество справедливости получения блокировки и работает следующим образом: есть два целочисленных значения, которые начинаются с 0. Первое значение — это тикет очереди, второе — тикет снятия с очереди. Билет очереди — это позиция потока в очереди, а тикет снятия с очереди — это тикет или позиция очереди, которая теперь имеет блокировку (Now Serving).
Когда поток прибывает, он атомарно получает и затем увеличивает билет очереди. Атомарность этой операции необходима для того, чтобы два потока одновременно не смогли получить один и тот же номер билета. Затем он сравнивает свое значение билета, до увеличения, со значением билета из очереди. Если они одинаковы, потоку разрешается войти в критическую секцию. Если они не одинаковы, то другой поток должен уже находиться в критической секции, и этот поток должен находиться в состоянии ожидания или уступить. Когда поток покидает критическую секцию, контролируемую блокировкой, он атомарно увеличивает билет из очереди. Это позволяет следующему ожидающему потоку, имеющему следующий по порядку номер билета, войти в критическую секцию. [1]
Понятие справедливости в получении блокировки применяется к порядку, в котором потоки успешно получают блокировку. [2] Если реализован какой-либо тип справедливости, он предотвращает длительную задержку выполнения потока из-за невозможности получить блокировку в пользу других потоков. При отсутствии гарантий справедливости может возникнуть ситуация, когда поток (или несколько потоков) могут выполняться непропорционально долго по сравнению с другими. Сейчас будет представлен простой пример, показывающий, как поток может быть чрезмерно задержан из-за отсутствия справедливости в получении блокировки.
Предположим случай, когда три потока, каждый из которых выполняется на одном из трех процессоров, выполняют следующий псевдокод, который использует блокировку без учета принципа справедливости.
в то время как ( 1 ) { блокировка { … критическая секция … } разблокировка } Теперь предположим далее, что физическое расположение трех процессоров, P1, P2 и P3, приводит к неравномерному времени доступа к памяти для расположения общей переменной блокировки. Порядок увеличения времени доступа к переменной блокировки для трех процессоров: P1 < P2 < P3. Таким образом, P1 всегда имеет наибольшее преимущество при получении блокировки, за ним следует P2, а P3 находится в наиболее невыгодном положении. То, как эта ситуация приводит к голоданию потока при отсутствии гарантии справедливости, показано на следующей иллюстрации выполнения приведенного выше псевдокода этими тремя процессорами.
Изначально блокировка свободна, и все три процессора пытаются получить блокировку одновременно (время 1). Поскольку P1 имеет самое быстрое время доступа к блокировке, он получает ее первым и входит в критическую секцию. P2 и P3 теперь вращаются, пока P1 находится в критической секции (время 2). После выхода из критической секции (время 3) P1 выполняет разблокировку, снимая блокировку. Поскольку P2 имеет более быстрый доступ к блокировке, чем P3, он получает блокировку следующим и входит в критическую секцию (время 4). Пока P2 находится в критической секции, P1 снова пытается получить блокировку, но не может (время 5), заставляя его ждать вместе с P3. Как только P2 заканчивает критическую секцию и выдает разблокировку, P1 и P3 одновременно пытаются получить ее еще раз (время 6). Но P1, с его более быстрым временем доступа, снова побеждает, таким образом входя в критическую секцию (время 7). Такая ситуация, когда P3 не может получить блокировку, будет продолжаться бесконечно, пока P1 или P2 не прекратят попытки ее получить.
Это иллюстрирует необходимость обеспечения некоторого уровня справедливости при получении блокировки в определенных обстоятельствах. Не все замки имеют механизмы, которые обеспечивают какой-либо уровень справедливости, что оставляет возможность для ситуаций, подобных проиллюстрированной выше. См. раздел Сравнение замков ниже для примеров замков, которые не реализуют никаких гарантий справедливости.
В системе с неоднородной архитектурой памяти (NUMA) важно иметь реализацию блокировки, которая гарантирует определенный уровень справедливости получения блокировки. Блокировка билета — это реализация спин-блокировки , которая добавляет этот желаемый атрибут. Следующий псевдокод [1] [3] показывает операции для инициализации блокировки, получения блокировки и снятия блокировки. Вызов ticketLock_acquire будет предшествовать критическому разделу кода, а ticketLock_release будет следовать за ним. Каждый процессор будет отслеживать свой ход с помощью значения my_ticket каждого процессора.
Пример псевдокода Яна Солихина представлен на диаграмме ниже. [1]
ticketLock_init ( int * next_ticket , int * now_serving ) { * now_serving = * next_ticket = 0 ; }ticketLock_acquire ( int * next_ticket , int * now_serving ) { my_ticket = fetch_and_inc ( next_ticket ); пока ( * now_serving != my_ticket ) {} }ticketLock_release ( int * now_serving ) { +++ сейчас_обслуживается ;}Следуя псевдокоду выше, мы видим, что каждый раз, когда процессор пытается получить блокировку с помощью ticketLock_acquire(), вызывается fetch_and_inc , возвращая текущее значение next_ticket в закрытый поток my_ticket и увеличивая общий next_ticket. Важно отметить, что выборка и увеличение выполняются атомарно, тем самым не допуская никаких других одновременных попыток доступа. После получения my_ticket каждый поток будет вращаться в цикле while, пока now_serving не будет равен его my_ticket. Как только now_serving станет равным my_ticket данного потока, им будет разрешено вернуться из ticketLock_acquire() и войти в критическую секцию кода. После критической секции кода поток выполняет ticketLock_release(), который увеличивает now_serving. Это позволяет потоку со следующим по порядку my_ticket выйти из ticketLock_acquire() и войти в критическую секцию. [3] Поскольку значения my_ticket приобретаются в порядке прибытия потока к замку, последующее приобретение замка гарантированно будет в том же порядке. Таким образом, обеспечивается справедливость приобретения замка, что обеспечивает упорядочение FIFO.
В следующей таблице показан пример блокировки билета в действии в системе с четырьмя процессорами (P1, P2, P3, P4), конкурирующими за доступ к критическому разделу. Следуя за столбцом «Действие», можно наблюдать результат, основанный на приведенном выше псевдокоде. Для каждой строки показаны значения переменных после завершения указанных действий. Ключевой момент, который следует отметить в примере, заключается в том, что начальные попытки всех четырех процессоров получить блокировку приводят к тому, что только первый прибывший фактически получает блокировку. Все последующие попытки, пока первый все еще удерживает блокировку, служат для формирования очереди процессоров, ожидающих своей очереди в критическом разделе. Затем каждый получает блокировку по очереди, позволяя следующему в очереди получить ее, поскольку предыдущий держатель уходит. Также обратите внимание, что другой процессор может прибыть в любое время во время последовательности получения/снятия блокировки другими процессорами и просто ждет своей очереди.
Первый шаг, перед использованием блокировки, — это инициализация всех переменных блокировки (строка 1). Инициализация next_ticket и now_serving в 0 гарантирует, что первый поток, который попытается получить блокировку, получит билет 0, таким образом, приобретя блокировку из-за того, что его билет соответствует now_serving. Таким образом, когда P1 пытается получить блокировку, он немедленно преуспевает, и next_ticket увеличивается до 1 (строка 2). Когда P3 пытается получить блокировку, он получает 1 для своего my_ticket, next ticket увеличивается до 2, и он должен ждать, так как now_serving по-прежнему равен 0 (строка 3). Затем, когда P2 пытается получить блокировку, он получает 2 для своего my_ticket, next_ticket увеличивается до 3, и он также должен ждать, так как now_serving по-прежнему равен 0 (строка 4). P1 теперь снимает блокировку, увеличивая now_serving до 1, тем самым позволяя P3 получить ее из-за его значения my_ticket, равного 1 (строка 5). Теперь P3 снимает блокировку, увеличивая now_serving до 2, позволяя P2 получить ее (строка 6). Пока P2 имеет блокировку, P4 пытается ее получить, получает значение my_ticket, равное 3, увеличивает next_ticket до 4 и должен ждать, поскольку now_serving по-прежнему равно 2 (строка 7). Когда P2 снимает блокировку, он увеличивает now_serving до 3, позволяя P4 получить ее (строка 8). Наконец, P4 снимает блокировку, увеличивая now_serving до 4 (строка 9). Ни один из ожидающих в данный момент потоков не имеет этого номера тикета, поэтому следующий прибывший поток получит 4 для своего тикета и немедленно получит блокировку.
Реализация ядра Linux может иметь меньшую задержку, чем более простые алгоритмы спин-блокировки test-and-set или exchange на современных машинах. Рассмотрите таблицу ниже при сравнении различных типов спин-блокировок. Более базовые механизмы блокировки имеют меньшую неконкурентную задержку, чем продвинутые механизмы блокировки. [1]
Блокировка тикетов была введена Меллором-Крамми и Скоттом в 1991 году. [3] Этот алгоритм был введен в ядро Linux в 2008 году из-за его преимуществ, [5] но был исключен из паравиртуализированных сред, где имел недостатки. [6] По состоянию на июль 2010 года [обновлять]ведется работа по включению использования блокировок тикетов в паравиртуализации. [7] По состоянию на март 2015 года этот тип схемы блокировки был повторно использован Red Hat Enterprise Linux в своей системе. [8]