自考操作系统原理第七章进程同步与进程通信.ppt

进程同步与进程通信 进程的顺序性 进程的顺序性是指进程在顺序处理器上的执行是严格按序的 即按照程序规定的操作顺序 只有在前一个操作结束后才能开始后继操作 当一个进程独占处理器时 它具有两个特性 封闭性可再现性 进程的并发性 每一个进程具有顺序性 但是在多道程序设计系统中 多个进程要竞争 轮流占用处理器 有两个进程A和B 它们各自顺序执行时的操作序列如下 进程A a1 a2 a3 am进程B b1 b2 b3 bm在多道程序设计系统中 处理器可能执行的操作序列a1 b1 a2 b2 a3 b3 a1 a2 b1 a3 b2 b3 进程的并发性 在一个进程的工作没有完成之前 另一个进程就可以开始工作 这些进程就称为可同时执行的 或者称它们具有并发性 并且把可同时执行的进程称为并发进程 进程的并发性 如果一个进程的执行不影响另一个进程的执行结果 也不依赖一个进程的进展情况 即它们是各自独立的 则称这些进程相互之间是无关的 如果一个进程的执行要依赖其他进程的进展状况 或者可能会影响其他进程的执行结果 则说这些进程是有交互的 与时间有关的错误 对于有交互的并发进程来说 并发会破坏 封闭性 和 可再现性 例1 车辆自动计数系统 processObserverbeginL1 observealorry count count 1 gotoL1 end processReporterbeginprintcount count 0 end 系统功能 统计每小时的卡车流量观察者进程 Observer 观察到一辆卡车 计数器 1报告者进程 Reporter 每隔1小时 将计数值输出 计数器清零 例2 航班售票系统 processPi i 1 2 beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ak代表某天某次航班的剩余票数 Pi代表售票处理进程 Ri是每个售票进程的私有变量 各个售票处进程的工作如左边代码所示 processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ri 5 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ri 5 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ri 5 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ri 5 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ri 4 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ak 4 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ri 4 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end Ak 4 假设某时刻Ak为5 A B两个人同时在2号3号窗口买票 processP3beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end processP2beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end 假设某时刻Ak为1 两个窗口同时卖票 可能出现什么情况 与时间有关的错误 由于进程交替修改了共享变量造成结果可能不正确 造成不正确的因素与进程占据处理器的时间 执行速度以及外界的影响 卡车 这些因素都与时间有关 所以称为与时间有关的错误 临界区 有交互的并发进程执行时出现与时间有关的错误 其根本原因是对共享资源 变量 的使用不受限 为了使并发进程能正确地执行 必须对共享变量的使用加以限制 processObserverbeginL1 observealorry count count 1 gotoL1 end 临界区 processReporterbeginprintcount count 0 end 把并发进程中与共享变量有关的程序段称为临界区 涉及相同共享变量的临界区称为相关临界区 临界区 processPi i 1 2 beginRi Ak ifRi 1thenbeginRi Ri 1 Ak Ri输出一张票 end else输出 票已售完 end 如果能保证一个进程在临界区执行时 不让另一个进程进入相关的临界区执行 即各进程对共享变量的访问是互斥的 就不会造成与时间有关的错误 临界区 当无进程在临界区时 若有进程要进入 则允许一个进程进入临界区当有进程在临界区执行时 其他试图进入临界区的进程必须等待当有一个进程离开临界区 若有等待进入临界区的进程 则允许一个进程进入它的临界区 信号量机制 Semaphores 1965年 荷兰的E W Dijkstra 狄克斯特拉 提出了信号量同步机制 用于进程同步广泛应用于存在临界资源和临界区控制的场合 信号量的概念 信号量S是一个整数 S 0可供并发进程使用的资源实体数 0绝对值表示等待使用资源的进程数 PV操作 对信号量的操作只能由P V操作来进行 即 信号量数值的改变只能由P V操作完成PV操作由P操作和V操作组成 也称P操作原语和V操作原语 P操作 P S 将信号量S减1 若结果小于0 则把调用P S 的进程设置成等待信号量S的状态ProcedureP VarS Semaphore beginS S 1 ifS 0thenW s end P W s 表示把调用P S 的进程设置成等待信号量S的状态 V S 将信号量S加1 若不大于0 小于等于0 则释放一个等待信号量S的进程 ProcedureV VarS Semaphore beginS S 1 ifS 0thenR s end V V操作 R s 表示释放一个等待信号量S的进程 进程的互斥 进程的互斥是指有若干进程都要使用某一共享资源时 任何时刻最多只允许一个进程去使用该资源 其他要使用的进程必须等待 直到该资源的占用者释放了该资源 beginS semaphore S 1 cobegin processPi i 1 2 3 beginP S 临界区Ci 访问共享资源的代码 V S end coend end 假设有n个进程P1 P2 P3 Pn共享某一资源 任意时刻只允许一个进程访问该资源 它们各自的临界区分别为C1 C2 Cn begincount integer count 0 S semaphore S 1 cobegin processObserverbeginL1 observealorry P S count count 1 V S gotoL1 end processReporterbeginP S printcount count 0 V S end coend end beginS semaphore S 1 cobegin processPi i 1 2 3 beginP S Ri Ak ifRi 1thenbeginRi Ri 1 Ak RiV S 输出一张票 end elsebeginV S 输出 票已售完 end coend end 读者 写者问题 计算机中 把可供多个进程使用的文件称为共享文件 想读文件的进程称为读进程 写文件的进程称为写进程 不允许多个进程同时使用共享文件 beginS semaphore S 1 cobeginprocessReaderi i 1 2 3 beginP S readfileF V S end processWriterj j 1 2 3 beginP S writefileF V S end coend end P22612 有4个并发执行的进程A B C D 它们在执行时都要读共享文件F 限定 不允许进程A和进程B同时读文件F 不允许进程C和进程D同时读文件F 写出用PV操作管理时四个进程的程序 beginS1 S2 semaphore S1 1 S2 1 cobeginprocessAbeginP S1 readfileF V S1 end processBbeginP S1 readfileF V S1 end coend end processDbeginP S2 readfileF V S2 end processCbeginP S2 readfileF V S2 end 某系统允许最多10个进程同时读文件F 当同时读文件F的进程不满10个时 欲读该文件的其他进程可立即读 当已有10个进程在读文件F时其他欲读文件F的进程必须等待 直至有进程读完后退出方可去读 写出进程并发执行时的程序 beginS semaphore S 10 cobeginprocessReaderi i 1 2 3 beginP S readfileF V s end coend end 允许多个进程同时使用共享文件 要求 1 多个进程可以同时读文件F 2 任何一个进程在对文件F进行写时 不允许其他进程读或写 3 有进程在读文件F时 不允许任何进程去写PV操作的实现思路 processWriteri i 1 2 3 beginP S writefileF V S end processReaderi i 1 2 3 beginif是第一个读进程thenP S readfileF if是最后一个完成的读进程thenV S end beginS semaphore S 1 rc integer rc 0 cobegin processReaderi i 1 2 3 beginrc rc 1 ifrc 1thenP S readfileF rc rc 1 ifrc 0thenV S end coend end processwriterj j 1 2 beginP S writefileF V S end beginS mutex semaphore S 1 mutex 1 rc integer rc 0 cobegin processReaderi i 1 2 3 beginP mutex rc rc 1 ifrc 1thenP S V mutex readfileF P mutex rc rc 1 ifrc 0thenV S V mutex end coend End processwriterj j 1 2 3 beginP S writefileF V S end 进程的同步 假设缓冲区容量为1一个生产者进程 将数据存在缓冲区中 一个消费者进程 从缓冲区中取数据 要求两者同步 即缓冲区空才可以存 缓冲区满才可以取 用PV操作实现进程的同步 beginSP SG semaphore SP 1 SG 0 Buffer integer cobegin processproducerbeginL1 produceaproductP SP buffer product V SG gotoL1 end coend End processconsumerbeginL2 P SG takeaproduct V SP Consume gotoL2 end 桌上只有一个盘子 一个盘子一次只能放一个苹果 爸爸向盘子里放苹果 儿子从盘子里拿苹果 用PV操作实现同步 beginS1 S2 semaphore S1 1 S2 0 cobegin process爸爸beginL1 P S1 放苹果V S2 gotoL1 end process儿子beginL2 P S2 拿苹果V S1 gotoL2 end coend end 用PV操作实现售票员和司机的同步 假设初始状态为车在始发站 要求售票员进程先开始执行 process售票员开车门关车门售票 process司机启动车辆正常行车到站停车 beginS1 S2 semaphore S1能否开门 S2能否开车S1 1 S2 0 cobegin process司机beginL1 P S2 启动车辆正常行驶到站停车V S1 gotoL1 end coend End process售票员beginL2 P S1 开门关门V S2 售票gotoL2 end P2257 有三个并发进程R M P 它们共享一个只能存放一个记录的缓冲区 R负责从输入设备读信息 每次读一个记录 存在缓冲区中 M对缓冲区中的记录加工 P把加工后的记录打印输出 记录经加工并输出后 缓冲区才能存放下一个记录 写出它们并发执行时的程序 假设有三个进程R W1 W2共享一个缓冲区B 又设B中每次只能放一个数 要求 缓冲区中无数时 R可以从设备读数存到缓冲若存到缓冲中的数是奇数 允许W1将其取出打印若存到缓冲中的数是偶数 允许W2将其取出打印R必须等缓冲区空才能放 W1 W2不能从空缓冲区中取数 beginSP SG1 SG2 semaphore SP 1 SG1 0 SG2 0 Buffer integer cobegin processRbeginL1 读入一个数numberP SP buffer number ifbuffermod20thenV SG1 elsethenV SG2 gotoL1 end coend end processW1beginL2 P SG1 y buffer V SP printy gotoL2 end processW2beginL3 P SG2 z buffer V SP printz gotoL3 end 多缓冲区的进程同步 假设缓冲区容量为n 或者假设有n个缓冲区 一个生产者进程 一个消费者进程 要求消费者进程的处理顺序与生产者进程的输入的完全一样 beginbuffer array 0 n 1 ofintegerk t integer k 0 t 0 SP SG semaphore SP n SG 0 cobegin processproducerbeginL1 produceaproductP SP buffer k product k k 1 modn V SG gotoL1 end coend end processconsumerbeginL2 P SG takeaproductfrombuffer t t t 1 modn V SP Consume gotoL2 end 同步与互斥的混合问题 某工厂有一个可以存放设备的仓库 总共可以存放8台设备 生产部门生产的每一台设备都必须入库 销售部门可以从仓库中提出设备供应客户 设备出 入库需要借助运输工具 现只有一套运输工具 每次只能运一台设备请设计一套能够协调工作的自动调度系统 beginS SP SG semaphore S 1 SP 8 SG 0cobegin process生产beginL1 生产一台设备P SP P S 运送到仓库 V S V SG gotoL1 end coend end process销售beginL1 P SG P S 从仓库运出 V S V SP gotoL1 end m个生产者和r个消费者怎样共享容量为n的缓冲区 每个生产者都要把生产的物品存入缓冲区 每个消费者要从缓冲区中取物品 beginbuffer array 0 n 1 ofintegerk t integer k 0 t 0 SP SG mutex1 mutex2 semaphore SP n SG 0 mutex1 1 mutex2 1 cobegin processproduceri i 1 2 beginL1 produceaproductP SP P mutex1 buffer k product k k 1 modn V mutex1 V SG gotoL1 end coend end processconsumeri i 1 2 beginL2 P SG P mutex2 takeaproductfrombuffer t t t 1 modn V mutex2 V SP Consume gotoL2 end 桌上放一个盘子 每次只能放一个水果 爸爸像盘子里放苹果 妈妈向盘子里放橘子 女儿专吃苹果 儿子专吃橘子 盘子空的时候爸爸或妈妈才能向盘子里面放一个水果 仅当盘子里有自己需要的水果时才可取一个水果 把爸爸 妈妈 儿子 女儿看做四个进程 用PV操作进行管理 使这四个进程能正确地并发执行 beginmutex SA SO semaphore mutex 1 SA 0 SO 0 cobegin process爸爸beginL1 P mutex 放苹果V SA gotoL1 end process妈妈beginL2 P mutex 放橘子V SO gotoL2 end coend end process儿子beginL4 P SO 拿橘子V mutex gotoL4 end process女儿beginL3 P SA 拿苹果V mutex gotoL3 end P2258 如果盘子的容量改为2 且任何时刻只允许爸爸 妈妈 女儿 儿子中的一个进程去访问盘子 放或者取 beginmutex1 mutex2 SA SO semaphore mutex1 2 mutex2 1 SA 0 SO 0 cobegin process爸爸beginL1 P mutex1 盘子P mutex2 伸手放苹果V mutex2 V SA gotoL1 end process妈妈beginL2 P mutex1 盘子P mutex2 伸手放橘子V mutex2 V SO gotoL2 end coend end process女儿beginL3 P SA P mutex2 伸手拿苹果V mutex2 V mutex1 gotoL3 end process儿子beginL4 P SO P mutex2 伸手拿橘子V mutex2 V mutex1 gotoL4 end 有三个进程A1 A2 A3 它们共享两个缓冲区B1和B2 缓冲区B1中可以存放n件产品 缓冲区B2中可以存放m件产品 进程A1每次生产一件产品 并把产品存入缓冲区B1 进程A2每次生产一件产品 并把产品存入缓冲区B2 进程A3每次从缓冲区B2中取一件产品区消费 为了防止把产品存入已满的缓冲 或者从空缓冲中取产品 或重复取一产品 用PV操作实现它们的相互制约关系 BeginB1 B2 array 0 n 1 ofintegerk1 k2 t1 t2 integer k1 0 k1 0 t1 0 SP SG semaphore SP n SG 0 cobegin processproducerbeginL1 produceaproductP SP buffer k product k k 1 modn V SG gotoL1 end coend End 进程通信 并发进程间可以通过PV操作交换信息实现进程的互斥和同步 因此可以把PV操作看做进程间的一种通信方式 但这种通信只交换了少量的信息 如果进程间要交换大量信息 这种大量信息的传递要有专门的通信机制来实现 通过专门的通信机制实现进程间大量信息的通信方式称为进程通信 通信机制 采用高级通信方式时 进程间用信件来交换信息 信件 信件内容包括发送者名 信息 信息存放的地址和长度 等 不等回信 回信存放地址 通信方式 信件的传递是由通信原语完成的 最基本的原语是两条 发送 send 原语和接收 receive 原语 通信方式 直接通信方式这种通信方式总是固定在一对进程之间进行send B M 把信件M发送给B A B receive A X 接受来自进程A的信件存入X中 通信方式 间接通信这种通信方式总是信箱为媒体来实现通信的 接受进程设立一个信箱 任何要向该进程发信的进程总是把信件发送到该进程的信箱里 A B 信箱N send N M 把信件M送入信箱N中 receive N X 从信箱N中取出一封信存入X 取 发 间接通信的实现 间接通信指的是进程之间利用信箱来交换信息 通信时要遵循的规则 信箱满时 把发送信件的进程置成 等信箱 直到信箱有空才被释放若信箱无信 则把接收信件的进程置成 等信件 直到信箱有信件才释放 取信件 信箱说明 信箱的数据结构定义 TYPEbox recordsize 0 n 信箱大小count 0 n 现有信件数letter array 1 n ofmessage 信件S1 S2 semaphore end send原语过程 proceduresend varB box M message vari integer beginifB count B sizethenW B S1 如果信箱满 等信箱elsebegini B count 1 确定可存放信件的位置B letter i M 信件存放到信箱指定位置B count i 信箱的信件数 1R B S2 释放等信件者end end send receive原语过程 procedurereceive varB box M message vari integer beginifB count 0thenW B S2 如果信箱无信 等信件elsebeginX B letter 1 总是取第一封信B count B count 1 信件数 1ifB count0thenfori 1toB countdoB letter i B letter i 1 所有信件上移R B S1 释放一个等信箱的进程end end receive 进程通信示意 组织信件Msend B M receive A Y receive B X 处理信件M组织回信Nsend A N 信件M 信件N B进程信箱 A进程信箱 A进程 B进程 磁盘管理 欲访问磁盘的进程begin 组织信件M send B M end 磁盘管理进程L1 receive B X 按信件要求组织通道程序 通道程序首址存入CAW 启动磁盘 等待磁盘传输结束 组织回信M send name M gotoL1 end 用进程通信实现进程同步 用直接通信方式解决生产者 消费者问题 cobegin processproducerbeginL1 生产物品组织信件Msend consumer M gotoL1 end cobegin processconsumerbeginL2 receive producer X 处理X中的信件gotoL2 end UNIX中的进程同步 UNIX的进程在用户态执行时 使用wait系统调用让自己等待 子进程执行完毕 用系统调用exit来终止自己 UNIX的进程在核心态执行时 使用sleep系统调用让进程进入睡眠态 使用wakeup来唤醒进程 UNIX中的进程通信 管道机制 UNIX中的管道通信机制允许进程按先进先出的方法传送信息 无名管道pipe无名管道pipe适用于一个用户有同一祖先的父子进程间的通信 无名管道就是一个进程间的共享文件 称为pipe文件一个进程调用pipe系统调用来建立一个无名管道 pipe文件 其子进程可以与该进程共享该管道 对pipe文件进行读写 P1 P2 无名管道 intfds 2 charbuffer 1024 pipe fds fds 0 用于读管道文件 fds 1 用于写管道文件write fds 1 buffer 6 从buffer写6个字节到管道文件read fds 0 buffer 6 从管道文件中读6个字节到buffer UNIX中的进程通信 管道机制 命名管道FIFOFIFO适用于不同用户的进程间通信 命名管道是一个有文件名的管道文件 用户可以用shell命令mknod来创建一个管道文件 也可以在程序中使用mknod调用来创建 使用方式同普通文件 命名管道FIFO charstri