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

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

ru
Offline Offline

« : 05-02-2010 06:46 » 

День добрый! Вот набрел на такое понятие как lock-free синхронизация. Суть объяснена например здесь: http://developer.amd.com/documentation/articles/pages/125200689.aspx http://www.audiomulch.com/~rossb/code/lockfree/ Меня весьма заинтересовал этот вопрос, поскольку по роду деятельности тоже приходится часто разрабатывать хитрозамученные многопоточные проекты, причем синхронизация и масштабируемость (в случае, если используется целый пул потоков, с числом потоков меняющегося в динамике) доставляет прилично головной боли. В сквязи с этим интересно есть ли у кого опыт использования такого рода синхронизации, а особенно lock-free структур, и каковы результаты.
ЗЫ Интересно, что в ядрах 2.6 линукса используется так называемый RCU механизм, по сути один из приемов lock-free синхронизации
« Последнее редактирование: 05-02-2010 07:25 от dimedrol » Записан

Как говориться, cемь бед - один Reset Улыбаюсь
sss
Специалист

ru
Offline Offline

« Ответ #1 : 05-02-2010 07:23 » 

dimedrol, нельзя малям по русски объяснить - что за lock-free? Не хочется сильно вкупаться, потому что полезность не ясна.. Кстати вторая ссылка не работает.... И вообще - привет, давно не было...
 
Записан

while (8==8)
dimedrol
Помогающий

ru
Offline Offline

« Ответ #2 : 05-02-2010 07:51 » 

Привет, sss, сколько лет сколько зим, действительно давно уже не заходил. Ссылку поправил Улыбаюсь Пусть у нас есть структура данных, доступ к ней разделяемый между кучей нитей , причем число процессоров в системе может быть произвольным. Расмотрим ситуацию 1.
1) Динамический список элементов, для кореектного удаления или вставки элемента используем синхронизацию через какой-либо примитив синхронизации - чревато дедлоками, если например одна нить захватити синхронизацию и помрет. Однако можно используя функцию атомарного сравнения и замены (на x86 cmpxchg, или InterlockedCompareExchange) потсорить алгоритм работы списка, без стандартных примитивов синхронизации, при этом работа сосписком будет происходить корректно в разделяемой среде, дедлоки ВПРИНЦИПЕ не возможны ни при каких обстоятельствах + фантастически низкие издержки на синхронизацию, которые практически не растут с увеличением числа програмных потоков или физических процессоров на которых они исполняются + можно забыть об инверсии приоритетов и прочие специфические прелести..
2) RCU (Read-Copy-Update) Пусть есть структура критичная по части синхронизации, которую чаще читают чем пишут. Логично использовать какой-либо примитив синхронизации для доступа к ней, но мы поступим хитрее: заведем глобальный указатель на структру данных str *p; Определим операцию чтения структуры, как атомарное присваивание этого указателя переменной b, и дальнейшее его использование в читающей нити. Для записи будет иначе - выделяем память под новый экземпляр структуры str, изменяем его как нам надо и атомарно присваиваем (InterlockedExchange) значению указателя p на нашу новую структуру, при этом все последующие читатели будут работать уже с этой копией. Разумеется необходимо предусмотреть механизм сборки мусора, так как предыдущее значение указателя затирается, а память надо бы освободить. Однако получаем опять-таки все перечисленные в п1 плюсы.

Вот это "вкратце суть". Конечно есть кое-какие фундаментальные проблемки этого подхода, но в целом очень интересно Улыбаюсь На данный момент я нарыл реализацию lock-free FIFO, FILO, stack, list, и аналоги stl-вского vector-а. Кстати, нашел довольно старую, но интересную статью о разработке игрового движка от valve http://arstechnica.com/gaming/news/2006/11/valve-multicore.ars
« Последнее редактирование: 05-02-2010 07:55 от dimedrol » Записан

Как говориться, cемь бед - один Reset Улыбаюсь
sss
Специалист

ru
Offline Offline

« Ответ #3 : 05-02-2010 08:14 » 

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

while (8==8)
sss
Специалист

ru
Offline Offline

« Ответ #4 : 05-02-2010 08:39 » 

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

 CLockCS l ( &m_csState) -  умная крит. секция....  Подсмотрено в DirectShow.

Код:
void CMessenger::ExecuteHandlers( PMesssage pMesssage)
{
  size_t       stCount;
  PPtrNode     pCurr;
  bool         bHandled      = false;
  size_t       stIdx         = 0;
  PMsgFuncNode *StepHandlers = NULL;
  try
  {
    //Создаем список обработчиков текущей петли и закрепляем их
    {
      CLockCS l ( &m_csState);
      stCount = m_Handlers.Count;
      if ( stCount)
      {
        StepHandlers = (PMsgFuncNode*) MemAlloc( stCount * sizeof( PMsgFuncNode));
        pCurr = m_Handlers.First;
        while ( pCurr)
        {
          StepHandlers[stIdx] = (PMsgFuncNode) pCurr->Data;
          StepHandlers[stIdx]->AddRef();
          stIdx++;
          pCurr = pCurr->Next;
        }
      }
    }
    //Выполняем обработчики       
    for ( size_t i = 0; i < stCount; i++)
    {
      //Любой из них мог вызвать Terminate!!!
      if ( m_State == State_Running && bHandled == false && StepHandlers[i]->Enabled)
      {
        {
          // Закрепляем, что бы связанный с контекстом HandlerContext
          // обломался со своим удалением до выполнения обработчика
          CLockCS l( &StepHandlers[i]->m_csState);
          if ( StepHandlers[i]->Enabled)
          {
            bHandled = StepHandlers[i]->HandleMessage( pMesssage);
          }
        }
      }
      StepHandlers[i]->Release();
    }
    if ( StepHandlers) MemFree( StepHandlers);
  }
  catch( EExcept* e)
  {
    if ( StepHandlers) MemFree( StepHandlers);
    e->Release();
  }
}
Записан

while (8==8)
Антон (LogRus)
Глобальный модератор

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


WWW
« Ответ #5 : 05-02-2010 08:43 » 

dimedrol, я уже несколько раз давал ссылки из тех что я использую (читаю)
http://groups.google.com/group/lock-free
http://herbsutter.wordpress.com
http://highscalability.com/
http://software.intel.com/ru-ru/parallel/
http://www.threadingbuildingblocks.org/

ссылки конечно здорово, но
.............используем синхронизацию через какой-либо примитив синхронизации - чревато дедлоками..........
имхо, кривые руки
.........дедлоки ВПРИНЦИПЕ не возможны ни при каких обстоятельствах..............
собственно не избавляет от кривых рук

...........заведем глобальный указатель на структру данных str *p; .................
какая гадость

кроме-то того, lock-free требуют очень аккуратного проектирования и очень тщательного тестирования
http://software.intel.com/ru-ru/articles/interview-with-dmitriy-vyukov-the-author-of-relacy-race-detector-rrd/

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

Странно всё это....
dimedrol
Помогающий

ru
Offline Offline

« Ответ #6 : 05-02-2010 08:50 » 

