1. 写在最前面

真正要做的作业,对神明都不要讲。必定如此,万般如此。

2. 并发:时刻是一个实质问题

引入赋值之后,有必要承认时刻在所用的核算模型中的方位。在引入赋值之前,一切程序都没有时刻问题,任何具有某个值的表达式,将总是具有这个值。

引入赋值之后带来的问题,以 3.1.1 节中模仿从银行账户提款并回来最终余额为例:

(withdraw 25)
75
(withdraw 25)
50

连续对同一个表达式求值,却发生了不同的值。这种行为的呈现便是由于:赋值句子的履行描绘出有关值变化的时刻,对一个表达式的求值成果不光依赖于该表达式自身,还依赖于求值发生咋这些时刻之前仍是之后。

现实世界里的目标并不是一次一个地次序变化,与此相反,它们总是发并地活动,一切东西一同活动。

注:能够经过将模型安排为一些具有彼此分离的部分状况目标,使做出的程序愈加模块化。

将核算模型划分为一些能各自独立地并发演化的部分

2.1 并发体系中时刻的性质

作业次序的非确认性,或许对并发体系的规划提出了严重的问题。举例证明,假定由 Peter 和 Paul 进行取款被完成为两个独立的进程,它们同享同一个变量 balance,这两个核算进程都由如下进程描述:

(define (withdraw amount)
  (if (>= balance amount)
    (begin (set! balance (- balance amount))
       balance)
    "Insufficent funds"))

上述表达式包括三个进程:

  • 获得变量 balance 的值
  • 核算出新的余额
  • 将变量 balance 设置为新值

假如 Peter 和 Paul 在提款进程中并发履行这一句子,那么这两次提款在拜访 balance 和将它设置为新值的动作就或许交错。

下图的时序图勾画了一个作业次序,其中的 balance 在开始时是 100,Peter 取走了 10,Paul 取走了 25,然后 balance 最终的值却是 75。

《计算机构造与解释》读书笔记(4)
上述实例表现出的一般性现象是:几个进程有或许同享同一个状况变量。使作业变得愈加复杂的原因,便是多个进程有或许一起试图去操作这种同享状况。

2.1.1 并发程序的正确行为

在写那些运用 set! 的程序时有必要小心,由于一个核算的成果依赖于其中的各个赋值发生的次序。关于并发进程,关于赋值就需要特别小心,由于无法操控其他进程所做赋值的呈现次序。 假如几个修改或许并发呈现,有必要采用某些方法,以设法确保体系的行为是正确的。

关于并发的一种或许束缚方法是规定,修改恣意同享状况变量的两个操作都不允许一起发生。

注:这是一个十分严峻的要求,以分布式银行体系举例,这就要求体系规划者确保一起呈现的只能有一个买卖,这样做或许过于低效,也太保存了。

关于并发的另一种不那么严峻的束缚方法是,确保并发体系发生的成果与各个进程依照某种方法次序运转发生出的成果彻底相同。这一要求中包括两个重要方面:

  • 它并没有要求各个进程实践上次序地运转,而只是要求它们发生的成果与假定它们次序运转所发生的成果相同。
  • 一个并发程序彻底或许发生多于一个「正确的」成果,只要求其成果与依照某种方法次序化的成果相同。

注:参考 raft 算法,节点间数据的同步

关于并发程序的正确履行,还能够提出一些更弱的要求。一个模仿扩缩进程的程序能够由一大批进程组成,每个进程代表空间中很小的一点体积,它们并发地更新自己的值。这里的每个进程都反复将自己的值更新为自己的原值和相邻进程的值的平均值。不管有关的操作按什么次序履行,这种算法都能收敛到正确的解,因而也就不需要对同享变量的并发运用提出任何束缚了

2.2 操控并发的机制

2.2.1 对同享变量的串行拜访

串行化:使进程能够并发地履行,可是其中也有一些进程不能并发地履行。

串行化的比如:创立一些不同的进程调集,并且确保在每个时刻,在任何一个串行化调集里至多只要一个进程的履行。假如某个调集里有进程正在履行,而另一进程妄图履行这个调集里的任何进程时,它就有必要等候到前一进程的履行完毕。

2.2.2 Schema 里的串行化

为了使上述「对同享变量的串行拜访」机制愈加具象化,假定扩大本书示例中所用的 Scheme 言语,参加一个称为 parallel-execute 的进程:

(parallel-execute <p1> <p2> ... <pk>)

这里的的每个

有必要是一个无参进程,parallel-execute 为每个

创立一个独立的进程,该进程将运用

以下面的比如为例:

(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
          (lambda () (set! x (+ x 1))))

假定 P1 要把 x 设置为 x * x,P2 要把 x 设置为 + x 1,在上述的比如履行过之后,x 将具有以下 5 种值之一:

101:P1 将 x 设置为 100,然后 P2 将 x 的值添加到 101

121:P2 将 x 的值添加到 11,然后 P1 将 x 设置为 x * x

110:P2 将 x 从 10 修改为 11 的动作呈现在 P1 两次拜访 x 的值之间,这两次拜访是为了求值表达式 (* x x)

11: P2 拜访 x,然后 P1 将 x 设置为 100,然后 P2 又设置 x

100:P1 拜访 x (两次),然后 P2 将 x 设置为 11,然后 P1 又设置 x

