计算机操作系统

大学计算机，操作系统期末考试知识点。操作系统(Operating System，简称OS)是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。希望对你有帮助!

操作系统

• 进程管理
  • 进程基本概念
    • 进程与程序的区别
      • 1. 程序是代码的集合，静态的。 2. 进程是程序的一次执行，动态的。
    • 进程的特性
      • 1. 动态性（最基本特征）。 2. 并发性。 3. 独立性。 4. 结构性。 5. 异步性。
    • 进程结构
      • 1. PCB。 2. 代码段。 3. 数据段。
    • 进程的五状态
      • 一. 五种状态 1. 创建态：创建PCB，初始化PCB，分配资源，插入就绪队列队尾。 2. 就绪态：获得了除CPU以外的所有资源。 3. 运行态：进程在CPU上运行。 4. 阻塞态：因缺少某一进程而处于等待状态。 5. 终止态：撤销PCB，回收资源。 二. 状态转换 1. 就绪态->运行态：调度 2. 运行态->就绪态：被高优先级进程抢占或时间片完。 3. 运行态->阻塞态：等待某一事件的发生。 4. 阻塞态->就绪态：等待的某一事件发生。 
    • 进程通信
      • 低级通信：PV操作 高级通信：共享存储，消息传递，管道通信。 共享存储：基于数据结构，基于存储区。 消息传递：直接传递，间接传递（信箱模式）。 管道通信：半双工，互斥访问。
  • 线程基本概念
    • 什么是线程？
      • 轻量级进程。
    • 线程的特性与优点
      • 1.引入线程后，进程依旧是资源分配的基本单位，而线程是调度的基本单位。 2.线程间的切换，代价小，提高了并发度。 进程间的切换，代价高，降低了并发度。
    • 线程的实现
      • 用户级线程
        • 1. 线程间管理由应用程序完成，因此线程间的切换代价低，速度快。 2. 然而操作系统无法意识到这种情况下线程的存在，因此当一个线程阻塞的时候，整个进程内的线程都阻塞。降低并发度。
      • 内核级线程
        • 1. 线程间管理由操作系统完成，因此线程间的切换代较高，速度较慢。 2. 操作系统意识到这种情况下线程的存在，因此当一个线程阻塞的时候，并不影响其他整个进程内的线程。提高了并发度。
  • 处理机调度
    • 三级调度
      • 高级调度（作业调度）
        • 频率最低，从磁盘后备队列选择一个作业，创建进程，放入就绪队列队尾。
      • 中级调度（内存调度）
        • 频率在三者之间。将处于就绪态或阻塞态的进程从内存中移出到外存，但 PCB 常驻内存。
        • 进程七状态图
          • 
      • 低级调度（进程调度）
        • 频率最高，就绪态->运行态，CPU的分配。
    • 性能评价指标
    • 调度算法
      • FCFS（先来先服务）
      • SJF（短作业优先）
      • 高响应比优先调度
      • 时间片轮转
      • 优先级调度
      • 多级反馈队列调度
  • 进程同步与互斥
    • 同步与互斥概念
      • 同步
        • 又称直接制约关系：为完成某种任务而建立两个或多个进程，需要在某些位置上协调工作次序而产生制约关系。
      • 互斥
        • 又称间接制约关系：进程互斥指当一个进程访问某临界资源 时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后， 另一个进程才能去访问临界资源。
    • 临界资源的互斥访问
      • 进入区
        • 检查是否可以进入临界区，若可以进入，则应该设置正在访问临界资源的标志。
      • 临界区
        • 访问临界资源的代码。
      • 退出区
        • 解除正在访问临界资源的标志。
      • 剩余区
        • 做后处理。
    • 进程互斥四大原则
      • 空闲让进
      • 忙则等待
      • 有限等待
      • 让权等待
    • 互斥实现方法
      • 软件实现
        • 操作不具备原子性。
        • 单标志法
          • 进程间交替进入临界区，当一个进程不想进入临界区，则另一个进程也进步了临界区。
        • 双标志先检查法
          • 存在两个进程同时进入临界区，违背忙则等待。
        • 双标志后检查法
          • 存在两个进程都进不入临界区，违背空闲让进。
        • Peterson
      • 硬件实现
        • 中断屏蔽方法
          • 利用关中断与开中断命令。这限制了处理机交替执行程序能力。
        • TestAndSet指令
        • Swap指令
    • 信号量机制
      • 为什么引入信号量？
        • 软件/硬件实现方法均无法解决让权等待原则。
      • 记录型信号量
        • 理解记录型信号量不同区间取值的意义： 1. 信号量>0 2. 信号量<=0
      • P,V操作
        • 1. P 操作，先 S.value--，之后执行 block 原语。 2. V 操作，先 S.value++，之后执行 wakeup 原语。
      • 经典例题
        • 生产者-消费者问题
        • 多生产者-消费者问题
        • 吸烟者问题
        • 读者-写者问题
        • 哲学家进餐问题
  • 死锁
    • 基本概念
      • 什么是死锁？
        • 多个进程因争夺资源，导致进程都无法向前推进。
      • 产生原因
        • 系统资源的争夺，进程推进顺序非法。
      • 产生的必要条件
        • 互斥条件
        • 不剥夺条件
        • 保持并请求
        • 循环等待
    • 死锁解决办法
      • 死锁预防
        • 破坏互斥条件（不现实）
        • 破坏不剥夺条件
          • 些不可剥夺资源的进程请求新的进程得不到满足的时候，不许释放已经保持的所有资源，待以后重新申请。
        • 破坏保持并请求
          • 运行前一次申请完所需的全部资源。
        • 破坏循环等待
          • 资源编号，按编号递增顺序请求资源。
      • 死锁避免
        • 安全状态与死锁
          • 安全状态一定不会发生死锁，不安全状态可能发生死锁。（可能期间存在有进程返还系统资源）
        • 银行家算法
      • 死锁检测
        • 数据结构：资源分配图
        • 死锁检测：死锁定理
        • 死锁解除
          • 资源剥夺法
            • 挂起某些死锁进程，并抢夺资源。
          • 进程撤销法
            • 撤销多个或全部死锁进程。
          • 进程回退法
            • 让一个或多个进程回退到足以回避死锁的阶段。
