第一章 操作系统引论
操作系统简介
- 手工操作阶段（无OS）
- 缺点：人机速度矛盾
- 批处理阶段（操作系统出现）
- 1、单道批处理阶段 - 一个cpu只能运行一个程序
- 2、多道批处理阶段（OS正式诞生）——目的：提高系统资源的利用率——可以多程序间切换，所以多道批处理
- 优点：多道程序并发执行，资源利用率搞
- 缺点：不提供人机交互能力（缺少交互性）
- 分时操作系统（不可以插队，有了人机交互）- 为每个程序分配一个时间片，每个程序运行完时间片轮转算法
- 优：提供人机交互（交互性）
- 缺：不能优先处理紧急事务
- 实时操作系统（可以插队）
- 硬实时系统：必须在被控制对象规定时间内完成（火箭发射）
- 软实时系统：可以松一些（订票）
- 优点：能优先处理紧急任务
从可靠性看实时操作系统更强，从交互性看分时操作系统更强
不得不知的概念
两种指令
- 特权指令：不允许用户程序使用（只允许操作系统使用）。如IO指令、置中断指令
- 非特权指令：普通的运算指令
两种程序
- 内核程序：系统的管理者，可执行一切指令、运行在核心态
- 应用程序：普通用户程序只能执行非特权指令，运行在用户态
处理机状态
- 用户态（目态）：CPU只能执行非特权指令
- 核心态（又称管态、内核态）：可以执行所有指令
- 用户态到核心态：通过中断（是硬件完成的）
- 核心态到用户态：特权指令psw的标志位0用户态1核心态
- 常考谁在用户态执行，谁在核心态执行
原语
- 1、处于操作系统的最底层，是最接近硬件的部分。
- 2、这些程序的运行具有原子性，其操作只能一气呵成
- 3、这些程序的运行时间都较短，而且调用频繁
中断和异常
- 内中断（异常，信息来自内部）
- 自愿中单–指令中断
- 强迫中断
- 硬件中断
- 软件中断
- 外中断（中断，信号来自外部）
- 外设请求
- 人工干预
- 内中断（异常，信息来自内部）
系统调用
- 系统给程序员（应用程序）提供的唯一接口，可获得OS的服务，在用户态发生，核心态处理
体系结构
- 大内核
- 微内核
第二章 进程调度
进程管理
引入进程目的
- 为了更好地描述和控制程序并发执行，实现操作系统的并发性和共享性（进程是动态的，程序是静态）
定义
- 是计算机中程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位
组成
- PCB
- 保存进程运行期间相关的数据，是进程存在的唯一标志
- 程序段
- 能被进程调度到CPU的代码
- 数据段
- PCB
进程的状态
状态种类
- 创建状态
- 进程正在被创建
- 就绪态
- 进程已处于准备运行的状态，即进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行
- 运行态
- 进程正在占用CPU
- 结束状态
- 进程正在从系统消失
- 创建状态
状态变化
- 就绪态->运行态
- 运行态->就绪态
- 运行态->阻塞态
- 进程需要的某一资源还没准备好
- 阻塞态->就绪态
线程
- 引入目的
- 为了更好的使用多道程序并发执行，提高资源利用率和系统吞吐量
- 特点
- 是程序执行的最小单位，基本不拥有任何系统资源（调度的基本单位）
- 引入目的
处理机调度
- 概念
- 是对处理机进行分配，即从就绪队列中按照定好的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
- 分类
- 高级调度（作业调度）（次数少）
- 中级调度（内存对换）（次数中等）（次数中点）
- 低级调度（进程调度）（次数少）
- 调度方法
- 剥夺式
- 非剥夺式
- 调度准则
- CPU利用率
- 系统吞吐量 - 单位时间内 CPU完成时间的速度
- 周转时间 - 完成时间减去提交时间
- 等待时间 - 运行完之前都是
- 响应时间 - 从提交到第一次开始运行
- 算法
- 先来先服务
- 短作业优先
- 优先级调度算法
- 高响应比优先调度算法
- (运行+等待时间)/等待时间 > 1
- 时间片轮转
- 为每个时间片分配一个算法，剥夺式的
- 多级反馈队列调度算法
- 概念
进程同步
- 引入原因
- 协调进程之间的相互制约关系
- 制约关系
- 同步
- 称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系
- 互斥
- 称间接制约关系。当一个进程进入临界区使用临界资源时，另有一个进程必须等待，当占用临界资源的进程退出临界区后，另进程才允许去访问此临界资源
- 同步
- 临界资源
- 一次仅允许一个进程使用的资源（打印机，共享缓冲区，共享变量，共用队列）
- 临界区
- 在每个进程中访问临界资源的那段程序
- 临界区互斥
- 原则
- 空闲让进：如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入
- 忙则等待：任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。
- 有限等待：进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。
- 让权等待：如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象
- 基本方法
- 信号量：利用PV操作实现互斥
- 原则
- 引入原因
死锁
- 产生的原因
- 非剥夺资源的竞争和进程的不恰当推进顺序（与饥饿的区别）
- 定义
- 多个进程因竞争资源而造成的一种僵局，如果没有外力，这些进程将无法推进
- 解决方法
- 预防死锁
- 破坏互斥条件
- 破坏不剥夺条件
- 破坏请求和保持条件
- 破坏循环等待条件
- 避免死锁
- 安全状态
- 银行家算法
- 检测死锁：利用死锁定理
- 解锁死锁
- 资源剥夺法
- 撤销进程法
- 进程回退法
- 预防死锁
- 产生的原因
习题
- 临界区：访问临界资源的那段程序
- 进程的同步与互斥
- 同步：直接制约关系
- 互斥：间接制约关系
同步机制
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待
信号量（是一种有效实现进程同步和互斥的工具）
- 信号量的值大于0：表示当前资源可用数量（S=5 表示 5个可用资源）
- 小于0：其绝对值表示等待使用该资源的进程个数（S=-5，有五个进程在等待S）
- 信号量初值为非负的整数变量，代表资源数
- 信号量值可变，但仅能由P、V操作来改变。
P/V操作原语
- P操作原语P(S)
- P操作一次，S值减1，即s=s-1（请求分配一资源）；
- 如果S>=0，则该进程继续执行；如果S<0表示无资源，则该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至另一个进程执行V（S）操作）
- V操作原语V(S)
- V操作一次，S值加1，即s=s+1（释放一单位量资源）;
- 如果S>0,表示有资源，则该进程继续执行；如果S<=0,则释放信号量队列上的第一个PCB所对应的进程（阻塞态改为就绪态），执行V操作的进程继续执行
- P操作原语P(S)
死锁产生的必要条件
- 互斥条件
- 不可剥夺条件
- 请求和保存条件
- 循环等待条件
当死锁产生的时候一定会有这四个条件，有一个条件不成立都不会造成死锁。其中互斥使用资源时是无法破坏的。
解决死锁的一般方法
- 死锁的预防
- 主动出击，打破死锁产生的必要条件
- 避免死锁的策略
- 躲着他，防止进入不安全状态
- 检测与恢复
- 一开始不作为->一步到位
- 采用措施接触死锁
- 死锁的预防
死锁预防和死锁避免
- 破坏互斥条件（共享）
- 如果允许系统资源都能共享使用，但有些资源根本无法使用，所以，这种防死锁的方法不太行，而且在有些场合应该保护这种互斥性
- 破坏不剥夺条件
- 释放已经保持的所有资源
- 破坏请求和保持条件
- 即进程在运行前一次申请完它所需要的全部资源，在它资源未满足前，不把它投入运行。
- 缺点就是系统资源被严重的浪费
- 破坏循环等待条件
- 为了破坏循环等待条件，可采用顺序资源分配法
- 破坏互斥条件（共享）
银行家算法
第三章 内存管理
- 引入目的
- 为了更好的支持多道程序的并发执行，提高系统性能
- 主要功能
- 内存空间的分配与回收
- 存储的保护和共享
- 保证各道作业在各自的存储空间内运行，互不干扰
- 地址转换
- 在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址。
- 内存扩充
- 利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存
- 用户程序的主要处理阶段
- 编辑阶段
- 创建源文件
- 编译阶段
- 由编译程序将用户源代码编译成若干目标模块，生成目标文件
- 链接阶段
- 由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块。生成可执行文件（形成逻辑地址）
- 装入阶段
- 由装入程序将装入模块装入内存运行
- 运行阶段
- 得到结果
- 编辑阶段
- 相关概念
- 程序的装入
- 绝对装入（逻辑地址必须和实际的内存地址完全一样）
- 静态重定位（地址变换在装入时一次完成）
- 动态重定位（地址变换在执行程序的时候再完成）
- 程序的链接
- 静态链接
- 程序的链接
- 运行时链接
- 地址空间
- 逻辑地址空间（地址空间从0开始）
- 物理地址空间（内存中物理单元的集合）
- 程序的装入
- 管理方式
- 连续分配管理方式（物理地址连续）
- 单一连续分配（分配到内存固定的区域——有内部碎片）
- 固定分区分配（分配到内存不同的固定区域，分区可以相等可以不等——内部碎片）
- 动态分区分配
- 可变分区存储管理：按照程序的需要进行动态的划分
- 动态分区的分配策略算法
- 首次适应（最好）
- 空闲分区以地址递增次数链接。分配内存时按顺序查找，找到大小能满足要求的第一个空闲分区（增大查找开销）
- 最佳适应
- 空闲分区按容量递增的方式形成成分区链，找到第一个能满足要求的空闲分区（外部碎片过多）
- 最坏适应
- 空闲分区按容量递减的方式形成成分区链，找到第一个能满足要求的空闲分区，即挑选出最大的分区（对大进程不利）
- 邻近适应
- 由首次适应算法演变而成。不同之处是，分匹配内存时从上次查找结束的位置开始继续查找
- 首次适应（最好）
- 非连续分配管理方式（物理地址不连续，一般是一段连续，一段不连续）
- 基于分页式存储管理
- 基本分段式存储管理
- 段页式
- 连续分配管理方式（物理地址连续）
- 内存扩充
- 覆盖（同一程序或进程中）
- 交换（不同进程/作业之间进行）
- 虚拟内存
- 引入原因——在逻辑上扩充内存
- 组成部分
- 页表机制
- 中断机制
- 地址变换机制
- 内存与外存
- 页面淘汰（置换）算法：
- 先进先出页面淘汰（置换）算法（FIFO）
- 最近最久未用页面淘汰（置换）算法（LRU）
- 最近最少用页面淘汰（置换）算法（clock）
- 最优（最佳）页面淘汰（置换）算法（OPT）
- 把以后不再使用的或最长时间内不会用到的页面淘汰出去（理论上，不会实现）
- 注意：页面淘汰是由缺页中断引起的，但缺页中断不见得一定引起页面淘汰
- 抖动
- 页面频繁的换进换出
- 原因
- 分配给进程的进程块不足
- 页面分配的策略
- 固定分区局部置换（物理块不变）
- 可变分区全局置换（动态增加物理块）
- 可变分区局部置换（只允许从该进程的内存页面中挑选一页）
第四章
- 文件、文件 系统
- 概念
- 文件是以计算机硬盘为载体的存储在计算机上的信息集合
- 文件系统：就是操作系统中负责操纵和管理文件的一套设施，实现了文件共享和保护，方便用户“按名存取（基本目标），提高文件的存取速度（最重要目标）”
- 功能
- 文件管理、目录管理、文件空间管理、文件共享和保护、提供方便的接口
- 概念
- 文件的逻辑结构
- 无结构文件（流式文件）
- 有结构文件（记录式文件）
- 顺序文件——磁带上一定是存储的顺序文件
- 索引文件
- 索引顺序文件
- 目录和目录结构
- 文件控制块
- 在文件系统内部给每个文件唯一地设置一个文件控制块，它用于描述和控制文件的数据结构，与文件一一对应
- 目录结构
- 单级目录（不允许重名）
- 二级目录（解决了重名问题）
- 主文件目录
- 用户文件目录
- 树形目录优
- 优：方便
- 缺：不便共享
- 绝对路径（从根目录出发）
- 相对路径（从当前目录出发）
- 图形目录（实现了共享）
- 文件控制块
- 文件实现
- 文件分配方式
- 连续分配（有外部碎片，可以直接访问）
- 链接分配（解决了外部碎片，但是不支持直接访问，数据易丢失）
- 索引分配（加入FAT表可直接访问，减少了访问磁盘的次数）
- 文件存储空间管理
- 空闲表法
- 空闲链表法
- 位示图法
- 文件分配方式
- 磁盘管理
- 磁盘地址结构
- 柱面号、盘面号、扇面号
- 磁盘调度算法
- 先到先服务算法（FCFS）
- 最短查找时间优先算法（SSTF）
- 扫描算法和LOOK算法（避免了饥饿算法）
- 循环扫描算法和循环LOOK算法
- 磁盘地址结构
第五章 设备管理
- 设备管理的目标
- 使用方便、与设备无关、效率高、管理统一。
- I/O设备
- 分类
- 存储设备或输入输出设备
- 块设备或字符设备
- 低速中速告诉设备
- I/O控制方式
- ①程序直接控制
- 方式
- 这种方式也可以称为查询方式，CPU不断地去查询设备控制器是否将数据放到了数据存储器中，或者从数据存储器存到设备中，当完成IO时CPU才能去干别的事。——以字为数据传输单元，cpu利用率低
- ②中断方式：
- cpu发出指令后就可以去干别的事，当设备控制器把数据存在数据存储器后，向cpu发出中断请求，然后cpu再来处理这部分数据
- ③DMA方式
- 解决了中断方式提高了cpu利用率，但是数据寄存器有限，介于i/o和主存之间。
- ④IO通道控制方式：
- DMA虽然大大地提升了cpu的利用率，但是DMA只能传输一个连续的数据块。所以引入了IO通道的控制方式，IO通道控制方式可以传输不连续的数据块，减少了CPU干预。CPU通过对IP通道发出指令，然后让IO通道自己工作，等数据传输完才向CPU发起中断。
- 分类
- 引入缓冲的目的和缓冲区的设置方式
- 1、引入缓冲区的目的
- 缓和CPU与外设间速度不匹配的矛盾
- 提高CPU与外设之间的并行性
- 减少对CPU的中断次数
- 磁盘的高速缓存——在内存中单独开辟一个空间，作为磁盘的高速缓冲
- 以空闲的区域作磁盘的高速缓冲区
- 2、缓冲区的设置方式
- 单缓冲：当数据到达率与离去率相差很大时，可采用单缓冲方式——设备和处理机之间
- 双缓冲：必须等缓冲区满
- 循环缓冲区
- 1、空缓冲队列
- 2、输入队列
- 3、输出队列
- 四个缓冲区
- 收容输入数据的工作缓冲区
- 提取输入数据的工作缓冲区
- 收容输出的工作缓冲区
- 提取输出数据的工作缓冲区
- 多缓冲
- 1、引入缓冲区的目的
- 常用设备分配技术
- 1、根据设备的使用性质
- 独占设备
- 不能共享的设备
- 共享设备
- 可由若干个进程同时共享的设备。如磁盘机
- 虚拟设备
- 是利用某些技术把独占设备改造成可由多个进程共享的设备
- 独占设备
- 对三种设备采用三种分配技术
- 独占分配技术
- 共享分配技术
- 虚拟分配技术
- 利用共享设备去模拟独占设备，从而使独占设备成为可共享的、快熟I/O的设备，实现虚拟分配的最有名的技术是SPOOLing技术，称为假脱机操作
- 分配因素
- 固有性质
- I/O设备分配算法
- I/O设备安全性
- I/O设备独立性
- 什么是设备的独立性
- 应用程序独立于具体使用的物理设备
- 1、根据设备的使用性质
