Блог им. aspotashev → Ticket spinlock
Ticket spinlock — это реализация спинлока в ядре Linux, гарантирующая -порядок входа в критическую секцию.
А теперь разберёмся, как он работает…
Для начала нужно знать, что такое spinlock: Спинлок — это средство синхронизации, предназначенное для предотвращения выполнения некой критической секции на нескольких процессорах одновременно.
Пример использования:
При «взятии» спинлока первым делом на процессоре запрещается переключение задач.
Если какой-то процессор уже «взял» спинлок (то есть выполнил spin_lock), то все остальные при попытке взятия того же спинлока будут крутиться в цикле, ожидая «отпускания» спинлока. Когда спинлок всё-таки будет отпущен, только один процессор сможет сразу же войти в критическую секцию, а остальные будут продолжать ждать.
До версии 2.6.25 в ядре Linux обычный spinlock состоял из одного целого числа (1=свободен, 0=занят). Его недостаток в том, что он «нечестный», то есть какой-нибудь процессор может очень долго не получать права входа в критическую секцию, даже если он ждал дольше всех. А непропорционально длинная задержка в некоторых случаях может быть недопустимой.
В версии 2.6.25 был добавлен так называемый "Ticket spinlock". Логика его работы точно такая же, как при организации . Под виртуальной очередью понимается следующее: в учреждение приходит новый клиент, берет «билетик» (ticket) с номером и ждёт, пока его не вызовут по этому номеру. Клиенты вызываются в том же порядке, в котором они зашли (то есть ). Лично я такую виртуальную очередь наблюдал в одном из офисов 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.
2.
3.
4.
5.
А теперь разберёмся, как он работает…
Для начала нужно знать, что такое spinlock: Спинлок — это средство синхронизации, предназначенное для предотвращения выполнения некой критической секции на нескольких процессорах одновременно.
Пример использования:
spin_lock(&lock);
<... критическая секция ...>
spin_unlock(&lock);
При «взятии» спинлока первым делом на процессоре запрещается переключение задач.
Если какой-то процессор уже «взял» спинлок (то есть выполнил spin_lock), то все остальные при попытке взятия того же спинлока будут крутиться в цикле, ожидая «отпускания» спинлока. Когда спинлок всё-таки будет отпущен, только один процессор сможет сразу же войти в критическую секцию, а остальные будут продолжать ждать.
До версии 2.6.25 в ядре Linux обычный spinlock состоял из одного целого числа (1=свободен, 0=занят). Его недостаток в том, что он «нечестный», то есть какой-нибудь процессор может очень долго не получать права входа в критическую секцию, даже если он ждал дольше всех. А непропорционально длинная задержка в некоторых случаях может быть недопустимой.
В версии 2.6.25 был добавлен так называемый "Ticket spinlock". Логика его работы точно такая же, как при организации . Под виртуальной очередью понимается следующее: в учреждение приходит новый клиент, берет «билетик» (ticket) с номером и ждёт, пока его не вызовут по этому номеру. Клиенты вызываются в том же порядке, в котором они зашли (то есть ). Лично я такую виртуальную очередь наблюдал в одном из офисов 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.
2.
3.
4.
5.
- +9
- aspotashev
- 25 октября 2009, 19:26
Можно по подробнее, зачем ето нужно и где используется? На серверах?
Извините за глупый вопрос, заинтересовало…
Например, 2 процесса в ядре одновременно выполняются на 2-х разных процессорах (или процессорных ядрах) и периодически добавляют новые элементы в начало односвязного . Для добавления элемента в односвязный список нужно изменить 2 указателя:
Здесь new_item — указатель на добавляемый элемент списка, after — указатель на элемент, за которым пойдет в списке новый элемент.
Может так совпасть, что оба процессора попытаются одновременно добавить разные элементы после какого-то одного. То есть сначала оба процессора установят new_item->next в одинаковое значение — after->next (указатель на элемент, следовавший за after до добавления новых элементов). Второй операцией оба процессора попытаются записать в одну ячейку new_item->next разные указатели, но, конечно же, останется записанным только одно.
Что мы видим: за after теперь следует один из новых элементов, а за ним следует элемент, который раньше следовал за after. То есть мы добавили только один из двух элементов, неожиданно? К тому же элементы будут исчезать не когда нам захочется, а случайно, то есть если «повезёт» или «не повезёт».
Чтобы элементы добавлялись правильно, нужно сделать операцию добавления элемента . Атомарность как раз достигается «оборачиванием» этой составной операции парой spin_lock/spin_unlock.
Если компьютер однопроцессорный или ядро не поддерживает многопроцессорность, спинлоки нет смысла использовать, потому что нет других процессоров, которые могут «влезть» и что-то испортить.