首页 > 编程语言 >调度算法(一)

调度算法(一)

时间:2024-11-08 08:59:32浏览次数:4  
标签:抢占 作业 调度 算法 等待时间 进程

调度算法(一)

(1)前言

此处列举的三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用户来说,交互性很糟糕。

因此这三种算法一般适合用于早期的批处理系统,当然, FCFS 算法也常结合其他的算法使用,在现在也扮演着很重要的角色。而适合用于交互式系统的调度算法见(二)。

image


(2)FCFS 先来先服务 First Come First Serve

Ⅰ. 算法思想

主要从”公平“的角度考虑。

Ⅱ. 算法规则

按照作业/进程到达的先后顺序进行服务。

Ⅲ. 用于作业/进程调度

用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,或虑的是哪个进程先到达就绪队列。

Ⅳ. 是否可抢占

非抢占式的算法。

Ⅴ. 优缺点

  • 优点:公平,算法实现简单。
  • 缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。即,FCFS 算法对长作业有利,对短作业不利。

Ⅵ. 是否会导致饥饿

不会(前面的作业/进程总有执行完毕的时候)。

Ⅶ. 例子

image


(3)SJF 短作业优先 Shortest Job First / SPF 短进程优先 Shortest Process First / SRTN 最短剩余时间优先算法 Shortest Remaining Time Next

Ⅰ. 算法思想

追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间。

Ⅱ. 算法规则

最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短)。

Ⅲ. 用于作业/进程调度

即可用于作业调度(SJF),也可用于进程调度(SPF)。

Ⅳ. 是否可抢占

(没明确说明)默认是非抢占式的算法。

也有抢占式的版本—— SRTN 最短剩余时间优先算法 Shortest Remaining Time Next

Ⅴ. 优缺点

  • 优点:“最短的”平均等待时间、平均周转时间。
  • 缺点:不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业/进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先。

Ⅵ. 是否会导致饥饿

会。如果源源不断地有短作业/进程到来,可能使长作业/进程长时间得不到服务,产生“饥饿”短象。如果一直得不到服务,则称为“饿死”。

Ⅶ. 例子

1. 非抢占式(当某个作业/进程执行结束后再进行调度)

image

2. 抢占式(当有新进程加入就绪队列或当某个进程执行结束后立即进行调度)

image

image

Ⅷ. 补充

image


(4)HRRN 高响应比优先 Highest Response Ratio Next

Ⅰ. 算法思想

综合考虑作业/进程的等待时间和要求服务的时间。

Ⅱ. 算法规则

在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务。(响应比 >= 1)

Ⅲ. 用于作业/进程调度

即可用于作业调度,也可用于进程调度。

Ⅳ. 是否可抢占

非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时,才需要调度,才需要计算响应比。

Ⅴ. 优缺点

综合考虑了等待时间和运行时间(要求服务时间)。

等待时间相同时,要求服务时间短的优先(SJF 的优点)。

要求服务时间相同时,等待时间长的优先(FCFS 的优点)。

Ⅵ. 是否会导致饥饿

不会(对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题)。

Ⅶ. 例子

image

标签:抢占,作业,调度,算法,等待时间,进程
From: https://www.cnblogs.com/Wind730/p/18534398/schedule-algorithm-1-z1dxjxn

相关文章

  • 人工智能图像算法:开启视觉新时代的钥匙
    一、引言在当今科技飞速发展的时代,人工智能已经成为了各个领域的热门话题。其中,人工智能图像算法作为人工智能领域的一个重要分支,正以其强大的功能和广泛的应用场景,改变着我们的生活和工作方式。本文将深入探讨人工智能图像算法的重要性以及其在各个领域的应用场景。二、人......
  • 基于遗传优化的SVD水印嵌入提取算法matlab仿真
    1.程序功能描述基于遗传优化的的SVD水印嵌入提取算法。对比遗传优化前后SVD水印提取性能,并分析不同干扰情况下水印提取效果。2.测试软件版本以及运行结果展示MATLAB2022a版本运行SVD GA优化SVD 性能对比: 3.核心程序%遍历遗传算法返回的各代最优个体(从......
  • FootyForecast足球数据预测软件——XGBoost算法实战
    足球数据分析——XGBoost算法实战基于上数据分析的AI足球大模型预测平台,感兴趣的可以下载。足球预测专家推荐链接:http://lcsjfx.com/FootyForecast/DownLoad随着足球数据的日益丰富,数据分析在足球领域的应用也越来越广泛。其中,XGBoost算法作为一种高效、强大的机器......
  • 内核调度抢占模式——voluntary和full对比
    一、背景在之前的内核调度子系统专栏里,我们已经把调度有关的如CFS调度/RT调度,调度时间片,调度时延,cfs唤醒抢占特性,这些基本概念和细节都讲了一遍。其实这些细节更多的是帮助我们理解调度系统是如何运作的,调度系统里的大部分参数其实我们都是不会去调整,或者说不敢去做大的调整的......
  • 【算法】动态规划
    一、算法概念动态规划算法是一种解决多阶段决策问题的方法。它将一个问题分解为多个子问题,并逐个求解子问题的最优解,最后得到原问题的最优解。二、基本思想动态规划算法的核心思想是通过存储中间结果来避免重复计算。在解决问题的过程中,会利用已经求解过的子问题的最优解......
  • 代码随想录算法训练营第九天|LeetCode151.翻转字符串里的单词、卡码网:55.右旋转字符串
    前言打卡代码随想录算法训练营第49期第九天︿( ̄︶ ̄)︿首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。今日题目LeetCode151翻转字......
  • 代码随想录算法训练营 day37 day38| 卡码网52.完全背包 518. 零钱兑换 II 377.
    学习资料:https://programmercarl.com/背包问题理论基础完全背包.html#算法公开课相比于01背包,完全背包中每个物品都可以无限次的放入组合:先遍历物品,再逆序遍历背包排列:先逆序遍历背包,再遍历物品学习记录卡码网52.携带研究资料(dp[i]代表当重量为i时的最大价值)点击查看代码n......
  • 大数据学习笔记 第5天 ZooKeeper 3.6.3安装部署 CAP原则 Paxos算法 ZAB协议详解
    ZooKeeper3.6.3重点CAP原则Paxos算法存储模型和监听机制一、集群与分布式集群:将一个任务部署在多个服务器,每个服务器都能独立完成该任务。分布式:将一个任务拆分成若干个子任务,由若干个服务器分别完成这些子任务,每个服务器只能完成某个特定的子任务。从概念上就可......
  • 算法每日双题精讲——双指针(移动零,复写零)
    ......
  • 双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动(3)
    前言:本篇来到双指针算法介绍的最终篇,该文将通过三个同类型但难度逐渐累增的题目,再次强化对双指针算法的理解和运用。 相关题目及讲解一.两数之和题目链接:LCR179.查找总价格为目标值的两个商品-力扣(LeetCode)题目分析:1.该题要求较为简单,只需要在数组中查找两个和......