• Основной язык
• Система модулей
• Объекты в OCaml
• Аргументы с метками
• Полиморфные варианты
• Полиморфизм и его ограничения
• Обобщённые алгебраические типы данных
• Продвинутые примеры с классами и модулями
• Параллельное программирование
• Модель памяти: сложные аспекты

Глава 9. Параллельное программирование

В этой главе мы рассмотрим средства параллельного программирования в OCaml. Стандартная библиотека OCaml предоставляет низкоуровневые примитивы для параллельного программирования. Мы рекомендуем использовать библиотеки параллельного программирования более высокого уровня, такие как domainslib. Сначала в этом руководстве рассматривается параллельное программирование высокого уровня с использованием domainslib, а затем — низкоуровневые примитивы, предоставляемые компилятором.

OCaml различает конкурентность и параллелизм и предоставляет отдельные механизмы для их выражения. Конкурентность — это чередующееся выполнение задач (раздел 12.24.2), тогда как параллелизм — одновременное выполнение задач. В частности, параллельные задачи перекрываются во времени, тогда как конкурентные задачи могут перекрываться во времени, а могут и нет. Задачи могут выполняться конкурентно, передавая управление друг другу. Конкурентность — это способ структурирования программы, а параллелизм — способ ускорить выполнение программ. Если вас интересуют механизмы конкурентного программирования в OCaml, обратитесь к разделу 12.24 об обработчиках эффектов и главе 35 о библиотеке потоков.

1 Домены

Домены — это единицы параллелизма в OCaml. Модуль Domain предоставляет примитивы для создания доменов и управления ими. Новые домены можно запускать с помощью функции spawn.

Domain.spawn (fun _ -> print_endline "I ran in parallel")

I ran in parallel
- : unit Domain.t = 

Функция spawn выполняет заданное вычисление параллельно с вызывающим доменом.

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

Рекомендуется не запускать больше доменов, чем доступно ядер.

В этом руководстве мы будем реализовывать, запускать и измерять производительность параллельных программ. Наблюдаемые результаты зависят от количества ядер, доступных на целевой машине. Руководство написано на MacBook Pro с процессором Intel Core i7 Quad-Core 2,3 ГГц, 4 ядрами и 8 аппаратными потоками. Для параллельных программ с небольшим объёмом взаимодействия между доменами, когда машина не загружена, разумно ожидать примерно четырёхкратного ускорения при запуске на 4 доменах. При использовании более 4 доменов ускорение, вероятно, будет меньше линейного. Для тестирования производительности программ мы также воспользуемся инструментом командной строки hyperfine.

1.1 Присоединение доменов

В качестве примера мы напишем программу для вычисления n-го числа Фибоначчи с помощью рекурсии. Ниже приведена последовательная программа для вычисления n-го числа Фибоначчи.

(* fib.ml *)
let n = try int_of_string Sys.argv.(1) with _ -> 1

let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2)

let main () =
  let r = fib n in
  Printf.printf "fib(%d) = %d\n%!" n r

let _ = main ()

Программу можно скомпилировать и протестировать следующим образом:

$ ocamlopt -o fib.exe fib.ml
$ ./fib.exe 42
fib(42) = 267914296
$ hyperfine './fib.exe 42' # Benchmarking
Benchmark 1: ./fib.exe 42
  Time (mean ± sd):     1.193 s ±  0.006 s    [User: 1.186 s, System: 0.003 s]
  Range (min … max):    1.181 s …  1.202 s    10 runs

Как видим, вычисление 42-го числа Фибоначчи занимает около 1,2 секунды.

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

(* fib_twice.ml *)
let n = int_of_string Sys.argv.(1)

let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2)

let main () =
  let d1 = Domain.spawn (fun _ -> fib n) in
  let d2 = Domain.spawn (fun _ -> fib n) in
  let r1 = Domain.join d1 in
  Printf.printf "fib(%d) = %d\n%!" n r1;
  let r2 = Domain.join d2 in
  Printf.printf "fib(%d) = %d\n%!" n r2

let _ = main ()

