ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2016 г.)
2-летний импакт-фактор РИНЦ: 0,493
2-летний импакт-фактор РИНЦ без самоцитирования: 0,389
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,732
5-летний импакт-фактор РИНЦ: 0,364
5-летний импакт-фактор РИНЦ без самоцитирования: 0,303
Суммарное число цитирований журнала в РИНЦ: 5022
Пятилетний индекс Херфиндаля по цитирующим журналам: 355
Индекс Херфиндаля по организациям авторов: 499
Десятилетний индекс Хирша: 11
Место в общем рейтинге SCIENCE INDEX за 2016 год: 304
Место в рейтинге SCIENCE INDEX за 2016 год по тематике "Автоматика. Вычислительная техника": 11

Больше данных по публикационной активности нашего журнале за 2008-2016 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

1
Ожидается:
16 Марта 2018

Локально определенные дисциплины планирования

Locally defined planning disciplines
Статья опубликована в выпуске журнала № 4 за 2013 год. [ на стр. 67-73 ][ 11.12.2013 ]
Аннотация:В статье рассматриваются системы, а также функции и дисциплины планирования. Система представляет собой конечное множество заданий, каждое из которых характеризуется моментом старта, требуемой ресурсной длительностью и максимальным временем исполнения. Функция планирования устанавливает соответствие между текущим моментом времени и исполняемым в этот момент заданием. Особую роль при изучении дисциплин планирования играют критические точки, то есть моменты времени старта заданий. Вводится понятие дисциплины планирования как правила, определяющего для каждой системы S функцию планирования D(S). Далее вводятся и изучаются унаследованные дисциплины планирования, которые задают функцию планирования только на основании состояния системы в критических точках. Формулируется теорема, устанавливающая тождественность алгоритмического и аксиоматического определений унаследованной дисциплины планирования. Дисциплина планирования является локально определенной, если функция D(S) зависит от состояния системы в произвольный момент времени, когда осуществляется планирование. В статье формулируется следующая структурная теорема, характеризующая локально определенные дисциплины планирования: дисциплина планирования является локально определенной тогда и только тогда, когда она является унаследованной по отношению к локально определенной синхронной дисциплине планирования.
Abstract:The paper deals with systems, considering as a number of tasks, which are to be executed in a predefined period of time. Planning function points to a particular task of a system which is to be executing in a current moment. Planning discipline is a rule prescribing a specific planning function to a system. Planning function, although it is a global object, could be considered locally, i.e. it could be built based on local conditions but not the whole scope of data, describing all tasks in the past and in the future (according to a current moment). Inherited and locally defined disciplines are under consideration. The paper clarifies corresponding notions in a mathematical manor. Inherited disciplines are those which depend on system state in critical points, i.e. moments when new tasks appear. A theorem establishing coincidence of algorithmic and axiomatic definitions of inherited disciplines is formulated. Locally defined discipline prescribes to a system its planning function in a way that depends on local state of the system in an arbitrary moment of time. A theorem is formulated which determines a structure of an arbitrary locally defined discipline. The theorem states that a locally defined discipline is inherited in relation to a locally defined discipline applied to systems with a single critical point.
Авторы: Грюнталь А.И. (grntl@niisi.msk.ru) - НИИСИ РАН, г. Москва, г. Москва, Россия, кандидат физико-математических наук
Ключевые слова: локально определенная дисциплина планирования, унаследованная дисциплина планирования, дисциплина планирования, функция планирования, программное обеспечение, системы реального времени
Keywords: locally defined planning discipline, inherited discipline, planning discipline, planning function, the software, realtime systems
Количество просмотров: 3109
Версия для печати
Выпуск в формате PDF (7.95Мб)
Скачать обложку в формате PDF (1.45Мб)

Размер шрифта:       Шрифт:

В статье рассматривается один из важных вопросов программирования – обеспечение доступа к ресурсу в условиях конкуренции. Наиболее очевидным примером является распределение ресурса процессора между различными потоками управления в системах реального времени. Каждый поток управления реализует некоторый прикладной аспект функционирования приложения и, как это должно быть в системах реального времени, должен получить определенный ресурс, чтобы завершить выполнение конкретной прикладной функции в условиях заданного ограничения на время исполнения. Потоки управления при этом должны выполняться в такой последовательности, чтобы все реализуемые ими прикладные функции были завершены в срок. Аналогичная проблема возникает при доступе к устройствам ввода-вывода, когда данные должны быть прочитаны или выведены в определенный промежуток времени разными программными агентами.

