1 概述
- 现代操作系统四个基本观点
- 从外部看：用户环境观点、虚拟机器观点
- 从内部看：资源管理观点、作业组织观点
- 资源管理：资源复用、资源虚拟、资源抽象
- 计算机软件分类
- 系统软件：操作系统等
- 支撑软件：开发环境
- 用户软件：应用程序
- 操作系统：管理和控制计算机系统软硬件资源，组织计算机工作流程的系统软件，计算机与用户间的接口。
- 操作系统特征：并发性、共享性、异步性、虚拟性
- 基本特征：并发性、共享性
- 异步性：各进程以相对独立的、不可预知的速度推进
2 硬件环境
- 4种I/O方式
- 程序I/O：处理器定期轮询I/O单元
- 中断
- 直接存储器访问DMA：自动控制成块数据在内存和I/O单元间传送
- 通道：专门负责I/O的处理机，运行专门软件
3 操作系统结构
- 操作系统组件
- 进程管理
- 主存管理
- 辅存管理
- I/O设备管理
- 文件管理
- 保护系统
- 网络
- 命令解释系统
- 操作系统结构
- 简单结构
- 宏内核：单一、庞大
- 分层结构：模块分隔
- 微内核：不完整、安全可靠
- 操作系统发展
- 批处理系统：单道、多道（调度、并发）
- 过程：提交、装入、执行
- 分时系统：强调用户交互
- 实时系统：固定时间约束
- 操作系统实现
- 原则：策略（做什么）与机制（如何作）分离
4 进程
- 进程组成（代码+数据/代码+数据+PCB）
- 程序代码
- PCB：与进程一一对应，由操作系统管理
- 上下文：PC计数器和寄存器
- 全局变量
- 栈：自动分配
- 堆：手动申请释放
- 进程与程序对比
- 进程是动态的；程序是静态的
- 进程是短暂的，有生命周期；程序相对长久
- 一个程序可以对应多个进程
- 进程可以创建其他进程，而程序不能
- 进程可以真实地描述并发，而程序不能
- 进程特征：并发性、动态性、独立性、交互性、异步性、结构性
- 进程状态：新建、运行、阻塞、就绪、结束
- 进程调度
- 高级调度（长程调度）：形成作业队列（分钟以上）
- 负载均衡：I/O密集型进程、CPU密集型进程
- 中级调度（中程调度）：存储器资源管理（调入主存）
- 低级调度（短程调度）：处理机资源分配（运行就绪进程）
- 调度模式：抢占式、非抢占式
- 调度算法（ch6）
- 进程关系
- 进程同步：合作、共享资源引起的直接制约
- 进程互斥：竞争公有资源引起的间接制约
- 进程通信：
- 共享存储：
- 共享数据结构：效率低
- 共享存储区：效率高
- 有限缓冲池——生产者消费者问题
- 消息传递（利用通讯原语）
- 直接通信：消息队列
- 间接通信：信箱（阻塞、非阻塞）
- 管道通信（共享文件）
- 网络通信
5 线程
- 线程优点
- 创建花费时间、空间少
- 切换花费时间少
- 共享数据空间，通信方便
- 能实现真正的并行
- 进程是资源分配的基本单位，线程是CPU调度的基本单位
- 线程是进程中的一个运行实体，不能独立于进程存在
- 线程组成：程序计数器、寄存器、一组栈、TCB
- 线程实现
- 用户级线程
- 优点
- 进程切换不调用内核
- 调度算法由用户程序指定
- 可运行于任何操作系统
- 缺点
- 系统调用要阻塞整个进程
- 同一进程的线程只能运行于同一处理器
- 线程共享处理器时间片，分到时间较短
- 内核级线程
- 优点
- 同一进程的线程可以并行
- 阻塞只影响线程
- 内核例程是多线程的
- 缺点
- 线程切换需要调用内核
- 方案
- 多对一：线程不能真正并行
- 一对一：用户线程数量受硬件限制
- 多对多：允许并行和创建大量线程
6 CPU调度
- 调度器：选择要执行的任务
派遣器：切换上下文
- 调度指标
- CPU使用率
- 吞吐量：单位时间执行完成的进程数
- 周转时间：进程从等待进入内存到结束的时间
- 等待时间：进程在就绪队列中等待时间的总和
- 响应时间：从提交请求到收到第一个响应的时间
- 调度算法
- 先到先行FCFS：非抢占
- 最短作业优先SJF：非抢占/抢占，最优，不适合短期调度
- 优先级调度：非抢占/抢占，饥饿-老化
- （时间片）轮转法RR：相比SJF周转时间更长，响应时间更短
- 多级队列：划分任务类型。多级反馈队列中任务可在队列间移动。
7 进程同步
- 竞争条件：多个进程并发访问和操作同一数据并且执行结果与访问发生的顺序有关
- 临界资源：一次只允许一个进程使用
临界区：涉及临界资源的程序段
- 临界资源访问原则：有空让进、无空等待、多中择一、有限等待、让权等待
- 临界区问题软件算法
- 单标志位法
- 思想：在进入区检查turn是否为i，在退出区将turn修改为j
- 问题：强制轮流（不可能连续使用）
- 双标志位法
- 思想：设立标志数组flag[]描述进程是否在临界区，若其他进程都不在则进入
- 问题：进程可能同时进入临界区或都无法进入临界区
- Peterson算法（正确）
- 思想：先修改、后检查，后修改者等待
- 缺点：忙等待、实现复杂
- 临界区问题硬件方法
- “测试并设置”指令
- “交换”指令
- 开关中断指令：关中断-临界区-关中断
- 优点：适用于任意数目进程、简单、支持多个临界区
- 缺点：忙等待、饥饿、死锁
- 信号量：一个与队列有关的整型变量，只能通过初始化和P/V原语访问
- 公用信号量：实现互斥，初值为1
- 私用信号量：实现同步，初值为非负整数
- P/V原语：必须成对出现
- P中可能要阻塞自己，V中可能要唤醒某个线程
- 对于互斥操作，PV处于同一进程；对于同步操作，PV处于不同进程
- 生产者-消费者问题
- 同步：full、empty
- 互斥：mutex
- 同步在外，互斥在内
- 读者-写者问题：不允许同时读-写或同时写-写
- 读者优先：可能导致写者饥饿
- readcount记录写着数量
- rmutex保证readcound的修改互斥
- wmutex保证读写互斥
- 写者优先：
- x保证readcount的修改互斥，初值为1
- y保证writecount的修改互斥，初值为1
- z保证第一个写出现时跳过读，初值为1
- r保证写时不可进入读队列，初值为1
- w保证读时不可写、写写互斥，初值为1
- 哲学家就餐问题
8 死锁
- 死锁原因
- 一组阻塞进程分别占有一定资源并等待获取另外一些已经被同组其他进程所占有的资源
- 资源竞争不一定会产生死锁
死锁的四个必要条件（特征）
- 互斥
- 持有并等待
- 非抢占
- 循环等待
- 资源分配图
- 进程指向申请的资源，资源指向被分配的进程
- 若有环且每种资源只有一个实例，则死锁
- 若有环且每种资源有若干实例，则可能死锁
- 若无环，一定没有死锁
- 死锁处理方法
- 死锁预防
- 思路：破坏四个必要条件之一
- 死锁避免
- 安全状态
- 安全一定不会死锁
- 不安全可能死锁
- 思路：动态检查资源分配状态，保证不存在循环等待，避免不安全状态
- 死锁检测
- 资源分配图算法
- 死锁恢复
- 终止进程
- 资源抢占：需要解决三个问题——选择牺牲品、回滚进程、避免饥饿
9 内存管理
- 程序执行前：编译、链接、装入
- 地址表现形式：符号、可重定位地址、绝对地址
- 地址再定位：将逻辑地址和物理地址对应起来的过程，由操作系统装入程序完成
- 常用程序装入技术
- 绝对装入技术
- 优点：装入过程简单
- 缺点：依赖硬件结构
- 可重定位装入技术
- 静态再定位：程序执行前进行再定位
- 动态再定位：程序访问内存前进行再定位
- 对比：实现难易、程序开始执行后是否可以移动、是否可以连续分配
- 存储管理任务
- 存储分配和回收
- 存储共享
- 存储保护
- 存储器扩充
- 连续分配方式
- 单一连续存储管理：用户区、系统区，一次一个进程
- 分区存储管理：
- 问题：存在内外碎片、难以共享内存
- 分区表：空闲分区表、占用分区表
- 空闲分区表根据分配算法进行排序
- 固定分区：内碎片、需要估计内存需求、并发数目受限
- 动态分区：外碎片
- 常用分配算法
- 最先适应算法：选择地址最小的
- 循环最先适应算法：从上次分配的地方开始查找
- 最佳适应算法：选择空间最小的
- 最坏适应算法：选择空间最大的
- 外碎片问题：紧凑技术
- 分区保护：定位寄存器+界限寄存器
- 内存扩充技术
- 覆盖技术：必要代码常驻内存，其余模块用到时装入并覆盖
- 交换技术：进程交换或段/页交换（虚拟内存）
- 比较
- 覆盖发生在进程内，交换发生在进程间
- 覆盖提高编程难度，交换不对用户有要求
- 离散分配方式
- 分页存储管理
- 进程页表
- 每个进程都有
- 记录逻辑页号与内存块号的关系
- 存放在内存中，属于进程的现场
- 通过页表始址寄存器、页表长度寄存器支持
- 物理页面表
- 整个系统用来描述物理内存空间使用状况的表
- 数据结构：位示图（固定分区）、链表（动态分区）
- 请求表：描述各进程页表的位置和大小
- 联想寄存器（快表）：提升速度，将页表装入关联存储器
- 解决了外碎片问题
- 分段存储管理
- 思想：按照程序自身逻辑划分用户空间，进而划分内存空间
- 进程段表
- 记录段号、段长度、段首地址
- 存放在内存中，属于进程的现场
- 系统段表（占用段）、空闲段表
- 通过段表始址寄存器、段表长度寄存器支持
- 联想寄存器（同上）
- 优点：便于动态申请内存、便于共享
- 缺点：产生碎片
- 段页式存储管理
- 逻辑空间段式划分，物理空间页式管理
- 按页分配，同段尽量分配到一起
10 虚拟内存
- 虚拟内存实现
- 请求页式管理机制
- 页表结构
- 采用两级或多级页表，每级都可以装入联想存储器
- 页面置换算法
- 先进先出算法FIFO：性能差，抖动现象
- 最佳算法OPT：选择未来不再使用的页面。理想算法，难以实现
- 最近最少算法LRU：选择最长时间没有被使用的页，性能最好
- 最不常用算法LFU：选择上次中断到本次中断访问次数最少的页
- 简单轮转算法clock：轮转，被访问可抵一次
- 调入策略
- 请求调页
- 预调页
- 被修改页面只能调出到交换区，只有未被修改页面可以从文件区读
- 调出策略
- 请求调页
- 语调页
- 常驻集：虚拟页式管理中给进程分配的物理页面数目。影响并行度和缺页率
11 文件管理
- 文件分类
- 按逻辑结构
- 流式文件：无结构，灵活
- 记录式文件：有结构
- 按物理结构
- 顺序：随机存取，速度最快
- 链接：无外碎片，可动态变化，但无法随机存取
- 索引：综合优点，但索引表带来了开销
- 综合模式：直接索引+多级索引
- 目录
- 目录项：FCB
- 目录文件通常保存在外存
- 目录结构
- 一级目录结构：所有用户共用一个目录
- 二级目录结构：每个用户一个分离的目录
- 多级目录结构：树型
- 文件名（路径）唯一
- 文件访问：按文件名检索目录（绝对/相对）
- 文件寻址：根据FCB中地址信息寻址
- 目录改进：目录项分解法，将FCB分为符号目录项和基本目录项两部分。
- 符号目录项（次部）：文件名、文件号
- 基本目录项（主部）：除文件名外的所有
- 访盘时只需访问符号目录项，访盘次数减少
- 空闲空间管理
- 数据结构：空闲块表、空闲块链表
- 管理方法：位示图法、成组链接法
- 文件系统实现
- 系统文件表：记录当前打开的文件号、共享计数、修改标志
- 用户文件表：每个进程一个，记录用户进程打开文件信息
- 文件操作
- 新建
- 检查合法性
- 检查重名
- 找空闲位置
- 填写目录项
- 返回
- 打开
- 找FCB主部
- 检查合法性
- 若已打开，共享计数+1；否则FCB主部填入内存中的打开文件表，共享计数为1
- 更新用户打开文件表
- 返回文件描述符
- 读取......
13 磁盘结构
- 磁盘调度算法
- 先来先服务FCFS
- 最短寻道时间
- 扫描算法
- 单向扫描算法