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

• Автор: Генинсон, Борис Абрамович
• Шифр специальности: 05.13.11, 05.13.13
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 152 c. : ил

Глава I. СИНХРОНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

§ I. Основные задачи синхронизации параллельных

процессов в вычислительных системах .... Л § 2. Основные средства синхронизации параллельных процессов

§ 3. Влияние конфликтов на производительность

многопроцессорной системы

§ 4. Способы уменьшения потерь, связанных с синхронизацией параллельных процессов

Выводы к первой главе

Глава 2. ОПТИМАЛЬНЫЕ ПРАВИЛА РАЗРЕШЕНИЯ КОНФЛИКТОВ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ПРИ РАВНОЦЕННЫХ
РЕСУРСАХ

§ I. Математическая модель конфликтов в вычислительной системе

§ 2. Общие замечания относительно модели конфликтов В вычислительной системе

§ 3. Оптимальное правило разрешения конфликтов в многопроцессорной системе: случай одного неделимого ресурса
§ 4. Экспериментальная проверка эффективности оптимального правила для модели с одним неделимым ресурсом

§ 5. Оптимальное взаимодействие между двумя параллельными процессами с несколькими критическими участками
§ 6. Аналитическая оценка эффективности оптимального правила разрешения конфликтов для двух процессов с несколькими критическими участками . ^50 § 7. Оптимальное правило разрешения конфликтов между слабосвязанными параллельными процессами . -5%
§ 8. Экспериментальная проверка эффективности оптимального правила для модели слабосвязанных
процессов
§ 9. Возможные обобщения рассмотренных ситуаций . . <
Выводы ко второй главе
Глава 3. ОПТИМАЛЬНЫЕ ПРАВИЛА РАЗРЕШЕНИЯ КОНФЛИКТОВ С
УЧЕТОМ НЕРАВНОЦЕННОСТИ РЕСУРСОВ
§ I. Модель конфликтов в многопроцессорной системе
с учетом неравноценности ресурсов
§ 2. Понятие оптимальности в и его свойства
§ 3. Управляемые марковские цепи с векторными штрафами
§ 4. Свойства управляемых марковских цепей с векторными штрафами
§ 5. Человеко-машинная процедура отыскивания оптимальной стратегии при существовании функции полезности
§ б. Применение разработанного аппарата к задаче
разрешения конфликтов

Выводы к третьей главе
Приложение к третьей главе
Глава 4. РЕАЛИЗАЦИЯ АЛГОРИТМОВ РАЗРЕШЕНИЯ КОНФЛИКТОВ
В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
§ I. Алгоритмы разрешения конфликтов в вычислительных системах
§ 2. Целесообразный табличный алгоритм разрешения
конфликтов и его модификации
§ 3. Обоснование выбора алгоритма ^ для разрешения конфликтов между параллельными процессами
§ 4. Оценка эффективности табличных алгоритмов на
имитационной модели
§ 5. Использование алгоритма разрешения конфликтов
в системах мультипрограммирования
§ б. Синхронизация параллельных процессов на уровне передачи сообщений. Реализация алгоритма разрешения конфликтов в вычислительном комплексе ПС-3000
Выводы к четвертой главе
Приложение к четвертой главе
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ (Акты о внедрении)

+tf-f£>Cc*)=Са'-а'>г «лг; - ?:>;j.
Методом математической индукции можно убедиться, что Vn ^ (ЙК, (р), откуда при fl 'А получим
- что и требовалось доказать.
2. И для данной модели доказательство теоремы в случае критерия 2 вытекает из предыдущего в силу асимптотического поведе-

ния критерия i) при Т-> оо , т.к. цепь Маркова
в пространстве М при фиксированном правиле разрешения конфликтов имеет единственный эргодический класс £Гз 0J
Следует отметить,что результат, полученный для рассматриваемой модели и результат для предыдущей модели согласованы между собой (если в предыдущей модели считать, что n=z , а в рассматриваемой модели, что уп= У ).
§ б. Аналитическая оценка эффективности оптимального правила разрешения конфликтов для двух процессов с несколькими критическими участками
Для модели, рассмотренной в § 5, эффективность оптимального правила разрешения конфликтов можно оценить аналитически. С этой целью найдем среднюю частоту конфликтов при оптимальном правиле разрешения конфликтов Sc . Заметим, что в силу С2°3
-2 X (АА) ,
где ^ А*) - стационарная вероятность состояния при фиксированном правиле Se
Для вероятностей 71~s0 (/1*>Аг), с , можно выписать