В качестве средства формализации этой задачи в статье рассматриваются системы, то есть набор заданий, каждому из которых требуется определенный ресурс для выполнения своей миссии и предписано максимальное время выполнения, соответствующее прикладной функции [1]. Единой универсальной мерой потребления ресурса является время. Поэтому задание характеризуем как объект, содержащий ресурсную длительность, – длительность потребления ресурса, необходимую для выполнения прикладной функции, и максимальную длительностью выполнения задания – интервал времени (начиная с момента возникновения задания), больше которого задание не может выполняться.

Кроме этих параметров, задание характеризуется моментом старта и индексом – идентификатором, позволяющим ссылаться на конкретное задание. Система, в свою очередь, формализуется как конечное множество заданий.

Таким образом, возникает задача распределения по времени последовательности выполнения заданий, из которых состоит система. Средством, определяющим задание, которое должно выполняться в заданный момент времени, является функция планирования. Она либо указывает на индекс задания, и тогда выполняется задание, либо принимает нулевое значение, которое по умолчанию означает ситуацию простоя. Кроме того, функция планирования должна удовлетворять некоторым ограничениям физического характера, например, функция планирования принимает значение индекса, относящегося к одному заданию, на множестве, представляющем собой объединение конечного количества непересекающихся полуинтервалов. Конечность множества полуинтервалов означает, что переключение при планировании обслуживания (выполнения) одного задания на другое может происходить только конечное число раз. Выбор в качестве сегментов постоянного указывания именно полуинтервалов, а, допустим, не интервалов связан с выбранной формализацией функции планирования.

Потенциально могут существовать два подхода к изучению систем указанного вида. Весь набор заданий, образующих систему, можно рассматривать как данность [1] и при планировании выполнения заданий учитывать не только текущее состояние системы, но и сведения относительно состояния системы в последующие моменты времени. Такое возможно, если поведение системы в каком-то смысле детерминировано. Но на прак- тике часто складывается ситуация, когда возникновение задания носит случайный во времени характер: например, когда в поле зрения радара появляется новый объект и надо неотлагательно обработать соответствующие данные. В этом случае планирование должно быть локальным по времени, то есть определяться состоянием системы на момент возникновения нового задания (или нескольких новых заданий) и вновь возникшими требованиями к вычислительной системе, относящимися к появившимся заданиям.

Функции планирования, описывающие именно второй тип реакции системы на задания, называются локально определенными. С их появлением возникает необходимость во введении адекватных математических понятий, выделяющих класс локально определенных функций планирования по отношению к остальным функциям планирования, не отвечающим требованиям локальной определенности. Следующая задача, помимо формального описания таких функций планирования, – исследование свойств функций. Ей и посвящена данная статья.

Объектом рассмотрения являются дисциплины планирования, то есть методы, определяющие выбор функции планирования для конкретной системы. Дисциплины планирования рассматриваются в статье как составные объекты, получаемые по определенной процедуре из более простых объектов, а именно, дисциплин планирования для систем, в которых моменты старта всех заданий совпадают. В статье вводятся локально определенные дисциплины планирования. Это такие дисциплины планирования, которые зависят только от текущего состояния системы.

Основные определения

Заданием назовем четверку чисел (t, L, T, I), такую, что t≥0, 0

Моментом старта системы называется наименьший из моментов старта, образующих систему заданий. Момент старта системы S обозначим через start(S). Область определения системы – множество чисел τ, удовлетворяющих неравенству start(S)≤τ.

Множество индексов системы S будем обозначать через IndSet(S). Расширенным множеством индексов системы S является множество, которое получается путем добавления к IndSet(S) числа 0. Расширенное множество индексов обозначается через IndSet(S)+.

Число τ называется критической точкой системы S, если оно является моментом старта хотя бы одного из заданий системы S. Системой с синхронным стартом (или синхронной системой) называется такая система, у которой только одна критическая точка. Системы с двумя или более критическими точками – это системы с асинхронным стартом (или асинхронные системы).