Программа запускает два домена, вычисляющих n-е число Фибоначчи. Функция spawn возвращает значение Domain.t, которое можно присоединить, чтобы получить результат параллельного вычисления. Функция join блокирует выполнение до завершения вычисления.

$ ocamlopt -o fib_twice.exe fib_twice.ml
$ ./fib_twice.exe 42
fib(42) = 267914296
fib(42) = 267914296
$ hyperfine './fib_twice.exe 42'
Benchmark 1: ./fib_twice.exe 42
  Time (mean ± sd):     1.249 s ±  0.025 s    [User: 2.451 s, System: 0.012 s]
  Range (min … max):    1.221 s …  1.290 s    10 runs

Как видно, благодаря параллелизму вычисление n-го числа Фибоначчи дважды занимает почти столько же времени, сколько однократное вычисление.

2 Domainslib: библиотека для вложенного параллельного программирования

Попробуем распараллелить функцию вычисления чисел Фибоначчи. Два рекурсивных вызова можно выполнить параллельно. Однако наивная попытка распараллелить рекурсивные вызовы, запуская для каждого из них отдельный домен, не сработает, поскольку будет создано слишком много доменов.

(* fib_par1.ml *)
let n = try int_of_string Sys.argv.(1) with _ -> 1

let rec fib n =
  if n < 2 then n else begin
    let d1 = Domain.spawn (fun _ -> fib (n - 1)) in
    let d2 = Domain.spawn (fun _ -> fib (n - 2)) in
    Domain.join d1 + Domain.join d2
  end

let main () =
  let r = fib n in
  Printf.printf "fib(%d) = %d\n%!" n r

let _ = main ()

fib(1) = 1
val n : int = 1
val fib : int -> int = 
val main : unit -> unit = 

$ ocamlopt -o fib_par1.exe fib_par1.ml
$ ./fib_par1.exe 42
Fatal error: exception Failure("failed to allocate domain")

OCaml допускает не более 128 одновременно активных доменов. Попытка запустить больше доменов приведёт к исключению. Как же тогда распараллелить вычисление чисел Фибоначчи?

2.1 Распараллеливание вычисления чисел Фибоначчи с помощью domainslib

Стандартная библиотека OCaml предоставляет только низкоуровневые примитивы для конкурентного и параллельного программирования, оставляя разработку и распространение библиотек высокого уровня за пределами основной дистрибуции компилятора. Domainslib — такая библиотека для вложенного параллельного программирования, примером которого служит параллелизм при рекурсивном вычислении чисел Фибоначчи. Используем domainslib для распараллеливания рекурсивной программы вычисления чисел Фибоначчи. Рекомендуется установить domainslib с помощью менеджера пакетов opam. В этом руководстве используется domainslib версии 0.5.0.

Domainslib предоставляет механизм async/await для запуска параллельных задач и ожидания их результатов. На его основе domainslib реализует параллельные итераторы. В основе библиотеки лежит эффективная реализация очередей с вытеснением задач, позволяющая эффективно распределять задачи между другими доменами. Ниже приведена параллельная реализация программы вычисления чисел Фибоначчи:

(* fib_par2.ml *)
let num_domains = int_of_string Sys.argv.(1)
let n = int_of_string Sys.argv.(2)

let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2)

module T = Domainslib.Task

let rec fib_par pool n =
  if n > 20 then begin
    let a = T.async pool (fun _ -> fib_par pool (n-1)) in
    let b = T.async pool (fun _ -> fib_par pool (n-2)) in
    T.await pool a + T.await pool b
  end else fib n

let main () =
  let pool = T.setup_pool ~num_domains:(num_domains - 1) () in
  let res = T.run pool (fun _ -> fib_par pool n) in
  T.teardown_pool pool;
  Printf.printf "fib(%d) = %d\n" n res

let _ = main ()

Программа принимает количество доменов и входное значение для функции вычисления чисел Фибоначчи в качестве первого и второго аргументов командной строки соответственно.

