操作系统概述

操作系统的概念

操作系统（Operating System，OS）是管理计算机硬件的软件。

  • 用户视角关注易用性而非资源利用率；
  • 系统视角看，操作系统是资源分配器，为各个程序和用户分配资源，操作系统是控制程序，管理用户程序的执行。

定义：

  • 操作系统包括当你预定一个操作系统时销售商发售的一切；
  • 操作系统时一直运行在计算机上的程序，称为内核（kernel）

计算机系统的组成

  • 硬件：为计算机提供基本的计算资源，如CPU、内存、I/O设备等；
  • 操作系统：控制硬件，并协调各个用户应用程序的硬件使用；
  • 应用程序：确定了用户为解决计算问题而使用这些资源的方式；
  • 用户：

操作系统的中断处理

中断： 是操作系统和硬件交互的关键部分，硬件可以通过系统总线随时发送信号到CPU触发中断，当CPU被中断时，它停止正在做的事情，并立即转到固定位置执行中断处理程序，中断处理程序是操作系统的一部分，它负责处理中断，并恢复CPU到中断前的状态。

存储结构

主存、辅存

I/O结构

  • 同步I/O：I/O 启动后，在 I/O 完成之前，控制权不会返回给用户程序。
  • 异步I/O：I/O 启动后，控制权将返回给用户程序，而无需等待 I/O 完成
  • DMA（直接内存访问）：设备控制器将数据块从缓冲区存储直接传输到主内存，无需 CPU 干预；每个块只生成一个中断，而不是每个字节生成一个中断

计算机系统的体系结构

根据通用处理器的数量

  1. 单处理器系统：使用一个具有单个处理核（core）的CPU。处理核是执行指令和利用寄存器存储数据的组件。
  2. 多处理器系统：多个处理器，每个处理器都有一个单核CPU。
    -SMP（对称多处理）：每个对等CPU处理器执行所有任务，包括操作系统功能和用户进程。每个处理器都有自己的CPU，每个CPU都有自己的寄存器和私有缓存，但是所有处理器通过系统总线共享物理内存。
    -非对称多处理（主从）
    -多核系统
    -NUMA：非均匀内存访问（NUMA）是一种内存访问策略，其中内存访问时间取决于内存的位置。在NUMA系统中，内存被划分为多个节点，每个节点都有自己的本地内存。当处理器访问本地内存时，访问时间较短，而访问远程内存（位于其他节点）时，访问时间较长。
  3. 集群系统：
    -对称集群…
    -非对称集群…

名词释义：

  • CPU：执行指令的硬件
  • 处理器：包含一个或多个CPU的物理芯片
  • 处理核：CPU的基本计算单元
  • 多核：位于同一CPU上的多个处理核
  • 多处理器：多个处理器
    表示计算机系统的单个计算单元时，使用术语CPU；表示CPU的一个或多个处理核时，使用术语单核或多核

一些概念

  • 并发：指两个或多个事件可以在同一个时刻发生，多核CPU可以实现并行，一个cpu同一时刻只有一个程序在运行；
  • 并行：指两个或多个事件可以在同一个时间间隔发生，用户看起来是每个程序都在运行，实际上是每个程序都交替执行。
  • 多道程序设计（multiprogramming）：通过组织程序使得CPU总有一个执行作业，从而提高CPU利用率，让用户满意（通过切换进程：正在执行的程序）
    适合批处理作业
    核心思想：内存中可以同时存在多道作业，它们并发或并行运行
    通过合理调度，让多道作业交替占用处理机，同时使用不同的资源。
    无交互性：用户直到作业结束前，都不能干预作业的执行。
  • 分时（time sharing）、多任务（multitasking）：多道的逻辑扩展
    适合交互作业
    每个用户获得相同的时间片，让多个进程轮流占用处理机，每个进程不管是否结束，在规定的一个时间片内都会被强制停止，更换等待队列中的下一个进程。如此循环执行。（running–>ready状态：时间片终止）
    效果：每个用户感觉独占处理机
    交互性：用户则可以干预作业的执行（可以根据系统响应结果，提出下一个要求）
    关注指标：响应时间
  • 双模式：用户模式、内核模式（特权模式、监视模式、系统模式），通过模式位区分为操作系统执行的任务和为用户执行的任务。
      执行用户应用时，处于用户模式，当用户应用通过*系统调用*请求操作系统服务时，系统从用户模式切换到内核模式。
  • 定时器（timer）：阻止用户程序、设置为在特定时间段后中断计算机，当定时器中断时，控制自动转到操作系统。

资源管理

进程管理

进程：主动实体，单线程进程有一个程序计数器PC，指定下一个要执行的指令，多线程进程有多个PC

 - 进程是系统的工作单元，有系统进程、用户进程，进程为了完成任务，需要一定的资源，包括CPU时间、内存、文件、I/O设备等，当进程终止时，操作系统将回收所有可重用的资源。

操作系统负责进程管理的以下活动：

 - 创建和删除用户进程和系统进程
 - 在CPU上调度用户进程和系统进程
 - 挂起和重启进程
 - 提供进程同步机制
 - 提供进程通信机制
 - 提供死锁处理机制
  • 程序：被动实体，如磁盘上的文件内容

    内存管理

    主存：现代计算机系统执行的中心，是一个大的字节数组，CPU所能直接寻址和访问的唯一大容量存储器。
    如果一个程序需要执行，那么它必须映射到绝对地址，并且加载到内存。进程终止时，它的内存空间得以释放。
    操作系统负责内存管理的以下活动：
  • 记录内存的哪部分在被使用，以及被谁使用
  • 根据需要分配和释放内存空间
  • 决定哪些进程会调入或调出内存

    文件管理

    操作系统将存储设备的物理属性抽象为一个逻辑存储单元，并提供信息存储的统一逻辑视图：文件
    操作系统将文件映射到物理介质上，并通过存储设备访问文件。
    文件是创作者定义的相关信息组合，通常为程序和数据。
    操作系统负责文件管理的以下活动：
  • 创建和删除文件
  • 创建和删除目录，以便组织文件
  • 提供文件和目录的操作原语
  • 映射文件到大容量存储
  • 备份文件到稳定存储介质

    大容量存储管理

    计算机必须提供辅助存储以备份主内存，大多数计算机使用磁盘作为主要的在线存储介质。
    操作系统负责与外存管理相关的以下活动：
  • 安装和卸载
  • 空闲空间管理
  • 存储分配
  • 硬盘调度
  • 分区
  • 保护

    高速缓存管理

    缓存是一种更快的存储系统
  • 可编程寄存器Programmable Register(高速缓存实现形式1)：段表、页表
  • Cache(高速缓存实现形式2)：由硬件管理的存储系统
  • Main memory （高速缓存实现形式3）：主内存可以被视为辅助存储的快速缓存
    缓存管理：
  • 缓存的大小有限
  • 数据一致性

    I/O系统管理

    OS 的一个目的是向用户隐藏硬件设备的特性
    I/O子系统包括以下几个组件：
  • 包括缓冲、高速缓存和假脱机的内存管理组件
  • 设备驱动器的通用接口
  • 特定硬件设备的驱动程序

保护和安全

保护：一种机制，用于控制进程或用户访问计算机系统的资源

- 检测组件子系统之间的接口处的潜在错误
- 及早检测到接口错误通常可以防止另一个出现故障的系统（故障）对健康的子系统进行污染（影响）。
- 未受保护的资源无法抵御未经授权或不称职 （不胜任的） 用户的使用/误用
- 面向保护的系统提供了一种区分授权和未授权使用的方法。

安全：防止系统不受外部或内部的攻击

- 具有足够保护的系统仍然容易出现故障并允许不适当的访问
- 防止一些攻击是作系统的责任，而其他的则留给 policy（规章制度）或其他软件

几种操作系统

  • 分布式系统是物理上独立的、可能是异构的、通过网络相连的一组计算机系统。
    网络是两个或多个系统之间的通信路径
  • 网络操作系统提供跨网络的文件共享、不同计算机进程的消息交换等功能。与分布式操作系统相比，运行网络作系统的计算机独立于所有其他计算机自主 （自治），分布式系统提供了一个自治程度较低的系统，并提供了一种单一作控制网络的不同计算机的错觉
  • 实时嵌入式系统
  • 多媒体系统
  • 手持式系统

计算环境

  • 传统计算机：办公环境、家庭环境
  • 客户端-服务器计算
  • 点对点计算
  • 基于 Web 的计算

操作系统结构

提供的服务、用户和程序员采用的接口、系统组件及其相互关系

操作系统的服务

