Writing in the front

A lot of times in concurrent programming, when it comes to locking, does it really make sense to lock blocks of code? Is there anything that needs to be optimized?

preface

In [High Concurrency] optimization lock mode unexpectedly deadlocked!! In this article, we introduce four necessary conditions for deadlocks to occur. Deadlocks can occur only when all four conditions are met simultaneously. We block request and hold conditions by applying for all resources at once. For example, when we complete the transfer operation, we apply for account A and account B at one time. After both accounts are successfully applied, the transfer operation will be carried out. Among them, in the transfer method we implemented, an infinite loop was used to obtain resources circulatively until account A and account B were obtained at the same time. The core code is shown as follows.

// Apply one transfer out and one transfer in until successful
while(! requester.applyResources(this, target)){
    // The loop body is empty
    ;
}
Copy the code

This is possible if the applyResources() method of the ResourcesRequester class is executed in a very short time and the concurrency of the program is not so conflicting that the program can loop a few to dozens of times to get both roll-out and roll-in accounts.

However, if the applyResources() method of the ResourcesRequester class takes a long time to execute, or if the concurrency of the program causes a large conflict, it may take thousands of cycles to get both the roll-out and roll-in accounts. This will consume too much CPU resources, and at this point, this scheme is not feasible.

So, is there a way to optimize this solution?

Problem analysis

Since there is a problem with using an endless loop to get resources all the time, let’s put ourselves in the other’s shoes. If the condition is not met while the thread is executing, can I put the thread into wait state? When the condition is met, tell the waiting thread to execute again?

That is, if the thread’s requirements are not met, we put the thread into a wait state; If the thread’s requirements are met, we notify the waiting thread to execute again. In this way, you can avoid the problem of your program looping around and consuming CPU.

So, again! How to make threads wait when conditions are not met? When the condition is met, how do you wake up the thread?

Yes, that’s a problem! But it’s a very simple problem to solve. To put it simply, it uses the wait and notification mechanism of threads.

Wait and notification mechanisms for threads

We can use the wait and notification mechanism of threads to optimize the problem of cyclic access to account resources when blocking requests and holding conditions. The specific wait and notification mechanism is as follows.

The executing thread first acquires the mutex. If the conditions are not met when the thread continues to execute, the mutex is released and the thread enters the wait state. When the conditions for the thread to continue execution are met, the waiting thread is notified to reacquire the mutex.

So, having said that, does Java support this kind of wait and notification mechanism for threads? In fact, this question is a bit of nonsense, Java such a good (awesome) language must support ah, and relatively easy to implement.

Implement thread wait and notification mechanism with Java

implementation

In fact, the use of Java language thread waiting and notification mechanism has a variety of ways, here I will simply list a way, other ways we can think and achieve their own, do not understand the place can also ask me!

In Java language, a simple way to implement the wait and notification mechanism is to use synchronized combined with wait(), notify() and notifyAll() methods.

Realize the principle of

When we use synchronized locking, only one thread is allowed to enter a block of synchronized protected code, known as the critical section. If a thread enters a critical section, the other threads wait in a blocking queue, which has a one-to-one relationship with synchronized mutex. In other words, a mutex corresponds to a separate blocking queue.

In concurrent programming, if a thread acquires a synchronized mutex but does not meet the conditions to proceed, it enters a wait state. At this point, you can use the Wait () method in Java. When a wait() is called, the current thread blocks and waits in a wait queue, which is also a mutex wait queue. In addition, a thread will release the mutex it acquired when it enters the wait queue, so that other threads have a chance to acquire the mutex and enter the critical section. The whole process can be represented as shown below.

When thread execution conditions are met, the Notify () and notifyAll() methods provided by Java can be used to notify threads in a mutex wait queue. This process can be briefly illustrated in the following figure.

Note the following:

(1) When notify() and notifyAll() are used to notify threads, the notify() and notifyAll() methods meet the execution conditions of the threads. However, when the threads actually execute, the conditions may no longer be met, and other threads may have entered the critical area for execution.

(2) The notified thread needs to acquire the mutex to continue execution, since the mutex is already released when it calls wait().

(3) Wait (), notify(), and notifyAll() are mutually exclusive wait queues. If synchronized locks this, Be sure to use the this.wait(), this.notify(), and this.notifyall () methods; If synchronized locks a target object, be sure to use the target.wait(), target.notify(), and target.notifyall () methods.

(4) Wait (), notify(), and notifyAll() are called only when the corresponding mutex has been obtained. In other words, wait(), notify(), and notifyAll() are called in synchronized methods or code blocks. If outside the synchronized method or block out of the three methods, or lock object is this, the use of the target object call three methods, the JVM throws Java. Lang. IllegalMonitorStateException anomalies.

The specific implementation

Implementation logic

There are a few other issues we need to consider before implementing:

  • Select which mutex

In the previous program, we had a singleton of the ResourcesRequester class in the TansferAccount class, so we could use this as the mutex. This is something that needs to be understood.

  • Conditions under which a thread executes a transfer operation

Neither outgoing nor incoming accounts have been assigned.

  • When does a thread enter the wait state

A thread enters the wait state when the conditions required to continue execution are not met.

  • When are waiting threads notified to execute

When there is a thread releasing the account’s resources, the waiting thread is notified to continue execution.

To sum up, we can get the following core code.

while{wait(); }Copy the code

So, here’s the problem! Why call wait() in a while loop? Because when wait() returns, it is possible that the condition that the thread executed has changed, that is, the condition that was satisfied before is no longer satisfied, and so the condition is rechecked.

The implementation code

The code for our optimized ResourcesRequester class is shown below.

public class ResourcesRequester{
    // Store a collection of requested resources
    private List<Object> resources = new ArrayList<Object>();
    // Apply all resources at once
    public synchronized void applyResources(Object source, Object target){
        while(resources.contains(source) || resources.contains(target)){
            try{
                wait();
            }catch(Exception e){
                e.printStackTrace();
            }
        }
        resources.add(source);
        resources.add(targer);
    }
    
    // Release resources
    public synchronized void releaseResources(Object source, Object target){ resources.remove(source); resources.remove(target); notifyAll(); }}Copy the code

The code for the Holder class ResourcesRequesterHolder that generates the ResourcesRequester singleton is shown below.

public class ResourcesRequesterHolder{
    private ResourcesRequesterHolder(a){}
    
    public static ResourcesRequester getInstance(a){
        return Singleton.INSTANCE.getInstance();
    }
    private enum Singleton{
        INSTANCE;
        private ResourcesRequester singleton;
        Singleton(){
            singleton = new ResourcesRequester();
        }
        public ResourcesRequester getInstance(a){
            returnsingleton; }}}Copy the code

The code for the class that performs the transfer operation is shown below.

public class TansferAccount{
    // Account balance
    private Integer balance;
    // singleton object of the ResourcesRequester class
    private ResourcesRequester requester;
   
    public TansferAccount(Integer balance){
        this.balance = balance;
        this.requester = ResourcesRequesterHolder.getInstance();
    }
    // Transfer operation
    public void transfer(TansferAccount target, Integer transferMoney){
        // Apply one transfer out and one transfer in until successful
        requester.applyResources(this, target))
        try{
            // Lock the outgoing account
            synchronized(this) {// Lock the transferred account
                synchronized(target){
                    if(this.balance >= transferMoney){
                        this.balance -= transferMoney; target.balance += transferMoney; }}}}finally{
            // Finally release account resources
            requester.releaseResources(this, target); }}}Copy the code

As you can see, we use notifyAll() instead of notify() in our program to notify threads in the wait state. What’s the difference between notify() and notifyAll()?

The difference between notify() and notifyAll()

  • Notify () method

Randomly notify a thread in the wait queue.

  • NotifyAll () method

Notify all threads in the wait queue.

In practice, if there is no special requirement, use notifyAll() method. Because using notify() is risky, some threads may never be notified!

Big welfare

WeChat search the ice technology WeChat 】 the public, focus on the depth of programmers, daily reading of hard dry nuclear technology, the public, reply within [PDF] have I prepared a line companies interview data and my original super hardcore PDF technology document, and I prepared for you more than your resume template (update), I hope everyone can find the right job, Learning is a way of unhappy, sometimes laugh, come on. If you’ve worked your way into the company of your choice, don’t slack off. Career growth is like learning new technology. If lucky, we meet again in the river’s lake!

In addition, I open source each PDF, I will continue to update and maintain, thank you for your long-term support to glacier!!

Write in the last

If you think glacier wrote good, please search and pay attention to “glacier Technology” wechat public number, learn with glacier high concurrency, distributed, micro services, big data, Internet and cloud native technology, “glacier technology” wechat public number updated a large number of technical topics, each technical article is full of dry goods! Many readers have read the articles on the wechat public account of “Glacier Technology” and succeeded in job-hopping to big factories. There are also many readers to achieve a technological leap, become the company’s technical backbone! If you also want to like them to improve their ability to achieve a leap in technical ability, into the big factory, promotion and salary, then pay attention to the “Glacier Technology” wechat public account, update the super core technology every day dry goods, so that you no longer confused about how to improve technical ability!