0202-1-处理机调度与死锁

第三章:处理机调度与死锁

在这里插入图片描述

处理机调度算法的目标

处理机调度算法的共同目标

  • 资源利用率:CPU的利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
  • 公平性
  • 平衡性
  • 策略强制执行

批处理系统的目标

  • 平均周转时间短
  • 系统吞吐量高
  • 处理机利用率高

分时系统的目标

  • 响应时间快
  • 均衡性

实时系统目标

  • 截止时间的保证
  • 可预测性

处理机调度的层次

  • 高级调度(作业调度)
    • 分时系统无需作业调度,因为需要交互
    • 批处理系统需要作业调度
  • 中级调度(和挂起有关)
  • 低级调度(进程调度)
    • 进程调度是最基本的调度,任何操作系统都有进程调度。
    • 低级调度的三个基本机制
      • 排队器
      • 分派器
      • 上下文切换
    • 进程调度方式
      • 非抢占方式
      • 抢占方式
        • 优先权原则
        • 短进程优先原则
        • 时间片原则
    • 进程调度的任务
      • 保存处理机的现场信息
      • 按某种算法选取进程
      • 把处理器分配给进程
    • 进程调度的算法
      • 优先级调度算法
        • 优先级调度算法的类型
          • 非抢占式优先级调度算法
            • 等当前进程执行完以后,再执行另一个优先权最高的进程
            • 这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中。
          • 抢占式优先级调度算法
            • 不等当前进程结束,直接抢处理机
            • 常用于要求比较严格的实时系统中, 以及对性能要求较高的批处理和分时系统中。
        • 优先级的类型
          • 静态优先级
            • 优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。一般地,优先权是利用某一范围内的一个整数来表示的,例如,07或0255中的某一整数, 又把该整数称为优先数。
            • 可以参考BIOS系统中设置boot的优先级
          • 动态优先级
            • 在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。
      • 轮转调度算法
        • 基本原理:在轮转(RR)法中,系统根据FCFS策略,将所有的就绪进程排成一个就绪队列,并可设置每隔一定时间间隔(如30ms)即产生一次中断,激活系统中的进程调度程序,完成一次调度,将CPU分配给队首进程,令其执行
        • 进程切换时机
          • 时间片未用完,进程完成
          • 时间片到,进程未完成
        • 时间片大小的确定
          • 太小利于短作业,增加系统切换开销
          • 太长就退化为FCFS算法
          • 一般选择: q略大于一次交互所需要的时间,使大多数进程在一个时间片内完成
        • 一般来说,平均周转时间将比SJF长,但是有较好的响应时间
      • 多队列调度算法
      • 多级反馈队列调度算法
        • 调度机制
          • 设置多个就绪队列
          • 每个队列都采用FCFS算法
          • 按照队列优先级调度,在第n队列中采取按时间片轮转的方式运行
        • 调度算法的性能
          • 对于终端型用户,由于作业小,感觉满意
          • 对于短批处理作业用户,周转时间也较小
          • 长批处理作业用户,也能够得到执行
      • 基于公平原则的调度算法
        • 保证调度算法
        • 公平分享调度算法

作业与作业调度

作业

  • 作业不仅包含程序和数据,还配有一份作业说明书,系统根据说明书对程序的运行进行控制。批处理系统是以作业为单位从外存掉入内存的。

作业控制块JCB

  • 为每个作业设置一个JCB,保存了对作业管理调度的全部信息。是作业存在的标志。

作业步

  • 作业步,每个作业都必须经过若干相对独立,有相互关联的顺序步骤才能得到结果。每一个步骤就是一个作业步。

作业运行的三个阶段

  • 收容阶段
  • 运行阶段
  • 完成阶段

作业运行的三个状态

  • 后备状态
  • 运行状态
  • 完成状态

