精华内容
参与话题
问答
  • 处理机调度

    2019-11-03 20:12:52
    调度层次 高级调度(作业调度) 中级调度(进程调度) 低级调度 作业调度 FCSF先来先服务,作业等待时间...该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)会被及时处理;由于作业(进程...
    1. 调度层次
      1. 高级调度(作业调度)
      2. 中级调度(进程调度)
      3. 低级调度
    2. 作业调度
      1. FCSF先来先服务,作业等待时间得长短。比较有利于长作业(进程),而不利于短作业(进程)。
      2. SJF短作业优先,作业的运行时间。
        1. 优点:能有效的降低作业的平均等待事件,提高系统吞吐量。
        2. 缺点:对长作业不利;该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)会被及时处理;由于作业(进程)的长短含主观因素,不一定能真正做到短作业优先。

      1. 高响应比优先  

    优先权=等待时间+要求服务时间/要求服务时间

      1. RR轮转调度算法,时间片的确定要适中
      2. 多级反馈队列
      3. EDF最早截至时间优先

    下图中有两个周期性任务,任务A的周期时间为20ms,每个周期的处理时间为10ms;任务B的周期时间为50ms,每个周期的处理时间为25ms

      1. LLF最低松弛度优先

    松弛度=必须完成时间-其本身的运行时间-当前时间

    进程切换条件:有任务完成;有任务松弛度降到0。

    1. 死锁
      1. 定义:是指多个进程在运行过程中因为争夺资源而造成的一种僵局,当进程处于这种状态时,若无外力作用,他们都将无法再向前推进
      2. 原因:竞争资源(不可抢占资源,可消耗资源),进程间推进顺序非法。
      3. 产生死锁得必要条件:互斥条件、请求和保持条件、不可抢占(不可剥夺)条件、环路等待条件
      4. 处理死锁的基本方法:
        1. 预防死锁:破坏产生死锁得必要条件,其中破坏互斥条件是最不实际的
          1. 破坏“请求和保持”条件:系统规定所有进程在开始运行之前,都必须一次性的申请其在整个运行过程所需的全部资源
          2. 破坏“不剥夺”条件
          3. 破坏“环路等待”条件:所有进程对资源的请求必须严格按照资源序号递增的次序提出
        2. 预防死锁:银行家算法、安全性算法
        3. 检测死锁:资源分配图,死锁定理
        4. 解除死锁:剥夺资源(从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。),撤销进程(最简单的是让全部进程都死掉;温和一点的是按照某种顺序逐个撤销进程,直至有足够的资源可用,使死锁状态消除为止。)
    2. 银行家算法
      1. 安全状态

      1. 银行家算法

    T0时刻的安全性:用安全性算法对T0时刻的资源分配情况进行分析,存在着一个安全序列{P1,P3,P4,P2,P0},故系统是安全的

    P1发出资源请求向量Request1(1,0,2),系统按银行家算法检查:

    (1)Request1(1,0,2)<=Need1(1,2,2)

    (2)Request1(1,0,2)<=Available1(3,3,2)

    (3)系统先假定可为P1分配资源,并修改向量Available,Allocation1,Need1

    (4)再利用安全性算法检查此时系统是否安全。如下表:

    由安全性检查得知,能找到一个安全序列{P1,P3,P4,P0,P2},因此,系统是安全的,可以立即将P1所申请的资源分配给它。

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

    展开全文
  • 本文主要是介绍处理机调度的目标,策略和评价方法等。因为处理机调度程序不可能选择全部驻留在外存的进程,因此,在调度一个进程占有处理机之前,系统必须按某种策略把外存中处于后备状态的作业选择出来,并创建进程...
  • 进程是操作系统最重要的概念之一,进程调度是操作系统内核的重要功能,本实验要求用C语言编写一个进程调度模拟程序,使用最早截止时间调度算法...设计一个模拟处理机调度算法,通过此实验可加深对进程调度算法的理解。
  • 1、处理机调度层次 处理器调度可分为三个级别: 高级调度(作业调度、长程调度) 中级调度(内存调度) 低级调度 低级调度是各类操作系统中必须具有的功能 在纯粹的分时或实时操作系统,作业被直接调入内存,因此...

    1、处理机调度层次

    处理器调度可分为三个级别:

    • 高级调度(作业调度、长程调度)
    • 中级调度(内存调度)
    • 低级调度

    低级调度是各类操作系统中必须具有的功能

    在纯粹的分时或实时操作系统,作业被直接调入内存,因此通常不需要高级调度

    在分时系统或具有虚拟存储器的操作系统中,专门引进了中级调度,控制进程在内存和外存间的对换

    在这里插入图片描述

    2、调度算法选择原则

    任何层次的处理器调度,都由操作系统的调度程序实施,调度程序(scheduler)所使用的算法称为调度算法

    “效益优先,兼顾公平原则”

    调度算法设计通常应考虑如下原则/目标:

    • 资源利用率
    • 吞吐率
    • 公平性
    • 响应时间
    • 周转时间
    • 截至时间的保证
    • 优先权原则

    (1)资源利用率

    • CPU利用率 = CPU有效工作时间/CPU总的运行时间

    • CPU总的运行时间 = CPU有效工作时间+CPU空闲等待时间

    (2)吞吐率

    单位时间内CPU处理的作业数

    • 长作业多:吞吐率低
    • 短作业多:吞吐率高

    (3)公平性

    确保每个用户每个进程获得合理的CPU份额或其他资源份额,不会出现饿死情况

    (4)响应时间

    交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间

    包括三部分时间:

    • 请求信息传到处理机的时间
    • 处理机处理请求信息的时间
    • 形成的响应回送到终端的时间

    使响应时间尽可能的短,是分时系统衡量调度性能的一个重要指标

    (5)作业周转时间

    作业周转时间:批处理用户从作业提交给系统开始,到作业完成为止的时间间隔

    • 如果作业 i 提交给系统的时刻是 t s,完成时刻是 t f,该作业的周转时间 t i为:
      t i = t f – t s
    • 实际上,它是作业在系统里的等待时间与运行时间之和

    使作业周转时间或平均作业周转时间尽可能短,是批处理系统衡量调度性能的一个重要指标

    (6)截止时间保证

    截止时间:指某个任务必须开始执行的最迟时间或必须完成的最迟时间,是评价实时系统调度性能的一个重要指标

    (7)优先权

    实时、分时、批处理均可遵循的原则,让一些紧急的任务尽快被执行

    3、作业的管理与调度

    (1)作业和进程的关系

    • 作业是用户提交给操作系统计算的一个独立任务。每个作业必须经过若干相对独立,且相互关联的顺序加工步骤才能得到结果。其中每个加工步骤称为一个作业步。
      进程是已提交完毕并选中运行的作业的执行实体,也是为完成作业任务向系统申请和分配资源的基本单位,它处于运行、就绪、等待等多个状态的变化之中,在CPU上推进。最终完成应用程序任务。

    • 作业是任务实体,进程是完成任务的执行实体。没有作业任务,进程无事可做,没有进程,作业任务无法完成。作业的概念更多的用于批处理操作系统中啊,而进程则用于各种多道程序设计系统。

    (2)批处理作业

    • 批处理作业的输入
    • 批处理作业的建立
    • 批处理作业的调度
      • 选择作业
      • 分配资源
      • 创建进程
      • 作业控制
      • 后续处理

    (3)交互式作业

    交互作业的组织、提交和控制与批处理作业的差别:

    • 生命周期,由用户决定
    • 作业情况和资源需求通过具体命令来提交和控制
    • 输入一条/一组命令,则创建一个/若干进程来完成

    具体的键盘命令:

    • 作业控制类
    • 资源申请类
    • 文件操作类
    • 目录操作类
    • 设备控制类

    4、低级调度的功能和类型

    (1)调度程序的任务

    调度程序担负两项任务

    • 调度:确定就绪进程/线程使用处理器的次序
    • 分派:确定如何时分复用CPU

    (2)低级调度类型

    • 剥夺方式(preemptive),抢占式:
      • 当一个进程正在处理器上执行时,系统可以根据规定的原则剥夺分配给它的处理器,而把处理器分配给其他进程使用
      • 有两种常见的剥夺原则:高优先级剥夺原则和时间片剥夺原则,前者高优先级进程或线程可以剥夺低优先级进程或线程运行,后者当运行进程时间用完后被剥夺处理器
    • 非剥夺方式(nonpreemptive),非抢占式:
      • 一旦某个进程或线程开始执行后便不再出让处理器,除非该进程或线程运行结束或发生了某个事件不能继续执行

    区别:

    5、作业调度和低级调度算法

    (1)FCFS:先来先服务算法

    在这里插入图片描述

    (2)SJF:最短作业优先算法

    在这里插入图片描述

    兼顾最近信息与历史信息
    历史越久远,对估算值影响越小

    (3)SRTF:最短剩余时间优先算法

    在这里插入图片描述

    在这里插入图片描述

    (4)HRRF:响应比高者优先算法

    在这里插入图片描述

    如果服务时间相同,则优先权取决于等待时间,待长作业等待时间足够长后,也将获得足够高的响应比

    在这里插入图片描述

    (5)PS:优先级调度算法(Priority Scheduling)

    在这里插入图片描述

    实现方式

    • 剥夺式 :SRTF(静态优先)
    • 非剥夺式:SJF(静态优先),HRRF(动态优先)

    (6)RR:轮转调度算法

    在这里插入图片描述

    • 基本轮转法:它要求每个进程轮流运行一个相同的时间片
    • 改进的轮转法:对于不同的进程给以不同的时间片;时间片的长短可以动态地修改等等

    (7)MLFQ:多级反馈队列调度算法

    多级反馈队列调度(反馈循环队列或多队列策略)

    • 主要思想:是将就绪进程分为两级或多级,系统相应建立两个或多个就绪进程队列,较高优先级的队列一般分配给较短的时间片。处理器调度每次先从高级就绪进程队列中选取可占有处理器的进程,只有在选不到时,才从较低级的就绪进程队列中选取。同一队列中的进程按先来先服务原则排队。开始工作时,每当一个新进程进入内存后,首先进入高优先级队列等候调度,若能在该级队列的一个时间片内执行完成,则撤离系统,否则进入低一级的队列等候调度,队列级别越低,时间片就越大,低优先级队列中的进程获得调度时运行的时间就长一些
    • 多级反馈队列如图所示:

    在这里插入图片描述

    (8)LS:彩票调度算法(Lottery Scheduling)

    展开全文
  • 处理机调度的模拟实现,用先来先服务、短作业优先、最短剩余时间优先、时间片轮转、基于静态优先级的调度,基于高响应比优先的动态优先级调度处理机调度算法的实现,能够模拟进程调度情况,并输出进程的完成时间,...
  • 4、处理机调度总是选队首进程运行。采用时间片轮转调度算法 5、若要求运行时间为零,则将其状态置为“结束”,且退出队列。 6、运行所设计程序,显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。

空空如也

1 2 3 4 5 ... 20
收藏数 3,604
精华内容 1,441
关键字:

处理机调度