Summary of knowledge related to Java spin lock (spinlock)

Catalogue 1. Preface
2. Lock optimization: Spin lock
3. Deadlock of spin lock 3.1, system interrupt
3.2. Interrupt Handler
3.3. Interrupt context Context
4. Deadlock resolution

1. Preface

When it comes to "spin lock", you may say that there is nothing to talk about, that is, the thread waiting for resources "spins around". Well, the literal meaning is in place, but can you go deeper and more specific? Is the design of spin lock really that simple?

The purpose of this article or this series is to let everyone not stay on the surface, but make in-depth analysis and achieve:

Flexible use Master the principle Advantages and disadvantages

2. Lock optimization: Spin lock

When multiple threads want to access the same resource at the same time, there is a resource conflict. At this time, the most direct thought of everyone is locking to mutually exclusive access. Lock will have several problems:

The thread waiting for the resource goes to sleep, and the switch from user mode to kernel mode occurs, which has a definite performance overhead; The thread occupying resources is quickly used up and released. At this time, the waiting thread is awakened and immediately switched back to user mode;

Then, if there is a way to make the waiting thread wait for a short time, there may be two results:

After waiting for more than one moment, there was no way, so I had to go to sleep; Before the waiting time is exceeded, the thread occupying the resource is released, and then the waiting thread can directly occupy the resource.

This is the small optimization of lock: spin lock! Spin lock is not a real lock, but lets the waiting thread "turn" 1 and 1 in place first. Usually, the implementation of small turn 1 is very simple:

int SPIN_LOCK_NUM = 64;
int i = 0;
boolean wait = true;

do {
 wait = //  Attempt to acquire a resource lock 
} while (wait && (++i) < SPIN_LOCK_NUM);

The number of times we determine by cycle 1 comes from the spin. \ color {red} {But we should also know that spinning around without going into hibernation will directly consume CPU resources, so there is spin restriction!} However, we should also know that spinning around without going to sleep will consume CPU resources directly, so there is spin restriction!

Look at the following JDK source code:

public final class Unsafe {
 public final int getAndSetInt(Object var1, long var2, int var4) {
  int var5;
  do {
   var5 = this.getIntVolatile(var1, var2);
  } while(!this.compareAndSwapInt(var1, var2, var5, var4));
 
  return var5;
 }
}

As we can see, CAS is a spin lock method, which continuously tries to read the value of the latest volatile modified variable, and tries to compare it with the expected value, and then updates it.

However, we should pay attention here, because it is an infinite loop, so we should ensure that the threads occupying resources can be released quickly, not for a long time (of course, because the source code system here also sets the int variable, the threads occupying this variable will be released soon after being used up).

3. Deadlock of spin lock

What? Why is there a deadlock? Although spin lock is easy to use, if we only stay in the above analysis, it is still very superficial; Although spin locking has great advantages, it also has many disadvantages. Besides the above, spinning in place (busy waiting) will consume CPU resources directly, and at the same time, there will be one potential defect: deadlock.

3.1. System interruption

Before talking about deadlock, we need to know the first system interrupt event (this chapter is in the college textbook, and the system interrupt vector table is also involved in the ASM compilation):

Interrupt means that during the normal operation of CPU, due to internal/external events or events arranged in advance by the program, CPU suspends the current work and handles the event instead, and then returns to continue running the interrupted (suspended) program after handling the event. Generally, the operating system divides interrupts into two categories: external interrupts (hardware interrupts) and internal interrupts (abnormal interrupts, that is, software-caused);

For example, interrupts caused by IO devices are hardware interrupts, such as keyboard input, hard disk/CD drive reading and writing, etc.; Abnormal interrupts are easy to understand, such as NullPointerException.

3.2. Interrupt Handler

The system provides an API that enables our program to register an interrupt handler with the system (for example, the program receives user input events).

request_irq(unsigned int irq, irq_handler_t handler, unsigned long flags, const char *name, void *dev)

The parameters have the following meanings:

irq: Interrupt number, the system is well defined, and the interrupt vector table can be viewed for details; handler: ISR (Interrupt Service Routines) occurred after interruption, which is directly translated as: interrupt service route; Practically similar, it is a program that responds to interruption of service; flags: Interrupt flag; name: ASCII of interrupt-related devices, such as "keyboard", which will be used in/proc/irq and/proc/interrupts; dev: Device architecture for sharing interrupt lines and passing drivers. Non-shared interrupt, directly set to NULL

Interrupt flag (flags):

IRQF_DISABLED: During the kernel processing of this ISR, other interrupts are prohibited (1 is rarely used); IRQF_SAMPLE_RANDOM: Indicates that interrupts generated by the device contribute to the kernel entropy pool; IRQF_TIMER: System timer; IRQF_SHARED: Multiple ISR share interrupt line, that is, one interrupt, and multiple ISR may exist;

A successful call to request_irq returns 0. The common error is-EBUSY, indicating that the given interrupt line is already in use (IRQF_SHARED is not specified).

Note:

This function may cause sleep, so it is not allowed to be used in programs that interrupt context or do not allow sleep! The interrupt handler in Linux is reentrant-free. When a given interrupt handler is executing, its interrupt line is masked on all processors to prevent another new interrupt from being received on the same interrupt line. Usually, all interrupts except this interrupt are open, which means that the key points on other interrupt lines can be handled, but the current interrupt line is always prohibited, so the same interrupt handler will never be nested by itself.

So what does this have to do with deadlock? Well, I'll talk about it in the next section. But all the interrupts mentioned here are because we also need to know one thing. When the system interrupts and the program is paused, the program cannot go to sleep. At this time, the program can only use one way: spin to ensure that it will not sleep.

Why can't you sleep? This involves "interrupt context context"!

3.3. Interrupt context Context

As mentioned above, request_irq may cause sleep, so it is not allowed to be used in interrupt context, that is, interrupt context does not allow sleep!

Interrupt context: This is different from the process context. The interrupt context is that the kernel is executing ISR. The ISR does not have its own stand-alone stack, but uses the kernel stack, and the size of 1 is generally limited (32 bits is the size of 8KB). At the same time, ISR interrupts the normal program flow, so it is necessary to ensure the fast execution speed of ISR. Because of the fast execution speed, the interrupt context is not allowed to sleep and is not allowed to be blocked!

You may say that the fast execution speed does not allow sleep, which is unreasonable. Can't I sleep for 1ms? Well, let's analyze the real reason why we can't sleep:

1. No process switching occurs when processing is interrupted.

Because the current interrupt can only be interrupted by a higher priority interrupt, the priority of other processes will not be higher than the interrupt priority; If the interrupt context is dormant, there is no way to wake it up, because all wake_up_xxx are for processes, and interrupts have no concept of processes; As long as it is an interrupt (or in hard, not cigarettes), it all occurs in the kernel. If the interrupt context sleeps, the kernel will block. Can the system block? Can't! If you block, you can only restart the machine;

2. schedule saves the current process context (CPU register value, status, SP contents of the stack) when switching processes for later resumption and re-operation. After an interrupt occurs, the kernel saves the context of the currently interrupted process. In ISR, it is an interrupt context. If it is dormant or blocked, schedule will be called. The saved process context is not the context of the current process, so schedule cannot be called in ISR;
3. The schedule in the kernel determines whether it is in an interrupt context when entering:

if(unlikely(in_interrupt()))) ..... crash!!!

4. Interrupting handler will use the interrupted process kernel stack, but it will not affect it, because handler will be saved before use, and will be cleared and restored after use;
5. In the context of handling interrupts, the kernel is not preemptive. If it is dormant, the kernel... 1 will be suspended. Similarly, you can only restart the machine;
Therefore, the interrupted program can't sleep! Then you can only use "spin lock" to spin around.

That still doesn't say why spin deadlock.

Spin lock is not recursive, otherwise you wait for the lock you have acquired, which will lead to deadlock!

A thread acquired a spin lock and was interrupted by an interrupt handler during execution, so the thread only paused execution, did not exit, and still held the spin lock; However, the interrupt handler tries to obtain the spin lock but cannot obtain it, so it can only spin; This leads to the fact that ISR can't get the spin lock, which leads to spin and can't exit. The thread is interrupted and can't resume execution until exit releases the spin lock, which leads to deadlock and system crash.

4. Deadlock resolution

When spin lock deadlock occurs, it is often because the critical resource of single CPU is preempted, which makes one party hold spin lock interrupt and pause, and one party keeps spinning to try to acquire spin lock. Therefore, under the multi-CPU architecture, if two parties run on different CPU respectively, deadlock will not occur.

Therefore, spin locking has several important characteristics to master:

The thread holding spin lock (which must be in the critical area at this time) cannot sleep, which will cause process switching, and CPU will be occupied by another process and cannot be used; Threads holding spin locks are not allowed to be interrupted, even if it is ISR, otherwise there will be ISR spin; The kernel of a thread holding a spin lock cannot be preempted, otherwise it is equivalent to CPU being preempted;

Therefore, according to the above summary 1 point: Threads holding spin locks cannot give up CPU for any reason! Therefore, based on the above problems, spin also needs to add an upper limit time to prevent deadlock.

There are three implementations of spin locking on linux:

In a single cpu, non-preemptive kernel, spin lock is an empty operation. In a single cpu, preemptive kernel, spin lock is implemented as "no kernel preemption", but not "spin". (Note) In multi-cpu, preemptive kernel, spin lock is implemented as "no kernel preemption" + "spin".

The above is the details of Java spin lock (spinlock) related knowledge summary. For more information about Java spin lock (spinlock), please pay attention to other related articles on this site!