Erlang 编程/并行编程
Linda 是一种协调多个处理器行动的方式。创建一个元组空间供候选素数存储。创建筛子进程并将消息发送到元组空间以移除非素数。筛子进程还相互发送消息以移除非素数筛子。
该程序可以使用多少个处理器？该程序创建的筛子数量等于矩阵（元组空间）中数字的平方根。如果我们寻找小于 100 的素数，那么大约有 10 个并行的筛子进程。实际上，大多数筛子进程都被停止，最终只剩下（小于 Max 的平方根的素数数量）个进程。这允许轻松地实现 100 的 10 个并行进程和 10000 的 100 个并行进程，只需少量修改。
在 Erlang 中，不建议使用大量原子，因此 N 不应过大。我们也可能耗尽进程或内存。
该程序违反了 Erlang 进程管理的一般规则：不要使用对等管理器。每个筛子进程都是一个对等管理器，因为每个筛子都可能停止其他任何筛子。相反，进程应该在自上而下的树形结构中进行管理。筛子的对等管理会导致一些糟糕的计时问题。计时是使用对等管理器通常是一个坏主意的一大原因。
当 2 的筛子结束时，会转储素数列表。Erlang 应该为每个进程分配相同的 CPU 时间。当时间片均匀时，2 的筛子首先开始，最后结束。当其他一些筛子因时间不足而被饿死时，它可能在 2 的筛子结束后结束，素数转储会过早，导致一些能被 2 整除的数字保留在推测素数列表中。某个进程的相对饥饿大约发生在 10 次中的一次。很明显，关键的词应该是：“尝试”。“Erlang 尝试为每个进程分配相同的时间片。”
运行非素数筛子会有害吗？我们可以使用一个 6 筛子。一个 6 筛子是冗余的，因为 2 筛子和 3 筛子会移除 6 筛子会移除的所有数字。通过移除 6 筛子及其非素数筛子兄弟，我们减少了矩阵必须处理的消息数量，从而加快了最终结果。
-module(primes).
% This is a simple linda tuplespace. Here we use it to find primes numbers.
% This tuplespace cannot have duplicate tuples, but with a prime sieve it does
% not matter.
-compile(export_all).
start() -> start(100). % default value for max is 100
start(Max) ->
io:format(" Loading ~w numbers into matrix (+N) \n ", [ Max ] ),
Lid = spawn_link( primes, linda, [Max, [], [] ]),
Sqrt = round(math:sqrt(Max)+0.5),
io:format(" Sqrt(~w) + 1 = ~w \n " , [Max,Sqrt] ),
io:format(" Tuple space is started ~n ",[]),
io:format(" ~w sieves are spawning (+PN) ~n ", [Sqrt] ),
io:format(" Non prime sieves are being halted (-PN) ~n ", [] ),
% load numbers into tuplespace
% and spawn sieve process
spawn( primes, put_it, [Max, Max, Lid] ).
start_sieves(Lid) ->
Lid ! {self(), get, all, pids},
receive
{lindagram, pids, Pids} -> done
end,
start_sieve_loop(Pids).
start_sieve_loop([]) -> done;
start_sieve_loop([Pid|Pids]) ->
receive
after 100 -> done
end,
Pid ! {start},
start_sieve_loop(Pids).
spawn_sieves( _Max, Sqrt, _Lid, Sqrt ) -> done;
spawn_sieves( Max, Inc, Lid, Sqrt ) ->
T = 1000,
Pid = spawn( primes, sieve, [ Max, Inc+Inc, Inc, Lid, T ]),
Name = list_to_atom("P" ++ integer_to_list(Inc)),
Lid ! {put, pid, Name},
register( Name, Pid),
io:format(" +~s ", [atom_to_list(Name)]),
spawn_sieves( Max, Inc+1, Lid, Sqrt ).
put_it(Max, N, Lid) when N =< 1 ->
Sqrt = round(math:sqrt(Max)+0.5),
spawn_sieves( Max, 2, Lid, Sqrt );
put_it(Max, N,Lid) when N > 1 ->
receive
after 0 ->
Lid ! {put, N, N},
if
N rem 1000 == 0 ->
io:format(" +~w ", [N]);
true -> done
end,
put_it(Max, N-1,Lid)
end.
% the 2 sieve starts last and has the most to do so it finishes last
sieve(Max, N, 2, Lid, _T) when N > Max ->
io:format("final sieve ~w done, ~n", [2] ),
Lid ! {dump,output};
sieve(Max, N, Inc, _Lid, _T) when N > Max ->
io:format("sieve ~w done ", [Inc] );
sieve(Max, N, Inc, Lid, T) when N =< Max ->
receive
after
T -> NT = 0
end,
receive
{lindagram,Number} when Number =/= undefined ->
clearing_the_queue;
{exit} -> exit(normal)
after
1 -> done
end,
% remove multiple of number from tuple-space
Lid ! {self(), get, N},
Some_time = (N rem 1000)==0,
if Some_time -> io:format("."); true -> done end,
% remove (multiple of Inc) from sieve-process space
Name = list_to_atom("P" ++ integer_to_list(N)),
Exists = lists:member( Name, registered()),
if
Exists ->
Name ! {exit},
io:format(" -~s ", [atom_to_list(Name)] );
true -> done
end,
sieve(Max, N+Inc, Inc, Lid, NT). % next multiple
%% linda is a simple tutple space
%% if it receives no messages for 2 whole seconds it dumps its contents
%% as output and halts
linda(Max, Keys, Pids) ->
receive
{put, pid, Pid} ->
linda(Max, Keys, Pids++[Pid]);
{put, Name, Value} ->
put( Name, Value),
linda(Max, Keys++[Name], Pids);
{From, get, Name} ->
From ! {lindagram, get( Name)},
erase( Name ), % get is a destructive read
linda(Max, Keys--[Name],Pids);
{From, get, all, pids} ->
From ! {lindagram, pids, Pids},
linda(Max, Keys, Pids );
{From, get, pid, Pid} ->
L1 = length( Pids ),
L2 = length( Pids -- [Pid]),
if
L1 > L2 -> % if it exists
From ! {lindagram, pid, Pid};
true ->
From ! {lindagram, pid, undefined}
end,
linda(Max, Keys, Pids );
{dump,output} ->
io:format(" ~w final primes remain: ~w ~n ", [length(Keys), lists:sort(Keys) ])
after (100*Max) -> % if there is not tuple action after some time then print the results
io:format(" ~w primes remain: ~w ~n ", [length(Keys), lists:sort(Keys) ])
end.
c(primes). primes:start(1000). Loading 1000 numbers into matrix (+N) Sqrt(1000) + 1 = 32 Tuple space is started 32 sieves are spawning (+PN) Non prime sieves are being halted (-PN) +1000 <0.46.0> +P2 +P3 +P4 +P5 +P6 +P7 +P8 +P9 +P10 +P11 +P12 +P13 +P14 +P15 +P16 +P17 +P18 +P19 +P20 +P21 +P22 +P23 +P24 +P25 +P26 +P27 +P28 +P29 +P30 +P31 -P8 -P6 -P4 -P9 -P12 -P10 -P15 -P15 -P18 -P14 -P21 -P21 -P22 -P26 -P20 -P24 -P25 -P27 -P28 -P30 -P30 -P16 sieve 31 done sieve 29 done sieve 19 done sieve 23 done sieve 11 done sieve 13 done sieve 17 done sieve 7 done .sieve 5 done sieve 3 done .final sieve 2 done, 168 final primes remain: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67, 71,73,79,83,89,97, 101,103,107,109,113,127,131,137,139,149,151,157,163, 167,173,179,181,191,193,197,199, 211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293, 307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397, 401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491, 499,503,509,521,523,541,547,557,563,569,571,577,587,593,599, 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691, 701,709,719,727,733,739,743,751,757,761,769,773,787,797, 809,811,821,823,827,829,839,853,857,859,863,877,881,883,887, 907,911,919,929,937,941,947,953,967,971,977,983,991,997]