Detailed explanation of classic process synchronization problems

2.5 Classic process synchronization problem （ a key ！！！）

• One 、 producer - Consumer issues
• Two 、 The question of philosophers eating
• 3、 ... and 、 readers - Write the questions

One 、 producer - Consumer issues

There are several processes ？

What mode exists ？

For the producer - Consumer issues , There are two processes , They are producer process and consumer process

buffer It is a public resource shared by producers and consumers , It's a critical resource , So it is mutually exclusive sharing buffer.

1、 Use recording semaphore to solve the problem of producer - Consumer issues

Mutex semaphores can be used mutex Realize the mutual exclusive use of buffer pool by various processes ;
Using semaphores empty and full It represents the number of empty buffer pools and full buffer pools respectively

Program realization

about producer In terms of procedure ,wait（empty） See if there is still storage space in the buffer ,wait（mutex） Is used to apply for buffer resources

about consumer In terms of procedure ,wait（full） See when there are goods in the buffer ,wait（mutex） Is used to apply for buffer resources

When the buffer is full ,empty by 0,full by n. At this time, if you execute wait（mutex）, Re execution wait（empty）, It will cause producers to apply for buffer resources , But the buffer has no storage space to store goods ; And for the consumer process , If you execute wait（mutex）, Re execution wait（full）, It will lead to , Consumer cannot apply for buffer resources , At this time, even if there are goods in the buffer , Still unable to take out the goods for consumption . Locked in a deadlock .

Producers are waiting for consumers to consume , Consumers are waiting for producers to release mutex.（ Deadlock situation ）

There is no sequence requirement when releasing resources from the exit area ！

2、 utilize AND Type semaphore solution producer - Consumer issues

One time application and release of resource semaphores and mutually exclusive semaphores .

Two 、 The question of philosophers eating

1、 Using recorded semaphores to solve the dining problem of philosophers

Program realization

Although the algorithm can ensure that two adjacent people will not eat at the same time , But it may cause deadlock .

Because when five people are hungry at the same time , Everyone will pick up a chopstick on their left , At this time, everyone can't eat with only one chopstick , Therefore, there is no way to release resources , So five people can only wait to starve , Locked in a deadlock .

resolvent ：

• Method 1： No more than four philosophers are allowed to reach for the left chopstick at the same time , Ultimately, at least one philosopher will be able to eat , And release the two chopsticks he used after using them , So that more philosophers can eat .
• Method 2： Only when the philosopher's left and right chopsticks are available , He was allowed to eat with chopsticks .
• Method 3： The odd number philosopher is required to take his left chopstick first , Then go get the chopsticks on the right ; Even philosophers are the opposite .

Method 1： Program realization

Chopsticks are mutually exclusive semaphores

The number of hungry philosophers is a resource semaphore

Method 2： utilize AND Type semaphore mechanism solves the dining problem of philosophers

In the dining problem of philosophers , Each philosopher is required to obtain two critical resources first ( chopsticks ) Before eating . Essentially, AND Synchronization problem .

Method 3： Program realization ：

3、 ... and 、 readers - Write the questions

1、 Use recording semaphores to solve the problem of readers - Write the questions

• Mutex semaphore wmutex： Realization reader And writer Mutual exclusion between processes when reading or writing , Integer variables readcount： Represents the number of processes being read ;
• Because as long as there is one reader Process reading , You are not allowed to writer Process write . therefore , Only when the readcount=0, That is no reader The process is reading ,reader To execute wait operation . if wait（wmutex） Successful operation ,reader The process can read , Accordingly , do readcount+1 operation .
• Empathy , Only when the reader The process is executing readcount reduce 1 After operation, its value is 0 when , To execute signal（wmutex） operation , In order to make write Process write .
  Mutex semaphore rmutex：reader Inter process exclusive access readcount.

about reader process ：

• 1、 Apply first readcount resources , The perform wait（rmutex）
• 2、 If readcount=0, You need to apply again wmutex, The perform wait（wmutex）, And then execute readcount+1, Then release readcount resources , The perform signal（rmutex）.
• 3、 If readcount！=0, Directly readcount+1, Then release readcount resources , The perform signal（rmutex）.
• 4、 Perform read operations
• 5、 apply readcount resources , perform readcount-1
• 6、 If readcount=0, Then release wmutex, The perform signal（wmutex）, Otherwise, release directly rmutex, The perform signal（rmutex）.
  The writing process is a normal application wmutex resources , And then write , Release wmutex, The perform signal（wmutex）.

2、 Use semaphore set mechanism to solve readers - Write the questions

about reader The process and writer process ：

• Every read process , Would be L-1, At most RN A read process to apply for resources
• swait（mx,1,0） Statements act as switches . As long as none writer The process enters write ,mx=1,reader The process can be read . But once there is writer When the process enters write ,mx=0, Then anything reader The process cannot be read .
• swait（mx, 1, 1; L, RN, 0） Statement means only if there is neither writer The process is writing （mx=1）, No reader Process reading （L=RN）,writer The process can enter the critical area to write .