How could thread safety be provided by a programming language similar to the way memory safety is provided by Java and C#?

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.