Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Московский государственный технический университет радиотехники, электроники и автоматики

Факультет кибернетики

Курсовая работа

На тему:

Синхронизация доступа к разделяемым ресурсам в многопроцессорных системах с разделяемой памятью и сетях

Выполнил: Кузовлев Евгений

студент 2 курса Группы КС-2-12

Проверила: Лукинова О.В.

Москва, 2013 г.



Содержание

1. Синхронизация доступа к разделяемым ресурсам

2. Механизмы организации взаимного исключения для синхронизации доступа к разделяемым ресурсам

2.1 Запрещение прерываний и специальные инструкции

2.2 Активное Ожидание

2.3 Семафоры

2.4 Мониторы

2.5 Обмен Сообщениями

2.6 Примитивы взаимоисключения

2.7 Организация адресации сообщений

2.8 Длина сообщения

3. Структура и специфика многопроцессорных систем

4. Общая структура многопроцессорной системы

5. Классификация Флинна

5.1 Классы многопроцессорных систем

6. Подробное представление многопроцессорной системы с разделяемой (общей) памятью

7. Синхронизация доступа к разделяемым ресурсам в многопроцессорных системах

7.1 Семафоры в многопроцессорной конфигурации

7.2 Алгоритмы

7.2.1 Выделение Буфера

7.2.2 Wait

7.2.3 Семафоры с драйверами устройств

7.2.4 Фиктивные процессы

8. Синхронизация доступа к разделяемым ресурсам в сети

9. Кластеры

9.1 Кластеры распределения нагрузки

9.2 Вычислительные кластеры

9.3 Системы распределенных вычислений

9.4 Кластер серверов, организуемых программно

9.5 Примеры программных кластерных решений

9.6 Применение

10. Службы именования ресурсов и проблемы прозрачности доступа

Вывод

Список литературы



1. Синхронизация доступа к разделяемым ресурсам

Процессам часто нужно взаимодействовать друг с другом, например, один процесс может передавать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла. Во всех этих случаях возникает проблема синхронизации процессов, которая может решаться приостановкой и активизацией процессов, организацией очередей, блокированием и освобождением ресурсов.

Одной из важных характеристик ОС является возможность одновременного выполнения взаимосвязанных процессов. Надо сказать, что в распараллеливаниии процессов состоит один из основных резервов повышения быстродействия и эффективности ЭВМ.

Процессы называются параллельными, если они существуют одновременно. Одновременно выполняющиеся и не взаимосвязанные процессы называются параллельными процессами. Одновременно выполняющиеся, взаимодействующие и совместно использующие общие ресурсы, называются асинхронными параллельными процессами.

При управлении асинхронными параллельными процессами возникает две проблемы:

· проблема синхронизации параллельных процессов;

· проблема взаимной блокировки - тупика (dead lock)

Задача синхронизации АПП в ОС решается методом взаимоисключения процессов при выполнении их на критических участках. [2]



2. Механизмы организации взаимного исключения для синхронизации доступа к разделяемым ресурсам

2.1 Запрещение прерываний и специальные инструкции

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

Этот подход, однако, имеет ряд существенных недостатков. Первым из них является снижение общей производительности системы вследствие ограничения возможности переключения процессов для оптимальной загрузки процессора. Другая проблема заключается в том, что нет никаких гарантий, что процесс, запретивший прерывания, не зациклится в своей критической секции, тем самым приведя систему в полностью неработоспособное состояние. Цена программной ошибки здесь становится слишком высокой. Кроме всего прочего, для многопроцессорной системы запрещение прерываний не гарантирует даже взаимного исключения, так как запрещение прерываний на одном из процессоров никак не влияет на исполнение процессов на других процессорах ВС, и эти процессы по-прежнему имеют доступ к разделяемому ресурсу, например, ячейке общей памяти. [2]

2.2.Активное ожидание

Общим недостатком рассмотренных выше решений является то, что процесс, желающий получить доступ к занятому ресурсу, блокируется в состоянии так называемого активного ожидания (в англоязычной литературе - busy waiting), т.е. в цикле постоянно проверяет, не наступило ли условие, при котором он сможет войти в критическую секцию. Использование активного ожидания приводит к бесполезному расходованию процессорного времени и, как следствие, снижению общей производительности системы. Кроме того, при некоторых стратегиях планирования времени ЦП в целом корректный алгоритм с активным ожиданием может привести к тупику. Примером может служить стратегия планирования с приоритетами, когда процесс, имеющий больший приоритет, загружается на выполнение и переходит в состояние активного ожидания, в то время как процесс с меньшим приоритетом захватил необходимый ресурс, но был выгружен до того, как освободил его. Поскольку процесс с большим приоритетом не блокирован, а готов к продолжению выполнения, переключение процессов не происходит, и процесс, владеющий ресурсом, никогда не сможет его освободить.

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