Пусть даны система S и множество A, принадлежащее области определения системы S. Ограничение системы S на множество A – это множество, состоящее только из тех заданий системы S, момент старта которых принадлежит множеству A. Ограничение системы S на множество A обозначается через S(A). Множество S(A) может быть пустым. Если множество S(A) не пустое, оно будет подсистемой системы S. В соответствии с этими обозначениями, если τ – критическая точка системы S, через S(τ) обозначается множество тех заданий из S, моменты старта которых равны τ.

Полуинтервалом [α, β) с границами α и β является множество точек τ вида α≤τ<β. Число α – левая, а β – правая граница полуинтервала. Левая граница полуинтервала c обозначается через inf(c), а правая – через sup(c). Отрезок [α, β] – это множество точек вида a≤τ≤β.

Множество C, представимое в виде объединения набора попарно непересекающихся полу- интервалов c1, …, cN, называется конечно составленным. Набор попарно непересекающихся полуинтервалов будем иногда называть комплектом полуинтервалов. Длина ||C|| конечно составленного множества C – это сумма длин полуинтервалов c1, …, cN. Длина пустого множества равна 0. Левой границей inf(C) конечно составленного множества C называется минимальная левая граница среди всех левых границ полуинтервалов c1, …, cN. Аналогично определяется правая граница sup(C).

Пусть p – числовая функция, принимающая значение a. Через coimg(p)(a) обозначим прообраз значения a, то есть множество таких чисел τ, что p(τ)=a. Определенная на неограниченном полуинтервале функция p называется ступенчатой, если множество значений функции p конечно и прообраз каждого значения функции p представляет собой конечно составленное множество. Пусть p1 и p2 – две функции с областями определения [t1, +∞) и [t2, +∞), t1

Функции планирования

 

Дадим определение функции планирования. Функцией планирования системы S является функция p, для которой выполнены следующие требования:

–      функция p определена на области определения системы S;

–      функция p принимает значения во множестве IndSet(S)+;

–      функция p является ступенчатой;

–      для каждого задания (t, L, T, I) из S выполнено ||coimg(p)(I)||=L;

–      для каждого задания (t, L, T, I) из S выполнено неравенство t≤inf(coimg(p)(I)).

Число sup(coimg(p)(I)) будем называть моментом окончания исполнения задания и обозначать через tfin.

Пару (S, p), где p – функция планирования системы S, будем называть системой с планированием. Пусть дана система с планированием (S, p). Для каждого задания (t, L, T, I) системы S и каж- дого числа τ≥t определим величину Σ(I, p)(τ). Примем Σ(I, p)(τ)=0. При τ>t положим, что Σ(I, p)(τ)=||coimg(p)(I)∩[t, τ)||.

Напомним, что в соответствии с определением длина пустого множества равна 0, и поэтому, если множества coimg(p)(I) и [t, τ) не пересекаются, Σ(I, p)(τ)=0. Величину Σ(I, p)(τ) назовем выполненной частью задания с индексом I на момент времени τ для системы с планированием (S, p). Величину Σ(I, p)(τ) можно рассматривать как функцию параметра τ при фиксированных значениях параметров I и p. Поэтому величину Σ(I, p)(τ) будем называть функцией расхода ресурса (за- дания с индексом I для системы с планировани- ем (S, p)).

Стандартным представлением конечно составленного множества C называется такой занумерованный в порядке возрастания комплект полуинтервалов c1, ..., cN, что sup(ci)βN функция Σ(I, p) – константа, равная Σ(I, p)(βN)=L. При τ из (αi,βi], где 1≤i≤N, выполнено равенство Σ(I, p)(τ)=Σ(I, p)(αi)+τ–αi. В частности, Σ(I, p)(βi)=Σ(I, p)(αi)+||βi–αi||.

Процесс выполнения во времени задания (t, L, T, I) можно рассматривать так: с течением времени τ величины L и T начинают уменьшаться. Параметр T уменьшается постоянно и линейно, с коэффициентом пропорциональности –1. Параметр L уменьшается на тех полуинтервалах, где функция планирования принимает значение I.

Если L станет равным 0 раньше или в момент, когда параметр T будет равным 0, то при τ=T+t задание успешно выполнено. Если же в момент времени T+t параметр L остается положительным, при заданной функции планирования p успешное планирование задания невозможно. Для уточнения этой ситуации рассмотрим определенную при τ≥t функцию R(I, p)(τ)=T–(τ–t)–(L–Σ(I, p)(τ)).

