Э. Таненбаум - Архитектура компьютера (1127755), страница 178
Текст из файла (страница 178)
Поля операции ооЬ обычно содержат константы, переменные или выражения, например: оогр"дагг1х-1", 1, ), 3.14): Эта операция вводит в пространство кортежей кортеж с четырьмя полями, причем второе и третье поля определяются по текущим значениям переменных 1 и 3. Вторая операция, 1л, извлекает кортеж из пространства кортежей. Обращение к кортежам производится по содержанию, а не по имени или адресу. Поля операции 1л могут содержать выражения или формальные параметры.
Например; ~праЬс". 2. ? 1): Эта операция просматривает пространство кортежей в поисках кортежа, состоящего из символьной строки "аЬс", целого числа 2 и третьего поля, которое может содержать любое целое число (предполагается, что 1 — целое). Найденный кортеж извлекается из пространства кортежей, а переменной 1 присваивается значение третьего поля. Поиск совпадения и извлечение являются атомарными действиями.
Поэтому когда два процесса одновременно выполняют одну и ту же операцию )п, а в пространстве кортежей более нет совпадающих кортежей, успешной оказывается только одна из операций. Пространство кортежей может содержать несколько копий одного кортежа. Алгоритм поиска совпадения, который используется в операции )п, довольно прост. Поля операции )п, называемые шаблоном, сравниваются с соответствующими полями каждого кортежа в пространстве кортежей. Совпадение имеет место, если удовлетворены следующие три условия: + шаблон и кортеж имеют одинаковое количество полей; + типы соответствующих полей совпадают; + каждая константа или переменная в шаблоне совпадает с соответствующим полем в кортеже.
Формальные параметры, указываемые знаком вопроса, за которым следует имя переменной или типа, в поиске совпадения не участвуют (за исключением проверки типа), хотя тем параметрам, которые содержат имя переменной, после нахождения совпадения присваиваются значения. Если совпадающий кортеж не обнаруживается, процесс приостанавливается, пока другой процесс не введет нужный кортеж в пространство кортежей. В этот момент вызывающий процесс автоматически возобновляет работу и обнаруживает новый кортеж.
Процессы блокируются и деблокируются автоматически, по- Ьяультикомпьютеры 695 этому если один процесс готов выводить кортеж, а другой — вводить, то не имеет никакого значения, какой из процессов будет первым. Третья операция, геаб, напоминает 1п, только она не удаляет кортеж из пространства кортежей. Четвертая операция, еча) на основе своих параметров строит новый кортеж, который копируется в пространство кортежей. Этот механизм можно использовать для выполнения любых вычислений. Именно так создаются параллельные процессы в системе Бпла. Основной программной парадигмой в 1лпс)а является модель тиражируемых рабочих (гер1!сасес( ччогкег тоде!).
В основе модели лежит понятие пакета заданий (Саз1с Ъай), которые должны быть выполнены. Основной процесс начинается с выполнения цикла, содержащего операцию ооС!"Сааа-Ьад", )ою . При каждом прохождении цикла одно из заданий вводится в пространство кортежей. Каждый рабочий процесс начинает функционирование с получения кортежа, описывающего задание: 1ЬССааг-Ьад". ?1ЬЬН Затем процесс выполняет это задание. По выполнении задания он получает следующее. Кроме того, во время выполнения в пакет заданий может быть включено новое задание. Таким образом, работа динамически распределяется среди рабочих процессов, и каждый рабочий процесс постоянно занят.
Существуют различные реализации Бпла в мультикомпьютерных системах. Во всех реализациях ключевым является вопрос о том, как распределить кортежи по машинам и как их при необходимости находить. Возможные варианты— широковещание и каталоги. Репликация — это тоже важный вопрос. Подробнее об этом см. !24]. Огса Е1емного иной подход к реализации в мультикомпьютере обшей памяти на прикладном уровне — задействовать для совместного использования не кортежи, полноценные объекты.
Как известно, объекты состоят из внутреннего (скрытого) состояния и методов для операций с этим состоянием. Поскольку программист не имеет прямого доступа к состоянию, появляется возможность совместного использования ресурсов машинами, которые не имеют обсцей физической памяти. Одна из систем, в которых реализован этот подход, называется Отса [16, 18, 19!. Огса — это традиционный язык программирования (в его основе лежит язык Мос(и1а 2), обладающий двумя новыми свойствами — поддержкой объектов и возможностью создавать новые процессы.
Объект в Отса — это абстрактный тип данных, аналогичный объекту в )ача или пакету в Ас(а. Объект инкапсулирует внутренние структуры данных и пользовательские методы, которые называются операциями. Объекты пассивны, то есть они не содержат программных потоков, которым можно посылать сообщения. Процессы получают доступ к внутренним данным объекта путем вызова его методов. Каждый метод в Огса состоит из списка пар предохранитель-блок операторов. Предохранитель — это логическое выражение, которое может принимать 696 Глава 8.
Параллельные компьютерные архитектуры значение истина (Ьгие) или ложь (Уа1 зе). Когда вызывается операция, все ее предохранители оцениваются в произвольном порядке. Если все они ложные, вызывающий процесс приостанавливается до тех пор, пока один из них не станет истинным. При нахождении такого предохранителя выполняется следующий за ним блок операторов. В листинге 8.2 показан объект зтасК с двумя операциями, рцвЬ и рор. Листинг 8.2.
Упрощенный объект з1асК с внутренними данными и двумя операциями ОЬЗесс тшр1ешепаат1оп вааси; сор:тлседег; Ф хранилище Лля стека агаси;аггауГтптедег О. М-Пот тптедег: орегаг1оп роза ттещ: 1птедег); а функция, которая ничего не возвращает Ьед1п зтаси(тор) - ттеш; () лоиещаен злеиент в стек Сор .= Сор я 1; () увеличение указателя стека епб; 1) функция, которая возвращает целое орегат1оп рорт): 1птедег; Ьедтп дцагб Сор>О Оо сор := сор — 1; гесцгп зсаскцсор): тк): епп, Е приостанавливает работу. если стек пуст т) уиенвшает указателя стека Ф возвращает вершину стека Ьед1п Сор:=О; епб; ф инициализация После определения объекта зсасК можно объявлять переменные этого типа: з, с, зтаск: Операция рор содержит предохранитель, поэтому попытка вытолкнуть переменную из пустого стека вызовет приостановку вызывающего процесса до тех пор, пока другой процесс не поместит что-либо в стек.
В Огса имеется оператор порождения нового процесса — оператор ГогК. Новый процесс запускает процедуру, указанную в операторе ГогК. Новому процессу могут передаваться и другие параметры, в том числе объект. Именно так объекты распределяются по ма)пинам. Например: Гог 1 1п 1 .л бо Гогк ГооЬаг1з) оп 1; об: Этот оператор порождает новый процесс на всех машинах с ( по и, запуская программу ГооЬаг в каждом из них.
Поскольку эти и новых процессов (а также исходный процесс) работают параллельно, они все могут помещать элементы в общий стек з и извлекать элементы из общего стека з, как будто все они работают на мультипроцессоре с общей памятью. Такая запись создает два объекта стека и устанавливает переменную сор в каждом объекте на О. Целочисленную переменную К можно поместить в стек з с помощью оператора 5$рцзптк): Мультикомпьютеры 697 Операции с совместно используемыми объектами атомарны и секвенциально состоятельны.
То есть система гарантирует, что если несколько процессов выполняют операции с одним объектом практически одновременно, система сама устанавливает определенную очередность событий, которую воспринимают все процессы. В Огса общие данные и синхронизация реализованы иначе, чем в системах со страничной организацией памяти. В параллельных программах требуются два вида синхронизации. Первый — взаимное исключение. Благодаря взаимному исключению два процесса не могут одновременно выполнять одну и ту >ке критическую секцию кода. В Отса каждая операция с совместно используемым объектом напоминает выполнение критической секции, поскольку система гарантирует, что конечный результат будет таким же, как если бы все критические секции кода выполнялись поочередно. В этом отношении объект в Огса похож на распределенный монитор 195].
Второй вид синхронизации — условная синхронизация, при которой процесс блокируется, ожидая выполнения определенного условия. В Огса условная синхронизация осуществляется при помощи предохранителей. В примере, приведенном в листинге 8.2, процесс, который пытается извлечь из пустого стека элемент, блокируется до появления элементов в стеке. Огса поддерживает репликацию, миграцию и состоятельность объектов, а также вызов для них операций. Каждый объект может находиться в одном из двух состояний: он может быть единственным или реплицированным.
В первом случае объект существует только на одной машине, поэтому все запросы направляются туда. Реплицированный объект присутствует на всех машинах, на которых запущен процесс, использующий этот объект. Это упрощает операцию чтения (поскольку ее можно производить локально), но усложняет обновление. При выполнении операции, которая изменяет реплицированный объект, сначала нужно получить от центрального процесса порядковый номер процесса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
