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]