Опишем поведение функции R(I, p). Прежде всего R(I, p)(t)=T–L, поэтому R(I, p)(t)≥0. При τ из [t, α1] выполнено равенство R(I, p)(τ)=T–L–(τ–t). На отрезках [αi, βi] функция R(I, p) – константа, равная R(I, p)(αi)=R(I, p)(βi). При τ из [βi, αi+1] выполнено равенство R(I, p)(τ)=R(I, p)(βi)–(τ–βi), а при τ≥βN – равенство R(I, p)(τ)=R(I, p)(βN)–(τ–βN). Таким образом, функция R(I, p) является невозрастающей на полуинтервале [t, +∞), где t – момент старта задания с индексом I, и принимает все значения от T–L до –∞. Из изложенного следует, что существует единственное число τI, такое, что при τ≤τI выполнено неравенство R(I, p)(τ)≥0, а при τ>τI – неравенство R(I, p)(τ)<0. Это число τI будем называть моментом исчерпания ресурса.

Пусть (t, L, T, I) есть задание системы с пла- нированием (S, p) и τ≥t. Тогда четверка чисел (τ, L–Σ(I, p)(τ), T–(τ–t), I) будет называться остатком задания с индексом I на момент времени τ. Остаток задания снова будет заданием, если выполнены неравенства L–Σ(I, p)(τ)>0 и R(I, p)(τ)≥0. Эти два неравенства можно также записать в следующем виде: τ

Классификация заданий системы с планированием

Пусть (S, p) – система с планированием, (t, L, T, I) – задание из этой системы и τ≥t. Если τ

Пусть (S, p) – система с планированием и τ>start(S). Будем считать, что система с планированием (S, p) разрешима на момент времени τ, если в S отсутствуют задания, не выполненные в срок на момент времени τ. Пусть система с планированием (S, p) разрешима на момент времени τ, (t, L, T, I) – задание системы S и τ>t. Тогда справедлива следующая альтернатива: либо задание (t, L, T, I) выполнено на момент времени τ, либо существует правое ограничение этого задания на момент времени τ.

Дадим определение остатка системы с планированием. Пусть (S, p) – система с планированием, τ>start(S), и система (S, p) разрешима на момент времени τ. Обозначим через Done(S, p)(τ) множество заданий системы S, выполненных на момент времени τ.

Пусть Ex(S, p)(τ)=S([start(S), τ))\Done(S, p)(τ) – теоретико-множественная разность S([start(S), τ)) и Done(S, p)(τ). Если множество Ex(S, p)(τ) не пусто, остаток системы с планированием (S, p) на момент времени τ – это множество правых ограничений заданий, входящих в Ex(S, p)(τ). Если же множество Ex(S, p)(τ) пусто, то остаток системы с планированием (S, p) на момент времени τ по определению является пустым множеством. Если система с планированием не является разрешимой на момент времени τ, остаток системы с планированием не определен. Остаток системы с планированием на момент времени τ будем обозначать через rem(S, p)(τ).

Срез системы с планированием

 

Определение среза системы с планированием дадим в несколько этапов. Пусть S – система, и τ≥start(S). Если число τ – критическая точка системы, то S(τ) – синхронная система. Если τ не является критической точкой, то S(τ) – пустое множество.

Пусть (S, p) – система с планированием. При τ=start(S) определим срез системы с планированием (S, p) на момент времени τ как S(start(S)). Пусть τ>start(S) и система (S, p) разрешима на момент времени τ. Тогда определим срез системы с планированием на момент времени τ как объединение множеств S(τ) и rem(S, p)(τ). Срез системы с планированием представляет собой либо синхронную систему, либо пустое множество.

Если система с планированием (S, p) не является разрешимой на момент времени τ, срез этой системы с планированием на момент времени τ не определен. Срез системы с планированием на момент времени τ обозначим через slice(S, p)(τ).

Пусть p – функция планирования системы S([s, α)) и определен срез системы с планированием (S([s, α)), p) на момент α. Пусть q – функция планирования системы slice(S([s, α)), p)(α). Обозначим через r композитную функцию, порожденную функциями планирования p и q.

Лемма (о композитной функции планирования). Композитная функция r будет функцией планирования системы S([s, α]).

 

Дисциплины планирования

 

