Особенности организации управления ППП                    с входным языком командного типа

 

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

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

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

Если ППП будет использоваться только в пакетном режиме, методы интерпретации и компиляции внешне не различимы для пользователя.

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

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

Блок-схема алгоритма работы ведущего модуля при интерпретации команд приведена на рис. 3.1.

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

В ППП, предназначенном для решения расчетных задач с использованием некоторого набора обрабатывающих программных модулей, управляющий код может быть записан в форме управляющего вектора U = (u₁, u₂, …, u_m ), каждая компонента которого содержит имя (код, номер) обрабатывающего или обслуживающего модуля и информацию о списке передаваемых в этот модуль фактических параметров.

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

 

 

	Рис. 3.1 - Блок-схема алгоритма работы ведущего модуля           в режиме интерпретации команд

 

	Рис. 3.2 - Блок-схема алгоритма работы ведущего модуля в режиме компиляции команд: 1 – режим компиляции; 2 – режим выполнения готовой программы; 3 – отказ от работы

 

 

Планирование вычислительного процесса в ППП

 

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

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

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

Планирование вычислительного процесса легко формализовать, если использовать понятие бинарного вектора состояния МПО (2.4) и бинарных матриц функциональных связей.

Совокупность функциональных связей в модели предметной области пакета можно представить матрицами Т и R, имеющими по m строк (m - число функциональных связей) и по n столбцов (n - число данных). Элементы матрицы T определяются по формуле:

Аналогично, элементы матрицы R определяются по формуле:

Таким образом, с помощью матрицы T описывается состояние входных данных обрабатывающих модулей, а с помощью матрицы R – выходных данных.

 

Пример. Пусть модель предметной области содержит пять обрабатывающих модулей (m=5) и шесть данных в информационной базе (n=6). Функциональные связи представлены в таблице 3.1.

 

Таблица 3.1 - Функциональные связи (обрабатывающие модули)

Имя модуля	Входные данные	Выходные данные
М1 М2 М3 М4 М5	a, b a, b c, b b, e a, d	c d e x x

 

Тогда матрицы T и R имеют вид:

.

 

Теперь, применяя логические операции к вектору-строке S и строкам матриц T_i и R_i (i=1…m), состоящим из n бинарных элементов, можем записать условие выполнимости i-ого обрабатывающего модуля и условие его эффективности. Напомним, что обрабатывающий модуль называется выполнимым (в данном состоянии S_k модели предметной области), если известны все его входные значения. Выполнимый модуль называется эффективным (в данном состоянии S_k модели предметной области), если его вызов переводит модель предметной области в новое состояние S_k+1¹S_k.

Условие выполнимости модуля:

,

условие эффективности модуля:

.

Здесь  - знак операции конъюнкции (логическое «И»),  - знак операции отрицания.

Если обозначить вектор исходного состояния S₀, а требования к конечному состоянию определить бинарным вектором Z , компоненты которого имеют вид:

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

.

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

Алгоритм можно описать так.

Этап 1. Очистить формируемый управляющий вектор U , установить его текущую длину К _U=0, установить вектор состояния МПО в начальное положение: S_k = S₀.

Этап 2. Проверить вектор состояния МПО на достижение конечной цели, т.е. на выполнение условия .

Этап 3. Если , то начать цикл по перебору функциональных связей, т.е. по строкам матриц T и R (i=1…m).

При этом если будет выполнено условие:

( ) ( ), 

т.е. I -ый модуль выполним и эффективен, то:

1) включить этот модуль в очередную позицию управляющего вектора (например, своим номером: К _U = К _U + 1, U (К _U ) = i );

2) преобразовать текущее состояние модели предметной области[6]:

;

3) проверить полученный вектор состояния МПО на достижение конечной цели, т.е. на выполнение условия . Если , то получено решение задачи, если нет – перебор продолжается.

 

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

Продолжим рассмотрение предыдущего примера.

Пусть исходное состояние МПО S₀ = (1 1 0 0 0 0), т.е. известны данные a , b . Требуется сформировать управляющий вектор для вычисления х, т.е. Z = (0 0 0 0 0 1).

 

1) Проверка на достижение конечной цели:

Цикл продолжается, т.к. результат операции не совпадает с вектором конечного состояния

 

2) Проверка первого модуля на выполнимость:

Модуль выполним, т.к. результат операции совпадает с первой строкой матрицы Т.

 

3) Проверка первого модуля на эффективность:

Модуль эффективен, т.к. результат операции ненулевой.

 

4) Модуль М1 включается в управляющий вектор, и вектор состояния МПО преобразовывается:

S1 = (1 1 1 0 0 0) – вектор нового состояния МПО

 

5) Снова происходит проверка на конец цикла (шаг 1), проверка на выполнимость и эффективность модуля М2 и т.д.

В результате будет сформирован управляющий вектор             U₁ = (M1, M2, M3, M4).

В рассмотренном примере легко можно увидеть, что существуют и другие управляющие векторы, реализующие поставленную задачу, а именно U₂ = (M1, M3, M5), U₃ = (M2, M5). Когда управляющий вектор не единственный, то можно ставить задачу о выборе оптимального (в некотором смысле) управляющего вектора.

Задача оптимального планирования вычислительного процесса формулируется следующим образом: найти управляющий вектор U^*, такой, что

,

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

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

 

 

	Рис. 3.3 - Граф переходов

 

 

Контрольные вопросы

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

2. Что такое входной язык пакета? Охарактеризуйте входные языки современных ППП (на примере известных вам пакетов).

3. В чем отличие метода компиляции от метода интерпретации программы на входном языке? Какие особенности организации управления при реализации этих методов?

4. Что понимают под планированием вычислительного процесса в ППП?

5. Пусть данное состояние МПО описывается вектором S={0,1,1,0,0,0,1}. Будет ли выполнимым обрабатывающий модуль, если его строка в матрице Т имеет вид: а) T_i = {1,1,1,1,0,0,0}; б)       T_i = {0,1,0,1,0,0,1}?

6. Пусть данное состояние МПО описывается вектором S={0,1,1,0,0,0,1}. Будет ли эффективным обрабатывающий модуль, если его строка в матрице R имеет вид: а) R_i = {0,1,0,0,0,0,1}; б)      R_i = {0,0,0,1,0,0,1}?