sicp exercise 3.47

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


;; Ans: a:
;; a shared variable, protected by a mutex, keeps count of the times the semaphore has been acquired.
(define (make-sem n)
  (let ((m (make-mutex))
        (count n))
    (define (the-sem s)
      (cond ((eq? s 'acquire)
             (m 'acquire)                   ;; acquire the mutex
             (if (> count 0)                ;; check if semaphore available
                 (begin                     ;; if semaphore available
                   (set! count (- 1 count)) ;; reduce by one
                   (m 'release))            ;; release mutex
                 (begin                     ;; if semaphore not available
                   (m 'release)             ;; release mutex
                   (the-sem 'acquire))))    ;; retry to acquire semaphore
            ((eq? s 'release)
             (m 'acquire)
             (set! count (+ 1 count))
             (m 'release))))
     the-sem))

;; Ans: b:
;; The implementation of make-sem with test-and-set! is same as above. Replace mutex code with test-and-set! code and increment the counter in different branches.