Re: cooperative multitasking

classic Classic list List threaded Threaded
41 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Luiz Henrique de Figueiredo
>I am
>interested in concurrent execution of multiple scripts within a LUA state,
>cooperative 'multitasking' that is.

This is implemented in Lua 5.0w0.
Here is an example program by Roberto that finds primes. Sorry for the
comments in Portuguese.
--lhf

-- co-rotina para gerar todos os números de 2 a n
function gen (n)
  return coroutine.create(function ()
    for i=2,n do coroutine.yield(i) end
  end)
end

-- co-rotina que filtra os números gerados por 'g', tirando os múltiplos
-- de 'p'
function filter (p, g)
  return coroutine.create(function ()
    while 1 do
      local n = g()
      if n == nil then return end
      if math.mod(n, p) ~= 0 then coroutine.yield(n) end
    end
  end)
end

x = gen(1000)   -- gerador inicial
while 1 do
  local n = x()   -- pega um número
  if n == nil then break end    -- acabou?
  print(n)   -- número é primo
  x = filter(n, x)   -- tira fora seus múltiplos
end

Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Philippe Lhoste
> >I am
> >interested in concurrent execution of multiple scripts within a LUA
state,
> >cooperative 'multitasking' that is.
> 
> This is implemented in Lua 5.0w0.
> Here is an example program by Roberto that finds primes. Sorry for the
> comments in Portuguese.

It work fine on my box. I translated the comments using Google, but I still
don't understand how this work, it is black magic for me :-)
I will study carefully the upcoming manual...

-- Co-routine to generate all the numbers from 2 to n
function gen (n)
  return coroutine.create(function ()
      for i = 2, n do coroutine.yield(i) end
    end)
end

-- Co-routine that filters the numbers generated by 'g', taking off the
multiples of 'p'
function filter (p, g)
  return coroutine.create(function ()
      while 1 do
        local n = g()
        if n == nil then return end
        if math.mod(n, p) ~= 0 then coroutine.yield(n) end
        end
    end)
end

x = gen(1000) -- Initial generator
while 1 do
  local n = x() -- It catches a number
  if n == nil then break end -- Finished?
  print(n) -- The number is a prime
  x = filter(n, x) -- It takes off its multiples
end

Note:
add "print(2)" before x = gen(1000), replace the for loop in g by:
for i = 3, n, 2 do coroutine.yield(i) end
and it works too... It seems not faster though.

Regards.

-- 
--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--
Philippe Lhoste (Paris -- France)
Professional programmer and amateur artist
http://jove.prohosting.com/~philho/
--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--

GMX - Die Kommunikationsplattform im Internet.
http://www.gmx.net


Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Roberto Ierusalimschy
> It work fine on my box. I translated the comments using Google, but I still
> don't understand how this work, it is black magic for me :-)

coroutine.create(f) creates a coroutine (that part is easy ;-). From
the point of view of Lua, a coroutine is a function. When you call that
function, "f" (the coroutine "body") starts execution (as if you have
called "f" directly).

However, at any point during its execution, "f" may call
"coroutine.yield(...)". (Actually, not only "f", but any function called
by "f".)  At that point, the coroutine stops its execution, and control
goes back to the call to "f" (that is, to the caller it is as if "f"
has returned). But when the caller calls the coroutine again, it continues
its execution from the point where it has yielded. That is, "yield"
suspends the execution of the coroutine, which can be resumed later.

As a simpler example:

function f ()
  for i=1,1000 do
    coroutine.yield(i)
  end
end

c = coroutine.create(f)

print(c())         --> 1
print(c())         --> 2
print(c())         --> 3
print(c())         --> 4
  ...

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Sean Middleditch
In other words, there is no real multi-tasking in Lua.  Just this
co-routine toy stuff... What would be truly useful is for the embedding
C program to be able to launch several different Lua scripts, which task
switch among themselves, and also allow the C program to run (either
using an update callback called once per schedular run, or by returning
from the schedular and requiring the C program to call into it again).

