Classical synchronization problem

1. Classic synchronization problem

Process synchronization ： This enables concurrent processes to advance in an orderly manner , Solve the uncertainty caused by disordered promotion in asynchrony （ There is a sequence of execution ）
Processes are mutually exclusive ： When a process accesses or operates on a resource , Other processes cannot operate on this resource （ I operate you cannot ）

1.1 producer - Consumer issues

There is a queue （ buffer ）, The producer is at the head of the queue , The consumer is at the end of the queue , Producers put things at the head of the team （ data ）, Consumers take things from the end of the line （ data ）
The following figure comes from 《 Half an hour cartoon computer 》

If the queue is empty , Consumers have to wait , Wait until the producer puts in something before telling the consumer to take it （ Queue is not full , Producers produce ）
If the queue is full , The producer has to wait , Wait until the consumer takes something away before telling the producer to put it away （ The queue is empty , Consumer consumption ）
There is a sequence between putting data and fetching data , That is, there is synchronization

Be careful ：
1. Because buffers are critical resources , Both cannot operate queues at the same time , So you need a mutex （mutex clock）
2. The thread also has to notify another thread when the above conditions are met

The mutex ： A thread attempts to lock a resource before operating on it , Operate the resource after locking successfully , Unlock after operation , That is, only one thread can hold the lock at a time

The following figure comes from 《 Half an hour cartoon computer 》


A producer , A consumer

semaphore muxtex=1;		// Mutex semaphore 
semaphore empty=n;		// Synchronous semaphore , The initial state is n Empty buffer units 
semaphore full=0;		// Synchronous semaphore , The initial state is 0 Full buffer units 
producer(){
    		// Producer process 
	while(1){
    
		produce data;
		P(empty);	// Request an empty buffer unit 
		P(mutex);	// Enter the mutex on the critical area 
		add data into buffer;	// Fill the buffer with data , The buffer unit becomes a full buffer unit 
		V(mutex);	// Exit the critical area and release the mutex 
		V(full);	// Release the full buffer unit 
	}
}
consumer(){
    		// Consumer process 
	while(1){
    
		P(full);	// Request a full buffer unit 
		P(mutex);	// Enter the mutex on the critical area 
		remove data from buffer;	// Fetch data from buffer , The buffer unit becomes an empty buffer unit 
		V(mutex);	// Exit the critical area and release the mutex 
		V(empty);	// Release the empty buffer unit 
	}
}

Suppose a situation ： Buffer is full （empty=0,full=n）, If you exchange two in the production function P Sequence of operations , Then there will be a deadlock

P(mutex);	// Top mutex 
P(empty);	// Request empty buffer unit , But there are no empty buffer units , So the process will wait here , You cannot release the mutex , Caused a deadlock problem 

So we need Sync first , Post mutual exclusion To avoid the deadlock problem in this case

1.2 readers - Write the questions

Readers can only read data , Can't modify data
The writer can read the data , Data can be modified

