Most languages were caught unaware by the multicore revolution. C++, predictably, developed a portable assembly language for multiprocessors (C++0x atomics). Out of sheer desperation some programmers turned to Erlang. Many still try to ignore the elephant in the room, while others try to shoot it with BB guns provided by their favorite languages.

The D programming language has the unique opportunity to build multithreading model from the ground up. If you’ve been following my blog, you might have noticed that I’d been reading a lot of literature describing various systematic approaches to safe multithreading using the type system. These ware my preparations for the task of designing a threading model for D–with the help of Walter Bright (the creator of D), Andrei Alexandrescu (the lead architect of D2), and Sean Kelly (contributor to various D libraries).
Goal 1: Making concurrent programming in D safer

I propose to do this by substantially extending the type system. I realize that there is strong resistance to extending a language’s type system (and D had it’s own share of struggle when introducing deep const and immutable). The main problem is increased complexity. The programmers are reluctant to study and use complex annotation schemes. I will argue that, in the case of multithreading, the complexity argument is reversed. Shared-memory multithreading is hard! Figuring out how to avoid all the pitfalls of sharing is harder than learning a type system that prevents them.

Would you let somebody who cannot read safety instructions operate a nuclear reactor?
Goal 2: Limiting complexity

To limit the complexity of the type system, I came up with several simple principles. The most important one is that multithreaded extensions should not require modifications to single-threaded programs. That means coming up with reasonable defaults for all new annotations.

If necessary, the compiler should be able to derive some of the defaults from program analysis. Because modularity is very important in D, such analysis should not creep across module boundaries. Whole-program analysis is out of the question.
Goal 3: Keeping goals reasonable

There are two major challenges in multithreaded programming:

   1. Avoiding races
   2. Preventing deadlocks

The first problem is approachable, whereas the second one seems to be a pie in the sky. I will therefore concentrate on making D race-free.

Since D is closely related to C++ (it has pointers, unchecked casts, and the option to use manual memory management), even that goal has to be limited in scope. There is a memory-safe subset of D called SafeD, for which race freedom seems to be within reach, so this will be my starting point. (Hopefully, ne day somebody might even come up with operational semantics for SafeD and prove its race freedom.)

The system would be incomplete without some support for lock-free programming. There is a consensus that D should enforce sequential consistency. For comparison, C++ committee, after a long struggle, decided to allow non-SC primitives (weak atomics). Java only enforces SC for volatile variables.
Lessons learned

There are many commonalities in various approaches to race freedom.

    * Ownership should be built into the type system. In OO languages each object must have an owner. In C-like languages each piece of data must have an associated lock.
    * There should be efficient mechanisms for passing data between threads
          o By value
          o By reference. (The object being passed must be a monitor.)
          o As immutable data, by const reference
          o By unique reference using move semantics (hard to do in C-like languages)

Most of those ideas are expressible through type qualifiers. D already has its share of type qualifiers, such as const or immutable. There is also a proposal to introduce shared, for non-thread-local objects. Large number of qualifiers often leads to code duplication (like having two versions of vector: one shared, one thread-local).

The problem of code duplication can be solved by qualifier polymorphism–the ability to use qualifiers as template parameters.

I will discuss each issue separately and in more detail in my future posts.
Higher-level models

Explicit synchronization is hard, no doubt about it. In D, the type system is supposed to make it safe. There are however other models of concurrency that, although more restrictive, are often easier to use.

One such model is based on message passing. D’s support for message passing will be library-based. The race-free type system will make it safe and flexible. It will, for instance, support passing messages not only by value but also by reference–without sacrificing safety. In traditional type systems there is no way to express the requirement that a message passed by reference must either be a monitor itself or behave like a C++ unique_ptr (an object that leaves no aliases behind). This requirement should be expressible in D, allowing the compiler to check for its violations.

I’ve been paying a lot of attention to software transactional memory (STM). I believe that STM could be built into D–again, with the support of the type system. It seems like the hardest problem with STM is how it should interoperate with other types of multithreaded access (both locked and lock-free).

The simplest solution is to enforce full isolation–no STM object can ever be accessed outside of a transaction. It’s not clear how practical such approach is, but it definitely simplifies things to the point that STM becomes orthogonal to other types of synchronization. And that means that it will be possible to tackle it at a later time, after the race-free multithreading model is firmly established.

In the next installment, I will describe the ownership scheme that is the foundation of the race-free type system for D.

我英文不好，看不懂，可以用中文大概说下一下吗？

多核并发

只是没看到这位老兄提交过什么东西啊，还是他自己另搞了一套？

多核并发

只是没看到这位老兄提交过什么东西啊，还是他自己另搞了一套？