Методы измерения и оценки временных характеристик алгоритмов : На примере распределенной вычислительной сети

• Автор: Селькин, Михаил Владиславович
• Шифр специальности: 05.11.16
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Тула
• Количество страниц: 181 с. : ил.

Содержание
ВВЕДЕНИЕ
1. РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ. МЕТОДЫ ИЗМЕРЕНИЯ И ОЦЕНКА ВРЕМЕННЫХ ХАРАКТЕРИСТИК
Введение
1.1. Распределенная вычислительная сеть. Основные определения
1.2. Действия пользователя в распределенной вычислительной сети
1.3. Семиуровневая сетевая архитектура распределенной вычислительной сети
1.4. Наиболее часто применяемые структуры РВС
1.5. Описание различных подходов к измерению временных интервалов в распределенной вычислительной сети
Выводы
2. МЕТОДЫ ИССЛЕДОВАНИЯ АЛГОРИТМОВ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТЕ
Введение
2.1. Модель описания алгоритмов в виде полумарковского процесса :
2.2. Структурный анализ алгоритмов распределенной вычислительной сети
2.3. Статистическое распределение времени реакции пользователя
2.4. Обобщенная функция плотности распределения времени реализации алгоритма в отдельном узле распределенной вычислительной сети
2.5. Оценка функции плотности распределения вероятности времени
реализации отдельной траектории
2.5.1. Экспоненциальный закон
Выводы
3. МЕТОДЫ АППРОКСИМАЦИИ РЕЗУЛЬТИРУЮЩЕГО ЗАКОНА ПЛОТНОСТИ РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТИ ВРЕМЕНИ ИСПОЛНЕНИЯ АЛГОРИТМА В РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ
Введение
3.1. Постановка задачи аппроксимации результирующего закона пдотности' распределения вероятности времени исполнения алгоритма

3.2. Аппроксимация результирующего закона плотности распределения вероятности времени исполнения алгоритма экспоненциальным законом
3.3. Аппроксимация результирующего закона плотности распределения
вероятности времени исполнения алгоритма нормальным законом
3.4. Оценка ошибки аппроксимации результирующего закона плотности распределения вероятности времени исполнения алгоритма
3.4.1. Ошибка аппроксимации экспоненциальным законом
3.4.2. Ошибка аппроксимации нормальным законом
Выводы
4. ПРОГРАММНЫЙ КОМПЛЕКС АНАЛИЗА ВРЕМЕННЫХ ХАРАКТЕРИСТИК , АЛГОРИТМОВ И ПРОГРАММ
Введение
4.1. Описание экспериментальной установки
4.2. Программа поиска траекторий алгоритмов
4.3. Программа исследования характеристик траекторий алгоритмов
4.4. Экспериментальное определение оценочных значений величин времени реакции пользователя
Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ!
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ
Актуальность темы. Современный этап развития сетей ЭВМ и средств телекоммуникаций характеризуется увеличением количества пользователей распределенных вычислительных сетей [1-4]. Этот процесс наблюдается во многих сферах деятельности человека: при комплексировании систем автоматизации проектирования, АСУ технологическими процессами, сбора, хранения и анализа информации в медицинских учреждениях [53-56], робототехнических-систем [16], конторских и банковских систем. С увеличением числа пользователей распределенных во времени и пространстве систем обработки, хранения и анализа данных возникает ряд проблем, что снижает эффективность использования распределенной вычислительной сети. Эти проблемы связаны с упорядочиванием обработки большого количества заявок [5-7]. В формировании потока заявок участвуют пользователи, программное обеспечение распределенной вычислительной сети и сама распределенная вычислительная сеть. В указанной ситуации возникает задача повышения эффективности использования распределенных вычислительных сетей [8-10], которая решается путем измерения в распределенной вычислительной сети и оценкой временных характеристик алгоритмов работы пользователя и программного обеспечения.
Перечисленные выше обстоятельства обусловили выбор объекта исследования диссертации, который может быть охарактеризован как распределенная вычислительная сеть, т.е. совокупность территориально распределенных ЭВМ, соединенных с помощью одной или большего числа линий связи, осуществляющих первичную обработку, накопление и организацию множественного доступа к сформированному массиву данных [3].
Неотъемлемой частью задачи повышения эффективности использования распределенных вычислительных сетей является задача измерения и оценки временных характеристик их программного обеспечения с учетом ра-

Роо Рої Ро2 '' ‘
Рю Рп Рц

Рю Рп Р
Рассмотрим переходные вероятности за п шагов
Р?=Р{Хп+т=]Хт=1}, п> О, /,У > 0 . (1.10)
Уравнения Чемпена-Колмогорова [3, 12-13], которые позволяют вычислить РЦ имеют вид

Г'ВД".-. и*0 (мі)

Из этих уравнений видно, что Р? является' элементом матрицы Рп
(матрицы переходных вероятностей Р, возведенной в степень п). *
В качестве применения уравнений глобального баланса рассмотрим цепь Маркова, типичную для систем массового обслуживания и более общих систем как системы рождения и гибели, в которых два последовательных состояния могут отличаться только на единицу, как показано на рис. 1.9.
Рис. 1.9. Диаграмма переходных вероятностей процесса рождения и гибели
Р]р], = Р,Р и*0 0-12)
Уравнения (1.12) известны как уравнения детального баланса [3]. Эти уравнения не обязательно справедливы для любой цепи Маркова. Однако во многих частых случаях они справедливы и сильно упрощают вычисления стационарного распределения. При доказательстве справедливости уравне-