На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

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

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

2
Ожидается:
17 Июня 2024

Планирование заданий с синхронным стартом

Planning of tasks with synchronous start
Статья опубликована в выпуске журнала № 4 за 2010 год.
Аннотация:Рассматривается формализованная модель исполнения произвольной многозадачной системы реального времени с синхронным стартом. Для таких систем формулируются необходимые и достаточные условия, выполнение которых обеспечивает своевременное исполнение всех задач. Приводится соответствующий алгоритм планирования.
Abstract:The paper deals with a formal execution model of multitask real time systems. Necessary and sufficient conditions that guarantees in time task completion of an arbitrary system with synchronous start are formulated. Corresponding planning algorithm is given.
Авторы: Грюнталь А.И. (grntl@niisi.msk.ru) - НИИСИ РАН, г. Москва, г. Москва, Россия, кандидат физико-математических наук
Ключевые слова: синхронный старт, планирование, многозадачность, программное обеспечение, реальное время
Keywords: synchronous start, planning, multitasking, the software, real time
Количество просмотров: 13376
Версия для печати
Выпуск в формате PDF (6.26Мб)
Скачать обложку в формате PDF (1.28Мб)

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

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

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

Приводимый в статье подход может применяться в вычислительных системах, создаваемых на базе разработанной в НИИСИ РАН операци- онной системы реального времени ос2000 [Годунов А.Н. и др.].

Модель многозадачной системы

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

Заданием назовем тройку положительных чисел (t, L, T), удовлетворяющих неравенству L≤T. Число t назовем началом задания (или моментом его старта), L – ресурсной длительностью задания, T – максимально допустимой длительностью задания исполнения.

Задание интерпретируется как исполняемая на ЭВМ задача, возникшая и готовая к исполнению в момент t. Ресурсная длительность задания L – это время, необходимое для выполнения задачи в монопольном режиме, то есть когда процессор занят только ее выполнением.

При многозадачном режиме выполнение задач прерывается другими задачами, функциями обработки прерываний, ожиданием ресурсов и др. Поэтому, даже если задача фактически стартовала сразу в момент своего возникновения, ее выполнение может завершиться в момент t1>t+L. Максимальная длительность задания T – это максимальное время, за которое задача должна быть выполнена.

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

Системой назовем такую конечную последовательность заданий (t1, L1, T1), … , (tN, LN, TN), для которой выполняются следующие неравенства: t1≤t2, t2≤t3, … , tN-1≤tN. Другими словами, начала составляющих систему заданий должны образовывать неубывающую последовательность. Число t1 будем считать началом (или моментом старта) системы.

Полуинтервалом [t1, t2) назовем множество чисел t, удовлетворяющих неравенствам t1≤t

Пусть дан полуинтервал [a, b). Разбиением полуинтервала назовем такую последовательность полуинтервалов [ai, bi), i=1, ..., K, при которой a=a1, bi-1=ai, bK=b. Определение справедливо и в случае, когда b=+∞. Если t1 – момент старта системы, то интервал [t1, +∞) будем называть интервалом определения системы.

Пусть дана система S={(ti, Li, Ti)}, i=1, …, N. Функцией планирования назовем произвольную кусочно-постоянную функцию p(t) со следующими свойствами:

1) функция p(t) определена на полуинтервале t1 ≤ t < +∞;

2) функция p(t) принимает значения во множестве 0, 1, …, N;

3) прообраз значения функции p(t) для любого i=0, 1, ..., N представляет собой объединение конечного количества несмежных полуинтервалов; при i≠0 все полуинтервалы должны быть ограниченными;

4) для каждого i≠0 сумма длин полуинтервалов, составляющих прообраз функции p(t) для значения i, равна Li – ресурсной длительности задания с номером i.

Интерпретация функции p(t) следующая. Значение p(t) – это номер задания, выполняемого в момент t. Нулевое значение p(t) означает, что ни одно из заданий в момент t не выполняется.

Определение функции планирования нуждается в формальной проверке корректности свойства 4, поскольку набор несмежных полуинтервалов, существование которых требуется в п. 3, может быть определен неоднозначно, а значит, и сумма их длин может изменяться от одного набора к другому.

Заметим, что для каждого i объединение несмежных полуинтервалов, рассматриваемых как множество, определено однозначно. Поэтому для доказательства корректности определения надо установить истинность следующей леммы.

Лемма (о единственности представления). Пусть дано множество M в виде объединения конечного количества несмежных полуинтервалов. Тогда такое представление единственно.

Доказательство леммы опускается.

Пусть даны функция p(t), обладающая свойствами 1 и 2, и два смежных интервала, принадлежащих области определения функции p(t). Будем считать, что функция p(t) удовлетворяет свойству перемены значения на заданных смежных полуинтервалах, если значения p(t) на этих полуинтервалах различны. Также положим, что функция p(t) удовлетворяет свойству перемены значения на разбиении полуинтервала, если для любых двух смежных полуинтервалов из разбиения выполняется свойство перемены значения.

Полуинтервалы, существование которых утверждается в пункте 3 определения функции планирования, назовем характеристическими полуинтервалами функции планирования, соответствующими значению i. Из леммы о единственности представления следует, что множество характеристических полуинтервалов, соответствующих значению i, определено однозначно. Набор всех характеристических полуинтервалов, соответствующих всем значениям функции планирования, назовем характеристическим разбиением функции планирования, а сами полуинтервалы – характеристическими полуинтервалами функции планирования.

Заметим, что определение характеристических интервалов корректно и в случае функции, для которой выполнены только первые три свойства из определения функции планирования.

Очевидно, разбиение функции планирования содержит не меньше чем N+1 полуинтервал, где N – количество заданий в системе. Для заданной системы  характеристическое разбиение полностью определяется функцией планирования. Поскольку значения функции планирования в пределах одного характеристического полуинтервала не меняются, под значением функции планирования на характеристическом полуинтервале будем понимать значение функции планирования в произвольной точке характеристического полуинтервала. Если I – полуинтервал, то это значение будем обозначать через p(I).

Левые границы полуинтервалов, образующих характеристическое разбиение, назовем точками переключения планирования (функции планирования). Количество точек переключения планирования равно количеству характеристических полуинтервалов.

Пусть даны система и функция планирования. Для задания с номером i через Fi обозначим правую границу самого правого характеристического полуинтервала, соответствующего значению i. Число Fi назовем окончанием (или моментом завершения) задания с номером i.

Функция планирования системы S={(ti, Li, Ti)} называется разрешающей, если для каждого входящего в систему задания момент его завершения не превосходит максимально допустимую длительность задания, то есть, если выполняется неравенство Fi≤ti+Ti. Система S называется разрешимой, если в ней существует разрешающая функция планирования.

Теоремы о системах c синхронным стартом

Определим критерии разрешимости системы и методы построения функций планирования, разрешающих систему. Рассмотрим только системы с синхронным стартом, или синхронные системы, то есть такие системы, все задания которых имеют общий момент старта. Это необходимый шаг при рассмотрении свойств систем общего вида. Итак, система S={(ti, Li, Ti)} является синхронной, если совпадают начала всех составляющих систему заданий, то есть, если t1 = … = tN. Общее начало заданий для синхронных систем обозначим через t0.

Дадим определение последовательной функции планирования. Для заданной синхронной системы S и функции планирования p(t) сегментом назовем непрерывную последовательность  полуинтервалов (s1, ..., sK), входящих в характеристическое разбиение функции p(t). Точнее, сегмент – это подмножество, состоящее из (различных) полуинтервалов характеристического разбиения, объединение которых в теоретико-множественном смысле – снова полуинтервал. Количество составляющих сегмент полуинтервалов назовем комбинаторной длиной сегмента.

Сегментом разрыва будем называть такой сегмент s1, ..., sK, K≥3, в котором для некого i из области значений функции p(t) выполняются следующие утверждения:

p(s1)=p(sK)=i;

p(sj)≠i при j=2, ..., K-1.

Функция планирования является последовательной, если у нее отсутствуют сегменты разрыва, то есть образующие систему задачи выполняются последовательно: сначала полностью выполняется одно задание, потом другое и т.д. Ясно, что функция планирования последовательная тогда и только тогда, когда принимает отличное от нуля значение ровно на N полуинтервалах характеристического разбиения. То же утверждение можно сформулировать следующим образом: функция планирования тогда и только тогда последовательная, когда у нее ровно N+1 точка переключения планирования.

