处理器与寄存器

corresponding slide-ch2.1

处理器部件的简单示意

用户程序可见寄存器

  • 可以使程序员减少访问主存储器的次数，提高指令执行的效率
  • 所有程序可使用，包括应用程序和系统程序
    • 数据寄存器：又称通用寄存器
    • 地址寄存器：索引、栈指针、段地址等寄存器

控制与状态寄存器

  • 用于控制处理器的操作；主要被具有特权的操作系统程序使用，以控制程序的执行
  • 程序计数器PC：存储将取指令的地址
  • 指令寄存器IR：存储最近使用的指令
  • 条件码CC：CPU为指令操作结果设置的位，标志正/负/零/溢出等结果
  • 标志位：中断位、中断允许位、中断屏蔽位、处理器模式位、内存保护位、……，等等

程序状态字PSW

  • PSW既是操作系统的概念，指记录当前程序运行的动态信息，通常包含：
    • 程序计数器，指令寄存器，条件码
    • 中断字，中断允许/禁止，中断屏蔽，处理器模式，内存保护、调试控制
  • PSW也是计算机系统的寄存器
    • 通常设置一组控制与状态寄存器
    • 也可以专设一个PSW寄存器

指令与处理器模式

corresponding slide-ch2.2

机器指令

  • 机器指令是计算机系统执行的基本命令，是中央处理器执行的基本单位
  • 指令由一个或多个字节组成，包括操作码字段、一个或多个操作数地址字段、以及一些表征机器状态的状态字以及特征码
  • 指令完成各种算术逻辑运算、数据传输、控制流跳转

指令执行过程

  • CPU根据PC取出指令，放入IR，并对指令译码，然后发出各种控制命令，执行微操作系列，从而完成一条指令的执行
  • 一种指令执行步骤如下：
    • 取指：根据PC从存储器或高速缓冲存储器中取指令到IR
    • 解码：解译IR中的指令来决定其执行行为
    • 执行：连接到CPU部件，执行运算，产生结果并写回，同时在CC里设置运算结论标志；跳转指令操作PC，其他指令递增PC值

指令执行周期与指令流水线

  • 指令执行周期
  • 指令流水线

特权指令与非特权指令

  • 用户程序并非能够使用全部机器指令，那些与计算机核心资源相关的特殊指令会被保护
    • 如：启动I/O指令、置PC指令、等等
    • 核心资源相关的指令只能被操作系统程序使用
  • 特权指令：只能被操作系统内核使用的指令
  • 非特权指令：能够被所有程序使用的指令

处理器模式

  • 计算机通过设置处理器模式实现特权指令管理
  • 计算机一般设置0、1、2、3等四种运行模式，建议分别对应：0操作系统内核、1系统调用、 2共享库程序、3用户程序等保护级别
  • 0模式可以执行全部指令；3模式只能执行非特权指令；其他每种运行模式可以规定执行的指令子集
  • 一般来说，现代操作系统只使用0和3两种模式，对应于内核模式和用户模式

处理器模式的切换

  • 简称模式切换，包括“用户模式→内核模式”和“内核模式→用户模式”的转换
  • 中断、异常或系统异常等事件导致用户程序向OS内核切换，触发：用户模式→内核模式
    • 程序请求操作系统服务
    • 程序运行时发生异常
    • 程序运行时发生并响应中断
  • OS内核处理完成后，调用中断返回指令（如Intel的iret）触发：内核模式→用户模式

中断

corresponding slide-2.3

中断的概念

  • 中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程
  • 操作系统是“中断驱动”的；换言之，中断是激活操作系统的唯一方式
  • 中断有广义和狭义之分，上述中断是指广义的中断

中断、异常与系统异常

  • 狭义的中断指来源于处理器之外的中断事件，即与当前运行指令无关的中断事件，如I/O中断、时钟中断、外部信号中断等
  • 异常指当前运行指令引起的中断事件，如地址异常、算术异常、处理器硬件故障等
  • 系统异常指执行陷入指令而触发系统调用引起的中断事件，如请求设备、请求I/O、创建进程等

中断源

corresponding slide-ch2.4

处理器硬件故障中断事件

  • 由处理器、内存储器、总线等硬件故障引起
  • 处理原则为：保护现场，停止设备，停止CPU，向操作员报告，等待人工干预

程序性中断事件

  • 处理器执行机器指令引起
    • 除数为零、操作数溢出等算术异常：简单处理，报告用户；也可以由用户编写中断续元程序处理
    • 非法指令、用户态使用特权指令、地址越界、非法存取等指令异常：终止进程
    • 终止进程指令：终止进程
    • 虚拟地址异常：调整内存后重新执行指令

自愿性中断事件

  • 处理器执行陷入指令请求OS服务引起；在操作系统中，它一般又被称作系统调用
    • 请求分配外设、请求I/O、等等
    • 处理流程是：陷入OS，保护现场，根据功能号查入口地址，跳转具体处理程序

I/O中断事件

  • 来源于外围设备报告I/O状态的中断事件
    • I/O完成：调整进程状态，释放等待进程
    • I/O出错：等待人工干预
    • I/O异常：等待人工干预

外部中断事件

  • 由外围设备发出的信号引起的中断事件
    • 时钟中断、间隔时钟中断：记时与时间片处理
    • 设备报到与结束中断：调整设备表
    • 键盘/鼠标信号中断：根据信号作出相应反应
    • 关机/重启动中断：写回文件，停止设备与CPU

中断系统

corresponding slides-ch2.5

中断系统

  • 中断系统是计算机系统中响应和处理中断的系统，包括硬件子系统和软件子系统两部分
  • 中断响应由硬件子系统完成
  • 中断处理由软件子系统完成

中断响应处理与指令执行周期

  • 在指令执行周期最后增加一个微操作，以响应中断

中断装置

  • 计算机系统中发现并响应中断/异常的硬件装置称为中断装置
  • 由于中断源的多样性，硬件实现的中断装置有多种，分别处理不同类型的中断
  • 这些中断装置因计算机而异，通常有：
    • 处理器外的中断：由中断控制器发现和响应
    • 处理器内的异常：由指令的控制逻辑和实现线路发现和响应，相应机制称为陷阱
    • 请求OS服务的系统异常：处理器执行陷入指令时直接触发，相应机制称为系统陷阱

中断控制器

  • 中断控制器：CPU中的一个控制部件，包括中断控制逻辑线路和中断寄存器
  • 外部设备向其发出中断请求IRQ，在中断寄存器中设置已发生的中断
  • 指令处理结束前，会检查中断寄存器，若有不被屏蔽的中断产生，则改变处理器内操作的顺序，引出操作系统中的中断处理程序

陷阱与系统陷阱

  • 陷阱与系统陷阱：指令的逻辑和实现线路的一部分
    • 执行指令出现异常后，会根据异常情况转向操作系统的异常处理程序
    • 出现虚拟地址异常后，需要重新执行指令，往往越过陷阱独立设置页面异常处理程序
    • 执行陷入指令后，越过陷阱处理，触发系统陷阱，激活系统调用处理程序

中断响应过程

  • 发现中断源，提出中断请求
    • 发现中断寄存器中记录的中断
    • 决定这些中断是否应该屏蔽
    • 当有多个要响应的中断源时，根据规定的优先级选择一个
  • 中断当前程序的执行
    • 保存当前程序的PSW/PC到核心栈
  • 转向操作系统的中断处理程序

中断的处理

  • 中断处理程序
    • 操作系统处理中断事件的控制程序, 主要任务是处理中断事件和恢复正常操作
  • 中断处理过程
    • 保护未被硬件保护的处理器状态
    • 通过分析被中断进程的PSW中断码字段，识别中断源
    • 分别处理发生的中断事件
    • 恢复正常操作

恢复正常操作

  • 情况一：对于某些中断，在处理完毕后，直接返回刚刚被中断的进程
  • 情况二：对于其他一些中断，需要中断当前进程的运行，调整进程队列，启动进程调度， 选择下一个执行的进程并恢复其执行

中断系统处理流程

多中断的响应与处理

corresponding slides-ch2.7

中断屏蔽

  • 当计算机检测到中断时, 中断装置通过中断屏蔽位决定是否响应已发生的中断
  • 有选择的响应中断

中断优先级

  • 当计算机同时检测到多个中断时, 中断装置响应中断的顺序
  • 有优先度的响应中断
  • 一种可能的处理次序： 处理机硬件故障中断事件、自愿性中断事件、程序性中断事件、时钟中断等外部中断事件、输入输出中断事件、重启动和关机中断事件
  • 不同类型的操作系统有不同的中断优先级

中断的嵌套处理

  • 当计算机响应中断后，在中断处理过程中，可以再响应其他中断
  • 操作系统是性能攸关程序系统，且中断响应处理有硬件要求，考虑系统效率和实现代价问题，中断的嵌套处理应限制在一定层数内，如3层
  • 中断的嵌套处理改变中断处理次序，先响应的有可能后处理

多中断的响应与处理

  • 决定中断处理次序的因素
    • 中断屏蔽可以使中断装置不响应某些中断
    • 中断优先级决定了中断装置响应中断的次序
    • 中断可以嵌套处理, 但嵌套的层数应有限制
    • 中断的嵌套处理改变了中断处理的次序

多重中断处理

顺序中断处理

  • X、Y两个中断同时发生
  • 先响应X
  • 因Y被屏蔽，继续处理X
  • 再响应并处理Y

嵌套中断处理

  • X、Y两个中断同时发生
  • 根据中断优先级，先响应X
  • 因未屏蔽Y，再响应并处理Y
  • Y处理完成后，再处理X

进程及其状态

corresponding slides-ch2.8

进程的提出

  • 操作系统必须全方位地管理计算机系统中运行的程序
  • 因此，操作系统为正在运行程序建立一个管理实体——进程

进程的概念

  • 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动
  • 进程是操作系统进行资源分配和调度的一个独立单位
  • 一个进程包括五个实体部分，分别是：
    • (OS管理运行程序的)数据结构P
    • (运行程序的)内存代码C
    • (运行程序的)内存数据D
    • (运行程序的)通用寄存器信息R
    • (OS控制程序执行的)程序状态字信息PSW

进程举例

  • 不同程序在不同数据集上运行：构成两个无关进程
  • 不同程序再相同数据集上运行：构成两个共享数据的交往进程
  • 相同代码在不同数据集上运行：构成两个共享代码的无关进程
  • 共享的代码称为可再入程序，如编辑器
  • 可再入程序是纯代码的

进程举例

  • 前述的程序与数据集均是内存级的
  • 那么，在不同时段中针对(同一个外存数据文件)运行(同一个外存程序文件)，意味着完全不同的（P, C, D, R, Psw）
  • 所以两次运行构成两个不同的进程

概念级的进程状态

  • 运行态指进程占有处理器运行
  • 就绪态指进程具备运行条件等待处理器运行
  • 等待态指进程由于等待资源、输入输出、信号等而不具备运行条件

进程三态模型


(1)运行态→等待态：等待资源、I/O、信号
(2)等待态→就绪态：资源满足、I/O结束、信号完成
(3)就绪态→运行态：处理器空闲时选择更高优先权进程抢占
(4)运行态→就绪态：运行时间片到、有更高优先权进程

进程挂起的概念

  • OS无法预期进程的数目与资源需求，计算机系统在运行过程中可能出现资源不足的情况
  • 运行资源不足表现为性能低和死锁两种情况
  • 解决办法：剥夺某些进程的内存及其他资源，调入OS管理的对换区，不参加进程调度，待适当时候再调入内存、恢复资源、参与运行
  • 这就是进程挂起
  • 挂起态与等待态有着本质区别，后者占有已申请到的资源处于等待，前者没有任何资源

进程挂起的选择与恢复

  • 一般选择等待态进程进入挂起等待态
  • 也可选择就绪态进程进入挂起就绪态
  • 运行态进程还可以挂起自己
  • 等待事件结束后，挂起等待态进入挂起就绪态
  • 一般选择挂起就绪态进程予以恢复

进程的数据描述

corresponding slides-ch2.9

进程控制块(Process Control Block)

  • 进程控制块PCB是OS用于记录和刻画进程状态及环境信息的数据结构
  • 借助PCB，OS可以全面管理进程的物理实体，刻画进程的执行现状，控制进程的执行

标识信息

  • 用于存放唯一标识该进程的信息
    • 系统分配的标识号
    • 系统分配的进程组标识号
    • 用户定义的进程名
    • 用户定义的进程组名

现场信息

  • 用于存放该进程运行时的处理器现场信息
    • 用户可见寄存器内容：数据寄存器、地址寄存器
    • 控制与状态寄存器内容：PC、IR、PSW
    • 栈指针内容：核心栈与用户栈指针

控制信息

用于存放与管理、调度进程相关的信息

  • 调度相关信息：状态、等待事件/原因、优先级
  • 进程组成信息：代码/数据地址、外存映像地址
  • 队列指引元：进程队列指针、父子兄弟进程指针
  • 通信相关信息：消息队列、信号量、锁
  • 进程特权信息：如内存访问权限、处理器特权
  • 处理器使用信息：占用的处理器、时间片、处理器使用时间/已执行总时间、记账信息
  • 资源清单信息：如正占有的资源、已使用的资源

进程映像(Process Image)

  • 某一时刻进程的内容及其执行状态集合：
    • 进程控制块: 保存进程的标识信息、状态信息和控制信息
    • 进程程序块: 进程执行的程序空间
    • 进程数据块: 进程处理的数据空间，包括数据、处理函数的用户栈和可修改的程序
    • 核心栈: 进程在内核模式下运行时使用的堆栈，中断或系统过程使用
  • 进程映像是内存级的物理实体，又称为进程的内存映像

进程的内存映像示意图

进程上下文(Process context)

  • 进程的执行需要环境支持，包括CPU现场和Cache中的执行信息
  • OS中的进程物理实体和支持进程运行的环境合成进程上下文，包括以下：
    • 用户级上下文：用户程序块/用户数据区/ 用户栈/用户共享内存
    • 寄存器上下文：PSW/栈指针/通用寄存器
    • 系统级上下文：PCB/内存区表/核心栈
  • 进程上下文刻画了进程的执行情况

进程的管理

corresponding slides-ch2.10

概念级的OS进程管理软件

  • 关键的进程管理软件包括：
    • 系统调用/中断/异常处理程序
    • 队列管理模块
    • 进程控制程序
    • 进程调度程序（独立进程居多）
    • 进程通信程序（多个程序包）
    • 终端登录与作业控制程序、性能监控程序、审计程序等外围程序

进程实现的队列模型

队列管理模块

  • 队列管理模块是操作系统实现进程管理的核心模块
  • 操作系统建立多个进程队列，包括就绪队列和等待队列
  • 按需组织为先进先出队列与优先队列
  • 队列中的进程可以通过PCB中的队列指引元采用单/双指引元或索引连接
  • 出队和入队操作
  • 进程与资源调度围绕进程队列展开

进程的控制与管理(原语-Primitive)

  • 进程创建：进程表加一项，申请PCB并初始化，生成标识，建立映像，分配资源，移入就绪队列
  • 进程撤销：从队列中移除，归还资源，撤销标识，回收PCB，移除进程表项
  • 进程阻塞：保存现场信息，修改PCB，移入等待队列，调度其他进程执行
  • 进程唤醒：等待队列中移出，修改PCB，移入就绪队列（该进程优先级高于运行进程触发抢占）
  • 进程挂起：修改状态并出入相关队列，收回内存等资源送至对换区
  • 进程激活：分配内存，修改状态并出入相关队列
  • 其他：如修改进程特权

原语与进程控制原语

  • 进程控制过程中涉及对OS核心数据结构(进程表/PCB池/队列/资源表)的修改
  • 为防止与时间有关的错误，应使用原语
  • 原语是由若干条指令构成的完成某种特定功能的程序，执行上具有不可分割性
  • 原语的执行可以通过关中断实现
  • 进程控制使用的原语称为进程控制原语
  • 另一类常用原语是进程通信原语

进程切换

  • 进程切换指从正在运行的进程中收回处理器，让待运行进程来占有处理器运行
  • 进程切换实质上就是被中断运行进程与待运行进程的上下文切换，处理过程是：
    • 保存被中断进程的上下文
    • 转向进程调度
    • 恢复待运行进程的上下文

模式切换

  • 进程切换必须在操作系统内核模式下完成，这就需要模式切换
  • 模式切换又称处理器状态切换，包括：
    • 用户模式到内核模式
      • 由中断/异常/系统调用中断用户进程执行而触发
    • 内核模式到用户模式
      • OS执行中断返回指令将控制权交还用户进程而触发

模式切换的基本工作任务

  • 中断装置完成正向模式切换，包括：
    • 处理器模式转为内核模式
    • 保存当前进程的PC/PSW值到核心栈
    • 转向中断/异常/系统调用处理程序
  • 中断返回指令完成逆向模式转换，包括：
    • 从待运行进程核心栈中弹出PSW/PC值
    • 处理器模式转为用户模式

进程切换的细节

进程切换的工作过程

  1. (中断/异常等触发)正向模式切换并压入PSW/PC
  2. 保存被中断进程的现场信息
  3. 处理具体中断/异常
  4. 把被中断进程的系统堆栈指针SP值保存到PCB
  5. 调整被中断进程的PCB信息，如进程状态
  6. 把被中断进程的PCB加入相关队列
  7. 选择下一个占用CPU运行的进程
  8. 修改被选中进程的PCB信息，如进程状态
  9. 设置被选中进程的地址空间，恢复存储管理信息
  10. 恢复被选中进程的SP值到处理器寄存器SP
  11. 恢复被选中进程的现场信息进入处理器
  12. (中断返回指令触发)逆向模式转换并弹出PSW/PC

进程切换的发生时机

  • 进程切换一定发生在中断/异常/系统调用处理过程中，常见的情况是：
  • 阻塞式系统调用、虚拟地址异常，导致被中断进程进入等待态
  • 时间片中断、I/O中断后发现更高优先级进程，导致被中断进程转入就绪态
  • 终止用系统调用、不能继续执行的异常，导致被中断进程进入终止态

进程切换与模式切换

  • 一些中断/异常不会引起进程状态转换，不会引起进程切换，只是在处理完成后把控制权交回给被中断进程，处理流程是：
    • (中断/异常触发)正向模式切换压入PSW/PC
    • 保存被中断进程的现场信息
    • 处理中断/异常
    • 恢复被中断进程的现场信息
    • (中断返回指令触发)逆向模式转换弹出PSW/PC

多线程技术概述

correspoonding slides-ch2.12

单线程结构进程

  • 传统进程是单线程结构进程

单线程结构进程的问题

  • 单线程结构进程在并发程序设计上存在的问题
    • 进程切换开销大
    • 进程通信开销大
    • 限制了进程并发的粒度
    • 降低了并行计算的效率

解决问题的思路

  • 把进程的两项功能，即“独立分配资源”与 “被调度分派执行”分离开来
  • 进程作为系统资源分配和保护的独立单位，不需要频繁地切换
  • 线程作为系统调度和分派的基本单位，能轻装运行，会被频繁地调度和切换
  • 线程的出现会减少进程并发执行所付出的时空开销，使得并发粒度更细、并发性更好

多线程结构进程

多线程环境下进程的概念

  • 在多线程环境中，进程是操作系统中进行保护和资源分配的独立单位。具有:
    • 用来容纳进程映像的虚拟地址空间
    • 对进程、文件和设备的存取保护机制

多线程环境下线程的概念

  • 线程是进程的一条执行路径，是调度的基本单位，同一个进程中的所有线程共享进程获得的主存空间和资源。它具有：
    • 线程执行状态
    • 受保护的线程上下文，当线程不运行时，用于存储现场信息
    • 独立的程序指令计数器
    • 执行堆栈
    • 容纳局部变量的静态存储器

多线程环境下线程的状态与调度

  • 线程状态有运行、就绪和睡眠，无挂起
  • 与线程状态变化有关的线程操作有：
    • 孵化、封锁、活化、剥夺、指派、结束
  • OS感知线程环境下：
    • 处理器调度对象是线程
    • 进程没有三状态（或者说只有挂起状态）
  • OS不感知线程环境下：
    • 处理器调度对象仍是进程
    • 用户空间中的用户调度程序调度线程

并发多线程程序设计的优点

  • 快速线程切换
  • 减少（系统）管理开销
  • （线程）通信易于实现
  • 并行程度提高
  • 节省内存空间

多线程技术的应用

  • 前台和后台工作
  • C/S应用模式
  • 加快执行速度
  • 设计用户接口

多线程技术

corresponding slides-ch2.13

内核级线程KLT, Kernel-Level Threads

  • 线程管理的所有工作由OS内核来做
  • OS提供了一个应用程序设计接口API，供开发者使用KLT
  • OS直接调度KLT

内核级线程的特点

  • 进程中的一个线程被阻塞了，内核能调度同一进程的其它线程占有处理器运行
  • 多处理器环境中，内核能同时调度同一进程中多个线程并行执行
  • 内核自身也可用多线程技术实现，能提高操作系统的执行速度和效率
  • 应用程序线程在用户态运行，线程调度和管理在内核实现，在同一进程中，控制权从一个线程传送到另一个线程时需要模式切换，系统开销较大

用户级线程ULT, User-Level Threads

  • 用户空间运行的线程库， 提供多线程应用程序的开发和运行支撑环境
  • 任何应用程序均需通过线程库进行程序设计，再与线程库连接后运行
  • 线程管理的所有工作都由应用程序完成，内核没有意识到线程的存在

用户级线程的特点

  • 所有线程管理数据结构均在进程的用户空间中，线程切换不需要内核模式，能节省模式切换开销和内核的宝贵资源
  • 允许进程按应用特定需要选择调度算法，甚至根据应用需求裁剪调度算法
  • 能运行在任何OS上，内核在支持ULT方面不需要做任何工作
  • 不能利用多处理器的优点，OS调度进程，仅有一个ULT能执行
  • 一个ULT的阻塞，将引起整个进程的阻塞

Jacketing技术

  • 把阻塞式系统调用改造成非阻塞式的
  • 当线程陷入系统调用时，执行jacketing程序
  • 由jacketing程序来检查资源使用情况，以决定是否执行进程切换或传递控制 权给另一个线程

用户级线程 vs. 内核级线程

  • ULT适用于解决逻辑并行性问题
  • KLT适用于解决物理并行性问题

多线程实现的混合式策略

  • 线程创建是完全在用户空间做的
  • 单应用的多个ULT可以映射成一些KLT，通过调整KLT数目，可以达到较好的并行效果

多线程实现混合式策略的特点

  • 组合用户级线程/内核级线程设施
  • 线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行
  • 一个应用中的多个用户级线程被映射到一些(小于等于用户级线程数目)内核级线程上
  • 程序员可以针对特定应用和机器调节内核级线程的数目，以达到整体最佳结果
  • 该方法将会结合纯粹用户级线程方法和内核级线程方法的优点，同时减少它们的缺点

线程混合式策略下的线程状态

  • KLT三态，系统调度负责
  • ULT三态，用户调度负责
  • 活跃态ULT代表绑定KLT的三态
  • 活跃态ULT运行时可激活用户调度
  • 非阻塞系统调用可使用Jacketing启动用户调度，调整活跃态ULT

多线程实现的各种策略总结

处理器调度

