Concurrency in the Linux kernel can be a contentious topic. The Linux kernel mailing list features numerous discussions related to consistency models, including those of the more than 30 CPU architectures supported by the kernel and that of the kernel itself. How are Linux programs supposed to behave? Do they behave correctly on exotic hardware? A formal model can help address such questions. Better yet, an executable model allows programmers to experiment with the model to develop their intuition. Thus we offer a model written in the cat language, making it not only formal, but also executable by the herd simulator. We tested our model against hardware and refined it in consultation with maintainers. Finally, we formalised the fundamental law of the Read-Copy-Update synchronisation mechanism, and proved that one of its implementations satisfies this law.

Read-copy update (RCU) is a synchronization technique that often replaces reader-writer locking because RCU's read-side primitives are both wait-free and an order of magnitude faster than uncontended locking. Although RCU updates are relatively heavy weight, the importance of read-side performance is increasing as computing systems become more responsive to changes in their environments. RCU is heavily used in several kernel-level environments. Unfortunately, kernel-level implementations use facilities that are often unavailable to user applications. The few prior user-level RCU implementations either provided inefficient read-side primitives or restricted the application architecture. This paper fills this gap by describing efficient and flexible RCU implementations based on primitives commonly available to user-level applications. Finally, this paper compares these RCU implementations with each other and with standard locking, which enables choosing the best mechanism for a given workload. This work opens the door to widespread user-application use of RCU.

In 1962 Jan Mycielski proposed a very general notion of interpretability [M1]. This led to the question whether a given theory could be interpreted in the disjoint union of two theories, without being interpretable in any of them. He argued that in such a case it would be presumably simpler to study each of these theories separately, and hence conjectured that this situation can never occur for any of the well-known theories of mathematics. This conjecture has now been verified for the following theories (see [MPS], [P], [S1, 2]): ELO (endless, i.e., without maximal element, linear order), Th(〈ℚ, ≤〉), Th(〈ω, ≤〉) and all sequential theories (those which can code finite sequences of elements of their models). The latter include PA, ZF, GB and Th(〈ω,+,·〉). In view of these confirmations it became ever more plausible that the conjecture is valid also for RCF (real closed fields), i.e., for Th(〈ℝ,≤,+,·,0,1〉). In the present paper we show that Mycielski's conjecture is valid for a class of theories which includes RCF and OF (ordered fields). We consider only theories with equality and without function symbols. Interpretations will be meant local, multidimensional, and with parameters, as defined in [M1], [M2] and surveyed in [MPS] (for a recent definition see also [S2]). We shall write T0 ≪ T1 to say that T0 is interpretable in T1 (or that T1 interprets T0), and this will mean that for every theorem α of T0 there is an interpretation of α in T1.

Abstract We introduce a notion of complexity for interpretations, which is used to prove some new results about interpretations of sequential theories. In particular, we give a new, elementary proof of Pudlák's theorem that sequential theories are connected. We also demonstrate a counterexample to the infinitary distributive law in the lattice of chapters, in which the chapters a and bi are compact. (Counterexamples in which a is not compact have been found previously.)