操作系统

计算机操作系统面试考点，大厂面试必备，涉及进程管理、内存管理、IO（文件） 管理三大核心内容，知识点全面。

操作系统

• 进程管理
  • 进程
    • 程序的集合
    • 资源分配的最小单位
    • 进程之间不可见、虚拟化
    • 创建、就绪、堵塞、执行、终止
  • 线程
    • 进程的更细的抽象
    • CPU 调度的最小单位
    • 线程之间互相影响
    • 创建、就绪、堵塞、执行、终止
  • 协程
    • 更轻量级、线程的抽象
    • 在用户态执行
  • 用户态与核心态
    • 陷阱调用、异常、中断
  • 死锁产生
    • 互斥、请求与保持、不可抢占、循环等待
    • 银行家算法
  • 进程间切换
    • 陷入内核态、保存当前进程的硬件上下文
    • 修改当前进程 PCB 信息为等待，加入内核队列
    • 调度另外一个进程
    • 修改调度进程 PCB 为运行
    • 装载调度进程的存储管理信息，如页表、快表等
    • 从队列中取出 PCB 信息，恢复上下文，修改 PC 指向
  • 进程间通信
    • 共享内存
      • 磁盘文件映射到内存，进程虚拟空间映射到内存
      • shm 函数 和 mmap 函数区别
    • 信号量
      • 作为共享内存的保护机制
      • 计数器
      • sem 函数
    • 管道
      • 匿名管道
        • 亲子间调用、fork函数(写时复制)、Shell 进程的子进程
        • 半双工、堵塞传递、简单但效率低
        • 读空时堵塞或返回、写满时堵塞或中止
      • 有名管道 FIFP
    • 消息队列
      • 双向通信、非堵塞通信、克服了消息体无格式的缺陷
      • 消息有长度上限、需要多一次拷贝、生命周期随内核
    • 信号
      • 异常时调用
      • 异步通知、软件层次上对中断的模拟
      • 严格的生命周期，创建、存储、发送、处理
    • 套接字 Socket
      • 客户端：connect、read、wirte、close
      • 服务端：bind、listen、accpet.....
  • 线程间同步
    • 互斥锁
      • TAS
      • CAS
    • POSIX 信号量
    • 条件变量
      • 一组等待唤醒的逻辑 — wait & singal
      • 条件变量与互斥量一起使用时，允许线程以无竞争的方式等待特定的条件发生
  • 进程调度算法
    • 周转时间 = 任务完成时间 - 任务到达时间
    • 响应时间
    • 先来先服务（FIFO）
      • 公平的策略
      • 如果长作业在前，那么短作业需要等待很长时间
      • 周转时间、响应时间都很糟糕
    • 最短作业优先（SJF）
      • 不公平的策略
      • 周转时间优秀、长作业优先级最低
      • 如果长作业最先到来，短作业后到，回到 FIFO
    • 最短完成时间优先（STCF）
      • SJF 的改良版
      • 抢占式调度任务，短作业可抢占运行
      • 长作业可能被饿死，永远得不到执行
    • 时间片轮转
      • 公平的策略
      • 响应时间非常优秀
    • 最高优先级（HPF）
      • 基于进程优先级调度
      • 可能饿死低优先级的进程
    • 多级反馈队列（MLFQ）
      • 观察工作的运行状况改变优先级，稳定
      • 规则1：优先运行在最高优先级队列中的进程
      • 规则2：每个优先级中单个进程都有运行时间限制， 超过后进程必须降低优先级
      • 规则3：同一个优先级内采用时间片轮转方式调度
      • 规则4：新创建的进程被防止最高的优先级中
      • 规则5：经过一段时间后，将所有进程重新放到最高优先级中
