12. Process synchronization and semaphore

【README】

1. The content of this paper is summarized from B standing 《 operating system - Li Zhijun, teacher of Harbin Institute of technology 》, The content is great , Wall crack recommendation ;

2. Process synchronization ： Let the cooperation between processes become reasonable and orderly ;

3. adopt Semaphore To achieve process synchronization ;

4. The operating system realizes process cooperation with semaphores , The process goes on and on ;（ When does the process stop , Where to stop is particularly important ）

---

【1】 Process cooperation ： Multiple processes work together to accomplish a task

 【 example 1】 Example of driver and conductor

The driver	conductor
While(true) {    Start the vehicle ;// Wait for the signal 1    The normal operation ;    Stop at the station ;// Sending signal 2 }	While(true) {     close ;// Sending signal 1    Sell ticket ;    Open door ; // Wait for the signal 2 }

【 example 2】 Producer consumer

producer	consumer
Block until  counter It's not equal to BUFFER_SIZE; After production data ,counter Add 1, Similar to sending signals to consumers ;	Block until counter It's not equal to 0; After consumption data ,counter reduce 1, Similar to sending signals to producers ;

---

 【2】 Process synchronization

Process synchronization definitions ： We need to let the process go and stop , Ensure the reasonable and orderly multi process cooperation ;

---

 【3】 Semaphore semantics

1） Signaling alone cannot solve all the problems ;

• Signals can only indicate Yes perhaps No, ; Introduce semaphores to express richer information ;

2） Problem description ：

• When counter be equal to BUFFER_SIZE when , producer 1 sleep ;
• When counter be equal to BUFFER_SIZE when , producer 2 sleep ;
• next , Consumers consume a piece of data ,counter reduce 1;
• here counter reduce 1 After equal to BUFFER_SIZE     reduce 1, So consumers will call wakeup Wake up producers 1;
• next , Consumer recycling consumption in addition 1 Data ,counter reduce 1;

What happened ：

• here counter reduce 1 After equal to BUFFER_SIZE reduce 2 （ Because this is the second 2 Secondary consumption ）, Because it 's not enough counter==BUFFER_SIZE-1 Conditions , So consumers will not wake up producers 2;
• obviously ,counter semantics Not enough to wake up all producers , So the semaphore is introduced ;
• （counter The number of free buffers is recorded , The number of sleep producers cannot be recorded , So according to counter Semantics cannot wake up all producers of sleep ）

3） Semaphore
Semaphores not only need to record sleep and wakeup , You also need to record the number of currently blocked producers and other information ;

 4） The semaphore starts to work

step	Producer and consumer execution details	Semaphore sem value
1	Buffer full , producer P1 perform , P1 sleep , The semaphore is reduced 1; Then the semaphore is -1;（ Semaphore -1 Express 1 Producers sleep ）	-1
2	producer P2 perform , P2 sleep , The semaphore is reduced 1; Then the semaphore is -2（ Express 2 Producers sleep ）	-2
3	Consumer execution 1 Secondary cycle , wakeup Wake up the P1 after , Semaphore plus 1 obtain -1;（ Express 1 Producers sleep ）	-1
4	Consumers will execute 1 Secondary cycle , wakeup Wake up the P2, Semaphore plus 1 obtain 0;（ No producer sleeps ）	0
5	The consumer is performing a cycle ; Semaphore plus 1;（ Express 1 Buffer space available ）	1
6	producer P3 perform , The semaphore is reduced 1;	0

Semaphore sem Value means ：

• -2： Yes 2 Producers are blocking , Or owe the producer queue 2 Unit buffer space ;
• -1： Yes 1 Producers are blocking , Or owe the producer queue 1 Unit buffer space ;
• 0： No producer blocking , The normal operation ;
• 1： It means that there is still 1 Units of available buffer space ;
• 2： It means that there is still 2 Units of available buffer space ;

【 Summary 】

• Next , Producers and consumers It can be based on   Semaphore sem  To determine process synchronization , Or determine the reasonable and orderly implementation of multiple process cooperation ;

5） Semaphore based process cooperation
Multiple processes work together to accomplish one thing , Multiple processes are executing , The order of implementation should be reasonable and orderly ;
In particular , After a certain degree of implementation , The process judges whether to stop and wait according to the semaphore ;

• 5.1） producer ： If the semaphore is equal to 0 Or negative value , Then the producer process waits , And the semaphore decreases 1;
• 5.2） consumer ： If semaphore equals negative value , Then the consumer wakes up a producer process , And the semaphore adds 1;
• If the semaphore is equal to 0, Then the consumer performs normally , And the semaphore adds 1;

---

【4】 Semaphore implementation

1） Semaphore definition ： A special integer variable , Quantity is used to record , Signals are used to determine whether you sleep sleep And wake up wakeup;
2） Semaphore code

//  Semaphore code 
struct semaphore() 
{
	//  Record the number of resources 
	int value ; 
	//  Process blocking queue （ Record the process waiting on this semaphore ） 
	PCB *queue;  
}

//  producer ： Consumption resources （ Here, the consumption of resources refers to the consumption of a free buffer by producers , Or an array item ）
P (semaphore s) 
{
	s.value--; //  Consumption resources  
	if (s.value < 0) {
		sleep(s.queue);  //  Current producer process sleep  
	}
}

//  consumer ： Generate resources  （ Generating resources here refers to the consumer releasing a free buffer , Or an array item ）
V (semaphore s)
{
	s.value++; //  Release resources 
	if (s.value <=0 ) {
		wakeup(s.queue);  //  Consumers wake up the producer process of sleep  
	}
}

 【 Add 】 In Dutch

• P Express proberen, namely test Test means , The producers ;
• V Express verhogen, namely increment, Increasing resources means , The consumer ;

---

【5】 Use semaphores to solve the problems of producers and consumers

 1） Semaphore solves the source code of producer consumer problems

• The following source code has 3 A semaphore
  • full： The number of data or contents in the cache , Or the number of buffers occupied ;
  • empty： Number of free buffers ;
  • mutex： Mutex semaphore , At the same time, only 1 Processes enter code ;

// 1  Define shared buffer with file  
int fd = open("buffer.txt");
write(fd, 0, sizeof(in)); //  Write data to in Location  
read(fd, 0, sizeof(out)); //  from out Location read data  

// 2  Definition and initialization of semaphores  
semaphore full = 0; //  Represents the data produced in the buffer （ Content ） Number , Or the number of buffers used ; 
semaphore empty = BUFFER_SIZE; //  Indicates the number of free buffers  
semaphore mutex = 1; //  Mutex semaphore , At the same time, there can only be 1 A process goes in ;

// 3  producer  
Producer(item) {
	P(empty); //  The producer tests first empty Whether the semaphore is 0（ by 0 Indicates that there is no free buffer ）
	P(mutex); 
	//  Read in, hold item Write to in Location  （ Production operation ）
	V(mutex); 
	V(full); //  Add data （ Content ） Number  
}

// 4  consumer  
Consumer() {
	P(full);  //  Consumers first test whether there is content in the buffer , If not, it will block 
	P(mutex); //  Determine whether the file can be accessed ,mutex It's a mutex semaphore , At the same time, only 1 Processes can access files （mutex reduce 1,  obtain mutex Semaphore or lock ）
	//  Read out, From file out The position is read to item, Print item （ Consumer operations ）
	V(mutex); // mutex Add 1, Release mutex  Semaphore 
	V(empty);//  After consumption, consumers , Increase the number of free buffers  
}