【图解八股-操作系统篇②-同步互斥和锁】
作者简介和专栏内容见专栏介绍:https://www.nowcoder.com/creation/manager/columnDetail/0eL5bM
麻烦看到贴子的伙伴点点赞大家点赞订阅支持下,提前祝各位offer多多,有问题评论区见~~
图解版
同步互斥与锁
同步和互斥
互斥概念
多线程执行共享变量的这段代码可能会导致竞争状态,因此我们将此段代码称为临界区(criticalsection),它是执行共享资源的代码片段,一定不能给多线程同时执行。
所以我们希望这段代码是互斥(mutualexclusion)的,也就说执行临界区(criticalsection)代码段的只能有一个线程,其他线程阻塞等待,达到排队效果。
互斥并不只是针对多线程的竞争条件,同时还可用于多进程,避免共享资源混乱。
同步概念
互斥解决了「多进程/线程」对临界区使用的问题,但是它没有解决「多进程/线程」协同工作的问题
我们都知道在多线程里,每个线程一定是顺序执行的,它们各自独立,以不可预知的速度向前推进,但有时候我们希望多个线程能密切合作,以实现一个共同的任务。
所谓同步,就是「多进程/线程间」在一些关键点上可能需要互相等待与互通消息,这种相互制约的等待与互通信息称为「进程/线程」同步。
互斥与同步的区别
互斥:某一资源同时只允许一个访问者对其进行访问,具有性和排它性。但互斥无法限制访问者对资源的访问顺序,即访问是无序的。「操作A和操作B不能在同一时刻执行」
同步:互斥的基础上,通过其它机制实现访问者对资源的有序访问。在大多数情况下,同步已经实现了互斥。
「操作A应在操作B之前执行」,「操作C必须在操作A和操作B都完成之后才能执行」
同步是一种更为复杂的互斥,而互斥是一种特殊的同步。也就是说互斥是两个线程之间不可以同时运行,他们会相互排斥,必须等待一个线程运行完毕,另一个才能运行,而同步也是不能同时运行,但他是必须要按照某种次序来运行相应的线程(也是一种互斥)!
死锁相关问题大总结,超全!
死锁是指两个(多个)线程相互等待对方数据的过程,死锁的产生会导致程序卡死,不解锁程序将永远无法进行下去。
1、死锁产生原因
举个例子:两个线程A和B,两个数据1和2。线程A在执行过程中,首先对资源1加锁,然后再去给资源2加锁,但是由于线程的切换,导致线程A没能给资源2加锁。线程切换到B后,线程B先对资源2加锁,然后再去给资源1加锁,由于资源1已经被线程A加锁,因此线程B无法加锁成功,当线程切换为A时,A也无法成功对资源2加锁,由此就造成了线程AB双方相互对一个已加锁资源的等待,死锁产生。理论上认为死锁产生有以下四个必要条件,缺一不可:
1. 互斥条件:多个线程不能同时使用同一个资源。
2. 不剥夺条件:进程在所获得的资源未释放前,不能被其他进程强行夺走,只能自己释放。
3. 请求和保持条件:进程当前所拥有的资源在进程请求其他新资源时,由该进程继续占有。
4. 循环等待条件:存在一种进程资源循环等待链,链中每个进程已获得的资源同时被链中下一个进程所请求。
3、死锁的解决方案
保证上锁的顺序一致。
5、处理方法
主要有以下四种方法:
鸵鸟策略
把头埋在沙子里,假装根本没发生问题。
因为解决死锁问题的代价很高,因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。 当发生死锁时不会对用户造成多大影响,或发生死锁的概率很低,可以采用鸵鸟策略。 大多数操作系统,包括 Unix,Linux 和 Windows,处理死锁问题的办法仅仅是忽略它。
死锁检测与死锁恢复
不试图阻止死锁,而是当检测到死锁发生时,采取措施进行恢复。
6、死锁恢复
利用抢占恢复 ;利用回滚恢复 ;通过杀死进程恢复
7、死锁避免
避免死锁问题就只需要破环其中一个条件就可以,最常见的并且可行的就是使用资源有序分配法,来破环环路等待条件。
1. 破坏互斥条件
例如假脱机打印机技术允许若干个进程同时输出,唯一真正请求物理打印机的进程是打印机守护进程。
2. 破坏请求和保持条件
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
3. 破坏不剥夺条件
允许抢占资源
4. 破坏循环请求等待
给资源统一编号,进程只能按编号来请求资源。
死锁如何发现
死锁是多线程或多进程程序中一种常见的问题,它会导致进程或线程无法继续执行,从而降低程序的性能甚至直接导致程序崩溃。下面是一些常见的发现程序死锁的方式:
1. 日志和输出信息:程序在发生死锁时,可能会输出一些错误信息或者日志,提示死锁的发生。在程序中加入一些调试信息,或者使用调试工具来查看程序的输出信息,可以帮助发现死锁问题。
2. 监控工具:可以使用一些系统监控工具来监控程序的资源使用情况,例如 CPU、内存等。如果程序出现死锁,可能会导致某些资源的占用率异常,从而提示死锁问题的发生。
3. 运行时分析工具:可以使用一些运行时分析工具来监控程序的运行情况,例如 gdb、strace 等。这些工具可以帮助分析程序的运行过程,发现出现死锁的位置和原因。
4. 静态分析工具:可以使用一些静态分析工具来分析程序的代码,例如 Valgrind、Clang 等。这些工具可以检测程序中的潜在死锁问题,并给出相应的警告。
介绍一下几种典型的锁?
开发过程中,最常见的就是互斥锁的了,互斥锁加锁失败时,会用「线程切换」来应对,当加锁失败的线程再次加锁成功后的这一过程,会有两次线程上下文切换的成本,性能损耗比较大。
如果我们明确知道被锁住的代码的执行时间很短,那我们应该选择开销比较小的自旋锁,因为自旋锁加锁失败时,并不会主动产生线程切换,而是一直忙等待,直到获取到锁,那么如果被锁住的代码执行时间很短,那这个忙等待的时间相对应也很短。
如果能区分读操作和写操作的场景,那读写锁就更合适了,它允许多个读线程可以同时持有读锁,提高了读的并发性。根据偏袒读方还是写方,可以分为读优先锁和写优先锁,读优先锁并发性很强,但是写线程会被饿死,而写优先锁会优先服务写线程,读线程也可能会被饿死,那为了避免饥饿的问题,于是就有了公平读写锁,它是用队列把请求锁的线程排队,并保证先入先出的原则来对线程加锁,这样便保证了某种线程不会被饿死,通用性也更好点。
互斥锁和自旋锁都是最基本的锁,读写锁可以根据场景来选择这两种锁其中的一个进行实现。
另外,互斥锁、自旋锁、读写锁都属于悲观锁,悲观锁认为并发访问共享资源时,冲突概率可能非常高,所以在访问共享资源前,都需要先加锁。
相反的,如果并发访问共享资源时,冲突概率非常低的话,就可以使用乐观锁,它的工作方式是,在访问共享资源时,不用先加锁,修改完共享资源后,再验证这段时间内有没有发生冲突,如果没有其他线程在修改资源,那么操作完成,如果发现有其他线程已经修改过这个资源,就放弃本次操作。
但是,一旦冲突概率上升,就不适合使用乐观锁了,因为它解决冲突的重试成本非常高。
不管使用的哪种锁,我们的加锁的代码范围应该尽可能的小,也就是加锁的粒度要小,这样执行速度会比较快。再来,使用上了合适的锁,就会快上加快了。
读写锁
它由「读锁」和「写锁」两部分构成,如果只读取共享资源用「读锁」加锁,如果要修改共享资源则用「写锁」加锁。
所以,读写锁适用于能明确区分读操作和写操作的场景。
读写锁的工作原理是:
- 当「写锁」没有被线程持有时,多个线程能够并发地持有读锁,这大大提高了共享资源的访问效率,因为「读锁」是用于读取共享资源的场景,所以多个线程同时持有读锁也不会破坏共享资源的数据。
- 但是,一旦「写锁」被线程持有后,读线程的获取读锁的操作会被阻塞,而且其他写线程的获取写锁的操作也会被阻塞。
互斥锁和自旋锁
最底层的两种就是「互斥锁和自旋锁」,有很多高级的锁都是基于它们实现的,你可以认为它们是各种锁的地基
加锁的目的就是保证共享资源在任意时间里,只有一个线程访问,这样就可以避免多线程导致共享数据错乱的问题。
当已经有一个线程加锁后,其他线程加锁则就会失败,互斥锁和自旋锁对于加锁失败后的处理方式是不一样的:
- 互斥锁加锁失败后,线程会释放 CPU ,给其他线程;
- 自旋锁加锁失败后,线程会忙等待,直到它拿到锁;
互斥锁加锁失败时,会从用户态陷入到内核态,让内核帮我们切换线程,虽然简化了使用锁的难度,但是会有两次线程上下文切换的成本。
如果你能确定被锁住的代码执行时间很短,就不应该用互斥锁,而应该选用自旋锁,否则使用互斥锁。
条件变量
互斥锁一个明显的缺点是他只有两种状态:锁定和非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足,他常和互斥锁一起使用,以免出现竞态条件。当条件不满足时,线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量,他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说互斥锁是线程间互斥的机制,条件变量则是同步机制。
悲观锁
前面提到的互斥锁、自旋锁、读写锁,都是属于悲观锁。
悲观锁做事比较悲观,它认为多线程同时修改共享资源的概率比较高,于是很容易出现冲突,所以访问共享资源前,先要上锁。
乐观锁
乐观锁做事比较乐观,它假定冲突的概率很低,它的工作方式是:先修改完共享资源,再验证这段时间内有没有发生冲突,如果没有其他线程在修改资源,那么操作完成,如果发现有其他线程已经修改过这个资源,就放弃本次操作。乐观锁全程并没有加锁,所以它也叫无锁编程。
这里举一个场景例子:在线文档。
我们都知道在线文档可以同时多人编辑的,如果使用了悲观锁,那么只要有一个用户正在编辑文档,此时其他用户就无法打开相同的文档了,这用户体验当然不好了。
那实现多人同时编辑,实际上是用了乐观锁,它允许多个用户打开同一个文档进行编辑,编辑完提交之后才验证修改的内容是否有冲突。
为什么自旋锁不能睡眠 而在拥有信号量时就可以?
自旋锁和信号量都是并发编程中常用的同步机制,但它们的实
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
作者简介:2个月时间逆袭嵌入式开发,拿下理想汽车-ssp、小米汽车-sp、oppo-sp、迈瑞医疗、三星电子等八家制造业大厂offer~ 专栏内容:涵盖算法、八股、项目、简历等前期准备的详细笔记和模板、面试前中后的各种注意事项以及后期谈薪、选offer等技巧。保姆级全阶段教程帮你获得信息差,早日收到理想offer~