SICP CONCLUSION
目录
1. 构造过程抽象
2. 构造数据抽象
3. 模块化、对象和状态
4. 元语言抽象
5. 寄存器机器里的计算
Chapter 3
- 模块化、对象和状态
练习答案
并发：时间是一个本质问题
限制并行进程之间的交错情况
对共享变量的串行访问
(parallel-execute <p1><p2><p3>) ;;并发的过程集
;;加入串行化就可以保证独立<p>的运行
(define s (make-serializer))
(parallel-execute <s p1> <s p2>)
;;存取款
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((protected (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw) (protected withdraw))
((eq? m 'deposit) (protected deposit))
((eq? m 'balance) balance)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
- 使用多重共享资源的复杂性
如果希望交换两个账户的余额就需要对整个过程进行串行化
(define (make-account-and-serializer balance)
(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)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
(define (deposit account amount)
(let ((s (account 'serializer))
(d (account 'deposit)))
((s d) amount)))
(define (serialized-exchange account1 account2)
(let ((serializer1 (account1 'serializer))
(serializer2 (account2 'serializer)))
((serializer1 (serializer2 exchange))
account1
account2)))
串行化的实现
(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(define (serialized-p . args)
(mutex 'acquire)
(let ((val (apply p args)))
(mutex 'release)
val))
serialized-p)))
互斥元的实现
(define (make-mutex)
(let ((cell (list false)))
(define (the-mutex m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell) ;;如果mutex已经被获取了那么就持续获取这个互斥元直到它被释放
(the-mutex 'acquire)))
((eq? m 'release) (clear! cell))))
the-mutex))
(define (clear! cell)
(set-car! cell false))
(define (test-and-set! cell) ;;必须支持原子操作才可能正确
(if (car cell)
true
(begin (set-car! cell true)
false)))
死锁
避免死锁
在进行串行化时，为每个进程都安排一个唯一标识，使每个进程都优先进去较低标识标号的账户。这一就不会产生一个交错的冲突，但是还是存在一些情况，需要更复杂的技术