{Ri (ej)} e -event.

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

Если рассматривается емкостная нагрузка - то берутся наборы данных, а если временная нагрузка - то выбираются обращения к программным компонентам.

Вторая группа событий - прерывания процессора как внутренние, так и внешние, наступаю-щие при обмене данными с внешними устройствами.

При выборочном способе измерения производятся в моменты времени tj, обычно равноудаленные друг от друга.

t_j = t_j-1 +t

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

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

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

Достоинства выборочного способа - более простой, т.к. не надо регистрировать наступление событий.

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

Обычно с помощью измерительных мониторов получают следующие типы характеристик

1. Трассировочная запись - множество пар {r_i  _j } значений, где

r_i - некоторый i-ый параметр потребления ресурсов системы

_j - интервал времени между предыдущим и текущим регистрируемым событием, либо момент регистрации.

Трассировочная запись является наиболее полной характеристикой поведения анализируемой программы и может содержать 10-ки тысяч записей. Её достоинством также является хронология последовательности выполнения программы.

2. Профиль (динамический) выполнения программы.

Они делятся на две группы

- частотные

- временные.

Частотные профили определяют количественное распределение потребления рассматриваемых ресурсных параметров.

Временные профили задают распределение времён потребления ресурсов в абсолютном или относительных масштабах.

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

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

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

3. Смеси (динамические) (команд/программ).

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

4. Коэффициенты загрузки позволяют оценить загруженность некоторого ресурса при выполнении программы как отношение времени использования ресурса к общему времени исполнения программы К_з = Т_исп/Т_общ.

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

13. Типы измерительных мониторов и требования к ним. Классификация измерительных мониторов. Сущность и особенности каждого класса мониторов.

К измерительным мониторам предъявляются следующие требования

1. Минимальные искажения в системе при выполнении программы.

Искажения бывают двух типов

- временные искажения - искажения связанные с рассогласованием реального времени наступления события и временем регистрации параметра монитором

• пространственные искажения - сам монитор и собираемые им данные занимают место в памяти ЭВМ и препятствуют размещению объектов программы).

2. Достаточная точность измерений.

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

4. Независимость от измеряемой системы (программы).

5. Низкая стоимость (Чтобы не отпугивать пользователей.)

6. Простота использования.

Классификация измерительных мониторов.

Общую схему классификации измерительных мониторов можно представить в виде, пока-занном на рис.5.

Рис.5

14. Аппаратные измерительные мониторы (АИМ). Общая структура. Достоинства и недостатки.

АИМ подразделяются на встроенные и автономные.

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

Основное назначение встроенного АИМ - для проверки, контроля и настройки ВС. Но т.к. в его составе могут находиться триггеры состояний схемы, счетчики и некоторые другие устройства, то они могут использоваться и ддя измерения параметров программ.

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

Рассмотрим структурную схему автономного АИМ, показанную на рис.6.

Рис.6

Зонд - высокоомный датчик сигналов, не влияющий на функционирование системы.

Фильтр событий – устройство, вырабатывающее сигнал истинности, при наступлении какого-либо события. Может содержать аналоговые компараторы для сравнения уровней сигналов с заданными границами, цифровые компараторы для сравнения кодов, простейшие автоматы типа детекторов последовательностей команд или адресов памяти (2-3 команды или адреса, повторяющиеся друг за другом могут служить признаком наступления события).

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

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

Часы реального времени - служат для регистрации моментов наступления событий или длительностей интервалов времени между событиями.

Достоинства:

1. Способность регистрации микрособытий

2. Низкие искажения измерительной системы при выполнении программы

3. Низкие накладные расходы

4. Высокая разрешающая способность по времени

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

Недостатки:

1. Сложность обнаружения событий, связанных с функционированием программ (макрособытий)

2. Специализированность приводит к высокой стоимости

3. Старение аппаратных компонентов снижает надежность мониторов

15. Аппаратные измерительные мониторы (АИМ) с фиксированной программой. Достоинства и ограничения использования.

Пример АИМ с фиксированной программой и последовательным входом (рис.7) для измерения коэффициента загрузки процессора или другого ресурса по формуле

Рис. 7

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

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

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

16. Аппаратные измерительные мониторы (АИМ) с изменяемой программой (гибридные). Достоинства и недостатки.

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

Пример ГИМ для оценки распределения частот использования нерезидентных и резидентных модулей программы (например, при настройке конфигурации ОС) показан на рис.8. При ограниченном ресурсе основной памяти часть модулей резидентно располагается в памяти с произвольным доступом RAM, другие же модули загружаются в память по мере необходимости из дисковой памяти и после их использования память очищается. Так как нерезидентные модули загружаются в свободные сегменты памяти, их размещение может быть произвольным и поэтому на основе фиксации участков памяти, используемых ЭВМ в данный момент, трудно определить, какой модуль занимает процессорное время в данный момент (за исключением резидентных модулей).

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

Рис.8

На рис.8 показаны:

• RAM - память с произвольным доступом управляющие таблицы ОС хранят адреса загрузки и размеры модулей программы в RAM;

• Контроллер диска с триггером состояния «занято» позволяет фиксировать моменты выполнения операций чтения - записи информации на диск, изменяющих размещение нерезидентных модулей;

• Фильтр событий (включающий счетчики и компараторы с установками адресов размещения модулей), управляемый измерительной ЭВМ, позволяет отслеживать, с какими модулями работает программа и как часто к ним идет обращение

• Через ШВВ (шину ввода - вывода) измерительная ЭВМ связана с управляющими таблицами RAM измеряемой ЭВМ, что позволяет ей определять, какой модуль программы размещен в заданных адресах ОЗУ.

Гибридные измерительные мониторы сочетают достоинства аппаратных и программных мониторов, но являются более специализированными, чем программные, и дорогими.

Достоинства:

1. Способность регистрировать макрособытия

2. Точность и разрешающая способность на уровне аппаратных мониторов

Недостатки:

1. Высокая стоимость

2. Сложность в усвоении и управлении

17. Назначение и принцип действия программных измерительных мониторов (ПИМ). Классификация ПИМ. Общие принципы работы ПИМ. Краткая характеристика стандартных ПИМ.

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

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

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

- как и на что расходуется время работы программы;

- сколько раз выполняется данная строка программы;

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

Пакет Interval Performance Monitoring (IPM) Калифорнийского Университета. IPM ориентирован исключительно на временные измерения и состоит из набора отдельных функций для замера времени и протоколирования результатов измерения. Функции вставляются в нужные места программы, после чего программа компилируется. Такой подход позволяет резко повысить точность измерений, но требует значительных дополнительных усилий по сбору и классификации полученной информации. Трудоемкость проведения измерительного эксперимента не позволяет считать системы типа IPM полноценными профилировщиками.

2 группы встроенных программных мониторов:

1) Встроенные мониторы для тестирования и настройки ОС

позволяют фиксировать ограниченное количество параметров для проверки корректности функционирования ядра ОС

2) Журналы учета

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

- время использования ЦП

- операции ввода-вывода

- работу с дисковой памятью

- число обращений к диску

- число обращений к устройствам ввода-вывода

- число набора данных

- емкость потребляемой памяти

Недостатки:

1. Отсутствуют программы их автоматического учета

2. Низкая точность оценки использования ресурсов (из-за сложности разделения выполнения пользовательских и системных программ; распределение ресурсов между пользователями выполняется некорректно)

2 группы автономных программных мониторов(запускаются извне ОС)

1) универсальные

используются для настройки ОС

GTF – JS-360

УСТ – ОС – ЕС

2) специализированные

«профилировщики» или «анализаторы кода выполнения программ»

Turbo Profiler – MS DOS

VTune 6.0 – Windows (под Intel)

AMD Code Analyst – под AMD

Visual C++ Profiler

Java Profiler

Профилировщики предназначены для:

1. поиск «узких» мест в программе

2. анализ покрытия выполнения программ

3. распределение времени выполнения между модулями

4. контроль взаимосвязей по данным между программами

Проблемы использования ПИМ:

1. проблема буферизации

маленький – часто переписывать

большой – долгий поиск места для записи

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

3. ситуация переполнения всех буферов

либо остановка монитора и перепись данных

либо заполнять буфер с потерей старых данных

4. приоритет измерительного монитора

высокий – возрастают накладные расходы

низкий - ошибки с регистрацией измер. параметров

18. ПИМ "TurboProfiler" как серийный монитор ПК Intel 80X86 для ОС MSDOS. Назначение и возможности. Организация измерений. Достоинства и недостатки.

Один из самых известных профилировщиков - Turbo Profiler фирмы Borland International. Система Turbo Profiler контролирует каждый шаг выполнения программы и предоставляет подробные статистические сведения о всех этапах ее работы. Такой подход к измерениям позволяет проводить профилирование в интерактивном режиме и получать большое количество сведений о работе программы, но вносит большие временные искажения в процесс ее выполнения. Кроме того, для проведения измерительного эксперимента тестируемая программа должна быть откомпилирована с отладочной информации при отключении оптимизации компилятора. Это делает профилирование неадекватным реальному выполнению программы. Для получения достоверной информации о времени выполнения от программиста требуется достаточно высокая квалификация в методике планирования и проведения измерительного эксперимента. Таким образом, Turbo Profiler ориентирован прежде всего на профессиональных программистов. За счет грамотного планирования эксперимента и отказа от ряда сервисных функций можно повысить точность временных измерений до 55 мс. Тем не менее, такая точность в ряде случаев недостаточна.

19. Пример ПИМ "Sampler" как монитора уникального типа для ПК семейства Intel 80X86. Обоснование методики измерений. Временная диаграмма снятия отсчета. Способ коррекции измерений.

