操作系统原理

全国计算机等级考试四级教程 操作系统原理 2017 版 第一章第一章 操作系统概论操作系统概论 1 计算机系统 计算机系统是一种可以按照用户的饿要求接收和存储信息 自动进行数据处理并输出结果信息的系统 计算机系 统包括硬件 子 系统 软件 子 系统 硬件系统是计算机系统赖以工作的实体 软件系统是保障计算机系统 按照用户指定的要求协商工作 计算机系统的资源也包括 硬件资源和软件资源 硬件系统 中央处理器 CPU 内存储器 外存储器 硬盘 磁带等 以及各种类型的输入 输出设备 键盘 鼠 标 显示器 打印机等 软件系统 各种程序和数据 2 操作系统 操作系统是集中了资源管理能力资源管理能力和控制程序执行能力控制程序执行能力的一种软件 能够有效地组织和管理计算机系统中的硬件及 软件资源 合理地组织计算机的工作流程 控制程序的执行 并向用户提供各种服务 使用户能够灵活 方便 有效地使用计算机 并使得整个计算机系统能够高效地运行 操作系统的任务 一是组织和管理计算机系统中的硬件及软件资源 二是想用户提供各种服务功能 一方面向程 序开发和设计人员提供高效的程序设计借口 另一方面想使用计算机系统的用户提供接口 使用户能够灵活 方 便 有效的使用计算机 3 操作系统的特征 1 并发性 计算机系统中同时存在若干个运行着的程序 并发性 体现在两个方面 用户程序与用户程序之间 用户程序与操作系统之间 宏观角度并发 微观角度不一定是并发的 例如在单处理器环境下 这些程序实际是 交替在中央处理器上运行 2 共享性 指操作系统程序与多个用户程序公用系统中的各种资源 一般有两种形式 互斥共享和同时共享 互斥共享是在一段特定的时间内只能由某一个用户程序使用 同时共享是在同一时间段内可以被多个程序同时访 问 3 随机性 操作系统的运行是在一种随机的环境下进行的 操作系统正处于什么状态是无法确切的知道的 4 操作系统的功能 操作系统的功能主要可以分为进程管理 处理器管理 存储管理 文件管理 作业管理和设备管理 1 进程管理 实质是对中央处理器进行管理 主要包括进程控制 进程同步 进程间通信 进程调度等 进程控制 主要任务就是创建进程 撤销结束的进程 控制进程运行时的各种状态转换 进程同步 多个进程的执行是并发的 他们以异步方式运行 OS 需要提供进程同步机制 以协调进程的执行 进程间通信 是协作的进程之间相互交换数据和消息的手段 调度 通常包括进程调度 线程调度 作业调度等 2 存储管理 管理计算机内存的资源 内存的分配与回收 当多个程序共享有限的内存资源时 如何为多个程序分配有限的内存空间 存储保护 存放在内存中的多个程序和数据应该彼此隔离 互不侵扰 内存扩充 将内存和外存结合起来管理 为用户提 供一个比实际内存大得多的虚拟存储器 3 文件管理 在计算机系统中的信息资源是以文件的形式存放在外存储器上 文件管理的任务是有效地支持文 件操作 解决文件的共享 保密和保护问题 使用户方便 安全地访问文件 4 设备管理 指除了 CPU 和内存以外的所有输入 输出设备的管理 5 用户接口 从用户的观点来看 操作系统是用户与计算机系统之间的接口 5 操作系统分类 按照用户界面的使用环境和功能特征的不同 一般可以吧操作系统分为三种基本类型 批处理操作系统 分时操 作系统 实时操作系统 只有又出现了许多类型的 OS 如个人操作系统 网络操作系统 分布式操作系统 嵌入 式操作系统等 1 批处理操作系统 工作方式 用户将作业交给系统操作员 系统操作员在受到后 并不立即将作业输入计算机 而是在受到一定数 量的用户作业之后 组成一批作业 再把这批作业输入到计算机中 这批作业可以在系统中形成连续的 自动转 接的作业流 2 分时系统 用户通过终端交互式地向系统提出命令请求 系统接收用户的命令之后 采用时间片轮转时间片轮转方式处理服务请求 并 通过交互方式在终端上向用户显示结果 分时系统追求的目标是及时响应用户输入的交互命令 3 实时操作系统 Real Time Operating System RTOS 主要目标是在严格时间范围内 对外部请求作出反应 系统具有高度可靠性 需要具有实时时钟管理 过载防护 高可靠性能力 4 嵌入式操作系统 Embedded OS 嵌入式操作系统就是运行在嵌入式芯片环境中 对整个芯片以及它所操作 控制的各种部件装置等资源进行统一 协调 调度 指挥和控制的系统软件 5 个人计算机操作系统 Personal Computer OS 是一种单用户多任务的操作系统 6 网络操作系统 Network OS 基于计算机网络的操作系统 其目的是相互通信及资源共享 网络环境中的计算机不仅能够共享数据 资源及服 务 还能共享运算处理能力 7 分布式操作系统 Distributed OS 分布式操作系统是网络操作系统的更高级形式 在系统中所有的主机使用的是同一个操作系统 可以实现资源的 深度共享 对用户透明 具有自治性 各主机之间平等 不是主从关系 8 智能卡操作系统 6 操作系统结构 操作系统结构 是指操作系统各部分程序的存在方式及相互关系 1 整体式结构 模块组合结构 系统中的模块不是根据程序和数据本身的特性而是根据他们完成的功能划分功能划分的 模块独立性差 系统结构不清晰 模块组合合法的关键在于 接口 2 层次式结构 各层之间的模块只能是单向依赖或单向调用关系 3 微内核 客户机 服务器 结构 效率比较低 所有的用户进程只能通过微内核相互通信 网络操作系统与分布式操作系统在概念上的主要不同之处在于网络操作系 统可以构架与不同的操作系统之上 而分布式操作系统强调单一操作系统 对整个系统的管理和调度 第二章第二章 操作系统运行机制操作系统运行机制 1 中央处理器 CPU 的构成 一般的处理器处理器由运算器运算器 控制器控制器 一系列寄存器寄存器 高速缓存高速缓存构成 1 运算器实现任何指令中的算术和逻辑运算 是计算机计算的核心 2 控制器负责控制程序运行的流程 包括取指令 维护 CPU 状态 CPU 与内存交互等 3 寄存器是指令在 CPU 内部作出理的过程中暂存数据 地址及指令信息 寄存器 用户可见寄存器 数据 通用寄存器 主要用于算术逻辑指令和访存指令 地址寄存器 存储数据集指令的物理地址 线地址或者有效地址 条件码寄存器 保存 操作结果的各种标记位 控制和状态寄存器 程序计数器 记录将要取出的指令地址 指令寄存器 最近取出的指令 程序状态字 记录 的运行模式信息 通常包括 的工作状态代码 反映执行后结果特征的条件码 中断屏蔽吗 4 高速缓存处于高速缓存处于 CPU 和物理内存之间和物理内存之间 一般由内存管理单元 Memory Management Unit MMU 管理 它的访 问速度快于内存 低于寄存器 利用程序局部性原理使得高速指令处理和低速内存访问得以匹配 2 CPU 指令执行的基本过程 处理器先从存储器中每次读取一条指令 然后执行该条指令 这样的单条指令处理过程称为一个指令周期指令周期 指令 访问存储器指令 负责 与存储器之间的数据传送 指令 负责 与 设备间的数据传送和命令发送 算术逻辑指令 执行有关数据的算术和逻辑操作 控制转移指令 指定一个新的指令的知行起点 控制指令 修改 状态 改变 工作方式 3 CPU 的状态 管态 系统态 特权态 指操作系统管理程序运行的状态 特权级别高 目态 普通态 用户态 指用户程序运行时的状态 特权级别低 特权越高 可以运行的指令集合就越大 而且特权级别高的可运行指令集合包含低特权级的 目态到管态的转换 通过中断或异常目态到管态的转换 通过中断或异常 中断响应时交换中断向量 新的中断向量中的程序状态字 PSW 的 CPU 状态标志位为管态 管态到目态的转换 设置管态到目态的转换 设置 PSW 指令指令 4 存储器的层次结构 容量 速度 成本 寄存器 高速缓存 内存储器 硬盘存储器 磁带和光盘 从左向右 每比特的价格下降 容量增大 速度变慢 CPU 访问频率下降 提高存储系统性能的关键在于程序的存储访问局部性原理存储访问局部性原理 5 中断与异常 1 中断 异常的概念 中断是指 CPU 对系统中或者系统外发生的异步事件异步事件的响应 异步事件是指没有一定时序关系的随机发生的事件 引起中断的那些事件成为中断事件或中断源中断事件或中断源 中断源向处理器发出的请求信号称为中断请求中断请求 把处理中断事件的 程序称为中断处理程序中断处理程序 发生中断时正在执行的程序的暂停点称为中断断点中断断点 处理器暂停当前程序转而处理中断 的过程为中断响应中断响应 中断处理结束后恢复原来程序的执行称为中断返回中断返回 中断是由外部事件外部事件引起的 异常是由正在执行的指令正在执行的指令引起的 中断分类 时钟中断 内部计数器产生 中断 由 控制器产生 操作正常结束 异常 控制台中断 如系统操作员通过控制台发出命令 硬件故障中断 不能被屏蔽 程序状态字 中的中断屏蔽位 程序性中断 只能由操作系统完成 可以由程序自己完成 2 中断系统 中断系统分为两大组成部分 中断系统的硬件中断装置和软件中断处理程序 硬件中断装置负责捕获中断源发出 的中断请求 并以一定的方式响应中断源 然后将处理器的控制权交给待定的中断处理程序 中断处理程序针对 中断事件的性质执行相应的操作 整个中断信号的接收 响应和处理过程可以简要的归纳为 接收和响应中断 保护中断断点现场 分析中断向量 整个中断信号的接收 响应和处理过程可以简要的归纳为 接收和响应中断 保护中断断点现场 分析中断向量 调用中断处理程序 中断处理结束恢复现场 原有程序继续执行 调用中断处理程序 中断处理结束恢复现场 原有程序继续执行 6 系统调用 system call 系统调用 就是用户在程序中调用操作系统调用操作系统提供的一些子功能 可以被看做一个低级的过程 只能由汇编语言直只能由汇编语言直 接访问接访问 系统调用是操作系统提供给编程人员的唯一接口 但是对用户屏蔽了具体动作 只是提供有关功能 6 1 系统调用与一般过程调用的区别系统调用与一般过程调用的区别 1 运行在不同的系统状态 一般过程调用 其调用程序和被调用程序都运行在相同的状态 而系统调用中 调用程序运行在用户态 被调用 程序运行在系统态 2 状态的转换 一般过程调用不涉及系统状态的转换 而系统调用中 通常是通过软中断机制先由用户态转为系统态 在 OS 分析 后再转向相应的系统调用子程序 3 返回问题 一般过程调用在被调用过程执行完成后 将返回到调用过程继续执行 而在系统调用中 由于采用抢占式调度方 式 被调用程序执行完成后 系统将对所有要求运行的进程进行优先级的排名 若调用进程优先级比较低 则系 统把调用进程放入就绪队列 4 嵌套调用 系统调用同一般的过程调用一样 允许嵌套调用 但是在一般情况下 每个系统对嵌套调用的深度都有一定的限 制 系统调用可以分为以下几类 1 进程控制类 2 文件操作类 3 进程通信类 4 设备管理类 5 信息维护类 6 2 系统调用的处理过程系统调用的处理过程 系统调用的过程类似于硬件中断处理中的中断处理机构 在系统中 为控制系统调用服务的机构称为 陷入 陷入 trap 或 异常指令异常指令 访管指令访管指令 1 保护处理现场 2 去系统调用功能号并寻找系统调用的子程序入口 3 返回调用程序 恢复现场 在系统调用中 需要向系统子程序传递参数 实现用户程序和系统程序之间的参数传递方法有 1 由陷入指令自 带参数 2 通过有关通用寄存器 系统程序和用户程序都能访问 3 在内存中开辟专用堆栈区来传参 7 I O 技术 1 I O 结构 在早期的计算机系统中 外部设备的控制器通过 I O 硬件结构直接与 CPU 相连 2 通道 I O 处理机 通道独立于 CPU 专门负责数据 I O 传输工作 通道对外部设备实行统一管理 代替 CPU 对 I O 操作进行控制 从而使得 CPU 与外设可以并行工作 通道的工作原理 CPU 按照程序规定的顺序执行一条条指令 当执行到 启动外设 的指令时 按照指令中的参数 启动设备 并对该外设的控制权转移给通道 在外设工作结束后 产生一个 输入 出操作结束 中断事件 3 直接存储器访问 DMA Direct Memory Access DMA 通过系统总线中的一个独立控制单元 即 DMA 控制器 自动控制成块数据成块数据在内存和 I O 单元之间的传送 处理器只需要在整块数据开始传送和结束时关注一下即可 结束时也要给处理器发送一个中断 4 缓冲技术 缓存技术是用在外部设备与其他硬件之间的一种数据暂存技术 一般有两种途径 外设与外设的通信 外设与 CPU 的通信 采用缓冲技术的根本原因是 采用缓冲技术的根本原因是 CPU 处理数据的速度与设备传输数据速度不匹配处理数据的速度与设备传输数据速度不匹配 8 时钟 时钟中断 硬时钟 电路中的振荡器 软时钟 利用内存单元模拟时钟寄存器 绝对时钟 不受外界干扰 公元日历时间 相对时钟 时间间隔 第三章第三章 进程线程模型进程线程模型 1 多道程序 多道程序同时在系统中存在且并发执行并发执行 系统中的资源由几道程序共享 所谓并发执行 对于单 CPU 而言 这些 并发程序按给定的时间片交替的在处理机上执行 其执行时间是重叠的 对于多 CPU 而言 并发程序在各自测处 理机上运行 宏观同时进行 微观单宏观同时进行 微观单 CPU 顺序执行顺序执行 衡量系统效率的尺度是系统吞吐量系统吞吐量 即单位时间内系统所处理作业 程序 的道数 数量 多道程序设计环境的特点 1 独立性 每道程序逻辑独立 执行速度与其他程序无关 执行起止时间独立 2 随机性 程序和数据的输入与执行开始时间都是随机的 3 资源共享性 程序并发执行并发执行的特性 1 并发程序在执行期间具有相互制约关系 因为多道程序的并发执行总是伴随着资源共享和竞争 从而制约了其 他各道程序的执行速度 2 程序与计算不再一一对应 允许多个用户作业调用同一个共享程序段 3 并发程序执行结果不可再现 执行结果与其执行速度有关 是不确定的 2 进程模型的概念 进程由程序 数据和程序控制块 进程由程序 数据和程序控制块 PCB 组成 组成 系统进程 执行操作系统程序 完成 的某些功能 用户进程 运行用户程序 直接为用户服务 进程与程序的联系与区别 进程与程序的联系与区别 1 联系 程序是进程的组成部分 一个进程的运行目标是执行它所对应的程序 若没有程序 进程就是去了意义 从静态角度分析 进程是由程序 数据 进程控制块 从静态角度分析 进程是由程序 数据 进程控制块 PCB 组成 组成 2 区别 程序是静态的 进程是动态的 有生命周期 进程的特点 并发性 动态性 独立性 交往性 异步性进程的特点 并发性 动态性 独立性 交往性 异步性 3 三状态进程模型 1 运行状态 Running 2 就绪状态 Ready 已具备运行条件但是没有获得 CPU 3 等待状态 Writing 又称阻塞或封锁状态 4 五状态进程模型 1 运行状态 2 就绪状态 3 阻塞状态 Blocked 4 创建状态 创建状态 New 进程正在创建中 不能运行 5 结束状态 结束状态 Exit 回收除了进程控制快 PCB 之外的其他资源 5 七状态进程模块 五状态进程模型没有区分进程地址空间位于内存还是外存五状态进程模型没有区分进程地址空间位于内存还是外存 由于进程优先级的引入 一些低优先级进程可能等待 时间较长而被转至外存 1 运行状态 2 创建状态 New 进程正在创建中 不能运行 3 结束状态 Exit 回收除了进程控制快 PCB 之外的其他资源 4 就绪状态 就绪状态 Ready 进程在内存进程在内存且可以立即进入运行状态 5 阻塞状态 阻塞状态 Blocked 进程在内存进程在内存并等待某时间出现 6 就绪挂起状态 就绪挂起状态 Ready Suspend 进程在外存进程在外存 但只要进入内存即可运行 7 阻塞挂起状态 阻塞挂起状态 Blocked Suspend 进程在外存进程在外存 并等待某时间出现 挂起挂起 把一个进程从内存转到外存 6 进程控制块 PCB 的内容 调度信息 供进程调度使用 描述了进程当前的状况 现场信息 刻画了进程的运行情况 只记录那些可能会被其他进程更改的寄存器 的组织方式 线性方式 所有的 不分状态组织在一个连续表 表 中 索引方式 具有相同状态的进程分别设置各自的 索引表 就绪索引表 等待索引表 三个指针 指向就绪索引表的起始地址 等待索引表的起始地址 执行态 在 表中的地址 链接方式 具有相同状态进程的 通过链接字构成一个列队 就绪队列 可多个 等待队列 可以有多个 因不同原因等待 7 进程控制 进程控制的作用就是对进程在整个生命周期中各个状态之间的转换进行有效的控制进程控制的作用就是对进程在整个生命周期中各个状态之间的转换进行有效的控制 进程控制是通过原语原语来实现 的 原语原语通常有若干条指令组成 由一组程序模块组成而不是由进程 原语是不可分割的或不可中断原语是不可分割的或不可中断的程序 即原语 的执行必须是连续执行必须是连续的 原语必须在管态下进行管态下进行 并且常驻内存常驻内存 原语分类 创建原语 父进程使用创建原语创建子进程 主要是建立 撤销原语 撤销属于该进程的所有 子孙进程 阻塞原语 把进程由运行状态转换成阻塞状态 唤醒原语 将进程由等待状态转换为就绪状态 还有挂起进程 激活进程 改变优先级等作用的原语 8 进程与线程的区别与联系 1 引入进程的目的是为了使多个程序并发执行进程的目的是为了使多个程序并发执行 以改善资源利用率及提高系统效率 引入线程的目的是为了减少程序的并发执行时所付出的时间和空间开销线程的目的是为了减少程序的并发执行时所付出的时间和空间开销 是操作系统具有更好的并发性 因为进 程是一个资源拥有者 因而在进程的创建 撤销和切换中系统必须为之付出较大的时空开销 2 进程具有两个基本属性进程具有两个基本属性 进程是一个可拥有资源的独立单位可拥有资源的独立单位 一个可以独立调度和分派的基本单位以独立调度和分派的基本单位 线程线程是 进程中的一个实体 比进程更小 是是 CPU 调度和分派的基本单位 基本不拥有系统资源 调度和分派的基本单位 基本不拥有系统资源 但是可以与同属于一个 进程的其他线程共享资源 总结总结 进程与线程的比较 进程与线程的比较 1 调度 调度 在引入线程的操作系统中 把线程作为调度和分派的基本单位而把进程作为资源拥有者的基本单位 从而使得传统进程的两个属性分开 可以显著的提高系统的并发程度 同一进程中 线程的切换不会引起进程的 切换 而属于不同进程的线程在切换时需要进程切换 2 并发性 并发性 在引入线程的操作系统中 不仅进程之间可以并发执行 同一进程中的多个线程也可以并发执行 3 拥有资源 拥有资源 进程是拥有资源的独立单位 而线程虽然不拥有系统资源但是可以访问其所属进程的资源 与同 一进程中的各个线程共享资源 代码段 数据段 内存地址等 4 系统开销 系统开销 进程 线程 9 线程的实现机制 1 用户级线程 User Level Threads Linux 操作系统 用户级线程只存在于用户态中 不通过系统调用来实现 不依赖于内核 内核也不知道用户线程的存在 这使得 用户级线程包可以在不支持线程的操作系统上实现 而且用户级线程允许每个进程有自己定制的调度算法 2 内核级线程 Kernel Supported Threads Windows 操作系统 内核级线程依赖于内核 每个进程中没有线程表 而是在内核中有用来记录所有线程的线程表 3 混合实现方式 Solaris 操作系统 将用户级线程与某些或者全部内核线程多路复用 每个内核线程有一个可以轮流使用的用户线程集合 总结总结 用户级线程与内核级线程的比较 用户级线程与内核级线程的比较 1 线程的调度与切换速速 用户级 内核级 2 系统调用 在用户级线程调用一个系统调用时用户级线程调用一个系统调用时 由于内核不知道该用户级线程的存在 因而把系统调用看做把系统调用看做 是是整个进程整个进程的行为的行为 于是使该进程等待 而调度另一个进程执行 在内核级线程中 则调度是在内核级线程中 则调度是以线程以线程为单位为单位 当 一个线程调用一个系统调用时 内核把系统调用只看做是该线程的行为 因而封锁该线程 3 线程执行时间 10 进程 线程 调度概念 进程 线程 调度的任务是控制 协调进程 线程 对 CPU 的竞争 按照一定的调度算法 使得某一就绪进程获 得 CPU 的控制权 转换成运行状态 可抢占方式 按优先级调度 就绪队列中一旦有优先级高于当前进程 就立即进行调度 转让 不可抢占方式 一旦把 分配就一直占用 直到进入阻塞或时间片用完 进程 计算密集型 大多数时间花在运算上 密集型 在等待 上花费了绝大多数时间 11 进程 线程 调度算法 进程 线程 调度算法解决以何种次序对各就绪进程 线程 进行处理机的分配处理机的分配以及按照何种时间比例时间比例让进程 线程 占用处理机占用处理机 1 先来先服务 First Come First Servered FCFS 非抢占式 2 最短作业优先 Shortest Job First SJF 非抢占式批处理调度算法 周转时间 周转时间 Turnaround Time 指从一个批处理作业提交时刻开始直到该作业完成时刻为止的统计平均时间 度 量了用户要得到输出所需的平均等待时间用户要得到输出所需的平均等待时间 例如有四个作业 A B C D 运行时间分别为 a b c d 分钟 若按照 A B C D 的次序运行 则 A 的周转时间为 a 分钟 B 的周转时间为 a b 12 分钟 C 的周转时间为 a b c 16 分钟 D 的周转时间为 a b c d 20 分钟 平均时间为 4a 3b 2c d 4 分钟 由于 A 的 a 分 钟对平均值影响最大 加了 4 次 所以它应该是最短作业 3 最短剩余时间优先 Shortest Remaining Time Next SRTN 4 轮转发 Round Robin RR 最早来自分时系统 将 CPU 的运行时间划分成一个个时间片 就绪队列中的进程轮流运行一个时间片 当时间片结束时 就强迫运行 进程让出 CPU 该进程进入就绪队列 等待下一次调度 时间片设置过短会导致过多的进程切换降低 CPU 的效率 时间片过长可能会引起对短的交互申请的响应时间边长 5 最高优先级优先 Highest Priority First HPF 6 多级反馈队列算法 多级队列反馈法综合了先进先出调度算法 时间片轮转算法 可抢占式最高优先级算法综合了先进先出调度算法 时间片轮转算法 可抢占式最高优先级算法的一种进程 线程 调度 算法 系统按照优先级别设置多个就绪队列 不同优先级的队列有不同的时间片 优先级越高时间片越小 同一个 队列遵循先进先出 系统总是先调用级别高的队列 仅当级别高的队列为空时才调用次一级的队列 当正在 执行的进程 线程 用完其时间片后 进入次一级的就绪队列 当等待进程 线程 被唤醒时 该进程进入与其 同级的队列中 若该进程的优先级高于正在执行的进程时 就抢占 CPU 7 最短进程优先 8 实时系统中的调度算法 实时任务 周期 以规则的时间间隔发生 非周期 发生时间不可预知 如果有 m 个周期事件 事件 i 以周期发生 并且需要秒 CPU 时间处理一个事件 那么可以处理负载的条件 满足这个条件的实时系统称为是可调度的可调度的 1 1 实时系统调度算法 静态 速率单调调度算法 动态 最早最终时限优先调度 适用于可抢先可抢先的周期性周期性进程的经典静态静态实时调度算法 速率单调调度算法 单调 是因为优先级是以程序触发事件发生的频率定义的 所以优先级与进程的速率 每秒运行进程的次数 呈 线性关系 RMS 要求 每个周期性的进程必须在其周期内完成 进程间相互独立 每个进程在一次突发中需要相同的 CPU 时 间量 进程抢先即刻发生而没有系统开销 任何非周期性进程都没有最终时间 动态算法 最早最终时限优先调度 只要一个进程需要 CPU 时间 它就宣布它的到来时间和最终时间 调度程序维持一个可运行进程的列表 该列表 按照最终时限排序 第四章第四章 并发与同步并发与同步 进程间的相互作用 相关进程 在逻辑上具有某种联系 无关进程 相互独立 在逻辑上没有任何关系 进程间的相互制约 进程同步 多个进程中发生的事件存在某种时序关系 必须协同动作相互配合 进程互斥 由于共享资源所要求的排他性 进程间相互竞争以使用临界资源 临界资源是指计算机系统中的需要互斥使用的硬件或 软件资源 计算机资源的共享程度 互斥 资源的互斥使用指多个进程不能同时使用同一个资源 死锁 避免多个进程互不相让 出现都没有得到足够资源的情况 饥饿 避免某些进程一直得不到资源或者得到的几率很小 互斥的解决办法 1 由竞争者平等协商 2 引入进程管理者 信号量 进程同步机制遵循准则 空闲则入 任何时刻最多只有一个进程位于临界区 互斥资源 忙则等待 当有进程处于临界区时 其他进程只能在进入区等待 有限等待 避免死锁等现象 让权等待 在进入区等待而不能进入临界区的进程应释放 转换到阻塞态 进程互斥协商实现 软件方法 单标志方法 设置允许进入临界区的进程的一个标志位 双标志 先检查算法 设置一个标志数组 先检查后修改标志位 双标志 后检查算法 设置一个标志数组 先修改标志位后检查 先修改 后检查 后修改者等待算法算法 先修改后检查 后修改这等待 硬件方法 指令 指令 每个临界资源设置一个标志位标注资源的状态 指令 临界资源设置一个公共布尔变量 每个进程设置一个私有布尔变量 与 进行信息交换 注 硬件与软件方法的比较 硬件优于软件 使用范围广 简单 支持多个临界区 管理者实现 信号量 由操作系统提供的管理公共资源的有效手段 代表可用资源实体的数量 信号量只通过初始化和 两个原语来访问 是 核心代码的一部分 其执行不受进程调度和执行 的打断 原语相当于进入区 原语相当于退出区 二者必须成对使用 不能错序 遗漏和重复 信号量 的 属性为非负数时 表示当前的空闲资源 为负值时表示当前等待临界区的进程数 1 经典的进程同步问题 经典的进程同步问题 1 简单生产者 消费者问题 生产者和消费者通过一个缓冲区联系起来 缓冲区只能容纳一个产品 消费者不断生产产品 然后送往缓冲区 消费者不断从缓冲区取出产品 2 多个生产者 消费者问题 多个生产者和多个消费者通过一个环形缓冲池联系起来 缓冲池有多个缓冲区 每个缓冲区只能容纳一个产品 3 读者 写者问题 有某个共享文件 系统允许若干个进程对文件进行读写 要读文件的进程称为读者 要写文件的称为写者 且读 者和写者之间存在如下关系 允许多个进程同时读 有进程在写时 其他进程不能读写 有进程在读时 其他进程不能写 2 管程 管程 Monitor 高级同步原语 一个管程是一个由过程 变量及数据结构等组成的集合 他们组成一个特殊的模块或软件包 进程可在任何时候进程可在任何时候 调用管程中的过程 但是不能在管程之外声明的过程中直接访问管程内的数据结构调用管程中的过程 但是不能在管程之外声明的过程中直接访问管程内的数据结构 管程由四部分组成组成 管程名称 共享数据的说明 对数据进行操作的一组过程 对共享数据赋初值的语句 管程能保障共享资源的互斥执行 即一次只能有一个进程可以在管程内活动 该性能是由管程本身实现的 因此管程能保障共享资源的互斥执行 即一次只能有一个进程可以在管程内活动 该性能是由管程本身实现的 因此 程序员可以不必显示编写程序代码去实现这种同步制约 程序员可以不必显示编写程序代码去实现这种同步制约 管程不能使用 C 语言 因为管程是语言特性而 C 不支持 管程的特性 模块化 信息隐蔽 抽象数据类型 管程是编程语言的组成部分 进入管程时的互斥由编译器负责 编译器知道管程的特殊性 因此采用与其他过程 调用不同的方法来处理对管程的调用 管程通常是用来管理资源的管程通常是用来管理资源的 1 共享变量 共享变量 管程的共享变量在管程外是不可见的 外部只能通过调用管程中所说明的外部过程 函数 来间接 访问共享变量 2 条件变量 条件变量 使得进程在无法继续运行时被阻塞 引入条件变量和两个操作 wait 和 signal 导致调用进程自身阻塞 并将另一个等待进程调入管程 唤醒进程 将正在等待的进程变成执行状态 3 进程通信 解决进程之间的大量信息通信的问题有三类方案 共享内存 消息机制 管道通信 共享文件 三种方式都是高 级通信原语 解决少量信息通信的问题 例如 P V 操作 是一类低级通信原语 1 共享内存 在相互通信的进程之间设一个公共内存区 通过读写实现进程之间的信息交换 需要注意的两个问题 怎样提供 共享内存 公共内存总的读写互斥 互斥问题由开发人员解决 2 消息机制 消息传递机制 消息缓冲通道 根据 生产者 消费者 利用内存中的公共消息缓冲区 信箱通信 信箱说明 可存信件数 已有信件数 可存信件的指针 信箱体 3 管道 Pipe 通信 管道通信的基础是文件系统文件系统 管道管道 连接两个进程间的一个打开的共享文件 发送进程和接收进程要实施正确 的同步和互斥才能确保通信的正确性 而同步和互斥是操作系统自动进行的 对用户透明 同步和互斥是操作系统自动进行的 对用户透明 第五章第五章 内存管理内存管理 计算机可以直接访问内存 但是不能直接访问外存 需要启动相应的 I O 设备后才能使外存与内存交换信息 存储体系 高速缓存器 容量小 存取速度很快 昂贵 内容易变 几百 内存 容量几千兆 中等速度 中等价格 内容易变 系统区 用于存放 常驻内存部分 用户区 分配给用户存放数据和程序 外存 磁盘 低速 价廉 内容不易变 几百到几千 存储管理实质上就是管理供用户使用的部分 用户区 1 操作系统中存储管理的主要任务 内存的分配和回收 存储共享 存储保护 地址转换 1 内存的分配与回收 有效的分配回收机制需要具有以下功能 记录每个存储区域的状态记录每个存储区域的状态 记录内存空间中哪些是分配了的 哪些是空 闲的 实施分配实施分配 按需分配 并修改相应的分配表格 回收回收 接收用户释放的区域 修改分配表格 2 存储共享 指两个或多个进程共用内存中的相同区域 包括代码共享和数据共享 代码共享节省内存空间 提高内存利用率 数据共享实现进程通信 3 存储保护 存储保护一般以硬件保护机制为主 软件为辅以硬件保护机制为主 软件为辅 因为完全用软件实现系统开销太大 速度显著降低 当发生地址 越界或非法操作时 由硬件产生中断硬件产生中断 进入操作系统处理 保护内容 保护系统程序区不被用户有意 无意侵犯 不允许用户程序读写不属于自己地址空间的数据 4 扩充 内存容量 借助虚拟存储技术活其他交换技术达到在逻辑上扩充内存容量 亦即为用户提供比内存物理空间大得多的地址空 间 2 地址转换 地址重定位 地址映射 地址 物理地址 绝对地址 系统 物理存储空间 逻辑地址 用户程序中使用的地址 逻辑存储空间 当用户程序进入计算机系统请求执行时 存储管理要为它分配合适的内存空间 该地址空间的起始地址不是固定 的 而且 逻辑地址与分配到的屋里地址多数是不一致的 为了保证程序的正确执行 必须根据分配给程序的内 存区域对程序中指令和数据的存放地址进行重定位重定位 即把逻辑地址转换成绝对地址把逻辑地址转换成绝对地址 物理地址 地址转换 静态 在程序执行前集中完成 不支持 程序浮动 执行时被改变存储区域仍能正确执行 动态 每执行一条指令重定位一次 基地址 逻辑地址 绝对地址 支持 程序浮动 内存管理方案 单一用户 连续区 管理 分区管理 连续存储空间 固定分区 可变分区 页式管理 不连续 段式管理 段页式管理 3 分区存储管理方案 分区存储管理是能满足多道程序运行的最简单的存储管理方案 基本思想是把内存划分成若干个连续区域 每个 分区装入一个运行程序 分区管理要求运行程序一次全部装入内存之后 才能开始运行 1 固定分区 每个分区一旦划分好 在系统运行期间不再重新划分 程序运行时必须提供对内存资源的最大申请量 用于管理固定分区管理的内存分配表内存分配表 按照顺序说明每个分区的序号 分区大小 分区起始地址 使用状态 占 用或空闲 2 可变分区 分区大小正好等于用户程序的需求量 而且分区的数目也是可变的 碎片碎片 内存经过一段时间的分配回收后 存在很多很小的空闲块 有时候每个碎片的大小都不满足程序进一步分配要求 但是总和可以满足时 通过 移动技术移动技术 或者称为 紧凑技术 紧凑技术 紧缩技术紧缩技术 来移动内存中的程序 把空闲碎片合并成一个连续的大空闲区来移动内存中的程序 把空闲碎片合并成一个连续的大空闲区 移动技术移动技术 可以集中分散的空闲区 提高内存的利用率 便于作业动态扩充内存 但是要尽可能减少需要移动的 作业数和信息量 并不需要将所有的空闲碎片合并 根据用户程序的大小和使用情况综合考虑 也不一定要移动 到内存一端 可变分区的实现 硬件设置两个专用的控制寄存器 基址寄存器和限长寄存器 基址寄存器和限长寄存器 程序执行的过程中 每执行一条指令都要取出该指令的逻辑地址 当逻辑地址小于限长寄存器中的限长值时 逻程序执行的过程中 每执行一条指令都要取出该指令的逻辑地址 当逻辑地址小于限长寄存器中的限长值时 逻 辑地址加上基地址得到绝对地址 当逻辑地址大于限长寄存器中的限长值时 表示欲访问的内存地址超出了所分辑地址加上基地址得到绝对地址 当逻辑地址大于限长寄存器中的限长值时 表示欲访问的内存地址超出了所分 配的分区范围 此时不允许访问 而形成一个配的分区范围 此时不允许访问 而形成一个 地址越界地址越界 的程序性中断事件 的程序性中断事件 可辨分区存储管理方案中的内存分配表由两张表组成 一张是已分配区表 一张是未分配表区 4 可变分区存储管理方案可变分区存储管理方案中空闲分区的分配策略 1 最先适应算法 顺序分配算法 顺序查找分区说明表 找到第一个满足申请长度的空闲区第一个满足申请长度的空闲区 将其分割并分 配 算法简单快速 2 最优适应算法 找到第一个满足申请长度的满足申请长度的最小最小空闲区空闲区 算法最节约空间 但是容易形成很多很小的碎片 3 最坏适应算法 找到第一个满足申请长度的满足申请长度的最大最大空闲区空闲区 分割剩下的空闲区还能用于装入其他程序 4 下次适应算法 从上一次分配的位置开始扫描内存 选择下一个大小足够的可用块 可变分区管理中 在回收空间时 应该先检查是否有与回收区相邻的空闲区 即检查相邻的空闲区表中标志为 未 分配 的栏目 已确定是否有相邻空闲区 若有 则应合并成一个空闲区登记 合并回收合并回收 5 分区保护 1 系统设置界限寄存器 界限寄存器可以是上 下界寄存器 也可以是基址 限长寄存器 通常 系统设置一对界限寄存器 用来存放现行 进程的存储界限 2 保护键 为每个分区分配一个保护键 相当于一把锁 同时为每个进程分配一个相应的保护键 相当于一把钥匙 存放在 程序状态字中 每当访问内存时 都要检查要是和锁是否匹配 若不匹配 则发出保护性中断 6 覆盖技术与交换技术 为了 扩充 内存 可以把进程地址空间中信息的一部分放在外存上 而把那些当前需要的执行程序段和数据段放 在内存中 在内 外存中需要进行信息交换 主要技术 覆盖技术 覆盖技术 Overlay 主要在早期的系统中 交换技术交换技术 Swapping 主要是目前的小型分时系统 1 覆盖技术 覆盖技术是指一个程序的若干程序段一个程序的若干程序段或几个程序的某些部分共享某一个存储空间 覆盖技术的实现是把程序划分把程序划分 为若干个功能相对独立的程序段 按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域为若干个功能相对独立的程序段 按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域 未执行的程序段先保存在磁盘 外存 上 当有关程序段的前一部分执行结束后 把后续程序段调入内存 覆盖 前面的程序段 覆盖发生在同一进程或程序内部 覆盖技术打破了需要将一个程序的全部信息装入内存后程序才能运行的限制 覆盖技术不需要任何来自操作系统的特殊支持 是用户程序自己附加的控制用户程序自己附加的控制 可以由编译程序提供支持 覆盖技术对用户不透明 增加了用户的负担 主要用于系统程序的内存管理上 因为系统软件设计者容易了解系 统程序的覆盖结构 2 交换技术 交换技术又称对换技术 指进程从内存移动到磁盘并再回内存 交换技术是进程在内存与外存间的动态调度 是由操作系统控制的 多用于分时系统 是虚拟页式存储技术的基 础 每次交换 进程可能会被换到磁盘不同的地方 交换技术打破了一个程序一旦进入内存便一直运行到结束的限制 交换可以发生在不同的进程或程序之间 7 页式存储管理方案 页式存储 是把一个逻辑地址连续的程序分散的存放到几个不连续的内存区域中 存储管理部件把内存分成大小相等的内存分成大小相等的 块块 块是进行主存空间分配的物理单位 同时 要求程序中的逻辑地址也程序中的逻辑地址也 进行分页进行分页 页的大小与块的大小一致页的大小与块的大小一致 这样就可以把程序按页存储 页面存储器提供变成使用的逻辑地址分两部分 页号页号 页内地址页内地址 页式存储管理分配空间以物理页面为单位 分配表中具有 可以标识那些块已经分配 哪些块未分配 当前剩余 空闲块数 位示图 为了实现页式存储管理 系统要提供一对硬件的页表控制寄存器 页表起始地址寄存器 页表长度寄存器 另外还 需高速缓冲存储器的支持 物理地址物理地址 内存块号内存块号 块长块长 页内地址页内地址 8 页式存储管理方案 页表页表 1 多级页表 存放页表的页面称为页表页 页表页可以不连续存放 需要对页表页的地址进行索引 在大多数的操作系统中 一般采用二级页表二级页表 即由页表页和页目录一起构成进程页表 第一季表示页目录 保存 页表页的地址 第二级为页表页 存放物理页面号 内存块号 2 散列页表 更适用于大于 32 位系统 比如 64 位 该方法是使用以页号为散列值 每个表项都包含一个链表 该链表中元素 的散列值都指向同一个位置 每个表项都包含三个字段 a 虚拟页号 b 所映射的页框号 c 指向链表 中下一个元素的指针 3 反置页表 在反置页表中 每个物理页框对应一个表项 每个表项包含于该页框相对应的虚拟页面地址以及拥有该页面进程 的信息 反置页表法减少了存放每个页表所使用的内存数量 但是增加了内存访问时的查表时间 反置页表是按反置页表是按 照物理地址排序的照物理地址排序的 而在使用中是按照虚拟地址查找在使用中是按照虚拟地址查找 因此有可能为了寻找相匹配的表项而遍历权标 9 页式存储管理方案 快表 一般而言 页式存储管理中的页表是存放在内存中页表是存放在内存中的 于是 当要按照给定的逻辑地址进行读写操作时 需要访 问两次 第一次按照页号独处页表中对应的块号 第二次按照计算出来的物理地址进行读写 快表快表 利用高速缓冲存储器存放当前访问最频繁的少数活动页面的页号访问最频繁的少数活动页面的页号 这个高速缓冲存储器称为 快表 实际上 查找快表和查找内存页表是并行进行的 一旦发现快表中有与所查页号一致的逻辑页号就停止查找内存 页表 而直接利用快表中的逻辑页号 10 虚拟存储技术 虚拟存储技术的基本思想是利用大容量的外存开扩充内存 产生一个比有限的实际内存空间大的多的 逻辑的虚 拟内存空间 实现虚拟存储技术需要以下硬件支持 a 系统有足够大的外存和一定容量的内存 b 硬件系统支持虚虚 实地实地 址映射址映射机制 虚拟存储技术与交换技术虚拟存储技术与交换技术在原理上类似 区别是 交换技术是以进程为单位进行的 如果一个进程所需的内存大 于当前系统内存 那么该进程就不能在系统中运行 而虚拟存储一般是以页或段为单位 如果一个进程所需的内 存大于当前系统内存 那么该进程仍然可以在系统中运行 因为该进程的一部分可以被换到外存上 11 虚拟页式存储管理 1 基本思想 在进程开始运行之前 不是装入所有页面 而是装入一个或 0 个页面 之后根据进程运行的需要 动态装入其他页面 当内存空间已满时 根据某种算法置换出某个页面以装入新的页面 2 页面调度策略 虚拟存储器系统通常定义三种策略来规定如何进行页面调度 调入策略 置页策略 置换策略 a 调入策略 缺页中断 若在页表中发现所要访问的页面不在内存不在内存中 则产生缺页中断 调入策略决定了什么时候讲一个页由外存调入内存中 通常有两种策略 请求调页 请求调页 Demand Paging 预调页 预调页 Pre paging 调入策略 请求调页 只调入发生缺页时所需要的页面 预调页 一次调入所缺页及其相邻的几页 b 置页策略 确定将调入的虚拟页放在屋里内存的什么位置 c 置换策略 置换策略用于确定哪个虚页面必须从内存中移出 为新的页面提供空位 置换策略 固定分配局部置换 为每一个进程分配固定页数的内存空间 可变分配全局置换 操作系统本身保持一个空闲物理块队列 当用完时才在内存中选择一块调出 可变分配局部置换 当某进程缺页时只允许从该进程的页面中选出一页换出而不影响其他进程 3 页面置换算法置换算法 置换算法 先进先出页面置换算法 最近最少使用页面置换算法 使用时间 计时器 最近最不常用页面置换算法 使用次数 计数器 理想页面置换算法 置换以后不再需要的或在最长时间以后才需要的页面 不可能实现 但可以作为衡量其他页面置换算法优劣的一个标准 最近未使用页面置换算法 在最近一个时钟滴答 典型是20 中置换一个从未被访问过的已修改页面 第二次机会页面置换算法 寻找最近时钟间隔内从来没有被访问过的页面 若 所有的页面都被访问过 该算法就退化为 算法 时钟页面置换算法 把所有的页面都保存在一个类似时钟面的环形链表中 一个表指针指向最老的页面 4 影响缺页中断率的因素 分配给程序的内存块数 分配给程序的内存块数越多 则同时装入内存的页面数就越多 中断率就越低 根据试验分析 对一共有 n 页的程序来说 只要能分到 n 2 块内存空间时才把他装入内存执行可使系统获得最高效 率 页面的大小 页面的大小即内存分块的大小 块大则页面也大 装入一页的信息量就大 就减少了缺页中断的 次数 降低了缺页中断率 程序编制方法 缺页中断与程序的局部化程度密切相关 一般来说 希望编制的程序能经常集中在几个页面上 进行访问 可以减少缺页中断率 页面置换算法 页面调度方法很重要 第六章第六章 文件管理文件管理 数据存储通常是以文件形式存放在磁盘或其他外界存储介质上 文件管理通过目录来完成 目录又是建立在分区 或者卷的基础上 操作系统与文件和目录相关的子系统称为文件系统 文件系统是操作系统中统一管理信息资源 的一种软件 文件是一种抽象机制 它提供了一种把信息保存在存储介质上而且便于存取的方法 用户不必关心文件实现的细 节 即对用户透明 1 文件分类 在文件系统中通常把文件按照其性质和用途的不同进行分类 也可以按照保护方式 信息流向 存放时间 存放 介质等进行分类 按用途分 系统文件