计算机操作系统许曰滨版第三章.ppt

1 第3章进程管理 2 本章主要内容 进程管理的基本概念进程控制块进程控制进程调度实时系统的进程调度线程 Thread 关于调度讨论 3 要点之一 操作系统为什么要引进 进程 到底什么是进程 进程有哪些特征 进程与程序 作业的关联与区别 进程管理模块要实现哪些功能 4 3 1进程管理的基本概念3 1 1程序的运行方式 顺序运行顺序运行方式是一种最容易实现的方式 常见于早期的单道批处理系统中 这种方式具有以下基本特征 l顺序特征 l独占特征 l确定性特征l可重现性特征 5 2 并发运行并发运行是多道程序系统中的一种运行方式 它允许多个程序共享CPU 以并发方式进行运算 在这种方式下 系统的资源不再被某一个程序独占 而是由多个程序共享 多道程序并发运行 指的是内存中同时活跃着多个用户进程 它们以CPU共享方式投入运行 6 并发运行方式的基本特征 异步特征资源共享特征相互制约特征不可重现性特征 7 3 1 2进程概念 进程 是程序的运行过程 是可以独立申请并获得系统资源 能够与其他进程并发运行的基本单位 进程具有以下5个特征 1 动态特征 2 并发特征 3 独立特征 4 异步特征 5 结构特征 8 3 1 3进程管理的主要功能 进程管理 是操作系统中最重要的组成部分 它的功能可大体分为两个方面 进程控制和进程调度 1 进程控制 创建新进程 撤消已结束的进程 阻塞或唤醒一个进程 挂起或激活一个进程 进程同步与通信控制 2 进程调度 根据进程当前状态决定哪个进程获得CPU 以及占用多长时间 将CPU分给进程 9 一般用户如何感知到进程 举例 10 ex1 c include include includeintmain intpid pid fork printf Hello n 11 要点之二 操作系统如何管理进程 PCB 进程状态 状态转换进程管理模块如何实现管理功能 进程控制原语进程调度进程的同步与互斥 第四章 12 进程控制块 一个进程在其生命周期中 需要经历多个发展阶段 每个阶段进程的推进位置 资源占有情况都在发生不断变化 为了描述不断变化的进程 系统引入一种与进程相联系的数据结构 进程控制块PCB 进程控制块PCB的内容包括以下4部分 进程标识调度信息处理机信息进程控制信息 13 1 进程标识进程标识是系统识别进程的标志 不同进程 其标识也不同 进程标识可分为外部标识和内部标识两部分 其中 外部标识 也称作进程的外部名 是进程的创建者提供的进程名字 通常由字符串组成 内部标识 也称作进程的内部名 简记为Pid 是系统为进程命名的一个代码 通常是一个整型数 14 2 调度信息 1 进程优先数 描述进程紧迫性的信息 2 进程状态信息 描述进程当前处于何种状态 3 其它调度信息 这部分信息有 进程在系统中等待的时间有多久 已在CPU上运行的时间是多少 剩余的运行时间有多少等 这些信息可帮助系统选择一个最迫切 最具运行条件的进程投入运行 15 3 处理机信息当一个进程运行过程中发生某些事件 使该进程运行不下去时 系统将剥夺它的CPU 交给别的进程使用 则 该进程的CPU现场信息可以保存在它自己的PCB内 以便该进程重新获得CPU时可以从此处恢复现场信息 继续运行 1 通用寄存器的内容 包括数据寄存器 段寄存器等 2 程序状态字PSW ProgramStatusWord 及程序计数器PC ProgramCount 值 3 进程的堆栈指针 16 4 进程控制信息这部分内容是系统对进程实施控制的依据 主要包括程序代码及数据集的相关说明 1 程序代码和数据集所在的内存地址 2 资源清单 记载进程请求资源的情况和已经占有资源的情况 3 同步与通信信息 4 外存地址 5 家族信息 6 链接指针 17 如Linux中PCB类型定义structtask struct unsignedshortuid intpid intprocessor volatilelongstate longpriority unsignedlongrt priority longcounter unsignedlongflags unsignedlongpolicy structtask struct next task prev task structtask struct next run prev run structtask struct p opptr p pptr p cptr p ysptr p ptr 18 3 2 2进程基本状态及状态变迁 一 进程的3种基本状态就绪 Ready 状态这是进程尚未获得CPU使用权的一种状态 在这一状态下 进程已经拥有除CPU外其它全部所需资源 因此该状态是一种 备运行 状态 运行 Running 状态这是进程获得CPU并投入运行的一种状态 事实上 在通常的单CPU系统中 每个瞬间最多只能有一个进程在运行 阻塞状态 BlockedStatus 这也是进程尚未获得CPU使用权的一种状态 在这一状态下 进程因某种要求得不到满足 只好等待 我们称之为运行 受阻 处于阻塞状态的进程是无权获得CPU的 19 进程的三种基本状态 20 1 后备 就绪当作业调度程序选中一个作业时 该作业就由外存装入内存 并被创建为进程 在大多数系统中 进程创建后的第1个状态是就绪状态 此刻进程已拥有所需的全部资源 只要获得CPU就可以运行 2 就绪 运行当进程调度程序按照某种算法 选中一个处于就绪状态的进程时 该进程就获得了CPU使用权 进程状态由 就绪 改为 运行 21 3 运行 阻塞一个正在运行的进程 因需要系统的某种支持 比如 等待输入输出或者等待系统的资源 那么该进程已无法继续运行下去 只好主动放弃CPU 将自己阻塞起来等待所需的事件发生 4 运行 就绪在一个按时间片进行轮转调度的系统中 当正在运行的进程使用完自己的时间片时 系统将中断该进程的运行 使它由 运行 状态转为 就绪 状态 显然 该进程已充分用完自己的时间片 剩余的运行只好等到下一个调度周期到来 在一个可抢占式调度系统中 如果有一个更高优先级的进程到来 系统将剥夺当前进程的CPU 交给更高优先级进程运行 当前进程只好由运行状态转为阻塞状态 22 5 阻塞 就绪当一个阻塞的进程遇到自己等待的事件发生 该进程便具有了运行的条件 进程控制模块将它由 阻塞 状态转为 就绪 状态 等待的事件包括 请求的资源已获得 等待的I O操作已完成 其它进程发来 唤醒 消息 及其它一些原因 6 运行 完成当正在运行的进程已经运行完自己的程序后 管理程序将收回它所占用的资源 比如 通过调用 存储管理模块 回收它所占用的内存空间 调用 设备管理模块 回收它所占用的外部设备 若当前进程的状态转为 完成 后 系统需要将CPU重新分配给他人使用 23 3 2 3扩展状态 挂起将内存中当前某个尚不能运行的进程调到外存上去 腾出来的空间接纳更多的进程 这一处理称作进程 挂起 Suspend 挂起状态挂起阻塞 S Blocked 状态挂起就绪 S Ready 状态 24 为什么要引入挂起状态 举一个例子 若系统的内存用户区有20M空间 收到的作业平均长度500K 每时刻可容纳的作业数量最多为40个 若每个作业平均执行104条指令将产生一次I O 相当于每次使用CPU运行0 1ms就需要等待20ms的I O时间 因此 CPU的利用率p可粗略地估算为 可以看出 处理机有近80 的时间是闲置的 25 加入挂起状态的进程状态转换图 26 Linux2 4版本中进程的6种状态 27 PCB队列结构 28 3 3进程控制 进程从产生到消亡的整个过程中都是由操作系统来控制的 操作系统中的一些功能程序来实现进程控制的使命 通常 这些离散的小程序块处于操作系统的底层 运行时不允许中断 我们习惯上称它们为 原语 29 原语 Primitive 是用机器指令构成的一种实现特定功能的小程序 它的运行具有不可分割性 l进程控制用的原语 这是一类实现进程管理和状态切换的原语 如 进程创建原语 进程撤消原语 阻塞原语 唤醒原语 进程挂起原语 进程激活原语 进程调度原语等 l进程通信用的原语 这类原语是用于实现进程之间通信的 如 消息发送原语 消息接收原语等 l资源互斥与同步用的原语 系统中的许多资源一次只能供一个进程使用 为了达到资源互斥访问的目的 系统需要设一组解决此类问题的原语 其中主要有P操作原语和V操作原语 l资源管理用的原语 主要有请求资源的原语和释放资源的原语 30 下面讨论各个控制进程状态装换的原语 1 何时执行 2 如何执行 31 3 3 1进程创建与撤消原语 进程创建原语何时 有以下4种事件会导致创建原语运行 批作业调度 批处理系统中 当系统准备增加新进程时 一个处于磁盘上的后备作业有可能被作业调度程序选中 将它创建为进程交互作业提交 在分时系统中 一个终端用户登录到系统 操作系统将创建一个与该终端相关联的终端进程 系统提供服务 操作系统创建一些为用户服务的进程 比如I O进程 这类进程的优先级要高于一般应用进程 用户需求创建子进程 现有进程根据运行需要创建一些子进程 使系统中形成了父子进程并发运行的格局 32 如何 进程创建原语Create Process 1 索取一个空白PCB块 2 填入进程信息 2 1填入进程标识 2 2PCB 优先级 赋予优先级或将JCB 优先级 填入 2 3PCB 内存地址 请求分配内存或JCB 内存地址 或父进程的内存地址填入 2 4PCB 资源清单 请求分配设备或JCB 资源清单 或父进程资源填入 2 5PCB 家族信息 用户名或父进程名 2 6PCB 现场信息 初始状态数据 2 7PCB 进程状态 就绪 3 挂入就绪队列 4 若需要将程序代码和数据集装入内存 可启动加载程序 33 2 进程撤销原语何时 进程撤销是进程创建的反过程 通常 有下列事件会导致进程撤消 1 进程自行终止 2 用户或父进程的原因使进程终止 3 运行超时而终止 4 运行出错而终止 34 如何 进程终止原语Destroy id name 1 根据id name查找被终止进程的进程控制块PCB 2 若该进程的状态是 运行 则置调度标志为TRUE 3 回收PCB 资源清单 中登记的全部资源 4 将进程的PCB从所在队列摘下来 等待其它程序来搜集信息 5 对于该进程的所有子进程Sub 递归调用End Process Sub 将子进程终止 6 如果调度标志 TRUE 启动进程调度程序 35 3 3 2阻塞与唤醒原语1 进程阻塞原语何时 当处于运行状态的进程需要等待某一事件时 由于运行受阻无法继续下去 该进程需要通过中断服务请求进入系统 系统按照进程的需求进行适当处理后 启动 进程阻塞原语 将该进程阻塞起来 引起进程阻塞 也就是运行受阻 的原因 等待I O请求资源得不到满足进程同步约束服务进程无服务任务 36 如何 阻塞原语Block 可以描述为下述过程 j GetInternalname Remove RunQueue j 从运行队列上摘下jj 进程上下文 CPU现场信息 j 状态 Blocked Insert BlockQueue j 将j插入阻塞队列上Scheduler 运行调度程序结束 37 2 进程唤醒原语 何时 当系统发生某一个事件时 正在等待该事件的进程需要立即被唤醒 由 阻塞 状态转为 就绪 状态 引起进程唤醒的原因源自进程的阻塞原因有 所等的I O操作已完成 请求的资源得到了满足 进程同步约束已撤消 服务进程收到新的任务 38 如何 唤醒原语Wake up 的功能过程 1 将当前进程的上下文保存到系统栈中 2 从阻塞队列上查找等待该事件的进程PCB 3 将PCB从阻塞队列上摘下来 4 将其状态置为 就绪 5 将PCB挂入就绪队列 6 弹出系统栈中的进程上下文 置入CPU 让被中断的进程恢复运行 7 结束 39 3 3 3挂起与激活原语 1 挂起原语何时 挂起的原因主要有 虚拟存储管理方式中 当前进程的内存空间太少根据操作系统的需要 将部分进程挂起 以便改善运行性能应用户的要求 将用户进程挂起应父进程要求 将其子进程挂起 40 如何 挂起原语Suspend 的功能过程 1 找到被挂起进程的PCB 2 将PCB从所在队列上摘下来 3 从中获得其内存空间地址 将内存空间归还给存储管理模块 4 若进程状态为阻塞 则将PCB状态置为 挂起阻塞 插入 挂起阻塞队列 若进程为就绪 则将进程状态置为 挂起就绪 插入 挂起就绪队列 5 申请外存交换区空间 将进程写到交换区上 并将交换区地址写入PCB 6 结束 41 二 激活原语 何时 当内存空间宽裕时 为了保证处理机将部分被挂起的进程激活 激活原因主要有 当一个进程运行完毕 若当前内存空间并不紧张 需要增加进程数量应用户要求 将其进程激活应父进程的要求 将将其子进程激活 或者进程自身设定的挂起周期已完成 42 如何 激活原语Active 可以描述为下述过程 1 扫描 挂起就绪队列 找到被激活进程的PCB 2 将PCB从所在队列上摘下来 3 按PCB登记的空间需求 申请内存 4 将该进程加载到内存中 5 归还外存交换区空间 6 若进程状态为 挂起就绪 则置为 就绪 插入就绪队列 否则 置为 阻塞 插入阻塞队列 7 结束 43 ex1 c include include includeintmain intpid pid fork printf Hello n if pid 0 printf Iamchild n else printf Iamparent n 44 3 5进程调度3 1 1进程调度分类 从调度方式上看 进程调度有两种类型 一种是非抢占式调度 另一种是抢占式调度 非抢占调度可能引起当前进程主动放弃处理机控制权的情况有两个 l进程运行完毕退出或遇到不可挽回的故障 l运行受阻 45 非抢占式调度运行示例 46 2 抢占调度 抢占调度也称作剥夺调度 主要指的是 在系统正常运转期间 如果某种事件出现 系统将迫使正在运行的进程停下来 将CPU控制权交给其它进程 抢占调度的思想源自对高紧迫度作业的响应 当一个紧迫性较高的进程到来 要求在限定的时间内做出响应 管理程序应及时停止正在运行的程序 将控制权交给紧迫性较高的进程 47 抢占式调度运行示例 表3 14个进程的创建数据 48 3 进程调度算法 lFCFS算法 先进入就绪队列的进程先调度 lSPF ShortestProcessFirst 算法 最短进程优先调度 lHPF HighestProcessFirst 算法 最高优先级调度 lHRF HighestResponseFirst 算法 最高响应比优先调度 lRR RoundRobin 算法 轮转调度 l多队列调度算法 l多级反馈队列调度算法 l最短剩余时间 SRT ShortestRemainTime 优先算法 49 RR算法 这是一种按时间片进行轮转调度的算法 当正在运行的进程用完自己的时间片后 管理程序停止它的运行 并将它转入就绪队列尾部 然后重新分配CPU 在这种情况下 进程失去CPU不是自愿的 而是被剥夺的 轮转算法的启动时机 一个时间片运行结束 当前进程运行结束 或者正在运行的进程因运行受阻主动放弃了CPU控制权 50 RR算法 51 时间片的选取 时间片的确定通常有下面几个原则 1 进程的道数较多时 q就选得小一些 反之 可选得大些 2 系统要求的响应时间比较苛刻的时候 q就选得小一些 反之 可选得大些 3 计算机的运算速度较慢的时候 q就选得小一些 反之 可选得大些 52 多就绪队列组织形式 53 多级反馈队列调度 54 多级反馈队列调度 1 设置n个队列Q1 Q2 Qn 2 记Qi的优先级为Pi 有P1 P2 Pn 3 记Qi的优先级为qi 有q1 q2 qn 4 新建进程进入Q1队 5 只有Qi为空时 才调度Qi 1中的进程 6 进程p在Qi中被调度执行 若时间片qi已到但尚未结束 则进程p转为就绪状态进入Qi 1队 进程p在Qn中被调度执行 若时间片已到但尚未结束 则进程转为就绪状态仍入Qn队 55 终端型用户满意 系统收到的终端型作业都是交互型的 通常比较小 当作业进入第1队列后 如果系统为第1队列规定的时间片比较合理 一般只要一个时间片就可完成 因而 会得到这部分终端用户的认可 短的批处理作业用户满意 对于短的批处理作业来说 开始时与终端作业一样首先进入第1个队列 得到与终端作业相同的响应时间 若轮转一周不能完成的话 通常只需在第2乃至第3队列上各执行一个时间片就可能完成 作业的周转时间仍比较短 因而 持有短的批处理作业的用户对系统的处理也是可以接受的 长的批处理作业用户满意 一个长批处理作业进入系统后 将依此在第1 2 n 1队列中各运行一个时间片 最后进入第n队列进行轮转运行 一般不必担心 受冷落 现象发生 56 3 5实时系统的进程调度 实时任务是一类对时间要求较为严格的任务 支持这类任务运行的系统称为实时处理系统 当此类任务到达系统后 系统应当按照任务的时间要求及时调度它 实时系统中的调度方式一般是剥夺式的 57 3 5 1实时任务的分类及其调度方法 紧迫型实时任务调度普通型的实时任务调度宽松型的实时任务调度非抢占的HPF调度算法RR算法 58 紧迫型实时任务调度 紧迫性强的任务多见于一些专用的 响应时间要求特别苛刻的数据采集和控制系统中 所要求的响应时间很短 一般是微秒量级的 解决的方法就是 采用 立即抢占的HPF 调度算法 普通型的实时任务调度 目前 大多数自动控制系统对响应时间的要求都不是太高 一般是毫秒量级的 由于它允许的响应时间长度与时钟中断的周期基本吻合 所以可采用 基于时钟中断抢占的高优先级调度 算法 59 60 宽松型的实时任务调度 宽松型实时任务要求的响应时间比较长 一般可达数百毫秒 甚至数秒钟 比如信息查询系统就属于此类任务 由于这类任务的要求差异很大 通常又有很多不同的处理 常见的算法有 1 非抢占的HPF调度算法 2 RR算法此类任务既可以进入批处理系统按上面说的高优先级算法进行调度 也可以作为交互型的任务 通过终端提交给系统 按时间片实行RR调度 61 3 5 2周期性任务调度 在一些信号检测和过程控制系统中 有许多任务呈现周期性的运行规律 比如 气象信息检测中每隔2小时要读取一次数据 我们将这类任务称为周期性任务 一个周期任务A第i次运行前的剩余时间FA i 的计算公式是 式中 TA为任务A的周期长度 TSA为任务A的每次执行时间长度 t为系统的当前时间 FA i 越小 说明任务的截止时间离当前时间越近 就越迫切 系统可以按照最小FA i 者优先原则进行调度 相应的算法称为SRT 最小剩余时间 调度算法 62 下面来看一个例子 周期任务A的周期长度为50ms 执行时间为10ms 次 松弛时间为40ms 任务B的周期长度为80ms 执行时间为20ms 次 松弛时间为60ms 63 两个周期任务的调度结果 64 周期任务的调度定理 对于单机系统中接收的n n 0 个周期任务 每个任务的周期长度为Ti 执行时间为Tsi 只有当下式成立时 系统有望实现调度 该定理明 在只有1台处理机的系统中 所有任务的运行时间与滞留时间之比的总和不能大于等于1 推而广之 在包含N台处理机的系统中 所有任务的这种比例之和不能大于等于N 65 3 6线程 Thread 3 1 1为什么引入线程在现代操作系统中 进程是一种庞大的结构型实体 其PCB结构包含的内容相当多 每当创建一个进程 系统无论在时间上或空间上都要花费较大开支 在管理和维护这些进程时 系统花费也不可忽视 另外 从运行角度看 当父进程将其子进程唤醒后 希望其子进程能立即运行 以完成交给的任务 而系统未必立即调度它 因为调度中采用的算法是从全局考虑的 这就使得进程对其子进程的运行完全不可预知 为此 提出了 轻量级进程 LightweightProcess 的概念 这就是线程 在支持多线程的操作系统中 线程被定义为调度运行的基本单位 而进程仅仅是资源分配和占有的实体 66 图3 16是P Kron于1990年给出一个在OS 2中用线程实现编辑排版的例子 该例中 服务线程完成初始化工作并负责自动流程控制 事件处理线程是一个事件响应程序 用户的鼠标移动或者键盘打字信号 都会激活它 屏幕重画线程需要保存原屏幕和用户新定义的屏幕 67 线程具有以下几个优点 提高运行效率和并发性 减少等待时间 加快响应时间 并使编程简化 可以取消进程级的中断 让线程来处理中断 而不是直接中断一个进程 线程的创建 终止 切换比进程的花费小 大部分情况下 前者的花费仅为后者的十分之一 线程之间进行通信的操作更简单易行 68 线程 多线程环境中的一个进程及其3个线程的模式 69 线程有两种不同的类型 内核级线程 KLT 和应用级线程 ULT 70 3 6 3内核级线程 采用内核级线程技术的好处是 内核级线程调度可以针对 对称多处理 SMP SymmetricMultiprocessing 结构 将同一个进程的多个线程同时调度到多台CPU上去并行运算 内核级线程的管理和控制耗时较小 据T Anderson等人1992年在单处理机VAX上运行Like UNIX的测试结果 内核级线程的耗时平均比进程的低一到两个数量级 当然 它比用户级线程要高一个数量级 当一个线程执行了一个系统调度后被阻塞起来 同一进程中的其它线程仍会照常运行 这一点 在用户级线程中是做不到的 71 3 6 4用户级线程 采用用户级线程的好处是 管理线程的数据结构都在用户地址空间中 线程的切换不需要内核访问特权 从而减少了在两种模式之间切换的开销 各个应用程序可采用适合自己的专用线程调度算法 比如有的可能采用高优先级调度 而有的可能是简单的循环调度 这些算法仅适应应用程序而不会对内核中的进程调度产生影响 用户级线程可以在各种操作系统中运行 只要装有一个可共享的应用级上的实用程序库 线程库就可以了 72 本章结束