进程的描述与控制VS处理机调度与死锁

成也进程,败也进程,不为成败,只为进程。

进程的描述与控制

前驱图

每个结点可用来表示一个进程或进程段,乃至一条语句,结点间的有向边则表示两个结点间存在偏序或前趋关系。

例如上图P1与P2之间有前趋关系,所以P1与P2只能顺序执行。再如P2与P3之间没有前趋关系,所以P2与P3可以并发执行。

说白了就是有向无环图,可以利用拓扑排序进行执行。

进程概述

简单理解,进程就是程序段+数据段+PCB。

由来

由于多道程序环境下,程序的执行属于并发执行,此时它们将失去封闭性,并且具有间断性,以及运行结果不可在现性的特征。由此决定了程序是不能参与并发执行的,否则,程序的运行便失去了意义。为了能使程序并发执行,并且对并发执行的程序加以描述和控制,人们引入了进程。

为使每个并发执行程序(含数据)都能独立运行,在操作系统中加入一个专门的数据结构——进程控制块(Process Control Block,PCB)

系统利用PCB描述进程的基本情况和活动过程。一般情况下,我们把进程实体简称为进程,所谓创建进程就是创建进程实体中的PCB;撤销进程就是撤销进程的PCB。

定义

  • 进程是程序的一次执行。
  • 进程是一个程序及其数据在处理机尚顺序执行是所发生的活动。
  • 进程是具有独立功能的程序在一个数据集合上执行的过程,它是系统执行资源分配和调度的一个独立单位

特征

  • 动态性:进程是进程实体的执行过程,由创建而生,调度而执行,撤销而亡。进程实体具有生命周期,而程序仅是一组有序命令的集合,存在于某种介质之上,因而是静态的。
  • 并发性:多个进程实体同存于内存之中,且能在一段时间同时运行。程序没有PCB,因而不能并发。
  • 独立性:进程实体是一个能独立运行,独立获得资源,独立接受调度的基本单位。而程序没有PCB,固不能执行以上操作。
  • 异步性:进程是按异步方式运行的,即按各自独立的、不可预知的速度推进,因而结果不可再现。为此,OS中引入进程的概念,并配置相应的同步机制。

状态及转换

三基态:

  • 就绪状态:进程已处于准备好运行的状态,只差CPU,在就绪队列等待调度。
  • 执行状态:进程已获得CPU,并立即执行。
  • 阻塞状态:正在运行的进程由于发生某种事件(I/O请求,申请缓冲区失败等)暂时无法继续执行,而让受阻进程处于暂停状态。进入阻塞队列。阻塞时进程自身的主动行为。

创建与终止状态:

  • 创建状态:申请空白PCB,并向PCB填写控制和管理进程的信息,然后分配资源,最后转入就绪队列中。
  • 终止状态:等待操作系统善后处理,然后PCB清零,返还系统。

挂起状态:

当操作作用于某个进程时,该进程处于静止状态。

引入
  1. 终端用户需要。例如运行时改bug。
  2. 父进程请求。
  3. 符合调节需要。
  4. 操作系统需要。例如检查运行情况。

PCB

PCB中的信息

  1. 进程描述符:进程标识符用于唯一标识进程。
  2. 处理机状态:进程切换时保留现场以及现场恢复。
  3. 进程调度信息:进程状态及相关进程调度信息。
  4. 进程控制信息:用于进程控制所需信息。

进程控制

进程控制一般由OS原语实现。

操作系统内核

  1. 支撑功能
    • 中断处理。
    • 始终处理。
    • 原语操作。原语由若干指令组成,用于完成一定功能的过程。原子操作,一个操作中所有行动要么全做,要么不做。
  2. 资源管理功能
    • 进程管理。
    • 存储器管理。
    • 设备管理。

进程的创建与终止

创建原语:Creat

终止原语:Holt

进程的阻塞与唤醒

阻塞原语:block

唤醒原语:wakeup

进程的挂起与激活

挂起原语:suspend

激活原语:active

进程同步

硬件同步机制

  1. 关中断
  2. 利用Test-and-Set指令实现互斥
  3. 利用Swap指令实现进程互斥

信号量

  1. 整型信号量
  2. 记录型信号量
  3. AND型信号量
  4. 信号量集

管程

信号量机制功能强大,但使用时对信号量的操作分散,而且难以控制,读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中,操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰,便于维护和修改,易于保证正确性。

