Lecture 26: Concurrency

1 Purpose

Introduce concurrency, and challenges it provides

2 Outline

Throughout the semester, thus far, all the programs we’ve written, including recent ones that involve tricky reasoning involving aliasing, have been sequential – i.e., one could model the program by walking through the program, step by step, even if in practice the number of steps makes that infeasible as an actual mental model.

Why concurrency

Since the 1960s, operating systems have allowed multiple programs to run "at the same time" – i.e., to allow limited resources (processor, memory, devices) to be shared among multiple different programs. Historically, most programs would still act as though they were the only program running on the computer, and the operating system would be responsible for switching between which program was running at a given time.

Up until maybe 20 years ago, this basic model was still relatively common for desktop applications: while the desktop metaphor provided the illusion of multiple programs running "at once", desktop hardware still largely, at that point, involved a single processor which could run a single thing at a time, which meant that the operating system (a highly concurrent program!) was responsible for switching between different programs, likely partly due to use input.

But a few things started to happen. First, with the growth of the web (starting in the 90s, but really taking off in the 2000s), a more significant portion of programs were running on servers, presenting web interfaces via web browsers.

This is very normal now (indeed, even many applications that purport to not be web applications, these days, are often browser shells), but a consequence of this was that the bulk of the program was now running on a server, or, for any significant program, servers.

This meant that logically, if not for the first time than in a more significant way, programs involved multiple things running at the same time, likely involving some amount of coordination. i.e., rather than having a program that can at least pretend to be running on its own, now your program is running at the same time on multiple pieces of hardware.

Of course, there was no reason why a single physical server couldn’t also handle having multiple versions of the program running at the same time, whether because it had multiple physical processors or via the same kind of scheduling that has been done by operating system for decades.

Second, there was another, more momentous, phenomenon that was starting to happen. An observation by Gordon Moore, one of the founders of Intel, was that that the number of transistors in a chip would double every year or two years (this is "Moore’s Law"). Now, for a long time, what that meant is that processing speed would increase correspondingly. However, for various reasons (heat, physics), that started to not hold around a decade ago; while Moore’s law is still, sort of, holding, single processor speed is not anymore. There are also many people who think it has/will end entirely.

What does this mean? Well, one obvious consequence is that the idea that you can write programs that assume there is one fast processor is no longer a useful assumption: to have a program go faster, it needs to use many processors. That means that not only backend web applications, which have operated in this mode for a while, but all applications essentially need to be written in a concurrent manner if they are to use hardware to its fullest.

Modern concurrency

To some extent, this should not be surprising, at least to those of you who have written programs outside of classes! While most programs feature local segments of sequential code, they are organized at a coarser level concurrently – i.e., there are multiple logical sequences of operations that are happening "at the same time".

The caveats in the previous sentence exist because depending on the language, or system, there may or may not actually be multiple things happening at once (certainly, the hardware supports it, operating systems support it, and some programs will!), but in either case, there are multiple threads of execution (or processes) that run in complex interleavings that, as a programmer, you have only limited ability to control.

One important reason for writing programs this way is that it allows the operating system to take advantage of the hardware available. It might be that your program is running at the same time as many other programs, and all of your processes actually end up running on a single physical processor, interleaved according to whatever decisions the scheduler makes. But the same program, running later, might run across a dozen different physical processors, and might see a massive speedup. The logical structure of the program as concurrent processes that are interleaved and might happen at the same time allows for this (important) difference.

Contrast that with writing a single threaded version of the same program. In the first situation, the performance would be the same (or slightly better, as there would be no overhead from interleaving), but when given full access to the hardware, the program would run no faster, as the other 11 physical processors would sit idle.

This is why we talk about concurrency, which is the model of programming, rather than parallelism, which is what happens (sometimes) when multiple things happen at the same time.

Models of concurrency

There are many models for this, and different languages and libraries provide their own mechanisms: operating system threads, "green" threads, callbacks, async/await, actors, etc.

In order to study this, and how to reason about it, we have a single, simple, mechanism in LSL that provides message-passing between independent processes.

Message-passing is a style of concurrency where processes (or actors) communicate by sending messages (which are any data) addressed to other processes, and each process then reacts to messages received.

Example: Erlang

A language that has explicit support for message-passing concurrency (and actors) is Erlang. Erlang was created in 1986, initially in order to make it easier to construct telephone exchanges, which both involve highly parallel operations (handling many different phone connections) and also extremely low tolerance for failure (on a trial of one of the switches developed with Erlang, the recorded uptime was 99.9999999%). Phone switches, which handle exchange of landline calls, have historically been extremely reliable (barring the wires being physically cut), and as the hardware that controlled them became more software controlled, the engineers involved were very concerned about reliability (much more concerned than most software engineers!).

