进程同步与互斥

进程同步与互斥（1）

第一节、进程间相互作用

一、相关进程和无关进程

二、与时间有关的错误

第二节、进程同步与互斥

一、进程的同步

二、进程的互斥

三、临界区

进程同步与互斥（2）

三、信号量与P、V操作的物理含义

四、用P、V操作实现进程间的互斥

五、用P、V操作实现进程间的同步

六、信号量及P、V操作总结

进程同步与互斥（3）

第四节经典的进程同步问题

一、简单生产者--消费者问题

二、多个生产者--消费者问题

三、读者--写者问题

进程同步与互斥（4）

四、同步与互斥的综合应用

第五节管程

一、管程的提出

第六节进程通讯

一、共享内存

二、消息机制

三、管道通信

进程同步与互斥（1）

第一节、进程间相互作用

一、相关进程和无关进程

1.相关进程：在逻辑上具有某种联系的进程
2.无关进程：在逻辑上没有关联的进程
3.举例：（1）为两个不同源程序进行编译的进程，它们可以并发执行，但它们之间无关
（2）三个进程，分别是读数据进程、处理数据进程、打印结果进程，它们相互依赖、相互合作，是一组相关进程。

二、与时间有关的错误

对于相关进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束，另一进程也开始使用，形成交替使用共享资源。
结果：形成与时间有关的错误

第二节、进程同步与互斥

一、进程的同步

进程的同步：是指进程之间一种直接的协同工作关系，一些进程相互合作共同完成一项任务。（一个进程执行完任务，另一个进程才能执行）
例如：进程A从硬盘上读记录，每读出一个记录就存入缓冲区，进程B从缓冲区中取出记录加工，直至所有记录处理结束。
直接制约关系：A若没有把记录读入缓冲区，B等待；反之，B若从缓冲区取出记录，A等待；

二、进程的互斥

在系统中，许多进程常常需要共享资源，而这些共享资源往往需要排他性的使用，即一次只能为一个进程服务，因此，各进程间只能互斥使用这些资源，进程间的这种关系就是进程的互斥。
例如：多个进程竞争使用打印机、一些变量、表格等资源，进程间的互斥是一种间接制约关系。（同步是直接制约关系）

三、临界区

1.临界资源：若在系统中的某些资源一次只允许一个进程使用，则这类资源称为临界资源或共享变量。
2.临界区：访问临界资源的那段代码
3.相关临界区：如果有若干进程共享某一临界资源，则该临界区称为相关临界区
4.相关临界区的调度使用原则：当临界资源空闲时，若有一个进程要求进入临界区，应允许它立即进入。---有空让进，有效利用资源。
（2）若有一个进程已在临界区，其他要求进入临界区的进程必须等待，--无空等待，互斥进入
（3）当没有进程在临界区，而同时有多个进程要求进入临界区，选择其一进入，其他等待。多种选一
（4）任一进程进入临界区的要求应在有限时间满足--有限等待，避免死等。
（5）处于等待状态的进程应放弃占用处理器。---让权等待，避免忙等。

进程同步与互斥（2）

三、信号量与P、V操作的物理含义

信号量S表示某类可用的资源，对于不同的资源，用不同的信号表示。
S>0时，S表示某类资源的可用数量
S<0时，其绝对值表示排在S等待队列中进程的数目。
执行一次P操作，表示请求一个资源。
执行一次V操作，表示进程释放一个资源。

四、用P、V操作实现进程间的互斥

假设有进程A、B竞争进入临界区，用P、V操作实现进程之间的互斥。
首先定义信号量S，并使之初值为1。

五、用P、V操作实现进程间的同步

解决思路：如果有两个进程同步，设置两个信号量S1，S2，初始值可以设为0。为了表达同步，同一信号量的P、V
操作分属于两个进程，如例一：

例二：有三个进程，进程get从输入设备上不断读取数据，并放入缓冲区buffer1；进程copy不断地将缓冲区buffer1中的内容复制到缓冲区buffer2；进程put则不断将buffer2中的内容在打印机上输出。
三者的制约关系：get进程必须先从设备读数据到buffer1，copy进程才能从buffer1复制内容到buffer2，最后put进程才能打印buffer2的内容。
反之，copy进程从buffer1取走数据之后，get进程才能继续从设备读数据到buffer1，put进程从buffer2取走数据之后，copy进程才能复制buffer1的数据到buffer2。
故可以设置四个信号量来保证三者的执行顺序
信号量设置：
S1，初始值为1，保证get进程能够从设备读取数据到buffer1。
S2，初始值为0，copy进程能否将buffer1数据复制到buffer2。
S3，初始值为1，put进程能否将buffer2内容打印输出。
S4，初始值为0，保证buffer2缓冲区内容可用

六、信号量及P、V操作总结

1.P、V操作必须成对出现
2.互斥操作时，P、V操作出现在同一进程
3.同步操作时，P、V操作出现在不同进程
4.既有同步、又有互斥操作时，同步信号量P操作在前，互斥信号量P操作在后，V操作顺序不限。

进程同步与互斥（3）

第四节经典的进程同步问题

一、简单生产者--消费者问题

