On Oct 4, 11:33 am, Michael Sparks <[email protected]> wrote:
> On Wednesday 30 September 2009 20:56:59 erisian wrote:
>
> > Now that I have the basic message passing and blocking policy working,
> > I'm investigating how to integrate my little lib with asynchronous
> > events in a (relatively) portable manner.
>
> Hopefully what follows here is useful. I'm summarising the sorts of
> things / thinking we followed with kamaelia.
(lots of good info on the evolution of the axon event architecture)
So, basically axon started as a primitive selector on network activity
and then became more sophisticated....
The solution to a system that lives inside cpython will, of course, be
somewhat different to one that has direct access to the metal.
There are several facets to the async / wait model.
1) The mechanism which controls the collection and demultiplexing of
async events into a (roughly) synchronous subsystem.
2) Feeding these events into the synchronous system (co-routines, axon
etc)
3) Handling truly separate threads which can sleep etc
1) If I remember correctly, demultiplexing async events into a
synchronous event system is essentially a reactor model. My idea was
that I knew I had to find a way to integrate these two systems into
one and that this problem had probably been solved 10 times by now, so
I went searching for libraries that had to perform this task for very
large numbers of events and actors.
I knew about libevent, but I also found libev which processes events
in a highly efficient manner and scales well as the number of events
and components rises. I also needed a system which could cleanly
demux async events in separate threads and synchronize between them
(which libev also does).
2) I currently working on synchronization of the libev callbacks and
feeding of those events into async component inboxes. I think it
should work without any complicated inbox locking. If not, I'll have
to devise one -- perhaps creating async outbox queues that are allowed
to deliver at some point (but I think that's unnecessary).
3) If async components need to run in completely separate threads,
libev can wake up a separate event loop. Also, the libev event loop
can be mergeed with both my baby axon and the gtk event loop.
Also...
I was thinking about your mention of O(1) instead of O(n) complexity.
Since the demo scheduler already implements a dual queue for waiting
and running processes, technically it already implements a pseudo O
(1) / constant priority round-robin algo.
But thats going to end if I ever need to implement priority (and who
doesn't).
So I would need a priority bitmap to search the list of active,
runnable run priority queues.
I assume that search would be some sort of newtonian search of a
priority bitmap. (If you have 64 priorities, then you AND with a 32-
bit 0xFFFFFFFF, in the high and then low-order words. When you get a
hit on the AND you split that into a 16-bit 0xFFFF and repeat until
you find the bit. Maybe with some sort of CPU instruction to
accelerate, like bitsearch or barrelshift.)
That should work nicely to make the priority search O(log(n)) or
effectively O(1) for small values of n.
This all maps pretty nicely into libev, if you consider that the libev
event loop is priority zero. libev splits its pre and post-event
processing into a "prepare" callback and an "idle" callback.
In prepare(), you dispatch one axon scheduling cycle (shed.call) and
then determine how many axon events are still running. If all axon
events are now waiting, you drop straight into the libev wait loop
which will block if no events are ready. If any axon procs are still
running you enable the idle callback which gives you back control
after all async events have been handled -- even if none are
available.
Then you have the ability to schedule low-priority procs (priority <
0).
In the outbox.send(), as soon as any proc goes from not-running to
running, you bump the runningProcs counter and the sheduler begins
running again.
But it's easier just to show you. :-)
Here's a little libev demo I crufted up. It simulates continuous axon
scheduling. If you press the spacebar, it flips the state of
runningProcs -- simulating all axon procs waiting/running. Any other
char quits. Also I only enable/disable the idle processor if
runningProcs transitions to or from zero so we don't waste time/
resources creating idle() every loop. (It uses termio to wait for
chars. It works under Unix. Don't know about win).
--- cut here ---
// this is public domain.
// erisian 10/05/09
#include <termios.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/ioctl.h>
#include <stdio.h>
#include <ev.h>
// every watcher type has its own typedef'd struct
// with the name ev_<type>
ev_io stdin_watcher;
ev_timer timeout_watcher;
ev_prepare prepare_watcher;
ev_idle idle_watcher;
struct ev_loop *loop;
int oldRunning = 0;
int runningProcs = 1;
int fd = 0; // stdin
static void idle_cb(EV_P_ struct ev_idle *w, int revents)
{
// come here if we are running/idleing
// schedule and run any low-priority processes (pri < 0)
printf("sched.call(low) ");
// and disable ourselves if no more runnables
if (!runningProcs) {
printf("all blocked: sleeping\n");
ev_idle_stop(EV_A_ w); // we must have just transitioned
oldRunning = runningProcs;
}
}
static void prepare_cb(EV_P_ struct ev_prepare *w, int revents)
{
// if there are runnable processes, schedule and run them
if (runningProcs) {
// schedule and run at least one fiber
printf("sched.call(hi) ");
// only enable idle processing if we just transitioned to
running
// (this prevents blocking on I/O and allows low-pri procs to
run)
if (runningProcs && !oldRunning) {
printf("unblocked: wakeup\n");
ev_idle_start(loop, &idle_watcher);
oldRunning = runningProcs;
}
}
// now we will either continue idleing (running fibers) or block for
events
}
unsigned char ctmp;
// all watcher callbacks have a similar signature
// this callback is called when data is readable on stdin
static void
stdin_cb (EV_P_ struct ev_io *w, int revents)
{
puts("waiting/idling"); fflush(stdout);
// for one-shot events, one must manually stop the watcher
// with its corresponding stop function.
read(fd, &ctmp, 1);
if (ctmp == 32) {
if (runningProcs) runningProcs = 0;
else runningProcs = 1;
}
else {
ev_io_stop(EV_A_ w);
ev_unloop(EV_A_ EVUNLOOP_ALL);
}
}
// another callback, this time for a 1 second timeout
static void
timeout_cb (EV_P_ struct ev_timer *w, int revents)
{
printf("%d: tick tock %d\n",ev_loop_count(loop),ctmp); fflush
(stdout);
}
int
main (void)
{
struct termios orig, raw;
unsigned char c;
unsigned long oldkbmode;
int ch;
/******* setup the pty for raw character mode ********/
// Get the console (keyboard) parameters and make a copy we can
modify
tcgetattr(fd, &orig);
tcgetattr(fd, &raw);
// Turn off echoing, linebuffering and special-character processing,
raw.c_lflag &=~ (ICANON | ECHO);
// Set the raw control bits and ioctl KDSKBMODE K_RAW
tcsetattr(fd, TCSANOW, &raw);
/******* setup the event loop and watchers ************/
// use the default event loop unless you have special needs
loop = ev_default_loop (0);
// register prepare watcher
ev_prepare_init(&prepare_watcher, prepare_cb);
ev_prepare_start(loop, &prepare_watcher);
// register idle watcher
ev_idle_init(&idle_watcher, idle_cb);
ev_idle_start(loop, &idle_watcher); // idle by
default
// initialise an io watcher, then start it
// this one will watch for stdin to become readable
ev_io_init (&stdin_watcher, stdin_cb, /*STDIN_FILENO*/ 0, EV_READ);
ev_io_start (loop, &stdin_watcher);
// initialise a timer watcher, then start it
ev_timer_init (&timeout_watcher, timeout_cb, 1.0, 1.0);
ev_timer_start (loop, &timeout_watcher);
puts("waiting...");
// now wait for events to arrive
ev_loop (loop, 0);
// unloop was called, so exit
/*************** restore tty to original mode ***************/
tcsetattr(fd, TCSANOW, &orig);
return 0;
}
---
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"kamaelia" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/kamaelia?hl=en
-~----------~----~----~----~------~----~------~--~---
