{"id":614,"date":"2011-06-04T20:07:27","date_gmt":"2011-06-04T19:07:27","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=614"},"modified":"2011-06-04T20:23:49","modified_gmt":"2011-06-04T19:23:49","slug":"introduction-to-erlang-shared-memory-example","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2011\/06\/04\/introduction-to-erlang-shared-memory-example\/","title":{"rendered":"Introduction to Erlang : Shared Memory Example"},"content":{"rendered":"<div class=\"seriesmeta\">This entry is part 16 of 16 in the series <a href=\"http:\/\/trigonakis.com\/blog\/series\/introduction-to-erlang\/\" class=\"series-57\" title=\"Introduction to Erlang\">Introduction to Erlang<\/a><\/div><h3>Shared Memory<\/h3>\n<p>This post will be about building step by step a shared memory abstraction in Erlang. As you should all know, variables in Erlang are immutable; once a variable is bound to a value, this value cannot change. Thus in order to implement a mutable variable\/object we need to represent it with a recursive process responsible for keeping the current value and providing the interface for using the object (read and write operations for example).<\/p>\n<p>So, in order to implement a memory abstraction we have to use the aforementioned approach. We can either create a single process to be responsible for keeping the whole address space as a simple list, or create one process for each allocation operation. We will follow the second approach because it is more interesting and protects the memory process from becoming the bottleneck.<\/p>\n<p><strong>Let&#8217;s start<\/strong>!<\/p>\n<h4>The Messaging Interface<\/h4>\n<p>The interface of the memory system is quite simple. We just need the following operations:<\/p>\n<ul>\n<li><code>start<\/code> : for starting the memory system<\/li>\n<li><code>stop<\/code> : for stopping the memory system<\/li>\n<li><code>alloc<\/code> : for allocating memory<\/li>\n<li><code>free<\/code> : for freeing memory<\/li>\n<li><code>read<\/code> : for reading the value of a memory address<\/li>\n<li><code>write<\/code> : for writing to a memory address<\/li>\n<\/ul>\n<p>From the above, the four first operations will be handled by the memory system, while the two last by each memory address (process) that they refer to. We  will create two modules:<\/p>\n<ul>\n<li><code>mem<\/code> : the memory system<\/li>\n<li><code>memif<\/code> : the memory interface<\/li>\n<\/ul>\n<p>and one file called &#8220;common&#8221; with the parameters of the system.<\/p>\n<pre lang=\"erlang\">\r\n-define(MEMREGNAME, mem).\r\n-define(MAXSIZE, 100).\r\n<\/pre>\n<p>This file will be include in both other modules (<code>-include(\"common\")<\/code> directive).<br \/>\n<!--more--><\/p>\n<h5><code>mem:start\/0<\/code><\/h5>\n<p>Starts the memory system and registers the memory process so it can be referred by name. If we do not register the process, then it is impossible to create a simple user interface.<\/p>\n<pre lang=\"erlang\">\r\nstart() ->\r\n\tregister(?MEMREGNAME, spawn(fun mem\/0)).\r\n<\/pre>\n<p>But what happens if we call <code>mem:start\/0<\/code> two consecutive times?<\/p>\n<pre lang=\"erlang\">\r\n2> mem:start().\r\ntrue\r\n3> mem:start().\r\n** exception error: bad argument\r\n     in function  register\/2\r\n        called as register(mem,<0.44.0>)\r\n     in call from mem:start\/0\r\n<\/pre>\n<p>So, we better catch the exception and report to the user that the system has already been started:<\/p>\n<pre lang=\"erlang\">\r\nstart() ->\r\n    try\r\n\tregister(?MEMREGNAME, spawn(fun mem\/0)),\r\n\tstarted\r\n    catch\r\n\t_Error:_Reason ->\r\n\t    already_started\r\n    end.\r\n<\/pre>\n<p>The exception will be caught and the user will get an <code>already_started<\/code> response.<\/p>\n<h5><code>mem:stop\/0<\/code><\/h5>\n<pre lang=\"erlang\">\r\nstop() ->\r\n    try\r\n\t?MEMREGNAME ! {self(), exit, user},\r\n\tstopped\r\n    catch\r\n\t_Error:_Reason ->\r\n\t    not_started\r\n    end.\r\n<\/pre>\n<p>If the memory system is not started, an exception will be thrown and the user will get a <code>not_started<\/code> response.<\/p>\n<h5><code>mem:mem\/0<\/code> &amp; <code>mem:mem\/3<\/code><\/h5>\n<p><code>mem:mem\/0<\/code> will be simply used to call <code>mem:mem\/3<\/code>. We use this intermediate step because we will do some extensions later.<\/p>\n<p>On the other hand, <code>mem:mem\/3<\/code> will provide the main functionality of the memory system:<\/p>\n<pre lang=\"erlang\">\r\nmem() ->\r\n    mem([], [], 0).\r\n\r\n% Memory : pids of the memory objects\r\n% Free : pids of the memory objects that have been freed\r\n% Size : number of memory objects that are being used (==length(Memory)) \r\nmem(Memory, Free, Size) ->\r\n    receive\r\n        % request for memory allocation\r\n\t{From, alloc} ->\r\n\t    ok;\r\n        % free the memory address\r\n\t{From, free, Addr} ->\r\n\t    ok;\r\n        % termination of the system. It terminates all the memory objects before it\r\n        %  terminates\r\n\t{From, exit, Reason} ->\r\n\t    lists:foreach(fun(Memobj) -> exit(Memobj, {From, Reason}) end, Memory ++ Free),\r\n\t    exit({From, Reason});\r\n        % printing the contents of the memory for debugging\r\n\t{_From, print} ->\r\n\t    io:format(\"Size: ~w --~nMemory~n-------~n~p~nFree~n-----~n~p~n\", [Size, Memory, Free])\r\n    end,\t\r\n    mem(Memory, Free, Size).\r\n<\/pre>\n<p>Now lets design how a memory object will look like.<\/p>\n<h5><code>mem:memobj\/1<\/code><\/h5>\n<p>This process is the one representing a memory address. It is the one that provides the <code>read,<\/code> and <code>write<\/code> operations.<\/p>\n<pre lang=\"erlang\">\r\n% Mem is the pid of the memory system process\r\nmemobj(Mem) ->\r\n    % initialize the memory location with 'null'\r\n    memobj(Mem, null).\r\n\r\nmemobj(Mem, Val) ->\r\n    receive\r\n        % return the value to the requester\r\n\t{From, read} ->\r\n\t    From ! {self(), read, Val};\r\n        % write a new value\r\n\t{_From, write, Val1} ->\r\n\t    memobj(Mem, Val1);\r\n\t_ ->\r\n\t    unkonwn\r\n\tend,\r\n    memobj(Mem, Val).\r\n<\/pre>\n<p>I immediately presented the implementation and not only the interface, since it is quite trivial. The <code>memobj<\/code> is only used to keep and change it&#8217;s state (variable <code>Val<\/code>).<\/p>\n<h4>Implementation<\/h4>\n<p>In this section we will implement the unimplemented operations in the <code>mem\/3<\/code> function.<\/p>\n<h5>alloc &#8211; allocating memory<\/h5>\n<p>The operation for allocating memory consists of the following steps:<\/p>\n<ol>\n<li>If the <code>Size<\/code> of the memory system is >= with the <code>?MAXSIZE<\/code>, then the memory is full, so return <code>null<\/code>.<\/li>\n<li>Else, if <code>Free<\/code>-list is not empty, return the head item.<\/li>\n<li>Else, spawn a new <code>memobj<\/code> and return its pid.<\/li>\n<\/ol>\n<pre lang=\"erlang\">\r\n\t{From, alloc} ->\r\n\t    if \r\n\t\tSize < ?MAXSIZE ->\r\n\t\t    case Free of\r\n\t\t\t[Memobj | Frees] ->\r\n\t\t\t    From ! {self(), alloc, Memobj},\r\n\t\t\t    mem([Memobj | Memory], Frees, Size + 1);\r\n\t\t\t_ ->\r\n\t\t\t    Memobj = spawn(?MODULE, memobj, [self()]),\r\n\t\t\t    From ! {self(), alloc, Memobj},\r\n\t\t\t    mem([Memobj | Memory], Free, Size + 1)\r\n\t\t    end;\r\n\t\ttrue ->\r\n\t\t    From ! {self(), alloc, null}\r\n\t    end;\r\n<\/pre>\n<h5>free &#8211; free a memory object<\/h5>\n<p>Message used to free a memory address.<\/p>\n<pre lang=\"erlang\">\r\n\t{_From, free, Addr} ->\r\n\t    case lists:delete(Addr, Memory) of\r\n\t        % if after the delete the Memory is the same ->\r\n\t        %  Addr was not a part of Memory\r\n\t\tMemory ->\r\n\t\t    ok;\r\n\t        % if not -> it was, so decrease the size and add it\r\n\t        %  to the Free-list\r\n\t\tMemory1 ->\r\n\t\t    mem(Memory1, [Addr | Free], Size - 1)\r\n\t    end;\r\n<\/pre>\n<h4>The Application Interface<\/h4>\n<p>The <code>alloc, read, write<\/code>, and <code>free<\/code> operations will be a part of the <code>memif<\/code> module. By registering the pid of the memory system with a name we have the possiblity to simplify the interface.<\/p>\n<h5><code>memif:alloc\/0<\/code><\/h5>\n<p>Allocates a new memory object and returns its pid.<\/p>\n<pre lang=\"erlang\">\r\nalloc() ->\r\n    Mem = whereis(?MEMREGNAME),\r\n    Mem ! {self(), alloc},\r\n    receive\r\n\t{Mem, alloc, Addr} ->\r\n\t    Addr\r\n    end.\r\n<\/pre>\n<p>But if the memory system is not initialized we get<\/p>\n<pre lang=\"erlang\">\r\n3> memif:alloc().\r\n** exception error: bad argument\r\n     in function  memif:alloc\/0\r\n4> mem:start().\r\nstarted\r\n5> memif:alloc().\r\n<0.52.0>\r\n<\/pre>\n<p>So we wrap it around a try-catch statement<\/p>\n<pre lang=\"erlang\">\r\nalloc() ->\r\n    try\r\n\tMem = whereis(?MEMREGNAME),\r\n\tMem ! {self(), alloc},\r\n\treceive\r\n\t    {Mem, alloc, Addr} ->\r\n\t\tAddr\r\n\tend\r\n    catch\r\n\t_:_ ->\r\n\t    mem_not_initialized\r\n    end.\r\n<\/pre>\n<h5><code>memif:free\/1<\/code><\/h5>\n<p>Frees the given memory object, making it available for re-allocation.<\/p>\n<pre lang=\"erlang\">\r\nfree(Addr) ->\r\n    try\r\n\t?MEMREGNAME ! {self(), free, Addr},\r\n\tfreed\r\n    catch\r\n\t_:_ ->\r\n\t    mem_not_initialized\r\n    end.\r\n<\/pre>\n<h5><code>memif:read\/1<\/code><\/h5>\n<p>Returns the value of a memory object. Notice that <code>read\/1<\/code> does not contact the memory system at all.<\/p>\n<pre lang=\"erlang\">\r\nread(Addr) when is_pid(Addr) ->\r\n    Addr ! {self(), read},\r\n    receive\r\n\t{Addr, read, Val} ->\r\n\t    Val\r\n    end;\r\nread(_null) ->\r\n    segmentation_fault.\r\n<\/pre>\n<h5><code>memif:write\/2<\/code><\/h5>\n<p>Writes a new value to a memory object. Notice that <code>write\/2<\/code> does not contact the memory system at all. The write operation is asynchronous (non-blocking) but it can be easily changed to be synchronous.<\/p>\n<pre lang=\"erlang\">\r\nwrite(Addr, Val) when is_pid(Addr) ->\r\n    Addr ! {self(), write, Val},\r\n    written;\r\nwrite(_null, _) ->\r\n    segmentation_fault.\r\n<\/pre>\n<h4>Robustness<\/h4>\n<p>In order to make the memory system a little more robust we will use linking between the memory system and the memory objects. This will help us achieve the following:<\/p>\n<ul>\n<li>If the memory system fails for some reason, the memory objects will also stop executing.<\/li>\n<li>By trapping the exit messages, if a memory object fails, the memory system will get notified.<\/li>\n<\/ul>\n<p>We can first start by <\/p>\n<pre lang=\"erlang\">\r\n mem() ->\r\n    process_flag(trap_exit, true),\r\n    mem([], [], 0).\r\n<\/pre>\n<p>trapping the exits on the <code>mem<\/code> function. Doing this will change the default behavior; if a process to which <code>mem<\/code> is linked fails, <code>mem<\/code> process will not exit, but an <code>{'EXIT', Pid, Reason}<\/code> message will be added to the <code>mem<\/code>&#8216;s message queue. This message can be normally delivered on the <code>receive<\/code> statement of <code>mem\/3<\/code> function.<\/p>\n<pre lang=\"erlang\">\r\n\t{'EXIT', Memobj, _Reason} ->\r\n\t    case lists:delete(Memobj, Memory) of\r\n\t\tMemory ->\r\n\t\t    mem(Memory, lists:delete(Memobj, Free), Size);\r\n\t\tMemory1 ->\r\n\t\t    mem(Memory1, Free, Size - 1)\r\n\t    end;\r\n<\/pre>\n<p>Now, the only thing remaining is to change the <code>spawn<\/code> call with a <code>spawn_link<\/code> call on the <code>alloc<\/code> message clause.<\/p>\n<h4>Example<\/h4>\n<p>With <code>define(MAXSIZE, 10)<\/code>.<\/p>\n<pre lang=\"erlang\">\r\n1> mem:start().\r\nstarted\r\n2> Mems = [memif:alloc() || I <- lists:seq(1, 12)]. \r\n[<0.39.0>,<0.40.0>,<0.41.0>,<0.42.0>,<0.43.0>,<0.44.0>,\r\n <0.45.0>,<0.46.0>,<0.47.0>,<0.48.0>,null,null]\r\n3> [memif:read(Mem) || Mem <- Mems].               \r\n[null,null,null,null,null,null,null,null,null,null,\r\n segmentation_fault,segmentation_fault]\r\n4> lists:foreach(fun(Mem) -> memif:write(Mem, ':)\r\n4> ') end, Mems).\r\nok\r\n5> [memif:read(Mem) || Mem <- Mems].             \r\n[':)\\n',':)\\n',':)\\n',':)\\n',':)\\n',':)\\n',':)\\n',':)\\n',\r\n ':)\\n',':)\\n',segmentation_fault,segmentation_fault]\r\n6> lists:foreach(fun(Mem) -> memif:write(Mem, ':)') end, Mems).\r\nok\r\n7> [memif:read(Mem) || Mem <- Mems].                           \r\n[':)',':)',':)',':)',':)',':)',':)',':)',':)',':)',\r\n segmentation_fault,segmentation_fault]\r\n<\/pre>\n<h4>Code<\/h4>\n<p>You can find the code for the example <a href='http:\/\/trigonakis.com\/blog\/wp-content\/uploads\/2011\/06\/shmem.tar.gz'>here<\/a>.<\/p>\n<h3>Next<\/h3>\n<p>In the next port I will extend this example to support<\/p>\n<ul>\n<li><strong>Virtual Address Space<\/strong> : referencing the address by an integer<\/li>\n<li>and <strong>Replication<\/strong><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<div class=\"seriesmeta\">This entry is part 16 of 16 in the series <a href=\"http:\/\/trigonakis.com\/blog\/series\/introduction-to-erlang\/\" class=\"series-57\" title=\"Introduction to Erlang\">Introduction to Erlang<\/a><\/div><p>Shared Memory This post will be about building step by step a shared memory abstraction in Erlang. As you should all know, variables in Erlang are immutable; once a variable is bound to a value, this value cannot change. Thus in order to implement a mutable variable\/object we need to represent it with a recursive [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[40,51,28],"tags":[26,190,42,189],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p1ouW6-9U","_links":{"self":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/614"}],"collection":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/comments?post=614"}],"version-history":[{"count":7,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/614\/revisions"}],"predecessor-version":[{"id":619,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/614\/revisions\/619"}],"wp:attachment":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/media?parent=614"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/categories?post=614"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/tags?post=614"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}