sicp03-3

都是无参过程，parallel-execute 为每个

建立一个独 立进程，这些进程并发运行 程序设计技术和方法 裘宗燕，2009-2010 /19 并发控制：串行控制器 (define x 10) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (+ x 1)))) ■ 可能行为（5种）： ‰ 先乘后加得 101；先加后乘得 121 ‰ x 加 1 出现在 (* x x) 两次访问 x 之间得 110 ‰ 加出现在乘和赋值之间得 100；乘出现在求和和赋值之间得 11 ■ 串行控制器可限制并发过程的行为。设 make-serializer 创建串行控制 器，以一个过程为参数返回同样行为的过程（参数与原过程一样），但 保证其执行被串行化 ■ 下面程序只能产生值 101 或 121（消除了不合适的并行） (define x 10) (define s (make-serializer)) (parallel-execute (s (lambda () (set! x (* x x)))) (s (lambda () (set! x (+ x 1))))) 多个可能结果 非确定性 程序设计技术和方法 裘宗燕，2009-2010 /20 并发控制：串行化 ■ make-account 的串行化版本： (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)) ■ 这个实现中不会出现两个进程同时取款或存款，避免了前面说的错误。 此外，每个账户用一个串行化控制器，不同账户互不干扰 程序设计技术和方法 裘宗燕，2009-2010 /21 多重资源带来的复杂性 „ 串行化控制器是一种有用抽象，用于隔离并发程序的复杂性。如果并发 程序中只有一种共享资源（如一个共享变量），问题已可以处理。如果 存在多项共享资源（常见），程序的行为将更难控制 „ 例：假设要交换两个账户的余额，用下面过程描述这一操作： (define (exchange account1 account2) (let ((difference (- (account1 'balance) (account2 'balance)))) ((account1 'withdraw) difference) ((account2 'deposit) difference))) „ 只有一个进程去交换账户余额时不会出问题。但如果 Peter 要交换账户 a1 和 a2 的余额，而 Paul 要交换 a2 和 a3 的余额 ‰ 设每个账户已正确地串行化 ‰ 若 Peter 算出 a1 和 a2 的差之后 Paul 交换了 a2 和 a3，程序就会 产生不正确行为（可找到许多产生不正确行为的动作交错序列，什 么是“不正确”还需严格定义） 程序设计技术和方法 裘宗燕，2009-2010 /22 多重资源带来的复杂性 „ 可用两个串行控制器把 exchange 串行化，并重新安排对串行控制器的访问。 下面做法把串行化控制器暴露出来，破坏了账户对象原有的模块性。（其他方 法也会有问题，请自己设计并 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ） „ 下面账户实现提供一个串行控制器，可通过消息获取，以便在账户之外实现对 该账户的余额的保护： (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)) 暴露内部的串行控制器，增加了使用的复杂性和不安全性 程序设计技术和方法 裘宗燕，2009-2010 /23 多重资源带来的复杂性 „ 安全使用这种账户对象是用户的责任，程序要按照复杂的规矩（协议） 去使用才能保证正确的串行化管理。例如，新存款过程写成： (define (deposit account amount) (let ((s (account 'serializer)) (d (account 'deposit))) ((s d) amount))) „ 导出串行控制器可支持灵活的串行化控制。如 exchange 重写为： (define (serialized-exchange account1 account2) (let ((serializer1 (account1 'serializer)) (serializer2 (account2 'serializer))) ((serializer1 (serializer2 exchange)) account1 account2))) exchange 就是前面定义的过程 „ 可以把这些过程再包装起来，但定义更复杂操作时又会遇到类似问题 „ 请阅读这几小节的练习，考虑练习中提出的问题 程序设计技术和方法 裘宗燕，2009-2010 /24 串行化控制器的实现 „ 串行控制器可基于更基本的互斥元数据抽象实现 ‰ 互斥元：一种抽象，可被获取，使用后释放 ‰ 如果某互斥元已被获取，企图获取这一互斥元的其他操作需要等待 到该互斥元被释放（任何时候至多有一个进程获取它） ‰ 设 make-mutex 创建互斥元，获取的方式是给互斥元送 acquire 消息，释放的方式是给它送 release 消息 „ 每个串行控制器里需要一个局部的互斥元，其实现是： (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))) „ 返回串行化控制器 „ 它以 p 为参数，返回加了串 行化控制的同一个过程 „ 每次调用时先获取，而后执 行，最后释放 程序设计技术和方法 裘宗燕，2009-2010 /25 互斥元的实现 „ make-mutex生成互斥元对象，它有一个内部状态变量 cell，其初始值 为 false。接到 acquire 消息时试图将 cell 设为 true (define (make-mutex) (let ((cell (list false))) (define (the-mutex m) (cond ((eq? m 'acquire) (if (test-and-set! cell) (the-mutex 'acquire))) ;重试 ((eq? m 'release) (set-car! cell false)))) the-mutex)) „ test-and-set! 是个特殊操作，它检查参数的 car 并返回其值，如果参 数的 car 为假就在返回值之前将其设为真： (define (test-and-set! cell) (if (car cell) true (begin (set-car! cell true) false))) ■ 这个实现不行。test-and-set! 是实 现并发控制的核心操作，必须以原 子操作的方式执行，不能中断 ■ 没有这种保证，互斥元也将失效 程序设计技术和方法 裘宗燕，2009-2010 /26 互斥元 „ test-and-set! 需要特殊支持。可以是一条特殊硬件指令，也可能是系统 软件提供的一个专门过程。具体实现依赖于硬件 ‰ 只有一个处理器的机器里并发进程以轮换方式执行，每个可执行进 程安排一段执行时间，而后系统将控制转给其他可执行进程。在这 种环境下 test-and-set! 执行中必须禁止进程切换 ‰ 对多处理器机器，必须有硬件支持的专门指令 ‰ 人们开发了这一指令的许多变形，它们都能支持基本的互斥操作 程序设计技术和方法 裘宗燕，2009-2010 /27 死锁 „ 即使有串行控制器，serialized-exchange 还可能出麻烦： 设 Peter 要交换账户 a1 和 a2，同时 Paul 也想交换 a2 和 a1。假定 Peter 进程已进入保护 a1 的串行化过程，同时 Paul 也进入保护 a2 的串行化过程。这时 Peter 将等待进入保护 a2 的过程，而 Paul 也等 待进入保护 a1 的过程。无穷等待！ „ 两个以上进程由于相互等待他方释放资源而无法继续的情况称为死锁 „ 使用多重资源的并发系统里总存在死锁的可能。死锁是并发系统里的一 种不可容忍的动态错误，常见系统的许多死机现象实际上是死锁 „ 人们开发了许多避免死锁的技术，以及许多检查死锁的技术 „ 避免死锁的一种技术（对本问题通用）是为每个账户确定一个唯一标识 号。对当前这个问题，需要修改serialized-exchange，使调用它的进 程总先获取编号小的账户的保护过程 „ 其他死锁可能需要更复杂的技术，不存在一般的死锁控制技术 程序设计技术和方法 裘宗燕，2009-2010 /28 并发性，时间和通信 „ 并发编程中需要控制访问共享变量的顺序，串行化控制器是一种控制工 具。实际上并发中什么是“共享状态”的问题常是不清楚的 „ test-and-set! 等机制要求进程能在任意时刻检查一个全局共享 标志 禁止坐卧标志下载饮用水保护区标志下载桥隧标志图下载上坡路安全标志下载地理标志专用标志下载 。新 型高速处理器采用了许多优化技术，如（多级）流水线和缓存等，使串 行化技术越来越不适用了（对效率影响太大） „ 在分布式系统里，共享变量在整个系统的一致性是很大问题 „ 如在分布式银行系统里，一个账户可能在多个分行有当地版本，这些版 本需要定期或不定期地同步。这种情况下账户余额就变成不确定的。假 如 Peter 和 Paul 分别向同一账户存款，账户在某个时刻有多少钱是不 清楚的（存入时，还是下次同步时，还是？）。不断存取钱的过程中， 账户余额也具有非确定性 „ 状态、并发和共享信息的问题总是与时间密切相关的，而且时很难控制 的。这些都使人回忆起函数式编程的美好时光 程序设计技术和方法 裘宗燕，2009-2010 /29 总结 „ 有局部状态的变量很有用，但赋值破坏了引用透明性，使语言的语义再 也不可能简洁清晰，还带来许多不易解决的问题 „ 赋值和状态改变背后的问题是时间依赖性：赋值改变变量的状态，从而 改变依赖于这些变量的表达式，改变计算的行为 „ 并发和赋值的相互作用产生的效果更难把握。无限制的并发可能带来各 种问题，可能产生不希望的效果。解决问题的办法是对并发加以控制， 不允许出现不希望的并发 „ 串行化控制器可以解决一项资源的管理问题，它需要基本并发原语的支 持，如 test-and-set! 指令。在更复杂的环境里需要硬件的支持 „ 多项资源的竞争，以及由此可能引起的死锁，都是并发程序设计中不容 易解决的问题 „ 人们正在研究各种各样的并发编程模型、并发程序的检查和验证技术、 并发程序开发的支持环境等等。并发问题在今后很长时间内一直会是计 算机领域中的最大挑战