Диссертация (1144013), страница 16
Текст из файла (страница 16)
В зависимости от ситуации выбор можетосуществляться или в абсолютно-приоритетном доступе, относительно приоритетномдоступе или бесприоритетном доступе. Каждая заявка имеет свой приоритет, взависимости от того откуда она поступает. До блока выбора заявки с разнымиприоритетами никак не пересекаются и поэтому их задержки рассчитываютсяиндивидуально вне расчета для блока выбора. В блоке выбора происходит выбор –какая заявку текущий момент времени будет выбрана для обработки и обработана.Каждая заявка может обрабатываться блоком выбора разное количество времени. Вкаждый момент времени только одна заявка может обрабатываться блоком выбора, вто время как в очереди может находится множество заявок с разными приоритетами.Возможны два варианта приоритетов в данном блоке – это абсолютный, иотносительный. При относительном приоритете при поступлении заявки с болеевысоким приоритетом – данная заявка ожидает обработку текущей заявки, какого бынизкого приоритета заявка в обработке не была в данный момент времени.
Послеобработки данной заявки – на обработку поступает заявка с самым высокимприоритетом, которая требует обработки на данный момент. Если приоритетабсолютный, то, как только заявка с более высоким приоритетом, чем заявка, котораяобрабатывается в данный момент, поступает в блок выбора - она немедленно попадаетна обработку блоком выбора, а заявка, которая не была полностью обработана –возвращается в ожидание. Данная заявка будет дообработана позже.64При бесприоритетном доступе все заявки имеют одинаковый приоритет, и ониотправляются последовательно из каждого канала (Рисунок 24).Канал 1Канал 2Канал 3Выборканала...Канал mРисунок 24. Модель СМО с одним каналомБлок выбора канала изначально будем рассматривать как общий случай блока сприоритетом обслуживания заявок M/G/1, причем с тем свойством, что поступающиезаявки делятся на несколько классов различного приоритета; 1-й класс имеетнаивысший приоритет, 2-й класс—второй по величине приоритет и т.
д. Данноедоказательство для приоритетного доступа было выведено с использованиедоказательства для системы M/G/1 для формулы Полячика Хинчина [94].Система массового обслуживания с одной очередью, в которой заявки поступаютв соответствии с пуассоновским процессом с интенсивностью X , длительности обслуживания заявок имеют экспоненциальное распределение. Предположим, что заявкиобслуживаются в порядке поступления, X t — длительность обслуживания i - й заявки,случайные величины (Х1, Х 2, ...) одинаково распределены, взаимно независимы и независят от интервалов между моментами поступления.Введем следующие значения = Е { X } = µ – средняя длительность обслуживания, = Е { X 2 } – второй момент длительности обслуживания.Для начала рассмотрим систему, где часть заявок находится в очереди и на входпоступает i-я заявка, в обслуживании находится заявка j, а в очереди некотороеколичество заявок.
Система обладает следующими характеристиками: , - время ожидания в очереди для i-й заявки; - остаточное время обслуживания в момент поступления i-й заявки. Этоозначает, что если заявка находится на обслуживании в момент появления заявки i, то равно промежутку времени от этого момента до завершения обслуживания заявки.Если нет заявки, которая обслуживается (т. е. система пуста в момент поступлениязаявки i), равно нулю; - Длительность обслуживания i-й заявки - Число требований, которые в очереди при поступлении i-й заявкиТаким образом = +∑ (11)65Проводя операции подстановки - получаем следующий результат = + µ (12)Вышеозначенные формулы корректны только в том случае, если выполняютсяпределы для данным систем, так как они существуют только в том случае, если λ<µ, чтообъяснимо, так как в противоположном случае очередь будет бесконечноувеличиваться.Мы получили формулу для средней задержки заявок, которые ожидают в очередина обработку.
Теперь, учитывая выведенную формулу – рассчитаем задержку длязаявок без отказа обслуживания, то есть несмотря на любой приоритет – текущая заявкабудет обработана.Введем обозначения — среднее число заявок в очереди k-го приоритета; — среднее время ожидания в очереди для заявки k-гo приоритета; — коэффициент использования системы для k-ro приоритета, рассчитываем поформуле =µ,Сумма коэффициентов использованияиспользования системы, причемдаютнамобщийкоэффициент + + + ⋯ + < 1 (13)Если это не выполняется, то задержка некоторого класса заявок будетбесконечной.Как и в приведенном выше выводе для наивысшего приоритета, получимследующую формулу(14) =+µ Воспользовавшись теоремой Литта, преобразуем в = (15)Подставив данное значение в формулу получим(16) = + И приводя к =(17)Для заявок второго приоритета получим аналогичное выражение, за темисключением, что необходимо учесть задержку, которая возникла из-за заявок болеевысокого приоритета, которые так же поступают в систему, и поступают на обработкураньше.В общем виде формулу для можно выразить как = +µ +µ +µ (18)66Используя теорему Литтла для общего случая и подставив в формулу для иформулу = =(µполучаем после преобразований получаем)()(19)Если и дальше использовать выводы, которые были использованы, то можнополучить следующий вариант для задержки k-го приоритета (который больше 1-го) =(⋯)(⋯)(20)Из данной формулы единственным неизвестным параметром представляетсясреднее остаточное время дообслуживания.
Его можно вычислить графическимспособом, где получается= ∑(21)Как итог – среднее время ожидания в очереди будет составлять∑ =(⋯)(⋯)(22)Данная формула представляет расчет времени для системы M/G/1. Чтобы сделатьрасчет для нашего блока выбора, а именно – системы M/M/1 необходимо учитыватьпараметр второго момента длительности обслуживания i-й заявки обозначен как .Длясистемы M/G/1 расчет может вызвать затруднения, однако в нашем случае нашасистема представляет собой СМО M/M/1 и в этом случае соответственно равен =µдля системы M/M/1.Средняя задержка в данном блоке заявки k-го приоритета будет составлятьвыбр = µ + (23)Теперь рассмотрим вариант, когда вместо относительных приоритетов данныйблок использует абсолютный приоритет, то есть заявки с более высоким приоритетомпоступают в обслуживание сразу, а заявки с более низким – ждут и дообслуживаютсяпосле.При вычислении среднего времени ожидания в очереди заявки k-го порядканеобходимо учитывать заявки с приоритетами с номером меньше k, в то время как всезаявки c приоритетом больше k игнорируются.Среднее время ожидания в очереди будет зависеть от обработки 2-хсоставляющих, а именно от среднего времени обслуживания заявок с приоритетом от 0до k-1, которые уже ждут обслуживания, и от среднего времени обслуживания заявок стем же приоритетом, которые поступили во время пребывания в очереди требования сприоритетом k.Второй параметр просто учитывает p всех заявок до k-го приоритета.
Такимобразом данный параметр , равный =⋯(24)67где – среднее остаточное время заявок k-го приоритета. Так как остаточноевремя не зависит от приоритета меньших порядков, то можно рассчитать по формуле = ∑(25)Общее среднеехарактеризовать как =нахождениеочередизаявкиk-гоприоритетаможно(26)+⋯вгде – это второй параметр, равный среднему времени обслуживания заявок,поступивших во время нахождения в очереди, равна среднему времени для заявокменьшего приоритета, чем k. Данный параметр можно рассчитать из среднего временипребывания заявок k-го приоритета, равное =µ + =µ +(27)+⋯Исходя из времени параметр рассчитывается как =∑µ =∑ = ∑(28)Подставив в вышеозначенное выражение получим =µ ++ ∑⋯(29)Преобразуя, получаем общую формулу задержки для данного блокавыбр = (µ(⋯⋯)()∑⋯)(30)Данная формула дает полную задержку нахождения требования k-го порядка всистеме при абсолютном приоритете требований.В вышеозначенной формуле также присутствует , который является вторыммоментом длительности обслуживания заявки, и соответственно равен = µдлясистемы M/M/1.
Это значение учитывается в конечной формуле. Блоки сортировкизаявок и задержка среды передачи сигналовЗадержка среды передачи сигналов считается, исходя из законов физики, котораяв основном делится на 2 типа кабелей – медный и оптический. Задержка, с которойинформация передается в проводах ограничена соответственно скоростью света (в 300тыс. км/с), что и является предельной скоростью передачи информации.
Рассчитаемминимальную задержку в кабеле из расчета задержки на 1 метр:11= =≈ 3,33 · 10 = 3,33 нс 300000000Соответственно – минимальная задержка каждого метра кабеля дает задержку в3.33 наносекунды. Коэффициент в данном случае равен 1.Если необходимо - дополнительно в задержках среды можно учитывать ошибки,которые могут произойти. Пусть ош – вероятность ошибки, обр – время обработкиошибки, которое будет затрачено на обработку данной ошибки. В этом случае время,которое будет потеряно на ошибке передачи заявки ош будет68ош = ош обр (31)Вероятность возникновения ошибки зависит от физических характеристиккоммуникационной среды и в данной работе не рассматривается.Итоговая формула для задержки среды для кабеля, длинной L, рассчитывается поформуле:сред = + ош(32)Что касается блоков сортировки заявок – общая задержка i-й заявки сорт считаетсядовольно просто, учитывая, что приемная часть не может задерживать приходящуюинформацию, ввиду отсутствия очереди, поэтому – в базовом случае – расчет задержкипредставляется простым значением в зависимости от количества тактов, потраченныхна обработку очередной заявки.2.8 Блок выдачиЗадержка в блоке выдачи (выходном буфере) вых рассчитывается как СМО M/M/1.Расчет для системы М/М/1выводится из описанных выше формул для одного каскадаконвейера и данные формулы можно применить для блока выдачи.
В этом случаеинтенсивность поступления заявок сохраняется равной изначальной λ, а µинтенсивности обработки задается системой, которая забирает данные из очередиизвне.2.9 Размер буфераРазмеры буферов (аппаратные затраты на очередь) для заявок i определяется спомощью формулы Литта =(33)где – интенсивность потока, а – среднее время задержки заявки.Данная формула дает средний размер заявок в очереди (или в системе). Учитываяданное значение можно сделать предположение о нужном размере буфера. Однако –среднее количество заявок не дает ответа – какая вероятность того, что данный буферне переполнится и система не будет простаивать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
