Лабораторная работа №2
ОПРЕДЕЛЕНИЕ МИНИМАЛЬНОГО БЫСТРОДЕЙСТВИЯ
ПРОЦЕССОРА
1. Цель работы
Исследование способов организации вычислительного процесса в цифровых управляющих системах и определение быстродействия процессора ЦВМ. В ходе выполнения работы студент знакомится с основными способами организации вычислительного процесса для различных режимов работы ВС и получает навыки расчета его количественных характеристик и формирования требований к быстродействию процессора для обеспечения заданного качества работы ВС.
2. Задание
2.1. Ознакомится с основными параметрами машинных алгоритмов и показателями качества ЦУС.
2.2. Изучить основные дисциплины обслуживания заявок и системы приоритетов ЦУС.
2.3. Определить минимальное значение быстродействия процессора ЦУС.
2.4. Определить показатели качества ЦУС для различных дисциплин обслуживания заявок ЦУС.
2.5. Определить оптимальное значение процессора ЦУС.
3. Рабочее место
Работы выполняются на ПЭВМ. При выполнении работ используется программный комплекс для исследования моделей систем обработки данных.
4. Теоретическая часть
4.1 Работа процессора в цифровой управляющей системе
Цифровыми управляющими системами (ЦУС) называются системы, работающие в реальном масштабе времени (РМВ) с объектом, непрерывно функционирующим во времени (управление ядерным реактором, коммутационным оборудованием автоматической телефонной станции и т.п.).
Режим работы при котором существуют предельные ограничения на время реализации программы, называется работой в РВМ. РВМ обеспечивается корректным выбором быстродействия устройств, входящих в управляющую систему, и соответствующим планированием порядка выполнения программ.
ЦУС, функционирующие в РВМ, работают по программам, хранимым в памяти системы. Последовательность выполнения программ определяется заявками, поступающими в вычислительную систему от управляемых объектов.
Заявки поступают в устройство прерывания системы и становятся в соответствующую очередь на обслуживание. Правило, на основании которого из очереди выбираются заявки на обслуживание, называется дисциплиной обслуживания.
В силу того, что в моменты поступления заявок являются случайными величинами, функционирование ЦУС носит стохастических характер. Это позволяет рассматривать ЦУС как системы массового обслуживания и описывать их в терминах этой теории.
Важнейшими характеристиками качества функционирования ЦУС являются:
1. Длительность времени обслуживания заявки, которая равна промежутку времени, необходимого устройству для обслуживания заявки. В общем случае – это случайная величина, характеризующаяся законом распределения и математическим ожиданием (средним значением).
2. Интенсивность обслуживания характеризует количество заявок, которое может быть обслужено в единицу времени
, (2.1)
3. Загрузка системы
, (2.2.)
где – интенсивность поступления заявок в систему.
Значение определяет среднее число заявок, поступивших в систему за среднее время обслуживания одной заявки. Наряду с этим величина загрузки характеризует долю времени, в течение которого обслуживающее устройство занято обслуживанием заявок, и одновременно вероятность того, что в произвольный момент времени обслуживающее устройство работает (не простаивает).
Коэффициент простоя системы характеризует вероятность того, что система не занята обслуживанием заявок
, (2.3)
При этом предполагается, что , что справедливо для всех реальных систем при их работе в стационарном режиме.
Стационарный (установившийся) режим работы – это такой режим работы, при котором вероятностные характеристики функционирования системы не зависят от времени. Условие существования стационарного режима определяется значением загрузки.
Время пребывания заявок в системе равно промежутку времени от момента поступления заявки в систему, до момента окончания ее обслуживания в устройстве. Время пребывания u складывается из времени ожидания w, когда заявка находится в очереди, и времени обслуживания ее в устройстве, т.е.
, (2.4)
Для систем, в которых поступившая заявка ожидает в очереди обслуживания сколь угодно долго, не покидая систему, средняя длина очереди определяется как
, (2.5)
а среднее число заявок в системе равно
, (2.6)
При обработке ЦУС многомерного потока заявок на вход обслуживающего устройства поступает поток заявок с интенсивностью , состоящей из заявок типа 1,…,M. В этом случае загрузка устройства потоком заявок типа i, будет составлять
, (2.7)
где – средняя длительность обслуживания заявок типа i.
Суммарная (общая) загрузка прибора со стороны всех потоков
, (2.8)
В этом случае условие существования стационарного режима определяется в виде R<1 и коэффициент простоя устройства . Остальные характеристики обслуживания определяются для каждого потока аналогичным образом и для заявок типа i равны ; ; .
Среднее время ожидания и пребывания одной заявки из суммарного потока в системе
, (2.9)
, (2.10)
где — суммарная интенсивность поступления заявок в систему; – вероятность того, что поступившая заявка является заявкой типа i; – среднее число заявок всех типов, находящихся в очереди; – среднее число заявок всех типов в системе.
В зависимости от требований к временным характеристикам ЦУС принято разделять на следующие основные классы:
1) с неограниченным временем пребывания заявок;
2) с относительными ограничениями на время пребывания заявок;
3) с абсолютными ограничениями на время пребывания заявок.
В качестве критерия эффективности ЦУС выбирается коэффициент потери качества функционирования из-за задержки обслуживания заявок, который характеризуется функцией штрафа. Для ЦУС с неограниченным временем пребывания заявок функция штрафа имеет вид:
, (2.11)
где – штраф за задержку одной заявки типа i на единицу времени.
Произведение определяет штраф за задержку обслуживания заявок типа i, поступающих в систему за единицу времени, а значение – штраф за задержку всех заявок. Критерий (2.11) инверсный: с увеличением качества системы значение уменьшается.
Если штрафы одинаковы для всех потоков заявок, то критерий принимает вид
, (2.12)
где – средняя длина очереди всех заявок типа i. Значение есть средняя длина очереди всех заявок.
Задержки, т.е. времена ожидания зависят от двух факторов: быстродействия процессора и дисциплины обслуживания заявок. Увеличение быстродействия приводит к уменьшению всех значений . За счет использования приоритетных дисциплин можно уменьшить времена ожидания заявок одних типов, но при этом времена ожидания заявок других типов увеличатся.
При использовании критерия (2.11) предполагается, что быстродействие процессора задано и оно может быть использовано в задаче выбора дисциплины обслуживания заявок, при условии обеспечения стационарного режима в системе. Минимальное значение быстродействия процессора , при котором может быть найдена дисциплина обслуживания, удовлетворяющая ограничениям на время ожидания заявок, является нижней оценкой быстродействия процессора.
После того, как найдена оптимальная дисциплина обслуживания, возникает задача уточнения быстродействия процессора B, заключающаяся в определении оптимального значения в смысле некоторого критерия. Такой критерий должен учитывать как возможность уменьшения времени ожидания заявок при увеличении B, так и эффективность использования процессора, которая может быть охарактеризована коэффициентом простоя процессора.
, (2.13)
Желательно, чтобы величина была бы минимальной.
Очевидно, что можно предположить о существовании некоторого оптимального решения, позволяющего определить B с учетом двух указанных противоречащих факторов. В качестве критерия эффективности в этом случае может быть использован функционал вида
, (2.14)
где – полное время ожидания заявок в очереди i-го типа (i = 1,…,M); – некоторые весовые коэффициенты, задаваемые при проектировании ЦУС (i = 1,…,M).
В ЦУС с относительными ограничениями на время пребывания заявок налагаются ограничения на средние времена пребывания (ожидания) заявок всех типов и задаются в виде неравенств:
, (2.15)
где – предельное ограничение времени ожидания заявки типа i = 1,…,M.
В ЦУС с абсолютными ограничениями на время пребывания заявок требования, предъявляемые к качеству обслуживания заявок, более жесткие, чем в ЦУС с относительными ограничениями. Это означает, что ограничения, заданные в виде (2.15), должны выполнятся не в среднем, а для большинства заявок. Особенно это важно для систем, где превышение допустимого ограничения на время пребывания заявки приводит к ее потери или резкому снижению ее ценности.
Показателем качества функционирования таких систем может служить вероятность превышение допустимого времени ожидания: .
Качество функционирования ЦУС тем выше, чем меньше эта вероятность. В случае M потоков заявок потеря качества функционирования может характеризоваться функцией штрафа:
, (2.16)
где – вероятность превышения допустимого времени ожидания заявки i-го типа; – штраф за превышение одной заявкой типа i допустимого ограничения.
На основании исследований статистических моделей установлено, что для широкого класса дисциплин обслуживания распределение времени ожидания потока заявок можно аппроксимировать с удовлетворительной точностью выражением
, (2.17)
где w – среднее время ожидания заявок в очереди; – предельно допустимое время ожидания.
Таким образом, среднее время ожидания w зависит от дисциплины обслуживания заявок и коэффициента простоя. Выбирая дисциплину обслуживания, уменьшающую w можно снизить вероятность превышения предельно допустимого времени ожидания. Такой же результат достигается путем уменьшения суммарной загрузки R системы, т.е. путем повышения быстродействия процессора.
В общем случае ограничения на время пребывания заявок могут быть: неограниченные, относительные и абсолютные. Это означает, что из M типов заявок, поступающих в ЦУС, типов имеют абсолютные ограничения, – относительные, – не имеют ограничений, причем .
При этом задачи синтеза формулируются следующим образом: требуется выбрать такое быстродействие процессора и такую дисциплину обслуживания заявок, при которых выполняются следующие ограничения на времена ожидания:

и критерий
, (2.18)
принимает минимальное значение. Здесь – штраф за простой процессора; – штраф за потерю заявок; – штраф за задержку заявок.
Таким образом, задача синтеза ЦУС может быть расчленена на три этапа:
1) определяется величина , обеспечивающая как минимум существование стационарного режима, а при наличии ограничений на время ожидания заявок – существование некоторой дисциплины обслуживания, удовлетворяющей этим ограничениям;
2) выбирается дисциплина обслуживания заявок, отвечающая ограничениям на времена ожидания (2.15) или оптимальная в смысле критерия (2.11) и (2.16);
3) для выбранной дисциплины обслуживания определяется величина B, обеспечивающая требуемое качество обслуживания заявок при минимально возможном простое процессора, т.е. оптимальное в смысле критерия (2.14).

4.2. Определение минимального быстродействия процессора
В качестве первого этапа синтеза ЦУС определяется нижняя оценка быстродействия процессора.
Для ЦУС с неограниченным временем пребывания заявок минимально необходимое быстродействие определяется из условия
, (2.19)
где – трудоемкость обслуживания заявок (алгоритмов).
При наличии относительных ограничений на время пребывания заявок минимально необходимое быстродействие определяется из условия

, (2.20)
где – второй начальный момент трудоемкости обслуживания заявки i-го типа.
При выражение (2.20) переходит в (2.19).
В ЦУС при организации вычислительного процесса возникают задачи, связанные с обеспечением различных временных критериев при обслуживании заявок различных типов. Это достигается применением различных дисциплин обслуживания заявок. В результате уменьшается время ожидания для одних типов заявок за счет увеличения времени ожидания заявок других типов.
В зависимости от преимущественного права на обслуживание заявок различают: бесприоритетные заявки, не имеющие определенных привилегий; заявки с относительным приоритетом, т.е. для которых приоритет учитывается только в момент выбора заявки на обслуживание; заявки с абсолютным приоритетом – заявки, которые прерывают обслуживание заявок с более низким приоритетом.

