操作系统考研复习

¶第一章 - 计算机系统概述

1. 操作系统的概念（了解，选择题不选错就行）：

   1. 控制和管理计算机软硬件
   2. 合理组织调度计算机的工作与资源
   3. 为用户和其它软件提供接口

2. 操作系统的基本特征（了解）：

   • 并发（区分并行）
   • 共享
   • 虚拟：一个物理实体变成多个逻辑上的对应物
     • 虚拟处理器：并发多道程序，让用户以为有多个处理器
     • 虚拟存储器：如虚拟内存
     • I/O处理器的空分复用技术
   • 异步：多道程序走走停停，以不可预知的速度前进

3. 操作系统的目标和功能（了解）

   • 管理功能：处理机管理、存储器管理、文件管理、设备管理。
   • 接口功能：
     • 命令接口：联机命令接口（cmd）、脱机命令接口（批处理系统的作业说明书）。
     • 程序接口：由系统调用（也叫广义指令）组成，例如“printf程序调用”由定位内存、显示字符等多个系统调用组成。
   • 扩展机器（不重要）
   • 系统调用

4. 操作系统发展与分类（重点关注批处理阶段，其它了解即可）

   1. 手工处理阶段：这个阶段没有操作系统，所有调度包括程序的装入、允许、结果输出都需要人为干预
   2. 批处理阶段：出现操作系统，为了解决“人（慢）机（快）矛盾”和“CPU（快）与I/O设备（慢）矛盾”而出现
      1. 单道批处理系统：自动性（磁带上的程序逐个允许，无需人工干预）、顺序性（磁带上的程序依次调入内存、依次按序执行）、单道性（一次只调入一道程序到内存，只有一道程序在运行）
      2. 多道批处理系统：允许多个程序同时（宏观）被调入内存并交替执行。宏观上并行，微观上串行。
   3. 分时操作系统：处理机运行时间划分时间片，分配给任务运行。同时、交互、独立、及时性。
   4. 实时操作系统：保证规定时间内完成某项任务。实时性、可靠性。
   5. 分布式计算机系统、个人计算机操作系统。

5. 操作系统的运行机制（重点关注中断和异常部分，其它简单或者在后面章节才展开）

   • 操作系统内核程序（核心态/管态）和用户程序（用户态/目态）
     • 核心态可以执行特权指令，而用户态只能执行非特权指令。
     • 切换要通过程序状态字寄存器PSW（计组）
     • 核心态 ➡ 用户态: 执行一条特权指令,修改程序状态字PSW,主动让出CPU使用权
     • 用户态 ➡ 核心态: 自陷/中断
   • 内核需要实现：
     1. 时钟管理：CLOCK
     2. 中断机制：见后面部分，一开始是为了提高CPU利用率（计组-系统总线设计部分），后面也负责核心/用户态切换。
     3. 原语：不可被打断的小程序，因为某些操作被中断会造成大麻烦。
     4. 系统控制的数据结构及处理：快表、索引表、进程控制块等等…
   • 中断与异常（重点！！！）：
     • 中断是操作系统必须要实现的！！！
     • 访管/陷入指令：顾名思义，访问管态程序/特权指令的指令，因其可以在用户态下使用，所以不是特权指令
     • 中断（外中断、相对于CPU来说是“外”）：I/O中断（输入输出完成）、时钟中断
       • 内存外存的访问都需要通过系统调用trap触发中断
     • 异常（内中断、相对于CPU来说是“内”、不能被屏蔽）：非法操作数（除0、地址越界、算术溢出）、陷入指令（用户程序自己设置，用户态➡核心态）
       • 内中断的响应发生在指令执行过程中，且不需要返回断点
   • 系统调用：操作系统中提供的实现一些特定功能的小程序。
     • 分类就不谈了，没见过考这么细的。

6. 大内核与微内核（需要理解）：

   • 大内核：操作系统的大多数功能都运行在核心态
     • 优点：性能优势（想想大部分功能都可以在核心态，也就是更靠近硬件的状态下运行）
     • 缺点：设计复杂
   • 微内核：操作系统的最基本功能运行在核心态
     • 优点：有效分离各功能模块，维护成本大大降低
     • 缺点：性能问题（需要在用户态和核心态频繁切换）

¶第二章 - 进程管理

1. 进程（超重点！！！）：

   • 区分程序和进程:
     • 程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
     • 进程（Process）：是动态的，是程序的一次执行过程。
   • 进程控制块PCB,以"打开三个QQ进程，操作系统怎么区分他们？"为例:
     • 当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”—— PID（Process ID，进程ID）
     1. 操作系统要记录PID、进程所属用户ID（UID）——基本的进程描述信息，可以让操作系统区分各个进程
     2. 还要记录给进程分配了哪些资源（如：分配了多少内存、正在使用哪些I/O设备、正在使用哪些文件）——可用于实现操作系统对资源的管理
     3. 还要记录进程的运行情况（如：CPU使用时间、磁盘使用情况、网络流量使用情况等）——可用于实现操作系统对进程的控制、调度
     • 这些信息都被保存在一个数据结构PCB （Process Control Block）中，即进程控制块操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中
   • 程序的运行过程: 程序文件 ➡ 可执行文件(二进制、机器指令) ➡ 入内存 ➡ 分配PCB ➡ 顺序执行机器指令 ➡ 执行产生的中间数据被放入数据段
   • 一个进程实体（进程映像）由PCB、程序段、数据段组成。
     • 进程是动态的，进程实体（进程映像）是静态的。
   • 进程的特征: 动态性、独立性、并发性、异步性、结构性（PCB、程序段、数据段）

2. 进程的状态和转换

   • 状态（解释部分看看就行）：
     • 运行态。进程正在处理机上运行。在单处理机环境下，一个时刻最多只有一个进程处于运行态。
     • 就绪态。进程已经获得了除了处理机以外的所有资源，一旦得到处理机资源，即可立即运行。处于就绪态的进程可能有多个，通常将他们排成队列即就绪队列。
     • 阻塞态（等待态）。进程正在等待某一事件而暂停运行，如等待某资源（除处理机以外）可用或I/O完成。即使处理机空闲，该进程也不能运行。
     • 创建态。进程正在被创建，尚未转到就绪态。
     • 结束态。进程正在从系统中消失，可能是进程正常运行结束或者中断退出运行。进程需要结束运行时，首先将进程置为结束态，然后回收资源。
   • 进程状态的转换（超重点！！！）：
     • 阻塞态只能到就绪态，只有运行态能到阻塞态。
   • 进程的创建：分配进程号、申请PCB ➡ 分配资源（内存等） ➡ 初始化PCB ➡ 进入就绪队列
   • 进程的结束：根据进程号找到PCB、查看进程状态 ➡ 剥夺处理机 ➡ 终止子进程 ➡ 剥夺所有资源（还给父进程或操作系统） ➡ 删除PCB
     • 正常结束、异常结束（异常事件导致无法执行）、外界干预（用户或操作系统请求关闭）
   • 进程的阻塞：根据进程号找到PCB、查看进程状态 ➡ 剥夺处理机，保存现场至PCB并修改状态为阻塞态 ➡ 入阻塞队列
   • 进程的唤醒/就绪：阻塞队列找到PCB ➡ 移出阻塞队列，状态改为就绪 ➡ 入就绪队列

3. 进程的切换：

   • 状态的切换在核心态！！！
   • 进程切换过程：保存现场 ➡ 更新PCB ➡ PCB移入相应队列（就绪、等待） ➡ 找到切换进程的进程号，更新其PCB ➡ 运行 ➡ 运行结束 ➡ 根据PCB恢复现场（不一定是那个被替换掉的进程）

4. 进程的组织

   • 即要解决怎么将各个进程的PCB组织起来的问题。
   • 进程控制块PCB：
     • PID（进程号、进程标识符）和UID（用户号、标识进程归属用户）
     • 进程运行、控制、中断相关的信息
     • 资源分配清单、处理机相关信息
   • 进程包括：程序控制块PCB、程序段、数据段
   • 进程的组织方式（重点！！！）：
     • 链接方式：指针。
       • 也可以细分，如阻塞队列细分为：打印机阻塞队列、磁盘阻塞队列
     • 索引方式：索引表。

5. 进程的控制

   • 创建进程、结束进程、进程状态转换
   • 原语的“原子性”
     • 利用开/关中断实现
   • 原语（理解）：
     • 进程创建原语：分配进程号、申请PCB ➡ 分配资源（内存等） ➡ 初始化PCB ➡ 进入就绪队列
       • 引起进程创建的事件：用户登录（创建系统父进程）、作业调度（作业放入内存，为其创建进程）、提供服务（某些请求会创建进程，如FTP）、应用请求（用户进程请求创建子进程）
     • 进程终止原语：根据进程号找到PCB、查看进程状态 ➡ 剥夺处理机 ➡ 终止子进程 ➡ 剥夺所有资源（还给父进程或操作系统） ➡ 删除PCB
       • 引起进程终止的事件：正常结束、异常结束、外界干预
     • 进程阻塞原语：根据进程号找到PCB、查看进程状态 ➡ 剥夺处理机，保存现场至PCB并修改状态为阻塞态 ➡ 入阻塞队列
       • 引起进程阻塞的事件：请求的资源不足、等待其它进程
     • 进程唤醒原语：阻塞队列找到PCB ➡ 移出阻塞队列，状态改为就绪 ➡ 入就绪队列
       • 引起进程唤醒的事件：等待的事件发生
     • 进程切换原语：保存现场 ➡ 更新PCB ➡ PCB移入相应队列（就绪、等待） ➡ 找到切换进程的进程号，更新其PCB ➡ 运行 ➡ 运行结束 ➡ 根据PCB恢复现场（不一定是那个被替换掉的进程）
       • 引起进程切换的事件：时间片到、高优先级到、进程主动阻塞、进程结束

6. 进程的通信

   • 共享存储：
   • 管道通信：相当于缓存
   • 信息传递：类似计网，中间一个信箱，信息都发往信息

7. 线程：进程 ➡ 线程

   • 引入线程之后：进程只是资源分配的单位，线程成为处理机的分配单元；
   • 线程最直接的理解就是“轻量级进程”。
   • 引入线程后的变化
     • 引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）
     • 引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。
     • 线程则作为处理机的分配单元。
   • 线程的特点/属性：（理解）：
     • 线程不能创建进程
     • 不拥有系统资源，拥有唯一标识符和线程控制块
     • 不同线程可以执行相同程序，同一服务程序被不同用户调用，可能创建不同线程
     • 同一进程的线程共享该进程全部资源（互斥共享）
     • 线程是处理机的独立调度单位
     • 线程也有生命周期、阻塞、就绪、运行等状态
     • 多CPU，各个线程可占用不同CPU
     • 每个线程都有线程ID、线程控制块（TCB）
     • 切换同进程的线程，开销小（不用换进程）
     • 线程共享进程的内存空间，因此其通信甚至无需系统干预

8. 线程的实现方式（重点！！！）：

   • 用户级线程：线程管理工作交由进程，内核意识不到线程的存在
     • 用户级线程切换不需要CPU状态转换
     • 当一个用户级线程被阻塞时，整个进程都被阻塞。多个线程不可在多核处理机上运行
   • 内核级线程：线程的管理工作由内核完成
     • 主流方式
     • 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
     • 一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
   • 多线程模型
     • 一对一模型
       • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
       • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
     • 多对一模型
       • 退化为用户级线程
       • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
       • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
       • 重点重点重点：操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。
     • 多对多模型
       • 即提高了并发性，又降低了开销（什么都会就是什么都不会…）

9. 处理机调度：作业调度（高级调度）、中级调度（内存调度）、进程调度（低级调度、最基本）（重要的是计算）：

   • 三层调度的对比
   • 不能进行调度的场景：中断处理中、进程进入内核程序临界区、其它需要完全屏蔽中断的原子操作过程
   • 剥夺式调度和非剥夺式调度
   • 周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
     • 它包括四个部分
       1. 作业在外存后备队列上等待作业调度（高级调度）的时间
       2. 进程在就绪队列上等待进程调度（低级调度）的时间
       3. 进程在CPU上执行的时间
       4. 进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次
     • （作业）周转时间 = 作业完成时间 – 作业提交时间
     • 平均周转时间 = 各作业周转时间之和 / 作业数
     • 带权周转时间 = 作业周转时间 / 作业实际运行时间
     • 带权平均周转时间 = 带权周转时间 / 作业数

10. 调度算法（重要的是计算）：

    • 先来先服务(FCFS)调度算法
      • 顾名思义：谁先到谁先被服务
      • 如图：
        • P1、P2、P3、P4依次到达，所以其时序图：
        • 周转时间：7-0、11-2、12-4、16-5，平均周转时间8.75
        • 带权周转时间：7/7、9/4、8/1、11/4，平均带权周转时间3.5
        • 等待时间：0、7-2、11-4、12-5，平均等待时间4.75
      • 特点：
        • 不会导致饥饿
        • 不可剥夺
        • 长作业有利、短作业不利（排在后面的短作业要等上非常久、但只运行小段时间）
        • 有利千CPU繁忙型作业、不利于I/0繁忙型作业（I/O作业往往更加紧急）
    • 短作业优先（SJF）算法：
      • 短作业优先调度
      • 如图：
      • 短作业优先调度SJF没什么好说的
      • 最短剩余时间优先SRTN（剥夺式SJF）
      • 特点：
        • 可能“饥饿”
    • 高响应比优先（HRRN）：
      • 响应比 = （等待时间 + 要求服务时间） / 要求服务时间
      • 如图
      • 特点：
        • 不会“饥饿”
        • 非抢占式
    • 时间片轮转算法：
      • 使用分时系统，使用时间片，就绪进程按照到达先后排成队列，依次在时间片内占用处理机，时间片到就释放
      • 时间片选择很重要，过大就变成了先来先服务，过小就变成了短作业优先
      • 特点：
        • 不会导致饥饿
        • 抢占式
    • 优先级调度算法
      • 抢占式、非抢占式都有
      • 会导致饥饿
      • 如图：
        • 非抢占式：
        • 抢占式：
      • 补充：
        • 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置
        • 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。
          • 静态优先级：创建进程时确定，之后一直不变。
          • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
            • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
            • 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
            • 如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级
        • 一些常见的系统优先级
          • 系统进程优先级高于用户进程
          • 前台进程优先级高于后台进程
          • 操作系统更偏好I/O型进程（或称I/O繁忙型进程）
            • 这是因为I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升
          • 与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）
    • 多级反馈调度算法：
      • 抢占式、会饥饿
      • 算法规则：
        1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
        2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
        3. 只有第k 级队列为空时，才会为k+1 级队头的进程分配时间片
      • 在k 级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k 级队列队尾。
      • 流程：
        1. P1(8)先到达, 入1级队列. 执行1个单位时间片P1(7), 进入2级队列.
        2. 1时刻P2(4)到达, 入1级队列. 执行1个单位时间片P2(3), 进入2级队列.
        3. 2时刻1级队列为空, 则对2级队列进行调度, P1(7)执行2个单位时间片之后入三级队列P1(5).
        4. 4时刻P2(3)运行到5时刻P2(2), 此时P3(1)进入, 应该优先调度1级队列, 被剥夺处理机的P2(2)重新放回2级队列.
        5. P3(1)运行1个单位时间P3(0), 完成并结束该进程.
        6. P2(2)运行2个时间单位P2(0), 完成并结束该进程.
        7. P1(5)运行4个时间单位P1(1), 已经位于最下级队列, 回到该队列运行并完成.

11. 进程同步、互斥（理解！！！）：

    • 进程同步：直接制约关系，进程间可能需要一种先后顺序或者互相依赖的关系
    • 进程互斥：间接制约关系，当一个进程访问临界资源的时候，其它进程不能访问
      • 一段时间内只允许一个进程使用的资源叫临界资源
    • 临界区互斥（同步机制实现需尽量遵循）（重点！！！）：
      • 前三个满足“临界区互斥”，最后一个解决“饥饿”
        1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
        2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
        3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
        4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

12. 进程互斥的软件实现方法(同步机制) （理解！！！）：

    • 单标志法
      • 只能按P0 P1 P0 P1 ……这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。
      • 因此，单标志法存在的主要问题是：违背“空闲让进”原则。
    • 双标志先检查法
      • 先检查是否被占用，然后才自己占用
      • 若按照①⑤②⑥③⑦….的顺序执行，P0 和 P1 将会同时访问临界区。(即并发进程中,P0执行while后正要标记数组值,这时发生切换…)
      • 因此，双标志先检查法的主要问题是：违反“忙则等待”原则。
      • 原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
    • 双标志后检查法
      • 先自己占用，然后才检查是否被占用
      • 若按照①⑤②⑥….的顺序执行，P0 和 P1 将都无法进入临界区
      • 因此，双标志后检查法虽然 解决了“忙则等待” 的问题，但是又 违背了“空闲让进”和“有限等待” 原则，会因各进程都长期无法访问临界资源而 产生“饥饿” 现象。
      • 两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。
    • Peterson算法
      • 进入区:
        1. 主动争取；
        2. 主动谦让；
        3. 检查对方是否也想使用，且最后一次是不是自己说了“客气话”
      • Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

13. 进程互斥的硬件实现方法(同步机制) （理解！！！）：

    • 硬件方法无法实现让权等待！！！
    • 中断屏蔽方法：
      • 利用开/关中断指令实现(与原语的实现思想相同,从进程开始访问临界区到结束访问为止都不允许中断,也就是不能发生进程切换)
      • 优点: 简单、高效
      • 缺点: 不适合多处理机; 只适用于操作系统内核进程,不适用于用户进程(开/关中断指令无法在用户态进行,也不能让用户随意使用)
    • TestAndSetLock指令（TSL）、Swap指令：硬件实现，不允许中断，必须一气呵成
    • 信号量
      • 信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语 wait(S)和 signal(S)访问， 也可记为 “ P 操作“ 和 “ V 操作“（来自荷兰语proberen 和verhogen）。其中S即信号量（可以是整型，也可以是复杂的记录型）。
      • 信号量其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量，P： S-- #若S不为0，则可以使用，资源S的量减少1，V： S++ # 资源使用完毕，释放资源，资源量+1。
      • 记录型信号量例子：
        1. P0申请打印机资源，S–
        2. P0使用打印机时，P1申请，S–
        3. P1使用打印机时，P2申请，S–，但此时S.value = -1，所以将其挂到等待队列中去
        4. P3申请，S–，S.value = -2，挂载到等待队列
        5. 此时P0使用完资源，S++，S.value = -1，唤醒等待队列中的一个进程（如P2，将其放入就绪队列，打印机资源分配给它）
        6. 这时P2得到处理机，使用资源并释放，S++，S.value = 0，唤醒P3，P3进入就绪队列，打印机资源分配给P3
        7. P3得到处理机，使用资源并释放，S++，因为S.value = 1，所以不需要执行唤醒操作
        8. 最后P1得到处理机并使用资源，S++，S.value = 2，不需要执行唤醒操作
      • 对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行S.value--，表示资源数减1，当S.value < 0 时表示该类资源已分配完毕，因此进程应调
        用 block原语 进行自我阻塞（当前运行的进程从运行态➡阻塞态），主动放弃处理机，并插入该类资源的等待队列S.L 中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
      • 对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数加1，若加1后仍是S.value <= 0，表示依然有进程在等待该类
        资源，因此应调用 wakeup原语 唤醒等待队列中的第一个进程（被唤醒进程从阻塞态➡就绪态）。

14. 管程（重要！！！）：

    • 用共享数据结构来描述临界资源，如：S是共享数据结构，然后take_away()申请一个资源，give_back()归还一个资源
    • 定义条件变量x，x.wait()表示将自己插入x条件的等待队列（x是否满足条件需要用户自己判断，这里一定会插入），x.signal()表示唤醒一个因为x条件阻塞的进程（一定唤醒，x是否满足条件用户判断）

15. 信号量机制实现进程同步和互斥：

    • 同步：实现进程或代码段的运行“一前一后”
    • 前驱：拆分成同步问题：
    • 认为PV操作中V操作自带唤醒功能!!!不然若多个进程互斥访问临界资源时,信号量负数,即使V操作释放了也依然负数,进程无法继续!!!