2.3 Семафоры

Семафор развивает механизм примитивов и обобщает его. Автор -Дейкстра. Семафор - это целочисленная неотрицательная переменная S - счетчик ресурса, которую можно менять и опрашивать при помощи операций P и V и очередь процессов к ресурсу Q(S). Над переменной определено три операции.

· инициализация ресурса I(S) - задает число доступных ресурсов;

· P(S) - захват ресурса;

· V(S) - освобождение ресурса.

Операция P(S) выполняется следующим образом:

IF S>0 есть ресурс?

THEN S:=S-1 выдать ресурс

ELSE ожидать очереди Q(S)

Операция V(S):

IF Q(S)? 0 очередь не пуста?

THEN вывести процесс из очереди (выдать ресурс)

ELSE S:=S+1 освободить ресурс

Если семафор управляет одним ресурсом, то это двоичный семафор и S принимает значение {0,1}. Если он управляет группой ресурсов, то в переменной S устанавливается число ресурсов. Для работы семафора необходимо один раз инициировать процесс и обрабатывать критические участки операциями P(S) и V(S).

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

Достоинства:

1. Пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов)

2. Возможность управления группой однородных ресурсов.

Недостатки:

1. Неправильное, либо умышленное использование операций на семафоре допускает нарушение работоспособности параллельных систем.

Обход недостатка: Для предотвращения возникновения подобных ситуаций используются соответствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливающие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых процесс должен одновременно захватывать несколько семафоров, довольно ограничено, легче было бы реализовать алгоритмы, предупреждающие возникновение тупиковых ситуаций еще до того, как они будут иметь место. Если, к примеру, какой-то набор семафоров всегда блокируется в одном и том же порядке, тупиковая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров в обратном порядке избежать не удается, операция предотвратит возникновение тупиковой, если операция завершится неудачно, процесс B освободит свои ресурсы, дабы избежать взаимной блокировки, и позже запустит алгоритм на выполнение повторно, скорее всего, тогда, когда процесс завершит работу с ресурсом.[2]



2.4 Мониторы

Монитор - это механизм организации параллелизма высокого уровня, который содержит множество переменных состояний, очередей и множество процедур, необходимых для реализации динамического распределения и доступа к общим ресурсам.

Монитор представляет собой централизованный семафор или совокупность семафоров, спрятанных от пользователей процессов в одном системном процессе, и потому, недоступным пользовательским программам, которые не могут их нарушить. Процессы, которые использует монитор для синхронизации, не имеют прямого доступа к переменным состояния, и могут воспользоваться ресурсами только путем вызова процедур монитора (или макрокоманд).

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

Достоинства монитора:

· Логические возможности не меньше, чем у семафоров.

· Упрощение написания параллельных программ. Достаточно знать процедуры организации параллельных вычислений.

· Повышение надежности параллельных систем, так как полностью защищает управление ресурсом.

· Обеспечение гарантированного получения ресурса.[2]

2.5 Обмен сообщениями

Общей проблемой и для мониторов, и для семафоров является то, что их реализация существенно опирается на предположение, что мы имеем дело либо с однопроцессорной системой, либо с многопроцессорной системой, где все процессоры имеют доступ к общей памяти. Однако в случае распределенной системы, где каждый процессор имеет прямой доступ только к своей памяти, такие средства не подходят. Более общим средством, решающим проблему синхронизации как для однопроцессорных систем и систем с общей памятью, так и для распределенных, является обмен сообщениями.

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

send(destination, message)

receive(source, message)

Как и семафоры, и в отличие от мониторов, эти примитивы являются системными вызовами, а не конструкциями языка.

Важные особенности: Синхронизация, Адресация и Длина сообщения.[2]

2.6 Примитивные взаимоисключения

Примитивы взаимоисключения используются для обработки критических участков программы и представляют собой совокупность логической переменной I, представляющей общий ресурс и принимающей два значения: 0 - свободен, 1 - занят, а также команды (проверить и установить) - TS (TS,I,B01).

· читает логическую переменную I

· проверяет ее значение

· устанавливает новое значение I.

Следует заметить, что операция проверки и установки блокирующей переменной должна быть неделимой. Поясним это. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к не желаемым последствиям.

На примере ниже перед входом в критическую секцию процесс проверяет, свободен ли ресурс. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной I устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной I снова устанавливается равным 0.

Do while (TS I,B'1') Do while (TS I,B'1')

END END

<критический участок> <критический участок>

TS I,B'0' TS I,B'0'

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

Недостатки:

· Циклический опрос переменной I и бессмысленное расходование времени ЦП.

· Не исключено бесконечное ожидание ресурса, хотя вероятность невелика.

· Работает с одним ресурсом.

Для устранения расходования времени ЦП может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по - своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(I), здесь I обозначает событие, заключающееся в освобождении ресурса I. Функция WAIT(I) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события I. Процесс, который в это время использует ресурс I, после выхода из критической секции выполняет системную функцию POST(I), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события I, в состояние ГОТОВНОСТЬ [2]

2.7 Организация адресации сообщений

Другая важная проблема - организовать адресацию сообщений. Одно из решений - так называемая прямая адресация, при которой каждому из процессов присваивается некоторый идентификатор, и сообщения адресуются этим идентификаторам. При этом процесс-получатель может указать явно идентификатор отправителя, от которого он желает получить сообщение, либо получать сообщения от любого отправителя.

Иное решение заключается в том, чтобы предоставить специальную структуру данных - почтовый ящик, или очередь сообщений, которая по сути своей является буфером, рассчитанным на определенное количество сообщений. В этом случае сообщения адресуются не процессам, а почтовым ящикам, при этом один и тот же ящик может использоваться и несколькими отправителями, и несколькими получателями. Такая схема, называемая косвенной адресацией, обеспечивает дополнительную гибкость. Заметим, что связь между процессом-получателем или отправителем и почтовым ящиком может быть не только статической (т.е. раз навсегда заданной при создании ящика), но и динамической; в последнем случае для установления и разрыва связи используются дополнительные примитивы (connect/disconnect). Кроме того, поскольку почтовый ящик является самостоятельным объектом, необходимо наличие примитивов создания и удаления ящика (create/destroy). [2]

2.8 Длина сообщения

Немаловажным аспектом является формат сообщений. В той или иной системе могут допускаться как сообщения фиксированной длины, так и переменной. В последнем случае в заголовке сообщения, помимо отправителя и получателя, должна указываться длина сообщения. Выбор того или иного варианта зависит от целей, которые преследует система обмена сообщениями, и от предполагаемой архитектуры ВС. Так, если предполагается возможность передачи больших объемов данных, то сообщения с переменной длиной будут более гибким решением и позволят сократить накладные расходы на большое количество коротких сообщений, где значительную часть занимает сам заголовок. С другой стороны, если обмен происходит между процессами на одной машине, немаловажную роль играет эффективность. Здесь, возможно, было бы уместно ограничить длину сообщения, с тем, чтобы использовать для их передачи системные буфера с быстрым доступом.

Механизм обмена сообщениями является мощным и гибким средством синхронизации, пригодным для использования как на однопроцессорных системах и системах с общей памятью, так и в распределенных ВС. Однако, по сравнению с семафорами и мониторами, он, как правило, является менее быстрым. [2]



3. Структура и специфика многопроцессорных систем

Многопроцессорная архитектура, включает в себя два и более центральных процессоров (ЦП), совместно использующих общую память и периферийные устройства, располагая большими возможностями в увеличении производительности системы, связанными с одновременным исполнением процессов на разных ЦП. Каждый ЦП функционирует независимо от других, но все они работают с одним и тем же ядром операционной системы. Поведение процессов в такой системе ничем не отличается от поведения в однопроцессорной системе - с сохранением семантики обращения к каждой системной функции - но при этом они могут открыто перемещаться с одного процессора на другой. Хотя, это не приводит к снижению затрат процессорного времени, связанного с выполнением процесса. Отдельные многопроцессорные системы называются системами с присоединенными процессорами, поскольку в них периферийные устройства доступны не для всех процессоров. [8]



4. Общая структура многопроцессорной системы

При построении многопроцессорной архитектуры может использоваться одна из нескольких концептуальных моделей соединения вычислительных элементов.

На рис. 2 показана общая структура МП-системы: связанная архитектура с общей памятью с распределенной обработкой данных и прерываний ввода-вывода. Она полностью симметрична; т. е. все процессоры функционально идентичны и имеют одинаковый статус, и каждый процессор может обмениваться с каждым другим процессором. Симметричность имеет два важных аспекта: симметричность памяти и ввода-вывода.

Память симметрична, если все процессоры совместно используют общее пространство памяти и имеют в этом пространстве доступ с одними и теми же адресами. Симметричность памяти предполагает, что все процессоры могут исполнять единственную копию ОС. Требование симметричности ввода-вывода выполняется, если все процессоры имеют возможность доступа к одним и тем же подсистемам ввода-вывода, причем любой процессор может получить прерывание от любого источника. [8]



5. Классификация Флинна

Самой ранней и наиболее известной является классификация архитектур вычислительных систем, предложенная в 1966 году М. Флинном. Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD,MISD,SIMD,MIMD.

1. SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка - как машина CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными попадают в этот класс.

2. SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производится либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.

3. MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. Будем считать, что пока данный класс пуст.

2. MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.[9]

5.1 Классы многопроцессорных систем

В основе МКМД-ЭВМ лежит традиционная последовательная организация программы, расширенная добавлением специальных средств для указания независимых фрагментов, которые можно выполнять параллельно. Параллельно-последовательная программа привычна для пользователя и позволяет относительно просто собирать параллельную программу из обычных последовательных программ.

МКМД-ЭВМ имеет две разновидности: ЭВМ с разделяемой (общей) и распределенной (индивидуальной) памятью. Структура этих ЭВМ представлена на рис.

Главное различие между МКМД-ЭВМ с общей и индивидуальной памятью состоит в характере адресной системы. В машинах с разделяемой памятью адресное пространство всех процессоров является единым, следовательно, если в программах нескольких процессоров встречается одна и та же переменная Х, то эти процессоры будут обращаться в одну и ту же физическую ячейку общей памяти. Это вызывает как положительные, так и отрицательные последствия.

Наличие общей памяти не требует физического перемещения данных между взаимодействующими программами, которые параллельно выполняются в разных процессорах. Это упрощает программирование и исключает затраты времени на межпроцессорный обмен.

Однако одновременное обращение нескольких процессоров к общим данным может привести к получению неверных результатов. [6]

многопроцессорный разделяемый синхронизация нагрузка



6. Подробное представление многопроцессорной системы с разделяемой (общей) памятью.



7. Синхронизация доступа к разделяемым ресурсам в многопроцессорных системах

7.1 Семафоры в многопроцессорной конфигурации

Поддержка системы UNIX в многопроцессорной конфигурации может включать в себя разбиение ядра системы на критические участки, параллельное выполнение которых на нескольких процессорах не допускается. Такие системы предназначались для работы на машинах AT&T 3B20A и IBM 370, для разбиения ядра использовались. Нижеследующие рассуждения помогают понять суть данной особенности. При ближайшем рассмотрении сразу же возникают два вопроса: как использовать семафоры и где определить критические участки. Если при выполнении критического участка программы процесс приостанавливается, для защиты участка от посягательств со стороны других процессов алгоритмы работы ядра однопроцессорной системы UNIX используют блокировку.

Механизм установления блокировки:

· выполнять пока (блокировка установлена) /* операция проверки */

· приостановиться (до снятия блокировки);

· установить блокировку;

Механизм снятия блокировки:

· снять блокировку;

· вывести из состояния приостановки все процессы, приостановленные в результате блокировки;

Блокировки такого рода охватывают некоторые критические участки, но не работают в многопроцессорных системах. Предположим, что блокировка снята и что два процесса на разных процессорах одновременно пытаются проверить ее наличие и установить ее. В момент t они обнаруживают снятие блокировки, устанавливают ее вновь, вступают в критический участок и создают опасность нарушения целостности структур данных ядра. В условии одновременности имеется отклонение: механизм не сработает, если перед тем, как процесс выполняет операцию проверки, ни один другой процесс не выполнил операцию установления блокировки. Если, например, после обнаружения снятия блокировки процессор A обрабатывает прерывание и в этот момент процессор B выполняет проверку и устанавливает блокировку, по выходе из прерывания процессор A так же установит блокировку. Чтобы предотвратить возникновение подобной ситуации, нужно сделать так, чтобы процедура блокирования была неделимой: проверку наличия блокировки и ее установку следует объединить в одну операцию, чтобы в каждый момент времени с блокировкой имел дело только один процесс. [6]

7.2 Алгоритмы

Рассмотрим четыре алгоритма ядра, реализованных с использованием семафоров. Алгоритм выделения буфера иллюстрирует сложную схему блокирования, на примере алгоритма wait показана синхронизация выполнения процессов, схема блокирования драйверов реализует изящный подход к решению данной проблемы, и наконец, метод решения проблемы холостой работы процессора показывает, что нужно сделать, чтобы избежать конкуренции между процессами. [5]

7.2.1 Выделение буфера

Алгоритм работает с тремя структурами данных: заголовком буфера, хеш-очередью буферов и списком свободных буферов. Ядро связывает семафор со всеми экземплярами каждой структуры. Другими словами, если у ядра имеются в распоряжении 200 буферов, заголовок каждого из них включает в себя семафор, используемый для захвата буфера; когда процесс выполняет над семафором операцию P, другие процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор, пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов также имеется семафор, блокирующий доступ к очереди. В однопроцессорной системе блокировка хеш-очереди не нужна, ибо процесс никогда не переходит в состояние приостановки, оставляя очередь несогласованном (неупорядоченном) виде. В многопроцессорной системе, тем не менее, возможны ситуации, когда с одной и той же хеш-очередью работают два процесса; в каждый момент времени семафор открывает доступ к очереди только для одного процесса. По тем же причинам и список свободных буферов нуждается в семафоре для защиты содержащейся в нем информации от искажения. [6]

