Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 [2]  Все   Вниз
  Печать  
Автор Тема: lock-free дизайн многопоточных программ  (Прочитано 85142 раз)
0 Пользователей и 1 Гость смотрят эту тему.
sss
Специалист

ru
Offline Offline

« Ответ #30 : 10-02-2010 09:56 » 

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

while (8==8)
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #31 : 10-02-2010 10:01 » 

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

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

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #32 : 10-02-2010 10:09 » 

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

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

Странно всё это....
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #33 : 10-02-2010 10:20 » 

RXL, не понял... Я имел ввиду превосходство сетей с коммутацией пакетов над сетями с коммутацией каналов. Причем здесь переход на цифровой способ доставки?
Взаимосвязано. Канал имеет прообраз - взят аналоговой техники. Обмен пакетам - естественная работа цифровой техники.
К тому же это оффтопик. Не вижу никакого отношения телефонии к синхронизации в программировании.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #34 : 10-02-2010 23:06 » 

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

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

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #35 : 11-02-2010 06:04 » 

...........не хватает адекватного компактного синтаксиса в языках программирования.........
OpenMP?
tbb?
boost::thread?
Записан

Странно всё это....
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #36 : 11-02-2010 08:09 » 

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

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #37 : 11-02-2010 08:51 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #38 : 11-02-2010 09:11 » 

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

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

ru
Offline Offline
Пол: Мужской

« Ответ #39 : 11-02-2010 09:24 » 

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

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #40 : 11-02-2010 09:46 » 

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

http://en.wikipedia.org/wiki/Green_threads
http://en.wikipedia.org/wiki/Light-weight_process
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
dimedrol
Помогающий

ru
Offline Offline

« Ответ #41 : 11-02-2010 11:13 » 

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

Как говориться, cемь бед - один Reset Улыбаюсь
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #42 : 11-02-2010 11:23 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #43 : 11-02-2010 12:16 » 

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
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #44 : 11-02-2010 19:19 » 

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

Код:
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;
  }
}

« Последнее редактирование: 11-02-2010 19:29 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #45 : 11-02-2010 20:06 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
lapulya
Молодой специалист

ru
Offline Offline

« Ответ #46 : 12-02-2010 00:26 » 

Dimka, +1  Жжешь Жжешь Жжешь
Записан

С уважением Lapulya
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #47 : 12-02-2010 07:42 » 

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

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #48 : 12-02-2010 08:12 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #49 : 12-02-2010 09:33 » 

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

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

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #50 : 07-02-2011 05:26 » 

Дмитрий Вьюков (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 Улыбаюсь
« Последнее редактирование: 07-02-2011 05:30 от LogRus » Записан

Странно всё это....
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #51 : 07-02-2011 21:37 » 

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #52 : 08-02-2011 04:58 » 

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

Странно всё это....
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #53 : 08-02-2011 09:07 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #54 : 08-02-2011 09:47 » 

Dimka, скорее первое, не так много людей интересуются lock-free, а тот кто интересуется обычно уже немного в теме
а конкретную статью можешь показать из тех, что тебе не приглянулись, я еще не все их прочёл Улыбаюсь
« Последнее редактирование: 08-02-2011 09:50 от Антон (LogRus) » Записан

Странно всё это....
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #55 : 08-02-2011 10:56 » 

Антон (LogRus), да любую бери. Это формат блога.
« Последнее редактирование: 08-02-2011 13:28 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #56 : 08-02-2011 13:03 » 

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

Странно всё это....
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #57 : 08-02-2011 13:49 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #58 : 09-02-2011 03:49 » 

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

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

Странно всё это....
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #59 : 09-02-2011 08:40 » new

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

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: 1 [2]  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines