操作系统原理

计算机系统

Week 2

操作系统运行环境与运行机制(重点)

• 操作系统运行环境
  • CPU状态
  • 中断/异常机制
• 操作系统运行机制
  • 系统调用

---

处理器状态（模式）

• CPU是由运算器、构成器、一系列的寄存器以及高速缓存构成
• 两类寄存器：
  1. 用户可见寄存器：高级语言编译器通过优化算法分配并使用之，以减少程序访问内存次数。
  2. 控制和状态寄存器：用于控制处理器的操作通常由操作系统代码使用
• 控制和状态寄存器：
  1. 用于控制处理器的操作
  2. 在某种特权级别下可以访问、修改
  3. 常见的控制和状态寄存器：
     1. 程序计数器（PC：Program Counter），记录将要取出的指令的地址
     2. 指令寄存器（IR：Instruction Register）,记录最近取出的指令
     3. 程序状态字（PSW：Program Status Word），记录处理器的运行状态如条件码、模式、控制位等信息
• 操作系统的需求–保护
  1. 从操作系统的特征考虑：并发、共享
  2. 从操作系统角度对硬件提出要求：实现保护与控制
• 操作系统为多个程序的执行提供了并发的环境，多个进程共享操作系统。
• 保护：用户程序与用户程序之间不受干扰，用户程序不会干扰操作系统。
• 需要硬件提供基本运行机制：
  1. 处理器具有特权级别，能在不同的特权级下可以运行不同的指令集合。
  2. 硬件保护机制可将OS与用户程序隔离。
• 处理器的状态（模式MODE）
  1. 现代处理器通常将CPU状态设计划分为两种、三种或四种
  2. 在程序状态字寄存器PSW中专门设置一位，根据运行程序对资源和指令的使用权限而设置不同的CPU状态。例如：X86架构中的EFLAGS寄存器 硬件提供的各种不同的CPU状态

• 特权指令和非特权指令

  1. 操作系统需要两种CPU状态：内核态（运行操作系统程序）、用户态（运行用户程序）
  2. 特权指令：只能由操作系统使用、用户程序不能使用的指令
  3. 非特权指令：用户程序可以使用的指令
     特权指令：启动I/O、内存清零、修改程序状态字、设置时钟、允许/禁止中断、停机
     非特权指令：控制转移、算数运算、取数指令、访管指令（使用户程序从用户态转为内核态）

     实例：X86系列处理器
         X86支持4个处理器特权级别
         特权环：R0、R1、R2和R3
         从R0到R3，特权能力由高到低
         R0相当于内核态；R3相当于用户态；R1和R2则介于两者之间
         不同特权级别能够运行的指令集合不同
         目前大多数基于x86处理器的操作系统只用了R0和R3两个特权级别

• CPU状态之间的转换
  用户态 -> 内核态 唯一途径 -> 中断/异常/陷入机制 interrupt exception
  内核态 -> 用户态 设置程序状态字PSW
  一条特殊的指令：陷入指令（又称访管指令,因为内核态又称supervisor mode），提供给用户程序的接口，用于调用操作系统的功能（服务）。例如：int, trap, syscall, sysenter/sysexit

  中断与异常机制介绍（处理器驱动力）

• 中断/异常机制
  • 中断/异常 对于操作系统的重要性就好比：汽车的发动机、飞机的引擎。
    可以说 操作系统是由“中断驱动”或者“事件驱动”的。
• 主要作用：
  • 及时处理设别发来的中断请求
  • 可使OS捕获用户程序提出的服务请求
  • 防止用户程序执行过程中的破坏性活动
• 中断/异常的概念
  • CPU对系统发生的某个事件作出的一种反应。事件的发生改变了处理器的控制流（硬件完成这一过程）。
  • CPU暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，处理完成后返回断点继续执行被打断的程序。
    特点：是随机发生的。是自动处理的。是可恢复的。
• 为什么引用中断与异常
  • 中断的引用：为了支持CPU和设备之间的并行操作
    当CPU启动设别进行输入/输出后，设备便可以独立公作，CPU转去处理与此次输入/输出不相关的事情；当设备完成输入/输出后，通过向CPU发中断报告此次输入/输出的结果，让CPU决定如何处理以后的事情。
  • 异常的引用：表示CPU执行命令时本身出现的问题
    如计算溢出、清零、取数时的奇偶错，访问地址时越界或执行了“陷入指令”等，这时硬件改变了CPU当前的执行流程，转到相应的错误处理程序或异常处理程序或执行系统调用。
• 事件
  • 中断（外中断）：I/O中断、时钟中断、硬件故障
  • 异常（内中断）：系统调用、页故障/页错误、保护性异常（只读缺写，数组越界）、断点指令、其他程序性异常（算术溢出等）
    中断：外部事件，正在运行的程序所不期望的
    异常：由正在执行的指令引发
• 中断与异常小结

类别	原因	异步/同步	返回行为
中断Interrupt	来自I/O设备、其他硬件部件	异步	总是返回到下一条指令
陷入Trap	有意识安排的	同步	返回到下一条指令
故障Fault	可恢复的错误	同步	返回到当前指令
终止Abort	不可恢复的错误	同步	不会返回

中断与异常机制工作原理

硬件和软件相互配合使计算机系统得以充分发挥能力

硬件该做什么事？ -- 中断/异常响应
    捕获中断源发出的中断/异常请求，以一定方式响应，将处理器控制权交给特定的处理程序。
软件要做什么事？ -- 中断/异常处理程序
    识别中断/异常类型并完成相应的处理

• 中断响应：发现中断、接收中断的过程由中断硬件部件完成

处理器控制部件中设有中断寄存器

• 中断处理程序
  • 设计操作系统时，为每一类中断/异常事件编好相应的处理程序，并设置好中断向量表。
  • 系统运行时若响应中断，中断硬件部件将CPU控制权转给中断处理程序：
    • 保存相关寄存器信息
    • 分析中断/异常的具体原因
    • 执行对应的处理功能
    • 恢复现场，返回被事件打断的程序
• 中断与异常小结（1/2）
  以设备输入输出中断为例：
  • 打印机给CPU发中断信号
  • CPU处理完当前指令后检测到中断，判断出中断来源并向相关设备发确认信号
  • CPU开始为软件处理中断做准备
    • 处理器状态被切换到内核态
    • 在系统栈中保存被中断程序的重要上下文环境，主要是程序计数器PC、程序状态字PSW
  • CPU根据中断码查中断向量表，获得与该中断相关的处理程序的入口地址，并将PC设置成该地址，新的指令周期开始时，CPU控制转移到中断处理程序
  • 中断处理程序开始工作（软件）
    • 在系统栈中保存现场信息
    • 检查I/O设备的状态信息，操纵I/O设备或者在设备和内存之间传送数据等等
  • 中断处理结束时，CPU检测到中断返回指令，从系统栈中恢复被中断程序的上下文环境，CPU状态恢复成原来的状态，PSW和PC恢复成中断前的值，CPU开始一个新的指令周期。

系统调用机制

• 系统调用：用户在编程时可以调用的操作系统功能
• 系统调用作用：系统调用是操作系统提供给编程人员的唯一接口，使CPU状态从用户态陷入内核态
• 典型系统调用：每个操作系统都提供几百种系统调用（进程控制、进程通信、文件使用、目录操作、设备管理、信息维护等）
• 系统调用、库函数、API、内核函数
  
• 系统调用机制的设计
  
• 参数传递过程问题
  常见的3种实现方法：
  • 由陷入指令自带参数：陷入指令的长度有限，且还要携带系统调用功能号，只能自带有限的参数
  • 通过通用寄存器传递参数：这些寄存器是操作系统和用户程序都能访问的，但寄存器的个数会限制传递参数的数量（一般采用这个）
  • 在内存中开辟专用堆栈区来传递参数

Week 3

进程/线程模型

