СПО - лекции

Лекция № 529 сентября 2011 г.12:09Реализация взаимного исключения.Алгоритмы такие же, как и в централизованных системах. Имеется центральный системный ресурс и есть несколько процессов, котор ыевыполняются без общей памяти (одна ячейка памяти доступная всем процессам). Реализация критических интервалов в сети на базе семафоровнереализуема, так как память находится на разных узлах, поэтому отказы компонентов, коммуникационные задержки и нет единого в ремени.Основные алгоритмы:1. Централизованный алгоритм.

Основан на управление доступом к критическому ресурсу посредством координирующего сервера. Естьпроцесс координатор. Если какой-то процесс хочет войти в критический интервал (интервал, в течение которого некоторый процессиспользует некоторый критический ресурс; критические интервалы реализуются на различный узлах) каждый процесс направляеткоординатору запрос на соответствующие критический ресурс. Координатор проверяет этот ресурс на критичность и ставит запрос в очередь.Алгоритм прост в реализации и минимален по сообщениям, но так как ресурс масштабен, то координатор становится узким местом и можетотказывать.2.

Маркерное кольцо. Запросы передаются по кольцу. Процессы, которым требуется доступ к критическому ресурсу, они организованы ввиртуальное кольцо и эти процессы передают друг-другу маркер (некое сообщение о разрешении или не разрешении входа в критическийинтервал). Если маркер не нужен, он передаёт дальше. Метод прост, но если никому маркер не нужен, он будет постоянно путешест воватьпо кольцу. Возможна потеря маркера, как любого сообщения.3.

Распределённый алгоритм. В этом алгоритме решается алгоритм "первый вошёл - первый вышел". Если процесс желает использоватькритический ресурс, он отправляет всем ресурсам запрос о запросе ресурса. Сообщение упорядочивается по времени. Процесс можетответить немедленно на сообщение или отложить отправку ответа. Если он находится в критическим интервале, то он не отвечает, доосвобождения критического ресурса. Если не собирается использовать критический ресурс, то сразу отправляет сообщение. Сравни ваютсяметки времени запросов (в том числе и своего).

Если есть метки раньше его, то отвечает, если нет - занимает ресурс. Процесс, получившийответ от всех процессов может получить критический интервал, а после выхода из него отвечает на запросы, отправка которых был азадержана. Узкими местами будут все узлы системы.Взаимоблокировка в сетевых (распределённых) системах (дедлоки).Это постоянное блокирование множества процессов, которые конкурируют друг с другом. Фиктивная блокировка.Распределённые бывают 2 типов:1.

Возникающие в связи разделения ресурсов. Возникает тогда, когда процесс пытается получить доступ к ресурсам, которые находятс я надругом узле сети. Образуется группа процессов, которые хотят получить ресурс на сервере.Взаимоблокировка возникает при условиях:- Условие взаимоисключение - может использовать критический ресурс только один процесс- Удержание и ожидание- Отсутствие перераспределения - ресурс не может принудительно быть отнят у процесса- Образуется замкнутая цепь запросов.Цель обработки взаимоблокировок - предотвратить взаимоожидание или его обнаружение с целью ликвидации.Существует ложная (фиктивная) взаимоблокировка.

Они могут возникатьP1P2P3r1r2r32. Возникающие при обмене сообщенийПри конфликтах на запросы на ресурсы решаются с помощью временных меток. Реализуются условия кругового ожидания.Избежание взаимоблокировок. Необходимы алгоритмы решения этих проблем.Минусы:1. Каждый узел должен следить за глобальным состоянием системы.2. Процесс проверки должен быть взаимоисключающий.Выявление взаимоблокировок.

Алгоритмы:1. При централизованном управлении - реализуется на одном узле. Все сообщения с запросами отправляются центральному процессору иликоординатору. Требуется большое количество сообщений.2. Иерархическое управление. Узлы организованы в форме древовидной структуры. Один узел главный.Взаимоблокировки, возникающие при обмене сообщениями:Возникают в том случае, когда требующимся процессом ресурсом является сообщение, при этом образуется группа процессов, каждый изкоторых ожидает сообщение от другого процесса, но каждый из них не может отправить сообщение.Сетевое ПО Стр.1Лекция №66 октября 2011 г.13:53Взаимоблокировки, возникающие при передаче сообщений.Сообщения являются ресурсами.Возникают в том случае, когда требующимся процессом ресурсом является сообщение, при этом образуется группа процессов, каждый из которыхожидает сообщение от другого процесса, но каждый из них не может отправить сообщение.Какой либо процесс ждёт сообщение от остальных процессов.Взаимоблокировка возникает при:1.

