subject
Give you 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");
}
}
}
Two different threads will share a FooBar instance:
Thread A will call the foo() method, and
Thread B will call the bar() method
Please design and modify the program to ensure that "foobar" is output n times.
Example 1:
Input: n = 1
Output: "foobar"
Explanation: two threads are started asynchronously. One calls the foo() method, the other calls the bar() method, and "foobar" will be output once.
Problem solution
Method 1: Semaphore
- Semaphore is a count semaphore.
- Conceptually, Semaphore contains a set of licenses.
- If necessary, each acquire() method blocks until an available license is obtained.
- Each release() method releases the licensed thread and returns an available license to Semaphore.
- However, in fact, there is no real license object for threads to use, and Semaphore only manages and maintains the amount available
- Summary: if a thread wants to access a resource, it must first obtain a semaphore. If the semaphore internal counter is greater than 0, the semaphore is decremented by 1, and then the resource is allowed to be shared; Otherwise, if the semaphore's counter is equal to 0, the semaphore will put the thread into sleep until the counter is greater than 0 When the semaphore is used up, it must be released
public class FooBar {
private int n;
public FooBar(int n) {
this.n = n;
}
private static Semaphore fooSem = new Semaphore(1);// There is a license by default
private static Semaphore barSem = new Semaphore(0);
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
fooSem.acquire(); //When the value is 1, you can get it and perform the following operations
printFoo.run();
barSem.release(); //Release the permission to barSema. The value of this semaphore barSema is + 1
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
barSem.acquire(); //When the value is 1, you can get it and perform the following operations
printBar.run();
fooSem.release();//Release the permission to barSema. The value of this semaphore barSema is + 1
}
}
}
Method 2: thread yield( )
Thread.yield(): change the current thread from the execution state (running state) to the executable state (ready state). The cpu will choose from many executable States, that is, the current thread, that is, the thread just now, may be executed again, which does not mean that other threads will be executed and the thread will not be executed next time.
class FooBar {
private int n;
volatile boolean fooExec = true;//foo can be executed
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; ) {
if (fooExec) {
printFoo.run();
fooExec = false;
i++;
} else {
Thread.yield();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; ) {
if (!fooExec) {
printBar.run();
fooExec = true;
i++;
} else {
Thread.yield();
}
}
}
}
Method 3:synchronized
background knowledge
1. wait() and notify/notifyAll() methods are local final methods of Object and cannot be overridden.
2. Wait() blocks the current thread on the premise that the lock must be obtained first. It is generally used with the synchronized keyword, that is, wait() and notify/notifyAll() methods are generally used in the synchronized synchronization code block.
3. Since wait() and notify/notifyAll() are executed in the synchronized code block, it indicates that the current thread must have acquired the lock.
When the thread executes the wait() method, it will release the current lock, then give up the CPU and enter the waiting state.
Only when notify/notifyAll() is executed will one or more waiting threads wake up, and then continue to execute until the synchronized code block is executed or wait() is encountered halfway to release the lock again.
In other words, the execution of notify/notifyAll() only wakes up the sleeping thread and does not release the lock immediately. The release of the lock depends on the specific execution of the code block. Therefore, in programming, try to exit the critical area immediately after using notify/notifyAll() to wake up other threads to obtain locks
4. wait() needs to be surrounded by try catch so that an abnormal interrupt can also wake up the waiting thread.
5. The order of notify and wait cannot be wrong. If thread A executes the notify method first and thread B executes the wait method, thread B cannot be awakened.
6. The difference between notify and notifyAll
The notify method wakes up only one waiting (object's) thread and causes it to execute. Therefore, if there are multiple threads waiting for an object, this method will wake up only one of them. The choice of which thread depends on the implementation of multithreading management by the operating system. NotifyAll will wake up all waiting (object's) threads, Although which thread will be the first to process depends on the implementation of the operating system. If multiple threads need to be awakened under the current situation, the notifyAll method is recommended. For example, in the use of producer consumer, it is necessary to wake up all consumers or producers every time to judge whether the program can continue to execute.
class FooBar {
private int n;
private Object obj = new Object();
private volatile boolean fooExec = true;
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (obj) {
if (!fooExec) {//When fooExec is false, the thread waits. When fooExec is true, the following operations are performed
obj.wait();
}
printFoo.run();
fooExec = false;
obj.notifyAll();//Wake up other threads
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (obj) {
if (fooExec) {
obj.wait();
}
printBar.run();
fooExec = true;
obj.notifyAll();
}
}
}
}
Option 4: Lock (fair Lock)
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; ) {
lock.lock();
try {
if(permitFoo) {
printFoo.run();
i++;
permitFoo = false;
}
}finally {
lock.unlock();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; ) {
lock.lock();
try {
if(!permitFoo) {
printBar.run();
i++;
permitFoo = true;
}
}finally {
lock.unlock();
}
}
}
}
Option 5: no lock
class FooBar {
private int n;
public FooBar(int n) {
this.n = n;
}
volatile boolean permitFoo = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; ) {
if(permitFoo) {
printFoo.run();
i++;
permitFoo = false;
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; ) {
if(!permitFoo) {
printBar.run();
i++;
permitFoo = true;
}
}
}
}
Scenario 6: CyclicBarrier
CyclicBarrier is more suitable for circular scenes
class FooBar {
private int n;
public FooBar(int n) {
this.n = n;
}
CyclicBarrier cb = new CyclicBarrier(2);
volatile boolean fin = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while(!fin);
printFoo.run();
fin = false;
try {
cb.await();
} catch (BrokenBarrierException e) {
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
try {
cb.await();
} catch (BrokenBarrierException e) {
}
printBar.run();
fin = true;
}
}
}
Method 7: use a CountDownLatch combined with a CyclicBarrier to solve the problem
CountDownLatch is used to ensure the execution order of tasks in the group, and CyclicBarrier is used to ensure that tasks are performed by group.
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.CyclicBarrier;
class FooBar {
private int n;
private CountDownLatch a;
private CyclicBarrier barrier;// Use CyclicBarrier to ensure that tasks are executed by groups
public FooBar(int n) {
this.n = n;
a = new CountDownLatch(1);
barrier = new CyclicBarrier(2);// Ensure that there are two tasks in each group
}
public void foo(Runnable printFoo) throws InterruptedException {
try {
for (int i = 0; i < n; i++) {
printFoo.run();
a.countDown();// The printFoo method completes the call to countDown
barrier.await();// Wait for printBar method execution to complete
}
} catch(Exception e) {}
}
public void bar(Runnable printBar) throws InterruptedException {
try {
for (int i = 0; i < n; i++) {
a.await();// Wait for the printFoo method to execute first
printBar.run();
a = new CountDownLatch(1); // Ensure that the next time you still wait for the printFoo method to execute first
barrier.await();// Wait for printFoo method execution to complete
}
} catch(Exception e) {}
}
}