notebooks
  • notebooks
  • _planning
    • 2022 OKR
    • basketball
    • swimming
  • communication
    • Dubbo
    • Kafka
    • Messaging
    • RPC
    • Thrift
  • computation
    • map-reduce
  • cs-basic-knowledge
    • computer-architecture
    • data-structure-and-algorithms
    • networks
    • os
  • devops
    • Docker
    • Linux
    • Prometheus
    • operations
    • security
    • trouble-shooting
  • distributed-knowledge
    • Zookeeper_CMD
    • distributed-system
  • game-engine
    • Unity
  • others
    • appium使用
  • protocols
    • http(s)协议
    • 官方链接
    • sip
  • storage
    • Elasticsearch
    • GuavaCache
    • MySQL
    • MySQL_CMD
    • NoSQL
    • Redis
    • Redis_CMD
  • system-design
    • system-design
  • tools
    • Git
    • IDEA
    • Mac
    • VScode
    • Vim
  • _working
    • doc-template
      • backend-design-review
      • correction-of-error
      • service-review
    • process
      • domain-backup
      • oncall
  • blogs
    • history
      • 8088/8086微处理器
      • 8088/8086指令系统
      • CSS-DOM
      • CSS定位
      • CSS工作原理
      • CSS控制背景
      • CSS浮动布局
      • CSS盒模型
      • Chrome开发者工具使用方法
      • DOM
      • Django Model模型层学习
      • Django-REST-framework Serializers学习
      • Django-REST-framework Views和ViewSets学习
      • Django View视图层学习
      • Gvim下Emmet安装及使用教程
      • HTTP协议简介
      • HashMap原理初探
      • JavaScript简史
      • JavaScript语法
      • Java内存模型和GC机制
      • Java基础——Lambda学习
      • Java基础——方法引用
      • Java基础——枚举类型
      • Java类加载机制
      • KMP算法
      • Kafka学习
      • Linux下用命令行编译Java程序
      • MathJax简介和基本用法
      • Python实现常见数据结构
      • Python装饰器总结
      • TCP协议的三次握手和四次挥手
      • Thrift学习
      • asyncio学习
      • markdown的常用语法
      • 修改hosts文件实现翻墙
      • 充实文档的内容
      • 关系数据库
      • 关系数据库标准语言SQL(一)
      • 关系数据库标准语言SQL(二)
      • 关系数据理论
      • 关系查询处理和查询优化
      • 内联元素和块级元素
      • 剑指offer算法题练习
      • 动态创建标记
      • 图形化用户界面
      • 在Eclipse中使用Maven构建Java Web项目
      • 增加微博秀遇到的一些问题
      • 处理机调度
      • 如何用github和hexo搭建个人博客
      • 存储管理
      • 存储系统的层次结构
      • 学习模仿lionhit网站首页的过程总结
      • 实用的GitHub小技巧
      • 并发控制
      • 循环与分支程序设计
      • 指令系统的设计
      • 指令级并行及其开发——硬件方法
      • 搭建自己的VPN服务器
      • 操作系统用户界面
      • 数据库安全性
      • 数据库完整性
      • 数据库恢复技术
      • 数据库绪论
      • 数据库编程
      • 数据库设计
      • 数据抽象
      • 文件系统
      • 文法和语言
      • 最佳实践
      • 案例研究:JavaScript图片库
      • 案例研究:图片库改进版
      • 汇编语言程序格式
      • 汇编语言程序设计基础知识
      • 流水线技术
      • 深度优先搜索和广度优先搜索
      • 牛客网——网易2017秋招编程题集合
      • 用JavaScript实现动画效果
      • 第一篇博客
      • 经典排序算法总结(Java实现)
      • 经典查找算法总结(Java实现)
      • 综合示例
      • 编译原理引论
      • 背包、队列和栈
      • 虚拟机安装Linux系统及常用软件
      • 计算机操作系统绪论
      • 计算机系统结构的基础知识
      • 设备管理
      • 设计模式之代理模式
      • 设计模式之单例模式
      • 设计模式之工厂模式
      • 设计模式之策略模式
      • 设计模式之观察者模式
      • 词法分析
      • 进程管理
      • 闭包
      • 阻止Google自动跳转到香港服务器的方法
      • 项目部署过程
  • programming-language
    • C#
      • C#
    • C&C++
      • C
    • C&C++
      • C++
    • Java
      • GoogleGuice
    • Java
      • JVM
    • Java
      • Java
    • Java
      • Maven
    • Java
      • Mybatis
    • Java
      • Spring知识
    • Java
      • SpringBoot
    • Java
      • Tomcat
    • Python
      • Python
    • Shell
      • Shell
  • wheels
    • dcc
      • 产品调研
      • 方案设计
    • red-envelope
      • 方案设计
    • short-url
      • 短链接服务
    • sso
      • 方案设计
Powered by GitBook
On this page
  • 分级调度
  • 调度层次
  • 作业的状态及转换
  • 作业和进程的关系
  • 调度性能的衡量
  • 作业调度
  • 作业控制块
  • 作业调度及功能
  • 作业调度目标与性能衡量
  • 进程调度
  • 进程调度的功能
  • 进程调度的时机
  • 进程调度的方式
  • 进程调度性能衡量
  • 调度算法
  • 先来先服务算法
  • 短作业优先法
  • 最高响应比优先法
  • 时间片轮转法
  • 多级队列算法
  • 优先级法
  • 多级反馈轮转法
  1. blogs
  2. history

处理机调度

处理机调度的核心是对CPU资源进行合理的分配使用。

分级调度

调度层次

  • 作业调度(宏观调度、高级调度)

    • 按一定原则选择外存后备队列中的作业,为其分配内存等资源,并建立进程,使其获得竞争处理机的资格,进入就绪队列。此外,在作业执行完毕时,回收系统资源。

  • 交换调度(中级调度:内外存交换)

    • 按给定策略,将外存中处于就绪状态或等待状态的进程调入内存,或将内存中暂时不能运行的进程调至外存,以提高内存利用率和系统吞吐量。

  • 进程调度(微观调度、低级调度)

    • 决定就绪队列中的哪个进程应获得处理机,为其进行进程上下文切换以建立相应的执行环境(即由处理机调度程序将处理机分配给某就绪进程,处理机调度程序常驻内存)

  • 线程调度:进程中相关堆栈和控制表等的调度

    • 可有OS内核完成,也可由用户程序进行

作业的状态及转换

作业从提交给系统,直到完成任务退出系统前,在整个活动过程中它会处于不同的状态

  • 提交状态:一个作业处于从输入设备进入外部存储设备的过程时所处的状态

  • 后备状态:作业的全部信息都已通过输入设备输入到外存输入井中,等待进入内存

  • 执行状态:作业一旦被作业调度程序选中,则为其分配所需的资源,并创建进程,送入内存中投入运行

  • 完成状态:作业运行完毕,准备退出系统时的状态(所占用的资源尚未全部被系统回收)

作业和进程的关系

作业是用户向计算机提交任务的任务实体。

进程是计算机为了完成用户任务实体而设置的执行实体。

计算机要完成一个任务实体,必须要有一个以上的执行实体,即一个作业是由一个以上的进程组成。 系统必须为一个作业创建一个根进程,然后再根据任务要求创建相应的子进程

调度性能的衡量

面向用户的性能衡量

  • 周转时间:作业从提交到完成(得到结果)所经历的时间。包括:在收容队列中等待,CPU上执行,就绪队列和阻塞队列中等待,结果输出等待等

    • 平均周转时间T

    • 平均带权周转时间W(综合考虑周转时间和执行时间)

  • 响应时间:用户发出命令(如击键,输入一个请求)到系统响应给出执行结果(如屏幕显示)所经历的时间

面向系统的性能衡量

  • 吞吐量:给定时间内所完成的作业总数。跟作业本身特性和调度算法都有关系

  • 设备(处理机)利用率

  • 设备的均衡利用:如CPU繁忙的作业和I/O繁忙的作业搭配

  • 公平性:避免某些作业的等待时间过长

  • 优先级

调度算法本身的性能衡量

  • 易于实现

  • 执行开销比

作业调度

作业控制块

作业调度及功能

作业调度的任务:完成作业从后备状态到执行状态的转变,以及从执行态到完成态的转变。

作业调度的具体功能

  • 记录系统中各个作业的情况;(记录情况)

  • 按照某种调度算法从后备作业队列中选取作业;(挑选作业)

  • 为被选取的作业分配内存、外设等需要的资源;(分配资源)

  • 为选中的作业建立相应的进程。(建立进程)

  • 在作业运行完毕或运行过程中因某种原因需要撤离时,进行善后处理工作,回收所占用的全部资源,撤消相关的进程及JCB。(善后处理)

作业调度目标与性能衡量

调度目标:

  • 尽量公平合理

  • 尽可能高的设备利用率

  • 执行尽可能多的作业

  • 尽快的响应时间

调度算法性能的衡量

  • 平均周转时间(假定某作业i的提交时间为Tsi,完成时间为Tei)

    • 作业的周转时间为:$T_i=T_{ei}-T_{si}$

    • 作业的平均周转时间为:$T=\frac1n\sum_{i=1}^nT_i$。(其中,n为作业流中的作业数)

  • 平均带权周转时间

    • 作业的带权周转时间为:$W_i=\frac{T_i}{r_i}$

    • 作业的平均带权周转时间为:$W=\frac1n\sum_{i=1}^n\frac{T_i}{r_i}$

  • 平均响应时间(分时、实时系统)

进程调度

进程调度的功能

进程调度的任务是控制协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选择一个进程,并把CPU的使用权交给被选中的进程。

进程调度的功能:

  1. 记录所有进程的执行状况(静态和动态)

  2. 按一定策略,选择一个就绪进程

  3. 完成进程上下文切换

进程(上下文)切换的步骤:

  1. 检查是否可以进行进程切换(如:原语执行时不可)

  2. 保存被切换进程的现场(如:程序计数器、寄存器),并移至合适的(就绪、阻塞)队列

  3. 选取一个新进程

  4. 恢复被选中进程的现场:装配该进程的正文,使其获得CPU控制权

进程调度的时机

进程调度的时机与引起进程调度的原因及进程调度方式有关。

引起进程调度的原因有(原因之一发生时引发):

  • 正在执行的进程运行完毕,或由于某种错误而终止运行

  • 执行中的进程自己调用阻塞原语,将自己阻塞起来进入等待状态

  • 执行中的进程执行了P原语操作,因资源不足而被阻塞,或执行了V原语操作激活了等待资源的进程队列

  • 执行中的进程提出I/O请求后被阻塞

  • 执行完系统调用,在系统程序返回用户进程时,可调度选择一新的用户进程执行

  • 分时系统中时间片到

  • 当有一个优先级更高的进程就绪(可抢占式)

进程调度的方式

  • 非抢占式 Non-preemptive(非剥夺式) 某一进程被调度执行后,将一直执行直到完成或发生某事件被阻塞,即是由于自身的原因而让出CPU。

  • 抢占式 Preemptive(可剥夺式) 由于优先权、短作业优先或时间片到等因素,系统强行剥夺正在执行进程的CPU。

进程调度性能衡量

  • 定性衡量

    • 公平性

    • 可靠性(避免因调度引起的破坏,对调度时机的选择和CPU现场的保护要十分谨慎)

    • 简洁性(避免调度程序消耗较大的系统开销)

  • 定量评价

    • CPU利用率

    • 响应时间(交互式系统)

    • 吞吐量(批处理系统)

调度算法

先来先服务算法

FCFS法(First Come First Serve)基本思想:按照作业提交/进程变为就绪状态的先后次序,调入系统或分派CPU,换句话说,调度程序每次选择的作业/进程是等待时间最久的,而不管其运行时间的长短。

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

特点

  • 系统开销小,实现简单

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

短作业优先法

SJF法(Shortest Job First)基本思想:对预计执行时间短的作业(进程)优先处理。通常后来的短作业不抢先正在执行的作业。

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

优点:

  • 缩短作业的等待时间

  • 提高系统的吞吐量

  • 比FCFS平均周转时间和平均带权周转时间短

缺点:

  • 对长作业非常不利,可能长时间得不到执行

  • 未能依据作业的紧迫程度来划分执行的优先级

  • 难以准确估计作业(进程)的执行时间,从而影响调度性能

最高响应比优先法

HRN法(Highest Response_Ratio Next)基本思想:响应比高者优先调度算法是介于先来先服务和短作业优先这两种算法之间的一种拆衷的算法,同时考虑每个作业的等待时间和估计需要的运行时间,从中选出响应比最高的作业投入运行。

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

时间片轮转法

RR法(Round Robin)基本思想:(使等待时间与享受服务的时间成正比)

  • 将系统中所有的就绪进程按照FCFS原则,排成一个队列。

  • 每次调度时将CPU分派给队首进程,让其执行一个时间片。时间片的长度从几个ms到几百ms。

  • 在一个时间片结束时,发生时钟中断。调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。

  • 进程可以未使用完一个时间片,就提前调度(如完成/阻塞)

可用于进程调度,但不能用于作业调度。

时间片长度的影响

  • 过长: 退化为FCFS算法,进程在一个时间片内可以都执行完。

  • 过短: 一个进程需要多个时间片才能处理完,上下文切换频繁,开销增加。

对时间片长度的要求:q (时间片长度) = R(要求的响应时间) / N (最大进程数)

时间片长度的影响因素:

  • 系统的响应时间:时间片越大,响应时间越长(当进程数一定时)

  • 就绪进程的数目:数目越多,时间片越小(当响应时间一定时)

  • CPU运行速度:CPU运行速度快,则时间片可以短些;反之,则取长些。

多级队列算法

根据作业或进程的性质或类型的不同,将后备或就绪队列再分为若干个子队列。各队列有不同的调度算法。

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

优先级法

本算法是对优先级高的作业/进程优先处理。可分成抢先式和非抢先式。

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

  1. 静态优先级 根据作业/进程的静态特性,优先级在作业/进程开始执行前就确定,直到终止都不改变。通常是一个整数。(静态优先级可由用户/系统/操作员确定) 确定静态优先级的依据:

  • 作业/进程类型(如:系统进程优先级较高)

  • 用户要求(紧迫程度和付费多少:系统对高优先级用户收取较高的费用)

  • 对资源的需求(对CPU和内存需求较少的进程,优先级较高)

  1. 动态优先级 创建时赋予的优先级,在运行过程中可以不断改变,以便获得更好的调度性能。

  2. 线性优先级调度算法——SRR法(Selfish Round Robin)

  • 基本思想 就绪进程队列分成两个:

    • 新创建进程队列:按FCFS方式排队;进程优先级按速率a增加;

    • 享受服务进程队列:已得到过时间片服务的进程也按FCFS方式排队;进程优先级按速率b增加;(a>b>0)

  • 新创建进程队列中的队首进程转入享受服务队列的条件:

    • 当新创建进程队列中的头一个进程的优先级与享受服务进程队列中最后一个进程的优先级相同时

    • 当享受服务队列为空时

多级反馈轮转法

多级反馈轮转法是时间片轮转法和优先级法的综合和发展。

多级反馈轮转法的基本思想

  • 设置多个就绪队列,分别赋予不同的优先级,如:

    • 优先级逐级降低,队列1的优先级最高。

    • 每个队列执行时间片的长度也不同,规定优先级越低,则时间片越长,如逐级加倍

  • 每个队列按FCFS原则排队。

  • 同一队列内优先级相同。

  • 仅当较高优先级的队列为空,才调度较低优先级的队列中的进程执行。

  • 新进程进入内存后,先投入队列1的末尾;若按队列1的一个时间片未能执行完,则降低投入到队列2的末尾;如此下去,直到最后一个队列(最低级)。

  • 最后一个队列(最低级)中的进程采用时间片轮转的方式进行调度。

多级反馈轮转法的优点:

  • 不必估计进程的执行时间,动态调节

  • 能较好地满足各种要求,提高系统吞吐量、缩短响应时间和平均周转时间

    • 短进程:能在较高优先级队列上的时间片内完成

    • 长进程:不必担心长期得不到处理

  • 系统开销小


《计算机操作系统教程(第3版)》张尧学 史美林 张高 著

Previous增加微博秀遇到的一些问题Next如何用github和hexo搭建个人博客

Last updated 3 years ago

处理机调度1

系统为每个作业设置了一个作业控制块(JCB),记录已进入系统的各作业的情况,以便于管理和调度作业。 JCB的主要内容

作业从后备状态到执行状态

作业从执行状态到完成状态

处理机调度2
处理机调度4
处理机调度3