[面试直通版]操作系统之锁、同步与通信(上)

点击->操作系统复习的文章集<-点击

目录

死锁的基本理论

典型问题：

死锁简述

死锁的产生

死锁的四个必要条件

预防死锁的方法

同步问题三大经典案例

生产者-消费者问题

读者-写者问题

哲学家进餐问题

附录

锁的种类

典型问题：

乐观锁/悲观锁

无锁/偏向锁/轻量级锁/重量级锁

公平锁/非公平锁

可重入锁/非可重入锁

共享锁/排他锁

---

• 死锁的基本理论

• 典型问题：

• 请简述死锁的必要条件
• 请简述什么是死锁，为什么会产生死锁

• 死锁简述

• 死锁是指两个或两个以上的进程在执行过程中
• 由于竞争资源或者由于彼此通信而造成的一种阻塞的现象
• 若无外力作用，它们都将无法推进下去
• 此时称系统处于死锁状态或系统产生了死锁
• 这些永远在互相等待的进程称为死锁进程

• 死锁的产生

• 主要归结于以下原因：
• 竞争资源
• 进程调度顺序不当
• 竞争资源
• 共享资源数量不满足各个进程需求
• 各个进程之间发生资源竞争导致死锁
• 来个例子：
• 有2个进程(进程1，进程2)
• 进程1先使用了传真机
• 进程2先使用了打印机
• 假设这时进程1需要使用打印机，进程2需要使用传真机
• 这种情况下就会发生死锁
• 因为进程1需要使用的打印机正在被进程2占用
• 进程2需要使用的传真机正在被进程1占用
• 如2者都不释放各自占用，就会进入等待状态
• 也就是
• 等待请求的资源被释放
• 自身占用资源不释放
• 如此就导致死锁
• 调度顺序不当
• 继续参考上面的例子
• A：进程1指向传真机
• B：进程2指向打印机
• C：进程2指向传真机
• D：进程1指向打印机
• 若是A->B->C->D 会导致死锁
• 若是A->D->B->C 将会解决死锁问题

• 死锁的四个必要条件

• 互斥条件
• 请求保持条件
• 不可剥夺条件
• 环路等待条件
• 互斥条件
• 进程对资源的使用是排他性的使用
• 某资源只能由一个进程使用，其它进程需要使用只能等待
• 请求保持条件
• 进程至少保持一个资源，又提出新的资源请求
• 新资源被占用，请求被阻塞
• 被阻塞的进程不释放自己保持的资源
• 不可剥夺条件
• 进程获得的资源在未完成使用前不能被剥夺
• 获得的资源只能由进程自身释放
• 环路等待条件
• 发生死锁时，必然存在进程-资源环形链

• 预防死锁的方法

• 破坏以上任意一个条件即可
• 摒弃请求保持条件
• 系统规定进程运行之前，一次性申请所有需要的资源
• 进程在运行期间不会提出资源请求，从而摒弃请求保持条件
• 摒弃不可剥夺条件
• 当一个进程请求新的资源得不到满足时，必须释放占有的资源
• 进程运行时占有的资源可以被释放，意味着可以被剥夺
• 摒弃环路等待条件
• 可用资源线性排序，申请必须按照需要递增申请
• 线性申请不再形成环路，从而摒弃了环路等待条件
• 银行家算法
• 是一个可操作的著名的避免死锁的算法
• 以银行借贷系统分配策略为基础的算法
• 理解：
• 客户申请的贷款是有限的，每次申请需声明最大资金量
• 银行家在能够满足贷款时，都应该给用户贷款
• 客户在使用贷款后，能够及时归还贷款
• 这个算法要求有3个数据结构
• 1.已分配资源表
• 2.所需资源表
• 3.可分配资源表
• 将所需资源表减去已分配资源表得到还需分配资源表
• 将还需分配资源表与可分配资源表进行对比
• 优先把可分配的所有资源都分发给某个可满足的进程
• 让此进程可以继续执行下去，等此进程执行完后，再归还相关资源
• 归还资源后，又可以把新的资源重新分配给其它需要的进程

• 同步问题三大经典案例

• 生产者-消费者问题

• 一组生产者进程，一组消费者进程，一个缓冲区
• 生产者在缓冲区溢出前，不断往缓冲区生产数据
• 消费者在缓冲区为空前，不断从缓冲区消费数据
• 生产者-消费者通过缓冲区存在同步关系
• 当缓冲区满时，生产者必须等待消费者消费数据
• 当缓冲区空时，消费者必须等待生产者生产数据
• 生产者-消费者，生产者之间，消费者之间存在互斥关系
• 对缓冲区数据进行存取操作时，必须互斥进行

• 读者-写者问题

• 来个例子：
• 有个count值为10
• 以下进行+1和-1操作
• 但是如果说+1和-1是由不同的线程去执行的，这时可能就会产生问题(可能不顺序)
• 
• 这是因为读-写操作之间存在同步关系
• 多个写操作应该串行完成

• 哲学家进餐问题

•   

