Простые и неправильные хамелеоны
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 01.05.07 08:12
Оценка: 88 (15) +1
Или небольшая история, подтверждающая известный афоризм о том, что любая сложная проблема имет очевидное, простое и красивое неправильное решение, на примере реализации теста производительности chameneos, в ходе которой в очередной раз проявились ужасы многопоточного программирования и еще раз довелось столкнуться с задачей, проверка решения которой гораздо важнее и сложнее, чем получение самого решения.

Исходная точка и условие задачи

Началось все с сообщения
Автор: Lazy Cjow Rhrr
Дата: 24.04.07
, в котором приводилось решение одной и той же задачи на Java и на Haskell. Глядя на компактный и совершенно непонятный мне код Haskell-варианта я почему-то подумал, что на D можно будет сделать похожее по лаконичности решение. Благодоря помощи Lazy Cjow Rhrr я получил условие самой задачи в виде текстового описания:
* нужно создать четырех конкурентных (в смысле каждый живет в своем потоке) хамелеонов разных цветов (синий, красный, желтый, синий);
* каждый хамелеон должен регулярно приходить на место встречи и встречаться там с другим хамелеоном. Если на месте встречи еще никого нет, пришедший первым хамелеон должен подождать второго;
* при встрече хамелеоны должны соответствующим образом поменять свои цвета. При вычислении нового цвета хамелеона нельзя использовать арифметические вычисления -- только if/else, switch/case или pattern-matching;
* после того, как на месте встречи образуются N пар, каждый хамелеон должен "пожухнуть" (получить специальный цвет FADED), сообщить количество встреченных лично им хамелеонов и завершить свою работу.
В качестве результата работы программа должна печатать сумму сообщенных каждым хамелеоном встреч. Например, для N=100 результатом программы должно быть 200.

Гранаты не той системы...
...или не стоит приступать к программированию на больную голову

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

Первые признаки того, что все идет не так, появились сразу. Почему-то я долго не мог понять условия задачи. Из-за чего рассматривал решения на Java, на Scala и оригинальное решение на D с сайта The Great Computer Language Shootout. Причем, чем дольше я смотрел на D-шную реализацию, тем меньше понимал, почему ее посчитали правильной реализаций. В подобных сомнениях я пребываю до сих пор. От окончательного вывода меня отделяет лишь то, что я никогда не работал с Unix-овыми семафорами и, поэтому, могу не понимать каких-то их особенностей.

Например, я не понимаю в методе MeetingPlace.OtherCreaturesColour:
    private Colour OtherCreaturesColour(Colour me)
    {
        Colour other = Colour.faded;

        sem_wait(&mustWait);
        if(firstCall)
        {
            if(n)
            {
                first = me;
                firstCall = false;
/*1*/           sem_post(&mustWait);
                other = second;
                n--;
            }
            sem_post(&mustWait);
        } else {
            firstCall = true;
/*2*/       second = me;
            other = first;
        }

        return other;
    }

одной вещи: каким же образом пришедший первым хемелеон ожидает прихода второго хамелеона. Ведь функция sem_post не блокирует нить первого хамелеона. Поэтому, когда первый хамелеон в точке 1 позволяет еще одному хамелеону войти на место встречи, нет никаких гарантий, что второй хамелеон успел пройти точку 2. Так что здесь, на мой взляд, явная ошибка, но к этому я еще вернусь.

Особенностью текущей версии стандарной библиотеки Phobos в языке D является то, что в ней отсутствуют такие базовые вещи для организации синхронизации нитей, как семафоры, условные переменные или, на худой конец, события. Есть возможность момечать методы как synchronized, но у объектов нет методов wait и notify, как в Java. Поэтому решение с Language Shootout использовало специфические для Unix-а POSIX-семафоры. Поскольку я использовал DMD под Windows, а под Linux-ом у меня DMD нет, то естественным образом встал вопрос о том, чтобы делать свою реализацию на основе библиотеки Tango.

Первые успехи?

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

Русским языком логику поведения хамелеонов можно описать так:
* приходит первый на место встречи, пишет свой цвет на записке и кладет записку в специальный ящик (MeetingPlace.first_) и ложится спать в ожидании второго;
* приходит второй, берет цвет первого из его ящичка, пишет своей цвет на второй записке и опускает записку в другой ящичек (MeetingPlace.second_);
* уходя второй хамелеон пинает первого, мол хватит уже спать;
* проснувшись от пинка певый берет записку второго и уходит, освобождая место для следующей пары хамелеонов.

Программа вроде бы работала. Хотя иногда подвисала. Попытки найти причину подвисаний привели к появлению в реализации MeetingPlace.meet вот такого if:
if( remaining_ > 0 )
  {
    // bla-bla-bla
  }

вместо
if( remaining_ ) ...

поскольку remaining_ по каким-то неведомым мне причинам уходил в минус (?!) Нифига себе оптимизатор у DMD, подумал я, вообще проверки выбрасывает. И просто написал remaining_>0 вместо того, чтобы разобраться в чем же дело. Ну нельзя программировать на больную голову.