Дисциплина планирования – это отображение, которое ставит в соответствие каждой системе из некоторого множества систем функцию планирования этой системы. Функцию планирования, определяемую дисциплиной планирования D для системы S, будем обозначать через D(S). Множество систем, для которых определена функция D(S), является областью определения дисциплины планирования. Будем говорить, что дисциплина планирования определена для системы S, если S принадлежит области определения дисциплины планирования. Область определения дисциплины планирования D обозначим через Dom(D).

Построим дисциплины планирования для произвольных систем исходя из дисциплины планирования для синхронных систем. В связи с этим определим синхронную дисциплину планирования как дисциплину планирования, определенную для синхронных систем.

Унаследованные дисциплины планирования являются промежуточным звеном между классом всех дисциплин планирования и локально определенными дисциплинами планирования. Приведем конструкцию, задающую построение функции планирования для асинхронных систем, исходя из дисциплины планирования для синхронных систем. Построение будем вести по индукции по числу критических точек системы. Пусть Dsyn – синхронная дисциплина планирования. Если система S имеет одну критическую точку, примем p1=Dsyn(S). Пусть теперь S – система и τ, …, τN+1 – критические точки системы S, пронумерованные в порядке возрастания.

Предположим, что функции планирования p1, …, pK определены соответственно для систем S([τ1, τ1]), …, S([τ1,τK]) и K

Приведенный алгоритм построения функции планирования является алгоритмом унаследования, а функция, построенная с помощью этого алгоритма, унаследованной функцией планирования по отношению к синхронной дисциплине планирования Dsyn. Заметим, что из построения функции pN непосредственно следует, что на полуинтервале [τ1, τK+1) функция pK совпадает с функцией pN.

Для того чтобы алгоритм унаследования приводил к построению функции планирования системы S, требуется выполнение двух условий. Во-первых, каждая из функций pK действительно должна быть функцией планирования системы S([τ1, τK]) и, во-вторых, срез slice(S([τ1, τK]), pK)(τK+1) должен быть определен при всех K от 1 до N–1.

Определенность среза slice(S([τ1, τK]), pK)(τK+1) эквивалентна условию разрешимости на момент времени τK+1 системы с планированием (S([τ1, τK]), pK). Выполнение (или невыполнение) этого условия определяется свойствами системы S. Поэтому можно лишь потребовать его выполнения. А то, что функция pK+1 действительно является функцией планирования при условии, что функция pK определена и является функцией планирования, непосредственно следует из леммы о композитной функции планирования, примененной к системе с планированием (S([τ1, τK]), pK) и к функции планирования Dsyn(slice(S([τ1, τK]), pK)(τK+1)).

Пусть S – система, τ1, …, τN – критические точки системы S, пронумерованные в порядке воз- растания. При K

–      определен срез slice(S, p)(τK);

–      на каждом из полуинтервалов mK функции p и Dsyn(slice(S, p)(τK)) совпадают.

Можно доказать, что каждая унаследованная функция планирования pN системы S с N крити- ческими точками удовлетворяет условию унаследования. Верно и обратное. Если функция планирования p системы S удовлетворяет условию унаследования, алгоритм унаследования приводит к построению функции планирования, то есть справедлива следующая теорема.

Теорема (об унаследованной функции планирования). Функция планирования системы S удовлетворяет условию унаследования для Dsyn тогда и только тогда, когда она является унаследованной функцией планирования по отношению к Dsyn.

Дадим определение унаследованной дисциплины планирования. Обозначим через Dom(Dsyn) множество систем, для которых существует уна- следованная функция планирования. Унаследованной дисциплиной планирования по отношению к синхронной дисциплине планирования Dsyn называется отображение, которое каждой системе S из Dom(Dsyn) ставит в соответствие унаследованную функцию планирования Dsyn(S). Дисциплину планирования, унаследованную по отношению к синхронной дисциплине планирования Dsyn, будем обозначать через inh(Dsyn).

Монохронные системы и дисциплины планирования

Синхронная система S называется монохронной, если момент старта системы S равен нулю. Область определения монохронной системы – это неограниченный полуинтервал [0, +∞). Термин «монохронный» используется в связи с тем, что все монохронные системы имеют один общий момент старта, равный нулю.

Дисциплина планирования называется монохронной, если она определена на множестве мо- нохронных систем. Покажем, что каждая монохронная дисциплина планирования порождает синхронную дисциплину планирования. Чтобы определить построение синхронной дисциплины планирования исходя из монохронной, введем понятия сдвига синхронной системы и сдвига функции и установим их свойства.

