• Concurrency, Distribution, and the Go memory model

    The Go memory model specifies two main ways in channels are used for synchronization:

    1. A send onto a channel happens-before the corresponding receive from that channel completes.
    2. The $k^{th}$ receive from a channel with capacity $C$ happens-before the $(k+C)^{th}$ send onto that channel completes.

    Recall that happens-before is a mathematical relation, as discussed here.

    Rule (1) above has been around for a while. The rule is very similar to what was originally proposed by Lamport in 1978. It establishes a happens-before relation between a sender and its corresponding receiver. Rule (2) is a bit more esoteric. It was not present in Lamport’s study of distributed systems. There is a good reason for that absence.

    continue reading...
  • Channels vs Locks

    With channels, we typically establish that two things are synchronized because A happens-before B. We often know the order in which they happen. In this post, we’ll see a use (or “misuse”) of channels. We will be able to establish that two things are synchronized, but we won’t know the order between them. We won’t know which happened first. We will then relate and contrast channels with locks: how are they different, how are they similar.

    continue reading...
  • What makes Go special

    goroutine What stands out the most in Go, to me, are goroutines and channels. The language was built for the many-core. It sprung from the observation that processors are not getting much faster at doing one thing, but are becoming faster by doing many things at once. To benefit from this trend, we ought to write multithreaded applications. Go makes it super easy to have multiple threads of execution. By prepending the keyword go at invocation, any function can run asynchronously (on its own “thread”). For example, the program below has only one goroutine, the main goroutine.

    continue reading...
  • Rhubarb tang

    If you are following the blog, you have been busy learning about memory models. We started from the basics: what are memory models? What’s interesting and challenging about them? Then covered weak memory and got to the point of introducing the concept of happens-before relation. With that, we visited a real-world memory model specification, that of the Go programming language.

    Pat yourself on the back. Great job! It is time to take a refreshing break. In my welcome post, I said I would share some (drink) recipes. Here is one for the summer. I call it “rhubarb tang”.

    continue reading...
  • The Go memory model

    The Go memory model starts with the following ominous trespassing sign:

    If you must read the rest of this document to understand the behavior of your program, you are being too clever.

    Don’t be clever.

    Feeling clever? Then come on in!

    continue reading...
  • The happens-before relation

    At the end of the previous post, we saw that a compiler can change the order of instructions in a binary (as long as single-threaded semantics is preserved). These changes can break synchronization, especially if we expect to synchronize by reading and writing to variables. When pondering about synchronization, it would be unreasonable to expect a programmer to peek into the compiler. Luckily, languages come with a memory model: a document that serves as a contract between the programmer and the compiler.

    Memory models are often defined in terms of the happens-before relation.

    continue reading...
  • Weak memory models

    In the previous post, we touched on consequences of our quest for performance. We saw that, by relaxing the order of execution of instructions, compilers are able to produce faster binaries, and processors are able to execute these binaries faster. We want this rearranging to be done for us because efficient instruction scheduling is a science in itself. Also on the previous post, we touched on the concept of sequential consistency.

    In this post, we will discuss single-threaded semantics, compositionality, and their relation to weak memory models.

    continue reading...
  • An introduction to memory models

    In this series of posts we will visit the concept of memory models using “real-world” examples. We will look behind the scenes and into a programming language’s implementation. We will see how the specification of the memory model relates to the language’s implementation.

    Below we cover some basics: what is a memory model and why do these models matter. We will touch on concepts associated with multi-threading and synchronization, such as the concept of sequential consistency, weak- or relaxed-memory, atomicity, etc. In future posts, we will discuss the Golang memory model and we will look into Go runtime source code. But first, a confession.

    continue reading...
  • Starting with a fizz!

    Welcome! I want to share with you some things I’ve learned about computer science. I hope to spark conversations, meet people, and have a bit of fun along the way. I will try to strike a balance between practice and theory, rigor and accessibility. I hope you’ll enjoy.

    My first “serious” post is about memory models, but before we start, here is a drink recipe that is as much revealing about my origins as it is tasty.

    continue reading...

subscribe via RSS