Моделирование автозаправочной станции: как моделировать автомобили, прибывающие через случайные интервалы - PullRequest
2 голосов
/ 28 октября 2010

Назначение выглядит следующим образом:

АЗС состоит из 2 насосов. Каждый насос имеет определенное количество топлива, которое он может распределить. Автомобили прибывают через произвольные интервалы и пытаются использовать один из двух насосов:

- Если насос доступен и имеет топливо, автомобиль сразу же может его использовать. Каждому автомобилю требуется определенное количество топлива (случайное число), и он должен ждать времени, пропорционального этому количеству топлива. Например, машине может потребоваться 6 галлонов, и она будет использовать насос в течение 3 секунд, другой машине может потребоваться 10 галлонов, и она будет использовать насос 5 секунд и т. Д. Когда автомобиль заправляется, он уходит, а другая машина может использовать насос , После заправки автомобиля количество топлива в насосе регулируется соответствующим образом.
- Если в настоящее время используются оба насоса, то прибывающая машина ждет, пока один из двух насосов не станет доступным.
- Если в насосе заканчивается топливо, он должен подождать, пока танкер подаст больше топлива. Танкер прибывает периодически (но не слишком часто) и заполняет оба насоса до предела. Пока танкер обслуживает насосы, никакие машины не могут использовать насосы. забыл добавить это

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

Часть II: вы должны представить полную реализацию вашего проекта с использованием потоков Java и соответствующих методов синхронизации. Ваша реализация должна быть тщательно проверена на соответствие вышеуказанным спецификациям.


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

Ответы [ 7 ]

12 голосов
/ 28 октября 2010

Создайте заводской класс автомобилей, который выплевывает автомобиль для добавления в очередь и засыпает на произвольный период времени.

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

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

  1. У вас есть строка, которая добавляет новые записи на одном конце и удаляет их на другом. Это называется структурой данных очереди. Читайте об этом. Посмотрите, можете ли вы написать (или повторно использовать) класс Java Dequeue. Понять это полностью. Напишите небольшой драйвер для добавления на одном конце и удаления с другого.
  2. Как только вы это сделаете, вам нужно написать классы, которые создают новые записи для добавления в очередь и еще одну для их удаления. Начните просто с написания сумматоров / съемников, которые работают с фиксированным интервалом. Что вы должны увидеть, так это то, что, если сумматор и съемник имеют абсолютно одинаковый интерфейс, количество ожидающих записей в строке не изменится. Если сумматор работает быстрее, чем съемник, строка должна заполниться. Если съемник работает быстрее, чем сумматор, у вас никогда не будет резервной копии. Убедитесь, что ваши простые классы демонстрируют такое поведение.
  3. Добавьте случайные биты и начните симуляцию. Вы захотите увидеть, как количество записей в строке меняется со временем.
  4. Теперь добавьте более одной строки. Вы хотите увидеть, как добавление дополнительных строк меняет динамику.
3 голосов
/ 28 октября 2010

Если у вас есть фиксированные интервалы, количество автомобилей, прибывающих в этот интервал, составляет Пуассон распределено.

Время между двумя автомобилями имеет вероятность, пропорциональную exp (-t / tau)Тау описывает частоту прибытия автомобилей.Таким образом, вам нужно выяснить, как создавать экспоненциально распределенные случайные числа.

Из плотности вероятности p (t) = c * exp (-t / tau) мы интегрируем накопленное распределение вероятности P (t)= 1-ехр (-t / тау).Таким образом, инвертируя эту функцию, вы получаете t = -tau * ln (1-P (t)).Таким образом, если вы генерируете число u, равномерно распределенное между 0 и 1, вы можете получить правильно распределенное t как t = -tau * ln (1-u)

1 голос
/ 29 октября 2010

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

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

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

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

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

Итак, задачи выглядят примерно так:

  • поступающие автомобили

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

    • каждый (период прибытия танкера) после события прибытия танкера за насос
  • ожидающие машины

    • увеличить число машин, ожидающих при прибытии машины
  • Насосы

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

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

Если задачи находятся в разных потоках, вам нужно будет синхронизировать различные счетчики, либо «вручную», либо используя атомарные значения в java.util.concurrent.atomic.

1 голос
/ 28 октября 2010

Я могу видеть, куда вы идете с потоком, но он вам на самом деле не нужен, если только это не графическое моделирование, в котором вы хотите, чтобы люди видели, как он работает в реальном времени. В противном случае просто следите за временной шкалой. Знать в любой момент времени, какое событие произойдет в следующем периоде: А) Грузовик прибывает. Б) Автомобиль прибывает. C) Автомобиль уезжает.

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

Поверь мне, тебе будет намного проще просто делать вещи.

0 голосов
/ 28 октября 2010

Не используйте распределение Пуассона.Poission выдаст вам «номер прибытия в следующие X минут».Это не даст вам «Время до следующего приезда».

Создайте небольшой цикл, например, так: *

  public int getTimeTillNextCar() {
    PROBABILITY = .001;
    int timeTillNextCar = 0;
    while(rand.nextDouble() > PROBABILITY) {
      timeTillNextCar++;
    }
  }

Очевидно, я просто предположил, что вы используете незаметное время.Тем не менее, возможно (и некоторые могут поспорить лучше) использовать одну ничью из экспоненты.Это будет более эффективным.Однако использование этого подхода делает код «математическим», который некоторым людям может не понравиться / не понять.

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

Что касается остальной части дизайна ...

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

Thread_A должен это сделать:
добавить автомобиль,
сон (getTimeTillNextCar ()),
добавить автомобиль,
сон (getTimeTillNextCar ()),
добавить автомобиль,
добавить автомобиль (getTimeTillNextCar ()),
и т.д ....

Thread_B и Thread_C должны убирать автомобили из очереди:
Thread_B (и C) должны сделать следующее:
get_car_off_queue,
sleep (car.getFuelingTime (),
get_car_off_queue,
sleep (car.getFuelingTime () и т. Д. ...

0 голосов
/ 28 октября 2010

Вы можете использовать потокобезопасный PriorityBlockingQueue для создания очереди событий.

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

Изначально вы запускаете нить для ветки производителя прибытия автомобилей и нити производителя прибытия танкеров. Поток прибытия автомобиля будет put() CarArrivalEvent в очередь, а затем будет спать в течение случайного количества времени. Нить танкера также делает то же самое, но вместо этого put() TankerArrivalEvent.

АЗС имеет два насоса, каждый из которых представлен потребительской резьбой. Каждая нить насоса будет take() CarArrivalEvent, а затем будет спать в течение времени, необходимого для заполнения автомобиля. Вы делаете то же самое для TankerArrivalEvent.

0 голосов
/ 28 октября 2010

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

...