10

Java and C# provide memory safety by checking array bounds and pointer dereferences.

What mechanisms could be implemented into a programming language to prevent the possibility of race conditions and deadlocks?

  • 3
    You might be interested in what Rust does: Fearless Concurrency with Rust – Vincent Savard Jan 25 at 16:37
  • 2
    Make everything immutable, or make everything async with safe channels. You might also be interested in Go and Erlang. – Theraot Jan 25 at 16:39
  • @Theraot "make everything async with safe channels" - wish you could elaborate on that. – mrpyo Jan 25 at 16:44
  • 2
    @mrpyo you would not expose processes or threads, every call is a promise, everything runs concurrently (with the runtime scheduling their execution, and creating/pooling system threads behind the scenes as needed), and the logic that protects state is in the mechanisms that passes information around... the runtime can automatically serialize by scheduling, and there would be an standard library with thread-safe solution for more nuance behaviors, in particular producer/consumer and aggregations are needed. – Theraot Jan 25 at 16:54
  • 2
    By the way, there is another possible approach: transactional memory. – Theraot Jan 25 at 16:54
14

Races occur when you have simultaneous aliasing of an object and, at least, one of the aliases is mutating.

So, to prevent races, you need to make one or more of these conditions untrue.

Various approaches tackle various aspects. Functional programming stresses immutability which removes the mutability. Locking/atomics remove the simultaneity. Affine types remove the aliasing (Rust removes mutable aliasing). Actor models usually remove aliasing.

You can restrict the objects that can be aliased so that it's easier to ensure that the above conditions are avoided. That's where channels and/or message passing styles come in. You can't alias arbitrary memory, just the end of a channel or queue which is arranged to be race free. Usually by avoiding simultaneity i.e. locks or atomics.

The downside of these various mechanisms is that they restrict the programs that you can write. The more blunt the restriction, the fewer the programs. So no aliasing or no mutability work, and are easy to reason about, but are very limiting.

That's why Rust is causing such a stir. It's an engineering language (as against academic one) that supports aliasing and mutability but has the compiler check that they do not occur simultaneously. Although not the ideal, it does allow a larger class of programs to be written safely than a lot of its predecessors.

11

Java and C# provide memory safety by checking array bounds and pointer dereferences.

It's important to first think about how C# and Java do this. They do so by converting what is undefined behaviour in C or C++ into defined behaviour: crash the program. Null dereferences and array index exceptions should never be caught in a correct C# or Java program; they should not happen in the first place because the program should not have that bug.

But that is I think not what you mean by your question! We could quite easily write a "deadlock safe" runtime that periodically checks to see if there are n threads mutually waiting on each other and terminate the program if that happens, but I do not think that would satisfy you.

What mechanisms could be implemented into a programming language to prevent the possibility of race conditions and deadlocks?

The next problem we face with your question is that "race conditions", unlike deadlocks, are difficult to detect. Remember, what we're after in thread safety is not eliminating races. What we're after is making the program correct no matter who wins the race! The problem with race conditions is not that two threads are running in an undefined order and we do not know who is going to finish first. The problem with race conditions is that developers forget that some orders of threads finishing are possible and fail to account for that possibility.

So your question basically boils down to "is there a way that a programming language can ensure that my program is correct?" and the answer to that question is, in practice, no.

Thus far I've only criticized your question. Let me try to switch gears here and address the spirit of your question. Are there choices that language designers could make that would mitigate the horrible situation we're in with multithreading?

The situation really is horrible! Getting multithreaded code correct, particularly on weak memory model architectures, is very, very difficult. It's instructive to think about why it is difficult:

  • Multiple threads of control in one process are hard to reason about. One thread is hard enough!
  • Abstractions become extremely leaky in a multithreaded world. In the single threaded world we are guaranteed that programs behave as though they are run in order, even if they are not actually run in order. In the multithreaded world, that's no longer the case; optimizations that would be invisible on a single thread become visible, and now the developer needs to understand those possible optimizations.
  • But it gets worse. The C# specification says that an implementation is NOT required to have a consistent order of reads and writes that can be agreed upon by all threads. The notion that there are "races" at all, and that there is a clear winner, is actually not true! Consider a situation where there are two writes and two reads to some variables on many threads. In a sensible world we might think "well, we can't know who is going to win the races, but at least there will be a race and someone will win". We are not in that sensible world. C# allows multiple threads to disagree about the ordering in which reads and writes happen; there is not necessarily a consistent world that everyone is observing.

So there's an obvious way that language designers can make things better. Abandon the performance wins of modern processors. Make all programs, even multi-threaded ones, have an extremely strong memory model. This will make multithreaded programs many, many times slower, which works directly against the reason for having multithreaded programs in the first place: for improved performance.

Even leaving aside the memory model, there are other reasons why multithreading is hard:

  • Preventing deadlocks requires whole-program analysis; you need to know the global order in which locks can be taken out, and enforce that order across the entire program, even if the program is composed of components written at different times by different organizations.
  • The primary tool we give you to tame multithreading is the lock, but locks cannot be composed.

That last point bears further explanation. By "composable" I mean the following:

Suppose we wish to compute an int given a double. We write a correct implementation of the computation:

int F(double x) { correct implementation here }

Suppose we wish to compute a string given an int:

string G(int y) { correct implementation here }

Now if we want to compute a string given a double:

double d = whatever;
string r = G(F(d));

G and F may be composed into a correct solution to the more complex problem.

But locks do not have this property because of deadlocks. A correct method M1 that takes locks in order L1, L2, and a correct method M2 that takes locks in order L2, L1, cannot both be used in the same program without creating an incorrect program. Locks make it so that you cannot say "every individual method is correct, so the whole thing is correct".

So, what can we do, as language designers?

First, don't go there. Multiple threads of control in one program is a bad idea, and sharing memory across threads is a bad idea, so don't put it into the language or runtime in the first place.

This apparently is a non-starter.

Let's turn our attention then to the more fundamental question: why do we have multiple threads in the first place? There are two main reasons, and they are conflated into the same thing frequently, though they are very different. They are conflated because they are both about managing latency.

  • We create threads, wrongly, to manage IO latency. Need to write a big file, access a remote database, whatever, create a worker thread rather than locking up your UI thread.

Bad idea. Instead, use single threaded asynchrony via coroutines. C# does this beautifully. Java, not so well. But this is the main way that the current crop of language designers are helping to solve the threading problem. The await operator in C# (inspired by F# asynchronous workflows and other prior art) is being incorporated into more and more languages.

  • We create threads, properly, to saturate idle CPUs with computationally heavy work. Basically, we're using threads as lightweight processes.

Language designers can help by creating language features that work well with parallelism. Think about how LINQ gets extended so naturally to PLINQ, for instance. If you are a sensible person and you limit your TPL operations to CPU-bound operations that are highly parallel and do not share memory, you can get big wins here.

What else can we do?

  • Make the compiler detect the most boneheaded mistakes and turn them into warnings or errors.

C# doesn't allow you to await in a lock, because that's a recipe for deadlocks. C# doesn't allow you to lock on a value type because that's always the wrong thing to do; you lock on the box, not the value. C# warns you if you alias a volatile, because the alias does not impose acquire/release semantics. There are lots more ways that the compiler could detect common problems and prevent them.

  • Design "pit of quality" features, where the most natural way to do it is also the most correct way.

C# and Java made a huge design error by allowing you to use any reference object as a monitor. That encourages all sorts of bad practices that make it harder to track down deadlocks and harder to prevent them statically. And it wastes bytes in every object header. Monitors should be required to be derived from a monitor class.

  • A huge amount of Microsoft Research time and effort went into an attempt to add software transactional memory to a C#-like language, and they never got it performing well enough to incorporate it into the main language.

STM is a beautiful idea, and I've played around with toy implementations in Haskell; it allows you to much more elegantly compose correct solutions out of correct parts than lock-based solutions do. However, I do not know enough about the details to say why it could not be made to work at scale; ask Joe Duffy next time you see him.

  • Another answer already mentioned immutability. If you have immutability combined with efficient coroutines then you can build features like actor model directly into your language; think Erlang, for example.

There's been a lot of research into process calculus based languages and I do not understand that space very well; try reading a few papers on it yourself and see if you get any insights.

  • Make it easy for third parties to write good analyzers

After I worked at Microsoft on Roslyn I worked at Coverity, and one of the things I did was get the analyzer front end using Roslyn. By having an accurate lexical, syntactic and semantic analysis provided by Microsoft, we could then concentrate on the hard work of writing detectors that found common multithreading problems.

  • Raise the level of abstraction

A fundamental reason why we have races and deadlocks and all that stuff is because we're writing programs that say what to do, and it turns out we are all crap at writing imperative programs; the computer does what you tell it, and we tell it to do the wrong things. Many modern programming languages are more and more about declarative programming: say what outcomes you want, and let the compiler figure out the efficient, safe, correct way to achieve that outcome. Again, think of LINQ; we want you to say from c in customers select c.FirstName, which expresses an intent. Let the compiler figure out how to write the code.

  • Use computers to solve computer problems.

Machine learning algorithms are way better at some tasks than hand-coded algorithms, though of course there are many tradeoffs including correctness, time taken to train, biases introduced by bad training, and so on. But it is probable that a great many tasks that we currently code "by hand" will soon be amenable to machine-generated solutions. If humans are not writing the code, they're not writing bugs.

Sorry that was a bit rambling there; this is a huge and difficult topic and no clear consensus has emerged in the PL community in the 20 years I've been following progress in this problem space.

  • "So your question basically boils down to "is there a way that a programming language can ensure that my program is correct?" and the answer to that question is, in practice, no." - actually, it's quite possible - it's called formal verification, and while inconvenient, I'm pretty sure it is routinely done on critical software, so I wouldn't call it impractical. But you being a language designer probably know this... – mrpyo Jan 26 at 0:32
  • 6
    @mrpyo: I am well aware. There are many problems. First: I once attended a formal verification conference where an MSFT research team presented an exciting new result: they were able to extend their technique to verify multithreaded programs of up to twenty lines in length and have the verifier run in less than a week. This was an interesting presentation, but of no use to me; I had a 20 million line program to analyze. – Eric Lippert Jan 26 at 0:35
  • @mrpyo: Second, as I mentioned, a big problem with locks is that a program made of thread safe methods is not necessarily a thread safe program. Formally verifying individual methods doesn't necessarily help, and whole program analysis is hard for non-trivial programs. – Eric Lippert Jan 26 at 0:36
  • 6
    @mrpyo: Third, the big problem with formal analysis is that what, fundamentally are we doing? We are presenting a specification of preconditions and postconditions and then verifying that the program meets that specification. Great; in theory that is totally doable. What language is the specification written in? If there is an unambiguous, verifiable specification language then let's just write all our programs in that language, and compile that. Why don't we do this? Because it turns out that it's really hard to write correct programs in the spec language too! – Eric Lippert Jan 26 at 0:38
  • 2
    Analyzing an application for correctness using pre-conditions/post-conditions is possible (e.g., using Coding Contracts). However, such analysis is only feasible on condition that the conditions are composable, which locks are not. I'll also note that writing a program in a way that allows for analysis requires careful discipline. For example, applications which fail to strictly adhere to the Liskov Substitution Principle tend to resist analysis. – Brian Jan 28 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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