Concurrency Improvements to GoLisp

The concurrency primitives in GoLisp 1.0 were enough to do some basic multi-task funcitonality, but lacked some of the features needed for advanced task managment. We’ve added to GoLisp’s concurrency functions to improve on this and allow greater control over forked processes.

Join

While we had the ability to create new tasks with fork long before GoLisp 1.0, the only way to communicate with the process was through wake. To help with this, we’ve introduced a join call. It works similarlly to a thread join: the running process is blocked until the one being joined finishes, and the value resulting from the forked process is returned by join.

Example

Using forked processes we can create a mergesort that splits each step of sorting into two concurrent processes:

(define (merge list1 list2 predicate)
  (if (nil? list1) list2
    (if (nil? list2) list1
      (if (apply predicate (list (car list1) (car list2)))
        (cons (car list1) (merge (cdr list1) list2 predicate))
        (cons (car list2) (merge (cdr list2) list1 predicate))))))

(define (mergesort a-list predicate)
  (if (>= (length a-list) 2) (begin
    (let* ((mid (integer (ceiling (/ (length a-list) 2.0))))
           (split-lists (partition mid a-list))
           (proc (fork (lambda (proc a-list predicate) (mergesort a-list predicate)) (car split-lists) predicate))
           (sorted-list1 (mergesort (cadr split-lists) predicate))
           (sorted-list2 (join proc)))
            (merge sorted-list1 sorted-list2 predicate)))
    a-list))

Atomic Operations

We also introduced an atomic primitive to use for cross-process communication. Operating normally on GoLisp objects do not promise to be syncronous, so it was very easy to introduce race conditions, and in a lot of cases impossible to fix them. We expose all of the functionality in the Go sync/atomic package for 64-bit integers, the native integer type in GoLisp.

Example

Atomic operations are very useful for creating lockless synchronization between different processes.

The following example has a race condition in it, can you spot it?

(define lock #f)

(define (do-a)
  (when (not lock)
    (set! lock #t)
    (do-a-stuff)
    (set! lock #f)))

(define (do-b)
  (when (not lock)
    (set! lock #t)
    (do-b-stuff)
    (set! lock #f)))

It is possible for two processes to call (do-a) and (do-b) at the same time, and for execution to happen like this:

Both functions can run their code at the same time, which is what the lock is trying to prevent.

Atomic operations can solve this:

(define lock (atomic))

(define (do-a)
  (when (atomic-compare-and-swap! lock 0 1)
    (do-a-stuff)
    (atomic-store! lock 0)))

(define (do-b)
  (when (atomic-compare-and-swap! lock 0 1)
    (do-b-stuff)
    (atomic-store! lock 0)))

That way the check of lock and setting it are one atomic operation, so the race condition can not happen.

Channels

Channels are now supported in GoLisp. Any GoLisp data type can be passed through them, and both buffered and unbuffered variants are supported. They also have syntax shortcuts for reading from and writing to them. If you have used channels in Go before, you should have no trouble using them in GoLisp.

Example

Channels make task queues very easy to implement:

(define job-queue (make-channel 10))
(define results-queue (make-channel 10))
(define (do-thing proc)
  (do ((item (<-job-queue) (<-job-queue)))
      ((not (cadr item)))
      (results-queue<- (do-thing-with-item (car item)))))

(map (lambda (x) (fork do-thing)) (interval 4)) ; set up work jobs
(map (lambda (x) (job-queue<- x)) (interval 10)) ; pass some data
(map (lambda (x) (car (<-results-queue))) (interval 10)) ; read results

You can also create mutex funcitonality using channels:

(define (create-mutex) {
  state: (make-channel 1)
  lock: (lambda () (state<- nil))
  unlock: (lambda () (<-state))
  try-lock: (lambda () (channel-try-write state nil))
})

(define m (create-mutex))
;;; locking
(lock:> m)
;;; unlocking
(unlock:> m)
;;; try unlocking
(try-unlock:> m) ; #t if lock acquired, #f if not