SICP Exercise 3.47

; a: based on mutexes
(define (make-semaphore n)
  (let ((the-mutex (make-mutex))
        (count 0))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
             (the-mutex 'acquire)
             (if (= count n)
                 (begin
                   (the-mutex 'release)
                   (the-semaphore 'acquire))
                 (begin
                   (set! count (+ count 1))
                   (the-mutex 'release))))
            ((eq? m 'release)
             (the-mutex 'acquire)
             (if (> count 0)
                 (set! count (- count 1)))
             (the-mutex 'release))))
    the-semaphore))

; b: based on atomic test-and-set! operations
(define (make-semaphore n)
  (let ((count-lock (list false))
        (count 0))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
             (acquire-count-lock)
             (if (= count n)
                 (begin
                   (release-count-lock)
                   (the-semaphore 'acquire))
                 (begin
                   (set! count (+ count 1))
                   (release-count-lock))))
            ((eq? m 'release)
             (acquire-count-lock)
             (if (> count 0)
                 (set! count (- count 1)))
             (release-count-lock))))
    (define (acquire-count-lock)
      (if (test-and-set! count-lock)
          (acquire-count-lock)))
    (define (clear! count-lock)
      (set-car! count-lock false))
    (define (test-and-set! count-lock)
      ; atmoic opeartions behaving as the following
      (if (car count-lock)
          true
          (begin (set-car! count-lock true)
                 false)))
    the-semaphore))

Like this:

Be the first to like this post.

This entry was posted on Tuesday, August 4th, 2009 at 10:52 pm and is filed under Scheme, SICP. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to SICP Exercise 3.47

kmdalal says:

August 6, 2011 at 1:22 pm

These solutions do not work for me. They appear incorrect, and also inefficient. Here are mine, which have been reasonably tested (in Petite Chez Scheme). They re-use some functions defined in the SICP text. I’ve added a ‘count message for debugging.
-Mike Dalal


;;; (a) based on mutexes
(define (make-semaphore n)
  (let ((the-mutex (make-mutex))
        (count 0))
    (define (the-semaphore m)
      (cond ((eq? m 'count) count)
            ((eq? m 'acquire)
             (if (< count n) (set! count (+ count 1)))
             (if (= count n) (the-mutex 'acquire)))
            ((eq? m 'release)
             (the-mutex 'release)
             (if (> count 0) (set! count (- count 1))))))
    the-semaphore))

;;; (b) based on atomic test-and-set
(define (make-semaphore1 n)
  (let ((cell (make-cell))
        (count 0))
    (define (the-semaphore m)
      (cond ((eq? m 'count) count)
            ((eq? m 'acquire)
             (if (< count n) (set! count (+ count 1)))
             (if (= count n) (acquire-cell)))
            ((eq? m 'release)
             (release-cell)
             (if (> count 0) (set! count (- count 1))))))
    (define (release-cell) (clear! cell))
    (define (acquire-cell) (if (test-and-set! cell) (acquire-cell)))
    the-semaphore))

Ed Connell says:

February 18, 2012 at 3:50 pm

Mike, I’m skeptical of your proposal. Imagine an N-size semaphore starting at count = 0. N+1 threads try to acquire. All pass the (if (< count n) …) check at the same time because count is still 0. Then they all increment count with (set! count (+ count 1))). Even if these assignments happen in a serialized way (which is *not* guaranteed), we now have N+1 threads inside the critical section.

Reply

	zhilongji on SICP Exercise 4.9
	hunglun on SICP Solutions
	Curly Brace on SICP Exercise 4.8
	leon on SICP Exercise 4.6
	prity on SICP Exercise 2.55

Weiqun Zhang's Blog