corresponding slides-ch2.15

处理器调度的层次

  • 高级调度：又称长程调度，作业调度
    • 决定能否加入到执行的进程池中
  • 中级调度，又称平衡负载调度
    • 决定主存中的可用进程集合
  • 低级调度：又称短程调度，进程调度
    • 决定哪个可用进程占用处理器执行

处理器调度层次与进程状态转换

处理器调度层次与关键状态转换

高级调度

  • 分时OS中，高级调度决定：
    • 是否接受一个终端用户的连接
    • 命令能否被系统接纳并构成进程
    • 新建态进程是否加入就绪进程队列
  • 批处理OS中，高级调度又称为作业调度，功能是按照某种原则从后备作业队列中选取作业进入主存，并为作业做好运行前的准备工作和完成后的善后工作

中级调度

  • 引进中级调度是为了提高内存利用率和作业吞吐量
  • 中级调度决定那些进程被允许驻留在主存中参与竞争处理器及其他资源，起到 短期调整系统负荷的作用
  • 中级调度把一些进程换出主存，从而使之进入“挂起”状态，不参与进程调度，以平顺系统的负载

低级调度

  • 低级调度：又称处理器调度、进程调度、短程调度，按照某种原则把处理器分配给就绪态进程或内核级线程
  • 进程调度程序：又称分派程序，操作系统中实现处理器调度的程序，是操作系 统的最核心部分
  • 处理器调度策略的优劣直接影响到整个系统的性能

低级调度的主要功能

  • 记住进程或内核级线程的状态
  • 决定某个进程或内核级线程什么时候获得处理器，以及占用多长时间
  • 把处理器分配给进程或内核级线程
  • 收回处理器

处理器调度算法

corresponding slides-ch2.16

选择处理器调度算法的原则

  • 资源利用率：使得CPU或其他资源的使用率尽可能高且能够并行工作
  • 响应时间：使交互式用户的响应时间尽可能小，或尽快处理实时任务
  • 周转时间：提交给系统开始到执行完成获得结果为止的这段时间间隔称周转时间，应该使周转时间或平均周转时间尽可能短
  • 吞吐量：单位时间处理的进程数尽可能多
  • 公平性：确保每个用户每个进程获得合理的CPU份额或其他资源份额

优先数调度算法

  • 根据分配给进程的优先数决定运行进程
    • 抢占式优先数调度算法
    • 非抢占式优先数调度算法
  • 优先数的确定准则
    • 进程负担任务的紧迫程度
    • 进程的交互性
    • 进程使用外设的频度
    • 进程进入系统的时间长短

与进入系统时间相关的优先数

  • 计算时间短(作业/进程)优先
  • 剩余计算时间短进程优先
  • 响应比高者(作业/进程)优先
  • 先来先服务：先进队先被选择
  • 多用于高级调度；低级调度中，以计算为主的进程过于优越

时间片轮转调度算法

  • 根据各个进程进入就绪队列的时间先后轮流占有CPU一个时间片
  • 时间片中断
  • 时间片长度的确定：选择长短合适的时间片, 过长则退化为先来先服务算法, 过短则调度开销大
  • 单时间片，多时间片和动态时间片

分级调度算法

  • 又称多队列策略，反馈循环队列
  • 基本思想
    • 建立多个不同优先级的就绪进程队列
    • 多个就绪进程队列间按照优先数调度
    • 高优先级就绪进程，分配的时间片短
    • 单个就绪进程队列中进程的优先数和 时间片相同

例子

分级原则

  • 一般分级原则
    • 外设访问，交互性，时间紧迫程度，系统效率，用户立场，…
  • 现代操作系统的实现模型
    • 多个高优先级的实时进程队列，如：硬实时、网络、软实时
    • 多个分时任务的进程队列，根据基准优先数和执行行为调整
    • 队列数可能多达32-128个

彩票调度算法

  • 基本思想：为进程发放针对系统各种资源（如CPU时间）的彩票；当调度程序需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源
  • 合作进程之间的彩票交换