16. 死锁的条件（重要！！！）：

    • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
    • 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
    • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
    • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
      • 注意！发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）
      • 如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

17. 为什么会发生死锁：对不可剥夺资源的不合理分配，可能导致死锁。

18. 🔗银行家算法🔗

19. 死锁的检测和解除

20. 解除死锁（重要！！！）：

    1. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
    2. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
    3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

21. 大题解法：

    • 生产消费者问题：前v后p。
    • 理发师问题：理发师=0、顾客=0、空椅子=n、椅子互斥量=1。
    • 读者写者问题：1+n+n；互斥锁lock=1；同类进程计数器count=0；同类进程count互斥锁=1。
    • 哲学家问题：大锁lock=1；a、b、c类型资源=m、n、k；

¶第三章 - 内存管理

1. 内存管理：

   • 程序的装入和链接（理解！！！）：
     1. 编译：编译程序将用户源代码编译成若干目标模块
     2. 链接：各个模块和所需要的库函数链接起来（形成完整装入模块、形成逻辑地址）
        • 静态链接：程序运行前，各模块和所需库函数链接，之后不再拆开
        • 装入时动态链接：装入过程中，边装入边链接
        • 运行时动态链接：程序运行时，执行中若需要某模块，才进行链接
          • 便于修改更新，便于模块共享
     3. 装入：模块装入内存（绝对地址）
        • 绝对装入：按照绝对地址寻址
          • 编译阶段（得到模块的绝对地址）
          • 只适用于单道程序环境。
        • 静态重定位：又称可重定位装入。按照相对地址寻址
          • 装入后物理地址不再改变（固定分区分配）的才能静态重定位
          • 装入阶段
          • 特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
        • 动态重定位：又称动态运行时装入。装入内存后，绝对地址可变，而且程序运行时才进行地址转换。这种方式需要一个重定位寄存器的支持。
          • 程序执行阶段
          • 重定位寄存器：存放装入模块存放的起始位置
   • 内存保护
     1. CPU中设置上、下限寄存器
     2. 采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程（数据）的起始物理地址。界地址寄存器中存放的是进程（数据）的最大逻辑地址。

2. 连续分配管理方式（了解）：

   • 连续分配（分配一个连续的内存空间）
     • 单一连续分配（将内存分为系统区/用户区，系统区存操作系统，用户区只有一道用户程序）
     • 优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护（eg：早期的PC 操作系统MS-DOS）。
     • 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。
   • 固定分区分配
     • 分区大小也可以不等，但必须予以规定，即总的来说固定。如：较多小分区、适量中分区、少量大分区
     • 优点：无外部碎片
     • 缺点：程序过大时一个分区不够、主存利用率低、内部碎片
   • 动态分区分配
     • 进程装入时，根据程序大小动态建立分区
     • 程序运行时可以改变物理位置
     • 优点：无内部碎片
     • 缺点：外部碎片（紧凑技术）

3. 动态分区分配算法（理解）：

   首次适应算法

   • 思想: 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
   • 算法: 空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   最佳适应算法

   • 思想: 优先使用能够满足要求的最小的空闲分区
   • 算法: 空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   最坏(最大)适应算法

   • 思想: 优先使用能够满足要求的最大的空闲分区,以使得外部小碎片数量问题得到缓解.
   • 算法: 空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   邻近适应算法

   • 思想: 首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
   • 算法: 空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   总结

   
   综合来看，四种算法中，首次适应算法的效果反而更好

4. 分页（了解）：

   • 将内存空间划分为大小相等的分区, 每个分区就是一个"页框"(= 页框 = 页帧 = 内存块 = 物理块 = 物理页), 页框号从0开始。
   • 将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面” 。每个页面也有一个编号，即“页号”，页号也是从0开始,与页框号一一对应.
     • 逻辑地址分成很多页，页表项 = {页号：物理块号/页框号/内存块号}
     • 页表项大小与页面大小没有直接联系！但由页表项大小可以推出逻辑空间大小，间接得出页面大小！
       • 认为页面个数 = 页面大小 / 页表项大小
   • 页表寄存器（PTR）：方便将逻辑地址转换为物理地址。存放页表在内存中的起始地址F 和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器
   • 页表：

5. 快表

6. 🔗二级页表🔗

7. 分段存储：分段大小不定,分页大小固定.

   • 段表：每个进程都有一张逻辑空间与内存空间的映射的段表，每个段表项对应进程的一段，段表项记录了该段在内存中的始址和长度
     • 段表内容 = 段号（隐含）、段长、本段在主存中的位置

8. 段页式管理

   	优点	缺点
   分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片	不方便按照逻辑模块实现信息的共享和保护
   分段管理	很方便按照逻辑模块实现信息的共享和保护	如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片