Выделение буфера с использованием семафоров:

алгоритм getblk /* многопроцессорная версия */

входная информация: номер файловой системы

номер блока

выходная информация: захваченный буфер, предназначенный для обработки |

содержимого блока |

{

выполнять (пока буфер не будет обнаружен)

{

P(семафор хеш-очереди);

если (блок находится в хеш-очереди)

{

если (операция CP(семафор буфера) завершается неудачно |

/* буфер занят */

{

V(семафор хеш-очереди);

P(семафор буфера); /* приостановка до момента освобождения*/

если (операция CP(семафор хеш-очереди) завершается неудачно

{

V(семафор буфера);

продолжить; /* выход в цикл "выполнять" */

}

в противном случае если (номер устройства или номер блока изменились |

{

V(семафор буфера);

V(семафор хеш-очереди);

}

}

выполнять (пока операция CP(семафор списка свободных буферов) не завершит-

успешно)

/* "кольцевой цикл" */

пометить буфер занятым;

убрать буфер из списка свободных буферов;

V(семафор списка свободных буферов);

V(семафор хеш-очереди);

вернуть буфер;

}

в противном случае /* буфер отсутствует в хеш-очереди*/

/* здесь начинается выполнение оставшейся части алгоритма*/

}

}

Взаимная блокировка при выполнении программы обработки прерывания:

P(семафор);

(Значение семафора теперь равно 0)

Прерывание

CP(семафор) завершается неудачно ---

семафор захвачен

Семафор не освобождается до выхода из прерывания.

Выход из прерывания без его обработки невозможен.

Тупиковая ситуация (взаимная блокировка)

v

Время

7.2.2 Wait

Во время выполнения системной функции wait процесс приостанавливает свою работу до момента завершения выполнения своего потомка. В многопроцессорной системе перед процессом встает задача не упустить при выполнении алгоритма wait потомка, прекратившего существование с помощью функции exit; если, например, в то время, пока на одном процессоре процесс-родитель запускает функцию wait, на другом процессоре его потомок завершил свою работу, родителю нет необходимости приостанавливать свое выполнение в ожидании завершения второго потомка. В каждой записи таблицы процессов имеется семафор, именуемый zombie_semaphore и имеющий в начале нулевое значение. Этот семафор используется при организации взаимодействия wait/exit. Когда потомок завершает работу, он выполняет над семафором своего родителя операцию V, выводя родителя из состояния приостанова, если тот перешел в него во время исполнения функции wait. Если потомок завершился раньше, чем родитель запустил функцию wait, этот факт будет обнаружен родителем, который тут же выйдет из состояния ожидания. Если оба процесса исполняют функции exit и wait параллельно, но потомок исполняет функцию exit уже после того, как родитель проверил его статус, операция V, вы-

полненная потомком, воспрепятствует переходу родителя в состояние приостановки. В худшем случае процесс-родитель просто повторяет цикл лишний раз. [5]

Многопроцессорная версия алгоритма wait:

многопроцессорная версия алгоритма wait

{

для (;;) /* цикл */

{

перебор всех процессов-потомков:

если (потомок находится в состоянии "прекращения

существования")

вернуть управление;

P(zombie_semaphore); /* начальное значение - 0 */

}

}

7.2.3 Семафоры с драйверами устройств

В многопроцессорной реализации вычислительной системы на базе компьютеров AT&T 3B20 семафоры в структуру загрузочного кода драйверов не включаются, а операции типа P и V выполняются в точках входа в каждый драйвер. Интерфейс, реализуемый драйверами устройств, характеризуется очень небольшим числом точек входа (на практике их около 20). Защита драйверов осуществляется на уровне точек входа в них:

· P(семафор драйвера);

· открыть (драйвер);

· V(семафор драйвера);

Если для всех точек входа в драйвер использовать один и тот же семафор, но при этом для разных драйверов - разные семафоры, критический участок программы драйвера будет исполняться процессом монопольно. Семафоры могут назначаться как отдельному устройству, так и классам устройств. Так, например, отдельный семафор может быть связан и с отдельным физическим терминалом и со всеми терминалами сразу. В первом случае быстродействие системы выше, ибо процессы, обращающиеся к терминалу, не захватывают семафор, имеющий отношение к другим терминалам, как во втором случае. Драйверы некоторых устройств, однако, поддерживают внутреннюю связь с другими драйверами; в таких случаях использование одного семафора для класса устройств облегчает понимание задачи. В качестве альтернативы в вычислительной системе 3B20A предоставлена возможность такого конфигурирования отдельных устройств, при котором программы драйвера запускаются на точно указанных процессорах. Проблемы возникают тогда, когда драйвер прерывает работу системы и его семафор захвачен: программа обработки прерываний не может быть вызвана, так как иначе возникла бы угроза разрушения данных. С другой стороны, ядро не может оставить прерывание необработанным. Система 3B20A выстраивает прерывания в очередь и ждет момента освобождения семафора, когда вызов программы обработки прерываний не будет иметь опасные последствия. [5]

Использование операции P условного типа для предотвращения взаимной блокировки:

Процесс A/Процессор A Процесс B/Процессор B

+-----------------------------------------------------------

P(семафор SA); -

- -

- P(семафор SB);

- -

- -

- если (! CP(семафор SA))

- {

- V(семафор SB);

- перезапустить алго-

- ритм

- }

P(семафор SB);

приостанавливается

v

Время

7.2.4 Фиктивные процессы

Когда ядро выполняет переключение контекста в однопроцессорной системе, оно функционирует в контексте процесса, уступающего управление. Если в системе нет процессов, готовых к запуску, ядро переходит в состояние простоя в контексте процесса, выполнявшегося последним. Получив прерывание от таймера или других периферийных устройств, оно обрабатывает его в контексте того же процесса. В многопроцессорной системе ядро не может простаивать в контексте процесса, выполнявшегося последним. Посмотрим, что произойдет после того, как процесс, приостановивший свою работу на процессоре A, выйдет из состояния приостановки. Процесс в целом готов к запуску, но он запускается не сразу же по выходе из состояния приостановки, даже несмотря на то, что его контекст уже находится в распоряжении процессора A. Если этот процесс выбирается для запуска процессором B, последний переключается на его контекст и возобновляет его выполнение. Когда в результате прерывания процессор A выйдет из простоя, он будет продолжать свою работу в контексте процесса A до тех пор, пока не произведет переключение контекста. Таким образом, в течение короткого промежутка времени с одним и тем же адресным пространством (в частности, со стеком ядра) будут вести работу (и, что весьма вероятно, производить запись) сразу два процессора. Решение этой проблемы состоит в создании некоторого фиктивного процесса; когда процессор находится в состоянии простоя, ядро переключается на контекст фиктивного процесса, делая этот контекст текущим для бездействующего процессора. Контекст фиктивного процесса состоит только из стека ядра; этот процесс не является выполнимым и не выбирается для запуска. Поскольку каждый процессор простаивает в контексте своего собственного фиктивного процесса, навредить друг другу процессоры уже не могут. [5]



8. Синхронизация доступа к разделяемым ресурсам в сети(DLM)

Средства DLM (Распределенный менеджер блокировки) обеспечивают базовый механизм глобальной блокировки для синхронизации в сети. Они дают возможность пользователям - системным клиентам на разных узлах производить глобальный захват разделяемых ресурсов для синхронизации доступа к ним. Такая координация обеспечивает гарантию полной согласованности работы большого числа процессоров. DLM устойчив к сбоям: в случае выхода из строя какого-либо узла блокировка ресурсов реконструируется и заново распространяется по сети. Для выполнения своих функций DLM поддерживает:

· множественность пространства имен, основываясь на концепции доменов;

· запоминание запросов и блокировок;

· распознавание взаимоблокировок;

· реконструкцию ресурсов и блокировок при сбое узлов.[4]



9. Кластеры

Кластер -- группа компьютеров, объединённых высокоскоростными каналами связи и представляющая с точки зрения пользователя единый аппаратный ресурс.

Один из первых архитекторов кластерной технологии Грегори Пфистер дал кластеру следующее определение: «Кластер -- это разновидность параллельной или распределённой системы, которая:

· состоит из нескольких связанных между собой компьютеров;

· используется как единый, унифицированный компьютерный ресурс».

Обычно различают следующие основные виды кластеров:

· отказоустойчивые кластеры (High-availability clusters, HA, кластеры высокой доступности)

· кластеры с балансировкой нагрузки (Load balancing clusters)

· вычислительные кластеры (High perfomance computing clusters)

· Грид-вычисления

9.1 Кластеры распределения нагрузки (Network Load Balancing, NLB)

Принцип их действия строится на распределении запросов через один или несколько входных узлов, которые перенаправляют их на обработку в остальные, вычислительные узлы. Первоначальная цель такого кластера -- производительность, однако, в них часто используются также и методы, повышающие надёжность. Подобные конструкции называются серверными фермами. Программное обеспечение (ПО) может быть как коммерческим (OpenVMS, MOSIX, Platform LSF HPC, Solaris Cluster, Moab Cluster Suite, Maui Cluster Scheduler), так и бесплатным (OpenMosix, Sun Grid Engine, Linux Virtual Server).



9.2 Вычислительные кластеры

Кластеры используются в вычислительных целях, в частности в научных исследованиях. Для вычислительных кластеров существенными показателями являются высокая производительность процессора в операциях над числами с плавающей точкой (flops) и низкая латентность объединяющей сети, и менее существенными -- скорость операций ввода-вывода, которая в большей степени важна для баз данных и web-сервисов. Вычислительные кластеры позволяют уменьшить время расчетов, по сравнению с одиночным компьютером, разбивая задание на параллельно выполняющиеся ветки, которые обмениваются данными по связывающей сети. Одна из типичных конфигураций -- набор компьютеров, собранных из общедоступных компонентов, с установленной на них операционной системой Linux, и связанных сетью Ethernet, Myrinet, InfiniBand или другими относительно недорогими сетями. Такую систему принято называть кластером Beowulf. Специально выделяют высокопроизводительные кластеры (Обозначаются англ. аббревиатурой HPC Cluster -- High-performance computing cluster). Список самых мощных высокопроизводительных компьютеров (также может обозначаться англ. аббревиатурой HPC) можно найти в мировом рейтинге TOP500. В России ведется рейтинг самых мощных компьютеров СНГ.

9.3 Системы распределенных вычислений (grid)

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

9.4 Кластер серверов, организуемых программно

Кластер серверов (в информационных технологиях) -- группа серверов, объединённых логически, способных обрабатывать идентичные запросы и использующихся как единый ресурс. Чаще всего серверы группируются посредством локальной сети. Группа серверов обладает большей надежностью и большей производительностью, чем один сервер. Объединение серверов в один ресурс происходит на уровне программных протоколов.

В отличие от аппаратного кластера компьютеров, кластеры организуемые программно, требуют:

· наличия специального программного модуля (Cluster Manager), основной функцией которого является поддержание взаимодействия между всеми серверами -- членами кластера:

· синхронизации данных между всеми серверами -- членами кластера;

· распределение нагрузки (клиентских запросов) между серверами -- членами кластера;

· от умения клиентского программного обеспечения распознавать сервер, представляющий собой кластер серверов, и соответствующим образом обрабатывать команды от Cluster Manager;

если клиентская программа не умеет распознавать кластер, она будет работать только с тем сервером, к которому обратилась изначально, а при попытке Cluster Manager перераспределить запрос на другие серверы, клиентская программа может вообще лишиться доступа к этому серверу (результат зависит от конкретной реализации кластера).



9.5 Примеры программных кластерных решений

· IBM Lotus Notes

· HP MC/ServiceGuard

9.6 Применение

В большинстве случаев, кластеры серверов функционируют на раздельных компьютерах. Это позволяет повышать производительность за счёт распределения нагрузки на аппаратные ресурсы и обеспечивает отказоустойчивость на аппаратном уровне.

Однако, принцип организации кластера серверов (на уровне программного протокола) позволяет исполнять по нескольку программных серверов на одном аппаратном. Такое использование может быть востребовано:

· при разработке и тестировании кластерных решений;

· при необходимости обеспечить доступность кластера только с учётом частых изменений конфигурации серверов -- членов кластера, требующих их перезагрузки (перезагрузка производится поочерёдно) в условиях ограниченных аппаратных ресурсов.[10]



10. Службы именования ресурсов и проблемы прозрачности доступа

Подобно большой организации, большая корпоративная сеть нуждается в централизованном хранении как можно более полной справочной информации о самой себе (начиная с данных о пользователях, серверах, рабочих станциях и кончая данными о кабельной системе). Естественно организовать эту информацию в виде базы данных, ведение которой поручить сетевой операционной системе. Данные из этой базы могут быть востребованы многими сетевыми системными приложениями, в первую очередь системами управления и администрирования. Кроме этого, такая база полезна при организации электронной почты, систем коллективной работы, службы безопасности, службы инвентаризации программного и аппаратного обеспечения сети, да и для практически любого крупного бизнес-приложения. Хотя полезных применений единой справочной службы много, она нужна по крайней мере для эффективного решения задачи администрирования, то есть ведения учетной информации на пользователей сети и определения прав доступа этих пользователей к разделяемым ресурсам сети. Эта задача всегда решалась каким-либо способом во всех многопользовательских операционных системах, не обязательно сетевых. В локальных версиях UNIX имеются файлы с предопределенными именами, хранящие эту информацию - например, файл /etc/passwd хранит информацию о пользователях и их паролях, а также о группах пользователей. В идеале сетевая справочная информация должна быть реализована в виде единой базы данных, а не представлять собой набор баз данных, специализирующихся на хранении информации того или иного вида, как это часто бывает в реальных операционных системах. Например, в Windows NT имеется по крайней мере пять различных типов справочных баз данных. Главный справочник домена (NT Domain Directory Service) хранит информацию о пользователях, которая используется при организации их логического входа в сеть. Данные о тех же пользователях могут содержаться и в другом справочнике, используемом электронной почтой Microsoft Mail. Еще три базы данных поддерживают разрешение низкоуровневых адресов: WINS - устанавливает соответствие Netbios-имен IP-адресам, справочник DNS - сервер имен домена - оказывается полезным при подключении NT-сети к Internet, и наконец, справочник протокола DHCP используется для автоматического назначения IP-адресов компьютерам сети. Ближе к идеалу находятся справочные службы, поставляемые фирмой Banyan (продукт Streettalk III) и фирмой Novell (NetWare Directory Services), предлагающие единый справочник для всех сетевых приложений. Единая база данных, хранящая справочную информацию, предоставляет все то же многообразие возможностей и порождает все то же множество проблем, что и любая другая крупная база данных. Она позволяет осуществлять различные операции поиска, сортировки, модификации и т.п., что очень сильно облегчает жизнь как администраторам, так и пользователям. Набор разрозненных баз данных не предоставляет такого прозрачного доступа к ресурсам сети, как это имеет место в случае использования ОС NetWare 3.x с ее базой bindery, локальной для каждого сервера. В последнем случае пользователь должен заранее знать, на каком сервере находится нужный ему ресурс и производить логическое подключение к этому серверу для получения доступа к этому ресурсу. Для того, чтобы получить доступ к ресурсам какого-нибудь сервера, пользователь должен иметь там свою учетную информацию, которая дублируется таким образом на всех серверах сети. В единой базе данных о каждом пользователе существует только одна запись. Но за удобства приходится расплачиваться решением проблем распределенности, репликации и синхронизации, которые возникают при построении крупномасштабной базы данных для большой сети. Реализация справочной службы над полностью централизованной базой данных, хранящейся только в виде одной копии на одном из серверов сети, не подходит для большой системы по нескольким причинам, и в первую очередь из-за низкой производительности и низкой надежности такого решения. Производительность будет низкой из-за того, что запросы на логический вход всех пользователей будут поступать в единственный сервер, который при большом количестве пользователей обязательно перестанет справляться с их обработкой, то есть такое решение плохо масштабируется в отношении количества пользователей и разделяемых ресурсов. Надежность также не может быть высокой в системе с единственной копией данных. Кроме снятия ограничений по производительности и надежности, желательно, чтобы структура базы данных позволяла производить логическое группирование ресурсов и пользователей по структурным подразделениям предприятия и назначать для каждой такой группы своего администратора. Проблемы сохранения производительности и надежности при увеличении масштаба сети решаются за счет использования распределенных баз данных справочной информации. Разделение данных между несколькими серверами снижает нагрузку на каждый сервер, а надежность при этом достигается за счет наличия нескольких копий (называемых часто репликами) каждой части базы данных. Для каждой части базы данных можно назначить своего администратора, который обладает правами доступа только к объектам своей порции информации о всей системе. Для пользователя же (и для сетевых приложений) такая распределенная база данных представляется единой базой данных, которая обеспечивает доступ ко всем ресурсам сети вне зависимости от того, с какой рабочей станции осуществил свой вход в сеть пользователь. Существует два подхода к организации справочной службы сети: доменный и глобальный. [9]



Вывод

Синхронизация доступа к разделяемым ресурсам многопроцессорных системах осуществляется различными способами, которые имеют свои плюсы и недостатки. Механизм синхронизации выбирается в зависимости от ситуации для более простой реализации.

Синхронизация доступа в сетях осуществляется аналогично архитектурам многопроцессорных систем.



Список литературы

1. http://esyr.org/wiki/Операционные_системы/Взаимодействие_процессов._Разделяемые_ресурсы

2. В.С. Князьков - Многопроцессорные системы

3. http://emanual.ru/download/www.eManual.ru_3210.html

4. http://citforum.ru/hardware/svk/glava_11.shtml

5. http://lib.ru/BACH/chap12.txt

6. http://khpi-iip.mipk.kharkiv.edu/library/extent/os/sos/sos03.html

7. http://www.parallel.ru/computers/taxonomy/flynn.html

8. http://khpi-iip.mipk.kharkiv.edu/library/extent/os/sos/sos03.html

9. http://www.ru.wikipedia.org

Размещено на Allbest.ru