Concurrency

In the real world, things don't happen one at a time. Even on the computer, you probably have several tabs open right now, with music playing in the background, and maybe some other homework open as you read this.

Computers deal with this by dividing their time among the different processes on the system. Naturally there are some issues to deal with—if you can stop in the middle of any procedure, you need to make sure you can pick up where you left off! And if you have a computer with multiple processors or multiple cores (which is quite likely these days), your computer can really be running two processes' instructions at the same time, instead of just faking it by switching back and forth.

This is a long review sheet, so here are the terms you ought to recognize, in advance:

• test-and-set!
• clear!
• atomic
• mutex (lock)
• acquire / release
• critical section
• serializer
• protect
• "correct"

The example of a concurrency problem I gave in section was the story about Wheat Thins, where you and your roommate both see that you are out, and both end up going to the store.

Another example concerns collaborative content, such as source code in a version-tracking repository, or more simply, two people editing the same Wikipedia page. If one of them sends their changes before the other is done, the second person might overwrite what was there, rather than taking it into account. Problem!

In this class, we talk about three levels of protection tools: test-and-set!, mutexes, and serializers. Let's use each of them to try to solve the Wikipedia problem.

We already know we can't use test-and-set! to modify a Wikipedia page—it only sets things to #t. Let's be a little more formal there. Here's what test-and-set! does:

(car cell) before the call	(car cell) after the call	Return value
#f	#t	#f
#t	#t	#t

You can see after calling test-and-set!, the variable is guaranteed to be #t. (Do you see why?) The return value is the old value of (car cell)