Так вот программа вроде бы работала, считала все довольно шустро. Иногда были небольшие разбежки в результатах. Например, при N=1000000 можно было получить и 2000000, 2000002 или 20000004. Опять же, догадаться, что поскольку о каждой встрече будут отчитываться два хамелеона и результат всегда должен быть 2N, я вовремя не смог.

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

Тихо шифером шурша крыша едет не спеша

После небольшой переделки получилось сие творение. Принцип работы состоит в том, что MeetingPlace теперь содержит только необходимые для проведения встречи данные: мутекс, условную переменную, количество оставшихся встреч и указатель на блок памяти, который будет использоваться очередной парой для обмена цветами (MeetingPlace.swappedColor_).

Первый хамелеон приходит на место встречи, видит, что swappedColor_ равен null, понимает, что он первый. В swappedColor_ помещается указатель на локальную переменную с собственным цветом. И засыпает.

Приходит второй хамелеон, видит, что swappedColor_ не равен null, считывает из нее цвет первого, записывает свой цвет, пинает первого и уходит.

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

если кто-то догадался, просьба помолчать

Все работает. Разбежка в результатах на больших N проявляется. Но не это страшно. Иногда (где-то на седьмом-восьмом старте) на N=1000000 программа зависает, отжирая по 100% процессора. А вот на значении N=40000 вычисление иногда затягивается на десятки секунд, но завершаются с какими-то фантастическими результатами:
bash-3.2$ time ./my_chameneous 40000
creaturesMeet_: 2579283
creaturesMeet_: 2093332
creaturesMeet_: 2178625
creaturesMeet_: 2290491
9141731

real    0m11.546s
user    0m0.031s
sys     0m0.016s

Откуда берется более 9 миллионов встреченных хамелеонов? Не плодятся ли они там в программе сами по себе? А кто знает:
bash-3.2$ time ./my_chameneous 40000
creaturesMeet_: 40000
creaturesMeet_: 40000
creaturesMeet_: 40000
creaturesMeet_: 0
creaturesMeet_: 0
80000

real    0m0.281s
user    0m0.046s
sys     0m0.015s

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

Помятуя о странном поведении оптимизатора с выбрасыванием проверок вида if(remaining_), я описал возникшую проблему в форуме Tango и лег спать. Надеясь, что утро вечера мудренее.

И оно-таки мудренее

Не получив никаких вразумительных ответов от разработчиков Tango я понял, что спасение утопающих дело рук самих утопающих. Поэтому искать ошибку нужно самому.

С утра я уже не верил в наличие таких серьезных багов в компиляторе DMD. Мысли мои крутились вокруг того, что либо я работая с указателями кому-то что-то затираю. Либо мои манипуляции с указателями на локальные объекты сводят с ума сборщик мусора, который разработчики Tango приделывали к D сами. Но посольку никаких противоправных действий со своей стороны я не видел, то я не придумал ничего лучше, как сделать аналог этой программы на C++. Благо Tango много чего скопировало из ACE, поэтому реализация теста на C++ и ACE практически 1 в 1 получилась всего за полчаса.

Каково же было мое удивление, когда C++ версия на N=40000 вела себя так же, как D-шная!

Где же была зарыта собака

Я не знал, портят ли мои манипуляции с указателями в D, но в корректности работы с указателями в C++ я был уверен. Значит дело было в самом алгоритме. Но где именно?

Я не ограничивал количество хамелеонов, которые могли заходить на место встречи в качестве "второго", т.е. пока первый хамелеон спит или просыпается после очередного пинка.

Хамелеоны висят на одном мутексе

Все дело в том, что перед местом встречи тусуются все не попавшие туда хамелеоны. Вход на место встречи им перекрывает мутекс (MeetingPlace.lock_) который сейчас захвачен вторым хамелеоном (именно вторым, поскольку первый освободил его уснув на MeetingPlace.condition_). Я ошибочно предполагал, что когда сработает MeetingPlace.condition_, первый хамелеон вновь захватит его первым. Не тут-то было! Мутекс мог захватить любой из ожидавших своего часа вне места встречи хамелеонов. И в этом случае второй хамелеон автоматически становился новым вторым. А затем опять первых хамелеон мог "пролететь" мимо мутекса и мутекс мог быть отдан очередному второму. Именно это и приводило к появлению такого большого количества встреч -- первый хамелеон мог встретиться сразу с несколькими вторыми и все это осуществлялось в рамках одной итерации по отношению к MeetingPlace.remaining_.

Проверить это предположение оказалось не сложно. Достаточно было сделать что-то такое:
    run()
      {
        while( true )
          {
            Color other = my_;
            scope localLock = new ScopedLock( meetingPlace_.lock_ );
            if( meetingPlace_.remaining_ )
              {
                static bool repeated_second = false;
                if( !meetingPlace_.swappedColor_ )
                  {
                    meetingPlace_.swappedColor_ = &other;
                    repeated_second = false;
                    meetingPlace_.condition_.wait();
                    meetingPlace_.swappedColor_ = null;
                    --meetingPlace_.remaining_;
                  }
                else
                  {
                    assert( !repeated_second, "Repeated Second Chameneos!!!" );
                    repeated_second = true;
                    other = *meetingPlace_.swappedColor_;
                    *meetingPlace_.swappedColor_ = my_;
                    meetingPlace_.condition_.notify();
                  }

                localLock.release;
                if( FADED != other )
                  {
                    my_ = complement( other );
                    ++creaturesMeet_;
                  }
              }
            else
              break;
          }
      }


