Distributed Life

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 process responsible for keeping the current value and providing the interface for using the object (read and write operations for example).

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.

Let’s start!

The Messaging Interface

The interface of the memory system is quite simple. We just need the following operations:

• start : for starting the memory system
• stop : for stopping the memory system
• alloc : for allocating memory
• free : for freeing memory
• read : for reading the value of a memory address
• write : for writing to a memory address

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:

• mem : the memory system
• memif : the memory interface

and one file called “common” with the parameters of the system.

-define(MEMREGNAME, mem).
-define(MAXSIZE, 100).

This file will be include in both other modules (-include("common") directive).

mem:start/0

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.

start() ->
	register(?MEMREGNAME, spawn(fun mem/0)).

But what happens if we call mem:start/0 two consecutive times?

2> mem:start().
true
3> mem:start().
** exception error: bad argument
     in function  register/2
        called as register(mem,<0.44.0>)
     in call from mem:start/0

So, we better catch the exception and report to the user that the system has already been started:

start() ->
    try
	register(?MEMREGNAME, spawn(fun mem/0)),
	started
    catch
	_Error:_Reason ->
	    already_started
    end.

The exception will be caught and the user will get an already_started response.

mem:stop/0

stop() ->
    try
	?MEMREGNAME ! {self(), exit, user},
	stopped
    catch
	_Error:_Reason ->
	    not_started
    end.

If the memory system is not started, an exception will be thrown and the user will get a not_started response.

mem:mem/0 & mem:mem/3

mem:mem/0 will be simply used to call mem:mem/3. We use this intermediate step because we will do some extensions later.

On the other hand, mem:mem/3 will provide the main functionality of the memory system:

mem() ->
    mem([], [], 0).
 
% Memory : pids of the memory objects
% Free : pids of the memory objects that have been freed
% Size : number of memory objects that are being used (==length(Memory)) 
mem(Memory, Free, Size) ->
    receive
        % request for memory allocation
	{From, alloc} ->
	    ok;
        % free the memory address
	{From, free, Addr} ->
	    ok;
        % termination of the system. It terminates all the memory objects before it
        %  terminates
	{From, exit, Reason} ->
	    lists:foreach(fun(Memobj) -> exit(Memobj, {From, Reason}) end, Memory ++ Free),
	    exit({From, Reason});
        % printing the contents of the memory for debugging
	{_From, print} ->
	    io:format("Size: ~w --~nMemory~n-------~n~p~nFree~n-----~n~p~n", [Size, Memory, Free])
    end,	
    mem(Memory, Free, Size).

Now lets design how a memory object will look like.

mem:memobj/1

This process is the one representing a memory address. It is the one that provides the read, and write operations.

% Mem is the pid of the memory system process
memobj(Mem) ->
    % initialize the memory location with 'null'
    memobj(Mem, null).
 
memobj(Mem, Val) ->
    receive
        % return the value to the requester
	{From, read} ->
	    From ! {self(), read, Val};
        % write a new value
	{_From, write, Val1} ->
	    memobj(Mem, Val1);
	_ ->
	    unkonwn
	end,
    memobj(Mem, Val).

I immediately presented the implementation and not only the interface, since it is quite trivial. The memobj is only used to keep and change it’s state (variable Val).

Implementation

In this section we will implement the unimplemented operations in the mem/3 function.

alloc – allocating memory

The operation for allocating memory consists of the following steps:

1. If the Size of the memory system is >= with the ?MAXSIZE, then the memory is full, so return null.
2. Else, if Free-list is not empty, return the head item.
3. Else, spawn a new memobj and return its pid.

	{From, alloc} ->
	    if 
		Size < ?MAXSIZE ->
		    case Free of
			[Memobj | Frees] ->
			    From ! {self(), alloc, Memobj},
			    mem([Memobj | Memory], Frees, Size + 1);
			_ ->
			    Memobj = spawn(?MODULE, memobj, [self()]),
			    From ! {self(), alloc, Memobj},
			    mem([Memobj | Memory], Free, Size + 1)
		    end;
		true ->
		    From ! {self(), alloc, null}
	    end;

free – free a memory object

Message used to free a memory address.

	{_From, free, Addr} ->
	    case lists:delete(Addr, Memory) of
	        % if after the delete the Memory is the same ->
	        %  Addr was not a part of Memory
		Memory ->
		    ok;
	        % if not -> it was, so decrease the size and add it
	        %  to the Free-list
		Memory1 ->
		    mem(Memory1, [Addr | Free], Size - 1)
	    end;

The Application Interface

The alloc, read, write, and free operations will be a part of the memif module. By registering the pid of the memory system with a name we have the possiblity to simplify the interface.

memif:alloc/0

Allocates a new memory object and returns its pid.

alloc() ->
    Mem = whereis(?MEMREGNAME),
    Mem ! {self(), alloc},
    receive
	{Mem, alloc, Addr} ->
	    Addr
    end.

But if the memory system is not initialized we get

3> memif:alloc().
** exception error: bad argument
     in function  memif:alloc/0
4> mem:start().
started
5> memif:alloc().
<0.52.0>

So we wrap it around a try-catch statement

alloc() ->
    try
	Mem = whereis(?MEMREGNAME),
	Mem ! {self(), alloc},
	receive
	    {Mem, alloc, Addr} ->
		Addr
	end
    catch
	_:_ ->
	    mem_not_initialized
    end.

memif:free/1

Frees the given memory object, making it available for re-allocation.

free(Addr) ->
    try
	?MEMREGNAME ! {self(), free, Addr},
	freed
    catch
	_:_ ->
	    mem_not_initialized
    end.

memif:read/1

Returns the value of a memory object. Notice that read/1 does not contact the memory system at all.

read(Addr) when is_pid(Addr) ->
    Addr ! {self(), read},
    receive
	{Addr, read, Val} ->
	    Val
    end;
read(_null) ->
    segmentation_fault.

memif:write/2

Writes a new value to a memory object. Notice that write/2 does not contact the memory system at all. The write operation is asynchronous (non-blocking) but it can be easily changed to be synchronous.

write(Addr, Val) when is_pid(Addr) ->
    Addr ! {self(), write, Val},
    written;
write(_null, _) ->
    segmentation_fault.

Robustness

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:

• If the memory system fails for some reason, the memory objects will also stop executing.
• By trapping the exit messages, if a memory object fails, the memory system will get notified.

We can first start by

 mem() ->
    process_flag(trap_exit, true),
    mem([], [], 0).

trapping the exits on the mem function. Doing this will change the default behavior; if a process to which mem is linked fails, mem process will not exit, but an {'EXIT', Pid, Reason} message will be added to the mem‘s message queue. This message can be normally delivered on the receive statement of mem/3 function.

	{'EXIT', Memobj, _Reason} ->
	    case lists:delete(Memobj, Memory) of
		Memory ->
		    mem(Memory, lists:delete(Memobj, Free), Size);
		Memory1 ->
		    mem(Memory1, Free, Size - 1)
	    end;

Now, the only thing remaining is to change the spawn call with a spawn_link call on the alloc message clause.

Example

With define(MAXSIZE, 10).

1> mem:start().
started
2> Mems = [memif:alloc() || I <- lists:seq(1, 12)]. 
[<0.39.0>,<0.40.0>,<0.41.0>,<0.42.0>,<0.43.0>,<0.44.0>,
 <0.45.0>,<0.46.0>,<0.47.0>,<0.48.0>,null,null]
3> [memif:read(Mem) || Mem <- Mems].               
[null,null,null,null,null,null,null,null,null,null,
 segmentation_fault,segmentation_fault]
4> lists:foreach(fun(Mem) -> memif:write(Mem, ':)
4> ') end, Mems).
ok
5> [memif:read(Mem) || Mem <- Mems].             
[':)\n',':)\n',':)\n',':)\n',':)\n',':)\n',':)\n',':)\n',
 ':)\n',':)\n',segmentation_fault,segmentation_fault]
6> lists:foreach(fun(Mem) -> memif:write(Mem, ':)') end, Mems).
ok
7> [memif:read(Mem) || Mem <- Mems].                           
[':)',':)',':)',':)',':)',':)',':)',':)',':)',':)',
 segmentation_fault,segmentation_fault]

Code

You can find the code for the example here.

Next

In the next port I will extend this example to support

• Virtual Address Space : referencing the address by an integer
• and Replication