This could be really useful where bunches of long-running incremental
tasks need to be done (updating a database, for example) or
time-gobbling tasks than require constant "progress" (multiple A*
searches).

I've seen a few patches around that supposedly pull this off.  I'm
curious why such functionality is not yet in Lua.

On Fri, 2002-06-07 at 10:48, Roberto Ierusalimschy wrote:
> > It work fine on my box. I translated the comments using Google, but I still
> > don't understand how this work, it is black magic for me :-)
> 
> coroutine.create(f) creates a coroutine (that part is easy ;-). From
> the point of view of Lua, a coroutine is a function. When you call that
> function, "f" (the coroutine "body") starts execution (as if you have
> called "f" directly).
> 
> However, at any point during its execution, "f" may call
> "coroutine.yield(...)". (Actually, not only "f", but any function called
> by "f".)  At that point, the coroutine stops its execution, and control
> goes back to the call to "f" (that is, to the caller it is as if "f"
> has returned). But when the caller calls the coroutine again, it continues
> its execution from the point where it has yielded. That is, "yield"
> suspends the execution of the coroutine, which can be resumed later.
> 
> As a simpler example:
> 
> function f ()
>   for i=1,1000 do
>     coroutine.yield(i)
>   end
> end
> 
> c = coroutine.create(f)
> 
> print(c())         --> 1
> print(c())         --> 2
> print(c())         --> 3
> print(c())         --> 4
>   ...
> 
> -- Roberto




Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

RLak
In reply to this post by Philippe Lhoste
Sean Middleditch grumped:


> In other words, there is no real multi-tasking in Lua.  Just this
> co-routine toy stuff...

It's not a toy at all! It's extremely useful and I appreciate it.
However, it may not be what you are looking for; calling it cooperative
multitasking may be a bit misleading.

This is great for writing generators, though, particularly with the
new improved for statement (Thanks, guys!)

Rici



Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Sean Middleditch
On Fri, 2002-06-07 at 11:55, [hidden email] wrote:
> 
> Sean Middleditch grumped:
> 
> 
> > In other words, there is no real multi-tasking in Lua.  Just this
> > co-routine toy stuff...
> 
> It's not a toy at all! It's extremely useful and I appreciate it.
> However, it may not be what you are looking for; calling it cooperative
> multitasking may be a bit misleading.

Yes, I meant it as a toy multi-tasker.

> 
> This is great for writing generators, though, particularly with the
> new improved for statement (Thanks, guys!)
> 
> Rici
> 
> 




Reply | Threaded
Open this post in threaded view
|

RE: cooperative multitasking

Michael Flad-2
In reply to this post by Roberto Ierusalimschy
Hi,

I like this feature very much and it shouldn't be that hard to build
a small scheduler to run tasks once per frame, once per seconds, once
per timeperiod whatever.

But now is there any way to save and restore the state of the
interpreter/the coroutines? Now that would be a really great
feature for game developers.

With kind regards,

Michael Flad

--
Fantastic Realms Interactive GmbH - Germany
Phone: +49 (0)7121 / 947 999 0
Fax:   +49 (0)7121 / 947 999 9


Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Thomas Wrensch-2
In reply to this post by Sean Middleditch
On 7 Jun 2002, Sean Middleditch wrote:

> Yes, I meant it as a toy multi-tasker.

Hmm, well you're origional request was for cooperative multitasking. I'm
going to assumey you are NOT talking about a system that uses timeslices
or some such, but rather one where the various processes give up their
turn at the processor by calling some particular routine.

If that's the case then it should be a simple matter to build a process
scheduler that turns this "toy" into a true cooperative multitasking
system.

Unless someone beats me to it I expect I'll have one done in an hour or
two.

  - Tom


Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Sean Middleditch
On Fri, 2002-06-07 at 12:30, Tom Wrensch wrote:
> On 7 Jun 2002, Sean Middleditch wrote:
> 
> > Yes, I meant it as a toy multi-tasker.
> 
> Hmm, well you're origional request was for cooperative multitasking. I'm
> going to assumey you are NOT talking about a system that uses timeslices
> or some such, but rather one where the various processes give up their
> turn at the processor by calling some particular routine.

