Содержание к диссертации
Введение
1. Проблемы управления перемещением заданий в распределенном межмодульном взаимодействии 10
1.1. Оценка производительности вычислительных систем как задача моделирования 10
1.2. Управление распределенными базами данных и их целостностью 12
1.3. Инструменты разработки, внедрения и сопровождения информационных систем, реализованных на основе Oracle 17
1.4. Постановка задач работы 29
2. Техника анализа для организации очереди в сетях со стратегией смешанных приоритетов и переключением класса 31
2.1. Исследование сети с переключением класса 31
2.2. Пример сети с переключением класса и стратегией смешанных приоритетов 48
2.3. Анализ мобильных информационных сетей с обслуживанием мультимедиа заявок 54
2.4. Выводы 62
3. Управление перемещением заданий в системе управления загрузкой многопроцессорной системы 66
3.1. Балансировка нагрузки и динамические задачи 66
3.2. Проактивная балансировка нагрузки и агентное управление заданиями 68
3.3. Алгоритмизация процессов управления перемещением заданий между процессорами в распределенной информационной системе 75
3.4. Верификация и численное моделирование алгоритмов управления перемещением заданий в распределенной информационной системе 83
3.5. Алгоритмизация повышения отказоустойчивости 94
3.6. Выводы 98
4. Информационное и программное обеспечение средств автоматизации контроля структуры и объектов территориально распределенных баз данных 103
4.1. Задачи и потоки 103
4.2. Информационное и алгоритмическое обеспечение средств автоматизации контроля структуры и объектов территориально распределенных баз данных 105
4.3. Особенности реализации распределенного программного обеспечения 119
4.4. Выводы 128
Основные результаты работы 129
Список использованных источников
- Инструменты разработки, внедрения и сопровождения информационных систем, реализованных на основе Oracle
- Пример сети с переключением класса и стратегией смешанных приоритетов
- Алгоритмизация процессов управления перемещением заданий между процессорами в распределенной информационной системе
- Информационное и алгоритмическое обеспечение средств автоматизации контроля структуры и объектов территориально распределенных баз данных
Введение к работе
Актуальность темы
Эффективно применяемый метод оценки производительности вычислительных систем - аналитическое моделирование, основанное на организации очереди в сетях, так как они детально исследованы. Для так называемой формы организации очереди в сетях существуют эффективные, точные и приближенные алгоритмы анализа, но чаще всего, организация очереди в сетях для реальных систем неполностью соответствует требованиям аналитических инструментов, например, в случае разноприоритетных очередей. Обычно используется метод Маркова или дискретное моделирование. Проблема в том, что требуется много времени для подготовки, осуществления и выполнения, особенно, когда необходим анализ системы с большим количеством параметров.
Однако результаты анализа в условиях современных баз данных требуют осторожного применения. Так, задача синхронизации баз данных возникает при наличии двух версий проекта - локальной "для разработчиков" и published-версии "для пользователей", когда нужно определить, что именно изменили разработчики в локальной версии базы данных, и перенести эти изменения в published-версию. Часто бывает так, что таблицы, поля, внешние ключи и ограничения создаются и изменяются хаотически, за ссылочной целостностью никто не следит, и никто не может точно сказать, чем же база данных на итерации N отличается от ее состояния на итерации N-1.
Информационное обеспечение автоматизированных систем обработки оперативной информации для фирм, имеющих территориально распределенные филиалы, требует специального контроля. Периодически возникает задача проведения глобальной модификации структуры таблиц базы данных в связи с изменением используемых приложений по обработке данных. Для нормального жизненного цикла информационной системы и необходима программная система автоматизации контроля структуры и объектов территориально распределенных баз данных.
Таким образом, актуальной является задача создания математического описания средств анализа замкнутой организации систем на основе преобразования классов в цепи с использованием компенсирующего вариабельность времени обслуживания коэффициента, а также разработка и практическое применение алгоритмического и программного обеспечения управления перемещением заданий в распределенном межмодульном взаимодействии, специализированной программы для автоматизации контроля структуры и объектов территориально распределенных баз данных на основе агентного параллелизма.
Работа выполнена в ФГБОУ ВО «Воронежский государственный технический университет» в рамках научного направления «Вычислительные комплексы и проблемно-ориентированные системы управления».
Цель работы заключается в разработке математического и программного
обеспечения управления перемещением заданий в распределенном межмодульном взаимодействии на основе стратегий смешанных приоритетов с переключением классов для повышения производительности системы.
Для достижения поставленной цели в диссертационной работе сформулированы следующие задачи:
предложить метод анализа смешанной организации систем, обеспечивающий для высоконагруженного узла корректное моделирование процессов при использовании узла только для открытых классов;
предложить теневой метод анализа систем с вытесняющей стратегией обработки приоритетных заданий, обеспечивающий асимптотически точные результаты анализа;
разработать алгоритмы работы агентного управления заданиями, обеспечивающие корректный выбор процессоров и заданий для перераспределения;
разработать проактивные алгоритмы распределенной балансировки нагрузки при реконфигурации, и обеспечивающие работоспособность системы в ситуациях штатных или нерегламентированных отказов оборудования;
разработать информационное и программное обеспечение программы автоматизации контроля структуры и объектов территориально распределенных баз данных на основе агентного параллелизма.
Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы методы математического моделирования, оптимизации, теории вероятностей и математической статистики, технологии объектно-ориентированного программирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.11: п. 3 «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем»; п.9 «Модели, методы, алгоритмы и программная инфраструктура для организации глобально распределенной обработки данных».
Научная новизна. В работе получены следующие результаты, отличающиеся научной новизной:
модифицированная техника анализа замкнутой организации систем, отличающаяся преобразованием классов в цепи с использованием компенсирующего вариабельность времени обслуживания коэффициента, причем количество заданий является константой в цепи, но в пределах цепи задание может переключиться в другой класс;
технология анализа смешанной организации систем, отличающаяся заменой основного распределенного источника в замкнутой сети -/G/1-узлом и обеспечивающая для высоконагруженного узла корректное моделирование процессов при использовании узла только для открытых классов;
теневой метод анализа систем с вытесняющей стратегией обработки приоритетных заданий, обеспечивающий асимптотически точные результаты анализа и отличающийся разбиением узлов в системе на параллельные подузлы
с итеративным увеличением времени обслуживания для каждого класса задания в теневом узле;
эвристические алгоритмы работы агентного управления заданиями, основанные на кворумальном множестве в задачах взаимного исключения и методах назначения арбитра, обеспечивающие корректный выбор процессоров и заданий для перераспределения;
проактивные алгоритмы распределенной балансировки нагрузки при реконфигурации, отличающиеся гибким выбором процессора-координатора и обеспечивающие работоспособность системы в ситуациях штатных или нерег-ламентированных отказов оборудования;
структура информационного и программного обеспечения программы автоматизации контроля структуры и объектов территориально распределенных баз данных, отличающаяся учетом загруженности компонент межмодульного взаимодействия во время осуществления транзакций и обеспечивающая повышение производительности системы за счет агентного параллелизма.
Практическая значимость заключается в создании интегральной технологии исследования стратегии смешанных приоритетов с переключением классов, в которой время вычислений может быть значительно уменьшено, особенно когда система должна быть проанализирована на большом диапазоне параметров, по сравнению с методом Маркова или с имитационным моделированием с выигрышем до 25 раз в модельном примере.
Создана программная система контроля целостности мультиверсионных информационных систем, основанная на естественной системной поддержке Oracle симметричных многопроцессорных систем, кластеров, систем с массовым параллелизмом и обеспечивающая автоматизацию контроля структуры и объектов территориально распределенных баз данных, однозначное соответствие текущей версии структуры базы данных.
Реализация и внедрение результатов работы. Результаты исследований используются в системе управления информационной системой университета (Технологический университет, г. Хо Ши Мин, г.Ханой, Вьетнам) для обеспечения устойчивости и актуальности распределенной базы данных.
Основные результаты работы внедрены в учебный процесс Воронежского государственного технического университета в рамках дисциплин: «Вычислительные машины, системы и сети», «Информационные сети и телекоммуникационные технологии», при выполнении курсового и дипломного проектирования.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: XII Международной научно-практической конференции «Современные инструментальные системы, информационные технологии и инновации» (Курск, 2015), Международной научно-практической конференции «Advanced models and technologies in computer networks» (Yelm, WA, USA, 2015), XXI Международной открытой научной конференции «Modern informatization problems in the technological and telecommunica-
tion systems analysis and synthesis» (Yelm, WA, USA, January 2016), Международной летней и зимней научных школах «Парадигма» (Варна, Болгария, 2015, 2016), а также на конференциях профессорско-преподавательского состава Воронежского государственного технического университета (Воронеж, 2014-2016).
Публикации. По теме диссертационного исследования опубликовано 13 печатных работ, из них 4 статьи в изданиях, рекомендованных ВАК РФ, одно свидетельство о регистрации программы для ЭВМ, 8 статей в журналах и материалах Международных и Всероссийских конференций и форумов. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: модифицированная техника анализа замкнутой организации систем, отличающаяся преобразованием классов в цепи с использованием компенсирующего вариабельность времени обслуживания коэффициента [6, 9]; технология анализа смешанной организации систем, обеспечивающая для высо-конагруженного узла корректное моделирование процессов [11, 13]; теневой метод анализа систем с вытесняющей стратегией обработки приоритетных заданий, обеспечивающий асимптотически точные результаты анализа [12]; эвристические алгоритмы работы агентного управления заданиями, обеспечивающие корректный выбор процессоров и заданий для перераспределения [2, 10]; проактивные алгоритмы распределенной балансировки нагрузки при реконфигурации, обеспечивающие работоспособность системы в ситуациях штатных или нерегламентированных отказов оборудования [3, 8]; структура информационного и программного обеспечения программы автоматизации контроля структуры и объектов территориально распределенных баз данных [5, 13].
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав с заключением и выводами. Работа содержит 142 страницы. Список использованной литературы включает 116 наименований.
Инструменты разработки, внедрения и сопровождения информационных систем, реализованных на основе Oracle
Реляционные базы данных применяются сегодня практически во всех приложениях, начиная от встроенных в мобильные и специальные устройства, Web-приложений и заканчивая системами управления предприятия. Проникновение баз данных во все виды приложений идет нарастающими темпами, а разработчики получают все более удобные в использовании инструменты и подходы.
Перед каждым разработчиком рано или поздно встаёт задача сравнения двух баз данных. Особенно часто задача синхронизации баз данных возникает при наличии двух версий проекта - локальной "для разработчиков" и published-версии "для пользователей", когда нужно определить, что именно изменили разработчики в локальной версии базы данных, и перенести эти изменения в published-версию. Часто бывает так, что таблицы, поля, внешние ключи и ограничения создаются и изменяются хаотически, за ссылочной целостностью никто не следит, и никто не может точно сказать, чем же база данных на итерации N отличается от ее состояния на итерации N-1.
Для решения проблемы синхронизации различных баз данных используются различные методы (обзор дан по Н.С.Рябкову): - репликация баз данных – процесс синхронизации данных и структуры различных баз данных. Это автоматизированный процесс, основанный на бинарном логе основного сервера БД; - синхронизация данных и структуры различных баз данных с использованием дампа (dump) основной БД; - использование различных утилит для сравнения баз данных и выявления недостающих таблиц, полей, индексов, хранимых процедур, функций и т.п. В большинстве случаев при разработке программного обеспечения возникает проблема синхронизации структуры баз данных, в этих случаях на помощь приходят утилиты для сравнения структур БД. Написание собственной утилиты направлено на реализацию недостающих возможностей в уже существующих утилитах.
Чтобы система репликации работала корректно, необходим корректно работающий алгоритм определения данных, которые необходимо передать между двумя узлами. Этот алгоритм является одной из ключевых характеристик систем репликации. Рассмотрим различные алгоритмы обнаружения (или захвата) изменений. Здесь рассматриваются алгоритмы, которые в результате своей работы гарантированно синхронизируют две базы данных (при условии штатной работы системы и отсутствия изменений во время сеанса обмена данными).
Полная передача таблиц Этот подход является вырожденным случаем обнаружения изменений, когда реально не происходит никакого захвата изменений, а таблица передается целиком уже во время сеанса репликации. Гипотетически такой подход может быть применим только для случаев, когда узлы связаны между собой очень быстрым каналом передачи данных. На практике он практически не используется из-за слишком неэффективного использования ресурсов. Транзакция с применением дубля таблицы целесообразна при старте интеракции между процессами, иначе говоря – в процессе стартового ремотного клонирования. Достоинства: - сравнительно несложные программные конструкции. Недостатки: - ресурсоемкая реализация, и, как следствие, неприемлемость применения в реально существующих информационно-вычислительных системах. Обнаружение изменений при помощи двойного копирования таблиц Данный подход состоит в том, что после каждого сеанса реализации запроса осуществляется дублицирование таблицы как локально, так и на удаленном источнике. Такой дубликат фиксируется до реализации следующего сеанса. В результате состояния «до» и «после» фиксируются и версии базы данных потенциально сравнимы.
Достоинства: - описание БД и основополагающие элементы программной реализации неизменны; - гарантируется полнота обнаружения всех мыслимых коррекций, как бы они не производились. Недостатки: - полное дублирование БД, ведущее к нерациональному расходованию ресурсов носителей; - чрезмерная загрузка каналов распределенной информационно-вычислительной системы в ситуации восстановлении исходных данных, поскольку необходима передача полного объема базы. Промежуточный уровень доступа к базе данных В описываемой ситуации вводится новый интерфейс, который имеет доступ и к логике приложения, и к средствам управления данными. Все транзакции по сути фиксируются в отдельно создаваемой таблице коррекций для каждой корректируемой таблицы данных в процессе осуществления транзакций. Достоинства: - инфологическая модель данных остается неизменной, что улучшает устойчивость системы. Недостатки: - введение нового интерфейса, первоначально не спроектированного для конкретной задачи, порождает существенные проблемы верификации; - журнализация транзакций, проводимых в обход нового интерфейса инструментами, которые специально для этого спроектированы, не осуществляется – что влечет за собой высоковероятную потерю как целостности данных, так и существования системы в целом.
Пример сети с переключением класса и стратегией смешанных приоритетов
Рассмотрена универсальная техника анализа для организации очереди в сетях со стратегией смешанных приоритетов и переключением класса. Раздел 2.1 вводит понятие цепей для открытых, закрытых и смешанных сетей с переключением класса. Цель: получить метод решения для любого типа стратегии смешанных приоритетов «с» и «без» переключения класса. Теневой метод вводится и распространяется для открытых, закрытых и смешанных сетей с переключением класса и смешанными приоритетами. В разделе 2.2 метод применяется к простой непродуктивной форме сети, которая содержит вышеуказанные проблемы. Показывается, как эта сеть может быть превращена в продуктивную форму сети и решена с использованием стандартного метода анализа. Представленные методы продемонстрированы в разделе 2.3 на примере мобильных информационных систем с услугами мультимедиа.
Используемые обозначения: N - число узлов в сети R - число заданий классов kir - номер класса r задания в узле i k - вектор заполнения (k1,k2,K,kR ), где kr число заданий в классе r (1 r R) в сети K - число заданий в закрытой сети (k -1r ) - вектор заполнения с одним удаленным заданием класса r mir - скорость обслуживания задания класса r в узле i sir =1/mir - время обслуживания задания класса r в узле i sir приближенное время обслуживания задания класса r в узле i в теневой сети l - скорость поступления задания класса r в узле i m І число серверов в узле i pir . вероятность того, что задание класса г переместится в класс s на узел f после завершения обслуживания в узле і eir. среднее число визитов заявок класса г в узле і j=lZjs=iejs Pjs,ir pir - удаление узла і заданием класса г pir = Air /(m; fih) tir - значимость времени задания класса г в узле і
Каждый узел имеет собственный набор вероятностей перехода, который характеризует переход на другие узлы и классы. Это означает, что задание может не только переключиться на другой узел, но также в другой класс задания, пока он в системе. В этом случае, количество заданий в классе не постоянно, как это бывает, когда переключение класса недоступно. Для модели организации без переключения класса необходимо выполнение следующих четырех условий [2.4]: 1. количество заданий в каждом классе в каждом узле всегда неотри цательно, т.е. kir OVl r RAl i N. 2. для всех заданий должно выполняться следующее условие: kir 0 здесь существует путь для заданий класса г в узел і с вероятностью большей 0. 3. число заданий в сети вычисляется к=ІІк,г. Г=1 i=l 4. сумма заданий класса г в сети постоянна за некоторое время N kr=kir=const.Vl r R І=І Эти сети могут быть разрешены использованием любого стандартного алгоритма анализа для сетей без переключения класса (например, MVA, свертка, SCAT). Если переключение класса допускается, выполняются все условия кроме 4, поскольку количество заданий в пределах класса не постоянно, а зависит от времени наблюдаемой системы и может иметь любую величину хє{0...К}. В целях предотвращения этой ситуации введено понятие цепей [2.4].
Рассмотрим общую матрицу вероятности перехода P = pirjJ, і, j = 1.. .N и r, s = 1.. .R с конечным пространством состояний Г. Это пространство состояний может быть разделено непересекающимися множествами Г = Г\ + Г2 +... + Гv с Г; - множеством периодических состояний. С возможной сменой состояний, мы рассматриваем матрицу вероятностей перехода рис. 2.1, где подматрицы Р содержат вероятности перехода в множестве Г;, и каждая Р; - непересекающаяся и эргодическая. Пусть цепь С; обозначает множество классов в Г;. В связи с непересекаемостью цепей С;, задание не может переключиться с одной цепи на другие. С этим методом разметки количество заданий в каждой цепи всегда постоянно. Следовательно, условие 4 для организации сетей выполняется для каждой цепи. В [2.8] доказано, что организация закрытой сети с U цепями эквивалентна организации закрытой сети с классами U заданий. Если переключение класса невозможно в сети, то количество цепей эквивалентно количеству классов. Но, если переключение класса возможно, то количество цепей меньше чем количество классов. Это означает, что размерность вектора заполнения понижается. Для согласованности, будем использовать ту же запись классов для цепей, но со звездочкой.
Алгоритмизация процессов управления перемещением заданий между процессорами в распределенной информационной системе
Изучаемая система включает N ячеек, каждая ячейка имеет m радиоканалов. Система телекоммуникации включает три типа обслуживания для требований пользователей мобильных сетей: первый тип обслуживания: в основном речевой трафик, который требует узкого диапазона соединения. Это один радиоканал. второй тип обслуживания: удовлетворяет потребности информа ционного взаимодействия с широким диапазоном соединений, которые в основном требуют сd каналов. третий тип обслуживания: поддержка мультимедиа соединений, сформированных из компонента информации и речевого компонента, ко торые должны управляться вместе. Этот тип соединения требует cd +1 ка налов. Запрос обслуживания от мобильного пользователя на базовой станции любой ячейки может быть обусловлен как генерацией нового звонка, так и запросом передачи из другой ячейки. Поскольку неудачи пересылки застают завершение соединения в процессе, считается, что эти события могут быть хуже, чем блокирование нового звонка, эффект которого только в повторении запроса доступа пользователя в последующее время. Следовательно, многие механизмы предложены в литературе [2.9, 2.11], что определяет приоритеты схем, которые резервируют каналы в каждой ячей ке для запросов передачи. В примере допустим, что система ячеек использует технику прерывания соединений мультимедиа, предложенную в [2.7]. Когда требуется передача мультимедийного соединения, базовая станция пытается разместить целый вызов, но, если это невозможно, два компонента вызова могут быть разорваны: речевое соединение, по возможности, принимается, пока информационное соединение временно приостанавливается, ожидая продолжения, как только будет доступно достаточно каналов в ячейке, чтобы обслуживать целый вызов мультимедиа.
Поскольку соединения мультимедиа требуют самого высокого количество каналов, нарушение связи из-за частично обслуживаемых передач может улучшить качество обслуживания, т.к. оно позволяет пользователю продолжить по крайней мере часть связи. В дальнейшем, хотя информационное соединение приостанавливается, пользователю дан шанс, чтобы продолжить его позже с той точки, с которой оно было прервано; это может быть очень полезной характеристикой для многих приложений, например, для передачи данных. В противном случае соединение должно быть прекращено, и все передаваемые данные будут потеряны.
Разорванное соединение мультимедиа требует только один канал, подобно нормальному речевому звонку. Далее разорванные мультимедиа звонки определим как 4 тип соединения. Допускается разорванное соединение, которое может быть продолжено так быстро, как это возможно, самый высокий приоритет дается 4 типу соединений, чтобы быть продолженным, как только возможно. Допускаем, что остальным типам даны приоритеты в следующем порядке: мультимедиа, голос, и, наконец, потерянные данные.
Время, которое мобильный терминал (MT) с оставшимся вызовом в области закрывает базовой станцией ячейки, называется временем задержки (dwti ), если вызов до сих пор активен после этого времени, MT нуждается в передаче к другой ячейке. Длительность сеанса вызова определена как время, в которое вызов должен оставаться в процессе, если он мог бы продолжить завершение, без принудительного завершения из-за неудачной передачи данных.
Большинство аналитических решений для мобильных сетей предполагают или одну ячейку, или однородные вызовы. Оба предположения довольно нереальны. В этом примере мы не должны принять любое из вышеуказанных условий.
Построенную модель можно сравнить с показанной на рис. 2.8 для системы из 2 ячеек. Построенная сеть имеет два узла и 4 класса заявок: прерванные мультимедиа заявки мультимедиа заявки голосовые информационные Первый шаг - применить закрытый метод для получения закрытой организации сети. Рис. 2.9 показывает модель с закрытым узлом (3). Время обслуживания узла 3 определяется показателями прибытия для каждого класса. Вероятности маршрутизации из узла 3 отражаются плотностью прибытия на каждую ячейку системы. Рис. 2.9. Организация закрытой модели системы
Проблема определения вероятности маршрутизации очень тонкая в этой системе. Например, рассчитываются вероятности маршрутизации для класса 3 задания из узла 1. Для некоторого задания, есть две вероятности: завершение в обычном режиме (1 vi) или требует пересылки на узел 2(1jUvhl). Это приводит к двум вероятностям Pvend и Pvho. Но для пересылок также есть две возможности: успех или неудача. Последняя называется завершением. Вероятности могут быть модифицированы так, что вероятность маршрутизации задания класса 3 из узла 1 на узел 2 эквивалентна вероятности успешной пересылки из ячейки 1 в ячейку 2 (Pvhl2). Пока вероятность существующей системы Ptl эквивалентна сумме вероятностей нормального завершения задания и вероятности невыполненной пересылки. Отметим, что голосовые заявки не меняют класс, pi3 js = 0 s Ф 3. Также вероятности перехода из узла 3 могут быть определены. Эти выводы применимы к заданиям 4 класса. Для класса 1 и класса 2 нарушения должны быть учтены.
Информационное и алгоритмическое обеспечение средств автоматизации контроля структуры и объектов территориально распределенных баз данных
Задачи, которые намечены на выполнение в ближайшее время, входят в активную очередь так же, как и задачи, которые были перенесены от других процессоров. Задачи, которые входят в активную очередь, не имеют права на перемещение; это гарантирует, что задачи не будут неоднократно безуспешно перемещаться. Совместно распределяющая и активная очереди формируют очередь ожидания. Первая задача в активной очереди обозначена как выполняющаяся задача. Задача перемещается от распределяющей очереди к активной очереди только тогда, когда активная очередь становится пустой.
Считаем, что генерация задач в процессоре Pi – Пуассоновский процесс со средней частотой генерации Ri; эта частота независима от частот других процессоров. Обозначим интенсивность поступления задач R, где R i=N-1 =i=0 Ri , и N - общее количество процессоров в системе. Предполагаем, что размеры очередей в каждом процессоре неограниченны.
Времена передачи для сообщений Migrate и Answer принимаются равными двум единицам. Все другие сообщения требуют одну единицу времени. Это учитывает тот факт, что перемещение задачи и возврат результатов будут требовать подробной информации, которая будет послана. Среднее время завершения для задач - 13 единиц [3.29].
Пусть W - число задач в очереди ожидания процессора; это - оценка текущей загрузки того процессора. Пусть Lmax (Nmax) - верхний порог числа ждущих задач, при которых процессор рассматривается, как недогруженным. Другими словами, процессор будет рассматривается как недогруженный, если W Lmax, нормально загружен если Lmax W Nmax, и перегружен если Nmax W. Доступная загрузка в процессоре может быть определена как Nmax–W-1; 1 вычитается от Nmax-W, чтобы объяснить факт, что задача может присутствовать, в то время как процессор ждет ответ. Принимаем Lmax=1 и Nmax=3. Эти пороги также идентичны данным в [3.29], чтобы результаты могли корректно сравниваться.
За исключением системного размера, параметры моделирования, выбранные для этого этапа, соответствуют принятым в [3.19]. Это позволяет более точно сравнивать результаты работы алгоритмов. В [3.15] представлены результаты сравнения алгоритма Суена с алгоритмами Ни и др. [3.25] и Риоу [3.27]. В [3.28] отмечено, что алгоритм Суена использует приблизительно на 60% меньше сообщений, чем алгоритм Ни, и приблизительно на 50% меньше сообщений, чем алгоритм Риоу. Алгоритм Суена также обес печивает небольшое улучшение времени ответа по сравнению с другими методами. С целью сравнения результаты по всем этим методам приведены в графиках, представленные в этом разделе.
Мы ожидаем, что наш метод будет использовать чуть большее количество полных сообщений, чем алгоритм Суена; его метод использует минимальные SendingSets и ReceivingSets полного размера. Если бы использовались меньшие наборы, было бы невозможно определить перекрестное свойство, без которого мы были бы неспособны доказать теорему 1 (перемещение задачи произойдет всякий раз, когда это возможно). Так как
SendingSets и ReceivingSets могут быть большими, чем VN в нашей схеме, сообщения о загрузке и сообщения Request могут в общем случае быть посланными большему числу наборов процессоров.
Сначала моделирование проводится на сети из 7 процессоров с оценкой мощности и оценках потребности, приведенными в табл. 3.5. Фактическая мощность и оценки потребности должны учесть внимание много факторов, некоторые из которых весьма специфические для определенных сетей.
Табл. 3.6 содержит SendingSet и ReceivingSet назначения, полученные алгоритмом, представленным в [3.17]. Процессоры А и G менялись, чтобы создать неустойчивость оценки мощности среди SendingSets. Видно, что процессор E с оценкой потребности 25, имеет SendingSet, в котором процессоры (кроме него самого) имеют полную оценку мощности 31 (от процессоров A, B, и C). Эти отношения соблюдаются для всех процессоров: SendingSet каждого процессора содержит процессоры с полной оценкой мощности, которая имеет по крайней мере такое же значение, как и оценка потребности процессора. Табл. 3.6 также иллюстрирует тенденцию для более (менее) мощных процессоров иметь больший (меньший) ReceivingSets. Мощные процессоры увеличивают полные оценки мощности кворумальных наборов, в которых они постоянно находятся, делая такой кворумальный набор более вероятным, чтобы быть назначенным на другие процессоры. Следовательно, мощные процессоры имеют тенденцию появляться в больших SendingSets процессоров, и вероятно, в больших ReceivingSets.