1 665c255d 2023-08-04 jrmu (define (make-serializer)
 2 665c255d 2023-08-04 jrmu   (let ((mutex (make-mutex)))
 3 665c255d 2023-08-04 jrmu     (lambda (p)
 4 665c255d 2023-08-04 jrmu       (define (serialized-p . args)
 5 665c255d 2023-08-04 jrmu 	(mutex 'acquire)
 6 665c255d 2023-08-04 jrmu 	(let ((val (apply p args)))
 7 665c255d 2023-08-04 jrmu 	  (mutex 'release)
 8 665c255d 2023-08-04 jrmu 	  val))
 9 665c255d 2023-08-04 jrmu       serialized-p)))
10 665c255d 2023-08-04 jrmu 
11 665c255d 2023-08-04 jrmu (define (make-mutex)
12 665c255d 2023-08-04 jrmu   (let ((cell (list false)))
13 665c255d 2023-08-04 jrmu     (define (the-mutex m)
14 665c255d 2023-08-04 jrmu       (cond ((eq? m 'acquire) (if (test-and-set! cell)
15 665c255d 2023-08-04 jrmu 				  (the-mutex 'acquire)))
16 665c255d 2023-08-04 jrmu 	    ((eq? m 'release) (clear! cell))))
17 665c255d 2023-08-04 jrmu     the-mutex))
18 665c255d 2023-08-04 jrmu 
19 665c255d 2023-08-04 jrmu (define (clear! cell)
20 665c255d 2023-08-04 jrmu   (set-car! cell false))
21 665c255d 2023-08-04 jrmu ;; (define (test-and-set! cell)
22 665c255d 2023-08-04 jrmu ;;   (if (car cell)
23 665c255d 2023-08-04 jrmu ;;       true
24 665c255d 2023-08-04 jrmu ;;       (begin (set-car! cell true)
25 665c255d 2023-08-04 jrmu ;; 	     false)))
26 665c255d 2023-08-04 jrmu (define (test-and-set! cell)
27 665c255d 2023-08-04 jrmu   (without-interrupts
28 665c255d 2023-08-04 jrmu    (lambda ()
29 665c255d 2023-08-04 jrmu      (if (car cell)
30 665c255d 2023-08-04 jrmu 	 true
31 665c255d 2023-08-04 jrmu 	 (begin (set-car! cell true)
32 665c255d 2023-08-04 jrmu 		false)))))
33 665c255d 2023-08-04 jrmu 
34 665c255d 2023-08-04 jrmu ;; 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
35 665c255d 2023-08-04 jrmu 
36 665c255d 2023-08-04 jrmu ;; a. in terms of mutexes
37 665c255d 2023-08-04 jrmu 
38 665c255d 2023-08-04 jrmu ;; b. in terms of atomic test-and-set! operations. 
39 665c255d 2023-08-04 jrmu 
40 665c255d 2023-08-04 jrmu (define (make-semaphore n)
41 665c255d 2023-08-04 jrmu   (let ((mutex (make-mutex)))
42 665c255d 2023-08-04 jrmu     (define (the-semaphore m)
43 665c255d 2023-08-04 jrmu       (cond ((eq? m 'acquire) 
44 665c255d 2023-08-04 jrmu 	     (mutex 'acquire)
45 665c255d 2023-08-04 jrmu 	     (if (> n 0)
46 665c255d 2023-08-04 jrmu 		 (begin (set! n (- n 1))
47 665c255d 2023-08-04 jrmu 			(mutex 'release))
48 665c255d 2023-08-04 jrmu 		 (begin (mutex 'release)
49 665c255d 2023-08-04 jrmu 			(the-semaphore 'acquire))))
50 665c255d 2023-08-04 jrmu 	    ((eq? m 'release) 
51 665c255d 2023-08-04 jrmu 	     (mutex 'acquire)
52 665c255d 2023-08-04 jrmu 	     (set! n (+ n 1))
53 665c255d 2023-08-04 jrmu 	     (mutex 'release))))
54 665c255d 2023-08-04 jrmu     the-semaphore))
55 665c255d 2023-08-04 jrmu 
56 665c255d 2023-08-04 jrmu (define (make-semaphore n)
57 665c255d 2023-08-04 jrmu   (let ((cell (list false)))
58 665c255d 2023-08-04 jrmu     (define (clear! cell)
59 665c255d 2023-08-04 jrmu       (set-car! cell false))
60 665c255d 2023-08-04 jrmu     (define (the-semaphore m)
61 665c255d 2023-08-04 jrmu       (cond ((eq? m 'acquire) 
62 665c255d 2023-08-04 jrmu 	     (if (test-and-set! cell)
63 665c255d 2023-08-04 jrmu 		 (the-semaphore 'acquire)
64 665c255d 2023-08-04 jrmu 		 (if (> n 0)
65 665c255d 2023-08-04 jrmu 		     (begin (set! n (- n 1))
66 665c255d 2023-08-04 jrmu 			    (clear! cell))
67 665c255d 2023-08-04 jrmu 		     (begin (clear! cell)
68 665c255d 2023-08-04 jrmu 			    (the-semaphore 'acquire)))))
69 665c255d 2023-08-04 jrmu 	    ((eq? m 'release) 
70 665c255d 2023-08-04 jrmu 	     (if (test-and-set! cell)
71 665c255d 2023-08-04 jrmu 		 (the-semaphore 'release)
72 665c255d 2023-08-04 jrmu 		 (begin (set! n (+ n 1))
73 665c255d 2023-08-04 jrmu 			(clear! cell))))))
74 665c255d 2023-08-04 jrmu     the-semaphore))