Методы синхронизации и блокировки в Linux ядре

Вы тоже работаете на IBM?

ЛОР - подразделение IBM! ;-)

Статья отстой. С таким же успехом можно открыть книжку по POSIX-нитям и узнать тоже самое. Перечисленные в статье механизмы используются повсюды. А вот необщепринятые механизмы синхронизации, которые используются в ядре (например, RCU) в статье-то как раз и не описаны.

А чем это лучше соответствующего раздела у Р. Лава?

А ведь можно написать ядро без критических секций и блокировок. Спорим?

однозадачное ;)

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

s/Многозодачное/Многозадачное/

Что, дико звучит, что ядро параллелится? Небось, привыкли что ядро исполняется в кванте времени задачи, которая вызвала syscall или в контексте прерывания? Пора отвыкать. В частном случае, прерывание и есть программный поток, который блокирован до прихода сообщения. Например, прерывания.

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

а мужики-то и не знают!...

> а мужики-то и не знают!..

Какая из систем не использует мютексы, критические секции и спинлоки в ядре?

>Какая из систем не использует мютексы, критические секции и спинлоки в ядре?

M$ DOS ? ;)

> Потоки обмениваются синхронными сообщениями.

В первом приближении у тебя будет блокировка в очереди сообщений, хотя если очень постараться, то очередь можно написать lock-free. Но очередь сообщений сосет, так как она плоха укладывается в идею real-time.

> M$ DOS ? ;)

Вообще-то да :)

> В первом приближении у тебя будет блокировка в очереди сообщений, хотя если очень постараться, то очередь можно написать lock-free. Но очередь сообщений сосет, так как она плоха укладывается в идею real-time.

И да и нет. Попробую пояснить. Да - насчёт блокировки. Тут надо сильно постараться в момент дизайна системы. Блокировки разруливаются конечными автоматами. Причём, разруливаются легко и красиво.

А очереди сообщений _нет_, поскольку IPC синхронные. Это в Mach используются асинхронные IPC, и там действительно очередь сообщений сосёт. А в случае синхронных сообщений передающий поток просто отдаёт свой timeslice другому потоку, иногда даже без переключения контекста.

> А в случае синхронных сообщений передающий поток просто отдаёт свой timeslice другому потоку

Этот трюк пройдет только на однопроцессорной системе. Пора уже мыслить глобальнее =)

> Этот трюк пройдет только на однопроцессорной системе. Пора уже мыслить глобальнее =)

Спорим?

Чой-то, сдается мне, ты про корпоративную многозадачность говоришь...

Чего тут спорить? Есть у тебя две нити и два процессора. Одна посылает сообщение второй, тем самым пробуждая её. Даже если ты отдашь остаток кванта второй нити, первая тут же снова встанет на исполнение (в предположении, что у нее есть чем занятся), так как второму процессору делать нечего, и она тут же может поставить ещё одно сообщение, а вторая нить в это время сообщение вынимает...

Говорю же, можно попыхтеть и написать lock-free очередь, но в этом есть свои заморочки. Тем более это все равно можно считать синхронизацией, т.е. без нее никуда.

> Спорим?

А вообще в споре один человек дурак, а другой падонок. Выкладывай по существу свой метод.

>s/Многозодачное/Многозадачное/

правильно таки многозадочное :-)

> Чего тут спорить? Есть у тебя две нити и два процессора. Одна посылает сообщение второй, тем самым пробуждая её. Даже если ты отдашь остаток кванта второй нити,

Стоп. Вот она ошибка. Остаток кванта второй ните отдать невозможно, поскольку она исполняется на другом физическом процессоре. Соответственно, дальнейшее рассуждение не верно.

Тут фишка в другом - если нить приёмник не готова к приёму (независимо от того, на том же самом процессоре она исполняется или на другом), то кванты времени передатчика отдаются другим нитям передающего процессора.

В случае, если других нитей на передающем процессоре нет или они тоже находятся в состоянии приёма/ожидания, такой процессор переводится в состояние низкого энергопотребления, до наступления любого события - таймаут, готовность приёмника или получение сообщение от другого процессора.

> Чой-то, сдается мне, ты про корпоративную многозадачность говоришь...

И да, и нет. Ты уже догадался, что речь идёт о L4?

Я говорю о подходе, при котором используются и корпоративная и вытесняющая многозадачность. Причём, используются на полную катушку. Если поток (нить) что-то усиленно считает в цикле, то её переключит планировщик.

Кстати, в подавляющем большинстве систем процессор основную часть времени простаивает в HLT, то есть ждёт прерывания - от клавиатуры, от мыши, от сетевой карты, от винта, от любого устройства. И не важно, что это, - UNIX сервер, Windows десктоп или мобила. Нормальное состояние процессора - это HALT.

> Говорю же, можно попыхтеть и написать lock-free очередь, но в этом есть свои заморочки.

Не уверен насчёт lock-free очереди, но уверен что основная пробелма в данном случае - оптимально раскидать нити между физичесими процессорами.

> Тем более это все равно можно считать синхронизацией, т.е. без нее никуда.

А вот с этим согласен. А теперь - внимание:

Я утверждал и продолжаю утверждать, что можно реализовать ядро, которое не будет использовать методы синхронизации и блокировки. Но я не говорил, что этих методов не должно быть в микроядре, на котором основано ядро.

В идеале, а я верю что этот идеал достижим, примитивы обмена синхронными сообщениями должны быть реализованы в железе.

Например, вместо инструкций x86 процессора INT и SYSENTER будет использоваться новая инструкция IPC.

Блин, спешу. 

- В случае, если других нитей на передающем процессоре нет или они тоже находятся в состоянии приёма/ожидания
+ В случае, если других нитей на передающем процессоре нет или они тоже находятся в состоянии ожидания приёма/передачи.

> Но очередь сообщений сосет, так как она плоха укладывается в идею real-time.

Она великолепно и идеально укладывает в реалтайм. У меня, пожалуй, не хватит слов, чтобы спеть песню, посвящённую реалтайму на синхронных сообщениях. С точностью до такта процессора. Это элементарно. Но я бы хотел эту идею запатентовать, прежде чем на объяснять здесь на пальцах.

айбиэм в своем репертуаре

>А ведь можно написать ядро без критических секций и блокировок. Спорим?

Необходимость критических секций и блокировок в многопоточных средах была строго доказана Дейкстрой.

> Необходимость критических секций и блокировок в многопоточных средах была строго доказана Дейкстрой.

Потрудитесь привести доказательство Дейкстры здесь. Или хотя бы возразить.

На уровне приложений критические секции и блокировки нужны. Но только потому, что легче дать такой инструмент программисту, чем заставить его изобретать Finity State Machine.

>Потрудитесь привести доказательство Дейкстры здесь. Или хотя бы 
>возразить.
Поведение системы не должно зависеть от относительной скорости работы
составляющих ее процессов. Как это обеспечить без синхронизации работы
процессов? Чего тут доказывать?

весьма поверхностно...

> Поведение системы не должно зависеть от относительной скорости работы составляющих ее процессов. Как это обеспечить без синхронизации работы процессов? Чего тут доказывать?

Проблема возникла из за неправильной терминологии, которая возникла в результате спора. Блокировки есть и будут. Но в правильном ядре нет критических секций и спинлоков.

_Сама идея синхронных сообщений подразумевает блокировку_.

> Поведение системы не должно зависеть от относительной скорости работы составляющих ее процессов.

Используйте реалтайм сигналы для посылки реалтайм сообщений.

>весьма поверхностно...
ага буков греческого алфавита в определении недостает ... :)

>Проблема возникла из за неправильной терминологии, которая возникла в
>результате спора. Блокировки есть и будут. Но в правильном ядре нет 
>критических секций и спинлоков.
>_Сама идея синхронных сообщений подразумевает блокировку_
отлично, взаимное недопонимание преодолено. Осталось понять чем метод
синхронизации при помощи очередей сообщений лучше метода 
синхронизации при помощи блокировок (спинлоков etc)? Ради чего 
корячится? Из любви к искусству?