4.3. Характеристики бесприоритетных дисциплин обслуживания
При бесприоритетной дисциплине заявки разных типов не имеют заранее определенных привилегий на досрочное обслуживание. Это правило выполняется, если заявки на обслуживание выбираются:
1) в порядке поступления (первой обслуживается заявка, поступившая раньше других (FIFO));
2) в порядке, обратном порядку поступления (первой обслуживается заявка, поступившая позже (LIFO));
3) в порядке случайного выбора.
Эти три дисциплины характеризуются одинаковым средним временем ожидания заявок, но дисциплина FIFO минимизирует дисперсию времени ожидания и поэтому применяется чаще других.
Если известны и вторые начальные моменты времени обслуживания заявок, тогда для бесприоритетной дисциплины обслуживания среднее время ожидания всех заявок всех типов одинаково и равно
, (2.21)
Представим второй начальный момент через коэффициент вариации в следующем виде:
, (2.22)
С учетом этого среднее время ожидания
, (2.23)
Время пребывания заявки типа i=1,…,M в системе . Так как при бесприоритетном обслуживании все , то время пребывания . При одинаковом времени ожидания время заявок различно.

4.4. Характеристики дисциплины обслуживания
с относительными приоритетами заявок
В случае необходимости представления некоторым типам заявок перед другими преимущественного права на обслуживание используют приоритеты. Приоритеты заявок характеризуются целыми положительными числами 1,2,3 …, причем высокому приоритету соответствует меньшее число. Относительные приоритеты учитываются только в момент выбора заявки на обслуживание. В момент выбора сравниваются приоритеты заявок, находящихся в состоянии ожидания, и обслуживание представляется заявке с наиболее высоким приоритетом. После этого выбранная заявка захватывает процессор. При поступлении после этого заявок с более высокими приоритетами ее обслуживание не прекращается, т.е. эта заявка, захватив процессор, оказывается наиболее приоритетной. Этот приоритет относительный, он имеет место только после захвата процессора.
Если в систему поступает M простейших потоков с параметрами при (i=1,…,M), то среднее время ожидания заявок, имеющих приоритеты k=1,…,M, определяются значениями
, (2.24)
где и – загрузки, создаваемые потоками заявок соответственно.
Используя коэффициенты вариации длительности обслуживания, выражение можно представить в виде
, (2.25)