Начнём с главной функции. Сначала создадим пул доменов, в котором будут выполняться вложенные параллельные задачи. Домен, вызывающий функцию run, также будет участвовать в выполнении задач, отправленных в пул. Вызовем параллельную функцию вычисления чисел Фибоначчи fib_par внутри функции run. Наконец, завершим работу пула и выведем результат.

Для достаточно больших входных значений (n > 20) функция fib_par асинхронно запускает левый и правый рекурсивные вызовы в пуле с помощью функции async. Функция async возвращает обещание результата. Результат асинхронного вычисления получают, дождавшись выполнения обещания с помощью функции await. Вызов функции await блокирует выполнение до разрешения обещания.

Для небольших входных значений функция fib_par просто вызывает последовательную функцию вычисления чисел Фибоначчи fib. Для небольших задач важно переключаться в последовательный режим. В противном случае затраты на распараллеливание превысят объём доступной работы.

Для простоты мы используем ocamlfind для компиляции этой программы. В общем случае пользователям рекомендуется использовать dune для сборки программ, использующих библиотеки, установленные через opam.

$ ocamlfind ocamlopt -package domainslib -linkpkg -o fib_par2.exe fib_par2.ml
$ ./fib_par2.exe 1 42
fib(42) = 267914296
$ hyperfine './fib.exe 42' './fib_par2.exe 2 42' \
            './fib_par2.exe 4 42' './fib_par2.exe 8 42'
Benchmark 1: ./fib.exe 42
  Time (mean ± sd):     1.217 s ±  0.018 s    [User: 1.203 s, System: 0.004 s]
  Range (min … max):    1.202 s …  1.261 s    10 runs

Benchmark 2: ./fib_par2.exe 2 42
  Time (mean ± sd):    628.2 ms ±   2.9 ms    [User: 1243.1 ms, System: 4.9 ms]
  Range (min … max):   625.7 ms … 634.5 ms    10 runs

Benchmark 3: ./fib_par2.exe 4 42
  Time (mean ± sd):    337.6 ms ±  23.4 ms    [User: 1321.8 ms, System: 8.4 ms]
  Range (min … max):   318.5 ms … 377.6 ms    10 runs

Benchmark 4: ./fib_par2.exe 8 42
  Time (mean ± sd):    250.0 ms ±   9.4 ms    [User: 1877.1 ms, System: 12.6 ms]
  Range (min … max):   242.5 ms … 277.3 ms    11 runs

Summary
  './fib_par2.exe 8 42' ran
    1.35 ± 0.11 times faster than './fib_par2.exe 4 42'
    2.51 ± 0.10 times faster than './fib_par2.exe 2 42'
    4.87 ± 0.20 times faster than './fib.exe 42'

Результаты показывают, что при использовании 8 доменов параллельная программа вычисления чисел Фибоначчи работает в 4,87 раза быстрее последовательной версии.

2.2 Конструкции параллельной итерации

Во многих численных алгоритмах используются циклы for. Примитив параллельного цикла for предоставляет простой способ распараллелить такой код. Возьмём тест spectral-norm из набора тестов производительности языков программирования и распараллелим его. Ниже приведена последовательная версия программы.

(* spectralnorm.ml *)
let n = try int_of_string Sys.argv.(1) with _ -> 32

let eval_A i j = 1. /. float((i+j)*(i+j+1)/2+i+1)

let eval_A_times_u u v =
  let n = Array.length v - 1 in
  for i = 0 to  n do
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A i j *. u.(j) done;
    v.(i) <- !vi
  done

let eval_At_times_u u v =
  let n = Array.length v - 1 in
  for i = 0 to n do
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A j i *. u.(j) done;
    v.(i) <- !vi
  done

let eval_AtA_times_u u v =
  let w = Array.make (Array.length u) 0.0 in
  eval_A_times_u u w; eval_At_times_u w v