有一组服务提供用户功能：

  • 用户界面：图形用户界面GUI、命令行CLI
  • 程序执行
  • I/O操作
  • 文件系统操作
  • 通信
  • 错误检测
    还有一组服务确保系统本身高效运行：
  • 资源分配
  • 日志
  • 保护和安全

系统调用

  1. 系统调用提供操作系统服务接口，这些调用常用C/C++编写
    通常，应用程序开发人员根据应用编程接口（API）来设计程序，API为方便应用程序员规定了一组函数，包括每个函数的输入参数和程序员所想得到的返回值。
    最常见的API
  • Win32 API，适用于 Windows 系统
  • POSIX API，用于 UNIX/Linux/MacOS X
  • JAVA API，用于 JAVA 虚拟机
    在后台，API函数通常为应用程序开发人员调用世纪系统调用，如Windows函数CreateProcess()实际调用Windows内核的系统调用NTCreateProcess()。
  1. 为什么使用 API 而不是系统调用？
  • 可移植性/兼容性 ：基于 API 的程序可以在支持相同 API 的任何不同系统上编译和运行
  • 简单性/可用性：API 比系统调用更容易使用

  1. 系统调用接口
    由RTE（运行时环境）提供，作为操作系统提供的系统调用的链接。
    系统调用接口截取API函数的调用，并调用操作系统中的所需系统调用。

  2. 三种向操作系统传递参数的方法

  • 通过寄存器传递参数：速度快，无需内存操作，减少开销，但在某些情况下，参数可能比寄存器多
  • 通过堆栈传递参数：支持大量参数或复杂数据结构。需额外内存操作，性能略低于寄存器传递
  • 通过内存传递参数：灵活性高，不限制参数数量和大小。堆栈操作较慢，且需注意堆栈平衡（调用者或被调用者需清理堆栈）

系统调用的类型

  1. 进程控制
    • 创建和终止进程
    • 加载、执行
    • 获取进程属性，设置进程属性
    • 等待事件，信号事件
    • 分配和释放内存
  2. 文件管理
    • 创建文件，删除文件
    • 打开，关闭
    • 读，写，重定位
    • 获取文件属性，设置文件属性
  3. 设备管理
    • 请求设备，释放设备
    • 读，写，重定位
    • 获取设备属性，设置设备属性
    • 逻辑增加或移除设备
  4. 信息维护
    • 获取时间和日期，设置时间和日期
    • 获取系统数据，设置系统数据
    • 获取进程、文件或设备属性
    • 设置进程、文件或设备属性
  5. 通信
    • 创建、删除通信连接
    • 发送、接收消息
    • 传输状态信息
    • 增加或移除远程设备
  6. 保护
    • 获取文件权限
    • 设置文件权限

进程

进程的概念

  • 关于对CPU活动的称呼，早期批处理系统称为作业，分时系统称为用户程序/任务，后来成为进程。（进程和作业几乎可以呼唤使用）
  • 进程是执行的程序（非正式）
  • 进程包括
    - 文本段：可执行代码，大小固定
- 数据段：全局变量，大小固定
- 堆段：动态分配的内存，动态变化
- 栈段: 调用函数时的临时数据存储（函数参数、返回地址、局部变量...），动态变化
  • 进程是动态实体，当一个可执行文件被加载到内存，这个程序就成为进程
  • 程序段、数据段、PCB（进程控制块）组成了进程实体，一般情况下把进程实体简称为进程，PCB是进程的唯一标识，创建进程就是创建PCB，终止进程就是撤销PCB。

进程的概念

进程的特征

进程状态

5状态模型（重要）

进程在执行时会改变状态，一次只能有一个进程可在处理核上运行，但是许多进程可处于就绪或等待状态

  • 创建（new）：进程正在创建
  • 就绪（ready）：进程等待分配CPU
  • 运行（running）：进程正在执行，使用CPU
  • 等待（waiting）、阻塞（blocking）：进程等待发生某个事件（如I/O完成或受到信号）
  • 终止（terminated）：进程已完成执行

5状态模型

PCB（进程控制块）

