Блог им. aspotashevTicket spinlock

Ticket spinlock — это реализация спинлока в ядре Linux, гарантирующая FCFS-порядок входа в критическую секцию.

А теперь разберёмся, как он работает…
Для начала нужно знать, что такое spinlock: Спинлок — это средство синхронизации, предназначенное для предотвращения выполнения некой критической секции на нескольких процессорах одновременно.
Пример использования:
spin_lock(&lock);
<... критическая секция ...>
spin_unlock(&lock);

При «взятии» спинлока первым делом на процессоре запрещается переключение задач.
Если какой-то процессор уже «взял» спинлок (то есть выполнил spin_lock), то все остальные при попытке взятия того же спинлока будут крутиться в цикле, ожидая «отпускания» спинлока. Когда спинлок всё-таки будет отпущен, только один процессор сможет сразу же войти в критическую секцию, а остальные будут продолжать ждать.

До версии 2.6.25 в ядре Linux обычный spinlock состоял из одного целого числа (1=свободен, 0=занят). Его недостаток в том, что он «нечестный», то есть какой-нибудь процессор может очень долго не получать права входа в критическую секцию, даже если он ждал дольше всех. А непропорционально длинная задержка в некоторых случаях может быть недопустимой.

В версии 2.6.25 был добавлен так называемый "Ticket spinlock". Логика его работы точно такая же, как при организации виртуальной очереди. Под виртуальной очередью понимается следующее: в учреждение приходит новый клиент, берет «билетик» (ticket) с номером и ждёт, пока его не вызовут по этому номеру. Клиенты вызываются в том же порядке, в котором они зашли (то есть FCFS). Лично я такую виртуальную очередь наблюдал в одном из офисов Social Security и в одном из отделений Сбербанка.

В нашей критической секции может находиться только один процессор, это эквивалентно тому, что в учреждении есть только одно окно, в котором могут обслуживать клиентов. Для наглядности скажем, что в учреждении есть табло, на котором высвечивается номер клиента, которого сейчас готовы принять. Если окно занято обслуживанием клиента, то, очевидно, номер этого клиента совпадает с номером на табло.

Ticket spinlock в Linux, вообще говоря, состоит из двух байт памяти (кроме случаев, когда у Вас больше 256 процессоров — тогда используются две двухбайтовые ячейки):

В терминологии виртуальной очереди Next — это номер, который будет выдан следующему клиенту (но ещё не был выдан), а Owner — это номер на табло.

Изначально, то есть сразу после инициализации спинлока, в ячейках лежат нули. Это означает, что, если мы ещё никого не обслуживаем, то первый вошедший клиент получит номер 0, увидит свой номер на табло и сразу же пойдёт к окну.

Когда новый клиент берет билет и начинает ждать (что эквивалентно выполнению spin_lock), процессору нужно запомнить Next в своём регистре, увеличить Next на единицу и ждать, пока число, сохранённое в регистре, не станет равным Owner.

После того, как клиент сделает свои дела (spin_unlock), нужно всего лишь увеличить Owner на единицу, то есть пустить следующего.

P.S. Погуглив «MSDN Queued Spin Locks», я узнал, что такое queued spinlock. Он требует больше памяти, чем обычный spinlock, но ходят слухи, что работает быстрее. А что могут сказать по этому поводу знатоки ReactOS и его дешёвых аналогов?

Литература:
1. Ticket spinlocks [LWN.net]
2. Внутреннее устройство ядра Linux: Синхронизация
3. Multiprocessor OSs & Synchronization
4. MSDN: Queued Spin Locks
5. Spinlocks benchmark

Комментарии (4)

  • avatar
  • eReS
  • 25 октября 2009, 22:13
  • #
  • 2
> Ticket spinlock — это реализация спинлока в ядре Linux, гарантирующая FIFO-порядок входа в критическую секцию.

Можно по подробнее, зачем ето нужно и где используется? На серверах?
Извините за глупый вопрос, заинтересовало…
Если несколько процессоров имеют возможность одновременного доступа к одной области памяти, нельзя давать им возможности что-либо делать с этой памятью, не задумываясь о действиях других процессоров.

Например, 2 процесса в ядре одновременно выполняются на 2-х разных процессорах (или процессорных ядрах) и периодически добавляют новые элементы в начало односвязного списка. Для добавления элемента в односвязный список нужно изменить 2 указателя:
new_item->next = after->next;
after->next = new_item;

Здесь new_item — указатель на добавляемый элемент списка, after — указатель на элемент, за которым пойдет в списке новый элемент.

Может так совпасть, что оба процессора попытаются одновременно добавить разные элементы после какого-то одного. То есть сначала оба процессора установят new_item->next в одинаковое значение — after->next (указатель на элемент, следовавший за after до добавления новых элементов). Второй операцией оба процессора попытаются записать в одну ячейку new_item->next разные указатели, но, конечно же, останется записанным только одно.

Что мы видим: за after теперь следует один из новых элементов, а за ним следует элемент, который раньше следовал за after. То есть мы добавили только один из двух элементов, неожиданно? К тому же элементы будут исчезать не когда нам захочется, а случайно, то есть если «повезёт» или «не повезёт».

Чтобы элементы добавлялись правильно, нужно сделать операцию добавления элемента атомарной. Атомарность как раз достигается «оборачиванием» этой составной операции парой spin_lock/spin_unlock.
Возможно, я ещё не ответил на вопрос. Спинлоки используются во всех разумных операционных системах (ядрах), работающих на многопроцессорных системах и использующих эту многопроцессорность.

Если компьютер однопроцессорный или ядро не поддерживает многопроцессорность, спинлоки нет смысла использовать, потому что нет других процессоров, которые могут «влезть» и что-то испортить.
Уточнение: на однопроцессорной системе захват спинлока сводится к запрету переключения задач, в противном случае могут быть конфликты доступа из разных потоков.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.