Все процессы находятся в ожидании.2. Каналы пусты для передачи сообщений (нет ни одного сообщения).Имеем 4 процесса:Самый простой случай, когда имеем один буфер, а узлы обмениваются.Непосредственную блокировку можно предотвратить не позволяя всем буферам заполняться сообщениям для одного узла.

Еслииспользовать раздельные буферы для каждой связи, то можно такие алгоритмы писать на псевдоязыке. Можно использовать и общийбуфер, но пространство сообщений недолжно заниматься для одного узла.Косвенная блокировка -если образуется замкнутый цикл узлов, на каждом из которых очередь сообщений, передаваемых на соседнийузел, до отказа забит пакетами, предназначенными для узла, находящимися за соседними.Чтобы предотвратить блокировки такого типа используют структурированные буферные пулы. Буферный пул разделён на некоторыебуферы разных уровней. Уровни от 0 до n, где n=количеству транзитных передач.

Когда узел получает сообщение, то анализируется,сколько транзитных передач прошло сообщение.Использование пула памяти на нулевом уровне не ограничивается никакими правилами. Там может храниться любой пакет.На k-том уровне буфера помещаются сообщения, которые прошли не менее k-транзитных передач.Пул позволяет избежать косвенную и взаимоблокировку.Репликация.Репликация - это копирование данных не несколько узлов.Изменения в начальных данных должны как-то отображаться в остальных репликах.

Вопросы репликации решаются по-разному длямелких и крупномасштабных систем.Основные проблемы решения - доступность серверов, синхронизация реплик, коммуникационные задержки.Два варианта изменения реплицированных данных.1. Слабая согласованность. В этом случае изменения, вносимые в одну из реплик немедленно становятся видны всем клиентам.2.

Строгая согласованность. Изменение в этом случае становятся видны процессам, только после согласования реплик. Доступ ковсем репликам закрыт во время согласования.Вводятся системы горячего резервирования - копирование информации на другие узлы, но это для некрупных сетей.Сбор кворума для обеспечения строгой согласованности.Обновление производится тогда, когда в этом обновлении готовы участвовать большинство реплик. Это большинство называетсякворум записи.WQ>=n-2Кворум чтения гарантирует, что хотя бы одна из реплик содержит последнюю версию. Тогда кворум чтения можно обозначить RQ>n-WQВ крупномасштабных системах реплики организованы иерархически.

Реплики верхнего уровня всегда строго согласованы.Кластерная обработка (кластерная сетевая архитектура):Симметричная мультипроцессорная система.Кластер - сетевой аналог мультипроцессорной системы, кластер можно представлять как некий единый ресурс и обращение к нему может бытьорганизовано как обращение к единому ресурсу.Свойства кластеров:1. Все компьютеры, входящие в состав кластера, могут работать самостоятельно2. Абсолютная масштабируемость (можно создавать кластер любого размера), причём кластеры могут быть из однопроцессорной илимногопроцессорной архитектуры.3.

Инкрементальная масштабируемость, т.е. можем добавлять узлы любыми способами.4. Высокая доступность - т.к. каждый узел - отдельный компьютер, то сбой или выход из строя одного узла не приводит к снижению обслуживания.5. Использование недорогих компьютеров в качестве узлов позволяют создавать высокопроизводительную систему, стоимостью меньше, чтомстоимость отдельного компьютера с такой же мощностью.Конфигурации кластеров:Взаимодействие узлов осуществляется с помощью высокоскоростных линий связи, для передачи сообщений в кластереа) локальная вычислительная сеть, которая используется как узлами кластера, так и узлами, не входящими в состав кластераб) специально предназначенными для работы кластера.Сетевое ПО Стр.2Сетевое ПО Стр.3Лекция №713 октября 2011 г.13:57Архитектура технических средств и ПО.Технические средства:1.