Пути исправления

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

Либо можно использовать счетчик количества хамелеонов на месте встречи и еще одну условную переменную, которая будет разрешать вход на место встречи новым хамелеонам. Вот этот вариант. (С++ный близнец.)


В результате

Все заработало. Без каких либо претензий к оптимизатору и разбежек в результатах.

Случай, когда тестирование важнее реализации

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

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

Записка с цветом от неизвестно кого

Пришло время вернуться к D-шной реализации с Language Shootout. Я получил возможность поиграться с ней поскольку Sean Kelly, один из разработчиков Tango, сделал ее порт на Tango. Если модифицировать код MeetingPlace вот так:
class MeetingPlace
{
    private static Semaphore mustWait;
    private Colour first, second;
    private bool firstCall = true;
    private int n;
    private bool second_was_here = false;

    this(int maxMeetings)
    {
        n = maxMeetings;
        mustWait = new Semaphore(1); //sem_init(&mustWait;,0,1);
    }

    private Colour OtherCreaturesColour(Colour me)
    {
        Colour other = Colour.faded;

        mustWait.acquire(); //sem_wait(&mustWait;);
        if(firstCall)
        {
            if(n)
            {
                first = me;
                firstCall = false;
                second_was_here = false;
                mustWait.release(); //sem_post(&mustWait;);
/*3*/           assert( second_was_here, "second must was be here" );
                other = second;
                n--;
            }
            mustWait.release(); //sem_post(&mustWait;);
        } else {
            firstCall = true;
            second = me;
            second_was_here = true;
            other = first;
        }

        return other;
    }
}

то assert в точке 3 срабатывает. Т.е., как я и ожидал, первый хамелеон пишет записку со своим цветом, кладет в ящик, разрешает вход на место встречи второму хамелеону. Затем, никого не ожидая, берет записку с цветом второго хамелеона и уходит. Но чья же это записка, если второй хамелеон на месте встречи еще не появился? Вероятно, это мусор, который остается на месте встречи от предыдущих тестов

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

Зачем нам все четыре хамелеона? Можно обойтись и меньшим количеством
...или хамелеон родился пожухшим.

С самого начала Lazy Cjow Rhrr обратил мое внимание, что в Java и в Scala программах цвета для хамелеонов задаются не так, как требовалось:
  val colours = List(RED, BLUE, YELLOW, FADED)
  ...
      val creatures = for(val x <- colours) yield {
        val cr = new Creature(mp, x);
        cr.start();
        cr
      }

т.е. последний хамелеон сразу создается с финальным цветом FADED. И как же он участвует в жизни остальных хамелеонов? А никак:
    override def run() {
      try {
        while(colour != FADED) {
          mp.meet(this)
          if(other == FADED) {
            colour = FADED
          } else {
            met = met + 1
            colour = complement(other)
          }
        }
      } catch {
        case e:InterruptedException => () // Let the thread exit
      }
    }

в его нити не выполняется ничего, кроме первой проверки условия в while. После чего хамелеон тихо помирает, вероятно, от врожденного уродства. В чем не сложно убедиться, если добавить в конец метода run() отладочную печать:
    override def run() {
      try {
        while(colour != FADED) {
          mp.meet(this)
          if(other == FADED) {
            colour = FADED
          } else {
            met = met + 1
            colour = complement(other)
          }
        }
      } catch {
        case e:InterruptedException => () // Let the thread exit
      }

      Console.println("I meet: " + met + " creatures" );
    }

При запуске сразу можно увидеть, что первая печать появляется мгновенно и сообщает о нуле встреченных хамелеонов. Т.е. правильный результат могут успешно сделать и трое оставшихся, зачем еще четвертый? Тем более, что по условию нужно создавать четырех хамелеонов, но не обязательно, чтобы все четверо потом работали К тому же, трое с работой справляются несколько быстрее, чем четверо (у меня исходный вариант работает 9сек, против 12сек в случае четырех хамелеонов).

В итоге

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

Ну или в нескольких словах: длинный (по сравнению с Haskell) вариант на D, два дня программирования в свое удовольствие (с очередной напряженностью в семье). Подорванная вера в корректность The Great Language Shootout. Ну и этот текст


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re: Простые и неправильные хамелеоны
От: FDSC Россия consp11.github.io блог
Дата: 01.05.07 13:34
Оценка: +2
Здравствуйте, eao197, Вы писали:

E>В итоге


E>Очередное повторение на собственной шкуре банальных истин:

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

Первый вывод, который нужно было сделать: писать нормальное ТЗ и представлять алгоритм без потери существенной информации из условия. Сразу бросилось в глаза, как ты описываешь логику работы хамелеонов

Первый хамелеон приходит на место встречи, видит, что swappedColor_ равен null, понимает, что он первый. В swappedColor_ помещается указатель на локальную переменную с собственным цветом. И засыпает.

Приходит второй хамелеон, видит, что swappedColor_ не равен null, считывает из нее цвет первого, записывает свой цвет, пинает первого и уходит.

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


