操作系统知识总结

操作系统知识全面总结与梳理，操作系统相关知识，进程与线程区别联系，线程调度，linux常用命令，扩展知识点，内存屏障，指令乱序，分支预测。

操作系统

• 内存管理
  • 存储器的层次结构
    • 寄存器
      • CPU寄存器
    • 高速缓存
    • 主存储器
    • 磁盘缓存
    • 主存
    • 固定磁盘
    • 可移动存储介质
    • 辅存
  • 装入和链接
    • 装入
      • 绝对装入
        • 目标模块采用绝对地址
        • 逻辑地址和实际地址完全相同
        • 适用于单道环境
      • 可重定位装入
        • 在程序装入的时候装入
        • 存在地址变换，但是是直接找的当前合适的内存位置
        • 程序需要连续空间
        • 不存在在程序执行的过程中在内存移动
      • 动态运行时装入
        • 地址转换在程序需要真正执行时才进行
        • 可以在内存之中移动
        • 可以实现虚拟存储
    • 链接
      • 静态链接
        • 在程序运行之前，将各目标模块以及它们需要的库函数链接成一个完整的转入模块
      • 装入时动态链接
        • 在装入的时候边装入边链接
        • 便于修改和更新
        • 便于实现目标模块的共享
      • 运行时动态链接
        • 当程序需要的时候采取链接
        • 节约内存空间、加快装入过程
  • 连续分配方式
    • 单一连续分配
    • 固定分区分配
      • 分区使用表
      • 内存利用与回收
      • 缺点
        • 规定了分区大小，大程序无法装入
        • 限制了活跃进程的最大数
        • 碎片过多
        • 扩充和贡献困难
    • 动态分区分配
      • 算法
        • 首次适应算法
        • 循环首次适应算法
        • 最佳适应算法
        • 最坏适应算法
      • 管理空闲分区
        • 空闲分区表
        • 空闲分区链
      • 分区回收
      • 分区分配
      • 没有程序数目和大小的限制但是会产生过多的碎片
    • 动态重定位分配
      • 重定位寄存器
      • 地址变换机构
      • 目标程序
    • 伙伴系统
      • 伙伴算法
      • 内存分配
      • 内存回收
      • 在进程释放存储空间时，寻找伙伴合并，可以做到类似递归进行，知道找不到可以合并的伙伴为止
    • 交换
      • 以进程为单位
      • 以页或段为单位
  • 基本分页存储管理方式
    • 存储空间
      • 主存中为块
      • 进程的逻辑结构中为页
    • 页面与页表
      • 页表存放
        • 页表
        • 为记录页面在内存中对应的物理块
      • 页表
      • 逻辑地址构成
        • 页号
          • 即在第几页
        • 页内位移
          • 即距离页面里面第一个地址的距离
          • 总的大小为页面大小，如1KB的页面，会有2的10次方的地址
        • 逻辑地址从0开始
    • 为解决连续分配方式存在的碎片
    • 地址变换机构
      • 分页逻辑地址
      • 映射
      • 快表
      • 两级和多级页表
        • 每多一次页表会多一次对主存的访问
    • 信息共享
    • 可重入代码
  • 基本分段存储管理方式
    • 逻辑地址结构
    • 段表
    • 与分页的区别
    • 信息共享
    • 大小
      • 逻辑地址结构
        • 段号
          • 通过段号可以知道最多允许有多少分段
        • 段内地址
          • 可以知道每段的最大长度
          • 不定
  • 段页式存储管理方式
    • 逻辑地址结构
    • 先分段再分段
      • 所以会先访问段表再访问页表
      • 最后访问信息
    • 段表和页表
  • 虚拟存储器
    • 原理
      • 请求调入
      • 置换
      • 局部性原理
        • 程序中少量分支和过程调用大都是顺序执行
        • 过程调用深度有限，
        • 存在着许多循环
        • 数组等数据结构
        • 体现
          • 时间局部性
          • 空间局部性
    • 物质基础
      • 相当数量的外存
      • 一定容量的内存
      • 地址变换机构
    • 实现方法
      • 请求分页存储管理方式
        • 内存分配和分配算法
          • 进程需要的最小物理块数
            • 执行一条指令所涉及的页面数确定
            • 单地址指令
              • 直接寻址
              • 间接寻址
              • 功能较强时
          • 进程的物理块数是固定还是可变
            • 固定分配局部置换
            • 可变分配全局置换
            • 可变分配局部置换
          • 按什么原则为进程分配物理块数
            • 平均分配算法
            • 按比例分配算法
            • 按优先级分配算法
            • 实现方案
          • 局部范围内
            • 页面置换算法
              • 最佳置换算法
                • 将来最长时间不会使用
                • 仅具有理论意义
              • 先进先出算法
                • 选择调入主存时间最长的页面予以淘汰
              • 最近最久未使用置换算法
                • 选择最近一段时间内最长时间没有被访问过的页面予以淘汰
                • 实现
                  • 基于寄存器的方法
                    • 配置一个n位寄存器，在进程访问页面的时候最左置1
                    • 每过一段时间则计数器右移1位
                    • 最小数值的寄存器即最近最久未使用的页面
                  • 基于栈的方法
                    • 栈顶存放最近使用过的页面
              • 时钟置换算法
                • 将页面设置成循环队列
                • 首次调入内存，置访问位置1
                • 被访问置访问位置1
                • 缺页中断的时候
                  • 访问为0则淘汰
                  • 不为0则置为0
                  • 接上次判定界面位置
                • 改进：访问位和修改位分开考虑
                  • 有四种情况
                  • 先寻找访问位和修改位都为0的页面淘汰
                  • 没有则再寻找访问页为0，修改位为1的淘汰，并将访问位设置为0
                  • 没有重复一操作
              • 其他置换算法
          • 性能分析
            • 有效访问时间
              • 访问存储器所需时间的平均值
              • 在快表中，则需要访问一次主存
              • 不在内存，则要缺页中断时间
                • 缺页中断时间
                  • 缺页中断时间
                  • 界面传送时间
                  • 进程重新执行时间
                  • 仅考虑页面传送时间
                • 影响缺页率的因素
                  • 分配给进程的物理块数
                  • 页面本身大小
                  • 程序编制方法
                  • 页面置换算法
            • 抖动现象
              • 全局抖动
              • 局部抖动
              • 产生原因
                • 进程分配物理块太少
                • 置换算法选择不当
                • 全局置换使抖动传播
              • 预防与解除
                • 采用局部置换策略
                • 增加分配给相应进程的物理块
                • 挂起进程
            • 页面大小的选择
              • 有个最佳界面大小可以选择
              • 每个页表项需e个字节
              • 内存大小为m
              • 进程的平均长度为s
              • 计算开销 碎片项和页表项的总和（pm/2s + me/p）求最小值
              • p=2es的算术平方根
        • 调页策略
          • 何时
            • 预调页策略
            • 请求调页策略
          • 何处
            • 文件区
              • 存放文件
              • 离散分配
            • 对换区
              • 存放对换页面
              • 连续分配
              • 磁盘I/O较高
          • 情况
            • 对换区空间足够
            • 对换区空间不够
              • 将进程中可能被修改的调入对换区
            • UNIX方式
              • 全部存放在文件区
              • 运行过调出的放于对换区
              • 存在页面共享
        • 支持机构
          • 页表
            • 扩充的页表
          • 缺页中断机构
            • 缺页中断
            • 中断过程
          • 地址变换机构
            • 类似于分页存储管理
            • 进行缺页中断处理
      • 请求分段存储管理方式
        • 请求调段
        • 分段置换
        • 支持结构
          • 段表
          • 缺段中断机构
            • 类似缺页中断
            • 内存管理
            • 段的置换
              • 有空间则直接调入
              • 没有就检查空闲区之后是否满足
              • 再不符合则淘汰若干段
          • 地址变换机构
            • 动态地址变换
        • 分段共享
          • 实现
            • 为了实现分段共享，可在系统中设置一张共享段表，所有共享分段都在其中占有一表项
            • 增加共享进程计数
            • 存取控制字段
            • 共享段在不同进程中有不同的段号
          • 分配
            • 对于第一个请求使用该段的进程，系统为该共享段分配一个内存区，在将共享段调入
            • 同时将该区的始地址填入请求进程的段表
            • 在共享段表中增加一项，填写有关数据将count置1
            • 填入相关的数据结构
          • 回收
            • 释放该进程段，将count减一
            • 如果变为0则需要系统回收共享段的物理内存及有关表项
        • 分段保护
          • 越界保护
            • 用段表长度与逻辑地址中的段号比较
            • 段长与逻辑地址中的段内位移比较
          • 存取方式检查
            • 本段的访问方式
          • 环保护结构
            • 低编号环具有高优先权
            • 原则
              • 一个程序可以访问在相同的环或者较低环中的数据
              • 一个程序可以调用驻留在相同环或较高环中的服务
    • 特征
      • 多次性
      • 对换性
      • 虚拟性
• 设备管理
  • I/O设备
    • I/O设备的类型
      • 传输速率
      • 信息交换单位
      • 共享属性
        • 拓展
    • 设备与控制器之间的接口
      • 数据信号线
      • 状态信号线
      • 控制信号线
      • 设备控制器
        • 功能
        • 组成
    • I／O设备通道
      • 类型
        • 字节多路
          • 以字节交换方式工作
          • 含有若干个非分配型子通道
          • 每个子通道连接一台I/O设备
          • 按时间片轮转方式共享主通道
          • 用于中低速设备
        • 数组选择
          • 以数组方式进行数据传送
          • 只有一个分配型子通道
          • 不允许其他设备使用该通道
        • 数组多路
          • 字节多路和数组选择的综合
      • 功能
        • 特殊的处理机，具有执行I/O指令的能力
        • 通过执行通道程序来控制I/O操作
        • 指令单一
        • 通道没有自己的内存
    • 多通路I/O系统
      • 存储器到设备之间有多通道
      • 提高运输速率
    • 总线系统
      • ISA和EISA总线
      • 局部总线
        • VESA
        • PCI
  • I/O控制方式
    • 程序I/O方式
      • CPU要不断地测试I/O设备的状态
      • 没有中断机构
      • 让I/O设备无法向CPU报告已完成一个字符的输入操作（是CPU没有办法终止）
    • 中断驱动I/O控制方式
      • 加入中断
      • 在输完一个数据时，需要CPU花费极短时间去做中断处理
    • DMA I/O控制方式
      • DMA
        • 组成
          • 命令／状态寄存器CR
            • 接收从CPU发来的I/O命令
            • 有关控制信息
            • 设备的状态
          • 内存地址寄存器MAR
            • 输入时，存放把数据从设备传送到内存的起始目标地址
            • 输出时，存放由内存到设备的内存源地址
          • 数据寄存器DR
            • 存储数据
            • 从设备到内存
            • 从内存到设备
          • 数据计数器DC
            • 本次CPU要读或写的字节数
        • 工作过程
          • 设置MAR和DC初值
          • 启动DMA传送命令
          • 挪用存储器周期传送数据字
          • 存储器地址增一
          • 字节数寄存器减一
      • 特征
        • 传输单位是数据块
        • 从设备和内存之间直接交互
        • 尽在数据块的传送开始和结束时，才需要CPU干预，在控制器的控制下完成传送
    • I/O通道控制方式
      • 进一步减少CPU的干预
      • 对一组数据块的相关操作
      • 通道程序
        • 向I/O通道发送一条I/O指令，以给出其所要执行的通道程序首地址和要访问的设备
        • 通道执行通道程序即可完成CPU的I/O任务
        • 组成
          • 操作码
          • 内存地址
          • 计数
          • 通道程序结束位P
          • 记录结束标志R
  • 缓冲管理
    • 缓冲
      • 单缓冲
      • 双缓冲
      • 循环缓冲
    • 缓冲池
      • 既可以用于输入又可用于输出
      • 空缓冲区
        • 队列emq
      • 装满输入数据的缓冲区
        • 队列inq
      • 装满输出数据的缓冲区
        • 队列outq
  • 设备分配
    • 设备独立性
      • 逻辑设备
      • 物理设备
      • 设备独立性软件
        • 执行所有设备的公有操作
          • 对独立设备的分配与回收
          • 映射
          • 对设备进行保护，禁止用户直接访问设备
          • 缓冲管理
          • 差错控制
        • 向用户层(或文件层)软件提供统一接口
      • 映射
      • 好处
    • 数据结构
      • 设备控制表
      • 控制器控制表
      • 通道控制表
      • 系统设备表
    • 考虑因素
      • 设备的固有属性
      • 设备分配算法
      • 设备分配中的安全性
    • 分配程序
      • 基本的设备分配程序
      • 设备分配程序的改进
    • 设备分配
      • 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环境
            • 转入相应的设备处理现场
            • 中断处理
            • 恢复被中断进程的现场
        • 硬件
    • SPOOLing技术
      • 为了缓和CPU的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术
      • 把低速I/O设备上的数据传送到高速磁盘上
      • 实现
        • 利用其中的一道程序，来模拟脱机输入时的外围控制机功
        • 再用另一道程序来模拟脱机输出时外围控制机的功能
        • 共享打印机
          • 将输出进程在输出井中申请一个空闲磁盘块区，并将打印的数据送入其中
          • 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入，再将该表挂到请求打印队列
      • 特点
        • 提高I/O速度
        • 将独占设备改造共享设备
        • 实现了虚拟设备功能
  • 磁盘存储器管理
    • 磁盘性能简介
      • 数据的组织和格式
      • 磁盘类型
        • 固定头磁盘
          • 在每条磁道上都有一读/写磁头
        • 移动头磁盘
          • 每一个盘面仅配有一个磁头
          • 移动磁头仅能以串行方式读/写
      • 磁盘访问时间
        • 寻道时间
          • 启动磁臂的时间s与磁头移动n条磁道所花费的时间之和
          • Ts=m×n+s
          • m是一常数，与磁盘驱动器的速度有关
        • 旋转延迟时间
          • 指定扇区移动到磁头下面所经历的时间
        • 传输时间
          • Tt的大小与每次所读/写的字节数b和旋转速度有关
          • r为磁盘每秒钟的转数；N为一条磁道上的字节数
        • 总时间
    • 磁盘调度
      • 先来先服务FCFS
        • 按进程请求访问磁盘的先后次序进行调度
      • 最短寻道时间优先SSTF
        • 选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象
        • 可能产生“饥饿”现象
      • 扫描(SCAN)算法
        • 当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象
      • 循环扫描(CSCAN)算法
        • 磁头移到最外磁道时立即又返回到最里磁道
        • 消除了对两端磁道请求的不公平
      • N-Step-SCAN
        • N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列
        • 每处理一个队列时又是按SCAN算法
        • 当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列
      • FSCAN调度算法
        • 一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理
        • 将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理
  • 磁盘高速缓存
    • 逻辑上属于磁盘，而物理上是驻留在内存中的盘块
    • 形式
      • 在内存中开辟一个单独的存储空间来作为磁盘高速缓存
      • 把所有未利用的内存空间变成一个缓冲池，供请求分页系统和磁盘I/O时共享
        • 当磁盘I/O的频繁程度较高时，该缓冲池可能包含更多的内存空间
        • 而在应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间
    • 数据交付方式
      • 数据交付
        • 直接将高速缓存中的数据，传送到请求者进程的内存工作区
      • 指针交付
        • 只将指向高速缓存中某区域的指针，交付给请求者进程
        • 数据量小，节省了时间
  • 置换算法
  • 周期性地写回磁盘
    • UNIX方法
    • MS-DOS方法
  • 提高速度的方法
    • 提前读
    • 延迟写
    • 优化物理块的分布
    • 虚拟盘
