[Kabdim 0]

Можно отсылку на труды классиков? Ну т.е. где бы эта концепция более подробно раскрывалась.

Это куцый огрызок от функционального программирования. Собственно ФП изучить стоит практически любому программисту для расширения кругозора, но не в виде таких постулатов. :rolleyes:

[sigmaN 0]

Собственно ФП изучить стоит практически любому программисту для расширения кругозора, но не в виде таких постулатов.

Вот именно поэтому и интересно было бы почитать классиков по данному вопросу

[Kabdim 0]

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

[xvr 12]

В современном софте разделяемой памяти быть не должно. Разделяемые должны быть высокоуровневые сущности, и то на худой конец.

Лучше вообще ничего не разделять. Указатель(ссылка) на обьект должен быть один единственный(в один момент времени), а все переменные должны быть const. К этому и стремимся.

Ой! Напоминает планы построения коммунизма :)

 

Да и если даже и с блокировками(например, когда аппаратная поддержка lock-free слабая или ее нет вовсе), то они очень короткие(на несколько инструкций, обычно до десяти,

Этого достаточно.

 

сама реализация традиционных мютексов и переключение контекста требует гораздо более длинных блокировок)

Вопрос не в длинне блокировки (она и в обычных мьютексах может быть кототкой), а в их принципиальном наличии

 

За пределами очередей блокировок нет. Это и есть то кардинальное отличие блокинга от нон-блокинга,

Для пользователя, тобышь программиста, блокировок нет и быть не может.

Опять ой! Это опять не так. Например, переменная counter меняется в 2х задачах:

// Low priority -
if (counter > 10)
{ 
...
  counter -= 10;
...
}

// High priority
counter=5;

Если высокоприоритетная задача вытеснит низкоприоритетную после if, то после ее окончания и возобновления низкоприоритетной задачи, в counter в конце концов окажется -5, чего никогда не может случиться, если бы if выполнялся атомарно (или под заблокированными прерываниями). Что и требовалось доказать :)

 

Нет, если нет места, то строчка записи в очередь выкинет исключение или вернет ошибку. Такие ошибки надо обязательно обрабатывать, нормальные высоко-уровневые языки программирования(типа Rust) сами заставляют программиста это делать. Блокировок здесь нет.

Вы опять подменяете условия задачи на другие. Сделать неблокирующее помещение в очередь (в данном случае) позволит избежать deadlock'а. Но это совершенно не значит, что в SST вообще не может быть deadlock'а. дной постановке задачи (с блокирующим помещением в очередь) он есть. И в SST он никуда не денется.

 

Похоже вы не совсем понимаете, что такое deadlock. Он не является обязательной чертой мультпоточного програмирования. Это просто ошибка в проектировании работы с разделяемыми ресурсами. И SST не является гарантией того, что ошибки в таком проектировании не повесят программу.

 

 

Да и такого понятия, как чтение из очереди тоже надо опасаться и обходить стороной.

Код должен быть не вида: while((size=read(data)))process(data,size);

а должен быть такого вида: void on_data_available(const Data* data, int size){ process(data, size); }

Если ваш process захочет записать 3 байта в другую очередь (как в исходной задаче), то и ваш 'такой' код тоже повиснет

 

Это совсем другой стиль и мыслить надо здесь иначе.

Но второй код проще - не нужно создавать бесполезный цикл, не нужно выделять место под буфер(data), не нужно проверять ошибки(чтения), не нужно ничего читать, не нужно ждать, не нужно блокироваться.

Он и без вашего участия сам заблокируется :)

 

А вот это гораздо ближе к делу. В принципе - типичная задача для embedded, и решение ее должно уже быть готовое в виде некого шаблонного класса, которое нужно просто взять и подключить парой строчек.

Теперь сравните размер - 5 строк в исходном коде и более 10 в SST. А если вспомнить, что is_ready_to_receive_packet тоже мог ждать, то код еще вырастет

 

В реальном мире все иначе - любая практическая задача, а тем более работа с аппаратурой ложится на асинхронщину, как влитая.

