►zthomae’s SICP solutions
▼3 Chapter 3
3.1 Exercise 3.1
3.2 Exercise 3.2
3.3 Exercise 3.3
3.4 Exercise 3.4
3.5 Exercise 3.5
3.6 Exercise 3.6
3.7 Exercise 3.7
3.8 Exercise 3.8
3.9 Exercise 3.9
3.10 Exercise 3.10
3.11 Exercise 3.11
3.12 Exercise 3.12
3.13 Exercise 3.13
3.14 Exercise 3.14
3.15 Exercise 3.15
3.16 Exercise 3.16
3.17 Exercise 3.17
3.18 Exercise 3.18
3.19 Exercise 3.19
3.20 Exercise 3.20
3.21 Exercise 3.21
3.22 Exercise 3.22
3.23 Exercise 3.23
3.24 Exercise 3.24
3.25 Exercise 3.25
3.26 Exercise 3.26
3.27 Exercise 3.27
3.28 Exercise 3.28
3.29 Exercise 3.29
3.30 Exercise 3.30
3.31 Exercise 3.31
3.32 Exercise 3.32
3.33 Exercise 3.33
3.34 Exercise 3.34
3.35 Exercise 3.35
3.36 Exercise 3.36
3.37 Exercise 3.37
3.38 Exercise 3.38
3.39 Exercise 3.39
3.40 Exercise 3.40
3.41 Exercise 3.41
3.42 Exercise 3.42
3.43 Exercise 3.43
3.44 Exercise 3.44
3.45 Exercise 3.45
3.46 Exercise 3.46
3.47 Exercise 3.47
3.48 Exercise 3.48
3.49 Exercise 3.49
3.50 Exercise 3.50
3.51 Exercise 3.51
3.52 Exercise 3.52
3.53 Exercise 3.53
3.54 Exercise 3.54
3.55 Exercise 3.55
3.56 Exercise 3.56
3.57 Exercise 3.57
3.58 Exercise 3.58
3.59 Exercise 3.59
3.60 Exercise 3.60
3.61 Exercise 3.61
3.62 Exercise 3.62
3.63 Exercise 3.63
3.64 Exercise 3.64
3.65 Exercise 3.65
3.66 Exercise 3.66
3.67 Exercise 3.67
3.68 Exercise 3.68
3.69 Exercise 3.69
3.70 Exercise 3.70
3.71 Exercise 3.71
3.72 Exercise 3.72
3.73 Exercise 3.73
3.74 Exercise 3.74
3.75 Exercise 3.75
3.76 Exercise 3.76
3.77 Exercise 3.77
3.78 Exercise 3.78
3.79 Exercise 3.79
3.80 Exercise 3.80
3.81 Exercise 3.81
3.82 Exercise 3.82
    ← prev  up  next → 

3.47 Exercise 3.47

An implementation of semaphores in terms of mutexes can proceed something like this:

A semaphore allows n concurrently-executing procedures at once. We can imagine checking this as equivalent to checking if any of n mutexes are unset.

(define (make-semaphore n)
  (define (get-available-mutex ms)
    (cond ((null? ms) null)
          ((car ms) ((car ms) 'acquire)
          (else (get-available-mutex ms)))))
  (define (make-mutexes times)
    (if (= 0 times)
        null
        (cons (make-mutex) (make-mutexes (- times 1)))))
  (let ((mutexes (make-mutexes n)))
    (define (the-semaphore m)
      (cond
        ((eq? m 'acquire)
          (let ((acquired (get-available-mutex mutexes)))
            (if (null? acquired)
                (the-semaphore 'acquire)
                (lambda () (acquired 'release)))))
        (else (error "UNKNOWN MESSAGE -- " m))))
    the-semaphore))

As our convention, is a slot in the semaphore is acquired, it returns a no-argument procedure that will release itself when called, so that the owner can relinquish control.

We could also implement the same idea using test-and-set! calls. Note the essential similarity between the two:

(define (make-semaphore n)
  (define (get-available-cell cells)
    (if (null? cells)
        null
        (let ((result (test-and-set! (car cells))))
          (if result
              (get-available-cell (cdr cells))
              (car cells)))))
  (define (make-cells times)
    (if (= 0 times)
        null
        (cons  (list false) (make-cells (- times 1)))))
  (let ((cells (make-cells n)))
    (define (the-semaphore m)
      (cond
        ((eq? m 'acquire)
          (let ((acquired (get-available-cell cells)))
            (if (null? acquired)
                (the-semaphore 'acquire)
                (lambda () (set-car! acquired false)))))
        (else (error "UNKNOWN MESSAGE -- " m))))
    the-semaphore))
    ← prev  up  next →