MP safe event-driven archtecture without explicit locking

[mystran]

Since this is kinda related to the GUI thread I just started, and which already has nice amount of interesting observations from other people, and I kinda thought about this related topic today as well, I thought I'd start another thread.

Was reading a paper about this libasync_mp thingie (google if you care, I'll cover the basics anyway) which has an interesting concept:

Basically, you have a single event-driven multiplexing system, with asynchronous I/O and a callback system (with the library doing some C++ magic to provide currying of arguments to callbacks and such). That's the basis for libasync as far as I understand.

Now, the _mp version goes further by handling the events in multiple threads (one per CPU) for hardware parallelism. To prevent conflicts from concurrently run callbacks, it has a concept of coloring, with the simple rule that no two events of the same color will ever be run at the same time...

So if several events need to access the same data structures, they can be given the same color, and no locking is necessary. Further (and I'm not sure if libasync_mp actually guarantees this) if the events are kept in order, and the first event that is runnable (not blocked by another event of same color) is already scheduled next, then events of a given color will always be run in the order they were added to the queue (with respect to each other that is). So not only could one control access to shared structures, but also control the order of processing for events where that is important (say, input from the user).

The paper I read, also mentions multi-color events in passing, so I kinda started thinking: if one allows several colors per event and guarantees that no two concurrently running events share any of the colors, then allows dynamic allocation of the colors and dynamic coloring of the events, then associates different colors to different data-structures (or parts of data-structures), then one essentially ends up with all the locking in the same place (the multi-threaded event-loop), and completely avoids potential for dead-locks (in the worst case the system would degenerate into a single-threaded event-loop if no two events can run concurrently, but would not completely dead-lock).

Am I overlooking something, or does this look like a nice model? I mean, in OS kernels one typically ends up using some sort of deferred procedure call mechanism all the time anyway, so maybe it would be worth the trouble to associate the coloring (essentially locking) with the DPC queuing system, and essentially get two fish with the same bait.

[Candy]

To prevent conflicts from concurrently run callbacks, it has a concept of coloring, with the simple rule that no two events of the same color will ever be run at the same time...

This works, but is a drag on the developer and hard to get right. "What color did we use for UI events?". It abstracts the main problem to "groups of events" and allows you to place arbitrary labels on each group, you being somebody who is probably not qualified to make that distinction. You will merge events that have no correlation and separate events that should be merged.

The point behind the color is "group of correlated events". If you can group all events explicitly or implicitly you can guarantee them to be ordered in the order they were sent. This is exactly why my own implementation at the moment lacks a little bit about MP invocations - at the moment it counts on everything locking its own data structures and just plain blocking the thread it receives for execution. I wasn't directly concerned about the threads (which is a basic problem but an architectural one that is abstracted away) but more about the reliability - you need a fair mutex with queueing or the order won't be guaranteed.

The "coloring" does appear to have merit now I think about it a bit more. It appears to be isomorph to the other solutions I had in mind but it is implementable, whilst the ideas I had in memory weren't.

The paper I read, also mentions multi-color events in passing, so I kinda started thinking: if one allows several colors per event and guarantees that no two concurrently running events share any of the colors, then allows dynamic allocation of the colors and dynamic coloring of the events, then associates different colors to different data-structures (or parts of data-structures), then one essentially ends up with all the locking in the same place (the multi-threaded event-loop), and completely avoids potential for dead-locks (in the worst case the system would degenerate into a single-threaded event-loop if no two events can run concurrently, but would not completely dead-lock).

Yep.

On the other hand, that requires you to know about all data structures, their internals, what they can and cannot do, how they interact and so on. I would not like you to color my FIFO for one-at-a-time use since it's intended to do two.

I see more future in the direction of join calculus.

some sort of deferred procedure call mechanism

Nice name -> My deferred calls

[Avarok]

Ah Candy, but a queue can't be processed by two events at the same time if there's 0,1, or max items in the queue.

Computers are discrete systems, and must be considered carefully as such before one goes off gallivanting into calculus.

For example, we still have a terrible bug in the x86 platform:

Code: Select all

add EAX, EBX

That instruction is buggy if you don't check the Overflow Flag. I have yet to see a compiler that does.

[Candy]

Ah Candy, but a queue can't be processed by two events at the same time if there's 0,1, or max items in the queue.

I've already made a list of requirements:

- The function/filter is stateless (pure)
- The input contains two or more items
- The output knows how to reserialize the items in proper order (possibly by passing a sequence of input objects along).

Realizing this, you can do all steps in parallel.

Computers are discrete systems, and must be considered carefully as such before one goes off gallivanting into calculus.

Computers are a concrete version of calculus with associated limitations. The trick is that you can model infinite calculus using only limited calculus (postulate here).

For example, we still have a terrible bug in the x86 platform:

Code: Select all

add EAX, EBX

That instruction is buggy if you don't check the Overflow Flag. I have yet to see a compiler that does.

The instruction is not buggy. Pascal compilers used to do that (iirc), I strongly dislike the overflow happening (actually - it's overflow if it's signed and carry if it's unsigned) because I count on it at times. Say, TCP sequence number calculations.

Also, it's according to specifications. Bugs in specifications are called design flaws or errors.

[Avarok]

Excellent. I'm glad you're ahead of me.

[tom9876543]

Code: Select all

add EAX, EBX

That instruction is buggy if you don't check the Overflow Flag. I have yet to see a compiler that does.

Hi

Could you please provide more details, I have never heard of it before. Do you have any web links to provide references?


Thanks

[Avarok]

Yes of course, sorry Tom.

add x, y

The problem with this instruction is that the result is store in x, which is the same size as x and y. If you add two numbers, and try to store them in a number of the same size...

What happens when x + y > MAX_INT?. This is true for nearly half of the cases! Yet in 90% of the code I see, nobody checks it. Compilers certainly don't.

So when you write

x++; next time, remember to think and see if it will ever possibly go over MAX_INT. Or when x *= y;

This is a "bit overflow".

It will certainly bugger things up for ya if it "occasionally but rarely happens"

[tom9876543]

Avarok,

What you said is wrong, "add eax, ebx" is NOT buggy.

That instruction works exactly as Intel etc specifies.

You could try and claim that the COMPILER is buggy because it doesn't check for overflow.

Even then I think you are wrong. I am fairly certain C/C++ language spec explicitly says that the generated code does NOT handle overflow and its
the programmers responsibility. Same for Java.

[Avarok]

Sure.