Насчет предсказуемости кода - согласен абсолютно. Насчет текущих читаетелей - они будут работать посути со своей локальной копией данных, пока не перечитают измененный вариант, такой механизм успешно работает, как пример - RCU в линуксовом ядре: выдержка из книги Бовет Д.Чезати М. Ядро Линукс
Цитата
Поскольку читающий тракт почти ничего не делает для предотвращения
конфликтов одновременного обращения, мы вправе ожидать, что вся работа
перекладывается на пишущий тракт. Действительно, когда пишущему тракту
нужно обновить структуру, он разыменовывает указатель и делает копию
всей структуры. Затем он обновляет копию. Закончив эту операцию, пишу-
щий тракт изменяет указатель на структуру так, чтобы он ссылался на обнов-
ленную копию. Поскольку изменение значения указателя является атомар-
ным действием, любой читающий или пишущий тракт видит либо старый
экземпляр структуры, либо новый, и никакая порча данных невозможна. Од-
нако при таком подходе необходим барьер памяти для гарантии того, что об-
новленный указатель будет виден на других процессорах только после моди-
фикации структуры данных. Такой барьер памяти неявно устанавливается,
если в комбинации с обновлением копии используется спин-блокировка,
предотвращающая параллельное выполнение пишущих трактов.
Реальная проблема с техникой обновления копии для чтения заключается в
том, что старая копия не может быть освобождена сразу после того, как пи-
шущий тракт изменит указатель. На практике читающие тракты, работавшие
со структурой, когда пишущий тракт начал процедуру обновления, могут все
еще читать старую копию.
Вполне рабочий подход, если вдуматься - как правило, то что читатель будет некоторое время работать со старой копией данных, никак не будет отражаться на работу системы.
В двнном случае больше интересен новый принцип синхронизации, который, кстати судя по гуглу уже находит применение в системах реального времени и высокопроизводительных системах (особенно многопроцессорных).
Вообще, погуглив lock-free я удивился числу научных статей на тему подобных алгоритмов, общие выводы сводятся к перспективности таких методов, особенно для многопроцессорных систем. Причем поддержку воплощают и в железе, вот подтверждение моих слов http://www.amd64.org/fileadmin/user_upload/pub/epham08-asf-eval.pdf
ИМХО за этим подходом будущее, число ядер и степень параллельности вычислений растут, неизбежен момент, когда издержки на привычные способы синхронизации станут неприемлемы.. возможно будущие виды микропроцессорных систем уже будут включать аппаратную поддержку атомарного доступа к тем или иным блокам памяти.. впринципе она уже есть Улыбаюсь на х86 инструкции cmpxchg cmpxchg8b и аналогичные, только большей разрядности, для 64бит систем, на других процессорах аналогичные вариации.
Записан

Как говориться, cемь бед - один Reset Улыбаюсь
dimedrol
Помогающий

ru
Offline Offline

« Ответ #7 : 05-02-2010 08:58 » 

LogRus спасибо за ссылки! да, дедлоки - это как правило кривые руки Улыбаюсь И все-таки мне интересно, кто-нибудь применял это в реальных проектах? Как ощущения? Улыбаюсь Каковы результаты?
Записан

Как говориться, cемь бед - один Reset Улыбаюсь
sss
Специалист

ru
Offline Offline

« Ответ #8 : 05-02-2010 08:59 » 

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

while (8==8)
RXL
Технический
Администратор

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

WWW
« Ответ #9 : 05-02-2010 09:05 » 

Цитата
Literature up to the turn of the 21st century used "non-blocking" synonymously with lock-free.

Очередная подмена терминов для большей запутанности?

http://en.wikipedia.org/wiki/Read-copy-update
« Последнее редактирование: 05-02-2010 09:23 от RXL » Записан

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

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


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

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

Странно всё это....
sss
Специалист

ru
Offline Offline

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

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

while (8==8)
dimedrol
Помогающий

ru
Offline Offline

« Ответ #12 : 05-02-2010 09:27 » 

Мне тоже как-то не подворачивается проект на котором бы пришлось опробовать новенькое, , хотя в перспективе кое-что вырисовывается поэтому и спрашиваю,а еще интерес взял по этой теме Улыбаюсь  Лично сам, стараюсь  минимизировать объем разделяемых данных, чтобы побольше пользоваться Interlocked функциями для доступа к ним - но это в критических случаях, обычно и стандартные примитивы синхронизации устраивают.
Записан

Как говориться, cемь бед - один Reset Улыбаюсь
Антон (LogRus)
Глобальный модератор

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


