can c/c++ do preemeptive multitasking in a single thread? [closed]

Question

Preemptive multitasking in C/C++: can a running thread be interrupted by some timer and switch between tasks?

Many VMs and other language runtimes using green-threading and such are implemented in these terms; can C/C++ apps do the same?

If so, how?

This is going to be platform dependent, so please discuss this in terms of the support particular platforms have for this; e.g. if there's some magic you can do in a SIGALRM handler on Linux to swap some kind of internal stack (perhaps using longjmp?), that'd be great!

---

I ask because I am curious.

I have been working for several years making async IO loops. When writing async IO loops I have to be very careful not to put expensive to compute computation into the loop as it will DOS the loop.

I therefore have an interest in the various ways an async IO loop can be made to recover or even fully support some kind of green threading or such approach. For example, sampling the active task and the number of loop iterations in a SIGALRM, and then if a task is detected to be blocking, move the whole of everything else to a new thread, or some cunning variation on this with the desired result.

There was some complaints about node.js in this regard recently, and elsewhere I've seen tantalizing comments about other runtimes such as Go and Haskell. But lets not go too far away from the basic question of whether you can do preemptive multitasking in a single thread in C/C++

Didst

What language do you think VMs are written in usually? – Ewers

That's what alarms do, in general. So assuming you have alarms, the question is reduced to trivial, isn't it? – Sarcoma

yes - it is possible to implement such behaviour in C/C++. What is your specific question ? What have you tried ? What doesn't work ? please show some source code... – Crudity

so can an alarm change the return stack? How? – Didst

@will, alarm can change a stack if you really want to mess around (you'll have to write that code), but what people usually do is changing a volatile variable, and checking on it once in a while, making decisions accordingly. – Sarcoma

changing the stack is problematic permission-wise... are you running as root ? – Crudity

littleadv, can you elaborate how to do pre-emptive multi-tasking? Checking variables is the definition of cooperative multi-tasking. – Didst

@Will: the thing running your VM (VirtualBox, qemu, whatever) is very likely to be coded in C or C++, or a bit of both. Your operating system kernel is also very likely to be coded in C or C++, or a bit of both. – Ewers

@Didst - if you want to write a scheduler for your threads - you'll have to actually save and restore all the registers (including process counter, by jumping to address of the next scheduled thread) and the stack, which can be done through alarms of course, but as mentioned - you'll have the issue of permissions. Why do you need to reinvent the wheel? I think you should add the actual problem you're trying to solve to your question, otherwise it should (and probably would) be closed. – Sarcoma

@Crudity imagine I'm running on win32 or iOS. If permissions is an issue on some platforms, please post an answer explaining how it can be done and what permissions are needed on that platform... – Didst

I fail to understand why people keep voting to close this; the very first version of the question was a legitimate complete free-standing question, even if people want to answer 'no, you can't'. I'm not especially bitter but I am disappointed; someone might actually know how to do it, or have meaningful ideas about spinning off the starved tasks into a fresh thread approach I outlined or other out-of-the-box thinking. – Didst

@Will: The question does seem reasonable, especially from an embedded-system perspective, where one might need a certain level of pre-emptive tasking but not want the overhead of a full-fledged pre-emptive OS. In general, I would disfavor homebrew pre-emptive multitasking solutions in favor of a combination of interrupts and cooperative multitasking. If task-switching is performed by a taskswitch() routine that's called as a normal function, one will generally only have to preserve those registers explicitly listed in the compiler documentation. If task-switching is done via interrupt... – Guth

...then one has to save and restore any register that might possibly be used anywhere. If a particular processor has some special registers or flags the compiler knows about but the author of the multi-tasker does not, one task may corrupt the registers or flags used by another, since the multi-tasker won't know to keep a separate copy for each context. In some embedded systems, the situation may be even worse, since some chips have things like multiply-accellerator units whose state cannot be adequately read out and restored. – Guth

@Guth thx for the thought. Indeed. I currently favour a watcher thread that, when discovering the io loop is stuck in the same task on the same iteration for too long, will put the io loop in a new fresh thread and leave the task some more time to finish gracefully. It will rely on signals and locks but not needing to change context or return addresses from the signal hander. Perhaps if you vote to reopen, you can add an answer? ;) – Didst

