内容纲要

死锁:是指各并发进程互相等待对方所拥有的资源,且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源,各并发进程不能继续向前推进的状态。

产生死锁的原因:

  • 资源数  <  要求该种资源的进程数
  • 进程的推进顺序非法

产生死锁的四个必要条件:

  • 互斥条件。并发进程所要求和占有的资源是不能同时被两个以上进程使用或操作的,进程对它所需要的资源进行排他性控制。
  • 不剥夺条件。进程所获得的资源在未使用完毕之前,不能被其他进程强行剥夺,而只能由获得该资源的进程自己释放。
  • 部分分配。进程每次申请它所需要的一部分资源,在等待新资源的同时,继续占用已分配到的资源。
  • 环路条件。存在一种进程循环链,链中每一个进程已获得的资源同时被下一个进程所请求。

死锁的消除方法:一般可分为预防、避免、检测与恢复3种。

死锁预防:是采用某种策略,限制并发进程对资源的请求,从而使得死锁的必要条件在系统执行的任何时间都不满足。

  • 打破资源的互斥和不可剥夺这两个条件
  • 打破资源的部分分配这个死锁产生的必要条件
  • 打破死锁的环路条件

死锁避免:是指系统在分配资源时,根据资源的使用情况提前做出预测,从而避免死锁的发生。通过资源分配算法分析系统是否存在一个并发进程的状态序列,在确定不会进程循环等待的情况下,才将资源真正分配给进程,以保证并发进程不会产生死锁。

  • 安全状态是指系统至少存在一个安全序列<P1, P2, …, Pn>,按照这个序列为进程分配资源,直到满足最大需求,每个进程都可顺序完成。
  • 若系统不存在这样一个安全序列,则系统处于不安全状态。

银行家算法:是以银行系统所采用的借贷策略(尽可能放贷、尽快回收资金)为基础而建立的算法模型。在此模型中,进程相当于贷款客户,系统资源相当于资金,调度程序相当于银行家(贷款经理)。

算法思路:

  1. 在某一时刻,各进程已获得所需的部分资源。有一进程提出新的资源请求,系统将剩余资源试探性地分配给该进程。
  2. 如果此时剩余资源能够满足余下的某些进程的需求,则将剩余资源分配给能充分满足的、资源需求缺口最大的进程,运行结束后释放的资源再并入系统的剩余资源集合。
  3. 反复执行第2步,直到所有的进程都能够获得所需而运行结束。说明第1步的进程请求是可行的,系统处于安全状态,相应的进程执行序列称为系统的安全序列。如果所有的进程都试探过而不能将资源分配给进程,即不存在安全序列,则系统是不安全的。
//n:系统中进程数量
//m:资源类数量
//Available[1…m]:每一种资源的资源数量
//Max[1…n, 1…m]:每一个进程对某一类资源的最大的需求量
//Allocation[1…n, 1…m]:当前系统中,哪些进程得到了哪些资源
//Need[1…n, 1…m]:每一个进程还需要多少资源
//Request[1…n, 1…m]:本次进程对资源的申请是多少
当进程Pi提出资源申请时,系统执行以下步骤
1、若Request[i] <= Need[i],转2;否则报错返回
2、若Request[i] <= Available,转3;否则进程等待
3、假设系统分配了资源,则有:
Available = Available - Request[i];
Allocation[i] = Allocation[i] + Request[i];
Need[i] = Need[i] - Request[i];

死锁检测与恢复:是指系统设有专门的机构,当死锁发生时,该机构能够检测到死锁发生的位置和原因,并能通过外力破坏死锁发生的必要条件,从而使得并发进程从死锁状态中恢复出来。

检测方法:

  • 有限状态转移图
  • PetriNet

恢复方法:

  • 撤销进程:撤销死锁进程,回收资源,优先选择占用资源最多或者撤销代价最小的,撤销一个不行就继续选择撤销进程,直至解除死锁。
  • 剥夺资源:剥夺死锁进程资源再分配,选择原则同上。
  • 重启:重新启动死锁进程,甚至重启操作系统。
  • 回滚:根据系统保存的检查点,使进程或系统回退到死锁前的状态。

