Глава 9 Параллельное программирование
В этой главе мы рассмотрим возможности параллельного программирования в OCaml. Стандартная библиотека OCaml предоставляет низкоуровневые примитивы для параллельного программирования. Мы рекомендуем пользователям использовать библиотеки для параллельного программирования более высокого уровня, такие как domainslib. В этом руководстве сначала будет рассмотрено параллельное программирование высокого уровня с использованием domainslib, а затем низкоуровневые примитивы, доступные компилятору.
OCaml различает конкурентность и параллельность и предоставляет отдельные механизмы для их выражения. Конкурентность — это перекрывающееся выполнение задач (раздел 12.24.2), в то время как параллельность — это одновременное выполнение задач. В частности, параллельные задачи перекрываются во времени, в то время как конкурентные задачи могут или не могут перекрываться во времени. Задачи могут выполняться конкурирующим образом, уступая друг другу управление. В то время как конкурентность — это механизм структурирования программы, параллельность — это механизм, позволяющий ускорить выполнение ваших программ. Если вы заинтересованы в механизмах конкурентного программирования в OCaml, обратитесь к разделу 12.24 по обработчикам эффектов и главе 34 по библиотеке потоков.
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 областях для параллельных программ с небольшой координацией между областями и когда машина не загружена. Помимо 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 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-го числа Фибоначчи дважды практически заняло столько же времени, сколько и его вычисление один раз, благодаря параллельности.
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 активных областей одновременно. Попытка создать больше областей приведёт к исключению. Как тогда можно распараллелить функцию Фибоначчи?
2.1 Распараллеливание функции Фибоначчи с помощью domainslib
Стандартная библиотека OCaml предоставляет только низкоуровневые примитивы для конкурирующего и параллельного программирования, оставляя библиотеки более высокого уровня для разработки и распространения за пределами ядра компилятора. Domainslib — одна из таких библиотек для вложенного параллельного программирования, что иллюстрируется параллелизмом, доступным в рекурсивном вычислении числа Фибоначчи. Воспользуемся domainslib для распараллеливания рекурсивной программы вычисления числа Фибоначчи. Рекомендуется устанавливать domainslib с помощью менеджера пакетов opam. В этом руководстве используется версия domainslib 0.5.0.
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_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, также участвует в выполнении задач, предоставленных в пуле. В функции 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 раза быстрее, чем последовательная версия.
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_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). GC OCaml разработан для обеспечения как низкой задержки, так и хорошей параллельной масштабируемости. OCaml имеет генерационный сборщик мусора с небольшой вспомогательной кучей и большой основной кучей. Новые объекты (до определенного размера) выделяются во вспомогательной куче. Каждый домен имеет свою локальную вспомогательную кучу, в которую новые объекты выделяются без синхронизации с другими доменам. Когда домен исчерпывает свою вспомогательную кучу, он вызывает остановку мира для сбора вспомогательных куч. В секции остановки мира все домены параллельно собирают свои вспомогательные кучи, эвакуируя выжившие объекты в основную кучу.
Для основной кучи каждый домен поддерживает локальные, сегментированные по размеру пулы памяти, в которые выделяются большие объекты и выжившие объекты из вспомогательного сбора. Наличие локальных пулов для каждого домена исключает необходимость синхронизации для большинства выделений основной кучи. Основная куча собирается с помощью конкуретного алгоритма метки и очистки, который включает несколько коротких остановок мира для каждого основного цикла.
В целом, пользователи должны ожидать, что сборщик мусора будет хорошо масштабироваться с увеличением числа доменов, сохраняя при этом низкую задержку. Для получения более подробной информации об архитектуре и оценке сборщика мусора, пожалуйста, ознакомьтесь со статьей ICFP 2020 о Retrofitting Parallelism onto OCaml.
4 Модель памяти: Легкая часть
Современные процессоры и компиляторы агрессивно оптимизируют программы. Эти оптимизации ускоряют программы без изменения поведения последовательных программ, но вызывают неожиданное поведение в параллельных программах. Для использования этих оптимизаций OCaml принимает расслабленную модель памяти, которая точно определяет, какое из этих расслабленных поведений программы могут наблюдать. Хотя эти модели трудно программировать напрямую, модель памяти OCaml предоставляет рецепты, которые сохраняют простоту последовательных рассуждений.
Во-первых, неизменяемые значения могут свободно использоваться в нескольких домена и могут обрабатываться параллельно. Для изменяемых структур данных, таких как ячейки ссылок, массивы и изменяемые поля записей, программисты должны избегать гонок данных. Ячейки ссылок, массивы и изменяемые поля записей являются неатомными структурами данных. Гонка данных возникает, когда два домена одновременно обращаются к неатомной области памяти без синхронизации, и по крайней мере одно из обращений является записью. OCaml предоставляет несколько способов введения синхронизации, включая атомарные переменные (раздел 9.7) и мьютексы (раздел 9.5).
Важно, что для программ без гонок данных (DRF) OCaml обеспечивает последовательно-согласованную (SC) семантику – наблюдаемое поведение таких программ может быть объяснено чередованием операций из разных доменов. Это свойство известно как гарантия DRF-SC. Более того, в OCaml гарантия DRF-SC является модульной – если часть программы не имеет гонок данных, то модель памяти OCaml гарантирует последовательную согласованность этих частей, несмотря на наличие гонок данных в других частях программы. Даже для программ с гонками данных OCaml предоставляет строгие гарантии. Хотя пользователь может наблюдать не последовательно-согласованное поведение, сбои не происходят.
Для более подробной информации о расслабленных поведении при наличии гонок данных, обратитесь к главе о сложной части модели памяти (глава 10).
5 Блокирующая синхронизация
Домены могут выполнять блокирующую синхронизацию с помощью модулей Mutex, Condition и Semaphore. Эти модули аналогичны модулям, используемым для синхронизации потоков, созданных библиотекой потоков (глава 34). Для ясности, в оставшейся части этой главы мы будем называть потоки, созданные библиотекой потоков, systhreads.
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 Взаимодействие с systhreads
Как systhreads взаимодействуют с доменам? Systhreads, созданные в конкретном домене, остаются привязанными к этому домену. Одновременно может выполняться только один systhread с кодом OCaml в конкретном домене. Тем не менее, systhreads, принадлежащие определенному домену, могут выполнять код библиотеки C или системный код параллельно. Systhreads, принадлежащие разным доменам, могут выполняться параллельно.
При использовании systhreads поток, созданный для выполнения вычисления, заданного Domain.spawn, также обрабатывается как systhread. Например, следующая программа создает в общей сложности два домена (включая начальный домен) с двумя systhreads каждый (включая начальный systhread для каждого домена).
(* 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
Эта программа использует общую ячейку ссылок, защищенную мьютексом, для связи между различными systhreads, выполняющимися в двух разных домена. Идентификаторы systhreads уникально идентифицируют systhreads в программе. Начальный домен получает идентификатор домена и идентификатор потока как 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, чтобы отложить выполнение на короткий период, что позволяет другим областям сделать прогресс, прежде чем повторить неудачную операцию. Эта реализация стека без блокировок также известна как стек Требера.
© 1995-2024 INRIA.
https://ocaml.org/manual/5.2/parallelism.html
