15 hours ago
my attempt to do the exercises in sicp.
Wednesday, March 24, 2010
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))
(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)
(set! count (+ 1 count))
;; 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.