操作系统

操作系统概述

操作系统的概念

操作系统（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）：进程已完成执行

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 调度线程

进程同步

竞争条件：多个进程并发访问和操作同一数据并且执行结果与特定访问顺序相关。
为防止竞争条件，需要确保一次只有一个进程可以操作变量count，为了做出这种保证，要求这些进程按一定方式来同步。

临界区问题

临界区：一段代码，其中进程可能正在访问与至少一个其他进程共享的数据。
当一个进程在临界区内执行时，其他进程不允许在它们的临界区内执行。即没有两个进程可以在它们的临界区内同时执行。
临界区问题就是要设计一个协议以便同步活动，从而合作共享数据。
在进入临界区前，每个进程应请求许可，实现这一请求的代码区为进入区
临界区之后有退出区，其他代码为剩余区。

while(true){
    //进入区
    临界区
    //退出区
    剩余区
}

临界区问题的解决方案应满足三条要求

• 互斥：如果进程p在临界区内执行，其他进程不能在其临界区内执行
• 进步、空闲让进：如果没有进程在临界区内执行，并且有进程需要进入临界区，那么只有哪些不在剩余区内执行的进程可以参加选择，以便确定下次谁能进入临界区，并且这种选择不能无限推迟
• 有限等待：从一个进程做出进入临界区的请求直到这个请求允许位置，其他进程允许进入临界区的次数有上限

Peterson解决方案

基于软件的临界区问题解决方案，满足互斥、进步、有限等待
适用于两个进程交替执行临界区与剩余区
两个进程共享两个数据项：

• int turn：哪个进程可以进入临界区，turn=i，标识Pi可以在临界区内执行
• boolean flag[2]：表示哪个进程准备进入临界区，flag[i]=true，标识Pi准备进入临界区

pi的结构
while(true){
    flag[i]=true;
    turn=j;
    while(flag[j]&&turn==j);
    //临界区
    flag[i]=false;
    //剩余区
}

pj的结构
while(true){
    flag[j]=true;
    turn=i;
    while(flag[i]&&turn==i);
    //临界区
    flag[j]=false;
    //剩余区
}

硬件同步支持

原子指令：以原子的方式检测和修改字的内容

test_and_set:

//将lock设置为true，并返回lock的旧值
boolean test_and_set(boolean *lock){
    boolean old=*lock;
    *lock=true;
    return old;
}

//采用test_and_set实现互斥
while(true){
    while(test_and_set(&lock));

    //临界区

    lock=flase;//释放锁

    //剩余区
}

如何实现互斥？
初始状态：
lock = false，表示锁是可用的（没有进程持有锁）。

进程尝试进入临界区：
调用 TestAndSet(&lock)：

• 如果 lock 是 false（未锁定）：
  TestAndSet 返回 false，同时将 lock 设置为 true（锁定）。
  while 循环退出，进程进入临界区。

• 如果 lock 是 true（已锁定）：
  TestAndSet 返回 true，同时 lock 仍然是 true。
  while 循环继续，进程忙等待（busy-wait），直到锁被释放。

进程退出临界区：
设置 lock = false，释放锁。
其他进程现在可以获取锁。

为什么能保证互斥？
TestAndSet 是原子的：
硬件保证 TestAndSet 的执行不会被中断，因此不会有两个进程同时读取 lock 的旧值并错误地进入临界区。
锁机制：
当一个进程进入临界区时，lock 被设置为 true，其他进程调用 TestAndSet 会得到 true，从而忙等待。
只有持有锁的进程能进入临界区，其他进程必须等待锁被释放（lock = false）。

compare_and_swap:

//如果value等于expected，则将value设置为new_value，返回value的旧值
int compare_and_swap(ind *value,int expected,int new_value){
    int temp=*value;
    if(*value==expected){
        *value=new_value;
    }
    return temp;
}

//采用compare_and_swap实现互斥
while(true){
    while(cpmpare_and_swap(&lock,0,1)!=0);
    //临界区
    lock=0;
    //剩余区
}

如何保证互斥？
初始状态：

lock = 0（锁是可用的）。
进程尝试获取锁：

调用 compare_and_swap(&lock, 0, 1)：
如果 lock == 0（锁可用）：
compare_and_swap 返回 0，并设置 lock = 1（锁定）。
while 循环退出，进程进入临界区。
如果 lock == 1（锁已被占用）：
compare_and_swap 返回 1，lock 仍为 1。
while 循环继续，进程忙等待（Busy Waiting），直到锁被释放。
进程释放锁：

设置 lock = 0，允许其他进程获取锁。

上述算法满足互斥，但是却不满足有限等待

// lock：共享锁变量，初始为 0（表示未锁定）。
// waiting[]：布尔数组，waiting[i] = true 表示进程 i 正在等待进入临界区。
// key：局部变量，用于 CAS 操作的结果检查。
// n：进程总数。
while(true){
    waiting[i]=true;//标记自己为等待状态
    key=1;
    while(waiting[j]&&key==1){
        key=compare_and_swap(&lock,0,1);
        //若lock==0（锁空闲），将lock设置为1并返回0，退出循环，进程i成功获取锁
        //若lock==1（锁被占用），返回1，继续循环，进程i继续忙等待
    }
    waiting[i]=false;//进入临界区前取消等待标记

    //临界区

    j=(i+1)%n;//检查下一个进程
    while((j!=i)&&!waiting[j]){
        j=(j+1)%n;//轮询找到下一个等待的进程
    }
    if(j==i) lock=0;//若无其他进程等待，释放锁
    else waiting[j]=false;//否则，唤醒进程j，进程j退出while循环

    //剩余区
}

互斥：只有waiting[i]==false或者key==0时，进程Pi才能进入临界区，只有当执行compare_and_swap时，key的值才能变为0。执行compare_and_swap的第一个进程会发现key=0，所有其他进程必须等待。只有另一进程离开临界区时，变量waiting[i]的值才能变成false。每次只有一个waiting[i]的值被设置成false，以满足互斥要求
空闲让进：进程在退出临界区时获奖lock设置为0，或将waiting[j]设置为false,这两种情况都允许等待进程进入临界区。
有限等待：当一个进程退出临界区时，它会循环扫描数组，指派第一个等待进程作为下次进入临界区的进程，因此任何等待进入临界区的进程只需等待n-1次

互斥锁

采用互斥锁保护临界区，防止竞争条件，一个进程在进入临界区时应得到锁，在退出临界区时释放锁。
用函数acquire()获取锁，用release()释放锁

while(true){
    //获取锁
    临界区
    //释放锁
    剩余区
}

acquire(){
    while(!available);//忙等待
    available=false;
}
release(){
    available=true;
}

忙等待：当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环地调用acquire()。
自旋锁：线程在获取锁失败时不会阻塞或休眠，而是通过循环（自旋）不断尝试获取锁，直到成功为止。自旋锁适用于锁持有时间较短的场景，因为它避免了上下文切换的开销。然而，如果锁持有时间较长，自旋锁会导致CPU资源浪费，因为线程会一直占用CPU进行忙等待。

信号量

同步工具
一个信号量S是一个整型变量，除了初始化外只能通过两个标准原子操作wait()（P操作）和signal()（V操作）来访问。

信号量本质上是一个计数器，结合等待队列实现对共享资源访问的控制。其核心组成包括：
整型变量：表示可用资源数量（称为信号量值）
等待队列：存放因资源不足而阻塞的进程/线程
原子操作：P（wait）和V（signal）操作

信号量的值含义：

0：表示当前有可用资源，数值即资源数量
=0：资源已被占用，无可用资源

<0：绝对值表示等待该资源的进程数量

wait(S){
    while(S<=0);
    S--;
}
signal(S){
    S++;
}

• 计数信号量：信号量S的值表示可用资源的数量，值不受限制。
  可以用于控制访问具有多个实例的某种资源，信号量的初值为可用资源的数量，当进程需要使用资源时，需要对该信号量执行wait()操作（减少信号量的计数），当进程释放资源时，需要对该信号量执行signal()操作(增加信号量的计数)。当信号量的资源为0时，所有资源都在使用中。之后，需要使用资源的进程将会陷入阻塞，直到计数大于0。
  也可以用信号量解决同步问题。例如，两个并发执行的线程：P1有语句S1，P2有语句S2，要求只有在S1执行后才能执行S2，通过让P1和P2共享一个信号量synch，初始化为0，可以实现。因为synch初始化为0，只有在P1调用signal(synch)后，即S1执行完后，P2才能执行S2。
  P1中：

  S1;
  signal(synch); //S1执行后，释放信号量，P2可以执行S2

  P2中：

  wait(synch); //P2等待，直到P1释放信号量
  S2;

• 二进制信号量：类似于互斥锁，值只能为0或1
  保证同一时刻只有一个进程进入临界区

  semaphore mutex=1;
  while(true){
  wait(mutex);
  //临界区
  signal(mutex);
  //剩余区
  }

为了克服忙等待，通过修改wait和signal的定义
wait：当一个进程执行wait操作并且发现信号量值不为正时，进程阻塞自身而不是忙等待。阻塞操作将一个进程放到与信号量相关的等待队列中，并且将该进程状态切换为等待状态。然后，控制转到CPU调度程序，以便选择执行另一进程。
signal：执行wakeup操作，将阻塞进程从等待状态改为就绪状态，然后，进程被添加到就绪队列。

typedef struct{
    int value; //信号量值
    struct process *list;//等待队列
}semaphore;

wait(semaphore *S){
    S->value--;
    if(S->value<0){
        add this process to S->list;
        block();//阻塞进程
    }
}

signal(semaphore *S){
    S->value++;
    if(S->value<=0){
        remove a process P from S->list;
        wakeup(P);//唤醒进程P
    }
}

wait和signal操作必须原子的执行，两种方法：

1. 禁用中断:在执行wait和signal操作期间禁用中断，以确保这两个操作作为一个原子操作执行。这种方法简单但可能影响系统的响应时间，因为它阻止了中断处理。适用于单处理器系统
2. 临界区问题：保证对于同一信号量，没有两个进程可以同时执行操作wait和signal。对于多处理器系统，通过基于硬件的解决方案或者基于软件的解决方案＋自旋锁来实现临界区保护。

这里定义的操作wait和signal，并没有完全取消忙等待，只是将忙等待从进入区移到临界区，wait和signal的临界区内通常比较短，几步不被占用，忙等待很少发生，而且所需时间很短

同步的典型问题

1. 生产者-消费者问题/有限缓存问题
   生产者-消费者问题是一个经典的同步问题，描述了两种进程（生产者和消费者）共享固定大小缓冲区的场景。生产者生成数据放入缓冲区，消费者从缓冲区取出数据消费。
   问题描述
   一个或多个生产者进程产生数据
   一个或多个消费者进程消费数据
   共享的有限大小缓冲区（通常为队列结构）
   需要保证：
   缓冲区满时生产者不能继续添加数据,生产者等待（wait(empty)）
   缓冲区空时消费者不能取出数据,消费者等待（wait(full)）
   对缓冲区的访问必须互斥,互斥锁（mutex）

   semaphore mutex = 1;     // 互斥信号量，初始为1，保证对缓冲区的互斥访问
   semaphore empty = N;     // 初始为缓冲区大小N，表示空槽数量
   semaphore full = 0;      // 计数信号量，初始为0，表示已填充槽数量
   
   Producer() {
       P(empty);
       P(mutex);
       // 生产物品
       V(mutex);
       V(full);
   }
   
   Consumer() {
       P(full);
       P(mutex);
       // 消费物品
       V(mutex);
       V(empty);
   }

2. 读者-写者问题
   多个读者（Reader）和写者（Writer）进程如何安全地共享一个数据资源（如文件、数据库、内存等）。
   读者：只读取数据，不会修改数据（允许多个读者同时访问）。
   写者：会修改数据（必须独占访问，不能与其他读者或写者同时访问）。

关键挑战
读者优先 vs 写者优先：
读者优先：只要有一个读者正在读，后续读者可以直接访问，可能导致写者饥饿（长时间无法写入）。
写者优先：如果有写者等待，新读者必须等待，避免写者饥饿。
公平策略：平衡读者和写者的访问，避免任何一方饥饿。

同步要求：
多个读者可以同时读（因为读操作不修改数据）。
写者必须独占访问（不能与其他读者或写者同时访问）。

semaphore mutex=1;//互斥信号量，保护read_count
semaphore rw_mutex=1;//读写互斥锁
int read_count=0;//计数信号量，当前读者的数量，初始化为0

//写者
writer(){
    while(true){
        wait(rw_mutex);//获取读写锁
        //写操作
        signal(rw_mutex);//释放读写锁
    }
}

//读者
reader(){
    while(true){
        wait(mutex);//// 获取 read_count 的锁
        read_count++;
        if(read_count==1) wait(rw_mutex);// 第一个读者需要获取 rw_mutex
        signal(mutex);// 释放 read_count 的锁

        //读操作

        wait(mutex);
        read_count--;
        if(read_count==0) signal(rw_mutex);// 最后一个读者释放 rw_mutex
        signal(mutex);
    }
}
//特点：只要有一个读者在读，后续读者可以直接进入，可能导致写者饥饿。

1. 哲学家就餐问题

如何在多个进程之间分配多个资源，而且不会发生死锁和饥饿

有 5 位哲学家围坐在一张圆桌旁，每人面前有一碗饭，每两人之间放一根筷子（共 5 根）。
哲学家只有两根筷子（左右各一根）才能吃饭，否则只能思考。
问题：如何设计算法，使得所有哲学家都能交替吃饭和思考，而不会出现死锁或饥饿？

关键挑战
死锁（Deadlock）：所有哲学家同时拿起左边的筷子，然后尝试拿右边的筷子，但由于没有筷子可用，所有人无限等待。
条件：

• 互斥（筷子一次只能被一个哲学家持有）
• 持有并等待（哲学家拿一根筷子，等待另一根）
• 非抢占（不能强行抢走筷子）
• 循环等待（每个哲学家都在等右边的人）

饥饿（Starvation）：某些哲学家可能一直拿不到筷子，无法吃饭。

信号量解决方案
通过wait操作试图获取相应的筷子，通过signal操作释放相应的筷子。

semaphore chopsticks[5];
for(int i=0;i<5;i++) chopsticks[i]=1;

Philosopher(int i){
    while(true){
        wait(chopsticks[i]);
        wait(chopsticks[(i+1)%5]);
        //吃饭
        signal(chopsticks[i]);
        signal(chopsticks[(i+1)%5]);
        //思考
    }
}

这种方案能够保证两位相邻的哲学家不能同时就餐，但是可能导致死锁。假设5位哲学家同时饥饿并拿起左边的筷子，所有筷子的信号量现在均为0，当每个哲学家试图拿起右边的筷子时，它的请求会被永远推迟。

补救措施：

• 允许最多只有4位哲学家同时坐在桌子旁

  semaphore coord=4;
  Philosopher(int i){
      while(true){
      wait(coord);
      wait(chopsticks[i]);
      wait(chopsticks[(i+1)%5]);
      //吃饭
      signal(chopsticks[i]);
      signal(chopsticks[(i+1)%5]);
      signal(coord);
      //思考
      }
  }

• 只有移位哲学家的两根筷子都可用时，他才能拿起它们（他必须在临界区内拿起两根筷子）
• 使用非对称解决方案：单号的哲学家先拿起左边的筷子，再拿起右边的筷子，双号的哲学家先拿起右边的筷子，再拿起左边的筷子。

解决死锁的方案，不一定能解决饥饿问题

管程

当程序员错误使用信号量或互斥锁来解决临界区问题时，容易导致各种错误，如死锁、饥饿、优先级反转等。为了简化并发编程，引入了管程（Monitor）的概念。将简单同步工具合并为高级语言结构。
管程（Monitor）是一种高级同步机制，用于管理多个线程/进程对共享资源的访问。
管程 = 共享变量 + 操作函数 + 同步机制
它封装了：
共享数据（如缓冲区、计数器）
操作共享数据的方法（如 produce()、consume()）
同步原语（如条件变量 Condition Variables）
特点：
互斥访问：任何时候只有一个线程能进入管程。
条件同步：线程可以等待某个条件成立（如缓冲区非空）。

管程的结构
(1) 基本组成
组成部分 作用
共享变量 存储需要保护的数据（如缓冲区）
初始化代码 初始化共享变量
操作方法 对共享数据的操作（如 put()、get()）
条件变量（Condition Variables） 用于线程等待和唤醒（如 notEmpty、notFull）
(2) 条件变量（Condition Variables）
wait()：当前线程挂起，释放管程锁，进入等待队列。
signal()（或 notify()）：唤醒一个等待的线程。
signalAll()（或 notifyAll()）：唤醒所有等待的线程。

“管程是一种机制，用于强制并发线程对一组共享变量的互斥访问（或等效操作）。此外，管程还提供了等待线程满足特定条件的机制，并通知其他线程该条件已满足的方法。”
这个定义描述了管程的两个主要功能：
互斥访问：管程确保多个线程对共享变量的访问互斥，即同一时间只有一个线程可以访问共享资源，以避免竞态条件和数据不一致性问题。
条件等待和通知：管程提供了等待线程满足特定条件的机制，线程可以通过条件变量等待某个条件满足后再继续执行，或者通过条件变量通知其他线程某个条件已经满足。

死锁

死锁：一组进程中每个进程都在等待只能由该组中另一进程引起的某个事件。

系统模型

一个系统拥有有限数量的资源需要分配到若干竞争线程。
资源可以分为多种类型，每种类型有一定数量的实例。如CPU周期、文件、I/O设备等。每种类型的所有实例是相同的。