WWW
« Ответ #13 : 05-02-2010 09:52 » 

в одной из статей Саттер (а может и не он Улыбаюсь ) выдвинул такую мысль, что однопоточность в многопоточном приложении, то именно, то что нужно, т.е. чем длиннее и не изолированней команды исполняемые потоками, тем лучше.
Записан

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

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

« Ответ #14 : 05-02-2010 16:11 » 

Что-то я не уловил, чем описанное RCU выгоднее сложной блокировки типа "много читателей - один писатель". Тем, что читатели не блокируются, пока писатель пишет? А как эта RCU обрабатывает ситуацию с многими писателиями? Ведь, пока один работает с одной копией, другой уже может успеть заменить исходные данные на собственные. Из приведённого отрывка книги я вижу, что это вопрос неоднозначный и "проблемный".

Но главное, чего я не уловил: где выгода? В избавлении от 1-й машинной инструкции типа cmpxchg? И каков прирост производительности?
Записан

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

ru
Offline Offline

« Ответ #15 : 09-02-2010 06:32 » 

Ну, если требуется очень частый доступ к разделяемым данным в ядре - стандартная синхронизация будет вносить большие издержки видимо. А выгода в том, что одной стандартной инструкцией cmpxchg мы можем максимум 4 или 8 байтами оперировать по сути, а RCU опрериует целыми структурами, вроде есть даже такое понятие Lock-free структуры. Заодно вот еще отрывок из той же книжки:
Цитата
Обновление копии для чтения (Read-copy update, RCU) является еще одним
приемом синхронизации, разработанным для защиты структур, к которым
несколько процессоров обращается, в основном, для чтения. RCU позволяет
нескольким пишущим и читающим трактам работать одновременно (это шаг
вперед, по сравнению с seqlock-блокировками, позволяющими работать толь-
ко одному пишущему тракту). Более того, техника обновления копии для
чтения свободна от блокировок, т. е. в ней нет блокировки или счетчика, ко-
торые бы совместно использовались всеми процессорами. Это огромное пре-
имущество перед спин-блокировками чтения/записи и seqlock-блокировками,
которые требуют больших накладных расходов из-за снупинга и порчи строк
кэша.
Каким образом применение техники RCU позволяет достичь удивительных
результатов при синхронизации нескольких процессов без совместно исполь-
зуемых структур данных? Основная идея состоит в ограничении области дей-
ствия RCU:
□ С помощью RCU можно защищать только динамически выделенные дан-
ные, доступные через указатели.
□ Никакой управляющий тракт ядра не может "спать" внутри критической
области, защищенной с помощью RCU.


Цитата
Обновление копии для чтения является нововведением в Linux 2.6; оно ис-
пользуется в сетевом слое и в виртуальной файловой системе.
Впринципе, кому интересно, можно и поглядеть в самих исходниках ядра Улыбаюсь лично у меня пока руки не доходят никак.
Записан

Как говориться, cемь бед - один Reset Улыбаюсь
Антон (LogRus)
Глобальный модератор

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


WWW
« Ответ #16 : 09-02-2010 07:23 » 

вот кое-что интересное
http://groups.google.com/group/lock-free/browse_thread/thread/c8e3201da4a6a300
Записан

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

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

« Ответ #17 : 09-02-2010 08:56 » 

Цитата: dimedrol
Каким образом применение техники RCU позволяет достичь удивительных
результатов при синхронизации нескольких процессов без совместно исполь-
зуемых структур данных? Основная идея состоит в ограничении области дей-
ствия RCU
Т.е., развивая мысль, идеально быстрая синхронизация наблюдается там, где не нужна никакая синхронизация Улыбаюсь

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

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

ru
Offline Offline

« Ответ #18 : 09-02-2010 08:58 » 

LogRus, классная ссылка интересный принцип Улыбаюсь кстати в форуме там еще одна ссылка на статьи http://research.sun.com/scalable/pubs/index.html
Dimka, разумеется надо вдумчиво планировать синхронизацию, даже если она допускает столько свободы, сколько обещает lock-free.
Записан

