画布 1
操作系统
  导论
    操作系统是管理计算机硬件的软件
    操作系统的功能
      用户视角
        方便用户使用
      系统视角
        资源分配器
    计算机系统的组成
      计算机系统的运行
        一（多）个CPU和若干设备控制器，使用公共总线连接
        开机启动固件上的引导程序（加载并执行OS）
        事件发生通过中断通知
      存储结构
      IO结构
    计算机系统的体系结构
      单处理器
      多处理器
        非对称处理
          主从关系
        对称处理
          独立完成任务
      集群系统
        由多个独立的系统组成
        非对称集群
          热备份模式
        对称集群
    操作系统的结构
      手工操作阶段
        无操作系统
      单道批处理系统
        磁带上的各道作业顺序进入内存
        内存中始终保持一道作业
        在发出IO请求后，CPU等待IO完成
      多道程序设计
        提高CPU利用率
        多个程序同时进入内存，并交替运行
        发出IO请求后，CPU切换作业继续运行
      分时系统
        提高进程切换频率
        允许用户与进程交互
        多个用户通过终端同时共享一台主机
      实时系统
        硬实时
          某个动作绝对地在规定时刻发生
          飞行器自动控制系统
        软实时
          接受偶尔违反时间规定且不会引起永久性的损害
          飞机订票、银行管理
    操作系统的执行
      中断驱动
        硬件利用总线传递中断信号📶
        软件执行系统调用
      双重模式
        用户模式
        内核模式
        模式位（硬件）
          内核模式：0、用户模式：1
        特权指令
          可能引起损害的机器指令
          硬件只有在内核模式下才允许执行特权指令
          切换模式指令即为特权指令
          访管指令不是特权指令
      定时器⏲️
        OS维持对CPU的控制
  操作系统结构
    操作系统的服务
      用户界面
        命令行界面CLI
          命令解释程序shell
            shell本身包含代码执行命令
            通过系统程序实现命令，找到命令的文件
        图形用户界面GUI
      程序执行
      IO操作
      文件系统操作
      通信
      错误检测
      资源分配
      记账🧾
        记录用户使用资源的类型和数量
      保护与安全
      用户
      系统
    系统调用
      系统调用接口
      向操作系统传递参数
        寄存器
        寄存器存储内存地址（间接索引）
        堆栈
      类型
        进程控制
        文件管理
        设备管理
        信息维护
        通信
          消息传递
          共享内存
            系统调用只需分配内存即可
    系统程序
      为程序开发和执行提供一个方便的环境
      文件管理
      状态信息
      文件修改
      程序语言支持
      程序加载与执行
      通信
      后台服务
    操作系统结构
      分层
      微内核
        提供最小的进程与内存管理以及通信功能
          删除不必要的部件
          保证内核可靠性
        通信：消息传递
        状态切换频繁
      模块
        可加载模块
        内核提供核心服务，其他服务在内核运行时动态实现
      混合系统
    系统引导
      引导程序
        定位内核，并加载到内存开始执行
        从磁盘调入更复杂的引导程序，后者再加载内核
        存储在固件上ROM、EPROM
  进程管理
    进程
      进程是执行的程序（活动实体）
        文本段
        程序计数器
        堆栈
          临时数据、返回地址、局部变量
          向下生长
        数据段
          全局变量
        堆
          程序运行时动态分配的内存
          向上生长
      进程状态
        new
          进程正在创建
        running
          指令正在执行
        waiting
          进程等待发生某个事件（IO完成或信号）
        ready
          进程等待分配处理器
        terminated
          进程完成执行
      进程控制块PCB
        进程状态
        程序计数器
        CPU寄存器
        CPU调度信息
        内存管理信息
        记账信息
        IO状态信息
      线程
        每个线程是CPU使用的一个基本单元
          与同进程的其他线共享代码段、数据段、其他操作系统资源
          拥有独立的线程ID、程序计数器、寄存器组、堆栈
        多线程模式
          多对一模型
            一个线程执行阻塞系统调用，整个进程就会阻塞
          一对一模型
            每个用户线程映射到一个内核线程
            linux、windos
          多对多模型
            多路复用（双层模型）
        线程库
          在用户空间提供没有内核支持的库
          实现操作系统直接支持的内核级的库
    进程调度
      调度队列
        作业队列
          系统内的所有进程
          进程进入系统即加入
        就绪队列
          驻留在内存、就绪的、等待运行的进程
          链表实现
            头节点两个指针：指向首尾PCB
            每个PCB指向下一个PCB
        设备队列
          等待特定IO设备的进程列表
      调度程序
        长期调度（作业调度）
          从作业池（磁盘）中选择进程，加载到内存
        中期调度
          将进程从内存中移出，降低多道程序程度
          换入换出
        短期调度（CPU调度）
          从就绪队列选择进程并分配CPU
            抢占调度
              就绪队列中的进程可以强制正在占用CPU的进程释放CPU资源
            调度延迟
              调度程序停止一个进程启动另一个进程
                切换上下文
                切换到用户模式
                跳转到用户程序合适的位置，以便重新启动程序
                  进程中的程序计数器
            调度准则
              CPU使用率
              吞吐量
                一个时间单位进程完成的数量
              周转时间
                等待进入内存+就绪队列等待+CPU执行+IO执行
              等待时间
                就绪队列等待时间⌛️
              响应时间
                从提交请求到第一次响应
        调度算法
          FCFS
            通过FIFO队列实现
              一个进程进入就绪队列，它的PCB被链接到队列尾部
          SJF
            最短作业优先调度（非抢占式）
              选择下次CPU执行长度最短的进程
              近似SJF调度
                指数平均（使用以前的CPU长度来预测）
            最短剩余时间优先（SRTF）
              抢占式SJF
          优先级调度
            最高优先级的进程分配到CPU
            造成极饿
              老化
                增加等待时间长的进程的优先级
          轮转调度RR
            将一个较小的时间单元定义为时间片
            FIFO队列
              新进程加到就绪队列尾部
              当前进程运行时间大于时间片，定时器中断，将该进程加到就绪队列尾部
          多级队列调度
            前台进程（交互进程）
            后台进程（批处理进程）
            多级队列
              进程不可调整队列
              将就绪队列根据进程属性分为多个单独队列
                每个队列调度算法可以不同
                队列间调度
                  优先级
                  分配一定比例的时间
            多级反馈队列
              允许进程在队列间移动
              根据不同的CPU执行特点区分进程
                CPU密集型优先级低
                IO密集型、交互进程优先级高
                较低优先级等待时间长的进程可移动到高优先级
          Gantt图
      切换上下文
        中断发生时需要保存运行在CPU上的进程上下文
        切换CPU到另一个需要保存当前进程状态以及恢复另一个进程的状态
        硬件支持
    进程运行
      进程表示符pid
      进程创建新进程时
        父进程与子进程并发执行
        父进程等待某个或者全部子进程运行完
          父进程使用wait（）将自己移出就绪队列，到等待状态，等待子进程结束
      新进程地址空间
        子进程与父进程有相同的程序与数据
        子进程加载另一个新进程
      进程系统调用
        fork（）
          父进程返回子进程pid（非0）
          子进程返回0
        exec（）
          加载二进制文件到内存中，并开始执行
        exit（）
          请求操作系统删除自身，进程终止
          进程资源由操作系统释放
          父进程通过系统调用终止子进程
            子进程使用超过它所分配到的资源
            不再需要子进程分配的任务
            父进程正在退出，操作系统不允许无父进程的子进程继续执行
        僵尸进程🧟‍♀️
          进程终止但父进程尚未调用wait（）
        孤儿进程
          父进程没有调用wait（）就退出
      进程间通信
        消息传递
          使用原语
            直接通信
              在两个链路间建立一条链路（只有一条）
            间接通信
              需要共享一个邮箱📪
            同步通信
              阻塞发送、接受
            异步通信
              非阻塞发送、接受
            自动缓冲
              通信消息的队列有一定长度或无限长度
            显式缓冲
              队列长度为0，链路中不能有任何消息处于等待
                发送方应阻塞，知道接收方接受该消息
            发送接受都阻塞时，发送方与接收方会产生一个交汇（rendezvous）
        共享内存
          生产者-消费者问题
            有界缓存
            无界缓存♾️
  存储管理
    文件系统
      文件：操作系统对存储设备的物理属性的抽象
        打开文件的关联信息
          文件指针
          文件打开次数
          文件在磁盘位置
          访问权限
          文件锁（可选）
          文件控制块FCB
        磁盘中文件系统信息
          （每个卷的）引导控制块
            从该卷引导操作系统的所需的信息
          （每个卷的）卷控制块
            卷的详细信息
              分区的块数
              块的大小
              空闲块数和指针
              空闲FCB数和指针
          （每个文件系统的）目录结构用于组织文件
          每个文件的FCB
        内存中文件系统信息
          安装表
            包括每个安装卷的信息
          目录结构的缓存含有最近访问目录的信息
          整个系统的打开文件表
            每个打开文件的FCB副本以及其他信息
          每个进程的打开文件表
          缓冲区保存文件系统的块
        内存和磁盘间的IO传输以块为单位执行
      文件的操作
        创建文件
        写文件
        读文件
        重定位文件
        删除文件
        截断文件
        操作系统使用打开文件表维护所有打开文件信息
      访问方法
        顺序访问
          文件信息按顺序处理
          也可以随机访问设备
        直接访问
          文件由固定长度的逻辑记录组成，以允许程序按照任意顺序读写
          相对块号：由用户向OS提供，允许OS分配文件位置
        索引访问
      目录
        一个磁盘可划分为多个分区，每个分区可以有单独的文件系统（包含文件系统的分区为卷）
          这些文件系统安装到一个逻辑文件系统架构上
        目录种类
          单级目录
          两级目录
            用户文件目录UFD
            主文件目录MFD
          树形目录
            两级目录的推广
              绝对路径名
              相对路径名
              允许用户创建子目录
            删除目录
          无环图目录
            共享文件
              连接🔗
                另一文件或子目录的指针（绝对路径或相对路径名称）
              在两个共享目录中复制有关他们的信息
          通用图目录
            需要垃圾回收机制
        实现方法
          线性列表
            使用文件名称以及数据块的指针
              查询文件需要线性搜索
          哈希表
            哈希数据结构
              溢出链接
      文件系统结构
        IO控制层
          在主存与磁盘系统间传输信息
          设备驱动程序、中断处理程序
            设备驱动程序将高级命令翻译为底层与硬件关联的指令，使IO设备与系统其它部分相连
        基本文件系统
          向适当设备驱动程序发送通用命令
            读写磁盘的物理快
          缓冲管理器
        文件组织层
          将逻辑地址转换为物理地址
          可用空间管理器
        逻辑文件系统
          管理元数据信息
            元数据包括文件系统的所有结构
          管理目录结构
          通过文件控制块维护文件结构
      虚拟文件系统
        将文件系统的通用操作和现实分开
        唯一地表示网络上的一个文件
      分配方法
        为文件在磁盘上分配空间
          连续分配
            要求每个文件在磁盘上占有一组连续的块
            目录条目中记录起始块地址和该文件所分配区域的长度
            支持顺序访问与直接访问
            有外部碎片
              需要停机合并空闲空间
          链接分配
            只需在目录中增加一个新的条目，含有文件首个磁盘块的一个指针（初始化为null）
            只能顺序访问文件
            将多个块组成为簇，按簇分配
              增加内部碎片🧩
            文件分配表FAT
              每个磁盘块都有一个条目，可按块号索引
          索引分配
            将所有指针放在索引块中
              创建文件时，索引块内所有指针都设为null
            拓展技术
              链接方案
                索引块的最后一块地址
                  nu l l
                    小文件
                  另一个索引块的指针
                    大文件
              多级索引
                第一级索引指向一组第二级索引块
              组合方案（UNIX标准）
                索引块前12个指向直接块（数据区）
                剩下三个指针
                  第一个：一级间接块
                  第二个：二级间接块
                  第三个：三级间接块
      空闲空间管理
        位向量
          支持硬件实现
          需要保存在内存，占空间
        链表
          将所有空闲磁盘块用链表链接起来
        组
          n个空闲块
        计数
        空间图
    大容量存储系统
      磁盘
        逻辑块是最小的传输单位
          将逻辑块号转换为磁盘内柱面号、柱面内磁道号、磁道内扇区号
          低级格式化改变逻辑块大小
        磁盘调度
          FCFS调度
          SSTF调度
            处理距离当前磁头位置最短寻道时间的请求
            导致极饿
          SCAN调度
            磁臂从一端开始，向另一端移动；每移过柱面，处理请求。到达另一端后，磁头反向移动继续处理请求。
          C—SCAN调度
            磁臂从一端开始，向另一端移动；每移过柱面，处理请求。到达另一端后，磁头立即返回磁盘开始，不会处理请求
          LOOK调度、C—LOOK调度
            磁臂只移动到一个方向的最远请求为止
          此处的调度只改善寻道时间，不会影响旋转延迟
        磁盘管理
          磁盘格式化
            低级格式化
              对磁盘分扇区
              使用特殊数据结构填充磁盘
            逻辑格式化
              将初始的文件系统数据结构存储在磁盘上
          引导块
          坏块
            扇区备用
            扇区滑动
        交换空间管理
          为虚拟内存提供最佳的吞吐量
          位置
            普通文件
              寻址效率低
            单独的原始分区
        磁盘冗余阵列RAID
          通过冗余提高可靠性
          通过并行处理提高性能
    IO系统
      总线、设备控制器、设备
  内存管理
    内存管理策略
      背景
        基本硬件
          CPU可以直接访问的只有内存与寄存器
          机器指令只能以内存地址为参数
          高速缓存cache
          确定进程访问的合法地址范围
            基地址寄存器
              最小的合法物理内存
            界限寄存器
              范围大小
            通过CPU硬件在用户模式下产生的地址与寄存器地址比较完成
            操作系统通过特权指令加载
        物理地址
          内存单元中的地址
        内存管理单元MMU
          完成从逻辑地址到物理地址到映射
        逻辑地址
          CPU生成的地址
        地址绑定
          编译时绑定：绝对代码
          加载时绑定：可重定位代码
          执行时绑定（需要特殊硬件）
            进程在执行时从一个内存段移至另一个内存段
      交换
        进程暂时从内存交换到备份存储
        标准交换
          正常情况下禁止交换
            空闲内存过低，启动交换
              空闲内存增加，停止交换
          交换进程的一部分
        降低多道程序的度
      内存分配方案
        驻留操作系统
          操作系统在内存中的位置由中断向量确定
          伙伴系统
            从物理连续的大小固定的段上分配
            2的幂分配器，所分配的大小为2的幂次
          slab分配
            每个slab由一个或多个物理连续的页面组成
        用户进程
          连续内存分配
            可变分区
              操作系统维护一个表，记录哪些内存可用，哪些内存已用
                孔：一大块可用内存
                操作系统为新进程找到合适的孔
                  孔太大分为两部分
                    一块分给进程
                    另一块归还给孔集合
                  没有合适的孔
                    等待有足够大的空间
                    寻找内存需求更小的进程
                进程终止
                  释放内存
                  如果新孔和其他孔相邻则合并为大孔
              动态分配问题
                首次适应
                  分配首个足够大的孔
                    从头查找
                    从上次首次适应结束处查找
                最优适应
                  分配最小的足够大的孔
                最差适应
                  分配最大足够大的孔
                查找整个列表，除非列表按大小排序
              碎片🧩
                外部碎片
                  首次适应、最优适应
                  总的可用内存只和可以满足要求但并不连续
                  解决办法
                    紧缩
                      移动内存内容，将所有空闲内存合并为一整块
                      只有重定位是动态的且在运行时进行才可使用
                    允许进程逻辑空间不连续
                内部碎片
                  进程分配的内存可能比所需的要大
            不可变分区
          分段
            逻辑地址空间为一组不同长度的段
              地址指定段名称、段内偏移 <段号，偏移>
            分段硬件
              段表
                每个条目都有段基地址、段界限
            存在外部碎片
          分页
            概念
              帧（页帧）
                物理内存分为固定大小的块
              页（页面）
                逻辑内存分为相同大小的块
            逻辑地址分为页码、页内偏移
              页码为页表的索引
              页大小确定了逻辑地址低位偏移字段的长度
            分页硬件
              页表
                每页所在的物理内存的基地址
                硬件
                  一组专用的寄存器
                  页表基地址寄存器
                  转换表缓冲区TLB
                    由键（标签🏷️）和值组成
                    命中率hit ratio
                      有效内存访问时间
                      如果TLB miss则要访问内存
                页表结构
                  分层分页（向前映射页表）
                  哈希页表
                    大于32位地址空间
                    每个条目都包括一个链表（解决冲突）
                      链表每个元素由虚拟页码、映射页码、指向一个元素的指针组成
                      根据虚拟页码找到链表，沿着链表寻找映射页码
                    聚簇页表
                      每个条目饮用多个页
                  倒置页表
                    每个条目保存真正内存位置上的页的虚拟内存页或帧、该页进程的信息
                    每个物理内存的页只有一条对应的条目
              页表长度寄存器PTLR
                表示页表大小
            帧表
              操作系统维护
                每个条目对应一帧
                  表示该帧是否空闲或是被哪个进程占用
            保护
              保护位
                定义权限
                  可读、可写
              有效-无效位
                有效
                  相关页在进程逻辑空间
                无效
                  相关页不在进程逻辑空间
            共享页
              可重入代码
              纯代码
            存在内部碎片
    虚拟内存管理
      请求调页
        只在需要时加载页面📃
        调页程序只涉及进程的页面
        缺页错误（中断请求）
          检查进程内部表确定该引用的内存访问是否有效
          引用无效，终止进程
          引用有效，调入页面
            找到一个空闲帧或是牺牲一个帧
            调度一个磁盘操作，将所需页面读到刚分配的帧
            磁盘读取完成，修改进程内部表，页表
            重启被陷阱🪤中断的指令
              此时进程可以访问所需页面
        性能
          有效访问时间
      写时复制
        允许父进程与子进程最初共享相同的页面来工作
          共享页面被标记为写时复制
          任何进程写入共享页面，就创建共享页面的副本
        页面池
          供副本使用
          分配前按需填零
      页面置换
        需要换出帧写入磁盘、换入帧写进内存
          修改位
            页面内任何字节被写入，设置修改位
            换出帧修改位未设置或是只读页，不用写入磁盘
        页面置换算法
          选择要置换的帧
          FIFO页面置换
            Belady异常
          最优页面置换OPT、MIN
            置换最长时间不会使用的页面
            主要用于比较研究
          LRU页面置换
            置换最长时间没有使用的页
              硬件支持
                计数器
                  记录📝页面最后引用时间
                堆栈
                  将引用的页移至栈顶，置换栈尾
                  大量指针操作
            难以实现
          近似LRU页面置换
            额外引用位算法
              使用n位引用位表示n个时间周期内的使用情况
            第二次机会算法（时钟算法⏰）
              引用位：1位
              循环队列
                指针向前移动找到引用位为0的页面，置换该页
            增强型第二次机会算法
              使用（引用位，修改位）
                （0，0）最近没有使用且未修改的页面
                  最佳置换
                （0，1）最近没有使用但修改过的页面
                  需要将页面写出
                （1，0）最近使用但未修改过的页main
                  可能会再次使用
                （1，1）最近使用且修改过
                  可能会再次使用且需要写出
              可能需要多次扫描循环队列，才能找到置换页
          基于计数的页面置换
            每个页面保存一个计数器记录引用次数
              LFU（最不经常使用）
                置换具有最小计数的页面
              MFU（最经常使用）
                具有最小计数的页面可能刚刚被引入且未被使用
          页面缓冲算法
            系统保留空闲帧缓冲池
              写出牺牲帧前，所需页面读到缓冲池中的空闲帧
              调页设备空闲时，选择一个已修改页面写入磁盘，重置其修改位
              将旧页面留在空闲帧池中
      帧分配
        决定为每个进程分配多少帧
          最小帧数
            由计算机架构定义
              寻址模式一次能访问的帧数
          最大帧数
            可用物理内存数量决定
        帧分配算法
          平均分配
          比例分配
            进程相对大小
            优先级
        全局分配与局部分配
          全局置换
            允许一个进程从所有帧集合中选择一个置换帧
          局部置换
            每个进程只能从自己分配的帧中选择
          优先权置换
            允许高优先级进程从低优先级进程中选择帧置换
      系统抖动
        进程的调页时间多于执行时间
          使用局部置换、优先权置换限制抖动
        局部性模型
          随着进程执行，它从一个局部移向另一个局部
          工作集模型
            最近n个页面引用的页面集合
        缺页错误频率PFF
          实际缺页错误率过高，分配一帧
          实际缺页错误率过低，删除一帧
  同步
    临界区问题
      进程在执行该区时会修改公共变量（临界变量）
      解决方案
        互斥
          一个进程在临界区执行指令，其他进程不能在临界区执行
        进步
          如果没有进程在其临界区内执行，并且有进程需要进入临界区，只在那些不在剩余区的、执行的进程可以参与选择
        有限等待
          一个进程发出请求后，其他进程进入临界区的次数具有上界
    Peterson解决方案
      turn表示哪个进程可以进入临界区
      flag表示哪个进程准备进入临界区
    硬件同步
      单处理器
        禁止中断出现
      多处理器
        test_and_set()
          执行是原子的
        compare_and_swap()
    互斥锁（自旋锁）
      忙等待
      等待锁时没有上下文切换
      用于多处理器系统
        一个线程在一个处理器上自旋（忙等），其他线程在其他处理器上执行临界区
    信号量
      一个信号量除初始化外，只能通过wait（）、signal（）来访问
      使用
        计数信号量
          用于控制访问具有多个实例的某种资源
        二进制信号量
          类似于互斥锁
      实现
        wait（）发现信号量不为正时，阻塞自己
        block（）将进程放到与该信号量相关等待队列
        signal（）等待信号量S而阻塞的进程重新执行
        wakeup（）进程的重新执行
        如果信号量为负，绝对值表示等待它的进程个数
      硬件支持（保证wait、signal原子性）
        单处理器
          禁止中断
        多处理器
          每个处理器都禁止中断
          提供其他加锁技术
      没有完全取消忙等待，只是将忙等待限制在ＰＶ操作的临界区上（该临界区只有几行代码，忙等代价很小，而且通过硬件支持同步）
      优先级反转
    经典同步问题
      有界缓冲问题
      读者-写者问题
        第一读写者问题
          读者不应该等待，除非写者使用
          写者饥饿
        第二读写者问题
          如果有写者等待，读者也应该等待
          读者饥饿
      哲学家就餐问题
    管程
      帮助程序员避免因信号量使用不当造成的死锁
    死锁
      死锁特征
        必要条件
          互斥
          占有并等待
          非抢占
          循环等待
        资源分配图
          资源类型单实例时，出现环说明死锁
          申请边
            进程申请资源类型的一个实例
            指向矩阵（资源类型）
            进程申请资源类型实例时加入申请边
          分配边
            资源类型分配一个实例给进程
            指定矩阵（资源类型）内的某个圆点（实例）
            进程不需要访问资源则删除
          需求边
            进程可能在将来某个时候申请资源
            申请资源，需求边转为申请边
            释放资源，分配边转为需求边
            进程开始执行时，所有需求边先处于图中
              进程所有边都为需求边时，可以新增需求边
      死锁处理
        死锁预防prevection
          确保必要条件至少有一个不成立
            互斥
              有些资源本身就是非共享的
            持有并等待
              进程执行前申请并获得所有资源
              进程在没有资源时才可申请
            非抢占
              一个进程处于等待时，其他进程可以抢占其资源
              常用于状态可保存和恢复的资源
                CPU寄存器、内存
            循环等待
              对所有资源类型完全排序
              要求每个进程按递增顺序申请资源
                限制用户申请资源的顺序
              需要应用程序员来按照顺序编写程序
        死锁避免avoidance
          系统根据进程申请、使用资源的信息确定是否满足请求
            安全序列
              系统按一定顺序为每个进程分配资源并避免死锁
              不是所有非安全状态都能导致死锁
              只要在安全状态下操作系统就能避免非安全状态
          资源分配图算法
            适用于资源类型单实例
          银行家算法
            安全算法
            资源请求算法
              检查按该请求分配后的状态是否安全
                请求的资源大于现有剩余资源
                请求资源+已分配资源大于声明的最大申请资源
              调用安全算法
        死锁检测
          资源类型单实例
            等待图
              删除资源分配图中的资源类型
              依赖边
                A->B
                  进程A等待进程B释放一个A所需的资源
          资源类型多实例
            类银行家算法
              将需求0的进程视为可完成的进程，回收其资源
        死锁恢复
          进程终止
            中止所有进程
            一次中止一个进程，直到消除死锁循环
          资源抢占
            选择牺牲进程
              沉默代价
            回滚
              完全回滚
              回滚至消除死锁
            饥饿
        不处理死锁