Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени
Изучается производительность распределенных мягких систем реального времени, которые используют стандартные компоненты с различными алгоритмами планирования и предлагаются пути их улучшения. Вивчається продуктивність розподілених м’яких систем реального часу, які використовують стандартні компоненти...
Gespeichert in:
| Veröffentlicht in: | Комп’ютерні засоби, мережі та системи |
|---|---|
| Datum: | 2012 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46483 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени / С.В. Зинченко // Комп’ютерні засоби, мережі та системи. — 2012. — № 11. — С. 13-22. — Бібліогр.: 19 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-46483 |
|---|---|
| record_format |
dspace |
| spelling |
Зинченко, С.В. 2013-06-30T11:18:19Z 2013-06-30T11:18:19Z 2012 Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени / С.В. Зинченко // Комп’ютерні засоби, мережі та системи. — 2012. — № 11. — С. 13-22. — Бібліогр.: 19 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/46483 681.3 Изучается производительность распределенных мягких систем реального времени, которые используют стандартные компоненты с различными алгоритмами планирования и предлагаются пути их улучшения. Вивчається продуктивність розподілених м’яких систем реального часу, які використовують стандартні компоненти з різними алгоритмами планування і пропонуються шляхи їх покращення. This paper studies the performance of distributed soft real-time systems that use standard components with various scheduling algorithms and ways to improve them. ru Інститут кібернетики ім. В.М. Глушкова НАН України Комп’ютерні засоби, мережі та системи Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени Research of performance of knowledge oriented intellectual soft real-time systems Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени |
| spellingShingle |
Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени Зинченко, С.В. |
| title_short |
Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени |
| title_full |
Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени |
| title_fullStr |
Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени |
| title_full_unstemmed |
Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени |
| title_sort |
исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени |
| author |
Зинченко, С.В. |
| author_facet |
Зинченко, С.В. |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Комп’ютерні засоби, мережі та системи |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Research of performance of knowledge oriented intellectual soft real-time systems |
| description |
Изучается производительность распределенных мягких систем реального времени, которые используют стандартные компоненты с различными алгоритмами планирования и предлагаются пути их улучшения.
Вивчається продуктивність розподілених м’яких систем реального часу, які використовують стандартні компоненти з різними алгоритмами планування і пропонуються шляхи їх покращення.
This paper studies the performance of distributed soft real-time systems that use standard components with various scheduling algorithms and ways to improve them.
|
| issn |
1817-9908 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/46483 |
| citation_txt |
Исследование характеристик знание ориентированных интеллектуальных систем мягкого реального времени / С.В. Зинченко // Комп’ютерні засоби, мережі та системи. — 2012. — № 11. — С. 13-22. — Бібліогр.: 19 назв. — рос. |
| work_keys_str_mv |
AT zinčenkosv issledovanieharakteristikznanieorientirovannyhintellektualʹnyhsistemmâgkogorealʹnogovremeni AT zinčenkosv researchofperformanceofknowledgeorientedintellectualsoftrealtimesystems |
| first_indexed |
2025-11-25T21:10:44Z |
| last_indexed |
2025-11-25T21:10:44Z |
| _version_ |
1850552537735757824 |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2012, № 11 13
S. Zinchenko
RESEARCH OF PERFORMANCE
OF KNOWLEDGE ORIENTED
INTELLECTUAL SOFT
REAL-TIME SYSTEMS
This paper studies the performance
of distributed soft real-time systems
that use standard components with
various scheduling algorithms and
ways to improve them.
Key words: soft real-time, distribu-
ted systems, deadline assignment,
priority assignment, scheduling.
Вивчається продуктивність роз-
поділених м’яких систем реально-
го часу, які використовують ста-
ндартні компоненти з різними
алгоритмами планування і пропо-
нуються шляхи їх покращення.
Ключеві слова: м’який реальний
час, розподілені системи, терміни
призначення, пріоритетні задачі,
планування.
Изучается производительность
распределенных мягких систем
реального времени, которые ис-
пользуют стандартные компо-
ненты с различными алгоритма-
ми планирования и предлагаются
пути их улучшения.
Ключевые слова: мягкое реальное
время, распределенные системы,
сроки назначения, приоритетные
задания, планирование.
C.В. Зинченко, 2012
УДК 681.3
C.В. ЗИНЧЕНКО
ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК
ЗНАНИЕ ОРИЕНТИРОВАННЫХ
ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ
МЯГКОГО РЕАЛЬНОГО ВРЕМЕНИ
Введение. Распределенные знание ориен-
тированные интеллектуальные системы (ЗО-
ИС) [1, 2], например, системы научных ис-
следований, позволяют собрать, отфильтро-
вать и сохранить в БД сервера информацию,
полученную с различных источников по оп-
ределенной теме, которую затем можно ис-
пользовать для организации и проведения
новых исследований [3].
Основная часть. Анализ подобных сис-
тем позволяет выделить их особенности. Во-
первых, они состоят из множества компонен-
тов (источники информации, по-
токи данных, сеть, сервер БД, ввод/вывод,
экспертные системы, процессоры и т. п.). Во-
вторых, решение глобальных задач состоят
из нескольких этапов, которые используют
разное подмножество компонентов .
Такие задачи связаны с мягкими сроками
выполнения, например, процедура обновле-
ния данных должна быть выполнена в тече-
ние нескольких минут с момента их получе-
ния. Поэтому ЗОИС можно отнести к рас-
пределенным системам мягкого реального
времени (СРВ) [4 6].
Проблемы проектирования. Распреде-
ленные ЗОИС можно проектировать с “нуля”
(программировать компоненты в соответст-
вии с алгоритмами и функциями будущих
приложений) или создавать из существую-
щих хорошо проверенных и стандартных
компонентов (коммерческие серверы БД, се-
ти и т. п.). Стоимость развития и поддержа-
ние ЗОИС в первом случае будет высокой, и
цикл разработки будет длительным. С точки
С.В. ЗИНЧЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 14
зрения стоимости и времени разработки целесообразным является второй под-
ход. Его недостатком является то, что стандартные компоненты, как правило, не
предназначены для выполнения задач в РВ. Например, коммерческие БД имеют
неопределенное время соединительных операций при запросе, что может при-
вести к приоритетным инверсиям [7]. Но даже если стандартные компоненты РВ
доступны, такие как коммерческие операционные системы РВ (ОС РВ) [7, 8],
они могут варьировать свойства задач в РВ, а их планировщики не могут обес-
печить внешний контроль. Это означает, что при планировании выполнение
глобальных задач в РВ необходимо согласовывать взаимодействия и координа-
ции между локальными планировщиками ( ).Учитывая это существу-
ет проблема создания распределенных ЗОИС из множества компонентов как РВ
так и не РВ с учетом реальных требований/ограничений к СРВ, где гарантиру-
ются выполнения "почти всех" ограничений [9].
Концептуальный подход. Предлагается использовать результаты экспери-
ментов, которые проясняют эти вопросы, иллюстрируют издержки в виде про-
пущенных сроков, и которые позволяют предложить стратегии по снижению
затрат проектирования ЗОИС как мягких СРВ.
Предполагаем, что ЗОИС состоит из множества разных компонент
, где и использует свою собственную политику плани-
рования. Исследуем, как локальные планировщики влияют на
способность системы удовлетворить сроки выполнения задач, а также способы
повышения ее производительности, когда некоторые из компонент , не
могут выполнять расписания в режиме РВ.
Основная цель мягких СРВ удовлетворение, сколько это возможно, сро-
ков, и в отличие от жестких СРВ они не гарантируют соблюдения всех сроков
[7, 8]. Ориентация ЗОИС на мягкое РВ объясняется такими причинами. Во-
первых, задачи СРВ непростые, их выполнение требует участия нескольких
уровней обработки, а это означает, что сложно получить точные оценки времени
работы, которые необходимы для планирования жесткого РВ. Во-вторых, в
большинстве случаев невозможно оценить верхний предел нагрузки на систему.
Обе эти проблемы означают то, что планирование жесткого РВ невозможно.
Известно, что является независимым, и не существует глобального
планировщика, который мог бы управлять всеми системы. Более того,
принимает решения, основываясь исключительно на задачах, которые ему необ-
ходимо выполнить, без согласования с другими , где . В ЗОИС, ко-
торая создается из существующих компонент, каждый компонент имеет свою
собственную политику планирования и неспособен подчинятся/согласовывать
свои решения с другим планированием. Планирование в режиме мягкого РВ
наиболее подходит для ЗОИС, где тип заданий или/и их длительность, как пра-
вило, неизвестны заранее. Особенно, когда система обеспечивает прозрачность
распределения (например, является частью локальных/удаленных данных), за-
дачи, которые должны быть созданы, неизвестны до начала их выполнения, и,
следовательно, выполнить предварительный их анализ невозможно.
ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК ЗНАНИЕ ОРИЕНТИРОВАННЫХ …
Комп’ютерні засоби, мережі та системи. 2012, № 11 15
В ЗОИС является уникальным, и задачи выполнятся на конкретной
компоненте , что приводит к несбалансированной нагрузке. Более того, пере-
груженный компонент не может передать задачу на другие компоненты, т. е.
, где .
Цель исследования. Цель исследования определение: производительно-
сти системы в зависимости от компонент, которые являются задачами FCFS;
преимуществ, которые можно получить, если компоненты предоставляют стати-
ческий приоритет планирования не в РВ.
В исследовании используются простые модели глобальной задачи и распре-
деленной системы, позволяющие понять и оценить основные компромиссы, ко-
торые необходимо использовать при проектировании СРВ [9]. Последователь-
ность исследований такая: описывается модель ЗОИС; обсуждается случай, ко-
гда все компоненты системы используются в режиме планирования EDF (earliest
deadline first); изучается вопрос снижения производительности системы, когда
некоторые компоненты являются задачами FCFS; обсуждаются преимущества,
которые можно получить, если не в РВ компонент выполняет статический при-
оритет планирования (RMS, rate monotonic scheduling).
Модель задач. Предполагаем, что имеется последовательность глобальных
задач , которые выполняются на нескольких компонентах системы. Каждая
глобальная задача состоит из подзадач , которые выполняются
последовательно при условии, что подзадача не может быть выпол-
нена до завершения подзадачи . или характеризуется такими атри-
бутами: время поступления; крайний срок завершения (время
завершения); резерв времени. Для определяются стадии, чтобы они
имели позиции в глобальной задаче. Например, если , то этап
(Т2) 2. Это означает, что подзадача ранних стадий выполняется раньше,
чем другая подзадача , если они входят в одну и ту же глобальную задачу и
стадия ( ) < стадии ( ).
Всегда существует проблема несвоевременных задач или политики управ-
ления перегрузкой. В ситуации, когда задача уже пропустила свой срок и не
завершила выполнение, для нее возможен только один вариант выполнения
отмена, в предположении, что все, что она делает далее бесполезно.
Модель системы. Модель распределенной ЗОИС включает компоненты,
управляющие различными ресурсами, такими как БД, экспертные системы, вы-
числители, сеть и т. п. (рис. 1). Отметим, что сеть может быть включена в каче-
стве одного/нескольких компонентов. Например, прямую связь между двумя
сайтами можно рассматривать как один из ресурсов, а всю сеть можно считать
другим ресурсом. Порядок выполнения целевой функции планируется в локаль-
ных планировщиках каждого из компонентов, которые являются независимыми
и не взаимодействуют между собой. Единственное, что может влиять на плани-
рование решения в режиме РВ это атрибуты каждой из задач.
С.В. ЗИНЧЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 16
Менеджер/ (ы)
процессов
...
...
Компонент s1
Локальный
планировщик p1
Компонент s2
Локальный
планировщик p2
Компонент si
Локальный
планировщик pi
Компонент sn
Локальный
планировщик pn
Источник
глобальных задач T
РИС. 1. Модель системы
Вновь созданные глобальные задачи сначала обрабатывает диспетчер про-
цессов (process manager) [10]. На самом деле может быть не один, а несколько
диспетчеров процессов, которые управляют одной/несколькими глобальными
задачами, и при этом определяют приоритеты, начало и конец выполнения, все
крайние сроки подзадач. Основной функцией диспетчера процессов является
представление подзадачи соответствующего компонента для исполнения, кон-
троль соблюдения ограничения и очередности среди подзадач глобальной зада-
чи. Часто диспетчер процессов должен генерировать информацию для планиро-
вания выполнения подзадач до их поступления. Например, если принимает
задачу в соответствии с приоритетами , а задачи в зависимости от их
сроков, диспетчер процессов должен убедиться, что представлены компонен-
там в соответствии со значениями их атрибутов. Отметим, что и сам диспетчер
процессов потребляет системные ресурсы, например, решая задачу установле-
ния связи между ядром диспетчера и компонентой, и это потребление можно
смоделировать как выполнение дополнительных подзадач в системе. В резуль-
тате можно получить модель требований к ресурсу диспетчера процессов.
Имитационная модель. Для изучения поведения системы в присутствии
множества локальных алгоритмов планировщика можно воспользоваться ими-
тационной моделью, реализованной на языке DeNet (Danish Information Network)
[11]. Каждый имитационный эксперимент генерирует одну точку данных про-
должительностью с, за один проход создаются > задач, что намного
больше максимальной нагрузки на реальную систему.
Имитационная модель системы состоит из компонент, где каждый из ко-
торых поддерживает график выполнения своих задач с помощью таких типов
локальных планировщиков: с ближайшим сроком завершения (EDF), со статиче-
ским приоритетом (RMS rate monotonic scheduling), поочередного обслужива-
ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК ЗНАНИЕ ОРИЕНТИРОВАННЫХ …
Комп’ютерні засоби, мережі та системи. 2012, № 11 17
ния вызовов (FCFS). Прерывание планировщика во всех случаях запрещено.
Глобальные задачи однородны, и создаются как единый поток пуассоновского
типа со средним интервалом времени между требованиями . Каждая гло-
бальная задача состоит из подзадач, время выполнения которых соответст-
вуют экспоненциальному распределению со средним значением (с). Общее
время выполнения глобальных задач, которое соответствует m-стадиям Эрланга
[12], распределено со средним значением . Поэтому, скорость выполнения
глобальных задач будет равна . Считаем, что узлы в равной степени ис-
пользуются в качестве исполнительных узлов подзадач. Пространство резервно-
го времени глобальных задач равномерно распределено в интервале [Smin, Smax].
Нормированная нагрузка на систему определяется, как отношение генери-
руемой скорости к общей мощности переработки системы, т. е.:
Для стабильной системы . Использованы такие базовые настройки
значений параметров: политика перегрузки управления без прерывания;
; ; ; ; .
Планировщики задач. Предполагается, что все компоненты выполняют
EDF планирование. Сначала подзадаче представляется компонент, и диспетчер
процессов назначает сроки их выполнения, так что компонент не знает как их
планировать. Одним из простых способов присвоения сроков подзадачам явля-
ется наследование ими (из конца в конец) сроков своих глобальных задач. Эту
стратегию называют стратегией максимального предельного срока (Ultimate
Deadline UD).
В работах [13, 14] показано, что UD эффективна, если глобальные задачи
системы, состоят из подзадач одинаковой длины и их времена выполнения поч-
ти одинаковы. Длинные глобальные задачи страдают высокой степенью пропус-
ков сроков. Причиной такого выполнения глобальной задачи в присутствии ко-
ротких подзадач является то, что на многочисленных этапах подзадачи, как пра-
вило, имеют более поздний предельный срок, чем конечный срок. На ранней
стадии глобальная задача свои подзадачи принимает с конца срока, и местные
EDF планировщики будут обмануты, полагая, что имеют существенный запас
для выполнения. Время, должно быть зарезервировано для выполнения подзадач
на более поздних этапах, и поэтому, EDF планировщики дают очень низкий
приоритет . Это приводит к существенной задержке в выполнении и, следо-
вательно, глобальная задача будет длительной и пропустит сроки.
В работе [13] предложены методы снижения пропущенных сроков обслужи-
вания глобальных задач. Метод равных запасов (Equal Slack EQS), оценивает
временной запас выполнения глобальной задачи и делит его поровну между ос-
тавшимися подзадачами. Например, глобальная задача поступает в момент вре-
мени 0 со сроком времени 12 и состоит из четырех подзадач, каждая из которых
выполняется за 1 единицу времени. Эта глобальная задача имеет запас в 8 еди-
С.В. ЗИНЧЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 18
ниц. EQS выделит 2 его единицы для и резервирует 6 единиц от до под-
задачи на более поздних стадиях к началу от срока времени. Как показано в [13],
EQS приводит к существенному снижению пропусков сроков глобальной зада-
чей. Далее предполагается, что когда подзадаче представляется компонент с
EDF планированием, то ей назначается суб-срок в соответствии со стратегией
EQS.
FCFS планировщики. Отметим, что при создании мягкой СРВ, можно как
использовать, так и не использовать специализированные компоненты РВ, на-
пример, сети РВ или БД, планирующие запросы ввода/вывода в зависимости от
сроков. Очевидно, что компоненты РВ решают проблему распределения сис-
темных конечных сроков проще, но, к сожалению, это гораздо дороже и не все-
гда доступно. Например, драйверы сети Ethernet и Token Ring не поддерживают
трафик в РВ и они, как правило, доставляют сообщения в соответствии со стра-
тегией FCFS.
В качестве другого примера можно назвать дисковые контроллеры, в кото-
рых используются так называемые лифтовые алгоритмы [15]. Расписание диско-
вых запросов блокирует дисковую операцию вместо того, чтобы запросить сро-
ки выполнения подзадач. Обычные алгоритмы планирования РВ как EDF не вы-
полняются эффективно для диска, поскольку они имеют длительное среднее
время поиска и плохую пропускную способность [16, 17].
Практически при создании ЗОИС как мягких СРВ возникают следующие
вопросы. Если нет возможности использовать компоненты РВ, то, как это влияет
на производительность системы в РВ? Насколько важно, чтобы каждый компо-
нент системы понимал сроки? Является ли компонент не РВ узким местом сро-
ков выполнения? Можно задержку задачи не РВ компенсировать во время ис-
пользования компоненты в режиме РВ? Чтобы ответить на эти вопросы и иссле-
дуется деградация распределенных мягких СРВ, когда компоненты выполняют
FCFS планирование вместо EDF.
Из рис. 2 видно, что глобальная задача увеличивает пропуски с увеличением
нагрузки на систему ( ). При низкой нагрузке, система
имеет достаточную мощность для обработки задач, и тип локального планиров-
щика FCFS /EDF является несущественным. По мере увеличения нагрузки сис-
тема начинает пропускать больше сроков, и разница между этими двумя плани-
ровщиками становится значимой. Например, при высокой нагрузке ,
система с 6 локальными FCFS планировщиками пропускает примерно на 1,5
срока больше, чем система с 6 локальными EDF планировщиками. Отметим, что
в нормальных условиях мягкая СРВ работает с малой нагрузкой и, поэтому,
имеет минимальное число пропусков. Однако, система может быть перегружен-
ной, и именно для таких режимов требуются планировщики, обеспечивающие
наименьшее количество пропущенных сроков. Для оценки работы системы в
таких режимах предлагается следующая математическая модель [18]:
ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК ЗНАНИЕ ОРИЕНТИРОВАННЫХ …
Комп’ютерні засоби, мережі та системи. 2012, № 11 19
Не удивительно, что все планировщики FCFS системы работают хуже в
сравнении с EDF планировщиками, а переход от компонента EDF к FCFS вызы-
вает незначительную потерю производительности. Производительность системы
имеет линейную деградацию по числу компонентов при увеличении на-
грузки на систему, что и показано на рис. 2. . Для оценки
такой потери производительности предложена такая математическая модель:
. .
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7
0,00
0,05
0,10
0,15
0,20
0,25
0,168
0,224
N
fcfc
= 0, локальный планировщик EDF
N
fcfc
=1
N
fcfc
=6
l=0,35
l=0,5
MD
l
l=0,65
A: высокая нагрузка, load=0,65
0 1 2 3 4 5 6 7
N
fcfc
РИС. 2. Доля пропущенных сроков в зависимости от загрузки системы, числа и типа
локальных планировщиков
Для изучения поведения системы при различной нагрузке были изменены ус-
ловия эксперимента так, чтобы все стадии 1 подзадач исключительно выполня-
лись на компоненте 1, при этом компоненты 2 6 обрабатывали остальные под-
задачи. Например, каждая глобальная задача распределенной мягкой СРВ ис-
пользует сетевой компонент, но не все задачи запрашивают доступ к серверу
данных. Так как каждая глобальная задача состоит с четырех подзадач, то 25 %
нагрузки будет обрабатываться компонентой 1, а другие 5 компонент будут об-
рабатывать остальные 75 % загрузки системы.
На рис. 3 показаны два случая переключения локальных планировщиков
EDF и FCFS один за другим, когда компонент 1 включается первым и послед-
ним, что соответствуют двум уровням нагрузки системы ( ). На-
блюдаем, что при переходе с EDF на FCFS в основном загружен компонент 1, и
С.В. ЗИНЧЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 20
количество пропусков увеличивается на ~3,5 %, и при переходе на другие 5
компонентов происходит постепенное линейное увеличение MD на 0,36 %
(до 13,5 %). Очевидно, что несмотря на то, что 2 6 компоненты совместно от-
вечают за 75 % общей нагрузки на систему, запуск 5 EDF планировщиков на
этих компонентах менее эффективен, чем запуск 1 EDF планировщика на ком-
поненте 1.
0,1 0,2 0,3 0,4 0,5 0,6 0,7
0,00
0,05
0,10
0,15
0,20
0,25
выключение компоненты 1 последней
выключение компоненты 1 первой
l=0,35
l=0,5
все EDF
RTE
все FCFS
l
0 1 2 3 4 5 6
MD N
fcfs
РИС. 3. Доля пропущенных сроков в зависимости от числа локальных планировщиков
FCFS и типов локальных планировщиков выполнение (FCFS, EDF,RTE)
Приведенные данные позволяют сделать вывод, что потеря производитель-
ности FCFS компонента вместо EDF связана с нагрузкой этого компонента. Ко-
гда все компоненты системы загружаются однотипно и используют приблизи-
тельно одинаковое количество задач, то потери производительности почти ли-
нейны от числа компонент FCFS. Это показывает то, что эффективно использо-
вать два FCFS компонента, если допустима незначительная потеря производи-
тельности. Если же это не так, то необходимо сосредоточить внимание на тяже-
ло нагруженных компонентах системы. Для обеспечения более высокой произ-
водительности эти компоненты должны использовать планировщики в режиме
РВ или должны быть продублированы. В некоторых случаях увеличить произ-
водительность можно путем использования компонент планирования EDF.
Статический приоритет планирования. Вышепоказано, как производи-
тельность системы снижается, когда в режиме РВ компоненты используют FCFS
планирование. Стандартные не РВ компоненты бывают более эффективными,
чем FCFS в случае использования статического планирования задач, например, в
ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК ЗНАНИЕ ОРИЕНТИРОВАННЫХ …
Комп’ютерні засоби, мережі та системи. 2012, № 11 21
POSIX UNIX и в кольцевых сетях с маркерным доступом. Рассмотрим вопрос
возможного использования статических приоритетов планирования в распреде-
ленных мягких СРВ и способы возможного улучшения производительности
FCFS планировщиков.
Идея состоит в эмуляции алгоритма планирования режима РВ (real time
emulation RTE) с использованием статического приоритета. В работе [19]
предложены способы отображения атрибутов задач РВ (срок, время прихода и т.
п.) в уровень приоритета для однопроцессорной системы. Перед выполнением
подзадачи диспетчер процессов компонента вычисляет для суб-срок. Затем
к началу срока вычисляется его уровень приоритета в соответствии с линей-
ным отображением:
,)()(
ji siiT tTarTdlpr
где настройка параметров для компонента .
На рис. 4 показаны результаты оценки пропусков сроков глобальной зада-
чей для таких случаев использования компонент: все FCFS; все EDF; все стати-
ческого приоритета планирования с 4 уровнями приоритетов. Видно, что даже с
4 уровнями приоритета, статический приоритет планирования с RTE выполняет
почти также как с EDF. Только при высокой нагрузке RTE незначительно пре-
восходит EDF. Причина того, что RTE пропускает меньше сроков в том, что при
высокой нагрузке, EDF, как правило, отдают предпочтение более поздним зада-
чам. Из-за этого в режиме перегрузки RTE не может прогнозировать сроки для
всех задач должным образом, по существу RTE не дает шанс закончить запозда-
лые задачи до их заданных сроков.
Недостаток RTE подхода проявляется в том, что его производительность
чувствительна к значению и распределению допусков для задач. При равно-
мерном распределении линейное отображение работает хорошо. В других усло-
виях необходимы другие отображения, которые будут равномерно распределять
задачи по приоритетам, для обеспечения хорошей производительности. Это
приводит к усложнению диспетчера процессов. Однако, когда для ЗОИС компо-
ненты РВ отсутствуют/недоступны, использование RTE является эффективным
и экономичным способом снижения пропущенных сроков.
Выводы. В работе исследованы системы мягкого РВ, где используются
обычные не РВ компоненты. Конечно, в системах жесткого РВ, никто не будет
использовать компоненты не РВ. Однако, есть много приложений, таких как
ЗОИС, в которых сроки не столь жесткие, что и является причиной использова-
ния доступных не РВ компонент против компонент РВ.
Показано, как производительность системы снижается, когда EDF плани-
ровщики заменяются FCFS планировщиками. В общем, при низкой нагрузке на
систему, использование не РВ компонентов несущественно увеличивает про-
пуски. Экономически оправдано использовать стандартные компоненты не РВ,
так как специализированные компоненты РВ являются дорогими и порой недос-
тупными. В системах, которые имеют высоконагруженные компоненты важно,
С.В. ЗИНЧЕНКО
Комп’ютерні засоби, мережі та системи. 2012, № 11 22
чтобы они содержали планировщики РВ. В случае отсутствия планировщиков
РВ, необходимо увеличить мощность компонентов системы путем дублирования
компонент FCFS, а в случае статического планировщика необходимо использо-
вать эмуляции алгоритмов РВ, устанавливающие сроки с учетом приоритетов.
Результаты показывают, что последний метод выполнятся почти как реальный
EDF планировщик. Для оценки доли пропущенных сроков можно воспользо-
ваться предложенными математическими моделями.
1. Зинченко С.В. Онтологически управляемые информационные системы // Открытые ин-
формационные и компьютерные интегрированные технологии. – Харьков: Гос. Аэроком.
Ун-т “ХАИ”, 2004. – Вып. № 19. – С. 256 – 262.
2. Зинченко С.В. Элементы структурирования знаний: понятия, атрибуты и произвольные
отношения // Открытые информационные и компьютерные интегрированные техноло-
гии. – Харьков: Гос. Аэроком. Ун-т “ХАИ”, 2004. – Вып. № 23. – С. 84 – 89.
3. Зинченко В.П., Зинченко С.В. Архитектура и организация системы удаленного доступа к
информации микроспутника // Комп’ютерні засоби, мережі та системи. –2011. – № 10. –
С. 56– 67.
4. Зінченко В.П., Ходаковський М.І., Зінченко С.В.,Татулашвілі Т.І. Онтологічний підхід до
проектування автоматизованих навчаючих систем // Комп’ютерні засоби, мережі та сис-
теми. – 2009. – № 8. – С. 94 – 101.
5. Гераїмчук М.Д., Зінченко В.П., Лапінський В.В., Зінченко С.В. та ін. Інформаційні
технології в освіті: методи та засоби. – Монографія. – К.: НТУУ “КПІ”, 2009. – 89 c.
6. Гераїмчук І.М., Зінченко С.В. Проблеми представлення знань в інформаційних
технологіях. – Монографія. – К.: НТУУ «КПІ», 2010. – 240 с.
7. Блискавицкий А.А., Кабаев С.В. Операционные системы реального времени (обзор) //
Средства и системы компьютерной автоматизации. http://www.asutp.ru.
8. Египко В.М., Зинченко В.П. Метод и инструментальные средства обработки данных
эксперимента в реальном времени. – Киев, 1995. – 24 с. (Препр. / АН Украины ИК
им. В.М. Глушкова; 95 – 20).
9. Kao B., Garcia-Molinay H., Adelbergz B. On Building Distributed Soft Real-Time Systems
Technical Report, Stanford University, 1994. – 12 p.
10. Олифер В.Г., Олифер Н.А. Сетевые операционные системы. – СПб.: Питер, 2002. – 544 с.
11. Livny M. DeNet user 's guide. Technical report, University of Wisconsin-Madison, 1990. –30 p.
12. Бусленко Н.П. Моделирование сложных систем. – М.: Наука, 1978. – 356 с.
13. Kao B., Garcia-Molina H. Deadline assignment in a distributed soft real-time system. In Pro-
ceedings of the 13th International Conf. on Distributed Computing Systems, 1993. – Р.
428 – 437.
14. Pang H., Livny M., Carey M.J. Transaction scheduling in multiclass real-time database sys-
tems. In Proceedings of IEEE Real-Time Systems Symposium, 1992. – P. 23 – 34.
15. Peterson J.L., Silberschatz A. Operating System concepts. Addison-Wesley, 1985. – 968 p.
16. Carey M.J., Jauhari R., Livny M. Priority in DBMS resource scheduling. In Proceedings of the
15th VLDB Conf. 1989. – Р. 397 – 410.
17. Abbott R., Garcia-Molina H. Scheduling II O requests with deadlines: a performance evalua-
tion. In Proceedings of IEEE Real-Time Systems Symposium, 1990. – Р. 124 – 133.
18. Зинченко В.П., Зинченко С.В., Муха И.П. Алгоритм полиномиальной регрессии и его реа-
лизация в среде Mathcad // Нові комп’ютерні засоби, обчислювальні машини та мережі.
Том 1. – К.: Ін-т кібернетики ім. В.М. Глушкова НАН України, 2001. – С. 115 – 123.
19. Adelberg B., Garcia-Molina H., Kao B. Emulating soft real-time scheduling using traditional
operating system schedulers. In IEEE Real-Time System Symposium, 1994. – 25 p.
Получено 11.10.2012
|