操作系统

操作系统作为计算机系统的核心软件，管理着计算机的硬件与软件资源。这张思维导图围绕操作系统展开，全面且细致地涵盖了多个关键知识板块。在计算机系统概述部分，梳理了操作系统的运行环境、体系结构等基础概念，为后续学习奠定根基。输入/输出管理板块详细介绍了I/O设备、I/O管理概述以及磁盘和固态硬盘等相关知识，帮助理解计算机如何与外部设备进行数据交互。进程与线程是操作系统的核心内容之一，此模板深入讲解了进程的概念和特征、状态与转换、调度，以及线程与多线程模型等，还涉及CPU调度算法、同步与互斥等重要知识点，这对于掌握操作系统的运行机制至关重要。文件管理部分则阐述了文件的基本概念、操作、逻辑结构、物理结构以及目录等内容，有助于理解数据的存储与组织方式。内存管理板块同样丰富，包含内存管理的基本原理、分配管理方式等关键要点，是掌握计算机内存运用规则的重要参考。通过这张思维导图，学习者能够以直观的方式梳理操作系统的复杂知识体系，将各个知识点串联起来，形成系统的认知。无论是用于课堂学习的辅助工具，还是考前的复习资料，亦或是工作中的技术参考，它都能发挥重要作用，帮助用户更高效地学习和掌握操作系统相关知识。

操作系统

• 计算机系统概述
  • 操作系统的基本概念
    • 操作系统的概念
      • 控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他润阿金提供方便接口与环境的程序集合
    • 操作系统的功能和目的
      • 作为计算机系统资源的管理者
        • 处理机管理
        • 存储器管理
        • 文件管理
        • 设备管理
      • 作为用户与计算机硬件系统之间的接口
        • 命令接口
          • 组织和控制作业的执行
          • 分类
            • 联机控制方式
              • 交互式命令接口
              • 适用于分时或实时系统
            • 脱机控制方式
              • 批处理命令接口
              • 适用于批处理系统
        • 程序接口
          • 请求操作系统服务
          • 由一组系统调用（广义指令）组成
      • 实现了对计算机资源的扩充
    • 操作系统的特征
      • 并发
      • 共享
        • 互斥共享方式
        • 同时访问方式
      • 虚拟
      • 异步
      • 操作系统最基本的特征是并发和共享，两者互为存在条件
    • 补充
      • 通道是独立于CPU、控制输入/输出的设备，与处理机可以并行
  • 操作系统发展历程
    • 手工操作系统
      • 用户独占全机
      • CPU等待手工操作
    • 批处理阶段
      • 单道批处理系统
        • 特征
          • 自动性
          • 顺序性
          • 单道性
      • 多道批处理系统
        • 作业队列+作业调度程序（中断调度）
        • 特征
          • 多道
          • 宏观上并行
          • 微观上串行
      • 作业执行时用户无法干预其行为
    • 分时操作系统
      • 分时技术
      • 特征
        • 同时性（多路性）
        • 交互性
        • 独立性
        • 及时性
      • 采用优先级+非抢占式调度算法有利于改善系统响应时间
      • 加大时间片会延迟系统响应时间
    • 实时操作系统
      • 硬实时系统
        • 必须在绝对严格的规定时间内完成处理
      • 软实时系统
        • 能接受偶尔违反时间规定
      • 能优先处理紧急任务
    • 网络操作系统和分布式计算机系统
    • 补充
      • 脱机技术是指在主机以外的设备上进行输入/输出操作，需要时再送主机处理，以提高设备利用率
      • 操作系统的基本类型主要有批处理操作系统、分时操作系统和实时操作系统
  • 操作系统的运行环境
    • 处理器运行模式
      • 程序性质
        • 操作系统内核程序
        • 用户自编程序（应用程序）
      • 指令分类
        • 特权指令
          • I/O指令
          • 关中断指令
          • 内存清零指令
          • 存取用于内存保护的寄存器
          • 修改程序状态字寄存器
          • ···
        • 非特权指令
      • 运行模式
        • 用户态（目态）
        • 内核态（管态、核心态）
      • 内核内容
        • 时钟管理
        • 中断机制
        • 原语
          • 处于操作系统底层
          • 运行具有原子性
          • 定义原语的直接方法是关中断
        • 操作系统控制的数据结构及处理
          • 进程管理
            • 进程状态管理、进程调度和分配、创建与撤销进程控制块等
          • 存储器管理
            • 存储器的空间分配和回收、内存信息保护程序、代妈对换程序等
          • 设备管理
            • 缓冲区管理、设备分配和回收等
    • 中断和异常的概念
      • 定义
      • 分类
        • 内中断（异常）
          • trap
          • fault
          • abort
        • 外中断
          • 时钟中断
            • 处理和时间有关的信息，以及决定是否执行调度程序
            • 有关信息包括
              • 系统时间
              • 进程的时间片
              • 延时
              • 进程使用CPU的时间
              • 各种定时器
          • I/O中断请求
      • 处理过程
        • 中断处理过程中，PC和PSW由中断隐指令自动保存，之后硬件找到该中断信号对应的中断向量，中断向量指明中断服务程序入口地址
          • 各中断向量统一存放在终端向量表中，该表由操作系统初始化
        • 操作系统执行中断服务程序，保存中断屏蔽字、保存各通用寄存器的值，并提供于中断信号对应的终端服务
      • 中断处理和子程序调用的比较
        • 中断处理程序与被中断的当前程序是相互独立的；子程序与主程序是同一程序的两部分，属于主从管理
        • 通常中断的产生是随机的，入口地址可由硬件向量法产生向量地址，进而找到入口地址；子程序的调用是通过调用指令（CALL）引起的，入口地址由CALL指令指明
        • 调用子程序的过程完全属于软件处理过程；中断过程需要有专门的硬件电路
        • 保存PC，中断处理由中断隐指令完成，子程序调用有CALL指令完成
      • 中断是操作系统必须要提供的功能
    • 系统调用
      • 与共享资源有关的操作（如存储分配、I/O传输及文件管理等），都必须经过系统调用的方式向操作系统提出服务请求，由操作系统代为完成，并将处理结果返回给应用程序
      • 系统调用的功能
        • 设备管理
        • 文件管理
        • 进程控制
        • 进程通信
        • 内存管理
      • 处理过程
        • 传递系统调用参数
          • 用户程序将系统调用号和所需参数压入堆栈
        • 调用实际的调用指令，执行陷入（trap，访管）指令
          • CPU状态从用户态转为内核态
            • 由CPU修改内核态状态字
          • 硬件和操作系统内核程序保护被中断进程的现场
            • PC、PSW及通用寄存器内容等压入堆栈
        • 分析系统调用，转入相应的系统调用处理子程序
        • 系统调用子程序执行结束，恢复被中断的或设置新进程的CPU现场，返回原进程或新进程
    • 补充
      • 系统调用需要保存PSW和PC的值，一般调用只需保存PC
      • 系统调用过程
        • 调用过程
          • 用户程序发起系统调用的操作
            • 用户态
        • 被调用过程
          • 操作系统内核相应并处理系统调用的阶段
            • 内核态
      • 系统调用完成后，CPU从内核态转为用户态
  • 操作系统结构
    • 分层法
      • 分层
        • 0层
          • 硬件
        • · · ·
        • 顶层
          • 用户接口
      • 优缺点
        • 优点
          • 便于系统的调试和验证
          • 易扩充和易维护
        • 缺点
          • 合理定义各层比较困难
          • 效率较差
      • 单向依赖
        • 每层只能调用紧邻它的底层的功能和服务
    • 模块化
      • 内聚性
        • 模块内部各部分间的紧密程度
      • 耦合度
        • 模块间相互联系和相互影响的程度
      • 优缺点
        • 优点
          • 提高了操作系统设计的正确性、可理解性和可维护性
          • 增强了操作系统的可适应性
          • 加速了操作系统的开发过程
        • 缺点
          • 模块间的接口规定很难满足对接口的实际需求
          • 各模块设计者齐头并进，无法找到一个可靠的决定顺序
      • 模块化操作系统的各功能模块都在内核中，且模块之间相互调用、相互依赖，任何一个模块出错，都可能导致整个内核崩溃
    • 宏内核
      • 将系统的主要功能模块都作为一个紧密联系的整体运行在内核态
    • 微内核
      • 基本概念
        • 将内核中最基本的功能保留在内核，将不需要在内核态执行的功能移到用户态执行，降低内核设计复杂性
        • 微内核将操作系统划分为两大部分
          • 微内核
            • 包含
              • 与硬件处理紧密相关的部分
              • 较基本的功能
              • 客户与服务器之间的通信
          • 多个服务器
      • 基本功能
        • 进程（线程）管理
          • 进程（线程）间通信
          • 进程的切换、调度
          • 多处理机之间的同步
          • 低级I/O
          • · · ·
        • 低级存储器管理
        • 中断和陷入处理
          • 捕获发生的中断和陷入事件，并进行中断响应处理，识别中断或陷入事件后，发送给相关的服务器处理
      • 特点
        • 扩展性和灵活性
        • 可靠性和安全性
        • 可移植性
        • 分布式计算
        • 性能问题
          • 需要频繁地在内核态和用户态之间进行切换，操作系统的执行开销偏大
    • 外核
      • 为虚拟机分配资源，并检查这些资源使用的安全性
      • 只负责硬件资源的分配、回收、保护等，进程管理相关的工作仍然由内核负责
    • 补充
      • Windows是融合了宏内核和微内核的操作系统
  • 操作系统引导
    • 指计算机利用CPU运行特定程序，通过程序识别硬盘，识别硬盘分区，识别硬盘分区上的操作系统，最后通过程序启动操作系统
    • 引导过程
      • 激活CPU
        • 读取ROM中的boot程序
        • 将指令寄存器置为BIOS的第一条指令，开始执行
      • 硬件自检
        • BIOS程序构建中断向量表
        • 通电自检（POST）
      • 加载带有操作系统的硬盘
        • BIOS读取 Boot Sequence（通过CMOS里保存的启动顺序、或通过与用户交互的方式）
      • 加载主引导记录（MBR）
      • 扫描硬盘分区表
      • 加载分区引导记录（PBR）
      • 加载启动管理器
      • 加载操作系统
    • 系统开机后，操作系统的程序会被自动加载到内存中的系统区，这段区域是RAM
  • 虚拟机
    • 基本概念
      • 第一类虚拟机管理程序
        • 虚拟内核态
        • 直接运行在硬件之上，能直接控制和分配物理资源
        • 性能更好，可迁移性差
        • 运行在最高特权级
      • 第二类虚拟机管理程序
        • 宿主操作系统，依赖宿主操作系统为其分配物理资源
        • 性能差，可迁移性更好
        • 部分运行在用户态、部分运行在内核态
          • 发出的系统调用会被VMM截获，转化为VMM对宿主操作系统的系统调用
    • 虚拟机可以用软件实现，也可以用硬件实现
• 进程与线程
  • 进程与线程
    • 进程的概念和特征
      • 进程的概念
        • 定义
          • 进程是一个正在执行程序的实例
          • 进程是一个程序及其数据从磁盘被加载到内存后，在CPU上的执行过程
          • 进程是一个具有独立功能的程序在一个数据集合是上运行的过程
        • PCB
          • 进程控制块
        • 进程实体（映像）
          • 程序段
          • 相关数据段
          • PCB
        • C语言编写的程序在使用内存时一般分为三个段
          • 正文段
            • 代码
            • 赋值数据段
              • 常量
              • 全局赋值变量
          • 数据堆段
            • 动态分配的存储区
          • 数据栈段
            • 临时使用的变量
      • 进程的特征
        • 动态性
          • 进程最基本的特征
        • 并发性
        • 独立性
        • 异步性
    • 进程的组成
      • 进程是操作系统进行资源分配和调度的基本单位
      • 组成
        • 进程控制块
          • 进程创建时操作系统为其新建一个PCB，PCB常驻内存，任意时刻可存取，进程结束时删除
          • 操作系统调度与PCB
            • 调度前
              • 从目标进程的PCB中查出其现行状态及优先级
            • 调度到
              • 根据PCB中所保存的CPU状态信息，设置该进程恢复运行的现场
              • 根据PCB中的程序和数据的内存地址，找到其程序和数据
            • 进程运行过程中
              • 需与其他进程实现同步、通信或访问文件时，需要访问PCB
            • 暂停运行时
              • 将断点的CPU环境保存在PCB中
          • 主要包括
            • 进程描述信息
              • 进程标识符（PID）
                • 唯一标识进程
              • 用户标识符（UID）
                • 标识进程所归属的用户
                • 主要为共享和保护服务
            • 进程控制和管理信息
              • 进程当前状态
              • 进程优先级
            • 资源分配清单
              • 说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入/输出设备信息
            • 处理机相关信息（CPU上下文）
              • 主要指CPU中各寄存器的值
          • 组织方式
            • 链接方式
              • 将同一状态的PCB链接成一个队列
              • 不同状态对应不同队列
              • 阻塞态进程的PCB，可根据其阻塞原因的不同，排成多个阻塞队列
            • 索引方式
              • 将同一状态的进程组织在一个索引表中
              • 不同状态对应不同的索引表
          • 补充
            • 每个进程都有独立的内核栈，用于执行内核代码时的临时数据存储，如函数调用和中断处理
            • PCB中仅保存内核栈的指针，而非直接存储寄存器的内容
              • 当系统调用触发用户态到内核态的切换时，硬件会自动将用户态的寄存器保存到当前进程的内核栈中，而非直接存入PCB
        • 程序段
          • 能被进程调度到CPU执行的程序代码段
          • 程序可被多个进程共享
          • 一个进程可以顺序地执行一个或多个程序，但不能同时执行多个程序
          • 一个程序在执行过程中可产生多个进程
            • 程序可以通过系统调用fork()或create()来创建子进程
        • 数据段
          • 可以是进程会给你对应程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果
    • 进程的状态与转换
      • 状态
        • 运行态
        • 就绪态
          • 就绪队列
        • 阻塞态（等待态）
          • 阻塞队列
        • 基本状态
        • 创建态
        • 终止态
      • 转换
      • 进程的生命周期是不连续的
    • 进程控制
      • 原语
      • 进程的创建
        • 父进程与子进程
          • 子进程可以继承父进程所拥有的资源
          • 子进程终止时，将从父进程获得的资源还给父进程
        • 创建过程（创建原语）
          • ①为新进程分配一个唯一的进程标识号，申请一个空白PCB
            • 若PCB申请失败，则创建失败
          • ②为进程分配其运行所需的资源
            • 资源或从操作系统获得，或从其父进程获得
            • 若资源不足，则并不是创建失败，而是处于创建态，等待内存资源
          • ③初始化PCB，主要包括初始化标志信息、初始化CPU状态信息和初始化CPU控制信息，以及设置进程的优先级等
          • ④若进程就绪队列能接纳新进程，则将新进程插入就绪队列，等待被调度执行
        • 场景
          • 用户登录
          • 高级调度
            • 即作业调度，会从后备队列中选择一个作业调入内存，并为之创建相应的进程
          • 操作系统响应用户提出的请求
          • 打开一个浏览器
          • · · ·
      • 进程的终止
        • 事件
          • 正常结束
          • 异常结束
            • 存储区越界
            • 保护错
            • 非法指令
            • 特权指令错
            • 运行超时
            • 算术运算错
            • I/O故障
            • · · ·
          • 外界干预
            • 操作员或操作系统干预
            • 父进程请求或父进程终止
        • 终止原语
          • ①根据被终止进程的标识符，检索出该进程的PCB，从中读出该进程的状态
          • ②若被终止进程处于运行状态，立即终止该进程的执行，将CPU资源分配给其他进程
          • ③若该进程还有子孙进程，通常需将其所有子孙进程终止（有些系统无此要求）
            • 级联终止
          • ④将该进程所拥有的全部资源，或归还其父进程，或归还给操作系统
          • ⑤将该PCB从所在队列中删除
        • 进程有它的生命周期，不会一直存在于系统中，也不一定需要用户显式地撤销
          • 通常用户进程被建立后，随着进程运行的正常或不正常结束而撤销
      • 进程的阻塞和唤醒
        • 阻塞
          • 期待事件未发生
            • 请求系统资源失败
            • 等待某种操作的完成
            • 新数据尚未到达
            • 无新任务可做
            • · · ·
          • 阻塞原语（Block）
            • ①找到将要被阻塞进程的标识号（PID）对应的PCB
            • ②若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行
            • ③将该PCB插入相应事件的等待队列，将CPU资源调度给其他就绪进程
        • 唤醒
          • 期待事件出现
          • 唤醒原语Wakeup
            • ①在该事件的等待队列中找到相应进程的PCB
            • ②将其从等待队列中移出，并置其状态为就绪态
            • ③将该PCB插入就绪队列，等待调度程序调度
      • 系统发生死锁时可能进程全部处于阻塞态，CPU空闲
    • 进程的通信
      • 共享存储
        • 操作系统提供可共享使用的存储空间和同步互斥工具
        • 不需要任何数据的拷贝和中介，是最快的进程通信方式
        • 分类
          • 低级方式
            • 基于数据结构的共享
          • 高级方式
            • 基于存储区的共享
      • 消息传递
        • 进程间的数据交换以格式化的消息为单位
        • 操作系统提供发送消息和接收消息两个原语
        • 过程
          • 当进程发送消息时，系统将消息从用户缓冲区复制到内核中的消息缓冲区，然后将消息缓冲区挂入消息队列，进程发送的消息保持在消息队列中，直到被另一进程接收，当进程接受消息时，系统从消息队列中解挂消息缓冲区，将消息从内核的消息缓冲区中复制到用户缓冲区，然后释放消息缓冲区
        • 分类
          • 直接通信方式
            • 发送进程直接将消息发送给接收进程
          • 间接通信方式
            • 发送进程将消息发送到某个中间实体（信箱），接收进程从中间实体取得消息
      • 管道通信
        • 管道是一个特殊的共享文件（pipe文件），数据在管道中是先进先出的
          • 普通管道只允许单向通信
          • 实现双向数据传输需要定义两个方向相反的管道
          • 在读/写过程中，操作系统保证数据的写入顺序和读出顺序是一致的
        • 生产者-消费者方式通信
          • 管道不满，写进程就能向管道的一端写入数据
          • 管道非空，读进程就能从管道的另一端读出数据
        • 协调能力
          • 互斥
            • 一个进程对管道进行读/写时，其他进程必须等待
          • 同步
            • 进程向管道写入一定数量的数据后，写进程阻塞，读进程读取数据后再将其唤醒
            • 读进程将管道中的数据取空后，读进程阻塞，直到写进程将数据写入管道后才将它唤醒
          • 确定对方存在
        • 管道可以克服使用文件进行通信的两个问题
          • 限制管道大小
            • 通过阻塞对管道的write()调用
          • 读进程也可能工作的比写进程快
            • 通过阻塞对管道的read()调用
        • 管道只能由创建进程所访问
          • 子进程可继承父进程的管道，用来与父进程进行通信
      • 信号
        • 是一种用于通知进程发生了某个事件的机制
          • 不同系统事件对应不同的信号类型
          • 在进程的PCB中
            • 用至少n位向量记录该进程的待处理信号
              • 若给某个进程发送一个信号，则把该类信号对应位置1
              • 信号处理后，对应位置0
            • 用另一个n位向量记录被阻塞（屏蔽）的型号
              • 对应位为1，表示该类信号将被进程忽略
        • 信号发送方式
          • 内核给某个进程发送信号
          • 一个进程给另一个进程发送信号
            • 进程也可以给自己发信号
        • 操作系统把一个进程从内核态转为用户态时，会检查该进程是否有未被阻塞的待处理信号
          • 若有则强制进程接收信号，并立即处理信号
          • 若有多个待处理信号，则通常处理序号更小的型号
        • 信号处理方式
          • 执行默认的型号处理程序
            • 操作系统为每类信号预设了默认的信号处理程序
          • 执行进程定义的型号处理程序
            • 进程可为某类信号自定义信号处理程序
    • 线程和多线程模型
      • 线程的基本概念
        • 目的
          • 引入进程
            • 更好地使多道程序并发执行，提高资源利用率和系统吞吐量
          • 引入线程
            • 减小程序在并发执行时所付出的失控开销，提高系统的并发性能
        • 线程最直接的理解就是轻量级进程
          • 线程是一个基本的CPU执行单元，也是程序执行流的最小单元
          • 由线程ID、程序计数器、寄存器集合和堆栈组成
        • 线程是进程中的一个实体，是被系统独立调度和分派的基本单位
          • 线程自己不拥有系统资源，只拥有少量运行必需资源
          • 线程可与统一进程下的其他线程共享进程拥有的全部资源
        • 优缺点
          • 优点
            • 提高系统并发性、节约系统资源、便于进程通信等
          • 缺点
            • 线程共享进程的地址空间和资源，若一个线程出错，可能影响整个进程的运行
      • 线程与进程的比较
        • 调度
          • 进程调度需要进程上下文切换，开销较大
            • 上下文切换时进程调度的实现手段
          • 引入线程的操作系统中，线程是独立调度的基本单位，线程切换的代价远低于进程
          • 统一进程中，线程切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时会引起进程切换
        • 并发性
          • 进程之间可以并发执行
          • 一个进程中多线程并发执行
          • 不同进程中的线程也能并发执行
        • 拥有资源
          • 进程是系统中拥有资源的基本单位
          • 线程不拥有资源，可以访问其隶属进程的系统资源
            • 表现在属于同一进程的所有线程都具有相同的地址空间
        • 独立性
          • 每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问
          • 某个进程中的线程对其他进程不可见，它们共享隶属进程的地址空间和资源
        • 系统开销
          • 创建和销毁进程时，系统都要为之分配或回收PCB及其他资源，切换进程涉及上下文切换
          • 线程切换只需保存和设置少量寄存器内容，开销很小
        • 支持多处理器系统
          • 传统单线程进程，只能运行在一个CPU上
          • 多线程进程，可将进程中的多个线程分配到多个CPU上执行
      • 线程的属性
        • 线程是一个轻型实体，不拥有系统资源，每个线程都应有一个唯一的标识符和一个线程控制块
          • 线程控制块记录线程执行的的寄存器和栈等现场状态
        • 不同的线程可以执行相同的程序
        • 统一进程中的各个线程共享该进程所拥有的资源
        • 线程是CPU的独立调度单位，多个线程可以并发执行
        • 线程在生命周期内会经历阻塞态、就绪态、运行态等各种状态变化
      • 线程的状态与转换
        • 基本状态
          • 执行态
          • 就绪态
          • 阻塞态
        • 转换和进程基本状态的转换一致
      • 线程的组织与控制
        • 线程控制块（TCB）
          • 系统为每个线程配置一个线程控制块
          • 用于记录控制和管理线程的信息
          • 包括
            • 线程标识符
            • 一组寄存器
              • 程序计数器
              • 状态寄存器
              • 通用寄存器
            • 线程运行状态
            • 优先级
            • 线程专有存储区
              • 线程切换时用于保护现场
            • 堆栈指针
              • 用于过程调用时保存局部变量和返回地址
        • 线程的创建
          • 初始化线程
            • 用户程序启动时，通常仅有一个初始化线程
            • 主要功能是用于创建新线程
          • 过程
            • 利用线程创建函数
            • 提供相应参数
              • 指向线程主程序的入口指针
              • 堆栈的大小
              • 线程优先级
              • · · ·
            • 线程创建函数执行完，返回线程标识符
        • 线程的终止
          • 事件
            • 线程完成自己的任务后
            • 线程在运行中出现异常而要被强制终止
          • 线程被终止后
            • 进程中的其他线程执行分离函数
              • 被终止线程与资源分离
            • 被终止但尚未释放资源的线程仍可以被其他线程调用，以使被终止线程恢复运行
      • 线程的实现方式
        • 用户级线程（ULT）
          • 有关线程管理（创建、撤销、切换）的所有操作，都由应用程序在用户空间（用户态）完成，无操作系统干预，内核意识不到线程存在
          • 可通过调用线程库中的派生例程创建一个在相同进程中运行的新线程
          • 设置了用户级线程的系统，其调度仍然以进程为单位进行
          • 优缺点
            • 优点
              • 线程切换不需要转换到内核空间，节省了模式切换的开销
              • 调度算法可以是进程专用的
              • 用户级线程的实现与操作系统平台无关
                • 对线程管理的代码是用户程序的一部分
            • 缺点
              • 系统调用的阻塞问题
                • 当线程执行一个系统调用时，该线程以及进程内的所有线程都会被阻塞
              • 不能发挥多CPU的优势
        • 内核级线程（KLT）
          • 内核级线程是在内核的支持下运行的，线程管理的所有工作也是在内核空间内（内核态）实现的
          • 操作系统为每个内核级线程设置一个线程控制块TCB
            • 内核根据该控制块感知某线程的存在，并对其加以控制
          • 优缺点
            • 优点
              • 能发挥多CPU的优势
              • 若进程中的一个线程被阻塞，则内核可以调度该进程中的其他线程占用CPU，或运行其他进程中的线程
              • 内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小
              • 内核本身也可采用多线程技术，提高系统的执行速度和效率
            • 缺点
              • 同一进程中的线程切换，需要从用户态转到内核态，系统开销较大
        • 组合方式
          • 内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程
          • 一个内核级线程对应多个用户级线程
            • 用户级线程通过时分多路复用内核级线程实现的
        • 线程库
          • 实现方式
            • 在用户空间中提供一个没有内核支持的库
            • 实现由操作系统直接支持的内核级的一个库
              • 库内的代码和数据结构位于内核空间
          • 三种主要线程库
            • POSIX Pthreads
              • 可提供用户级或内核级的库
            • Windows API
              • 内核级线程库
            • Java
              • Java线程API通常采用宿主系统的线程库来实现
      • 多线程模型
        • 多对一模型
          • 多个用户级线程被映射到一个内核级线程
          • 每个进程只被分配一个内核级线程，线程的调度和管理在用户空间完成
        • 一对一模型
          • 将每个用户级线程映射到一个内核级线程
        • 多对多模型
          • 将n个用户级线程映射到m个内核级线程
            • n≥m
          • 既克服了一对一模型并发度不高的缺点，又克服了一对一模型的一个用户级线程占用太多内核级线程而开销太大的缺点
  • CPU调度
    • 调度的概念
      • 基本概念
        • 从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将CPU分配给它运行，以实现进程的并发执行
        • CPU调度是多道程序操作系统的基础，也是操作系统设计的核心问题
      • 调度的层次
        • 高级调度（作业调度）
          • 按照某种规则，从外存上处于后备队列的作业中挑选一个或多个，分配内存、I/O设备等必要的资源，建立相应的进程，使其获得竞争CPU的权利
          • 内存与辅存之间的调度
          • 每个作业只调入一次、调出一次
          • 常见于多道批处理系统中
        • 中级调度（内存调度）
          • 目的
            • 提高内存利用率和系统吞吐量
          • 过程
            • 将暂时不能运行的进程调至外存等待
              • 挂起态
            • 当挂起态进程具备运行条件且内存有空闲时，由中级调度来决定将外存上已具备运行条件的挂起进程再重新调入内存，修改其状态为就绪态
          • 是对存储器管理中的对换功能
        • 低级调度（进程调度）
      • 三级调度的联系
        • 作业调度为进程活动做准备，进程调度使进程正常活动起来
        • 中级调度处于作业调度和进程调度之间
        • 作业调度次数最少，中级调度次数略多，进程调度频率最高
        • 进程调度是最基本的，不可或缺
    • 调度的实现
      • 调度程序（调度器）
        • 排队器
          • 将系统中所有就绪程序按照一定的策略排成一个或多个队列
          • 每当有一个进程转为就绪态时，排队器便将其插入相应队列
        • 分派器
          • 将调度程序选择的进程从就绪队列中取出，并分配CPU
        • 上下文切换器
          • 对CPU进行切换时，需要两对上下文切换操作
            • 第一对
              • 将当前进程上下文保存到其PCB
              • 装入分派程序的上下文
            • 第二对
              • 移出分派程序的上下文
              • 将新选进程的CPU现场信息装入CPU的各个寄存器
          • 上下文切换需执行大量load、store指令
            • 硬件实现方法减少耗时
              • 采用两组寄存器，一组内核使用，一组用户使用
              • 上下文切换时，改变指针，让其指向当前寄存器组
      • 调度的时机、切换与过程
        • 时机
          • 创建新进程后，父进程与子进程都处于就绪态，调度其中一个运行
          • 进程正常结束或异常终止后，从就绪队列中选取一个进程运行
            • 若没有就绪进程，通常运行一个系统提供的闲逛进程
          • 当进程因I/O请求、信号量操作或其他原因被阻塞时
          • I/O设备准备就绪后，发出I/O中断
        • 不能进行进程的调度与切换的情况
          • 在处理中断的过程中
          • 需要完全屏蔽中断的原子操作过程中
      • 进程调度的方式
        • 非抢占调度方式（非剥夺调度方式）
          • 直到正在执行的进程运行完成（正常结束、异常终止）或发生某种事件进入阻塞态时，才将CPU分配给其他进程
        • 抢占调度方式（剥夺方式）
          • 遵循一定的原则
            • 主要有优先权、短进程有限和时间片原则等
      • 闲逛进程（Idle Process）
        • PID为0
        • 没有其他就绪进程时
          • 一直运行，并在指令周期后测试中断
        • 不会被阻塞
      • 两种线程的调度
        • 用户级线程
          • 由进程中的调度程序决定
        • 内核级线程
          • 内核选定特定线程运行，通常不考虑线程属于哪个进程
          • 对被选择线程赋予一个时间片
            • 超时强制挂起
    • 调度的目标
      • CPU调度算法评价标准
        • CPU利用率
        • 系统吞吐量
          • 单位时间内CPU完成作业的数量
          • 长作业会降低系统吞吐量，短作业相反
        • 周转时间
          • 周转时间
            • 作业提交到作业完成所经历的时间
            • 作业完成时间 - 作业提交时间
          • 平均周转时间
            • 多个作业周转时间的平均值
          • 带权周转时间
            • 作业周转时间与作业运行时间的比值
          • 平均带权周转时间
        • 等待时间
          • 进程处于等待CPU的时间之和
        • 响应时间
          • 从用户提交到系统首次产生响应的时间
    • 进程切换
      • 上下文切换
        • ①挂起一个进程，将CPU上下文保存到PCB
        • ②将进程的PCB移入相应的队列
        • ③选择另一个进程执行，并更新其PCB
        • ④恢复新进程的上下文
        • ⑤跳转到新进程的PCB中的程序计数器所指位置
      • 上下文切换的消耗
      • 上下文切换与模式切换
        • 上下文切换只能发生在内核态
    • CPU调度算法
      • 先来先服务（FCFS）
        • 可用于作业调度，又可用于进程调度
      • 短作业优先（SJF）
        • 短作业优先
          • 从后备队列中选择一个或几个估计运行时间最短的作业，调入内存运行
        • 短进程优先（SPF）
          • 从就绪队列中选择一个估计运行时间最短的进程，分配CPU，直到完成或阻塞
        • 饥饿现象
          • 调度程序总是优先调度短作业，导致长作业长期不被调度
      • 高响应比优先调度
        • 主要用于作业调度
        • 每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行
      • 优先级调度
        • 可用于作业调度，又可用于进程调度
        • 分类
          • 根据能否抢占
            • 非抢占式优级先调度
            • 抢占式优先级调度
          • 根据进程创建后优先级是否可改变
            • 静态优先级
            • 动态优先级
        • 参照原则
          • 系统进程 > 用户进程
          • 交互型进程 > 非交互型进程 （或 前台进程 > 后台进程）
          • I/O型进程 > 计算型进程
      • 时间片轮转（RR）
        • 主要适用于分时系统
        • 原理
          • 系统将所有就绪进程按FCFS策略排成一个就绪队列
          • 每隔一定的时间便产生一次中断，激活调度程序进行调度
          • 执行完一个时间片后，即使程序并未运行完成，也需要释放CPU给就绪队列的新队首进程，被剥夺的进程返回队末重新排队
      • 多队列调度
        • 在系统中设置多个队列，将不同类型或性质的进程固定分配到不同的就绪队列
      • 多级反馈队列调度
        • 实现思想
          • ①设置多个就绪队列，并为每个队列赋予不同的优先级，第1级队列优先级最高，其余队列优先级逐个降低
          • ②赋予各个队列的进程运行时间片的大小各不相同
            • 优先级越高的队列中，时间片越小
            • 如，第i+1级的时间片是第i级的1倍
          • ③每个队列采用FCFS算法
            • 新进程进入内存后，首先放入第1级队列，按FCFS等待调度
            • 若某进程再分配时间片
              • 完成
                • 撤离系统
              • 未完成
                • 调度程序将其转入下一级队列末尾
          • ④按队列优先级调度
            • 仅当第i-1级队列为空时，才会调度第i级队列中的进程运行
            • 若CPU正在执行第i级队列中的某个进程时，有新进程进入优先级更高的队列，则立即将正在运行的进程放回第i级队列末尾，将CPU分配给新到的高优先级进程
      • 基于公平原则的调度算法
        • 保证调度算法
        • 公平分享调度算法
          • 对进程公平，但不意味对用户公平
    • 多处理机调度
      • 非对称多处理机（AMP）
        • 大多采用主从式操作系统
          • 内核驻留在主机上，从机上只运行用户程序，进程调度由主机负责
          • 从机空闲时，向主机发送一个索取进程的信号，主机分配
      • 对称多处理机（SMP）
        • 所有处理机都是相同的
        • 调度问题
          • 亲和性负载平衡
            • 处理器亲和性
              • 系统应尽量避免将进程从一个CPU转移到另一个CPU（这样需要将第一个CPU的缓存设置为无效，然后重新填充第二个CPU的缓存），应当试图让一个进程运行在同一个CPU上
            • 负载平衡应设法将负载平均分配到SMP所有CPU上
          • 多处理机调度方案
            • 公共就绪队列
              • 系统中进设置一个公共就绪队列，所有CPU共享
              • 提升处理器亲和性
                • 软亲和
                  • 调度程序尽量保持一个进程到某个CPU上，但这个进程也可以迁移到其他CPU
                • 硬亲和
                  • 用户进程通过系统调用，主动请求系统分配到固定的CPU上
            • 私有就绪队列
              • 每个CPU设置一个就绪队列
              • 平衡负载
                • 推迁移
                  • 一个特定的系统程序周期性检查每个CPU的负载，若发现不平衡，则从超载CPU的就绪队列中“推”一些进程到空闲CPU的就绪队列
                • 拉迁移
                  • 若一个CPU负载很低，就从超载PCU的就绪队列“拉”进程到自己的就绪队列
  • 同步与互斥
    • 同步与互斥的基本概念
      • 临界资源
        • 系统中一次仅允许一个进程使用的资源
        • 临界区
        • 访问过程
          • 进入区
            • 检查是否可进入临界区
              • 若能进入，应设置正在访问临界区的标志，以阻止其他进程同时进入临界区
          • 临界区（临界段）
            • 进程中访问临界资源的代码段
          • 退出区
            • 将正在访问临界区的标志清除
          • 剩余区
            • 代码中的其余部分
      • 同步（直接制约关系）
        • 指为完成某种任务而建立的两个或多个进程，这些进程因为要协调他们的运行次序而等待、传递信息所产生的制约关系
      • 互斥（间接制约关系）
      • 同步机制准则
        • 空闲让进
        • 忙则等待
        • 有限等待
        • 让权等待
          • 当进程不能进入临界区时，应立即释放处理器
    • 实现临界区互斥的基本方法
      • 软件实现方法
        • 单标志法
          • 设置一个公用整型变量 turn，只是允许进入临界区的进程编号
            • 示例
              • 进程0： while(turn!=0); critical section; turn=1; remainder section;
              • 进程1： while(turn!=1); critical section; turn=0; remainder section;
          • 两个进程必须交替进入临界区，容易造成资源利用不充分
        • 双标志先检查法
          • 设置一个布尔型数组flag[2]，用来标记各个进程想进入临界区的意愿
            • Pi进入临界区前，先检查对方是否想进入临界区，若想则等待，否则将flag[i]置true再进入临界区
          • P0和P1可能同时进入临界区
        • 双标志后检查法
          • 先设置自己的标志，再检查对方的标志
          • 可能都无法进入临界区
        • Peterson算法
          • // 进程0 void process0() { flag[0] = true; turn = 1; while (flag[1] && turn == 1); // 临界区 flag[0] = false; // 剩余区 } // 进程1 void process1() { flag[1] = true; turn = 0; while (flag[0] && turn == 0); // 临界区 flag[1] = false; // 剩余区 }
      • 硬件实现方法
        • 中断屏蔽方法
          • 关中断 临界区 开中断
          • 缺点
            • 限制了CPU交替执行程序的能力，系统效率明显降低
            • 需要将关中断的权限交给用户
            • 不适用于多处理器系统
        • 硬件指令方法
          • TestAndSet指令（TS指令）
            • 原子操作
              • boolean TestAndSet(boolean *lock) { boolean old; old = *lock; *lock = true; return old; }
            • TS指令检查lock值
              • false
                • 表示没有任何进程在临界区，并将lock置为true
              • true
                • 进入循环等待
            • 实现互斥
              • while TestAndSet(&lock); 临界区 lock=false; 剩余区
          • Swap指令
            • boolean key=ture; while(key!=false) Swap(&lock, &key); 临界区 lock=false; 剩余区
          • 硬件指令方法
            • 优点
              • 简单、容易验证其正确性
              • 适用于任意数量的进程，支持多处理器系统
              • 支持系统中有多个临界区
            • 缺点
              • 等待进入临界区的进程会占用CPU执行while循环，不能实现“让权等待”
              • 容易导致“饥饿”现象
    • 互斥锁
      • 解决临界区最简单的工具
      • 互斥锁可用于多线程或多进程之间，但只有对它加锁的线程或进程才能解锁它
      • acquire()函数
        • 一个进程在进入临界区时调用，以获得锁
      • release()函数
        • 退出临界区时调用，以释放锁
      • 必须是原子操作，通常硬件实现
      • 也称自旋锁
      • 主要缺点
        • 忙等待
    • 信号量
      • 只能被两个标准原语wait()和signal()访问
        • 简写为P()和V()，或简称P操作和V操作
      • 整型信号量
        • wait(S) { while(S<=0); S=S-1; }
        • signal(S) { S=S+1; }
      • 记录型信号量
        • 需要一个用于代表资源数量的整型变量value，和一个进程链表用于链接所有等待该资源的进程
          • typedef struct{ int value; struct process *L; } samaphore;
        • void wait(semaphore S) { S.value--; if(S.value<0){ add this process to S.L; block(S.L) } }
          • 让权等待
        • void signal(semaphore S) { S.value++; if(S.value<=0) { remove a process P from S.L; wakeup(P); } }
      • 利用信号量实现进程互斥
        • 为临界资源设置一个互斥信号量S，初值为1
        • 将各个进程访问该资源的临界区置于P(S)和V(S)之间
        • S的取值范围
          • 1
            • 表示两个进程都未进入临界区
          • 0
            • 有一个进程已进入临界区
          • -1
            • 有一个进程正在临界区，另一个进程因等待而阻塞在阻塞队列中，需要被当前已在临界区的经常退出时唤醒
      • 利用信号量实现同步
        • 同步源于进程之间相互合作，让本来异步的并发进程相互配合，有序推进
        • 信号量的初始值应根据具体情况来确定
        • 实现
          • semaphore S=0; P1() { x; V(S); · · · } P2() { · · · P(S); y; · · · }
      • 利用信号量实现前驱关系
        • 每对前驱关系都是一个同步问题
          • 要为每对前驱关系设置一个同步信号量
      • 分析进程同步和互斥问题的方法步骤
        • 关系分析
        • 整理思路
        • 设置信号量
    • 经典同步问题
      • 生产者-消费者问题
        • semaphore mutex = 1; semaphore empty = n; semaphore full = 0; producer(){ while(1){ 生产一个产品 P(empty); P(mutex); 将产品放入缓冲区 V(mutex); V(full); } } consumer(){ while(1){ P(full); P(mutex); 从缓冲区取出一个产品 V(mutex); V(empty); 消费产品 } }
        • 生产者和消费者共享缓冲区，每次仅允许一个生产者或消费者进入缓冲区，生产者可能唤醒其他生产者或消费者，消费者也可能唤醒其他生产者或消费者
      • 读者-写者问题
        • 读进程优先
          • int count=0; semaphore mutex=1; semaphore rw=1; writer(){ while(1){ P(rw); 写文件 V(rw); } } reader(){ while(){ P(mutex); if(count==0) P(rw); count++; V(mutex); 读文件 P(mutex); count--; if(count==0) V(rw); V(mutex); } }
            • 存在写进程“饥饿”情况
        • 写进程优先（读/写公平法）
          • int count=0; semaphore mutex=1; semaphore rw=1; semaphore w=1; writer(){ while(1){ P(w); P(rw); 写文件 V(rw); V(w); } } reader(){ while(){ P(w); P(mutex); if(count==0) P(rw); count++; V(mutex); V(w); 读文件 P(mutex); count--; if(count==0) V(rw); V(mutex); } }
      • 哲学家进餐问题（5名哲学家）
        • 一般算法
          • semaphore chopstick[5]={1,1,1,1,1} Pi(){ do{ P(chopstick[i]); P(chopstick[(i+1)%5]); 进餐 V(chopstick[i]); V(chopstick[(i+1)%5]); 思考 } while(1); }
        • 防止死锁的限制条件
          • 至多允许4名哲学家同时进食
          • 仅当一名哲学家左右两边的筷子都可用时，才允许他拿起筷子
          • 对哲学家顺序编号，奇数号先拿左筷子，偶数号先拿右筷子
        • 如果加上座位信号量seat，初值应为筷子数减1
    • 管程
      • 管程的定义
        • 代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序
          • 由编程语言实现，编译器提供支持
        • 组成
          • 管程的名称
          • 局部于管程内部的共享数据结构说明
          • 对该数据结构进行操作的一组过程（或函数）
          • 对局部于管程内部的共享数据结构设置初始值的语句
        • 示例
          • monitor Demo{ 共享数据结构 S; init_code(){ S=5; } take_away(){ S--; · · · } give_back(){ S++; · · · } }
      • 条件变量
        • 当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，若该进程不释放管程，则其他进程无法进入管程。阻塞原因即为条件变量 condition
        • 对条件变量 x 的操作
          • x.wait
            • 当x对应条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程
          • x.signal
            • x对应条件发生了变化，调用x.signal，唤醒一个因x条件而阻塞的进程
          • wait与signal操作不一定需要严格配对
        • 示例
          • monitor Demo{ 共享数据结构 S; condition x; init_code(){· · · } take_away(){ if(S<=0) x.wait(); · · · } give_back(){ 归还资源，做一系列相应处理 if(有进程等待) x.signal(); } }
        • 条件变量是“没有值”的，仅实现了“排队等待”功能；信号量是“有值”的
  • 死锁
    • 死锁的概念
      • 死锁的定义
        • 指多个进程因竞争资源而造成的一种僵局（互相等待对方手中的资源），使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进
      • 死锁与饥饿
        • 发生饥饿的进程可以只有一个；死锁是因循环等待对方手里的资源而导致，发生死锁的进程必然大于等于两个
        • 发生饥饿的进程可能处于就绪态；发生死锁的进程必定属于阻塞态
      • 死锁产生的原因
        • 系统资源的竞争
        • 进程推进顺序非法
          • 请求或释放资源的顺序不当
          • 信号量使用不当
      • 死锁产生的必要条件
        • 必须同时满足4个条件
          • 互斥条件
          • 不可剥夺条件
          • 请求并保持条件
          • 循环等待条件
      • 死锁的处理策略
        • 要求
          • 为使系统不发生死锁，必须设法破坏产生死锁的4个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复
        • 处理策略
          • 死锁预防
            • 设置某些限制条件，产生死锁的破坏必要条件
            • 可以确保系统不发生死锁
          • 避免死锁
            • 在资源的动态分配中，用某种方法防止系统进入不安全状态
          • 死锁的检测与解除
            • 无需采取任何限制性措施，允许发生死锁
            • 通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁
          • 比较
            • 并发性从大到小：死锁检测 >死锁避免>死锁预防
    • 死锁预防
      • 破坏互斥条件
      • 破坏不可剥夺条件
      • 破坏请求并保持条件
        • 静态分配法
          • 进程在运行前一次申请完它所需要的全部资源
            • 该分配方式不会让进程部分地占有资源
            • 会导致“饥饿”
        • 允许进程只获得运行初期所需的资源后，便开始运行，运行过程中逐步释放已分配给自己且使用完毕的资源后，才能请求新资源
      • 破坏循环等待
        • 顺序资源分配法
          • 对资源进行编号，分配时只能按照编号从大到小（或从小到大）的顺序分配
    • 死锁避免
      • 系统安全状态
        • 指系统能按某种决策会给你推进顺序（P1, P2, · · · , Pn）为每个进程Pi分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成
          • 此时称P1, P2, · · · , Pn为安全序列（可能有多个）
          • 若系统无法找到一个安全序列，则称系统处于不安全状态
        • 若x系统处于安全状态，则一定不会发生死锁；进入不安全状态，则可能发生死锁
      • 银行家算法
        • 数据结构描述（n个进程，m类资源）
          • 可利用资源向量 Available
            • Available[j] = K
              • 此时系统中有K个Rj类资源可用
          • 最大需求矩阵 Max
            • Max[i,j] = K
              • 表示进程Pi需要Rj类资源的最大数量为K
          • 分配矩阵 Allocation
            • Allocation[i,j] = K
              • 表示进程Pi当前已分得Rj类资源的数量为K
          • 需求矩阵 Need
            • Need[i.j] = K
              • 表示进程Pi还需要Rj类资源的数量为K
          • Need = Max - Allocation
        • 算法描述
          • 设 Requesti 是进程 Pi 的请求向量
            • Requesti[j] = K 表示进程 Pi 需要 j 类资源 K 个
          • 当进程 Pi 发出请求后，系统按下述步骤检查
            • ① Requesti[j] ≤ Need[i,j]
              • 否则认为出错
            • ② Requesti[j] ≤ Available[i,j]
              • 否则，表示尚无足够资源，Pi 必须等待
            • ③系统尝试将资源分配给 Pi
              • Available = Available - Request
              • Allocation[i,j] = Allocation[i,j] + Requesti[j]
              • Need[i,j] = Need[i,j] - Requesti[j]
            • ④系统执行安全性算法，检查资源分配后，系统是否处于安全状态
              • 若安全，才正式将资源分配给进程
              • 否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程等待
        • 只要保证系统中进程申请的最大资源数小于或等于实际资源数，就一定存在一个安全序列
          • 即任何时刻都能保证至少有一个进程可以得到所需的全部资源
      • 安全性算法
        • 设置工作向量 Work，表示系统中剩余可用资源数量，有m个元素，在执行安全性算法前，零Work=Available
        • 步骤
          • ①初始时安全序列为空
          • ②从Need矩阵中找出符合下面条件的行
            • 该行对应进程不在安全序列中，且该行小于等于Work向量
              • 找到，将对应的进程加入安全序列
              • 找不到，执行步骤④
          • ③进程Pi进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源
            • Work = Work + Allocation[i]，返回步骤②
          • ④若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态
    • 死锁检测和解除
      • 死锁检测
        • 资源分配图
          • 组成
            • 圆圈
              • 表示一个进程
            • 框
              • 表示一类资源
              • 框中的一个圆表示该类资源中的一个资源
            • 请求边
              • 从进程到资源的有向边
            • 分配边
              • 从资源到进程从有向边
          • 简化方法
            • 在资源分配图中找出既不阻塞又不孤立的进程Pi，消去它所有的请求边和分配边，使之成为孤立节点
              • 判断某种资源是否有空闲，应用它的资源数减去它在资源分配图中的出度
            • 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程
          • 若能通过简化消去所有的边，则称该图是可以完全简化的
          • S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的
            • 死锁定理
      • 死锁解除
        • 资源剥夺法
          • 挂起某些死锁进程，并抢占他的资源，将这些资源分配给其他的死锁进程
        • 撤销进程法
          • 强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源
        • 进程回退法
          • 让一个或多个死锁进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺
            • 要求系统保持进程的历史信息，设置还原点
• 内存管理
  • 内存管理概念
    • 内存管理的基本原理和要求
      • 内存管理的主要功能
        • 内存空间的分配与回收
          • 对主存的访问是以字节或字位单位的，分配单位需根据内存管理方式来确定
        • 地址转换
        • 内存空间的扩充
        • 内存共享
        • 存储保护
      • 逻辑地址与物理地址
        • 相对地址
          • 编译后，每个目标模块都从0号单元开始编址
        • 逻辑地址空间
          • 链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构建统一的从0号单元开始编址的逻辑地址空间
          • 不同进程可以有相同的逻辑地址
        • 物理地址空间
          • 指内存中物理单元的集合
          • 地址重定位
            • 当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址
        • 内存管理部件（MMU）
          • 操作系统通过MMU将进程使用的逻辑地址转换为物理地址
          • 逻辑地址通过页表映射到物理内存，页表由操作系统维护并被处理器使用
      • 程序的链接与装入
        • 将用户源程序变为可在内存中执行的程序步骤
          • 编译
            • 有编译程序将用户源代码编译成若干目标模块
          • 链接
            • 由链接程序将编译后形成的一组目标模块，以及他们所需的库函数链接在一起，形成一个完整的装入模块
            • 链接方式
              • 静态链接
                • 在程序运行之前，现将各目标模块及他们所需的库函数链接成一个完整的装入模块，以后不在拆开
                • 问题
                  • 修改相对地址，编译后的所有目标模块都是从0开始的相对地址，当链接成一个装入模块时要修改相对地址
                  • 变换外部调用符号，将每个模块中所用的外部调用符号也都变化为相对地址
              • 装入时动态链接
                • 将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式
                • 便于修改和更新，便于实现对目标模块的共享
              • 运行时动态链接
                • 在程序执行中需要某目标模块时，才对它进行链接
                • 能加快程序的装入过程，还可节省内存空间
          • 装入
            • 由装入程序将装入模块装入内存运行
            • 装入方式
              • 绝对装入
                • 只适用于单道程序环境
                • 程序中的逻辑地址与实际内存地址完全相同
                • 通常情况下在程序中采用的时符号地址，编译或汇编时在转为绝对地址
              • 可重定位装入（静态重定位）
                • 装入模块的始址通常都是从0开始，程序中使用的指令和数据的地址都是相对于始址而言的逻辑地址
                • 在装入对目标程序的相对地址的修改过程称为重定位，地址转换通常是在进程装入时依次完成的
                  • 当一个作业装入内存时，必须给它分配要求的全部内存空间，否则无法装入
                  • 作业一旦进入内存，整个运行期间就不能再内存中移动，也不能再申请内存空间
                • 固定分区方式可以采用静态重定位
              • 动态运行时装入（动态重定位)
                • 装入程序将装入模块装入内存后，将地址转换推迟到程序真正要执行才进行
                • 重定位寄存器
                  • 存放装入模块的起始地址
                • 优点
                  • 可以将程序分配到不连续的存储区
                  • 在程序运行前只需装入它的部分代码即可，在程序运行期间，根据需要动态申请分配存储
                  • 便于程序段的共享
                • 过程依赖于
                  • 可重定位装入程序
                  • 重定位寄存器
                  • 地址变换机构
      • 进程的内存映像
        • 组成要素
          • 代码段
            • 程序的二进制代码，只读的，可被多个进程共享
          • 数据段
            • 包括全局变量和静态变量
          • 进程控制块
            • 存放在系统区
          • 堆
            • 存放动态分配的变量
              • 通过调用malloc函数动态的向高地址分配空间
          • 栈
            • 用来实现函数调用
              • 从用户空间的最大地址往低地址方向增长
        • 映像
          • 只读代码段
            • .init
              • 程序初始化时调用的_init函数
            • .text
              • 用户程序的机器代码
            • .rodata
              • 只读数据
          • 读/写数据段
            • .data
              • 已初始化的全局变量和静态变量
            • .bss
              • 未初始化及所有初始化为0的全局变量和静态变量
      • 内存保护
        • 确保每个进程都有一个单独的内存空间
          • 需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响
        • 方法
          • 在CPU中设置一对上、下限寄存器
            • 存放用户进程在主存中的下限和上限地址
            • 每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断是否越界
          • 采用
            • 重定位寄存器（基地址寄存器）
              • 存放进程的起始物理地址
              • 用来“加”，用来地址转换
            • 界地址寄存器（限长寄存器）
              • 存放进程的最大逻辑地址
              • 用来“比”，判断是否越界
            • 必须使用特权指令加载
      • 内存共享
        • 可重入代码（纯代码）
          • 允许多个进程同时访问但不允许任何进程修改的代码
          • 通过动态链接的方式将所需的程序段映射到相关进程中去，从而减少了对程序段的调入/调出，减少了对换次数
        • 内存映射文件
      • 内存分配与回收
        • 单一连续分配->固定分区分配
          • 操作系统由单道程序向多道发展
        • 固定分区分配->动态分区分配
          • 适应不同大小的程序要求
        • 连续分配方式->离散分配方式（页式存储管理）
          • 提高内存利用率
        • 分段存储管理
          • 满足用户在编程和使用方面的要求
    • 连续分配管理方式
      • 连续分配方式是指为一个用户程序分配一个连续的内存空间
      • 分类
        • 单一连续分配
          • 内存被分为
            • 系统区
              • 仅供操作系统使用
              • 通常在低地址部分
            • 用户区
              • 仅有一道用户程序
          • 只能用于单用户、单任务的操作系统中
        • 固定分区分配
          • 将用户内存空间划分为若干固定大小的分区，每个分区只装入一道作业
          • 划分分区
            • • 分区大小相等
                • 缺乏灵活性
              • 分区大小不等
                • 多个较小分区、适量中等分区、少量大分区
            • 分区大小可以不同但预先固定
          • 分区使用表
            • 表项包括对应分区的始址、大小及状态（是否已分配）
          • 问题
            • 程序太大而放不进任何一个分区
            • 内部碎片
              • 当程序小于固定分区大小时，也要占用一个完整的分区，存在空间浪费
        • 动态分区分配
          • 基本原理
            • 可变分区分配
              • 进程装入内存时，根据进程的实际需要，动态地位置分配内存，并使分区的大小正好适合进程的需要
              • 系统中分区的大小和数量是可变的
            • 外部碎片
              • 随着时间的推移，内存中会产生越来越多的小内存块，导致利用率也随之下降
              • 可通过紧凑技术来克服
                • 操作系统不是地对进程进行移动和整理
                • 需要动态重定位寄存器的支持，且相对费时
            • 空闲分区链（表）
              • 按始址排序
              • 分配内存时
                • 检索空闲分区链，找到所需分区，若其大小大于请求大小，则从该分区中按请求大小分割一块空间分配给装入进程（若剩余部分小到不足以划分，则不需要分割），余下部分仍然留在空闲分区链中
              • 回收内存时
                • 系统根据回收分区的始址，从空闲分区链中找到相应的插入点
                • 四种情况
                  • 回收区与插入点的前一空闲分区相邻
                    • 将这两个分区合并，并修改前一分区表项的大小为两者之和
                  • 与后一空闲分区相邻
                    • 合并，修改后一分区表项的始址和大小
                  • 同时与前、后分区相邻
                    • 将三个分区合并，修改前一分区表项的大小为三者之和
                  • 没有相邻的空闲分区
                    • 新建一个表项，填写始址和大小，插入空闲分区链
          • 基于顺序搜索的分配算法
            • 将作业装入主存时，需要按照一定的分配算法从空闲分区链中选出一个分区分配
            • 按分区检索方式分
              • 顺序分配算法
                • 首次适应（First Fit）算法
                  • 空闲分区按地址递增的次序排列
                  • 每次分配内存，顺序查找到第一个能满足大小的空闲分区分配
                  • 保留了内存高地址部分的大空闲分区，但会使低地址部分出现许多小碎片，每次分配查找都需要经过这些分区，增加开销
                • 邻近适应（Next Fit）算法
                  • 循环首次适应算法
                  • 分配内存时从上次查找结束的位置开始继续查找
                  • 会导致内存高地址部分没有空闲大分区可用，通常比首次适应算法更差
                • 最佳适应（Best Fit）算法
                  • 空闲分区按容量递增的次序排列
                  • 每次分配，顺序查找第一个能满足大小的（最小）空闲分区
                  • 产生最多的外部碎片
                • 最坏适应（Worst Fit）算法
                  • 空闲分区按容量递减的次数排列
                  • 每次分配，顺序查找第一个能满足大小的（最大）空闲分区，从中分割一部分给作业
                  • 会导致没有大空闲分区可用
              • 索引分配算法
                • 思想
                  • 根据其大小对空闲分区分类，对每类空闲分区，单独设立一个空闲分区链，并设置一张索引表来管理这些空闲分区链
                • 分类
                  • 快速适应算法
                    • 首先根据进程的长度，在索引表中找到能容纳它的最小空闲分区链表，从链表中去下第一块进行分配
                    • 缺点
                      • 回收分区时，需要有效地合并分区，算法复杂开销大
                  • 伙伴系统
                    • 规定所有分区的大小均为2的k次幂（k为正整数）
                    • 当需要为进程分配大小为n的分区时（2i-1＜n≤2i），在大小为2i的空闲分区链中查找
                      • 找到
                        • 分配
                      • 不存在
                        • 在大小为2i+1的空闲分区链中查找，找到则将其等分为两个分区（称为一对伙伴），其中一个用于分配，另一个插入大小为2i的空闲分区链，找不到则向分区大小更大的空闲分区链中查找，直到找到为止
                    • 回收时，需要将相邻的空闲伙伴分区合并成更大的分区
                  • 哈希算法
                    • 根据空闲分区链的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应空闲分区链的头指针
                    • 分配时通过所需分区的大小，通过哈希函数计算得到哈希表中的位置，从中得到相应的空闲分区链
    • 基本分页存储管理
      • 思想
        • 将内存空间分为若干固定大小的分区，称为页框、页帧或物理块
        • 进程的逻辑地址空间页分为与块大小相等的若干区域，成为页或页面
        • 操作系统以页框为单位为各个进程分配内存空间
      • 与固定分区技术的对比
        • 相同
          • 不产生外部碎片
        • 不同
          • 块的大小相对分区要小很多，进程页按照块进行划分
          • 进程运行时按块申请主存可用空间并执行
          • 进程只会在最后一个不完整的块申请主存块空间时，才产生内部碎片（也称页内碎片）
            • 平均每个进程产生半个块大小的内部碎片
      • 基本概念
        • 页面和页面大小
          • 页号和页框号一一对应
            • 页号
              • 进程的逻辑地址空间中每个页面有一个编号
            • 页框号
              • 内存空间中的页框的编号
          • 为方便地址转换，页面大小应是2的整数次幂
            • 过小会使进程页面数过多，页表过长，占用大量内存，增加硬件地址转换开销，降低页面换入/换出的效率
            • 过大会使页内碎片增多，降低内存的利用率
        • 地址结构
          • 页号 P
          • 页内偏移量 W
        • 页表
          • 为了便于找到进程的每个页面在内存中存放的位置，系统为每个进程建立了一张页面映射表
          • 页表项
            • 每个页面对应一个页表项
            • 由页号和块号组成
          • 实现从页号到物理块号的地址映射
      • 基本地址变换机构
        • 页表寄存器（PTR）
          • 存放页表在内存的始址F和页表长度M
        • 变换过程（页面大小L，逻辑地址A到物理地址E）
          • ①根据逻辑地址计算出
            • 页号 P = A/L
            • 页内偏移量 W = A%L
          • ②判断页号是否越界
            • 页号P ≥ 页表长度M
              • 越界中断
          • ③在页表中查询页号对应的页表项，确定页面存放的物理块号
            • 页号P对应的页表项地址 = 页表始址F + 页号P × 页表项长度
            • 取出页表项内容b，即为物理块号
          • ④计算物理地址
            • E = bL + W
              • 物理地址 = 页面在内存中的始址 + 页内偏移量
              • 始址 = 块号 × 块大小
        • 主要问题
          • 每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快
          • 每个进程引入页表，页表不能太大
      • 具有快表的地址变换机构
        • 快表（TLB）也称相联存储器
        • 地址变换过程
          • ①CPU给出逻辑地址，由硬件进行地址转换，将页号与快表中的所有页号进行比较
          • ②过找到匹配的页号，直接从中取出与该页对应的物理块号，与页内偏移量拼接形成物理地址
          • ③未找到，需要访问内存中的页表，获取物理地址。找到页表项后，应同时将其存入快表
      • 两级页表
        • 逻辑地址空间格式
          • 一级页号或页目录号 | 二级页号或页号 | 页内偏移
        • 外层页表寄存器（页目录基址寄存器）
          • 用于存放页目录始址
        • 访存过程（3次访存）
          • ①将逻辑地址中的页目录号作为页目录的索引，找到对应页表的始址
          • ②再用二级页号作为页表分页的索引，找到对应页表项
          • ③从页表项获得物理地址，访问内存单元
    • 基本分段存储管理
      • 分段
        • 分段系统将用户进程的逻辑地址空间划分为带下不等的段
          • 段内要求连续，段间不要求连续
        • 逻辑地址结构
          • 段号S | 段内偏移量W
      • 段表
        • 段表项
          • 段号 | 段长 | 本段在主存的始址
      • 地址变换机构
        • 段表寄存器
          • 段表始址 F
          • 段表长度 M
        • 地址变换过程（从逻辑地址A到物理地址E）
          • ①从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W
          • ②判断段号是否越界
            • 段号S > 段表长度M
              • 越界中断
          • ③在段表中查询段号对应段表项，取出段表项中的段长C
            • 段号S对应段表项地址 = 段表始址F + 段号S × 段表项长度
            • 若W≥C
              • 越界中断
          • ④取出段表项中该段的始址b，计算物理地址用于访存
            • E = b + W
      • 分页和分段的对比
        • 目的
          • 页是信息的物理单位
            • 分页主要为了提高内存利用率
            • 用户不可见
          • 段是信息的逻辑单位
            • 分段是为了更好地满足用户需求，用户可按照逻辑关系将程序划分为若干段
            • 用户可见
        • 大小
          • 页的大小固定，由系统决定
          • 段的大小不固定，取决于用户所编写的程序
        • 维数
          • 分页管理的地址是一维的
          • 分段管理的地址空间是二维的
            • 每段的长度不固定，无法送过除法得出段号，无法通过求余得出段内偏移，所以一定要显示给出段号和段内偏移
        • 系统给用户提供的物理地址空间位总空间大小减去页表或段表的长度，页表或段表的长度不能确定，所以提供物理空间大小也不确定
        • 查找页表的工作是由硬件自动完成的，不需要操作系统或其他软件的干预；段表项中的内容，如段的基地址、长度等信息的具体解读和合法性检查，通常需要软件（操作系统内核）参与
      • 段的共享与保护
        • 共享段表
          • 所有共享的段都在共享段表中占一个表项
          • 表项记录了共享段的短号、段长、内存始址、状态（存在）位、外存始址和共享计数器count等
            • 共享计数器count记录有多少进程正在共享该段，当count=0时才回收该段所占的内存区
        • 对于一个共享段，在不同的进程中可以具有不同的段号，每个进程用自己进程的段号去访问该共享段
        • 为了防止程序在执行时修改共享代码，在每个进程中都必须配以局部数据区，将在执行过程中可能改变的部分复制到数据区，这样就可以对该数据区中的内容进行修改
        • 保护方法
          • 存取控制保护
          • 地址越界保护
    • 段页式存储管理
      • 在段页式系统中，进程的地址空间首先被分成若干逻辑段，每段有自己的段号，然后将各段分成大小固定的页
      • 逻辑地址
        • 段号S | 页号P | 页内偏移量W
      • 地址变换
        • 系统为每个进程建立一张段表，每个段对应一个段表项
          • 段表项至少包含段号（隐含）、页表长度和页表始址
          • 每个段有一张页表
            • 页表项至少包含页号（隐含）和块号
        • 段表寄存器
          • 指出进程的段表始址和段表长度
        • 过程
          • 首先通过段表查到页表始址，然后通过页表找到物理块号，形成物理地址用于访存
        • 可以使用快表来加速查找，其关键字有段号、页号组成，值是对应的物理块号和保护码
  • 虚拟内存管理
    • 虚拟内存的基本概念
      • 传统存储管理方式的特征
        • 一次性
          • 作业必须一次性全部装入内存后，才能开始运行
        • 驻留性
          • 作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束
      • 局部性原理
        • 时间局部性
        • 空间局部性
      • 虚拟存储器的定义和特征
        • 定义
          • 基于局部性原理，在程序装入时，仅需将程序当前运行要用到的少数页面（或段）装入内存，而将其余部分暂留在外存，便可启动程序执行
          • 请求调页（或请求调段）
            • 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息调入内存，然后继续执行程序
          • 页面置换（或段置换）
            • 当内存空间不够时，由操作系统负责将内存中暂时不用的信息换出到外存，从而腾出空间存放将要调入内存的信息
        • 特征
          • 多次性
            • 最重要的特征
            • 无须在作业运行时一次性全部装入内存
          • 对换行
            • 在作业运行时无须一直常驻内存
          • 虚拟性
            • 实现虚拟存储器的最重要目标
            • 从逻辑上扩充了内存的容量
      • 虚拟存储技术的实现
        • 实现方式
          • 请求分页存储管理
          • 请求分段存储管理
          • 请求段页式存储管理
        • 需要的支持
          • 一定容量的内存和外存
          • 页表基址（或段表机制）
            • 作为主要数据结构
          • 中断机制
            • 当用户程序需要访问的部分尚未调入内存时，产生中断
          • 地址变换机构
            • 逻辑地址到物理地址的变换
      • 在虚拟存储系统中，作业的编址空间一般由地址总线宽度决定，不是任意大
    • 请求分页管理方式
      • 页表机制
        • 请求分页系统中的页表项
          • 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址
          • 相比基本分页系统增加4个字段
            • 状态位P（有效位或合法位）
              • 标记该页是否已调入内存，供程序访问时参考
              • 决定了是否会发生页面故障
            • 访问字段A
              • 记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问
                • 供置换算法换出页面时参考
            • 修改位M
              • 标记该页在调入内存后是否被修改过
                • 决定换出时是否写回外存
            • 外存地址
              • 记录该页在外存的存放地址
                • 通常是物理块号，供调入该页时参考
      • 缺页中断机构
        • 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，请求操作系统的缺页中断处理程序处理
          • 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列
          • 内存中有无空闲页框
            • 有，则为进程分配一个页框，将所缺页面存外存装入该页框，并修改页表中相应的表项
            • 无，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则还要将其写回外存
        • 与一般中断的比较
          • 相同
            • 同样要经历保护CPU、分析中断原因、转入相应处理程序、恢复CPU环境等
          • 不同
            • 在指令执行期间而非一条指令执行完后产生和处理中断，属于内部异常
            • 一条指令在执行期间可能产生多次缺页中断
      • 地址变换机构
        • 请求分页系统的地址变换过程
          • ①先检索快表
            • 命中
              • 从相应表项中取出该页的物理块号，修改页表项中的访问位，对于写指令还要将修改位置1
            • 未命中
              • 到页表中查找
                • 页面在内存中
                  • 从相应表项中取出物理块号，并将该页表项写入快表，若快表已满，需采用某种算法替换
                • 页面不在内存中
                  • 缺页中断处理，请求系统将该页从外存换入内存，页面被调入内存后，有操作系统负责奉行页表和快表，并获得物理块号
          • ②利用得到的物理块号和页内地址拼接形成物理地址，用以访存
        • 在多级页表中，若快表命中，则只需要一次访存操作
    • 页框分配
      • 驻留集大小
        • 驻留集
          • 给一个进程分配的页框的集合就是这个进程的驻留集
        • 助留集越小，驻留在内存中的进程就越多，可以提高多道程序的并发度，但分配给每个进程的页框太少，会导致缺页率较高，CPU需耗费大量时间来处理缺页
        • 助留集越大，当分配给进程的页框超过某个数量时，在为进程增加页框对缺页率的改善是不明显的，反而浪费内存空间，并导致多道程序的并发度下降
      • 内存分配策略
        • 固定分配局部置换
          • 为每个进程分配固定数量的物理块，在进程运行期间都不改变
          • 局部置换
            • 若进程在运行中发生缺页，则只能从分配给改进程在内存的页面中选出一页换出，然后再讲所缺页面调入
          • 评价
            • 难以确定应为每个进程分配的物理块数
        • 可变分配全局置换
          • 先为每个进程分配一定数量的物理块，在进程运行期间可根据情况适当低增加或减少
          • 全局置换
            • 若进程在运行中发生缺页，则系统可以从全部进程的所有页面中选取页面进行置换
          • 评价
            • 比固定分配局部置换更灵活
            • 会盲目地给进程增加物理块
        • 可变分配局部置换
          • 为每个进程分配一定数量的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选一页换出
          • 若进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直至该进程的缺页率趋于适当程度
          • 若进程在运行中的缺页率特别低，则可适当减少分配给该进程的物理块，但不能引起明显的缺页率增加
          • 评价
            • 保证系统不会过多调页，页保持了系统的多道程序并发能力
            • 实现复杂和开销较大，对比频繁换入/换出浪费的计算机资源，是值得的
        • 确定进程运行所需的最少页框数时，需要考虑的指标是 指令系统的寻址方式
      • 物理块调入算法
        • 平均分配算法
          • 将系统中所有可供分配的物理块平均分配给各个进程
        • 按比例分配算法
          • 根据进程的大小按比例分配物理块
        • 优先权分配算法
          • 为重要和紧迫的进程分配较多的物理块
      • 调入页面的时机
        • 预调页策略
          • 预测不久之后可能被访问的页面，将它们预先调入内存
            • 目前预测成功率仅约50%
          • 主要用于进程的首次调入，有程序员指出应预先调入哪些页
        • 请求调页策略
          • 进程在运行中需要访问的页面不在内存，便提出请求
          • 目前的虚拟预调页大多采用此策略
      • 从何处调入页面
        • 系统中的外存分为两部分
          • 文件区
            • 用于存放文件
            • 采用离散分配方式
          • 对换区（交换区）
            • 用于存放对换页面
            • 采用连续分配方式
        • 三种情况
          • 系统拥有足够的对换区空间
            • 在进程运行前需将与该进程有关的文件从文件区复制到对换区
            • 全部从对换区调入所需页面，以提高调页速度
          • 系统缺少足够的对换区空间
            • 凡是不会被修改的文件都直接从文件区调入
            • 可能被修改的部分，将它们换出时必须放在对换区，后续需要时再从对换区换入
          • UNIX方式
            • 与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入
            • 曾经运行过但又被换出的页面，因为放在对换区，下次调入时应从对换区调入
            • 进程请求的共享页面若被其他进程调入内存，则不需要再从对换区调入
      • 如何调入页面
    • 页面置换算法
      • 最佳（OPT）置换算法
        • 选择淘汰的页面是以后用不使用的页面，或是在最长时间内不再访问的页面
        • 性能最好，但无法实现
      • 先进先出（FIFO）页面置换算法
        • 选择最早进入内存的页面淘汰
        • Belady异常
          • 为进程分配的物理块增多，缺页次数不减反增的异常现象
          • 只有FIFO算法可能出现
        • 算法实现简单，性能较差
      • 最近最久未使用（LRU）置换算法
        • 该算法为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间
        • 淘汰页面时选择现有页面中值最大的页面
        • 性能较好，实现需要寄存器和栈的硬件支持，开销较大
          • 需要对所有的页进行排序
      • 时钟（CLOCK）置换算法
        • 简单的CLOCK算法
          • 为每个页面设置一个访问位，当某页首次被装入或被访问时，其访问位置为1
          • 算法将内存中的页面链接成一个循环队列，并有一个替换指针与之关联。当某一页被替换时，该指针被设置指向被替换页面的下一页
          • 在选择淘汰一页时，只需检查页面的访问位
            • 若为0
              • 就选择该页换出
            • 若为1
              • 将它置为0，暂不换出，给与该页第二次驻留内存的机会
              • 再依次顺序检查下一个页面
              • 当检查到最后一个页面，且访问位为1时，则返回到队首去循环检查
        • 改进型CLOCK算法
          • 针对于修改过的页面，替换代价更大，增加了置换代价——修改位
          • 选择页面换出时，优先考虑既未使用过又未修改过的页面
          • 四种类型的页面（访问位A，修改位M）
            • 1类 A=0，M=0
              • 最佳淘汰页
            • 2类 A=0，M=1
              • 次佳淘汰页
            • 3类 A=1，M=0
            • 4类 A=1，M=1
          • 算法执行过程
            • ①从指针的当前位置开始，扫描循环队列
              • 将遇到的第一个1类页面作为选中的淘汰页
              • 扫描期间不改变访问位A
            • ②若第①步未找到淘汰页，则进行第二轮扫描
              • 将所有扫描过的页面访问位都置0
              • 将遇到的第一个2类页面作为淘汰页
            • ③若②未找到淘汰页，重复从①开始
    • 抖动和工作集
      • 抖动（颠簸）
        • 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出内存
      • 工作集
        • 在某段时间间隔内，进程将要访问的页面集合
        • 由时间t和工作窗口△确定
          • 工作集包含t时刻最近△次访问过的页面
    • 页框回收
      • 页面缓冲算法
        • 影响页面换入/换出效率的因素主要包括
          • 对页面进行置换的算法
          • 将已修改的页面写回磁盘的频率
          • 将磁盘内容读入内存的频率（缺页率）
        • 算法
          • 在原页面置换算法的基础上增设已修改页面链表，保存已修改且需要被换出的页面，等被换出的页面数量到达一定值时，再一起换出磁盘，以减少页面换出的开销
        • 主要特点
          • 显著降低换入/换出的频率，是磁盘的I/O开销大为减少，进而减少页面换入/换出的开销
            • 此时，若采用一种较简单的置换策略（如FIFO）时，不需要特殊硬件支持
        • 为了显著降低内存换入/换出的频率，在内存中设置了一下两个链表
          • 空闲页面链表
          • 修改页面链表
      • 页框回收
        • 不可回收页框
          • 属于内核的大部分页框（如内核栈、内核代码段、内核数据段和大部分内核使用的页框）
        • Linux内核中，设置了一个负责页面换出的守护进程kswapd
          • 它定期检查内存的使用情况，当空闲页框数量少于特定的阈值时，便发起页框回收操作
    • 内存映射文件
      • 操作系统向应用程序提供的一个系统调用，它与虚拟内存有些相似，在磁盘文件与进程的虚拟地址空间之间建立映射关系
        • 实现了页面到磁盘块的映射
      • 进程通过该系统调用，将一个文件映射到其虚拟地址空间的某个区域，之后就能用访问内存的方式来读/写文件
        • 将一个文件当做内存中的一个大字符数组来访问，而不通过文件I/O来访问
        • 磁盘文件的读/写由操作系统来完成，对进程透明
        • 在映射进程的页面时，不会实际读入文件的内容，只在访问页面时才被每次一页地读入
        • 当进程退出或关闭文件映射时，所有被改动的页面才被写回磁盘文件
      • 共享内存多数是通过映射相同文件到通信进程的虚拟地址空间来实现的
        • 当多个进程映射同一个文件时，各进程的地址空间都是相互独立的，但操作系统将对应的这些虚拟地址空间映射到相同的物理内存（用页表实现）
      • 好处
        • 使程序员的编程更简单，已建立映射的文件，只需按访问内存的方式进程读/写
        • 方便多个进程共享同一个磁盘文件
    • 虚拟存储器性能影响因素
      • 缺页率是影响虚拟存储器性能的主要因素
        • 缺页率影响因素
          • 页面大小
          • 分配给进程的物理块数（工作集大小）
          • 页面置换算法
          • 进程的多少
          • 程序的编制方法
            • 编写程序的局部化程度越高，执行时的缺页率越低
            • 如，若存储采用按行存储，则访问时就要尽量采用相同的方式访问
    • 地址翻译
    • 补充
      • 虚拟存储技术是补充内存逻辑空间的技术
      • 用于交换的磁盘利用率接近饱和，CPU和其他设备的利用率较低，说明在任务作业不多的情况下交换操作非常频繁，物理内存严重短缺
