Skip to content

Instantly share code, notes, and snippets.

@kachayev
Last active December 12, 2015 09:19
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save kachayev/4751010 to your computer and use it in GitHub Desktop.
Save kachayev/4751010 to your computer and use it in GitHub Desktop.
Solve sleeping barber problem with many barbers and many client generators
%%
%% 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
%% * TODO: each barber can fail with known probability
%%
-module(sleep_barber).
-export([run/4, barber/0, clients_generator/1, simulator/1]).
-define(RANDOM(Min, Max), Min + random:uniform(Max)).
-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) ->
%% create all barbers as separated processes
BarbersQueue = queue:from_list([spawn(?MODULE, barber, [])
|| _ <- lists:seq(1, BarbersCount)]),
%% run simulartor with barbers queue
SimulatorPid = spawn(?MODULE, simulator, [#simulator{ barbers = BarbersQueue
, room = 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
barber()
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(#simulator{ barbers = Barbers
, room = Room
, curr = Curr
, success = Success
, failure = Failure} = Simulator) ->
{NextBarber, Workers} = queue:out(Barbers),
receive
{generator, client} when NextBarber =/= empty ->
{value, Barber} = NextBarber,
io:format("Client goes to barber [~p]~n", [Barber]),
Barber ! {client, self()},
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]),
simulator(Simulator#simulator{curr=Curr+1});
{generator, client} ->
io:format("No free space for client, room size [~p]~n", [Curr]),
simulator(Simulator#simulator{failure=Failure+1});
{barber, Barber} when Curr > 0 ->
io:format("Barber [~p] take client from room, new size [~p]~n", [Barber, Curr-1]),
Barber ! {client, self()},
simulator(Simulator#simulator{success=Success+1, curr=Curr-1});
{barber, Barber} ->
io:format("Barber [~p] finished, idle~n", [Barber]),
simulator(Simulator#simulator{barbers=queue:in(Barber, Barbers)});
{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))
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment