4.3-第九讲 进程同步与通讯

第九讲进程同步与通讯 目的与要求 掌握信号量解决进程同步互斥问题的方法 掌握进程通信的基本实现方法 重点与难点 信号量的典型应用 通讯实现 作业 13 14 15 4 2 4进程同步与互斥举例一 有限缓冲区问题问题描述 设有n个缓冲区 一组生产者进程往缓冲区写数据 一组消费者进程从缓冲区取数据 写取以一个缓冲区为单位 说明 将缓冲池看作是共享数据 对缓冲区的操作必须是互斥操作 如果n个缓冲区全满 生产者进程必须等待 如果缓冲区全空 消费者进程必须等待 有限缓冲区的生产者 消费者问题 生产者和消费者共享一个产品缓冲池 共享N个缓冲区 P1P2 PmC1C2 Cn 生产者 消费者 缓冲池 解 设置以下信号量mutex 初值为1 控制互斥访问缓冲池 full 初值为0 表示当前缓冲池中满缓冲区数 empty 初值为n 表示当前缓冲池中空缓冲区数 有限缓冲区生产者 消费者进程描述如下 item表示消息数据类型 semaphorfull empty mutex itemnextp nextc 置初值full 0 empty n mutex 1 P empty P mutex getaemptybufferi bufferi next addbufferitofullbufferqueue V full V mutex while 1 Producer do produceaniteminnextp consumetheiteminnextc while 1 consumer do P full P mutex getabufferfromfullbufferqueue nextc bufferiputbufferibacktoemptyqueue V empty V mutex 若存在一共享数据A 那些对它进行读访问者叫Reader 对它进行写访问者叫做Writer 第一类Reader Writer问题 Reader和Writer争夺访问共享数据A时 Reader有较高优先数 表现在 除了某个Writer正在访问数据之外 任何情况下Reader欲访问数据均可以直接进行访问 二 Readers Writers问题 该问题可具体描述为 1 如果当前无人访问数据 则Reader Writer欲访问即可访问 2 如果已存在一个Reader正在访问数据 其它欲访问Reader可马上访问 这体现Reader有较高优先权 而欲访问的Writer必须等待 3 若某个Writer正访问数据 则欲访问的Reader Writer都必须等待 续 4 当最后一个结束访问数据的Reader发现有Writer正在等待时 则将其中一个唤醒 5 当某个Writer结束访问时 若只有Writer在等待 则唤醒某个Writer 若既有Writer也有Reader 则按FIFO或某它原则唤醒一个Writer或所有Reader Reader的一般结构为 P mutex readcount readcount 1 If readcount 1 P wrt V mutex 读数据AP mutex readcount readcount 1 If readcount 0 V wrt V mutex Writer的一般结构 P wrt 写数据AV wrt 三 哲学家就餐问题问题描述 五个哲学家五只筷子 哲学家循环做着思考和吃饭的动作 吃饭程序是 先取左边筷子 再取右边筷子 再吃饭 再放筷子 实现 为每个筷子设一把锁 信号量 初值为1 每个哲学家是一个进程 共享数据结构为semaphorechopstick 5 第i个进程描述为 i 0 4 do P chopstick i 取左边筷子 P chopstick i 1 5 取右边筷子 eat 放左边筷子 V chopstick i 放右边筷子 V chopstick i 1 5 think while 1 这可能导致死锁 4 3消息传递原理两种基本进程通讯方法 1 共享存储 Shared memory 相互通讯的进程有共享存储区 进程间可以通过直接读写共享存储区的变量来交互数据 同步与互斥在并发程序设计时安排进入程序 操作系统提供这样的共享存储区及某些同步互斥工具 2 消息传递 message passing 若进程间无共享空间 则必须通过消息传递通讯 且必须通过操作系统系统调用实现 消息传递系统调用语句的一般形式 发送消息 Send destination 接收消息 Receive source message 一 消息传递方法1 直接通讯法基本思想 进程在发送和接收消息时直接指明接收者或发送者进程ID 缺点 必须指定接收进程ID UNIX的信号机制类似这种形式 4 3 1消息传递通讯原理 举例 UNIX中两进程利用信号通讯 ProcessA kill 1040 SIGUSR1 向1040号进程发送一个SIGUSR1信号 ProcessB Signal SIGUSR1 func 当收到SIGUSR1信号时 就执行func 如果SIGUSR1信号未到 则系统登记func函数 待其信号到时再调用执行 2 间接通讯法 信箱命名法 基本思想 系统为每个信箱设一个消息队列 消息发送和接收都指向该消息队列 每个进程可以对消息队列发送并接收 只发送 只接收 缺点 必须有一个通讯双方共享的一个逻辑消息队列 UNIX的PIPE FIFO及IPC消息传递机制都属于这种形式 使用时消息发送者约定写方式打开信箱 消息接受者约定读方式打开信箱或同时读写打开 优点 很容易建立双向通讯链 只要对信箱说明为读写打开 逻辑通讯链容量 在通讯发送者和接收者之间存在一条逻辑通讯链 设链的容量是指该链暂存消息的能力 有限容量 表示链中有有限缓冲区 发送者不必等接收者发出接收请求 不必等接收者准备好接收缓冲区 即可将消息存于通讯链中的缓冲区中 消息从发送方缓冲进入系统缓冲区 即可再次发新消息 无需等上一消息被完全接收 二 消息缓冲与同步 发送者执行send 的同步问题 1 将发送者消息拷入通讯链缓冲区即将控制返回发送者 2 在将消息从硬通讯通道发出后将控制返回发送者 3 在消息由接收方节点的系统收到后再将控制返回发送者 4 在消息由接收方收到后再将控制返回发送者 5 在消息由接收方处理完后再将控制返回发送者 RPC LPC 为实现3 4情形同步需要建立回送到发送者所在系统的通讯链 5情形需要建立回送到发送者的通讯链 4 3 2进程消息传递通讯示例直接通讯消息系统 两个基本操作为 send A A指向含接收者pid和消息正文的空间 Receive A A指向缓冲区用于接收消息 该系统调用函数返回值是消息发送者pid 实现 系统有一空闲缓冲池 每个进程有一个消息缓冲队列 缓冲区用于存放消息及消息发送者pid和消息链指针 用pid定位进程PCB表 Sender spid 消息正文 消息链指针 消息缓冲区 每个进程的消息队列存放发送给该进程的消息 队列头存于PCB中 同时在PCB中设一互斥信号量mutex 初值为1 和信号量Sm 初值为0 Sm用于记录消息队列中的消息数 mutex Sm Sender spid text Sender spid text Receiver sPCBmessagemessage Hptr Send A New p 从缓冲池得一个buffer 置sender spid 将A中消息送bufferp 获得A中Receiver spid P mutex 将bufferp挂入相应的消息队