起因
有几本知名的垫显示器🖥专用书, 提到他们时,很多人都会直接用几个奇怪的字母来代替. 什么CSAPP, TAOCP, CLRS, SICP, 一个个神神叨叨的, 听着就烦,也提不起心思去看.
昨日翻出来一本CLRS第三版,翻看了一下新增的第27章多线程算法 .还真有点收获.这种砖头🧱,有时候还是需要看一看的,有用.
所以, 专门写写这一章的阅读心得.
大背景
CLRS 作为一本算法书, 讲的多是些单核CPU时代留下来的串行算法(serial algorithm).在
摩尔定律已经走到头,多核CPU大行其道的今天,不讲讲并行算法( parallel algorithm),实在
不行了.因此作者加了这么一章,并行算法. 基于的主要模型, 是共享存储( shared memory)计算机,分布式存储( distributed memory) 计算机不在讨论之列.
最好玩的部分,是作者指出了staic threading模型催生了concurrency platform. 由软件层来调度管理协调计算资源.
一部分靠运行时库建立,一部分作为并行语言靠编译器和运行时支撑. dynamic multithreading这块的差别不太懂啊,
说实话,因为一开始就用java,没往下研究过. 我还以为就一种模型呢, 开眼了.
java这个1:1线程模型,不知道跟这个有没有关系,先不深究.
java 应该算是用运行时库支撑的并发平台吧?
重要收获
这章很薄,就几十页,如果后面的多线程矩阵和归并不自己动手实现的话, 前面只有十来页. 但对于我这种野生程序员而言,还是学到了点东西的.
动态多线程模型是对串行编程模型的简单扩展.
这句让人惊艳了. 特别加入了3个关键字,简单点缀一下,串行算法就变成并行算法了这点.
- parallel
- spawn
- sync
动态多线程模型的两个特点嵌套并行,并行循环,都可以用这3个关键字组合出来.
感觉上, 这个 spawn+sync, 有点像js和c#里的await, 不知道对不对. 在java里应该是Future,或者Thread的start和join.
并行循环
想来想去, java里提供类似功能的,应该是Stream.parallel
这套接口.搜了下, Executors 也能做到.
搜了下, python里的几个 实现 也是
这么做的,pool.map,差不离.
c++ 的实现也类似. 不知道市面上,
有没有直接支持语法级别支持的. 或许,spring 里加个注解, 可以模拟下?
总体看起来,在现代确实是个基本特性. 不过不是书上写, 我都没意识到这是个特性,😄.
意识到这3个原语, 对我而言其实是有好处的.
以前的多线程实现,我都是直接new 了thread, 就开始写了. 然后再处理优化.
现在想想, 既然都可以通过串行算法加这3个实现, 那就可以先写出串行版本. 然后进行伪代码改造.最后翻译回实现的语言里就行了.
执行链的有向无环图DAG
这个分析起来,其实非常有趣. 因为涉及到古老的软件工程问题.
1个女人,生一个孩子要10个月, 10个女人1个月能生出来吗?工期延误,通过加人,不能赶上工期是为什么?
这几个性能度量指标,对思考很有帮助. 以前能模糊感觉到,但是作为 一个严格的量化指标来思考,还是没干过的.
工作量定律, T_p >= T_1/P 持续时间定律 T_p >= T_∞
加速比, T_1/T_P T_1/T_P = P 完美线性加锁 T_1/T_P = θ(P) 线性加锁 T_1/T_∞ 并行度
并行度/P 松弛度
有点意思. 加服务器提高tps,qps,其实也是这么个东西啊. 加多了更浪费机器,就是加速比有问题啊.集群能放到多大,看的 就是并行度啊. 这几个概念,感觉可以画张图连起来. 更清楚
工作量不饱和+贪心调度的优越性,貌似直接把管理的诀窍说出来了. 别让闲着.
线程安全的本质
竞争条件一个多线程算法是确定的( deterministic),如果在同样的输人情况下总是做相同的事,且无论指令在多核计算机上如何被调度也是如此。一个多线程算法是非确定的( nondeterministic),如果每次执行它做的事情有所不同。一个多线程算法意图确定地做一些事情,但常常会失败,究其原因是算法中包含了“确定性竞争”
当两个逻辑上并行指令访问存储器同一位置且至少有一个指令执行写操作的时候,便会发生确定性竞争( determinacy race)
共享存储模型下的, 竞争关系啊. 那,分布式其实不是共享存储啊. 分布式的算法,还不是这一套.
不过,redis在一定层面上, 做了个共享存储. 这可能也是近年来,redis越来越重的原因. 否则随着服务器集群的加大, 不用共享存储模型编程,其实是非常陌生的领域啊.