preface
Java concurrency is studied for a while, thinking about get some headphones, to force the buckle flipped through, even free (can’t afford to the poor filling member), six problem has to be said, is a universal force, to summarize, here each question given his solution and analysis at that time, attention, was the author of his own way, each question and there are many other ways.
Six multithreading problems
1114. Print in sequence
We provide a class:
public class Foo { public void first() { print("first"); } public void second() { print("second"); } public void third() { print("third"); }}Copy the codeThree different threads A, B, and C will share an instance of Foo.
- One will call
first()methods - One will call
second()methods - One more will be called
third()methods
Design modifications to ensure that the second() method is executed after the first() method and the third() method after the second() method.
Threads A,B, and C may call their respective methods in order C,B, and A, but still output “firstSecondThird” in that order. So you have to write code to control the order of execution of different threads, so that even if C calls third first, it can’t execute before A,B, and B. Therefore, some variables can be considered to represent the completed state of each thread. Only after A is completed, the corresponding state variable will become the state that B can execute. After B is completed, the variable will be updated to make it become the state that C can execute. I wrote the following code:
class Foo {
Object obj = new Object(a); volatile int flag =1;
public Foo() {
}
public void first(Runnable printFirst) throws InterruptedException {
synchronized(obj) {
while(flag ! =1) obj.wait();
printFirst.run();
// Set the next working thread
flag = 2;
obj.notifyAll();
}
}
public void second(Runnable printSecond) throws InterruptedException {
synchronized(obj){
// If the lock is not met, the lock must be removed
while(flag ! =2) obj.wait();
printSecond.run();
// Set the next working thread
flag = 3;
obj.notifyAll();
}
}
public void third(Runnable printThird) throws InterruptedException {
synchronized(obj) {
// If the lock is not met, the lock must be removed
while(flag ! =3) obj.wait(); printThird.run(); }}}Copy the codeFor example, flag is used to indicate whether three threads can execute, initialized to 1. To ensure visibility of write operations, flag is volatile, similarly below. B can be executed only when flag is 2; otherwise, even if B grabs the synchronized lock first, it still needs to call obj.wait() to surrender the lock because the condition of flag is not met. Similarly, C sets flag to the value required by the next thread after the execution of each thread. In this way, You’re done printing in the order you want.
Of course, this problem can also be done with ReentrantLock, with a slight change to the code as follows:
class Foo {
volatile int flag = 1;
ReentrantLock lock = new ReentrantLock();
Condition condition1,condition2,condition3;
public Foo() {
condition1 = lock.newCondition();
condition2 = lock.newCondition();
condition3 = lock.newCondition();
}
public void first(Runnable printFirst) throws InterruptedException {
lock.lock();
try {
while(flag ! =1) {
condition1.await();
}
printFirst.run();
flag = 2;
// call B
condition2.signal();
} finally {
lock.unlock();
}
}
public void second(Runnable printSecond) throws InterruptedException {
lock.lock();
try {
while(flag ! =2) {
condition2.await();
}
printSecond.run();
flag = 3;
// call C
condition3.signal();
} finally {
lock.unlock();
}
}
public void third(Runnable printThird) throws InterruptedException {
lock.lock();
try {
while(flag ! =3) {
condition3.await();
}
printThird.run();
} finally{ lock.unlock(); }}}Copy the codeThe same idea as above is not explained, but different. Synchronized + obj.wait() + obj.NotifyAll () must be called obj.notifyAll() each time. This is because obj.notify() can only wake up one thread at A time. Obj. Wait (); obj. Wait (); obj. To avoid this, only obj.notifyall () is called to wake up all waiting threads. However, this brings up a problem: if both B and C are aroused,C may grab the lock first, and then call obj.wait() to suspend itself, which actually wastes some CPU resources.
ReentrantLock does not have this problem. A lock can correspond to multiple condition variables. After each thread is executed, it can accurately call up the next thread to be executed.
1115. Print FooBar alternately
We provide a class:
class FooBar { public void foo() { for (int i = 0; i < n; i++) { print("foo"); } } public void bar() { for (int i = 0; i < n; i++) { print("bar"); }}}Copy the codeTwo different threads will share one instance of FooBar. One thread will call the foo() method and the other thread will call the bar() method.
Please design the modification program to ensure that “foobar” is printed n times.
If n is input, n foobar structures are output. If one thread prints once, it must stop and let another thread print. Then we can use a flag variable and change it each time a thread is finished. Let another thread work and stop this thread. Since there are only two threads, we can use a Boolean variable as follows:
class FooBar {
private int n;
Object obj = new Object(a);// indicate which thread can work
volatile boolean flag = true;
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized(obj) {
// Control the thread print order
while(! flag) obj.wait(); printFoo.run();// After printing once, flag changes to false, even if the thread grabs the lock first next time, it will only suspend
flag = false;
obj.notifyAll();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized(obj) {
while(flag) obj.wait();
// After printing once, the flag changes to true, even if the thread grabs the lock first next time, it will only suspend
printBar.run();
flag = true; obj.notifyAll(); }}}}Copy the codeA flag variable is used here, and since there are only two threads, the Boolean type can easily solve the problem. Flag is initialized to true, which ensures that the Foo thread prints for the first time. When it prints for the first time, flag immediately changes, Bar threads work, and so on, eventually printing n foobars. At this point, both threads finish their for loops and exit normally without trying to grab the lock. End of program.
There are only two threads in this problem, so multi-condition variables for reentrant locks are of little use. Obj.wait () + obj.notifyall () will do the job.
1116. Print zeros and odd and even numbers
Suppose we have a class like this:
class ZeroEvenOdd { public ZeroEvenOdd(int n) { ... } // Constructor public void zero(printNumber) {... } // print only 0 public void even(printNumber) {... Public void odd(printNumber) {... } // print only odd numbers}Copy the codeThe same ZeroEvenOdd class instance will be passed to three different threads:
- Thread A will call
zero(), it outputs only 0. - Thread B will call
even(), it outputs only even numbers. - Thread C will call
odd(), it outputs only odd numbers.
Each thread has a printNumber method to print an integer. Please modify the code given to output the integer sequence 010203040506… Where the length of the sequence must be 2n.
So this is a problem where you’re given an n and you’re going to print from 1 to n, but every time you print an integer, you have to print a 0, and again, control the order of the three threads. After thread B and thread C finish their work, it is very simple to make the flag variable change to the state of printing 0. The key is that after A prints 0, how to determine whether B or C should be aroused next, how to set the corresponding flag variable? And that’s easy. The first time you print a zero you have to call up C, the next time it’s B, and then you take turns. Let’s set flag = 0 to indicate that thread A can work. Each time thread A finishes working, flag = I % 2 + 1; I is 0 at the beginning, so the value of flag changes alternately between 1 and 2. Flag equals 1 to indicate that C can work, and 2 to indicate that B can work. The code is as follows:
class ZeroEvenOdd {
private int n;
volatile int flag = 0;
Object obj = new Object(a); publicZeroEvenOdd(int n) {
this.n = n;
}
public void zero(IntConsumer printNumber) throws InterruptedException {
for (int i = 0; i < n; ++i) { synchronized (obj) {while(flag ! =0) {
obj.wait();
}
printNumber.accept(0);
// Calculate which thread will work next time
flag = i % 2 + 1;
obj.notifyAll();
}
}
}
public void even(IntConsumer printNumber) throws InterruptedException {
for (int i = 2; i <= n; i +=2) {
synchronized (obj) {
// If you do not meet the condition, you must suspend the lock even if you grab it first
while(flag ! =2) {
obj.wait();
}
printNumber.accept(i);
flag = 0;
obj.notifyAll();
}
}
}
public void odd(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i +=2) {
synchronized (obj) {
// If you do not meet the condition, you must suspend the lock even if you grab it first
while(flag ! =1) {
obj.wait();
}
printNumber.accept(i);
flag = 0; obj.notifyAll(); }}}}Copy the codeOf course, for this kind of collaborative work of three threads or more, we can use the multiple condition variables of reentrant lock to accurately evoke, as well as sequential printing, without further details.
1117. Generated H2O
Now you have two threads, oxygen and hydrogen, and your goal is to organize these two threads to produce water molecules.
There is a barrier that causes each thread to wait until a complete water molecule can be created.
Hydrogen and oxygen threads are given releaseHydrogen and releaseOxygen methods respectively to allow them to break through the barrier.
These threads should break through the barrier in groups of three and three and instantly combine to produce a water molecule.
You have to make sure that the combination of threads needed to produce one water molecule takes place before the next one.
In other words:
- If an oxygen thread reaches the barrier when no hydrogen thread arrives, it must wait until two hydrogen threads arrive.
- If a hydrogen thread reaches the barrier when no other thread arrives, it must wait until one oxygen thread and another hydrogen thread arrive.
Write hydrogen and oxygen thread synchronization code that meets these constraints.
The input use case for this problem is of the form “OOHHHH”, which I understand is that the total length of the input string is 3n, which guarantees that the number of O’s is n and the number of H’s is 2n. Each character represents a thread calling the function that prints the corresponding H or O once, and 3N characters (threads, if you like) operate on the same instance variable. We want to control the instance variable in units of three characters. When the H thread comes in, if it finds that H has printed twice in the unit, the H thread must be suspended and cannot work, such as HHH…… , the third H cannot print and needs to be suspended, waiting for the O thread to wake up; Similarly, if O comes in and finds that the unit O has been printed once, it must also hang and wait for the thread H to wake up.
We can use a count to keep track of how many times H is printed, and then suspend it at two times, waiting for O to be printed, and then set count to zero. And that guarantees that in the final output, for any unit, the output will be HHO.
class H2O {
// How many times is H currently printed
volatile int count = 0;
Object obj = new Object(a); publicH2O() {
}
public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
synchronized (obj) {
// Print H = 2, wait for O to print
while(count > 1) {
obj.wait();
}
releaseHydrogen.run();
++count;
obj.notifyAll();
}
}
public void oxygen(Runnable releaseOxygen) throws InterruptedException {
synchronized (obj) {
// If the number of H is less than 2, O cannot be printed
while (count < 2) {
obj.wait();
}
releaseOxygen.run();
count = 0; obj.notifyAll(); }}}Copy the codePrint strings alternately
Write a program that prints a string representing this number from 1 to n, but:
- If the number is divisible by 3, print “fizz”.
- If the number is divisible by 5, print “buzz”.
- If the number is divisible by both 3 and 5, print “fizzbuzz”.
For example, when n = 15, output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz.
Suppose we have a class like this:
class FizzBuzz {
public FizzBuzz(int n) { ... } // constructor
public void fizz(printFizz) { ... } // only output "fizz"
public void buzz(printBuzz) { ... } // only output "buzz"
public void fizzbuzz(printFizzBuzz) { ... } // only output "fizzbuzz"
public void number(printNumber) { ... } // only output the numbers
}
Copy the codeA FizzBuzz instance will be used by the following four threads:
- Thread A will call
fizz()To see if it is divisible by 3, and if so, outputfizz. - Thread B will call
buzz()To see if it is divisible by 5, and if so, outputbuzz. - Thread C will call
fizzbuzz()To determine whether it is divisible by both 3 and 5, and if so, outputfizzbuzz. - Thread D will call
number()To output numbers that are not divisible by either 3 or 5.
Or in an instance variable for 4 threads to carry out collaborative control, looks like the above line printing zero and odd even very similar, not this thread after printing, set the corresponding flag, call up the next thread. But this problem, WHEN I do find a place is quite pit, look at the code:
class FizzBuzz {
private int n;
volatile int flag = 1;
Object obj = new Object(a); publicFizzBuzz(int n) {
this.n = n;
}
// printFizz.run() outputs "fizz".
public void fizz(Runnable printFizz) throws InterruptedException {
retry:
for (int i = 3; i <= n; i +=3) {
synchronized (obj) {
while(flag ! =3) {
obj.wait();
// if I = 15, the thread will not be aroused, so skip it; otherwise, the thread will remain stuck at I = 15
if (i % 15= =0) {
continue retry;
}
}
printFizz.run();
flag = 1; obj.notifyAll(); }}}// printBuzz.run() outputs "buzz".
public void buzz(Runnable printBuzz) throws InterruptedException {
retry:
for (int i = 5; i <= n; i +=5) {
synchronized (obj) {
while(flag ! =5) {
obj.wait();
If // // I = 15, the thread will not be aroused, so skip it; otherwise, the thread will remain stuck at I = 15
if (i % 15= =0) {
continue retry;
}
}
printBuzz.run();
flag = 1; obj.notifyAll(); }}}// printFizzBuzz.run() outputs "fizzbuzz".
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
for (int i = 15; i <= n; i +=15) {
synchronized(obj){
while(flag ! =15) {
obj.wait();
}
printFizzBuzz.run();
flag = 1; obj.notifyAll(); }}}// D to determine what flag is and which thread should be used next time
public void number(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i +=1) {
synchronized (obj) {
while(flag ! =1) {
obj.wait();
}
// If I is not divisible by 3 and 5, output it directly
if (i % 3! =0 && i % 5! =0) {
printNumber.accept(i);
}
// Otherwise, calculate which thread I corresponds to work
else {
flag = i % 15= =0?15:(i % 3= =0?3:5); } obj.notifyAll(); }}}}Copy the codeWhen A,B, and C work, D will be called up, and D will decide which thread will work next. The corresponding flags of A,B, and C are also set by D. But at first my code kept running out of time until I realized why: If n is greater than or equal to 15, then both A and B will go to I = 15 of their loops, but I = 15, and neither of these threads will be aroused, so if n is 15, 16, 17, these two threads will be suspended, and no one will be aroused, even if n is 18, at this point, Thread D seems to be able to go to I = 18, and it seems to wake up A, but A’s I is 15, and then it’s going to go to I = 18, and thread D has finished, and A is going to hang at I = 18, and it’s going to wake up one less time, and it’s going to time out.
Obj.wait (); obj.wait(); obj.wait();
if (i % 15= =0) {
continue retry;
}
Copy the codeIf I get aroused and I is divisible by 15, I just skip this loop. Of course, it is also possible to place this statement outside the synchronized block.
1226 The philosopher dines
This is a long problem with a nice picture, so I’m not going to put the original problem. Dining philosophers problem is a typical deadlock in the operating system, if five philosophers everyone picked up his fork on the left, everyone is waiting for the right fork, and everyone will not take the initiative to put down the fork, so will cause a deadlock, in order to solve the deadlock, we can control the number of people eating at the same time, for example, if there can be only one person have a meal at the same time, It must be edible, and it won’t deadlock. I wrote the code like this at the beginning.
class DiningPhilosophers {
Object obj = new Object(a); publicDiningPhilosophers(){}// call the run() method of any runnable to execute its code
public voidwantsToEat(int philosopher, Runnable pickLeftFork, Runnable pickRightFork, Runnable eat, Runnable putLeftFork, Runnable putRightFork) throws InterruptedException { synchronized (obj) { pickLeftFork.run(); pickRightFork.run(); eat.run(); putLeftFork.run(); putRightFork.run(); }}}Copy the codeUse Java semaphore to control the number of people eating at the same time.
class DiningPhilosophers {
ReentrantLock[] locks;
// Use the semaphore to control the number of entries
Semaphore limit;
public DiningPhilosophers() {
// Each fork has a lock
locks = new ReentrantLock[5];
for (int i = 0; i <5; ++i) { locks[i] =new ReentrantLock();
}
// Limit the number of simultaneous diners to 2
limit = new Semaphore(2);
}
// call the run() method of any runnable to execute its code
public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
There are several ways to define the number of each philosopher's left and right forks
// Just make sure that the final number corresponds to the philosopher
int left = philosopher,right = (philosopher + 4) % 5; limit.acquire(); locks[left].lock(); locks[right].lock(); pickLeftFork.run(); pickRightFork.run(); eat.run(); putLeftFork.run(); putRightFork.run(); locks[left].unlock(); locks[right].unlock(); limit.release(); }}Copy the codeThe philosopher is numbered 0-4, and the fork can be numbered yourself, so for example, you can have the fork around philosopher 0 be numbered 0, 4, or 1,0. As long as you end up with the semantics of each philosopher picking up the left fork and the right fork.
Here, the semaphore is set to 2, and only two people can eat at the same time. Before taking the fork, the lock corresponding to the fork should be obtained. In fact, the semaphore is set to 3 or 4, and even 4, there must be one person who can eat (and get the lock of two forks at the same time). As long as it’s not 5 (5 people eating at the same time can still be deadlocked).
conclusion
The main difficulty of multithreaded programming, at least in terms of these problems, is how to do some synchronization within a shared variable so that different threads work together the way we want them to, and they don’t really care much about how they start.