Значение уровня языка

В течение последних десятилетий значительная доля усилий специалистов в области языков программирования была направлена на разработку и реализацию новых языков и часто при этом выполнялось усовершенствование ранее существовавших языков Но из-за отсутствия количественного измерения вывод о реальном улучшении языка был весьма субъективным Без принятия гипотезы соотносящей конкретный язык с мысленной работой по его использованию нельзя с уверенностью сказать положительно или отрицательно его введение Объединяя уравнение (47) с уравнением работы получаем что число элементарных мысленных различений требуемых для написания некоторой программы должно подчиняться закону обратных квадратов относительно уровня языка или

Е = V^*3/² (48)

Из соотношений Е = V²/V^* и V = V^*/L следует что Е = V^*/L² откуда при помощи равенства L = /V^* выводим (48) Для небольшой выборки программ написанных на двух языках можно определить средние значения  и с их помощью найти сравнительную трудоемкость Так выигрыш во времени программирования при переходе от языка низкого уровня ₁ к языку высокого уровня ₂ определяется соотношением

ΔT/T = (T₁ - T₂) / T₁ = 1 - T₂ / T₁ = 1 - (₁)² / (₂)² (4.9)

Тогда по данным табл.6 при переходе от Ассемблера к Фортрану выигрыш во времени составит 40% , от Ассемблера к ПЛ-1 - 67%.

Важность понятия уровня языка подтверждается также из уравнения (48) следующими обстоятельствами Поскольку потенциальный объем V^* и среднее значение  должны быть известны или вычислимы сразу после определения программистского проекта и выбора языка это дает рациональную основу для планирования времени программирования

С другой стороны, подставляя в (4.7) выражение для L из (3.2), получим

 = (V^*)² / V (4.10)

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

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

Метрика числа ошибок в программе.

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

Время, требуемое на разработку программы, характеризуется числом элементарных мыс­ленных различений Е. Следовательно, число моментов, в которые можно сделать ошибочное различение, также определяется значением Е или связанным с ним значением объема программы V. По утверждениям психолога Джорджа Миллера (закон “7±2”) мозг человека может в своей “сверхбыстрой” памяти обрабатывать пять “объектов” одновременно (т. е. получать из них результат). Представив эту способность мозга как Е_крит, получим ее программное значение.

Пусть каждый объект так же, как и результат, соответствует единице уникальных операндов в потенциальном языке, т. е. ₂* = 6. С помощью равенств ₁* = 2 и

V* = (₁* + ₂*) log₂ (₁* + ₂*) (4.11)

получаем

V*_крит = (2 + 6)log₂(2 + 6) = 24 (4.12)

Далее из уравнения (4.8) имеем

E = (V*)³/² ,

а из табл. 6 получаем для английского языка = 2,16. Тогда для описания программы на уровне английского языка приходим к следующему выводу

Е_крит = (24)³ * (2,16)² = 3000 (4.13)

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

В = Е/Ео, (4.14)

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

Однако уровень программы L, собственно, и является мерой такой избыточности. Заметим, что только в потенциальном языке, на котором любая программа может быть выражена в виде вызова процедуры, не повторяются ни операторы, ни операнды. Для такого потенциального языка L = 1. Для всех же остальных языков L уменьшается с увеличением избыточности.

Следовательно, вместо уравнения (4.14) реальнее ожидать, что

B = L * Е/Е_о. (4.15)

По правилам алгебры произведение L  Е можно заменить на V, что даст

B=V/Eo. (4.16)

Если теперь приравнять E_o из уравнений (4.14) значению Е_крит, найденному по уравнению (4.13), то получим соотношение

B= V / 3000 (4.17)

C другой стороны, подставив в (4.17) выражение для V из (4.10), получим

B= (V^*)² / (3000*) (4.18)

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

9. Метрики структурной сложности программ. Маршруты выполнения программ и их сложность. Критерии выбора маршрутов. Общая характеристика. Критерий выбора маршрутов по принципу минимального покрытия графа управления программы.

Структурная сложность программ определяется:

• числом взаимодействующих компонент;

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

• сложностью взаимодействия компонент.

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

Установлено, что сложность программного модуля связана не столько с размером (числом команд) программы, сколько с числом маршрутов ее исполнения и их сложностью.

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

Все маршруты исполнения программного модуля условно можно разделить на две группы

• вычислительные маршруты

• маршруты принятия логических решений.

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

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

