Fair spinlock with protection against thread preemption
Techniques can include: thread TH1 acquiring a spinlock; while TH1 holds the spinlock, adding threads TH2 and TH3 to a wait queue based on a FIFO (first in first out) ordering in which threads attempt to acquire the spinlock, where TH1, TH2 and TH3 respectively have positions P 1 , P 2 and P 3 in the FIFO ordering; while TH1 holds the spinlock, pre-empting TH2; while TH2 is inactive and waiting at P 2 in the FIFO ordering of the queue, TH1 releasing the spinlock; detecting that the spinlock is free and that TH3 is waiting in the queue at P 3 , where TH2 is next, in the FIFO ordering of threads in the queue, to acquire the spinlock after released by TH1; and responsive to said detecting, performing first processing including: cancelling the second position or index P 2 of TH2 in the FIFO ordering; and TH3 acquiring the spinlock.
1 . A computer-implemented method comprising:
a first thread TH1 acquiring a spinlock;
while TH1 holds the spinlock, a second thread TH 2 and a third thread TH3 each attempting to acquire the spinlock;
responsive to TH2 and TH3 attempting to acquire the spinlock while held by TH1, adding TH2 and TH3 to a queue of threads waiting to acquire the spinlock, wherein TH2 and TH3 are added to the queue based on a FIFO (first in first out) ordering in which threads attempt to acquire the spinlock, where TH1 has a first position or index P 1 in the FIFO ordering, TH2 has a second position or index P 2 in the FIFO ordering consecutively following TH1, and TH3 has a third position or index P 3 in the FIFO ordering consecutively following TH2;
while TH1 holds the spinlock, pre-empting TH2 so that TH2 becomes inactive;
while TH2 is inactive and waiting at the second position or index P 2 in the FIFO ordering of the queue, TH1 releasing the spinlock so that the spinlock is free;
detecting that the spinlock is free and that TH3 is waiting in the queue at the third position or index P 3 immediately following the second position or index P 2 of TH2, where TH2 is next, in the FIFO ordering of threads in the queue, to acquire the spinlock after released by TH1;
responsive to said detecting, determining that TH2 is inactive and has been pre-empted, and performing first processing including:
saving a copy of the second position or index P 2 in saved information;
cancelling the second position or index P 2 of TH2 in the FIFO ordering; and
TH3 acquiring the spinlock;
subsequent to said canceling, rescheduling TH2 for execution; and
responsive to said rescheduling, TH2 resuming execution, wherein said TH2 resuming execution includes TH2 performing second processing including:
determining, using the copy of the second position or index P 2 , that the second position or index P 2 of TH2 in the FIFO ordering is canceled; and
responsive to determining that the second position or index P 2 of TH2 in the FIFO ordering is canceled, assigning TH2 a fourth position or index P 4 in the FIFO ordering, wherein P 4 has a corresponding position or index in the FIFO ordering subsequent to the third position or index P 3 .
2 . The computer-implemented method of claim 1 , wherein P 4 denotes a position or index in the FIFO ordering at a tail or end of the FIFO ordering such that all threads having corresponding indices less than P 4 occur in the FIFO ordering prior to TH2 such that all threads having corresponding indices less than P 4 are expected to acquire the spinlock prior to TH2.
3 . The computer-implemented method of claim 1 , wherein said detecting is performed by TH 3 having the second position or index P 2 immediately following the first position or index P 1 of TH2.
4 . The computer-implemented method of claim 3 , wherein said detecting includes repeatedly checking a specified number of times that i) the spinlock is free or not taken, and ii) TH 3 is waiting in the queue at the third position or index P 3 immediately following the second position or index P 2 of TH2.
5 . The computer-implemented method of claim 4 , wherein the FIFO ordering is a sequence of consecutive integers such that threads attempting to acquire the spinlock are each assigned a next consecutive integer in the sequence in accordance with an order in which the threads attempt to acquire the spinlock.
6 . The computer-implemented method of claim 5 , wherein while TH 1 holds the spinlock, a first variable, now_serving, is equal to the first position or index P 1 of TH1, and a second variable, lock_taken, is 1 or true to denote the spinlock is taken or held by a corresponding thread TH1 having the first position or index P 1 as indicated by now_serving.
7 . The computer-implemented method of claim 6 , wherein said TH1 releasing the spinlock includes:
incrementing now_serving from P 1 to P 2 denoting that TH2, having the second position or index P 2 , is a next thread following TH1 allowed to acquire the spinlock in accordance with the FIFO ordering; and
updating lock_taken to 0 or false to denote that the spinlock is free and not taken thereby denoting that the spinlock is available for acquisition by a next thread.
8 . The computer-implemented method of claim 7 , wherein said detecting includes:
determining whether lock_taken is 0; and
determining whether a first quantity, now_serving +1, is equal to the third position or index P 3 of TH3.
9 . The computer-implemented method of claim 8 , wherein said TH3 acquiring the spinlock includes:
incrementing now_serving from P 2 to P 3 denoting that TH3, having the third position or index P 3 , is a next thread allowed to acquire the spinlock in accordance with the FIFO ordering; and
updating lock_taken to 1 or true to denote that the spinlock taken or held by a corresponding thread TH 3 having the third position or index P 3 as indicated by now_serving.
10 . The computer-implemented method of claim 1 , further comprising:
subsequent to TH1 acquiring the spinlock, TH1 executing a first critical code section that includes updating one or more data items that are only allowed to be updated by a single thread at a time.
11 . The computer-implemented method of claim 10 , wherein each of TH1, TH2 and TH3 includes a corresponding critical code section the updates said one or more data items whose access is serially synchronized using the spinlock such that a corresponding thread is required to acquire and hold the spinlock in order to provide the corresponding thread with exclusive access to the one or more data items accessed in the corresponding critical code section.
12 . The computer-implemented method of claim 10 , wherein subsequent to TH 1 completing execution of the first critical code section, said TH1 releasing the spinlock so that the spinlock is free.
13 . The computer-implemented method of claim 1 , wherein TH1 and TH2 are added to the queue, in said adding, at a first point in time where TH1 and TH2 are waiting in the queue each executing code in a busy wait loop.
14 . A system comprising:
one or more processors; and
a memory comprising code stored thereon that, when executed, performs a method comprising:
a first thread TH 1 acquiring a spinlock;
while TH1 holds the spinlock, a second thread TH2 and a third thread TH3 each attempting to acquire the spinlock;
responsive to TH2 and TH3 attempting to acquire the spinlock while held by TH1, adding TH2 and TH3 to a queue of threads waiting to acquire the spinlock, wherein TH2 and TH3 are added to the queue based on a FIFO (first in first out) ordering in which threads attempt to acquire the spinlock, where TH1 has a first position or index P 1 in the FIFO ordering, TH2 has a second position or index P 2 in the FIFO ordering consecutively following TH1, and TH3 has a third position or index P 3 in the FIFO ordering consecutively following TH2;
while TH1 holds the spinlock, pre-empting TH2 so that TH2 becomes inactive;
while TH2 is inactive and waiting at the second position or index P 2 in the FIFO ordering of the queue, TH1 releasing the spinlock so that the spinlock is free;
detecting that the spinlock is free and that TH3 is waiting in the queue at the third position or index P 3 immediately following the second position or index P 2 of TH2, where TH2 is next, in the FIFO ordering of threads in the queue, to acquire the spinlock after released by TH1;
responsive to said detecting, determining that TH2 is inactive and has been pre-empted, and performing first processing including:
saving a copy of the second position or index P 2 in saved information;
cancelling the second position or index P 2 of TH2 in the FIFO ordering; and
TH3 acquiring the spinlock;
subsequent to said canceling, rescheduling TH2 for execution; and
responsive to said rescheduling, TH2 resuming execution, wherein said TH 2 resuming execution includes TH2 performing second processing including:
determining, using the copy of the second position or index P 2 , that the second position or index P 2 of TH2 in the FIFO ordering is canceled; and
responsive to determining that the second position or index P 2 of TH2 in the FIFO ordering is canceled, assigning TH 2 a fourth position or index P 4 in the FIFO ordering, wherein P 4 has a corresponding position or index in the FIFO ordering subsequent to the third position or index P 3 .
15 . A non-transitory computer-readable media comprising code stored thereon that, when executed, performs a method comprising:
a first thread TH1 acquiring a spinlock;
while TH1 holds the spinlock, a second thread TH2 and a third thread TH3 each attempting to acquire the spinlock;
responsive to TH2 and TH3 attempting to acquire the spinlock while held by TH1, adding TH2 and TH3 to a queue of threads waiting to acquire the spinlock, wherein TH2 and TH3 are added to the queue based on a FIFO (first in first out) ordering in which threads attempt to acquire the spinlock, where TH1 has a first position or index P 1 in the FIFO ordering, TH2 has a second position or index P 2 in the FIFO ordering consecutively following TH1, and TH3 has a third position or index P 3 in the FIFO ordering consecutively following TH2;
while TH1 holds the spinlock, pre-empting TH2 so that TH2 becomes inactive;
while TH2 is inactive and waiting at the second position or index P 2 in the FIFO ordering of the queue, TH 1 releasing the spinlock so that the spinlock is free;
detecting that the spinlock is free and that TH3 is waiting in the queue at the third position or index P 3 immediately following the second position or index P 2 of TH2, where TH2 is next, in the FIFO ordering of threads in the queue, to acquire the spinlock after released by TH1;
responsive to said detecting, determining that TH2 is inactive and has been pre-empted, and performing first processing including:
saving a copy of the second position or index P 2 in saved information;
cancelling the second position or index P 2 of TH2 in the FIFO ordering; and
TH3 acquiring the spinlock;
subsequent to said canceling, rescheduling TH2 for execution; and
responsive to said rescheduling, TH2 resuming execution, wherein said TH2 resuming execution includes TH2 performing second processing including:
determining, using the copy of the second position or index P 2 , that the second position or index P 2 of TH2 in the FIFO ordering is canceled; and
responsive to determining that the second position or index P 2 of TH2 in the FIFO ordering is canceled, assigning TH2 a fourth position or index P 4 in the FIFO ordering, wherein P 4 has a corresponding position or index in the FIFO ordering subsequent to the third position or index P 3 .