问题描述：设有一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来，如图4-2所示。
1.二者关系描述：
（1）生产者生产产品放入缓冲区，消费者从缓冲区取产品，进行消费；
（2）P进程不能往已经“满”的缓冲区放产品，Q进程不能从“空”缓冲区取产品
2.信号量设置：
empty，初值为1，用于指示空缓冲区数量
full,初值为0，用于指示满缓冲区数量
3.解决方案：

二、多个生产者--消费者问题

1.问题描述：设有若干个生产者P1、P2、……，若干个消费者Q1、Q2、……，他们通过一个环形缓冲池联系起来，如图4-3所示。

2.同步问题和信号量设置，生产者不能往“满”缓冲区中放产品，设置信号量empty，初始值为k，指示缓冲池中空缓冲区数目。
消费者不能从“空”缓冲区中取产品，设置信号量full，初始值为0，指示缓冲池中的满缓冲区数目。
3.互斥问题和信号量设置，缓冲必须互斥访问，设置信号量mutex，初始值为1。
4.其他变量设置，整型量i、j，初始值0，分别用于指示空缓冲区和满缓冲区位置。
5.算法

6.例题：桌子上有一个水果的盘子，一次只能放一个水果，父亲向盘中放苹果或橘子，女儿专吃苹果，儿子专吃橘子，试用PV操作写出他们能正确同步的过程。
（1）分析：在本题中，爸爸、女儿、儿子共用一个盘子，盘子一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入盘中的是橘子，则允许儿子吃，女儿必须等待；若放入盘中的是苹果，则允许女儿吃，儿子必须等待；
本题实际是生产者--消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只能消费其中一类固定产品。

（2）信号量设置：设置3个信号量S、So、Sa，信号量S表示盘子是否为空其初值为1；信号量So表示盘子是否有橘子，其初值为0；信号量Sa表示盘子是否有苹果，其初值为0；
（3）信号量定义：Semaphore S=1，So=0，Sa=0
（4）算法

三、读者--写者问题

1.问题描述：假定有某个共享文件F，系统允许若干进程对文件F进行读或写。读文件的进程称为读者，写文件的进程称为写者，他们遵守如下规定：
（1）多个进程可以同时读文件F
（2）当一个进程在对文件F进行写时，不允许其他进程对文件进行读或写。
（3）当有进程正在读文件时不允许任何进程去写文件。
2.问题分析：
（1）写者与写者进程之间互斥，互斥文件F
（2）写者进程与第一个读者之间互斥访问文件。
3.变量设定：
read_count:整型量，当前正在读的读者进程个数，来一个读者数量加1，走一个读者数量减1；
mutex：互斥信号量，对read_count互斥访问
write：互斥信号量，写者与写者的互斥，写者与读者之间的互斥。
4.算法：

例题：若有一个文件F，供多进程读，现在把进程分成A、B两组，规定同组的进程可同时读文件F，但不同组的进程不能同时读文件F。试用PV操作写出该文件的同步算法。
（1）变量设置：定义两个计数器C1和C2分别记录A组和B组中正在读文件F的进程数，它们的初始值均为0。
（2）信号量设置：设置三个信号量S1、S2、SAB才能保证正确并发执行；S1用来保证A组进程对C1的互斥访问，S2用来保证B组对进程C2的互斥访问，SAB用来保证A组进程和B组进程对文件F的互斥访问，它们的初始值均为1；

进程同步与互斥（4）

四、同步与互斥的综合应用

例4-1：路口单双号交通管制
问题描述：某个城市为解决市内汽车太多、拥堵问题，出台一项措施，对进入市区的车辆实行单双号限行办法，规定单号单行，双号双行。
有一个进入市区中心的路口，进入该路口的道路有一条，离开该路口道路有两条，一条进入市区，一条进入环线，路口设有车牌识别设备和放行栅栏。如图4-4所示：
例4-1分析
可抽象为生产者--消费者问题
生产者：检查车辆牌号
消费者1：进入“市区放行栅栏”
消费者2：进入“进入环路放行栅栏”

第五节管程

一、管程的提出

信号量及P、V操作的缺点：
（1）程序易读性差
（2）程序不利于修改和维护
（3）正确性难以保证
（4）为了更易于编写正确的程序，引入管程

二、管程的概念及组成

定义：是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程。
组成：管程名称、共享数据说明、对数据进行操作的一组过程、对共享数据赋初值的语句。

第六节进程通讯

一、共享内存

1.原理：在相互通信的进程之间设有一个公共内存区，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程之间的信息交换。

二、消息机制

1.消息缓冲
消息缓冲通信原理：进程间的数据交换，是以格式化的消息（也称为消息报文）为单位的。程序员直接利用操作系统提供的一组通信命令（原语），实现大量数据的传递，通信过程对用户是透明的。
消息格式：
struct message_buffer{
int sender;//发送者进程标识符
int size;//消息长度
char *text;//消息正文
struct message_buffer *next;//指向下一个消息缓冲区的指针
}

2.信箱
信箱通讯原理：为了实现进程间的通信，可以设计一个通信机构-信箱，以发送信件和接收信件为进程间通信的基本方式。