Подход первый. Явный параллелизм.Этот подход близок к MPI, но в MPI процессы порождаются при запуске, а нити можно легко порождать в процессе работы. В отчете в этим месте можно порассуждать что лучше и что больше подходит к функциональным языкам вообще, и к Рефалу+ в частности ;).Функция порождения нити - аналогична Apply, только ничего не возвращает. $func ParApply s.func e.args = ; Send-ReceiveИ нужны явные конструкции для синхронизации/передачи сообщений. Можно сделать как в MPI или как в Erlang'е - идентификация номерами, но мне видится, что для Рефала+ более подходящим будет специальный почтовый ящик MsgBox.Чем-то похож на Рефал+'овский ящик, в которой одни кладут, другие - достают. (Об этом тоже можно порассуждать в отчете ;))В итоге нужны функции заведения ящика, посылки и приема: $func MsgBox = s.mbox; $func Send s.mbox e.letter = ; // Посылка сообщения $func Recv s.mbox = e.letter; // Блокирующий прием сообщения $func? IRecv s.mbox = e.letter; // Неблокирующий прием сообщения Семантика Send/Recv - ровно как в MPI: каждой посылке, вызову Send'а, соответствует ровно один успешный прием. Отмечу, что с ящиком могут работать сразу много нитей: все дружно могут писать и читать. Например, чтобы реализовать парадигму Мастер/Раб, когда куча процессов-рабов что-то делают, а один мастер раздает им работу и собирает результаты достаточно двух ящиков:
MsgBox = <Box.Box>; Send s.mbox e.letter = <Box.Put s.mbox (e.letter)>; IRecv s.mbox = <Box.Get s.mbox> : (e.letter) e.other, <Box.Store s.mbox e.other>, e.letter; Монотонные объектыИдеология Send-Receive не слишком вписывается в функциональную парадигму:
$func SOBox = s.sobox; $func Get s.sobox = e.expr; $func Store s.sobox e.expr = ; Такие ящики можно использовать для одной передачи данных между нитями. Одним из наиболее часто используемый способ использоваться SOBox - передача через них результата функции. Для этого определим функцию $func FutureApply s.func e.arg = s.sobox;
Подход второй. Неявный параллелизм.Этот подход навеян Т-системой и прочими неявными параллелизмами в функциональных языках. А так же явной схемой с монотонными объектамиИдея 1 - любой вызов функции можно запустить в параллель (или не считать в ленивых языках), пока результаты функции реально не потребовались. Идея 2 - сделать монотонные объекты неявнями (по сравнению со схемой с монотонными объектами). Над общей памятью этот поход реализуется гораздо проще, чем в OpenTS, поскольку не нужно думать о распределении данных. И, для начала, использовать Явовские нити (примерно как в TSim использует системные, а OpenTS наоборот - свои). Возможно, что Явовских нитей окажется достаточно. Есть мечта поставить куда-нибудь Solaris для экспериментов - в нем есть несколько интересных вещей, которых нет в мире Linux. Одна из них - легкие нити. Чтобы такой подход реализовать нужно в представление данный добавить понятие неготового выражения. Как и в версии над OpenTS, пусть оно будет неготово в глубину. Конечно, можно помечтать о том, чтобы выражение могло быть некоторым в ширину: например, самый левый (и, может одновременно и самый правый) терм известен, а остальные - нет. Но это сложнее и требует существенно менять текущую реализацию выражение - это можно в планах/мечтах писать, но не обещать ;). Из-за того, что есть класс Expr, представляющий неизменяемое выражение, поля которого заполняются при создании, то сделать на его базе неготовое выражение (которое создается неготовым, а заполняется потом специальным методом) достаточно просто. Тогда даже реализация упроститься, поскольку неготовое выражение можно будет использовать для возвращения результатов из функций, даже если функция не вызывается параллельно, для чего сейчас используется специальный класс Result с одним полем типа Expr. Далее потребуется добавить в язык понятие параллельного вызова. При параллельном вызове заводится новая нить, в которой производятся вычисления вызываемой функции. А в вызываемой нити управление возвращается сразу и в качестве результатов возвращаются неготовые выражения. При обращении к некоторым выражениям нить засыпает. Есть два способа добавить параллельный вызов в язык:
Независимо от выбранного подхода придется менять компилятор. Это уже студенту тяжело поручить - долго разбираться будет, но нам с Антоном это сделать несложно (пара дней?). Атомарные операцииКроме
порождения нитей и передачи данных, часто в программирование нужны
атомарные операции - функции, вычисление которых в разных нитях не
может перекрываться во времени. Классические атомарные операции: CompareAndStore , CompareAndSwap и т.п.В Рефале+ атомарные операции нужны над изменяемыми ячейками - ящиками, векторами, таблицами и пр. Для выполнения атомарной операции над ящиками заведена функция $func? AtomicApply s.func s.box e.arg = e.res; Она выполняет <s.func s.box e.arg> над ящиком s.box , т.е. при ее выполнени другие вызовы AtomicApply с тем же s.box не начинают работу до заверщения первого вызова. В каждый момент времени только один вызов AtomicApply для данного s.box работает и он не может прерываться другими вызовами AtomicApply для этого же s.box .Например, если нужно выполнить атомарно Put - добавления выражения в ящик (например, для реализации Send в схеме Send-Receive), то для этого нужно заменить вызов <Put ...> на <AtomicApply &Put ...> :<Put s.box e.data> -> <AtomicApply &Put s.box e.data> Примеры
|