第五讲进程调度与线程概念

进程调度 CPU调度 要解决的问题WHAT 按什么原则分配CPU 进程调度算法WHEN 何时分配CPU 进程调度的时机HOW 如何分配CPU CPU调度过程 进程的上下文切换 处理机调度分成三个层次 处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响可把处理机调度分成三个层次 高级调度中级调度低级调度 高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟 小时或天中级调度涉及进程在内外存间的交换 从存储器资源管理的角度来看 把进程的部分或全部换出到外存上 可为当前运行进程的执行提供所需内存空间 将当前进程所需部分换入到内存 指令和数据必须在内存里才能被处理机直接访问低级调度也称微观调度 从处理机资源分配的角度来看 处理机需要经常选择就绪进程或线程进入运行状态 低级调度的时间尺度通常是毫秒级的 由于低级调度算法的频繁使用 要求在实现时做到高效 一 进程调度算法 1 进程调度进程调度的任务是控制协调进程对CPU的竞争 即按一定的调度算法从就绪队列中选中一个进程 把CPU的使用权交给被选中的进程 2 确定算法的原则 具有公平性资源利用率高 特别是CPU利用率 在交互式系统情况下要追求响应时间 越短越好 在批处理系统情况下要追求系统吞吐量 3 各种进程调度算法 先进先出进程调度算法 FIFO 按照进程就绪的先后次序来调度进程优点 实现简单缺点 没考虑进程的优先级 基于优先数的调度 HPF HighestPriorityFirst 优先选择就绪队列中优先级最高的进程投入运行优先级根据优先数来决定 确定优先数的方法静态优先数法 在进程创建时指定优先数 在进程运行时优先数不变动态优先数法 在进程创建时创立一个优先数 但在其生命周期内优先数可以动态变化 如等待时间长优先数可改变 两种占用CPU的方式 可剥夺式 可抢占式Preemptive 当有比正在运行的进程优先级更高的进程就绪时 系统可强行剥夺正在运行进程的CPU 提供给具有更高优先级的进程使用不可剥夺式 不可抢占式Non preemptive 某一进程被调度运行后 除非由于它自身的原因不能运行 否则一直运行下去 时间片轮转程序调度算法 RR RoundRobin 把CPU划分成若干时间片 并且按顺序赋给就绪队列中的每一个进程 进程轮流占有CPU 当时间片用完时 即使进程未执行完毕 系统也剥夺该进程的CPU 将该进程排在就绪队列末尾 同时系统选择另一个进程运行 分时系统中常用时间片轮转法 时间片选择问题 固定时间片可变时间片与时间片大小有关的因素 系统响应时间就绪进程个数CPU能力 多队列反馈调度算法 将就绪队列分为N级 每个就绪队列分配给不同的时间片 队列级别越高 时间越长 级别越小 时间片越小 最后一级采用时间片轮转 其他队列采用先进先出 系统从第一级调度 当第一级为空时 系统转向第二个队列 当运行进程用完一个时间片 放弃CPU时 进入下一级队列 等待进程被唤醒时 进入原来的就绪队列 当进程第一次就绪时 进入第一级队列 首先系统中设置多个就绪队列 每个就绪队列分配给不同时间片 优先级高的为第一级队列 时间片最小 随着队列级别的降低 时间片加大 各个队列按照先进先出调度算法 一个新进程就绪后进入第一级队列 进程由于等待而放弃CPU后 进入等待队列 一旦等待的事件发生 则回到原来的就绪队列 当有一个优先级更高的进程就绪时 可以抢占CPU 被抢占进程回到原来一级就绪队列末尾 当第一级队列空时 就去调度第二级队列 如此类推 当时间片到后 进程放弃CPU 回到下一级队列 二 进程调度的时机 当一个进程运行完毕 或由于某种错误而终止运行当一个进程在运行中处于等待状态 等待I O 分时系统中时间片到当有一个优先级更高的进程就绪 可抢占式 例如 新创建一个进程 一个等待进程变成就绪在进程通信中 执行中的进程执行了某种原语操作 P操作 阻塞原语 唤醒原语 三 进程切换 进程切换一个进程让出处理器 由另一个进程占用处理器的过程进程的切换使系统中的各进程均有机会占用CPU进程的切换是由进程状态的变化引起的 而进程状态的变化又与出现中断事件有关当有中断事件发生时 当前运行的进程被中断 中断响应后由操作系统处理出现的中断事件 中断处理后 某些进程的状态会发生变化 也可能又创建了一些新的进程 因此 要进行队列的调整 然后 进程调度根据预定的调度算法从就绪队列选一个进程占用CPU 这个占用CPU运行的进程可能仍是被中断的进程 也可能是另一个进程 何时切换进程 只要OS取得对CPU的控制 进程切换就可能发生 如 超级用户调用来自程序的显式请求 如 打开文件 该进程通常会被阻塞陷阱最末一条指令导致出错 会引起进程移至退出状态中断外部因素影响当前指令的执行 控制被转移至IH 中断处理程序 中断的例子 时钟进程用完其时间片 被转换至就绪状态I O先前等待该事件的进程被转换为就绪 或就绪挂起 状态然后重新运行该进程或选择一更高优先级的进程存储器因素内存地址是在虚拟存储器中 它必须把对应的存储块调入主存于是相应的进程成为阻塞状态 等待I O完成 四 CPU调度过程 保存现场 顺序保存 最后一步保存PSW 选择要运行的程序 如果没有就绪进程 系统会安排一个闲逛进程 idle 没有其他进程时该进程一直运行 在执行过程中可接收中断 恢复现场 最后一步恢复选中进程的PSW 在进程 上下文 中切换的步骤 保存处理器的上下文 包括程序计数器和其它寄存器用新状态和其它相关信息更新正在运行进程的PCB把原来的进程移至合适的队列 就绪 阻塞选择另一个要执行的进程更新被选中进程的PCB从被选中进程中重装入CPU上下文 二 系统核心 系统核心 向上提供多个无中断的虚拟机器在核心内不允许中断特点 为进程运行提供一个舞台 核心常驻内存 设计短小精焊 1 核心的组成 中断处理进程管理 调度控制通讯互斥同步等原语管理 在核心中提供一系列原语 同步 通信 创建 撤消等 队列管理 队列数据结构 指向队首的表指针三个队列 运行 就绪 等待队列排队方式 排队首排队尾插队出队方式 队首出队 队中出队队列管理 中断之后 进程调度之前 现场管理 保存现场 注意顺序 中断之后第一步恢复现场 恢复时机 进程调度最后一步时钟管理 以固定频率 1 1用途 进入绝对时钟间隔时钟进行分析比较 虚时钟 每个进程分配给一个虚时钟来记录CPU时间 这个时钟称为虚时钟虚时钟存放在PCB中 属于现场的一部分 进程运行时 将虚时钟放入内存开辟的专门单元 离开CPU则放在PCB中 2 核心处理流程 进入核心的唯一入口 中断中断后进入核心 由硬件完成 3 内核的执行特点 由中断驱动的 中断 内核 退出内核执行是连续的内核执行过程中在中断屏蔽状态下内核使用特权指令 三 线程的基本概念 线程的引入线程与进程的对比线程的实现实例 Solaris 1 线程的引入 进程的两个基本属性 资源的拥有者 给每个进程分配一虚拟地址空间 保存进程映像 控制一些资源 文件 I O设备 有状态 优先级 调度调度单位 进程是一个执行轨迹以上两个属性构成进程并发执行的基础 线程的引入 续1 系统必须完成的操作 创建进程撤消进程进程切换缺点 时间空间开销大 限制并发度的提高 线程的引入 续2 在操作系统中 进程的引入提高了计算机资源的利用效率 但在进一步提高进程的并发性时 人们发现进程切换开销占的比重越来越大 同时进程间通信的效率也受到限制线程的引入正是为了简化线程间的通信 以小的开销来提高进程内的并发程度 线程的引入 续3 线程 有时称轻量级进程进程中的一个运行实体是一个CPU调度单位资源的拥有者还是进程或称任务将原来进程的两个属性分开处理 线程的引入 续4 线程 有执行状态 状态转换 不运行时保存上下文有一个执行栈有一些局部变量的静态存储可存取所在进程的内存和其他资源可以创建 撤消另一个线程 线程和进程 单进程 单线程单进程 多线程多进程 一个进程一个线程多进程 一个进程多个线程 引入线程的好处 创建一个新线程花费时间少 结束亦如此 两个线程的切换花费时间少 如果机器设有 存储 恢复 所有寄存器 指令 则整个切换过程用几条指令即可完成 因为同一进程内的线程共享内存和文件 因此它们之间相互通信无须调用内核适合多处理机系统 例子1 LAN中的一个文件服务器 在一段时间内需要处理几个文件请求因此有效的方法是 为每一个请求创建一个线程在一个SMP机器上 多个线程可以同时在不同的处理器上运行 例子2 一个线程显示菜单 并读入用户输入 另一个线程执行用户命令考虑一个应用 由几个独立部分组成 这几个部分不需要顺序执行 则每个部分可以以线程方式实现当一个线程因I O阻塞时 可以切换到同一应用的另一个线程 2 线程与进程的比较 调度并发性拥有资源系统开销 3 线程的实现机制 用户级线程核心级线程两者结合方法 1 用户级线程 UserLevelThread 由应用程序完成所有线程的管理通过线程库 用户空间 一组管理线程的过程核心不知道线程的存在线程切换不需要核心态特权调度是应用特定的 线程库 创建 撤消线程在线程之间传递消息和数据调度线程执行保护和恢复线程上下文 对用户级线程的核心活动 核心不知道线程的活动 但仍然管理线程的进程的活动当线程调用系统调用时 整个进程阻塞但对线程库来说 线程仍然是运行状态即线程状态是与进程状态独立的 用户级线程的优点和缺点 优点 线程切换不调用核心调度是应用程序特定的 可以选择最好的算法ULT可运行在任何操作系统上 只需要线程库 缺点 大多数系统调用是阻塞的 因此核心阻塞进程 故进程中所有线程将被阻塞核心只将处理器分配给进程 同一进程中的两个线程不能同时运行于两个处理器上 2 核心级线程 KLT 所有线程管理由核心完成没有线程库 但对核心线程工具提供API核心维护进程和线程的上下文线程之间的切换需要核心支持以线程为基础进行调度例子 WindowsNT OS 2 核心级线程的优点和缺点 优点 对多处理器 核心可以同时调度同一进程的多个线程阻塞是在线程一级完成核心例程是多线程的缺点 在同一进程内的线程切换调用内核 导致速度下降 3 两者分析 针对不同的操作系统开销和性能 线程的调度和切换速度 系统调用 阻塞 线程执行时间灵活性可扩充性抢占CPU共享进程的资源 4 ULT和KLT结合方法 线程创建在用户空间完成大量线程调度和同步在用户空间完成程序员可以调整KLT的数量可以取两者中最好的例子 Solaris 4 实例 Solaris 进程 用户地址空间用户栈进程控制块 实例 Solaris 续1 用户级线程 线程库 可在应用进程中建立多个ULT每个ULT需要 栈 程序计数器不受调度程序的调度 线程切换快对操作系统不可见提供应用程序并行性接口 实例 Solaris 续2 核心级线程 设置了大量KLT有一个小的数据结构和栈完成内核的所有工作调度处理器的单位 其结构由核心维护 实例 Solaris 续3 轻型进程 LWP 每个ULT利用LWP与内核通信每个LWP支持一个或多个用户级线程 并映射到一个核心级线程每个LWP