Глава 9 Параллельное программирование
- 9.1 Области
- 9.2 Domainslib: Библиотека для вложенного параллельного программирования
- 9.3 Параллельный сбор мусора
- 9.4 Модель памяти: простые моменты
- 9.5 Блокирующая синхронизация
- 9.6 Взаимодействие с C-связями
- 9.7 Атомарные операции
В этой главе мы рассмотрим средства параллельного программирования в OCaml. Стандартная библиотека OCaml предоставляет примитивы низкого уровня для параллельного программирования. Мы рекомендуем пользователям использовать библиотеки параллельного программирования более высокого уровня, такие как domainslib. В этом учебнике мы сначала рассмотрим параллельное программирование высокого уровня с использованием domainslib, а затем примитивы низкого уровня, предоставляемые компилятором.
OCaml различает конкурентность и параллельность и предоставляет различные механизмы для их выражения. Конкурентность — это перекрывающееся выполнение задач (раздел 12.24.2), в то время как параллельность — это одновременное выполнение задач. В частности, параллельные задачи перекрываются во времени, а конкурентные задачи могут или не могут перекрываться во времени. Задачи могут выполняться одновременно, уступая друг другу управление. В то время как конкурентность — это механизм структурирования программы, параллельность — это механизм ускорения работы ваших программ. Если вас интересуют механизмы конкурентного программирования в OCaml, обратитесь к разделу 12.24 об обработчиках эффектов и главе 33 о библиотеке потоков.
9.1 Области
Области — это единицы параллельности в OCaml. Модуль Domain предоставляет примитивы для создания и управления областями. Новые области могут быть созданы с помощью функции spawn.
Domain.spawn (fun _ -> print_endline "I ran in parallel") I ran in parallel - : unit Domain.t =
Функция spawn выполняет заданную вычислительную задачу параллельно с вызывающей областью.
Области являются ресурсоемкими сущностями. Каждая область отображается 1:1 на системный поток операционной системы. Каждая область также имеет свое собственное состояние выполнения, которое включает структуры локальные для области для выделения памяти. Следовательно, их создание и уничтожение относительно дорогостоящие.
Рекомендуется, чтобы программы не создавали больше областей, чем доступных ядер.
В этом учебнике мы будем реализовывать, запускать и измерять производительность параллельных программ. Полученные результаты зависят от количества ядер на целевой машине. Этот учебник написан на MacBook Pro с процессором Intel Core i7 с 4 ядрами и 8 аппаратными потоками, работающим на частоте 2,3 ГГц. Можно ожидать примерно 4-кратного прироста производительности на 4 областях для параллельных программ с небольшим взаимодействием между областями и когда машина не загружена. За пределами 4 областей ускорение, вероятно, будет меньше линейного. Мы также будем использовать инструмент командной строки для бенчмаркинга hyperfine для оценки производительности наших программ.
9.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 1 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) = 433494437 $ 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 1 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) = 433494437 fib(42) = 433494437 $ 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-го числа Фибоначчи дважды почти заняло столько же времени, сколько и вычисление его один раз, благодаря параллельности.
9.2 Domainslib: Библиотека для вложенного параллельного программирования
Попробуем распараллелить функцию Фибоначчи. Два рекурсивных вызова можно выполнить параллельно. Однако, наивно распараллеливать рекурсивные вызовы, создавая области для каждого из них, не сработает, так как это создаст слишком много областей.
(* fib_par1.ml *)
let n = try int_of_string Sys.argv.(1) with _ -> 1
let rec fib n =
if n < 2 then 1 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 активных областей одновременно. Попытка создать больше областей вызовет исключение. Как тогда можно распараллелить функцию Фибоначчи?
9.2.1 Распараллеливание функции Фибоначчи с помощью domainslib
Стандартная библиотека OCaml предоставляет только примитивы низкого уровня для конкурентного и параллельного программирования, оставляя библиотеки высокого уровня для разработки и распространения за пределами основного дистрибутива компилятора. Domainslib — такая библиотека для вложенного параллельного программирования, которая иллюстрируется параллелизмом, доступным в рекурсивном вычислении Фибоначчи. Воспользуемся domainslib для распараллеливания рекурсивной программы вычисления Фибоначчи. Рекомендуется установить domainslib с помощью менеджера пакетов opam. В этом руководстве используется версия domainslib 0.4.2.
Domainslib предоставляет механизм async/await для запуска параллельных задач и ожидания их результатов. На основе этого механизма domainslib предоставляет параллельные итераторы. В основе 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 1 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_additional_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 ()
Программа принимает количество областей и входные данные для функции Фибоначчи в качестве первого и второго аргументов командной строки соответственно.
Начнем с функции main. Сначала создаем пул областей, в которых будут выполняться вложенные параллельные задачи. Область, вызывающая функцию run, также будет участвовать в выполнении задач, переданных в пул. В функции run вызываем параллельную функцию Фибоначчи fib_par. Наконец, закрываем пул и печатаем результат.
Для достаточно больших входных данных (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) = 433494437
$ 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 раза быстрее, чем последовательная версия.
9.2.2 Конструкции параллельной итерации
Многие численные алгоритмы используют циклы for. Примитив parallel-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. Следовательно, итерации внешнего цикла не зависят друг от друга и могут выполняться параллельно.
Параллельная версия спектральной нормы показана ниже.
(* 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_additional_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 физических ядра. Отладка и исправление этой проблемы производительности выходит за рамки этого руководства.
9.3 Параллельный сбор мусора
Важным аспектом масштабируемости параллельных программ на OCaml является масштабируемость сборщика мусора (GC). OCaml GC разработан для обеспечения как низкой задержки, так и хорошей параллельной масштабируемости. OCaml имеет генерационный сборщик мусора с небольшой меньшей кучей и большой основной кучей. Новые объекты (до определенного размера) выделяются в меньшей куче. Каждый домен имеет собственную локальную для домена область меньшей кучи, в которую новые объекты выделяются без синхронизации с другими доменам. Когда область меньшей кучи домена исчерпывается, он вызывает остановку мира для сбора меньших куч. В разделе остановки мира все домены параллельно собирают свои области меньшей кучи, эвакуируя выживших в основную кучу.
Для основной кучи каждый домен поддерживает локальные для домена, сегментированные по размеру, пулы памяти, в которые выделяются большие объекты и выжившие из сбора меньшей кучи. Использование локальных пулов для домена избегает синхронизации для большинства выделений основной кучи. Основная куча собирается конкурирующим алгоритмом маркировки и очищения, который включает несколько коротких остановок мира для каждого основного цикла.
В целом, пользователи должны ожидать, что сборщик мусора будет хорошо масштабироваться с увеличением количества доменов, при этом задержка останется низкой. Для получения дополнительной информации о проектировании и оценке сборщика мусора, пожалуйста, ознакомьтесь со статьей ICFP 2020 о Retrofitting Parallelism onto OCaml.
9.4 Модель памяти: Легкие моменты
Современные процессоры и компиляторы агрессивно оптимизируют программы. Эти оптимизации ускоряют программы без изменения последовательных программ, но вызывают неожиданное поведение в параллельных программах. Для использования этих оптимизаций OCaml использует расслабленную модель памяти, которая точно определяет, какое из этих расслабленных поведений программы могут наблюдать. Хотя такие модели трудно использовать напрямую в программировании, модель памяти OCaml предоставляет рецепты, которые сохраняют простоту последовательных рассуждений.
Во-первых, неизменяемые значения могут свободно использоваться между несколькими доменам и могут быть обработаны параллельно. Для изменяемых структур данных, таких как ячейки ссылок, массивы и изменяемые поля записей, программисты должны избегать гонок за данными. Ячейки ссылок, массивы и изменяемые поля записей считаются неатомными структурами данных. Гонка за данными происходит, когда два домена одновременно обращаются к неатомной ячейке памяти без синхронизации, и по крайней мере одно из обращений является записью. OCaml предоставляет несколько способов введения синхронизации, включая атомные переменные (раздел 9.7) и мьютексы (раздел 9.5).
Важно, что для программ без гонок за данными (DRF) OCaml обеспечивает последовательную семантику (SC) — наблюдаемое поведение таких программ может быть объяснено чередованием операций из разных доменов. Это свойство известно как гарантия DRF-SC. Более того, в OCaml гарантия DRF-SC модульна — если часть программы не содержит гонок за данными, то модель памяти OCaml гарантирует, что эти части обладают последовательной согласованностью, несмотря на наличие гонок в других частях программы. Даже для программ с гонками за данными OCaml предоставляет сильные гарантии. Хотя пользователь может наблюдать не последовательное поведение, сбои не происходят.
Для получения дополнительной информации о расслабленных поведенческих моделях в присутствии гонок за данными, пожалуйста, ознакомьтесь с главой о сложных моментах модели памяти (глава 10).
9.5 Блокирующая синхронизация
Домены могут выполнять блокирующую синхронизацию с помощью модулей Mutex, Condition и Semaphore. Эти модули такие же, как и те, которые используются для синхронизации потоков, созданных библиотекой потоков (глава 33). Для ясности, в остальной части этой главы мы будем называть потоки, созданные библиотекой потоков, системными потоками.
Следующая программа реализует конкурирующий стек, используя мьютексы и переменные условия.
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 обеспечивает достаточную синхронизацию между несколькими доменам при использовании стека. Таким образом, гонок за данными нет, когда несколько доменов используют стек параллельно.
9.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 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. Новый созданный домен получает идентификатор домена как 1.
9.6 Взаимодействие с C-связями
Во время параллельного выполнения с несколькими доменам код C, выполняющийся в одном домене, может выполняться параллельно с любым кодом C, выполняющимся в других доменам, даже если ни один из них не освободил «блокировку домена». До OCaml 5.0 C-связи могли предполагать, что если блокировка OCaml-среды не освобождена, то будет безопасно манипулировать глобальным состоянием C (например, инициализировать локальную статическую переменную функции). Это больше не верно при параллельном выполнении с несколькими доменам.
9.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 является атомарной ссылкой.
9.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, чтобы отступить на короткий период, позволяя конкурирующим областям продвинуться вперед перед повторной попыткой не удавшейся операции. Эта реализация стека без блокировок также известна как стек Трейбера.
© 1995-2022 INRIA.
https://v2.ocaml.org/releases/5.0/htmlman/parallelism.html
