Ликбез по симуляции на Си++

[vak]

Давайте покажу вам в упрощённом варианте, чем я занимаюсь по работе последние полтора десятка лет. Симуляторы компьютерных архитектур, которые по сути сводятся к так называемому Discrete-event simulation.

Промоделируем на Си++ классическую задачку: пять обедающих философов.

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



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

Watch on YouTube

Смоделируем это дело на Си++. Представим каждого философа объектом класса Philosopher, каждую вилку объектом класса Fork. Объект Simulator будет разворачивать процесс во времени. Вот такая главная программа:

int main()
{
    Fork forks[5]{};
    Philosopher a(0, forks[0], forks[1]);
    Philosopher b(1, forks[1], forks[2]);
    Philosopher c(2, forks[2], forks[3]);
    Philosopher d(3, forks[3], forks[4]);
    Philosopher e(4, forks[4], forks[0]);
    Simulator sim;

    a.behave(sim);
    b.behave(sim);
    c.behave(sim);
    d.behave(sim);
    e.behave(sim);

    while (sim.is_active()) {
        sim.run();
    }
}

Вилка штука простая. Она находится в одном из двух состояний: свободна или занята.

enum class Fork {
    FREE,
    TAKEN,
};

Философ имеет уникальный идентификатор (index), ссылки на левую и правую вилки, а также состояние думаем/едим/ждём. Приватный метод random() генерит случайное число в указанном диапазоне - как долго философ будет "думать". Приватный метод display() отобразит состояние философа на экране.

class Philosopher : public Event {
private:
    const unsigned index;
    Fork &left_fork;
    Fork &right_fork;

    enum class State {
        THINKING,
        EATING,
        WAITING,
    };
    State state{};

    unsigned random(unsigned lo, unsigned hi);
    void display(uint64_t current_time) const;

public:
    Philosopher(unsigned i, Fork &l, Fork &r) : index(i), left_fork(l), right_fork(r) {}

    void behave(Simulator &sim) override;
}

Самое интересное происходит в методе behave().

    void behave(Simulator &sim) override
    {
        if (state != State::EATING) {
            // Хотим начать есть.
            if (left_fork == Fork::FREE && right_fork == Fork::FREE) {
                left_fork  = Fork::TAKEN;
                right_fork = Fork::TAKEN;
                state      = State::EATING;
                sim.wait(*this, 1000);
            } else {
                // Ждём, когда освободятся вилки.
                state = State::WAITING;
                sim.wait(*this, 10);
            }
        } else {
            // Прекращаем есть, начинаем думать.
            left_fork  = Fork::FREE;
            right_fork = Fork::FREE;
            state      = State::THINKING;
            sim.wait(*this, random(10, 2000));
        }
        display(sim.get_clock());
    }

Заметьте, что класс Philosopher унаследован от класса Event. Его я покажу позже, но суть в том, что симулятор будет ставить философов в очередь событий, и в нужное время вызывать для них метод behave(). При этом в качестве аргумента передаётся ссылка на сам симулятор. Чтобы продолжить ожидание на некоторый интервал времени (здесь в миллисекундах), философ вызывает метод sim.wait().

Собственно, это всё про устройство философов. Теперь заглянем в устройство симулятора. Что такое "событие"? Оно определяет виртуальный метод behave(), который должен быть реализован для всякого симулируемого объекта. Также событие имеет приватное поле start_time - момент времени, когда событие должно наступить. В этот момент будет вызван метод behave().

class Event {
public:
    virtual void behave(Simulator &sim) = 0;

private:
    uint64_t start_time{};

    // Сравниваем два события на больше-меньше, для упорядочивания по времени.
    struct Cmp {
        bool operator()(const Event *a, const Event *b) const
        {
            if (a->start_time < b->start_time)
                return true;
            if (a->start_time > b->start_time)
                return false;
            return (intptr_t)a < (intptr_t)b;
        }
    };

    friend class Simulator;
};

Также для событий задан способ упорядочивать их по времени - структура Cmp с оператором ().

Симулятор состоит из счётчика времени (поле master_clock) и очереди событий (поле queue). Метод wait() добавляет событие в очередь, откладывая его на указанный интервал времени относительно "сейчас". Метод run() активируем следующее событие из очереди.

class Simulator {
private:
    // Текущее время
    uint64_t master_clock{}; 

    // Очередь событий
    std::set<Event *, Event::Cmp> queue;

public:
    uint64_t get_clock() const { return master_clock; }

    // Есть ли чего в очереди?
    bool is_active() const { return !queue.empty(); }

    // Добавление события в очередь
    void wait(Event &event, unsigned num_cycles);

    // Выполнение следующего события из очереди
    void run();
};

Обратите внимание очередь queue реализована как std::set - множество указателей на объекты Event, упорядоченное по времени посредством метода Event::Cmp(). Дёшево и сердито.

Ожидание, то есть занесение объекта в очередь будущих событий, делается очень просто. Запоминаем нужное значение времени, затем вызываем метод insert() класса std::set.

    void wait(Event &event, unsigned num_cycles)
    {
        event.start_time = master_clock + num_cycles;
        queue.insert(&event);
    }

Напомню, что основной цикл симуляции в программе main() работает так:

    while (sim.is_active()) {
        sim.run();
    }

То есть пока есть события в очереди - продолжаем их обрабатывать. А вот как выглядит обработка одного события:

    void run()
    {
        // Извлекаем следующее (по времени) событие из очереди.
        Event *event = queue.extract(queue.begin()).value();

        // Если нужно - наращиваем счётчик времени.
        // Также подвешиваем программу на это время, для наглядности.
        if (event->start_time > master_clock) {
            unsigned msec = event->start_time - master_clock;
            usleep(msec * 1000);
        }
        master_clock = event->start_time;

        // Выполняем событие.
        event->behave(*this);
    }

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

