Skip to content

Instantly share code, notes, and snippets.

@kachayev
Created February 11, 2013 17:30
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save kachayev/4755974 to your computer and use it in GitHub Desktop.
Save kachayev/4755974 to your computer and use it in GitHub Desktop.
Solve sleeping barber problem with many barbers and many client generators and barber failures (exit)
%%
%% Solve sleeping barber problem in most general case
%% Task description on Wikipedia:
%% http://en.wikipedia.org/wiki/Sleeping_barber_problem
%%
%% Additions to classic variant:
%% * many barbers
%% * many clients generators with random timeouts between clients
%% * calculation for total served clients
%% * random time for each client to make barber's job
%% * each barber can fail with known probability (0.3)
%%
-module(sleep_barber_exit).
-export([run/4,
barber/0, clients_generator/1,
simulator/2, do_simulator/1]).
-define(RANDOM(Min, Max), Min + random:uniform(Max)).
-define(FAILURE, 3).
-record(simulator, { barbers = queue:new() %% queue with ready-to-work barbers
, room = 3 %% size of room for waiters
, curr = 0 %% count of waiters in room
, success = 0 %% count of clients served
, failure = 0 %% count of barber shop failures
}).
run(BarbersCount, GeneratorsCount, RoomSize, Duration) ->
%% run simulartor with barbers queue
SimulatorPid = spawn(?MODULE, simulator, [BarbersCount, RoomSize]),
%% spawn all clients generators as separated processes
Generators = [spawn(?MODULE, clients_generator, [SimulatorPid])
|| _ <- lists:seq(1, GeneratorsCount)],
%% create timer to close simulator after duration time
timer:send_after(Duration, SimulatorPid, {close, Generators}).
barber() ->
receive
close -> io:format("Barber [~p] finished~n", [self()]);
{client, Simulator} ->
%% "working" with client
timer:sleep(?RANDOM(15, 10)),
%% send to simulator self PID in order
%% to notify that given job is already done
Simulator ! {barber, self()},
%% wait for next client or close sign
case ?RANDOM(0, 10) > ?FAILURE of
true -> barber();
false -> exit(sick)
end
end.
clients_generator(Simulator) ->
Rnd = ?RANDOM(7, 28),
receive
close -> io:format("Clients generator [~p] finished~n", [self()])
after Rnd ->
Simulator ! {generator, client},
clients_generator(Simulator)
end.
simulator(BarbersCount, RoomSize) ->
%% create all barbers as separated linked processes
process_flag(trap_exit, true),
BarbersQueue = queue:from_list([spawn_link(?MODULE, barber, [])
|| _ <- lists:seq(1, BarbersCount)]),
do_simulator(#simulator{ barbers = BarbersQueue
, room = RoomSize}).
do_simulator(#simulator{ barbers = Barbers
, room = Room
, curr = Curr
, success = Success
, failure = Failure} = Simulator) ->
{NextBarber, Workers} = queue:out(Barbers),
receive
%% messages from clients generator
{generator, client} when NextBarber =/= empty ->
{value, Barber} = NextBarber,
io:format("Client goes to barber [~p]~n", [Barber]),
Barber ! {client, self()},
do_simulator(Simulator#simulator{barbers=Workers, success=Success+1});
{generator, client} when NextBarber == empty, Room > Curr ->
io:format("Client goes to room, new size [~p]~n", [Curr+1]),
do_simulator(Simulator#simulator{curr=Curr+1});
{generator, client} ->
io:format("No free space for client, room size [~p]~n", [Curr]),
do_simulator(Simulator#simulator{failure=Failure+1});
%% messages from barber
{barber, Barber} when Curr > 0 ->
io:format("Barber [~p] take client from room, new size [~p]~n", [Barber, Curr-1]),
Barber ! {client, self()},
do_simulator(Simulator#simulator{success=Success+1, curr=Curr-1});
{barber, Barber} ->
io:format("Barber [~p] finished, idle~n", [Barber]),
do_simulator(Simulator#simulator{barbers=queue:in(Barber, Barbers)});
%% close message indicates that work should be stopped just now
{close, ClientsGenerator} ->
io:format("***~nFinish working with [~p] success served clients and [~p] failures~n",
[Success, Failure]),
%% should send close message to all client generators and barbers
lists:map(fun(Generator) -> Generator ! close end, ClientsGenerator),
lists:map(fun(Barber) -> Barber ! close end, queue:to_list(Barbers));
%% catch all messages about barber failures
{'EXIT', Pid, _} ->
io:format("Barber [~p] goes home, need to hire new one~n", [Pid]),
Barber = spawn_link(?MODULE, barber, []),
io:format("New barber [~p] is hired~n", [Barber]),
NewBarbers = queue:in(Barber, queue:filter(fun(Item) -> Item =/= Pid end, Barbers)),
do_simulator(Simulator#simulator{barbers=NewBarbers})
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment