Programming Erlang Exercise 8.11

[Charles Gordon-2]

I'm new to Erlang and working my way through Joe Armstrong's "Programming Erlang". I'm a little stumped by exercise 8.11, and I'm hoping someone can give me a hint or two. Here is the full text of the exercise for those of you without the book:

"Write a function start(AnAtom, Fun) to register AnAtom as spawn(Fun). Make sure your program works correctly in the case when two parallel processes simultaneously evaluate start/2. In this case, you must guarantee that one of these processes succeeds and the other fails."

I think I understand the problem to mean that start(AnAtom, Fun) should spawn(Fun) and then register the resulting Pid with AnAtom. Here is my best shot at such a function:

 start(AnAtom, Fun) ->
     case whereis(AnAtom) of
         undefined ->
             Pid = spawn(Fun),
             register(AnAtom, Pid);
         true ->
             true
     end.

The problem didn't specify what the function should return after the first call, so I'm just returning "true" (since that is what "register/2" returns). The trouble I'm having is that I can't see how this avoids a race condition. I don't understand what underlying mechanisms ensure that two parallel processes calling this function don't both evaluate "whereis(AnAtom)", both get "undefined" and both spawn the process (and register it). The problem here is that whereis and register seem to be accessing some sort of shared global state, which is supposed to be impossible. At least, I think they are, since I can't understand how else they would work. What am I missing here?

Thanks!
Charles Gordon


_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[igwan]

Hi,

One solution would be to make the new spawned process call register/2
before calling Fun, but in this case you would use spawn_link instead of
spawn to cause the process calling the start function to exit when the
name is already registered :

start(AnAtom, Fun) ->
    Fun2 = fun() -> register(AnAtom, self()), Fun() end,
    spawn_link(Fun2).

igwan

Charles Gordon a écrit :

> I'm new to Erlang and working my way through Joe Armstrong's
> "Programming Erlang". I'm a little stumped by exercise 8.11, and I'm
> hoping someone can give me a hint or two. Here is the full text of the
> exercise for those of you without the book:
>
> "Write a function start(AnAtom, Fun) to register AnAtom as spawn(Fun).
> Make sure your program works correctly in the case when two parallel
> processes simultaneously evaluate start/2. In this case, you must
> guarantee that one of these processes succeeds and the other fails."
>
> I think I understand the problem to mean that start(AnAtom, Fun)
> should spawn(Fun) and then register the resulting Pid with AnAtom.
> Here is my best shot at such a function:
>
>  start(AnAtom, Fun) ->
>      case whereis(AnAtom) of
>          undefined ->
>              Pid = spawn(Fun),
>              register(AnAtom, Pid);
>          true ->
>              true
>      end.
>
> The problem didn't specify what the function should return after the
> first call, so I'm just returning "true" (since that is what
> "register/2" returns). The trouble I'm having is that I can't see how
> this avoids a race condition. I don't understand what underlying
> mechanisms ensure that two parallel processes calling this function
> don't both evaluate "whereis(AnAtom)", both get "undefined" and both
> spawn the process (and register it). The problem here is that whereis
> and register seem to be accessing some sort of shared global state,
> which is supposed to be impossible. At least, I think they are, since
> I can't understand how else they would work. What am I missing here?
>
> Thanks!
> Charles Gordon
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@...
> http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[igwan]

Oops, forget it, I clicked on send too fast

The function I proposed will not fail when calling it, but exit at a
later time only when the second process happens to call register/2.
I'm interested in a correct/atomic solution too :)

igwan

igwan a écrit :
> start(AnAtom, Fun) ->
>     Fun2 = fun() -> register(AnAtom, self()), Fun() end,
>     spawn_link(Fun2).
>  

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Ladislav Lenart]

igwan wrote:

> Oops, forget it, I clicked on send too fast
>
> The function I proposed will not fail when calling it, but exit at a
> later time only when the second process happens to call register/2.
> I'm interested in a correct/atomic solution too :)
>
> igwan
>
> igwan a écrit :
>> start(AnAtom, Fun) ->
>>     Fun2 = fun() -> register(AnAtom, self()), Fun() end,
>>     spawn_link(Fun2).

Hello,

and what about this:

start(Atom, Fun) when is_atom(Atom), is_function(Fun, 0) ->
        Sender = self(),
        Fun2 = fun() ->
                case catch register(Atom, self()) of
                        true ->
                                Sender ! {started, self()},
                                Fun();
                        _ ->
                                Sender ! {already_running, self()}
                end
        end,
        Pid = spawn(Fun2),
        receive
                {started, Pid} ->
                        {ok, Pid};
                {already_running, Pid} ->
                        already_running
        end.

Hope this helps,

Ladislav Lenart


_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Charles Gordon-2]

From: Ladislav Lenart <lenartlad@... >

start(Atom, Fun) when is_atom(Atom), is_function(Fun, 0) ->
        Sender = self(),
        Fun2 = fun() ->
                case catch register(Atom, self()) of
                        true ->
                                Sender ! {started, self()},
                                Fun();
                        _ ->
                                Sender ! {already_running, self()}
                end
        end,
        Pid = spawn(Fun2),
        receive
                {started, Pid} ->
                        {ok, Pid};
                {already_running, Pid} ->
                        already_running
        end.

Thanks Ladislav, this seems to be the correct solution to the problem. Thanks also to Chris Newcombe who patiently explained to me how this works. For the future readers of this list, I'll reproduce my understanding of it here.

The key insight I was missing is that "register/2" does an atomic test-and-set, so it will only register a given atom once, regardless of how it is called (and how many processes try concurrently). My original solution had the obvious race condition between the "whereis/1" and "register/2" calls. Just getting rid of the call to "whereis/1" wouldn't fix the problem, since you would have already spawned the process by the time you realized someone else had beaten you to registering it. Ladislav's solution starts a process every time "start/2" is called and then has that function register itself. If it succeeds, it runs the original fun, so now the registered atom is linked to the original fun (as the problem requires).

I assumed this meant that the "register/2" BIF was keeping some global shared state that was also accessible via "whereis/1". Chris explained that a better way to look at it, in Erlang, is that register/2 acts as a server for some state (in this case, the registered atoms) and is able to atomically update that state when called by clients. So you can think of it as having a serialized queue of requests and responding to them in order. I'm not sure if that is how it is actually implemented, but it makes sense (to me) to think of it that way.

Any mistakes in the above explanation are definitely mine!

Thanks again,
Charles Gordon

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[y17chen]

how do you compile this and run this? sorry but i'm really lost as how this code works. PlEASE help!!!

Thanks

Charles Gordon-2 wrote:

> From: Ladislav Lenart <[e-mail]>
>
> start(Atom, Fun) when is_atom(Atom), is_function(Fun, 0) ->
>         Sender = self(),
>         Fun2 = fun() ->
>                 case catch register(Atom, self()) of
>                         true ->
>                                 Sender ! {started, self()},
>                                 Fun();
>                         _ ->
>                                 Sender ! {already_running, self()}
>                 end
>         end,
>         Pid = spawn(Fun2),
>         receive
>                 {started, Pid} ->
>                         {ok, Pid};
>                 {already_running, Pid} ->
>                         already_running
>         end.


Thanks Ladislav, this seems to be the correct solution to the problem.
Thanks also to Chris Newcombe who patiently explained to me how this works.
For the future readers of this list, I'll reproduce my understanding of it
here.

The key insight I was missing is that "register/2" does an atomic
test-and-set, so it will only register a given atom once, regardless of how
it is called (and how many processes try concurrently). My original solution
had the obvious race condition between the "whereis/1" and "register/2"
calls. Just getting rid of the call to "whereis/1" wouldn't fix the problem,
since you would have already spawned the process by the time you realized
someone else had beaten you to registering it. Ladislav's solution starts a
process every time "start/2" is called and then has that function register
itself. If it succeeds, it runs the original fun, so now the registered atom
is linked to the original fun (as the problem requires).

I assumed this meant that the "register/2" BIF was keeping some global
shared state that was also accessible via "whereis/1". Chris explained that
a better way to look at it, in Erlang, is that register/2 acts as a server
for some state (in this case, the registered atoms) and is able to
atomically update that state when called by clients. So you can think of it
as having a serialized queue of requests and responding to them in order.
I'm not sure if that is how it is actually implemented, but it makes sense
(to me) to think of it that way.

Any mistakes in the above explanation are definitely mine!

Thanks again,
Charles Gordon

_______________________________________________
erlang-questions mailing list
[e-mail]
http://www.erlang.org/mailman/listinfo/erlang-questions