Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Поток поступающих требований ограничен, то есть одновременно в системе обслуживания не может находиться больше  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

Категория: Учебники