Многие из полезных принципов организации системы Turbo Profiler и пакета IPM были реализованы на кафедре МОЭВМ в ПИМ Sampler. Особенностью работы ПИМ Sampler являются:

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

2. Исследуемая программа выполняется "естественным" образом, а не по шагам и без использования отладочной информации.

3. Измерения времени выполняются с максимально возможной точностью.

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

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

На этапе планирования измерительного эксперимента производится задание контрольных точек. После этого исследуемая программа компилируется. Задание контрольной точки предполагает вызов некоторой функции на языке программирования исследуемой программы. Назовем эту функцию функцией задания контрольных точек или просто функцией контрольных точек. Эта функция не должна вносить больших искажений в работу исследуемой программы. Для этого она должна быть небольшого размера и обладать высоким быстродействием. Вызов функции контрольных точек осуществляется с помощью механизма прерываний, в частности, используется прерывание пользователя с номером 65. Функция контрольных точек выполняет измерение времени дважды: сразу после входа в нее и непосредственно перед выходом. Оба значения времени передаются измерительному монитору. После первого замера управление передается монитору и он выполняет действия по идентификации и накоплению результатов измерений. После возврата управления в функцию задания контрольных точек, выполняется второе измерение времени. Такой подход наиболее полно соответствует условиям 3 и 4, поскольку позволяет точно измерить не только время выполнения участка программы между контрольными точками, но и убрать временное искажение вносимое измерительным монитором.

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

• Подготовительные операции. На этом этапе производится проверка допустимости входных параметров, формирование необходимых структур данных и операции по калибровке измерительного монитора. После окончания подготовительных операций управление передается исследуемой программе. Управление передается по схеме - "запуск программы-потомка с возвратом в предок".

• Идентификация и накопление измерительный информации. Эти действия производится после перехвата прерывания от исследуемой программы. Идентификация информации подразумевает не только анализ положения контрольных точек, но и определение ряда статистических сведений о проходах между контрольными точками. Накопление такого рода измерительной информации облегчает последующее формирование отчета и позволяет резко сократить расход памяти, потребляемой монитором. При накоплении измерительная информация корректируется для снятия временных искажений монитора. Таким образом, исследуемая программа выполняется без трассировки и освобождается от операций по анализу и протоколированию измерительной информации. Это полностью соответствует принципам 1, 2 и 4.

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

В «Sampler»e замеры системного времени проводятся, как и для IPM, внутри тестируемой программы вызовом функции задания точки профилирования. Этим достигается высокая точность измерения времени и отсутствие ограничений на использование отладочной информации и оптимизации компилятора. Функция задания точки профилирования определена в модуле на соответствующем языке программирования, подключаемом к тестируемой программе. С другой стороны, запуск тестируемой программы осуществляется, как и для Turbo Profiler, через монитор. Это позволяет освободить пользователя от сбора и классификации измерительной информации. Результаты измерения могут быть представлены как на экране компьютера, так и твердой копией после вывода протокола измерения на принтер.

ПИМ Sampler состоит из двух исполняемых модулей следующего функционального назначения

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

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

Обоснование методики измерения времени.

В ПИМ Sampler используются два режима измерения моментов времени, соответствующих выполнению фрагментов программы.

Режим 1: Измерения времени через 0 канал таймера с использованием портов ввода-вывода.

Для задания временных интервалов и формирования сигналов с различными временными параметрами в компьютерах IBM PC используется программируемый таймер 8253. Таймер работает независимо от процессора и считает реальное время. Формирование времени суток в компьютерах IBM PC можно пояснить схемой, показанной на рис.9.

IRQ0

Рис.9

Микросхема таймера имеет три канала, основным из которых с точки зрения измерения времени, является канал 0. Импульсы частотой 1.19 МГц от системных часов поступают на микросхему таймера, где происходит деление частоты на 64 К и на выходе канала 0 мы получаем импульсы с частотой 18,2 Гц ( с периодом следования 55 мс). Эти импульсы поступают на контроллер прерываний в виде запроса аппаратного прерывания на уровне 0 и, если разрешены прерывания, вырабатывается сигнал INT8. В результате обработки прерывания INT8 накапливаются данные в двойном слове с адресом 0040:006Сh, расположенном в области данных BIOS.

Более подробно возможность измерения временных характеристик программ с использованием микросхемы таймера можно пояснить с помощью рис.10.

Рис.10

Микросхема таймера содержит три канала с адресами 40h, 41h, 42h. Каждый канал содержит три регистра, два из которых двухбайтные - задвижка и счетчик и один - однобайтный - регистр ввода-вывода. Регистр ввода-вывода связан шиной с аккумулятором (регистром AL) для считывания информации.

Канал 0 таймера выполняет две функции

1. Осуществляет контроль времени суток

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

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

Канал 1 таймера обеспечивает прямой доступ к памяти (DMA).

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

Управление работой таймера осуществляется регистром команд по адресу 43h.

