做网站要具备哪些,网站备案核验单怎么填,绿色食品网站开发步骤,品牌宣传推广方案2.22 什么是死锁
在多道程序环境下#xff0c;多个进程可以竞争有限数量的资源。当一个进程申请资源时#xff0c;如果这时没有可用资源#xff0c;那么这个进程进入等待状态。有时#xff0c;如果所申请的资源被其他等待进程占有#xff0c;那么该等待进程有可能再也无法…2.22 什么是死锁
在多道程序环境下多个进程可以竞争有限数量的资源。当一个进程申请资源时如果这时没有可用资源那么这个进程进入等待状态。有时如果所申请的资源被其他等待进程占有那么该等待进程有可能再也无法改变状态。这种情况称为 死锁。 2.23 死锁的四个必要条件 如果系统中以下四个条件同时成立那么就能引起死锁
互斥资源必须处于非共享模式即一次只有一个进程可以使用。如果另一进程申请该资源那么必须等待直到该资源被释放为止。请求与等待一个进程至少应该占有一个资源并等待另一资源而该资源被其他进程所占有。不可剥夺资源不能被剥夺。只能在持有资源的进程完成任务后该资源才会被释放。环路等待有一组等待进程 {P0, P1,…, Pn} P0 等待的资源被 P1 占有P1 等待的资源被 P2 占有…Pn-1 等待的资源被 Pn 占有Pn 等待的资源被 P0 占有。
注意只有四个条件同时成立时死锁才会出现。
2.24 解决死锁的方法
解决死锁的方法可以从多个角度去分析一般的情况下有预防避免检测和解除四种。
预防 是采用某种策略限制并发进程对资源的请求从而使得死锁的必要条件在系统执行的任何时间上都不满足。避免则是系统在分配资源时根据资源的使用情况提前做出预测从而避免死锁的发生。检测是指系统设有专门的机构当死锁发生时该机构能够检测死锁的发生并精确地确定与死锁有关的进程和资源。解除 是与检测相配套的一种措施用于将进程从死锁状态下解脱出来。
死锁的预防
只要破坏四个必要条件中的任何一个就能够预防死锁的发生。
破坏第一个条件 **互斥条件**使得资源是可以同时访问的这是种简单的方法磁盘就可以用这种方法管理但是我们要知道有很多资源 往往是不能同时访问的 所以这种做法在大多数的场合是行不通的。破坏第三个条件 非抢占也就是说可以采用 剥夺式调度算法但剥夺式调度方法目前一般仅适用于 主存资源 和 处理器资源 的分配并不适用于所有的资源会导致 资源利用率下降。
所以一般比较实用的 预防死锁的方法是通过考虑破坏占有并等待和循环等待。 1、静态分配策略 静态分配策略可以破坏死锁产生的第二个条件占有并等待。
所谓静态分配策略就是指一个进程必须在执行前就申请到它所需要的全部资源并且知道它所要的资源都得到满足之后才开始执行。进程要么占有所有的资源然后开始执行要么不占有资源不会出现占有一些资源等待一些资源的情况。静态分配策略逻辑简单实现也很容易但这种策略 严重地降低了资源利用率因为在每个进程所占有的资源中有些资源是在比较靠后的执行时间里采用的甚至有些资源是在额外的情况下才是用的这样就可能造成了一个进程占有了一些 几乎不用的资源而使其他需要该资源的进程产生等待 的情况。
2、层次分配策略 层次分配策略破坏了产生死锁的第四个条件(循环等待)。
在层次分配策略下所有的资源被分成了多个层次一个进程得到某一层次的一个资源后它只能再申请较高一层的资源。当一个进程要释放某层的一个资源时必须先释放所占用的较高层的资源按这种策略是不可能出现循环等待链的因为那样的话就出现了已经申请了较高层的资源反而去申请了较低层的资源不符合层次分配策略。
死锁的避免
1、预防死锁与避免死锁的区别 破坏 死锁产生的四个必要条件之一就可以成功 预防系统发生死锁 但是会导致 低效的进程运行 和 资源使用率 。 死锁的避免相反它的角度是允许系统中同时存在四个必要条件 只要掌握并发进程中与每个进程有关的资源动态申请情况做出 明智和合理的选择 仍然可以避免死锁因为四大条件仅仅是产生死锁的必要条件。 2、如何避免死锁银行家算法-典型 我们将系统的状态分为 安全状态 和 不安全状态 每当在未申请者分配资源前先测试系统状态若把系统资源分配给申请者会产生死锁则拒绝分配否则接受申请并为它分配资源。
如果操作系统能够保证所有的进程在有限的时间内得到需要的全部资源则称系统处于安全状态否则说系统是不安全的。很显然系统处于安全状态则不会发生死锁系统若处于不安全状态则可能发生死锁。
那么如何保证系统保持在安全状态呢通过算法其中最具有代表性的 避免死锁算法 就是 Dijkstra 的银行家算法。
银行家算法用一句话表达就是当一个进程申请使用资源的时候银行家算法 通过先 试探 分配给该进程资源然后通过 安全性算法 判断分配后系统是否处于安全状态若不安全则试探分配作废让该进程继续等待若能够进入到安全的状态则就 真的分配资源给该进程。银行家算法详情可见《一句话一张图说清楚——银行家算法》open in new window 。 死锁的避免(银行家算法)改善解决了 资源使用率低的问题 但是它要不断地检测每个进程对各类资源的占用和申请情况以及做 安全性检查 需要花费较多的时间。
死锁的检测
对资源的分配加以限制可以 预防和避免 死锁的发生但是都不利于各进程对系统资源的充分共享。 解决死锁问题的另一条途径是 死锁检测和解除
感觉死锁的检测和解除就像是 乐观锁 分配资源时不去提前管会不会发生死锁了等到真的死锁出现了再来解决嘛而 死锁的预防和避免 更像是悲观锁总是觉得死锁会出现所以在分配资源的时候就很谨慎。这种方法对资源的分配不加以任何限制也不采取死锁避免措施但系统 定时地运行一个 “死锁检测” 的程序判断系统内是否出现死锁如果检测到系统发生了死锁再采取措施去解除它。
1、进程—资源分配图 操作系统中的每一刻时刻的系统状态都可以用进程-资源分配图来表示进程-资源分配图是描述进程和资源申请及分配关系的一种有向图可用于检测系统是否处于死锁状态。
用一个方框表示每一个资源类。方框中的黑点表示该资源类中的各个资源。每个键进程用一个圆圈表示。用 有向边 来表示进程申请资源和资源被分配的情况。 图中 2-21 是进程-资源分配图的一个例子。
其中共有三个资源类每个进程的资源占有和申请情况已清楚地表示在图中。在这个例子中由于存在 占有和等待资源的环路 导致一组进程永远处于等待资源的状态发生了 死锁。
进程-资源分配图中存在环路并不一定是发生了死锁。因为循环等待资源仅仅是死锁发生的必要条件而不是充分条件。 图 2-22 便是一个有环路而无死锁的例子。
虽然进程 P1 和进程 P3 分别占用了一个资源 R1 和一个资源 R2并且因为等待另一个资源 R2 和另一个资源 R1 形成了环路但进程 P2 和进程 P4 分别占有了一个资源 R1 和一个资源 R2它们申请的资源得到了满足在有限的时间里会归还资源于是进程 P1 或 P3 都能获得另一个所需的资源环路自动解除系统也就不存在死锁状态了。
2、死锁监测步骤 1. 如果进程-资源分配图中无环路则此时系统没有发生死锁。2. 如果进程-资源分配图中有环路且每个资源类仅有一个资源则系统中已经发生了死锁。3. 如果进程-资源分配图中有环路且涉及到的资源类有多个资源此时系统未必会发生死锁。如果能在进程-资源分配图中找出一个 **既不阻塞又非独立的进程** 该进程能够在有限的时间内归还占有的资源也就是把边给消除掉了重复此过程直到能在有限的时间内 **消除所有的边** 则不会发生死锁否则会发生死锁。(消除边的过程类似于 **拓扑排序**)死锁的解除
当死锁检测程序检测到存在死锁发生时应设法让其解除让系统从死锁状态中恢复过来常用的解除死锁的方法有以下四种
立即结束所有进程的执行重新启动操作系统 这种方法简单但以前所在的工作全部作废损失很大。撤销涉及死锁的所有进程解除死锁后继续运行 这种方法能彻底打破死锁的循环等待条件但将付出很大代价例如有些进程可能已经计算了很长时间由于被撤销而使产生的部分结果也被消除了再重新执行时还要再次进行计算。逐个撤销涉及死锁的进程回收其资源直至死锁解除。抢占资源 从涉及死锁的一个或几个进程中抢占资源把夺得的资源再分配给涉及死锁的进程直至死锁解除。
2.25 协程是怎么实现的
1、协程执行
每个线程拥有自己的线程函数相应每个协程都拥有一个自己的协程函数。线程函数每次从函数的第一句开始执行参数局部变量等都保留在线程栈上函数返回清空栈信息。但是协程函数所有信息保留在堆中协程函数第一次执行在堆中动态分配一个协程上下文其中包含局部变量参数以及交出控制权的位置交出控制权后堆中信息不会被删除下一次被执行会从堆中恢复上下文信息。协程函数结束清空对应堆中的信息。 之前提过协程是基于线程的在用户层面上维护一个数据结构与多个线程(线程池)。协程函数在一个队列中维护多个线程(线程池)从队列中取出协程函数执行。
2、协程调度
协程没有cpu权限 无法使用cpu去完成调度。那么协程如何实现调度的呢
2.1、有栈协程
创建大量协程这些协程绑定在一个线程上(主协程)。并且每一个协程保留一个私有栈。协程执行到异步IO处交出控制权给主协程由主协程进行调度分配。
处于同一线程协程间不存在竞态关系。带有协程栈所以可以再任意节点交出控制权
有栈协程保存调用栈信息空间消耗太大空间使用共享栈来解决这种问题但是也会带来相应的copy问题。
2.2、无栈协程
封装系统异步IO函数作为协程函数协程一旦发起异步IO操作后保留当前信息控制权交付当前执行函数线程去队列中拉取另一个协程函数执行。异步IO完成后重新获取控制权恢复上下文环境继续执行之前协程函数。
只有在异步IO操作是才能交出控制权。无需住协程调度线程A执行异步协程B的IO操作协程B交出控制权线程C执行此时协程B恢复操作。因为B不在线程C中。所以可能存在竞态关系。
无栈协程需要标准语言与编译器支持。 由于协程必须支持 挂起/恢复因此对于挂起点的状态保存就显得极其关键。我们知道线程在切换时它的中断状态会保存在调用栈中。事实上协程的中断状态也可以通过开辟相应的调用栈来保存。因此按照是否开辟相应的调用栈我们可以将协程分为两类 有栈协程Stackful Coroutine每个协程都有自己的调用栈类似于线程的调用栈。无栈协程Stackless Coroutine协程没有自己的调用栈挂起点的状态通过状态机或闭包等语法来实现。 类似微信的 libco、阿里的 cooobjc、Golang 中的 goroutine、Lua 中的协程都是有栈协程类似 ES6、Dart 中的 await/async、Python 的 Generator、Kotlin 中的协程、C20 中的 cooroutine 都是无栈协程。 初识协程 2.26 多线程冲突了怎么办
多线程冲突也就是线程安全问题。线程安全也就是要确保在多线程访问的时候我们的程序还能按照我们预期的行为去执行或者说在多线程执行时可以得到我们预期的结果。而导致线程不安全的原因主要有原子性和可见性。 如果是原子性导致的可以通过加锁或者使用互斥信号量来解决。总之就是对临界区代码进行互斥访问确保同一时间只有一个线程在执行临界区代码。 那什么是可见性导致呢比如说比如说有一个共享变量 i 开两个线程去处理 i 另外开两个进程去读取 i 这个时候就会产生意想不到的结果也就是线程不安全。 那可见性导致的线程不安全怎么去解决呢 可见性导致的线程不安全的例子 // The following code demonstrates a thread safety issue caused by visibility
// 可见性导致的线程安全问题public class VisibilityIssue {private static boolean stop false;public static void main(String[] args) throws InterruptedException {Thread backgroundThread new Thread(() - {int i 0;while (!stop) {i;}System.out.println(Background thread stopped. Counted up to i);});backgroundThread.start();Thread.sleep(1000);stop true; // 更改了缓存的值但是由于写时复制导致线程不可见更改后的值System.out.println(Main thread stopped background thread.);}
}// One solution to the visibility issue causing thread safety problems is to use the volatile keyword
// 使用volatile关键字解决可见性导致的线程安全问题public class VisibilityIssue {// 使用 volatile 当值发生变化时直接写回地址private static volatile boolean stop false;public static void main(String[] args) throws InterruptedException {Thread backgroundThread new Thread(() - {int i 0;while (!stop) {i;}System.out.println(Background thread stopped. Counted up to i);});backgroundThread.start();Thread.sleep(1000);stop true;System.out.println(Main thread stopped background thread.);}
}这其实是线程同步问题。 2.27 孤儿进程与僵尸进程的区别
我们知道在unix/linux中正常情况下子进程是通过父进程创建的子进程在创建新的进程。子进程的结束和父进程的运行是一个异步过程,即父进程永远无法预测子进程 到底什么时候结束。 当一个进程完成它的工作终止之后它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。 孤儿进程一个父进程退出而它的一个或多个子进程还在运行那么这些子进程将成为孤儿进程。孤儿进程将被 init进程(进程号为1) 所收养并由 init 进程对它们完成状态收集工作。
僵尸进程一个进程使用fork创建子进程如果子进程退出而父进程并没有调用wait或waitpid获取子进程的状态信息那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。
2.28 后台进程和守护进程有什么区别
1、守护进程已经完全脱离终端控制台了而后台程序并未完全脱离终端(在终端未关闭前还是会往终端输出结果); 2、守护进程在关闭终端控制台时不会受影响而后台程序会随用户退出而停止需要在以 nohup command 格式运行才能避免影响; 3、守护进程的会话组和当前目录文件描述符都是独立的。后台运行只是终端进行了一次fork让程序在后台执行这些都没改变;
2.29 守护进程的特点
守护进程(Daemon)是在后台运行的一种特殊进程它脱离于终端从而可避免进程被任何终端所产生的信号打断它在执行进程中的产生信息也不在任何终端上显示。守护进程周期性地执行某种任务或等待处理某些发生的事件Linux的大多数服务器就是用守护进程实现的。
2.30 操作系统有哪几种锁
在Linux中常见的锁有互斥锁、读写锁、自旋锁、RCU。
1. 互斥锁mutex
互斥锁mutex用于保证在任何时刻都只能有一个线程访问该对象。当获取锁操作失败时线程会进入睡眠等待锁释放时被唤醒。
2. 读写锁 rwlock
读写锁rwlock分为读锁和写锁。处于读操作时可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态直到写锁释放时被唤醒。 注意写锁会阻塞其它读写锁。当有一个线程获得写锁在写时读锁也不能被其它线程获取写者优先于读者一旦有写者则后续读者必须等待唤醒时优先考虑写者。 适用于读取数据的频率远远大于写数据的频率的场合。
3. 自旋锁spinlock
自旋锁spinlock在任何时刻同样只能有一个线程访问对象。但是当获取锁操作失败时不会进入睡眠而是会在原地自旋直到锁被释放。这样节省了线程从睡眠状态到被唤醒期间的消耗在加锁时间短暂的环境下会极大的提高效率。但如果加锁时间过长则会非常浪费CPU资源。
4. RCU
RCU即read-copy-update在修改数据时首先需要读取数据然后生成一个副本对副本进行修改。修改完成后再将老数据update成新的数据。 使用RCU时读者几乎不需要同步开销既不需要获得锁也不使用原子指令不会导致锁竞争因此就不用考虑死锁问题了。而对于写者的同步开销较大它需要复制被修改的数据还必须使用锁机制同步并行其它写者的修改操作。在有大量读操作少量写操作的情况下效率非常高。
