Exercise 3.47

a

The semaphore that uses a mutex.
Note the mutex is used to protect both the read and mutation of count when acquiring and releasing the semaphore.

(define (make-sempahore n)
  (let ((count n)
        (the-mutex (make-mutex)))
    (define (the-sempahore m)
      (cond ((eq? m 'acquire)
             (the-mutex 'acquire)
             (if (zero? count)
                 (begin
                   (the-mutex 'release)
                   (the-semaphore 'acquire))
                 (begin
                   (set! count (- count 1))
                   (the-mutex 'release))))
            ((eq? m 'release)
             (the-mutex 'acquire)
             (if (= count n)
                 (the-mutex 'release)
                 (begin
                   (set! count (+ count 1))
                   (the-mutex 'release))))))
    the-sempahore))

b

The semaphore that uses calls to test-and-set!.
Note that for these to work both test-and-set! and clear! must be atomic.

(define (make-sempahore n)
  (let ((count n)
        (cell (list false)))
    (define (the-sempahore m)
      (cond ((eq? m 'acquire)
             (if (test-and-set! cell)
                 (the-semaphore 'acquire)
                 (if (zero? count)
                     (clear! cell)
                     (begin
                       (set! count (- count 1))
                       (clear! cell)))))
            ((eq? m 'release)
             (if (test-and-set! cell)
                 (the-semaphore 'release)
                 (if (= count n)
                     (clear! cell)
                     (begin
                       (set! count (+ count 1))
                       (clear! cell)))))))
    the-sempahore))
Advertisements

5 thoughts on “Exercise 3.47

  1. Yes – it seems I messed up this exercise. Can you say a bit more about the considerations that cause the problems?

    I’ll leave the original though – it’s good to see past mistakes:)

    Thanks for the link to your solution.

  2. On line 8 of the latter “a” (should be “b”, I figure), when (zero? count) is true, after the cell is cleared, you should call (the-semaphore ‘acquire) again so the procedure can try and try until “count” is larger than zero. And on line 16, you don’t have to do that check since count won’t get larger than n :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s