Threads without Locks

Russ Cox

http://swtch.com/~rsc/talks/

Second International Plan 9 Workshop

December 2007

Introduction

Two popular camps for designing concurrent programs.

Should we use threads or events?

Bell Labs approach: threads and events.

Threads vs. Events

Drawbacks of threads (Ousterhout):

Drawbacks of events (Ousterhout):

Actually drawbacks of locks and top-level select loops!

The “Plan 9” Way: Threads and Events

Model:

Benefits:

Talk content

At the end, I hope you understand:

For more information:

Outline

Introduction and motivation

Primitives

Examples

Comparison with locking, select loops

History and related topics

Cooperative (non-preemptive) scheduling

Primitives

Pseudocode in this talk

Process creation

Channel: the communication abstraction

Primitives - send and receive

Send

Receive

Semantics:

Primitives - alt

Alt (aka select)

    alt {
    x = <-c1:
        print("received %d from c1\n", x);
    c2 <-= y:
        print("sent %d to c2\n", y);
    }
    

Warm-up: concurrent prime sieve (McIlroy)

Can generate primes using a pipeline of procs.

    p = receive from left neighbor
    print p
    loop:
        x = receive from left neighbor
        if (p does not divide x)
            send x to right neighbor
    

Generating process sends 2, 3, 4, 5, 6, ... to leftmost proc.

Warm-up: code

Implementation in our pseudo-language.

    filter(c: chan of int)
    {
        p = <-c;
        print("%d\n", p);
    
        c1 = chan of int;
        proc filter(c1);
        while(x = <-c)
            if(x%p)
                c1 <-= x;
    }
      
    c = chan of int;
    proc filter(c);
    for(i=2;; i++)
        c <-= i;
    

Not representative of systems uses; hopefully mind-expanding.

Example: venti indexer

Background

For performance, want to keep all the disks busy.

With locks?

Example: venti indexer

Channel-based solution:

Arena reader:

    arenadiskproc(d: ArenaDisk)
    {
        for(each block b in d){
            xd = indexdisk(b);
            xd.c <-= indexentry(b);
        }
    }
    

Example: venti indexer (source code)

Arena reader:

    arenadiskproc(d: ArenaDisk)
    {
        for(each block b in d){
            xd = indexdisk(b);
            xd.c <-= indexentry(b);
        }
    }
    

Index writer:

    indexdiskproc(d: IndexDisk)
    {
        nentries = 0;
        while(ie = <-d.c){
            entries[nentries++] = ie;
            if(nentries == nelem(entries)){
                bufwrite(entries, nentries);
                nentries = 0;
            }
        }
        bufwrite(entries, nentries);
    }
    

Example: publish/subscribe

Pub/sub server publishes pair of channels, for publish and subscribe.

    typedef message = (string, string);  /* (topic, body) */
    struct Server
    {
        csub: chan of (string, chan of message);
        cpub: chan of message;
    };
    

Subscriber registers a channel with its topic of interest.

    c = chan of message;
    server.csub <- ("slashdot", c);
    for(;;){
        (t, s) = <-c;
        print("slashdot: %s\n", s);
    }
    

Publisher sends messages on server.cpub.

    server.cpub <- ("slashdot", "l337 hax0r dudes");
    

Example: pub/sub server

Event loop handling just the two server channels.

    subscribers = list of (string, chan of message);
    for(;;)
        alt {
        (topic, c) = <-csub:
            append(subscribers, (topic, c));
        (topic, body) = <-cpub:
            for((t, c) in subscribers)
                if(t == topic)
                    c <-= (topic, body);
        }
    

Problem: publishing can block if client stops reading.

Example: pub/sub server

Introduce new per-client thread to take care of queueing messages.

    buffer(dst: chan of message): chan of message
    {
        c = chan of message;
        proc bufferproc(c, dst);
        return c;
    }
    
    bufferproc(src: chan of message, dst: chan of message)
    {
        messages = list of string;
        for(;;)
            alt {
            msg <-= src:
                append(messages, msg);  
            len(messages) > 0 && dst <-= messages[0]:
                pop(messages);
            }
    }
    

Server loop barely changes, because interface is the same.

    (topic, c) = <-csub:
        append(subscribers, (topic, buffer(c)));
    

Example: pub/sub server proxy

    proxy(remote: Server): Server
    {
        new_csub = chan of (string, chan of message);
        local = Server(new_csub, remote.cpub);
        proc proxyproc(remote, local);
        return local;
    }
    
    proxyproc(remote: Server, local: Server)
    {
        topics = list of string;
        subscribers = list of (string, chan of message);
        from_remote = chan of message;
    
        for(;;)
            alt {
            (topic, c) = <-local.csub:
                append(subscribers, (topic, c));
                if(topic not in topics){
                    append(topics, topic);
                    remote.csub <- (topic, from_remote);
                }
            (topic, body) = <-from_remote:
                for((t, c) in subscribers)
                    if(t == topic)
                        c <-= (topic, body);
            }
    }
    

Pub/sub lessons

Communication abstraction makes both sides simple.

Channel (or set of channels) is an interface.

Outline

Introduction and motivation

Primitives

Examples

Comparison with locking, select loops

History and related topics