Сложность вычислительных маршрутов оценивается следующей формулой:

,

где m – количество маршрутов исполнения программы

l_i – число данных обрабатываемых в i-ом маршруте

_j – число значений обрабатываемых данных j-го типа (2  _j  5)

Расчет сложности программы по данной формуле имеет значительную неопределенность из-за произвола в выборе количества значений _j при изменении входных данных. Поскольку доля вычислительной части во многих сложных программных комплексах обработки информации относительно невелика (общее число арифметических операций не выходит за предел 5–10%), вычислительные маршруты не определяют структурную сложность программ.

Сложность маршрутов принятия логических решений оценивается формулой

,

где p_i – число ветвлений или число проверяемых условий в i-ом маршруте.

Общая сложность программы определяется формулой

,

где с – некоторый коэффициент пропорциональности, определение которого является сложной задачей.

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

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

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

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

Граф потока управления – ориентированный граф, моделирующий поток управления программы.

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

Рассмотрим структурную сложность типичной программы управления, содержащей 100 – 200 команд, граф потока управления которой, представленный на рис.3, содержит 14 вершин, 20 дуг и 3 цикла.

Для полной проверки этой программы по первому критерию достаточно следующих четырех маршрутов:

m1: 1 – 2 – 14

m2: 1 – 3 – 4 – 6 – 8 – 6 – 8 – 14

m3: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m4: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 14

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

m

S =  p_{i ,}

i =1

где p_i – количество вершин ветвления в i-том маршруте без учета последней вершины

m1 1 - 2 - 14 = 1

m2 1 - 3 - 4 - 6 - 8 - 6 - 8 - 14 = 5

m3 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 - 13 - 14 = 5

m4 1 - 3 - 4 - 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 - 14 = 9

20

Таким образом, сложность программы, представленной графом на рис.3, составляет некоторую метрику в 20 единиц.

Недостаток первого критерия: не учитывается комбинаторика сочетания условий на разных участках маршрутов (например, при сочетаниях ветвлений в вершинах 3 и 12).

Рис.3

10. Критерии выбора маршрутов на основе цикломатического числа графа управления программы.

Критерий 2. Основан на анализе базовых маршрутов в программе, формируемых и оцениваемых на основе цикломатического числа графа потока управления программы (см. работы Т.МcCabe и В.В.Липаева).

Цикломатическое число Z исходного графа программы определяется формулой

Z = Y - N +2*,

где Y – общее число дуг в графе

N – общее число вершин в графе

 – число связных компонент графа.

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

Максимально связным графом называется граф, у которого любая вершина доступна из любой другой вершины.

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

Для рассматриваемого графа максимально связанный граф получается путем добавления дуги (14, 1)

Z = Y - N + 2P = 20 - 14 + 21 = 8

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

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

m1 6 – 8

m2 9 – 10 Линейно-независимые циклические маршруты

m3 7 – 9 – 10 – 11

m4 1 – 2 – 14 Линейно-

m5 1 – 3 – 4 – 6 – 8 – 14 независимые

m6 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 14 ациклические

m7 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14 маршруты

m8 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 14

Определение структурной сложности по второму критерию:

m1 6 - 8 = 1

m2 9 - 10 = 1

m3 7 - 9 - 10 – 11 = 2

m4 1 - 2 – 14 = 1

m5 1 - 3 - 4 - 6 - 8 – 14 = 4

m6 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 5

m7 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 6

m8 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 - 13 – 14 = 6

26

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

Z = n_в +1

Для рассматриваемого примера Z = 7 + 1 = 8 (ветвления имеют место в вершинах графа 1, 3, 4, 8, 10, 11, 12).

Исследования графов реальных программных модулей с достаточно большим фиксированным числом вершин показали, что:

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

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

В.В. Липаев показал, что для Z  10 модули корректно проверяемы и число ошибок в таких модулях будет минимальным. Приемлемыми значениями Z считаются 10  Z 30. При Z > 30 устранить ошибки в процессе тестирования практически невозможно.

Для автоматического анализа графов по второму критерию с помощью ЭВМ используются матрицы смежности и достижимости графов.

Матрица смежности – это квадратная матрица, в которой 1 располагается в позиции (i, j), если в графе имеется дуга (i, j).

Для рассматриваемого графа программы матрица смежности имеет вид, показанный в табл.7.

Таблица 7

	1	2	3	4	5	6	7	8	9	100	11	12	13	14