Пусть S – синхронная система и s=start(S). Левым сдвигом системы S на число λ является система, состоящая из всех заданий вида (s–λ, L, T, I), где (s, L, T, I) – произвольное задание системы S. Правым сдвигом синхронной системы S на число λ является система, состоящая из всех заданий вида (s+λ, L, T, I). Левый и правый сдвиги на число λ обозначаются через Lλ и Rλ. Пусть f – функция, определенная на полуинтервале [s, +∞). Правым сдвигом функции f на число λ является определенная на полуинтервале [s+λ, +∞) функция g, задаваемая равенством g(t)=f(t–λ). Отображение, которое ставит в соответствие функции ее правый сдвиг на число λ, будем обозначать через rλ.

Состояние системы с планированием

Пусть (S, p) – система с планированием и срез slice(S, p)(α) не пуст. Монохронную систему Lα(slice(S, p)(α)) будем называть состоянием системы с планированием (S, p) на момент времени α и обозначать ее через state(S, p)(α).

Замечание. Срез может быть определен и являться при этом пустым множеством. В таком случае состояние не будет определенным.

Пусть Dmon – монохронная дисциплина пла- нирования. Дисциплина планирования, кото- рая синхронной системе S с моментом старта s ставит в соответствие функцию планирования rs(Dmon(Ls(S))), называется синхронной дисциплиной планирования, порожденной монохронной дисциплиной планирования Dmon. Синхронная дисциплина планирования, порожденная монохронной дисциплиной планирования Dmon, обозначается через [Dmon]. Таким образом, если S – синхронная система и start(S)=s, то [Dmon](S)=rs(Dmon(Ls(S))). Обозначим через Dom(Dmon) область определения монохронной дисциплины планирования Dmon. Тогда, по определению, областью определения дисциплины [Dmon] будет объединение правых сдвигов систем Dom(Dmon) на число s. Пусть Dmon – монохронная дисциплина планирования. Функция планирования p системы S удовлетворяет условию локальной определенности (по отношению к монохронной дисциплине планирования Dmon и для заданной системы S), если выполнены следующие два требования:

–      при любом α≥start(S) определен срез системы с планированием (S, p) на момент времени α;