; from SICP, p. 312
(define (test-and-set! cell)
  (if (car cell)
    #t
    (begin (set-car! cell #t)
           #f)))

The book's implementation uses a pair to hold the single value to avoid making test-and-set! a special form; the cdr is ignored. (This isn't really important, but in case anyone was curious.)

• Keywords: What part of the system provides the test-and-set! operation?

  (show answer)

  Generally hardware. Occasionally, a different low-level concurrency operation will be provided; it depends on what processor you have. In this case, test-and-set! can usually be implemented in terms of another hardware operation.

  (hide answer)

• Keywords: What's the corresponding method to clear a cell after it's been set?

  (show answer)

  Sort of a giveaway: clear!. Notice that it is not test-and-clear!; while you could certainly define such an operation, it turns out you generally only need one test in practice.

  (hide answer)

• Why can't we just type this definition into STk and use it that way? (Hint: what would be incorrect behavior here?)

  (show answer)

  Well, it works fine in a non-concurrent system, but that defeats the purpose! In a concurrent situation, you could have procedure J and procedure B both trying to test-and-set! the same cell. Assuming the cell is initially false, what we want is for either J or B to set the cell to #t and get the old value of #f back. Then the other procedure should see that the cell is already set, and get a return value of #t.

  What might happen, however, is that J gets there first, sees that the cell is false—and then gets interrupted. The CPU switches over to B's process and also finds that the cell is false. It sets the cell to #t and returns #f to the caller. Now it's J's turn again, and the CPU will once again set the cell to #t and returns #f to the caller. Both callers got back false values!

  Why might this be a problem? It depends what the cell is representing. Consider the game Spoons, in which there are N players and N-1 spoons. At the end of the game, everyone tries to grab a spoon. If the cell represents whether or not a spoon is taken, then both the J and B processes will think that the spoon was unused before they tried to grab it. But they can't both have the spoon!

  (hide answer)

The last question used the word "incorrect". Let's take a moment to define what correct means: a correct result from running several things in parallel is a result you could get by running them in some order in serial (one after another).

(parallel-execute (lambda () (set! x 0))
                  (lambda () (set! x 1)) )

Both 1 and 0 are "correct" values for x!

Let's apply test-and-set! to our problem: how about each page on Wikipedia has a flag (either #t or #f) that indicates whether or not someone is editing? Then an edit might look something like this:

(define (edit page)
  (if (test-and-set! (get-cell page))
      (begin (wait-a-bit)  ; don't worry how this works
             (edit page) ) ; try again
      (begin (display-page page)
             (set-contents! page (read))
             (clear! (get-cell page)) )))

If someone else was already editing, we wait a bit and see if they've finished. Otherwise, if the page is clear, we've set the editing flag ourself, and can edit the page safely. We do have to remember to clear the editing flag when we're done.

This "wait until available" pattern turns out to be a convenient one: let's build another useful ADT for it. A mutex (or lock) is a data type that is either held or free. If someone holds the mutex, no one else can acquire it until the holder releases it.

• Keywords: What part of the system usually provides the mutex data type?

  (show answer)

  Generally the operating system. Mutexes are simple, low-level, and widely used, so having them in the OS seems like a good choice. (It also implements users from having to call test-and-set! themselves.)

  (hide answer)

• Fill in implementations for the acquire and release messages:

  (define (make-mutex)
    (let ((cell (list #f)))
      (define (dispatch msg)
        (cond ((eq? msg 'acquire) ...)
              ((eq? msg 'release) ...)
              (else (error "Bad message to mutex: " msg)) ))
      dispatch))

  (show answer)

  (define (make-mutex)
    (let ((cell (list #f)))
      (define (dispatch msg)
        (cond ((eq? msg 'acquire)
               (if (test-and-set! cell)
                   (begin (wait-a-bit)
                          (dispatch 'acquire) )) ; No else clause!
              ((eq? msg 'release) (clear! cell))
              (else (error "Bad message to mutex: " msg)) ))
      dispatch))

  When we acquire the mutex, we test-and-set! the cell, just like when explicitly protecting the Wikipedia edit. Again, if the cell was already #t, we wait a bit and then try again. The difference is that when we know we've set the cell ourselves (when it was #f before we set it), we just end.

  Releasing the mutex is easy: just call clear!.

  (hide answer)

Since we are guaranteed that only one process can acquire the mutex at once, we can rewrite our Wikipedia-editing procedure to be a little more straightforward.

(define (edit page)
  ((get-mutex page) 'acquire) ; will wait until we actually hold the mutex
  (display-page page)
  (set-contents! page (read))
  ((get-mutex page) 'release) )

Much easier to see what's going on this way!

But of course, we still have the serialization code inside the methed. Every operation on this page will use the same mutex. That's why we have one more level of abstraction: serializers. While mutexes protect a critical section of code, serializers protect entire procedures.

How do we use serializers? A serializer is a procedure that takes a procedure and returns a protected version of that procedure. Any protected procedures created using the same serializer are guaranteed not to run at the same time!

• Keywords: What part of the system usually provides serializers?

  (show answer)

  The programming language, or high-level libraries. Serializers depend at least a little bit on how procedure calls work, so they can't really be provided by a lower-level part of the system. But like mutexes, serializers insulate the user from having to think about details (such as remembering to release the mutex when you're done!).

  (hide answer)

• Fill in implementations for the serializer

  (define (make-serializer)
    (let ((m (make-mutex)))
      (lambda (proc)
        (lambda args
          ...))))

  Confused by "(lambda args ...)? This is the super-short form of the dotted-tail syntax for "any number of arguments"; in this case, all of the arguments are collected in the args variable. This lets us use serializers with functions that take any number of arguments. Hint: you're going to want to use Scheme's apply in your answer...

  If you don't want to deal with it, you can pretend all procedures being serialized have no arguments and don't return anything useful, which makes the problem a little easier.

  (show answer)

  (define (make-serializer)
    (let ((m (make-mutex)))
      (lambda (proc)
        (lambda args
          (m 'acquire)
          (let ((result (apply proc args)))
            (m 'release)
            result)))))

  Notice how it looks exactly like our previous implementation of edit! We just took the original idea and wrapped it in some code to make the whole thing generic. Now we have a procedure that generates serializers.

  The simplified version is even easier, since it doesn't have to deal with return values:

  (define (make-serializer)
    (let ((m (make-mutex)))
      (lambda (proc)
        (lambda ()
          (m 'acquire)
          (proc)
          (m 'release) ))))

  (hide answer)

If we're using serializers to implement our code, things get really simple.

(define (edit page)
  (((get-serializer page)
    (lambda ()
      (display-page page)
      (set-contents! page (read)) ))))

That is the correct number of parens: we're getting the serializer, then using it to protect our actual work, then calling the protected procedure that the serializer just created.

Even better, we can reuse this serializer for any other kinds of edits to the page, like deleting it, or moving it to another section of the wiki. We can even save protected versions of procedures, and only invoke the serializer once:

(define (make-editor page)
  ((get-serializer page)
   (lambda ()
     (display-page page)
     (set-contents! page (read)) )))
     
(define edit-homepage (make-editor homepage))

edit-homepage is now a procedure of no arguments that edits the Wikipedia homepage in a safe way; it waits for anyone else to finish editing first. There is no chance of you seeing an old version of the page; the page shown by display-page is guaranteed to be up-to-date—which is what we were after all along.

As a final note, it's worth pointing out that Wikipedia doesn't actually do this! Instead, they keep track of people's changes, and if multiple edits happen, they try to merge them. If the merge doesn't work out, hopefully one of the editors is notified to complete the merge by hand. But there are real systems that work like this one, where only one person can access some data at a time.

Whew! That was quite a lot of material. Hopefully that helped some; if not, take a look again at the lecture notes, the book, and perhaps some other TA's notes. And, as always, feel free to send me e-mail, or post to the newsgroup!

Back to Jordy's home page | Course home page