• 进程模型
  • 多道程序设计
  • 进程的概念、进程控制块
  • 进程状态及转换、进程队列
  • 进程控制
    进程创建、撤销、阻塞、唤醒……
• 线程模型
  • 为什么引用线程？
  • 线程的组成
  • 线程机制的实现
    用户级线程、核心级线程、混合方式

---

进程的基本概念

• 多道程序设计：允许多个程序==同时==进入内存并运行，其目的是为了提高系统效率。
• 并发环境与并发程序
  • 并发环境：一段时间间隔内，单处理器上有两个或两个以上的程序==同时==处于==开始运行但尚未结束的状态==，并且==次序不是事先确定的==。
  • 并发程序：在并发环境中执行的程序。
• 进程的定义：进程Process是具有独立功能的程序关于==某个数据集合上==的==一次运行活动==，是系统进行资源分配和==调度==的独立单位。又称任务（Task or Job）
  • 程序的一次执行过程
  • 是正在运行程序的抽象
  • 将一个CPU变幻成多个虚拟的CPU
  • 对CPU的抽象
  • 系统资源以进程为单位分配，如内存、文件……每个具有独立的地址空间
  • 操作系统将CPU调度给需要的进程
• 进程控制块PCB
  • PCB ： Process Control Block
    • 又称 进程描述符、进程属性
    • 操作系统用于管理控制进程的一个专门数据结构
    • 记录进程的各种属性，描述进程的动态变化过程
  • PCB是系统感知进程存在的唯一标志
    • 进程与PCB是一一对应的
  • 进程表：所有进程的PCB集合
    确定了 在一个操作系统中，最多支持多少个进程 那么有的时候我们会说，这就是操作系统的并发度 最多有多少个进程可以执行。
  • PCB包括4部分内容：
    • 进程描述信息：进程标识符（process ID），唯一，通常是一个整数；进程名：通常基于可执行文件名，不唯一；用户标识符（user ID）；进程组关系
    • 进程控制信息：当前状态；优先级（priority）；代码执行入口地址；程序的磁盘地址；运行统计信息（执行时间、页面调度）；进程间同步和通信；进程的队列指针；进程的消息队列指针
    • 所拥有的资源和使用情况：虚拟地址空间的状况；打开文件列表
    • CPU现场信息：寄存器值（通用寄存器，程序计数器PC，程序状态字PSW，栈指针）；指向该进程页表的指针；

进程状态及状态转换

• 进程的三种基本状态：运行态、就绪态、等待态
  • 运行态（running）占有CPU，并在CPU上运行
  • 就绪态（ready）已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
  • 等待态（Waiting/Blocked）因等待某一事件而暂时不能运行
• 进程的其他状态：创建态，终止态，挂起态
  • 创建态（New）已完成创建一进程所必要的工作，但尚未同意执行该进程
  • 终止态（Terminated）终止执行后，进程进入该状态，可完成一些数据统计工作，并回收资源
  • 挂起态：用于调节负载，其进程不占用内存空间，映像交换到磁盘上

• 进程队列：
  • 操作系统为每一类进程建立一个或多个队列；
  • 队列元素为PCB；
  • 伴随进程状态的改变，其PCB从一个队列进入另一个队列
  • 多个等待队列等待的事件不同；
  • 就绪队列也可以多个；
  • 单CPU情况下，运行队列中只有一个进程

进程控制、线程

原语：完成某种特定功能的一段程序，具有不可分割性或不可中断性。原语的执行必须是连续的，在执行过程中不允许被中断（原子操作）
进程控制操作完成进程各状态之间的转换，由具有特定功能的原语完成。（进程创建原语，进程撤销原语，阻塞原语，唤醒原语，挂起原语，激活原语，改变进程优先级…)

• 进程的创建
  • 给新进程分配一个唯一标识以及进程控制块；
  • 为进程分配地址空间；
  • 初始化进程控制块；
  • 设置相应的队列指针，如把新进程加到就绪队列链表中。
    Unix：fork/exec
    Windows: CreateProcess
• 进程的撤销
  • 收回进程所占有的资源
  • 关闭打开的文件、断开网络连接、回收分配的内存
  • 撤销该进程的PCB（意味着结束进程）；
    Unix：exit
    Windows：TerminateProcess
• 进程的阻塞
  处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其他进程发送消息，当被等待事件未发生时，由==进程自己执行阻塞原语==，使自己由运行态变为阻塞态。
  Unix:wait
  Windows:WaitForSingleObject
• Unix的几个进程控制操作
  • fork（） 通过复制调用进程来建立新的进程，是最基本的进程建立过程
  • exec（）包括一些列的系统调用，它们都是通过用一段新的程序代码覆盖原来的地址空间，实现进程执行代码的转换
  • wait（）供初级进程同步操作，能使一个进程等待另外一个进程结束
  • exit（）用来终止一个进程的运行
• Unix的FORK()实现：
  • 为子进程分配一个空闲的进程描述符（proc结构）；
  • 分配给子进程唯一标识pid；
  • ==以一次一页的方式复制父进程地址空间；==
  • 从父进程处继承共享资源，如打开的文件和当前工作目录等；
  • 将子进程的状态设为就绪，插入到就绪队列；
  • 对子进程返回标识符0；
  • 向父进程返回子进程的pid
    COW（Copy-On-Write）Linux采用写时拷贝技术，只有进程空间的各段内容要发生变化时，才会将父进程的内容复制一份给子进程
• 使用fork（）的示例代码：

  pid=fork();
  if(pid==0){
  printf("child");
  } else{
  printf("parent");
  }

进程的相关概念

• 进程分类
  • 系统进程，用户进程
  • 前台进程，后台进程
  • CPU密集型进程，I/O密集型进程
  • Unix进程家族树：init为根
  • Windows：地位相同
• 进程与程序的区别
  • 进程更能准确刻画并发，而程序不能
  • 程序是静态的，进程是动态的
  • 进程是有生命周期的，有诞生有消亡，是短暂的，而程序是相对长久的
  • 一个程序可对应多个进程
  • 进程可具有创建其他进程的功能
    操作系统为每个进程都分配了一个地址空间
• 进程映像:是对进程执行活动全过程的静态描述由进程地址空间内容、硬件寄存器内容及与该进程相关的内核数据结构、内核栈组成。
• 用户相关：进程地址空间（代码段、数据段、堆和栈、共享库）
  • 寄存器相关：程序计数器、指令寄存器、程序状态寄存器、栈指针、通用寄存器等的值。
  • 内核相关：
    • 静态部分：PCB及各种资源数据结构
    • 动态部分：内核栈（不同进程在进入内核后使用不同的内核栈）
• 上下文切换
  • 将CPU硬件状态从一个进程换到另一个进程的过程叫上下文切换
  • 进程运行时，其硬件状态保存在CPU上的寄存器中
    寄存器：程序计数器、程序状态寄存器、栈指针、通用寄存器、其他控制寄存器的值。
  • 进程不运行时，这些寄存器的值保存在进程控制块PCB中，当操作系统要运行一个新的进程时，将PCB中的相关值送到对应的寄存器中。

线程的引入

为什么需要线程：

• 应用的需要
• 开销的需要
• 性能的需要

---

应用的需要

• 典型的应用：Web服务器
  • 工作方式：
    • 从客户端接受网页请求（http协议）
    • 从磁盘上检索相关网页，读入内存
    • 将网页返回给对应的客户端
  • 如何提高服务器工作效率
    • 网页缓存(Web page cache)

构造服务器的三种方法：

• 多线程：有并发、阻塞系统调用
• 单线程进程：无并发、阻塞系统调用
• 有限状态机：有并发、非阻塞系统调用、中断

开销的需要

• 进程时间和空间开销大，限制了并发度的提高，而线程的开销小
• 创建一个新线程花费时间少；撤销一个新线程花费时间少；
• 两个线程切换花费时间少；
• 线程之间相互通信无需调用内核（同一进程内的线程共享内存和文件）

性能的需要

多个线程，有的计算，有的I/O

• 进程的两个基本属性：
  • 资源的拥有着（依然是进程）
  • CPU调度单位（线程继承了这一属性）

线程：进程中的一个运行实体，是CPU的调度单位，有时将线程称为轻量级进程

• 线程的属性：
  • 有标识符ID
  • 有状态及状态转换->需要提供一些操作
  • 不运行时需要保存的上下文（程序计数器等寄存器）
  • 有自己的栈和栈指针
  • ==共享所在进程的地址空间和其他资源==
  • 可以创建、撤销另一个进程（程序开始是以一个单线程进程方式运行的）

线程机制的实现

• 用户级线程
• 核心级线程
• 混合线程

---

用户级线程

• 优点：
  • 线程切换快
  • 调度算法是应用程序特定的
  • 用户级线程可运行在任何操作系统上（只需要实现线程库）
• 缺点：
  • 内核只将处理器分配给进程，同一进程中的两个线程不能同时运行在两个处理器上
  • 大多数系统调用是阻塞的，因此由于内核阻塞进程，故进程中所有线程也被阻塞

核心级线程

混合模型

本章重点小结

• 进程
  • 并发性：任何进程都可以与其他进程一起向前推进
  • 动态性：进程是正在执行程序的实例
    • 进程是动态产生，动态消亡的
    • 进程在其生命周期内，在三种基本状态之间转换
  • 独立性：进程是资源分配的一个独立单位
    例如：各进程的地址空间相互独立
  • 交互性：指进程在执行过程中可能与其他进程产生直接或间接的关系
  • 异步性：每个进程都以其相对独立的、不可预知的速度向前推进
  • 进程映像：程序 + 数据 + 栈（用户栈、内核栈）+ PCB
• 线程
  • 多线程应用场景
  • 线程基本概念、属性
  • 线程实现机制

可再入程序（可重入）：可被多个进程同时调用的程序，具有下列性质：
它是纯代码的，即在执行过程中自身不改变；调用它的进程应该提供数据区。

Week 4

处理器调度的相关概念

• CPU调度的基本概念
• 设计调度算法时要考虑的几个要点
• 批处理系统的调度算法
• 交互式系统的调度算法
• Windows操作系统的线程调度算法
• 其他

---

CPU调度

• CPU调度——其任务是控制、协调进程对CPU的竞争。

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

• 系统场景
  • N个进程就绪、等待上CPU运行
  • M个CPU，M>=1
  • 需要决策：给哪一个进程分配哪一个CPU？

CPU调度需要解决的三个问题

WHAT ：按什么原则选择下一个要执行的进程——调度算法

WHEN ：何时进行选择——调度时机

HOW ：如何让被选中的进程上CPU运行——调度过程（进程的上下文切换）

CPU调度的时机

事件发生 -> 当前运行的进程暂停运行 -> 硬件机制响应后 -> 进入操作系统，处理相应的事件 -> 结束处理后 -> 就绪队列改变了-> 需要进程调度根据预设的调度算法，从就绪队列中选一个进程

某些进程的状态会发生变化，也可能又创建了一些新的进程

典型的事件举例

• 创建、唤醒、退出等进程控制操作
• 进程等待I/O、I/O中断
• 时钟中断，如：时间片用完、定时器到时
• 进程执行过程中出现abort异常

时机总结

• 进程终止（正常或发生错误）
• 新进程创建（变为就绪态）
• 等待进程变成就绪
• 运行进程变成就绪
• 运行进程变成阻塞

内核对中断/异常/系统调用处理后返回到用户态时

调度过程（进程切换）

进程调度程序从就绪队列选择了要运行的进程：这个进程可以是刚刚被暂停执行的进程，也可能是另一个新的进程
进程切换：是让一个进程让出处理器，让另一个进程占用处理器，包括对原来进程各种状态的保存和对新进程各种状态的恢复

• 进程切换主要包括两部分工作：
  • 切换全局页目录以加载一个新的地址空间
  • 切换内核栈和硬件上下文，其中硬件上下文包括了内核执行新进程需要的全部信息，如CPU相关寄存器

    切换过程包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复

• 上下文切换具体步骤：
  场景：进程A下CPU，进程B上CPU
  • 保存进程A的上下文环境（程序计数器、程序状态字、其他寄存器）
  • 更新A的PCB（新状态和其他信息）
  • 把进程A移至合适队列（就绪，阻塞，···）
  • 把进程B的状态设置为运行态
  • 从进程B的PCB中恢复上下文（程序计数器、程序状态字、其他寄存器）
• 上下文切换的开销：
  • 保存和恢复寄存器
  • 切换地址空间（相关指令可能比较昂贵）
  • 缓存和缓冲失效（高速缓存、缓冲区缓存、TLB）

调度算法的设计

算法衡量指标：

• 吞吐量（Throughput）：单位时间完成的进程数目
• 周转时间（Turnaround Time, TT）：进程从提出请求到运行完成的时间
• 响应时间（Response Time，RT）：从提出请求到第一次回应的时间
• CPU利用率（CPU Utilization）：CPU做有效工作的时间比例
• 等待时间（Waiting Time）：进程在就绪队列中等待的时间

相关概念：

• 进程优先级
• 抢占式（Preemptive）与不可抢占式（Non-preemptive）
• I/O密集型（I/O bound）与CPU密集型（CPU bound）
• 时间片（Time slice， Quantum）

批处理系统中采用的调度算法

考虑：吞吐量、周转时间、CPU利用率、公平、平衡

• 先来先服务（FCFS）
• 短作业优先（SJF）
• 最短剩余时间优先（SRTN）
• 最高响应比优先（HRRN）

---

• 先来先服务
  • First Come First Serve
  • 先进先出 First In First Out （FIFO）
  • 按照进程就绪的先后顺序使用CPU
  • 非抢占
    优缺点：
  • 公平
  • 实现简单
  • 长进程后面的短进程需要等很长时间，不利于用户体验
• 短作业优先调度算法：
  • Shortest Job First
  • 具有最短完成时间的进程优先执行
  • 非抢占式
    优缺点：
  • 最短的平均周转时间：在所有进程同时可运行时，采用SJF调度算法可以得到最短的平均周转时间
  • 不公平：源源不断的短任务到来，可能使长的任务长时间得不到运行——>产生“饥饿”现象。
• 最短剩余时间优先（SRTN）
  • Shortest Remaining Time Next
  • SJF的抢占式版本，即当一个新就绪的进程比当前运行进程具有更短的完成时间时，系统抢占当前进程， 选择新就绪的进程执行
• 最高响应比优先HRRN
  • Highest Response Ratio Next
  • 是一个综合的算法
  • 调度时，首先计算每个进程的响应比R：之后总是选择R最高的进程执行

    响应比R = 周转时间/处理时间 = （周转时间 + 等待时间）/ 处理时间 = 1 + （等待时间/处理时间）

交互式系统调度算法

目标：响应时间

包含以下三种调度算法：

• 时间片轮转（RR）
• 最高优先级（HPF）
• 多级反馈队列（Multiple feedback queue）

---

（1）时间片轮转

• 将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
• 时间片轮转算法中选择合适的时间片很重要：
  • 如果太长，会降级为先来先服务算法，延长短进程的响应时间
  • 如果太短，进程切换会浪费CPU时间

（2）最高优先级

• Highest Priority First
• 选择优先级最高的进程投入运行
• 优先级可以是静态不变的，也可以是动态调整的
• 通常：
  • 系统进程优先级 高于 用户进程
  • 前台进程优先级 高于 后台进程
  • 操作系统更偏好 I/O型进程
• 就绪队列可以按照优先级组织
• 不公平
• 会导致优先级翻转问题（基于优先级的抢占式）

  优先级翻转是当一个高优先级任务通过信号量机制访问共享资源时，该信号量已被一低优先级任务占有，因此造成高优先级任务被许多具有较低优先级任务阻塞，实时性难以得到保证。

