2.2.6 经典的进程同步问题
这里介绍两个经典的进程同步问题以及它们的解决方法,这些问题代表了计算机应用中进程之间并发及共享资源的典型问题,深入分析和理解这些例子对于全面解决操作系统内同步、互斥问题有很大启发,同时对设计计算机应用软件有重要指导作用。
1.生产者-消费者问题
生产者-消费者问题是计算机中某些实际问题的一个抽象,代表两类对象共享资源,形成间接制约的关系。将问题描述为:一组生产者和一组消费者,通过一个有界的缓冲池进行通信。生产者不断(循环)将产品送入缓冲池,消费者不断(循环)从中取用产品。这里既存在同步问题又存在互斥问题。
这里将生产者和消费者看为两类进程,同步问题存在于两类进程之间。
·若缓冲池满(供过于求),则生产者不能将产品送入,必须等待消费者取出产品;
·若缓冲池已空(供不应求),则消费者不能取得产品,必须等待生产者送入产品。
互斥问题则存在于所有进程之间:缓冲池是临界资源,所有进程必须互斥地使用缓冲池,不论是存放产品还是取出产品。
使用信号量机制解决这个同步与互斥问题。先来看同步问题,如上分析,生产者和消费者的执行顺序,初始时,生产者先生产产品,之后消费者才能消费;接下来二者的执行顺序是不可预测的,但是与产品多少有关,也与缓冲池大小有关,因此控制二者同步,需要设置两个同步信号量,一个是产品数量(也可以看成满缓冲数量),一个是空缓冲数量,前者记为full,后者记为empty,这两个同步变量有语义含义,因此其初值设置也与语义相关,full的初值为0(开始时无产品),empty的初值为n。再来看互斥问题,这里只有一种临界资源,缓冲池,因此设一个互斥信号量mutex,切记,互斥信号量初值一定为1。
为了描述这个问题,将每类进程分为两部分:生产者的工作分为“生产产品”和“存放产品”,其中“生产产品”为非临界区,“存放产品”为临界区;消费者的工作分为“取出产品”和“消费产品”,其中“消费产品”为非临界区,“取出产品”为临界区。使用Wait作为临界区入口码,Signal作为临界区出口码。设producer为生产者进程,consumer为消费者进程,数组buffer表示一个环形缓冲池,in为缓冲池存放产品的指针,out为缓冲池取出产品的指针,nextp代表生产的产品,nextc代表消费的产品,则生产者与消费者并发执行过程形式描述如图2-22所示。
图2-22中对于生产者来说执行以下步骤。
①首先生产产品。
②将产品放入缓冲区(即将进入临界区)。
③执行临界区入口码程序:
·申请空缓冲区,执行Wait(empty),申请同步信号量empty,如果当前有空缓冲区,则进程继续执行;否则进程阻塞——阻塞点P1;
·生产者获得空缓冲区后,申请互斥进入临界区,执行Wait(mutex),如果此时无进程在临界区,则生产者进入临界区,否则进程阻塞——阻塞点P2。
④在临界区存放产品结束,退出临界区,执行临界区出口码:
·执行出口码Signal(mutex),唤醒因等待互斥信号量而阻塞的进程,如生产者的P2阻塞点或者消费者的S2阻塞点;
·执行出口码Signal(full),唤醒因等待产品而阻塞的进程,如消费者的S1阻塞点。
图2-22 生产者与消费者并发执行过程形式描述
对于消费者来说执行以下步骤。
①从缓冲区取出产品(即将进入临界区)。
②执行临界区入口码程序:
·申请取出产品,执行Wait(full),申请同步信号量full,如果当前缓冲区有产品,则进程继续执行;否则进程阻塞——阻塞点S1;
·消费者得知有产品后,申请互斥进入临界区,执行Wait(mutex),如果此时无进程在临界区,则消费者进入临界区,否则进程阻塞——阻塞点S2。
③在临界区取出产品结束,退出临界区,执行临界区出口码:
·执行出口码Signal(mutex),唤醒因等待互斥信号量而阻塞的进程,如生产者的P2阻塞点或者消费者的S2阻塞点;
·执行出口码Signal(empty),唤醒因等待空缓冲区而阻塞的进程,如生产者的P1阻塞点。
④消费产品。
两类进程同步过程如图2-23所示。
这里临界区的入口控制码都由两个Wait操作组成,注意这两个Wait操作的顺序千万不能颠倒,否则可能引起死锁(Deadlock)。死锁是并发进程竞争资源的最大问题。死锁概念是由荷兰学者Dijkstra在1965年提出的。死锁是指两个或两个以上的进程在运行过程中,因争夺资源而造成的一种互相等待(谁也无法再继续推进)的现象。若无外力作用,它们都将无法推进下去,造成进程永远不能完成,并且阻碍使用系统资源,阻止了其他作业开始执行,导致系统的资源利用率急剧下降,最终会导致操作系统崩溃。读者如果想进一步了解死锁的相关概念,可以阅读其他操作系统书籍。
图2-23 生产者与消费者进程同步过程示意图
计算机应用程序中存在许多生产者-消费者问题。如手机短信网关,接收上行短信进程和转发下行短信进程,共享一个存储短信的缓冲池,二者构成生产者-消费者关系,接收进程将短信写入缓冲池,转发进程从中取出短信。当缓冲池满时,接收进程不能接收短信,或者接收新短信写入缓冲池,覆盖掉旧短信(高峰期短信丢失可能与缓冲池不够大有关);当缓冲池为空时,转发进程等待。对缓冲池的互斥访问也与典型问题相同。
2.读者-写者问题
生产者-消费者问题描述的情况是协作的进程运行比较均衡,这里考虑另一类较普遍的情况,从被共享的数据对象考虑,多个并发进程共享一个数据对象(如数据库或文件),这些进程中有的只想读共享数据,而其他一些进程可能要更新(即改和写)共享数据,把前者称为读者,后者称为写者,将这类问题抽象为读者-写者问题来描述和解决。
一个数据文件或记录,可被多个进程共享,我们把只要求读该文件的进程称为“Reader进程”,其他进程则称为“Writer进程”。显然,多个读者同时读共享数据是没有问题的,然而一个写者和别的进程同时存取共享数据,则可能产生混乱。这个问题和前面所举火车售票系统很相似,车票文件即共享数据,对车票的查询程序为读者,而售出车票程序是写者,多个窗口运行查询程序,为并发的读者进程,可以同时查询到正确的车票数量,但是当售出车票程序改写车票数量时则不允许有其他进程读或者写该车次的车票数量,否则,读取或售出都会造成车票数量的不正确。因此解决读者-写者问题,是指保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。即允许多个进程同时读一个共享对象,但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。
为了解决读者-写者问题,先来分析多个并发进程的行为。进程分为两类,读者Reader进程和写者Writer进程,它们共同访问临界资源——数据对象。多个Reader进程和多个Writer进程各自以自己的速度运行,各自的工作如下。
Reader进程临界区入口时:首先判断是否有Reader进程在访问数据对象,如果没有,说明有可能有Writer进程在访问数据对象,需要与Writer进程互斥访问数据对象;否则直接进入临界区读数据对象。
Reader进程临界区出口时:判断是否还有Reader进程在访问数据对象,如果没有,可以唤醒等待进入的Writer进程;否则直接退出临界区。
Writer进程:只单纯考虑与其他Writer进程的互斥即可。
利用信号量机制解决读者-写者问题,首先设置一个写数据对象的互斥信号量Wmutex,初值为1;另外,由以上分析发现,Reader进程处在临界区的数量对各进程运行有很大影响,因此设一个整数变量ReaderCount,记录Reader进程处在临界区的数量,这个变量初值为0,它的变化由Reader进程进出临界区时加1或减1,注意,每个Reader进程都要访问ReaderCount变量,但是对其加1或减1的操作需要互斥进行,否则会出现混乱,显然变量ReaderCount也是一个临界资源,而对它的加减操作的程序段也是临界区,因此对该临界资源设一个互斥信号量RCmutex,初值为1。利用信号量机制解决读者-写者问题的算法描述如图2-24所示。
图2-24 信号量机制解决读者-写者问题的算法描述
在Reader进程中,在“读数据对象”前后,分别要对读进程数量变量ReaderCount进行加减操作,形成两个临界区,如图中虚线框所示,ReaderCount的值变化影响读者和写者进程运行关系,算法通过两个临界区的入口码和出口码进行控制。
Reader进程(读者进程)工作流程如下。
①读者为了进行“读数据对象”工作,先要对Reader Count变量进行操作,进入第一临界区(ReaderCount++),要执行进入此临界区的入口码代码。
·申请互斥信号量RCmutex,执行Wait(RCmutex);如果没有申请到互斥信号量,说明有进程在临界区内,本进程阻塞——阻塞点R1;否则继续执行。
·判断Reader Count是否为0,如果为0,说明没有读者在进行读操作,那么有可能有Writer进程在临界区内进行写操作,因此申请互斥信号量Wmutex,执行Wait(Wmutex)操作。
·执行Wait(Wmutex)操作,判断如果Writer进程没有在临界区,那么读者从此入口码出来,进入读者第一临界区。
·如果Writer进程在临界区,那么读者进程阻塞在此——阻塞点R2。
②第一临界区操作:Reader Count++。
③第一临界区出口码:执行Signal(RCmutext);唤醒因等待RCmutex而阻塞的进程(其他进程的阻塞点R1,阻塞点R3)。
④读者进程读数据操作。
⑤读者进程结束读数据操作,退出,要对Reader Count变量操作,即进入第二临界区(ReaderCount——),要执行进入此临界区的入口码代码。
申请互斥信号量RCmutex,执行Wait(RCmutex);如果没有申请到互斥信号量,说明有进程在临界区内,本进程阻塞——阻塞点R3;否则继续执行。
⑥第二临界区操作:Reader Count——。
⑦退出第二临界区出口码。
·判断Reader Count是否为0,如果为0,首先判断是否有读者在申请写操作,如果唤醒因此阻塞的写者进程,执行Signal(Wmutex),唤醒阻塞在阻塞点W1的写者。
·执行Signal(RCmutext);唤醒因等待RCmutex而阻塞的读者进程(其他进程的阻塞点R1,阻塞点R3)。
Writer进程(写者进程)工作流程如下。
①执行“更新数据操作”临界区入口码。
申请写操作互斥信号量,执行Wait(Wmutex),如果无法得到,阻塞自己——阻塞点W1;否则继续执行。
②进入临界区,更新数据操作。
③更新数据操作结束,退出临界区,执行Signal(Wmutex),唤醒阻塞在阻塞点W1的写者,或者阻塞在阻塞点R1的读者。
读者-写者同步关系如图2-25所示。
读者-写者问题对解决非对称进程的同步及互斥有很好的借鉴作用。
图2-25 读者-写者同步关系