Событийный симуляционный класс

Я работаю над некоторыми упражнениями на языке программирования C ++ Бьярна Страуструпа. Меня смущает проблема 11 в конце главы 12:

(* 5) Разработайте и внедрите библиотеку для написания событийно-ориентированных симуляций. Подсказка: <task.h>. ... Объект задачи класса должен быть в состоянии сохранить свое состояние и восстановить это состояние, чтобы он мог работать как сопрограмма. Конкретные задачи могут быть определены как объекты классов, полученных из задачи. Программа, выполняемая задачей, может быть определена как виртуальная функция. ... Должен быть планировщик, реализующий концепцию виртуального времени. ... Задачам нужно будет общаться. Разработайте очередь классов для этого. ...

Я не уверен точно, что это просит. Является ли задача отдельным потоком? (Насколько я знаю, невозможно создать новый поток без системных вызовов, и, поскольку это книга о C ++, я не верю, что это так.) Без прерываний, как можно запустить и остановить запуск? функция? Я предполагаю, что это будет связано с занятым ожиданием (то есть непрерывным циклом и проверкой условия), хотя я не могу понять, как это можно применить к функции, которая может не завершиться в течение некоторого времени (например, если она содержит бесконечный цикл) ,

РЕДАКТИРОВАТЬ: Пожалуйста, смотрите мой пост ниже с дополнительной информацией.

15.12.2008 22:42:25
8 ОТВЕТОВ
РЕШЕНИЕ

Подсказка: <task.h>.

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

Если вы прочитаете статью « Набор классов C ++ для совместного программирования стилей », все станет намного понятнее.


Добавляем немного:

Я не достаточно старый программист, чтобы использовать библиотеку задач. Однако я знаю, что C ++ был разработан после того, как Страуструп написал симуляцию в Simula, у которой было много свойств, аналогичных библиотеке задач, поэтому мне всегда было интересно.

Если бы я реализовал упражнение из книги, я бы, вероятно, сделал это следующим образом (обратите внимание, я не тестировал этот код и даже не пытался его скомпилировать):

class Scheduler {
    std::list<*ITask> tasks;
  public:
    void run()
    {
        while (1) // or at least until some message is sent to stop running
            for (std::list<*ITask>::iterator itor = tasks.begin()
                      , std::list<*ITask>::iterator end = tasks.end()
                    ; itor != end
                    ; ++itor)
                (*itor)->run(); // yes, two dereferences
    }

    void add_task(ITask* task)
    {
        tasks.push_back(task);
    }
};

struct ITask {
    virtual ~ITask() { }
    virtual void run() = 0;
};

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

Идея состоит в том, что вызовы ITask :: run () будут блокировать планировщик до тех пор, пока задача не достигнет точки, в которой она может быть прервана, и в этот момент задача вернется из метода run, и подождать, пока планировщик снова вызовет run для Продолжить. «Кооператив» в «кооперативной многозадачности» означает «задачи говорят, когда их можно прервать» («сопрограмма» обычно означает «кооперативная многозадачность»). Простая задача может делать только одну вещь в своем методе run (), более сложная задача может реализовывать конечный автомат и может использовать свой метод run (), чтобы выяснить, в каком состоянии находится объект в настоящее время, и выполнить вызовы других методов на основе в этом состоянии. Задачи должнывремя от времени оставляйте контроль, чтобы это работало, потому что это определение «совместной многозадачности». Это также причина, по которой все современные операционные системы не используют совместную многозадачность.

Эта реализация не (1) не следует честному планированию (возможно, сохраняя промежуточное количество тактов, потраченных в методе run () задачи, и пропуская задачи, которые использовали слишком много времени относительно других, пока другие задачи не «догонят») , (2) разрешить удаление задач или даже (3) разрешить остановку планировщика.

Что касается связи между задачами, вы можете рассмотреть возможность поиска вдохновения в libtask в Plan 9 или в новостном письме Роба Пайка (загрузка «Реализация Newsqueak в UNIX» включает документ «Реализация новостного скрипта», в котором обсуждается передача сообщений в интересной виртуальной машине).

Но я считаю, что это основной скелет, который имел в виду Страуструп.

3
18.12.2008 00:15:29

(Я не разработчик C ++)

Вероятно, это означает, что вам нужно создать класс Task (как в Event), который будет состоять в основном из указателя функции обратного вызова и запланированного времени и может быть сохранен в списке в классе Scheduler, который, в свою очередь, должен сохранять отслеживать счетчик времени и вызывать функцию каждой задачи, когда наступит время. Эти задачи должны быть созданы Объектами симуляции.

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

1
15.12.2008 22:47:31
Как это будет работать с сохранением и восстановлением состояния задачи?
titaniumdecoy 15.12.2008 22:53:23
Хорошо прочитав ответ Харпера, это, вероятно, означает, что каждая задача может выполняться в течение определенного периода времени, но вам нужно распределить виртуальное время между всеми активными задачами на данном «тике».
krusty.ar 16.12.2008 00:08:22
Как бы вы сделали это без использования потоков или отдельных процессов?
titaniumdecoy 16.12.2008 01:53:19
@ krusty.ar, то, что описывает ваш комментарий, является симуляцией, управляемой временем.
Scottie T 17.12.2008 13:41:43

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

2
15.12.2008 23:14:27
В значительной степени - на самом деле, это напоминает мне домашнее задание в моем классе операционных систем.
Harper Shelby 16.12.2008 16:39:17

