Exercise 3.47.  A semaphore (of size n) is a generalization of a mutex. 
Like a mutex, a semaphore supports acquire and release operations, but 
it is more general in that up to n processes can acquire it 
concurrently. Additional processes that attempt to acquire the semaphore 
must wait for release operations. Give implementations of semaphores

a. in terms of mutexes

b. in terms of atomic test-and-set! operations.

————————————————————————————————————————————————————————————————————————

a.

(define (make-semaphore n)
  (let ((avail n)
        (mutex make-mutex))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
              (acquire-mutex mutex)
              (if (eq? avail 0)
                  (begin
                    (release-mutex mutex)
                    (the-semaphore 'acquire))
                  (begin
                    (set! avail (- avail 1))
                    (release-mutex mutex)
                    true)))
            ((eq? m 'release)
              (acquire-mutex mutex)
              (set! avail (+ avail 1))
              (release-mutex mutex)
              true)))

b.

(define (make-semaphore n)
  (define (make-cells n)
    (cond ((eq? n 0) '())
          (else (cons false (make-cells (- n 1))))))

  (define (acquire-one cells)
    (cond ((null? cells) false)
          ((test-and-set! cells) true)
          (else (acquire-one (cdr cells)))))

  (define (release-one cells)
    (if (car cells)
        (set-car! cells false)
        (release-one (cdr cells))))

  (let ((cells (make-cells n)))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
              (if (acquire-one cells)
                  true
                  (the-semaphore 'acquire)))
            ((eq? m 'release)
              (release-one cells))))
    the-semaphore))