Структура команд порта по адресу 43h

Канал 7 – 6

Операция 5 – 4

Режим 3-1

0

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

Биты 1 - 3 задают режим работы таймера

• 000 - запись данных счетчика в задвижку

• 011 - выполнение основных операций по считыванию информации канала 0 и подсчета поступивших импульсов.

Биты 4 - 5 определяют возможные операции:

• 00 - передача данных из счетчика в задвижку или наоборот

• 01 - чтение или запись старшего байта

• 10 - чтение или запись младшего байта

• 11 - чтение или запись последовательно младшего и старшего байтов.

При снятии измерений регистр задвижки загружается кодом (0FFFFh), который потом перемещается в счетчик. Счетчик считает поступающие тактовые импульсы в обратном направлении (в убывающем порядке), поэтому при его загрузке и считывании надо брать дополнение до FFFFFh. После того как счетчик обнулится, вырабатывается сигнал контроллера прерывания INT-8. Содержимое счетчика следует поместить в задвижку и считать его в аккумулятор AL. После этого восстановить содержимое задвижки и продолжить работу. Интервал времени в 1/18.2 сек (55 мс) получил название «тик», а минимально различимый интервал, равный 1/FFFF «тика» получил название «минитик» = 0.84 мкс.

Наиболее точное и полное значение промежутков времени можно получить, используя совместно значение переменной области данных BIOS (0040:006С) и внутреннего счетчика таймера. Это позволяет измерять промежутки времени длительностью от 0,84 мсек до 24 часов.

Достоинства режима измерения времени через 0 канал таймера с использованием портов ввода-вывода:

- возможность применения на машинах типа IBM PC любого класса.

Недостатки:

- низкая точность измерений;

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

Режим 2. Измерения времени через счетчик Time Stamp Counter (TSC).

Режим применяется только для старших моделей IBM PC, начиная с Pentium. В составе этих компьютеров появился внутренний 64 битный таймер, который может быть прочитан в регистры EDX:EAX с помощью инструкции RDTSC (Read Time Stamp Counter). Каждый такт этот счетчик увеличивает свое значение на 1. Это очень полезно для замера точного количества тактов, потребовавшихся на исполнение некоторого фрагмента кода.

К сожалению, имеются проблемы чтения содержимого счетчика TSC. В Pentium добавлен внутренний регистр CR4, флаг TSD которого управляет возможностью чтения счетчика TSC. При CR4.TSD, равном 0, счетчик TSC можно читать в любом случае. При CR4.TSD, равном 1, содержимое счетчика можно прочитать только на 0-ом уровне привелегий. В общем случае флаг CR4.TSD установлен. Поэтому, инструкция RDTSC не может выполняться в режиме виртуального 8086 (3-й уровень привилегий).

При использовании EMM386 или Windows процессор находится в защищенном режиме и Dos - приложения типа Sampler запускаются в виртуальном режиме и имеют 3 уровень привелегий. Поэтому, если запускать измеряемую программу под DOS, необходимо закомментировать EMM386 (или любой другой менеджер памяти) в CONFIG.SYS и не следует запускать программу в режиме DOS из под Windows.

Достоинства данного режима измерений:

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

• высокая точность измерений (до нескольких машинных тактов):

• для регистрации отсчета времени требуется только команда RDTSC и сохранение регистров EAX:EDX (20-30 тактов).

Недостатки:

• возможность применения только на машинах класса Pentium и выше.

возможность полноценной работы только под DOS и в отсутствие драйверов памяти типа EMM386 (QEMM).

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

Под корректностью программы понимают её соответствие некоторому эталону или совокупности формализованных эталонных правил и характеристик.

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

Требования к корректности делятся в зависимости от двух типов критериев качества

• Для функциональных критериев они определяются предметной областью и функциями выполняемой программы.

• Для конструктивных критериев они определяются общими для всех программ свойствами.

В зависимости от проверяемых компонентов программ различают следующие виды их корректности, показанные на рис.11.

Рис.11

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

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

• Конструктивная составляющая определяется правилами построения структуры программных модулей, задаваемыми в технологии и языке программирования.

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

Функциональная составляющая корректности может проверяться в различных условиях:

Детерминированная - для фиксированных наборов входных данных должны быть получены конкретные значения результатов;

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

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

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

Рис.12

3.Корректность данных имеет конструктивную и функциональную составляющие.

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

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

Эталоны и методы проверки корректности.

Эталоны для проверки корректности программ могут использоваться в следующих трех формах, поясняемых с помощью рис.13:

1. Формализованные правила.

2. Программные спецификации.

3. Тесты.

Формализованные правила - имеют достаточно неопределенностей, так как опреде-ляются двумя видами требований

• требования стандартов (общероссийских и стандартов предприятий)

• требования языков и технологий программирования.

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

• синтаксический контроль

• семантический контроль

• структурный контроль.

• контроль полноты спецификаций

• верификация программ.

