12. 并发 Bugs
1 致命的并发Bugs
事件级的并发
12345678910111213Event(doMouseMove) { hoveredItem = Item("$1");} // 被插入的非预期事件 Event(clickEvent) { hoveredItem = Item("$99"); // <- Shared state Inventory.append(hoveredItem); }Event(doPickUp) { InHand = hoveredItem;}
Therac-25 Incident (1985-1987)
事件驱动导致的并发 bug,导致至少 6 人死亡
Diablo I 案例再现
选择 X-Ray (High) Mode
机器开始移动 mirror,大约需要 8s 完成…
切换到 Electron (Low) Mode (OK)
再迅速切换到 X-Ray (High) Mode
...
11. 真实世界的并发编程
1 我们身边的并发编程
1.1 互联网的开始:Web1.0
从 PC 时代到互联网时代 (1990s)
Amazon (1994), Yahoo (1994), eBay (1995), Google (1998)
HTTP (对,没有 HTTPS), HTML,但没有 CSS
中国互联网初代 “三巨头”:新浪、搜狐、网易诞生
<font>, <table>, vbscript 和切图工程师一统天下
1.2 Web2.0
Asynchronous JavaScript and XML (Ajax; ~1999)
允许网页实现 “后台刷新”
悄悄请求后端,然后更新 DOMTree
“应用” 可以做的,网页也都可以做了!
(你没看错,竟然不是 JSON)
原因:后端 (Java) 应用广泛使用 XML
jQuery $ (2006)
允许 Javascript 代码优雅地修改 DOMTree
$('h3').replaceWith('XXX');
从此,做“任何事”都只要浏览器就行
甚至诞生了 ChromeOS
HTM ...
js前世今生
1990年,世界上第一个网页诞生
蒂姆·伯纳斯-李,他是一名计算机科学家,他在1990年发明了万维网,并且没有申请专利。他希望所有人在互联网上分享知识。
需要解决的问题一:语言
设计一个超文本的实现,html
a标签,超链接,锚点ahchor
需要解决的问题二:数据接受和传输
基于TCP/IP协议发明了http协议
需要解决的问题三:可以渲染html的引擎
浏览器(终端内的www)
1993年,页面不只是文字,还有图片
马克安德森和另一位NCSA的朋友一起研发了mosiac浏览器,可以渲染图片。
1994年以后,安德森和吉姆克拉克从NCSA离开了,成立了NetScap网景公司
在MOSIAC浏览器的基础上,开发了netscap naviagtor浏览器,可以渲染图片和文字。
1995年,liveScript诞生
Brendan Eich开发这种网页脚本语言,可以嵌入网页中。
同年12月,网景公司与Sun公司达成协议,命名这种语言叫做javascrpt。
1996年,微软加入浏览器市场
3月,Navigato浏览器正式内置了javas ...
10. 并发控制:同步 (2)
1 信号量
1.1 用互斥锁实现同步
一个奇妙的想法
创建锁时,立即 “获得” 它 (总是成功)
其他人想要获得时就会等待
此时 release 就实现了同步
一个线程上锁,在另一个线程解锁
让我们来试一试吧 (demo)
先把厕所门都锁上
线程到达以后等待
管理员把所有门都打开
Acquire-Release 实现计算图
为每一条边 𝑒=(𝑢, 𝑣) 分配一个互斥锁
初始时,全部处于锁定状态
对于一个节点,它需要获得所有入边的锁才能继续
可以直接计算的节点立即开始计算
计算完成后,释放所有出边对应的锁
挺好用 (demo)
甚至比条件变量还好用!
1.2 本质:Release as Synchronization
Release-Acquire 实现了 happens-before
Acquire = 等待 token
Release = 发出 token
Token 可以理解为现实生活中的“资源”
停车场:停车位
游泳馆:获得手环 (token) 的人可以进入更衣室
mutex 实现 token 似乎有什么问题?
缺点:t ...
9. 并发控制:同步 (1)
1. 线程同步
Synchronization
控制并发,使得 “两个或两个以上随时间变化的量在变化过程中保持一定的相对关系”
有点抽象,让我们来看例子
理解并发的方法
线程 = 我们自己
共享内存 = 物理空间
1.1 现实世界中的同步
演奏音乐中的同步
每个乐手都是一个 “线程”
节拍 𝑖 到达 → 演奏 𝑛𝑖𝑛_𝑖ni
123456void T_player() { while (!end) { wait_next_beat(); play_next_note(); }}
在某个瞬间达到 “互相已知” 的状态
NPY: 等我洗个头就出门
NPY: 等我打完这局游戏就来
舍友:等我修好这个 bug 就吃饭
导师:等我出差回来就讨论这个课题
join(): 等所有线程结束就继续
“先到先等”,在条件达成的瞬间再次恢复并行
同时开始出去玩/吃饭/讨论
1.2 状态机视角
系统到达某个 “同步” (互相已知) 的状态
1234567891011121 ...
8. 调试理论与实践
1. 调试理论
1.1 Debug
如果我们已经知道 bug 的存在
Segmentation Fault
Online Judge 拒绝
虚拟机神秘重启
……
怎么找到它
公理 1:机器永远是对的
CPU: “无情的、执行指令的机器”
Crash, Wrong Answer, 虚拟机神秘重启
99.9999% 是自己的问题
有亿点点概率是编译器错了 (但你可以知道)
有亿点点点点概率是处理器错了 (你也可以知道)
公理 2:未测代码永远是错的
反复测试过的代码都是错的
你以为最不可能出 bug 的地方,往往 bug 就在那躺着
1.2 调试理论
“软件” 的两层含义
人类需求在信息世界的投影
理解错需求 → bug
计算过程的精确 (数学) 描述
实现错误 → bug
调试为什么困难?
Bug 的触发经历了漫长的过程
可观测的现象未必能直接对应到 root cause 上
1.3 Fault,Error,和Failure
需求 → 设计 → 代码 (Fault/bug) → 执行 (Error) → 失败 (Failur ...
7. 并发控制:互斥 (2)
1 操作系统内核中的互斥
1.1 计算机系统的状态机模型
状态
共享内存 + per-CPU 寄存器
初始状态
由系统设计者规定 (CPU Reset)
状态迁移
选择任意 CPU:
从 PC 取指令执行或响应中断信号 (中断打开时)
计算:改变内存/寄存器数值
I/O:与 “计算机系统外” 交换数据
1.2 操作系统内核中的互斥
操作系统接管了完整的计算机系统
每个处理器都并行 x++
每个处理器中断发生时执行 x += 1000000000
(假想 x 是操作系统中的数据结构,例如进程表)
如何正确实现 x 的原子访问?
仅仅自旋是不够的
lock后,sum++,如果sum++里面也lock,再执行其他任务的时候,会死锁。
因为还有中断
1.3 正确性准则
正确实现互斥
关中断 + 自旋可以保证实现互斥
上锁/解锁前后中断状态不变
不得在关中断时随意打开中断 (例如处理中断时)
不得随意关闭中断 (否则可能导致中断丢失)
因此我们需要保存中断状态
全局?
Per CPU?
Per Thread?
xv6 自旋锁 ...
6. 并发控制:互斥 (1)
1 阻止并发 (并行) 的发生
1.1 并发困难的原因
人类是 “sequential creatures[有序生物]”
人类具备 𝐴→…→𝐵 简化为 𝐴→𝐵 的直觉本能
并且据此开发了编译器 (处理器也是编译器)
多处理器和并发执行推翻了顺序执行的基本假设!
1.2 互斥
人类是 (绝不轻言放弃的) sequential creatures
互斥 (互相排斥):阻止并发,问题不就解决了?
1ATOMIC { sum++; }
1234567891011int T_alipay_withdraw(int amt) { ... ATOMIC { // No concurrency with // other critical sections if (balance >= amt) { balance -= amt; } } ...}
1.3 互斥:阻止并发、独占访问
...
关于对抽象的一点理解
1 什么是抽象
1.1 关于多态
在面向对象编程中,多态是指一类事物有多种形态。比如A类,A-1和A-2都属于动物类,它们都有A类中公共的方法
由于多态的存在,每个子类都可以覆写父类的方法,例如下面的代码中子类1和2都覆写了父类中的某个方法:
在这里,假如我们要设计一款游戏名叫 Apax 的枪械游戏。在这款游戏中,我们的武器就是枪械,所以我们来为我们的游戏设计一个 Weapon 类,它代表所有枪械的父类:
12345678910111213141516171819// 父类-武器class Weapon { // 具有的方法 // 子弹类型 public void WeaponAmmo() { … } // 击中要害转化倍率 public void WeaponForce() { … } // ...}// 子类1-轻型弹药武器class LightAmmo extends Weapon { @Override public void WeaponAmmo() ...
5. 多处理器编程:从入门到放弃
1 多处理器编程入门
1.1 多线程编程模型
多个共享内存的状态机
C 语言状态机的多个线程
共享所有全局变量
独立的栈帧列表
汇编语言状态机的多个线程
共享一个地址空间
独立的寄存器 (SP 指向不同内存位置)
状态迁移
选择任意一个线程执行一步
Mosaic 状态机
“heap” 是共享内存
sys_sched 主动随机切换线程
单处理器系统:中断会引起切换
(这就是为什么死循环不能把机器卡死)
多处理器系统:真正同时执行
相当于无时不刻在切换
模拟多线程程序的行为
思考题:我们可以借助共享内存做什么?
1.2 多处理器编程:入门
简化的线程 API (使用thread.h库就可以直接create)
spawn(fn)
创建一个入口函数是 fn 的线程,并立即开始执行
void fn(int tid) { ... }
参数 tid 从 1 开始编号
行为:sys_spawn(fn, tid)
join()
等待所有运行线程的返回 (也可以不调用)
行为:while (done != ...