Как говориться, cемь бед - один Reset Улыбаюсь
sss
Специалист

ru
Offline Offline

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

dimedrol, а ты понял смысл? Просвяти пожалуйста...

Код:
while (n->next_ == 0)
                            SwitchToThread();

Мне это напомнило мои коды из детства, когда я пытался синхронизироваться вокруг глобального флага....
Записан

while (8==8)
sss
Специалист

ru
Offline Offline

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

Кстати, вот пример... Сто потоков прошли условие n->next_ == 0 одновременно... И чё? Извиняюсь, не прошли...
Вообще мне все это представляется попытками написать свои объекты диспетчеризации. Флаг в руки....
« Последнее редактирование: 09-02-2010 09:57 от sss » Записан

while (8==8)
RXL
Технический
Администратор

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

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

Dimka,

1. На SMP работает нормально: как только выполняется запись, она распространяется в кеш L0 и L1 процессора, а остальные ядра/процессоры перед чтением данной ячейки памяти должны провести валидацию с чужими кешами - тут то и найдется изменение.

2. Согласен, что это разрушительно. Но для чего в SQL существует READ COMMITED? — Ведь оно тоже не поддерживает целостность данных на изменение. Выходит, что для производительности! Значит, есть задачи, для которых старые данные не важны.

Для поддержания целостности с сохранением достоинств RCU можно скомбинировать:

struct
{
  mutex mtx;
  unsigned int version;
  data_t *data;
}

1. Копирование.
1.1. Блокируем.
1.2. Копируем указатель данных.
1.3. Копируем версию.
1.4. Снимаем блокировку.
1.5. Копируем данные.
2. Обработка.
3. Обновление.
3.1. Блокируем.
3.2. Сверяем версию:
  не равно - возвращаемся к п.1.2.
  равно - увеличиваем номер версии.
3.3. Подменяем указатель на данные.
3.4. Снимаем блокировку.

Это как раз эквивалент REPEATABLE READ.

« Последнее редактирование: 09-02-2010 10:49 от RXL » Записан

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

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

« Ответ #22 : 09-02-2010 23:34 » 

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

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

ru
Offline Offline

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

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

while (8==8)
RXL
Технический
Администратор

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

WWW
« Ответ #24 : 10-02-2010 05:21 » 

Думаю, что каждой задаче - свой алгоритм.
Записан

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

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

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

Цитата: sss
Более перспективным считаю направление, в котором параллельные задачи выполняются одним потоком последовательно...
Кстати, хотелось бы поподробнее.

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

Кто про это может рассказать кратко, но по существу? Лучше с небольшим примерчиком кода.
« Последнее редактирование: 10-02-2010 08:36 от Dimka » Записан

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

ru
Offline Offline

« Ответ #26 : 10-02-2010 08:45 » 

Dimka, да это мне просто в голову приходит все чаще и чаще... Не знаю, интуитивно что ли.... Я смотрю на то, как отмёрли шлейфы IDE и прижились 3 провода SATA... Как пакетный принцип передачи в телефонии вытесняет канальный и т.д. и т.п...
Записан

while (8==8)
RXL
Технический
Администратор

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

WWW
« Ответ #27 : 10-02-2010 08:59 » 

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

Телефонию вообще странно тут приводить - она не коррелирует.  Ее изменение целиком объясняются переходом на цифровой способ доставки сигналов и информации.

В условиях многопроцессорности/многопоточности выгоднее как раз многозадачность. И чем реже происходит синхронизация (читай - блокировка), тем выгоднее.
« Последнее редактирование: 10-02-2010 09:03 от RXL » Записан

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

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


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

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

не явную синхронизацию кэшей тоже считаем Улыбаюсь
Записан

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

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

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
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 » 

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

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

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

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

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines