WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 || 4 |

Существует множество компиляторов для языков высокого уровня, рассчитанных на работу в среде MS-DOS. В силу этих соображений, выбор был остановлен на MS-DOS и сосредоточены усилия на создании приемлемой многозадачной оболочки реального времени.

Управляющую программу удалось реализовать в виде многозадачной надстройки над операционной системой MS-DOS версии 3.30 и выше на основе многозадачной оболочки реального времени CTask-RT, прототипом которой послужил распространяемый бесплатно пакет Т.Вагнера. CTask-RT позволяет создать программную среду, использующую многозадачные элементы BIOS IBM PC/AT, обойти барьеры нереентерабельности MS-DOS и даёт возможность работать совместно с резидентными (TSR) программами и под управлением оболочки MS-Windows.

Следует заметить, что написанная Управляющая программа достаточно мобильна, т.е. может быть перенесена на другие операционные системы и машины, поскольку почти 90% кода программы написано на языке Си.

Управляющая программа является составной частью исполняемого EXE-модуля РВ-программы и выполняет следующие функции:

• приём, хранение и обработка поступающей извне информации (кадров данных);

• реакция на внешние апериодические сигналы;

• исполнение команд, вводимых с клавиатуры консоли;

• переключение между условными и простыми заданиями в соответствии со значениями системного вектора условий;

• запуск процессора согласно директивным срокам и приоритетам;

• обмен данными между процессами;

• действия по завершению работы процесса.

Структура управляющей программы. Логически управляющую программу можно условно разделить на следующие части:

• интерпретатор команд;

• диспетчер (ядро);

• монитор данных;

• драйверы внешних устройств.

Интерпретатор команд обеспечивает интерфейс между оператором и системой РВ. Он представляет собой систему меню, работа с которой возможна как с помощью клавиатуры, так и посредством «мыши».

Примерная схема сеанса работы интерпретатора управляющей программы может быть следующей. После запуска EXE-модуля РВ-программы начинает работать интерпретатор команд. На экране появляется главное меню. Выбор из меню осуществляется либо нажатием «горячей» клавиши подсвеченной буквы, либо мышью. Сначала доступны для выбора поля StartUp и Quit, что соответствует запуску и выходу из системы. После выбора StartUp появляется подменю с полями Overview, Help, Info, Install & Run, посредством которых можно получить дополнительную информацию по системе или начать работу.

Функция диспетчера – активизация и запуск на счёт процессов в соответствии с приоритетами, которые определяются блоком ГСМР при составлении расписания.

Множество процессов РВ-программы состоит из процессов реакции на внешнее апериодическое сообщение (по одному на каждое УЗ), основных процессов ПЗ и фоновых процессов УЗ.

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

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

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

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

В главе 5 описывается генерация кода, сборка и запуск программного комплекса «СРВ-Конструктор».

Ранее уже упоминалось, что различают подготовительный этап использования «СРВ-Конструктора», по окончании которого генерируется готовая к выполнению прикладная РВ-программы, и этап работы в самом режиме реального времени полученной программы.

Для запуска подготовительного этапа от пользователя требуются:

– прикладные модули, написанные на языках программирования C, FORTRAN, PASCAL, ASSEMBLER (в формате компиляторов фирмы Microsoft v. 6.0;

– задание на обработку информации в реальном времени, написанное на входном языке СРВ-Конструктора.

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

Общая схема предварительного этапа показана на рис. 2..

Предварительный этап работы системы «СРВ-Конструктор» включает последовательный вызов следующих обрабатывающих программных комплексов:

– компилятора для трансляции исходного текста РВ-программы; формат обращения: lang <имя_РВ-программы.rts>;

Задание на обработ- ку РВ-программы Прикладная СРВ-Конструктор СРВ Прикладные модули Рис.2. Последовательность проектирования ВСРВ с помощью СРВ-Конструктора.

– программы вывода диагностики и сообщений об ошибках при компиляции, помещаемых компилятором в файл <имя_РВ-программы.lst> (предусмотрен анализ более 70 типов ошибок); формат обращения: spl;

– программы генерации сетевых моделей и расписаний; формат обращения: _gsm_gr;

– программы генерации кодов; формат обращения: _cd_gnr.

Далее осуществляется трансляция полученных модулей с помощью компилятора фирмы Microsoft.C (6.0) и сборка готового модуля прикладной программы реального времени с помощью стандартного компоновщика связей фирмы Microsoft link. Файл с расширением <имя_РВ-программы.lrf>, используемый при работе данного компоновщика (включает перечень предназначенных для сборки файлов), создаётся автоматически.

Для выполнения расписания может понадобиться создание копий некоторых прикладных модулей пользователя. Список пар имён таких модулей (имеющееся имя и то, которое необходимо создать) выдаётся в файл «_cg_user.lst». Для успешной работы компилятора необходим также ряд вспомогательных файлов.

Блок генерации кода выполняет следующие функции:

1. Формирует на языке Си и записывает в текущий каталог исходные тексты получившейся программы.

2. Создаёт ряд вспомогательных файлов для последующих определённых действий пользователя, компиляции и редактирования связей.

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

Постановка задачи для случая процессоров одинаковой производительности. Имеется M независимых заданий и N идентичных процессоров, на каждом из которых может выполняться одновременно не более одного задания. В фиксированный момент времени каждое задание выполняется не более чем одним процессором. Задания выполняются без прерываний и переключений с одного процессора на другой. Для каждого задания i известна длительность ti его выполнения. Необходимо определить такое распределение заданий по процессорам, чтобы время выполнения всей совокупности заданий (от начала первого до завершения последнего) было минимальным.

Эту задачу можно описать следующим образом: T min, M j = 1, N, t xij T, i i= N xij = 1, i = 1, М, (1) j= xij = {0,1}, i = 1, M, j = 1, N, где T - время выполнения всей совокупности заданий; xij = 1, если i-е задание распределено на j-й процессор, xij = 0 в противном случае.

Постановка задачи для случая процессоров различной производительности. Имеется M независимых заданий и N процессоров, которые могут отличаться производительностью. На каждом процессоре одновременно может выполняться не более одного задания. В фиксированный момент времени каждое задание выполняется не более чем одним процессором. Задания выполняются без прерываний и переключений с одного процессора на другой. Объём работы по выполнению задания i равен Qi. Производительность процессора j равна Sj. Таким образом, если i-е задание выполняется процессором j в течение интервала tij, то Qi = Sj tij.

Будем считать, что задания упорядочены по не возрастанию объёмов их работ: Q1 Q2 … QM, а процессоры упорядочены по не возрастанию их производительностей: S1 S2 … SN.

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

Эту задачу можно записать следующим образом: T min, M Qi j = 1, N, S xij T, i=j N xij = 1, i = 1, М, (2), j= xij = {0,1}, i = 1, M, j = 1, N, где T - время выполнения всей совокупности заданий; xij = 1, если i-е задание распределено на j-й процессор, xij = 0 в противном случае.

Обе сформулированные выше задачи, как показано в литературе, являются NP-трудными в сильном смысле.

Приводится обзор существующих методов решения поставленных задачи. Основное внимание уделено следующим известным методам:

• алгоритмы случайного поиска (ненаправленного, направленного, с самообучением);

• алгоритмы детерминированной коррекции расписаний;

• алгоритмы имитации отжига;

• генетические алгоритмы;

• алгоритмы агрегирования.

На основе обзора сделан вывод, что с учётом особенностей задач целесообразно совершенствовать методики построения расписаний по всем указанным направлениям. В силу научных интересов автор сосредоточил внимание на новых эвристических алгоритмах.

В седьмой главе подробно изложены предлагаемые эвристические алгоритмы.

Решение задачи 1 (для случая одинаковых процессоров).

При работе эвристического алгоритма вычисляется идеальная оценка M t* = ( ) / N времени завершения всей совокупности заданий, а также её каt i i=либрованное значение t. Под калибровкой понимается увеличение величины t* на некоторое число процентов, причём алгоритм запускается с разными значениями калибровки и выбирается лучшее достигнутое для рассматриваемого набора входных данных решение.

Эвристический алгоритм 1.

а) Отсортировать задания по не возрастанию длительностей, т.е. будет выполняться соотношение ti ti +1, i = 1,..., M - 1.

б) Вычислить величины t* и t.

в) Распределять на каждый процессор j, начиная с первого, нераспределенные ранее задания до тех пор, пока суммарная длительность заданий на каждом процессоре не будет превышать величины t. При этом сначала максимально нагружается текущий выбранный процессор, а лишь затем происходит переход к загрузке заданий следующего. Если в какой-то момент при попытке распределить очередное задание на процессор происходит превышение величины t, то сначала производится попытка распределения на тот же процессор оставшихся нераспределённых заданий вплоть до наименее трудоёмкого (также с не превышением величины t ) и только потом – переход на загрузку следующего процессора (для каждого j = 1,..., N определять M xij = 1 до тех пор, пока xijti < t для данного j).

i =г) Определить номер k* процессора, для которого суммарная длительность заданий, назначенных на него, минимальна, т.е.

M k* = arg( min ti ) (2) x ij k =1,N i =д) Распределить на этот процессор самое длинное из ранее не распределённых заданий.

е) Повторять выполнение пунктов (г) и (д) до тех пор, пока не все задания распределены.

Результаты ряда экспериментов с эвристическим алгоритмом 1 приведены на рис. 3.

РядРяд1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 M/N (от 5,15 до 7,68) Рис. 3. Результаты ряда экспериментов с эвристическим алгоритмом Ряд 1 () – эвристический алгоритм 1 лучше, чем «жадный».

Ряд 2 () – результаты совпадают.

Контрольные алгоритмы. Для сравнительного контроля качества получаемых предложенными алгоритмами решений использован известный «жадный» алгоритм распределения заданий. Как уже упоминалось, он состо Число опытов ит в том, что распределение осуществляется, начиная с самого трудоёмкого из необработанных заданий, на наименее загруженный на момент распределения процессор.

Для оценки качества получаемых решений при малых размерностях задачи использовался и метод полного перебора вариантов распределения заданий по процессорам. Этот алгоритм хорошо известен и не требуется его описание в подробностях. Оценка его трудоёмкости составляет величину порядка O(NM).

Таким образом, оценки трудоёмкостей обсуждаемых эвристических алгоритмов определяются трудоёмкостью предварительной сортировки и, в зависимости от выбранного метода, составляют либо O(M2), либо O(M log M), соответственно. Оба вида сортировки используются в связи с тем, что при малых M (M 14), трудоёмкость сортировки методом пузырька оказывается ниже, чем сортировки разделением-слиянием.

Решение задачи 2 (для случая различных процессоров).

Описание жадного алгоритма.

1. Пусть Lj – длина временного интервала загруженности j-го процессора.

2. Положить Lj = 0 j = 1, N.

3. Назначить первое задание на первый процессор и L1 := Q1 / S1.

4. Для каждого i = 2, M выполнять шаги 5-7.

5. Положить R = max(L1, L2,…, L,(Lj + Qi / S ), Lj +1,...,LN ) для j j -1 j j = 1, N 6. Вычислить R = min R.

j0 j j =1,N 7. Назначить задание i на процессор j0: Lj0 := Lj0 + Qi / S.

jОписание эвристического алгоритма 2.

При работе эвристического алгоритма вычисляется нижняя оценка M N t* = ( ) / S времени завершения всей совокупности заданий, а также Q i j i =1 j =её калиброванное значение t. Под калибровкой понимается увеличение величины t* на некоторое значение, причём алгоритм запускается с разными значениями калибровки и выбирается лучшее достигнутое для данного набора входных данных решение. В качестве значения верхней оценки TG длины расписания используется время выполнения всей совокупности заданий, полученное «жадным» алгоритмом для соответствующих данных.

Pages:     | 1 | 2 || 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»