>Сама идея синхронных ообщений подразумевает блокировку

Изобретаешь QNX в лучшем случае

> Осталось понять чем метод синхронизации при помощи очередей сообщений лучше метода синхронизации при помощи блокировок (спинлоков etc)? Ради чего корячится? Из любви к искусству?

1. Точность передачи сообщений - 1 такт процессора.

2. Нет необходимости "греть" процессор при раскручивании спинлоков.

3. Умное переключение контекста.

4. В будущем, IPC может быть реализована одной командой процессора. Со всей выткающей отсюда оптимизацией.

> Изобретаешь QNX в лучшем случае

Нет. L4 - http://l4ka.org/projects/pistachio/l4-x2-r5.pdf

>1. Точность передачи сообщений - 1 такт процессора.
>2. Нет необходимости "греть" процессор при раскручивании спинлоков.
>3. Умное переключение контекста.
>4. В будущем, IPC может быть реализована одной командой процессора.
> Со всей выткающей отсюда оптимизацией
Тут опять видимо недопонимание с моей стороны. Про spinlock'и 
согласен. Но очереди в моем понимании довольно сложный объект,
нужен ли он? Не уверен, но мне кажется проблему синхронизации
процессов можно решить при помощи более простого объекта синхронизации
- например защелка с "проскальзыванием". Поскольку смысл синхронизации
сводится к защите разделяемых данных (ресурсов), достаточно ввести
функцию lock(), которая при успешном запирании возвращает например 0,
а если ресурс занят например -1. Тогда задача решается примерно так:

again:
if (lock() == -1) {
   schedule();
   goto again;
} else {
  // работаем с разделяемым ресурсом  
  unlock();
}

зачем нужны очереди?

>1. Точность передачи сообщений - 1 такт процессора.

>2. Нет необходимости "греть" процессор при раскручивании спинлоков.

>3. Умное переключение контекста.

>4. В будущем, IPC может быть реализована одной командой процессора. Со всей выткающей отсюда оптимизацией.

В общем, единственное, что вы пытаетесь изобрести (стащить из микрояда), это замена spinlock на mutex, т.е. busy waiting на обычное ождание. Блокировки как были, так и остаются.

Но когда вы начнете работать с железом и обнаружите, что прерывания нужно иногда выключать, а спать с выключенными прерываниями нельзя (т.к. маска прерываний может измениться), то тут же изобретете spinlock (типа только для private use)...

Так что идея неработоспособна.

Кстати, нарисуйте-ка конечный автомат добавления и одновременного удаления элемента из списка (хоть односвязного) без блокировок?

> Не уверен, но мне кажется проблему синхронизации процессов можно решить при помощи более простого объекта синхронизации - например защелка с "проскальзыванием".

Защёлка с "проскальзыванием" - хорошая идея, но не универсальная. Такую защёлку имеет смысл использовать, например, при сбросе кэшей на диск. Т.е. flusher бежит по объектам и проверяет блокировку. Если объект занят основным потоком (нитью), то он просто пропускается до следующей итерации. Но ежели flusher уже начал сбрасывать буфера на диск, то в основном потоке (ните) придётся или блокироваться или прерывать операцию, которая использует занятый flusher'ом объект.

> Поскольку смысл синхронизации сводится к защите разделяемых данных (ресурсов), достаточно ввести функцию lock(), которая при успешном запирании возвращает например 0, а если ресурс занят например -1.

А вот посмотрите внимательно на Ваш пример. В нём идет непосредственный вызов schedule(). Вот тут и начинается потеря производительности. Планировщик переключит контекст, а это дорогая, во всех смыслах, операция.

Использование умного переключения контекста в этом месте даст выигрыш в скорости. Т.е. поток (нить), пока находится в фазе ожидания приёма/передачи, - не потребляет ресурсов процессора. Все кванты времени этого потока отдаются другим потокам.

> В общем, единственное, что вы пытаетесь изобрести (стащить из микрояда), это замена spinlock на mutex, т.е. busy waiting на обычное ождание. Блокировки как были, так и остаются.