Не любая, а с более менее простой структурой управления (в идеале вообще линейная) и с небольшим набором возможных состояний. Для МК это так. Для систем побольше, уже не так.

 

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

Дались вам эти циклы. Далеко не все из них состоит. И преимущество thread перед SST состоит не в том, что в thread программе можно написать бесконечный цикл, а в том, что thread сохраняет текущий контекст выполнения, включая стек вызовов со всеми переменными. В SST вам придется самому организовывать хранение контекста: переменные на внутренних переменных класса (или в захваченных лямбдой переменных), а положение в графе управления (call stack в thread) - явным дроблением и выделением всех возможных точек входа/выхода и переходов.

 

Наличие или отсуствие синхронизации, deadlock'ов и разделяемых переменных не играет никакой роли - и thread и SST модели делают это концептуально одинаково.

 

[brag 0]

Да, это все огрызки. С ними возимся не из за того, что не можем дорасти до нормального ФП, а из за того, что железо, с которым работаем -императивное и слишком слабое и нормальные ФП-языки на нем запустить пока не удается.

 

Опять ой! Это опять не так. Например, переменная counter меняется в 2х задачах:

Нет, в sst так писать нелься. Не должен counter меняться в 2х задачах.

 

Но это совершенно не значит, что в SST вообще не может быть deadlock'а. дной постановке задачи (с блокирующим помещением в очередь) он есть. И в SST он никуда не денется.

Пример ситуации можно, когда будет dead-lock?

 

Если ваш process захочет записать 3 байта в другую очередь (как в исходной задаче), то и ваш 'такой' код тоже повиснет

Почему это он повиснет? Он либо запишет 3 байта, либо не запишет. Как быть в случаи провала записи в очередь решает уже программист, обрабатывая ошибку записи.

 

Теперь сравните размер - 5 строк в исходном коде и более 10 в SST. А если вспомнить, что is_ready_to_receive_packet тоже мог ждать, то код еще вырастет

Ну это особенность языка, да и то большинство строк - комментарии :)

 

Не любая, а с более менее простой структурой управления (в идеале вообще линейная) и с небольшим набором возможных состояний. Для МК это так. Для систем побольше, уже не так.

Хотелось бы реальный пример такой задачи, мозг потренировать ;)

 

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

Это да. но хотелось бы реальную задачу, где именно сохранение контекста необходимо или сильно облегчало бы жизнь.

 

Наличие или отсуствие синхронизации, deadlock'ов и разделяемых переменных не играет никакой роли - и thread и SST модели делают это концептуально одинаково.

Да, одинаково, поэтому делают active-object pattern и тогда программа стает такая же, как бы она была написана на SST (если все вызовы асинхронные).

[xvr 12]

Да, это все огрызки. С ними возимся не из за того, что не можем дорасти до нормального ФП, а из за того, что железо, с которым работаем -императивное и слишком слабое и нормальные ФП-языки на нем запустить пока не удается.

С этим согласен на все 100%. Вот только не уверен, что когда нибудь появится такое железо, где можно будет напрямую ФП запустить :)

 

Вспоминается история с PicoJAVA. SUN решил, что если исполнение JAVA байт кода сделать напрямую в железе, то такая штука всех порвет. И сделал. А потом выяснилось, что обычный SPARC этот самый байт код успевает интерпретировать быстрее, чем спец процессор исполнять :(

Провал был грандиозный :cranky: Не все можно эффективно на железо положить :smile3046:

 

[brag 0]

Та мощный проц запросто под ФП идет, но я работаю в основном на embedded, cortex-ы там всякие, под них erlang хоть и есть, но ресурсов сжирает много, а под avr-образные вообще такого нет.

[xvr 12]

Нет, в sst так писать нелься. Не должен counter меняться в 2х задачах.

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

 

Пример ситуации можно, когда будет dead-lock?

Почему это он повиснет? Он либо запишет 3 байта, либо не запишет. Как быть в случаи провала записи в очередь решает уже программист, обрабатывая ошибку записи.

Так, расписываю подробно (думал, что и так понятно, но видимо нет)

process(input_queue, output_queue)
{
  input_queue.on_data_avail = function()
  {
    data = input_queue.get();
    var out[3], index=0;
    ...
    output_queue.on_space_avail = function()
    {
      if (index<3) output_queue.push(out[index++]);
      else output_queue.on_space_avail = NULL;
    }
  }
}

queue A, B;
process(A,B);
process(B,A);
A.push(<some data>)

Можем получить deadlock

 

Это да. но хотелось бы реальную задачу, где именно сохранение контекста необходимо или сильно облегчало бы жизнь.

Возьмите любую MT задачу размером более 10000 строк С/С++

 

[brag 0]

Возьмите любую MT задачу размером более 10000 строк С/С++

И переписать на SST? Так я таким и занимался, вышло отлично.

 

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

Этих примитив в современном коде нужно избегать, хотите верьте - хотите нет, но в каждой современной книге об этом написано и расписано почему.

Да, SST не умеет работать с такими примитивами, он заставляет программиста обходится без них, на то он и нужен ;)

 