Теорема 1 (о существовании последовательного планирования). Пусть дана синхронная система. Если эта система разрешима, то существует последовательная функция планирования, разрешающая ее.

Доказательство. (Приведем только алгоритм построения последовательной функции планирования; проверка выполнения требований, предъявляемых к функции планирования, опускается.)

Пусть S – разрешимая синхронная система, определенная на полуинтервале [t0, +∞); p(t) – разрешающая эту систему функция планирования. Допустим, что функция p(t) не является последовательной. Тогда у нее существуют сегменты разрыва. Пусть Seg=(u1, ..., uK) – сегмент разрыва с наименьшей комбинаторной длиной (если их несколько, возьмем любой из них). Так как Seg – сегмент разрыва, то p(u1)=p(uK). Так как комбинаторная длина сегмента минимальна, значения функции p(t) на всех сегментах u2, ..., uK-1 попарно различны и отличны от p(u1).

Через l1, ..., lK обозначим левые границы составляющих сегмент разрыва полуинтервалов, а через r1, ..., rK – правые границы; Iseg – полуинтервал [l1, rK); Lj – длина rj–lj полуинтервала uj. Очевидно, что Iseg является теоретико-множест­венным объединением полуинтервалов u1, ..., uK, а количество точек переключения планирования функции p(t), принадлежащих Iseg, равно K.

Через (v1, ..., vL) обозначим полуинтервалы характеристического разбиения функции p(t), находящиеся левее Iseg, а через (w1, ..., wR) – полуинтервалы, находящиеся правее Iseg. Очевидно, что полуинтервал wR неограниченный. Объединение полуинтервалов v1, ..., vL обозначим через Lseg, объединение полуинтервалов w1, ..., wR – через Rseg.

Количество точек переключения планирования функции p(t) на Lseg, Iseg и Rseg равно соответственно L, K и R. Общее количество точек переключения планирования функции p(t) равно B=L+K+R. Естественно, возможен случай, когда L=0 или R=0. При R=0 полуинтервал uK неограниченный.

Построим новую функцию планирования p1(t) синхронной системы S, количество точек переключения планирования которой будет меньше B. На полуинтервалах Lseg и Rseg положим p1(t) равной p(t). Для задания p1(t) построим разбиение (z1, ..., zK-1) на Iseg и определим p1(t) на каждом из полуинтервалов этого разбиения.

При i=1, ..., K-2 положим zi=[li+1–L1, ri+1–L1). Пусть zK-1=[lK-L1, rK). Легко проверить, что (z1, ..., zK-1) образуют разбиение полуинтервала Iseg.

При i=1, ..., K-2 значение функции p1(t) на zi примем равным p(ui+1), значение функции p1(t) на zK-1 – равным p(uK). Поскольку объединение полуинтервалов z1, ..., zK-1 равно Iseg, функция p1(t) определена на всей области определения системы S.

Можно проверить, что построенная функция p1(t) является разрешающей функцией планирования системы S, а количество точек переключения этой функции меньше количества точек переключения функции p(t).

Если функция p1(t) не является последовательной, то повторно применим к ней описанную процедуру и получим функцию планирования, у которой количество точек переключения будет еще на единицу меньше. Так будем поступать до тех пор, пока у полученной функции планирования не станет ровно N+1 точка переключения планирования, а значит, функция последовательная. Теорема 1 доказана.

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

Опишем монотонный алгоритм планирования. Пусть дана синхронная система S={(t0, Li, Ti)}. Монотонный алгоритм планирования состоит в том, что сначала выполняется задание с наименьшей максимально допустимой длительностью, потом следующее за ним, и так далее, пока не будут выполнены все задания.

Сформулируем определение монотонного алгоритма в терминах функции планирования. Пусть φ(i) – такое взаимно-однозначное отображение первых N натуральных чисел на себя, что φ(a)<φ(b) тогда и только тогда, когда либо Ta

Обозначим через ψ(i) отображение, обратное φ(i). Определим последовательность полуинтервалов u1, ..., uN следующим образом. Примем u1=[t0, t0+Lψ(1)). Пусть теперь построены u1, ..., uK для некоторого K, 1≤K

Очевидно, что объединение построенных полуинтервалов является полуинтервалом (обозначим его через Iseg), а последовательность u1, ..., uN образует разбиение этого полуинтервала. Определим монотонную функцию планирования p(t).

