Содержание к диссертации
Введение
1 Способы планирования задач реального времени в системах автоматизации и управления 10
1.1 Особенности систем автоматизации и управления 10
1.2 Характеристики и структура входных информационных потоков в системах автоматизации и управления 11
1.3 Анализ современных технологий планирования потока задач 17
1.4 Основные результаты 24
2 Способ планирования апериодических задач реального времени, обеспечивающий адаптацию параметров планирования к состоянию потока запросов апериодических задач 25
2.1 Применение опрашивающего сервера в системах планирования апериодических запросов задач реального времени 25
2.2 Способ планирования апериодических задач реального времени на основе применения опрашивающего сервера 26
2.3 Основные результаты 31
3 Алгоритм оценки состояния потока запросов апериодических задач на основе его нечетких параметров 33
3.1 Основные понятия и определения ТНМ 33
3.2 Задание нечетких переменных, характеризующих состояние входного потока 36
3.2.1 Элементарные нечеткие переменные 36
3.2.2 Понятие р-подобия на основе использования свойств схожести функций распределения и функций принадлежности 39
3.2.3 Разработка методики экспертной оценки параметров входного потока 42
3.3 Алгоритм оценки состояния входного потока с использованием сложных нечетких переменных 44
3.4 Основные результаты 48
4 Разработка имитационной модели системы планирования апериодических задач реального времени 49
4.1 Описание концептуальной модели 49
4.2 Алгоритм вычисления значений Ее по оценкам сложных нечетких переменных 53
4.3 Понятие уровня а-принадлежности 54
4.4 Переменные и ограничения задач РВ, вводимые при моделировании 55
4.5 Формирование входного потока апериодических запросов 57
4.5.1 Формирование случайного потока апериодических запросов с нормальным законом распределения длин и количеством запросов 59
4.5.2 Формирование случайного потока апериодических запросов с экспоненциальным законом распределения длин и равномерным законом распределения количества запросов 62
4.5.3 Изменение входного потока апериодических запросов 64
4.6 Экспертная оценка характеристик входного потока 64
4.7 Формирование суждения о входном потоке апериодических запросов 66
4.8 Реализация обслуживания запросов сервером в имитационной модели 68
4.9 Работа модели 68
4.10 Основные результаты 71
5 Экспериментальные исследования моделей системы планирования апериодических задач реального времени 73
5.1 Влияние ограничений входных параметров на результаты работы модели системы 75
5.2 Исследование зависимости эффективности от уровня сложности нечетких правил 79
5.3 Модели входного потока апериодических запросов и их влияние на значение эффективности 81
5.3.1 Первая модель входного потока, 81
5.3.2 Ограничения параметров первой модели входного потока 82
5.3.3 Вторая модель входного потока 83
5.3.4 Ограничения параметров второй модели входного потока 83
5.4 Исследование зависимости эффективности от усреднения текущих значений элементарных нечетких переменных 85
5.5 Влияние параметров законов распределения характеристик входного потока апериодических запросов на значение эффективности 86
5.6 Заключение по работе модели, основанной на ТНМ 87
5.7 Применение алгоритма оценки состояния входного потока на основе нечеткой логики в системах автоматизации и управления 89
5.8 Комбинированный способ планирования апериодических задач реального времени 92
5.9 Основные результаты 96
Заключение 98
Список литературы 100
Приложения 108
- Особенности систем автоматизации и управления
- Применение опрашивающего сервера в системах планирования апериодических запросов задач реального времени
- Задание нечетких переменных, характеризующих состояние входного потока
- Алгоритм вычисления значений Ее по оценкам сложных нечетких переменных
Введение к работе
В современных системах автоматизации и управления их вычислительные ресурсы обрабатывают сложные и интенсивные потоки запросов задач управления и контроля в условиях ограничений реального времени (РВ) и мощности вычислительных средств. При этом необходимо планировать процессы обработки запросов, исходя из параметров задач и ограничений, накладываемых на эти задачи. Планирование обеспечивает распределение процессорного времени при выполнении совокупного множества задач с различными параметрами в течение функционирования системы. При неэффективном планировании задач РВ снижается эффективность и качество функционирования системы: возрастают задержки, предъявляются повышенные требования к быстродействию вычислительных средств и пр. Поэтому разработка способов планирования задач РВ в системах автоматизации и управления представляет собой актуальную проблему.
На сегодняшний день существуют различные подходы к планированию задач РВ. Наиболее успешно планирование осуществляется в отношении детерминированных задач, характеризующихся детерминированными параметрами, что позволяет провести точное распределение последовательности их выполнения с учетом ограничений РВ. Исследованиям в области планирования детерминированных задач с различными видами ограничений посвящены известные работы таких авторов, как G. Fohler, А.К. Мок, A. Burns, С. Сорокин, Н. Бусленко и др. [1,2].
Вместе с тем среди задач, подлежащих выполнению прежде всего в контурах управления и контроля автоматизированных систем управления технологическими процессами, систем автоматизации испытаний сложными объектами, информационно-управляющих систем, значительную долю составляют апериодические задачи, характеризующиеся неопределенностью основных параметров (время поступления запроса, объем процессорного времени, требуемого для его выполнения и т.д.). Планирование апериодических задач РВ является сложной проблемой. Неопределенность параметров этих задач делает неэффективными алгоритмы, используемые при планировании детерминированных задач. Применение вероятностных подходов к планированию апериодических задач РВ, нашедшее изложение в работах таких авторов, как В.М. Лохин, И.М. Макаров, СВ. Манько, М.П. Романов, Р. Дорф, Р. Бишоп, Ч. Филипс, Р. Харбор, ограничивается некоторыми целевыми классами апериодических задач и отличается повышенной затратностью вреализации алгоритмов, что ведет к снижению эффективности функционирования систем [3,4, 5].
Проведенный анализ показал, что рациональные подходы кпланированию апериодических задач РВ лежат в области осуществления планирования на основе использования нечетких моделей потока запросов,позволяющих получить оценки текущего состояния потока с применением нечеткой логики. Известные примеры использования аппарата нечеткой логики в системах управления показывают его широкие возможности. Вместе с тем применение методов нечеткой логики в решении проблем достижения эффективного планирования апериодических задач РВ не нашло должного развития.
Таким образом, разработка способов и алгоритмов планирования апериодических задач РВ, основанных на методах нечеткой логики и обеспечивающих повышение эффективности функционирования систем автоматизации и управления за счет снижения требований к быстродействию вычислительных средств и снижения потерь в использовании вычислительных ресурсов, является актуальной.
Цель работы
Целью работы является повышение качества планирования апериодических задач РВ и эффективности систем автоматизации и управления в условиях нечетких параметров апериодических потоков. Научная задача
В работе решается важная научная задача, которая включает в себя разработку способов и алгоритмов планирования апериодических задач реального времени на основе нечетких моделей потока апериодических задач.
Указанная научная задача предполагает решение следующих частных задач:
- разработка способа планирования апериодических задач реального времени, обеспечивающего адаптацию параметров планирования к состоянию потока апериодических задач, характеризующегося нечеткостью параметров;
- создание основ теории р-подобия, устанавливающей отношения подобия функций принадлежности и функций распределения величин, оценивающих параметры потока апериодических задач;
- создание алгоритма оценки состояния потока апериодических запросов на основе его нечетких параметров;
- разработка и исследование имитационной модели системы планирования, реализующей планирование апериодических задач на основе предложенного способа с адаптацией параметров планирования к состоянию потока запросов, характеризующегося нечеткими параметрами.
Методы исследования
В работе использован математический аппарат теории вероятностей, теории нечетких множеств и математического моделирования динамических процессов на ЭВМ с применением численных методов.
Научная новизна
- предложен новый способ планирования апериодических задач реального времени, основанный на применении теории нечетких множеств к формированию параметров планирования на основе нечеткой модели оценки состояния потока;
- разработан новый алгоритм оценки состояния потока апериодических запросов, реализуемый с применением нового понятия р-подобия функций принадлежности и распределения величин, оценивающих нечеткие параметры потока;
- разработан новый алгоритм определения параметров системы планирования, основанный на применении теории нечетких множеств;
- предложена и исследована имитационная модель системы планирования, новизну которой составляет использование алгоритма оценки состояния входного потока апериодических запросов на основе его нечетких параметров.
Практическая ценность работы состоит в разработке и реализации способа планирования апериодических задач РВ, обеспечивающего повышение эффективности систем автоматизации и управления за счет увеличения эффективности использования вычислительных ресурсов и уменьшения затрат на аппаратурное обеспечение.
Предложенный способ планирования и составляющие его основу алгоритмы оценки состояния потока апериодических задач и определения параметров системы планирования целесообразно применять при разработке аппаратно-программного обеспечения систем автоматизации и управления.
Алгоритмы и прикладные программы, их реализующие, использовались при создании программного обеспечения системы автоматизации испытаний сложных объектов в ОАО «СТАР».
Теоретические результаты, полученные в работе, внедрены в учебный процесс и использованы в содержании учебных дисциплин по специальности 220201 «Управление и информатика в технических системах» Пермского государственного технического университета. Апробация работы
Основные результаты диссертационной работы докладывались и получили положительную оценку на международном научно-образовательном семинаре «Современная миссия технических университетов в развитии инновационных территорий» (Варна, 2004), научно-техническом форуме с международным участием «Высокие технологии 2004» (Ижевск, 2004), третьей
Всероссийской конференции «Необратимые процессы в природе и технике» (Москва, 2005), IV международной конференции «Идентификация систем и задачи управления» SICPRO 05 (Москва, 2005).
Публикации
Основные положения и результаты диссертации опубликованы в 9 печатных работах (в том числе 2 статьи в изданиях, указанных в Перечне ВАК).
Основные положения, выносимые на защиту:
- подход к планированию апериодических задач РВ, основанный на применении нечетких моделей оценки состояния потока апериодических запросов;
- алгоритм оценки состояния потока запросов апериодических задач РВ с нечетко определенными параметрами;
- алгоритм определения параметров системы планирования, основанный на применении теории нечетких множеств;
- результаты имитационного моделирования системы планирования апериодических задач РВ и их оценка, подтверждающая достоверность научных результатов;
- комбинированный подход к планированию апериодических задач РВ, основанный на применении нечетких и вероятностно-статистических моделей оценки состояния потока апериодических запросов. Объем работы
Диссертация содержит 107 страниц основного текста, 31 рисунок, список литературы из 75 наименований, приложения и состоит из введения, 5 глав и заключения.
Достоверность полученных в работе научных положений и выводов обеспечивается результатами имитационного моделирования и данными экспериментальных исследований, а также корректным применением математического аппарата теории вероятностей и нечетких множеств.
Особенности систем автоматизации и управления
В различных отраслях науки и техники находят широкое применение информационно-управляющие системы (ИУС), выполняющие функции сбора, преобразования, передачи, обработки первичной информации от объектов. ИУС составляют ядро автоматизированных систем управления технологическими процессами и используются в автоматизированных системах научных исследований, стендах автоматизированных испытаний ракетных двигателей, электронной аппаратуры и пр. Сложность и быстродействие объектов автоматизации постоянно возрастает. Это влечет за собой увеличение количества измерительных и управляющих каналов и требует повышения быстродействия ИУС.
Для обеспечения эффективного функционирования рассматриваемых систем в условиях конечного быстродействия устройства обработки информации (УО) и ограниченной полосы пропускания каналов связи (КС) разработаны и широко применяются различные алгоритмы сбора, преобразования и обработки входных сигналов [6, 7]. Указанные алгоритмы реализуются в подсистемах сбора информации (ПСИ) и подсистемах преобразования и передачи информации (ПЛИ), входящих в ИУС.
Для большинства ИУС характерным является то, что входные информационные потоки являются асинхронными как по отношению друг к другу, так и по отношению к УО.
Применение современных информационно-измерительных систем (ИИС) для решения задач измерения и управления сложными динамическими объектами требует выполнения функций по управлению информационными потоками, процессами преобразования, переработки, хранения и представления информации: сбор информации от большого числа разнотипных источников; управление быстродействующими устройствами ввода-вывода и накопителями информации для формирования сообщений с целью передачи по каналам связи; t» преобразование и обработка информации; дешифрация, вторичная обработка и регистрация информации.
В числе задач, которые решают системы, выполняя указанные функции, задачи обработки информации, поступающей от источников, выделяются своей сложностью. Эффективная реализация указанных задач представляется значительной проблемой, прежде всего в связи с резко возросшими характеристиками и усложнением структуры входных потоков информации.
Существенным фактором, определяющим качество информационно-управляющей системы, являются требования, обусловленные особенностями функционирования в режиме реального времени (РВ). Режим реального времени, характерный для современных информационно-управляющих систем, предполагает жесткое лимитирование времени отклика (ответа) на запрос от объекта. Отсюда при построении информационно-управляющих систем, работающих в режиме реального времени требуется: во-первых, обеспечить минимальное время отклика, а во-вторых, обеспечить высокую эффективность использования вычислительных мощностей. Проектировщики, стремясь обеспечить выполнение основных функций и в том числе задач сбора и обработки информации, поступающей от источников, при ограничениях жесткого реального времени (ЖРВ), вынуждены закладывать значительную избыточность прежде всего по быстродействию. Однако избыточность по быстродействию не позволяет достичь высокой эффективности использования вычислительного ресурса систем.
Входные информационные потоки в ИУС представляют собой последовательности требований, формируемых источниками информации.
В современных информационно-управляющих системах входные информационные потоки характеризуются (рис. 1.1): значительным числом источников измеряемых параметров N, от нескольких десятков до 15000 и более [7]; высокой суммарной интенсивностью X, достигающей нескольких сотен тысяч отсчетов (сообщений) в секунду; повышенными требованиями к точности преобразования измерительной информации.
Применение опрашивающего сервера в системах планирования апериодических запросов задач реального времени
Предлагаемый способ основывается на идее сервера управления (The Control Server), предложенного в работе A. Cervin и J. Eker [23], (в дальнейшем для краткости он указывается просто как «сервер»). В данном случае под сервером понимается алгоритм, который обеспечивает для задачи РВ определенную долю в процессорном времени за счет того, что на каждом периоде Г для выполнения запросов этой задачи выделяется время, не меньшее чем EQ [24, 25]. Такой подход позволяет выделить долю процессорного времени для задач жесткого РВ, обеспечив соблюдение их ограничений РВ, а оставшееся процессорное время разделить в необходимых пропорциях между апериодическими запросами. При этом проблему планирования апериодических задач можно свести к определению доли процессорного времени, отводимой для каждой такой задачи, то есть к выбору параметра Ес для сервера (при заданном периоде Т). Если запросов нет, то сервер ожидает окончания отведенного ему времени выполнения. Серверу присваивается наибольший приоритет и задается небольшой период.
Недостатком опрашивающего сервера является то, что при отсутствии запросов он просто расходует процессорное время. Для устранения этого недостатка были разработаны различные виды модификации опрашивающего сервера. Суть модификаций заключается в том, что при отсутствии запросов сервер прекращает свою работу и освобождает процессор для задач жесткого реального времени, накапливая незатраченное время. В дальнейшем это накопленное время может быть использовано для выполнения последующих апериодических запросов.
Так, были разработаны: - задерживаемый сервер (Deferrable Server); - сервер обмена приоритетов (Priority Exchange Server); - спорадический сервер (Sporadic Server); - сервер расширенного обмена приоритетов (Extended Priority Exchange Server) [26].
Различные версии серверов отличаются разными способами накопления и освобождения незатраченного времени. Отметим, что модификации опрашивающего сервера характеризуются существенным усложнением алгоритма и увеличением времени реализации.
Основной характеристикой является загрузка сервера апериодическими запросами, причем для эффективной работы системы в целом она (загрузка) должна стремиться к 100 %. Таким образом, общая загрузка системы будет складываться из загрузки системы периодическими задачами РВ и загрузки системы сервером. При этом загрузка системы периодическими задачами РВ может быть обеспечена постоянной и достигающей 100 %. Отсюда с целью обеспечения большей эффективности системы в целом следует стремиться к максимальной загрузке сервера. Поскольку параметры потока апериодических запросов характеризуются неизвестностью (нечеткостью), то заранее точно определить значение размера сервера, обеспечивающее 100 %-ную загрузку невозможно.
В связи с вышеизложенным можно сформулировать следующую проблему. Имеется однопроцессорная вычислительная система, на которой выполняются задачи жесткого РВ и апериодические задачи. Применяется модель планирования со следующими допущениями: 1) для каждой апериодической задачи ось времени делится на интервалы времени равной длины Т, при этом апериодический запрос, появившийся на интервале, либо выполняется в течение этого интервала (обрабатывается), либо отбрасывается как необработанный (как вариант передается на другое вычислительное устройство); 2) ограничение РВ для каждой апериодической задачи определяется допустимым процентом необработанных запросов (паоп). Собственно проблема состоит в минимизации параметра Ее для сервера при соблюдении ограничения п птп, где п - процент необработанных запросов за заданное количество интервалов Т. В дальнейшем для упрощения параметр Ее называется «размером сервера». Очевидно, что минимизация размера сервера позволяет больший процент процессорного времени выделить для других апериодических задач, тем самым повышая эффективность использования вычислительного ресурса.
Для удобства представления количественных показателей при решении данной проблемы вводится следующее понятие эффективности. На этапе проектирования возможно определить максимальные значения (на интервале 7) параметров количества и длины запросов апериодических задач, обозначаемых Nmax и Lmax соответственно, что позволяет на основе использования ДеТерМИНИрОВаННОГО ПОДХОДа ОЦеНИТЬ Предельное Значение cmax=-Nmax max5 позволяющее обрабатывать все апериодические запросы [1, 2]. Однако при таком подходе для Ni Nmax и ,у тах (гДе N{, Ljj - соответственно 7=1 количество запросов на /-м интервале и длина у -го запроса на этом интервале) часть выделенного интервала стах остается неиспользованной, что ведет к простоям процессора и снижению эффективности системы. Эффективность Э, р работы системы на /-м интервале определяется отношением Э(- =1 —. В Crnax целом эффективность работы Э определяется как среднее по всем Э, на рассматриваемом интервале работы системы. При этом Э позволяет оценить объем времени, затраченного на работу сервера, по отношению к ЕСтах, то есть О Э 1. Тем самым сформулированная проблема сводится к максимизации Э. Параметр Э удобно отражает соотношение рассматриваемого подхода с детерминированным подходом.
Задание нечетких переменных, характеризующих состояние входного потока
Результаты, полученные методами ТНМ, в значительной степени зависят от выбора функции принадлежности нечетко заданных параметров входного потока системы. На практике требуется упорядочение элементов конечного нечеткого множества по предпочтениям. С целью упрощения процедуры формирования экспертного суждения в работе предлагается использование нового понятия - р-подобия в ТНМ.
Понятие р-подобия основано на подобии (схожести) функций распределения и принадлежности [71].
Пусть и = {ах,а2,...,ап} - универсальное упорядоченное множество с числовыми элементами. Рассмотрим некоторую функцию принадлежности \iA, и пусть A = l\iA(bi)/bl,\iA(b2)/b2,...,\iA(bm)/bm) - нечеткое множество, где bt є U.
Пусть F(x) функция распределения (ФР) F(x) = P(X x), где X -случайная величина, значениями которой могут быть элементы множества U. Без ограничений общности будем предполагать, что F(x) = 0, х 0 (или же значения F(x) не превышает некоторого «малого» значения) [72]. Определение. Назовем функцию принадлежности \iA р-подобной F, если из \1А \iAj = Pi Pj, где Pi =F(bi).
Проиллюстрируем смысл понятия р-подобия на следующем примере. Пусть U - базовое множество {1,2,3,4,5} и, соответственно, А - некоторое нечеткое множество {0,1/1; 0,7/2; 1/3}, где 0,1;0,7;1 ц4 - соответствующие значения функции принадлежности элементов 1;2;3-6,.. Представим F(x) и функцию принадлежности \хА{х) в одной системе координат (рис. 3.3).
Пусть F(x) - некоторая монотонная функция. ФП - функция принадлежности, определяется некоторой монотонной функцией [ІА{Х). Из взаиморасположения функций можно говорить о их одинаковом поведении на некотором выделенном участке [хг,хй\.
Для равновероятного закона распределения в промежутке [х , /,] появление значений х,- случайной величины х равновероятно. Для достижения р-подобия \iA(x) F(x) необходимо подобрать ее значения в пределах [xg,xh], где функция распределения возрастает.
При этом существует достаточно много различных функций принадлежности, удовлетворяющих заданному условию. Для случая равномерного распределения ФП р-подобна ФР, если ФП определена на [xg,xf,] и при xg xk следует, что iiA(xg) )xA{xh) (рис. 3.4). В случае показательного распределения график функции принадлежности также проходит через некоторую точку а,- (рис. 3.6). В случае показательного распределения график функции принадлежности также проходит через некоторую точку at (рис. 3.6). Таким образом, можно выделить критерии р-подобия: 1) прохождение ФП влизи а, = т[х], т.е. цл(а,) = т(х)±38; 2) нахождение в диапазоне параметра х такого, что 0 F(x) 0,95; 3) если F(xg) F(xh),TO \ІА(Х.) \ІА(Х„). Если реально функция распределения неизвестна, а имеется только предполагаемая функция принадлежности, то возможна обратная оценка.
Таким образом, введение понятия р-подобия позволяет упорядочить совокупность конечных нечетких элементов с точки зрения реальных систем, тем самым проводить описание нечетких параметров, учитывая при этом наиболее вероятные числовые значения и соответствующие им значения ФП -ц,(х),0 М ) 1.
Применение понятия р-подобия осуществляется на этапе формирования мнения эксперта о состоянии входного потока, при составлении функций принадлежности нечетких множеств для его описания и при необходимости определения конечного значения параметра сервера из множества возможных. Экспертная оценка подразумевает построение функций принадлежностей нечетко заданных параметров [73, 74].
Эксперт моделирует интервальную неопределенность. Эксперт может сказать, что значение некоторой величины Zneed будет не больше Zmax, но не меньше Zmin (рис. 3.7).
Алгоритм вычисления значений Ее по оценкам сложных нечетких переменных
Имитационная модель системы планирования обеспечивает потактное моделирование процесса вычисления значений параметра адаптации Ее на основе оценки состояния потока апериодических запросов на предыдущих периодах длиной Т. Поток апериодических запросов формируется генератором псевдослучайной последовательности запросов с заданными законами распределения параметров Ц, Nh Ц.
Система отслеживает формирование входного потока на протяжении нескольких периодов и затем выдает рекомендации по изменению управляемой величины - Ее Таким образом, оценивая состояние входного потока на протяжении нескольких предыдущих периодов, система предполагает дальнейшее его состояние и рекомендует изменение управляемой величины.
Содержание вычислительных операций при работе модели составляет выполнение алгоритма оценки состояния потока запросов и алгоритма вычисления прогнозируемого значения Ес.
На вход системы поступает некоторый сложный поток заявок, требующих обслуживания, в состав которых входят задачи апериодического типа. Необходимо определить, какими размерами параметров (временем выполнения Ес и периодом Тс) должен обладать сервер (идея серверного подхода описана в главе 2), чтобы не нарушить имеющихся в системе ограничений и повысить эффективность ее работы.
Для определения предельного времени выполнения всех апериодических запросов на гиперпериоде необходимо определить максимальный размер сервера, выделяемого на обслуживание апериодических запросов.
Для этого рассматривается крайний (максимально не благоприятный) случай, когда апериодических запросов максимум (много) - N и они требуют максимум времени на выполнение (длинные) - ЕАш. Поскольку наилучшей системой будет та, которая обслужит все запросы, поэтому сервер, выделяемый на обслуживание апериодических запросов, будет иметь максимальное время на выполнение Ес =КЛ -ЕА . Пусть Тс=ТЖі=Тж = Я,тогда Н-ЕС=ЕЖ.
Для минимизации задержки при выполнении апериодических запросов т необходимо, чтобы сервер имел наивысший приоритет, то есть будет прерывание задач ЖРВ задачами апериодическими. В главе 1 подробно описывалось, что назначение апериодическим запросам наивысшего приоритета, по отношению к запросам ЖРВ, при обработке сложного входного потока запросов позволит сделать задержки при выполнении апериодических запросов минимальными, а следовательно, эффективность работы системы в целом будет высокой.
Из всего вышеизложенного можно сделать вывод, что общая загрузка системы будет меньше 100 % (U06 100 %) во всех случаях, когда NA NAna и Ел Ел л лтач Н = Еж + Ес. Существует следующая зависимость загрузки системы апериодическими запросами от уже указанных параметров: ис = NA EA -100 %. Еж+Ес Следовательно, загрузка сервера апериодическими запросами определяется согласно N L = оД.+л VA,.p+NAdi Nm„, (4.2) = 7 -100%. Необходимо, чтобы загрузка UA стремилась к 100 %, тогда система будет работать эффективно.