第05章 并发性：互斥与同步.pptVIP

* 5.5.1 同步 发送者执行send原语 接受者执行receive原因 发送者和执行者阻塞或不阻塞 排列组合2×2=4种 send阻塞、receive阻塞 send阻塞、receive不阻塞 send不阻塞、receive阻塞 send不阻塞、receive不阻塞 是否全部可行？会产生什么问题？ * 5.5.2 寻址 直接寻址 send原语包括目标进程ID receive原语事先知道源进程ID receive原语通过source参数知道源进程ID * 间接寻址 消息发送到临时保存这些消息的队列组成的一个共享数据结构 这些队列称为信箱（mailbox） 一个进程发送消息到信箱，另一个进程从信箱获取消息 5.5.2 寻址 * 5.5.2 寻址 图5.18 间接的进程通信 * 5.5.3 消息格式 * 5.5.4 排队原则 先进先出（FIFO） 优先级 允许接受者检查消息来选择 * 5.5.5 使用消息的互斥 Send无阻塞 Receive阻塞 mailbox初始化为一条无内容消息 获取消息的进程可进入临界区 离开临界区将消息放回信箱 可否实现互斥？？ * 5.5.5 使用消息的互斥 用消息解决生产者和消费者问题 有限缓冲区n Send无阻塞 Receive阻塞 两个信箱 mayproduce mayconsume * 5.6 读者-写者问题 任意多的读进程可以同时读一个文件 一次只有一个写进程可以往文件中写 如果一个写进程正在往文件中写时，则禁止任何读进程读文件 读读、读写、写写（并行/互斥） 生产者和消费者问题等价？ 生产者＝写进程？ 不仅仅是一个写进程，它必须读取队列指针，以确定往哪里写一项，并且它还必须确定缓冲区是否已满？ 消费者＝读进程？ 不仅仅是一个读进程，它必须调整队列指针以显示它已经从缓冲区中移走一个单元 * 5.6.1 读进程具有优先权 x：更新readcount变量的信号量 wsem：缓冲区访问权信号量 第一个读进程要获取访问权 最后一个退出的读进程要释放访问权 * 5.6.1 写进程具有优先权 x：更新readcount变量的信号量 y：更新writecount变量的信号量 z：读进程排队信号量 wsem：缓冲区写权限信号量 rsem：缓冲区读权限信号量 * 5.6.1 写进程具有优先权 通过消息传递实现 三个信箱 Readrequest Writerequest Finished 发送请求 获得批准 通知完成 发送请求 获得批准 通知完成 * 5.6.1 写进程具有优先权 通过消息传递实现 初始化（P176） Count=100 无读进程等待，读进程可能有0-N个在执行 等待所有正在执行的读进程结束 接受处理写进程请求 接受处理读进程请求，因无写进程申请，给读权限 只有写进程，无读进程 给写进程写权限 等待写进程结束 有写进程请求，但有读进程已经先获得读权限并正在执行 等待所有读进程完成 5.7 进程趋势图 S1 S2 S3 S4 * 作业 P177复习题5.8、5.11、5.13 P179习题5.2、5.3 P182习题5.13、5.14 练 习 一 设有一个发送者进程和一个接收者进程，其流程图如下所示。s是用于实现进程同步的信号量，mutex是用于实现进程互斥的信号量。试问流程图中的A、B、C、D四个框中应填写什么？假定缓冲区有无限多个，s 和mutex 的初值应为多少？ 发送者进程 申请缓冲区 把信息写入缓冲区 A 将缓冲区放到消息链尾 B semSingal(s) C D 从消息链首取一个缓冲区 semSignal(mutex) 从缓冲区中取出信息 释放缓冲区 接收者进程 练 习 二 桌子上有一空盘，允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专门等吃盘中的桔子，女儿专门等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用。 请用信号量原语实现爸爸、儿子、女儿三个并发进程的同步。 请用消息原语实现爸爸、儿子、女儿三个并发进程的同步。 请用管程实现爸爸、儿子、女儿三个并发进程的同步。 练 习 三 设公共汽车上，司机和售票员的活动分别是： 司机活动 启动车辆 正常行车 到站停车 售票员活动 关车门 售票 开车门 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？ 用信号量实现它们的同步 用消息实现它们的同步 用管程实现它们的同步 练 习 四 有个寺庙，庙中有小和尚和老和尚若干人，有一只水缸，由小和尚提水入缸给老和尚饮用。水缸可容10桶水，水取自同一口水井中。水井径窄，每次仅容一只水桶取水，水桶总数为3个。若每次只能入缸1桶水和取缸中1桶水，而且还不可以同时进行。试用一种同步工具写出小和尚和老和尚入水、取水的活动过程。 竞赛组队 /s/