操作系统里的算法

处理机管理

调度算法

先来先服务调度算法(first come first server,FCFS)

简介;先来先服务调度算法是最简单的调度算法,系统按照作业到达的先后次序进行调度。

优点:有利于长作业,适合繁忙的工作

缺点:不利于短作业

短作业优先调度算法(short job first,SJF)

简介:按照作业的长短来计算优先级,作业越短,优先级越高。

优点:有利于短作业

缺点:不利于长作业,长作业可能长时间得不到执行而“饿死”

优先级调度算法

该算法通过优先级决定顺序,优先级一般由外部决定(如用户)

高响应比优先调度算法(highest response ratio next,HRRN)

简介:优先级=(等待时间+要求服务时间)/要求服务时间

特点:如果作业等待时间相同,类似于SJF调度算法;如果作业要求服务时间相同,类似于FCFS调度算法;对于长作业的优先级,其可随等待时间的增加而提高,当作业的等待时间足够长时,也可以获得处理机

优点:实现了较好的折中

缺点:增加系统的开销

轮转调度算法(round robin,RR)

简介:该算法采用了非常公平的处理机分配方式,即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有n个进程,则每个进程每次大约可获得1/n的处理机时间

优点:非常公平

缺点:内存开销大

实时调度

最早截止时间优先算法(earliest deadline first,EDF)

简介:完成截止时间越早越优先,可以拥有抢占式调度方式也可以用于非抢占式调度方式。

最低松弛度优先算法(least laxity first,LLF)

简介:根据松弛度确定优先级,主要用于抢占式调度方式,当松弛度为0时发生抢占。松弛度=必须完成时间-其本身运行时间-当前时间,程序开始运行时松弛度不变。

存储器管理

动态分区分配

首次适应算法(first fit,FF)

简介:在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止

优点:有利于大作业,因为很多小作业在低址部分已经分区,在高址部分留下很多大的空闲空间

缺点:在低址部分留下很多难以利用的碎片,每次查找都从低址开始也增加了开销

循环首次适应算法(next fit,NF)

简介:从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区

优点:使内存中的空闲分区分布更加均匀,减小了查找空闲分区的开销

缺点:使得大的空闲分区比较缺乏

最佳适应算法(best fit,BF)

简介:每次分配时,总是把能满足要求的最小空闲分区分配给作业,为了加速寻找,所有空闲空间从小到大排序,排成一个空闲分区块

缺点:实际效果最差,会形成很多难以利用的碎片

最坏适应算法(worst fit, WF)

简介:在扫描整个空闲分区表或空闲分区链时,总是挑选一个最大的空闲区,从中分割一部分存储空间给作业使用,以至于存储器中会缺乏大的空闲分区。要求所有空闲分区按容量从大到小排成一个空闲分区链

优点:实际效果最佳,让剩下的空间不至于太小,产生碎片概率最最小,查找效率很高

页面置换算法

最佳页面置换算法(optimal,OPT)

简介:选择淘汰的页面,是以后永不使用或在未来很长时间内不会被访问的页面

优点:可以保证最低缺页率

缺点:不可能实现,因为无法预测未来,不过可以作为指标

先进先出页面置换算法(first in first out,FIFO)

简介:总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。

优点:适合没有循环的程序

缺点:循环在程序里很常见,但是该算法遇到循环会频繁换页面,缺页率高

最近最久未使用页面置换算法(least recently used,LRU)

简介:将最近最久未使用的页面予以淘汰。

优点:实际效果好,缺页率较低

缺点:需要系统提供较多的硬件支持

最少使用页面置换算法(least frequently used,LFU)

简介:将最少使用的页面调出,在效果上和LRU一样

Clock页面置换算法

简介:LRU需要有较多硬件支持,所以大多时候使用LRU算法的近似算法,Clock就是其中之一。

过程:当使用该算法时,要为每页设置一个访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列即可。当某页被访问时,其访问页被置1。当选择一页进行淘汰时,只要检查页的访问位,如果是0就换出,是1置0暂不换出。

外部设备管理

磁盘调度算法

FCFS调度算法

简介:最简单的磁盘调度算法,根据程序请求访问磁盘的先后顺序进行调度。

优点:公平、简单

缺点:未对寻道进行优化,平均寻道时间可能较长。

SSTF调度算法

简介:最短距离优先

优点:相较于FCFS有更好的性能

缺点:不能保证平均寻道时间最短,容易导致饥饿现象。

SCAN调度算法

简介:SCAN算法不仅考虑距离,还优先考虑当前磁头移动方向。

优点:平均寻道时间短,相比SSTF避免饥饿。

缺点:当磁头恰好在一个区域临近相反方向移动,读取需要很长时间。

CSCAN算法

简介:当磁头移动到最外面立刻回到最里面要访的磁头。

优点:更加公平

缺点:时间较长

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/491839.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

密码编码学与网络安全(第五版)答案

通过如下代码分别统计一个字符的频率和三个字符的频率,"8"——"e",“;48”——“the”,英文字母的相对使用频率,猜测频率比较高的依此为),t,*,5,分别对应s,o,n,…

【功能安全】随机硬件失效导致违背安全目标的评估(FMEDA)

目录 01 随机硬件失效介绍 02 FMEDA介绍 03 FMEDA模板 01 随机硬件失效介绍 GBT 34590 part5

mybatis 的动态sql 和缓存

动态SQL 可以根据具体的参数条件,来对SQL语句进行动态拼接。 比如在以前的开发中,由于不确定查询参数是否存在,许多人会使用类似于where 1 1 来作为前缀,然后后面用AND 拼接要查询的参数,这样,就算要查询…

Web APIs - 第5章笔记

目标: 依托 BOM 对象实现对历史、地址、浏览器信息的操作或获取 具备利用本地存储实现学生就业表案例的能力 BOM操作 综合案例 JavaScript的组成 ECMAScript: 规定了js基础语法核心知识。 比如:变量、分支语句、循环语句、对象等等 Web APIs : DO…

AI视频配音技术创新应用与商业机遇

随着人工智能技术的飞速发展,AI视频配音技术已经成为内容创作者和营销人员的新宠。这项技术不仅能够提升视频内容的吸引力,还能为特定行业带来创新的解决方案。本文将探讨AI视频配音技术的应用场景,并讨论如何合法合规地利用这一技术。 AI视频…

vlan和vlanif

文章目录 1、为什么会有vlan的存在2、vlan(虚拟局域网)1、vlan原理1. 为什么这样划分了2、如何实现不同交换机相同的vlan实现互访呢3、最优化的解决方法,vlan不同交换机4、vlan标签和vlan数据帧 5、vlan实现2、基于vlan的划分方式1、基于接口的vlan划分方式2、基于m…

Java每日一题(1)

给定n个数a1,a2,...an,求它们两两相乘再相加的和。 即:Sa1*a2a1*a3...a1*ana2*a3...an-2*an-1an-2*anan-1*an 第一行输入的包含一个整数n。 第二行输入包含n个整数a1,a2,...an。 样例输入 4 1 3 6 9 样例输出 117 答案 import java.util.Scanner; // 1:无…

Redis应用—6.热key探测设计与实践

大纲 1.热key引发的巨大风险 2.以往热key问题怎么解决 3.热key进内存后的优势 4.热key探测关键指标 5.热key探测框架JdHotkey的简介 6.热key探测框架JdHotkey的组成 7.热key探测框架JdHotkey的工作流程 8.热key探测框架JdHotkey的性能表现 9.关于热key探测框架JdHotke…

Elasticsearch:使用 Open Crawler 和 semantic text 进行语义搜索