Пусть t принадлежит Iseg. Тогда t принадлежит в точности одному полуинтервалу ui. Примем p(t)=ψ(i). Обозначим через r правую границу Iseg. При значениях t≥r примем p(t)=0.

Лемма. Построенная функция p(t) является функцией планирования системы S, разбиение (u1, ..., uN, u+∞) – характеристическим разбиением, соответствующим функции планирования p(t). (Доказательство леммы опускается.)

Теорема 2 (о монотонном планировании). Если синхронная система разрешима, то монотонная функция планирования разрешающая.

Доказательство. Опишем конструкцию, приводящую к построению монотонной функции планирования. Пусть система S={(t0, Li, Ti)} разрешима. В силу теоремы 1 для системы S существует последовательная функция планирования p(t). Пусть (z1, ..., zN, z+∞) – характеристическое разбиение, соответствующее функции p(t).

Пару характеристических интервалов из разбиения (z1, ..., zN) c номерами a и b назовем неупорядоченной парой, если a<φ(p(za)). Количество неупорядоченных пар характеристических интервалов назовем дефектом функции планирования (напомним, что характеристически полуинтервалы однозначно определяются функцией планирования). Обозначать дефект будем через δ(S, p). Очевидно, что функция планирования монотонная тогда и только тогда, когда δ(S, p)=0. Если образующие неупорядоченную пару полуинтервалы смежные, такую неупорядоченную пару назовем смежной.

Лемма (о существовании смежных неупорядоченных пар). Если дефект функции планирования положительный, то существует по крайней мере одна смежная неупорядоченная пара. (Доказательство опускается.)

Предположим, что δ(S, p)>0. Тогда построим последовательную функцию планирования p1(t), дефект которой меньше дефекта p(t). Рассмотрим смежную неупорядоченную пару характеристических полуинтервалов. Допустим, что этo пара zj=[lj, rj), zj+1=[lj+1, rj+1). То, что смежная пара неупорядоченная, означает следующее: Tp(zj+1)≤ ≤Tp(zj). Заменим пару полуинтервалов zj, zj+1 на пару полуинтервалов yj, yj+1. Пусть lj – левая граница zj, rj+1 – правая граница zj+1.

Пусть Li обозначает ресурсную длительность задания с номером i. Тогда примем yj=[lj, lj+Lq) и yj+1=[lj+Lq, r(j+1)), где q=p(zj+1). Очевидно, что полуинтервалы yj и yj+1 смежные, и их объединение совпадает с объединением zj и zj+1. На yj и yj+1 определим p1(t), полагая p1(yj)=p(zj+1) и p1(yj+1)= =p(zj). В остальных точках определения системы S положим p1(t)=p(t). Можно проверить, что p1(t) – последовательная разрешающая функция планирования системы S, такая, что δ(S, p1)=δ(S, p)–1.

Если функция p1(t) немонотонная, то, снова применив процедуру уменьшения дефекта, получим новую функцию планирования с еще меньшим дефектом. И так далее, до тех пор, пока дефект не станет нулевым, а функция планирования монотонной. Теорема о монотонном планировании доказана.

Критерий разрешимости синхронных систем

Пусть дана синхронная система S={(t0, Li, Ti)}, i=1, …, N. Предположим нумерацию заданий системы такой, что Ti≤Ti+1. Из теоремы о монотонном планировании следует, что система разрешима тогда и только тогда, когда она монотонно разрешима. Отсюда вытекает следующий критерий разрешимости: система разрешима тогда и только тогда, когда для каждого k=1, …, N выполняется неравенство L1+…+Lk≤Tk.

Приведенный критерий представляет конструктивный способ проверки разрешимости конкретной системы с синхронным стартом.

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

Дальнейшая работа связана с анализом разрешимости произвольных несинхронных систем.

Литература

Годунов А.Н. [и др.]. Введение в ос2000 // Вопросы кибернетики. Информационная безопасность. Операционные системы реального времени. Базы данных [под. ред. В.Б. Бетелина]. М.: НСК РАН, 1999. С. 76–106.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=2604&lang=&lang=&like=1
Версия для печати
Выпуск в формате PDF (6.26Мб)
Скачать обложку в формате PDF (1.28Мб)
Статья опубликована в выпуске журнала № 4 за 2010 год.

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