作业调度的主要任务

  • 接纳多少个作业
  • 接纳哪些作业

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

  • 比较有利于长作业,而不利于短作业。
  • 有利于CPU繁忙的作业,而不利于I/O繁忙的作业。

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

  • 优点
    • 比FCFS改善平均周转时间和平均带权周转时间,缩短作业的等待时间;
    • 提高系统的吞吐量;
  • 缺点
    • 必须预知作业的运行时间
    • 对长作业非常不利,长作业的周转时间会明显地增长
    • 在采用SJF算法时,人–机无法实现交互
    • 该调度算法完全未考虑作业的紧迫程度,故不能保证紧迫性作业能得到及时处理

优先级调度算法(priority–scheduling algorithm,PSA)

高响应比优先调度算法(Highest Response Ratio Next,HRRN)

  • 原理
    • 在每次选择作业投入运行时,先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行
    • 优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间=1+等待时间/要求服务时间
  • 特点
    • 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而类似于SJF算法,有利于短作业
    • 当要求服务的时间相同时,作业的优先权又决定于其等待时间,因而该算法又类似于FCFS算法
    • 对于长时间的优先级,可以为随等待时间的增加而提高,当等待时间足够长时,也可获得处理机

实时调度(HRT和SRT任务)

实现实时调度的基本条件

  • 提供必要信息
    • 就绪时间
    • 开始截止时间和完成截止时间
    • 处理时间
    • 资源要求
    • 优先级
  • 系统处理能力强
    • ∑(Ci/Pi)≤1
    • N个处理机:∑(Ci/Pi)≤N
  • 采用抢占式调度机制
  • 具有快速切换机制
    • 对中断的快速响应能力
    • 快速的任务分派能力

实时调度算法的分类

  • 非抢占式调度算法
    • 非抢占式轮转调度算法
    • 非抢占式优先调度算法
  • 抢占式调度算法
    • 基于时钟中断的抢占式优先级调度算法
    • 立即抢占的优先级调度算法

最早截止时间优先EDF(Earliest Deadline First)算法

  • 根据任务的开始截至时间来确定任务的优先级
    • 截至时间越早,优先级越高
  • 非抢占式调度方式用于非周期实时任务
  • 抢占式调度方式用于周期实时任务

最低松弛度优先LLF(Least Laxity First)算法

  • 类似EDF
  • 算法根据任务紧急(或松弛)的程度,来确定任务的优先级。任务的紧急程度愈高,为该任务所赋予的优先级就愈高, 以使之优先执行。
  • 松弛度例子
    • 例如,一个任务在200ms时必须完成,而它本身所需的运行时间就有100ms,因此,调度程序必须在100 ms之前调度执行,该任务的紧急程度(松弛程度)为100 ms

优先级倒置(Priority inversion problem)

  • 优先级倒置的形成
    • 高优先级进程被低优先级进程延迟或阻塞。
  • 优先级倒置的解决方法
    • 简单的:假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占
    • 实用的:建立在动态优先级继承基础上的

死锁概述

资源问题

  • 可重用性资源
    • 计算机外设
  • 消耗性资源
    • 数据,消息
  • 可抢占性资源
    • 不引起死锁
    • CPU,内存
  • 不可抢占性资源
    • 光驱,打印机

计算机系统中的死锁

  • 竞争不可抢占性资源引起死锁
  • 竞争可消耗资源引起死锁
  • 进程推进顺序不当引起死锁

