1 665c255d 2023-08-04 jrmu (define (make-serializer)
2 665c255d 2023-08-04 jrmu (let ((mutex (make-mutex)))
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)
9 665c255d 2023-08-04 jrmu serialized-p)))
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))))
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)
24 665c255d 2023-08-04 jrmu ;; (begin (set-car! cell true)
26 665c255d 2023-08-04 jrmu (define (test-and-set! cell)
27 665c255d 2023-08-04 jrmu (without-interrupts
29 665c255d 2023-08-04 jrmu (if (car cell)
31 665c255d 2023-08-04 jrmu (begin (set-car! cell true)
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
36 665c255d 2023-08-04 jrmu ;; a. in terms of mutexes
38 665c255d 2023-08-04 jrmu ;; b. in terms of atomic test-and-set! operations.
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)
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))
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)
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))
76 665c255d 2023-08-04 jrmu ;; Exercise 3.48. Explain in detail why the deadlock-avoidance method described above, (i.e., the accounts are numbered, and each process attempts to acquire the smaller-numbered account first) avoids deadlock in the exchange problem. Rewrite serialized-exchange to incorporate this idea. (You will also need to modify make-account so that each account is created with a number, which can be accessed by sending an appropriate message.)
78 665c255d 2023-08-04 jrmu ;; The mutex for the account with the smaller number will always be acquired first. So, if two processes need to process the same two accounts, only one mutex for the lower-numbered account will be acquired successfully. So, only one process will obtain the first mutex, and that process will then proceed to obtain the other mutex.
80 665c255d 2023-08-04 jrmu (define (serialized-exchange account1 account2)
81 665c255d 2023-08-04 jrmu (let ((serializer1 (account1 'serializer))
82 665c255d 2023-08-04 jrmu (serializer2 (account2 'serializer))
83 665c255d 2023-08-04 jrmu (num1 (account1 'number))
84 665c255d 2023-08-04 jrmu (num2 (account2 'number)))
85 665c255d 2023-08-04 jrmu (cond ((< num1 num2)
86 665c255d 2023-08-04 jrmu ((serializer1 (serializer2 exchange))
89 665c255d 2023-08-04 jrmu ((> num1 num2)
90 665c255d 2023-08-04 jrmu ((serializer2 (serializer1 exchange))
91 665c255d 2023-08-04 jrmu account1 account2))
92 665c255d 2023-08-04 jrmu (else (error "Identical accounts" num1 num2)))))
94 665c255d 2023-08-04 jrmu ;; Exercise 3.49. Give a scenario where the deadlock-avoidance mechanism described above does not work. (Hint: In the exchange problem, each process knows in advance which accounts it will need to get access to. Consider a situation where a process must get access to some shared resources before it can know which additional shared resources it will require.)
96 665c255d 2023-08-04 jrmu ;; Maybe you want to transfer to an account but you need to ask the account for which account to transfer to.
