第3章处理机调度与死锁

一、处理机调度的层次和调度算法的目标

调度的实质是一种资源分配,处理机调度是对处理机资源进行分配。

1. 处理机调度的层次

(1)高级调度(作业调度)。

(2)中级调度(内存调度)。

(3)低级调度(进程调度)。

2. 处理机调度算法的目标

(1)资源利用率。

(2)公平性。

(3)平衡性。

(4)策略强制执行。

二、作业与进程的基本概念

1. 批处理系统中的作业

(1)作业和作业步 ①作业

作业是用户提交给系统的一项相对独立的工作,它不仅包含了通常的程序和数据,而且还应配有一份作业说 明书,系统根据该说明书来对程序的运行进行控制。

②作业步

在作业运行期间,每个作业都必须经过若干个相对独立,又相互关联的顺序加工步骤才能得到结果。其中的 每一个加工步骤称为一个作业步。

(2)作业控制块 (JCB) ①定 

作业控制块是作业在系统中存在的标志,其中保存了系统对作业进行管理和调度所需的全部信息。 ②内容

JCB中包含的内容有:作业标识、用户名称、用户账号、作业类型 (CPU 繁忙型、I/O 繁忙型、批量型、终 端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使 用情况等。

2. 进程调度的任务和方式

(1)进程调度的任务

①保存处理机的现场信息。

 按某种算法选取进程。

③把处理器分配给进程。

(2)进程调度方式

①非抢占方式。

②抢占方式。

【说明】“抢占”必须遵循一定的原则,主要原则有:优先权原则、短进程优先原则、时间片原则。

(3)不能进行进程调度的情况

①在处理中断的过程中。

②进程在操作系统内核程序临界区中。

③需要完全屏蔽中断的原子操作过程中。

3. 调度的基本准则

(1)CPU  利用率,其中计算公式为

(2)系统吞吐量

(3)周转时间,需掌握以下公式:

①周转时间=作业完成时间-作业提交时间

②平均周转时间=(作业1的周转时间+…+作业n 的周转时间)/n

③带权周转时间=作业周转时间/作业实际运行时间

(4)等待时间

(5)响应时间

三、典型调度算法

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

(1)FCFS    算法既可用于作业调度,也可用于进程调度。

(2)每次选择最早进入队列的作业(或进程)调入内存(或分配处理机)。

(3)属于不可剥夺算法。

(4)有利于CPU 繁忙型作业,不利于I/O 繁忙型作业;有利于长作业,不利于短作业。

2.短作业优先 (SJF)   调度算法

(1)SJF    算法既可用于作业调度,也可用于进程调度。

(2)每次选择运行时间最短的作业(或进程)调入内存(或分配处理机)。

(3)对长作业不利,且未考虑作业的紧迫程度。

(4)SJF    算法的平均等待时间、平均周转时间最少。

3. 优先级调度算法

(1)既可用于作业调度,也可用于进程调度。

(2)每次选择优先级最高的作业(或进程)调入内存(或分配处理机)。

(3)根据更高优先级进程是否可以抢占正在执行的进程,分类为:

①抢占式优先级调度算法。

②非抢占式优先级调度算法。

(4)根据进程的优先级是否可以改变,将进程的优先级分类为:

 静态优先级。

②动态优先级。

4.  高响应比优先调度算法 (HRRN)

(1)该算法主要用于作业调度。

(2)既考虑了作业的等待时间,又考虑了作业运行时间。

(3)响应比Rp的计算公式为:

由上式可以看出:

a.  如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,有利于短作业。

b.   当要求服务的时间相同时,作业的优先权又决定于其等待时间,类似于FCFS 算法。

c.  长作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,也可获得处理机,避免“饥饿”。

5. 时间片轮转调度算法

(1)主要适用于分时系统。

(2)每次选择就绪队列中的第一个进程,但是只能运行一个时间片大小。

(3)时间片长短的选择参考因素:系统的响应时间、就绪队列中的进程数目、系统的处理能力。

6. 多级反馈队列调度算法

(1)调度机制

①设置多个就绪队列,并为每个队列赋予不同的优先级。第一队列优先级最高,其余队列优先级依次降低。

②各个队列中进程执行时间片大小不同。优先级越高的队列中进程运行的时间片越小。

③除第n 队列外,每个队列都采用FCFS 算法,第n 队列中按RR 方式运行。

(2)调度算法的优势

①终端型用户:短作业优先。

②短批处理作业用户:周转时间短。

③长批处理作业用户:经过前面队列的部分执行,不会出现“饥饿”。

 、死锁

1.死锁的定义、必要条件和处理方法

(1)死锁的定义

死锁是指多个进程因竞争资源而造成的一种相互等待,若无外力作用,这些进程都将无法继续运行。

(2)产生死锁的原因

①竞争不可抢占性资源。

②进程推进顺序不当。

(3)产生死锁的必要条件(填空题重要考点)

产生死锁必须同时具备下面四个必要条件,只要其中一个条件不成立,死锁就不会发生。

①互斥条件。

②请求和保持条件。

③不可抢占条件。

④循环等待条件。

2. 死锁的处理方法

(1)预防死锁

预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个,从而避免死锁的产生。 【说明】互斥条件是非共享设备所必须的,不仅不能改变,还应加以保护。

①破坏“请求和保持”条件

方法:所有进程在开始运行之前,必须一次性地申请其在整个运行过程中所需的全部资源。

②破坏“不可抢占”条件

方法:当一个进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源。

③破坏“循环等待”条件

方法:对系统所有资源类型进行线性排序,并赋予不同的序号。每个进程必须按序号递增的顺序请求资源。

(2)死锁避免

①系统安全状态

a. 安全状态是指系统能按某种进程推进顺序为每个进程P; 分配其所需资源,直至满足每个进程对资源的最 大需求,使每个进程都可顺利地完成。此时称 (P₁,P₂,…,Pn)           为安全序列。

b.  如果系统无法找到这样一个安全序列,则称系统处于不安全状态。

②利用银行家算法避免死锁

(3)死锁检测

①资源分配图

资源分配图中的符号表示: a. 圆圈代表一个进程。

b. 方框代表一类资源。

c. 方框中的一个点代表一类资源中的一个资源。

d.   由进程出发到资源的有向边表示请求边。

e.   由资源出发到进程的有向边表示分配边。

【说明】资源分配图中有环不一定存在死锁,无环一定没有死锁。

②死锁定理

状态S 为死锁状态的充分条件是当且仅当S 状态的资源分配图不可完全简化。

(4)死锁解除

①资源剥夺法。

②终止(或撤消)进程法。

③进程回退法。

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

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

相关文章

csrf漏洞(三)

本文仅作为学习参考使用,本文作者对任何使用本文进行渗透攻击破坏不负任何责任。 前言: 本文依靠phpstudy以及dvwa靶场进行操作,具体搭建流程参考:xss漏洞(二,xss靶场搭建以及简单利用) 前篇…

ArcGIS10.8 安装教程

目录 一、环境及安装包准备 二、安装流程 1、解压安装包ArcGIS_108.rar 2、安装 三、汉化 四、激活 五、自定义菜单(可选) 六、打开软件按查看 七、安装过程中出现的报错 八、其他 一、环境及安装包准备 安装环境:win7 安装包下载…

集团数字化转型方(五)

集团数字化转型方案通过全面整合人工智能(AI)、大数据分析、云计算和物联网(IoT)等前沿技术,构建了一个高度智能化的业务平台,从而实现业务流程的自动化、数据驱动的决策支持、精准的市场预测、以及个性化的…

基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(一)---UnrealCV获取深度+分割图像

前言 本系列教程旨在使用UE5配置一个具备激光雷达深度摄像机的仿真小车,并使用通过跨平台的方式进行ROS2和UE5仿真的通讯,达到小车自主导航的目的。本教程使用的环境: ubuntu 22.04 ros2 humblewindows11 UE5.4.3python8 本系列教程将涉及以…

Leetcode JAVA刷刷站(58)最后一个单词的长度

一、题目概述 二、思路方向 要解决这个问题,你可以通过遍历字符串 s 并从后往前计数的方式来实现。但更简洁且易于理解的方法是,首先去除字符串尾部的空格(如果有的话),然后找到最后一个单词的起始位置,并计…

XSS反射型和DOM型+DOM破坏

目录 第一关 源码分析 payload 第二关 源码分析 payload 第三关 源码分析 payload 第四关 源码分析 payload 第五关 源码分析 payload 第六关 源码分析 第七关 源码分析 方法一:构造函数 方法二:parseInt 方法三:locat…

【C语言】冒泡排序保姆级教学

C语言冒泡排序保姆级教学 直奔主题&#xff1a; 拿排升序举例子 第一步&#xff1a; 将想要排序的数组中数值最大的那个数排到该数组的最后 具体实现如下图&#xff1a; 第一步代码实现 for (int i 1; i < n ; i)//n为数组大小此处为4 {if (a[i - 1] > a[i])//注意越…

【java基础】IDEA 的断点调试(Debug)

目录 1.为什么需要 Debug 2.Debug的步骤 2.1添加断点 2.2单步调试工具介绍 2.2.1 Step Over 2.2.2 Step Into 2.2.3 Force Step Into 2.2.4 Step Out 2.2.5 Run To Cursor 2.2.6 Show Execution Poiint 2.2.7 Resume Program 3.多种 Debug 情况介绍 3.1行断点 3.2方…

[数据集][目标检测]锤子检测数据集VOC+YOLO格式1510张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;1510 标注数量(xml文件个数)&#xff1a;1510 标注数量(txt文件个数)&#xff1a;1510 标注…

美团外卖新版 web mtgsig 1.2 分析

声明: 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、 敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业 用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 有相关问题请第一时间头像或私信联…

Pcie学习笔记(24)

Ordering and Receive Buffer Flow Control 流量控制(FC)用于防止接收端缓冲区溢出&#xff0c;并使其符合定义的排序规则。请注意&#xff0c;请求者使用流量控制机制来跟踪代理中可用的队列/缓冲区空间&#xff0c;如图2-48所示。也就是说&#xff0c;流控制是点对点的(跨一…

集团数字化转型方案(六)

集团数字化转型方案旨在通过引入前沿技术&#xff0c;如人工智能&#xff08;AI&#xff09;、大数据分析、云计算和物联网&#xff08;IoT&#xff09;&#xff0c;全面提升业务运营效率和市场竞争力。该方案首先实现业务流程的自动化&#xff0c;减少人工干预&#xff0c;通过…

学习C语言 第十八天

第一项 C 强制类型转换 强制类型转换是把变量从一种类型转换为另一种数据类型。可以使用强制类型转换运算符来把值显式地从一种类型转换为另一种类型 (type_name) expression 一个整数变量除以另一个整数变量&#xff0c;得到一个浮点数&#xff1a; eg: #include <st…

AI在线免费数学工具:Qwen2-Math

1、Qwen2-Math https://huggingface.co/spaces/Qwen/Qwen2-Math-Demo

Python爬虫——简单网页抓取(实战案例)小白篇

Python 爬虫是一种强大的工具&#xff0c;用于从网页中提取数据。这里&#xff0c;我将通过一个简单的实战案例来展示如何使用 Python 和一些流行的库&#xff08;如 requests 和 BeautifulSoup&#xff09;来抓取网页数据。 实战案例&#xff1a;抓取一个新闻网站的头条新闻标…

【Qt】 常用控件QLCDNumber

常用控件QLCDNumber QLCDNumber是一个专门用来显示数字的控件&#xff0c;类似于“老式计算机”的效果。 QLCDNumber的属性 属性说明 intValue QLCDNumber 显⽰的数字值(int). value QLCDNumber 显⽰的数字值(double). 和 intValue 是联动的. 例如给 value 设为 1.5, i…

Docker 存储空间不足无法导入加载镜像

问题&#xff1a;在载入镜像时&#xff0c;发现docker没有空间了 解决办法&#xff1a; 更改docker的存储路径 1.添加新的硬盘 docker info #查看docker的存储位置 df -Th #查看占用以及挂载情况 发现没有可用的剩余空间&#xff0c;我们可以添加一个新的硬盘 在linu…

Java之HashMap的底层实现

Java之HashMap的底层实现 摘要HashMap的底层原理哈希值转换为数组下标节点初始化put(Object key, Object value)重写toString()get(Object key)增加泛化remove(K key) 摘要 本博客主要讲述了Java的HashMap的底层实现 HashMap的底层原理 底层原理&#xff1a;数组链表 过程…

Golang | Leetcode Golang题解之第352题将数据流变为多个不相交区间

题目&#xff1a; 题解&#xff1a; type SummaryRanges struct {*redblacktree.Tree }func Constructor() SummaryRanges {return SummaryRanges{redblacktree.NewWithIntComparator()} }func (ranges *SummaryRanges) AddNum(val int) {// 找到 l0 最大的且满足 l0 < val…

Elasticsearch 使用误区之四——不合理的使用 track_total_hits

0、企业级实战问题 在使用 Elasticsearch 进行搜索时&#xff0c;我们常常关心匹配查询的文档总数而将 track_total_hits 设置为 true&#xff0c;如下截图所示&#xff0c;在数据量非常大的情况下这种检索导致的问题是&#xff1a;查询特别慢&#xff0c;聚合会更慢&#xff0…