• 文件管理
  • 文件系统基础
    • 文件的基本概念
      • 文件（File）
        • 是以硬盘为载体存储在计算机上的信息集合
        • 文件是用户进行输入、输出的基本单位
      • 文件的定义
        • 数据项
          • 文件系统中最低级的数据组织形式
          • 分类
            • 基本数据项
              • 用于描述一个对象的某种属性的一个值
              • 是数据中的最小逻辑单位
            • 组合数据项
              • 有多个基本数据项组成
        • 记录
          • 一组相关的数据项的集合，用于描述一个对象在某方面的属性
        • 文件
          • 有创建者所定义、具有文件名的一组相关元素的几何
          • 分为
            • 有结构文件
              • 文件由若干个相似的记录组成
            • 无结构文件
              • 被视为一个字符流
              • 如二进制文件或字符文件
      • 文件的属性
        • 名称
          • 文件名称唯一
        • 类型
        • 创建者
        • 所有者
        • ID
        • 位置
          • 指向设备和设备上文件的指针
        • 大小
          • 文件当前大小，也可包含文件允许的最大值
        • 保护
          • 对文件进行保护的访问控制信息
        • 创建时间、最后一次修改时间和最后一次存取时间
      • 文件的分类
        • 按性质和用途
          • 系统文件
          • 用户文件
          • 库文件
        • 按文件中数据的形式
          • 源文件
          • 目标文件
          • 可执行文件
        • 按存取控制属性
          • 可执行文件
          • 只读文件
          • 读/写文件
        • 按组织形式和处理方式
          • 普通文件
          • 目录文件
          • 特殊文件
            • UNIX操作系统中，所有设备都被视为特殊文件，UNIX操作系统控制和访问外部设备的方式和访问一个文件的方式是相同的
    • 文件控制块和索引节点
      • 文件控制块（FCB）
        • 用来存放控制文件需要的各种信息的数据结构
          • 以实现按名存取
        • 文件目录
          • FCB的有序集合，也被视为一个文件
        • FCB主要包含
          • 基本信息
            • 文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等
          • 存取控制信息
            • 文件主的存取权限、核准用户的存取权限以及一般用户的存取权限
          • 使用信息
            • 文件建立时间、上次修改时间等
      • 索引节点
        • 在文件目录中每个目录项仅由文件名和相应的索引节点号（或索引节点指针）构成
          • 不同目录下文件的文件名可以相同，所以在考虑系统创建最多文件数量时，只需考虑索引节点的个数
            • 创建文件数量上限 = 索引节点数量上限
        • 分类
          • 磁盘索引节点
            • 存放在磁盘上的索引节点，每个文件有一个唯一的磁盘索引节点
            • 主要包括
              • 文件主标识符
              • 文件类型
              • 文件存取权限
              • 文件的物理地址
              • 文件长度
              • 文件的链接技术
                • 在本文件系统中所有指向该文件的文件名的指针计数
              • 文件的存取时间
          • 内存索引节点
            • 当文件被打开时，要将磁盘索引节点复制到内存的索引节点中，以便以后使用
            • 增加了
              • 索引节点号
              • 状态
                • 指示i节点是否上锁或被修改
              • 访问计数
              • 逻辑设备号
              • 链接指针
                • 设置分别指向空闲链表和散列队列的指针
            • 文件链接计数变为0时，文件系统会释放相应的内存索引节点
    • 文件的操作
      • 文件的基本操作
        • 创建文件
          • 必要步骤
            • 为新文件分配外存空间
            • 在目录中为之创建一个目录项
        • 删除文件
          • 根据文件名查找目录，删除制定文件对应的目录项和文件控制块，回收文件所占用的存储空间（包括磁盘空间和内存缓冲区）
        • 读文件
          • 根据文件名查找目录，找到指定文件的目录项，从中得到被读文件在外存中的地址
          • 在目录项中，还有一个指针用于对文件进行读操作
        • 写文件
          • 查找目录，找到目录项，利用目录项中的写指针对文件进行写操作
          • 每当写操作发生，便更新写指针
      • 文件的打开与关闭
        • 文件的打开
          • 用户首次对某文件发出请求时
            • 需先利用系统调用open将该文件打开
              • open中的参数包含文件的路径名与文件名
              • read只需使用open返回的文件描述符，并不使用文件名作为参数
                • read参数：文件描述符fd，buf缓冲区首址，传送的字节数n
          • 打开文件表
            • 包含所有打开文件信息的表
          • 打开
            • 系统检索到制定文件的目录项后，将该目录项从外存复制到内存中的打开文件表的一个表目中，并将该表目的索引号（UNIX称为文件描述符，Windows称为文件句柄）返回给用户
              • 打开文件操作的主要工作是把指定文件的目录项复制到内存指定的区域
            • 当用户再次对该文件发出操作请求时，可通过索引号在打开文件表中查找到文件信息，节省大量检索开销
          • 当文件不再使用时，可利用系统调用close关闭它
            • 系统将从打开文件表中删除对应表目
          • 每个打开文件都具有如下关联信息
            • 文件指针
              • 系统跟踪上次的读/写位置作为当前文件位置的指针
              • 对打开文件的某个进程来说是唯一的，必须与磁盘文件属性分开保存
                • 对单个进程来说文件指针具有唯一性
                • 对多个进程同时打开一个文件，针对不同操作系统，可能是多个文件共享一个指针，也可能是每个文件拥有自己的指针
            • 文件打开计数
            • 文件磁盘位置
            • 访问权限
        • 文件的关闭
          • 两级表
            • 在多个进程可以同时打开文件的操作系统中
            • 整个系统表
              • 包含与进程无关的信息
                • 文件在磁盘上的位置、访问日期、文件大小等
              • 一旦有进程打开了一个文件，系统表就包含该文件的条目
              • 为每个文件关联一个打开计数器
                • 打开计数器为0时，可从系统表中删除相应条目
            • 每个进程表
              • 保存进程对文件的使用信息
                • 文件的当前读/写指针、文件的访问权限
                  • 多个进程打开一个文件时，读/写指针的位置不同
                • 并包含指向系统表中适当条目的指针
              • 当一个进程执行调用open时，只不过是在其打开文件表中增加一个条目，并指向系统表的相应条目
              • 进程不再使用某个文件时，利用系统调用close关闭它，会删除单个进程的打开文件表中的相应条目，系统表中相应的打开计数器会递减
      • 一旦完成对FCB在磁盘上的定位，系统就不再使用文件名
        • 文件名不必是打开文件表的一部分
        • 只要文件未被关闭，所有文件操作都是通过文件描述符来进行
    • 文件的逻辑结构
      • 从用户角度出发所看到的文件的组织形式
        • 而文件的物理结构是将文件存储在外存上的组织形式，是用户不可见的
      • 分类
        • 无结构文件
          • 最简单的文件组织形式，是由字符流构成的文件，也称流式文件
          • 长度以字节为单位
          • 访问
            • 通过读/写指针来指出下一个要访问的字节
            • 对记录的访问只能通过穷举搜索的方式
          • 如系统中运行的大量源程序、可执行文件、库函数等
        • 有结构文件
          • 有一个以上记录构成的文件，也称记录式文件
          • 根据各记录长度是否相等
            • 定长记录
              • 文件中所有记录的长度都是相同的，各数据项在记录中的相同位置，有相同长度
              • 检索记录速度快，方便用户对文件进行处理，广泛用于数据处理中
            • 变长记录
              • 文件中各记录的长度不一定相同
              • 检索记录只能顺序查找，速度慢
          • 按记录的组织形式
            • 顺序文件
              • 文件中的记录一个接一个的顺排列，记录可以是定长或变长
              • 记录排列结构
                • 串结构
                  • 个记录之间的顺序与关键字无关
                • 顺序结构
                  • 所有记录按关键字顺序排列
                  • 检索时可采用折半查找
              • 评价
                • 对记录进行批量操作，顺序文件效率最高
                • 对顺序存储设备，只有顺序文件才能被存储并有效的工作
                • 处理单个文件的场合，性能较差
            • 索引文件
              • 计算第i条记录相对于第1条记录的地址
                • 定长记录
                • 变长记录
              • 变长记录的顺序文件可以建立一张索引表
                • 为主文件的每个记录在索引表中分别设置一个索引表项，其中包含指向记录的指针和记录长度
                • 转变为对定长索引文件的随机检索
                • 增加存储开销
            • 索引顺序文件
              • 一级索引
                • 将变长记录顺序文件中的所有记录分为若干组，为文件建立一张索引表，为每组中的第一个记录建立一个索引项，包含该关键字和指针
                • N条记录
                  • 顺序查找，平局需要N/2次
                  • 索引顺序
                    • 将记录分为
                    • 平均需要
            • 直接文件或散列文件（Hash File）
              • 给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址
    • 文件的物理结构
      • 磁盘块
        • 磁盘中的存储单元
        • 大小通常与内存页面大小相同
        • 内存与磁盘之间的数据减缓都是以块为单位进行的
      • 文件的组织形式与存储介质特性有关
        • 如磁带只能顺序存取，磁盘可以随机存取
      • 连续分配
        • 要求每个文件在磁盘上占有一组连续的块
        • 评价
          • 优点
            • 支持顺序访问和直接访问
            • 顺序访问容易且速度快，文件所占用的块可能位于一条或几条相邻的磁道上，磁头的移动距离最小
              • 查询时间最短用于视频文件的随机播放可使播放性能最好
          • 缺点
            • 为文件分配连续的存储空间会产生很多外部碎片
            • 必须事先知道文件的长度，也无法满足文件动态增长的要求
            • 为保持文件的有序性，删除和插入记录时，需要对相邻的记录做物理上的移动
      • 链接分配
        • 优点
          • 消除磁盘的外部碎片，提高了利用率
          • 便于动态的为文件分配磁盘块
          • 文件的插入、删除和修改方便
        • 分类
          • 隐式链接
            • 除文件的最后一个盘块外，每个盘块都存有指向文件下一个盘块的指针，这些指针对用户是透明的
            • 缺点
              • 只支持顺序访问
              • 稳定性问题
                • 任何一个指针出问题，都会导致文件数据丢失
              • 耗费存储空间
            • 改进
              • 将几个盘块组成一个簇，按簇来分配
              • 提高查找速度，减少指针所占空间
              • 代价
                • 增加内部碎片
          • 显示链接
            • 文件分配表（FAT）
              • 将用于链接文件各个物理块的指针，显式地存放在内存的一张链接表中
              • 每个表项存放指向下一个盘块的指针
            • 评价
              • 优点
                • 支持顺序访问和直接访问
                • FAT在系统启动时就被读入内存，检索记录是在内存中进行的，提高检索速度，减少磁盘访问次数
              • 缺点
                • 占用内存空间
            • FAT的表项与物理磁盘块一一对应，并且可以用一个特殊的数字-1表示文件的最后一块，用-2表示这个磁盘块是空闲的（也可用-3，-4表示）
              • 因此FAT不仅记录了文件中各个块的先后连接关系，还标记了空闲的磁盘块
      • 索引分配
        • 思想
          • 将每个文件所有的盘块号集中地放在一起，当访问到某个文件时，将该文件对应的盘块号一起调入内存
        • 单级索引分配
          • 为每个文件分配一个索引块（表），将分配给该文件的所有盘块号都记录在该索引块中
          • 评价
            • 优点
              • 支持直接访问
              • 不产生内部碎片
            • 缺点
              • 增加了额外的存储空间开销
            • 主要问题
              • 每个文件必须有一个索引块
              • 当文件很小，仍为之分配一个索引块，索引块利用率低
              • 当文件很大，占用若干个索引块，通过链指针链接比较低效
        • 多级索引分配
          • 主索引
            • 为索引块再建立一级索引
          • 评价
            • 优点
              • 极大加快了对大型文件的查找速度
            • 缺点
              • 访问一个盘块是，需启动磁盘的次数随着索引级数的增加而增多
        • 混合索引分配
          • 较全面地照顾到小型、中型、大型和特大型文件
            • 小文件
              • 直接寻址
                • 最好能将它们每个盘块地址直接放入FCB
            • 中型文件
              • 单级索引分配
                • 一次间址
            • 大型或特大型文件
              • 两级和三级索引分配
          • UNIX系统采用分配方式（设有13个地址项）
            • 直接地址
              • i.addr(0)~i.addr(9)
            • 一次间接地址
              • i.addr(10)
            • 多次间接地址
              • 二次间址
                • i.addr(11)
              • 三次间址
                • i.addr(12)
    • 文件保护
      • 目的
        • 为了防止文件共享可能导致文件被破坏或未经核准的用户修改文件
      • 方式
        • 口令保护、加密保护、访问控制等
      • 访问类型
        • 可加以控制的访问类型
          • 读
          • 写
          • 执行
          • 添加
          • 删除
          • 列表清单
        • 一些高层的功能（对文件的重命名、复制、编辑等）通过系统程序调用底层系统调用来实现
        • 保护可以只在底层提供
      • 访问控制
        • 根据用户身份进行控制
        • 访问控制列表（ACL）
          • 实现基于身份访问的最为普通的方法
          • 为每个文件和目录增加一个ACL，以规定每个用户名及其所允许的访问类型
          • 精简的访问控制表采用
            • 拥有者
            • 组
              • 一组需要共享文件且具有类似访问的用户
            • 其他
          • 二进制位串
            • 表示的访问权限是这个文件所持有的，不是某个用户所持有的
            • 需要表示所有类别用户的访问权限
            • 描述文件权限的位数至少为
              • 用户类别数*访问权限类别数
        • 口令
          • 指用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应的口令，同时告诉允许共享该文件的其他用户
          • 用户请求访问时必须提供相应的口令
          • 评价
            • 时间和空间开销不多
            • 口令直接存在系统内部，不够安全
        • 密码
          • 用户对文件进行加密，文件被访问时需要使用密钥
          • 评价
            • 保密性强，节省了存储空间
            • 编码和译码要花费一定的时间
        • 口令和密码都是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型
        • 多级目录结构，不仅需要保护单个文件，还需要保护子目录内的文件
          • 需要提供目录保护机制
          • 目录与文件操作不同，需要不同的保护机制
      • 文件安全性管理等级
        • 系统级
          • 主要任务是不允许未经许可的用户进入系统，从而也防止了他人非法使用系统中的分类资源
            • 如注册和登录
        • 用户级
          • 对所有用户分类和对指定用户分配访问权
            • 系统将用户分为超级用户、系统操作员、一般用户
        • 目录级
          • 为了保护系统中各种目录而设计的，它与用户权限无关
        • 文件级
          • 通过系统管理员或文件主队文件属性的设置来控制用户对文件的访问
      • 存取控制矩阵
        • 用于多用户之间的存取权限保护
        • 存取控制矩阵是一个二维矩阵，行代表主体，列代表客体。矩阵中的每个元素表示某个主体对某个客体的访问权限
  • 目录
    • 目录的基本概念
      • 目录管理的基本要求
        • 按名存取
          • 从用户的角度看，目录在用户所需要的文件名和文件之间提供一种映射
        • 要提高对目录的检索速度
        • 提供用于控制访问文件的信息
          • 在多用户系统中，应允许多个用户共享一个文件
        • 应允许不同用户对不同文件采用相同的名字
          • 目录管理通过树形结构来解决和实现
    • 目录的操作
      • 搜索
      • 创建文件
      • 删除文件
        • 不删除非空目录
          • 删除时要先删除目录中的所有文件，并递归地删除子目录
        • 可删除非空目录
          • 目录中的问价和子目录被同时删除
      • 创建目录
      • 删除目录
      • 移动目录
      • 显示目录
        • 用户可以请求显示目录的内容
      • 修改目录
    • 目录结构
      • 单级目录结构
        • 在整个文件系统中只建立一张目录表，每个文件占一个目录项
        • 实现了“按名存取”，但查找速度慢、文件不允许重名、不便于文件共享
      • 两级目录结构
        • 文件目录分为
          • 主文件目录
            • 记录用户名及相应用户文件目录所在的存储位置
          • 用户文件目录
            • 记录该用户所有文件的FCB
        • 评价
          • 提高了检索速度，解决了多用户之间的文件重名问题，文件系统可以在目录上实现访问限制
          • 缺乏灵活性，不能对文件分类
      • 树形目录结构
        • 文件路径名
          • 由从根目录出发到所找文件通路上所有目录名和数据文件名用分隔符“/”链接而成
          • 当用户要访问某个文件时，用文件的路径名标识文件
        • 绝对路径
          • 从根目录出发的路径
        • 当前目录（工作目录）
        • 相对路径名
          • 从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成
        • 评价
          • 可以很方便地对文件进行分类，层次结构清晰，能够更有效地进行文件的管理和保护
          • 在树形目录中查找一个文件，需要按路径名逐级访问中间节点，增加了磁盘访问次数，影响查询速度
      • 无环图目录结构
        • 在属性目录结构的基础上增加一些指向同一节点的有向边，是整个目录成为一个有向无环图
        • 为每个共享节点设置一个共享计数器
          • 每当图中增加对该节点的共享链时加1
          • 每当用户提出删除该节点时减1
          • 共享计数器为0时才真正删除节点，否则仅删除请求用户的共享链
        • 评价
          • 方便地实现了文件的共享
          • 使得系统的管理更加复杂
    • 目录实现
      • 线性列表
      • 哈希表
    • 文件共享
      • 基于索引节点的共享方式（硬链接）
        • 将文件的物理地址和属性等信息不再放在目录项中，而是放在索引节点中，在目录中只设置文件名及指向相应索引节点的指针
          • 硬链接与文件共享一个索引节点，读写指针位置不一定相同，获得对应的文件描述符分别指向各自的用户打开文件表中的一项
        • 索引节点中有链接计数（引用计数）count
          • count=0时才删除该文件
      • 利用符号链实现文件共享（软链接）
        • 为使用户B能共享用户A中的一个文件F，可有系统创建一个LINK类型的新文件L，并将L写入用户B的目录，已实现B的目录与文件F的链接
          • 文件L中只含有被链接文件F的路径名
          • 类似与Windows中的快捷方式
        • 只有文件主菜拥有指向其索引节点的指针，共享该文件的其他用户只有该文件的路径名
        • 当文件主将一个共享文件删除之后，若其他用户有试图通过符号链去访问它时，则会访问失败，于是再将符号链删除
        • 评价
          • 每次访问共享文件时，都可能要多次地读盘
          • 符号链接也是一个文件，其索引节点也要耗费一定的磁盘空间
      • 硬链接的查找速度要比软链接快
    • 补充
      • 对文件的访问控制，常由用户访问权限和文件属性共同限制
  • 文件系统
    • 文件系统结构
      • 文件系统
        • 提供高效和便捷的磁盘访问，以便允许存储、定位、提取数据
      • 文件系统层次结构
        • I/O控制层
          • 包括设别驱动程序和中断处理程序
          • 在内存和磁盘系统之间传输信息
        • 基本文件系统
          • 向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块
            • 每个物理块由磁盘地址标识
            • 管理内存缓冲区，并保存各种文件系统、目录和数据块的缓存
        • 文件组织模块
          • 组织文件及其逻辑块和物理块
            • 可以将文件的逻辑块地址转换为物理块地址
            • 空闲空间管理器
        • 逻辑文件系统
          • 用于管理文件系统的中的元数据信息
            • 元数据包括文件系统的所有结构，而不包括实际数据
            • 管理目录结构
            • 通过文件控制块来维护文件结构
            • 负责文件保护
    • 文件系统布局
      • 文件系统在磁盘中的结构
        • 文件系统存放在磁盘上，多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统
        • 文件系统可能包含的信息
          • 启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等
        • 可能的文件系统布局
          • 主引导记录（MBR)
            • 位于磁盘的0号扇区
            • 用来引导计算机
              • MBR的后面是分区表
                • 给出每个分区的起始和结束地址
                • 表中的每一个分区被标记为活动分区
              • 当计算启动时，BIOS读入并执行MBR
                • MBR做的第一件事是确定活动分区，读入它的第一块，即引导块
          • 引导块
            • MBR执行引导块中的程序后，该程序负责启动该分区中的操作系统
            • 每个分区都是统一从一个引导块开始
              • 即使它不含有一个可启动的操作系统，也不排除以后会在该分区安装一个操作系统
          • 超级块
            • 包含文件系统的所有关键信息在计算机启动时，或在该文件系统首次使用时，超级快就会被读入内存
            • 超级块中的典型信息包括
              • 分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等
          • 文件系统中的空闲块的信息
          • i节点
          • 根目录
            • 存放文件系统目录树的根部
          • 文件和目录
      • 文件系统在内存中的结构
        • 内存中的信息用于管理文件系统并通过缓存能来提高性能，这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃
        • 结构的类型
          • 内存中的安装表（mount table）
            • 包含每个已安装文件系统分区的有关信息
          • 内存中的目录结构的缓存
            • 包含最近访问目录的信息
          • 整个系统的打开文件表
            • 包含每个打开文件的FCB副本、打开计数及其他信息
          • 每个进程的打开文件表
            • 包含进程打开文件的文件描述符（文件句柄），和指向整个系统的打开文件表中对应表项的指针
    • 文件存储空间管理
      • 卷（volume）
        • 包含文件系统的分区
        • 卷可以是磁盘的一部分，可以是整个磁盘，还可以是多个磁盘组成RAID集
        • 在一个卷中，文件区（存放文件数据的空间）和目录区（FCB的空间）是分离的
        • 卷在提供文件服务前，必须有对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块
      • 文件存储设备分成许多大小相同的物理块，并以块为单位交换信息
        • 文件存储设备的管理实质上是对空闲块的组织和管理，包括空闲块的组织、分配与回收等问题
      • 磁盘空闲块管理的方法
        • 空闲表法
          • 属于连续分配方式
            • 为每个文件分配一块连续的存储空间
          • 组织方式
            • 系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项
              • 包括
                • 表项序号
                • 该空闲区的第一个空闲盘块号
                • 该空闲区的空闲盘块数
                • · · ·
            • 将所有空闲区按其起始盘块号递增的次序排列
          • 盘块的分配
            • 与内存的动态分配类似，采用首次适应算法、最佳适应算法等
          • 盘块的回收
            • 类似于内存回收
              • 要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接，对相邻接者予以合并
          • 评价
            • 具有较高的分配速度，可减少访问磁盘I/O的频率
        • 空闲链表法
          • 分为
            • 空闲盘块链
              • 将磁盘上所有的空闲空间以盘块为单位拉成一条链
                • 每个盘块都有指向下一个空闲盘块的指针
              • 用户请求分配存储空间
                • 从链首开始，一次摘下适当数量的空闲盘块分配给用户
              • 用户释放存储空间
                • 将回收的盘块一次插入空闲盘块链的末尾
              • 评价
                • 优点
                  • 分配和回收一个盘块过程非常简单
                • 缺点
                  • 在为一个文件分配盘块时可能要重复操作多次，效率较低
                  • 空闲盘链很长
            • 空闲盘区链
              • 将磁盘上的所有空闲盘区拉成一条链，每个盘区包含若干相邻盘块
              • 分配盘区
                • 与内存的动态分区分配类似，通常采用首次适应算法
              • 回收盘区
                • 将回收区与相邻接的空闲盘区合并
              • 评价
                • 分配与回收的效率高，且空闲盘区链较短
                • 分配与回收过程比较复杂
          • 适用于离散分配，比较难得到连续空间
        • 位示图法
          • 利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上的所有盘块都有一个二进制位与之对应
          • 对应二进制位的值
            • 0
              • 对应的盘块空闲
            • 1
              • 已分配
          • 盘块的分配
            • ①顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位
            • ②将找到的一个或一组二进制位转换成与之对应的盘块号
              • 计算盘块号b（假设n为每行位数，找到的位在位示图i行j列）
                • b = n(i-1) + j
            • ③修改位示图
              • map[i, j] = 1
          • 盘块的回收
            • ①将回收盘块的盘块号转换成位示图中的行号和列号
              • i = (b-1) DIV n + 1
              • j = (b-1) MOD n + 1
            • ②修改位示图
              • map[i, j] = 0
          • 评价
            • 优点
              • 很容易在位示图中找到一个或一组相邻接的空闲盘块
              • 位示图很小，占用空间少，可保存在内存中，节省许多磁盘启动的开销
              • 占用外存空间的大小与当前空闲块数量无关
            • 问题
              • 位示图带下回随着磁盘容量的增加而增大，因此常用于小型计算机
        • 成组链表法
          • 思想
            • 每组（除最后一组）的第一块作为索引块，然后将这些索引块链接起来
              • 将空闲盘块分成若干组，每组的第一个盘块记录下一组的空闲盘块总数和空闲盘块号
              • 由各组的第一个盘块可以链接成一条链
              • 第一组的空闲盘块总数和空闲盘块号存在内存的专用栈中
                • 空闲盘块号栈
          • 盘块的分配
            • 根据空闲盘块号栈的指针，将与之对应的盘块分配给用户，同时移动指针，并将栈中的空闲盘块数减1
            • 若该指针指向的是栈底的盘块号，则在该盘块号对应的盘块中保存的是下一组空闲盘块号
              • 因此要将该盘块的内容读入栈，作为新的空闲盘块号栈的内容，并将原栈底盘块号对应的盘块分配出去（其中有用的数据以读入栈）
          • 盘块的回收
            • 将回收的盘块号存入空闲盘块号的顶部，同时移动指针，并将栈中的空闲盘块数加1
            • 当栈中的空闲盘块数已达100时，表明栈以满
              • 将现有栈中的100个空闲盘块号存入新回收的盘块，并将该新回收的盘块号作为新栈底，再将栈中空闲盘块数置为1
      • 表示空闲空间的位向量表和空闲盘块号栈，以及卷中的目录区、文件区划分信息都要存放在磁盘中，一般放在卷头的位置，在UNIX系统中称为超级块
        • 对卷中的文件进行操作前，超级块都要预先读入内存，并经常保持超级块与磁盘卷中超级块的一致性
    • 虚拟文件系统
      • VFS
        • 屏蔽了不同文件系统的差异和操作细节，向上为用户提供了文件操作的统一调用接口，而无需考虑具体的文件系统和实际的存储介质
      • 思想
        • 面向对象思想
        • 抽象出一个通用的文件系统模型，定义类通用文件系统都支持的接口
          • 新的文件系统只要支持并实现这些接口，即可安装和使用
      • 为了实现虚拟文件系统，系统抽象了四种对象类型
        • 超级块对象
          • 表示一个已安装（或称挂载）的特定文件系统
          • 操作方法
            • 分配inode
            • 销毁inode
            • 读inode
            • 写inode
            • . . .
        • 索引节点对象
          • 表示一个特定的文件
            • 索引节点和文件是一对一的关系
            • 只有当文件被访问时，才在内存中创建索引节点对象
          • 操作函数
            • 创建新索引节点
            • 创建硬链接
            • 创建新目录
            • . . .
        • 目录项对象
          • 表示一个特定的目录项
            • 是一个路径的组成部分
              • 包含
                • 指向关联索引节点的指针
                • 指向父目录和指向子目录的指针
            • 在磁盘上没有对应的数据结构
              • 在VFS遍历路径的过程中，逐个解析成目录项对象
        • 文件对象
          • 表示一个与进程相关的已打开文件
            • 可以通过调用open()打开一个文件，调用close()关闭一个文件
            • 文件对象和物理文件的关系类似于进程和程序
            • 包含
              • 与该文件相关联的目录项对象
              • 该文件的文件系统、文件指针
              • 该文件上的一系列操作函数
      • VFS对每个文件系统的所有细节进行抽象，使得不同的文件系统在系统中运行的进程看来都是相同的
      • VFS并不是一种实际的文件系统，只存在于内存中，不存在于任何外存空间，在系统启动时建立，在系统关闭时消亡
    • 文件系统挂载
      • 文件系统在进程使用之前必须先安装，也称挂载（Mounting）
      • 将设备中的文件系统挂载到某个目录后，就可通过这个目录来访问该设备上的文件（这里设备指逻辑上的设备）
• 输入/输出管理
  • I/O管理概述
    • I/O设备
      • 分类
        • 按信息交换的单位
          • 块设备
            • 磁盘、磁带等
            • 传输速率较高、可寻址
          • 字符设备
            • 交互式终端机、打印机等
            • 传输速率低，不可寻址
        • 按设备传输速率
          • 低速设备
            • 每秒几字节到几百字节
            • 键盘、鼠标等
          • 中速设备
            • 每秒数千字节至数万字节
            • 激光打印机等
          • 高速设备
            • 数百千字节至千兆字节
            • 磁盘、光盘等
        • 按设备的使用特性
          • 人机交互设备
          • 存储设备
          • 网络通信设备
        • 按设备的共享属性
          • 独占设备
            • 同一时间段只能由一个进程占用
          • 共享设备
            • 同一时间段内允许多个进程同时访问
              • 共享设备必须是可寻址和可随机访问的设备，否则不能保证数据的完整性和一致性
          • 虚拟设备
            • 通过SPOOLing技术将独占设备改造成共享设备，将一个物理设备变为多个逻辑设备，从而可将设备同时分配给多个进程
              • 引入虚拟设备是为了克服独占设备速度慢、利用率低的特点
      • I/O接口
        • CPU与设备之间的“桥梁”，以实现设备和计算机之间的数据交换
          • 接收发自CPU的命令，控制设备工作，使CPU能从繁杂的设备控制事务中解脱出来
        • 组成
          • 设备控制器与CPU的接口
            • 用于实现CPU与设备控制器之间的通信
            • 三类信号线
              • 数据线
                • 传送读/写数据、控制信息和状态信息
              • 地址线
                • 要访问I/O接口中的寄存器编号
              • 控制线
                • 读/写等控制信号
          • 设备控制器与设备的接口
            • 一个设备控制器可以连接一个或多个设备
              • 控制器中有一个或多个设备接口
                • 每个接口都可传输数据、控制和状态三种类型的型号
          • I/O逻辑
            • 用于实现对设备的控制
              • 通过一组控制线与CPU交互，对从CPU收到的I/O命令进行译码
        • 设备控制器的主要功能
          • 接收和识别命令
          • 数据交换
          • 标识和报告设备状态
          • 地址识别
          • 数据缓冲
          • 差错控制
        • 为了便于上层软件的编制，设备控制器通常需要提供
          • 控制寄存器和状态寄存器
            • 分别用于接收上层发来的命令并存放设备状态信号
            • 是设备与上层的接口
          • 控制命令
            • 由设备控制器提供，每种设备控制器都对应一组相应的控制命令
            • 由CPU发出，用来控制设备控制器
      • I/O接口的类型
        • 按数据传送的方式
          • 并行接口
          • 串行接口
        • 按主机访问I/O设备的控制方式
          • 程序查询接口
          • 中断接口
          • DMA接口
          • . . .
        • 按功能选择的灵活性
          • 可编程接口
          • 不可编程接口
      • I/O端口
        • 指设备控制器中可被CPU直接访问的寄存器
        • 主要有三类
          • 数据寄存器
            • 用于缓存从设备送来的输入数据，或CPU送来的输出数据
          • 状态寄存器
            • 保存设备的执行结果或状态信息
          • 控制寄存器
            • 由CPU写入，以便启动命令或更改设备模式
        • 编址
          • 对各个端口进行编址，每个端口对应一个端口地址
          • 编址方式
            • 独立编址
              • 为每个端口分配一个I/O端口号
                • I/O端口的地址空间与主存地址空间是两个独立的地址空间
                  • 范围可以重叠，相同地址可能属于不同的地址空间
              • 普通用户程序不能对端口进行访问，只有操作系统使用特殊的I/O指令才能访问端口
              • 评价
                • 优点
                  • I/O端口数比主存单元少得多，只需少量地址线，使得I/O端口译码简单，寻址速度更快
                  • 使用专用I/O指令，可是程序更加清晰，便于理解和检查
                • 缺点
                  • I/O指令少，只提供简单的传输操作，所以程序设计的灵活性较差
                  • CPU需要提供两组独立的存储器和设备读/写控制信号，增加了控制的复杂性
            • 统一编址（内存映射I/O）
              • 将主存地址空间分出一部分给I/O端口进行编址
                • I/O端口和主存单元在同一地址空间的不同分段中
                • 根据地址范围就能区分访问的时I/O端口还是主存单元
              • 无需设置专门的I/O指令，用同一的访存指令就可以访问I/O端口
              • 评价
                • 优点
                  • 不需要专门的I/O指令，使得CPU访问I/O的操作更加灵活和方便，还使得端口有较大的编址空间
                  • I/O访问的保护机制可有虚拟存储管理系统来实现，无需专门设置
                • 缺点
                  • 端口地址占用了部分主存地址空间，是主存的可用容量变小
                  • 由于在识别I/O端口时全部地址线都需参加译码，使得译码电路更加复杂，降低了寻址速度
    • I/O控制方式
      • 程序直接控制方式（程序轮询方式）
        • CPU对I/O设备的控制采取轮询的I/O方式
          • CPU向控制设备发出一条I/O指令，启动从I/O设备读取一个字（节），然后不断地循环测试设备状态，直到确定该字（节）已在设备控制器的数据寄存器中。于是CPU将数据寄存器中的数据取出，送入内存的指定单元
        • 评价
          • 易于实现
          • CPU的绝大部分时间都处于等待I/O设备状态的循环测试中，CPU和I/O设备只能串行工作，由于CPU和I/O设备的速度差异很大，导致CPU的利用率相当低
      • 中断驱动方式
        • 思想
          • 允许I/O设备打断CPU的运行并请求服务，使得CPU向设备控制器发出一条I/O指令后可以继续做其他有用的工作
        • 工作过程
          • 从设备控制器的角度
            • 设备控制器从CPU 接收一个读命令，然后从设备读数据
            • 一旦数据读入设备控制器的数据寄存器，便通过控制线给CPU发出中断信号，表示数据已准备好，然后等待CPU请求该数据
            • 设备控制器收到CPU发出的取数据请求后，将数据放到数据总线上，传到CPU的寄存器中
          • 从CPU的角度
            • 当前运行进程发出读命令，该进程将被阻塞，然后保存该进程的上下文，转去执行其他程序
            • 在每个指令周期的末尾，CPU检查中断信号
            • 当有来自设备控制器的中断时，CPU保存当前运行的上下文，转去执行中断处理程序以处理该中断请求
            • CPU从设备控制器读一个字的数据传送到寄存器，并存入主存
            • 中断处理完后解除发出I/O命令的进程的阻塞状态，然后恢复原进程（或其他进程）的上下文，继续运行
        • 评价
          • 在设备准备数据期间，CPU和设备并行工作，CPU的利用率得到明显提升
          • 问题
            • 设备与内存之间的数据交换都必须经过CPU中的寄存器
            • CPU是以字（节）为单位进行干预的，若将这种方式用于块设备的I/O操作，则显然是及其低效的
      • DMA方式（直接存储器存储）
        • 基本思想
          • 在I/O设备和内存之间开辟直接的数据交换通路
        • 特点
          • 基本传送单位是数据块
          • 所传送的数据，是从设备直接送入内存的，或者相反
          • 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预
        • 4类寄存器
          • 命令/状态寄存器（CR）
          • 内存地址寄存器（MAR）
          • 数据寄存器（DR）
          • 数据计数器（DC）
        • 工作过程
          • CPU接收到设备的DMA请求时，向DMA控制器发出一条命令，同时设置MAR和DC的处置，启动DMA控制器，由DMA控制器负责数据传送
          • DMA控制器直接与内存交互，每次传送一个字，这个过程不需要CPU参与
          • 整个数据传送结束后，DMA控制器向CPU发送一个中断信号
        • 评价
          • 数据以“块”为单位，CPU接入的频率进一步降低
          • 数据传送不再经过CPU的寄存器，CPU和设备的平行操作程度得到了进一步提升
      • 通道控制方式
        • 设置通道后，CPU只需向通道发送一条I/O指令，指明通道程序在内存中的位置和要访问的I/O设备，通道收到该指令后，执行通道程序，完成规定的I/O任务后，向CPU发出中断请求
        • 通道方式可以实现CPU、通道和I/O设备三者的并行工作
    • I/O软件层次结构
      • 为使复杂的I/O软件能够具有清晰的结构、良好的可移植性和以适应性，目前普遍采用层次结构的I/O软件
        • 将系统中的设备管理模块分为若凡层次，每层都是利用其下层提供的服务，完成输入/输出功能中的某些子功能，并屏蔽这些功能的实现细节，向高层提供服务
        • 在层次结构的I/O软件中，只要层次间的接口不变，对某一层次中的软件的修改都不会引起其下层或高层代码的变更，仅最底层才设计硬件的具体特性
      • 4个层次的系统结构
        • 用户层软件
          • 实现与用户交互的接口，用户可直接调用在用户层提供的、与I/O操作有关的库函数，对设备进行操作
          • 用户层I/O软件必须通过一组系统调用来获取操作系统服务
        • 设备独立性软件
          • 用于实现用户程序与设备驱动器的统一接口、设备命名、设备保护，以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间
            • 将系统调用参数翻译成设备操作命令
            • 就是系统调用的处理程序
          • 设备独立性（设备无关性）
            • 应用程序所用的设备不局限于某个具体的物理设备
              • 在应用程序中，使用逻辑设备名来请求使用某类设备
              • 在系统实际执行时，必须将逻辑设备名映射成物理设备名
            • 使用逻辑设备的好处
              • 增加设备分配的灵活性
              • 易于实现I/O重定向
                • 指用于I/O操作的设备可以更换（重定向），而不必改变应用程序
          • 设备独立性软件的主要功能
            • 执行所有设备的共有操作，包括
              • 对设备的分配与回收
              • 将逻辑设备名映射为物理设备名
              • 对设备进行保护，禁止用户直接访问设备
              • 缓冲管理
              • 差错控制
              • 提供独立于设备的大小统一的逻辑块，屏蔽设备之间信息交换单位大小和传输速率的差异
            • 向用户层（或文件层）提供统一接口
              • 无论何种设备，它们向用户所提供的接口应是相同的
        • 设备驱动软件
          • 与硬件直接相关，每类设备需要配置一个设备驱动程序
          • 设备驱动程序负责具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序
            • 是I/O进程与设备控制器之间的通信程序
            • 通常以进程的形式存在
            • 包括接收进程发来的I/O命令和参数，并检查其合法性
          • 设备驱动程序向上层用户程序提供一组标准接口，设备具体的差别被设备驱动程序锁封装，用于接收上层软件发来的抽象I/O要求，如read和write命令，转换为具体要求后，发送给设备控制器，控制I/O设备工作
            • 向设备寄存器的写命令是在设备驱动程序中完成的
          • 将由设备控制器发来的信号传送给上层软件，从而为I/O内核子系统隐藏设备控制器之间的差异
          • 设备驱动程序的处理过程
            • ①将抽象要求转化为具体要求
            • ②对服务请求进行校验
            • ③检查设备的状态
            • ④传送必要的参数
            • ⑤启动I/O设备
          • 补充
            • 设备驱动程序负责处理与设备相关的中断处理过程
              • 不同厂家的设备通常提供不同的驱动程序，对应不同的中断处理，因此需要驱动程序来完成
            • 驱动程序仅有一部分需要用汇编语言编写，其余部分可用高级语言编写
            • 不同信号的磁盘的调度方式不一定相同，磁盘调度由磁盘驱动程序完成
            • 不同的操作系统有不同的驱动程序接口，因此驱动程序要根据操作系统的要求进行定制
        • 中断处理程序
          • 当I/O操作完成时，设备控制器发送一个中断信号，CPU相应中断后，根据中断类型号找到相应的中断处理程序进行处理，处理完后，再返回被中断的进程
          • 主要任务
            • 进行进程的上下文切换
            • 对处理中断信号源进行测试
            • 读取设备状态和修改进程状态
            • . . .
      • 磁盘I/O操作汇总各层次的处理过程
        • ①当用户要读取某设备的内容是，通过操作系统提供的 read 命令接口
          • 用户层
        • ②用户发出 read 命令，首先经过设备独立层进行解析，然后交往下层
          • 设备独立层
        • ③不同类型的设备对 read 命令的行为有所不同，针对不同设备，将read命令解析成不同的指令
          • 设备驱动层
        • ④命令解析完毕后，需要中断正在运行的进程，转而执行read命令
          • 中断处理程序
        • ⑤最后，命令真正抵达硬件设备，硬件设备的控制器按照上层传达的命令操作硬件设备，完成相应的功能
    • 应用程序I/O接口
      • I/O接口的分类
        • 字符设备接口
          • 数据的存储和传输是以字符为单位的设备
          • 键盘、打印机等
          • get和put操作
            • 由于字符设备不可寻址，只能采取顺序存取方式
            • 通常为字符设备建立一个字符缓冲区，用户程序通过get操作从缓冲区获取字符，通过put操作将字符输出到缓冲区
          • in-control指令
            • 在接口中提供一种通用的in-control指令来处理它们
          • 都属于独占设备
            • 接口中还需提供打开和关闭操作，以实现互斥
        • 块设备接口
          • 磁盘等
            • I/O常使用DMA方式
              • 在预处理之前，请求I/O的进程通过系统调用进入内核态
                • 预处理程序和后处理程序都运行在内核态
              • 负责预处理的进程是请求I/O的进程，负责后处理的进程是中断服务例程
                • 中断服务例程不是一个单独的进程
              • 预处理由请求I/O的进程在内核态执行相关操作，之后阻塞其自身，直到系统调用返回
                • 因此在后处理阶段请求I/O的进程仍处于阻塞态
          • 基本特征
            • 传输速率较高、可寻址
          • 块设备接口支持将上层发来的打开、读、写、关闭等抽象命令，映射为设备能识别的较低层的具体操作
            • 隐藏了磁盘的二维结构
          • 内存映射接口通过内存的字节数组来访问磁盘，不提供读/写磁盘操作
            • 映射文件到内存的系统调用返回包含文件副本的一个虚拟内存地址，只在需要访问内存映像时，才由虚拟存储器实际调页
        • 网络设备接口
          • 许多操作系统提供的网络I/O接口为网络套接字接口
            • 套接字接口的系统调用使应用程序创建本地套接字连接到远程应用程序创建的套接字，通过此连接发送和接收数据
      • 阻塞I/O和非阻塞I/O
        • 阻塞I/O
          • 当用户进程调用I/O操作时，进程就被阻塞，I/O操作完成后，进程才被唤醒
          • 当进程恢复执行时，它收到系统调用的返回值，并继续处理数据
          • 大多数操作系统提供的I/O接口都是采用阻塞I/O
        • 非I/O阻塞
          • 用户进程调用I/O时，不阻塞该进程，但需要进程不断询问I/O操作是否完成
            • 在I/O执行阶段，进程还可以做其他事情
          • 评价
            • 优点
              • 进程在等待I/O期间不会阻塞，可以做其他事情，适合并发量大的应用开发
            • 缺点
              • 轮询方式询问I/O结果，回占用CPU的时间
  • 设备独立性软件
    • 设备独立性软件（设备无关软件）
      • 是I/O系统的最高层软件
    • 高速缓存与缓冲区
      • 磁盘高速缓存（Disk Cache）
        • 利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息
        • 逻辑上属于磁盘，物理上是驻留在内存中的盘块
        • 在内存中分为两种形式
          • 在内存中开辟一个单独的空间作为缓存区，大小固定
          • 将未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O共享
      • 缓冲区（Buffer）
        • 在设备管理子系统中引入缓冲区的目的
          • 缓和CPU与I/O设备间速度不匹配的矛盾
          • 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
          • 解决基本数据单元大小（数据粒度）不匹配问题
          • 提高CPU和I/O设备之间的并行性
        • 实现方法
          • 单缓冲
            • 每当用户进程发出一个I/O请求，操作系统便在内存中为之分配一个缓冲区
              • 通常一个缓冲区大小就是一个块
            • • T和C是可并行的
              • 单缓冲区处理每块数据的平均时间为 Max(C, T)+M
          • 双缓冲
            • • 双缓冲区处理每块数据的平均时间为 Max(C+M, T)
          • 循环缓冲
            • 循环缓冲包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区，最后一个缓冲区指针指向第一个缓冲区，多个缓冲区链接成一个循环队列
            • 循环缓冲中还需设置 in 和 out 两个指针，in 指向第一个可以输入数据的空缓冲区，out 指向第一个可以提取数据的满缓冲区，输入/输出时，两个指针沿链接方向循环移动
          • 缓冲池
            • 包含一个用于管理自身的数据结构和一组操作函数的管理机制，用于管理多个缓冲区，缓冲池可供多个进程共享使用
            • 缓冲池由多个系统公用的缓冲区组成，按其使用状况分为
              • 空缓冲队列
              • 输入队列
                • 装满输入数据
              • 输出队列
                • 装满输出数据
            • 还应具有4种工作缓冲区
              • hin
                • 用于收容输入数据的工作缓冲区
              • sin
                • 用于提取输入数据的工作缓冲区
              • hout
                • 用于收容输出数据的工作缓冲区
              • sout
                • 用于提取输出数据的工作缓冲区
            • 缓冲池中的缓冲区有以下4中工作方式
              • 收容输入
                • 输入进程需要输入数据时，从空缓冲队列的队首摘下一个空缓冲区，作为收容输入工作缓冲区，然后将数据输入其中，装满后再将它挂到输入队列的队尾
              • 提取输入
                • 计算进程需要输入数据时，从输入队列的队首取得一个缓冲区，作为提取输入工作缓冲区，从中提取数据，用完该数据后将它挂到空缓冲队列的队尾
              • 收容输出
                • 计算进程需要输出数据时，从空缓冲队列的队首摘下一个空缓冲区，作为收容输出工作缓冲区，装满后再将它挂到输出队列的队尾
              • 提取输出
                • 输出进程需要输出数据时，从输出队列的队首取得一个缓冲区，作为提取输出工作缓冲区，数据提取完后，后将它挂到空缓冲队列的队尾
        • 缓冲区是一种临界资源，在使用缓冲区时都有一个申请和释放（互斥）的问题需要考虑，即实现进程访问缓冲区的同步
      • 高速缓存与缓冲区的对比
        • 相同点
          • 都介于高速设备和低速设备之间
        • 区别
    • 设备分配与回收
      • 设备分配概述
        • 充分发挥设备的使用效率，又避免由于不合理的分配方法造成进程死锁
      • 设备分配的数据结构
        • 设备控制表（DCT）
          • 系统为每个设备配置一张DCT
          • 表项
            • 设备类型type
            • 设备标识符：deviceid
              • 设备物理名，在系统中是唯一的
            • 设备状态：等待/不等待 忙/闲
            • 指向控制器表的指针
            • 重复执行次数或时间
              • 重复执行次数达到规定值时仍不成功，认定此次I/O失败
            • 设备队列的队首指针
              • 指向正在等待该设备的进程队列（由进程的PCB组成）的队首
        • 控制器控制表（COCT）
          • 每个设备控制器都对应一张COCT
          • 操作系统根据COCT的信息对控制器进行操作和管理
          • 每个控制器由一个通道控制，通过表项“与控制器连接的通道表指针”可以找到相应通道的信息
          • COCT组成
            • 控制器标识符：controllerid
            • 控制器状态
            • 与控制器连接的通道表指针
            • 控制器队列的队首指针
            • 控制器队列的队尾指针
        • 控制通道表（CHCT）
          • 每个通道对应一张CHCT
          • 组成
            • 通道标识符：channelid
            • 通道状态
            • 与通道连接的控制器表首址
            • 通道队列的队首指针
            • 通道队列的队尾指针
          • 一个通道可为多个控制器服务，通过表项“与通道连接的控制器表首址”可以找到该通道管理的所有控制器的信息
        • 系统设备表（SDT）
          • 整个系统只有一张SDT
          • 记录已连接到系统中的所有物理设备的情况
          • 每个物理设备对应一个表目
            • 表目组成
              • 设备类
              • 设备标识符
              • DCT
              • 驱动程序入口
      • 设备分配时应考虑的因素
        • 设备的属性
          • 类型
            • 独占设备
            • 共享设备
            • 虚拟设备
          • 设备的访问权限
          • 设备的占用状态
        • 设备分配算法
          • FCFS算法
          • 最高优先级优先算法
        • 设备分配中的安全性（设备分配中应防止发生进程死锁）
          • 安全分配方式
            • 每当进程发出I/O请求后 ，便进入阻塞态，直到I/O操作完成时才被唤醒
            • 设备分配安全，但CPU和I/O设备是串行工作的
          • 不安全分配方式
            • 进程在发出I/O请求后仍继续运行，需要时有所会发出第二个、第三个I/O请求
            • 可能造成死锁
      • 设备分配的步骤
        • ①分配设备
          • 根据I/O请求中的物理设备名，查找SDT，从中找出该设备的DCT
            • DCT中的设备状态字段
              • 忙
                • 将进程PCB挂到设备等待队列
              • 不忙
                • 根据一定的策略将设备分配给该进程
        • ②分配控制器
          • 设备分配后，根据DCT找到COCT
            • 控制器的状态
              • 忙
                • 将进程PCB挂到控制器等待队列
              • 不忙
                • 将控制器分配给该进程
        • ③分配通道
          • 控制器分配后，根据COCT找到CHCT
            • 通道的状态
              • 忙
                • 将进程PCB挂到通道等待队列
              • 不忙
                • 将通道分配给该进程
        • 只有设备、控制器和通道都分配成功时，这次设备分配才算成功，之后便可启动设备进行数据传送
      • 逻辑设备名到物理设备名的映射
        • 逻辑设备表（LUT）
          • 表项
            • 逻辑设备名
            • 物理设备名
            • 设备驱动程序入口地址
        • 在系统中可采取两种方式设置逻辑设备表
          • 整个系统中只设置一张LUT
            • 主要适用于单用户系统
          • 为每个用户设置一张LUT
            • 不同用户可以使用相同的逻辑设备名
        • 用户程序对I/O设备的请求采用逻辑设备名，程序实际执行时使用武力设备名，它们之间的转换是由设备无关软件完成的
      • 分配方式
        • 静态分配方式
          • 在作业执行前，系统根据作业堆资源的需求，一次性分配给该作业所需的独占设备，直到作业结束才释放
        • 动态分配方式
          • 当进程需要使用共享设备时，系统根据设备的当前状态和进程的请求，适时地将设备分享给进程，进程使用完毕后立即释放设备，供其他进程使用
    • SPOOLing计数（假脱机技术）
      • 将独占设备改造成共享设备的技术
        • 为了缓和CPU的高速性和I/O设备的低速性之间的矛盾
        • 提高单机资源利用率的关键技术是多道程序设计技术
      • 利用专门的外围控制机，先将低速I/O设备上的数据传送到高速磁盘上，或者相反
        • 当CPU需要输入数据时，便可直接从磁盘中读取数据
        • 当CPU需要输出数据时，也能以很快的速度将数据先输出到磁盘上
      • SPOOLing系统的组成
        • 输入井和输出井
          • 在磁盘上开辟出的两个存储区域
            • 输入井模拟脱机输入时的磁盘，用于收容I/O设备输入的数据
            • 输出井模拟脱机输出时的磁盘，用于收容用户程序的输出数据
            • 一个进程的输入（或输出）数据保存为一个文件，所有进程的输入（或输出）文件链接成一个输入（输出）队列
        • 输入缓冲区和输出缓冲区
        • 输入进程和输出进程
          • 输入进程用于模拟脱机输入时的外围控制机
            • 将用户要求的数据从输入设备传送到输入缓冲区，再存放到输入井中
            • 当CPU需要输入数据时，直接从输入井读入内存
          • 输出进程将用户要求输出的数据从内存传送到输出井，当输出设备空闲时，在就爱那个输出井中的数据井输出缓冲区输出至设备
        • 井管理程序
          • 用于控制作业与磁盘井之间的信息交换
        • 另一种说法
          • SPOOLing系统由预输入程序、井管理程序、缓输出程序组成
      • 特点
        • 提高了I/O速度，将对低速I/O设备执行的操作演变为对磁盘缓冲区中数据的存取操作
        • 将独占设备改造为共享设备
        • 实现了虚拟设备功能
      • SPOOLing技术是一种以空间换时间的技术
      • SPOOLing技术需要使用磁盘空间（输入井和输出井）和内存空间（输入/输出缓冲区），不需要外围计算机支持
    • 设备驱动程序接口
      • 设备驱动程序是I/O系统的上层与设备控制器之间的通信程序
        • 主要任务是接收上层应用发来的抽象I/O请求，将它们转换为具体要求后发送给设备控制器，进而使其启动设备取执行任务
        • 反之，它也将设备控制器发来的信号传送给上层应用
      • 设备驱动程序应具有的功能
        • 接收由上层关键发来的命令和参数，并将抽象要求转换为与设备相关的具体要求
        • 检查用户I/O的合法性，了解设备的工作状态，传递与设备操作有关的 参数，设置设备的工作方式
        • 发出I/O命令
          • 若设备空闲，则立即启动，完成执行的I/O操作
          • 若设备忙，则将请求者的PCB挂到设备队列上等待
        • 及时响应由设备控制器发来的中断请求，并根据其中断类型，调用相应的中断处理程序处理
      • 设备驱动程序的特点
        • 设备驱动程序将抽象的I/O请求转成具体的I/O操作后，传送给设备控制器，并将设备控制器中记录的设备状态和I/O操作的完成情况及时地反馈给请求进程
        • 设备驱动程序与设备采用的I/O控制方式紧密相关，常用的I/O控制方式是中断驱动方式和DMA方式
        • 设备驱动程序与硬件密切相关，对于不同类型的设备，应配置不同的设备驱动程序
        • 由于设备驱动程序与硬件密切相关，目前很多设备驱动程序的基本部分已固化在ROM中
        • 设备驱动程序应允许同时多次调用执行
    • I/O操作举例
      • 程序调用 "scanf(%c), &d" 时
        • 第一阶段的工作是在C语言函数库中完成的
          • 检查与 scanf 函数关联的用户缓冲区 buf
            • 若缓冲区已有数据，则直接读取
            • 若缓冲区为空，则触发系统调用 read，从内核缓冲区中读取数据
          • 执行系统调用read，read调用会在执行 trap 指令前传入本次调用的三个参数
            • fd
              • 文件描述符，指明输入设备
            • buf
              • 用户空间的缓冲区
            • count
              • 读取的最大字节数
        • 第二阶段的加工作是系统调用
          • 进入内核态后，系统调用服务例程申请一个内核缓冲区，并且最终转到真正执行I/O操作的设备驱动层。
          • 中断方式系统调用服务例程的过程
            • ①设置相应的I/O参数后，发起I/O的进程P进入阻塞态，CPU调度其他进程运行
            • ②用户通过键盘输入字符，字符被送到键盘I/O接口的数据端口
            • ③键盘I/O接口向CPU发出中断请求
            • ④CPU相应中断并执行键盘中断处理程序，将字符从I/O接口的数据端口送入内核缓冲区
              • 中断服务例程执行结束时，所输入数据存放位置是内核缓冲区
            • ⑤进程P被唤醒，插入就绪队列，等待被调度
            • ⑥进程P再次获得CPU后，系统调用服务例程将字符从内核缓冲区复制到用户缓冲区
            • ⑦进程P从系统调用返回，之后 scanf 函数进行字符解析，最终将字符存储到变量 d 中
  • 磁盘和固态硬盘
    • 磁盘
      • 组成
        • 表面涂有磁性物质的物理盘片，通过一个称为磁头的导体线圈从磁盘存取数据
          • 磁道
            • 扇区（盘块）
      • 读/写磁盘的过程
        • ①根据柱面号移动磁头臂，让磁头移动到对应的柱面
        • ②激活对应盘面的磁头
        • ③当磁盘旋转时，磁头从对应扇区上划过，从而完成对制定扇区的读/写
      • 磁盘分类
        • 固定头磁盘
          • 磁头相对于盘片的径向方向固定
          • 每个磁道有一个磁头
        • 活动头磁盘
          • 磁头可移动，磁头臂可来回伸缩定位磁道
        • 温彻斯特磁盘
          • 磁头活动而盘片固定
    • 磁盘的管理
      • 磁盘初始化
        • 低级格式化（物理格式化）
          • 在磁盘可以存储数据之前，必须将它分成扇区，以便磁盘控制器能够进行读/写操作
          • 低级格式化是磁盘制造商在生产磁盘时进行的操作，它负责创建磁盘的物理结构，包括磁道、扇区的划分，并将一些控制信息（如扇区号、磁道号等）写入每个扇区的头部和尾部
      • 分区
        • 在可以使用磁盘存储文件前，需要两个步骤
          • ①将磁盘分区
            • 每个分区由一个或多个柱面组成，每个分区的起始扇区和大小都记录在磁盘主引导记录的分区表中
          • ②对物理分区进行逻辑格式化（高级格式化）
            • 将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲的空间和已分配的空间，以及一个初始为空的目录，建立根目录、对保存空闲磁盘块信息的数据结构进行初始化
        • 为提高效率，操作系统将多个相邻的扇区组合在一起，形成一簇（Linux中称为块）
          • 为了更高效地管理磁盘，一簇只能存放一个文件的内容，文件所占用的空间只能是簇的整数倍
      • 引导块
        • 计算机启动时需要运行一个初始化程序（自举程序），它初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统
        • 自举程序通常存放在ROM中，为了避免改变自举代码而需要改变ROM硬件的问题，通常只在ROM中保留很小的自举装入程序，而将完整功能的引导程序保存在磁盘的启动块上，启动块位于磁盘的固定位置
          • 具有启动分区的磁盘称为启动磁盘或系统磁盘
        • Windows引导过程
          • Windows允许将磁盘分为很多个分区，有一个分区为引导分区，它包含操作系统和设备驱动程序
          • Windows系统将引导代码存储在磁盘的第0号扇区
            • 主引导记录（MBR）
              • 包含引导代码、一个磁盘分区表和一个标志（以指示从哪个分区引导系统）
          • 引导首先运行ROM中的代码，这个代码指示系统从MBR中读取引导代码，当系统找到引导分区时，读取分区的第一个扇区，称为引导扇区，并继续余下的引导过程，包括加载各种系统服务
      • 坏块
        • 对于简单磁盘，FAT表上会标明，因此程序不会使用它们
        • 对于复杂磁盘，控制器维护磁盘内的坏快列表
          • 这个列表在出厂低级格式化就已初始化，在磁盘使用过程中不断更新
          • 低级格式化会保留一些块作为备用，操作系统看不到这些块
          • 控制器可以采用备用块来逻辑地替换坏块
            • 备用扇区
    • 磁盘调度算法
      • 磁盘的存取时间
        • 寻道时间
          • 跨越磁道条数*跨越一个磁道所需的时间 + 启动磁头臂的时间
          • Ts = mn+s
        • 旋转延迟时间
          • Tr = 1/2r
            • 磁盘的旋转速度为r
        • 传输时间
          • 读/写的字节数 / (磁盘每秒的转速*一个磁道上的字节数)
          • Tt = b/rN
        • 总平均存取时间
          • Ta = Ts +Tr + Tt
      • 磁盘调度算法
        • 先来先服务（FCFS）
          • 根据进程请求访问磁盘的先后顺序进行调度
          • 具有公平性
        • 最短寻道时间有限（SSTF）
          • 每次选择调度的是离当前磁头最近的磁道，使每次的寻道时间最短
          • 性能优于FCFS，会产生“饥饿”现象
        • 扫描（SCAN）算法
          • 只有磁头移动到最外侧磁道时才能向内移动
        • 循环扫描（C-SCAN）
          • 移动到最外侧后快速返回起始端而不服务任何请求
          • 优化
            • 磁头只需移动到最远端的一个请求即可返回，不需要到达磁盘端点
            • 改进后的算法称LOOK调度和C-LOOK调度
          • 消除了SCAN对磁道两端请求的不公平
      • 减少延迟时间的方法
        • 交替编号
          • 磁头读入一个扇区后，需要经过短暂的处理时间，才能读入下一个扇区
          • 对一个盘面的盘区进行交替编号
          • 让逻辑上相邻的块在物理上保持一定的间隔
        • 错位命名
          • 对不同的盘面
      • 提高磁盘I/O速度的方法
        • 优化方面
          • 改进文件的目录结构和检索目录的方法，以减少对目录的查找时间
          • 选取好的文件存储结构，以提高对文件的访问速度
          • 提高磁盘的I/O速度
            • 采用磁盘高速缓存
            • 调整磁盘请求顺序
            • 提前读
              • 读磁盘当前块时，将下一磁盘块也读入内存缓冲区
            • 延迟写
              • 仅在缓冲区首部设置延迟写标志，然后释放次缓冲区并将其链入空闲缓冲区链表尾部，当其他进程申请到此缓冲区时，才真正将缓冲区信息写入磁盘块
            • 优化物理块的分布
            • 虚拟盘
              • 用内存空间去仿真磁盘，又叫RAM盘
                • 常用于存放临时文件
            • 采用磁盘阵列RAID
              • 可以采用并行交叉存取
      • 磁臂黏着
        • 系统总是访问磁盘的某个磁道而不响应对其他磁道的请求访问
        • SSTF、SCAN、C-SCAN均可能出现磁臂黏着现象
    • 固态硬盘
      • 原理
        • 基于闪存技术Flash Memory，属于电可擦除ROM，即EEPROM
      • 组成
        • 闪存翻译层
          • 负责翻译逻辑块号，找到对应页
        • 存储介质
          • 多个闪存芯片（Flash Chip）
            • 每个芯片包含多个块
              • 每个块包含多个页
      • 读写性能特性
        • 以页为单位读写
          • 相当于磁盘的“扇区”
        • 以块为单位“擦除”，擦干净的块，其中的每页都可以写一次，读无限次
        • 支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址
        • 读快、写慢
          • 要写的页如果有数据，则不能写入，需要将块内的其他页全部复制到一个新的（擦除过的）块中，再写入新的页
      • 与机械硬盘相比的特点
        • 读写速度快，随机访问性能高，用电路控制访问位置；机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟
        • SSD安静无噪音、耐摔抗震、能耗低、造价更贵
        • SSD的一个“块”被擦除次数过多（重复写同一个块）可能会坏掉，而机械硬盘的扇区不会因为写的次数太多而坏掉
      • 磨损均衡技术
        • 思想
          • 将“擦除”平均分布在各个块上，以提升使用寿命
        • 动态磨损均衡
          • 写入数据时，优先选择累积擦除次数少的新闪存块
        • 静态磨损均衡
          • SSD监测并自动进行数据分配、迁移，让老旧的闪存块担以读为主的任务，让较新的闪存块承担更多写任务
          • 通常必动态磨损均衡算法表现更优秀
            • 在没有数据写入时，SSD监测并自动进行数据分配，从而使各块的擦写更加均衡