os_ch2-1进程概念.ppt

1 第二章进程的描述与控制 2 主要内容 2 1前趋图和程序执行 理解 2 2进程的描述 掌握 2 3进程控制 理解 补充Unix进程模型 掌握 2 4进程同步 掌握 2 5经典的进程同步问题 理解 2 6进程通信 掌握 2 7线程 理解 2 8线程的实现 了解 3 Question 1 什么是进程 2 OS如何知道进程存在 3 用户能否控制进程 4 如何管理进程 提高CPU利用率 5 如何协调多个进程对处理机及其他系统资源的竞争和共享 6 如何预防 解决多个进程因竞争资源而出现故障 4 补充一相关硬件知识1 计算机的基本硬件元素 5 相关硬件知识2 与操作系统相关的几种主要寄存器 典型的用户可编程寄存器包括以下几种 数据寄存器DR地址寄存器AR条件码寄存器程序计数器PC指令寄存器IR程序状态字PSW中断现场保护寄存器过程调用用堆栈 6 相关硬件知识3 指令的执行与中断 中断执行过程 指令执行过程 7 相关硬件知识3 具有中断处理时的指令执行过程 8 相关硬件知识4 CPU的硬件特性 单处理机系统和多处理机系统CPU的构成 运算器 控制器 总线和相关寄存器CPU主要性能指标 主频 MIPSCPU工作方式 9 10 补充二用户对处理机的使用要求 是否并发 CPU管理内容或问题由何决定CPU管理功能共有三种模型CPU管理功能要完成的工作 11 CPU管理内容由何决定 硬件背景用户要求CPU数量和是否并发两因素影响最大 12 CPU管理功能共有三种模型 单任务模型 单处理机 多任务模型 单处理机或多处理机 进程模型线程模型 13 CPU管理功能的工作内容与任务 1 启动程序执行 将CPU交给用户程序使用 将程序装入内存置PCOS 装入程序 建立进程2 处理程序结束工作 将CPU的使用权从用户手中收回 程序结束系统调用指令中断OS 释放资源 返回结果信息或错误信息 返回父程序 14 CPU管理功能的工作内容与任务 3 提高对CPU的利用率 实现并发技术 实现多个程序对CPU的并发共享 OS 建立进程 进程切换 调度 进程通信4 向用户程序提供与CPU使用相关的用户接口操作系统提供的系统调用中与CPU使用相关的有 在一个程序中启动另一程序程序结束关于信号操作的一组系统调用等等5 在多CPU硬件背景下负责多个CPU登录 分配和通讯等管理工作 15 2 1前趋图和程序执行 2 1 1前趋图有向无循环图 用来描述程序各部分间的依赖关系或一个大的计算各子部分间的因果关系 前趋图中的元素 结点 表示一个语句 程序段 进程有向边 表示结点间的偏序关系 前驱关系 16 存在下面的前驱关系 P1 P2 P1 P3 P1 P4 P2 P5 P3 P5 P4 P6 P5 P7 P6 P7 17 例 下述四条语句的程序段画出前驱图S1 a x 2S2 b y 4S3 c a bS4 d c 6 18 1 程序的顺序执行程序概念程序执行 2 1 2程序顺序执行 19 举例1 顺序执行 两个程序P1 P2 P1执行序列 输入10ms 计算20ms 打印15msP2执行序列 输入20ms 计算10ms 打印20ms 20 2 程序顺序执行时的特征 顺序性封闭性 资源独占 可再现性缺点 资源利用率低解决 某资源被一个程序释放后 可分配给另一个程序 并发执行 21 2 1 3程序并发执行 程序并发执行时的前驱图前驱关系 22 1程序并发执行一组逻辑上相互独立的程序或程序段在执行过程中 其执行时间在客观上相互重叠 即一个程序段的执行 尚未结束 另一个程序段的执行已经开始的这种执行方式 23 2程序并发执行的特征 间断性程序在并发执行时 由于它们共享资源或为完成某一项任务而合作 致使在并发程序之间存在相互制约的关系 失去封闭性 资源共享 程序在并发执行时 是多个程序共享系统中的各种资源 因而这些资源的状态将由多个程序来改变 致使程序的运行失去了封闭性 24 不可再现性程序在并发执行时 由于失去了封闭性 也导致失去了可再现性 例如 有两个循环程序A和B 共享一个变量N 程序A N N 1 程序B print N N 0 假定某时刻变量N的值为n 程序并发执行的特征 25 执行结果 1 N N 1在print N 和N 0之前 此时得到的N值分别为n 1 n 1 0 2 N N 1在print N 和N 0之后 此时得到的N值分别为n 0 1 3 N N 1在print N 和N 0之间 此时得到的N值分别为n n 1 0 26 不可再现性 举例一个飞机订票系统可以有多个订票处的n个订票终端 假设n 2 公共数据区为Hi i 1 2 n 分别存放各次班机的现存票数 T1和T2表示售票终端的进程 R1和R2分别表示进程T1和T2执行时所需的工作单元 27 T1和T2进程的程序 T1 T2 BeginBegin按乘客需要查找到Hi 按乘客需要查找到Hi R1 Hi R2 Hi ifR1 1thenifR2 1thenbeginbeginR1 R1 1 R2 R2 1 Hi R1 Hi R2 售出一张票 售出一张票 endendelse 提示 票已售完 else 提示 票已售完 end end 28 补充程序并发执行的条件 1966年 Bernstein提出了相邻语句S1 S2可以并发执行的条件 如果并发执行的各程序段中语句或指令满足Bernstein的三个条件 则认为并发执行不会对执行结果的封闭性和可再现性产生影响 29 将程序中任一语句Si划分为两个变量的集合R Si 和W Si 其中R Si a1 a2 am 是语句Si在执行其间必须对其进行读取的变量W Si b1 b2 bn 是语句Si在执行其间必须对其进行修改 访问的变量如果对于语句S1和S2 有 R S1 W S2 W S1 R S2 W S1 W S2 同时成立即 R S1 W S2 W S1 R S2 W S1 W S2 则语句S1和S2是可以并发执行的 30 例 若有两条语句c a b和w c 1 判断它们是否可以并发执行 解 它们的 读集 和 写集 分别为R c a b a b R w c 1 c W c a b c W w c 1 w R c a b W w c 1 R w c 1 W c a b c 所以 两条语句不能并发执行 31 程序的顺序执行 程序的并发执行特征比较程序的顺序执行程序的并发执行1顺序性1间断性2封闭性2失去封闭性3可再现性3不可再现性 32 并发执行对OS提出更高要求 协调各操作执行顺序控制共享数据访问内存管理 选择多少 哪些执行 CPU管理 谁先执行 33 2 2进程的描述 进程的引入多道程序系统的特点是并发性 在多道程序系统所带来的复杂环境中 程序具有了并行 制约 动态的特性 原来的程序概念 难以刻画系统中的情况了 程序本身完全是静态的概念程序概念也反映不了系统中的并行特性 34 2 2 1进程的定义和特征1进程的定义 进程是程序的一次执行 进程是可以并发执行的计算部分 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 进程是具有独立功能的程序在一个数据集合上运行的过程 它是系统进行资源分配和调度的一个独立单位 进程是一个独立的可以调度的活动进程是一个抽象的实体 当它执行某个任务时 将要分配和释放各种资源行为的规则叫程序 程序在处理机上执行的活动称为进程 35 进程是进程实体的运行过程 是系统进行资源分配和调度的一个独立单位单位 P38 36 进程和程序的区别 1进程是一个动态的概念 进程的实质是程序的一次执行过程 动态性是进程的基本特征 同时进程是有一定的生命期的 而程序只是一组有序指令的集合 本身并无运动的含义 是静态的 2并发性 并发性是进程的重要特征 引入进程的目的正是为了使其程序和其它程序并发执行 而程序 没有建立进程 是不能并发执行的 3独立性 是指进程一个能独立运行 独立分配资源和独立调度的基本单位 凡未建立进程的程序 都不能作为一个独立的单位参加运行 不同的进程可以包含同一个程序 同一个程序在执行中也可以产生多个进程 37 2 进程的特征1 动态性动态性是进程最基本的特征 2 并发性指多个进程实体 同时存于内存中 能在一段时间内同时运行 3 独立性进程实体是一个能独立运行的基本单位 同时也是系统中独立获得资源和独立调度的基本单位 没有建立进程的程序 不能作为一个独立的单位参加运行 38 4 异步性进程按各自独立的 不可预之的速度向前推进5 制约性一个进程的执行可能要依赖其他相关进程的执行结果 形成进程之间的相互等待 6 结构性每个进程都有固定的结构 都由程序段 数据段和PCB三部分组成 39 进程的组成 进程的静态描述 由三部分组成PCB 有关程序段和该程序段对其进行操作的数据结构集 各部分的作用 1进程控制块 用于描述进程情况及控制进程运行所需的全部信息 2程序段 是进程中能被进程调度程序在CPU上执行的程序代码段 3数据段 一个进程的数据段 可以是进程对应的程序加工处理的原始数据 也可以是程序执行后产生的中间或最终数据 40 例题 例1 程序和进程是两个不同的概念 以下不能描述这个观点的是 A 程序指出了处理器执行操作的步骤 而进程是一个程序在一个数据集合上的一次执行 B 同一个程序运行10次 产生的是同一个进程 C 进程是动态的 是程序的执行过程 D 多个不同的进程可以包含相同的程序 41 例2 一个进程是 A 处理机一次或多次执行的一个程序 B 一个独立的程序 数据集 C PCB结构与程序和数据的组合 D 一个独立的程序 42 2 2 2进程的基本状态及转换 1 执行状态 Running 运行状态 指进程已获得处理机 其程序正在执行 在单处理机系统中 只能有一个进程处于执行状态 在多处理机中 可能有多个进程处于执行状态 43 44 2 就绪状态 Ready 当进程已经分配到除CPU以外的所有必要的资源后 只要能再获得处理机 就可以立即执行 这时的进程的状态称为就绪状态 45 46 3 阻塞状态 Block 等待状态 进程因为发生某个事件而暂停执行时的状态 如 请求I O 申请缓冲空间等 进程受到阻塞 称这种暂停状态为阻塞状态 有时也称 等待 状态或 睡眠 状态 47 48 4 进程三种状态间的转化 就绪 执行 调度 执行 等待 等待某个事件发生而睡眠 等待 就绪 因等待的时间发生而唤醒 执行 就绪 时间片用完 49 50 Question1 就绪 等待 等待 执行 51 52 Question2 一个只有一个处理机的系统中 OS的进程有运行 就绪 阻塞三个基本状态 假如某时刻该系统中有10个进程并发执行 在略去调度程序所占用时间情况下试问 这时刻系统中处于运行态的进程数最多有几个 最少有几个 这时刻系统中处于就绪态的进程数最多有几个 最少有几个 这时刻系统中处于阻塞态的进程数最多有几个 最少有几个 53 5创建状态和终止状态1 创建状态一个进程刚刚建立 但还没有将它送入就绪队列时的状态 2 终止状态当一个进程已经正常结束或异常结束 OS已经将它从就绪队列中移出 但还没有将它撤消时的状态 54 3 进程五种状态的转换对于一个进程 新状态 和 终止状态 只有一次 创建状态就绪状态 就绪状态执行状态 执行状态阻塞状态 执行状态就绪状态 执行状态终止状态 55 56 2 2 3进程的挂起状态 当终端用户在自己的程序运行期间 有时希望暂时使自己的进程静止下来 如果进程处于执行状态 则暂停执行 如果进程处于就绪状态 则暂时不接受调度 以便研究其执行情况或对程序进行修改 这种静止状态称为挂起状态 57 进程七种状态的转换在引入挂起状态后 又增加从挂起状态 又称静止状态 到非挂起状态 又称活动状态 的转换 或者相反 有以下几种情况 1 活动就绪静止就绪2 活动阻塞静止阻塞3 静止就绪活动就绪4 静止阻塞活动阻塞 58 具有挂起状态的进程状态图 59 2 2 4进程管理中的数据结构 1 操作系统中用于管理控制的数据结构进程 PCB 内存 分区表 页表 设备 设备控制表 控制器控制表 文件 文件控制块 目录 索引表 60 2 2 4进程管理中的数据结构 2 进程控制块的作用PCB ProcessControlBlock作为独立运行基本单位的标志能实现间断性运行方式提供进程管理需要的信息提供进程调度需要的信息实现与其他进程的同步与通信 61 2 2 4进程管理中的数据结构 3 进程控制块中的信息进程控制块中包括用于描述和控制进程运行的信息 1 进程标识符进程标识符用于唯一的标识一个进程 外部标识符 由创建者提供 通常是由字母 数字组成 往往是用户 进程 访问该进程使用 如 计算进程 打印进程 发送进程 接收进程等 内部标识符 在所有的OS中 都为每一个进程赋予一个唯一的整数 作为内部标识符 62 2 处理机状态处理机状态信息主要是由处理机各种寄存器中的内容所组成 通用寄存器 又称为用户可视寄存器 可被用户程序访问 用于暂存信息 指令寄存器 存放要访问的下一条指令 程序状态字PSW 其中含有状态信息 条件码 执行方式 中断屏蔽标志等 用户栈指针 每个用户进程有一个或若干个与之相关的系统栈 用于存放过程和系统调用参数及调用地址 栈指针指向该栈的栈顶 63 3 进程调度在PCB中还存放了一些与进程调度和进程对换有关的信息 1 进程状态 指明进程当前的状态 作为进程调度和对换时的依据 2 进程优先级 用于描述进程使用处理机的优先级别的一个整数 优先级高的进程优先获得处理机 3 进程调度所需要的其他信息 进程已等待CPU的时间总和 进程已执行的时间总和 4 事件 进程由执行状态转变为阻塞状态所等待发生的事件 阻塞原因 64 4 进程控制信息程序和数据的地址进程同步和通信机制资源清单链接指针 65 4 进程控制块的组织方式PCB表 系统把所有PCB组织在一起 并把它们放在内存的固定区域 就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数 称为系统的并发度 66 PCB的组织方式 常用的组织方式有两种 链接方式 索引方式 1 链接方式 具有相同状态的PCB 用其中的链接字 链接成一个队列 可以形成就绪队列 若干个阻塞队列和空白队列等 其中 就绪队列常按照进程优先权的大小排列 优先权高的进程的PCB排在队列前面 67 68 2 索引方式系统根据所有进程的状态 建立几张索引表 如 就绪索引表 阻塞索引表 把各索引表在内存的首地址记录在内存中的一些专用单元中 每个索引表的表目中 记录具有相同状态的某个PCB在PCB表中的地址 69 70 2 3进程控制 2 3 1操作系统内核OS内核 通常将一些与硬件紧密相关的模块 中断处理程序 各种常用设备的驱动程序 以及运行频率较高的模块 时钟管理 进程调度 都安排在紧靠硬件的软件层次中 使它们常驻内存 以便提高OS的运行效率 并对它们加以特殊的保护 这一部分称为OS内核 71 原语 primitive 有若干条指令组成 用于完成一定功能的一个过程 原子操作 一个操作中的所有动作要么全做要么不做 72 2 3 2进程的创建 1进程图进程图是用来描述进程家族关系的有向树 73 2引起创建进程的事件用户登录 在分时系统中 用户在终端键入登录命令后 若是合法用户 系统建立一个进程 并插入就绪队列 作业调度 批处理系统中 作业调度程序调度到某个作业以后 就把这个作业装入内存 并分配必要的资源 创建进程 插入就绪队列 提供服务 运行中的用户向系统提出请求后 系统专门建立一个进程为用户服务 打印请求 由操作系统核心 系统程序模块 创建应用请求 根据应用进程的需要 由它自己创建一个新进程 使新进程以并发运行方式完成特定任务 由父进程创建 74 3进程的创建过程 create 75 76 2 3 3进程的终止 撤消进程 1引起进程终止的事件正常结束 计算机系统中 都有一个表示进程已经运行完成的指示 批处理 Halt 分时系统中 LogsOff 异常结束越界错误 保护错 特权指令错 非法指令错 运行超时 等待超时 算术运算错 I O故障外界干预操作员或操作系统干预父进程请求父进程终止 77 2进程终止过程 78 79 2 3 4进程的阻塞与唤醒1引起进程阻塞的事件请求系统服务正在执行的程序请求操作系统服务 但是由于某种原因操作系统没有立即满足该进程的要求 该进程只能转变为阻塞状态来等待 启动某操作当进程启动某种操作后 如果该进程必须在该操作完成之后才能继续执行 所有必须先使进程阻塞 新数据尚未到达无新工作可做系统往往设置一些具有某特定功能的系统进程 每当这种进程完成任务以后便把自己阻塞起来等待新任务的到来 发送进程 80 2进程阻塞过程当有阻塞事件发生时 进程便调用阻塞原语block把自己阻塞 进入block后 应先立即停止执行 把进程控制块中的执行状态改为阻塞状态 并把它插入阻塞队列 3进程唤醒过程当阻塞进程所期待的事件出现时 则调用唤醒原语wakeup 将等待事件的进程唤醒 唤醒原语执行的过程是 首先把被阻塞进程从等待该事件的阻塞队列中移出 将其PCB中的阻塞状态改为就绪状态 然后把该进程插入到就绪队列中 Block和wakeup是一对作用刚好相反的原语 81 阻塞与唤醒 82 2 3 5进程的挂起和激活当出现了引起进程挂起的事件时 用户请求将自己挂起 或者父进程请求挂起自己的子进程 应该利用挂起原语suspend 挂起原语的执行过程 检查被挂起进程的状态 如果处于活动就绪状态 就将它改为静止就绪 如果处于活动阻塞 则改为静止阻塞 进程的激活过程当发生激活事件后 系统利用激活原语Active 将指定进程激活 激活原语先将进程从外存调入内存 然后检查进程的状态 静止就绪活动就绪静止阻塞活动阻塞 83 课后习题1 1 为什么要引入进程 进程是什么 2 进程生命周期内三种基本状态如何进行转换 从创建进程到进程终止 3 什么是PCB 有何作用 发送至邮箱qust os 84 实例研究 UNIX进程模型 1进程模型的基本结构和工作过程2进程状态及转换3UNIX的进程控制与管理4UNIX的进程层次和初启过程 85 UNIX的进程由三部分组成 proc结构 常驻内存的PCB 数据段 执行时用到的数据 正文段 程序代码 合称进程映像 UNIX中把进程定义为映像的执行 1进程模型的基本结构和工作过程 86 PCB由基本控制块proc结构和扩充控制块user结构组成 proc结构存放一个进程最基本 必需的信息 常驻内存 user结构存放进程运行时才用到的数据和状态信息 当进程暂时不在处理机上运行时 就把它放在磁盘的对换区中 87 系统中维持一张名叫proc的进程表 共有50个表目 每个表目为一个proc结构 供一个进程使用 最多同时存在50个进程 创建进程时 在proc表中找一个空表目 以建立起相应于该进程的proc结构 内存中设置一张text正文段表 有40个表目 每个都是一个text结构 记录一个共享正文段的属性 磁盘和主存中的位置 尺寸 共享的进程数等 正文段文件节点指针 88 进程映像的基本结构 89 1 进程基本控制块结构structproc charp stat 进程状态 charp flag 进程标志 charp pri 进程优先级 charp sig 软中断号 charp uid 用户号 charp time 驻留时间 charp cpu 进程占据CPU的时间量 charp nice 用于计算优先级 90 intp ttyp 控制终端tty结构的地址 intp pid 进程号 intp ppid 父进程号 intp addr 数据段地址 intp size 数据段大小 intp wchan 等待的原因 int p textp 对应正文段的text项地址 proc NPROC 91 p flag的助记符包括 SLOAD01在内存SSYS02进程0 SLOCK03锁住 不能换出内存SSWAP04正在换出STRC05被跟踪 92 p stat的助记符 UNIX系统 定义了10种进程状态 NULL0proc为空SSLEEP1睡眠SWAIT2等待SRUN3运行或就绪SIDL4创建时的临时状态SZOMB5僵死状态SSTOP6被跟踪SXBRK7因数据段扩展未满足的换出状态SXSTK8因栈段扩展未满足的换出状态SXFRK9创建子进程时内存不够 父进程锁定在内存的状态SXTXT10因正文段扩展未满足的换出状态 93 2 进程扩展控制块结构structuser intu rsav 2 保留现场保护区指针 charu segflg 用户 核心空间标志 charu error 返回出错代码 charu uid 有效用户号 charu gid 有效组号 intu procp proc结构地址 charu base 内存地址 char u count 传送字节数 char u offset 2 文件读写位移 94 int u cdir 当前目录I节点地址 char u dirp I节点当前指针 Struct intu ino charu name DIRSIZ u dent 当前目录项 intu ofile NOFILE 用户打开文件表 intu arg 5 存系统调用的自变量 intu tsize 正文段大小 95 intu dsize 用户资料区大小 intu ssize 用户栈大小 intu utime 用户态执行时间 intu stime 核心态执行时间 intu cutime 子进程用户态执行时间 intu cstime 子进程核心态执行时间 intu ar0 当前中断保护区内r0地址 96 3 正文段结构structtext intx daddr 磁盘地址 intx caddr 内存地址 intx size 内存块数 每块64字节 intx iptr 文件内存I节点地址 charx count 共享进程数 charx ccount 内存副本的共享进程数 text NTEXT 97 UNIX的进程状态及转换图 2进程状态及转换 98 3UNIX的进程控制与管理 1 创建进程UNIX系统中 进程分为两大类 系统进程和用户进程 系统进程执行操作系统程序 提供系统功能 例如资源分配 进程调度 99 用户进程执行用户程序 提供用户功能 0号是swap进程 系统自举时被创建 1号是init进程 由0号进程孵化而创建 其他进程都是1号进程调用fork 创建的子进程 fork系统调用生成一个新进程 新生成的进程称为子进程 生成新进程的进程为父进程 100 101 Fork举例 includemain intpid 0 printf theparentisgoingtofork n pid fork if pid 0 printf Iamthefatherof d pid elseprintf Iamthechild 运行结果 102 fork系统调用的工作流程 103 父进程创建子进程 104 fork程序实例分析 fork演示 105 fork 创建子进程 系统执行操作 为子进程分配进程表 为子进程分配进程标识符 复制父进程的进程映像 但不复制共享内存区 增加父进程所打开文件的计数 表示新进程也在使用这些文件 把子进程置为 就绪 状态 返回子进程标识符给父进程 把0值返回给子进程 fork 说明 106 父进程还应执行以下操作之一 以完成进程指派 继续待在父进程中 把进程控制切换到父进程的用户模式 在fork 点继续运行 而子进程进入 就绪 状态 把进程控制传递到子进程 子进程在fork 点继续运行 父进程进入 就绪 态 把进程控制传递到其他进程 父进程和子进程进入 就绪 状态 107 fork 说明 1子进程是父进程的复制品 完全一样2父子进程的指令执行点都在fork 语句之后的那个语句3fork 没有参数 但返回值pid不一样 子进程中pid为0 父进程中pid为非0正整数 即子进程的内部标识号 4父子进程可根据不同pid值执行不同程序 完成不同工作 108 父 子1 子2 main if fork 0 子1的代码段 else if fork 0 子2的代码段 else 父代码段 main if fork 0 子1的代码段 if fork 0 子2的代码段 else 子1的代码段 else 父代码段 109 例1 includemain intp x x 2 if p fork 0 printf thisisparent d x elseprintf thisischild d x 110 例2main fork fork fork 写出程序生成的进程树 A 111 例3main intpid printf Beforefork n while pid fork 1 if pid printf Itisparentprocess PID d n getpid printf Producechi