Статическое и динамическое тестирование

Рис.13

2. Программные спецификации - относятся к функциональным эталонам и в основ-ном обеспечивают проверку корректности программ в статике.

3. Тесты.

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

Как формируются эталоны для тестирования? Существует несколько способов формирования эталонов:

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

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

3. Использование результатов испытаний предшествующих вариантов программ.

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

Степень достоверности проверки корректности программ при использовании этих методов убывает по номерам способов формирования эталонов.

В 1-ом случае обеспечивается 100% гарантия корректности программ, в третьем случае такой уверенности нет, но мы можем убедиться в том, что программа работает так же или иначе, чем аналогичный вариант. Менее достоверные тесты приходится использовать из-за недостаточности сил и средств.

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

Различают два типа проверки корректности:

• валидация (validation) – установление соответствия между тем, что делает программа, и тем, что нужно Заказчику;

• верификация (verification) – установление соответствия между программой и ее спецификацией.

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

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

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

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

• частичную корректность – удовлетворение внешним (входной и выходной) спецификациям программы при условии завершения выполнения программы;

• завершенность – достижение в процессе выполнения выхода программы при определенных входной спецификацией данных.

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

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

• частичная корректность (при условии завершенности);

• завершенность программы;

• незавершенность программы;

• тотальная корректность (частичная корректность и завершенность);

• частичная некорректность (некорректность при условии завершенности);

• некорректность (незавершенность или частичная некорректность).

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

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

Анализ завершенности последовательных программ

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

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

• обращение к частично определенной функции со значением аргументов вне области определения;

• зацикливание.

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

21. Тестирование программных изделий. Методы и критерии тестирования. Понятие теста. Основные принципы тестирования. Критерии завершения тестирования.

Основные понятия процесса тестирования

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

В литературе имеется несколько различных определений понятия “тестирование”. Будем использовать следующее:

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

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

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

Определение. Методы тестирования – это совокупность правил, регламентирующих последовательность шагов по тестированию.

Определение. Критерии тестирования – соображения, позволяющие судить о достаточности проведенного тестирования.

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

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

Результативным (удачным) считается тест, прогон которого привел к обнаружению ошибки. Из данного свойства теста вытекает важное следствие: тестирование – процесс деструктивный (обратный созидательному, конструктивному). Именно этим объясняется, почему многие считают его трудным. Большинство людей склонны к конструктивному процессу созидания объектов и в меньшей степени – к деструктивному процессу.

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

Определение. Тест – это набор входных значений, условий выполнения и ожидаемых значений на выходе, разработанных для проверки конкретного пути выполнения программы.

Программный продукт, как объект тестирования, имеет ряд особенностей, которые отличают процесс тестирования программного обеспечения от традиционного, исторически ранее появившегося “аппаратного” тестирования:

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

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

• высокая сложность программ и принципиальная невозможность построения тестовых наборов, достаточных для исчерпывающего тестирования;

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

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

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

• относительно невысокая степень формализации критериев завершения процесса тестирования и оценки качества тестирования.

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

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

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

Сформулируем основные принципы тестирования:

• Описание предполагаемых значений выходных данных или результатов должно быть неотъемлемой частью теста.

• Следует избегать тестирования программы ее автором; тестирование является более эффективным, если оно выполняется не автором программы, но отладка программы обычно более эффективно выполняется авторами.

• Организация не должна сама тестировать разработанные ею программные продукты.

• Необходиимо досконально изучать результаты применения каждого теста.

• Тесты для неправильных и непредусмотренных входных данных следует разрабатывать так же тщательно, как для правильных и предусмотренных данных.

• Необходимо проверять программу на нежелательные побочные эффекты.

• Не следует выбрасывать тесты, даже если программа уже не нужна.

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

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

22. Объекты тестирования. Категории тестов. для различных объектов тестирования. Тестирование на основе потока управления. Критерий покрытия решений.

Объекты тестирования

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

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

• спецификации программных модулей, групп программ и программных комплексов;

• программные модули (код программных модулей);

• группы программ, решающие законченные функциональные задачи;

• комплексы программ, для которых завершены все виды отладки;

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

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

цикла.

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

Состояние теории и практики тестирования можно изобразить следующим графиком (нумерация объектов на рисунке соответствует списку объектов тестирования):

1 2 3 4 5 6

С

Объекты тестирования

пецификации Модули Группы Комплексы Прогр. Программный

программ программ ср-ва продукт

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

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

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

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

Категории тестов для различных объектов тестирования

На разных этапах ЖЦ программного обеспечения для каждой категории объектов тестирования ставятся свои задачи тестирования и, соответственно, применяются свои виды тестирования и категории тестов. Каждая категория имеет специфическое, частное назначение для выявления ошибок определенного класса.

Для описанных выше объектов тестирования выделяются следующие категории тестов:

1. На этапе тестирования спецификаций:

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

• согласованности интерфейса в спецификациях программных компонент.

