首页 > 系统相关 >计算机系统进程调度算法

计算机系统进程调度算法

时间:2022-10-04 12:03:00浏览次数:47  
标签:计算机系统 队列 作业 调度 算法 时间 进程

不同环境的调度算法目标不同,因此需要针对不同环境来讨论调度算法。

  1. 批处理系统

批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量和周转时间(从提交到终止的时间)。

1.1 先来先服务 first-come first-serverd(FCFS)

非抢占式的调度算法,按照请求的顺序进行调度。

有利于长作业,但不利于短作业,因为短作业必须一直等待前面的长作业执行完毕才能执行,而长作业又需要执行很长时间,造成了短作业等待时间过长。

1.2 短作业优先 shortest job first(SJF)

非抢占式的调度算法,按估计运行时间最短的顺序进行调度。

长作业有可能会饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。

1.3 最短剩余时间优先 shortest remaining time next(SRTN)

最短作业优先的抢占式版本,按剩余运行时间的顺序进行调度。 当一个新的作业到达时,其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少,则挂起当前进程,运行新的进程。否则新的进程等待。

  1. 交互式系统

交互式系统有大量的用户交互操作,在该系统中调度算法的目标是快速地进行响应。

2.1 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列,每次调度时,把 CPU 时间分配给队首进程,该进程可以执行一个时间片。当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系:

  • 因为进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,会导致进程切换得太频繁,在进程切换上就会花过多时间。
  • 而如果时间片过长,那么实时性就不能得到保证。

请添加链接描述

2.2 优先级调度

为每个进程分配一个优先级,按优先级进行调度。

为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级。

2.3 多级反馈队列

一个进程需要执行 100 个时间片,如果采用时间片轮转调度算法,那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑,它设置了多个队列,每个队列时间片大小都不同,例如 1,2,4,8,..。进程在第一个队列没执行完,就会被移到下一个队列。这种方式下,之前的进程只需要交换 7 次。

每个队列优先权也不同,最上面的优先权最高。因此只有上一个队列没有进程在排队,才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

<div align="center"> <img src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/042cf928-3c8e-4815-ae9c-f2780202c68f.png"/> </div><br>

  1. 实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时,前者必须满足绝对的截止时间,后者可以容忍一定的超时。

标签:计算机系统,队列,作业,调度,算法,时间,进程
From: https://blog.51cto.com/u_14068620/5731171

相关文章

  • AcWing算法提高课 中国剩余定理 求解多个线性同余方程
        注意这里是构造了一个解,ti由于Mi与mi互质,可以用ExGCD求解例题:https://www.acwing.com/problem/content/1300/模板:#include<bits/stdc++.h>usingnamespac......
  • 一个简单的模拟实例说明Task及其调度问题
    编者荐语:蒋老师只用短短的几百行样例代码就为大家解释清楚了在C#中至关重要的Task和其调度的原理,这是不可多得的高质量文章。Task对于.NET的重要性毋庸置疑。通过最近的一些......
  • 月薪20k-40k| 苏州挚途科技视觉SLAM算法工程师招聘
    3D视觉工坊致力于推荐最棒的工作机会,精准地为其找到最佳求职者,做连接优质企业和优质人才的桥梁。公司介绍:苏州挚途科技有限公司,成立于2019年08月08日,坐落在苏州高铁新城。公......
  • 从学算法体会如何更好的学习
    一、第一次学习算法记得第一次学习《数据结构和算法》还是在大学的必修课里,是严蔚敏那一版。那个版本的算法跟《算法导论》一样,代码使用的是伪代码。而我们学习的时候,并......
  • 算法
    24.两两交换链表中的节点![image.png](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/6b52140970264dc68234ba92976a3954~tplv-k3u1fbpfcp-watermark.image?)```/*......
  • 字符串匹配之Sunday算法
    简介Sunday算法是一种字符串匹配算法,相比于KMP算法,它比较简单易学。在有些时候,比如字符串很长的时候,它是比KMP要高效的。核心思想从前往后匹配,匹配失败时关注主串中......
  • Java手写实现链表队列和数组队列【数据结构与算法】
    packagealgorithm;/**@authorAdministrator@date2022-09-1317:50*/publicclassQueueLinked{privatestaticclassNode{Eitem;Nodenext;publicNode(Eitem,N......
  • Java手写实现栈【数据结构与算法】
    packagealgorithm;importjava.util.Arrays;importjava.util.Iterator;/**@authorAdministrator@date2022-09-1216:38数组栈*/publicclassMyArrayStack{//定义......
  • 常见距离算法
    机器学习中有很多的距离计算公式,用于计算数据和数据之间的距离,进而计算相似度或者其他。1.欧式距离(EuclideanDistance)​ 欧式距离是最常见的距离度量方法。小学、初中、......
  • Latex 如何写算法?推荐模板
    之前我已经在​​这篇文章​​总结了现有的算法包的区别。如果有选择苦难症的朋友可以考虑无脑使用以下模板来写算法。\usepackage[noend]{algpseudocode}#noend表示算法......