• 内存管理
  • 实现功能
    • 内存的分配与回收
    • 地址转换
    • 内存保护
    • 内存空间扩充
  • 程序编译基本概念
    • 编译
      • 将源代码文件编译成若干目标模块。
    • 链接
      • 通过链接程序将目标模块与其所需的库函数链接，形成完整的装入模块。
      • 静态链接
      • 装入时链接
      • 运行时链接
    • 装入
      • 由装入程序将装入模块装入内存。本质是将逻辑地址转换为物理地址。
      • 绝对装入
        • 编译，链接时需要给出绝对地址。
      • 静态重定位
        • 一次性将装入的所有模块重定位。
      • 动态重定位
        • 在重定位寄存器的支持下，按运行时的进行重定位。
  • 内存保护
    • 可以通过设置重定位寄存器（基址寄存器），和界地址寄存器实现。
  • 内存扩充方法
    • 覆盖技术
      • 前者将用户空间划分为一个固定区和若干覆盖区，需要写程序时提前声明。
    • 交换技术
      • 程序在内存和辅存间对换。
    • 虚拟内存技术
  • 连续分配方式
    • 单一连续分配
      • 内存分为用户区和系统区。无外部碎片，有内部碎片。
    • 固定分区分配
      • 无外部碎片，有内部碎片。
      • 分区大小相等
      • 分区大小不等
    • 动态分区分配
      • 有外部碎片，无内部碎片。
      • 数据结构
        • 空闲分区表
        • 空闲分区链
      • 分配算法
        • 首次适应
          • 空闲分区按地址递增顺序，找到第一个满足的空闲分区。性能最优。
        • 最佳适应
          • 空闲分区按容量递增顺序，找到第一个满足的空闲分区。
        • 最坏适应
          • 空闲分区按容量递减顺序，找到第一个满足的空闲分区。
        • 邻近适应
          • 首次适应加上每次从上次结束位置处开始。
      • 回收算法
  • 非连续分配
    • 基本分页式
      • 基本概念
        • 内存空间划分为大小相等的分区 页（页面）：进程中的块。 页框：内存中的块。 页与页框一一对应。 页表寄存器：存放页表地址信息（页表始址，页表长度）。 页表：记录了由页号->内存块号的映射。
      • 地址结构
        • 地址结构 = （页号，页内偏移量）
      • 页表结构
        • 页号（不实际存储），物理块号。
      • 地址变换
        • 1. 计算页号，页内偏移（十进制通过除取整，求余，二进制根据位数判断）。 2. 页号与页表寄存器内的页表长度比较， 超过则越界中断。 3. 页表项长度 = 页表始址 + 页号 * 页表项长度。 4. 找到页表项，得到物理块号。 5. 物理地址 = 页面大小 * 物理块号 + 页内偏移 
    • 基本分段式
      • 基本概念
        • 以程序的逻辑关系分为若干段，段间非连续存放。段内连续存放。
      • 地址结构
        • 地址结构 = （段号，段内偏移）
      • 段表结构
        • 段号，段始址，段长度。
      • 地址变换
        • 1. 计算段号，段内偏移。 2. 段号与段表寄存器的段表长度比较，超过则发生越界中断。 3. 段表项地址 = 段表始址 + 段号 * 段表项大小。 4. 根据段表得到段始址和段长度。 5. 段内偏移与段长度比较，超过则发生越界中断。 6. 物理地址 = 段表始址 + 段内偏移。 
    • 基本段页式
      • 基本概念
        • 结合二者的优点。
      • 地址结构
        • 地址结构 = （段号，页号，页内偏移）
      • 段/页表结构
        • 段表：段号，页表长度，页表始址。 页表：物理块号。
      • 地址变换
        • 1. 计算段号，页号，页内偏移。 2. 段号与段表寄存器的段表长度比较，超过则越界中断。 3. 段表项地址 = 段表始址 + 段号 * 段表项长度。 4. 访问段表得到页表长度，页表始址。 5. 页号与页表长度比较，超过则越界中断。 6. 页表项地址 = 页表始址 + 页号 * 页面大小。 7. 查询页表得到物理块号。 8. 物理地址 = 物理块号 * 页面大小 + 页内偏移。 
    • 分页式与分段式的比较
      • 信息的单位
        • 分页的基本单位是页，是物理单位。 分段的基本单位是段，是逻辑单位。
      • 大小
        • 页表的大小是固定的，段是不固定的。
      • 可见性
        • 段是由编程时决定，可见。 页时由操作系统决定，不可见。
      • 地址空间
        • 段的地址空间是二维，页的地址空间是一维。
      • 信息共享与保护
        • 段有利于信息共享与保护。页不方便。
    • 快表机制
      • 什么是快表？
        • 在存储器层次结构中，属于高速缓存，访问最近访问的页表项副本。
      • 局部性原理
        • 时间局部性
        • 空间局部性
      • 地址变换
        • 1. 计算页号，页内偏移（十进制通过除取整，求余，二进制根据位数判断）。 2. 页号与页表寄存器内的页表长度比较， 超过则越界中断。 查快表，若命中则直接指导了物理块号。若未命中，则无事发生。 3. 页表项长度 = 页表始址 + 页号 * 页表项长度。 4. 找到页表项，得到物理块号。 5. 物理地址 = 页面大小 * 物理块号 + 页内偏移。 
      • 平均访问时间
        • 快表和慢表同时访问（内存中的页表）
        • 先访问快表，未命中再访问慢表
    • 两/多级页表机制
      • 为什么引入两/多级页表？
        • 如果页表过大（即页表项过多，且页表项连续存放），会占据较大的连续存储空间。因此引入层次概念。
      • 地址结构
        • 以两级页表为例：地址结构 = （一级页号，二级页号，页内偏移量） 
      • 注意事项
        • 1. 页表内加入了一个“是否在内存中”的状态位。 2. 顶级目录只有一个。 3. n 级页表的访问内存次数为 n+1 次。
  • 虚拟存储
    • 虚拟内存特性
      • 多次性
        • 作业允许分成多次调入内存。
      • 对换性
        • 作业无需常驻内存，可以换入换处。
      • 虚拟性
        • 逻辑上扩充内存容量。
    • 请求分页系统
      • 在基本分页管理的基础上，加入了请求调页功能，页面置换。
      • 页表
        • 页表 = （页号，物理块号，状态位，访问字段，修改位，外存地址） 状态位：是否处于内存中。 修改位：是否被修改。（决定是否在调出时，写回内存否？）。 访问字段：算法位。
      • 缺页中断
        • 缺页中断属于内部中断，且一条指令的执行期间可能存在多次缺页中断。
      • 地址变换
        • 1. 比较页号与页表长度，超过则越界中断。 2. 检查快表中是否有该项，没有则访问页表。 3. 如果页表在内存中，则修改访问位和修改位，形成物理地址。 4. 如果页面不再内存，则进行缺页中断。 缺页中断 1. 保护 CPU 现场。 2. 从外存中找到缺页。 3. 若内存中有空闲块则直接放入，若没有则通过页面置换算法选择一个页面调出。 4. 被调出的页面检查修改位，若被修改需要写回到外存。 5. 换入内存后修改页表，回到程序中断处。
    • 请求分段系统
    • 页面置换算法
      • 最佳置换算法（OPT）
      • 先进先出
        • 存在 Belady 异常：增加物理块，命中率降低。
      • LRU
        • 淘汰最近最长时间未使用的页面。
      • CLOCK 算法
    • 页面分配策略
      • 驻留集
        • 请求分页存储管理中给进程分配的物理块集合。
        • 固定分配局部置换
          • 系统为每个进程分配一定数量的物理块，整个运行期间不变。
        • 可变分配全局置换
          • 先为系统中每个进程分配一定数目物理块，操作系统本身维持一个空闲物理块队列。哪个进程发生缺页，就分配一块。无空闲块时，选择未锁定页面换出。
        • 可变分配局部置换
          • 先为系统中每个进程分配一定数目物理块，当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存，若频繁缺页，系统会为该进程多分配物理块。反之会减少分配物理块。
      • 工作集
        • 某段时间间隔内，进程实际访问页面的集合。 注意：驻留集大小不能小于工作集大小。
      • 调入策略
        • 预调页策略（运行前调入）
        • 请求调页策略（运行时调入）
      • 抖动
        • 刚换入的页面马上又被换出，刚换出的页面马上又被换入。
• 设备管理
  • I/O控制方式
    • 程序查询方式
      • CPU 循环测试I/O 状态。
    • 中断驱动方式
      • I/O 每完成一个字的数据放到指定寄存器后，I/O 设备通过中断方式请求服务。
    • DMA 方式
      • 基本单位数据块，DMA 与 内存直接交换数据，仅在预处理与后处理需要 CPU 干预。
    • 通道方式
      • 通道是专用 I/O 处理机，一组数据块，通道比 DMA 可以独立决定数据始址和长度。
  • I/O 子系统
    • 用户I/O软件
    • 设备独立性软件
    • 设备驱动程序
    • 中断处理程序
    • 硬件
  • I/O核心子系统
    • I/O调度
    • 高速缓存缓冲区
      • 单缓冲区
        • max(T1, T3) + T2
      • 双缓冲区
        • max(T1 + T2, T3)
      • 循环缓冲
        • 循环队列。
      • 缓冲池
        • 三个队列：空缓冲队列，输入队列和输出队列。 四个缓冲区：收容输入数据缓冲区，收容输出数据缓冲区，提取输入数据缓冲区，提取输出数据缓冲区。
    • 设备分配与回收
      • 数据结构
        • 设备控制表（DCT） 系统设备表（SDT） I/O 控制器设备表（COCT） I/O 通道控制表（CHCT）
      • 设备分配流程
        • SDT -> DCT -> COCT -> CHCT。
      • 设备分配方式
        • 静态分配
          • 运行前一次分配所有。
        • 动态分配
          • 运行时按需分配。
      • 逻辑设备表（LUT）
        • 逻辑设备与物理设备间的映射关系。
    • SPOOLing 技术
      • 基本组成
        • 输入井，输出井，输入缓冲区，输出缓冲区，输入进程，输出进程。
      • 共享打印机工作流程
        • 输出进程在输出井申请空白磁盘区，将打印数据放进去。 输出进程申请一张空白 PCB，初始化信息后放在打印队列队尾。 打印机从输出井中提取数据。
• 文件管理
  • 文件基本概念
    • 文件的结构
      • 自底向上 记录项：不可分割，最低级的数据组织方式。 记录：一组相关数据项的集合。 文件：一组相关信息的集合。
    • 文件基本操作
      • 创建文件
      • 打开文件
      • 写文件
      • 读文件
      • 文件重定位（文件寻址）
      • 删除文件
      • 关闭文件
    • 文件属性
  • 文件的逻辑结构
    • 无结构文件（流式文件）
    • 有结构文件（记录文件）
      • 顺序文件
        • 链式存储
          • 无法实现随机存取。
        • 顺序存储
          • 可变长记录
            • 无法实现随机存取。
          • 定长记录
            • 可实现随机存取。
            • 串结构（不按关键字顺序存储）
            • 顺序结构（按关键字顺序存储）
      • 索引结构
        • 由于索引表本身就是顺序表，所以即使逻辑文件是可变长的，仍然可以实现随机存取。 
      • 索引顺序结构
        • 为了能有效降低索引表的大小，引入索引顺序结构。索引结构是一个索引项对应一个记录，而索引顺序结构一个索引项对应一组记录。 
        • 多级索引顺序结构
          • 进一步地提高了提高了检索的效率。 
  • 目录结构
    • FCB
      • 文件控制块（FCB）包含了文件基本信息，多个FCB 构成目录。
      • 索引结点
        • 将整个 FCB 放入目录会降低检索效率，因此将 FCB 中除文件名之外的文件描述信息放入索引结点中。目录中只包括文件名，一个指向索引结点的指针。 
    • 单级目录结构
      • 
    • 两级目录结构
      • 
      • 主文件目录
      • 用户文件目录
    • 多级目录结构（树型目录结构）
      • 
      • 绝对路径
      • 相对路径
    • 无环图目录结构
      • 方便共享，每个共享结点设置一个共享计数器。 
  • 文件分配方式
    • 连续分配
      • 1. 支持随机访问。 2. 存取速度最快。 3. 扩展较难。  可以通过紧凑技术来解决碎片问题。
    • 链式分配
      • 隐式链接
        • 除了文件最后一个盘块，每个盘块中都存有指向下一个盘块的指针。
      • 显式链接
        • 链接各物理块的指针显式存放在 FAT 表中。 
    • 索引分配
      • 单独弄出一些盘块存放索引表信息。  存放数据的盘块称：数据块。 存放索引表的盘块称：索引块。
      • 链接方案
        • 
      • 多层索引
        • 
      • 混合索引
        • 
  • 文件存储空间管理
    • 空闲表法
      • 空闲盘块表 = （序号，第一个空闲盘块号，空闲盘块数）
    • 空闲链表法
      • 空闲盘块链
        • 所有空闲盘块以盘块为单位组成一条链。
      • 空闲盘区链
        • 所有空闲盘块以盘区为单位组成一条链。
    • 位示图法
    • 成组链接法
  • 文件共享
    • 硬链接
    • 软链接
  • 文件保护
    • 口令保护
    • 加密保护
    • 访问控制
  • 磁盘管理
    • 磁盘结构
      • 磁盘
      • 磁道
      • 扇区
    • 磁盘地址结构
      • （柱面号，盘面号，扇区号） 磁头指到指定的柱面。 选择特定的盘面激活磁头。 磁盘旋转划过指定扇区。 这么设计：因为盘面号不同不需要移动磁头臂。
    • 磁盘调度
      • 磁盘访问时间
        • 寻道时间
          • 寻道时间 = 启动磁臂时间 + 移动一个磁道的单位时间 * 移动磁道数
        • 旋转时延
          • 磁头定位到指定扇区的平均时间（转半圈） = 1 / (2 * 磁盘转速)
        • 数据传输时延
          • 划过指定扇区。
      • 磁盘调度算法
        • 改善寻道时间。
        • 先来先服务（FCFS）
        • 最短寻找时间（SSTF）
          • 优先处理与当前磁头最近的磁道。
        • 扫描算法（SCAN）
          • 移动到最外侧磁道时才能往内移动，移动到最内侧磁道时才能往外移动。
          • LOOK 算法
            • 在 SCAN 基础上，若磁头移动方向上无别的请求，可以立即改变磁头移动方向。
          • C-SCAN 算法
            • 只有沿特定方向移动才处理磁道访问请求，返回时直接快速移动至起始端不处理任何请求。
          • C-LOOK 算法
            • 相比于 C-SCAN，若移动方向上无请求，则直接快速返回起始端。
    • 其他减少时延方法
      • 交替编号
        • 针对单个盘面。
      • 错位命名
        • 针对多个盘面。
    • 磁盘初始化
      • 物理格式化
        • 将磁道划分为扇区，初始化管理扇区的控制信息。
      • 磁盘分区
      • 逻辑格式化
        • 创建文件系统。
    • 磁盘引导区
    • 坏块管理
      • 解决方法：提供备用扇区
      • FAT 标明
      • 维护坏块链表
• 操作系统基本概念
  • 功能
    • 控制和管理计算机系统硬件与软件资源，为用户和其他软件提供方便接口与环境的程序集合，计算机系统中最基本的系统软件。
  • 特征
    • 并发
      • 并发：两个或多个事件在同一时间段内发生。 并行：两个或多个事件在同一时刻发生。
    • 共享
    • 虚拟
    • 异步
  • 接口
    • 命令接口
      • 交互式命令接口
      • 批处理命令接口
    • 程序接口
      • 系统调用（广义指令）
    • 图形接口（GUI）
  • 发展
    • 多道批处理系统：提高系统利用率，但缺乏人机交互。 分时操作系统：提供人机交互，但时间片切换存在系统开销。 实时操作系统：追求及时性与可靠性。
    • 批处理
      • 单道批处理
      • 多道批处理
    • 分时系统
    • 实时系统
    • 网络操作系统
    • 分布式计算机系统
  • 运转机制
    • 用户态 & 内核态
    • 特权指令 & 非特权指令
    • 用户态与内核态间的切换
      • 用户态->内核态
        • 中断。 一方面是主动的中断：系统调用。 一方面是被动的中断：系统强行转为内核态。
      • 内核态->用户态
        • 操作系统主动的过程。
    • 中断
      • 内中断（异常）
        • 陷入
          • 程序自愿的行为。
        • 故障
        • 终止
      • 外中断（中断）
  • 体系架构
    • 大内核
      • 时钟管理，中断管理，原语。
    • 微内核
      • 微内核 + 进程管理，内存管理，设备管理。
    • 大内核与微内核差异比较
      • 大内核：一次申请系统服务所需要的状态转换次数较少，性能较优。 微内核：一次申请系统服务所需要的转台转换次数较多，性能较差。 但微内核管理较大内核要好点。