in this article, we focus on three classic examples of PV operation: producer consumer problem, reader writer problem and philosopher dining problem. These three problems will be analyzed layer by layer and continuously improved. I hope to have a deeper understanding of PV operation through this process.

  producer consumer issues

   background description: there are two types of processes (producer and consumer). The producer is responsible for production, and the produced products will be put into the shared buffer. The size of the shared buffer is n. As long as the number of products does not reach n, you can continue to play. Consumers are responsible for taking products from the shared buffer. They can take them all the time only if the shared buffer is not empty. Realize the coordination of the two processes. The key points of the problem are as follows:

  version 1.0:

void producer() {
	while (true) {
		produce_an_item;
		while (count == n);
		buffer[in] = item;
		in = (in+1)%n;
		count++;
	}
}  
void customer() {
	while (count == 0);
	item = buffer[out];
	out = (out+1)%n;
	count--;
	consume_the_item;
}

  there is a problem in this version: for global variables modified by multiple processes, in order to prevent errors in the execution order during assembly. Will add a semaphore to limit it. Improvements are as follows:

  version 1.1:

semaphore mutex = 1; 
void producer() {
	while (true) {
		produce_an_item;
		while (count == n);
		buffer[in] = item;
		in = (in+1)%n;
		wait(mutex);
		count++;
		signal(mutex);
	}
}  
void customer() {
	while (count == 0);
	item = buffer[out];
	out = (out+1)%n;
	wait(mutex);
	count--;
	signal(mutex);
	consume_the_item;
}

   problems in 1.1: when using the while loop, there is a "busy" problem, which needs to be improved by the semaphore mechanism

  version 2.0:

    for the producer: define the semaphore empty and initialize it to n. when the product is put in, the number of empty will be reduced by one
    for consumers: define the semaphore full and initialize it to 0. When consuming products, the number of full is reduced by one
   the code is as follows:

semaphore empty=n,full=0; 
void producer() {
	while (true) {
		produce_an_item;
		wait(empty);
		buffer[in] = item;
		in = (in+1)%n;
		signal(full);
	}
}  
void customer() {
	wait(full);
	item = buffer[out];
	out = (out+1)%n;
	signal(empty);
	consume_the_item;
}

   this version also leaves such a problem (only for multiple producers / consumers):
   question 2: the two sentences buffer[in] = item and in=(in+1)%n in the producer are separated. In the case of multiple producer processes, process A may store item1 into the current in, and change to process B without having time to change in. Process B puts item2 into in again, overwriting the previous data. Similarly, the out of the consumer process is the same.

  version 3.0

   improvement: a mutually exclusive semaphore is specially added for in/out to make two statements execute continuously
   the code is as follows (similarly for consumer, add wait(mutex1) under wait(full) and signal(mutex1) under signal(empty)):

semaphore empty=n,full=0，mutex=1; 
void producer() {
	while (true) {
		produce_an_item;
		wait(empty);
		wait(mutex);
		buffer[in] = item;
		in = (in+1)%n;
		signal(mutex);
		signal(full);
	}
}  
void customer() {
	wait(full);
	wait(mutex);
	item = buffer[out];
	out = (out+1)%n;
	signal(mutex);
	signal(empty);
	consume_the_item;
}

  readers and writers

  Problem Description: for a document, there are two kinds of operation objects (reader and writer). Writers can read or write, and readers can only read but not write. Multiple readers can read at the same time. When a writer modifies data, other writers and readers cannot access it. As shown below:

  problem analysis: we need to pay attention to the sequence!
  No: writing, reading and writing
  yes: reading, writing and reading

  version 1.0:

semaphore mutex = 1;
void writer() {
	while (true) {
		wait(mutex);
		// write something;
		signal(mutex);
	}
} 
void reader() {
	while (true) {
		wait(mutex);
		// read something;
		signal(mutex);
	}
} 

  the problem with this version is that there is only one semaphore mutex, which leads to only one reader reading at the same time, which violates the requirement of multiple readers reading at the same time.

  version 2.0:

semaphore mutex = 1;
int readcount = 0;
void writer() {
	while (true) {
		wait(mutex);
		// write something;
		signal(mutex);
	}
} 

void reader() {
	while (true) {
		if (readcount == 0) {
		wait(mutex);
		readcount++;
		}
		else {
			readcount++;
		}
		// read something
		readcount--;
		if (readcount == 0) {
			signal(mutex);
		}
	} 
}

   improvement: This version sets the variable readcount to control the number of readers. It is limited only when readcount is 0. In the reader, whether readcount is 0 or not, readcount + + is executed. So simplify the code and write the following version

  version 2.1:

semaphore mutex = 1;
int readcount = 0;
void writer() {
	while (true) {
		wait(mutex);
		// write something;
		signal(mutex);
	}
} 

void reader() {
	while (true) {
		if (readcount == 0) {
			wait(mutex);
		}
		readcount++;
		// read something
		readcount--;
		if (readcount == 0) {
			signal(mutex);
		}
	}
}

  there is still a problem in this version: readcount is a global variable, and the value can be changed in many places. To avoid confusion, increase semaphores and limit readcount (right? What's more explicit?)

  version 3.0:

semaphore wmutex = 1;
semaphore rmutex = 1; 
int readcount = 0;
void writer() {
	while (true) {
		wait(wmutex);
		// write something;
		signal(wmutex);
	}
} 

void reader() {
	while (1) {
		if (readcount == 0) {
			wait(wmutex);
		}
		wait(rmutex);
		readcount++;
		signal(rmutex);
		// read something
		wait(rmutex);
		readcount--;
		signal(rmutex);
		if (readcount == 0) {
			signal(wmutex);
		}
	}
}

  improvement: increase the semaphore rmutex to limit the readcount
   version 3.0 solves the confusion of readcount. However, if there are multiple reader processes, assuming that each reader process only executes after wait(wmutex), the readcount will always be 0, while wmutex continues to decrease, which will cause problems.

  version 4.0:

semaphore wmutex = 1;
semaphore rmutex = 1; 
int readcount = 0;
void writer() {
	while (true) {
		wait(wmutex);
		// write something;
		signal(wmutex);
	}
} 

void reader() {
	while (1) {
		wait(rmutex);
		if (readcount == 0) {
			wait(wmutex);
		}
		readcount++;
		signal(rmutex);
		// read something
		wait(rmutex);
		readcount--;
		if (readcount == 0) {
			signal(wmutex);
		}	
		signal(rmutex);
	}
}

  improvement: by advancing rmutex, the judgment of readcount and the operation of readcount become a whole. The problem of continuous self reduction of wmutex is solved.
  but there is still a problem with this version: for the writer, only after the reaccount is reset to zero can the signal(wmutex) and then execute the write process. If there are too many reader processes, the readcount is always not 0, and the writing process never gets resources. This problem is called "the writer starves to death".

   version 5.0 (solve the problem of writer starvation)

  improvement: increase the read-write priority and set the write priority higher. Add semaphore w for control. The specific codes are as follows:

semaphore wmutex = 1;
semaphore rmutex = 1; 
w = 1 //Writer read first 
int readcount = 0;
void writer() {
	while (true) {
		wait(w);
		wait(wmutex);
		// write something;
		signal(wmutex);
		signal(w);
	}
} 

void reader() {
	while (1) {
		wait(w);
		wait(rmutex);
		if (readcount == 0) {
			wait(wmutex);
		}
		readcount++;
		signal(rmutex);
		signal(w);
		// read something
		wait(rmutex);
		readcount--;
		if (readcount == 0) {
			signal(wmutex);
		}	
		signal(rmutex);
	}
}

   sample analysis: assume that the arrival order of the process is as follows: reader A, writer B and reader C
   reader a is the first to enter and occupy the w, rmutex semaphore. When B arrives, it is blocked because w is not released. A can be executed all the way to signal(w). After releasing w, B takes possession of w, but waits at wait(wmutex). When C arrives, it waits at wait(w) because w is occupied until a is executed and wmutex is released because readcount is 0. B gets wmutex to write. After writing, release w, and C can read. Completing B takes precedence over C, which solves the problem of writer starvation.

  the dining problem of philosophers

  the problem description is shown in the figure below:

   version 1.0 (all take one side: deadlock)

semaphore chopstick[5] = {1,1,1,1,1};
void process(int i) {
	while (true) {
		wait(chopstick[i]);
		wait(chopstick[(i+1)%5]);
		eat;
		signal(chopstick[i]);
		siganl(chopstick[(i+1)%5]);
	}
} 

  the idea of this version of code is to take one side first and then the other. When the meal is over, put down the chopsticks in the same order. If there are five processes at the same time, they all execute wait (chop stick [i]), then each chopstick is occupied, and all processes will stop at wait (chop stick [(I + 1)% 5]). Cause deadlock.

  version 2.0:

  for this problem, the main idea is to enable at least one philosopher to get two chopsticks. When he finishes eating, he can give chopsticks to others, that is, he can successfully turn them around. There are several solutions, which are described in turn below:

  scheme 1: limit the number of diners

  idea: by setting the number of semaphores to 4, it is stipulated that only four philosophers can eat. This will ensure that at least one philosopher can have two chopsticks and give them to others when the philosopher is finished, so as to ensure the orderly operation of the process. The code is as follows:

semaphore chopstick[5] = {1,1,1,1,1};
semaphore num_mutex = 4；
while(wait(num_mutex))
{
	wait(chopstick[i]);
	wait(chopstick[(i+1)%5]);
 	// eat()
	
	signal(chopstick[i]);
	signal(chopstick[(i+1)%5]);
	signal(num_mutex);
}

   scheme 2: use AND semaphore to eat when someone gets two chopsticks at the same time. The code is as follows:

semaphore chopstick[5] = {1,1,1,1,1}
do{
···
	// think()
	swait(chopstick[(i+1)%5],chopstick[i]);


	//eat()
	signal(chopstick[(i+1)%5],chopstick[i]);

}while(true)

   scheme 3: processes are distinguished according to process parity. It is stipulated that odd processes take the left chopsticks first and then the right chopsticks, and even processes take the right chopsticks first and then the left chopsticks. In this way, 1 and 2 will compete for No. 1 chopsticks, 3 and 4 will compete for No. 3 chopsticks, and 5 will get No. 5 chopsticks. When turning to the other, there will always be a process that gets two to complete the operation. Draw a picture like this:

   the code is as follows:

semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int i)
{
	while(true)
	{
		think();
		if(i%2 == 0) //Even philosophers, right first and then left.
		{
			wait (chopstick[(i + 1)%5]) ;
			wait (chopstick[i]) ;
			eat();
			signal (chopstick[(i + 1)%5]) ;
			signal (chopstick[i]) ;
		}
		else //Odd philosophers, left first and then right.
		{
			wait (chopstick[i]) ;
			wait (chopstick[(i + 1)%5]) ;
			eat();
			signal (chopstick[i]) ;
			signal (chopstick[(i + 1)%5]) ;
		}
	}
}

  reference blog: Solutions to the dining problem of philosophers (three kinds)_ jdq8576 blog - CSDN blog_ Three codes for philosophers' dining problems

   there is a problem that has been bothering me: what is the routine of PV operation? How can I analyze a problem?

  in fact, up to now, I don't have a definite answer, only a little understanding.
  first of all, we should analyze the process, determine how many processes there are, and what is the relationship between processes?
  the second step is to determine what resources are?
  the third step is to determine the number of semaphores. This is very vague. You can only try one by one, one can't, two can't, and so on.
   in addition, there are still few questions to be done at present. If you have clearer ideas in the future, you will add them again!