死锁的定义,必要条件和处理方法

  • 定义:如果一组进程中的每一个进程都在等待仅由该进程中的其他进程才能引发的事件,那么该组进程是死锁的
  • 产生死锁的必要条件
    • 互斥条件
    • 请求和保存条件
    • 不可抢占条件
    • 循环等待条件
      • 如果每个资源只有一个实例,则环路等待条件是死锁存在的充分必要条件
  • 处理死锁的方法
    • 预防死锁
      • 静态方法,在进程执行前采取的措施,通过设置某些限制条件,去破坏产生死锁的四个条件之一,防止发生死锁。
      • 预防死锁的策略
        • 破坏"请求和保存"条件
          • 第一种协议
            • 所有进程在开始运行之前,必须一次性地申请其在整个运行过程中所需的全部资源
            • 优点:简单,易行,安全
            • 缺点
              • 资源被严重浪费,严重地恶化了资源的利用率
              • 使进程经常会发生饥饿现象
          • 第二种协议
            • 它允许一个进程只获得运行初期所需的资源后,便开始运行。进程运行过程中再逐步释放已分配给自己的,且已用毕的全部资源,然后再请求新的所需资源
        • 破坏"不可抢占"条件
          • 当一个已经保存了某些不可被抢占资源的进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请
        • 破坏"循环等待"条件
          • 对系统所以资源类型进行线性排序,并赋予不同的序号
          • 例如令输入机的序号为1,打印机序号为2,磁盘机序号为3等。所有进程对资源的请求必须严格按资源序号递增的次序提出。
    • 避免死锁
      • 动态的方法,在进程执行过程中采取的措施,不需事先采取限制措施破坏产生死锁的必要条件,而是在进程申请资源时用某种方法去防止系统进入不安全状态,从而避免发生死锁。如银行家算法
      • 避免死锁的策略
        • 系统安全状态
          • 安全状态
            • 某时刻,对于并发执行的n个进程,若系统能够按照某种顺序如<p1,p2…pn>来为每个进程分配所需资源,直至最大需求,从而使每个进程都可顺利完成,则认为该时刻系统处于安全状态,这样的序列为安全序列
          • 安全状态之例
          • 由安全状态向不安全状态的转换
        • 利用银行家算法避免死锁
          • 含义:每一个新进程在进入系统时,它必须申明在运行过程中,可能需要每种资源类型的最大单元数目,其数目不应超过系统所拥有的资源总量。当进程请求一组资源时,系统必须首先确定是否有足够的资源分配给该进程。若有,再进一步计算在将这些资源分配给进程后,是否会使系统处于不安全状态。如果不会,才将资源分配给它,否则让进程等待
          • 银行家算法中的数据结构
            • 可用资源向量 Available[m]:m为系统中资源种类数,Available[j]=k表示系统中第j类资源数为k个。
            • 最大需求矩阵 Max[n,m]:n为系统中进程数,Max[i,j]=k表示进程i对j类资源的最大需求数为中k。
            • 分配矩阵 Allocation[n,m]:它定义了系统中每一类资源当前已分配给每一进程资源数, Allocation[i,j] = k表示进程i已分得j类资源的数目为k个。
            • 需求矩阵 Need[n,m]:它表示每个进程尚需的各类资源数,Need[i,j]=k 表示进程i 还需要j类资源k个。Need[i,j]=Max[i,j] - Allocation[i,j]
          • 银行家算法
          • 安全性算法
          • 银行家算法之例
          • 解题
            • 矩阵
            • 列表
    • 检测死锁
      • 死锁的检测与解除
        • 死锁的检测
          • 资源分配图
            • 简化步骤
              • 选择一个没有阻塞的进程p
              • 将p移走,包括它的所有请求边和分配边
              • 重复步骤1,2,直至不能继续下去
          • 死锁定理
            • 若一系列简化以后不能使所有的进程节点都成为孤立节点
          • 检测时机
            • 当进程等待时检测死锁 (其缺点是系统的开销大)
            • 定时检测
            • 系统资源利用率下降时检测死锁
          • 死锁检测中的数据结构
        • 死锁的解除
          • 抢占资源
          • 终止(或撤销)进程
          • 终止进程的方法
            • 终止所有死锁进程
            • 逐个终止进程
              • 代价最小
                • 进程的优先级的大小
                • 进程已执行了多少时间,还需时间
                • 进程在运行中已经使用资源的多少,还需多少资源
                • 进程的性质是交互式还是批处理的
          • 付出代价最小的死锁解除算法
            • 是使用一个有效的挂起和解除机构来挂起一些死锁的进程
    • 解除死锁

XMind: ZEN - Trial Version

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

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