Answer 1

Windows has fibers that are user-scheduled units of execution sharing the same thread. http://msdn.microsoft.com/en-us/library/windows/desktop/ms682661%28v=vs.85%29.aspx

UPD: More information about user-scheduled context switching can be found in LuaJIT sources, it supports coroutines for different platforms, so looking at the sources can be useful even if you are not using lua at all. Here is the summary: http://coco.luajit.org/portability.html,

Monospermous

so cooperative threading - thinking coroutines - and not preemptive, but still interesting to have in the discussion; thx – Didst

Sorry, I've missed preemptive in your question, as far as I know there is no easy way to control fibers outside its hosting thread – Monospermous

Answer 2

As far as i understand you are mixing things that are usually not mixed:

• Asynchrounous Singals
  A signal is usually delivered to the program (thus in your description one thread) on the same stack that is currently running and runs the registered signal handler... in BSD unix there is an option to let the handler run on a separate so-called "signal stack".

• Threads and Stacks
  The ability to run a thread on its own stack requires the ability to allocate stack space and save and restore state information (that includes all registers...) - otherwise clean "context switch" between threads/processes etc. is impossible. Usually this is implemented in the kernel and very often using some form of assembler since that is a very low-level and very time-sensitive operation.

• Scheduler
  AFAIK every system capable of running threads has some sort of scheduler... which is basically a piece of code running with the highest privileges. Often it has subscribed to some HW signal (clock or whatever) and makes sure that no other code ever registers directly (only indirectly) to that same signal. The scheduler has thus the ability to preemt anything on that system. Main conern is usually to give the threads enough CPU cycles on the available cores to do their job. Implementation usually includes some sort of queues (often more than one), priority handling and several other stuff. Kernel-side threads usually have a higher priority than anything else.

• Modern CPUs
  On modern CPUs the implementation is rather complicated since involves dealing with several cores and even some "special threads" (i.e. hyperthreads)... since modern CPUs usually have several levels of Cache etc. it is very important to deal with these appropriately to achieve high performance.

All the above means that your thread can and most probably will be preempted by OS on a regular basis.

In C you can register signal handlers which in turn preempt your thread on the same stack... BEWARE that singal handlers are problematic if reentered... you can either put the processing into the signal handler or fill some structure (for example a queue) and have that queue content consumed by your thread...

Regarding setjmp/longjmp you need to be aware that they are prone to several problems when used with C++.

For Linux there is/was a "full preemption patch" available which allows you to tell the scheduler to run your thread(s) with even higher priority than kernel thread (disk I/O...) get!

For some references see

• http://www.kernel.org/doc/Documentation/scheduler/sched-rt-group.txt
• http://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt
• http://www.kernel.org/doc/Documentation/scheduler/
• http://www.kernel.org/doc/Documentation/rt-mutex.txt
• http://www.kernel.org/doc/Documentation/rt-mutex-design.txt
• http://www.kernel.org/doc/Documentation/IRQ.txt
• http://www.kernel.org/doc/Documentation/IRQ-affinity.txt
• http://www.kernel.org/doc/Documentation/preempt-locking.txt
• http://tldp.org/LDP/LG/issue89/vinayak2.html
• http://lxr.linux.no/#linux+v3.1/kernel/sched.c#L3566
• Can my thread help the OS decide when to context switch it out?
• https://www.osadl.org/Realtime-Preempt-Kernel.kernel-rt.0.html
• http://www.rtlinuxfree.com/
• C++: Safe to use longjmp and setjmp?
• Use of setjmp and longjmp in C when linking to C++ libraries
• http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_21.html