操作系统中每个进程的表示，都采用进程控制块PCB，用作启动或重新启动进程所需的所有数据以及一些记账信息的存储仓库，它包含

  • 进程状态：新建、就绪、执行、阻塞、终止等
  • 程序计数器：表示进程将要执行的下个指令的地址
  • CPU寄存器：…
  • CPU调度信息：包括优先级、调度队列的指针和其他调度参数
  • 内存管理信息：包括基址/界限寄存器的值/段表/页表…
  • 记账信息：CPU时间、实际使用实际、时间期限、记账数据、作业或进程数量等
  • I/O状态信息：包括分配给进程的I/O设备列表和打开文件列表等

OS是根据PCB来对并发执行的进程进行控制和管理的。
在进程的整个生命期中，系统总是通过PCB对进程进行控制的，即系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的。
所以说，PCB是进程存在的唯一标志。

线程

进程（Process）与线程（Thread）：

  • 线程：操作系统进行运行调度的最小单位。
  • 进程：系统进行资源分配和调度的基本单位。

区别与联系：

  • 一个进程可以有一个或多个线程；
  • 线程包含在进程之中，是进程中实际运行工作的单位；
  • 进程的线程共享进程资源；
  • 一个进程可以并发多个线程，每个线程执行不同的任务。

进程调度

为什么要进程调度

  • 多道程序设计的目标：无论何时都有进程执行，从而最大化CPU利用率
  • 分时系统的目标：在进程之间快速切换CPU核，以便用户在程序运行时能与其交互。
  • 进程调度器实现选择一个进程到CPU核上执行，每个CPU核一次只能运行一个进程。对于单核CPU，一次只能运行一个进程，多核CPU一次可以运行多个进程。
  • 如果进程的数量多于CPU核的数量，则进程调度器必须决定哪个进程应该使用CPU核，哪个进程应该等待。
  • 同时，为平衡多道与分时的目标，还需考虑进程的类型。I/O密集型进程指花费在I/O上的时间多于花费在计算上的时间。CPU密集型进程很少生成I/O请求，而是使用更多的时间进行计算。

调度队列

  1. 就绪队列:放置就绪的进程
  2. 等待队列：放置等待某个事件发生的进程

最初，新进程被加载到就绪队列中，知道被选中执行或被分派。当进程被分配到CPU核并被执行时，可能发生下列事件

  • 进程发出I/O请求，此时进程被移到等待队列中，直到I/O完成，回到就绪队列
  • 进程可能创建一个新的子进程，然后返回到等待队列并等待子进程终止
  • 进程可能由于中断或时间片到期而被强制释放CPU核，并被放回到就绪队列
    进程重复这一循环直到终止，然后从就绪队列中删除，其PCB和资源也被释放

调度器

  • CPU调度器负责从就绪队列的进程中进行选择，并为其中之一分配一个CPU核。
  • CPU调度器必须频繁地为CPU选择一个新进程。
  • 交换：有时从内存中删除一个进程更有利，稍后该进程可重新引入内存，并从中断的地方继续执行。交换通常仅在内存已被过度使用且必须释放时才需要。

长程调度、短程调度、中程调度

  1. 长程调度（作业调度、高级调度）

    • 从作业队列中选择应将哪些进程引入就绪队列
    • 长期调度程序的执行频率要低得多
    • 在批处理系统中，需要有作业调度的过程，以便将它们分批地装入内存，在分时系统和实时系统中，通常不需要长期调度。它的频率比较低，主要用来控制内存中进程的数量。
    • 功能：决定哪些作业（或用户程序）从外存后备队列调入内存，并为其创建进程、分配资源（如内存、I/O设备），使其进入就绪队列等待执行
      • 触发时机：新作业提交或系统资源空闲时，频率较低（分钟级至小时级）
      • 核心作用：控制系统的并发度（多道程序数量），平衡资源负载
      • 在批处理系统中尤为重要，分时/实时系统通常不需要
      • 调度算法：先来先服务（FCFS）、短作业优先（SJF）、优先级调度等

  2. 短程调度（CPU调度、进程调度）

    • 选择接下来应执行的进程并分配 CPU
    • 它必须经常为 CPU 选择一个新的进程，选择必须很快
    • 功能：从就绪队列中选择一个进程分配CPU时间片，直接决定进程的执行顺序
    • 触发时机：时钟中断、I/O请求、进程阻塞或终止时，频率极高（毫秒级）
    • 核心作用：最大化CPU利用率与响应速度，确保多任务并发执行
    • 分为抢占式（如时间片轮转RR）和非抢占式（如FCFS）两种调度方式
    • 常见算法：时间片轮转（RR）、最短剩余时间优先（SRTF）、多级反馈队列（MLFQ）等

  3. 中程调度（交换调度）

    • 功能：管理内存中的进程数量，通过“挂起（Suspend）”或“激活（Resume）”进程来缓解内存压力。将暂时不运行的进程换出到外存（挂起状态），待条件满足时再换入内存
    • 触发时机：内存不足或系统负载过高时，频率介于长程和短程调度之间（秒级至分钟级）
    • 核心作用：提高内存利用率和系统吞吐量
    • 与交换技术（Swapping）配合使用，动态调整进程在内存与外存间的分布

  4. 三者的联系与区别

    • 协作流程：长程调度为进程提供“准入资格”，中程调度调节内存中的进程数量，短程调度最终分配CPU资源
    • 频率：短程 > 中程 > 长程
    • 目标：长程关注系统整体负载均衡，中程优化内存使用，短程确保CPU高效运行