• 内存管理
  • 高速缓存
    • 直接映射高速缓存
      • 标记 + 组索引 + 块内偏移
      • 每个组只有一行
      • 不命中时需要替换一行
    • 组相连高速缓存
      • 直接映射高速缓存的升级版，一个组有多行
    • 全相连高速缓存
      • 标记 + 块内偏移
      • 只有一个组
  • 分段
    • 动态重定位、支持稀疏的地址空间、代码共享、利于存放逻辑
    • 过多的外部碎片、不足以支持更一般化的稀疏地址空间
    • 段表存放物理基址、虚拟地址被拆分成 段号 + 段内偏移
  • 分页
    • 不会产生外部碎片、支持稀疏的虚拟地址空间、便于操作系统管理
    • 页表过大、内存浪费
    • 段表存放在段寄存器中，通过段号映射内存的 GDT 读取信息。但页表非常大，存放在物理内存中，转换时需要一次额外的内存访问，性能很低
    • 地址转换类似与段，通过 页表号(VPN) + 页内偏移(VPO) 翻译
  • 加速分页地址转换 — TLB
    • 高速缓存的一种，一般是全相联高速缓存，缓存 FPO
    • 未命中时抛出异常，陷入系统调用，从页表中读取，让后重试指令
    • 可以添加地址标识符指示 TLB 所属的进程，利于进程上下文切换
  • 段页式管理
    • 对程序分段，对逻辑段分页，结合分段与分页的优点
    • 段表存放对于段的页表地址，虚拟地址分为：段号 + VPN + VPO
    • 分段不足以支持更一般化的稀疏地址空间，如果有一个大而稀疏的堆，仍然需要装载一整个段，依然会造成页表过大等原因
  • 多级页表
    • 虚拟地址分为 VPN1 + VPN2 + VPN3 + ... + VPO
    • 最后一个页表存储实际的 VPO，而其余页表存储下一级页表地址
    • 如果某个页表有效位设置为 0，则不必将下一级页表加载进来，大大减少内存
  • 页面置换算法
    • 物理内存无法存放所有的页
    • 局部分配、全局分配、内存颠簸
    • 最优替换策略（OPT）
      • 淘汰最晚使用的页面
    • 先进先出策略（FIFO）
      • 淘汰最先使用的页面
    • 第二次机会（SC）
      • NRU 思想
      • 分配 R 位，淘汰时如果最近使用，则重新加入表尾
    • 最近未使用算法（NRU）
      • 每隔一段时间清除 R 位
      • 淘汰 R = 0 的页面，即未使用
      • 若有多个页面，优先淘汰干净页面
    • 时钟算法
      • NRU 思想
      • “最近”定义为时钟的一圈，软件实现的时钟周期
    • 最近最少使用算法（LRU）
      • 双端链表 + 哈希，每次都要移动链表，性能无法接受
      • 可以用时间戳模拟，用硬件加速这个过程
      • 不可靠的时钟
    • 最不常使用算法（NFU）
      • 维护一个计数器，记录页面使用情况
      • 淘汰最少使用的
      • 从不忘记任何事情，这样不好
    • 老化算法
      • NFU 的改良，让 NFU 忘记一些事情
      • 让计数器的值周期性的减小，可以右移一位（忘记之前的事情）
      • 让 R 位加到计数器的最左边的一位
      • 计数器位数固定，这是一个限制
    • 基于工作集的算法
      • 制定一个工作集，例如 T ms 之内访问过的页面
      • 淘汰未访问、且不在工作集内的页面
      • 如果都在工作集内，则淘汰时间戳最小的那个
      • 工作集的定义可以是不同的、与 LRU 相比工作集算法不在乎频率
  • 空闲空间管理
    • 放置策略
      • 最优匹配
      • 最差匹配
      • 首次匹配
      • 下次匹配
    • 空闲空间链表
      • 隐式空闲链表
      • 显示空闲链表
        • 空闲空间的双向链表
    • 分离空闲链表
    • 伙伴系统
      • 合并和分离非常高效
      • 就像 HashMap 一样，能够快速确定最近的 2 的幂
