2.3_9 读者-写者问题

（一）问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

因此要求：

1.允许多个读者可以同时对文件执行读操作；

2.只允许一个写者往文件中写信息；

3.任一写者在完成写操作之前不允许其他读者或写者工作；

4.写者执行写操作前，应让已有的读者和写者全部退出。

一个文件，可能多有多个读进程想对它进行读操作。由于读操作并不会更改这个文件当中的数据，所以，多个读进程同时读取文件是可以被允许的。

注意：读进程和消费者是不一样的。消费者在消费的时候会把这一块数据取走，而读者进程在读数据后并不会将数据拿走，也不会更改数据。

当一个写进程正在对文件进行写操作的时候，其他进程是不能访问这个文件的。或者换一个角度来讲，当一个写进程想要写这个共享文件的时候，它必须等待其他进程对这个文件的操作结束后，它才能往里面开始写数据。

问题1：读进程与写进程同时共享数据，可能导致读出的数据不一致的问题。

比如此时文件中有4条数据，而读者和写者并发运行的话。当读者读取前三条数据之后，转到写者进程运行，此时写者进程写数据，并把第四条数据做了更改。之后，再切换到读者进程继续读取数据，那么此时读进程读出的第四条数据就不是它原本想要的那个数据了。

问题2：两个写进程同时共享数据，可能导致数据错误覆盖的问题。

比如此时文件中有3条数据，而两个写者进程并发运行的话。写者1起初会认为第4块空间是空闲的，于是就会往那里写数据，正准备开始写、但还没有写的时候，切换了进程，切换到写者2，那么写者2也会认为第4块空间可以写数据。由于这两个写者数据都以为这个位置是空的，所以写者1会往这个位置写入自己的数据，写者2同时也会把自己的数据写进入。因此，就会发生，后面的写者把前面的写者所写数据给覆盖掉的问题。

（二）问题分析

接下来要做的事情，就是尝试用PV操作来解决这个问题。

1.关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

1）两类进程：写进程、读进程。

2）互斥关系：写进程-写进程互斥、写进程-读进程互斥。而读进程-读进程不存在互斥问题。

（三）如何实现

我们设置一个叫rw的互斥信号量，用于实现各个进程对文件的互斥访问。

写者进程要做的事情就是不断地写文件；读者进程要做的事情就是不断地读文件。

由于写者、读者进程之间，要互斥地进行访问文件这个共享资源，所以写者在写文件之前需要对rw这个互斥信号量进行P操作，也就是“加锁”；写完文件之后再“解锁”，即进行V操作。读者进程同理，需要在读之前加锁、在读之后解锁。——由此实现读者和写者之间互斥地访问文件。

但如果我们只是这样处理，会出现一个问题——不同的读者进程之间也要互斥地访问文件，即读者和读者不能同时访问文件。

为了解决这一问题，我们可以设置一个变量count，这个变量记录了“当前有几个读进程”正在访问这个文件。count的初始值为0，也即意味着刚开始并没有读进程在访问这个文件。

那么，当一个读进程要对文件进行加锁动作之前，它需要进行一个“检查”——看一下自己是不是第一个想要读这个文件的进程。如果自己是第一个读进程的话，那么它就会执行P(rw)操作，对文件执行加锁，同时执行count++，表示此时正在访问文件的进程数加1。而当任何一个读进程读完文件之后，都会执行count--，表示对这个文件进行访问的读进程数减1。同时，再对count的值进行判断，如果一个读进程执行完count--之后，发现count==0，那么就说明此时已经没有别的读进程正在读这个文件了，这种情况下，就说明，我这个读进程是最后一个正在读这个文件的进程，那么当我读完这个文件之后，我需要把这个文件“解锁”，即执行V(rw)。

这样一来，就可以实现读进程-读进程之间可以同时访问这个文件，同时，也不影响读进程-写进程的互斥问题。

到此，似乎问题已经解决了，但是仔细思考一下，还是存在一定的问题。

思考：若两个读进程并发执行，则count=0时两个进程也许都能满足if(count==0)的条件，都会执行P(rw)，从而会使第二个读进程阻塞。

如何解决：首先思考该问题出现的原因在于什么。出现该问题的原因在于，对count变量的检查和赋值无法一气呵成。因此，解决方案就有了——设置另外一个互斥信号量来保证各读进程对count的访问是互斥的。同一时刻只能有一个读进程进行对count变量的检查和赋值操作，那么就不会出现上述问题。

至此，已经没什么大的问题了。但是，仔细分析一下，依然存在一个潜在的问题。

问题：只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。在这种算法中，读进程是优先的。（读进程是有更高优先权的）

分析一下确实如此。由于在这个算法中，只有当最后一个读进程离开时，才会执行V(rw)对文件进行“解锁”。那么，如果在此期间有源源不断的读进程一直到来的话，也就是说这个文件一直有读进程正在读，那么写进程就会一直阻塞在P(rw)处，永远写不进来，导致写进程饿死的现象。

如何解决：我们可以再设置一个互斥信号量w，这个信号量是用于实现“写优先”的。然后，我们可以在如图所示的位置，对w执行P、V操作。

自行分析一下并发执行的情况：

读者1 —> 读者2；

写者1 —> 写者2；

写者1 —> 读者1；

读者1 —> 写者1 —> 读者2。

写者1 —> 读者1 —> 写者2。

理解：相当于在“读者源源不断地读文件”之间，给了写者一个参加排队的机会。写者只要发起P(w)并阻塞了，写者就会被放进阻塞队列。当读进程V(w)之后就会轮到写者开始写。而不是读者进程源源不断地读、完全不考虑写进程是否要写。（因为“记录型信号量”，它除了“记录当前这种资源还有几个”之外，它还有一个排队功能）

结论：在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，单页并不是真正的“写优先”，而是相对公平的先来先服务原则。——因此，有的书上把这种算法称为“读写公平法”。