操作系统 读者写者问题

读者写者问题是一个经典的进程同步问题，它涉及到一个数据集，例如一个文件在同一时间被多个进程共享。在这些不同的进程中，一些是读者-它们只能读取数据集，不进行任何更新，一些是写者-它们可以读取和写入数据集。

读者写者问题用于管理读者和写者进程之间的同步，以避免数据集出现问题，即不会产生不一致性。

让我们通过一个例子来理解-如果两个或多个读者在同一时间想要访问文件，那么不会有问题。然而，在其他情况下，比如当两个写者或一个读者和一个写者在同一时间想要访问文件时，可能会出现问题，因此任务是设计代码，使得如果有一个读者在读取，那么在同一时间不允许有写者进行更新，同样地，如果有一个写者在写入，那么在那个时间点不允许读者读取文件，并且如果有一个写者正在更新一个文件，其他写者不应该被允许在同一时间更新文件。然而，多个读者可以同时访问该对象。

让我们通过下面的表格来了解读写的可能性：

表1

读者和写者的解决方案可以使用二进制信号量来实现。

我们使用两个二进制信号量“write”和“mutex”，其中二进制信号量可以定义为：

信号量：信号量是S中的整数变量，在初始化之外只能通过两个标准原子操作 – 等待（wait）和信号（signal）来访问，其定义如下：

1. wait( S )
{
while( S <= 0) ;
S--;
}

2. signal( S )
{
S++;
}

从以上对wait的定义可知，如果S的值小于等于0，则会进入无限循环（因为while循环后面有一个分号）。而signal的作用是增加S的值。

下面的代码将解决读者-写者问题，给出了读者和写者进程的代码如下-

读者进程的代码

读者进程的代码如下-

static int readcount = 0;
wait (mutex);
readcount ++; // on each entry of reader increment readcount
if (readcount == 1)
{
  wait (write);
}
signal(mutex);

--READ THE FILE?

wait(mutex);
readcount --; // on every exit of reader decrement readcount
if (readcount == 0)
{
  signal (write);
}
signal(mutex);

在上述的读取器代码中， mutex 和 write 是初始化值为1的信号量，而 readcount 变量的初始值为0。在读取器和写入器的代码中， mutex 和 write 都是共享的，信号量 mutex 确保互斥性，而信号量 write 处理写入机制。

readcount 变量表示同时访问文件的读取器数量。当 readcount 变为1时，使用等待操作来减少写入信号量的值。这意味着一个写入器不再被允许访问文件。完成读取操作后， readcount 减一。当 readcount 变为0时，使用信号操作来允许 write 写入器访问文件。

写者进程的代码

下面给出了定义写者进程的代码：

wait(write);
WRITE INTO THE FILE
signal(wrt);

如果写作者希望访问文件， 等待 操作将在 写入 信号量上执行，该操作将将 写入 减少到0，并且没有其他写入者可以访问该文件。当访问文件的写入作业完成后，将在 写入 上执行信号操作。

让我们看看表1中提及的每种情况的证明

CASE 1: 写入 – 写入→不允许。当两个或多个进程愿意写入时，不允许这种情况。让我们看看我们的代码是否按预期工作？

Explanation :
The initial value of semaphore write = 1
Suppose two processes P0 and P1 wants to write, let P0 enter first the writer code, The moment P0 enters
 Wait( write ); will decrease semaphore write by one, now write = 0
And continue WRITE INTO THE FILE
Now suppose P1 wants to write at the same time (will it be allowed?) let's see.
P1 does Wait( write ), since the write value is already 0, therefore from the definition of wait, it will go into an infinite loop (i.e. Trap), hence P1 can never write anything, till P0 is writing.
Now suppose P0 has finished the task, it will
signal( write); will increase semaphore write by 1, now write = 1
if now P1 wants to write it since semaphore write > 0
This proofs that, if one process is writing, no other process is allowed to write.

CASE 2: 读取-写入 → 不允许。当一个或多个进程正在读取文件时，另一个进程的写入是不允许的。让我们看看我们的代码是否按照预期工作？

Explanation:
Initial value of semaphore mutex = 1 and variable readcount = 0
Suppose two processes P0 and P1 are in a system, P0 wants to read while P1 wants to write, P0 enter first into the reader code, the moment P0 enters 
Wait( mutex ); will decrease semaphore mutex by 1, now mutex = 0
Increment readcount by 1, now readcount = 1, next
if (readcount == 1)// evaluates to TRUE
{
  wait (write); // decrement write by 1, i.e. write = 0(which   
                   clearly proves that if one or more than one 
                   reader is reading then no writer will be  
                   allowed.
}

signal(mutex); // will increase semaphore mutex by 1, now mutex = 1 i.e. other readers are allowed to enter.

And reader continues to --READ THE FILE?

Suppose now any writer wants to enter into its code then:

As the first reader has executed wait (write); because of which write value is 0, therefore wait(writer); of the writer, code will go into an infinite loop and no writer will be allowed.
This proofs that, if one process is reading, no other process is allowed to write.
Now suppose P0 wants to stop the reading and wanted to exit then
Following sequence of instructions will take place:
wait(mutex); // decrease mutex by 1, i.e. mutex = 0
readcount --; // readcount = 0, i.e. no one is currently reading
if (readcount == 0) // evaluates TRUE
{
  signal (write); // increase write by one, i.e. write = 1 
}
signal(mutex);// increase mutex by one, i.e. mutex = 1