Задание было изначально неточно переведено в формальное ТЗ, а затем и в алгоритм, естественно, после этого хоть ты десять раз правильно спроектируй систему, всё равно ошибка может спокойно возникнуть.
Re[2]: Простые и неправильные хамелеоны
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 01.05.07 15:56
Оценка:
Здравствуйте, FDSC, Вы писали:

FDS>Первый вывод, который нужно было сделать: писать нормальное ТЗ и представлять алгоритм без потери существенной информации из условия.


Правильно это.
Наверное.
Писать ТЗ для олимпиадной задачи, которая делается для собственного удовольствия в свободное время... Куда, однако, катится мир?

FDS> Сразу бросилось в глаза, как ты описываешь логику работы хамелеонов


FDS>

FDS>Первый хамелеон приходит на место встречи, видит, что swappedColor_ равен null, понимает, что он первый. В swappedColor_ помещается указатель на локальную переменную с собственным цветом. И засыпает.

FDS>Приходит второй хамелеон, видит, что swappedColor_ не равен null, считывает из нее цвет первого, записывает свой цвет, пинает первого и уходит.

FDS>Первый просыпается, обнуляет swappedColor_, берет из своей локальной переменной цвет второго и уходит, освобождая площадку.


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


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

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


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re: Простые и неправильные хамелеоны
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 01.05.07 16:00
Оценка:
E>Пути исправления

E>Можно использовать семафор с ограничением на вход на место встречи только двух хамелеонов. Но тогда нужно чтобы освобождал семафор только первый хамелеон, причем инкрементируя счетчик семафора сразу на два (освобождая тем самым вход на место встречи). Второй хамелеон не может изменять значение семафора, т.к. это приведет к той же самой проблеме. Вот вариант, использующий семафор (у меня на WinXP он в два раза медлее второго варианта).


E>Либо можно использовать счетчик количества хамелеонов на месте встречи и еще одну условную переменную, которая будет разрешать вход на место встречи новым хамелеонам. Вот этот вариант. (С++ный близнец.)


Вот еще один, более компактный вариант. Использует возможность D автоматически сворачивать блоки кода в анонимные делегаты. Для большей компактности чуть переформатирован и используется семафор для ограничения количества хамелеонов на площадке.


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: Простые и неправильные хамелеоны
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.05.07 17:48
Оценка: +1 :))) :))
Здравствуйте, eao197, Вы писали:

E>Правильно это.

E>Наверное.
E>Писать ТЗ для олимпиадной задачи, которая делается для собственного удовольствия в свободное время... Куда, однако, катится мир?

Согласен. Безграмотно. Давайте лучше подумаем как бы из кого-нить финансирование на это дело выбить.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Простые и неправильные хамелеоны
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.05.07 17:48
Оценка:
Здравствуйте, eao197, Вы писали:

E>Вот еще один, более компактный вариант. Использует возможность D автоматически сворачивать блоки кода в анонимные делегаты. Для большей компактности чуть переформатирован и используется семафор для ограничения количества хамелеонов на площадке.


Лучше на Скале и Эрланге забацайте .
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Простые и неправильные хамелеоны
От: FDSC Россия consp11.github.io блог
Дата: 01.05.07 18:29
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, eao197, Вы писали:


E>>Правильно это.

E>>Наверное.
E>>Писать ТЗ для олимпиадной задачи, которая делается для собственного удовольствия в свободное время... Куда, однако, катится мир?

VD>Согласен. Безграмотно. Давайте лучше подумаем как бы из кого-нить финансирование на это дело выбить.


Да. Тогда ТЗ точно писать придётся, и не набросок на клочке бумажки, а отпечатанное на лазерном принтере на глянцевой бумаге с красивыми рисунками, страниц 15, не меньше...
Зато лазерный принтер купим
Re: Простые и неправильные хамелеоны
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 19.05.07 11:05
Оценка: 2 (1) +1
Здравствуйте, eao197, Вы писали:

E>На мой взгляд это как раз тот самый случай. У данной задачи есть только один стабильный показатель, который легко контролировать -- итоговое количество встреч. Все остальные вещи выполняются в случайном порядке. Например, при одном запуске могут вначале встретиться красный и синий хамелеон. А при втором -- желтый и красный. И невозможно составить какой-то фиксированный сценарий, который бы всегда выполнялся при определенном N. Поэтому и невозможно прогнать программу на каком-то N и сравнить ее след работы с фиксированным сценарием.


имхо, это скорее случай — когда необходимо делать правильное тестирование.
соответственно для сложных программ (в том числе и многопоточных) используются такие методы, как анализ трассы на корректность + статистический анализ трассы.

ты ошибаешься, когда говоришь, что есть только одна "точка" для тестирования — итоговое кол-во встреч.

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

автоматически, в данном случае, по трассе стоило проверять
инварианты:
1. что хамелеон между встречами сам по себе не перекрасился
2. что обмен цветов после встречи был проведен корректно
статистику:
1. что хамелеоны участвовали в встречах — равномерно
2. что цвета по встречам тоже распределены равномерно
5. что номера хамелеонов, участвующих в встречах, распределено равномерно по времени