semaphore rw=1;	// Realize mutually exclusive access to shared files 
writer(){
    	// Writer process 
	while(1){
    
		P(rw);	// Request operation share file 
		write(); // Writing documents 
		V(rw);	// Release shared files 
	}
}
reader1(){
    	// The reader process 1
	while(1){
    
		P(rw);	// Request access to shared files 
		read(); // Reading documents 
		V(rw);	// Release shared files 
	}
reader2(){
    	// The reader process 2
	while(1){
    
		P(rw);	// Request access to shared files 
		read(); // Reading documents 
		V(rw);	// Release shared files 
	}	
}

In the above case , If there are multiple readers calling at the same time reader To read the file , First of all, such behavior is allowed , But it was locked before reading , Multiple readers are mutually exclusive , Therefore, multiple readers cannot read files at the same time , So how can multiple readers read files at the same time ？ We introduce a variable count Record the number of readers reading the file , And introduce mutually exclusive semaphores countmutex To make processes mutually exclusive count Variable

semaphore rw=1;	// Realize mutually exclusive access to shared files 
int count=0;	// Number of processes currently accessing shared files , The initial value is 0
semaphore countmutex=1;	// Guarantee right count Mutually exclusive access to variables 
writer(){
    	// Writer process 
	while(1){
    
		P(rw);	// Request operation share file 
		write(); // Writing documents 
		V(rw);	// Release shared files 
	}
}
reader1(){
    	// The reader process 1
	while(1){
    
		P(countmutex);
		//if(count==0) You can determine whether the current read process is the first read process or the last read process 
		if(count == 0)	// A reader process calls reader, Check count by 0, Indicates that no process is currently accessing the shared file 
			P(rw);	// Request access to shared files 
		count++;	// The previous process has requested to read the file , Therefore, the current number of processes accessing shared files is increased by 1
		V(countmutex);
		read();	 	// The process reads the file 
		P(countmutex);
		count--;	// The previous process has finished reading , Therefore, the current number of processes accessing shared files decreases 1
		if(count == 0)	// Determine whether there are still processes reading files , If meet , It means there is no , You can release the lock 
			V(rw);	// Release the lock to access the shared file 
		V(countmutex);
	}
reader2(){
    	// The reader process 2
	while(1){
    
		P(countmutex);
		//if(count==0) You can determine whether the current read process is the first read process or the last read process 
		if(count == 0)	// A reader process calls reader, Check count by 0, Indicates that no process is currently accessing the shared file 
			P(rw);	// Request access to shared files 
		count++;	// The previous process has requested to read the file , Therefore, the current number of processes accessing shared files is increased by 1
		V(countmutex);
		read();	 	// The process reads the file 
		P(countmutex);
		count--;	// The previous process has finished reading , Therefore, the current number of processes accessing shared files decreases 1
		if(count == 0)	// Determine whether there are still processes reading files , If meet , It means there is no , You can release the lock 
			V(rw);	// Release the lock to access the shared file 
		V(countmutex);
	}
}

Although the above implements the operation of reading shared files by multiple readers at the same time , However, there is a hidden danger in this situation, that is, if multiple readers have been reading the shared files , At this time, the writer process has been blocking and waiting , This may cause the writer process to starve , In order to solve the problem that the writing process may starve , We need to implement write first
We introduce mutually exclusive semaphores w To achieve write first
( In fact, it is not really write first , A read-write fairness policy is required to achieve true write first )

semaphore rw=1;	// Ensure that readers and writers are mutually exclusive to access files 
int count =0;	// Number of processes reading files , Initially, no process was reading file 
semaphore mutex=1;	// The process is right count Variables for mutually exclusive access 
semaphore w=1;	// Used to implement write first . Prevent multiple reading processes from reading files , The writer process starved to death due to blocking and waiting too long 
writer(){
    	// Writer process 1
	while(1){
    
		P(w);	// Lock the write process 
		P(rw);	// Lock the write file 
		 Writing documents 
		V(rw);	// Unlock write file 
		V(w);	// Unlock the write process 
	}
}
reader1(){
    	// The reader process 1
	while(1){
    
		P(w);	
		P(mutex);	// The variable count Lock 
		if(count==0)	// Check that no process is currently reading the file 
			P(rw);		// If there is a writer , Block the writer 
		count++;		// Number of processes currently reading files +1
		V(mutex);	// The variable count Unlock 
		V(w);			
		 Reading documents 
		P(mutex);	// The variable count Lock 
		count--;	// Last process read completed , Number of processes currently reading files -1
		if(count==0)	// Check that no process is currently reading the file 
			V(rw);		// Unlock the read file 
		V(mutex);	// The variable count Unlock 
	}
reader2(){
    	// The reader process 2
	while(1){
    
		P(w);	
		P(mutex);	// The variable count Lock 
		if(count==0)	// Check that no process is currently reading the file 
			P(rw);		// If there is a writer , Block the writer 
		count++;		// Number of processes currently reading files +1
		V(mutex);	// The variable count Unlock 
		V(w);			
		 Reading documents 
		P(mutex);	// The variable count Lock 
		count--;	// Last process read completed , Number of processes currently reading files -1
		if(count==0)	// Check that no process is currently reading the file 
			V(rw);		// Unlock the read file 
		V(mutex);	// The variable count Unlock 
	}
}

Hypothetical reader 1, Writer 1, readers 2 Concurrent execution
Writer 1 In the reader 2 Pre execution , Realize write first , It avoids the starvation of the writing process

1.3 The question of philosophers eating

There is... On one table 5 A philosopher (5 A process ),5 Chopsticks (5 A critical resource ), Only when philosophers pick up their left and right chopsticks at the same time can they eat ( Access critical resources ), If you can't get it at the same time 2 Chopsticks , Then philosophers think ( Process blocking wait )

The following figure is from the Wangdao postgraduate entrance examination operating system

hypothesis 5 Two philosophers picked up their left chopsticks at the same time , Every philosopher is waiting for the philosopher on the right to put down his chopsticks , And will not take the initiative to put down the chopsticks in their hands , So there's a deadlock

How to solve the deadlock problem ?
Scheme 1 : 4 Two philosophers picked up the chopsticks on the left side at the same time ,3 No. 1 also picked up the chopsticks on the right , After eating , put down 2 Chopsticks ,2 No. pick up 3 Put down the chopsticks to eat
stay 3 While the No. 1 philosopher was eating ,0 Number ,1 Number ,2 Number is occupied 1 Resources are blocking and waiting at the same time ( Some waste resources )

semaphore chopstick[5]={
    1,1,1,1,1}; // Semaphore ( Critical resource quantity ,1 Chopsticks stand for 1 A critical resource )
Pi(){
    	// The first i A philosopher process 
	do{
    
		P(chopstick[i]);	// Take the left chopsticks 
		P(chopstick[(i+1)%5]);	// Take the right chopsticks 
		eat;
		V(chopstick[i]);	// Put back the left chopsticks 
		V(chopstick[(i+1)%5]);	// Put back the right chopsticks 
		think;
	}while(1);
}

Option two : Odd numbered philosophers take the chopsticks on the left first , Then take the chopsticks on the right , Even numbered philosophers take the chopsticks on the right first , Then take the chopsticks on the left
If two philosophers vie for one of the chopsticks , Surely one of the philosophers will vie for it , Another philosopher would be empty handed ( Do not use resources to block and wait )

Option three : Only when the chopsticks on the left and right sides of the philosopher are available , Just grab two chopsticks to eat

Consider whether you can pick it up at once 2 Chopsticks , Then make a decision , This will avoid deadlock , This is the essence of the dining problem of philosophers

semaphore chopstick[5]={
    1,1,1,1,1};	// Semaphore ( Critical resource quantity ,1 Chopsticks stand for 1 A critical resource )
semaphore mutex = 1;	// Mutex semaphore , Mutually exclusive chopsticks 
Pi(){
    	// The first i A philosopher process 
	do{
    
		P(mutex);	// locked 
		P(chopstick[i]);	// Take the left chopsticks 
		P(chopstick[(i+1)%5]);	// Take the right chopsticks 
		V(mutex);	// Unlock 
		eat;
		V(chopstick[i]);	// Put back the left chopsticks 
		V(chopstick[(i+1)%5]);	// Put back the right chopsticks 
		think;
	}while(1);
}

1.4 Smoker problem

Essential for ： Single producer — The problem of multiple consumers

The supplier provides three materials without limit ： paper 、 glue 、 Tobacco , And only two of them are provided at a time
Smokers have only one material in their hands , Only when there are two other materials , Then you can roll out cigarettes , And smoke , Tell the supplier after smoking , The supplier continues to supply materials and puts them on the table

Mutual exclusion ：
Three smoker processes are mutually exclusive to access the table （ Capacity of 1 The buffer ）
Synchronous relationship ：
There are combinations on the table 1, Then the first smoker takes away
There are combinations on the table 2, Then the second smoker takes away
There are combinations on the table 3, Then the third smoker takes away
A smoker sends a signal to the supplier after smoking , Then the supplier continues to supply materials and puts them on the table

The following figure is from the Wangdao postgraduate entrance examination operating system

The following figure is from the Wangdao postgraduate entrance examination operating system

int num=0;		// It is used to realize that three smokers smoke in turn 
semaphore offer1=0;
semaphore offer2=0;
semaphore offer3=0;
semaphore finish=0;
provider(){
    
	while(1){
    
		num++;	
		num=num%3;	// Make smokers 0,1,2 Take turns getting materials 
		if(num==0)
			V(offer1);	// Release the combination 1 material ： paper + glue 
		else if(num==1)
			V(offer2);	// Release the combination 2 material ： Tobacco + glue 
		else
			V(offer3);	// Release the combination 3 material ： Tobacco + paper 
	 Put the material on the table 
	P(finish);	// Receive completion signals from smokers 
	}
}

smoker1(){
    
	while(1){
    
		P(offer1);	// smoker 1 Take away the combination 1 material 
		 Smoke after making cigarettes with three materials 
		V(finish);	// Notify the supplier , Smoking completed 
	}
}

smoker2(){
    
	while(1){
    
		P(offer2);	// smoker 2 Take away the combination 2 material 
		 Smoke after making cigarettes with three materials 
		V(finish);	// Notify the supplier , Smoking completed 
	}
}

smoker3(){
    
	while(1){
    
		P(offer3);	// smoker 3 Take away the combination 3 material 
		 Smoke after making cigarettes with three materials 
		V(finish);	// Notify the supplier , Smoking completed 
	}
}