Учебное пособие допущен о министерством образования и науки Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в сфере сервиса)» Омск 2005

Вид материала

Учебное пособие

Содержание 4.1. Способы организации управления процессами ММВС сосредоточенного типа ММВС распределенного типа

Подобный материал:

• Учебное пособие Выпуск второй, 4617.34kb.
• В. В. Крупица Личность Коллектив Стиль отношений (социально-психологический аспект), 4876.34kb.
• Учебное пособие для вузов, 3736.61kb.
• Учебное пособие для вузов, 7834.87kb.
• Учебное пособие рекомендовано Министерством общего и профессионального образования, 3469.26kb.
• Учебное пособие красноярск 2003 министерство образования российской федерации, 1240.84kb.
• П. Я. Гальперин введение в психологию Учебное пособие, 3266.24kb.
• Учебное пособие Допущено Министерством образования Российской Федерации в качестве, 2582.59kb.
• В. Ю. Медведев сущность дизайна учебное пособие, 1623.05kb.
• Учебное пособие Рекомендовано Министерством общего и профессионального образования, 4790.13kb.

4.1. Способы организации управления процессами

и ресурсами в многомашинных вычислительных системах

Одним из эффективнейших направлений развития вычислитель-ной техники стало построение так называемых многомашинных вычислительных систем (далее – ММВС). Принципиальным отличием ММВС от многопроцессорных ВМ является то, что каждая машина, входящая в состав ММВС, имеет свою собственную оперативную память. Всю совокупность ММВС обычно разделяют на два крайних по архитектуре класса, которые до сих пор не имеют общепринятого и устоявшегося наименования. Несмотря на отсутствие единой терминологии, один из этих классов чаще всего называют классом «многомашинных вычислительных систем сосредоточенного типа», а другой – классом «многомашинных вычислительных систем распределенного типа» или «распределенных вычислительных систем».

Под ММВС сосредоточенного типа понимают многомодульную (или многоузловую) систему, каждый модуль которой включает центральный процессор, оперативную память, интерфейсное устройство и, возможно, дисковую память для свопинга. Такие модули обычно называют «вычислительными модулями». Все вычислительные модули, как правило, имеют общие периферийные устройства. Для связи отдельных модулей (узлов) используются выделенные интерфейсные линии. Вся система чаще всего располагается в одном помещении и администрируется одной организацией. Такие системы в свою очередь принято подразделять на два типа: «кластер­ные системы» (claster – гроздь), которые состоят из нескольких единиц или десятков (как правило, не более четырех десятков) модулей, и «массово-паралллельные вычислительные системы» или «массивно-параллельные системы» MPP (Massive parallel processing), которые включают более 100 единиц вычислительных модулей. Основными ком­понентами таких систем, то есть отдельными вычислительными модулями чаще всего являются «усеченные» варианты обычных ВМ.

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

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

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

Таким образом, в самом простом случае системные средства обеспечения связи могут быть сведены к двум основным системным вызовам (примитивам): один – для отправки сообщения, другой – для получения сообщения. Соответствующие библиотечные процедуры могут иметь следующий формат:

1) вызов для отправки сообщения send(dest, &mptr);

2) вызов для получения сообщения receive(addr, &mptr).

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

Отметим, что возможны различные варианты этих двух процедур и их параметров.

Описанные выше вызовы представляют собой блокирующие вызовы (иногда на­зываемые синхронными вызовами). Когда процесс обращается к процедуре send, он указывает адресат и буфер, данные из которого следует послать указанному адресату. Пока сообщение посылается, передающий процесс блокирован (то есть приостановлен). Команда, следующая за обращением к процедуре send, не выпол­няется до тех пор, пока все сообщение не будет послано. Аналогично, обращение к процедуре receive не возвращает управления, пока сообщение не бу­дет получено целиком и положено в буфер, адрес которого указан в параметре. Процесс остается приостановленным, пока не прибудет сообщение, даже если на это уйдет несколько часов. В некоторых системах получатель может указать, от кого именно он ожидает прихода сообщения. В этом случае процесс будет блоки­рован, пока не прибудет сообщение от указанного отправителя.

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

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


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

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

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

Таким образом, у отправителя имеется следующий выбор:

1. Блокирующая операция send (центральный процессор простаивает во вре­мя передачи сообщения).

2. Неблокирующая операция send с копированием (время центрального про­цессора теряется на создание дополнительной копии).

3. Неблокирующая операция send с прерыванием (усложняет программу).

4. Копирование при записи (в конечном итоге требуется дополнительная опе­рация копирования).

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

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

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

В более сложной форме, чем рассмотрено выше, передача сообщений скрыта от пользовате­ля под видом вызова удаленной процедуры RPC (Remote Procedure Call).

Идея вызова удаленных процедур состоит в расширении хорошо известного механизма передачи управления и данных внутри программы, выполняющейся на одной ВМ, на передачу управления и данных через коммуникационные каналы, связывающие разные ВМ. Другими словами, программам разрешается вызывать процедуры, расположенные на других ВМ. Когда процесс на ВМ 1 вызывает процедуру на ВМ 2, вызывающий процесс на ВМ 1 приостанавливается, а на ВМ 2 выполняется вызванная процедура. Информация между вызывающим процессом и вызываемой процедурой может передаваться через параметры, а также возвращаться в результате процедуры.

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

Реализация удаленных вызовов существенно сложнее реализации вызовов локальных процедур. Для вызова локальных процедур характерны асимметричность (то есть одна из взаимодействующих сторон является инициатором) и синхронность (то есть выполнение вызывающей процедуры приостанавливается с момента выдачи запроса и возобновляется только после возврата из вызываемой процедуры).

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

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

Эти и некоторые другие проблемы решаются на основе реализации механизма «прозрачности» RPC: вызов удаленной процедуры должен выглядеть максимально похожим на вызов локальной процеду­ры и вызывающей процедуре не требуется знать, что вызываемая процедура находится на другой ВМ, и наоборот.


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

RPC достигает прозрачности следующим путем. Когда вызываемая процедура действительно является удаленной, в библиотеку помещается вместо локальной процедуры другая версия процедуры, называемая клиентским стабом (stub – заглушка). Подобно оригинальной процедуре, стаб вызывается с использованием вызывающей последовательности, так же происходит прерывание при обращении к ядру. Только в отличие от оригинальной процедуры он не помещает параметры в регистры и не запрашивает у ядра данные, вместо этого он формирует сообщение для отправки ядру удаленной ВМ.

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

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

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

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

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

2. Потерян запрос от клиента к серверу. Самое простое решение – через определенное время повторить запрос.

3. Потеряно ответное сообщение от сервера клиенту. Один из вариантов решения проблемы в этом случае – последовательная нумерация всех запросов клиентским ядром. Ядро сервера запоминает номер самого последнего запроса от каждого из клиентов, и при получении каждого запроса выполняет анализ: является ли этот запрос первичным или повторным.

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

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


б) сразу сообщить приложению об ошибке. Этот подход гарантирует, что RPC был выполнен не более одного раза.

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

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

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

Следует подчеркнуть, что при реализации метода вызова удаленных процедур, клиентская процедура, написанная пользователем, выполняет «нормальный» (то есть локальный) процедурный вызов клиентского стаба. Так как клиентская процедура и клиентский стаб находятся в одном адресном пространстве, пара­метры передаются обычным образом. Аналогично, серверная процедура вызыва­ется процедурой в своем адресном пространстве. Таким образом, вместо выполне­ния с помощью процедур send и receive по сути операций ввода-вывода, в методе вызова удаленных процедур связь с удаленными объектами осуществляется при помощи имитации локальных процедурных вызовов.