трасса должна была представлять собой примерно следующее:
<номер встречи> <номер первого хамелеона> <номер второго хамелеона> <цвет первого хамелеона до встречи> <цвет второго хамелеона до встречи> <цвет первого хамелеона после встречи> <цвет второго хамелеона после встречи>

E>Очередное повторение на собственной шкуре банальных истин:

E>* программировать нужно сначала на бумаге, а не лихим кавалерийским наскоком;

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

ps
> Поэтому и невозможно прогнать программу на каком-то N и сравнить ее след работы с фиксированным сценарием.

в запущенных случаях, даже делается возможность прогона программы по уже готовой трассе. в данном случае, из трассы берется кто должен придти на n-ую встречу, соответственно те хамелеоны, что не участвуют в n-ой встрече искусственно усыпляются.
Re[2]: Простые и неправильные хамелеоны
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 19.05.07 17:57
Оценка: +2
Здравствуйте, DarkGray, Вы писали:

E>>На мой взгляд это как раз тот самый случай. У данной задачи есть только один стабильный показатель, который легко контролировать -- итоговое количество встреч. Все остальные вещи выполняются в случайном порядке. Например, при одном запуске могут вначале встретиться красный и синий хамелеон. А при втором -- желтый и красный. И невозможно составить какой-то фиксированный сценарий, который бы всегда выполнялся при определенном N. Поэтому и невозможно прогнать программу на каком-то N и сравнить ее след работы с фиксированным сценарием.


DG>имхо, это скорее случай — когда необходимо делать правильное тестирование.


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

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

DG>соответственно для сложных программ (в том числе и многопоточных) используются такие методы, как анализ трассы на корректность + статистический анализ трассы.


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

DG>ты ошибаешься, когда говоришь, что есть только одна "точка" для тестирования — итоговое кол-во встреч.


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

DG>есть намного более важная информация — это сами встречи, т.е. кто с кем встретился, какой цвет был до встречи, какой цвет был получен в итоге и т.д.

DG>т.е. если бы ты вывел на печать трассу встреч, то ты бы сразу увидел все свои проблемы, как глазами, так и автоматически.

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

Теперь можно пройтись по рекомендациям:

DG>автоматически, в данном случае, по трассе стоило проверять

DG>инварианты:
DG>1. что хамелеон между встречами сам по себе не перекрасился

А смысл? Какой смысл проверять действия, которые в программе не выполняются. Ну не меняют хамелеоны свой цвет между встречами.

DG>2. что обмен цветов после встречи был проведен корректно


Да, это имело бы смысл.
Но в данном случае я использовал уже готовые алгоритмы обмена цветов, которые были практически идентичными в реализациях на трех разных языках (D, Scala и Java).

DG>статистику:

DG>1. что хамелеоны участвовали в встречах — равномерно
DG>2. что цвета по встречам тоже распределены равномерно
DG>5. что номера хамелеонов, участвующих в встречах, распределено равномерно по времени

А вот здесь, если бы вы сами сделали реализацию этого теста, вы бы могли увидеть интересные вещи. При небольших N нити первых двух хамелеонов успевают выполнить все встречи еще до того, как стартуют нити двух последних хамелеонов. При увеличении N успевает отхватить свой кусок третья нить, а четвертой остаются только остатки. И только при N => 1M распределение более-менее выравниваются.

При этом такое поведение вполне корректно, т.к. по условиям задачи вовсе не требуется, чтобы все хамелеоны стартовали одновременно. И даже если бы они одновременно стартовали на маленьких N такая ситуация (когда все встречи исчерпываются всего двумя хамелеонами) вполе могла бы повториться.

DG>трасса должна была представлять собой примерно следующее:

DG><номер встречи> <номер первого хамелеона> <номер второго хамелеона> <цвет первого хамелеона до встречи> <цвет второго хамелеона до встречи> <цвет первого хамелеона после встречи> <цвет второго хамелеона после встречи>

А вот здесь вы бы не увидели ошибки, которую я сам совершил -- в таком трейсе нет печати о входе и выходе хамелеонов на площадку для встречи. Без этой информации вполне может оказаться, что один хамелеон не покидает площадку для встречи и обменивается цветами с другими посетителями. Например, взгляните на Scala-реализацию, там MeetingPlace сама назначает цвета хамелеонам. Т.е. уснувшему на площадке хамелеону даже не нужно просыпаться, чтобы получить правильный цвет -- MeetingPlace сам ему этот цвет назначит.

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

При всем при этом в ваших рекомендациях нет проверки на то, что на месте встречи присутствует не более двух хамелеонов одновременно.

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


Хотел бы я увидеть решение данной задачи, которое использует трассы для верификации, сами верификаторы трассы, а так же возможность прогона программы по заранее определенной трассе. Вы сами как оцениваете объем всего необходимого для подобной проверки кода?


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: Простые и неправильные хамелеоны
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 21.05.07 17:28
Оценка:
DG>>1. что хамелеон между встречами сам по себе не перекрасился

E>А смысл? Какой смысл проверять действия, которые в программе не выполняются. Ну не меняют хамелеоны свой цвет между встречами.


для того, чтобы убедиться, что хамелеон меняет цвет только во время встречи