作者:来自 Elastic Jeff Vestal 了解如何使用开放爬虫与 semantic text 字段结合来轻松抓取网站并使其可进行语义搜索。 Elastic Open Crawler 演练 我们在这里要做什么? Elastic Open Crawler 是 Elastic 托管爬虫的后继者。 Semantic text 是 Elasti…

python爬虫入门教程

安装python 中文网 Python中文网 官网 安装好后打开命令行执行(如果没有勾选添加到Path则注意配置环境变量) python 出现如上界面则安装成功 设置环境变量 右键我的电脑->属性 设置下载依赖源 默认的是官网比较慢,可以设置为清华大…

数据结十大排序之(冒泡,快排,并归)

接上期: 数据结十大排序之(选排,希尔,插排,堆排)-CSDN博客 前言: 在计算机科学中,排序算法是最基础且最重要的算法之一。无论是大规模数据处理还是日常的小型程序开发,…

游戏引擎学习第54天

仓库: https://gitee.com/mrxiao_com/2d_game 回顾 我们现在正专注于在游戏世界中放置小实体来代表所有的墙。这些实体围绕着世界的每个边缘。我们有活跃的实体,这些实体位于玩家的视野中,频繁更新,而那些离玩家较远的实体则以较低的频率运…

网络安全漏洞挖掘之漏洞SSRF

SSRF简介 SSRF(Server-Side Request Forgery:服务器端请求伪造是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。一般情况下,SSRF攻击的目标是从外网无法访问的内部系统。(正是因为它是由服务端发起的,所以它能够请求到与它相连而与外…

33. Three.js案例-创建带阴影的球体与平面

33. Three.js案例-创建带阴影的球体与平面 实现效果 知识点 WebGLRenderer (WebGL渲染器) WebGLRenderer 是 Three.js 中用于渲染 3D 场景的核心类。它负责将场景中的对象绘制到画布上。 构造器 new THREE.WebGLRenderer(parameters)参数类型描述parametersObject可选参数…

Go有限状态机实现和实战

Go有限状态机实现和实战 有限状态机 什么是状态机 有限状态机(Finite State Machine, FSM)是一种用于建模系统行为的计算模型,它包含有限数量的状态,并通过事件或条件实现状态之间的转换。FSM的状态数量是有限的,因此称…

iPhone恢复技巧:如何从 iPhone 恢复丢失的照片

在计算机时代,我们依靠手机来捕捉和存储珍贵的回忆。但是,如果您不小心删除或丢失了手机上的照片怎么办?这真的很令人沮丧和烦恼,不是吗?好吧,如果您在 iPhone 上丢失了照片,您不必担心&#xf…

Linux高性能服务器编程 | 读书笔记 | 6. 高性能服务器程序框架

6. 高性能服务器程序框架 《Linux 高性能服务器编程》一书中,把这一章节作为全书的核心,同时作为后续章节的总览。这也意味着我们在经历了前置知识的学习后,正式进入了 Web 服务器项目的核心部分的学习 文章目录 6. 高性能服务器程序框架1.服…

前端的知识(部分)

11 前端的编写步骤 第一步:在HTML的页面中声明方法 第二步:在<script>中定义一个函数,其中声明一个data来为需要的数据 赋值一个初始值 第三步:编写这个方法实现对应的功能

Xcode

info.plist Appearance Light 关闭黑暗模式 Bundle display name 设置app名称&#xff0c;默认为工程名 Location When In Use Usage Description 定位权限一共有3个key 1.Privacy - Location When In Use Usage Description 2.Privacy - Location Always and When In U…

C# 中的Task

文章目录 前言一、Task 的基本概念二、创建 Task使用异步方法使用 Task.Run 方法 三、等待 Task 完成使用 await 关键字使用 Task.Wait 方法 四、处理 Task 的异常使用 try-catch 块使用 Task.Exception 属性 五、Task 的延续使用 ContinueWith 方法使用 await 关键字和异步方法…