Catalina and Multi-Processing Lua on the Propeller 2
RossH
Posts: 5,477
I thought I'd start a new thread for this topic in the Propeller 2 area, because while bog-standard Lua runs on the P1 as well as the P2, the multi-processing extensions currently do not run on the P1 - and while I have learned to "never say never when it comes to the Propeller", I don't think there is much hope they will do so anytime soon.
The multi-processor extensions are based on "luaproc" - a multi-threading library designed by the designers of Lua itself, and extended by me to add multi-processor support. These extensions are described in the document Lua on the Propeller 2 with Catalina but they are neither P2 nor Catalina specific. They use Posix threads, so will run on any platform that has a pthreads library - which includes just about any platform with a C compiler.
However, there are no full-blown complete working examples in that document - it just provides a tutorial introduction to the various individual features. So I thought I'd add one here. The program below is quite a sophisticated implementation of the classic Dining Philosopher's problem, including deadlock detection, implemented in Multi-Processing Lua:
--[[
****************************************************************************
* *
* Dining Philosophers *
* *
* This program simulates the "Dining Philosophers" dilemma in Lua. *
* It uses a thread to represent each philosopher, and a condition variable *
* to represent each fork. *
* *
* This program must be executed with a multi-processing version of Lua - *
* i.e. either mlua or mluax. See the document "Lua on the Propeller 2 with *
* Catalina" for more details on Catalina's Multi-processing extensions to *
* Lua. *
* *
* The program will run under Windows, Linux or on the Propeller. You can *
* have up to 16 philosophers when executed under Windows or Linux, but on *
* the Propeller with mlua you can have only about 7, and with mluax about *
* 10 before running out of Hub RAM. On the Propeller you can request the *
* program to use up to 8 processors. On Windows and Linux you can only *
* use 1. . *
* *
* Note that this program does not SOLVE the dilemma - it just demonstrates *
* it. Although a big hint to a possible solution is given in the deadlock *
* detection code! *
* *
* To execute the program using mluax do: *
* *
* luac -o diners.lux diners.lua *
* mluax diners.lux *
* *
* For more details on this classic problem in concurrency, see: *
* *
* http://en.wikipedia.org/wiki/Dining_philosophers_problem *
* *
****************************************************************************
--]]
-- make sure we are being executed with mlua
-- (or mluax) and not just plain lua (or luax):
if not threads then
print("threads not supported - use mlua or mluax");
print("(see 'Lua on the Propeller 2 with Catalina')");
if propeller then
propeller.msleep(100);
end
os.exit();
end
t = require 'threads';
t.print("\nThe Dining Philosophers\n");
t.stacksize(2200);
-- define up to 16 philosophers:
Philosopher = {
{name = "Aristotle" };
{name = "Kant" },
{name = "Spinoza" },
{name = "Marx" },
{name = "Russell" },
{name = "Aquinas" },
{name = "Bacon" },
{name = "Hume" },
{name = "Descarte" },
{name = "Plato" },
{name = "Hegel" },
{name = "de Beauvoir" },
{name = "Sartre" },
{name = "Wittgenstein" },
{name = "Schopenhauer" },
{name = "Rousseau" },
};
io.write("How many Philosophers do you want (1 to 16)? ");
num = io.read("n", "l");
io.write("How many Cogitoriums do you want (1 to 8)? ");
cogs = io.read("n", "l");
-- check and adjust the number of philosophers and cogs:
if num < 1 or num > #Philosopher then
num = #Philosopher;
end
if cogs < 1 then
cogs = 1;
end
-- to make the workers execute on multiple processors
-- we need multiple factories - asking for 8 means we
-- will use all the available cogs on the Propeller.
-- On Windows or Linux we can only ever use 1:
t.factories(cogs);
print("Using " .. t.factories() .. " Cogitoriums!\n");
-- philosophers are implemented as threads, so we need
-- at least as many workers as threads if we want them
-- to execute concurrently:
t.workers(num);
-- return the name of fork i:
function fork(i)
return "fork ".. tostring(i);
end
-- allocate forks to philosophers:
for i = 1, num do
Philosopher[i].left = fork(i);
Philosopher[i].right = fork(i+1);
end
Philosopher[num].right = fork(1);
-- forks are implemented as condition variables:
for i = 1, num do
t.condition(fork(i));
end
-- the dinner bell is implemented as a shared global:
t.update("Dinner_Bell", nil);
-- generate a function that represents a philosopher dining:
function Diner(i)
local name = Philosopher[i].name;
local left = Philosopher[i].left;
local right = Philosopher[i].right;
return function()
local t = require 'threads';
-- Pick_Up - pick up a fork (lock the condition)
function Pick_Up(fork)
t.lock(fork);
t.print(name .. " has picked up " .. fork);
end
-- Put_Down - put down a fork (unlock the condition)
function Put_Down(fork)
t.print(name .. " has put down " .. fork);
t.unlock(fork);
end
-- Think - do some thinking
function Think()
t.print(name .. " is thinking");
end
-- Eat - do some eating
function Eat()
t.print(name .. " is eating");
end
-- wait till dinner is served
repeat until t.shared("Dinner_Bell")
-- think ... and eat ...
while true do
Think();
Pick_Up(left);
Pick_Up(right);
Eat();
Put_Down(left);
Put_Down(right);
end
end
end
-- create the diners:
for i = 1, num do
t.print("Introducing " .. Philosopher[i].name);
t.new(Diner(i));
-- memory is tight on the Propeller, so do some
-- housekeeping after creating each diner:
collectgarbage();
mem = propeller.sbrk(true);
if mem > 490000 then
t.print("Too many Philosophers!\n");
t.msleep(100);
os.exit(1);
end
end
-- serve dinner:
t.print("\nPress ENTER to begin ...");
io.read();
Dinner_Bell = true;
t.export("Dinner_Bell");
-- test for a potential deadlock every few seconds by
-- trying to pick up the forks - while we can pick up
-- any of the forks, we do NOT have a deadlock:
while true do
t.sleep(2);
free_fork = false;
for i = 1, num do
if t.trylock(fork(i)) then
free_fork = true;
t.unlock(fork(i));
break;
end
end
if not free_fork then
-- it is possible all the forks were just
-- in use when we happened to try them,
-- but report this condition - if it is
-- not a real deadlock, the dinner will
-- continue automatically:
t.print("\nDEADLOCK?\n");
end;
end
As the program says - a big hint to at least one possible solution to the dilemma is fairly clear from the program itself - but there are other possibilities.
The main problem with Lua on the P2 at the moment is that it is quite memory hungry, which limits its application. It is also a bit slow, but that's less of an issue in a scripting language, which is what Lua was designed to be. Lua is not intended to replace C - it extends C by adding scripting capabilities. Raw speed is less of an issue when you can just drop in to C when needed, or else just throw multiple cogs at the problem.
My goal is to reduce Lua's Hub RAM footprint, and possibly extend the multi-processing capabilities to allow them to be run from external RAM (currently a multi-processing program has to run entirely from Hub RAM, the same limitation that C has). A possible compromise would be to add a multi-model option (again, the same as C) where parts of the program run in Hub RAM if they need speed or multiple cogs, while the bulk of the program runs single-threaded from XMM RAM.
I won't be happy until Lua becomes as natural a language to use on the P2 as Spin or C, with all the bells and whistles those languages provide. That should keep me busy for a while! 
Comments
@RossH
Pretty darned exciting, I would say
I had no idea
Craig
Yes, Lua is highly addictive. It has become my favorite language after C. I note from your link:
The source contains around 30000 lines of C. Under 64-bit Linux, the Lua interpreter built with all standard Lua libraries takes 282K and the Lua library takes 470K.Whn compiled in COMPACT mode on the Propeller, the Lua Interpeter with all standard libraries takes about 220k. Adding in the multi-processing library brings that up to about 250k, and it is this that I want to try and reduce.
My current thinking is that using Posix threads offers a very portable implementation of the multi-processing library, but it is also an expensive one. But in Catalina the Posix threads library is implemented using Catalina's native threads so I can rewrite the Lua library to use them directly - that will make it functionally identical but smaller and faster.
Ross.