Linked by Hadrien Grasland on Fri 27th May 2011 11:34 UTC
General Development After having an interesting discussion with Brendan on the topic of deadlocks in threaded and asynchronous event handling systems (see the comments on this blog post), I just had something to ask to the developers on OSnews: could you live without blocking API calls? Could you work with APIs where lengthy tasks like writing to a file, sending a signal, doing network I/O, etc is done in a nonblocking fashion, with only callbacks as a mechanism to return results and notify your software when an operation is done?
Thread beginning with comment 474880
To read all comments associated with this story, please click here.
My Preference
by Brendan on Sat 28th May 2011 06:33 UTC
Brendan
Member since:
2005-11-16

Hi,

My preference is threads (with potentially large "Thread Local Storage" areas); where each thread is responsible for a specific set/s of data, where only that thread is able to modify its data; and all threads communicate via. asynchronous/non-blocking messages.

For a simplified "phone book" example; imagine you've got a list of people's names and a phone numbers. You spawn one thread per CPU, and divide the list into sub-lists - e.g. for 4 CPUs you might have one thread for "A to E", one for "F to M", one for "N to R" and one for "S to Z" (in practice you'd use hashes but I'm trying to keep it simple). If you want to find a person's phone number you ask the thread responsible for that part of the sub-list; and if you're adding a new entry you tell the thread responsible for that sub-list to do it. If you want to search the list (maybe find all people who's names end with "e") you end up doing a parallel/multi-threaded search (and then combining the results from each thread). The main idea here is to balance the majority of the load across available CPUs.

Once you've got this happening for one set of data, you could reuse the same threads for completely unrelated sets of data. For example, one thread might handle phonebook entries for "A to E", plus keep track of vehicles who's registration plate ends with the digits "0 to 3", plus handle all bookings where "bookingID % 4 == 0". The main idea here is to avoid thread switches (after the majority of the load is balanced across CPUs); so that (under heavy load) you end up with one thread per CPU going flat out (with no task switches, no blocking, no waiting to acquire locks, etc).

Because none of the data is shared (other than "read only" data) there's no locking needed (which can make it a lot simpler to use), it easily adapts itself to any number of CPUs, and it tends be "naturally good" for data locality issues (tends to be efficient for CPU caches, etc). For all these reasons, it's relatively easy to get extremely good scalability out of it.

The problem with this sort of approach is that it requires special design - it's not "procedural" and it's not "OOP". This means you can't port software to this type of system, the normal design tools most people are familiar with (e.g. UML class diagrams, flowcharts, etc) aren't well suited to describing it, and the number of programmers familiar with it are a lot less.

What makes asynchronous/non-blocking messages more complex is the restrictions and the guarantees the system makes. How much data can be sent in a single message (4 dwords, 4 KiB, 4 MiB)? Are sent messages guaranteed to be received (common example of "no" would be network failures in distributed systems)? What guarantees are there for the order messages are received (none, some)?

- Brendan

Reply Score: 2

RE: My Preference
by Alfman on Sun 29th May 2011 17:55 in reply to "My Preference"
Alfman Member since:
2011-01-28

Brendan,

"What makes asynchronous/non-blocking messages more complex is the restrictions and the guarantees the system makes. How much data can be sent in a single message (4 dwords, 4 KiB, 4 MiB)?"

Why need there be any limit at all, short of memory constraints or policy?

"Are sent messages guaranteed to be received (common example of "no" would be network failures in distributed systems)?"

Locally delivered messages can be guarantied, network messages would depend on the underlying protocols - but how is this any different between threads/async?

"What guarantees are there for the order messages are received (none, some)?"


A queued async model doesn't get out of sequence messages, so I'm not sure why your asking this question?

Reply Parent Score: 2

RE[2]: My Preference
by Brendan on Mon 30th May 2011 09:26 in reply to "RE: My Preference"
Brendan Member since:
2005-11-16

Hi,

"What makes asynchronous/non-blocking messages more complex is the restrictions and the guarantees the system makes. How much data can be sent in a single message (4 dwords, 4 KiB, 4 MiB)?"

Why need there be any limit at all, short of memory constraints or policy?


There doesn't need to be any hard limit.

In practice, if the limit is too small you end up splitting data into many messages and combining the pieces at the receiving end (and possibly pounding the daylights out of the kernel); and if the message size is too big (or unspecified/unlimited) it's hard to tasks to reserve space for receiving messages, and you risk running out of RAM (e.g. all your free RAM gets tied up in messages in queues).

There's also compatibility issues. For example, imagine a 64-bit kernel capable of running 64-bit processes and 32-bit processes. With no limit, what happens when a 64-bit process sends a 12 GiB message to a 32-bit process?

"Are sent messages guaranteed to be received (common example of "no" would be network failures in distributed systems)?"

Locally delivered messages can be guarantied, network messages would depend on the underlying protocols - but how is this any different between threads/async?


Locally delivered messages may not be guaranteed to be received. You send a message to a task, it's placed in that task's queue, then that task terminates or crashes before it gets your message from its queue.

It's using asynchronous messaging and multiple threads; so I'm not sure if that's different to whatever you think "threads/async" is... ;-)

"What guarantees are there for the order messages are received (none, some)?"

A queued async model doesn't get out of sequence messages, so I'm not sure why your asking this question?


Imagine 3 tasks. Task A sends a message to task B and then sends a message to task C. When task C receives the message from Task A, it sends a message to task B. Can task B receive the message from task C before it receives the message from task A?

In some cases the answer is "yes" - mostly when there's some sort of intermediate buffering/queuing happening before the message reaches the final task's queue (e.g. in networking layers).

- Brendan

Reply Parent Score: 2