DG>>2. что обмен цветов после встречи был проведен корректно


E>Да, это имело бы смысл.

E>Но в данном случае я использовал уже готовые алгоритмы обмена цветов, которые были практически идентичными в реализациях на трех разных языках (D, Scala и Java).

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

E>При этом такое поведение вполне корректно, т.к. по условиям задачи вовсе не требуется, чтобы все хамелеоны стартовали одновременно. И даже если бы они одновременно стартовали на маленьких N такая ситуация (когда все встречи исчерпываются всего двумя хамелеонами) вполе могла бы повториться.


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

DG>>трасса должна была представлять собой примерно следующее:

DG>><номер встречи> <номер первого хамелеона> <номер второго хамелеона> <цвет первого хамелеона до встречи> <цвет второго хамелеона до встречи> <цвет первого хамелеона после встречи> <цвет второго хамелеона после встречи>

E>А вот здесь вы бы не увидели ошибки, которую я сам совершил -- в таком трейсе нет печати о входе и выходе хамелеонов на площадку для встречи. Без этой информации вполне может оказаться, что один хамелеон не покидает площадку для встречи и обменивается цветами с другими посетителями. Например, взгляните на Scala-реализацию, там MeetingPlace сама назначает цвета хамелеонам. Т.е. уснувшему на площадке хамелеону даже не нужно просыпаться, чтобы получить правильный цвет -- MeetingPlace сам ему этот цвет назначит.


так мы по статистике как раз увидем, что у нас один хамелеон участвует во всех 100% встреч, что не должно быть.

E>При всем при этом в ваших рекомендациях нет проверки на то, что на месте встречи присутствует не более двух хамелеонов одновременно.


если на площадке три хамелеона, это как раз и приведет к изменению цвета хамелеона без реальной зафиксированной встречи.
Re[4]: Простые и неправильные хамелеоны
От: FDSC Россия consp11.github.io блог
Дата: 21.05.07 19:07
Оценка:
Здравствуйте, DarkGray, Вы много писали

Всё здорово. Но, думаю, на написание тестов он потратил бы больше времени, чем на написание и отладку так, как он это сделал в реальности
Всё-таки, согласитесь, тесты не очень. Да и аргумент по поводу того, что тесты в многопоточности вносят сильные искажения во временные диаграммы потоков тоже вы не опровергли
Re: Простые и неправильные хамелеоны
От: Flamage Россия  
Дата: 21.05.07 22:30
Оценка: 23 (1)
Собственно вариант на Эрланге:

-module(cham).
-export([start/1, creature/2, meeting_place/1, meeting_place/2]).

creature(Colour, MPPid) ->
    MPPid ! {self(), Colour},
    creature(Colour, MPPid, 0).
creature(Colour, MPPid, Met) ->
    receive
        faded ->
            MPPid ! Met;
        OColour when is_atom(OColour) ->
            NColour = complement({Colour, OColour}),
            MPPid ! {self(), NColour},
            creature(NColour, MPPid, Met+1)
    end.

meeting_place(N) ->
    meeting_place(N, 0).
meeting_place(0, _) ->
    end_meeting(0, 4);
meeting_place(N, Cr) ->
    receive
        {CrPid, Colour} when is_tuple(Cr) ->
            {CrPid1, Colour1} = Cr,
            CrPid ! Colour1,
            CrPid1 ! Colour,
            meeting_place(N-1, 0);
        {CrPid, Colour} ->
            meeting_place(N, {CrPid, Colour})
    end.

end_meeting(TMet, 0) ->
    io:format("Total meetings: ~p~n", [TMet]);
end_meeting(TMet, Crs) ->
    receive
        {CrPid, _} ->
            CrPid ! faded,
            end_meeting(TMet, Crs);
        Met  when is_number(Met) ->
            end_meeting(TMet + Met, Crs-1)
    end.


start(N) ->
    MPPid = spawn(?MODULE, meeting_place, [N]),
    spawn(?MODULE, creature, [blue, MPPid]),
    spawn(?MODULE, creature, [red, MPPid]),
    spawn(?MODULE, creature, [yellow, MPPid]),
    spawn(?MODULE, creature, [blue, MPPid]).

complement(Pair) ->
    case Pair of
        {blue, red} -> yellow;
        {blue, yellow} -> red;
        {blue, blue} -> blue;
        {red, yellow} -> blue;
        {red, blue} -> yellow;
        {red, red} -> red;
        {yellow, yellow} -> yellow;
        {yellow, red} -> blue;
        {yellow, blue} -> red;
        {faded, _} -> faded;
    _Else -> erlang:error(badarg)
end.


Производительность еще не успел замерить до конца, хочу еще в виде кластера creature'ов попробовать запустить по сетке.
Re[4]: Простые и неправильные хамелеоны
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 22.05.07 05:51
Оценка:
Здравствуйте, DarkGray, Вы писали:

DG>>>1. что хамелеон между встречами сам по себе не перекрасился


E>>А смысл? Какой смысл проверять действия, которые в программе не выполняются. Ну не меняют хамелеоны свой цвет между встречами.


DG>для того, чтобы убедиться, что хамелеон меняет цвет только во время встречи



Забавно получается. Хамелеоны в программе меняют цвет только во время встречи. Более точно это происходит так: хамелеон ожидает встречи, встреча происходит (именно здесь вся блокировка) и результатом встречи оказывается цвет второго хамелеона. Только после этого хамелеон вычисляет свой новый цвет. Т.е. обращение к функции complement производится только один раз.

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

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

DG>>>2. что обмен цветов после встречи был проведен корректно


E>>Да, это имело бы смысл.

E>>Но в данном случае я использовал уже готовые алгоритмы обмена цветов, которые были практически идентичными в реализациях на трех разных языках (D, Scala и Java).

DG>я верю, что сам код обмена работает правильно, но есть сомнение, что обмен цветами происходит правильно в реальной многопоточной программе.

DG>простейший пример, если забыть лочить хамелеона на время обмена цветами, то как раз и вылезет, что у нас цвет некорректно меняется после обменов.

Если говорить о конкретно моей реализации, то таких сомнений нет, поскольку вся синхронизация выполняется внутри функции processMeeting. А снаружи никакой синхронизации нет. Нет так же и доступа к разделяемым между несколькими потоками данным, результаты processMeeting возвращаются по значению.

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

E>>При этом такое поведение вполне корректно, т.к. по условиям задачи вовсе не требуется, чтобы все хамелеоны стартовали одновременно. И даже если бы они одновременно стартовали на маленьких N такая ситуация (когда все встречи исчерпываются всего двумя хамелеонами) вполе могла бы повториться.


DG>если бы это была реальная задача, то это решение сложно считать корректным, когда по ТЗ должно было участвовать 4 хамелеона, а в реальности мы видем только два.

DG>то что данная реализация приводит к тому, что успевают запуститься только два хамелеона — это проблема именно реализации, а не ТЗ.

По ТЗ должно быть создано четыре конкурентных хамелеона. Они созданы. Но по ТЗ не было ограничений на то, что хамелеон должен поучавствовать хотя бы в одной встрече. Или, что хамелеон может поучавствовать не более чем в N/2 встречах.

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

DG>>>трасса должна была представлять собой примерно следующее:

DG>>><номер встречи> <номер первого хамелеона> <номер второго хамелеона> <цвет первого хамелеона до встречи> <цвет второго хамелеона до встречи> <цвет первого хамелеона после встречи> <цвет второго хамелеона после встречи>

E>>А вот здесь вы бы не увидели ошибки, которую я сам совершил -- в таком трейсе нет печати о входе и выходе хамелеонов на площадку для встречи. Без этой информации вполне может оказаться, что один хамелеон не покидает площадку для встречи и обменивается цветами с другими посетителями. Например, взгляните на Scala-реализацию, там MeetingPlace сама назначает цвета хамелеонам. Т.е. уснувшему на площадке хамелеону даже не нужно просыпаться, чтобы получить правильный цвет -- MeetingPlace сам ему этот цвет назначит.


DG>так мы по статистике как раз увидем, что у нас один хамелеон участвует во всех 100% встреч, что не должно быть.


Как раз не будет одного в 100% встреч. Ведь рано или позно он просыпается.

E>>При всем при этом в ваших рекомендациях нет проверки на то, что на месте встречи присутствует не более двух хамелеонов одновременно.


DG>если на площадке три хамелеона, это как раз и приведет к изменению цвета хамелеона без реальной зафиксированной встречи.


Это зависит от того, кто фиксирует встречу -- первый хамелеон или второй. Если первый, тогда да, цвет меняется несколько раз. А вот если встречу фиксирует второй хамелеон, тогда наличие трех хамелеонов на площадке не будет заметно в трассе.
Под фиксацией встречи понимается декрементирование счетчика оставшихся встреч.


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[2]: Простые и неправильные хамелеоны
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 22.05.07 05:55
Оценка:
Здравствуйте, Flamage, Вы писали:

F>Собственно вариант на Эрланге:


<...skipped...>

А вы не сравнивали свой вариант с вариантом из language shootout?
Чем ваш вариант лучше/хуже?

F>Производительность еще не успел замерить до конца, хочу еще в виде кластера creature'ов попробовать запустить по сетке.


А вот в духе нашего спора с DarkGray
Автор: DarkGray
Дата: 19.05.07
: как вы верифицировали вашу реализацию?


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: Простые и неправильные хамелеоны
От: Flamage Россия  
Дата: 22.05.07 09:51
Оценка:
F>>Собственно вариант на Эрланге:

E><...skipped...>


E>А вы не сравнивали свой вариант с вариантом из language shootout?

E>Чем ваш вариант лучше/хуже?

Вариант с shootout не видел, когда писал свою реализацию. В целом она похожа, конечно, на мою, но это не стиль Эрланга


F>>Производительность еще не успел замерить до конца, хочу еще в виде кластера creature'ов попробовать запустить по сетке.


E>А вот в духе нашего спора с DarkGray
Автор: DarkGray
Дата: 19.05.07
: как вы верифицировали вашу реализацию?


Тестировал с помощью "юнит-тестов", их реализацию вместе с тестами производительсности выложу чуть позже.