9. 虚拟内存（了解）：
   虚拟存储技术和交换技术很像，乍一看都是换入换出，把暂时不需要用的数据换出内存，将需要用到的数据换入内存，从而实现逻辑上内存的扩充。二者之间的区别是，虚拟存储技术是在一个作业运行的过程中，将作业的数据进行换入换出。王道老师举得例子就是玩儿游戏。这儿换一个游戏，比如玩儿DOTA，停留在场景A的时候，场景B的数据不需要用到，所以不放在内存，转换到场景B的时候再把场景B的数据放入内存。而交换技术是内存紧张时，换出某些进程，腾出内存空间，换入其他进程。换而言之，交换技术是在不同的进程（作业）间的，虚拟存储技术是在一个作业间的。另外提一嘴，覆盖技术也是在同一个程序或进程中的。
   引用一个大哥的话，“交换技术是以进程为单位，若进程所需内存大于系统内存 ，则此进程无法进行。而虚拟存储是以页或段为单位，是把进程再分为页或段对内存进行分化，若进程所需内存大于系统内存，进程也可以运行，因为该进程的一部分可换到外存上”，这个总结的挺好的。(否则我以4G的老年机怎么可能运行十几G的游戏23333)

10. 请求分页管理方式

    • 缺页时，请求从外存上调入缺失的页。

11. 页面置换算法（理解！！！）：

    最佳置换算法

    

    先进先出置换算法

    
    只有先进先出算法会产生Belady异常, 即可用内存块增加, 缺页次数反而增加的现象.

    最近最久未使用置换算法

    

    时钟置换算法

    
    

12. 页面分配策略和调页时机（重要！）：

    • 页面分配策略（物理块数即页框数、驻留集大小）：
      • 固定分配全局置换
      • 可变分配全局置换
      • 可变分配局部置换
    • 调页时机：
      • 预调页策略：把预计不久将被访问的页面调入，成功率55开
      • 请求调页：进程提出缺页时，才调入
    • 调页来源：
      • 对换区充足：从对换区调入可以提高速度
      • 对换区不足：不会被修改的文件从文件区调入，可能被修改的文件换入对换区，再从对换区调入
      • UNIX方式：进程相关文件访问文件区，没有运行的页面从文件区调入，曾经运行过但被换出的页面放在对换区

¶第四章 - 文件管理

1. 文件的结构：数据项（描述某个属性的值，如文件大小是10KB、文件名是1.txt等）、记录（一组相关数据项的集合，如一个文件包含文件名、后缀名/格式、大小等）、文件（有结构文件、无结构文件）

   • 数据项 ➡ 记录 ➡ 文件

2. 文件的属性：名称、标识符（计算机识别的唯一标签，用户不可见）、类型（格式）、位置、大小、保护、其它（时间、日期、归属用户等标识）

3. 文件控制块和索引节点（理解！！！）：

   • 文件控制块（FCB）：用来存放控制文件需要的各种信息的数据结构，实现“按名存取”
     • 包含：基本信息（文件名、文件物理位置、逻辑结构、物理结构等）、存取控制信息（文件存取权限、安全）、使用信息（文件建立信息、修改时间）
   • 索引节点（检索文件时，不需要将文件调入内存，而只是查找由目录项、文件描述信息等形成的叫做索引节点的数据结构）
     • 当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
     • 磁盘索引节点：文件主标识符、文件类型（目录、文件、ISO）、文件存取权限、文件物理地址、文件大小、文件链接计数（文件系统中指向该文件的快捷方式等），文件存取/修改时间
     • 文件打开后索引节点增加的信息：
   • 索引表查找到的是逻辑地址

4. 文件共享（理解！！！）：

   • 基于索引节点的共享（硬链接）： 如共享文件D:\MATH\1.txt的物理地址及其它文件信息不再放在目录项当中，而是放在索引结点当中（目录项中关于该文件就只会有：文件名、指向改索引结点的指针）。需要共享给其它文件夹D:\ENGLISH\ 时在文件目录里增加一项指针指向那个索引节点即可
   • 基于符号链的共享（软连接）：创建一个快捷方式（内含原文件路径），将快捷方式加入要共享到的路径下即可

5. 目录的实现：线性列表（文件名：文件指针）、哈希表（哈希值：文件指针）

6. 文件的逻辑结构

   • 无结构文件(流式文件)：.txt .jpg等，往往以字节为单位存储。
   • 有结构文件(记录文件)：.csv .xls等，往往以记录为单位存储。
     • 顺序文件：每个记录都是一个定长的数据，每个记录之间没有任何的间隔。
       • 串结构：记录没有特定顺序
       • 顺序结构：记录按照特定顺序存储，可采用折半查找
     • 索引文件：采用索引表，每个表项为长度 记录指针
     • 索引顺序文件：采用索引表，每个表项为组名 记录指针，分组按顺序排列，组内无序，组间有序

7. 文件的物理结构（文件分配）（重点！！！）：

   • 连续分配
     • 记录文件的起始块号和长度
     • 支持顺序访问和随机(直接)访问
     • 连续分配的文件块物理相邻,所以方便磁盘读取
     • 不方便文件的拓展(当前连续分配块之后的空闲地址块可能不够)
     • 存储空间利用率低,产生磁盘碎片
   • 链接分配
     • 链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
     • 隐式链接
       • 记录起始块号和结束块号(或者长度),
       • 每个磁盘块(除最后)都保存有一个指针指向下一个盘块.
       • 只支持顺序访问,查找效率低
       • 不会产生碎片问题、方便拓展文件
       • 指针也要占用盘块少量空间
     • 显式链接
       • 将隐式链接盘块尾的指针用文件分配表(FAT)来表示，文件分配表记录了所有磁盘块的分配情况，开机时放入内存
       • 优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
       • 缺点：文件分配表的需要占用一定的存储空间。
   • 索引分配
     • FAT表记录了所有盘块的文件分配情况，但我们希望随文件打开再将索引表放入内存。
     • 在显示链接的基础上，将文件分配表变成索引块存在盘块上，目录信息直接指向索引盘块
     • 每个文件都有一个文件索引表，文件FCB记录了文件索引表所在的盘块号(索引块)，索引块中第i项指向该文件的第i块。
     • 优化方式：
   • 文件分配方式比较

8. 空闲空间管理（重点！！！）：

   • 空闲表法:
   • 空闲链表法:
     • 空闲盘块链
     • 空闲盘区链
   • 位示图法:
   • 成组链接法:
     • 把顺序的n个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区则保存另一顺序扇区的地址，如此继续，直到所有空闲扇区都链接上
     • 超级块：一般放在卷头，开机时超级块会被读入到主存，并保持主存和辅存超级块的一致性。

9. 虚拟文件系统VFS：用于解决不同文件系统(u盘FAT、移动硬盘NTFS)间的差异性

   • 向上层用户进程提供统一标准的系统调用接口
   • 要求下层文件系统(u盘FAT、移动硬盘NTFS)支持VFS(否则用不了)
   • 为解决不同文件系统文件结构不同的问题，为每个打开的文件创建一个vNode，vNode中保存了文件的所有信息，且指向对应下层文件系统的函数列表

10. 磁盘的结构（理解）：

    • 磁盘以簇为分配单位进行空间分配!
    • 寻找时间（寻道时间）T_s：在读/写数据前，将磁头移动到指定磁道所花的时间
      1. 启动磁头臂是需要时间的。假设耗时为s；
      2. 移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则：寻道时间T_s = s + m * n
    • 延迟时间T_r：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需的延迟时间T_r = (1/2)*(1/r) = 1/2r
    • 传输时间T_t：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则：传输时间T_t = (1/r) * (b/N) = b/(rN)
    • 可以看到操作系统唯一能够影响的只有寻道时间, 所以寻道算法很重要…

11. 磁盘调度算法（重点！！！）：

    先来先服务(FCFS)

    

    最短寻找时间优先(SSTF)

    

    扫描算法(SCAN)

    

    LOOK调度算法

    

    C-SCAN算法

    

    C- LOOK算法

    

12. 减少磁盘延迟时间的方法：扇区交替编号，因为磁头在读/写完一个数据块时（往往是一个扇区），需要经过短暂的处理时间才能继续读/写下一块

13. 磁盘的管理

    • 磁盘初始化:
      • 物理(低级)格式化：划分扇区、扇区校验码、分区
      • 逻辑格式化：创建文件系统、根目录、初始化存储空间管理的数据结构（位示图、空闲分区表）
    • 引导块:
    • 坏道

14. 固态硬盘SSD

    • 
    • 

¶第五章 - I/O管理

1. I/O设备分类（了解）：

   • 块设备。以数据块为存取单位，属于有结构设备。传输速率高，可寻址（随机读写）。
     • 硬盘、蓝光光盘、U盘
   • 字符设备。以字符为存取单位，属于无结构设备。传输速率低，不可寻址（不可随机读写）
     • 打印机、网络设备、鼠标以及大多数与磁盘不同的设备

2. I/O控制方式（理解！！！）：

   • 程序直接控制方式：每次读一个字的数据，对读入的每个字，CPU都要对外设状态循环检查
     • 读写单位：字
     • 优点：简单
     • 缺点：CPU全程负责I/O设备，效率极低。CPU和I/O只能串行
   • 中断驱动方式：
     • 读写单位：字
     • 优点：CPU效率比程序直接控制高
     • 缺点：数据的传输需要经过CPU，仍然消耗CPU的时间
   • DMA方式：
     • 读写单位：数据块
     • 在I/O设备和内存间开辟数据通路，彻底解放CPU
     • 设备直接送入内存
     • 只有当一个或多个数据块开始/结束时，CPU才会干预
     • DMA控制器的组成：
       • 命令/状态寄存器（CR）。用来接收CPU发来的控制信息，或设备的状态
       • 内存地址寄存器（MAR）。输入时，存放数据将要放到内存的起始目标地址；输出时，存放数据由内存到设备的内存源地址。
       • 数据寄存器（DR）。暂存设备到内存或内存到设备的数据
       • 数据寄存器（DC）。记录本次要传输的字（节）数
   • 通道控制方式：设置一个专门负责I/O的处理机，这个处理机就叫通道
     • 读写单位：一组数据块
     • 优点：完全解放CPU，通道只需要接收CPU的I/O任务即可
     • 缺点：实现复杂
   • DMA与通道的区别：

3. I/O软件的层次结构（了解）：

   • 设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。
     • 向上层提供统一的调用接口（如read/write系统调用）
     • 设备的保护
     • 差错处理
     • 设备分配与回收
     • 数据缓冲区管理
     • 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序
   • 设备驱动程序
     • 主要负责对硬件设备的具体控制，将上层发出的一系列命令（如read/write）转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器；检查设备状态等
   • 中断处理程序