经典进程同步问题

生产者-消费者问题

读者-写者问题

哲学家进餐问题

进程间通信

  1. 共享存储器系统

  2. 管道(pipe)通信系统

  3. 消息传递系统

    • 消息传递的实际功能以一对原语的形式提供:

      • send(destination,message)
      • receive(source,message)

      这是进程间进程消息传递所需要的最小操作集。

      一个进程以消息的形式给另一个指定的目标进程发送消息;

      进程通过执行receive原语接收消息,receive原语中指明发送消息的源进程和消息。

  4. 客户机-服务机系统

    • 套接字socket

线程

作为调度和分派的基本单位。

每个线程有一个线程控制块TCB。

处理机调度与死锁

处理机调度

无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,以使之执行。

处理机调度层次

高级、中级和低级调度作业从提交开始直到完成,往往要经历下述三级调度:

高级调度:(High-Level Scheduling)又称为作业调度,它决定把外存上后备作业调入内存运行;

低级调度:(Low-Level Scheduling)又称为进程调度,它决定把就绪队列的某进程获得CPU;

中级调度:(Intermediate-Level Scheduling)又称为在虚拟存储器中引入,在内、外存对换区进行进程对换。把不能正常运行的进程调至外存等待。

处理机调度算法

CPU利用率 = CPU有效工作时间 / (CPU有效工作时间 + CPU空闲等待时间)

批处理系统

周转时间Ti = 完成时间 - 到达时间

平均周转时间T = 1/n( T1 + …… + Ti + …… + Tn )

带权周转时间为周转时间/运行时间(越小越好)

分时系统

响应时间快,均衡性好。

实时系统

考虑截至时间,提高可预测性。

作业与作业调度

作业(Job)

程序的集合+数据的集合+作业说明书+JCB。

三个状态:后备状态,运行状态,收容状态。

三个阶段:收容阶段(创建JCB),运行阶段,完成阶段(回收JCB)。

任务

  1. 接纳多少作业
  2. 接纳哪些作业

作业调度算法

先来先服务算法(first-come first-served,FCFS)

系统按照作业到达的优先顺序调度。

不利于短作业。

短作业优先算法(short job first,SJF)

系统以作业长短为优先级。

不利于长作业,容易出现进程饥饿现象。

优先级调度算法(priority-scheduling algorithm,PSA)

根据作业紧迫程度,由外界赋予优先级。

高响应比有限调度算法(Highest Rseponse Ratio Next,HRRN)

动态优先级,根据长短赋初值,根据等待时间加权。作业越短,初值越大,等待时间越长,加权越大。

Rp = 响应时间/要求服务时间

进程调度

方式

剥夺方式

当一个进程正在运行时,系统可以基于某种原则,剥夺已分配给它的处理机,将之分配给其它进程。剥夺原则有:优先权原则、短进程优先原则、时间片原则。

非剥夺方式

分派程序一旦把处理机分配给某进程后便让它一直运行下去,直到进程完成或发生某事件而阻塞时,才把处理机分配给另一个进程。

任务

  1. 保存处理机现场信息。
  2. 按某种算法选取进程。
  3. 把处理器分配给进程。

进程调度算法

进程调度也称为低级调度,它所调度的对象为进程(或者内核级线程),而进程调度算法主要有以下几种:

基于时间片的轮转调度算法

它的原理通俗来讲就是队列中每一个进程都获得了一定的执行时间,从几ms到几百ms,当一个执行时间结束,计时器会发出一个信号,此时正在执行的进程将被中断,同时此进程将被放在队列的末尾,然后执行这时候的队列的队首进程,因此队列中每一个进程都将获得一定时间执行。

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

先来先服务调度算法是一种最简单的调度算法,可用于作业调度,也可用于进程调度。

短作业优先调度算法(SJ(P)F)

短作业(进程)优先调度算法是指短作业或者短进程的优先调度算法,它们分别作用于作业调度和进程调度,它是先来先服务调度算法的一种优化版本。

高优先权优先调度算法

为了解决在短作业优先调度算法中进程的紧迫程度问题,我们引入高优先权优先调度算法,高优先权调度算法的方法也很简单,就是在队列中选取优先权最高的进程装入内存,该算法又分为以下两类:

①非抢占式优先权算法
如果系统已经分配好一个优先权最高的进程,它会一直被执行,直到结束或者因为某事件放弃执行,此时系统才会选择另外一个优先权最高的进程,这种调度算法主要被用于批处理系统中。

