- •Алгоритм выхода из тупиковой ситуации с минимальной ценой
- •Алгоритмы защиты от взаимных блокировок. Классификация алгоритмов защиты.
- •Асинхронные параллельные процессы. Проблема «производитель-потребитель».
- •Асинхронные параллельные процессы. Проблемы синхронизации параллельных процессов.
- •Высокопроизводительный Фортран hpf. Общая характеристика.
- •Задача предотвращения тупиков. Алгоритм банкира.
- •Задача предотвращения тупиков. Алгоритм упорядоченных классов.
- •1. Некоторые процессы бесконечно ожидают освобождения требуемых ресурсов, не производя никакой полезной работы
- •2. Процессы удерживают некоторые ресурсы не выполняя никакой полезной работы, и система без внешнего воздействия не может выйти из этого состояния.
- •Конструктор массивов в языке Фортран 90.
- •Непроцедурный язык Норма. Понятие сетки. Понятие области.
- •Оператор полагать в языке норма.
- •Операторы языка Фортран 90
- •Операции над массивами в языке Фортран 90.
- •Организация ввода и вывода в языке норма.
- •Понятия критического ресурса и критической секции.
- •Проблема «Производитель-потребитель». Общие семафоры.
- •Проблема взаимных блокировок (тупиков).
- •Программирование пространственно-временных структур на языке оккам.
- •Секции массивов в языке фортран 90.
- •19. Система программирования pvm (Parallel Virtual Machine).
- •20. Система параллельного программирования dvm(Distributed Virtual Machine).
- •21. Система параллельного программирования mpi.
- •22. Структура программы на языке норма. Оператор итерация.
- •23. Условные области в языке норма.
- •24. Язык фортран 90. Общая характеристика.
- •25,26. Язык оккам. Общая характеристика. Операторы языка оккам.
-
Алгоритм выхода из тупиковой ситуации с минимальной ценой
Тупиковое состояние:
1. Некоторые процессы бесконечно ожидают освобождения требуемых ресурсов, не производя никакой полезной работы
2. Процессы удерживают некоторые ресурсы не выполняя никакой полезной работы, и система без внешнего воздействия не может выйти из этого состояния.
Меры борьбы с тупиками
- Статические (анализ текста программы).
- Динамические
-
Обнаружение с последовательным выходом из тупика
-
Прекращение: 1)Ручной выход; 2)Автоматический
-
Перехват ресурсов
-
-
Методы предотвращения
-
Метод упорядоченных классов
-
Алгоритм банкира
-
Минимальная цена выхода (Прекращение процессов с автоматическим выходом)
Р1 С1
……….
Рn Сn
Pn – параллельные процессы
Cn – цена, внешняя, динамически назначаемая.
Цена отображает ценность процесса.
Затем формируется шкала цен для всех процессов и всех сочетаний.
Р1 + Р2 → С1 + С2
…………………..
Полученная шкала сортируется по возрастанию.
Теорема о тупике: система находится в тупике, когда двудольный граф состояний содержит хотя бы один цикл.
Процессы, входящие в цикл, составляют тупиковое множество.
Алгоритм
-
Если система находится в тупиковом состоянии, то в шкале цен помечаются процессы, входящие в тупиковое множество.
-
Моделируется состояние системы, если прекратить процесс с минимальной ценой.
-
Затем снова анализируется граф состояний. Если система выходит из тупика – алгоритм заканчивается, и выдаётся команда на прекращение процесса.
-
Если система не выходит из тупика, то восстанавливается предыдущее состояние и выбирается другая группа процессов.
-
Алгоритмы защиты от взаимных блокировок. Классификация алгоритмов защиты.
- Статические (анализ текста программы).
- Динамические
-
Обнаружение с последовательным выходом из тупика
-
Прекращение: 1)Ручной выход; 2)Автоматический
-
Перехват ресурсов
-
-
Методы предотвращения
-
Метод упорядоченных классов
-
Алгоритм банкира
-
Статические методы – методы одного решения. Применяются в системах, где простые алгоритмы, число параллельных процессов ограничено. Метод анализа текста программы основан на просмотре опасных участков в программе, в которых имеются запросы на ресурсы системы. В настоящее время разработаны теоретические основы анализа этих участков. Используется в основном в системах, в которых функционирует ограниченное количество параллельных процессов, ограничено кол-во ресурсов и жестко заданы алгоритмы для каждого процесса (системы, где заранее известно как будут исп. ресурсы).
Методы предотвращения – используются в системах, где недопустимо возникновение тупиковых ситуаций. В настоящее время эти методы представлены в основном методом упорядочивания классов (предварительно распределения всех ресурсов системы по классам). Каждому такому классу ставится в соответствие вес от 1 до N и любой процесс может получить ресурс класса L, только если до этого он получит все ресурсы класса L-1. Процессам навязывается порядок использования ресурсов системы. Это приводит к тому, что в графе состояния системы никогда не может возникнуть цикла, т.е. по теореме о тупике система никогда не войдёт в тупиковое состояние. Недостатки: навязывание процессам жесткого порядка в использовании ресурсов, что снижает эффективность системы в целом. Используется в системах с достаточным количеством ресурсов, в которых допустимо плавное снижение эффективности.
Прекращение процессов
- с ручным выходом: ограниченное количество ресурсов, в которых можно найти косвенные критерии попадания системы в тупик (например, существенное увеличение времени выполнения процесса)
- с автоматическим выходом: применяется в системах с большим числом параллельных процессов и ресурсов, и в которых невозможно определить косвенный критерий.
Минимальная цена выхода (Прекращение процессов с автоматическим выходом)
-
Р1 С1
……….
Рn Сn
Pn – параллельные процессы
Cn – цена, внешняя, динамически назначаемая.
Цена отображает ценность процесса.
Затем формируется шкала цен для всех процессов и всех сочетаний.
Р1 + Р2 – С1 + С2 …………………..
Полученная шкала сортируется по возрастанию.
Алгоритм
-
Если система находится в тупиковом состоянии, то в шкале цен помечаются процессы, входящие в тупиковое множество.
-
Моделируется состояние системы, если прекратить процесс с минимальной ценой.
-
Затем снова анализируется граф состояний. Если система выходит из тупика – алгоритм заканчивается, и выдаётся команда на прекращение процесса.
-
Если система не выходит из тупика, то восстанавливается предыдущее состояние и выбирается другая группа процессов.
Алгоритм банкира: в алгоритме Банкира (на основе априорной информации о процессах и ресурсах) перед выполнением каждой элементарной операции (операция запроса на ресурс SR типа, CR типа или освобождения ресурса CR типа) проверяется новое состояние системы. В случае удовлетворения этого запроса - если состояние безопасное, то запрос удовлетворяется, в противном случае - нет.
Все состояния системы делятся на три категории:
- безопасное,
- опасное,
- тупиковое.
Безопасными (БС) будут считаться состояния, из которых возможен переход при выполнении элементарной операции только в другое безопасное состояние или в опасное состояние. Опасными (ОС) считаются состояния, из которых возможен переход в тупиковое состояние. Из тупикового (ТС) состояния невозможен переход ни в какое другое состояние.
В алгоритме реализована стратегия принятия решения о предоставлении ресурса по запросу только если система после удовлетворения запроса продолжает оставаться в опасном состоянии. Основой для принятия решений в алгоритме Банкира является анализ информации о максимальной потребности процессов в каждом из ресурсов системы.
Недостаток: высокий % необоснованных отказов в удовлетворении запросов на ресурсы, а также высокие собственные затраты вычислительных ресурсов на реализацию этого алгоритма.
Алгоритм банкира исключает попадания системы в опасные состояния. Перед началом работы каждый процесс в системе должен сообщить свои максимальные потребности в ресурсах каждого класса. Алгоритм банкира моделирует будущие состояния системы, если удовлетворяется запрос процесса на ресурс или другая элементарная операция.
Алгоритм банкира состоит из двух частей:
-
Первая определят тип будущего состояния (удовлетворение запроса на ресурс).
-
Вторая принимает решения и корректирует (модель определение типа состояния).