处理机调度与死锁

处理机,调度,死锁 · 浏览次数 : 11

小编点评

**死锁的检测与解除** **死锁检测** *允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生。** **死锁解除** * **重新启动**:系统由若干类资源构成,一类资源称为一个资源类;每个资源类中包含若干个同种资源,称为资源实例。** * **撤消进程**:系统中的每个资源类都包含一个资源实例,撤消进程的资源实例将被释放。** * **剥夺资源**:如果存在多个进程等待一个资源,剥夺该资源给一个等待该资源的进程。** * **进程回退**:进程在申请资源时回退,直到获得资源。** **死锁的生成条件** *资源分配图中没有环路,则系统中没有死锁。 *环路中存在资源分配的请求边,则系统中可能存在死锁。 **死锁的恢复条件** *当且仅当资源分配图是不可完全简化的。 **死锁的例子** *假定系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图所示。 **T0时刻的安全性** *允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生。 *一旦死锁发生则采取专门的措施,解除死锁并以最小的代价恢复操作系统运行。

正文

一、处理机调度的层次

概念

  • 按什么原则分配CPU:调度算法。
  • 何时分配CPU:调度时机。
  • 如何分配CPU:调度过程。
  • 周转时间:完成时间-进入时间。(注意:从进入系统到执行完成包括在后备队列中等待调度、在就绪队列中等待进程调度、执行以及等待I/O操作完成四部分时间,作业进入是指作业准备好被调度的状态)。
  • 平均周转时间:周转时间/执行时间。
  • 资源利用率:CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)。

