Re: Методы синхронизации и блокировки в Linux ядре
> ??? Аллах акбар, система капут! Интересно, а как вы выключаете устройство, прерывания остаются включенными? :)
Никто не мешает выключить прерывания непосредственно на устройстве. Например, сетевая карта может генерить около десятка различных прерываний, активность которых управляется устновкой соответствующего бита в соответствующем порту. Только на самом деле их отключать не нужно. Как максимум, можно просто не подтвердить какое либо прерывания и оно будет заблокировано контроллером прерывания. Но это вандализм. Не нужно их запрещать. Не нужно.
> А если используется один и тот же список (например tcp retransmit очередь), который нужно обрабатывать для каждого полученного пакета (tcp ack например) - пакеты добавляются из process context, а удаляются из обработчика прерываний - без запрета прерываний в process context у вас мгновенно случится deadlock или race condition на smp.
Если говорить непосредственно о TCP, то этот протокол крутится в отдельном потоке (нити_. Сверху ему приходят сообщения от userspace, снизу приходят сообщения от потока (нити) IP.
TCP пакеты упорядочены по времени retransmita. Когда приходит ack, пакет удаляется из очереди и освобождается. Кстати, TCP тоже совмещает вход для запросов сверху и пакетов от IP слоя.
На событие приёма ставится таймаут retransnmition пакета, который первый в очереди (а они отсортированы по возрастанию).
Если за случился таймаут, то есть не пришёл ack, то осуществляется повторная передача или, если счетчик retransnmition обнулился, дропанье пакета с соответсвующей сигнализацией в юзерспейс.
В ситуации, когда когда вместо ack пришёл новый запрос от юзерспейса, например запись или чтение в другой сокет. Разница таймаута ack для первого пакета в очереди - пересчитыватся. Но это очень быстрая операция. И только для первого пакета в очереди.
Не, так нельзя. Я сейчас все профессиональные секреты и Knoow How открою и чего мне тогда делать? :)
Re: Методы синхронизации и блокировки в Linux ядре
> Т.е. 3 переключения контекста. Наверное они еще и на разных уровнях защиты живут (userspace на 3, сервисы на 1, само ядро наверное на 0), т.е. вы намеренно в 3 (!) раза ухудшили производительность.
Насколько я знаю, уровни защиты в L4 не используются. Их с успехом заменяет страничная виртуальная память.
В худшем случае - три переключения. Всего-лишь три. Я не возмусь посчитать, сколько переключений контекстов происходит при использовании объектов синхронизации.
В нормальном случае - Сервис 1 и Сервис 2 в одном контексте. Т.е. выходит то же, что и в Linux/Windows.
Ничего не мешает поместить Сервис 1, Сервис 2 и пользовательское приложение в одно адресное пространство. Даже алгоритм работы меня не нужно. Только оперирование адресными пространствами. Сомневаюсь, что кто-нить перебить быстродействие системы при такой организации.
> Далее, завершение чтения блока сигнализируется прерыванием ide контроллера, как и кем это прерывание будет обработано?
Это прерывание обрабатывает исключительно сервис IDE контроллера. Более того, сервис IDE контроллера ничего не знает об очереди блоков. Он тупо читает/пишет блоки. Хотете реализовать схему лифта для минимизации движения головки винта? Не проблема. Создавайте сервис /dev/hda_cached поверх /dev/hda.
Саиое интересно, что такой сервис будет являться фильтром в чистом виде, то есть его можно воткнуть между файловой системой и серсивом IDE контроллера.
Причём, без правки хоть одной строчки кода в файловой системе. Сервис "лифта" снаружи выглядит точно так же, как и сервис IDE контроллера.
Re: Методы синхронизации и блокировки в Linux ядре
>Если говорить непосредственно о TCP, то этот протокол крутится в отдельном потоке (нити_. Сверху ему приходят сообщения от userspace, снизу приходят сообщения от потока (нити) IP.
Ога, и как они синхронизируются, если случается одновременная запись и прерывание (сразу после начала добавления элемента в список или в любой другой "неподходящий" момент?), в котором обрабатывается ack и удаляется пакет? Без выключения прерываний говорите? :)
Эта система неработоспособна. Даже если забыть о ее скорости. Даже если забыть, что нет никакого разделения процессов между собой (раз они все в одном кольце).
Re: Методы синхронизации и блокировки в Linux ядре
>> Далее, завершение чтения блока сигнализируется прерыванием ide контроллера, как и кем это прерывание будет обработано?
>Это прерывание обрабатывает исключительно сервис IDE контроллера. Более того, сервис IDE контроллера ничего не знает об очереди блоков.
У вас 2 клиента, каждый читает с диска - два запроса в очереди (один в ide контроллере, один ждет), если контроллер поддерживает много дескрипторов (а наверняка так и есть), то увеличиваем число клиентов до того момента, как свободных дескрипторов не остается.
Итак, сервис ide контроллера имеет очередь запросов от различных пользователей, с одной стороны пользователи, с другой аппаратное прерывание, сигнализирующее о готовности блока...
Re: Методы синхронизации и блокировки в Linux ядре
> Т.е. userspace крутится в нулевом кольце? :)))
Не совсем так. Правильней будет сказать что часть ядра крутится в юзерспейсе. Т.е. если мы передаём сообщение от потока к потоку, которые находятся в одной адресном пространстве, входа в нулевое кольцо может и не быть. Если память мне не изменяет, то есть только два кольца 0 и 3. Но это зависит от платформы. А чем Вас страничная защита не устраивает?
Re: Методы синхронизации и блокировки в Linux ядре
> Ога, и как они синхронизируются, если случается одновременная запись и прерывание (сразу после начала добавления элемента в список или в любой другой "неподходящий" момент?), в котором обрабатывается ack и удаляется пакет? Без выключения прерываний говорите? :)
Я терпеливый. Щас покажу.
while ( true )
{
L4_ThreadId_t tid;
L4_MsgTag_t tag;
tag = L4_Wait( L4_TimePeriod( tmout ), &tid );
if( L4_IpcFiled(tag) )
{
// За период tmout не получили ни одного сообщения.
// Обрабатываем первый TCP пакет в очереди
сontinue
}
if( L4_ThreadNo(tid) > mac+irq_number )
{
// Получили запрос на запись/чтение от IP слоя, Смотрим, чего ему надо
switch( L4_Label(tag) )
{
case WriteEtherentFramу:
// тут всё понятно.
break;
case ReadyToReadReceiveEtherentFrame:
// тут тоже всё понятно.
break;
default:
// По-видимому чужой запрос или неподдерживаемый протокол.
break;
}
}
else
{
// Полчили прерывание. Проверяем статус прерывания сетевой карты
// в зависимости от статуса выполняем обработку прерывания
// Затем подтверждаем прерывание.
}
}
Вот и всё! Одновременно может прийти только одно из трёх событий - таймаут, запрос или прерывание. Где тут пересечение? Где?
> Эта система неработоспособна. Даже если забыть о ее скорости. Даже если забыть, что нет никакого разделения процессов между собой (раз они все в одном кольце).
Эта система реально работает. Система реально работает. Реально работает. Работает.
Re: Методы синхронизации и блокировки в Linux ядре
> Итак, сервис ide контроллера имеет очередь запросов от различных пользователей, с одной стороны пользователи, с другой аппаратное прерывание, сигнализирующее о готовности блока...
Выше шаблон - там наглядно всё показано.
ide от ethernet будет отличаться меткой сообщения, которая берётся при помощи L4_Label(tag).
Re: Методы синхронизации и блокировки в Linux ядре
> Даже если забыть, что нет никакого разделения процессов между собой (раз они все в одном кольце).
Погуглите на предмет address space.
Одно кольцо никак не значит что нет разделения процессов.
Именно адресные пространства отличают процесс от потока(нити).
Re: Методы синхронизации и блокировки в Linux ядре
> Чего тут спорить? Есть у тебя две нити и два процессора. Одна посылает сообщение второй, тем самым пробуждая её. Даже если ты отдашь остаток кванта второй нити, первая тут же снова встанет на исполнение (в предположении, что у нее есть чем занятся), так как второму процессору делать нечего, и она тут же может поставить ещё одно сообщение, а вторая нить в это время сообщение вынимает...
Re: Методы синхронизации и блокировки в Linux ядре
> Но это уровень микроядра. В идеале это должно быть реализовано аппаратно на уровне микропроцессора. А в ядре защёлки не нужны.
Видимо, в данном треде неблюдается тотальное взимонепонимание и несогласованность терминологии.
Разумеется, если все блокировки перенести в микроядро и обеспечить доступность соответствующего интерфейса для приложений, то в ядре блокировок не будет -- просто потому, что мы обозвали "ядром" то, что не имеет блокировок.
Я вообще плохо понимаю концепцию "ядро" в контексте микроядерного подхода.
Re: Методы синхронизации и блокировки в Linux ядре
> Одно кольцо никак не значит что нет разделения процессов.
Одно кольцо - это значит, что любое приложение может обойти страничную защиту (при желании или случайно). Вряд ли разработчики L4 настолько ламеры, что позволят userspace работать в нулевом кольце :)
Re: Методы синхронизации и блокировки в Linux ядре
> У меня, пожалуй, не хватит слов, чтобы спеть песню, посвящённую реалтайму на синхронных сообщениях. С точностью до такта процессора. Это элементарно. Но я бы хотел эту идею запатентовать
Молодой человек, пристройтесь в конец длинной очереди из достойных и заслуженных людей. Ну или хотя бы почитайте о CSP, Occam и Ada ;)
Re: Методы синхронизации и блокировки в Linux ядре
> Видимо, в данном треде неблюдается тотальное взимонепонимание и несогласованность терминологии.
Не спорю с этим утверждением. Вроде с понятием "блокировка" разобрались, но по ходу спора обнаружено ещё несколько проблем в терминологии.
> Разумеется, если все блокировки перенести в микроядро и обеспечить доступность соответствующего интерфейса для приложений, то в ядре блокировок не будет -- просто потому, что мы обозвали "ядром" то, что не имеет блокировок.
> Я вообще плохо понимаю концепцию "ядро" в контексте микроядерного подхода.
Никогда не задумывался об этом. Предлагаю "ядром" считать "L4 roottask" и совокупность сервисов, которые обеспечивают POSIX функциональность.
Re: Методы синхронизации и блокировки в Linux ядре
> Одно кольцо - это значит, что любое приложение может обойти страничную
> защиту (при желании или случайно).
Честно говоря, с этим вопросом не разбирался. L4 работает на множестве процессоров:
* Alpha (21164, 21264)
* AMD64 (Opteron 242, Simics)
* ARM (SA1100, XScale, ARM925T)
* IA32 (Pentium and higher)
* IA64 (Itanium1, Itanium2, Ski)
* MIPS 64bit (R4000, R5000)
* PowerPC 32bit (IBM 750)
* PowerPC 64bit (Power3, Power4)
Не уверен, что все они поддерживают понятие колец защиты.
Интересно, каким образом Вы запишите/прочитаете память, чья страница не
отображена в адресное пространство потока (нити)?
> Вряд ли разработчики L4 настолько ламеры, что позволят userspace работать в нулевом кольце :)
Хе-хе. Я совершенно доверяю разработчикам L4. В особенности команде L4Ka.
Re: Методы синхронизации и блокировки в Linux ядре
>Не уверен, что все они поддерживают понятие колец защиты.
Просто называется это по разному, но поддерживают все.
>Интересно, каким образом Вы запишите/прочитаете память, чья страница не
отображена в адресное пространство потока (нити)?
Простите, а кто переключает адресное пространство? Если приложение на том же уровне защиты, то значит и текущее приложение может изменить. Если на более низком уровне, значит вот вам и ядро, которому нужно отключение прерываний и т.п.
>> Вряд ли разработчики L4 настолько ламеры, что позволят userspace работать в нулевом кольце :)
>Хе-хе. Я совершенно доверяю разработчикам L4. В особенности команде L4Ka.
Я бы не удивился, что там все работает на 0 кольце - это не в L4 необходимом самому приложению делать преобразования адресов?
Re: Методы синхронизации и блокировки в Linux ядре
>Одно кольцо никак не значит что нет разделения процессов. Именно адресные пространства отличают процесс от потока(нити).
Хмм, так кто же переключает адресные пространства? Это привилегированная операция, стало быть что-то на более низком уровне защиты, следовательно есть специальное ядро.
Или действительно все процессы в L4 крутятся в нулевом кольце и могут лезть в память друг друга.
Re: Методы синхронизации и блокировки в Linux ядре
>Если память мне не изменяет, то есть только два кольца 0 и 3.
По-разному, например на x86 есть несколько колец, xen использует это для разделения гостей. На x86_64 (и то только в новых процессорах) только 2 кольца, но есть аппаратный тег для страниц (один бит для guest/host).
Re: Методы синхронизации и блокировки в Linux ядре
> Так вы даже не показали ни одной очереди - как раз там все блокировки и происходят, с выключением прерываний и т.п
Вы имеете в вижу в примере из ЖЖ? Если да, то посмотрите в сторону функций write_data_to_device( &msg ), read_from_device( &msg ), handle_interrupt(). Которые управляют сразу двумя (!) очередями.
Очередь приёма и очередь передачи.
> Кстати, вы еще и удалили немало кода (например откуда берется tag).
Я не удалил не строчки кода. Просто, вместо copy'n'paste из проекта, набирал этот пример прям здесь.
Re: Методы синхронизации и блокировки в Linux ядре
> Простите, а кто переключает адресное пространство? Если приложение на том же уровне защиты, то значит и текущее приложение может изменить. Если на более низком уровне, значит вот вам и ядро, которому нужно отключение прерываний и т.п.
Переключает микроядро. Но не забывайте, что несколько нитей могут работать в одном адресном пространстве, и переключение между ними не требует смены уровня защиты. Просто небольшая часть микроядра может исполнятся в адресном пространстве любой нити.
Re: Методы синхронизации и блокировки в Linux ядре
> Хмм, так кто же переключает адресные пространства? Это привилегированная операция, стало быть что-то на более низком уровне защиты, следовательно есть специальное ядро.
Я виноват. Сейчас восстановил в памяти, как это работает. Адресные пространства переключает микроядро. Но в случае локальных IPC, между нитями пределах одного адресного пространства, часть кода микроядра, отвечающего за передачу сообщений, просто исполняется в адресном пространстве этих нитей. Конечно, это не значит, что всё микроядро исполняется в одном кольце защиты с сервисами и приложениями.
Кстати, для архитектуры x86 существует понятие small address space. Честно говоря, я так и не разобрался, что это означает, возможно что все процессы в одном кольце с микроядром. Но мне это не интересно.
Re: Методы синхронизации и блокировки в Linux ядре
> откуда берется tag
tag это переменная типа L4_MsgTat_t
Вот так он определён в файле message.h из userspace L4Ka:
/*
* Message tag
*/
typedef union {
L4_Word_t raw;
struct {
#if defined(L4_BIG_ENDIAN)
L4_Word_t label:16 __PLUS32;
L4_Word_t flags:4;
L4_Word_t t:6;
L4_Word_t u:6;
#else
L4_Word_t u:6;
L4_Word_t t:6;
L4_Word_t flags:4;
L4_Word_t label:16 __PLUS32;
#endif
} X;
} L4_MsgTag_t;
Назначение тега - хранить информацию о сообщение и его статус
приёма/передачи сообщения. Тег однозначно описывает формат сообщения.
Более подробную информацию о теги и сообщениях смотрите в спецификации
L4: http://l4ka.org/projects/pistachio/l4-x2-r5.pdf
Re: Методы синхронизации и блокировки в Linux ядре
>tag это переменная типа L4_MsgTat_t
Вопрос был не в том, что это такое, а как он передается и откуда берется. А берется он после добавления пакета в очередь в обработчике прерываний (с выключенными прерываниями кстати), с блокировкой. Откуда затем он удаляется и передается в написанную функцию. Так что, показав кусок кода, вырвав его из контекста, вы ничего не доказали.
В микроядре так же есть spin-блокировки, так же выключаются прерывания, только дополнительно в несколько раз ухудшена производительность.
Re: Методы синхронизации и блокировки в Linux ядре
> Вы так и не написали автомат работы списка без блокировок. Так что коментарий уместен.
write_data_to_device( &msg ) - вставляет пакет в хвост списка передачи
read_from_device( &msg ) - выбирает пакет из головы списка приёма
handle_interrupt() - анализирует, чем вызвано прерывание
в случае, если прерывание вызвано приёмом пакета из устройства,
то пакет добавляется в хвост списка, приёма.
в случае, когда прерывание вызвано готовностью устройства к передаче,
пакет добавляется, выбирается пакет из головы списка передачи.
_блокировки обеспечиваются микроядром_
Необходимость использовать функции pthread_mutex_lock,
EnterCriticalSection и запрета прерываний отпадает полностью.
Re: Методы синхронизации и блокировки в Linux ядре
> Вопрос был не в том, что это такое, а как он передается и откуда берется.
Tag - это результат работы IPC. Его значение возвращает микроядро, после передачи/приёма сообщения.
> А берется он после добавления пакета в очередь в обработчике прерываний (с выключенными прерываниями кстати), с блокировкой. Откуда затем он удаляется и передается в написанную функцию.
О какой очереди Вы говорите? Очереди сообщений - это более высокий уровень абстракции.
> Так что, показав кусок кода, вырвав его из контекста, вы ничего не доказали.
Ну Вы даёте! Я дал практически готовый шаблон, на основе которого можно написать _любой_ драйвер _любого_ устройства. Этот шаблон можно использовать для организации сервиса, преобразовав логику прерывания в логику ответа от низлежащего сервиса. При этом, программисту не надо задумывать о синхронизации доступа к данным, поскольку показанный мной подход исключает возможность пересечения.
> В микроядре так же есть spin-блокировки, так же выключаются прерывания, только дополнительно в несколько раз ухудшена производительность.
На счёт spin-блокировок ничего не скажу, может и есть, может и нет.
Только вот на счёт ухудшения производительности я привык больше доверять своим глазам, чем общепринятым заблуждениям.
Re: Методы синхронизации и блокировки в Linux ядре
>write_data_to_device( &msg ) - вставляет пакет в хвост списка передачи
:)) вы, похоже, вообще не разбираетесь в коде, извините :)
Это высокоуровневые функции, которые вызывают некоторые другие функции, это не код, который добавляет пакет в очередь.
Пример из ядра Linux: вы бы сказали, что функция skb_queue_tail() добавляет пакет в очередь. Это так, но на самом деле эта функция выключает прерывания, работает со списком, обновляет различные статистические переменные и т.п. Она вызывается как из прерывания (softirq), так и из process context, поэтому она обязана выключать прерывания.
Хотя в вашем linux аналоги скорее будут sys_send() и sys_recv() :)
Все абсолютно то же самое происходит и в микроядре. Микроядро вызывает выключение прерываний, обработку списка и т.п.
Да, для вызова read_from_device() не нудны блокировки, просто потому, что они есть внутри. Точно так же как для sys_recv().
Re: Методы синхронизации и блокировки в Linux ядре
>Ну Вы даёте! Я дал практически готовый шаблон, на основе которого можно написать _любой_ драйвер _любого_ устройства. Этот шаблон можно использовать для организации сервиса, преобразовав логику прерывания в логику ответа от низлежащего сервиса. При этом, программисту не надо задумывать о синхронизации доступа к данным, поскольку показанный мной подход исключает возможность пересечения.
Вы действительно считаете, что 20 строк кода, это "шаблон, на основе которого можно написать _любой_ драйвер _любого_ устройства"?
Попробуйте как-нибудь, о результатах потом расскажите. Будет очень интересно посмотреть на дрйвер сетевого адаптера, написанного по этому "шаблону" :)
Re: Методы синхронизации и блокировки в Linux ядре
> Попробуйте как-нибудь, о результатах потом расскажите. Будет очень интересно посмотреть на дрйвер сетевого адаптера, написанного по этому "шаблону" :)