OS大纲

操作系统概述

基本概念

• 操作系统 (Operating System, OS) 是指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。操作系统是计算机系统中最基本的系统软件。
• 基本特征：并发、共享、虚拟、异步。
  • 并发和共享是最基本的特征。
  • 注意区分并发和并行
• 目标和功能
  • 作为计算机系统资源的管理者
    • 处理机管理（进程管理）
    • 存储器管理（内存管理）
    • 文件管理
    • 设备管理（IO 管理）
  • 作为用户与计算机硬件系统之间的接口
    • 命令接口：
      • 联机命令接口/交互式命令接口：用于分时或实时系统，由命令解释程序解释用户输入的命令。
      • 脱机命令接口/批处理命令接口：用于批处理系统，由一组作业控制命令组成，提交后用户不能干预。
    • 程序接口：
      • 由一组系统调用组成。
  • 实现对计算机资源的扩充：
    • 裸机 → 虚拟机

发展历程

• 手工阶段：
  • 独占计算机资源，资源利用率低。
• 脱机处理：
  • 减少了 CPU 的空闲时间，提高了 IO 速度
• 早期批处理：
  • 高效利用CPU的资源
• 多道批处理：
  • 多道、宏观上并行、微观上串行
• 分时操作系统：
  • 交互性强
• 实时操作系统：
  • 及时性和可靠性强，交互性不如分时系统
• 网络操作系统：
  • 服务于计算机网络，集中控制方式。
• 分布式操作系统：
  • 建立在网络操作系统上，控制功能均为分布式
• 个人计算机操作系统
  • 目前最广泛

程序运行

• CPU 运行模式
  • 指令：
    • 特权指令：I/O 指令、关中断指令、内存清零指令、存取内存保护寄存器、送 PSW 到 PSWR 等。
    • 非特权指令：访管指令等。
  • CPU 模式：
    • 用户态/目态：只能执行非特权指令。
    • 核心态/管态/内核态：能执行除访管指令的所有指令。
• 原语-原子操作：必须连续运行，硬件实现或关中断。
• 系统调用
  • 执行过程：

层次结构

• 分层法，模块化
• 宏内核：只有微内核运行在内核态，其余模块运行在用户态。
• 微内核：只有微内核运行在内核态，其余模块运行在用户态
• 外核：运行在内核态，为虚拟机分配资源，并检查安全性。

引导

1. CPU 运行 ROM 中的 BIOS。
2. BIOS 构建中断向量表，检查硬件是否故障。
3. BIOS 读取设备清单（CMOS 保存或用户手动配置），逐个找到有 MBR 的磁盘。
4. 读取引导扇区（第一个扇区）MBR/主引导记录，MBR 包含引导代码和分区表。
5. MBR 检查分区表，找到活动分区/引导分区。
6. 读取活动分区的第一个扇区 PBR/分区引导记录。
7. PBR 找到启动管理器 Boot Loader。
8. 启动管理器加载操作系统初始化程序。
9. 操作系统初始化程序加载操作系统。

虚拟机

• 两类虚拟机（又称裸金属架构和寄居架构）
  • 第一类虚拟机：裸金属架构
    • 
  • 第二类虚拟机：寄居架构
    • 

进程管理

进程与线程

进程

• 是系统进行资源分配的基本单位
  • 若未引入线程，还是处理机分配的基本单位
• 进程的组成：
  • 进程控制块 PCB
  • 程序段
  • 数据段
• 状态转换
  • 
• 进程控制
  • 创建：
    • 父进程创建子进程
      • 子进程继承父进程的所有资源
    • 申请 PCB，分配资源，初始化 PCB，插入就绪队列
  • 终止：
    • 终止运行，
    • 回收资源和PCB，包括其子进程
  • 阻塞：
    • 使用阻塞原语，保护现场，PCB 插入阻塞队列
  • 唤醒：
    • 使用唤醒原语，PCB 插入就绪队列
• 进程通信
  • 共享存储：
  • 消息传递：
    • 直接通信
    • 间接通信：信箱
  • 管道：
    • 是一种特殊的文件，是固定大小的缓冲区
    • 先进先出
    • 互斥、同步、确定对方存在
    • 子进程继承父进程的管道，可用于父子进程通信
    • 读数据是一次性的

线程

• 处理机分配的基本单位
• 线程不拥有系统资源，同一进程的线程共享地址空间和全局变量
• 通常线程被终止后，只有其他线程执行分离函数后才释放资源
• 实现方式：
  • 用户级线程
    • 内核意识不到线程的程序
    • 对线程的操作都是在用户态完成
  • 内核级线程
    • 在内核态完成线程的操作
    • 操作系统为每个内核级线程设置一个线程控制块TCB，根据控制块感知线程的存在，加以控制
  • 组合方式
    • 内核支持多个内核级线程的建立、 调度和管理
    • 同时，允许用户程序建立多个用户级线程
    • 同一进程中的多个线程可以同时在多 CPU 上并行执行, 且在阻塞一个线程时不需要将整个进程阻塞,
• 多线程模型：
  • 多对一
  • 一对一
  • 多对多
• 轻量级线性，其余没写到的部分都和进程类似

CPU调度

• CPU调度的概念
  • 三级调度：
    • 高级调度（作业调度）：
      • 批处理系统，内存与外存作业的调度
    • 中级调度（内存调度）：
      • 内存与外存进程的调度
    • 低级调度（进程调度）：
      • 最基本的调度，等待事件
  • 调度程序（调度器）：
  • 调度时机：
    • 创建进程后，
    • 进程结束后，
    • 进程阻塞时，
    • IO结束时
  • 抢占调度（剥夺），
  • 非抢占调度（非剥夺）
  • 闲逛进程：不会被阻塞
• CPU调度的实现
  • 指标：
    • CPU 利用率，
    • 系统吞吐量，
    • 周转时间，
    • 平均周转时间，
    • 带权周转时间，
    • 平均带权周转时间，
    • 等待时间，
    • 响应时间
  • 上下文切换：
    1. 保存当前进程上下文到 PCB
    2. PCB 移入相应队列
    3. 调入新 PCB，从其 PCB 恢复现场
• 调度算法：
  • 先来先服务 FCFS
  • 短作业优先 SJF
  • 高响应比优先
  • 优先级调度
  • 时间片轮转调度 RR
  • 多级队列调度
    • 

同步与互斥

• 概念：
  • 临界资源
    • 一个时间段只允许一个进程使用的资源， 各进程需要互斥的访问临界资源
  • 临界区
    • 临界区指的是同一时间只能供一个进程访问的代码块
  • 内核程序临界区
    • 一般是用来访问某种内核数据结构的，例如进程的就绪队列（由各就绪进程的 PCB 组成）
  • 同步
  • 互斥
• 互斥
  • 准则：
    • 空闲让进
    • 忙则等待
    • 有限等待
    • 让权等待（并不必须遵守，很多方法采用忙等）
  • 基本方法
    • 软件实现互斥
      • 单标志
        • 违背“空闲让进”：若一方不进，另一方也没法进
        • 设置标志turn，进程的turn被设置为1，进程就进入临界区，否则等待
        • 如果两个人都没进去，也就是都认为对方要进去了，从而自己不进，导致两个人都进不去
      • 双标志先检查
        • 违背“忙则等待”：可能同时进入
        • 进程先检查对方是否进入临界区，若对方未进入，自己进入
        • 如果两者几乎同时检查对方是否进入，同时检测到对方没进入，导致两个人一起进入，只能一个人进入的区域
      • 双标志后检查
        • 违背“空闲让进”，违背“有限等待”：死锁，饥饿
        • 进程先设置自己的标志，表示想要进入，再看对方的
        • 如果两者同时设置了想要进入，互相看对方都认为对方要进入，那么就没有人真的可以进入，形成了死锁，想进去吃饭的，吃不上就形成饥饿
      • Peterson 算法
        • 违背“让权等待”：忙等
        • 设置了公共变量true，作为回合的概念，让对方先进，表示此时是对方的回合，依次给对方赋值，取最后一次的值
          • 也就避免了两个人都想进，但是都认为对方要进，结果两个人都进不去
          • 即使自己可以进去，也要让对方进，除非对方真的不想进
            • 假设有两个进程 P0 和 P1 竞争使用打印机（临界资源）。
            • P0 先到达，设置 flag[0] = true 和 turn = 1，表示自己想进入临界区，并礼貌地让 P1 先进入。
            • P1 到达，设置 flag[1] = true 和 turn = 0，表示自己也想进入临界区，并礼貌地让 P0 先进入。
            • 此时，P0 检查循环条件 flag[1] && turn == 1。由于 flag[1] 为真，但 turn 为 0，所以 P0 可以进入临界区，开始打印。
            • 假设 P0 的打印任务需要很长时间。
            • 现在，假设有一个新的进程 P2 需要使用 CPU 执行其他任务。
            • 虽然 P1 无法进入临界区，但它仍然在 while (flag[0] && turn == 0) 循环中忙等待，占用着 CPU。
            • 这就导致 P2 无法获得 CPU 的使用权，即使 P0 正在进行 I/O 操作（打印），CPU 实际上是空闲的。
    • 硬件实现互斥
      • 中断屏蔽：
        • 流程
          • 关中断
          • 临界区
          • 开中断
      • TestAndSet 指令（TS 指令）（原子操作）
        • 为临界区设置一个共享变量lock

        • 2.3-同步与互斥#^19ykpy

      • Swap 指令（原子操作）
        • 设置共享的lock和局部的key

        • 2.3-同步与互斥#^j5huyu

  • 互斥锁
    • 解决临界区（只能一个访问）问题最简单的工具

    • 2.3-同步与互斥#^08w1iv

    • available就是锁
  • 信号量（PV操作）
    • 整形信号量：
      • wait(S) 相当于进入区，
      • signal(S) 相当于退出区，使
        • 用完后，就释放一个资源，违背“让权等待”，忙等
    • 记录型信号量：
      • 数据结构
      • 使用方法
      • 用来解决：
        • 同步
        • 互斥
        • 前驱关系
  • 管程
    • 概念：共享数据结构及其之上的操作过程构成的资源管理程序，面向对象里的类 (class)
    • 条件变量的定义与使用
      • 条件变量没有值，有值的是共享数据结构
      • 条件变量只起到阻塞和唤醒进程的作用

死锁

• 概念
  • 定义：形成僵局
  • 产生原因：
    • 不可剥夺资源不足
    • 使用资源顺序不当
  • 必要条件：
    • 互斥条件：
      • 仅有独占设备会引起死锁，共享设备不会
    • 不可剥夺条件：
      • 只有不可剥夺的资源会引起死锁，可剥夺的不会
    • 请求并保持条件：
      • 死锁进程数必然大于等于两个，死锁进程必然处于阻塞态
    • 循环等待条件：
      • 死锁发生时资源分配图必含圈
• 解决策略
  • 死锁预防：破坏必要条件
    • 破坏互斥条件：
      • 独占资源改造为共享资源
    • 破坏不可剥夺条件：
      • 进程已占有的资源允许暂时释放（被剥夺）
    • 破坏请求并保持条件：
      • 逐步分配，逐步释放
    • 破坏循环等待条件：
      • 编号，顺序资源分配
  • 死锁避免：防止系统进入不安全状态
    • 相关概念：
      • 安全序列
      • 安全
    • 银行家算法
      • 构造数据机构
      • 尝试分配
      • 执行安全性算法
  • 死锁检测和解除：不采取限制措施，及时检测及时解除
    • 死锁检测
      • 资源分配图
      • 可完全简化
        • 死锁定理
    • 死锁解除
      • 资源剥夺法
      • 撤销进程法
      • 进程回退法