中南大学数学院计算机操作系统第四章课件进程通信.ppt

第四章进程通信 1 2 4 1进程的同步与互斥 4 1 1同步与互斥的概念 两个或两个以上的进程要协作完成一个任务 它们之间就要互相配合 需要在某些动作之间进行同步 进程间另一种关系是互斥 这种关系一般发生在两个或两个以上的进程竞争某些同时只能被一个进程使用的资源的情况下 3 4 1 2临界段问题 在一段时间内只能允许一个进程访问的资源称为临界资源 如打印机 磁带机 光盘刻写机 绘图仪等进程执行的访问临界资源的程序段称为临界段或互斥段 临界资源与临界段 4 统计两个进程P1和P2对共享变量count访问计数 P1 P2 R1 count 0 R2 count 1 R1 R1 1R2 R2 1count R1 1 count R2 2 结果 count 2 设count初值 0 5 两个进程可能的相对执行次序 P1 R1 count 0 R1 R1 1 1 P2 R2 count 0 R2 R2 1 1 count R2 1 P1 count R1 1 虽然P1和P2进程各自都执行了对count加1的操作段 但结果count只增加1 因此 变量count就是临界资源 P1 P2访问count的两个程序段就是临界段 诸进程必须互斥地进入临界段 6 4 2进程间互斥控制方法 锁可以用于控制临界段的互斥执行 锁有两个状态 一个是打开状态 另一个是关闭状态 故锁可以用布尔变量表示 在C中 锁变量可以定义为char或int类型变量 设x为锁变量 则定义 x 0锁的打开状态 1锁的关闭状态 4 2 1锁的表示和操作 7 当进程希望进入临界段时 首先要测试锁的状态 如锁是打开的 表示无进程处于临界段 那么可以关闭该锁 并进入临界段 当该进程处于临界段时 其他试图进入临界段的进程由于在测试锁的状态时发现它处于关闭状态 就只能在临界段外等待 用锁变量控制临界段的执行 8 用锁操作控制进程对临界段的互斥执行 a LOCK x x 0 x 1 临界段 UNLOCK x 临界段 x 0 b 9 4 2 2锁的安全控制 锁的关闭操作LOCK包括测试和关闭两个操作步骤 这两个操作步骤涉及临界资源x 故这段程序也是临界段 假定锁是打开的 当一个进程P1在测试锁的状态后 还没来得及关闭它的一瞬间 发生了中断 中断返回时 系统可能调度另一个进程P2执行 P2执行时也对该锁的状态进行测试 发觉它处于打开状态 于是关闭该锁 并进入临界段 那么两个进程就同时处于一个临界段之中 10 1 测试并设置指令test set 有些计算机提供专门的锁操作指令test set 该指令首先测试锁变量的值 如为1 则重复执行本指令 如为0 则立即将锁变量的值置为1 由于test set是一条完整的指令 而在一条指令的执行中间是不会被中断的 故保证了锁的测试和关闭操作的连续性 11 2 交换指令 用8086指令实现锁操作 check MOVAL 1 置测试单元寄存器AL的值为1LOCKXCHGX AL 在本指令的执行时封锁总线 交换锁变量X与测试单元的值TESTAL AL 测试AL的值JNZcheck 如AL非0 即原锁处于关闭状态 跳转至check 重复测试过程临界段 锁变量X已置为1 12 3 开 关中断法 1 这种方法只能用于单CPU系统 2 如果临界段操作比较复杂 执行时间较长 那么长时间地关闭中断会降低系统对外部中断响应的速度 影响系统处理紧迫事件的能力 3 采用开 关中断的硬件锁方法禁止了其他无关的进程进入不同的临界段 这种做法显然伤害了很多的 无辜者 关中断临界区开中断 13 4 用硬件锁锁软件锁 用软件锁锁临界段 软件锁的LOCK操作包括测试和关闭两个操作步骤 它本身也是一种临界段 故可以用硬件锁 开 关中断保证软件锁操作的完整性 由于软件锁是一种程序长度最短的临界段 故用开 关中断的方法保证锁操作的完整性几乎不会影响到系统响应其他的中断请求 用软件锁保证临界段执行的独占性 不会影响到其他无关进程进入不同的临界段 这是一种安全而高效的锁 LOCK x 关中断开中断x 0 x 1开中断临界段图4 3复合锁的操作流程 14 4 3信号灯和semWait semSignal操作 信号灯定义成具有整型值 并能对其施加以下三种操作的变量 除了这三种操作之外的任何操作都不能测试和处理信号灯的值 1 初始化操作 信号灯能初始化为非负的值 2 semWait操作 能减小信号灯的值 如结果值为负 执行semWait操作的进程就被封锁 3 semSignal操作 能增加信号灯的值 如果结果值非正 那么原先因执行semWait操作而阻塞的进程被解除阻塞 15 semWait semSignal操作两个原语定义 typedefstructsemaphore intvalue Queuequeue Semaphore Semaphores 16 voidsemSignal s semaphores if s value 0 从等待队列queue中移出一进程 将该进程置入就绪队列中 voidsemWait s semaphores if s value 0 将进程置入等待队列queue中 封锁进程 转进程调度程序 17 4 4信号灯的应用 4 4 1利用信号灯实现互斥 18 信号灯的所有可能取值及意义为 s 1无进程进入临界段0有一进程进入临界段 1有一进程进入临界段 另一进程被阻塞如有n个并发进程涉及一个临界段 则上式最后一行s的取值为i n 1 i 1 表示当前有 i 个进程被阻塞 两个并发进程涉及一个临界段 19 4 4 2阻塞 唤醒协议 置信号灯s的初值为0PaPb计算func1 计算func2 L1 semWait s 将计算结果存入缓冲区获得Pb的计算结果L2 semSignal s 计算乘积 图4 5阻塞 唤醒协议的实现 20 从图中可以看出 当进程a执行到L1点时 如进程b还未执行到L2点 也即func2函数的计算还未完成 进程a就要同步等待进程b 而进程b则不必同步等待进程a 所以说这种同步是非对称的 或可以称为 半同步 21 4 4 3两个进程间的同步 1 一个全同步的例子 设有两个进程Pa和Pb 进程Pa每次执行一个计算 并将结果存入一个缓冲区 进程Pb则从缓冲区中取出结果 并将结果打印出来 22 为了实现计算进程和打印进程之间的相互同步 就需要设置2个信号量S1和S2 在semWait semSignal操作之前两个信号量的含义为 S1表示缓冲区中是否已存入进程Pa的计算结果 也即通知进程Pb是否可取出缓冲区中的信息并送往打印机 S1值为 0 Pa没存入新的计算结果1 Pa已存入新的计算结果 23 S2 表示缓冲区中的结果是否已被进程Pb取去 也即通知进程Pa是否可将新的计算结果再存入缓冲区 S2的值为 0 Pb没取走缓冲区中的数据 缓冲区满1 Pb已取走缓冲区中的数据 缓冲区空 24 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 25 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 26 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 3 0 27 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 3 0 4 28 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 3 0 4 5 0 29 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 6 3 0 4 5 0 30 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 6 3 0 7 1 4 5 0 31 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 6 3 0 7 1 4 5 0 8 32 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 6 3 0 7 1 4 5 0 8 9 0 33 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 2 6 3 0 7 1 4 5 0 8 9 0 10 34 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 11 1 2 6 3 0 7 1 4 5 0 8 9 0 10 35 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 11 1 2 6 3 0 7 1 4 12 5 0 8 9 0 10 36 信号灯的初值可设置为 S1为0 缓冲区还未存入数据S2为1 缓冲空闲 相当于Pb已取走数据 计算进程 P a 打印进程 P b computing semWait s1 semWait s2 get result put result semSignal s2 semSignal s1 printing 图 4 6 两个进程之间的全同步 1 1 11 1 2 6 3 0 7 1 4 12 5 0 8 9 0 10 37 2 互斥和同步对信号灯操作方法的差异 互斥和同步都是通过对信号灯的semWait semSignal操作来实现的 但这两种控制机制对信号灯的操作策略是不同的 互斥实现是不同的进程对同一信号灯进行semWait semSignal操作 一个进程在成功地对信号灯执行了semWait操作后进入临界段 并在退出临界段后 由该进程本身对这信号灯执行semSignal操作 表示没有进程处于临界段 可让其他进程进入 同步的实现由一个进程Pa对一个信号灯进行semWait操作后 只能由另一个进程Pb对同一个信号灯进行semSignal操作 使Pa能继续前进 在这种情况下 进程Pa要同步等待Pb 如进程Pb也要同步等待Pa 则要设置另一个信号灯 38 4 4 4生产者和消费者问题 生产者和消费者问题是通过有限的缓冲区 仓库 将一群生产者P1 P2 Pk和一群消费者C1 C2 Cm联系起来 可设信号量buffers的初值为n 表示空闲的缓冲区数目 products的初值为0 表示已存入缓冲区的产品数目 生产者和消费者问题的一般过程为 生产者在执行semWait buffers 之后 只要buffers 0 还有空闲的缓冲区 就可将产品送入 消费者在执行semWait products 后 只要products 0 产品还未取完 就可以从缓冲区中取走产品 并消费之 否则 生产者或消费者进程就被阻塞 39 producers customers while while producenextproduct semWait products semWait buffers getproductfrombuffers Putproductintobuffers semSignal buffers semSignal products consumeproduct 40 producers customers while while producenextproduct semWait products semWait buffers semWait mutex semWait mutex getproductfrombuffers Putproductintobuffers semSignal mutex semSignal mutex semSignal buffers semSignal products consumeproduct 请仔细推敲semWait semSignal操作的次序 这些操作的次序安排得不合理 就有可能发生 死锁 41 4 4 5读者 写者问题 常会有若干个并发进程对数据对象进行读写的情况 有些进程只要求读数据对象 有些进程则要求修改数据对象 若干个读者可以同时访问数据对象 不需要互斥也不会产生任何问题 但一个写者不能与任何的读者或者写者同时访问数据对象 否则就可能破坏数据对象的完整性 正确性与一致性 可将所有的读进程看成是一类的 但写进程必须和任何其他的写进程和读进程类互斥 42 当有读进程正在访问数据对象时 读进程的个数与互斥要求没有关系 只有当第一个读进程需要对数据对象访问时 才需要执行semWait操作 以判断是否有写进程正在更新数据对象 只有当最后一个读进程退出访问数据对象的临界段时 才需要执行semSignal操作 以便拆除 路障 让一个写进程进入 需要设置一个跟踪正在临界段访问数据对象的读进程个数的全局共享变量count 由于该计数器也是一个临界资源 所以诸进程对它的访问也应当互斥地进行 为此 还要设置另外一个互斥信号灯 43 解决读者 写者问题的算法 信号灯初值 mutex为1wrt为1计数器变量 intcount 0writors while semWait wrt writeinformationsemSignal wrt 44 readers while semWait mutex if count 1 semWait wrt semSignal mutex Readinformation semWait mutex if count 0 semSignal wrt semSignal mutex 45 4 5进程间的数据通信 4 5 1消息通信 消息通信的基本思想是由系统的消息通信机构统一管理一组空闲的消息缓冲区 一个进程要向另一个进程发送消息 先要向系统申请一个缓冲区 填写了消息正文和其他有关消息的特征 控制信息后 通过消息通信机构将该消息送到接收其他消息队列中 接收进程在一个适当时机从消息队列中移出一个消息 读取所有的信息后 再释放消息缓冲区 一个消息缓冲区的数据结构中除了要包括消息的正文外 一般还要包括其他有关的控制信息 46 send pid 发送进程标识type 消息类型size 消息长度next ptr 下一个消息的指针text 消息正文为了支持消息通信 在进程控制PCB中还要增设有关管理消息的成员 如 hd ptr 进程已收到消息的队列首指针mutex 对消息队列进行操作的互斥信号灯ssm 接收进程和发送进程之间的同步信号灯 其值表示接收进程消息队列中的消息数 47 发送进程在发送消息之前 先要在进程自己的内存空间中开辟一个发送缓冲区 将消息正文及有关控制信息填入其中 再调用发送消息的系统调用msgsnd sm ptr 其中参数sm ptr指向进程的发送缓冲区始址 接收进程在接收消息之前 也先要在进程自己的内存空间中开辟一个接收缓冲区 再调用接收消息的系统调用msgrcv rm ptr 其中参数rm ptr指向接收缓冲区始址 msgsnd和msgrcv系统调用 48 4 5 2共享存储区 共享存储区机制可以把内存中的一个区域连入多个进程的虚地址空间 当一个进程对该地址空间写入数据后 另一个进程就可以从自己所连入的虚地址空间直接读出共享存储区中的数据 就如同进程存取自己的私有数据一样方便 进程要求分配一个共享存储区时 核心先要按进程提供的关键字值查找系统的共享存储区段表 如已存在指定关键字的共享段 则说明该共享段已先由其他进程创建 只要权限允许 可简单地返回该表项的描述符 49 共享存储区 续 如未找到指定关键字的表项 系统就根据进程对共享存储区的大小及存取控制权的要求 分配一个空闲的页表区和空闲的内存块 在共享存储区段表中填入共享段的关键字 大小 共享段的页表始址及存取控制权等信息 并返回该表项的描述符 接下来进程就可以通过该共享存储区的描述字 将共享存储段映射到进程的虚地址空间 50 4 5 3管道通信 管道是一种信息流缓冲机构 它用于连接发送进程和接收进程 以实现它们之间的数据通信 管道以先入先出 FIFO 的方式组织数据的传输 在发送进程和接收进程之间能传递任意大的信息 但在实现时所开的缓冲区太小是有限的 故当管道写满时 发送进程就被阻塞 只有当接收进程从管道中读出一部或全部信息后 发送进程才能继续向管道写信息 反之也一样 当接收进程读空管道时 就要等待发送进程继续将信息写入管道 在UNIX中 管道是以文件为基础 再适当考虑其特殊要求而实现的通信机构 51 4 6软中断和信号机构 4 6 1信号的产生与类型 1 信号的概念 UNIX提供了一组软中断信号 用于模拟硬件中断 但它们的实现机制是不同的 信号是一取值为1 19 MAX SIGS 的某个整数 可以在进程之间传送 用于通知进程发生了某种异常事件 需要执行事先安排好的动作 进程在运行中的某几个时机要主动通过信号机制检查是否有信号到达 如有 便中断正在执行的程序 转入对应的事件处理程序 处理完毕 再返回断点执行原先的程序 信号处理过程与硬件中断处理很相似 故称为 软中断 52 2 信号的产生 在UNIX中 主要在以下几种情况下向进程发送软中断信号 1 在用户态运行时产生了各种软 硬件故障 2 用户通过键盘按键向与该终端有关的进程发信号3 进程之间通过系统调用kill传送信号 信号机构将发给进程的信号存放在该进程proc结构的p sig项 进程收到信号后并不立即进行处理 只有当进程从核心态即将返回到用户态时 即系统调用 陷入或中断返回时才检查p sig项 并处理与信号对应的事件 如一个进程处于较低优先级的睡眠状态 那么系统将唤醒该进程 使其转入就绪状态 并在被调度程序选中 转入执行状态时执行信号处理程序 53 3 信号的类型 0没有收到信号1SIGHUP终止进程终端线挂断2SIGINT终止进程在键盘上击 DELETE 键7SIGFPE产生core浮点溢出9SIGKILL终止进程无条件终止进程11SIGSEGV产生core段违例14SIGALARM终止进程闹钟15SIGTERM终止进程软件终止16SIGUSR1终止进程用户自定义17SIGUSR2终止进程用户自定义19SIGPWR终止进程电源故障 54 4 6 2信号的处理方式及设置 1 信号的处理方式 每一个进程的user结构中有一个长度为NSIG 20 的数组signal NSIG 以信号类型作为该数组的下标索引 元素的值决定了对应信号的处理方式 信号的处理方式有三类 1 若数组元素值为0 则执行信号机构定义的缺省动作 2 若数组元素值为1 或奇数 则忽略该信号 不执行任何动作 3 若数组元素值为偶数 函数入口地址 则作为对应信号处理程序的指针 55 2 信号处理方式的设置 一个进程在创建时 继承了父进程所有的信号处理方式 也即其signal NSIG 各元素的值与父进程完全相同 但此后除了SIGKIL外 信号表中定义的信号处理方式都可以用系统调用signal sig func 设置或修改 设置的方法是 intsig intfunc oldptr oldptr signal sig func 其中sig为信号类型 取值范围为1 19 但不包括9 SIGKIL func为新的信号处理函数 oldptr为函数指针 用于保存系统调用signal返回的信号sig原先处理函数入口地址 以便有必要时可恢复原先的信号处理方式 56 newfunc 0 a oldptr proc u u signal 进程Pa的图像 图4 9信号处理方式的设置 57 4 6 3信号的传送 利用信号实施进程间通信的主要方式是使用系统调用kill pid sig 其功能是将信号sig传送给由参数pid限定的进程 当 pid为正值时 对应于一个有效的进程标识数 该信号就发送给这个唯一的进程 pid为0时 将信号发送给受同一终端控制的所有进程 pid为 1时 将信号发送给与发送进程用户标识数相同的所有进程 pid 1时 将信号发送给组标识数为pid的绝对值的所有进程 下面举一个信号机构方法的例子 58 include includemain intstatus pid tpid voidfunc signal SIGUSR1 func 1 预置信号处理程序 if pid fork 2printf Parent willsendsignal n 4kill pid SIGUSR1 5 发送信号 wait status 6 等待子进程停止 printf status d Parentfinish n status 10 else sleep 10 3 等待接受信号 printf Child signalisreceived n 8exit 0 9 59 voidfunc printf Itissignalprocessingfunction n 7 在程序的开始部分用系统调用设置信号16的处理方式为执行func程序 在父进程用fork创建子进程后 子进程继承了对信号的处理方式 父进程向子进程发送信号后 如子进程处于低优先权睡眠 则将其唤醒 子进程被唤醒后 检查是否收到信号 发现已收到信号 就执行该信号 SIGUSR1 所对应的处理程序func 执行完毕后返回 继续执行余下程序段 60 Solaris的进程通信机制 SPARC处理机为互斥原语实现了有原子性test and set语义的内存访问指令 如cas compareandswap 比较和交换 指令 如果第一个寄存器与内存单元的内容相同 则交换内存单元和第二个寄存器的内容 锁以几种不同的形式出现 Solaris内核中最常用的是互斥锁 它可以实现对数据的互斥读写访问 此外还有读 写锁 它适用于在同一时刻对同一数据可以有多个读操作 但只能有一个写操作的情况 在内核的一些部分 如果获取最佳性能是要追求的首要目标 为了提高速度 许多锁代码用汇编语言实现 而不是C语言 61 Solaris支持SystemV的三种IPC机制 共享内存 信号量和消息队列 还支持基于套接字的进程间通信机制 同时 Solaris引入了自己独特的IPC机制 Solaris门 Solaris门是一种快速的进程间过程调用 这种类似于远程过程调用的机制允许我们快速地调用其他进程中的方法 一个进程可以通过创建门而成为门服务器 门是一个函数 在服务器中以线程的形式存在 其他的客户端进程可以调用门 Solaris门 62 Solaris门服务器会在线程池中创建一个内核线程以等待客户端的调用 只要门线程池中还有空闲的线程 客户端就能马上得到服务 这就使得门函数的调用非常快速 服务器进程成功创建门时 返回一个门的描述符 门服务器进程通过创建一个门 door create 来使得该进程中的一个函数可以被客户端的进程所使用 内核中将门实现为一个伪文件系统doorfs 进程通过门描述符来引用门 门描述符在形式和功能上都与文件描述符相似 服务器必须将创建的门和一个文件系统名字空间的文伴描述符相关联 服务器端是通过调用fattach 来将一个文件系统路径名和门文件描述符相关联的 一旦关联充成 客户端就可以对该路径名进行打开操作 并且在door call 使用打开操作返回的文件捕述符来得到一个门的描述符 客户端通过门描述符来找到一个门 Solaris门 63 Solaris中的信号处理 Solaris中的信号处理是进程级别的 但每个线程可以有自己的信号屏蔽掩码 线程可以独立于同一进程中执行的其他线程来选择自己要屏蔽的信号 因而在进程执行的不同时刻可以有不同的线程来接收不同的信号 接口pthread sigmask 用来建立每个线程的信号屏蔽掩码 进程中的所有线程共享所有信号的处理及处理例程 那么具有默认处理的SIGINT信号 作为例子 的产生将会使整个进程退出 作为异常的结果产生的同步信号 SIGFPE SIGILL等 将被发送到产生异常的线程本身 异步信号是所有没有被定义为异常的其他信号 它们将被传递到系统找到的第一个不屏蔽该信号的线程 信号在数据结构中表示为二进制位 例如设置第16位 SIGURS1 这实际上是位15 位的编号是从0开始的 64 4 7死锁 4 7 1产生死锁的原因 图4 10过河的相持 65 当两个进程各占了对方所要的一个资源 就会形成死锁 进程B等待资源R1 资源R1 进程B 进程A 资源R2 进程A占用资源R1 进程A等待资源R2 进程B占用资源R2 图4 11两个进程的死锁 66 系统资源可分为两类 一类是可重复使用的永久性资源 另一类是会被消耗的临时性资源 可重复用的资源在使用后不会减少资源 进程在释放了可重用资源后 该资源又可被其他进程再次使用 可重用的资源有处理机 主存 暂存 I O通道 打印机以及文件 数据库等 可重用的资源又可分为可剥夺的资源和不可剥夺的资源 最典型的可剥夺的资源是处理机 最普通的不可剥夺的资源是打印机 当系统把这类资源分配给进程后 只能在使用完毕后由进程自愿释放 系统不能强行收回 涉及到可重用资源的死锁例子是 一个进程占用了打印机 又要申请磁带机 另一个进程占用了磁带机 又要申请打印机 这样每个进程都占用并保持了一个资源 并等待对方所占用的资源时就发生了死锁 67 4 7 2产生死锁的条件 同时具备下列三个静态的必要条件时 才有可能产生死锁 1 互斥执行每次只能允许一个进程占有和使用一个资源 其他申请该资源的进程被阻塞 2 保持并等待当进程等待分配给它新的资源时 保持占有已分配的资源 3 不可剥夺不能强迫移去进程占有的未使用完的资源 上述这三个条件是产生死锁的必要条件 但即使存在全部这三个条件也不一定会发生死锁 要产生死锁必须存在第四个动态条件 4 循环等待存在一个闭合的进程 资源链 以致每一个进程至少占有链中下一个进程所需要的一个资源 68 4 7 3死锁的预防 1 互斥执行一般说 第一个条件是不能排除的 如果存取一个资源需要互斥执行 那么操作系统就要支持互斥执行 某些资源 例如文件 可以允许多个用户同时读 但对写只能互斥地进行 就是在这个情况 如果一个以上的进程需要进行写操作 就可能发生死锁 2 保持和等待保持和等待条件是能预防的 只要进程一次申请它所需要的所有的资源 在所有的需要同时满足以前 阻塞自己 69 有几种方法可预防这个条件 一个方法是 如占有某些资源的进程不能获得进一步的资源 该进程必须释放原先所占有的资源 如果需要 以后再申请这些资源 另外的方法是 如果一个进程需要申请当前正被其他进程占用的资源 操作系统就要求后者释放它所占用的这类资源 这种预防死锁的方法只能用在后申请资源的进程优先级较高的情况下 只有当资源的状态容易保存和便于以后恢复的情况下 这种方法才是实际可行的 处理机就是这类资源的例子 如剥夺像打印机那样的资源 就会使输出变得杂乱无章 毫无意义 但借助spooling技术可将独享设备改为虚拟的共享设备 就能破坏本条件 预防死锁 3 不可剥夺 70 4 循环等待采用有序资源使用法可以防止循环等待条件 如果一个进程已经分配了类型R的资源 那么以后它只能申请在资源顺序表中排在R后面的资源类型 1 2 3 4 5 数 模 转 换 器 磁 带 机 光 刻 机 绘 图 仪 71 五个哲学家吃通心面 P1 思考semWait f1 取f1semWait f2 取f2吃通心面放下f1 f2semSignal f1 semSignal f2 p1 f1 f2 p2 f3 f4 f5 p3 p4 p5 P5 思考semWait f5 取f5semWait f1 取f1吃通心面放下f5 f1semSignal f5 semSignal f1 72 五个哲学家吃通心面 P1 思考semWait f1 取f1semWait f2 取f2吃通心面放下f1 f2semSignal f1 semSignal f2 p1 f1 f2 p2 f3 f4 f5 p3 p4 p5 P5 思考semWait f1 取f5semWait f5 取f1吃通心面放下f5 f1semSignal f5 semSignal f1 73 4 7 4死锁的避免 死锁避免的方法允许三个死锁的必要条件都存在 但要动态地进行审慎的判断 以保证运行不会到达死锁这一点上 避免死锁主要有以下两个判断和处理时机 1 进程启动时判断如果对资源的要求会导致死锁 就不启动有关进程 这种方法仅仅在当前所有进程对资源的最大请求加上启动进程对资源的请求都满足的情况下 才能启动新进程 故这种避免死锁的策略不会是最优的 因为它假定的是最坏情况 即所有进程都同时需要最大数量的资源 2 资源分配时判断如果对资源的分配会导致死锁 就暂不允许进一步为进程分配资源 74 分配资源时 申请者要把同类资源的最大需求量告诉系统 如系统现存的可用资源数能满足申请者剩余需求量时 就满足当前的部分或全部申请 否则就推迟分配 这样至少保证有一个申请者能得到所需的全部资源 可执行到结束 然后释放资源供别的申请者使用 如果系统保证申请者在有限的时间内能获得所需的全部资源 则称系统处于安全状态 否则称系统处于不安全状态 并有可能引起死锁 银行家算法是在能确保系统处于安全状态时才把资源分配给申请者 银行家算法 75 例 有8个资源供三个进程共享 它们的最大需求数分别为6 4 7 在某一时刻 资源的分配情况如下所示 最大需求当前占有还要申请P0624P1422P2716系统剩余数3这时 系统处于安全状态 因为剩余的资源可以先供进程P1使用 P1运行结束后将释放所占全部资源 这样系统剩余资源数变为5 又可保证P0的全部申请得到满足 等到P0归还所占资源后 就可满足P2的申请 如此系统存在着一个安全的资源分配序列 76 但在上述的状态中 如果P0要申请2个 而不是1个 资源 系统就不能立即分配给它 而要推迟到一个适当的时机再实施分配过程 否则系统资源的分配情况将变为 最大需求当前占有还要申请P0642P1422P2716系统剩余数1这种状态是不安全的 因为剩余的资源数已不能满足任何一个进程还要申请的资源数 如此就可能形成死锁 77 4 7 5死锁的检测 死锁的预防策略是非常保守的 它是靠限制对资源的存取及进程的并发执行程度来实施的 与其相反 死锁检测策略不减少对资源的存取或限制进程的并发运行 使用死锁检测 只要可能 就将所申请的资源分配给进程 操作系统定期地执行检查算法 以判断是否存在条件4的循环等待链 78 资源分配表 资源等待表 状态图和状态表 79 4 7 6死锁的解除 下面列举了一些解除死锁的方法 强迫撤销所有的死锁进程 将每一个死锁进程退回到一些以前定义的 检查站 再启动进程 这需要系统支持进程的回退和重启动机制 逐个撤销死锁进程 直至死锁不存在 终止死锁进程的次序应当基于最小代价的标准 每终止一个进程后就调用死锁检测算法 以判定死锁是否还存在 相继地剥夺进程所占的资源 直至死锁不再存在 同样 剥夺资源的次序应基于成本方面的考虑 被剥夺资源的进程必需回退到获得该资源之前的某个执行点上 80 4 9Solaris的进程通信机制 SPARC处理机为互斥原语实现了有原子性test and set语义的内存访问指令 如cas compareandswap 比较和交换 指令 如果第一个寄存器与内存单元的内容相同 则交换内存单元和第二个寄存器的内容 锁以几种不同的形式出现 Solaris内核中最常用的是互斥锁 它可以实现对数据的互斥读写访问 此外还有读 写锁 它适用于在同一时刻对同一数据可以有多个读操作 但只能有一个写操作的情况 在内核的一些部分 如果获取最佳性能是要追求的首要目标 为了提高速度 许多锁代码用汇编语言实现 而不是C语言 81 4 9 2Solaris中的信号处理 Solaris中的信号处理是进程级别的 但每个线程可以有自己的信号屏蔽掩码 线程可以独立于同一进程中执行的其他线程来选择自己要屏蔽的信号 因而在进程执行的不同时刻可以有不同的线程来接收不同的信号 接口pthread sigmask 用来建立每个线程的信号屏蔽掩码 进程中的所有线程共享所有信号的处理及处理例程 那么具有默认处理的SIGINT信号 作为例子 的产生将会使整个进程退出 作为异常的结果产生的同步信号 SIGFPE SIGILL等 将被发送到产生异常的线程本身 异步信号是所有没有被定义为异常的其他信号 它们将被传递到系统找到的第一个不屏蔽该信号的线程 信号在数据结构中表示为二进制位 例如设置第16位 SIGURS1 这实际上是位15 位的编号是从0开始的 82 Solaris支持SystemV的三种IPC机制 共享内存 信号量和消息队列 还支持基于套接字的进程间通信机制 同时 Solaris引入了自己独特的IPC机制 Solaris门 Solaris门是一种快速的进程间过程调用 这种类似于远程过程调用的机制允许我们快速地调用其他进程中的方法 一个进程可以通过创建门而成为门服务器 门是一个函数 在服务器中以线程的形式存在 其他的客户端进程可以调用门 4 9 4Solaris门 83 Solaris门服务器会在线程池中创建一个内核线程以等待客户端的调用 只要门线程池中还有空闲的线程 客户端就能马上得到服务 这就使得门函数的调用非常快速 服务器进程成功创建门时 返回一个门的描述符 门服务器进程通过创建一个门 door create 来使得该进程中的一个函数可以被客户端的进程所使用 内核中将门实现为一个伪文件系统doorfs 进程通过门描述符来引用门 门描述符在形式和功能上都与文件描述符相似 服务器必须将创建的门和一个文件系统名字空间的文伴描述符相关联 服务器端是通过调用fattach 来将一个文件系统路径名和门文件描述符相关联的 一旦关联充成 客户端就可以对该路径名进行打开操作 并且在door call 使用打开操作返回的文件捕述符来得到一个门的描述符 客户端通过门描述符来找到一个门 Solaris门 84 思考题 为什么Windows和Unix等实际操作系统在设计中不采取课程教学中讲过的各种死锁解决方法 而任系统发生死锁呢 85 谢谢各位