Исходники здесь: github.com/sergev/vak-opensource/tree/master/languages/c++/philosophers

Comments

[kondybas]

Товарищ в конце 1990-х наваял полную либу компонентов для делфи для симуляций такого рода. А я на этой либе сварганил решение этой задачи Дейкстры (и еще нескольких других, более интересных). И мое решение даже тиснули в "Simulation News/Europe" за 1998-й, кажется. Самым бесценным было выражение лиц начальства в конторе, когда на мое имя пришел толстенный иностранный пакет DHL с авторскими экземплярами :)

[vak]

Ого, круто! Есть ссылочка глянуть на статью? Любопытно посмотреть.

[kondybas]

В личку отправил

[vak]

Классно, спасибо!

[kondybas]

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

[vak]

Сильно однако! Имеет ли какое отношение к OpenSimply?

Обычно паскальный софт не сильно востребован в индустрии.

[kondybas]

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

[vak]

Запощу картинки сюда для наглядности. Красиво же.

[kondybas]

Эх, детство босоногое! Слезы умиления наворачиваются :)

А можно тоже ссылочку на статью

[carrauntoohil]

Заранее большое спасибо )

[cali4nickation]

А есть не связанные с историей аргументы почему не использовать языки из этого века и может быть даже с GC (на работе но для этого домена)?

[vak]

Я очень даже за новые языки. Я бы на Rust с удовольствием переключился. Golang тоже неплох. Но где ж таких программистов в команду найти? Проблема.

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

[ircicq]

JIT сильно продвинулись по производительности за последние 10 лет

Сейчас на Си/Си++ писать производительнее чем C#, надо хорошо знать низкоуровневые функции, типа AVX.
Да и в них есть подвижки в .NET

[vak]

По моему опыту, всякий (успешный) симулятор, написанный на C#/Java/JS, придётся рано или поздно переписать на Си++. Жизнь заставит. 😀

[cali4nickation]

Плюсы моя первая любовь, так что я не критиковал а мне было интересно у кого за пределами embedded остались причины его использовать. Где под причинами кажется обычно понимают способность нанять молодежь.

Я не ожидал что вы поставите golang в тот же ряд как C++ и Rust. Он вроде даже по меркам Java убог неуклюж.

Fun fact: Мартин Одерски похожий пример выбрал в своей книге про Scala еще в 2009: "10.3 Extended Example: Discrete Event Simulation".

[vak]

Почему же, Golang вполне приятный язык на мой вкус. Я на нём сделал один небольшой компилятор. Удобно, что не надо тратить усилия на изучение каких-то жутких премудростей, как в Rust. Сразу берешь и пишешь.

[sobriquet9]

А где в приведённом примере поможет GC? Там же вроде нет никакого явного управления памятью, никаких malloc()/free()/new/delete. Какой мусор он будет собирать?

[vak]

GC вполне пригождается. Не часто, но бывает. Симулятор обычно обрастает массой родственного софта, и там находится место для сборки мусора.

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

[ircicq]

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

[vak]

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

[sobriquet9]

С циклическими ссылками и у сборщика мусора могут возникнуть проблемы. Особенно если система реального времени, которую нельзя остановить на произвольное время сборки мусора.

[ircicq]

Это решают найстройкой режимов.

Есть алгоритмы GC, требующие остановки только на короткие периоды.
Можно запрещать GC на критические периоды real-time, сделав достаточный резерв памяти.

Да и Си-шный malloc()/free() не гарантирует фиксировнного overhead
Приходится консолидировать списки блоков, занимать у других пулов, если собственнй пул треда исчерпался, и т.д.

Строгий Real-Time разве что на статических переменных можно писать.

[ircicq]

// Get next event from queue.
Event *event = *queue.begin();
queue.erase(event);


Эффективнее (без лишнего поиска по множеству) так:

auto it = queue.begin();
Event *event = *it;
queue.erase(it);

или даже

Event *event = queue.extract(queue.begin()).value();   // C++17

[vak]

О, это ценное замечание, спасибо!
Поправлю в тексте.
Век живи, век учись.

[juan_gandhi]

О как элегантно написано! Восхищен.

[vak]

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

[juan_gandhi]

Не в смысле книжку Хора, CSP?

[vak]

Вот эта, как я понимаю: http://www.usingcsp.com/cspbook.pdf

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

[juan_gandhi]

Да я бы не квалифицировал это как теорию; скорее как философию.

[vak]

Как философию-то я ценю. Нам такого типа вещи Курочкин преподавал на лекциях ТРЯП (теория и реализация языков программирования). Но лучше бы он про YACC и LEX рассказывал.

[ufm]

            if (left_fork == Fork::FREE && right_fork == Fork::FREE) {
                left_fork  = Fork::TAKEN;
                right_fork = Fork::TAKEN;
                state      = State::EATING;
                sim.wait(*this, 1000);
            }

Понимаю что в данном случае проблем не будет, но всё равно, когда вижу такие конструкции без локов - аж вздрагиваю. :)

[vak]

Здесь локи не к месту: все однопоточное.

[ufm]

Дык я и говорю - понятно, что оно тут не неужно, но... Разработчики питона тоже так говорили. :)

P.S. Не обращай внимания, у меня профдеформация на предмет того, что мир вокруг нас асинхронный и многопоточный.

[igaa]

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

Тут вы обошлись без семафоров (и потенциальных дедлоков) за счёт "телепатии" - замены индетерминированного wait на детерминированный wait с ordered queue.

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

[vak]

В этом и проблема: нынешние программисты слишком много знают про многопоточность, поэтому норовят применить её всюду, даже не к месту. 😀

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