- 串行，就是任务一个接一个的执行。
- 并行，就是同一时刻，有多个任务在同时运行。
- 计算机为SMP或多核架构，才能同一时刻运行多个任务
- 并发，是一种假的并行。
- 在单核处理器中，同一时刻只能处理一个任务
- 每个任务只运行一小段时间（时间片），不停地切换任务
- 时间片一般只有几十毫秒，使得多个任务看起来在同时运行一样
举个多孩家庭的例子（响应国家号召）
- 老王家生了3个孩子，每个孩子年龄相差不大，都处于需要喂饭的时候
- 妈妈为了照顾小的，先从小的开始一个一个的喂饭 —— 这是串行
- 孩子都很饿，三个大人，一人照顾一个孩子，三个孩子就能同时吃上饭了 —— 这是并行
- 今天只有妈妈在家，只能一人一口不停地喂饭，让小孩们都吃上饭。 —— 这是并发
- CPU通过时间片算法来循环执行任务，前一个任务时间片用完，会切换到下一个任务
- 在切换前，需要保存前一个任务的状态，以便下次加载时使用
- 任务从保存 ⇒ Rightarrow ⇒ 再次加载的过程，就是一次上下文切换
- 上下文切换，首尾的准备工作会影响多线程的执行速度
- 这也是为什么，多线程有时不如单线程快：线程的创建和上下文的切换都需要一定的开销
vmstat
- linux系统中，可以使用vmstat命令可以测量上下文切换的次数
- vmstat 1，表示每隔1秒打印系统的状态
- cs，context Switch，表示上下文切换的次数
- 从打印结果可以看出，每秒的上下文切换十分频繁（真的是闪瞎眼，怪不得给人多个任务同时运行的错觉）
- 如向了解其他项的含义，可以查看博客：linux java block,Linux中vmstat命令详解
减少上下文切换的方法
- 无锁并发编程
- 多线程竞争锁时，会引起上下文切换：一次锁的使用，需要四次切换
- 申请锁时，从用户态进入内核态；获取到锁，从内核态返回用户态
- 释放锁时，需要从用户态进入内核态；唤醒其他等待锁的线程，又从内核态返回用户态
- 无锁，即不使用锁，但并非后续的CAS算法，而是从逻辑层面避免锁的使用
- 例如，多线程处理数据，可以将数据ID按照hash算法取模分段，不同的线程处理不同的数据段
- 多线程竞争锁时，会引起上下文切换：一次锁的使用，需要四次切换
- CAS算法
- Java的Atomic包使用CAS算法来更新数据，而无需加锁
- CAS：compare and swap，内存地址V中的值，与旧的预期值A一致，则更新为新的值B；否则，什么都不做
- 使用最少线程，避免创建不需要的线程
- 可以说，Java线程与OS级别的线程是一一对应的
- 每start一个Java线程，JVM中会多一个线程，最终会多一个OS级别的线程
- Java线程的调度将依赖OS底层的线程调度，不可避免的存在上下文切换带来的开销
- 最终，如果线程过多，线程执行代码的时间变少，大部分CPU时间都消耗在了线程的上下文切换上
- 协程
- 单线程实现多任务调度，并在单线程维持过个任务间的切换
为何说说Java线程与OS的线程是一一对应的？
- Thread的start()方法中，调用native的start0()方法，最终会在OS级别创建一个线程
- 所以说，Java中线程和OS的线程是1:1的关系
- 具体可以参考博客：Kotlin 协程真的比 Java 线程更高效吗？
- 毕设做的是区块链，当时go语言还是了解一点的
- go语言经常问到的就是协程了
- 进程、线程属于内核态，其调度受CPU时间片的影响，不受应用程序的控制
- 协程，是用户级线程，对内核透明，其调度完全有用户自己程序控制
- 不受内核的控制，就需要协程之间相互协作，主动转让控制权，避免某些协程长时间阻塞
go语言中的协程
-
go语言从语言层面原生支持协程，这是其一大特色
-
下面是一段协程的代码：
- 通过go语言关键字，以协程的方式执行函数say()
- 同时，使用WaitGroup避免由于主线程结束，导致协程还未执行就结束
- 这和Java中，thread.join()有异曲同工的作用
package main import ( "sync" ) var wg = sync.WaitGroup{} func main() { wg.Add(1) go say("Hello World") wg.Wait() } func say(s string) { println(s) wg.Done() }
Java是否支持协程？
- 肯定地说，Java不支持协程，仍然主打多线程
- 看看大佬怎么分析：为什么 Java 坚持多线程不选择协程？
- 其实，也有很多人想实现Java的协程，出现了很多Java协程库
- 最出名的协程库是Kotlin，Kotlin-JVM这个组合并不支持协程
- 因为，Kotlin在语言级别并未实现自己的同步机制，仍然 Kotlin-JVM中Java关键字
- 也就是说，Kotlin-JVM 声称自己是协程，但实际上干活的还是JVM中Thread那一套东西。
参考文档
- Golang协程详解和应用
- Java协程库总结
- Kotlin 协程真的比 Java 线程更高效吗？
- 本小节是对之前博客的总结与补充，之前的博客：操作系统之死锁
死锁的官方定义：
- 两个或两个以上的进程在执行过程中，由于资源竞争或彼此通信而造成的一种阻塞现象
- 若无外力的作用，它们都将无法推进下去
简单的说
-
当前进程拥有其他进程等待的资源
-
当前进程等待其他进程已拥有的资源
-
所有进程都不放弃自己拥有的资源
-
实例： 十字路口的小汽车，互相等待其他其他汽车退出路口，又不愿意自己退出路口（退一步海阔天空 ）
-
死锁的原因：① 由于资源不足而引发的资源竞争；② 并发执行的顺序不当
-
死锁的四个必要条件：互斥、占有且等待、不可抢占、循环等待
-
基于synchronized关键字，实现一个死锁的示例程序
public class DeadLock { public static String objA = "objA"; public static Integer objB = 1; public static void main(String[] arg) { // 创建线程Thread1 Thread thread1 = new Thread(() -> { try { System.out.println("Thread1 is running ..."); synchronized (DeadLock.objA) { // Thread1先获取objA System.out.printf("%s got the DeadLock.objAn", Thread.currentThread().getName()); Thread.sleep(1000); // 等待Thread2获取资源objB synchronized (DeadLock.objB) { // Thread1再获取objB System.out.printf("%s got the DeadLock.objBn", Thread.currentThread().getName()); } } } catch (InterruptedException e) { e.printStackTrace(); } }); thread1.setName("Thread1"); // 创建线程Thread2 Thread thread2 = new Thread(() -> { try { System.out.println("Thread2 is running ..."); synchronized (DeadLock.objB) { // Thread2先获取objB System.out.printf("%s got the DeadLock.objBn", Thread.currentThread().getName()); Thread.sleep(1000); // 等待Thread1获取资源objA synchronized (DeadLock.objA) { // Thread2再获取objA System.out.printf("%s got the DeadLock.objAn", Thread.currentThread().getName()); } } } catch (InterruptedException e) { e.printStackTrace(); } }); thread2.setName("Thread2"); // 启动线程，出现死锁，无法退出程序 thread1.start(); thread2.start(); } } -
程序执行起来以后，两个线程均因无法获取到第二个对象而阻塞，程序无法正常结束、
-
通过jps命令，获取当前程序的进程号：12218
-
通过jstack命令jstack 12218，获取进程的dump信息：
- dump信息，提示存在死锁，Thread2和Thread1均想要获取对方已拥有的对象而发生死锁
- dump信息，提示存在死锁，Thread2和Thread1均想要获取对方已拥有的对象而发生死锁
从教科书层面来说，死锁的解决办法有
- 鸵鸟策略： 死锁发生的概率很低，计算发生死锁，也不采取任何措施
- 死锁的预防： 主要是破坏死锁的四个必要条件，防止形成死锁（事前行为）
- 破坏互斥：互斥不可能被禁止，如文件只能多读单写
- 破坏占有且等待：进程在运行前，一次性获取所有的资源，否则一直阻塞直到能获取所有的资源
- 无法事先知道进程所需的资源
- 低效（由于获取资源而阻塞较长时间；获取之后，某些资源不会立即被使用）
- 破坏不可抢占：① 高优先级的进程抢占低优先级进程拥有的资源；② 进程进一步请求资源失败，释放已拥有的资源
- 破坏循环等待：统一编号，按照编号顺序请求资源（怀疑： 无法事先知道所需资源，后续资源的编号可能更小？）
- 死锁的避免：
- 不是破坏死锁的必要条件，而是预测发生死锁的可能性，并提前扼杀这种可能性（扼杀苗头）
- 在资源的动态分配过程中，使用一些算法防止系统进入不安全状态
- 两种策略：进程启动拒绝、资源分配拒绝（银行家算法）
- 死锁的检测与恢复（事后行为）
- 先检测是否存在死锁，然后采取一些措施恢复死锁的进程
- 取消所有死锁的进程，OS中最常用的方法
- 回滚死锁的进程到checkpoint，再重新启动；利用并发执行的不确定性，保证再出现死锁的风险的很低
- 按照某种原则，连续取消死锁的进程，直到不存在死锁
- 按照某种原则，连续抢占其他进程的资源，直到不存在死锁
- 先检测是否存在死锁，然后采取一些措施恢复死锁的进程
- 小镇的银行家，手中一部分资金借出给客户后，剩余的资金也不多了
- 客户再次申请资金时，需要做合理的评估：因为若无法满足客户的资金需求，之前的资金也会无法回收
- 这时，银行家需要找到一种剩余资金的分配策略，可以让所有客户的资金需求都得到满足，自己的资金才不会打水漂
- 很简单的想法：
- 手中剩余的资金先借给一个胃口小的客户，该客户生意成功后就能归还所有的资金；
- 手中剩余资金增加，再找下一个客户满足其申请；
- 以此类推，找到一个合理的分配、回收顺序，保证所有客户的资金申请都能满足
- 算法解决：
- 每个进程所需的资源Claim、已分配的资源Allocation、计算仍需的资源 C − A C-A C−A、系统的剩余资源 V V V
问题描述：
- 5个哲学家、5盘意大利面、5把叉子，哲学家的动作只有思考和吃意面
- 哲学家吃面时，先拿左边的叉子、再拿右边的叉子
- 所有哲学家同一时间感到饥饿，发现右边的叉子已经被另一个哲学家拿起
- 哲学家是呆板的，不好意思抢叉子、也不知道主动谦让，大家都干等着，最后饿死
- 要求同时拿起左右两把叉子，则需要对叉子加锁，保证使用时其他哲学家（线程）无法访问
- 实质： 破坏占有且等待
- 程序执行前，一次性获取所有需要的资源；
- 资源不足，则阻塞直到能一次性获取所有需要的资源
- 尝试获取左右两把叉子时，发现不能同时拿起，则需要等待其他哲学家释放叉子，自己再次尝试同时拿起
- 使用Java同步机制synchronized、wait、notify或notifyAll就可以实现上述的同步要求
- 具体代码，参考博客：操作系统之死锁
-
解决办法分析：
- 最多只允许4个哲学家同时就餐，也就是最多只允许4个哲学家同时拿起左边的叉子
- 这样还剩下一个叉子，某个哲学家可以拿起右边的叉子成功吃上意大利面
- 该哲学家放下左右两把叉子后，其他哲学家可以再次竞争叉子
-
实质： 有博客说这是破坏了循环等待，但是自己觉得好像和破坏循环等待的方法套不上？（欢迎交流）
-
使用信号量可以解决该问题
- 每把叉子同时只允许一个哲学家拿起，因此是值为1的信号量
- 为了保证最多只有4个哲学家同时拿起左边的叉子，可以使用值为4的信号量
- 为了避免某些哲学家一直等待，使用公平的信号量
-
信号量：实质是PV操作
- p操作让信号量的值减1；若信号量value >= 0，表明条件满足，可以进入临界区；否则，线程会被阻塞，直到被其他线程唤醒
- v操作，让信号量的值加1；若信号量value <= 0，表明有线程在等待，需要唤醒一个阻塞的线程，然后退出临界区；否则，直接退出临界区。
- PV操作，其实可以看做lock、unlock操作（菜鸟的理解 ）
- 信号量的值permits，
- 我的理解是：允许访问临界区的最大并行度
- 以最多允许4个哲学家拿起左边的叉子为例，人数就是临界区，4就是最大的并行度
-
基于信号量的代码实现
public class PhilosopherProblem { // 5把叉子，每把的状态均为可用或不可用 static Semaphore[] forks = new Semaphore[5]; // 可以拿起左边叉子的人数 static Semaphore leftCount; public static void main(String[] arg) { ExecutorService executorService = Executors.newFixedThreadPool(5); // 初始化信号量 for (int i = 0; i < 5; i++) { forks[i] = new Semaphore(1, true); } leftCount = new Semaphore(4, true); // 创建5个哲学家线程，模拟哲学家思考、吃面的过程 for (int i = 0; i < 5; i++) { executorService.submit(new Philosopher(i)); } } // 通过信号量实现哲学家的吃面过程 static class Philosopher implements Runnable { private int index; public Philosopher(int index) { this.index = index; } @Override public void run() { while (true) { try { // 哲学家思考 System.out.println("Philosopher " + index + ": I'm thinking"); Thread.sleep(1000); // 哲学家尝试拿起叉子 leftCount.acquire(); // 要求拿起左边叉子的人数最大为4，否则需要等待 forks[index].acquire(); // 尝试拿起左边的叉子 forks[(index + 1) % 5].acquire(); // 尝试拿起右边的叉子 // 开始吃面 System.out.println("Philosopher " + index + ": I'm eating"); Thread.sleep(1000); // 放下叉子 forks[index].release(); leftCount.release(); // 左边的叉子成功放下，拿起左边叉子的人数减一 forks[(index + 1) % 5].release(); } catch (InterruptedException e) { e.printStackTrace(); } } } } }
-
还有一种很奇妙的解决办法：给哲学家编号：1 ~ 5，奇数号的哲学家先拿起左边的叉子，偶数号的哲学家先拿起右手边的叉子
-
形成如图所示的场景：
- 拿起第一把叉子：2号和3号哲学家争抢叉子3，4号和5号哲学家挣钱叉子5，1号哲学家可以直接拿起叉子1
- 假设最终为1号、3号和4号哲学家成功拿到第一把叉子
- 拿起第二把叉子：3号和4号哲学家将争抢叉子4，1号哲学家可以直接拿起叉子2，这样1号哲学家可以成功吃上意大利面
- 有人吃上了面，后面的人就有拿起叉子的希望了
-
还是可以使用信号量实现：每把叉子对应值为1的信号量，按照哲学家的编号，决定应该先拿起哪边的叉子
- 注意： 由于数组的编号从0开始，因此奇数号的哲学家的index实际为偶数
public class PhilosopherProblem { // 5把叉子，每把的状态均为可用或不可用 static Semaphore[] forks = new Semaphore[5]; public static void main(String[] arg) { ExecutorService executorService = Executors.newFixedThreadPool(5); // 初始化信号量 for (int i = 0; i < 5; i++) { forks[i] = new Semaphore(1, true); } // 创建5个哲学家线程，模拟哲学家思考、吃面的过程 for (int i = 0; i < 5; i++) { executorService.submit(new Philosopher(i)); } } // 通过信号量实现 static class Philosopher implements Runnable { private int index; public Philosopher(int index) { this.index = index; } @Override public void run() { while (true) { try { // 哲学家思考 System.out.println("Philosopher " + index + ": I'm thinking"); Thread.sleep(1000); // 根据编号，决定拿起叉子的顺序 if (index % 2 == 0) { // 奇数号哲学家，先左手，再右手 forks[index].acquire(); forks[(index+1)%5].acquire(); } else { // 偶数号哲学家，先右手，再左手 forks[(index + 1) % 5].acquire(); forks[index].acquire(); } // 开始吃面 System.out.println("Philosopher " + index + ": I'm eating"); Thread.sleep(1000); // 放下叉子 if (index % 2 == 0) { forks[index].release(); forks[(index+1)%5].release(); } else { forks[(index + 1) % 5].release(); forks[index].release(); } } catch (InterruptedException e) { e.printStackTrace(); } } } } }
- 哲学家就餐问题，实际是资源不足而导致的资源竞争问题，并在资源竞争的过程中发生了死锁
- 解决方法必须满足以下条件：
- 保持互斥：一把叉子不可能两位哲学家同时拿起
- 避免死锁：避免所有的哲学家都吃不上
- 避免饥饿：避免某些哲学家一直吃不上，使用公平信号量
参考链接
- 信号量：java并发系列 - 02信号量机制
- 破坏哪种条件：Java哲学家进餐问题|多线程
- 信号量实现解法二和三：java实现哲学家进餐问题，及其死锁问题的解决
- 图文分析：哲学家进餐问题的三种解决方法(C++11)
- 死锁的总结可以参考之前的博客：操作系统之死锁
- 个人觉得重点如下：
- 死锁的定义、四个必要条件、如何解决死锁
- 银行家算法（死锁的避免、资源分配拒绝策略）、哲学家就餐问题（三种常见解决办法、程序示例）
- 死锁、活锁、饥饿
并发度越大，程序运行的越快或效率越高？
- 在前面的内容中提到过，多线程的速度不一定比单线程快
- 因为线程的创建和上线文切换需要一定的开销，这使得真正执行代码的时间不是很长
- 除此之外，资源的限制也会影响程序运行效率。
- 例如，办公网宽带为2MB/s，每个下载线程为1MB/s
- 摸鱼下载电影时，10个下载线程反而没有一个下载线程快
- 因为总的带宽为2MB/s，10个下载线程，下载速度最多也是2MB/s，而不会变成10MB/s
- 可见，资源的限制也会影响并发度
常见的资源限制
- 硬件：网络带宽的上传/下载速度、CPU的处理速度、磁盘的读写速度等
- 软件：socket连接数、数据库连接数等
如何解决资源限制的问题？
- 对硬件资源，可以考虑单机变多机、并发变并行
- 对软件资源，可以考虑资源的复用，如数据库连接的复用
并发编程，学会因地制宜，及时根据资源限制调整并发度
4. 总结- 这一章主要讲解了并发编程的挑战，总结起来有三大挑战：
- 上下文切换的开销：多线程不一定比单线程快
- 死锁：由于资源有限或并发执行的顺序不当而引起的死锁
- 资源限制对并发度的影响：并发度越大，不一定程序效率越高，会受限于软件或硬件资源
- 重点在死锁，复习了死锁的相关知识，尝试使用Java解决哲学家就餐问题
