Created
February 11, 2013 16:59
-
-
Save kachayev/4755741 to your computer and use it in GitHub Desktop.
Solve sleeping barber problem with many barbers and many client generators and barber failures (monitor)
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 | |
%% * each barber can fail with known probability (0.3) | |
%% | |
-module(sleep_barber_monitor). | |
-export([run/4, | |
barber/0, hire_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 -> throw(sick) | |
end | |
end. | |
hire_barber() -> | |
%% create monitor to catch 'DOWN' message on process failure | |
{Pid, _Ref} = spawn_monitor(?MODULE, barber, []), | |
Pid. | |
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 processes | |
BarbersQueue = queue:from_list([hire_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 | |
{'DOWN', _Ref, process, Pid, _} -> | |
io:format("Barber [~p] goes home, need to hire new one~n", [Pid]), | |
Barber = hire_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