4

I came across this question and was very impressed by this answer.

I would really like to follow the advices from that answer, but I cannot imagine how to do that. How can I avoid multi threading?

There are often situations, that need to deal with different things concurrently (different hardware resources or networking for example) but at the same time they need to access shared data (like configurations, data to work on, and so on). How could this be solved single-threaded without using any kinds of huge state-machines or event loops?

I know, that this is a huge topic, which cannot be answered as a whole on a platform like Stackoverflow. I think I really should go reading the advised book from the mentioned answer, but for now I would love to read some input here.

Maybe it is worth noting, that I am interested in solutions in C. Higher languages like Java, C++ and especially frameworks like Qt or similar ones simplify this a lot, but what about pure C?

Any input is very appreciated. Thank you all in advance

Community
  • 1
  • 1
exilit
  • 1,156
  • 11
  • 23
  • You should not try to. I was not impressed by that answer, which boils down to 'if you implement multithreading really badly, it will work really bad'. – Martin James Mar 05 '15 at 13:39

3 Answers3

3

You already mentioned event loops, but I still think those provide an excellent alternative to multi-threading for many applications, and also serve as a good base when adding multi-threading later, if warranted.

Say you have an application that needs to handle user input, data received on a socket, timer events, and signals for example:

  • One multi-threaded design would be to spawn different threads to wait on the different event sources and have them synchronize their actions on some global state as events arrive. This often leads to messy synchronization and termination logic.

  • A single-threaded design would be to have a unified event loop that receives all types of events and handles them in the same thread as they arrive. On *nix systems, this can be accomplished using e.g. select(2), poll(2), or epoll(7) (the latter Linux-specific). Recent Linux versions also provide signalfd(2), timerfd (timerfd_create(2)), and eventfd(2) for cleanly fitting additional event types into this model, and on other unices you can use various tricks involving e.g. pipe(2)s to signal events. A nice library that abstracts much of this away is libevent, which also works on other platforms.

Besides not having to deal with multi-threading right away, the event loop approach also cleanly lends itself to adding multi-threading later if needed for performance or other reason: You simply let the event handler spawn threads for certain events. Having all event handling in a single location often greatly simplifies application design.

When you do need multiple threads (or processes), it helps to have narrow and well-tested interfaces between them, using e.g. synchronized queues. An alternative design for the event handler would be to have event-generating threads push events to an event queue from which the event handler then reads and dispatches them. This cleanly separates various parts of the program.

Ulfalizer
  • 4,664
  • 1
  • 21
  • 30
  • Where would the events come from? Other threads, presumably:) 'Event loop' is merely an implementation of multithreading where mutable state data is protected from multiple access by serialising input into an event/message queue. It's surely not a bad design, (I use it often), but it is not an alternative to multithreading - it's an implementation of it. – Martin James Mar 05 '15 at 13:35
  • 1
    They could also come from the kernel, e.g. when events are tied to file descriptors, as is often the case. Maybe you could argue semantics, but I don't consider it multi-threading when there's just one thread in the process. :) – Ulfalizer Mar 05 '15 at 13:41
  • @Martin I do not agree with you. Events could come from everywhere, I think. They could also come from other parts of the event loop. – exilit Mar 05 '15 at 15:04
  • In an event loop structured around `select(2)` and pals, many events that are generated as a side effect of other events can be handled in a reasonable fashion automatically. For example, if one event causes a client process to send some kind of I-wish-to-be-terminated message to the server, the kernel will automatically inform the process when the server later closes the connection. This can remove the need for error-prone manual shutdown logic. – Ulfalizer Mar 05 '15 at 16:03
  • A timer event could be inserted at the same time too (using e.g. `timerfd` on Linux or a timer signal along with the self-pipe trick -- http://www.sitepoint.com/the-self-pipe-trick-explained/) to handle a timeout on the disconnect. There's lots of different design possibilities, but in my experience it's a good thing to at least squeeze as much of the event handling as possible into a single location (preferably a single blocking system call even). Leads to code that's simple to reason about, and that's usually efficient too to boot. – Ulfalizer Mar 05 '15 at 16:18
  • I like the approach you mentioned here. But there are two questions coming up: 1) How to deal with blocking event handlers? Or should this be avoided completely with this design (Is it even possible ...?)? 2) I understand the term "event" also as a general technique for generic communication inside the application itself (for a loose coupling between different "modules"). What do you think about the suitability of the approach you mentioned for such a generic communication model? – exilit Mar 09 '15 at 08:42
  • 1
    @exilit: Blocking (or "slow") event handlers require careful design, yeah. In some cases you can use timer events. For example, the handler for new client connections can schedule a "ping client" event (assume it's non-blocking and "fast enough" for the sake of the example) set for one minute later, with that event handler scheduling another "ping client" event, and so on. In other cases, like doing long-running calculations in the background, it's easier to spawn a thread and let it notify the event loop when it's done. – Ulfalizer Mar 09 '15 at 13:31
  • 1
    @exilit: You could easily use this approach with internally generated events/messages too. All you need is a queue of messages and some way to signal to `select/poll/epoll()` (or just use libevent) that there are new messages available (entirely single-threaded designs might not even need that). Once you detect new messages, you handle the first message from the queue (or handle all messages currently in the queue, depending on how you set things up). Try to avoid nested message loops (message loops within event handlers) as my practical experience is that they turn into a mess. – Ulfalizer Mar 09 '15 at 13:32
  • It's probably best to avoid internal messages until you feel you really need them though. If some event should cause A and B to happen, then it's cleaner to just have it do A and B rather than having A schedule B, imo. Needing to use messages in that case might be a code smell. Old large real-world programs aren't always very clean though. ;) – Ulfalizer Mar 09 '15 at 13:54
  • It seems POSIX message queues (`mq_overview(7)`) can be used with `select/poll/epoll()` on Linux by the way if you don't feel like rolling your own, though the man page warns that "this is not portable". Maybe you're not even on Linux. :) – Ulfalizer Mar 09 '15 at 17:00
  • @exilit: Did that answer your questions? – Ulfalizer Mar 12 '15 at 09:56
  • Not completely, but I think I will accept it. Thank you. – exilit Mar 13 '15 at 07:11
  • @exilit: No problem! If there's something specific you're wondering about, you could ask a new question and link it from here. Bit tricky to cover all bases for "high-level" design stuff like this. :/ – Ulfalizer Mar 13 '15 at 07:16
  • Yes you are absolutely right. It's not my intention to get a complete introduction into that topic. I even use the event driven design already but came across the limitations of such a design. Especially the 'blocking events' thing. Spinning off a different thread each time there has to be done blocking work seems not appropriate and a bit messy to me. But as you mention it is a huge topic. Maybe I really could ask a new question. But for now we can leave it at it. – exilit Mar 13 '15 at 08:19
  • @exilit: What kinds of blocking events are you dealing with in your application by the way? – Ulfalizer Mar 13 '15 at 09:12
  • There are some that come in my mind. e.g. Network IO (Which is asynchronous by design, but needs to wait for a specific response sometimes), Sometimes there is interaction with a piece of hardware (Embedded Linux device), that is restricted to timings and therefore blocks there for some time. And in other cases it's also the user interface, that may block (Timings, waiting for interaction before proceed, and so on). So it's mostly IO of any kind. Computational tasks are not a problem, I think, as the solution you mentioned some comments before is appropriate for that. – exilit Mar 13 '15 at 09:34
2

Read more about continuations and contination-passing style (and CPS transform).

CPS-transform could be a systematic way to "mimic" multi-threading.

You could have a look into CPC (Continuation Passing C, by Juliusz Chroboczek and Gabriel Kerneis), which is also a source to source C transformer. You could also read old Appel's book: Compiling with Continuations and Queinnec's book Lisp In Small Pieces

Read also more about event loops, callbacks, closures, call stacks, tail calls. These notions are related to your concerns.

See also the (nearly obsolete) setcontext(3) Linux function, and idle functions in event loops, see this.

Community
  • 1
  • 1
Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
1

You can implement concurrent tasks by using coroutines. You then have to explicitly pass control (the cpu) to another coroutine. It won't be done automatically by an interrupt after a small delay.

http://en.wikipedia.org/wiki/Coroutine

chmike
  • 20,922
  • 21
  • 83
  • 106
  • 1
    Sounds really nice but I think implementing Coroutines in C could be very messy, no? – exilit Mar 05 '15 at 11:14
  • iirc, bsnes (an SNES emulator) uses coroutines to efficiently switch between emulated components (main CPU, sound CPU, support chips, etc.). It's a nice design there to avoid having to manually save and restore all the state when switching between components. Because it needs precise control over the timing, ordinary threads wouldn't work well either. :) – Ulfalizer Mar 05 '15 at 12:55