Тестирование на взаимное исключение в Erlang

Question

В настоящее время у меня есть простой банковский счет, написанный с использованием erlang, у меня также есть тот же банковский счет, переписанный с целью взаимного исключения, идея состоит в том, что невозможно сделать два депозита, где баланс набора/получить может быть interupted так, чтобы конечное значение является неправильным, например, BAL а = 10 бал B = 20:

WRONG 
get_bal.A 0 → get_bal.B 0 → set_bal.A 10 → set_bal.B 20 == 20 
RIGHT 
get_bal.A 0 → set_bal.A 10 → get_bal.B 10 → set_bal.B 30 == 30 

Мой код исходный код выглядит следующим образом:

-module(bank). 
-export([account/1, start/0, stop/0, deposit/1, get_bal/0, set_bal/1]). 

account(Balance) -> 
receive 
    {set, NewBalance} -> 
     account(NewBalance); 
    {get, From} -> 
     From ! {balance, Balance}, 
     account(Balance); 
    stop -> ok 
end. 

start() -> 
    Account_PID = spawn(bank, account, [0]), 
    register(account_process, Account_PID). 

stop() -> 
    account_process ! stop, 
    unregister(account_process). 

set_bal(B) -> 
    account_process ! {set, B}. 

get_bal() -> 
    account_process ! {get, self()}, 
    receive 
    {balance, B} -> B 
end. 

deposit(Amount) -> 
    OldBalance = get_bal(), 
    NewBalance = OldBalance + Amount, 
    set_bal(NewBalance). 

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

account(Balance) -> 
receive 
    {deposit, Amount, From} -> 
     NewBalance = Balance + Amount, 
     From ! {deposit, Amount, NewBalance}, 
     account(NewBalance); 
    {withdraw, Amount, From} when Amount > Balance -> 
     From ! {error, {insufficient_funds, Amount, Balance}}, 
     account(Balance); 
    {withdraw, Amount, From} -> 
     NewBalance = Balance - Amount, 
     From ! {withdrawal, Amount, NewBalance}, 
     account(NewBalance);  
    {get, From} -> 
     From ! {balance, Balance}, 
     account(Balance); 
    stop -> ok 
end. 

deposit(Amount) when Amount > 0 -> 
account_process ! {deposit, Amount, self()}, 
receive 
    {deposit, Amount, NewBalance} -> 
     {ok, NewBalance} 
end. 

withdraw(Amount) when Amount > 0 -> 
account_process ! {withdraw, Amount, self()}, 
receive 
    {withdrawal, Amount, NewBalance} -> 
     {ok, NewBalance}; 
    Error -> 
     Error 
end. 

Спасибо за чтение и любая помощь будет очень признателен.

Answer 1

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

Взгляните на этот вопрос: Is it easy to write traditional concurrency problems in Erlang?

Что касается кода, я бы, вероятно, сделать что-то вроде этого («Банк» представлен как gen_server). Это на самом деле не решение вашей проблемы, но другой способ достижения то же самое с помощью OTP:

-module(bank). 

-behaviour(gen_server). 

%% API 
-export([start_link/0, new_account/1, withdraw/2, deposit/2, get_bal/1]). 

%% gen_server callbacks 
-export([init/1, 
    handle_call/3, 
    handle_cast/2, 
    handle_info/2, 
    terminate/2, 
    code_change/3]). 

-record(state, {accounts = [] :: list()}). 

%%%=================================================================== 
%%% API 
%%%=================================================================== 

start_link() -> 
    gen_server:start_link({local, ?MODULE}, ?MODULE, [], []). 

new_account(Name) -> 
    gen_server:call(?MODULE, {new_account, Name}). 

deposit(Account, Amount) when Amount > 0 -> 
    gen_server:call(?MODULE, {deposit, Account, Amount}). 

withdraw(Account, Amount) when Amount > 0 -> 
    gen_server:call(?MODULE, {withdraw, Account, Amount}). 

get_bal(Account) -> 
    gen_server:call(?MODULE, {get_bal, Account}). 

%%%=================================================================== 
%%% gen_server callbacks 
%%%=================================================================== 

