计算机软件及应用

第二讲进Q179412340重点 进程的并发执行 进程的状态及切换 处理机对进程的调度算法难点 FCFS 优先级调度算法 时间轮转法 短进程优先调度算法 最短剩余时间调度算法 最高响应比调度算法 一 程序的顺序执行和并发执行1 程序的顺序执行 程序的顺序执行 具有独立功能的程序独占CPU直至得到最终结果的过程 如 单道批处理系统 顺序环境 计算机系统中只有一个程序在运行该程序独占系统中所有资源其执行不受外界影响 顺序执行的特征顺序性 按照程序结构所指定的次序 可能有分支或循环 封闭性 独占全部资源 计算机的状态只由于该程序的控制逻辑所决定 不受外界影响 可再现性 初始条件相同则结果相同 如 可通过空指令控制时间关系 程序执行结果的确定性 程序运行结果与程序执行速度无关 只要初始状态相同 结果应相同 现在的操作系统多为并发执行 具有许多新的特征 引入并发执行的目的是为了提高资源利用率 2 程序的并发执行程序的并发执行 指一组在逻辑上互相独立的程序或程序段在执行时间上客观上互相重叠 即一个程序或程序段的执行尚未结束 另一个程 段 的执行已经开始的方式 并发执行的特征间断 异步 性 走走停停 一个程序可能走到中途停下来 失去原有的时序关系 失去封闭性 共享资源 受其他程序的控制逻辑的影响 如 一个程序写到存储器中的数据可能被另一个程序修改 失去原有的不变特征 失去可再现性 失去封闭性 失去可再现性 外界环境在程序的两次执行期间发生变化 失去原有的可重复特征 并发程序执行的结果与其执行的相对速度有关 是不确定的 资源共享 系统中资源被多个程序使用个并发程序间独立的相对速度 起始时间程序之间可相互作用 相互制约 可分为直接作用和间接作用 并发执行的优点 并发程序 并发环境 一定时间内 物理机器上有两个或两个以上的程序同时处于开始运行但尚未结束的状态 并且次序不是事先确定的 引入并发的目的 为了提高资源利用率 从而提高系统效率 并发程序示例有两个进程A B 如图所示 在顺序环境下 A先执行 B再执行CPU利用率 40 80 50 DEV1利用率 15 80 18 75 DEV2利用率 25 80 31 25 在并发环境下CPU利用率 89 DEV1并发环境下利用率 33 DEV2并发环境下利用率 66 二 进程2 1进程定义 进程由以下几个方面组成 1 一个可执行程序 包括初始代码和数据2 一个独立的用户地址空间3 系统资源 由OS分配给进程的系统资源 包括 I O设备 文件等4 进程运行及处理机调度进程切换时所要涉及到的数据 进程 一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程 简言之 进程是程序的一次执行活动 在现在操作系统中 用户程序以进程方式占用系统资源 操作系统负责创建进程 为进程分配资源 调度进程占用处理机等 进程描述了程序的动态执行过程 反映系统中程序执行的并发性 随机性和资源共享多进程 提高了对硬件资源的利用率 但又带来额外的空间和时间开销 增加了OS的复杂性 2 2进程特征 动态性 进程对应程序的执行进程是动态产生 动态消亡的进程在其生命周期内 在基本状态之间转换独立性 各进程的地址空间相互独立 除非采用进程间通信手段 并发性 任何进程都可以同其他进程一起向前推进异步性 每个进程都以其相对独立的不可预知的速度向前推进 进程控制块 processcontrolblock PCB 由操作系统管理控制进程而使用的标识和特性信息集合称之为进程控制块 processcontrolblock PCB 每个进程对应一个PCB 一个PCB包含以下信息 1 进程标识信息 本进程的标识 本进程的产生者标识等 2 进程运行的现场信息 进程运行所需的数据或地址寄存器等 3 进程控制信息 进程的状态信息 进程优先级 进程存储管理信息等 进程执行完后 进程从系统退出 其所对应的PCB也随之消失 2 3进程 与程序的区别 进程是动态的 程序是静态的 程序是有序代码的集合 通常对应着文件 静态和可以复制 进程是程序的执行 进程是暂时的 程序是永久的 进程是一个状态变化的过程 程序可长久保存 进程与程序的组成不同 进程的组成包括程序 数据和PCB processcontrolblock进程控制块 进程与程序的对应关系 通过多次执行 一个程序可对应多个进程 通过调用关系 一个进程可包括多个程序 举例 正在运行的Web浏览器是一个进程 正在运行的Windows资源管理器是一个进程 正在运行的VisualC 编程环境也是一个进程 2 4进程 并发示例 3个进程并发执行的图示 假设处理机正在执行A 程序计数器 PCProgramcounter 为了保证程序 在操作系统中理解为进程 能够连续地执行下去 程序计数器 指令计数器 在程序开始执行前 必须将它的起始地址 即程序的一条指令所在的内存单元地址送入PC 因此程序计数器 PC 的内容即是从内存提取的一条指令的地址 当执行指令时 CPU将自动修改PC的内容 即每执行一条指令PC增加一个量 这个量等于指令所含的字节数 以便使其保持的总是将要执行的下一条指令的地址 由于大多数指令都是按顺序来执行的 所以修改的过程通常只是简单的对PC加1 单进程的轨迹 进程的轨迹 trace 一个进程的执行指令序列 用于描述单个进程的行为 3进程并发执行的轨迹 理解处理器的行为 如何在三个进程间交替执行 规定 每个进程仅允许最多连续执行6个指令周期 之后被中断 避免独占 A B C dispatcher dispatcher dispatcher A C I O请求 2 5进程的状态 新建状态 new 刚刚创建的进程 辅存中 就绪态 Ready 一个进程已经具备运行条件 但由于无CPU暂时不能运行的状态 当调度给其CPU时 立即可以运行 既一个进程获得了除处理机之外的一切所需资源 位于 就绪队列 中执行态 Running 进程占有了包括CPU在内的全部资源 正在CPU上运行 在单机环境下 每一时刻最多只有一个进程处于运行状态 等待态 阻塞态 waiting Blocked 指进程因等待某种事件的发生而暂停运行的状态 暂停时不占用处理机 即使CPU空闲 该进程也不可运行 位于 等待队列 中 终止 退出状态 Exit 终止后进程移入该状态 它不再有执行资格 终止可能是正常结束也可能是中途终止 导致进程状态转换的事件类型 状态转换 在进程运行过程中 由于进程自身进展情况及外界环境的变化 基本状态可以依据一定的条件相互转换导致进程状态转换的事件类型NuLL 新建 创建执行一个程序的新进程新建 就绪 OS准备好了接纳一个进程 进程进入内存 为该进程分配除处理机之外的一切资源 就绪 运行 OS调度程序从就绪队列选择一个新的进程运行 占据CPU 运行 就绪 运行进程用完了时间片 不得不让出处理机的使用权运行进程被更高优先级进程中断 被更高优先级进程剥夺了处理机 因为一高优先级进程处于就绪状态运行 阻塞 当一进程等待某一事件的发生时 如 OS尚未完成系统服务调用 对一资源的访问尚不能进行 初始化I O且必须等待结果 等待某一进程提供输入 IPC 阻塞 就绪 当进程所等待的事件发生时 进入就绪队列 重新等到处理机的调度 进程状态转换图 进程在OS内用PCB表示 processcontrolBlock PCB是进程的属性之一 包含 进程控制信息 调度和状态信息 进程状态 优先级 与调度有关的信息 数据结构 队列等 进程间通信 进程特权 内存管理信息 I O状态信息 2 7进程控制块PCB 2 8进程操作 创建和终止 创建进程给新进程分配一个唯一的PID 在基本表中增加一个项目给进程分配空间 进程映像 PCB初始化PCB设置正确的连接 置入相应队列中创建或扩充其他数据结构 如记帐文件等 导致进程创建的事件新的批作业 批处理系统中 交互登录 分时系统 OS为提供一项服务而创建由已有的进程生成 用户进程规定创建的 并发执行 提交一个程序执行父进程 子进程 进程树 进程何时中止 程序执行Halt指令用户退出登录进程执行一个中止服务请求出错及失败因素 进程中止的原因 正常结束给定时限到缺少内存存储器出界保护性出错例子 写只读文件算术错超出时间进程等待超过对某事件的最大值 进程中止的原因 I O失败无效指令如试图执行数据特权指令操作系统干预如当死锁发生时父进程请求中止某一子进程父进程中止 所以子进程也中止 进程在执行过程中 能通过系统调用创建多个进程子进程资源的获得 物理资源 CPU时间 内存 I O设备 文件 初始化数据 或者输入数据 创建新进程后 父进程与子进程并发执行 2 9进程操作 创建 三 CPU对进程的调度 多道程序的关键是调度 对CPU资源进行合理的分配使用 以提高处理机利用率 并使各用户公平地得到处理机资源 处理机调度是OS的重要功能之一 WHAT 按什么原则分配CPU 进程调度算法WHEN 何时分配CPU 进程调度的时机HOW 如何分配CPU CPU调度过程 进程的上下文切换 处理器调度的类型 处理器调度对CPU资源进行合理地分配使用 以提高CPU的利用率 使各用户公平地得到CPU资源 处理器调度的目标以满足系统目标 如响应时间 吞吐率 处理器效率 的方式 把进程分配在一个处理器或多个处理器上执行 处理器调度的准则 面向用户的准则响应时间 min 周转时间 min 结束时间 进入系统时间 从进入系统直至完成所经历的时间 面向系统的准则吞吐量 max 系统在单位时间内完成的作业数 CPU利用率 max 公平资源的平衡使用系统开销 min 3 1处理器调度的分级 1 长程调度 高级调度 作业调度 决定从外存的批处理队列中选择哪个 些 作业被系统接收做进一步运行 并为它们创建进程 分配必要的资源 作业一旦被高调选中 相应的进程及进程组才会产生 才能去占用系统资源 进程状态 创建长程调度程序决定OS可以接纳一个还是多个进程创建的进程越多 每个进程执行时间百分比就越小 每当一个进程终止时或空闲时间片超过了一定的域值 调度程序可能会决定增加一个或多个新进程 或调用长程调度程序 2 中程调度 中级调度 决定将哪些进程调入内存 为占用处理机做好准备 当然也会有一些进程被剥夺内存的使用权 将进程的部分或全部加载到内存中 提高内存利用率 进程状态 创建就绪3 短程调度 低级调度 进程调度 分派程序dispatcher 决定就绪队列中哪个进程将获得处理机 选择哪个进程在处理机上执行 执行最频繁 进程状态 就绪运行当可能导致当前进程挂起或可能剥夺当前正在运行的进程的事件发生时 调用短程调度程序 包括如下事件 时钟中断 I O中断 操作系统调用 信号 用于调度的队列图 批作业 CPU 释放 超时 短程调度 内存就绪队列 就绪 挂起队列 阻塞 挂起队列 阻塞队列 事件等待 事件发生 交互用户 长程调度 中程调度 3 2进程调度算法 基本类型 非抢占调度 NonPreemptive 就绪进程不可以从运行进程手中抢占CPU 一旦进程处于运行状态 它就不断执行直到终止或者为等待I O或请求某些操作系统服务而阻塞时 才把CPU让给另一进程 特点 系统开销小 但当一个紧急任务到达时 不能立刻投入运行 实时性差 如 有三个进程P1 P2 P3先后到达 它们分别需要20 4 2个单位时间运行完毕 若它们按照P1 P2 P3的顺序执行且不可剥夺 则三个进程各自的周转时间为20 24 26个工作单位 抢占调度 Preemptive 某个进程正在运行时可以被系统以某种原则剥夺已分配给它的处理机 将处理机分配给其它进程 允许调度程序根据某种策略中止当前运行进程的执行 将其转移到就绪状态 并选择另一个进程投入运行 时机 一个新进程到达时一个中断的发生将一个被阻塞进程置为就绪态周期性的时间中断 比较 抢占策略可能会导致较大的开销 但是可对所有进程提供较好的服务 避免任一个进程独占CPU太长时间通过使用有效的进程切换机制以及提供比较大的主存 使得大部分程序都在主存中 剥夺的代价可以相对比较低 3 3调度算法 先来先服务FCFS 先来先服务FCFS First Come First Served 按照进程进入就绪队列的先后次序选调度 FCFS属于不可抢占策略 一旦一个进程占有了处理机 它就一直运行下去 直到该进程完成工作或因等待某事件而不能运行时才能释放除处理器 评价非抢占调度对于长进程有利 而不利于短进程 有利于CPU繁忙型的进程 而不利于I O繁忙型的进程不能用于分时系统 改进FIFO自身对于单处理器系统并不是很有吸引力 通常与优先级策略结合 维护多个队列 每个优先级一个队列 每个队列采用FCFS的方法 如反馈法 最短作业优先 shortest job first SJF 原则 非剥夺的 从进程的就绪队列中挑选那些所需运行时间最短的进程进入主存运行 如果两个进程剩余时间相同 则使用FCFS来调度 SJF是一个非抢占的策略 它一旦选中某个进程后 就保证该进程尽可能快地完成运行并退出 问题 需要知道或至少需要估计每个进程所需要的处理时间 通常一进程没有这方面的信息 只能估计 评价 有利于短进程 可以证明 SJF算法平均等待时间最小长进程就可能被饿死 只要有持续不断的短进程存在 缺少剥夺机制 不适用于对分时系统或事务处理环境 最短剩余时间调度SRT shortestremainingTimer SRT 原理 对SJF增加了剥夺机制 将SJF算法用于分时环境 从就绪队列中选择进程运行到完成时所需时间最短的进程优先得到处理 它可能比当前运行的进程具有更短的剩余时间 只要满足条件的新进程就绪 调度程序就进行剥夺 优点 既不偏爱长进程 也不像RR算法那样会产生额外的中断 从而减少了开销 周转时间方面 SRT比SJF性能要好 短作业可以立即被选择执行 SRT问题 需要知道或至少需要估计每个进程所需要的处理时间 只要有持续不断的短进程存在 长进程就可能被饿死它必须记录过去的服务时间 从而增加了开销 优先级调度 优先级每个进程都有一个优先级 调度程序总是选择具有较高优先级的进程 静态优先级 static 优先数在进程创建时分配 生存期内不变 响应速度慢 开销小 适合批处理进程动态优先级 dynamic 进程创建时继承优先级 生存期内可以修改 响应速度快 开销大 问题低优先级的进程可能会饿死 无穷阻塞 如果一直有高优先级的就绪进程的话 改进一个进程的优先级随着它的时间或执行历史而变化 老化策略 aging 轮转调度RR RoundRobin 轮转调度 或称时间片调度 timeslicing 其就绪队列按进程达到的时间来排序 以一定的时间间隔周期性产生一个时钟中断 当中断