能够用串行化的进程给此处的并发性添加一些束缚,经过串行化组完成这种束缚,假定结构串行化组的方法为调用 make-serializer。一个串行化组以一个进程为参数,它回来的串行化进程具有与原进程相同的行为方法。

(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () (set! x (* x x))))
          (s (lambda () (set! x (+ x 1)))))

经过此种方法只或许发生 x 的两种或许性 101 和 121,其他的几种或许性都被清除了,由于 P1 和 P2 的履行不会交错进行。

2.2.3 运用多重同享资源的复杂性

假如只存在一个同享资源(例如一个银行账户),串行化的运用问题是相对比较简单的。可是假如存在多项同享资源,并发程序规划就或许变得十分难以掌握。

为了展示或许呈现的一种困难,假定操作为交流两个账户的余额。

  • 首先拜访每个账户,以确认其中的余额
  • 核算出两个余额之间的差额
  • 从一个账户里减去这一差额,然后将它存入另一个账户
(define (exchange account1 account2)
  (let ((difference (- (account1 `balance)
             (account2 `balance))))
    ((account1 `withdraw) difference)
    ((account2 `deposit)  difference))
  • 只要一个进程试图做这种交流,这一进程能够作业得很好。
  • 涉及到多个进程操作这种交流,就会带来「多重同享资源的复杂性」问题

假定 Peter 和 Paul 都能拜访 a1 、a2 和 a3 账户,在 Peter 要交流 a1 和 a2 时,正好 Paul 也并发地要求交流 a1 和 a3。

假如呈现 Peter 算出 a1 和 a2 的余额差值,可是 Paul 却或许在 Peter 完结交流之前改变了 a1 的余额。

注:为了得到正确的行为,就有必要重新规划 exchange 进程,让它在完结整个交流期间锁住关于账户的任何其他拜访。

2.2.4 串行化完成

能够用一种更根本的称为「互斥元(mutex)」的同步机制来完成串行化。互斥元是一种目标,假定它提供两个操作:

  • 能够被获取(acquired)
  • 能够被开释(released)

一旦某个互斥元被获取,关于这个互斥元的任何其他获取操作都有必要比及该互斥元被开释后进行操作。在实践完成运用中,给定一个进程 P,串行化组将回来一个进程,该进程获取相应互斥元,之后运转 P,最终开释互斥元,此种操作即可确保串行化性质。

2.2.5 死锁

在账户交互问题里还存在一个麻烦,假定 Peter 妄图去交互账户 a1 和 a2,一起 Paul 并发地妄图去交互 a2 和 a1。

  • 假定 Peter 获取了 a1 的互斥元,等候 a2 的互斥元
  • 假定 Paul 获取了 a2 的互斥元,等候 a1 的互斥元

此种情况下,就会进入「死锁」状况。

注:关于多种同享资源的并发拜访的体系里,总是存在着死锁的危险。

避免死锁的一种方法,是首先给每个账户确认一个仅有的标识编号,使每个进程总是首先设法进入保护具有较低标识编号的账户进程。

注:此次笔者了解便是锁的粒度变的更大了,能够一起将 a1 和 a2 的账户锁定,在操作期。

2.2.6 并发性、时刻和通讯

在并发体系的程序规划中,关于以下两个问题,已经有明晰的描述:

  • 为什么需要去操控不同进程拜访同享变量作业发生的次序?
  • 假如运用串行化去操控并发?

可是,从一种更根本的观念来看,「同享状况」终究意味着什么,这件事常常并不清楚。

「同享变量」的各个方面问题也呈现在大型的分布式体系里。例如,设想一个分布式的银行体系,其中的各个分支银行维护着银行余额的部分值,并且周期性地将这些值与其他分支所维护的值彼此比较。在这样的体系里,「账户余额」的值或许是不确认的。

假定 Peter 在他与 Paul 公用的一个账户里存入了一些钱,什么时分才能说账户的余额已经改变了:

  • 本地银行修改余额之后
  • 本地银行将余额同步之后

假如 Paul 从另一分支银行拜访这个账户,怎么在这一银行体系里对这种行为的「正确性」确认合理的束缚?

在此处,能考虑的或许便是坚持 Peter 和 Paul 的各自行为,以及确保刚刚完结同步时刻的账户「状况」正确性。

这里的根本现象是不同进程之间的同步,建立起同享状况,或迫使进程之间通讯所发生的作业依照某种特定的次序运转 。 从实质上看,在并发操控中,任何时刻概念都必然与通讯有内在的密切联系。

注:在处理时刻和状况时,在核算模型领域所遭遇的复杂性,事实上,或许便是物理世界中最根本的复杂性的一种反映。

3. 碎碎念

原本想要把第三章啃完的,可是这本书,看过的都知道有多不流畅难明,那就慢一点吧,「走的慢一点,走的稳一点,走的久一点」

  • 不再走出舒适圈,一个人老去的标志,绝不是老成稳重,默不做声;而是不肯再测验,不肯再容许自己置身不熟悉的地步,当你停止学习,固步自封,那么你已经向平庸迈进了一大步。
  • 沉溺短期快感,不再做长期投入,玩游戏、看小说,这是适应人道,由于它们有及时反馈,你能够短期内获得快感。
  • 你现在状况不对,你就得改,你不能由于一件作业影响你太久,太耽误事了,本钱过高,太不划算了。

注:你是什么时分发现时刻竟然不知不觉的已经从指缝中流走的?

在突然间意识到自己好像没有了刚刚作业时的那种奋斗向上的感觉时。