1. Problem description
There is a box on the bicycle production line, in which there are N positions (N ≥ 3). Each position can store a frame or a wheel, and there are three workers. Their activities are:
2. Problem analysis (including knowledge points involved, restriction relationship analysis, problem solving ideas, etc.)
According to the meaning analysis of the topic, the worker 1, worker 2 and worker 3 described in the topic constitute the relationship between producer and consumer. There is a synchronous relationship between producer and consumer problems. The knowledge points involved include semaphores, PV primitives, process synchronization, deadlock problems, etc.
Problem solving ideas:
The cooperation of three workers is realized by semaphore and PV operation. Firstly, the deadlock problem is not considered. Worker 1 and worker 3 and worker 2 and worker 3 constitute the producer consumer relationship. These two pairs of production consumer relationships are connected through a common buffer - box. From the perspective of resources, the empty position in the box is equivalent to the resources of worker 1 and worker 2, while the frame and wheel are equivalent to the resources of worker 3. Define three semaphores empty (number of empty positions), frame (number of frames) and wheel (number of wheels) to realize this synchronization relationship, and analyze what problems will occur:
semaphore empty = N;//Number of empty positions
semaphore frame = 0;//Number of frames
semaphore wheel = 0;//Number of wheels
do{ //Worker 1 activity
P(empty);
Machining a frame;
Put the frame into the box;
V(frame);
}while(1)
do{ //Worker 2 activities
P(empty);
Machining a wheel;
Put the wheel in the box;
V(wheel);
}while(1)
do{ //Worker 3 activities
P(frame);
P(wheel);
P(wheel);
Take a frame from the box;
Take a frame from the box;
Assemble a car;
V(empty);
V(empty);
V(empty);
}while(1)
It is easy to see from the analysis that when the processing speed of worker 1 is fast, the hollow position of the box may be completely occupied by the frame or only one position for storing the wheels. At this time, when worker 3 takes two wheels at the same time, it will not be available, and worker 2 cannot put the newly processed wheels into the box; when the processing speed of worker 2 is fast, the hollow position of the box may be completely occupied by the wheels, and when worker 3 In order to prevent deadlock, the number of frames in the box shall not exceed N-2 and the number of wheels shall not exceed N-1. These limits can add two other semaphores maxframe and maxwheel To solve the deadlock problem, the solution is as follows.
3. Solution (including introduction of tools used, scheme flow chart, scheme pseudo code, etc.)
The pseudo code of the scheme is as follows:
semaphore empty = N;//Number of empty positions
semaphore maxframe = N-2;//Maximum number of frames in the box
semaphore maxwheel = N-1;//Maximum number of wheels in the box
semaphore frame = 0;//Number of frames
semaphore wheel = 0;//Number of wheels
do{ //Worker 1 activity
P(maxframe);
P(empty);
Machining a frame;
Put the frame into the box;
V(frame);
}while(1)
do{ //Worker 2 activities
P(maxwheel);
P(empty);
Machining a wheel;
Put the wheel in the box;
V(wheel);
}while(1)
do{ //Worker 3 activities
P(frame);
P(wheel);
P(wheel);
Take a frame from the box;
Take a frame from the box;
Assemble a car;
V(maxframe);
V(maxwheel);
V(maxwheel);
V(empty);
V(empty);
V(empty);
}while(1)
Tool introduction:
The tool used is jBACI. The toolkit has its own compiler and interpreter. The source code is compiled by the compiler and then interpreted and executed. Similar to java, the tool can be run directly under Windows 10 system. The program is written in ". cm" and ". pm" formats, ". cm" The format is similar to that of C language and C + +. There are some built-in graphic functions. For details, you can learn to use them by referring to the instructions in the docs folder and the examples in the examples folder. Before use, you need to change the internal configuration file config.cfg file. The modification content is as follows:
SOURCE_DIRECTORY=.\examples\
PASCAL_COMPILER=.\bin\bapas.exe
C_COMPILER=.\bin\bacc.exe
(download address: https://github.com/motib/jbaci )
After the code is written, you need to click Compile to Compile before you can click Run to execute. After entering the execution page, you can see the code execution area, console, global variable area, etc. you can Add breakpoints to the code, and step-by-step execution. After you click Go to execute, you can also see the detailed execution of each process and the numerical changes of each variable.
In short, jBACI is a very friendly and practical tool for learning the relationship between process synchronization and mutual exclusion constraints of computer operating system.
The schematic flow chart of the scheme is as follows:
The specific implementation code of the scheme is as follows:
const int ValueOfCars = 50;//Set the expected number of production vehicles
int sumframe = 0;//Used to count the number of production frames
int sumwheel = 0;//Used to count the number of production wheels
int sumcar = 0;//Used to count the number of production vehicles
semaphore empty = 6;//Semaphore: for easy program implementation, set position N=6
semaphore maxframe = 4;//Semaphore: in order to prevent deadlock, the maximum number of frames that can be accommodated in the box
semaphore maxwheel = 5;//Semaphore: the maximum number of wheels that can be accommodated in the box to prevent deadlock
semaphore frame = 0;//Semaphore: initial value of frame number = 0
semaphore wheel = 0;//Semaphore: number of wheels initial value = 0
void worker1() {
while (sumframe < ValueOfCars) {//To prevent deadlock, give worker 1 a stop condition
wait(maxframe);
wait(empty);
sumframe = sumframe + 1;
cout << "Worker1 is working " << endl;
signal(frame);
}
cout << "Worker1 have finished work " << endl;//Worker 1 finished work
}
void worker2() {
while (sumwheel < 2*ValueOfCars) {//To prevent deadlock, give worker 2 a stop condition
wait(maxwheel);
wait(empty);
sumwheel = sumwheel + 1;
cout << "Worker2 is working "<< endl;
signal(wheel);
}
cout << "Worker2 have finished work " << endl;//Worker 2 finish work
}
void worker3() {
while (sumcar < ValueOfCars) {//To prevent deadlock, give worker 3 a stop condition
wait(frame);
wait(wheel);
wait(wheel);
sumcar = sumcar + 1;
cout << "Worker3 is working "<< endl;
signal(maxframe);
signal(maxwheel);
signal(maxwheel);
signal(empty);
signal(empty);
signal(empty);
}
cout << "Worker3 have finished work " << endl;//Worker 3 finish work
}
void main() {
cobegin {
worker1();
worker2();
worker3();
}
cout << "Sumframe = " << sumframe << endl;//Output the total number of frames produced
cout << "Sumwheel = " << sumwheel << endl;//Output total number of wheels produced
cout << "Sumcar = " << sumcar << endl;//Output total number of vehicles produced
}
4. Analysis of experimental results (including result display, result cause analysis, etc.)
Result display:
The results on the left show that worker 1 stopped working first, worker 2 followed, and worker 3 finally completed the work. The results on the right show that the number of frames and wheels in the box is 0, the number of empty spaces in the box is reset to 6, the maximum number of frames and wheels that can be accommodated maxwheel are reset, and the number of frames, wheels and vehicles produced just meet the set expectations, It does not exceed or decrease, and there is no deadlock warning of "a deadlock occurred" during program execution.
Result cause analysis:
The result is in line with the expectation and successfully avoids the deadlock. First, two semaphores maxframe and maxwheel are added to prevent the deadlock of workers 1 or 2 processing too fast in production, resulting in the inability to gather the necessary parts of a vehicle in the box. Second, each worker is given one by setting the expected value of production vehicle quantity The work completion condition avoids the deadlock that when one of workers 1 or 2 finishes the work first, worker 3 does not finish the work but waits all the time due to the lack of a part, and the other worker also waits for worker 3 to take away the parts in the box before continuing processing.