2. На этапе тестирования программных модулей:

• структуры программного модуля;

• вычислений и преобразований данных программным модулем;

• полноты функций, выполняемых модулем.

3. На этапе тестирования функциональных групп программ:

• структуры группы программ;

• межмодульного интерфейса в группе программ;

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

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

3. На этапе тестирования комплекса программ при отладке:

• полноты решения функциональных задач комплексом программ для типовых исходных данных;

• функционирования программ в критических ситуациях по условиям и логике решения задач;

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

• параллельного (одновременного) исполнения различных программ;

• эффективности защиты от искажения входных данных;

• определения надежности комплекса программ;

• оценки эффективности защиты от сбоев аппаратуры и не выявленных ошибок программ.

3. На этапе тестирования комплекса программ при испытаниях:

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

• удобства эксплуатации и взаимодействия человека с комплексом программ;

• удобства установки и подготовки рабочей версии;

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

• корректности документации;

• удобства сопровождения и модификации программ.

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

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

Одним из общих принципов тестирования ПО является проведение работ по тестированию в течение всего ЖЦ.

Методы структурного тестирование программ

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

Тестирование на основе потока управления

При проведении структурного тестирования на основе управляющего графа программы используются следующие критерии:

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

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

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

• покрытие условий/решений – поскольку критерии покрытия решений и условий не заменяют друг друга, поэтому их можно объединить, получив критерий покрытия условий/решений. Он требует такого набора тестов, чтобы все возможные результаты каждого условия в решении выполнялись по крайней мере один раз и все результаты каждого решения выполнялись по крайней мере один раз. Недостатком критерия покрытия решений/условий является невозможность его применения для выполнения всех результатов всех условий (некоторые условия могут быть скрыты другими условиями). Например, результаты условий при выполнении операций И и ИЛИ могут блокировать действия других условий. Так, если условие И есть ложь, то никакое из последующих условий в выражении не будет выполнено. Аналогично, если условие ИЛИ есть истина, то никакое из последующих условий в выражении не будет выполнено.

• комбинаторное покрытие условий – требует такого набора тестов, чтобы все возможные комбинации результатов условия в каждом решении выполнялись по крайней мере один раз. Слово возможные употреблено потому, что не все комбинации условий могут быть реализуемыми; например, в выражении (A>2) & (A<10) могут быть реализованы только три комбинации условий. Набор тестов, удовлетворяющий критерию комбинаторного покрытия условий, удовлетворяет также и критериям покрытия решений, покрытия условий и покрытия решений/условий;

• покрытие путей – каждый путь хотя бы один раз (это наиболее полный, но нереализуемый критерий);

• покрытие функций - каждая функция должна быть выполнена хотя бы один раз;

• покрытие вызовов – каждый вызов каждой функции хотя бы один раз.

23. Тестирование на основе потока управления. Критерий покрытия условий и критерий комбинаторного покрытия условий

см. № 22

Пример

if ( (A > 1) & ( B=0 ) ) then X:=X/A;

if ( (A = 2) Or ( X>1 ) ) then X:=X+1;

Покрытие ветвей

Покрытие решений может быть реализовано двумя тестами, покрывающими либо пути ace и abd, либо пути acd и abe. Если выбрать второе покрытие, то входами двух тестов являются: A=3; B=0; X=3 (путь acd) и A=2; B=1; X=1 (путь

abe). Эти тесты также недостаточны. Например, если выбрано первое покрытие (путь acd),путь, где X не изменяется, будет проверен с вероятностью 50%. Если во втором условии имеется ошибка (например, X<1 вместо X>1), то эта ошибка тестами не будет обнаружена!

Покрытие условий

В программе имеются 4 условия: A > 1, B = 0, A = 2 и X > 1. Следовательно, требуется достаточное число тестов, чтобы реализовать ситуации, где A>1, A1, B=0 и B0 (первое условие) и A=2, A2, X>1, X1 (второе условие). Тесты, удовлетворяющие критерию покрытия условий, и соответствующие им пути:

• A=2; B=0; X=4 (путь ace);

• A=1; B=1; X=1 (путь abd)

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

С другой стороны, критерий покрытия условий может не удовлетворять критерию покрытия решений. Для рассмотренного примера предложенные тесты покрытия условий покрывают результаты всех решений, но это случайное совпадение. Например, два альтернативных теста: A=1, B= 0, X=3 и

A=2, B=1, X=1 покрывают результаты всех условий, но только два из четырех результатов решений (оба они покрывают путь abe и, следовательно, не выполняют результат истина первого решения и результат ложь второго решения).

Комбинаторное покрытие условий

По этому критерию должны быть покрыты тестами следующие 8 комбинаций:

(1) A > 1, B = 0 (5) A = 2, X >1

(2) A > 1, B  0 (6) A = 2, X  1

(3) A < 1, B = 0 (7) A  2, X >1

(4) A < 1, B  0 (8) A  2, X  1