Можем получить deadlock

process(input_queue, output_queue)
{
  input_queue.on_data_avail = function() // ок, установили обработчик на очередь B
  {
    data = input_queue.get(); // получили указатель на данные B. лучше бы он передавался в обработчик автоматически, ну да ладно.
    var out[3], index=0;
    ...
    output_queue.on_space_avail = function() // а так не делается.
// on_space_avail срабатывает один раз когда очередь переходит из состояния полностью заполненной к состоянию не полностью заполненной.
// этот код требует рефакторинга
// а если это событие будет возникать всякий раз, когда очередь не пуста, то получим 100%ную бесполезную загрузку процессора, так тоже делать нельзя.
    {
      if (index<3) output_queue.push(out[index++]); // тут недо было бы проверить на наличие ошибки, поскольку очередь A - конкурентная, кто-то другой мог уже туда что-то записать и там может не оказаться места.
      else output_queue.on_space_avail = NULL; // удалили обработчик - будет пропуск события. хорошо это или плохо - зависит от программиста
    }
  }
}

queue A, B;
process(A,B); // это бессмысленная строчка, тк input_queue.on_data_avail будет тут же переопределен следующей строкой. в данном примере эта строка не делает ничего
process(B,A); // а тут можно уже заглянуть по-глубже в код ф-ции process, там комменты для этой сторчки
A.push(<some data>) // конкурентная запись в очередь A(process -> output_queue) - норм, наши очереди это поддерживают.

Ну этот код вообще по моему не корректен для SST. трудно по нему сказать, как он должен был бы работать по задумке его автора.

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

[xvr 12]

Этих примитив в современном коде нужно избегать, хотите верьте - хотите нет, но в каждой современной книге об этом написано и расписано почему.

Да, SST не умеет работать с такими примитивами, он заставляет программиста обходится без них, на то он и нужен ;)

Т.е. SST это такая смирительная рубашка, которая ограничивает возможности програмиста?

 

Ну этот код вообще по моему не корректен для SST. трудно по нему сказать, как он должен был бы работать по задумке его автора.

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

То, что вы не видите потенциального deadlock'а, не значит, что его нет. В этом и проблема.

Deadlock будет при заполненных очередях. Когда в событии on_space_avail каждый процесс будет пытаться положить данные в очередь. Т.к. места в очереди нет (после 1го срабатывания on_space_avail) оба процесса будут ожидать пока освободится место для 2го и 3го байта. Но это место никогда не освободится, т.к. только эти самые процессы могут освободить место, читая из очередей. А они не могут, т.к. они не доработали до конца - не все данные помещены в очереди. Deadlock

 

 

[brag 0]

Т.е. SST это такая смирительная рубашка, которая ограничивает возможности програмиста?

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

 

То, что вы не видите потенциального deadlock'а, не значит, что его нет. В этом и проблема.

Deadlock будет при заполненных очередях. Когда в событии on_space_avail каждый процесс будет пытаться положить данные в очередь. Т.к. места в очереди нет (после 1го срабатывания on_space_avail) оба процесса будут ожидать пока освободится место для 2го и 3го байта. Но это место никогда не освободится, т.к. только эти самые процессы могут освободить место, читая из очередей. А они не могут, т.к. они не доработали до конца - не все данные помещены в очереди. Deadlock