线程使用资源前必须请求资源，使用后必须释放资源。线程可以请求执行指定任务所需的尽可能多的资源，但是不能超过系统的可用资源总数。
在正常情况下，线程按以下顺序使用资源：

• 申请：线程请求资源，如果申请不能立即被允许，申请线程必须等待直到它能获得该资源为止。
• 使用：线程对资源进行操作
• 释放：线程释放资源

死锁的特点

死锁的四个必要条件

1. 互斥：一次只能有一个线程可以使用该资源，如果另一线程申请资源，应等到该资源释放。
2. 占有并等待：一个线程因请求资源而阻塞时，对已获得的资源保持不放。/持有至少一个资源的进程正在等待获取其他进程持有的其他资源
3. 非抢占：资源不能被抢占，只能由持有它的线程自愿释放。
4. 循环等待：若干进程之间形成一种头尾相接的循环等待资源关系。多个事务之间形成了一个闭环，每个事务都在等待下一个事务所占有的资源。

循环等待条件意味着占有并等待条件，这四个条件并不完全独立，但分开考虑仍有一定意义。
四个条件必须同时成立才可能发生死锁。

资源分配图

有向图 描述死锁
节点集合V

• T：表示系统所有活动线程的集合，用圆表示
• R：表示系统所有资源类型的集合，用矩形表示
  边集合E
• 申请边Ti→Rj：表示线程Ti正在申请资源Rj
• 分配边Rj→Ti：表示资源Rj被线程Ti占用

如果分配图没有环，系统就欸有线程死锁。
如果分配图有环，若每个资源节点只有一个实例，则系统有死锁，若每个资源节点有多个实例，则系统不一定有死锁。

死锁处理方法

预防或避免、检测和恢复、忽略

死锁预防

死锁预防：通过确保至少有一个死锁的必要条件不成立，来防止死锁的发生。
缺点：设备利用率低、系统吞吐率低

• 互斥：资源不能被多个线程共享，只能被一个线程独占。
• 占有并等待：方案一是每个线程在执行前申请并获得所有资源，方案二是线程仅在没有资源时才可申请资源，在请求之前，必须释放已分配给进程的任何资源。两种方案都有缺点：资源利用率低、可能发生饥饿
• 非抢占：方案一（谦让型），如果持有某些资源的进程 P1 请求另一个无法立即分配给它的资源（必须等待），P1 当前持有的所有资源都将被释放/抢占，被抢占的资源将添加到进程正在等待的资源列表中，只有当进程 P1 可以重新获得其旧资源以及它所请求的新资源时，它才会重新启动。方案二（抢夺型），如果进程请求了一些资源，我们首先检查它们是否可用，如果资源不可用，并且被分配给正在等待其他资源的进程，从等待进程中抢占这些资源。
• 循环等待：对所有资源类型进行完全排序，而且要求每个线程按递增顺序来申请资源

死锁避免

死锁避免：要求操作系统事先得到有关线程申请资源和使用资源的额外信息

最简单最有用的死锁避免模型要求每个线程都应声明可能需要的每种类型资源的最大数量。基于这个先验信息，构造一个算法，动态检查资源分配状态，以确保永远不会有循环等待条件，资源分配状态由可用资源和已分配资源的数量以及进程的最大需求定义。

安全状态

如果系统能按一定顺序为每个进程分配资源，且避免死锁，那么这个系统的状态就是安全的。
即只有存在一个安全序列，系统才处于安全状态。
线程序列在当前分配下为安全序列是指对于每个Ti，Ti需要的资源不超过当前可用资源加上Tj（j<i）已分配资源之和。
在这种情况下，线程Ti需要的资源即使不能立即可用，也可用等待直到所有线程Tj释放资源。
如果没有这样的资源，系统就是非安全的。

死锁状态是非安全状态，非安全状态不一定是死锁状态。
安全状态不是死锁状态。

通过算法确保系统永远不会进入非安全状态。
两种：资源分配图算法、银行家算法

资源分配图算法

对于每种资源类型只有一个实例的资源分配系统。
引入需求边(Ti->Rj):表示线程Ti可能在将来某个时候申请资源Rj，用虚线表示，

边的变化
线程申请资源时，需求边变为申请边，释放资源时，分配边变为需求边。

系统资源的需求应实现说明。

假设线程Ti申请资源Rj，只有在将申请边(Ti->Rj)转换为分配边(Rj->Ti)后且不会导致图中形成环时，才能允许申请。
通过采用环检测算法检查安全性，需要n^2数量级的操作，n为线程数量。
如果没有环，那么资源的分配会使得系统处于安全状态，如果有环，那么系统处于非安全状态，在这种情况下，线程Ti应该等待资源申请。

银行家算法

前提：

• 每种资源类型具有多个实例
• 每个进程提前声明它可能需要的每种类型资源的最大数量
• 当进程请求资源时，它可能必须等待
• 当进程获取其所有资源时，它必须在有限的时间内返回这些资源

数据结构：
设n为进程数，m为资源类型数量

• Available：可用资源向量，长度为m，记录每种资源类型的可用数量
• Max：最大需求矩阵，n*m，记录每个进程对每种资源类型的最大需求
• Allocation：分配矩阵，n*m，记录每个进程已分配的每种资源类型的数量

• Need：需求矩阵，n*m，记录每个进程还需的每种资源类型的数量

• Work：工作向量，长度为m，每个元素 Work[j] 表示第 j 类资源当前可用的数量

• Finish：完成向量，长度为n，每个元素 Finish[i] 表示进程 i 是否已完成
• Request：请求向量

安全状态检测算法

1. 初始化 Work = Available，Finish[i]=false for i=0,1,…,n-1
2. 找到满足以下条件的进程 i：(a)Finish[i]=false (b)Need[i]<=Work 如果没有这样的i，跳到步骤4
3. Work=Work+Allocation[i]，Finish[i]=true 进程i在当前状态可以完成并释放资源 ， 跳回步骤2
4. 如果Finish[i]==true for i=0,1,…,n-1，则系统处于安全状态，否则处于非安全状态

资源请求算法

1. 如果Request[i]<=Need[i]，跳到步骤2，否则，触发错误条件，因为进程请求超出最大声明
2. 如果Request[i]<=Available，跳到步骤3，否则，进程必须等待，因为可用资源不足
3. 假设将请求的资源分配给进程i，更新状态：
   Available=Available-Request[i],
   Allocation[i]=Allocation[i]+Request[i],
   Need[i]=Need[i]-Request[i],
4. 调用安全状态检测算法，如果安全，资源分配给进程i，如果不安全，进程必须等待，并恢复旧的资源分配状态

死锁检测

如果允许系统进入死锁状态，系统应提供

• 检测算法：检查系统状态以确定是否发生死锁
• 恢复算法：一种从死锁中恢复的算法

两种检测算法

• 等待图算法：
  每种类型的资源节点只有一个实例
  从相应的资源分配图生成等待图，删除资源节点并合并对应的边，结点为进程，Pi->Pj表示Pi等待Pj
  定期调用在图中搜索环的算法
• 检测算法：每种类型的资源节点有多个实例。类似于安全检测算法

死锁恢复

进程终止

• 终止所有死锁进程
• 一次终止一个进程，直到消除死锁

通过采取资源抢占来消除死锁，需要处理三个问题

• 选择牺牲进程，最大限度的降低代价
• 回滚，返回到某个安全状态，重新启动该状态的进程
• 饥饿：相同的进程可能始终被选为受害者，解决：1一个进程可以被选择为有限次数的受害者 2在选择牺牲对象时在成本系数中包含回滚次数

内存管理

背景

CPU直接访问的通用存储只有内存和CPU核内置的寄存器。执行指令及指令使用的数据应当先位于这些可直接访问的存储设备。

内存地址保护
需要保护操作系统不被用户进程访问，保护用户进程免受他人的攻击
首先需要确保每个进程都有单独的内存空间，需要确定进程合法的地址范围，需要确保进程只能访问这些合法地址

通过两根寄存器提供这种保护

• 基址寄存器：含有最小的合法的物理内存地址
• 界限寄存器：指定了范围的大小
  内存空间保护的实现是通过CPU硬件对在用户模式下产生的地址与寄存器的地址进行比较来完成的。

内存管理的种类

1. 物理内存中的整个程序
   • 连续内存分配：固定大小的连续分区、动态连续分区
   • 非连续内存分配：分页、分段、段页式
2. 物理内存中的部分程序（虚拟内存）：请求调页、请求段页

地址绑定

通常程序作为二进制的可执行文件存放在磁盘上。为了运行，程序必须调入内存并放置在进程的上下文中，以便有资格在可用的CPU上执行。当进程执行时，它访问内存的指令和数据。最终，该进程终止，其内存被回收以供其他进程使用。
地址绑定是指将程序中的逻辑地址（如变量名、函数名、指令地址等）转换为计算机内存中的物理地址的过程。在不同的阶段，地址绑定可能发生在不同的时间，这取决于操作系统的内存管理策略。

地址绑定的三种时机

• 编译时：程序在编译时确定所有内存地址。如果程序运行时的内存起始地址发生变化，必须重新编译。
• 加载时：程序在装入内存时才确定物理地址。如果程序被换出内存后重新装入，地址可能不同。
• 执行时：程序运行时，CPU 访问指令或数据时才进行地址转换。需要硬件支持（如MMU + 基址寄存器/页表）。大多数操作系统采用

逻辑地址空间与物理地址空间

逻辑地址（虚拟地址）：CPU生成的地址
物理地址：内存单元的地址，即加载到内存地址寄存器的地址

编译时绑定和加载时绑定的方法生产的逻辑地址和物理地址相同，执行时绑定方案生成的逻辑地址和物理地址不同。
由程序所生成的所有逻辑地址的集合称为逻辑地址空间，这些逻辑地址对应的所有物理地址的集合称为物理地址空间。

从虚拟地址到物理地址的执行时映射是由内存管理单元MMU的硬件设备完成的。

交换

可以将进程暂时从内存中交换到后备存储，然后带回内存继续执行

连续内存分配

内存分为两个区域：一个用于操作系统，另一个用于用户进程
连续内存分配是一种内存管理方式，要求进程的整个地址空间在物理内存中连续存放。

内存保护

• 界限地址寄存器：含有逻辑地址的范围值
• 重定位寄存器：含有最小的物理地址

CPU生成的逻辑地址应在界限地址寄存器规定的范围内，MMU通过动态地将逻辑地址加上重定位寄存器的值来实现映射，映射后的地址再发送到内存中。

内存分配-固定分区/可变分区

固定大小的连续分区（固定分区）
在系统生成时将内存划分为多个固定大小的分区，每个分区可以只包含一个进程
优点：易于实施、开销小
缺点：内碎片（分配的内存可能大于请求的内存），固定的进程数

可变分区
操作系统保留一个表，只是哪些部分的内存可用，哪些已被占用。分区大小、分区始址
分区是动态创建的，每个进程都可以加载到与该进程大小完全相同的分区中。
孔（可用内存块）:最初，所有内存都可用于进程，并被视为一个孔，当进程到达，从一个孔中分配内存以精确容纳它，其余的返回形成一个较小的孔
随着进程的到达和终止，各种大小的空洞散布在整个内存中
当进程终止时，释放内存，如果新孔与其他孔相邻，则合并孔
可用内存块时分散在内存里不同大小的孔的集合。

从一组可用孔中选择一个可用孔的最常办法包括，分配算法，用于满足来自自由孔列表的大小为 n 的请求；

• 首次适应：分配首个足够大的孔
• 最优适应：分配最小的足够大的孔，此策略会产生可能被浪费的最小剩余孔
• 最差适应：分配最大的孔，此策略会产生可能有用的最大剩余孔

碎片

内碎片：分配的内存可能略大于请求的内存，已分配给进程但未被使用的内存，即分配的内存块比进程实际需要的更大，导致剩余部分被浪费。
发生在固定大小的内存分配策略 中（如固定分区、分页系统）
外碎片：内存中零散的空闲块，它们总和足够大，但由于不连续，无法分配给新进程
发生在动态内存分配 中（如动态分区、分段系统）

外碎片解决方案

• 压缩：移动内存内容，以便将所有空闲空间合并成一整块。只有当重定位是动态的，并且在执行时才进行时，才能进行压缩。并且开销很大。
• 允许逻辑地址空间是不连续的：分页

分页

一种允许进程的物理地址空间不连续的内存管理方案，避免了外部碎片和相关的压缩需求。

基本方法

帧、块：将物理内存分为固定大小的块
页：将逻辑内存分为同样大小的块
当需要执行一个进程时，其页从文件系统或备份存储源等源处加载到内存的可用帧。

CPU生成的每个地址分为两部分；

• 页码p：用作每个进程页表的索引。页表中包含物理内存每个帧的基址（f：块号）
• 页偏移d：被引用帧中的位置，与基址 （f：块号） 组合，以定义发送到内存单元的物理内存地址

物理地址：

• 帧号f
• 偏移量d

MMU将CPU生成的逻辑地址转换为物理地址的步骤如下：

1. 从逻辑地址提取页码p，作为页表的索引
2. 根据索引，从页表中提取对应帧码f
3. 将逻辑地址中的页码p替换为帧码f，帧码和偏移量构成物理地址

页的大小由硬件决定，从4KB到16MB不等，选为2的幂，可用方便地将逻辑地址转换为页码和页偏移。
如逻辑地址空间为2^m,页大小为2^n,则页码p=逻辑地址的高m-n位，页偏移d=逻辑地址的低n位。

分页本身是一种动态的重定位。每个逻辑地址由分页硬件绑定为你某个物理地址。采用分页类似于采用一组基址（重定位）寄存器，每个基址对应着一个空闲帧。
分页方案不会产生外部碎片，但是有内碎片问题

操作系统的责任
必须意识到用户进程在用户空间中运行，所有的逻辑地址需要映射搭配物理地址。
必须为每个进程维护页表的副本，当要为进程分配 CPU 时，CPU 调度程序将使用副本来定义硬件页表 。分页会增加上下文切换时间
必须了解物理内存的分配详细信息，包括哪些帧已分配、哪些帧空着、总共有多少帧等，这些信息保存在帧表（主存分块表）中

帧表（主存分块表）
每个条目对应着一个帧，表示该帧是空闲的还是已占用的，如果是已占用的，同时显示是被哪个或哪些进程的哪个页占用。

硬件支持

页表的硬件实现

• 页表寄存器：如果页表足够小（如少于 256 个条目），可用。但是这种方法增加了上下文切换的时间，而且大部分页表都很大
• 保存在主存中，页表基址寄存器(PTBR)；指向页表，当进程切换时，加载页表只需要更改 PTBR，从而大大减少了上下文切换，但是每个数据/指令访问都需要两次内存访问（一次是页表，一次是数据/指令）
• TLB/转换后援寄存器/联想寄存器/快表：一种特殊的快速查找硬件高速缓存，解决两次内存访问问题，仅包含少量页表条目，支持并行搜索。如果 TLB 中没有条目，则必须访问主存中的页表，这称为 TLB 未命中，此时需要进行地址转换访问内存页表，得到帧码后再次访问内存，可以将页码和帧码添加到TLB中，以便将来使用。如果TLB条目已满，需要根据替换策略选择一个替。
  某些 TLB 在每个 TLB 条目中存储地址空间标识符 （ASID）
  TLB 可以同时包含多个不同进程的条目
  ASID 唯一标识每个进程，以便为该进程提供地址空间保护
  如果 TLB 不支持单独的 ASID，则每次选择新页表时，都必须刷新 TLB

有效访问时间EAT
命中率：在TLB中找到对应所需页码的次数的百分比
有效访问时间=命中率访问时间+（1-命中率）（访问时间+TLB未命中时间）

保护

分页环境下的内存保护是通过与每个帧关联的保护位来实现的。通常，这些位保存在页表中。

• 有效/无效位：与页表中的每一条目相关联。valid表示关联的页面位于进程的逻辑地址空间中，因此是合法页面。invalid表示该页不在进程的逻辑地址空间中。
• 读写/只读/仅执行

共享页

共享代码
在进程（即文本编辑器、编译器、窗口系统）之间共享的只读（可重入）代码的一个副本。
共享代码必须出现在所有进程的逻辑地址空间的同一位置

私有代码和数据
每个进程都保留代码和数据的单独副本
私有代码和数据的页面可以出现在逻辑地址空间中的任何位置

页表结构

问题：页表可能过大
对于32位CPU，页大小4k=2^12，页表大小为2^32/2^12=1M个条目，每个条目4B，则页表大小为4MB
每个进程的页表可能最多需要4M的物理内存，4M/4k=1024个帧，即每个页表可能需要多达1k个物理块，不适合在主内存中连续分配页表。

解决方案

• 分层页表
  将逻辑地址空间分解为多个页表
  两级页表（向前映射页表），对于32位系统，分为10位页码，10位页偏移，12位偏移量
  而对于64位系统，分层页表不适当，分得少了页表仍然很大，分的多了内存访问开销太大
• 哈希页表
  对于大于32位地址空间的常用方法是使用哈希页表，采用虚拟页码作为哈希值。哈希页表的每一个条目都包括一个链表，该链表的元素哈希到同一位置（该链表用来解决处理碰撞）。每个元素由三个字段组成：虚拟页码、映射的帧码、指向链表内下一个元素的指针。
  该算法的工作如下：用虚拟地址的虚拟页码哈希到哈希表。用虚拟页码与链表内的第一个元素的第一个字段相比较。如果匹配，那么相应的帧码（第二个字段）就用来形成物理地址；如果不匹配，那么与链表内后续结点的第一个字段进行比较，来查找匹配的页码。
• 倒置页表
  标准页表的缺点：
  • 每个进程都有一个关联的页表
  • 每个页表可能包含数百万个条目
  • 这些表可能会消耗大量物理内存
    对于倒置页表，系统中只有一个页表，只有对于每个真正的内存页或帧，倒置页表才有一个条目。每个条目包含保存在真正内存位置上的页的虚拟地址，以及拥有该页进程的信息。
    由于一个倒置页表通常包含多个不同的映射物理内存的地址空间，通常要求它的每个条目保存一个地址空间标识符。
    减少存储每个页表所需的内存，但增加发生页引用时搜索表所需的时间；
    导致共享内存困难。

分段

分段是一种内存管理方案，支持用户查看内存。
用户对程序的视图：

• 程序是段的集合，段是一个逻辑单元，如主程序，函数，数据，堆栈等
• 如何分段，由程序员/编译器
• 逻辑地址由段号和段内偏移量组成
• 段表：将二维地址映射到一维物理地址，每个表条目都有base（包含段在内存中驻留的其实地址）和limit（指定段的长度）
• 段号s用作段表中的索引，偏移量d介于0和段限制之间，如果无效，为非法内存访问，如果有效，则base+d->物理地址

虚拟内存

虚拟内存技术允许执行进程不必完全处于内存中。这种方案的一个主要优点在于程序可以大于物理内存；可以同时运行更多程序；将每个用户程序加载或交换到内存中所需的 I/O 更少，因此程序将开始运行得更快。

虚拟内存将用户逻辑内存与物理内存分开。

虚拟地址空间 就是进程如何在内存中存放的逻辑（虚拟）视图。
其中包括称为稀疏地址空间的孔
允许更高效地创建流程
允许多个进程共享地址空间

虚拟内存可通过如下方式实现：请求页式、请求段式

请求调页/请求页式

虚拟内存系统中常用的一种技术，仅在需要时将页面引入内存，类似于具有交换的分页系统，但进程驻留在外存上。

基本概念：
仅在需要时将页面引入内存，需要的I/O更少，需要更少的内存，更多用户（进程/线程）

硬件支持：页表，通过有效/无效位区分合法/非法内存访问，valid表示相关联的页面既合法有在内存中，invalid表示非法或不在内存中；辅助内存，高速磁盘、交换空间，保留当前不在内存中的页面

缺页错误：访问标记为无效的页面会导致缺页中断，操作系统处理这种缺页错误的过程如下：

1. 检查这个进程的内部表（PCB），来确定该引用是有效的还是无效的内存访问，如果无效，则终止进程abort，如果有效但是尚未调入页面，不在内存中，进行调入步骤2
2. 找到一个空闲帧
3. 将所需的页面交换到刚分配的空闲帧
4. 修改进程的内部表和页表，以指示该页现在处于内存中
5. 重新启动被陷阱中断的指令。

纯请求调页：开始执行一个没有内存页面的进程

指令复执；请求调页的关键要求是在缺页错误后重新启动任何指令的能力。保存被中断的进程状态，应当能够在完全相同的位置和状态下，重新启动进程，只不过现在所需的页面已经在内存中并且是可以访问的。
在大多数情况下，这个要求可以满足。但是任何内存引用都可能发生页面错误，如果在获取指令时出现了缺页错误，那么可以再次获取指令；如果在获取操作数时出现了缺页错误，我们必须再次获取并解码指令，然后再次获取操作数。
重启指令的困难
如果源或目标跨越页面边界，则在移动部分完成后可能会发生页面错误
如果源块和目标块重叠，则源块可能已被修改，在这种情况下，我们不能简单地重新启动指令
解决方案

1. 提前尝试访问两块的两端。如果会出现缺页错误，就让它在这一步发生（在任何内容被修改之前）
2. 使用寄存器保存被覆盖位置的值，如果存在页面错误，所有的旧值都会写回

需求分页的性能
内存的有效访问时间EAT
如果没有页面错误，有效访问时间=内存访问时间；如果由页面错误，必须首先从磁盘读取相关页面，然后访问所需的单元，有效访问时间很长
设p位缺页率，有效访问时间EAT=p缺页错误时间+(1-p)内存访问时间；
如果p=0，无页面错误；p=1，每个引用都是错误的

写时复制

写时复制（Copy-on-Write）是一种用于创建进程的技术，其中每个进程最初都共享相同的内存副本，这些共享页面标记为写时复制。当进程需要修改内存时，会创建该内存的副本，然后在该副本上进行修改。因此，写时复制可以显著减少创建进程所需的内存。
允许更高效的创建进程，因为仅复制修改后的页面
fork()
vfork()：采用vfork时，父进程被挂起，子进程使用父进程的地址空间，vfork不采用写时复制，如果子进程更改了父进程地址空间的任何页面，那么这些修改的页面对于恢复的父进程也是可见的。效率高，但是危险，需要确保子进程不会修改父进程的地址空间时使用。如当子进程创建后立即调用exec时，可使用vfork。

页面置换

提高了多道程序的程度，那么就可能导致过度分配内存。
内存的过度分配表现为：当用户程序正在执行时，可能发生缺页错误，操作系统确定所需页面的磁盘位置，但是缺发现空闲帧列表没有空闲帧，所有内存都在使用。
此时，操作系统可以

• 终止进程
• 换出进程，释放其所有帧，降低多道系统级别
• 页面置换

基本页面置换

如果没有空闲帧，那么就查找当前没有在使用的一个帧，并释放它。可以这样释放一个帧：将其内容写道交换空间，并修改页表（和所有其他表），以表示该页不在内存中。现在可以使用空闲帧来保存进程出错的页面。
步骤：

1. 找到所需页面的辅助存储位置
2. 查找空闲帧，如果有，就使用它；如果没有，就使用页面置换算法选择一个牺牲帧，将牺牲帧写入辅助存储，并修改对应的页表和帧表
3. 将所需页面读入新的空闲帧，修改页表和帧表
4. 从发生缺页错误的位置继续进程

如果没有空闲帧，那么需要两次页面传输，一个调出，一个调入。加倍了缺页错误处理时间，并相应的增加了有效访问时间。
解决方法：
采用修改位(modify bit)（或脏位(dirty bit)）来减少此开销。每个页面或帧都有一个修改位，每当页面中任何字节被修改时，修改位会由硬件来设置。
如果修改，进行换入换出
如果没有修改过，只需要换入。

为实现请求调页，需要两种算法

• 帧分配算法：确定为每个进程分配多少帧
• 页面置换算法：决定要选择和替换的页面

如何评估页面置换算法：通过在特定的内存引用字符串上运行它并计算页面错误的数量来评估
引用串：内存引用的串
为减少数据数量，1.只考虑页码而不是完整的地址；2. 如果我们引用了页面 p，那么任何紧随其后的对页面 p 的引用都不会导致页面错误。
根据上述两个事实将地址序列缩减为引用串

为了确定特定引用串和页面置换算法的缺页错误数量，还需要知道可用帧的数量。随着可用帧数量的增加，缺页错误的数量会减少。

FIFO页面置换

为每个页面记录了调到内存的时间。当必须置换页面时，选择最旧的页面。
通过FIFO队列管理所有的内存页面，无需严格记录时间。
特定：易于理解和实施，性能并不总是最好的
被置换的页面可能是很早使用现在不再使用的初始化模块，也可能是仍在被使用，一旦置换出去，几乎立即发生缺页错误，反而会增加缺页错误率，这是Belady异常的一个例子。

最优页面置换（OPT）

置换最长时间不会使用的页面。
特点：最优的页面错误率；没有Belady异常；难以实现；可用用于比较

LRU页面置换

置换最近最少使用的页面。
使用最近的过去作为不远将来的近似，那么可以置换最长时间未使用的页面。
没有Belady异常
实现：

• 计数器
  每个页面条目都有一个计数器
  每次引用该页时，将clock复制到计数器中
  每个内存引用的时钟递增
  需要时，替换具有最小时间值的页面
• 堆栈
  使用页码堆栈，每当页面被引用时，它就从堆栈中移除并放在顶部。这样最近使用的页面总是在堆栈的顶部，最近最少使用的页面总是在底部。
  因为必须从堆栈的中间删除条目，最好通过具有首指针和尾指针的双向链表来实现这种方法。

如果没有额外的硬件，计数器和堆栈都是不可能的。每次内存引用都必须更新时钟域或堆栈，如果每次引用都采用中断进行更新，那么它会使内存引用至少慢10倍，进而使进程运行慢10倍。

近似LRU页面置换

硬件支持——引用位
引用位于页表中的每个条目相关联，最初等于0
引用页面时，硬件将页面的参考位设置为1

额外引用位算法

在内存中位表中的每个页保留一个8位字节
定时器中断会定期（每 100 毫秒）将控制权转移给操作系统。操作系统将参考位移动到页面的 8 位字节的高位，将其他位右移一位，并丢弃最低位。这8位字节就包含最近8个时间周期内页面使用情况。
如果我们将这些 8 位字节解释为无符号整数，则编号最小的页面是 LRU 页面，可以替换它。