–      если срез системы с планированием (S, p) на момент времени α не пуст, то функция [Dmon](slice(S, p)(α)) определена и функции p и [Dmon](slice(S, p)(α)) совпадают на любом стационарном полуинтервале [α, β) системы S (полуинтервал [α, b) называется стационарным, если среди точек α<τ

Если функция планирования p удовлетворяет требованию локальной определенности, значит, выполнено равенство p(α)=[Dmon](slice(S, p)(α))(α). С использованием понятия «состояние системы» второе требование из определения локально определенной функции планирования можно сформулировать так: если срез системы с планированием (S, p) на момент α не пуст, то при τ из любого стационарного полуинтервала [α, β) должно выполняться равенство p(τ)=Dmon(state(S, p)(α))(τ–α). Последнее равенство можно записать и в таком виде: p(τ)=rαDmon(state(S, p)(α))(τ).

Из теоремы об унаследованной функции планирования следует, что локально определенная функция планирования по отношению к монохронной дисциплине планирования Dmon является унаследованной функцией планирования по отношению к синхронной дисциплине планирования [Dmon]. Таким образом, все локально определенные функции планирования представляют собой унаследованные функции планирования по отношению к синхронной дисциплине планирования, порожденной монохронной дисциплиной планирования.

Теорема о локальной определенности

Введем понятие локально определенной дисциплины планирования. Пусть D – дисциплина планирования и W – подмножество области определения дисциплины планирования D. Дисциплина планирования D является локально определенной по отношению к монохронной дисциплине планирования Dmon на W, если для каждой системы S из W функция планирования D(S) удовлетворяет условию локальной определенности по отношению к Dmon. Введенное выше множество W будем называть областью локальной определенности дисциплины планирования D.

Определение локально определенной дисциплины планирования применительно к монохронной дисциплине планирования Dmon будет следующим: монохронная дисциплина является локально определенной на подмножестве W из Dom(Dmon), если выполнены такие требования:

–      при любом α≥0 и для любой монохронной системы S из W определен срез системы с планированием (S, Dmon(S)) на момент времени α;

–      если срез системы с планированием (S, Dmon(S)) на момент времени α не пуст, то функция планирования [Dmon](slice(S, p)(α)) определена и функции Dmon(S) и [Dmon](slice(S, p)(α)) совпадают на любом интервале (α, +∞).

Можно показать, что если монохронная дисциплина планирования Dmon является локально определенной, то порожденная ею синхронная дисциплина планирования [Dmon] также будет локально определенной. Ранее выявлено, что каждая локально определенная дисциплина планирования имеет вид inh([Dmon]), где Dmon – монохронная дисциплина планирования. Оказывается, для того чтобы дисциплина планирования inh([Dmon]) была локально определенной, достаточно, чтобы локально определенной была дисциплина планирования Dmon. Сформулируем соответствующую теорему.

Теорема (о локальной определенности унаследованной дисциплины планирования). Пусть Dmon – монохронная локально определенная дисциплина планирования, D – унаследованная дисциплина планирования по отношению к синхронной дисциплине планирования [Dmon] и S – система, принадлежащая области определения D. Тогда функция планирования D(S) удовлетворят условию локальной определенности.

В заключение отметим, что настоящая статья посвящена построению и изучению свойств дисциплин планирования. Вначале определяются унаследованные дисциплины планирования, получаемые из дисциплин планирования, определенных для систем с синхронным стартом. Унаследованные дисциплины планирования определяются аксиоматически как дисциплины, обладающие некоторым набором свойств. Формулируется теорема о существовании и единственности унаследованной дисциплины планирования.

В статье рассмотрены локально определенные дисциплины планирования. Это такие дисциплины, которые определяют планирование системы исключительно в соответствии с ее текущим состоянием вне зависимости от всей системы в целом или от выполненной части системы. Сформулирована структурная теорема, устанавливающая, что каждая локально определенная дисциплина планирования является унаследованной по отношению к локально определенной дисциплине планирования для синхронных систем.

Подробный обзор результатов в части планирования содержится в [2]. Результаты статьи могут быть использованы при создании приложений, функционирующих в среде разработанных в НИИСИ РАН операционных систем реального времени ос2000 [3] и ОС РВ Багет 3.0 [4].

Литература

1.     Грюнталь А.И. Планирование систем с асинхронным стартом // Информационные технологии и вычислительные системы. М.: Изд-во ИСА РАН. 2012. № 1. С. 32–51.

2.     Никифоров В.В. Выполнимость приложений реального времени на многоядерных процессорах: тр. СПИИРАН. СПб, 2009. Вып. 8. С. 255–284.

3.     Безруков В.Л., Годунов А.Н., Назаров П.Е., Солда- тов В.А., Хоменков И.И. Введение в ОС 2000 / Вопросы кибернетики. Информационная безопасность. Операционные системы реального времени. Базы данных. М.: Изд-во НИИСИ РАН, 1999. С. 3–13.

4.     Годунов А.Н. Операционная система реального времени Багет 3.0 // Программные продукты и системы. 2010. № 4. С. 15–19.

References

1.     Gryuntal A.I. Informatsionnye tekhnologii i vychislitelnye sistemy [Information technologies and computer systems]. Moscow, ISA RAN Publ., 2012, no. 1, pp. 32–51.

2.     Nikiforov V.V. Vypolnimost prilozheniy realnogo vremeni na mnogoyadernykh protsessorakh: tr. SPIIRAN [Satisfiability of real-time applications on multicore processors: proc. of SPIIRAS]. St. Petersburg, 2009, iss. 8, pp. 255–284.

3.     Bezrukov V.L., Godunov A.N., Nazarov P.Ye., Solda- tov V.A., Khomenkov I.I. Voprosy kibernetiki. Informatsionnaya bezopasnost. Operatsionnye sistemy realnogo vremeni. Bazy dan­nykh [Cybernetics issues. Information security. Real-time operation systems. Databases]. Moscow, NIISI RAN Publ., 1999, pp. 3–13.

4.     Godunov A.N. Operatsionnaya sistema realnogo vremeni Baget 3.0 [Real-time operating system baget 3.0]. Programmnye produkty i sistemy [Software & Systems]. 2010, no. 4, pp. 15–19.N,


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=3660
Версия для печати
Выпуск в формате PDF (7.95Мб)
Скачать обложку в формате PDF (1.45Мб)
Статья опубликована в выпуске журнала № 4 за 2013 год. [ на стр. 67-73 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: