操作系统CPU调度

2023-11-15

概述

多道程序操作系统的基础。通过在进程之间切换CPU,操作系统可以提高计算机的吞吐率。
对于单处理器系统,每次只允许一个进程运行:任何其他进程必须等待,直到CPU空闲能被调度为止。

CPU按一定的调度算法从就绪队列中选择一个进程,把CPU的使用权交给被选中的进程,如果没有就绪进程,系统会安排一个系统空闲进程或系统空闲进程。

调度触发事件:

  • 创建、唤醒、退出等进程控制操作
  • 进程等待I/O,I/O中断
  • 时钟中断(时间片用完,计时器到时)
  • 出现abort异常

调度过程

同时把多个进程导入内存,在内存中等待的就绪队列的节点是PCB,使得一个进程在CPU中执行I/O时,一个进程用来填补CPU的时间。 通常进程都是在CPU区间和I/O区间之间转换。

CPU调度程序称为短期调度程序,从内存调度到CPU。

抢占调度和非抢占调度(协作):前者为一个进程还没结束之前就被夺取CPU的拥有权,而后者则要一个进程结束或等待I/O才给予其他进程CPU的拥有权。

虽然现代操作系统都是用抢占调度,但是对于同时访问一个数据来说就会有风险,比如一个进程在试图更新一个数据,但是另一个进程抢占,并且读取这个数据,使得数据不一致。进程同步可以使数据得到安全的访问。

调度准则:

  • CPU使用率。
  • 吞吐量:单位时间完成进程的数量。
  • 周转时间:进程提交到进程完成。即从磁盘等待进入内存+就绪队列等待时间+CPU执行时间+I/O执行时间。但是CPU调度算法只是里面的一块。
  • 等待时间:在就绪队列等待的时间之和。
  • 响应时间:用于交互系统。

具体步骤:

  • 保存进程A的上下文环境(程序计数器,程序状态字,其他寄存器)
  • 更新A的PCB(新状态和其他信息)
  • 把进程A移至合适队列(就绪,阻塞,…)
  • 把进程B的状态设置为运行态
  • 从进程B的PCB中恢复上下文(程序计数器,程序状态字,其他寄存器)

上下文切换的开销:

  • 保存和恢复寄存器
  • 切换地址空间(相关指令可能比较昂贵)
  • 缓存和缓冲失效(高速缓存,缓冲区缓存,TLB)

调度算法

各种调度算法:

image

多处理器调度:

  • 需要决定在哪一个CPU上执行
  • 要考虑进程在多个CPU之间迁移的开销(高速缓存失效,TLB失效),尽可能使CPU总在同一个进程上执行
  • 要考虑负载均衡问题

    1. FCFS 先到先服务
      一旦选定进程,那么在结束之前就不能再切换到另一个进程。
    2. SJF 最短优先 精确的讲是最短下一个CPU区间的算法
      前面提到,一个进程是由CPU区间和I/O区间交替组成的。而SJF是看哪个进程的CPU区间最短。
  • SRTF抢占式:又称最短剩余优先,当新进来的进程的CPU区间比当前执行的进程所剩的CPU区间短,则抢占。
  • 非抢占:称为下一个最短优先,因为在就绪队列中选择最短CPU区间的进程放在队头。
    SJF用于长期调度而不能用短期调度,因为进程是一个整体,CPU没法知道进程中第一个CPU区间长度。
    SJF需要确定下一个CPU区间的时间长度,可以通过近似估算出下一个CPU区间的长度,比如tn+1=atn+(1-a)rn tn为最近最近一次的CPU时间,rn为历史记录。a是给定的权重。
    1. 优先级调度算法 pintos的优先级是0-63 0为最低优先级,63为最高优先级
      SJF是特殊的优先级调度算法,以CPU区间长度的倒数为优先级。
      (1)内部优先级:通过内部数据比如内存要求等。
      (2)外部优先级:用户自己设定。set_priority
      分为抢占式和非抢占式,前者为如果进来的进程优先级高于运行的进程,则替换;后者只是在就绪队列中按优先级排队。
      缺点:无线阻塞或饥饿。前者为一个优先级高且运行时间长的进程一直阻塞,后者为优先级低的进程永远都得不到执行。
      解决饥饿的方法是老化。通过每个时间间隔后将等待的进程优先级降低。
    2. 转轮法 RR算法 抢占式
      用于分时系统。每个进程都占用一个时间片的时间。就绪队列为FIFO循环队列。如果一个进程的CPU区间长度小于时间片,则继续下面的进程;如果大于时间片,则中断切换到下一个进程执行。
      通常时间片长度为10ms-100ms,由此需要确定时间片大小使得上下文切换次数适当少。
    3. 多级队列调度
      根据某种性质将一个就绪队列分成不同的独立队列,如系统进程,交互进程(前台进程),交互编辑进程,批处理进程,学生进程。
      每个队列都有不同的调度算法。
      每个队列都有优先级,比如前台队列就比后台队列要有绝对的优先级,因此队列间的分配方法:
  • 只有优先级高的队列为空,才能执行低优先级队列。
  • 为队列分配不同权重的CPU时间,优先级高的分配时间多。

CPU调度例子

  1. 多级反馈队列调度算法(BSD 5.3)

    • 设置多个就绪队列,第一级队列优先级最高
    • 给不同就绪队列中的进程分配不同长度的时间片,随着优先级的降低逐渐增大
    • 当第一级队列为空时,在第二级队列调度,以此类推
    • 各级队列按照时间片轮转方式进行调度
    • 当一个新创建进程就绪后,进入第一级队列
    • 如果进程因为用完时间片而放弃CPU,则进入下一级就绪队列
    • 如果进程因为阻塞而放弃CPU,则进入相应的等待队列,等待事件发生后,该进程回到原来一级就绪队列末尾(或队首)
    • 若允许抢占,被抢占进程回到原来一级就绪队列末尾(或队首)
  2. 基于优先级的抢占式多任务调度(Windows)

    • 调度单位是线程
    • 采用基于优先级的抢占式调度,结合时间配额的调整
    • 就绪线程按优先级进入相应队列
    • 系统总是选择优先级最高的就绪线程运行
    • 同一优先级的各线程按时间片轮转进行调度
    • 多CPU系统中允许多个线程并行运行
参考资料

《操作系统概念》 第七版

http://blog.csdn.net/xiazdong/article/details/6280345

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

操作系统CPU调度 的相关文章

  • seata分布事务

    Seata是什么 官网解释 Seata 是一款开源的分布式事务解决方案 致力于提供高性能和简单易用的分布式事务服务 Seata 将为用户提供了 AT TCC SAGA 和 XA 事务模式 为用户打造一站式的分布式解决方案 用咱们理解的说 s

随机推荐

  • [Pandas]Dataframe中的多条件切片为什么不能使用and运算符

    对于Dataframe中同一列 如果有多个条件 则不能使用and运算符 需要使用 位运算符 示例如下 import pandas as pd df pd DataFrame name a a b b classes 1 2 3 4 pric
  • [哲学部分]马克思主义基本原理概论思维导图

    2020 3 3 更新 之前链接关了补一个 链接 https pan baidu com s 1tsmAkdRG7jE1eMz34Ea4qQ 提取码 7y2j 2019 10 23 更新 由于最近比较忙 没时间一一回复大家的评论和邮件 我把
  • 用选择法对数组中n个整数按由小到大排序

    include
  • 判断python字典中key是否存在的两种方法

    今天来说一下如何判断字典中是否存在某个key 一般有两种通用做法 下面为大家来分别讲解一下 第一种方法 使用自带函数实现 在python的字典的属性方法里面有一个has key 方法 这个方法使用起来非常简单 在python的字典的属性方法
  • 前几天面了个30岁左右的测试员,年薪50w问题基本都能回答上,必是刷了不少八股文···

    互联网行业竞争是一年比一年严峻 作为测试工程师的我们唯有不停地学习 不断的提升自己才能保证自己的核心竞争力从而拿到更好的薪水 进入心仪的企业 阿里 字节 美团 腾讯等大厂 所以 大家就迎来了一堆问题 自己目前的能力能不能够支撑自己晋升 如果
  • 2022年11月26日-12月15日(CesiumGeospatial源码抄写+其他视频教程,本周10小时,合计1757小时,剩余8243小时)

    远程办公中 目前 视频教程进行到了mysql 7 1 tf1 4 4 oss 12 1 蓝图反射 1 7 moba 1 5 webapp 2 4 mmoarpg 00A 04 socket 2 41 按照月计划 制定周计划如下 1 cesi
  • 关于浏览器主页被https://hao.360.com/?src=lm&ls=n78852a3c9b劫持

    一 起因 是我的vscode不支持html文件夹右键用vscode打开 后来百度了下 有两种方法 一种是重新下载vscode 一种是在注册表注册vscode信息 鉴于我的vscode里用很多插件了 懒得再下载就决定使用第二种方法 结果设置到
  • java学习路线

    阶段一 第一阶段 Java 基础 第二阶段 数据库 第三阶段 Java Web 第四阶段 主流框架 第五阶段 服务器中间件 第六阶段 微服务和分布式 第七阶段 练手项目 第一阶段 Java 基础 最开始要学习的是 Java 基础 学习了这部
  • Java实现一个简单的Kafka消息测试程序

    记录一下最近做的一个小程序 模拟很多辆车不定时上报里程等状态数据到Kafka 从而对后端的批处理应用进行性能测试 车辆的上报消息是JSON格式 假设包含如下字段 telemetry engineStatus 1 odometer 120 d
  • Always On 数据库无法自动同步的问题

    问题 在给客户的SQL Server 2019 配置好Always On 之后 不久就出现高可用组里的一个库无法正常同步 第一次出现 以为是偶发性问题 直接右键点击恢复数据同步 没一会就同步好了 过了一个月问题又出现了 这次右键恢复数据同步
  • 计算机网络 概念

    一 计算机网络概念 计算机网络的组成 有若干个节点和连接的节点的链路组成 主机的概念 与网络相连接的计算机称为主机 计算机网络 是一个将分散的 具有独立功能的计算机系统 通过通信设备和线路 由功能完善的软件实现资源共享和信息传递 计算机网络
  • 再谈缓存

    凡是涉及管理数据的系统 都可以用图书馆来考虑 都要面临图书的位置查找和实际摆放两个问题 对应的两大组件就是就是index store 所有的数据管理系统都包含这两部分 缓存从过期又什么触发的角度分为容量触发和时间触发 容量触发 就是缓存满了
  • 内置tomcat整合SpringMVC

    spring MVC是一个基于MVC模式的表现层框架 在spring2 5以后增加了注解功能 使得开发变得更加高效 快捷 由于spring MVC是spring框架的一个模块 springmvc和spring无需通过中间整合层进行整合 可以
  • SQLServer 2008R2 配置允许外网访问

    SQL Server 2008 1433端口启用的解决方案 cqs 2012 CSDN博客
  • R聚类分析航空公司数据(筛选出不同的客户类别)

    效果图如下 图片是将3万四千条航空公司数据用k means算法分成五个类 并通过ggplot2包作图作出来的特征属性 我们将通过不同的属性值 分析出高价值用户 低价值用户 主力用户 一般用户 潜力用户 可以分析得F M C自然是越高越好 C
  • ext3grep恢复linux下误删除的文件

    在linux下使用rm rf时千万要小心 但是总有不小心的时候 导致误删除一些文件 这里我做个试验 故意删除 data 2 txt文件 测试文件恢复 此时2 txt文件已经删除 1 安装ext3grep软件 wget http ext3gr
  • vue之路由的嵌套(父子路由)

    路由的嵌套 1 配置路由 main js文件中 import Users from components Users import UserAdd from components Users UserAdd import UserList
  • 第二章 Scala入门——让你的代码跑起来

    一 Scala的安装方法 要使用Scala 首先需要保证已经安装好了Java 8 对于Linux操作系统 Java 8已经默认安装了 而使用Windows操作系统的用户 则需要在Java官网下载安装包进行安装 请在CMD PowerShel
  • 小米解bl锁跳过168小时_红米K30S至尊纪念版秒解BL工具分享支持小米红米机型秒解BL跳过168小时...

    目前小米的新机 官方风控都默认绑定7天也就是168小时才能解锁BL 部分账号需要绑定15天才能满足条件 导致很多爱玩机的小伙伴被拒门外 并不是所有人都愿意等待官方解锁时候 而跳过168小时解锁 也成为了很多小伙伴希望的事情 本工具来自ROM
  • 操作系统CPU调度

    概述 多道程序操作系统的基础 通过在进程之间切换CPU 操作系统可以提高计算机的吞吐率 对于单处理器系统 每次只允许一个进程运行 任何其他进程必须等待 直到CPU空闲能被调度为止 CPU按一定的调度算法从就绪队列中选择一个进程 把CPU的使