lock-free дизайн многопоточных программ

[sss]

RXL, не понял... Я имел ввиду превосходство сетей с коммутацией пакетов над сетями с коммутацией каналов. Причем здесь переход на цифровой способ доставки?

[Вад]

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

Offtopic:

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

Поставлю в угол.

[Антон (LogRus)]

LogRus, ну, это уже не наш уровень - над этим пусть производители процессоров думают, как этого избежать.

ну строго говоря мы тоже должны думать, например, есть такое понятие, как false sharing, например вроде, как потоки не пересекаются по переменным, НО переменные находятся в одной кэш-линии, что при постоянном обновлении этих переменных может привести к сильному снижению производительности.

[RXL]

RXL, не понял... Я имел ввиду превосходство сетей с коммутацией пакетов над сетями с коммутацией каналов. Причем здесь переход на цифровой способ доставки?

Взаимосвязано. Канал имеет прообраз - взят аналоговой техники. Обмен пакетам - естественная работа цифровой техники.
К тому же это оффтопик. Не вижу никакого отношения телефонии к синхронизации в программировании.

[Dimka]

Нашёл статейку, отчасти объясняющую идею мультиплексирования:

http://www.smira.ru/2009/02/10/deferred-async-programming/

Здесь примеры на Python. Через замыкания организуются ленивые вычисления, получение результатов (или ошибок) которых приводит к callback. В частности, немного говорится о приёме программирования без блокировок (правда, порождать нить на маленький расчёт не всегда выгодно по ресурсам).

Но вообще чувствуется, что для такого подхода не хватает адекватного компактного синтаксиса в языках программирования. В тему об "одномерности" кода и программирования обработки сигналов. А также о в тему о пользе функционального подхода с его stateless.

[Антон (LogRus)]

...........не хватает адекватного компактного синтаксиса в языках программирования.........

OpenMP?
tbb?
boost::thread?

[Вад]

Dimka, для подобных асинхронных действий существуют "зелёные нити". Собственно, весь язык erlang построен на том, что если нужно выполнить что-то отдельно, а потом получить ответ - то нужно породить отдельный поток, который займётся выполнением и вернёт результат (сообщение): либо успешный, либо сообщение о собственной преждевременной смерти

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

[RXL]

Вад, а чем эти "зеленые" отличаются от обычных?

[Вад]

Тем, что они могут работать и в одном обычном. Это "cooperative multitasking" - контекст "переключает" виртуальная машина, поэтому переключение контекста куда дешевле: фактически, это такие замыкания, выполнение которых мультиплексирует виртуальная машина.

Скажем, в ОС Symbian по соображениям производительности настоятельно рекомендуют использовать так называемые Active Objects, которые по сути представляют собой зелёные нити, вместо обычных потоков, где это возможно. Хотя обычные потоки также доступны.

[Dimka]

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

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

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

[RXL]

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

http://en.wikipedia.org/wiki/Green_threads
http://en.wikipedia.org/wiki/Light-weight_process

[dimedrol]

Bad, зеленые нити это типа Fiber-ов в винде получается?
 ЗЫ Вспоминаю свой курсовой проект, который писал курсе на 3-м. Там была прога-чат для обмена сосбщениями по маркерному кольцу. Изначально планировалось 6 ниток, в итоге, упрощая код, осталось 2, включая нить по обработке пользовательского ввода и нитка на сетевую активность (юзал сокеты) К сожалению в самой ОС и некоторых стандартах много завязано на многопоточность, например касательно СОМ в винде.

[Dimka]

Модель fiber'ов как раз и использует невытесняющую многозадачность, т.е. каждый fiber сам должен сказать, когда можно передать исполнение следующему.

[Вад]

RXL, в терминах немного сбился В том и дело, что то, что называется легковесными процессами в erlang, по факту является green threads (В статье про erlang, кстати, так и сказано: "Erlang processes are neither operating system processes nor operating system threads, but lightweight processes somewhat similar to Java's original “green threads”.").

[RXL]

Я бы сказал так: никаких "зеленых" потоков не существует - это глюки от переизбытка кофе, но есть очередь заданий и ее можно пополнять. Я верно выразился?

Код:

task_queue_t tasks;
task_t *task;

while (true)
{
  if ((task = tasks.shift()))
  {
    yield();
  }
  else
  {
    if (stars_coincided())
      tasks.push(new task_t(......));

    delete task;
  }
}

[Dimka]

Очередь задач понимаю, маленьких зелёных поточков своими глазами не видел, так что ничего не могу сказать Может и есть, раз кто-то их видел...

[lapulya]

Dimka, +1 

[Вад]

Я бы сказал так: никаких "зеленых" потоков не существует - это глюки от переизбытка кофе, но есть очередь заданий и ее можно пополнять. Я верно выразился?

Ну, если добавить к этому то, что каждое задание в такой очереди имеет свою очередь заданий (сообщений) и может общаться с другими заданиями из очереди - то, в принципе, всё так

[RXL]

Вад, т.е. неоконченное задание может вернуться в очередь. Но ничего зеленого тут нет - просто им название понравилось. Лишние термины лишь запутывают...

[Вад]

Да, но нужно же это как-то называть Не называть же "очередь задач, выполняемых по частям". Зелёные - как бы намёк на экологичность, экономность в смысле переключения контекста. Ведь, по сути, механизм обеспечивает именно многопоточность без расходов собственно на реальную многопоточность.

И как абстракция, это запускаемый поток(процесс), а не задание, которое ставится куда-то в очередь. Очередь скрыта, очередь - это деталь реализации.

[Антон (LogRus)]

Дмитрий Вьюков (aka Remark на rsdn.ru) некоторое время назад запустил ресурс http://www.1024cores.net/
очень рекомендую всем кого волнуют Lock-Free алгоритмы и вообще оптимизационные трюки
Блог сателит - http://blog.1024cores.net/
твитер - http://twitter.com/dvyukov


Добавлено через 4 минуты и 11 секунд:
ах да, на http://www.1024cores.net/ внимательный взгляд заметит кнопочку In Russian

[Dimka]

Чего-то у него материалы какие-то необработанные - больше похожи на отрывки или заметки из чего-то внешнего. Контекста нет.

P.S. Философские тетради Ленина напомнило

[Антон (LogRus)]

А по мне так нормально ИМХО, человек давно занимается вопросом lock-free и просто выбрасывает из текста куски которые он считает очевидыми. Так бывает с людьми, вспомним дядьку Шерлока, который выдавал ответ, а цепочку размышлений выдавал по запросу

[Dimka]

Антон (LogRus), я отнюдь не о том, что у него объяснения непонятные. Я о том, что эти объяснения непрезентабельны, не содержат какого-то введения: хотя бы на уровне кратких характеристик тех библиотек и инструментов, которые он использует. Поэтому непонятно, для кого это пишется. Если это материалы для узкого междусобойчика (или тусовки) людей, которые в теме - это одно. Если это материалы, призванные осчастливить человечество новыми знаниями, то над ними ещё работать и работать.

[Антон (LogRus)]

Dimka, скорее первое, не так много людей интересуются lock-free, а тот кто интересуется обычно уже немного в теме
а конкретную статью можешь показать из тех, что тебе не приглянулись, я еще не все их прочёл

[Dimka]

Антон (LogRus), да любую бери. Это формат блога.

[Антон (LogRus)]

http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms
ничего такого не заметил

[Dimka]

Антон (LogRus), а это и вовсе не про lock-free design приложения. Это больше про заточку решения под архитектуру железа, в коей я большого смысла не вижу. Это одноразовые трудозатраты, которые при смене аппаратной архитектуры (а то и даже просто конфигурации) пропадают - на таком фундаменте долговечную прикладную систему не создать, и годится это лишь для таких продуктов, где железо и софт продаются вместе в одном комплекте; либо же это довольно узкая сфера разработки системных библиотек, инкапсулирующих аппаратные особенности платформ. Т.е. в плане научных изысканий - дело нужное, но не будучи оформлено как системный продукт, это слабо помогает прикладникам - возникает ощущение попусту потраченного времени на перелопачивание всех этих заметок.

[Антон (LogRus)]

Dimka, иногда оно надо, лично мне надо и lock-free и оптимизации аля уменьшение false-sharing
lock-free часто тоже заточен под конкретную железяку, в прикладном программирование редко возникают задачи (а возникают ли?), когда нужно выжать всё из железяки.

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

[Dimka]

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

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

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