One particularly impressive more modern result for Erlang, and the model of computation that it supports, is WhatsApp.

Originally entirely written in Erlang, at the point that it was acquired by Facebook, WhatsApp had 450 million users with only 32 engineers, a ratio that is still essentially unheard of.

Message Passing Concurrency in LSL

So how does message passing work in LSL?

Here is a small example, which also demonstrates the main components: process, which defines a process, and start, which takes a "scheduler" (here the first function) to decide how to choose the next process to run and a list of processes to run. In our (very simplified model), all processes must be created at the beginning, so there is no mechanism for either spawning or terminating processes.

(: start-handler (-> (List String) (Action Natural)))

(define (start-handler others)   (action 0 (list (send-packet "self" 1))))

(: receive-handler (-> Natural (ReceivePacket Natural) (Action Natural)))

(define (receive-handler state pkt)   (cond     [(> state 10)      (action state (list))]     [else      (let ([state* (+ state (receive-packet-msg pkt))])        (action state* (list (send-packet "self" 1))))]))

(second (first (start first                                (list                                 (process                                  (name "self")                                  (on-start start-handler)                                  (on-receive receive-handler))))))

11

What is scheduling? Well, unless you are running processes on physically distinct processors, and only running enough to put each on its own physical processor, there has to be some decision of when to run processes. This is called a scheduler, and there are sometimes relatively sophisticated ways of doing this. In our case, each task to run is a call to the on-receive handler with a given packet, and the scheduler is a function that, given a list of such available jobs, decides which to run.

In the above example, we only had one thread, which was sending messages to itself, so the decision of how to schedule it was not very interesting: there would only ever be one process to choose among, and thus our scheduler just always chose the first.

But by even just adding one other process, we can start making decisions. Do we choose them randomly? Do we use state to alternate, picking one and then the other?

Walking through the rest of the example, to create a process, we need to pass it three clauses, similar to how Big Bang worked in Fundies 1.

The first, name, gives a name to the process, which is a string. This needs to be unique, so if you are going to create a family of processes for a particular task, make a function that takes the name and returns the process.

The next, on-start, is a function that takes a list of names of all the other processes (all strings), and returns an action. An action has two fields: the new state of the process (here, just a natural number 0), and a list of packets to send. These are the initial messages that start the concurrent process. In the above, there is only one. It is addressed to itself (which is fine), and the data that is passed in the message is the number 1.

The second clause, on-receive, is how the process handles messages that are sent to it. This function is called for every message that is sent to this process. It is called with the current version of the processes state and the packet. The packet, which is a receive-packet, has two fields: msg and from, which is the id of the process that sent it. In this case, what we do is construct a new version of the state by adding whatever value is included (the msg field) to the state. In this program, we don’t care who sent the message, since we know it was the same process! Like on-start, the on-receive handler returns an action, and in this case, we do essentially the same thing: send a message to ourself with the number 1. Once the the state reaches 10, we stop sending messages.

Once all messages have been handled, the final states of all processes are returned: this is a list of tuples: names of the processes paired with their final states.

To get more visibility into what is happening, you can run with start-debug instead of start. This will print all packets that are being sent, and show the state of each process after it it handles a packet.

Exercise: extend the above to create a program that has two processes. They should send messages to each other, counting how many messages have been sent, and stop once one has received 10 messages.

(define (other-p nm)   (if (string=? nm "a") "b" "a"))

(define (p nm)   (process    (name nm)    (on-start     (λ (others)       (action 0 (list (send-packet (other-p nm) 1)))))    (on-receive     (λ (state pkt)       (cond         [(> state 10)          (action state (list))]         [else          (let ([state* (+ state (receive-packet-msg pkt))])            (action state* (list (send-packet (other-p nm) 1))))])))))

(start-debug first (list (p "a") (p "b")))

;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 1) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 1) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 2) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 2) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 3) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 3) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 4) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 4) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 5) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 5) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 6) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 6) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 7) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 7) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 8) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 8) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 9) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 9) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 10) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 10) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 11) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 11) ;;;; (packet #:from "a" #:to "b" #:msg 1) ;;;; (state #:process "b" #:value 11) ;;;; (packet #:from "b" #:to "a" #:msg 1) ;;;; (state #:process "a" #:value 11)

'(("b" 11) ("a" 11))