Cooperative (non-preemptive) scheduling

Comparison with Locks

Locks protect shared mutable state.

Message-passing moves mutable state into single-threaded loop.

Comparison with event loops

Top-level event loops provide one single thread of execution.

Threaded message-passing provides many single threads of execution.

History: Rumblings

Doug McIlroy, 1964

Doug McIlroy, 1968

History: Pipes

Thompson recalls:

History: Pipes

Thompson continued:

History: Pipes

McIlroy recalls:

Side note: prime sieve in shell script

    #!/bin/rc
    
    filter()
    {
        read p || exit
        while read x; do
            if [ `expr $x % $p` != 0 ]; then
                echo $x
            fi
        done | filter
    }
    
    seq 2 100 | filter
    

History: Communicating Sequential Processes (CSP)

Tony Hoare, 1978

Luca Cardelli and Rob Pike, 1985

Rob Pike, 1989

Result is like pipes but send typed messages instead of text.

History: Later languages

Phil Winterbottom, Alef, 1991 or so

Sean Dorward and Phil Winterbottom, Limbo, 1997 or so

Rob Pike's 2007 Google tech talk
Concurrency and message passing in Newsqueak

Related languages: Erlang

Erlang is all message-passing, completely functional.

Like in CSP, Erlang does not have first-class channels.

Erlang message sends are asynchronous, unreliable, unordered!

Related languages: Haskell

Haskell is a lazy functional programming language.

Concurrent prime sieve uses threads to implement lazy streams.

If language supports laziness directly, can write even cleaner programs.

Plan 9 thread library cheat sheet

    #include <thread.h>
    
    Channel *c;  
    c = chancreate(sizeof(int), 0);   /* c = chan of int */
    c = chancreate(sizeof(int), 5);   /* c = chan[5] of int */
    
    recv(c, &x);                      /* x = <-c */
    x = recvp(c);
    x = recvul(c);
    
    send(c, &x);                      /* c <-= x */
    sendp(c, x);
    sendul(c, x);
    

Plan 9 thread library cheat sheet - alt

    alt {
    x = <-c1:
        print("received %d from c1\n", x);
    cond && c2 <-= y:
        print("sent %d to c2\n", y);
    }
    

C + Libthread:

    Alt alts[3];
    
    alts[0] = (Alt){c1, &x, CHANRCV};
    alts[1] = (Alt){c2, &y, cond ? CHANSND : CHANNOP};
    alts[2] = (Alt){nil, nil, CHANEND};
    switch(alt(alts)){
    case 0:
        print("received %d from c1\n", x);
        break;
    case 1:
        print("sent %d to c2\n", y);
        break;
    }
    

Plan 9 thread library cheat sheet - proc

    proc f(x, y, z);
    

C + Libthread:

    struct Args
    {
        int x;
        int y;
        int z;
    };
    
    a = malloc(sizeof *a);
    *a = (Args){ x, y, z };
    proccreate(run_f, a, STACK);
    
    void
    run_f(void *v)
    {
        Args a = *(Args*)v;
        free(v);
        f(a.x, a.y, a.z);
    }
    

Duality

Lauer and Needham, 1979:

Many operating system designs can be placed into one of two very rough categories, depending upon how they implement and use the notions of process and synchronization. One category, the “Message-oriented System,” is characterized by a relatively small, static number of processes with an explicit message system for communicating among them. The other category, the “Procedure-oriented system,” is characterized by a large, rapidly changing number of small processes and a process synchronization mechanism based on shared data.

In this paper, it is demonstrated that these two categories are duals of each other and that a system which is constructed according to one model has a direct counterpart in the other. The principal conclusion is that neither model is inherently preferable, and the main consideration for choosing between them is the nature of the machine architecture upon which the system is being built, not the application which the system will ultimately support.

Duality, continued

Lauer and Needham's terminology

Libevent, libasync, etc. are not dual to threads and locks. They are crippled “Message-oriented systems”!

Alef, which provides locks and channels (and a lot of other things), is dual to itself!

Duality, continued.

If they are equivalent, why choose one over the other?

Complexity issues

If all you have is locks, use them to build multiple-reader, multiple-writer finite queues.

Summary

The “threads vs. events” question is misphrased.

Locks and top-level event loops are both evil.

Threads with events (message passing) works very well.

Plan 9 thread library provides necessary primitives.

Go forth and sin no more.

 

 

http://swtch.com/~rsc/talks/

Cooperative scheduling

Alef introduced cooperatively-scheduled tasks.

Typical use: procs for I/O, with one main proc for all tasks.

Example: acme fsys proc

Acme's implementation relies heavily on tasks.

Solution: a pool of execution server tasks running in the main proc:

    Xfid.ctl(Xfid *x)
    {
        for(;;){
            (*<-x->c)(x);     /* f = <- x->c; f(x); */
            bflush();         /* update screen */
            cxfidfree <-= x;  /* make x available for reuse */
        }
    }
    

Example: acme fsys proc

Rob Pike, Acme: a User Interface for Programmers

Cooperative scheduling: a warning

Cooperative scheduling is convenient, seductive.

Also subtle, precarious.

Ultimately, perhaps not worth the trouble. But there it is.