let () =
  let u = Array.make n 1.0  and  v = Array.make n 0.0 in
  for _i = 0 to 9 do
    eval_AtA_times_u u v; eval_AtA_times_u v u
  done;

  let vv = ref 0.0  and  vBv = ref 0.0 in
  for i=0 to n-1 do
    vv := !vv +. v.(i) *. v.(i);
    vBv := !vBv +. u.(i) *. v.(i)
  done;
  Printf.printf "%0.9f\n" (sqrt(!vBv /. !vv))

Обратите внимание, что в функциях eval_A_times_u и eval_At_times_u есть вложенные циклы. Каждая итерация тела внешнего цикла читает данные из u, но записывает их в отдельные области памяти в v. Следовательно, итерации внешнего цикла не зависят друг от друга и могут выполняться параллельно.

Параллельная версия spectral norm показана ниже.

(* spectralnorm_par.ml *)
let num_domains = try int_of_string Sys.argv.(1) with _ -> 1
let n = try int_of_string Sys.argv.(2) with _ -> 32

let eval_A i j = 1. /. float((i+j)*(i+j+1)/2+i+1)

module T = Domainslib.Task

let eval_A_times_u pool u v =
  let n = Array.length v - 1 in
  T.parallel_for pool ~start:0 ~finish:n ~body:(fun i ->
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A i j *. u.(j) done;
    v.(i) <- !vi
  )

let eval_At_times_u pool u v =
  let n = Array.length v - 1 in
  T.parallel_for pool ~start:0 ~finish:n ~body:(fun i ->
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A j i *. u.(j) done;
    v.(i) <- !vi
  )

let eval_AtA_times_u pool u v =
  let w = Array.make (Array.length u) 0.0 in
  eval_A_times_u pool u w; eval_At_times_u pool w v

let () =
  let pool = T.setup_pool ~num_domains:(num_domains - 1) () in
  let u = Array.make n 1.0  and  v = Array.make n 0.0 in
  T.run pool (fun _ ->
  for _i = 0 to 9 do
    eval_AtA_times_u pool u v; eval_AtA_times_u pool v u
  done);

  let vv = ref 0.0  and  vBv = ref 0.0 in
  for i=0 to n-1 do
    vv := !vv +. v.(i) *. v.(i);
    vBv := !vBv +. u.(i) *. v.(i)
  done;
  T.teardown_pool pool;
  Printf.printf "%0.9f\n" (sqrt(!vBv /. !vv))

Обратите внимание, что функция parallel_for изоморфна циклу for в последовательной версии. Никаких других изменений не требуется, кроме шаблонного кода для создания и завершения пулов.

$ ocamlopt -o spectralnorm.exe spectralnorm.ml
$ ocamlfind ocamlopt -package domainslib -linkpkg -o spectralnorm_par.exe \
  spectralnorm_par.ml
$ hyperfine './spectralnorm.exe 4096' './spectralnorm_par.exe 2 4096' \
            './spectralnorm_par.exe 4 4096' './spectralnorm_par.exe 8 4096'
Benchmark 1: ./spectralnorm.exe 4096
  Time (mean ± sd):     1.989 s ±  0.013 s    [User: 1.972 s, System: 0.007 s]
  Range (min … max):    1.975 s …  2.018 s    10 runs

Benchmark 2: ./spectralnorm_par.exe 2 4096
  Time (mean ± sd):     1.083 s ±  0.015 s    [User: 2.140 s, System: 0.009 s]
  Range (min … max):    1.064 s …  1.102 s    10 runs

Benchmark 3: ./spectralnorm_par.exe 4 4096
  Time (mean ± sd):    698.7 ms ±  10.3 ms    [User: 2730.8 ms, System: 18.3 ms]
  Range (min … max):   680.9 ms … 721.7 ms    10 runs

Benchmark 4: ./spectralnorm_par.exe 8 4096
  Time (mean ± sd):    921.8 ms ±  52.1 ms    [User: 6711.6 ms, System: 51.0 ms]
  Range (min … max):   838.6 ms … 989.2 ms    10 runs

Summary
  './spectralnorm_par.exe 4 4096' ran
    1.32 ± 0.08 times faster than './spectralnorm_par.exe 8 4096'
    1.55 ± 0.03 times faster than './spectralnorm_par.exe 2 4096'
    2.85 ± 0.05 times faster than './spectralnorm.exe 4096'

