操作系统
操作系统
  1.计算机系统概述
    1.1并发与并行
      并发 共享 虚拟 异步
    1.2操作系统发展历程
      手工阶段
      单道批处理系统
        内存中只有一道作业运行
      多道批处理系统
        通过中断机制，各部件之间并行工作
        宏观上并行，微观上串行
          同一时刻只有一个程序在运行
      分时操作系统
      实时操作系统
        及时性可靠性
        规定时间内完成
    1.3操作系统运行环境
      特权指令与非特权指令
      内核态与用户态
      中断
        内部异常
          和当前指令执行有关的操作
          故障
          自陷
          终止
          硬件中断
          软件中断
        外部中断（硬件）
          可屏蔽中断与不可屏蔽中断
      系统调用
        与共享资源有关的操作都必须通过系统调用
    1.4操作系统结构
      分层法
        性能差，稳定性一般，扩展性差，维护性好，安全性一般，灵活性差
      模块化
        性能好，稳定性差，扩展性好，维护性好，安全性一般，灵活性较好
      宏内核
        性能极好，稳定性差，扩展性差，维护性差，安全性一般，灵活性差
      微内核
        性能差，稳定性好，扩展性好，维护性好，安全性好，灵活性好
        可支持分布式，采用面向对象技术
        基于C/S模式：客户与服务器之间借助为内核提供的消息传递机制交互
      外核
        性能好，扩展性好，维护性复杂，安全性好，灵活性好
    1.5操作系统引导
      激活CPU，开始执行BIOS的指令
      硬件自检，BIOS在内存最开始空间构建中断向量表，接下来使用中断功能通电自检
      加载带有操作系统的硬盘
      加载主引导记录MBR，告诉CPU去哪个主分区寻找操作系统
      主引导记录扫描分区表，识别含有操作系统的硬盘分区
      加载分区引导记录PBR，寻找并激活分区根目录下引导操作系统的程序(启动管理器)
      加载启动管理器
      加载操作系统
    1.6虚拟机
      第一类虚拟机管理程序是唯一一个运行在最高特权级的程序
  2.进程与线程
    2.1进程与线程
      进程控制快（PCB）
        进程描述信息
        进程控制和管理信息
        资源分配
        处理及相关信息
          各种寄存器的值和状态字
      进程的状态
        运行态
        就绪态
          得到CPU即可运行 就绪队列
        阻塞态
        创建态
          PCB申请失败则创建失败，
若资源不足则处于创建态
        终止态
      进程控制
        进程的创建
        进程的终止
          正常结束
          异常结束
          外界干预
        进程的阻塞和唤醒
          需要修改PCB状态
      进程通信
        共享存储区
        消息传递
        管道通信(共享文件)
          同一时刻只能单向流动
        信号
          在PCB中用n位向量(位图)记录 待处理 和 被屏蔽 的信号
同一种待处理信号只能记录一个，后来的被丢弃
          内核给某个进程发信号、一个进程给另一个进程发信号
          操作系统把一个进程从内核态切换到用户态时会检查是否有未被阻塞的待处理的信号
          信号的处理方式：忽略、执行默认处理程序、自定义处理程序
          SIGKILL与SIGSTOP不可自定义或忽略
          信号处理结束后会返回进程的下一条指令执行
      线程与多线程
        线程
          类似一个大软件里面的各个小功能
          被调度与分配的基本单位
          与同属于一个进程的其他线程共享进程所拥有的全部资源
        线程的实现方式
          用户级线程
            调度单位为进程
            操作系统内核意识不到线程的存在
            优点
              线程切换不需要转到内核空间
              不同的进程可以对自己的线程选择不同的调度算法
              实现与操作系统平台无关，线程管理是用户程序的事
            缺点
              一个线程阻塞时其他线程也阻塞
              不能发挥多CPU优势
          内核级线程
            调度单位为线程
            线程管理的所有工作都在内核进行的
            线程切换需要转换到内核态
          组合方式
        多线程
          多对一
            线程管理无需切换到内核态
            不能发挥多CPU优势
          一对一
            并发能力强
            开销大
          多对多
    2.2CPU调度
      调度的基本概念
        高级调度、中级调度、低级调度
        调度的时机、方式
        在中断或原子操作中不能进行进程切换
      调度的目标
        CPU利用率=有效工作时间/(有效工作时间+空闲等待时间)
        吞吐量
        周转时间=完成时间-提交时间
        带权周转时间=周转时间/实际运行时间
        等待时间：进程处于等待CPU的时间之和
      进程切换
        需要进行上下文切换
          上下文切换只能发生在内核态
          上下文保存到进程的PCB中
      调度算法
        先来先服务(FIFO)
        短作业优先(SJF)
        高响应比优先
          响应比=(等待时间+要求服务时间)/要求服务时间
        优先级调度
        时间片轮转(RR)
        多级队列调度算法
          不同的就绪队列可以采用不同的调度算法
        多级反馈队列调度算法
      多处理机调度
    2.3同步与互斥
      同步与互斥的基本概念
        临界区
        空闲让进
        忙则等待
        有限等待
        让权等待
          不能进入临界区时释放处理器
      实现互斥的方法
        软件方法
          单标志法
            用trun表示允许谁进入临界区
          双标志先检查法
            用两个bool表示想要进入临界区的意愿
          双标志后检查法
            谁都无法进入临界区，会导致饥饿
          peterson算法
            两个bool表示进入的意愿，trun表示谁先可以进去
        硬件方法
          中断屏蔽法
          TestAndSet指令
          Swap指令
          有进程可能一直无法选中，会导致饥饿，
并且没有阻塞态进程，直到时间片用完
      互斥锁
        acqiure()和release()执行都是原子操作
        常用与多处理器操作系统
      信号量
        整形信号量
        记录形信号量
          可以阻塞和唤醒进程semaphore
        信号量实现进程的同步与互斥
      经典同步与互斥问题
        生产者-消费者
        多生产者-多消费者
        读者-写者
        哲学家进餐
          至多n-1名哲学家进餐
          左右筷子都可以拿时
          奇数先拿左边，偶数先拿右边
      管程
        条件变量没有值(无需初始化)，wait操作无条件阻塞进程，signal在不一定会唤醒进程
        每次仅允许一个进程在管程内执行某个内部过程
        各外部进程/线程只能通过管程提供的特定”入口”才能访问共享数据
        互斥访问管程的特性是由编译器实现的
    2.4死锁
      死锁的概念
        饥饿可能只有一个，死锁一定大于等于两个
        死锁必定处于阻塞态
        死锁产生的必要条件
          互斥
          不可剥夺
          请求并保持
          循环等待
      死锁的预防
        破坏互斥
        破坏不可剥夺
        破坏请求并保持
          静态分配
            一次分配所需要的所有资源
        破坏循环等待
          顺序资源分配法
            必须按编号递增的顺序请求资源
      死锁的避免
        安全状态一定不会发生死锁、不安全状态可能会发生死锁
        银行家算法
        需要知道开始到结束的所有资源请求
      死锁的检测与解除
        仅需要知道某一时刻的资源请求
        资源分配图的简化
          所有简化顺序都会得到相同的不可化简图
        死锁的解除
          资源剥夺法
            挂起某些死锁进程，抢占他的资源
          撤销进程法
            强制撤销某些或所有死锁进程
          进程回退法
            回退到没有死锁的地步
  3.内存管理
    3.1内存管理概念
      内存管理的基本原理与要求
        程序的链接与装入
          编译
          装入
            绝对装入
              编译直接产生绝对地址
            可重定位装入
              装入时将相对地址修改为绝对地址
              装入内存时分配要求的全部内存空间
              装入内存后不能随意移动
            动态运行时装入
              需要一个重定位寄存器
              地址转换在运行时进行
          链接
            静态链接
              直接将所需的库函数链接成完整的模块，以后不再拆开
            装入时动态链接
              边装入边链接
            运行时动态链接
              程序执行时进行链接
        进程的内存映像
        内存保护
          设置上下限寄存器
          重定位寄存器：存放进程起始物理地址
界地址寄存器：存放进程最大逻辑地址
      连续分配管理
        单一连续分配
          有内部碎片，无外部碎片
        固定分区分配
          分区大小相等或不等，需要分区使用表
          有内部碎片，无外部碎片
        动态分区分配
          需要空闲分区表或分区链
          对内存进行整理采用紧凑技术，需要动态重定位寄存器的支持
          分配算法
            首次适应
            邻近适应
            最佳适应
              产生最多的外部碎片
            最坏适应
            快速适应
            伙伴系统
            哈希算法
      基本分页存储管理
        用户不可见
        逻辑地址页面称为页号
        物理地址称为页框号
        每个进程有一张页表，页表连续存放，页号可以隐含。
        设置页表寄存器，页表信息存在PCB中。
如页表始址，页表长度
        快表TLB依据局部性原理，减少访存次数
      基本分段存储管理
        用户可见，会有外部碎片
        段表存段长与始址
        实现段共享，配置一张共享段表
      段页式存储管理
        无外部碎片
        每个进程一个段表
        段表记录页表长度和页表始址
        段表只有一个，页表可能有多个
    3.2虚拟内存管理
      建立在离散分配基础上
      访问页面不在内存中时产生缺页中断
      页表机制
        状态位、访问字段、修改位、外存地址
      驻留集
        分配给进程页框的集合
      内存分配
        最小物理块数取决于指令的格式、功能和寻址方式
        内存分配策略
          固定分配局部置换
          可变分配全局置换
          可变分配局部置换
      从外存何处调入页面
        对换区：连续分配，速度快
        文件区：离散分配，速度慢
      页面置换算法
        最佳置换算法OPT
        先进先出算法FIFO
          会出现Belady异常
        最近最久未使用算法LRU
          需要硬件和栈的支持
        最少使用算法LFU
          需要硬件支持
        时钟置换算法CLOCK
          改进型CLOCK算法
            <访问位，修改位>淘汰
      页框回收
        页面缓冲算法
          空闲页面链表
          修改页面链表
          当缺页时，若要读入的数据在链表中则可以避免I/O
      内存映射文件
        映射相同文件到进程的虚拟地址空间
  4.文件管理
    4.1文件的基本概念
      文件系统
        管理对象
          文件
      文件的基本概念
        文件控制块FCB：FCB的有序集合是“文件目录”，一个FCB就是一个文件目录项，文件目录也视为一个文件，称为“目录文件”。
        索引节点：减少磁盘I/O，将
文件名与文件信息分离存储。
          内存索引节点
            增加了索引节点号、状态、访问计数、链接指针等
            查找到索引节点物理地址后还需要一次I/O将索引节点读入内存
          磁盘索引节点
            文件链接计数
      文件的基本操作
        创建、删除、读、写
          ⚠️注意修改文件后还要写回磁盘
        打开与关闭
          系统打开文件表
            存储与进程无关的信息
            设置打开计数器，记录多少进程打开了该文件
          进程打开文件表
            进程的读写指针、访问权限等
          第一次使用open()打开后，后期操作
都使用文件描述符而不是文件名
      文件的逻辑结构
        无结构文件
        有结构文件
          顺序文件
          索引文件
          索引顺序文件
      文件的物理结构
        连续分配
          在磁盘上有连续的块
          FCB中记录文件第一个块号与块数
          支持顺序访问与随机访问
          磁头移动距离小
        链接分配
          隐式链接
            FCB中有第一块指针和最后一块指针
            每个盘块内部有指向下一个盘块的指针
            只能顺序查找，并且每次顺序查找都需要一次I/O读取下一个盘快地址
          显示链接
            整个系统设置一张FAT表，存放下一个盘块指针
            FAT表存在于内存中，相比于隐式链接减少了磁盘I/O，检索在内存中进行
            可顺序访问也可以随机访问
            FCB只记录文件的起始块号
            FAT也可管理空闲盘块与坏块
          索引分配
            单级索引
            多级索引
            混合索引
            需要索引表
      文件保护
        口令保护
          存在FCB中
        加密保护
        访问控制
          用户访问控制列表
    4.2目录
      单级目录
      两级目录
      树形目录
        可以为每个进程设置当前目录
      无环图目录
        方便共享文件，设置共享计数器
      文件共享
        硬链接
          链接到索引节点上
          链接计数：计算链接到本索引节点的用户目录项个数
        软链接(符号链接)
          类似快捷方式
          存储共享文件的路径
    4.3文件系统
      文件系统布局
        文件系统在磁盘中的结构
          主引导记录(MBR)。后面是分区表，标记每个分区的起始地址和结束地址，BIOS读入执行MBR
          MBR执行引导块中的程序后，启动该分区的操作系统
          超级块：包括分区块的数量、大小、空闲块的数量和指针、空闲FCB的数量和FCB的指针等
          文件系统空闲块的信息：位示图或指针链接
        文件存储空间管理(空闲块)
          空闲表法
            连续分配，需要建立一张空闲表
          空闲链表法
            空闲盘快链
            空闲盘区链
              每个盘区包含连续的盘块，盘区内有指
向下一个盘区的指针和本盘区的盘块数
          位示图
            1bit表示一个盘块，大小与磁盘容量有关
          成组链接法
            在内存有空闲盘块号栈
      虚拟文件系统VFS
        屏蔽不同文件系统差异，向上提供统一的调用接口
        存在于内存中，系统启动时建立，关闭时消亡
      文件系统挂载
  5.输入/输出管理
    5.1I/O管理概述
      I/O接口的组成
        设备控制器与CPU的接口
        设备控制器与设备的接口
        I/O逻辑
      I/O端口
        数据、控制、状态寄存器
        独立编址
          需要特殊I/O指令，如in、out等
        统一编址(内存映射I/O)
      I/O控制方式
        程序直接控制
        中断驱动方式
          每个指令周期末尾检查中断信号
        DMA方式
      I/O软件层次结构
        用户层软件
          产生I/O请求
          格式化I/O
        设备独立性软件
          SPOOLing
          逻辑设备名映射为物理设备名
          设备保护
          分块
          缓冲管理
          设备分配与回收
          进程调度
        设备驱动程序
          与硬件直接相关
          向上层用户提供一组标准接口
        中断处理程序
          与硬件紧密相关
        硬件
    5.2设备独立性软件
      高速缓存与缓冲区
        磁盘高速缓存
          功能类似于Cache，逻辑上属于磁盘，物理上属于内存
        缓冲区(内存)
          单缓冲
            处理数据平均时间为MAX(C，T)+M
              输入到缓冲区时间为T，缓冲区输入到工作区时间为M，CPU处理工作区时间为C
          双缓冲
            处理数据平均时间为MAX(C+M，T)
          循环缓冲
          缓冲池
            可供多个进程使用
      设备分配与回收
        设备分配的数据结构
          设备分配表DCT
          控制器控制表COCT
          通道控制表CHCT
          系统设备表SDT
        设备分配安全性
          安全分配
            发出I/O请求后便阻塞
          不安全分配
            发出I/O请求后继续运行
            所请求设备被占用时才进入阻塞状态
        逻辑设备表
          将逻辑设备名映射为物理设备名
      SPOOLing技术
        用空间换时间，将独占设备改造为共享设备
        实现了虚拟设备功能
        将打印请求挂到等待队列上
      设备驱动程序接口
        接受上层软件的命令和参数，将抽象要求转换为具体要求
：例如将逻辑块号转换为物理块号
        检查I/O请求的合法性：是否有出错或越权
        检查设备状态
        发出I/O命令
        及时响应设备控制器的中断请求
    5.3磁盘和固态硬盘
      磁盘
        柱面号 盘面号 扇区号
      磁盘的管理
        1.低级格式化(物理格式化)
          分成扇区
          对扇区编号，利用CRC进行校验
        2.将磁盘分区
          类似C盘D盘等形式分区，创建分区表
        3.逻辑格式化
          将初始文件系统数据结构存储在磁盘上
          建立引导块、空闲存储管理、根目录
          对保存空闲磁盘块的数据结构进行初始化
        引导块
        坏块
          会在FAT表上标明
          利用备用块来替代(对操作系统透明)
      磁盘调度算法
        磁盘存取时间
          寻道时间
          旋转延迟
          数据传输时间
        调度算法
          先来先服务
          最短寻道优先
          扫描算法SCAN（LOOK）（电梯调度算法）
          循环扫描C-SCAN（C-LOOK）
        减少延迟方法
          由于读入一个扇区后要短暂的处理，所以盘面的扇区交替编号，而不是连续编号
          不同盘面错位命名
        提高I/O速度方法
          采用磁盘高速缓存
          调整磁盘请求顺序
          提前读
          延迟写
          优化物理块分布
          虚拟盘
            用内存仿真磁盘。虚拟盘用户控制，磁盘高速缓存OS控制
          磁盘阵列
            并行交叉存取，类似多位交叉存储器
      固态硬盘
  文件名1
  索引节点
链接计数count=2
  文件名2
  系统调用过程
    传递系统调用参数
    执行trap指令陷入到内核态
    执行服务程序
    返回用户态
宏观上并行：从用户角度看，多个程序“同时”都在向前推进。
微观上串行：在任意一个时刻点（微观时间），单CPU实际上只能执行一道程序中的指令。多个程序是交替、穿插地使用CPU。
通过中断和调度实现切换
需要硬软件支持
特权指令：如I/O指令、关中断指令、内存清零指令、存取用于内存保护的寄存器、修改程序状态字等指令。
访管指令在用户态执行。用户程序通过中断或异常进入内核态。
可被计算机修复：缺页、运算溢出
终止：非法操作码、保护错、除数为0
用户态下调用操作系统内核程序，陷阱指令，系统调用指令。
单步跟踪，断点设置
CPU无法继续执行的硬件故障。控制器出错、存储器校验错等。
改变中断屏蔽字可实现多重中断，异常不能被屏蔽
必要服务放入内核：内存管理，进程调度，进程通信，原语，中断处理等
非必要：文件系统，设备驱动等
分区表是MBR的一部分
用户登录、作业调度、系统提供服务、用户程序的应用请求等
线程之间栈空间，PC与状态等是不共享的
平均等待时间与周转时间最优
boolean TestAndSet(boolean *lock){
boolean old;
old=*lock;
*lock=true;
return old;
}
while(TestAndSet(&lock));
进程临界区代码段;
lock=false;
进程的其他代码;
void Swap(boolean *a,boolean *b){
boolean temp=*a;
*a=*b;
*b=temp
}
boolean key=true;
while(key!=false)
Swap(&lock,&key);
进程的临界区代码段；
lock=false;
进程的其他代码段。
预防->避免->检测与解除 资源分配策略逐渐宽松
将原代码编译成若干模块，每个模块都从0开始编址
高级语言翻译为机器语言
程序装入模块装入内存运行
将编译产生的目标模块与所需库函数链接在一起
产生相对地址(逻辑地址)
方便编程，信息共享，信息保护，动态链接，动态增长
实现了段共享，有共享计数，记录多少进程共享该段。
每个进程用自己的段号访问共享段
UNIX：文件存放在文件区，未运行过的页面从文件区调入，运行过被换出的页面从对换区调入
页面掉入内存后还要再次访问TLB
缺页时会访问2次TLB
换出的页面若修改过则要写回外存，未修改过的则不要
每隔一段时间记录一次，会出现访问1次与访问1000次等效的情况
访问计数：有多少个进程正在访问该节点
系统首次操作请求时，open()打开文件。先将目录项复制到内存的打开文件表中，并不调入文件数据。将表项的索引号给用户使用
产生很多外部碎片
消除了磁盘的外部碎片
有第一组的空闲盘块总数和空闲盘块号
指设备控制器中可被CPU直接访问的寄存器
根据SDT找到DCT->COCT->CHCT
驱动程序不允许系统调用，驱动程序本身就运行在内核态，而系统调用是用户态的程序请求使用内核态的服务
磁头从一端移动到另一端时经过的磁道数也要计算