Блокировка билетов - Ticket lock
В Информатика, а билетный замок это механизм синхронизации, или алгоритм блокировки, это тип спин-блокировка который использует "билеты", чтобы контролировать, какие нить исполнения разрешено войти в критическая секция.
Обзор
Основная концепция блокировки билетов аналогична системе управления очередью заявок. Это метод, который используют многие пекарни и гастрономы для обслуживания клиентов в порядке их прибытия, не заставляя их стоять в очереди. Как правило, существуют диспенсеры, из которых клиенты по прибытии берут последовательно пронумерованные билеты. Обычно над диспенсером или рядом с ним есть табличка с надписью «Возьмите номер». Также обычно есть динамический знак, обычно цифровой, который отображает номер билета, который сейчас обслуживается. Каждый раз, когда следующий номер билета (клиент) готов к обслуживанию, значок «Сейчас обслуживается» увеличивается и вызывается номер. Это позволяет всем ожидающим клиентам узнать, сколько человек еще впереди них в очереди или очереди.
Подобно этой системе, билетная блокировка - это первым пришел - первым ушел (FIFO) очередной механизм. Это добавляет преимущества справедливость приобретения замка и работает следующим образом; есть два целочисленных значения, которые начинаются с 0. Первое значение - это билет очереди, второе - билет удаления из очереди. Билет очереди - это позиция потока в очереди, а билет выхода из очереди - это билет или позиция в очереди, которая теперь имеет блокировку (Сейчас обслуживается).
Когда поток прибывает, он атомарно получает и затем увеличивает билет очереди. В атомарность этой операции требуется, чтобы два потока не могли одновременно получить один и тот же номер билета. Затем он сравнивает значение своего билета до приращения со значением искомого билета. Если они совпадают, потоку разрешается входить в критическую секцию. Если они не совпадают, то другой поток уже должен быть в критической секции, и этот поток должен занято-подожди или уступить. Когда поток покидает критическую секцию, управляемую блокировкой, он атомарно увеличивает билет удаления из очереди. Это позволяет следующему ожидающему потоку, имеющему следующий порядковый номер билета, войти в критическую секцию.[1]
Справедливость приобретения замка
Понятие справедливость При получении блокировки применяется к порядку, в котором потоки успешно получают блокировку.[2] Если реализован какой-то тип справедливости, он предотвращает запуск потока голодал из-за невозможности получить блокировку в пользу других потоков на долгое время. Без гарантий справедливости может возникнуть ситуация, когда поток (или несколько потоков) может занять непропорционально много времени для выполнения по сравнению с другими. Теперь будет представлен простой пример, чтобы показать, как поток может быть чрезмерно задержан из-за недостаточной справедливости получения блокировки.
Предположим, что три потока, каждый из которых выполняется на одном из трех процессоров, выполняют следующий псевдокод, который использует блокировку без учета справедливости.
в то время как (1) { замок { … критический раздел … } разблокировать}Теперь предположим, что физическое расположение трех процессоров, P1, P2 и P3, приводит к неравномерный доступ к памяти время до местоположения переменной разделяемой блокировки. Порядок увеличения времени доступа к переменной блокировки для трех процессоров: P1
| Время | P1 | P2 | P3 |
|---|---|---|---|
| 1 | попытка блокировки (успех) | попытка блокировки (неудачная) | попытка блокировки (неудачная) |
| 2 | критическая секция | вращение | вращение |
| 3 | разблокировать замок | попытка блокировки (успех) | попытка блокировки (неудачная) |
| 4 | ... | критическая секция | вращение |
| 5 | попытка блокировки (неудачная) | ... | ... |
| 6 | попытка блокировки (успех) | разблокировать замок | попытка блокировки (неудачная) |
| 7 | критическая секция | вращение | вращение |
| ... | ... | ... | ... |
Первоначально блокировка свободна, и все три процессора пытаются получить блокировку одновременно (время 1). Поскольку P1 имеет самое быстрое время доступа к замку, он первым его получает и входит в критическую секцию. P2 и P3 теперь вращаются, пока P1 находится в критической секции (время 2). После выхода из критической секции (Время 3) P1 выполняет разблокировку, снимая блокировку. Поскольку P2 имеет более быстрый доступ к блокировке, чем P3, он получает блокировку следующей и входит в критическую секцию (Time 4). Пока P2 находится в критической секции, P1 еще раз пытается получить блокировку, но не может (время 5), заставляя его ждать вращения вместе с P3. Как только P2 завершает критическую секцию и выдает разблокировку, оба P1 и P3 одновременно пытаются получить его еще раз (время 6). Но P1, с его более быстрым временем доступа, снова выигрывает, таким образом входя в критическую секцию (Time 7). Этот паттерн, когда P3 не может получить блокировку, будет продолжаться бесконечно, пока P1 или P2 не прекратят попытки получить ее.
Это иллюстрирует необходимость обеспечения определенного уровня справедливости при получении блокировки в определенных обстоятельствах. Не все блокировки имеют механизмы, обеспечивающие какой-либо уровень справедливости, что оставляет возможность для ситуаций, аналогичных показанной выше. Увидеть Сравнение замков в разделе ниже приведены примеры блокировок, которые не реализуют никаких гарантий справедливости.
Реализация блокировки билетов
В Неоднородная архитектура памяти (NUMA) системе важно иметь реализацию блокировки, которая гарантирует некоторый уровень справедливость приобретения замка. Блокировка билетов - это реализация спин-блокировка который добавляет этот желаемый атрибут. Следующий псевдокод[1][3] показывает операции для инициализации блокировки, получения блокировки и снятия блокировки. Вызов ticketLock_acquire будет предшествовать критическому разделу кода, а ticketLock_release последует за ним. Каждый процессор будет отслеживать свою очередь через значение my_ticket каждого процессора.
Пример псевдокода Яна Солихина приведен на диаграмме ниже.[1]
1 ticketLock_init(int *next_ticket, int *now_serving) 2 { 3 *now_serving = *next_ticket = 0; 4 } 5 6 ticketLock_acquire(int *next_ticket, int *now_serving) 7 { 8 my_ticket = fetch_and_inc(next_ticket); 9 в то время как (*now_serving != my_ticket) {}10 }11 12 ticketLock_release(int *now_serving)13 {14 ++*now_serving;15 }Следуя псевдокоду выше, мы видим, что каждый раз, когда процессор пытается получить блокировку с 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), конкурирующими за доступ к критической секции. Следуя столбцу «Действие», можно увидеть результат, основанный на приведенном выше псевдокоде. Для каждой строки показаны значения переменных. после указанное действие (я) завершено. Ключевым моментом, который следует отметить из этого примера, является то, что первоначальные попытки всех четырех процессоров получить блокировку приводят к тому, что только первый прибывший фактически получает блокировку. Все последующие попытки, пока первая все еще удерживает блокировку, служат для формирования очереди процессоров, ожидающих своей очереди в критической секции. После этого каждый по очереди получает замок, позволяя следующему в очереди получать его, когда предыдущий держатель уходит. Также обратите внимание, что другой процессор может прибыть в любой момент во время последовательности получения / снятия блокировки другими процессорами и просто ждет своей очереди.
| Ряд | Действие | next_ticket | now_serving | P1 my_ticket | P2 my_ticket | P3 my_ticket | P4 my_ticket |
|---|---|---|---|---|---|---|---|
| 1 | Инициализировано 0 | 0 | 0 | - | - | - | - |
| 2 | P1 пытается получить блокировку (успешно) | 1 | 0 | 0 | - | - | - |
| 3 | P3 пытается получить блокировку (ошибка + ожидание) | 2 | 0 | 0 | - | 1 | - |
| 4 | P2 пытается получить блокировку (сбой + ожидание) | 3 | 0 | 0 | 2 | 1 | - |
| 5 | P1 снимает блокировку, P3 получает блокировку | 3 | 1 | 0 | 2 | 1 | - |
| 6 | P3 снимает блокировку, P2 принимает блокировку | 3 | 2 | 0 | 2 | 1 | - |
| 7 | P4 пытается получить блокировку (ошибка + ожидание) | 4 | 2 | 0 | 2 | 1 | 3 |
| 8 | P2 снимает блокировку, P4 получает блокировку | 4 | 3 | 0 | 2 | 1 | 3 |
| 9 | P4 освобождает замок | 4 | 4 | 0 | 2 | 1 | 3 |
| 10 | ... | 4 | 4 | 0 | 2 | 1 | 3 |
Первым шагом перед использованием блокировки является инициализация всех переменных блокировки (строка 1). Инициализация next_ticket и now_serving равными 0 гарантирует, что первый поток, который попытается получить блокировку, получит билет 0, таким образом получив блокировку из-за того, что его билет соответствует now_serving. Поэтому, когда P1 пытается получить блокировку, он немедленно преуспевает, и next_ticket увеличивается до 1 (строка 2). Когда P3 пытается получить блокировку, он получает 1 для своего my_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 реализация может иметь меньшую задержку, чем более простая испытать и установить или обмен алгоритмы спин-блокировки на современных машинах. При сравнении различных типов замков на основе вращения обратите внимание на таблицу ниже. Более простые механизмы блокировки имеют меньшую неконтролируемую задержку, чем продвинутые механизмы блокировки.[1]
| Критерии | испытать и установить | Тест и тест-установка | Ссылка загрузки / магазин-условно | Билет | ABQL |
|---|---|---|---|---|---|
| Неконтролируемая задержка | Самый низкий | Нижняя | Нижняя | Высшее | Высшее |
| 1 Освободить максимальный трафик | Ө (п) | Ө (п) | Ө (п) | Ө (п) | Ө (1) |
| Ждать пробок | Высоко | - | - | - | - |
| Место хранения | Ө (1) | Ө (1) | Ө (1) | Ө (1) | Ө (п) |
| Гарантия справедливости | Нет | Нет | Нет | да | да |
Преимущества
- Одним из преимуществ блокировки билета перед другими алгоритмами спин-блокировки является то, что это честно. Ожидающие потоки обрабатываются в первым прибыл, первым обслужен по мере увеличения целого числа заявки на удаление из очереди, что предотвращает голодание.
- Алгоритм блокировки билетов также предотвращает проблема громового стада происходит, поскольку только один поток одновременно пытается войти в критическую секцию.
- Хранение не обязательно является проблемой, поскольку все потоки вращаются на одной переменной, в отличие от блокировки очередей на основе массивов (ABQL), у которых потоки вращаются на отдельных элементах массива.[1]
Недостатки
- Одним из недостатков является более высокая неконтролируемая задержка из-за дополнительных инструкций, необходимых для чтения и проверки значения, на котором вращаются все потоки, прежде чем блокировка будет снята.[1]
- Еще один серьезный недостаток блокировки билета заключается в том, что он не масштабируется. Исследования показали, что по мере добавления процессоров к системе Ticket Lock производительность, похоже, экспоненциально падает.[4]
- Еще одна проблема возникает из-за снятия блокировки. Все потоки вращаются на одной переменной, поэтому при снятии блокировки возникает Ө (p) недействительных (а также well (p) приобретений). Это связано с тем, что все потоки должны перезагрузить свой блок в кэш и выполнить тест, чтобы определить их доступность к критической секции.[1]
История
Блокировка билетов была введена Меллор-Крамми и Скоттом в 1991 году.[3] Этот алгоритм был введен в Ядро Linux в 2008 году благодаря своим преимуществам,[5] но был опущен в паравиртуализированный среды, где у него были недостатки.[6] По состоянию на июль 2010 г.[Обновить], ведется работа по включению блокировок билетов при паравиртуализации.[7] С марта 2015 года этот тип схемы блокировки был повторно использован Red Hat Enterprise Linux в своей системе.[8]
Связанных с работой
- Алгоритм пекарни Лампорта использует аналогичную концепцию «билета» или «счетчика», но не использует атомарные аппаратные операции. Он был разработан для обеспечения отказоустойчивости, а не производительности. Вместо того, чтобы все процессоры постоянно проверяли счетчик выпуска, блокировка пекарни вращается на проверке заявок своих сверстников.[3]
- Спин-блокировки на основе очереди гарантируют справедливость, поддерживая очередь официантов и предоставляя блокировку первому официанту во время операции разблокировки.[9]
Смотрите также
- получить и добавить, еще одна атомарная инструкция, которая может использоваться вместо выборки и увеличения для реализации блокировки билета.
использованная литература
- ^ а б c d е ж г час Солихин, Ян (2009). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы. Солихин Паб. С. 262–269. ISBN 978-0-9841630-0-7.
- ^ Соттиль, Мэтью Дж .; Маттсон, Тимоти Дж .; Расмуссен, Крейг Э. (28 сентября 2009 г.). Введение в параллелизм в языках программирования. Бока-Ратон, Флорида, США: CRC Press. п. 56. ISBN 978-1-4200-7214-3.
- ^ а б c d Джон М. Меллор-Крамми и Майкл Л. Скотт; и другие. (Февраль 1991 г.). «Алгоритмы масштабируемой синхронизации на мультипроцессорах с общей памятью». ACM TOCS.
- ^ Бойд-Викайзер, Сайлас и др. «Немасштабируемые блокировки опасны». Труды симпозиума по Linux. 2012 г. http://pdos.csail.mit.edu/papers/linux:lock.pdf
- ^ Джонатан Корбет, Спинлоки билетов, Linux Weekly News, 6 февраля 2008 г. Дата обращения 23 июля 2010 г.
- ^ Джереми Фицхардинг, paravirt: представьте реализацию спин-блокировки "байта блокировки", Ядро Linux, 7 июля 2008 г.
- ^ Вернуть "Объединить ветку 'xen / pvticketlock' в xen / next"
- ^ "Билетные замки".
- ^ Майкл Л. Скотт и Уильям Н. Шерер III. Масштабируемые спин-блокировки на основе очереди с тайм-аутом Труды восьмого симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, стр. 44-52, 2001.