<<
>>

Linda

Системы DSM со страничной организацией памяти (такие как IVY и Treadmarks) используют диспетчера памяти, чтобы аппаратно перехватывать доступ к отсутствующим страницам. Хотя подготовка и пересылка только различающихся слов вместо всей страницы положительно сказывается на производительности, страницы остаются неудобными объектами совместного использования, поэтому применяются и другие подходы.

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

Доступ к этой памяти осуществляется с помощью минимального набора примитивов, которые можно включать в существующие языки (например, в С или FORTRAN), в результате формируются так называемые параллельные языки — в данном случае это C-Linda и FORTRAN-Linda.

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

Каждый из кортежей в пространстве кортежей состоит из одного или нескольких полей. В C-Linda поля могут содержать целые, длинные целые и числа с плавающей точкой, а также сложные типы данных, например массивы (в том числе символьные строки) и с- труктуры (но не другие кортежи). В листинге 8.1. приведено 3 примера кортежей.

Листинг 8.1. Кортежи в Linda

("abc", 2, 5)

("matrix-1", 1, 6, 3.14)

("family", "is sister", Carolyn, Elinor)

С кортежами можно выполнять 4 операции. Первая из них, out, вводит кортеж в пространство кортежей. Например:

outC'abc", 2, 5);

Эта операция вводит кортеж ("abc", 2, 5) в пространство кортежей.

Поля операции out обычно содержат константы, переменные или выражения, например:

out("matrix-Iм, i, j, 3.14);

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

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

inC’abc". 2, ? i);

Эта операция просматривает пространство кортежей в поисках кортежа, состоящего из символьной строки "abc", целого числа 2 и третьего поля, которое может содержать любое целое число (предполагается, что i — целое). Найденный кортеж извлекается из пространства кортежей, а переменной i присваивается значение третьего поля. Поиск совпадения и извлечение являются атомарными действиями. Поэтому когда два процесса одновременно выполняют одну и ту же операцию in, а в пространстве кортежей более нет совпадающих кортежей, успешной оказывается только одна из операций. Пространство кортежей может содержать несколько копий одного кортежа.

Алгоритм поиска совпадения, который используется в операции in, довольно прост. Поля операции in, называемые шаблоном, сравниваются с соответствующими полями каждого кортежа в пространстве кортежей. Совпадение имеет место, если удовлетворены следующие три условия:

♦ шаблон и кортеж имеют одинаковое количество полей;

♦ типы соответствующих полей совпадают;

♦ каждая константа или переменная в шаблоне совпадает с соответствующим полем в кортеже.

Формальные параметры, указываемые знаком вопроса, за которым следует имя переменной или типа, в поиске совпадения не участвуют (за исключением проверки типа), хотя тем параметрам, которые содержат имя переменной, после нахождения совпадения присваиваются значения.

Если совпадающий кортеж не обнаруживается, процесс приостанавливается, пока другой процесс не введет нужный кортеж в пространство кортежей.

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

Третья операция, read, напоминает in, только она не удаляет кортеж из пространства кортежей. Четвертая операция, eval на основе своих параметров строит новый кортеж, который копируется в пространство кортежей. Этот механизм можно использовать для выполнения любых вычислений. Именно так создаются параллельные процессы в системе Linda.

Основной программной парадигмой в Linda является модель тиражируемых рабочих (replicated worker model). В основе модели лежит понятие пакета заданий (task bag), которые должны быть выполнены. Основной процесс начинается с выполнения цикла, содержащего операцию

outC’task-bag", job);

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

in("task-bag", ?job);

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

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

<< | >>
Источник: Таненбаум Э.. Архитектура компьютера. 5-е изд. 2007

Еще по теме Linda:

  1. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  2. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  3. ПЕРЕДМОВА
  4. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  5. Розділ І. Загальні положення цивільного права
  6. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  7. Тема 2. Цивільне законодавство України
  8. Тема 3. Поняття, елементи та види цивільних правовідносин
  9. Тема 4. Здійснення цивільних прав і виконання обов’язків
  10. Тема 5. Захист цивільних прав та інтересів