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?
Permalink for 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