1
\$\begingroup\$

Can anyone check my solution to the first part of exercise 3.47 in SICP? Thanks.

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

  1. in terms of mutexes
    ...

I have a local state called number-of-processes which tracks the processes that acquired the semaphore. Since it is mutated when acquire and release operations occur, I used a mutex to prevent concurrent writes.

Here is my code: I displayed the outputs of some variable for testing.

> (define (make-serializer n)
    (let ((semaphore (make-semaphore n)))
      (lambda (p)
        (define (serialized-p . args)
          (semaphore 'acquire)
          (let ((val (apply p args)))
            (newline)
            (display val)
            (semaphore 'release)
            val))
        serialized-p)))

  (define (make-semaphore n)
    (let ((mutex (make-mutex))
          (number-of-processes 0))
      (define (acquire)
        (mutex 'acquire)
        (if (< number-of-processes n)
            (begin (set! number-of-processes (+ number-of-processes 1))
                   (display 'acquired)
                   (mutex 'release))
            (begin (mutex 'release)
                   (acquire))))
      (define (release)
        (mutex 'acquire)
        (if (> number-of-processes 0)
            (begin (set! number-of-processes (- number-of-processes 1))
                   (newline)
                   (display 'released)
                   (newline))
            (error "error!"))
        (mutex 'release))
      (define (the-semaphore m)
        (cond ((eq? m 'acquire) (acquire))
              ((eq? m 'release) (release))))
      the-semaphore)) 

I tested it like this:

(define s (make-serializer 2))
(define p1 (s (lambda () 1)))
(define p2 (s (lambda () 2)))
(define p3 (s (lambda () 3)))
(define p4 (s (lambda () 4)))
(define p5 (s (lambda () 5)))

The outputs are:

> (parallel-execute p1)
acquired
1
released
(1)
> (parallel-execute p1 p2)
acquired
1
acquired
2
released
released
(1 2)
> (parallel-execute p1 p2 p3)
acquired
1
acquired
2
released
acquired
3
released
released
(1 2 3)
> (parallel-execute p1 p2 p3 p4)
acquired
1
acquired
2
released
acquired
4
released
acquired
3
released
released
(1 2 4 3)
> (parallel-execute p1 p2 p3 p4 p5)
acquired
4
acquired
1
released
acquired    
2
released
released
acquired
5
acquired
3
released
released
(4 1 2 5 3)

I believe my procedure is working correctly. All my tests passed. How can I improve this code? Thanks.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please use Emacs to format your code. \$\endgroup\$ – sds Dec 17 '18 at 16:46
  • 1
    \$\begingroup\$ @sds I'm afraid emacs is inaccessible with my screen reader. \$\endgroup\$ – morbidCode Dec 17 '18 at 17:16
  • \$\begingroup\$ @sds I used the indenting feature of racket. Can you check it out? Is it readable now? Thanks. \$\endgroup\$ – morbidCode Dec 18 '18 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.