线程:是进程中的一个实体,是系统独立调度和分派的基本单位。有时又被称为轻权进程或轻最级进程(light weight process)。

线程与进程区别:

  • 进程Process:资源分配单位(存储器、文件)和CPU 调度(分派)单位。又称为“任务(task)”,多线程是指OS 支持在一个进程中执行多个线程的能力。
  • 线程Thread:作为CPU 调度单位,而进程只作为其他资源分配单位,只拥有必不可少的资源,如:线程状态、寄存器上下文和栈,同样具有就绪、阻塞和执行三种基本状态。
  • 调度:在传统的操作系统中,作为拥有资源的基本单位和独立调度、分派的基本单位都是进程;引入线程的操作系统中,线程作为调度、分派的基本单位;进程作为拥有资源的基本单位;同一进程中,线程的切换不会引起进程的切换;从一个进程中的线程切换到另一个进程中的线程时,将会引起进程的切换。
  • 并发性:在引入线程的操作系统中,不仅进程之间可并发执行,在一个进程中的多个线程之间也可并发执行,使得操作系统具有更好的并发性,从而提高系统资源的利用率和系统吞吐量。
  • 拥有资源:不论是传统的操作系统,还是引入线程的操作系统,进程都可以拥有资源,是系统中拥有资源的基本单位;一般而言,线程不拥有系统资源(除少量必不可少的资源),但它可以访问其隶属进程的资源,如一个进程的代码段、数据段等。
  • 系统开销:线程的创建、撤销、切换快,操作系统所付出的开销明显小于进程;通信方面:由于同进程内线程间共享进程的代码、数据、内存和文件资源,可直接进行不通过内核的通信;而进程间的通信需要通过内核进行,以提供保护和通信所需机制。

线程的实现:

内核线程(kernel-level thread):线程在核心空间实现,核心知道线程存在,并对它们实施管理。

  • 内核维护进程和线程的上下文信息;
  • 线程切换由内核完成;
  • 一个线程发起系统调用而阻塞,不会影响其他线程的运行;
  • 时间片分配给线程,所以多线程的进程获得更多CPU 时间。

用户线程(User-level thread):把线程库整个地放在用户空间,核心对线程一无所知,核心只对常规进程进行管理,并不知道线程是否存在。

  • 应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。
  • 调度由应用软件内部进行,通常采用非抢先式和更简单的规则,也无需用户态/核心态切换,所以速度特别快。
  • 一个线程发起系统调用而阻塞,则整个进程在等待。
  • 时间片分配给进程,多线程则每个线程就慢。

轻权进程(Light Weight Process):

  • 它是内核支持的用户线程。一个进程可有一个或多个轻权进程,每个轻权进程支持一个或多个用户线程,并映射到一个内核线程;
  • 由于同时提供内核线程控制机制和用户线程库,因此可很好地把内核线程和用户线程的优点结合起来。

混合线程(hybrid thread):

处理机调度:处理机管理的工作是对CPU 资源进行合理的分配使用,以提高处理机利用率,并使各用户公平地得到处理机资源。

作业的状态及其转换:

  • 提交状态:作业处于从输入设备进入外存的过程;
  • 收容状态:作业的全部信息被输入到输入井,尚未被调度执行;
  • 完成状态:作业运行完毕,所占资源尚未被收回

调度的层次:

  • 第1 级:作业调度(宏观调度、高级调度):对外存输入井上的大量作业进行选择,对选择的作业分配资源,建立相应进程。作业执行完毕时,回收资源。
  • 第2 级:交换调度(中级调度):将处于外存交换区中的就绪状态或等待状态的进程调入内存,或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。
  • 第3 级:进程调度(微观调度、低级调度):选取一个处于就绪状态的进程占用处理机,之后,进行上下文切换以便建立与占用处理机进程相适应的执行环境。
  • 第4 级:线程调度:选取一个处于就绪状态的线程进入执行状态。

进程调度方式:

  • 不可剥夺方式:不可剥夺方式也被称为非抢占方式。采用这种调度方式时,一旦把处理机分配给某个进程,该进程将一直执行下去,直到运行完毕或因某种原因不能运行,才把处理机分配给其它进程,决不允许其它进程强占正在运行进程占有的处理机。
  • 可剥夺方式:可剥夺方式也被称为抢占方式。在这种方式下,允许一个进程按照某种原则,抢占其它进程占有的处理机。抢占采用优先权原则的比较多,也就是说,如果一个进程比正在运行进程的优先级高,则它可以抢占处理机而运行。