init([]) -> 
    {ok, #state{}}. 

handle_call({new_account, Name}, _From, State) -> 
    Accounts = State#state.accounts, 
    case find_account(Name, Accounts) of 
     none -> 
      {reply, {account_created, Name}, State#state{accounts=[{Name, 0}|Accounts]}}; 
     _ -> 
      {reply, already_exists, State} 
     end; 

handle_call({get_bal, Account}, _From, State) -> 
    Accounts = State#state.accounts, 
    {_Name, Balance} = find_account(Account, Accounts), 
    {reply, Balance, State}; 

handle_call({deposit, Account, Amount}, _From, State) -> 
    Accounts = State#state.accounts, 
    {Name, Balance} = find_account(Account, Accounts), 
    NewBalance = Balance + Amount, 
    NewAccounts = lists:keyreplace(Name, 1, Accounts, {Name, NewBalance}), 
    {reply, {deposit, Amount, NewBalance}, State#state{accounts=NewAccounts}}; 

handle_call({withdraw, Account, Amount}, _From, State) -> 
    Accounts = State#state.accounts, 
    {Name, Balance} = find_account(Account, Accounts), 
    case Amount of 
     Amount when Amount > Balance -> 
      {reply, {insufficient_funds, Amount, Balance}, State}; 
     _ -> 
      NewBalance = Balance - Amount, 
      NewAccounts = lists:keyreplace(Name, 1, Accounts, {Name, NewBalance}), 
      {reply, {withdrawal, Amount, NewBalance}, State#state{accounts=NewAccounts}} 
    end; 

handle_call(_Request, _From, State) -> 
    Reply = not_implemented, 
    {reply, Reply, State}. 

handle_cast(_Msg, State) -> 
    {noreply, State}. 

handle_info(_Info, State) -> 
    {noreply, State}. 

terminate(_Reason, _State) -> 
    ok. 

code_change(_OldVsn, State, _Extra) -> 
    {ok, State}. 

%%%=================================================================== 
%%% Internal functions 
%%%=================================================================== 
find_account(Account, Accounts) -> 
    proplists:lookup(Account, Accounts). 

Answer 2

Ответ подобно тому, как один «повышает производительность узкое место в Erlang». В случае узких мест цель не в том, чтобы улучшить ее (сделать ее более результативной), а скорее полностью ее устранить (что очень редко невозможно).

В случае исключения цель состоит не в том, чтобы доказать, что вы «заблокировали данные X на время процедуры Y и отката на Z», а скорее для того, чтобы писать программы таким образом, чтобы блокировки были полностью ненужным. Я уверен, что есть случаи, когда этого нельзя избежать, но я никогда не встречался с ним в Эрланге (по крайней мере, я не помню). Процессы не разделяют память. Вот почему ответ Стива Виноски на ваш предыдущий (почти идентичный) вопрос (Applying a mutex into an erlang example) продемонстрировал, как вы должны комбинировать операции, а не отделять их шаги от внешнего API.

Если вы выставляете процедуру add(Account, Value), которая точно делает точно loop(Current + Value), если ничего не происходит, убедитесь, что вы просите о неприятностях. Но это демонстрирует крайне низкий уровень API, не так ли? Правильный способ решения этого - сделать то, что Vinoski рекомендовал и раскрыл только API более высокого уровня, который объединяет операции изменения значений и, в которых сообщается о последствиях изменения. Существует нет шанса, что другая ожидающая операция той же формы, исходящая из другого процесса, может изменить значение при попытке прочитать его сейчас, вызывая сбой одного или другого вызова API, поскольку вызовы API - это сообщения которые помещаются в очередь, а не вызовы функций C-стиля, встречающиеся среди разных потоков, которые могут изменять базовое значение одного и того же местоположения в памяти в произвольном порядке без блокировки на них.

Почтовый ящик процесса is Ваш мьютекс. Если вы используете процессы Erlang так, как они предназначены, этот класс ошибок просто не существует. Вы не можете это испортить.Каждое действие полностью атомарно, поставлено в очередь в порядке поступления сообщений, полностью блокирует/блокирует данные, а базовые данные недоступны извне в любом случае.

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

Answer 3

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

Если у вас есть два таких клиентов, управляемых как это, вот что произойдет, если они выполнили последовательность, показанную на ваш вопрос, используя исходный код банка, если клиент А хотел внести 10 и клиент B хочет внести 20:

1. делает get_bal, получает 0
2. B делает get_bal, получает 0
3. делает set_bal(0+10), а учетная запись в настоящее время занимает 10
4. B делает set_bal(0+20), и счет в настоящее время занимает 20

Очевидно, что это неверно, так как баланс в результате счет должен быть 30.

Применяя ту же последовательность клиента с правильными результатами банка в правильном количестве:

1. делает deposit(10), и счет в настоящее время занимает 10
2. B делает deposit(20), а учетная запись в настоящее время занимает 30

Answer 4

Как говорит @Stratus, способ, которым вы написали второй метод, гарантирует, что в методе депозитов нет риска состояния гонки, поскольку сам процесс учета делает операции по балансу + обновлению в одной транзакции.

Если вы хотите убедить себя и сравнить 2 метода, вы можете вызвать множество процессов, которые обновляют одну и ту же учетную запись параллельно и сравнивают фактический баланс после того, как все депозиты будут сделаны до ожидаемого. Следующий код делает тест на депозит:

-module(bank). 
-export([account/1, start/0, stop/0, deposit1/1, deposit2/1, get_bal/0, set_bal/1, withdraw/1]). 

%test 

-export ([test/3,user/3]). 

account(Balance) -> 
receive 
    {set, NewBalance} -> 
     account(NewBalance); 
    {get, From} -> 
     From ! {balance, Balance}, 
     account(Balance); 
    {deposit, Amount, From} -> 
     NewBalance = Balance + Amount, 
     From ! {deposit, Amount, NewBalance}, 
     account(NewBalance); 
    {withdraw, Amount, From} when Amount > Balance -> 
     From ! {error, {insufficient_funds, Amount, Balance}}, 
     account(Balance); 
    {withdraw, Amount, From} -> 
     NewBalance = Balance - Amount, 
     From ! {withdrawal, Amount, NewBalance}, 
     account(NewBalance);  
    stop -> ok 
end. 





start() -> 
    Account_PID = spawn(bank, account, [0]), 
    register(account_process, Account_PID). 

stop() -> 
    account_process ! stop, 
    unregister(account_process). 

set_bal(B) -> 
    account_process ! {set, B}. 

get_bal() -> 
    account_process ! {get, self()}, 
    receive 
     {balance, B} -> B 
    end. 

deposit1(Amount) -> 
    OldBalance = get_bal(), 
    NewBalance = OldBalance + Amount, 
    set_bal(NewBalance). 

deposit2(Amount) when Amount > 0 -> 
    account_process ! {deposit, Amount, self()}, 
    receive 
     {deposit, Amount, NewBalance} -> 
      {ok, NewBalance} 
    end. 

withdraw(Amount) when Amount > 0 -> 
    account_process ! {withdraw, Amount, self()}, 
    receive 
     {withdrawal, Amount, NewBalance} -> 
      {ok, NewBalance}; 
     Error -> 
      Error 
    end. 


test(Nbuser, Nbdeposit, Method) -> 
    start(), 
    done = spawn_users(Nbuser,Nbdeposit,Method,self()), 
    receive_loop(Nbuser), 
    Res = (get_bal() == Nbdeposit*Nbuser), 
    stop(), 
    Res. 

spawn_users(0,_Nbdeposit,_Method,_Pid) -> done; 
spawn_users(Nbuser,Nbdeposit,Method,Pid) -> 
    spawn(?MODULE,user,[Nbdeposit,Method,Pid]), 
    spawn_users(Nbuser-1,Nbdeposit,Method,Pid). 

receive_loop(0) -> done; 
receive_loop(N) -> 
    receive 
     end_deposit -> receive_loop(N-1) 
    end. 

user(0,_,Pid) -> 
    get_bal(), % to be sure that with method deposit1, the last set_bal is processed 
    Pid ! end_deposit; 
user(N,Method,Pid) -> 
    ?MODULE:Method(1), 
    user(N-1,Method,Pid). 

И вы можете убедиться в том, что с 2 пользователей сделать 1 депозит вы получите сообщение об ошибке с помощью метода 1, в то время как с помощью метода 2 вы даже не с 1000 пользователей делают 1000 месторождений.

2> bank:test(1,100,deposit1). 
true 
3> bank:test(2,1,deposit1). 
false 
4> bank:test(1,100,deposit2). 
true 
5> bank:test(2,1,deposit2). 
true 
6> bank:test(1000,1000,deposit2). 
true 

Примечание

Результаты будут зависеть от машины, с которым вы работаете. Я использую четырехъядерный ядро ​​с smp, поэтому неправильный метод не срабатывает немедленно, я думаю, что ему может понадобиться больше пользователей или внести депозит на одном ядре.