②抢占式优先权算法
系统在队列中把一个优先权最高的进程执行,但如果在执行中又出现一个优先权更高的进程,此时当前进程被停止,换入另外一个优先权更高的进程,这种调度算法主要被用于要求比较严格的实时系统,以及对性能要求较高的批处理和分时系统中。

优先权的类型:

优先权的类型被分为静态优先权和动态优先权。

静态优先权就是给定某个整形数字来表示进程的优先级,数字越小表示优先级越高,数字越大,进程优先级越低。

动态优先权随着进程的创建而被创建,可以随着进程的推进或者等待时间而变化。

多队列调度算法

进程就绪队列由一个拆成多个,不同类型进程分配不同就绪队列,不同就绪队列采用不同算法。一个就绪队列可以设置不同优先级,不同就绪队列本身也可设优先级。

系统根据不同的用户选用不同的调度策略。

多级反馈队列调度算法

设置多个就绪队列,每个队列的优先级逐渐降低,同时每个队列的执行时间也各不相同,优先级越高的队列,执行时间越短,优先级越低的队列,执行时间越长。
当一个进程进入内存后,首先进入第一个队列的末尾,按照先来先服务的调度算法进行调度,如果在第一个队列的执行时间内未执行完成,此时把此进程放入第二个队列的末尾,按照之前的方法进行执行,直到在某一个队列的队首执行完成。

当第一个队列全部执行完成,此时系统才会执行第二个队列,但是如果此时又有新的进程进入,此时执行完毕这个时间段,立刻把此进程分配给新的作业。

根据公平原则的调度算法

公平分配每个进程相同的处理机时间,或按进程比例公平分配用户相同的处理机时间。

死锁

锁与信号量

锁强调于资源,信号量强调于执行次序。

资源分类

重用性资源与消耗性资源

可抢占性资源与不可抢占资源

死锁起因

源于多个进程对资源的争夺,不仅对不可抢占资源金进行争夺时容易产生死锁,而且对消耗性资源抢夺也会产生死锁。还有就是进程推进不当引起死锁。

死锁产生必要条件

  1. 互斥条件(不能破坏该条件)
  2. 请求与保持条件
  3. 不可抢占条件
  4. 循环等待条件

处理死锁的方法

以下四种方法从上往下防范程度逐渐减弱,但资源利用率与并发程度逐渐提高。

预防死锁

破坏”请求保持条件“
  1. 一次性分配所有需要的资源。
  2. 用到时再调用资源,用完即释放资源。
破坏”不可抢占条件“

调用资源时如果资源被占用,则必须释放已有所有资源,用时再调用。

破坏”循环等待条件“

先给进程编号并排序,再按照顺序分配资源。

避免死锁

银行家算法

银行家算法的数据结构
可利用资源向量(Available):系统还可以分配的资源

最大需求矩阵(Max):进程的最大资源需要

分配矩阵(Alloction):进程已经获得的资源

需求矩阵(Need):进程还需要获得的资源

银行家算法

假设 P1 进程提出请求 K 个资源

如果 K <= Need,就继续步骤;否则出错,因为请求资源 K 不能超过还需要获得的资源

如果 K <= Available,就继续步骤;否则出错,因为请求资源 K 不能超过系统还可以分配的资源

Available系统试探分配资源,并修改下列数据

Available = Available - K;表示分配给 P1 K 个资源后,还剩多少系统可分配资源

Allocation = Allocation + K;表示 P1 已经获得的资源

Need = Need - K;表示进程 P1 还需要获得的资源

此时系统执行安全性算法,计算进程是否处于安全性状态

PS:此时是执行的试探分配,为的是检查进程是否处于安全状态,不处于则试探分配作废

安全性算法

安全性算法是银行家算法在第五步执行的子算法,用于检查进程的安全状态

两个向量

工作向量(Work):系统提供给进程的各类资源数目

Finish:表示系统是否有足够的资源分配给进程,这是一个布尔值。初始化为 false。

算法描述

在进程集合中找到下述条件的进程

Finish[ i ] = false;

Need <= Work

进程执行完毕

Work = Work + Allocation

Finish [ i ] = true

返回继续执行 1 ,寻找其他的进程分配资源

若所有的 Finish 为 true 则安全

检测死锁

资源分配图。

解除死锁

杀死进程。


文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!