На машине автора программа достаточно хорошо масштабируется вплоть до 4 доменов, но работает хуже при использовании 8 доменов. Напомним, что в машине всего 4 физических ядра. Отладка и устранение этой проблемы производительности выходят за рамки данного руководства.

3 Параллельная сборка мусора

Важным аспектом масштабируемости параллельных программ на OCaml является масштабируемость сборщика мусора (GC). Сборщик мусора OCaml спроектирован так, чтобы обеспечивать и низкую задержку, и хорошую масштабируемость при параллельной работе. В OCaml используется поколенческий сборщик мусора с небольшой младшей кучей и большой старшей кучей. Новые объекты (до определённого размера) выделяются в младшей куче. У каждого домена есть собственная локальная область младшей кучи, в которой выделяются новые объекты без синхронизации с другими доменами. Когда область младшей кучи домена исчерпывается, запускается сборка младших куч с остановкой мира. Во время этой приостановки все домены параллельно собирают свои области младшей кучи, перемещая сохранившиеся объекты в старшую кучу.

Для старшей кучи каждый домен поддерживает локальные пулы памяти, разделённые по размерам, в которые выделяются крупные объекты и объекты, пережившие сборку младшей кучи. Локальные пулы позволяют избежать синхронизации при большинстве выделений памяти в старшей куче. Сборка старшей кучи выполняется конкурентным алгоритмом пометки и очистки, который включает несколько коротких приостановок мира в каждом цикле сборки старшей кучи.

В целом пользователям следует ожидать, что сборщик мусора будет хорошо масштабироваться по мере увеличения количества доменов, сохраняя низкую задержку. Подробнее о проектировании и оценке сборщика мусора можно узнать из статьи, представленной на ICFP 2020, Добавление параллелизма в OCaml.

4 Модель памяти: простые аспекты

Современные процессоры и компиляторы активно оптимизируют программы. Эти оптимизации ускоряют выполнение, не влияя на результат последовательных программ, но могут приводить к неожиданному поведению параллельных программ. Чтобы воспользоваться преимуществами этих оптимизаций, OCaml использует ослабленную модель памяти, которая точно определяет, какие из этих ослабленных вариантов поведения могут наблюдаться в программах. Хотя напрямую программировать с такими моделями сложно, модель памяти OCaml предлагает рекомендации, сохраняющие простоту последовательного рассуждения.

Во-первых, неизменяемые значения можно свободно передавать между несколькими доменами и обращаться к ним параллельно. При работе с изменяемыми структурами данных, такими как ячейки ссылок, массивы и изменяемые поля записей, программистам следует избегать гонок данных. Ячейки ссылок, массивы и изменяемые поля записей называются неатомарными структурами данных. Гонка данных возникает, когда два домена одновременно обращаются к неатомарной ячейке памяти без синхронизации и хотя бы одно из обращений является записью. OCaml предоставляет несколько способов введения синхронизации, включая атомарные переменные (раздел 9.7) и мьютексы (раздел 9.5).

Важно отметить, что для программ без гонок данных (DRF) OCaml обеспечивает семантику последовательной согласованности (SC) — наблюдаемое поведение таких программ можно объяснить чередованием операций из разных доменов. Это свойство называется гарантией DRF-SC. Более того, в OCaml гарантия DRF-SC является модульной: если часть программы не содержит гонок данных, модель памяти OCaml обеспечивает последовательную согласованность для этой части, даже если в других частях программы есть гонки данных. Даже для программ с гонками данных OCaml предоставляет сильные гарантии. Пользователь может наблюдать поведение, не соответствующее последовательной согласованности, но сбоев не происходит.

Подробнее об ослабленном поведении при наличии гонок данных см. главу о сложных аспектах модели памяти (глава 10).

5 Блокирующая синхронизация

