计算机科学与技术专业段雪丽—操作系统.pdf

操作系统 授课教师：段雪丽 信息工程学院 计算机科学与技术教研室 TRANSITION PAGE 2.1 2.2 2.3 前趋图和程序的执行 进程的描述 进程控制 2.4 2.5 2.6 2.7 2 进程通信 进程同步基本概念 经典的同步问题 线程及其实现 目 录 页 本节课 主要内容 重点： Ø 进程的并发执行 Ø 进程特征 Ø 进程状态转换 Ø 进程控制块 难点： Ø 进程管理中的数据结构 3 第一节 2.1.1 程序的顺序执行及其特征 前趋图及程序的执行 程序的顺序执行:一个具有独立功能的程序,独占处理机直至得到最终结 Ø 果的过程,称为程序的顺序执行。（一个较大的程序通常都由若干个程序 段组成。程序在执行时，必须按照某种先后次序逐个执行，仅当前一操 作执行完后，才能执行后继操作。） 1) 程序段按固定的流程执行下去 例1：输入I，计算C，打印P 2) 语句的顺序执行 例2： S1: a=x+y S2: b=a-5 S3: c=b+1 4 第一节 2.1.1 程序的顺序执行及其特征 前趋图及程序的执行 Ø 程序顺序执行时的特征 (1) 顺序性 处理机的操作严格按照程序所规定的顺序执行。 (2) 封闭性 程序一旦开始执行，其计算结果不受外界因素的影响。即程 序运行时独占全机资源，资源的状态（除初始）只有本程序才能改变它。 (3) 可再现性 程序执行的结果与它的执行速度无关(即与时间无关)，而 只与初始条件有关。 5 第一节 2.1.2 前趋图 前趋图及程序的执行 Ø 引入前趋图描述程序执行的先后顺序：为了描述一个程序的各部分 （程序段、语句）间的依赖关系，或是一个大的计算的各子任务间的 因果关系，采用前驱图方式。 6 第一节 2.1.2 前趋图 前趋图及程序的执行 • 有向无循环图 • 节点用于表示一个进程或一段程序 • 节点之间用一个有方向的线段相连 • 方向表示所连接的节点之间的前趋和后继关系 • 节点间的有向边则表示两个结点之间存在的偏序(Partial Order)或前趋关 系(Precedence Relation)“→” • 被指向的节点为后继节点，离开箭头的节点是前趋节点。 （Pi,Pj)→ 可写成Pi→Pj,表示Pi必须在Pj前完成 7 第一节 2.1.2 前趋图 前趋图及程序的执行  G={P, → }  P={P1, P2, P3, P4, P5, P6, P7, P8, P9}  →={ (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9)} 8 第一节 2.1.2 前趋图 前趋图及程序的执行 P2 P4 P1 P6 P3 P7 P5 9 第一节 2.1.2 前趋图 具有循环的前趋图 前趋图及程序的执行 前趋图中是不允许有循环的，否则必 然会产生不可能实现的前趋关系。 S2→S3，S3→S2 10 第一节 2.1.3 程序的并发执行及其特征 前趋图及程序的执行 1) 程序并发执行 Ii Ii+1 Ci Ci+1 Pi Pi+1 Ii Ci Pi 前趋关系Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1，而Ii+1和Ci及Pi-1是 重叠的，即在Pi-1和Ci以及Ii+1之间，不存在前趋关系，可以并发执行。 11 第一节 2.1.3 程序的并发执行及其特征 前趋图及程序的执行 2) 程序并发执行时的特征 (1) 间断性（制约性） (2) 失去封闭性 (3) 不可再现性 12 第一节 2.1.3 程序的并发执行及其特征 前趋图及程序的执行 2) 语句的并发 S1: A=X+2 S2: B=Y+1 S3: C=A+B S4: D=C-6 S1 S3 S4 S2 13 第一节 2.1.3 程序的并发执行及其特征 前趋图及程序的执行 对于下述五条语句的程序段： S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+b S5: e:=d+3 14 第一节 顺序执行与并发执行的特征 前趋图及程序的执行 完成前一操作才能 进入下一操作 初始条件相同，结果唯一 (执行次数和执行速度与结果无关) 程序顺序执行的特征 １)顺序性 ２)封闭性 ３)可再现性 资源的状态只能由执行程序改变(运行时程序独占资源) 执行 暂停 程序并发执行时的特征 原因：相互制约（直接/间接） １)间断性 ２)失去封闭性 ３)不可再现性 资源被共享，状态由多个共享者改变 15 第一节 程序并发执行带来的问题: 前趋图及程序的执行 不可再现性 程序A N=N+1 情况Ａ 程序B N=N+1 情况Ｃ PRINT(N) PRINT(N) PRINT(N) N=0 N=N+1 N=0 N=N+1 N=0 Ｎ值为： ０ １ ０ 打印结果： Ｎ＋１ Ｎ Ｎ PRINT(N) N=0 情况Ｂ 16 第一节 程序并发执行带来的问题: 前趋图及程序的执行 余额： 余额： 1000 1000 读取余额1 读取余额1 读取余额2 取500 取200 保存余额1 保存余额2 余额： ？ 800 读取余额2 存500 保存余额1 ？ 取1500 17 第一节 程序并发执行带来的问题: 前趋图及程序的执行 程序并发执行，虽然能有效地提高资源利用率和系统的吞吐量， 但必须采取某种措施，以便并发程序能保持其“可再现性”。 程序并发性的分析 1)如何使程序并发(行) 2)并发中出现的问题 3)如何处理 任务能否并发，不但取决于算法，还与程序 的结构形式有很大关系，并行的方法: 在标准语言的基础上加以扩充 重新设计专门的并行语言 18 第二节 2.2.1 进程的定义和特征 进程的描述 ？ 为什么要引入进程？ 为了使内存中的多道程序能够正确地并发执行， ？ 为什么程序不能并发执行？ 因为并发执行的程序是“停停走走”地执行，会失去封闭进而结果不可再现。因此， 人们引入“进程”（Process）这一概念来描述程序动态执行过程的性质并加以记 录，实现可再现性，即进程就是操作系统为进行处理机管理而引入的概念。 为了使参与并发执行的每个程序（含数据）都能独立地运行，在操作系统中必须 为之配置一个专门的数据结构，称为进程控制块PCB，当程序停下时，能将其现 场信息保存在它的PCB中，待下次被调用执行时，再从PCB中恢复CPU现场而继 续执行。进而PCB、程序段和数据是进程的核心内容。 19 第二节 2.2.1 进程的定义和特征 进程的描述 进程的定义 异步性 进程都是并发的 进程的定义：进程是可并发执行的、具有独立功能的程序在一定数据集 合上的一次执行过程，是操作系统进行资源分配和调度的基本单位。 组成：程序+数据 独立性：资源的拥有者和CPU调度的分配者 一次性+动态性 创建/撤消 进程是一个程序及数据在处理机上顺序执行时所发生的活动（执行的过程） 书中的定义 进程是进程实体的运行过程，是系统进行资源分配 和调度的一个独立单位。 20 第二节 2.2.1 进程的定义和特征 进程的描述 相同的程序可以多次运行，每 进程的理解： 次运行的环境可能不相同。这种多 –进程是程序运行过程 次运行可以发生在同一时间段中。 操作系统通过进程的数据结构了解 –进程是以异步为主要特征并具有“活力”的过程 虽然进程是程序运行，但是 进程的详细信息，采用进程管理的方法 进程与程序却不能完全等同。程 –操作系统需要用数据结构描述进程 实现对进程运行轨迹的控制。 进程的异步特征的表现形式是进程推进过 序是静态的，是以文件形式存放 程中的“走走停停”，某一进程被别的进程切 –进程的运行轨迹是可以控制的 在磁盘上的代码序列。 操作系统为了管理进程，对每个进 换又切换其他的进程； –进程是资源分配的单位 进程是动态的，是不断向前 程都有一个数据结构用来描述进程的 在以进程为基础的操作系统 进程的每一步执行都是一个向前推进的过 推进的过程，进程具有各种状态 详细信息，该数据结构根据进程的动 中，系统资源以进程为单位进行 –进程与程序不同 程，是具有“活力”的过程。 并可以在状态之间转换。 态过程不断更新。 分配。系统资源包括各种硬件资 源和软件资源，特别是处理器资 源。 21 第二节 2.2.1 进程的定义和特征 进程的描述 进程包含有描述进程信息的数据结构和 进程的特征：运行在进程上的程序。操作系统用进程控制 –结构性 块描述和记录进程的动态变化过程。进程的 进程是程序在数据集合上的一次执行过 数据结构至少包含进程控制块、程序块和代 –动态性 程，具有生命周期，由创建而产生，由调度 码块。 在同一段时间内，若干个进程可以共享 –并发性 而运行，由结束而消亡，是一个动态推进的 一个处理器。进程的并发性能够改进系统的 过程。 –独立性 资源利用率，提高计算机的效率。 在操作系统管理上，进程是一个独立的 –异步性 资源分配单位，进程可以在创建时获取资源， 在计算机环境中，处理器的数量总是小 也可以在运行过程中获取资源。操作系统为 于进程的数量，多个进程被强制分享同一个 进程分配各种资源，如处理器和内存地址空 处理器，进程以交替方式被处理器执行。进 间等。 程的这种执行方式为异步性。 22 小结 程序 顺序 执行 时的 特征 程序 并发 执行 时的 特征 1)顺序性 前一操作完成才能进入下一操作 2)封闭性 运行时独占资源,结果不受外界影响； 即资源的状态只能由本程序改变 3)可再现性 初始条件相同，结果唯一(结果与程序的 执行次数和速度无关（停—走—停—走） 1)间断性 出现执行——暂停——执行这种间断性的活动规律 原因：相互制约（直接／间接） 2)失去封闭性 资源被共享，状态由多个共享者改变 3)不可再现性 初始条件相同，结果不唯一 (结果与执行程序的速度相关） 23 小结 进程的定义：进程是可并发执行的、具有独立功能的程序在一定数据集 合上的一次执行过程，是操作系统进行资源分配和调度的基本单位。 进程是程序的执行过程,创建而产 生﹑调度而执行﹑撤消而消亡 按各自独立的、不可预知的速度向前推 进，导致程序执行的不可再现性。 １)动态性 ２)并发性 ３)独立性 进程可以并发执行,而程 序却不能 ４)异步性 ５)结构特 征 进程实体由程序段、数据段和进程控制 块组成,又称为“进程映像”。 独立运行／资源分配／调度的基本单位 24 小结 进程与程序的区别 动态 静态（定义） 暂时性（具有生命期） 永久性 并发性、独立性、结构特征 程序都没有 程序+数据+PCB块 程序+数据 一个进程可以涉及多个程序 一个程序可以对应多个进程 异步运行，会相互制约 程序不具备此特征 （不同的进程可以包含相同的程序） 25 第二节 2.2.2 进程的状态及其转换 进程的描述 Ready： 该进程运行所需的一 切条件都得到满足，但因 处理机资源个数少于进程 个数，所以该进程不能运 行，而必须等待分配处理 机资源，一旦获得处理机 就立即投入运行。 26 第二节 2.2.2 进程的状态及其转换 进程的描述 Running： 进程正在处理机上 运行的状态，该进程已 获得必要的资源，也获 得了处理机，用户程序 正在处理机上运行。 27 第二节 2.2.2 进程的状态及其转换 进程的描述 Blocked: 进程等待某种事件 完成（例如，等待输入 /输出操作的完成）而 暂时不能运行的状态， 处于该状态的进程不能 参加竞争处理机，此时， 即使分配给它处理机， 它也不能运行。 28 第二节 2.2.2 进程的状态及其转换 进程的描述 状态变化： 就绪状态 → 执行状态 执行状态 → 就绪状态 执行状态 → 阻塞状态 阻塞状态 → 就绪状态 29 第二节 2.2.2 进程的状态及其转换 进程的描述 创建状态是指操作系统创建进程时，进程所处的状 态。进程新建成功后即转入就绪状态，在就绪进程队列中 排队。 操作系统创建进程需要为进程分配资源。因此，操作 系统将根据系统的性能和内存容量的情况决定是否创建新 进程达到了结束点或进程出现了严重的错误时， 的进程。如果系统性能较差或内存容量受到限制，不能为 会被操作系统终止或被其他有终止权的进程终止。 新进程分配资源，则操作系统会发出创建新进程失败的响 应或将创建新进程的工作推迟。 进入终止状态的进程不再被执行，等待操作 系统完成进程终止处理。当操作系统完成进程终止 处理后，操作系统会删除进程，收回进程所占用的 资源。 30 小结 执行状态 释放 终止 中断(时间片用完) 进程调度 创建 许可 就绪状态 所等待事件发生 （如I/O完成） 等待事件发生 （如等待I/O或请求I/O） 阻塞状态 执行态：此时正用CPU； 就绪态：可运行,但未分到CPU； 阻塞态：不能运行,等待某个外部事件发生。 在一定条件下,进程状态才发生转换 31 第二节 2.2.3 挂起操作和进程状态的转换 进程的描述 终端用户可以直接操作自己的程序。  挂起状态 当程序员需要调试、检查和修改自己的程 • 系统资源的需要 序时，可以要求挂起与程序相对应的进程， 某些定期执行的进程，如系统监控进 暂停进程的推进。 • 调节竞争或消除故障的需要父进程对自己的子进程实施控制、修 程、日志进程等，在执行时间未到而需要 当系统中所有的进程均处于阻塞状态 • 终端用户的需要 改和检查时，需要挂起自己的子进程，暂 等待时，可以将进程挂起，对换到外存， 时，没有就绪进程，处理器处于空闲。如 停子进程的推进。 • 父进程的需要 从而减轻内存负担。当执行时间到时，再 操作系统在检查进程运行中竞争资源 果这时内存空间已经被进程占满，不能装 将这些进程激活换入到内存。 的情况时，或在系统出现故障使某些功能 • 调节进程的需要 入更多的进程，需要将内存中处于阻塞状 受到破坏时，为了解决进程的资源竞争或 态的进程挂起，对换到外存上，让出内存 消除系统故障，操作系统需要挂起某些对 空间接纳新创建的进程。 资源竞争的进程或怀疑引起系统故障的进 程，将进程对换到外存。 32 第二节 2.2.3 挂起操作和进程状态的转换 进程的描述 “挂起”的实质是使进程不能继续执行，处于静止状态，而没被挂起的进程 称为活动状态。处于静止状态的进程，只有通过“激活”动作，才能转换 成活动状态。 挂起 内存 激活 磁盘 “挂起”常被用于进程对换中，挂起的进程从内存对换到外存，以便腾出更多 内存空间接纳新创建的进程。常将内存中处于阻塞状态的进程挂起。 进程只能由操作系统，父进程，进程自身挂起 33 度 CP O 求 I/ 放 调 时 间 片 完 起 U 挂  活动就绪 → 静止就绪 激活  活动阻塞 → 静止阻塞  静止就绪 → 活动就绪 挂起 释  静止阻塞 → 活动阻塞 放 激活 释 进程的描述 终止 请 第二节 2.2.3 挂起操作和进程状态的转换 挂起 图2-7 具有挂起状态的进程状态图 34 小结 进程可以在：新建，就绪，阻塞，运行状态被挂起。 进程只能由操作系统，父进程，进程自身挂起 挂起 进程状态转换 35 第二节 2.2.4 进程管理中的数据结构 进程的描述 OS中用于管理控制的数据结构 OS的内存 占用部分 内存表 进程 设备表 文件表 是进程的唯一实体,系统根据PCB块而感知进程的存在,即PCB块是进程存在 的唯一标识。 进程实体 (进程映象) 程序代码 数据 PCB块 36 第二节 2.2.4 进程管理中的数据结构 进程的描述 进程控制块中的信息 通用寄存器﹑指令寄存器 程序状态字﹑用户栈指针 进程状态﹑ 优先级﹑调度所需的其 它信息﹑阻塞原因 外部标识符 内部标识符 程序和数据地址﹑进程同步和进程 通信机制﹑资源清单﹑链接指针 创建时用户指定 OS唯一指定 37 第二节 2.2.4 进程管理中的数据结构 PCB的作用 进程的描述 进程的创建 异步性 状态的转变 进程管理 同步和通信 OS不同，PCB的长度不一(时空开销) OS的内存 占用部分 内存表 1）线性表 进程 2）链接方式 设备表 文件表 3）索引方式 38 第二节 2.2.4 进程管理中的数据结构 进程的描述 PCB的组织方式： PCB块号 指针 PCB 1 4 1）PCB线性队列示意图 PCB 2 3 PCB 3 5 PCB 4 8 PCB 5 6 PCB 6 7 PCB 7 9 PCB 8 2 PCB 9 X PCB块指针 39 第二节 2.2.4 进程管理中的数据结构 进程的描述 2）PCB链接队列示意图 执行指针 PCB1 PCB2 PCB3 就绪队列指针 PCB4 4 3 0 8 PCB5 阻塞队列指针 PCB6 PCB7 PCB8 空闲队列指针 PCB9 7 9 0 1 ... 40 第二节 2.2.4 进程管理中的数据结构 进程的描述 链接方式  优点 直观，体现了进程的本身特性，如等待时间的长短、优先级的高低、需要 处理时间的长短，为进程调度算法的实施提供了方便。  缺点 以链接方式组织进程控制块的主要缺点是如果进程状态发生变化，则链接 队列需要作相应的调整，进程控制块中的首部和尾部指针需要改变。 41 第二节 2.2.4 进程管理中的数据结构 进程的描述 执行指针 就绪队列 单CPU时 就绪索引表 PCB 1 PCB 2 PCB 3 PCB 4 3)按索引方式组织PCB ………. 阻塞队列 阻塞索引表 PCB 5 PCB 6 …… …… ………. PCB的查找和修改都在索引表中进行 PCBn 42 第二节 2.2.4 进程管理中的数据结构 进程的描述 索引方式  优点 • 通过索引表可以快速得到进程控制块地址，不需要像链接方式一样，从链首到 链尾查找； • 如果进程状态变化，不需要修改进程控制块的链接指针，只需要增加或删除索 引表中的记录。  缺点 • 索引表本身需占用内存空间； • 搜索索引表需要时间。 43 第二节 2.2.4 进程管理中的数据结构 进程的描述 内存映像  是进程在内存中的组成  包括如下内容： • 进程程序块 • 进程数据块 • 系统或用户堆栈 • 进程控制块 进程程序块为执行的程序代码， 规定了进程一次运行需要完成的功能。 进程运行时的全局变量、局部变 量和常量等的存储区以及开辟的工作 区。 每个进程捆绑的系统/用户堆栈， 用来解决过程调用或系统调用时的信 息存储和参数传递。 进程的标志信息、处理机状态信 息、进程调度信息、进程控制信息。 44 第二节 2.2.4 进程管理中的数据结构 进程的描述 进程上下文  进程的物理实体和支持进程运行的环境合称为进程上下文（ process context）。 • 用户级上下文（user-level context） • 系统级上下文（system-level context） • 寄存器上下文（register context）。 由进程的正文区、数据区、用户 由进程控制块、内存管理信息、 栈区和共享存储区组成，在编译目标 进程环境块和系统堆栈等组成的进程 文件时生成，占据进程的虚拟地址空 由程序状态寄存器、各类控制寄 地址空间。 间。 存器、地址寄存器、通用寄存器和用 户栈指针等组成。 45 第三节 小结 进程控制 是进程的唯一实体,系统根据PCB块而感知进程的存在,即PCB块是进程存在的唯一 标识。 进程实体 (进程映象) 程序代码 数据 PCB块 46 第三节 2.3 进程控制 进程控制 n进程管理最基本的功能 n一般由OS内核中的原语实现 n包括： 00 00 进程创建 进程终止 00 进程阻塞与唤醒 00 进程挂起与激活 47 第三节 2.3.1 进程的创建 进程控制 n 进程具有层次结构 A n 创建新进程是通过创建原语完成的，被创建 B C 的进程称作子进程，而创建子进程的进程则称 作父进程。子进程又可以创建自己的子进程， 从而形成一棵有向的进程树，即进程图 • 关系 D I E J F K G L H M • 子进程可以继承父进程的所有资源 • 子进程撤销时，向父进程归还资源 • 父进程撤销时，所有子进程也被撤销 48 第三节 2.3.1 进程的创建 进程控制 n 进程创建过程： ① 申请空白PCB； ② 分配所需资源； ③ 初始化PCB； ④ 插入就绪队列。 49 第三节 2.3.1 进程的创建 进程控制 正在运行的进程由于程序自身需要 当操作系统启动时，通常会创建若 可以用系统调用创建新进程。一个  引起进程创建的事件 干进程，特别是一些常驻系统的进 正在运行的进程，如果需要处理与 程。这些进程有的运行在系统的前 其相关却又相互独立的事件，可以 • 操作系统初始化 台，供用户交互；有的运行在后台 用系统调用来创建一个新的进程来 当运行中的程序需要某种服务时， ，完成某些专门的功能。如网络服 • 提供用户服务(输入/输出) 系统专门创建一个进程来提供所需 完成这样的事件。如UNIX操作系统 务器中的电子邮件服务进程，如果 中父进程用系统调用创建子进程， 要的服务，如打印文件、屏幕输出 没有邮件需要处理，则进入休眠状 • 用户登录（分时系统） 子进程协同父进程完成同一任务。 等。 态；如果邮件到来，则该进程被唤 当用户在终端键入登录命令后，系 • 用户请求系统创建新进程 醒，处理接收到的邮件。 在交互式系统中，用户用键盘键入 统将为该终端用户建立一个进程。 命令或用鼠标点击，则可以创建新 • 执行创建新进程的系统调用 进程。如在Windows操作系统中，用 户可以用键盘运行多个程序，或用 用户提交批处理作业，当操作系统 • 批处理作业的初始化和调度 鼠标打开多个窗口。每个程序或每 能够提供资源时，作业调度程序按 个窗口对应一个新的进程。 照一定的算法，从批处理作业清单 中调度某个作业并装入内存，为作 业分配必要的资源，创建作业的进 程。 50 第三节 2.3.1 进程的创建 进程控制  创建步骤 进程创建原语的主要任务是创建进程控制块PCB。 命名进程：为进程设置进程标志符； 从PCB集合中为新进程申请一个空白PCB； 确定进程的优先级； 为进程的程序段、数据段和用户栈分配内存空间；如果进程 中需要共享某个已在内存的程序段，则必须建立共享程序段 的链接指针; 为进程分配除内存外的其他各种资源; 初始化PCB，将进程的初始化信息写入PCB; 如果就绪队列能够接纳新创建的进程，则将新进程插入到就绪 队列; 通知OS的其他管理模块，如记账程序、性能监控程序等。 51 第三节 2.3.1 进程的创建 进程控制 fork( ) 代码区 Linux中进程的创建 的返回码 fork( ) 代码区 if (fork()= = 0) {printf(“hello”);} else {printf(“ok”) ;} 52 第三节 2.3.2 进程的终止 进程控制  终止原因 • 进程正常结束: 批处理作业中的“halt”，多用户系统中的“log off”，用户程序中的“end”等。 第一步：根据被终止进程的标识符，从PCB集合中查 • 操作异常(进程自身): 越界﹑保护错﹑特权指令错﹑非法指令错﹑ 第二步：若被终止进程正处于执行状态，则终止该 找对应进程控制块并读出该进程的状态； 运行超时﹑等待超时﹑算术运算错﹑I/O故障. 第三步：若进程还有子孙进程，应将其所有子孙进 进程的执行，并设置调度标志为真，用于指示该进 • 外界干预:操作员(提前结束)或操作系统(竞争资源死锁)﹑父进程 第四步：将进程所占有的全部资源释放（还给父进 程终止，以防它们成为不可控制的。 程被终止后应重新进行调度，选择一新进程，把处 请求﹑父进程终止 程或系统），释放进程控制块（若该进成为执行态， 第五步：将被终止进程（它的PCB）从所在队列（或 理机分配给它。 链表）中移出，等待其他程序来收集相关信息。 要进行进程调度）。 53 第三节 2.3.3 进程的阻塞与唤醒 进程控制 引起进程阻塞和唤醒的事件 1)向系统请求资源失败： 请求打印机(间接制约) 2)等待某种操作的完成： 等待I/O的完成 3)新数据尚未到来：合作进程之间(直接制约) 4)等待新任务的到达： 服务进程 进程阻塞过程（自身阻塞） 停止该进程的执行 改PCB中状态 插入阻塞队列 重新调度新进程 保留处理机状态 54 第三节 2.3.3 进程的阻塞与唤醒 进程控制 进程阻塞是进程的一种自主行为，是进程为了等待某事件的发生， 而自己调用阻塞原语使得自己放弃处理器，进入阻塞队列中等待 进程唤醒过程 （合作进程/系统进程唤醒） 运行 阻塞 就绪 唤醒 阻塞 从阻塞队列中移出 阻塞 改PCB的状态为就绪 唤醒 插入就绪队列 主体 客体 阻塞 A A 自我行为 唤醒 B 非B 被动行为 55 第三节 2.3.4 进程的挂起与激活 进程控制 处于阻塞状态、就绪状态和运行状态的进程都可以被挂起，根据进程挂起前的 状态决定挂起后的状态。 如果进程被挂起，进程的进程控制块中的信息要修改，进程上下文被放到外存。 如果进程挂起的时间到或者内存资源充足时，系统或有关进程，特别是进程同 步中的原语操作，会激活被挂起的进程。 激活进程的主要工作是将进程上下文从外存调入内存，修改进程控制块信息并 调入内存，修改进程控制块中的进程状态，并按照进程状态将进程控制块排入到相 应的进程队列。 56 第三节 2.3.4 进程的挂起与激活 进程控制 挂起 内存 挂起进程 激活 修改PCB块中的信息 进程调入外存 激活进程 磁盘 进程放入相应的状态队列中 将调出的进程从外存调入内存 修改PCB块中的进程状态 并按照进程状态将进程控制块排入到相应的进程队列 进程只能由操作系统，父进程，进程自身挂起 57 第三节 2.3.4 进程的挂起与激活 进程控制 1）三对进程控制原语 阻塞Block 创建Creation 结束Termination 唤醒Wakeup 挂起Suspend 激活Active 2）PCB块使用频繁，放入内存的专用区 3）每个系统的PCB块结构都不相同，进程的状态也都不一样。 58 小结 进程可以在：新建，就绪，阻塞，运行状态被挂起。 进程只能由操作系统，父进程，进程自身挂起 挂起 进程状态转换 59 2.4 进程通信概念 进程通信是指进程之间的信息交换 低级进程通信 ：进程的同步和互斥 Ø 效率低 Ø 通信对用户不透明 高级进程通信 Ø 使用方便 Ø 高效地传送大量数据 60 2.4.1 进程通信的类型(1) 共享存储器系统 Ø 基于共享数据结构的通信方式（效率低） Ø 基于共享存储区的通信方式（高级） 管道通信 Ø 管道：用于连接一个读进程和一个写进程以 实现它们之间通信的一个共享文件，又名 pipe文件。 Ø 管道机制的协调能力：互斥、同步、对方是 否存在 61 2.4.1 进程通信的类型(2) 消息传递系统 Ø 直接通信方式 Ø 间接通信方式（通过邮箱） 客户机-服务器系统 Ø 套接字（Socket） Ø 远程过程调用（RPC）和远程方法调用 （RMI，Java） 62 2.4.2 消息传递通信的实现方式 直接通信方式 Ø Ø 发送原语：send(P, message) 发送 通信链路的属性 拼命搞信息到进程P Ø 自动建立链路 接收原语：receive(Q, message) 从 Ø 一条链路恰好对应一堆通信进程 Ø 每对进程之间只有一个链路存在 Ø 链路可以是单向的，通常都是双向 进程Q接收消息 63 2.4.2 消息传递通信的实现方式 send(mailbox, message) receiver(mailbox,message) 间接通信方式：通过信箱来完成 Ø 定向接收消息 Ø 每个消息队列都有一个唯一的ID p 只有他们共享了一个消息队列进程才能 通信链路属性 Ø 建立链路 通信 Ø p 只有进程共享一个共享的消息队列才 信箱类型 Ø 链接可以与许多进程相关联 私用邮箱，公共邮箱，共享邮箱 Ø 每对进程可以共享多个通信链路 Ø 连接可以单向或双向 64 2.4.3 Linux进程通信方式 管道 信号 消息队列 共享内存 信号量 套接字 65 2.4.3 无名管道实例 #define INPUT 0 #define OUTPUT 1 close(file_descriptors[INPUT]); void main() { write(file_descriptors[OUTPUT], "test data", int file_descriptors[2]; pid_t pid; char buf[256]; exit(0); } int returned_count; pipe(file_descriptors); if((pid = fork()) == -1) { printf("Error in fork/n"); exit(1); else { printf("in the spawning (parent) process.../n"); close(file_descriptors[OUTPUT]); returned_count = read(file_descriptors[INPUT], } if(pid == 0) { strlen("test data")); printf("in the spawned (child) process.../n"); buf, sizeof(buf)); printf("%d bytes of data received from spawned process: %s/n",returned_count, buf); } } 66 2.4.3 有名管道实例 #include out_file = fopen("mypipe", "w"); #include if (out_file == NULL) { void main() { printf("Error in fdopen./n"); FILE * in_file, *out_file; exit(1); int count = 1; } char buf[80]; sprintf(buf,"this is test data for the named pipe in_file = fopen("mypipe", "r"); example./n"); if (in_file == NULL) { fwrite(buf, 1, 80, out_file); printf("Error in fdopen./n"); fclose(out_file); exit(1); } } while ((count = fread(buf, 1, 80, in_file)) > 0) printf("received from pipe: %s/n", buf); fclose(in_file); 67 小结 Ø 具体看思维导图 68 小结 无论是在单机系统、多机系统还是计算机网络中，消息传递机制都是一种使用十分广泛的进程 通信机制，我们必须了解以下几个问题。 （1）什么是消息传递通信机制。消息传递通信机制是指以格式化的消息为进程间数据交换单 位的进程通信方式。 （2）消息传递通信机制有哪几种实现方式。消息传递通信机制有直接通信和间接通信两种实 现方式，在学习时应注意比较它们在原语的提供、通信链路的建立、通信的实时性等方面的异 同。 （3）如何协调发送进程和接收进程。为了使诸进程间能协调地进行通信，必须对进程通信的 收、发双方进行进程同步 （4）消息队列通信机制是一种常用的直接通信方式。 69 课程思政小讲堂 长期“冷战”之后 Linux与Windows究竟谁会更胜一筹？ 20世纪90年代初期，基于MINIX和UNIX思想而研发的开源Linux系统面 市，其是一款支持多用户、多任务、多线程和多内核的操作系统，不仅能够运 行UNIX工具软件、应用程序和网络协议，还具有稳定的系统性能。发展至今， Linux已有上百种不同的发行版本。 在Linux系统稳步发展过程中，Windows系统亦不分昼夜地进行着功能完 善、界面美化以及版本更新等工作。进入21世纪后，微软公司的Windows系 统在个人计算机领域基本占领了垄断地位。由垄断所导致的潜在安全问题是各 国相关部门尤为关心的核心问题，而解决该问题（即去微软公司化）的主流途 径便是采用开源Linux系统。 70 课程思政小讲堂 长期“冷战”之后 Linux与Windows究竟谁会更胜一筹？ 但是，要想简单地通过采用Linux系统实现去微软公司化，实属不易。 典型例子：2004年，德国慕尼黑政府宣布将政府办公计算机中所采用的 Windows系统换为Linux系统，希望此举可以降低运维信息化成本；然而10年 之后，这场“吃螃蟹”的试验并未获得预期的效果；近年来，该政府又开始逐 步在政府办公计算机上重新安装Windows系统。 从此类案例中可以看出，单纯地通过采用Linux系统+开源软件的模式来降低 运维信息化成本，效果并不理想，大都会陷入所须开发的专业软件多和后期维 护工作量大等风险中。此外，由于Linux系统代码开源，其产品化始终不足，因 此，采用Linux系统实现去微软公司化缺乏相应的产业基础。 71 课程思政小讲堂 长期“冷战”之后 Linux与Windows究竟谁会更胜一筹？ 形势即便如此，我们也绝对不应放弃反垄断！在此情形下，我们知识分 子与科技人才更应深度思考：究竟应当如何解决操作系统垄断问题，以及 如何在解决该问题的过程中，通过发挥我们自身的价值，助力研发自主可 控的国产操作系统？ 72 TRANSITION PAGE 2.1 2.2 2.3 2.4 前趋图和程序的执行 进程的描述 进程控制 进程同步基本概念 2.5 2.6 2.7 2.7 1 管程机制 经典的同步问题 进程通信 线程及其实现 目 录 页 回顾 n 在OS中引入进程，可以使系统中的多道程序并发执行，提高了资 源利用率及系统吞吐量。但也会使系统更加复杂，引起系统对资源 的无序争夺。 n 为了保证多进程能有条不紊运行，必须引入进程同步机制。 2 本节课内容导图 3 2.4 进程同步与互斥 教学目的和要求 q 知道同步互斥问题的原因 q 掌握临界区和信号量概念 q 掌握解决简单同步互斥问题的信号量方法 n 重点 q 临界区和信号量概念 n 难点 q 应用信号量解决同步互斥问题 n 4 第四节 2.4.1 进程同步概念的引入 进程同步基本概念 n 把异步环境下的一组并发进程因直接制约而互相发送消息互相合作、互相等 待，使得各进程按一定的速度执行的过程，称为进程同步。 n 具有同步关系的一组并发进程称为协作进程。 n 进程同步机制的主要任务——在执行次序上对多个协作进程进行协调，使并 发执行的诸多协作进程之间能按照一定的规则（或时序）共享资源、相互合 作，从而使程序的执行具有可再现性。 5 5 第四节 2.4.2 两种制约关系 进程同步基本概念 § 在多道程序系统中，由于资源共享或进程合作，使进程间形成间 接相互制约和直接相互制约关系。 § 间接制约关系（互斥关系) – 这是由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而 得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行。 § 直接制约关系（同步关系） – 这通常是在那些逻辑上相关的程序段之间发生的，一般是由于各种程序 段要求共享信息引起的。 § 这种相互依赖、相互合作又相互竞争的关系，意味着进程间需要 用某种形式的通信来实现，主要表现为进程互斥与同步两方面。 6 第四节 同步关系 进程同步基本概念 n 例子1： 有一输入进程 A 通过单缓冲向进程 B 提供数据。当该缓冲空时，计 算进程因不能获得所需数据而阻塞，而当进程 A 把数据输入缓冲区 后，便将进程 B 唤醒；反之，当缓冲区已满时，进程 A 因不能再向 缓冲区投放数据而阻塞，当进程 B 将缓冲区数据取走后便可唤醒 A。 7 7 第四节 互斥关系 进程同步基本概念 n 例子2：两个进程共享打印机 进程A： ······ 打印文件AAA； ······· 进程B： ······ 打印文件BBB； ······· 打印结果： AAA的文本； BBB的文本； AAA的文本； AAA的文本； BBB的文本； AAA的文本； BBB的文本； BBB的文本； BBB的文本； AAA的文本； AAA的文本； 8 ······· 8 第四节 进程间的关系（一）：同步 synchronism 进程同步基本概念 n 直接制约：“进程—进程” 进行协作，等待来自其他进程的信息，否则就进行不下去，“同步”。 n n 概念：指系统中多个进程中发生的事件存在某种时序关系，必须协 同动作，相互配合，从而共同完成一项任务。 一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获 得消息之前，该进程处于等待（阻塞）状态，获得消息后被唤醒进 入就绪状态。 9 第四节 进程间的关系（一）：同步 synchronism 进程同步基本概念 例子3：“司机－售票员”问题（同步） 司机进程 售票员进程 正确运行过程 While(True) While(True) While(True) { { { } 启动公车； 关车门； （售票员）关车门 驾驶公车； 卖车票； （司机）启动公车； 停止公车； 开车门； （司机）驾驶公车； } （售票员）卖车票 （司机）停止公车； （售票员）开车门； } 10 第四节 进程间的关系（一）：同步 synchronism 进程同步基本概念 例4: 电子邮件信箱 1 2 发送进程 A …… n 接收进程 B 接收进程必须等待发送进程发送信件。 11 第四节 进程间的关系（一）：同步 synchronism 进程同步基本概念 例 5: 进程P1 X = fun1(y)*fun2(Z) 进程P2 计算fun2(Z) 计算fun1(y) N 进程p2 算完fun2(Z)? 设置计算完成标志 Y 取用P2计算结果 终 止 ···· 两个协同工作进程的同步 12 第四节 进程间的关系（二）：互斥 mutual exclusion 进程同步基本概念 进程互斥： n 间接制约：“进程—资源—进程” 进行竞争，独占分配到的部分或全部共享资源，等待释放后才能使用， “互斥”。 n n 概念：有些资源需要互斥使用，因此各进程间要相互竞争，以使用这些 互斥资源，进程的这种关系为进程的互斥。 解决进程互斥有两种办法： 1.由竞争各方平等协商。 2.引入进程管理者，由管理者来协调竞争各方对互斥资源的使用。 13 第四节 进程间的关系（二）：互斥 mutual exclusion 进程同步基本概念 例 6: 公共 地段 交通十字路口的控制：公共地段互斥 14 第四节 2.4.3 临界资源 critical resource 进程同步基本概念 系统中某些软件或者硬件资源一次只允许一个进程使用， 称这样的资源为临界资源 或互斥资源 或共享变量。 如：外设（打印机、磁带机、绘图仪等）、共享代码段、 共享数据结构等。 15 第四节 2.4.3 临界资源 critical resource 系统中共享的资源分为 进程同步基本概念 互斥共享资源(打印机) 同时共享资源(磁盘) 临界资源(Critical Resouce):（互斥资源、逐次再使用资源） 一段时间内只允许一个进程使用的资源。 硬件 扫描仪 生活中 软件 座位 R/W文件 变量N 队列 16 第四节 2.4.3 临界资源 critical resource 进程同步基本概念 进 进 程 程 互斥性/排它性/独占性 二个进程串行执行 降低并发性 关中断执行 实现的困难 时间片 实时系统 及时性 高优先权 的抢占 中断时间 的太长 多CPU 17 第四节 系统中资源的共享程度 进程同步基本概念 互斥： 指多个进程不能同时使用同一个资源。是正确使用资源的基本要求。 死锁： 指多个进程互不相让，都得不到足够的资源。 饥饿： 指一些进程一直得不到资源或得到资源的概率很小。 18 18 第四节 进程的制约关系 进程同步基本概念 相互感知的程度 交互关系 对其他进程的影响 潜在的控制问题 相互不感知 （完全不了解其 它进程的存在) 竞争 对其他进程的结果 互斥、死锁、饥 (competit 无影响 饿 ion) 间接感知 一个进程的结果间 通过共享进 互斥、死锁、饥 (双方都与第三方 接依赖于从其他进 饿 交互，如共享资 行协作 程获得的信息 源) 直接感知 一个进程的结果直 通过通信进 接依赖于从其他进 (双方直接交互， 行协作 程获得的信息 如通信) 死锁、饥饿 19 第四节 2.4.4临界区 进程同步基本概念 进 临界资源 进 程 程 互斥性/排它性/独占性 访问相同临界资源的 进程进入临界区时才 互斥 二进程串行执行 串行执行或互斥进入 20 第四节 临界区的访问过程 进程同步基本概念 n 进入区(entry section) q 检查当前进程可否进入临界区的一段代码。 如果当前进程可以进入临界区，通常设置相应“正在访问临界区” 标志，防止其他进程同时进入临界区。 n 临界区(critical section) q 进程中访问临界资源的一段代码。 n 退出区(exit section) q 用于将“正在访问临界区”的进程的标志清除。 n 剩余区(remainder section) q 代码中的其余部分。 21 第四节 临界区的访问过程 进程同步基本概念 进入区 退出区 进程1 进入区 退出区 进程2 22 第四节 临界区的访问过程 进程等待进入临界区 进程同步基本概念 进程1请求临界资源并获得资源 临界区 进程1释放临界资 源 进程1 进程2 进程B请求临界资 源并等待资源释放 CPU=1 临界区 进程2获得资源 都需采取同步措施 进程2释放 临界资源 CPU>1 23 第四节 临界区与临界资源 一个访问临界资源的循环进程的描述 进程同步基本概念 While(TRUE){ 附加部分 进入区 原程序体 临界区 附加部分 退出区 剩余区 } 进入区 通常是测试语句或判断语句(while,if等) critical section 退出区 剩余区 临界资源访问结束后的标志,标明临界资源 可用,等待进程可进入 remainder section 24 第四节 同步机制应遵循的四条准则 进程同步基本概念 n-1个进程等待 进程1 进程n 临界资源空 进程1 进程n 某进程占用 进程 进程 某一进程占用 进程1 进程n 某进程继续占用 25 小结 (直接制约) (间接制约) 26 小结 注意∶ Ø 临界区是进程中访问临界资源的代码段。 Ø 进入区和退出区是负责实现互斥的代码段。 Ø 临界区也可称为"临界段"。 27 第四节 2.4.5进程同步和互斥的解决方法 进程同步基本概念 软件同步机制 01 Ø 使用编程方法解 决临界区问题 Ø 有难度、具有局 限性，现在很少 采用 硬件同步机制 02 Ø 使用特殊的硬件 指令，可有效实 现进程互斥 信号量机制 管程机制 03 04 Ø 一种有效的进 程同步机制， 已被广泛应用 Ø 新的进程同步机 制 28 第四节 进程互斥的软件方法 进程同步基本概念 n 通过平等协商方式实现进程互斥的最初方法是软件方法。 n 软件方法基本思路： 在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通 过循环检查进行等待；在退出区修改标志。 n 其中的主要问题： 设置什么标志和如何检查标志。 29 第四节 进程同步基本概念 j i Turn=i或j While(1){ while (turn!=i ); critical section； turn=j; remainder section; } 30 第四节 进程互斥的软件方法 进程同步基本概念 算法1：单标志 n 有两个进程Pi, Pj， n 设立一个公用整型变量 turn： 描述允许进入临界区的进程标识。 31 第四节 进程互斥的软件方法 进程同步基本概念 在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入； q 在退出区修改允许进入进程标识： 进程Pi退出时，改turn为进程Pj的标识j； q n 缺点： q 强制轮流进入临界区。 q 容易造成资源利用不充分。 （在Pi出让临界区之后，Pj使用临界区之前，Pi不能再次使用临界区。） 问题？同一进程不能连续的进入临界区.违背空闲让进的原则 32 第四节 进程互斥的软件方法 进程同步基本概念 算法2：双标志、先检查后修改（先人后己） 设立一个标志数组flag[]： 描述是否有进程在临界区， true: 进程正在临界区； false:进程未进入临界区，初值均为FALSE n 33 第四节 进程互斥的软件方法 进程同步基本概念 算法2：双标志、先检查后修改（先人后己） q q 先检查，后修改： 在进入区检查另一个进程是否在临界区，不在时修改 本进程在临界区的标志； 在退出区修改本进程在临界区的标志； n 优点： q 不用交替进入，可连续使用。 34 第四节 进程互斥的软件方法 进程同步基本概念 n 缺点： Pi和Pj可能同时进入临界区。 按下面序列执行时，会同时进入： “PiPjPiPj”。 即在检查对方flag之后和切换自己flag之前有一段时间， 结果双方都检查通过。 问题出在检查和修改操作不能连续进行。 问题？ 二个进程都看到对方没进临界区而决定进去时则会发生 冲突,互不相让.违背忙则等待的原则. 35 第四节 进程互斥的软件方法 进程同步基本概念 算法3：双标志、先修改后检查（先斩后奏） n 类似于算法2，与算法2的区别在于：先修改后检查； flag[]表是否想进入临界区。 36 第四节 进程互斥的软件方法 进程同步基本概念 n n 优点： q 可防止两个进程同时进入临界区。 缺点：Pi和Pj可能都进入不了临界区。 按下面序列执行时，会都进不了临界区：“PiPjPiPj” 即在切换自己flag之后和检查对方flag之前有一段时间，结果都切换flag，结 果都检查不通过。 问题？ 二个进程首先表示自己要进入临界区,再去判断另一进程是否会 进入临界区,结果是都认为对方会进入临界区而谦让,都不进去.违背空闲 让进的原则. 37 第四节 进程互斥的软件方法 进程同步基本概念 算法4:先修改、后检查、后修改者等待（Peterson算法） 设置一个数组flag[i/j]=true/flase=进入/未进入临界区 一个变量turn=i/j=表示允许谁进入; n 结合算法1和算法3，是正确的算法。turn描述标志修改的先 后，flag[]表示是否想进入临界区。 38 第四节 进程互斥的软件方法 进程同步基本概念 在进入区先修改后检查，并检查并发修改的先后。 n 实现了：空闲则入、忙则等待。 n 检查对方flag: 如果对方不想进入临界区，则自己进入－“空闲则入”。 q 否则再检查turn： turn中保存的是较晚的一次赋值。则较晚的进程等待，较早的进程 进入－先到先入，后到等待。 q 满足三个需求；解决了两个进程的临界区问题。 39 第四节 进程互斥的软件方法 进程同步基本概念 ▲ 软件实现方法中： 两个和三个以上进程间的互斥的进入区要区别对待。 不适合进程较多的进程间的互斥。 现在已很少单独采用软件方法。在平等协商时利用某些硬件指令来实现进 程互斥。 最主要的问题：修改和检查标志不能作为一个整体被执行。 40 第四节 进程互斥的硬件方法 N个进程共享1个临界资源 进程同步基本概念 申请 关锁 关锁(lock) 临界资源=W W=0或false: 资源空 W=1或true：资源忙 L: if (W= =1) goto L else W=1 Lock(w); /* critical section; unlock(w); /* remainder section; 释放 开锁 开锁(unlock) W=0 Ø 将标志看作一个锁，"锁开"进入，"锁关"等待， 初始时锁是打开的。 Ø 每个要进入临界区的进程，必须先对锁进行测试，当锁 未开时，则必须等待，直至锁被打开。当锁打开时，则 应立即把其锁上，以阻止其他进程进入临界区。 Ø 测试和关锁操作必须是连续的，不允许分开进行。 41 第四节 进程互斥的硬件方法 进程同步基本概念 ▲ 硬件方法基本思路： 用一条指令完成读和写两种操作，因而保证读操作与写操作不被打断。 ▲ 分类： 依据所采用的指令不同，分为两种： 1.TS 指令 2.Swap 指令 一条机器指令 中断请求 一条机器指令 响应中断 一条机器指令 特殊的硬件指令 Test and Set 测试和设置 swap交换 42 第四节 进程互斥的硬件方法 中断屏蔽方法 进程同步基本概念 利用"开/关中断指令"实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为 止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况） 优点∶简单、高效 缺点∶不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内 核态，这组指令如果能让用户随意使用会很危险） 43 第四节 进程互斥的硬件方法 TestAndSet指令 简称TS指令，也有地方称为 TestAndSetLock指令，或TSL指令 进程同步基本概念 TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑 Ø 若刚开始 lock是 false，则 TSL返回的 old值为false，while 循环条件不满足，直接跳过循环，进入临界区。若刚 开始 lock是 true，则执行TLS后 old 返回的值为 true，while循环条件满足，会一直循环，直到当前访问临界区的 进程在退出区进行"解锁"。 Ø 相比软件实现方法，TSL指令把"上锁"和"检查"操作用硬件的方式变成了一气呵成的原子操作。 Ø 优点∶实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。 Ø 缺点∶ 不满足"让权等待"原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致"忙等"。 44 第四节 进程互斥的硬件方法 Swap指令 有的地方也叫 Exchange 指令，或简称 XCHG指令。 进程同步基本概念 Swap指令是用硬件实现的，执行过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑 Ø 逻辑上来看 Swap 和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old变量上），再将上 锁标记lock设置为 true，最后检查 old，如果 old 为false 则说明之前没有别的进程对临界区上锁，则可跳出循环， 进入临界区。 Ø 优点∶实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境 Ø 缺点∶不满足"让权等待"原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致"忙等"。 45 第四节 进程互斥的硬件方法 硬件方法的优点： q 适用范围广： 适用于任意数目的进程，在单处理器或多处理器上完全相同。 q 简单： 标志设置简单，含义明确，容易验证其正确性。 q 支持多个临界区： 一个进程内 存在多个临界区时，只需为每个临界区设立一个布尔变量。 n 进程同步基本概念 n 硬件方法的缺点： q 不能实现“让权等待”。 进程在等待进入临界区时，要耗费处理机时间。 q 可能“饥饿“。 进入临界区的进程是从等待进程中随机选择有的进程可能一直没有被选中。 46 第四节 测验 进程同步基本概念 n 两进程互斥算法（双标志、后检查）存在什么问题？ A. 强制轮流进入临界区 B. 可能同时进入临界区 C. 可能都进入不了临界区 47 第四节 测验 进程同步基本概念 n用TS指令实现的临界区访问控制无法实现哪些控制准则？ A. B. C. 空闲则入 忙则等待 有限等待 D. 让权等待 48 小 结 进程同步与互斥 Ø 进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、 Peterson算法） Ø 进程互斥的三种硬件实现方式（中断屏蔽方法、TS指令、Swap/CHG指 令） 1. 在双标志先检查法中，进入区的"检查"、"上锁"操作无法一气呵成，从而导致了两 个进程有可能同时进入临界区的问题; 2. 所有的解决方案都无法实现"让权等待"。 49 小 结 进程同步与互斥 算法思想∶ 两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就 Ø 是说每个进程进入临界区的权限只能被另一个进程赋予 缺点：turn 表示当前允许进入临界区 的进程号，而只有当前允许进入临界 区的进程在访问了临界区之后，才会 修改turn的值。也就是说，对于临界 区的访问， 一定是P0->P1->P0->P1......这样轮流 访问。这种必须“轮流访问”带来的 Ø turn 的初值为0，即刚开始只允许0号进程进入临界区。 Ø 若P1先上处理机运行，则会一直卡在⑤。直到P1的时间片用完，发生调度， 切换 P0上处理机运行。代码①不会卡住P0，P0可以正常访问临界区，在 Ø 问题是，如果此时允许进入临界区的 进程是P0，而P0一直不访问临界区， 那么虽然临界区空闲，但是并不允许 P1访问。 P0访问临界区期间即时切换回P1，P1依然会卡在⑤。只有P0在退出区将 因此，但标志法存在的主要问题是： turn 改为1后，P1才能进入临界区。 违背了“空闲让进”原则。 因此，该算法可以实现"同一时刻最多只允许一个进程访问临界区" 50 小 结 进程同步与互斥 Ø 算法思想∶设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的 意愿，比如"flag[0]=ture"意味着0号进程 P0现在想要进入临界区。每个进程在进入临界 区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为true，之后开始访问临界区。 若按照 ①⑤②⑥③⑦…的顺序执行，P0和P1将会同时访问临界区。 因此，双标志先检查法的主要问题是∶违反"忙则等待"原则。 51 小 结 进程同步与互斥 Ø 算法思想;双标志先检查法的改版。前一个算法的问题是先"检查"后"上锁"，但是这两个 操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先 "上锁"后"检查"的方法，来避免上述问题。 若按照①⑤②⑥..的顺序执行，P0和 P1将都无法进入临界区 因此，双标志后检查法虽然解决了"忙则等待"的问题， 但是又违背了"空闲让进"和"有限等待"原则， 会因各进程都长期无法访问临界资源而产生"饥饿"现象。 52 小 结 进程同步与互斥 Ø 算法思想∶ 双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁 都无法进入临界区。GaryL.Peterson 想到了一种方法，如果双方都争着想进入临界区， 那可以让进程尝试"孔融让梨"，主动让对方先使用临界区。 53 小 结 信号量 机 制 54 第四节 信号量（semaphore）机制 进程同步基本概念 前面的互斥算法都存在问题，它们是平等进程间的一种协商机制。 有时需要一个地位高于进程的管理者来解决公有资源的使用问题。 信号量就是OS提供的管理公有资源的有效手段。 信号量代表可用资源实体的数量。 一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这 种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当 的信号结构得到满足。 55 迪科斯彻(1930-2002) 艾兹格·W·迪科斯彻(Edsger Wybe Dijkstra) Ø 信号量和PV原语发明者 Ø 解决了“哲学家就餐”问题 Ø 最短路径算法(SPF)和银行家算法的创造者 Ø 结构程序设计之父 Ø THE操作系统设计者和开发者 与D. E. Knuth并称为这个时代最伟大的计 算机科学家 56 第四节 信号量（semaphore）机制 进程同步基本概念 信号量 1965年 E.W.Dijkstra 不同形式 1)整型信号量 2)记录型信号量 3)AND型信号量 4)信号量集。 荷兰语“Proberen” 的意思为“检测”（判断） P操作 wait操作 V操作 signal操作 原语 Ø 信号量S Ø 提供两个不可分割的[原子操作]访问信号量 “Verhogen”的意思为“增量”（归还） 57 第四节 1. 整型信号量 是一种最简单的信号量，主要用于解决并发进程互斥访问临界资源问题。 进程同步基本概念 Ø Wait(s)又称为P(S) Ø Signal(s)又称为V(S) Ø 缺点：进程忙等 58 第四节 2. 记录型信号量：:去除忙等的信号量 进程同步基本概念 每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放阻 塞在该信号量的各个进程PCB typedef struct { Ø 信号量只能通过初始化和两个标 准的原语PV来访问，作为OS核 int value; 心代码执行，不受进程调度的打 stuct process_control_block *list; 断 }semaphore; Ø 初始化指定一个非负整数值，表 示空闲资源总数（又称为"资源信 值 号量"），若为非负值表示当前的 空闲资源数，若为负值，其绝对 值表示当前等待临界区的进程数 整型数 PCB的指针 等待该资源的进程PCB队列 59 第四节 2. 记录型信号量 进程同步基本概念 注意两个原语中的value条件为什么不同？ 60 第四节 2. 记录型信号量 P(S):申请一个资源 进程同步基本概念 S =S-1 P(S)的定义 意味着请求分配 一个单位资源 S-- >0 OK：能分配，还有资源 ==0 OK：能分配，刚好分完 <0 NO: 不能分配，没有资源 Void P(semaphore *S) { S->Value - -; if (S->value<0 ) block(S->list);} N S<0？ 引起进程调度 Y 阻塞自己，等 待资源的释放 P操作后的 下一条指令 放在S队列上等待 被释放资源 的进程唤醒 PCB1 PCBi S=-i 61 第四节 2. 记录型信号量 V(S):释放一个资源 进程同步基本概念 = =0 释放前有一个等待的进程 <0 释放前至少有二个等待的进程 >0 无进程等待该资源 S =S+1 V(S)的定义 V(semaphore *S) { S->value + +; if (S->value<=0 ) wakeup(S->list); } N S++ S<=0？ Y 唤醒等待该资 源的阻塞进程 S=-3 S=-2 V操作后的 下一条指令 PCB1 PCB2 → PCB2 → → PCB3 PCB3 62 第四节 2. 记录型信号量 在考研题目中wait（S）、signal（S）也可以记为P（S）、V（S）， 进程同步基本概念 这对原语可用于实现系统资源的"申请"和"释放"。 ü S.value的初值表示系统中某种资源的数目。 ü 对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此 需要执行S.value-，表示资源数减1，当S.value<0时表示该类资源 已分配完毕，因此进程应调用block 原语进行自我阻塞（当前运行 的进程从运行态→阻塞态），主动放弃处理机，并插入该类资源的等 待队列S.L中。可见，该机制遵循了"让权等待"原则，不会出现"忙等 "现象。 ü 对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此 需要执行 S.value++，表示资源数加1，若加1后仍是S.value<=0， 表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等 待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）。 63 小 结 信号量（semaphore）机制 信号量 机 制 定义结构体 type semaphore = record value : integer; *list : list of process end; var s: semaphore; wait原子操作 wait(s): s.value := s.value – 1; if s.value < 0 then begin block P; insert P into s.list； end; signal原子操作 signal(s): s.value:= s.value + 1; if s.value ≤ 0 then begin wakeup the first P； remove the P from s.list; end； program mutualexclusion; const n=…; var s: semaphore(:= 1); procedure P(i:integer); begin begin repeat parbegin wait(s); P(1); P(2); … P(n) <临界区>; parend signal(s); end. <其余部分> forever end; 利用信号量实现互斥的通用模式 64 第四节 信号量（semaphore）机制 进程同步基本概念 >1 信号量S的初值 =1 =0 <0 信号量S上的正值，表示还有多少可用的资源，负值表示等待该资源上的进程数 如n个进程共享信号量S表示的资源 初值S=1 取值范围[1，1-n] 初值S=m 取值范围[m，m-n] 65 第四节 3. AND型信号量 进程同步基本概念 （1）多个进程共享两个或更多的资源： A、B两个进程共享数据D和E，采用信号量的方法实现A、B进程的同步。 互斥使用数据D和E的信号量分别为Dmutex和Emutex。 Dmutex=1; Emutex=1; 进程A： wait(Dmutex); 进程B： wait(Emutex); wait(Emutex); wait(Dmutex); 访问数据D； 访问数据D； 访问数据E； 访问数据E； signal(Dmutex); signal(Dmutex); signal(Emutex); signal(Emutex); 66 66 第四节 3. AND型信号量 进程同步基本概念 问题：A、B进程有可能进入死锁状态，导致A、B进程都无法向前推进。 （2）AND同步机制的基本思想： 将进程运行过程中所需的全部资源一次性全部分配给进程，待进程用完后 再一起释放。只有有一个资源不能满足进程的要求，其他所有可能分配给它的 资源也暂不分配。 主要思想：要么全分配，要么一个也不分配。 67 第四节 3. AND型信号量 进程同步基本概念 Swait(S1，S2，…，Sn); { if(S1>=1 &&S2>=1…Sn>=1) S1--; S2--; … Sn--; else 将进程阻塞并加入到每个信号量链表中 } Ssignal(S1，S2，…，Sn); { S1++; S2++; … Sn++; 将进程从信号量链表中删除并变为就绪状态 } 68 小 结 信号量（semaphore）机制 信号量 机 制 wait.signal操作讨论 1) 信号量的物理含义： S>0，表示有S个资源可用。 S=0，表示无资源可用。 S<0，则|S|表S等待队列中的进程个数。 wait(S): 表示申请一个资源。 signal(S): 表示释放一个资源。 信号量的初值应该 〉= 0。 69 69 小 结 信号量的类型 信号量 机 制 信号量分为：互斥信号量和资源信号量。 • 互斥信号量用于申请或释放资源的使用权，常初始化为1，表示只允许一个进 程访问临界资源，用于进程互斥。 • 资源信号量用于申请或归还资源，可以初始化为大于1的正整数，表示系统中 某类资源的可用个数。 • wait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己； • signal操作用于释放资源（或归还资源使用权），进程执行signal原语时，有 责任唤醒一个阻塞进程。 70 小 结 信号量的类型 信号量 机 制 信号量的意义 1. 互斥信号量：申请/释放使用权，常初始化为1 2. 资源信号量：申请/归还资源，资源信号量可以初始化为一个正整数（表示系 统中某类资源的可用个数）， s.value的意义为： • s.value≥0：表示还可执行wait(s)而不会阻塞的进程数（可用资源数） • s.value<0：表示s.list队列中阻塞进程的个数（被阻塞进程数） 71 小 结 信号量的类型 信号量 机 制 当仅有两个并发进程共享临界资源时，互斥信号量仅能取值0、1、－1。其中， ü s.value=1,表示无进程进入临界区 ü s.value=0，表示已有一个进程进入临界区 ü s.value= - 1,则表示已有一进程正在等待进入临界区 当用s来实现n个进程的互斥时，s.value 的取值范围为1～－（n-1） 72 小结 73 第四节 信号量的应用 进程同步基本概念 操作系统内核以系统调用形式提供wait和signal原语， 应用程序通过该系统调用实现进程间的互斥。 工程实践证明，利用信号量方法实现进程互斥是高效的，一直被广泛采用。 74 小 结 信号量的应用 某进程A 信号量 机 制 n 实现进程互斥 q 使用信号量mutex（初值＝1） P(mutex); 临界段 V(mutex); n n 实现进程同步 q 进程A执行完S1语句后，进程 B才能执行S2。 q 使用信号量synch（初值＝0） 进程A： 进程B： ······ ······ S1; P(synch); 同步点 V(synch); S2; ······· ······· 实现进程的前驱关系（多层的同 步关系） 75 第四节 利用信号量实现进程互斥 进程同步基本概念 n 为每个临界资源设置一个互斥信号量mutex(MUTual Exclusion)， 其初值为1。 n 在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间。 n P、V原语不能次序错误、重复或遗漏。 n 必须成对使用P和V原语： 遗漏P原语则不能保证互斥访问； 遗漏V原语则不能在使用临界资源之后将其释放 给其他等待的进程。 76 第四节 利用信号量实现进程互斥 进程同步基本概念 进程1 进程2 进程n 进程共享某类临界资源 信号量初值mutex为0,1,n? 互斥信号量P(mutex)和V(mutex)的成对 P(mutex)；csi(临界区)；V(mutex) 77 第四节 利用信号量实现进程互斥 进入临界区 正等待进入临界区 进程同步基本概念 进程A请求临界资源并获得资源 A释放资源并唤醒B P(S) V(S) 进程A S ∧ 1 进程B 0 ∧ P(S) 进程B请求临界资源 并等待资源释放 -1 B 0 ∧ 1 ∧ V(S) B被A唤醒并 B退出临界区并 进入临界区 释放资源释放 如果初值S=1，有二个进程，S的取值范围[1，-1] S==1 表示无进程进入临界区 S==0 表示一进程进入临界区 S==-1 表示一进程在临界区，另一进程在等待进入临界区 78 第四节 利用信号量实现进程互斥 进程同步基本概念 进程A P(mutex); CS1; V(mutex); 1 S=1 ∧ 2 S=0 C B 进程B申请进入临界区而阻塞 6 S=0 ∧ 进程C退出临界区，并唤醒阻塞进程B 进程C P(mutex); CS3; V(mutex); C 3 S=-1 ∧ 进程1已进入临界区 初始状态 4 S=-2 进程B P(mutex); CS2; V(mutex); 进程C申请进入临界区而阻塞 B 5 S=-1 进程A退出临界区，并唤醒阻塞进程C 7 S=1 ∧ 进程B退出临界区,资源空闲可用 79 第四节 利用信号量实现同步关系 进程同步基本概念 P1、P2并发执行，由于存在异步性，因此二者交 替推进的次序是不确定的。 若P2的"代码4"要基于 P1的"代码1"和"代码2"的 运行结果才能执行，那么就必须保证"代码4"一定 是在"代码2"之后才会执行。 情况2 这就是进程同步问题，让本来异步并发的进程互相 配合，有序推进。 80 第四节 利用信号量实现同步关系 进程同步基本概念 /*信号量机制实现同步k/ semaphore S=0;//初始化同步信号量，初始值为0 1.分析什么地方需要实现"同步关 系"，即必须保证"一前一后"执行 的两个操作（或两句代码） 2.设置同步信号量 S，初始为0 3.在"前操作"之后执行 V（S） 4.在"后操作"之前执行P（S） 81 第四节 利用信号量实现前驱关系：A---->B 进程同步基本概念 A执行体 B执行体 A开始 B等待A执行完 A结束 B开始 情况1 B开始 B开始 情况2 B开始 B开始 情况3 B开始 82 第四节 利用信号量实现前驱关系：A---->B V(S) 进程同步基本概念 A进程 A执行完 B在等待？ N B进程 P(S) A执行完？ N Y Y 唤醒等待进程B 为B顺利执 行创造条件 等待A执行 （B阻塞） S初值=0,1或>1? A; V(S); 执行B P(S); B; 83 第四节 利用信号量实现前驱关系 进程同步基本概念 每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作） 因此， 1.要为每一对前驱关系各设置一个同步变量 2.在"前操作"之后对相应的同步变量执行 V操作 3.在"后操作"之前对相应的同步变量执行P操作 84 第四节 利用信号量实现前驱关系 进程同步基本概念 例 有6个进程A、B、C、D、E、F，它们并发执行的关系如下 semaphore s1,s2,s3,s4,s5,s6,s7,s8= 0,0,0,0,0,0,0,0; A：{ A; V(s1); V(s2); } B: { P(s1); B; V(s3); V(s4); } （信号量个数能减少？） C: { P(s2); C; V(s5); } D: { P(s3); D; V(s6); V(s7); } E: { P(s4); P(s5); P(s7); E; V(s8);} F: { P(s6); P(s8); F; } 85 第四节 利用信号量实现前驱关系 进程同步基本概念 B C A D { { { { b=0,c=0,d=0 A; V(b) ;V(c) ;V(d);} P(b); B; } P(c); C ; } P(d) ; D ; } a A a B C b a=0,b=0 { A; V(a) ;V(a); } { P(a); B; V(b); } { P(a); P(b); C; } { { { { a=0 A; V(a) ;V(a) ;V(a);} P(a); B; } P(a); C ; } P(a) ; D ; } a=0,b=0 { A ; V(a); } { P(a); B; V(b); } { P(b); C; } 86 第四节 利用信号量实现前驱关系 B 进程同步基本概念 C A b=0,c=0,d=0 { A; V(b);V(c);V(d);} { P(b); B ； } { P(c); C ； } { P(d) ;D； } a=0 { A; V(a) ;V(a) ;V(a);} {P(a); B； } {P(a); C； } {P(a) ; D； } b=0,c=0,d=0 { P(b) ;P(c) ;P(d) ;A;} { B; V(b); } { C; V(c) ; } { D; V(d) ; } a=0 { P(a) ;P(a) ;P(a) ;A;} { B; V(a); } { C; V(a); } { D; V(a); } D B C A D a A a B C b a=0,b=0 { A; V(a) ;V(a); } { P(a); B; V(b); } { P(a); P(b); C; } a=0,b=0 { A ; V(a); } { P(a); B; V(b); } { P(b); C; } 87 第四节 利用信号量实现前驱关系 练习： 有并发进程P1和P2 进程同步基本概念 进程P1 进程P2 S1 x = a + 2 S2 z = 3  y S3 y= x + 4 S4 w= z + 6 进程并发需要按照S1→S3→S2→S4的顺序执行，才能得到x、y、z和w的合理值 a b c S1→S3→S2→S4 semaphore a,b,c= 0,0,0; 进程P1 S1 x= a + 2； V(a); P(b); S2 z= 3  y； V(c); 进程P2 P(a); S3 y= x + 4; V(b); P(c); S4 w= z + 6; 88 第四节 信号量（semaphore）机制 总结：N个进程共享一临界资源,一个互斥信号量mutex=1(初值) 进程同步基本概念 进程1 互斥访问 进入区 临界资源 CSi;(临界区) mutex=1 进程n P(mutex)； 退出区 V(mutex)； 进程A 进程B A; V(S); P(S); B; Mutex何时可以>1 利用信号量实现前趋关系A-->B 一个信号量S=0(初值) 信号量用于互斥与前趋关系比较 1)信号量的个数及初值 2)涉及的进程数量 3)P，V所处的位置 4)重复执行的次数 89 第四节 分析同步问题 进程同步基本概念 分析进程同步和互斥问题的方法步骤 Ø 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。 同步、互斥、前驱关系直接按照上面例子中的经典范式改写。 Ø 整理思路。找出解决问题的关键点，并且根据做过的题目找出解决的思 路。根据进程的操作流程确定P操作、V操作的大致顺序。 Ø 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。 90 第四节 单缓冲的同步问题 进程同步基本概念 【例】有一计算进程和打印进程，它们共享一个单缓冲区，计算进程不断地 计算出一个整形结果并将它放入单缓冲区中，打印进程则负责从单缓冲区 中取出每一个结果进行打印，请用信号量来实现它们的同步关系。 91 第四节 单缓冲的同步问题 进程同步基本概念 分析1∶可从临界资源的角度来思考，先找临界资源，并为每种临界资源设置信 号量，在访问临界资源之前加wait操作来申请资源，访问完临界资源后加 signal操作来释放临界资源。本题中有两类临界资源，第一类是计算进程争用 的空闲缓冲区，初始状态下有一个空闲缓冲可供使用，故可为它设置初值为1 的信号量empty;第二类是打印进程争用的已放入缓冲中的打印结果，初始状 态下缓冲中无结果可供打印，故可为它设置初值为0的信号量full。 92 第四节 单缓冲的同步问题 进程同步基本概念 缓冲区空 计算进程I 放数 等待 单缓冲区 等待 打印进程P 取数 缓冲区满 放数 V(S1) P(S2) S1=0 S2=0 P(S1) 取数 V(S2) 93 第四节 单缓冲的同步问题 S2=1（初值） 进程同步基本概念 缓冲区空 计算进程I 放数 等待 等待 单缓冲区 打印进程P 取数 缓冲区满 P(S2) 放数 V(S1) S1=0（初值） P(S1) empty=1,full=0 取数 While(1) { P(empty); 放数; V(full);} while(1) {P(full); 取数; V(empty);} V(S2) 94 第四节 单缓冲的同步问题 进程同步基本概念 答1∶具体的同步算法可描述为∶ 95 第四节 单缓冲的同步问题 进程同步基本概念 分析2∶还可从同步的角度来思考，对某种同步关系，如进程A在某处必须等待 进程B完成某个动作D后才能继续执行，可为它设置一初值为0的信号量，并 在A需要等待B 的位置插入wait操作，在B完成动作D之后插入signal操作。 本题中存在两种同步关系∶ （1）打印进程必须等待计算进程将计算结果放入缓冲之后，才能取结果打印， 因此，可为它们设置初值为0的信号量SA; （2）除第一个计算结果可直接放入缓冲区外，计算进程必须等打印进程将缓冲 中的前一个结果取走，缓冲区变空后，才能将下一个计算结果放入缓冲区，因 此，可为它们设置初值为0的信号量SB。 96 第四节 单缓冲的同步问题 进程同步基本概念 答2∶具体的同步算法可描述为∶ 97 小结 (直接制约) (间接制约) 98 小结 注意∶ Ø 临界区是进程中访问临界资源的代码段。 Ø 进入区和退出区是负责实现互斥的代码段。 Ø 临界区也可称为"临界段"。 99 小结 10 小结 Ø 信号量机制的基本原理∶两个或多个进程可以利用彼此间收发的简单 的信号来实现"正确的"并发执行，一个进程在收到一个指定信号前， 会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。 Ø 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作， 从而很方便的实现了进程互斥、进程同步。 Ø 信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录 型变量），可以用一个信号量来表示系统中某种资源的数量，比如∶ 系统中只有一台打印机，就可以设置一个初值为1的信号量。 10 小结 Ø 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语 是由关中断/开中断指令实现的。 Ø 一对原语∶wait（S）原语和signal（S）原语，可以把原语理解为我 们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量S 其实就是函数调用时传入的一个参数。 Ø wait、signal原语常简称为P、V操作（来自荷兰语proberen和 verhogen）。因此，做题的时候常把wait(S)、signal(S)两个操作 分别写为P(S)、V(S) 10 小结 10 回顾——实例分析 互斥量mutex_vat=1 某寺庙，有小和尚、老和尚若干。有一水缸，由小和尚提 两个流程 水入缸，老和尚从缸中取水饮用。水缸可容纳10桶水，水 互斥量mutex well=1 取自同一水井中，水井径窄，每次只能容一个水桶取水。 pail=3 确认取水\入水时水缸互斥 水桶总数为3个，每次入、取缸水仅为1桶，且不可同时进 行。试给出取水、入水的算法描述。 小和尚打水入缸流程： 拿桶-->去水井取水（互斥，P、V操作）-->把水倒入水缸（互斥，P、V操作）-->放桶 老和尚取水饮用流程： 拿桶-->去水缸取水（互斥，P、V操作）--->放桶 1 回顾——实例分析 2 第五节 3.5.1 生产者—消费者问题 经典的同步问题 ①一个生产者、一个消费者共享一个缓冲区 ②一个生产者、一个消费者共享多个缓冲区 ③多个生产者、多个消费者共享多个缓冲区 3 第五节 一个生产者、一个消费者共享一个缓冲区的解 经典的同步问题 • int B; • semaphore empty; //可以使用的空缓冲区数 • semaphore full; //缓冲区内可以使用的产品数 • empty=1; //缓冲区内允许放入一件产品 • full=0; //缓冲区内没有产品 • cobegin process consumer(){ • process producer(){ while(true) { • while(true){ P(full); • produce( ); take( ) from B; • P(empty); V(empty); • append( ) to B; consume( ); • V(full); } • } } • } coend 4 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 n 问题描述：在生产者和消费者之间有共用缓冲池，有 n个缓冲区，生产者不断地向缓冲池中生产物品（相 当于向缓冲区添加物品，即占有缓冲区），每个缓冲 区可以放一个物品；消费者也不断消费物品（相当于 向缓冲区删除物品，即腾空缓冲区）。 n 只要缓冲池中仍有空闲的缓冲区就可以不断地生产; n 同样，只要有缓冲区仍有物品就可以不断地消费。 5 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 n 互斥信号量 q mutex：防止多个进程同时进入临界区 n 同步信号量 empty和full：保证事件发生的顺序 q 缓冲区满时，Producer停止运行 q 缓冲区空时，Consumer停止运行 q n 概念差别——互斥与同步（并发的两个要素） 互斥：保护临界区，防止多个进程同时进入 q 同步：保证进程运行的顺序合理 q 6 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 n 互斥信号量 必定成对出现： q 进入临界区——临界区——退出临界区 q n 同步信号量 q 未必成对出现，依赖于同步关系的性质 n 同步信号量和互斥信号量的操作顺序 q 基本原则：互斥信号量永远紧邻临界区 7 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 § 缓冲池buffer[n]：数组表示，具有n个(0，1，…，n-1)缓 冲区 § 输入指针in：指示下一个可投放产品的缓冲区 § 输出指针out：指示下一个可从中获取产品的缓冲区 § 缓冲池采用循环组织，故： – 输入指针加1表示成 in:= (in+1)mod n； – 输出指针加1表示成out:= (out+1) mod n。 – 当 (in+1) mod n=out时表示缓冲池满；而in=out则表示缓冲池空。 8 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 空缓冲 装满数据的缓冲 缓冲区大小=n， buffer[n] 消费者1 生产者1 0 1 2 3 4 5 6 7 8 生产者X 消费者Y Out(取数指针) in (放数指针) X>=1 X个进程 1个生产者程序 n1 整型变量，初值=0 信号量为empty=n ，full=0 Y>=1 Y个进程 1个消费者程序 9 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 0 1 2 3 4 5 6 7 8 Out(取数指针) 信号量 n1 in (放数指针) 1）empty表示生产者可放产品的缓冲区个数，初值=n 2）full表示消费者可取的产品数，初值=0 P(empty) 生产者 只要缓冲区未满，生产者可将产品放入， V(full) 否则，等待缓冲区有空 P(full) 消费者 只要缓冲区未空，消费者可将产品取出， 否则，等待有可取产品 V(empty) 10 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 缓冲区大小=n， buffer[n] 消费者1 生产者1 0 1 2 3 4 5 6 7 8 n1 消费者Y 生产者X Out(取数指针) 1个生产者程序 in (放数指针) 信号量为empty=n ，full=0 1个消费者程序 Producer(生产者) Consumer(消费者) P(empty); P(full); buffer(in)=nextp; nextc=buffer(out); in= (in+1) % n; out=(out+1) % n; V(full); V(empty); 11 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 缓冲区大小=n， buffer[n] 经典的同步问题 消费者1 生产者1 n1 0 1 2 3 4 5 6 7 8 生产者X (取数指针)Out 消费者Y in (放数指针) 临界资源 X个生产者程序 mutex1=1 Producer(生产者) P(empty); P(mutex1); buffer(in)=nextp; in= (in+1) % n; V(mutex1); V(full); mutex2=1 Y个消费者程序 Consumer(消费者) P(full); P(mutex2); nextc=buffer(out); out=(out+1) % n; V(mutex2); V(empty); 12 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 生产者1 缓冲区大小=n， buffer[n] 消费者1 0 1 2 3 4 5 6 7 8 n-1 消费者Y 生产者X F(empty) 空 空 空 空 F(in/out) 满 满 满 满 二队列合用信号量mutex=1 13 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 生产者1 缓冲区大小=n， buffer[n] 消费者1 n1 0 1 2 3 4 5 6 7 8 生产者X (取数指针)Out x个生产者程序 Producer(生产者) P(empty); P(mutex); buffer(in)=nextp; in= (in+1) % n; V(mutex); V(full); 消费者Y in (放数指针) 临界资源 mutex=1 Y个消费者程序 Consumer(消费者) P(full); P(mutex); nextc=buffer(out); out=(out+1) % n; V(mutex); V(empty); 14 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 full是“满”缓冲数目，初值为0。 empty是“空”缓冲数目，初值为N。 实际上，full和empty是同一个含义。 full + empty == N mutex用于访问缓冲区时的互斥，初值是1。 生产者进程 消费者进程 P(empty) P(full) P(mutex) P(mutex) 缓冲区 产品 取产品 V(mutex) V(mutex) V(full) V(empty) 15 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 生产者——消费者问题 经典的同步问题 整型变量in=0,out=0 资源信号量为empty=n ，full=0 互斥信号量为mutex=1 Producer(生产者) P(empty); P(mutex); buffer(in)=nextp; in= (in+1) % n; V(mutex); V(full); Consumer(消费者) P(full); P(mutex); nextc=buffer(out); out=(out+1) % n; V(mutex); V(empty); Q)二个V的次序可交换? 先mutex后资源信号量有利? 16 第五节 3.5.1 经典进程同步问题之一：生产者—消费者问题 经典的同步问题 Producer(生产者) P(empty); P(mutex); buffer(in)=nextp; in= (in+1) % n; V(mutex); V(full); Consumer(消费者) P(full); P(mutex); nextc=buffer(out); out=(out+1) % n; V(mutex); V(empty); 分析：如果将两个P操作，即 P(full)和P(mutex)互换位置，或者 P(empty)和 P(mutex)互换位置，其后果如何? 如果将两个V操作互换位置，即V(full)和V(mutex)互换位置，或者 V(empty)和V(mutex)互换位置，其后果又如何? 答∶在生产者—消费者问题中，如果将两个 P操作，即P(full)和 P(mutex)互换位置，或者P(empty)和P(mutex)互换位置，都可能引起 死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了P(mutex) 操作并获得成功，当再执行P(empty)操作时，它将因失败而进入阻塞 状态，它期待消费者执行V(empty)来唤醒自己，在此之前，它不可能 执行 V(mutex)操作，从而使企图通过P(mutex)进入自己的临界区的其 他生产者和所有的消费者进程全部进入阻塞状态，从而引起系统死锁。 类似地，消费者进程若先执行 P(mutex)，后执行 P(full)同样可能造成 死锁。 V(full)和V(mutex)互换位置，或者V(empty)和V(mutex)互换位置， 则不会引起死锁，其影响只是改变临界资源的释放次序。 17 第五节 //生产者 semaphore empty=n;//同步信号量 Producer(){ semaphore full=0;//同步信号量 while(1){ semaphore mutex=1;//互斥信号量 P(empty); //生产者申请一个可用缓冲区 int in,out=0;//放数取数指针 P(mutex);//互斥使用缓冲区 生产者和消费者之间的约束：临界区。 buffer(in)=nextp; 生产者在生产时，消费者不能消费。 in= (in+1) % n; V(mutex);//释放缓冲区占用权 V(full); //增加一个消费者可用数量 } 控制：缓冲区满时不能继续生产， 控制：缓冲区空 } 制约生产者进程P。(同步关系) 经典的同步问题 时不能继续消费， 制约消费者进程 C。(同步关系) //消费者 Consumer(){ while(1){ P和V操作成对出现； P(full); //申请一个消费者可用数量 对资源信号量的P操作在前 P(mutex); //互斥使用缓冲区 生产者和消费者之间的约束：临界区。 nextc=buffer(out); 对互斥信号量的P操作在后 生产者在生产时，消费者不能消费。 out=(out+1) % n; V(mutex); //释放缓冲区使用权 V(empty); //增加一个缓冲区（生产者可用数量） } 18 } 第五节 回顾思考：单缓冲区问题与生产者——消费者问题区别 经典的同步问题 单缓冲的情况下，缓冲区只需用简单变量来描述，而不必再用数组;另外，也不再 需要in/out指针来指示产品放到（取自）哪个缓冲区，而且，由于此时生产者、 消费者不可能同时访问缓冲区，所以原来的mutex信号量也不再需要。 Producer(生产者) P(empty); P(mutex); buffer(in)=nextp; in= (in+1) % n; V(mutex); V(full); Consumer(消费者) P(full); P(mutex); nextc=buffer(out); out=(out+1) % n; V(mutex); V(empty); 19 读者——写者问题 • 问题描述：读者和写者共若干人，都可以向同一个存储区 进行操作。 • 写者执行写操作时,每次只允许一位写者进行写操作；读者 执行读操作，可以多名读者同时进行读操作，读者读的时 候写者不能写。 20 20 读者——写者问题 • 问题描述：对共享资源的读写操作，任一时刻“写者”最 多只允许一个，而“读者”则允许多个。 – “读－写”互斥， – “写－写”互斥， – "读－读"允许 21 21 读者——写者问题 • 写者信号量mutex: 实现读者与写者进程间的互斥。 • 读者计数 rcount • 读者信号量rmutex 注：其中写者信号量的权力最大，如果写者获得，读者 不能读；如果读者获得，读者能读但不能写，写者 肯定不能写。 22 22 读者——写者算法 23 23 读者——写者算法说明 n 算法说明： q q 由于只有一个读者进程在读时便不允许写者进程 去写。因此，仅当rcount=0,表示尚无读者进程 在读时，读者进程才需要执行P(mutex)操作。 若P(mutex)操作成功，读者进程便可去读，相 应地，做rcount+1操作。 同理，仅当读者进程在执行了rcount减1操作后 其值为0时，才须执行V(mutex)操作，以便让写 者进程去写。 24 24 第五节 3.5.1 经典进程同步问题之二：读者—写者问题 经典的同步问题 R 共享文件 读者 RN>= 1 W 写者 R文件 WN=0 W文件 RN=0 WN=1 25 第五节 利用记录型信号量解决读者---写者问题 3.5.1 经典进程同步问题之二：读者—写者问题 经典的同步问题 R 共享文件 读者 W 写者 wmutex=1 P(wmutex); Read; V(wmutex); RN=1 R文件 P(wmutex); Write; V(wmutex); WN=0 W文件 RN=0 WN=1 26 第五节 3.5.1 经典进程同步问题之二：读者—写者问题 经典的同步问题 共享文件 R W Rn>0 rn=0 计数器初值rn=0 if (rn==0 ) P(wmutex); rn=rn+1; Read; rn=rn-1; if (rn==0 ) V(wmutex); 初值wmutex=1 P(wmutex); write; V(wmutex); 27 第五节 3.5.1 经典进程同步问题之二：读者—写者问题 共享文件 经典的同步问题 R Rn>0 W rn=0 初值wmutex=1 P(rmutex); if (rn==0 ) P(wmutex); rn=rn+1; V(rmutex); Read; P(rmutex); rn=rn-1; if (rn==0 ) V(wmutex); V(rmutex); 计数器初值rn=0 rn为临界资源 信号量Rmutex=1 P(wmutex); write; V(wmutex); 28 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 经典的同步问题 思考 饥饿 拿到左右两边筷子？ 用餐 等候 放下两边筷子 29 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 经典的同步问题 哲学家就餐过程描述如下： semaphore fork[5] = {1,1,1,1,1}; do { P(fork[i])； P(fork[(i+1)%5])； 就餐； V(fork[i])； V(fork[(i+1)%5])； 思考； }while (TRUE); 思考1：这样的解法有何问题？ 思考2：对左右的叉子是否可用进 行验证，这样的修改有何优缺点？ 思考3：需要引入几个信号量才能 实现最优化的解法呢？ 30 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 经典的同步问题 哲学家就餐死锁问题的解决方法 1 最多允许4个哲学家同时去拿左手边的叉子， 在就餐完毕后放 下叉子，其他的哲学家能够就餐 2 哲学家只有将左右两把叉子同 时拿到后才能就餐，否则放弃叉子 3 奇数者先左后右拿二边的叉子, 偶数号哲学家则相反,先右后左拿叉子。 4 调整哲学家就餐拿起叉子的时间，分间隔时间进行 31 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 经典的同步问题 引入变 量的基 本方法 最多允许4个哲学家同时能够就餐 计数变量Count=0（初值） Count= =5 互斥信号量mutex=1（初值） 进入部分 P(mutex); Count=count+1; if (count==5) P(S); V(mutex); If (count==5) {V(mutex);P(S);}; else V(mutex); 阻塞信号量S=0 （初值） 退出部分 P(mutex); Count=count-1; if (count==4) V(S); V(mutex); 32 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 经典的同步问题 最多允许4个哲学家同时能够就餐 计数变量Count=4（初值） Count<0 互斥mutex=1（初值） 进入部分 P(mutex); Count=count-1; if(count<0){V(mutex);P(S);}el se V(mutex); 阻塞信号量S=0 （初值） 退出部分 P(mutex); Count=count+1; if(count==0 )V(S); V(mutex); 33 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 经典的同步问题 P(S); P(mutex); Count=count-1; If (count<0 ){V(mutex);P(S)}; else V(mutex); P(fork[i])； P(fork[(i+1)%5])； 就餐； V(fork[i])； V(fork[(i+1)%5])； V(S); P(mutex); Count=count+1; if count=0 then V(S); V(mutex); 思考；} semaphore; S=4 do {P(S); P(fork[i])； P(fork[(i+1)%5])； 就餐； V(fork[i])； V(fork[(i+1)%5])； V(S); 思考； }while (TRUE); 34 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 计数变量Count=信号量S1的初值 经典的同步问题 互斥mutex=1（初值） 阻塞信号量S=0 （初值） P(mutex); Count=count-1; if (count<0){V(mutex);P(S)}; else V(mutex); P(mutex); Count=count+1; if (count==0) V(S); V(mutex); 计数变量Count在程序中能参加运算 P(S1) V(S1) 35 第五节 3.5.1 经典进程同步问题之三：哲学家就餐问题 经典的同步问题 procedure PB（s） { if (S.value==1) S.value=0; else block(S,L) }; procedure VB（s） { if (S.queue.is_empty()) S.value=1 ; else wakeup(S,L); }; 按信号量的取值分 二元信号量(1,0)／一般信号量(n) 按实施P，V操作分 公用信号量(＝１)／私用信号量(>=0) 36 信号量其它应用问题 (例1)吃水果 父(apple) plate (empty) =1 儿(orange) orange(full2)=0 果盘 女(apple) 母(orange) apple (full1)=0 37 信号量其它应用问题 P(plate); Put apple; V(apple); 二个不同的生产者和消费者 程序数与进程数的关系 apple orange P(orange); Take orange; V(plate); 果盘 apple P(plate); orange Put orange; 单缓冲取放数问题 V(orange); P(apple); Take apple; V(plate); 38 信号量其它应用问题 §§ 变量设置： 题目： –dish：表示盘子是否为空，初值=1； – 桌上有一个盘子，可以存放一个水果。父亲总是把苹果放在盘子中， 母亲总是把香蕉放在盘子中；一个儿子专等吃盘中的香蕉，一个女 –apple：表示盘中是否有苹果，初值=0； 儿专等吃盘中的苹果。 –banana：表示盘中是否有香蕉，初值=0。 § 分析： § 进程描述： –四人公用一个盘子； –Father：父亲放置水果的进程； –盘子每次只能放一个水果，当盘子为空时，父母均可尝试放 –Mother：母亲放置水果的进程； 水果，但一次只能有一人成功； –Son：儿子吃水果的进程； –盘中是香蕉，儿子吃，女儿等； –Daughter：女儿吃水果的进程。 –盘中是苹果，女儿吃，儿子等。 39 信号量其它应用问题 Father: P ( dish ); dish：盘子是否为空，1 apple：盘中是否有苹果，0 banana：盘中是否有香蕉，0 Son: 将苹果放入盘中； P ( banana ); V ( apple ); 从盘中取出香蕉； Mather: P ( dish ); V ( dish ); 吃香蕉； Daughter: 将香蕉放入盘中； P ( apple ); V ( banana ); 从盘中取出苹果； V ( dish ); 吃苹果； 40 (例2)过桥问题 § 题目： –有一座桥如图所示，车流如 图中箭头所示。桥上不允许 两车交会，但允许同方向多 辆车依次通行（即桥上可以 有多个同方向的车）。 –用P、V操作实现交通管理， 以防止桥上堵塞。 41 (例2)过桥问题 § 进程描述： § 分析： –North、South：分别代表北方、南方车辆过桥的进程 –车辆过桥时，提出过桥申请，如桥上无对方车辆则过桥； § 变量设置： –若该车为本方向第一辆车，应阻塞对方车辆过桥； –mutexN：用于实现北方车辆互斥访问变量countN，初值=1； –mutexS：用于实现南方车辆互斥访问变量countS，初值=1； –当本方向无车辆过桥时，允许对方车辆过桥； –wait：用于实现双方申请过桥车辆的排队，初值=1； –同方向的多辆车可依次过桥，如果对方提出过桥申请，则 –countN：用于记录当前北方正在过桥及已申请过桥的车辆数， 阻塞本方向后续车辆过桥，待桥上车辆过完后，对方车辆 初值=0； 过桥。 –countS：用于记录当前南方正在过桥及已申请过桥的车辆数， 初值=0； –同方向车辆的控制类似于读者-写者问题 42 (例2)过桥问题 mutexN：北方车辆互斥访问变量countN，1 mutexS：南方车辆互斥访问变量countS，1 North: P ( wait ); P ( mutexN ); wait：双方申请过桥车辆的排队，1 countN：北方正在过桥及已申请过桥的车辆数，0 countS：南方正在过桥及已申请过桥的车辆数，0 if (countN==0) P( mutexS)//本方向第一辆车，阻塞对方车辆过桥 countN ++； V ( mutexN ); V ( wait ); 车辆过桥； P ( mutexN ); countN --； if (countN==0) V( mutexS)//本方向最后一辆车允许对方车辆过桥 V ( mutexN ); 43 (例2)过桥问题 mutexN：北方车辆互斥访问变量countN，1 mutexS：南方车辆互斥访问变量countS，1 wait：双方申请过桥车辆的排队，1 South: P ( wait ); countN：北方正在过桥及已申请过桥的车辆数，0 countS：南方正在过桥及已申请过桥的车辆数，0 P ( mutexS ); if (countS==0) P( mutexNS)//本方向第一辆车，阻塞对方车辆过桥 countS ++； V ( mutexS ); V ( wait ); 车辆过桥； P ( mutexS ); countS --； if (countS==0) V( mutexN)//本方向最后一辆车允许对方车辆过桥 V ( mutexS ); 44 （例3）信号量解决理发师问题(1) • 理发店理有一位理发师、一把理发椅和n 把供等候理发的顾客坐的椅子 • 如果没有顾客，理发师便在理发椅上睡觉 • 一个顾客到来时，它必须叫醒理发师 • 如果理发师正在理发时又有顾客来到，则 如果有空椅子可坐，就坐下来等待，否则 就离开 45 信号量解决理发师问题(2) • int waiting=0;//等候理发顾客坐的椅子数 • int CHAIRS=N; //为顾客准备的椅子数 • semaphore customers,barbers,mutex; • customers=0;barbers=0;mutex=1; 46 • • • • • • • • • • • • • • • • • • • • • • • • 信号量解决理发师问题(3) cobegin process barber( ) { while(true) { P(customers); //有顾客吗？若无顾客，理发师睡眠 P(mutex); //若有顾客时，进入临界区 waiting--; //等候顾客数少一个 V(barbers); //理发师准备为顾客理发 V(mutex); //退出临界区 cut_hair(); //理发师正在理发(非临界区) } } process customer_i( ) { P(mutex); //进入临界区 if(waitingB->D->A或C->D->B->A 或C.....的顺序是可行的 最终，A、B、C、D都完成了项目，银行家得到了贷款利润。 存在的安全序列是：C、B、D、A或C、D、B、A 29 第八节 3.8.2 安全序列、不安全状态、死锁的联系 避免死锁 企业 最大需求 已借走 最多还会借 企业 最大需求 已借走 最多还会借 A B C D A B C D 6 5 4 7 1 1+1=2 2 4 5 4-1=3 2 3 给B借1亿是不安全的，之后手里只剩下1亿， 如果其他的企业都 提出借款，那么任何一个 企业的需求都得不到满足… 6 5 4 7 1 1 2+2 4 5 4 2-2=0 3 给C借2亿是安全的， 因为存在C->B->D->A这样的安全序列 所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安 全序列，系统就是安全状态。当然，安全序列可能有多个。 30 第八节 3.8.2 安全序列、不安全状态、死锁的联系 避免死锁 Ø 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味 着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统 也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。 比如D 先归还了1亿，那么就 有安全序列B->C->D->A Ø 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（ 处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态） Ø 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答 应资源分配请求。这也是“银行家算法”的核心思想。 31 第八节 3.8.3 银行家算法 避免死锁 银行家算法是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不 会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。 核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如 果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。 l 操作系统（银行家） l 操作系统管理的资源(周转资金) l 进程（要求贷款的客户） 32 第八节 3.8.3 银行家算法 避免死锁 Ø 思考：银行贷款的例子中，只有一种类型的资源——钱，但是在计算机 系统中会有多种多样的资源，应该怎么把算法拓展为多种资源的情况呢？ Ø 可以把单维的数字拓展为多维的向量。比如：系统中有5个进程 P0~P4， 3种资源 R0~R2，初始数量为 (10, 5, 7)，则某一时刻的情况可表示如下： 企业 最大需求 已借走 最多还会借 A B C D 6 5 4 7 1 1 2 4 5 4 2 3 进程 最大需求 已分配 (R0,R1,R2) (R0,R1,R2) 最多还需要 (R0,R1,R2) P0 (7, 5, 3) (0, 1, 0) (7, 4, 3) P1 (3, 2, 2) (2, 0, 0) (1, 2, 2) P2 (9, 0 ,2) (3, 0, 2) (6, 0, 0) P3 (2, 2, 2) (2, 1, 1) (0, 1, 1) P4 (4, 3, 3) (0, 0, 2) (4, 3, 1) 减 此时总共已分配 (7, 2, 5)，还剩余 (10,5,7)- (7, 2, 5)=(3, 3, 2),可把最大需求、已分配 的数据看作矩阵，两矩阵相减，就可算出各进程最多还需要多少资源了 33 第八节 3.8.3 银行家算法 判断系统此时是否处于安全状态？（即寻找系统中是否存在安全调度序列） 避免死锁 进程 最大需求 已分配 (R0,R1,R2) (R0,R1,R2) 最多还需要 (R0,R1,R2) 资源总数 (7, 4, (5, 3, 3, 3) 2) 资源总数 (10, (10, 5, 5, 7)，剩余可用资源 7)，剩余可用资源 (3, 2) P0 (7, 5, 3) (0, 1, 0) (7, 4, 3) >(3, 3, 3, 2) 2) >(5, P1 (3, 2, 2) (2, 0, 0) (1, 2, 2) <(3, 3, 2) P2 (9, 0 ,2) (3, 0, 2) (6, 0, 0) >(5, 3, 2) P3 (2, 2, 2) (2, 1, 1) (0, 1, 1) <(5, 3, 2) P4 (4, 3, 3) (0, 0, 2) (4, 3, 1) 说明如果优先把资源分配给P1， 那P1一定是可以顺利执行结束 的。等P1结束了就会归还资源， 说明如果优先把资源分配给P3， 于是，资源数就可以增加到： 那P3一定是可以顺利执行结束 (2, 0, 0)+ (3, 3, 2)=(5, 3, 2) 的。等P3结束了就会归还资源， 于是，资源数就可以增加到： (2, 1, 1)+ (5, 3, 2)=(7, 4, 3) 思路：尝试找出一个安全序列…{...} {P1} {P1,P3} {P1,P3,P0,P2,P4} 依次检查剩余可用资源 (3, 3, 2) 是否能满足各进程的需求 (1)可满足P1需求，将 P1 加入安全序列，并更新剩余可用资源值为 (5, 3, 2) (2)依次检查剩余可用资源 (5, 3, 2) 是否能满足剩余进程（不包括已加入安全序列的进程）的需求 (3)可满足P3需求，将 P3 加入安全序列，并更新剩余可用资源值为 (7, 4, 3) (4)依次检查剩余可用资源 (7, 4, 3) 是否能满足剩余进程（不包括已加入安全序列的进程）的需求………… 以此类推，共五次循环检查即可将5个进程都加入安全序列中，最终可得一个安全序列。该算法称为安全性算法。 34 第八节 3.8.3 银行家算法 避免死锁 进程 最大需求 已分配 (R0,R1,R2) (R0,R1,R2) 最多还需要 (R0,R1,R2) P0 (7, 5, 3) (0, 1, 0) (7, 4, 3) P1 (3, 2, 2) (2, 0, 0) (1, 2, 2) P2 (9, 0 ,2) (3, 0, 2) (6, 0, 0) P3 (2, 2, 2) (2, 1, 1) (0, 1, 1) P4 (4, 3, 3) (0, 0, 2) (4, 3, 1) 资源总数 (10, 5, 7)，剩余可用资源 (7, (3,3,4,2) 3) {P1,P3} {P1,P3,P0,P2,P4} 实际做题（手算）时可用更快速的方法找到一个安全序列： 经对比发现，（3, 3, 2）可满足 P1、P3，说明无论如何，这两个进程的资源需求一定是可以依次被满足的，因 此P1、P3 一定可以顺利的执行完，并归还资源。 可把 P1、P3 先加入安全序列。 (2, 0, 0) + (2, 1, 1) + (3, 3, 2) = (7, 4, 3) 剩下的 P0、P2、P4 都可被满足。同理，这些进程都可以加入安全序列。 于是，5个进程全部加入安全序列，说明此时系统处于安全状态，暂不可能发生死锁。 35 第八节 3.8.3 银行家算法 避免死锁 进程 最大需求 已分配 (R0,R1,R2) (R0,R1,R2) 最多还需要 (R0,R1,R2) P0 (8, 5, 3) (0, 1, 0) (8, 4, 3) P1 (3, 2, 2) (2, 0, 0) (1, 2, 2) P2 (9, 5 ,2) (3, 0, 2) (6, 5, 0) P3 (2, 2, 2) (2, 1, 1) (0, 1, 1) P4 (4, 3, 6) (0, 0, 2) (4, 3, 4) 资源总数 资源总数(10, (10,5,5,7)，剩余可用资源 7)，剩余可用资源(3,3, (7, 4,2)3) {P1,P3} 再看一个找不到安全序列的例子： 经对比发现，（3, 3, 2）可满足 P1、P3，说明无论如何，这两个进程的资源需求一定是可以依次 被满足的，因此P1、P3 一定可以顺利的执行完，并归还资源。 可把 P1、P3 先加入安全序列。 (2, 0, 0) + (2, 1, 1) + (3, 3, 2) = (7, 4, 3) 剩下的 P0 需要 (8, 4, 3)，P2 需要 (6, 5, 0)，P4 需要 (4, 3, 4)。任何一个进程都不能被完全满足 于是，无法找到任何一个安全序列，说明此时系统处于不安全状态，有可能发生死锁。 可以很方便地用代码实现以上流程，每一轮检查都从编号较小的进程开始检查 36 第八节 3.8.3 银行家算法——数据结构 避免死锁 假设系统中有 n 个进程，m 种资源； 在系统中必须设置这样四个数据结构，分别用来描述系统中的量： （1）最大需求矩阵Max：每个进程在运行前先声明对各种资源 的最大需求数，可用一个n*m的矩阵，如果Max[i,j]＝K，则表示 进程 Max 矩阵 最大需求 Allocation 矩阵 Need 矩阵 已分配 最多还需要 (R0,R1,R2) (R0,R1,R2) (R0,R1,R2) 进程i需要Rj类资源的最大数目为K。 P0 (7, 5, 3) (0, 1, 0) (7, 4, 3) （2）分配矩阵 Allocation: 这也是一个n*m的矩阵，定义了系 P1 (3, 2, 2) (2, 0, 0) (1, 2, 2) 统中每一类资源当前已分配给每一进程的资源数。如果 P2 (9, 0 ,2) (3, 0, 2) (6, 0, 0) P3 (2, 2, 2) (2, 1, 1) (0, 1, 1) P4 (4, 3, 3) (0, 0, 2) (4, 3, 1) Allocation[i,j]＝K,则表示进程Pi当前已分得Rj类资源的数目为K。 （3）需求矩阵Need: n*m的矩阵，表示每一个进程尚需的各类 资源数。如果Need[i,j]＝K，则表示进程Pi还需要Rj类资源K个,方 Available=(3,3,2) 能完成其任务。Need[i, j]=Max[i, j]-Allocation[i, j] （4）可利用资源向量 Available: 长度为m的一维数组，表示当前系统中还有多少可用资源。其初始 值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[ j]＝K，则表示系统中现有Rj类资源K个 37 3.8.3 银行家算法——实现过程 某进程Pi向系统申请Rj类资源，可用 Request[i, j]请求向量表示，如果 Request[i, j]＝K，表示 进程Pi需要Rj类资源K个。当Pi发出资源请求后，可用 银行家算法预判本次分配是否会导致系统进入不安全状态： （1）如果 Request[i, j］≤Need[i, j］便转向步 骤(2);否则认为出错，因为它所需要的资源数已超 过它所宣布(请求)的最大值。 （2）如果 Request[i, j］≤ Available[j]，便转向 步骤(3); 否则，表示尚无足够资源，Pi须等待。 （3）系统试探着把资源分配给进程Pi，并修改下 面数据结构中的数值(并非真分配，修改数值只是 为了做预判)： 进程 Max 矩阵 最大需求 Allocation 矩阵 Need 矩阵 已分配 最多还需要 (R0,R1,R2) (R0,R1,R2) (R0,R1,R2) P0 (7, 5, 3) (7, 3, 4, 2) 3) (5, (3, 2, 2) (0, 2, 1, 1) 0) (2, (2, 0, 0) P1 P2 (9, 0 ,2) (3, 0, 2) (6, 0, 0) P3 (2, 2, 2) (2, 1, 1) (0, 1, 1) P4 (4, 3, 3) (0, 0, 2) (4, 3, 1) Available=(1,2,1) Available=(3,3,2) (1, 2, 2) Request0=(2,1,1) Available[ j] = Available[ j] - Request [i, j]; Allocation[i,j] = Allocation[i,j] + Request[i, j]; Need[i, j] = Need[i, j] - request[i, j]; 38 3.8.3 银行家算法——实现过程 Max 矩阵 （4）操作系统执行安全性算法，检查此次资 进程 最大需求 P0 (7, 5, 3) 式将资源分配给进程Pi，以完成本次分配；否 P1 配状态，让进程Pi阻塞等待。 Need 矩阵 已分配 最多还需要 (R0,R1,R2) (R0,R1,R2) (R0,R1,R2) 源分配后系统是否处于安全状态。若安全，正 则，将本次的试探分配作废，恢复原来资源分 Allocation 矩阵 (7, 3, 4, 2) 3) (5, (3, 2, 2) (0, 2, 1, 1) 0) (2, (2, 0, 0) P2 (9, 0 ,2) (3, 0, 2) (6, 0, 0) P3 (2, 2, 2) (2, 1, 1) (0, 1, 1) P4 (4, 3, 3) (0, 0, 2) (4, 3, 1) Available=(1,2,1) Available=(3,3,2) (1, 2, 2) Request0=(2,1,1) 39 3.8.3 银行家算法——实现过程 进程Pi申请K个Rj类型的资源 K≤Need[i,j]? Y K≤ Available[j]? Y 尝试为Pi分配K个Rj类型的资源 系统是否安全? Available[j]=Available[j]-K Allocation[i,j]=Allocation[i,j]+K Need[i,j]=Need[i,j]-K 利用安全性算法进行进 行检测 恢复原来的资源分配状况 40 3.8.4 安全性算法——实现过程 系统所执行的安全性算法可描述如下： 检查当前的剩余可用资源是否能满足某个进程的最大需求， 如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。 不断重复上述过程，看最终是否能让所有进程都加入安全序列。 安全性算法步骤： （1）设置两个向量： ①工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，它含 有m个元素，在执行安全算法开始时，work＝ Available; ② Finish: 表示系统是否有足够的资源分配给进程，使之运行完成。 开始时先设 Finish[i]＝ false；当有足够资源分配给进程时，再令 Finish[i]＝tur 41 3.8.4 安全性算法——实现过程 （2）从进程集合中找到一个能满足下述条件的进程： ① Finish[i]＝ false Work=Available； ② Need[i,j]≤ Work[ j] 若找到，执行步骤（3），否则，执行步骤（4）。 Fininsh[i]=False； 对Finish[i]为False的进程： （3）当进程P获得资源后，可顺利执行，直至完成，并 if(Need[i,j] ≤Work[i]) 释放出分配给它的资源，故应执行： { Work[ j]= Work [ j]+ Allocation[i, j]; Work[i]=Work[i]+Allocation[i,j]; Finish[i]= true; Finish[i]=True; go to step 2: } （4）如果所有进程的 Finish[i]＝true都满足，则表示系 如果所有的Finish[i]都为True， 表示系统处于安全状态。 统处于安全状态： 否则，系统处于不安全状态 42 3.8.5 银行家算法举例： 系统中有5个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各资源的数量 分别为10、5、7，T0时刻资源的分配情况如下所示。 资源 情况 进程 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 43 （1）判断系统此时是否处于安全状态？（即寻找系统中是否存在安全调度序列） 资源 情况 进程 Work Need Allocation Work +Alloction A B A B C A B C A B C P1 3 3 2 1 2 2 2 0 0 5 3 2 P3 5 3 2 0 1 1 2 1 1 7 4 3 P4 7 4 3 4 3 1 0 0 2 7 4 5 P0 7 4 5 7 4 3 0 1 0 7 5 5 P2 7 5 5 6 0 0 3 0 2 10 存在安全调度序列P1，P3，P4，P0，P2，因此系统是安全的。 5 C 7 44 （2）若P1发出请求向量Request1(1，0，2)，能否为其分配资源？ ① Request1(1，0，2)≤Need1(1，2，2) ② Request1(1，0，2)≤Available(3，3，2) ③ 系统尝试为P1分配资源，修改相关的数据结构。 进程 资源 情况 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 2 3 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 45 ④ 判断此时系统是否安全： 资源 情况 进程 Work Need Allocation Work +Alloction A B C A B C A B C A B C P1 2 3 0 0 2 0 3 0 2 5 3 2 P3 5 3 2 0 1 1 2 1 1 7 4 3 P4 7 4 3 4 3 1 0 0 2 7 4 5 P0 7 4 5 7 4 3 0 1 0 7 5 5 P2 7 5 5 6 0 0 3 0 2 10 5 7 存在安全调度序列P1，P3，P4，P0，P2，因此系统是安全的。 46 （3）若P4发出请求向量Request4(3，3，0)，能否为其分配资源？ ① Request4(3，3，0)≤Need4(4，3，1) ② Request4(3，3，0)≥Available(2，3，0) 此时可用资源无法满足请求资源的要求，因此P4进程等待。 47 （4）若P0发出请求向量Request0(0，2，0)，能否为其分配资源？ ① Request0(0，2，0)≤Need1(7，4，3) ② Request0(0，2，0)≤Available(2，3，0) ③ 系统尝试为P0分配资源，修改相关的数据结构。 进程 资源 情况 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 ④ 安全性检查： 此时可用资源无法满足任何进程的需求，因此不能为进程P0分配资源。 48 第八节 基本事实 避免死锁 如果一个系统在安全状态，就没有死锁 如果一个系统不是处于安全状态，就有可能死锁 死锁避免  确保系统永远不会进入不安全状态 49 第八节 知识回顾与总结 避免死锁 银行家算法数据结构： 长度为 m 的一维数组 Available 表示还有多少可用资源 n*m 矩阵 Max 表示各进程对资源的最大需求数 n*m 矩阵 Allocation 表示已经给各进程分配了多少资源 Max – Allocation = Need 矩阵表示各进程最多还需要多少资源 n*m 矩阵 Request 表示进程此次申请的各种资源数 银行家算法步骤： ①检查此次申请是否超过了之前声明的最大需求数 ②检查此时系统剩余的可用资源是否还能满足这次请求 ③试探着分配，更改各数据结构 ④用安全性算法检查此次分配是否会导致系统进入不安全状态 50 第八节 知识回顾与总结 避免死锁 安全性算法步骤： ①设置两个向量：初始Work=Available；Fininsh[i]=False； ②从进程集合中找到一个能满足下述条件的进程： ① Finish[i]＝ false ② Need[i,j]≤ Work[ j] 若找到，执行步骤（3），否则，执行步骤（4） ③当进程获得资源顺利执行后，释放资源，执行： Work[ j]= Work [ j]+ Allocation[i, j]; Finish[i]= true; go to step 2: ④如果所有进程的 Finish[i]＝true都满足，则表示系统处于安全状态： 否则，系统处于不安全状态 系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。 51 练习题 假定系统中有5个进程P0、P1、P2、P3、P4和4种资源A、B、C、D，若 出现如表所示资源分配情况。 进程 已分配到资源 尚需资源需求 当前可用资源数 P0 （1，1，1，0） （0，3，3，1） （0，3，2，2） P1 （0，2，3，1） （0，3，4，2） P2 （0，2，1，2） （1，0，3，4） P3 （0，3，1，0） （0，3，2，0） P4 （1，0，2，1） （0，4，2，3） 问：（1）该状态是否安全？为什么？ （2）如果进程P0提出资源请求（0，0，0，1），系统能否将资源分配给它？为什么？ 52 练习题 严格按照银行家算法及安全检查子算法进行。 （1）初始状态如表所示。 进程 Work Need Allocation Work +Allocation Finish P3 0，3，2，2 0，3，2，0 0，3，1，0 0，6，3，2 True P0 0，6，3，2 0，3，3，1 1，1，1，0 1，7，4，2 True P1 1，7，4，2 0，3，4，2 0，2，3，1 1，9，7，3 True P4 1，9，7，3 0，4，2，3 1，0，2，1 2，9，9，4 True P2 2，9，9，4 1，0，3，4 0，2，1，2 2，11，10，6 True 存在一个安全序列P3，P0，P1，P4，P2，所以，该状态是安全的。 53 练习题 （2）Request0(0，0，0，1) 将导致Finish[i] = true，因此死锁不存在。 68 第九节 3.9.1 死锁的检测 例子（续） 死 锁 的 检 测 与 解除 P2请求一个额外的C实例 P0 P1 P2 P3 P4 Request ABC 000 201 001 100 002 系统的状态？ Ø 可以归还P0所有的资源，但是资源不够完成其他进程的请求。 Ø 死锁存在，包括进程P1、P2、P3和P4。 69 第九节 3.9.2 死锁的解除 死 锁 的 检 测 与 解除 常用解除死锁的两种方法： 01 02 抢占资源。从一个或多个进程中抢占足够数量的资源给死锁进程， 以解除死锁状态 终止或撤消进程。终止系统中一个或多个死锁进程，直到打破循环 环路，使死锁状态消除为止。 Ø终止所有死锁进程（最简单方法） Ø逐个终止进程（稍温和方法） 70 第九节 3.9.2 死锁的解除 死 锁 的 检 测 与 解除 中断所有的死锁进程。 一次中断一个进程，直到死锁环消失。 应该选择怎样的中断顺序，使“代价最小”？ Ø 进程的优先级； Ø 进程需要计算多长时间，以及需要多长时间结束； Ø 进程使用的资源，进程完成还需要多少资源； Ø 进程是交互的还是批处理的。 71 练习题 假设系统中有下述解决死锁的办法： （1）银行家算法； （2）检测死锁，终止处于死锁状态的进程，释放该进程占有的资源； （3）资源预分配。 简述哪种办法允许最大的并发性？请按“并发性”从大到小对上述3种办法 排序 72 题中给出的3种办法中，检测死锁能允许更多的进程无等待地向前推进，并发性最大。 因为该方法允许进程最大限度地申请并分配资源，直至出现死锁，再由系统解决。 银行家算法允许进程自由申请资源，只是在某个进程申请时检查系统是否处于安全状 态，若是，则可立即分配，若不是，才拒绝。并发性大小次于检测死锁的方法。最后 是资源预分配，因为此方法要求进程在运行之前申请所需的全部资源才可以，这会使 得许多进程因申请不到资源而无法开始，得到部分资源的进程因得不到全部资源也不 释放已占用的资源，因此导致资源的浪费。因此，3种方法的并发性按从大到小排序 为：检测死锁、银行家算法、资源预分配。 73 课程思政小讲堂 中科红旗之后，谁将再次勇战操作系统世界霸主？ 提及北京中科红旗软件技术有限公司（简称中科红旗），读者可能有所不 知，从事计算机信息技术领域具备国产自主知识产权的“红旗Linux系统”研 发的中科红旗，曾长期占据国产操作系统市场老大位置。因此对于操作系统 领域的相关人员而言，中科红旗绝对是一个“难以忘怀”的名字。 20世纪90年代初期，在微软公司大举进入中国市场并展示傲慢的信息技术 （information technology，IT）巨头形象时，中科红旗被它的过分张扬与 霸道所激怒，随即燃起了“起来，抵抗微软公司”的民族情绪，并联合北京 金山办公软件股份有限公司（简称金山）等民族软件厂商抵抗微软公司的市 场垄断行为。之后，红旗Linux系统在国内外渐渐具备一定的影响力，广泛 74 课程思政小讲堂 中科红旗之后，谁将再次勇战操作系统世界霸主？ 应用于国家信息平台正版化、中国科学院、国家外汇管理局等全国性关键应 用领域的国产信息化建设之中。联想、戴尔、惠普等公司的计算机也都曾预 装过红旗Linux系统。 不料在种种因素的影响下，2014年2月10日，中科红旗突然宣布解散，引 发业界轩然大波，令人感到万分遗憾！实际上，中科红旗的对手——微软公 司是一家称霸全球、长期占据操作系统第一位置的企业，其庞大的生态系统， 就像一艘巨型游轮，与之较量，实属不易。此外，令中科红旗十分尴尬的事 实是，国人似乎已形成一种消费心理定势，宁可将预装的正版Linux系统卸载， 也要安装上盗版的Windows系统！ 75 课程思政小讲堂 中科红旗之后，谁将再次勇战操作系统世界霸主？ 但是，这些都不是理由！当下，我们必须重整旗鼓、自主创新，要以蚕 食桑叶之精神，与垄断型的操作系统争完善、比实用，待势均力敌之时再与 它们抢市场、争地位。金山的WPS办公软件不就如此一路走来，现已可以取 代微软公司的Office办公软件了吗？！ 因此，无须畏惧现在的微软公司、苹果、谷歌等公司，只要我们坚持创 新，机会的大门就会永远为我们敞开。卧薪尝胆，刻苦自励，坚信下一个勇 于挑战Windows系统霸主地位的国产操作系统企业，定会浩然而至！ 76 实验案例 利用银行家算法避免死锁 • 最有代表性的避免死锁的算法是 Dijkstra的银行家算法。起这样的名字 是由于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时， 不会发生不能满足所有客户需要的情况。在OS中也可用它来实现避免死 锁要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源 总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分 配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会 使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等 待。 1．银行家算法中的数据结构利用的资源、所有进程对资源的最大需求、系统中的资源分配， 以及所有进程还需要多少 为了实现银行家算法，在系统中必须设置这样四个数 据结构，分别用来描述系统中可 （1）可利用资源向量 Available。这是一个含有m个元素的数组， 其中的每一个元素代资源的情况。表一类可利用的资源数目，其初 始值是系统中所配置的该类全部可用资源的数目，其数值随该类资 源的分配和回收而动态地改变。如果 Available[ j]＝K，则表示系 统中现有Rj类资源K个 （2）最大需求矩阵Max。这是一个nxm的矩阵，它定义了系统中n个进程中的每 个进程对m类资源的最大需求。如果Max[i，j]＝K，则表示进程i需要Rj类资源的 最大数目为K。 （3）分配矩阵 Allocation。这也是一个nxm的矩阵，它定义了系统中每一类资 源当前已分配给每一进程的资源数。如果 Allocation[i，j]＝K，则表示进程i当前 已分得R1类资源的数目为K。 （4）需求矩阵Necd这也是一个nxm的矩阵，用以表示每一个进程尚需的各类资 源数。如果Need[I,j]＝K，则表示进程i还需要Rj，类资源K个方能完成其任务上述 三个矩阵间存在下述关系：Need[i, j]=Max[i, j]-allocation[i, j] 2．银行家算法 设 Request；是进程P的请求向量，如果 Request＝K，表示进程P需要K个类型的资源。当P发 出资源请求后，系统按下述步骤进行检查： （1）如果 Request[i，j]≤Need[i，j]便转向步骤（2）：否则认为 出错，因为它所需要的资源数已超过它所宣布的最大值。 （2）如果 Request[i， j］≤ Available[i]，便转向步骤（3）;否则， 表示尚无足够资源，Pi须等待。 （3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数 值：Available[ j]= Available[ j]-Request[i，J]; Allocation [i, j] =Allocation[i, j]+Request[i，j]: Need[i, j]= Need[i, j]-request[i，j]; （4）系统执行安全性算法，检查此次资源分配后系统是否处于安全 状态。若安全，正式将资源分配给进程Pi，以完成本次分配：否则， 将本次的试探分配作废，恢复原来资源分配状态，让进程Pi等待。 3．安全性算法 系统所执行的安全性算法可描述如下： （1）设置两个向量：①工作向量work，它表示系统可提供给进程继续运 行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，work ＝ Available;(2) Finish:它表统示系统是否有足够的资源分配给进程，使之 运行完成。开始时先做 Finishi[i]＝ false；当有足够资源分配给进程时， 再令 Finish[i]＝ture（2）从进程集合中找到一个能满足下述条件的进程： ① Imishli＝ false② Need[i,j]≤ Work[ j]若找到，执行步骤（3），否则， 执行步骤（4）。 (3)当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它 的资源，故应执行：Work[ j]= Work [ j]+ Allocation[i, j]; Finish[i]= true; go to step 2: （4）如果所有进程的 Finishi＝true都满足，则表示系统处于安全状 态：否则，系统处于不安全状态 银行家算法之例 假设五个进程{P0，P1，P2，P3，P4}，三个资源{A,B,C}，各种资 源的数量分别为10、5、7。T0时刻的资源分配表如下。 进程\资源情况 最大需求 分配 需求 可利用 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 (2 3 2 0) P1 3 2 2 2 0 (3 0 0 2) 1 2 (0 2 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 T0时刻存的安全性：利用安全性算法对T0时刻的资源分配情况进行 分析可知，T0时刻存在一个安全序列{P1,P3,P4,P2,P0}故系统是安全 的 进程\资源情况 Work Need Allocation Workl+Allocation Final A B C A B C A B C A B C P1 3 3 2 1 2 2 2 0 0 5 3 2 TRUE P3 5 3 2 0 1 1 2 1 1 7 4 3 TRUE P4 7 4 3 4 3 1 0 0 2 7 4 5 TRUE P2 7 4 5 6 0 0 3 0 2 10 4 7 TRUE P0 10 4 7 7 4 3 0 1 0 10 5 7 TRUE P1请求资源，p1发出请求向量Request1（1，0，2），系统按银行家算法进行 检查： 1.Request1(1,0,2)≤Need1(1,2,2); 2.Request1(1,0,2)≤Available1(3,3,2); 3.系统先假定可为p1分配资源,并修改Available1,Allocation1,和Need1向量,由 此形成的资源变化情况在T0时刻为 P1 3 2 2 3 0 2 0 2 4.再利用安全性算法检查此时系统是否安全，如图。 0 2 3 0 进程\资源情 况 Work Need Allocation Workl+Allocation Final A B C A B C A B C A B C P1 2 3 0 0 2 0 3 0 2 5 3 2 TRUE P3 5 3 2 0 1 1 2 1 1 7 4 3 TRUE P4 7 4 3 4 3 1 0 0 2 7 4 5 TRUE P0 7 4 5 7 4 3 0 1 0 7 5 5 TRUE P2 7 5 5 6 0 0 3 0 2 10 5 7 TRUE 由所进行的安全性检查可知，可以找到一个安全性序列 {P1,P3,P4,P2,P0}，因此系统是安全的，可以将p1所申请的资源分 配给他。 （3）P₄ 请求资源：P₄ 发出请求向量Request₄ （3，3，0），系统按银行 家算法进行检查： 1.Request₄ （3，3，0）≤Need₄ （4，3，1）； 2.Request₄ （3，3，0）＞Available（2，3，0），让P₄ 等待。 （4）P₀ 请求资源：P₀ 发出请求向量Request₀ （0，2，0），系统按银行 家算法进行检查： 1.Request₀ （0，2，0）≤Need₀ （7，4，3）； 2.Request₀ （0，2，0）≤Available（2，3，0）； 3.系统暂时先假定可为P₀ 分配资源，并修改有关数据，如图 进程\资源情况 P0 P1 P2 P3 P4 Allocation A B C 0 3 3 3 0 2 3 0 2 2 1 1 0 0 2 Need A B 7 2 0 2 6 0 0 1 4 3 C 3 0 0 1 1 Available A B C 2 1 0 (5)进行安全性检查，可用资源Availabale（2，1，0）已不能满 足任何进程的需要，故系统进入不安全状态，此时系统不分配资 源。