I have a programming question to ask. It's not simple, and is not something I would expect a beginner to be able to answer. Here it is:

Suppose we have two (sort-of) threads, A and B. These aren't threads in the usual sense; instead, usually only A is executing. However, at unpredictable times, B will start executing; during this time, A will not execute until B returns. Furthermore, thread B *must* finish executing in a certain amount of time, or the entire program crashes. (In other words, consider B's task to be hard real time.) In order to do its task, B needs to use data produced by A; if B executes at a time when the data is unavailable, the entire program crashes (in other words, the data must always be available).

The problem is this: How can we get this working correctly, with B always being able to access the data produced by A, without creating race conditions or other concurrency issues?

Before anyone suggests it, something like a mutex will *not* work here. If A acquires the mutex then gets interrupted, B will block forever when trying to acquire the mutex (because A can't interrupt B), causing a deadlock, which is clearly not acceptable.

Note that what I am calling thread B could easily be a callback for an API (something like a signal handler), or it could be an interrupt service routine in kernel-level code.

Any ideas?

I am not sure I get the problem, due to the vague description, but let's see. One critical thing you need to specify is, how recent the data produced by A should be when B wants to access it.

If A is in the middle of producing the data, and B interrupts, and B needs the data being produced, and you can't just stop B to try again later due to the real-time req, you are screwed. There is no way around it.

If it is okay for B to use the previously available data produced by A, you make A store the past value at another location always, and swap it atomically with the new value when new value is computed. Since there is a clear interrupt priority where B > A, in this case you don't need any explicit process-level synchronization at all.

If you are inside the kernel, you may need to deal with CPU core-level synchronization issues, which is trivial.

Am I missing something?

I did a bit of research on the issue, and one thing that came up is the use of a circular buffer.

Basically, A stores the data in the buffer, and the start and end can be integers that can be changed atomically. (A should add data *before* incrementing the end, or else B might run when the length has increased but the data hasn't been added, leading to B getting garbage data.)

If the circular buffer fills up, A can just wait a bit until B has had a chance to run. Perhaps some sort of lock that A acquires and waits for, but B releases when it's done executing could work there. (Is there a good way to handle this case without having A spin or having to guess the amount of time it takes for B to be called?)

(By the way, the question came up when I was reading about real-time audio processing and the portaudio library; in this instance, B would be the callback, and its job would be to send data to the sound card.) One catch with this: You can't do this in standard C; an extension is needed. Also, perhaps the code needs to run on a CPU that does not provide an instruction to atomically swap two values.

Just a note, anything you can do with your CPU, you can do in standard C (whatever you mean when you say standard C). I don't understand what an "extension" means.

Also, atomic swaps are an essential part of any computational model that support multi threading. It's been there for decades, so that you can implement a mutex. Also, your solution is a different spin on this solution too. You may want to look into lockless data structures for a specific instance of a circular buffer that solves your problem. Generally, you would need some understanding of the run-times of routines for any real-time programming, so you shouldn't be guessing, you should (probabilisticaly) know.

I guess I understand what you mean by standard C. You can't enumerate directory entries in "standard C" either, you rely on OS interfaces for most tasks.

Anyway, I guess your problem is resolved :)

EDIT: Sorry for frequent edits, writing in the gym between sets :)

Sorry, last post. Forgot to add the final sentence to previous post. Queueing theory. It will allow you to know how to model and set up your circular buffer, so that B doesn't catch up to A.

Frankly, the question makes little sense to me...
You say that thread A cannot execute until thread B is done, so in other words, I see no point in having two threads. B should be a part of A.

Otherwise, if there are parts of A which can still function, you just need a global flag.

Thread B will set the flag to false at thread start and set it to true when done. At the point A needs the data, it checks the flag, if false, it "holds" periodically checking the global flag until it is true. When true, it proceeds to use the processed data.

In short, if the program bugs under certain conditions, have it check a global status flag thrown by the other thread when the data isn't ready. You don't lose much processing time setting a single bit.

If this is a problem you're actually trying to solve in practice, and not just an academic question, have you considered re-doing the whole thing in a different way. The way you describe it makes me think that surely there must be a better way of solving this, but I can't offer much without a little bit more specifics.

As I said, perhaps thread B is a signal handler or an interrupt service routine. In other words, while A and B don't execute concurrently, B can be executed at arbitrary times. The problem is that doing things a different way might not be an option, as the software library or even the hardware might be designed around something that acts like a callback or interrupt.

In the audio example I mentioned, the current version of portaudio *does* have a callback free alternative, but previous versions did not. Hence, if using an older version (or a different audio API that doesn't have that option), then we do encounter the problem of having to use a callback function.

One *could* compute the data in the callback (that is, in thread B), but that doesn't work for the problem of reading from disk. As I specified in the problem, thread B is hard real time, and reading a file from disk can take an arbitrarily long amount of time; therefore, the program could fail. (In practice, in the audio example you will hear a glitch in the audio when this happens.)

A reverse example (with B producing data for A to read) is the keyboard interrupt. At the kernel level (or if you are writing a DOS or embedded program with a custom interrupt handle), when a key is pressed, an interrupt is sent to the CPU. This would result in what I am calling thread B executing, and it needs to put the input somewhere that A can safely read it. If B fails to put the input into the buffer, then keyboard input is dropped, which is not a good thing. If B runs too slowly and the user presses too many keys, the system will lag and the keyboard buffer (assuming there is one) will fill up. (In the DOS days, when this would happen you would start to hear beeping.)

I see. Interesting.

This is not really my forte, so I don't think I'd be able to help you much here, sorry.

Be careful on multi cpu platforms, though! Every processor typically has its own interrupts. In other words, A and B *can* run simultaneously, e.g. B interrupts on cpu1 while A runs on cpu2. If you are in the user space, you wouldn't normally be exposed to this situation, but different situation if you are writing a driver or programming directly inside the kernel.

It sounds to me the solution is proper error handling (trapping). You anticipate what can go wrong and write routines to resolve it as best as possible. If one of the threads is something outside of your control, then you program contingent threads the best you can to control for potential issues.

If there is an issue with one "thread"'s state being ready, you have the other thread check before proceeding. Re-checking for the other thread to be ready as necessary.

Parallel programming is a bitch. Welcome to modern threaded programming. Why are you doing this? What is this for?

Incidentally, questions like this are best off asked on GameDev.net or another programming-heavy site like that. I doubt the majority of the people here possess the knowledge in this domain. They're primarily gamers, not game programmers. Yeah, you need a library that can access either threads or other cores like OpenMP, or Visual C++'s equivalent.

[url=http://www-public.tem-tsp.eu/~gibson/Teaching/CSC5021/L4-ParallelProgrammingC++.pdf]http://www-public.tem-tsp.eu/~gibson/Teaching/CSC5021/L4-ParallelProgrammingC++.pdf[/url]

Folks, of course you can do it. Multi-threaded programming is not a language feature, it is also not a software engineering paradigm. It has nothing to do with the language you use. OpenMP et al simply abstract away from the OS and CPU interfaces that give you access to synchronization primitives. You can do it yourselves if you wanted to. Take the Linux kernel, it doesn't even have access to libc, so no malloc, no strcat, no nothing. You are thinking about very high-level userspace programming, which is very different from the question asked.

This situation is common in all sorts of kernel programming cases, writing drivers, embedded programming, or directly programming on the bare metal. It will help to have an understanding of these areas, operating systems, and software engineering (which is not "programming").

For the record, dtgreene's circular buffer approach is an accepted, standard solution to this pattern of problems. You can find this implemented all over operating system code, e.g. look at how the Linux TCP/IP stack handles data buffers. Just an example. What I suggested with atomic assignment ops is a simplified version where the computed data fits into a single register, so dtgreene's is more general and better.

For the record 2, neither solution requires explicit synchronization between threads. The interrupt service routine in question has explicit priority over the other routine. You may only need to sync between different physical cores, but only if you are inside the kernel. Otherwise, the OS will abstract away this problem too.

Of course, but this is outside the scope of what's being asked. For the same reason people don't write their own Printf's. Practically-speaking, reinventing what already exists and functions well is not the best use of time. For learning, that's another story, but I digress.