Да, и к вопросу сравнения ИП и ФП, с чего тема появилась... Я потратил на проектирование, написание кода и общее тестирование всего 2 часа
Все-таки обмен сообщениями гораздо более нагляден в таких задачах.
Re[4]: Простые и неправильные хамелеоны
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 22.05.07 10:17
Оценка:
Здравствуйте, Flamage, Вы писали:

E>>А вот в духе нашего спора с DarkGray
Автор: DarkGray
Дата: 19.05.07
: как вы верифицировали вашу реализацию?


F>Тестировал с помощью "юнит-тестов", их реализацию вместе с тестами производительсности выложу чуть позже.


F>Да, и к вопросу сравнения ИП и ФП, с чего тема появилась... Я потратил на проектирование, написание кода и общее тестирование всего 2 часа


Рад за вас
К сожалению, это не показатель сравнения ИП и ФП. Поскольку на нитях, тем более в D, я вообще очень мало программировал. А реализация этого же теста на привычном мне SObjectizer-е у меня заняла бы те же самые 2 часа , причем значительную часть времени занимала бы компиляция C++ кода

F>Все-таки обмен сообщениями гораздо более нагляден в таких задачах.


Конкретно в этой задаче -- не факт, имхо. Хотя утвержать не буду

Тем более, что меня больше интересовал объем результирующего кода. Кстати, если вот из этого варианта удалить все пустые строки и строки, содержащие только фигурные скобки, то получается 65 строк. Если же из вашего решения удалить все пустые строки, то получится 58 строк. Разрыв не так уж велик. Тем более, что вариант на D не требует перестройки мозгов с ИП на ФП.


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[4]: Простые и неправильные хамелеоны
От: Flamage Россия  
Дата: 24.05.07 21:56
Оценка: 4 (1)
Как и обещал — резултаты тестов.

Сначала о производительности, тестировал на Athlon X2 64 3600.
Исходниками с тестами здесь, код грязноват, но кто хочет может тоже поэксперементировать.

К сожалению пока нет версии Эрланга с поддержкой SMP для винды из-за чего производительность на одной ноде на двух ядрах замерить не удалось.
1. Одна нода, одно ядро — 1'000'000 встречь — примерно 1.25 сек.
2. Две ноды — 75 сек., как и предполагалось, разрыв внушительный, пересылка сообщений посредством TCP/IP сокетов отбирает большую часть времени.
3. Две ноды, но с выставлением в пользование каждой первого ядра, т.е. эмуляция одноядерного процессора — 138 сек. Надо отметить, что если задачи достаточно продолжительны, то ноды позволяют задействовать всю мошь многоядерных процессоров и достичь почти линейной масштабируемости.
4. Две ноды, но каждой выставленно отдельное ядро — 71 сек., с учетом того, что тесты проводились сериями и затем считалось среднее значение, результат получился очень интересным. Получается, что Эрланг более эффективен при распределении производительности многоядерных/многопроцессорных систем, чем встроенные механизмы ОС!

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

Теперь о тестах верификации.
Обработчик очереди сообщений Эрланга очень эффективен и главное предсказуем — после запуска на "месте встречи" всегда(!, за серию из 100 тестов по 1'000'000 встречь тесты не выявили ни одной другой пары) получаются пары a-b и c-d, причем когда выносишь один из процессов на отдельную ноду все равно получается очевидный результат — a-b, потом b-c, далее c-a и т.д., появление сообщения от процесса d только сдвигает варианты пар на шаг.
Впрочем это не противоречит условию задачи и даже использование 3-х процессов (4-й сразу уходит в статус faded) никак не влияет на результат.
Re: Простые и неправильные хамелеоны
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.11.07 11:12
Оценка:
Кстати, о Хамелионах...

Сделал тут поиск по Немерловым снипетам и нашел (нечаяно) там хамелиона на нем:
http://nemerle.org/svn/nemerle/trunk/snippets/shootout/chameneos.n
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Простые и неправильные хамелеоны
От: remark Россия http://www.1024cores.net/
Дата: 26.03.08 09:37
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Кстати, о Хамелионах...


VD>Сделал тут поиск по Немерловым снипетам и нашел (нечаяно) там хамелиона на нем:

VD>http://nemerle.org/svn/nemerle/trunk/snippets/shootout/chameneos.n


По условию задачи реализация должна использовать kernel threads.

lightweight threads… cooperative threads… and other programs with custom schedulers will be listed as interesting alternative implementations




1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: Простые и неправильные хамелеоны
От: remark Россия http://www.1024cores.net/
Дата: 26.03.08 16:12
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, VladD2, Вы писали:


VD>>Кстати, о Хамелионах...


VD>>Сделал тут поиск по Немерловым снипетам и нашел (нечаяно) там хамелиона на нем:

VD>>http://nemerle.org/svn/nemerle/trunk/snippets/shootout/chameneos.n


R>По условию задачи реализация должна использовать kernel threads.

R>

R>lightweight threads… cooperative threads… and other programs with custom schedulers will be listed as interesting alternative implementations



Хотя там написано в стиле "Казнить нельзя помиловать":

Programs may use kernel threads, lightweight threads… cooperative threads… and other programs with custom schedulers will be listed as interesting alternative implementations. Briefly say what concurrency technique is used in the program header comment.



R>


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.