CN116204303A - Implementation method of spin lock capable of optimizing interrupt delay - Google Patents

Abstract

The application provides a realization method of spin lock capable of optimizing interrupt delay, which belongs to the technical field of computer system software, and specifically comprises the steps of controlling a plurality of threads to access resources by adopting a two-stage spin lock, wherein the two-stage spin lock comprises a first stage of a plurality of first threads; receiving a request for a thread to acquire a resource, placing the thread on a first queue associated with a first phase of a two-phase spin lock, determining whether at least one predetermined slot is available in a second phase of the two-phase spin lock, when the slot is not available, processing an interrupt serviced by the selected thread based on a number of attempts by the selected thread to enter the second phase, and when at least one slot is available, selecting one of the first threads to enter the second phase based on a time priority order. Two-stage spin locks can take advantage of various features to maintain a deterministic approach while still providing an opportunity to service interrupts, allowing interrupts to be handled while waiting, while ultimately successfully obtaining a lock without the risk of deadlock.

Description

A Spinlock Implementation Method That Can Optimize Interrupt Latency

technical field

The present application relates to the field of computer system software, in particular to an implementation method of a spin lock capable of optimizing interrupt delay.

Background technique

Locks are used to control access to computing resources. For example, a lock restricts access to a resource when multiple different threads attempt to access the resource. A spin lock is a special type of lock that allows requesting threads that are waiting to access an occupied resource to wait in a loop, while repeatedly checking whether the resource's spin lock is available. There are two main types of spin locks: task spin locks and interrupt spin locks. While a task spinlock is in a loop, the requesting thread may still be active and perform other tasks; however, an interrupt spinlock does not allow the requesting thread to perform other tasks.

Spinlocks introduce latency and inefficiency. For example, a resource might be allocated to a requesting thread that is not actively using the resource. In this case, the resource may become inaccessible for a long period of time because the thread does not release the spinlock.

Computing environments can be configured in a deterministic manner to handle threads efficiently, however, interrupts may need to be disabled. Because of the immediate need for attention and the relatively unsystematic nature of interrupts, environments may choose to disable interrupts when queuing, acquiring, and releasing spinlocks.

Traditional interrupt spin locks must be spun with interrupts disabled on the local CPU core in order to acquire the lock. Any interrupts routed to that CPU core will likely have to wait a long time (and possibly indeterminately). In traditional interrupt spinlock implementations, spinning with interrupts enabled can easily lead to deadlock.

Contents of the invention

In view of this, this application provides an implementation method of a spin lock that can optimize the interrupt delay, which solves the problems in the prior art. In the implementation of the interrupt spin lock, the spin is not easy to deadlock when the interrupt is enabled .

The implementation method of a spin lock that can optimize the interrupt delay provided by this application adopts the following technical solution:

A method for implementing a spin lock capable of optimizing interrupt latency, comprising:

Using a two-stage spin lock to control multiple threads to access resources, the two-stage spin lock includes a first stage of multiple first threads;

receiving a thread's request to acquire a resource, placing the thread on the first queue associated with the first phase of the two-phase spinlock, determining whether at least one reserved slot is available in the second phase of the two-phase spinlock, Handle the interrupt serviced by the selected thread according to the number of attempts made by the selected thread to enter the second phase when the slot is not available, and select one of the first threads to enter the second phase according to the temporal priority order when at least one slot is available ;

Determines whether a lock to access a resource is available, when the lock is available, selects one of multiple second threads in the second phase of the two-phase spinlock to acquire the lock, determines the age of the selected second thread, and when the age is not

The oldest of the second threads in the second stage, prohibit any first thread from entering the second stage; otherwise, when 5 years old is the oldest of the second threads in the second stage, choose the oldest first thread to enter the second stage;

Receives further requests from the selected thread and places the selected thread in the first queue.

Optionally, the operation of putting the threads in the first queue is based on atomic acquisition and addition operations, and the acquisition and addition operations include: assigning respective ticket numbers to each thread according to time priority order.

Optionally, determining whether a first counter tracking a first number corresponding to 0 attempts for the selected thread to enter the second phase has been exhausted;

When the first counter is exhausted, the interrupt cannot be serviced and remains in the first queue;

