sicp-ex-3.47



<< Previous exercise (3.46) | Index | Next exercise (3.48) >>


gws

  
  
  
 (define (make-semaphore n) 
   (let ((lock (make-mutex)) 
         (taken 0)) 
     (define (semaphore command) 
       (cond ((eq? command 'acquire) 
              (lock 'acquire) 
              (if (< taken n) 
                  (begin (set! taken (1+ taken)) (lock 'release)) 
                  (begin (lock 'release) (semaphore 'acquire)))) 
             ((eq? command 'release) 
              (lock 'acquire) 
              (set! taken (1- taken)) 
              (lock 'release)))) 
     semaphore)) 

leafac

I think the above implementation can be improved. Instead of the explicit busy way, we can use a second mutex that makes the clients hang. This way, if we can come up with a better implementation for mutexes, semaphores get the benefit as well:

 (define (make-semaphore maximum-clients) 
   (let ((access-mutex (make-mutex)) 
         (exceeded-mutex (make-mutex)) 
         (clients 0)) 
     (define (the-semaphore message) 
       (cond ((eq? message 'acquire) 
              (access-mutex 'acquire) 
              (cond ((> clients maximum-clients) 
                     (access-mutex 'release) 
                     (exceeded-mutex 'acquire) 
                     (the-semaphore 'acquire)) 
                    (else 
                     (set! clients (+ clients 1)) 
                     (if (= clients maximum-clients) 
                         (exceeded-mutex 'acquire)) 
                     (access-mutex 'release)))) 
             ((eq? message 'release) 
              (access-mutex 'acquire) 
              (set! clients (- clients 1)) 
              (exceeded-mutex 'release) 
              (access-mutex 'release)))) 
     the-semaphore)) 

Also, here's an answer for part b, which is very similar to what gws did. Here, the busy wait is inevitable:

 (define (make-semaphore maximum-clients) 
   (let ((access-mutex (list false)) 
         (clients 0)) 
     (define (the-semaphore message) 
       (cond ((eq? message 'acquire) 
              (if (test-and-set! access-mutex) 
                  (the-semaphore 'acquire)) 
              (cond ((> clients maximum-clients) 
                     (clear! access-mutex) 
                     (the-semaphore 'acquire)) 
                    (else 
                     (set! clients (+ clients 1)) 
                     (clear! access-mutex)))) 
             ((eq? message 'release) 
              (if (test-and-set! access-mutex) 
                  (the-semaphore 'release)) 
              (set! clients (- clients 1)) 
              (clear! access-mutex)))) 
     the-semaphore))