PV operation questions

PV operation knowledge structure

the dining philosophers problem

Problem Description:

Have n (n) ≥ \ge ≥ 3) philosophers sit around a round table, and each philosopher eats and thinks alternately. There is m(m) in the center of the round table ≥ \ge ≥ 1) bowl, with one chopstick between each two philosophers. Every philosopher must take a bowl and chopsticks on both sides before eating. After eating, put the bowl and chopsticks back in place and continue thinking. In order to make as many philosophers eat at the same time as possible and prevent deadlock, please use the P and V operations of semaphores [wait(), signal() operation] to describe the mutual exclusion and synchronization in the above process, and explain the meaning of semaphores and initial values used.

Solution 1: limit the maximum number of people who can access resources

semaphore capacity = n-1;		//Indicates that at most n-1 philosophers can compete for resources
semaphore bowl = m;				//bowl
semaphore chopsticks[n] = {1};	//n chopsticks,
for(int i = 0; i < n; i++)
	chopsticks[i] = 1;			//The number of chopsticks on each side is 1

Process Philosopher()
{
	while(true)
	{
		reflection
		
		P(capacity);			//Up to n-1 people can access the resource
		P(bowl)					//Application bowl
		P(chopsticks[i]);		//Left hand chopsticks
		P(chopsticks[(i+1)%n]	//Right hand chopsticks
		Dry rice
		V(bowl);
		V(chopsticks[i]);
		V(chopsticks[(i+1)%n];
		V(capacity);
		
	}
}

Solution 1 Optimization

The number of bowls m can be used to limit the number of visitors, that is, the semaphore bowl not only acts as a resource, but also limits the number of visitors. It should be noted that the number of bowls must be less than n

semaphore bowl；				//bowl
semaphore chopsticks[n] = {1};	//n chopsticks,
for(int i = 0; i < n; i++)
	chopsticks[i] = 1;			//The number of chopsticks on each side is 1
bowl = min(m,n-1);				//Limit the maximum number of people accessing resources to n-1

Process Philosopher()
{
	while(true)
	{
		reflection
		
		P(bowl);				//Take a bowl
		P(chopsticks[i]);		//Left hand chopsticks
		P(chopsticks[(i+1)%n]	//Right hand chopsticks
		
		Dry rice
		
		V(chopsticks[i]);
		V(chopsticks[(i+1)%n];
		V(bowl);
	}
}

Solution 2: mutually exclusive access to resources (locking)

Book Description: a philosopher is allowed to grab chopsticks only when both left and right chopsticks are available.

Personal understanding: in fact, this strategy is to "lock" the whole process of philosophers applying for resources, that is, when philosophers can only apply for resources mutually exclusive, it ensures that the first philosopher can apply for all resources.

semaphore lock = 1;				//Semaphores used to mutually exclusive request resources
semaphore bowl = m；			//bowl
semaphore chopsticks[n] = {1};	//n chopsticks,
for(int i = 0; i < n; i++)
	chopsticks[i] = 1;			//The number of chopsticks on each side is 1

Process Philosopher()
{
	while(true)
	{
		reflection
		
		P(lock);				//"Lock"
		P(chopsticks[i]);		//Left hand chopsticks
		P(chopsticks[(i+1)%n]	//Right hand chopsticks
		P(bowl);				//Take a bowl
		V(lock);
		
		Dry rice
		
		V(chopsticks[i]);
		V(chopsticks[(i+1)%n];
		V(bowl);
	}
}

Solution two optimization

In the previous solution, if the process scheduling occurs after the processes of philosophers other than the first philosopher execute the application, and after one cycle of concurrent execution, There will be a situation that only the first philosopher has the resources to eat in his hand (at worst), while other philosophers only have a chopstick in his left hand. This is consistent with the requirement of "Let as many philosophers eat at the same time" Inconsistent. Therefore, consider the following optimization. While locking, judge whether philosophers can apply for all resources. If they can, take them. Otherwise, they will not apply.

int n = 10;                         //Number of chopsticks
 int m = 10;                        //Number of bowls
semaphore lck = 1;					//Semaphore of resource
bool chopsticks[n];            		//The status of all chopsticks, false is not taken away
int bowls = 0;                     	//Number of bowls currently allocated
for(int i = 0; i < n; i++)
	chopsticks[i] = false;			//Initialize all chopsticks as not taken away

Progress Philosopher(int i)			//Philosopher i
{
    while (true)
    {
    	//reflection
    	
        P(lck);		//Ensure that only one philosopher is trying to take it at the same time
        if (!chopsticks[i] && !chopsticks[(i + 1) % n] && bowls < m)//Only when you can get all the resources can you apply
        {
            chopsticks[i] = true;           //Take the left chopsticks
            chopsticks[(i + 1) % n] = true; //Take your right chopsticks
            bowls++;                        //Take a bowl
        }
        V(lck);

        //Dry rice

        P(lck);                             //Mutually exclusive access array
        chopsticks[i] = false;              //Put down your left chopsticks
        chopsticks[(i + 1) % n] = false;    //Put down your right chopsticks
        bowls--;                            //Release bowl
        V(lck);
    }
}