计算机操作系统第四章.ppt

1 第4章并发与互斥 基本概念互斥 软件方法硬件方法信号量机制管程死锁 主要内容 2 4 1基本概念 4 1 1临界资源和临界区临界资源 CriticalResources 一种一次只能为一个进程服务的资源 临界区 CriticalSection 进程中访问临界资源的程序 每个使用该资源的进程都要包含一个临界区 操作系统在管理可控制资源分配与使用方面 应当保证进程对临界资源的访问满足以下3点 l互斥访问要求 l不致于产生 死锁 l不能有 饥饿 进程 3 4 1 2互斥管理准则 空闲让进 当没有进程在临界区时 任何需要进入临界区的进程都允许立即进入 忙则等待 在共享同一对象的所有进程中 一次只能有一个进程进入临界区 其它要求进入临界区的进程只能等待 有限等待 任何一个进程经有限时间等待后都能进入临界区 不允许出现进程死锁或饥饿的情况发生 让权等待 当一个进程不能进入临界区时要立即阻塞自己 释放处理机让其它进程使用 避免 忙等 4 4 2互斥 软件方法 第一次尝试算法中设计了一个变量turn保存允许进入临界区的进程编号 初值为1 表示进程1可以首先进入 当一个进程要求进入临界区时 先检查turn的值 若turn保存的不是自己的进程编号就进行循环等待 否则进入临界区 访问完成后退出临界区 再将turn设置为对方的进程编号 第二次尝试算法中定义了一个标志数组flag 当flag i true 表示进程i正在临界区 初始时Flag 的各分量值皆为false 表示尚无进程进入 当一个进程要求进入临界区时 先检查是否有进程已进入 若有进程进入 就循环等待 否则 设置自己的标志为真 立即进入 访问完成后再将自己的标志设为假 4 2 1Dekker方法 5 算法如下 ProcessP 1 ProcessP 2 Beginbegin While Flag 2 doskip While Flag 1 doskip Flag 1 true Flag 2 true Criticalsection Criticalsection Flag 1 false Flag 2 false end end 6 第三次尝试 在第二次尝试的基础上 将其中的两个语句顺序交换 形成了新的算法如下 ProcessP 1 ProcessP 2 Beginbegin Flag 1 true Flag 2 true While Flag 2 doskip While Flag 1 doskip Criticalsection Criticalsection Flag 1 false Flag 2 false end end 7 第四次尝试 这是一个 礼让为先 的算法 每个进程设置好自己的flag标志 表明希望进入临界区 但也准备重置flag 以表示谦让 算法如下 ProcessP 1 ProcessP 2 Beginbegin Flag 1 true Flag 2 true While Flag 2 doWhile Flag 1 do flag 1 false flag 2 false flag 1 true flag 2 true Criticalsection Criticalsection Flag 1 false Flag 2 false end end 8 正确的算法 为了避免过度互斥礼让的问题 Dekker使用第一种尝试中的轮盘变量turn 表示哪个进程有权进入临界区 让它在两个进程的活动中规定一个强制性的顺序 算法如下 ProcessP 1 ProcessP 2 Beginbegin Flag 1 true Flag 2 true While Flag 2 doWhile Flag 1 doif turn 2 if turn 1 flag 1 false flag 2 false while turn 2 doskip while turn 1 doskip flag 1 true flag 2 true Criticalsection Criticalsection turn 2 turn 1 Flag 1 false Flag 2 false end end 9 4 2 2Peterson算法 变量turn用来保存进程的编号 当turn i 表示进程i有权进入临界区 数组flag表示哪个进程进入了临界区 Flag i true 表示进程i已进入 初始时 标志数组flag的各元素值皆为false 表示无进程进入临界区 变量turn可以不设初始值 下面是该算法的主要部分 ProcessP 1 ProcessP 2 Beginbegin Flag 1 true Flag 2 true turn 2 turn 1 While Flag 2 turn 2 While Flag 1 turn 1 doskip doskip Criticalsection Criticalsection Flag 1 false Flag 2 false end end 10 4 3硬件方法 4 3 1交换指令将两个指定位置上的数据进行交换 是该指令实现的操作 微型机PC上对应的指令格式是XCHGop1 op2 用于交换两个操作对象的值 其中 opi是操作对象 交换指令的功能可描述为下面的过程 ProcedureXCHG op1 op2 BeginBooleantemp temp op1 op1 op2 op2 temp End 11 4 3 2测试与设置指令 该指令将状态测试和状态设置集于一条指令中 形成一个原子操作 也就是说 两个操作的执行不受中断信号的干扰 下面将指令格式定义为TS 功能是 读出一个指定变量的值 同时将一个新值置入 对于逻辑变量 比如lock TS 的测试和设置的功能可描述为下面的函数 FunctionTS lock BeginTS Lock Lock true End 12 下面的例子中定义的全局变量是mutex 初始值为false表示无人进入 利用TS指令实现的互斥机制描述如下 ProcedureProcess i Begin While TS mutex doskip 循环等待Criticalsection mutex false End 13 4 4信号量机制 著名的计算机学者Dijkstra通过长期的操作系统研究与设计 于1965年提出了一种同步机制 信号量机制 该机制由一个称为信号量 Semaphore 也译为 信号灯 的特殊变量和两个被命名为P V操作的原语组成 在广泛的应用中 该机制得到了迅速发展 这一机制的基本原理是 为每个临界资源设置一个信号量 负责在多个进程之间转发互斥信息 当一个进程需要互斥使用某个临界资源时 可通过对信号量的P操作 了解该资源的空闲情况 当它使用完该临界资源后 又可通过对相关信号量的V操作 让其它需要该资源的进程感知到它的离去 若一个资源被视为临界资源 就应当为它定义一个独立的信号量 对进程访问起 放行 和 阻止 作用 就像交通管理中每个路口设置的交通灯一样 14 4 4 1整型信号量 整型信号量是Dijkstra最初提出的一种信号量 被定义为整型变量 其取值范围是 0 1 其值等于1是放行状态 也称作 绿灯 等于0为阻止状态 也称作 红灯 整型信号量机制中的P V操作是两个小巧玲珑的过程 它们是操作系统中提供的两个原语 其代码如图所示 15 利用整型信号量机制实现进程互斥访问临界资源时 需要为该资源设一个整型信号量 比如mutex 令其初始值为1 表示它的初始状态空闲 每个要求访问临界资源的进程都要在临界区的前面通过P操作来访问mutex 决定是否可以立即进入临界区 此外 还要在临界区的后面使用V操作 声明使用完毕 程序结构如下所示 processp i begin P mutex Criticalsection V mutex end 16 4 4 2记录型信号量 记录型信号量机制是在整型信号量机制的基础上发展起来的 它实现了 让权等待 功能 一个记录型信号量包含两个分量 信号量的值 信号量的等待队列指针 描述如下 typesemaphore recordvalue integer L integer end 记录型信号量的取值范围是 N M 其值大于0时为放行状态 也称作 绿灯 状态 小于等于0时为阻止状态 也称作 红灯 状态 进程可通过执行P操作来了解临界资源的状态 如果发现当前为阻止状态时 就将进程阻塞起来 颇像是交通管理系统中的汽车过路口排队等候一样 17 P原语具有 阻塞 功能 当某个临界资源被其他进程占用时 就将自己阻塞 V原语具有 唤醒 功能 它能将等待该资源的进程唤醒 18 生产者 消费者问题 系统里有若干个合作的进程 其中 n n 0 个生产者进程 m m 0 个消费者进程 以及由P P 0 个缓冲区组成的缓冲区环 任何一个生产者进程都可以将自己的产品存入环内的一个缓冲区中 任何一个消费者可以将环内的一个产品取出 生产者源源不断地生产并存入产品 消费者周而复始地从环内取出产品并掉 假定使用的约束条件是 1 当环中有空闲缓冲区时 允许任一生产者进程把它的产品存入 2 当环中无空闲缓冲区时 则试图将产品存入缓冲区环的任何生产者进程必须等待 3 当环中尙有未取出的产品时 允许任一个消费者进程把其中的一个产品取出 4 当环中没有未取出的产品时 试图从该环内取出产品的任何消费者进程必须等待 19 图中 左侧的进程P1 Pn为生产者进程 右侧的S1 Sm为消费者进程 图中的缓冲区环内有8 P 8 个缓冲区 每个缓冲区可以存入一件产品 环上设有存入指针和读取指针 都按顺时针方向移动 20 生产者进程的同步控制程序描述为下述过程 Semaphore mutex Sin Sout1 8 0 Integer in out0 0 ParbeginProducer Consumer Parend ProcessProducer BeginWhile true BeginProduce an Item in NextP1 计算一个数据P Sin P mutex Buffer in NextP1 临界区in in 1 MOD8 V mutex V Sout 21 EndEndProcessConsumer BeginWhile true BeginP Sout P mutex NextP2Buffer out 临界区out out 1 MOD8 V mutex V Sin Consume an Item in NextP2 消费一个数据EndEnd 22 读者 写者问题有一个数据块被多个用户共享 其中部分用户是读者 另一部分是写者 我们规定 读者对数据块是只读的 而且允许多个读者同时读 写者对数据块是只写的 当一个写者正在向数据块写信息的时候 不允许其他用户使用 无论是读还是写 该问题中的数据块作为多个用户共享的资源 只要有读者使用时就不允许任何一个写者使用 当一个写者使用时 不允许其它写者或读者使用 因此 可以将数据块访问的程序视为临界区 但是 数据块不是绝对的临界资源 因为它允许多个读者用户同时使用 这一问题是由Courtois等人提出了解决方案 首先 使用一个互斥信号量mutex 实现读者与写者 写者与写者之间的互斥 由于读者可以同时访问数据块 因此我们让第一个准备进入临界区的读者 通过P mutex 强占临界资源 以便排斥写者访问 当最后一个读者离开临界区时 通过V mutex 将临界资源释放 以便其它用户使用 其次 设计一个专为读者共享的变量counter 让它记录读数据块的人数 Counter应视为临界资源 应有一个互斥信号量 比如Rmutex 23 程序结构如下 varmutex Semaphore 1 Rmutex Semaphore 1 varcounter Integer 0 ParbeginWriter i Reader j Parend ProcedureWriter i Beginwhile true Begincaculate an data 计算一个数据P mutex Write the data 临界区V mutex End End 24 ProcessReader j BeginWhile true BeginP Rmutex Ifcounter 0thenP mutex counter counter 1 V Rmutex Read operation 临界区P Rmutex Ifcounter 1thenV mutex counter counter 1 V Rmutex End End 25 哲学家用餐问题 在该问题中设想有5位哲学家 他们共同坐在一张餐桌前用餐 用餐过后开始思考问题 他们的生活方式可描述为一个单调的循环 思考 饥饿 用餐 再思考 已知餐桌上摆的是面条 每个人必须左右手各拿到一把叉子才可以开始进餐 而餐桌上只有5把叉子 任两个哲学家之间有一把 见图所示 26 第i位哲学家的行为过程可描述为下面的形式 ProcessPhilosopher i BeginWhile true BeginThinking P mutex i 请求左叉子P mutex i 1 mod5 请求右叉子Eating 用餐过程V mutex i 释放左叉子V mutex i 1 mod5 释放右叉子End End 27 4 4 3信号量集机制 该机制可分为两类 AND型信号量集机制和一般型信号量集机制 一 AND型信号量集机制这种机制中 让P原语具有同时给多个信号量减1的功能 不过 它要先判断各个信号量是否都是 绿灯 若是 则将各个信号量的值减1 立即进入临界区 若其中至少有一个信号量是 红灯 进程就要让权等待 并将P原语的第1条指令作为断点地址 保存到该进程的PCB 信息保护区 中 等恢复运行时重执P原语 二 一般型信号量集机制我们为每一种临界资源设一个记录型信号量Si 并让Si的值域表示当前的可用资源数量 当一个进程根据需要 一次性地请求Si类型的资源di台时 可让它的P原语作Si Si di操作 28 3种信号量机制进行比较 整型信号量机制比较简单 适用面较窄记录型信号量机制较为灵活 可用于多种同步场合信号量集机制能够简化应用程序的设计 但系统的开销较大 29 4 5管程 这是一种具有面向对象程序设计思想的同步机制 它提供了与信号量机制相同的功能 管程 Monitor 概念是著名学者Hore于1974年提出的 并在很多系统中得到实现 诸如Pascal Java Modula 3等 管程是由局部数据结构 多个处理过程和一套初始化代码组成的模块 管程的特征为 1 管程内的数据结构只能被管程内的过程访问 任何外部访问都是不允许的 2 进程可通过调用管程的一个过程进入管程 3 任何时间只允许一个进程进入管程 其他要求进入管程的进程统统被阻塞到等待管程的队列上 30 下图是管程的一个结构模型 31 lP c 当遇到同步约束 就将进程阻塞在条件变量c关联的等待队列上 lV c 从条件变量c关联的等待队列上唤醒一个进程 让它恢复运行 若队列上没有进程在等待 就什么也不做 管程的语言结构可描述为下属形式 Type管程名 MonitorBegin数据结构定义 局部变量定义 条件变量定义 Porcedure过程名 形式参数 Begin 过程体End End 32 利用管程PC解决生产者 消费者问题的算法如下 ProcedureProducer BeginVarchar x While true BeginProduce an item in x PUT x End End ProcedureConsumer BeginVarchar x While true BeginGET x Consume the item in x EndEnd 33 4 6进程通信 4 1 1共享存储器系统这种通信需要在内存中开辟一个共享的存储空间 供进程之间进行数据传递 比如计算进程将所得的结果送入内存共享区的缓冲区环中 打印进程从中将结果取出来 就是一个利用共享存储器进行通信的例子 这种通信方式在UNIX Linux Windows及OS 2等系统中都有具体的实现 共享存储器系统中 共享的空间一般应当是需要互斥访问的临界资源 诸多进程为了避免丢失数据或重复取数 需要执行特定的同步协议 在利用共享存储器进行通信之前 信息的发送者和接收者都要将共享空间纳入到自己的虚地址空间中 让它们都能访问该区域 存储器管理模块将共享空间映射成实际的内存空间 34 1 创建或删除共享存储区 2 共享存储区的附接与断接 3 共享存储区状态查询 4 共享存储区管理共享存储器系统的特点 利用共享存储器系统进行通信的效率特别高 适用于通信速度要求特别高的场合 这种同步与互斥机制的实现一般要由程序员来承担 系统仅仅提供一个共享内存空间的管理机制 35 4 6 2管道通信 管道 Pipe 是可供进程共享的一种外存文件 主要用于连接一个写入进程和一个读出进程 以实现它们之间的数据通信 写入进程按字符流的形式将数据写入管道文件中 让读出进程从中获得数据 由于管道机制特别适用于大容量数据的通信 因此在许多操作系统中被采用 管道通信机制中的协调内容包括 1 互斥问题 2 同步问题 3 状态测试管道通信机制分为无名管道和有名管道 36 4 6 3消息传递 系统中的进程在交互传送数据时 涉及到对数据结构的互斥使用问题 为实施互斥 进程之间需要同步 提供这写功能的一个好方法是消息传递 还有一个优点是 消息传递可较容易地在单处理机系统 分布式系统 共享存储器的多处理机系统中实现 消息传递中的管理机制由操作系统提供 主要体现为以下两个原语 发送原语 send destination message 其中 destination为消息的目的地 接收进程名 该原语表示发送消息到进程destination 接收原语 receive source message 其中 source是消息发出地 发送进程名 该原语表示从进程source接收消息 37 一 实现同步的方法 在这种方式中要解决的关键问题仍然是同步问题 仅当一条消息从某个进程发送后 其他进程才可能接收到消息 那么 消息发送者通过send原语发出一条消息后 应当如何处理呢 有两种选择 要么将发送进程阻塞起来 直到消息被接收为止 再把它唤醒 要么不阻塞发送进程 同样地 消息接收者通过receive原语要接收一条消息时 如果能立即收到 可继续运行 如果消息尚未发出的话 也有两种选择 要么阻塞发送进程等待消息 要么不阻塞发送进程 放弃接收 这样一来 系统可选择的处理有以下几种 会合 renezvous 方式 宽松同步方式 不阻塞发送者 只阻塞接收者方式 38 二 直接通信和间接通信 在消息传递中 发送者需要明确消息发往哪里 接收者需要指明消息的来源 通常 按send和receive原语的实现方式可分为直接寻址和间接寻址两类 1 直接寻址 DirectAddressing 实现直接寻址的一个较为简单的方案是 让send原语明确指出接收者的进程号 receive原语明确指出发送者的进程号 系统根据这两个原语实现直接通信 这种一对一的通信 用来处理并发进程之间的合作是相当有效的 2 间接寻址 IndirectAddressing 在间接寻址方式中 消息并不直接从发送进程传到接收进程 而是要经过一个中间介质 临时保存消息的队列 通常称为 信箱 因此 两个通信进程的操作是 一个进程将消息发到信箱中 另一个从信箱中取消息 39 4 7死锁 死锁 DeadLock 是指系统中存在一组进程 其中每一个进程都在等待组内别的进程占有的资源 这样一来 该组进程都不能向前推进 陷入等待状态 系统死锁 是系统中n n 1 个进程因资源请求得不到满足 皆无法运行而出现的一种无限期等待现象 这是一种极其浪费的现象 它给系统带来的损失有时比出现某些硬件故障还要大 如果不给予有效地制止 这种状态将永远不能结束 40 4 7 1产生死锁的原因 当系统同时满足以下4个必要条件时 会产生死锁 1 互斥条件 进程请求的资源属于临界资源 每一瞬间只能由一个进程使用 若有多个进程同时请求使用同一个临界资源时 只能允许一个使用 其它进程等待 2 不剥夺条件 进程获得某资源后 便一直占有它 直到用完为止才可以释放 其它进程不可以剥夺某个进程已占有的资源 即使该进程目前无法运行 3 请求和保持条件 允许一个进程在保持已有资源不放弃的情况下 进一步请求新资源 当请求资源得不到满足而被阻塞时 也不会释放已占有的资源 4 环路条件 一组进程 P1 Pn 的占有资源情况与请求资源情况构成了一个环型链 比如P1等待P2的资源 P2等待P3的资源 Pn等待P1的资源 41 定义 资源分配图G 是一个有向图 N是结点集 E是边集 其中 N PR P为进程集 R为资源集 E E1E2 E1为资源占有边集 E2为资源请求边集 我们用圆圈表示进程pP 矩形表示资源rR 同时 用r p表示资源r被进程p占有 p r表示进程p请求资源r 那么两个进程P1和P2竞争资源R1和R2 及P1 P2和P3竞争R1 R2和R3的环路如图所示 42 4 7 2死锁预防 预防死锁的主要工作就是使系统一直保持在安全状态下运行 预防措施可从死锁的4个必要条件去考虑 1 资源静态分配方案2 资源可剥夺方案3 资源有序使用方案 43 4 7 3死锁避免 一 安全状态为了研究如何避免死锁 我们先来看一下系统的状态变化情况 比如 有两个进程P1和P2竞争资源R1和R2 如图 44 二 银行家算法 该算法需要建立多种数据结构予以支