4.5. Характеристики обслуживания с абсолютными приоритетами
В ряде случаев время ожидания заявок некоторых типов нужно уменьшить в такой степени, которая недостижима при использовании относительных приоритетов. В таких случаях используется дисциплина обслуживания с абсолютными приоритетами. Работа процессора тогда организуется следующим образом: для каждого потока заявок устанавливается очередь , в которой заявки размещаются в порядке поступления. Заявкам соответствуют абсолютные приоритеты 1,…,M. Если процессор занят обслуживанием заявки , то при заявка заносится в конец очереди , а при i>j обслуживание заявки прерывается, заявка заносится в начало очереди и программа-диспетчер переключает прибор на обслуживание заявки .
Обслуживание прерванных заявок может производится:
1) от начала;
2) от момента прерывания (дообслуживание).
Обычно стараются использовать второй способ – дообслуживание прерванных заявок, при этом сохраняется вся информация о процессе обслуживания, необходимая для продолжения обслуживания. В случае, когда длительность обслуживания распределена по экспоненциальному закону, среднее время дообслуживания совпадает со средним времени обслуживания.
Если потоки заявок простейшие, известны величины и прерванные заявки дообслуживаются от точки прерывания, то среднее время ожидания заявки с абсолютными приоритетами k=1,…,M
, (2.26)
где – загрузка системы от первых j потоков заявок.
При этом для систем с одним обслуживающим устройством выполняется закон сохранения времени ожидания: для любой дисциплины обслуживания величина
, (2.27)
т.е. инвариантна относительно дисциплины обслуживания.
Закон (2.27) справедлив, если система отвечает следующим требованиям:
1) отсутствие отказов в обслуживании, т.е. все заявки на обслуживание удовлетворяются;
2) система обслуживания простаивает лишь в том случае, когда на ее входе нет заявок на обслуживание;
3) при наличии прерываний длительность обслуживания описывается экспоненциальным распределением;
4) все входные потоки описываются независимыми пуассоновскими распределениями, и длительность потоков не зависит от входящих потоков.
Закон сохранения времени ожидания универсален и справедлив для всех дисциплин обслуживания заявок, удовлетворяющих перечисленным требованиям. Его можно использовать для оценки достоверности приближенных результатов, полученных при анализе сложных дисциплин обслуживания и проведения статистического моделирования.

