Поток поступающих требований ограничен, то есть одновременно в системе обслуживания не может находиться больше m требований, где m — конечное число. Это дает право считать, что требования на обслуживание поступают от m обслуживаемых объектов, которые время от времени нуждаются в обслуживании. Пусть вероятность того, что поступит заявка на обслуживания на данном такте равна Р(А) и вероятность того, что требование из очереди поступит на обслуживание равно Р(В) ( на каждом такте может поступить не более одной заявки на обслуживание). Число обслуживающих аппаратов равно N. Допустим, требование дождалось своей очереди и оно начало обслуживаться. Обслуживание может длиться в течении не более 3-х тактов. Заявки могут быть двух приоритетов:
Заявка первого приоритета:
Это обычная заявка, она не обладает ни какими привилегиями. Она может покинуть систему через определенное число тактов Т. При приходе в обслуживающую систему заявка первого приоритета становится в конец очереди.
Заявка второго приоритета:
Эта заявка отличается только тем, что она при поступлении в обслуживающую систему становится в начало очереди, то есть как только освобождается аппарат, то она поступает на обслуживание с вероятностью Р(В).
Заявка второго приоритета , как и заявка первого приоритета, покидает систему через Т тактов. Естественно, что появление заявок второго приоритета достаточно мало ( хотя эта вероятность задается пользователем и может быть любой ). Теперь об обслуживании: Количество тактов, в течение которых будет обслуживаться та или иная заявка выбирается случайно (эта величина в данной задаче не должна быть больше 3). Если заявка обслужилась положенное ей число тактов, то она покидает систему. Если заявка находится в очереди больше Т тактов, то она с некоторой вероятностью покидает систему.
Алгоритм
Наиболее рациональна реализация очередей в виде списковых структур данных. Данная задача при ее реализации на ЭВМ дает большие навыки при работе со списковыми структурами и при написании алгоритма программы следует воспользоваться стандартными процедурами, такими как присоединение элемента в начало и конец списка, удаление произвольного элемента из списка. Эти процедуры имеют следующий вид:
Процедура прибавления элемента в начало списка.
p = getnode Node(p) — элемент, на который указывает
info(p) = d указатель Р
ptr(p) = lst info(ptr(p)) — информационное поле следующего
lst = b элемента списка
Процедура удаления из начала списка.
p = lst
х = info(p)
lst = ptr(p)
freenode(p) — делает свободный узел с указателем
Процедура прибавления элемента в список.
p = getnode q — вставляемый
info(p) = x
ptr(q) = ptr(p)
ptr(p) = q
Процедура удаления из списка
q = ptr(p) q — удаляемый
ptr(p) = ptr(q)
x = info(p)
freenode(q)
Структуры и алгоритмы обработки данных
Поток поступающих требований ограничен, то есть одновременно в системе обслуживания не может находиться больше m требований, где m — конечное число. Это дает право считать, что требования на обслуживание поступают от m обслуживаемых объектов, которые время от времени нуждаются в обслуживании. Пусть вероятность того, что поступит заявка на обслуживания на данном такте равна Р(А) и вероятность того, что требование из очереди поступит на обслуживание равно Р(В) ( на каждом такте может поступить не более одной заявки на обслуживание). Число обслуживающих аппаратов равно N. Допустим, требование дождалось своей очереди и оно начало обслуживаться. Обслуживание может длиться в течении не более 3-х тактов. Заявки могут быть двух приоритетов:
Заявка первого приоритета:
Это обычная заявка, она не обладает ни какими привилегиями. Она может покинуть систему через определенное число тактов Т. При приходе в обслуживающую систему заявка первого приоритета становится в конец очереди.
Заявка второго приоритета:
Эта заявка отличается только тем, что она при поступлении в обслуживающую систему становится в начало очереди, то есть как только освобождается аппарат, то она поступает на обслуживание с вероятностью Р(В).
Заявка второго приоритета , как и заявка первого приоритета, покидает систему через Т тактов. Естественно, что появление заявок второго приоритета достаточно мало ( хотя эта вероятность задается пользователем и может быть любой ). Теперь об обслуживании: Количество тактов, в течение которых будет обслуживаться та или иная заявка выбирается случайно (эта величина в данной задаче не должна быть больше 3). Если заявка обслужилась положенное ей число тактов, то она покидает систему. Если заявка находится в очереди больше Т тактов, то она с некоторой вероятностью покидает систему.
Алгоритм
Наиболее рациональна реализация очередей в виде списковых структур данных. Данная задача при ее реализации на ЭВМ дает большие навыки при работе со списковыми структурами и при написании алгоритма программы следует воспользоваться стандартными процедурами, такими как присоединение элемента в начало и конец списка, удаление произвольного элемента из списка. Эти процедуры имеют следующий вид:
Процедура прибавления элемента в начало списка.
p = getnode Node(p) — элемент, на который указывает
info(p) = d указатель Р
ptr(p) = lst info(ptr(p)) — информационное поле следующего
lst = b элемента списка
Процедура удаления из начала списка.
p = lst
х = info(p)
lst = ptr(p)
freenode(p) — делает свободный узел с указателем
Процедура прибавления элемента в список.
p = getnode q — вставляемый
info(p) = x
ptr(q) = ptr(p)
ptr(p) = q
Процедура удаления из списка
q = ptr(p) q — удаляемый
ptr(p) = ptr(q)
x = info(p)
freenode(q)
Задания
Общее задание для всех.
Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84