三级调度图

上下文切换

上下文切换：切换CPU核到另一个进程需要保存当前进程的状态并恢复另一个进程的状态

进程上下文采用进程PCB表示，包括CPU寄存器的值、进程状态核内存管理信息等。

进程操作

进程创建

每个进程可以再创建其他进程，从而形成进程树。
对进程的识别采用进程标识符pid，每个进程都有一个唯一的pid,通常为一个整数，可用作索引，以便访问内核中进程的各项属性。

子进程可以从操作系统获得资源或者父进程获得资源子集。父进程可能要在子进程之间分配资源或共享资源，限制子进程只能使用父进程的资源，可以防止创建过多进程，导致系统超载。

当进程创建新进程时，有两种执行可能：

  • 父进程与子进程并发执行
  • 父进程等待，直到某个或全部子进程执行完
    新进程的空间也有两种可能：
  • 子进程时父进程的复制品
  • 子进程加载另一个新程序
    Unix中，通过系统调用fork()创建新进程，对于子进程，fork()返回0，对于父进程，fork()返回子进程的pid，如果fork()失败，则返回-1。
    exec()函数族用于将新程序加载到子进程，系统调用exec()加载二进制文件到内存中，并开始执行。

    进程终止

当进程执行完最后一条语句并通过系统调用exit()请求操作系统删除自身时，进程终止。这时，进程可以将状态值返回到父进程（通过wait()）。
如果进程已经终止，但是其父进程尚未调用wait(),这样的进程称为僵尸进程
如果父进程没有调用wait()就终止，导致子进程称为孤儿进程。

进程间通信(IPC)

进程可以是独立的或协作的，对于协作进程，需要有一种进程间通信机制，以允许进程相互交换数据。有两种基本模型：共享内存和消息传递。

共享内存

共享内存模型建立起一块供协作进程共享的内存区域，进程通过向共享区域读写数据来交换信息。
允许通信达到最大速度和便捷性，因为它可以在内存速度下完成

共享内存系统
采用共享内存的进程间通信需要通信进程建立共享内存区域
通常，共享内存区域位于创建共享内存段进程的地址空间中
其他进程必须将共享内存段附加到它们的地址空间中

消息传递

消息传递模型中，通信是通过在协作进程之间的交换消息来实现的。
适用于交换较小量的数据，更慢，更容易实现，经常采用系统调用。

消息传递系统
允许进程进行通信和同步动作
至少提供两种操作：send(message) 和 receive(message)
消息大小可以是固定的或可变的
如果P和Q需要通信，那么他们必须发送消息和接收消息，这意味着他们必须要有通信链路

通信链路的逻辑实现

  • 直接或间接的通信
    直接通信的每个进程必须明确指明通信的接收者和发送者，send(P,message) receive(Q,message) 寻址对称
    这种方案的通信链路具有以下属性：链路自动建立，每个链路只与两个进程相关，每对进程只有一个链路
    send(P,message)向进程P发送message receive(id,message)从任何进程接收message 非对称

    间接通信中通过邮箱或端口来发送和接收消息。邮箱可以抽象成一个对象，进程可以向其中存放消息，也可以从中删除消息。每个邮箱都有一个唯一的标识符。
    一个进程可以通过多个不同的邮箱与另外一个进程通信，但是两个进程只有拥有一个共同邮箱时才能通信。
    send(A,message)向邮箱A发送message receive(A,message)从邮箱A接收message
    链路特点：仅当进程共享一个公共邮箱时才建立链接 一个链接可以与多个进程相关联 每对进程可以共享多个通信链接，每个链接对应一个邮箱

    邮箱可以由进程或操作系统拥有。如果邮箱为进程拥有，那么需要区分所有者（只能从邮箱接收）和使用者（只能向邮箱发送）。当拥有者终止，邮箱消失
    如果邮箱由操作系统拥有，进程可以创建新的邮箱、通过邮箱发送和接收消息、删除邮箱

  • 同步或异步的通信
    消息传递可以是阻塞的（同步的）或者非阻塞的（异步的）

    • 阻塞发送：发送进程阻塞，直到消息由进程或邮箱接收。
    • 非阻塞发送：发送进程发送消息，并恢复操作。
    • 阻塞接收：接收进程阻塞，直到消息可用。

    • 非阻塞接收：接收进程受到一个有效消息或空消息。

      阻塞发送和阻塞接收，在发送方和接收方之间有一个 rendezvous（同步点），可以解决消费者问题
      非阻塞发送和阻塞接收，最常见

  • 自动或显式的通信

生产者-消费者问题

线程

线程：CPU利用率的一个基本单元，包括线程ID、程序计数器、寄存器组和堆栈。与同一进程的其他线程共享代码段、数据段和其他操作系统资源。

多线程编程的优点

  • 响应性：当交互式应用程序的一部分被阻止或正在执行长时间的作时，交互式应用程序可能会继续运行
  • 资源共享：线程共享它们所属的进程的内存和资源
  • 经济：
  • 可伸缩性

多线程模型

用户模型与内核模型的关系

  • 多对一模型
    定义：多个用户线程映射到单个内核线程，线程管理完全由用户空间的线程库（如线程调度、同步）负责，内核仅感知一个内核线程
    优点：
    高效切换：线程切换在用户态完成，无需切换到内核态，开销小
    线程数量灵活：用户线程数量几乎不受限制，适合轻量级任务
    缺点：
    阻塞问题：若一个用户线程执行阻塞系统调用（如I/O），整个进程会被阻塞，其他线程无法执行
    无法并行：多核处理器上无法利用多核优势，因为内核仅调度一个线程
  • 一对一模型
    定义：每个用户线程对应一个独立的内核线程，由操作系统直接管理调度
    优点：
    真正并发：线程阻塞时不影响其他线程，且支持多核并行
    与内核线程一致：线程调度、优先级等由内核实现，功能完整
    缺点：
    资源开销大：每个线程需创建内核线程，数量受系统限制（如Linux默认线程数限制）
    切换成本高：用户态与内核态频繁切换影响性能
  • 多对多模型
    定义：用户线程动态映射到多个内核线程（数量通常少于用户线程），结合前两种模型的优点
    优点：
    平衡性能与并发：既避免多对一的阻塞问题，又减少一对一的开销
    灵活调度：内核线程可绑定到不同CPU核心，实现负载均衡
    缺点：
    实现复杂：需用户层和内核协同调度，开发难度高
    依赖第三方库：操作系统原生支持较少，如Go语言的goroutine（通过调度器实现M:N模型）

线程库

线程库：为程序员提供用于创建和管理线程的 API

两种实现方式：
库完全位于用户空间中
操作系统支持的内核级库

多线程问题

系统调用fork()和exec()

信号处理

线程池

CPU调度

多道程序的目的是始终允许某个进程一直在运行，最大化CPU利用率。
多个程序同时处于内存中。当一个进程等待时，操作系统就从该进程接管CPU控制，并将CPU移交给另一进程。
进程执行包括周期地进行CPU执行和I/O等待，进程在这两个状态之间不断交替。

CPU调度程序

每当CPU空闲时，操作系统应从就绪队列中选择一个进程来执行。进程选择采用CPU调度程序，调度程序从内存中选择一个能够执行的进程，并为其分配CPU。

需要CPU调度的四种情况

  1. 当一个进程的状态从运行->等待 （例如I/O请求） 非抢占
  2. 当一个进程的状态从运行->就绪 （例如当出现中断）抢占
  3. 当一个进程的状态从等待->就绪 （例如I/o完成） 抢占
  4. 当一个进程终止 非抢占

抢占式和非抢占式调度
如果调度只能发生在第一种和第四种情况下，则调度方案式非抢占的，否则是抢占的(在所有条件下进行调度)。
在非抢占调度下，一旦某个进程分配到CPU，该进程就会一直使用CPU，直到它终止或切换到等待状态。

