Linda (координационный язык)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:43, 22 мая 2016.
Linda
Спроектировано David Gelernter, Nicholas Carriero
Первый   появившийся 1985

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

Модель

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

  • in — атомарное извлечение кортежа
  • rd — неизменяющее чтение кортежа
  • out — создание кортежа
  • eval — создание нового процесса для обработки кортежей с записью результата в кортеж

Сравнение с другими моделями

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

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

Описание

Кортеж

Кортеж - это упорядоченная последовательность значений

( "Hello", 42, 3.14 ),   ( "P", 5, FALSE, 97, 1024, 2),   ( "worker", 5 ) .

Первый элемент кортежа всегда является символьной строкой и выступает в роли имени кортежа. Так первый кортеж предыдущего примера состоит из имени ("Hello"), элемента целого типа (42) и вещественного числа (3.14). Во втором кортеже кроме имени "P" есть элемент целого типа (5), элемент логического типа (FALSE) и три целых числа. Последний кортеж состоит из двух элементов: имени ("worker") и целого числа (5). Количество элементов в кортеже может быть любым.

Функция OUT

Функция OUT помещает кортеж в пространство кортежей.

out ( "GoProcess", 5);

OUT помещает в пространство кортежей кортеж ("GoProcess", 5). Если такой кортеж уже есть в пространстве кортежей, то появится второй. С помощью функции out нельзя изменить кортеж, уже находящийся в пространстве. Для этого кортеж должен быть сначала оттуда изъят, затем изменен и после этого помещен назад.

Функция EVAL

Функция EVAL похожа на функцию OUT. Разница заключается лишь в том, что дополнительным элементом кортежа у eval является функция пользователя. Для вычисления значения этой функции система Linda порождает параллельный процесс, на основе работы которого она формирует кортеж и помещает его в пространство кортежей.

	eval ("hello", funct( z ), TRUE, 3.1415);

При обработке данного вызова система создаст новый процесс для вычисления функции funct( z ). Когда процесс закончится и будет получено значение w = funct( z ), в пространство кортежей будет добавлен кортеж ("hello", w, TRUE, 3.1415). Функция, вызвавшая eval, не ожидает завершения порожденного параллельного процесса и продолжает свою работу дальше. Следует отметить и то, что пользователь не может явно управлять размещением порожденных параллельных процессов на доступных ему процессорных устройствах - это Linda делает самостоятельно.

Синхронизация процессов

Система Linda не имеет никаких явных средств для синхронизации процессов, но синхронизацию можно написать самому. Предположим, что в некоторой точке нужно выполнить барьерную синхронизацию N процессов. Какой-то один процесс заранее помещает в пространство кортеж ("ForBarrier", N). Подходя к точке синхронизации, каждый процесс выполняет следующий фрагмент, который и будет выполнять функции барьера:

	in( "ForBarrier", formal Bar);
	Bar = Bar - 1;
	if( Bar != 0 ) {
		out( "ForBarrier", Bar);
		read( "Barrier" );
	} else 
		out( "Barrier" );

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

Реализации

Linda была первоначально реализована в C и Fortran, но с тех пор был реализована во многих языках программирования, в том числе:

  • C: C-Linda, TCP-Linda, LinuxTuples
  • C++: CppLinda
  • Erlang: Erlinda
  • Java: JavaSpaces, TSpaces, LightTS, LIME
  • Lisp
  • Lua: LuaTS, Lua Lanes
  • Prolog: SICStus Prolog Linda
  • Python: PyLinda
  • Ruby: Rinda

Литература

  • N.J. Carriero, D. Gelernter, T.G. Mattson, A.H. Sherman The Linda Alternative to Message Passing Systems (англ.) // Parallel Computing. — 1994.
  • Carriero, Nicholas and Gelernter, David How to Write Parallel Programs: A Guide to the Perplexed (англ.) // ACM Comput. Surv.. — ACM, 1989. — ISSN 0360-0300.

Ссылки