处理机调度的层次

  1、高级调度(作业调度):调度对象是作业,主要功能:根据某种算法,决定将外存上处于后备队列中的哪几个作业调入内存,为它们创建进程、分配必要的资源,并将其放在就绪队列中
  2、低级调度(进程调度):调度对象是进程,主要功能:根据某种算法,决定就绪队列中哪个进程应获得处理机,并由分派程序将处理机分配给被选中的进程。(即分配哪个进程进入运行状态
  3、中级调度(内存调度):其主要目的是提高内存利用率和系统吞吐量。当一个进程暂时不能运行时,它被调至外存等待,此时该进程为挂起状态。当这个进程具备继续运行条件又稍有空闲时,由中级调度来决定,把外存上的那些已经具备运行条件的就绪进程重新调入内存,并修改其状态为就绪状态,挂在就绪队列上等待。

二、作业与作业调度

  作业:不仅包含通常的程序和数据,还应配有一份作业说明书,系统根据该说明书对程序的运行进行控制。在批处理系统中,是以作业为基本单位从外存调入内存的。

2.1 先来先服务(FCFS)调度算法

  就绪队列中最先进入队列的进程,先为之分配处理机运行,直至其结束或阻塞,将处理机分配给其他进程。有利于长作业,CPU繁忙型作业。可用于作业调度,也可用于进程调度。

2.2 短作业优先(SJF)调度算法

  作业越短,优先级越高(注意:若一个进程已进入,而其他进程未进入,尽管未进入的进程作业更短,但仍先执行已进入的作业)。可用于作业调度,也可用于进程调度。

2.3 优先级调度算法(PSA)

  可用于作业调度,也可用于进程调度。作业调度:选择-创建进程-放入就绪队列。进程调度:选择-分配处理机。

2.4 高响应比优先调度算法(HRRN)

  主要用于作业调度。每次计算所有符合被调度条件(已经进入)的作业的响应比(响应比=周转时间/处理时间),响应比高的先处理,然后再继续计算下一步中所有符合被调度条件的作业的响应比,直到所有作业被调度完毕。

2.5 时间片轮转调度算法

  主要用于进程调度,时间片大小需选择合适:太大退化为FCFS,太小切换频繁,用于运行时间太少。其举例具体实现过程如下:

2.6 多级队列调度算法

  主要用于进程调度。将就绪队列分成若干子队列,每个进程属于一个就绪队列,每个就绪队列采用一种调度算法

2.7 多级反馈队列调度算法

  调度机制:

  • 设置多个就绪队列,并为每一个就绪队列赋予不同的优先级,第一个队列优先级最高,依次降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同,在优先级越高的队列中,时间片越小。
  • 每个队列都采用FCFS算法。新进程进入内存后,先将其放在第一个队列末尾,按FCFS算法等待调度,轮到该进程执行时,若它能在时间片内完成,便可撤离系统,否则将其转入第二个队列的末尾,等待调度,若在第二个队列中运行一个时间片后仍未完成,转入第三个队列,依次类推。当进程最后被降到第n队列后,在第n队列中便采取RR方式运行。
  • 按队列优先级调度。仅当前面队列都空闲时,当前队列才能够执行。

三、死锁

3.1 死锁

3.1.1 死锁定义

  一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到该资源,这种现象称为进程死锁,这一组进程就称为死锁进程。
  结论:

  • 参与死锁的进程最少是两个
  • 参与死锁的进程至少两个已经占有资源
  • 参与死锁的所有进程都在等待资源
  • 参与死锁的进程是当前系统中所有进程的子集

3.1.2 产生死锁的必要条件

  • 互斥条件:涉及的资源是非共享的。
  • 不可抢占条件(不可剥夺条件):不能强行剥夺进程拥有的资源。
  • 请求和保持条件:进程在等待一新资源时继续占有已分配的资源。
  • 循环等待条件:存在一种进程的循环链,链中每一个进程已获得的资源同时被链中下一个进程请求。

3.1.3 处理死锁的方法

  • 预防死锁:通过设置某些限制条件,去破坏死锁四个必要条件中的一个或多个,来防止死锁。
  • 避免死锁:在资源动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免死锁的发生。
  • 检测死锁
  • 解除死锁:与检测死锁配套。

3.2 预防死锁

  互斥条件是非共享设备所必须的,不能改变

  • 破坏不可剥夺条件:一个已拥有资源的进程,若它再提出新资源要求而不能立即得到满足时,必须释放已经拥有的所有资源。以后需要时再申请。
  • 破坏请求和保持条件:系统要求所有进程一次性地申请在整个运行过程中所需的全部资源。若系统有足够资源则全部分配。
  • 破坏循环等待条件:系统中的所有资源都有一个确定的唯一号码,所有分配请求必须以序号上升的次序进行

3.3 避免死锁

  死锁避免定义:在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统可能发生死锁,则不予分配,否则予以分配。
  安全状态:如果系统能按某种顺序(如P 4,P 1,·,Pn,称为安全序列)为每个进程分配其所需的资源,直至所有进程都能运行完成。称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。

银行家算法

1、数据结构

  • 可利用资源向量Available。含有m个元素的数组,每一个元素代表一类可利用的资源数目。
  • 最大需求矩阵MAX。n×m矩阵,定义系统中n个进程中的每一个进程对m类资源的最大需求。
  • 分配矩阵Allocation。系统中每一类资源已分配给每一进程的资源数。
  • 需求矩阵Need。每一个进程尚需要的各类资源数。
  • Need[i,j]=Max[i,j]-Allocation[i,j]。

2、银行家算法

  • 若Request i[j]<=Need[i,j],继续检查;否则认为出错,请求大于需求。
  • 若Request i[j]<=Available[i,j],继续检查,否则,等待,资源不够。
  • 试探分配给进程Pi:Available[i,j]-=Request i[j];Allocation[i,j]+=Request i[j];Need[i,j]-=Request i[j]。
  • 系统执行安全性算法,若系统新状态是安全的,则分配完成,若系统新状态是不安全的,则恢复原状态,进程等待。

3、安全性算法

  • 设置两个向量:可利用资源work,work=Available;标记进程是够结束Finish=false(还未释放)
  • 从进程集合中选择满足条件的进程:1、Finish[i]=false;2、Need[i,j]<=work[j];若不存在,转(4)。
  • 执行Work[j]+=Allocation[i,j];Finish[j]=true;go to step2。
  • 若所有进程Finish[i]=true都满足,表示系统处于安全状态,否则,处于不安全状态。

4、银行家算法例子
  假定系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图所示。

  T0时刻的安全性:利用安全性算法对To时刻的资源分配情况进行分析(如图所示)可知,在To时刻存在着一个安全序列{P1,P3,P4,P2,P0},故系统是安全的。

  将剩下的资源执行银行家算法,看是否处于安全状态。

3.4 死锁的检测与解除

  死锁检测:允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生。一旦死锁发生则采取专门的措施,解除死锁并以最小的代价恢复操作系统运行。
  死锁解除:重要的是以最小的代价恢复系统的运行。方法如下:1、重新启动;2、撤消进程;3、剥夺资源;4、进程回退。
  用有向图描述进程的死锁。 系统由若干类资源构成,一类资源称为一个资源类;每个资源类中包含若干个同种资源,称为资源实例。二元组G=(V,E),V:结点集,分为P,R两部分,进程P={p1,p2,…,pn},资源R={r1,r2,…,rm},E:边的集合,其元素为有序二元组请求资源(pi,rj)或分配资源(rj,pi)。表示法:方框表示资源,圆圈表示进程,方框中的黑圆点表示资源实例。例如:

  死锁定理:如果资源分配图中没有环路,则系统中没有死锁,如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件。
  资源分配图化简

  • 找一个非孤立进程结点且只有分配边,去掉分配边,将其变为孤立结点
  • 再把相应的资源分配给一个等待该资源的进程,即将某进程的申请边变为分配边
  • 重复以上步骤,若所有进程成为孤立结点,称该图是可完全简化的,否则称该图是不可完全简化的。

死锁状态的充分条件是:当且仅当资源分配图是不可完全简化的。

与处理机调度与死锁相似的内容:

处理机调度与死锁

一、处理机调度的层次 概念 按什么原则分配CPU:调度算法。 何时分配CPU:调度时机。 如何分配CPU:调度过程。 周转时间:完成时间-进入时间。(注意:从进入系统到执行完成包括在后备队列中等待调度、在就绪队列中等待进程调度、执行以及等待I/O操作完成四部分时间,作业进入是指作业准备好被调度的状态

Qt信号槽与事件循环学习笔记

事件与事件循环 信号槽机制 事件与事件循环 在Qt中,事件(event)被封装为QEvent类/子类对象,用来表示应用内部或外部发生的各种事情。事件可以被任何QObject子类的对象接收并处理。 根据事件的创建方式和调度方式,Qt中事件可分为三类,分别是: 自发事件(Spontaneous even

深入理解操作系统中进程与线程的区别及切换机制(上)

进程是正在运行的程序的实例,它可以包含一个或多个线程。我们了解了进程的执行方式,包括早期单核处理器上的顺序执行以及引入多任务概念实现的伪并行。我们还探讨了进程的状态模型。进程可以处于就绪、运行、阻塞和结束等不同的状态。就绪状态表示进程已经准备好运行,但还没有被调度执行。运行状态表示进程正在执行。阻塞状态表示进程被阻塞,需要等待某些事件的发生才能继续执行。结束状态表示进程已经完成执行。

[转帖]鲲鹏性能优化十板斧——鲲鹏处理器NUMA简介与性能调优五步法

https://www.cnblogs.com/huaweicloud/p/12166354.html 1.1 鲲鹏处理器NUMA简介 随着现代社会信息化、智能化的飞速发展,越来越多的设备接入互联网、物联网、车联网,从而催生了庞大的计算需求。但是功耗墙问题以功耗和冷却两大限制极大的影响了单核算力的发

iOS APP启动广告实现方式 与 APP唤端调用

APP启动广告功能实现要从2个方面思考 一是UI方案,怎样处理广告页与主页之间的切换方式。 二是广告页展示时机,是使用后台实时广告数据还是使用本地缓存广告数据。后台数据方式获取广告最新但是用户要等待后台返回数据后才能展示,增加用户等待时间。使用本地缓存启动速度快但数据更新不及时。 UI方案实现 双W

3.0 Python 迭代器与生成器

当我们需要处理一个大量的数据集合时,一次性将其全部读入内存并处理可能会导致内存溢出。此时,我们可以采用迭代器`Iterator`和生成器`Generator`的方法,逐个地处理数据,从而避免内存溢出的问题。迭代器是一个可以逐个访问元素的对象,它实现了`python`的迭代协议,即实现了`__iter__()`和`__next__()`方法。通过调用`__next__()`方法,我们可以逐个访问迭代

[转帖]磁盘读速度巨慢使用arcconf工具调整后的二次优化

情况叙述:lvm文件系统出现损坏,格式为xfs,磁盘修复失败后该节点需要重新格式化处理,格式化后重新划分pv,vg,lv,做完之后应用反应读写的速度达不到应用使用的要求,与正常的相比速度不稳定 现象:time和dd测试速度后发现写的速度为10-20MB/s 解决1:yy3:~ # chmod +x

浅析 Jetty 中的线程优化思路

本文介绍了 Jetty 中 ManagedSelector 和 ExecutionStrategy 的设计实现,通过与原生 select 调用的对比揭示了 Jetty 的线程优化思路。Jetty 设计了一个自适应的线程执行策略(EatWhatYouKill),在不出现线程饥饿的情况下尽量用同一个线程侦测 I/O 事件和处理 I/O 事件,充分利用了 CPU 缓存并减少了线程切换的开销。这种优化思路

[转帖]《Linux性能优化实战》笔记(六)—— Linux 软中断与对应故障分析方法

中断是系统用来响应硬件设备请求的一种机制,它会打断进程的正常调度和执行,然后调用内核中的中断处理程序来响应设备的请求。 一、 为什么要有中断 举个生活中的例子,让你感受一下中断的魅力。比如说你订了一份外卖,但是不确定外卖什么时候送到,也没有别的方法了解外卖的进度,但是,配送员送外卖是不等人的,到了你

[flask]统一API响应格式

前言 在设计API返回内容时,通常需要与前端约定好API返回响应体内容的格式。这样方便前端进行数据反序列化时相应的解析处理,也方便其它服务调用。不同公司有不同的响应内容规范要求,这里以常见的JSON响应体为例: { "code": 200, "data": { "content": "this is