Вот мое понимание «симуляции на основе событий»:

  • Контроллер обрабатывает очередь событий, планируя события, происходящие в определенное время, затем выполняя верхнее событие в очереди.
  • События происходят мгновенно в назначенное время. Например, событие «перемещение» будет обновлять положение и состояние объекта в моделировании, так что вектор состояния будет действительным в текущее время моделирования. «Смысловое» событие должно было бы убедиться, что все состояния сущностей находятся в текущем времени, а затем использовать некоторую математическую модель, чтобы оценить, насколько хорошо текущая сущность может воспринимать другие сущности. (Подумайте, роботы движутся по доске.)
  • Таким образом, время прогрессирует с перерывами, прыгая от события к событию. Сравните это с управляемой временем симуляцией, когда время движется дискретными шагами, а состояния всех сущностей обновляются каждый временной шаг (в большинстве моделей Simulink).
  • Затем события могут происходить с естественной скоростью. Обычно не имеет смысла пересчитывать все данные с максимальной скоростью в симуляции.

Большинство производственных событий, управляемых событиями, выполняются в одном потоке. Они могут быть сложными по своей природе, поэтому попытка синхронизировать многопоточное моделирование имеет тенденцию добавлять экспоненциальные уровни сложности. С учетом вышесказанного, существует стандарт для многопроцессного военного моделирования, называемый Distributive Interactive Simulation (DIS), который использует предопределенные сообщения TCP для передачи данных между процессами.

РЕДАКТИРОВАТЬ: важно определить разницу между моделированием и симуляцией. Модель - это математическое представление системы или процесса. Симуляция строится из одной или нескольких моделей, которые выполняются в течение определенного периода времени. Опять же, управляемое событиями моделирование переходит от события к событию, в то время как управляемое временем моделирование выполняется с постоянным временным шагом.

5
16.12.2008 04:14:40
Этот ответ имеет наибольшее значение для меня до сих пор. Однако, как описано, это не похоже на симуляцию, управляемую «событием», поскольку каждое событие запланировано на определенное время.
titaniumdecoy 16.12.2008 01:52:46
Время - это «виртуальное время» в симуляции, вытесненное из очереди приоритетов. Симуляция не регулируется, чтобы быть синхронизированной со временем настенных часов.
ConcernedOfTunbridgeWells 17.12.2008 14:02:29
@NXC, точно. Симуляции обычно работают намного быстрее, чем в реальном времени. Вот почему они полезны. Вы можете проводить эксперименты, изменяя параметры, и генерировать тысячи (миллионы?) Точек данных за то же время, которое может потребоваться для процесса «реального мира».
Scottie T 17.12.2008 18:04:28
Конечно, некоторые симуляции намного медленнее, чем в реальном времени. Это, как правило, научное моделирование потока жидкости или теплопередачи, и для моделирования 30 секунд «реального времени» может потребоваться несколько часов.
Scottie T 17.12.2008 18:05:54

В документе, связанном с "me.yahoo.com / ...", который описывает класс task.h:

  1. Задачи выполняются параллельно
  2. Задача может быть приостановлена ​​и возобновлена ​​позже

Библиотека описывается как метод мультипрограммирования.

Возможно ли это сделать без использования потоков или отдельных процессов?

0
16.12.2008 03:28:41
Это зависит от того, что вы подразумеваете под «параллелью». Для действительно параллельной работы вам понадобятся потоки / процессы. Но если вы реализуете планировщик (вам требуется, чтобы в каждой задаче были методы yield () и resume () для приостановки и возобновления обработки, а планировщик вызывает эти методы), вы можете приблизиться к параллельному режиму.
Max Lybbert 17.12.2008 01:49:23

Это в ответ на комментарий Titaniumdecoy к ответу SottieT812. Его слишком много для комментария, поэтому я решил сделать еще один ответ.

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

Это в отличие от симуляции, основанной на времени, где точное положение ракеты (и каждого другого объекта в симуляции) вычисляется после каждого временного шага, скажем, 1 секунды.

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

Изменить: Если кто-то заинтересован в получении дополнительной информации, ознакомьтесь с документами Зимней симуляционной конференции

1
17.12.2008 13:16:05
В качестве альтернативы, положение ракеты может быть явно рассчитано в случае «полета». Это пример события самоосадки, потому что обычно одно событие полета приводит к другому, пока ракета не выйдет из строя или не ударит что-то.
Scottie T 16.12.2008 20:02:50
Конечно. Есть куча разных способов делать вещи. Тысячи (10, 100?) Людей, работающих на оборонных подрядчиков, занимаются этим.
KeithB 17.12.2008 13:14:13

Существует книга и фреймворк под названием DEMOS (моделирование дискретных событий на Simula), в котором описывается фреймворк, основанный на сопрограмме (одноименный DEMOS). Несмотря на то, что ему или около 30 лет, DEMOS на самом деле довольно хорошая система, а Грэм Бёртвистл - действительно хороший парень.

Если вы реализуете сопрограммы на C ++ (например, setjump / longjump), вы должны взглянуть на эту книгу для описания действительно очень элегантной структуры моделирования дискретных событий. Хотя ему 30 лет, он немного вечная классика и до сих пор имеет фанатов.

1
17.12.2008 13:47:10

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

    Пока (не конечное условие):
        Получить следующее событие (с наименьшим временем) из очереди с приоритетами
        Обработать это событие, которое может генерировать больше событий
        Если новое событие генерируется:
            Поместите это в приоритетную очередь, ключ сгенерированный во время ее создания

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

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

2
18.12.2008 21:41:41