Домены могут выполнять блокирующую синхронизацию с помощью модулей Mutex, Condition и Semaphore. Эти модули используются и для синхронизации потоков, созданных библиотекой потоков (глава 35). Для ясности далее в этой главе потоки, созданные библиотекой потоков, называются системными потоками. Следующая программа реализует конкурентный стек с помощью мьютекса и условных переменных.

module Blocking_stack : sig
  type 'a t
  val make : unit -> 'a t
  val push : 'a t -> 'a -> unit
  val pop  : 'a t -> 'a
end = struct
  type 'a t = {
    mutable contents: 'a list;
    mutex : Mutex.t;
    nonempty : Condition.t
  }

  let make () = {
    contents = [];
    mutex = Mutex.create ();
    nonempty = Condition.create ()
  }

  let push r v =
    Mutex.lock r.mutex;
    r.contents <- v::r.contents;
    Condition.signal r.nonempty;
    Mutex.unlock r.mutex

  let pop r =
    Mutex.lock r.mutex;
    let rec loop () =
      match r.contents with
      | [] ->
          Condition.wait r.nonempty r.mutex;
          loop ()
      | x::xs -> r.contents <- xs; x
    in
    let res = loop () in
    Mutex.unlock r.mutex;
    res
end

Конкурентный стек реализован в виде записи с тремя полями: изменяемым полем contents, в котором хранятся элементы стека; mutex, контролирующим доступ к полю contents; и условной переменной nonempty, которая используется для оповещения заблокированных доменов, ожидающих, пока стек перестанет быть пустым.

Операция push блокирует мьютекс и обновляет поле contents, присваивая ему новый список, в котором добавляемый элемент становится головой, а старый список — хвостом. Условная переменная nonempty сигнализируется, пока блокировка ещё удерживается, чтобы разбудить домены, ожидающие этого условия. Если ожидающие домены есть, один из них пробуждается. Если их нет, операция signal не оказывает эффекта.

Операция pop блокирует мьютекс и проверяет, пуст ли стек. Если пуст, вызывающий домен ожидает на условной переменной nonempty с помощью примитива wait. Вызов wait атомарно приостанавливает выполнение текущего домена и снимает блокировку с mutex. Когда домен снова пробуждается (то есть вызов wait возвращает управление), блокировка mutex снова принадлежит ему. Домен повторно пытается прочитать содержимое стека. Если операция pop обнаруживает, что стек не пуст, она присваивает полю contents хвост старого списка и возвращает его голову.

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

5.1 Взаимодействие с системными потоками

Как системные потоки взаимодействуют с доменами? Системные потоки, созданные в конкретном домене, остаются привязанными к этому домену. В каждый момент времени только одному системному потоку разрешено выполнять код OCaml в конкретном домене. Однако системные потоки, принадлежащие одному домену, могут параллельно выполнять код библиотек C или системный код. Системные потоки, принадлежащие разным доменам, могут выполняться параллельно.

При использовании системных потоков поток, созданный для выполнения вычисления, переданного в Domain.spawn, также рассматривается как системный поток. Например, следующая программа создаёт в общей сложности два домена (включая исходный домен), в каждом из которых по два системных потока (включая исходный поток каждого домена).

(* dom_thr.ml *)
let m = Mutex.create ()
let r = ref None (* protected by m *)

let task () =
  let my_thr_id = Thread.(id (self ())) in
  let my_dom_id :> int = Domain.self () in
  Mutex.lock m;
  begin match !r with
  | None ->
      Printf.printf "Thread %d running on domain %d saw initial write\n%!"
        my_thr_id my_dom_id
  | Some their_thr_id ->
      Printf.printf "Thread %d running on domain %d saw the write by thread %d\n%!"
        my_thr_id my_dom_id their_thr_id;
  end;
  r := Some my_thr_id;
  Mutex.unlock m

let task' () =
  let t = Thread.create task () in
  task ();
  Thread.join t

let main () =
  let d = Domain.spawn task' in
  task' ();
  Domain.join d

let _ = main ()