• IO 管理
  • IO 设备
    • IO 轮询与中断
      • 硬件完成操作后，抛出中断
      • 陷入 ISR 中断处理程序，恢复进程运行
      • 中断并非万用，轮询与中断混合搭配
    • 直接内存处理器 DMA
      • CPU 让出总线，仅可执行内部操作
  • 磁盘驱动器
    • 组成
      • 磁头
      • 扇区 512字节
      • 磁道
      • 缓存
    • IO 时间 = 寻道时间 + 旋转时间 + 传输时间
      • 顺序读取快得多
    • 磁盘调度
      • 最短寻道优先
      • 电梯思想
      • 最短定位时间优先 SPTF
  • 磁盘阵列 RAID
    • 通过数组的方式操作磁盘，将扇区封装成磁盘块
    • RAID 0级
      • 磁盘块条带化，可以并行访问磁盘块
      • 块0,1,2,3分离放置在磁盘0,1,2,3中，作为一个条带，块4,5,6,7分离放置在磁盘0,1,2,3中，作为另一个条带......
      • 理论上吞吐量可以达到原来的 N 倍
    • RAID 1级
      • 使用一半的磁盘作为备份
      • 读取与写入带宽是 0 级的一半，磁盘空间利用率只有 50%，但可靠性增加
    • RAID 4级
      • 条带中最后一个磁盘作为奇偶校验磁盘，存储条带中其他磁盘的异或结果
      • 如果只有一个磁盘损坏，可以根据异或结果复原，具有一定的可靠性
      • 空间利用率为 (N-1)/N，读取性能也非常优秀
      • 任何写入都要维护奇偶结果，必须序列化读取奇偶校验磁盘，因此写入是序列化的
    • RAID 5级
      • RAID4 的代替
      • 奇偶校验结果不在集中放置在一个磁盘内
  • 文件
    • 文件拥有一个 index node 和 一个可读的中文名
    • inode 中存放了文件的各自元数据
      • inode 编号，此编号作为 文件 的低级名称，通过此 编号可计算出 inode 内存位置
      • 文件类型、文件大小、文件权限、文件指针等
    • 目录是特殊的文件，目录中存放文件低级名和文件可读中文名的映射
    • 硬链接与软链接
      • 硬链接链接到同一个 inode，维护引用计数
        • ln 命令
      • 软链接创建新 inode，文件内容为链接文件地址
        • ln -s 命令
  • 文件描述符
    • 文件描述符存在于每个进程的 page _ table 中，不含亲子关系间的进程描述符不同
    • 每一个描述符(一个数字)特殊的标识了文件的信息
      • 文件名
      • 文件类型
      • 文件权限
      • 指向文件的指针（可偏移, lseek 函数）等
    • 有三个标准描述符被打开：0 标准输入、1 标准输出、2 标准错误
    • fork 函数会复制父进程的文件描述符
    • 读写缓冲区，fsync() 函数
  • 文件系统
    • 文件系统是在存储设备上组织文件的方法与存储文件、目录及元数据的数据结构
    • 磁盘是基于扇区读写，而文件系统是基于数据块的，并且由一个超级块开头
      • 如果磁盘未能读写完整个数据块（多个扇区）， 则文件系统认为读写失败
    • 管理 inode
      • inode 区基址已知，inode 大小固定，一旦知道 inode 编号就能得知 inode 内存区域
      • 通过位图查询空闲区域
    • 定位文件数据块
      • inode 存放指向第一个文件块的指针以及文件大小
      • 文件块存放指向下一个文件的指针, inode 存放指向第一个文件块的指针
        • 必须遍历链表，性能低
      • inode 中存放指针列表，指向所有文件块
        • 指针列表长度固定，文件块过多时无能为力
      • 多级索引
    • 分配空闲数据块
      • 空闲空间链表
      • 位图法
    • 目录存储
      • 任何文件都要从根目录递归搜索太慢了（根目录位置已知）
      • 用哈希加速搜索，读取目录哈希到内存中
    • 局部性的利用
      • 随机分配数据块无法在磁盘上顺序读取
      • 将磁盘分组，每个组都是抽象的文件系统
        • 相关的东西放在一个组，同组内可以良好的利用磁盘顺序读取
        • 同一个文件数据位于同一个组（大文件例外）
        • 文件同 inode 位于同一个组
        • 同一个目录下的文件位于同一个组
        • 目录需要额外表示 inode 属于哪个组
        • ext2 的做法
    • 崩溃一致性
      • 写文件、更新 inode 时可能会突然崩溃
        • 例如创建了 inode 但没创建文件
      • 预写日志