• 进程管理
  • 进程的基本概念
    • 程序的顺序执行及其特征
    • 前趋图
    • 程序的并发执行及其特征
    • 进程的特征与状态
      • 特征
        • 结构性
        • 动态性
        • 并发性
        • 独立性
        • 异步性
      • 状态
        • 基本状态
          • 就绪
          • 执行
          • 阻塞
        • 进程的挂起
          • 静止就绪
          • 静止阻塞
        • 考虑全局
          • 创建状态
          • 终止状态
        • 转换
    • 进程控制块
      • 进程标识信息
      • 处理机状态信息
      • 进程调度和状态信息
      • 进程控制信息
      • 组织方式
        • 链接方式
        • 索引方式
  • 进程控制
    • 前置概念
      • 进程图
      • 原语
    • 进程的创建
      • 引起事件
      • 创建原语
        • 创建一个空闲PCB结构
        • 为新进程分配资源
        • 初始化新的PCB结构
        • 将PCB结构插入相应的队列
    • 进程的终止
      • 引起事件
      • 终止原语
        • 根据进程标识符，找到相应的PCB，读取状态
        • 如果正处于进行状态，则停止进程的执行
        • 如果有子进程，终止子进程
        • 归还资源到父进程或者系统
        • 撤销PCB
    • 进程的阻塞与唤醒
      • 引起事件
      • 阻塞原语
        • 根据当前执行进程的标识符找到PCB
        • 停止执行进程，改状态为阻塞
        • 保存进程的现场到PCB结构
        • 将该进程PCB插入等待队列
        • 转进程调度程序
      • 唤醒原语
        • 从等待队列中取出相应进程
        • 改程序状态为就绪，将进程插入就绪队列
        • 转进程调度或返回
    • 进程的挂起与激活
      • 挂起引起事件
      • 挂起原语
        • 根据被挂起进程的标识符，找到PCB
        • 取PCB的状态
          • 运行状态
          • 就绪状态
          • 等待状态
      • 激活原语
        • 系统将外存上被挂起的进程换入内存
        • 将进程状态由挂起改为激活后的状态
        • 有需要转进程调度
  • 进程同步
    • 进程同步的基本概念
      • 进程制约关系
        • 相互协作关系
        • 资源共享关系
      • 临界资源与互斥
        • 临界资源
        • 互斥
        • 临界区
        • 同类临界区
      • 互斥与同步
        • 互斥
        • 同步
    • 信号量机制
      • 信号量
        • 整型信号量
          • Wait(S) P操作
          • signal(S) V操作
          • 缺点
        • 记录型信号量
          • 增加记录资源数目的整型变量value值
          • 增加一个进程链表指针L 链接所有等待进程
          • signal和wait原语操作
          • 记录型数据结构包含value值和链表L
        • AND型信号量集
          • 全部分配或全不分配
        • 信号量集
          • 和AND型信号量集一样
          • 加判断条件后全分配或全不分配
          • 特殊应用
    • 信号量的应用
      • 实现互斥
        • wait(mutex)
        • 临界区
        • signal(mutex)
      • 实现前趋关系
        • S1
        • signal(S)
        • wait(S)
        • S2
    • 管程机制
      • 管程
        • 管程名字
        • 局部于管程的共享数据结构（变量）
        • 对共享数据结构进行的一组操作（函数）
        • 对局部于管程的数据设置初始值的语句
      • 基本特性
        • 共享变量仅能由管程内定义函数访问
        • 一个进程只有通过调用管程内函数才能访问共享变量
        • 管程互斥进入
        • 由编译程序在编译时自动添加上
      • 入口等待队列
      • 紧急等待队列
        • x.wait
        • x.signal
      • 条件变量
        • 说明
          • 同步原语
            • x.wait
            • x.signal
          • condition x
        • 作用
      • 生产者、消费者
  • 经典进程的同步问题
    • 生产者--消费者问题
      • 用记录型信号量解决
        • 用empty和full分别表示空缓冲区的数量和满缓冲区的数量
          • empty初值为n
          • full初值为0
        • 临界资源mutex 初值为1
        • • wait次序颠倒
            • 生产者
            • 消费者
      • 用AND信号量解决
    • 哲学家进餐问题
      • 算法描述
      • 存在问题
      • 尝试解决
        • 至多允许四个哲学家同时进餐
        • 同时使用左右筷子
        • 奇数号哲学家先拿左边筷子再拿右边筷子，偶数号哲学家相反
      • 用AND信号量解决
    • 读者--写者问题
      • 共享整型变量 readcount 记录当前正在读数据的读者数量
        • 初值为0
      • wmutex 用于写者与写者、写者与读者之间的互斥
        • 初值为1
      • rmutex 用于读者互斥地访问共享变量readcount
        • 初值为1
      • 算法描述
        • 读者描述
        • 写者描述
      • 使用信号量集解决
        • 至多允许RN个读者同时读
        • 引入信号量L 初值为RN
        • 信号量mx 初值为1
  • 进程通信
    • 进程通信的类型
      • 共享存储器系统
        • 共享数据结构
        • 共享存储区
          • 建立
          • 附接
          • 断接
      • 管道通信系统
        • 互斥
        • 同步
        • 确定对方是否存在
      • 消息传递系统
        • 直接通信方式
        • 间接通信方式
      • 客户机-服务器系统
        • 套接字
          • 基于文件型
          • 基于网络型
        • 远程过程调用
        • 远程方法调用
    • 消息传递通信的实现方式
      • 直接消息传递系统
        • 发送原语
        • 接受原语
        • 过程
          • 在自己的工作区设置一个发送区
          • 适用发送原语发送给接收进程，将其挂在接收进程的消息队列上
          • 调用接收原语从自己的消息队列中摘下第一个消息，将内容复制到自己的消息接收区
        • 消息缓冲区
        • 增加的数据结构
        • 对称寻址方式
      • 信箱通信
        • 私用邮箱
          • 用户进程创建、其余进程只可发送
        • 公用邮箱
          • 操作系统创建
        • 共享邮箱
          • 用户创建，可共享
        • 非对称寻址方式
        • 结构
          • 信箱头
          • 信箱体
        • 信箱原语
          • 创建和撤销
          • 消息的发送和接收
      • 管道通信
        • 以管道方式
  • 线程
    • 线程的基本概念
      • 是进程内的一个执行单元
      • 资源分配的实体还是进程
      • 线程是调度和分派的基本单位
      • 将进程的两个属性分开
      • 属性
        • 轻型实体
        • 独立调度和分派的基本单位
        • 可并发执行
        • 共享进程资源
      • 状态
        • 执行
        • 阻塞
        • 就绪
      • 线程控制块
        • 寄存器
        • 堆栈
        • 线程运行状态
        • 优先级
        • 线程专有存储器
        • 信号屏蔽
    • 线程和进程关系
      • 一个线程必须有一个父进程
      • 一个进程可以有多个线程
    • 线程间的同步与通信
      • 互斥锁
      • 条件变量
      • 信号量机制
    • 线程的实现方式
      • 内核支持线程
      • 用户级线程
      • 两者结合的办法
      • 用户级线程和内核支持线程比较
        • 线程的调度和切换速度
        • 系统调用
        • 线程执行时间
        • 适应性
    • 线程的实现
      • 内核支持线程
      • 用户级线程
        • 运行在中间系统之上
          • 运行时系统
          • 内核控制线程
        • 可以和内核支持线程相互关联
• 操作系统引论
  • 操作系统目标和作用
    • 作用
    • 目标
    • 主要发展动力
  • 操作系统的发展过程
    • 无操作系统的计算机系统
    • 脱机输入／输出
    • 单道批处理系统
      • 形式
      • 特征
    • 多道批处理系统
      • 形式
      • 特征
      • 优点
    • 分时系统
    • 实时系统
  • 操作系统的基本特征
    • 并发性
    • 共享性
    • 虚拟技术
    • 异步性
  • 操作系统的主要功能
    • 处理机管理功能
    • 存储器管理功能
    • 设备管理功能
    • 文件管理功能
    • 操作系统与用户之间的接口
  • OS结构设计
    • 传统的操作系统结构
      • 无结构操作系统
      • 模块化的操作系统
        • 优点
        • 问题
      • 分层次结构OS
        • 优点
        • 缺点
    • 客户／服务器模式
      • 客户机
      • 服务器
      • 网络系统
    • 面向对象的程序设计
    • 微内核OS结构
      • 微内核
      • 优点
      • 缺点
• 处理机调度与死锁
  • 处理机调度的层次
    • 高级调度
      • 决定后备队列中调入主存的作业
      • 多少作业：取决于多道程序度
      • 接纳哪些作业：取决于调度算法
    • 中级调度
      • 闪存中把暂时不运行的换出外存
      • 决定那些进程被允许参与竞争CPU
      • 处于挂起状态
      • 引入原因
        • 换出
        • 换入
    • 低级调度
      • 就绪队列中分配处理机
      • 进程调度
        • 方式
          • 抢占式
            • 原则
          • 非抢占式
    • 作业状态
      • 提交状态
      • 后备状态
      • 执行状态
      • 完成状态
    • 只有低级调度是必须的
  • 调度队列模型和调度准则
    • 调度队列模型
      • 一级
      • 二级
      • 三级
    • 选择调度方式和调度算法的若干准则
      • 面向系统的准则
        • 系统吞吐量
        • CPU利用率
        • 各类资源的平衡利用
      • 面向用户的准则
        • 周转时间短
        • 相应时间快
        • 截止时间的保证
        • 稳定性
      • 算法的性能准则
        • 易于实现
        • 执行开销比
  • 调度算法
    • 先来先服务和短作业（进程）优先调度算法
    • 最短剩余时间优先调度算法
    • 高优先权优先调度算法
      • 抢占式
      • 非抢占式
      • 优先权
        • 静态优先权
        • 动态优先权
    • 最高相应比优先调度算法
      • 响应比
    • 基于时间片的轮转调度算法
      • 最开始的在队首，执行完时间片到队尾
      • 时间片过大
      • 时间片过小
      • 多级反馈队列调度算法
        • 设置多个队列
        • 优先级越高，执行时间越短
        • 在第一个队列执行完以后再执行第二个队列
        • 执行过的进程放到最后一个队列的末尾
  • 实时调度
    • 实现实时调度的基本条件
      • 提供必要的信息
      • 系统处理能力强
      • 采用抢占式调度机制
      • 具有快速切换机制
    • 实时调度算法的分类
      • 非抢占式调度算法
        • 非抢占式轮状调度算法
        • 非抢占式优先调度算法
      • 抢占式调度算法
        • 基于时钟中断的抢占式优先权调度算法
        • 立即抢占的优先权调度算法
    • 常用的几种实时调度算法
      • 最早截止时间优先
      • 最低松弛度优先
        • 松弛度
        • 抢占式的
  • 产生死锁的原因和必要条件
    • 产生死锁的原因
      • 竞争资源
        • 可剥夺资源与不可剥夺
        • 永久性和临时性
        • 不可剥夺、永久性和临时性资源可造成死锁
      • 进程推进顺序不当
    • 死锁
    • 产生死锁的必要条件
      • 互斥条件
      • 请求和保持条件
      • 不可剥夺条件
      • 环路等待条件
    • 处理死锁的基本方法
      • 预防死锁
        • 预防死锁的方法
          • 互斥？
            • 是设备本身固有的属性
            • 不可修改
          • 请求和保持条件
            • 静态资源分配法
            • 一次分配所用的全部资源
            • 资源利用率低，进程延迟
          • 摒弃“不可剥夺”
            • 已有该资源的进程要求释放资源
            • 只可用于状态可以保存和恢复的资源
          • 摒弃“环路等待”
            • 有序资源分配
            • 资源利用率提高（还是存在浪费）
            • 限制了用户编程
            • 限制了设备的增加
      • 避免死锁
        • 系统安全状态
        • 利用银行家算法避免死锁
          • 1. 通过对资源分配进行分析
          • 2. 如果有任何一个进程的资源需求满足现有资源储备量，则可分配，并释放占用的资源 重复1
          • 如果所有进程可全部被释放，则处于安全状态
      • 检测死锁和解除
        • 死锁的检测
          • 资源分配图
            • 用圆圈代表进程
            • 方框表示一类资源
            • 方框中一个点代表一类资源的一个实例
            • 从进程到资源表示进程请求一个该类资源
            • 从资源指向进程表示有一个资源分配给该进程
          • 检测
            • 不可完全简化即死锁
            • 完全简化即形成孤立结点
            • 可以获取到想要的资源则移除请求边和分配边
        • 死锁的解除
          • 资源剥夺法
          • 撤销进程法
      • 不考虑此问题
• 文件管理
  • 文件和文件系统
    • 文件、记录和数据项
      • 数据项
        • 基本数据项
          • 原子数据
          • 数据组织中可以命名的最小逻辑数据单位
          • 描述对象某种属性的字符集
        • 组合数据项
          • 由若干基本数据项组成
      • 记录
        • 一组相关数据项的集合
        • 描述一个对象在某方面的属性
      • 对象
      • 文件
        • 有结构文件
        • 无结构文件
        • 一个对象集
        • 属性
          • 文件类型
          • 文件长度
          • 文件的物理位置
          • 文件的建立时间
    • 文件类型和文件系统模型
      • 类型
        • 按用途分类
        • 按文件中数据的形式分类
        • 存取控制属性
      • 文件系统模型
        • 对象及其属性
          • 文件
          • 目录
          • 磁盘存储空间
        • 对对象操纵和管理的软件集合
          • 对文件存储空间的管理
          • 对文件目录的管理
          • 用于将文件的逻辑地址转换为物理地址的机制
          • 对文件的读和写的管理
          • 文件的共享与保护
        • 文件系统的接口
          • 命令接口
          • 程序接口
    • 文件操作
      • 创建文件
      • 删除文件
      • 读文件
      • 写文件
      • 截断文件
      • 设置文件的读／写位置
  • 文件的逻辑结构
    • 文件逻辑结构的类型
      • 有结构文件
        • 顺序文件
          • 文件中的记录一个接一个地顺序排列
          • 记录是可以定长或变长的
          • 结构
            • 串结构
              • 记录之间的顺序与关键字无关
            • 顺序结构
              • 文件中的所有记录按关键字顺序排列
        • 索引文件
          • 变长记录文件只能顺序查找
          • 索引表
        • 索引顺序文件
          • 索引顺序文件将顺序文件中的所有记录分为若干个组
          • 在索引表中为每组中的第一个记录建立一个索引项
        • 直接文件或散列文件
          • 给定记录的键值或通过Hash函数转换的键值直接决定记录的物理地址
          • 这种映射结构不同于顺序文件或索引文件，没有顺序的特性
      • 无结构文件
        • 无结构文件将数据按顺序组织成记录并积累保存，它是有序相关信息项的集合，以字节(Byte)为单位
        • 只能以穷举搜索的方式
        • 管理简单
  • 外存分配方式
    • 连续分配
      • 优点
        • 顺序访问容易
        • 顺序访问速度快
      • 缺点
        • 连续的存储空间
        • 事先知道文件的长度
    • 链接分配
      • 隐式链接
        • 一个串联文件结构是按顺序由串联的块组成
        • 文件的信息存储在若干个块之中
        • 最后一个块为链接字，指出后续地址
        • 链首指针存放在文件目录之中
      • 显式链接
        • 是指把用于链接文件各物理块的指针，显示地存放在内存的一张连接表中。该表在整个磁盘就一张。此表就是文件分配表
    • 索引分配
      • 单级索引
      • 多级索引
      • 混合索引
        • 索引结点中可设置10个直接地址项
        • 文件较小的时候可以直接从索引结点中读出该文件的全部盘块号
        • 对于较大的文件，将直接地址项变为间接地址
        • 多次间接地址（开始增加地址项来提供间接地址）
  • 目录管理
    • 文件控制块和索引结点
    • 目录结构
      • 单级目录结构
      • 两级目录结构
      • 多级目录结构
        • 目录结构
        • 路径名
        • 当前目录
        • 增加和删除目录
          • 目录文件不为空时，不可删除
          • 或删除目录文件中所有其他文件
    • 目录查询技术
      • 线性检索法
      • Hash方法
  • 文件存储空间的管理
    • 空闲表法
      • 存储空间的分配与回收
      • 和动态分配类似
    • 空闲链表法
      • 空闲盘块链
      • 空闲盘区链
    • 位示图法
      • 位示图
      • 盘块的分配
        • 令值变成1
      • 盘块的回收
        • 令值变成0
    • 成组链接法
      • 空闲盘块的组织
      • 以栈的形式体现
      • 空闲盘块的分配与回收
        • 执行空闲盘块数加1操作
        • 执行空闲盘块数减1操作
  • 文件共享与文件保护
    • 利用符号链实现文件共享
    • 磁盘容错技术
      • 第一级容错技术SFT-Ⅰ
        • 双份目录和双份文件分配表
          • 备份一份文件目录和文件分配表
        • 热修复重定向和写后读校验
      • 第二级容错技术SFT-Ⅱ
        • 磁盘镜像
        • 磁盘双工
    • 数据一致性控制
      • 事务
        • 定义
        • 记录
        • 恢复
      • 检查点
      • 并发控制
      • 重复数据的数据一致性问题