$ ocamlopt -I +threads -I +unix unix.cmxa threads.cmxa -o dom_thr.exe dom_thr.ml
$ ./dom_thr.exe
Thread 1 running on domain 1 saw initial write
Thread 0 running on domain 0 saw the write by thread 1
Thread 2 running on domain 1 saw the write by thread 0
Thread 3 running on domain 0 saw the write by thread 2

В этой программе для обмена данными между системными потоками, работающими в двух разных доменах, используется общая ячейка ссылки, защищённая мьютексом. Идентификаторы системных потоков однозначно определяют потоки в программе. Исходный домен получает идентификатор домена 0 и идентификатор потока 0. Новый запущенный домен получает идентификатор домена 1.

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

6 Взаимодействие с привязками C

При параллельном выполнении в нескольких доменах код C, работающий в одном домене, может выполняться параллельно с любым кодом C в других доменах, даже если ни один из них не освободил «блокировку домена». До OCaml 5.0 привязки C могли предполагать, что если блокировка среды выполнения OCaml не освобождена, то глобальное состояние C можно безопасно изменять (например, инициализировать локальное для функции статическое значение). При параллельном выполнении в нескольких доменах это предположение больше неверно.

7 Атомарные операции

Мьютексы, условные переменные и семафоры используются для реализации блокирующей синхронизации между доменами. Для неблокирующей синхронизации OCaml предоставляет атомарные переменные Atomic. Как следует из названия, неблокирующая синхронизация не предоставляет механизмов приостановки и пробуждения доменов. С другой стороны, примитивы, используемые для неблокирующей синхронизации, часто компилируются в атомарные примитивы чтения-модификации-записи, предоставляемые аппаратным обеспечением. Например, следующая программа параллельно увеличивает неатомарный и атомарный счётчики.

(* incr.ml *)
let twice_in_parallel f =
  let d1 = Domain.spawn f in
  let d2 = Domain.spawn f in
  Domain.join d1;
  Domain.join d2

let plain_ref n =
  let r = ref 0 in
  let f () = for _i=1 to n do incr r done in
  twice_in_parallel f;
  Printf.printf "Non-atomic ref count: %d\n" !r

let atomic_ref n =
  let r = Atomic.make 0 in
  let f () = for _i=1 to n do Atomic.incr r done in
  twice_in_parallel f;
  Printf.printf "Atomic ref count: %d\n" (Atomic.get r)

let main () =
  let n = try int_of_string Sys.argv.(1) with _ -> 1 in
  plain_ref n;
  atomic_ref n

let _ = main ()

$ ocamlopt -o incr.exe incr.ml
$ ./incr.exe 1_000_000
Non-atomic ref count: 1187193
Atomic ref count: 2000000

Обратите внимание, что результат с неатомарным счётчиком меньше ожидаемого. Это происходит потому, что неатомарная функция incr эквивалентна следующему коду:

let incr r =
  let curr = !r in
        r := curr + 1

Обратите внимание, что загрузка и сохранение — это две отдельные операции, а операция инкремента в целом не выполняется атомарно. Когда два домена выполняют этот код параллельно, они оба могут прочитать одно и то же значение счётчика curr и увеличить его до curr + 1. Поэтому вместо двух инкрементов произойдёт только один. Атомарный счётчик, напротив, выполняет загрузку и сохранение атомарно благодаря аппаратной поддержке атомарности. Атомарный счётчик возвращает ожидаемый результат.

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

let r = Atomic.make None

let sender () = Atomic.set r (Some "Hello")

let rec receiver () =
  match Atomic.get r with
  | None -> Domain.cpu_relax (); receiver ()
  | Some m -> print_endline m

let main () =
  let s = Domain.spawn sender in
  let d = Domain.spawn receiver in
  Domain.join s;
  Domain.join d

let _ = main ()

Hello
val r : string option Atomic.t = 
val sender : unit -> unit = 
val receiver : unit -> unit = 
val main : unit -> unit = 

Хотя отправитель и получатель конкурируют за доступ к r, гонки данных не возникает, поскольку r — атомарная ссылка.

7.1 Стек без блокировок

Модуль Atomic используется для реализации неблокирующих структур данных без блокировок. Следующая программа реализует стек без блокировок.

