Содержание к диссертации
Введение
Глава I Анализ существующих систем и стандартов тестирования мобильных устройств 10
1.1 Виды тестируемых устройств 10
1.2 Анализ специфики разработки программных средств 14
1.3 Понятие качества программного средства 16
1.4 Общие характеристики качества программных средств . 19
1.5 Стандарты, регламентирующие требования к мобильным устройствам 25
1.6 Обзор существующих операционных систем для мобильных устройств 28
1.7 Разработка требований к системам производящих автоматическое тестирование 31
1.8 Выводы 34
Глава 2: Разработка системы автоматического контроля мобильных устройств 35
2.1 Система автоматического контроля 35
2.2 Загрузка устройств 41
2.2.1 Использование общей файловой системы NFS . 41
2.2.2 Загрузка устройств по DHCP 42
2.2.3 Использование tftp 47
2.3 Подбор кластерной системы 48
2.4 Связывание каналов 61
2.5 Выводы 64
Глава 3: Решение задач оптимизации тестирования 66
3.1 Задачаї о минимизации времени тестирования 69
3.1.1 Анализ эффективных алгоритмов нахождения кратчайших путей 76
3.1.2 Сравнения скорости алгоритмов 93
3.2 Задача2 о минимизации времени на подготовительный этап тестирования 96
3.3 Вероятностные характеристики тестирующей системы . 102
3.4 Выводы 115
Глава 4: Разработка требований и алгоритмов программного обеспечения . 117
4.1 Требования к программному обеспечению 118
4.2 Функциональная схема программы проверки драйверов ввода-вывода 118
4.3 Использование базы данных 123
4.4 Выводы 125
Заключение 127
Литература
- Анализ специфики разработки программных средств
- Использование общей файловой системы NFS .
- Анализ эффективных алгоритмов нахождения кратчайших путей
- Функциональная схема программы проверки драйверов ввода-вывода
Введение к работе
Развитие наукоемких технологий на современном этапе в значительной мере определяется прогрессом в области компьютерных средств, программных систем и информационных технологий. В последнее время становятся очень популярными мобильные устройства, которые представляют из себя сложные электронно-программные приборы. Разработка таких устройств занимает существенное время и больших человеческих ресурсов. Для нахождения ошибок в проектировании таких устройств или в реализованном программном обсспечепии производят тестирование отдельных частей этих устройств. Поскольку в последнее время сложность данных устройств увеличивается, то полный цикл тестирования занимает очень длительное время. С целью сократить это время; разрабатывают системы автоматического контроля, обеспечивающие тестирование в автоматическом режиме.
В настоящее время к мобильным устройствам предъявляется ряд достаточно жестких требований. Эти требования обусловлены как сложностью самих продуктов, так и возрастающими практическими потребностями по размерности и сложности решаемых задач. При этом такая характеристика качества устройств, как временная эффективность, является одной из определяющих.
Очень актуальным является вопрос посвященный решению комплек-
са задач, направленных на разработку и повышение эффективности системы автоматического контроля мобильных устройств, производящей тестирование мобильных устройств. В работе произведен анализ уже существующих систем для тестирования, который показывает, что недостатки этих систем в том, что в них отсутствует оптимизационная часть, позволяющая выполнять оптимальным образом нагруженные тесты. В данной работе разработан ряд алгоритмов позволяющий существенно сократить время тестирования.
Анализ литературы, посвященной тестированию программного обеспечения[56-61] и реализуемых систем автоматического контроля [69-71] а так-же существующих видов и стандартов на проверку и разработку мобильных устройств, показывают, что необходимость проведения работ в данной области обусловлена, в первую очередь отсутствием соответствующего математического и программного обеспечения, способного успешно решать следующие задачи:
построения эффективного метода тестирования мобильных
устройств;
разработки и апробации способов тестирования;
сокращения времени путем автоматизации процесса тестирования;
оптимизации процесса тестирования;
обработки и анализа результатов тестирования.
Целью диссертационной работы является сокращение времени тести-
рования мобильных устройств за счет разработки математического и программного аппарата. Для достижения поставленных целей необходимо решить задачи:
проанализировать существующие системы и стандарты на тестирование мобильных устройств;
разработать требования к системам производящих автоматическое тестирование;
разработать систему автоматического контроля (обосновать принципы и методы построения, используемых технологий);
решить задачи оптимизирования тестирования (задача о минимизации времени тестирования, минимизация времени на подготовительный этап тестирования);
проанализировать вероятностные характеристик тестирующей системы;
разработать требования к программному обеспечению для тестирования мобильных устройств.
В диссертационной работе использованы методы и технологии компьютерной техники, электроники, теории графов, методы оптимизации, элементы теории массового обслуживания. Приведен и реализован метод автоматического тестирования. При программной реализации предлагаемых методов и алгоритмов использованы технологии объектного, структурного и модульного программирования.
Научная новизна работы заключается в следующем:
разработаны основные требования к системам, производящим автоматическое тестирование мобильных устройств;
создана система автоматического контроля эффективного тестирования мобильных устройств;
разработана методика проверки, оценки результатов и принятия решения об эффективности результатов проверки;
разработано программное обеспечение, позволяющее производить автоматизированную проверку аппаратно-программных частей различных типов устройств.
решены основные проблемные задачи тестирования мобильных устройств: задачи о минимизации времени тестирования, минимизации времени на подготовительный этап тестирования;
предложен метод вычисления вероятностных характеристик тестирующей системы, который позволяет выносить суждение о избыточности или недостаточности тестирования, делать прогнозы с определенной вероятностью достоверности.
Работа затрагивает анализ существующих разработок в данной области и анализ существующих стандартов. Для оптимизационных решений используются кластерные технологии миграции процессов. Определен способ подключения устройств к САК. Загрузка, процесс тестирования и
процесс предоставления результатов. Устранены ограничения присутствующие в существующий системах автоконтроля.
Анализ специфики разработки программных средств
Разработке программных средств для мобильных устройств присущ ряд специфических особенностей [6]:
1. Прежде всего следует отметить некоторое противоречие: неформальный характер требований к ПС (постановки задачи) и понятия ошиб
ки в нем, и формализованный основной объект разработки - программы ПС. Тем самым разработка ПС содержит определенные этапы формализации; а переход от неформального к формальному существенно неформален.
2. Разработка ПС носит существенно творческий характер (на каждом шаге приходится делать какой-либо выбор, принимать какое-либо решение) . а не сводится к выполнению какой-либо последовательности регламентированных действий. Тем самым эта разработка ближе к процессу проектирования каких-либо сложных устройств, но никак не к их массовому производству. Этот творческий характер разработки ПС сохраняется до самого се конца;
3. Следует отметить также особенность продукта разработки. Он представляет собой некоторую совокупность текстов (т.е. статических объектов), смысл же (семантика) этих текстов выражается процессами обработки данных и действиями пользователей, запускающих эти процессы (т.е. является динамическим). Это предопределяет выбор разработчиком ряда специфичных приемов, методов и средств.
4. Продукт разработки имеет и другую специфическую особенность: ПС при своем использовании (эксплуатации) не расходуется и не расходует используемых ресурсов. 1.3. Понятие качества программного средства.
Каждое ПС должно выполнять определенные функции, т.е. делать то, что задумано. Хорошее ПС должно обладать еще целым рядом свойств, позволяющим успешно его использовать в течении длительного периода, т.е. обладать определенным качеством. Качество ПС - это совокупность его черт и характеристик, которые влияют на его способность удовлетворять заданные потребности пользователей [И]. Это не означает, что разные ПС должны обладать одной и той же совокупностью таких свойств в их высшей возможной степени. Этому препятствует тот факт, что повышение качества ПС по одному из таких свойств часто может быть достигнуто лишь ценой изменения стоимости, сроков завершения разработки и снижения качества этого ПС по другим его свойствам. Качество ПС является удовлетворительным, когда оно обладает указанными свойствами в такой степени, чтобы гарантировать успешное его использование.
Совокупность свойств ПС, которая образует удовлетворительное для пользователя качество ПС, зависит от условий и характера эксплуатации этого ПС. т,е. от позиции, с которой должно рассматриваться качество этого ПС. Поэтому при описании качества ПС должны быть прежде всего фиксированы критерии отбора требуемых свойств ПС. В настоящее время критериями качества ПС принято считать [11-14]: функциональность, надежность, легкость применения, эффективность, сопровождаємость, мобильность.
Функциональность - это способность ПС выполнять набор функций, удовлетворяющих заданным или подразумеваемым потребностям пользователей. Набор указанных функций определяется во внешнем описании ПС.
Надежность - это способность безотказно работать при меняющейся нагрузке в течении определенного временного интервала.
Рассмотрим теперь общие принципы обеспечения надежности ПС, что является основным мотивом разработки ПС, задающим специфическую окраску всем технологическим процессам разработки ПС. В технике известны четыре подхода обеспечению надежности [15]: предупреждение ошибок; само-обнаружение ошибок; само-исправление ошибок; обеспечение устойчивости к ошибкам. Целью подхода предупреждения ошибок - не допустить ошибок в готовых продуктах, в нашем случае - в ПС.
Использование общей файловой системы NFS .
Последний вид, вычислительный кластер, используется специально для центров обработки информации, которым необходима максимально возможная производительность. К подобным системам относится система Beowulf, разработанная именно для исследовательских центров, нуждающихся в большой скорости вычислений. В таких системах также присутствует некоторая функция балансировочных кластеров: для повышения производительности они стараются распределить процессы на большее количество машин. Только в данном случае процесс распараллеливается на части, которые выполняются на многих машинах одновременно, вместо того чтобы выполняться друг за другом по очереди.
Модели кластеров
Существует несколько технологий реализации параллельных вычислений: (N)UMA, DSM, PVM и MPI - всё это различные схемы параллельных вычислений. Некоторые из них уже реализованы аппаратгго. другие только в программном, а некоторые - и в том, и в другом виде.
(N)UMA: здесь машины пользуются разделяемым доступом к памяти, в которой они могут выполнять свои программы. В ядре Linux реализована поддержка NUMA, позволяющая получать доступ к раз ным областям памяти. При этом задача ядра использовать ту память, которая находится ближе к процессору, работающему с ней. DSM уже реализована пе только в программном виде, но и в аппаратном. Основная концепция DSM в организации абстрактного слоя для физически распределённой памяти. Технологии PVM и MPI наиболее часто упоминаются, когда речь заходит о GNU/Linux Beowulf кластерах. MPI - это открытая спецификация библиотеки передачи сообщений. Самой популярной реализацией МРЇ является MPICH. Второй по популярности после MPICH можно назвать LAM, также являющейся свободной реализацией MPI. PVM - ещё один «родственник» MPI, широко используемый при создании Beowulf. PVM работает как пользовательская программа, поэтому никаких изменений в ядро системы вносить не нужно - выходит, что любой пользователь с минимальными правами может запустить PVM.
Программный пакет openMosix позволяет превратить в кластер компьютеры под управлением GNU/Linux, объединённые в сеть. Такой кластер позволит автоматически балансировать нагрузку на узлах, при этом новые узлы могут присоединяться или покидать кластер без прерывания его работы. Нагрузка на узлы распределяется исходя из скорости соединения и мощностей процессоров.
Поскольку openMosix является частью ядра и полностью совместим с Linux, то и все пользовательские программы, файлы и прочие ресурсы будут работать также, как и раньше, без каких-либо изменений. Простой пользователь даже не заметит разницы между Linux и openMosix системой. В целом картину можно представить, как будто весь кластер работает как одна (быстрая) GNU/Linux система. openMosix представляет собой патч для ядра Linux, который, тем не менее, обеспечивает полную совместимость с платформой IA32. Благодаря внутреннему механизму балансировки нагрузки процессы могут мигрировать на другие узлы кластера. В результате получается выигрыш в производительности при использовании ресурсов нескольких машин. К тому же кластер постоянно самостоятельно пытается оптимизировать обработку процессов (естественно, что администратор системы может вмешаться в процесс автобалансировки в любое время).
Такой механизм прозрачной миграции процессов позволяет представить кластер как одну большую SMP-систему с множеством процессоров на доступных узлах кластера (конечно, следует учитывать и количество процессоров в двух и четырёх процессорных системах). К тому же openMosix предоставляет оптимизированную файловую систему (oMFS) для НРС-приложений, которая, в отличие от NFS, поддерживает кэширование, отметки о времени и ссылки.
Анализ эффективных алгоритмов нахождения кратчайших путей
Используется два способа представления графа G=(V,E) - как набор списков смежных вершин или как матрицу смежностей. Первый обычно предпочтительнее, ибо дает более компактное представление для разреженных графов - тех, у которых Е\многоменьшеV2 . Списки смежных вершин удобны для хранения графов с весами, в которых каждому ребру прописан некоторый вещественный вес. При представлении графа в виде списка смежных вершин используется массив Adj из V списков - по одному на вершину. Недостатком списков смежных вершин является то, что если необходимо узнать если ли в графе ребро из и в v, приходится просматривать весь список Adj[u] в поисках и. Кратчайшие пути методом рекурсивного перебора
Рассмотрим алгоритм нахождения самого длинного пути в графе. На вход функции подается граф (например таким способом, как показан выше) ; начальная вершина для поиска и конечная вершина. Результатом выполнения функции будет являться список состоящий из узлов графа, при чем список подобран таким образом, что сумма ребер данных узлов будет максимальной. Схематично данный алгоритм можно представить следующим образом (Рис 3.3):
Обратим внимание, что если в данном алгоритме условие выделенное пунктиром, изменить на противоположное, то мы автоматически получаем алгоритм для нахождения самого длинного пути в графе. Заметим, что число интерраций выполнения алгоритма остается прежним. Следовательно временная оценка эффективности данного алгоритма, не будет зависеть от того какое значение из 2-х мы пытаемся найти.
Реализацией данного алгоритма на языке Python будет явятся следующий код: def find„longest_path(graph, start, end, path=[]): path = path + [start] if start == end: return path if not graph.has_key(start): return None longest = None for node in graph[start]: if node not in path: newpath = find_longest_path(graph, node, end, path) if newpath: if not longest or lenCnewpath.) lenQongest) : longest = newpath return longest Кратчайшие пути и умножение матриц Отметим, что отрезки кратчайшего пути сами являются кратчайшими путями между соответствующими вершинами. Рекурсивная формула для; длины кратчайшего пути Пусть Щ обозначает минимальный вес пути из вершины і в вершину j, если рассматривать пути с не более чем m ребрами. При m = 0 допустимы лишь 1пути"воЕсе без ребер, т.е. О, еслш — 7, DM ) (3.2) со, еслш ф j. Если же m 1 , то минимальный вес Щ достигается либо на пути из не более чем т-1 ребра ( и тогда равен сС-1, либо же на пути из m ребер. В последнем случае этот путь можно разбить на начальный отрезок из т-1 ребер, ведущий из начальной вершины і в некоторую вершину к, и на последнее ребро (к, j). Мы приходим к формуле: d[f = mm{df 1], mm d{ l) + whj) = mm d{ i} + wkj (3.3) J l k n l k n (Последнее равенство использует равенство w[ij] = 0).
Если граф не содержит циклов с отрицательными весами, кратчайший путь можно выбирать без циклов, такой путь содержит не более п-1 ребер.
Функциональная схема программы проверки драйверов ввода-вывода
Хост часть состоит из сервера-обработчика пользовательских скриптов. Пользовательский скрипт в целом соответствует плану тестирования. Он оперирует следующими сущностями:
1. объект "драйвер либо локальный драйвер (хостовый), либо удаленный драйвер (данный объект общается через XML-RPC с реальным драйвером па таргете). Это полезно в случае, если нужно протестировать, например, два com-порта, один из которых на таргете, а другой на хосте. Или же, можно протестировать два corn-порта между двумя таргетами.
2. объект "тест соответствует отдельному тесту плана тестирования (testcase ). При инициализации данного объекта ему передаются ссылки на объекты драйверов, таким образом ему все равно, драйвер у него локальный или удаленный, т.е. интерфейс общения с драйвером унифицирован.
В задачу скрипта входит создать через XML-RPC объекты драйверов на таргете, создать локальные драйвера на хосте и создать объекты тестов, проинициализировав их от нужных драйверов, запустить эти тесты и собрать результаты.
Диаграмма классов и их взаимодействие представлены на рисунке. На таргете требуется только наличие python и таргет-части (демона). Драйвера загружаются на таргет автоматически в процессе работы самим демоном. Из дополнительных библиотек требуется только установленная р expect. В приложении 2 приведено: 1. пример скрипта, который запускает ethernet-тест между хостом и таргетом; 2. пример теста Ether Test 3. пример драйвера EtherDevice
Путем использования технологии python/xmlrpc достигается максимальная гибкость и модульность системы. При изменении конфигурации тестового окружения (например, физическое соединение между хостом и устройством меняется на соединение между устройством и устройством) изменения в исходных текстах затронут только скрипт, а драйвера и тесты остаются неизменными, т.е. достигается высокое повторное использование кода для разных платформ и конфигураций без каких-либо существенных изменений. Фактически, скрипт после этого можно рассматривать исключительно как конфигурационный файл, который есть реализация плана тестирования.
Система может быть построена таким образом, что она сама при первом запуске компилирует нужную версию python для таргета и ставит со на таргет в локальную директорию (например, в домашнюю директорию какого-либо пользователя, который будет использоваться для процесса тестирования).
Использование базы данных
Результаты тестирования очень важны, но как сделать их более эффективными? Об этом и пойдет речь в этой главе.
Предполагается, что у вас есть набор тестов, которые представляют из себя программу, выводящую слово PASS, если тест прошел или слово FAIL, если тест не прошел. Требуется собирать статистику относительно пройденных и не пройденных тестов и отображать ее результаты. Наиболее целесообразным является хранить статистику в базе данных. Например MySql. Ваза должна содержать примерно следующий вид: 1. время проведения теста 2. название тестируемой программы 3. номер теста 4. статус PASS - если тест прошел, и FAIL - если тест не прошел. 5. релиз статус При разборе данной таблицы можно вывести следующие результаты: 1. Время, занимаемое тестированием данной программы. 2. Определить трудные тесты, которые чаще всего не проходят.
3. Определить вероятность прохождения тестов.
4. Определить скорость запуска тестов (количество пройденных или не пройденных тестов за день.