• 解决方案：1、设置优先级天花板；2、优先级继承 ；3、使用中断禁止

  例如：有优先级为A、B和C三个任务，优先级A>B>C，任务A，B处于挂起状态，等待某一事件发生，任务C正在运行，此时任务C开始使用某一共享资源S。在使用中，任务A等待事件到来，任务A转为就绪态，因为它比任务C优先级高，所以立即执行。当任务A要使用共享资源S时，由于其正在被任务C使用，因此任务A被挂起，任务C开始运行。如果此时任务B等待事件到来，则任务B转为就绪态。由于任务B优先级比任务C高，因此任务B开始运行，直到其运行完毕，任务C才开始运行。直到任务C释放共享资源S后，任务A才得以执行。在这种情况下，优先级发生了翻转，任务B先于任务A运行。

优先级天花板是当任务申请某资源时， 把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级， 这个优先级称为该资源的优先级天花板。这种方法简单易行， 不必进行复杂的判断， 不管任务是否阻塞了高优先级任务的运行， 只要任务访问共享资源都会提升任务的优先级。

优先级继承是当任务A 申请共享资源S 时， 如果S正在被任务C 使用，通过比较任务C 与自身的优先级，如发现任务C 的优先级小于自身的优先级， 则将任务C的优先级提升到自身的优先级， 任务C 释放资源S 后，再恢复任务C 的原优先级。这种方法只在占有资源的低优先级任务阻塞了高优先级任务时才动态的改变任务的优先级，如果过程较复杂， 则需要进行判断。

（3）多级反馈队列（Multiple feedback queue）（BSD 5.3）（综合调度算法）

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

调度算法	英文	占用CPU方式	吞吐量	响应时间	开销	对进程的影响	饥饿问题
先来先服务	FCFS	非抢占	不强调	当进程执行时间差别很大时，可能很慢	最小	对短进程不利，对I/O型进程不利	无
时间片轮转	Round Robin,RR	抢占（时间片用完）	若时间片小，吞吐量会很低	为短进程提供好的响应时间	最小	公平对待	无
短作业优先	SJF	非抢占	高	为短进程提供好的响应时间	可能较大	对长进程不利	可能
最短剩余时间优先	SRTN	抢占（到达时）	高	提供好的响应时间	可能较大	对长进程不利	可能
最高响应比优先	HRRN	非抢占	高	提供好的响应时间	可能较大	很好的平衡	无
多级反馈队列	Multilevel Feedback	抢占（时间片用完）	不强调	不强调	可能较大	对I/O型进程有利	可能

基于优先级的抢占式多任务调度（Windows）

典型系统所采用的调度算法

• UNIX 动态优先数法
• 5.3BSD 多级反馈队列法
• Linux 抢占式调度
• Windows 基于优先级的抢占式多任务调度
• Solaris 综合调度算法

调度过程：

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

引发线程调度的条件：

• 进程终止（正常或发生错误）
• 新进程创建（变为就绪态）
• 等待进程变成就绪
• 运行进程变成就绪
• 运行进程变成阻塞
• 一个线程的优先级改变了
• 一个线程改变了它的亲和处理机集合

32个线程优先级：

• 实时优先级（16-31)不改变其优先级
• 可变优先级（1-15）其优先级可在一定范围内升高或降低
• 系统线程（0）用于对系统中空闲物理页面清零（零页线程）

调度策略：

• 主动切换：转到阻塞态
• 抢占：回到相应优先级的就绪队列队首，如果被抢占线程处于实时优先级，则重置为- 完整的时间配额，如果是可变优先级，则时间配额不变（得到剩余时间配额）
• 时间配额用完：如果线程的优先级没有降低，则回到原来就绪队列末尾（可能继续运行），如果优先级降低了，则选择更高优先级的线程运行。

线程优先级的提升：

• I/O操作完成
• 信号量或事件等待结束
• 前台进程中的线程完成一个等待操作
• 由于窗口活动而唤醒窗口线程
• 线程处于就绪态超过了一定时间还没有运行（饥饿现象）