操作系统第1章-第4章(华中科技大学版).ppt

操作系统原理 操作系统是如何工作的？ 为什么要学习操作系统？ 操作系统 裸机 应用软件 用户程序 操作系统的重要性 地位：操作系统是现代计算机、软件的基础 收获：通过学习操作系统的，我们可以： 掌握底层、大型软件的构造，及实现方法 2 掌握并行处理的思想 只有一个CPU在工作 如何使计算机同时完成多项任务呢？ 程序间合作的方法 如：多个独立的程序，合作完成一项复杂任务 如何正确地保证它们有序地执行呢？ 死锁的处理 一些复杂的系统常常会死机。 死机的原因有那些，和程序间的合作有关吗？ 为以后进行软件系统的开发，打好基础 3 了解操作系统的基本原理、概念 掌握操作系统的实现技术 通过实例的分析，培养解决问题的能力 如何学习操作系统 提问： 没有操作系统，计算机能否运行？ 计算机中为什么要配备操作系统? 4 配备操作系统的目的 管理各种软、硬件资源， 提高资源的利用率 方便用户使用计算机 (2)原理 并发处理：让一个CPU与所有的设备同时工作 二、操作系统 1.早期的操作系统 (1) 目标 提高CPU的利用率，将一个物理上的单处理机 改造成逻辑上的多处理机。为多个用户服务 (3)采用的软件技术 多道程序设计技术：多个程序在内存执行 2. 当今的操作系统及发展 (1)多样化 (2)注重用户操作界面的友好 (3)多处理机的并行处理 (4)嵌入式操作系统 (5)微软的观点 制定资源的分配策略及实施技术 解决程序之间的相互制约、及合作 引入虚拟机的概念 1.2 1.2 操作系统的形成和发展操作系统的形成和发展 （1）受应用 需求 的推动 （2）受硬件结构、软件技术的制约和推动 从时间上，可分为三个阶段： 形成、完善、发展 从硬件载体上，可分为三个主要的分支： 多用户操作系统 (大、中、小型计算机、服务器，研究的主体) 单用户操作系统(个人计算机) 嵌入式操作系统(无完整的计算机) 批处理(出现管理软件) 联机 批处理 脱机 批处理 执行 系统 操作系统形成 实时系统 多道程序系统 多道批 分时 处理系统 系统 手工操 作阶段 (无管理软件) 多处理机、多核 系统 单用户操作系统 网络操作系统 分布式操作系统 嵌入式操作系统 操作系统形成和发展的各个阶段 三. 多道程序设计技术 9 1、一个程序在内存的运行(单道程序设计) 用户程序 监督程序 IO操作 计算 请求输入 启动IO IO完成 继续计算 结束中断 中央处理机 外部设备 原因？ 空闲 解决方法：在内存中，存放多个可运行的用户程序 10 2、 多个程序在内存的运行(多道程序设计) CPU 打印机 输出 结束 程序B 打印 输出 绘图 输出 绘图 输出 输出结束 输出结束 程序A 输出 结束 程序A 程序B 打印 输出 绘图仪 空闲？ 11 (1) 什么是多道程序设计技术 在主存中同时存放几道相互独立的程序； 在管理程序控制之下，相互穿插地运行； 当某道程序不能继续运行时(如等待外部设备 传输数据)： 便将另一道程序投入运行。 12 (2) 多道运行的特征 多道 宏观上并行 微观上串行 执行系统采用多道程序设计技术后，就形成 了操作系统。 13 操作系统形成 批处理 手工操 作阶段 联机 批处理 脱机 批处理 执行 系统 实时系统 多道程序系统 多道批 分时 处理系统 系统 问题：只有一个CPU，在内存中运行的每一个程序 如何才能得到CPU 、并保持对其的占有的呢？ 14 1.什么是多道成批处理 所有的作业输入外存； 根据资源条件、及调度原则 选择一批作业进入内存 进入内存的作业按某种次序交替运行 当前运行的程序，只要不自动放弃CPU 就一直运行下去。 即： CPU不能被强行剥夺 第一种：系统不干涉程序的执行 四. 多道成批处理、及批量操作系统 15 2. 批量操作系统 采用多道、成批处理的操作系统，称为批量 操作系统。也称为批处理系统。 它是操作系统的一种基本类型。 作业运行的方式 系统把用户提交的作业送入计算机外存； 在适当的时机，由系统的作业调度程序在外 存选择一批作业，装入内存进行多道运行。 特点： 脱机操作(即：用户只需将程序提交给系统) 合理搭配作业 多道运行 16 优点： 资源利用率高、系统吞吐量大 缺点： (1)用户作业的周转时间长， 或对用户的响应时间慢； (2) 用户无法与程序交互，使用不方便 解决？ 第二种：由系统控制内存中各个程序的执行 17 五. 分时技术与分时操作系统 1. 分时技术 产生的原因：用户希望 能与程序交互、 有较快的响应时间快、甚至独占计算机 分时技术： 把处理机的时间划分成很短的时间片(如几百 毫秒)，轮流分配给各个联机的作业使用 如果某个作业在分配的时间片用完后，计算 仍未完成，就暂时中断执行，等待下一轮 18 作业i 作业i+1 作业n 作业i 提问： 与批处理相比，CPU的效率有没有降低？ 即：CPU的占用是可剥夺的。 19 3. 分时操作系统的特点 多路调制性 (一台主机与多个用户终端设备相连接) 独占性 交互性 作业运行的方式 一台计算机与多个终端设备连接 用户以联机的方式使用计算机 因此，也称为交互式系统。 20 六实时操作系统 什么是实时? 说明：实时处理，也可由分时操作系统 提供的实时处理功能来实现。 (实时用户优先使用CPU) 1. 实时操作系统的定义 对外部输入的信息 能够在很短的、规定时间内处理完毕 并作出反应的一种专用操作系统 21 2. 实时处理的类型 (1) 实时控制(必须物理实时) 如生产过程控制、作战指挥等。 (2) 实时信息处理(可以逻辑实时) 如订票系统、情报检索等。 3. 实时操作系统的特点 及时响应 高可靠性和安全性 系统的整体性强 22 批处理 手工操 作阶段 联机 批处理 脱机 批处理 执行 系统 操作系统形成 实时系统 多处理机、多核 系统 单用户操作系统 网络操作系统 分布式操作系统 嵌入式操作系统 多道程序系统 多道批 分时 处理系统 系统 操作系统的进一步发展操作系统的进一步发展 23 并行的方式： 流水线(一条指令分解为多个步骤) 向量机(一条指令同时在多个运算器上执行) 七 多运算器的单处理机系统 CPU 特点：一条指令在多个运算器上执行 目的：提高计算速度 适用性：适应面较窄，主要为专用 24 特点：CPU可分可合 分开：相当于多台主机 合作：提高计算速度(执行并行程序) 多核？ 八多处理机系统 cpucpucpucpu 25 网络操作系统除具备一般操作系统的功能 外，还要增加一个网络通信模块。 该模块由以下内容组成： 通信接口中断处理程序； 通信控制程序； 各级网络协议软件 十网络操作系统 26 5. 网络OS扩充的功能 (1) 节点间文件的复制、远程打印、电子邮件 (2) 联合文件系统 (3) 程序的远程执行(如通过Telnet进行远程登) 6. 不足之处 (1) 节点间相互独立 (2) 节点对用户不透明(CORBA有改进) (3) 要有一个集中管理的控制节点 操作系统是一个大型的程序系统 负责计算机的全部软、硬件资源的管理 即：资源的调度和分配 控制和协调并发的活动 实现信息的存取和保护 问题：操作系统是如何对资源进行管理的呢？ 为用户使用计算机提供接口 使用户获得一个良好的工作环境 1.3 1.3 操作系统的概念操作系统的概念 28 三、操作系统的资源管理功能 系统资 源分类 处理机主 存 I/O 设备 软件 资源 操作系统 功能模块 处理机 管 理 存储 管 理 设备 管 理 文件 系 统 29 1.4 OS的特性及应解决的问题 一、特性 并发 共享 不确定性 二、应解决的基本问题 、提出资源分配的策略 要考虑：利用率、公平、资源的特性 、协调并发活动的关系 原因：并发活动也存在直接、间接的制约 多个独立的程序，进行合作的要求 、保证数据的一致性 保证系统及用户的程序、数据不被破坏 避免与时间有关的错误 、实现数据的存取控制 操作系统的组织结构可从三个方面来描述 (1)系统的结构：系统功能的分组、及如何交互 (2) 接口：是用户、及用户程序使用系统的手段 (3) 运行时的结构：定义了系统运行过程中 存在的实体类型、及调用方式 2.2 2.2 操作系统的组织结构操作系统的组织结构 一、系统的结构化组织 操作系统是一组软件模块的集合。 为了满足系统的正确性、可维护性和性能的要求 其功能模块，通常可采用多种方法来进行组织 缺点： 结构不清晰，难于理解 难以维护、及验证正确性(因数据的交叉引用) 1. 一体化结构 操作系统的所有功能模块和数据结构，放在一 个逻辑模块中，任何子模块都不提供外部接口 应应用软软件 其他系统软统软 件 操作系统统功能模块块 内核功能 优点：通信开销小，系统效率高；安全性好 应用：OS问世后被许多系统采用 典型的代表是 UNIX系统，如： AT /* 参数的个数 */ int (*call)( ); /* 执行程序人口地址 */ sysent ; 系统初始化后，系统调用表如下： int sysent 0, nosys() u.u_error = 100; 是一个非法的系统调用(没有用到) 该系统调用，将返回一个系统调用失败的错误码。 更详细的细节见：P59：图3.5 4、系统调用的实现过程 6、系统调用执行的实例 (read) （1）C语言形式 char buffer int nbytes files=open(.) read( files, buffer, nbytes) （2）生成的部分汇编代码 (id=3) /*设置命令的操作数，为reab的功能号3 (files=r0) /*寄存器r0，专用于程序间传递第0个参数 sys id /*目标代码为：104403(即104400+3 ,见P58） buffer /*系统调用的第1个参数 nbytes /*系统调用的第2个参数 (a) 中断响应： 将当前进程的PC、PS的压入核心栈 中断向量：(034) = PC、 (036) = 340+6 =PS 转入俘获总控程序(入口地址为trap) (b) 俘获总控程序执行： 保护现场(包括：寄存器r0 = u.u_aror0 ) 由俘获类型: dev=6，转入系统调用分支程序 (3) sys 指令的执行过程 (c) 系统调用分支程序执行： 取系统调用功能号(即：sys 指令的操作数 3 ) 从system3，得到read的入口地址、参数个数 根据read的参数个数 2： 将断点后2个参数复制到当前进程的user区保存单元 u.u_arg0 、 u.u_arg1 将PC的值加4，使断点后移4个字节(2个指令字) (d) read子例程执行： 完成读操作后，实际传输数=u.u_aror0 作为返回值 (f) 俘获总控程序执行： 恢复现场，返回新断点自继续执行(或调度其他进程) (e) 系统调用分支程序 俘获总控程序 将user区中，u.u_aro0的值，复制到 r0 寄存器 (作为传递给子程序参数)，然后转read子例程 3.5 UNIX的命令程序设计语言shell 特点： 可将程序设计元素、与多个独立的UNIX执行 程序(或命令)组成一个shell过程，存放在一个文 件中(通常称为命令处理文件) 。 通过该文件，集成为一个逻辑整体(应用系统) shell过程中，可包括的程序设计元素主要有： 108 1. 变量 包括： 字符串变量 输入变量：用read从键盘读入其内容 shell过程的位置参数： $0，$1，$9 环境变量(用于获得环境信息)，包括： 用户注册名及主目录(用户的根目录)名、 检索存放信件的文件路径、 检查信件的时间间隔、 等等 109 2. 特殊符号 通配符： 、？ 符号列表 、 起始符 - 终止符 ！. 输入输出重定向符： 、 管道： 后台命令符： (2) 若首元素的等待时间为0，则： 从首节点开始 将等待时间为0的所有节点唤醒； 另外： 有的系统还允许在唤醒时执行一个函数 Linux中： 延迟时间用真实时间(绝对时钟间隔)表示 150 4. 5 4. 5 进程互斥进程互斥 由于共享资源，多个进程之间的间接制约还 有什么其他更一般的表现形式呢？ 结果有可能会交织在一起，很难区分 一、进程互斥的概念 1、临界资源 例1：设两个进程A、B 共享一台打印机。 若不加以控制，最终会打印出什么结果？ 151 例2：设服务器上有一个变量X ，初值为 0 代表某航班已卖出的机票数 P1 和 P2 为二个客户机上的售票进程 每卖出一张票，对服务器上的变量X加1 思考： 若二个售票进程各卖出了一张票 可能会出现什么结果呢？ 假定：二个进程并发执行，并分别先在自己的 内部寄存器 r1、r2 中，对变量的值进行处理 152 p2： r2:= x 0 r2 := r2+1； x := r2 ； 1 p1： r1:= r1+1 x := r1 ； 1 执行结果： x = 1 序列A(顺序) x值 P1 ： r1 := x； 0 r1:= r1+1； x := r1 ； 1 p2： r2:= x； 1 r2 := r2+1； x := r2 ； 2 执行结果： x = 2 二进程并发执行时的两种可能次序: 序列B (交错) x值 p1： r1 := x； 0 153 当多个进程共享这类资源时： 它们必须顺序地使用 即：只有一个进程用完后，其他进程才能使用 这一类问题应如何解决呢？ () 临界资源 将一次(一段时间内)仅允许 一个进程使用的资源，称为临界资源 具有这种性质的资源有： 硬件资源：输入机、扫描仪、打印机、绘图仪 软件资源：会修改的变量、表格、队列等 154 问题： 为了尽可能地实现多进程的并发运行 以提高资源的利用率，这段时间如何确定？ 最好是与该资源有关的部分程序段顺序地执行 是多个进程顺序地执行(依次创建进程)？ 还是多个进程的程序顺序地执行？ 或多个进程的部分程序段顺序地执行呢？ 通常将其称为封锁的“ 粒度 ” 155 (2) 临界区 在每个进程中 访问临界资源的那段程序 能够从逻辑上分离出来 称其为临界区、或 临界段 156 注意： (a)访问同一临界资源的多个进程 每个进程都有自己的临界段 而且其代码通常不相同 (b) 同一进程中，可能有 访问多个不同临界资源的多个临界段 (c) 只有访问同一临界资源的临界段 才需要相互制约 157 csA 进程A 进程C CScy Y=0 CScx X=X+10 进程B YY csB 例： 158 (3) 互斥 当某一进程正在访问某一临界资源时： 就不允许其他进程访问该资源 (否则，可能会发生后果无法估计的错误) 将进程间的这种相互制约关系，称为互斥 csA 进程A 进程C CScy Y=0 CScx X=X+10 例：进程A 、进程C并发执行 159 操作系统是如何保证临界段的互斥执行呢？ 对互斥处理的三原则： (1) 可进入性 (2) 排它性 (3) 有限性 进程之间是相互独立、并且互不可知的。 那么，当前执行进程 又是如何实现这些原则的呢？ 为此引入了锁的概念 二、锁、上锁及开锁操作 1. 什么是锁 用一个变量w (或二进制位) 代表某种资源的 状态(空闲、或被占用 ) ，称其为锁 2. 进程使用临界资源的步骤 (1) 上锁操作 检测 w 的值 如果w的值为1 (表示已上锁，资源被占用)： 则继续检测，直到锁打开 161 如果 w 的值为0 (表示未上锁，资源空闲) ： 将锁 w 置为1 (上锁防别人) (2) 进入临界区执行 (3) 开锁操作 临界资源使用完毕后，将锁置0 (开锁) 最 好 由 系 统 完 成 问题： 由谁来完成上锁、开锁的具体操作呢？ 162 3. 上锁原语和开锁原语 (1) 简单的算法 (a) 上锁原语 lock（w） test： if (w = 1) goto test *重复测试锁 else w = 1 * 上锁 163 (b) 开锁原语 unlock（w） w = 0 * 开锁 分析： 164 上锁原语： test： if (w = 1) goto test else w = 1 开锁原语： w = 0 思考：有没有什么问题呢？ 效率低：当锁已上时，当前执行上锁的进程忙等 无法实现：由于执行的是原语 当已上锁时，占着CPU的进程不断地测试锁 谁来开锁呢？死锁！ 如果不是原语呢？ 如何改进呢？ 165 (2) 改进算法的思想 采用上锁等待和开锁唤醒。 (b) 开锁原语 if ( 有进程等待) 唤醒等待的进程 w=0 * 开锁 基本的描述是： (a) 上锁原语 if ( w = 1) 调用进程等待 else w=1 * 上锁 思考： 假定有多个进程在等待，资源释放后： 根据唤醒算法，资源可能会先分给谁？ 被唤醒进程使用资源前，还要不要测试锁？ 该算法有没有可完善的地方？ 对改进算法的深入分析 4. 用上锁原语和开锁原语实现进程互斥 上 锁 临界区csb 开 锁 进程B 上 锁 临界区csa 开 锁 进程A 问题： (1) 若有多个不同的临界资源怎么办？ (2) 若有同一类型的多个临界资源又怎么办？ 168 4. 6 信号灯和 p、v操作 1. 什么是信号灯 信号灯可看作是一种广义的锁，它的结构是 一个二元组(S，q)。其中： S 是一个初值0的整型变量 表示同一类资源中，可用的资源数 q 表示该资源的等待队列，初始状态为空 由于每个 S 都对应于一个 q，因此在实用中 通常将 q 省略，直接将 S 称为信号灯 169 信号灯的用途： S 0：表示有S个资源 请求资源的进程可继续执行 S 0：表示无资源，请求进程必须等待 注意：创建信号灯时 应说明信号灯 S 的用途 定义信号灯 S初值(不能为负值。为什么？) 操作系统通过判别、改变信号灯的值，对多个 并发进程共享同一类的资源进行控制和管理 170 2. P、V操作的原语 信号灯S是受保护的特权变量(内核模式访问) 只能由系统的P、V操作原语来读、写 (1) P操作(可看作一种广义的上锁) 对信号灯S的 P操作记为 P(S)，定义为： (a) s = s 1 (b) 若s 0 ：调用P(S)的进程被阻塞 (c) 否则：返回调用的进程继续执行 ？ 171 P操作原语的算法描述 S= S 1； if ( S 0 ) 保留调用进程CPU现场 将该进程入S的等待队列 置为等待状态 转进程调度 唤醒后的执行点(以后不用再测试信号灯) 172 (2) V操作(可看作一种广义的开锁) 对信号灯S的 V操作记为 V(S) 定义为： (a) S = S + 1 (b) 若s 0 (有进程在等待)： 唤醒信号灯等待队列的首进程 (c) 返回调用V(S)的进程继续执行 173 V操作原语的算法描述 输入：变量S 输出：无 SS1； if (S = 0) 移出S等待队列的首进程 /*简单的FIFO 将该进程插入就绪队列 将该进程置为就绪状态 174 程序描述 main( ) mutex=1 * 互斥信号灯 * cobegin pa( ) pb( ) coend 3. 用信号灯实现进程互斥 例：二个进程Pa 、 Pb共享一个临界资源 175 pa( ) p(mutex) csa : 使用资源 v(mutex) 阻塞 pb( ) p(mutex) csb : 使用资源 V(mutex) mutex = 1 0 -1 176 (3)互斥信号灯的取值及含义 设N个并发进程互斥，信号灯mutex 的初值为1 mutex 的取值范围为：1 (N1)。含义为: 1：无进程进入临界区 有1个资源，无进程等待 0： 一个进程正在访问临界资源 无资源，无进程等待 i：一个进程正在访问临界资源 无资源，而且有i 个 进程等待 177 4. 7 4. 7 进程的同步进程的同步 多个并发进程合作，为了避免与时间有关的 错误，是否也存在着其他的直接制约呢？ 若有，它们又有哪些表现形式呢？ 一. 进程同步的概念 1. 什么是进程的同步 所谓同步，就是多个并发进程，在一些关键 点上需要互相等待(有次序限制)、互通消息。 2. 进程同步的例子 178 例：二个合作进程，循环共享一单位缓冲区buf 完成数据的处理。其中： 计算进程cp： 对数据进行计算后，结果送入 buf 打印进程iop： 从 buf 中取出结果后，再打印 正确性要求： 对一组结果数据，从 buf 中取出打印的次序 ，应与送入 buf 的次序相一致 缓冲区 iop cp 为了打印结果的正确， 二个进程的执行，有没有次序的限制? 180 二、执行次序确定(唯一)的进程的同步 图中用连接点表示： 对进程开始和结束的约束 如： 1. 执行次序已知的多个进程同步 若一组进程的执行次序是已知的 则可用进程流图来描述它们的执行时间轨迹 s f P5 P6 P7 P3 s f P4 P1 P2 p5 s f P9 P10 P8 182 例1：设 P1 、P2 、P3 、P 、 P 为一组合作进程 用信号灯的P、V操作实现这五个进程的同步 s f p2 p1 p3 p4 p5 问题： 用什么来表示资源呢? 183 s p1 p3 p4 f p2 p5 p5 : 等p1完成资源，不释放资源 p4 : 等P2、p3资源，不释放资源 p3 : 等p1资源，释放一个资源 P2: 不等资源，释放一个资源 p1 : 不等资源，释放二个资源 观察：有几类抽象的资源？ 分析：若一进程必须等待进程A完成后才能执行 则可将进程A的完成视为一类抽象资源 S1 S3 S2 因此，设3个同步信号灯： s1 、 s2 、 s3 分别表示 进程 p1、 p、 p是否完成 再观察：信号灯的设置， 有无规律？ 184 s p1 p3 p4 f p2 p5 S1 S2 S3 程序描述 main( ) s1=s2=s3=0 *分别表示 *进程p1、 p2、 p是否完成 cobegin p( ) p( ) p( ) p( ) p( ) coend 问题： 怎么对进程进行描述呢？ 185 s p1 p3 p4 f p2 p5 S1 S2 S3 P2( ) v(s2 ) p( ) v(s ) v(s ) p3( ) p(s) v(s3 ) p4( ) p(s2) p(s3 ) P5( ) p(s1 ) 再观察：进程的描述， 有无规律？ 思考：为实现控制， 至少要几个信号灯？ 最少信号灯 186 问题：若没有明显的次序，或难于画出次序如何解决？ 设计进程： P1: x1= a + b P2: x2= c + d P3: x3= x1 * x2 先画出进程流图，再实现同步 例2：在下列表达式中，每一步计算 由一个进程完成。画出进程流图， 并用p、v操作实现各计算进程的同步 ( ( a + b ) * ( c + d ) ) s f P1 P2 P3 程序描述： 画进程流图： 187 2. 共享一个缓冲区的合作进程同步 例：设一个计算进程cp、和一个打印进程 iop 共享一个单位缓冲区，完成计算与打印。 用信号灯的p、v操作实现两个进程的同步 io p cp 二进程的执行规律：交错执行(而且cp先执行) 559 8 7 6 566778899 执行次序： 可用次序图表示，但图、程序的描述都较繁琐 188 (1) 用缓冲区的状态为资源，进程的同步限制为 对cp进程 只有当buf为空时，才能将结果送入buf (即：开始、或iop进程已将数据取走) 否则，必须等待 对iop进程 只有buf内有数据时，才能从buf中取出数据 (即：cp进程把一个新的结果送入buf后) 否则，必须等待 对buf 的操作要互斥(缓冲区作为一个单位) 189 (2) 算法描述 将同步的限制看作资源，可设置信号灯： sa ：表示缓冲区中是否有新数据，初值为0； sb ：表示缓冲区有无空位置，初值为1； 先暂时不设置互斥信号灯，算法描述为： cp: 产生一个结果数据； p(sb)； 将数据放入buf v(sa)； iop: p(sa)； 从buf中取数据； v(sb)； 打印； 190 (3) 程序描述 main( ) int sa=0； *表示buf中有无数据 int sb=1； *表示buf中有无空位置 cobegin cp( )； iop( )； coend 191 cp( ) while(计算未完成) 产生一个结果数据； p(sb)； 将数送到缓冲区中； v(sa)； 考虑：是否实现了对缓冲区的互斥操作？ 是否实现了二个进程的同步？ iop( ) while(打印未完成) p(sa)； 从缓冲区中取数据； v(sb)； 在打印机上输出； 观察：信号灯的操作有什么规律？ 192 初始 Sa=0 Sb=1 iop( ) cp( ) CP CP执行V(sa)操作后 Sa=1 Sb=0 iop( ) cp( ) IOP CP 执行p(sb)操作后 Sa=0 Sb=0 iop( ) cp( ) iOP执行p(sa)操作后 Sa=0 Sb=0 iop( ) cp( ) 思考：若有多个CP和iOP进程，该模型是否适用？ 此时，iop能对缓冲区进行操作吗？ 不能，实现互斥的原因? 同样互斥 193 三、生产者消费者问题 问题的提出： 多个并发进程的同步，更一般的情况是： 存在某种次序限制，但这种次序又不唯一 若将这种限制理解为一种抽象的资源，则： 释放资源的进程可看作是一个生产者 占用资源的进程可看作是一个消费者 因此，可将多进程间同步的一般问题 抽象为资源(或产品)的生产和消费 194 1、生产者消费者问题的一般模型 (1) 有一个有界的多缓冲区(资源、限制) (2) 多个生产者，生产产品后，放入缓冲区 (3) 多个消费者，从缓冲区中取出产品后，进行消费 说明：共享一个缓冲区，可看作它的一个特例 c1p1 c2 c3 ck p2 p3 pm 195 2、生产者消费者的实例 (1) 多进程之间的通信问题 生产者(即发送消息进程 send)： 不断地产生消息 然后将消息送到消息缓冲区中 消费者(即接收消息进程 receive)： 不断地从消息缓冲区中取消息 然后对消息进行处理 196 (2) 通过缓冲区进行外部设备的输出(或输入) 生产者 (数据处理进程 cp)，重复完成： 每次将一个缓冲区写满后 将缓冲区插入到输出队列中 消费者(输出进程 iop)，重复完成： 每次从输出队列中取出一个缓冲区 将其内容输出到外部设备 197 3、同步限制(不是考虑次序，而是考虑规律) 对生产者的限制 当缓冲区中有空位置时： 可将产品送入缓冲区中 (不限定产品位置的次序，因为是抽象的模型) 对消费者的限制 当缓冲区中有产品时： 可从缓冲区取出产品 (也不限定位置的次序 ) 对buf 的操作要互斥 198 5、程序描述 main( ) int full=0 *满缓冲区信号灯 int empty= n *空缓冲区信号灯 int mutex=1 *缓冲区互斥信号灯 cobegin P ( i ) i =1,2 m /*也可分别 C ( j ) j=1,2 k /* 列出各个进程 coend 199 P( i ) i=1,2 m while(还要生产) 生产一个产品 C( j ) j=1,2 k while(还要消费) p(full)； p(mutex) 从缓冲区中取一个产品 v(mutex) v(empty) p(empty) p(mutex) 送一个产品到缓冲区 v(mutex) v(full) 消费一个产品 为什么要互斥： 可能有多个进程都有操作的权利 应防止多个进程操作，造成的与时间有关错误 200 思考: （1）若只有一个生产者和消费者 该模型是否适用？ （2）现实中，若要求送入数据的次序 与取出数据的次序相一致，应如何解决？ （3）两个P操作的次序是否不重要？ 交换次序后可能会出现什么问题？ Pi( ) Cj( ) while(还要生产) while(还要消费) p(mutex) 生产一个产品； p(full)； p(empty)； 从缓冲区中取产品； p(mutex)； v(mutex)； 送一个产品到缓冲区； v(empty)； v(mutex)； v(full)； 消费一个产品； 阻塞 阻塞 阻塞 当缓冲区全为空，一个消费者先执行时 这是一种什么样的问题呢？ 连续进行二次封锁，处理不当，就有可能造成死锁 . 202 p1( ) p2( ) while(生产未完成) while(还要继续消费) p(full)； 生产一个产品； p(mutex)； p(mutex)； 从缓冲区取产品； p(empty)； v(mutex)； 送一个产品到缓冲区； v(empty)； v(mutex)； v(full)； 消费一个产品； 也会产生什么死锁吗？在什么情况下会？ 203 解同步问题的5个要点 1. 确定同步类型 次序唯一、且无循环：次序图 ；否则： 互斥 共享一个缓冲区 生产者-消费者 2.设计信号灯(包括其他的附加限制) 3. 写 mand( )：定义信号灯、并赋初值( 0) 4. 用过程写进程的描述步骤（至少分为二步） 在受限制的程序段前进行P操作(一次或多次) 在受限制的程序段后进行V操作(一次或多次) 5. 检查，至少：P(Si)=V(Si) 例1：习题4.12(P116) 缓冲区S 缓冲区T getcopy put 缓冲区S copy get 5 4 3 2 1 5 4 3 2 1 缓冲区T put copy 共享一个缓冲区? 或生产者消费者问题? 5 4 3 2 1 任何同步的关键：都是避免与时间有关的错误 此题：可对各个局部考虑其正确性 main( ) int sa=0 *表示缓冲区S是否为满 int sb=1 *表示缓冲区S是否为空 int ta=0 *表示缓冲区T是否为满 int tb=1 *表示缓冲区T是否为空 cobegin get( ) copy( ) put( ) coend 206 get( ) while(还要计算) 产生一个结果数据 p(sb) 数据送缓冲区s中 v(sa) put( ) while(还要输出) p(ta) 从缓冲区t中取数据 v(tb) 在打印机上输出 207 copy( ) while(还要复制) p(sa) 取s中的数据 v(sb) p(tb) 将数据送到t中 v(ta) copy( ) while(还要复制) p(sa) p(tb) 将s中的数据复制到t v(ta) v(sb) 那一种算法的并发性好些呢？ 同步的类型，还能进行更深入的划分吗？ 典型1：读者写者问题(可互斥、共享的资源) 定义：一个数据对象(如文件、数据库表等) 可由多个并发进程读、写。 其同步限制是： (1) 当一进程正在写时： 其他进程不能读，不能写(反之亦然) (2) 当一进程正在读时： 其他进程能读，但不能写 分析：对写进程，互斥问题 对读进程，要区分三种可能的情形 第一个进程读之前： 申请资源(互斥问题) 第二个及以后的进程读之前：没有限制 最后一个进程读完后： 释放资源(互斥问题) 实现: (1) 写进程完成： 对数据对象进行封锁 将数据写入数据对象 解除对数据对象的封锁 (2) 读进程通过一个计数器完成： 计数器加1，设定自己的身份 若是第一个读者： 对数据对象进行封锁 读数据对象 完成后，计数器减1 若是最后一个读者： 解除数据对象的封锁 思考：程序的描述(特别是读进程)？ 同步的类型：对互斥问题的进一步扩展 思考题：过隧道的问题 东 西 思考：更完善的解法 （读者问题、或两边分批通过） 简单的解法 整体作为一个临界资源互斥 问题？ 典型2：哲学家进餐的问题 5个哲学家坐在餐桌旁思考问题 不与邻座的同事发生任何联系(相互独立) 饥饿时(随机，或定点开饭) 拿手边的筷子吃饭 一次只能拿一只筷子 只有拿到两只筷子后(二次封锁)，才能吃饭 否则，就必须等待 他们可能 会饿死吗？ 如何解决？ 0 1 4 3 2 解决办法：必须保证有一个人不参与争抢 但又不能将一个人置于死地，如何实现呢？ 0 1 2 3 4 (1) 0号哲学家先拿左边的筷子 其余的先拿右边的筷子 0 1 4 3 2 0、1 号哲学家，机会至少比平均数少一半 问题 ？ (2) 双号哲学家先拿左边的筷子 单号哲学家先拿右边的筷子。 问题？ 0 1 4 3 2 4号哲学家