软件技术基础-操作系统.ppt

第2章操作系统 主要内容 操作系统概论处理机管理作业管理存储管理设备管理文件管理 2 1操作系统概论 操作系统是加到计算机硬件上的第一层软件 它是对计算机硬件的首次扩充 操作系统管理的是计算机的硬件 随着计算机硬件的发展和深化 必然导致操作系统更新换代 操作系统是用户与计算机硬件设备之间的接口 一 操作系统的形成和发展 1 手工操作阶段 1946 50年代 工作方式用户 用户既是程序员 又是操作员 用户是计算机专业人员 编程语言 机器语言 输入输出 纸带或卡片 计算机的工作特点用户独占全机 不出现资源被其他用户占用 资源利用率低 CPU等待用户 计算前 手工装入纸带或卡片 计算完成后 手工卸取纸带或卡片 CPU利用率低 第一台电子管计算机 ENIAC 手工操作阶段 续 主要矛盾计算机处理能力的提高 手工操作的低效率 造成浪费 用户独占全机的所有资源 提高效率的途径专门的操作员 批处理 2 早期批量处理阶段 50年代末 60年代中 利用磁带把若干个作业分类编成作业执行序列 每批作业由一个专门的监督程序 Monitor 自动依次处理 可使用汇编语言开发 批处理中的作业的组成 用户程序数据作业说明书 作业控制语言 批 供一次加载的磁带或磁盘 通常由若干个作业组装成 在处理中使用一组相同的系统软件 系统带 两种批处理方式联机批处理脱机批处理 用户交给计算机执行的具有独立功能的任务 3 管理程序阶段 60年代初 发展了通道技术和中断技术 这些技术的出现使控制程序在负责作业运行的同时提供I O控制功能 通道 专用于控制输入输出设备的小型处理机 I O处理机 通道有专用的I O处理器 可与CPU并行工作可实现I O联机处理中断 是指CPU在收到外部中断信号后 停止原来工作 转去处理该中断事件 完毕后回到原来断点继续工作 中断处理过程 中断请求 中断响应 中断点 暂停当前任务并保存现场 中断处理例程 中断返回 恢复中断点的现场并继续原有任务可处理算术溢出和非法操作码 死循环 利用时钟中断进行超时限定 控制程序发展为执行系统 executivesystem 常驻内存 4 多道程序设计与多道批处理系统 管理程序实现了CPU和I O的并行 但作业仍然是串行执行的 60年代 70年代 集成电路 利用多道批处理提高资源的利用率 多道批处理的运行特征多道 内存中同时存放几个作业 宏观上并行运行 都处于运行状态 但都未运行完 微观上串行运行 各作业交替使用CPU 优点 资源利用率高 CPU和内存利用率较高 作业吞吐量大 单位时间内完成的工作总量大 缺点 用户交互性差 整个作业完成后或中间出错时 才与用户交互 不利于调试和修改 作业平均周转时间长 短作业的周转时间显著增长 5 分时系统 分时 是指多个程序分时共享硬件和软件资源 即 多任务 多个用户分享使用同一台计算机 即 多用户 特点 人机交互性好 在调试和运行程序时由用户自己操作 共享主机 多个用户同时使用 用户独立性 对每个用户而言好象独占主机 现在的许多操作系统都具有分时处理的功能 在分时系统的基础上 操作系统的发展开始分化 如实时系统 通用系统 个人系统等 6 实时系统 real timesystem 用于工业过程控制 军事实时控制 金融等领域 包括实时控制 实时信息处理 要求 响应时间短 在一定范围之内 系统可靠性高任务的类型 周期性实时任务 非周期性实时任务 截止时间 deadline 开始截止时间 最晚开始时间 和完成截止时间 最晚完成时间 目前的操作系统 通常具有分时 实时和批处理功能 又称作通用操作系统 可适用于计算 事务处理等多种领域 能运行在多种硬件平台上 如UNIX系统 WindowsNT等 二 操作系统的功能 1 处理机管理管理目标 完成处理机资源的分配调度等功能 处理机调度的单位可为进程或线程 进程控制 创建 撤销 挂起 改变运行优先级等 主动改变进程的状态进程同步 协调并发进程之间的推进步骤 以协调资源共享 交换信息能力弱进程通信 进程之间传送数据 以协调进程间的协作 交换信息能力强 也可以用来协调进程之间的推进进程调度 作业和进程的运行切换 以充分利用处理机资源和提高系统性能 未必是进程控制操作所引起 可能是时间片轮转 I O操作 2 存储器管理 管理目标 提高利用率 方便用户使用 提供足够的存储空间 方便进程并发运行 存储分配与回收存储保护 保证进程间互不干扰 相互保密 如 访问合法性检查 甚至要防止从 垃圾 中窃取其他进程的信息 地址映射 变换 进程逻辑地址到内存物理地址的映射 内存扩充 覆盖 交换和虚拟存储 提高内存利用率 扩大进程的内存空间 3 设备管理 管理的目标 方便设备使用 提高CPU与I O设备利用率 设备操作 利用设备驱动程序 通常在内核中 完成对设备的操作 还需处理外设的IRQ 设备独立性 deviceindependence 提供统一的I O设备接口 使应用程序独立于物理设备 提高可适应性 在同样的接口和操作下完成不同的内容 如FAXModem作为Windows上的打印机设备 设备分配与回收 在多用户间共享I O设备资源 虚拟设备 virtualdevice 设备由多个进程共享 每个进程如同独占 缓冲区管理 匹配CPU和外设的速度 提高两者的利用率 单缓冲区 双缓冲区和公用缓冲区 4 文件管理 管理目标 解决软件资源的存储 共享 保密和保护 文件存储空间管理 解决如何存放信息 以提高空间利用率和读写性能 目录管理 解决信息检索问题 文件的属性 如文件名 单一副本赋予多文件名 文件的读写管理和存取控制 解决信息安全问题 系统设口令 哪个用户 用户分类 哪个用户组 文件权限 针对用户或用户组的读写权 软件管理 软件的版本 相互依赖关系 安装和拆除等 5 作业管理 管理目标 提供一个友好的用户访问操作系统的接口 系统命令 供用户用于组织和控制自己的作业运行 命令行 菜单式或GUI 联机 命令脚本 脱机 编程接口 供用户程序和系统程序调用操作系统功能 系统调用和高级语言库函数 操作系统的主要功能 提供用户和计算机之间的接口 有效管理控制计算机软 硬件资源 合理调度计算机工作流程 改善计算机系统的性能 三 操作系统的特性 由于现代操作系统一般为多道程序系统 给操作系统的设计 实现带来了许多复杂问题 从资源管理和用户服务的观点出发 操作系统具有以下特征 1 并发性 concurrency 两个或两个以上事件在同一时间间隔中发生 2 共享性 sharing 互斥共享并发访问3 虚拟性 virtual 把物理实体映射为一个或者多个逻辑实体 4 不确定性 nondeterministic 程序执行顺序 时间 系统事件 中断 故障 发生的不确定性 四 操作系统的分类 按操作系统的使用环境和对作业处理方式来考虑 将操作系统分为 批处理操作系统分时操作系统实时操作系统网络操作系统分布式操作系统 1 批处理操作系统 批处理系统也称为作业处理系统 在批处理系统中 操作人员将作业成批地装入计算机中 由操作系统在计算机中某个特定区域 一般称为输入井 将其组织好并按一定的算法选择其中的一个或几个作业 将其调入内存使其运行 运行结束后 把结果放入 输出井 由计算机统一输出后 交给用户 批处理系统包括单道批处理系统和多道批处理系统 单道批处理系统 用户一次可以提交多个作业 但系统一次只处理一个作业 处理完一个作业后 再调入下一个作业进行处理 多道批处理系统 把内存分为若干部分 属于同一批次的若干个作业调入内存 存放在内存的不同部分 一个作业由于等待输入输出操作而让处理机出现空闲时 系统自动进行切换 处理另一个作业 批处理操作系统 续 多道 和 成批 是批处理系统的两大特点 多道 系统内允许有多个作业 这些作业存放在外存中 组成一个后备队 系统按照一定的调度策略从队列中选取一个或多个作业进入内存运行 成批 作业在运行过程中不允许用户直接干预操作 作业的装入 运行 结果的显示都由系统自动实现 批处理系统的主要优点是系统吞吐量大 资源利用率高 所谓 吞吐量 是指单位时间内系统所能完成的任务的总和 批处理系统的主要缺点是交互能力比较差 2 分时操作系统 分时操作系统利用分时技术实现多道程序设计的一种操作系统 它一般采用时间片轮转的办法 使一台计算机同时为多个终端用户服务 对每个用户都能保证足够快的响应时间 并提供交互会话功能 特点 多路性 即众多联机用户可以同时使用同一台计算机 交互性 用户与计算机之间可进行 会话 独立性 各终端用户感觉到自己独占了计算机 3 实时操作系统 实时操作系统是又一种类型的操作系统 对外部的请求 实时操作系统能够在规定的时间内处理完毕 实时 指计算机对于用户请求能足够快地进行处理 并做出反映 要求毫秒 微秒级 实时操作系统的应用 实时控制 工业过程控制 防空系统等实时信息处理 情报检索和查询 飞机订票系统 银行信用卡系统 系统特点 及时响应 每一个信息接收分析处理和发送的过程必须在严格的时间限制内完成 简单的交互功能 支持用户使用终端 提供联机服务 高可靠性 要求高可靠性和安全性 效率则放在第二位 4 网络操作系统 计算机网络是通过通信设施把地理上分散的具有自制能力的计算机连接起来 以实现数据交换 资源共享和互操作为目的的计算机系统 网络操作系统是建立在主机操作系统基础上 用于管理网络通信和共享资源 协调各主机上任务的运行 并向用户提供统一的 有效的网络接口的软件集合 包括网络管理 通信 资源共享 系统安全和多种网络应用服务 主要功能 提供高效 可靠的网络服务功能 提供多种网络服务功能 5 分布式操作系统 分布式操作系统也是通过通信网络将物理上分散且具有自制能力的计算机系统互连起来 实现信息和资源共享 协作完成任务 但分布式系统要求一个统一的操作系统实现系统资源的统一地管理 分布式操作系统负责管理分布式系统中的所有资源 包括整个系统的资源分配和调度 任务划分 数据传输 协调工作 并为用户提供一个统一的界面 用户通过该界面使用系统资源时无须了解资源的位置 处理上的分布是分布式系统最基本的特征 2 2处理机管理 一 进程的概念1 程序的顺序执行与并发执行顺序执行 一个具有独立功能的程序独占CPU直至得到最终结果的过程 单道程序系统 特点 顺序性 封闭性 可再现性并发执行 逻辑上相互独立的一组程序在执行时间上相互重叠 多道程序系统 特点 程序间相互约束性 资源的争夺与共享 2 进程的概念 进程的概念是在60年代初期由MIT的Multics系统和IBM的TSS 360系统首先引用 从那以后人们对进程下过各种定义 例如 进程是一个可以并发执行的计算部分 进程是一抽象的实体 它在执行的过程中需要分配和释放各种资源 进程是一次可以进行调度的独立势执行活动 归纳各种定义的本质 给出进程的定义 进程是可并发执行的程序在给定数据集合上的一次执行过程 是系统进行资源分配和调度的一个独立的基本单位和实体 是指执行一个映象程序的总环境 进程的基本特征 动态性 进程是程序的一次执行 它有着创建 活动 暂停 终止等过程 具有一定的生命期 是动态地产生 变化和消亡的 并发性 进程之间的动作在时间上可以重叠 即系统中有若干进程都已经开始 但又没有结束 称这些进程为并发进程 独立性 进程是系统调度和资源分配的独立单位 它具有相对独立的功能 拥有自己独立的进程控制块PCB 异步性 各个并发进程按照各自独立的 不可预知的速度向前推进 交互性 由于并发进程之间具有直接或间接的关系 在运行过程中它们之间需要进行必要的交互 同步 互斥和数据通信等 以完成特定的任务 结构性 从结构上看 进程实体是由程序段 数据段和进程控制段三部分组成 进程和程序的区别和联系 进程是为了更好地描述并发执行程序的动态特性而引入的 而进程与程序既有区别又有联系 主要表现在以下方面 1 程序是一组有序的指令 是一种静态的概念 而进程是指一次运行的活动 是动态的概念 即进程是执行程序的动态过程 程序是进程运行的静态文件 若把程序比喻为动画片的拷贝 则进程就是动画片的放映过程 2 一个进程可以执行一个或多个程序 如编译C程序时 同时执行预处理 语法 语义分析 代码生成和优化等几个程序 反之 一个程序也可能被多个进程执行 3 程序可以作为一种资源以文件的形式长期保存 而进程只是一次执行过程 具有生命期 3 进程控制块 进行控制块PCB ProcessControlBlock 是操作系统为了反映进程的动态特性 便于系统控制和描述进程的活动过程而专门定义的一种数据结构 用于记录和描述进程执行情况和状态变化 PCB是进程存在的惟一标志 进程 程序 数据 进程控制块 4 进程状态及其转换 1 进程状态就绪状态 若进程已具备了运行条件 只因CPU被别的进程占用而不能被CPU执行 则称此时进程处于就绪状态 一旦把CPU分配给它 该进程就可以运行 从宏观上讲 它是一种逻辑上的可运行状态 系统中处于就绪状态的进程可以有多个 执行状态 当一个进程已分配到CPU 它的程序正在被CPU执行时进程所处的状态称执行状态 也称为运行状态 对于单CPU系统而言 处于执行状态的进程只可能有一个 等待状态 进程因等待某种事件的发生而暂时不能运行的状态称等待状态 例如 等待输入 输出 等待进程间的同步 互斥等 一旦引起等待的原因消失 进程便转为就绪状态 以便在适当的时候占用CPU 系统中处于等待状态的进程可以有多个 有的系统按照进程不同的等待原因 把处于等待状态的进程又分成多种状态 系统中处于等待状态的进程可以有多个 2 进程的状态转换 就绪 运行调度程序选择一个新的进程运行运行 就绪运行进程用完了时间片运行进程被中断 因为一高优先级进程处于就绪状态运行 等待当一进程必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I O且必须等待结果等待某一进程提供输入等待 就绪当所等待的事件发生时 二 进程控制 进程有一个从创建到撤消的生命周期 进程控制就是对进程在其生命期的各种活动及状态转变实施有效的控制 创建 撤消进程以及完成进程各状态之间的转换是由具有特定功能的进程控制原语实现的 原语 Primitive 原语就是计算机机器指令的延伸 它是由若干条机器指令构成 并完成一种特定功能的程序段 为保证原语操作的正确性 还规定原语在执行期间必须一次执行完 中间不允许被中断 也就是说 原语具有原子性 即原语操作中的所有指令 动作 要么全做 要么全不做 不允许被分割 在单CPU系统中 在执行原语的过程中一般要关中断 原语是机器指令的延伸 是非进程模块 原语操作的执行过程不可间断 原语用微代码实现 进程控制原语 进程控制原语包括 创建原语 建立PCB 申请PCB 信息填入PCB 插入就绪队列 可由系统模块和父进程创建 进程控制原语 续 撤消原语 进程完成或异常中断时撤消 撤消进程及其所有子进程 释放相应资源和PCB 阻塞原语 执行中需要I O或其它条件时阻塞 中断执行 保存状态到PCB 设置为阻塞状态 PCB插入到阻塞队列中 唤醒原语 阻塞的进程获得所需资源时唤醒 置PCB当前状态为就绪 将进程从阻塞队列中撤消 插入到就绪队列中 三 进程调度 处理机调度 1 进程调度的原因及方式进程调度的原因 执行的进程运行完毕 等待某种事件发生 时间片用完 就绪队列中出现高优先级的进程等 进程调度的方式分 剥夺式 就绪队列中一旦有高优先级的进程出现 则立即剥夺正在执行的进程的CPU使用权 而将CPU使用权交给高优先级的进程 非剥夺式 进程一旦获得CPU使用权 则一直占有 直到由于其它原因而阻塞为止 2 进程调度的功能 记录系统中所有进程的执行情况进程管理模块记录系统中进程的执行情况和状态 根据PCB的变化 在适当的时间选择就绪队列中的一个进程占据处理机运行 确定分配处理机的原则进程的主要功能是按照一定的调度策略 调度算法 选择一个处于就绪状态的进程 使其获得处理机执行 处理机的分配和回收PCB中的有关现场信息送入CPU的相关寄存器 进程执行结束后回收处理机 3 进程调度的算法 进程调度算法的原则 尽可能提高资源利用率减少CPU空闲时间调度算法的评价指标 周转时间TT或平均周转时间ATT 进程第一次进入就绪队列到进程结束的时间间隔 响应时间RT 从提交一个请求开始到计算机做出响应的时间间隔 进程调度的常用算法 先来先服务 FCFS 算法 每次进行进程调度时 总是选择就绪队列的最首进程运行 优点 算法简单 一般意义下公平缺点 对短进程需等待较长时间 平均周转时间长使用场合 一般作为辅助调度算法 最短CPU运行期优先 SCBF 算法 优先调度CPU运行期短的进程 优点 平均周转时间短缺点 长进程等待时间长 依赖于各进程的下一个CPU周期 需要估算CPU周期其中 n为估计的第n个CPU时间 tn为实际的第n个CPU时间 系数a在0 1之间 常取a 0 5 时间片轮转算法 按照公平服务的原则 将CPU时间划分为小时间片 进程被调度后执行一个时间片 然后让出CPU 排到就绪队列尾 等待下一次调度 同时调度当前就绪队列中的第一个进程 依此轮转 优点 公平缺点 时间片大小的选择十分关键时间片的选择考虑 系统响应时间就绪进程数量计算机处理能力使用场合 主要用于分时系统中 最高优先级优先 HPF 算法 进程调度每次将CPU分配给就绪队列中具有最高优先级的进程 核心是确定进程的优先级 静态优先级 进程创建时根据初始特性和用户要求确定 确定后不再改变 算法简单系统开销小可能导致优先级低的进程无限期等待 效率低动态优先级 创建时确定初始优先级 在进程运行过程中做适当修改 根据等待时间修改根据占有的CPU时间修改 进程优先级的确定原则 进程的类型 系统进程高于用户进程 前台进程高于后台进程 实时进程高于一般进程 对资源的需求量及类型 CPU短 资源少的高优先级 作业到达系统的时间 先到先服务 用户类型和要求 用户自己确定优先级 多级队列反馈法 几种基本算法的结合 基本思想是 按优先级分别设置n个就绪队列 优先级高的分配较小时间片 进程的优先级在运行过程中按进程动态特性调整 不固定在某一队列中 系统总是先调度优先级高的队列 仅当高优先级队列为空时 才调度下一优先级队列中的进程 同一优先级队列中按照先来先服务 FCFS 和时间片轮转 RR 法相结合的策略调度 四 进程互斥与同步 1 进程的互斥与临界区进程的互斥是由多个进程竞争同一共享资源而产生的相互制约的关系 这种因共享资源而产生的关系称为进程的互斥 MutualExclusion 以互斥关系使用的共享资源称为临界资源 CriticalSource 包括硬件 打印机 显示器 软驱等 和软件 公共变量 数据 子程序等 临界区是指每个进程中访问临界资源的那段代码 为保证对临界资源的互斥访问 进程的代码由以下部分组成 进入区 entrysection 申请进入临界区 临界区 criticalsection 访问临界资源 退出区 exitsection 退出对临界资源的访问 剩留区 remaindersection 进程其他部分 2 进程的同步 多个并发进程协作完成某项任务的过程中需要相互传递某种信息 进程之间通过在执行时序上的一种限制而达到相互合作 我们把这种合作关系称为进程的同步 Syrchronization 例如 A进程负责从键盘读取数据到缓冲区 B进程负责从缓冲区读取数据进行计算 A B进程并发执行的过程如下图所示 3 信号量和P V操作 同步机制同步机制 实现进程同步与互斥的机制 系统的同步机制为了解决对临界资源的访问 应遵守以下规则 空闲让进无进程处于临界区内 可让一申请进入临界区的进程进入 忙则等待若临界区内有进程 其余申请进入临界区的进程必须等待 有限等待进程进入临界区的要求必须在有限时间内得到满足 让权等待等待进入临界区的进程 若占有CPU必须立即释放 同步机制 续 早期解决进程互斥问题有软件的方法和硬件的方法 如 严格轮换法 Peterson的解决方案 TSL指令 Swap指令都可以实现进程的互斥 不过它们都有一定的缺陷 这里就不一一详细说明 而后来Kijkstra提出的信号量机制则更好的解决了互斥问题 如 硬件指令 TestandSet TS 为临界资源设置 锁 即设置一个锁变量Lock Lock false 开锁 表示临界资源空闲 Lock true 关锁 表示临界资源不空 保证了进程互斥 但当一个进程在临界区上执行时 其它任何企图进入临界区的进程都进入循环等待 不断调用TS测试 造成处理机浪费 P V操作 1986年荷兰计算机科学家Dijkstra把互斥的关键含义抽象为信号量 Semaphore 提出典型同步机制 P V操作 设信号量为S 整数 用S的值表示共享资源的使用情况 P V操作的定义如下 P S S S 1 若S 0 该进程继续执行 否则 进程阻塞进入S信号量的等待队列 直到其它进程执行V S 操作为止 V S S S 1 若S 0 则进程继续执行 否则唤醒阻塞队列中的一个进程 使其进入就绪状态 显然S可用于表示资源的数量 S 0 表示可分配的资源数量 S 0 S绝对值表示等待队列中的进程数目 用P V操作实现进程间互斥 设A B进程竞争临界资源 mutex为互斥信号量 初值为1 利用P V操作实现的进程互斥模型如下 进入时 若mutex 0 则阻塞 退出时mutex 1 每次只允许一个进程进入临界区 4 用P V操作实现进程间同步 例一 如图一个打印进程 一个计算进程和一个缓冲区 缓冲区为空时计算进程才能不断将结果送入缓冲区 打印进程必须在缓冲区不空时 才可以取出数据打印 两信号量S1 S2初值为0 S1 S2 缓冲区数据是否满 缓冲区数据是否空 用P V操作实现进程间同步 续 P V操作实现计算 打印进程同步的模型如下 例2 设有4个信号量 S1 S2 S3 S4 其中 S2 S3分别表示缓冲Buffer1和Buffer2是否装满数据 S1 S4分别表示缓冲区Buffer1和Buffer2是否为空 其初值分别为 S1 1 S2 0 S3 0 S4 1该三个并发进程同步模型如下 5 生产者 消费者问题 Producer ConsumerProblems 并发进程的同步和互斥问题的一般化 生产者 释放某一类资源的进程 消费者 使用某一类资源的进程 一组消费者进程 C1 C2 Cm 和一组生产者进程 P1 P2 Pk 通过一个由n个单元组成的环形缓冲区联系起来 如图 每个单元可放一个 产品 放入缓冲区内 消费者进程则不断地从缓冲区取出 产品 显然 生产者进程与消费者进程在使用缓冲区时有以下制约关系 缓冲区中至少有一个单元为空 生产者进程才能放入 产品 缓冲区中至少有一个单元是满的 消费者进程才能取出 产品 各消费者进程与各生产者进程只能互斥地使用临界资源缓冲区 根据上述分析 设置以下信号量 公用信号量mutex 初值为1 用于实现临界区互斥 生产者私有信号量empty 初值为n 表示空缓冲单元数 消费者私有信号量full 初值为0 表示满缓冲单元数目 指针in out分别指向当前第一个空缓冲区和第一个满缓冲区 下面给出生产者 消费者进程的模型 生产者进程 生产一个产品 P mutex in in 1 modn 将产品放入in所指向的缓冲区 P empty V full 消费者进程 P full 从out所指向的缓冲区取产品 V mutex out out 1 modn P mutex V empty V mutex 五 进程的通信 进程通信是指进程之间的消息交换 进程通信方式 低级通信原语 交换信息量较少 如互斥 同步机构 高级通信原语 交换信息量较多 如直接通信 间接通信 高级通信原语 直接通信 一个进程直接发送消息给接受者进程 Send P Msg Receive P Msg 间接通信 进程通过一个 信箱 来传递消息 Send A Msg Receive A Msg 目前常用的高级通信方式有消息缓冲通信 管道通信和信箱通信 1 消息缓冲通信 直接通信 基本思想 利用内存公共消息缓冲区实现进程间信息交换 公共消息缓冲区 把内存中的一个区域连入多个进程的虚拟地址空间 消息缓冲通信 续 发送者申请一个消息缓冲区 将消息填入其中 使用send receiver m 原语将消息发送出去 插入到接收进程消息队列 receiver为接收消息的进程名 m为发送进程内存存放消息的地址 接收进程利用receive n 原语从消息队列中摘取一则消息 释放相应的缓冲区 消息结构描述 typedefstructmessage intsender 发送者进程ID intsize 消息长度 char text 消息正文 structmessage next 下一消息 msg 消息缓冲通信 续 由于消息缓冲机制中所使用的是公用缓冲区 所以在传送消息时 两通信进程应满足如下条件 在发送进程把消息写入缓冲区及把缓冲区插入消息队列时 应禁止其他进程对该缓冲区消息队列的访问 否则将引起消息队列的混乱 同理 当接收进程从消息队列中读取消息时 也禁止其他进程对消息队列的访问 当缓冲队列为空时 接收进程不能接收任何消息 核心 进程的互斥与同步 消息缓冲通信描述 将发送与接收过程描述如下 其中mutex为公用信号量 用于控制进程对缓冲区的互斥访问 初值为1 设sm为接收进程的私有信号量 表示消息队列中等待接收的消息个数 初值为0 Send receiver m begin向系统申请一个消息缓冲区 P mutex 将发送区消息送入消息缓冲区 将消息缓冲区插入消息队列 V mutex V sm end Receive n beginP sm P mutex 取消息队列中的消息 将消息从缓冲区复制到接收区 释放缓冲区 V mutex end 2 管道通信 管道 pipe 通信由Unix首创 是一种有效的通信技术 因而管道通信成为进程通信的一种重要方式 管道 就是连接两个进程之间的一个打开的共享文件 管道文件 说明 管道文件是一种外存文件 主要用于连接一个写入进程和一个读出进程 以实现他们之间的数据通信 管道通信 续 利用管道进行通信的两个进程之间的关系 互斥关系 写入和读出进程不可能同时读或者写 同步关系 当管道文件为空时 读出进程等待写入进程 当管道文件为满时 写入进程等待读出进程 特点 数据传输量大 通信速度慢 3 信箱通信 间接通信 信箱通信是以发送 接收 回答信件作为通信的基本方式 由发送进程申请建立一个与接收进程链接的邮箱 发送进程把消息送往邮箱 接收进程从邮箱中取出消息 从而完成进程间信息交换 邮箱由邮箱头和邮箱体组成 其中邮箱头描述邮箱名 大小及拥有该邮箱的进程名等 邮箱体主要用于存放消息 信箱通信 续 由信箱建立起来的发送者与接收者之间的耦合关系 可分为一对一 一对多 多对一 多对多的关系 一对一 提供具有隔离作用的专用通道 一对多 适用于广播通信 多对一 适合于客户机 服务器结构的系统 多对多 一种通用信箱 用于消息的收集和分发系统 对只有一个发送进程和一个接收进程使用的邮箱 进程间通信应满足如以下条件 接收进程接收消息时 邮箱中至少要有一个消息存在 发送进程发送消息时 邮箱中至少要有一个空格能够存放消息 六 死锁 死锁 若干进程彼此等待对方所拥有且又不放的资源 其结果是谁也无法得到继续运行所需的全部资源而永远等待下去的现象 1 产生死锁的原因 两种 争夺资源引起的死锁 进程推进顺序不当而引起死锁 进程执行时操作顺序不当 也可能造成死锁 如生产者 消费者问题中 若颠倒两个P操作的顺序就可能造成死锁 生产者进程 生产一个产品 P mutex in in 1 modn 将产品放入in所指向的缓冲区 P empty V full 消费者进程 P full 从out所指向的缓冲区取产品 V mutex out out 1 modn P mutex V empty V mutex 死锁 产生死锁的必要条件 通过以上分析 可以得到产生死锁的必要条件 互斥条件进程互斥使用资源 任一时刻一个资源只为一个进程独占 其他进程若请求一个已被占用的资源 只能等占用者释放后才能使用 不剥夺条件进程所获得的资源在未使用完毕前 不能被其他进程强行剥夺 只能由获得该资源的进程自己释放 部分分配条件进程每次申请它所需要的一部分新资源的同时 继续占用它已分配到的资源 环路条件存在一个循环等待链 链中每一个进程都在等待它的前一个进程所持有的资源 2 死锁的预防 预防死锁 采用某种策略 限制并发进程对资源的请求 破坏产生死锁的必要条件 1 采用资源的静态预分配策略 破坏 部分分配 条件 要求进程必须预先申请其所需的全部资源 仅当全部资源满足时 系统才一次分配 进程运行过程不再申请资源 2 允许进程剥夺使用其他进程占有的资源 从而破坏 不可剥夺条件 进程请求新资源不能满足时 必须释放已占有的全部资源 3 采用资源顺序使用法 破坏 环路 条件 将系统资源按照类型线性排队 并按递增规则赋予每类资源唯一编号 进程申请资源时严格按资源编号递增顺序分配 这样 总有一个进程占据了较高序号的资源 它继续请求的资源必然是空闲的 该进程可以一直向前推进 3 死锁的避免 避免死锁不严格限制产生死锁的必要条件的存在 而是在系统运行过程中 一旦有可能出现死锁 尽量避免系统进入不安全状态 安全状态 系统保证申请者在有限的时间内获得所需的全部资源 则称系统处于安全状态 否则称系统处于不安全状态 例如 有8个资源供3个进程共享 它们的最大需求数分别为6 4 7 在某一时刻的资源分配情况如下 1 不安全啦 死锁的避免 续 基本方法 系统对每种资源的分配提供一种算法 当进程申请资源时 采用相应算法计算 以确定这一申请是否会造成死锁 若计算结果表明有可能产生死锁 就不予分配资源 例如 荷兰科学家Dijkstra的银行家算法 4 死锁的检测及解除 系统不限制资源的分配 但定时运行一个 死锁检测 程序 判断系统内是否出现死锁 若检测到死锁 则按一定的方法解除 常用解除死锁的方法 1 撤销进程法逐个撤消死锁进程 撤消 检测 撤消 2 资源剥夺法逐个撤消死锁等待链上的进程并剥夺它的全部资源 分配给死锁进程 直到死锁解除 七 线程 进程中包含了两种不同的独立概念 一是与资源的所有权有关 二是与执行有关 近年来开发的操作系统区别了这两个特征 用进程来实现资源的申请和分配 并创建了一种新的调度和执行的实体单元 线程 1 线程的概念线程是进程的一个实体 是能被系统独立调度和分配的基本单位 同一进程的多个线程可以并发执行 共享所属进程的资源 故线程又成为轻型进程 2 线程的描述 线程用TCB ThreadControlBlock 描述 一个TCB块大体包括 线程标识优先级线程状态 运行 阻塞 就绪寄存器值 保存线程寄存器的上下文堆栈指针 保存线程的栈指针 3 线程的基本操作 派生 由系统调用或相应的库函数派生自己的线程阻塞 一个线程在执行中需要等待某个事件发生 则被阻塞激活 阻塞线程的事件发生 则该线程被激活并进入就绪队列调度 选择一个就绪线程进入执行状态结束 线程结束 释放寄存器上下文及堆栈内容 4 线程的特性 线程是处理机调度的基本单位 自己不能申请资源 同一进程的多个线程可以并发执行线程具有就绪 阻塞 执行三种基本状态 但没有挂起状态线程的控制可以由操作系统内核完成 也可以由用户完成线程的系统开销小于进程 5 线程的分类 用户级线程 User levelThreads 管理过程全部由用户程序完成 操作系统内核只对进程进行管理 核心级线程 Kernel levelTheads 由操作系统内核进行管理 附 Windows的CPU管理相关 进程与线程的控制进程控制CreateProcess 创建进程GetGuiResources 查看进程GUI资源SetPriorityClass 设置进程优先级ExitProcess 终止进程TerninateProcess 结束进程线程控制CreateThread 创建线程SuspendThread 挂起线程ResumeThread 恢复线程SetThreadPriority 设置线程优先级 Windows的CPU管理相关 续 互斥和同步互锁函数Interlock 实现线程间一个长整数的读写InterlockIncrement InterlockDecrement 等 临界段 CriticalSectionInitializeCriticalSection EnterCriticalSection TryEnterCriticalSection LeaveCriticalSection DeleteCriticalSection 等互斥体MutexesCreateMutex OpenMutex ReleaseMutex 等信号量SemaphoresCreateSemaphore OpenSemaphore ReleaseSemaphore 等 2 3作业管理 一 作业的概念一个作业 就是用户请求计算机系统执行的一次独立的上机任务 是能共享公共资源区域的一族有关进程 进程家族 由控制命令序列 程序集和数据集三部分组成 一个作业一般又可分为若干顺序处理的作业步 作业步相互独立又相互关联 上一作业步的执行结果 往往是下一作业步的输入数据或输入文件 一般只有上一作业步完成才能继续执行下一作业步 作业管理包括对作业的控制和调度 1 作业控制块 一个作业也由作业控制块JCB JobControlBlock 来描述 JCB是记录类型的数据结构 用于记录作业的有关信息 通常包括 作业名 优先级 作业建立时间 作业状态 外存中存放作业的首地址 作业长度 内存需求量 作业估计的执行时间等 作业控制块JCB与作业之间具有一一对应的关系 JCB是作业在系统中存在的唯一标志 作业控制块定义举例 structJCB 定义作业控制块JCBcharname 10 作业名char state 作业状态inttime 估计运行时间intWtime 等待时间intarrive 到达时间intFtime 完成时间intBtime 开始时间floatRp 响应比 p structSqList structJCBr MAXSIZE 1 intlength L1 L2 L3 L4 2 作业状态 进入状态 用户将作业信息以操作说明书的形式输入 后备状态 作业信息提交后 建立JCB并插入到作业后备队列中等待调度 运行状态 作业从进入内存开始到完成 完成状态 作业完成或中止 系统回收全部资源 作业消亡 二 作业控制 作业管理包括对作业的控制和调度 作业控制包括两个方面 从用户角度看 作业控制就是用户通过作业控制级接口 组织和控制其作业在计算机上的运行的全过程 从系统管理的角度看 作业控制就是系统接受 分析并执行用户发出的控制命令 为作业的每个发展阶段提供必要的系统服务 1 用户与操作系统的接口 命令接口又称为作业控制级接口 这是系统为用户在作业控制级获得系统服务而设置的接口 用户利用作业控制级接口对作业在系统中运行的全过程进行控制 分联机接口和脱机接口 系统调用又称为程序级接口 由一级系统调用命令 又称广义指令 组成 是操作系统为用户在程序一级提供的服务 编程人员利用系统调用在源程序一级动态请求和释放系统资源 2 作业控制方式 联机控制方式 分时系统常用命令驱动方式 DOS 内部命令由解释执行 菜单驱动方式 Menu 菜单命令方式 窗口环境 X Windows MS Windows 图形用户界面GUI 作业控制方式 续 脱机控制方式 批处理系统常用脱机控制方式通常用于批处理系统 由系统提供一组作业控制语言JCL JobControlLanguage 供脱机用户使用 JCL由一组作业控制命令组成 如 ccmainprogram cccsubprogram clinkmainprogram objsubprogram objmainprogram exe 说明 4条作业控制命令定义了4个作业步 三 作业调度 作业调度由作业调度程序完成 作业调度的主要任务是 按照某种调度算法 从作业的后备队列中挑选一批合理搭配的作业进入内存 实现作业从后备状态转变为运行状态 同时为选中的作业分配内存和外设资源 并为其建立有关的进程 思考 作业调度和进程调度的区别和联系 进程调度 低级调度 作业调度 高级调度 宏调度 2 4存储管理 存储管理主要是对主存储空间的管理 包括 内存分配 释放 虚拟存储技术 地址变换 内存保护和共享 一 存储管理的功能1 内存分配和回收 管理内存分配表记录内存的分配情况相关信息 制定分配策略放置策略 如何选择空闲区域原则 调入策略 信息装入内存的时机 淘汰策略 暂时无用的数据调出内存 内存区域的划分方式以块为单位分配空闲内存 作业或进程终止并释放内存后 存储管理应回收相应存储空间 2 内存的共享 共享主存资源共享内存某些区域的信息 公用子程序 编译程序 链接程序以及公用数据等 3 存储保护避免内存中的程序相互干扰 防止用户程序侵犯系统内存区域 4 地址映射经过编译或汇编后所形成的目标代码 通常采用相对地址 即其首地址为零 其他指令中的地址都是相对首地址而定 因此 这个相对地址也称逻辑地址或虚拟地址 而在内存中不能用逻辑地址存取信息 只有物理地址才是内存中存储单元的实际地址 也称绝对地址 是可识别的 可寻址并实际存在的 重定位 逻辑地址转换成物理地址 1 静态重定位静态重定位也称静态地址映射 是在用户程序运行前 在程序装入内存的过程中一次完成从逻辑地址到物理地址的转换 且在程序运行过程中地址不再改变 2 动态重定位 简单 需连续内存空间 5 内存空间的扩充 为解决内存实际容量远小于多道程序所需内存容量的矛盾 利用大容量的外存空间来逻辑扩充内存 将暂时不用的程序和数据存放到外存中 等到需要访问时再装入 内存的扩充是通过覆盖与交换技术 主要是虚拟存储技术实现的 二 分区存储管理 基本思想 把内存划分成若干连续区域 每个作业可以占用一个或多个分区 1 固定分区 FixedPartitions 将内存分为若干大小相等或不等的区域 系统和用户作业分别占用 分区划分后 其长度和数量保持不变 分区存储管理 续 系统设置一内存分配表 记录分区号 起始地址 大小及占用情况 如图所示 缺点 常常产生许多不可使用的存储碎片 即 内零头 分区数固定 如果作业数大于分区数 则总有作业不能分配到分区 2 可变分区 VariablePartitions 可变分区是指在存储分配的过程中 按照作业的大小来划分分区 因此 分区大小可以随作业的要求改变 分区的数量也可以改变 管理方式 内存分配表采用两张表 已分配分区表 未分配分区表 每张表的表项为存储控制块MCB MemoryControlBlock 包括AMCB和FMCB 空闲分区控制块按某种次序构成FMCB链结构 内存的申请和释放 内存的申请作业申请内存时 系统在未分配分区表中查看是否有足够大的空闲分区 将其划分出作业要求大小的一部分 另一部分为空闲 同时修改两个分配表 内存的释放作业释放时回收内存 并将相邻的空闲区合并 缺点 采用可变分区技术 会产生极小的分区 即 外零头 解决方法 拼接 紧缩 可变分区分配及回收示意图 3 存储分配策略 首次适应算法FF FirstFit 未分配分区按地址从小到大排列 每次分配时顺序查找分区分配表 选择所遇到的第一个足以满足请求容量的内存空闲区进行分配 最佳适应算法BF BestFit 将空闲区按其大小从小到大的次序排列 每次分配时总是从头顺序查找未分配分区表 找到第一个能满足要求的最小空闲区进行分配 最坏适应算法WF WorstFit 最坏适应算法要求空闲区按照从大到小的顺序排列 每次分配时总是挑选一个最大的空闲区分配给作业 三 覆盖与交换技术 为了解决大作业与小内存的矛盾 常采用 覆盖 和 交换 两种存储管理技术 其实质是对内存进行逻辑扩充 1 覆盖 Overlay 所谓覆盖就是一个作业的若干程序段 或几个作业的某些部分共享某一内存区域 2 交换 Swapping 交换技术是指在内外存之间交换程序和数据 系统在高速大容量的外存中 通常是磁盘 开辟一个进程交换区 作为内存的直接延伸 所有用户进程的实体都存放在交换区中 引入中级调度机制 交换调度 从存储管理角度 交换并不是一种独立的管理方案 常与分区 分页及分段等存储管理技术相结合 四 虚拟存储管理 实存管理技术 对实际内存空间的管理 要求作业执行代码一次性装入 而且分区内部的地址必须连续 浪费存储空间 虚拟存储技术 用大容量的外存来扩充内存 为用户提供一个比有限的实际内存空间大得多的虚拟内存空间 虚拟存储管理技术采用 部分装入 部分交换 的策略 当内存已占满而又需将外存上信息装入时 则按一定策略进行内外存的交换 虚拟存储技术的具体实现有分页存储管理 分段存储管理和段页式存储管理 五 分页存储管理 分页式管理技术 通过地址转换机制 能明显消除内 外存之间的差别 将外存看作内存的扩充和延伸 解决存储空间的 外零头 问题 分页存储管理中 将逻辑地址空间分为大小相同的块 称为虚页面 Page 通常页面大小为2的整数次幂 512K 4K 将物理内存空间也划分为与页面大小相等的块 称之为存储块或页框 Pageframe 连续逻辑地址空间的页面 通过页面地址转换机构可以映射到不连续的内存块中 1 页面地址转换 为实现作业逻辑地址到物理地址的转换 需要建立以下数据结构 存储分块表MBT MemoryBlockTable 表中记录内存中每个存储块的使用情况 其中状态是指存储块是否空闲整个系统一张表 表目数等于内存块的总数 页表PT PageTable 每个运行的作业建立一张页表 表项对应该作业虚拟地址空间的一页 作业被调度时 将作业对应的页表起始地址及大小装入特定的页表控制寄存器 PTCR 中 存储分块表和页表示意 说明 页表是在作业装入主存时 由系统根据内存分配情况建立的 系统为每个装入主存的作业建立一张相应的页表 存储分块表MBT 页表PT 作业表JT JobTable 整个系统设置一张作业表 每个作业为一个表项 用于记录该作业的页表在内存中的起始地址 大小及状态等 逻辑地址到物理地址的转换 作业被调度时 系统从作业表 JT 中查找相应页表的起始地址和大小 装入页表控制寄存器 按页表起始地址查找页表 并对页号做合法性检查 合法