相关文章

帅气的性能监控平台Grafana(Windows下使用Grafana监控系统指标与GPU指标)

帅气的性能监控平台Grafana&#xff08;Windows下使用Grafana监控系统指标与GPU指标&#xff09; 前情提要 系统环境准备 windows_exporter下载 nvidia_gpu_exporter下载 prometheus下载 Grafana下载 安装指导 windows_exporter安装与nvidia_gpu_exporter安装 promethe…

Mac brew教程

一、安装brew /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"二、查看brew版本 brew -vbrew -v 三、搜索软件 命令格式&#xff1a;brew search 软件名 eg&#xff1a; brew search nginx四、安装软件 命令格…

布局技巧及CSS初始化

一&#xff0c;margin负值巧妙应用 二&#xff0c;文字围绕浮动元素 三&#xff0c;行内块 四&#xff0c;CSS三角强化 五&#xff0c;CSS初始化 一&#xff0c;margin负值巧妙应用 制作盒子的细线边框&#xff1a; 鼠标经过li后变色&#xff1a; 二&#xff0c;文字围绕…

遇到ubuntu设置交叉编译环境的问题

今天交叉编译器一直没安装成功&#xff0c;环境变量也配置了还是不对&#xff0c;最后发现Ubuntu是64位的要装 然后就好了 另外在进行嵌入式Linux开发的时候&#xff0c;要把主机、虚拟机、以及开发板设置在同一网段下&#xff0c;虚拟机一般设成临时的就可以&#xff0c;但是…

POI操作word表格,添加单元格,单元格对齐方法(不必合并单元格)

添加单元格&#xff0c;直接对row进行create新的cell&#xff0c;则会导致新创建的单元格与前面的单元格不对齐的现象。 //表格信息XWPFTable table doc.createTable();table.setWidth("100%");//第一行XWPFTableRow row0table.getRow(0);XWPFTableCell cell00row0.…

机器学习:多项式回归(Python)

多元线性回归闭式解&#xff1a; closed_form_sol.py import numpy as np import matplotlib.pyplot as pltclass LRClosedFormSol:def __init__(self, fit_interceptTrue, normalizeTrue):""":param fit_intercept: 是否训练bias:param normalize: 是否标准化…

无法在 word 中登录 Grammarly

目录 1. 情况描述 2. 解决方法 3. 原因分析 1. 情况描述 在浏览器中可以登录 Grammarly&#xff0c;但是在 word 中登录失败&#xff0c;大致如下图所示&#xff1a; 我自己没有截图&#xff0c;这是网上别人的图&#xff0c;但差不多都长这个样子。 2. 解决方法 我点击了…

AJAX-入门

定义 概念&#xff1a;AJAX是浏览器与服务器进行数据通信的技术 使用 1.先使用axios库&#xff0c;与服务器进行数据通信 1&#xff09;基于XMLHttpRequest封装、代码简单、月下载量在14亿次 2&#xff09;Vue、React项目中都会用到axios 2.再学习XMLHttpRequest对象的使用…

基于微服务的高考志愿智能辅助决策系统(附源码)

目录 一.引言 1、编写目的 2、系统功能概述 二.功能分析 三.微服务模块 1、微服务用户相关模块 &#xff08;1&#xff09;用户注册 &#xff08;2&#xff09;用户登录 &#xff08;3&#xff09;用户信息管理 &#xff08;4&#xff09;用户操作 2、微服务文件云存…

day37WEB攻防-通用漏洞XSS跨站权限维持钓鱼捆绑浏览器漏洞

目录 XSS-后台植入 Cookie&表单劫持&#xff08;权限维持&#xff09; 案例演示 XSS-Flash 钓鱼配合 MSF 捆绑上线 1、生成后门 2、下载官方文件-保证安装正常 3、压缩捆绑文件-解压提取运行 4、MSF 配置监听状态 5、诱使受害者访问 URL-语言要适当 XSS-浏览器网马…

Matlab处理excel数据

我们新建个excel文档&#xff0c;用Matlab读取里面的内容&#xff0c;计算和判断里面的计算结果是否正确&#xff0c;并打印到另一个文档当中。 新建文档 新建输入文档&#xff0c;文件名TestExcel 编写脚本 [num,txt] xlsread(TestExcel.xlsx); SNcode num(:,1);%从序号中…

回归预测 | Matlab实现CPO-LSSVM冠豪猪算法优化最小二乘支持向量机多变量回归预测

回归预测 | Matlab实现CPO-LSSVM冠豪猪算法优化最小二乘支持向量机多变量回归预测 目录 回归预测 | Matlab实现CPO-LSSVM冠豪猪算法优化最小二乘支持向量机多变量回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab实现CPO-LSSVM冠豪猪算法优化最小二乘支持向…

洛谷P8599 [蓝桥杯 2013 省 B] 带分数

[蓝桥杯 2013 省 B] 带分数 题目描述 100 100 100 可以表示为带分数的形式&#xff1a; 100 3 69258 714 100 3 \frac{69258}{714} 100371469258​。 还可以表示为&#xff1a; 100 82 3546 197 100 82 \frac{3546}{197} 100821973546​。 注意特征&#xff1a;带分…

Prompt Learning 的几个重点paper

Prefix Tuning: Prefix-Tuning: Optimizing Continuous Prompts for Generation 在输入token之前构造一段任务相关的virtual tokens作为Prefix&#xff0c;然后训练的时候只更新Prefix部分的参数&#xff0c;PLM中的其他参数固定。针对自回归架构模型&#xff1a;在句子前面添…

Django模型(八)

一、修改数据 先获取对象,通过对象属性更新数据,再保存 (更新单一数据)通过QuerySet的update函数更新数据 (更新多条数据) #单条记录修改 save c = Cook.objects.get(pk=1) c.name = 安妮 c.save()# 更新多个值 update Cook.objects.filter(sect=粤菜).update(level=5)1.1、…

SD-WAN如何解决企业网络面临的问题?

企业网络在不断增长和发展的同时&#xff0c;所面临的问题也越来越多。SD-WAN作为一项崭新的网络技术&#xff0c;正迅速成为企业的首选。究竟SD-WAN在解决企业网络问题上有何独特之处呢&#xff1f; 优化网络性能与带宽利用率 传统广域网常常面临多地点数据传输时的高延迟、低…

【深蓝学院】移动机器人运动规划--第3章 基于采样的路径规划--作业

0. Assignment T1. MATLAB实现RRT 1.1 GPT-4任务分析 RRT伪代码&#xff1a; 任务1即使用matlab实现RRT&#xff0c;结合作业所给框架&#xff0c;简单梳理&#xff0c;可结合1.2代码理解&#xff1a; 设置start&#xff0c;goal&#xff0c;near to goal threshold Thr&am…

MySql主从同步,同步SQL_ERROR 1032解决办法

1.登录从库 mysql -u root -p 2.输入命令查看状态 SHOW SLAVE STATUS\G; 3.找到对应的错误数据位置 Slave_IO_Running: YesSlave_SQL_Running: NoReplicate_Do_DB: app_push_centerReplicate_Ignore_DB: Replicate_Do_Table: Replicate_Ignore_Table: Replicate_Wild_Do_Tabl…

github连不上

github连不上 错误提示解决方案steam 采用Hosts加速 错误提示 fatal: unable to access ‘https://github.com/Ada-design/qianduan.git/’: Failed to connect to github.com port 443 after 21073 ms: Couldn’t connect to server 解决方案 下载steam https://steampp.ne…

Flutter的安装与环境配置

一、下载安装Futter&#xff1a; 1、Flutter中文文档&#xff1a; 安装和环境配置 - Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 2、下载 Futter SDK&#xff1a; Flutter中文文档 里面有&#xff0c;下载完成之后找个文件夹解压出来&#xff0c;最好不要将 Flu…