Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

OK, so, background:

I have a little "server" app/module that is written in C++. This is kindof a tunnel application that provides a standardized API via TCP/IP[a] and on the other hand talks to the "real" server via TCP/IP[a] via it's own interface.

It doesn't even officially support multiple clients, but due to the inherently multithreaded nature of the processing that is done by the server and by the client (plus asynchronous callbacks) the tunneling app itself is multithreaded and runs pretty well during normal operations.

The application uses a number of simple mutexes (Win32 CRITICAL_SECTIONS) to lock down the code paths that would create problems when executed concurrently and this does work pretty well in practice.

A little picture:

[proprietary server]        [tunneling app]        [client]
                     <--1-                  <--1-
                              (upcalls)    |<--2-
                     <--3-                  <--3-
                                           | -2-->
                      --1->    (returns)     -1-->
                      --3->                  -3-->
                      -a-->    (callbacks)   -a1->
                      -b--> |                -a2->

So pretty much everything goes with regards to call chains.


We have now identified a number of problems in fringe cases like calls during initialization or shutdown of the server and/or tunneling app and I'm struggling to properly fix these as they are mostly related to multithreaded object and thread lifetimes and just throwing more mutexes or more locks at the problem really doesn't cut it.


As for the Question:

What I am looking for is advice and guideline on how to write multithreaded (C++) code that would work in all corner cases from the start and doesn't involve just locking everything down. Possibly with a specific focus on the context of heavy multithreading in a network communication scenario.

Any insights welcome.


Notes:

[a] : It's a CORBA communication interface. But The problems I see are really not related to the actual messaging mechanism used, as the messaging part on the wire works very well.

share|improve this question

Running multiple threads in a shared memory space and trying to figure out where to put locks does not work, as you discovered. You need to approach the problem from the opposite end: threads really should share nothing and communicate with each other via messages. See this article on Erlang-style concurrency.

share|improve this answer
    
Upvoted. Maybe I should do some re-reading on Erlang. Then again, I'm not convinced it's that simple in the average C++ context (performance/memory/design constraints). Doesn't share nothing eventually lead to copy-everything? Have you ever applied this to a C++ project? – Martin Ba Aug 4 '11 at 14:19
1  
@Martin: It is a matter of design really. For instance, if multiple threads need to access a file, one approach would be to put a lock around each piece of code that touches that file, but it is error-prone and does not scale. Another approach would be to have a specialized thread that has exclusive access to a file, runs in a loop, takes requests from a queue and puts results in another queue. All other threads would now submit requests to this specialized thread instead of competing for the lock. Of course, this is not a real-life example (there is async IO for that) but the strategy is. – Nemanja Trifunovic Aug 4 '11 at 14:28
2  
@Martin - I've done things this way in C++. The way we did it was, not to "copy state", but rather "grant state" during IPC. That is, if a second thread needed to be able to manipulate state, the current owning thread needed to give ownership of that state to the other thread for manipulation - and the old owner would then no longer be able to manipulate that state, unless it got granted back to it. – Aidan Cully Aug 4 '11 at 14:31

throwing more locks does cut it you know :) Eventually you'll be running your multithreaded app in a single-threaded mode (ie only 1 at a time) but it'll run :)

I think what you need is a mechanism for communicating the state of the app to the runnign threads. If you crash when shtting down its because some threads still expect the app to be present, even though its closing down its data. structures. In this case, you need to stop accepting new threads, but wait for the old ones to terminate. Alternatively, you need to send a messagwe to each running thread to tell it that's its time to stop whatever it was doing. Which way you choose depends on the app.

You shouldn't have any problem on initialisation - just prevent any threads from being created until you're ready for them.

share|improve this answer

Micro-Facets of Functionality

This is going to be more of a general design strategy answer, without understanding the precise issues you are dealing with in a networking context. It might completely miss. Yet understanding this was so helpful to me in just software engineering in general that I'm eager to share it, and I think it has a good chance of helping. Simplifying state/resource management and control flows tends to go hand-in-hand with simplifying multithreading, which is handy.

To me the perceived sense of overwhelming complexity of a very large-scale codebase is often owed to the fact that it's structured in a way that has us zooming in to a micro-level of teeny islands of functionality and control flows and then trying to have us reason about how it functions abroad at an overseer level. In that case, it's making us try to sum up little pieces of functionality to try to reason about the codebase, and it's hard to try to work bottom-up in this fashion and piece together what's actually going on.

This problem is multiplied when you have a central data structure, with all these little teeny micro-facets of functionality all weaving and winding and forming a maze of functionality which ultimately works their way towards calling functions which update this central data structure.

enter image description here

Such a codebase can be perfectly SOLID in its engineering. All entities might perform a singular responsibility, all dependencies flow towards abstractions, everything is easily extensible that needs to be extensible, etc.

Regardless, the conceptual complexity of the codebase seems beastly when trying to comprehend it, and trying to achieve both thread safety and thread efficiency might seem like a hopeless endeavor. It's because this twisting maze of control flow still makes it very difficult to reason about when and where critical things happen. Such systems make us have to zoom in, making us trying to understand the big picture from little puzzle pieces.

"When does this shared, central data structure get updated?"

"Well, it might be updated when this event is triggered when the user pushes this button which causes this function to get called which causes that function to get called which updates this structure. It might also get updated when this event is triggered which calls functions A->B->C->D->E....->Z which then updates this structure, etc. etc. etc."

It's hard to reason about when and how this shared state is accessed and modified, and when it's hard to reason about that, the temptation is often to lock with every little hand that touches it.

Flat, Bulk, Deferred Processing (Mass Consumer Design)

The solution to me here to both alleviate perceived complexity and also kind of flatten the whole system and make it easier to multithread efficiently with smarter locks is to design the system in a way that allows you to zoom out. Instead of this:

enter image description here

We do something like this:

enter image description here

By doing this, you centralize one single place in the entire system that can actually modify this data structure. And that one place can potentially multithread to its hearts' content, using one of the simplest means of multithreading -- the parallel for loop. Such a place then can process many requests at once, and thus lock at a more appropriately coarse/granular level. It'll also make it easier to split up the central data structure, for example, and reduce the contention that way with only the central processor to update in response.

Just about everything is easier when you avoid having a teeny little isolated pipeline for each little request that can occur, and instead have a bulk, centralized pipeline that handles multiple requests at once. Just at a meta level, reasoning about such a codebase's behavior starts to become like reasoning about a dozen continents rather than thousands of little islands.

In such a case, each micro-facet (each client, e.g.) might push or write some local state which is then read/popped/cleared by this deferred, flat, bulk processor. A general approach is have each one push to a local, concurrent queue (producer) that gets popped by the bulk processor (mass consumer), though a queue is overkill if you can just have some atomic variables you can read/write.

We have now identified a number of problems in fringe cases like calls during initialization or shutdown of the server and/or tunneling app and I'm struggling to properly fix these as they are mostly related to multithreaded object and thread lifetimes and just throwing more mutexes or more locks at the problem really doesn't cut it.

By having one centralized place which does all the heavy-lifting, it's easier to multithread but also avoid issues like these associated with attempts to update shared state once destroyed or prior to initialization. This kind of awkwardness with initialization and destruction order can also be understood and tackled from untangling state management and associated control flow. The central, mass consumer (bulk processor) would simply ignore the local state of clients (not consume and therefore not do anything with shared state) when the system is not ready (pre-startup or post-shutdown). The clients are still free to safely push/write local state, since they are not modifying any shared/central state in doing so. The centralized system will pull/process that state when it's actually ready to do so.

If this kind of asynchronous, deferred processing is applicable, it can tremendously simplify all kinds of goals ranging from correctness to simplicity to safety and efficiency. Most of all, codebases structured like this just tend to be easier to comprehend for humans at a broad level without thinking so much at a micro-facet level, the "what if?" scenarios become few in number, and life becomes a lot simpler.

If there are multiple phases involved (like a state machine), then you can have more than one centralized bulk processor. The first could push results back to each entity ("micro-facet"). The second system then consumes those results and processes the second phase in a serial fashion for order-specific, multi-phase processing.

Optimization

To avoid needlessly looping through micro-facets which don't need to do anything, one strategy is to aggregate them into blocky data structures, like so:

enter image description here

This aggregates 4 "micro-facet" entities into a each unrolled block (kind of like an unrolled linked list but without shuffling contents around to keep nodes at least half full). You can keep track of vacant spaces in the list and reclaim them upon subsequent insertions. And of course you can aggregate more than 4 of these, maybe even like 64 at once, and can even form a hierarchy (I just used 4 because it's easy to draw).

The key idea is that you can skip N (4 in this diagram) micro-facets at once to process if this Needs Processing atomic flag is not set, so it's kind of like a miniature skip list (and can be expanded to a full-blown hierarchy for maximum scalability). Any time one of these entities have work that needs to be done, they can set the Needs Processing flag in the block they reside in (and possibly upwards to the root of the hierarchy if a full-blown hierarchy is used). We can also use condition variables to put this deferred processing thread to sleep when there's nothing to do.

The bulk processor works its way downwards from these blocks that have Needs Processing set to true down to the individual entities that need to be processed within that block.

CES/ECS

This is similar to the design of entity-component systems used in games, but playing especially to the "systems" part. Systems as bulk processors can really help reason about the software, as well as multithread more efficiently when each system is doing a lot of work. Even games spanning millions of lines of code might only have a couple dozen systems which are the sole places doing the critical work, and that's really easy to digest for the human brain when there's only a couple of dozens of places in the codebase that are responsible for the most critical updates to the software's core state, instead of tens of thousands of miniature functions to think about.

enter image description here

The key is not to confine yourself into a little tiny island of functionality, and to avoid all such little teeny islands communicating directly with central data structures. Make it one big island of bulk processing that has sole access to the central data, make each little island which is responsible only for its local state, and life will become a lot easier.

The control flow will become untangled in the places where it's most critical, and likewise the temptation to lock on every little teeny request will also go away. Your call stacks will also become very shallow. Instead we have end up having big, chunky bulk work to do in a handful of centralized places, and that leaves a lot of breathing room to lock at more appropriate levels, and less frequently with less contention. Most importantly, it should have you dealing with bugs a lot less when the question of "when and where" the critical things happen, like updating central data, is no longer such a mystery that requires reaching for a magnifying glass and sifting through the entire codebase.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.