SICP-Refresher-Chapter-3(4)

1
2

;; 完全是体力活，列出各种排列组合...
;; 就在这里列举了。

1
2
3

;; 121
;; 101
;; 100

1
2
3
4
5
6
7
8
9

;; without serialization
;; 1000000
;; 100
;; 1000
;; 10000
;; 100000

;; with serialization
;; 1000000

1
2
3
4
5
6

;; 并没有必要；
;; 第一，非串行地访问帐户过程并不会影响其他两个过程的结果；
;; 第二，可能存在一种担心，即非串行地访问帐户取到的值是不正确的，
;; 因为访问帐户可能处于其他并发过程的取值和修改值之间，
;; 访问帐户取到的值马上就无效了；
;; 这是不用担心的，因为可以这样说，访问帐户取值取的就是那一时刻的值。

1
2

;; 安全的；
;; 与原来的版本并无什么不同；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

;; 顺序运行交换过程
;; 10 20 30
;; 10 30 20
;; 20 10 30
;; 20 30 10
;; 30 10 20
;; 30 20 10

;; 使用本节第一个版本的帐户交换程序
;; 10 20 30
;; 40 10 10
;; 20 20 20
;; 30 30 0
;; 10 40 10
;; 0 30 30
;; 30 0 30
;; 10 10 40
;; 20 10 30
;; 30 20 10
;; 10 30 20
;; 30 10 20
;; 20 30 10

1
2
3
4
5
6
7
8

;; Louis 的说法是错的；

;; 帐户余额交换过程中必须先计算帐户差额，
;; 而这个差额计算过程是可以与其他对这两个帐户的操作并行进行的，
;; 导致计算出来的差额可能是错误的，所以需要串行化整个 exchange 过程；

;; 而转移款项 transfer 过程中对帐户的所有操作都受到串行化组的保护；
;; 不必担心最初的 exchange 中出现的问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

;; 当调用本节定义的 serialized-exchange 时，会出现死锁，

;; 串行化组里的并发过程运行 将卡在某个节点无法运行下去；
;; 比如，现在 exchange 过程在 serializer2 串行化组里；
;; 而 (serializer2 exchange) 过程在 serializer1 组里；
;; 当运行此 exchange 过程时，
;; (account 'withdraw) 与 (account 'deposit) 将返回两个被串行化的过程，
;; 分别属于串行化组 serializer1 和 serializer2，
;; exchange 过程内部的两个串行化过程必须等待同组的进程结束；
;; 而此时这两个组里都有过程作为进程在运行，
;; 即前面所说的 (serializer2 exchange) 和 exchange 本身;
;; 如此 exchange 将永远无法结束，这个调用将会死锁。

1
2
3
4

;; 如果没有企图使 test-and-set! 的操作原子化，
;; 两个并发进程就可以同时获取互斥元并进而运行下去，
;; 这是与以互斥元实现串行化的初衷相背的。
;; 画时序图是重复劳动，这里就不做了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

;; a

(define (make-semaphore n)
  (let ((mutex (make-mutex))
	(original-n n))
    (define (acquire)
      (mutex 'acquire)
      (if (> n 0)
	  (begin (set! n (- n 1))
		 (mutex 'release)
		 'ok)
	  (begin (mutex 'release)
		 (acquire))))
    (define (release)
      (if (< n original-n)
	  (begin (mutex 'acquire)
		 (set! n (+ n 1))
		 (mutex 'release)
		 'ok)))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
	     (acquire))
	    ((eq? m 'release)
	     (release))))
    the-semaphore))

;; b

(define (make-semaphore n)
  (let ((original-n n))
    (define (acquire)
      (if (test-and-set! n)
	  (acquire)
	  'ok))
    (define (release)
      (if (< n original-n)
	  (begin
	    (set! n (+ n 1))
	    'ok)))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
	     (acquire))
	    ((eq? m 'release)
	     (release))))
    the-semaphore))

(define (test-and-set! n)
  (if (= n 0)
      true
      (begin (set! n (- n 1))
	     false)))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

(define (make-account-and-serializer balance n)
  (define (withdraw amount)
    (if (>= balance amount)
	(begin (set! balance (- balance amount))
	       balance)
	"Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) withdraw)
	    ((eq? m 'deposit) deposit)
	    ((eq? m 'balance) balance)
	    ((eq? m 'serializer) balance-serializer)
	    ((eq? m 'label) n)
	    (else (error "Unknown request -- MAKE-ACCOUNT"
			 m))))
    dispatch))

(define (label acc)
  (acc 'label))

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
	(serializer2 (account2 'serializer))
	(n1 (label account1))
	(n2 (label account2)))
    (if (> n1 n2)
	((serializer2 (serializer1 exchage))
	 account1
	 account2)
	((serializer1 (serializer2 exchage)))
	account1
	account2)))

1
2
3
4
5
6
7
8
9

;; 竟然无法理解自己之前写的回答了...
;; 摘录一条别人的情形描述：
;; https://sicp.readthedocs.io/en/latest/chp3/49.html

;; 关联帐号的其中一种状况产生的死锁无法使用 练习 3.48 的机制来防止。

;; 假设 peter 和 mary 是两夫妇，他们各自拥有自己的帐号 peter-acc 和 mary-acc ，并且这两个帐号都将对方的帐号设置成了关联帐号，也即是，当 peter-acc 的余额不足以支付的时候，它会去提取 mary-acc 的余额；而当 mary-acc 的余额不足以支付的时候，它也回去提取 peter-acc 的余额。

;; 现在，考虑这样一种情况， peter 和 mary 分别在不同的地方消费，然后各自账户的余额都不足以支付订单，于是 peter-acc 尝试访问关联帐号 mary-acc ，而 mary-acc 也在同一时间访问 peter-acc ，因为两个帐号都已经被打开，而且两个帐号都试图访问关联帐号，这样就造成了一个死锁：除非 peter 或 mary 的其中一个主动退出账户，否则支付永远都无法完成。