4. 设备控制器的组成（了解）：

5. I/O调度：

   • 通过I/O调度改善系统整体性能，使得进程之间公平共享设备访问，减少I/O的平均等待时间
   • 使用主存或者磁盘上的存储空间的技术，如：缓存、高速缓存、假脱机等改善计算机效率

6. 磁盘高速缓存和缓冲区（重点！！！）：

   • 磁盘高速缓存：
     • 逻辑上属于磁盘，物理上属于驻留在内存中的盘
     • 在内存中的两种形式：
       • 在内存中开辟出一个单独的存储空间，大小固定
       • 未利用的内存空间作为缓冲池，供请求分页系统和磁盘I/O共享
   • 缓冲区：
     • 缓和CPU与I/O之间的速度差异矛盾、提高CPU与I/O的并行度、减少CPU中断的频率、解决基本数据单元大小不匹配问题
     • 实现：
       • 硬件缓冲器（成本过高）
       • 内存缓冲区
     • 分类：
       • 单缓冲：
         • T：I/O ➡ 缓冲区，M：缓冲区 ➡ 用户区，C：CPU处理
         • 使用时间MAX(C , T) + M
       • 双缓冲：
         • 使用时间MAX(C + M , T)
       • 循环缓存：包含多个大小相等的缓冲区，通过指针首位相连形成环状。
       • 缓冲池：
         • 缓冲区分为三个队列：空缓冲、输入缓冲、输出缓冲。
         • 缓冲池包含四种缓冲区：收容输入、收容输出、提取输入、提取输出
   • 高速缓存和缓冲区的对比：
     • 相同点：速度都介于高速设备和低速设备之间
     • 不同点：
       • 数据来源：高速缓存存放的是低速设备上的某些数据的复制；缓冲区存放的是低速设备传给高速设备的数据
       • 数据目标：高速缓存放的是高速设备经常要访问的（低速设备）数据，若高速缓存中没有，高速设备就直接访问低速设备；高速设备和低速设备的双向通信都经过缓冲区，高速设备永远不会直接访问低速设备
         • 数据流向：高速设备 ⬅ 高速缓存 ⬅ 低速设备、高速设备 ↔ 缓冲区 ↔ 低速设备

7. 设备分配的数据结构（了解、类比Windows的设备管理器！！！）：

   • 设备控制表（DCT）：一个设备控制表对应一个设备，控制表是设备的各项属性
   • 控制器控制表（COCT）：记录某个设备控制器的具体信息
   • 通道控制表（CHCT）：记录某个通道设备的具体信息
   • 系统设备表（SDT）：记录已经连接到系统的所有物理设备的情况

8. 设备分配的策略（发挥效率，避免死锁）：

   • 静态：设备一次性分配给相应的作业，直到作业结束
     • 没有死锁，但设备利用率低
   • 动态：进程执行过程中根据需要进行分配
     • 设备利用率高，但算法不当会导致死锁
   • 独占设备一般静态分配，共享设备一般动态分配。

9. 设备分配的安全性：

   • 安全分配方式：进程发出I/O请求后立即阻塞（无条件），I/O完成后唤醒
     • CPU和I/O设备串行工作
   • 不安全分配方式：进程发出I/O请求后继续运行，需要时发出第二个、第三个请求
     • 进程推进速度快，但可能产生死锁

10. 假脱机技术（SPOLLing）

    • 当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
    1. 在磁盘输出井中为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的），并将要打印的数据送入其中；
    2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件队列上。当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务

11. 设备分类：独占设备、共享设备、虚拟设备。

    • 独占设备: 一个时段只能分配给一个进程（如打印机）
    • 共享设备: 可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。
    • 虚拟设备: 采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使
      用（如采用SPOOLing技术实现的共享打印机）

¶新考点

1. 用户进程
2. 分层操作系统
   • 便于维护,增加一层
   • 难以定义层边界
3. 模块操作系统
4. 外核
5. 虚拟机
   1. 第一类虚拟机管理程序: 内核态
   2. 虚拟机: 用户态(以为自己在内核态)
   3. 第二类虚拟机即我们常用的虚拟机软件,第一类虚拟机会直接管理硬件.第二类虚拟机管理程序运行在用户态
6. 操作系统引导: 运行RAM自举程序,将操作系统内核部分从磁盘加载到内存.
7. 虚拟文件系统: 操作系统可能有多个文件系统,其调用的接口各不相同,因此引入虚拟文件系统VFS,用户进程只需使用VFS提供的接口,VFS负责文件操作和将结果返回给用户进程

¶tool

四号绿: <font color=green size=4></font>
四号红: <font color=red size=4></font>
红:    <font color=red></font> 
绿:    <font color=green></font>
蓝:    <font color=blue></font>

分割线:  

----------------------------

表格:  
|        |      |       |
| ----- | --:  | :----: |
|       |       |       |
|       |       |       |
|       |       |       |

拼图
{% gi 2 2 %}

{% endgi %}

便签：  
{% note success %}  

{% endnote %}

链接:  
🔗