Содержание к диссертации
Введение
Глава I. Методы построения базиса допустимых расписаний для одностадийных детерминированных систем обслуживания 17
1. Основные определения 18
2. Полные системы обслуживания 26
3. Базис допустимых расписаний для системы обслуживания с одним прибором 33
4. Базис допустимых расписаний для системы обслуживания с несколькими параллельными приборами 43
Глава II. Алгоритмы составления расписаний на основе методов построения базиса допустимых расписаний ; 52
I. Активные расписания 53
2. Верхняя оценка числа прерываний в оптимальном расписании 60
3. Оптимизация расписаний с директивными сроками 70
4. Множество допустимых расписаний для системы обслуживания с несколькими параллельными приборами 76
Глаеа III. Расчет характеристик и планирование вычислительного процесса для вычислительных систем реального времени 82
I. Задачи расчёта характеристик и планирования вычислительного процесса при проектировании вычислительных систем реального времени 83
2. Расчёт быстродействия процессора вычислительной системы реального времени 90
3. Оценка количества ресурсов, необходимых для управления объектом в реальном времени 95
4. Результаты вычислительного эксперимента .» 103
Заключение 108
Литература но
- Полные системы обслуживания
- Базис допустимых расписаний для системы обслуживания с несколькими параллельными приборами
- Верхняя оценка числа прерываний в оптимальном расписании
- Расчёт быстродействия процессора вычислительной системы реального времени
Введение к работе
Потребности в высоком быстродействии и большом объёме памяти, предъявляемые к современным вычислительным системам (ВС), в настоящее время значительно опережают возможности вычислительной техники. В связи с этим задача разработки методов эффективного использования ресурсов ВС весьма актуальна.
Важное значение эта проблема имеет для ВС, применяемых для управления различными техническими объектами в реальном времени, поскольку к таким системам обычно предъявляются требования высокой надёжности при жёстких ограничениях на использование вычислительных ресурсов.
Поэтому при проектировании ВС реального времени возникает целый ряд задач, связанных с расчётом различных временных характеристик и характеристик основных ресурсов ВС, необходимых для управления объектом в реальном времени. Среди этих задач весьма важными являются расчёт необходимого быстродействия процессора, оценки потребностей в основных ресурсах ВС и построение расписаний выполнения комплекса программ, осуществляющих обработку информации и управление объектом в реальном времени.
В настоящей работе эти задачи рассматриваются главным образом для однопроцессорных ВС реального времени с учётом основных ресурсов ВС таких, как время центрального процессора (ЦП), основная память, вспомогательная память, периферийные устройства.
Вычислительные системы реального времени расчитаны на автоматический приём и обработку информации, поступающей в процессе управления различными техническими объектами, и вы- дачу управляющей информации непосредственно на исполнительные органы или человеку-оператору. В промышленности такие системы широко применяются с целью автоматизации процессов управления объектов с непрерывным и непрерывно-дискретным характером производства, в первую очередь, на химических, нефтеперерабатывающих, металлургических и бумагоделательных предприятиях. Весьма эффективно ВС реального времени используются для автоматизации различных энергетических объектов, автоматизации исследований, проводимых с помощью сложных экспериментальных установок, и для других целей [і].
Для ВС реального времени важнейшим параметром функционирования системы является время ответа. Как правило, все программы в таких системах должны быть обработаны с учётом временных ограничений на сроки их выполнения, зачастую довольно жёстких, чтобы обеспечить гарантированное время ответа системы. Прекращение измерения времени в этом случае эквивалентно полному отказу системы, т.к. теряется временная связь вычислительного процесса с состоянием источников внешней информации и потребителей вырабатываемых сигналов J2-4J.
Используемые в ВС реального времени управляющие ЭВМ обычно являются наиболее специализированными, т.к. к ЭВМ этого класса предъявляются весьма жёсткие требования по габариту, весу, потребляемой мощности и использованию внешних ресурсов. Поэтому алгоритмы и программы для ЭВМ в ВС реального времени приходится разрабатывать при весьма жёстких требованиях к оптимальности использования ресурсов управляющей ЭВМ [2].
При распределении ресурсов операционной системой зачастую возникает ситуация, когда программы, готовые к решению, - б - не могут быть полностью обеспечены необходимыми ресурсами. В таком случае операционная система реального времени (рСРВ) должна принимать решения относительно порядка обработки очереди для обеспечения наиболее эффективного использования ресурсов ВС и гарантированного времени ответа.
Важным видом ресурсов ВС, подлежащим распределению операционной системой, является так называемый повторно используемый ресурс, или ресурс нескладируемого типа. Ресурс этого типа обладает следующими свойствами: число единиц ресурса постоянно; каждая единица ресурса или доступна или распределена только одному процессу (разделение отсутствует) ; процесс может освободить единицу ресурса (сделать её доступной), только если он ранее получил эту единицу. Примерами ресурсов такого типа являются компоненты аппаратуры, такие, как основная память, вспомогательная память, периферийные устройства и, возможно, процессоры, а также программное обеспечение, такое, как файлы данных и таблицы [б].
В настоящее время большинство вычислительных систем реального времени имеют ОСРВ, которые дают возможность работать в режиме мультипрограммирования, позволяющем обрабатывать несколько программ одновременно. Режим мультипрограммирования обеспечивает, в частности, высокую загруженность вычислительных ресурсов и улучшает пропускную способность системы І4,5].
Одной из важных задач, с которой приходится сталкиваться при проектировании ВС реального времени, является задача оптимальной организации вычислительного процесса. Критерий эффективности вычислительного процесса для ВС реального времени должен обеспечивать гарантированное время ответа при минимальных потребляемых ресурсах ВС.
Обычно анализ вычислительного процесса, определение его числовых характеристик и проверка различных принципов планирования вычислений проводятся на имитационной модели ВС. Определение правил поведения и параметров отдельных частей имитационной модели, выбор и обоснование принципов планирования основывается на исследовании математических моделей [2-4,6-8].
Реальную ВС или её части представляют в виде стохастической или детерминированной модели массового обслуживания. Далее исследуют эту модель, используя аппарат теории расписаний, теории очередей, комбинаторного анализа, математического программирования.
Важным классом моделей планирования вычислительного процесса для ВС реального времени являются детерминированные задачи теории расписаний [2,3,6-8].
Многие задачи теории расписаний, представляющие интерес с точки зрения практики, принадлежат классу N 3 -полных задач [10,11,27,31,35-37,61,64,671. Широко распространена гипотеза, что для решения задач этого класса не существует алгоритмов полиномиальной временной сложности [29-3l].
В работах ^[2,41,45] предлагаются методы решения таких задач средствами математического программирования и на основе методов ветвей и границ.
В работах [І6,І9,47,48,69,70] исследуются частные случаи, когда hiS -полная задача разрешима за полиномиальное время.
В последнее время наряду с исследованием сложности детерминированных задач теории расписаний [30,31,67,71-73] большое внимание уделяется построению эффективных приближённых алгоритмов [ЗЗ], в которых за счёт снижения точности решения уменьшается трудоёмкость.
Среди детерминированных задач теории расписаний следует выделить класс задач, которые могут быть использованы при исследовании математических моделей ВС реального времени. Зто прежде всего задачи построения расписаний, не нарушающих директивных сроков обслуживания требований, для одностадийных детерминированных систем обслуживания.
Существует большое число работ, посвященных исследованию такого рода задач [9-27,40-54].
В системах этого типа множество требований о -{4,&,..., N обслуживается М >, 4 параллельными приборами, которые обычно считаются идентичными [17,18,27,32,43,46,50-56], но могут быть и различными [і6,49J
Требование Le S поступает в очередь на обслуживание в момент времени Ъс і и длительность его обслуживания равна Zi . Обычно предполагается также заданным директивный срок Jt обслуживания требования, т.е. момент времени, к которому обслуживание этого требования должно быть завершено.
На множестве требований может быть задано отношение частичного порядка, которое определяет возможную последовательность обслуживания требований. В самом общем случае последовательность обслуживания требований определяется направленным ациклическим графом [l4,15,28,48,54,56J, в других случаях эта последовательность задается параллельно-последовательной сетью, совокупностью деревьев или деревом [22,55,57, 58].
Обычно рассматривают две дисциплины обслуживания требований: обслуживание с прерываниями [13-18,20,21,23,24,26,32, 41-43,46,49,52,53] и без прерываний [12,14-16,19,22,27,28,
44,45,47-48,50,51,55-58]. При обслуживании требований с прерываниями обычно предполагается, что каждое требование одновременно может обслуживаться лишь одним прибором, причём на прерывания не расходуется дополнительное время.
В некоторых работах допускается возможность обслуживания требования одновременно несколькими приборами [І6-І8І.
Качество расписания обычно оценивается значением некоторой функции, аргументами которой являются моменты завершения обслуживания требований. Значение функции в этом случае представляет собой штраф за обслуживание требований, а расписание, которому соответствует наименьшее значение функции, называется оптимальным.
Обычно рассматриваются критерии качества расписания, при которых минимизируются следующие величины [9-11,15,18,22, 24-27,40,46-48,50-51,55-58]: общее время обслуживания требований; сумма (или среднее значение) моментов окончания обслуживания требований; взвешенная сумма моментов окончания обслуживания требований; взвешенная сумма величин, экспоненциально зависящих от моментов окончания обслуживания требований; сумма запаздываний в обслуживании требований; взвешенная сумма запаздываний; число запаздывающих требований; взвешенное число запаздывающих требований.
Как отмечалось выше, при исследовании математических моделей ВС реального времени особый интерес представляет задача построения расписаний, не нарушающих директивных сроков.
Эта задача для системы обслуживания с одним прибором рассматривается в работах [9-16,20-22,24-27,40,41,44-48,51, 53,54].
При обслуживании требований с прерываниями известны различные необходимые и достаточные условия существования допустимых (не нарушающих директивных сроков и ограничения предшествования требований') расписаний [J4-I6,20,21,26,46,53] и различные алгоритмы построения допустимых расписаний [9-II, 14-16,20,21,23,24,26,41,46].
В работах [20,24,46] получена верхняя оценка числа прерываний обслуживания требований по оптимальному расписанию, в предположении, что критерий оптимальности - минимальное число прерываний обслуживания требований. В этих работах предлагаются алгоритмы построения допустимого расписания, при котором прерывания обслуживания требований имеют место не чаще, чем в моменты поступления требований в систему.
В случае, когда прерывания обслуживания требований запрещены, задача построения допустимого расписания является /V о -полной в сильном смысле [ЗІ,72,73І.
В работах [12,41,45] предлагаются точные решения задачи построения допустимого расписания без прерываний обслуживания требований средствами математического программирования и методом ветвей и границ. Исследованию частных случаев, когда задача разрешима за полиномиальное время, посвящены работы [16,19,47,48,69,70]. В работе [44] определяются характеристики множества всех допустимых расписаний.
Задача построения допустимых расписаний для системы обслуживания с несколькими параллельными приборами рассматривается в работах [9-11,15,20-21,23,25,27,40,42,43,46,49-54]. - II -
В случае, когда разрешены прерывания обслуживания требований и не задано ограничение предшествования требований, известны необходимые и достаточные условия существования допустимых расписаний [20,21,46І.
В работах [20,2l] задача построения допустимого расписания решается сведением к задаче нахождения максимального потока в транспортной сети, а в [бв] - средствами математического программирования.
В работе [46І приводится алгоритм построения некоторого подмножества допустимых расписаний в случае, когда требования в систему поступают одновременно и не задано ограничение предшествования требований.
В работах [59,60J рассматривается модель ВС реального времени, представляющая собой систему обслуживания, в которую периодически поступают потоки требований.
Однако вышеперечисленные модели учитывают лишь основной ресурс ВС - время центрального процессора.
В работах [15,34,62-66] рассматриваются более сложные модели, в которых учитываются различные факторы, влияющие на функционирование ЦП.
В работах [І5,34І предлагается модель однопроцессорной ВС реального времени, которая учитывает влияние системы ввода/вывода на работу ЦП.
В работах [62-66І предлагаются алгоритмы планирования, которые учитывают распределение основных ресурсов ВС. Однако в [б2,64,6б] предполагается, что времена обслуживания всех требований одинаковы, в [65І предполагается, что требования в систему поступают одновременно и отсутствует ограничение предшествования требований, а в [бЗ] предлагается лишь метод оценки гарантированного времени ответа системы.
В настоящей работе исследуется математическая модель ВС реального времени, которая учитывает основные ресурсы, подлежащие распределению, такие, как время ЦП, основная память, вспомогательная память и периферийные устройства.
Модель представляет собой одностадийную детерминированную систему обслуживания, состоящую из М ъ А параллельных идентичных приборов. На обслуживание поступает конечный поток S-{^,fc,,..., N\ требований, каждое из которых может обслуживаться на любом приборе, причём одно и то же требование не может обслуживаться одновременно на нескольких приборах, и в любой момент времени каждый прибор обслуживает не более одного требования.
Требование і е S поступает в очередь на обслуживание в момент времени іі >,0 , требует для обслуживания іі > О единиц времени и должно быть обслужено к моменту времени Sc , называемому директивным сроком.
На множестве требований задано отношение частичного порядка, определяющее возможную последовательность обслуживания требований. Предполагается, что разрешены прерывания обслуживания требований, причём на прерывания не расходуется дополнительное время.
Имеется и, видов ресурсов dt - (vi^(Rlv..? (&*.) не-складируемого типа, причём количество ресурсов каждого вида конечно.
Для каждого требования .te S задан вектор потребляемых ресурсов х" - (х\, Ч.І,., ^и. ) Начинать обслуживание требования cg S можно только после того, как выделены все необходимые ресурсы, а после окончания обслуживания этого тре- - ІЗ - бования все выделенные ранее ресурсы освобождаются и могут быть повторно использованы.
Задачи расчёта временных характеристик и оценки необходимого количества ресурсов ВС реального времени сводятся к задаче построения допустимых (относительно директивных сроков, ограничения предшествования требований и ограничения на ресурсы) расписаний для вышеописанной системы обслуживания.
Последняя задача является N 3 -полной в сильном смысле в случае, когда времена обслуживания всех требований равны единице, на множестве требований задано отношение частичного порядка и число приборов М > -і [Зі] .
Основной целью данной работы является исследование свойств вышеописанной математической модели ВС реального времени, исследование случаев, когда задача построения допустимых расписаний разрешима за полиномиальное время и конструирование эффективных алгоритмов построения расписаний работы моделей такого типа.
В первой главе диссертационной работы вводится понятие базиса допустимых расписаний, и предлагаются методы построения базиса допустимых расписаний для одностадийных детерминированных систем обслуживания с одним или несколькими параллельными идентичными приборами.
Показывается, что можно ограничиться рассмотрением только полных систем обслуживания, в которых в любой момент времени каждый из приборов занят обслуживанием некоторого требования, т.е. недопустимы простои приборов.
В случае, когда отсутствуют ограничения на повторно используемые ресурсы, даётся описание методов построения базиса допустимых расписаний для системы обслуживания с одним прибором и несколькими параллельными идентичными приборами при одновременном поступлении требований в систему.
Предлагается способ построения любого допустимого расписания, основанный на использовании методов построения базиса допустимых расписаний, и описывается множество всех допустимых расписаний в вышеуказанных случаях.
Приводятся оценки временной сложности разработанных алгоритмов.
Вторая глава посвящена конструированию различных алгоритмов построения допустимых расписаний для одностадийных детерминированных систем обслуживания при отсутствии ограничений на повторно используемые ресурсы. При этом существенно используются методы построения базиса допустимых расписаний, разработанные в первой главе.
Описывается множество активных расписаний, обладающих тем свойством, что при каждом назначении требования обслуживаются максимальное возможное время, но не больше, чем до момента поступления в систему некоторого требования.
Показывается, что при построении допустимых расписаний для системы обслуживания с одним прибором и ограниченными ресурсами можно рассматривать только активные расписания. Получены верхние оценки числа прерываний обслуживания требований по любому активному расписанию для системы обслуживания с одним прибором и несколькими приборами при одновременном поступлении требований в систему.
Для системы обслуживания с одним прибором получена верхняя оценка числа прерываний обслуживания требований по оптимальному расписанию, в предположении, что критерий оптимальности - минимальное число прерываний обслуживания требований.
Далее предлагается эффективный алгоритм приоритетного планирования для системы обслуживания с одним прибором и несколькими параллельными приборами при одновременном поступлении требований в систему.
Описывается алгоритм метода ветвей и границ построения активного расписания с минимальным числом прерываний обслуживания требований для системы обслуживания с одним прибором.
В конце главы описывается множество всех допустимых расписаний для системы обслуживания с несколькими параллельными приборами при отсутствии ограничения предшествования требований.
В третьей главе алгоритмы построения базиса допустимых расписаний и активных расписаний применяются для решения задач расчёта характеристик и планирования вычислительного 'Процесса при проектировании ВС реального времени.
Предлагается метод определения необходимого быстродействия процессора ВС реального времени. Основу метода составляет алгоритм построения активного расписания для системы обслуживания с одним прибором и ограниченными ресурсами. Этот алгоритм использует метод построения базиса допустимых расписаний, позволяющий существенно совратить перебор вариантов.
Далее описывается метод оценки количества ресурсов ВС, необходимых для управления объектом в реальном времени. Основу этого метода составляет алгоритм построения активного расписания, при котором прерывания обслуживания требований имеют место не чаще, чем в моменты поступления в систему требований, имеющих вложенные директивные интервалы.
В заключении главы приводятся результаты вычислительных экспериментов, которые показали достаточно высокую скорость сходимости алгоритмов построения активных расписаний для систем обслуживания с числом требований около 100.
Результаты вычислительных экспериментов подтвердили, что разработанные в данной работе алгоритмы могут быть использованы при проектировании ВС реального времени для расчёта временных характеристик и характеристик ресурсов ВС.
В данной работе в основном используется терминология, принятая в теории расписаний [9].
Основные результаты диссертационной работы опубликованы в [75-79].
Полные системы обслуживания
Потребности в высоком быстродействии и большом объёме памяти, предъявляемые к современным вычислительным системам (ВС), в настоящее время значительно опережают возможности вычислительной техники. В связи с этим задача разработки методов эффективного использования ресурсов ВС весьма актуальна.
Важное значение эта проблема имеет для ВС, применяемых для управления различными техническими объектами в реальном времени, поскольку к таким системам обычно предъявляются требования высокой надёжности при жёстких ограничениях на использование вычислительных ресурсов.
Поэтому при проектировании ВС реального времени возникает целый ряд задач, связанных с расчётом различных временных характеристик и характеристик основных ресурсов ВС, необходимых для управления объектом в реальном времени. Среди этих задач весьма важными являются расчёт необходимого быстродействия процессора, оценки потребностей в основных ресурсах ВС и построение расписаний выполнения комплекса программ, осуществляющих обработку информации и управление объектом в реальном времени.
В настоящей работе эти задачи рассматриваются главным образом для однопроцессорных ВС реального времени с учётом основных ресурсов ВС таких, как время центрального процессора (ЦП), основная память, вспомогательная память, периферийные устройства.
Вычислительные системы реального времени расчитаны на автоматический приём и обработку информации, поступающей в процессе управления различными техническими объектами, и выдачу управляющей информации непосредственно на исполнительные органы или человеку-оператору. В промышленности такие системы широко применяются с целью автоматизации процессов управления объектов с непрерывным и непрерывно-дискретным характером производства, в первую очередь, на химических, нефтеперерабатывающих, металлургических и бумагоделательных предприятиях. Весьма эффективно ВС реального времени используются для автоматизации различных энергетических объектов, автоматизации исследований, проводимых с помощью сложных экспериментальных установок, и для других целей [і].
Для ВС реального времени важнейшим параметром функционирования системы является время ответа. Как правило, все программы в таких системах должны быть обработаны с учётом временных ограничений на сроки их выполнения, зачастую довольно жёстких, чтобы обеспечить гарантированное время ответа системы. Прекращение измерения времени в этом случае эквивалентно полному отказу системы, т.к. теряется временная связь вычислительного процесса с состоянием источников внешней информации и потребителей вырабатываемых сигналов J2-4J.
Используемые в ВС реального времени управляющие ЭВМ обычно являются наиболее специализированными, т.к. к ЭВМ этого класса предъявляются весьма жёсткие требования по габариту, весу, потребляемой мощности и использованию внешних ресурсов. Поэтому алгоритмы и программы для ЭВМ в ВС реального времени приходится разрабатывать при весьма жёстких требованиях к оптимальности использования ресурсов управляющей ЭВМ [2].
При распределении ресурсов операционной системой зачастую возникает ситуация, когда программы, готовые к решению, не могут быть полностью обеспечены необходимыми ресурсами. В таком случае операционная система реального времени (рСРВ) должна принимать решения относительно порядка обработки очереди для обеспечения наиболее эффективного использования ресурсов ВС и гарантированного времени ответа.
Важным видом ресурсов ВС, подлежащим распределению операционной системой, является так называемый повторно используемый ресурс, или ресурс нескладируемого типа. Ресурс этого типа обладает следующими свойствами: число единиц ресурса постоянно; каждая единица ресурса или доступна или распределена только одному процессу (разделение отсутствует) ; процесс может освободить единицу ресурса (сделать её доступной), только если он ранее получил эту единицу. Примерами ресурсов такого типа являются компоненты аппаратуры, такие, как основная память, вспомогательная память, периферийные устройства и, возможно, процессоры, а также программное обеспечение, такое, как файлы данных и таблицы [б].
Базис допустимых расписаний для системы обслуживания с несколькими параллельными приборами
В настоящее время большинство вычислительных систем реального времени имеют ОСРВ, которые дают возможность работать в режиме мультипрограммирования, позволяющем обрабатывать несколько программ одновременно. Режим мультипрограммирования обеспечивает, в частности, высокую загруженность вычислительных ресурсов и улучшает пропускную способность системы І4,5].
Одной из важных задач, с которой приходится сталкиваться при проектировании ВС реального времени, является задача оптимальной организации вычислительного процесса. Критерий эффективности вычислительного процесса для ВС реального времени должен обеспечивать гарантированное время ответа при минимальных потребляемых ресурсах ВС. Обычно анализ вычислительного процесса, определение его числовых характеристик и проверка различных принципов планирования вычислений проводятся на имитационной модели ВС. Определение правил поведения и параметров отдельных частей имитационной модели, выбор и обоснование принципов планирования основывается на исследовании математических моделей [2-4,6-8]. Реальную ВС или её части представляют в виде стохастической или детерминированной модели массового обслуживания. Далее исследуют эту модель, используя аппарат теории расписаний, теории очередей, комбинаторного анализа, математического программирования. Важным классом моделей планирования вычислительного процесса для ВС реального времени являются детерминированные задачи теории расписаний [2,3,6-8]. Многие задачи теории расписаний, представляющие интерес с точки зрения практики, принадлежат классу N 3 -полных задач [10,11,27,31,35-37,61,64,671. Широко распространена гипотеза, что для решения задач этого класса не существует алгоритмов полиномиальной временной сложности [29-3l]. В работах [2,41,45] предлагаются методы решения таких задач средствами математического программирования и на основе методов ветвей и границ. В работах [І6,І9,47,48,69,70] исследуются частные случаи, когда hiS -полная задача разрешима за полиномиальное время. В последнее время наряду с исследованием сложности детерминированных задач теории расписаний [30,31,67,71-73] большое внимание уделяется построению эффективных приближённых алгоритмов [ЗЗ], в которых за счёт снижения точности решения уменьшается трудоёмкость.
Среди детерминированных задач теории расписаний следует выделить класс задач, которые могут быть использованы при исследовании математических моделей ВС реального времени. Зто прежде всего задачи построения расписаний, не нарушающих директивных сроков обслуживания требований, для одностадийных детерминированных систем обслуживания. Существует большое число работ, посвященных исследованию такого рода задач [9-27,40-54]. В системах этого типа множество требований о -{4,&,..., N обслуживается М , 4 параллельными приборами, которые обычно считаются идентичными [17,18,27,32,43,46,50-56], но могут быть и различными [і6,49J Требование Le S поступает в очередь на обслуживание в момент времени Ъс і и длительность его обслуживания равна Zi . Обычно предполагается также заданным директивный срок Jt обслуживания требования, т.е. момент времени, к которому обслуживание этого требования должно быть завершено. На множестве требований может быть задано отношение частичного порядка, которое определяет возможную последовательность обслуживания требований. В самом общем случае последовательность обслуживания требований определяется направленным ациклическим графом [l4,15,28,48,54,56J, в других случаях эта последовательность задается параллельно-последовательной сетью, совокупностью деревьев или деревом [22,55,57, 58].
Обычно рассматривают две дисциплины обслуживания требований: обслуживание с прерываниями [13-18,20,21,23,24,26,32, 41-43,46,49,52,53] и без прерываний [12,14-16,19,22,27,28, 44,45,47-48,50,51,55-58]. При обслуживании требований с прерываниями обычно предполагается, что каждое требование одновременно может обслуживаться лишь одним прибором, причём на прерывания не расходуется дополнительное время.
Верхняя оценка числа прерываний в оптимальном расписании
В некоторых работах допускается возможность обслуживания требования одновременно несколькими приборами [І6-І8І. Качество расписания обычно оценивается значением некоторой функции, аргументами которой являются моменты завершения обслуживания требований. Значение функции в этом случае представляет собой штраф за обслуживание требований, а расписание, которому соответствует наименьшее значение функции, называется оптимальным. Обычно рассматриваются критерии качества расписания, при которых минимизируются следующие величины [9-11,15,18,22, 24-27,40,46-48,50-51,55-58]: - общее время обслуживания требований; - сумма (или среднее значение) моментов окончания обслуживания требований; - взвешенная сумма моментов окончания обслуживания требований; - взвешенная сумма величин, экспоненциально зависящих от моментов окончания обслуживания требований; - сумма запаздываний в обслуживании требований; - взвешенная сумма запаздываний; - число запаздывающих требований; - взвешенное число запаздывающих требований.
Как отмечалось выше, при исследовании математических моделей ВС реального времени особый интерес представляет задача построения расписаний, не нарушающих директивных сроков. Эта задача для системы обслуживания с одним прибором рассматривается в работах [9-16,20-22,24-27,40,41,44-48,51, 53,54]. При обслуживании требований с прерываниями известны различные необходимые и достаточные условия существования допустимых (не нарушающих директивных сроков и ограничения предшествования требований ) расписаний [J4-I6,20,21,26,46,53] и различные алгоритмы построения допустимых расписаний [9-II, 14-16,20,21,23,24,26,41,46]. В работах [20,24,46] получена верхняя оценка числа прерываний обслуживания требований по оптимальному расписанию, в предположении, что критерий оптимальности - минимальное число прерываний обслуживания требований. В этих работах предлагаются алгоритмы построения допустимого расписания, при котором прерывания обслуживания требований имеют место не чаще, чем в моменты поступления требований в систему. В случае, когда прерывания обслуживания требований запрещены, задача построения допустимого расписания является /V о -полной в сильном смысле [ЗІ,72,73І.
В работах [12,41,45] предлагаются точные решения задачи построения допустимого расписания без прерываний обслуживания требований средствами математического программирования и методом ветвей и границ. Исследованию частных случаев, когда задача разрешима за полиномиальное время, посвящены работы [16,19,47,48,69,70]. В работе [44] определяются характеристики множества всех допустимых расписаний.
Задача построения допустимых расписаний для системы обслуживания с несколькими параллельными приборами рассматривается в работах [9-11,15,20-21,23,25,27,40,42,43,46,49-54]. В случае, когда разрешены прерывания обслуживания требований и не задано ограничение предшествования требований, известны необходимые и достаточные условия существования допустимых расписаний [20,21,46І. В работах [20,2l] задача построения допустимого расписания решается сведением к задаче нахождения максимального потока в транспортной сети, а в [бв] - средствами математического программирования. В работе [46І приводится алгоритм построения некоторого подмножества допустимых расписаний в случае, когда требования в систему поступают одновременно и не задано ограничение предшествования требований. В работах [59,60J рассматривается модель ВС реального времени, представляющая собой систему обслуживания, в которую периодически поступают потоки требований. Однако вышеперечисленные модели учитывают лишь основной ресурс ВС - время центрального процессора. В работах [15,34,62-66] рассматриваются более сложные модели, в которых учитываются различные факторы, влияющие на функционирование ЦП. В работах [І5,34І предлагается модель однопроцессорной ВС реального времени, которая учитывает влияние системы ввода/вывода на работу ЦП. В работах [62-66І предлагаются алгоритмы планирования, которые учитывают распределение основных ресурсов ВС. Однако в [б2,64,6б] предполагается, что времена обслуживания всех требований одинаковы, в [65І предполагается, что требования в систему поступают одновременно и отсутствует ограничение предшествования требований, а в [бЗ] предлагается лишь метод оценки гарантированного времени ответа системы.
В настоящей работе исследуется математическая модель ВС реального времени, которая учитывает основные ресурсы, подлежащие распределению, такие, как время ЦП, основная память, вспомогательная память и периферийные устройства.
Расчёт быстродействия процессора вычислительной системы реального времени
Модель представляет собой одностадийную детерминированную систему обслуживания, состоящую из М ъ А параллельных идентичных приборов. На обслуживание поступает конечный поток S-{ ,fc,,..., N\ требований, каждое из которых может обслуживаться на любом приборе, причём одно и то же требование не может обслуживаться одновременно на нескольких приборах, и в любой момент времени каждый прибор обслуживает не более одного требования.
Требование і е S поступает в очередь на обслуживание в момент времени іі ,0 , требует для обслуживания іі О единиц времени и должно быть обслужено к моменту времени Sc , называемому директивным сроком. На множестве требований задано отношение частичного порядка, определяющее возможную последовательность обслуживания требований. Предполагается, что разрешены прерывания обслуживания требований, причём на прерывания не расходуется дополнительное время. Имеется и, видов ресурсов dt - (vi (Rlv..? (& .) не-складируемого типа, причём количество ресурсов каждого вида конечно. Для каждого требования .te S задан вектор потребляемых ресурсов х" - (х\, Ч.І,., и. ) Начинать обслуживание требования CG S можно только после того, как выделены все необходимые ресурсы, а после окончания обслуживания этого тре - ІЗ бования все выделенные ранее ресурсы освобождаются и могут быть повторно использованы. Задачи расчёта временных характеристик и оценки необходимого количества ресурсов ВС реального времени сводятся к задаче построения допустимых (относительно директивных сроков, ограничения предшествования требований и ограничения на ресурсы) расписаний для вышеописанной системы обслуживания. Последняя задача является N 3 -полной в сильном смысле в случае, когда времена обслуживания всех требований равны единице, на множестве требований задано отношение частичного порядка и число приборов М -і [Зі] . Основной целью данной работы является исследование свойств вышеописанной математической модели ВС реального времени, исследование случаев, когда задача построения допустимых расписаний разрешима за полиномиальное время и конструирование эффективных алгоритмов построения расписаний работы моделей такого типа. В первой главе диссертационной работы вводится понятие базиса допустимых расписаний, и предлагаются методы построения базиса допустимых расписаний для одностадийных детерминированных систем обслуживания с одним или несколькими параллельными идентичными приборами. Показывается, что можно ограничиться рассмотрением только полных систем обслуживания, в которых в любой момент времени каждый из приборов занят обслуживанием некоторого требования, т.е. недопустимы простои приборов.
В случае, когда отсутствуют ограничения на повторно используемые ресурсы, даётся описание методов построения базиса допустимых расписаний для системы обслуживания с одним прибором и несколькими параллельными идентичными приборами при одновременном поступлении требований в систему.
Предлагается способ построения любого допустимого расписания, основанный на использовании методов построения базиса допустимых расписаний, и описывается множество всех допустимых расписаний в вышеуказанных случаях. Приводятся оценки временной сложности разработанных алгоритмов. Вторая глава посвящена конструированию различных алгоритмов построения допустимых расписаний для одностадийных детерминированных систем обслуживания при отсутствии ограничений на повторно используемые ресурсы. При этом существенно используются методы построения базиса допустимых расписаний, разработанные в первой главе.
Описывается множество активных расписаний, обладающих тем свойством, что при каждом назначении требования обслуживаются максимальное возможное время, но не больше, чем до момента поступления в систему некоторого требования.
Показывается, что при построении допустимых расписаний для системы обслуживания с одним прибором и ограниченными ресурсами можно рассматривать только активные расписания. Получены верхние оценки числа прерываний обслуживания требований по любому активному расписанию для системы обслуживания с одним прибором и несколькими приборами при одновременном поступлении требований в систему.
Для системы обслуживания с одним прибором получена верхняя оценка числа прерываний обслуживания требований по оптимальному расписанию, в предположении, что критерий оптимальности - минимальное число прерываний обслуживания требований. Далее предлагается эффективный алгоритм приоритетного планирования для системы обслуживания с одним прибором и несколькими параллельными приборами при одновременном поступлении требований в систему. Описывается алгоритм метода ветвей и границ построения активного расписания с минимальным числом прерываний обслуживания требований для системы обслуживания с одним прибором. В конце главы описывается множество всех допустимых расписаний для системы обслуживания с несколькими параллельными приборами при отсутствии ограничения предшествования требований. В третьей главе алгоритмы построения базиса допустимых расписаний и активных расписаний применяются для решения задач расчёта характеристик и планирования вычислительного Процесса при проектировании ВС реального времени. Предлагается метод определения необходимого быстродействия процессора ВС реального времени. Основу метода составляет алгоритм построения активного расписания для системы обслуживания с одним прибором и ограниченными ресурсами. Этот алгоритм использует метод построения базиса допустимых расписаний, позволяющий существенно совратить перебор вариантов.
Далее описывается метод оценки количества ресурсов ВС, необходимых для управления объектом в реальном времени. Основу этого метода составляет алгоритм построения активного расписания, при котором прерывания обслуживания требований имеют место не чаще, чем в моменты поступления в систему требований, имеющих вложенные директивные интервалы.
В заключении главы приводятся результаты вычислительных экспериментов, которые показали достаточно высокую скорость сходимости алгоритмов построения активных расписаний для систем обслуживания с числом требований около 100. Результаты вычислительных экспериментов подтвердили, что разработанные в данной работе алгоритмы могут быть использованы при проектировании ВС реального времени для расчёта временных характеристик и характеристик ресурсов ВС.
Похожие диссертации на Детерминированные задачи планирования для вычислительных систем реального времени с ограниченными ресурсами