Следует обратить внимание, что комбинации (5) – (8) представляют собой значения второго оператора if. Поскольку X может быть изменено до выполнения этого оператора, значения, необходимые для его проверки, следует восстановить исходя из логики программы с тем, чтобы найти соответствующие входные значения.

Для того, чтобы протестировать эти комбинации, необязательно использовать все восемь тестов. Фактически они могут быть покрыты четырьмя тестами:

A=2, B=0, X=4 покрывает 1,5

A=2, B=1, X=1 покрывает 2,6

A=1, B=0, X=2 покрывает 3,7

A=2, B=0, X=4 покрывает 4,8

24. Функциональное тестирование. Метод эквивалентного разбиения. Анализ граничных значений.

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

Функциональное тестирование – это тестирование, проводимое для проверки соответствия программной системы или программного модуля специфицированным функциональным требованиям.

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

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

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

1. Метод эквивалентного разбиения

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

Правильно выбранный тест этого подмножества должен обладать двумя свойствами:

1. включать как можно больше входных условий с тем, чтобы минимизировать общее число тестов;

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

Разработка тестов методом эквивалентного разбиения осуществляется в два этапа:

1. выделение классов эквивалентности;

2. построение тестов.

1.1. Выделение классов эквивалентности

Классы эквивалентности выделяются путем выбора каждого входного условия (предложение спецификации) и разбиения его на две или более групп.

Различают два типа классов эквивалентности:

• правильные классы эквивалентности, представляющие правильные входные данные программы;

• неправильные классы эквивалентности, представляющие ошибочные входные данные.

Выделение классов эквивалентности представляет собой взначительной степени эвристический процесс. Однако существует ряд правил, которые следует выполнять:

1. Если входное условие описывает область значений (например, 1  I  100), то задается один правильный класс эквивалениности (1  I  100) и два неправильных ( X < 1 и X>100).

2. Если входное условие описывает число значений (например, число элементов последовательности N не должно превышать 10), то определяется один правильный класс эквивалентности (N  10) и два неправильных (N<1 и N>10).

3. Если входное условие описывает множество входных значений и есть основание полагать, что каждое значение программа трактует особо (например, цвет может принимать значения: красный, желтый, зеленый), то определяется правильный класс эквивалентности для каждого значения и один неправильный класс эквивалентности – значение, не принадлежащее множеству (например, белый).

4. Если входное условие описывает ситуацию “должно быть” (например, первым символом идентификатора должна быть буква), то определяется один правильный класс эквивалентности (первый символ – буква) и один неправильный класс эквивалентности (первый символ – не буква).

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

1.2. Построение теста

1. Назначение каждому классу эквивалентности уникального номера.

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

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

2. Анализ граничных значений

Граничные условия – это ситуации, возникающие непосредственно на, выше или ниже границ входных и выходных классов эквивалентности.

Анализ граничных значений отличается от эквивалентного разбиения в двух отношениях:

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

2. При разработке тестов рассматривают не только входные условия, но и выходные значения.

Правила использования данного метода:

1) Построить тесты для границ области и тесты с неправильными входными данными для ситуаций незначительного выхода за границы области, если входное условие описывает область значений. Например, если правильное значение -1.0  X  +1.0, то составить тесты для ситуаций: -1.0, 1.0, -1.001, 1.001.

2. Построить тесты для минимального и максимального значений условий и тесты, большие и меньшие этих значений, если входное условие принимает значения из некоторого дискретного диапазона. Например, если входной файл может содержать от 1 до 256 записей, то необходимо составить тесты для 0, 1, 255 и 256 записей.

3. Использовать правило 1) для каждого выходного условия. Например, если программа вычисляет ежемесячный расход и если минимум расхода составляет 0.00 руб., а максимум – 100000.00 руб, то нужно построить тесты, которые вызывают следующие расходы: -1.00, 0.00, 100000.00 и 100000.25.

4. Использовать правило 2) для каждого выходного условия. Например, если система информационного поиска отображает на экране терминала не более 8 наиболее подходящих рефератов для входного запроса, то следует составить тесты, которые могли бы вызвать выполнение программы с отображением 0, 1, 8, >8 рефератов.

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

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

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

25. Метод тестирования на основе предположения об ошибке. Критерии завершения тестирования.

Метод функциональных диаграмм

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

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

Метод, основанный на предположении об ошибке

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

В качестве примера рассмотрим тестирование подпрограммы сортировки. Необходимо предусмотреть следующие специальные случаи, которые могут быть не учтены при проектировании программы:

• Сортируемый список пуст.

• Сортируемый список содержит только одно значение.

• Все записи в сортируемом списке имеют одно и то же значение.

• Список уже отсортирован.

Общая стратегия разработки тестов

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

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

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

2. Использовать анализ граничных значений.

3. Определить правильные и неправильные классы эквивалентности для входных и выходных данных и дополнить, если это необходимо, тесты, построенные ранее.