For seeing an acutal implementation of a scheduler etc. checkout the linux serouce code at https://kernel.org .

Since your question isn't very specific I am not sure whether this is a real answer but I suspect it has enough information to get you started.

REMARK:

I am not sure why you might want to implement something already present in the OS... if it for a higher performance on some async I/O then there are several options with maximum performance usually available on the kernel-level (i.e. write kernel-mode code)... perhaps you can clarify so that a more specific answer is possible.

Crudity

Answer 3

Userspace threading libraries are usually cooperative (e.g: GNU pth, SGI's statethreads, ...). If you want preemptiveness, you'd go to kernel-level threading.

You could probably use getcontext()/setcontext()... from a SIGALARM signal handler, but if it works, it would be messy at best. I don't see what advantage has this approach over kernel threading or event-based I/O: you get all the non-determinism of preemptiveness, and you don't have your program separated into sequential control flows.

Redd

Answer 4

As others have outlined, preemptive is likely not very easy to do.

The usual pattern for this is using co-procedures.

Coprocedures are a very nice way to express finite state machines (e.g. text parsers, communication handlers).

You can 'emulate' the syntax of co-procedures with a modicum of preprocessor macro magic.

---

Regarding optimal input/output scheduling

You could have a look at Boost Asio: The Proactor Design Pattern: Concurrency Without Threads

Asio also has a co-procedure 'emulation' model based on a single (IIRC) simple preprocessor macro, combined with some amount of cunningly designed template facilities that come things eerily close to compiler support for _stack-less co procedures.

The sample HTTP Server 4 is an example of the technique.

The author of Boost Asio (Kohlhoff) explains the mechanism and the sample on his Blog here: A potted guide to stackless coroutines

Be sure to look for the other posts in that series!

Passepartout

yes, cooperative multitasking is susceptible to getting stuck in a non-cooperative task. Hence wondering how to do preemptive task switching instead, of only say sampling the current active task and number of loop iterations in a signal handler and if the task is blocking for some time, move it off to a dedicated thread and let the OS schedule it... or something like that ;) – Didst

Answer 5

What you're asking makes no sense. What would your one thread be interrupted by? Any executing code has to be in a thread. And each thread is basically a sequential execution of code. For a thread to be interrupted, it has to be interrupted by something. You can't just jump around randomly inside your existing thread as a response to an interrupt. Then it's no longer a thread in the usual sense.

What you normally do is this:

• either you have multiple threads, and one of your threads is suspended until the alarm is triggered,
• alternatively, you have one thread, which runs in some kind of event loop, where it receives events from (among other sources) the OS. When the alarm is triggered, it sends a message to your thread's event loop. If your thread is busy doing something else, it won't immediately see this message, but once it gets back into the event loop and processing events, it'll get it, and react.

Siegbahn

Wouldn't the thread be interrupted by the operating system, like with alarms or other signals? – Mounting

signals on posix work by interrupting a thread and making it run a handler; win32 also has basic signal support, but generally only for abortive signals like terminate and such. – Didst

@Will: but signals aren't really a mechanism for multitasking, which was what you asked for. Yes, there's an OS running underneath your thread, which can, at any time, mess around with your thread, but preemptive multitasking, pretty much by definition, relies on having multiple threads running side by side (or appearing to do so) – Siegbahn

The question - before it was closed - was full of trigger words like green threads and signals. It even said that other runtimes do it. So the question, in that context, does make sense. Shame it was closed. – Didst

Answer 6

The title is an oxymoron, a thread is an independent execution path, if you have two such paths, you have more than one thread.

You can do a kind of "poor-man's" multitasking using setjmp/longjmp, but I would not recommend it and it is cooperative rather than pre-emptive.

Neither C nor C++ intrinsically support multi-threading, but there are numerous libraries for supporting it, such as native Win32 threads, pthreads (POSIX threads), boost threads, and frameworks such as Qt and WxWidgets have support for threads also.

Sodomy