操作系统笔记.pdf

1 1 操作系统的目标 作用和模型 1 计算机系统的组成 硬件系统 裸机 CPU 存储器 主存 辅存 I O I O 控制系统 软件系统 系统软件 系统软件 支援软件 应用软件 系统软件 管理计算机本身的操作 如操作系统 编译 支援软件 支援其他软件的编制和维护 如 接口软件 软件开发工具 应用软件 提供给用户进行解题 如 科学计算 事物 管理 2 计算机系统的构成方式 层次结构 硬件和软件 部分软件之间时一种层次结构关系 应用软件 支援软件 编辑软件编译软件 裸机 3 操作系统的地位 其他软件的支撑环境 4 操作系统的作用 用户角度 用户与计算机硬件系统之间接口 资源管理角度 计算机资源的管理者 处理机管理 存储器 管理 I O 设备 管理 文件管理 扩充机器 虚拟机 5 操作系统的目标 方便性 有效性 可扩充性 开放性 6 操作系统模型 整体式系统 无序模块法 存在程度很低的结构化 层次式系统 用户接口 对 OS 对象操纵和管理的软件集合 OS 对象 客户 服务器式系统 虚拟机系统 1 2 操作系统的发展过程 1 5 操作系统的进一步发展 推动操作系统发展的动力 不断提高计算机资源利用率的需要 方便用户 器件的不断更新换代 计算机体系结构的不断发展 1 无操作系统时代 2 单道批处理系统 自动性 顺序性 单道性 3 多道批处理系统 多道程序设计的概念 把一个以上的作业 程序 存放在主 存中 并且同时处于运行状态 共享处理机时间和外部设备等其 他资源的方法 多道程序设计的优点 举例说明 提高 CPU 的利用率 提高内存和 I O 设备的利用率 增加 系统吞吐量 多道批处理系统 介绍 多道批处理系统的特征 脱机操作 成批处理 多道性 无序性 调度性 多道批处理系统的优点 缺点 优点 资源利用率高 系统吞吐量大 缺点 平均周转时间长 无交互能力 周转时间定义 4 分时操作系统 产生原因 人机交互 共享主机 便于用户上机 实现关键 及时接收处理 实现方法 单道分时系统 多道分时系统 具有前台和后台 的分时系统 特征 多路性 独立性 及时性 交互性 5 实时操作系统 实时系统的引入 实时控制 实时信息处理 实时系统定义 实时 指对随机发生的外部时间做出及时的相应并对其进 行处理 所谓事件时指来自与计算机系统相连接的设备所提出 的服务要求和采集数据 实时系统 指系统能及时 或即时 相应外部事件的请求 在规定的时间内完成对该事件的处理 并控制所有实时任务协调 一致地运行 实时操作系统的主要特征 及时响应 高可靠性 专用性 少人工干预 实时任务类型 按任务执行时是否出现周期划分 周期性实时任务 非周 期性实时任务 根据对截止时间的要求划分 硬实时任务 软实时任务 实时系统与分时系统的比较 多路性 独立性 及时性 交互性 可靠性 6 通用操作系统 多道批处理 分时 实时的结合 UNIX 7 微机操作系统 8 多处理机操作系统 多处理机系统的引入 增加系统的吞吐量 节省投资 提 高系统的可靠性 多处理机的类型 紧密耦合 松散耦合 多处理机操作系统的类型 非对称多处理模式 对称多处 理模式 9 网络操作系统 计算机网络类型 按网络拓扑结构分类 星型网络 树型网络 总线型网络 网状型网络 按网络地理范围分类 广域网 局域网 网络操作系统模式 客户 服务器 C S 模式 对等模式 网络操作系统的功能 网络通信 资源管理 网络服务 网络管理 互操作能力 10 分布式操作系统 分布式系统 分布式操作系统和网络操作系统的比较 分布性 并行性 透明性 共享性 健壮性 1 3 操作系统的特征和服务 1 操作系统的特征 并发 共享 虚拟 异步性 并发性 并行性的概念 共享有互斥式共享 同时访问方式 2 操作系统的服务 公共服务类型 程序执行 I O 操作 文件系统操纵 通 信 差错检测 系统调用 作用 类型 进程控制类系统调用 文件操纵类系统调用 设备 管理类系统调用 通信用系统调用 信息维护 1 4 操作系统的功能 1 存储器管理的功能 内存分配 内存保护 地址映射 逻辑地址 物理地址的定义 2 处理机管理的功能 进程控制 进程同步 进程通信 调度 3 设备管理的功能 缓冲管理 设备分配 设备处理 设备独立性和虚拟设备 4 文件管理的功能 文件存储空间的管理 目录管理 文件的读 写管理和存取 控制 5 用户接口 命令接口 程序接口 图形接口 2 1 前驱图和程序执行 1 前驱图的定义 略 2 程序顺序执行 程序顺序执行概念 程序顺序执行的特征 顺序性 封闭性 可再现性 封闭性 所谓封闭性是指程序一旦开始执行 其执行过程 不受任何外界因素影响 顺序性 当程序在处理机上执行时 处理机的操作严格按 照程序所规定的顺序执行 确定性 其程序执行结果与执行速度 时间的无关性 可再现性 指程序对一组数据的重复执行必得到相同的结 果 3 程序并发执行 程序并发执行 使一个程序分成若干个可同时执行的程序模块的方法成为 并发程序设计 能够并发执行的程序成为并发程序 程序顺序执行的特征 间断性 失去封闭性 不可再现性 举例说明 4 并发程序与顺序程序的比较 顺序程序并发程序 执行过程顺序执行并发执行 程序与执行对应一一对应一个程序可对应多个 执行 封闭性独占资源 具有封闭 性 共享资源 不具有封闭 性 确定性具有无 可再现性具有无 程序间关系无有间接制约或直接制 约关系 5 程序并发执行的条件 保持可再现性 两段程序间无共享变量或对共享变量仅有读操作 2 2 进程的描述 1 进程的引入和定义 进程引入的原因 进程 操作系统中最基本 最重要的概念 多道程序设计出现以后 为了刻划系统内部出现的情况 描 述系统内部各作业的活动规律引入的 多到系统的特点 并行性 程序间的制约 动态特征 程序是静态的 不能并行 进程的定义 通用定义 举例解释 进程的特征 动态性 并发性 独立性 异步性 结构特征 进程和程序的区别与联系 区别 进程是一动态概念 而程序则是一静态概念 程序 是指令的有序集合 永远存在 进程强调的是执行 是程序在数 据集上的一次执行 有创建有撤销 存在是暂时的 进程具有并发性 而程序没有 进程是竞争计算机资源的基本单位 程序不是 联系 进程是程序在数据集上的一次执行 一个程序可对应多个进程 一个进程可包括多个程 序 2 进程的基本状态 进程的三种基本状态 引入状态的原因 等待态 就绪态 运行态 进程的状态不断发生变化 但任何时候都要处于某种状态 新状态和终止状态 进程的状态转换 进程状态转换图 3 进程的挂起状态 挂起状态的引入 终端用户的需要 父进程的需要 操作系统的需要 对换的 需要 负荷调节的需要 进程的状态转换 进程状态转换图 4 进程控制块 PCB PCB 是用以记录进程有关信息的一块主存 由系统建立 PCB 的作用 操作系统调度进程的主要数据依据 记录进程的有关信息 供系统对进程进行控制 标志进程存在 PCB 中的信息 进程标识信息 处理机状态信息 进程调度信息 进程控制信息 PCB 组织方式 链接方式 索引方式 一般就绪队列一个 等待队列按等待原因分为多个 2 3 进程控制 区分特权指令的原因 避免用户使用而使系统陷于混乱 方便用户 不必了解硬件细节 特权指令 只能由操作系统内核部分使用 不允许用户直接 使用的指令 如 I O 指令 置终端屏蔽指令 清内存 建存储 保护 设置时钟指令 非特权指令 所有程序均可直接使用 引入系统态和核心态的原因 系统态 核心态 特态 管态 执行全部指令 用户态 常态 目态 执行非特权指令 1 操作系统内核 内核的引入原因及定义 内核功能 支撑功能 中断处理 时钟管理 原语操作 原语的定义 资源管理功能 进程管理 存储管理 设备管理 2 进程的创建 系统创建 父进程创建 进程图 引起进程创建的事件 用户登录 作业调度 提供服务 应用请求 进程的创建流程 申请空白 PCB 块 为新进程分配资源 初始化进程控制块 将进程插入就绪队列 3 进程的终止 引起进程终止的事件 正常结束 异常结束 外界的干预 进程的终止流程 查找对应进程控制块 终止该进程及子孙进程 释放资源 释放进程控制块 若该进成为执行态 要进行进程调度 4 进程的阻塞和唤醒 进程的阻塞和唤醒的事件 请求系统服务 启动某种操作 新数据味道大 无新工作可 做 进程的阻塞流程 进程自己阻塞自己 保存当前 CPU 现场 置该进程为阻塞状态 被阻塞进程进 入就绪队列 进程调度 进程的唤醒流程 唤醒方法 其他进程唤醒 由系统进程唤醒或由事件发生 进程唤醒 从等待队列中摘下被唤醒进程的进程控制块 将进程置成就 绪态 被唤醒进程进程控制块送入就绪队列 进程调度或返回 5 进程的挂起和激活 进程的挂起过程 进程的激活过程 2 4 线程的基本概念 1 线程的引入 2 线程与进程的比较 调度 并发性 拥有资源 系统开销 3 用户线程和内核支持线程 线程的调度与切换速度 系统调用 线程的执行时间 3 1进程同步的概念 进程之间的关系 资源共享关系 相互合作关系 1 临界资源 临界资源的定义 2 临界区 临界区的定义 临界区进入和退出的方法 同步机制应该遵循的准则 空闲让进 忙则等待 有限等待 让权等待 3 利用软件方法解决进程互斥问题 算法 1 算法 2 算法 3 算法 4 4 利用硬件方法解决进程互斥问题 利用 Test and Set 指令实现互斥 TS 指令 TS lock Int lock int t t lock lock 1 return t 入口 while TS 出口 lock 0 利用 Swap 指令实现互斥 Swap 指令 Swap a b Int a a a a b intt t a a b b t 入口 key 1 do swap while key 0 出口 lock 0 3 2信号量机制 1 整型信号量机制 整形信号量 利用信号量互斥 利用信号量描述前驱关系 2 记录型信号量机制 3 信号量集机制 AND 信号量集机制 一般信号量集机制 3 3经典进程同步问题 1 生产者消费者问题 2 读者写者问题 3 哲学家进餐问题 3 4管程机制 1 管程的引入 2 管程的基本概念 管程的定义 条件变量 3 利用管程解决生产者 消费者问题 4 利用管程解决哲学家进餐问题 5 利用管程解决读者写者问题 孙钟秀 3 5进程通信 进程通信的定义 进程间的信息交换 进程通信 低级进程通信 少量的信息交换 没有专门的通信机制 如信号量机制 缺点 效率低 通信对用户不透明 高级进程通信 大量的信息交换 有专门的通信机制 1 进程的通信类型 共享存储器系统 基于共享数据结构的通信方式 基于共享存储区的通信方式 消息传递系统 message 为传递单位 直接通信方式和间接通信方式 信箱方式 管道通信 2 直接通信和间接通信方式 直接通信方式 间接通信方式 3 消息传递系统的几个问题 通信链路 消息的格式 进程的同步方式 发送进程阻塞 接收进程阻塞 发送进程不阻塞 接收进程阻塞 发送进程和接收进程均不阻塞 4 消息缓冲队列机制 消息缓冲队列机制中的数据结构 发送原语 接收原语 4 1 调度的类型和模型 4 1 1 调度类型 一 高级调度 1 接纳多少个作业 2 接纳哪些作业 二 低级调度 1 非抢占方式 2 抢占方式 三 中级调度 4 1 2 调度队列模型 一 仅有进程调度的调度队列模型 二 具有高级和低级调度的调度队列模型 三 同时具有三级调度的调度队列模型 4 1 3 选择调度方式和算法的若干准则 一 面向用户的准则 1 周转时间短 2 响应时间快 3 截止时间的保证 4 优先权准则 二 面向系统的准则 1 系统吞吐量高 2 处理机利用率好 3 各类资源的平衡利用 4 2 调度算法 概念 根据系统的资源分配策略所规定的资源分配算法 4 2 1 先来先服务调度算法 FCFS 一 调度算法 二 FCFS 实例 作业情 况 调度算 法 进程 名 ABCDE平均 到达 时间 01234 服务43524 时间 FCFS a 完成 时间 47121418 周转 时间 461011149 带权 周转 时间 1225 53 52 8 SJF b 完成 时间 4918613 周转 时间 4816398 带权 周转 时间 12 673 11 52 252 1 4 2 2 短作业 进程 优先调度算法 4 2 3 时间片轮转调度算法 一 调度算法 二 时间片大小的确定 1 系统对响应时间的要求 2 就绪队列中进程的数目 3 系统的处理能力 4 2 4 优先权调度算法 一 优先权调度算法的类型 1 非抢占式优先权算法 主要用于批处理系统中 也可用于某些对实时性要求不严的实时 系统中 2 抢占式优先权调度算法 这种方式的优先权调度算法 能更好地满足紧迫作业的要求 常 用于要求比较严格的实时系统中 以及对性能要求较高的批处理 和分时系统中 二 优先权的类型 1 静态优先权 在创建进程时确定 且优先权在整个进程的生命周期内不会发生 变化 确定优先权的依据有 1 进程类型 2 进程对资源的需求 3 根据用户要求 2 动态优先权 在创建进程时所赋予的优先权 可以随进程的推进而改变 以便 获得更好的调度性能 4 2 5 高响应比优先调度算法 4 2 6 多级队列调度 4 2 7 多级反馈队列调度算法 一 调度算法 二 多绍反馈队列调度算法的牲能 4 3实时系统中的调度 4 3 1对实时系统的要求 1 提供必要的调度信息 1 就绪时间 2 开始截止时间和完成截止时间 3 处 理时间 4 资源要求 5 优先级 2 调度方式 在实时控制系统中 广泛采用抢占调度方式 3 具有快速响应外部中断的能力 4 快速任务分派 4 3 2实时调度算法 1 时间片轮转调度算法 2 非抢占优先权调度算法 3 基于时钟中断抢占的优先权调度算法 4 立即抢占的优先权调度 4 3 3实时调度实例 一 具有开始截止时间的非周期实时任务的调度 在事前能知道各实时任务的开始截止时间 且对调度时延要求不 太严格的情况下 系统采用最早截止时间优先的非剥夺调度策 略 任务 1 2 3 4 的调度 二 具有完成截止时间的周期性实时任务的调度 A 每 20ms 执行一次 执行时间为 10ms B 每 50ms 执行一次 执行时间为 25ms 4 4多处理机调度 4 4 1进程调度 一 同构型多处理机系统中的进程调度 1 静态分配 Static Assignment 2 动态分配 Dynamic Assignment 3 自调度 Self Scheduling 二 异构型多处理机系统中的进程调度 4 4 2自调度 1 自调度方式 系统中有一个公共的线程或进程的就绪队列 所有的处理机在空闲时 都可自己从该队列中取出一个进程或线 程运行 2 成组调度 这时由系统将一组相关的进程或线程 同时分 配到 组处理机上运行 进程或线程与处理机一 对应 3 专用处理机分配方式 它是将同属于一个应用程序的一组 线程 分配到一组处理机上 在应用程序末结束前 处理机专用 于处理这组线程 4 4 3 成组调度 1 面向所有的应用程序平均分配处理机时间 2 面向所有的线程平均分配处理机时间 4 4 4 专用处理机分配 把这种调度方式用于并发程度相当高的多处理机环境 是根据下 述一些理由 1 在具有数十个乃至数百个处理机的高度并行的系统中 单 个处理机的利用率已远不像在单机系统中那么重要 2 可以避免了进程或线程的切换 从而可大大地加速程序的 完成 根据实践证明 在同时加工的应用程序中 其线程数的总和不应 超过系统中处理机的数目 4 6死锁的基本概念 所谓死锁 Deadlock 是指多个进程因竞争资源而造成的一 种僵局 若无外力作用 这些进程都将永远不能再向前推进 4 6 1产生死锁的原因 产生死锁的原因可归结为两点 1 竞争资源 2 进程推进顺序非法 一 竞争资源引起死锁 1 可剥夺和非剥夺性资源 2 竞争非剥夺促资源 3 竞争临时性资源 二 进程推进顺序不当引起死锁 1 进程推进顺序合法 2 进程推进顺序非法 4 6 2产生死锁的必要条件 1 互斥条件 2 请求和保持条件 3 不剥夺条件 4 环路等待条件 4 6 3处理死锁的基本方法 1 预防死锁 2 避免死锁 3 检测死锁 4 解除死钡 死锁的检测和解除措施 有可能使系统获得较好的资源利用宰相 系统吞吐量 但在实现上难度也最大 4 7 死锁的预防和避免 4 7 1死锁的预防 一 摒弃 请求和保持 条件 二 据弃 不剥夺 条件 三 摒弃 环路等待 条件 4 7 2 系统的安全状态 一 安全状态 所谓安全状态 是指系统能按某种顺序如 称 序列为安全序列 来为每个进程分配其所 需资源 直至最大需求 使每个进程都可顺序完成 若系统不存 在这样一个安全序列 则称系统处于不安全状态 虽然并非所有不安全状态都是死锁状态 但当系统进入不安全状 态后 便可能进而进入死锁状态 反之 只要系统处于安全状态 系统便可避免进入死锁状态 因此 避免死锁的实质在于 如何 使系统不进入不安全状态 二 安全状态之例 我们通过一个例子来说明安全性 假定系统有三个进程 P1 P2 和 P3 共有 12 台磁带 机 进程 P1 总共要求 10 台磁带机 P2 和 P3 分别要求 4 台和 9 台 设在 T0 时刻 进程 Pl P2 和 P3 已分别获得 5 台 2 台和 2 台 尚有 3 台空闲未分 如 下表所示 进程最大需求已分配可用 P11053 P242 P392 三 由安全状态向不安全状态的转换 如果不按照安全序列分配资源 则系统可能会由安全状态进入不 安全状态 4 7 3利用银行家算法避免死锁 一 银行家算法中的数据结构 1 可利用资源向量 Available 它是一个含有 m 个元素的数组 其中的每一个元素代表一类可 利用的资源数目 其初始值是系统中所配置的该类全部可用资源 数目 其数值随该类资源的分配和回收而动态地改变 2 最大需求短阵 Max 这是 个 n m 的矩阵 它定义了系统中 n 个进程中的每一个 进程对 m 类资源的最大需求 如果 Max i j k 表示进程 i 需要Rj类资源的最大数目为 k 3 分配短阵 Allocation 这是一个 n m 的矩阵 它定义了系统中每一类资源当前已分配 给每个进程的资源数 如果 Allocation i j k 表示进程 i 当前 已分得Rj类资源的数目为 k 4 需求矩阵 Need 它是一个 n m 的矩阵 用以表示每一个进程尚需的各类资源数 如果 表示进程 i 还需要Rj类资源 k 个 方能完成其任务 上述三个矩阵间存在下述关系 二 银行家算法 设 Requesti是进程 Pi的请求向量 如果 Requesti j k 表示 进程只需要 k 个Rj类型的资源 当 Pi发出资源请求后 系统按 下述步骤进行检查 1 如果 则转向步骤 2 否则 认为出错 因为它所需要的 资源数已超过它所宣布的最大值 2 如果 则转向步骤 3 否则 表示系统中尚无足够的资源 Pi必须等待 3 系统试探把要求的资源分配给进程 Pi 并修改下面数据结 构中的数值 4 系统执行安全性算法 检查此次资源分配后 系统是否处 于安全状态 若安全 才正式将资源分配给进程 Pi 以完成本次 分配 否则 将试探分配作废 恢复原来的资源分配状态 让进 程 Pi等待 三 安全性算法 系统所执行的安全性算法可描述如下 1 设置两个向量 工作向量 Work 它表示系统可提供给进程继续运行所需要 的各类资源数目 它含有 m 个元素 执行安全算法开始时 Work Available Finish 它表示系统是否有足够的资源分配给进程 使之运 行完成 开始时先做 当有足够资源分配给进程时 令 2 从进程集合中找到一个能满足下述条件的进程 如找到 执行步骤 3 否则 执行步骤 4 3 当进程 Pi 获得资源后 可顺利执行 直至完成 并释放出 分配给它的资源 故应执行 go to step 2 4 如果所有进程的 则表示系统处于安全状态 否则 系统 处于不安全状态 四 银行家算法之例 假定系统中有五个进程 P0 P1 P2 P3 P4 和三种类型的 资源 A B C 每一种资源的数量分别为 10 5 7 在 T0 时 刻的资源分配情况如图 4 17 所示 4 8死锁的检测和解除 4 8 1 死锁的检测 当系统为进程分配资源时 若未采取任何限制性措施 则系统必 须提供检测和解除死锁的手段 为此 系统必须 1 保存有关资源的请求和分配信息 2 提供 种算法 以利用这些信息来检测系统是否已进入死 锁状态 一 资源分配图 Resource Allocation Graph 二 死锁定理 我们可以利用把资源分配图加以简化的方法 来检测系统处于 S 状态时 是否为死锁状态 简化方法如下 1 在资源分配图中 找出 个既不阻塞又非独立的进程结点 pi 在顺利情况下 pi可获得所需资源而继续执行 直至 运行完毕 再释放其所占有的全部资源 这相当于消去 pi 所有的请求边和分配边 使之成为孤立的结点 2 pi释放资源后 便可使 p2获得资源而继续运行 直到 p2 完成后又释放出它所占有的全部资源 3 在进行一系列的简化后 若能消去图中所有的边 使所有 进程都成为孤立结点 则称该图是可完全简化的 若不能 通过任何过程使该图完全简化 则称该图是不可完全简化 的 对于较复杂的资源分配图 可能有多个既末阻塞 又非孤立的进 程结点 有关文献已经证明不同的简化顺序 将得到相同的不可 简化图 同样可以证明 S 为死锁状态的充分条件是 当且仅省 S 状态的资源分配图是不可完全简化的 该充分条件称为死锁定 理 三 死锁检测中的数据结构 死锁检测中的数据结构 类似于银行家算法中的数据结构 1 可利用资源向量 Available 它表示了 m 类资源中每一类 资源的可用数目 2 把不占用资源的进程向量 Allocation 0 记人表 L 中 即 3 从进程集合中找到一个 的进程 做如下处理 将其资源分配图简化 释放出资源 增加工作向量 将它记入 L 表中 4 若不能把所有进程都记人 L 表中 则表明系统状态 S 的资 源分配图是不可完全简化的 因此 该系统状态将发生死锁 4 8 2 死锁的解除 当发现有进程死锁时 使当立即把它们从死锁状态中解脱出来 常采用的两种方法是 1 剥夺资源 2 撤消进程 一个付出最小代价的方法为树的宽度优先搜索算法 这种算法不 太实际 一个比较有效地方法为最短路径的优先策略搜索算法 5 1 程序的装入和链接 在多道程序环境下 程序要运行必须为之创建进程 而创建进 程的第一件事 就是要将程序和数据装入内存 如何将一个用户 源程序变为一个可在内存中执行的程序 通常要经过以下几步 1 编译 由编译程序 Compiler 将用户源代码编译成若干 个目标模块 Object Module 2 链接 由链接程序 Linker 将编译后形成的目标模块以 及它们所需要的库函数 链接在一起 形成一个装入模块 Load Module 3 装入 由装入程序 Loader 将装入模块装入内存 5 1 1程序的装入 一 绝对装入方式 Absolute Loading Mode 二 可重定位装入方式 Relocatable Loading Mode 三 动态运行时装入方式 Dynamic Run Time Loading 5 1 2 程序的链接 一 静态链接 在将几个目标模块链接装配成一个装入模块时 需要解决以下两 个问题 1 对相对地址进行修改 2 变换外部调用符号 二 装入时动态链接 Load Time Dynamic Linking 装入时动态链接方式有以下优点 1 便于软件版本的修改和更新 2 便于实现目标模块共享 三 运行时动态链接 Run Time Dynamic Linking 5 2连续分配存储管理方式 连续分配是指为一个用户程序分配一个连续的内存空间 5 2 1 单一连续分配 这是最简单的一种存储管理方式 但只能用于单用户 单任务的 操作系统中 采用这种存储管理方式时 内存分为以下两个分区 1 系统区 2 用户区 5 2 2 固定分区分配 一 划分分区的方法 将内存空间划分为若干个固定大小的分区 可用下述两种方法 1 分区大小相等 2 分区大小不等 二 内存分配 分区使用表 表项包含有每个分区的起始地址 大小及状态 是否 已分配 5 2 3动态分区分配 动态分区分配是根据进程的实际需要 动态地为之分配连续的内 存空间 在实现可变分区分配存储管理方式时 必须解决下述三 个问题 1 分区分配中所用的数据结构 2 分区的分配算法 3 分区的分配和回收操作 分区分配中的数据结构 1 空闲分区表 2 空闲分区链 二 分区分配算法 1 首次适应算法 FF 2 循环首次适应算法 3 最佳适应算法 三 分区分配操作 在动态分区存储管理方式中 主要的操作是分配和回收内存 1 分配内存 2 回收内存 当进程运行完毕释放内存时 系统根据回收区的首址 从空闲区 链中找到相应的插入点 此时可能出现以下四种情况之一 1 回收区与插入点的前一个分区 F1 相邻接 2 回收分区与插入点的后一分区 F2 相邻接 3 回收区同时与插入点的前 后两个分区邻接 4 回收区既不与 F1 邻接 也不与 F2 邻接 5 2 4 动态重定位分区分配 一 紧凑 不能被利用的小分区称为 零头 或 碎片 通过移动 把多个分散的小分区拼接成大分区的方法被称为 拼 接 或 紧凑 二 动态重定位 三 动态重定位分区分配算法 5 5 5 5 3 3 3 3对换对换对换对换 5 3 1 多道程序环境下的对换 所谓 对换 是指把内存中暂不能运行的进程 或暂时不用的 程序和数据 换出到外存上 以腾出足够的内存空间 把已具备 运行条件的进程 或进程所需要的程序和数据 换入内存 对换 是提高内存利用率的有效措施 如果对换是以整个进程为单位 便称之为 整体对换 或 进程 对换 如果对换是以 页 或 段 为单位进行 则分别称之 为 页面对换 或 分段对换 又统称为 部分对换 5 3 2 对换空间的管理 在具有对换功能的 OS 中 通常把外存分为文件区和对换区 由于对对换区的分配 是采用连续分配方式 因而对对换区空间 的分配与回收 与动态分区方式时内存的分配与回收方法雷同 其分配算法可以是首次适应算法 循环首次适应算法和最佳适应 算法 具体的分配操作也与图 5 9 中的操作相同 对换区的回收 操作也可分为下述四种情况 即 1 回收区与插入点的前一分区 F1 相邻接 2 回收区与插人点的后一分区 F2 相邻接 3 回收区还同时与 F1 和 F2 二个分区相邻接 4 回收区的前 后没有与之相邻接的空闲分区 对这几种情况的处理方法也与动态分区分配时的方法相同 5 3 3 进程的换出与换入 一 进程的换出 1 选出被换出的进程 2 换出过程 二 进程的换入 5 5 5 5 4 4 4 4分页存储管理方式分页存储管理方式分页存储管理方式分页存储管理方式 5 4 1 分页存储管理的基本方法 一 页面和物理块 在分页存储管理方式中 将一个进程的逻辑地址空间分成若干个 大小相等的片 称为页面或页 相应地 内存空间也分成与页相 同大小的若干个存储块 或称为物理块或页框 frame 由于进 程的最后一页经常装不满一块 而形成不可利用的碎片 称为 页 内碎片 在分页存储管理方式中的地址结构如下 页号页内地址 3112 110 分页存储管理方式的地址结构 若给定一个逻辑地址空间中的地址为 A 页面的大小为 L 则页 号 P 和页内地址 d 可按下式求得d A mod L 其中 INT 是整除函数 mod 是取余函数 例如 其系统的页面大小为 1KB 设 A 2170 H 则由上式可以 求得 P 2 d 122 二 页表 页号物理块号 010 125 234 354 三 页面大小的选择 在确定地址结构时 若选择的页面较小 一方面可使内存碎片小 并减少了内存碎片的总空间 有利于提高内存利用串 但另一方 面 也会使每个进程要求较多的页面 从而导致页表过长 占用 大量内存 此外 还会降低页面换进换出的效率 若选择的页面 较大 虽然可减少页表长度 提高换进换出效率 但却又会使页 内碎片增大 因此 页面的大小应选得适中 通常页面的大小是 2 的幂 且常在 29一 212之间 即在 512 字节一 4KB 之间 5 4 2 地址变换机构 一 基本的地址变换机构 二 具有快表的地址变换机构 5 4 3两级和多级页表 一 两级页表 P1P2 外层页号外层页内地 址页内地址 二 多级页表结构 5 4 4 反置页表 反置页表的地址结构 pidpd 5 5 5 5 5 5 5 5 分段存储管理分段存储管理分段存储管理分段存储管理 5 5 1 分段存储管理方式的引入 1 方便编程 2 分段共享 3 分段保护 4 动态链接 5 动态增长 5 5 2 分段系统的基本原理 一 分段 二 段表 三 地址变换机构 四 分页和分段的主要区别 1 页是信息的物理单位 段是信息的逻辑单位 2 页的大小固定且由系统确定 段的长度不固定 决定于用户所 编写的程序 3 分页的作业地址空间是一维的 分段的作业地址空间是二维的 5 5 3 共享与保护 5 5 4 段页式存储管理方式 一 基本原理 二 地址变换过程 6 6 6 6 1 1 1 1虚拟存储器的基本概念虚拟存储器的基本概念虚拟存储器的基本概念虚拟存储器的基本概念 1 虚拟存储器的引入 虚拟存储器的设想 基本原理 当成需要运行时 不是讲它 的全部信息装入主存 而是将其中一部分装入主存 另外一部分 暂时留在辅存中 程序运行到不在主存的信息时再设法将它们装 入主存 保证程序的正常运行 局部性原理 程序中有些部分是彼此互斥的 不是每次运行时都能执行到 程序执行的时间局部性 程序执行的空间局部性 虚拟存储器的定义 2 虚拟存储器的实现方式 分页请求系统 请求分段系统 3 虚拟存储器的特征 离散性 多次性 对换性 虚拟性 4 实现虚拟存储器必须解决的问题 5 虚拟存储器并非无限大 限制条件有 外部存储器大小 指令中地址场长度的限制 6 2请求页式存储管理方式 1 请求分页中的硬件支持 页表机制 缺页中断机构 地址变换机构 2 页面分配 最小物理块数 页面分配和置换策略 固定分配局部置换 可变分配全局置换 可变分配局部置换 分配算法 平均分配算法 按比例分配算法 考虑优先权的分配算法 3 页面调入策略 何时调入页面 预掉页策略 请求调页策略 从何调入页面 页面调入过程 6 3页面置换算法 抖动现象 1 最佳置换算法 理想置换算法 算法 淘汰永不使用的或是在最长时间内不再被访问的页 无实现价值 作为其它算法的衡量标准 2 先进现出置换算法 算法 淘汰最先进出主存的页 性能差 有异常现象 belady 现象 举例 设进程有 5 页 访问顺序 1 2 3 4 1 2 5 1 2 3 4 5 分 3 块主存块和 4 块主存块时 3 最近最久未使用 LRU 算法 算法 淘汰最近最久未使用的页 硬件支持 实现方法 寄存器 栈 特点 软件实现 系统 非生产性 开销过大 硬件实现 增大成本 4 Clock 置换算法 LRU 算法的近似实现 简单的 Clock 置换算法 改进型 Clock 置换算法 5 最少使用 LFU 置换算法 淘汰最近使用次数最少的页 6 页面缓冲置换算法 6 4请求分页系统的性能分析 1 缺页中断率对有效访问时间的影响 影响缺页中断率的因素 分配给程序的主存块数 页面的大小 程序本身的编制方法 页面置换算法 2 工作集 3 抖动产生的原因和预防方法 抖动产生的原因 抖动的预防 采取局部置换策略 在 CPU 调度程序中引入工作集算法 L S 准则 挂起若干进程 6 5请求分段存储管理方式 1 请求分段中的硬件支持 段表机制 缺段中断机构 地址变换机构 2 分段共享与保护 共享段 共享进程计数 存取控制字段 段号 共享段的分配与回收 分段保护 越界检查 存取控制检查 环保护机构 7 1I O 系统组成 学生自行阅读 7 1 1 I O 系统的结构 一 微型机 I O 系统 总线 I O 系统结构 二 主机 I O 系统 通道 I O 系统结构 7 1 2 I O 设备 一 I O 设备的类型 1 按传输速率分 低速设备 几个 数百个 B S 中速设备 数 K 数十 KB S 高速设备 数百 K 数 MB S 2 按信息交换的单位分类 块设备 用于存储信息 信息的存取以数据块为单位 特征 传输速率较高 可寻址 采用 DMA 方式 字符设备 用于数据的输入和输出 基本单位是字符 特征 传输速率较低 不可寻址 采用中断驱动方式 3 按设备的共享属性分类 独占设备 一段时间内只允许一个用户 进程 访问的设备 共享设备 一段时间内允许多个进程同时访问的设备 虚拟设备 通过虚拟技术将一台独占设备变换为若干台逻辑设 备 二 设备与控制器之间的接口 数据信号 控制信号 状态信号 7 1 3 设备控制器 一 设备控制器的功能 1 接收和识别命令 2 数据交换 3 设备状态的了解和报告 二 设备控制器的组成 1 设备控制器与处理机的接口 2 设备控制器与设备的接口 3 I O 逻辑 7 1 4 I O 通道 一 通道设备的引入 二 通道类型 1 字节多路通道 Byte Multiplexor Channal 2 数组选择通道 Block Selector Channal 3 数组多路通道 三 瓶颈 问题 7 2I O 控制方式 学生自行阅读 着重介绍通道方式 一 程序 I O 方式 二 中断驱动 I O 控制 三 直接存储器访问 DMA 控制方式 1 DMA 控制方式的引入 2 DMA 控制器的组成 命令 状态寄存器 CR 内存地址寄存器 MAR 数据寄存器 DR 数据计数器 DC 3 DMA 工作过程 四 I O 通道控制方式 1 I O 通道控制方式的引入 2 通道程序 7 3缓冲管理 1 缓冲的引入 缓和 CPU 和 I O 设备速度不匹配的矛盾 减少对 CPU 的中断频率 放宽对中断响应时间的限制 提高 CPU 和 I O 设备之间的并行性 2 单缓冲 3 双缓冲 4 循环缓冲 组成 多个缓冲区 多个指针 缓冲区的使用 Getbuf 过程 Releasebuf 过程 进程同步 Nexti 指针追上 Nextg 指针 Nextg 指针追上 Nexti 指针 5 缓冲池 缓冲池的组成 空缓冲队列 emq 输入队列 inq 输出队 列 outq Getbuf 过程和 Putbuf 过程 缓冲区的工作方式 收容输入工作方式 提取输出工作方 式 收容输出工作方式 提取输出工作方式 7 4 设备分配 1 设备分配中的数据结构 逻辑设备表 LUT 系统设备表 SDT 设备控制表 DCT 控制器控制表 COCT 通道控制表 CHCT 2 设备分配时应考虑的若干因素 考虑设备的固有属性 独享设备 共享设备 虚拟设备 设备分配算法 先来先服务 优先级高者优先 设备分配的安全性 安全分配方式 不安全分配方式 3 设备独立性 设备独立性 设备独立性概念 应用程序独立于具体使用的物理设备 设备独立性优点 设备分配时的灵活性 易于实现 I O 重定向 设备独立性软件 完成功能 执行所有设备的公有操作 向用户层 或文件层 软件提供统一的接口 逻辑设备名到物理设备名映射的实现 逻辑设备表 LUT LUT 的设置问题 整个系统设置一张 LUT 每个用户设置一张 LUT 4 独占设备的分配程序 基本的设备分配程序 分配设备 分配控制器 分配通道 设备分配程序的改进 增加设备的独立性 考虑多通路情况 5 SPOOLING 技术 什么是 SPOOLING Simultaneous Peripheral Operations On Line 假脱机操作 SPOOLING 系统的组成 输入井和输出井 输入缓冲区和输出缓冲区 输入进程和输出 进程 共享打印机 SPOOLING 系统的特点 提高了 I O 速度 将独占设备改造为共享设备 实现了虚拟设 备功能 7 5设备处理 1 设备驱动程序的功能和特点 设备驱动程序的功能 设备处理方式 设备驱动程序的特点 2 设备驱动程序的处理过程 将抽象要求转换为具体要求 检查 I O 请求的合法性 读出和检查设备的状态 传送必要的参数 方式的设置 启动 I O 设备 3 中断处理程序的处理过程 唤醒被阻塞的驱动程序进程 保护被中断进程的 CPU 环境 分析中断的原因 转入相应的设备中断处理程序 进行中断处理 恢复被中断进程的现场 8 1文件和文件系统 1 文件 记录和数据项 数据项 基本数据项 组合数据项 记录 是一组相关数据项的集合 用于描述一个对象某方 面的属性 文件 是具有文件名的一组相关信息的集合 可分为有结 构文件和无结构文件两种 文件属性 类型 长度 物理位置 存取控制 建 立时间 2 文件类型 主要看逻辑结构和物理结构 按用途分类 系统文件 用户文件 库文件 按文件中的数据形式分类 源文件 目标文件 可执行文件 按存取控制属性分类 只执行文件 只读文件 读写文件 按文件的逻辑结构分类 有结构文件 无结构文件 按文件的物理结构分类 顺序文件 链接文件 索引文件 3 文件系统的模型 层次模型 对象及其属性说明 文件 目录 磁盘 磁带 存储空间 对对象操纵和管理的软件集合 I O 控制层 基本文件系 统 基本 I O 管理程序 逻辑文件系统 文件系统的接口 命令接口 程序接口 4 文件操作 对记录的操作 检索所有记录 检索单个记录 插入一个 记录 修改一个记录 删除一个记录 对文件的操作 创建文件 删除文件 读文件 写文件 截断文件 设置文件的读 写位置 8 2文件的逻辑结构 文件的逻辑结构 又称文件组织 文件的物理结构 又称文件的存储结构 对文件的逻辑结构的要求 提高检索效率 便于修改 降低文件 存储费用 1 文件逻辑结构的类型 有结构文件 记录式文件 定长记录 变长记录 顺序文件 索引文件 索引顺序文件 无结构文件 流式文件 2 顺序文件 1 逻辑记录的排序 串结构 顺序结构 2 对顺序文件的读或写操作 3 顺序文件的优缺点 3 索引文件 4 索引顺序文件 8 3目录管理 对目录管理的要求 实现按名存取 提高对目录的检索速度 文件的共享 允许文 件重名 1 文件控制块和索引结点 文件控制块 FCB 基本信息类 存取控制信息类 使用信息类 索引结点 索引结点的引入 磁盘索引结点 内存索引结点 2 单级目录结构 缺点 查找速度慢 不允许重名 不便于实现共享 3 两级目录结构 优点 提高了检索目录的速度 在不同的用户目录中 可以使 用相同的文件名 不同用 户可以通过不同文件名 来访问系统中的同一个共享文 件 4 树型目录结构 树型目录 路径名 当前目录 增加和删除目录 5 目录查询技术 线性检索技术 顺序检索法 Hash 检索技术 8 4文件共享 1 早期实现文件共享的办法 绕弯路法 连访法 利用基本文件目录实现文件共享 2 基于索引结点的共享方式 3 利用符号链实现文件共享 8 5文件保护 影响文件安全性的主要因素有 人为因素 系统因素 自然因素 通过存取控制机制来防止人为因素所造成的文件不安全性 通过系统容错技术来防止系统部分故障所造成的文件不安全性 通过 后备系统 来防止由自然因素所造成的不安全性 1 保护域 静态联系 动态联系 2 访问矩阵 3 访问矩阵的修改 拷贝权 所有权 控制权 4 访问矩阵的实现 访问控制表 访问权限表 5 分级安全管理 系统级安全管理 用户级安全管理 目录级安全管理 文件及安全管理 9 1磁盘 I O 提高磁盘 I O 速度的主要途径 选择性能好的磁盘 采用好的磁盘调度算法 设置磁盘高速缓冲区 1 磁盘性能简述 数据组织 标识符字段 数据字段 磁盘类型 固定头磁盘 每条磁道有一个读 写磁头 移动头磁盘 每一个盘面仅配有一个磁头 磁盘访问时间 寻道时间 把磁头从当前位置移动到指定磁道上所经历的时间 旋转延迟时间 指定扇区移动到磁头下面所经历的时间 传输时间 把数据从磁盘读出 或向磁盘写入数据所经历的时 间 2 早期的磁盘调度算法 先来先服务 根据进程访问磁盘的时间顺序先来先服务 优点 公平 简单 缺点 效率低 最短寻道时间优先 总是选择请求对列中距磁头当前距离最近的请求为之服务 缺点 新请求不断到达 磁头往往滞留在中央柱面 致使远离 中央的柱面的访问无限延长 饿死 现象 各种扫描算法 扫描算法 SCAN 进程 饥饿 现象 总是选择请求对列中沿移动臂移动方向上距磁头当前距离最 近的请求为之服务 循环扫描算法 CSCAN N Step SCAN 调度算法 N Step SCAN 调度算法 FSCAN 调度算法 9 2外存分配方法 1 连续分配 优点 顺序访问容易 顺序访问速度快 缺点 要求有连续的存储空间 必须事先知道文件的长度 2 链接分配 隐式链接 在文件目录的每个目录项中含有指向链接文件第一和 最后一个盘块的指针 显式链接 把用于链接文件各物理块的指针 显式的存放在内存 的一张链接表中 3 索引分配 单级索引分配 多级索引分配 混合分配方式 直接地址 一次间接地址 多次间接地址 9 3空闲存储空间的管理 1 空闲表法 2 空闲链表法 空闲盘块链 空闲盘区链 3 位示图法 位示图 盘块的分配 盘块的回收 4 成组链接法 空闲盘块的组织 空闲盘块的分配与回收 9 4磁盘容错技术 磁盘容错技术 SFT 1 低级磁盘容错技术 主要用于防止磁盘表面仿生缺陷所引 起的数据丢失 SFT 2 中级磁盘容错技术 主要用于防止磁盘驱动器和磁盘控制 器故障引起的系统不能正常工作 SFT 3 高级磁盘容错技术 1 第一级容错技术 双份目录和双份文件分配表 热修复重定向和写后读校验 热修复重定向 写后读校验 2 第二级容错技术 磁盘镜像 磁盘双工 3 廉价磁盘冗余阵列 并行交叉存取 RAID 分级 RAID 的优点 4 后备系统 后备系统的类型 磁带机 硬盘 光盘 拷贝方法 完全转储 增量转储 9 5文件系统的性能改善 提高对文件的访问速度 改进文件的目录结构以及检索目录的方法 来减少对文件的查 找时间 选择好的文件存储结构 以提高对文件的访问速度 提高磁盘 I O 速度 以提高对数据的传送速度 1 磁盘高速缓存 磁盘高速缓存的形式 指利用内存中的存储空间 来暂存 从磁盘中读出的一系列盘块中的信息 在内存中开辟一个单独的存储空间 把所有未利用的内存空间变为一个缓冲池 数据交付 将磁盘高速缓存中的数据传送给请求者进程 数据交付 指针交付 置换算法 周期性写回磁盘 2 优化数据的分布 优化物理块的分布 优化索引结点的分布 3 提高磁盘 I O 速度的其它方法 提前读 延迟写 虚拟盘 9 6 数据一致控制 1 事务 事务的定义 事务记录 恢复算法 2 检查点 检查点 恢复算法 3 并发控制 利用互斥锁来实现 顺序性 利用互斥锁和共享锁来实现顺序性 4 若干具体的数据的一致性问题 重复文件的一致性 盘块好的一致性的检查 链接数一致性检查 10 1 联机命令接口 联接命令接口 分时系统中 脱机命令