recitation 23: asynchronous computing

------------------------------------------------------------------------
* special form to launch parallel computation (extension of Scheme)
  (parallel-execute <process-1> <process-2> ... <process-n>)

* code to serialize accesses to share resources by parallel computation

(define (make-serializer) 
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
	(mutex 'acquire)
	(let ((val (apply p args)))
	  (mutex 'release)
	  val))
      serialized-p)))

(define (make-mutex)
  (let ((cell (list #f)))
    (define (the-mutex m)
      (cond ((eq? m 'acquire)
	     (if (test-and-set! cell)
		 (the-mutex 'acquire)))
	    ((eq? m 'release)
	     (clear! cell))))
    the-mutex))

(define (clear! cell) (set-car! cell #f))

;; remember this must be atomic to guarantee proper serialization
(define (test-and-set! cell)
  (if (car cell)
      #t
      (begin (set-car! cell #t)
	     #f)))

------------------------------------------------------------------------
* We want the student(s) to copy down exactly once everything the 
  professor(s) draws on the chalkboard.

(define (make-chalkboard)
  (let ((drawing '())
        (mutex (make-mutex)))
    (define (write! new-drawing)
      (mutex 'acquire)
      (set! drawing new-drawing)
      (mutex 'release))
    (define (contents)
      (mutex 'acquire)
      (let ((result drawing))
	(mutex 'release)
	result))
    (lambda (m) 
      (cond ((eq? m 'write!) write!)
	    ((eq? m 'contents) contents)
	    (else (error "Invalid message -- CHALKBOARD"))))))

* what does the mutex do in this code?
  the mutex ensures that a partially written drawing is not copied
  by the student.  We don't want to read the variable drawing at
  the exact time it is being set! because we might get garbage.

(define (make-professor chalkboard)
  (define (draw-environment-diagram) ...)
  (define (lecture)
    ((chalkboard 'write!) (draw-environment-diagram))
    (lecture))
  (lambda (m) 
    (cond ((eq? m 'lecture) lecture)
	  (else (error "Your message has confused the professor")))))

(define (make-student chalkboard)
  (define (write-on-paper notes) ...)
  (define (take-notes)
    (write-on-paper ((chalkboard 'contents)))
    (take-notes))
  (lambda (m) 
    (cond ((eq? m 'take-notes) take-notes)
	  (else (error "Your message has confused the student")))))

(define chalkboard (make-chalkboard))
(define Trevor (make-professor chalkboard))
(define Alyssa (make-student chalkboard))
(parallel-execute ((Trevor 'lecture)) ((Alyssa 'take-notes)))

* what can still go wrong?  how can we fix it?
  if Trevor writes too fast (or Alyssa falls asleep during class)
  Alyssa might miss some notes.  likewise, if Alyssa copies too fast
  (or Trevor pauses) Alyssa might copy down the same notes multiple 
  times.  We can fix it by adding a condition variable:

(define (make-chalkboard)
  (let ((drawing '())
        (mutex (make-mutex))
	(student-done? #f))
    (define (write! new-drawing)
      (mutex 'acquire)
      (if student-done?
	  (begin
	    (set! drawing new-drawing)
	    (set! student-done? #f)
	    (mutex 'release))
	  (begin
	    (mutex 'release)
	    (write! new-drawing))))
    (define (contents)
      (mutex 'acquire)
      (if student-done?
	  (begin (mutex 'release)
		 (contents))
	  (let ((result drawing))
	    (mutex 'release)
	    result)))
    (lambda (m) 
      (cond ((eq? m 'write!) write!)
	    ((eq? m 'contents) contents)
	    (else (error "Invalid message -- CHALKBOARD"))))))

------------------------------------------------------------------------
(define Peter (make-professor chalkboard))
(define Ben (make-student chalkboard))
(parallel-execute ((Trevor 'lecture)) ((Peter 'lecture)) 
		  ((Alyssa 'take-notes)) ((Ben 'take-notes)))

* what can go wrong now?  how can we fix it?
  multiple professors is not a problem, they can only write on the
  board one-at-a-time, and they'll have to wait until the student 
  is done taking notes.  but to handle multiple students we'll need
  to store a list of the students who have finished copying the
  drawing and only write something new when all of the students
  are done.

------------------------------------------------------------------------
(define (make-thing)
  (let ((mutex (make-mutex)))
    (lambda (m)
      (cond ((eq? m 'grab) (lambda () (mutex 'acquire)))
            ((eq? m 'drop) (lambda () (mutex 'release)))))))
(define chalk (make-thing))
(define book (make-thing))

(define (make-professor chalkboard)
  (define (make-environment-diagram) ...)
  (define (prepare-diagram from-what) ...)
  (define (confirm-environment-diagram with-what) ...)
  (define (cautious-lecture)
    ((book 'grab))
    (let ((diagram (prepare-diagram book)))
      ((chalk 'grab))
      ((chalkboard 'write!) diagram))
    ((chalk 'drop))
    ((book 'drop))
    (cautious-lecture))
  (define (brash-lecture)
    ((chalk 'grab))
    ((chalkboard 'write!) (make-environment-diagram))
    ((book 'grab))
    (confirm-environment-diagram book)
    ((chalk 'drop))
    ((book 'drop))
    (brash-lecture))
  (lambda (m) 
    (cond ((eq? m 'cautious-lecture) cautious-lecture)
	  ((eq? m 'brash-lecture) brash-lecture)
	  (else (error "Your message has confused the professor")))))

(define Trevor (make-professor chalkboard))
(define Peter (make-professor chalkboard))
(parallel-execute ((Trevor 'cautious-lecture)) ((Peter 'brash-lecture)))

* what can go wrong?  how can we fix it?
  we can get into deadlock if Trevor grabs the book and Peter grabs
  the chalk.  neither can finish since they are waiting for the other
  mutex.  we can fix this deadlock by insisting that all mutexes 
  necessary for a particular computation are acquired in some 
  predefined order,  often alphabetical or numerical.  in this example 
  we can change the code as follows:

  (define (brash-lecture)
    ((book 'grab))
    ((chalk 'grab))
    ((chalkboard 'write!) (make-environment-diagram))
    (confirm-environment-diagram book)
    ((chalk 'drop))
    ((book 'drop))
    (brash-lecture))

------------------------------------------------------------------------