Так процесс всего один - process(B,А ) , и то какой-то странный. Первый(process(A, B ) ) не делает ничего, его можно смело закомментировать, как по мне.

Какую задачу должен решать этот код? Я попытаюсь сделать правильное решение.

deadlock можно и в одном потоке получить :) только какой в этом смысл?

[xvr 12]

Равно, как и любой высокоуровневый язык.

Ага, но такое ограничение - это черезчур :)

 

Так процесс всего один - process(B,А ) , и то какой-то странный. Первый(process(A, B ) ) не делает ничего, его можно смело закомментировать, как по мне.

Почему это? Работают оба процесса. Попробую написать в виде thread кода, в SST переведете сами

void process(queue& inp, queue& out)
{
  for(;;)
  {
   char data = inp.get(); // Can block until data is available
   .... // calculate data to send
   char a1, a2, a3;
   out.put(a1); // Can block until space is available
   out.put(a2); // Can block until space is available
   out.put(a3); // Can block until space is available
  }
}

queue A, B;

run_task( [] (process(A,B);} );
run_task( [] (process(B,A);} );
A.put(1);

 

[brag 0]

Ну такое переливание делается как-то так. deadlock-a нет, есть ошибка записи, которую нужно обработать.

void process(queue& inp, queue& out){
    inp.on_ready_read = [](const Data* data){
        // process the data
        // ....
        Data data2(...);
        // ....
        if(!out.push(data2, [](){
            inp.signal_data_processed();
        })){
            throw queue_full_error("Queue full");
            // or process an error in another way
            // resolve signal_data_processed on inp
        }
    };
}

queue A, B;

process(A,B);
process(B,A);
A.push(1);

Если этого не сделать, то сообщения перестанут обрабатываться, но эту ситуацию можно исправить на горячую, в отличии от dead-locka на мютексах.

 

[xvr 12]

// or process an error in another way

// resolve signal_data_processed on inp

Именно, что 'another way'. Нужно поставить событие на освобождение места в out и в нем пытаться записать (именно это делает оригинальный код)

 

Если этого не сделать, то сообщения перестанут обрабатываться,

Это и есть deadlock :rolleyes:

но эту ситуацию можно исправить на горячую, в отличии от dead-locka на мютексах.

deadlock на мьютексах тоже можно разбить на горячую, проблема в том, что система уже находится в некорректном состоянии (что в этом примере, что в мьютексах). Для избежания deadlock'ов нужно перепроектировать систему, а не ломать их 'на горячую'. И это относится как к обычным thread'ам, так и к SST

 

Так что SST от deadlock'ов не спасает :rolleyes:

 

NB. Уточнение во избежание недопонимания - dedlock это не только взаимная блокировка мьютексов, но и любая взяимная блокировка на каких то ресурсах. От обычной блокировки (например, если пытаться писать в очередь из которой никто не читает) отличается тем, что возникает очень спорадически и невоспроизводим.

NNB. Еще уточнение - 'спасает от dedlockов' обозначает принципиальную невозможность возникновения dedlock'ов в любом случае, а не их отсутвие при правильно написанной программе.

 

 

[brag 0]

Именно, что 'another way'. Нужно поставить событие на освобождение места в out и в нем пытаться записать (именно это делает оригинальный код)

Переполнение очереди - это аналог переполнения стека. Только в первом случаи его можно резолвить софтово, а во втором - это крах системы.

При проектировании блокинг-модели надо дать заведомо достаточно стека. При проектировании SST - заведомо достаточно места в очереди. То есть избегать их переполнения.

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

 

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

 

Еще уточнение - 'спасает от dedlockов' обозначает принципиальную невозможность возникновения dedlock'ов в любом случае, а не их отсутвие при правильно написанной программе.

Ну такой deadlock(когда система перестает обрабатывать события) можно получить и в одном потоке и даже в функциональном программировании.