module Lockfree_stack : sig
  type 'a t
  val make : unit -> 'a t
  val push : 'a t -> 'a -> unit
  val pop  : 'a t -> 'a option
end = struct
  type 'a t = 'a list Atomic.t

  let make () = Atomic.make []

  let rec push r v =
    let s = Atomic.get r in
    if Atomic.compare_and_set r s (v::s) then ()
    else (Domain.cpu_relax (); push r v)

  let rec pop r =
    let s = Atomic.get r in
    match s with
    | [] -> None
    | x::xs ->
        if Atomic.compare_and_set r s xs then Some x
        else (Domain.cpu_relax (); pop r)
end

Атомарный стек представлен атомарной ссылкой, содержащей список. Операции push и pop используют примитив compare_and_set, чтобы атомарно обновить атомарную ссылку. Выражение compare_and_set r seen v присваивает r значение v тогда и только тогда, когда его текущее значение физически равно seen. Важно, что сравнение и обновление выполняются атомарно. Выражение вычисляется в true, если сравнение прошло успешно (и обновление выполнено), и в false в противном случае.

Если вызов compare_and_set завершается неудачей, значит, в тот же момент другой домен также пытается обновить атомарную ссылку. В этом случае операции push и pop вызывают Domain.cpu_relax, чтобы ненадолго отступить и дать конкурирующим доменам возможность продвинуться, после чего повторяют неудачную операцию. Эта реализация стека без блокировок называется стеком Трайбера.

7.2 Атомарные поля записей

Тип 'a Atomic.t является атомарным аналогом типа ссылок OCaml 'a ref. Начиная с OCaml 5.4, мы также поддерживаем атомарные поля записей, которые должны быть изменяемыми и помечаться атрибутом [@atomic].

Например:

type 'a refcounted = {
  value : 'a;
  mutable readers : int [@atomic];
}

Поле readers является атомарным, поэтому чтение и запись этого поля — атомарные операции, аналогичные Atomic.get и Atomic.set. Другие атомарные операции над этим полем можно выполнять с помощью встроенного узла расширения %atomic.loc: если rc — значение типа foo refcounted, то [%atomic.loc rc.readers] — выражение встроенного типа foo Atomic.Loc.t, позволяющее выполнять атомарные операции, определённые в модуле Atomic.Loc стандартной библиотеки. Эти операции повторяют операции, доступные для атомарных ссылок в модуле Atomic:

# let add_reader rc =
    Atomic.Loc.fetch_and_add [%atomic.loc rc.readers] 1;;

val add_reader : 'a refcounted -> int = 

# #show Atomic.Loc;;

module Loc :
  sig
    type 'a t = 'a atomic_loc
    external get : 'a t -> 'a = "%atomic_load_loc"
    val set : 'a t -> 'a -> unit
    external exchange : 'a t -> 'a -> 'a = "%atomic_exchange_loc"
    external compare_and_set : 'a t -> 'a -> 'a -> bool = "%atomic_cas_loc"
    external fetch_and_add : int t -> int -> int = "%atomic_fetch_add_loc"
    val incr : int t -> unit
    val decr : int t -> unit
  end

Ограничение

В настоящее время для атомарных полей записей нет аналога Atomic.make_contended. Если для конкретного поля записи возникает проблема ложного совместного использования, наилучший поддерживаемый подход — использовать поле типа Atomic.t. В будущем мы надеемся реализовать поддержку заполнения полей записей по запросу.

Примечание о производительности

Внутри [%atomic.loc rc.readers] представлено парой, состоящей из значения записи и смещения поля. Если это выражение непосредственно применяется к атомарному примитиву модуля Atomic.Loc, компилятор оптимизирует создание пары и передаёт значение и смещение как отдельные параметры нижележащему примитиву среды выполнения. С другой стороны, сохранение атомарного расположения в структуре данных или передача его другой функции, не встроенной в код, может привести к выделению памяти под пару. Если вы сомневаетесь, можно проверить промежуточное представление кода -dcmm.