What, did I start this thread?  (short memory span...)  ~,^

> 
> If that's the case then it should be a simple matter to build a process
> scheduler that turns this "toy" into a true cooperative multitasking
> system.

I'm not seeing how it would work - the co-routines actually only allow
one process to work at a time, and the thread has to give up it's right
to run.  Long-running threads with lots of processing would be sprinkled
with yield calls, no?

Or I suppose one could use the line-hook, although that would be quite
slow.

> 
> Unless someone beats me to it I expect I'll have one done in an hour or
> two.
> 
>   - Tom
> 




Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Philippe Lhoste
In reply to this post by Luiz Henrique de Figueiredo
> coroutine.create(f) creates a coroutine (that part is easy ;-). From
> the point of view of Lua, a coroutine is a function. When you call that
> function, "f" (the coroutine "body") starts execution (as if you have
> called "f" directly).
> 
> However, at any point during its execution, "f" may call
> "coroutine.yield(...)". (Actually, not only "f", but any function called
> by "f".)  At that point, the coroutine stops its execution, and control
> goes back to the call to "f" (that is, to the caller it is as if "f"
> has returned). But when the caller calls the coroutine again, it continues
> its execution from the point where it has yielded. That is, "yield"
> suspends the execution of the coroutine, which can be resumed later.

Amazing, not only I understood your explainations, but I think I also
understood the "primes" example. Thanks for answering so quickly and for your
cristal clear explanations, as usual.

Stop me if I say something stupid, but is seems that f is not only a
function, but also a closure. Ie. in your example, n is frozen.
So your program just divide all numbers by all numbers and output those
found prime.
Mmm, that's not so simple, x is dynamic, ouch...

OK, I will study your code more, even if I understand the bases of
co-routines now.

Thank you.

-- 
--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--
Philippe Lhoste (Paris -- France)
Professional programmer and amateur artist
http://jove.prohosting.com/~philho/
--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--

GMX - Die Kommunikationsplattform im Internet.
http://www.gmx.net


Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Roberto Ierusalimschy
> Stop me if I say something stupid, but is seems that f is not only a
> function, but also a closure.

Whenever we say "function" we may mean "closure". Now Lua has (true?)
lexical scoping.


> Mmm, that's not so simple, x is dynamic, ouch...

Each time we get a new prime, we create a new 'x', that gets its values
from the old x and filters out those divisible by 'n'.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Francis Burton
In reply to this post by Luiz Henrique de Figueiredo
At 11:53 AM 6/7/02 -0400, Sean Middleditch wrote:
>> It's not a toy at all! It's extremely useful and I appreciate it.
>> However, it may not be what you are looking for; calling it cooperative
>> multitasking may be a bit misleading.
>
>Yes, I meant it as a toy multi-tasker.

What exactly do you mean by 'toy'? Are you saying that it
has no real-life uses, or that it there are other limitations
(such as performance) which make it impossible to be used in
any real world application?

Please elaborate!

Francis


Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Luiz Henrique de Figueiredo
>Long-running threads with lots of processing would be sprinkled
>with yield calls, no?

Yes, that's why it's called cooperative multitasking.

>Or I suppose one could use the line-hook, although that would be quite
>slow.

Or the call hook.

Anyway, cooperative multitasking is provide now in the core of Lua.
If your platform allows multithreading then you can add that too. An example
is given in LuaThreads:
	http://www.tecgraf.puc-rio.br/~diego/luathreads/
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Sean Middleditch
In reply to this post by Francis Burton
On Fri, 2002-06-07 at 12:55, Francis Burton wrote:
> At 11:53 AM 6/7/02 -0400, Sean Middleditch wrote:
> >> It's not a toy at all! It's extremely useful and I appreciate it.
> >> However, it may not be what you are looking for; calling it cooperative
> >> multitasking may be a bit misleading.
> >
> >Yes, I meant it as a toy multi-tasker.
> 
> What exactly do you mean by 'toy'? Are you saying that it
> has no real-life uses, or that it there are other limitations
> (such as performance) which make it impossible to be used in
> any real world application?

