T01a Tutorial 1(上):两张时钟图,一步不漏地手算
Lamport 和向量时钟手算的三处失分点,以及那个没标字母的黑点。
一句话版
这一半只考一件事:给图机械算时钟。靠熟练度,不靠灵感。
先认识这几个词
读之前最好先懂逻辑时钟:Lamport 时钟见 L02b-2,向量时钟见 L02b-3。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 内部事件 | local event | 进程自己做的一件事,不收也不发消息 |
| 发送 / 接收事件 | send / receive event | 发出或收到一条消息,各算一个事件 |
| Lamport 时钟 | Lamport clock | 每个进程一个整数计数器,用来给事件排先后 |
| 向量时钟 | vector clock | 每个进程记一串数,第 k 个数是它知道的 Pₖ 已发生的事件数 |
| e → e′ / e ∥ e′ | 读「e 先于 e′」/「e 与 e′ 并发」 | → 是 happens-before,有因果先后;∥ 是谁也不影响谁 |
题目地图
整份 tutorial 五页题,三种题型,前三讲各考一遍。本页拆两张时钟图,选择题和广播判定题在 T01b。
| 题 | 考什么 | 主要失分点 |
|---|---|---|
| Figure 1 | Lamport 时钟手算,事件 a 到 z | max 的另一边取错;接收事件忘了 +1 |
| Figure 2 | 向量时钟手算,同样 a 到 z | 只更新自己那一维,忘了逐分量 max |
时钟题逐事件列值,图里有没标字母的事件,先在答卷上写一句假设。
概念卡
1. Lamport 三条规则与「本地上一个事件」(Lamport Clock)
人话定义:它用一个数给每个事件编号,让有因果关系的事件编号一定变大。本地事件和发送事件加 1,接收事件先和消息戳取 max 再加 1。
例子:规则只有三条。计数器初值 0。本地或发送事件 C ← C + 1,发送时把这个值附在消息上。接收事件 C ← max(C, 消息戳) + 1。
max 里的 C 指的是本进程上一个事件的时间戳,这是全题唯一的坑。Figure 1 里 f 收到时间戳 6 的消息,P1 上一个事件 e = 7。本地值比消息戳大,max 取本地:
f = max(7, 6) + 1 = 8
常见误解
把接收事件算成「消息戳 + 1」→ 本地值更大时会给出完全不同的数。改卷时区分度最高的三个事件(i、s、t)全是这种情形。
另一处是接收事件忘了最后那个 +1,直接把 max 的结果当时间戳。
回讲义:L02b-2 Lamport 时钟:给每个事件发一个号
2. 向量时钟三条规则与因果判据(Vector Clock)
人话定义:它能反过来从时间戳判断两个事件有没有因果关系,Lamport 时钟做不到。规则和 Lamport 几乎一样,差别只有两处:max 逐分量取,加 1 只加自己那一维。
例子:进程 Pᵢ 维护长度为 n 的向量,初值全 0。本地或发送事件 V[i] ← V[i] + 1,之后再把整个向量附在消息上。接收事件先对所有 k 做 V[k] ← max(V[k], V′[k]),再 V[i] ← V[i] + 1。意思是先把对方知道的历史并进来,再给自己记一笔。
第 k 维的含义是「本进程当前所知的 Pₖ 已发生的事件数」。判因果:逐维 ≤ 且至少一维严格 < 就是 happens-before;两个方向都不成立就是并发。
常见误解
接收时只给自己那一维加 1、跳过逐分量 max → 这是两个高频错误里的第一个,第二个是 max 做完忘了加 1。
发送端也有一处:附在消息上的是自增之后的向量,先发再加会让接收方少算一格。
回讲义:L02b-3 向量时钟:每台机器记一位,就能判出并发
3. 那个没标字母的黑点(Unlabeled Event)
人话定义:两张图的 P3 上各有一个没有字母的黑点。按分布式系统的惯例,它是一个内部事件,要占一个计数。
例子:下面的答案默认把它算作内部事件。不计它的话,Figure 1 里 P3 从 q 起整体减 1,连带 P4 的 y、z 也变;Figure 2 只有 r、s 两行变,因为 q 到 r 之间没有跨进程消息发出。
常见误解
以为黑点没字母就可以跳过 → 计不计它会改动后面一串数字。两种算法都可能被接受,但评分口径要向教师确认,答卷上先写一句假设。
回讲义:L02b-1 事件、割与 happens-before:没有统一的表,怎么排先后
逐题拆解
Figure 1(Lamport 时钟)
答案如下,方括号那格是 P3 上未标注的黑点,按内部事件计:
- P1 = 1, 2, 3, 6, 7, 8
- P2 = 1, 2, 3, 4, 5, 6, 8
- P3 = 1, 2, 3, [4], 5, 6, 7, 8, 9
- P4 = 1, 2, 3, 6, 7
最容易错的五个:
- d = max(3, 5) + 1 = 6(收到 k 的 5,本地上一个是 c = 3)
- m = max(6, 7) + 1 = 8,f = max(7, 6) + 1 = 8
- y = max(3, 5) + 1 = 6,u = max(8, 7) + 1 = 9
另外三个本地值大于消息戳的:i = max(2, 1) + 1 = 3,s = max(6, 3) + 1 = 7,t = max(7, 3) + 1 = 8。
这张图还顺手给出了 Lamport 的局限:c = 3 和 p = 3 时间戳相同,却毫无因果关系;f = 8 和 m = 8 也一样。不同事件的 Lamport 时间戳相等可以推出并发,因为任一方向的因果都会要求严格增大。
有序则不能反推因果,单向蕴含只有 e → e′ ⟹ C(e) < C(e′) 这一个方向。这正是下一题换向量时钟的理由。
一步一步看
目标:分五批算出 Figure 1 每个事件的 Lamport 值,重点看接收时 max 什么时候取本地值。
图里事件按时钟值排横坐标,只是示意。每一步只算「所需消息已经到了」的事件,空心点是还没算的。
-
先算不收消息的事件:P1 的 a、b、c,P2 的 g,P3 的 n,P4 的 v、w、x,各自在上一个值上 +1。
-
P2 收到 a、n、b:
h = max(1, 1) + 1 = 2,i = max(2, 1) + 1 = 3,j = max(3, 2) + 1 = 4,之后 k = 5,l = 6。P3 收到 v、g:o = 2,p = 3,黑点 = 4,q = 5。 -
k 和 q 的值送达:
d = max(3, 5) + 1 = 6,e = 7;y = max(3, 5) + 1 = 6,z = 7。 -
P3 依次收 w、c、x:
r = max(5, 2) + 1 = 6,s = max(6, 3) + 1 = 7,t = max(7, 3) + 1 = 8。三次都取本地值。 -
最后三个接收事件:
f = max(7, 6) + 1 = 8,m = max(6, 7) + 1 = 8,u = max(8, 7) + 1 = 9。全图算完。
Figure 2(向量时钟)
关键值:c = (3, 4, 1, 0),k = (1, 6, 6, 4),p = (1, 1, 5, 4),r = (4, 4, 8, 4),s = (4, 4, 9, 7),黑点 = (1, 1, 7, 4)。k 的第 3、4 维一下子跳到 6 和 4,说明那条消息链把 P3、P4 的历史整段带了过来。
因果判断题拿这张图出。c = (3, 4, 1, 0) 与 p = (1, 1, 5, 4) 互不包含,c ∥ p 并发。a = (1, 0, 0, 0) 与 s 每一维都 ≤ 且有严格小于,a → s,图里确实存在 a → n → … → r → s 这条链。
一步一步看
目标:分五批算出 Figure 2 每个事件的向量,看接收时逐维 max 怎样把别人的历史带进来。
同样按时间先后分五批算,每个事件先逐维取 max(只有接收事件需要),再给自己那一维 +1。
-
先算发送事件:a =
(1, 0, 0, 0),b =(2, 0, 0, 0),f =(0, 1, 0, 0),l =(0, 0, 1, 0),t =(0, 0, 0, 1),u =(0, 0, 0, 2)。 -
g 收 l:逐维 max 得
(0, 1, 1, 0),第 2 维 +1 得(0, 2, 1, 0)。h、i、j 依次加到(0, 5, 1, 0)。v 收 f 得(0, 1, 0, 3),w =(0, 1, 0, 4)。 -
P3 依次收 t、a、u、w:m =
(0, 0, 2, 1),n =(1, 0, 3, 1),o =(1, 0, 4, 2),p =(1, 1, 5, 4)。之后 q =(1, 1, 6, 4),黑点 =(1, 1, 7, 4)。 -
P1 收 i、j:c =
(3, 4, 1, 0),d =(4, 4, 1, 0),e =(5, 5, 1, 0)。P4 收 h、b:x =(0, 3, 1, 5),y =(2, 3, 1, 6),z =(2, 3, 1, 7)。 -
最后三个接收事件:k 收 q,
max((0, 5, 1, 0), (1, 1, 6, 4))后第 2 维 +1,得(1, 6, 6, 4)。r 收 d 得(4, 4, 8, 4),s 收 z 得(4, 4, 9, 7)。
课件里的坑
- [课件留白] P3 的未标注黑点是否计作内部事件需注明假设;评分口径应向教师确认,不能保证哪种写法不扣分(p.1、p.3)。
- [课件留白] 不计那个黑点时的差异要能立刻说出:Figure 1 里 P3 从 q 起整体减 1(q = 4 … u = 8),连带 y = 5、z = 6,P1 与 P2 不受影响;Figure 2 里只有 r = (4, 4, 7, 4) 和 s = (4, 4, 8, 7) 两行变,因为 q 到 r 之间没有跨进程消息发出(p.1、p.3)。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写三条:Lamport 的接收规则、向量时钟的接收两步、因果判据。再把下面的「变式题」算一遍。最后回查两处最容易错的地方:max 的另一边取成了消息戳、逐分量 max 之后忘了给自己加 1。三步做完再往下看答案。
必背
- Lamport 接收事件:C ← max(本地上一个事件, 消息戳) + 1,max 的另一边是本地上一个事件,不是本进程初值;本地事件与发送事件只做 +1。
- 向量时钟接收事件先逐分量 max、再只给自己那一维 +1,两步都不能省;发送时先自增再把整个向量附在消息上。
- 向量时钟判因果:逐维 ≤ 且至少一维严格 < 即 happens-before,互不包含即并发;不同事件的 Lamport 戳相等可判并发;戳较小却不能反推因果。
- 图里没标字母的黑点默认按内部事件计一格,答卷上先写一句假设。
- 不计 P3 那个黑点时:Figure 1 里 P3 从 q 起整体减 1,连带 y = 5、z = 6;Figure 2 只有 r、s 两行变。
完整例题
把 Figure 2 里最长的那条线(P3,从 l 一路到 s)完整推一遍,向量按 (P1, P2, P3, P4) 排,初值全 0。这条线上有五个接收事件,正好把两个高频错误都踩一遍。
- l(本地):只给第 3 维加 1 → (0, 0, 1, 0)。它随后被发往 P2,附带的就是这个向量。
- m(收 t 的 (0, 0, 0, 1)):本地上一个是 l = (0, 0, 1, 0),逐分量 max → (0, 0, 1, 1),第 3 维加 1 → (0, 0, 2, 1)。
- n(收 a 的 (1, 0, 0, 0)):max((0,0,2,1), (1,0,0,0)) = (1, 0, 2, 1),加 1 → (1, 0, 3, 1)。
- o(收 u 的 (0, 0, 0, 2)):max → (1, 0, 3, 2),加 1 → (1, 0, 4, 2)。
- p(收 w 的 (0, 1, 0, 4)):max((1,0,4,2), (0,1,0,4)) = (1, 1, 4, 4),加 1 → (1, 1, 5, 4)。四维里有三维同时被推高,这是典型的「消息把别人的历史带过来」。
- q(本地)→ (1, 1, 6, 4);黑点(按内部事件计)→ (1, 1, 7, 4)。
- r(收 d 的 (4, 4, 1, 0)):本地上一个是黑点 (1, 1, 7, 4),max → (4, 4, 7, 4),加 1 → (4, 4, 8, 4)。注意第 3、4 维走的是本地值,第 1、2 维走的是消息值。
- s(收 z 的 (2, 3, 1, 7)):max((4,4,8,4), (2,3,1,7)) = (4, 4, 8, 7),加 1 → (4, 4, 9, 7)。
自检:s 是这条线的末尾,它的第 1 维 4 表示该事件已获知的 P1 事件数,第 4 维 7 表示已获知的 P4 事件数,不是全知的全局实时计数——数一遍图上的黑点,对得上就说明中间没漏步。若不计那个未标注黑点,只有 r 和 s 两行变成 (4, 4, 7, 4) 与 (4, 4, 8, 7),前面全不动,因为 q 到 r 之间没有任何跨进程消息发出。
变式题(先自己做)
(自编情境)三个进程,向量按 (P1, P2, P3) 排,初值全 0。事件序列:P1 上先有本地事件 a₁,再发消息 m 给 P3(发送事件 a₂);P2 上先有本地事件 b₁,再发消息 m′ 给 P3(发送事件 b₂);P3 上先有本地事件 c₁,然后先收到 m′(事件 c₂)、再收到 m(事件 c₃),最后回发一条给 P1(发送事件 c₄);P1 收到它,记作 a₃。
(1) 写出全部九个事件的向量时钟。(2) a₁ 与 b₁ 是并发还是有因果关系?(3) 若 P3 上在 c₁ 之前还有一个未标注黑点,哪些值会变、变成多少?
提示
发送事件也要先给自己那一维加 1,附在消息上的是加完之后的值。c₄ 带走的向量和 c₃ 的不一样。第 (3) 问不必重算,只需想清楚「P3 那一维整体后移一格」会波及到谁——被 P3 发出去的消息带到哪,哪里就会变。
参考答案与自检(非官方评分标准)
自检要点:① 接收事件先逐分量 max 再只给自己加 1;② 发送事件附带的是自增之后的向量;③ 并发的判据是两个方向的 ≤ 都不成立,不能只看某一维。
(1) a₁ = (1, 0, 0);a₂ = (2, 0, 0),m 带 (2, 0, 0)。b₁ = (0, 1, 0);b₂ = (0, 2, 0),m′ 带 (0, 2, 0)。c₁ = (0, 0, 1);c₂ = max((0,0,1), (0,2,0)) + 第 3 维加 1 = (0, 2, 2);c₃ = max((0,2,2), (2,0,0)) + 加 1 = (2, 2, 3);c₄ = (2, 2, 4),带走的就是这个值。a₃ = max((2,0,0), (2,2,4)) + 第 1 维加 1 = (3, 2, 4)。
(2) 并发,a₁ ∥ b₁。a₁ = (1, 0, 0) 的第 1 维大,b₁ = (0, 1, 0) 的第 2 维大,互不包含,两个方向的 ≤ 都不成立。
(3) 黑点 = (0, 0, 1) 之后,P3 那一维整体后移一格:c₁ = (0, 0, 2),c₂ = (0, 2, 3),c₃ = (2, 2, 4),c₄ = (2, 2, 5)。P1 的 a₃ 因为收了 c₄ 也跟着变成 (3, 2, 5)。a₁、a₂ 与 P2 的两个事件全不变——P3 的变化只能通过它发出的消息传播出去。
闪卡自测
1. 写出 Lamport 接收事件的公式,指出 max 的两个操作数分别是什么。
C ← max(C, 消息时间戳) + 1。其中 C 是本进程上一个事件的时间戳,不是初值也不是消息戳。Figure 1 里 f = max(7, 6) + 1 = 8 就是本地值更大的情形(p.1)。
2. Figure 1 里 d 收到 k(时间戳 5),P1 上一个事件是 c = 3。d 是多少?
d = max(3, 5) + 1 = 6。不是 5 + 1 碰巧对,也不是 3 + 1(p.1)。
3. Figure 1 里 c 和 p 的 Lamport 戳都是 3,说明什么?
两者并发、毫无因果关系。不同事件的戳相等可以推出并发,因为有因果就一定严格增大;但戳有大小也不能反推因果(p.1)。
4. 向量时钟接收事件的两步是什么?哪一步最容易漏?
先对所有 k 做逐分量 V[k] ← max(V[k], V′[k]),再只给自己那一维加 1(p.2)。两个高频错误是只更新自己那一维、跳过逐分量 max,以及 max 做完忘了加 1。
5. 发送事件附在消息上的向量,是自增之前还是之后的?
之后。先给自己那一维加 1,再把整个向量附上;先发再加会让接收方少算一格(p.2)。
6. Figure 2 里 c 与 p 是什么关系?判据是什么?
c = (3, 4, 1, 0),p = (1, 1, 5, 4)。c 的第 1、2 维大,p 的第 3、4 维大,互不包含,所以 c ∥ p 并发。判据是逐维 ≤ 且至少一维严格 < 才构成 happens-before(p.3)。
7. Figure 2 里 a = (1, 0, 0, 0) 与 s = (4, 4, 9, 7) 是什么关系?
a → s。每一维都 ≤ 且有严格小于,图里也确实有 a → n → … → r → s 这条因果链(p.3)。
8. Figure 2 里 r 收到 d 的 (4, 4, 1, 0),本地上一个是黑点 (1, 1, 7, 4)。r 是多少?
逐分量 max 得 (4, 4, 7, 4),P3 那一维加 1 得 (4, 4, 8, 4)。第 1、2 维走消息值,第 3、4 维走本地值(p.3)。
9. 不计 P3 那个黑点,Figure 1 会变哪些值?
P3 从 q 开始整体减 1:q = 4 … u = 8。连带 P4 的 y = max(3, 4) + 1 = 5,z = 6。P1、P2 不受影响(p.1、p.2)。
10. 不计 P3 那个黑点,Figure 2 为什么只有两行变?
只有 r = (4, 4, 7, 4) 和 s = (4, 4, 8, 7) 变。q 之后到 r 之间没有任何跨进程消息发出,所以变化传不到别的进程(p.3)。
下一步
两张图各重算一遍,不看答案——这是这门课唯一能靠熟练度稳拿分的题型,错也只错在机械步骤上,盯住「本地上一个事件」和「先 max 再 +1」两处,练三遍就不会再错。再把「图里出现无标签事件先在答卷上写一句假设」写进自己的答题模板。然后接着做 T01b 的选择题和广播判定题。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。