1
2	1
3	1
4			1
5			1	1
6				1				1
7					1						1
8						1
9							1			1
10									1
11										1
12											1
13												1
14		1						1				1	1

Матрицей достижимости называется квадратная матрица, в которой 1 располага-ется в позиции, соответствующей дуге (i, j). Для рассматриваемого графа программы матрица достижимости имеет вид, показанный в табл.8.

Таблица 8

	1	2	3	4	5	6	7	8	9	100	11	12	13	14
1
2	1
3	1
4	1		1
5	1		1	1
6	1		1	1		1		1
7	1		1	1	1		1		1	1	1
8	1		1	1		1		1
9	1		1	1	1		1		1	1	1
10	1		1	1	1		1		1	1	1
11	1		1	1	1		1		1	1	1
12	1		1	1	1		1		1	1	1
13	1		1	1	1		1		1	1	1	1
14	1	1	1	1	1	1	1	1	1	1	1	1	1

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

С помощью матрицы достижимости можно сравнительно просто выделить циклы, отмечая диагональные элементы, равные 1, и идентичные строк.

Для рассматриваемого примера одинаковыми являются строки 6 и 8, которые имеют 1 на диагонали, следовательно, вершины 6 и 8 образуют цикл. Аналогично можно выделить еще два маршрута с циклами, образованными вершинами 9 и 10 и 7, 9, 10 и 11 соответственно.

11. Критерий выбора маршрутов, основанный на выделении полного состава базовых структур графа потока управления программы.

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

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

Для рассматриваемого примера по данному критерию необходимо исполнить 6 ациклических маршрутов и 5 маршрутов, из которых достижимы элементарные циклы.

m1 1 – 2 – 14

m2 1 – 3 – 4 – 6 – 8 – 14

m3 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 14

m4 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 14

m5 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m6: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m7 1 – 3 – 4 – 6 – 8 – 6 – 8 – 14

m8: 1 – 3 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 14

m9: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 14

m10: 1 – 3 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m11: 1 – 3 – 4– 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 13 – 14

Определим структурную сложность заданной программы по третьему критерию:

m1 1 - 2 - 14 = 1

m2 1 - 3 - 4 – 6 – 8 – 14 = 4

m3 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 - 14 = 5

m4 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 6

m5 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 - 13 - 14 = 5

m6: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 - 13 – 14 = 6

m7 1 - 3 - 4 - 6 - 8 - 6 - 8 - 14 = 5

m8: 1 - 3 - 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 14 = 8

m9: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 14 = 9

m10: 1 - 3 - 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 13 – 14 = 8

m11: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 – 13 – 14 = 9

S₂ = 1 + 4 + 5 + 6 + 5 + 6 + 5 + 8 + 9 + 8 + 9 = 66

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

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

12. Методы и средства измерения характеристик программ. Схема проведения измерений. Способы регистрации измеряемых параметров. Виды измеряемых характеристик программ. Детерминированные и статистические характеристики. Трассировочные записи, временные и частотные профили.

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

В целом измерительные методы имеют следующее назначение

1. Измерение параметров потребления программами ресурсов вычислительной системы с целью устранения дефектов производительности.

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

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

Необходимые условия применения измерительных методов

1. Наличие готовой программы, подлежащей измерительному исследованию;

2. Наличие реальной вычислительной системы (а не её модели) для прогона программы

3. Наличие аппаратных или программных средств проведения измерений

4. Создание условий снижения искажений, вносимых в функционирование системы в процессе проведения измерений, до приемлемого уровня.

Общая схема проведения измерений показана на рис.4.

Рис.4

Представленная на рис.4 схема измерений включает следующие компоненты

1. Исследуемую ВС с установленными программами.

2. Средства регистрации параметров потребляемых ресурсов при выполнении данной рабочей нагрузки.

3. Архив для хранения результатов многочисленных измерений.

4. Результаты измерений обрабатываются некоторой ВС (отдельная ВС или та же, на которой снимались измерения, но после выполнения сеанса измерений.).

5. Рабочая нагрузка - одна или несколько программ или наборов данных для получения статистики проводимых измерений.

Процесс измерения подготовки и проведения измерений включает следующие три этапа

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

2. Выбор (разработка) средств регистрации параметров потребления ресурсов системы.

3. Выбор (разработка) алгоритмов расчетов характеристик программ по результатам измерений.

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

Существует два основных способа регистрации измеряемых параметров

- трассирующий

- выборочный.

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