操作系统

操作系统是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。

操作系统

• 文件系统
  • 概念
    • 簇与块
      • Windows下叫簇,Linux下叫块
      • 文件系统管理的最小单位
  • 逻辑结构
    • 顺序文件
    • 索引文件
      • 需要一张索引表
      • 定长记录文件的索引表无长度项
    • 顺序索引文件
      • 当索引数=索引块内条目数时查找次数最少,为sqrt(N)
    • 直接文件或Hash文件
  • 目录
    • 文件目录即文件的FCB
    • 目录文件指表示目录的文件,这种文件的数据是其子文件与子目录的目录项
    • FCB包含文件权限信息
    • 在UNIX中FCB分离为文件目录与索引节点
      • 文件目录仅包含文件名与索引节点指针
    • FCB中包含着物理地址,具体取决于实现方式
      • 连续分配
        • 首地址
      • 链接分配
        • 首地址
      • 索引分配
        • 索引块地址
    • 内存索引节点
      • 逻辑设备号
      • 链接指针
      • 访问计数
      • 状态
        • 是否被访问/修改
      • 编号
        • 标识内存结点
    • 硬链接与软链接
      • 每个目录下都有两个硬链接文件,一个指向自身,另一个指向父目录
      • 因此每个目录的硬链接数=2+子目录数
      • 软链接
        • 事实上是一个包含指向文件路径的文件
        • 访问时就相当于按照这个路径访问文件
        • 因此比硬链接慢
      • 在linux中，当拥有某文件的权限而不拥有父目录的权限，此时硬链接能访问该文件而软链接不行
    • 目录结构
      • 单级
        • 不允许文件的文件名相同
      • 两级
        • 允许不同用户持有文件名相同的文件
      • 树型
        • 路径名唯一确定文件
      • 无环图
        • 支持用户间文件共享
  • 访问控制
    • 访问控制列表ACL
      • 又称存取控制矩阵
    • 口令
      • 要求访问文件时必须提供口令
      • 口令存储在OS内部,不安全
    • 密码
      • 加密文件,需要使用密码解密
  • 文件访问
    • 用户调用接口
    • 系统依次查找目录以获取文件FCB或索引节点
    • 按照索引信息检查用户访问权限
    • 将用户提供的逻辑地址转换为物理地址
  • 文件实现
    • 目录实现
      • 线性表
        • 只支持顺序查找
        • 在表尾添加新目录项
      • 哈希表
    • 文件分配方式
      • 连续分配
      • 显式链接分配（FAT）
        • 在内存中
        • 并可用于管理空闲块
        • 在FAT中0，1号簇有特殊用途
        • -9表示坏块，-10~-15保留，-8~-1用于文件结束标志
        • 但是计算最大支持文件仅需考虑表项长度（例如FAT16，2^16*sector size即可
        • 最大地址也只需考虑FAT表长度
      • 隐式链接分配
        • 目录包含头尾指针
        • 稳定性差
      • 索引分配
        • 多层索引
      • 混合索引分配
        • Linux方式
    • 逻辑卷与物理卷
      • 逻辑卷包括目录区和文件区
    • 空闲空间管理
      • 空闲表
        • 头地址-空闲块长度
        • 跟内存回收一致，可以合并
      • 空闲链表
        • 空闲盘块链
          • 将空闲盘块串起来
          • 每个项长度为1
        • 空闲盘区链
          • 将连续的空闲盘区串起来
          • 每个项长度不定
      • 位图法
      • 成组链接法
        • 每个索引块含有(n-1)个数据块与1个索引块的指针
        • 系统拥有一个指向第一个索引块的指针
  • 磁盘管理
    • 格式化
      • 低级格式化
        • 创建物理扇区
          • 确定物理扇区使用的数据结构
          • 例如校验码的位数
      • 逻辑格式化
        • 创建文件系统
    • 访问时间
      • 寻找时间（寻道时间）
      • 延迟时间（旋转延迟）
        • 平均半圈
      • 传输时间
        • 一般而言，传输时间等于转过该扇区需要的时间
    • 磁盘调度
      • FCFS
      • SSTF
      • SCAN
        • 双方向处理
      • CSCAN
        • 单方向处理
      • 默认LOOK=SCAN,CLOOK=CSCAN
