专栏首页大眼瞪小眼操作系统常用算法

操作系统常用算法

作业调度算法

介绍:又称为高级调度或长程调度,调度对象是作业。根据作业控制块(JCB)中的信息,审查系统能否满足用户作业的资源需求,以及按照一定的算法,从外存的后备队列中选取某些作业调入内存,并为他们创建进程、分配必要的资源。然后再将新创建的进程插入到就绪队列,准备执行。

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

按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单,公平。其缺点是没有考虑到系统中各种资源的综合使用情况,往往使短作业的用户不满意,因为短作业等待处理的时间可能比实际运行时间长得多。

短作业优先调度算法(SPF)

优先调度并处理短作业,所谓短是指作业的运行时间短。而在作业未投入运行时,并不能知道它实际的运行时间的长短,因此需要用户在提交作业时同时提交作业运行时间的估计值。 

最高响应比优先算法(HRN)

FCFS可能造成短作业用户不满,SPF可能使得长作业用户不满,于是提出HRN,选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。

基于优先数调度算法(HPF)

每一个作业规定一个表示该作业优先级别的整数,当需要将新的作业由输入井调入内存处理时,优先选择优先数最高的作业。

均衡调度算法,即多级队列调度算法

基本概念:

   作业周转时间(Ti)=完成时间(Tei)-提交时间(Tsi)

   作业平均周转时间(T)=周转时间/作业个数

   作业带权周转时间(Wi)=周转时间/运行时间

   响应比=(等待时间+运行时间)/运行时间

一个关于作业调度的考试题

页面置换算法(内存调度)

介绍:又称为中级调度或者内存调度,操作对象是内存中的页面和程序中的页面,主要功能是决定内存中页面的换入换出,提高程序的运行速度。

理想页面置换算法(OPT)

这是一种理想的算法,在实际中不可能实现。该算法的思想是:发生缺页时,选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

先进先出页面置换算法(FIFO) 

选择最先进入内存的页面予以淘汰。

最近最久未使用算法(LRU)

选择在最近一段时间内最久没有使用过的页,把它淘汰。 

最少使用算法(LFU) 

选择到当前时间为止被访问次数最少的页转换。

进程调度算法

介绍:又称为低级调度或短程调度,调度对象是进程,主要功能是决定就绪队列中的那个进程应获得处理机。

为了实现进程调度,应该具有如下三个基本机制 

① 排队器,为了提高进程调度的效率,事先应该将系统的所有就绪进程按照一定的方式排成一个或多个队列,以便调度程序能最快地找到它。 

② 分派器,分派器把由进程调度程序所选定的进程,从就绪队列中去除该进程,然后进行上下文切换,将处理机分配给它。

③ 上下文切换机制,当对处理机进行切换时,会发生两对上下文切换操作,在第一对上下文切换时,操作系统将保存当前进程的上下文,而装入分派程序的上下文,一遍分派程序运行,在第二对上下文切换时,将移出分派程序,而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。

先进先出算法(FIFO)

按照进程进入就绪队列的先后次序来选择。即每当进入进程调度,总是把就绪队列的队首进程投入运行。

时间片轮转算法(RR)

分时系统的一种调度算法。轮转的基本思想是,将CPU的处理时间划分成一个个的时间片,就绪队列中的进程轮流运行一个时间片。当时间片结束时,就强迫进程让出CPU,该进程进入就绪队列,等待下一次调度,同时,进程调度又去选择就绪队列中的一个进程,分配给它一个时间片,以投入运行。

最高优先级算法(HPF)

进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式最高优先级算法和不可抢占式最高优先级算法。

多级队列反馈法

几种调度算法的结合形式多级队列方式。

空闲分区分配算法

介绍:操作对象计算机内存,主要功能是决定内存的分配策略,减少内存浪费。

首先适应算法