进程调度的时机:

  • 正在执行的进程执行完毕
  • 执行进程自己调用阻塞原语使自己变为等待状态
  • 将睡眠的进程唤醒,将其加入就绪队列后,执行进程调度程序
  • 执行进程调用P 操作,因资源不足被阻塞,(count‐1<0):阻塞,执行进程调用V 操作,(count+1<=0) :唤醒等待的进程
  • 执行进程因I/O 被阻塞
  • 分时系统中时间片用完
  • 系统调用执行完毕,从系统程序返回到用户程序时,进行进程调度
  • 可剥夺方式下,就绪队列中某进程优先级高于执行进程

进程调度性能评价:

  • 定性衡量:调度的可靠性、调度的简洁性
  • 定量衡量:CPU 利用率、进程在队列中的等待时间与执行时间之比

作业调度目标:

  • 公平性:对所有作业应该是公平的
  • 利用率:应使设备有高的利用率
  • 作业量:每天执行尽可能多的作业
  • 响应时间:有快的响应时

作业调度性能衡量:用户的角度、处理机的角度、算法实现的角度

用户的角度:

  • 周转时间:作业从提交到完成(得到结果)所经历的时间。包括:在收容队列中等待,CPU 上执行,就绪队列和阻塞队列中等待,结果输出等待。
  • 带权周转时间

处理机的角度:

  • 吞吐量:单位时间内所完成的作业数,与作业本身特性和调度算法都有关系——一般该准则适合于批处理系统,强调单位时间内可以完成的作业数
  • 处理机利用率:——适合大中型主机,强调充分利用处理机资源
  • 各种设备的均衡利用:如CPU 繁忙的作业和I/O 繁忙(指次数多,每次时间短)的作业搭配——适合大中型主机,同时运行多种类型的作业,强调对CPU 繁忙和I/O 繁忙作业的搭配调度

算法实现的角度:

  • 易于执行
  • 执行开销比

调度算法:也称为调度策略

●先来先服务调度算法(FCFS):将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列,并按照先来先服务(First Come First Serve,FCFS)的方式进行调度处理。

短作业(进程)优先调度算法(SJF):以进入系统的作业所要求的CPU服务时间为标准,总选取估计所需CPU时间最短的作业优先投入运行。

●最短剩余时间优先(SRTF):若一就绪状态的新作业所需的CPU时间比当前正在 l执行的作业剩余任务所需CPU时间还短,SRTF将打断正在执行作业,将执行权分配给新作业。SRTF将SJF算法改为抢占式,因此只要有新作业进入就绪队列,就可能会引发进程切换。

●最高响应比优先法(Highest Response-ratio Next, HRN):是FCFS与SJF两种算法的折衷——既考虑作业等待时间,又考虑作业的运行时间,既照顾短作业又不使长作业等待过久,改善了调度性能,仍属于非抢占式算法。响应比 =1 +(已等待的时间 / 估计运行时间)

●时间片轮转调度算法:将CPU的处理时间分成固定大小的时间片。 如果一个进程在被调度选中之后用完了系统规定的时间片,但未完成要求的任务,则它自行释放自己所占有的 CPU而排到就绪队列的末尾,等待下一次调度。 同时,进程调度程序又去调度当前就绪队列中的第一个进程或作业。

●优先权调度算法:系统或用户首先按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。该算法的核心是确定进程或作业的优先级。

●多级反馈队列:

  • 根据作业的性质和类型不同,将就绪队列再分为若干个子队列,每个进程分属于一个队列。
  • 在多级队列的基础上,不但设多个队列,且为每个队列赋予不同的优先权,第一个队列的优先权最高,第二个队列次之,其余队列的优先权逐个降低。
  • 各个队列中的进程执行时间片大小逐渐增大。
  • 新进程投入第一个队列。
  • 调度从第一个队列进行,仅当第一个队列为空时,才调度第二个队列中的进程。

最后修改日期:2020年4月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。