• 过程：
• 正常情况：拿起左边筷子，然后发现右边筷子被拿了
• 等待右边筷子释放
• 拿起右边筷子
• 进餐
• 特殊情况：5个哲学家同时拿起左边筷子
• 发现右边筷子被拿了
• 5个哲学家都等待右边筷子释放
• 相互等待
• 5个哲学家饿死
• 解决：
• 根源问题是：彼此相互之间没有通信
• 需要生产者通知消费者我已经完成一件生产
• 或是哲学家向旁边哲学家说我要进餐了，别拿我筷子
• 也就是需要进程间的同步
• 对竞争资源在多进程间进行使用次序的协调
• 使得并发执行的多个进程之间可以有效使用资源和相互合作

• 附录

• 临界资源指的是一些虽作为共享资源却又无法同时被多个线程共同访问的共享资源
• 原子性
• 原子性是指一系列操作不可被中断的特性
• 这一系列操作要么全部执行完成，要么全部没有执行
• 不存在部分执行部分未执行的情况

• 锁的种类

• 典型问题：

• 请简述乐观锁/悲观锁/可重入锁
• 请简述轻量锁/重量锁/公平锁/非公平锁

• 乐观锁/悲观锁

• 悲观锁每次操作都加锁，乐观锁默认不添加锁
• 悲观锁：
• 每次操作数据时都认为别人会修改，很悲观，所以操作时加锁
• 乐观锁：
• 每次操作数据时都认为别人不会修改，很乐观，但是更新时会判断一下在此期间别人有没有去更新这个数据
• 悲观锁适合写操作的场景
• 乐观锁适合读操作的场景

• 无锁/偏向锁/轻量级锁/重量级锁

• 无锁：
• 不锁资源，多个线程只有一个线程修改成功，其它线程会重试
• 偏向锁：
• 同一个线程执行临界资源会自动获取资源
• 顾名思义，偏向某一个线程，当线程数目不多的时候，由于反复获取锁会使得我们的运行效率下降，于是出现了偏向级锁
• 在无竞争时，之前获得锁的线程再次获得锁时，会判断是否偏向锁指向我，那么该线程将不用再次获得锁，直接就可以进入同步块
• 总结一点：偏向级锁就是为了消除资源无竞争情况下的同步原语，进一步提高了程序的运行性能
• 在竞争激烈的场合，偏向锁会增加系统负担（因为每次都要加一次是否偏向的判断）
• 轻量级锁：
• 多个线程竞争同步资源时，没有获得资源的线程自旋等待锁释放
• 轻量级锁是由偏向锁升级来的，偏向锁运行在一个线程进入同步块的情况下，当第二个线程加入锁争用的时候，偏向锁就会升级为轻量级锁（又叫做锁膨胀）
• 轻量级锁适用于那些同步代码块执行的很快的场景，这样，线程原地等待很短很短的时间就能够获得锁了
• 轻量级锁主要有两种
• ①自旋锁
• ②自适应自旋锁
• 重量级锁：
• 根据上面推出，当多个线程竞争同一个锁时，会导致除锁的拥有者外，其余线程都会自旋，这将导致自旋次数过多，cpu效率下降，所以会将锁升级为重量级锁
• 多个线程竞争同步资源时，没有获得资源的线程阻塞等待唤醒

• 公平锁/非公平锁

• 公平锁：
• 加锁时考虑排队等待问题，按照申请锁的顺序，按照FIFO规则，先申请的线程先取得锁，其他线程进入队列等待锁的释放，当锁释放后，在队头的线程被唤醒
• 优点：所有的线程都能得到资源，不会饥饿等待
• 缺点：吞吐量会下降很多，队列里面除了第一个线程，其他的线程都会阻塞，cpu唤醒阻塞线程的开销会很大
• 非公平锁：
• 加锁时不考虑排队等待问题，直接尝试获取锁；如果此时恰好锁处于unlock，则不管有没有其他线程在等待，直接拿到锁；
• 否则就转化成公平锁的模式，进入队列等待
• 优点：可以减少CPU唤醒线程的开销，整体的吞吐效率会高点，CPU也不必取唤醒所有线程，会减少唤起线程的数量
• 缺点：非公平锁让获取锁的时间变得更加不确定，可能会导致在阻塞队列中的线程长期处于饥饿状态

• 可重入锁/非可重入锁

• 重入：
• 任意线程获取锁以后，这个线程再次获得该锁时不会阻塞
• 可重入锁：
• 又名递归锁，是指在同一个线程在外层方法获取锁的时候，再进入该线程的内层方法会自动获取锁
• 不会因为之前已经获取过还没释放而阻塞
• 非可重入锁：
• 当前线程再次获取当前线程已经获得的锁时
• 如果该锁仍被当前线程所持有，未被释放，那么将会出现死锁

• 共享锁/排他锁

• 排他锁(互斥锁)是指该锁一次只能被一个线程所持有
• 共享锁是指该锁可被多个线程所持有
• 获得共享锁的线程只能读数据，不能修改数