第二次机会算法

选择了一个页面时，就需要检查其引用位，如果值为0，就直接置换此页面；如果引用位设置为1，就给此页面第二次机会，将引用位设置为0，并继续选择下一个FIFO页面。
实现：页面的循环队列

增强的二次机会算法

（引用位，修改位）

1. （0，0）：最近没有使用且没有被修改——最佳置换页面
2. （0，1）：最近没有使用但被修改过的页面——不太好的置换，因为在置换之前需要将页面写出
3. （1，0）：最近使用过但没有修改的页面——可能很快再次使用
4. （1，1）：最近使用过且修改过的页面——可能很快再次使用，并且在置换之前需要将页面写出到磁盘

基于计数的页面置换

为每个页面的引用次数保存一个计数器

1. LFU最不经常使用
2. MFU最经常使用

页面缓冲算法

系统保存一个空闲帧池，当出现缺页错误时，选择牺牲者，所需页面读到缓冲池中的空闲帧，牺牲帧稍后写出。
允许进程尽快启动
尽可能减少修改的页面数量

帧分配

在各种进程之间分配固定数量的可用内存

帧的最小数
我们必须有足够的帧来保存任何单个指令可以引用的所有不同页面。
由计算机架构定义

帧的最大数
由可用物理内存的数量决定
分配算法；固定分配 优先级分配

固定分配

• 平均分配：n个进程分配m个帧，每个进程得到m/n个帧
• 按比分配；根据进程虚拟内存大小占比分配

优先级分配

页面置换算法可用分为两大类：

• 全局置换：允许一个进程从所有帧的集合中选择一个置换帧，而不管该帧是否已分配给其他进程。可以增加分配的帧数，更高的系统吞吐量；无法控制其页面错误率
• 局部置换：每个进程只从其字节分配的帧中进行选择。无法增加分配的帧数；不受外部环境影响

抖动

如果一个进程没有足够的帧，进程很快就会出现页面错误，必须替换掉某些页面，但这些页面正在只用中，它又必须立即替换再次需要的页面。很快又会一次又一次的出现页面错误，替换它马上调回的页面。
抖动：高度页面调度活动，一个进程的调页时间多于执行时间，那么这个进程就在抖动

抖动的原因
如果 CPU 利用率较低，OS 会引入一个新进程来提高多程序编程的程度
进程将从其他进程中夺走帧（通过全局替换）
但是这些进程也需要这些页面，因此它们也会导致错误
进程排队等待分页设备，分页设备正忙于换页和换出
CPU 利用率降低 ➔抖动

防止抖动的方法

1. 工作集策略
   根据需要为进程分配尽可能多的帧
   局部模型：当进程执行时，它会将一个局部移动到另一个局部。局部是最近使用页面的一个集合。一个程序通常是由多个不同的可能重叠的局部组成。
   如果进程具有足够的帧来包含其位置，则它会平稳运行。
   工作集模型是基于局部性假设。采用参数Δ定义工作集窗口，是最近Δ个页面引用的集合。如果一个页面处于活动状态，那么它还在工作集中。如果它不再使用，在最后一次引用的Δ时间单位后，会从工作集中删除。
   工作集是程序局部的近似。
   工作集的精度取决于Δ的选择。如果Δ太小，不能包含整个局部；太大，可能包含多个局部。

   计算系统中每个进程的工作集大小
   计算帧的总需求。如果总需求小于总可用帧，则不会发生抖动，如果大于可用帧，则会发生抖动。

1. 缺页错误频率PFF方案

确定可接受的缺页错误率，如果实际错误率太高，则可再为进程分配一帧；如果太低，则回收一帧。

内存映射文件

内存映射
通过将磁盘块映射到内存中的页面，将文件 I/O 视为常规内存访问
最初使用需求分页将文件读取 （到内存中）。
文件的页面大小的部分将从文件系统读取到物理页面。
对文件的后续读取/写入被视为普通内存访问。
通过内存而不是 read（） write（） 系统调用来处理文件 I/O，从而简化文件访问
还允许多个进程同时映射同一文件，以允许共享内存中的页面

分配内核内存

内核内存
与用户内存区区别对待
从可用内存池分配

内核内存分配的两种策略

• 伙伴系统
  从由物理上连续的页面组成的固定大小的段分配内存
  使用 2 的幂分配器分配的内存
  优点：合并（可以将相邻伙伴快速组合以形成更大的分段）
  缺点；内碎片
• slab分配
  每个slab由一个或多个物理连续的页面组成。
  每个缓存由一个或多个slab组成
  每个内核数据结构都有一个缓存
  如果slab中充满了已使用的对象，则从孔slab中分配下一个对象。如果没有空slab，则分配新slab
  优点：无碎片；快速满足内存请求

文件系统

文件系统由两部分组成：文件集合，每个文件存储相关数据；目录结构，用于组织系统内的所有文件并提供文件信息。

文件概念

主存通常太小，无法永久容纳所有数据和程序。计算机系统使用辅助存储来备份主存。这些辅存（磁盘、磁带、光盘、软盘、闪存）在许多方面都有不同，操作系统提供了信息存储的统一逻辑视图，对存储设备的物理属性加以抽象，从而定义逻辑存储单位——文件。
文件由操作系统映射到物理设备。这些设备通常是非易失性的。
文件是记录在外存上的相关信息的命名组合。用户角度看，文件是逻辑外村的最小分配单元，数据只有通过文件才能写到外存。通常，文件表示程序和数据。

文件类型

内容上：数据文件、程序文件
形式上：自由格式、严格格式

文件属性

• 名称：人类可读的符号化文件名
• 标识符：唯一标记标识文件系统中的文件，非人类可读
• 类型：支持不同类型的系统需要
• 位置：指向设备与设备上文件位置的指针
• 大小：当前文件大小
• 保护：访问控制信息确定谁能进行读取、写入、执行
• 时间戳和用户标识：用于保护、安全和监控
  所有文件的信息都保存在目录结构中，该目录结构与文件本身位于同一设备。通常，目录条目由文件名称及其唯一标识符组成。

  文件操作

• 创建文件：分配文件空间并分配目录条目
• 打开文件：所有操作（除了创建和删除），都需要先打开文件。如果成功，open()将返回一个文件句柄，该句柄在其他调用中用作参数。
• 写文件：使用一个系统调用指定打开的文件句柄和要写入文件的信息。根据文件名称，搜索目录以查找文件位置。系统保留写指针，用于指向需要进行下次写操作的文件位置。每当写操作时，写指针必须更新。
• 读文件：使用一个系统调用指定打开的文件句柄和需要文件的下一个块应该放在内存哪里。找到相关条目，保留读指针，指向下一次读取操作的文件位置。读指针和写指针可使用相同的当前文件位置指针。
• 重新定位文件：打开文件的当前文件位置指针被重新定位到给定值。
• 删除文件：查找目录条目并释放所有文件空间并擦除目录条目。
• 截断文件：擦除文件的内容，但保留其长度以外的属性。

辅助操作
大多数文件作都涉及在目录中搜索与命名文件关联的条目，为避免这种不断的搜索，许多系统要求在首次使用文件之前进行系统调用open()。操作系统有一个打开文件表(open-file table)，用于维护所有打开文件的信息，当请求文件操作时，可通过该表的索引指定文件，而不需要搜索，当文件最近不再使用时，进程关闭它，操作系统从打开文件表中删除相关条目，可能会释放锁。
每个打开的文件具有以下关联信息：

• 文件指针：指向上次读/写位置的指针，对于已打开文件的每个进程是唯一的
• 文件打开计数：该文件被打开的次数 — — 允许在最后一个进程关闭打开文件表时从打开的文件表中删除数据
• 文件位置：保存在内存中
• 访问权限：每个进程的访问模式信息

文件类型

如果操作系统识别出文件的类型，它就可以以合理的方式对文件进行操作。
实现文件类型的常见技术是将类型作为文件名的一部分。文件名分为名称和扩展两部分，通常由句点分开。
操作系统使用扩展名来只是文件类型和可用于文件的操作类型。
可执行：exe、com、bin或无 可运行的机器语音程序
对象：obj、o 已编译、机器语言、未链接的
源代码：c、cc、java 各种语言的源代码
批处理：bat、sh 命令到命令解释器

文件结构

文件类型可用于指示文件的内部结构。
某些文件必须符合操作系统可以理解的必需结构
一些操作系统将这个想法扩展到一组系统支持的文件结构中
操作系统支持多种文件格式的缺点：庞大笨重

所有操作系统必须至少支持一种结构——即可执行文件的结构，以便系统能够加载和运行程序。

内部文件结构

磁盘系统通常具有明确定义的块大小
所有磁盘 I/O 都以一个块为单位执行
物理记录的大小不太可能刚好匹配期望的逻辑记录的长度。通常将多个逻辑记录包装到物理块中。打包可由用户的应用程序或操作系统来完成。所有文件系统都有内碎片，块越大，内碎片也越大。

访问方法

文件存储信息，使用时，必须访问这种信息，并将其读到计算机内存。文件信息可按多种方式来访问。

顺序访问

文件信息按顺序加以处理。目前最常见。基于文件的磁带模型。
读操作读取文件的下一部分，并且自动前移文件指针以便跟踪I/O位置。
写操作会在文件的结尾附加内容，并前移到新写材料的末尾。

直接访问

文件由固定长度的逻辑记录组成，以允许程序按任意顺序快速读取和写入记录。
基于文件的磁盘模型。磁盘可以允许对任何文件块的随机访问。
对于直接访问，文件可以作为块或记录的编号序列。
对于大量信息的立即访问，直接访问文件极为有效。
对于直接访问方法，必须修改文件操作以便包括快好作为参数。
read(n)
write(n)
用户提供给操作系统的块号通常为相对块号，是相对于文件开头的索引。

其他访问

通常涉及创建文件索引。索引包括各块的指针。为了在文件中查找记录，首先搜索索引，然后根据指针直接访问文件并且找到所需记录。
对于大文件，索引文件本身可能变得太大而无法保存在内存中。一种解决方案是为索引文件创建索引。主索引文件包含指向辅助索引文件的指针，而辅助索引文件包含指向实际数据项的指针。

目录结构

目录可以视为符号表，以文件名称转换成目录条目。
对目录执行的操作：

• 搜索文件：搜索目录结构，以查找特定文件的条目
• 创建文件：创建新的文件，添加到目录
• 删除文件：从目录中删除文件
• 遍历目录：遍历目录内的文库，以及目录内每个文件的目录条目的内容
• 重命名文件：当文件内容和用途改变时，名称也应改变。重命名文件也允许改变其在目录结构中的位置。
• 遍历文件系统：访问每个目录和目录结构内的每个文件。

单级目录

所有文件包含在同一目录中。
命名问题：所有文件必须具有唯一的名称。

两级目录

每个用户都有自己的用户文件目录UFD。
系统的主文件目录MFD按用户名或账户索引，每个条目都指向一个UFD。
对于不同的用户，可以具有相同的用户名。只要每个UFD中的所有文件名是唯一的。
缺点：将一个用户与另一个用户隔离，在需要用户共享时，十分困难。
将两级目录视为高度为2的树，树根为MFD，树根的直接后代为UFD，UFD的直接后代为文件本身，文件为树的叶。
指定用户名和文件名定义了在树中从根到叶的路径。因此，用户名和文件名定义了路径名。系统内每个文件都有一个路径名。
指定文件的卷需要另外的语法。

树形目录

允许用户创建自己的子目录并相应地组织文件。
一个目录或子目录可以包含一组文件或子目录。
目录只是另一个文件，但它以特殊方式处理。每个目录条目都有一位来将条目定义为文件(0)或子目录(1)。
每个进程都有一个当前目录。当前目录包括进程当前感兴趣的大多数文件。
优点：高效搜索、分组功能
缺点：难以在不同用户之间共享文件

无环图目录

允许目录共享子目录和文件。同一文件或子目录可出现在两个不同的目录中。无环图是树形目录方案的扩展。
实现共享的几种方法

1. 创建一个名为链接的新目录条目
   链接实际上是另一文件或子目录的指针。链接可以用绝对路径或相对路径的名称来实现，当引用文件时，就搜索目录。如果目录条目被标记为链接则真实文件的名称包括在链接信息中。采用该路径名来解析链接，定位真实文件。链接可通过目录条目格式加以标识，它实际上是具有名称的间接指针。在遍历目录树时，操作系统忽略这些链接以维护系统的五环结构。
2. 在两个共享目录中复制有关它们的所有信息。
   复制目录条目使得原件和副本难以区分
   在修改文件时要维护一致性

无环图结构比树结构更灵活，但更复杂。
潜在问题：
不同的文件名可以指向相同的文件，在遍历整个文件系统时，可能会多次访问同一文件。
删除文件时可能会留下悬空指针，而后这些悬挂指针可能会指向其他文件。对于符号链接实现共享的系统中，如果文件被删除，1可以搜索其悬空链接并删除它们（搜索很昂贵）2可以保留链接，知道尝试使用它们时视为非法链接
另一种解决方案，保留文件，直到它所有的引用都被删除。需要保留对文件的所有引用的列表。文件引用列表的可变和较大。文件引用列表 —→引用计数

通用图目录（有环）

略 P385

文件系统挂载

挂载
必须先挂载文件系统，然后才能访问它
挂载点
未挂载的文件系统可以挂载在挂载点
挂载的过程可以理解为将一个文件系统的根目录“嫁接”到当前文件系统层次结构中的某个目录上。这个目录称为挂载点（mount point），一旦文件系统被挂载到该目录，用户访问该目录时实际上访问的是挂载的文件系统中的内容。

例如，将一个新的存储设备（如USB驱动器）挂载到系统中的/media/usb目录后，用户访问/media/usb时即在访问USB驱动器中的文件。

文件共享

对于多用户系统，文件共享是可取的。
文件共享存在的问题：允许多个共享文件，对于共享、命名、保护提出要求；将文件扩展到多个文件系统，包括远程文件系统；对共享文件一致性语义的动作冲突
对于多用户，要实现共享和保护，系统必须维护更多的文件和目录属性：
所有者，用户ID标识用户，用户可以更改文件并授予访问权限
组，组ID允许用户位于组中，从而允许组访问权限
远程文件系统
在分布式系统上，文件可以通过网络共享

保护

文件的所有者应该能控制文件能做什么，被谁来使用
访问类型

• 读
• 写
• 执行
• 附加
• 删除
• 列表
• 属性更改

访问控制

解决保护问题最常见的方法是根据用户身份控制访问。
为每个文件和目录关联一个访问控制列表（ACL）指定每个用户的名称及允许访问的访问类型。

文件系统实现

文件系统结构

磁盘提供维护文件系统的大量辅助存储。
优点：

• 磁盘可以原地重写。从磁盘上读取一块，修改该块，并写回原来的位置
• 磁盘可以直接访问所包含的任何信息块。可以简单地按顺序或随机访问文件。从一个文件切换到另一个文件只需移动读写磁头，并且等待磁盘旋转。

内存和磁盘之间的I/O传输以块而不是字节为单位执行。每块具有一个或多个扇区，扇区通常为512字节。

文件系统驻留在二级存储（磁盘）上，它允许轻松存储、定位和检索数据，从而提高对磁盘的高效便捷访问。
它提出了两个截然不同的设计问题

• 定义文件系统应该如何呈现给用户，设计如何定义文件及其属性、所允许的文件操作、组织文件的目录结构。
• 创建算法和数据结构，以便将逻辑文件系统映射到物理外存设备。

文件系统本身通常由许多不同的层组成。每层利用更低层的功能创建新的功能，以用于更高层的服务。
应用程序->逻辑文件系统->文件组织模块->基本文件系统->I/O控制->设备

• 逻辑文件系统：管理元数据信息。元数据包括文件系统的所有结构，而不包括实际数据（或文件内容）。逻辑文件系统管理目录结构，以便根据给定文件名称为文件组织模块提供所需信息。通过文件控制块FCB来维护文件结构。文件控制块包含有关文件的信息，包括所有者、权限、文件内容的位置等。逻辑文件系统也复制保护和安全
• 文件组织模块：知道文件及其逻辑块和物理块。将文件的逻辑块地址转换为物理块地址。每个文件的逻辑块从0（或1）到N编号，而包含数据的物理块并不与逻辑块匹配，因此需要转换来定位块。还包括可用空间管理器来跟踪未分配的块并根据需要提供给文件组织模块。
• 基本文件系统：向适当的设备驱动程序发出通用命令，以读取和写入磁盘上的物理块。还包括缓冲区
• I/O控制：包括设备驱动程序和中断处理程序，用于在主存和磁盘之间传输信息。设备驱动程序可以作为翻译器，输入为高级命令，输出由底层的、硬件指定的指令组成，硬件控制器利用这些指令来使I/O设备与其他系统部分相连。

分层结构实现文件系统，可最小化代码重复。每个文件系统可以拥有自己的逻辑文件系统额文件组织模块。
但分层可能增加了操作系统开销，导致性能降低。

大多数操作系统支持多个文件系统结构

文件系统操作

用于实现文件系统的数据结构

磁盘上结构

• 引导控制块：可以包含从该卷引导操作系统的所需信息。UFS称为引导快，NTFS称为分区引导扇区
• 分区控制块、卷控制块：包括卷的详细信息，如分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针。UFS称为超级块，NTFS称为主控文件表
• 目录结构：用于组织文件。UFS中，包含文件名和相关的i-node的号码；在NTFS中，它存储在主控文件表中。

FCB 每个文件的FCB包括该文件的许多详细信息，文件权限、所有权、大小、数据块的位置。它有唯一的标识号，以便与目录条目相关联。

内存中结构
用于管理文件系统并通过缓存来提高性能。

• 安装表、内存分区表：包含每个安装/挂载卷的相关信息
• 内存中的目录结构的缓存含有最近访问目录的信息
• 整个系统的打开文件表：包括每个打开文件的FCB的副本及其他信息
• 单个进程的打开文件表：包括指针，指向整个系统的打开文件表中的适当条目以及其他信息。

为了创建新的文件，进程调用逻辑文件系统。逻辑文件系统知道目录结构的格式，为了创建新的问价，它会分配一个新的FCB，然后系统将相应的目录读到内存，使用新的文件名和FCB进行更新，并将其写回文件系统。

目录实现

目录分配和目录管理的算法选择会显著影响文件系统的效率、性能和可靠性。

线性列表

使用文件名称和数据块指针的线性链表
查找文件：要求进行线性搜索
创建文件：搜索目录以确保没有现有文件具有相同的文件名，在目录末尾添加新条目
删除文件：在目录中搜索文件，删除条目，释放分配给此文件的空间

编程简单、执行耗时、搜索成本高昂

哈希表

使用线性列表来存储目录条目，并使用哈希表快速找出给定文件名的目录条目
两种方式

• 允许冲突（每个哈希条目都有一个包含多个值的列表）
  使用哈希函数将文件名映射到哈希值，使用此值为哈希表编制索引，然后搜索列表以查找目录条目
  更快
• 不允许冲突（每个哈希条目都有一个值）
  使用哈希函数将文件名映射到哈希值
  哈希函数应该动态更改

分配方法

如何为这些文件分配空间，以便有效使用存储空间和快速访问文件。

连续分配

每个文件在磁盘上占用一组连续的块
文件的目录仅包含起始位置和长度
支持顺序访问和直接访问
问题：

• 存在外部碎片
• 文件无法增长 如果分配的空间太小，无法扩展文件；太大，就会浪费空间

  链接分配

  每个文件都是存储块的链接，存储块可能散布在设备上的任何地方。
  该目录包含指向文件的第一个和最后一个块的指针。
  没有外部碎片问题
  只能顺序访问，无随机访问
  指针浪费空间
  变种-文件分配表FAT

  索引分配

  将所有指针放在一起，即使用索引块
  每个文件都有自己的索引块。该目录包含索引块的地址。
  支持顺序访问和直接访问
  索引块会浪费空间

大文件的解决方案

1. 链接方案 大文件，将多个索引块链接起来；小文件，一个索引块
2. 多级索引
3. 组合方案

性能

两个标准：存储利用率，数据块访问时间
连续分配：适用于已知大小的文件
链接索引：有利于存储利用率
索引分配：访问时间取决于索引结构、文件大小、区块位置

空闲空间管理

由于存储空间有限，如果可能，需要将已删除文件的空间重新用于新文件。为了跟踪空闲磁盘空间，系统需要维护一个空闲空间列表。空闲空间列表记录了所有空闲存储空间，即未分配给文件或目录的空间。创建文件时，搜索空闲空间列表以得到所需的空间数量，并将该空间分配给新文件。然后，这些空间会从空闲空间列表中删除。删除文件时，其空间会增加到空闲空间列表上，空闲空间列表虽然被称为列表，但是不必按照列表来实现。

位向量

空闲空间列表按位向量来实现。每块用一位来标识。如果块是空闲的，位为1，如果块是分配的，位为0。
优点：在查找磁盘上的第1个空闲块和n个连续的空闲块时相对简单和高效。

链表

将所有空闲块用链表链接起来，将指向第一空闲块的指针保存在文件系统的特殊位置上，同时也将其缓存在内存中。第一个块包含下一个空闲块的指针，如此继续下去。
缺点：比较低效，在遍历整个列表时，需要读入每个块，从而需要大量的I/O时间。
优点：不浪费空间

分组

第一个空闲块存储n个空闲块的地址
n个空闲块中的前n-1个是空闲区块，最后一块包含另外n个空闲块的地址
更容易找到大量空闲区块。

计数

每个条目都是一对（起始地址、连续区块号），而不仅仅是一个地址
表的总长度更短

大容量存储系统

现代计算机的主要大容量存储系统是二级存储（或外存），通常由硬盘驱动器（HDD）和非易失性存储器（NVM）设备提供。一些系统还具有更慢、更大的三级存储，包括磁带、光盘甚至云存储。

硬盘驱动器

磁盘结构

• 盘片；为一个扁平的圆片，覆盖有磁性材料，以每秒60-250次的速度旋转，通过将信息磁性记录在盘片上来存储信息，通过检测盘片上的磁性格式来读取信息。
• 磁道：盘片表面在逻辑上分为圆形轨道
• 扇区：每个磁道细分为几个扇区
• 柱面：是位于一个磁臂位置的磁道集合
• 读写头：磁盘磁头在空气或其他气体的极薄垫上飞行，有与磁盘表面接触的危险，发生磁头划碰
• 磁臂：将所有磁头作为一个整体移动

磁盘速度

• 传输速率：驱动器和计算机之间数据流的速率，每秒数兆字节的数据
• 定位时间（随机访存时间）：寻道时间+旋转延迟
• 寻道时间：将磁臂移到所需柱面所需的时间
• 旋转延迟：所需扇区旋转到磁头所需的时间，几毫米

二级存储连接方法

I/O总线

• 一组电线，通过它连接到计算机的磁盘驱动器
• 种类：EIDE, ATA, SATA, SCSI （SAS），USB、光纤通道、Fireware
• 主机控制器：在I/O总线的计算机端，CPU 使用内存映射 I/O 端口将命令放入主机控制器，主机控制器通过消息将命令发送到磁盘控制器
• 磁盘控制器：在I/O总线的磁盘驱动器端，内置于每个磁盘驱动器或存储阵列中，作磁盘驱动器硬件以执行命令

磁带

• 早期的二级存储结构，相对永久，保存大量数据
• 随机访问速度比磁盘慢1000倍左右
• 一旦数据在头部附近，传输数据与磁盘相当
• 主要用于备份、存储不常用数据、系统间传输介质
• 保存在线轴中，并在读写头上缠绕或倒带

地址映射

存储设备按大型一维数据的逻辑块来寻址，逻辑块是最小的传输单元。
每个逻辑块映射到一个物理扇区。
地址转换：通过映射，理论上至少能够将逻辑块号转换为老式硬盘地址，该地址有磁盘内的柱面号、磁盘内的磁道号、磁道内的扇区号组成。
实践中，由于三个原因，这个转换的执行很难实现

1. 大多数磁盘都有一些缺陷扇区。因此映射必须用磁盘上的其他空闲扇区来替代这些缺陷删除。逻辑块地址保持顺序，但是物理删除位置发生改变。
2. 对于某些驱动器，每个磁道的扇区数并不是常量。
   对于采用恒定线速度CLV的媒介，每个磁道的比特密度是均匀的，磁道距离磁盘中心越远，长度越长，从而也能容纳更多的扇区。当从外部区域移到内部区域时，每个轨道的扇区数量会降低，驱动器会增加旋转速度，以保持传输数据率的恒定。适用于CD-ROM和DVD-ROM。
   恒定角速度CAV：适用于硬盘，磁盘旋转速度保持不变，内部磁道到外部磁道的比特密度不断降低，以保持数据率不变。
3. 硬盘制造商会在内部管理LBA到物理地址的映射。

磁盘调度

对于磁盘驱动器HDD，操作系统需要负责具有最小化访问时间和最大化数据传输带宽。
访问时间有两个主要组成部分

• 寻道时间是磁臂移动磁头到包含目标扇区的柱面的时间。目标是最小化寻道时间。可以近似将寻道时间看为寻道距离
• 旋转延迟是磁盘旋转目标扇区到磁头下的额外时间。

设备带宽：传输字节的总数除以从服务请求开始到最后传递结束之间的总时间。

通过管理存储I/O请求的服务顺序，可以改善访问时间和带宽。

对于磁盘I/O请求，如果所需的磁盘驱动器和控制器可用，则可以立即为请求提供服务。
如果繁忙，任何新请求都将放入该如东其的挂起请求队列。队列通常可能有多个待处理请求。

先来先服务FCFS

最简单、比较公平、不提供最快的服务

最短寻道时间优先SSTF

从当前head位置选择具有最小寻道时间的请求
SSTF调度是SJF的一种形式，可能会导致饥饿

扫描SCAN

电梯算法
磁臂从磁盘的一段开始向另一端移动，在移过每个柱面时提供请求。当到达磁盘的另一端时，磁头移动方向反转，并继续处理。磁头连续来回扫描磁盘。

循环C-SCAN

提供更均匀的等待时间
磁臂从磁盘的一端移动向另一端，在移过每个柱面时提供请求。但是，当它到达另一端时，它会立即返回到磁盘的开头，而不在回程中处理任何请求。
将柱面视为一个环链，将最后柱面连到首个柱面