[Back]

3.4 并发:时间是一个本质问题

3.38

可能值

45

35

50

40

如果并发的执行,还可以出现

110 80 55 30 60 90这六种情况

具体图略

3.39

可能出现的值会有

121 101

实际上a能够访问的值只有10和11,而b能访问的值只有10和100

由于a、b的运行串行性,答案只会是100+1和11*11

3.40

两个都是乘法,由于结合律的特殊性质

可能产生的值会有

x2 x3 x4 x5 x6这五种情况

如果加入了串行计算,就只会有

x6这一种情况了

这是加速并行运算的一种有效方式之一(结合律等价性)

3.41

如果一个人在和一个并发的取款操作一起查看余额,那么他的接下来取款就会发生无法取出足够钱的情况,但是注意的是,我们的并发系统是注意事务处理的,即对于任意一个请求,都得保证它不能知道其他请求的存在。这样并不会导致不正常,只会导致不愉快。

3.42

不安全。

这样的修改,本质上是组织了并发的存在。因为它会用已经创建好的串行去处理并发,而不是在并发的时候创建串行,这会使得一个时间只会有一个进程运行。

3.43

证明,并发的交换会在两个账户之间等价的读取差值进行转移,因此并不在外来的金额交换.

按序执行的操作是封闭的。

如果不使用外显的串行,那么在读取一个差值后可能会发生未转移完即与其他的账户通信的行为,然而即使如此,由于每个存取款的数量都是这个账户在某一时刻的状态,那么总数额就不会发生变化。

如果去除了存取款的串行化,那么单个账户的外来状态就无法统一,因而也就不封闭了。

3.44

Louis的担忧是没有道理的。

转移和交换之间的本质性问题在于,交换需要的差值也是依赖于局部的状态变量,而转移的数目则是人为指定的。只要我们在单个账户建立了串行化组,就不需要担心共享资源的问题。

或者形式化的一点讲,交换问题是一个A->B的映射,而转移问题应该是一个C->{A,B}的映射。

3.45

这个问题和3.42是一样的,本质上讲,这是那已经创建好的串行化组来使用。

如果并发的交换账户,那么串行化的2锁住了exchange的操作,而exchange里对2存款使用的却是同一个串行化组,这就造成了错误。因此我们每次都只能创建新的串行化组用于并发。

3.46

如果同时访问互斥元,那么在一个检查到这个为假的时候,还没来得及设为真,另一个进程就也访问到它为假,这样,两个进程都获取到了互斥元。

3.47

(define (make-signal-volume n)
    (let ((cell 0))
        (define (me m)
            (cond ((eq? m `acquire)
                    (if (test-and-set! cell)
                        (me `acquire)))
                  ((eq? m `release) (minus! cell))))
        (define (minus! a)
            (without-interrupt
                (lambda () (set! a (- a 1)))))
        (define (test-and-set! a)
            (without-interrupt
                (lambda () 
                    (if (= a n)
                        #t
                        (begin (set! a (+ a 1))
                        #f)))))
        me))

3.48

这个策略实际上就是在给进程指定一个进入串行的过程,保证了不会互相阻塞的情况。

(define (serialized-exchange acc-1 acc-2)
    (if (< (acc-1 'id) (acc-2 'id))
        (serialize-and-exchange acc-1 acc-2)
        (serialize-and-exchange acc-2 acc-1)))

(define (serialize-and-exchange smaller-id-account bigger-id-account)
    (let ((smaller-serializer (smaller-id-account 'serializer)))
        (let ((bigger-serializer (bigger-id-account 'serializer)))
            ((smaller-serializer (bigger-serializer exchange))
             smaller-id-account
             bigger-id-account))))

3.49

设想一个并发的修改堆(heap)的操作,然后两个并发的进程在搜索过程中分别锁死了两棵子树。

(修改,如果我们强行指定左子树高于右子树能解决这个问题)