• 概论
  • 性能指标
    • MIPS
      • 每秒百万指令
      • 由于快慢是相对程序而言的，MIPS大的计算机不一定比MIPS小的快
  • 操作系统特征
    • 并发
      • 一段时间内多个任务
      • 并行
        • 同时多个任务
        • 注意并行一定是并发的
    • 共享
      • 资源共享
      • 分类
        • 独占/互斥共享
        • 同时访问
    • 虚拟
      • 虚拟存储器
      • 虚拟设备
    • 异步
      • 进程推进顺序不可预知,与调度有关
  • 接口
    • 命令接口
      • 交互式命令接口(SHELL)
      • 批处理命令接口(BAT)
    • 程序接口
      • 用户程序通过使用系统调用获取服务
      • 系统调用
        • 又称广义指令
        • 可以在用户态调用
        • 在内核态执行
  • 操作系统演进
    • 总体上,批处理->分时->实时
    • 单道批处理系统
    • 多道操作系统(多道批处理系统)
      • 也称多任务操作系统
      • 宏观上并行，微观上并发/串行
      • 主要缺点是不提供人机交互能力
    • 分时操作系统
      • 支持交互
    • 实时操作系统
      • 软实时
      • 硬实时
        • 有硬指标
  • 系统调用
    • 每个进程/线程有两个栈,用户栈与内核栈
    • 当陷入中断进入内核态后,会将当前栈指针压入内核栈,之后在内核态下运行
    • 返回时使用中断返回指令(iret)而非无条件跳转指令
    • 在系统调用中可以被阻塞
  • 大内核与微内核
    • 微内核增加稳定性,降低性能
• 进程管理
  • 进程的组成,状态
  • 进程控制
    • 创建
      • 分配PID
      • 分配必要资源
        • 如果资源不足,进入阻塞态
      • 初始化PCB
      • 插入就绪队列
    • 终止
      • 按PID查找PCB
      • 若正执行,立刻终止执行
      • 关闭所有子进程
      • 释放资源
      • 删除PCB
    • 阻塞
      • 按PID查找PCB
      • 将状态改为阻塞,插入等待队列
    • 唤醒
    • 切换
      • 一定处于核心态
  • IPC
    • 高级通信
      • 消息传递机制
        • 直接通信
          • 操作系统提供一组原语,通信不经过操作系统
        • 间接通信
          • 双方通过共享中间实体(邮箱)交换信息
      • 存储器共享
      • 管道
    • 低级通信
      • 信号量
  • 线程
    • 共享地址空间及其他资源
    • 共享堆但不共享栈
    • 不共享栈,但允许runtime利用指针等方式访问其他线程的栈空间
    • 假装不考与父子进程的联系与区别
    • 内核级与用户级
      • 内核级线程是native的,由os调度
      • 用户级线程由library支持,由lib调度
      • 因此多对一模型一个线程阻塞将导致整个进程阻塞
  • 调度
    • 高级/作业调度
      • 只进行一次,使作业开始运行
    • 中级/内存调度
      • 即交换技术,将暂时不运行的进程移出内存
    • 低级/调度
      • FCFS
        • 不适合IO型进程
          • 因为进入阻塞态的概率会比IO型大得多
        • 事实上对短进程不利
      • RR
        • 一定是抢占式
      • SJF
        • 必定导致饥饿
      • 高响应比
        • 没有饥饿
      • 多级反馈
      • (静态)优先级
        • 系统进程>用户进程
        • 交互型>非交互型
        • IO型>计算型
    • 不能调度的情况
      • 中断中,此时逻辑上不属于某一进程
      • 在操作系统内核临界区时
        • 注意在普通临界区可以调度
        • 内核临界区指访问OS互斥资源的临界区,例如访问PCB的代码
      • 在原语中
      • 注: 目前(Linux2.6以后),当不属于上述情况时,处于内核态的程序总可以被抢占
      • 另外,当使用抢占式时,当从内核态回到用户态时,总会发生调度
  • 进程同步
    • 信号量
      • 整型信号量
        • 忙等
      • 记录型信号量
        • 先修改再对队列进行操作
        • 所以注意临界条件
    • 进程之间的关系
      • 同步
        • 又称直接制约
      • 互斥
        • 又称间接制约
        • 没有逻辑上的先后
    • 死锁判断
      • 代码中有计数器时认为有多个进程,例如读写者问题
    • 并发进程推进的相对速度与调度策略有关
    • 单缓冲区的生产者消费者问题不需要mutex
    • 管程
      • 语言机制,保证同一时刻至多一个进程使用管程
    • 条件变量
      • 为了使管程支持同步,加入类似信号量的机制
      • 条件变量拥有wait和signal方法
      • 与记录型信号量的不同的时它不记录值,仅将进程移入移出等待队列
    • 死锁
      • 鸵鸟策略
        • Windows
        • Linux
        • OpenBSD
  • 死锁
    • 死锁的原因
      • 互斥
        • 共享资源不会死锁
      • 不剥夺
        • 不允许OS强制拿走进程目前独占的资源
      • 请求并保持
        • 进程保持资源后又会提出新请求
      • 循环等待
    • 死锁预防
      • 破坏互斥
        • 不现实
      • 破坏不剥夺
        • 一般用于易于保存和恢复的资源
      • 破坏请求并保持
        • 静态分配,即一次分配所有资源
      • 破坏循环等待
        • 顺序资源分配
    • 死锁避免
      • 使用银行家算法防止进入不安全状态
      • 限制资源的分配顺序而非申请顺序
    • 死锁检测
      • 资源分配图
        • 进程是大圆
        • 资源是方框,其中的小圆代表资源实例
        • 资源向进程的边为分配边
        • 进程向资源的边为请求边
      • 死锁定理
        • S死锁当且仅当资源分配图不可完全化简
    • 死锁解除
      • 资源剥夺
        • 挂起某些死锁进程并剥夺资源
        • 可能导致这些被剥夺进程的饥饿
      • 撤销进程
        • 撤销部分或全部死锁进程
      • 回退
        • 需要设置还原点
        • 执行对象不一定死锁
• 内存管理
  • 交换,覆盖
    • 交换指硬盘中的进程A覆盖内存中的进程B
    • 覆盖指进程在硬盘中的段A覆盖内存中的段B
    • 交换要求换出的进程必须空闲
    • 覆盖段必须由开发者手动设计
  • 装入与链接
    • 链接
      • 静态链接
        • 编译为一个完整的程序
      • 装入时动态链接
        • 编译为多个模块,装入时一起读入
      • 执行时动态链接
        • 编译为多个模块,需要时再读入
    • 装入
      • 绝对装入
        • 程序将被放置到固定位置
        • 只适合单道程序
      • 可重定位装入
        • 又称静态重定位
        • 在装入时将代码段的相对地址修改为绝对地址
        • 一旦装入后,内存位置与大小就不再变化
      • 动态运行时装入
        • 需要重定位寄存器的支持
        • 允许地址空间比存储空间大
  • 内存分配方式
    • 连续分配
      • 单一连续分配
        • 只适合单道环境
      • 固定分区
        • 等长分区
        • 不等长分区
      • 动态分区
        • 无内部碎片有外部碎片
    • 非连续分配
      • 分页
        • 每个进程有半页的页内碎片
        • 页表基本上常驻内存
        • 需要增加页表寄存器
        • 快表TLB
        • 页号可能有越界中断,但页内偏移没有
      • 分段
        • 段表寄存器
        • 分段系统中地址二维,由用户提供
        • 段号和段内偏移都可能出现越界中断
      • 段页式
        • 高层段机制,底层页机制
  • 虚存
    • 核心是局部性原理
    • 只能在非连续分配上实现
    • 页面置换算法
      • 页面置换只考FIFO OPT LRU CLOCK
      • Belady
        • 有FIFO选FIFO
        • 会出现Belady的算法
          • NRU/CLOCK及其改进
          • FIFO
        • 不会出现Belady的算法
          • OPT
          • LRU
      • CLOCK算法
        • 替换后额外移动一次指针
        • 改进型CLOCK一般会提供指针位置
    • 页面分配策略
      • 没有固定分配全局置换
      • 驻留集指进程的物理页框集合
      • 调入页面的时机
        • 预调页
        • 请求调页
      • 从何处调入
        • swap够
          • 文件预先复制到swap
          • 从swap调入
        • swap不够
          • 不被修改的部分从文件区调入,不换出
          • 可能被修改的文件换出后再从交换区调入
        • UNIX
          • 所有文件初次均从文件区调入
          • 由其他进程调入的共享页面不重复调入
      • 工作集
        • 最近访问窗口中的不同页面