4.6. Выбор класса приоритетов
После определения нижней оценки быстродействия процессора возникает задача выбора дисциплины обслуживания заявок, обеспечивающей минимум значения критерия эффективности (2.11) для систем с неограниченным временем пребывания заявок или минимум критерия эффективности (2.16) для систем с абсолютными ограничениями на время пребывания заявок и выполнения ограничений для систем с относительными ограничениями. Такая дисциплина обслуживания может считаться оптимальной.
Перед решением задачи выбора дисциплины обслуживания заявок необходимо установить режим обработки их очередей (одиночный, групповой, смешанный). Если режим обработки не задан, то его выбор должен осуществляться на основе требований, предъявляемых к способу управления потоками заявок с учетом достоинств каждого из режимов: одиночный режим обработки обеспечивает защиту особо важных заявок при возникновении кратковременных перегрузок за счет резкого ухудшения качества обслуживания или потери заявок низкого приоритета; при групповом режиме значительно меняются непроизводительные затраты ресурсов процессора на диспетчирование; смешанный режим обработки занимает промежуточное положение между одиночны и групповым режимом.
При одиночном режиме обработки очередей заявок сначала выбираем класс приоритетов, присваиваемых заявкам (дисциплины бесприоритетные, с относительными, абсолютными и смешанными). Затем в классе бесприоритетных дисциплин обслуживания должна решаться задача оптимального распределения приоритетов в соответствии с выбранным критерием эффективности.
Условием выиграша при введении относительных приоритетов по сравгнению с бесприоритетными дисциплинами обслуживания является соотношение
(p=1,…,M-1), (2.28)
Таким образом, задача оптимального назначения приоритетов сводится к расположению приоритетов в порядке убывания величины .
Условие выиграша при использовании дисциплины обслуживания с абсолютными приоритетами по отношению к дисциплине с относительными приоритетами в случае M потоков заявок имеет вид
, (2.29)
Условие выиграша для дисциплин обслуживания с абсолютными приоритетами по отношению к бесприоритетной дисциплине совпадает с (2.28).
При экспоненциальном распределении длительности обслуживания заявок, как правило, условие (2.28) служит также для оптимального назначения абсолютных приоритетов.

4.7. Определение оптимального быстродействия процессора
Для бесприоритетных дисциплин обслуживания с неограниченным временем пребывания заявок оптимальное быстродействие процессора
, (2.30)
Для ЦУС, к которым не предъявляются никакие требования по времени пребывания заявок (кроме требования, чтобы все заявки были обслужены за конечное время) и для которых k=0, оптимальное значение совпадает с нижней оценкой быстродействия процессора. Но чем выше требования, предъявляемые к качеству обслуживания заявок, т.е. чем выше k, тем более высокое быстродействие процессора должно быть выбрано по сравнению с нижней оценкой.
В общем случае, кроме ограничений на время ожидания заявок задаются и ограничения на коэффициент простоя и задача определения оптимального быстродействия формулируется следующим образом: найти значение быстродействия B, которое обеспечивает минимум критерия эффективности (2.14) при ограничениях
(i=1,…,M), B>0, (2.31)
Для ЦУС с бесприоритетной дисциплиной обслуживания и относительными ограничениями на время пребывания заявок оптимальное быстродействие процессора определяется на основании неравенства

, (2.32)
где – среднее предельно допустимое время ожидания заявок.
Для ЦУС с абсолютными ограничениями на время пребывания заявок задача с определением оптимального быстродействия процессора решается с использованием критерия эффективности, построенного по аналогии с критериями для систем с относительными ограничениями. Этот критерий может быть записан в виде
, (2.33)
Выражение для оптимального быстродействия не может быть получено в явном виде даже для простейших случаев, поскольку задача сводится к решению трансцендентного уравнения. Оно может быть найдено в каждом конкретном случае для заданных характеристик заявок с помощью численных методов.

