首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >进程调度算法

进程调度算法

原创
作者头像
用户3906509
修改2020-06-15 10:31:18
1.9K0
修改2020-06-15 10:31:18
举报
文章被收录于专栏:污啦啦滴专栏污啦啦滴专栏

一、进程调度算法的评价指标

  1. cpu利用率:

利用率=cpu忙碌时间/总时间

  1. 系统吞吐量:

系统吞吐量=总共完成了多少道作业/总共花费的时间

  1. 周转时间:
  2. 周转时间: 周转时间=作业完成时间-作业提交时间
  3. 平均周转时间: 平均周转时间=各作业周转时间之和/作业数量
  4. 带权周转时间: 带权周转时间=作业周转时间/作业实际运行的时间
  5. 平均带权周转时间: 平均带权周转时间=各作业带权周转时间之和/作业数量
  6. 等待时间:

进程/作业 等待被服务的时间之和

平均等待时间即各个 进程/作业 等待时间的平均值

  1. 响应时间:

从用户提交请求到首次产生响应所用的时间


二、调度算法(早期批处理系统)

Tips:各种调度算法的学习思路

  • 算法思想
  • 算法规则
  • 这种调度算法是用于**作业调度**还是**进程调度**?
  • 抢占式?非抢占式?
  • 优点核缺点
  • 是否会导致***饥饿***(某进程/作业长期得不到服务)
1. 先来先服务(FCFS)
image-20200325150609731
image-20200325150609731
2. 短作业优先(SJF)
  1. 短作业/进程优先调度算法:每次调度时选择**当前已到达**且**运行时间最短**的作业/进程。
  2. 最短剩余时间优先算法:每当有进程加入**就绪队列改变时就需要调度**,如果新到达的进程**剩余时间**比当前运行时间的进程剩余时间**更短**,则由新进程**抢占**处理机,当前运行进程重新回到就绪队列。另外,当一个**进程完成时也需要调度**。
image-20200325152858734
image-20200325152858734
3. 高响应比优先

响应比: 响应比=(等待时间+要求服务时间)/要求服务时间

**高响应比优先算法规则**:在每次调度时先计算各个作业/进程的*相应比*,选择*相应比最高的*作业/进程为其服务

image-20200325154733465
image-20200325154733465

知识回顾
image-20200325154848100
image-20200325154848100

三、调度算法(交互式系统)

1. 时间片轮转调度算法(RR)——常用于分时操作系统
    \*\*\*算法规则:\*\*\*按照各进程到达就绪队列的顺序,轮流让各个进程执行一个\*\*时间片\*\*(如100ms)。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。
    \*\*\*如果时间片太大\*\*\*,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法\*\*退化为先来先服务\*\*调度算法,并且会\*\*增大进程响应时间\*\*。因此\*\*时间片不能太大\*\*。
    \*\*\*如果时间片太小\*\*\*,进程调度、切换是有时间代价的(保存、恢复运行环境),因此如果时间片太小,会导致\*\*进程切换过于频繁\*\*,系统会花大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减小。
image-20200325163257508
image-20200325163257508
2. 优先级调度算法
    \*\*\*算法规则:\*\*\*每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程
    \*\*\*抢占式的优先级调度算法:\*\*\*每次调度时选择\*\*当前已到达\*\*且\*\*优先级最高\*\*的进程。当前进程\*\*主动放弃处理机时\*\*发生调度。另外,当\*\*就绪队列发生改变时\*\*也需要检查是否会发生抢占。
    \*\*\*非抢占的优先级调度算法:\*\*\*每次调度时选择\*\*当前已到达\*\*且\*\*优先级最高\*\*的进程。仅在当前进程\*\*主动放弃处理机时\*\*发生调度。
    \*\*\*优先级调度算法的补充:\*\*\*
  • 就绪队列未必只有一个,可以按照不同优先级来组织。另外,也可以把优先级高的进程排在更靠近就绪队列队头的位置
  • 根据优先级是否可以动态改变,可将优先级分为**静态优先级**和**动态优先级**两种。
  • 静态优先级:创建进程时确定,之后一直不变。
  • 动态优先级:创建进程时有一个初始值,之后会根据情况动态地调整优先级。
  • 系统进程优先级**高于**用户进程
  • 前台进程优先级**高于**后台进程
+ 如果某进程在就绪队列中等待了很长时间,则可以适当提高其优先级
+ 如果某进程占用处理机运行了很长时间,则可以适当降低其优先级
+ 如果一个进程频繁地进行I/O操作,则可适当提升其优先级
  • 操作系统更**偏好于I/O型进程(或称I/O繁忙型进程)**
+ I/O设备和CPU可以\*\*并行\*\*工作。如果优先让I/O繁忙型进程优先运行的话,则越有可能让I/O设备尽早地投入工作,则资源利用率、系统吞吐量都会得到提升。
+ 注:与I/O型进程相对的是\*\*计算型进程(或称CPU繁忙型进程)\*\*
image-20200325171035937
image-20200325171035937
3. 多级反馈队列调度算法
    \*\*\*算法规则:\*\*\*
  1. 设置多级就绪队列,各级队列优先级从高到低,时间片从小到大
  2. 新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经是在最下级的队列,则重新放回该队列队尾。
  3. 只有第K级队列为空时,才会为K+1级队头分配时间片。
 \*\*\*抢占式的算法:\*\*\*在K级队列的进程运行过程中,若上级的队列(1~K-1级)中进入了一个新进程,则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回K级队列队尾。
 ![image-20200325173853530](https://img-wqnmd.obs.cn-south-1.myhuaweicloud.com/image-20200325173853530.png)

知识回顾
image-20200325174051062
image-20200325174051062

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、进程调度算法的评价指标
  • 二、调度算法(早期批处理系统)
    • 1. 先来先服务(FCFS)
      • 2. 短作业优先(SJF)
        • 3. 高响应比优先
          • 知识回顾
          • 三、调度算法(交互式系统)
            • 1. 时间片轮转调度算法(RR)——常用于分时操作系统
              • 2. 优先级调度算法
                • 3. 多级反馈队列调度算法
                  • 知识回顾
                  相关产品与服务
                  文件存储
                  文件存储(Cloud File Storage,CFS)为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用,为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用,可实现对现有应用的无缝集成;按实际用量付费,为您节约成本,简化 IT 运维工作。
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档