When the first counter indicates at least one first opportunity for the corresponding set of attempts, determining whether the second counter tracks a second number by the selected thread, the second number corresponding to each attempt entering the second phase;

When the second counter indicates at least one second attempt opportunity, decrementing the second counter by 5 after the selected thread performs the attempt;

When the second counter is exhausted, receiving an interrupt that the selected thread has serviced, decrementing the first counter.

Optionally, when the age is not the oldest among the second threads in the second stage, and the lock is available when the selected second thread releases the lock, select from the remaining second threads in the second stage to obtain Lock.

Optionally, the selected second thread acquires the lock based on an atomic test and set operation, and in the selected second thread's lock acquisition operation, the second thread competes for the lock.

Optionally, each thread is serviced for a maximum duration.

Optionally, the maximum duration is based on a chronological entry of a thread in the first queue, the maximum number of second threads configured in the second stage, and the number of threads with lower chronological entries.

In summary, the application includes the following beneficial technical effects:

The spin lock mechanism of this application creates a deterministic spin lock, and at the same time allows waiting threads to be interrupted in service while waiting for the lock to be acquired. In the first stage, the thread may still service the interrupt. When entering the second stage, the spin lock can allocate resources to threads based on competition for resources. Two-phase spinlocks can take advantage of various properties to maintain a deterministic approach while still providing the opportunity for service interruptions, allowing interruptions to be handled while waiting, without the risk of deadlock when the lock is eventually successfully acquired.

The two-phase spinlock configuration ensures "acquire" memory semantics when a thread acquires the lock; the unlock operation provides "release" memory semantics. Thus, having a deterministic manner of spinlock operation while still providing the opportunity for service interruption, two-phase spinlocks can operate in a more efficient and faster manner than traditional spinlocks.

Description of drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present application, the following will briefly introduce the accompanying drawings that need to be used in the embodiments. Obviously, the accompanying drawings in the following description are only some embodiments of the present application. Those of ordinary skill in the art can also obtain other drawings based on these drawings without any creative effort.

Fig. 1 is the exemplary system of two-stage spin lock of the present application;

Fig. 2 is the exemplary method of the first stage of the two-stage spin lock of the present application;

FIG. 3 is an exemplary method of the second stage of the two-stage spinlock of the present application.

Detailed ways

Embodiments of the present application will be described in detail below in conjunction with the accompanying drawings.

Embodiments of the present application are described below through specific examples, and those skilled in the art can easily understand other advantages and effects of the present application from the content disclosed in this specification. Apparently, the described embodiments are only some of the embodiments of this application, not all of them. The present application can also be implemented or applied through other different specific implementation modes, and various modifications or changes can be made to the details in this specification based on different viewpoints and applications without departing from the spirit of the present application. It should be noted that, in the case of no conflict, the following embodiments and features in the embodiments can be combined with each other. Based on the embodiments in this application, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of this application.

It is noted that the following describes various aspects of the embodiments that are within the scope of the appended claims. It should be apparent that the aspects described herein may be embodied in a wide variety of forms and that any specific structure and/or function described herein is illustrative only. Based on the present application one skilled in the art should appreciate that an aspect described herein may be implemented independently of any other aspects and that two or more of these aspects may be combined in various ways. For example, any number of the aspects set forth herein can be used to implement an apparatus and/or practice a method. In addition, such an apparatus may be implemented and/or such a method practiced using other structure and/or functionality than one or more of the aspects set forth herein.

It should also be noted that the diagrams provided in the following embodiments are only schematically illustrating the basic idea of the application, and only the components related to the application are shown in the drawings rather than the number, shape and number of components in actual implementation. Dimensional drawing, the type, quantity and proportion of each component can be changed arbitrarily during actual implementation, and the component layout type may also be more complicated.

Additionally, in the following description, specific details are provided to facilitate a thorough understanding of examples. However, it will be understood by those skilled in the art that the described aspects may be practiced without these specific details.

An embodiment of the present application provides a method for implementing a spin lock that can optimize interrupt latency.

Exemplary embodiments relate to apparatus, systems, and methods for implementing a spinlock mechanism with starvation protection properties that create deterministic spinlocks while allowing waiting threads to service interruptions while waiting for lock acquisition. Spinlocks can assign tickets to threads requesting resources to put them in the first phase. While in the first phase, the thread may still be servicing the interrupt. When entering the second phase, spinlocks can allocate resources to threads based on contention for the resource. Two-phase spinlocks can take advantage of various properties to maintain a deterministic approach while still providing the opportunity for service interruption. Exemplary embodiments allow interrupts to be handled while waiting without the risk of deadlock when the lock is eventually successfully acquired.

The exemplary embodiments provide a two-phase spin lock to control access to resources by multiple requesting entities (eg, processors). A two-phase spinlock may include a first phase that provides a first queue in which threads requesting resources may spin. In the first phase, threads may service interrupts; the two-phase spinlock includes a second phase providing a second queue in which threads requesting resources compete for resources. In the second phase, the thread is disabled from servicing interrupts.

A two-phase spinlock configuration according to an exemplary embodiment ensures "acquire" memory semantics when a thread acquires a lock; an unlock operation provides "release" memory semantics. Thus, the exemplary embodiments have a deterministic manner of spinlock operation, while still providing opportunities for service interruptions, two-phase spinlocks can operate in a more efficient and faster manner than traditional spinlocks.

Figure 1 represents an exemplary system for a two-phase spinlock

A system includes multiple processors, spinlocks, and resources.

A "handler" describes an entity attempting to access a resource. "Processor" may represent a hardware processor, a software application, a thread of execution requesting access to a resource, and the like.

A resource can be any resource with a limited capacity, and more than a predetermined number of processors (or requesting entities) are prohibited from concurrently accessing the resource. For example, a resource might be a shared memory space, a peripheral, etc.

A spinlock can be a two-phase spinlock, where a thread can enter either the first phase or the second phase of the spinlock. During the first phase, the thread can enter the spin state, waiting to enter the second phase. In the second phase, threads can keep spinning while competing for resources until they are acquired.

According to the exemplary embodiment, the locking process is divided into two phases. In the first phase, the spinlock performs an atomic acquire-increment operation on a "ticket" counter for each thread requesting the resource. During the first phase, the spinning thread can continue to service interrupts when appropriate. In the first stage, the spinlock does not achieve the maximum number of threads still spinning in the first stage. In the second phase, the spin lock performs an acquire-release operation on the thread that was spinning in the second phase. In the second phase, the spin lock enables the maximum number of threads that are held spinning in the second phase.

According to the exemplary embodiment, a spin lock can guarantee a maximum bounded wait time for a thread before acquiring the resource. For example, according to the exemplary embodiment, a thread with ticket N may be serviced no later than N+D+W threads are granted the lock. W is the number of threads with ticket numbers less than N running in the first phase, W is a dynamic component that depends on the degree of lock contention, where W does not exceed the number of threads in the system minus 1; D is a hung CPU The maximum number of times a thread discards a ticket in the first phase. Tickets should be discarded before enabling local interrupts. Once local interrupts are enabled, any pending interrupts will be serviced. Thus, through the spinlock enforcement mechanism, exemplary embodiments can ensure that there is an upper bound on the number of times a thread that is spinning must wait before being granted the lock.

An embodiment of the present application provides a method for implementing a spin lock that can optimize interrupt latency.

A method for implementing a spin lock capable of optimizing interrupt latency, comprising:

Access to resources by multiple threads is controlled by using a two-stage spin lock, and the two-stage spin lock includes a first stage of multiple first threads.

Receive a thread's request to acquire resources, put the thread on the first queue associated with the first phase of the two-phase spinlock, because the first thread is associated with the first phase of the two-phase spinlock, determine the two-phase self Whether at least one of the scheduled slots is available in the second phase of the spinlock, and when a slot is unavailable, handles the interrupt serviced by the selected thread, based on the number of attempts the selected thread made to enter the second phase, when at least one slot is available , select one of the first threads to enter the second stage according to the order of time priority, and determine whether the lock to access the resource is available.

Determine whether a lock to access a resource is available, when the lock is available, select one of multiple second threads in the second stage of the two-stage spinlock to acquire the lock, determine the age of the selected second thread, and when the age is not the first The oldest of the second threads in the second stage, prohibit any first thread from entering the second stage; otherwise, when the age is the oldest of the second threads in the second stage, select the oldest first thread to enter the second stage. One of the ways to determine whether a lock is available is to set a flag that indicates whether the lock is available. Wherein the second thread disables service interruption.

