Last active
December 12, 2015 09:19
-
-
Save kachayev/4751010 to your computer and use it in GitHub Desktop.
Solve sleeping barber problem with many barbers and many client generators
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% | |
%% 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