MC Sharp

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:36, 2 июня 2016.
MC#
Парадигма Параллельное программирование
Первый   появившийся 2009
Стабильная версия 3.0 / 17 июля 2015
Портал: http://www.mcsharp.net/

Язык программирования MC# является расширением языка C# и предназначен для написания параллельных и распределенных программ. Параллельная программа − это программа, которая предназначена для исполнения на машинах, имеющих несколько ядер/процессоров и общую (разделяемую) память для них. Распределенная программа − это программа, которая предназначена для исполнения на нескольких машинах (возможно, многоядерных), каждая из которых имеет свою собственную память. Примерами систем для исполнения распределенных программ являются кластеры и Grid-сети.

Введение

Язык программирования MC# основан на модели асинхронного параллельного программирования, впервые введенной в языке Polyphonic C#. Особенность этой модели состоит в том, что в ней предложены высокоуровневые параллельные конструкции, которые превращают объектно-ориентированный язык C# в язык параллельного программирования. В частности, они обеспечивают все необходимые средства, которые требуются при параллельном программировании:

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

Эти высокоуровневые конструкции естественным образом входят в объектно-ориентированную модель программирования и, практически, исключают необходимость применения дополнительных библиотек (таких как библиотека System.Threading платформы .NET, а также библиотек Microsoft Parallel Extensions for .NET и Intel Threading Building Blocks). Недостатком последних из вышеназванных библиотек является то, что, во-первых, в них вводится семейство дополнительных параллельных конструкций, таких как потоки (threads) и задачи (tasks), и, во-вторых, они, как таковые, не поддерживают распределенное программирование. В данном документе описываются новые конструкции языка программирования MC# и приводятся законченные примеры их использования для написания параллельных и распределенных программ. Правила компиляции и запуска программ обоих видов приведены в “Руководстве пользователя”, входящем в установочный пакет системы программирования MC#.

Асинхронные методы

В любом из традиционных объектно-ориентированных языков, обычные методы являются синхронными: вызывающая программа всегда ожидает завершения исполнения вызванного метода, и только затем продолжает свою работу. Ключевая особенность языка MC# состоит в добавлении к обычным, синхронным методам так называемых асинхронных методов. Асинхронные методы (а также рассматриваемые далее перемещаемые (movable) методы) − это единственный способ порождения параллельных процессов в языке MC# (традиционные средства порождения параллельных процессов, такие как потоки, являются библиотечными функциями, доступными из программ на языке C#). Общий синтаксис определения асинхронных методов в языке MC# имеет вид:

 модификаторы async имя_метода ( аргументы )
 {
 < тело метода >
 }

Заметим, что ключевое слово async, определяющее метод как асинхронный, располагается на месте типа возвращаемого значения. Соответственно, синтаксическое правило, задающее тип возвращаемого значения в объявлении метода в языке MC#, имеет вид:

 return_type ::= type | void | async | movable

(Таким образом, ключевое слово movable, задающее перемещаемый метод, также должно располагаться на месте типа возвращаемого значения). Задание ключевого слова async при объявлении некоторого метода означает, что при вызове данного метода он будет запущен в виде отдельного потока на данной машине. Отличия async-метода от обычного, синхронного метода состоят в следующем:

  • вызов async-метода заканчивается, по существу, мгновенно, т.е. после вызова такого метода, не дожидаясь завершения его работы, управление передается на оператор, следующий за оператором вызова
  • async-методы не возвращают результатов

Правила корректного определения async-методов в языке MC# включают в себя также следующие требования:

  • async-методы не могут объявляться статическими;
  • в их теле не может использоваться оператор return;
  • к формальным параметрам async-методов не могут применяться модификаторы ref, out и params.

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

 using System;
 public class MatrixMultiplier {
   public static int N = 1000;
   public static int count = 2;
   public static void Main ( String[] args ) {
     double[] a, b, c;
     a = new double [ N, N ];
     b = new double [ N, N ];
     c = new double [ N, N ];
     Random r = new Random();
     for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < N; j++ ) {
          a [ i, j ] = r.NextDouble();
          b [ i, j ] = r.NextDouble();
          c [ i, j ] = 0.0;
        }
     MatrixMultiplier mm = new MatrixMultiplier();
     using ( ManualResetEvent mre = new ManualResetEvent ( false ) )
     {
       mm.multiply ( 0, N/2, a, b, c, mre );
       mm.multiply ( N/2, N, a, b, c, mre );
       mre.WaitOne();
     }
   }
   public async multiply ( int from, int to, double[,] a, double[,] b, double[,] c, ManualResetEvent mre )
   {
     for ( int i = from; i < to; i++ )
       for ( int j = 0; j < N; j++ )
         for ( int k = 0; k < N; k++ )
           c [ i, j ] += a [ i, k ] * b [ k, j ];
     if ( Interlocked.Decrement ( ref count ) == 0 )
       mre.Set()
   }
 }

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

Каналы и обработчики

Каналы и обработчики канальных сообщений (или просто обработчики) представляют собой средства для организации взаимодействия параллельных и распределенных процессов между собой. Второе их назначение в языке MC# − служить средством синхронизации работы вышеуказанных процессов. Синтаксически, каналы и обработчики обычно объявляются в программе с помощью специальных конструкций − связок (chords). Например, объявление канала sendInt для передачи одиночных целочисленных значений вместе с соответствующим обработчиком getInt для получения значений из этого канала выглядит следующим образом:

 handler getInt int() &amp; channel sendInt ( int x ) {
   return x;
 }

В общем случае, синтаксические правила определения связок (и, соответственно, каналов и обработчиков) в языке MC# имеют вид:

 chord-declaration ::= [ handler-header &amp; ] channel-header
  [ &amp; channel-header ]* body
 handler-header ::= attributes modifiers handler handler-name
  return-type ( formal parameters )
 channel-header ::= attributes modifiers channel channel-name
  ( formal parameters )

В приведенных правилах, нетерминалы body, attributes, modifiers, return-type и formal-parameters определяются согласно стандартным синтаксическим правилам языка C#. Нетерминалы handler-name и channel-name являются простыми (т.е., не составными) идентификаторами. При определении каналов и обработчиков действуют следующие ограничения:

  1. каналы и обработчики не могут объявляться статическими
  2. к формальным параметрам каналов и обработчиков не могут применяться модификаторы ref, out и params
  3. если в связке объявлен обработчик с типом возвращаемого значения return-type, то в теле связки должны использоваться операторы return только с выражениями, имеющими тип return-type
  4. все идентификаторы формальных параметров каналов и обработчиков из связки должны быть различными.

Одна из важных ключевых особенностей языка MC# состоит в том, что каналы и обработчики могут передаваться в качестве аргументов методам (в том числе, async- и movable методам) отдельно от объектов, которым они принадлежат (т.е., в рамках которых они объявлены). В этом смысле, каналы и обработчики похожи на указатели на функции в языке C или, в терминах языка C#, на делегатов (delegates).

В соответствии с этим, система типов языка MC# включает в себя типы для каналов и обработчиков:

 type ::= chanel-type | handler-type | …
  channel-type ::= channel ( type-list )
  handler-type ::= handler retur-type ( type-list )
  type-list ::= // empty list
  | type [ , type ]*

Отличие каналов и обработчиков от остальных типов (как скалярных, так и ссылочных) состоит в том, что они могут объявляться только в составе связок, т.е., с обязательным указанием тела связки. Следствием этого является то, что каналы и обработчики не могут объявляться аналогично другим типам − например, объявление

public channel с1;

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

Синтаксис оператора посылки значений по каналу во многом совпадает с синтаксисом вызова обычного метода и имеет вид:

 [ qualified-object-name. ] channel-name ! ( argument-list );

Например, для посылки по каналу sendInt, объявленного в рамках объекта a, целого числа n, необходимо записать выражение

 a.sendInt ! ( n );

Синтаксис оператора вызова обработчика имеет двойственный вид:

 [ qualified-object-name.] handler-name ? ( argument-list );

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

 int x = (int) a.getInt ? ();

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

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

 sendStop ! ( );

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

 for ( i = 0; i < N; i++ )
 atc.getStop ? ();
 using System;
 public class AsyncTerminationClass {
   public static int N = 10;
   public static void Main ( String[] args ) {
     int i;
     AsyncTerminationClass atc = new AsyncTerminationClass();
     for ( i = 0; i < N; i++ )
       atc.a_method ( i, atc.sendStop );
     for ( i = 0; i < N; i++ )
       atc.getStop ?();
   }
   public async a_method ( int myNumber, channel () sendStop )
   {
     Console.WriteLine ( “Process “ + myNumber );
     sendStop ! ();
   }
   public handler getStop void() &amp; public channel sendStop () {
   return;
 }

Пример 3. Данный пример иллюстрирует использование связок в качестве средства синхронизации. Например, для связки вида

 public handler Get2 long () &amp; channel c1 ( long x )
 &amp; channel c2 ( long y )
 {
   return ( x + y );
 }

Тело связки сработает и обработчик Get2 возвратит значение только в случае когда по обоим каналам c1 и c2 посланы значения. В общем случае, один обработчик может быть связан с произвольным числом каналов. Связка, приведенная выше, обычно используется для

  1. обнаружения завершения работы async-методов
  2. получения значений от этих методов.

В примере, показанном ниже – программе вычисления чисел Фибоначчи, вычисление n-го числа Фибоначчи сводится к рекурсивному вычислению n- 1-го и n-2-го чисел Фибоначчи асинхронно. Соответствующая связка позволяет обнаружить завершение вычисления рекурсивно вызванных методов и получить от них результирующие значения.

 using System;
 public class Fib
 {
   public handler Get2 long() &amp; channel c1( long x ) &amp; channel c2( long y ) {
   return x + y;
 }
 public async Compute( long n, channel( long ) c )
 {
   Console.WriteLine( "Compute: n=" + n );
   if ( n <= 1 )
     c ! ( 1 );
   else
   {
     new Fib().Compute( n-1, c1 );
     new Fib().Compute( n-2, c2 );
     c ! ( (long)Get2 ? () );
   }
 }
 public class ComputeFib
 {
   handler Get long() &amp; channel c( long x ) {
   return x;
 }
 public static void Main( string[] args )
 {
   if ( args.Length < 1 )
   {
     Console.WriteLine( "Usage: Fib.exe <number>" );
     return;
   }
   int n = System.Convert.ToInt32( args [ 0 ] );
   ComputeFib cf = new ComputeFib();
   Fib fib = new Fib();
   fib.Compute( n, cf.c );
   Console.WriteLine( "For n = " + n + " value is " + cf.Get?() );
 }

Распределенное программирование на языке MC#

Под “распределенным программированием” понимается написание программ, предназначенных для исполнения на сети из двух и более компьютеров (например, на вычислительном кластере, состоящем, как правило, из головного узла и множества рабочих узлов). Особенность языка MC# заключается в том, что в нем сохраняется единая модель программирования как для локального (в рамках одной многоядерной/многопроцессорной машины), так и для распределенного случаев. А именно, для порождения локальных асинхронных потоков используются async-методы, а для порождения асинхронных потоков, которые могут быть спланированы для исполнения на другой машине, используются, так называемые, “перемещаемые” или movable-методы. Синтаксис определения movable-методов аналогичен синтаксису async-методов, за исключением того, с первыми из названных методов может использоваться только модификатор public:

[ public ] movable имя_метода ( аргументы )
{
< тело метода >
}

Отличия movable-методов от обычных методов и правила их корректного определения в языке MC# совпадают с аналогичными отличиями и правилами для async-методов (см. Раздел 2 “Асинхронные методы”). При разработке распределенной программы на языке MC# необходимо учитывать следующие особенности её выполнения, связанные с передачей объектов и значений между различными машинами на которых выполняется программа. Во-первых, объекты, создаваемые во время исполнения MC#-программы, являются, по своей природе статическими: после своего создания они остаются привязанными к тому месту (машине), где они были созданы, и в дальнейшем не перемещаются. Однако, при вызове movable-метода, все необходимые данные для этого, а именно:

  1. сам объект, которому принадлежит данный movable-метод
  2. аргументы вызова (как скалярные, так и ссылочные)

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

Пример 4. В приведенном ниже примере, вызов movable-метода Compute, в котором производится изменение поля x, никак не влияет на значение этого поля объекта b в главной программе.

 class A {
   public static void Main ( String[] args ) {
     B b = new B ();
     b.x = 1;
     Console.WriteLine ( “Before movable method call: x = “ + b.x );
     b.Compute ();
     Console.WriteLine ( “After movable method call: x = “ + b.x );
   }
 }
 class B {
   public int x;
   public B () { }
   movable Compute () {
   x = 2;
 }
}

Исполнение этой программы приведет к печати на консоли сообщений:

 Before movable method call: x = 1
 After movable method call: x = 1

Пример 5. Программу из Примера 3 легко переделать в распределенную программу, заменив в определении метода Compute ключевое слово async на слово movable:

 using System;
 public class Fib
 {
   public handler Get2 long() &amp; channel c1( long x ) &amp; channel c2( long y ) {
   return x + y;
 }
 movable Compute( long n, channel( long ) c )
 {
   Console.WriteLine( "Compute: n=" + n );
   if ( n <= 1 )
     c ! ( 1 );
   else
   {
     new Fib().Compute( n-1, c1 );
     new Fib().Compute( n-2, c2 );
     c ! ( (long)Get2 ? () );
   }
 }

 public class ComputeFib
 {
   handler Get long() &amp; channel c( long x ) {
   return x;
 }
 public static void Main( string[] args )
 {
   if ( args.Length < 1 )
   {
     Console.WriteLine( "Usage: Fib.exe <number>" );
     return;
   }
   int n = System.Convert.ToInt32( args [ 0 ] );
   ComputeFib cf = new ComputeFib();
   Fib fib = new Fib();
   fib.Compute( n, cf.c );
   Console.WriteLine( "For n = " + n + " value is " + cf.Get?() );
 }

Каналы и обработчики могут передаваться в качестве аргументов movable-методам отдельно от объектов, которым они принадлежат. Одна из ключевых особенностей исполнения распределенных MC#-программ состоит в том, что при копировании каналов и обработчиков на удаленную машину автономно или в составе некоторого объекта, они становятся прокси-объектами, или посредниками для оригинальных каналов и обработчиков. Такая подмена скрыта для прикладного программиста − он может использовать переданные каналы и обработчики на удаленной машине (а, в действительности, их прокси-объекты) также, как и оригинальные: как обычно, все действия с прокси-объектами перенаправляются Runtime-системой на исходные каналы и обработчики. В этом отношении, каналы и обработчики отличаются от обычных объектов: модификации последних на удаленной машине не переносятся на исходные объекты.

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

Смотри также