Здравствуйте, в универе получил задание, необходимо смоделировать СМО, но проблема в том, что я вообще не имею представления о том, как её делать.

Вот текст задания:

Система массового обслуживания состоит из обрабатывающего аппарата (ОА) и очереди заявок 2-х типов.

          T1           ___________________              ____              T2
>--------------+------|____|____|____|____|------------|_ОА_|-------+---------->
               |                                                    |
               ^                                                T3  v
               |                                                    |
               +------------------------<---------------------------+




Заявки 1-го типа поступают в "хвост" очереди по случайному закону с интервалом времени T1, равномерно распределённым от 0 до 5 едениц времени (е.в.). В ОА они поступают из "головы" очереди по одной, и обслуживаются также равновероятно ха время T2 от 0 до 4 е.в., после чего покидают систему.

Единственная заявка 2-го типа постоянно обращается в системе, обслуживаясь в ОА равновероятно за время Т2 от 0 до 4 е.в. и возвращаясь в очередь не далее 4-й позиции от её "головы". В начале процесса заявка второго типа входит в ОА, оставляя пустую очередь.

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


Пожалуйста помогите мне с этим ужасом, что к чему, зачем и как здесь делать? или ссылки на материал по этой теме дайте (яндексом ничего не шашёл).
Заранее благодарен.

Это сообщение отредактировал(а) Fally - 2.4.2007, 15:22

В чём собственно проблема?
Генерируем времена поступления 1000 заявок в систему...
Первая заявка - от 0 до 5... пускай рандомом выпало 3, тогда время следующей генерируется и прибавляется к времени старта предыдущей(если я правильно понял задание)... пускай у второй сгенерировалось 2, значит она войдёт в систему в момент времени 3+2=5...  строим массив на 1000 заявок...
(3),(5),...
Отлично, теперь мы знаем последовательность прихода заявок в систему по временам, соответственно будем знать, какое событие произойдёт следующим...
первое событие происходит во время 3 - приход первой заявки. Устанавливаем текущее время равным 3. ОА свободен, поэтому ставим заявку на обслуживание. Генерируем время обработки заявки - пускай 3. Тогда время освобожения ОА = текущее + 3 = 6.
Следующее событие приход в систему второй заявки - текущее время 5. Смотрим, ОА - занят, ставим в буффер.
Следующее время - 6. Событие освобождение ОА. Смотрим, есть ли что в буффере? Есть - в ОА, сдвигаем буффер, нет - идём на следующее событие.
И т.д. и т.п. + надо ещё учесть блуждающую заявку типа 2.
Понятно?

Это сообщение отредактировал(а) Ryoga - 2.4.2007, 17:03

В этотм то вся проблема, что время поступления не обязательно целое число + между поступлениями заявок могут быть разные интервалы времени.
И как раз в заявки типа 2 тоже есть проблема, т.к. она иногда будет вклиниваться в очередь.

P.S. При этом ни в коем случае время в модели не должно быть связано с временем реальным.

Это сообщение отредактировал(а) Fally - 2.4.2007, 17:03

И что, что не целое?
Ну будет у Вас массив (3,5),(5,8),... какая разница? Зная текущее время, время освобождения ОА, и следующей заявки, Вы знаете, что за событие у Вас будет обрабатываться в следующий "момент"... Собственно, ищем минимум от текущего времени между, следующей заявки поступающей в систему и освобождением ОА...
Событие приход заявки - обрабатываете так, освобождение ОА - так...
В смысле вклиниваться?
З.Ы.: О реальном времени никто не говорит...

То есть, если в очереди было более 4 заявок 1-го типа, то заявка 2-го типа становится на 4-ую позицию, а вся очередь сдвигается в сторону хвоста.

Ну, отлично... поставили заявку второго типа на позицию 4, а заявки первого типа, с четвёртой и т.д. сдвинули на единицу к хвосту... проблема то в чём?

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

Так эт я ступил. А как вообще организовать это "повременное" добавление заявок в очередь?

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

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

Если будет добавляеться в систему заявок со скоростью меньше, чем обрабатывает ОА, то тогда буффер очереди будет пустовать... так что, это врятли...

Мне препод говорил, что ситуация может быть любой, будь то пустая очередь или наоборот в ней может быть оч. много эл-тов.

Ты учти что паралельно идет обслуживание очереди причем с различным от добавления
интервалом

Допустим организовать одно просто а вот второе смутно выглядит

Fally, либо я не понимаю Вашу задачу, либо я не понимаю, что Вы не понимаете...  я реализовывал систему массового обслуживания в универе - ничего сложного там нет. Что там "смутно выглядит" мне не понятно...
Попробую записать, как я понял, может выяснится, что что-то не так...

вход           буффер         ОА           выход
                    ---     ---
---->--------- | | |...| | | ---- |*|------->
                    ---     ---
Правила:
1) Заявки приходят со входа, обрабатываются ОА и уходят на выход.
2) Если ОА занят, то заявка становится в буффер.
3) Когда освободится ОА, если в буффере есть заявка, она берётся оттуда по методу ФИФО (первый пришёл, первый вышел).
4) Если в буффер ставится заявка типа 2, тогда - если количество элементов там больше 3, все заявки в буффере с номером больше 3 сдвигаются, а заявка с типом 2 ставится на позицию 4.
5) Если обработанная заявка ОА является заявкой типа 2, то подаём её на вход, если нет, на выход.
Похоже?
Отлично... Итак схема... * - заявка.
                   -----    ------
-*->--------- | |*|...|*|*| ---- |*|------->
                   -----    ------
tz                  nm       n1      toa

t - текущее время.
tz - время прихода в системы следующей заявки со входа. (Понятно как считать?)
toa - время освобождения ОА от обрабатываемой заявки. (Понятно, как считать?)
n1...nm - индексы буффера, определяющие, что в этих ячейках находится заявка.
t,tz,toa - виртуальное время (просто числа типа float). Никакого отношения к реальному не имеет!

Следующий момент времени, который надо рассмотреть, определяется так.
  t = МИН(tz,toa).
отлично, перемещаемся в этот период времени.
  Если t = tz (событие "пришла заявка"):
ОА свободно? Если да, ставим на обслуживание. Нет - в буффер (постановка в буффер см. правила).
  Если t = toa (событие "освобожение ОА"):
Если заявка = 1, то выход. Если заявка = 2 - событие "пришла заявка 2" (m>3 - сдвигаем и т.д.).
И т.д.

Понятно?

Это сообщение отредактировал(а) Ryoga - 2.4.2007, 21:02

спасибо, как работать понятно... если будут вопросы я здесь напишу...


  
Вопрос для Ryoga: А на каком курсе университета вы делали СМО? У нас просто это дали на 1-ом + сказали выучить С++ на первой лабе, до этого речь шла о паскале... Вот и результат, что в голове начинается каша и непонятки со всеми этими СМО.