I meant that it doesn't really multi-task in the way other had implied
it would - it doesn't really multi-task at all. ~,^

Something I'd be looking for, and again I don't see why it hasn't been
added to Lua proper yet, is a full "pre-emptive" multi-tasker.  One
that's implemented in the interpreter proper with all the
speed/efficiency benefits.

I recall reading that there is still a lot of information stored on the
C-stack in the Lua interpreter across function calls, which makes such
multi-tasking difficult (yet Ruby, which is based on a tree-node
approach, pulls it off - haven't looked to see what tricks they use).

This exact lack of multi-tasking is what prompted me to start Scriptix,
which has full multi-tasking (not optimized worth crap yet, but it's not
even close to as mature as Lua yet).

I certainly will have to pick my words more carefully in the future - I
wouldn't have thought referring to a lite-weight scripting language's
feature as a "toy" would be taken as a mini-flame.  Maybe it's just me,
but I consider everything short of C a toy.  ~,^  Many of them useful
toys, mind you...

> 
> Please elaborate!
> 
> Francis
> 




Reply | Threaded
Open this post in threaded view
|

Re: cooperative multitasking

Thomas Wrensch-2
In reply to this post by Thomas Wrensch-2
On Fri, 7 Jun 2002, Tom Wrensch wrote:

> On 7 Jun 2002, Sean Middleditch wrote:
> 
> > Yes, I meant it as a toy multi-tasker.
> 
> Hmm, well you're origional request was for cooperative multitasking. I'm
> going to assumey you are NOT talking about a system that uses timeslices
> or some such, but rather one where the various processes give up their
> turn at the processor by calling some particular routine.
> 
> If that's the case then it should be a simple matter to build a process
> scheduler that turns this "toy" into a true cooperative multitasking
> system.
> 

And here it is. Of course this is only for cooperative multiprocessing. So
you have to put yield calls in your code. This is pretty easy if you have
some library routines that are called all the time, just put the yield
calls in those.

Anyway, I hope this is useful to somebody.

  - Tom Wrensch


-- -------------------------------------------------
-- Simple scheduler for cooperative multitasking 
-- using Lua 5.0w0's coroutines
-- 
-- To use:
-- New tasks are scheduled using the scheduleTask
-- function:
--
--     scheduleTask(function() ...code here... end)
--
-- Inside the code of your task, you will need to 
-- call coroutine.yield() to give up the processor
-- time.
-- 
-- To start the scheduler, execute this function:
--
--     runScheduler()
--
-- This function will return once all tasks have
-- completed.
--
-- Note that you will have to add at least one task
-- before running the scheduler, or it will simply
-- return without doing anything.
-- -------------------------------------------------


tasks = {}

function scheduleTask(func)
    table.insert(tasks, coroutine.create(func))    
end

function removeTask(t)
    local i=1
    while i<=table.getn(tasks) and tasks[i]~=t do
        i=i+1
    end
    if tasks[i]==t then
        table.remove(tasks,i)
    end
end

function runScheduler()
    while table.getn(tasks) > 0 do
        for i=1,table.getn(tasks) do
            local task=tasks[i]
            if type(task)=="function" then
                if not pcall(task) then
                    removeTask(task)
                end
            end
        end
    end
end


-- --------------------------------------------------
-- A simple set of functions, each of which will
-- be used as the root of a thread.
--
-- To run the example, call runScheduler()
-- --------------------------------------------------

function task1()
  for i=1,5 do 
      print(i) 
      coroutine.yield()
  end
end

function task2()
    for i=6,12 do 
        print(i) coroutine.yield()
    end 
end

function task3() print("goodbye") end

function task4() 
    for i=1,6 do 
        print("hello")
        scheduleTask(task3)
        coroutine.yield()
    end 
end


-- Add the tasks to the scheduler
scheduleTask(task1)
scheduleTask(task2)
scheduleTask(task4)

-- Now do it
-- runScheduler()


Reply | Threaded
Open this post in threaded view
|

Suggested addition to coroutines

Thomas Wrensch-2
In reply to this post by Thomas Wrensch-2
Hello,

When I was working on the cooperative scheduler, I ran into a need to be
able to tell when a coroutine was finished executing. What I wanted was
something like this:

    if coroutine.complete(task) then
        removeTask(task)
    else
      ...
    end

What I did instead was wrap the execution in pcall, (which I would do
anyway so an error in one task/thread doesn't kill the scheduler).

  - Tom Wrensch 



Reply | Threaded
Open this post in threaded view
|

Problem with loading files

Thomas Wrensch-2
In reply to this post by Thomas Wrensch-2
Hello all,

I ran into a rather silly problem with Lua 5.0 work 0. I don't seem to be
able to load a .lua file.

In 4.1w4 I would do this:

    dofile("scheduler.lua")

Since dofile is not implemented in 5.0w0, I tried loadfile:

    loadfile("scheduler.lua")

This executes with no error, but does NOT load the file (!).

I also tried require:

    require("scheduler.lua")

And got this error message:

    stdin:1: could not load package `scheduler.lua' from path `?.lua'
    stack traceback:
       1-  [C]: in function `require'
       2-  stdin:1: in main chunk

Any idea what I'm doing wrong?

(This is on Windows 2000 Pro, compiled with VC++6.0 and also the same
error appeared when compiled with Bloodsheds Dev-C++ version 4.9.3.0)

  - Tom Wrensch


Reply | Threaded
Open this post in threaded view
|

RE: cooperative multitasking

Curt Carpenter
In reply to this post by Luiz Henrique de Figueiredo
As an platform-specific detail, let me just add that on Win32 I have had
very successful results using a fiber for each Lua thread, and switching
the fiber instead of using Lua's coroutines. The major advantage is that
switching a fiber is just a handful of machine instructions. It
basically just swaps out registers. Using Lua's coroutines requires that
you unwind the Lua call stack, wind it back up when you continue. The
only downside is that you need stack space for each thread (but you
configure that to just what you need). I have run over 1000 fibers/Lua
threads without any problems. Plus, with fibers you can switch out while
in the middle of a registered C function. Anyway, it's not a
general-purpose Lua thing, so it's not for everyone, but I thought some
people might be interested in that approach if it's a possibility for
them.

-----Original Message-----
From: Luiz Henrique de Figueiredo [[hidden email]] 
Sent: Friday, June 07, 2002 9:56 AM
To: Multiple recipients of list
Subject: Re: cooperative multitasking


>Long-running threads with lots of processing would be sprinkled with 
>yield calls, no?

Yes, that's why it's called cooperative multitasking.

>Or I suppose one could use the line-hook, although that would be quite 
>slow.

Or the call hook.

Anyway, cooperative multitasking is provide now in the core of Lua. If
your platform allows multithreading then you can add that too. An
example is given in LuaThreads:
	http://www.tecgraf.puc-rio.br/~diego/luathreads/
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: Problem with loading files

Luiz Henrique de Figueiredo
In reply to this post by Thomas Wrensch-2
>Since dofile is not implemented in 5.0w0, I tried loadfile:
>
>    loadfile("scheduler.lua")
>
>This executes with no error, but does NOT load the file (!).

Try loadfile("scheduler.lua")()
dofile was removed from 5.0w0, but will be put back, with a in different form,
as mentioned by Roberto recently.
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: Problem with loading files

Thomas Wrensch-2
Ah yes. I now recall seeing the extra () in the description you
posted. Seems to be my week for overlooking points like this.
Thank you.

  - Tom

On Fri, 7 Jun 2002, Luiz Henrique de Figueiredo wrote:

> >Since dofile is not implemented in 5.0w0, I tried loadfile:
> >
> >    loadfile("scheduler.lua")
> >
> >This executes with no error, but does NOT load the file (!).
> 
> Try loadfile("scheduler.lua")()
> dofile was removed from 5.0w0, but will be put back, with a in different form,
> as mentioned by Roberto recently.
> --lhf
> 



123