Receives further requests from the selected thread and places the selected thread in the first queue.

The operation of putting threads in the first queue is based on atomic acquire and add operations, and the acquire and add operations include: assigning respective ticket numbers to each thread according to time priority order.

Determines whether the first counter tracking the first number corresponding to the number of attempts to enter the second phase by the selected thread 5 has been exhausted; when the first counter is exhausted, interrupts cannot be serviced and remain in the first queue ; when the first counter indicates at least one first opportunity for the corresponding set of attempts, determine whether the second counter tracks a second number by the selected thread, the second number corresponding to each attempt to enter the second phase; when the second counter indicates at least A second chance to try, after the selected thread execution attempt is decremented

Two counters; when the second counter is exhausted, receive the interrupt serviced by the selected thread, and decrement the first counter 0.

When the age is not the oldest among the second threads of the second stage, and the lock is available when the selected second thread releases the lock, a selection is made from the remaining second threads of the second stage to acquire the lock.

The selected second thread acquires the lock based on an atomic test and set operation in which the selected second thread acquires the lock in which the second thread competes for the lock.

5 Each thread is serviced for a maximum duration. The maximum duration is based on the chronological entry of one thread in the first queue, the maximum number of second threads configured in the second stage, and the number of threads with lower chronological entries.

As shown in Figure 2, the thread spinning in the first phase will provide interrupt service while waiting to enter the second phase. Interrupt servicing does not interrupt the deterministic way spinlocks are used. For example, a thread with ticket number N will not block a thread with ticket number N+1, it will be a purely ticket-based traditional spinlock

accomplish. Assuming N is the oldest ticket (e.g., the ticket number issued by the spinlock is the lowest ticket number), when at least 5 threads with ticket number N-A have been served in the second phase, the thread with ticket number N enters next second stage. In this way, tickets can identify an age, which corresponds to a ticket number (e.g., tickets with the highest age have the lowest ticket number, tickets with the youngest age have the highest ticket number).

Main process:

Spinlocks receive requests for resources from threads. A spin lock can assign a ticket to a thread. Spinlock 0 can use any ticket-based mechanism to process requests and allocate tickets. Put the thread in the first phase of the spinlock.

For example, threads spin in the first phase, waiting for access to resources.

A spinlock determines whether the second phase is available. The second stage of the spinlock has variable "A", which is the maximum number of slots that can be filled by the thread that is spinning. Thus, a spinlock can identify when a slot is

On (for example, a flag is set). For example, a resource is already available, so a thread in second phase 5 can acquire the resource. When this happens, the thread that acquired the resource no longer spins, and exits the second phase, at which point the occupied slot is now free.

If a second-stage slot is available, the spinlock selects the thread with the oldest ticket number among the threads spun in the first stage. For example, tickets may be assigned to each thread requesting a resource in chronological order (eg, starting with ticket number 1 and going to ticket number N). With this ticket number assignment scheme, the ticket with the lowest ticket number can be chosen. A spinlock can place selected threads in the second phase.

If the slot in the second stage is not available, the spin lock determines whether the thread spinning in the first stage still has a chance to service the interrupt. In making this decision, spinlocks can take advantage of discard counters. A drop counter keeps track of the number of attempts to enter the second phase. The drop counter can limit the duration of the interruption of the spin thread service in the first phase. As mentioned above, the maximum number of discards a CPU thread can do is limited to "D". A spinlock according to the exemplary embodiment services interrupts using a spin thread in the first phase. However, continued use interruptions may cause a particular thread to stay in the first stage indefinitely without entering the second stage, because each time the service is interrupted, the thread discards the ticket and loses its place in the first stage queue . When a thread discards a ticket and re-enters Phase 1, the spinlock can reallocate a new ticket with an up-to-date ticket number (e.g., the highest ticket number).