4. Использовать метод предположения об ошибке.

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

Критерии завершения тестирования

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

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

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

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

26. Особенности тестирования программ при отладке и при сопровождении.

На этапе тестирования комплекса программ при отладке:

• полноты решения функциональных задач комплексом программ для типовых исходных данных;

• функционирования программ в критических ситуациях по условиям и логике решения задач;

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

• параллельного (одновременного) исполнения различных программ;

• эффективности защиты от искажения входных данных;

• определения надежности комплекса программ;

• оценки эффективности защиты от сбоев аппаратуры и не выявленных ошибок программ.

На этапе тестирования комплекса программ при испытаниях:

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

• удобства эксплуатации и взаимодействия человека с комплексом программ;

• удобства установки и подготовки рабочей версии;

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

• корректности документации;

• удобства сопровождения и модификации программ.

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

27. Надежность программ. Основные понятия: отказ, сбой, ошибки и восстановление - применительно к программам. Количественные оценки (показатели ) надежности.

Основные показатели надежности программного обеспечения (ПО).

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

• элементы ПО не стареют от износа

• число способов контроля ПО значительно больше числа способов контроля аппаратуры

• в ПО значительно больше объектов для контроля, чем в аппаратуре

• в ПО гораздо проще вносить исправления и дополнения, чем в аппаратуру, но это трудно делать корректно и безошибочно.

Основные понятия, связанные с надежностью программного обеспечения:

• ошибки в программах и признаки их наличия;

• количество оставшихся в программе ошибок (ошибок, дошедших до пользователя); вероятность безотказной работы программы;

• интенсивность обнаружения ошибок (или функция риска);

• прогон программы;

• отказ программы.

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

• при выполнении программы появилась ошибочная операция

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

• несоответствие функций, выполняемых программой, ее спецификации;

• ошибки в самой спецификации, которые вызывают необходимость корректирования программы;

• ошибки в вычислениях (например, переполнение и т.п.);

• ошибки интерфейса программы с пользователем.

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

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

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

Пусть P(t) - вероятность того, что ни одной ошибки не будет обнаружено на временном интервале [0,t]. Тогда вероятность хотя бы одного отказа за этот период будет Q(t) = 1 – P(t), и плотность вероятности можно записать как

Рассмотрим функцию риска R(t), как условную плотность вероятности отказа программы в момент времени t, при условии, что до этого момента отказов не было

(13.1)

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

Из выражения (13.1), ясно, что , и, следовательно,

или

(13.2)

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

Прогон программы – это набор действий, включающий в себя: ввод в программу одной из возможных комбинаций E_i пространства входных данных E (); выполнение программы, которое заканчивается либо получением результата F(E_i), либо отказом.

Для некоторых наборов входных данных E_i, отклонение полученного на выходе результата (F’(E_i)) от требуемого результата F(E_i) находится в пределах допустимого отклонения , то есть выполняется следующее неравенство

()

а для всех остальных E_i из подмножества , выполнение программы не дает приемлемого результата, то есть

()

Случаи, описанные неравенством (13.4), называются отказами программы.

Рассмотрим дихотомическую переменную :

Тогда статистическая оценка вероятности отказа программы в течении m прогонов будет равна:

()

Обозначим через приемлемую ошибку оценкивероятности отказа. Тогда требуемое количество прогонов программы m должно быть пропорционально значению, где Q – заданная вероятность отказа программы. Это означает, что если, например, требуемая относительная ошибка оценки (13.5), и требуемое (желаемое) значение, тогда количество независимых прогонов программы m одлжно быть не меньше, чем, что, конечно, нелегко реализовать на практике. Решением этой проблемы может быть использование процедуры последовательного анализа Вальда.

И наконец, еще один показатель надежности ПО, который тоже будет использоваться в этой работе – среднее время наработки программы до отказа:

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

1. Этап разработки спецификаций 140$;

2. Программирование 1100$;

3. Комплексная отладка 7000$

4. Этап сопровождения от 14000$ до 140 000$

28. Математические модели надежности программ. Классификация и общая характеристика.

Математические модели оценки надежности ПО.

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

Математические модели надежности программ можно разбить на группы по следующим признакам:

• Вид «функции риска», определяющей временную структуру появления ошибок в программе;

• Сложность разработки программы;

• Способы «посева» ошибок и оценки числа исходных ошибок по соотношению исходных и внесенных;

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

Основные метрики, предсказываемые моделями: количество ошибок в программе, полное время тестирования и т.д.

Модели бывают:

- на основе функции риска

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

Джелинского-Моранды

Шика-Уолвертона

Липова

Шнейдевинда

- на основе посева ошибок

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

Оценка производится на основе количества выявленных искусственных и естественных ошибок.

- на основе структур входных данных

модели используют парадигму множества входных данных и реакции программы на входные данные.

29. Группа моделей надежности программ на основе временной структуры появления ошибок (функции риска).