5. Порядок выполнения работы
5.1. Ознакомится с методикой определения быстродействия процессора на ПЭВМ.
5.2. Определить быстродействие процессора ЦУС. Исходные параметры выбираются из таблицы 2.1 согласно номеру варианта, а значения трудоемкости для систем при М = 5 задаются преподавателем по результатам выполнения лабораторной работы №1.
а) Определить нижнюю оценку быстродействия процессора.
б) Осуществить распределение приоритетов.
в) Определить время ожидания заявок и функции штрафов для различных дисциплин обслуживания.
г) Определить оптимальное быстродействие для бесприоритетной дисциплины обслуживания с неограниченным временем пребывания заявок; с относительным ограничением на время пребывания заявок.
5.3. Определить оптимальное быстродействие для бесприоритетных дисциплин обслуживания на одном графике. Построить зависимость и для , изменяющегося от 0 до 1 с шагом 0,2 и , изменяющегося от 0 до 0,5 с шагом 0,1. Определить область решения неравенства. Пример определения быстродействия процессора приведен в программном комплексе.

6. Содержание отчета
6.1. Цель работы.
6.2. Таблица со значениями переменных и параметров своего варианта и результаты расчетов лабораторной работы №1.
6.3. Таблицы с результатами расчетов по п. 5.2.
6.4. Графики зависимостей и .
6.5. Выводы.

7. Контрольные вопросы

7.1. Перечислите и кратко охарактеризуйте основные режимы обработки данных.
7.2. Какие существуют системы назначения приоритетов и каким образом влияет распределение приоритетов на параметры процессора?
7.3. Какие критерии могут быть использованы при оптимизации параметров процессора для режимов оперативной обработки, реального масштаба времени, пакетной обработки?
7.4. При каких условиях для систем с одним обслуживающим приоритетом выполняется закон сохранения времени ожидания при любой дисциплине обслуживания заявок?
7.5. В каком режиме работает ЦУС, если быстродействие процессора превышает величину его нижней оценки?
7.6. Какие факторы влияют на выбор дисциплины обслуживания заявок?
7.7. Какие критерии используются при определении оптимального значения быстродействия процессора?

Таблица 2.1.

Исходные данные для определения быстродействия процессора ЦУС

№ ва-рианта
Оп/с k
1 1,1 5,2 4 5,5 1,7 1 2 3 10 15 150000 0
2 8,1 4,1 1 2 4,2 1 3 4 9 14 100000 1
3 3,3 5 4 8,5 1 1 2 5 10 15 100000 2
4 7 1,5 12 1,4 2 1 3 4 9 20 110000 3
5 2,5 2 4 1 2,6 1 3 5 10 25 90000 0
6 1 3 4,1 2 5 1 2 3 15 20 80000 1
7 2 2 3 2,1 1,5 1 3 4 10 15 105000 2
8 1 7 7 12 8,2 1 2 4 10 15 150000 3
9 2,4 2 8 4 3,5 1 3 4 15 16 100000 0
10 7 3 4 1,9 2 1 2 4 10 20 100000 1
11 1,3 6,3 14,8 1,8 10,1 1 2 3 10 15 145000 2
12 1,5 7,1 5,2 1,1 0,8 1 3 4 10 18 100000 3
13 2,1 2,3 5,1 2 5,3 1 2 4 8 20 100000 0
14 3,8 4,1 5,3 1 8,4 1 2 2 10 15 90000 1
15 4,1 3,2 6,8 5,7 8,8 1 2 3 9 15 140000 2
16 1,8 1,5 7,2 8,1 2,5 1 1 3 10 13 110000 3
17 2,5 3,7 1,3 6,7 15,3 1 1 2 8 15 135000 0
18 6,1 6,3 1,1 2,3 4,2 1 2 3 8 20 100000 1
19 6,2 1,3 2,9 7,8 7,2 1 2 2 2 10 120000 2
20 5,3 4,8 1,9 5,2 1,3 1 3 3 3 10 125000 3
21 4,6 6,7 1,2 1,2 9,8 1 1 1 1 1 100000 3
22 3,4 1,4 4,1 4,8 7,8 1 2 3 6 15 135000 0
23 1,8 2,2 2,6 2,1 8,5 1 3 4 10 20 100000 1
24 1,7 1,2 3,3 7,3 9,3 1 1 3 10 15 100000 2
25 4,2 7,1 1,2 3,2 3,6 1 2 3 10 25 100000 0