分派程序、分派器：一个模块，用来将CPU核控制交给由CPU调度程序选择的进程。功能包括：切换上下文、切换到用户模式、跳转到用户程序的合适位置以便继续执行程序。

调度准则、标准

用于比较CPU调度算法

  • CPU利用率：使CPU尽可能繁忙
  • 吞吐量：一个时间单元内进程完成的数量
  • 周转时间：从进程提交到进程完成的时间段，衡量的是运行这个进程需要多长时间，包括在就绪队列中等待、在CPU上执行和I/O执行
  • 等待时间：在就绪队列中等待的时间之和，CPU调度算法不会影响进程运行和执行I/O的时间，只影响在就绪队列中的等待时间
  • 响应时间：从提交请求到产生第一响应的时间，是开始响应的时间

调度算法

CPU调度处理就绪队列中哪些进程将被分配给CPU核的问题。

先来先服务 （FCFS）

先请求的CPU进程先分配到CPU，可通过FIFO队列实现。
缺点：平均等待时间往往很长、护航效应（所有其他进程都等待一个大进程释放CPU）
非抢占
长作业有利，短作业不利

短作业优先（SJF）

将CPU分配给具有最短下次CPU突发的进程
对于一组给定的进程，SJF的平均等待时间最短
可以是抢占的，也可以是非抢占的
缺点：长进程可能饥饿；无法预测下次CPU突发的长度，只能进行近似预测

优先级调度

CPU被分配给具有最高优先级的进程。SJF算法是优先级算法的一个特例。
抢占或非抢占
缺点：无穷阻塞（饥饿）：某个低优先级进程无穷等待CPU
解决方案：老化（aging）：逐渐增加在系统中等待时间很长时间的进程的优先级

轮转调度（RR）

CPU调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的CPU。
抢占
没有进程被连续分配超过一个时间片的CPU（除法它是唯一可运行的），如果CPU突发超过一个时间片，该进程会被抢占，并被添加到就绪队列尾部。
公平，如果就绪队列中有 n 个进程，并且时间量程为 q，每个进程获得 1/n 的 CPU 时间（一次最多 q 个时间单位），没有进程等待超过 （n-1） q 个时间单位。
性能很大程度取决于时间片的大小，过大，变为FCFS，过小，上下文切换开销大

多级队列调度

就绪队列被划分为几个单独的队列，每个队列具有自己的优先级和调度算法。进程根据其属性被分配到某个队列中。
比如实时进程队列、系统进程队列、交互进程队列、批处理队列
必须在队列之间进行调度，通常采用固定优先级抢占调度。
可能导致饥饿

多级反馈队列调度

允许进程在队列之间迁移，根据不同CPU突发的特点来区分进程，如果进程使用过多CPU时间，那么它会被移动到更低优先级的队列，将I/O密集型和交互进程放在更高优先级队列。
在较低优先级队列中等待过长的进程会被移动到更高优先级队列，通过老化防止饥饿
最通用的调度算法，也是最复杂的算法

多处理器调度

多处理器调度的方法
非对称多处理(AMP)
只有一个处理器（主服务器）处理所有调度决定、I/O处理以及其他系统活动，其他的处理器只执行用户代码。
简单，只有一个处理核能够访问系统数据结构，减少了数据共享的需要

对称多处理(SMP)
每个处理器都是自调度的
公共就绪队列中的所有进程或每个处理器都有自己的就绪进程私有队列

线程调度

大多数现代操作系统上，内核级线程才是操作系统所调度的，而不是进程，用户级线程由线程库管理，要在 CPU 上运行，用户级线程最终必须映射到关联的内核级线程

竞争范围
进程竞争范围(PCS)
多对一和多对多模型，线程库将用户级线程调度到 LWP（虚拟 CPU）上运行
竞争”CPU”(LWP)发生在同一进程的线程之间，将用户线程调度到可用的 LWP 上，并不意味着在 CPU 上运行的线程，它要求 OS 将内核线程调度到物理 CPU 上
通常，PCS 是根据优先级完成的

系统竞争范围(SCS)
决定将哪个内核线程调度到 CPU 上
系统中所有线程之间对 CPU 的竞争
使用一对一模型的系统仅使用 SCS 调度线程

进程同步