When the discard counter expires or is exhausted and there is no longer an opportunity to service the interrupt, the thread continues to spin at the position indicated by the ticket. When the discard counter indicates that there are more opportunities to service the interrupt, the spin lock determines whether the spinning thread in the first stage has a chance to try to enter the second stage. Under the traditional spin lock mechanism, the spin lock tries to obtain resources in a basically similar manner, and the spin thread in the first phase can try to enter the second phase independently of the ticket. As mentioned above, the drop counter may track a set of attempts performed by the spinning thread from the first phase to the second phase. Each spin thread in the first stage may further track the number of times a plurality of first stage spin threads attempt to enter the second stage using a spin lock counter. However, under the mechanism of the spin lock to transfer the spinning thread from the first stage to the second stage, the spinning thread of the first stage can remain in the first stage. Assuming the thread remains in the first phase, the spinlock will decrement the spinlock counter for the given thread.

When the spinlock counter indicates that the spinning thread in the first stage has no chance to enter the second stage, the spinlock continues to execute. The spinlock determines that when all attempts to enter the second phase have been exhausted by the thread, an instance of discarding the counter occurs. Thus, spinlocks allow threads to service interruptions. The spinlock decrements the discard counter when the interrupt is serviced. When the interrupt is serviced, the spin lock discards the ticket for the thread. The spinlock returns so that the thread is assigned a new ticket (eg, an up-to-date ticket number).

As shown in Figure 3, in the second phase, the spin lock can limit the number of threads in this phase. Therefore, no more threads than A will spin in the second phase. The second-stage set of threads can spin on the lock until it becomes available, and then compete for the lock by performing atomic test-and-set operations on the lock's atomic flag. Thus, threads will not necessarily acquire the lock in strict ticket order, since any thread in the second phase may "win" the atomic test-and-set to acquire the lock. Test and set operations can be performed using acquire memory semantics, and the same variable can be stored in it using release semantics in the unlock path to achieve proper memory consistency semantics for the lock. All other atomic operations in the lock/unlock path can use "relaxed" atomics (eg, atomic operations that are not synchronized with any other loads/stores), which will be faster.

A spin lock determines the state of a resource's lock. For example, when controlling access to a resource, a spinlock can allow a predetermined number of threads to access the resource. Typically, a spin lock is a mutual exclusion mechanism that allows only one thread that can write to a resource to acquire the lock. However, in some exemplary embodiments, readers may be separated from writers, where there is only one writer but multiple readers. When determining state, a spinlock checks the resource for a flag that indicates that the resource can be acquired. A spin lock determines whether a resource lock is available. For example, when the department

The lock is available if the system is active and the resource is not fully locked, or if a thread has recently released the resource's lock, either of which causes the resource's lock flag to be set to available. In another example, each lock on a resource is held by a thread such that no locks are available. If no locks are available, continue to monitor the status of resource locks.

If the resource has an available lock, an atomic test-and-set operation is performed, and each spin thread in the second phase competes for the available lock to acquire the resource.

The 0-spin lock determines the ticket of the winning thread exiting the second phase and acquires the lock on the resource. As mentioned above,

Exemplary embodiments may guarantee an upper bound on what must wait in the first and second phases before processing the thread (eg, acquiring a resource). In one operation that enforces this guarantee, a spinlock prevents a thread from entering the second phase when certain conditions apply. A spinlock can determine a condition that the winning thread's ticket is

No is the oldest ticket (eg lowest numbered ticket). In this instance, the thread that won the lock holds the oldest 5 votes, and the spin lock opens the second phase for the spinning thread of the first phase. As mentioned above, the thread that spins in the first phase has the oldest ticket selected to be placed in the second phase. Subsequently, the above method is repeated in the second phase with newly introduced threads; in this instance, the thread that won the lock is not the oldest, and the spinlock closes the second phase to the thread of the first phase. Subsequently, the spin lock returns, and the above method is repeated, and only the remaining threads spin in the second stage.

In the example scenario, the spin lock allows up to three threads to spin in the second phase, while only one lock is available for the resource. Threads in the second phase include threads A, B, and C, from oldest to newest, while thread D is the oldest in the first phase. In the first example, thread A wins the lock. When thread A releases the lock, the spinlock determines that thread A is the oldest, allowing the threads in the first phase to enter the second phase. Thus, thread D can transition from the first phase to the second phase. The threads in the second phase are now threads B, C and D.

In the second example, thread B wins the lock. When thread B releases the lock, the spinlock will determine that thread B holds the oldest ticket because thread A is still in the second phase. Therefore, a spin lock can prevent a new thread from entering the second phase from the first phase. In the next competition, thread A and thread C will compete for the lock. If thread A wins, you can use what you did in the first example. Therefore, when thread A releases the lock, the spin lock will allow the thread in the first stage to enter the second stage. In this case, thread D and thread E can transition from stage one to stage two because there are two slots available in stage two. The threads in the second phase are C, D and E. However, after thread B releases the lock, the operations performed in the second example are repeated if thread C wins. So after thread C releases the lock, the only thing left is thread A. In the absence of other contention, thread A will definitely win the lock on this resource. Since thread A is the oldest, after thread A releases the lock, all three slots are open to threads in the first stage. Therefore, the threads in the second phase are now threads D, E, and F.

The exemplary embodiments provide an apparatus, system, and method that implement a two-phase spinlock that is used in a deterministic manner while enabling interrupts to be serviced while also providing starvation protection. The first stage of a two-stage spinlock controls access to resources, and requests for resources can be processed using a ticket mechanism that sorts requests in chronological order as they are received. Threads in the first phase can service interrupts, specifically based on a drop counter that tracks the number of attempts to enter the second phase of the two-phase spinlock and a spin counter that tracks each attempt to enter the second phase. The second phase of a two-phase spinlock can perform acquire and release operations on a predetermined maximum number of threads allowed to be in the second phase. The spin lock can ensure that only when the oldest ticket thread acquires the resource lock, the new thread can enter the second stage from the first stage.

The above is only a specific embodiment of the application, but the scope of protection of the application is not limited thereto. Any person familiar with the technical field can easily think of changes or substitutions within the technical scope disclosed in the application. All should be covered within the scope of protection of this application. Therefore, the protection scope of the present application should be based on the protection scope of the claims.

Claims (7)

1. A method for implementing a spin lock that optimizes interrupt latency, comprising:

controlling a plurality of threads to access a resource by adopting a two-stage spin lock, wherein the two-stage spin lock comprises a first stage of a plurality of first threads;

receiving a request for a thread to acquire a resource, placing the thread on a first queue associated with a first phase of the two-phase spin lock, determining whether at least one predetermined slot is available in a second phase of the two-phase spin lock, when the slot is not available, processing an interrupt serviced by the selected thread according to a number of attempts by the selected thread to enter the second phase, when at least one slot is available, selecting one of the first threads to enter the second phase according to a time priority order;

determining whether a lock to access the resource is available, selecting one of a plurality of second threads in a second phase of the two-phase spin lock to acquire the lock when the lock is available, determining an age of the selected second thread, and prohibiting any first thread from entering the second phase when the age is not the oldest of the second threads in the second phase; otherwise, when the age is the oldest in the second threads of the second stage, selecting the oldest first thread to enter the second stage;

further requests from the selected thread are received and the selected thread Cheng Fang is in the first queue.

2. The method of claim 1, wherein the act of placing the thread in the first queue is based on an atomic acquire and add operation, the acquire and add operation comprising: each thread is assigned a respective ticket number according to the time priority order.

3. The method of claim 1, wherein determining whether a first counter tracking a first number has been exhausted, the first number corresponding to a number of attempts by the selected thread to enter the second phase;

when the first counter is exhausted, the interrupt cannot be serviced and remains in the first queue;

determining if the second counter passes the selected line Cheng Genzong a second number corresponding to each attempt to enter the second phase when the first counter indicates at least one first opportunity for a corresponding set of attempts;

decrementing the second counter after the selected thread performs the attempt when the second counter indicates at least one second attempt opportunity;

when the second counter is exhausted, an interrupt is received that the selected thread has serviced, and the first counter is decremented.

4. The method of claim 1, wherein when the age is not the oldest in the second threads of the second phase, and the lock is available after the selected second thread releases the lock, selecting from the remaining second threads of the second phase to obtain the lock.

5. The method of claim 1, wherein the selected second thread acquire lock is based on an atomic test and set operation in which the second thread contends for the lock.

6. The method of claim 1, wherein each thread is serviced for a maximum duration.

7. The method of claim 1, wherein the maximum duration is based on a chronological entry of one thread in the first queue, a maximum number of second threads of the second stage configuration, and a number of threads having a lower chronological entry.

Images