Re: Методы синхронизации и блокировки в Linux ядре
Статья отстой. С таким же успехом можно открыть книжку по POSIX-нитям и узнать тоже самое. Перечисленные в статье механизмы используются повсюды. А вот необщепринятые механизмы синхронизации, которые используются в ядре (например, RCU) в статье-то как раз и не описаны.
Re: Методы синхронизации и блокировки в Linux ядре
Многозодачное.
Идея не очень сложная - система должна быть спроектирована таким образом, чтобы каждым ресурсом владел только один программный поток. Потоки обмениваются синхронными сообщениями. Именно синхронные сообщения защищают объекты и структуры от одновременного доступа.
При этом ядро легко параллелится на несколько процессоров.
Re: Методы синхронизации и блокировки в Linux ядре
Что, дико звучит, что ядро параллелится? Небось, привыкли что ядро исполняется в кванте времени задачи, которая вызвала syscall или в контексте прерывания? Пора отвыкать.
В частном случае, прерывание и есть программный поток, который блокирован до прихода сообщения. Например, прерывания.
Re: Методы синхронизации и блокировки в Linux ядре
>>Многозодачное. Идея не очень сложная - система должна быть спроектирована таким образом, чтобы каждым ресурсом владел только один программный поток. Потоки обмениваются синхронными сообщениями. Именно синхронные сообщения защищают объекты и структуры от одновременного доступа. При этом ядро легко параллелится на несколько процессоров.
Re: Методы синхронизации и блокировки в Linux ядре
> Потоки обмениваются синхронными сообщениями.
В первом приближении у тебя будет блокировка в очереди сообщений, хотя если очень постараться, то очередь можно написать lock-free. Но очередь сообщений сосет, так как она плоха укладывается в идею real-time.
Re: Методы синхронизации и блокировки в Linux ядре
> В первом приближении у тебя будет блокировка в очереди сообщений, хотя если очень постараться, то очередь можно написать lock-free.
Но очередь сообщений сосет, так как она плоха укладывается в идею real-time.
И да и нет. Попробую пояснить. Да - насчёт блокировки. Тут надо сильно постараться в момент дизайна системы. Блокировки разруливаются конечными автоматами. Причём, разруливаются легко и красиво.
А очереди сообщений _нет_, поскольку IPC синхронные. Это в Mach используются асинхронные IPC, и там действительно очередь сообщений сосёт. А в случае синхронных сообщений передающий поток просто отдаёт свой timeslice другому потоку, иногда даже без переключения контекста.
Re: Методы синхронизации и блокировки в Linux ядре
Чего тут спорить? Есть у тебя две нити и два процессора. Одна посылает сообщение второй, тем самым пробуждая её. Даже если ты отдашь остаток кванта второй нити, первая тут же снова встанет на исполнение (в предположении, что у нее есть чем занятся), так как второму процессору делать нечего, и она тут же может поставить ещё одно сообщение, а вторая нить в это время сообщение вынимает...
Говорю же, можно попыхтеть и написать lock-free очередь, но в этом есть свои заморочки. Тем более это все равно можно считать синхронизацией, т.е. без нее никуда.
Re: Методы синхронизации и блокировки в Linux ядре
> Чего тут спорить? Есть у тебя две нити и два процессора. Одна посылает сообщение второй, тем самым пробуждая её. Даже если ты отдашь остаток кванта второй нити,
Стоп. Вот она ошибка. Остаток кванта второй ните отдать невозможно, поскольку она исполняется на другом физическом процессоре. Соответственно, дальнейшее рассуждение не верно.
Тут фишка в другом - если нить приёмник не готова к приёму (независимо от того, на том же самом процессоре она исполняется или на другом), то кванты времени передатчика отдаются другим нитям передающего процессора.
В случае, если других нитей на передающем процессоре нет или они тоже находятся в состоянии приёма/ожидания, такой процессор переводится в состояние низкого энергопотребления, до наступления любого события - таймаут, готовность приёмника или получение сообщение от другого процессора.
Re: Методы синхронизации и блокировки в Linux ядре
> Чой-то, сдается мне, ты про корпоративную многозадачность говоришь...
И да, и нет. Ты уже догадался, что речь идёт о L4?
Я говорю о подходе, при котором используются и корпоративная и вытесняющая многозадачность. Причём, используются на полную катушку.
Если поток (нить) что-то усиленно считает в цикле, то её переключит планировщик.
Кстати, в подавляющем большинстве систем процессор основную часть времени простаивает в HLT, то есть ждёт прерывания - от клавиатуры, от мыши, от сетевой карты, от винта, от любого устройства. И не важно, что это, - UNIX сервер, Windows десктоп или мобила. Нормальное состояние процессора - это HALT.
Re: Методы синхронизации и блокировки в Linux ядре
> Говорю же, можно попыхтеть и написать lock-free очередь, но в этом есть свои заморочки.
Не уверен насчёт lock-free очереди, но уверен что основная пробелма в данном случае - оптимально раскидать нити между физичесими процессорами.
> Тем более это все равно можно считать синхронизацией, т.е. без нее никуда.
А вот с этим согласен. А теперь - внимание:
Я утверждал и продолжаю утверждать, что можно реализовать ядро, которое не будет использовать методы синхронизации и блокировки. Но я не говорил, что этих методов не должно быть в микроядре, на котором основано ядро.
В идеале, а я верю что этот идеал достижим, примитивы обмена синхронными сообщениями должны быть реализованы в железе.
Например, вместо инструкций x86 процессора INT и SYSENTER будет использоваться новая инструкция IPC.
Re: Методы синхронизации и блокировки в Linux ядре
Блин, спешу.
- В случае, если других нитей на передающем процессоре нет или они тоже находятся в состоянии приёма/ожидания
+ В случае, если других нитей на передающем процессоре нет или они тоже находятся в состоянии ожидания приёма/передачи.
Re: Методы синхронизации и блокировки в Linux ядре
> Но очередь сообщений сосет, так как она плоха укладывается в идею real-time.
Она великолепно и идеально укладывает в реалтайм. У меня, пожалуй, не хватит слов, чтобы спеть песню, посвящённую реалтайму на синхронных сообщениях. С точностью до такта процессора. Это элементарно. Но я бы хотел эту идею запатентовать, прежде чем на объяснять здесь на пальцах.
Re: Методы синхронизации и блокировки в Linux ядре
> Необходимость критических секций и блокировок в многопоточных средах была строго доказана Дейкстрой.
Потрудитесь привести доказательство Дейкстры здесь.
Или хотя бы возразить.
На уровне приложений критические секции и блокировки нужны. Но только потому, что легче дать такой инструмент программисту, чем заставить его изобретать Finity State Machine.
Re: Методы синхронизации и блокировки в Linux ядре
>Потрудитесь привести доказательство Дейкстры здесь. Или хотя бы
>возразить.
Поведение системы не должно зависеть от относительной скорости работы
составляющих ее процессов. Как это обеспечить без синхронизации работы
процессов? Чего тут доказывать?
Re: Методы синхронизации и блокировки в Linux ядре
> Поведение системы не должно зависеть от относительной скорости работы
составляющих ее процессов. Как это обеспечить без синхронизации работы
процессов? Чего тут доказывать?
Проблема возникла из за неправильной терминологии, которая возникла в результате спора. Блокировки есть и будут. Но в правильном ядре нет критических секций и спинлоков.
_Сама идея синхронных сообщений подразумевает блокировку_.
Re: Методы синхронизации и блокировки в Linux ядре
>весьма поверхностно...
ага буков греческого алфавита в определении недостает ... :)
>Проблема возникла из за неправильной терминологии, которая возникла в
>результате спора. Блокировки есть и будут. Но в правильном ядре нет
>критических секций и спинлоков.
>_Сама идея синхронных сообщений подразумевает блокировку_
отлично, взаимное недопонимание преодолено. Осталось понять чем метод
синхронизации при помощи очередей сообщений лучше метода
синхронизации при помощи блокировок (спинлоков etc)? Ради чего
корячится? Из любви к искусству?
Re: Методы синхронизации и блокировки в Linux ядре
> Осталось понять чем метод синхронизации при помощи очередей сообщений лучше метода синхронизации при помощи блокировок (спинлоков etc)? Ради чего корячится? Из любви к искусству?
1. Точность передачи сообщений - 1 такт процессора.
2. Нет необходимости "греть" процессор при раскручивании спинлоков.
3. Умное переключение контекста.
4. В будущем, IPC может быть реализована одной командой процессора. Со всей выткающей отсюда оптимизацией.
Re: Методы синхронизации и блокировки в Linux ядре
>1. Точность передачи сообщений - 1 такт процессора.
>2. Нет необходимости "греть" процессор при раскручивании спинлоков.
>3. Умное переключение контекста.
>4. В будущем, IPC может быть реализована одной командой процессора.
> Со всей выткающей отсюда оптимизацией
Тут опять видимо недопонимание с моей стороны. Про spinlock'и
согласен. Но очереди в моем понимании довольно сложный объект,
нужен ли он? Не уверен, но мне кажется проблему синхронизации
процессов можно решить при помощи более простого объекта синхронизации
- например защелка с "проскальзыванием". Поскольку смысл синхронизации
сводится к защите разделяемых данных (ресурсов), достаточно ввести
функцию lock(), которая при успешном запирании возвращает например 0,
а если ресурс занят например -1. Тогда задача решается примерно так:
again:
if (lock() == -1) {
schedule();
goto again;
} else {
// работаем с разделяемым ресурсом
unlock();
}
зачем нужны очереди?
Re: Методы синхронизации и блокировки в Linux ядре
>1. Точность передачи сообщений - 1 такт процессора.
>2. Нет необходимости "греть" процессор при раскручивании спинлоков.
>3. Умное переключение контекста.
>4. В будущем, IPC может быть реализована одной командой процессора. Со всей выткающей отсюда оптимизацией.
В общем, единственное, что вы пытаетесь изобрести (стащить из микрояда), это замена spinlock на mutex, т.е. busy waiting на обычное ождание. Блокировки как были, так и остаются.
Но когда вы начнете работать с железом и обнаружите, что прерывания нужно иногда выключать, а спать с выключенными прерываниями нельзя (т.к. маска прерываний может измениться), то тут же изобретете spinlock (типа только для private use)...
Так что идея неработоспособна.
Кстати, нарисуйте-ка конечный автомат добавления и одновременного удаления элемента из списка (хоть односвязного) без блокировок?
Re: Методы синхронизации и блокировки в Linux ядре
> Не уверен, но мне кажется проблему синхронизации
процессов можно решить при помощи более простого объекта синхронизации
- например защелка с "проскальзыванием".
Защёлка с "проскальзыванием" - хорошая идея, но не универсальная. Такую защёлку имеет смысл использовать, например, при сбросе кэшей на диск. Т.е. flusher бежит по объектам и проверяет блокировку. Если объект занят основным потоком (нитью), то он просто пропускается до следующей итерации. Но ежели flusher уже начал сбрасывать буфера на диск, то в основном потоке (ните) придётся или блокироваться или прерывать операцию, которая использует занятый flusher'ом объект.
> Поскольку смысл синхронизации сводится к защите разделяемых данных (ресурсов), достаточно ввести функцию lock(), которая при успешном запирании возвращает например 0, а если ресурс занят например -1.
А вот посмотрите внимательно на Ваш пример. В нём идет непосредственный вызов schedule(). Вот тут и начинается потеря производительности. Планировщик переключит контекст, а это дорогая, во всех смыслах, операция.
Использование умного переключения контекста в этом месте даст выигрыш в скорости. Т.е. поток (нить), пока находится в фазе ожидания приёма/передачи, - не потребляет ресурсов процессора. Все кванты времени этого потока отдаются другим потокам.
Re: Методы синхронизации и блокировки в Linux ядре
> В общем, единственное, что вы пытаетесь изобрести (стащить из микрояда), это замена spinlock на mutex, т.е. busy waiting на обычное ождание. Блокировки как были, так и остаются.
Я ничего не тащу из микроядра. Я просто пишу более высокоуровневое API, _поверх_ микроядра. Между прочим, POSIX совместимое API.
> Но когда вы начнете работать с железом и обнаружите, что прерывания нужно иногда выключать, а спать с выключенными прерываниями нельзя (т.к. маска прерываний может измениться), то тут же изобретете spinlock (типа только для private use)...
Я давно работаю с железом - клавиатура, RS-232 порты, флоппи дисковод (кстати, драйвер флоппи из FreeDOS, который был портирован туда из Линукса, IDE контроллер, сетевая карта. Ни разу, я повторяю - ни разу, у меня не возникла необходимость выключать прерывания.
> Кстати, нарисуйте-ка конечный автомат добавления и одновременного удаления элемента из списка (хоть односвязного) без блокировок?
Вы уверены, что понимаете проблему? Для добавления/удаления элемента из списка, конечный автомат не нужен. Но если настаиваете, то это делается так - существует поток (нить), владелец списка. Посылаете ей сообщение "Insert" со вставляемым элементом, затем посылаете сообщение "Remove" с идентификатором удаляемого элемента.
Хе-хе. Такой подход будет работать, но если кто-то так спроектировал систему, то он ССЗБ.
Конечный автомат нужен для других целей - для развязки синхронных вызовов в асинхронные. Делается это за счёт введния понятия "контекст сообщения". Щас попробую в ASCII графике нарисовать и запостить сюда.
Re: Методы синхронизации и блокировки в Linux ядре
>А вот посмотрите внимательно на Ваш пример. В нём идет непосредственный
>вызов schedule(). Вот тут и начинается потеря производительности.
>Планировщик переключит контекст, а это дорогая, во всех смыслах,
>операция.
>Использование умного переключения контекста в этом месте даст выигрыш в
>скорости. Т.е. поток (нить), пока находится в фазе ожидания
>приёма/передачи, - не потребляет ресурсов процессора. Все кванты
>времени этого потока отдаются другим потокам.
Я никак не специфицировал schedule(), понятно что эта функция для разных случаев
будет разной (в том числе может вырождаться в пустую операцию по
необходимости, превращая "скользящую" защелку в spinlock). Никто не
мешает спрятать умный переключатель контекста в schedlue(). Собственно
"скользящая" защелка была приведена в качестве примера самого простого
примитива синхронизации из которого можно сделать все остальные по
необходимости. А клоню я к тому, что у вас скорее всего очереди
в результате будут содержать те же spinlockи и т.п. в нужных случаях.
И вы получите те же "яйца только в профиль". В лучшем случае вы
получите удобную для некоторых случаев "универсальную" абстракцию с
соответствующей потерей производительности. Собственно rtc уже на это
указал.
Re: Методы синхронизации и блокировки в Linux ядре
> Я никак не специфицировал schedule(), понятно что эта функция для
> разных случаев будет разной (в том числе может вырождаться в пустую
> операцию по необходимости, превращая "скользящую" защелку в spinlock).
Ок. Рассмотрим вариант пустой операции schedule:
again:
if (lock() == -1) {
goto again;
} else {
// работаем с разделяемым ресурсом
unlock();
}
Действительно, почти спинлок. Соответственно, "греем" процессор. И нехило так "греем".
> Собственно "скользящая" защелка была приведена в качестве примера
> самого простого примитива синхронизации из которого можно сделать
> все остальные по необходимости. А клоню я к тому, что у вас скорее
> всего очереди в результате будут содержать те же spinlockи и т.п. в
> нужных случаях.
А вот не надо все остальные методы синхронизации делать на защёлках. Повер IPC так же легко реализуется pthread_mutex_lock()
Re: Методы синхронизации и блокировки в Linux ядре
>А вот не надо все остальные методы синхронизации делать на защёлках.
>Повер IPC так же легко реализуется pthread_mutex_lock()
есть большие подозрения, что сам IPC будет содержать защелки в том или
ином виде
Re: Методы синхронизации и блокировки в Linux ядре
>Я давно работаю с железом - клавиатура, RS-232 порты, флоппи дисковод (кстати, драйвер флоппи из FreeDOS, который был портирован туда из Линукса, IDE контроллер, сетевая карта. Ни разу, я повторяю - ни разу, у меня не возникла необходимость выключать прерывания.
??? Аллах акбар, система капут! Интересно, а как вы выключаете устройство, прерывания остаются включенными? :) А если используется один и тот же список (например tcp retransmit очередь), который нужно обрабатывать для каждого полученного пакета (tcp ack например) - пакеты добавляются из process context, а удаляются из обработчика прерываний - без запрета прерываний в process context у вас мгновенно случится deadlock или race condition на smp.
Re: Методы синхронизации и блокировки в Linux ядре
На картинке выше (сожалею что "поползла") показан пример, для чего нужны конечные автоматы. Каждый сервис организован в виде программного потока (нити). В отличие от обычного фильтра, сервис с автоматом имеет совмещенной вход для запросов от протоколов верхнего уровня со входом для ответов от низлежащих протоколов.
Т.е. принимая сообщения, сервис определяет, получил ли он запрос или ответ и в зависимости от этого, меняет своё состояние. При этом, ответ от низлежащего сервиса может (после обработки или без) отправиться к верхнему протоколу. А может потребоваться дополнительный запрос к низлежащему драйверу.
Приведу простейший пример. Допустим, Сервис 1 - это сервис файловой системы, а Сервис 2 - сервис абстрактного блочного устройства.
Пользовательское приложение выполняет операцию read( );
Сервис файловой системы обнаружил, что позиция чтения попадает на double indirect block. Поэтому сначала происходит запрос к блочному устройству на вычитвание цепочки индексных блоков, а уже затем собственно чтение блока данных. При этом Сервис 1, прежде чем дать ответ приложению, три раза вызовет Сервис 2.
Всё очень тривиально. При этом всеми стуктурами данных файловой системы владеет поток (нить) Сервиса 1, и никакой одновременный доступ к этим структурам данных извне невозможен.
Re: Методы синхронизации и блокировки в Linux ядре
> есть большие подозрения, что сам IPC будет содержать защелки в том или
ином виде
А я этого нигде не отрицаю. Но это уровень микроядра. В идеале это должно быть реализовано аппаратно на уровне микропроцессора. А в ядре защёлки не нужны.
Re: Методы синхронизации и блокировки в Linux ядре
>Приведу простейший пример. Допустим, Сервис 1 - это сервис файловой системы, а Сервис 2 - сервис абстрактного блочного устройства.
>Пользовательское приложение выполняет операцию read( );
>Сервис файловой системы обнаружил, что позиция чтения попадает на double indirect block. Поэтому сначала происходит запрос к блочному устройству на вычитвание цепочки индексных блоков, а уже затем собственно чтение блока данных. При этом Сервис 1, прежде чем дать ответ приложению, три раза вызовет Сервис 2.
Т.е. 3 переключения контекста. Наверное они еще и на разных уровнях защиты живут (userspace на 3, сервисы на 1, само ядро наверное на 0), т.е. вы намеренно в 3 (!) раза ухудшили производительность.
Далее, завершение чтения блока сигнализируется прерыванием ide контроллера, как и кем это прерывание будет обработано? Наверное ядром на 0 уровне, при этом нужна блокировка очереди, чтобы сервисы не могли добавить/удалить блоки из очереди запросов (причем блокировка с прерываниями).
(12.11.2007 19:11:10)