当接到内存申请时,查找分区说明表,找到第一个满足申请长度的空闲区,将其分割并分配。此算法简单,可以快速做出分配决定。

最佳适应算法

当接到内存申请时,查找分区说明表,找到第一个能满足申请长度的最小空闲区,将其进行分割并分配。此算法最节约空间,因为它尽量不分割到大的空闲区,其缺点是可能会形成很多很小的空闲分区,称为“碎片”。

最坏适应算法

当接到内存申请时,查找分区说明表,找到能满足申请要求的最大的空闲区。该算法的优点是避免形成碎片,而缺点是分割了大的空闲区后,在遇到较大的程序申请内存时,无法满足的可能性较大。

磁盘调度

介绍:操作对象计算机磁盘存储区,主要功能是对磁头寻道进行优化,使对磁盘的寻道时间较少。

先来先服务(FCFS)

是按请求访问者的先后次序启动磁盘驱动器,而不考虑它们要访问的物理位置

最短寻道时间优先(SSTF)

让离当前磁道最近的请求访问者启动磁盘驱动器,即是让查找时间最短的那个作业先执行,而不考虑请求访问者到来的先后次序,这样就克服了先来先服务调度算法中磁臂移动过大的问题

扫描算法(SCAN)或电梯调度算法

总是从磁臂当前位置开始,沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时,就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度,所以它也称为电梯调度算法。

循环扫描算法(CSCAN)

循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动,由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时,再回到最外,访问柱面号最小的作业请求。

转载OS中常用的调度算法总结

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序的机器级表示

    预处理阶段:预处理器cpp根据编译文件以“#”开头的命令,读取系统头文件stdio.h(.h结尾的表示头文件,.c表示可执行文件)的内容,并把它插入到程序文本中...

    大眼瞪小眼
  • 字符,字符集,字符编码

    现在Unicode已然一统天下,我想很多年轻的程序员可能都没遇到过编码问题,更不用说了解编码的发展了。前些日子在一个老网站上偶遇乱码,虽然入行时间不短,但对其究...

    大眼瞪小眼
  • Compoer介绍

    Composer 是 PHP 的一个依赖管理工具。它允许你申明项目所依赖的代码库,它会在你的项目中为你安装他们。

    大眼瞪小眼
  • Hadoop总结篇之五---模块间是怎么驱动执行的

    在MRv1中,各个模块间驱动运行的方式是函数调用的方式。这是同步的过程,上一模块调用下一模块函数后,等待其执行。效率不高。 在MRv2中做了改进,yarn基于事...

    小端
  • 日常评 | 深夜,来谈一谈未来 #191005

    假期已经过半,近期对于未来的科技发展,有些许想法从头脑中迸出。趁着假期这个机会分享给大家。

    ZNing
  • 模式识别考点总结(第7-12个ppt)

    小白学视觉
  • 中科院发布寒武纪深度神经网络处理器是什么?

    第三届世界互联网大会于2016年11月16日在浙江乌镇召开,并举办了领先科技成果发布会。其中中国最引人注目的就是中国科学院计算技术研究所发布了寒武纪深度神经网络...

    机器人网
  • GMIS 2017 | NIPS最佳论文作者之一吴翼:价值迭代网络

    机器之心原创 机器之心编辑部 全球机器智能峰会(GMIS 2017),是全球人工智能产业信息服务平台机器之心举办的首届大会,邀请来自美国、欧洲、加拿大及国内的众...

    机器之心
  • 深度学习笔记-神经网络介绍

    ---- Deep Learning 学习笔记-第一周 Andrew Ng发布了新课程,业界评价很好。在看的过程中非常不错,我把一些重要的知识和要点进行了总结和...

    BrianLv
  • Archiva 仓库提示文件没有找到

    如果提示的是 404 的话,提示你的 Archiva 在可能的源仓库中已经进行了搜索,但是没有找到。

    HoneyMoose

扫码关注云+社区

领取腾讯云代金券