Now if again any writer wants to write, it can do it now, since write > 0

CASE 3: 写入 – 读取 → 不允许。这是指如果一个进程正在向文件中写入数据，那么另一个进程就不允许读取。我们来看看我们的代码是否按照预期工作？

Explanation:
The initial value of semaphore write = 1
Suppose two processes P0 and P1 are in a system, P0 wants to write while P1 wants to read, P0 enter first into the writer code, The moment P0 enters 
Wait( write ); will decrease semaphore write by 1, now write = 0
And continue WRITE INTO THE FILE
Now suppose P1 wants to read the same time (will it be allowed?) let's see.
P1 enters reader's code
Initial value of semaphore mutex = 1 and variable readcount = 0
Wait( mutex ); will decrease semaphore mutex by 1, now mutex = 0
Increment readcount by 1, now readcount = 1, next
if (readcount == 1)// evaluates to TRUE
{
  wait (write); // since value of write is already 0, hence it 
                   will enter into an infinite loop and will not be  
                   allowed to proceed further (which clearly 
                   proves that if one writer is writing then no  
                   reader will be allowed.
}

The moment writer stops writing and willing to exit then 
This proofs that, if one process is writing, no other process is allowed to read.

The moment writer stops writing and willing to exit then it will execute:
signal( write); will increase semaphore write by 1, now write = 1
if now P1 wants to read it can since semaphore write > 0 

CASE 4： READING – READING → 允许。这是指当一个进程正在读取文件时，其他进程也愿意读取，那么它们都是允许的，即读取-读取并非互斥的。让我们看看我们的代码是否按照预期工作？

Explanation :
Initial value of semaphore mutex = 1 and variable readcount = 0
Suppose three processes P0, P1 and P2 are in a system, all the three processes P0, P1, and P2 want to read, let P0 enter first into the reader code, the moment P0 enters 
Wait( mutex ); will decrease semaphore mutex by 1, now mutex = 0
Increment readcount by 1, now readcount = 1, next
if (readcount == 1)// evaluates to TRUE
{
  wait (write); // decrement write by 1, i.e. write = 0(which   
                   clearly proves that if one or more than one 
                   reader is reading then no writer will be  
                   allowed.
}

signal(mutex); // will increase semaphore mutex by 1, now mutex = 1 i.e. other readers are allowed to enter.

And P0 continues to --READ THE FILE?

→Now P1 wants to enter the reader code
current value of semaphore mutex = 1 and variable readcount = 1
let P1 enter into the reader code, the moment P1 enters 
Wait( mutex ); will decrease semaphore mutex by 1, now mutex = 0
Increment readcount by 1, now readcount = 2, next
if (readcount == 1)// eval. to False, it will not enter if block

signal(mutex); // will increase semaphore mutex by 1, now mutex = 1 i.e. other readers are allowed to enter.

Now P0 and P1 continues to --READ THE FILE?

→Now P2 wants to enter the reader code
current value of semaphore mutex = 1 and variable readcount = 2
let P2 enter into the reader code, The moment P2 enters 
Wait( mutex ); will decrease semaphore mutex by 1, now mutex = 0
Increment readcount by 1, now readcount = 3, next
if (readcount == 1)// eval. to False, it will not enter if block

signal(mutex); // will increase semaphore mutex by 1, now mutex = 1 i.e. other readers are allowed to enter.

Now P0, P1, and P2 continues to --READ THE FILE?


Suppose now any writer wants to enter into its code then:

As the first reader P0 has executed wait (write); because of which write value is 0, therefore wait(writer); of the writer, code will go into an infinite loop and no writer will be allowed.  

Now suppose P0 wants to come out of system( stop reading) then
wait(mutex); //will decrease semaphore mutex by 1, now mutex = 0
readcount --; // on every exit of reader decrement readcount by 
                 one i.e. readcount = 2

if (readcount == 0)// eval. to FALSE it will not enter if block

signal(mutex); // will increase semaphore mutex by 1, now mutex = 1 i.e. other readers are allowed to exit


→ Now suppose P1 wants to come out of system (stop reading) then
wait(mutex); //will decrease semaphore mutex by 1, now mutex = 0
readcount --; // on every exit of reader decrement readcount by 
                 one i.e. readcount = 1

if (readcount == 0)// eval. to FALSE it will not enter if block

signal(mutex); // will increase semaphore mutex by 1, now mutex = 1 i.e. other readers are allowed to exit

→Now suppose P2 (last process) wants to come out of system (stop reading) then
wait(mutex); //will decrease semaphore mutex by 1, now mutex = 0
readcount --; // on every exit of reader decrement readcount by 
                 one i.e. readcount = 0

if (readcount == 0)// eval. to TRUE it will enter into if block
{
  signal (write); // will increment semaphore write by one, i.e. 
                     now write = 1, since P2 was the last process
                     which was reading, since now it is going out, 
                     so by making write = 1 it is allowing the writer    
                     to write now.
}

signal(mutex); // will increase semaphore mutex by 1, now mutex = 1 


The above explanation proves that if one or more than one processes are willing to read simultaneously then they are allowed.