Я ничего не тащу из микроядра. Я просто пишу более высокоуровневое API, _поверх_ микроядра. Между прочим, POSIX совместимое API.

> Но когда вы начнете работать с железом и обнаружите, что прерывания нужно иногда выключать, а спать с выключенными прерываниями нельзя (т.к. маска прерываний может измениться), то тут же изобретете spinlock (типа только для private use)...

Я давно работаю с железом - клавиатура, RS-232 порты, флоппи дисковод (кстати, драйвер флоппи из FreeDOS, который был портирован туда из Линукса, IDE контроллер, сетевая карта. Ни разу, я повторяю - ни разу, у меня не возникла необходимость выключать прерывания.

> Кстати, нарисуйте-ка конечный автомат добавления и одновременного удаления элемента из списка (хоть односвязного) без блокировок?

Вы уверены, что понимаете проблему? Для добавления/удаления элемента из списка, конечный автомат не нужен. Но если настаиваете, то это делается так - существует поток (нить), владелец списка. Посылаете ей сообщение "Insert" со вставляемым элементом, затем посылаете сообщение "Remove" с идентификатором удаляемого элемента.

Хе-хе. Такой подход будет работать, но если кто-то так спроектировал систему, то он ССЗБ.

Конечный автомат нужен для других целей - для развязки синхронных вызовов в асинхронные. Делается это за счёт введния понятия "контекст сообщения". Щас попробую в ASCII графике нарисовать и запостить сюда.

>А вот посмотрите внимательно на Ваш пример. В нём идет непосредственный 
>вызов schedule(). Вот тут и начинается потеря производительности. 
>Планировщик переключит контекст, а это дорогая, во всех смыслах, 
>операция.
>Использование умного переключения контекста в этом месте даст выигрыш в 
>скорости. Т.е. поток (нить), пока находится в фазе ожидания 
>приёма/передачи, - не потребляет ресурсов процессора. Все кванты 
>времени этого потока отдаются другим потокам. 

Я никак не специфицировал schedule(), понятно что эта функция для разных случаев
будет разной (в том числе может вырождаться в пустую операцию по 
необходимости, превращая "скользящую" защелку в spinlock). Никто не 
мешает спрятать умный переключатель контекста в schedlue(). Собственно
"скользящая" защелка была приведена в качестве примера самого простого
примитива синхронизации из которого можно сделать все остальные по 
необходимости. А клоню я к тому, что у вас скорее всего очереди
в результате будут содержать те же spinlockи и т.п. в нужных случаях.
И вы получите те же "яйца только в профиль". В лучшем случае вы
получите удобную для некоторых случаев "универсальную" абстракцию с 
соответствующей потерей производительности. Собственно rtc уже на это
указал.

Фильтр, реализующий какой либо протокол.

        +------------------------+         +------------------------+
запрос  |                        | запрос  |                        | запрос	 
------->|  Сервис 1              |-------->|  Сервис 2              |-------->
        |                        |		   |                        |			 
ответ	|                        | ответ   |                        | ответ	 
<-------|                        |<--------|                        |<--------
        |                        |		   |                        |
        +------------------------+		   +------------------------+


Тот же фильтр, с использование КА
                
    <-----<-----ответ-<----<------<---+
    |   +------------------------+    |    +------------------------+
запрос  |                        |    -<---|                        | 	 
-->-+-->|  Сервис 1              |         |  Сервис 2              |
        |                        | запрос  |                        |запрос			 
ответ	|                        |-->----->|                        |---->--->  	 
<---<---|                        |    ^    |                        |
        |                        |    |    |                        |
        +------------------------+    |    +------------------------+   ответ
                                      +--<----<-----<------<------<-----<-----

> Я никак не специфицировал schedule(), понятно что эта функция для 
> разных случаев будет разной (в том числе может вырождаться в пустую 
> операцию по необходимости, превращая "скользящую" защелку в spinlock).

Ок. Рассмотрим вариант пустой операции schedule:

again:
if (lock() == -1) {
   goto again;
} else {
  // работаем с разделяемым ресурсом  
  unlock();
}

Действительно, почти спинлок. Соответственно, "греем" процессор. И нехило так "греем".

> Собственно "скользящая" защелка была приведена в качестве примера 
> самого простого примитива синхронизации из которого можно сделать
> все остальные по необходимости. А клоню я к тому, что у вас скорее
> всего очереди в результате будут содержать те же spinlockи и т.п. в 
> нужных случаях.

А вот не надо все остальные методы синхронизации делать на защёлках. Повер IPC так же легко реализуется pthread_mutex_lock()

>А вот не надо все остальные методы синхронизации делать на защёлках. 
>Повер IPC так же легко реализуется pthread_mutex_lock()
есть большие подозрения, что сам IPC будет содержать защелки в том или
ином виде

>Я давно работаю с железом - клавиатура, RS-232 порты, флоппи дисковод (кстати, драйвер флоппи из FreeDOS, который был портирован туда из Линукса, IDE контроллер, сетевая карта. Ни разу, я повторяю - ни разу, у меня не возникла необходимость выключать прерывания.

??? Аллах акбар, система капут! Интересно, а как вы выключаете устройство, прерывания остаются включенными? :) А если используется один и тот же список (например tcp retransmit очередь), который нужно обрабатывать для каждого полученного пакета (tcp ack например) - пакеты добавляются из process context, а удаляются из обработчика прерываний - без запрета прерываний в process context у вас мгновенно случится deadlock или race condition на smp.

На картинке выше (сожалею что "поползла") показан пример, для чего нужны конечные автоматы. Каждый сервис организован в виде программного потока (нити). В отличие от обычного фильтра, сервис с автоматом имеет совмещенной вход для запросов от протоколов верхнего уровня со входом для ответов от низлежащих протоколов.

Т.е. принимая сообщения, сервис определяет, получил ли он запрос или ответ и в зависимости от этого, меняет своё состояние. При этом, ответ от низлежащего сервиса может (после обработки или без) отправиться к верхнему протоколу. А может потребоваться дополнительный запрос к низлежащему драйверу.

Приведу простейший пример. Допустим, Сервис 1 - это сервис файловой системы, а Сервис 2 - сервис абстрактного блочного устройства.

Пользовательское приложение выполняет операцию read( );

Сервис файловой системы обнаружил, что позиция чтения попадает на double indirect block. Поэтому сначала происходит запрос к блочному устройству на вычитвание цепочки индексных блоков, а уже затем собственно чтение блока данных. При этом Сервис 1, прежде чем дать ответ приложению, три раза вызовет Сервис 2.

Всё очень тривиально. При этом всеми стуктурами данных файловой системы владеет поток (нить) Сервиса 1, и никакой одновременный доступ к этим структурам данных извне невозможен.

>Нет. L4 -

Оно не умерло?

> есть большие подозрения, что сам IPC будет содержать защелки в том или ином виде

А я этого нигде не отрицаю. Но это уровень микроядра. В идеале это должно быть реализовано аппаратно на уровне микропроцессора. А в ядре защёлки не нужны.

>Приведу простейший пример. Допустим, Сервис 1 - это сервис файловой системы, а Сервис 2 - сервис абстрактного блочного устройства.

>Пользовательское приложение выполняет операцию read( );

>Сервис файловой системы обнаружил, что позиция чтения попадает на double indirect block. Поэтому сначала происходит запрос к блочному устройству на вычитвание цепочки индексных блоков, а уже затем собственно чтение блока данных. При этом Сервис 1, прежде чем дать ответ приложению, три раза вызовет Сервис 2.

Т.е. 3 переключения контекста. Наверное они еще и на разных уровнях защиты живут (userspace на 3, сервисы на 1, само ядро наверное на 0), т.е. вы намеренно в 3 (!) раза ухудшили производительность.

Далее, завершение чтения блока сигнализируется прерыванием ide контроллера, как и кем это прерывание будет обработано? Наверное ядром на 0 уровне, при этом нужна блокировка очереди, чтобы сервисы не могли добавить/удалить блоки из очереди запросов (причем блокировка с прерываниями).