Should we use threads or events?

• Andrew Birrell: threads.
• John Ousterhout: events.
• John DeTreville: no.
• Rob Pike: yes.

Bell Labs approach: threads and events.

• Squeak, Newsqueak, Alef, Limbo

Drawbacks of threads (Ousterhout):

• synchronization, deadlock, hard to debug
• library layering, callbacks complicated by locks
• good performance is hard, threads not well supported
• “often don't want concurrency anyway”

Drawbacks of events (Ousterhout):

• long-running handlers make apps non-responsive
• can't maintain local state across events
• no CPU concurrency
• event-driven I/O not always well supported

Actually drawbacks of locks and top-level select loops!

Model:

• Each thread maintains private, local state.
• Threads interact by communication (messages, aka events).
• No mutable global variables.
• Thread creation, context switch, message sends are very cheap
• Shared data sits behind protocol-serving threads

Benefits:

• no locking problems
• can maintain local state across events
• can use CPU concurrency
• long-running handlers don't stop other threads
• don't need event-driven I/O support

Pseudocode in this talk

• Essential syntax common to Newsqueak, Alef, Limbo
• Translation to C and libthread at end.

Process creation

• proc f(x, y, z)
  • Creates new proc (thread) executing f(x, y, z).

Channel: the communication abstraction

• chan of int
  • Unidirectional channel for sending and receiving ints.
• c = chan of int
  • Allocate unbuffered channel
• c = chan[5] of int
  • Allocate buffered channel (queue)

Send

• c <-= x;
  • Send the value x on c.

Receive

• x = <-c;
  • Receive a value from c and assign it to x.

Semantics:

• Guaranteed in-order delivery.
• Receive blocks until there is data to receive.
• Send on unbuffered channel blocks until receiver comes along.
• Send on buffered channel blocks until data is placed in buffer.
• Multiple readers, multiple writers okay.

Background

• Venti stores data across many arena disks, index disks.
• Indexer's job is to read each block on arena disks and store index entries on the index disks.
• Assignment of arena block to index disk is (pseudo)random.

For performance, want to keep all the disks busy.

• Read from all arena disks simultaneously.
• Write to all index disks simultaneously.

With locks?

• one reader per arena, using locks to synchronize index writes?
• ???

Arena reader:

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

    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);
    }
    

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");
    

    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.

    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)));
    

Communication abstraction makes both sides simple.

• Have server loop and client loop.
• Thread & lock solutions much more complicated.
  • Subscription registers a callback?
  • If one thread publishes, what thread do the callbacks run in?
  • If subscription has get() method, how does that block and synchronize with publishers?

Channel (or set of channels) is an interface.

• Defines exactly how to interact with a given resource.
• Easy to use filters that preserve that interface.
  • buffer, proxy
• Rob Pike built a window system as a channel filter on top of the usual hardware screen interface.

Locks protect shared mutable state.

• Specifically, they protect invariants about the state.
• lock(x) says “I depend on the invariants protected by x.”
  or “I'm about to break the invariants protected by x. Look away!”
• unlock(x) says “I'm done (and if I broke the invariants, I've fixed them).”
• Invariants always existed, just easier to break with multithreading.
• Locks unnecessary in single-threaded program.

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

• Invariants still exist, like in single-threaded code.
• But the server thread is itself single-threaded, easier to reason about.
• Can inspect individual server threads for correctness.
• No need to worry about other threads — they can't see into our state.

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

• Single-threaded, so easy to reason about.
• Handlers might have their own constrants, simulating logical threads.
• Handlers can't maintain local state (stack variables).
• Handlers can't block easily (stack ripping).

Threaded message-passing provides many single threads of execution.

• (If one event loop is good, many is better!)
• Each is single-threaded and isolated, so easy to reason about.
• Protocol for interacting with other threads is specified.
• Each message loop can maintain local state, can block if needed.

Doug McIlroy, 1964

• “We should have some ways of coupling programs like garden hose--screw in another segment when it becomes necessary to massage data in another way. This is the way of IO also.”

Doug McIlroy, 1968

• “Coroutines: semantics in search of a syntax”
• Unpublished Bell Labs memorandum
• [McIlroy] “It was clearly a beautiful mental model, this idea that the output from one process would just feed in as input to another. There was syntactic difficulty in talking about that mental model, and I have a co-routine paper written in 1968 that was never, never printed, because it was always a little too ugly, struggling with syntax.”

Tony Hoare, 1978

• “Communicating sequential processes,” CACM, August 1978
• Later a book, but the paper is far more concise.

Luca Cardelli and Rob Pike, 1985

• “Squeak: a Language for Communicating with Mice,” SIGGRAPH 1985

Rob Pike, 1989

• “Newsqueak: a Language for Communicating with Mice,” Computing Science Technical Report 143, AT&T Bell Laboratories, Murray Hill, 1989.
• “A Concurrent Window System,” Computing Systems 2(2) 133-153.

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

• Implementation is more efficient (user space)

Erlang is all message-passing, completely functional.

• Developed at Ericsson telecom starting in late 1980s.
• No way to create shared mutable data.
• Used in many telecommunications apps, with one thread per call!
• Starting to get traction for other network programming.

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

• Sends are targeted at proc ids.
• Receives can restrict acceptable messages with pattern matching.

Erlang message sends are asynchronous, unreliable, unordered!

• Perhaps a better model for real world networks.
• Makes it easier to express real world failures.

Haskell is a lazy functional programming language.

• On the surface, nothing to do with concurrency.
• Lazy computation ends up creating lots of parallel threads of control.

Concurrent prime sieve uses threads to implement lazy streams.

• Doug McIlroy, “Squinting at Power Series,” Software—Practice and Experience, 20(7) (July 1990), 661-683.

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

• Doug McIlroy, “Power series, power serious,” Functional Pearl, 1999.

• Doug McIlroy, “The music of streams,” Information Processing Letters 77 (2001) 189-195.

Lauer and Needham's terminology

• Traditional threads and locks == “Procedure-oriented system”
• Threads with message-passing == “Message-oriented system”
• One big event loop with message-passing == ???

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!

The “threads vs. events” question is misphrased.

Locks and top-level event loops are both evil.

Threads with events (message passing) works very well.

• exposes interfaces, often composable ones
• can produce simpler, easier to understand programs

Plan 9 thread library provides necessary primitives.

Go forth and sin no more.

Alef introduced cooperatively-scheduled tasks.

• Tasks are hard-wired to a particular proc.
• In a proc, only one task runs at a time.
• Must block explicitly (send, receive, alt).
• System calls block entire proc, don't reschedule task.
• Tasks within a proc can share data in tiny critical sections without locks (as long as sections cannot block).
• Tasks in other procs still run independently.

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

Acme's implementation relies heavily on tasks.

• Almost all tasks in main proc, sharing data, no locks.
• 9P protocol I/O (blocking system calls) must be in separate proc.
• 9P service logic needs to run in the main proc.

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 */
        }
    }
    

• Actually many of these tasks, allocated on demand.

Cooperative scheduling is convenient, seductive.

• no need to worry about concurrency, locks
• can safely share data between tasks in a single proc

Also subtle, precarious.

• might accidentally call a function that blocks, breaking up what needs to be an atomic section
• system call I/O (blocks proc) is different from channel I/O (reschedules task)
  • Plan 9 from User Space adds a “turn off task rescheduling in this proc” primitive to mimic system call I/O even when using channels.

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

• tempting to reintroduce locks anyway (p2psim)
• Dorward and Winterbottom dropped tasks when designing Limbo.